Bayesian Optimization in a Billion Dimensions via Random Embeddings

By Ziyun Wang, Masrour Zoghi, Frank Hutter, David Matheson, Nando de Freitas. Journal of Artificial Intelligence Research, 2013

551 citations recorded by the source corpus.

Bayesian optimization techniques have been successfully applied to robotics, planning, sensor placement, recommendation, advertising, intelligent user interfaces and automatic algorithm configuration. Despite these successes, the approach is restricted to problems of moderate dimension, and several workshops on Bayesian optimization have identified its scaling to high-dimensions as one of the holy grails of the field. In this paper, we introduce a novel random embedding idea to attack this problem. The resulting Random EMbedding Bayesian Optimization (REMBO) algorithm is very simple, has important invariance properties, and applies to domains with both categorical and continuous variables. We present a thorough theoretical analysis of REMBO. Empirical results confirm that REMBO can effectively solve problems with billions of dimensions, provided the intrinsic dimensionality is low. They also show that REMBO achieves state-of-the-art performance in optimizing the 47 discrete parameters of a popular mixed integer linear programming solver.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3c5bda56f8bc81f267faa73c152437552d3c7ca3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Black-Box Tuning for Language-Model-as-a-Service (2022, methodology): “Previous work (Wang et al., 2016; Qian et al., 2016; Letham et al., 2020) in derivativefree optimization usually sets each entry in the random matrix A by sampling from some normal distribution.”
BoTorch: Programmable Bayesian Optimization in PyTorch (2019, methodology): “• A simple and ﬂexible formulation of the Knowledge Gradient—a powerful look-ahead algorithm known for being difﬁcult to implement — with improved performance over the state-of-the-art (Wu & Frazier, 2016).”
BayesOpt: a Bayesian optimization library for nonlinear optimization, experimental design and bandits (2014, methodology): “We also provide a method for optimization in high-dimensional spaces (Wang et al., 2013).”
Bayesian Optimization for Categorical and Category-Specific Continuous Inputs (2019, unknown): “A possible example of k ( c, c (cid:48) ) is Hamming kernel that was used by (Wang et al. 2016).”
A Tutorial on Bayesian Optimization (2018, methodology): “Directions for research include developing statistical methods that identify and leverage structure present in high-dimensional objectives arising in practice, which has been pursued by recent work including Wang et al. (2013, 2016b); Kandasamy et al. (2015).”
Towards Automatically-Tuned Neural Networks (2016, methodology): “Adapting GPs to handle these characteristics is an active field of research (Swersky et al., 2013; Wang et al., 2016), but so far Bayesian optimization methods using tree-based models (Hutter et al.”
Scalable Global Optimization via Local Bayesian Optimization (2019, background): “Therefore, a small sample budget may suffice, which allows to run p invocations in parallel, following [51].”
Recent Advances in Bayesian Optimization (2022, background): “Note that the number of dimensions in BO may vary from dozens to thousands or even one billion [191].”
An Evolutionary Algorithm for Large-Scale Sparse Multiobjective Optimization Problems (2020, methodology): “…search space of LOPs, they cannot be easily solved by general evolutionary algorithms, hence some novel techniques have been adopted to tackle speciﬁc types of LOPs, such as variable interaction analysis [32]–[34], linkage learning [35], and random embedding-based Bayesian optimization [36], [37].”
Constrained Bayesian Optimization for Automatic Chemical Design (2017, unknown): “LP) [126, 129] and Statistical Machine Translation (SMT) [4], Robotics and Reinforcement Learning [67, 78, 77, 17, 12], Combinatorial Optimization problems such as the tuning of mixed integer solvers [46, 127, 125] and nearest neighbour algorithms [75] and interactive interfaces for preference learn”
Hyperparameter optimization: Foundations, algorithms, best practices, and open challenges (2021, background): “Extensions for mixed-hierarchical spaces that are based on special kernels (Swersky et al., 2014) exist, and the use of random embed-dings has been suggested for high-dimensional spaces (Nayebi et al., 2019; Wang et al., 2016).”
Gaussian Processes for history-matching: application to an unconventional gas reservoir (2017, methodology): “Meanwhile, if the intrinsic dimensionality is low, sensitivity analysis and dimension reduction techniques can be used to reduce the number of variables in [61].”
Learning Decision Trees with Reinforcement Learning (2017, methodology): “Bayesian optimization refines its choices sequentially via Bayesian posterior updating as more data is observed, which has been widely applied in hyper-parameter optimization [4, 9, 13, 16].”