High Dimensional Bayesian Optimisation and Bandits via Additive Models

By Kirthevasan Kandasamy, Jeff Schneider, Barnab'as P'oczos. 2015

418 citations recorded by the source corpus.

Bayesian Optimisation (BO) is a technique used in optimising a $D$-dimensional function which is typically expensive to evaluate. While there have been many successes for BO in low dimensions, scaling it to high dimensions has been notoriously difficult. Existing literature on the topic are under very restrictive settings. In this paper, we identify two key challenges in this endeavour. We tackle these challenges by assuming an additive structure for the function. This setting is substantially more expressive and contains a richer class of functions than previous work. We prove that, for additive functions the regret has only linear dependence on $D$ even though the function depends on all $D$ dimensions. We also demonstrate several other statistical and computational benefits in our framework. Via synthetic examples, a scientific simulation and a face detection problem we demonstrate that our method outperforms naive BO on additive functions and on several examples where the function is not additive.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

DeepArchitect: Automatically Designing and Training Deep Architectures (2017, background): “There has been a wide variety of theoretical and empirical research in this area [2, 4, 5, 21], including Bayesian optimization methods [12, 14, 24].”
Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization (2016, background): “While the rate of convergence for random search depends on the smoothness and is exponential in the number of dimensions in the search space, the same is true for Bayesian optimization methods without additional structural assumptions (Kandasamy et al., 2015).”
Multi-fidelity Bayesian Optimisation with Continuous Approximations (2017, methodology): “Following the recommendations in Kandasamy et al. (2015) we set it to be of the correct “order”; precisely, β t = 0 .”
AlphaX: eXploring Neural Architectures with Deep Neural Networks and Monte Carlo Tree Search (2019, methodology): “Bayesian Optimization (BO) is a popular method for the hyper-parameter search [12, 36, 41, 14]; It is proven to be an effective black-box optimization technique for small scale problems, e.g. ﬁnding good hyper-parameters for Stochastic Gradient Descent (SGD).”
AutoPrognosis: Automated Clinical Prognostic Modeling via Bayesian Optimization with Structured Kernel Learning (2018, background): “) High-dimensionality renders standard GP-based BO infeasible as both the sample complexity of nonparametric estimation and the computational complexity of maximizing the acquisition function are exponential in D (Györfi et al., 2006; Kandasamy et al., 2015).”
Scalable Global Optimization via Local Bayesian Optimization (2019, methodology): “Many methods exist that exploit potential additive structure in the objective function [25, 15, 52].”
Differentiable Compositional Kernel Learning for Gaussian Processes (2018, methodology): “But simple kernels lead to inefficient exploration due to the curse of dimensionality, leading various researchers to consider additive kernels (Kandasamy et al., 2015; Gardner et al., 2017; Wang et al., 2017).”
Bayesian Optimization for Likelihood-Free Inference of Simulator-Based Statistical Models (2015, background): “ent work, it was assumed that the objective varies along a low dimensional subspace only (Chen et al., 2012; Wang et al., 2013; Djolonga et al., 2013), or that it takes the form of an additive model (Kandasamy et al., 2015). This work and further developments in high-dimensional Bayesian optimizatio”
BoTorch: Programmable Bayesian Optimization in PyTorch (2019, methodology): “Its core is implemented in C++, which provides performance beneﬁts but renders it hard to modify and extend.”
Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining (2020, background): “While recent works have tried to develop models to extend BO to either structured [1, 27, 6, 42] or high-dimensional [25, 39, 18] input spaces, we are not aware of any BO method that can efﬁciently handle the types of high-dimensional and structured spaces considered in this work.”
Recent Advances in Bayesian Optimization (2022, methodology): “An algorithm called Add-GP-UCB was proposed in [94], assuming that the objective function f (x) : X → R with input space X = [0, 1] is a sum of functions of small, disjoint groups of dimensions,”
Asynchronous Parallel Bayesian Optimisation via Thompson Sampling (2017, methodology): “Set Z = − max i X i and Z i = − max j (cid:54) = i X j and using the same argument, we get Here the inequality follows from Theorem 24 and the identity uses Fact 22.”
Gaussian Process Bandit Optimisation with Multi-fidelity Evaluations (2016, background): “This can be alleviated by assuming additional structure in the problem [8, 15].”
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).”
Optimization as Estimation with Gaussian Processes in Bandit Settings (2015, background): “Common assumptions are a low-dimensional or simpler underlying st ructure off [7, 34, 15].”
Parallelised Bayesian Optimisation via Thompson Sampling (2018, methodology): “Following recommendations in [24], we set it βj = 0.”