PAC-Bayes Generalization Bounds: From McAllester to Nonvacuous Bounds

Modern generalization theory begins with a puzzle: deep networks fit random labels with zero training error yet still generalize when the labels are real (Zhang et al. 2017). By any classical capacity measure (VC dimension, parameter count, Rademacher complexity on a norm ball wide enough to memorize), the hypothesis class is too rich for a non-trivial test-error bound; the random-label baseline is therefore not a bound but a sharp falsification of capacity-based explanations¹. Four resolutions emerged, each with its own well-known structural problems walked through paragraph-by-paragraph after the SoTA leaderboard below: PAC-Bayes, spectrally-normalized margin bounds, information-theoretic mutual-information bounds, and sharpness-based empirical predictors. A fifth strand is the impossibility result of (Nagarajan and Kolter 2019), which proves a formal obstruction to the entire uniform-convergence program.

The PAC-Bayes resolution (section PAC-Bayes Framework) replaces worst-case analysis over a hypothesis class with a weighted average over an algorithm-dependent posterior $Q$; the bound depends only on the KL divergence $\mathrm{KL}(Q \Vert P)$ between $Q$ and a data-independent prior $P$. Introduced by (McAllester 1999), refined by (Seeger 2002) for Gaussian-process classifiers via a binary-kl form, and systematized by (Catoni 2007) into a thermodynamic formalism, the framework was first made non-vacuous on a realistic deep network by (Dziugaite and Roy 2017) using a SGD-optimized Gaussian posterior on a 3-layer MLP². (Neyshabur et al. 2018) connected PAC-Bayes with spectral norms via a perturbation argument; the resulting bound remains vacuous on production-scale ConvNets because the $\sqrt{\mathrm{KL}/n}$ term blows up under the huge KL between random initialization and the trained weights³, and tightening the KL via a posterior shift toward zero conflicts with low train risk⁴. A second-generation refinement uses data-dependent priors (priors learned on a held-out split) (Dziugaite and Roy 2018)(Perez-Ortiz et al. 2021), at the cost that any data dependence in $P$ inflates the bound or breaks the proof⁵.

The spectrally-normalized margin resolution (section Spectrally-Normalized Margin Bounds) extends (Schapire et al. 1998)'s margin theory for boosting to neural networks: (Neyshabur et al. 2015) gave the first product-of-Frobenius bound, (Bartlett et al. 2017) sharpened it to the product of spectral norms divided by the classification margin. The bound is conceptually clean but suffers from spectral-norm vacuity: $\prod_\ell \|W_\ell\|$ grows polynomially in depth and the bound is vacuous beyond a small architecture⁶. The information-theoretic resolution (section Information-Theoretic Generalization Bounds) was initiated by (Russo and Zou 2016) in the adaptive-data-analysis literature and developed into a general tool by (Xu and Raginsky 2017), who replaced capacity with the mutual information $I(S; W)$ between the training sample and the learned weights. (Bu et al. 2020) sharpened the bound using per-sample MI $I(Z_i; W)/n$, which is tighter but harder to estimate⁷; (Haghifam et al. 2020) gave a conditional MI (CMI) refinement⁸, and (Pensia et al. 2018) applied the framework to Langevin dynamics where the MI admits a closed form.

A complementary line, orthogonal to capacity in the PAC sense, asks how parameter count itself relates to robust interpolation. (Bubeck and Sellke 2021) prove the Universal Law of Robustness via an isoperimetric argument: any class of $p$-parameter Lipschitz models that interpolates $n$ labelled points on a distribution satisfying isoperimetry (Gaussians, uniform distributions on spheres, manifolds with positive Ricci curvature all qualify) must satisfy $p \gtrsim n d$ up to logarithmic factors, where $d$ is the ambient data dimension. Put differently, the $\mathcal{O}(n)$ parameters sufficient for non-robust interpolation are provably insufficient for smooth (i.e., Lipschitz-bounded) interpolation by a multiplicative factor of $d$. The bound is tight: radial-basis-function constructions with $p = n(d+1)$ parameters achieve $\mathcal{O}(1)$-Lipschitz interpolation, confirming that overparameterization by exactly $d$ is both necessary and sufficient.

The isoperimetry assumption controls how Lipschitz functions concentrate on the data distribution: for an $L$-Lipschitz $f$, it requires $\Pr[|f(x) - \mathbb{E}[f]| \geq t] \leq 2\exp(-dt^2 / 2cL^2)$. The condition is the reason the bound's factor of $d$ is ambient dimension and not intrinsic manifold dimension (a distinction that matters in practice, since ImageNet data lives in $\mathbb{R}^{150528}$, not in a low-dimensional manifold for the purposes of adversarial perturbations measured in $\ell_2$).

The lower bound is algorithm-independent: it applies to any procedure returning a Lipschitz interpolator, so neither implicit bias nor training dynamics can rescue a model from the $p \gtrsim nd$ constraint. The bound gives a quantitative explanation of the (Szegedy et al. 2014) fragility observation (imperceptible adversarial perturbations fool AlexNet, with average $\ell_2$ distortion as small as 0.0065 on ImageNet): under-parameterized-for-robustness networks cannot achieve small Lipschitz constants even when they generalize cleanly on unperturbed inputs. Bubeck and Sellke estimate that robust ImageNet models may require $10^{10}$ - $10^{11}$ parameters, substantially more than current architectures, which is consistent with the persistent failure of adversarial training to close the accuracy-robustness gap at scale.

The sharpness-based empirical audit (section Empirical Audit of Bound Tightness) is the negative result: (Jiang et al. 2020) evaluated more than forty complexity measures across ten thousand trained networks. The most predictive measures (by Kendall-tau rank correlation with the true test gap) are sharpness / PAC-Bayes variants, not the norm-products that dominate the theory; the spectral-norm product is negatively correlated with the gap across realistic hyperparameter sweeps⁹¹⁰. The impossibility result of (Nagarajan and Kolter 2019) sharpens this picture: no two-sided uniform-convergence bound can be non-vacuous on certain linear classifiers under realistic SGD¹¹; (Negrea et al. 2020) partially defends uniform convergence by restricting attention to a hypothesis-class subset.

The table groups the literature into eight bound families, walked through in chronological order. Classical PAC-Bayes (McAllester, Seeger, Catoni, Lacasse) gave the foundational machinery (square-root form, binary-kl inversion, Legendre/Gibbs construction, C-bound derandomization) but was applied only to toy classifiers and Gaussian-process models; the bounds are tight asymptotically but were never fielded on a deep network because the KL between a deep-net random init and its SGD-trained weights is far too large for a useful absolute bound¹²¹³. The Dziugaite-Roy line broke this barrier by SGD-optimizing the bound itself on a 3-layer MLP¹⁴, reaching 0.161 on binary MNIST T-600; Perez-Ortiz tightened the recipe to 0.2377 on CIFAR-10 with a 9-layer CNN by combining a prior learnt on a 70 percent split (legal because $P$ does not see the training fold) with a tuned Catoni $\beta$¹⁵.

The spectrally-normalized margin line (Bartlett-Foster-Telgarsky, Neyshabur PB-spectral) unifies VC-style class capacity with margin theory. The bound class is conceptually appealing because it depends only on weight-matrix norms and the margin (no $Q$-design), but the spectral product $\prod_\ell \|W_\ell\|_2$ is empirically too large at production scale¹⁶; in the (Jiang et al. 2020) sweep this family scored Kendall $\tau = -0.537$ with granulated $\Psi = -0.434$, the largest-magnitude correlation of any measure they tried and pointing the wrong way. Norm-product capacity, the quantity the margin theorems control, is therefore not uninformative about generalization; it is informative with the sign reversed, which is a stronger and more uncomfortable result than mere noise. Jiang et al. trace most of that predictive power to depth: the spectral product's correlation with the gap runs at $-0.908$ along the depth axis alone, and the conditional mutual information it carries collapses once depth is already observed.

The information-theoretic line (Russo-Zou, Xu-Raginsky, Bu-Zou-Veeravalli, Haghifam CMI, Pensia, Lei, Esposito) replaces hypothesis-class capacity with the mutual information $I(S; W)$ between the training sample and the learned weights, and progressively tightens it: per-sample $I(Z_i; W)/n$ is sharper than $I(S; W)/n$¹⁷, conditional MI on a supersample is sharper still¹⁸, and Langevin / SGD-noise dynamics give analytic closed forms. None of these has been fielded on a deep ConvNet: estimating $I(S; W)$ in dimensions exceeding $10^6$ remains an open problem, and the bounds are useful as theoretical guarantees rather than numerical certificates.

The sharpness-empirical line (Jiang and co-authors) is conceptually a step back from formal bound-proving: it replaces "what is the absolute test gap?" with "which capacity-like measure best predicts the gap across a hyperparameter sweep?" This reframing is what produces the negative result for spectral-norm capacity and the positive result for sharpness-magnitude. Its weakness is flatness fragility: pointwise reparameterization can rescale sharpness arbitrarily without changing the predictor function (Dinh et al.)²², so any sharpness-based measure must be carefully normalized to be invariant under reparameterization; the field has not converged on a single such normalization.

The impossibility result and its partial rebuttals form the methodological coda. (Nagarajan and Kolter 2019) prove that on a linear-classifier mixture-of-Gaussians problem, no two-sided uniform-convergence bound applied to the SGD-output distribution can be tight: the bound is forced to be vacuous regardless of how the hypothesis class is parameterized²³. (Negrea et al. 2020) partially defends UC by restricting attention to a strict hypothesis-class subset that the algorithm visits with high probability; the result is that uniform convergence is salvageable but only via algorithm-dependent restrictions, which moves the framework closer to PAC-Bayes in spirit. Together with (Zhang et al. 2017)'s random-label baseline²⁴, the impossibility line is the negative half of modern generalization theory: a definitive falsification of class-capacity-only programs and a forcing function toward algorithm-dependent analyses (PAC-Bayes, MI, sharpness).

The leaderboard separates four eras: foundational PAC-Bayes (1999-2007), the deep-learning challenge (2015-2017, when capacity-based bounds were shown to be vacuous on real architectures and the puzzle of Zhang et al. was sharpened), the bound-engineering era (2017-2021, when SGD-optimized PAC-Bayes and data-dependent priors finally produced fielded non-vacuous numbers on small models), and the modern audit-and-impossibility era (2019-2024, dominated by the Jiang sweep and the Nagarajan-Kolter obstruction). Three readings. First, the only fielded non-vacuous bounds on real classifiers are PAC-Bayes-data-dep variants and only on MLPs / small CNNs at most; every classical norm-product or margin bound exceeds 1 on AlexNet-scale and beyond. Second, the most predictive measures of the empirical generalization gap (by Kendall $\tau$) are sharpness-magnitude hybrids, not the norm-products that dominate the theory. Third, the impossibility result of Nagarajan-Kolter shows that the entire class-capacity-only program cannot in principle deliver tight bounds for SGD-trained classifiers; the path forward is algorithm-dependent, in line with PAC-Bayes and MI but in contrast with the spectral-margin tradition.

References