Beyond Parameter Counting: Dimension-Free PAC-Bayes Generalization Bounds for Deep Networks via Dirichlet Processes

When Parameter Count Becomes a Shackle on Generalization Theory

Modern deep neural networks routinely have hundreds of millions of parameters, far exceeding the number of training samples. Yet classical PAC-Bayes generalization theory struggles badly in this overparameterized regime. The problem lies at its very foundation: the prior distribution is defined on the Euclidean parameter space $\Theta \subseteq \mathbb{R}^D$, causing the relative entropy—the key term in the generalization bound—to grow linearly with network dimension $D$. When $D \gg n$ (the sample size), this bound quickly inflates beyond 1000%, rendering it meaningless.

This is not a technical detail but a paradigm-level predicament. As long as the prior remains anchored in parameter space, any complexity measure based on parameter counting will fail in the overparameterized regime. To break this shackle, the prior's footing must be moved entirely out of parameter space.

PAC-Bayes generalization bounds are a class of generalization error upper bounds in statistical learning theory, built on the Probably Approximately Correct (PAC) framework and combined with Bayesian ideas. Their core form is typically: with high probability, the test error does not exceed the empirical error plus a complexity term, which is controlled by the KL divergence (relative entropy) between the posterior and prior distributions. In deep learning, if the prior is taken as a Gaussian on parameter space and the posterior is the weight distribution output by the learning algorithm, the KL term grows linearly with the parameter dimension $D$. This is precisely the root cause of classical PAC-Bayes bounds failing for overparameterized networks: when $D \gg n$, the complexity term dominates the bound, quickly pushing it above 100% and stripping it of practical meaning. Thus, designing a prior that does not depend on parameter dimension becomes the key to whether this theory can apply to modern deep networks.

Data Distribution Space: A New Home for the Prior

The core insight of this paper is: rather than designing a prior in parameter space, define the prior on the data distribution space $\mathcal{M}_1(\mathcal{Z})$. Specifically, the authors adopt a Dirichlet process $\mathcal{DP}(\alpha, F_0)$ as a nonparametric prior over data distributions, then induce a posterior distribution in parameter space through the push-forward measure of the learning algorithm.

The beauty of this transformation lies in its use of the Data Processing Inequality: the relative entropy in parameter space is strictly bounded by the DP divergence in data space. The DP divergence in data space can be computed in exact closed form via the Digamma function, completely bypassing parameter dimension. In other words, the generalization certificate now depends only on the intrinsic structure of the data distribution, regardless of the network's width, depth, or total parameter count.

For learning tasks operating on an intrinsic $d^$-dimensional submanifold, the authors prove that the optimal partition scaling can achieve the minimax nonparametric rate $\mathcal{O}(n^{-1/(d^+2)} \sqrt{\ln n})$. This means that even in the overparameterized regime, generalization error still decays as a power law in sample size, rather than being held hostage by parameter counting.

Dirichlet process (DP) is a stochastic process defined on the space of probability distributions, commonly used as a nonparametric Bayesian prior. Given a concentration parameter $\alpha > 0$ and a base distribution $F_0$, a sample drawn from $\mathcal{DP}(\alpha, F_0)$ is itself a probability distribution. It can be viewed as a distribution over "distributions": when $\alpha$ is large, the drawn distribution is closer to the base distribution $F_0$; when $\alpha$ is small, it tends to concentrate near a few atoms. In this paper, the DP is used as a prior over the data distribution $\mathcal{M}_1(\mathcal{Z})$, rather than the traditional prior over parameter space. Through the discrete structure of posterior concentration, the DP can adaptively characterize the intrinsic dimension of the data, so that the generalization complexity measure based on it does not depend on network parameter count.

The Data Processing Inequality states: if random variables $X \to Y$ form a Markov chain (i.e., $Y$ is obtained from $X$ via some transformation), then $I(X; Z) \ge I(Y; Z)$, where $I$ denotes mutual information. In the PAC-Bayes framework, this corresponds to: the push-forward measure from data space distribution to parameter space distribution does not increase relative entropy. Specifically, the KL divergence between the parameter-space posterior and prior is controlled by the KL divergence between the data-space DP prior and posterior. Since the data-space divergence can be computed exactly via the Digamma function and does not explicitly depend on parameter dimension, this inequality becomes the key bridge for "de-dimensionalizing" the generalization bound.

Experimental Validation: From 7,850 to 4.2 Million Parameters, the Certificate Holds Firm

Theoretical derivation requires empirical support. The authors tested multiple vision architectures on the full MNIST benchmark, ranging from $D = 7{,}850$ to $D = 4{,}203{,}522$ (about 4.2 million parameters). The results are highly convincing:

• Classical weight-space bounds: as parameter count increases, the generalization bound rapidly inflates, exceeding $940%$ on the largest model and becoming completely useless;
• Data-space DP-PAC-Bayes certificate: remains stable across all model scales, non-vacuous, with certified values in the $8.8%$–$9.4%$ range.

This means that when traditional methods collapse under the curse of dimensionality, the new framework still provides reliable generalization guarantees. More importantly, this certificate is strictly invariant to the number, width, and depth of network parameters—a truly "dimension-free" generalization bound.

Significance and Limitations: New Coordinates for Generalization Theory

The value of this work lies in repositioning the coordinate system of generalization theory: rather than continuing to patch things up in parameter space, it anchors complexity in the intrinsic dimension of the data distribution. This opens a nonparametric path for generalization analysis of overparameterized deep networks, and offers a new perspective on understanding "why large models can generalize"—generalization ability may not depend on how many parameters there are, but on how the learning algorithm performs inference in data distribution space.

Of course, current validation is still limited to MNIST and relatively small vision architectures. The impact of the choice of DP prior (such as the concentration parameter $\alpha$ and base distribution $F_0$) on the tightness of the practical certificate, as well as whether the method can extend to more complex architectures like Transformers, still requires further exploration. Additionally, although the closed-form computation of the data-space DP divergence is elegant, its numerical stability in larger-scale problems remains to be tested.

Regardless, this research points to a clear direction: to break through the generalization theory bottleneck of deep learning, it may be necessary to liberate the prior from parameters and let the data distribution itself define complexity.

The minimax nonparametric rate is a benchmark in statistical estimation theory for measuring the optimality of estimators. For nonparametric regression problems defined on a $d^$-dimensional smooth submanifold, when the true function has a certain smoothness, no estimator can converge faster than $\mathcal{O}(n^{-1/(d^+2)})$ (ignoring logarithmic factors), and kernel methods or local polynomial estimators exist that achieve this rate. This paper proves that the proposed DP-PAC-Bayes framework achieves this rate multiplied by $\sqrt{\ln n}$ under the intrinsic dimension $d^*$, meaning its generalization bound decays as a power law as sample size $n$ grows, rather than being dominated by network parameter dimension $D$. This result connects the generalization behavior of deep networks with classical nonparametric statistical theory, providing quantitative grounds for understanding why overparameterized models can still generalize.

One-line Summary

Moving the prior from parameter space to data distribution space, using Dirichlet processes to construct PAC-Bayes generalization bounds independent of parameter count.

Paragraph Summary

Classical PAC-Bayes generalization bounds define the prior in parameter space, causing relative entropy to grow linearly with network dimension and rendering the bound useless (exceeding 1000%) in overparameterized regimes. This paper proposes moving the prior to data distribution space, adopting a Dirichlet process as a nonparametric prior, and using the Data Processing Inequality to bound parameter-space relative entropy within the data-space DP divergence, which can be computed in closed form via the Digamma function and does not depend on parameter dimension. The theory proves achieving the minimax nonparametric rate O(n^{-1/(d*+2)} sqrt(ln n)) on an intrinsic d*-dimensional submanifold. Experiments on MNIST with architectures from 7,850 to 4.2 million parameters confirm the new certificate stabilizes at 8.8%–9.4%, while classical bounds exceed 940% and fail. This work opens a nonparametric path for generalization analysis of overparameterized deep networks, but validation is limited to smaller vision architectures, and extension to Transformers remains to be explored.