"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions

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

165 citations recorded by the source corpus.

We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our AGD variant converges quickly, as if the function was convex, or we produce a certificate that the function is "guilty" of being non-convex. This non-convexity certificate allows us to exploit negative curvature and obtain deterministic, dimension-free acceleration of convergence for non-convex functions. For a function $f$ with Lipschitz continuous gradient and Hessian, we compute a point $x$ with $\|\nabla f(x)\| \le \epsilon$ in $O(\epsilon^{-7/4} \log(1/ \epsilon) )$ gradient and function evaluations. Assuming additionally that the third derivative is Lipschitz, we require only $O(\epsilon^{-5/3} \log(1/ \epsilon) )$ evaluations.

Subfields: Artificial Intelligence, Computational Mechanics, Mathematical Physics

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 Mathematical Physics

Citations in the corpus

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron (2018, background): “Under these conditions, constant step-size SGD has a better convergence rate than algorithms which have recently been proposed to improve on SGD [2, 4].”
Momentum Improves Normalized SGD (2020, background): “75 ) Carmon et al. (2017) rather than the O (1 / 2 ) achieved by gradient descent.”
Lower bounds for non-convex stochastic optimization (2019, background): “Recent years have seen rapid development of a body of work that studies non-convex optimization through the lens of non-asymptotic convergence rates to -stationary points [35, 27, 12, 29, 22, 53, 23].”
Ellipsoidal Trust Region Methods and the Marginal Value of Hessian Information for Neural Network Training (2019, methodology): “[14] Yair Carmon, Oliver Hinder, John C Duchi, and Aaron Sidford.”
Lower bounds for finding stationary points I (2017, methodology): “The lower bounds exhibit a fundamental gap between first- and second-order methods, and nearly match the known upper bounds [14].”
L ] 1 0 A pr 2 01 9 AdaGrad-Norm convergence over nonconvex landscapes AdaGrad stepsizes : sharp convergence over nonconvex landscapes , from any initialization (2019, methodology): “It is becoming common to define an ε-approximate stationary point as ‖∇F (x)‖ ≤ ε (Agarwal et al., 2017; Carmon et al., 2018, 2017a; Fang et al., 2018; Zhou et al., 2018; Allen-Zhu, 2018), but we use the convention ‖F (x)‖2 ≤ ε (Lei et al., 2017; Bottou et al., 2018) to most easily compare our…”
The Case for Full-Matrix Adaptive Regularization (2018, methodology): “…for large-scale implementation, these quasi-Newton methods, along with (subsampled, online, cubic-regularized) Newton methods [EM15, ABH17, LACBL16, HAK07, AAZB + 17, CDHS17] exhibit very diﬀerent dynamics than the standard optimizers in deep learning, and thus have not seen widespread adoption.”
SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator (2018, methodology): “We emphasize that Assumptions 1, 2, and 3 are standard for non-convex stochastic optimization (Agarwal et al., 2017; Carmon et al., 2017b; Jin et al., 2017a; Xu et al., 2017; Allen-Zhu & Li, 2018).”
Escaping Saddles with Stochastic Gradients (2018, background): “Recently, it has been shown that GD can be accelerated to ﬁnd such a point in O ( − 7 / 4 log( − 1 ) ) (Carmon et al., 2017).”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, methodology): “Under the additional assumption of Lipschitz Hessians (see Deﬁnition 4), Carmon et al. [2017] develop a new algorithm that converges in O (1 /ǫ 7 / 4 ) steps.”
Non-convex Finite-Sum Optimization Via SCSG Methods (2017, background): “Gradient Methods GD O ( n ε ) [24, 13] Õ ( n μ ) [25, 17] Best available Õ ( n ε7/8 ) [9] smooth gradient Õ ( n ε5/6 ) [9] smooth Hessian Stochastic Gradient Methods SGD O ( 1 ε2 ) [24, 26] O ( 1 μ2ε ) [17] H∗ = O(1) Best available O ( n+ n 2/3 ε ) [26, 27] Õ ( n+ n 2/3 μ ) [26, 27] SCSG Õ ( 1 ε5/3 ”