Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms

By Saeed Ghadimi, Guanghui Lan. 2013

230 citations recorded by the source corpus.

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

Is Local SGD Better than Minibatch SGD? (2020, methodology): “Looking to the analysis of local AC-SA for quadratic objectives in Corollary 1, we might hope to design an algorithm which achieves error for general convex objectives.”
Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming (2013, background): “The convergence of existing SA methods requires f ( ) to be convex [23, 19, 18, 11, 10].”
Accelerated gradient methods for nonconvex nonlinear and stochastic programming (2013, background): “, [10,11,15,23,30,31,33]) require the convexity assumption about Ψ .”
The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2013, methodology): “complexity to solve (3.34) will be comparable to the one to solve (1.2). Note however, that such a selection of k·k will possibly increase the value of the condition number given by L/µ. Motivated by [23], we present a shrinking CndG method under the above assumption on the enhanced LO oracle. It sh”
Minibatch vs Local SGD for Heterogeneous Distributed Learning (2020, methodology): “Minibatch SGD can also be accelerated to improve its convergence rate [8, 9].”
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.”
An Improved Analysis of Stochastic Gradient Descent with Momentum (2020, methodology): “In [8] and [10], doubling argument based rules are analyzed for SGD on strongly convex objectives, where the stage length is doubled whenever the stepsize is halved.”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “Alternately, if we split the convergence rate into a deterministic and stochastic part, these methods can improve the dependency of the convergence rate of the deterministic part [18,22,63].”
Accelerating Stochastic Gradient Descent (2017, methodology): “The worst-case lower bounds in Nemirovsky and Yudin (1983) are based on that η is bounded; the accelerated methods in Lan (2008); Hu et al. (2009); Ghadimi and Lan (2012, 2013); Dieuleveut et al. (2016) which match these lower bounds in various cases, all assume either bounded noise or, at least E…”
An Overview of Stochastic Approximation (2015, methodology): “The accelerated SA (AC-SA) algorithm [21] takes a similar approach to iterate averaging and RSA by taking long strides and incorporating each of the iterates into”
On Acceleration with Noise-Corrupted Gradients (2018, methodology): “Such a model captures the setting of stochastic methods, in which the gradient is only estimated from a subset of its components (Lan, 2012; Ghadimi & Lan, 2012; 2013; Atchade et al., 2014; Krichene & Bartlett, 2017; Jain et al., 2018), the setting of differentially private empirical risk…”
Asynchronous Decentralized Accelerated Stochastic Gradient Descent (2018, methodology): “in [1], [43], [44] to approximately solve the primal subprob-”
First-order methods of smooth convex optimization with inexact oracle (2013, background): “This complexity is optimal, up to a logarithmic factor (see [12, 5]).”
Optimal Primal-Dual Methods for a Class of Saddle Point Problems (2013, background): “In both deterministic and stochastic cases, the rate of convergence of the APD algorithms will depend on the distance from the initial point to the set of optimal solutions.”