# Noisy Blackbox Optimization with Multi-Fidelity Queries: A Tree Search Approach

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2018.

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

- [VolcanoML: Speeding up End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2107.08861/) (2021)
- [Hyper-Tune: Towards Efficient Hyper-parameter Tuning at Scale](https://mlsanity.com/paper/2201.06834/) (2022)
- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [Certified Multi-Fidelity Zeroth-Order Optimization](https://mlsanity.com/paper/2308.00978/) (2023)
- [Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-Fidelity Feedback](https://mlsanity.com/paper/2110.07232/) (2021)
- [Adaptive multi-fidelity optimization with fast learning rates](https://mlsanity.com/paper/2604.16239/) (2026)
- [Two-Fidelity Best-Action Identification for Stochastic Minimax Tree](https://mlsanity.com/paper/2606.01708/) (2026)
- [Efficient End-to-End AutoML via Scalable Search Space Decomposition](https://mlsanity.com/paper/2206.09423/) (2022)
- [FlexHB: a More Efficient and Flexible Framework for Hyperparameter Optimization](https://mlsanity.com/paper/2402.13641/) (2024)

## Abstract (arXiv)

We study the problem of black-box optimization of a noisy function in the presence of low-cost approximations or fidelities, which is motivated by problems like hyper-parameter tuning. In hyper-parameter tuning evaluating the black-box function at a point involves training a learning algorithm on a large data-set at a particular hyper-parameter and evaluating the validation error. Even a single such evaluation can be prohibitively expensive. Therefore, it is beneficial to use low-cost approximations, like training the learning algorithm on a sub-sampled version of the whole data-set. These low-cost approximations/fidelities can however provide a biased and noisy estimate of the function value. In this work, we incorporate the multi-fidelity setup in the powerful framework of noisy black-box optimization through tree-like hierarchical partitions. We propose a multi-fidelity bandit based tree-search algorithm for the problem and provide simple regret bounds for our algorithm. Finally, we validate the performance of our algorithm on real and synthetic datasets, where it outperforms several benchmarks.