Finding approximate local minima faster than gradient descent

DOI10.1145/3055399.3055464zbMath1369.68290arXiv1611.01146OpenAlexW2609037894MaRDI QIDQ4978058

Tengyu Ma, Naman Agarwal, Brian Bullins, Zeyuan Allen Zhu, Elad Hazan

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.01146

zbMATH Keywords

nonconvex optimization deep learning cubic regularization second-order optimization

Mathematics Subject Classification ID

Nonconvex programming, global optimization (90C26) Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (40)

Adaptive Quadratically Regularized Newton Method for Riemannian Optimization ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Accelerated Methods for NonConvex Optimization ⋮ Escaping Strict Saddle Points of the Moreau Envelope in Nonsmooth Optimization ⋮ Cubic regularization methods with second-order complexity guarantee based on a new subproblem reformulation ⋮ Approximating the nearest stable discrete-time system ⋮ Unnamed Item ⋮ 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 ⋮ First-Order Methods for Nonconvex Quadratic Minimization ⋮ Optimizing mean field spin glasses with external field ⋮ Newton-type methods for non-convex optimization under inexact Hessian information ⋮ Lower bounds for finding stationary points I ⋮ A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points ⋮ Second-Order Guarantees of Distributed Gradient Algorithms ⋮ Recent Theoretical Advances in Non-Convex Optimization ⋮ Lower bounds for finding stationary points II: first-order methods ⋮ Solving Large-Scale Cubic Regularization by a Generalized Eigenvalue Problem ⋮ Complexity Analysis of Second-Order Line-Search Algorithms for Smooth Nonconvex Optimization ⋮ The global optimization geometry of shallow linear neural networks ⋮ Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points ⋮ Unnamed Item ⋮ Minimizing uniformly convex functions by cubic regularization of Newton method ⋮ A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds ⋮ Adaptive regularization with cubics on manifolds ⋮ A concise second-order complexity analysis for unconstrained optimization using high-order regularized models ⋮ An accelerated first-order method with complexity analysis for solving cubic regularization subproblems ⋮ 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 ⋮ Unnamed Item ⋮ Gradient Descent Finds the Cubic-Regularized Nonconvex Newton Step ⋮ Unnamed Item ⋮ Trust-Region Newton-CG with Strong Second-Order Complexity Guarantees for Nonconvex Optimization ⋮ Stochastic proximal linear method for structured non-convex problems ⋮ Unnamed Item ⋮ One-dimensional system arising in stochastic gradient descent ⋮ Higher-Order Methods for Convex-Concave Min-Max Optimization and Monotone Variational Inequalities

This page was built for publication: Finding approximate local minima faster than gradient descent