Train faster, generalize better: Stability of stochastic gradient descent

Abstract

We show that parametric models trained by a stochastic gradient method (SGM) with few iterations have vanishing generalization error. We prove our results by arguing that SGM is algorithmically stable in the sense of Bousquet and Elisseeff. Our analysis only employs elementary tools from convex and continuous optimization. We derive stability bounds for both convex and non-convex optimization under standard Lipschitz and smoothness assumptions. Applying our results to the convex case, we provide new insights for why multiple epochs of stochastic gradient methods generalize well in practice. In the non-convex case, we give a new interpretation of common practices in neural networks, and formally show that popular techniques for training large deep models are indeed stability-promoting. Our findings conceptually underscore the importance of reducing training time beyond its obvious benefit.

References in corpus (5)

• Recurrent Neural Network Regularization
• Non-stochastic Best Arm Identification and Hyperparameter Optimization
• In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• On the Generalization Properties of Differential Privacy

Cited by in corpus (104)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
• Regularizing and Optimizing LSTM Language Models
• A Closer Look at Memorization in Deep Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• A Study on Overfitting in Deep Reinforcement Learning
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Generalization in Deep Learning
• Veridical Data Science
• No bad local minima: Data independent training error guarantees for multilayer neural networks
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• The Modern Mathematics of Deep Learning
• Swapout: Learning an ensemble of deep architectures
• AdaNet: Adaptive Structural Learning of Artificial Neural Networks
• Eigenvalues of the Hessian in Deep Learning: Singularity and Beyond
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• Private Stochastic Convex Optimization with Optimal Rates
• On the Expressive Power of Deep Neural Networks
• A Progressive Batching L-BFGS Method for Machine Learning
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Theory of Deep Learning III: explaining the non-overfitting puzzle
• Algorithmic stability and hypothesis complexity
• Training behavior of deep neural network in frequency domain
• Where is the Information in a Deep Neural Network?
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• On the cross-validation bias due to unsupervised pre-processing
• Understanding training and generalization in deep learning by Fourier analysis
• Proving Expected Sensitivity of Probabilistic Programs
• Path integral contour deformations for observables in $SU(N)$ gauge theory
• Oversampling Higher-Performing Minorities During Machine Learning Model Training Reduces Adverse Impact Slightly but Also Reduces Model Accuracy
• Classification regions of deep neural networks
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin
• Machine Learning with Membership Privacy using Adversarial Regularization
• Hybrid Differentially Private Federated Learning on Vertically Partitioned Data
• Near-optimal control of dynamical systems with neural ordinary differential equations
• Understanding Deep Learning via Decision Boundary
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Statistical Inference for the Population Landscape via Moment Adjusted Stochastic Gradients
• Measuring and regularizing networks in function space
• Lipschitzness Is All You Need To Tame Off-policy Generative Adversarial Imitation Learning
• Efficient Private ERM for Smooth Objectives
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Towards Understanding Theoretical Advantages of Complex-Reaction Networks
• Ensemble Robustness and Generalization of Stochastic Deep Learning Algorithms
• From Dependence to Causation
• Stability and Generalization of Graph Convolutional Neural Networks
• Learning subtree pattern importance for Weisfeiler-Lehmanbased graph kernels
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping
• Improving Regression Performance with Distributional Losses
• Visualizing high-dimensional loss landscapes with Hessian directions
• Positively Scale-Invariant Flatness of ReLU Neural Networks
• Information Bottleneck and its Applications in Deep Learning
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• Deep Q-Networks for Accelerating the Training of Deep Neural Networks
• Stochastic Gradient Descent: Going As Fast As Possible But Not Faster
• A Bayesian Perspective on Training Speed and Model Selection
• Universal Stagewise Learning for Non-Convex Problems with Convergence on Averaged Solutions
• Deep Learning with CNNs: A Compact Holistic Tutorial with Focus on Supervised Regression (Preprint)
• ByGARS: Byzantine SGD with Arbitrary Number of Attackers
• Information Losses in Neural Classifiers from Sampling
• Stochastic Gradient Descent with Polyak's Learning Rate
• Implicit Rugosity Regularization via Data Augmentation
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• Mini-batch stochastic subgradient for functional constrained optimization
• Generalization Bounds for Stochastic Saddle Point Problems
• Faster Convergence in Deep-Predictive-Coding Networks to Learn Deeper Representations
• The Impact of Local Geometry and Batch Size on Stochastic Gradient Descent for Nonconvex Problems
• Representational Power of ReLU Networks and Polynomial Kernels: Beyond Worst-Case Analysis
• Model-Agnostic Private Learning via Stability
• Efficient Dictionary Learning with Gradient Descent
• On generalization bounds for deep networks based on loss surface implicit regularization
• On architectural choices in deep learning: From network structure to gradient convergence and parameter estimation
• Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent
• Deep Online Convex Optimization with Gated Games
• Challenges in Bayesian Adaptive Data Analysis
• Importance Resampling for Off-policy Prediction
• Stochastic Optimization with Laggard Data Pipelines
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• Deep Online Convex Optimization by Putting Forecaster to Sleep
• Efficient Gradient Approximation Method for Constrained Bilevel Optimization
• Robust Blind Deconvolution via Mirror Descent
• Estimating informativeness of samples with Smooth Unique Information
• Semantics, Representations and Grammars for Deep Learning
• Understanding Deep Architectures with Reasoning Layer
• Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
• Pre-interpolation loss behaviour in neural networks
• Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning
• SaaS: Speed as a Supervisor for Semi-supervised Learning
• Stability and Generalization of Hypergraph Collaborative Networks
• Communication-Efficient Distributed Learning via Sparse and Adaptive Stochastic Gradient
• Stabilized Sparse Online Learning for Sparse Data
• Generalisation under gradient descent via deterministic PAC-Bayes
• High-Dimensional Private Empirical Risk Minimization by Greedy Coordinate Descent
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives
• Distributed SGD Generalizes Well Under Asynchrony
• Distributed stochastic optimization for deep learning (thesis)
• Stability of the Stochastic Gradient Method for an Approximated Large Scale Kernel Machine
• Minimax Excess Risk of First-Order Methods for Statistical Learning with Data-Dependent Oracles
• A Generalization Theory based on Independent and Task-Identically Distributed Assumption
• Generalization Error Bounds for Optimization Algorithms via Stability
• On the generalization of bayesian deep nets for multi-class classification