Taken from paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.

Theorem 3. Let $\mathcal{F}$ be a class of functions from $\mathbb{R}^{d} \rightarrow \mathbb{R}$ and let $\left(x_{i}, y_{i}\right)_{i=1}^{n}$ be i.i.d. input-output pairs in $\mathbb{R}^{d} \times[-1,1]$. Fix $\epsilon, \delta \in(0,1)$.

Assume that:

  1. The function class can be written as $\mathcal{F}=\left\{f_{\boldsymbol{w}}, \boldsymbol{w} \in \mathcal{W}\right\}$ with $\mathcal{W} \subset \mathbb{R}^{p}$, $\operatorname{diam}(\mathcal{W}) \leq W$ and for any $\boldsymbol{w}_{1}, \boldsymbol{w}_{2} \in \mathcal{W}$, $$ \left\|f_{\boldsymbol{w}_{1}}-f_{\boldsymbol{w}_{2}}\right\|_{\infty} \leq J\left\|\boldsymbol{w}_{1}-\boldsymbol{w}_{2}\right\| $$

  2. The distribution $\mu$ of the covariates $x_{i}$ can be written as $\mu=\sum_{\ell=1}^{k} \alpha_{\ell} \mu_{\ell}$, where each $\mu_{\ell}$ satisfies c-isoperimetry.

  3. The expected conditional variance of the output is strictly positive, denoted $\sigma^{2}:=\mathbb{E}^{\mu}[\operatorname{Var}[y \mid x]]>0$.\newline

Then, with probability at least $1-\delta$ with respect to the sampling of the data, one has simultaneously for all $f \in \mathcal{F}$ : $$ \frac{1}{n} \sum_{i=1}^{n}\left(f\left(x_{i}\right)-y_{i}\right)^{2} \leq \sigma^{2}-\epsilon \Rightarrow \operatorname{Lip}(f) \geq \frac{\epsilon}{2^{9} \sqrt{c}} \sqrt{\frac{n d}{p \log \left(60 W J \epsilon^{-1}\right)+\log (4 / \delta)}} . $$

Proof. Define $\mathcal{W}_{L} \subseteq \mathcal{W}$ by $\mathcal{W}_{L}=\left\{\boldsymbol{w} \in \mathcal{W}: \operatorname{Lip}\left(f_{\boldsymbol{w}}\right) \leq L\right\}$. Denote $\mathcal{W}_{L, \epsilon}$ for an $\frac{\epsilon}{6 J}$-net of $\mathcal{W}_{L}$. We have in particular $\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$. We apply Theorem 2 to $\mathcal{F}_{L, \epsilon}=\left\{f_{\boldsymbol{w}}, \boldsymbol{w} \in \mathcal{W}_{L, \epsilon}\right\}$ :

This continues .........

I feel curious to know the size of a $\epsilon$-net Vector Space.

How $\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$???

Edit:- Corollary 4.2.13 (Covering numbers of the Euclidean ball). The covering numbers of the unit Euclidean ball $B_{2}^{n}$ satisfy the following for any $\varepsilon>0$ : $$ \left(\frac{1}{\varepsilon}\right)^{n} \leq \mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq\left(\frac{2}{\varepsilon}+1\right)^{n} . $$ The same upper bound is true for the unit Euclidean sphere $S^{n-1}$. Proof The lower bound follows immediately from Proposition 4.2.12, since the volume in $\mathbb{R}^{n}$ scales as $$ \left|\varepsilon B_{2}^{n}\right|=\varepsilon^{n}\left|B_{2}^{n}\right| . $$ The upper bound follows from Proposition 4.2.12, too: $$ \mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq \frac{\left|(1+\varepsilon / 2) B_{2}^{n}\right|}{\left|(\varepsilon / 2) B_{2}^{n}\right|}=\frac{(1+\varepsilon / 2)^{n}}{(\varepsilon / 2)^{n}}=\left(\frac{2}{\varepsilon}+1\right)^{n} . $$ The upper bound for the sphere can be proved in the same way. To simplify the bound a bit, note that in the non-trivial range $\varepsilon \in(0,1]$ we have $$ \left(\frac{1}{\varepsilon}\right)^{n} \leq \mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq\left(\frac{3}{\varepsilon}\right)^{n}.............(1) $$

By the inequality 1 I am able to reach that

$$\mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq\left(\frac{18J}{\varepsilon}\right)^{p}.$$ This is not dependent on $W$ right. How can we scale it down then?


2 Answers 2


Note that $\mathcal{W}_{\epsilon}$ is an epsilon-net in the parametrization space, which is just $p$-dimensional Euclidean space. (So there is no need to think about covering numbers in e.g. spaces of functions; there seems to be some confusion in the other discussion.) The result being used is here: https://mathoverflow.net/questions/356310/covering-number-of-l-2-ball-in-mathbbrd. The constant 60 is definitely a bit loose :).

To prove this covering number bound, the idea is to greedily choose a finite subset of points, so that the balls of radius $\eta/2$ around them are disjoint (where in this case, $\eta=\frac{\epsilon}{6J}$). By considering volumes, you can upper-bound the number of balls by $(60WJ\epsilon^{-1})^p$. Moreover, you can show that once there is no room to add another point, increasing the radius of these balls from $\eta/2$ to $\eta$ covers the whole region. So taking their centers as the set $\mathcal{W}_{\epsilon}$ does the job.

  • $\begingroup$ $(1/\epsilon)^d \le N(\epsilon, B_2) \le (3/\epsilon)^d$. this eventually leads $(\frac{18J}{\epsilon})^p$ . .. how it is matching with the result of paper? :( $\endgroup$
    – XYZ
    Commented May 7, 2022 at 22:22
  • $\begingroup$ It's an upper bound, so it is okay that 60 is larger than necessary. You do need the factor of $W$ inside the $p$-th power though. This is because it's an $\epsilon$ cover of a radius $W$ ball, while the bound you quoted from the link is for a radius $1$ ball. $\endgroup$ Commented May 7, 2022 at 22:28
  • $\begingroup$ Ok Mark got some insight . Some doubts are still in my head. So epsilon / 6j is the radius of 1 ball. Diam(w) < W is given, Does this imply that there are atmost W balls? That's why the W factor needed !! $\endgroup$
    – XYZ
    Commented May 7, 2022 at 22:48
  • $\begingroup$ Diameter ≤ W means the set is contained inside a ball of radius W. So you can scale everything down by a factor of W and apply the result that you quoted. This scaling down also turns $\epsilon$ into $\epsilon/W$, so you end up with an extra $W$ factor inside the $p$-th power. $\endgroup$ Commented May 7, 2022 at 22:56
  • $\begingroup$ Okay so this leads to $\frac{\epsilon}{6JW}$ and eventuall by that inequality $N(\epsilon,B_{2}) \leq (\frac{18WJ}{\epsilon})^p.$ that is great. But unable to find why $\frac{\epsilon}{W}$ is happening here. The radius of the Ball is $W$ and there are of small balls with $\frac{\epsilon}{6J}$ which can cover the Ball. why the scaling is eventually needed to determine the upper-bound $\endgroup$
    – XYZ
    Commented May 8, 2022 at 5:55

See, for example, Lee-Ad Gottlieb, Aryeh Kontorovich, Robert Krauthgamer: Efficient Regression in Metric Spaces via Approximate Lipschitz Extension. IEEE Trans. Inf. Theory 63(8): 4838-4849 (2017) https://arxiv.org/pdf/1111.4470.pdf enter image description here

If you're wondering about the extra log factor, there's a refinement in the case of connected spaces: enter image description here (see, e.g.,

Aryeh Kontorovich, Roi Weiss: Maximum Margin Multiclass Nearest Neighbors. ICML 2014: 892-900 https://www.cs.bgu.ac.il/~karyeh/max-margin-multi-nn.pdf )


Edit. It appears that the claim $\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$ is incorrect -- it should be $\log\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$.

You can find a very readable proof for the Euclidean case in Wainwright's book,"High-Dimensional Statistics" enter image description here ... enter image description here


Edit II. I retract my comment about a possible mistake in the paper. Please see Mark Sellke's answer. Leaving mine up for pedagogical reasons only.

  • $\begingroup$ Notice that the results I quote all have diam=1. You can rescale to diam=W, and you pay for it in the numerator (it multiplies the Lipschitz constant, which is L in my notation and J in yours). $\endgroup$
    – Aryeh
    Commented May 7, 2022 at 21:02
  • $\begingroup$ As for the constant 60, you can probably do much better (as the bounds I quote suggest). $\endgroup$
    – Aryeh
    Commented May 7, 2022 at 21:03
  • $\begingroup$ Again, I am not getting. If I use lemma 5.2 , will come up with $(\frac{16J}{\epsilon})^W$. $\endgroup$
    – XYZ
    Commented May 7, 2022 at 21:09
  • $\begingroup$ No no. Modulo constants, it's (Lip*diam/eps)^dim . $\endgroup$
    – Aryeh
    Commented May 7, 2022 at 21:17
  • $\begingroup$ Oops, it appears that there was a missing log in the claim -- see my updated answer. $\endgroup$
    – Aryeh
    Commented May 7, 2022 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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