PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast Bayesian Optimization Through Linear Models

Colin Doumont, Henry Moss, Philipp Hennig

arXiv:2610.29580v1cs.LG

TL;DR

BO can be too slow when evaluations are cheap, leaving practitioners to choose faster black-box optimizers. The paper exploits linear structure to accelerate BO for continuous and combinatorial inputs, and reports strong performance on a broader speed-performance frontier. Its methods extend BO to settings with evaluations as cheap as 0.1 seconds, subject to the paper's stated scope limits.

  • Problem

    BO methods can take multiple minutes to choose an acquisition, making algorithm overhead a major cost when black-box evaluations are cheaper and motivating use of faster, less sample-efficient optimizers such as CMA-ES.

    Source: §1 · p. 1

  • Method

    The paper exploits linear structure to speed hyperparameter fitting and acquisition optimization, extending gradient-free methods across continuous and combinatorial inputs.

    Source: §1 · pp. 1–2

  • Results

    Fast BO methods consistently cover new speed-performance Pareto-frontier areas across continuous and combinatorial inputs, with strong performance at several-orders-of-magnitude higher speed.

    Source: §6 · p. 8

  • Takeaways & Limitations

    The methods make BO applicable to black-box evaluations as cheap as 0.1 seconds while still outperforming faster optimizers such as CMA-ES.

    Source: §6 · p. 8

    Experiments omit very low-dimensional spaces (D < 10), mixed spaces, and batch acquisitions; for expensive evaluations, slower state-of-the-art BO may have slightly more consistent performance.

    Source: §6 · p. 8

Abstract

from arXiv · show

Bayesian optimization (BO) is typically used only for problems where the underlying function is deemed "expensive" (e.g. in time or money), with the speed of the BO algorithm being of little importance. In the real world, however, problems span a continuous range of values, going from cheap to expensive. In this paper, we present BO algorithms through the lens of a speed-performance Pareto frontier: we compare BO against faster algorithms like CMA-ES, and highlight how certain regions of the Pareto frontier are currently empty. As a solution, we propose a new set of fast BO methods that exploit the linear structure in existing BO algorithms, for both continuous and combinatorial inputs (from ~10 to 6000+ dimensions). Our methods achieve performance similar to state-of-the-art BO, while being more than $10^2\times$ to $10^3\times$ faster, opening the field of BO to an entirely new class of problems.

1 INTRODUCTION

BO is sample-efficient but its computational overhead can dominate when black-box evaluations are cheap, pushing practitioners toward faster optimizers. This paper exploits linear structure to speed BO across continuous and combinatorial spaces while extending its speed-performance frontier.

1 INTRODUCTION

  • When function evaluations cost less than choosing the next acquisition, BO overhead becomes the main cost and practitioners may switch to faster, less sample-efficient methods such as CMA-ES.State-of-the-art BO acquisition selection can take multiple minutes.Source: §1 · p. 1
  • The methods exploit a spherical-linear model's structure to accelerate hyperparameter fitting and acquisition optimization, targeting speedups of several orders of magnitude with little to no performance loss.The cited linear-model approach already scales beyond 20,000 observations, but remains slow because of gradient-based fitting and acquisition optimization.Source: §1 · pp. 1–2
  • Fast BO methods occupy new speed-performance frontier regions, matching many established BO methods at a fraction of the cost.The summary plot also reports CMA-ES matching TuRBO on high-dimensional problems.Source: Figure 1 · p. 2
  • A standardized framework extends gradient-free fast BO to combinatorial and low-dimensional spaces, with the goal of making BO viable even when evaluations take only a second.The authors hope this broader availability will let practitioners choose BO over faster alternatives such as CMA-ES.Source: §1 · p. 2

2 BACKGROUND

The background frames BO as pointwise optimization of an unknown function, typically using a surrogate and an acquisition function. It introduces linear structure in BO models and locates the paper among related work on continuous, latent, and unbounded search spaces.

2.1 Bayesian Optimization

  • BO seeks the global optimum of an unknown function through pointwise evaluations, fitting a probabilistic surrogate and optimizing an acquisition function to select the next point.Gaussian processes are common surrogates; TS, UCB, and EI are among the most commonly used acquisition functions.Source: §2.1 · pp. 2–3

2.2 Linear Structure in BO Algorithms

  • Linear kernels yield Bayesian linear regression with a posterior mean linear in features and a convex-quadratic posterior variance, properties later exploited for fast acquisition optimization.The background also describes spherical-linear BO for high-dimensional problems and CoCaBO's categorical kernel as a combinatorial counterpart to the linear kernel.Source: §2.1 · p. 3, §2.2 · p. 3

2.3 Related Work

  • Related work studies faster acquisitions on the sphere and unbounded spaces, while this paper targets the hypercube and extends its method to combinatorial spaces.Fan et al. (2026) focus on latent spaces on the sphere; Whitehead (2026) shows that EI optimization on an unbounded domain reduces to one-dimensional search.Source: §2.3 · pp. 3–4

3 METHOD (CONTINUOUS)

For continuous inputs on a hypercube, the method reduces fitting overhead by simplifying the spherical-linear surrogate and accelerates acquisition optimization by exploiting its structure. Thompson sampling is solved exactly up to numerical tolerance, while UCB and EI use minorize–maximize updates.

3.1 Surrogate Model

  • Dropping ARD reduces the surrogate's hyperparameters from hundreds or thousands to four, and a mixed grid-search and inner-fit procedure reuses eigendecompositions to limit fitting overhead.The global lengthscale is grid-searched; the full grid search is run every 10 BO iterations, with only the inner fit between searches.Source: §3.1 · p. 4

3.2 Acquisition Functions

  • The surrogate's posterior mean is linear and variance convex quadratic in its standardized features, linking the three acquisition optimizations through repeated Thompson-sampling-based subproblems.UCB and EI differ by a parameter, with EI using a self-tuning exploration weight.Source: §3.1 · p. 4, §3.2 · p. 4, (a) TS · p. 6

(a) TS

  • Dinkelbach's algorithm solves the Thompson-sampling fractional program globally without gradients, line searches, or restarts; its iterations converge superlinearly and cost O(D) each.The resulting TS maximum over the hypercube is exact up to numerical tolerance.Source: §3.2 · p. 4, (a) TS · p. 5

3.2 Acquisition Functions

  • UCB and EI use tangent-based minorizers and the same Dinkelbach solver, yielding nondecreasing acquisition values and stationary limit points, but not a guarantee of a global maximum.The method uses multiple random starts to seek better solutions.Source: (a) TS · pp. 5–6

4 METHOD (COMBINATORIAL)

For combinatorial inputs, the method represents categorical variables through one-hot features and exploits the resulting linear-regression structure. Acquisition optimization uses separable, per-variable discrete maximization rather than the continuous setting's spherical-projection solver.

4.1 Surrogate Model

  • The combinatorial surrogate has a posterior mean linear and variance convex quadratic in its features, but it needs no spherical projection because acquisition optimization occurs over a discrete set.The model's structure supports fast acquisition-function optimization.Source: §4.1 · p. 6
  • Rewriting kCoCaBO as an inner product reveals a Bayesian linear regression model whose posterior can be computed in O(NM^2 + M^3) time when N > M.The paper identifies this weight-space connection for kCoCaBO as a first.Source: §4.1 · p. 6

4.2 Acquisition Functions

  • For TS, UCB, and EI, the combinatorial optimizations reduce to per-variable argmax subproblems; UCB and EI use minorize–maximize updates and differ only in λ.Unlike continuous inputs, these subproblems do not require Dinkelbach's algorithm.Source: §4.2 · pp. 6–7

5 EXPERIMENTS

The experiments compare fast BO with state-of-the-art BO and other black-box optimizers on continuous and combinatorial problems, including tasks with evaluations typically under a second. Fast BO retains strong performance while reducing algorithm time across these settings.

5 EXPERIMENTS

  • The evaluation covers six high-dimensional benchmarks (60D–6392D), four low-dimensional benchmarks (12D–33D), and five combinatorial benchmarks (25–125 variables), with separate evaluation budgets.Each problem typically takes less than a second to evaluate, though some benchmarks are proxies for slower real-world processes.Source: §5 · p. 7

5.1 Continuous Problems

  • On high-dimensional inputs, fast UCB and EI match Vanilla BO's performance while running about 700× faster on average.The paper attributes EI's performance in part to its similarity to Linear BO, previously reported to match Vanilla BO.Source: §5.1 · p. 7
  • In low/mid dimensions, the TS variant is on par with Vanilla BO and Bounce, with only TuRBO slightly better; it is about 10× faster than TuRBO and 100× faster than Vanilla BO.The method fits only the last D observations and adopts TuRBO's trust region; Linear BO is fit every 50 iterations to supply its lengthscales.Source: §5.1 · p. 7
  • CMA-ES matches TuRBO's average sample efficiency, but at 0.1-second evaluations its faster execution yields similar total time and worse final values.The 0.1-second evaluation assumption and the time-versus-best-value comparison are shown in Figure 2.Source: §5.1 · p. 7, Figure 2 · p. 8
  • With the trust-region adaptation, TS outperforms EI and UCB in low dimensions; the authors hypothesize that the trust region may favor more exploratory behavior.Inside a small trust region, the linear model acts as a local-linear approximation, suggesting links to local BO and model-based trust-region methods.Source: §5.1 · pp. 7–8

5.2 Combinatorial Problems

  • On combinatorial problems, UCB and EI approach One-hot BO performance while running one to two orders of magnitude faster, and outperform the original CoCaBO method.Using CoCaBO's bandit for acquisition optimization instead reduces performance to CoCaBO's level.Source: §5.2 · p. 8

6 CONCLUSION

The paper exploits linear structure in BO to reduce computational overhead across continuous and combinatorial inputs. Its fast methods cover new parts of the speed-performance frontier, including settings with evaluations as cheap as 0.1 seconds.

6 CONCLUSION

  • The framework speeds both model fitting and acquisition-function optimization, yielding strong performance across high- and low-dimensional continuous and combinatorial problems at several orders of magnitude less algorithm time.The paper reports that these methods make BO applicable to 0.1-second evaluations while still outperforming faster black-box optimizers such as CMA-ES.Source: §6 · p. 8
  • Exact Thompson-sampling maximization and the EI–UCB connection open theoretical avenues, while exact solvers provide a reference for studying inexact acquisition optimization.The paper also links its trust-region variant to local BO and model-based trust-region methods.Source: §6 · p. 8
  • The experiments omit very low-dimensional spaces (D < 10), mixed spaces, and batch acquisitions; for expensive evaluations, slower state-of-the-art BO may offer slightly more consistent performance.Extending the methods to these settings and to other acquisition functions is left for future work.Source: §6 · p. 8

A DERIVATIONS

The derivations make surrogate fitting and acquisition optimization more efficient by exploiting the linear model’s structure. They give exact or monotonicity-based optimization procedures for continuous and combinatorial inputs, with distinct convergence guarantees.

A.1 Surrogate Fits

  • A shared global lengthscale and cached eigendecompositions reduce continuous-input NLL evaluations to O(min(N, D)); combinatorial fits reuse one eigendecomposition for O(M) updates.For continuous inputs, the fit also uses grid search and Nelder–Mead; for combinatorial inputs, it uses MacKay fixed-point updates.Source: §A.1 · pp. 12–13

A.2 Thompson Sampling

  • For continuous Thompson sampling, Dinkelbach’s algorithm solves separable subproblems exactly in O(D), yielding a global maximizer; combinatorial sampling optimizes variables independently or changes the largest-gain variables within a Hamming trust region.For the constrained combinatorial case, selecting up to r variables takes O(M + D log D).Source: §A.2 · p. 15

A.3 Upper Confidence Bound

  • For UCB, the minorizer is a global lower bound that is tight at the current point; convexity in feature space, not input space, suffices.The resulting acquisition values are nondecreasing and converge on the compact box.Source: §A.3 · pp. 15–16
  • UCB minorization yields nondecreasing acquisition values and stationary limit points, but only a local guarantee, so the method uses multiple random starts.Each MM step costs one Dinkelbach solve plus O(ND) to compute Σu0.Source: §A.3 · p. 16

A.4 Expected Improvement

  • Expected Improvement is convex and increasing in its mean and standard deviation, enabling a tight linear minorizer whose convergence argument matches UCB’s.For combinatorial inputs, maximizing this minorizer is equivalent to Thompson sampling and reduces to a per-variable argmax.Source: §A.4 · pp. 16–17

B.1 Benchmarks

The benchmark suite covers high- and low-dimensional continuous problems and combinatorial tasks, with baselines selected for each input type. The appendix also records evaluation-setting differences that constrain some comparisons.

B.1 Benchmarks

  • Rover, Robot Pushing, and MuJoCo evaluations are stochastic, while Lunar Lander uses fixed shared seeds and is repeatable at the same point.MuJoCo evaluations average 10 rollouts and Lunar Lander averages 50, following settings in the cited original papers.Source: §B.1 · p. 17

B.2 Baselines

  • Continuous comparisons include BO and derivative-free methods, while combinatorial comparisons include One-hot BO, CoCaBO, random search, and MCBO optimizers.The combinatorial One-hot BO baseline uses EI with MCBO’s genetic algorithm; CoCaBO uses its default overlap-kernel and multi-armed-bandit settings.Source: §B.2 · p. 18
  • Py-BOBYQA’s initial quadratic design exceeds the evaluation budget on Ant and Humanoid, so those runs never optimize and their low algorithm time is not an optimization-time comparison.The design interpolates a quadratic through 2D+1 points.Source: §B.2 · p. 18
  • A faster batched PyTorch implementation is used for MCBO timing comparisons and gives exactly the same results as the original pandas implementation.One-hot BO timings are also reported with the original framework code.Source: §B.2 · p. 18

B.3 Implementation

Implementation settings are held consistent across benchmark suites, with separate procedures for continuous, low-dimensional, and combinatorial inputs. Acquisition optimization also includes safeguards against returning previously observed points in finite spaces.

Continuous fit

  • Settings chosen in preliminary runs are used unchanged across benchmarks within each suite, and all three acquisition functions share the same fit with double-precision model and acquisition computations.Continuous fits search a 10-value lengthscale grid every 10 fits and use Nelder–Mead for the inner fit; intervening fits hold the lengthscale fixed.Source: §B.3 · p. 18

Continuous acquisition optimization

  • Continuous Thompson sampling uses one exact solve per sample, while UCB and EI use 10 random starts and at most 10 MM iterations.Dinkelbach’s algorithm stops when the ratio changes by less than 10^-6 or after 100 iterations; UCB and EI return the highest-scoring unobserved point when available.Source: §B.3 · pp. 18–19

Combinatorial acquisition optimization

  • Combinatorial acquisition searches within MCBO’s Hamming trust region; UCB and EI use 10 starts and up to 10 MM iterations, while Thompson sampling uses one exact solve.When selected points have already been observed, the procedure searches nearby unobserved points inside the trust region.Source: §B.3 · p. 19

Low-dimensional variant

  • The low-dimensional variant uses TuRBO trust regions, restarts from a new 30-point Sobol design when the region collapses, and fits on only the latest D observations.Its projection is centered at the trust-region midpoint, and ARD lengthscales are refit every 50 fits and after each restart.Source: §B.3 · p. 19

B.4 Hardware, Timing, and Seeds

The appendix specifies the timing measure, hardware, seeds, and statistics used to compare methods. Pareto plots report mean final best value against mean algorithm time across seeds.

B.4 Hardware, Timing, and Seeds

  • Algorithm time sums wall-clock model fitting and acquisition-function optimization, excluding objective evaluations and the initial fit on continuous benchmarks.This measure is used for the Pareto plots’ x-axis and Table 2.Source: §B.4 · p. 19
  • Continuous CPU runs used four pinned threads on AMD EPYC 7513 CPUs, while combinatorial runs used one core of the same CPU type.GPU runs used NVIDIA A100 PCIe GPUs with 40 GB of memory.Source: §B.4 · p. 19
  • The study uses 10 seeds for high-dimensional, 40 for low-dimensional, and 20 for combinatorial benchmarks; SAASBO* has 10 low-dimensional seeds.For each seed, continuous methods except Bounce share the same initial design.Source: §B.4 · p. 19
  • Pareto-plot points show mean final best value and mean algorithm time over seeds, with the frontier marking the best mean value reachable within each time budget.Figure 1 error bars are 95% bootstrap intervals; other figures generally use ±1 standard error.Source: §B.4 · pp. 19–20
  • On each high-dimensional benchmark, the acquisition functions are one to nearly four orders of magnitude faster than every model-based baseline and lie on the Pareto frontier.The slow part of the time axis is shaded and uses a different scale.Source: Figure 3 · p. 20

C.1 Per-Benchmark Pareto Plots

Across high-dimensional, low-dimensional, and combinatorial benchmarks, the per-benchmark Pareto plots compare final values with algorithm time. The companion plots track best value found over optimization evaluations.

C.1 Per-Benchmark Pareto Plots

  • On high-dimensional problems, EI and UCB consistently lie on the Pareto frontier; they match or trail state of the art when N > D and outperform other methods when N ≈ D or N < D.The proposed explanation for the latter cases is that data may not determine a linear model, reducing the benefit of a more flexible GP.Source: §C.1 · p. 20
  • On three low-dimensional problems, TS matches or outperforms Vanilla BO at more than 100× less algorithm time; CMA-ES outperforms it on Lunar Lander.TS lies on the Pareto frontier for three of four problems.Source: §C.1 · p. 20, Figure 4 · p. 21
  • On four of five combinatorial problems, all three acquisition functions lie on the Pareto frontier; on LABS, TS performs similarly to random search.The methods are 20–100× faster than One-hot BO using the shared PyTorch framework, and 100–500× faster than the original MCBO code.Source: §C.1 · p. 20
  • Table 2 reports per-run algorithm time and speedup over Vanilla BO for high-dimensional benchmarks, sorted by dimensions from 60 to 6392.Times exclude black-box evaluations; Fast BO runs on CPU, while TuRBO and Linear BO use a GPU on Humanoid.Source: Table 2 · p. 21

C.2 Best Value Found per Iteration

  • Figures 6–8 plot best value found against evaluation count for the high-dimensional, low-dimensional, and combinatorial benchmarks, respectively.They include methods from the corresponding Pareto plots, with proposed methods as solid lines and baselines as dashed lines.Source: §C.2 · p. 21

C.3 Algorithm Time

Fast BO reduces algorithm time substantially on high-dimensional benchmarks, while timing breakdowns show that model fitting and acquisition optimization can each dominate depending on the method and setting.

C.3 Algorithm Time

  • Fast BO runs in seconds to minutes on high-dimensional benchmarks, while Vanilla BO takes hours or more than a day; speedups are largest on Rover and Lasso-DNA at over 10^3×.Speedups are smallest on SVM and Humanoid, at a few hundred; Linear BO is slower than Vanilla BO on MOPTA08, SVM, and Humanoid.Source: §C.3 · p. 21
  • With N = 1000, baseline fitting dominates when N > D, both steps take similar shares when N ≈ D, and acquisition optimization takes over 90% of baseline time when N < D.Fast BO TS spends about 90–99% of its time fitting, whereas UCB and EI spend roughly 20–65% optimizing the acquisition function.Source: §C.3 · p. 21
  • Baseline methods take seconds to minutes per step and slow as N grows, while proposed methods take tens of milliseconds on Rover to a few seconds on Humanoid.At these budgets, baseline per-step cost grows roughly linearly to quadratically in N; computing the kernel and gradients dominates Cholesky decomposition.Source: §C.3 · p. 22

C.4 Ablations

Ablations identify acquisition optimization and model fitting as sources of Fast BO’s speed, and show distinct performance effects for combinatorial and low-dimensional variants.

C.4 Ablations

  • Replacing Fast BO’s MM optimizer with LogEI makes high-dimensional runs approximately 20–40× slower; fitting the full lengthscale grid every fit makes them 2–6× slower.Gradient-based MAP fitting is about 10–20× slower and worsens final value on MOPTA08, Lasso-DNA, and Ant, but improves it on Rover.Source: §C.4 · p. 22, Figure 11 · p. 25
  • In combinatorial problems, a genetic algorithm reaches the same final values as the MM optimizer but is approximately 10–20× slower.Using the multi-armed bandit drops performance to CoCaBO’s level; the MM optimizer contributes most to Fast BO’s speed among the ablated ingredients.Source: §C.4 · p. 22, Figure 12 · p. 25, Figure 11 · p. 25
  • In low-dimensional problems, the trust region accounts for most improvement; the window alone often degrades performance but usually helps when combined with the trust region.The isotropic trust region plus window is faster than the proposed method but performs slightly worse; the ablation uses 10 of 40 seeds.Source: §C.4 · p. 22, Figure 13 · p. 26
Loading 2610.29580v1…