Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization

By Alexander Rakhlin, Ohad Shamir, Karthik Sridharan. 2011

839 citations recorded by the source corpus.

Stochastic gradient descent (SGD) is a simple and popular method to solve stochastic optimization problems which arise in machine learning. For strongly convex problems, its convergence rate was known to be O(log(T)/T), by running SGD for T iterations and returning the average point. However, recent results showed that using a different algorithm, one can get an optimal O(1/T) rate. This might lead one to believe that standard SGD is suboptimal, and maybe should even be replaced as a method of choice. In this paper, we investigate the optimality of SGD in a stochastic setting. We show that for smooth problems, the algorithm attains the optimal O(1/T) rate. However, for non-smooth problems, the convergence rate with averaging might really be Ω(log(T)/T), and this is not just an artifact of the analysis. On the flip side, we show that a simple modification of the averaging step suffices to recover the O(1/T) rate, and no other change of the algorithm is necessary. We also present experimental results which support our findings, and point out open problems.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research, Optimization & Training

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 Management Science and Operations Research

In Optimization & Training

Citations in the corpus

Deeply-Supervised Nets (2014, background): “Based on lemma 1 in [20], this upper bound directly holds.”
On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, methodology): “…is given gradient information, the attainable optimization error / average regret is well-known: under mild conditions, it is Θ(1/ √ T ) for convex functions and Θ(1/T ) for strongly-convex functions, where T is the number of queries Zinkevich (2003); Hazan and Kale (2011); Rakhlin et al. (2012).”
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, neutral): “…(cid:107) 2 ≤ c ) or bounded variance assumptions ( E (cid:107)∇ f i ( x ) − ∇ f ( x ) (cid:107) 2 ≤ c ) [Recht et al., 2011, Hazan and Kale, 2014, Rakhlin et al., 2012] or growth condition ( E (cid:107)∇ f i ( x ) 2 ≤ c 1 (cid:107)∇ f ( x ) 2 + c 2 ) [Bottou et al., 2018, Schmidt et al., 2017].…”
Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence (2020, background): “Besides smoothness and convexity, several papers (Shamir and Zhang, 2013; Recht et al., 2011; Hazan and Kale, 2014; Rakhlin et al., 2012) assume that the variance of the stochastic gradient is bounded; that is there exists a c such that Ei‖∇fi(x)‖(2) ≤ c.”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “(15) This is what Rakhlin et al. (2012) calls (1 − µ)-suffix averaging and it appeared in the context of getting a stochastic subgradient method with O(1/k) convergence rate for strongly convex functions instead of the standard O((log k)/k) rate that one can prove for the individual iterates x(k).”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “In Section 5, we show that models trained for multiple epochs match classic bounds for stochastic gradient [28,29].”
Minimizing finite sums with the stochastic average gradient (2013, background): “Several authors have recently shown that suitable iterate averaging schemes obtain an O(1/k) rate for strongly-convex optimization even for non-smooth objectives [21,48].”
On the Outsized Importance of Learning Rates in Local Update Methods (2020, methodology): “Using techniques similar to those in (Rakhlin et al., 2012), we arrive at the following descent lemma.”
A Unified Theory of Decentralized SGD with Changing Topology and Local Updates (2020, background): “It is important to note that in analyses based on the bounded gradient assumption—which was traditionally assumend for analyzing SGD (Lacoste-Julien et al., 2012; Rakhlin et al., 2012)—the diversity in the data distribution on each worker sometimes can be hidden in this generous upper bound and the ”
The Non-IID Data Quagmire of Decentralized Machine Learning (2019, methodology): “These works reduce communication overhead by proposing algorithm-speciﬁc approaches, such as solving a dual problem (Shalev-Shwartz & Zhang, 2013; Takác et al., 2013; Jaggi et al., 2014) or employing a different optimization algorithm (Rakhlin et al., 2012; Zhang & Lin, 2015).”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, neutral): “tion in [5], [18], [20], [23], [33], [39]–[43].”
Communication trade-offs for synchronized distributed SGD with large step size (2019, background): “Bounds on the excess risk of SGD for convex functions have been widely studied: most proofs rely on controlling the decay of the mean squared distance E[‖vt −w?‖(2)], which results in an upper bound on the mean excess of risk E[F (v̄t)−F (w?)] (LacosteJulien et al., 2012; Rakhlin et al., 2011).”
Decentralized Stochastic Optimization and Gossip Algorithms with Compressed Communication (2019, methodology): “The proof follows from Theorem 19 using the consensus averaging algorithm 1 (giving p = δ 2 ω 82 by Theorem 2) and the inequality E µ (cid:107) x 0 − x (cid:63) (cid:107) ≤ 2 G derived in (Rakhlin et al., 2012, Lemma 2) to upper bound the ﬁrst term.”
cpSGD: Communication-efficient and differentially-private distributed SGD (2018, positive): “Similar (and stronger) results can be obtained for (strongly) convex functions using results in [16] and [29].”
Local SGD Converges Fast and Communicates Little (2018, methodology): “Similar as in [15, 28, 34] we define a suitable averaging scheme for the iterates {x̄t}t≥0 to get the optimal convergence rate.”
Byzantine Stochastic Gradient Descent (2018, background): “Traditionally, to achieve a high-conﬁdence result of SGD for the strongly convex objectives, one either applies a reduction to non-strongly convex ones (c.f. Hazan and Kale [17]), or a sophisticated martingale analysis for a single-run algorithm (c.f. Rakhlin et al. [30]).”
LoAdaBoost: Loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care data (2018, background): “he same time with wt;r k between the server and Client k, little additional communication cost would be incurred by our method. Similar to other stochastic optimization-based machine learning methods [11,19,21,22], an important assumption for our approach to work satisfactorily was that the stochast”
Federated Learning with Non-IID Data (2018, background): “Federated learning relies on stochastic gradient descent (SGD), which is widely used in training deep networks with good empirical performances [12, 13, 14, 15, 16, 17].”