Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization

Sam Daulton, Xingchen Wan, David Eriksson, Maximilian Balandat, Michael A Osborne, Eytan Bakshy

Bayesian Optimization (BO) is a powerhouse for tuning expensive "black-box" systems, offering a sample-efficient way to find optimal configurations. However, it traditionally struggles when search spaces include discrete or categorical variables. This paper introduces Probabilistic Reparameterization (PR), a method that transforms discrete optimization into a continuous problem by optimizing the expected value of an acquisition function over a probability distribution. This allows researchers to use efficient, gradient-based tools on discrete problems without losing the theoretical "no-regret" guarantees that make BO so reliable.

The Challenge of Mixed Search Spaces

In many engineering fields—from designing oil-absorbing materials to configuring satellite networks—practitioners must tune a mix of continuous parameters (like temperature) and discrete ones (like the type of metal or a binary "on/off" switch).

Standard BO relies on an Acquisition Function (AF) to decide which point to test next. If the space is continuous, we use gradients to find the best point. If the space is discrete, we usually have to check every single point, which is computationally impossible for large spaces.

The common workaround is continuous relaxation: treating categories like numbers, optimizing them continuously, and then rounding them to the nearest valid discrete value. Unfortunately, rounding is notoriously problematic. It creates "flat" regions where gradients are zero, and it often leads the optimizer to overestimate the value of a point, causing the BO loop to get stuck in sub-optimal cycles.

Comparison of continuous relaxation versus the Probabilistic Objective (PO) landscape.

The Solution: Probabilistic Reparameterization (PR)

To bypass the pitfalls of rounding, the authors propose Probabilistic Reparameterization (PR). Instead of trying to find the best discrete point $z$ directly, they define a probability distribution $p(Z|\theta)$ over the discrete space, where $\theta$ represents continuous parameters (like the probability of picking a certain category).

Algorithm for Bayesian Optimization with Probabilistic Reparameterization.

Key components of this approach include:

  • The Probabilistic Objective (PO): Instead of maximizing the AF directly, the algorithm maximizes the expectation of the AF over the distribution $p(Z|\theta)$. Because $\theta$ is continuous, the objective becomes differentiable.
  • Gradient Estimation: Calculating the exact expectation is often too expensive, as it requires a sum over all possible discrete combinations. Instead, PR uses Monte Carlo (MC) sampling and the score function estimator (also known as REINFORCE) to calculate gradients.
  • Variance Reduction: To make the noisy MC gradients more stable, the authors apply a "baseline" technique—subtracting a moving average of previous values—which is a common trick borrowed from reinforcement learning.
  • Reparameterization Trick: They use softmax and other transformations to ensure the distribution parameters $\theta$ stay within valid ranges (e.g., probabilities strictly between 0 and 1).

Key Insights and Theoretical Guarantees

The most critical theoretical contribution of the paper is the proof that maximizing the Probabilistic Objective is mathematically equivalent to maximizing the original Acquisition Function. This means PR inherits all the theoretical convergence and regret bounds of standard BO.

Furthermore, by looking at the expectation, PR effectively "smooths out" the discrete jumps of the search space. As seen in the landscape comparisons, this smoothing allows gradient ascent to navigate toward the best regions even when the underlying space is jagged.

Unlike previous methods that required specific types of "diffusion kernels" or tree-based models, PR is model agnostic. It works with almost any surrogate model (like Gaussian Processes) and any standard acquisition function (like Expected Improvement or Upper Confidence Bound). It also scales additively with the number of models, making it highly suitable for multi-objective or heavily constrained problems.

Empirical Results and Benchmarks

The authors evaluated PR against state-of-the-art methods (like CASMOPOLITAN and HyBO) across a diverse set of challenges, including synthetic functions (Ackley, Rosenbrock) and complex real-world engineering tasks:

  • Welded Beam Design: A constrained optimization problem involving 5 black-box constraints.
  • SVM Feature Selection: Choosing from 50 binary features for a Support Vector Machine.
  • Cellular Network Optimization: A 30-dimensional problem tuning antenna tilt and power.
  • Direct Arylation Chemical Synthesis: Optimizing yield by choosing solvents, bases, and ligands.
  • Electrospun Oil Sorbent: A complex multi-objective problem aimed at maximizing oil absorption, mechanical strength, and water contact angle simultaneously.

Across nearly all benchmarks, PR (often combined with Trust Regions) achieved lower "regret"—meaning it found better solutions—than standard continuous relaxation or specialized discrete BO solvers. In the high-dimensional SVM feature selection task, PR significantly outperformed competitors, finding superior configurations in fewer iterations. While PR is computationally intensive due to MC sampling, it is "embarrassingly parallel." When run on a GPU, it provides competitive wall-clock times, avoiding the severe slowdowns that plague methods like HyBO as the search space expands.

Limitations and Future Work

The primary drawback of PR is the computational overhead required for Monte Carlo sampling to achieve an accurate gradient. While highly parallelizable, it still demands more raw FLOPs than simpler rounding methods. Additionally, PR requires the Acquisition Function itself to be differentiable with respect to the continuous inputs, which may limit the use of certain exotic or non-differentiable selection criteria.

Future work will likely focus on optimizing these AF calculations on distributed hardware to further reduce the time it takes to suggest the next experiment, solidifying PR as a go-to method for complex, mixed-space optimization.

Summary updated

Abstract

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.
BibTeX
@inproceedings{daulton2022bayesian,
  author = {Sam Daulton and Xingchen Wan and David Eriksson and Maximilian Balandat and Michael A Osborne and Eytan Bakshy},
  title = {{Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=WV1ZXTH0OIn},
}
Figure