Question 4

Will it generalize, and with how much data?

How well does finite training data pin down population performance, and how many samples does a given excess risk require? Generalization gaps, sample complexity, consistency and statistical rates all live here.

Symptoms

Is this your question?

Sub-cases

Which version are you facing?

Case Usually start with
A statement uniform over a hypothesis class? Symmetrization, then Rademacher complexity, VC dimension or covering numbers, then concentration.
A bound that exploits the learning algorithm? Uniform or on-average stability, mutual information, compression.
A certificate for one learned predictor or posterior? PAC-Bayes.
Sample complexity or statistical consistency? Prove a finite-sample excess-risk rate, then solve for \(n(\epsilon, \delta)\); consistency follows if every term vanishes.
Parametric efficiency? M-estimation: a score expansion, the Hessian or Fisher information, the CLT and Slutsky's lemma.
A norm or margin bound for a modern network? Lipschitz and margin arguments with spectral or Frobenius norms, fed into Rademacher or PAC-Bayes machinery.
The recipe

Decompose first, then choose uniform or algorithm-specific

Write the population excess risk you want and split it before choosing a theorem:

\[R(\hat f) - R(f^\star) = \underbrace{R(\hat f) - \hat R(\hat f)}_{\text{generalization}} + \underbrace{\hat R(\hat f) - \inf_{f \in \mathcal{F}} \hat R(f)}_{\text{optimization}} + \underbrace{\inf_{f \in \mathcal{F}} \hat R(f) - R(f^\star)}_{\text{estimation and approximation}}.\]
  1. Decide whether the bound is uniform over \(\mathcal{F}\) or specific to your algorithm's output. That choice separates Rademacher and VC proofs from stability, information and compression proofs.
  2. Derive the complexity term with every dependence on norms, margin, depth, dimension and confidence visible.
  3. Solve for \(n\) if you promise a sample complexity.
  4. Evaluate the bound numerically in the regime you claim. A correct bound can still be vacuous.
100
100
Set \(k = 1\) to see Hoeffding hold.
Why Hoeffding needs a fixed hypothesis. Each experiment draws \(n\) examples and \(k\) classifiers that guess at random, so every one has true error 1/2. We keep the one with the lowest training error and record how much it flatters itself. Hoeffding (\(\delta = 0.05\)) is exceeded far more than 5% of the time once \(k > 1\), because the winner was selected using the same sample. The union bound pays \(\sqrt{\ln(2k/\delta)/2n}\) and holds.
A complete proof

Empirical risk minimization over a finite class

The claim

Let \(\mathcal{H}\) contain \(k\) hypotheses and let \(\hat h\) minimize the training risk \(\hat R\). With probability at least \(1 - \delta\) over the sample,

\[R(\hat h) \le \min_{h \in \mathcal{H}} R(h) + 2\sqrt{\frac{\ln(2k/\delta)}{2n}}.\]
Assumptions
  • The \(n\) training examples are i.i.d. from the distribution that defines \(R\).
  • The loss takes values in \([0, 1]\).
  • \(\mathcal{H}\) is fixed before seeing the data.
First move, and why

Make the deviation bound hold for every hypothesis at once. \(\hat h\) is chosen using the sample, so a bound for a fixed \(h\) does not apply to it, as the demo above shows. A bound that holds simultaneously for all of \(\mathcal{H}\) holds in particular for whichever one the data selects.

Show the proof, with commentary

Step 1: one fixed hypothesis. For each fixed \(h\), \(\hat R(h)\) averages \(n\) independent values in \([0, 1]\) with mean \(R(h)\), so Hoeffding gives

\[\Pr\big(\lvert \hat R(h) - R(h) \rvert \ge \epsilon\big) \le 2e^{-2n\epsilon^2}.\]

Step 2: all hypotheses at once. By the union bound over the \(k\) members of \(\mathcal{H}\),

\[\Pr\big(\exists h \in \mathcal{H}: \lvert \hat R(h) - R(h) \rvert \ge \epsilon\big) \le 2k\,e^{-2n\epsilon^2}.\]

Set the right side equal to \(\delta\): \(\epsilon = \sqrt{\ln(2k/\delta)/(2n)}\). With probability at least \(1 - \delta\), every \(h\) satisfies \(\lvert \hat R(h) - R(h) \rvert < \epsilon\).

The price of uniformity is only \(\ln k\) inside the square root. That is why the green line in the demo moves so slowly as \(k\) grows.

Step 3: chain through the minimizer. Let \(h^\star = \arg\min_{\mathcal{H}} R\). On the good event, and because \(\hat h\) minimizes \(\hat R\),

\[R(\hat h) < \hat R(\hat h) + \epsilon \le \hat R(h^\star) + \epsilon < R(h^\star) + 2\epsilon. \quad \blacksquare\]

The middle inequality is the only place ERM is used. The two outer ones are the uniform bound applied to two different hypotheses, which is exactly why it had to be uniform.

A tempting approach that fails

Apply Step 1 directly to \(\hat h\). The sample that is supposed to be independent of the hypothesis was used to pick it, so the training errors of the chosen hypothesis are no longer an unbiased average. In the demo, this "bound" is exceeded in roughly a quarter of the runs at \(k = 100\).

If you relax an assumption
  • Infinite classes: replace \(\ln k\) by a complexity measure. Symmetrization gives \(\mathbb{E}\sup_f (P - P_n)f \le 2\,\mathbb{E}\,\mathfrak{R}_S(\mathcal{F})\), and McDiarmid's inequality turns that into a high-probability bound.
  • Unbounded loss: use sub-Gaussian or Bernstein-type concentration in Step 1, with matching tail assumptions.
  • Dependent or shifted data: Step 1 fails as stated. You need mixing conditions or an explicit model of the shift.
Try it yourself

How many samples for a million hypotheses?

The exercise

A finite class has \(k = 10^6\) hypotheses. Using the bound proved above, how many samples \(n\) guarantee \(R(\hat h) \le \min_h R(h) + 0.1\) with probability at least \(0.95\)? How many more do you need if the class doubles in size?

Hint

Set \(2\sqrt{\ln(2k/\delta)/(2n)} \le 0.1\) and solve for \(n\).

Show a solution

The condition is \(\ln(2k/\delta)/(2n) \le 0.0025\), that is \(n \ge \ln(2k/\delta)/0.005\). With \(k = 10^6\) and \(\delta = 0.05\), \(\ln(4 \times 10^7) \approx 17.50\), so \(n \ge 3501\) suffices.

Doubling \(k\) adds \(\ln 2 / 0.005 \approx 139\) samples. The class size enters only through its logarithm, which is why a union bound is affordable even for very large finite classes, and why infinite classes need a different measure of size, such as VC dimension or Rademacher complexity, instead of \(\ln k\).

The toolkit

What each tool gives you, and what it costs

Hoeffding's inequality

\[\Pr\Big(\Big\lvert \tfrac{1}{n}\textstyle\sum_i X_i - \mathbb{E}X_i \Big\rvert \ge \epsilon\Big) \le 2\exp\!\left(-\frac{2n\epsilon^2}{(b - a)^2}\right)\]

For independent \(X_i \in [a, b]\).

Gives
Concentration for one fixed hypothesis.
Costs
Independence and bounded variables.
Wrong tool when
The predictor was selected using the same sample; you need a uniform or stability argument first.

Symmetrization and Rademacher complexity

\[\mathfrak{R}_S(\mathcal{F}) = \mathbb{E}_\sigma \sup_{f \in \mathcal{F}} \frac{1}{n}\sum_{i=1}^n \sigma_i f(z_i), \qquad \mathbb{E}\sup_{f \in \mathcal{F}} (P - P_n) f \le 2\, \mathbb{E}\, \mathfrak{R}_S(\mathcal{F})\]

This page uses the convention without absolute values, with \(\sigma_i\) independent random signs. For a two-sided bound, apply it to \(\mathcal{F} \cup (-\mathcal{F})\). Some texts put an absolute value inside the supremum; keep one convention through a proof. Standard measurability and integrability conditions apply.

Gives
Converts generalization into a random-sign complexity of the class.
Costs
An i.i.d. sample and a class of manageable complexity.
Wrong tool when
The class is huge but your algorithm is very stable; uniform bounds can then be vacuous.

Contraction (Ledoux–Talagrand)

\[\mathbb{E}_\sigma \sup_f \tfrac{1}{n}\textstyle\sum_i \sigma_i \phi_i\big(f(x_i)\big) \le L\, \mathbb{E}_\sigma \sup_f \tfrac{1}{n}\sum_i \sigma_i f(x_i)\]

If each \(\phi_i\) is \(L\)-Lipschitz. (The absolute-value convention also needs \(\phi_i(0) = 0\) and costs a factor 2.)

Gives
Moves complexity through Lipschitz losses and activations.
Costs
Lipschitz transformations.
Wrong tool when
The target metric is discontinuous and there is no margin surrogate step.

Uniform stability

\[\sup_z \big\lvert \ell(A(S), z) - \ell(A(S'), z) \big\rvert \le \beta \;\Longrightarrow\; \big\lvert \mathbb{E}\,\mathrm{gen} \big\rvert \le \beta\]

For all datasets \(S, S'\) differing in one example.

Gives
An algorithm-dependent bound on the expected generalization gap.
Costs
Stability under replacing one sample.
Wrong tool when
The algorithm is highly unstable or interpolating, unless a weaker average notion is available.

PAC-Bayes (kl form)

\[\mathrm{kl}\big(\hat L(Q) \,\Vert\, L(Q)\big) \le \frac{D_{\mathrm{KL}}(Q \Vert P) + \ln(2\sqrt{n}/\delta)}{n}\]

With probability at least \(1 - \delta\), simultaneously for all posteriors \(Q\), for a prior \(P\) chosen independently of the sample and a loss in \([0, 1]\).

Gives
A data-dependent certificate trading empirical risk against KL complexity.
Costs
A prior independent of the data, bounded loss, and a stochastic predictor.
Wrong tool when
The prior is chosen after seeing the data without a corrected theorem.

Mutual-information bound

\[\big\lvert \mathbb{E}\big[\mathrm{gen}(W, S)\big] \big\rvert \le \sqrt{\frac{2\sigma^2}{n}\, I(W; S)}\]

If \(\ell(w, Z) - \mathbb{E}_Z \ell(w, Z)\) is \(\sigma\)-sub-Gaussian for every \(w\).

Gives
An expected, algorithm-dependent bound driven by how much the output reveals about the sample.
Costs
A sub-Gaussian loss and finite mutual information.
Wrong tool when
You need a high-probability bound, or the algorithm is deterministic and continuous so \(I(W; S)\) can be infinite.
Worked examples

How published papers answer it

  1. Hardt, Recht & Singer, Train Faster, Generalize Better: Stability of Stochastic Gradient Descent, ICML 2016. arXiv

    Bounds how much SGD's output changes when one example is replaced, then uses stability to control the expected train–test gap. The key ingredients are Lipschitzness, smoothness and how expansive each gradient update is.

  2. Bartlett, Foster & Telgarsky, Spectrally-Normalized Margin Bounds for Neural Networks, NeurIPS 2017. arXiv

    Bounds multiclass generalization by the empirical margin distribution and a spectral complexity built from the product of layer spectral norms. The canonical "Lipschitz propagation plus margin plus complexity" template.

  3. Dziugaite & Roy, Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data, UAI 2017. arXiv

    Turns PAC-Bayes into an optimization over stochastic network posteriors and reports explicit non-vacuous certificates. The writing lesson: evaluate your bound numerically instead of hiding the constants.

  4. Arora, Ge, Neyshabur & Zhang, Stronger Generalization Bounds for Deep Nets via a Compression Approach, ICML 2018. arXiv

    First shows a trained network is noise-stable and therefore compressible, then bounds generalization through the compressed description. Useful when parameter counts make uniform bounds too pessimistic.

  5. Xu & Raginsky, Information-Theoretic Analysis of Generalization Capability of Learning Algorithms, NeurIPS 2017. arXiv

    Relates the expected train–test gap to the mutual information between the sample and the algorithm's output, shifting complexity from the hypothesis class to what the algorithm extracts.

Common traps

Where proofs of this kind go wrong

Resources

Where to go next

← Back to the guide

Found an error, or have a better example or a question this guide should cover? Email [email protected]. Corrections and contributions are welcome. Last updated October 5, 2026.