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

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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-TuRBOPathwiseLogEISAASBOBAxUS
Rover (60D) 2.87±0.85\mathbf{2.87\pm 0.85}2.36±0.94\mathbf{2.36\pm 0.94}−0.33±0.49-0.33\pm 0.493.09±0.44\mathbf{3.09\pm 0.44}2.42±1.01\mathbf{2.42\pm 1.01}0.67±1.290.67\pm 1.29
LassoDNA (180D) −0.28±0.00\mathbf{-0.28\pm 0.00}−0.28±0.00\mathbf{-0.28\pm 0.00}−0.30±0.00-0.30\pm 0.00−0.29±0.00-0.29\pm 0.00−0.29±0.00-0.29\pm 0.00−0.29±0.00-0.29\pm 0.00
MOPTA08 (124D) −215.81±1.07\mathbf{-215.81\pm 1.07}−225.12±1.46-225.12\pm 1.46−227.79±1.51-227.79\pm 1.51−217.94±0.67-217.94\pm 0.67−219.16±2.34\mathbf{-219.16\pm 2.34}−240.85±2.30-240.85\pm 2.30
SVM (388D) −0.04±0.00\mathbf{-0.04\pm 0.00}−0.05±0.00-0.05\pm 0.00−0.21±0.00-0.21\pm 0.00−0.05±0.00-0.05\pm 0.00−0.15±0.02-0.15\pm 0.02−0.10±0.00-0.10\pm 0.00
M. Mol. 1 (256D) 0.30±0.01\mathbf{0.30\pm 0.01}0.28±0.02\mathbf{0.28\pm 0.02}0.27±0.010.27\pm 0.010.30±0.01\mathbf{0.30\pm 0.01}—0.29±0.01\mathbf{0.29\pm 0.01}
M. Mol. 2 (256D) 0.14±0.000.14\pm 0.000.13±0.000.13\pm 0.000.10±0.010.10\pm 0.010.19±0.01\mathbf{0.19\pm 0.01}—0.20±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=100q=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)
ACTS0.53 ± 0.140.52 ± 0.100.53 ± 0.070.65 ± 0.12
RAASP0.44 ± 0.060.45 ± 0.060.47 ± 0.050.53 ± 0.06
Cylindrical0.75 ± 0.060.77 ± 0.060.80 ± 0.070.92 ± 0.07
Pathwise1.57 ± 0.534.61 ± 2.246.09 ± 2.3311.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)
ACTS4.64 ± 0.304.58 ± 0.184.57 ± 0.064.73 ± 0.23
RAASP3.93 ± 0.103.95 ± 0.103.96 ± 0.104.01 ± 0.10
Cylindrical4.77 ± 0.104.79 ± 0.104.82 ± 0.114.93 ± 0.13
Pathwise0.08 ± 0.040.12 ± 0.060.17 ± 0.080.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=10q=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=50q=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 10610^{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 xt{\bm{x}}_{t} to xt−1{\bm{x}}_{t-1} averaged over tt 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=50t=50t=100t=100t=200t=200t=500t=500t=750t=750t=1000t=1000
Rover (60D)0.3230.3450.2810.1950.1980.207
MOPTA08 (124D)0.4150.3830.2720.1690.1280.110
SVM (388D)0.4700.4390.3840.3340.2710.246
LassoDNA (180D)0.4460.4070.3760.2130.2330.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 pp in this table can be interpreted to say that, on average, pp 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

CardsList

  1. On Regret Bounds of Thompson Sampling for Bayesian Optimization

    Mar 10, 2026Shion Takeno, Shogo IwazakiBayesian OptimizationThompson Sampling

    Nagoya University · MI-6 Ltd.

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

    Mar 11, 2026Rohit GoswamiBayesian Optimization

    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

  3. Rethinking Trust Region Bayesian Optimization in High Dimensions

    Apr 24, 2026Wei-Ting Tang, Joel A. PaulsonBayesian OptimizationBlack-Box Optimization

    University of Wisconsin–Madison