Accelerated methods for nonconvex optimization
From MaRDI portal
Abstract: We present an accelerated gradient method for non-convex optimization problems with Lipschitz continuous first and second derivatives. The method requires time to find an -stationary point, meaning a point such that . The method improves upon the complexity of gradient descent and provides the additional second-order guarantee that for the computed . Furthermore, our method is Hessian free, i.e. it only requires gradient computations, and is therefore suitable for large scale applications.
Recommendations
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Lower bounds for finding stationary points II: first-order methods
- Newton-type methods for non-convex optimization under inexact Hessian information
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
Cites work
- A linear-time algorithm for trust region problems
- A note on the complexity of \(L _{p }\) minimization
- A second-order cone based approach for solving the trust-region subproblem and its variants
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Accelerated methods for nonconvex optimization
- Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization
- Adaptive cubic regularisation methods for unconstrained optimization. I: Motivation, convergence and numerical results
- Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
- Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
- Cubic regularization of Newton method and its global performance
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Fast Curvature Matrix-Vector Products for Second-Order Gradient Descent
- Finding approximate local minima faster than gradient descent
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- Introductory lectures on convex optimization. A basic course.
- Linear coupling: an ultimate unification of gradient and mirror descent
- On the complexity of approximating a KKT point of quadratic programming
- On the use of iterative methods in cubic regularization for unconstrained optimization
- Random Fields and Geometry
- Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
- Some NP-complete problems in quadratic and nonlinear programming
- Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming
- Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
Cited in
(96)- Accelerations for a variety of global optimization methods
- The global optimization geometry of shallow linear neural networks
- Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems
- An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
- A FISTA-type accelerated gradient algorithm for solving smooth nonconvex composite optimization problems
- An adaptive high order method for finding third-order critical points of nonconvex optimization
- Accelerated methods with fastly vanishing subgradients for structured non-smooth minimization
- Accelerated inexact composite gradient methods for nonconvex spectral optimization problems
- A regularization interpretation of the proximal point method for weakly convex functions
- An efficient adaptive accelerated inexact proximal point method for solving linearly constrained nonconvex composite problems
- Lower bounds for finding stationary points I
- Optimization for deep learning: an overview
- Lower bounds for finding stationary points II: first-order methods
- Second-order guarantees in centralized, federated and decentralized nonconvex optimization
- A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds
- A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization
- Combining stochastic adaptive cubic regularization with negative curvature for nonconvex optimization
- Provable accelerated gradient method for nonconvex low rank optimization
- Accelerated first-order methods for large-scale convex optimization: nearly optimal complexity under strong convexity
- Optimality condition and complexity analysis for linearly-constrained optimization without differentiability on the boundary
- Accelerated randomized mirror descent algorithms for composite non-strongly convex optimization
- Behavior of accelerated gradient methods near critical points of nonconvex functions
- Acceleration method for convex optimization over the fixed point set of a nonexpansive mapping
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Accelerated gradient methods for nonconvex nonlinear and stochastic programming
- Superfast second-order methods for unconstrained convex optimization
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- Inexact accelerated high-order proximal-point methods
- Classical algebraic geometry. Abstracts from the workshop held June 20--26, 2021 (hybrid meeting)
- Zeroth-order nonconvex stochastic optimization: handling constraints, high dimensionality, and saddle points
- Adaptive quadratically regularized Newton method for Riemannian optimization
- Accelerating Proximal Markov Chain Monte Carlo by Using an Explicit Stabilized Method
- scientific article; zbMATH DE number 7449564 (Why is no real title available?)
- scientific article; zbMATH DE number 16627 (Why is no real title available?)
- Katyusha: the first direct acceleration of stochastic gradient methods
- Accelerated methods for nonconvex optimization
- A Newton-based method for nonconvex optimization with fast evasion of saddle points
- Universal Regularization Methods: Varying the Power, the Smoothness and the Accuracy
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Lower bounds for parallel and randomized convex optimization
- On stationary-point hitting time and ergodicity of stochastic gradient Langevin dynamics
- Stochastic nested variance reduction for nonconvex optimization
- Inexact high-order proximal-point methods with auxiliary search procedure
- Convex Synthesis of Accelerated Gradient Algorithms
- Extending the Step-Size Restriction for Gradient Descent to Avoid Strict Saddle Points
- Global convergence of stochastic gradient Hamiltonian Monte Carlo for nonconvex stochastic optimization: nonasymptotic performance bounds and momentum-based acceleration
- Running Primal-Dual Gradient Method for Time-Varying Nonconvex Problems
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- Accelerated Schemes for the $L_1/L_2$ Minimization
- First-Order Methods for Nonconvex Quadratic Minimization
- Second-order guarantees of distributed gradient algorithms
- An average curvature accelerated composite gradient method for nonconvex smooth composite optimization problems
- Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem
- Convergence of Newton-MR under inexact Hessian information
- scientific article; zbMATH DE number 7306906 (Why is no real title available?)
- An Accelerated Inexact Proximal Point Method for Solving Nonconvex-Concave Min-Max Problems
- Stochastic variance-reduced cubic regularization methods
- Sharp worst-case evaluation complexity bounds for arbitrary-order nonconvex optimization with inexpensive constraints
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs
- Accelerated Stochastic Algorithms for Nonconvex Finite-Sum and Multiblock Optimization
- Trust-region Newton-CG with strong second-order complexity guarantees for nonconvex optimization
- Stochastic proximal linear method for structured non-convex problems
- Higher-order methods for convex-concave min-max optimization and monotone variational inequalities
- Lower bounds for non-convex stochastic optimization
- Worst-Case Complexity of TRACE with Inexact Subproblem Solutions for Nonconvex Smooth Optimization
- Accelerated First-Order Methods for Convex Optimization with Locally Lipschitz Continuous Gradient
- A modified PRP-type conjugate gradient algorithm with complexity analysis and its application to image restoration problems
- Inertial projected gradient method for large-scale topology 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
- A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
- Average curvature FISTA for nonconvex smooth composite optimization problems
- Optimizing mean field spin glasses with external field
- A sub-sampled tensor method for nonconvex optimization
- Recent Theoretical Advances in Non-Convex Optimization
- Parameter-free accelerated gradient descent for nonconvex minimization
- Advancing neural network calibration: the role of gradient decay in large-margin Softmax optimization
- Complexity-optimal and parameter-free first-order methods for finding stationary points of composite optimization problems
- Efficient first order method for saddle point problems with higher order smoothness
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- Accelerated optimization landscape of linear-quadratic regulator
- Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
- 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
- Gradient tracking for sum-of-nonconvex decentralized optimization
- Efficient parameter-free restarted accelerated gradient methods for convex and strongly convex optimization
- Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
- Efficiently escaping saddle points in bilevel optimization
- Faster perturbed stochastic gradient methods for finding local minima
- Nesterov's acceleration at the limit: first-order schemes
- Exploiting negative curvature in conjunction with adaptive sampling: theoretical results and a practical algorithm
- On the convergence of SignSGD under weak first- and second-order gradient Lipschitz
- Settling the complexity of Nash equilibrium in congestion games
This page was built for publication: Accelerated methods for nonconvex optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4571877)
