PAC-Bayes Bounds

Why This Matters

Classical generalization bounds (VC dimension, Rademacher complexity) scale with the number of parameters. For modern neural networks with millions or billions of parameters, these bounds are vacuous: they predict generalization error larger than 1 even for networks that generalize well in practice.

PAC-Bayes bounds offer a different approach. Instead of measuring the size of the hypothesis class, they measure how much the learning algorithm's output (posterior) differs from a prior chosen before seeing data. If the learned solution is close to the prior in KL divergence, the bound is tight. This provides a path to non-vacuous generalization bounds for deep networks.

Formal Setup

Let $\mathcal{H}$ be a hypothesis space. Let $P$ be a prior distribution over $\mathcal{H}$, chosen before seeing data. Let $Q$ be a posterior distribution over $\mathcal{H}$, which may depend on the training data $S = \{(x_1, y_1), \ldots, (x_n, y_n)\}$ drawn i.i.d. from $\mathcal{D}$.

Definition

Stochastic Classifier

A stochastic classifier draws $h \sim Q$ and predicts using $h$. The population risk of $Q$ is:

$R(Q) = \mathbb{E}_{h \sim Q}[R(h)] = \mathbb{E}_{h \sim Q}\left[\mathbb{E}_{(x,y) \sim \mathcal{D}}[\ell(h(x), y)]\right]$

The empirical risk of $Q$ is:

$\hat{R}_n(Q) = \mathbb{E}_{h \sim Q}\left[\frac{1}{n} \sum_{i=1}^{n} \ell(h(x_i), y_i)\right]$

Definition

KL Divergence

The Kullback-Leibler divergence from $Q$ to $P$ is:

$\mathrm{KL}(Q \| P) = \mathbb{E}_{h \sim Q}\left[\log \frac{Q(h)}{P(h)}\right]$

This measures how much $Q$ diverges from the prior $P$. It is zero when $Q = P$ and infinite when $Q$ has support outside $P$.

Main Theorems

Theorem

McAllester PAC-Bayes Bound

Statement

For any prior $P$ over $\mathcal{H}$ chosen independently of $S$, for any $\delta > 0$, with probability at least $1 - \delta$ over the draw of $S$, simultaneously for all posteriors $Q$:

$R(Q) \leq \hat{R}_n(Q) + \sqrt{\frac{\mathrm{KL}(Q \| P) + \log(n/\delta)}{2n}}$

Intuition

The bound has two terms. The first is the training performance of the stochastic classifier. The second is a complexity penalty that grows with $\mathrm{KL}(Q \| P)$. If the posterior concentrates near the prior, the penalty is small. The bound holds simultaneously for all posteriors $Q$, so you can optimize $Q$ after seeing data without invalidating the guarantee.

Proof Sketch

The proof uses a change-of-measure argument. Start from the moment generating function: for any fixed $h$, $\mathbb{E}_S[e^{n(R(h) - \hat{R}_n(h))^2}]$ is bounded by Hoeffding's lemma. Then use the Donsker-Varadhan variational formula: $\mathbb{E}_{h \sim Q}[f(h)] \leq \mathrm{KL}(Q \| P) + \log \mathbb{E}_{h \sim P}[e^{f(h)}]$ for any measurable $f$. Apply this with $f(h) = n(R(h) - \hat{R}_n(h))^2$, take expectations over $S$, and apply Markov's inequality.

Why It Matters

Unlike VC and Rademacher bounds, the PAC-Bayes bound depends on the relationship between the learned solution and a reference prior, not on the raw capacity of the hypothesis class. For a network with 10 million parameters, if the learned weights are close to initialization (a natural prior), the KL term can be small enough to give non-vacuous bounds.

Failure Mode

The bound is only useful when $\mathrm{KL}(Q \| P)$ is much smaller than $n$. If the prior is poorly chosen (far from the learned solution), the KL term dominates and the bound becomes vacuous. In practice, choosing the prior is the main difficulty. The bound also requires bounded loss; for unbounded losses, modified versions with sub-Gaussian assumptions are needed.

Theorem

Catoni PAC-Bayes Bound

Statement

For any prior $P$, any $\delta > 0$, and any $\lambda > 0$, with probability at least $1 - \delta$ over $S$, for all posteriors $Q$:

$R(Q) \leq \frac{1}{1 - e^{-\lambda}}\left(1 - \exp\left(-\lambda \hat{R}_n(Q) - \frac{\mathrm{KL}(Q \| P) + \log(1/\delta)}{n}\right)\right)$

Intuition

Catoni's bound is tighter than McAllester's because it avoids the square root. The parameter $\lambda$ can be optimized. For small empirical risk and small KL, Catoni gives substantially better numerical bounds.

Proof Sketch

Uses the exponential moment method directly. For bounded losses, the cumulant generating function satisfies $\log \mathbb{E}[e^{-\lambda(\ell - R)}] \leq \log(1 - R + Re^{-\lambda})$. Combine with Donsker-Varadhan and take expectations over $P$.

Why It Matters

In the race to produce non-vacuous bounds for deep networks, Catoni's bound consistently produces tighter numerical values than McAllester's. Dziugaite and Roy (2017) used optimized Catoni bounds to get the first non-vacuous generalization bound for a neural network on MNIST.

Failure Mode

Same prior-dependence issue as McAllester. The $\lambda$ parameter must be chosen or optimized, adding another degree of freedom. For very small training error, the bound approaches the KL term divided by $n$, which is the irreducible cost of choosing the posterior.

Why PAC-Bayes Works for Deep Learning

The key insight: overparameterized networks have many parameters, but the effective complexity of the learned solution may be low. PAC-Bayes captures this through three mechanisms.

Compression view. If the posterior $Q$ is a narrow Gaussian centered on the learned weights and the prior $P$ is a broader Gaussian centered on initialization, then $\mathrm{KL}(Q \| P)$ measures how many bits are needed to describe the learned weights relative to initialization. Networks that learn "simple" functions (expressible with low-precision weights) have small KL.

Flat minima. The posterior width relates to the flatness of the loss landscape. If the loss is insensitive to perturbations of the weights (a flat minimum), then $Q$ can be broad, the KL can be small, and the bound is tight. Sharp minima require narrow $Q$ and yield larger KL.

Data-dependent priors. Using part of the training data to choose the prior (with the remaining data for the bound) can dramatically tighten PAC-Bayes bounds. Ambroladze, Parrado-Hernandez, and Shawe-Taylor (2007) formalized this data-splitting approach.

Comparison with Classical Bounds

Bound type	Depends on	Deep net behavior
VC dimension	Number of parameters	Vacuous (billions of params)
Rademacher complexity	Norm constraints on weights	Often vacuous for practical norms
PAC-Bayes	KL(posterior, prior)	Non-vacuous with good prior
Algorithmic stability	Sensitivity to one sample	Bounded for SGD with early stopping

Common Confusions

Watch Out

PAC-Bayes does not require Bayesian inference

Despite the name, PAC-Bayes bounds are frequentist. The prior $P$ is not a belief; it is a reference distribution chosen for the bound. The posterior $Q$ is not computed by Bayes rule; it is any distribution, typically optimized to minimize the bound. You can apply PAC-Bayes to a deterministic network by setting $Q$ to be a Gaussian centered on the trained weights.

Watch Out

Non-vacuous does not mean tight

The first non-vacuous bound for MNIST (Dziugaite and Roy, 2017) was about 0.16 for a network with test error around 0.02. Non-vacuous means the bound is less than 1 (better than random guessing), which is a milestone but not a precise characterization of generalization.

Watch Out

The prior must be independent of training data

If you set $P$ after looking at the training data, the bound is invalid. The data-splitting trick (use half the data for $P$, half for the bound) is the standard workaround. Forgetting this independence requirement is a common error.

Canonical Examples

Example

Gaussian prior and posterior

Let $P = \mathcal{N}(0, \sigma_P^2 I_d)$ and $Q = \mathcal{N}(w, \sigma_Q^2 I_d)$ where $w$ are the trained weights and $d$ is the number of parameters. Then:

$\mathrm{KL}(Q \| P) = \frac{d}{2}\left(\frac{\sigma_Q^2}{\sigma_P^2} - 1 - \log\frac{\sigma_Q^2}{\sigma_P^2}\right) + \frac{\|w\|^2}{2\sigma_P^2}$

For $\sigma_Q \ll \sigma_P$ (narrow posterior, broad prior), this is approximately $\frac{\|w\|^2}{2\sigma_P^2} + \frac{d}{2}\log\frac{\sigma_P^2}{\sigma_Q^2}$. The first term penalizes large weights; the second penalizes many parameters that must be specified precisely. If $\sigma_Q$ can be large (the network is insensitive to weight perturbations), the second term shrinks.

Key Takeaways

• PAC-Bayes bounds depend on $\mathrm{KL}(Q \| P)$, not on the raw size of the hypothesis class
• The prior $P$ must be chosen before seeing data (or via data-splitting)
• Non-vacuous bounds for deep networks exist when the prior is chosen well (e.g., initialization)
• Catoni's bound is tighter than McAllester's in practice
• The connection to compression and flat minima explains why PAC-Bayes captures generalization better than VC/Rademacher for overparameterized models

Exercises

ExerciseCore

Problem

Let $P = \mathcal{N}(0, I_d)$ and $Q = \mathcal{N}(\mu, I_d)$ for some $\mu \in \mathbb{R}^d$. Compute $\mathrm{KL}(Q \| P)$. How does it scale with $d$ and $\|\mu\|$?

Hint

Reveal Solution

ExerciseAdvanced

Problem

A network has $d = 10^6$ parameters trained on $n = 50{,}000$ MNIST images with 0-1 loss. You set $P = \mathcal{N}(0, 0.1 \cdot I_d)$ and $Q = \mathcal{N}(w, 0.01 \cdot I_d)$ where $\|w\|^2 = 100$. The empirical risk of $Q$ (measured by sampling from $Q$ and averaging) is 0.02. Using McAllester's bound with $\delta = 0.05$, is the bound non-vacuous?

Hint

Reveal Solution

ExerciseResearch

Problem

Explain why data-dependent priors (using part of the training set to choose $P$) can dramatically improve PAC-Bayes bounds. What is the formal justification, and what fraction of data should you allocate to the prior?

Hint

Reveal Solution

References

Canonical:

• McAllester, "PAC-Bayesian Model Averaging" (1999), Sections 1-3
• Catoni, PAC-Bayesian Supervised Classification (2007), Chapters 1-2

Current:

• Dziugaite & Roy, "Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks" (2017)
• Perez-Ortiz, Rivasplata, Shawe-Taylor, Szepesvari, "Tighter Risk Certificates for Neural Networks" (JMLR 2021)

Next Topics

• Algorithmic stability: an alternative path to generalization bounds that does not require a prior
• Implicit bias and modern generalization: why SGD finds solutions with small PAC-Bayes complexity