Unified Optimal Analysis of the (Stochastic) Gradient Method

By Sebastian U. Stich. 2019

138 citations recorded by the source corpus.

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( LR^2 \exp \bigl[-\frac{\mu}{4L}T\bigr] + \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.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Mathematical Physics

Citations in the corpus

Personalized Federated Learning with Moreau Envelopes (2020, methodology): “(44) Defining ∆F := F (w) − F ∗, and following the techniques used by [3, 54, 55], we consider two cases:”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, methodology): “…(McMahan et al., 2016; 2017) and has recently attracted the attention of the theoretical community in the seek of the best convergence rates (Stich, 2019b; Wang & Joshi, 2018; Yu et al., 2019; Basu et al., 2019; Patel & Dieuleveut, 2019; Stich & Karimireddy, 2019; Li et al., 2019; Khaled…”
Is Local SGD Better than Minibatch SGD? (2020, background): “…case (where λ > 0), the gap between local GD and minibatch SGD can be even more dramatic: In that case, the optimization term of minibatch SGD scales as exp( − R ) (see Stich (2019) and references therein), while our theorem implies that local SGD cannot obtain a term better than ( KR ) − 2 .”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, unknown): “Also note the following result from Stich [21], which is useful for optimizing the step-sizes.”
Better Theory for SGD in the Nonconvex World (2020, methodology): “This idea of weighting different iterates has been used in the analysis of SGD in the convex case (Rakhlin et al., 2012; Shamir & Zhang, 2013; Stich, 2019) typically with the goal of returning a weighted average of the iterates x̄K at the end.”
Random Reshuffling: Simple Analysis with Vast Improvements (2020, background): “Besides this, we do not expect any direct or short term societal consequences.”
SCAFFOLD: Stochastic Controlled Averaging for Federated Learning (2019, background): “The ﬁrst one is a slightly improved (and simpliﬁed) version of (Stich, 2019, Theorem 2).”
The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication (2019, methodology): “The next two technical lemmas we borrow from (Stich, 2019a).”
Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization (2020, background): “As a result, there has been a recent surge in trying to avoid these assumptions on the stochastic gradients for several classes of smooth functions: strongly convex [14, 25, 31], convex [14, 25, 40, 42], or even nonconvex functions [20, 24, 25].”