Explaining generalization in deep learning: progress and fundamental limits

Vaishnavh NagarajanarXiv 2021 · OpenReview

TL;DR

This dissertation tackles the "generalization puzzle" in deep learning: why do overparameterized networks generalize well despite fitting training data perfectly? It first explores data-dependent uniform convergence bounds, then demonstrates their fundamental limitations, and finally proposes a novel empirical technique using unlabeled data to predict generalization, bypassing traditional complexity measures.

What Problem Does This Paper Address?

Deep learning models, particularly neural networks, often achieve remarkable performance by fitting training data to zero error, even when heavily overparameterized. This phenomenon, known as the "generalization puzzle," contradicts classical learning theory, which suggests such models should overfit and generalize poorly. The paper aims to understand why deep networks generalize well and to develop better theoretical tools for explaining and predicting this behavior. Existing approaches, primarily based on uniform convergence, struggle to provide tight and insightful bounds, especially for overparameterized models.

Methods

The dissertation takes a multi-pronged approach:

  1. Empirical Study of Implicit Bias: Investigating how stochastic gradient descent (SGD) implicitly controls network capacity, focusing on "distance from initialization" as a key factor.
  2. Data-Dependent Uniform Convergence Bounds: Developing theoretical bounds that incorporate information about the training data and algorithm, aiming for tighter guarantees than traditional methods.
  3. Demonstrating Limits of Uniform Convergence: Presenting theoretical examples where uniform convergence bounds provably fail to explain generalization, even for simple models, highlighting a fundamental limitation.
  4. Empirical Generalization Prediction with Unlabeled Data: Proposing a novel technique that uses unlabeled data to predict generalization, bypassing traditional complexity measures and uniform convergence. This method is shown to be remarkably precise.
  5. Theoretical Justification for the Empirical Technique: Providing theoretical explanations for why the proposed empirical method works so well.

Datasets

The paper mentions the use of standard datasets for experiments, including:

  • MNIST
  • CIFAR-10
  • CIFAR-100
  • SVHN
  • PACS (for distribution shift experiments)

No new benchmarks are introduced.

Key Insights and Ideas

  • Distance from Initialization Matters: The dissertation argues that "distance from initialization" is a crucial implicit bias of SGD that influences generalization, offering a more insightful measure than just weight norms.
  • Uniform Convergence Has Fundamental Limits: The paper demonstrates that uniform convergence, a cornerstone of learning theory, fundamentally fails to explain generalization in certain overparameterized settings, even when accounting for implicit bias. This suggests a need to move beyond this paradigm.
  • Disagreement as a Predictor of Generalization: A surprising and powerful finding is that the disagreement rate between two models trained on the same data (but with different stochasticity) strongly correlates with, and can even serve as a direct estimate of, the test error. This holds even for unlabeled data.
  • Calibration Implies Generalization-Disagreement Equality (GDE): The work establishes a formal link between model calibration (how well predicted probabilities match true likelihoods) and the Generalization-Disagreement Equality, suggesting that well-calibrated ensembles are key to this phenomenon.
  • Moving Beyond Complexity: The proposed empirical technique for predicting generalization bypasses traditional complexity measures, offering a more practical and precise approach.

Key Results

  • Data-Dependent Bounds: Developed generalization bounds for deep networks that are data-dependent, incorporate distance from initialization, and avoid exponential depth dependence on spectral norms.
  • Provable Failure of Uniform Convergence: Demonstrated theoretically that uniform convergence bounds are vacuous in certain overparameterized settings, even with implicit bias.
  • Empirical Generalization Prediction: Proposed an empirical technique using unlabeled data and model disagreement that accurately predicts generalization, showing strong correlation with test error across various models and datasets.
  • Calibration-GDE Link: Formally proved that class-aggregated calibration implies the Generalization-Disagreement Equality.

Limitations and Future Work

  • Limitations of Uniform Convergence: The dissertation highlights that uniform convergence, while widely used, has fundamental limitations in explaining generalization for overparameterized models.
  • Assumptions in Bounds: Some theoretical bounds rely on assumptions (e.g., about pre-activation values) that might not hold in all practical scenarios.
  • Future Work:
    • Exploring novel ways to incorporate distributional assumptions (e.g., unlabeled data) into generalization bounds.
  • Developing new theoretical tools beyond uniform convergence.
  • Investigating the source of noise-resilience in deep ReLU networks for tighter guarantees.
  • Understanding why different sources of stochasticity have similar effects on calibration.
  • Developing more precise characterizations of when calibration and GDE hold.
  • Further refining the CACE metric for a tighter bound on the gap between test error and disagreement.
  • Exploring the implications of the "deep learning conjecture" regarding simple macroscopic behavior with microscopic fluctuations.

Summary updated

Abstract

This dissertation studies a fundamental open challenge in deep learning theory: why do deep networks generalize well even while being overparameterized, unregularized and fitting the training data to zero error? In the first part of the thesis, we will empirically study how training deep networks via stochastic gradient descent implicitly controls the networks' capacity. Subsequently, to show how this leads to better generalization, we will derive {\em data-dependent} {\em uniform-convergence-based} generalization bounds with improved dependencies on the parameter count. Uniform convergence has in fact been the most widely used tool in deep learning literature, thanks to its simplicity and generality. Given its popularity, in this thesis, we will also take a step back to identify the fundamental limits of uniform convergence as a tool to explain generalization. In particular, we will show that in some example overparameterized settings, {\em any} uniform convergence bound will provide only a vacuous generalization bound. With this realization in mind, in the last part of the thesis, we will change course and introduce an {\em empirical} technique to estimate generalization using unlabeled data. Our technique does not rely on any notion of uniform-convergece-based complexity and is remarkably precise. We will theoretically show why our technique enjoys such precision. We will conclude by discussing how future work could explore novel ways to incorporate distributional assumptions in generalization bounds (such as in the form of unlabeled data) and explore other tools to derive bounds, perhaps by modifying uniform convergence or by developing completely new tools altogether.
BibTeX
@misc{nagarajan2021explaining,
  author = {Vaishnavh Nagarajan},
  title = {{Explaining generalization in deep learning: progress and fundamental limits}},
  year = {2021},
  eprint = {2110.08922},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2110.08922},
}
Figure