Uniform convergence may be unable to explain generalization in deep learning

By Vaishnavh Nagarajan, J. Kolter. 2019

365 citations recorded by the source corpus.

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 $\epsilon$ 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-\epsilon$. 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.

Subfields: Artificial Intelligence, Scaling & Learning Theory, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Scaling & Learning Theory

In Statistical Learning Theory

Citations in the corpus

Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time (2022, background): “By contrast, Nagarajan and Kolter (2019 Stochastic Weight Averaging (SWA) (Izmailov et al., 2018), which averages weights along a single optimization trajectory, is also motivated by the relation between ensembling model outputs and averaging model weights.”
Linear Mode Connectivity and the Lottery Ticket Hypothesis (2019, background): “The only extant example of linear mode connectivity is by Nagarajan & Kolter (2019), who train MLPs from the same initialization on disjoint subsets of MNIST and ﬁnd that the resulting networks are connected by linear paths of constant test error; we explore linear mode connectivity from points…”
On Measuring Excess Capacity in Neural Networks (2022, background): “While the resultant generalization bounds are typically vacuous and can exhibit concerning behavior [36], the capacity bounds themselves offer invaluable insights through the behavior of the bound-driving quantities, such as various types of weight norms or Lipschitz constants.”
Classification vs regression in overparameterized regimes: Does the loss function matter? (2020, result): “[31] Vaishnavh Nagarajan and J Zico Kolter.”
SGD on Neural Networks Learns Functions of Increasing Complexity (2019, methodology): “(11)A similar setting is analyzed in the concurrent work of Nagarajan and Kolter [29] to show the limitations of uniform convergence bounds for explaining generalization of deep learning.”
Stabilizing the Lottery Ticket Hypothesis (2019, background): “As a follow-up, one might explore whether subnetworks that are more stable to pruning are also more likely to reach the same basin of attraction as the original network (Nagarajan and Kolter, 2019).”
Implicit Self-Regularization in Deep Neural Networks: Evidence from Random Matrix Theory and Implications for Learning (2018, background): “There are connections here with questions of the appropriateness of uniform convergence style analysis (Nagarajan and Kolter, 2019).”
The Pitfalls of Simplicity Bias in Neural Networks (2020, background): “[46] Vaishnavh Nagarajan and J Zico Kolter.”