# Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization

arXiv: https://arxiv.org/abs/2405.15285 · HTML: https://mlsanity.com/paper/2405.15285/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 24 May 2024.

## Builds on (most cited first, 22 of 22)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Bayesian Optimization in a Billion Dimensions via Random Embeddings](https://mlsanity.com/paper/1301.1942/) (2013)
- [High-Dimensional Bayesian Optimization with Sparse Axis-Aligned Subspaces](https://mlsanity.com/paper/2103.00349/) (2021)
- [High Dimensional Bayesian Optimisation and Bandits via Additive Models](https://mlsanity.com/paper/1503.01673/) (2015)
- [Batched Large-scale Bayesian Optimization in High-dimensional Spaces](https://mlsanity.com/paper/1706.01445/) (2017)
- [Bayesian Optimization with Unknown Constraints](https://mlsanity.com/paper/1403.5607/) (2014)
- [Re-Examining Linear Embeddings for High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2001.11659/) (2020)
- [Local Latent Space Bayesian Optimization over Structured Inputs](https://mlsanity.com/paper/2201.11872/) (2022)
- [A survey on high-dimensional Gaussian process modeling with application to Bayesian optimization](https://mlsanity.com/paper/2111.05040/) (2021)
- [Adaptive and Safe Bayesian Optimization in High Dimensions via One-Dimensional Subspaces](https://mlsanity.com/paper/1902.03229/) (2019)
- [Uniform Error Bounds for Gaussian Process Regression with Application to Safe Control](https://mlsanity.com/paper/1906.01376/) (2019)
- [Bayesian Optimization with Gradients](https://mlsanity.com/paper/1703.04389/) (2017)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Local policy search with Bayesian optimization](https://mlsanity.com/paper/2106.11899/) (2021)
- [Are Random Decompositions all we need in High Dimensional Bayesian Optimisation?](https://mlsanity.com/paper/2301.12844/) (2023)
- [Local Bayesian optimization via maximizing probability of descent](https://mlsanity.com/paper/2210.11662/) (2022)
- [High-Dimensional Bayesian Optimization via Tree-Structured Additive Models](https://mlsanity.com/paper/2012.13088/) (2020)
- [ProxyBO: Accelerating Neural Architecture Search via Bayesian Optimization with Zero-cost Proxies](https://mlsanity.com/paper/2110.10423/) (2021)
- [The Behavior and Convergence of Local Bayesian Optimization](https://mlsanity.com/paper/2305.15572/) (2023)
- [Robust Model-free Reinforcement Learning with Multi-objective Bayesian Optimization](https://mlsanity.com/paper/1910.13399/) (2019)
- [Tuning Particle Accelerators with Safety Constraints using Bayesian Optimization](https://mlsanity.com/paper/2203.13968/) (2022)

## Built on by (most cited first, 9 of 9)

- [We Still Don't Understand High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2512.00170/) (2025)
- [NeST-BO: Fast Local Bayesian Optimization via Newton-Step Targeting of Gradient and Hessian Information](https://mlsanity.com/paper/2510.05516/) (2025)
- [BayeSQP: Bayesian Optimization through Sequential Quadratic Programming](https://mlsanity.com/paper/2602.03232/) (2026)
- [Bencher: Simple and Reproducible Benchmarking for Black-Box Optimization](https://mlsanity.com/paper/2505.21321/) (2025)
- [Rethinking Trust Region Bayesian Optimization in High Dimensions](https://mlsanity.com/paper/2604.22967/) (2026)
- [Local Entropy Search over Descent Sequences for Bayesian Optimization](https://mlsanity.com/paper/2511.19241/) (2025)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)
- [Local Preferential Bayesian Optimization](https://mlsanity.com/paper/2606.02351/) (2026)
- [GRAPE: Gradient Refinement and Progress-Aware Exploitation for Query-Efficient High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2608.25116/) (2026)

## Abstract (arXiv)

Local Bayesian optimization is a promising practical approach to solve the high dimensional black-box function optimization problem. Among them is the approximated gradient class of methods, which implements a strategy similar to gradient descent. These methods have achieved good experimental results and theoretical guarantees. However, given the distributional properties of the Gaussian processes applied on these methods, there may be potential to further exploit the information of the Gaussian processes to facilitate the BO search. In this work, we develop the relationship between the steps of the gradient descent method and one that minimizes the Upper Confidence Bound (UCB), and show that the latter can be a better strategy than direct gradient descent when a Gaussian process is applied as a surrogate. Through this insight, we propose a new local Bayesian optimization algorithm, MinUCB, which replaces the gradient descent step with minimizing UCB in GIBO. We further show that MinUCB maintains a similar convergence rate with GIBO. We then improve the acquisition function of MinUCB further through a look ahead strategy, and obtain a more efficient algorithm LA-MinUCB. We apply our algorithms on different synthetic and real-world functions, and the results show the effectiveness of our method. Our algorithms also illustrate improvements on local search strategies from an upper bound perspective in Bayesian optimization, and provides a new direction for future algorithm design.