Risk Seeking Bayesian Optimization under Uncertainty for Obtaining Extremum

Shogo Iwazaki, Tomohiko Tanabe, Mitsuru Irie, Shion Takeno, Yu InatsuAISTATS 2024 · OpenReview

Abstract

Real-world black-box optimization tasks often focus on obtaining the best reward, which includes an intrinsic random quantity from uncontrollable environmental factors. For this problem, we formulate a novel risk-seeking optimization problem whose aim is to obtain the best possible reward within a fixed budget under uncontrollable factors. We consider two settings: (1) environmental model setting for the case that we can observe uncontrollable environmental variables that affect the observation as the input of a target function, and (2) heteroscedastic model setting for the case that any uncontrollable variables cannot be observed. We propose a novel Bayesian optimization method called kernel explore-then-commit (kernel-ETC) and provide the regret upper bound for both settings. We demonstrate the effectiveness of kernel-ETC through several numerical experiments, including the hyperparameter tuning task and the simulation function derived from polymer synthesis real data.

1. Introduction

In many real-world optimization tasks, the objective is not to achieve a high average performance but to find the single best possible outcome—a "home run"—within a limited budget. For instance, a materials scientist may only need to discover a record-breaking polymer once for a breakthrough. Similarly, in machine learning hyperparameter tuning, only the single best-performing model matters for deployment.

Standard Bayesian Optimization (BO) typically focuses on risk-neutral or risk-averse strategies, which maximize expected reward or balance reward with low variance. These methods often avoid "risky" areas of the search space that might occasionally yield a massive reward but usually produce poor results. As shown in Figure 1, an algorithm seeking the maximum expected reward (blue star) will miss regions that, while inconsistent, have the potential to yield the true global extremum (red star).

Comparison of risk-neutral vs. risk-seeking optimization objectives.

2. Methodology

The authors propose kernel-ETC, a kernelized version of the "Explore-Then-Commit" strategy. The algorithm operates in two distinct phases:

  1. Exploration Phase: The learner queries the controllable space to build a robust Gaussian Process (GP) surrogate model of the underlying function, reducing uncertainty about potential peaks.
  2. Exploitation (Commit) Phase: Based on the gathered knowledge, the learner "commits" to the single most promising input for the remainder of the budget to maximize the chance of hitting an extreme value.

The paper addresses two specific modeling challenges:

  • Environmental Model Setting: Uncontrollable factors (e.g., humidity) are treated as additional inputs to the surrogate model.
  • Heteroscedastic Model Setting: Uncontrollable factors are treated as input-dependent noise. The authors use a "repeated experiment" strategy to estimate noise levels at different points.

Crucially, the authors provide extreme regret bounds—a theoretical guarantee that the gap between the best possible reward and the best reward obtained by kernel-ETC shrinks as the budget increases.

3. Experimental Setup

The approach was evaluated using a mix of synthetic and real-world benchmarks:

  • Synthetic and RKHS Functions: Designed to mislead standard BO algorithms.
  • Polymer Synthesis Simulation: A 2D simulation derived from real experimental data, where the goal is to find a mixing ratio yielding high glass transition temperatures despite manufacturing uncertainties.
  • CNN Hyperparameter Tuning: Optimizing a 3-layer CNN on CIFAR-10, where noise arises from stochastic training elements like dropout and random initialization.

4. Key Results and Discussion

The kernel-ETC algorithm consistently outperformed standard BO (GP-UCB) and risk-averse methods across all benchmarks. In synthetic benchmarks, kernel-ETC's extreme regret dropped toward zero as the budget $T$ increased, while standard methods often plateaued.

Extreme regret performance on synthetic and RKHS benchmarks.

Key insights include:

  • Risk Formalization: In "one-shot" discovery, the distribution of the maximum of random variables is more important than the mean.
  • Efficiency of ETC: While standard BO is often preferred for its adaptivity, a structured Explore-Then-Commit approach is easier to analyze theoretically for extreme regret and performs remarkably well in risk-seeking settings.
  • Modeling Noise as a Signal: In the heteroscedastic setting, "noise" is part of the potential for an extreme reward. By explicitly modeling variance, the algorithm identifies regions where a "lucky" high-variance draw is likely to beat a "safe" low-variance peak.

In the CNN tuning task, kernel-ETC achieved a lower best validation loss ($1.446 \pm 0.005$) compared to GP-UCB ($1.457 \pm 0.006$).

5. Conclusion and Future Work

This work provides a theoretical and practical roadmap for optimizing systems plagued by uncontrollable environmental factors to achieve extreme outcomes. Future work includes addressing the scaling of uncontrollable factors, adaptive exploration ratios, and non-Gaussian noise distributions.

Summary updated

Abstract

Real-world black-box optimization tasks often focus on obtaining the best reward, which includes an intrinsic random quantity from uncontrollable environmental factors. For this problem, we formulate a novel risk-seeking optimization problem whose aim is to obtain the best possible reward within a fixed budget under uncontrollable factors. We consider two settings: (1) environmental model setting for the case that we can observe uncontrollable environmental variables that affect the observation as the input of a target function, and (2) heteroscedastic model setting for the case that any uncontrollable variables cannot be observed. We propose a novel Bayesian optimization method called kernel explore-then-commit (kernel-ETC) and provide the regret upper bound for both settings. We demonstrate the effectiveness of kernel-ETC through several numerical experiments, including the hyperparameter tuning task and the simulation function derived from polymer synthesis real data.
BibTeX
@inproceedings{iwazaki2024risk,
  author = {Shogo Iwazaki and Tomohiko Tanabe and Mitsuru Irie and Shion Takeno and Yu Inatsu},
  title = {{Risk Seeking Bayesian Optimization under Uncertainty for Obtaining Extremum}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=hYw7WiegHu},
}
Figure