Linear Models Accelerate Bayesian Optimization by 1000x

Bayesian optimization (BO) is often seen as a powerful tool for handling expensive black-box functions (such as experiments that take days), but its own runtime speed has received little attention. In reality, problems vary in cost—some are cheap, some are expensive. A new paper proposes restructuring BO through linear structure, making it up to three orders of magnitude faster while maintaining optimization performance comparable to state-of-the-art methods. This opens up entirely new application domains for BO.

The Gap in the Speed-Performance Pareto Frontier

Conventional wisdom holds that BO is only suitable for expensive functions, and algorithm speed doesn't matter. But the paper points out that problem cost is a continuous spectrum, from cheap to expensive. The authors compare BO with faster evolutionary strategies (such as CMA-ES) on the speed-performance Pareto frontier and find a clear gap in the frontier: there is neither a BO method that achieves both high speed and high performance, nor a fast algorithm that can handle complex problems.

This gap means that many medium-cost problems with speed requirements (such as hyperparameter tuning, real-time decision-making) cannot benefit from BO's high sample efficiency. The authors' fast BO method is designed to fill these gaps.

The speed-performance Pareto frontier is a common visualization tool for measuring trade-offs in optimization algorithms: the horizontal axis is typically per-iteration or total runtime, and the vertical axis is the number of evaluations needed to reach a certain performance level or the final objective value. Algorithms on the frontier are optimal in performance for a given speed, or fastest for a given performance. The article notes that existing Bayesian optimization methods are far from the high-speed end due to high computational overhead, while evolutionary strategies like CMA-ES are fast but have lower sample efficiency, leaving a gap in the middle of the frontier. Filling this gap means algorithms can achieve high sample efficiency within acceptable time, making them suitable for medium-cost scenarios such as hyperparameter tuning.

Linear Structure: The Key to Acceleration

The core of the new method lies in exploiting linear structure in existing BO algorithms. Specifically, the authors find that Gaussian process (GP) surrogate models can be transformed into linear models under certain conditions, reducing computational complexity from cubic to linear or quadratic. The method applies to both continuous and combinatorial inputs (dimensions ranging from ~10 to 6000+).

Through linearization, BO's per-iteration time is greatly reduced without sacrificing sample efficiency. Experiments show that under the same evaluation budget, the new method achieves performance comparable to state-of-the-art BO but is 100 to 1000 times faster. This acceleration enables BO to handle large-scale problems that were previously out of reach due to prohibitive computational costs.

The Gaussian process (GP) surrogate model is a core component of Bayesian optimization. It defines the covariance between data points through a kernel function, thereby performing nonparametric Bayesian modeling of the objective function. Standard GP inference requires computing the inverse of the kernel matrix or solving a linear system, with time complexity O(n^3), where n is the number of observation points. As the evaluation budget grows or problem dimensionality increases, this cubic complexity becomes the main computational bottleneck. Linear structure refers to the fact that under certain conditions (such as using specific kernel functions or inputs lying in a linear subspace), the GP posterior mean and variance can be expressed in the form of a linear model, thereby avoiding matrix inversion and reducing complexity to O(n) or O(n^2). This exact linearization introduces no approximation error and is the theoretical basis for the method's hundredfold acceleration.

Performance Validation: From Low to High Dimensions

The authors validate the method's effectiveness on multiple benchmark problems, including continuous optimization and combinatorial optimization (such as hyperparameter tuning, protein sequence design). In combinatorial spaces with dimensions up to 6000+, traditional BO cannot run due to computational bottlenecks, while the new method can search efficiently.

Compared with fast evolutionary strategies like CMA-ES, the new method maintains an advantage in sample efficiency while approaching their speed. This means users no longer need to compromise between speed and performance. The paper emphasizes that this acceleration is not achieved through approximation or simplification, but through exact exploitation of linear algebraic structure, ensuring theoretical rigor.

Combinatorial optimization problems (such as protein sequence design) have discrete, high-dimensional search spaces. Traditionally, Bayesian optimization handles them by encoding discrete variables as continuous vectors or using specialized kernel functions, but computational complexity rises sharply with dimensionality. A combinatorial space with dimensions up to 6000+ means the number of candidate solutions grows exponentially, and standard GP inference cannot complete in reasonable time due to O(n^3) complexity. The fast BO method exploits linear structure to make exact Bayesian inference feasible in high-dimensional combinatorial spaces, thereby extending BO's application range from low-dimensional continuous problems to large-scale discrete design problems.

Impact and Outlook

The significance of this work lies in redefining the applicability boundaries of Bayesian optimization. In the past, BO was confined to expensive functions; now, fast BO allows medium-cost problems (such as automated machine learning, rapid screening in materials discovery) to benefit from BO's sample efficiency. Meanwhile, the method is open-sourced for community use and extension.

In the future, the authors plan to further explore acceleration possibilities under nonlinear structures and extend the method to more problem types. For practitioners, when facing problems with moderate evaluation costs but high dimensionality, it may be worth considering this fast BO method—it could bring unexpected efficiency gains.

One-line Summary

A new method restructures Bayesian optimization through linear structure, achieving 100x to 1000x speedup while maintaining performance.

Paragraph Summary

This article introduces research on accelerating Bayesian optimization (BO). Traditional BO focuses only on expensive black-box functions and ignores algorithm speed, but real-world problem costs are continuously distributed, leaving a gap in the speed-performance Pareto frontier. The authors find that the Gaussian process surrogate model in BO can be transformed into a linear model under certain conditions, reducing computational complexity from cubic to linear or quadratic, thereby achieving 100x to 1000x acceleration while maintaining sample efficiency. The method applies to both continuous and combinatorial inputs with dimensions from ~10 to 6000+, and performs comparably to state-of-the-art BO on multiple benchmarks. The acceleration enables BO to handle large-scale problems previously out of reach, redefines BO's applicability boundaries, and has been open-sourced.