Efficient approaches for escaping higher order saddle points in non-convex optimization

Abstract

Local search heuristics for non-convex optimizations are popular in applied machine learning. However, in general it is hard to guarantee that such algorithms even converge to a local minimum, due to the existence of complicated saddle point structures in high dimensions. Many functions have degenerate saddle points such that the first and second order derivatives cannot distinguish them with local optima. In this paper we use higher order derivatives to escape these saddle points: we design the first efficient algorithm guaranteed to converge to a third order local optimum (while existing techniques are at most second order). We also show that it is NP-hard to extend this further to finding fourth order local optima.

Cited by in corpus (36)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Entropy-SGD: Biasing Gradient Descent Into Wide Valleys
• A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics
• Towards Theoretically Understanding Why SGD Generalizes Better Than ADAM in Deep Learning
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• On Interpretability of Artificial Neural Networks: A Survey
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Optimization Landscape of Tucker Decomposition
• Finding Local Minima via Stochastic Nested Variance Reduction
• Distributed Stochastic Gradient Descent: Nonconvexity, Nonsmoothness, and Convergence to Local Minima
• Symmetry, Saddle Points, and Global Optimization Landscape of Nonconvex Matrix Factorization
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• Deep Neural Networks with Multi-Branch Architectures Are Less Non-Convex
• Matrix Completion and Related Problems via Strong Duality
• DANTE: Deep AlterNations for Training nEural networks
• NeCPD: An Online Tensor Decomposition with Optimal Stochastic Gradient Descent
• On the Learnability of Deep Random Networks
• Complexity aspects of local minima and related notions
• Third-order Smoothness Helps: Even Faster Stochastic Optimization Algorithms for Finding Local Minima
• Ill-Posedness and Optimization Geometry for Nonlinear Neural Network Training
• A Conservation Law Method in Optimization
• On The Geometric Analysis of A Quartic-quadratic Optimization Problem under A Spherical Constraint
• Are Saddles Good Enough for Deep Learning?
• Landscape Correspondence of Empirical and Population Risks in the Eigendecomposition Problem
• Tensor decompositions and algorithms, with applications to tensor learning
• Escaping Saddle Points with Stochastically Controlled Stochastic Gradient Methods
• Stochastic Learning in Potential Games: Communication and Payoff-Based Approaches
• Reannealing of Decaying Exploration Based On Heuristic Measure in Deep Q-Network
• Effective Proximal Methods for Non-convex Non-smooth Regularized Learning
• Stochastic Approximation for Online Tensorial Independent Component Analysis
• One-dimensional System Arising in Stochastic Gradient Descent
• Recovering the Lowest Layer of Deep Networks with High Threshold Activations
• Escaping Saddle Points with Compressed SGD
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• Complexity Aspects of Fundamental Questions in Polynomial Optimization
• A Comprehensive Study on Optimization Strategies for Gradient Descent In Deep Learning