PaperlayerView exact revision on arXiv

Source-linked AI summary

Unexpected Improvements to Expected Improvement for Bayesian Optimization

Sebastian Ament, Samuel Daulton, David Eriksson, Maximilian Balandat, Eytan Bakshy

arXiv:2310.20708v3cs.LGmath.NAstat.ML

TL;DR

The paper addresses numerical vanishing of EI values and gradients, which makes improvement-based acquisition functions difficult to optimize. It proposes LogEI reformulations that preserve or approximate canonical optima while improving numerical behavior, and reports substantially better optimization performance across acquisition variants and benchmarks. The paper concludes that careful acquisition-function reformulation can materially affect Bayesian optimization results, while gains depend on objective structure and surrogate quality.

  • Problem

    EI and its variants often have numerically vanishing acquisition values and gradients, making them difficult to optimize consistently.

  • Method

    LogEI reformulates analytic, constrained, hypervolume, noisy, and parallel EI variants to preserve or approximately preserve their optima while producing more numerically stable optimization objectives.

  • Results

    LogEI variants substantially outperform their canonical analogues across a broad range of benchmarks without meaningful additional computational cost, often matching or exceeding recent methods.

  • Takeaways & Limitations

    Numerical optimization of acquisition functions is an important contributor to Bayesian optimization performance, including for joint batch optimization.

  • Takeaways & Limitations

    LogEI’s gains depend on the concentration of high objective values and the surrogate’s quality, so high dimensionality alone does not guarantee improvement over EI.

Abstract

from arXiv · show

Expected Improvement (EI) is arguably the most popular acquisition function in Bayesian optimization and has found countless successful applications, but its performance is often exceeded by that of more recent methods. Notably, EI and its variants, including for the parallel and multi-objective settings, are challenging to optimize because their acquisition values vanish numerically in many regions. This difficulty generally increases as the number of observations, dimensionality of the search space, or the number of constraints grow, resulting in performance that is inconsistent across the literature and most often sub-optimal. Herein, we propose LogEI, a new family of acquisition functions whose members either have identical or approximately equal optima as their canonical counterparts, but are substantially easier to optimize numerically. We demonstrate that numerical pathologies manifest themselves in "classic" analytic EI, Expected Hypervolume Improvement (EHVI), as well as their constrained, noisy, and parallel variants, and propose corresponding reformulations that remedy these pathologies. Our empirical results show that members of the LogEI family of acquisition functions substantially improve on the optimization performance of their canonical counterparts and surprisingly, are on par with or exceed the performance of recent state-of-the-art acquisition functions, highlighting the understated role of numerical optimization in the literature.

1 Introduction

The paper identifies numerical vanishing in EI values and gradients as an overlooked implementation problem that undermines gradient-based acquisition optimization. It introduces LogEI reformulations designed to preserve canonical optima while improving numerical optimizability across EI variants.

  • Motivation: Bayesian optimization uses surrogate models and acquisition functions to select evaluations of expensive black-box objectives.EI is an established improvement-based acquisition function and standard baseline across constrained, noisy, multi-objective, and batch settings.
  • Problem: Prior work emphasized optimization algorithms and initialization strategies rather than numerical computation of EI itself.
  • Contribution: LogEI comprises acquisition functions with identical or approximately equal optima to canonical counterparts but substantially easier numerical optimization.The analytic LogEI variant mathematically yields the same Bayesian optimization policy as EI.
  • Contribution: The reformulations extend beyond analytic EI to constrained, hypervolume, and parallel acquisition functions using smooth approximations that produce non-vanishing gradients.The proposed family includes CEI, EHVI, qEI, and qEHVI variants.
  • Contribution: LogEI variants substantially outperform their canonical analogues without meaningful additional computational cost and often match or exceed recent methods.
  • Problem: EI values and gradients can become numerically zero across much of the domain, making gradient-based optimization ineffective.The problem worsens as observations and dimensionality increase, and arises because improvement likelihood becomes small relative to the incumbent.

2 Background

The paper reviews Bayesian optimization surrogates, improvement-based acquisition functions, and the non-convex optimization procedures used to maximize them. It emphasizes that parallel acquisition optimization is harder because it expands the search dimension and complicates the optimization surface.

  • Bayesian optimization: Bayesian optimization combines a probabilistic surrogate with an acquisition function that values candidate evaluations.The objective may have multiple outputs for multi-objective optimization or black-box constraints.
  • Surrogate models: Gaussian processes are widely used Bayesian optimization surrogates because they provide data efficiency and uncertainty quantification.They model predictive outputs with multivariate or univariate Normal distributions, depending on the setting.
  • Improvement-based acquisition functions: Classic EI measures expected positive improvement over the incumbent, the best function value observed so far.Its closed-form expression uses the standard Normal density and distribution functions.
  • Acquisition variants: Constrained EI weights improvement by constraint feasibility, while EHVI measures expected improvement in Pareto-front hypervolume relative to a reference point.Under conditional independence, constrained EI simplifies to EI multiplied by probability of feasibility.
  • Parallel acquisition functions: Parallel EI evaluates batches of candidates and generally requires Monte Carlo computation rather than a closed-form expression.Monte Carlo samples are drawn from the joint posterior, and batch optimization operates in qd dimensions instead of d.
  • Optimizing acquisition functions: Acquisition optimization is non-convex, so practice uses gradient-free, evolutionary, first-order, second-order, and multi-start methods.The paper focuses on gradient-based optimization because it is often faster and more performant on continuous domains.
  • Related work: Existing work largely introduced acquisition-function variants or initialization and optimization methods without addressing numerical degeneracies in the acquisition functions themselves.The paper distinguishes these pathologies from ill-conditioned covariance-matrix issues.

3 Theoretical Analysis of Expected Improvement’s Vanishing Gradients

The theoretical analysis characterizes when EI develops numerically vanishing gradients. It links this behavior to a shrinking optimality gap and decreasing surrogate uncertainty as optimization progresses.

  • Conditions for vanishing gradients: EI is increasingly likely to have numerically vanishing gradients as the optimality gap closes and posterior uncertainty decreases.
  • Theoretical result: Theorem 1 bounds the probability that the standardized improvement argument falls below a threshold using the region where the sampled objective is below f∗−ϵ_n.
  • Theoretical result: The threshold term ϵ_n depends on the optimality gap and the maximum posterior uncertainty.The theorem also provides a high-probability statement over objective functions drawn from a Gaussian process prior.
  • Interpretation: Early iterations need not have small ϵ_n because both the optimality gap and maximum posterior standard deviation can initially be large.Under technical kernel and training-data conditions, maximum posterior variance eventually vanishes as observations increase.

4 Unexpected Improvements

The paper reformulates analytic and Monte Carlo improvement-based acquisition functions in log-space, using stable evaluations and smooth approximations to prevent numerically vanishing values and gradients. These reformulations extend to constrained and hypervolume-based variants while retaining identical or approximately equal optima.

  • Analytic LogEI: Analytic LogEI evaluates the logarithm of expected improvement stably across inputs where naïve implementations become numerically zero.The reformulation uses log_h((µ(x) − y*)/σ(x)) + log(σ(x)), with log_h mathematically equivalent to log ◦h.
  • Analytic LogEI: Asymptotic treatment for strongly negative standardized improvements ensures numerical stability and produces asymptotically quadratic behavior amenable to gradient-based optimization.The implementation adds a third asymptotic case beyond earlier log-transformed EI implementations, addressing instabilities as z becomes negative.
  • Monte Carlo Parallel LogEI: qLogEI smooths positive-part improvement and the batch maximum, then transforms the resulting strictly positive quantities to log-space for effective optimization.The two stages approximate [ξi(xj) − y*]+ with softplus and the maximum across batch candidates with a p-norm.
  • Monte Carlo Parallel LogEI: The qLogEI approximation error relative to qEI can be bounded as a function of the smoothing temperatures and batch size.The paper states a relative approximation guarantee for τ0, τmax > 0.
  • Monte Carlo Parallel LogEI: Low smoothing temperatures are needed for good qLogEI optimization, and log-space computation makes such temperatures possible without numerically vanishing gradients.Without the log transformation, the smooth approximation would inherit numerical gradient vanishing from the discrete maximum.
  • Extensions: LogEI ideas extend to constrained EI and EHVI variants by combining stable log evaluations with smooth approximations of constraint indicators and hypervolume operations.Analytic constrained EI adds stable log constraint probabilities, while qEHVI uses smoothing and log transformations within a differentiable inclusion-exclusion formulation.

5 Empirical Results

Across sequential, constrained, parallel, and high-dimensional Bayesian optimization benchmarks, LogEI variants generally optimize more effectively than their canonical EI-based counterparts, with gains often increasing in harder or higher-dimensional settings. Results also show that joint batch optimization and qLogEHVI can be competitive with or better than established alternatives, although improvements vary by problem.

  • Single-objective sequential BO: LogEI substantially outperforms EI and GIBBON on Ackley and Michalewicz, with the performance gap widening as dimensionality increases.JES performs slightly better than LogEI on Ackley but fails on Michalewicz and is almost two orders of magnitude slower than the other acquisition functions.
  • BO with Black Box Constraints: LogCEI outperforms naive CEI and converges faster than SCBO on four constrained engineering design problems.Its gains over CEI grow with problem dimensionality and the number of constraints; some results improve on quoted literature results using three orders of magnitude fewer function evaluations.
  • Parallel Expected Improvement with qLogEI: qLogEI improves parallel optimization over qEI, while jointly optimizing batch candidates can outperform sequential greedy optimization.The comparison uses the 16-dimensional Ackley function across varying batch sizes.
  • High-dimensional BO with qLogEI: qLogEI yields varying improvements across three high-dimensional problems, with significant gains on embedded Hartmann but not on SVM or Rover.On embedded Hartmann, qLogEI enables a canonical-GP BO model eventually to catch up with the SAAS-prior-equipped model.
  • Multi-Objective optimization with qLogEHVI: qLogEHVI consistently outperforms qEHVI and JES across batch sizes on two multi-objective problems.For the largest batch size on DTLZ2, qLogNEHVI improves later than the other methods but dominates their performance in later batches.

6 Discussion

LogEI’s benefits depend on the problem and surrogate: improvements are tied to concentrated high objective values, can emerge late or remain small, and may disappear with poor predictions.

  • On problem dimensionality: LogEI’s advantages grow with concentration of high objective values, not dimensionality itself; high ambient but low intrinsic dimensionality can yield little improvement over EI.The SVM problem in Figure 6 is given as an example.
  • Multi-Objective optimization with qLogEHVI: On two multi-objective problems, qLogEHVI consistently outperforms qEHVI and JES across batch sizes, although qLogNEHVI improves later for the largest batch on DTLZ2.The comparison uses hypervolume of the observed Pareto frontier.
  • On asymptotic improvements: LogEI may provide only small optimization gains or improvements that emerge in later iterations.Examples include log-objective results on the convex 10D sum of squares and q = 16 on DTLZ2.
  • On model quality: Poor surrogate predictions or uninformative uncertainty can prevent better acquisition values from improving Bayesian optimization performance.The paper cites Rover in Figure 6 as an example.
  • Replacing EI: The authors strongly suggest replacing EI variants with LogEI counterparts, while noting that EI dominance could indicate broader sub-optimality in the EI family.They attribute such gains to the exploratory quality of randomly distributed candidates in that case.

7 Conclusion

The paper develops numerically stable LogEI reformulations for improvement-based acquisition functions and shows that they preserve or approximate canonical optima while improving optimization. Its analyses address analytic and Monte Carlo settings, including asymptotic regimes and batch variants.

  • Conclusion: Across modified EI variants, careful reformulations substantially improve optimization, reduce dependence on brittle initialization, and do not meaningfully increase computational complexity.The results also show joint batch optimization can be competitive with, and sometimes exceed, sequential greedy selection.
  • Stable analytic LogEI: The analytic implementation is stabilized by factoring logarithms and using erfcx, log1mexp, expm1, and log1p in numerically stable computations.These implementations target cancellation and underflow in the negative-z regime.
  • Numerical Study of Acquisition Values: Naïve analytic EI becomes exactly zero for moderately negative z, whereas the log_h implementation retains quadratic asymptotic behavior suited to numerical optimization.Here z = (µ(x) − f*)/σ(x).
  • Equivalence of Optimizers: LogEI preserves the maximizers of EI when the maximum EI is positive, while avoiding numerical vanishing that impedes acquisition optimization.If EI is zero everywhere, both policies treat every point as a maximizer, although LogEI is undefined.
  • Asymptotic computation: For still larger negative z, the proposed method uses a Laurent expansion to stabilize the problematic final term in the analytic LogEI computation.The expansion is used in an asymptotic computation motivated by failures in existing robust branches and implementations.
  • Related implementations: Existing alternatives improve stability but retain limitations: RoBO can remain unstable for large negative z, while HEBO’s approximation omits a Gaussian normalization constant and has a discontinuity at z = −6.The proposed implementation is exact in the non-asymptotic regime and accurate to numerical precision asymptotically.
  • Monte Carlo LogEI: For Monte Carlo variants, the paper smooths zero-valued utilities and candidate maxima before transforming computations into log space.Softplus and a norm approximation introduce temperature-controlled approximation errors, while stable log-softplus handles a broad input range.

A.4 A Class of Smooth Approximations with Fat Tails for Larger Batches

The section introduces fat-tailed smooth approximations that replace exponential decay with polynomial decay to preserve useful approximation properties while improving numerical behavior for larger batches.

  • Motivation: Polynomially decaying approximations to ReLU, maximum, and indicator functions reduce the dynamic range that causes numerical difficulties in batch acquisition functions.The proposed tails decay as O(1/x^2) rather than exponentially as x → −∞.
  • Fat Softplus: The fat softplus preserves positivity, monotonicity, convexity, and a tight approximation to max(x, 0).Figure 11 uses temperature τ0 = 0.01.
  • Fat Maximum: The fat maximum addresses vanishing gradients when the batch range exceeds roughly 760 in double precision.Elements far below the maximum are increasingly likely to receive numerically zero gradients under logsumexp.
  • Fat Sigmoid: The fat sigmoid provides a positive, monotonic approximation to the constraint indicator with O(1/x^2) decay for negative inputs.A temperature parameter τ controls pointwise tightness to the Heaviside step function away from the origin.
  • Acquisition Extensions: The same numerical reformulations extend to noisy EI and parallel EHVI by smoothing improvements, batch maxima, and constraint indicators before taking logarithms.For qLogNEI, the main change from qLogEI is replacing the scalar incumbent with a sample-specific incumbent vector.

C Proofs

This section establishes approximation guarantees for the smooth and fat-tailed constructions, including bounds relating LogEI variants to their canonical acquisition functions.

  • Theorem 1: Theorem 1 bounds the relevant acquisition-function quantities using the optimality gap and maximal posterior standard deviation rather than posterior statistics at a specific point.The bound holds with probability 1 − δ.
  • qLogEI Guarantee: The approximation error of qLogEI relative to qEI is bounded for positive smoothing temperatures τ0 and τmax.The result is stated as a relative approximation guarantee.
  • Softplus Approximation: Softplusτ approximates ReLU with infinity-norm error log(2)τ.The approximation is everywhere above ReLU and converges to it asymptotically.
  • Fat-Tailed Guarantees: Approximation guarantees for the fat-tailed nonlinearities can be derived using analogous arguments.

D.1 Experimental details

The experiments use BoTorch implementations and compare canonical, proposed, and recent acquisition functions under repeated simulation with standardized modeling choices.

  • Experimental Setup: All simulations use 32 replicates, with error bars representing ±2 standard errors of the mean.The experiments use a Matérn-5/2 kernel with automatic relevance determination.

D.2 Additional Empirical Results on Vanishing Values and Gradients

Additional experiments show that vanishing acquisition values and gradients arise in realistic BO settings, while LogEI variants improve optimization across parallel, noisy, multi-objective, and high-dimensional problems.

  • Vanishing Values and Gradients: For most test points, a well-calibrated model’s mean prediction lies many standard deviations from the incumbent, making EI values and gradients vanish numerically.The replicate uses 60 training points and 50 randomly selected test points.
  • Parallel Optimization: qLogEI outperforms qEI on 16-dimensional Ackley, while joint batch optimization becomes increasingly competitive on Levy as batch size grows.
  • Noisy Optimization: qLogNEI improves over canonical noisy-EI counterparts as dimensionality and noise increase.The benchmark covers Hartmann 6d, Ackley 8d, and Ackley 16d.
  • Multi-Objective Optimization: qLogEHVI consistently outperforms qEHVI across six multi-objective test problems, with larger gaps in higher dimensions.The problems span 2–3 objectives and 2–30 dimensions, including three real-world-inspired tasks.
  • High-Dimensional Optimization: Combining TuRBO-1 with LogEI substantially improves performance on 50-dimensional Ackley with few evaluations, although Thompson sampling eventually performs better.Joint q = 50 optimization with qLogEI requires no random restarts for good performance.

D.7 Constrained Problems

LogEI achieved strong sample-efficient results on constrained design problems, including outperforming a literature result for pressure vessel design while using far fewer evaluations. Across the remaining problems, its performance was competitive but not uniformly better.

  • Pressure vessel design: 5651.8862 was LogEI’s best feasible pressure-vessel objective after 110 evaluations, versus 6059.946341 as the quoted literature best case.Its worst-case feasible objective was 5659.1108 across 16 runs, using almost three orders of magnitude fewer evaluations than the comparison study.
  • Welded beam: 1.7496 was LogEI’s best welded-beam objective after 110 evaluations, compared with 1.728226 from Coello and Montes.The result was lightly worse despite using three orders of magnitude fewer evaluations.
  • Tension-compression: 0.0129 was the feasible tension-compression value found by LogEI after 110 evaluations, compared with 0.012681 reported in the literature.The reported LogEI value was slightly higher than the comparison value.
  • Evaluation budget: These results show that Bayesian optimization can compete with or outperform a genetic algorithm while using only a tiny fraction of the sample budget.The paper emphasizes sample efficiency as especially relevant for physical systems.

D.8 Parallel Bayesian Optimization with cross-batch constraints

The section studies parallel Bayesian optimization when batch elements share a total resource constraint, using a constrained surrogate of a silver nanoparticle synthesis problem. Jointly optimized qLogEI with explicit constraints provided the additional gains, while initialization and numerical-stability choices also affected optimization behavior.

  • Problem setup: The silver nanoparticle synthesis task optimizes absorbance spectrum score over five parameters, including four component flow-rate ratios and total flow rate Qtot.The continuous surrogate was fitted from the experimental dataset using an RBF interpolator on the negative loss.
  • Problem setup: A cross-batch constraint limits total flow Qmax_tot because each syringe can deliver at most 1000µL/min.The constraint prevents all batch elements from simultaneously operating in the high-flow regime.
  • Results: qLogEI with proper batch-constrained optimization outperformed qEI under the same constraint treatment, whereas qLogEI did not outperform qEI with the random-Qtot heuristic.The comparison indicates that both LogEI and joint constraint-aware batch optimization contributed to the additional performance gain.
  • Experimental design: The experiment used batch size q = 3, five random starting points, 75 replicates, and uniform random sampling as the baseline.Error bars represent ± two standard errors of the mean, with shared random initial conditions across methods.
  • Experimental design: qEI and qLogEI were each evaluated with explicit batch constraints and with a heuristic that sampled total flow rates before optimizing with them fixed.The explicit optimizer used scipy’s SLSQP solver; the heuristic sampled flow rates uniformly from the constraint set.
  • Results: The study reports that both heuristic and properly constrained optimization substantially outperformed the purely random baseline.Additional gains over the other combinations required using LogEI together with proper constraints and joint batch optimization.
  • Numerical and initialization sensitivity: Smaller fixed τ values for the softplus operator typically improved optimization performance on the Ackley and sum-of-squares ablation problems.Choosing τ0 as low as 10^-6 was possible because all computations were transformed into log-space.
  • Numerical and initialization sensitivity: BoTorch’s Boltzmann initialization improved regret for all cases relative to uniformly random restart points, using 1024 initial candidates.The figure also examines sensitivity to initialization strategy and the number of multi-start points on 16-dimensional Ackley and Levy problems; higher negative regret is better.
Loading 2310.20708v3…