Empirical Risk Minimisation and Uniform Convergence

Why minimising training error can work, why it needs a uniform bound, and the finite-class and PAC guarantees that follow.

Learning TheoryGraduate⏱ 3 hours16 min readermuniform convergencepac learninggeneralisationsymmetrisation

5 problems →

AssumesConcentration Inequalities

The setup

Data $(X,Y)\sim\Dcal$ on $\Xcal\times\Ycal$ , a hypothesis class $\Hcal \subseteq \{h : \Xcal\to\Ycal\}$ , a loss $\ell(h(x),y) \in [0,1]$ . Define

\underbrace{R(h) = \E_{\Dcal}\big[\ell(h(X),Y)\big]}_{\text{risk}}, \qquad \underbrace{\hat R_n(h) = \frac1n\sum_{i=1}^n \ell(h(x_i),y_i)}_{\text{empirical risk}} .

Empirical risk minimisation returns $\hat h \in \argmin_{h\in\Hcal}\hat R_n(h)$ .

PropositionExcess risk decomposition for ERM

Let $h^\star \in \argmin_{h\in\Hcal}R(h)$ and let

\Delta_n = \sup_{h\in\Hcal}\big|R(h)-\hat R_n(h)\big|

be the uniform deviation. Then

R(\hat h) - \inf_{h\in\Hcal}R(h) \le 2\Delta_n,

and therefore

R(\hat h) - \underbrace{\inf_{\text{all }h}R(h)}_{\text{Bayes risk}} \le \underbrace{2\Delta_n}_{\text{estimation error}} + \underbrace{\Big(\inf_{h\in\Hcal}R(h) - \inf_{\text{all }h}R(h)\Big)}_{\text{approximation error}} .

Key idea

This three-line argument is the reason the whole subject is about $\Delta_n$ . It also displays the fundamental tension: enlarging $\Hcal$ decreases the approximation error and increases $\Delta_n$ . That is the honest statement of the bias–variance trade for ERM — and note that it is a statement about this bound, not about the true risk, which is exactly the loophole the double-descent phenomenon exploits.

Finite classes

TheoremGeneralisation bound for a finite hypothesis class

Let $|\Hcal| = N$ and $\ell\in[0,1]$ . With probability at least $1-\delta$ over the sample,

\Delta_n = \sup_{h\in\Hcal}\big|R(h)-\hat R_n(h)\big| \le \sqrt{\frac{\log(2N/\delta)}{2n}},

and consequently $R(\hat h)\le\inf_{h\in\Hcal}R(h) + 2\sqrt{\frac{\log(2N/\delta)}{2n}}$ .

Assumptions

Bounded loss, i.i.d. sample, and a hypothesis class fixed before seeing the data. The last is the one most easily violated in practice: any hyperparameter chosen by looking at the test set effectively enlarges $\Hcal$ , and the bound must be inflated accordingly.

TheoremFaster rate in the realizable case

Suppose some $h^\star\in\Hcal$ has $R(h^\star)=0$ and the loss is the zero-one loss. Then with probability at least $1-\delta$ , any ERM solution $\hat h$ (which necessarily has $\hat R_n(\hat h)=0$ ) satisfies

R(\hat h) \le \frac{\log(N/\delta)}{n} .

Key idea

$1/n$ instead of $1/\sqrt n$ — a genuinely different rate, obtained by replacing Hoeffding's two-sided bound with the exact one-sided multiplicative bound available when the variance is small. This is the simplest instance of a fast rate under a low-noise condition, and it is the reason interpolating classifiers are not automatically suspect: when the problem is realizable, fitting the training data exactly is the right thing to do.

PAC learnability and the necessity of inductive bias

DefinitionPAC learnability

$\Hcal$ is agnostically PAC learnable if there is a function $n_\Hcal(\eps,\delta)$ , polynomial in $1/\eps$ and $1/\delta$ , and an algorithm $\mathcal{A}$ , such that for every distribution $\Dcal$ and every $n \ge n_\Hcal(\eps,\delta)$ ,

\P\Big(R(\mathcal{A}(S)) \le \inf_{h\in\Hcal}R(h)+\eps\Big) \ge 1-\delta .

TheoremNo free lunch

Let $\Xcal$ be a domain of size $2m$ and consider the zero-one loss with $\Ycal=\{0,1\}$ and $\Hcal$ the class of all functions $\Xcal\to\{0,1\}$ . For every algorithm $\mathcal{A}$ using $n \le m$ samples there is a distribution $\Dcal$ on which

\E_{S\sim\Dcal^n}\big[R(\mathcal{A}(S))\big] \ge \frac14,

while some $h\in\Hcal$ has $R(h)=0$ .

Key idea

Inductive bias is not a regrettable practical compromise; it is a mathematical necessity. Learning is impossible over the class of all functions, so every working learning algorithm encodes assumptions about which functions are plausible — through the hypothesis class, the regulariser, the architecture, or the optimiser's implicit preferences. "This model has no assumptions built in" is always false. The interesting question is never whether there is an inductive bias but what it is, which is why the implicit-bias results on the deep learning theory page matter so much.

From finite to infinite classes

The finite-class bound is useless for $\Hcal$ infinite — every interesting class, including all linear classifiers. Two routes out, both developed on the next page:

Combinatorial. Replace $N$ by the number of distinct labellings the class can produce on $n$ points, the growth function $\Pi_\Hcal(n)$ . Sauer's lemma bounds this by $O(n^{d})$ where $d$ is the VC dimension, so $\log \Pi_\Hcal(n) = O(d\log n)$ takes the place of $\log N$ .
Analytic. Bound $\E\Delta_n$ directly by the Rademacher complexity of the class, which is a scale-sensitive measure that does not require finiteness at all.

The bridge to both is symmetrisation, which replaces the unknown population risk by a second independent sample:

LemmaSymmetrisation

Let $\mathcal{G}$ be a class of functions $\Xcal\to[0,1]$ . Then

\E_S\left[\sup_{g\in\mathcal{G}}\Big(\E g - \frac1n\sum_i g(x_i)\Big)\right] \le 2\,\E_{S,\eps}\left[\sup_{g\in\mathcal{G}}\frac1n\sum_{i=1}^n\eps_i g(x_i)\right],

where $\eps_i$ are independent Rademacher signs.

What uniform convergence cannot do

Empirical observationUniform convergence is not necessary for generalisation

Empirical observation — a regularity seen in experiments. No theorem on this page establishes it in general.

There are settings — including realistic overparameterised networks — where the trained model generalises well while the uniform deviation $\Delta_n$ over any hypothesis class containing it is close to its maximum possible value, making every uniform-convergence bound vacuous.

What this does not say

Nagarajan and Kolter construct explicit examples where the generalisation gap of the learned predictor is small but any bound derived by uniform convergence over a class containing the algorithm's possible outputs is near-trivial — even when the class is restricted to exactly the hypotheses the algorithm can return on samples of that size. The obstruction is not looseness of the union bound; it is that the two-sided uniform deviation is genuinely large.

What follows and what does not:

Uniform convergence remains sufficient: when the bound is non-vacuous, it is a real guarantee, and for classical model classes it is the right tool.
It is not necessary, so the failure of a uniform bound is not evidence that a model will generalise badly.
Explaining generalisation in the overparameterised regime therefore requires algorithm-dependent analysis — stability, PAC-Bayes with a data-dependent prior, margin-based bounds, or implicit-bias characterisations — not a better bound on $\Delta_n$ .

This is an active research area, and there is no settled answer.

Problems

The excess risk decomposition for ERMProof · Beginner · 15 min Generalisation for a finite classProof · Beginner · 30 min The fast rate in the realizable caseProof · Intermediate · 30 min The no-free-lunch theoremProof · Advanced · 1 hour The symmetrisation lemmaProof · Graduate · 1 hour

References

BookShai Shalev-Shwartz and Shai Ben-David (2014). Understanding Machine Learning: From Theory to AlgorithmsThe standard modern textbook for this material; the exposition here is written independently.
BookMehryar Mohri, Afshin Rostamizadeh and Ameet Talwalkar (2018). Foundations of Machine Learning
BookVladimir N. Vapnik (1998). Statistical Learning Theory
PaperVaishnavh Nagarajan and J. Zico Kolter (2019). Uniform convergence may be unable to explain generalization in deep learning

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

PropositionExcess risk decomposition for ERMproof includedThe excess risk of ERM is bounded by twice the uniform deviation plus the approximation error of the class.
TheoremGeneralisation bound for a finite hypothesis classproof includedFor a class of size N the uniform deviation is of order the square root of log N over n.
TheoremFaster rate in the realizable caseproof includedWhen some hypothesis has zero risk the rate improves from 1/sqrt n to log N over n.
DefinitionPAC learnabilityA class is PAC learnable if a polynomial sample suffices to get low risk with high confidence.
TheoremNo free lunchproof includedWithout restricting the hypothesis class no algorithm can generalise, so some inductive bias is mathematically necessary.
Empirical observationUniform convergence is not necessary for generalisationOverparameterised models can generalise while the uniform deviation over their hypothesis class is vacuous.

Problems (5)

All problems