PaperlayerView exact revision on arXiv

Source-linked AI summary

The Parallel Knowledge Gradient Method for Batch Bayesian Optimization

Jian Wu, Peter I. Frazier

arXiv:1606.04414v4stat.MLcs.AIcs.LG

TL;DR

Black-box optimization often permits multiple simultaneous evaluations, creating a need for batch Bayesian optimization. The paper introduces q-KG, an efficiently computable one-step Bayes-optimal batch policy, and reports stronger or competitive performance across synthetic and practical machine-learning problems, especially with noise.

  • Problem

    Bayesian optimization commonly selects evaluations sequentially, despite applications that can evaluate q ≥1 points simultaneously.

  • Method

    The paper generalizes knowledge gradient to parallel batches, selecting q points by their expected incremental improvement in the GP predictor’s minimum.

  • Results

    q-KG outperforms or is competitive with state-of-the-art benchmark algorithms on several synthetic functions and practical machine-learning tuning problems.

  • Takeaways & Limitations

    q-KG provides especially large value when function evaluations are noisy.

  • Takeaways & Limitations

    Computing q-KG and its gradient is very expensive, requiring a computational method to optimize it efficiently.

Abstract

from arXiv · show

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.

1 Introduction

Bayesian optimization targets expensive black-box functions with few evaluations, but conventional methods usually select points sequentially. This paper develops a decision-theoretic acquisition function for evaluating q points simultaneously.

  • Bayesian optimization uses a Gaussian process and an acquisition function to select evaluations for expensive objectives.It often finds near-optimal values with fewer evaluations than other global optimization algorithms.
  • The setting permits q ≥1 simultaneous evaluations at each iteration, whereas most prior Bayesian optimization work assumes sequential evaluations.Parallel evaluation is practical when multiple machines can test different hyperparameter configurations concurrently.
  • The paper proposes parallel knowledge gradient (q-KG), a batch acquisition function derived from decision-theoretic analysis.It measures the information gain from evaluating q points and selects the average-case optimal remaining batch.
  • q-KG gradients are computed efficiently using infinitesimal perturbation analysis, enabling optimization of the batch acquisition function.Naive maximization becomes especially expensive as q grows.
  • Experiments compare q-KG with parallel EI, batch UCB, and parallel UCB with exploration on synthetic and practical machine-learning problems.The paper reports especially large value from q-KG when function evaluations are noisy.

2 Related work

Prior parallel Bayesian optimization methods commonly construct batches greedily from single-evaluation criteria, while other methods jointly optimize batch criteria. The paper positions q-KG as a collective, decision-theoretic alternative and evaluates it against these benchmarks.

  • Parallel EI methods iteratively add points using posterior-averaged single-evaluation EI or the constant-liar strategy.These procedures construct the batch sequentially rather than optimizing all points together.
  • GP-BUCB fills batches by sequential UCB selection with kernel updates, while GP-UCB-PE combines UCB with pure exploration.Both extend UCB-based selection to parallel evaluations.
  • Many parallel methods construct batches greedily by optimizing a single-evaluation acquisition function while holding previously selected points fixed.Other work instead jointly optimizes parallel EI or related collective criteria.
  • The experiments compare against several prior methods and demonstrate improvement, especially for noisy evaluations.The comparison includes the parallel Bayesian optimization methods discussed in this section.
  • q-KG extends sequential knowledge gradient to parallel decisions, where the batch is selected collectively and the final solution need not be sampled.Sequential KG is Bayes-optimal when one iteration remains; expected improvement is Bayes-optimal when the final solution must be sampled.

3 Background on Gaussian processes

The paper models the objective with a Gaussian process prior specified by a mean and kernel, then updates it with observations to obtain a Gaussian-process posterior. Measurement errors are assumed exact or independently normally distributed.

  • A Gaussian process prior over f : A →R is specified by mean function µ(x) and kernel function K(x1, x2).The kernel maps pairs of feasible-domain points to real values.
  • Function evaluations may be exact or include independent normally distributed measurement errors.The model treats the evaluation at xi as an observation subject to the specified error structure.
  • The measurement-error variance σ2 : A →R+ is a known function, although the paper also estimates it in experiments when needed.This variance describes the noise associated with measurements across the domain.
  • After observing n function values and corresponding measurements, the prior is updated to a posterior Gaussian process with mean µ(n) and kernel K(n).These posterior functions provide the quantities used later by the optimization method.

4 Parallel knowledge gradient (q-KG)

Parallel knowledge gradient selects a batch by the expected improvement in the GP predictor’s minimum after observing that batch. It is one-step Bayes-optimal, reduces to parallel EI under specific conditions, and is implemented with an efficient gradient strategy.

  • Parallel knowledge gradient (q-KG): q-KG generalizes knowledge gradient to parallel Bayesian optimization by evaluating the expected incremental value of a batch of q points.Unlike expected improvement, the final recommendation need not be one of the sampled points.
  • Parallel knowledge gradient (q-KG): The batch value is the difference between the current predictor minimum and the predictor minimum after the additional batch is observed.The post-batch minimum is random because it depends on the sample outcomes.
  • Parallel knowledge gradient (q-KG): q-KG assigns each candidate batch its posterior expected value and selects the q points maximizing that parallel knowledge gradient factor.The expectation is taken with respect to the posterior after n evaluations.
  • Properties: By construction, parallel knowledge gradient is Bayes-optimal for minimizing the GP predictor minimum when only one decision remains.This optimality concerns the one-step remaining-decision setting.
  • Properties: q-KG reduces exactly to parallel EI when evaluations are noise-free and the final recommendation is restricted to previously sampled points.Under those conditions, the expected solution-quality increment becomes the parallel EI acquisition function.
  • Computation: Computing q-KG and its gradient is very expensive, motivating the paper’s computational strategy for efficient optimization.The algorithm initializes with Latin hypercube samples, repeatedly optimizes q-KG, samples the selected batch, and updates the GP.

5 Computation of q-KG

The paper computes q-KG by representing posterior updates with Gaussian Monte Carlo samples, estimating gradients with IPA, and optimizing the resulting acquisition function. For infinite feasible domains, it discretizes the domain using an evolving set of posterior-optimum samples augmented with observed and candidate points.

  • Finite-domain computation: q-KG can be computed for finite A by sampling a standard q-dimensional normal vector, evaluating the posterior-update expression, and averaging the resulting values.The posterior residual is represented using the Cholesky factor of the observation covariance matrix.
  • Gradient estimation: The q-KG gradient is estimated with infinitesimal perturbation analysis and optimized using multi-start stochastic gradient ascent.The approach uses an unbiased gradient estimator under continuously differentiable mean and kernel functions.
  • Infinite-domain approximation: When A is infinite, the method discretizes A and maximizes q-KG over the resulting approximation.The discretization is used to approximate q-KG before optimization.
  • Infinite-domain approximation: The discretization set evolves after each Gaussian-process posterior update by sampling M global optima of the posterior and adding previously sampled and candidate points.The evolving set is updated in every iteration.

6 Numerical experiments

The experiments evaluate q-KG across synthetic functions, machine-learning hyperparameter tuning, noisy objectives, and small test sets. q-KG is generally competitive or superior, with especially strong advantages under noisy evaluations.

  • Experimental settings: Experiments use noise-free and noisy synthetic functions plus practical machine-learning hyperparameter-tuning problems, with q = 4 in the reported tests.The noisy setting adds independent Gaussian noise with standard deviation σ = 0.5, which the algorithms must learn from data.
  • Synthetic functions: q-KG is significantly better on Rosenbrock3, Ackley5, and Hartmann6, but slightly worse than the best benchmark on Branin2.The synthetic-function comparison runs 100 random initializations and reports mean and standard deviation of log10 immediate regret.
  • Machine-learning tuning: On logistic regression tuning for MNIST, q-KG maintains early progress longer and generally produces a better algorithm configuration.Results report mean and standard deviation of test error over 20 independent runs while tuning four hyperparameters.
  • Machine-learning tuning: For CNN tuning on CIFAR10, q-KG makes more aggressive progress than parallel EI and improves test error from around 14% to around 11%.The comparison concerns an eight-hyperparameter tuning problem using a CNN architecture based on a TensorFlow tutorial.
  • Noisy objectives: In noisy synthetic problems, q-KG is consistently better than or competitive with all competing methods, with a larger performance advantage than in noise-free problems.The experiments use the same four synthetic functions as the noise-free setting and add independent Gaussian noise.
  • Small test sets: With logistic regression evaluated on 1,000 randomly selected MNIST test samples, q-KG beats both parallel EI variants and approaches the noise-free test error.The reported full-test error uses hyperparameters recommended by each method over 20 independent runs.

7 Conclusions

The paper introduces q-KG, a decision-theoretic batch Bayesian optimization method, together with an efficient computational implementation. Across synthetic and practical machine-learning problems, q-KG outperforms or matches state-of-the-art benchmarks.

  • Contributions: q-KG is a novel batch Bayesian optimization method derived from a decision-theoretical perspective and implemented through a computationally efficient method.The method is introduced as a new parallel acquisition approach for batch optimization.
  • Empirical conclusion: Across several synthetic functions and practical machine-learning tuning problems, q-KG outperforms or is competitive with state-of-the-art benchmark algorithms.The paper reports this comparison as its empirical conclusion.

Supplementary Material

The supplementary material extends q-KG from synchronous to asynchronous batch optimization. It recommends new points while some earlier evaluations remain unfinished.

  • Synchronous optimization: Synchronous q-KG waits for all q points in the previous batch to finish before selecting the next batch.This is the baseline formulation generalized in the supplementary material.
  • Asynchronous optimization: Asynchronous q-KG recommends q new points while p < q evaluations remain in progress, using gradients with respect to only the recommended points.The q-KG estimate is formed for the combined q + p points before applying gradient-based optimization.

B Speed-up analysis

q-KG achieves speed-ups as batch size increases in noisy synthetic tests, while its analysis and computation rely on regularity and boundedness conditions.

  • Empirical speed-up: q-KG provides a speed-up as the batch size q increases on noisy Branin2 and Hartmann6 functions.The experiments use noise with standard deviation σ = 0.5 and compare q-KG with fully sequential KG.
  • Empirical speed-up: Figure 5 reports mean and standard deviation of log10 immediate regret against iteration number for different q values.Iteration 0 denotes the initial designs; subsequent iterations evaluate q points recommended by q-KG.
  • Regularity conditions: The derivative-based analysis assumes continuous differentiability of the mean and kernel functions when the domain A is finite.The proposition concerns the q-KG factor under these regularity conditions.
  • Regularity conditions: The stochastic-gradient interchange uses continuity, differentiability except on a denumerable set, and a uniformly bounded derivative with finite expected bound.These conditions are stated for the relevant q-KG function with respect to each batch coordinate.

C.1 Proof of condition (i)

For finite A, the q-KG-related function is continuous in each batch coordinate when the mean and kernel functions are continuously differentiable.

  • Continuity: For any fixed x, the posterior standard-deviation term is continuously differentiable in the batch points under continuously differentiable mean and kernel functions.This follows because multiplication, inversion when defined, and Cholesky operations preserve continuous differentiability.
  • Continuity: When A is finite, the function g is continuous in the batch points, so the coordinate-wise function fA,Zq is continuous in zij.The latter continuity follows directly from the definition of fA,Zq.
  • Continuity: The proof establishes condition (i), namely continuity of fA,Zq(zij) in the coordinate zij for fixed A and Zq.This is the continuity condition required for the subsequent derivative argument.

C.2 Proof of condition (ii)

The proof establishes differentiability except on a denumerable set by analyzing isolated nondifferentiability points and bounding derivative terms under compactness assumptions.

  • Differentiability: The nondifferentiability set D(A) is analyzed through possible ties between competing terms depending on the coordinate zij.The proof introduces continuous differentiable differences such as η(zij) and δ(zij).
  • Differentiability: A contradiction argument shows that the relevant exceptional set contains only isolated points, and therefore is denumerable.The argument considers a convergent sequence of exceptional points and derives a contradiction.
  • Bounds: The derivative of the posterior mean contribution is bounded because the mean function is continuously differentiable and A is compact.The bound is denoted by B > 0.
  • Bounds: The derivative of the posterior standard-deviation contribution is continuously bounded on compact A by a finite vector Λ.This supplies a finite bound for the derivative terms used in the expectation argument.
  • Bounds: The expectation of the resulting bound is finite, supporting the integrability condition needed for the stochastic-gradient analysis.The bound uses the batch-point coordinates and the finite Λ components.
  • Stochastic-gradient convergence: The later convergence proof for stochastic gradient ascent requires diminishing step sizes and a finite second moment of the gradient estimator.The step size must satisfy γt → 0 as t → ∞, together with the stated summability condition.
Loading 1606.04414v4…