An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions

Wei-Ting Tang; Akshay Kudva; Calvin Tsay; Joel A. Paulson

math.OCApr 21, 2026

An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions

Authors: Wei-Ting Tang, Akshay Kudva, Calvin Tsay, Joel A. Paulson

Abstract

We study the deterministic global optimization of trained Gaussian process posterior mean functions over hyperrectangular domains. Although the posterior mean function has a compact closed-form representation, its global optimization is challenging because it remains nonlinear and nonconvex. Existing exact deterministic approaches become increasingly difficult to scale as the number of training data points grows, leading to approximation-based methods that improve tractability by optimizing a modified (inexact) objective. In this work, we propose PALM-Mean, a piecewise-analytic lower-bounding framework embedded in reduced-space spatial branch-and-bound. At each node, kernel terms that are locally important are replaced by a sign-aware piecewise-linear relaxation in an appropriate scalar distance variable, while the remaining terms are bounded analytically in closed form. We show this hybrid approach yields a valid lower bound for the posterior mean, while limiting the size of the branch-and-bound subproblems. We establish validity of the node lower bounds and $\varepsilon$ -global convergence of the resulting algorithm. Computational results on synthetic benchmarks and real-world application problems show that PALM-Mean improves scalability relative to representative general-purpose deterministic global solvers, particularly as the number of training data points increases.

Explore similar work

May 19, 2026stat.ML

Goal-Oriented Lower-Tail Calibration of Gaussian Processes for Bayesian Optimization

Gaussian process (GP) predictive distributions are commonly used in Bayesian optimization (BO) to guide the selection of evaluation points for expensive objective functions. The choice of kernel and hyperparameters has a strong influence on the exploration--exploitation trade-off. For minimization, sampling criteria such as expected improvement (EI) depend on both the probability mass below the current best value and the shape of the predictive distribution in this region. This article studies goal-oriented calibration of GP predictive distributions below a low threshold

t

in the noiseless setting, for standard GP models with hyperparameters selected by maximum likelihood. We consider two complementary forms of calibration below

t

for inputs distributed according to a reference measure

μ

: occurrence calibration over the design space and thresholded

μ

-calibration on sublevel sets of the form

\{x\in\mathbb{X}, f(x)\le t\}

. We propose tcGP, a post-hoc method that combines these two forms of calibration for GP predictive distributions below

t

. With fixed GP hyperparameters, the exact EI sampling criterion based on tcGP generates a sequence of evaluation points that is dense in the design space. Experiments on standard benchmarks show improved lower-tail calibration and BO performance relative to standard GP models and globally calibrated GP models.

Aurélien Pion, Emmanuel Vazquez

Bayesian Optimization Gaussian Process Posterior Multicalibration and Calibration Hyperparameter Optimization

Ask PDF

May 13, 2026math.OC

Stochastic global optimization of continuous functions via random walks on Grassmannians

We introduce a stochastic global optimization method based on random walks on Grassmannian manifolds. To minimize a continuous objective

\ell:\mathbb{R}^d\rightarrow\mathbb{R}

, the method repeatedly samples random

k

-dimensional linear subspaces (with

k\ll d

), solves the resulting low-dimensional restrictions of these problems to these subspaces using an arbitrary black-box optimizer, and updates the iterate (which monotonically improves upon the previous iterate). Unlike classical optimization analyses that rely on convexity, smoothness, Lipschitz bounds, or Polyak-Lojasiewicz-type conditions, our convergence guarantees depend only on the geometric distribution of restricted minima across the

k

-dimensional subspaces passing through a given point in

\mathbb{R}^d

. We identify a gap parameter -- an analogue of a spectral gap for random walks -- that controls the rate at which the iterates approach the global minimum value. Finally, we argue that the same analysis yields a blind-spot robustness property: sufficiently narrow, deep dips of the loss function (small-measure regions where

\ell

spikes downward) have limited influence on the algorithm's trajectory, since they are unlikely to be encountered by random subspace sampling.

Kartik Gupta, Stephen D. Miller, Pradeep Ravikumar +1

Stochastic Optimization Low-Dimensional Structure Llm-Based Optimization Modeling Subsampling

Ask PDF

Jun 1, 2026cs.LG

Local Preferential Bayesian Optimization

Bayesian optimization (BO) is a popular and effective approach for tuning expensive, noisy experiments, but requires the formulation of an explicit objective function. Preferential BO (PBO) removes this requirement by learning from pairwise human feedback, yet existing methods struggle to efficiently optimize beyond low- and medium-dimensional problems due to their global search approaches. We address this limitation by developing a family of local PBO methods that transfer key ideas from high-dimensional BO to the preferential setting. In particular, we introduce local PBO methods which adapt trust-region and derivative-informed local search to pairwise preference feedback, where the latter exploits first- and second-order derivatives of the Laplace-approximated GP posterior. Our benchmark on GP sample paths, standard optimization benchmark functions, and policy-search tasks shows that local PBO methods are especially effective in high-dimensional and complex landscapes with steep optima. Compared with global preference-based baselines, they can substantially reduce cumulative regret, making them particularly useful for real-world preference-based optimization tasks such as policy search.

Johanna Menn, Miriam Kober, Paul Brunzema +2

Bayesian Optimization Parallel Continuous Local Search Robust Preference Optimization Bayesian

Ask PDF