Adaptive Candidate Point Thompson Sampling for High-Dimensional Bayesian Optimization

This paper introduces Adaptive Candidate Thompson Sampling (ACTS), a method that improves high-dimensional Bayesian optimization by adaptively reducing the search space during candidate point generation using surrogate model gradients, thereby overcoming the sparsity issues inherent in fixed discretizations.

The Gist

Imagine you are trying to find the highest peak in a massive, foggy mountain range. You can't see the whole landscape, and every time you want to check the height of a spot, you have to send a very expensive, slow drone to fly there and report back. This is the problem of Bayesian Optimization: finding the best solution (the highest peak) with as few expensive checks as possible.

For a long time, computers have been good at this in small, simple mountains (low dimensions). But when the mountain range gets huge and complex (high dimensions, like tuning a machine learning model with thousands of settings), the old methods break down.

Here is a simple breakdown of the paper's solution, Adaptive Candidate Thompson Sampling (ACTS), using some everyday analogies.

The Problem: The "Grid Search" Trap

Imagine you are looking for the highest point in a 100-dimensional space. To do this, a computer usually picks a bunch of random spots to check (like dropping pins on a map).

• The Old Way: If you have a 2D map, you can drop 100 pins and cover the whole area nicely. But if you have a 100D map, you need astronomical numbers of pins just to cover the space even a little bit. It's like trying to find a specific grain of sand on a beach by dropping a few grains of sand randomly; you'll likely miss the spot entirely.
• The Result: The computer picks pins that are far apart, misses the "good" areas, and wastes its budget checking empty spots.

The Solution: ACTS (The "Smart Hiker")

The authors propose a new way to pick those pins. Instead of dropping them randomly everywhere, they use a "Smart Hiker" strategy.

1. The "Ghost Map" (The Posterior Sample)

The computer builds a "Ghost Map" (a mathematical model) of the mountain based on what it has seen so far. It knows where it's been, but it's guessing what the rest looks like.

• Old Method: The computer picks a random spot on this Ghost Map and says, "Let's go there!" But because the map is so big, the random spot might be in a valley or a flat plain, far from the peak.

2. The "Compass" (The Gradient)

This is the magic of ACTS. Before picking a spot, the computer asks the Ghost Map: "If I were standing right here, which way would the ground go UP?"

• It calculates a gradient (a compass needle pointing uphill).
• Crucially, this compass is based on a random guess of what the mountain looks like. Sometimes the compass points North, sometimes South. This randomness is good because it keeps the search from getting stuck in one spot.

3. The "Flashlight Cone" (The Adaptive Search Space)

Instead of looking at the entire mountain, the computer turns on a flashlight.

• It shines the flashlight only in the direction the compass is pointing.
• It creates a cone (a narrow, focused search area) starting from where it is now and stretching out in that uphill direction.
• The Analogy: Imagine you are in a dark forest. Instead of walking randomly in every direction, you look at your compass, see which way is "uphill," and only drop your pins in a narrow cone in front of you.

4. Packing the Pins (Density)

Because the computer is only looking at this tiny "cone" instead of the whole mountain, it can drop way more pins in that small area.

• The Benefit: It's like zooming in on a map. If you zoom in, you can see the details. By focusing only on the "uphill" direction, the computer finds the local peak of that specific "Ghost Map" much more accurately.

Why is this better?

• Efficiency: It stops wasting time checking flat areas or valleys.
• Accuracy: It finds the "best" spot on the computer's current guess much faster.
• Safety: You might worry, "What if the compass points the wrong way and we miss the real peak?" The paper proves that because the "Ghost Map" changes every time (it's random), the compass will eventually point in the right direction. It won't get stuck in a local loop forever; it will eventually explore the whole mountain.

The Real-World Result

The authors tested this on real problems, like tuning robot controllers and designing new molecules.

• Before: The computer was like a tourist wandering aimlessly in a huge city, hoping to stumble upon the best restaurant.
• With ACTS: The computer is like a food critic who asks a local for a direction, then focuses their search entirely on that specific neighborhood, checking every single restaurant there before moving on.

In short: ACTS solves the "too many choices" problem by using a smart, temporary compass to narrow the search down to the most promising direction, allowing the computer to look much more closely at the right place.

Technical Summary

1. Problem Statement

Bayesian Optimization (BO) is a powerful framework for optimizing expensive black-box functions. Thompson Sampling (TS) is a popular acquisition function that balances exploration and exploitation by maximizing a sample drawn from the posterior distribution of a surrogate model (typically a Gaussian Process, GP).

However, applying TS in high-dimensional spaces ($d \gg 10$) faces a critical bottleneck known as the curse of dimensionality:

• Intractability: Sampling a continuous function path from a GP posterior is computationally intractable.
• Discretization Necessity: Practical implementations must sample over a finite set of candidate points $\tilde{X}$.
• Sparsity: To adequately cover a high-dimensional space, the number of required candidate points grows exponentially with dimension $d$. Standard methods (e.g., Sobol sequences) typically use $\approx 10^4$ points. In high dimensions, this set becomes exponentially sparse, meaning the true maximum of the sampled function path is likely missed entirely.
• Limitations of Existing Fixes: Previous approaches attempt to mitigate this via:
  • Sparsity: Restricting perturbations to a few dimensions (e.g., RAASP).
  • Locality: Using trust regions (e.g., TuRBO).
  • Approximations: Using pathwise sampling or MCMC, which introduce their own approximation errors or scaling issues.

The paper argues that these methods do not fundamentally solve the density issue within the candidate set relative to the specific function sample being maximized.

2. Methodology: Adaptive Candidate Thompson Sampling (ACTS)

The authors propose Adaptive Candidate Thompson Sampling (ACTS), a method that dynamically constructs the candidate set based on the specific GP sample being evaluated, rather than using a fixed, pre-defined grid.

Core Insight

The key realization is that the candidate set $\tilde{X}$ does not need to be independent of the GP sample path $f$. Instead, the set can be adaptively constructed to concentrate points in regions where the sampled function $f$ is likely to attain its maximum.

Algorithmic Steps

1. Joint Sampling: ACTS leverages the fact that GPs are closed under linear operations. It constructs a joint posterior over the function values at candidate points ($f_{\tilde{X}}$) and the gradient at the current incumbent ($\nabla f(x_0)$).
2. Gradient Sampling: At each iteration, ACTS first samples the gradient of the posterior at the incumbent point: $\nabla f(x_0) \sim p(\nabla f(x_0) | D_t)$. This gradient represents the "ascent direction" for that specific function sample.
3. Adaptive Search Space Construction: Instead of sampling candidates over the entire domain $X$, ACTS defines a smaller, axis-aligned search space $T_{\nabla f(x_0)}$ rooted at $x_0$ and aligned with the sampled gradient:
   $$T_{\nabla f(x_0)} = \{ x_0 + v \odot \nabla f(x_0) \mid 0 \preceq v \in \mathbb{R}^d \} \cap X$$
   This creates a "cone" (or rectangular region) extending in the positive direction of the gradient.
   • Volume Reduction: In a $d$-dimensional space, this reduces the search volume by a factor of $2^d$ (removing half the space for each dimension). For $d=100$, this is a reduction of $\approx 10^{30}$.
4. Candidate Generation: A base policy (e.g., RAASP or Sobol) is applied within this reduced search space to generate $M$ candidate points.
5. Sampling: The GP posterior is sampled over these candidates conditioned on the sampled gradient, and the point maximizing this sample is selected as the next query.

Key Theoretical Guarantees

• Global Consistency: Despite focusing on a local, gradient-aligned region, the authors prove (Theorem 1) that ACTS maintains global consistency. Because the gradient is a random draw from the posterior, the search space is stochastic. Over infinite iterations, the algorithm is guaranteed to query points arbitrarily close to the global maximizer.
• Exactness: The resulting function sample is a valid realization of the GP posterior; the adaptation only changes where the sample is evaluated, not the distribution itself.

Compatibility

• Drop-in Replacement: ACTS can replace the candidate generation step in existing TS methods (e.g., RAASP, Cylindrical TS).
• Trust Regions: It is orthogonal to trust region methods (like TuRBO). ACTS can be combined with TuRBO by intersecting the trust region with the gradient-aligned cone, further increasing density.
• Batch Optimization: It extends naturally to batch settings by generating independent gradient samples and candidate sets for each batch member, promoting diversity.

3. Key Contributions

1. Novel Strategy: Introduces a paradigm shift from "fixed discretization" to "adaptive discretization" guided by the posterior gradient.
2. Theoretical Proof: Provides a proof of global consistency, addressing concerns that gradient-based local search might trap the optimizer in local optima.
3. Computational Efficiency: The overhead of sampling the gradient is negligible ($O(n_t^2 d)$) compared to the dominant cost of GP sampling ($O(M^3)$), making it scalable.
4. Empirical Superiority: Demonstrates that ACTS consistently outperforms state-of-the-art TS baselines (RAASP, Cylindrical TS, Pathwise TS) and non-TS methods (LogEI, SAASBO, BAxUS) across diverse benchmarks.

4. Experimental Results

The authors evaluated ACTS on a wide range of synthetic and real-world benchmarks, including:

• Medium Dimensions: Robotics control tasks (Lunar Lander, Robot Pushing, Swimmer, Hopper).
• High Dimensions: MOPTA08 (124D), SVM hyperparameter tuning (388D), LassoBench (up to 1000D), and molecule design (GuacaMol, 256D).

Key Findings:

• Performance: ACTS achieved the highest objective values in the majority of benchmarks, often significantly outperforming RAASP and Pathwise TS.
• Candidate Quality: Analysis showed that ACTS generates candidate points that are much closer to the true maximum of the GP sample path than other methods. This confirms that the adaptive density allows for a more accurate maximization of the acquisition function.
• Search Behavior: Contrary to the intuition that gradient-guided search is overly local, ACTS exhibited less locality (more exploratory trajectories) than TuRBO-based methods in some cases, due to the randomness of the gradient samples.
• Ablation Studies:
  • Using a 1D line search along the gradient performed worse than the proposed cone, suggesting the cone offers a better balance between volume reduction and search flexibility.
  • ACTS improved performance even when applied to naive Sobol sequences, closing the gap between simple and sophisticated candidate policies.

5. Significance

This paper addresses a fundamental limitation in high-dimensional Bayesian Optimization: the inability of standard Thompson Sampling to effectively discretize high-dimensional spaces. By aligning the candidate set with the gradient of the posterior sample, ACTS effectively "zooms in" on promising regions without sacrificing global convergence guarantees.

The method is significant because:

• It offers a principled, drop-in solution that improves existing TS implementations without requiring complex architectural changes.
• It bridges the gap between local gradient information and global optimization, proving that local heuristics can be used stochastically to achieve global optimality.
• It provides a new direction for future research in high-dimensional BO, moving beyond static candidate sets toward dynamic, sample-aware discretization.