Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization

By Elad Hazan, Satyen Kale. 2014

237 citations recorded by the source corpus.

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

Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity (2021, neutral): “3 Connection to Other Assumptions In the optimization literature, the standard convergence analysis of stochastic gradient algorithms like SGD relied on bounded gradient (E‖∇fi(x)‖(2) ≤ c) or bounded variance assumptions (E‖∇fi(x)− ∇f(x)‖2 ≤ c) (Recht et al., 2011; Hazan and Kale, 2014; Rakhlin et a”
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.”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “These results have been extended by many machine learning researchers, yielding tighter bounds and probabilistic guarantees [13,14,35].”
Qsparse-Local-SGD: Distributed SGD With Quantization, Sparsification, and Local Computations (2019, neutral): “This is a standard assumption in [SSS07, NJLS09, RRWN11, HK14, RSS12, SCJ18, Sti19, YYZ18, KSJ19, AHJ + 18].”
Byzantine Stochastic Gradient Descent (2018, neutral): “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]).”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “If f(x) is also known to be strongly convex, to get the tightest convergence rate, one can repeatedly apply SGD with decreasing learning rate α [19].”
On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimization (2017, methodology): “Similar averaging approaches have been proposed in the literature, see [Hazan and Kale, 2014; Johnson and Zhang, 2013; Smith et al., 2016; Zhang et al., 2016; Loshchilov and Hutter, 2016; Chen et al., 2016; Wang et al., 2017].”
Perturbed Iterate Analysis for Asynchronous Stochastic Optimization (2015, neutral): “, [1,29]).”
SGD: General Analysis and Improved Rates (2019, neutral): “L G ] 26 F e b 2019 eral recent papers (Recht et al., 2011; Hazan & Kale, 2014; Rakhlin et al., 2012).”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “For instance, obtaining the optimal 1/T rate for online learning was a very meaningful result, even though the logT /T rate was known [18, 35].”
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption (2018, background): “…The classical theoretical analysis of SGD assumes that the stochastic gradients are uniformly bounded , i.e. there exists a ﬁnite (ﬁxed) constant σ < ∞ , such that (see e.g. (Shalev-Shwartz et al., 2007; Nemirovski et al., 2009; Recht et al., 2011; Hazan & Kale, 2014; Rakhlin et al., 2012), etc.).”
Variants of RMSProp and Adagrad with Logarithmic Regret Bounds (2017, background): “We are aware of the fact that in the strongly convex case online to batch conversion is not tight (Hazan & Kale, 2014), however that does not necessarily imply that the algorithms behave generally suboptimal.”
Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm (2015, methodology): “nity. If we assume that the total number of iterations is ﬁxed (ﬁnite horizon setting), a straightforward optimization in γleads to a bound of order O((log(n)n−1)1/2). Using the ”doubling trick” (see [18]) this can be converted to an anytime algorithm with a bound on kδxQn γ− πkTV of order O((log(n)”
The Step Decay Schedule: A Near Optimal, Geometrically Decaying Learning Rate Procedure (2019, methodology): “Dekel et al. (2012); Lacoste-Julien et al. (2012); Rakhlin et al. (2012); Ghadimi and Lan (2012, 2013b); Hazan and Kale (2014); Bubeck (2014); Dieuleveut et al. (2016) use iterate averaged SGD to achieve minimax rates for various problem classes non-asymptotically.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “ying SGD once for T iterations, we can obtain a point, denoted by x 1 , satisfying E [F (x 1 )] F (x ) V 2(1 L ) + kx 0 x k2 2T V 2(1 L ) + F (x 0 ) F (x ) T : (B.4) Now, following the idea of [25], we repeatedly apply Theorem 3.7a to get the tightest result. In particular, we rst apply (B.4) for ”
A Distributed Hierarchical SGD Algorithm with Sparse Global Reduction (2019, background): “Many recent studies adopt new variants of synchronous parallel SGD algorithms (see Hazan and Kale [2014], Johnson and Zhang [2013], Smith et al. [2016], Zhang et al. [2016], Loshchilov and Hutter [2016], Chen et al. [2016], Wang et al. [2017], Zhou and Cong [2018]).”