Uniform convergence may be unable to explain generalization in deep learning

Vaishnavh Nagarajan; J. Zico Kolter

Source-linked AI summary

Uniform convergence may be unable to explain generalization in deep learning

Vaishnavh Nagarajan, J. Zico Kolter

arXiv:1902.04742v4Feb 13, 2019cs.LGstat.ML

TL;DR

The paper asks whether uniform-convergence bounds can fully explain why overparameterized deep networks generalize well. It examines their dataset-size behavior and constructs gradient-descent-trained linear and neural models, finding provable vacuity even after accounting for implicit bias, while noting scope limitations for explicit regularization and one-sided bounds.

Problem
Existing deep-learning generalization bounds based on uniform convergence are intended to explain overparameterized networks' good generalization, but their ability to provide appropriate dataset-size dependence remains uncertain.
Method
The paper empirically studies norm-dependent bounds and theoretically analyzes overparameterized linear classifiers and neural networks trained by gradient descent, including aggressively pruned algorithm-dependent hypothesis sets.
Results
Uniform-convergence bounds can increase with training-set size and remain at least 1 − ε even when restricted to gradient-descent outputs with test error at most ε.
Takeaways & Limitations
The findings cast doubt on uniform convergence as a complete explanation for generalization in overparameterized deep learning.
Takeaways & Limitations
The results do not preclude uniform convergence working when gradient descent uses explicit regularization, and the analysis targets two-sided bounds.

Abstract

from arXiv · show

Aimed at explaining the surprisingly good generalization behavior of overparameterized deep networks, recent works have developed a variety of generalization bounds for deep learning, all based on the fundamental learning-theoretic technique of uniform convergence. While it is well-known that many of these existing bounds are numerically large, through numerous experiments, we bring to light a more concerning aspect of these bounds: in practice, these bounds can {\em increase} with the training dataset size. Guided by our observations, we then present examples of overparameterized linear classifiers and neural networks trained by gradient descent (GD) where uniform convergence provably cannot "explain generalization" -- even if we take into account the implicit bias of GD {\em to the fullest extent possible}. More precisely, even if we consider only the set of classifiers output by GD, which have test errors less than some small $ε$ in our settings, we show that applying (two-sided) uniform convergence on this set of classifiers will yield only a vacuous generalization guarantee larger than $1-ε$. Through these findings, we cast doubt on the power of uniform convergence-based generalization bounds to provide a complete picture of why overparameterized deep networks generalize well.

1 Introduction

The paper identifies shortcomings in existing uniform-convergence bounds for explaining generalization in overparameterized models. It shows that these bounds may worsen with dataset size and remain vacuous even after incorporating gradient-descent bias and restricting to algorithmically selected classifiers.

Explaining why overparameterized networks generalize despite fitting random labels remains an open question motivating algorithm-dependent generalization bounds.
Existing bounds are often numerically large, lack desired width/depth dependencies, or apply only to modified or specially trained networks.
Existing bounds can increase with training dataset size, violating the criterion that they decrease at the same rate as generalization error.
Weight norms, including distance from initialization, can grow polynomially with training examples, causing norm-dependent bounds to grow with dataset size for small batches.
Across overparameterized linear and neural-network setups, any two-sided uniform-convergence bound can be nearly vacuous despite small generalization error.
The analysis argues that even aggressively pruning to hypotheses selected by gradient descent does not rescue uniform convergence, while explicit regularization remains outside the main scope.

2 Existing bounds vs. training set size

Experiments show that several norm-based generalization bounds can worsen as training-set size m grows, even while test error decreases. The observed mismatch arises because norm quantities in bound numerators increase with m.

Norm-based replacements for parameter-count terms introduce training-set-size dependencies in bound numerators, causing bounds to increase for small batch sizes.The paper identifies these numerator dependencies as contributing to vacuous behavior.
Test error decreases as 1/m^0.43, whereas the evaluated generalization bounds can increase with training-set size.Networks are trained with SGD on MNIST until 99% of training examples satisfy margin γ⋆ = 10.
The distance from initialization grows at least as m^0.4, and the product of spectral norms grows as m.Both quantities recur in the numerators of several recent bounds.
The observed growth in distance from initialization fails to explain generalization dependence on m, despite potentially improving width dependence.The same issue is reported for distance from the origin.
For the plotted bounds, the generalization terms grow as Ω(m^0.68) despite setting γ = 10 to make the training-error term at most 0.01.The growth is attributed to numerator terms that increase with m; larger γ values do not remove the m-dependence.
The reported behavior is setting-dependent: larger batches can produce better m-dependence, although breakdown persists across many tested hyperparameter settings.The authors frame this as evidence of potential limitations in uniform-convergence-based bounds.

3 Provable failure of uniform convergence

The paper constructs overparameterized classifiers that generalize well yet defeat even the tightest algorithm-dependent two-sided uniform-convergence bounds.

Motivation: Pseudo-overfitting explains only a limited portion of the bounds’ problems and therefore does not account for their failure.The authors instead investigate uniform convergence itself as a fundamental limitation.
Algorithm-dependent uniform convergence: The tightest algorithm-dependent bound restricts uniform convergence to hypotheses explored by the learning algorithm on high-probability datasets.This formalizes aggressive pruning of hypotheses associated with implicit regularization.
General failure result: Even when generalization error is at most ε, the tightest algorithm-dependent uniform-convergence error can be at least 1−ε.This result holds in the paper’s overparameterized GD or SGD examples.
Proof mechanism: For each learned classifier, a data-dependent bad dataset can have the same distribution as training samples while producing large empirical error.The construction exploits the distinction between random test data and a dataset selected in dependence on the learned classifier.
Scope: The failure applies to two-sided bounds, while the paper notes that hypothetical purely one-sided bounds are not covered by this argument.The authors also state that making existing tools purely one-sided is non-trivial.
High-dimensional linear classifier: In the linear example, setting the noisy coordinate to zero yields non-vacuous bounds, but no extension of that bound to the original classifier is possible in this example.The original classifier still has small test error despite the obstruction.
ReLU neural network: In the ReLU setup, test 0-1 error decreases as O(m^-0.5), while a constructed dataset obtained by swapping hyperspheres and flipping labels is completely misclassified.The bad dataset can contain as many as 60k points, indicating complexity that harms uniform convergence without affecting test error.
Broader interpretation: The paper conjectures that overparameterized networks combine simple macroscopic decision boundaries with microscopic fluctuations that impair uniform convergence.This is proposed as a broader interpretation of the linear and ReLU examples.

4 Conclusion and Future Work

The conclusion argues that existing uniform-convergence bounds can worsen with dataset size and can fail even after incorporating implicit bias, motivating alternatives such as algorithmic stability.

Conclusion: Existing uniform-convergence bounds can increase with training-set size for small batch sizes, and uniform convergence can fail even after accounting for implicit bias.The paper presents this as evidence against uniform convergence providing a complete explanation of deep-network generalization.
Future work: The authors suggest that future work on implicit regularization should account for how weight norms depend on sample size.They also identify algorithmic stability and other learning-theoretic techniques as promising alternatives.

A Summary of existing generalization bounds.

The paper summarizes existing ReLU-network bounds and emphasizes that their applicability or scaling can depend strongly on training and architectural conditions.

Overview: Table 1 provides an informal summary of selected existing generalization bounds for ReLU networks.The table is used to compare properties of the bounds discussed in the paper.
Dependence on training conditions: Li and Liang’s analysis assumes a learning rate of approximately O(1/m^1.2) and a batch size of approximately Ω(√m).Under these assumptions, the resulting bound cannot describe variation with other hyperparameters.
Sample-size scaling: Allen-Zhu et al.’s bound decreases as Ω(1/m^0.16), whereas the actual generalization error is typically as small as O(1/m^0.43).The comparison concerns dependence on training-set size with other quantities fixed.

B More Experiments

Additional experiments show that several parameter- and margin-based bounds behave poorly as training-set size changes, often worsening while test error improves.

Layerwise dependence on m: The lowermost layer shows the greatest dependence on training-set size m.
Distance between trajectories of shuffled datasets grows with m: Distances between solutions learned from different shuffles of the same dataset grow substantially with m.
Flat minima: Linear interpolation between weights learned from independent dataset draws preserves the original networks’ test error.
Frobenius norms grow with m when m ≫ h: For sufficiently large m, distance from origin grows as Ω(m0.42) for a width-256, depth-6 network.
Even a relaxed notion of margin does not address the m-dependency: Using the median training margin, the bounds grow as Ω(m0.48), while the median margin grows only as O(m0.2).
Effect of depth: For a single hidden-layer network with 50k hidden units, bounds decrease at most as Ω(m−0.066), whereas test errors decrease as O(m−0.35).
Effect of width: The bounds increase with m for widths h = 128 and h = 2000.

B.1 Effect of batch size

The experiments examine batch size and loss choices, finding that bounds often track parameter growth rather than the observed decrease in test error.

Bounds vs. batch size for fixed m: For fixed m = 16384, bounds increase by a couple of orders of magnitude as batch size decreases, while test error decreases.
Effect of depth: For a single hidden-layer network with 50k hidden units, bounds are nearly constant, decreasing at most as Ω(m−0.066), while test errors decrease as O(m−0.35).
Effect of width: For widths h = 128 and h = 2000, bounds grow as Ω(m0.94) and Ω(m0.79), respectively.
Bounds vs. m for batch size of 32: With batch size 32, bounds decrease as O(m−0.23), while test error decreases as Ω(m−0.44).
Squared error loss: Under squared error loss, distance from initialization and spectral norms grow at least as m0.3, while test error decreases as 1/m0.38.

C Pseudo-overfitting

The paper distinguishes pseudo-overfitting from a broader failure of uniform-convergence explanations, showing that margin-based bounds can remain non-decreasing or vacuous despite improving generalization.

Margin-based uniform convergence: Generalization error can decrease roughly as m−0.5 while the relevant margin quantity remains independent of m, making the bound non-decreasing and potentially vacuous.
Pseudo-overfitting: Pseudo-overfitting describes training-set-local output bumps that enlarge training margins without affecting nearby test margins.
Pseudo-overfitting: In this construction, choosing γ approximately ∆ makes the margin-based bound an m-independent constant close to 1.
Deep-network margins: For the deep-network experiment, the train–test margin gap decreases as O(m−0.33), while generalization error decreases faster as O(m−0.43).
Beyond pseudo-overfitting: The linear and hypersphere examples’ uniform-convergence failures do not rely on pseudo-overfitting, and pseudo-overfitting alone does not imply their uniform-convergence lower bounds.
Beyond pseudo-overfitting: The paper concludes that a phenomenon beyond pseudo-overfitting is at play in deep learning.

E Proof for Theorem 3.1"

The proof constructs a linear classifier that generalizes well but defeats algorithm-dependent uniform convergence through noise-negated datasets, yielding a nearly vacuous lower bound.

Setup: The model uses a linear classifier h(x) = w1x1 + w2x2, with class centers in x1 and isotropic Gaussian noise in x2.
Setup: Gradient descent learns weights with w1 = 2mu and a noise-dependent component w2 determined by the training samples.
Theorem 3.1: Theorem 3.1 gives εunif-alg(m, δ) ≥ 1 − ε whenever εgen(m, δ) ≤ ε for γ ∈ [0, 1].
Generalization: For γ ∈ [0, 1], the learned classifier has zero training L(γ) loss and distribution loss at most ε.
Uniform-convergence lower bound: Negating the training noise produces a dataset on which the learned classifier misclassifies every example and has loss 1.
Uniform-convergence lower bound: Because noise negation preserves the dataset distribution, any mass-1−δ sample space contains a paired bad dataset with positive probability when δ < 1/4.

F Neural Network with Exponential Activations

This section analyzes an infinite-width exponential-activation network with frozen hidden weights and trainable output weights, showing that it can generalize well while uniform convergence remains nearly vacuous.

Architecture and algorithm: The model is an infinite-width exponential-activation network with frozen hidden-layer weights and trainable output-layer weights, effectively a linear model over randomized features.The output is represented as h(x) = E_w[a_w exp(w · x)], and gradient descent updates the functional output weights.
Uniform convergence failure: For the same γ range, uniform convergence satisfies ϵunif-alg(m, δ) ≥ 1 − ϵ, making the guarantee vacuous despite the small generalization error.The lower bound follows from constructing a modified dataset whose points are misclassified while preserving the relevant distribution.
Analysis: The analysis derives a closed-form expression for the network output after each gradient-descent update and uses it to analyze training and test predictions.The proof proceeds through a closed-form update, an upper bound on generalization error, and a lower bound on uniform convergence.
Generalization: The learned network has zero training error because each training point’s contribution dominates the contributions from other points.Training inputs are correctly classified with margin 1.
Generalization: For γ ∈ [0, 1], the generalization error satisfies ϵgen(m, δ) ≤ ϵ.The result holds under the section’s distributional and dimensionality conditions with the stated probability guarantees.

G.1 Nearly vacuous bounds for any γ > 0.

The section extends the vacuity result beyond small margin parameters: the uniform-convergence-based bound remains nearly vacuous for every γ ≥ 0.

Motivation: Standard conversions from L(γ) test error to 0-1 test error typically optimize over γ > 0, so failure must be established beyond γ ≤ 1.The section explicitly addresses whether larger γ can avoid the vacuity shown for small γ.
Small γ: For γ ∈ [0, 1], the uniform-convergence term is nearly vacuous while the corresponding generalization error remains at most ϵ.Thus, the small-γ part of the converted 0-1-error bound cannot yield a meaningful guarantee.
All γ: The authors show that the right-hand side of the converted bound is nearly vacuous for any γ ≥ 0, including γ > 1.The argument rules out rescuing the guarantee by selecting a larger margin parameter.
Proof strategy: Assuming the converted bound were below 1/2 would imply a uniform-convergence quantity below 1/2, contradicting the established lower bound.The contradiction is stated through the resulting inequalities for the algorithm-specific uniform convergence term.

G.2 Applicability of the observation in Section 3.2 to other settings

The section examines how the vacuity phenomenon depends on model capacity, hypersphere separation, and the treatment of generalization error’s dependence on dataset size.

Capacity dependence: Full misclassification of the constructed set S′ requires sufficient overparameterization, through either larger network width or larger input dimension.When m becomes too large, S′ is not as strongly misclassified as in the reported setting.
Hyperparameter sensitivity: The observation is sensitive to the hypersphere-radius difference: with outer radius 2, SGD perfectly classifies both the test data and S′, so the uniform-convergence lower bound does not hold.This is an explicit hyperparameter setting where the claimed lower bound fails.
Weaker uniform convergence: The paper informally argues that a weaker, practice-oriented notion of uniform convergence may also remain vacuous by constructing a distribution-preserving adversarial set for a complex decision boundary.The constructed alternative distribution obeys the same assumptions, forcing the bound to be vacuous there as well.
Dependence on m: Although one simplified example can have generalization error growing with m, a modified setup with an estimated low-complexity boundary yields overall error decreasing with m in the sufficiently overparameterized regime.The noise-induced term O(e^−D/m) becomes smaller than the boundary-estimation contribution when D ≫ m ln(m/K).
Hypothesis-dependent bounds: Hypothesis-dependent uniform-convergence bounds are defined by comparing the specific learned hypothesis across nearly all datasets in a high-probability dataset set.The construction first selects Sδ with failure probability at most δ, then evaluates the learned hypothesis over that set.
Hypothesis-dependent bounds: Even these hypothesis-specific bounds fail when a typical training set and its corresponding bad set both lie in Sδ, because the learned hypothesis has low test error but unit empirical error on the bad set.The resulting lower bound is 1 − ϵgen(m, δ) with probability at least 1 − O(δ).

H An abstract setup

The abstract construction isolates why uniform convergence can fail: a learner may generalize perfectly while its training-set-dependent misclassified regions create datasets with the same distribution and maximal discrepancy.

Setup: The abstract setup uses a spherical Gaussian input distribution in R^D with labels determined by a target classifier h⋆.The Gaussian choice simplifies the argument, while the setup is stated to apply more broadly.
Learner construction: The learner misclassifies the negations of the training samples, requiring an overparameterized classifier with Ω(mD) parameters to store the relevant set.The paper identifies this construction as the mechanism behind the uniform-convergence failure.
Generalization: The learner has zero training and test error except for pathological sample intersections, which have probability zero under the distribution.Consequently, its generalization error is zero.
Uniform convergence failure: Despite this perfect generalization, the algorithm-specific uniform-convergence quantity equals 1.The failure persists after truncating the hypothesis space to hypotheses produced by the learner.
Uniform convergence failure: The construction works because the bad dataset has the same distribution as the training set, using Gaussian invariance under negation.For δ < 1/2, the probability of finding a suitable pair of datasets is at least 1 − 2δ > 0.
Interpretation: The abstract construction captures a learner whose misclassified region has low probability but is complex and highly dependent on the training-set draw.The authors suggest these traits are relevant to SGD-trained deep networks, while noting that the particular learner is artificial.

I Learnability and Uniform Convergence

Uniform convergence is sufficient for learnability but need not explain why a particular algorithm generalizes on a particular distribution. The paper constructs distributions showing that even restricting attention to hypotheses explored by the algorithm can leave the corresponding problem non-learnable.

The paper argues that uniform convergence may fail to explain generalization for a particular algorithm and distribution, despite being necessary for learnability.
Uniform convergence is equivalent to finite VC dimension and is necessary and sufficient for learnability in binary classification.
Learnability evaluates performance across all possible distributions, whereas a fixed algorithm may generalize well on one underlying distribution.
For the algorithm-dependent hypothesis class Hδ, the corresponding binary classification problem is shown to be non-learnable.
A constructed distribution places half its mass on correctly labeled data outside a flipped random sample and half uniformly on that flipped sample.
With high probability, a hypothesis in Hδ fits the flipped sample perfectly while retaining error at most ϵ on the original distribution.
Any learning rule fails on enough unseen flipped examples to incur error at least 1/16, yielding ϵlearnability(m) ≥ 1/16 − ϵ/2 independently of m.
The negative result extends immediately to VC-dimension, Rademacher-complexity, and covering-number bounds because they upper-bound the uniform-convergence term.

J.1 Deterministic PAC-Bayesian Bounds of Type A

The appendix analyzes deterministic PAC-Bayesian bounds for algorithm-dependent hypothesis sets, showing that both considered constructions remain tied to two-sided uniform convergence and can become constant despite negligible generalization error.

Type A: The Type A proof uses two cases to upper-bound empirical-minus-test error, then takes an absolute value to connect the result to the two-sided uniform-convergence bound.The two cases distinguish whether e^3/2 b exceeds a, with PAC-Bayesian inequalities applied in the second case.
Type A: Theorem J.1 establishes that the deterministic Type A PAC-Bayesian bound is lower-bounded through the algorithm-dependent uniform-convergence quantity.The argument constructs restricted sample and hypothesis sets and applies the generalization and perturbation bounds on those sets.
Type A: For sufficiently large D, Type A yields ϵpb-det-A(m, δ) = Ω(1) − O(ϵ) even when the generalization error is negligibly small.The corollary invokes ϵgen(m, δ) ≤ ϵ, zero training loss, and ϵunif-alg(m, 3δ) > 1 − ϵ under the stated δ and D conditions.
Type A: Type A selects hypothesis-specific posteriors Qh and adds perturbation terms to derive a deterministic PAC-Bayesian bound.The construction considers the best possible Qh for each hypothesis and defines the resulting algorithm-dependent bound through uniform convergence over hypotheses explored by the algorithm.
Type B: A second deterministic PAC-Bayesian construction, Type B, also has a bound lower-bounded by the algorithm-dependent uniform-convergence quantity.Its formal definition uses a prior P and hypothesis-specific distributions Qh, while the proof applies a margin-based loss and avoids extra perturbation terms in one step.
Type B: For sufficiently large D, Type B likewise gives ϵpb-det-B(m, δ) = Ω(1) − O(ϵ), so the bound can remain constant despite negligibly small generalization error.The result is stated for the same Section 3 setup and is concluded through Corollary J.2.1 under the stated δ and D conditions.