On the Second-order Convergence Properties of Random Search Methods Aurelien Lucchi Antonio Orvieto Adamos Solomou Department of Computer Science ETH Zurich

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.