# Predicting the utility of search spaces for black-box optimization: a simple, budget-aware approach

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 45 references that are in the map.
- First posted on arXiv 15 Dec 2021.

## Builds on (most cited first, 30 of 31)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Wide Residual Networks](https://mlsanity.com/paper/1605.07146/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [One Billion Word Benchmark for Measuring Progress in Statistical Language Modeling](https://mlsanity.com/paper/1312.3005/) (2013)
- [Are GANs Created Equal? A Large-Scale Study](https://mlsanity.com/paper/1711.10337/) (2017)
- [Predictive Entropy Search for Efficient Global Optimization of Black-box Functions](https://mlsanity.com/paper/1406.2541/) (2014)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020](https://mlsanity.com/paper/2104.10201/) (2021)
- [Bayesian Optimization with Unknown Constraints](https://mlsanity.com/paper/1403.5607/) (2014)
- [On the State of the Art of Evaluation in Neural Language Models](https://mlsanity.com/paper/1707.05589/) (2017)
- [On Empirical Comparisons of Optimizers for Deep Learning](https://mlsanity.com/paper/1910.05446/) (2019)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search](https://mlsanity.com/paper/2007.00708/) (2020)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Hyperparameter Importance Across Datasets](https://mlsanity.com/paper/1710.04725/) (2017)
- [A General Framework for Constrained Bayesian Optimization using Information-based Search](https://mlsanity.com/paper/1511.09422/) (2015)
- [Learning search spaces for Bayesian optimization: Another view of hyperparameter transfer learning](https://mlsanity.com/paper/1909.12552/) (2019)
- [Parallel Bayesian Global Optimization of Expensive Functions](https://mlsanity.com/paper/1602.05149/) (2016)
- [Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions](https://mlsanity.com/paper/1511.07130/) (2015)
- [An Analysis of Neural Language Modeling at Multiple Scales](https://mlsanity.com/paper/1803.08240/) (2018)
- [Optimization, fast and slow: optimally switching between local and Bayesian optimization](https://mlsanity.com/paper/1805.08610/) (2018)
- [A Large Batch Optimizer Reality Check: Traditional, Generic Optimizers Suffice Across Batch Sizes](https://mlsanity.com/paper/2102.06356/) (2021)
- [Unbounded Bayesian Optimization via Regularization](https://mlsanity.com/paper/1508.03666/) (2015)
- [Hyperparameter Transfer Across Developer Adjustments](https://mlsanity.com/paper/2010.13117/) (2020)
- [Heteroscedastic Treed Bayesian Optimisation](https://mlsanity.com/paper/1410.7172/) (2014)
- [Sub-linear Regret Bounds for Bayesian Optimisation in Unknown Search Spaces](https://mlsanity.com/paper/2009.02539/) (2020)

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

- [Show Your Work with Confidence: Confidence Bands for Tuning Curves](https://mlsanity.com/paper/2311.09480/) (2023)
- [How far away are truly hyperparameter-free learning algorithms?](https://mlsanity.com/paper/2505.24005/) (2025)

## Abstract (arXiv)

Black box optimization requires specifying a search space to explore for solutions, e.g. a d-dimensional compact space, and this choice is critical for getting the best results at a reasonable budget. Unfortunately, determining a high quality search space can be challenging in many applications. For example, when tuning hyperparameters for machine learning pipelines on a new problem given a limited budget, one must strike a balance between excluding potentially promising regions and keeping the search space small enough to be tractable. The goal of this work is to motivate -- through example applications in tuning deep neural networks -- the problem of predicting the quality of search spaces conditioned on budgets, as well as to provide a simple scoring method based on a utility function applied to a probabilistic response surface model, similar to Bayesian optimization. We show that the method we present can compute meaningful budget-conditional scores in a variety of situations. We also provide experimental evidence that accurate scores can be useful in constructing and pruning search spaces. Ultimately, we believe scoring search spaces should become standard practice in the experimental workflow for deep learning.