Research map / Optimization / Optimizers
Minimizing UCB: a Better Local Search Strategy in Local Bayesian Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MinUCB and LA-MinUCB, local Bayesian optimization methods that replace the gradient-descent step of GIBO with minimizing a UCB, with polynomial convergence and a look-ahead acquisition for exploration.
Problem
High-dimensional black-box optimization with Gaussian process surrogates, where local approximated-gradient BO methods (GIBO, MPD) use loose upper bounds and underuse GP information.
Approach
Shows that the gradient-descent step corresponds to minimizing a quadratic upper bound, and that minimizing a GP UCB gives a tighter bound and lower point; replaces GIBO's gradient step with UCB minimization (MinUCB) and adds a look-ahead, knowledge-gradient-like exploration acquisition (LA-MinUCB).
Key results
- On high-dimensional synthetic GP objectives (d=25,50,100, 500 evaluations), LA-MinUCB and MinUCB are highly competitive with GIBO and MPD, with LA-MinUCB slightly better.
- On MuJoCo linear policy tasks, LA-MinUCB shows faster convergence and may reach better local optima than GIBO and MPD across CartPole, Swimmer and Hopper.
- MinUCB attains a polynomial convergence rate similar to GIBO's (Wu et al.), with batch sizes that grow over iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace GIBO's gradient-descent exploitation step with UCB minimization (MinUCB) | GIBO · Synthetic GP objectives (25, 50, and 100 dimensions) | current best reward | Helped |
| use look-ahead exploration with UCB-minimizing exploitation (LA-MinUCB) | Local Bayesian optimization · Synthetic GP objectives (25, 50, and 100 dimensions) | current best reward | Helped |
| use look-ahead exploration with UCB-minimizing exploitation (LA-MinUCB) | Local Bayesian optimization · CartPole-v1 | current best reward | Helped |
| use look-ahead exploration with UCB-minimizing exploitation (LA-MinUCB) | Local Bayesian optimization · Swimmer-v1 | current best reward | Helped |
| use look-ahead exploration with UCB-minimizing exploitation (LA-MinUCB) | Local Bayesian optimization · Hopper-v1 (without state normalization) | current best reward | Helped |
| replace gradient descent with UCB minimization (MinUCB) | GIBO · CartPole-v1, Swimmer-v1, and Hopper-v1 | current best reward | Helped |
| use MPD's multi-step descent strategy | MPD · Synthetic GP objectives | current best reward | Hurt |
| use GIBO's gradient-based local exploitation | GIBO · Synthetic GP objectives | convergence speed | Hurt |
Surprising findings
- MPD shows instability after its initial rapid ascent because of its multi-step descent within one iteration.
- GIBO reaches near the local optimum but converges slowly because its strategy is conservative.
Limitations
- Convergence proof is not provided for LA-MinUCB.
- Theoretical dimension dependence is worse than Wu et al. because of the smoothness bound of the GP posterior.
- MinUCB requires iteratively increasing batch sizes and beta_t to guarantee convergence, which is costly in practice.
Experimental setup
Datasets: synthetic GP-sampled functions (RBF kernel, dimensions 25/50/100) MuJoCo CartPole-v1 MuJoCo Swimmer-v1 MuJoCo Hopper-v1
Benchmarks: synthetic GP objectives in d=25,50,100 CartPole-v1 Swimmer-v1 Hopper-v1
Metrics: current best reward vs number of queries
Baselines: GIBO MPD TuRBO ARS
Builds on: GIBO MPD Knowledge Gradient BoTorch one-shot optimization
Closest papers by meaning
- Understanding High-Dimensional Bayesian Optimization (ICML 2025 · similarity 0.90)
- A General Framework for User-Guided Bayesian Optimization (ICLR 2024 · similarity 0.88)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.88)
- Standard Gaussian Process is All You Need for High-Dimensional Bayesian Optimization (ICLR 2025 · similarity 0.88)
- Posterior Inference with Diffusion Models for High-dimensional Black-box Optimization (ICML 2025 · similarity 0.88)
- Vanilla Bayesian Optimization Performs Great in High Dimensions (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.