Sample Complexity Bounds for Active Ranking from Multi-wise Comparisons
Year: 2022

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 multiwise 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 12 . 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 logm 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 logm factor. We also conduct numerical simulations to confirm our theoretical results.

heading: 1 Introduction

heading: 1.1 Background and motivation
text: Ranking from comparisons is a class of fundamental problems that underpin many areas in machine learning, and has found various applications in problems involving crowd-sourcing, 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 a 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 or non-deterministic (i.e., noisy or they may return incorrect results). The noise comes from the uncertain nature of humans, the lack of information, or the underlying physics. In this paper, we focus on 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.
Our focus is on active ranking (e.g., [4–7, 10, 17–19]), where “active” means that after each comparison, the learner can adaptively choose the next items to be compared according to past observations
35th Conference on Neural Information Processing Systems (NeurIPS 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 23 , passively ranking n items needs Ω(n
2) comparisons [3], while active ranking only needs O(n log n)1 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 a 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 > 12 and an arbitrary incorrect result otherwise. When q = 1, the comparisons are deterministic and always return correct results, and when q < 1, we say the comparisons are nondeterministic or noisy. This differs from parametric models2 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 paper3, and thus, the conclusion drawn under parametric models cannot be directly applied to this paper.

heading: 1.2 Problem formulation
text: Assume that there are n items, indexed by 1, 2, 3, ...n, that form the item set [n]4. We further assume that these items have a unique unknown true ranking r1 ≻ r2 ≻ · · · ≻ rn, 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 at a time. The comparisons can be either deterministic or non-deterministic. We also assume that the comparisons are independent across time, items, and sets, which is standard in the literature (e.g., [5–7, 10, 11, 13, 17–22]). Here, we note that the independence is 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 are non-deterministic, we assume that they return the correct results with a certain fixed probability q ∈ ( 12 , 1). 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− δ for some δ ∈ (0, 12 ). We focus on the case where q = 23 . We note that this does not lose much generality. When q > 2 3 , the
1All log in this paper are natural log unless explicitly noted. 2For instance, parametric models can be the Bradley-Terry-Luce (BTL) model [2], the Plackett-Luce (PL) model [15], or the multinomial logit (MNL) model [14]. 3For instance, given three items i, j, k with i being the best and k being the worst, in the setting of this paper with q = 0.7, the multi-wise 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 j and k. In contrast, in a parametric model, the comparison over {i, j, k} would return i, j, or k 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.
4For any positive integer l, we define [l] := {1, 2, 3, ..., l}.
algorithms and sample complexity bounds in this paper can be directly applied. When q < 23 , we can use repeated comparisons to simulate one comparison with correct probability at least 23 . To see this, consider a set over which a comparison returns the correct result with probability 12 +∆ > 1 2 . By comparing this set for ⌈ 12∆2 log 3⌉ times, the item or permutation that occurs most often is the correct result with probability at least 23 (by Hoeffding Inequality). Thus, we can use the above method to substitute the comparisons in the algorithms designed for the case where q = 23 while only introducing an additional 1∆2 factor on the sample complexity.
This ( 12 +∆) 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 a simple example. We use pi,S to denote the probability that item i wins the comparison performed on set S (assuming |S| ≤ m) and we use i∗ to denote the best item of S. If pi∗,S ≥ pi,S +∆ for any item i ̸= i∗ and any set S, then by repeatedly comparing S for Θ( 1∆2 log |S|) times, one can find the best item of S with confidence 23 . 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 logm factor to the sample complexities. In more general cases, we can use similar tricks but the additional factors may vary.

heading: 1.3 Main results
text: The main results of this paper are summarized in Table 1. We note that due to space limitation, all proofs in this paper are left to the supplementary material.

heading: 2 Related works
text: When m = 2 and the comparisons are deterministic, the top-k selection problem becomes the classical pairwise k-selection problem, which requires Θ(n) comparisons [1], and the full ranking problem becomes the classical pairwise sorting problem, which requires Θ(n log n) comparisons. Thus, ranking from multi-wise comparisons can also be viewed as 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 Θ(n log kδ ) comparisons are necessary and sufficient to reach confidence level 1− δ. For probably approximately correct (PAC)5 top-k selection with error tolerance ϵ > 0, the authors of [5, 7] proved a Θ( nϵ2 log 1 δ ) bound for k = 1, and the authors of [16, 18] proved a Θ( n ϵ2 log k δ ) bound for k ≤ n 2 .
For full ranking from non-deterministic pairwise comparisons, an early work was [9], whose authors proved that when the comparisons of all pairs have the same noise level, then to get the full ranking with confidence 1 − δ, Θ(n log nδ ) comparisons are necessary and sufficient. The authors of [17]
5The PAC setting means that we want to find the ranking approximately with an error tolerance ϵ and a confidence 1− δ, where the ϵ tolerance means that for any two items i and j, item i is viewed to rank higher than item j if item i wins the comparisons over item j with probability 1
2 − ϵ or higher.
extend the above results to the case where the comparisons on different pairs have different noise levels, and also obtained the Θ(n log nδ ) bounds. The authors of [5–7] showed the Θ( n ϵ2 log n δ ) order-wise tight upper and lower bounds for PAC full ranking with error tolerance ϵ > 0.
Thus, we can see that for m = 2 (i.e., ranking from pairwise comparisons), people have already 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 (ignoring constant factors). For multi-wise full ranking under the MNL model, the works in [16, 17] 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 [19].
In contrast to the above works, we do not assume any parametric model, and instead use a nonparametric model where each comparison returns a correct result with a certain fixed probability q. As noted in Section 1.1, the results drawn from the parametric models cannot be directly applied to this non-parametric model. Multi-wise ranking under this non-parametric setting is even less under-explored in the literature. The most related work to this paper is [17], where the authors showed a Θ(n lognlogm ) 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 is studied in this paper and shown in Table 1. We will study the rest seven cases in this paper.
3 Top-k selection from winner feedback

heading: 3.1 Deterministic feedback
text: Lower bound. We first state an Ω( nm + k) lower bound in Theorem 1. When m = 2, this lower bound reduces to Ω(n), the same as that for the pairwise k-selection problem.
Theorem 1. To find the top-k items from n items by m-wise deterministic winner feedback, any algorithm needs to conduct at least Ω( nm + k) comparisons.
Upper bound When m = 2, the problem reduces to the basic pairwise k-selection problem, which requires Θ(n) comparisons. One algorithm to 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 O(n) (in the worst case it will be O(n2)).
However, if we want to get the O( nm + k) sample complexity upper bound for multi-wise top-k selection that matches the lower bound stated in Theorem 1, we cannot split the items into two piles because splitting (n − 1) items into two piles requires Ω(n) comparisons. Instead, we split them into m piles that are formed by (m− 1) randomly chosen pivots. Also, if the algorithm splits all the non-pivot items, then we still have Ω(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( nm + 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 O( nm ) in expectation, and thus, finding the top-k items from it only takes O( nm ) comparisons by QS. Therefore, we find the top-k items by using O( nm + k) comparisons in expectation.
We name the above method as Multi-wise Quick-Select (MQSelect) and describe it in Algorithm 1. The theoretical performance of MQSelect is formally stated in Theorem 2.
Theorem 2. MQSelect returns the top-k items of S after O( nm + k) comparisons in expectation.
Algorithm 1 Multi-wise Quick-Select(S,m, k) (MQSelect).
1: if |S| ≤ m 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− 1 items and form a pivot set V ; 6: R1 ← S − V ; R2, R3, ..., Rm ← ∅; D0 ← ∅; Ai ← ∅ for i ∈ [m− 1]; 7: for t = 1, 2, 3, ...,m− 1 do 8: Compare V once and denote the winner as vt; 9: V ← V − {vt}; E ← ∅;
10: while Rt ̸= ∅ do 11: Choose items from Rt and add them to E until |E| reaches min{m− 1, |Rt|}; 12: Compare E ∪ {vt} and denote the winner as w; 13: if w = vt then 14: Rt+1 ← Rt+1 + E; Rt ← Rt − E; E ← ∅; 15: else 16: At ← At + {w}; Rt ← Rt − {w}; E ← E − {w}; 17: end if 18: end while 19: Dt ← Dt−1 ∪At ∪ {vt}; 20: if |Dt| = k then 21: return Dt; 22: else if |Dt| = k + 1 then 23: return Dt − {vt}; 24: else if |Dt| > k + 1 then 25: return Dt−1∪ Quick-Select(At, k − |Dt−1|); 26: end if 27: end for 28: return Dm−1∪ Quick-Select(Rm, k − |Dm−1|);
According to the lower bound stated in Theorem 1, MQSelect is optimal up to a constant factor. When m = 2, the Θ( nm + k) bound reduces to Θ(n), the same as that for pairwise k-selection.

heading: 3.2 Non-deterministic feedback
text: Lower bound. The lower bound for m-wise top-k selection from non-deterministic winner feedback is stated in Proposition 3. Later Theorem 5 will show that this bound is optimal up to a log k logmδ factor, and when k ≤ nm , this bound is optimal up to a log logm factor. Proposition 3. There is an n-sized instance such that to find the top-k items with confidence 1− δ by using m-wise non-deterministic winner feedback, any algorithm needs at least Ω(k + nm log k δ ) comparisons in expectation.
Upper bound. We first introduce a simple subroutine Basic Compare (BC) in Algorithm 2. Given δ
Algorithm 2 Basic Compare(S, δ) (BC).
1: Compare S for N0 = ⌈18 log 1δ ⌉ times; 2: return the result that is returned for the most number of times;
and input set S, BC compares S for N0 = ⌈18 log 1δ ⌉ times and returns the most often result, which is correct with probability at least 1− δ. This can be shown by using Hoeffding inequality
P{X ≤ N0/2} ≤ exp{−2N0(2/3− 1/2)2} ≤ δ, (1)
where X is the number of times that the correct result is 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 m-wise comparisons in
MQSelect by the calls of BC with a certain confidence 1−δ1. Intuitively, we can set δ1 = δn2 to make BKS return the correct result with confidence 1− δ as MQSelect conducts at most n2 comparisons. In this case, we will need O((k + nm ) log n δ ) comparison. However, by showing that with probability at least 1− δ0, MQSelect conducts at most N = O((k + nm ) log nk logm mδ0 ) comparisons, we can set δ1 = δ0 N and δ0 = δ 3 and get a better upper bound O(( n m + k) log nk logm mδ ). In fact, if we use BKS with δ1 = δn2 , then the algorithm we construct in the later subsection will have a worse upper bound. We describe BKS in Algorithm 3. Its theoretical performance is formally stated in Lemma 4.
Algorithm 3 Basic k-Select(S,m, k, δ) (BKS).
1: δ0 ← δ3 ; T1 ← 1 + n m−2 log 2(m−1)(m−2) δ0 ; δ1 ← δ06k+5T1 if m > 2; δ1 ← δ0 |S|2 if m = 2; 2: Run MQSelect on M , but using calls of BC with confidence 1 − δ1 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 1− δ0|At|2 ;
Lemma 4. BKS terminates after O(( nm + k) log nk logm mδ ) comparisons in expectation, and with probability at least 1− δ, 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 t, we split the remaining items into subsets with sizes at most mk. For each set, we use BKS with confidence 1− δtk to find the top-k items and call them winners. We can show that with probability at least 1 − δt, 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 k winners remain, and these k winners are the top-k items of [n] with probability at least 1− ∑∞ t=1 δt. By setting proper values of δt, we can find the top-k items with confidence 1− δ by using O(( nm + k) log k logm
δ ) comparisons. We name this algorithm Multi-wise Tournament k-Select (MTKS) and describe it in Algorithm 4. Its theoretical performance is formally stated in Theorem 5.
Algorithm 4 Multi-wise Tournament k-Select (S,m, k, δ) (MTKS)
1: if |S| ≤ mk then 2: return BKS(S,m, k, δ); 3: end if 4: Set t← 0 and R1 ← S; 5: repeat 6: t← t+ 1; δt ← 6δπ2t2 ; 7: Distribute Rt to ⌈ |Rt|mk ⌉ disjoint sets A1, A2, ..., Ad, each with size at most mk; 8: For i ∈ [d], let Bi ←BKS(Ai,m, k, δtk ); 9: Rt+1 ← ⋃ i∈[d] Bi;
10: until |Rt+1| ≤ k 11: return Rt+1;
Theorem 5. MTKS terminates after O(( nm + k) log k logm δ ) comparisons in expectation, and with probability at least 1− δ, returns the top-k items of S.
We can see that, by using multi-wise comparisons, MTKS can achieve up to an m-reduction in the sample complexity. According to Proposition 3, when k ≤ nm , our upper bound is optimal up to a log logm factor, which is almost constant for most of the practical cases.

heading: 4 Full ranking from winner feedback

heading: 4.1 Deterministic feedback
text: This setting has been studied in [17], where the authors have shown Θ(n logm n) upper and lower bounds for the sample complexity. We restate their results in Proposition 6. By using m-wise comparisons, we can reduce the sample complexity for finding the full ranking by a logm factor.
Proposition 6 ([17]). To exactly rank n items by using m-wise deterministic comparisons under the winner feedback model, Θ(n logm n) comparisons are necessary and sufficient.

heading: 4.2 Non-deterministic feedback
text: 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 7.
Theorem 7. There is an n-sized instance such that to get the full ranking with confidence 1− δ from m-wise winner feedback, any algorithm needs at least Ω(n log nδ ) comparisons.
For m = 2, i.e., when using pairwise comparisons, the algorithms in [18] can already find the full ranking of n items with confidence 1− δ by O(n log nδ ) comparisons, matching the lower bound in Theorem 7. Thus, we do not propose an algorithm for m > 2 and one can directly use the pairwise algorithms for m > 2 and obtain optimal sample complexity (ignoring constant factors).
5 Top-k selection from full-ranking feedback

heading: 5.1 Deterministic feedback
text: 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 Ω( nm ) lower bound. For the upper bound, we develop a Quick-Select-like algorithm MQSelect-FRF (Multiwise 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 O(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 8 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-ranking feedback, Θ( nm ) comparisons are necessary and sufficient.

heading: 5.2 Non-deterministic feedback
text: Lower bound. In this part, we provide a lower bound in Proposition 9, which is optimal up to a logm · log logm factor. This lower bound is proved by reducing the pairwise ranking problem to the list-wise ranking problem. In fact, we are not aware whether there is a 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 nondeterministic full-ranking feedback, any algorithm needs Ω( nm logm k δ ) 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 replaces the comparisons of the deterministic-comparison algorithm by a call of BC with a certain confidence and has sample complexity O( nm log n logm mδ ). When k < n m , we further use similar steps as in MTKS and develop an algorithm named MTKS-FRF (MTKS from Full-Ranking Feedback) that further reduces the sample complexity to O( nm log min{n/m,k} logm δ ), which is optimal up to a logm · log logm factor. Due to space limitation, we only state the upper bound in Theorem 10 and the algorithms are presented in the supplementary material.
Theorem 10. MTKS-FRF terminates after O( nm log min{n/m,k} logm
δ ) comparisons in expectation, and with probability at least 1− δ, returns the top-k items of S.

heading: 6 Full ranking from full-Ranking feedback

heading: 6.1 Deterministic feedback
text: Lower bound. We first show the lower bound for this setting in Theorem 11. The proof is based on an information-theoretic 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 Inequality [8], to get the true ranking with probability at least 34 , the information about the true ranking one needs to obtain is at least Ω(log(n!)). Since log(n!) = Θ(n log n) and log(m!) = Θ(m logm), the lower bound is at least Ω( n lognm logm ). Theorem 11. To get the full ranking of n items by using m-wise comparisons under the full-ranking feedback model, any algorithm needs at least Ω( n lognm logm ) comparisons in expectation.
Algorithm 5 Multi-wise Quick-Sort(S,m) (MQSort)
1: if |S| ≤ m then 2: Compare S, obtain its full ranking and return; 3: end if 4: Randomly choose h := ⌊m2 ⌋ items and form pivot set V ; 5: Compare V to get its full ranking v1 ≻ v2 ≻ · · · ≻ vh; 6: Let v0 represent a dummy item that ranks higher than all other items; 7: R← S − V ; Ai ← ∅ for i = 0, 1, 2, ..., h; 8: while R ̸= ∅ do 9: Choose (m− h) items from R and form set E;
10: Compare set E ∪ V and get the ranking; 11: for item i in E do 12: Add item i to set Aj if j items in V ranks higher than i (i.e., if vj−1 ≻ i ≻ vj); 13: end for 14: end while 15: for j = 0, 2, 3, ..., h do 16: Call MQSort(Aj ,m) to get the full ranking of Aj ; 17: Insert the sorted items of Aj into between vj−1 and vj ; 18: end for 19: return the current ranking of S;
Upper bound. Since it is well-known that full ranking from pairwise comparisons needs O(n log n) comparisons, developing a full ranking algorithm under the non-deterministic full-ranking feedback model with sample complexity O( nm log n) is trivial by viewing an m-wise comparison as ⌊ m 2 ⌋ pairwise comparisons. Instead, we propose an algorithm called Multi-wise Quick-Sort (MQSort) with expected sample complexity O( n lognm logm ), better than the above trivial bound and matches the lower bound stated in Theorem 11. MQSort can be viewed as an extension of the classical Quick-Sort algorithm, but requires more complicated mathematical analysis to prove its sample complexity. We describe MQSort in Algorithm 5 and formally state its theoretical performance in Theorem 12. Theorem 12. MQSort terminates after O( n lognm logm ) m-wise comparisons in expectation and returns the full ranking of S.

heading: 6.2 Non-deterministic feedback
text: Lower bound. When the full ranking is obtained, then the top-n2 items can also be obtained for free. Thus, we immediately have the Ω( nm logm n δ ) full-ranking lower bound in Corollary 13 by invoking Proposition 9. Corollary 13 is optimal up to a logm factor. Whether a tighter bound exists remains an open problem and requires further investigation. Corollary 13. There is an n-sized instance such that to find the full ranking from m-wise full-ranking feedback with confidence 1− δ, any algorithm needs Ω( nm logm n δ ) comparisons in expectation.
Next, we modify the algorithm in [9] to achieve an O( nm log n mδ ) upper bound, which is stated in Theorem 14. Due to space limitation, we leave the algorithm to the supplementary material.
Theorem 14. There is an algorithm that finds the full ranking of n items by m-wise full-ranking feedback with confidence 1− δ and conducts O( nm log n mδ ) comparisons in expectation.

heading: 7 Numerical results
text: In this section, we conduct numerical experiments to verify out theoretical results. The codes can be found in our GitHub repo.6
In Figure 1 (a,b), we present the results of MQSelect. In Figure 1 (a), we set n = 1000 and k = {1, 10, 100, 500}, and vary the value of m. In Figure 1 (b), we set n = 1000 and m = {2, 10, 100, 500}, and vary the value of k. First, from the results, we can see 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 1m according to Figure 1 (a), consistent with our theory that the sample complexity of MQSelect is O( nm + k). This indicates that using multi-wise comparisons can significantly reduce the required number of comparisons for top-k ranking, especially for a large value of m. Second, Figure 1 (b) shows that for a given value of m, when k 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.
In Figure 1 (c,d), we compare the performance of MTKS and BKS. In Figure 1 (c), we set n = 1000, δ = 0.01, and k = {1, 10}, and vary the value of m. In Figure 1 (d), we set n = 1000, δ = 0.01, and m = {2, 10}, and vary the value of k. First, we can see from Figure 1 (c) that when m increases, the number of comparisons conducted by MTKS and BKS both decrease, and the decreasing rate is larger for smaller values of k, which is consistent with the theory that the sample complexities of both algorithms depend on ( nm + k). This also indicates that by using multi-wise comparisons, we can save a significant number of comparisons for top-k selection. Second, from Figure 1 (c), we
6https://github.com/WenboRen/Multi-wise-Ranking.git
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 k logmδ , smaller than the log nk logmmδ rate of BKS. However, from Figure 1 (c), we can also see that, when k is larger, 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 to Figure 1 (d), when k increases, the number of comparisons conducted by both algorithms tend to increase except for a small set of points. When m = 1, the increasing rate of the number of conducted comparisons with k is smaller than that when m = 10, which is consistent with the theory that the sample complexities of both algorithms depend on ( nm + k). Thus, when m is larger, the complexity of the algorithms are more sensitive with k.
In Figure 1 (e,f), 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 Multiwise Merge Sort (MMS) algorithm proposed in [17], which uses the winner feedback. In theory, to rank n items, MQSort uses O( n lognm logm ) comparisons and MMS uses O( n logn logm ) comparisons. In Figure 1 (e), we set n = 1000 and vary the value of m. In Figure 1 (f), we set m = {2, 5, 10, 50, 100} and vary the value of n. First, from Figure 1 (e,f), we can see that when m increases, the number of comparisons conducted by MQSort decreases, and the decreasing rate is nearly 1m logm , which is consistent with the theory that the sample complexity of MQSort is O( n lognm logm ). This indicates that by using multi-wise full-ranking feedback with large values of m, we can significantly reduce the sample complexity for finding the full ranking. Second, we can also see that MQSort uses less comparisons than MMS for m ≥ 5, and the decreasing rate of the complexity is also faster than MMS, consistent with the theory that MQSort has sample complexity O( n lognm logm ) and MMS has sample complexity O(n lognlogm ). This suggests that compared to winner feedback, using full-ranking feedback is more efficient in terms of sample complexity for finding the full ranking.

heading: 8 Conclusion
text: This paper studied the problems of selecting the top-k items or finding the full ranking of a set of n items by using m-wise 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-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 is 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, CNS-2112471, CNS-2102233, CNS-2112471, CNS-2106932, CNS-1955535, CCF-2110252, ECCS-2140277, IIS2112471, and a Google Faculty Research Award.

Review summaries:
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.  

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.    

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.