Adaptive Candidate Point Thompson Sampling for High-Dimensional Bayesian Optimization

Donney Fan; Geoff Pleiss

cs.LGApr 10, 2026

Adaptive Candidate Point Thompson Sampling for High-Dimensional Bayesian Optimization

Authors: Donney Fan, Geoff Pleiss

Organizations: University of British Columbia Vector Institute

Abstract

In Bayesian optimization, Thompson sampling selects the evaluation point by sampling from the posterior distribution over the objective function maximizer. Because this sampling problem is intractable for Gaussian process (GP) surrogates, the posterior distribution is typically restricted to fixed discretizations (i.e., candidate points) that become exponentially sparse as dimensionality increases. While previous works aim to increase candidate point density through scalable GP approximations, our orthogonal approach increases density by adaptively reducing the search space during sampling. Specifically, we introduce Adaptive Candidate Thompson Sampling (ACTS), which generates candidate points in subspaces guided by the gradient of a surrogate model sample. ACTS is a simple drop-in replacement for existing TS methods -- including those that use trust regions or other local approximations -- producing better samples of maxima and improved optimization across synthetic and real-world benchmarks.

Figures & tables

Figure 1: Optimization performance of medium-dimensional real-world optimization problems. ACTS consistently exhibits top performance (within two standard errors) and achieves high objective values earlier in optimization than other methods.

Figure 2: Optimization performance on several high-dimensional problems. ACTS ranks highly in all benchmarks, achieving top performance (within two standard errors) on all benchmarks, and outperforming RAASP (with significance) on MOPTA08, SVM, and Median Molecules 1. (Note that TuRBO does not consistently improve performance on all benchmarks, but the performance boost/regression it induces is consistent across all methods on a given benchmark.)

	ACTS-TuRBO (Ours)	RAASP-TuRBO	Pathwise	LogEI	SAASBO	BAxUS
Rover (60D)	$\mathbf{2.87\pm 0.85}$	$\mathbf{2.36\pm 0.94}$	$-0.33\pm 0.49$	$\mathbf{3.09\pm 0.44}$	$\mathbf{2.42\pm 1.01}$	$0.67\pm 1.29$
LassoDNA (180D)	$\mathbf{-0.28\pm 0.00}$	$\mathbf{-0.28\pm 0.00}$	$-0.30\pm 0.00$	$-0.29\pm 0.00$	$-0.29\pm 0.00$	$-0.29\pm 0.00$
MOPTA08 (124D)	$\mathbf{-215.81\pm 1.07}$	$-225.12\pm 1.46$	$-227.79\pm 1.51$	$-217.94\pm 0.67$	$\mathbf{-219.16\pm 2.34}$	$-240.85\pm 2.30$
SVM (388D)	$\mathbf{-0.04\pm 0.00}$	$-0.05\pm 0.00$	$-0.21\pm 0.00$	$-0.05\pm 0.00$	$-0.15\pm 0.02$	$-0.10\pm 0.00$
M. Mol. 1 (256D)	$\mathbf{0.30\pm 0.01}$	$\mathbf{0.28\pm 0.02}$	$0.27\pm 0.01$	$\mathbf{0.30\pm 0.01}$	—	$\mathbf{0.29\pm 0.01}$
M. Mol. 2 (256D)	$0.14\pm 0.00$	$0.13\pm 0.00$	$0.10\pm 0.01$	$\mathbf{0.19\pm 0.01}$	—	$\mathbf{0.20\pm 0.01}$

Table 1: Final objective values from ACTS vs. state-of-the-art methods on high-dim. benchmarks.

Figure 3: Batch optimization performance (

q=100

) of selected high-dimensional problems. ACTS achieves top results (within two standard errors) on all benchmarks.

Figure 4: ACTS increases candidate point density by shrinking search spaces. ACTS exhibits volumes similar to TuRBO without the direct use of trust regions in two BO runs of Rover, with and without TuRBO, up to the first restart.

Figure 5: ACTS produces greater TS maxima than other candidate policies on several benchmarks. We generate candidates from each policy, sample from the posterior 100 times, and aggregate over 10 models with standardized outputs.

Figure 6: Optimization performance of Sobol and RAASP policies with and without ACTS on high-dimensional objectives. RAASP consistently outperforms the poorly-performing Sobol policy. ACTS search spaces provide a significant performance boost to all methods, especially Sobol. This indicates the ACTS search spaces provide better fidelity for TS maximization than TuRBO trust regions.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

	Rover (60D)	MOPTA08 (124D)	LassoDNA (180D)	SVM (388D)
ACTS	0.53 ± 0.14	0.52 ± 0.10	0.53 ± 0.07	0.65 ± 0.12
RAASP	0.44 ± 0.06	0.45 ± 0.06	0.47 ± 0.05	0.53 ± 0.06
Cylindrical	0.75 ± 0.06	0.77 ± 0.06	0.80 ± 0.07	0.92 ± 0.07
Pathwise	1.57 ± 0.53	4.61 ± 2.24	6.09 ± 2.33	11.07 ± 2.93

Appendix

Table 2: Wallclock time (in seconds

\pm

2 std. err.) to propose a single candidate of selected TS methods.

	Rover (60D)	MOPTA08 (124D)	LassoDNA (180D)	SVM (388D)
ACTS	4.64 ± 0.30	4.58 ± 0.18	4.57 ± 0.06	4.73 ± 0.23
RAASP	3.93 ± 0.10	3.95 ± 0.10	3.96 ± 0.10	4.01 ± 0.10
Cylindrical	4.77 ± 0.10	4.79 ± 0.10	4.82 ± 0.11	4.93 ± 0.13
Pathwise	0.08 ± 0.04	0.12 ± 0.06	0.17 ± 0.08	0.36 ± 0.14

Appendix

Table 3: Mean peak memory usage (in GiB

\pm

2 std. err.) of selected TS methods.

Figure 7: Optimization performance of high-dimensional optimization problems without TuRBO . The TS methods exhibit strong performance compared to several non-TS benchmarks, though notably the LogEI and BAxUS baselines obtain significantly better performance on Median Molecules 2.

Figure 8: Optimization performance of high-dimensional optimization problems with TuRBO . When using TuRBO trust regions, the Thompson sampling methods’ optimization performance can be enhanced.

Figure 9: Ranking significance of selected TS methods. Left: Global setting. Right: TuRBO setting.

Figure 10: Optimization performance of selected high-dimensional benchmarks of small batches (

q=10

). ACTS achieves strong performance in all benchmarks compared to other TS methods, though potentially requiring a larger evaluation budget to overcome RAASP in SVM.

Figure 11: Optimization performance of selected high-dimensional benchmarks of medium-sized batches (

q=50

). ACTS ranks high among TS methods, with Pathwise finding the best performance in MOPTA08.

Figure 12: Global space filling sequence fail to fill the space of high-dimensional problems . We track the best observed objective value as the number of space filling points increases, up to a budget of

10^{6}

points. Aside from low-dimensional problems, the best found point remains far from the (approximate) optimal.

Figure 13: Mean euclidean distance (

\pm

one standard error) from

{\bm{x}}_{t}

{\bm{x}}_{t-1}

averaged over

t

and 10 runs (arbitrary units).

Figure 14: Travelling Salesman Problem tour (

\pm

one standard error) for several selected objectives and acquisitions (arbitrary units), averaged over 10 runs.

Figure 15: ACTS reduces the uncertainty appreciably with new observations . We aggregate over 10 runs, where the uncertainty in the gradient is measured by the trace of the covariance of the gradient distribution.

	$t=50$	$t=100$	$t=200$	$t=500$	$t=750$	$t=1000$
Rover (60D)	0.323	0.345	0.281	0.195	0.198	0.207
MOPTA08 (124D)	0.415	0.383	0.272	0.169	0.128	0.110
SVM (388D)	0.470	0.439	0.384	0.334	0.271	0.246
LassoDNA (180D)	0.446	0.407	0.376	0.213	0.233	0.240

Appendix

Table 4: ACTS search space reduces uncertainty while also permitting exploration. We compute the average minimum fraction of gradient samples that point in the minority direction. A number

p

in this table can be interpreted to say that, on average,

p

fraction of gradient samples point in the minority direction for any given dimension.

Figure 16: Optimization performance of ACTS when ablating on different search spaces . While the 1D line search spaces provide a comparable level of performance in some cases, it fails to be as performant as the proposed cone search space.

Figure 17: Candidate point quality of 1D line subspace. (See Figure 5 to compare). While the observed TS maxes are high, the objective function values at these maxima are highly concentrated.

Figure 18: Increased preference to large-magnitude gradient dimensions improves ACTS . Except when using “TopK”, the final performance remains competitive.

Figure 19: Increased preference to large-magnitude gradient dimensions improves ACTS . However, the effect is less pronounced when using TuRBO.

Figure 20: Optimization performance when ablating on the effective number of dimensions perturbed by RAASP.

Figure 21: Optimization performance when ablating on the effective number of dimensions perturbed by RAASP when using TuRBO.

Explore similar work

Mar 10, 2026

On Regret Bounds of Thompson Sampling for Bayesian Optimization

We study a widely used Bayesian optimization method, Gaussian process Thompson sampling (GP-TS), under the assumption that the objective function is a sample path from a GP. Compared with the GP upper confidence bound (GP-UCB) with established high-probability and expected regret bounds, most analyses of GP-TS have been limited to expected regret. Moreover, whether the recent analyses of GP-UCB for the lenient regret and the improved cumulative regret upper bound can be applied to GP-TS remains unclear. To fill these gaps, this paper shows several regret bounds: (i) a regret lower bound for GP-TS, which implies that GP-TS suffers from a polynomial dependence on

1/δ

with probability

δ

, (ii) an upper bound of the second moment of cumulative regret, which directly suggests an improved regret upper bound on

δ

, (iii) expected lenient regret upper bounds, and (iv) an improved cumulative regret upper bound on the time horizon

T

. Along the way, we provide several useful lemmas, including a relaxation of the necessary condition from recent analysis to obtain improved regret upper bounds on

T

Shion Takeno, Shogo Iwazaki

Nagoya University · MI-6 Ltd.

Bayesian Optimization Thompson Sampling

Ask PDF

Mar 11, 2026

A Tutorial Review of Bayesian Optimization with Gaussian Processes to Accelerate Stationary Point Searches

Building local surrogates to accelerate stationary point searches on potential energy surfaces spans decades of effort. Done correctly, surrogates can reduce the number of expensive electronic structure evaluations by roughly an order of magnitude while preserving the accuracy of the underlying theory, with the gain depending on oracle cost, search distance, and the availability of analytical forces. We present a unified Bayesian optimization view of minimization, single-point saddle searches, and double-ended path searches: all three share one six-step surrogate loop and differ only in the inner optimization target and the acquisition criterion. The framework uses Gaussian process regression with derivative observations, inverse-distance kernels, and active learning, and we develop optional extensions for production use, including farthest-point sampling with the Earth Mover's Distance, MAP regularization, an adaptive trust radius, and random Fourier features for scaling. Accompanying pedagogical Rust code demonstrates that all three applications use the same Bayesian optimization loop, bridging the gap between theoretical formulation and practical execution.

Rohit Goswami

Institute IMX and Lab-COSMO, École polytechnique fédérale de Lausanne · Institute IMX and Lab-COSMO, École polytechnique fédérale de Lausanne (EPFL), Station 12, CH-1015 Lausanne, Switzerland

Bayesian Optimization

Ask PDF

Apr 24, 2026

Rethinking Trust Region Bayesian Optimization in High Dimensions

Trust Region Bayesian Optimization (TuRBO) is an effective strategy for alleviating the curse of dimensionality in high-dimensional black-box optimization. However, inappropriate lengthscale design can cause the local Gaussian process (GP) model within the trust region to degenerate, leading to suboptimal performance in high dimensions. In this work, we show that TuRBO's local GP may remain either excessively complex or overly simple as the dimension

D

and trust region side length

L

vary. To address this issue, we propose a straightforward variant, AdaScale-TuRBO, which scales the GP lengthscale with both the problem dimension and trust region size, thereby preserving kernel geometry and maintaining consistent prior complexity. Empirically, we show that AdaScale-TuRBO can robustly outperform standard TuRBO and other popular high-dimensional BO methods on synthetic benchmarks and real-world trajectory planning tasks.

Wei-Ting Tang, Joel A. Paulson

University of Wisconsin–Madison

Bayesian Optimization Black-Box Optimization Trust-Region Optimization Gaussian Process Regression

Ask PDF