mlsanityData to 7 Oct 2026

Accelerated Methods for Non-Convex Optimization

arXiv 1611.00756 ↗First posted 2 Nov 2016math.OC cs.DScited by 20

Not on the map. Why?

Abstract (arXiv)

We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time O(ε-7/4 log(1/ ε) ) to find an ε-stationary point, meaning a point x such that |nabla f(x)| ≤ ε. The method improves upon the O(ε-2 ) complexity of gradient descent and provides the additional second-order guarantee that nabla2 f(x) succeq -O(ε1/2)I for the computed x. Furthermore, our method is Hessian free, i.e. it only requires gradient computations, and is therefore suitable for large scale applications.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Nov 2016.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 9; 2022: 6; 2023: 5.

20 papers.

Sort:

  1. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  2. 2021Large-Scale Deep Learning Optimizations: A Comprehensive Surveycited by 10
  3. 2021Why Do Local Methods Solve Nonconvex Problems?cited by 8
  4. 2021Escaping Saddle Points Faster with Stochastic Momentumcited by 8
  5. 2023A Cubic-regularized Policy Newton Algorithm for Reinforcement Learningcited by 7
  6. 2021A Stochastic Newton Algorithm for Distributed Convex Optimizationcited by 6
  7. 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
  8. 2022From graphs to DAGs: a low-complexity model and a scalable algorithmcited by 5
  9. 2022Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decompositioncited by 5
  10. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  11. 2023Differentially Private Optimization for Smooth Nonconvex ERMcited by 5
  12. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
8 more
  1. 2022Tackling benign nonconvexity with smoothing and stochastic gradientscited by 2
  2. 2022Asynchronous Training Schemes in Distributed Learning with Time Delaycited by 2
  3. 2021Escaping Saddle Points with Compressed SGDcited by 1
  4. 2021Faster Perturbed Stochastic Gradient Methods for Finding Local Minimacited by 1
  5. 2023Beyond first-order methods for non-convex non-concave min-max optimizationcited by 1
  6. 2023A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guaranteescited by 1
  7. 2022DRSOM: A Dimension Reduced Second-Order Methodcited by 0
  8. 2023Accelerated Optimization Landscape of Linear-Quadratic Regulatorcited by 0