<p>Note that <span class="math-container">$\mathcal{W}_{\epsilon}$</span> is an epsilon-net in the parametrization space, which is just <span class="math-container">$p$</span>-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: <a href="https://mathoverflow.net/questions/356310/covering-number-of-l-2-ball-in-mathbbrd">https://mathoverflow.net/questions/356310/covering-number-of-l-2-ball-in-mathbbrd</a>. The constant 60 is definitely a bit loose :).</p>
<p>To prove this covering number bound, the idea is to greedily choose a finite subset of points, so that the balls of radius <span class="math-container">$\eta/2$</span> around them are disjoint (where in this case, <span class="math-container">$\eta=\frac{\epsilon}{6J}$</span>). By considering volumes, you can upper-bound the number of balls by <span class="math-container">$(60WJ\epsilon^{-1})^p$</span>. Moreover, you can show that once there is no room to add another point, increasing the radius of these balls from <span class="math-container">$\eta/2$</span> to <span class="math-container">$\eta$</span> covers the whole region. So taking their centers as the set <span class="math-container">$\mathcal{W}_{\epsilon}$</span> does the job.</p>

CC BY-SA 4.0
2022-05-07T22:22:21.070Z
$(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? :(
XYZ
CC BY-SA 4.0
2022-05-07T22:28:37.960Z
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.
Mark Sellke
CC BY-SA 4.0
2022-05-07T22:48:03.447Z
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 !!
XYZ
CC BY-SA 4.0
2022-05-07T22:56:13.993Z
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.
Mark Sellke
CC BY-SA 4.0
2022-05-08T05:55:55.613Z
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
XYZ
CC BY-SA 4.0
2022-05-07T22:12:33.387Z
2022-05-07T22:12:33.387Z
Mark Sellke
<p>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)
<a href="https://arxiv.org/pdf/1111.4470.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1111.4470.pdf</a>
<a href="https://i.sstatic.net/FokEk.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FokEk.png" alt="enter image description here" /></a></p>
<p>If you're wondering about the extra log factor, there's a refinement in the case of connected spaces:
<a href="https://i.sstatic.net/fYAdj.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/fYAdj.png" alt="enter image description here" /></a>
(see, e.g.,</p>
<p>Aryeh Kontorovich, Roi Weiss:
Maximum Margin Multiclass Nearest Neighbors. ICML 2014: 892-900
<a href="https://www.cs.bgu.ac.il/%7Ekaryeh/max-margin-multi-nn.pdf" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~karyeh/max-margin-multi-nn.pdf</a>
)</p>
<p>=======================================================</p>
<p>Edit.
It appears that the claim <span class="math-container">$\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$</span>
is incorrect -- it should be
<span class="math-container">$\log\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$</span>.</p>
<p>You can find a very readable proof for the Euclidean case in Wainwright's book,&quot;High-Dimensional Statistics&quot;
<a href="https://i.sstatic.net/DZD1Q.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DZD1Q.png" alt="enter image description here" /></a>
...
<a href="https://i.sstatic.net/tIK5d.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/tIK5d.png" alt="enter image description here" /></a></p>
<p>=======================================================</p>
<p>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.</p>

CC BY-SA 4.0
2022-05-07T21:02:33.727Z
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).
Aryeh
CC BY-SA 4.0
2022-05-07T21:03:24.013Z
As for the constant 60, you can probably do much better (as the bounds I quote suggest).
Aryeh
CC BY-SA 4.0
2022-05-07T21:09:51.113Z
Again, I am not getting. If I use lemma 5.2 , will come up with $(\frac{16J}{\epsilon})^W$.
XYZ
CC BY-SA 4.0
2022-05-07T21:17:43.163Z
No no. Modulo constants, it's (Lip*diam/eps)^dim .
Aryeh
CC BY-SA 4.0
2022-05-07T21:25:55.500Z
Oops, it appears that there was a missing log in the claim -- see my updated answer.
Aryeh
CC BY-SA 4.0
2022-05-07T21:26:44.623Z
Ok so diam here refers to diameter?  as per your notation, and $(\frac{6JW}{\epsilon})^p$...
XYZ
CC BY-SA 4.0
2022-05-07T21:27:39.330Z
See my edit and apparent mistake in the OP.
Aryeh
CC BY-SA 4.0
2022-05-07T21:28:12.663Z
Kindly see the original paper. It was written there only.
XYZ
CC BY-SA 4.0
2022-05-07T21:33:43.030Z
It appears to be a mistake -- there's a missing log. I'll write to them.
Aryeh
CC BY-SA 4.0
2022-05-07T21:36:40.203Z
Can you please elaborate the proof in steps? I am not getting it right in my head how it is coming :( $\log\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$.
XYZ
CC BY-SA 4.0
2022-05-07T21:45:19.633Z
I added a reference to a simpler proof of a special case, which should be enough for your needs. Do you understand Wainwright's proof?
Aryeh
CC BY-SA 4.0
2022-05-07T22:17:43.933Z
According to that proof , it is coming with $(\frac{6J}{\epsilon})^p$
XYZ
CC BY-SA 4.0
2022-05-07T22:24:09.073Z
Please see Mark Sellke's answer.
Aryeh
CC BY-SA 4.0
2022-05-07T20:51:45.310Z
2022-05-07T22:25:10.860Z
2022-05-07T22:25:10.860Z
Aryeh
<p>Taken from paper <a href="https://arxiv.org/pdf/2105.12806.pdf" rel="nofollow noreferrer">&quot;A Universal Law of Robustness via isoperimetry&quot;</a> by Bubeck and Sellke.</p>
<p><strong>Theorem 3.</strong> Let <span class="math-container">$\mathcal{F}$</span> be a class of functions from <span class="math-container">$\mathbb{R}^{d} \rightarrow \mathbb{R}$</span> and let <span class="math-container">$\left(x_{i}, y_{i}\right)_{i=1}^{n}$</span> be i.i.d. input-output pairs in <span class="math-container">$\mathbb{R}^{d} \times[-1,1]$</span>. Fix <span class="math-container">$\epsilon, \delta \in(0,1)$</span>.</p>
<p>Assume that:</p>
<ol>
<li><p>The function class can be written as <span class="math-container">$\mathcal{F}=\left\{f_{\boldsymbol{w}}, \boldsymbol{w} \in \mathcal{W}\right\}$</span> with <span class="math-container">$\mathcal{W} \subset \mathbb{R}^{p}$</span>, <span class="math-container">$\operatorname{diam}(\mathcal{W}) \leq W$</span> and for any <span class="math-container">$\boldsymbol{w}_{1}, \boldsymbol{w}_{2} \in \mathcal{W}$</span>,
<span class="math-container">$$
\left\|f_{\boldsymbol{w}_{1}}-f_{\boldsymbol{w}_{2}}\right\|_{\infty} \leq J\left\|\boldsymbol{w}_{1}-\boldsymbol{w}_{2}\right\|
$$</span></p>
</li>
<li><p>The distribution <span class="math-container">$\mu$</span> of the covariates <span class="math-container">$x_{i}$</span> can be written as <span class="math-container">$\mu=\sum_{\ell=1}^{k} \alpha_{\ell} \mu_{\ell}$</span>, where each <span class="math-container">$\mu_{\ell}$</span> satisfies c-isoperimetry.</p>
</li>
<li><p>The expected conditional variance of the output is strictly positive, denoted <span class="math-container">$\sigma^{2}:=\mathbb{E}^{\mu}[\operatorname{Var}[y \mid x]]&gt;0$</span>.\newline</p>
</li>
</ol>
<p>Then, with probability at least <span class="math-container">$1-\delta$</span> with respect to the sampling of the data, one has simultaneously for all <span class="math-container">$f \in \mathcal{F}$</span> :
<span class="math-container">$$
\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)}} .
$$</span></p>
<p><strong>Proof.</strong> Define <span class="math-container">$\mathcal{W}_{L} \subseteq \mathcal{W}$</span> by <span class="math-container">$\mathcal{W}_{L}=\left\{\boldsymbol{w} \in \mathcal{W}: \operatorname{Lip}\left(f_{\boldsymbol{w}}\right) \leq L\right\}$</span>. Denote <span class="math-container">$\mathcal{W}_{L, \epsilon}$</span> for an <span class="math-container">$\frac{\epsilon}{6 J}$</span>-net of <span class="math-container">$\mathcal{W}_{L}$</span>. We have in particular <span class="math-container">$\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$</span>. We apply Theorem 2 to <span class="math-container">$\mathcal{F}_{L, \epsilon}=\left\{f_{\boldsymbol{w}}, \boldsymbol{w} \in \mathcal{W}_{L, \epsilon}\right\}$</span> :</p>
<p>This continues .........</p>
<p>I feel curious  to know the size of a <span class="math-container">$\epsilon$</span>-net Vector Space.</p>
<blockquote>
<p>How <span class="math-container">$\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$</span>???</p>
</blockquote>
<hr />
<p>Edit:- Corollary 4.2.13 (Covering numbers of the Euclidean ball). The covering numbers of the unit Euclidean ball <span class="math-container">$B_{2}^{n}$</span> satisfy the following for any <span class="math-container">$\varepsilon&gt;0$</span> :
<span class="math-container">$$
\left(\frac{1}{\varepsilon}\right)^{n} \leq \mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq\left(\frac{2}{\varepsilon}+1\right)^{n} .
$$</span>
The same upper bound is true for the unit Euclidean sphere <span class="math-container">$S^{n-1}$</span>.
Proof The lower bound follows immediately from Proposition 4.2.12, since the volume in <span class="math-container">$\mathbb{R}^{n}$</span> scales as
<span class="math-container">$$
\left|\varepsilon B_{2}^{n}\right|=\varepsilon^{n}\left|B_{2}^{n}\right| .
$$</span>
The upper bound follows from Proposition 4.2.12, too:
<span class="math-container">$$
\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} .
$$</span>
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 <span class="math-container">$\varepsilon \in(0,1]$</span> we have
<span class="math-container">$$
\left(\frac{1}{\varepsilon}\right)^{n} \leq \mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq\left(\frac{3}{\varepsilon}\right)^{n}.............(1)
$$</span></p>
<p>By the inequality 1 I am able to reach that</p>
<p><span class="math-container">$$\mathcal{N}\left(B_{2}^{n}, \varepsilon\right) \leq\left(\frac{18J}{\varepsilon}\right)^{p}.$$</span> This is not dependent on <span class="math-container">$W$</span> right. How can we scale it down then?</p>

<pr.probability><vc-dimension><high-dimensional-geometry><epsilon-nets>
How to find the size of an ϵ-net of a vector space?
XYZ
# How to find the size of an ϵ-net of a vector space?

(Asked by: username_0 on 2022-05-07)

Taken from paper ["A Universal Law of Robustness via isoperimetry"](https://arxiv.org/pdf/2105.12806.pdf) 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?

**Tags:** pr.probability, vc-dimension, high-dimensional-geometry, epsilon-nets

---

## 2 answers

### Answer by username_1 on 2022-05-07. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_0**: $(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? :(  
> **username_1**: 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.  
> **username_0**: 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 !!  
> **username_1**: 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.  
> **username_0**: 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  

---

### Answer by username_2 on 2022-05-07. Score: 0

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](https://i.sstatic.net/FokEk.png)](https://i.sstatic.net/FokEk.png)

If you're wondering about the extra log factor, there's a refinement in the case of connected spaces:
[![enter image description here](https://i.sstatic.net/fYAdj.png)](https://i.sstatic.net/fYAdj.png)
(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](https://www.cs.bgu.ac.il/%7Ekaryeh/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](https://i.sstatic.net/DZD1Q.png)](https://i.sstatic.net/DZD1Q.png)
...
[![enter image description here](https://i.sstatic.net/tIK5d.png)](https://i.sstatic.net/tIK5d.png)

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

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.

> **Comments:**
> **username_2**: 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).  
> **username_2**: As for the constant 60, you can probably do much better (as the bounds I quote suggest).  
> **username_0**: Again, I am not getting. If I use lemma 5.2 , will come up with $(\frac{16J}{\epsilon})^W$.  
> **username_2**: No no. Modulo constants, it's (Lip*diam/eps)^dim .  
> **username_2**: Oops, it appears that there was a missing log in the claim -- see my updated answer.  
> **username_0**: Ok so diam here refers to diameter?  as per your notation, and $(\frac{6JW}{\epsilon})^p$...  
> **username_2**: See my edit and apparent mistake in the OP.  
> **username_0**: Kindly see the original paper. It was written there only.  
> **username_2**: It appears to be a mistake -- there's a missing log. I'll write to them.  
> **username_0**: Can you please elaborate the proof in steps? I am not getting it right in my head how it is coming :( $\log\left|\mathcal{W}_{\epsilon}\right| \leq\left(60 W J \epsilon^{-1}\right)^{p}$.  
> **username_2**: I added a reference to a simpler proof of a special case, which should be enough for your needs. Do you understand Wainwright's proof?  
> **username_0**: According to that proof , it is coming with $(\frac{6J}{\epsilon})^p$  
> **username_2**: Please see Mark Sellke's answer.  

---

