Minimax-optimal Inference from Partial Rankings
This paper studies the problem of rank aggregation under the Plackett-Luce model. The goal is to infer a global ranking and related scores of the items, based on partial rankings provided by multiple users over multiple subsets of items. A question of particular interest is how to optimally assign items to users for ranking and how many item assignments are needed to achieve a target estimation error. Without any assumptions on how the items are assigned to users, we derive an oracle lower bound and the Cramér-Rao lower bound of the estimation error. We prove an upper bound on the estimation error achieved by the maximum likelihood estimator, and show that both the upper bound and the Cramér-Rao lower bound inversely depend on the spectral gap of the Laplacian of an appropriately defined comparison graph. Since random comparison graphs are known to have large spectral gaps, this suggests the use of random assignments when we have the control. Precisely, the matching oracle lower bound and the upper bound on the estimation error imply that the maximum likelihood estimator together with a random assignment is minimax-optimal up to a logarithmic factor. We further analyze a popular rankbreaking scheme that decompose partial rankings into pairwise comparisons. We show that even if one applies the mismatched maximum likelihood estimator that assumes independence (on pairwise comparisons that are now dependent due to rank-breaking), minimax optimal performance is still achieved up to a logarithmic factor.
This work studies the use of the Plackett-Luce model on the problem of rank aggregation with partial feedbacks. It mainly consists in a theoretical study of the estimation error depending on the quantity of feedbacks that are given by the users and depending on the assignments of the items to the users. The authors provide first two lower bounds on the estimation error  of the PL model – one for any estimator, the other (tighter) only for unbiased estimators. Then, the authors present three different upper bounds, depending on the how the feedback is observed (partial ranking or pairwise preferences), with two schemes for the observations of the pairs.I liked the technical quality of this theoretical analysis (even if I didn’t checked the proof deeply) for several reasons:-	The results proved are really non-trivial,-	the authors paid attention to enlarge the scope of their results when they could – e.g. the first lower bound holds for a larger family of models than PL,-	the authors only narrowed the scope to obtain tighter bound and actually provided some insights to compare their different bounds.-	The discussion is not restricted on the pure performance of the estimation w.r.t. the quantity of feedback, but also with the way the feedback are assigned (even if I’m not familiar with this setting).Beyond these aspects, truth should be said, the major drawback of this paper concerns itsform. The writing and the structure (1 and ½ page of notations and definitions at the beginning) all contribute to make it extremely difficult to read.