PAC-learning bound with epsilon-cover of hypothesis class

Question

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?

Answer 1

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

Answer 2

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}