# PAC-learning bound with epsilon-cover of hypothesis class

In this video at 43:00, 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?

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

• 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. Mar 27 '18 at 19:54
• On a side note, I like how in learning theory what is essentially "Chernoff + union bound" is named after a person :) Mar 28 '18 at 12:25
• @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. Mar 28 '18 at 12:29
• 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. Mar 28 '18 at 16:33
• @SashoNikolov Bring back Legendre's constant! Mar 28 '18 at 19:47

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}