In Bayesian Optimization (BO), high-dimensional search spaces present a significant challenge. As dimensionality increases, the volume of the search space grows exponentially, making accurate modeling of the objective function difficult. A common mitigation strategy is Additive BO, which assumes the objective function $f(x)$ can be decomposed into a sum of lower-dimensional sub-functions: $f(x) = \sum_{i=1}^M f_i(x_i)$.
The Challenge of Bilateral Uncertainty
While the additive assumption simplifies the mean of the Gaussian Process (GP) surrogate, it complicates the uncertainty modeling. Because we only observe the total sum of the sub-functions, the individual components $f_i$ become statistically coupled. This correlation is known as Bilateral Uncertainty (BU).
Most existing Additive BO frameworks ignore BU to maintain computational tractability, treating sub-functions as independent during the acquisition phase. This research investigates whether accounting for these correlations—untangling the sub-functions—leads to better optimization performance.
Methodology: Exact vs. Approximate Sampling
The research focuses on Thompson Sampling (TS), an acquisition rule where a function is drawn from the posterior and minimized to find the next sample point. Two primary approaches are compared:
- Exact Method (
ts): Uses an autoregressive sampling scheme that respects BU by conditioning each sub-function sample on the residuals of the others. This method is computationally efficient, with a complexity of $O(M(N + B^*)^3)$. - Approximate Method (
ats): The standard baseline that ignores BU, sampling each sub-function independently from its marginal posterior.
As visualized above, accounting for bilateral uncertainty significantly alters the predictive variance and the resulting posterior draws. Theoretically, the exact method provides a more faithful representation of the search space, which should lead to a better exploration-exploitation trade-off.
Empirical Findings
The methods were evaluated across 15 test functions, ranging from synthetic benchmarks (Ackley, Rastrigin) to complex simulators like Robot Push (14D) and cosmological inference problems (up to 25D).
The results yielded a surprising insight: despite the mathematical elegance and theoretical superiority of the exact method, the approximate method performs nearly as well in practice. Across 1,500 trials, the exact method showed only a slight statistical edge in sequential sampling, which vanished entirely in batch settings (batch size 10). The extra information provided by bilateral uncertainty is often drowned out by general noise and model mismatch inherent in BO.
Conclusion
The study concludes that while bilateral uncertainty is a real phenomenon in additive modeling, the common practice of ignoring it is "sufficient for BO in practice," even with small evaluation budgets. For practitioners, this suggests that simpler, independent sampling methods remain a robust and computationally efficient choice for high-dimensional additive optimization.
Summary updated