Data-Dependent Stability of Stochastic Gradient Descent

Abstract

We establish a data-dependent notion of algorithmic stability for Stochastic Gradient Descent (SGD), and employ it to develop novel generalization bounds. This is in contrast to previous distribution-free algorithmic stability results for SGD which depend on the worst-case constants. By virtue of the data-dependent argument, our bounds provide new insights into learning with SGD on convex and non-convex problems. In the convex case, we show that the bound on the generalization error depends on the risk at the initialization point. In the non-convex case, we prove that the expected curvature of the objective function around the initialization point has crucial influence on the generalization error. In both cases, our results suggest a simple data-driven strategy to stabilize SGD by pre-screening its initialization. As a corollary, our results allow us to show optimistic generalization bounds that exhibit fast convergence rates for SGD subject to a vanishing empirical risk and low noise of stochastic gradient.

Cited by in corpus (33)

• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• SGD on Neural Networks Learns Functions of Increasing Complexity
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Understanding Generalization through Visualizations
• Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Toward Better Generalization Bounds with Locally Elastic Stability
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Generalization bounds for deep learning
• The Local Elasticity of Neural Networks
• Orthogonal Deep Neural Networks
• Instability, Computational Efficiency and Statistical Accuracy
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• PAC-Bayesian Margin Bounds for Convolutional Neural Networks
• Weak and Strong Gradient Directions: Explaining Memorization, Generalization, and Hardness of Examples at Scale
• Improved Learning Rates for Stochastic Optimization
• Learning with Gradient Descent and Weakly Convex Losses
• Stability of SGD: Tightness Analysis and Improved Bounds
• Robustness, Privacy, and Generalization of Adversarial Training
• Time-Delay Momentum: A Regularization Perspective on the Convergence and Generalization of Stochastic Momentum for Deep Learning
• What training reveals about neural network complexity
• An Empirical Study on the Intrinsic Privacy of SGD
• Towards Statistical and Computational Complexities of Polyak Step Size Gradient Descent
• Making Coherence Out of Nothing At All: Measuring the Evolution of Gradient Alignment
• Distributed SGD Generalizes Well Under Asynchrony
• Stability and Generalization for Randomized Coordinate Descent
• Leave-one-out Unfairness
• Why Does Multi-Epoch Training Help?
• Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint
• Optimizing Information-theoretical Generalization Bounds via Anisotropic Noise in SGLD