mlsanityData to 7 Oct 2026

Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation

arXiv 2410.16893 ↗First posted 22 Oct 2024math.OC cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

Bayesian optimization relies on iteratively constructing and optimizing an acquisition function. The latter turns out to be a challenging, non-convex optimization problem itself. Despite the relative importance of this step, most algorithms employ sampling- or gradient-based methods, which do not provably converge to global optima. This work investigates mixed-integer programming (MIP) as a paradigm for global acquisition function optimization. Specifically, our Piecewise-linear Kernel Mixed Integer Quadratic Programming (PK-MIQP) formulation introduces a piecewise-linear approximation for Gaussian process kernels and admits a corresponding MIQP representation for acquisition functions. The proposed method is applicable to uncertainty-based acquisition functions for any stationary or dot-product kernel. We analyze the theoretical regret bounds of the proposed approximation, and empirically demonstrate the framework on synthetic functions, constrained benchmarks, and a hyperparameter tuning task.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 22 of its 63 references that are in the map. First posted on arXiv 22 Oct 2024.

Builds on

22 of 63 references.

References · 22

  1. 2018A Tutorial on Bayesian Optimizationcited by 734
  2. 2019Scalable Global Optimization via Local Bayesian Optimizationcited by 359
  3. 2023Unexpected Improvements to Expected Improvement for Bayesian Optimizationcited by 144
  4. 2016GPflow: A Gaussian process library using TensorFlowcited by 139
  5. 2021High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspacescited by 139
  6. 2015High Dimensional Bayesian Optimisation and Bandits via Additive Modelscited by 137
  7. 2018Maximizing acquisition functions for Bayesian optimizationcited by 113
  8. 2018Bayesian Optimization of Combinatorial Structurescited by 64
  9. 2018BOCK : Bayesian Optimization with Cylindrical Kernelscited by 62
  10. 2019Greed is Good: Exploration and Exploitation Trade-offs in Bayesian Optimisationcited by 47
  11. 2022Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterizationcited by 35
  12. 2019Mixed-Variable Bayesian Optimizationcited by 29
10 more
  1. 2020Mercer Features for Efficient Combinatorial Bayesian Optimizationcited by 27
  2. 2021Constrained Discrete Black-Box Optimization using Mixed-Integer Programmingcited by 16
  3. 2024Bayesian optimization as a flexible and efficient design framework for sustainable process systemscited by 15
  4. 2020Global Optimization of Gaussian processescited by 14
  5. 2022Tree ensemble kernels for Bayesian optimization with known constraints over mixed-feature spacescited by 14
  6. 2024The Vizier Gaussian Process Bandit Algorithmcited by 14
  7. 2021Multi-Objective Constrained Optimization for Energy Applications via Tree Ensemblescited by 12
  8. 2018Global sensitivity analysis for optimization with variable selectioncited by 9
  9. 2019On Local Optimizers of Acquisition Functions in Bayesian Optimizationcited by 7
  10. 2021Global optimization using random embeddingscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 3; 2026: 4.

8 papers.

  1. 2024EARL-BO: Reinforcement Learning for Multi-Step Lookahead, High-Dimensional Bayesian Optimizationcited by 6
  2. 2025Deterministic Global Optimization of the Acquisition Function in Bayesian Optimization: To Do or Not To Do?cited by 3
  3. 2025BARK: A Fully Bayesian Tree Kernel for Black-box Optimizationcited by 2
  4. 2025Global optimization of graph acquisition functions for neural architecture searchcited by 2
  5. 2026An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functionscited by 0
  6. 2026Meta-learning for sample-efficient Bayesian optimisation of fed-batch processescited by 0
  7. 2026Transferring Information Across Interventions in Causal Bayesian Optimizationcited by 0
  8. 2026ILP-BO: Integer Linear Programming-Based Black-Box Optimizationcited by 0