# Learning to Guide Random Search

arXiv: https://arxiv.org/abs/2004.12214 · HTML: https://mlsanity.com/paper/2004.12214/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2020.

## Built on by (most cited first, 13 of 13)

- [Pareto Set Learning for Expensive Multi-Objective Optimization](https://mlsanity.com/paper/2210.08495/) (2022)
- [Megaverse: Simulating Embodied Agents at One Million Experiences per Second](https://mlsanity.com/paper/2107.08170/) (2021)
- [Harmony in Divergence: Towards Fast, Accurate, and Memory-efficient Zeroth-order LLM Fine-tuning](https://mlsanity.com/paper/2502.03304/) (2025)
- [Generalizing Gaussian Smoothing for Random Search](https://mlsanity.com/paper/2211.14721/) (2022)
- [Continuation Path Learning for Homotopy Optimization](https://mlsanity.com/paper/2307.12551/) (2023)
- [Perturbation-efficient Zeroth-order Optimization for Hardware-friendly On-device Training](https://mlsanity.com/paper/2504.20314/) (2025)
- [Dimensionality Reduction and Prioritized Exploration for Policy Search](https://mlsanity.com/paper/2203.04791/) (2022)
- [Domain Generalization without Excess Empirical Risk](https://mlsanity.com/paper/2308.15856/) (2023)
- [Towards Fast LLM Fine-tuning through Zeroth-Order Optimization with Projected Gradient-Aligned Perturbations](https://mlsanity.com/paper/2510.18228/) (2025)
- [Zeroth-Order Actor-Critic: An Evolutionary Framework for Sequential Decision Problems](https://mlsanity.com/paper/2201.12518/) (2022)
- [Stochastic Two Points Method for Deep Model Zeroth-order Optimization](https://mlsanity.com/paper/2402.01621/) (2024)
- [Efficient On-Policy Reinforcement Learning via Exploration of Sparse Parameter Space](https://mlsanity.com/paper/2509.25876/) (2025)
- [Constraint-Bound Agnostic Bayesian Optimization: One Model for All Thresholds](https://mlsanity.com/paper/2607.23448/) (2026)

## Abstract (arXiv)

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.