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.
Introduction
Optimizing expensive-to-evaluate black-box functions $f$ over discrete or mixed-variable search spaces is a fundamental challenge in science and engineering. While Bayesian Optimization (BO) is effective for continuous domains, discrete parameters—such as categorical choices or integer counts—break the gradient-based optimization of acquisition functions (AFs). Common workarounds, such as naive continuous relaxation followed by rounding or exhaustive search, often fail due to "overestimation" of infeasible points or lack of scalability in high-dimensional spaces.
Probabilistic Reparameterization (PR)
To address these limitations, we propose Probabilistic Reparameterization (PR). Rather than optimizing the AF $\alpha(x, z)$ directly over discrete $z$, we define a probability distribution $p(Z|\theta)$ over the discrete space, where $\theta$ are continuous parameters (e.g., weights in a softmax function). We then maximize the Probabilistic Objective (PO): the expectation of the acquisition function over this distribution.
As shown in Algorithm 1, the BO loop remains largely standard, but the AF maximization step (Line 4) now utilizes the probabilistic objective. This allows the use of gradient-based optimizers like Adam via the score function estimator, even for discrete spaces. This approach is "plug-and-play," working with any surrogate model (like Gaussian Processes) and any standard acquisition function (like Expected Improvement).
Theoretical and Practical Advantages
A key theoretical contribution of this work is proving that the maximum of the PO is equivalent to the maximum of the original AF. Consequently, PR-based BO inherits the same regret bounds as traditional BO.
Practically, PR avoids the "rounding trap" where continuous relaxations might suggest a high-value region that disappears once rounded to a valid discrete point. By evaluating the expectation over valid discrete samples, PR ensures the optimizer focuses on feasible regions. This effectively "blurs" the rugged discrete landscape into a smooth surface where gradients can point toward the global optimum.
Figure 2 illustrates this smoothing effect. While standard continuous relaxations can be jagged or misleading, the PO creates a well-behaved surface where gradients effectively guide the search toward the global optimum. The heatmap comparison shows that the PO value more accurately reflects the true potential of the discrete candidates compared to naive relaxation.
Experimental Evaluation
We evaluated PR across a diverse suite of benchmarks:
- Synthetic Functions: High-dimensional variants of Ackley (13D) and Rosenbrock (10D) tailored to include binary and ordinal variables.
- Engineering Design: A welded beam design problem with over 370 million discrete combinations and five black-box constraints.
- Real-World Applications: Feature selection for SVMs (50 binary features), cellular network parameter tuning (30D), and chemical synthesis optimization.
Across nearly all benchmarks, PR (or PR combined with Trust Regions) achieved lower regret and found superior solutions faster than state-of-the-art baselines like CASMOPOLITAN and HYBO. Sensitivity analysis further showed that PR is remarkably robust to the number of Monte Carlo samples used; even with as few as 128 samples, it maintains high performance.
Conclusion
Probabilistic Reparameterization provides a robust, scalable, and theoretically grounded framework for BO in discrete and mixed spaces. By smoothing the search landscape through expectation, PR enables the application of powerful continuous optimization tools to previously intractable discrete problems. While calculating expectations via Monte Carlo sampling adds some computational overhead, the method's linear scalability and superior optimization performance make it a powerful tool for complex engineering tasks.
Summary updated