Research map / Probabilistic and scientific modeling / Bayesian optimization
Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal
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 Length scale Balancing (LB-GP-UCB), which aggregates GP-UCB base learners with progressively added shorter length scales via regret-balancing with elimination, achieving a regret bound only log g(T) from oracle.
Problem
Bayesian optimisation with an unknown GP length scale (smoothness) hyperparameter, where MLE may pick a length scale that is too long and misspecify the RKHS class, and prior A-GP-UCB over-explores without a stopping mechanism.
Approach
Extends regret-balancing with elimination to infinitely many base learners: GP-UCB base learners with different length scales share data, the master picks the one with smallest suspected regret, eliminates underperformers, and intermittently adds shorter length scales while keeping longer ones.
Key results
- LB-GP-UCB's regret bound is O(d ln g(T)) relative to oracle, versus O(g(T)^d) for A-GP-UCB.
- On the Berkenkamp toy problem, A-GP-UCB's cumulative regret grows faster than LB-GP-UCB's due to over-exploration; MLE and MCMC get stuck in the local optimum.
- On Michalewicz and material design tasks, LB-GP-UCB performs well across both regret metrics and is more robust than A-GP-UCB to the choice of growth function g(t).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace A-GP-UCB's progressively decreasing length scale with regret balancing over length-scale candidates | Bayesian optimization with unknown length scale · Unknown length scale θ | Regret ratio R_T / R*(T): \mathcal{O}(g(T)^{d}) -> \mathcal{O}({d} \ln g(T)) | Helped |
| Extend length-scale balancing to also balance candidate norm values | Bayesian optimization with unknown length scale and norm · Unknown length scale θ and norm B | Regret ratio R_T / R*(T): \mathcal{O}(b(T)g(T)^{d}) -> \mathcal{O}({d} \ln g(T) \ln b(T)) | Helped |
| Use LB-GP-UCB rather than MLE or MCMC for length-scale selection | Bayesian optimization · Berkenkamp Toy Problem | Cumulative regret | Helped |
| Use LB-GP-UCB rather than A-GP-UCB | Bayesian optimization · Berkenkamp Toy Problem | Cumulative regret | Helped |
| Use LB-GP-UCB rather than the other baselines | Bayesian optimization · Michalewicz | Cumulative regret | Helped |
| Use LB-GP-UCB rather than the other baselines | Bayesian optimization · Michalewicz | Best regret | Helped |
| Use LB-GP-UCB rather than MLE or MCMC | Bayesian optimization · AGNP | Best regret | Helped |
| Use LB-GP-UCB rather than A-GP-UCB | Bayesian optimization · CrossedBarrel | Cumulative regret | Helped |
| Vary the growth function to g(t) = max(t₀, tᵃ), with a in (0.25, 0.5, 0.75) (ablation) | LB-GP-UCB on Michalewicz · Michalewicz | Best regret | No clear effect |
| Vary the growth function to g(t) = max(t₀, tᵃ), with a in (0.25, 0.5, 0.75) (ablation) | A-GP-UCB on Michalewicz · Michalewicz | Best regret | Mixed |
Limitations
- Only handles isotropic length scales; non-isotropic case requires MIG bounds not available.
- Assumes known noise magnitude sigma_N.
- Standard GP scalability limits to large datasets and high dimensions.
Experimental setup
Datasets: Berkenkamp toy function Michalewicz function CrossedBarrel material design AGNP material design
Benchmarks: Berkenkamp toy problem Michalewicz (5-D) CrossedBarrel (4-D) AGNP (5-D)
Metrics: cumulative regret best regret selected length scale histogram
Baselines: A-GP-UCB MLE MCMC (NUTS)
Builds on: GP-UCB A-GP-UCB regret balancing with elimination
Closest papers by meaning
- BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability (NeurIPS 2026 · similarity 0.90)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.90)
- This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization (NeurIPS 2024 · similarity 0.90)
- Principled Preferential Bayesian Optimization (ICML 2024 · similarity 0.89)
- Bayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs (AAAI 2025 · similarity 0.89)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.89)
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.