Optimal Sample Complexity of M -wise Data for Top-K Ranking
We explore the top-K rank aggregation problem in which one aims to recover a consistent ordering that focuses on top-K ranked items based on partially revealed preference information. We examine an M -wise comparison model that builds on the Plackett-Luce (PL) model where for each sample, M items are ranked according to their perceived utilities modeled as noisy observations of their underlying true utilities. As our result, we characterize the minimax optimality on the sample size for top-K ranking. The optimal sample size turns out to be inversely proportional to M . We devise an algorithm that effectively converts M -wise samples into pairwise ones and employs a spectral method using the refined data. In demonstrating its optimality, we develop a novel technique for deriving tight ∞ estimation error bounds, which is key to accurately analyzing the performance of top-K ranking algorithms, but has been challenging. Recent work relied on an additional maximum-likelihood estimation (MLE) stage merged with a spectral method to attain good estimates in ∞ error to achieve the limit for the pairwise model. In contrast, although it is valid in slightly restricted regimes, our result demonstrates a spectral method alone to be sufficient for the general M -wise model. We run numerical experiments using synthetic data and confirm that the optimal sample size decreases at the rate of 1/M . Moreover, running our algorithm on real-world data, we find that its applicability extends to settings that may not fit the PL model.
Summary:
    The authors consider the problem of optimal top-K rank aggregation from many samples each containing M-wise comparisons. The setup is as follows: There are n items and each has a hidden utility w_i such that w_i >= w_{i+1}. w_K-w_{K+1} has a large separation Delta_K. The task is to identify the top K items. There is a series of samples that are given. Each samples is a preference ordering among M items out of the n chosen. Given the M items in the sample, the preference ordering follows the PL model. Now there is a random hyper graph where each set of M vertices is connected independently with probability p. Further, every hyperedge gives L M-wise i.i.d preference order where M items come from the hyperedge.
  
     The authors show that under some density criterion on p, the necessary and sufficient number of samples nis  O( n log n/M Delta_K^2 ) . The notable point is that it is inversely proportional to M.
     The algorithm has two parts: For every M-wise ordered sample, one creates M pariwise orderings that respect the M-wise ordering such that these pairwise orderings are not correlated. This is called sample breaking. Then the problem uses standard algorithmic techniques like Rank Centrality that use the generated pairwise ordered samples to actually generate a top K ranking.
    The proofs involve justifying the sample breaking step and new analysis is needed to prove the sample complexity results.
 Strengths:
  a) For the dense hypergraph case, the work provides sample optimal strategy for aggregation which is the strength of the paper.
  b) Analyzing rank centrality along with path breaking seems to require a strong l_infinity bound on the entries of the stationary distribution of a Markov Chain whose transition matrix entries have been estimated upto to some additive error. Previous works have provided only l_2 error bounds. This key step helps them separate the top K items from the rest due to the separation assumed.
I did not have the time to go through the whole appendix. However I only quickly checked the proof of Theorem 3 which seems to be quite crucial. It seems to be correct. 
Weaknesses:
      a) Spectral MLE could be used once sample breaking is employed and new pairwise ordered samples generated. Why has that not been compared with the proposed approach for the experiments in section 4.2 ? Infact that could have been compared even for synthetic experiments in Section 4.1 for M > 2 ?
      b) The current method's density requirements are not optimal (at least w.r.t the case for M=2). I was wondering if experimentally, sample breaking + some other algorithmic approach can be shown to be better ?