The Parallel Knowledge Gradient Method for Batch Bayesian Optimization

Jian Wu, Peter I. Frazier

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:

  1. Observations are noise-free.
  2. 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

Abstract

In many applications of black-box optimization, one can evaluate multiple points simultaneously, e.g. when evaluating the performances of several different neural network architectures in a parallel computing environment. In this paper, we develop a novel batch Bayesian optimization algorithm --- the parallel knowledge gradient method. By construction, this method provides the one-step Bayes optimal batch of points to sample. We provide an efficient strategy for computing this Bayes-optimal batch of points, and we demonstrate that the parallel knowledge gradient method finds global optima significantly faster than previous batch Bayesian optimization algorithms on both synthetic test functions and when tuning hyperparameters of practical machine learning algorithms, especially when function evaluations are noisy.
BibTeX
@inproceedings{wu2016parallel,
  author = {Jian Wu and Peter I. Frazier},
  title = {{The Parallel Knowledge Gradient Method for Batch Bayesian Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2016},
  url = {https://openreview.net/forum?id=Hkbzfd-OWH},
}

Loading related content...

Figure