Research map / Learning theory and algorithms / Prediction and decision losses
Maxing and Ranking with Few Assumptions
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 SST alone (no triangle inequality) with sequential elimination plus anchor pruning for PAC maxing | PAC maxing under SST · Theory (Theorem 6) | comparisons needed for eps-maximum | Helped |
| Remove the triangle inequality assumption and rely on SST only for ranking | PAC ranking under SST · Theory (Theorem 7) | comparisons needed for 1/4-ranking | Hurt |
| Use Borda-score metric with no model assumptions for maxing | PAC Borda maxing · Theory (Theorem 8) | comparisons needed for eps-Borda maximum | Helped |
| Borda-ranking via comparing each element with random opponents and ranking empirical win fractions | PAC Borda ranking with no assumptions · Theory (Theorem 9) | comparisons needed for eps-Borda ranking | Helped |
| Use SEQ-ELIMINATE instead of OPT-MAXIMIZE when n is small (delta around 0.1, n<1000) (ablation) | PAC maxing · Synthetic p=0.6, n up to 1300 | sample complexity | Mixed |
| Use SEQ-ELIMINATE (SST-based) instead of KNOCKOUT (triangle-based) on models without triangle inequality | PAC maxing · Non-triangle SST model, 0.05-maximum, delta=0.1 | success rate and comparisons | Helped |
| Use SEQ-ELIMINATE instead of MallowsMPI for PAC maxing on Mallows model | PAC maxing · Mallows model, n=10, delta=0.05 | comparisons | Helped |
| Use the PL-designed PLPAC instead of SST-based SEQ-ELIMINATE on a non-PL model | PAC maxing · Synthetic p=0.6, 0.09-maximum, n=100 | fraction of runs finding 0.09-maximum | Hurt |
| Use BTM-PAC (regret-oriented bandit method) instead of SEQ-ELIMINATE | PAC maxing · Synthetic p=0.6, small n | comparisons | Hurt |
| Use AR (Borda-max) instead of SEQ-ELIMINATE for maxing | PAC maxing · Synthetic p=0.6, large n | comparisons | Hurt |
Closest papers by meaning
- Maximum Selection and Ranking under Noisy Comparisons (ICML 2017 · similarity 0.92)
- On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons (NeurIPS 2019 · similarity 0.89)
- Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity (ICML 2025 · similarity 0.88)
- Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons (NeurIPS 2021 · similarity 0.88)
- Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.85)
- Beyond Kemeny Medians: Consensus Ranking Distributions. Definition, Properties and Statistical Learning (NeurIPS 2026 · 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.