Noisy Blackbox Optimization using Multi-fidelity Queries: A Tree Search Approach

Rajat Sen, Kirthevasan Kandasamy, Sanjay ShakkottaiAISTATS 2019 · OpenReview

Abstract

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. We propose MFHOO and MFPOO, two tree-search algorithms designed to optimize expensive functions by leveraging cheap, low-fidelity approximations. Unlike previous methods, these algorithms are specifically built to handle evaluations that are both noisy and biased, providing strong theoretical guarantees and outperforming state-of-the-art Bayesian optimization techniques in real-world tuning tasks.

Introduction

Optimizing complex systems—such as tuning the hyper-parameters of a deep neural network—is notoriously expensive. A single evaluation (training a model to completion) can take days. To speed this up, researchers often use "multi-fidelity" queries: instead of training on the full dataset, they might train on a small sub-sample.

While these sub-sampled queries are much cheaper, they introduce two major challenges:

  1. Bias: The validation error on a sub-sample is a biased estimate of the error on the full dataset.
  2. Noise: Stochasticity in data sampling and optimization (like SGD) adds random noise to the result.

Existing tree-search methods for optimization either ignored noise or didn't account for the cost-benefit trade-off of multiple fidelities. This paper fills that gap by providing a framework that intelligently decides when to use cheap, low-fidelity queries and when to invest in expensive, high-fidelity ones.

Methodology

The authors use a hierarchical partitioning approach, representing the search space as a binary tree where each node is a sub-region of the space.

  • MFHOO (Multi-Fidelity Hierarchical Optimistic Optimization): This core algorithm navigates the tree by calculating an upper confidence bound (UCB) for each node. Crucially, it ties the fidelity of a query to the depth of the tree. Shallow nodes (large regions) are queried at low fidelity, while deeper nodes (refined regions) are queried at higher fidelity. This prevents wasting budget on high-fidelity evaluations in regions that are clearly sub-optimal.
  • MFPOO (Multi-Fidelity Parallel Optimistic Optimization): Since the "smoothness" of the function is rarely known in practice, MFPOO spawns multiple instances of MFHOO with different smoothness assumptions in parallel, ensuring that at least one instance achieves near-optimal performance.

Experimental Evaluation

The algorithms were evaluated on a variety of benchmarks:

  1. Synthetic Functions: Standard test-beds like Hartmann3, Hartmann6, Branin, and CurinExp, modified to include multi-fidelity bias and noise.
  2. Real-World ML Tuning: Tuning XGBoost (MNIST and Solar-Radiation datasets), SVM (20-News Group dataset), and a ConvNet (CIFAR-10 dataset with 6 hyper-parameters).

Key Results and Insights

The most elegant idea presented is Fidelity-Depth Coupling. If you are still exploring a large, coarse region of the search space, a cheap, biased estimate is "good enough" to decide if that region is worth further investigation. This paper proves that the tree-search structure is robust enough to handle the cumulative error of both noise and bias, provided the fidelity increases appropriately as you descend the tree.

Comprehensive performance comparison across synthetic and real-world benchmarks.

In almost all tests, MFPOO outperformed state-of-the-art methods like BOCA, MF-GP-UCB, and standard Bayesian Optimization (GP-EI). The authors prove "simple regret" bounds, showing that the gap between the algorithm's choice and the true optimum shrinks at a predictable rate as the total budget increases.

Validation accuracy vs. wall-clock time for the CIFAR-10 deep learning task.

On the CIFAR-10 ConvNet task, MFPOO reached a higher validation accuracy significantly faster than its competitors. It outperformed the standard POO algorithm (which only uses high-fidelity queries) because it could explore many more configurations using the same time budget.

Conclusion

While MFPOO is highly effective, it currently assumes a parametric form for the bias function. Future work could explore more flexible, non-parametric ways to handle unknown bias. Additionally, the performance is somewhat dependent on how the search space is partitioned; if the optimal point lies on a partition edge, convergence may slow. Future research may also investigate more adaptive strategies where fidelity is decided based on local confidence rather than strictly by tree depth.

Summary updated

Abstract

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-par...
BibTeX
@inproceedings{sen2019noisy,
  author = {Rajat Sen and Kirthevasan Kandasamy and Sanjay Shakkottai},
  title = {{Noisy Blackbox Optimization using Multi-fidelity Queries: A Tree Search Approach}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=mKOcb2VL_Tz},
}
Figure