On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems

By Coralia Cartis, N. Gould, Philippe L. Toint. 2010

266 citations recorded by the source corpus.

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

Accelerated gradient methods for nonconvex nonlinear and stochastic programming (2013, methodology): “nd show that by properly specifying the stepsize policy, it not only achieves the optimal rate of convergence for convex optimization, but also exhibits the best-known rate of convergence as shown in [25,4] for solving general smooth NLP problems by using ﬁrst-order methods. Algorithm 1 The accelera”
Smoothing and worst-case complexity for direct-search methods in nonsmooth optimization (2013, background): “It has been proved by Cartis, Gould, and Toint [7] that the worst case bound O(ǫ −2 ) for steepest descent is sharp or tight (see the details in [7]).”
Global rates of convergence for nonconvex optimization on manifolds (2016, unknown): “Since the rates O (1 /ε 2 ) and O (1 /ε 3 ) are sharp for gradient descent and trust regions when M = R n (Cartis et al., 2010, 2012), they are also sharp for M a generic Riemannian manifold.”
Distributed Non-Convex First-Order optimization and Information Processing: Lower Complexity Bounds and Rate Optimal Algorithms (2018, background): “It has been shown in [10] that the above rate is (almost) tight for GD.”
Lower bounds for non-convex stochastic optimization (2019, background): “An earlier line of work develops lower bounds for finding stationary points of non-convex functions in the low-dimensional regime where d is constant, but they obtain either weaker lower bounds [45] or tight bounds that hold only for specific algorithm classes [15, 16, 17, 18].”
On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization (2018, methodology): “The most well-known ﬁrst-order algorithms are gradient descent (GD) for deterministic optimization [6, 7] and stochastic gradient descent (SGD) for stochastic optimization [8, 9], where the former determines ∆ t using the full (batch) gradient of an objective function, and the latter uses a simpler…”
Convergence Rate of Frank-Wolfe for Non-Convex Objectives (2016, methodology): “Cartis et al. (2010) also showed that the O (1 / √ t ) rate was tight for the gradient descent method for an unconstrained objective.”
On the Oracle Complexity of First-Order and Derivative-Free Algorithms for Smooth Nonconvex Minimization (2012, methodology): “This result was extended by Cartis et al. (2010a) to an algorithm no longer requiring the computation of exact second-derivatives, but merely of a suitably accurate approximation (2) .”
Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization (2013, methodology): “ar from mature. For the deterministic case, i.e., σ = 0 in (4), the NONCONVEX STOCHASTIC COMPOSITE OPTIMIZATION 3 complexity of the gradient descent method for solving problem (1) has been studied in [6,26]. Very recently, Ghadimi and Lan [15] proposed an SA-type algorithm coupled with a randomizati”
"Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions (2017, background): “Without convexity, gradient descent is significantly worse, having worst-case complexity Θ( −2) (Cartis et al., 2010).”
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (2017, background): “Gradient descent (GD), a simple and fundamental optimization algorithm that has proved its value in large-scale machine learning, is known to ﬁnd an ǫ -ﬁrst-order stationary point (where k∇ f ( x ) ≤ ǫ ) in O (1 /ǫ 2 ) iterations [Nesterov, 1998], and this rate is sharp [Cartis et al., 2010].”
Worst case complexity of direct search (2013, methodology): “It has been proved by Cartis, Gould, and Toint [4] that the worst case bound O( −2) for steepest descent is sharp or tight, in the sense that there exists an example, dependent on an arbitrarily small parameter τ > 0, for which a steepest descent method (with a Goldstein-Armijo line search) requires”
Bayesian Nonparametric Kernel-Learning (2015, methodology): “ large datasets where N≫ M> d, and M≥ L. For classiﬁcation, sampling Wj’s is O(MN(d+ǫ−2)); where the ǫ−2 term arises from performing the 2- dimensional optimization required in (15) to ǫprecision [Cartis et al., 2010]. Treating ǫas a constant, we have a total runtime of O(MNd) for inference. Henc”