An optimal method for stochastic composite optimization

By Guanghui Lan. 2011

597 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

Measuring the Effects of Data Parallelism on Neural Network Training (2018, background): “7 Meanwhile, when losses are convex and the objective is H -smooth, accelerated parallel mini-batch SGD enjoys the bound (Lan, 2012) where b is the batch size.”
Train faster, generalize better: Stability of stochastic gradient descent (2015, background): “e update is a linear combination of the current iterate and the previous direction. For convex problems, momentum is known to decrease the number of iterations required by stochastic gradient descent [22]. For general nonlinear problems, is believed to decrease the number of iterations required to a”
Advances and Open Problems in Federated Learning (2019, methodology): “[49] J. Wang, A. Sahu, G. Joshi, and S. Kar, “MATCHA: Speeding up decentralized SGD via matching decomposition sampling,” Preprint, May 2019.”
Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization (2018, methodology): “Comparing (18) and (22), we see that SVRG also improves over A-MB-SGD as soon as K > T log(TKM/L), that is if the number of points we are processing on each machine each round is slightly more then the total number of rounds, which is also a realistic scenario.”
Deep learning with Elastic Averaging SGD (2014, methodology): “It is based on the Nesterov’s momentum scheme Nesterov (2005); Lan (2012); Sutskever et al. (2013), where the update of the local worker of the form captured in Equation 4 is replaced by the following update , where δ is the momentum term.”
Optimal Distributed Online Prediction Using Mini-Batches (2010, methodology): “The analysis in Appendix A (and Appendix B) actually applies to a much larger class of update rules, which includes the family of mirror descent updates (Nemirovski et al., 2009; Lan, 2009) and the family of (non-Euclidean) dual averaging updates (Nesterov, 2009; Xiao, 2010).”
Distributed delayed stochastic optimization (2011, methodology): “Our second assumption has been used to show rates of convergence based on the variance of a gradient estimator for stochastic optimization problems (e.g. [JNT08, Lan10]).”
Communication-efficient algorithms for decentralized and stochastic optimization (2017, neutral): “et X is nonempty. In this paper, we also consider the situation where one can only have access to noisy ﬁrst-order information (function values and subgradients) of the functions fi, i = 1,...,m (see [41,23]). This happens, for example, when the function fi’s are given in the form of expectation, i.”
An asynchronous mini-batch algorithm for regularized stochastic optimization (2015, neutral): “[16] M. Zinkevich, J. Langford, and A. J. Smola, “Slow learners are fast,” Advances in Neural Information Processing Systems, pp. 2331–2339, 2009.”
Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n) (2013, background): “, see [10]) but not on the rate itself, which remains O(1/ √ n) for non-strongly-convex problems.”
Incremental Majorization-Minimization Optimization with Application to Large-Scale Machine Learning (2014, background): “Even though these methods have inherent sublinear convergence rates for convex and strongly convex problems [34, 43], they typically have a cheap computational cost per iteration, enabling them to efficiently find an approximate solution.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, background): “The authors of [19, 22] obtained running time of the formO(L/√ε+ σ/ε2) in the presence of stochastic gradient with variance σ .”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “al performance with O(n(ε)/m) runtime, as long as the minibatch size is not too large: Dekel et al. (2012) showed that the minibatch size can be as large as bm = O( p n(ε)), and Cotter et al. (2011); Lan (2012) showed with acceleration this can be improved to bm = O(n(ε)3/4). Using this maximal mini”
Accelerated gradient methods for nonconvex nonlinear and stochastic programming (2013, methodology): “(1.5) Currently, the randomized stochastic gradient (RSG) method initially studied by Ghadimi and Lan [12] and later improved in [13,6] seems to be the only available stochastic approximation (SA) algorithm for solving the aforementioned general stochastic NLP problems, while other SA methods (see, ”
Stochastic Heavy ball (2016, methodology): “However, this remark should be balanced by the fact that we did not use the Lan adaptation of the Nesterov accelerated gradient descent introduced in [Lan12].”
Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regression (2016, background): “They do not assume knowledge of the distribution of the inputs; however, Massart (2007) and Tsybakov (2008) discuss optimal rates on ellipsoids, and Györfi et al.”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, background): “5], [22, 32, 51]), which is reasonable when X is compact, but may fail for non-compact X .”
Guaranteed Sufficient Decrease for Stochastic Variance Reduced Gradient Optimization (2018, methodology): “Moreover, we also introduce the following lemmas [51, 52], which are useful in our convergence analysis.”
On Perturbed Proximal Gradient Algorithms (2014, background): “Some of these works focused on stochastic sub-gradient and mirror descent algorithms; see Nemirovski et al. (2008); Duchi et al. (2011); Cotter et al. (2011); Lan (2012); Juditsky and Nemirovski (2012a,b).”