cs.LGOct 21, 2026

Fast Bayesian Optimization Through Linear Models

Authors: Colin Doumont, Henry Moss, Philipp Hennig

Organizations: University of Tübingen, Tübingen AI Center · Lancaster University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 102×10^2\times to 103×10^3\times faster, opening the field of BO to an entirely new class of problems.

Figures & tables

Figure 1: Summary plot of the speed-performance Pareto frontiers in Figures 3 , 4 and 5 . Speed is measured relative to state-of-the-art BO (averaged using a geometric mean). For performance, we rescale the final best values of each benchmark such that random search scores 00 and the best method scores 11 (and then average these scores over all benchmarks). In all three settings, our fast BO methods cover new areas of the Pareto frontier , matching many well-known BO methods at a fraction of the cost. Moreover, CMA-ES performs surprisingly well — matching TuRBO on high-dimensional problems — highlighting the relevance of fast black-box optimizers.
Figure 2: Best value found against wall-clock time on the high-dimensional benchmarks, with each method run for 1000 evaluations (except SAASBO ∗ for 500). For this figure, evaluations are assumed to take only 0.10.1 seconds. Even in this fast regime, the speed advantage of CMA-ES does not lead to better results compared to our fast BO methods : its overall wall-clock time is similar to ours, while performing worse (on average).
Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

 BenchmarkDDEvaluationsRolloutsReference
High-dimensional continuousRover60601000100011Wang et al., (2018) ; Eriksson et al., (2019)
MOPTA0812412410001000–Eriksson and Jankowiak, (2021)
Lasso-DNA18018010001000–Šehić et al., (2022)
SVM38838810001000–Eriksson and Jankowiak, (2021)
Ant888888100010001010Wang et al., (2020)
Humanoid63926392100010001010Wang et al., (2020)
Appendix
Table 1: Benchmarks, with their dimension DD , their number of evaluations (including the initial design), and the number of rollouts averaged per evaluation (– for deterministic benchmarks).
Figure 3: Extension of Figure 1 for each high-dimensional benchmark. Our AFs are one to nearly four orders of magnitude faster than every model-based baseline, and always lie on the Pareto frontier. (The slow part of the time axis is shaded and uses a different scale.)
Figure 4: Extension of Figure 1 for each low-dimensional benchmark. Our TS method matches or outperforms Vanilla BO on three of the four problems, at more than 100×100\times less algorithm time. (The slow part of the time axis is shaded and uses a different scale.)
Figure 5: Extension of Figure 1 for each combinatorial benchmark. Our AFs lie on the Pareto frontier on all problems except LABS , and are 100100 – 500×500\times faster than One-hot BO with the original MCBO code (hollow circles). (The slow part of the time axis is shaded and uses a different scale, and the yy axis is inverted since the tasks are minimized.)
Figure 6: Extension of Figure 3 over the course of the optimization.
Figure 7: Extension of Figure 4 over the course of the optimization.
Figure 8: Extension of Figure 5 over the course of the optimization.
 Fast BOBaselines
BenchmarkTSUCBEITuRBOVanilla BOLinear BO
Rover3254×3254\times ( 6.06.0 s)1366×1366\times ( 1414 s)1251×1251\times ( 1616 s)3.2×3.2\times ( 1.71.7 h)– ( 5.45.4 h)7.3×7.3\times ( 4545 m)
MOPTA081747×1747\times ( 8.18.1 s)740×740\times ( 1919 s)690×690\times ( 2020 s)4.6×4.6\times ( 5151 m)– ( 3.93.9 h)0.51×0.51\times ( 7.77.7 h)
Lasso-DNA2036×2036\times ( 1515 s)1266×1266\times ( 2424 s)1175×1175\times ( 2626 s)11×11\times ( 4646 m)– ( 8.58.5 h)1.5×1.5\times ( 5.85.8 h)
SVM415×415\times ( 3939 s)330×330\times ( 4949 s)329×329\times ( 4949 s)4.3×4.3\times ( 1.11.1 h)– ( 4.54.5 h)0.14×0.14\times ( 3131 h)
Ant994×994\times ( 1.61.6 m)812×812\times ( 2.02.0 m)810×810\times ( 2.02.0 m)2.4×2.4\times ( 1111 h)– ( 2727 h)4.0×4.0\times ( 6.76.7 h)
Appendix
Table 2: Algorithm time per run on the high-dimensional benchmarks (model fitting and AF optimization, mean over 1010 seeds, excluding black-box evaluations). Each entry is the speedup over Vanilla BO (the dash), with the wall-clock time in gray parentheses. Benchmarks are sorted by dimension ( 6060 to 63926392 ). Fast BO runs on CPU throughout, whereas TuRBO and Linear BO use a GPU on Humanoid ( † ). These are the times plotted in Figure 3 .
Figure 9: Depending on the problem, either the fit or the AF optimization can dominate the algorithm time of most BO baselines. In contrast, our TS method spends almost all of its time in the fit ( † GPU).
Figure 10: Our AFs take at most 55 seconds per step, which is negligible compared to the BO baselines (median over seeds, smoothed with a 6464 -step rolling mean).
Figure 11: Each ingredient of Fast BO (EI) contributes to its speed, with our MM optimizer contributing most (about 2020 – 40×40\times ). Only the gradient-based fit lowers the final value on some benchmarks.
Figure 12: The genetic algorithm reaches the same values as our MM optimizer, but is about 1010 – 20×20\times slower. The multi-armed bandit drops to the level of CoCaBO . (The yy axis is inverted since the tasks are minimized.)
Figure 13: Most of the improvement of our low-dimensional variant is due to the ARD trust region, whereas the window mainly helps once combined with this trust region (mean over the first 1010 of the 4040 seeds).
More in this topic

Bayesian Optimization

Bayesian optimization uses probabilistic models and sequential experiments to find strong solutions when evaluating a black-box objective is costly.

See all 243 papers

Explore similar work

CardsList

  1. Bayesian Optimization in Linear Time

    Apr 30, 2026Jesse Schneider, William J. WelchBayesian OptimizationBlack-Box Optimization

    Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada

  2. BayMOTH: Bayesian optiMizatiOn with meTa-lookahead -- a simple approacH

    Apr 13, 2026Rahman Ejaz, Varchas Gopalaswamy, Ricardo Luna +5Bayesian OptimizationMulti-Task Optimization

    Laboratory for Laser Energetics, Rochester, NY, USA · Department of Mechanical Engineering, University of Rochester, Rochester, NY, USA · Hewlett Packard Labs, Santa Clara, CA, USA +2

  3. Local Preferential Bayesian Optimization

    Jun 1, 2026Johanna Menn, Miriam Kober, Paul Brunzema +2Pairwise Preference LearningPairwise Preference Evaluation

    Institute for Data Science in Mechanical Engineering, RWTH Aachen University, Aachen, Germany · Department of Clinical Research, University of Bern, Bern, Switzerland · Center for Reproducible Science and Research Synthesis, University of Zurich, Zurich, Switzerland +1