Recent work demonstrated that executing Bayesian Optimization (BO) using simply a linear surrogate with a clever transformation is enough to approximate the performance of the standard Gaussian-Process (GP) based version on high-dimensional test functions. When the decision region is a sphere, this strategy admits rapid exact acquisition. However, it is the unit cube we encounter most often in the BO literature, and in this setting a standard approach, namely a multi-start quasi-Newton method, is employed for solving the acquisition subproblem. In this article, we will discuss a series of results, both positive and negative, regarding the complexity of global resolution of various acquisition subproblems over the unit cube. On the basis of this discussion, we will propose a new acquisition function which is globally optimizable using significantly less execution time than the incumbent approach while maintaining or improving performance. The resulting method is competitive with GP-based BO in terms of accuracy per evaluation, and is superior in terms of accuracy per walltime on black-boxes of low to moderate computational intensity.
Figures & tables
Figure 1: Search Region for BO in Spherical Coordinates. Left Panel: Random points in the unit cube [−ℓ,ℓ]2 , with coloration shared across panels. Remaining Panels: The image of [−ℓ,ℓ]2 under P for various settings of ℓ , showing the shape of the feasible region. As ℓ grows, the preimage grows, the space around the origin is stretched, and the corners of the unit cube are compressed to the north pole.
Figure 2: Illustration of Corollary 1 . The image of the constraint set [−ℓ,ℓ]D under the inverse stereographic transformation, shaded in green, is given by the intersection of the polyhedral cone H originating at the north pole (orange) and the sphere SD (gray), minus the point at the north pole.
Figure 3: Probability a Uniform Point on Sphere is Box-Feasible . The solid blue line gives a numerical estimate of the true relationship derived via Gaussian quadrature, while the dotted red line gives an estimate obtained from a thin shell approximation. We see that the relationship is not monotonic in D .
Figure 4: Necessity of Dinkelbach Iteration. These panels show three random spherical-linear functions on [−1,1]2 , as well as the performance of 25 L-BFGS-B runs (initializations in white linked to solutions in open red circles) and our proposed Dinkelbach iteration (path in pink and solution in closed orange circle). Panel (a) shows a function which is concave within the unit cube and which is amenable to a standard quasi-Newton search. In Panel (b), the desired maximum is almost in the box, but the minimum is too, and points on the other side cannot cross it. Panel (c) shows the local search methods failing to maximize a convex function unless they are propitiously initialized. In all cases, the Dinkelbach iteration is successful, as anticipated by its global convergence properties.
Problem
Rover
MOPTA08
Lasso-DNA
SVM
Ant
Dimension
60
124
180
388
888
Linear (MAP) + LogEI
-1.76
237
0.289
0.079
188
Linear (MAP) + surface TS
-3.28
238
0.289
0.083
222
Linear (Fixed) + LogEI
-2.68
236
0.294
0.061
846
Linear (Fixed) + surface TS
-2.85
242
0.296
0.061
913
Vanilla BO
-2.86
215
0.285
0.050
348
Table 1: Median BoV at 1,000 evaluations, lower is better. Best method in bold, second-best underlined. First four methods are Spherical-Linear models, next three are GP baselines.
Figure 5: Average model performance across all problems with budget given by walltime; lower is better.
Figure 6: Average model performance across all problems with batch size of 50; lower is better.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 7: Full results with budget given by evaluations. Shaded regions are interquartile range.
Figure 8: Full results of empirically observed walltime versus BoV.
Figure 9: Full results showing the best performing method as a function of ν , the time it takes a single black-box call to resolve, and the total walltime budget. The shaded color indicates the method of choice for a given combination.
Bayesian optimization is a sequential method for minimizing objective functions that are expensive to evaluate and about which few assumptions can be made. By using all gathered data to train a Gaussian process model for the function and adaptively employing a mixture of global exploration and local exploitation, this method has been used for optimization in many fields including machine learning, automotive engineering and reinforcement learning. However, the standard method suffers from two problems: 1) with cubic computational complexity in the training-set size it eventually becomes computationally infeasible to train the model, and 2) globally modeling the objective function is not necessarily optimal given the local nature of minimization. Using flexible and recursive binary partitioning of the search space, we adapt both the modeling and acquisitive aspects of standard Bayesian optimization to work harmoniously with the partitioning scheme, thereby ameliorating both standard shortcomings. We compare our method against a commonly used Bayesian optimization library on seven challenging test functions, ranging in dimensionality from 6 to 124, and show that our method achieves superior optimization performance in all tests. In addition our method has linear computational complexity.
Jesse Schneider, William J. Welch
Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
Bayesian optimization (BO) of expensive black-box functions is traditionally addressed with Gaussian processes (GPs), which scale cubically with observations, or Bayesian neural networks (BNNs), which incur costly posterior sampling and inner-loop acquisition optimization. We propose VBO-MI (Variational Bayesian Optimization with Mutual Information), a fully gradient-based BO framework that requires no explicit GP prior or fixed parametric posterior family over objective function and treats it as a strict black box. An actor-critic architecture pairs an action-net with a variational critic that estimates information gain, eliminating the acquisition optimization bottleneck and achieving up to 102× fewer FLOPs than BNN-BO baselines. A lightweight surrogate network further reduces real function queries to one batch per iteration. We establish consistency guarantees and evaluate VBO-MI on synthetic benchmarks (Ackley, Levy, Griewank) and real-world tasks (Rover Trajectory, Lunar Lander, Pest Control), demonstrating competitive or superior performance over the baselines.
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× to 103× faster, opening the field of BO to an entirely new class of problems.
Colin Doumont, Henry Moss, Philipp Hennig
University of Tübingen, Tübingen AI Center · Lancaster University