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

By Elad Hazan, Satyen Kale. 2011

252 citations recorded by the source corpus.

How researchers see this paper

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

In Optimization & Training

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “Keywords: Stochastic Convex Optimization; Derivative-Free Optimization; Bandit Convex Optimization; Regret”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “We consider both adversarial regret, where the data sample dt are drawn adversarially based on the past output {θ1, . . . , θt} (Hazan, 2019), and stochastic regret (Hazan & Kale, 2014), where the data samples in D are drawn i.i.d. from some fixed distribution τ .”
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization (2011, methodology): “Note that this is a somewhat weaker assumption than (Hazan & Kale, 2011), which required that (cid:107) ˆ g t 2 ≤ G 2 with probability 1, since we focus only on bounds which hold in expectation.”
Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes (2012, methodology): “2), and O (1 / √ T ) error for general convex F Zinkevich (2003); Hazan et al. (2007); Hazan & Kale (2011).”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, methodology): “It is classical to use doubling trick s to remedy this problem while preserving convergence rates [26], this is done in “2-step-dbl.”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “Based on their ﬁndings, we do not include in our ﬁgures other variants of SGD, e.g., [17, 23, 25, 49].”
A simpler approach to obtaining an O(1/t) convergence rate for the projected stochastic subgradient method (2012, methodology): “Following [1, 2, 3, 4], we consider a stochastic approximation scenario where only unbiased estimates of subgradients of f are available, with the projected stochastic subgradient method.”
Information-theoretic lower bounds on the oracle complexity of convex optimization (2009, background): “In particular, for S = B∞(1), stochastic gradient descent achieves the rate (11) up to logarithmic factors [7], and a closely related algorithm proposed in very recent work [8] matches the lower bound exactly.”
A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets (2012, methodology): “Stochastic versions of FG methods : Various options are available to accelerate the convergence of the FG method for smooth functions, such as the accelerated full gradient (AFG) method Nesterov [1983], as well as classical techniques based on quadratic approximations such as non-linear conjugate…”
Improved Dynamic Regret for Non-degenerate Functions (2016, methodology): “Furthermore, those upper bounds are proved to be minimax optimal (Abernethy et al., 2008a; Hazan and Kale, 2011).”
On the Computation and Communication Complexity of Parallel SGD with Dynamic Batch Sizes for Stochastic Non-Convex Optimization (2019, methodology): “However, for general strongly convex stochastic minimization, it is in general impossible to develop linearly converging stochastic gradient based solver and the fastest possible convergence is O(1/T ) (Rakhlin et al., 2012; Hazan & Kale, 2014; Lacoste-Julien et al., 2012).”
Complexity of finding near-stationary points of convex functions stochastically (2018, methodology): “We will see here that this complexity can be improved to (cid:16) (cid:17) The work horse of the strategy is the subgradient method for minimizing strongly convex functions [8–10 by adapting the technique of [1].”
How To Make the Gradients Small Stochastically (2018, methodology): “Now, following the idea of [11], we repeatedly apply Theorem 4.”