# Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 41 of its 85 references that are in the map.
- First posted on arXiv 18 Oct 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Densely Connected Convolutional Networks](https://mlsanity.com/paper/1608.06993/) (2016)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2006.05078/) (2020)
- [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 Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement](https://mlsanity.com/paper/2105.08195/) (2021)
- [Maximizing acquisition functions for Bayesian optimization](https://mlsanity.com/paper/1805.10196/) (2018)
- [A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations](https://mlsanity.com/paper/1805.12168/) (2018)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Scalable Constrained Bayesian Optimization](https://mlsanity.com/paper/2002.08526/) (2020)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [Dealing with Integer-valued Variables in Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1706.03673/) (2017)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization](https://mlsanity.com/paper/2006.04655/) (2020)
- [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)
- [No-Regret Bayesian Optimization with Unknown Hyperparameters](https://mlsanity.com/paper/1901.03357/) (2019)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Parallel Bayesian Global Optimization of Expensive Functions](https://mlsanity.com/paper/1602.05149/) (2016)
- [Robust Multi-Objective Bayesian Optimization Under Input Noise](https://mlsanity.com/paper/2202.07549/) (2022)
- [Bayesian Optimization with High-Dimensional Outputs](https://mlsanity.com/paper/2106.12997/) (2021)
- [A Latent Variable Approach to Gaussian Process Modeling with Qualitative and Quantitative Factors](https://mlsanity.com/paper/1806.07504/) (2018)
- [Gryffin: An algorithm for Bayesian optimization of categorical variables informed by expert knowledge](https://mlsanity.com/paper/2003.12127/) (2020)

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

- [Unexpected Improvements to Expected Improvement for Bayesian Optimization](https://mlsanity.com/paper/2310.20708/) (2023)
- [PFNs4BO: In-Context Learning for Bayesian Optimization](https://mlsanity.com/paper/2305.17535/) (2023)
- [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)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [From Few to Many: Self-Improving Many-Shot Reasoners Through Iterative Optimization and Generation](https://mlsanity.com/paper/2502.00330/) (2025)
- [Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning](https://mlsanity.com/paper/2310.12774/) (2023)
- [Framework and Benchmarks for Combinatorial and Mixed-variable Bayesian Optimization](https://mlsanity.com/paper/2306.09803/) (2023)
- [BOtied: Multi-objective Bayesian optimization with tied multivariate ranks](https://mlsanity.com/paper/2306.00344/) (2023)
- [The Vizier Gaussian Process Bandit Algorithm](https://mlsanity.com/paper/2408.11527/) (2024)
- [Return of the Latent Space COWBOYS: Re-thinking the use of VAEs for Bayesian Optimisation of Structured Spaces](https://mlsanity.com/paper/2507.03910/) (2025)
- [Efficient Federated Prompt Tuning for Black-box Large Pre-trained Models](https://mlsanity.com/paper/2310.03123/) (2023)
- [HARBOR: Automated Harness Optimization](https://mlsanity.com/paper/2604.20938/) (2026)
- [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)
- [Variational Search Distributions](https://mlsanity.com/paper/2409.06142/) (2024)
- [In-Context Multi-Objective Optimization](https://mlsanity.com/paper/2512.11114/) (2025)
- [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)
- [Language Model Prompt Selection via Simulation Optimization](https://mlsanity.com/paper/2404.08164/) (2024)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (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)
- [Bayesian Optimization Framework for Efficient Fleet Design in Autonomous Multi-Robot Exploration](https://mlsanity.com/paper/2408.11751/) (2024)
- [A Guide to Bayesian Optimization in Bioprocess Engineering](https://mlsanity.com/paper/2508.10642/) (2025)
- [What to Do When Your Discrete Optimization Is the Size of a Neural Network?](https://mlsanity.com/paper/2402.10339/) (2024)
- [Deep Electromagnetic Structure Design Under Limited Evaluation Budgets](https://mlsanity.com/paper/2506.19384/) (2025)
- [Model-free Reinforcement Learning for Model-based Control: Towards Safe, Interpretable and Sample-efficient Agents](https://mlsanity.com/paper/2507.13491/) (2025)
- [MOCA-HESP: Meta High-dimensional Bayesian Optimization for Combinatorial and Mixed Spaces via Hyper-ellipsoid Partitioning](https://mlsanity.com/paper/2508.06847/) (2025)

## Abstract (arXiv)

Optimizing expensive-to-evaluate black-box functions of discrete (and potentially continuous) design parameters is a ubiquitous problem in scientific and engineering applications. Bayesian optimization (BO) is a popular, sample-efficient method that leverages a probabilistic surrogate model and an acquisition function (AF) to select promising designs to evaluate. However, maximizing the AF over mixed or high-cardinality discrete search spaces is challenging standard gradient-based methods cannot be used directly or evaluating the AF at every point in the search space would be computationally prohibitive. To address this issue, we propose using probabilistic reparameterization (PR). Instead of directly optimizing the AF over the search space containing discrete parameters, we instead maximize the expectation of the AF over a probability distribution defined by continuous parameters. We prove that under suitable reparameterizations, the BO policy that maximizes the probabilistic objective is the same as that which maximizes the AF, and therefore, PR enjoys the same regret bounds as the original BO policy using the underlying AF. Moreover, our approach provably converges to a stationary point of the probabilistic objective under gradient ascent using scalable, unbiased estimators of both the probabilistic objective and its gradient. Therefore, as the number of starting points and gradient steps increase, our approach will recover of a maximizer of the AF (an often-neglected requisite for commonly used BO regret bounds). We validate our approach empirically and demonstrate state-of-the-art optimization performance on a wide range of real-world applications. PR is complementary to (and benefits) recent work and naturally generalizes to settings with multiple objectives and black-box constraints.