Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons
Authors: Wenbo Ren
Jia Liu
Ness Shroff
Venue: NeurIPS 2021 Poster (2021)
Keywords: Ranking from Comparisons
Active Learning
Sample Complexity
Duelling Bandits

Abstract: We study the sample complexity (i.e., the number of comparisons needed) bounds for actively ranking a set of $n$ items from multi-wise comparisons. Here, a multi-wise comparison takes $m$ items as input and returns a (noisy) result about the best item (the winner feedback) or the order of these items (the full-ranking feedback). We consider two basic ranking problems: top-$k$ items selection and full ranking. Unlike previous works that study ranking from multi-wise comparisons, in this paper, we do not require any parametric model or assumption and work on the fundamental setting where each comparison returns the correct result with probability $1$ or a certain probability larger than $\frac{1}{2}$. This paper helps understand whether and to what degree utilizing multi-wise comparisons can reduce the sample complexity for the ranking problems compared to ranking from pairwise comparisons. Specifically, under the winner feedback setting, one can reduce the sample complexity for top-$k$ selection up to an $m$ factor and that for full ranking up to a $\log{m}$ factor. Under the full-ranking feedback setting, one can reduce the sample complexity for top-$k$ selection up to an $m$ factor and that for full ranking up to an $m\log{m}$ factor. We also conduct numerical simulations to confirm our theoretical results. 

Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons
Wenbo Ren
Jia Liu
Dept. Computer Science & Engineering The Ohio State University
Dept. Electrical & Computer Engineering The Ohio State University
ren 453@osu.edu
liu. 17 17360osu. edu
Ness B. Shroff
Dept. Electrical & Computer Engincering and Computer Science Engineering The Ohio State University shroff. 110osu...cco edu
Abstract
We study the sample complexity (i.e., the number of comparisons needed) bounds for actively ranking set of items from multi-wise comparisons. Here, multi- wise comparison takes m items as input and returns a (noisy) result about the best item (the winner feedback) or the order of these items (the full-ranking feedback). We consider two basic ranking problems: top-k items selection and full ranking. Unlike previous works that study ranking from multi-wise comparisons, in this paper, we do not require any parametric model or assumption and work on the fun- damental setting where each comparison returns the correct result with probability or certain probability larger than This paper helps understand whether and to what degree utilizing multi-wise comparisons can reduce the sample complexity for the ranking problems compared to ranking from pairwise comparisons. Specifically, under the winner feedback setting, one can reduce the sample complexity for top-k selection up to an m factor and that for full ranking to a log m factor. Under the full-ranking feedback setting, one can reduce the sample complexity for top-k selection up to an m factor and that for full ranking up to an m log m factor. We also conduct numerical simulations confirm our theoretical results.
1 Introduction
Background and motivation
Ranking from comparisons is class of fundamental problems that underpin many areas in machine learning, and has found various applications in problems involving crowd-soureing, social choices, recommendation, and searching. In such ranking problems, there is a hidden ranking among multiple items to be recovered, where items may refer to candidates, products, movies, advertisements, etc. In this paper, we study ranking from multi-wise comparisons. A multi-wise comparison refers to query on m items about the most preferred one (the winner feedback) or the full ranking (the full-ranking feedback) of these items. These comparisons may be deterministic they may return incorrect results). The noise comes from the uncertain nature of humans, the lack of information, the underlying physics. In this paper, focus two goals. One is to find the top-k items (ranking or ordering these items are not necessary), and the other is to find the full ranking.
non-determiiistic (i.c., noisy
Our focus is on active ranking (e.g., I0 17.19) where "active" means that after each compari- son, the learner can adaptively choose the next items to be compared according to past observations
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

and comparison results. Active ranking can be viewed as active learning for ranking problems and the comparisons refer to the samples. The opposite of active ranking is passive ranking. where the learner first obtains a set of comparison results and then recovers a ranking from there. Active ranking can greatly reduce the sample complexity in many scenarios, e.g., if all comparisons return correct results with probability 3. passively ranking n items needs (2(n)) comparisons 3 while active ranking only needs (n log n comparisons [9 18].
Most existing works have focused on ranking from pairwise comparisons. In contrast, we focus on ranking from multi-wise (or m-wise) comparisons. The pairwise comparisons can be viewed as multi-wise comparisons with m = 2. One motivation is that in many scenarios, multi-wise comparisons are more common. For instance, in video streaming websites or e-shopping apps, customers or users are normally presented more than two options, and the choices made by users can be viewed as multi-wise comparisons that suggest their preferences over these options. Studying ranking from multi-wise comparisons is useful for these types of applications. Besides, ranking from multi-wise comparisons may also reduce the cost of the learning process. In some applications, conducting the comparisons may be expensive. For instance, to find the candidates that are most preferred by the voters. people may need to do a series of surveys. Each survey contains query about the preference order of a voter. In this application, the cost of finding the voter and asking this voter to fill the survey could far outweigh the cost of filling the survey itself. This means that the cost of conducting a multi-wise comparison is almost the same as that for a pairwise comparison, and how to reduce the number of samples by multi-wise comparisons becomes more interesting. Thus, it is not only interesting but also significant to study whether and to what degree we can reduce the sample complexity for ranking by using multi-wise comparisons.
We focus on a non-parametric model, where each comparison returns the correct result with a certain probability q >> 2/2 and arbitrary incorrect result otherwise. When q = 1, the comparisons are deterministic and always return correct results, and when g < 1, we say the comparisons are non- deterministic or noisy. This differs from parametric models" that assume that each item holds a value representing the users' preference on this item. In parametric models, the comparisons may provide more information than the setting in this pape and thus, the conclusion drawn under parametric models cannot be directly applied to this paper.
1.2 Problem formulation
Assume that there are n items, indexed by 1, 3,2,,...7 that form the item set |n We further assume that these items have a unique unknown true ranking T1 > r2 > ... >- Tn, where for any items i and j. notation i >> j means that item i ranks higher (or is more preferred) than item j. Assume that we can compare at most m items a time. The comparisons can be either deterministic or -enedmteriiiistic. We also assume that the comparisons are independent across time, items, and sets, which is standard in the literature (e.g.. 7 10 IT 13 22). Here, we note that the independence based on the assumption that the hidden parameters and ranking are some fixed values.
When the comparisons are deterministic, the comparisons always return the correct results, i.e., the best item under the winner feedback model or the true ranking of the compared items under the full-ranking feedback model. In the deterministic case, our goal is to find the exact top-k items or the true ranking.
When the comparisons non-deterministic, assume that they return the correct results with a certain fixed probability 9 E 12. In this case, it is infeasible to rank the items with 100% confidence, and thus, our goal is to find the ranking with confidence 1 - 8 for some ó E (0, f). We focus on the case where = We note that this does not lose much generality. When
the
All log in this paper are natural log unless explicitly noted. For instance, parametric models can be the Bradley-Terry-Luce (BTL) model 2 the Plackett-Luce (PL.) model [T3), or the multinomial logit (MNL) model [4].
'For instance, given three items j. k with i heing the best and k heing the worst, in the setting of this paper with g = 0.7, the multi- comparison returns the best item i with probability 0.7, and return j or k with some unknown probabilities, which does not provides information about the orders of and k. In contrast, in a parametric model, the comparison over {i.j. k} would return i, j. or with probability 0.7, 0.2, and 0.1, respectively, which not only provides information about the best one but also information for ordering j and k. For any positive integer we define [[] := (1, 3,... l).

---

algorithms and sample complexity bounds in this paper can be directly applied. When < 3. we can use repeated comparisons to simulate one comparison with correct probability at least 3.2 To this, consider set over which comparison returns the correct result with probability 1/2 + 2 By comparing this for 1 log 37 times, the item or permutation that occurs most often is the correct result with probability at least 3 (by Hoeffding Inequality). Thus, we can use the above method to substitute the comparisons in the algorithms designed for the case where g = while only introducing an additional I factor on the sample complexity.
This (2 + A) m-wise comparison model can also be justified in many scenarios that use an iterative subroutine to conduct m-wise comparisons over a set in a smaller time-scale. Here, we give simple example. We use Pi. to denote the probability that item wins the comparison performed on set S (assuming |S| I m) and we use i" to denote the best item of S. If Pe , 2 Pi. + A for any item i + i and any set SS, then by repeatedly comparing S for O ( log (S() times, one can find the best item of with confidence 3. We can use the above procedure as a subroutine in each iteration of our algorithms, and get the algorithms for this case while only introducing an additional log m factor to the sample complexities. In more general cases, we can use similar tricks but the additional factors may vary.
1.3
Main results
The main results of this paper are summarized in Table We note that due space limitation, all proofs in this paper are left to the supplementary material.
Table 1:
Main results of this paper. All results are established in this paper unless explicitly cited. For results of -etermiimiii feedback, ö is the error probability and assume that all comparisons return correct results with probability 5.
Problem
Top-k Selection
Full Ranking
Winner Feedback Model
Deterministic Feedback
( 12
+ k)
pogg O log m
m
Non-Deterministic Feedback
O(( m m
k) log
& llogm
(n log )
22k + 22 log $)
Full-Ranking Feedback Model
Deterministic Feedback
θ
log m log m
m
Non-Deterministic Feedback
0 log
min nn m. log
n 0 log
m
8
m3
Q log,
N log 1
m
2
Related works
When m = 2 and the comparisons are deterministic, the top-k selection problem becomes the classical pairwise k-selection problem, which requires (()) comparisons [0] and the full ranking problem becomes the classical pairwise sorting problem, which requires O(n v1) comparisons. Thus, ranking from multi-wise comparisons can also be viewed extensions of these foundational problems. Surprisingly, these extensions have not been well understood.
For top-k selection from non-deterministic pairwise comparisons, the authors of 9 showed that On ( comparisons are necessary and sufficient to reach confidence level - 8. For probably approximately correct (PAC top-k selection with error tolerance > 0, the authors of 5 7 proved
10(% log 1)) bound for k- 1, and the authors of [16] 18 proved a O log {) bound for k < 3-
For full ranking from non-deterministic pairwise comparisons, early work proved that when the comparisons of all pairs have the same noise level, then to get the full ranking with confidence 1 6, (n log 4) comparisons are necessary and sufficient. The authors of [17
19) whose authors
'The PAC setting means that we want to find the ranking approximately with an error tolerance and a confidence 1 - 6. where the tolerance means that for any two items i and j. item is viewed to rank higher than item if item i wins the comparisons over item with probability 1 or higher.
3

---

extend the above results to the case where the comparisons on different pairs have different noise levels, and also obtained the (n log }) bounds. The authors of 7 showed the @ 2 log ) order-wise tight upper and lower bounds for PAC full ranking with error tolerance > 0.
Thus, we can see that for established optimal sample complexity bounds for top-k selection and full ranking. However, the corresponding multi-wise ranking problems have been relatively under-explored. Most of these works have focused on parametric models such as the PL model and the MNL model. Under the MNL model, the work in 4 showed that under certain cases, one can get an m-reduction from m-wise comparisons over ranking from pairwise comparisons. However, for most cases, using m-wise comparisons does not reduce the sample complexity (gnoring constant factors). For multi-wise full ranking under the MNL model, the works in [T6] [7] showed that the lower bound is the same as that using pairwise comparisons, i.e., there is no reduction by using m-wise comparisons. Under the list-wise PL. model with certain types of feedback, we may achieve up to m-reduction in the sample complexity according to [9.
(i.e., ranking from pairwise comparisons), people have already
In contrast to the above works, we do not assume any parametric model, and instead use a non- parametric model where each comparison returns a correct result with a certain fixed probability g. As noted in Section T.I] the results drawn from the parametric models cannot be directly applied to this non non-parametric model. Multi-wiss ranking under this non-parametric setting is even less under-explored in the literature. The most related work to this paper is [7], where the authors showed m bound for full ranking from the winner feedback, which solves one of the eight cases (top-k selection or full ranking, winner feedback or full-ranking feedback, deterministic feedback or non-deterministic feedback) that studied in this paper and shown Table [ We will study the rest seven cases in this paper.
O( n lag
3 Top-k selection from winner feedback
3.1 Deterministic feedback
Lower bound. We first state an 12 nn bound reduces to (m)), the same as that for the pairwise k-selection problem.
n + k)) lower bound in Theorem I When m 2, this lower
Theorem 1. To find the top-k items from items by m-wise deterministic winner feedback, any algorithm needs to conduct at least 22 n + k) comparisons.
Upper bound When m = 2. the problem reduces to the basic pairwise k-selection problem, which requires (n) comparisons. One algorithm solve the pairwise k-selection problem is Quick-Select (QS) 12 With n items, QS randomly chooses a pivot, splits other items into two piles based on whether them are larger or smaller than the pivot, and then recursively calls QS on one of these two piles according to the piles' sizes. The expected number of comparisons required by QS is (n) (in the worst case will be On))).
However, if we want to get the O m + k) sample complexity upper bound for multi-wise top-k selection that matches the lower bound stated in Theorem T we cannot split the items into two piles because splitting (n - 1) items into two piles requires (() comparisons. Instead, we split them into piles that are formed by (m - 1) randomly chosen pivots. Also, if the algorithm splits all the non-pivot items, then we still have 2(n) sample complexity, which is sub-optimal. Our key idea is to stop splitting if we have identified the elements of the first several piles and the number of items in these piles along with the corresponding pivots is no less than k. By analyzing how the items will be split, we will show that we only need to conduct O(21 22 + k) comparisons in expectation before terminating splitting. After the splitting, we only need to focus on the pile that contains the k-th item as the piles that rank higher contain only items better than the k-th item and the others contain only items worse then the k-th item. We can show that this pile is of size (( ) in expectation, and thus, m comparisons by QS. Therefore, we find the top-k
m
finding the top-k items from it only takes O " items by using O n + k) comparisons in expectation.
We name the above method as Multi-wise Quick-Select (MQSelect) and describe it in Algorithm The theoretical performance of MQSelect is formally stated in Theorem
Theorem 2. MQSelect returns the top-k items of S after O 2 + comparisons in expectation.

---

Algorithm Multi-wise Quick-Select(S, m, (MQSelect)
1: if [S| S then
2: Compare S for k times; After each comparison remove the winner from S and add it to Ans;
3: return Ans;
4: end if
5: Randomly choose m items and form a pivot set V:
6: R1 < < -V; R2, R3, ... Rm + 0; Do < 0: A t 0 for i E Im 1];
7: for = =,,,,,8,, 3....... ...,. m 1 do
8: Compare V once and denote the winner as Vz;
9:
V '+vV V {w+ E - 0: while R2 * 0 do
10:
Choose items from R2 and add them E until F] reaches min(m 1, [R]B: Compare U } and denote the winner
12:
13:
if = 2/ then
14:
R&+1 < Ru+1 + E; R4 R E; E + 0:
15:
else
16:
At A (w); R4 t Rs {w) E E - (w);
17:
end
18:
end while
19:
D. < D,-1 U A, (wr):
20:
if [Dl = h then
21:
return D2;
else if [Dr] k then
23:
return Dr - {
24:
else if [De] > k + then
25:
return D Qui - (D--1l):
end if
27:
end for
return D Quick-Select( Rm,; k 1 1mm-1))
According the lower bound stated in Theorem [ MQSelect is optimal up to a constant factor. When m = 2, the O a + k) bound reduces to (nn), the same as that for pairwise k-selection.
3.2 Non-deterministic feedback
Lower bound. The lower bound for m-wise top-k selection from non-deterministic winner feedback stated in Proposition 3 Later Theorem 5 will show that this bound optimal up log log factor, and when
this bound is optimal up to a log log m factor.
Proposition There is an n-sized instance such that to find the top-k items with confidence 1 by using m-wise non-deteriinistic winner feedback, any algorithm needs at least Ω + log comparisons in expectation.
Upper bound. We first introduce simple subroutine Basic Compare (BC) in Algorithm
Given
Algorithm 2 Basic Compare () (BC).
1: Compare S for N, [18 log 11 times;
2: return the result that is returned for the most number of times;
and input set S, BC compares S for No [18 log 1 times and returns the most often result, which correct with probability at least - 8. This can shown by using Hoeffding inequality
P(X < No/2] < exp(-2N.(2/3 1/2) S 6,
where X is the number of times that the correct result returned.
We now present a relatively simple algorithm called Basic k-Selection (BKS), which will be used later for developing another algorithm. The idea of BKS is that we replace the misiie comparisons in
5

---

In fact, we use BKS MQSelect by the calls of BC with a certain confidence 1 - 81. Intuitively, we can set 61 = 5 BKS return the correct result with confidence
na to make 5 as MQSelect conducts most n² comparisons. comparison. However, by showing that with probability at least 1 - op. MQSelect conducts at most N = (kk + ) log
In this case, we will need O + ) log 8)
mk log m
comparisons, we can set nuk log mn
51 6g and dg N
and get better upper bound O(( + k) log
with 61 2 then the algorithm we construct in the later subsection will have worse upper bound.
We describe BKS in Algorithm 3 Its theoretical performance formally stated in Lemma
Algorithm 3 Basic k-Select(S, m, 8) (BKS).
1: 6n T
m- log 2(m 1)(m-2) 61 6k+67 if m 2: 81
6a if m 2: [S]
6n
2: Run MQSelect on M, but using calls of BC with confidence 61 to replace multi-wise
comparisons (except those in the call of QS);
3: For the call of QS, we replace the pairwise comparisons with calls of BC with confidence
Lemma 4. BKS terminates after O + k) log nklogg comparisons in expectation, and with probability least - 8, returns the top-k items of S.
With BKS, we develop an enhanced algorithm for multi-wise top-k selection that can remove the log n factor in the sample complexity of BKS, At each round I, we split the remaining items into subsets with sizes most mk. For each set, we use BKS with confidence items and call them winners. We can show that with probability at least - og the winners of all subsets together contain the top-k items of [n]. We keep the winners and remove other items. Repeat the above step on remaining items for multiple rounds until only h: winners remain, and these winners the top-k items of [n] with probability at least
* find the top-k
> 8r. By setting proper values of S, we can find the top-k items with confidence 1 - by using O(( ((2 + kog
Is loog m comparisons. We name this algorithm Multi-wiss wise Toumnment k-Select (MTKS) and describe it in Algorithm 4 Its theoretical performance is formally stated in Theorem
Algorithm 4 Multi-wise Tournament k-Select (S, m, k, 8) (MTKS)
1: if [S| S. mk then
2: return (KS(S, m, k,);
3: end if
4: Set f < 0 and R1 S;
5: repeat
6:
1- 1; 0
68
7: Distribute R₁ to mi
Rel
disjoint sets A1, A2, .... Ag. each with size at most mk;
8: For E [d] let B, BBBKKAA m, k, 6x)
9: Re41 + Uleld B;:
10: until |Re+1| < k
11:
return Re41;
Theorem S. MTKS terminates after O1 k) log probability at least 8, returns the top-k items of S.
& &log m) comparisons in expectation, and with
We can see that, by using multi-wise comparisons, MTKS can achieve up to m--reduction in the sample complexity. According to Proposition when & < a our upper bound optimal up to log log factor, which is almost constant for most of the practical cases.
m

---

Full ranking from winner feedback
4.1 Deterministic feedback
This setting has been studied in 17.. where the authors have shown O log n) upper and lower
bounds for the sample complexity. We restate their results in Proposition By using m-wise comparisons, can reduce the sample complexity for finding the full ranking by log m factor.
Proposition 6 (177). To exactly rank items by using m-wise deterministic comparisons under the winner feedbaakk model, (n logm n) comparisons are necessary and sufficient.
4.2 Non-deterministic feedback
Unlike full ranking from deterministic comparisons, when the comparisons are non-deterministic, this logarithmic reduction may not exist any more. This result is stated in Theorem
Theorem 7. There is an n-sized instance such that to get the full ranking with confidence - 5 from m-wise winner feedback, any algorithm needs at least 12(n log ğ comparisons.
For 2, i.e. when using pairwise comparisons, the algorithms in 18 can already find the full ranking of items with confidence 1 - by On log 3 comparisons, matching the lower bound in Theorem 7 Thus, do not propose algorithm for >> 2 and one directly use the pairwise algorithms for m >> and obtain optimal sample complexity (ignoring constant factors).
5 Top-k selection from full-ranking feedback
5.1 Deterministic feedback
For the lower bound, since each comparison involves at most m items and all items need to be involved in at least one comparison to get the top-k items, we immediately have the D m)) lower bound. For the upper bound, we develop a Quick-Select-like algorithm MQSelect-FRF (Multi- wise Quick-Select from Full-Ranking Feedback) under the full-ranking feedback model similar to MQSelect. In the splitting, MQSelect-FRF takes less comparisons since the full-ranking feedback provides more information than the winner feedback, which removes the ((k) term in the upper bound that exists in the sample complexity of MQSelect. Due to space limitation, we only state the bounds in Theorem g and the proofs and algorithms are relegated to the supplementary material.
Theorem 8. To get the top-k items of n items from deterministic m-wise full- feedback, O (1) comparisons are necessary and sufficient.
5.2 Non-deterministic feedback
Lower bound. In this part, provide lower bound in Proposition 9 which is optimal up to log m - log log m factor. This lower bound is proved by reducing the pairwise ranking problem to the list-wise ranking problem. In fact, are not aware whether there is stronger lower bound, and this problem requires future investigation.
Proposition 9. There is an n-sized instance such that to find the top-k items by m-wise non- deterministic full-ranking feedback, any algorithm needs Di log, 5) comparisons.
Upper bound. We develop the full-ranking algorithm following the similar steps as in MTKS. First, we develop an algorithm named BKS-FRF (BKS from Full-Ranking Feedback) similar to BKS, which algorithm by a call of BC with a certain n llggm ). When & < we further use similar steps me
replaces the comparisons of the deterministic-compaan
confidence and has sample complexity O 2 log as MTKS and develop an algorithm named MTKS-FRF (MTKS from Full-Ranking Feedback)
that further reduces the sample complexity to O log log m log log m factor. Due to space limitation, we only state the upper bound in Theorem 10 and the algorithms are presented in the supplementary material.
min(n/mm.e) log m.) which is optimal up to
Theorem 10. MTKS-FRF terminates after O R log min(n/m.K)) log comparisons in expectation,
and with probability at least 8, returns the top-k items of
7

---

Full ranking from full-Ranking feedback
6.1 Deterministic feedback
Lower bound. We first show the lower bound for this setting in Theorem [1] an information-theorede approach. Specifically, there are n. permutations, which implies that the information entropy of the true ranking is log(n!). Each m-wise comparison has at most m!! possible results. Thus, each m-wise comparisons provides at most log(m!) information towards the true ranking. By Fano's 's Inequality [8] to get the true ranking with probability at least 3 the information about the true ranking
The proof is based on
needs to obtain is at least ([llggnn))). Since log(n!) 4. O log n) and
(m)) (m log m), the lower bound is least 92 Theorem 11. To get the full ranking of n items by using m-wise comparisons under the full-ranking feedback model, any algorithm needs least {2( n log
m log plogg
log comparisons in expectation.
Algorithm 5 Multi-wise Quick-Sort(S,n) m) (MQSort)
1: if [||] I then
2: Compare S, obtain its full ranking and return;
3: end if
4: Randomly choose h :== [ items and form pivot set V;
5: Compare V to get its full ranking i1 U2 > Uh:
6: Let do represent a dummy item that ranks higher than all other items;
7: R + S V; A, f 0 for O, 1, h:
8: while R + 0 do
9: Choose (m h) items from R and form set E;
10: Compare set E U V and get the ranking;
for item in E do
12: Add item i to set Aj if items in V ranks higher than i (i.e., if ey-1 > i x Uy);
end for end while
14:
for j 3,, do
16: Call MQSort(A, j,, m)) to get the full ranking of Ay;
17: Insert the sorted items of A, into between U/-1 and By;
18:
end for
19:
return the current ranking of S;
Upper bound. Since it is well-known that full ranking from pairwise comparisons needs Onn log n) comparisons, developing full ranking algorithm under the non-deterministic full-ranking feedback model with sample complexity O log is trivial by viewing an m-wise comparison as Im pairwise comparisons. Instead, propose an algorithm called Multi-wise Quick-Sort (MQSort) n log logm: better than the above trivial bound and matches the lower bound stated in Theorem [I MQSort can be viewed an extension of the classical Quick-Sort algorithm, but requires more complicated mathematical analysis to prove its sample complexity. We describe MQSort Algorithm 5
with expected sample complexity O
and formally state its theoretical performance in Theorem 12
Theorem 12. MQSort terminates after O( log nt log m) m--wie comparisons in expectation and returns
the full ranking of S.
6.2 Non-deterministic feedback
Lower bound. When the full ranking is obtained, then the top- items also be obtained for free.
Thus, we immediately have the 9 log... +) full-ranking lower bound in Corollary 13 by invoking Proposition 9 Corollary 13 is optimal up to log m factor. Whether tighter bound exists remains an open problem and requires further investigation.
Corollary 13. There is an n-sized instance such that to find the fill ranking from m-wise fill-ranking feedback with confidence 6, any algorithm needs R2 log.. z) comparisons expectation.
Next, we modify the algorithm [9] achieve an O a log =h upper bound, which stated in Theorem 14 Due to space limitation, we leave the algorithm to the supplementary material.
8

---

10
10
109
MTRS
MIKS =
num comparsono
109
10
num of comparisons
-0a-
8KS =0
10"
204
10
MOSelect
MOSelectk +0
5Q m
MQSelecck #00
10
MG m 100 MGSelect
MOSelectk:
100
207
100
300
100
m
(a) MQSelect, vary m.
(b) MQSelect, vary k.
(c) MTKS and BKS, vary m.
10
10"
109
num comparbore
pum comperisore
30-
10
:02
20a
MC55ortm
MTKS m
30*
Mo =5
BK3 m #
MoSortm =10
MTKS 10
Sort =
M05ort
20
1000
(d) MTKS and BKS, vary k.
(e) MQSort and MMS, vary m..
(1) MQSort, vary r.
Figure 1: Performance comparisons all algorithms: In all figures, 1000 (except (f)), 8 0.01 (if applicable), and all points are averaged over 100 independent trials with random true rankings.
There is an algorithm that finds the full ranking of n items by m-wise full-ranking feedback with confidence ö and conducts O n. log mb) comparisons in expectation.
Theorem 14.
Numerical results
In this section, we conduct numerical experiments verify out theoretical results. The codes can be found in our GitHub repo
In Figure T (a.b), we present the results of MQSelect. In Figure (a),
1000 and
== [1, 10, 100, 500}, and vary the value of m. In Figure (b), we set n = 1000 and m = 10, 100, 500), and vary the value of k. First, from the results, can that that given the same value of k, the number of comparisons conducted by MQS decreases as m increases, and the decreasing rate is approximately 1 according to Figure 1 (a)) consistent with our theory that the Ta
sample complexity of MQSelect is ( 2 + k). This indicates that using multi-wise comparisons can significantly reduce the required number value of m. Second, Figure (b) shows that for given value of m. when & increases, the number of comparisons conducted by MQSelect increases nearly linearly. The larger the m-values, the closer to linear the increasing rates are, which is also consistent with the theory.
comparisons for top-k ranking, especially for large
In Figure (c.d), we compare the performance of MTKS and BKS. In Figure 5 = 0.01, and A = {1, 10), and vary the value of m. In Figure [ (d), we set n = 1000, 5 = 0.01, and m = (2, 10). and vary the value of k. First, we can see from ( that when m increases, the number of comparisons conducted by MTKS and BKS both decrease, and the decreasing rate larger for smaller values of which consistent with the theory that the sample complexities of both algorithms depend on ( + k). This also indicates that by using multi-wise comparisons. we can save significant number of comparisons for top-k selection. Second, from Figure (c), we
set 1000,
https://gihhbbcco/WWwooo..... wit.eee//MMMiiiiiseeiesaaaiiiiee Raee-Rannnggiii

---

can see that, when k = 1, MTKS uses less comparisons than BKS for almost all values of m, which is consistent with the theory that the sample complexity of MTKS depends on log *log "h smaller than the log mogog rate of BKS. However, from Figure 1 (c), we can also see that, when & is larger, má
e.g.. k = 10, the performance of BKS is slightly better than that of MTKS, which indicates that MTKS has a larger constant factor. Third, according Figure[[dd) when & increases, the number of comparisons conducted by both algorithms tend to increase except for small set of points. When m I, the increasing rate of the number of conducted comparisons with & is smaller than that when m = 10, which is consistent with the theory that the sample complexities of both algorithms depend on ( 2 in k). Thus, when m is larger, the complexity of the algorithms are more sensitive with
In Tigure[(eeD) we present the numerical results of MQSort. To show how the full-ranking feedback can help reduce the sample complexity for finding the full ranking, we compare MQSort with Multi- wise Merge Sort (MMS) algorithm proposed in [17), which uses the winner feedback. In theory, to rank n items, MQSort uses ( i log xi
Tog comparisons. In (2, 10, 50, 100} and vary the value of n. First, from Figure (c.f). we can see that when m increases, the number of comparisons conducted by MQSort decreases, and the decreasing rate is nearly log which
Iog.n comparisons and MMS uses O na log
Figure (e), set 1000 and vary the value of m. In Figure (f), we set
is consistent with the theory that the sample complexity of MQSort is Ol n mlogg that by using multi-wise full-ranking feedback with large values of m, can significantly reduce the sample complexity for finding the full ranking. Second, we can also see that MQSort uses less comparisons than MMS for 2 5, and the decreasing rate of the complexity is also faster than MMS, consistent with the theory that MQSort has sample complexity O n log log ) and MMS has
log m This indicates
sample complexity O( 0("1gg ") ). This suggests that compared to winner feedback, using full-ranking feedback is more efficient in terms of sample complexity for finding the full ranking.
8 Conclusion
This paper studied the problems of selecting the top-k items or finding the full ranking of a of items by using m--ise comparisons under the winner feedback model or the full-ranking feedback model. The comparisons can be either deterministic or non-deterministic. For all eight combinations of settings (top-k selection or full ranking, winner feedback or full-ranking feedback, deterministic or non non-deterministic feedback), we proposed algorithms, derived upper bounds, and/or proved lower bounds. For four settings, we obtained tight upper and lower bounds (up to constant factors). For three settings, we obtained upper and lower bounds where there only logarithmic gaps between them. The results in this paper showed that by using multi-wise comparisons, one could dramatically reduce the number of comparisons needed for the ranking problems compared to ranking from pairwise comparisons. The numerical results presented also confirmed our theoretical predictions.
Acknowledgments and Disclosure of Funding
This work has been supported in part by NSF grants CAREER CNS-2110259, 2NS-2112471, CNS-2102233, CNS-2112471, CNS-2106932, CNS-1955535, CCF-2110252, ECCS-2140277, IIS- 2112471, and Google Faculty Research Award.
References
[1] Blum, M., Floyd, R. W., Pratt, V. R., Rivest, R. L., and Tarjan, R. E. (1973). Time bounds for selection. J. Comput. Syst. Sci., 7(4):448-44 461.
[2] Bradley, R. A. and Terry, M. F. (1952). Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 394344):324-455
[3] Braverman, M., Mao, J.. and Peres, Y. (2019). Sorted top-k in rounds. In Conference on Learning Theory, pages 342-382. PMLR.
[4] Chen, X., Li, Y., and Mao, J. (2018). A nearly instance optimal algorithm for top-k ranking under the multinomial logit model. In Annual ACM-SIAM Symposium on Algorithms, pages 2504-2522 SIAM.
10

---

[5] Falahatgar, M., Hao, Y., Orlitsky, A., Pichapati, V., and Ravindrakumar, V. (2017a). Maxing and ranking with few assumptions. Advances Neural Information Processing Systems, pages 7060-7070.
[6] Falahatgar, M., Jain, A., Orlitsky, A., Pichapati, V., and Ravindrakumar, V. (2018). The limits maxing, ranking, and preference learning. In International Conference on Machine Learning, pages 1427-1436. PMLR.
[7] Falahatgar, M., Orlitsky, A., Pichapati, V., and Suresh, A. T. (2017b). Maximum selection and ranking under noisy comparisons. In International Conference on Machine Learning, pages 1088-1096. JMLR. org.
[8] Fano, R. M. (1961). Transmission of information. Bell System technical journal.
[9] Feige, U., Raghavan, P., Peleg, D., and Upfal, E. (1994). Computing with noisy information. SIAM Journal on Computing, 23(5):1001-1018
[10] Heckel, R., Shah, N. B., Ramchandran, K., Wainwright, M. J., al. (2019). Active ranking from pairwise comparisons and when parametric assumptions do not help. The Annals of Statistics, 47(6):3099-3126,
[11] Heckel, R., Simchowitz, M., Ramchandran, K., and Wainwright, M. (2018). Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics, pages 1057-1066.
[12] Hoare, C. A. (1961). Algorithm 65: find. Communications of the ACM, 4(7):321-322.
[13] Katariya, S., Jain, I.,, Sengupta, N., Evans, J., and Nowak, R. (2018). Adaptive sampling for coarse ranking. In International Conference on Artificial Intelligence and Statistics, pages 1839-1848.
[14] McFadden, D. (1973). Conditional logit analysis qualitative choice behavior.
[15] Plackett, R. L. (1975). The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), 2432).193-20.
[16] Ren, W., Liu, and Shroff, N. B. (2018). PAC ranking from pairwise and listwise queries: 02970.
Lower bounds and upper bounds. arXiv preprint
[17] Ren, W. Liu, J., and Shroff, N. B. (2019). On sample complexity upper and lower bounds for exact ranking from noisy comparisons. Advances in Neural Information Processing Systems, pages 10014-10024.
[18] Ren, W. Liu, J., and Shroff, N. B. (2020). The sample complexity of best-k items selection from pairwise comparisons. In International Conference on Machine Learning, pages 8051-8072. PMLR.
[19] Saha, A. and Gopalan, A. (2019a). Active ranking with subset-wise preferences. In International Conference on Artificial Intelligence and Statistics, pages 3312-3321.
[20] Saha, A. and Gopalan, A. (2019b). From PAC to instance-optimal sample complexity in the Plackett- Luce model. arXiv preprint 19Xx009903000588
[21] Shah, N. B. and Wainwright, M. J. (2017). Simple, robust and optimal ranking from pairwise comparisons. The Journal of Machine Learning Research, 18(1):7446-283.
[22] Szörényi. B., Busa-Fekete, R., Paul, A., and Hüllermeier, E. (2015), Online rank clicitation for Plackett-Luce: dueling bandits approach. In Advances in Neural Processing Systems, pages 604-612.
11


Reviews:
[{"review_id": "s630BiJVmW", "reviewer": "Reviewer_Qykc", "summary": "This paper considers the problem of ranking from multi-wise comparisons where the goal is either to find the set of top-k items or to find a complete ranking over the items. The paper considers a model for multi-wise comparisons where the feedback is either-- (1) deterministic where the correct result is returned; or (2) probabilistic where the feedback is correct with probability larger than 1/2. The paper assumes that there is an underlying ordering over items and considers two models of feedback-- (1) winner feedback where the best item in a set is returned; (2) full-ranking feedback where a complete ordering over arms is returned. The paper proposes lower and upper bounds on sample complexity for each of these 8 problem settings and outlines the reduction in sample complexity due to the use of multi-wise comparisons. \n", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Modeling Assumption: The probabilistic model for multi-wise comparisons proposed in this paper does not seem motivated by practical applications. As the value of m increases, it seems unrealistic to assume that the best arm (or correct answer) will be returned with a probability of 1/2 + \\Delta. One should expect the best arm to have win probability much less than 1/2 for larger values of m. Furthermore, the proposed model differs significantly from other well-studied models such as MNL/Random Utility Models as win probability of the best arm here is a function of the other arms in the set. It is not clear why this model is interesting to study. Since the reduction in sample complexity due to m can be dependent on the underlying model, it is not clear how these results generalise to more realistic problem settings. \n\nTechnical Novelty: Most of the results in this paper are simple extensions of existing results from theoretical computer science for both the deterministic and probabilistic settings. The idea to use multi-way pivoting in the Quick Select/Sort algorithm is a natural extension of the usual two-way pivoting. There are other classic algorithms that can be similarly extended to this setting, for example, one can construct m-way heaps and perform Heap Select/Sort over these m-way heaps by using m-wise winner feedback. The probabilistic setting is also based on existing/similar ideas except that one needs to perform the comparisons with high confidence over a sufficiently small instance (for example, see Feige et al., 1994). Finally, the lower bounds also do not require any new ideas.\n\nOverall, I do not think that this paper satisfies the expectations from a theory paper at NeurIPS.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Broader impact section is not present. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "l8QWvgyEJOr", "reviewer": "Reviewer_hWKg", "summary": "The paper systematically analyzes the sample complexity of top-k selection and ranking under active multi-wise comparisons. It studies the winner model and full ranking model of multi-wise comparison, both deterministic and with 2/3 correct probability. The algorithms are mainly based on an extension of either QuickSelection or QuickSort.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper contains comprehensive results about various cases of active ranking. While the results look good and are quite complete, I feel that they can still be improved in several ways:\n\ni) What are the implications of the results? More discussion will be helpful to understand the results. Generally, it seems like m-way comparison can help by a $O(\\log m)$, $O(m)$ or $O(m \\log m)$ factor. Why can it be different?\n\nii) What techniques are involved? Previous methods also use QuickSelect or QuickSort to solve ranking but under different assumptions. Are the algorithms presented related to previous algorithms?\n\nIn general, I think the results are good but more discussion can make the paper better.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper is mostly theoretical.", "review_text": "", "extra_scores": {"ethical_concerns": "The paper is mostly theoretical.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "kjmIrm8iLAk", "reviewer": "Reviewer_7QRR", "summary": "This paper studies the problem of active ranking from ($m$) multi-wise comparisons. The focus on past literature was on pairwise comparisons $m=2$. For this problem the authors considered both  top-$k$ items selection and full ranking. For both problems the authors provide theoretical guarantees (lower and upper bounds) on the sample complexity, i.e., the number of comparison. Furthermore, contrary to previous related works, the current model is not parametric and quite general.  \n ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written, interesting, and motivated. The introduction is comprehensive, and the model is clear. I read all the proofs and everything seems okay -- some proofs are quite standard and straightforward. The algorithms are also reasonable, some of which are motivated by the special case of pairwise comparisons. To me, this paper is a nice contribution, and therefore I recommend accepting the paper.\n\nI do not have any important comments or suggestion except the following:\n\nFor the non-deterministic setting (or, noisy) it is assumed that one can repeat the same comparisons; simple averaging then allows one to \"get rid\" of the noise, at the price of an additional logarithmic factor due to repetition. The underlying main assumption here is, however, that the comparison responses statistically independent and identical. I suspect that this assumption is quite strong, and in practice, the responses will be quite dependent if not the same. For example, in crowdsourcing platforms there is no reason to believe that humans over these platforms will provide independent responses. Therefore, in my opinion the non-deterministic is less motivated. The remedy for this might be: 1) to assume some kind of dependency over the repeated responses, 2) limit the number of allowed repetitions, 3) consider a model where repetitions is not allowed at all. For the last two cases, some kind of structure must be induced for the problem to be feasible. \n\nIt would be great if you could discuss/mention in the conclusion open and challenging questions, future directions, etc., that follow from your work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"ethical_concerns": "No.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper considers the problem of ranking from multi-wise comparisons where the goal is either to find the set of top-k items or to find a complete ranking over the items. The paper considers a model for multi-wise comparisons where the feedback is either-- (1) deterministic where the correct result is returned; or (2) probabilistic where the feedback is correct with probability larger than 1/2. The paper assumes that there is an underlying ordering over items and considers two models of feedback-- (1) winner feedback where the best item in a set is returned; (2) full-ranking feedback where a complete ordering over arms is returned. The paper proposes lower and upper bounds on sample complexity for each of these 8 problem settings and outlines the reduction in sample complexity due to the use of multi-wise comparisons. There is a near consensus amongst reviewer that this is a "border-line" work.
Decision: Accept (Poster)