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 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:
- 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}$).
- Monte Carlo (MC) Parallel LogEI (qLogEI): For batch optimization (sampling $q$ points at once), they use smooth approximations like
softplusand $p$-norms, all computed entirely in log-space. - Fat-Tailed Approximations: Standard
softplusstill 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. - 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.
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