Technical Summary: Optimal-Point Variance Reduction for Bayesian Optimization with Regret Guarantee

Problem Statement

Bayesian Optimization (BO) is a framework for optimizing expensive-to-evaluate black-box functions. While one-step lookahead methods, such as Entropy Search (ES) and Knowledge Gradient (KG), have demonstrated superior empirical performance by accounting for global utility, they suffer from two primary limitations:

1. Computational Intractability: They often rely on complex, computationally expensive nested optimizations or heuristic approximations (e.g., for conditional distributions given the optimal input or maximum value).
2. Lack of Theoretical Guarantees: Despite their practical efficacy, the theoretical characterization of one-step lookahead BO methods remains underdeveloped. Specifically, finite-sample regret guarantees for these methods are largely an open problem, and existing analyses often rely on assumptions (like submodularity of posterior variance) that do not hold in general.

Methodology

The paper proposes Optimal-Point Variance Reduction (OVR) and its regularized variant, Regularized OVR (ROVR). These are one-step lookahead BO methods designed to minimize the posterior variance (or standard deviation) at the optimal input $x^*$.

Core Mechanism

Unlike ES-based methods that maximize mutual information (requiring heuristic approximations for conditional distributions), OVR directly targets the expected posterior standard deviation at the optimum. The acquisition function (AF) for OVR is defined as:
$$\alpha_t(x) = \mathbb{E}_{x^*} [\sigma_t(x^* | x) \mid D_{t-1}]$$
where $\sigma_t(x^* | x)$ is the posterior standard deviation at the optimal point $x^*$ given a new observation at $x$.

Key Technical Features:

• Analytical Transformation: The authors show that the expectation over the observation $y_x$ can be removed analytically, simplifying the AF to an expectation solely over the optimal point $x^*$.
• Monte Carlo (MC) Approximation: Since the distribution of $x^*$ is intractable, OVR approximates the expectation using MC sampling. It generates $M_t$ posterior sample paths $g_t \sim p(f \mid D_{t-1})$, optimizes each to find sample optima $x^*_{t,m}$, and computes the AF as:
  $$\hat{\alpha}_t(x) = \frac{1}{M_t} \sum_{m=1}^{M_t} \sigma_t(x^*_{t,m} \mid x)$$
• Regularization (ROVR): To ensure exploration and achieve theoretical convergence, ROVR introduces a regularization term:
  $$\hat{\alpha}_t(x) = \frac{1}{M_t} \sum_{m=1}^{M_t} \sigma_t(x^*_{t,m} \mid x) - c_t \sigma_{t-1}(x)$$
  where $c_t \geq 0$ is a regularization parameter. This term penalizes low uncertainty, promoting the selection of inputs with high uncertainty (exploration).

Implementation Details

• Posterior Sampling: The method employs the pathwise conditioning and random Fourier feature approximation (Wilson et al., 2020, 2021) to generate approximate posterior sample paths efficiently.
• No Heuristics: Unlike Predictive ES (PES), Max-value ES (MES), or Joint ES (JES), OVR does not require heuristic approximations for conditional distributions given the optimal input or maximum value.

Key Contributions

The paper makes three primary contributions:

1. Proposal of OVR and ROVR: The authors introduce easy-to-implement one-step lookahead methods that minimize posterior variance at the optimal input. These methods rely only on posterior sampling and MC approximations, avoiding the heuristic approximations required by PES, MES, and JES.
2. Uniform MC Estimation Error Bounds: The paper provides theoretical uniform error bounds for the MC estimation of the acquisition function over the input domain.
   • For discrete domains, the error bound is $O(\sqrt{\log(|X|/\delta)/M_t})$.
   • For continuous domains, under Lipschitz continuity assumptions on the kernel, the error bound is $O(\sqrt{d \log(M_t)/M_t})$. This establishes that $M_t = \Omega(\log(t/\epsilon)/\epsilon^2)$ samples are sufficient for $\epsilon$-accuracy.
3. Regret Guarantee: The paper proves that ROVR achieves a vanishing Bayesian Expected Simple Regret (BSR) upper bound. The bound is comparable to existing results for other BO methods:
   $$\text{BSR}_T \leq \sqrt{\frac{C_1 \beta_T \gamma_T}{T}} + O\left(\frac{\beta_T^{1/2}}{T}\right) + O\left(\frac{1}{T c_T}\right) + O\left(\frac{1}{T} \sum_{t=1}^T \frac{\log M_t}{\sqrt{M_t} c_t}\right)$$
   where $\gamma_T$ is the maximum information gain and $\beta_T$ depends on the domain size and smoothness.

Experimental Results

The authors evaluated OVR and ROVR on synthetic functions, benchmark functions (Ackley, Hartmann), and emulators from the Olympus framework.

• Performance: In synthetic experiments with varying noise levels ($\sigma^2 = 10^{-4}$ and $\sigma^2 = 1$), OVR and ROVR consistently outperformed or were comparable to state-of-the-art methods including EI, UCB, TS, PIMS, JES, and MES.
• Robustness: Unlike JES and MES, which showed sensitivity to the number of MC samples (often getting stuck in local optima as sample counts increased due to heuristic modifications), OVR and ROVR demonstrated robust performance that stabilized or improved with more MC samples.
• Comparison: The methods showed superior performance particularly among one-step lookahead strategies (MES, JES), validating the effectiveness of the variance reduction approach without heuristic approximations.

Significance and Claims

The paper claims that OVR and ROVR bridge the gap between the practical efficacy of one-step lookahead strategies and their theoretical justification.

• Theoretical Advancement: By providing a vanishing regret bound for a one-step lookahead method without relying on submodularity assumptions (which are often violated), the work addresses a significant gap in the theoretical literature of BO.
• Practical Utility: The methods are computationally efficient, requiring only posterior sampling and MC approximations, making them more tractable than existing one-step lookahead approaches like KG or ES variants.
• Limitations: The authors acknowledge that the analysis of cumulative regret for one-step lookahead methods remains an open problem, as obtaining instantaneous regret bounds is difficult compared to bandit-based algorithms like UCB or TS. Additionally, the current analysis ignores the error introduced by posterior sampling approximations, which is left for future work.

In summary, the paper presents a theoretically grounded, computationally tractable one-step lookahead BO method that achieves vanishing simple regret while avoiding the heuristic approximations that plague existing entropy-based approaches.