Knowing The What But Not The Where in Bayesian Optimization

Vu Nguyen, Michael A. Osborne

Introduction

Standard Bayesian Optimization (BO) is designed to find both the maximum value of a black-box function and the exact input location where it occurs. However, in many real-world optimization tasks, we are not searching entirely in the dark—we already know the best possible outcome (the "what"), but we do not know the parameters to achieve it (the "where"). For instance, when tuning hyperparameters for a classifier, the maximum possible accuracy is strictly 100%. In Reinforcement Learning (RL), many benchmark environments have a known maximum reward.

Standard BO treats these scenarios like any other black-box function, ignoring this valuable prior knowledge. This oversight leads to wasted queries where the model explores regions that are mathematically impossible (e.g., predicting an accuracy of 110%) or fails to exploit the known target. This paper introduces a framework that bakes the known optimum value ($f^*$) directly into the surrogate model and the decision-making process, allowing the optimization to reach the optimum significantly faster.

Methodology

To bridge the gap between standard BO and known-optimum problems, the authors propose two major innovations: a Transformed Gaussian Process and novel acquisition functions.

Transformed Gaussian Process (TGP)

Standard Gaussian Processes (GPs) can predict values anywhere, often exceeding known logical limits. To enforce the constraint that the function never exceeds the known maximum $f^*$, the authors apply a mathematical transformation:

$$f(x) = f^* - \frac{1}{2}g^2(x)$$

where $g(x)$ is a standard GP. Because the squared term is always non-negative, $f(x)$ is strictly guaranteed to be $\leq f^*$. To keep the mathematics tractable—since squaring a GP makes it non-Gaussian—they utilize a Taylor expansion linearization trick to approximate the posterior as a Gaussian.

Comparison of standard GP and Transformed GP

This transformation creates a "ceiling effect." The model lifts its predictions toward the known maximum in promising areas but strictly prevents the mean or confidence intervals from crossing that ceiling, resulting in a much more informative surrogate model.

New Acquisition Functions

With the TGP in place, the authors introduce two acquisition functions tailored for known optima:

  • Confidence Bound Minimization (CBM): Inspired by the Upper Confidence Bound (UCB) algorithm, CBM flips the traditional logic. Instead of searching for the highest possible value, it searches for the location where the predicted mean is closest to $f^*$ and the uncertainty is low.
  • Expected Regret Minimization (ERM): This is the known-optimum counterpart to Expected Improvement (EI). It calculates the expected difference between the known $f^*$ and the function value at a candidate point, choosing the point that minimizes this "regret." Crucially, ERM is parameter-free, making it highly robust.

Experiments and Key Results

The researchers evaluated their approach across synthetic benchmarks (Branin, Hartmann, Alpine1, gSobol) and real-world tasks, including XGBoost hyperparameter tuning on the Skin Segmentation dataset (target accuracy 100%) and Deep Reinforcement Learning tuning for CartPole-v0 (known maximum reward of 200).

Key Insights: * ERM Outperforms Baselines: Across almost all benchmarks, Expected Regret Minimization (ERM) outperformed standard BO methods (EI and UCB) and other recent methods designed to handle known optima (like MES). * Faster Convergence: In the XGBoost tuning task, ERM reached near-perfect accuracy in significantly fewer iterations. On the CartPole problem, the ERM approach reached the optimal reward of 200 within just 20 iterations, while standard methods continued to fluctuate at lower reward levels. * High-Dimensional Efficiency: The benefit of knowing $f^*$ becomes increasingly pronounced as problem dimensionality grows. In 10D synthetic problems, the proposed methods successfully found the optimum while standard BO struggled to gain traction. * Smarter Exploration:* Standard BO often over-explores because it doesn't know how close it is to the peak. By knowing $f^*$, ERM recognizes when it has likely found the optimum and stops wasting resources, or conversely, abandons regions where even the best-case prediction falls far below $f^*$.

Limitations and Future Work

While highly effective, the framework has limitations. The authors noted a sensitivity to misspecification: if an incorrect $f^*$ is provided, performance drops. Under-specifying the maximum is particularly dangerous, as the acquisition function can get "stuck" in a sub-optimal region, falsely believing it has reached the peak.

Future work could extend this approach to handle noisy observations or scenarios where the maximum is only known within a certain range. Additionally, extending the framework to "batch" BO—evaluating multiple points simultaneously—would be a valuable next step for parallel computing environments.

Summary updated

Abstract

Bayesian optimization has demonstrated impressive success in finding the optimum input x$\ast$ and output f$\ast$ = f(x$\ast$) = max f(x) of a black-box function f. In some applications, however, the optimum output is known in advance and the goal is to find the corresponding optimum input. Existing work in Bayesian optimization (BO) has not effectively exploited the knowledge of f$\ast$ for optimization. In this paper, we consider a new setting in BO in which the knowledge of the optimum output is available. Our goal is to exploit the knowledge about f$\ast$ to search for the input x$\ast$ efficiently. To achieve this goal, we first transform the Gaussian process surrogate using the information about the optimum output. Then, we propose two acquisition functions, called confidence bound minimization and expected regret minimization, which exploit the knowledge about the optimum output to identify the optimum input more efficient. We show that our approaches work intuitively and quantitatively better performance against standard BO methods. We demonstrate real applications in tuning a deep reinforcement learning algorithm on the CartPole problem and XGBoost on Skin Segmentation dataset in which the optimum values are publicly available.
BibTeX
@inproceedings{nguyen2020knowing,
  author = {Vu Nguyen and Michael A. Osborne},
  title = {{Knowing The What But Not The Where in Bayesian Optimization}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=rn50MVcNCo},
}
Figure