Generalization Bounds: Mathematical Guarantees for Learning

The generalization bounds we've developed—from the union bound through Rademacher complexity to margin-based analysis—share a common limitation: they provide guarantees for the worst-case hypothesis that could be selected. The union bound says: 'for any hypothesis you might choose, the gap is bounded.' But learning algorithms don't choose hypotheses arbitrarily; they follow specific procedures that favor certain hypotheses over others.

PAC-Bayes bounds represent a paradigm shift: instead of bounding generalization for any single hypothesis, they bound the expected generalization error of a distribution over hypotheses. This subtle change has profound implications:

1. Algorithm-Specific Bounds: The analysis can incorporate properties of the learning algorithm (e.g., SGD finds solutions with specific structure)
2. Prior Knowledge Integration: Bayesian priors encode beliefs about which hypotheses are plausible
3. Tighter Bounds: By averaging over hypotheses, PAC-Bayes often yields significantly tighter guarantees
4. Non-vacuous Deep Learning Bounds: PAC-Bayes provides some of the first non-trivial generalization bounds for deep neural networks

The name 'PAC-Bayes' reflects the synthesis: PAC (Probably Approximately Correct) learning framework meets Bayesian reasoning about hypothesis distributions.

PAC-Bayes bounds consider distributions over hypotheses rather than single hypotheses. We develop the framework carefully.

The Key Objects:

1. Hypothesis Space: $\mathcal{H}$ is a (potentially infinite) set of hypotheses $h: \mathcal{X} \to \mathcal{Y}$

2. Prior Distribution: $P$ is a distribution over $\mathcal{H}$ chosen before seeing data. This encodes prior beliefs about which hypotheses are plausible.

3. Posterior Distribution: $Q$ is a distribution over $\mathcal{H}$ chosen after seeing data. This is the output of learning—not a single hypothesis, but a distribution.

4. Stochastic Classifier: The learned predictor is randomized: to classify $x$, sample $h \sim Q$ and output $h(x)$. The expected error is: $$R(Q) = \mathbb{E}{h \sim Q}[R(h)] = \mathbb{E}{h \sim Q}\mathbb{E}_{(x,y) \sim \mathcal{D}}[\mathbf{1}[h(x) \neq y]]$$

Why Distributions Over Hypotheses?

Interpretation 1: Bayesian Learning

In Bayesian learning, we start with a prior $P$ and update to a posterior $Q$ given data. PAC-Bayes provides frequentist guarantees for this Bayesian procedure.

Interpretation 2: Randomized Predictors

The distribution $Q$ represents randomized prediction: we average predictions over multiple hypotheses, often improving robustness.

Interpretation 3: Algorithm Analysis

Learning algorithms don't output a single hypothesis—they output a procedure (parameters, training state) that can be viewed as a distribution. For neural networks, $Q$ might be a Gaussian around the learned weights.

Interpretation 4: Compression

A 'tight' distribution $Q$ (concentrated on few hypotheses) indicates that the algorithm has found a simple, compressible solution. PAC-Bayes rewards compression.

We now state and prove the fundamental PAC-Bayes inequality, the cornerstone of the theory.

Theorem (McAllester's PAC-Bayes Bound): Let $P$ be any prior distribution over $\mathcal{H}$ chosen before seeing data. For any $\delta > 0$, with probability at least $1 - \delta$ over the draw of $S \sim \mathcal{D}^m$, simultaneously for all distributions $Q$ over $\mathcal{H}$:

$$\mathbb{E}{h \sim Q}[R(h)] \leq \mathbb{E}{h \sim Q}[\hat{R}(h)] + \sqrt{\frac{D_{\text{KL}}(Q | P) + \ln(2\sqrt{m}/\delta)}{2m}}$$

where $D_{\text{KL}}(Q | P) = \mathbb{E}_{h \sim Q}\left[\ln \frac{Q(h)}{P(h)}\right]$ is the KL divergence from $Q$ to $P$.

Interpretation:

The bound says: the generalization gap of a posterior $Q$ is controlled by:

1. KL Divergence: How far $Q$ has moved from the prior $P$. Large changes require more data.
2. Sample Size: $\sqrt{1/m}$ scaling, as expected from concentration.

The KL divergence plays the role of 'complexity'—it measures how much information about the data is encoded in $Q$.

Proof Outline:

Step 1: Change of Measure

For any function $\phi(h)$: $$\mathbb{E}{h \sim Q}[\phi(h)] = \mathbb{E}{h \sim P}\left[\frac{Q(h)}{P(h)} \phi(h)\right]$$

This converts expectations under $Q$ to expectations under $P$ (which is data-independent).

Step 2: Donsker-Varadhan Variational Formula

For any random variable $X$ under $P$: $$\ln \mathbb{E}{h \sim P}[e^X] = \sup_Q \left{\mathbb{E}{h \sim Q}[X] - D_{\text{KL}}(Q | P)\right}$$

Rearranging for any $Q$: $$\mathbb{E}{h \sim Q}[X] \leq D{\text{KL}}(Q | P) + \ln \mathbb{E}_{h \sim P}[e^X]$$

Step 3: Apply to Generalization Gap

Let $X(h) = m \cdot (R(h) - \hat{R}(h))^2$. Using Hoeffding's lemma and the variational formula, we bound: $$\mathbb{E}{h \sim Q}[(R(h) - \hat{R}(h))^2] \leq \frac{D{\text{KL}}(Q | P) + \ln(2\sqrt{m}/\delta)}{2m}$$

Jensen's inequality and algebra complete the proof. $\square$

McAllester's bound is foundational but admits several refinements for practical applications.

Catoni's Bound (Tighter, Non-Square-Root Form):

With probability $\geq 1 - \delta$, for all $Q$ and any $\lambda > 0$:

$$D_{\text{kl}}\left(\mathbb{E}{h \sim Q}[\hat{R}(h)] | \mathbb{E}{h \sim Q}[R(h)]\right) \leq \frac{D_{\text{KL}}(Q | P) + \ln(2\sqrt{m}/\delta)}{m}$$

where $D_{\text{kl}}(q | p) = q \ln(q/p) + (1-q)\ln((1-q)/(1-p))$ is the binary KL divergence.

Solving for $R(Q)$ gives tighter bounds than McAllester for small training errors.

Seeger's Bound (Direct Binary KL Inversion):

For bounded losses in $[0, 1]$, with prob $\geq 1 - \delta$:

$$D_{\text{kl}}(\hat{R}(Q) | R(Q)) \leq \frac{D_{\text{KL}}(Q | P) + \ln(2\sqrt{m}/\delta)}{m}$$

Inverting this (numerically) gives the tightest known PAC-Bayes bounds.

Oracle PAC-Bayes (Data-Dependent Priors):

A subtle but powerful extension: use part of the data to construct the prior, then apply PAC-Bayes to the rest:

1. Split data: $S = S_1 \cup S_2$
2. Use $S_1$ to construct prior $P_{S_1}$
3. Apply PAC-Bayes with prior $P_{S_1}$ and data $S_2$

This allows data-dependent priors while maintaining validity.

PAC-Bayes with Unbounded Losses:

Extensions handle regression (squared loss) and other unbounded losses by truncating or using sub-Gaussian assumptions.

Comparison of Bounds:

The KL divergence $D_{\text{KL}}(Q | P)$ is the central quantity in PAC-Bayes. Understanding its role provides deep insight.

Information-Theoretic Interpretation:

KL divergence measures the 'information gained' when updating from prior $P$ to posterior $Q$: $$D_{\text{KL}}(Q | P) = \mathbb{E}_{h \sim Q}\left[\ln \frac{Q(h)}{P(h)}\right]$$

• If $Q = P$: no information gained, $D_{\text{KL}} = 0$
• If $Q$ concentrates on hypotheses unlikely under $P$: large $D_{\text{KL}}$
• If $Q$ is broad but shifted from $P$: moderate $D_{\text{KL}}$

Coding Interpretation:

$D_{\text{KL}}(Q | P)$ is the extra bits needed to describe a hypothesis from $Q$ using a code optimized for $P$. Small KL means the posterior is 'efficient' relative to the prior.

Compression Interpretation:

PAC-Bayes rewards solutions that can be compressed:

• A narrow posterior $Q$ (concentrated on few hypotheses) from a broad prior $P$ has small $D_{\text{KL}}$
• This indicates the algorithm found a simple pattern, not memorization

For Gaussian Prior/Posterior (Neural Networks):

In deep learning applications, common choices are:

• Prior: $P = \mathcal{N}(0, \sigma_P^2 I)$ (spherical Gaussian centered at origin)
• Posterior: $Q = \mathcal{N}(w, \sigma_Q^2 I)$ (Gaussian around learned weights $w$)

The KL divergence has closed form: $$D_{\text{KL}}(Q | P) = \frac{d}{2}\left(\frac{\sigma_Q^2}{\sigma_P^2} - 1 - \ln\frac{\sigma_Q^2}{\sigma_P^2}\right) + \frac{|w|^2}{2\sigma_P^2}$$

where $d$ is the number of parameters.

Key Observation: The term $|w|^2 / (2\sigma_P^2)$ is exactly L2 regularization! PAC-Bayes provides a principled interpretation: L2 regularization bounds the KL divergence from an isotropic prior, which bounds generalization.

Practical Implication: For a network with $d$ parameters, $|w|^2$ bounded, and $\sigma_Q \to 0$ (deterministic): $$D_{\text{KL}}(Q | P) \approx \frac{|w|^2}{2\sigma_P^2} + \frac{d}{2}\ln\frac{\sigma_P^2}{\sigma_Q^2}$$

The logarithmic dependence on $d$ (rather than linear) is what enables non-vacuous bounds for large networks!

PAC-Bayes provides some of the first non-trivial generalization guarantees for deep neural networks. Let's explore how.

The Challenge:

Deep networks have millions of parameters. Standard bounds give:

• VC dimension: $\tilde{O}(d \cdot L \cdot \log W)$ for $d$ parameters, $L$ layers
• Rademacher: $\tilde{O}(\prod_\ell |W_\ell|_F / \sqrt{m})$

For VGG-16 ($\sim 138$ million parameters), these exceed 1—vacuous!

PAC-Bayes Approach:

Step 1: Choose a Prior $$P = \mathcal{N}(0, \sigma_P^2 I)$$ with $\sigma_P$ chosen to reflect prior belief about weight scale.

Step 2: Define Posterior Around Learned Weights $$Q = \mathcal{N}(w^, \sigma_Q^2 I)$$ where $w^$ is the trained network's weights.

Step 3: Bound Stochastic Classifier Error

The stochastic classifier samples $w \sim Q$ and predicts. The expected error can be bounded using PAC-Bayes.

The Compression Perspective (Arora et al., 2018):

A key insight: neural networks can often be compressed without losing accuracy:

• Pruning: Remove small weights
• Quantization: Round weights to low precision
• Knowledge distillation: Train smaller network to mimic larger one

If a network can be compressed from $d$ parameters to effectively $k < d$ parameters, the PAC-Bayes bound depends on $k$ rather than $d$.

Theorem (Informal): If a neural network can be compressed to use $k$ effective bits (through quantization, pruning, etc.) while maintaining accuracy $\hat{R}$, then with high probability: $$R \leq \hat{R} + O\left(\sqrt{\frac{k + \log(1/\delta)}{m}}\right)$$

Noise Stability (Dziugaite & Roy, 2017):

Alternatively, if a network is stable to noise injection (adding Gaussian noise to weights doesn't hurt accuracy much), this implies a tight posterior $Q$:

1. Train network to weights $w^*$
2. Measure accuracy when using $w^* + \epsilon$ for $\epsilon \sim \mathcal{N}(0, \sigma^2 I)$
3. If accuracy is preserved, $\sigma$ can be large, making $D_{\text{KL}}(Q | P)$ small

Let's implement PAC-Bayes bound computation and see how to evaluate bounds for real models.

PAC-Bayes connects to many important concepts in machine learning theory.

Connection 1: Minimum Description Length (MDL)

The PAC-Bayes bound can be rewritten as: $$R(Q) \leq \hat{R}(Q) + \sqrt{\frac{L_P(Q) + O(\log m)}{m}}$$

where $L_P(Q) = D_{\text{KL}}(Q | P)$ is the description length of the posterior relative to the prior. MDL principle: prefer hypotheses with short description. PAC-Bayes formalizes this.

Connection 2: Bayesian Inference

The Bayesian posterior $Q^* = P(h | S) \propto P(S | h) P(h)$ minimizes a combination of empirical risk and KL divergence: $$Q^* = \arg\min_Q \left{\mathbb{E}{h \sim Q}[\hat{R}(h)] + \frac{1}{m} D{\text{KL}}(Q | P)\right}$$

This is the Gibbs posterior. PAC-Bayes shows it has optimal generalization guarantees!

Connection 3: Regularization

For Gaussian posteriors, KL divergence includes an L2 norm term. Thus:

• L2 regularization ↔ Gaussian prior → PAC-Bayes bound
• Dropout ↔ Specific noise distribution → PAC-Bayes bound
• Early stopping ↔ Limiting KL from initialization → PAC-Bayes bound

Extension 1: PAC-Bayes + Margins

Combining PAC-Bayes with margin analysis gives even tighter bounds: $$R_{0-1}(Q) \leq \hat{R}\gamma(Q) + \frac{1}{\gamma}\sqrt{\frac{D{\text{KL}}(Q | P) + O(\log m)}{m}}$$

Large margins reduce the complexity penalty!

Extension 2: PAC-Bayes for Gradient Descent

Recent work analyzes gradient descent through PAC-Bayes:

• The trajectory of SGD can be viewed as defining a posterior
• The implicit regularization of SGD corresponds to a specific KL penalty
• This provides generalization bounds specific to the optimization algorithm

Extension 3: PAC-Bayes with Excess Risk

Instead of bounding $R(Q)$ absolutely, bound the excess risk $R(Q) - R^$ where $R^$ is the Bayes-optimal error: $$R(Q) - R^* \leq \hat{R}(Q) - \hat{R}^* + O\left(\sqrt{\frac{D_{\text{KL}}(Q | P)}{m}}\right)$$

This shows how quickly we approach the best possible classifier.

We have developed PAC-Bayes bounds—the frontier of generalization theory, providing algorithm-specific guarantees that can be non-vacuous for modern deep networks.

Module Complete!

You have now mastered the complete toolkit of generalization bounds in statistical learning theory:

1. Union Bound: The bridge from individual to uniform guarantees
2. Hoeffding's Inequality: Exponential concentration for bounded random variables
3. Rademacher Complexity: Data-dependent complexity for infinite classes
4. Margin-Based Bounds: Geometric structure for tighter guarantees
5. PAC-Bayes Bounds: Algorithm-specific, Bayesian generalization theory

Together, these tools form the mathematical foundation for understanding why machine learning works—why algorithms that minimize empirical risk on finite samples can generalize to unseen data. This understanding guides algorithm design, architecture choices, regularization strategies, and the development of new learning methods.