Computational and Statistical Tradeoffs in Learning to Rank
For massive and heterogeneous modern data sets, it is of fundamental interest to provide guarantees on the accuracy of estimation when computational resources are limited. In the application of learning to rank, we provide a hierarchy of rankbreaking mechanisms ordered by the complexity in thus generated sketch of the data. This allows the number of data points collected to be gracefully traded off against computational resources available, while guaranteeing the desired level of accuracy. Theoretical guarantees on the proposed generalized rank-breaking implicitly provide such trade-offs, which can be explicitly characterized under certain canonical scenarios on the structure of the data.
This paper considers the problem of rank aggregation. Given ordinal data about users’ preferences, the goal is to aggregate them in the form of partially ordered sets (a poset). Assuming the revealed preference is consistent, the poset can be represented as a directed acyclic graph.  The authors propose a “generalized rank-breaking” algorithm, which is a unified framework which spans from the maximum likelihood estimator to pairwise rank-breaking. The MLE is consistent, but can be intractable and impractical. A common remedy is to use pairwise rank-breaking, which treats all pairwise comparisons as independent. However, this might lead to a statistically inconsistent estimator due to the ignored correlations.  The proposed algorithm broadly does the following: Step 1) For each user j \in [n], extract a maximal ordered partition P_j of S_j which is consistent with her preference G_j;  Step 2) Represent the extracted ordered partition by a directed hypergraph G_j(S_j, E_j) with e = (B(e), T(e)) \in E_j being a directed hyperedge;  Step 3) Compute the probability of B(e) < T(e) in terms of parameters \theta_i (latent true utility);  Step 4) Maximize the log-likelihood composed of the terms only with |T(e)| \leq M under the independent assumption.   The authors show that finding an order-M rank-breaking estimate is a concave maximization with high probability, and that the estimate is consistent for sufficiently large M under the Plackett-Luce model.   The main result of the paper suggests a high-probability upper bound on the achieved error of the estimate. This upper bound is optimal up to a logarithmic factor with respect to the Cramer-Rao bound when (a) the topology of the data is well-behaved (quantities defined on line 206 are finite), and (b) there is no limit on the computational power and M \to \infty. 
Overall, the paper is well-organized: the process for generalized rank-breaking is clearly explained and the analysis provides an upper bound on the achieved error. It is also shown that this upper bound is nearly optimal under certain conditions, and the computational-statistical trade-off is also glimpsed. However, there are many parameters/quantities involved in the analysis so that sometimes it becomes not easy to follow and appreciate the authors’ arguments. I would like to suggest having an easy-to-find notation paragraph which readers can refer to, while reading.  Also, there are several questions with regard to the contents of the paper: - Line 52:   Can this generalized rank-breaking be applied beyond the Plackett-Luce model? - Line 98 – 99:  I do not understand why none of the pairwise orderings can be used from G_j in the example. - Line 206:  Does $\gamma_3$ also have an intuitive interpretation like $\gamma_1$ and $\gamma_2$? Also, is there any special reason you use $\nu$, not $\gamma_4$ to define the last quantity? Isn’t that related to the topology of the data? - Lines 244 – 251:  I am a little bit confused. Lines 244 – 247 implies the upper bound is tight with respect to the lower bound when the topology of the data is well-behaved. However, Lines 248 – 251 seem to mean the opposite: Eq (13) gives a tighter lower bound when the topology is not well-behaved. Could you please clarify what I am misunderstanding for me? - Line 259:  I am not following where in the analysis the increase of the error accompanied by the growth of m is predicted.   Typoes: - Line 169:  One -> On - Line 188:  position of 'and'