Dimension-Free PAC-Bayes Generalization for Deep Neural Networks via Dirichlet Processes

Sumit Vashishtha

stat.MLOct 15, 2026

Dimension-Free PAC-Bayes Generalization for Deep Neural Networks via Dirichlet Processes

Authors: Sumit Vashishtha

Organizations: Independent Researcher

Abstract

Classical PAC-Bayesian generalization theory places prior distributions over Euclidean parameter space $Θ\subseteq \mathbb{R}^D$ , causing relative entropy to scale with network dimension $D$ . For modern overparameterized neural networks where $D \gg n$ , this parameter-counting dependency yields vacuous generalization bounds ( $> 1{,}000\%$ ). In this work, we resolve this barrier by shifting prior specification from internal parameters to the non-parametric space of data distributions $\mathcal{M}_1(\mathcal{Z})$ via a Dirichlet Process (DP), $\mathcal{DP}(α, F_0)$ , inducing parameter distributions through push-forward measures under the learning algorithm. By the Data Processing Inequality, parameter-space relative entropy is strictly bounded by the data-space DP divergence, which we evaluate in exact closed form using Digamma functions. The resulting PAC-Bayesian certificate is strictly invariant to network parameter count $D$ , width, and depth. On intrinsic $d^*$ -dimensional submanifolds, optimal partition scaling achieves the minimax non-parametric rate $\mathcal{O}(n^{-1/(d^*+2)} \sqrt{\ln n})$ . Across vision architectures scaling up to 4.2 million parameters ( $D = 7{,}850$ to $D = 4{,}203{,}522$ ) on the full MNIST benchmark, while classical weight-space bounds scale past $940\%$ (becoming vacuous), our data-space DP-PAC-Bayes certificate remains stable, non-vacuous, and certified at \textbf{ $8.8\%$ -- $9.4\%$ }.

Figures & tables

Figure 1: Generalization Certificates vs. Model Scale on MNIST (

n=60{,}000

). (a) Classical weight-space PAC-Bayes bounds grow with parameter count

D

, exceeding the

100\%

vacuity threshold for

D\geq 10^{5}

. In contrast, our data-space DP-PAC-Bayes certificate remains strictly non-vacuous (

\leq 10.3\%

, reaching

8.8\%

for overparameterized models), reliably upper-bounding held-out test error. (b) While compositional depth restricts posterior weight perturbation tolerance

\sigma_{\mathrm{post}}

, our data-space formulation contracts under the Data Processing Inequality, ensuring invariance to parameter count.

Architecture	Parameters ( $D$ )	Train Error	Test Error	Noise $\sigma_{\mathrm{post}}$	Weight-Space Bound	DP-BNN Bound [Ours]
Linear Classifier	$7{,}850$	$7.38\%$	$7.65\%$	$7.0\times 10^{-2}$	$45.2\%$	16.08% (Certified)
2-Layer MLP (128)	$101{,}770$	$1.57\%$	$2.62\%$	$4.8\times 10^{-2}$	$148.2\%$ (vacuous)	10.27% (Certified)
LeNet-5 CNN	$110{,}578$	$0.65\%$	$1.00\%$	$4.8\times 10^{-2}$	$153.4\%$ (vacuous)	9.35% (Certified)
Wide CNN	$390{,}410$	$0.68\%$	$1.02\%$	$4.8\times 10^{-2}$	$287.7\%$ (vacuous)	9.38% (Certified)
4-Layer MLP (384)	$600{,}970$	$1.41\%$	$2.27\%$	$4.8\times 10^{-2}$	$357.5\%$ (vacuous)	10.11% (Certified)
Deep Overparam CNN	$4{,}203{,}522$	$0.08\%$	$0.82\%$	$4.8\times 10^{-2}$	$946.8\%$ (vacuous)	8.78% (Certified)

Table 1: Empirical Generalization Certificates on the Full MNIST Vision Benchmark (

n=60{,}000

). Real empirical train error, held-out test error on

10{,}000

unseen images, weight noise tolerance

\sigma_{\mathrm{post}}

, classical weight-space PAC-Bayes bounds, and our data-space DP-PAC-Bayes certificates (

\delta=0.05

). Values exceeding

100\%

are vacuous.

Framework	Prior Domain	Sample Splitting	Depth Sensitivity	Dimension Scaling	Non-Vacuous ( $D\geq 10^{6}$ )
Weight-Space PAC-Bayes ( McAllester, 1999 )	$\Theta\subseteq\mathbb{R}^{D}$	None	$\Omega(L\ln W)$	$\mathcal{O}(D)$	No ( $>1{,}000\%$ )
Data-Split PAC-Bayes ( Dziugaite and Roy, 2017 )	$\Theta\subseteq\mathbb{R}^{D}$	Required ( $S_{1}\cup S_{2}$ )	Polynomial in $L$	$\mathcal{O}(D)$	No ( $>100\%$ )
Spectrally-Normalized ( Bartlett et al., 2017 )	$\Theta\subseteq\mathbb{R}^{D}$	None	$\prod_{l=1}^{L}\\|W_{l}\\|_{\mathrm{op}}$	Independent	No (Exponential in $L$ )
Uniform Stability ( Bousquet and Elisseeff, 2002 )	$\mathcal{Z}^{n}$	None	$\mathcal{O}(e^{L})$	Independent	No (for deep non-convex)
Data-Space DP-PAC-Bayes [Ours]	$\mathcal{M}_{1}(\mathcal{Z})$	None (100% data used)	Strictly Invariant	$\mathcal{O}(1)$ ( Dimension-Free )	Yes ( $\leq 8.8\%$ – $9.4\%$ certified)

Table 2: Theoretical landscape of generalization bounds for deep neural networks. Comparison across prior domain, empirical sample-splitting requirements, sensitivity to network depth

L

, explicit parameter-dimension scaling, and practical non-vacuity for overparameterized architectures (

D\geq 10^{6}

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Architecture	Parameters ( $D$ )	Train Error	Test Error	Noise $\sigma_{\mathrm{post}}$	Weight-Space Bound	DP-BNN Bound [Ours]
Tiny MLP	$42$	$0.0\%$	$0.0\%$	$1.0\times 10^{-1}$	$5.4\%$	8.6% (Certified)
Shallow MLP	$162$	$0.0\%$	$0.0\%$	$1.0\times 10^{-1}$	$9.3\%$	8.6% (Certified)
3-Layer MLP	$4,482$	$0.0\%$	$0.1\%$	$1.0\times 10^{-1}$	$45.1\%$	8.6% (Certified)
4-Layer MLP	$33,666$	$0.0\%$	$0.0\%$	$1.0\times 10^{-1}$	$123.4\%$ (vacuous)	8.6% (Certified)
Wide MLP	$132,866$	$0.0\%$	$0.1\%$	$1.0\times 10^{-1}$	$245.1\%$ (vacuous)	8.6% (Certified)
Deep-5 MLP	$790,530$	$0.0\%$	$0.0\%$	$7.0\times 10^{-2}$	$654.7\%$ (vacuous)	8.6% (Certified)

Appendix

Table 3: Quantitative Comparison on the Concentric Annular Manifold (

n=20{,}000

). Ground truth test error, tolerable weight perturbation

\sigma_{\mathrm{post}}

, and resulting 95% PAC-Bayesian generalization certificates.

PAC-Bayesian Generalization Bounds

PAC-Bayesian Generalization Bounds use prior-to-posterior complexity to certify how well learned predictors perform beyond training data.

See all 34 papers

May 13, 2026

A Survey on Data-Dependent Worst-Case Generalization Bounds

Deep neural networks generalize well despite being heavily overparameterized, in apparent contradiction with classical learning theory based on uniform convergence over fixed hypothesis spaces. Uniform bounds over the entire parameter space are vacuous in this regime, and recent work has shown that non-vacuous guarantees can be recovered by restricting attention to the part of parameter space that the algorithm actually visits. This survey paper organizes this line of work around three steps: extending PAC-Bayesian theory to random, data-dependent hypothesis sets (arXiv:2404.17442); refining the complexity term with geometric and topological descriptors of the optimization trajectory, including fractal dimensions, alpha-weighted lifetime sums, and positive magnitude (arXiv:2006.09313, arXiv:2302.02766, arXiv:2407.08723); and replacing the resulting information-theoretic terms by stability assumptions (arXiv:2507.06775). We unify these contributions around a single template inequality and a head-to-head comparison of the resulting bounds.

Hubert Leroux, Jean Marcus, Julien Roger

´Ecole polytechnique Palaiseau, France

Neural Network Generalization PAC-Bayesian Generalization Bounds Generalization Bounds Algorithmic Generalization

Ask PDF

May 25, 2026

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms

Understanding the relationship between generalization and privacy remains a challenge in modern machine learning theory, particularly for deep networks that are trained by variants of differentially private stochastic gradient descent (DP- SGD). In this work we make progress on this persistent open problem. First, we derive explicit upper bounds on the approximate max-information of any algorithm that fulfills

(ε, δ)

-differential privacy or Rényi differential privacy, thereby going beyond the classical results for pure

ε

-differential privacy. Subsequently, we show even stronger guarantees for two common private learning algorithms, output perturbation with the Gaussian mechanism, and streaming DP-SGD, by exploiting the structure of their internal randomization. As an application of our results, we demonstrate how to obtain non-vacuous PAC-Bayes generalization bounds for deep networks, in which the prior distribution is learned by DP-SGD instead of the classical way of choosing it in a data-independent way.

Christoph H. Lampert, Max Cairney-Leeming, Hossein Zakerinia

Institute of Science and Technology Austria (ISTA) Klosterneuburg, Austria

PAC-Bayesian Generalization Bounds Differentially Private Stochastic Gradient Descent Information-Theoretic Generalization Bounds Differential Privacy

Ask PDF

Apr 17, 2026

When Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth

Early-exit neural networks enable adaptive computation by allowing confident predictions to exit at intermediate layers, achieving 2-8

\times

inference speedup. Despite widespread deployment, their generalization properties lack theoretical understanding -- a gap explicitly identified in recent surveys. This paper establishes a unified PAC-Bayesian framework for adaptive-depth networks. (1) Novel Entropy-Based Bounds: We prove the first generalization bounds depending on exit-depth entropy

H(D)

and expected depth

\mathbb{E}[D]

rather than maximum depth

K

, with sample complexity

\mathcal{O}((\mathbb{E}[D] \cdot d + H(D))/ε^2)

. (2) Explicit Constructive Constants: Our analysis yields the leading coefficient

\sqrt{2\ln 2} \approx 1.177

with complete derivation. (3) Provable Early-Exit Advantages: We establish sufficient conditions under which adaptive-depth networks strictly outperform fixed-depth counterparts. (4) Extension to Approximate Label Independence: We relax the label-independence assumption to

ε

-approximate policies, broadening applicability to learned routing. (5) Comprehensive Validation: Experiments across 6 architectures on 7 benchmarks demonstrate tightness ratios of 1.52-3.87

\times

(all

p < 0.001

) versus

>

100

\times

for classical bounds. Bound-guided threshold selection matches validation-tuned performance within 0.1-0.3%.

Dongxin Guo, Jikun Wu, Siu Ming Yiu

The University of Hong Kong, Hong Kong, China · Brain Investing Limited, Hong Kong, China

Neural Network Generalization PAC-Bayesian Generalization Bounds Adaptive Inference Dynamic Neural Networks Early-Exit Neural Networks

Ask PDF

Abstract

PAC-Bayesian Generalization Bounds

Explore similar work

A Survey on Data-Dependent Worst-Case Generalization Bounds

From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms

When Do Early-Exit Networks Generalize? A PAC-Bayesian Theory of Adaptive Depth