Research map / Probabilistic and scientific modeling / Uncertainty and Gaussian processes
Practical Bayesian Algorithm Execution via Posterior Sampling
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 PS-BAX, a posterior-sampling method for Bayesian algorithm execution that selects evaluation points by running the base algorithm once on a posterior sample and picking the most uncertain point in the sampled target set.
Problem
Estimating the output of an expensive base algorithm applied to a black-box function, where running the base algorithm directly needs too many evaluations; existing EIG-based BAX methods (INFO-BAX) are computationally costly.
Approach
Sample a function from the GP posterior, run the base algorithm on that sample to get a target set, then evaluate the point in that set with highest posterior uncertainty. This extends posterior (Thompson) sampling beyond optimization to general target-set properties, avoiding expensive EIG maximization.
Key results
- PS-BAX is 1-3 orders of magnitude faster per iteration than INFO-BAX (e.g., 0.37s vs 7.64s on Hartmann-6D, 0.49s vs 289.91s on Volcano).
- On Ackley-10D local optimization PS-BAX significantly outperforms EI and INFO-BAX; on Hartmann-6D it performs on par with EI.
- On topographic level set estimation PS-BAX outperforms all baselines including LSE; PS-BAX outperforms INFO-BAX on five of eight problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PS-BAX instead of INFO-BAX | BAX · Hartmann (6D) | runtime per iteration: 7.64 -> 0.37 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · Ackley (10D) | runtime per iteration: 29.31 -> 3.36 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · Himmelblau | runtime per iteration: 14.97 -> 0.57 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · Volcano | runtime per iteration: 289.91 -> 0.49 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · Rosenbrock (k=6) | runtime per iteration: 18.31 -> 0.92 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · GB1 (k=10) | runtime per iteration: 865.85 -> 145.23 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · Tau Protein Assay | runtime per iteration: 113.20 -> 3.78 s | Helped |
| use PS-BAX instead of INFO-BAX | BAX · Interferon-Gamma Assay | runtime per iteration: 97.03 -> 3.95 s | Helped |
| use PS-BAX instead of INFO-BAX | local optimization on Hartmann (6D) · Hartmann (6D) | log10 inference regret | Helped |
| use PS-BAX instead of INFO-BAX and EI | local optimization on Ackley (10D) · Ackley (10D) | log10 inference regret | Helped |
| use PS-BAX instead of the baselines | level set estimation · Himmelblau | F1 score | No clear effect |
| use PS-BAX instead of the baselines | level set estimation · Volcano | F1 score | Helped |
Surprising findings
- A constructed example shows PS-BAX can fail to concentrate its posterior (limit probability 1/2) when the target set is not complement-independent.
Limitations
- Narrower class of problems than EIG-based methods; requires target set to be complement-independent for convergence.
- Not asymptotically consistent for some non-complement-independent algorithms.
- Experiments rely on GP models and approximations (1000 random Fourier features) and a single fixed base algorithm per problem.
Experimental setup
Datasets: Hartmann-6D Ackley-10D Himmelblau Maunga Whau volcano topographic data Rosenbrock GB1 protein fitness Achilles tau protein assay Achilles interferon-gamma assay
Benchmarks: Hartmann-6D Ackley-10D Himmelblau Volcano topographic Rosenbrock top-k GB1 top-k DiscoBAX tau protein DiscoBAX interferon-gamma
Metrics: log10 inference regret F1 score Jaccard distance regret wall-clock runtime
Baselines: INFO-BAX Random Expected improvement LSE
Builds on: INFO-BAX Bayesian algorithm execution Thompson sampling joint entropy search BoTorch
Closest papers by meaning
- Bayesian Optimisation with Unknown Hyperparameters: Regret Bounds Logarithmically Closer to Optimal (NeurIPS 2024 · similarity 0.86)
- Informed Initialization for Bayesian Optimization and Active Learning (NeurIPS 2025 · similarity 0.86)
- Stopping Bayesian Optimization with Probabilistic Regret Bounds (NeurIPS 2024 · similarity 0.86)
- Optimizing Posterior Samples for Bayesian Optimization via Rootfinding (ICLR 2025 · similarity 0.86)
- BayeSQP: Bayesian Optimization through Sequential Quadratic Programming (NeurIPS 2025 · similarity 0.86)
- BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability (NeurIPS 2026 · similarity 0.86)
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.