Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
From MaRDI portal
Abstract: There has been much recent interest in finding unconstrained local minima of smooth functions, due in part of the prevalence of such problems in machine learning and robust statistics. A particular focus is algorithms with good complexity guarantees. Second-order Newton-type methods that make use of regularization and trust regions have been analyzed from such a perspective. More recent proposals, based chiefly on first-order methodology, have also been shown to enjoy optimal iteration complexity rates, while providing additional guarantees on computational cost. In this paper, we present an algorithm with favorable complexity properties that differs in two significant ways from other recently proposed methods. First, it is based on line searches only: Each step involves computation of a search direction, followed by a backtracking line search along that direction. Second, its analysis is rather straightforward, relying for the most part on the standard technique for demonstrating sufficient decrease in the objective from backtracking. In the latter part of the paper, we consider inexact computation of the search directions, using iterative methods in linear algebra: the conjugate gradient and Lanczos methods. We derive modified convergence and complexity results for these more practical methods.
Recommendations
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis
- A stochastic line search method with expected complexity analysis
- Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
- LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums
Cites work
- A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds
- A trust region algorithm with a worst-case iteration complexity of \(\mathcal{O}(\epsilon ^{-3/2})\) for nonconvex optimization
- Accelerated methods for nonconvex optimization
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- Adaptive cubic regularisation methods for unconstrained optimization. II: Worst-case function- and derivative-evaluation complexity
- Complexity bounds for second-order optimality in unconstrained optimization
- Cubic regularization of Newton method and its global performance
- Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Finding approximate local minima faster than gradient descent
- Gradient descent finds the cubic-regularized nonconvex Newton step
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Nonlinear stepsize control algorithms: complexity bounds for first- and second-order optimality
- On the complexity of steepest descent, Newton's and regularized Newton's methods for nonconvex unconstrained optimization problems
- The Conjugate Gradient Method and Trust Regions in Large Scale Optimization
- The use of quadratic regularization with a cubic descent condition for unconstrained optimization
- Trust Region Methods
Cited in
(45)- A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- A generalized worst-case complexity analysis for non-monotone line searches
- An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization
- Exploiting negative curvature in deterministic and stochastic optimization
- First-order methods almost always avoid strict saddle points
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- Analysis of performance of symmetric second-order line search algorithms through continued fractions
- Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- First-Order Methods for Nonconvex Quadratic Minimization
- Convergence of Newton-MR under inexact Hessian information
- A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
- Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
- Stochastic variance-reduced cubic regularization methods
- A stochastic line search method with expected complexity analysis
- On the Evaluation Complexity of Constrained Nonlinear Least-Squares and General Constrained Nonlinear Optimization Using Second-Order Methods
- Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
- LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums
- Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
- Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization
- A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
- A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression
- Convergence Properties of an Objective-Function-Free Optimization Regularization Algorithm, Including an \(\boldsymbol{\mathcal{O}(\epsilon^{-3/2})}\) Complexity Bound
- A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
- The evaluation complexity of finding high-order minimizers of nonconvex optimization
- Recent Theoretical Advances in Non-Convex Optimization
- Parameter-free accelerated gradient descent for nonconvex minimization
- Complexity bounds for second-order optimality in unconstrained optimization
- Complexity of a projected Newton-CG method for optimization with bounds
- Complexity analysis of regularization methods for implicitly constrained least squares
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
- Homogeneous second-order descent framework: a fast alternative to Newton-type methods
- Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
- Yet another fast variant of Newton's method for nonconvex optimization
- Riemannian trust-region methods for strict saddle functions with complexity guarantees
- A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- Riemannian adaptive regularized Newton methods with Hölder continuous Hessians
- Complexity analysis of inexact cubic-regularized primal-dual methods for finding second-order stationary points
- Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
- An improvement of the Goldstein line search
- Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
This page was built for publication: Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4641667)
