# Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?

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

## Key facts

- Cited by 36 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 53 references that are in the map.
- First posted on arXiv 30 Jan 2023.

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

- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [Deep Kernel Learning](https://mlsanity.com/paper/1511.02222/) (2015)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [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)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Sample-Efficient Optimization in the Latent Space of Deep Generative Models via Weighted Retraining](https://mlsanity.com/paper/2006.09191/) (2020)
- [Multi-fidelity Bayesian Optimisation with Continuous Approximations](https://mlsanity.com/paper/1703.06240/) (2017)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [HEBO Pushing The Limits of Sample-Efficient Hyperparameter Optimisation](https://mlsanity.com/paper/2012.03826/) (2020)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [NAS-Bench-1Shot1: Benchmarking and Dissecting One-shot Neural Architecture Search](https://mlsanity.com/paper/2001.10422/) (2020)
- [The reparameterization trick for acquisition functions](https://mlsanity.com/paper/1712.00424/) (2017)
- [Distributionally Robust Bayesian Optimization](https://mlsanity.com/paper/2002.09038/) (2020)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [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)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [LassoBench: A High-Dimensional Hyperparameter Optimization Benchmark Suite for Lasso](https://mlsanity.com/paper/2111.02790/) (2021)
- [High Dimensional Bayesian Optimization Using Dropout](https://mlsanity.com/paper/1802.05400/) (2018)
- [Good practices for Bayesian Optimization of high dimensional structured spaces](https://mlsanity.com/paper/2012.15471/) (2020)
- [High-Dimensional Bayesian Optimization via Tree-Structured Additive Models](https://mlsanity.com/paper/2012.13088/) (2020)
- [High Dimensional Bayesian Optimization via Supervised Dimension Reduction](https://mlsanity.com/paper/1907.08953/) (2019)
- [Additive Gaussian Processes Revisited](https://mlsanity.com/paper/2206.09861/) (2022)
- [BOiLS: Bayesian Optimisation for Logic Synthesis](https://mlsanity.com/paper/2111.06178/) (2021)
- [Are we Forgetting about Compositional Optimisers in Bayesian Optimisation?](https://mlsanity.com/paper/2012.08240/) (2020)

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

- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2402.02746/) (2024)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [Understanding High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2502.09198/) (2025)
- [Comparison of High-Dimensional Bayesian Optimization Algorithms on BBOB](https://mlsanity.com/paper/2303.00890/) (2023)
- [We Still Don't Understand High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2512.00170/) (2025)
- [Functional Graphical Models: Structure Enables Offline Data-Driven Optimization](https://mlsanity.com/paper/2401.05442/) (2024)
- [LLaMEA-BO: A Large Language Model Evolutionary Algorithm for Automatically Generating Bayesian Optimization Algorithms](https://mlsanity.com/paper/2505.21034/) (2025)
- [Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2305.19838/) (2023)
- [Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization](https://mlsanity.com/paper/2405.15285/) (2024)
- [Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal](https://mlsanity.com/paper/2410.10384/) (2024)
- [Simulation-Aided Policy Tuning for Black-Box Robot Learning](https://mlsanity.com/paper/2411.14246/) (2024)
- [High Dimensional Bayesian Optimization using Lasso Variable Selection](https://mlsanity.com/paper/2504.01743/) (2025)
- [Cliqueformer: Model-Based Optimization with Structured Transformers](https://mlsanity.com/paper/2410.13106/) (2024)
- [Augmented Bayesian Policy Search](https://mlsanity.com/paper/2407.04864/) (2024)
- [Sharpness-Aware Black-Box Optimization](https://mlsanity.com/paper/2410.12457/) (2024)
- [High-Dimensional Bayesian Optimization via Random Projection of Manifold Subspaces](https://mlsanity.com/paper/2412.16554/) (2024)
- [Enhancing Trust-Region Bayesian Optimization via Newton Methods](https://mlsanity.com/paper/2508.18423/) (2025)
- [Do We Really Need to Approach the Entire Pareto Front in Many-Objective Bayesian Optimisation?](https://mlsanity.com/paper/2604.09417/) (2026)
- [Rethinking Trust Region Bayesian Optimization in High Dimensions](https://mlsanity.com/paper/2604.22967/) (2026)
- [High-Dimensional Bayesian Optimisation with Large-Scale Constraints -- An Application to Aeroelastic Tailoring](https://mlsanity.com/paper/2312.08891/) (2023)
- [FigBO: A Generalized Acquisition Function Framework with Look-Ahead Capability for Bayesian Optimization](https://mlsanity.com/paper/2504.20307/) (2025)
- [Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2510.26633/) (2025)
- [Learning Relevant Contextual Variables Within Bayesian Optimization](https://mlsanity.com/paper/2305.14120/) (2023)
- [Swine Diet Design using Multi-objective Regionalized Bayesian Optimization](https://mlsanity.com/paper/2409.12919/) (2024)
- [Learning Low-Dimensional Embeddings for Black-Box Optimization](https://mlsanity.com/paper/2505.01112/) (2025)
- [MOCA-HESP: Meta High-dimensional Bayesian Optimization for Combinatorial and Mixed Spaces via Hyper-ellipsoid Partitioning](https://mlsanity.com/paper/2508.06847/) (2025)
- [On Thompson Sampling and Bilateral Uncertainty in Additive Bayesian Optimization](https://mlsanity.com/paper/2510.11792/) (2025)
- [Leveraging Discrete Function Decomposability for Scientific Design](https://mlsanity.com/paper/2511.03032/) (2025)

## Abstract (arXiv)

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.