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
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- 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
- 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)- Analysis of performance of symmetric second-order line search algorithms through continued fractions
- Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
- Parameter-free accelerated gradient descent for nonconvex minimization
- Error estimates for iterative algorithms for minimizing regularized quadratic subproblems
- A line-search algorithm inspired by the adaptive cubic regularization framework and complexity analysis
- An improvement of the Goldstein line search
- Convergence Properties of an Objective-Function-Free Optimization Regularization Algorithm, Including an \(\boldsymbol{\mathcal{O}(\epsilon^{-3/2})}\) Complexity Bound
- Exploiting negative curvature in deterministic and stochastic optimization
- First-order methods almost always avoid strict saddle points
- First-Order Methods for Nonconvex Quadratic Minimization
- A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Regional complexity analysis of algorithms for nonconvex smooth optimization
- Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
- LSOS: Line-search second-order stochastic optimization methods for nonconvex finite sums
- Complexity of a projected Newton-CG method for optimization with bounds
- A generalized worst-case complexity analysis for non-monotone line searches
- Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization
- Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
- Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
- An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
- Complexity guarantees for nonconvex Newton-MR under inexact Hessian information
- The evaluation complexity of finding high-order minimizers of nonconvex optimization
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- Complexity analysis of regularization methods for implicitly constrained least squares
- A nonlinear conjugate gradient method with complexity guarantees and its application to nonconvex regression
- Yet another fast variant of Newton's method for nonconvex optimization
- Homogeneous second-order descent framework: a fast alternative to Newton-type methods
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- Riemannian trust-region methods for strict saddle functions with complexity guarantees
- Gradient norm regularization second-order algorithms for solving nonconvex-strongly concave minimax problems
- A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
- On the Evaluation Complexity of Constrained Nonlinear Least-Squares and General Constrained Nonlinear Optimization Using Second-Order Methods
- Complexity bounds for second-order optimality in unconstrained optimization
- Recent Theoretical Advances in Non-Convex Optimization
- A stochastic line search method with expected complexity analysis
- Convergence of Newton-MR under inexact Hessian information
- A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
- Stochastic variance-reduced cubic regularization methods
- A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- Riemannian adaptive regularized Newton methods with Hölder continuous Hessians
- A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
- Complexity analysis of inexact cubic-regularized primal-dual methods for finding second-order stationary points
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)
