Explaining generalization in deep learning: progress and fundamental limits

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.

arXiv commentarXiv admin note: text overlap with arXiv:1902.04742

References in corpus (28)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Deep Ensembles: A Loss Landscape Perspective
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning
• On the Spectral Bias of Neural Networks
• Predicting the Generalization Gap in Deep Networks with Margin Distributions
• Evaluating model calibration in classification
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• Generalization in Deep Networks: The Role of Distance from Initialization
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
• Adversarial Spheres
• The implicit fairness criterion of unconstrained learning
• Generalization Bounds for Uniformly Stable Algorithms
• NeurIPS 2020 Competition: Predicting Generalization in Deep Learning
• Assessing Generalization of SGD via Disagreement
• Don't Just Blame Over-parametrization for Over-confidence: Theoretical Analysis of Calibration in Binary Classification
• Representation Based Complexity Measures for Predicting Generalization in Deep Learning
• Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
• Distributional Generalization: A New Kind of Generalization
• Moment Multicalibration for Uncertainty Estimation
• Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixtures
• Early-stopped neural networks are consistent
• Should Ensemble Members Be Calibrated?
• RATT: Leveraging Unlabeled Data to Guarantee Generalization