Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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. 

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. 

Technical 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.

Overall, I do not think that this paper satisfies the expectations from a theory paper at NeurIPS.

limitations_and_societal_impact: Broader impact section is not present.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
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:

i) 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?

ii) 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?

In general, I think the results are good but more discussion can make the paper better.
limitations_and_societal_impact: The paper is mostly theoretical.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.  
 
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.

I do not have any important comments or suggestion except the following:

For 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. 

It would be great if you could discuss/mention in the conclusion open and challenging questions, future directions, etc., that follow from your work.
limitations_and_societal_impact: Yes.
review_title: null

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)