On the Second-order Convergence Properties of Random Search Methods

Abstract

We study the theoretical convergence properties of random-search methods when optimizing non-convex objective functions without having access to derivatives. We prove that standard random-search methods that do not rely on second-order information converge to a second-order stationary point. However, they suffer from an exponential complexity in terms of the input dimension of the problem. In order to address this issue, we propose a novel variant of random search that exploits negative curvature by only relying on function evaluations. We prove that this approach converges to a second-order stationary point at a much faster rate than vanilla methods: namely, the complexity in terms of the number of function evaluations is only linear in the problem dimension. We test our algorithm empirically and find good agreements with our theoretical results.

References in corpus (13)

• 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
• No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis
• Simple random search provides a competitive approach to reinforcement learning
• The Noisy Power Method: A Meta Algorithm with Applications
• Escaping Saddles with Stochastic Gradients
• The Power of Normalization: Faster Evasion of Saddle Points
• On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points
• Gradientless Descent: High-Dimensional Zeroth-Order Optimization
• Guided evolutionary strategies: Augmenting random search with surrogate gradients
• Hessian-Aware Zeroth-Order Optimization for Black-Box Adversarial Attack
• On Noisy Negative Curvature Descent: Competing with Gradient Descent for Faster Non-convex Optimization