The Problem with Greedy Parallelization
When optimizing expensive black-box functions, parallel computing allows us to evaluate multiple candidate points simultaneously. As Kirthevasan Kandasamy et al. demonstrate in Parallelised Bayesian Optimisation via Thompson Sampling and Jialei Wang et al. show in Parallel Bayesian Global Optimization of Expensive Functions, distributing evaluations across parallel workers can drastically reduce wall-clock time without sacrificing overall optimization efficiency.
However, the traditional way to construct a batch of points relies on a greedy or sequential heuristic. In these approaches, an algorithm selects the single best point, "hallucinated data" is used to update the model, and the algorithm greedily selects the next point.
This sequential approach fails because it does not optimize the collective information gain of the group. As noted by Jian Wu et al. in The Parallel Knowledge Gradient Method for Batch Bayesian Optimization and Amar Shah et al. in Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions, greedy selection ignores the spatial correlations and information overlap between points within the same batch. Because the algorithm does not consider how the points interact, it frequently samples redundant information, causing candidate points to cluster or "clump" together in high-probability regions. This lack of diversity leads to inefficient exploration when navigating complex, multi-modal landscapes.
The Core Idea: Holistic Batch Selection
The core insight of joint batch optimization is to select all evaluation points simultaneously by maximizing a single, collective acquisition function. Instead of treating batch construction as a sequence of isolated decisions, the entire set of inputs is optimized jointly.
By optimizing the batch holistically, the framework explicitly accounts for the mutual information and spatial correlations across the entire group. As Quoc Phong Nguyen et al. explain in Top-k Ranking Bayesian Optimization, this joint framing prevents the acquisition of redundant information and ensures that the selected set provides the most diverse and informative feedback.
Several major acquisition frameworks have been successfully extended to this joint batch setting:
- Parallel Knowledge Gradient ($q$-KG): Proposed by Jian Wu et al., this decision-theoretic approach maximizes a collective acquisition function for the entire set, making it highly resilient when function evaluations are noisy or uncertain.
- Parallel Predictive Entropy Search (PPES): Developed by Amar Shah et al., this information-theoretic method optimizes the entire batch at once to maximize the mutual information between the observations and the location of the global maximum.
- Batch Expected Improvement ($q$-EI & $q$-mEI): Frameworks such as the one introduced by David Gaudrie et al. in Targeting solutions in Bayesian multi-objective optimization: sequential and batch versions extend standard criteria to a batch setting, selecting a batch of $q$ points that collectively maximize expected improvement to accelerate convergence.
As demonstrated by Erik A. Daxberger et al. in Distributed Batch Gaussian Process Optimization and Quoc Phong Nguyen et al. in Trusted-maximizers entropy search for efficient Bayesian optimization, accounting for these intra-batch interactions consistently yields lower cumulative regret and superior search space coverage compared to one-at-a-time selection.
Overcoming the Computational Bottleneck
If joint batch optimization is mathematically superior, why did researchers historically rely on greedy heuristics? The challenge lies in the computational complexity: maximizing a complex, multi-point acquisition landscape introduces a severe optimization bottleneck. Recent work has introduced several key mechanisms to make simultaneous batch selection numerically stable and scalable:
- Log-Space Reformulations: Joint optimization can suffer from severe numerical instability. Sebastian Ament et al. discovered in Unexpected Improvements to Expected Improvement for Bayesian Optimization that reformulating these acquisition functions in log-space restores numerical stability, making simultaneous sampling highly effective and superior to sequential greedy strategies.
- Stochastic Gradient Estimators: To navigate the intricate multi-point expected improvement landscape, the authors of Parallel Bayesian Global Optimization of Expensive Functions utilized a novel stochastic gradient estimator, enabling fast and precise optimization of the inner batch problem.
- Exact Analytic Expressions: In multi-objective optimization, Jingda Deng et al. showed in Expected Hypervolume Improvement Is a Particular Hypervolume Improvement that the batch version of Expected Hypervolume Improvement ($q$EHVI) can be expressed as an exact analytic sum of individual terms. This eliminates the need for slow Monte Carlo approximations and provides precise gradients for simultaneous optimization.
- Single-Pass Approximations: Instead of iteratively re-fitting models for each individual point in a batch, the authors of Parallel predictive entropy search for multi-objective Bayesian optimization with constraints applied to the tuning of machine learning algorithms designed an information-theoretic approach that executes heavy approximations only once per batch iteration, substantially reducing computational overhead when scaling to large batch sizes.
Broader Applications of Joint Batch Feedback
The intuition behind joint batch optimization—that a batch should be optimized as an interconnected collective rather than an average of isolated parts—extends to other domains facing distorted gradient signals.
For instance, in physical deep learning, training neural networks to interact with differentiable physics simulators often fails because solvers distort standard gradient signals. To resolve this, Patrick Schnell et al. introduced Half-Inverse Gradients in Half-Inverse Gradients for Physical Deep Learning. Instead of averaging individual gradients, their method performs a collective inversion of the Jacobian across an entire batch. This collective feedback mechanism allows the optimization process to achieve higher accuracy in hitting target states, demonstrating that joint batch awareness is a powerful tool for stabilizing and accelerating parallel optimization across diverse scientific domains.
Key Foundational Work
The Parallel Knowledge Gradient Method for Batch Bayesian Optimization (2016) — contributed 3 concept elements to this direction.
Parallel Predictive Entropy Search for Batch Global Optimization of Expensive Objective Functions (2015) — contributed 3 concept elements to this direction.