# Bayesian Optimization of Combinatorial Structures

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

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2018.

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

- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [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)
- [The Out-of-Distribution Problem in Explainability and Search Methods for Feature Importance Explanations](https://mlsanity.com/paper/2106.00786/) (2021)
- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Increasing the Scope as You Learn: Adaptive Bayesian Optimization in Nested Subspaces](https://mlsanity.com/paper/2304.11468/) (2023)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimization](https://mlsanity.com/paper/2406.15708/) (2024)
- [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)
- [Bayesian Optimization over Hybrid Spaces](https://mlsanity.com/paper/2106.04682/) (2021)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [Query-Efficient and Scalable Black-Box Adversarial Attacks on Discrete Sequential Data via Bayesian Optimization](https://mlsanity.com/paper/2206.08575/) (2022)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [Application of QUBO solver using black-box optimization to structural design for resonance avoidance](https://mlsanity.com/paper/2204.04906/) (2022)
- [Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning](https://mlsanity.com/paper/2310.12774/) (2023)
- [NOMU: Neural Optimization-based Model Uncertainty](https://mlsanity.com/paper/2102.13640/) (2021)
- [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)
- [Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spaces](https://mlsanity.com/paper/2207.00879/) (2022)
- [Low-Cost Algorithmic Recourse for Users With Uncertain Cost Functions](https://mlsanity.com/paper/2111.01235/) (2021)
- [OpenBox: A Python Toolkit for Generalized Black-box Optimization](https://mlsanity.com/paper/2304.13339/) (2023)
- [Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation](https://mlsanity.com/paper/2410.16893/) (2024)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2306.01276/) (2023)
- [Batch Multi-Fidelity Bayesian Optimization with Deep Auto-Regressive Networks](https://mlsanity.com/paper/2106.09884/) (2021)
- [Retrieving Black-box Optimal Images from External Databases](https://mlsanity.com/paper/2112.14921/) (2021)

## Abstract (arXiv)

The optimization of expensive-to-evaluate black-box functions over combinatorial structures is an ubiquitous task in machine learning, engineering and the natural sciences. The combinatorial explosion of the search space and costly evaluations pose challenges for current techniques in discrete optimization and machine learning, and critically require new algorithmic ideas. This article proposes, to the best of our knowledge, the first algorithm to overcome these challenges, based on an adaptive, scalable model that identifies useful combinatorial structure even when data is scarce. Our acquisition function pioneers the use of semidefinite programming to achieve efficiency and scalability. Experimental evaluations demonstrate that this algorithm consistently outperforms other methods from combinatorial and Bayesian optimization.