An optimal algorithm for stochastic strongly-convex optimization

By Elad Hazan, Satyen Kale. 2010

19 citations recorded by the source corpus.

We consider stochastic convex optimization with a strongly convex (but not necessarily smooth) objective. We give an algorithm which performs only gradient updates with optimal rate of convergence.

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

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

Citations in the corpus

Variance-based Regularization with Convex Objectives (2016, background): “ √ n with high probability, as long as the growth of R away from its optima scales appropriately. For example, when γ = 2, which corresponds to the usual strong convexity conditions in the literature [17, 15] (though ours is easier to satisfy, as it is a more local notion of strong convexity), we ob”
Stochastic Gradient Methods for Distributionally Robust Optimization with f-divergences (2016, background): “(This is not just a theoretical issue: in extensive simulations that we omit because they are a bit boring, SGD and other heuristic approaches that impose shrinking bounds of the form c > at each iteration t all fail to optimize the objective (5).)”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, unknown): “tions in Section4.1, strong convexity conditions play an important role in the analysis and implementation of methods for convex optimization [25,46,43,18] as well as stochastic optimization problems [24,21]. It is thus of interest to develop an understanding of the behavior of the aProx family of m”
Asynchronous stochastic convex optimization: the noise is in the noise and SGD don't care (2015, methodology): “for each problem, whether we use stepsizes αk = k−β (with β = .55) that we analyze or the epoch-based exponentially decreasing stepsize scheme used by Niu et al. [25], also analyzed by Hazan and Kale [14] and Ghadimi and Lan [13]. In Figures 7 and 8, we plot speedup achieved for these same experimen”
Beyond the regret minimization barrier: an optimal algorithm for stochastic strongly-convex optimization (2011, unknown): “This work however was done independently and a preliminary version was published on arXiv (Hazan and Kale (2010)) before the technical report of Juditsky and Nesterov was available.”
Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization (2014, methodology): “Our work was done independently and a preliminary version was published on arXiv [Hazan and Kale, 2010] before the technical reports of Juditsky and Nesterov [2010] and Ghadimi and Lan [2010] were made available.”
Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization (2010, unknown): “ese lower bounds are sharp. 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. Note how the geometry of the set does not come into play, but r”