Neon2: Finding Local Minima via First-Order Oracles

Abstract

We propose a reduction for non-convex optimization that can (1) turn an stationary-point finding algorithm into an local-minimum finding one, and (2) replace the Hessian-vector product computations with only gradient computations. It works both in the stochastic and the deterministic settings, without hurting the algorithm's performance. As applications, our reduction turns Natasha2 into a first-order method without hurting its performance. It also converts SGD, GD, SCSG, and SVRG into algorithms finding approximate local minima, outperforming some best known results.

version 2 and 3 improve writing

Cited by in corpus (29)

• A Convergence Theory for Deep Learning via Over-Parameterization
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Escaping Saddles with Stochastic Gradients
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization
• Asymmetric Valleys: Beyond Sharp and Flat Local Minima
• Local Saddle Point Optimization: A Curvature Exploitation Approach
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• Stochastic Recursive Variance-Reduced Cubic Regularization Methods
• Finding Local Minima via Stochastic Nested Variance Reduction
• Perturbed Proximal Descent to Escape Saddle Points for Non-convex and Non-smooth Objective Functions
• A Hybrid Stochastic Optimization Framework for Stochastic Composite Nonconvex Optimization
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning
• Efficiently avoiding saddle points with zero order methods: No gradients required
• Escaping Saddle Points Faster with Stochastic Momentum
• Alternating Direction Method of Multipliers for Quantization
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Escape saddle points faster on manifolds via perturbed Riemannian stochastic recursive gradient
• Quickly Finding a Benign Region via Heavy Ball Momentum in Non-Convex Optimization
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• SSRGD: Simple Stochastic Recursive Gradient Descent for Escaping Saddle Points
• Faster Perturbed Stochastic Gradient Methods for Finding Local Minima
• Escaping Saddle Points with Compressed SGD
• The perturbed prox-preconditioned spider algorithm: non-asymptotic convergence bounds
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Exclusive Topic Modeling