NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:5291
Title:On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons

The paper considers a setting where one can actively query for pairwise comparisons (there is also an extension to listwise comparisons) and where the goal is to find the total ranking of the items. This is an important problem, in an area of significant interest to the NeurIPS community. The results are strong enough to recommend acceptance. However, there are also a number of misleading statements made in the paper that were flagged in the review process. It is very important that the authors fix these in the camera ready submission. (1) The abstract says "while most of the previous works either require prior knowledge or focus on approximate rankings". Due to this and other artifacts of writing of the paper, a reviewer incorrectly believed from reading this paper that "Active ranking under few assumptions is an important question, and previous works only solves this under the PAC setting" (as mentioned in the reviewer's initial review). The reviewer only later realized that [15] and others address exact ranking. (2) There was also confusion about the misleading statement "that Borda-Score algorithms are not suitable for exact ranking". The review team disagrees with such as statement as the assumptions in Borda-Score algorithms [15, 16, 21, 29] and this submission are simply incomparable. (3) The author's rebuttal stated that " If it is not true, the meaning of “more preferred” becomes vague and we may not have enough information to recover the ranking." That is incorrect as shown in the Borda-Score papers. (4) The paper considers the weak stochastic transitivity model in A3 for pairwise comparisons, and we suggest making a connection to this model to help the reader who are familiar with the literature (see arxiv 1510.05610 for an overview of different stochastically transitive models; also a good related read regarding these models is arxiv 1605.03933). The authors should carefully rewrite parts of the paper to remove all unclear and misleading statements that are discussed above and in the initial reviews.