🤖 machine learning

B3O: Scalable Boltzmann Batch Bayesian Optimization

The paper introduces B3O, a scalable Bayesian Optimization framework that reframes batch generation as a direct sampling problem from the Boltzmann distribution of the acquisition function, thereby overcoming the computational bottlenecks and diversity limitations of existing methods while maintaining theoretical regret guarantees and demonstrating superior performance on complex engineering tasks.

Original authors: Maximilian Bloor, Liyuan Xu, Hrvoje Stojic, Victor Picheny

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Maximilian Bloor, Liyuan Xu, Hrvoje Stojic, Victor Picheny

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to find the perfect recipe for a new dish. You have a limited number of ingredients (time and money), and every time you cook a batch, it takes a long time to taste-test the results. Your goal is to find the absolute best recipe as quickly as possible.

In the world of computer science and engineering, this is called Bayesian Optimization (BO). It's a smart way to search for the best solution to a problem without trying every single possibility.

Usually, you test one recipe at a time. But modern computers are so powerful that you can cook many recipes at the same time (a "batch"). The challenge is: How do you pick a batch of recipes that are different enough from each other to explore new ideas, but similar enough to be likely to be good?

The Problem with Current Methods

The paper argues that existing ways to pick these batches have two main flaws:

They are too slow: Some methods try to calculate the perfect combination of all recipes at once. As the batch size grows, the math becomes so heavy it crashes the computer (like trying to solve a puzzle with a million pieces all at once).
They get stuck: Other methods try to be fast by picking recipes one by one, but they end up picking recipes that are all very similar (like picking 100 variations of "spicy pasta" and missing the "sweet dessert" entirely). This is called a lack of diversity.

The Solution: B3O (Boltzmann Batch Bayesian Optimization)

The authors propose a new method called B3O. Instead of trying to calculate the perfect batch, they treat it like a lottery or a weather forecast.

Here is the core idea using a simple analogy:

Imagine the "Acquisition Function" is a map of a mountain range. The highest peaks represent the best recipes (the most promising solutions).

Old methods try to climb the mountain by calculating the steepest path for every single person in the group. It's exhausting and often leads the whole group to the same peak, missing the other mountains.
B3O uses a concept called the Boltzmann Distribution. Think of this as a magical fog that settles over the map.
- The fog is thickest at the highest peaks (the best spots).
- But there is still some fog on the lower hills and even in the valleys.
- The "temperature" of the fog controls how thick it is.
  - High Temperature: The fog is thin and spread out. People (samples) wander everywhere, exploring the whole map.
  - Low Temperature: The fog is thick and clumps tightly around the highest peaks. People stick to the best spots.

B3O simply draws random samples from this fog.

Because the fog is naturally thicker on the peaks, you are more likely to pick good spots.
Because the fog isn't only on the peaks, you still pick some spots on the hills, ensuring you don't miss hidden treasures.
The Magic: You can pick 1,000 people (a huge batch) in the time it used to take to pick 10. It scales perfectly because you aren't doing complex math for each person; you just let the fog do the work.

Why is this a big deal?

The paper claims three main victories:

It's Fast and Scalable: Whether you want to test 10 recipes or 1,000, B3O handles it easily. It doesn't get bogged down by the math.
It's Smart (Theoretically): The authors proved mathematically that this "lottery" approach is almost as good as the perfect, slow calculation. You don't lose much efficiency by just sampling from the fog.
It's Flexible: It works on all kinds of problems.
- Battery Design: They used it to design better lithium-ion batteries, balancing energy and power.
- Race Car Setup: They used it to tune a Formula E car with a mix of continuous settings (like weight) and discrete settings (like gear ratios).

The "Secret Sauce": Temperature

The key to making this work is the temperature parameter.

At the start, when you know nothing, you keep the temperature high. This lets the algorithm explore widely, like a tourist looking at every street in a new city.
As you learn more, you can lower the temperature. This focuses the search on the best areas, like a tourist narrowing down to the best restaurant.
Interestingly, the authors found that you don't even need to change the temperature over time. Keeping it constant often works just as well, making the method very easy to use.

Summary

B3O is a new way to run experiments in parallel. Instead of trying to solve a complex math puzzle to pick your next batch of tests, it uses a statistical "fog" to naturally select a diverse and promising group of tests. It's faster, handles huge batches, and works on everything from designing batteries to tuning race cars, all while being mathematically proven to be highly efficient.

Technical Summary: B3O (Scalable Boltzmann Batch Bayesian Optimization)

1. Problem Formulation

The paper addresses the challenge of Batch Bayesian Optimization (BO) in scenarios requiring massive parallel evaluation of expensive black-box functions. In modern engineering workflows (e.g., simulation-driven design, molecular screening), $B$ candidate points must be queried concurrently per iteration.

Existing strategies face a trade-off between scalability and diversity:

Joint-posterior methods (e.g., q-EI, q-UCB): These optimize a multi-point acquisition over the joint posterior. While they implicitly capture diversity, they require evaluating high-dimensional expectations involving $O(B^3)$ Cholesky factorizations and optimizing over a $B \cdot d$ dimensional space, rendering them intractable for large $B$ .
Greedy/Repulsion heuristics (e.g., Local Penalization): These reduce complexity to $O(B)$ by sequentializing the selection but rely on heuristics that often fail to capture joint uncertainties, leading to clustered, suboptimal batches.
Scalable Thompson Sampling (TS): This method optimizes independent posterior trajectories. However, practical implementations relying on spectral approximations (e.g., Random Fourier Features) suffer from variance starvation, where trajectories collapse onto a narrow set of modes, failing to explore the acquisition landscape effectively. Furthermore, these methods are often restricted to stationary kernels and Gaussian Process (GP) surrogates.

The core problem is to develop a batch BO algorithm that scales linearly with batch size $B$ , preserves multimodal exploration, and remains agnostic to the specific surrogate model or acquisition function used.

2. Methodology: B3O

The authors propose B3O (Boltzmann Batch Bayesian Optimization), which reframes batch generation not as an optimization problem, but as a pure sampling problem.

Core Mechanism

Instead of optimizing an acquisition function $\alpha_t(x)$ or sampling posterior trajectories, B3O draws $B$ independent and identically distributed (i.i.d.) samples directly from a Boltzmann (Gibbs) distribution defined by the marginal acquisition function:
$p_t(x) = \frac{\exp(\lambda_t \alpha_t(x))}{Z_t(\lambda_t)}$
where:

$\alpha_t(x)$ is the point-wise acquisition function (e.g., UCB, LogEI, EHVI).
$\lambda_t$ is an inverse temperature parameter controlling the trade-off between exploration (diversity) and exploitation.
$Z_t(\lambda_t)$ is the normalization constant.

Key Design Choices

Marginal vs. Joint: By sampling from the marginal acquisition density rather than the joint posterior, B3O avoids the $O(B^3)$ computational bottleneck. Generating the batch requires only $B$ i.i.d. draws, scaling linearly with $B$ .
Temperature Scheduling: The paper explores two regimes for $\lambda_t$ $λ_{t}$ :
- Scheduled: $\lambda_t$ increases over time (e.g., $\lambda_t \propto \sqrt{t \log t}$ ) to encourage initial diversity and later convergence.
- Constant: A fixed $\lambda$ is used throughout. Empirical results suggest this is often sufficient and robust.
Sampler Agnosticism: The framework separates the BO loop from the sampling mechanism.
- For continuous spaces, global samplers like DEFER (recursive partitioning) are used.
- For mixed continuous-discrete spaces, the sampler is swapped for a Metropolis-Hastings variant without altering the core BO logic.
Surrogate Agnosticism: Since the method relies only on point-wise evaluations of the marginal acquisition, it is compatible with any surrogate providing marginal predictives (e.g., Sparse Variational GPs, Bayesian Neural Networks), unlike trajectory-based TS which often requires specific kernel decompositions.

3. Theoretical Contributions

The paper provides a finite-time cumulative regret analysis for B3O when paired with the Upper Confidence Bound (UCB) acquisition (referred to as B3O-UCB).

Regret Bound: In the sequential setting ( $B=1$ ), the authors prove that sampling from the Boltzmann distribution incurs only a negligible additive penalty compared to greedy maximization.
Rate: With an inverse temperature schedule $\lambda_t = O(\sqrt{t \log t})$ , the cumulative regret is upper-bounded by $O(\sqrt{T} + \sqrt{C_1 T \beta_T \gamma_T})$ . This recovers the standard GP-UCB regret rate up to a negligible term, theoretically validating that replacing maximization with sampling does not significantly harm optimization performance.
Assumptions: The proof assumes exact sampling from the true Boltzmann distribution and a quadratic lower bound on the acquisition curvature near its maximum.

4. Empirical Results

The authors evaluate B3O across synthetic benchmarks, multi-objective design, and mixed-variable optimization.

Synthetic Benchmarks

Setup: Tested on Shekel-4D, Ackley-5D, and Hartmann-6D with large batch sizes ( $B=100$ ) and small batch sizes ( $B=5$ ).
Performance:
- All B3O variants outperformed Scalable Thompson Sampling (TS) and Random Search on all benchmarks.
- On multimodal functions (Ackley, Hartmann), B3O variants matched or exceeded the performance of Sequential Expected Improvement (Seq-EI), demonstrating efficient use of parallel resources.
- LogEI with constant temperature consistently achieved the lowest regret among batch methods on Ackley and Hartmann.
- UCB with scheduled temperature was most effective on Shekel for escaping deep local minima.
- In the small-batch regime ( $B=5$ ), B3O remained competitive against q-EI and Local Penalization, which struggled with the high-dimensional inner optimization and repulsion heuristics on noisy surrogates.

Real-World Applications

Multi-Objective Battery Electrode Design:
- Task: Maximize specific energy and power for a lithium-ion battery using a physics-based simulator.
- Setup: Compared against NSGA-II and Sequential EHVI with a budget of 600 evaluations ( $B=50$ ).
- Result: B3O achieved a Pareto front comparable to the sequential EHVI baseline in only 12 batch iterations. The constant-temperature variant yielded superior diversity and final hypervolume compared to the scheduled variant.
Mixed-Variable Race Car Configuration:
- Task: Minimize lap time and energy use for a Formula E car with 4 continuous and 2 discrete variables.
- Setup: Compared against Scalable TS and a sequential mixed-variable LogEI baseline.
- Result: B3O variants converged significantly faster (under 20 iterations) than TS (hundreds of iterations) and achieved lower final objectives. This highlights the advantage of B3O's ability to swap samplers for mixed spaces without re-engineering the BO loop.

5. Significance and Claims

The paper claims that B3O offers a unified, scalable framework for batch Bayesian optimization that resolves the scalability-diversity trade-off inherent in existing methods.

Scalability: It achieves linear $O(B)$ scaling by replacing complex joint optimizations or trajectory samplings with a single sampling step.
Robustness: It is agnostic to the choice of surrogate model, acquisition function, and search space type (continuous, constrained, multi-objective, or mixed).
Theoretical Grounding: It provides the first regret analysis for batch BO based on Boltzmann sampling, showing that the approach preserves standard convergence rates.
Practicality: The authors emphasize that a simple constant temperature schedule is often sufficient, making the method easy to deploy without complex hyperparameter tuning.

The paper concludes that B3O effectively circumvents the "variance starvation" of trajectory-based methods and the computational bottlenecks of joint-posterior methods, making it a robust solution for large-scale, parallel black-box optimization. Future work is suggested regarding adaptive temperature schemes and extending the regret analysis to general batch sizes $B > 1$ .