Unexpected Improvements to Expected Improvement for Bayesian Optimization

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

Expected Improvement (EI) has long served as the default acquisition function in Bayesian Optimization (BO). Since its introduction decades ago, it has been the standard mathematical tool that tells an algorithm where to sample next. However, in recent years, EI has been losing its luster, frequently outperformed by newer, more complex methods.

A recent paper from researchers at Meta, titled "Unexpected Improvements to Expected Improvement for Bayesian Optimization," suggests that the problem isn't with EI’s underlying logic, but with its numerical implementation. By simply changing how we calculate EI, we can unlock performance that matches or even beats current state-of-the-art methods.

TL;DR

The classic Expected Improvement (EI) acquisition function often fails because its values and gradients "vanish" (become numerically zero) in high dimensions or as more data is collected. The authors introduce LogEI, a family of reformulations that operate in log-space to maintain healthy gradients. This allows standard optimizers to find significantly better points, revitalizing EI as a top-tier method.

The Problem: Vanishing Gradients in Numerical Optimization

Bayesian Optimization works by building a probabilistic "surrogate" model (usually a Gaussian Process) of an expensive black-box function. We then maximize an acquisition function (like EI) to find the next best point to evaluate.

The catch? Maximizing the acquisition function is itself an optimization problem. The authors identify a "numerical pathology": in many regions of the search space, the value of EI is so tiny that it rounds to exactly zero in standard floating-point precision. When the value is zero, the gradient is also zero.

As more data points are added or dimensions increase, the fraction of the search space with vanishing gradients approaches 100%.

As illustrated above, as the number of training points ($n$) or the dimensionality ($d$) grows, the gradients of EI vanish across almost the entire domain. This renders gradient-based optimizers (like L-BFGS-B) useless, effectively turning the search into a blind random guess.

The Solution: LogEI

The core solution is LogEI. Instead of optimizing $EI(x)$, the authors propose optimizing $\log(EI(x))$. While mathematically the optima are identical, the numerical landscape is transformed from a flat "zero-plain" into a manageable slope.

The paper introduces several key technical innovations to make this work in practice:

  1. Analytic LogEI: A robust "three-branch" implementation for the standard sequential case. It uses a new asymptotic expansion to accurately compute the log-improvement even when the probability of improvement is astronomically small (e.g., $10^{-100}$).
  2. Monte Carlo (MC) Parallel LogEI (qLogEI): For batch optimization (sampling $q$ points at once), they use smooth approximations like softplus and $p$-norms, all computed entirely in log-space.
  3. Fat-Tailed Approximations: Standard softplus still leads to vanishing gradients in large batches. To counter this, they introduced a novel "fat-tailed" version based on the Cauchy distribution that ensures gradients stay alive even for very sub-optimal candidates in a batch.
  4. Broad Extension: They applied these "Log" principles to Constrained EI (CEI) and Expected Hypervolume Improvement (EHVI) for multi-objective optimization.

Key Insights and Results

The authors evaluated LogEI across a diverse set of benchmarks, ranging from synthetic functions (Ackley, Michalewicz) to real-world engineering tasks (Rover trajectory planning, Lunar Lander control, and vehicle safety optimization).

  • Optimization > Formulation: The perceived "weakness" of EI in recent literature is often an artifact of poor numerical optimization rather than a flaw in the EI logic itself.
  • The "Stalling" Effect: Standard EI often "stalls" after a certain number of iterations. This isn't because it has found the global optimum, but because the optimizer can no longer find a path to improvement due to vanishing gradients.
Comparison of Regret and Acquisition values. Standard EI stalls as its acquisition values drop and become numerically unstable, while LogEI maintains a smooth path.

The results are striking. On the 10D Sum-of-Squares problem, standard EI stalls almost immediately, while LogEI continues to make steady progress toward the optimum. In high-dimensional engineering problems, LogCEI (the constrained version) achieved better results in 110 evaluations than previous genetic algorithm methods achieved in 80,000 evaluations—a nearly 1,000x improvement in sample efficiency. Furthermore, LogEI variants consistently matched or outperformed modern SOTA methods like GIBBON and JES across almost all benchmarks.

Limitations and Future Work

The authors note that while LogEI fixes the numerical issues, it cannot fix a poor underlying surrogate model. If your Gaussian Process is a bad fit for the data (e.g., using a smooth kernel for a highly non-differentiable function), LogEI will still struggle to find the true optimum.

Future work could involve applying these log-space numerical tricks to other classes of acquisition functions, such as information-theoretic methods, which may suffer from similar (though perhaps less acute) numerical challenges.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ament2023unexpected,
  author = {Sebastian Ament and Samuel Daulton and David Eriksson and Maximilian Balandat and Eytan Bakshy},
  title = {{Unexpected Improvements to Expected Improvement for Bayesian Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=1OFbSTb2aj},
}
Figure