2
$\begingroup$

For some $L>0$ say ${\cal L}$ is the space of all $L-$Lipschitz functions mapping $(X,\rho) \rightarrow [0,1]$ where $(X,\rho)$ is a metric space.

  • For any $\alpha >0$ do we know of a lowerbound on the $\alpha-$packing number of ${\cal L}$ assuming boundedness (or even compactness) of $(X,\rho)$?

On the function space I am assuming a a pseudo metric which is defined as follows : i.e for any $2$ functions $f$ and $g$ we have, the distance between them defined as, $d(f,g) = \frac{1}{n} \sum_{i=1}^n \vert f(x_i) - g(x_i) \vert$ for some choice of $n$ points $\{ x_1,..,x_n\}$ in the common domain of the functions i.e $X$.

Improve this question
$\endgroup$
6
  • $\begingroup$ No. Packing number and covering number are roughly of the same order of magnitude but they are not the same things. Though a lowerbound on the covering number will imply a lowerbound on the packing number at a different scale. $\endgroup$
    – gradstudent
    Commented Jun 27, 2018 at 16:45
  • 1
    $\begingroup$ Maybe "$\alpha$-packing number"=maximum number of disjoint balls of radius $\alpha$? $\endgroup$
    – Pietro Majer
    Commented Jun 27, 2018 at 17:04
  • $\begingroup$ Yes. Typically one is doing these under a "pesudo-metric" whereby some $n$ points in the domain has been chosen and one defines the distance between two functions $f$ and $g$ as, $d(f,g) := \frac{1}{n} \sum_{i=1}^n \vert f(x_i) - g(x_i) \vert$ $\endgroup$
    – gradstudent
    Commented Jun 27, 2018 at 17:20
  • $\begingroup$ You have to tell us what the metric on $\mathcal{L}$ is before this is a meaningful question. $\endgroup$
    – Nik Weaver
    Commented Jun 27, 2018 at 18:53
  • $\begingroup$ I mentioned the pseudo-metric in the comment just above yours. $\endgroup$
    – gradstudent
    Commented Jun 27, 2018 at 20:54

1 Answer 1

Reset to default
3
$\begingroup$

Suppose the metric space $(X,\rho)$ has $\alpha$-packing numbers $M(\alpha)$. Then the function class $\mathcal{L}$ has $\gamma$-fat shattering dimension $M(2\gamma/L)$ --- see here https://ieeexplore.ieee.org/document/6867374/ for the relevant definitions as well as a proof of this claim (Theorem 1).

The fat-shattering estimate implies an upper bound on the $\alpha$-packing numbers of $\mathcal{L}$: these are at most $$ \left(\frac2\alpha\right)^{K M(c\alpha/L)} $$ for universal constants $K,c>0$; see Theorerm 2.18 in Mendelson's "A few notes on Statistical Learning Theory", https://people.eecs.berkeley.edu/~jordan/courses/281B-spring04/readings/mendelson.ps

A lower bound bound of $(c'/\alpha)^{M(c''\alpha/L)}$ follows from the discussion in this question, metric entropy for Lipschitz functions --- since the $L_\infty$ covering numbers always majorize the $L_1$ ones.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .