Improved Learning Rates for Stochastic Optimization

Abstract

Stochastic optimization is a cornerstone of modern machine learning. This paper studies the generalization performance of two classical stochastic optimization algorithms: stochastic gradient descent (SGD) and Nesterov's accelerated gradient (NAG). We establish new learning rates for both algorithms, with improved guarantees in some settings or comparable rates under weaker assumptions in others. We also provide numerical experiments to support the theory.

This version substantially revises and supersedes all previous versions. Earlier versions contained errors and should not be relied upon for the current results or statements. The manuscript has been thoroughly rewritten, with a narrowed scope, a simplified presentation, a revised focus, and corresponding updates to the title and main claims. Please refer to and cite the current version

References in corpus (34)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Asynchronous Parallel Stochastic Gradient for Nonconvex Optimization
• Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)
• Gradient Descent Learns Linear Dynamical Systems
• Online Learning: A Modern Introduction Using Convex Optimization
• Private Stochastic Convex Optimization with Optimal Rates
• Data-Dependent Stability of Stochastic Gradient Descent
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Algorithmic stability and hypothesis complexity
• Gradient methods for convex minimization: better rates under weaker conditions
• Optimal Rates for Multi-pass Stochastic Gradient Methods
• Generalization Properties and Implicit Regularization for Multiple Passes SGM
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Optimistic Rates for Learning with a Smooth Loss
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions
• Generalization Bounds for Uniformly Stable Algorithms
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• SGD Converges to Global Minimum in Deep Learning via Star-convex Path
• Average Stability is Invariant to Data Preconditioning. Implications to Exp-concave Empirical Risk Minimization
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods
• Hypothesis Set Stability and Generalization
• Distribution-Free Robust Linear Regression
• SGD Generalizes Better Than GD (And Regularization Doesn't Help)
• Stability and Generalization of Stochastic Gradient Methods for Minimax Problems
• Differentially Private SGD with Non-Smooth Losses
• Approximate Newton Methods
• Beating SGD Saturation with Tail-Averaging and Minibatching
• Stability of SGD: Tightness Analysis and Improved Bounds
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory