Accelerated gradient methods for nonconvex nonlinear and stochastic programming

By Saeed Ghadimi, Guanghui Lan. 2013

627 citations recorded by the source corpus.

In this paper, we generalize the well-known Nesterov’s accelerated gradient (AG) method, originally designed for convex smooth optimization, to solve nonconvex and possibly stochastic optimization problems. We demonstrate that by properly specifying the stepsize policy, the AG method exhibits the best known rate of convergence for solving general nonconvex smooth optimization problems by using first-order information, similarly to the gradient descent method. We then consider an important class of composite optimization problems and show that the AG method can solve them uniformly, i.e., by using the same aggressive stepsize policy as in the convex case, even if the problem turns out to be nonconvex. We demonstrate that the AG method exhibits an optimal rate of convergence if the composite problem is convex, and improves the best known rate of convergence if the problem is nonconvex. Based on the AG method, we also present new nonconvex stochastic approximation methods and show that they can improve a few existing rates of convergence for nonconvex stochastic optimization. To the best of our knowledge, this is the first time that the convergence of the AG method has been established for solving nonconvex nonlinear programming in the literature.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis, Mathematical Optimization

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 Numerical Analysis

In Mathematical Optimization

Citations in the corpus

PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “The proof of convergence of EF-SGD with momentum can be derived by incoporating a few key changes to the proof of Karimireddy et al. (2019): i) we are in a multi-worker setting, and ii) we incorporate the techniques introduced by Ghadimi & Lan (2016) to handle the additional momentum .”
Byzantine Stochastic Gradient Descent (2018, methodology): “r sections for the full specication of such parameters. We use the Oe notation to hide a logarithmic factor in the parameters. 3 use acceleration methods [26] to improve it to p1 " or p1 (cf. [16]), and this is optimal (in terms of number of stochastic gradient computations as opposed to numbe”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, methodology): “no SGD1 (SGD after SGD) O ( ε−8/3 ) (see [17] or Theorem 1)”
Closing the Generalization Gap of Adaptive Gradient Methods in Training Deep Neural Networks (2018, background): “3) is strictly better than the convergence rate of nonconvex SGD (Ghadimi and Lan, 2016).”
AdaGrad stepsizes: Sharp convergence over nonconvex landscapes, from any initialization (2018, methodology): “In the noisy setting, faster rates than O ( 1/ √ N ) are also possible using accelerated SGD methods (Ghadimi and Lan, 2016; Allen-Zhu and Yang, 2016; Reddi et al., 2016; Allen-Zhu, 2017; Xu et al., 2017; Carmon et al., 2018).”
On Nonconvex Decentralized Gradient Descent (2016, neutral): “Similar rates of convergence to a stationary point have also been shown for different nonconvex algorithms in [18], [28], [57].”
Accelerated Methods for Non-Convex Optimization (2016, background): “Ghadimi and Lan [19] show how to modify Nesterov’s accelerated gradient descent method so that it enjoys the same convergence guarantees as gradient descent on non-convex optimization problems, while maintaining the accelerated (optimal) firstorder convergence rates for convex problems.”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, background): “We refer the interested reader to [65, 1, 88, 87, 214, 215, 98] and the references therein.”
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization (2018, background): “A recent work [12] studied a generalization of NAG for nonconvex stochastic programming.”
Accelerated Proximal Gradient Methods for Nonconvex Programming (2015, methodology): “In these methods, k iterations are sufficient to find a solution within O 1 Table 1: Comparisons of GD (General Descent Method), iPiano, GIST, GDPA, IR, IFB, APG, UAG and our method for problem (1).”
The Complexity of Making the Gradient Small in Stochastic Convex Optimization (2019, background): “In stochastic non-convex optimization, there has been a flurry of recent research on algorithms with provable guarantees for finding near-stationary points (Ghadimi and Lan, 2013, 2016; Reddi et al., 2016; Allen-Zhu, 2017; Lei et al., 2017; Jin et al., 2017; Zhou et al., 2018; Fang et al., 2018).”
Gradient Diversity: a Key Ingredient for Scalable Distributed Learning (2017, background): “The step-sizes in the following results are known to be the order-optimal choices for serial SGD with constant step-size (Bottou et al., 2016, Ghadimi and Lan, 2016, Karimi et al., 2016).”
On the Convergence of a Family of Robust Losses for Stochastic Gradient Descent (2016, background): “Ghahdimi & Lan introduce a randomized stochastic algorithm to solve nonconvex problems [14], and then generalize the accelerated gradient method to improve the convergence rate if the problem is nonconvex [15].”
A Unified Analysis of Stochastic Momentum Methods for Deep Learning (2018, methodology): “However, the variant of accelerated gradient method in [ Ghadimi and Lan, 2016 ] is hard to be explained in the framework of momentum meth-ods and is not widely employed for optimizing deep neural networks.”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, background): “Single-loop GD (Nesterov, 1998) O(1/ 2) AGD (Ghadimi and Lan, 2016) O(1/ 2)”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “One can use acceleration techniques to improve the lower-order term ε−2 in this complexity [23], but not the ε−4 term.”