Research map / Probabilistic and scientific modeling / Bayesian optimization
Active Set Ordering
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.
Formalizes active set ordering (actively estimating top-k sets via pairwise orderings of noisy blackbox evaluations) and proposes the mean prediction (MP) algorithm with a sublinear cumulative regret bound, recovering GP-UCB as the k=1 special case.
Problem
Estimating subsets of a finite input domain defined by pairwise orderings of expensive, noisy blackbox function evaluations (top-k sets), which lies between experimental design and Bayesian optimization/level set estimation.
Approach
Define a regret for predicted pairwise orderings, predict the top-k set from GP posterior means, and select sampling inputs at the boundary of the predicted top-k set so that the confidence-interval width bounds the regret; with k=1 this recovers GP-UCB's sampling rule and regret bound.
Key results
- MP with any of the four sampling choices in Lemma 4.3 converges to lower top-5 set regret than Var and Rand across synthetic and environmental datasets (15 repeats).
- Theorem 4.4 gives a cumulative regret bound O(sqrt(T beta_T gamma_T)) for MP, which for SE kernels gives O*(sqrt(T (log T)^{2d})).
- On Bayesian optimization (k=1), MP performs comparably to GP-UCB, while EI and MES outperform GP-UCB in some experiments.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MP with any of the four Lemma 4.3 sampling choices instead of Var or Rand | MP for active set ordering · Top-5 set: GP sample, Branin-Hoo, Goldstein-Price, Hartmann-6D, NO3, Phosphorus, and Humidity | regret | Helped |
| Vary the sampling input among ¯xt ▽ ¯x′t, ¯xt △ ¯x′t, ¯xt ∨ ¯x′t, and ¯xt ∧ ¯x′t (ablation) | MP for active set ordering · Top-5 set: GP sample, Branin-Hoo, Goldstein-Price, Hartmann-6D, NO3, Phosphorus, and Humidity | regret | No clear effect |
| Use MP with any of the four sampling choices instead of Var or Rand | MP for active multiple set ordering · S(1), S(10), and S(20): GP sample, Branin-Hoo, Goldstein-Price, Hartmann-6D, NO3, Phosphorus, and Humidity | maximum regret | Helped |
| Use MP sampling choices ¯xt △ ¯x′t, ¯xt ∨ ¯x′t, or ¯xt ∧ ¯x′t instead of the GP-UCB-equivalent choice ¯xt ▽ ¯x′t (ablation) | MP for Bayesian optimization · Branin-Hoo, NO3, Phosphorus, and Humidity | regret | No clear effect |
| Use EI or MES instead of MP/GP-UCB | Bayesian optimization · NO3 and Phosphorus | regret | Helped |
| Use EI or MES instead of MP/GP-UCB | Bayesian optimization · Branin-Hoo and Humidity | regret | No clear effect |
Surprising findings
- Expected improvement and max-value entropy search outperform GP-UCB (and hence MP) on some BO experiments.
- Uncertainty sampling (Var) spreads samples across the whole domain and performs worse than MP, which focuses on the top-k boundary.
Limitations
- Assumes a finite input domain and that f lies in an RKHS with bounded norm.
- Theory covers the regret of predicted orderings under a known noise variance and GP model correctness; empirical evaluation limited to 100-400 point domains and 15 repeats.
Experimental setup
Datasets: Lake Zurich NO3 dataset Brooms Barn phosphorus dataset Intel Lab humidity dataset Branin-Hoo Goldstein-Price Hartmann-6D GP sample
Benchmarks: Branin-Hoo Goldstein-Price Hartmann-6D GP sample NO3 (Lake Zurich) Phosphorus (Brooms Barn) Humidity (Intel Lab)
Metrics: cumulative regret of predicted top-k set maximum regret over multiple top-k sets simple regret of predicted maximizer
Baselines: Var (uncertainty sampling) Rand GP-UCB probability of improvement expected improvement max-value entropy search
Builds on: GP-UCB level set estimation max-value entropy search
Closest papers by meaning
- Principled Preferential Bayesian Optimization (ICML 2024 · similarity 0.86)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.85)
- Improved Regret Bounds for Gaussian Process Upper Confidence Bound in Bayesian Optimization (NeurIPS 2025 · similarity 0.85)
- Posterior Sampling-Based Bayesian Optimization with Tighter Bayesian Regret Bounds (ICML 2024 · similarity 0.85)
- Amortized Active Generation of Pareto Sets (NeurIPS 2025 · similarity 0.84)
- Transductive Active Learning: Theory and Applications (NeurIPS 2024 · similarity 0.84)
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.