Efficiently avoiding saddle points with zero order methods: No gradients required

Abstract

We consider the case of derivative-free algorithms for non-convex optimization, also known as zero order algorithms, that use only function evaluations rather than gradients. For a wide variety of gradient approximators based on finite differences, we establish asymptotic convergence to second order stationary points using a carefully tailored application of the Stable Manifold Theorem. Regarding efficiency, we introduce a noisy zero-order method that converges to second order stationary points, i.e avoids saddle points. Our algorithm uses only $\tilde{\mathcal{O}}(1/{\epsilon }^2)$ approximate gradient calculations and, thus, it matches the converge rate guarantees of their exact gradient counterparts up to constants. In contrast to previous work, our convergence rate analysis avoids imposing additional dimension dependent slowdowns in the number of iterations required for non-convex zero order optimization.

To appear in NeurIPS 2019

References in corpus (10)

• ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models
• Evolution Strategies as a Scalable Alternative to Reinforcement Learning
• The Loss Surfaces of Multilayer Networks
• Bandit Convex Optimization for Scalable and Dynamic IoT Management
• Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization
• A Comprehensive Linear Speedup Analysis for Asynchronous Stochastic Parallel Optimization from Zeroth-Order to First-Order
• The Power of Normalization: Faster Evasion of Saddle Points
• Neon2: Finding Local Minima via First-Order Oracles
• On the Local Minima of the Empirical Risk
• Zeroth-order Asynchronous Doubly Stochastic Algorithm with Variance Reduction

Cited by in corpus (3)

• Min-Max Optimization without Gradients: Convergence and Applications to Adversarial ML
• Escaping Saddle-Points Faster under Interpolation-like Conditions
• Stochastic Gradient Langevin Dynamics with Variance Reduction