Generalization Bound

Definition

A generalization bound controls the gap between true and empirical risk, uniformly over the function class, with high probability. It bounds the estimation error, is worst case over distributions and over all functions in $\mathcal{F}$.

Formula

With probability at least $1-\delta$, for all $f\in \mathcal{F}$:

$$\begin{array}{rl}\text{finite, }m\text{ functions:}& R(f)\le R_n(f)+\sqrt{\frac{\log (2m)+\log (1/\delta )}{2n}}\\ \text{shattering coefficient:}& R(f)\le R_n(f)+2\sqrt{\frac{\log \mathcal{N}(\mathcal{F},2n)-\log \delta }{n}}\\ \text{VC dimension }d\text{:}& R(f)\le R_n(f)+2\sqrt{\frac{d\log (2en/d)-\log \delta }{n}}\\ \text{Rademacher:}& R(f)\le R_n(f)+2{\mathrm{Rad}}_n(\mathcal{F})+\sqrt{\frac{\log (1/\delta )}{2n}}\end{array}$$

• Finite class: Hoeffding plus the union bound, cost only $\log m$. Infinite classes: symmetrization with a ghost sample reduces the supremum to at most $\mathcal{N}(\mathcal{F},2n)$ labelings.
• All rates are $1/\sqrt{n}$ up to logs; sample size $\sim d/{\epsilon }^2$. Faster ($1/n$) under a margin assumption (perceptron). Stability gives bounds for algorithms instead of classes (Lecture 4).
• Vacuous in the overparameterized regime.

Appears in

• Lecture 3, finite classes
• Lecture 3, Theorem 10 and symmetrization
• Lecture 3, Theorem 13
• Lecture 3, summary table
• Lecture 3, limitations
• n bound for the perceptron
• Lecture 4, the stability bound

Related concepts

• Hoeffding Inequality
• VC Dimension
• Rademacher Complexity