# From Random Search to Bandit Learning in Metric Measure Spaces

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 19 May 2023.

## Builds on (most cited first, 13 of 13)

- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Contextual Bandits with Continuous Actions: Smoothing, Zooming, and Adapting](https://mlsanity.com/paper/1902.01520/) (2019)
- [Lipschitz Bandits with Batched Feedback](https://mlsanity.com/paper/2110.09722/) (2021)
- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [A Lipschitz Bandits Approach for Continuous Hyperparameter Optimization](https://mlsanity.com/paper/2302.01539/) (2023)
- [Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning](https://mlsanity.com/paper/2006.12367/) (2020)
- [Nonparametric Contextual Bandits in an Unknown Metric Space](https://mlsanity.com/paper/1908.01228/) (2019)
- [Bandits for BMO Functions](https://mlsanity.com/paper/2007.08703/) (2020)

## Abstract (arXiv)

Random Search is one of the most widely-used method for Hyperparameter Optimization, and is critical to the success of deep learning models. Despite its astonishing performance, little non-heuristic theory has been developed to describe the underlying working mechanism. This paper gives a theoretical accounting of Random Search. We introduce the concept of scattering dimension that describes the landscape of the underlying function, and quantifies the performance of random search. We show that, when the environment is noise-free, the output of random search converges to the optimal value in probability at rate  widetildeO left( left( frac1T right)^ frac1ds  right) , where  ds ≥ 0  is the scattering dimension of the underlying function. When the observed function values are corrupted by bounded iid noise, the output of random search converges to the optimal value in probability at rate  widetildeO left( left( frac1T right)^ frac1ds + 1  right) . In addition, based on the principles of random search, we introduce an algorithm, called BLiN-MOS, for Lipschitz bandits in doubling metric spaces that are also endowed with a probability measure, and show that under mild conditions, BLiN-MOS achieves a regret rate of order  widetildeO left( T^ fracdzdz + 1  right) , where dz is the zooming dimension of the problem instance.