Accelerated Methods for Non-Convex Optimization

By Yair Carmon, John C. Duchi, Oliver Hinder, Aaron Sidford. 2016

196 citations recorded by the source corpus.

We present an accelerated gradient method for nonconvex optimization problems with Lipschitz continuous first and second derivatives. In a time $O(\epsilon^{-7/4} \log(1/ \epsilon) )$, the method finds an $\epsilon$-stationary point, meaning a point $x$ such that $\|\nabla f(x)\| \le \epsilon$. The method improves upon the $O(\epsilon^{-2} )$ complexity of gradient descent and provides the additional second-order guarantee that $\lambda_{\min}(\nabla^2 f(x)) \gtrsim -\epsilon^{1/2}$ 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.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

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

Citations in the corpus

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).”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “, 2015) or methods with second order information (Carmon et al., 2016; Agarwal et al., 2017) can find a global minimum in polynomial time.”
Lower bounds for finding stationary points I (2017, methodology): “Examples include time to -optimality, in which case T ( {x}t∈N, f ) = inf{t ∈ N | f(x(t))− infx f(x) ≤ }, and the second-order stationarity desired in many non-convex optimization problems [13, 23], where for 1, 2 > 0 we define T ( {x}t∈N, f ) = inf{t ∈ N | ‖∇f(x(t))‖ ≤ 1 and ∇2f(x(t)) − 2I}.”
Natasha 2: Faster Non-Convex Optimization Than SGD (2017, methodology): “In recent works [3, 13], it has been proposed to study a more reﬁned convergence rate, by assuming that f ( x ) is of σ -bounded nonconvexity (or σ -nonconvex), meaning all the eigenvalues of ∇ 2 f ( x ) lie in [ − σ, L ] (A3) for some σ ∈ (0 , L ] .”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “stationary point in O(ε−7/4) iterations (up to some logarithmic factor) with high probability, which matches the computational complexity of [173], [175].”
Stochastic Cubic Regularization for Fast Nonconvex Optimization (2017, methodology): “Several algorithms incorporating Hessian-vector products [Carmon et al., 2016, Agarwal et al., 2017] have been shown to achieve faster convergence rates than gradient descent in the non-stochastic setting.”
A Generic Approach for Escaping Saddle points (2017, background): “[4] presented algorithms for finding second-order critical points by tackling some 255 practical issues that arise in [23].”
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions (2017, methodology): “In distinction from the methods of Carmon et al. (2016) and Agarwal et al. (2016), our method provides no guarantees on positive definiteness of ∇2f(x); if initialized at a saddle point it will terminate immediately.”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, methodology): “Rates of O (1 /ǫ 7 / 4 ) have been established for such algorithms [Carmon et al., 2016, Agarwal et al., 2017, Royer and Wright, 2017]. e Finally, in the realm of purely gradient-based algorithms, Ge et al. [2015] present the ﬁrst polynomial guarantees for a perturbed version of GD, and Jin et al.…”
Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning (2018, background): “, 2017b), Hessian-vector-product-based (Carmon et al., 2016; Agarwal et al., 2016; Royer & Wright, 2018; Royer et al., 2018), and Hessian-based (Nesterov & Polyak, 2006; Curtis et al.”
No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis (2017, methodology): “Combined with recent results (e.g. Ge et al. [2015], Carmon et al. [2016], Agarwal et al. [2016], Jin et al. [2017]) that are guaranteed to ﬁnd a local minimum for many non-convex functions, such problems can be efﬁciently solved by basic optimization algorithms such as stochastic gradient descent.”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “The breakthrough of gradient cost for finding second-order stationary points were achieved in 2016/2017, when the two recent lines of literatures, namely FastCubic [1] and CDHS [8] as well as their stochastic versions [2, 35], achieve a gradient cost of Õ(min(n −1.”