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.

For 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 result characterizes PAC learnability for binary classification: $\mathcal{H}$ is PAC learnable if and only if its VC dimension is finite. The sample complexity is $\Theta(d/\epsilon^2)$ up to log factors, giving a tight characterization.

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 linear classes in $\mathbb{R}^d$ with bounded norm, $\mathfrak{R}_n = O(\sqrt{d/n})$, recovering the VC result without going through combinatorics.

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.