# High Dimensional Bayesian Optimisation and Bandits via Additive Models

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

## Key facts

- Cited by 139 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2015.

## Built on by (most cited first, 30 of 139)

- [Hyperparameter Optimization: Foundations, Algorithms, Best Practices and Open Challenges](https://mlsanity.com/paper/2107.05847/) (2021)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Local Latent Space Bayesian Optimization over Structured Inputs](https://mlsanity.com/paper/2201.11872/) (2022)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning](https://mlsanity.com/paper/2106.03609/) (2021)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [BBTv2: Towards a Gradient-Free Future with Large Language Models](https://mlsanity.com/paper/2205.11200/) (2022)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [A Study of Bayesian Neural Network Surrogates for Bayesian Optimization](https://mlsanity.com/paper/2305.20028/) (2023)
- [Practical and Rigorous Uncertainty Bounds for Gaussian Process Regression](https://mlsanity.com/paper/2105.02796/) (2021)
- [Monte Carlo Tree Search based Variable Selection for High Dimensional Bayesian Optimization](https://mlsanity.com/paper/2210.01628/) (2022)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2402.02746/) (2024)
- [Discovering Many Diverse Solutions with Bayesian Optimization](https://mlsanity.com/paper/2210.10953/) (2022)
- [TREGO: a Trust-Region Framework for Efficient Global Optimization](https://mlsanity.com/paper/2101.06808/) (2021)
- [Sample-Then-Optimize Batch Neural Thompson Sampling](https://mlsanity.com/paper/2210.06850/) (2022)
- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization](https://mlsanity.com/paper/2206.08575/) (2022)
- [Self-Correcting Bayesian Optimization through Bayesian Active Learning](https://mlsanity.com/paper/2304.11005/) (2023)
- [The Behavior and Convergence of Local Bayesian Optimization](https://mlsanity.com/paper/2305.15572/) (2023)
- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [Active Learning and Bayesian Optimization: a Unified Perspective to Learn with a Goal](https://mlsanity.com/paper/2303.01560/) (2023)
- [Randomized Gaussian Process Upper Confidence Bound with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2302.01511/) (2023)
- [Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds](https://mlsanity.com/paper/2311.03760/) (2023)
- [Principled Preferential Bayesian Optimization](https://mlsanity.com/paper/2402.05367/) (2024)
- [Derivative-Free Reinforcement Learning: A Review](https://mlsanity.com/paper/2102.05710/) (2021)
- [B2Opt: Learning to Optimize Black-box Optimization with Little Budget](https://mlsanity.com/paper/2304.11787/) (2023)

## Abstract (arXiv)

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.