8
$\begingroup$

What do we know about the covering number of $L$-Lipschitz functions mapping say, $\mathbb{R}^n \rightarrow \mathbb{R}$ for some $L >0$?

Only 2 results I have found so far are,

  • That the $\infty$-norm covering number for $L$-Lipschitz functions constrained to map $[0,1]^d \rightarrow [0,1]$ is $\exp\left(\Theta\left( L/\epsilon\right)^d\right)$. And for this I could not find a reference for the proof.

  • Another such $\infty$-norm covering number count for $1$-Lipschitz functions mapping an unit diameter metric space to $[-1,1]$ was given in this previously unanswered question here, metric entropy for Lipschitz functions

    Even here I can't find the proof anywhere and the link in the MO question seems to go to something else (and the original reference in the Uspekhi Mat. Nauk, 1959, Volume 14, Issue 2(86), Pages 3–86, is in Russian and hence I can't read it).

Is there some reason why we don't have (is provably impossible?) such counts when either the range or the domain of the function space is unbounded?

It would be great if someone can maybe reference the proofs for the two results quoted here!

Improve this question
$\endgroup$
4
  • $\begingroup$ Is $\Theta$ just a constant? $\endgroup$
    – Pietro Majer
    Commented Jun 2, 2018 at 14:07
  • $\begingroup$ If the OP (or anyone else) is interested in results of this kind, check out our recent paper which, among other things, estimates covering numbers of functions that are smooth on average -- a much trickier problem! arxiv.org/abs/2007.06283 $\endgroup$
    – Aryeh Kontorovich
    Commented Jan 24, 2023 at 18:25
  • $\begingroup$ may I ask a fundamental (probably stupid) question? I’m new to this area. In the example above “the ∞-norm covering number for L-Lipschitz functions constrained to map [0,1]^d to [0,1], is this function class compact? Thank you. $\endgroup$
    – J M
    Commented Jun 15 at 1:32
  • $\begingroup$ It would be helpful to have a definition of “covering number” in the post. $\endgroup$
    – Nate River
    Commented Jun 15 at 5:43

1 Answer 1

Reset to default
8
$\begingroup$

Here is a reference to a more general result: Lipschitz functions over a doubling metric space (rather than $[0,1]^d$). The $||\cdot||_\infty$ $\epsilon$-metric entropy of such functions is, disregarding log factors, of order $(D/\epsilon)^{ddim}$, where $D$ and $ddim$ are the diameter and doubling dimension of the metric space, respectively. A modern proof may be found in Lemma 4.2 here: https://www.sciencedirect.com/science/article/pii/S0304397515009469

Edit: As pointed out in the comments, the result above is stated without proof. However, a proof is given in Lemma 6 here: https://ieeexplore.ieee.org/document/7944658/

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thanks for the clarifications! So is it provably necessary that the domain and the range be bounded for such a count to be possible? Or is this need a weakness of our current methods? $\endgroup$
    – gradstudent
    Commented May 31, 2018 at 18:40
  • $\begingroup$ I think I am missing something. This Lemma 4.2 or its intermediate Lemma 2.1 dont seem to have been proven in your paper. I dont see the proofs anywhere! $\endgroup$
    – gradstudent
    Commented Jun 1, 2018 at 2:38
  • $\begingroup$ Oops, you're right! I edited the answer, and linked to a paper where the proof appears. $\endgroup$
    – Aryeh Kontorovich
    Commented Jun 1, 2018 at 7:45
  • $\begingroup$ Regarding your first question on the bounded range: yes, it's necessary, even for Lipschitz functions $f:[0,1]\to [a,b]$. You can always rescale either the Lipschitz constant $L$ or the range $b-a$ to be 1, but if either is unbounded, the covering numbers will be infinite. $\endgroup$
    – Aryeh Kontorovich
    Commented Jun 1, 2018 at 7:46
  • $\begingroup$ Also, in any case finitely many balls can't cover an unbounded set, e.g. the constant maps $\endgroup$
    – Pietro Majer
    Commented Jun 2, 2018 at 13:57

You must log in to answer this question.

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