Acquisition for Spherical-Linear Bayesian Optimization on the Cube

Nathan Wycoff

stat.MLOct 23, 2026

Acquisition for Spherical-Linear Bayesian Optimization on the Cube

Authors: Nathan Wycoff

Organizations: Department of Mathematics and Statistics, University of Massachusetts Amherst

Abstract

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 $[-\ell,\ell]^{2}$ , with coloration shared across panels. Remaining Panels: The image of $[-\ell,\ell]^{2}$ under $P$ for various settings of $\ell$ , showing the shape of the feasible region. As $\ell$ 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 $[-\ell,\ell]^{D}$ under the inverse stereographic transformation, shaded in green, is given by the intersection of the polyhedral cone $\mathcal{H}$ originating at the north pole (orange) and the sphere $S_{D}$ (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 $\nu$ , 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

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

See all 240 papers

Bayesian Optimization in Linear Time
Apr 30, 2026Jesse Schneider, William J. WelchBayesian Optimization Black-Box Optimization
Department of Statistics, University of British Columbia, Vancouver, BC V6T 1Z4, Canada
Amortized Acquisition Optimization for Bayesian Optimization with Variational Mutual Information
Jan 13, 2026Farhad MirkarimiBayesian Optimization Black-Box Optimization
Fast Bayesian Optimization Through Linear Models
Oct 21, 2026Colin Doumont, Henry Moss, Philipp HennigBayesian Optimization Surrogate Modeling
University of Tübingen, Tübingen AI Center · Lancaster University

Apr 30, 2026J/K move · Enter open · S save

Bayesian Optimization in Linear Time

Jesse Schneider, William J. Welch

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

Bayesian Optimization Black-Box Optimization

Open paper AskPDF arXiv

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

124

, and show that our method achieves superior optimization performance in all tests. In addition our method has linear computational complexity.

Abstract

Bayesian Optimization

Explore similar work

Bayesian Optimization in Linear Time

Amortized Acquisition Optimization for Bayesian Optimization with Variational Mutual Information

Fast Bayesian Optimization Through Linear Models