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

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

## Key facts

- Cited by 53 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 67 references that are in the map.
- First posted on arXiv 14 Feb 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks](https://mlsanity.com/paper/1805.11770/) (2018)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [GenAttack: Practical Black-box Attacks with Gradient-Free Optimization](https://mlsanity.com/paper/1805.11090/) (2018)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Parallel and Distributed Thompson Sampling for Large-scale Accelerated Exploration of Chemical Space](https://mlsanity.com/paper/1706.01825/) (2017)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [Sparse-RS: a versatile framework for query-efficient sparse black-box adversarial attacks](https://mlsanity.com/paper/2006.12834/) (2020)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Provably Efficient Online Hyperparameter Optimization with Population-Based Bandits](https://mlsanity.com/paper/2002.02518/) (2020)
- [High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups](https://mlsanity.com/paper/1802.07028/) (2018)
- [Bayesian Optimisation over Multiple Continuous and Categorical Inputs](https://mlsanity.com/paper/1906.08878/) (2019)
- [Batched High-dimensional Bayesian Optimization via Structural Kernel Learning](https://mlsanity.com/paper/1703.01973/) (2017)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Mixed-Variable Bayesian Optimization](https://mlsanity.com/paper/1907.01329/) (2019)
- [Optimal Transport Kernels for Sequential and Parallel Neural Architecture Search](https://mlsanity.com/paper/2006.07593/) (2020)
- [Bayesian Optimization for Categorical and Category-Specific Continuous Inputs](https://mlsanity.com/paper/1911.12473/) (2019)
- [On the choice of the low-dimensional domain for global optimization via random embeddings](https://mlsanity.com/paper/1704.05318/) (2017)
- [A warped kernel improving robustness in Bayesian optimization via random embeddings](https://mlsanity.com/paper/1411.3685/) (2014)
- [Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework](https://mlsanity.com/paper/2012.07320/) (2020)
- [Black-box Mixed-Variable Optimisation using a Surrogate Model that Satisfies Integer Constraints](https://mlsanity.com/paper/2006.04508/) (2020)
- [Combinatorial Black-Box Optimization with Expert Advice](https://mlsanity.com/paper/2006.03963/) (2020)

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

- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [Vanilla Bayesian Optimization Performs Great in High Dimensions](https://mlsanity.com/paper/2402.02229/) (2024)
- [Automated Reinforcement Learning (AutoRL): A Survey and Open Problems](https://mlsanity.com/paper/2201.03916/) (2022)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [Revisiting Design Choices in Offline Model-Based Reinforcement Learning](https://mlsanity.com/paper/2110.04135/) (2021)
- [AutoPEFT: Automatic Configuration Search for Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2301.12132/) (2023)
- [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)
- [Local Bayesian optimization via maximizing probability of descent](https://mlsanity.com/paper/2210.11662/) (2022)
- [Bounce: Reliable High-Dimensional Bayesian Optimization for Combinatorial and Mixed Spaces](https://mlsanity.com/paper/2307.00618/) (2023)
- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [Self-Correcting Bayesian Optimization through Bayesian Active Learning](https://mlsanity.com/paper/2304.11005/) (2023)
- [From Few to Many: Self-Improving Many-Shot Reasoners Through Iterative Optimization and Generation](https://mlsanity.com/paper/2502.00330/) (2025)
- [Bayesian Generational Population-Based Training](https://mlsanity.com/paper/2207.09405/) (2022)
- [BOiLS: Bayesian Optimisation for Logic Synthesis](https://mlsanity.com/paper/2111.06178/) (2021)
- [Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning](https://mlsanity.com/paper/2310.12774/) (2023)
- [AntBO: Towards Real-World Automated Antibody Design with Combinatorial Bayesian Optimisation](https://mlsanity.com/paper/2201.12570/) (2022)
- [Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization](https://mlsanity.com/paper/2306.09803/) (2023)
- [Improved Off-policy Reinforcement Learning in Biological Sequence Design](https://mlsanity.com/paper/2410.04461/) (2024)
- [We Still Don't Understand High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2512.00170/) (2025)
- [E2ETune: End-to-End Knob Tuning via Fine-tuned Generative Language Model](https://mlsanity.com/paper/2404.11581/) (2024)
- [Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization](https://mlsanity.com/paper/2405.15285/) (2024)
- [BruSLeAttack: A Query-Efficient Score-Based Black-Box Sparse Adversarial Attack](https://mlsanity.com/paper/2404.05311/) (2024)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Bayesian Optimisation of Functions on Graphs](https://mlsanity.com/paper/2306.05304/) (2023)
- [Approximate Neural Architecture Search via Operation Distribution Learning](https://mlsanity.com/paper/2111.04670/) (2021)
- [Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approach](https://mlsanity.com/paper/2306.05843/) (2023)
- [High-dimensional Bayesian Optimization via Covariance Matrix Adaptation Strategy](https://mlsanity.com/paper/2402.03104/) (2024)
- [Adversarial Attacks on Graph Classification via Bayesian Optimisation](https://mlsanity.com/paper/2111.02842/) (2021)

## Abstract (arXiv)

High-dimensional black-box optimisation remains an important yet notoriously challenging problem. Despite the success of Bayesian optimisation methods on continuous domains, domains that are categorical, or that mix continuous and categorical variables, remain challenging. We propose a novel solution -- we combine local optimisation with a tailored kernel design, effectively handling high-dimensional categorical and mixed search spaces, whilst retaining sample efficiency. We further derive convergence guarantee for the proposed approach. Finally, we demonstrate empirically that our method outperforms the current baselines on a variety of synthetic and real-world tasks in terms of performance, computational costs, or both.