Capacity, VC Dimension, Rademacher Complexity, and Stability

Consider a class of linear separators in a plane. The two observations below are not an illustration invented for this lesson. They are the standard proof sketch on the way to VCdim(hyperplanes in R^d) = d+1, the one Mehryar Mohri gives in his Foundations of Machine Learning lecture on infinite hypothesis sets at NYU Courant.

Statistical learning theory asks when empirical performance can justify a claim about population performance across a class of candidate predictors. The difficulty grows when the algorithm may choose among many functions after seeing the data. Capacity measures describe how flexibly a class can fit different labelings or losses. Parameter count is one clue, but geometry, norms, margins, sparsity, and the learning algorithm can matter as much or more.

How weak a clue parameter count is has been measured. Standard architectures were trained on CIFAR-10 after every label had been replaced with a uniformly random one. A small Inception with 1,649,402 parameters reached 100.0% training accuracy and 9.78% test accuracy. AlexNet, with 1,387,786 parameters, reached 99.82% training and 9.86% test. An MLP 1x512 with 1,209,866 parameters reached 99.34% training and 10.61% test — chance on ten classes. Same architectures, same parameter counts; only the labels changed. Zhang and four colleagues put the finding in five words at ICLR 2017: “Deep neural networks easily fit random labels.” Effective capacity sufficed to memorise the whole 50,000-image training set while generalisation collapsed. Arpit and colleagues reproduced the memorisation of noise independently at ICML 2017, and argued that dataset-independent notions of effective capacity cannot explain how these networks generalize.

Capacity is not even monotone in the direction the textbook curve suggests. The double-descent risk curve was documented in the Proceedings of the National Academy of Sciences in 2019: test risk falls, rises to a peak at the interpolation threshold, then falls again as capacity grows past it. Belkin and three colleagues state it directly in the abstract — “This “double-descent” curve subsumes the textbook U-shaped bias–variance trade-off curve by showing how increasing model capacity beyond the point of interpolation results in improved performance.” Nakkiran and five colleagues reproduced the effect independently in modern deep networks at ICLR 2020. They added an epoch-wise version, and identified regimes where quadrupling the number of training samples makes test performance worse. More capacity can mean less risk. More data can mean more error. Raw class size is plainly not the quantity being controlled.

The classical result underneath all of this is older than any of it. Vapnik and Chervonenkis published the uniform convergence theorem in 1971.

These measures capture different aspects of flexibility, and each of the four has a dated primary result you can go and check.

VC dimension is the distribution-free combinatorial one. The classical route from it to a guarantee is the 1971 Vapnik–Chervonenkis uniform convergence theorem, and Theorem 9.3 of Shalev-Shwartz and Ben-David fixes the number for nonhomogenous halfspaces in R^d at d+1. It supports sample-complexity bounds, and it can be loose for trained deep models — for the reason the random-label experiment makes concrete.

Rademacher complexity has a datable primary result of its own. Bartlett and Mendelson open their 2002 paper in the Journal of Machine Learning Research with the plan: “We investigate the use of certain data-dependent estimates of the complexity of a function class, called Rademacher and Gaussian complexities.” Their Theorem 5(b) states that with probability at least 1-δ, every f in F satisfies P(Y ≠ f(X)) ≤ P̂_n(Y ≠ f(X)) + R_n(F)/2 + sqrt(ln(1/δ)/(2n)). Put that beside their Theorem 1, the VC-based bound, which scales as c·sqrt(VCdim(F)/n). The data-dependence is visible as a single substitution. R_n(F)/2, computed on the observed sample, stands where a complexity fixed in advance stood. Theorem 6 shows the exchange costs little: the Rademacher bound is never much worse than the VC one. Koltchinskii and Panchenko developed Rademacher-process bounds for combined classifiers independently that same year, in the Annals of Statistics.

Norm or margin control uses scale-sensitive properties of predictors, and it too has a theorem and an experiment. Bartlett and two colleagues proved at NIPS 2017 a margin-based multiclass generalization bound scaling with margin-normalized spectral complexity — the product of the spectral norms of the weight matrices, times a correction factor. They then trained AlexNet on MNIST and on CIFAR-10, with true labels and with random ones, and showed that the bound, the Lipschitz constants and the excess risk move together. That is a capacity measure that separates the true-label run from the random-label run. Counting labelings cannot do that. Golowich and two colleagues then gave norm-based Rademacher complexity bounds for neural networks at COLT 2018 that, under additional assumptions, are “fully independent of the network size (both depth and width)”.

Algorithmic stability is the column that is not a property of the class at all. Bousquet and Elisseeff state the programme in their 2002 abstract: “We define notions of stability for learning algorithms and show how to use these notions to derive generalization error bounds based on the empirical error and the leave-one-out error.” Their Definition 6 gives uniform stability β. Their Theorem 12 gives the bound: for a loss bounded by M, with probability at least 1-δ, R ≤ R_emp + 2β + (4mβ + M)·sqrt(ln(1/δ)/(2m)). Regularization in a Hilbert space (RKHS) with parameter λ has uniform stability β ≤ σ²κ²/(2λm), that is stability of order 1/m, which is exactly the regime in which the theorem is tight. So the regularization parameter is what buys the guarantee, and the sentence "useful for regularized algorithms" has an inequality behind it. Hardt and two colleagues later proved at ICML 2016 that stochastic gradient descent is itself “algorithmically stable in the sense of Bousquet and Elisseeff”, in the convex and non-convex cases.

A neural architecture may represent many functions, while an optimizer, initialization, early stopping rule, or norm penalty makes only a subset easy to reach. Telling those two apart motivates algorithm-dependent and norm-based analyses. The formal hypothesis class alone can overstate the flexibility exercised in practice. The Dziugaite and Roy table shows by how much: a VC-dimension bound of 26 million sitting over 55,000 examples, while the trained stochastic network makes 0.034 test error.

The two anchored routes out of the gap are the ones already named. Bousquet and Elisseeff's β ≤ σ²κ²/(2λm) is an explicit statement of how much an explicit penalty buys, and the ICML 2016 stability result carries the same treatment over to stochastic gradient descent itself. The spectral-norm quantity is the norm-based route: a number computed from the trained weights that moved with the excess risk in the AlexNet experiments.

However, “implicit regularization” should not become an explanation nobody has measured. The induced bias must be characterized for the actual training procedure. Nagarajan and Kolter show how far that characterization may have to go. Restricting attention to the set of classifiers gradient descent actually outputs was not enough to rescue two-sided uniform convergence in their construction. It still left a guarantee larger than 1-ε on networks whose test error was below ε.

Use these checks when a paper or report cites a learning-theory guarantee: identify the random sample, the class, and the loss; read the probability statement; inspect constants and scaling; and compare with shift.

Two of the six steps have worked examples in this lesson. Inspecting constants and scaling is what separates 26 million from 55,000 in the Dziugaite and Roy setting, and separates both from an optimized PAC-Bayes value of 0.161 holding with probability 0.965. The same trained network, three numbers, and only one of them informative at that sample size. Reading the probability statement is what keeps 0.161 in its place: it bounds test error with probability 0.965, not with certainty, and it is not a forecast of the 0.034 actually observed.

The scaling check also has a failure mode worth naming, since it is the one nobody looks for. Nagarajan and Kolter found bounds that increase with the training dataset size. A guarantee can degrade under the one intervention practitioners assume always helps.

A classical proof separates approximation, estimation, and optimization components. A hypothesis class H is fixed, empirical risk is computed for each candidate on the sample, a uniform bound controls sample-to-population deviation for all candidates at once, the empirical minimizer is chosen after observing the data, and the selected predictor is finally compared with the best member of H.

The uniform bound in the middle of that chain is where a capacity measure enters, and which measure enters is a choice: c·sqrt(VCdim(F)/n) in Bartlett and Mendelson's Theorem 1, or R_n(F)/2 computed on the observed sample in their Theorem 5(b). It is also the step Nagarajan and Kolter attack. In their construction two-sided uniform convergence is precisely what fails while the learned classifier still generalizes. That is why algorithm-dependent measures such as uniform stability, defined on the procedure rather than on H, are a different argument and not a refinement of this one.