Research map / Learning theory and algorithms / Sample complexity
The Sample Complexity of Best-$k$ Items Selection from Pairwise Comparisons
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TKS for PAC best-k selection instead of EQS | PAC best-k selection · Synthetic equal-noise data; small k (k≤2) | number of comparisons | Helped |
| Use TKS for PAC best-k selection instead of EQS | PAC best-k selection · Synthetic equal-noise data; k not too small | number of comparisons | Hurt |
| Use TKS rather than EQS within SEEKS (ablation) | Exact best-k selection · Synthetic equal-noise data; k not too small | number of comparisons | Hurt |
| Replace TKS with EQS within SEEKS (ablation) | Exact best-k selection · Synthetic equal-noise data; k=1 | number of comparisons | Hurt |
| Use SEEBS rather than SEEKS | Exact best-item selection · Synthetic equal-noise data; k=1 | number of comparisons | Helped |
| Use TKS instead of EQS for PAC best-item selection | PAC best-item selection · Synthetic equal-noise data; ε=0.001 | number of comparisons | No clear effect |
| Use TKS or SEEKS instead of EQS or SEEKS-v2 | PAC and exact best-k selection · Public election datasets; k=1 | number of comparisons | Helped |
| Use TKS or SEEKS instead of EQS or SEEKS-v2 | PAC and exact best-k selection · Public election datasets; k=4 | number of comparisons | Hurt |
| Use the proposed algorithms on election data that do not satisfy SST or STI | EQS, TKS, SEEBS, and SEEKS · Irish election and web search datasets | correctness: 1-δ | Helped |
Closest papers by meaning
- On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons (NeurIPS 2019 · similarity 0.92)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.88)
- Optimal Sample Complexity of Contrastive Learning (ICLR 2024 · similarity 0.87)
- Sample-Adaptivity Tradeoff in On-Demand Sampling (NeurIPS 2025 · similarity 0.86)
- Active preference learning for ordering items in- and out-of-sample (NeurIPS 2024 · similarity 0.85)
- Clustering Items through Bandit Feedback: Finding the Right Feature out of Many (ICML 2025 · similarity 0.85)
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.