Research map / Probabilistic and scientific modeling / Bayesian optimization
Optimizing Posterior Samples for Bayesian Optimization via Rootfinding
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 TS-roots, which optimizes GP posterior samples by seeding gradient-based multistart with local minima of a separable prior sample (found via univariate global rootfinding) plus observed locations, and introduces a sample-average posterior acquisition function.
Problem
Global optimization of GP posterior sample paths (the inner loop of Thompson sampling and other posterior-sample acquisition functions) is hard in higher dimensions because samples have exponentially many local optima.
Approach
Use a separable prior sample as a surrogate for the posterior sample: compute its best local minima efficiently via univariate rootfinding and min-heap ordering, then use these plus top observed points as starting points for gradient-based multistart, scaling linearly in dimension.
Key results
- TS-roots gives the best outer-loop results on 2D Schwefel, 16D Ackley and 16D Powell among compared BO methods over 20 runs.
- Rootfinding inner-loop optimization matches random multistart in low dimensions and clearly outperforms random multistart and genetic algorithm in 10D Levy, 16D Ackley and 16D Powell in value and runtime.
- MES with TS-roots outperforms MES with TS-RF on 4D Rosenbrock and 6D Hartmann, especially with 50 f* samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TS-roots instead of TS-DSRF, TS-RF, EI, LCB, and LogEI | Bayesian optimization · 2D Schwefel | outer-loop solution quality | Helped |
| Use TS-roots instead of TS-DSRF, TS-RF, EI, LCB, and LogEI | Bayesian optimization · 16D Ackley | outer-loop solution quality | Helped |
| Use TS-roots instead of TS-DSRF, TS-RF, EI, LCB, and LogEI | Bayesian optimization · 16D Powell | outer-loop solution quality | Helped |
| Use TS-roots instead of LogEI | Bayesian optimization · 4D Rosenbrock | outer-loop solution quality | Helped |
| Use TS-roots instead of LogEI | Bayesian optimization · 10D Levy | outer-loop solution quality | Helped |
| Use TS-roots instead of LogEI | Bayesian optimization · 16D Ackley | outer-loop solution quality | Helped |
| Use rootfinding instead of random multistart and a genetic algorithm | GP-TS inner-loop optimization · 10D Levy, 16D Ackley, and 16D Powell | optimized acquisition value | Helped |
| Use rootfinding instead of random multistart and a genetic algorithm | GP-TS inner-loop optimization · 10D Levy, 16D Ackley, and 16D Powell | optimization runtime | Helped |
| Use TS-roots instead of TS-RF to generate MES samples | MES · 4D Rosenbrock and 6D Hartmann | outer-loop solution quality | Helped |
| Use TS-roots instead of TS-RF to generate MES samples | MES · 10D Levy with 10 samples of f-star | outer-loop solution quality | Helped |
| Use TS-roots instead of TS-RF to generate MES samples | MES · 10D Levy with 50 samples of f-star | outer-loop solution quality | No clear effect |
| Increase the sample-average control parameter from N_c=1 to N_c=10 (ablation) | TS-roots with the sample-average posterior function · 2D Schwefel, 4D Rosenbrock, and 6D Ackley | outer-loop solution quality | Helped |
Surprising findings
- Improving the inner-loop optimization of posterior samples also substantially improves outer-loop BO performance, often outperforming EI and LCB in most cases.
Limitations
- Relies on approximating prior samples as separable functions over a hypercube domain, limiting applicability.
- No analysis yet of how often TS-roots fails to find the global optimum.
- Optimal sample-average parameter N_c has no principled selection method.
Experimental setup
Datasets: Schwefel 2D Rosenbrock 4D Levy 10D Ackley 16D Powell 16D Hartmann 6D ten-bar truss engineering problem
Benchmarks: Schwefel 2D Rosenbrock 4D Levy 10D Ackley 16D Powell 16D Hartmann 6D ten-bar truss
Metrics: log optimality gap of best observed value log distance to true minimizer optimized acquisition value CPU time
Baselines: random multistart genetic algorithm TS-DSRF TS-RF EI LCB LogEI
Builds on: Gaussian process Thompson sampling pathwise conditioning max-value entropy search expected improvement
Closest papers by meaning
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.89)
- Understanding High-Dimensional Bayesian Optimization (ICML 2025 · similarity 0.88)
- Sample-efficient Bayesian Optimisation Using Known Invariances (NeurIPS 2024 · similarity 0.88)
- A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization (ICML 2025 · similarity 0.88)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.88)
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.87)
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.