Learning to Guide Random Search
This addresses the high sample complexity problem in derivative-free optimization for high-dimensional continuous control and optimization benchmarks, representing a novel method for a known bottleneck.
The paper tackles derivative-free optimization of high-dimensional functions by exploiting that many datasets lie on low-dimensional manifolds, developing an online learning approach that jointly learns the manifold and optimizes the function, achieving significantly lower sample complexity than existing methods like Augmented Random Search and CMA-ES.
We are interested in derivative-free optimization of high-dimensional functions. The sample complexity of existing methods is high and depends on problem dimensionality, unlike the dimensionality-independent rates of first-order methods. The recent success of deep learning suggests that many datasets lie on low-dimensional manifolds that can be represented by deep nonlinear models. We therefore consider derivative-free optimization of a high-dimensional function that lies on a latent low-dimensional manifold. We develop an online learning approach that learns this manifold while performing the optimization. In other words, we jointly learn the manifold and optimize the function. Our analysis suggests that the presented method significantly reduces sample complexity. We empirically evaluate the method on continuous optimization benchmarks and high-dimensional continuous control problems. Our method achieves significantly lower sample complexity than Augmented Random Search, Bayesian optimization, covariance matrix adaptation (CMA-ES), and other derivative-free optimization algorithms.