<p>This follows from Massart's finite class lemma. Let $F$ is a binary function class restricted to some set $\{X_1,\ldots,X_n\}$, and let $P_n$ be the empirical (i.e., uniform) measure on this set. Then, for any $\epsilon&gt;0$, the empirical Rademacher complexity of $F$ is bounded by
$$ R_n(F;X) \le \epsilon + \sqrt{\frac{2\log N_F(\epsilon)}{n}},$$
where $N_F(\epsilon)$ is the $\ell_2$ $\epsilon$-covering number of $F$ w.r.t. $P_n$. This is proved in display (1) here:
<a href="https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf</a>
-- check out the course notes:
<a href="https://www.cs.bgu.ac.il/~asml162/Class_Material" rel="nofollow noreferrer">https://www.cs.bgu.ac.il/~asml162/Class_Material</a></p>

CC BY-SA 3.0
2018-03-27T19:51:39.043Z
Oh interesting. So it's a considerably more advanced result than plain PAC. Will have a look at those, thanks!
guillefix
CC BY-SA 3.0
2018-03-27T19:54:19.830Z
I'd say it's less difficult than, say, the standard PAC bounds, which rely on the "deep" Sauer's Lemma -- while this is really just a clever use of Hoeffding + union bound.
Aryeh
CC BY-SA 3.0
2018-03-27T19:55:43.203Z
I was referring to the non-VC PAC bounds.
But I thought that stuff with Rademacher complexity was on a similar level than VC stuff, or more advanced. But I'm not very familiar with it.
guillefix
CC BY-SA 3.0
2018-03-27T19:58:12.387Z
BTW, feel free to accept so the question doesn't linger in the queue :)
Aryeh
CC BY-SA 3.0
2018-03-28T12:25:29.627Z
On a side note, I like how in learning theory what is essentially "Chernoff + union bound" is named after a person :)
Sasho Nikolov
CC BY-SA 3.0
2018-03-28T12:29:22.643Z
@SashoNikolov you bring up an interesting meta-point that may be worthy of its own post. Massart's finite class lemma is indeed a rather trivial result, likely folklore long before he published it. But he's a famous probabilist, well-known for highly non-trivial results (such computing the optimal constants in the DKW inequality). I've observed that famous people often have simple results named after them, and this is not unique to learning theory. Just look at the Johnson-Lindenstrauss lemma -- certainly not the deepest or most difficult, thought probably what they're best known for.
Aryeh
CC BY-SA 3.0
2018-03-28T16:33:57.830Z
I agree :). I think "Chernoff bound" is an even better example. Chernoff considered it a minor lemma in a paper, whose proof he had learned from Rubin. The proof technique is at least thirty years older than Chernoff's paper, and dates back to the work of Sergei Bernstein. But the name took off.
Sasho Nikolov
CC BY-SA 3.0
2018-03-28T19:47:43.470Z
@SashoNikolov [Bring back Legendre's constant!](https://en.wikipedia.org/wiki/Legendre%27s_constant)
Clement C.
CC BY-SA 3.0
2018-03-29T15:27:01.977Z
Oh, actually, the pdf you linked doesn't contain the proof?
guillefix
CC BY-SA 3.0
2018-03-29T15:30:40.610Z
You're right, it's proven in a note mentioned in (a note mentioned in) there -- so two hops away :)
http://www.cs.berkeley.edu/~bartlett/courses/281b-sp06/lecture23.ps
Aryeh
CC BY-SA 3.0
2018-03-29T15:31:11.230Z
Thm. 1.1 in that .ps file
Aryeh
CC BY-SA 3.0
2018-03-29T15:46:18.843Z
Yeah, I found it through the two hops. Also had to google Massart's lemma
guillefix
CC BY-SA 3.0
2018-03-29T15:46:26.587Z
Indeed -- that's the note I just linked.
Aryeh
CC BY-SA 3.0
2018-03-29T15:47:43.383Z
Massart's lemma is really nothing more than this: https://www.cs.bgu.ac.il/~asml162/wiki.files/Expected%20maximum%20of%20subgaussian%20variables.pdf
Aryeh
CC BY-SA 3.0
2018-03-27T19:34:12.350Z
2018-03-27T19:34:12.350Z
Aryeh
<p>Let the risk be a random variable, by the Chernoff-Hoeffding's inequality, you can bound the approximation to the true risk:
<span class="math-container">\begin{align}
   P \left(\Bigg | \frac{1}{n} \sum_{i=1}^{n}\xi_i -
  \mathbb{E}(\xi) \Bigg | \geq  \epsilon \right)  &amp;\leq 2 \exp(-2n\epsilon^2)\\
  P(|\hat{R}_{S}(h) - R(h)| \geq \epsilon) &amp;\leq 2 \exp(-2n\epsilon^2)
\end{align}</span></p>

<p>Unfortunately, this bound only holds for a fixed function <span class="math-container">$h$</span> which does not depend on the training data, but our hypothesis certainly does depend. The reason for such constraint is intuitive. If we let the hypothesis space convey all possible functions and do not restrict our hypothesis to not depend on the training data, we can always generate a function that ``memorises'' the given sample and has no empirical error. Such function will most certainly not generalise well and invalidate the bound.</p>

<p>Vapnik and Chervonenkis solved this conundrum by using the union bound.</p>

<p>==Union Bound==</p>

<p>If we enumerate all the functions in <span class="math-container">$H$</span>, using the fact that it is finite (it is a <span class="math-container">$\epsilon$</span>-cover of <span class="math-container">$H$</span>), the bound still holds for each hypothesis:
<span class="math-container">\begin{align}
 P(|\hat{R}_{S}(h_1) - R(h_1) | &gt; \epsilon) &amp;\lor \nonumber \\
 P(|\hat{R}_{S}(h_2)-R(h_2)| &gt; \epsilon) &amp;\lor  \cdots \nonumber \\
 P(|\hat{R}_{S}(h_{|H|})-R(h_{|H|})| &gt; \epsilon)
 &amp;\leq \sum^{|H|} 2 \exp(-2n\epsilon^2) \nonumber\\
 \therefore P(\sup_{h \in H}|\hat{R}_{S}(h) - R(h)| &gt;\epsilon)
 &amp;\leq 2 |H| \exp(-2n\epsilon^2)\\
 P\left[ \exists h \in H:~|\hat{R}_{S}(h) - R(h)| &gt;\epsilon\right]
 &amp;\leq 2 |H| \exp(-2n\epsilon^2)
\end{align}</span>
    <span class="math-container">\begin{align}
  P\left[ \exists h \in H:~|\hat{R}_{S}(h) - R(h)| &gt;\epsilon\right]
 &amp;&lt; \delta \tag{PAC}\\
 P\left[ \exists h \in H:~|\hat{R}_{S}(h) - R(h)| &gt;\epsilon\right]
 &amp;\leq 2 |H| \exp(-2n\epsilon^2) \\
 \therefore \delta &amp;&gt; 2 |H| \exp(-2n\epsilon^2)
 \end{align}</span>
Assuming <span class="math-container">$\delta = 2 |H| \exp(-2n\epsilon^2)$</span>, we have:
<span class="math-container">\begin{align}
 \exp(-2n\epsilon^2) = \frac{\delta}{2|H|} \\
 -2n\epsilon^2 = \ln{\delta} - ln{2|H|}\\
 \epsilon^2 = \frac{\ln{|H|}+\ln{2}-\ln{\delta}}{2n}\\
 \therefore \epsilon &gt; 0 \rightarrow \epsilon = + \sqrt{\frac{\ln{|H|}+ \ln{2/\delta}}{2n}}
\end{align}</span></p>

CC BY-SA 4.0
2020-02-06T03:22:26.630Z
2020-02-06T03:22:26.630Z
Fred Guth
<p>In <a href="https://youtu.be/EQTtBRM0sIs?t=42m55s" rel="nofollow noreferrer">this video at 43:00</a>, a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted:</p>

<p>$$\epsilon^2 &lt; \frac{\log{|H_\epsilon|} + \log{1/\delta}}{2m}$$</p>

<p>where $m$ is the number of samples, $\delta$ is the confidence parameter, and $H_\epsilon$ is the cardinality of an "$\epsilon$-cover of the hypothesis class", where he defines an $\epsilon$-cover as a set of subsets of the hypothesis class, such that the probability that two hypothesis in the same subset disagree is less than $\epsilon$.</p>

<p>Apart from the fact that this isn't a formal statement, I couldn't prove this myself. Has anyone heard of this version of PAC, and if so, could they point me to resources explaining it, or give some explanation here?</p>

<machine-learning><vc-dimension><pac-learning>
PAC-learning bound with epsilon-cover of hypothesis class
guillefix
# PAC-learning bound with epsilon-cover of hypothesis class

(Asked by: username_0 on 2018-03-27)

In [this video at 43:00](https://youtu.be/EQTtBRM0sIs?t=42m55s), a version of the PAC bound for generalization error $\epsilon$, which I hadn't seen before, is quoted:

$$\epsilon^2 < \frac{\log{|H\_\epsilon|} + \log{1/\delta}}{2m}$$

where $m$ is the number of samples, $\delta$ is the confidence parameter, and $H\_\epsilon$ is the cardinality of an "$\epsilon$-cover of the hypothesis class", where he defines an $\epsilon$-cover as a set of subsets of the hypothesis class, such that the probability that two hypothesis in the same subset disagree is less than $\epsilon$.

Apart from the fact that this isn't a formal statement, I couldn't prove this myself. Has anyone heard of this version of PAC, and if so, could they point me to resources explaining it, or give some explanation here?

**Tags:** machine-learning, vc-dimension, pac-learning


---

## 2 answers

### Answer by username_1 on 2018-03-27. Score: 4 | Accepted answer

This follows from Massart's finite class lemma. Let $F$ is a binary function class restricted to some set $\{X\_1,\ldots,X\_n\}$, and let $P\_n$ be the empirical (i.e., uniform) measure on this set. Then, for any $\epsilon>0$, the empirical Rademacher complexity of $F$ is bounded by
$$ R\_n(F;X) \le \epsilon + \sqrt{\frac{2\log N\_F(\epsilon)}{n}},$$
where $N\_F(\epsilon)$ is the $\ell\_2$ $\epsilon$-covering number of $F$ w.r.t. $P\_n$. This is proved in display (1) here:
<https://www.cs.bgu.ac.il/~asml162/wiki.files/dudley-pollard.pdf>
-- check out the course notes:
<https://www.cs.bgu.ac.il/~asml162/Class_Material>

> **Comments:**
> **username_0**: Oh interesting. So it's a considerably more advanced result than plain PAC. Will have a look at those, thanks!  
> **username_1**: I'd say it's less difficult than, say, the standard PAC bounds, which rely on the "deep" Sauer's Lemma -- while this is really just a clever use of Hoeffding + union bound.  
> **username_0**: I was referring to the non-VC PAC bounds. But I thought that stuff with Rademacher complexity was on a similar level than VC stuff, or more advanced. But I'm not very familiar with it.  
> **username_1**: BTW, feel free to accept so the question doesn't linger in the queue :)  
> **username_2**: On a side note, I like how in learning theory what is essentially "Chernoff + union bound" is named after a person :)  
> **username_1**: @SashoNikolov you bring up an interesting meta-point that may be worthy of its own post. Massart's finite class lemma is indeed a rather trivial result, likely folklore long before he published it. But he's a famous probabilist, well-known for highly non-trivial results (such computing the optimal constants in the DKW inequality). I've observed that famous people often have simple results named after them, and this is not unique to learning theory. Just look at the Johnson-Lindenstrauss lemma -- certainly not the deepest or most difficult, thought probably what they're best known for.  
> **username_2**: I agree :). I think "Chernoff bound" is an even better example. Chernoff considered it a minor lemma in a paper, whose proof he had learned from Rubin. The proof technique is at least thirty years older than Chernoff's paper, and dates back to the work of Sergei Bernstein. But the name took off.  
> **username_3**: @SashoNikolov [Bring back Legendre's constant!](https://en.wikipedia.org/wiki/Legendre%27s_constant)  
> **username_0**: Oh, actually, the pdf you linked doesn't contain the proof?  
> **username_1**: You're right, it's proven in a note mentioned in (a note mentioned in) there -- so two hops away :) http://www.cs.berkeley.edu/~bartlett/courses/281b-sp06/lecture23.ps  
> **username_1**: Thm. 1.1 in that .ps file  
> **username_0**: Yeah, I found it through the two hops. Also had to google Massart's lemma  
> **username_1**: Indeed -- that's the note I just linked.  
> **username_1**: Massart's lemma is really nothing more than this: https://www.cs.bgu.ac.il/~asml162/wiki.files/Expected%20maximum%20of%20subgaussian%20variables.pdf  

---

### Answer by username_4 on 2020-02-06. Score: 0

Let the risk be a random variable, by the Chernoff-Hoeffding's inequality, you can bound the approximation to the true risk:
\begin{align}
P \left(\Bigg | \frac{1}{n} \sum\_{i=1}^{n}\xi\_i -
\mathbb{E}(\xi) \Bigg | \geq \epsilon \right) &\leq 2 \exp(-2n\epsilon^2)\\
P(|\hat{R}\_{S}(h) - R(h)| \geq \epsilon) &\leq 2 \exp(-2n\epsilon^2)
\end{align}

Unfortunately, this bound only holds for a fixed function $h$ which does not depend on the training data, but our hypothesis certainly does depend. The reason for such constraint is intuitive. If we let the hypothesis space convey all possible functions and do not restrict our hypothesis to not depend on the training data, we can always generate a function that ``memorises'' the given sample and has no empirical error. Such function will most certainly not generalise well and invalidate the bound.

Vapnik and Chervonenkis solved this conundrum by using the union bound.

==Union Bound==

If we enumerate all the functions in $H$, using the fact that it is finite (it is a $\epsilon$-cover of $H$), the bound still holds for each hypothesis:
\begin{align}
P(|\hat{R}\_{S}(h\_1) - R(h\_1) | > \epsilon) &\lor \nonumber \\
P(|\hat{R}\_{S}(h\_2)-R(h\_2)| > \epsilon) &\lor \cdots \nonumber \\
P(|\hat{R}\_{S}(h\_{|H|})-R(h\_{|H|})| > \epsilon)
&\leq \sum^{|H|} 2 \exp(-2n\epsilon^2) \nonumber\\
\therefore P(\sup\_{h \in H}|\hat{R}\_{S}(h) - R(h)| >\epsilon)
&\leq 2 |H| \exp(-2n\epsilon^2)\\
P\left[ \exists h \in H:~|\hat{R}\_{S}(h) - R(h)| >\epsilon\right]
&\leq 2 |H| \exp(-2n\epsilon^2)
\end{align}
\begin{align}
P\left[ \exists h \in H:~|\hat{R}\_{S}(h) - R(h)| >\epsilon\right]
&< \delta \tag{PAC}\\
P\left[ \exists h \in H:~|\hat{R}\_{S}(h) - R(h)| >\epsilon\right]
&\leq 2 |H| \exp(-2n\epsilon^2) \\
\therefore \delta &> 2 |H| \exp(-2n\epsilon^2)
\end{align}
Assuming $\delta = 2 |H| \exp(-2n\epsilon^2)$, we have:
\begin{align}
\exp(-2n\epsilon^2) = \frac{\delta}{2|H|} \\
-2n\epsilon^2 = \ln{\delta} - ln{2|H|}\\
\epsilon^2 = \frac{\ln{|H|}+\ln{2}-\ln{\delta}}{2n}\\
\therefore \epsilon > 0 \rightarrow \epsilon = + \sqrt{\frac{\ln{|H|}+ \ln{2/\delta}}{2n}}
\end{align}


---

