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

Reviewer 1

The paper is not well written. The ideas are not clearly presented. The paper adapts the previous algorithm to extend it from PAC to instance optimal guarantees which has been previously studied for maximum but not ranking. The paper proved the results theoretically and provided experiments evaluating their algorithm with previous works. The paper also doesn't mention the precise applications where this method will be more useful compared to that of PAC one. Post Rebuttal : I am happy with Author's feedback

Reviewer 2

The paper is of high quality and is well written. It is fairly dense in the number of results and contains strong empirical results to support their theory which makes a good paper for NeurIPS in my humble opinion. I did not fully check the proofs but they seem sound. I am also not very familiar with the ranking literature so my next questions are mostly to help me better understand the results and will guide me to adjust my score. * How realistic is to assume that comparisons are independent across items, sets and time? Is this a widely used assumption in the ranking community? From a layman point of view, this may seem a strong assumption as it is not the same as assuming the typical iid sampling, no? If the assumption, as stated, is required to have a well defined problem, then the question translates to whether or not aiming for exact ranking in general is realistic. * I am not fully clear about the notation in line 49. Why is p_{i, j} disregarding "j" and defined as p_{i, S}? This was a bit confusing to me as later we see \Delta_{i, j} but it is not clear to me the role of j in this case. * It seems that the focus is in having a small number of comparisons. However, what is the computational complexity for m-wise comparison in contrast to pairwise? And, how realistic is the worst case scenario? Where it is claimed that the number of m-wise comparisons is of the same order as number of pairwise comparisons. On a minor note: the shorthand MNL in line 76 is not introduced properly.

Reviewer 3

Originality: The paper solves a previously unsolved problem and the methods seem novel. Quality: The paper is technically sound. I still have some questions: 1. What is the purpose of Section 3.1? Since section 3.2 provides a lower bound for MNL model and MNL is a special case of SST, isn't eqn (2) immediately follows from Theorem 3? Theorem 2 is better in eqn(1), but in what case can it be larger than (2)? 2. Why do the 3 plots in Figure 2 have different number of baselines? Significance: Active ranking under few assumptions is an important question, and previous works only solves this under the PAC setting. I think the results are significant. Clarity: Some small typos: 1. It would be good to clarify the implications of the assumptions on line 50-58: for pairwise comparisons, this just means p_{ij}>1/2 for i>j. 2. Line 87: the square is probably inside the parenthesis?