Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
arXiv:1703.11008
Abstract
One of the defining properties of deep learning is that models are chosen to have many more parameters than available training data. In light of this capacity for overfitting, it is remarkable that simple algorithms like SGD reliably return solutions with low test error. One roadblock to explaining these phenomena in terms of implicit regularization, structural properties of the solution, and/or easiness of the data is that many learning bounds are quantitatively vacuous when applied to networks learned by SGD in this "deep learning" regime. Logically, in order to explain generalization, we need nonvacuous bounds. We return to an idea by Langford and Caruana (2001), who used PAC-Bayes bounds to compute nonvacuous numerical bounds on generalization error for stochastic two-layer two-hidden-unit neural networks via a sensitivity analysis. By optimizing the PAC-Bayes bound directly, we are able to extend their approach and obtain nonvacuous generalization bounds for deep stochastic neural network classifiers with millions of parameters trained on only tens of thousands of examples. We connect our findings to recent and old work on flat minima and MDL-based explanations of generalization.
arXiv comment14 pages, 1 table, 2 figures. Corresponds with UAI camera ready and supplement. Includes additional references and related experiments
References in corpus (6)
- Train faster, generalize better: Stability of stochastic gradient descent
- Path-SGD: Path-Normalized Optimization in Deep Neural Networks
- Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
- Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
- Norm-Based Capacity Control in Neural Networks
- On Graduated Optimization for Stochastic Non-Convex Problems
Cited by in corpus (146)
- Bayesian Deep Convolutional Encoder-Decoder Networks for Surrogate Modeling and Uncertainty Quantification
- Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
- Deep Learning Scaling is Predictable, Empirically
- A deep-learning-based surrogate model for data assimilation in dynamic subsurface flow problems
- Certifying Some Distributional Robustness with Principled Adversarial Training
- Exploring Generalization in Deep Learning
- Neural Lander: Stable Drone Landing Control using Learned Dynamics
- Sensitivity and Generalization in Neural Networks: an Empirical Study
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
- On the importance of single directions for generalization
- Adversarial Weight Perturbation Helps Robust Generalization
- Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
- Bayesian Deep Learning and a Probabilistic Perspective of Generalization
- Fantastic Generalization Measures and Where to Find Them
- Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
- Neural Quantum States of frustrated magnets: generalization and sign structure
- A Theoretical Analysis of Deep Q-Learning
- Scalable agent alignment via reward modeling: a research direction
- Sharpness-Aware Minimization for Efficiently Improving Generalization
- The no-free-lunch theorems of supervised learning
- Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
- The Pitfalls of Simplicity Bias in Neural Networks
- Stronger generalization bounds for deep nets via a compression approach
- Implicit Regularization in Deep Learning
- Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
- An analytic theory of generalization dynamics and transfer learning in deep linear networks
- Identity Crisis: Memorization and Generalization under Extreme Overparameterization
- Classification vs regression in overparameterized regimes: Does the loss function matter?
- High Frequency Component Helps Explain the Generalization of Convolutional Neural Networks
- Reliability and Interpretability in Science and Deep Learning
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
- Invariant Causal Prediction for Block MDPs
- Identifying Generalization Properties in Neural Networks
- Tighter risk certificates for neural networks
- The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent
- Uncertainty Quantification and Deep Ensembles
- Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
- Analysis of Generalizability of Deep Neural Networks Based on the Complexity of Decision Boundary
- The Implicit and Explicit Regularization Effects of Dropout
- Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
- Efficient Sharpness-aware Minimization for Improved Training of Neural Networks
- A Diffusion Theory For Deep Learning Dynamics: Stochastic Gradient Descent Exponentially Favors Flat Minima
- NeurIPS 2020 Competition: Predicting Generalization in Deep Learning
- A Scale Invariant Flatness Measure for Deep Network Minima
- Assessing Generalization of SGD via Disagreement
- On the role of data in PAC-Bayes bounds
- Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
- Observational Overfitting in Reinforcement Learning
- On the Benefits of Invariance in Neural Networks
- The Deep Bootstrap Framework: Good Online Learners are Good Offline Generalizers
- Representation Based Complexity Measures for Predicting Generalization in Deep Learning
- Learning under Model Misspecification: Applications to Variational and Ensemble methods
- PAC-Bayes with Backprop
- Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
- Generalization bounds via distillation
- Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks
- The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks
- A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
- Benign Overfitting in Multiclass Classification: All Roads Lead to Interpolation
- Distributional Generalization: A New Kind of Generalization
- Minnorm training: an algorithm for training over-parameterized deep neural networks
- DNN or k-NN: That is the Generalize vs. Memorize Question
- Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks
- Generalization Bounds for Neural Belief Propagation Decoders
- Understanding Generalization in Deep Learning via Tensor Methods
- The Training Process of Many Deep Networks Explores the Same Low-Dimensional Manifold
- Scalable Marginal Likelihood Estimation for Model Selection in Deep Learning
- Generalization Guarantees for Imitation Learning
- Incorporating Unlabeled Data into Distributionally Robust Learning
- How noise affects the Hessian spectrum in overparameterized neural networks
- Wide flat minima and optimal generalization in classifying high-dimensional Gaussian mixtures
- A Bayesian Perspective on Training Speed and Model Selection
- A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
- Robustness to Pruning Predicts Generalization in Deep Neural Networks
- SALR: Sharpness-aware Learning Rate Scheduler for Improved Generalization
- Stationary Points of Shallow Neural Networks with Quadratic Activation Function
- Gradient-Free Learning Based on the Kernel and the Range Space
- Sharpness-aware Quantization for Deep Neural Networks
- Towards Theoretical Understanding of Large Batch Training in Stochastic Gradient Descent
- The Bayesian Learning Rule
- Analytic Network Learning
- Implicit Rugosity Regularization via Data Augmentation
- For self-supervised learning, Rationality implies generalization, provably
- Robustness to Augmentations as a Generalization metric
- Deep ReLU Networks Preserve Expected Length
- Improving Generalization by Controlling Label-Noise Information in Neural Network Weights
- PAC-Bayes, MAC-Bayes and Conditional Mutual Information: Fast rate bounds that handle general VC classes
- On improving deep learning generalization with adaptive sparse connectivity
- A Theoretical Analysis of Fine-tuning with Linear Teachers
- Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent
- Data-Dependent Coresets for Compressing Neural Networks with Applications to Generalization Bounds
- Generalization Guarantees for Neural Architecture Search with Train-Validation Split
- Neural Complexity Measures
- PAC-Bayes Analysis Beyond the Usual Bounds
- Capacity Control of ReLU Neural Networks by Basis-path Norm
- Still no free lunches: the price to pay for tighter PAC-Bayes bounds
- PAC-Bayesian Contrastive Unsupervised Representation Learning
- PAC-Bayes Bounds for Meta-learning with Data-Dependent Prior
- Sample Complexity Bounds for Recurrent Neural Networks with Application to Combinatorial Graph Problems
- PAC-Bayes Generalisation Bounds for Dynamical Systems Including Stable RNNs
- A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks
- Fast Convergence for Langevin Diffusion with Manifold Structure
- Dichotomize and Generalize: PAC-Bayesian Binary Activated Deep Neural Networks
- Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
- Information-Theoretic Local Minima Characterization and Regularization
- A Deep Conditioning Treatment of Neural Networks
- CAP: Co-Adversarial Perturbation on Weights and Features for Improving Generalization of Graph Neural Networks
- Improved generalization by noise enhancement
- Noise and Fluctuation of Finite Learning Rate Stochastic Gradient Descent
- Hyperplane Arrangements of Trained ConvNets Are Biased
- Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
- Learning Partially Known Stochastic Dynamics with Empirical PAC Bayes
- An Optimization and Generalization Analysis for Max-Pooling Networks
- Probably Approximately Correct Vision-Based Planning using Motion Primitives
- On Predicting Generalization using GANs
- RATT: Leveraging Unlabeled Data to Guarantee Generalization
- Extreme Memorization via Scale of Initialization
- PAC-Bayesian Generalization Bounds for MultiLayer Perceptrons
- A Free-Energy Principle for Representation Learning
- PAC-Bayes Analysis of Sentence Representation
- Semantically Robust Unpaired Image Translation for Data with Unmatched Semantics Statistics
- The role of invariance in spectral complexity-based generalization bounds
- Nonlinear Collaborative Scheme for Deep Neural Networks
- Dissecting Non-Vacuous Generalization Bounds based on the Mean-Field Approximation
- Unifying Variational Inference and PAC-Bayes for Supervised Learning that Scales
- Loss Landscape Dependent Self-Adjusting Learning Rates in Decentralized Stochastic Gradient Descent
- Margin Maximization as Lossless Maximal Compression
- Chaining Meets Chain Rule: Multilevel Entropic Regularization and Training of Neural Nets
- Generalisation in fully-connected neural networks for time series forecasting
- Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD
- Relative Flatness and Generalization
- Inherent Noise in Gradient Based Methods
- Uniform Generalization Bounds for Overparameterized Neural Networks
- Deep Learning Theory through the Lens of Statistical Physics: A Topical Review
- VC dimension of partially quantized neural networks in the overparametrized regime
- Towards Understanding Generalization via Decomposing Excess Risk Dynamics
- Risk Bounds for Learning via Hilbert Coresets
- MSR-DARTS: Minimum Stable Rank of Differentiable Architecture Search
- Maximum Multiscale Entropy and Neural Network Regularization
- Think Global, Act Local: Relating DNN generalisation and node-level SNR
- Characterizing Inter-Layer Functional Mappings of Deep Learning Models
- Notes on Deep Learning Theory
- Using Human Psychophysics to Evaluate Generalization in Scene Text Recognition Models
- Learning Provably Robust Motion Planners Using Funnel Libraries
- A Revision of Neural Tangent Kernel-based Approaches for Neural Networks
- On the generalization of bayesian deep nets for multi-class classification