VC Dimension, Sauer's Lemma and Rademacher Complexity

VC dimension

DefinitionShattering, growth function, VC dimension

Let $\Hcal\subseteq\{\pm1\}^\Xcal$. For $C = \{x_1,\dots,x_n\}\subseteq\Xcal$ write

$$\Hcal|_C = \big\{(h(x_1),\dots,h(x_n)) : h\in\Hcal\big\}\subseteq\{\pm1\}^n .$$

$\Hcal$ shatters $C$ if $|\Hcal|_C| = 2^n$. The growth function is $\Pi_\Hcal(n) = \max_{|C|=n}|\Hcal|_C|$, and the VC dimension is

$$\mathrm{VC}(\Hcal) = \sup\{n : \Pi_\Hcal(n)=2^n\} .$$

TheoremSauer–Shelah lemma

If $\mathrm{VC}(\Hcal)=d<\infty$ then for every $n$,

$$\Pi_\Hcal(n) \le \sum_{k=0}^d\binom nk \le \left(\frac{en}{d}\right)^d \quad (n \ge d).$$

ProofReveal

TheoremVC generalisation bound

Let $\mathrm{VC}(\Hcal)=d$ and let $\ell$ be the zero-one loss. With probability at least $1-\delta$,

$$\sup_{h\in\Hcal}\big|R(h)-\hat R_n(h)\big| \le C\sqrt{\frac{d\log(n/d)+\log(1/\delta)}{n}} .$$

The derivation combines symmetrisation, Sauer's lemma applied to the (at most $\Pi_\Hcal(2n)$) labellings on the doubled sample, and Massart's lemma below; it is carried out in the references and the structure is exactly the one reproduced for the Rademacher bound in the next section.

PropositionVC dimension of linear classifiers

Let $\Hcal = \{x\mapsto\sign(\ip{w}{x}) : w\in\R^d\}$ be the homogeneous halfspaces. Then $\mathrm{VC}(\Hcal)=d$. With a bias term, $\mathrm{VC}=d+1$.

ProofReveal

Rademacher complexity

DefinitionRademacher complexity

For a class $\mathcal{G}$ of functions $\Xcal\to\R$ and a sample $S = (x_1,\dots,x_n)$, the empirical Rademacher complexity is

$$\hat{\mathfrak{R}}_S(\mathcal{G}) = \E_\eps\left[\sup_{g\in\mathcal{G}}\frac1n\sum_{i=1}^n\eps_ig(x_i)\right],$$

with $\eps_i$ i.i.d. Rademacher, and the Rademacher complexity is $\mathfrak{R}_n(\mathcal{G}) = \E_S\hat{\mathfrak{R}}_S(\mathcal{G})$.

TheoremRademacher generalisation bound

Let $\mathcal{G}$ be a class of functions $\Xcal\to[0,1]$. With probability at least $1-\delta$ over the sample, simultaneously for all $g\in\mathcal{G}$,

$$\E g \le \frac1n\sum_{i=1}^ng(x_i) + 2\mathfrak{R}_n(\mathcal{G}) + \sqrt{\frac{\log(1/\delta)}{2n}} .$$

ProofReveal

LemmaMassart's finite lemma

Let $A\subseteq\R^n$ be finite with $\norm{a}_2\le r$ for all $a\in A$. Then

$$\E_\eps\left[\max_{a\in A}\ip{\eps}{a}\right] \le r\sqrt{2\log|A|} .$$

ProofReveal

Applying Massart with $A = \Hcal|_S \subseteq\{\pm1\}^n$, so $r = \sqrt n$ and $|A| \le \Pi_\Hcal(n) \le (en/d)^d$, gives

$$\hat{\mathfrak{R}}_S(\Hcal) \le \frac{\sqrt n\sqrt{2d\log(en/d)}}{n} = \sqrt{\frac{2d\log(en/d)}{n}},$$

which recovers the VC bound. So the Rademacher route subsumes the combinatorial one.

PropositionRademacher complexity of a norm-bounded linear class

Let $\mathcal{G} = \{x\mapsto\ip{w}{x} : \norm{w}_2\le B\}$ and suppose $\norm{x_i}_2\le R$. Then

$$\hat{\mathfrak{R}}_S(\mathcal{G}) \le \frac{BR}{\sqrt n} .$$

The bound does not depend on the dimension of $x$.

ProofReveal

LemmaTalagrand contraction

If $\phi:\R\to\R$ is $K$-Lipschitz then $\hat{\mathfrak{R}}_S(\phi\circ\mathcal{G}) \le K\,\hat{\mathfrak{R}}_S(\mathcal{G})$.

Quoted from Ledoux–Talagrand via the references. It is the tool that converts a bound on the complexity of the predictor class into a bound on the complexity of the loss class: the hinge loss is $1$-Lipschitz, the logistic loss is $1$-Lipschitz, and a ramp surrogate for the zero-one loss at margin $\gamma$ is $1/\gamma$-Lipschitz — whence the $1/\gamma$ in every margin bound.

Two other routes to generalisation

DefinitionUniform stability

An algorithm $\mathcal{A}$ is $\beta$-uniformly stable if for every pair of samples $S, S'$ differing in one point, and every $(x,y)$,

$$\big|\ell(\mathcal{A}(S)(x),y) - \ell(\mathcal{A}(S')(x),y)\big| \le \beta .$$

Bousquet and Elisseeff show that such an algorithm satisfies $\E[R(\mathcal{A}(S)) - \hat R_n(\mathcal{A}(S))]\le\beta$, and that regularised ERM with a $\lambda$-strongly convex regulariser is $O(1/(\lambda n))$-stable.

DefinitionPAC-Bayes bound

For a prior $P$ over hypotheses fixed before seeing the data and any posterior $Q$ (possibly data-dependent), with probability at least $1-\delta$,

$$\E_{h\sim Q}R(h) \le \E_{h\sim Q}\hat R_n(h) + \sqrt{\frac{\mathrm{KL}(Q\,\|\,P) + \log(2\sqrt n/\delta)}{2n}} .$$

Both are algorithm-dependent, which is what makes them candidates for explaining deep learning where uniform convergence fails: stability speaks about what the optimiser does, and PAC-Bayes charges only for the information the posterior adds to the prior. Neither has yet produced a non-vacuous bound for a state-of-the-art network trained on a standard benchmark, which is the honest state of the art.

Problems

Prove the Sauer–Shelah lemmaProof · Graduate · 3 hours VC dimension of halfspacesProof · Intermediate · 30 min A one-parameter class with infinite VC dimensionProof · Advanced · 1 hour Massart's finite maximal inequalityProof · Advanced · 30 min Rademacher complexity of a norm-bounded linear classProof · Advanced · 30 min Derive the margin generalisation boundProof · Graduate · 1 hour