ML Mathematics: Generalization¶

Job: state the generalization puzzle for over-parameterized neural networks — classical VC-dimension / Rademacher bounds are vacuous at the parameter scale of modern nets — and the modern resolutions: norm-based / spectral-norm Rademacher bounds (Bartlett–Foster–Telgarsky), double descent (Belkin–Hsu–Ma–Mandal), and PAC-Bayes bounds (McAllester, Dziugaite–Roy) that give non-vacuous generalization guarantees for trained nets.

Core¶

The generalization puzzle¶

The generalization gap of a network $f_{\hat\theta}$ trained on $n$ samples to zero empirical loss is $L_{\mathrm{test}}(\hat\theta)-L_{\mathrm{train}}(\hat\theta)=L_{\mathrm{test}}(\hat\theta)$ (since $L_{\mathrm{train}}=0$). For a ReLU net with $P$ parameters and $P\gg n$ (millions of parameters, thousands of samples), classical capacity-control bounds give:

Theorem (VC dimension of ReLU nets, Bartlett et al.; Harvey–Liang–Rajput). The VC dimension of a ReLU net with $W$ weights and $L$ layers is $\Theta(WL\log W)$; the Rademacher complexity of the hypothesis class $\mathcal{F}_\Theta$ (bounded weights) is $$ \mathfrak{R}n(\mathcal{F}\Theta)=O!\left(\sqrt{\frac{WL\log W}{n}}\right). $$

For $P=W\sim 10^7$, $n\sim 10^4$, the bound $\sqrt{P\log P/n}\gg 1$ — vacuous. The puzzle: the actual generalization gap is small, but the parameter-count-based bound is useless. The resolution is that the bound controls the wrong quantity — the effective capacity is not $P$ but a norm-based complexity that is small for the trained net.

Norm-based / spectral-norm Rademacher bounds¶

Theorem (Bartlett–Foster–Telgarsky 2017, spectral-norm bound). For a depth-$L$ ReLU net $f(x)=W_L\sigma(W_{L-1}\cdots\sigma(W_1 x)\cdots)$ with weight matrices $W_i$, the Rademacher complexity is bounded by the spectral-norm product and the $l_{2,1}$ (group-$(2,1)$) norms of the first layer: $$ \mathfrak{R}n(\mathcal{F})\;\le\;\frac{C\,\prod^L|W_i|{\sigma}}{\sqrt{n}}\;\cdot\;\bigl(\sqrt{d\log n} + \log L\bigr)\;\cdot\;|W_1|, $$ where }\,/\,|W_1|_{\sigma$\|W_i\|_{\sigma}=\sigma_{\max}(W_i)$ is the spectral norm and $\|W_1\|_{2,1}=\sum_j\|w^{(1)}_j\|_2$ is the $l_{2,1}$ norm of the first-layer rows. The bound is independent of the parameter count $P$ when the spectral-norm product is $O(1)$ — i.e. for trained nets with controlled spectral norms, even if $P\gg n$.

The key insight: the effective complexity of a ReLU net is controlled by the product of spectral norms (a Lipschitz constant of the net) and the $l_{2,1}$ norm (a sparsity / coherence of the first layer), not by $P$. A trained net with $\prod_i\|W_i\|_{\sigma}=O(1)$ has Rademacher complexity $O(\sqrt{d\log n/n})$ — non-vacuous and dimension-controlled. The margin bound strengthens this: if the net classifies with margin $\gamma>0$ (the data is separated by the net with confidence $\gamma$), the generalization error is $O(\mathfrak{R}_n/\gamma)$ — large margins give small generalization error.

Bound	Quantity	Dependence on $P$	Vacuous for $P\gg n$?
VC dimension	$\Theta(WL\log W)$	yes, $O(P\log P)$	yes (vacuous)
Rademacher (param count)	$\sqrt{WL\log W/n}$	yes, $\sqrt{P/n}$	yes
Spectral-norm (BFT)	$\prod_i\\|W_i\\|_{\sigma}\sqrt{d\log n/n}$	no (norm only)	no (if norms controlled)
Margin (BFT)	$\mathfrak{R}_n/\gamma$	no	no
Compression / lottery ticket	compressed size $P'$	only via $P'\ll P$	no (if compressible)
PAC-Bayes (McAllester)	$\mathrm{KL}(Q\\|P)+\log n/n$	no	no (non-vacuous for posteriors)

Implicit regularization and compression¶

Theorem / perspective (Neyshabur–Bhojanapalli–Srebro–Recht; implicit regularization). Gradient descent on over-parameterized nets implicitly minimizes a norm-based complexity (the path-norm / spectral-norm product), biasing the trained net toward low-complexity solutions even without explicit regularization. The path-norm $\|\theta\|_{\mathrm{path}}=\sum_{\text{paths}}\prod_{i}|W_i|$ controls the Rademacher complexity and is the natural regularizer GD minimizes. The lottery ticket (Frankle–Carbin) observation — a sparse sub-network trains to comparable accuracy — is the empirical shadow of this: the trained net is effectively low-rank / sparse, and its generalization is controlled by the compressed size $P'\ll P$.

Double descent¶

Theorem / phenomenon (Belkin–Hsu–Ma–Mandal 2019; Advani–Saxe 2018). The test error of a learning model as a function of model complexity (parameters $P$ or basis size) has a second descent beyond the interpolation threshold $P=n$: after the classical U-curve (bias-variance tradeoff) peaks at $P\approx n$, the test error decreases again in the over-parameterized regime $P\gg n$, often reaching a lower minimum than the best under-parameterized model. The peak at $P=n$ (interpolation threshold) is the worst test error, corresponding to the most ill-conditioned interpolating solution; the descent for $P\gg n$ corresponds to the over-parameterized solutions being "smoother" / lower-norm and generalizing better.

The phenomenon contradicts the classical bias-variance tradeoff, which predicts that test error increases monotonically past the interpolation threshold. The reconciliation: classical bias-variance applies to the under-parameterized / interpolation regimes; the over-parameterized regime has a different geometry (minimum-norm interpolants), and the test error descends.

Theorem (Mei–Montanari 2022, random features / kernel ridgeless). For Gaussian random features (a fixed random feature matrix $\Phi\in\mathbb{R}^{n\times P}$ with i.i.d. Gaussian entries, ridgeless regression $=\min\|\Phi\beta-y\|$ with $\beta\in\mathbb{R}^P$), the test error in the proportional regime $P/n\to\gamma\in(0,\infty)$ exhibits double descent: the test error peaks at $\gamma=1$ (the interpolation threshold, where the Gram matrix $\Phi\Phi^T$ becomes singular / ill-conditioned) and descends on both sides, with the second descent ($\gamma>1$, over-parameterized) reaching a limit determined by the kernel / feature covariance spectra. The peak at $\gamma=1$ is the condition number blow-up of the feature Gram matrix.

PAC-Bayes bounds for NNs¶

Theorem (McAllester 1999; Dziugaite–Roy 2017 for NNs). For any prior $P$ over parameters and any posterior $Q$ (a distribution over parameter perturbations / compressed nets), with probability $1-\delta$, $$ L_{\mathrm{test}}(Q)\;\le\;L_{\mathrm{train}}(Q)\;+\;\sqrt{\frac{\mathrm{KL}(Q|P)+\log(2\sqrt{n}/\delta)}{2n}}. $$ Choosing $Q$ as a Gaussian perturbation around the trained weights $\hat\theta$ with variance chosen to minimize $\mathrm{KL}(Q\|P)$ gives a non-vacuous generalization bound for trained NNs (Dziugaite–Roy): the trained net is robust to small perturbations (the loss is flat near $\hat\theta$), so the perturbed posterior $Q$ has near-zero train loss and a small KL to a data-independent prior $P$, yielding a concrete numerical bound on $L_{\mathrm{test}}$ that is competitive with (and sometimes better than) the test error itself.

See it¶

Random-features double descent (Mei–Montanari). Let $\Phi\in\mathbb{R}^{n\times P}$ be a random feature matrix with i.i.d. $\mathcal{N}(0,1)$ entries, $y=\Phi\beta^\ast+\varepsilon$ for a true $\beta^\ast\in\mathbb{R}^P$ (or a linear ground truth in feature space), and ridgeless regression $\hat\beta=(\Phi^T\Phi)^+\,y$ (or $\hat\beta=\Phi^T(\Phi\Phi^T)^{-1}y$ in the over-parameterized regime $P>n$). The test error on a fresh input $x$ with features $\phi(x)\in\mathbb{R}^P$ is

\[ \mathcal{E}_{\mathrm{test}}=\mathbb{E}_x[(\phi(x)^T\hat\beta-y(x))^2]. \]

In the proportional regime $P/n\to\gamma$ (with $\Phi$ Gaussian, the Marchenko–Pastur spectrum governs the Gram matrix $\Phi\Phi^T$), the test error is computed via random matrix theory: for $\gamma<1$ (under-parameterized) the error is $\sigma^2/(1-\gamma)+\mathrm{bias}$ (curse of the missing dimensions); for $\gamma=1$ the Gram matrix is singular, the ridgeless solution is ill-defined / has divergent variance, and the error peaks (the worst test error at the interpolation threshold); for $\gamma>1$ (over-parameterized) the minimum-norm interpolant $\hat\beta=\Phi^T(\Phi\Phi^T)^{-1}y$ has test error $\sigma^2/(\gamma-1)+\mathrm{bias}\to\mathrm{bias}$ as $\gamma\to\infty$ — the second descent, with the error decreasing in $\gamma$. The peak at $\gamma=1$ is the condition number blow-up: $\Phi\Phi^T$ has smallest eigenvalue $\lambda_{\min}\to 0$ as $\gamma\to 1^-$, and the inverse $(\Phi\Phi^T)^{-1}$ amplifies the noise by $1/\lambda_{\min}\to\infty$; for $\gamma>1$ the minimum-norm solution inverts the $n\times n$ matrix $\Phi\Phi^T$ which is well-conditioned (smallest eigenvalue bounded away from $0$), so the noise amplification is controlled and the test error descends. This single computation — the Marchenko–Pastur / condition-number analysis of Gaussian random features — is the prototypical double-descent curve: the peak at $\gamma=1$ is a genuine condition-number singularity, and the second descent is the over-parameterized regime where the minimum-norm interpolant is smoother.

Check¶

Pin down exactly why the VC-dimension bound $\sqrt{WL\log W/n}$ is vacuous for modern nets ($P\sim 10^7$, $n\sim 10^4$) and why the spectral-norm bound is not, by computing both.

For $P=W=10^7$, $L=10^2$, $n=10^4$: the VC bound is $\sqrt{WL\log W/n}=\sqrt{10^9\cdot 16/10^4}=\sqrt{1.6\cdot 10^6}\approx 1.3\times 10^3\gg 1$, a bound on a probability / error that exceeds $1$ — useless. The spectral-norm bound: $\prod_i\|W_i\|_{\sigma}\sqrt{d\log n/n}$; for a trained net with controlled spectral norms $\|W_i\|_{\sigma}=O(1)$ and $L=100$, the product is $O(1)$, and $\sqrt{d\log n/n}$ for $d=10^3$ is $\sqrt{10^3\cdot 9/10^4}=\sqrt{0.9}\approx 1$ — a bound of $O(1)$, still not tight but not the $10^3$ of the VC bound. With margin $\gamma=0.1$ the margin bound gives $O(10)$, still loose, but with the PAC-Bayes perturbation (Dziugaite–Roy) one gets a numerical bound of $O(0.1)$ in concrete experiments. The point is not that the spectral-norm bound is always small but that it can be small when the norms are controlled (the trained net has small effective complexity), whereas the VC bound is always vacuous at scale — the right quantity is the norm, not the parameter count.

Explain why double descent does not contradict the classical bias-variance tradeoff, by identifying the regime in which each applies and the geometric origin of the peak.

Classical bias-variance applies to the under-parameterized regime (model complexity $\le n$): as complexity increases toward $n$, variance grows (the model fits noise) and the test error U-curves up to the peak at $P=n$ (interpolation). Beyond $P=n$ the classical theory does not apply — it assumes the model is uniquely determined by the data (the MLE / least-squares solution), but at $P>n$ the interpolating solution is non-unique and one selects the minimum-norm interpolant (or the GD trajectory), which has different geometry. The peak at $P=n$ is the condition-number blow-up of the Gram matrix (the interpolating solution is the most ill-conditioned, maximally sensitive to noise); the second descent for $P\gg n$ is the minimum-norm interpolant being smoother / lower-variance (the minimum-norm solution in the over-parameterized regime has smaller complexity by the implicit regularization of the pseudo-inverse). Hence classical bias-variance and double descent describe different regimes (under- vs over-parameterized) with different selection rules (unique MLE vs minimum-norm interpolant), and there is no contradiction — the U-curve is the under-parameterized regime, the second descent is the over-parameterized one.

Pitfalls¶

VC / parameter-count bounds are vacuous for modern nets: $\sqrt{P\log P/n}\gg 1$ for $P\sim 10^7$, $n\sim 10^4$; citing them as the generalization theory of deep learning is misleading. The right bounds are spectral / norm / PAC-Bayes.
Spectral-norm bound needs the norm controlled: the BFT bound is non-vacuous only when $\prod_i\|W_i\|_{\sigma}=O(1)$, which is an empirical property of trained nets, not a universal property of the architecture. A net with large norms has the same vacuous bound as the VC one.
Double descent peak is real, not an artifact: the peak at $P=n$ is a genuine condition-number singularity of the Gram matrix; it is not a sampling artifact or an overfitting of the test set. Treating it as an artifact misses the phenomenon.
Classical bias-variance is the under-parameterized regime only: the second descent is a new regime (minimum-norm interpolant); reconciling them requires recognizing the regime change, not adjusting the bias-variance formula.
PAC-Bayes bounds depend on the prior and the posterior: the choice of prior $P$ and the perturbation variance of $Q$ determine the bound; a poorly-chosen prior makes the bound vacuous. The non-vacuous bounds (Dziugaite–Roy) are for specific data-dependent posteriors, not arbitrary ones.
Implicit regularization is a perspective, partly conjectural: the "GD minimizes the path-norm" claim is supported by theory in some cases and is a research program in general; do not state it as a universal theorem.

Refs¶

Bartlett–Foster–Telgarsky, Spectrally-normalized margin bounds for neural networks (NeurIPS 2017)
Harvey–Liang–Rajput, Tight VC dimension for neural networks (2020); Bartlett–Maass–Wolfram, VC dimension bounds (earlier)
Belkin–Hsu–Ma–Mandal, Reconciling modern machine-learning practice and the classical bias-variance trade-off (PNAS 2019); Advani–Saxe, High-dimensional dynamics of over-parameterized neural networks (2018)
Mei–Montanari, The generalization error of random features (2022); Neyshabur et al., Implicit regularization in deep learning (2017)
McAllester, PAC-Bayesian model averaging (COLT 1999); Dziugaite–Roy, Computing non-vacuous generalization bounds for deep neural networks (ICML 2017)

Next¶

Approximation Theory · NTK & Optimization · Information-Theoretic Limits · ML Mathematics index · Statistics · Probability · Information theory · Optimization