How to find the size of an ϵ-net of a vector space?

Question

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?

Answer 1

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.

Answer 2

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

If you're wondering about the extra log factor, there's a refinement in the case of connected spaces: (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" ...

=======================================================

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.