Papers › Active Learning for Top-K Rank Aggregation from Noisy Comparisons
Active Learning for Top-K Rank Aggregation from Noisy Comparisons
Soheil Mohajer, Changho Suh, Adel Elmahdy
We explore an active top-K ranking problem based on pairwise comparisons that are collected possibly in a sequential manner as per our design choice. We consider two settings: (1) top-K sorting in which the goal is to recover the top-K items in order out of n items; (2) top-K partitioning where only the set of top-K items is desired. Under a fairly general model which subsumes as special cases various models (e.g., Strong Stochastic Transitivity model, BTL model and uniform noise model), we characterize upper bounds on the sample size required for top-K sorting as well as for top-K partitioning. As a consequence, we demonstrate that active ranking can offer significant multiplicative gains in sample complexity over passive ranking. Depending on the underlying stochastic noise model, such gain varies from around logn/loglogn to (n² logn)/loglogn. We also present an algorithm that is applicable to both settings.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections