Unified Optimal Analysis of the (Stochastic) Gradient Method

Abstract

In this note we give a simple proof for the convergence of stochastic gradient (SGD) methods on $\mu$-convex functions under a (milder than standard) $L$-smoothness assumption. We show that for carefully chosen stepsizes SGD converges after $T$ iterations as $O\left(L{R}^2\exp [-\frac{\mu }{4L}T]+\frac{{\sigma }^2}{\mu T}\right)$ where ${\sigma }^2$ measures the variance in the stochastic noise. For deterministic gradient descent (GD) and SGD in the interpolation setting we have ${\sigma }^2=0$ and we recover the exponential convergence rate. The bound matches with the best known iteration complexity of GD and SGD, up to constants.

11 pages, version 2 fixes typos and case distinction in the proof

References in corpus (4)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Sparsified SGD with Memory
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• SGD and Hogwild! Convergence Without the Bounded Gradients Assumption

Cited by in corpus (37)

• SCAFFOLD: Stochastic Controlled Averaging for Federated Learning
• Personalized Federated Learning with Moreau Envelopes
• A Unified Theory of Decentralized SGD with Changing Topology and Local Updates
• The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication
• Better Theory for SGD in the Nonconvex World
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Is Local SGD Better than Minibatch SGD?
• Linearly Converging Error Compensated SGD
• Random Reshuffling: Simple Analysis with Vast Improvements
• Consensus Control for Decentralized Deep Learning
• Federated Accelerated Stochastic Gradient Descent
• Local Adaptivity in Federated Learning: Convergence and Consistency
• A Better Alternative to Error Feedback for Communication-Efficient Distributed Learning
• Adaptive Gradient Descent without Descent
• On the Convergence of SGD with Biased Gradients
• Zeroth-Order Algorithms for Smooth Saddle-Point Problems
• Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGD
• On Communication Compression for Distributed Optimization on Heterogeneous Data
• Local SGD: Unified Theory and New Efficient Methods
• A general sample complexity analysis of vanilla policy gradient
• RelaySum for Decentralized Deep Learning on Heterogeneous Data
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent
• A Unified Analysis of Variational Inequality Methods: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Proximal and Federated Random Reshuffling
• Synthetic data shuffling accelerates the convergence of federated learning under data heterogeneity
• Distributed Deep Learning in Open Collaborations
• Gradient-free algorithm for saddle point problems under overparametrization
• Delayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
• Stochastic Extragradient: General Analysis and Improved Rates
• About some works of Boris Polyak on convergence of gradient methods and their development
• The Minimax Complexity of Distributed Optimization
• Private Federated Learning Without a Trusted Server: Optimal Algorithms for Convex Losses
• An Even More Optimal Stochastic Optimization Algorithm: Minibatching and Interpolation Learning
• ${\text{A}}^2{\text{CiD}}^2$: Accelerating Asynchronous Communication in Decentralized Deep Learning
• Det-CGD: Compressed Gradient Descent with Matrix Stepsizes for Non-Convex Optimization
• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning
• Stochastic Polyak Stepsize with a Moving Target