Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
arXiv:2006.08157
Abstract
Recently there are a considerable amount of work devoted to the study of the algorithmic stability and generalization for stochastic gradient descent (SGD). However, the existing stability analysis requires to impose restrictive assumptions on the boundedness of gradients, strong smoothness and convexity of loss functions. In this paper, we provide a fine-grained analysis of stability and generalization for SGD by substantially relaxing these assumptions. Firstly, we establish stability and generalization for SGD by removing the existing bounded gradient assumptions. The key idea is the introduction of a new stability measure called on-average model stability, for which we develop novel bounds controlled by the risks of SGD iterates. This yields generalization bounds depending on the behavior of the best model, and leads to the first-ever-known fast bounds in the low-noise setting using stability approach. Secondly, the smoothness assumption is relaxed by considering loss functions with Holder continuous (sub)gradients for which we show that optimal bounds are still achieved by balancing computation and stability. To our best knowledge, this gives the first-ever-known stability and generalization bounds for SGD with even non-differentiable loss functions. Finally, we study learning problems with (strongly) convex objectives but non-convex loss functions.
to appear in ICML 2020
References in corpus (15)
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Data-Dependent Stability of Stochastic Gradient Descent
- On exponential convergence of SGD in non-convex over-parametrized learning
- Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
- Algorithmic stability and hypothesis complexity
- Optimal Rates for Multi-pass Stochastic Gradient Methods
- High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
- Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
- On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
- Sharper bounds for uniformly stable algorithms
- Privacy-preserving Prediction
- Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
- Hypothesis Set Stability and Generalization
- Optimistic bounds for multi-output prediction