# Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming

arXiv: https://arxiv.org/abs/1310.3787 · HTML: https://mlsanity.com/paper/1310.3787/

## Key facts

- Cited by 75 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Oct 2013.

## Built on by (most cited first, 30 of 75)

- [On the Convergence Rates of Policy Gradient Methods](https://mlsanity.com/paper/2201.07443/) (2022)
- [Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimization](https://mlsanity.com/paper/2503.12645/) (2025)
- [Policy Gradient Method For Robust Reinforcement Learning](https://mlsanity.com/paper/2205.07344/) (2022)
- [Fixing by Mixing: A Recipe for Optimal Byzantine ML under Heterogeneity](https://mlsanity.com/paper/2302.01772/) (2023)
- [Lower Bounds and Accelerated Algorithms for Bilevel Optimization](https://mlsanity.com/paper/2102.03926/) (2021)
- [Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2209.05045/) (2022)
- [High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize](https://mlsanity.com/paper/2204.02833/) (2022)
- [Policy Gradient in Robust MDPs with Global Convergence Guarantee](https://mlsanity.com/paper/2212.10439/) (2022)
- [LDAdam: Adaptive Optimization from Low-Dimensional Gradient Statistics](https://mlsanity.com/paper/2410.16103/) (2024)
- [Faster Rates of Convergence to Stationary Points in Differentially Private Optimization](https://mlsanity.com/paper/2206.00846/) (2022)
- [Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks](https://mlsanity.com/paper/2206.10870/) (2022)
- [Learning Weakly Convex Regularizers for Convergent Image-Reconstruction Algorithms](https://mlsanity.com/paper/2308.10542/) (2023)
- [Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning](https://mlsanity.com/paper/2305.18424/) (2023)
- [On the Convergence and Optimality of Policy Gradient for Markov Coherent Risk](https://mlsanity.com/paper/2103.02827/) (2021)
- [Stochastic Halpern Iteration with Variance Reduction for Stochastic Monotone Inclusions](https://mlsanity.com/paper/2203.09436/) (2022)
- [MicroAdam: Accurate Adaptive Optimization with Low Space Overhead and Provable Convergence](https://mlsanity.com/paper/2405.15593/) (2024)
- [SGD-Net: Efficient Model-Based Deep Learning with Theoretical Guarantees](https://mlsanity.com/paper/2101.09379/) (2021)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [PPO-Clip Attains Global Optimality: Towards Deeper Understandings of Clipping](https://mlsanity.com/paper/2312.12065/) (2023)
- [Robust Constrained Reinforcement Learning](https://mlsanity.com/paper/2209.06866/) (2022)
- [Orthogonal Directions Constrained Gradient Method: from non-linear equality constraints to Stiefel manifold](https://mlsanity.com/paper/2303.09261/) (2023)
- [Convergence of Adam for Non-convex Objectives: Relaxed Hyperparameters and Non-ergodic Case](https://mlsanity.com/paper/2307.11782/) (2023)
- [Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator](https://mlsanity.com/paper/2104.14840/) (2021)
- [On the fast convergence of minibatch heavy ball momentum](https://mlsanity.com/paper/2206.07553/) (2022)
- [Complexity of normalized stochastic first-order methods with momentum under heavy-tailed noise](https://mlsanity.com/paper/2506.11214/) (2025)
- [Non-convex Stochastic Composite Optimization with Polyak Momentum](https://mlsanity.com/paper/2403.02967/) (2024)
- [An Accelerated Algorithm for Stochastic Bilevel Optimization under Unbounded Smoothness](https://mlsanity.com/paper/2409.19212/) (2024)
- [Escaping Saddle Points Faster with Stochastic Momentum](https://mlsanity.com/paper/2106.02985/) (2021)
- [Gradient Norm Minimization of Nesterov Acceleration: o(1/k3)](https://mlsanity.com/paper/2209.08862/) (2022)
- [Measurement Score-Based Diffusion Model](https://mlsanity.com/paper/2505.11853/) (2025)

## Abstract (arXiv)

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.