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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.