PaperlayerView exact revision on arXiv

Source-linked AI summary

Batch Bayesian Optimization via Local Penalization

Javier González, Zhenwen Dai, Philipp Hennig, Neil D. Lawrence

arXiv:1505.08052v4stat.ML

TL;DR

Bayesian optimization often evaluates costly black-box functions sequentially, limiting throughput when parallel resources can process batches at comparable cost. The paper introduces Lipschitz-based local penalization to approximate sequential batch decisions without repeated GP updates, and reports strong performance across computational and experimental settings. Its applicability depends on learning a sufficiently small and valid Lipschitz constant, and a single global value assumes a Lipschitz-homogeneous objective.

  • Problem

    Batch Bayesian optimization must model interactions among simultaneously selected evaluations, but explicitly updating the GP after each batch location adds O(n3) computational overhead.

  • Method

    BBO-LP iteratively maximizes and locally penalizes an acquisition function, using GP-LCA to infer a Lipschitz constant from GP gradients.

  • Results

    LP-UCB achieves the best results in 5 of 9 gSobol cases, while LP-EI and LP-UCB are the most competitive methods in Cosines and wet-lab experiments.

  • Takeaways & Limitations

    Local penalization reduces the computational burden of batch Bayesian optimization while retaining fast, appropriate batch-location decisions and working with any acquisition function.

  • Takeaways & Limitations

    Using one Lipschitz constant assumes a Lipschitz-homogeneous function, although local Lipschitz values could extend the method to non-Lipschitz cases.

Abstract

from arXiv · show

The popularity of Bayesian optimization methods for efficient exploration of parameter spaces has lead to a series of papers applying Gaussian processes as surrogates in the optimization of functions. However, most proposed approaches only allow the exploration of the parameter space to occur sequentially. Often, it is desirable to simultaneously propose batches of parameter values to explore. This is particularly the case when large parallel processing facilities are available. These facilities could be computational or physical facets of the process being optimized. E.g. in biological experiments many experimental set ups allow several samples to be simultaneously processed. Batch methods, however, require modeling of the interaction between the evaluations in the batch, which can be expensive in complex scenarios. We investigate a simple heuristic based on an estimate of the Lipschitz constant that captures the most important aspect of this interaction (i.e. local repulsion) at negligible computational overhead. The resulting algorithm compares well, in running time, with much more elaborate alternatives. The approach assumes that the function of interest, $f$, is a Lipschitz continuous function. A wrap-loop around the acquisition function is used to collect batches of points of certain size minimizing the non-parallelizable computational effort. The speed-up of our method with respect to previous approaches is significant in a set of computationally expensive experiments.

1 Introduction

Bayesian optimization efficiently optimizes costly black-box functions, but sequential evaluation becomes a bottleneck when many evaluations are needed. This work develops batch designs that approximate sequential decisions using Lipschitz-based local exclusion while reducing computational overhead.

  • Sequential Bayesian optimization: Bayesian optimization uses Gaussian processes and acquisition functions to choose evaluations of costly, possibly noisy black-box functions.The GP posterior supplies the model used to form the acquisition function and select the next evaluation.
  • Batch Bayesian optimization: Parallel batches are useful when evaluating a batch costs the same as evaluating one point, such as with computer cores or wet-lab experiments.Batch observations augment the available data with multiple points selected together.
  • Batch Bayesian optimization: Sequentially modeling interactions among batch elements requires updating the GP after each selected point, incurring O(n3) computational overhead.This optimization-marginalization loop is intractable even for small batch sizes.
  • Lipschitz-based batch design: The proposed approach uses Lipschitz continuity to bound the optimum’s distance from evaluated locations and construct batch points through local penalization.The method aims to mimic sequential acquisition decisions without evaluating the objective between batch selections.
  • Lipschitz-based batch design: BBO-LP iteratively maximizes and penalizes any acquisition function, while GP-LCA estimates the Lipschitz constant from GP gradient properties for batch selection.The approach models local exclusion around new evaluations rather than recomputing the GP after every selected point.

2 Maximization-Penalization Strategy for Batch Design

BBO-LP builds a batch by repeatedly maximizing an acquisition function and locally penalizing regions around selected points. Its penalizers use Lipschitz-based exclusion zones, with GP-LCA estimating the Lipschitz constant and avoiding GP re-estimation between selections.

  • Maximization-Penalization Strategy: Local penalizers smoothly reduce acquisition values near selected locations, approximating the local exclusion caused by evaluating the objective.This heuristic is especially useful when the acquisition function has multiple modes.
  • Maximization-Penalization Strategy: BBO-LP replaces batch optimization’s maximization-marginalization loop with iterative maximization and local penalization around previously selected points.Each new batch element is chosen by optimizing a penalized acquisition function rather than marginalizing unknown evaluations.
  • Choosing Local Penalizers ϕ(x; xj): The penalizer represents the probability that a candidate maximum lies outside a Lipschitz-derived ball around each selected point.The ball’s radius depends on the Lipschitz constant, the estimated maximum, and the objective value at the selected point.
  • Choosing Local Penalizers ϕ(x; xj): Exclusion zones become smaller and more localized when the posterior mean at a selected point is near the estimated maximum, while larger L reduces penalizer effects.When the posterior mean is far from the maximum, the correction is wider but less intense.
  • Algorithm: Algorithm 1 fits a GP, builds a transformed acquisition function, selects each batch point by maximization, penalizes it, and then evaluates the batch in parallel.The procedure uses a single estimated L and does not re-estimate the GP after each location is selected.
  • Selecting the parameters L and M: GP-LCA estimates the Lipschitz constant from the maximum norm of the GP posterior mean gradient.The approximation assumes a sufficiently differentiable kernel and ignores gradient variance.
  • Heteroscedastic scenarios: Using one global L assumes the objective is Lipschitz homocedastic, although local L values can extend the method to non-Lipschitz cases.The proposed extension replaces the global value with location-specific estimates such as ||µ∇(xj)||.

3 Experimental Section

The experiments compare batch Bayesian optimization methods across dimensions, batch sizes, acquisition functions, and objective-evaluation costs. LP methods perform especially well in higher-dimensional and expensive-evaluation settings.

  • Experimental design: The study compares methods across fixed-time simulations and three objectives with cheap, moderate, and expensive evaluations.The simulations vary problem dimension, batch size, and acquisition function; the cost experiments compare information gained per second.
  • Experimental design: The gSobol experiments use dimensions d = 2, 5, 10 and batch sizes nb = 5, 10, 20 under dimension-specific time budgets.UCB methods use κ = 2, and results report averaged best values over completed iterations.
  • gSobol results: LP-UCB achieves the best results in 5 of 9 gSobol cases, with relatively small standard deviations and consistently better results as nb increases.In dimension 2 with batch size 5, LP-EI is the best method.
  • Cost-sensitive comparisons: In the Cosines experiment, sequential EI and UCB lead during the first 10 iterations, after which LP-EI and LP-UCB improve performance in iterations and wall-clock time.The remaining batch methods explore less efficiently and obtain poorer results as the experiments progress.
  • Cost-sensitive comparisons: In the wet-lab experiment, LP-EI and LP-UCB outperform the other batch methods and sequential policies, with larger differences than in Cosines.Parallel evaluation is particularly effective for the more expensive objective, especially with LP-UCB.
  • Cost-sensitive comparisons: For the SVR experiment, objective-evaluation cost dominates batch-design cost, making the different batch methods comparable in performance.The experiment uses nb = 10 and only Python implementations of the listed methods.

4 Discussion

The discussion presents BBO-LP as a fast batch Bayesian optimization heuristic that models local repulsion using Lipschitz continuity. Its effectiveness depends on learning a valid, sufficiently small Lipschitz constant.

  • Conclusions: BBO-LP reduces the computational burden of non-parallelizable tasks and can be used with any acquisition function.The method selects batch locations quickly while avoiding considerable additional overhead when evaluations are parallelizable.
  • Empirical interpretation: Random-exploration batch policies work reasonably well in simple scenarios, whereas methods using information about f improve them as problem complexity increases.The discussion identifies BBO-LP as particularly efficient in the more complex setting.
  • Mechanism: The method models batch interactions through Lipschitz continuity instead of recomputing the GP after every selected point.This approximates the local exclusion effect of evaluations on the acquisition function more efficiently.
  • Limitations: The main limitation is the ability to learn a small enough and valid Lipschitz constant for f.The inferred constant determines the quality of the local-penalization approximation.
  • Scope of the assumption: The approach does not require Lipschitz-continuous GP sample paths because it models acquisition-function effects rather than the GP probability measure itself.For Lipschitz kernels, the posterior mean, covariance, and common acquisition functions are Lipschitz under the stated discussion.

A Proof of Proposition 1

The proposition derives the explicit local-penalization functions from the Gaussian distribution of the distance-related quantity r_j under the Lipschitz model.

  • Derivation: The distribution of r_j is Gaussian with mean (M − µ_n(x_j))/L and variance σ_n^2(x_j)/L^2.These moments follow from the properties of f(x_j).

B Optimization of the penalized acquisition function

The penalized acquisition is optimized sequentially within each batch using gradient descent, with a logarithmic transformation making the gradient additive and tractable.

  • Optimization procedure: Selecting the k-th element of batch t requires optimizing the locally penalized acquisition function.The optimization can be performed with any gradient descent method.
  • Optimization procedure: The method maps the penalized acquisition problem into natural-log space before optimization.Logarithm properties transform the objective into a maximization problem with additive terms.
  • Gradient calculation: In additive form, the gradient combines the original acquisition gradient with gradients of the local penalizers.This makes the gradient with respect to x straightforward to calculate.
  • Gradient calculation: When the acquisition is positive, choosing g(z) = z yields a simplified gradient for the log-penalized acquisition.A separate transformation g(z) = exp(z) is used when the acquisition is not necessarily positive.

C Lipschitz constant approximation

The paper approximates the Lipschitz constant using a proposition-based method and evaluates the approximation on the Cosines function under varying noise and sample sizes.

  • Lipschitz constant approximation: The section introduces a proposition intended to identify a valid Lipschitz constant for functions on compact domains.The proof uses the mean value theorem and Hölder’s inequality.
  • Cosines experiment: The Cosines experiment compares the approximation with the true L∇ value of 8.808636 using up to 50 randomly sampled observations.Function evaluations are perturbed with Gaussian noise.

D.1 Synthetic functions

The synthetic-function experiments use a set of benchmark functions summarized in Table 2, with all gSobol parameters fixed to ai = 1.

  • Synthetic functions: Table 2 lists the functions used in the experimental section.The supplied passage identifies the table as the experiment-function summary.
  • Synthetic functions: The gSobol function uses parameters ai = 1 for all i in the experiments.This setting is specified in the table caption.

D.2 Gene design experiment

The gene-design experiment models protein production from gene features and optimizes the resulting surrogate in a 71-dimensional design space.

  • Gene design experiment: The experiment emulates designing synthetic genes that transform cells into factories producing drugs of interest.This motivates optimizing gene sequences through a biological design task.
  • Gene design experiment: Protein production is modeled as a function of gene-sequence features using a Gaussian process.The model follows the approach described in Gonz´alez et al. [2014].
  • Gene design experiment: The final design space has 71 dimensions, and the model is validated on the remaining 2908 genes before optimization.The posterior mean is used as the function to optimize.

D.3 SVR parameter tuning experiment

The SVR experiment uses Bayesian optimization to tune three support-vector-regression parameters, motivated by the cost of evaluating large datasets.

  • SVR parameter tuning: The SVR depends on kernel lengthscale γ, soft margin parameter C, and band size ϵ.These are the three parameters optimized in the experiment.
  • SVR parameter tuning: Bayesian optimization tunes SVR parameters by minimizing test-dataset mean square error, or RMSE.The passage describes parameter choice through regression-performance evaluation.
  • SVR parameter tuning: The tuning task can be expensive, especially for large datasets.This motivates applying Bayesian optimization to the SVR parameter-selection problem.
Loading 1505.08052v4…