TL;DR
The authors introduce Parallel Knowledge Gradient ($q$-KG), a batch Bayesian optimization algorithm that selects a batch of $q$ points simultaneously to maximize the expected improvement in the Gaussian Process posterior minimum. By pairing a decision-theoretic acquisition function with Infinitesimal Perturbation Analysis (IPA) for efficient gradient computation, $q$-KG consistently outperforms existing batch methods—especially under noisy evaluations.
What Problem Does This Paper Address?
Bayesian optimization (BO) is widely used to optimize expensive black-box functions, such as hyperparameter tuning for deep neural networks. While classical BO algorithms evaluate points sequentially (one at a time), modern computing clusters make it easy to evaluate batches of candidate configurations in parallel.
However, existing parallel BO approaches rely heavily on greedy sequential approximations (e.g., GP-BUCB, constant liar heuristics) or parallel Expected Improvement ($q$-EI). Crucially, Expected Improvement assumes that:
- Observations are noise-free.
- The final recommended optimum must be chosen from the set of previously sampled points.
When evaluations are noisy—such as training a model on subsampled datasets—these assumptions break down, leading to poor optimization efficiency.
Methods
The authors formalize the selection of $q$ candidate points $z^{(1:q)} = \{z_1, \dots, z_q\}$ through the lens of decision theory:
-
The $q$-KG Acquisition Function: Measures the expected reduction in the minimum of the GP predictor after observing the batch: $$q\text{-KG}(z^{(1:q)}, A) = \min_{x \in A} \mu^{(n)}(x) - \mathbb{E}_n \left[ \min_{x \in A} \mu^{(n+q)}(x) \;\middle|\; y(z^{(1:q)}) \right]$$ By construction, $q$-KG is one-step Bayes-optimal without restricting the eventual solution to previously evaluated points.
-
Reparameterization Trick & IPA Gradients: The posterior mean after evaluating the batch can be rewritten linearly in terms of a standard normal random vector $Z_q \sim \mathcal{N}(0, I_q)$ via the Cholesky factor of the batch covariance matrix. Using Infinitesimal Perturbation Analysis (IPA), the authors derive an unbiased stochastic gradient estimator for $q$-KG, enabling efficient batch optimization via multi-start stochastic gradient ascent.
- Dynamic Discretization: Because the search domain $A$ is typically continuous and infinite, the authors approximate $A$ dynamically at each iteration by taking $M = 1000$ Thompson-style samples of the global posterior minimum, augmented with historical points and the current batch candidates.
Datasets
The authors evaluated the method across standard synthetic benchmarks and real-world machine learning tuning tasks:
- Synthetic Benchmarks: Branin (2D), Rosenbrock (3D), Ackley (5D), and Hartmann (6D), evaluated in both noiseless and noisy settings (additive Gaussian noise with $\sigma = 0.5$).
- Logistic Regression on MNIST: Tuning 4 hyperparameters (batch size, iterations, $\ell_2$ regularization, learning rate) using 60,000 training images and 10,000 test images.
- Convolutional Neural Network (CNN) on CIFAR-10: Tuning 8 hyperparameters (batch size, epochs, $\ell_2$ penalty, learning rate, kernel size, convolutional channel counts, dense hidden units, dropout rate) on 50,000 train and 10,000 test images.
- Subsampled (Noisy) MNIST: Tuning logistic regression evaluated on a mini-test split of 1,000 random samples rather than the full 10,000-image test set, simulating noisy, fast evaluations.
Key Insights and Ideas
- Equivalence to $q$-EI in the Limit: If measurements are strictly noise-free and the final recommendation is restricted to previously evaluated points, $q$-KG mathematically reduces to parallel Expected Improvement ($q$-EI).
- Collective vs. Greedy Batching: Rather than building batches incrementally by freezing earlier points (as in UCB variants or heuristic EI), $q$-KG jointly assesses and optimizes the collective information value of all $q$ points.
- Resilience to Noise: Because $q$-KG values points by how much they improve the underlying belief surface rather than requiring the best evaluation itself to be noise-free, it avoids over-exploiting spurious noisy observations.
Key Results
Experiments evaluated batches of size $q = 4$:
- Synthetic Functions: $q$-KG outperformed state-of-the-art baselines (GP-BUCB, GP-UCB-PE, Spearmint-$q$EI, and MOE-$q$EI) on Rosenbrock3, Ackley5, and Hartmann6 in immediate regret, achieving significantly faster convergence in early iterations.
- Noisy Optimization: On noisy synthetic functions and subsampled MNIST, the gap between $q$-KG and competing parallel methods widened considerably.
- CIFAR-10 CNN Tuning: Starting from an expert hand-tuned architecture with $\approx 14\%$ test error, $q$-KG reduced test error to $\approx 11\%$ within 90 total function evaluations, progressing faster and finding better configurations than Spearmint-$q$EI.
Limitations and Future Work
- Computational Overhead: Computing Monte Carlo expectations and stochastic gradients with $M = 1000$ discretized points per batch step is considerably more compute-intensive than analytical heuristics like UCB.
- Myopic Formulation: $q$-KG optimizes a one-step horizon (assuming only one batch remains), which may be suboptimal over long sequential horizons.
- Differentiability Requirement: The IPA gradient framework assumes continuously differentiable GP kernel and mean functions, limiting its plug-and-play use with non-smooth priors or discrete decision spaces without adaptation.
Summary updated