On the Second-order Convergence Properties of Random Search Methods
This addresses a fundamental bottleneck in derivative-free optimization for non-convex problems, offering a significant theoretical improvement with practical implications for high-dimensional settings.
The paper tackles the problem of optimizing non-convex functions without derivatives using random-search methods, proving that standard methods converge to second-order stationary points but with exponential complexity in dimension, and proposes a novel variant that reduces this complexity to linear while maintaining convergence.
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.