Sample Complexity Bounds

For a finite hypothesis class $\mathcal{H}$ with loss in $[0,1]$, ERM achieves excess risk at most $\epsilon$ with probability at least $1 - \delta$ whenever:

$n \geq \frac{2(\log|\mathcal{H}| + \log(2/\delta))}{\epsilon^2}$

Equivalently, the sample complexity satisfies $n(\epsilon, \delta, \mathcal{H}) = O\!\left(\frac{\log|\mathcal{H}| + \log(1/\delta)}{\epsilon^2}\right)$.

Each hypothesis needs roughly $1/\epsilon^2$ samples to pin down its population risk (by Hoeffding). The union bound over $|\mathcal{H}|$ hypotheses costs a factor of $\log|\mathcal{H}|$, not $|\mathcal{H}|$, because the bound enters through an exponential inequality.

This is the baseline sample complexity result. It shows that finite classes are always learnable, and the cost is logarithmic in the class size. A class with $2^d$ hypotheses needs only $O(d/\epsilon^2)$ samples, not $O(2^d/\epsilon^2)$.

The bound is vacuous for infinite classes. It also gives no help when $|\mathcal{H}|$ is finite but astronomically large (e.g., all possible decision trees of a given depth), because the $\log|\mathcal{H}|$ term may be too large to be useful.

Under realizability (some $h^* \in \mathcal{H}$ has $R(h^*) = 0$) with 0-1 loss and finite $\mathcal{H}$, any ERM hypothesis $\hat{h}$ (i.e., any $h \in \mathcal{H}$ consistent with the training set) satisfies $R(\hat{h}) \leq \epsilon$ with probability $\geq 1 - \delta$ whenever:

$n \geq \frac{1}{\epsilon}\!\left(\log|\mathcal{H}| + \log\frac{1}{\delta}\right)$

The dependence on $\epsilon$ is linear, not quadratic. Realizability buys a full factor of $1/\epsilon$ over the agnostic case.

When some $h^*$ achieves zero error, ERM can refuse to return any hypothesis with positive empirical error. The only way ERM fails is if a bad hypothesis (one with $R(h) > \epsilon$) happens to look perfect on the training set. The probability of this shrinks like $(1 - \epsilon)^n \leq e^{-n\epsilon}$ per bad hypothesis, giving the $1/\epsilon$ rate.

The $\log|\mathcal{H}|$ factor is the key. You pay logarithmically in the size of the hypothesis class, not linearly. For infinite $\mathcal{H}$, this argument fails because $\log|\mathcal{H}| = \infty$, and you need VC theory to replace the union bound with a polynomial growth-function argument.

The realizable rate $1/\epsilon$ versus the agnostic $1/\epsilon^2$ is a real distinction: at $\epsilon = 0.01$, the realizable bound asks for $\sim 100 \log|\mathcal{H}|$ samples while the agnostic bound asks for $\sim 10\,000 \log|\mathcal{H}|$ — two orders of magnitude more. This gap is the formal cost of not knowing whether the target sits in your class.

This bound requires realizability. Without it, no $h^*$ achieves zero training error, the $(1 - \epsilon)^n$ tail no longer applies, and the rate degrades to the agnostic $1/\epsilon^2$ from Hoeffding-style concentration. The bound is also vacuous for infinite hypothesis classes (linear classifiers, neural networks); use VC dimension or Rademacher complexity instead.

For agnostic binary classification with 0-1 loss, if $\mathcal{H}$ has VC dimension $d < \infty$:

Upper bound: There exists a constant $C > 0$ such that ERM achieves excess risk $\leq \epsilon$ with probability $\geq 1 - \delta$ whenever:

$n \geq C \cdot \frac{d + \log(1/\delta)}{\epsilon^2}$

Lower bound: There exist constants $c_1, c_2 > 0$ such that for any algorithm:

$n(\epsilon, \delta, \mathcal{H}) \geq c_1 \cdot \frac{d}{\epsilon^2} + c_2 \cdot \frac{\log(1/\delta)}{\epsilon^2}$

VC dimension $d$ replaces $\log|\mathcal{H}|$ for infinite classes. The Sauer-Shelah lemma shows that the effective number of behaviors of $\mathcal{H}$ on $n$ points is at most $(en/d)^d$. Taking logs recovers $d \log(n/d)$, which leads to a sample complexity of $O(d/\epsilon^2)$ up to log factors. The lower bound shows this is tight.

This is the noisy, distribution-free version of the VC sample-complexity story. Finite VC dimension characterizes learnability for binary classification, but the rate depends on the setting: realizable problems can have $1/\epsilon$ scaling, while agnostic excess-risk learning has the slower $1/\epsilon^2$ scaling.

The VC bound applies only to binary classification with 0-1 loss. For regression, multi-class classification, or other loss functions, you need different complexity measures (pseudo-dimension, Natarajan dimension, or Rademacher complexity). The constants $C, c_1, c_2$ are often not known tightly, making the bound hard to use for choosing $n$ in practice.

If the Rademacher complexity of the loss class satisfies $\mathfrak{R}_n(\ell \circ \mathcal{H}) \leq R(n)$, then ERM achieves excess risk $\leq \epsilon$ with probability $\geq 1 - \delta$ whenever:

$n \text{ is chosen so that } 2R(n) + \sqrt{\frac{\log(1/\delta)}{2n}} \leq \epsilon$

For many classes, $R(n) = O(1/\sqrt{n})$, giving sample complexity $O(1/\epsilon^2)$.

Rademacher complexity directly measures how well the class can fit random noise. If the class cannot fit noise well (small $\mathfrak{R}_n$), it cannot overfit real data either. The sample complexity is determined by how fast $\mathfrak{R}_n$ decays with $n$.

Rademacher bounds are data-dependent: you can estimate $\mathfrak{R}_n$ from the training sample itself. This gives tighter sample complexity for specific distributions, not just worst-case over all distributions. For $\ell_\infty$- or $\ell_1$-bounded linear classes in $\mathbb{R}^d$, the chaining route gives $\mathfrak{R}_n = O(\sqrt{d/n})$, recovering the VC result without going through combinatorics. For the $\ell_2$-bounded class $\{x \mapsto \langle w, x \rangle : \|w\|_2 \leq B,\, \|x\|_2 \leq R\}$ a direct Cauchy-Schwarz / Khintchine argument gives a sharper dimension-free bound $\mathfrak{R}_n \leq BR/\sqrt{n}$. This is the bound used for SVM, ridge, and kernel analyses; the $O(\sqrt{d/n})$ rate is not the right rate for $\ell_2$-bounded classes.

Computing or bounding $\mathfrak{R}_n$ can be difficult for complex hypothesis classes (e.g., deep neural networks). The resulting bounds are often loose in practice and do not explain the generalization of overparameterized models.

Let $P_1, \ldots, P_M$ be distributions such that for all $i \neq j$, the associated optimal hypotheses satisfy $d(h_i, h_j) > 2\epsilon$ and $\mathrm{KL}(P_i^n \| P_j^n) \leq \beta$. Then for any estimator $\hat{h}$:

$\max_{1 \leq i \leq M} \Pr_{S \sim P_i^n}[d(\hat{h}(S), h_i) > \epsilon] \geq 1 - \frac{n\beta + \log 2}{\log M}$

If you have $M$ hypotheses that all look similar (low KL divergence) but require different answers, then no algorithm can reliably pick the right one unless $n$ is large enough for the total information $n\beta$ to exceed $\log M$.

This is the workhorse of minimax lower bounds. Nearly every known sample complexity lower bound in nonparametric statistics and learning theory uses some form of Fano's method or its generalizations.

Constructing the right packing (the $M$ distributions) is the hard part. A poor choice of packing gives a weak lower bound. The bound is also limited to worst-case analysis; it says nothing about specific distributions that might be easier.