Pith. sign in

REVIEW 6 minor 71 references

Optimal Top-$k$ Identification from Pairwise Comparisons

T0 review · 0 major / 6 minor · reviewed 2026-07-13 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read An online algorithm matches the information lower bound for fixed-confidence top-k identification from pairwise comparisons under latent utilities.

desk verdict Solid asymptotic-optimality result for top-k from pairwise comparisons; the boundary-pair saddle point is the real contribution, and the proofs hold under standard assumptions. read the letter →

arxiv 2607.08979 v1 pith:RLXK7JKJ submitted 2026-07-09 cs.LG stat.APstat.MLstat.OT

Motti Goldberger , Nils Rudi This is my paper
classification cs.LGstat.APstat.MLstat.OT
keywords top-kidentificationpairwisecomparisonsfixed-confidencepureexplorationasymptoticoptimalityTrack-and-Stopprimal-dualonlinelearninglatentutilitymodelsBradley-Terry
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies how to find the top-k items among n candidates by adaptively choosing noisy pairwise comparisons and stopping only when the returned set is correct with probability at least 1-δ. The design goal is to make the expected number of comparisons as small as possible. Information theory supplies a lower bound on that expectation that is governed by an oracle allocation of comparisons; until now no algorithm was known to match that bound for top-k under a latent-utility model. The authors rewrite the oracle problem as a two-player game whose equilibrium gives both the optimal sampling proportions and the minimal sample complexity. They then build a primal-dual online learner that tracks that equilibrium from data and prove that the resulting adaptive procedure is asymptotically optimal: its expected stopping time, divided by log(1/δ), tends exactly to the reciprocal of the information rate as δ goes to zero. A sympathetic reader cares because the same reduction and tracking scheme apply to both binary and cardinal comparisons and yield a practical algorithm that is competitive with existing elimination methods on moderate-sized instances.

What carries the argument

The boundary reduction of the alternative set: every alternative parameter must invert at least one of the k(n-k) boundary pairs that straddle the true top-k cut. This turns the max-min oracle program into a saddle-point game F(w,q;θ) whose primal-dual gradients can be estimated by sampling a single boundary pair, enabling efficient entropic FTRL updates that track the optimal design.

What would settle it

On any fixed positive-gap instance, plot E[τ_δ]/log(1/δ) against log(1/δ) for successively smaller δ; the curve must approach the constant 1/Γ*(θ) computed from the true θ, not merely stay within a log-factor of existing elimination bounds.

Watch

Extended reading notes

Core claim

For top-k identification under a latent-utility pairwise model, the information-theoretic lower bound is attained by a computationally tractable primal-dual procedure that learns the optimal comparison allocation online; the resulting Track-and-Stop algorithm is δ-correct and satisfies lim δ o0 E[τ_δ]/log(1/δ) = 1/Γ*(θ).

Load-bearing premise

Utilities are confined to a known bounded range so that the exponential-family link has uniform curvature and sub-Gaussian tails on that compact set.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 6 minor

Summary. The paper studies fixed-confidence top-k identification from noisy pairwise comparisons under a latent-utility exponential-family model. It derives the instance-dependent lower bound Γ*(θ) via a boundary-pair reduction of Alt(θ), reformulates the oracle allocation as a saddle-point game F(w,q;θ), and gives an adaptive algorithm that tracks this equilibrium online by entropic FTRL with stochastic gradients, C-tracking sampling, and a GLR stopping rule. The main results are δ-correctness (Proposition 6.4) and asymptotic optimality (Theorem 6.5): lim_{δ→0} E_θ[τ_δ]/log(1/δ) = 1/Γ*(θ), matching the information-theoretic lower bound of Theorem 3.4 including constants. Simulations compare the method to SEEKS and Active Ranking on synthetic instances.

Significance. This appears to be the first algorithm that is asymptotically optimal (exact constant match as δ→0) for top-k identification from pairwise comparisons under latent-utility models, filling a gap relative to Track-and-Stop-style results for multi-armed and linear bandits and to existing pairwise top-k procedures that are optimal only up to log factors or under different models. The boundary reduction to k(n-k) half-spaces and the resulting primal–dual game are clean and make online learning of the allocation computationally tractable via single-boundary-pair stochastic gradients. Full appendix proofs of δ-correctness and asymptotic optimality, built from standard martingale, FTRL-regret, and C-tracking arguments, are a clear strength. The contribution is solid for the pure-exploration literature even if practical moderate-δ performance remains limited by the stopping threshold.

minor comments (6)
  1. Section 7 and Figure 1: the equally-spaced and SST instances show that the GLR threshold (4) can make Algorithm 1 worse than SEEKS at δ=0.01 when ∥θ̂_t∥₂ grows with n. Figure 2 partially addresses this for smaller δ, but a short quantitative discussion of when β(t,δ) becomes tight (e.g., relative size of log(1/δ) vs. (λ/2)∥θ̂∥₂²) would help readers set expectations.
  2. Section 5.5: the O(k(n-k)n²) cost of the full stopping check is noted; stating the sparse-check schedule used in the experiments (or that none was used) would improve reproducibility.
  3. Appendix G.3 and the choice of α=0.2, γ=1/3: the sensitivity plots (Figures 3–4) are useful; a one-sentence default recommendation in the main text (e.g., α∈[0.15,0.3], γ=1/3) would make the algorithm easier to reimplement.
  4. Assumption 3 and Θ_gap: the positive-gap condition is standard, but a brief remark that the algorithm’s finite-time behavior near vanishing gaps is not characterized (only the asymptotic rate for fixed θ∈Θ_gap) would clarify the scope.
  5. Related work (Section 2.2): Wang et al. (2021) are correctly distinguished as nonparametric/combinatorial; a single sentence on whether their Frank–Wolfe oracle could be specialized to the latent-utility boundary structure would further situate the contribution.
  6. Notation table and Algorithm 1: ˆB_t vs B(θ) and Θ_ij(t) are clear in the appendix but slightly dense in Section 5; a short inline reminder that after t_stab the estimated boundary equals the true one (Corollary 6.2) would help the main-text reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: asymptotic optimality matches an independent information-theoretic lower bound via standard Track-and-Stop analysis, not by construction or self-citation.

full rationale

The central claim (Theorem 6.5) equates lim δ→0 E_θ[τ_δ]/log(1/δ) to 1/Γ*(θ). Γ*(θ) is defined independently of the algorithm as the max–min KL rate over Alt(θ) (Section 3.3, Theorem 3.4 from Garivier & Kaufmann 2016 / Kaufmann et al. 2016). The paper’s contribution is structural: boundary reduction of Alt(θ) to k(n−k) half-spaces, saddle-point formulation of F via Sion, and an online primal–dual (entropic FTRL) + C-tracking sampler that achieves that rate (Sections 4–6). The matching upper bound is proved by high-probability oracle-rate tracking (Prop. 6.3), GLR stopping with a mixture-martingale threshold (Prop. 6.4), and a standard limsup argument (App. E)—none of which redefine Γ* from the algorithm’s own sample complexity. No free parameters are fitted to the target complexity expression; α and γ are algorithm hyperparameters whose ranges still yield the asymptotic limit. Citations are to external pure-exploration tools (Garivier–Kaufmann, Degenne et al., Kaufmann–Koolen, Abbasi-Yadkori et al.), not to load-bearing uniqueness theorems by the same authors. Boundedness of Θ is an assumption used for concentration, not a circular fit. The derivation is therefore self-contained against the external lower bound and is not circular.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central asymptotic-optimality claim rests on the standard pure-exploration lower-bound machinery plus three modeling assumptions that make the KL projections well-posed and the MLE consistent. Free parameters are only the learning-rate schedules chosen for the online algorithm; they do not enter the lower bound itself. No new physical or statistical entities are postulated.

free parameters (3)
  • FTRL learning-rate exponent α = 0.2
    Set to 0.2 after oracle experiments; controls the decay of μ_t = t^{-α}. Affects finite-time regret but not the asymptotic claim.
  • C-tracking mixing exponent γ = 1/3
    Set to 1/3 to balance mixing bias and estimation error (Prop. 6.3). Again finite-time only.
  • parameter bound R
    Defines the compact set Θ = {θ : ∑θ_i=0, ∥θ∥_∞≤R}. Used for uniform curvature and concentration; treated as a known modeling constant.
assumptions (4)
  • domain assumption Comparison outcomes belong to a one-parameter exponential family with natural parameter θ_i−θ_j and log-partition A satisfying 0 < A″(η) ≤ σ² on the relevant range (Assumptions 1–2).
    Standard for Bradley–Terry / Gaussian-difference models; invoked throughout Sections 3–6 for KL expressions and MLE concentration.
  • domain assumption True parameter θ lies in the interior of the bounded set Θ and has a strict top-k gap (Assumption 3).
    Ensures uniqueness of S*(θ) and well-posedness of the alternative region Alt(θ).
  • standard math Sion’s minimax theorem applies to the continuous concave-convex function F on compact convex simplices, yielding existence of a saddle point (w*,q*).
    Used in Section 4.2 to interchange max_w min_q.
  • standard math Garivier–Kaufmann change-of-measure lower bound (Theorem 3.4) holds for any δ-correct strategy.
    Imported from the pure-exploration literature; the paper only specializes the alternative set.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal Top-$k$ Identification from Pairwise Comparisons." pith.science (2026). https://pith.science/paper/RLXK7JKJ

@misc{pith2026260708979,
  author       = {Pith},
  title        = {Pith review of: Optimal Top-$k$ Identification from Pairwise Comparisons},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RLXK7JKJ}},
  note         = {Machine review of arXiv:2607.08979}
}
abstract

We study the active learning problem of fixed-confidence top-$k$ identification from noisy pairwise comparisons. In this problem, an algorithm sequentially chooses pairs of items to compare, observes the outcomes, and stops when it can return the set of top-$k$ items with error probability at most $\delta$. The objective is to design such a $\delta$-correct procedure that minimizes the expected number of comparisons (the sample complexity). This problem falls within the broader literature on fixed-confidence pure exploration in bandit models, where a common target is asymptotic optimality: the algorithm's expected sample complexity matches the information theoretic lower bound as $\delta \to 0$. Asymptotically optimal procedures have been developed for a range of fixed-confidence pure-exploration problems, however to the best of our knowledge, for top-$1$, or more generally top-$k$ identification from pairwise comparisons under latent utility models an asymptotically optimal algorithm has not been established. In this setting, we develop such an algorithm. We characterize the structure of the lower bound and formulate it as a saddle-point problem. This structure enables a computationally efficient primal-dual procedure that learns the asymptotically optimal comparison allocation online. We then construct an adaptive comparison-allocation algorithm that tracks the allocation learned by the primal-dual procedure and prove it is asymptotically optimal.

Figures

Figures reproduced from arXiv: 2607.08979 by the authors.

Figure 1
Figure 1. Mean stopping times over 100 simulations with δ = 0.01. Columns correspond to the three instances; rows correspond to (a) varying n with k = 5 fixed, and (b) varying k with n = 100 fixed. increases, but does not increase for SEEKS and SEEKS-v2. The primary driver is that our stopping threshold grows with ∥θˆ t∥ 2 2 , which grows with n in this equally spaced in￾stance. Theorem 6.5 guarantees that for sufficiently sm… view at source ↗
Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Mean stopping time over 100 simulations as a function of the learning-rate exponent α for varying k, on the Equally Spaced instance with n = 50, gap = 0.25, and δ = 0.01. Each panel compares Algorithm 1 (blue) to the Online Oracle (orange) at k ∈ {1, 2, 3, 5, 10} [PITH_FULL_IMAGE:figures/full_fig_p028_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Mean stopping time over 100 simulations as a function of the learning-rate exponent α, on the Equally Spaced instance with k = 5 and δ = 0.01. Rows vary n ∈ {20, 50, 100}; columns vary gap ∈ {0.1, 0.25}. Algorithm 1 (blue) versus Online Oracle (orange). 28 [PITH_FULL_…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

71 extracted references · 2 linked inside Pith

  1. [1]

    and Li, Tianle and Li, Dacheng and Zhu, Banghua and Zhang, Hao and Jordan, Michael I

    Chiang, Wei-Lin and Zheng, Lianmin and Sheng, Ying and Angelopoulos, Anastasios N. and Li, Tianle and Li, Dacheng and Zhu, Banghua and Zhang, Hao and Jordan, Michael I. and Gonzalez, Joseph E. and Stoica, Ion , booktitle =. Chatbot Arena: An Open Platform for Evaluating

  2. [2]

    and Chen, Ted Hsuan Yun , title =

    Narimanzadeh, Hasti and Badie-Modiri, Arash and Smirnova, Iuliia G. and Chen, Ted Hsuan Yun , title =. Proceedings of the ACM on Human-Computer Interaction , volume =

  3. [3]

    Proceedings of the 2017 ACM International Conference on Management of Data , address =

    Kou, Ngai Meng and Li, Yan and Wang, Hao and U, Leong Hou and Gong, Zhiguo , title =. Proceedings of the 2017 ACM International Conference on Management of Data , address =

    2017

  4. [4]

    and Collins-Thompson, Kevyn and Horvitz, Eric , title =

    Chen, Xi and Bennett, Paul N. and Collins-Thompson, Kevyn and Horvitz, Eric , title =. Proceedings of the Sixth ACM International Conference on Web Search and Data Mining , address =

  5. [5]

    Proceedings of the 12th ACM Conference on Recommender Systems , address =

    Kalloori, Saikishore and Ricci, Francesco and Gennari, Rosella , title =. Proceedings of the 12th ACM Conference on Recommender Systems , address =

  6. [6]

    Identification of the Generalized Condorcet Winner in Multi-dueling Bandits , booktitle =

    Bj. Identification of the Generalized Condorcet Winner in Multi-dueling Bandits , booktitle =

  7. [7]

    Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence , pages =

    Dueling Bandits with Qualitative Feedback , author =. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence , pages =

  8. [8]

    Proceedings of the Thirty-Second Conference on Learning Theory , pages =

    Sorted Top-k in Rounds , author =. Proceedings of the Thirty-Second Conference on Learning Theory , pages =

Show all 71 references
  1. [9]

    IEEE Transactions on Information Theory , volume =

    Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues , author =. IEEE Transactions on Information Theory , volume =

  2. [10]

    Saha, Aadirupa and Gopalan, Aditya , booktitle =. From

  3. [11]

    Saha, Aadirupa and Gopalan, Aditya , booktitle =

  4. [12]

    Journal of Machine Learning Research , volume =

    On the Complexity of Best-Arm Identification in Multi-Armed Bandit Models , author =. Journal of Machine Learning Research , volume =

  5. [13]

    Proceedings of the 29th Annual Conference on Learning Theory , pages =

    Optimal Best Arm Identification with Fixed Confidence , author =. Proceedings of the 29th Annual Conference on Learning Theory , pages =

  6. [14]

    Journal of Machine Learning Research , volume =

    Preference-based Online Learning with Dueling Bandits: A Survey , author =. Journal of Machine Learning Research , volume =

  7. [15]

    Proceedings of the 30th International Conference on Machine Learning , pages =

    Top- k Selection Based on Adaptive Sampling of Noisy Preferences , author =. Proceedings of the 30th International Conference on Machine Learning , pages =

  8. [16]

    Proceedings of the 37th International Conference on Machine Learning , pages =

    The Sample Complexity of Best- k Items Selection from Pairwise Comparisons , author =. Proceedings of the 37th International Conference on Machine Learning , pages =

  9. [17]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

    A Nearly Instance Optimal Algorithm for Top- k Ranking under the Multinomial Logit Model , author =. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =

  10. [18]

    , journal =

    Ren, Wenbo and Liu, Jia and Shroff, Ness B. , journal =

  11. [19]

    and Ramchandran, Kannan and Wainwright, Martin J

    Heckel, Reinhard and Shah, Nihar B. and Ramchandran, Kannan and Wainwright, Martin J. , title =. The Annals of Statistics , volume =

  12. [20]

    Proceedings of the 34th International Conference on Machine Learning , pages =

    Mohajer, Soheil and Suh, Changho and Elmahdy, Adel , title =. Proceedings of the 34th International Conference on Machine Learning , pages =

  13. [21]

    The Annals of Statistics , volume =

    Yuxin Chen and Jianqing Fan and Cong Ma and Kaizheng Wang , title =. The Annals of Statistics , volume =

  14. [22]

    Operations Research , volume =

    Sahand Negahban and Sewoong Oh and Devavrat Shah , title =. Operations Research , volume =

  15. [24]

    Proceedings of the 33rd International Conference on Machine Learning , pages =

    Ashish Khetan and Sewoong Oh , title =. Proceedings of the 33rd International Conference on Machine Learning , pages =

  16. [25]

    Spectral

    Chen, Yuxin and Suh, Changho , booktitle =. Spectral

  17. [26]

    Advances in Neural Information Processing Systems 27 , pages =

    Bruce Hajek and Sewoong Oh and Jiaming Xu , title =. Advances in Neural Information Processing Systems 27 , pages =

  18. [27]

    Non-Asymptotic Pure Exploration by Solving Games , booktitle =

    Degenne, R. Non-Asymptotic Pure Exploration by Solving Games , booktitle =

  19. [28]

    Gamification of Pure Exploration for Linear Bandits , booktitle =

    Degenne, R. Gamification of Pure Exploration for Linear Bandits , booktitle =

  20. [29]

    Optimal Best-Arm Identification in Linear Bandits , booktitle =

    Jedra, Yassir and Prouti. Optimal Best-Arm Identification in Linear Bandits , booktitle =

  21. [30]

    Fast Pure Exploration via Frank-Wolfe , booktitle =

    Wang, Po-An and Tzeng, Ruo-Chun and Prouti. Fast Pure Exploration via Frank-Wolfe , booktitle =

  22. [31]

    Journal of Machine Learning Research , volume =

    Mixture Martingales Revisited with Applications to Sequential Tests and Confidence Intervals , author =. Journal of Machine Learning Research , volume =

  23. [32]

    Advances in Neural Information Processing Systems 24 , pages =

    Improved Algorithms for Linear Stochastic Bandits , author =. Advances in Neural Information Processing Systems 24 , pages =

  24. [33]

    Foundations and Trends in Machine Learning , volume =

    Shalev-Shwartz, Shai , title =. Foundations and Trends in Machine Learning , volume =

  25. [34]

    Foundations and Trends in Optimization , volume =

    Hazan, Elad , title =. Foundations and Trends in Optimization , volume =

  26. [35]

    Theory of Computing , volume =

    Arora, Sanjeev and Hazan, Elad and Kale, Satyen , title =. Theory of Computing , volume =

  27. [36]

    2020 , publisher =

    Bandit Algorithms , author =. 2020 , publisher =

    2020

  28. [37]

    Improved algorithms for linear stochastic bandits

    Abbasi-Yadkori, Y., P \'a l, D., and Szepesv \'a ri, C. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems 24, pp.\ 2312--2320, 2011

    2011

  29. [38]

    The multiplicative weights update method: a meta-algorithm and applications

    Arora, S., Hazan, E., and Kale, S. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8: 0 121--164, 2012

    2012

  30. [39]

    Preference-based online learning with dueling bandits: A survey

    Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A., and H \"u llermeier, E. Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research, 22: 0 1--108, 2021

    2021

  31. [40]

    Sorted top-k in rounds

    Braverman, M., Mao, J., and Peres, Y. Sorted top-k in rounds. In Proceedings of the Thirty-Second Conference on Learning Theory, pp.\ 342--382, 2019

    2019

  32. [41]

    o r \'e nyi, B., Weng, P., Cheng, W., and H \

    Busa-Fekete, R., Sz \"o r \'e nyi, B., Weng, P., Cheng, W., and H \"u llermeier, E. Top- k selection based on adaptive sampling of noisy preferences. In Proceedings of the 30th International Conference on Machine Learning, pp.\ 1094--1102, 2013

    2013

  33. [42]

    N., Collins-Thompson, K., and Horvitz, E

    Chen, X., Bennett, P. N., Collins-Thompson, K., and Horvitz, E. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pp.\ 193--202, Rome, Italy, 2013

    2013

  34. [43]

    A nearly instance optimal algorithm for top- k ranking under the multinomial logit model

    Chen, X., Li, Y., and Mao, J. A nearly instance optimal algorithm for top- k ranking under the multinomial logit model. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\ 2504--2522, 2018

    2018

  35. [44]

    and Suh, C

    Chen, Y. and Suh, C. Spectral MLE : Top - K rank aggregation from pairwise comparisons. In Proceedings of the 32nd International Conference on Machine Learning, pp.\ 371--380, 2015

    2015

  36. [45]

    Spectral method and regularized MLE are both optimal for Top - K ranking

    Chen, Y., Fan, J., Ma, C., and Wang, K. Spectral method and regularized MLE are both optimal for Top - K ranking. The Annals of Statistics, 47 0 (4): 0 2204--2235, 2019

    2019

  37. [46]

    N., Li, T., Li, D., Zhu, B., Zhang, H., Jordan, M

    Chiang, W.-L., Zheng, L., Sheng, Y., Angelopoulos, A. N., Li, T., Li, D., Zhu, B., Zhang, H., Jordan, M. I., Gonzalez, J. E., and Stoica, I. Chatbot arena: An open platform for evaluating LLM s by human preference. In Proceedings of the 41st International Conference on Machine...

    2024

  38. [47]

    M., and M \'e nard, P

    Degenne, R., Koolen, W. M., and M \'e nard, P. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems 32, pp.\ 14492--14501, 2019

    2019

  39. [48]

    Gamification of pure exploration for linear bandits

    Degenne, R., M \'e nard, P., Shang, X., and Valko, M. Gamification of pure exploration for linear bandits. In Proceedings of the 37th International Conference on Machine Learning, pp.\ 2432--2442, 2020

    2020

  40. [49]

    and Kaufmann, E

    Garivier, A. and Kaufmann, E. Optimal best arm identification with fixed confidence. In Proceedings of the 29th Annual Conference on Learning Theory, pp.\ 998--1027, 2016

    2016

  41. [50]

    Identification of the generalized condorcet winner in multi-dueling bandits

    Haddenhorst, B., Bengs, V., and H \"u llermeier, E. Identification of the generalized condorcet winner in multi-dueling bandits. In Advances in Neural Information Processing Systems 34, pp.\ 25904--25916, 2021

    2021

  42. [51]

    Minimax-optimal inference from partial rankings

    Hajek, B., Oh, S., and Xu, J. Minimax-optimal inference from partial rankings. In Advances in Neural Information Processing Systems 27, pp.\ 1475--1483, 2014

    2014

  43. [52]

    Introduction to online convex optimization

    Hazan, E. Introduction to online convex optimization. Foundations and Trends in Optimization, 2 0 (3-4): 0 157--325, 2016

    2016

  44. [53]

    B., Ramchandran, K., and Wainwright, M

    Heckel, R., Shah, N. B., Ramchandran, K., and Wainwright, M. J. Active ranking from pairwise comparisons and when parametric assumptions don’t help. The Annals of Statistics, 47 0 (6): 0 3099--3126, 2019

    2019

  45. [54]

    Top- K ranking from pairwise comparisons: When spectral ranking is optimal

    Jang, M., Kim, S., Suh, C., and Oh, S. Top- K ranking from pairwise comparisons: When spectral ranking is optimal. arXiv preprint arXiv:1603.04153, 2016

    2016 arXiv

  46. [55]

    and Prouti \`e re, A

    Jedra, Y. and Prouti \`e re, A. Optimal best-arm identification in linear bandits. In Advances in Neural Information Processing Systems 33, pp.\ 10007--10017, 2020

    2020

  47. [56]

    Eliciting pairwise preferences in recommender systems

    Kalloori, S., Ricci, F., and Gennari, R. Eliciting pairwise preferences in recommender systems. In Proceedings of the 12th ACM Conference on Recommender Systems, pp.\ 329--337, Vancouver, BC, Canada, 2018

    2018

  48. [57]

    and Koolen, W

    Kaufmann, E. and Koolen, W. M. Mixture martingales revisited with applications to sequential tests and confidence intervals. Journal of Machine Learning Research, 22: 0 1--44, 2021

    2021

  49. [58]

    On the complexity of best-arm identification in multi-armed bandit models

    Kaufmann, E., Capp \'e , O., and Garivier, A. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17: 0 1--42, 2016

    2016

  50. [59]

    and Oh, S

    Khetan, A. and Oh, S. Data-driven rank breaking for efficient rank aggregation. In Proceedings of the 33rd International Conference on Machine Learning, pp.\ 89--98, 2016

    2016

  51. [60]

    M., Li, Y., Wang, H., U, L

    Kou, N. M., Li, Y., Wang, H., U, L. H., and Gong, Z. Crowdsourced top-k queries by confidence-aware pairwise judgments. In Proceedings of the 2017 ACM International Conference on Management of Data, pp.\ 1415--1430, Chicago, IL, USA, 2017

    2017

  52. [61]

    and Szepesv \'a ri, C

    Lattimore, T. and Szepesv \'a ri, C. Bandit Algorithms. Cambridge University Press, 2020

    2020

  53. [62]

    Active learning for top- k rank aggregation from noisy comparisons

    Mohajer, S., Suh, C., and Elmahdy, A. Active learning for top- k rank aggregation from noisy comparisons. In Proceedings of the 34th International Conference on Machine Learning, pp.\ 2488--2497, 2017

    2017

  54. [63]

    G., and Chen, T

    Narimanzadeh, H., Badie-Modiri, A., Smirnova, I. G., and Chen, T. H. Y. Crowdsourcing subjective annotations using pairwise comparisons reduces bias and error compared to the majority-vote method. Proceedings of the ACM on Human-Computer Interaction, 7 0 (CSCW2): 0 1--29, 2023

    2023

  55. [64]

    Rank centrality: Ranking from pairwise comparisons

    Negahban, S., Oh, S., and Shah, D. Rank centrality: Ranking from pairwise comparisons. Operations Research, 65 0 (1): 0 266--287, 2017

    2017

  56. [65]

    Ren, W., Liu, J., and Shroff, N. B. PAC ranking from pairwise and listwise queries: Lower bounds and upper bounds. arXiv preprint arXiv:1806.02970, 2018

    2018 arXiv

  57. [66]

    Ren, W., Liu, J., and Shroff, N. B. The sample complexity of best- k items selection from pairwise comparisons. In Proceedings of the 37th International Conference on Machine Learning, pp.\ 8051--8072, 2020

    2020

  58. [67]

    and Gopalan, A

    Saha, A. and Gopalan, A. PAC battling bandits in the plackett-luce model. In Proceedings of the 30th International Conference on Algorithmic Learning Theory, pp.\ 700--737, 2019

    2019

  59. [68]

    and Gopalan, A

    Saha, A. and Gopalan, A. From PAC to instance-optimal sample complexity in the plackett-luce model. In Proceedings of the 37th International Conference on Machine Learning, pp.\ 8367--8376, 2020

    2020

  60. [69]

    B., Balakrishnan, S., Guntuboyina, A., and Wainwright, M

    Shah, N. B., Balakrishnan, S., Guntuboyina, A., and Wainwright, M. J. Stochastically transitive models for pairwise comparisons: Statistical and computational issues. IEEE Transactions on Information Theory, 63 0 (2): 0 934--959, 2017

    2017

  61. [70]

    Online learning and online convex optimization

    Shalev-Shwartz, S. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4 0 (2): 0 107--194, 2012

    2012

  62. [71]

    Fast pure exploration via frank-wolfe

    Wang, P.-A., Tzeng, R.-C., and Prouti \`e re, A. Fast pure exploration via frank-wolfe. In Advances in Neural Information Processing Systems 34, pp.\ 5810--5821, 2021

    2021

  63. [72]

    Dueling bandits with qualitative feedback

    Xu, L., Honda, J., and Sugiyama, M. Dueling bandits with qualitative feedback. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, pp.\ 5549--5556, 2019

    2019

Pith tools

Reviewed July 13, 2026 · model on record in the stance chip above.