SGD: General Analysis and Improved Rates

Abstract

We propose a general yet simple theorem describing the convergence of SGD under the arbitrary sampling paradigm. Our theorem describes the convergence of an infinite array of variants of SGD, each of which is associated with a specific probability law governing the data selection rule used to form mini-batches. This is the first time such an analysis is performed, and most of our variants of SGD were never explicitly considered in the literature before. Our analysis relies on the recently introduced notion of expected smoothness and does not rely on a uniform bound on the variance of the stochastic gradients. By specializing our theorem to different mini-batching strategies, such as sampling with replacement and independent sampling, we derive exact expressions for the stepsize as a function of the mini-batch size. With this we can also determine the mini-batch size that optimizes the total complexity, and show explicitly that as the variance of the stochastic gradient evaluated at the minimum grows, so does the optimal mini-batch size. For zero variance, the optimal mini-batch size is one. Moreover, we prove insightful stepsize-switching rules which describe when one should switch from a constant to a decreasing stepsize regime.

arXiv comment23 pages, 6 figures

References in corpus (13)

• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning
• Fast Convergence of Stochastic Gradient Descent under a Strong Growth Condition
• Fast and Simple PCA via Convex Optimization
• SDCA without Duality, Regularization, and Individual Convexity
• Nonconvex Variance Reduced Optimization with Arbitrary Sampling
• Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron
• Optimal mini-batch and step sizes for SAGA
• Primal Method for ERM with Flexible Mini-batching Schemes and Non-convex Losses
• On the linear convergence of the stochastic gradient method with constant step-size

Cited by in corpus (20)

• An Exponential Learning Rate Schedule for Deep Learning
• Analysis of Stochastic Gradient Descent in Continuous Time
• The Practicality of Stochastic Optimization in Imaging Inverse Problems
• Multiplicative noise and heavy tails in stochastic optimization
• A Double Residual Compression Algorithm for Efficient Distributed Learning
• Recent theoretical advances in decentralized distributed convex optimization
• A Selective Review on Statistical Methods for Massive Data Computation: Distributed Computing, Subsampling, and Minibatch Techniques
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent
• Tight Dimension Independent Lower Bound on the Expected Convergence Rate for Diminishing Step Sizes in SGD
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• On stochastic mirror descent with interacting particles: convergence properties and variance reduction
• Distributed Fixed Point Methods with Compressed Iterates
• Error Lower Bounds of Constant Step-size Stochastic Gradient Descent
• A Study of Condition Numbers for First-Order Optimization
• SGD with Coordinate Sampling: Theory and Practice
• AdaSub: Stochastic Optimization Using Second-Order Information in Low-Dimensional Subspaces
• Characterization of Convex Objective Functions and Optimal Expected Convergence Rates for SGD
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity
• AutoDrop: Training Deep Learning Models with Automatic Learning Rate Drop
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions