1
$\begingroup$

On page 12 of the slide deck here, the author gives an example where a lower bound (and upper bound, but I am particularly interested in the lower bound) on the $\epsilon$-covering number of a Lipschitz function space $\mathbf{F}$ is constructed. It is assumed that every $f\in\mathbf{F}$ is a function $f:[0,1]\to [0,1]$.

A proof idea for the upper bound is also provided in the slide deck. It seems that the intuition is to form a collection of zig-zag paths such that for any $L$-Lipschitz function $f$ in the unit square there is a path that remains within $\epsilon$ of it in the supremum norm. An upper bound on the covering number is then constructed by counting how many such paths there are using a combinatorial argument. In particular, the authors claim that, \begin{eqnarray} \log_2 (\epsilon\text{-convering number}) = \mathcal{O}\left(\frac{L}{\epsilon}\right). \end{eqnarray}

At any rate I get how this upper bound is constructed but I am not seeing how the logic also applies to obtaining a lower bound on the covering number. In particular, how can they also claim. \begin{eqnarray} \log_2 (\epsilon\text{-convering number}) = \Omega\left(\frac{L}{\epsilon}\right)? \end{eqnarray}

It'd be great if anyone can help me see why this is true.

$\endgroup$
1

1 Answer 1

0
$\begingroup$

On slide 12 it is also noted that the constructed set $\left\{ y_j \right\}$, $j=1, \dots, 2^{L/\varepsilon}$, of piecewise linear functions is also an $\varepsilon/2$-packing, meaning that $$ \left\Vert y_i - y_j \right\Vert > \varepsilon/2 \quad \mbox{ for all }i\ne j.$$ Now, for any $\varepsilon/4$-cover of $\mathbf F$ for each $y_j$ we can find a point in this cover which is in the $\varepsilon/4$ ball around $y_j$. This way we can assign to each $y_j$ a unique element of the cover set, meaning that the $\varepsilon/4$-covering number $N(\varepsilon/4)$ cannot be smaller than $2^{L/\varepsilon}$, the $\varepsilon/2$-packing number. Thus, $$\log_2 N(\varepsilon) \geq L/(4\varepsilon),$$ providing the lower bound.

$\endgroup$

You must log in to answer this question.

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