# Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings

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

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 59 references that are in the map.
- First posted on arXiv 3 Mar 2023.

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

- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (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)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [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)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Local Latent Space Bayesian Optimization over Structured Inputs](https://mlsanity.com/paper/2201.11872/) (2022)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [BOCK : Bayesian Optimization with Cylindrical Kernels](https://mlsanity.com/paper/1806.01619/) (2018)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Molecular Hypergraph Grammar with its Application to Molecular Optimization](https://mlsanity.com/paper/1809.02745/) (2018)
- [Bayesian Optimisation over Multiple Continuous and Categorical Inputs](https://mlsanity.com/paper/1906.08878/) (2019)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Improving black-box optimization in VAE latent space using decoder uncertainty](https://mlsanity.com/paper/2107.00096/) (2021)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Active Learning of Linear Embeddings for Gaussian Processes](https://mlsanity.com/paper/1310.6740/) (2013)
- [Mercer Features for Efficient Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2012.07762/) (2020)
- [Bayesian Optimization over Hybrid Spaces](https://mlsanity.com/paper/2106.04682/) (2021)
- [Facilitating Database Tuning with Hyper-Parameter Optimization: A Comprehensive Experimental Evaluation](https://mlsanity.com/paper/2110.12654/) (2021)
- [Low Autocorrelation Binary Sequences](https://mlsanity.com/paper/1512.02475/) (2015)
- [Optimizing Discrete Spaces via Expensive Evaluations: A Learning to Search Framework](https://mlsanity.com/paper/2012.07320/) (2020)
- [BaCO: A Fast and Portable Bayesian Compiler Optimization Framework](https://mlsanity.com/paper/2212.11142/) (2022)
- [Combinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes](https://mlsanity.com/paper/2011.13094/) (2020)

## Built on by (most cited first, 24 of 24)

- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [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)
- [Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization](https://mlsanity.com/paper/2306.09803/) (2023)
- [Language Model Embeddings Can Be Sufficient for Bayesian Optimization](https://mlsanity.com/paper/2410.10190/) (2024)
- [A Bayesian approach for prompt optimization in pre-trained language models](https://mlsanity.com/paper/2312.00471/) (2023)
- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [BARK: A Fully Bayesian Tree Kernel for Black-box Optimization](https://mlsanity.com/paper/2503.05574/) (2025)
- [CATBench: A Compiler Autotuning Benchmarking Suite for Black-box Optimization](https://mlsanity.com/paper/2406.17811/) (2024)
- [Bencher: Simple and Reproducible Benchmarking for Black-Box Optimization](https://mlsanity.com/paper/2505.21321/) (2025)
- [Fine-tuning LLMs with variational Bayesian last layer for high-dimensional Bayesian optimization](https://mlsanity.com/paper/2510.01471/) (2025)
- [Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2510.26633/) (2025)
- [Discovery of Feasible 3D Printing Configurations for Metal Alloys via AI-driven Adaptive Experimental Design](https://mlsanity.com/paper/2601.17587/) (2026)
- [Grey-box Bayesian Optimization for Sensor Placement in Assisted Living Environments](https://mlsanity.com/paper/2309.05784/) (2023)
- [Simulation Based Bayesian Optimization](https://mlsanity.com/paper/2401.10811/) (2024)
- [Non-Myopic Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2412.08085/) (2024)
- [Selecting Critical Scenarios of DER Adoption in Distribution Grids Using Bayesian Optimization](https://mlsanity.com/paper/2501.14118/) (2025)
- [Weighted Euclidean Distance Matrices over Mixed Continuous and Categorical Inputs for Gaussian Process Models](https://mlsanity.com/paper/2503.02630/) (2025)
- [Tree-Structured Parzen Estimator Can Solve Black-Box Combinatorial Optimization More Efficiently](https://mlsanity.com/paper/2507.08053/) (2025)
- [MOCA-HESP: Meta High-dimensional Bayesian Optimization for Combinatorial and Mixed Spaces via Hyper-ellipsoid Partitioning](https://mlsanity.com/paper/2508.06847/) (2025)
- [A reproducible comparative study of categorical kernels for Gaussian process regression, with new clustering-based nested kernels](https://mlsanity.com/paper/2510.01840/) (2025)
- [Black-Box Optimization From Small Offline Datasets via Meta Learning with Synthetic Tasks](https://mlsanity.com/paper/2604.12325/) (2026)
- [Categorical Optimization with Bayesian Anchored Latent Trust Regions for Structural Design under High-Dimensional Uncertainty](https://mlsanity.com/paper/2604.25241/) (2026)

## Abstract (arXiv)

We consider the problem of optimizing expensive black-box functions over high-dimensional combinatorial spaces which arises in many science, engineering, and ML applications. We use Bayesian Optimization (BO) and propose a novel surrogate modeling approach for efficiently handling a large number of binary and categorical parameters. The key idea is to select a number of discrete structures from the input space (the dictionary) and use them to define an ordinal embedding for high-dimensional combinatorial structures. This allows us to use existing Gaussian process models for continuous spaces. We develop a principled approach based on binary wavelets to construct dictionaries for binary spaces, and propose a randomized construction method that generalizes to categorical spaces. We provide theoretical justification to support the effectiveness of the dictionary-based embeddings. Our experiments on diverse real-world benchmarks demonstrate the effectiveness of our proposed surrogate modeling approach over state-of-the-art BO methods.