Are Random Decompositions all we need in High Dimensional Bayesian Optimisation? (2023-01-30T00:00:00.000000Z)

TL;DR

This paper formally shows that a random tree-based decomposition sampler exhibits favourable theoretical guarantees that effectively trade off maximal information gain and functional mismatch between the actual black-box and its surrogate as provided by the decomposition.

Abstract

Learning decompositions of expensive-to-evaluate black-box functions promises to scale Bayesian optimisation (BO) to high-dimensional problems. However, the success of these techniques depends on finding proper decompositions that accurately represent the black-box. While previous works learn those decompositions based on data, we investigate data-independent decomposition sampling rules in this paper. We find that data-driven learners of decompositions can be easily misled towards local decompositions that do not hold globally across the search space. Then, we formally show that a random tree-based decomposition sampler exhibits favourable theoretical guarantees that effectively trade off maximal information gain and functional mismatch between the actual black-box and its surrogate as provided by the decomposition. Those results motivate the development of the random decomposition upper-confidence bound algorithm (RDUCB) that is straightforward to implement - (almost) plug-and-play - and, surprisingly, yields significant empirical gains compared to the previous state-of-the-art on a comprehensive set of benchmarks. We also confirm the plug-and-play nature of our modelling component by integrating our method with HEBO, showing improved practical gains in the highest dimensional tasks from Bayesmark.

Authors

Haitham Bou-Ammar

2 papers

Juliusz Ziomek

1 papers

TL;DR

Abstract

Authors

References53 items

Additive Gaussian Processes Revisited

BOiLS: Bayesian Optimisation for Logic Synthesis

Misspecified Gaussian Process Bandit Optimization

LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso

High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning

Bayesian Optimization is Superior to Random Search for Machine Learning Hyperparameter Tuning: Analysis of the Black-Box Optimization Challenge 2020

High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces

Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces

Good practices for Bayesian Optimization of high dimensional structured spaces

High-Dimensional Bayesian Optimization via Tree-Structured Additive Models

Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?

HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation

Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining

Distributionally Robust Bayesian Optimization

Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization

NAS-Bench-1Shot1: Benchmarking and Dissecting One-shot Neural Architecture Search

Constrained Bayesian optimization for automatic chemical design using variational autoencoders

Scalable Global Optimization via Local Bayesian Optimization

High Dimensional Bayesian Optimization via Supervised Dimension Reduction

A Framework for Bayesian Optimization in Embedded Subspaces

High-dimensional Bayesian optimization using low-dimensional feature spaces

Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces

No-regret Bayesian Optimization with Unknown Hyperparameters

Parallelised Bayesian Optimisation via Thompson Sampling

High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups

High Dimensional Bayesian Optimization using Dropout

The reparameterization trick for acquisition functions

On Kernelized Multi-armed Bandits

Multi-fidelity Bayesian Optimisation with Continuous Approximations

Automatic Chemical Design Using a Data-Driven Continuous Representation of Molecules

Deep Kernel Learning

Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning

High Dimensional Bayesian Optimisation and Bandits via Additive Models

Additive Gaussian Process Regression

Bayesian Optimization in a Billion Dimensions via Random Embeddings

Bayesian optimisation for Intelligent Environmental Monitoring

Additive Gaussian Processes

Additive Covariance Kernels for High-Dimensional Gaussian Process Modeling

Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting

A Knowledge-Gradient Policy for Sequential Information Collection

The Elements of Statistical Learning

Distributed h-infinity consensus of heterogeneous multi-agent systems with nonconvex constraints

Our proof follows the idea of the proof of Theorem 1 from (Bogunovic

AUTO-ENCODING VARIATIONAL BAYES

Bayesian optimization and attribute adjustment

High Dimensional Bayesian Optimization with Elastic Gaussian Process

Regret for Expected Improvement over the Best-Observed Value and Stopping Condition

improvement brought by using a different acquisition function. Tree-EI stands for the Tree algorithm (Han et al., 2021) utilising the expected-improvement acquisition function (Nguyen et al.

Taking the Human Out of the Loop: A Review of Bayesian Optimization

Package 'lpsolve

Bayesian Optimization in High Dimensions via Random Embeddings

Gaussian process optimization in the bandit setting: No regret and experimental design

Uci machine learning repository

Field of Study

Journal Information

Name

Volume

Venue Information

Name

Type

URL

Alternate Names