Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step
From MaRDI portal
Publication:5233102
DOI10.1137/17M1113898zbMath1461.65135arXiv1612.00547OpenAlexW2971617498WikidataQ127320765 ScholiaQ127320765MaRDI QIDQ5233102
Publication date: 16 September 2019
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1612.00547
global optimizationNewton's methodpower methodgradient descenttrust region methodscubic regularizationnonasymptotic rate of convergencenonconvex quadratics
Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30) Quadratic programming (90C20)
Related Items
An improvement of adaptive cubic regularization method for unconstrained optimization problems ⋮ Unnamed Item ⋮ Smoothness parameter of power of Euclidean norm ⋮ Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation ⋮ Riemannian stochastic variance-reduced cubic regularized Newton method for submanifold optimization ⋮ A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees ⋮ Random Coordinate Descent Methods for Nonseparable Composite Optimization ⋮ First-Order Methods for Nonconvex Quadratic Minimization ⋮ Newton-type methods for non-convex optimization under inexact Hessian information ⋮ A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization ⋮ Second-Order Guarantees of Distributed Gradient Algorithms ⋮ Recent Theoretical Advances in Non-Convex Optimization ⋮ On the Quadratic Convergence of the Cubic Regularization Method under a Local Error Bound Condition ⋮ Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem ⋮ Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization ⋮ Minimizing uniformly convex functions by cubic regularization of Newton method ⋮ Adaptive regularization with cubics on manifolds ⋮ Decentralized and parallel primal and dual accelerated methods for stochastic convex programming problems ⋮ A concise second-order complexity analysis for unconstrained optimization using high-order regularized models ⋮ Error estimates for iterative algorithms for minimizing regularized quadratic subproblems ⋮ An accelerated first-order method with complexity analysis for solving cubic regularization subproblems ⋮ Adaptive regularization for nonconvex optimization using inexact function values and randomly perturbed derivatives ⋮ Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization ⋮ Unified Acceleration of High-Order Algorithms under General Hölder Continuity
Uses Software
Cites Work
- A linear-time algorithm for trust region problems
- 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
- On solving trust-region and other regularised subproblems in optimization
- Introductory lectures on convex optimization. A basic course.
- Cubic regularization of Newton method and its global performance
- On the use of iterative methods in cubic regularization for unconstrained optimization
- Fast Curvature Matrix-Vector Products for Second-Order Gradient Descent
- A Subspace Minimization Method for the Trust-Region Step
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
- Trust Region Methods
- Globally Solving the Trust Region Subproblem Using Simple First-Order Methods
- Accelerated Methods for NonConvex Optimization
- Optimization Methods for Large-Scale Machine Learning
- Solving the Trust-Region Subproblem using the Lanczos Method
- Finding approximate local minima faster than gradient descent
- Tight query complexity lower bounds for PCA via finite sample deformed wigner law
- A Second-Order Cone Based Approach for Solving the Trust-Region Subproblem and Its Variants
- On the Generalized Lanczos Trust-Region Method
- Affine conjugate adaptive Newton methods for nonlinear elastomechanics
- Some methods of speeding up the convergence of iteration methods
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step
