  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.
