Finding approximate local minima faster than gradient descent
From MaRDI portal
Abstract: We design a non-convex second-order optimization algorithm that is guaranteed to return an approximate local minimum in time which scales linearly in the underlying dimension and the number of training examples. The time complexity of our algorithm to find an approximate local minimum is even faster than that of gradient descent to find a critical point. Our algorithm applies to a general class of optimization problems including training a neural network and other non-convex objectives arising in machine learning.
Recommendations
- A batch, derivative-free algorithm for finding multiple local minima
- Gradient-only approaches to avoid spurious local minima in unconstrained optimization
- Accelerated gradient descent methods with line search
- Performance of approximate algorithms for global minimization
- scientific article; zbMATH DE number 94238
- Finding local optima of high-dimensional functions using direct search methods
- scientific article; zbMATH DE number 2206820
- A descent gradient method and its global convergence
- Accelerated gradient sliding for minimizing a sum of functions
- Fast Cadzow's algorithm and a gradient variant
Cited in
(54)- The global optimization geometry of shallow linear neural networks
- Minimizing uniformly convex functions by cubic regularization of Newton method
- Adaptive regularization with cubics on manifolds
- An accelerated first-order method with complexity analysis for solving cubic regularization subproblems
- Newton-type methods for non-convex optimization under inexact Hessian information
- Lower bounds for finding stationary points I
- 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
- Approximating the nearest stable discrete-time system
- Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation
- Adaptive quadratically regularized Newton method for Riemannian optimization
- 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
- Second-order stochastic optimization for machine learning in linear time
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Stochastic nested variance reduction for nonconvex optimization
- Matrix completion and related problems via strong duality
- One-dimensional system arising in stochastic gradient descent
- Why Do Local Methods Solve Nonconvex Problems?
- Escaping strict saddle points of the Moreau envelope in nonsmooth optimization
- First-Order Methods for Nonconvex Quadratic Minimization
- Second-order guarantees of distributed gradient algorithms
- Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem
- scientific article; zbMATH DE number 7306906 (Why is no real title available?)
- A concise second-order complexity analysis for unconstrained optimization using high-order regularized models
- Non-convex matrix completion and related problems via strong duality
- Stochastic variance-reduced cubic regularization methods
- Gradient descent finds the cubic-regularized nonconvex Newton step
- Kernel approximation methods for speech recognition
- 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
- A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
- A Newton-CG Based Augmented Lagrangian Method for Finding a Second-Order Stationary Point of Nonconvex Equality Constrained Optimization with Complexity Guarantees
- Optimizing mean field spin glasses with external field
- Recent Theoretical Advances in Non-Convex Optimization
- Parameter-free accelerated gradient descent for nonconvex minimization
- A deterministic gradient-based approach to avoid saddle points
- A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization
- Hessian barrier algorithms for non-convex conic optimization
- Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
- Homogeneous second-order descent framework: a fast alternative to Newton-type methods
- Near-optimal nonconvex-strongly-convex bilevel optimization with fully first-order oracles
- A randomized algorithm for nonconvex minimization with inexact evaluations and complexity guarantees
- Riemannian adaptive regularized Newton methods with Hölder continuous Hessians
- Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
- Efficiently escaping saddle points in bilevel optimization
- Last-iterate convergence rates for min-max optimization: convergence of Hamiltonian gradient descent and consensus optimization
- Faster perturbed stochastic gradient methods for finding local minima
This page was built for publication: Finding approximate local minima faster than gradient descent
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978058)
