3
$\begingroup$

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?

|cite|improve this question
$\endgroup$
3
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Aryeh Mar 27 '18 at 19:54
  • 2
    $\begingroup$ On a side note, I like how in learning theory what is essentially "Chernoff + union bound" is named after a person :) $\endgroup$ – Sasho Nikolov Mar 28 '18 at 12:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Aryeh Mar 28 '18 at 12:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Mar 28 '18 at 16:33
  • 1
    $\begingroup$ @SashoNikolov Bring back Legendre's constant! $\endgroup$ – Clement C. Mar 28 '18 at 19:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.