Generalization Theory & PAC-Bayes

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. Classical Generalization Bounds
5. VC Dimension of Neural Networks
6. Rademacher Complexity
7. PAC-Bayes Bounds
8. Flat vs Sharp Minima
9. Implicit Regularization of SGD
10. Double Descent Revisited
11. Common Pitfalls
12. Research Perspective
13. Summary
14. Exercises

Learning Objectives

1. State the classical uniform convergence bound and identify why it fails for deep networks.
2. Define VC dimension and Rademacher complexity.
3. State the PAC-Bayes theorem and interpret the KL divergence penalty.
4. Explain the flat minima hypothesis and its connection to generalization.
5. Describe how SGD implicitly regularizes toward low-complexity solutions.

Notation

• $R(f)$ — population risk, $\hat{R}_n(f)$ — empirical risk
• $\mathcal{F}$ — hypothesis class
• $\text{VC}(\mathcal{F})$ — VC dimension
• $\mathcal{R}_n(\mathcal{F})$ — Rademacher complexity
• $Q$ — posterior distribution over hypotheses
• $P$ — prior distribution over hypotheses
• $\text{KL}(Q \| P)$ — KL divergence from prior to posterior

Core Intuition

Classical statistical learning theory says: more parameters = higher complexity = more overfitting. Yet modern neural networks with millions of parameters generalize well despite perfectly fitting (interpolating) training data. This "mystery of generalization" in deep learning requires going beyond traditional bounds and understanding the implicit biases of the optimization algorithm, architecture, and parameterization.

Classical Generalization Bounds

Uniform convergence: With probability $\geq 1-\delta$, for all $f \in \mathcal{F}$:

The "complexity" term depends on the measure: VC dimension, covering numbers, or Rademacher complexity.

VC Dimension of Neural Networks

Definition. The VC dimension of $\mathcal{F}$ is the largest set of points that can be shattered (classified in all $2^n$ possible ways) by functions in $\mathcal{F}$.

For neural networks: A network with $W$ weights has VC dimension $\Theta(W\log W)$ (Bartlett et al., 1998). For a modern network with $W = 10^9$ parameters and $n = 10^6$ samples, the bound gives:

This is vacuous (greater than the maximum possible loss). Classical bounds completely fail to explain neural network generalization.

Rademacher Complexity

Definition. The empirical Rademacher complexity of $\mathcal{F}$:

where $\sigma_i \in \{-1, +1\}$ are independent Rademacher random variables.

Interpretation: How well can $\mathcal{F}$ correlate with random noise? High correlation = high complexity.

Bound: $R(f) \leq \hat{R}_n(f) + 2\mathcal{R}_n(\mathcal{F}) + \sqrt{\frac{\log(1/\delta)}{2n}}$.

For neural networks with bounded weights (spectral norm constraints), norm-based Rademacher bounds can be non-vacuous.

PAC-Bayes Bounds

The PAC-Bayes framework bounds the expected risk of a distribution $Q$ over hypotheses:

Theorem (McAllester, 1999). For any prior $P$ (chosen before seeing data) and any $\delta > 0$, with probability $\geq 1-\delta$ over the draw of training data, for all posteriors $Q$:

Interpretation: The generalization gap is bounded by how much the learned distribution $Q$ diverges from the prior $P$. If training doesn't move far from initialization (small KL), generalization is guaranteed.

Application to neural networks: Let $P = \mathcal{N}(\boldsymbol\theta_0, \sigma_P^2\mathbf{I})$ (centered at initialization) and $Q = \mathcal{N}(\hat{\boldsymbol\theta}, \sigma_Q^2\mathbf{I})$ (centered at learned weights). Then:

The bound is tighter when parameters stay close to initialization and when the posterior is concentrated (low $\sigma_Q$).

Flat vs Sharp Minima

Hypothesis: Networks that converge to "flat" minima (large region with low loss) generalize better than those at "sharp" minima.

Formalization (Keskar et al., 2017): Sharpness of minimum $\boldsymbol\theta^*$:

Flat minima are robust to perturbations → robust to train/test distribution shift.

Connection to PAC-Bayes: A flat minimum allows a wide Gaussian posterior $Q$ around $\hat{\boldsymbol\theta}$ with low expected empirical risk, reducing the KL term and yielding a tighter bound.

SAM (Sharpness-Aware Minimization): Explicitly minimizes the worst-case loss in a neighborhood, seeking flat minima:

Implicit Regularization of SGD

SGD with finite learning rate introduces implicit biases:

1. Minimum-norm bias: Gradient flow from zero initialization converges to the minimum-norm interpolant (see Gradient Flow).
2. Noise-induced regularization: SGD noise (from mini-batches) helps escape sharp minima, favoring flat ones.
3. Edge of stability: With large learning rate, SGD oscillates at the edge of stability, implicitly regularizing the largest Hessian eigenvalue.
4. Label noise robustness: Early in training, SGD learns signal (low-frequency patterns) before noise (high-frequency) — "early stopping" regularizes even without explicit stopping.

Double Descent Revisited

The test error as a function of model complexity ($d$):

In the heavily overparameterized regime, many interpolating solutions exist; SGD selects the one with favorable properties (minimum norm, flat, aligned with data structure).

Common Pitfalls

Pitfall 1. Citing VC dimension bounds for neural networks as meaningful. They are astronomically loose — orders of magnitude above any achievable gap.

Pitfall 2. Equating "interpolation" with "overfitting." In the overparameterized regime, interpolating models can generalize perfectly well due to implicit regularization.

Pitfall 3. Assuming flatness alone explains generalization. Flatness is parameterization-dependent (reparameterizing weights can make any minimum appear flat or sharp).

Research Perspective

Understanding why deep networks generalize remains one of the central open problems in machine learning theory. Current leading explanations involve: (1) implicit bias of SGD toward low-complexity solutions, (2) the structure of real data (low intrinsic dimension), (3) architecture-induced biases (convolutions, attention), and (4) the neural tangent kernel regime for very wide networks. No single theory fully explains all observations.

Summary

• Classical VC/Rademacher bounds are vacuous for modern networks.
• PAC-Bayes provides tighter bounds via the KL between learned and prior distributions.
• Flat minima generalize better; SGD is biased toward finding them.
• Implicit regularization of SGD (minimum norm, noise-induced) partially explains generalization.
• Double descent shows that more parameters can improve generalization beyond the interpolation threshold.

Exercises

Exercise 1. Compute the VC dimension of the class of linear classifiers in $\mathbb{R}^d$ and verify it equals $d+1$.

Exercise 2. For a prior $P = \mathcal{N}(0, \sigma^2\mathbf{I})$ and posterior $Q = \mathcal{N}(\boldsymbol\mu, \sigma^2\mathbf{I})$, compute $\text{KL}(Q \| P)$.

Exercise 3. Show that adding Gaussian noise to weights is equivalent to L2 regularization in expectation (for quadratic loss).

Exercise 4. For a linear model interpolating $n$ points in $d > n$ dimensions, derive the minimum-norm solution and show it generalizes better than a random interpolant.

Exercise 5. Explain why the "edge of stability" phenomenon (loss oscillating but not diverging with large learning rate) constitutes implicit regularization of the Hessian's top eigenvalue.