Optimizing Posterior Samples for Bayesian Optimization via Rootfinding

Taiwo A. Adebiyi, Bach Do, Ruda Zhang

TL;DR

Researchers from the University of Houston have introduced TS-roots, a method that finally makes optimizing posterior samples in Bayesian Optimization (BO) efficient and scalable. By exploiting the mathematical property of "separability" and using univariate rootfinding to pick intelligent starting points, the algorithm breaks the curse of dimensionality, allowing Thompson Sampling to outperform traditional favorites like Expected Improvement (EI) in high-dimensional spaces.

What Problem Does This Paper Address?

Bayesian Optimization is the gold standard for optimizing "expensive" black-box functions—think of tuning a multi-million dollar chemical process or a massive neural network where every "test" costs significant time or money.

BO works in two loops:

  1. The Outer Loop: Deciding where to sample the expensive function next.
  2. The Inner Loop: Optimizing an "acquisition function" to find that next best point.

The "Inner Loop" is a hidden bottleneck. If you use Thompson Sampling (TS)—which involves drawing a sample path from a Gaussian Process posterior—you end up with a function that is incredibly "wiggly," non-convex, and full of local traps. In high dimensions, finding the global maximum of this wiggly sample is "catastrophically difficult." Most practitioners resort to random restarts or genetic algorithms, which either miss the global optimum or become agonizingly slow as dimensions increase.

Methods

The authors propose TS-roots, which approaches the inner-loop optimization not as a random search, but as a targeted strike. Their approach relies on three key pillars:

  • Pathwise Conditioning: They decompose the posterior sample into two parts: a prior sample (which represents our initial beliefs) and a data adjustment term (which pulls the sample toward observed data).
  • Exploiting Separability: By choosing a separable GP prior, the $d$-dimensional prior sample becomes a product of $d$ independent 1D functions. This is the "secret sauce." Instead of searching a $d$-dimensional haystack, they solve $d$ simple 1D problems.
  • Global Rootfinding: They use Chebyshev polynomial approximation to find all the roots of the derivatives of these 1D functions. This allows them to identify the exact local minima of the prior sample.
  • Smart Starting Points: Instead of thousands of random starts, they pick a tiny handful of "judicious" starting points:
  • Exploration Set ($S_e$): The best local minima of the prior sample.
  • Exploitation Set ($S_x$): The locations of existing data points.

They also introduce a Sample-Average Posterior Function, a new acquisition function that allows users to explicitly tune the balance between exploration and exploitation by averaging multiple samples.

Datasets

The method was evaluated on a battery of challenging synthetic benchmarks and one real-world engineering problem:

  • Synthetic Benchmarks: 2D Schwefel, 4D Rosenbrock, 10D Levy, 16D Ackley, and 16D Powell functions. These are standard "torture tests" for optimization algorithms due to their many local optima or flat plateaus.
  • Real-World Problem: A Ten-bar Truss engineering design problem. The goal is to minimize the weight and displacement of a structural truss by adjusting the cross-sectional areas of ten different members.

Key Insights and Ideas

  • The Prior as a Map: The core "aha moment" is that the prior sample's landscape is a fantastic surrogate for the posterior sample's landscape. The local minima of the prior are usually very close to the local minima of the posterior.
  • Quality over Quantity: Remarkably, the authors found that starting a gradient-based optimizer from just one point in the exploration set and one in the exploitation set often discovers the global optimum. This is a massive efficiency gain over traditional "multistart" methods that use hundreds of random points.
  • Linear Scaling: Because the rootfinding happens in 1D, the computational cost scales linearly with the number of dimensions ($d$), effectively "breaking" the curse of dimensionality that usually makes high-dimensional BO a nightmare.

Key Results

  • Superior Performance: In the outer-loop optimization, TS-roots outperformed standard methods like Expected Improvement (EI) and Lower Confidence Bound (LCB) on the Schwefel, Ackley, and Powell functions.
  • Inner-Loop Precision: Compared to genetic algorithms and random multistart, TS-roots found significantly better (lower) acquisition values in a fraction of the time.
  • Scalability: While random search performance tanked as dimensions rose (e.g., moving from 2D to 16D), TS-roots remained robust and efficient.
  • Boosting Other Methods: The authors showed that TS-roots could even improve other advanced BO strategies like Max-value Entropy Search (MES) by providing higher-quality samples of the maximum value.

Limitations and Future Work

  • Separability Assumption: The current algorithm requires the GP prior to be separable. While this is a common choice in the BO community, it excludes certain complex, non-separable kernels.
  • Spectral Representations: The authors aim to extend the method to other spectral representations (like those based on Bochner’s theorem) to handle a wider variety of GP models.
  • Failure Analysis: Future work will involve a deeper theoretical study into the exact probability of the algorithm failing to find the global optimum and how that relates to the chosen "subset sizes" for starting points.

Summary updated

BibTeX
@inproceedings{adebiyi2025optimizing,
  author = {Taiwo A. Adebiyi and Bach Do and Ruda Zhang},
  title = {{Optimizing Posterior Samples for Bayesian Optimization via Rootfinding}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=I6UbnkUveF},
}
Figure