🤖 machine learning

Beyond Objective-Based Improvement: Stationarity-Aware Expected Improvement for Bayesian Optimization

This paper introduces Expected Improvement via Gradient Norms (EI-GN), a novel Bayesian Optimization acquisition function that enhances search efficiency by incorporating first-order stationarity conditions into the improvement criterion, thereby addressing the limitations of traditional Expected Improvement in regions where objective-value improvement signals vanish.

Original authors: Joshua Hang Sai Ip, Georgios Makrygiorgos, Ali Mesbah

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Joshua Hang Sai Ip, Georgios Makrygiorgos, Ali Mesbah

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the highest peak in a vast, foggy mountain range, but you can only take a few steps at a time, and every step costs you a lot of energy. This is what Bayesian Optimization does: it tries to find the best solution to a complex problem (like tuning a robot or designing a new material) without wasting time testing every single possibility.

The most common tool used for this is called Expected Improvement (EI). Think of EI as a hiker who only looks at the height of the ground. If a spot is higher than where they are now, they get excited and go there. If it's lower, they ignore it.

The Problem: The "Flatland" Trap

The paper points out a flaw in this "height-only" strategy. Imagine you are standing on a wide, flat plateau. To your left and right, the ground is exactly the same height as where you stand.

The Old Way (EI): The hiker looks around, sees no higher ground, and thinks, "There's no point moving." The signal to move vanishes. The hiker gets stuck in a loop, checking the same flat spot over and over, or wandering aimlessly because the "height" metric gives no useful information.
The Reality: Even if the height isn't changing, the slope might be. You might be standing on a flat spot that is actually the top of a small hill, or you might be on a flat stretch leading toward a much bigger mountain. The old method ignores the slope.

The Solution: EI-GN (The "Slope-Smart" Hiker)

The authors propose a new tool called EI-GN (Expected Improvement via Gradient Norms).

Instead of just asking, "Is this spot higher?" EI-GN asks two questions:

"Is this spot higher?" (The old question).
"Is this spot flatter?" (The new question).

The Analogy of the "Smoothness Penalty":
Imagine you are looking for the perfect spot to set up a tent.

Old Method: You only care about the view (the height). If the view is the same, you don't care.
New Method (EI-GN): You care about the view, but you also get a bonus if the ground is perfectly flat and stable. If you find a spot that is slightly lower than your current one, but the ground is incredibly flat (meaning you are very close to a peak or a stable valley), EI-GN says, "Hey, this is actually a great improvement because it's so stable!"

By valuing flatness (which mathematicians call "stationarity"), the hiker is guided toward the tops of hills even when the view hasn't changed yet. It keeps the search moving in flat areas where the old method would have given up.

How It Works (Without the Math)

The paper explains that they created a new "score" for every location. This score combines the height of the mountain with a penalty for how "bumpy" the ground is.

If the ground is bumpy (steep slopes), the score goes down.
If the ground is flat (near a peak), the score goes up.

They proved mathematically that this new score can be calculated quickly and easily. They also showed that this doesn't require building a more complicated map of the mountains; it just changes how the hiker decides where to walk next.

What They Found

The authors tested this new method on several "fake mountains" (standard computer test problems) and found:

In bumpy, complex terrain: It worked much better than the old method, finding the highest peaks faster.
In flat terrain: It didn't get stuck. While the old method would stop moving because the height didn't change, EI-GN kept moving because it was chasing the "flatness" signal.
In a Robot Control Test: They used it to teach a robot how to balance a pole. The robot learned faster using EI-GN than with the old method or standard robot-learning tricks.

The Bottom Line

The paper introduces a smarter way to search for the best solution. Instead of only looking for "higher" results, it also looks for "flatter" results. This prevents the search from getting stuck in boring, flat areas and helps it find the true best spots more efficiently, even when the "height" doesn't seem to be changing.

Technical Summary: Stationarity-Aware Expected Improvement for Bayesian Optimization

Problem Statement
Bayesian Optimization (BO) is a standard framework for optimizing expensive black-box functions, typically relying on Expected Improvement (EI) as a primary acquisition function (AF). While EI is empirically successful, it is fundamentally agnostic to first-order optimality conditions, relying solely on the potential for objective-value improvement. Consequently, in regions where the objective function is flat or near-stationary, the EI signal can vanish, leading to over-exploitation of local basins and a failure to guide exploration effectively. Although gradient information is often available in practical settings (e.g., policy gradients in control, adjoint sensitivities in PDEs, hypergradients in machine learning) at negligible cost, existing gradient-enhanced BO methods primarily focus on incorporating gradients into the surrogate model to improve predictive accuracy. This approach often incurs high computational complexity due to modeling cross-correlations between function values and derivatives. Conversely, leveraging gradient information directly within the acquisition function remains under-explored.

Methodology
The authors propose Expected Improvement via Gradient Norms (EI-GN), a novel acquisition function that extends the improvement principle to incorporate first-order stationarity.

Auxiliary Objective: Instead of modifying exploration heuristics, the method generalizes the definition of "improvement." It defines an auxiliary objective function $g(x)$ that augments the original objective $f(x)$ with a soft penalty on the gradient norm:
$g(x) = f(x) - \alpha \|\nabla f(x)\|_2^2$
where $\alpha \geq 0$ is a hyperparameter. This formulation treats the gradient norm as a soft penalty for deviations from stationarity, encouraging the search to favor regions that are either high-performing or close to stationary points.
Acquisition Formulation: The method defines Expected Improvement on this auxiliary objective, denoted as $EI_g$ . However, computing $EI_g$ directly is intractable due to the coupling of function values and gradient norms. The authors derive a tractable lower bound using the Positive Part Inequality:
$EI_g(x) \geq EI_f(x) - \alpha E I_s(x)$
where $EI_f$ is the standard EI on the objective, and $EI_s$ is an EI-style term measuring improvement in stationarity (reduction in gradient norm).
Tractable Approximation (EI-GN): To make the method practical, the authors derive a closed-form expression for a tractable approximation of the stationarity term, $E I_s$ . By assuming independent Gaussian Process (GP) models for the objective and its partial derivatives (avoiding the $O((d+1)^3N^3)$ complexity of joint models), they utilize a whitening transformation to decouple the norm-based truncation. This allows the expectation to be computed via separable truncated moments, resulting in the final acquisition function:
$EI\text{-}GN(x) = EI_f(x) - \alpha E I_s(x)$
This formulation provides two pathways for improvement: increasing the objective value or reducing the gradient norm.

Key Contributions

Novel Acquisition Function: The paper introduces EI-GN, which applies the improvement principle to a stationarity-aware auxiliary objective, extending improvement-based acquisition beyond pure objective-value criteria.
Theoretical Derivation: The authors derive a lower bound for the expected improvement on the auxiliary objective and provide a tractable, closed-form expression (EI-GN) that instantiates these principles under Gaussian posteriors.
Computational Efficiency: By utilizing independent GP models for the objective and gradients, the method avoids the computational burden of joint derivative modeling while still leveraging gradient information to reshape the acquisition landscape.

Experimental Results
The paper evaluates EI-GN across several experimental regimes:

Synthetic Benchmarks: On standard functions (Shekel, Hartmann, Griewank, Ackley) with varying dimensions, EI-GN consistently outperforms or matches baselines (EI, LogEI, UCB, CMA-ES). It shows particular advantage in functions with flat or oscillatory structures where standard EI signals vanish.
GP Samples: In both within-model (idealized) and out-of-model (mismatched hyperparameters) comparisons, EI-GN demonstrates robust performance gains over standard EI-family baselines. This confirms that the gradient-based signal guides optimization effectively even when surrogate models are imperfect.
Gradient Ablation: Comparisons with methods that incorporate gradients into the surrogate model (joint GPs) versus the acquisition function show that these approaches are orthogonal. Combining both (dEI-GN) yields the strongest results, indicating that acquisition-level and surrogate-level improvements address complementary aspects of the optimization problem.
Policy Search: In reinforcement learning tasks (Acrobot and CartPole), EI-GN is compared against local gradient methods (REINFORCE) and standard EI. EI-GN achieves higher sample efficiency and more reliable convergence to high-reward policies, particularly in scenarios where local methods get stuck in local basins.

Significance and Claims
The paper claims that EI-GN provides a richer and more informative notion of improvement by embedding progress toward stationarity into the acquisition criterion. The authors assert that this approach allows the acquisition landscape to remain informative even in regimes where standard EI provides little signal (e.g., flat regions or near-stationary points). The method is presented as a principled extension of the EI framework that leverages available gradient information without the computational overhead of complex joint surrogate modeling. The empirical results suggest that EI-GN offers consistent gains over baseline methods, particularly in challenging landscapes where traditional objective-value-based improvement criteria are insufficient.