On the Sample Complexity of Rank Regression from Pairwise Comparisons

We consider a rank regression setting, in which a dataset of N samples with features in ℝd is ranked by an oracle via M pairwise comparisons. Specifically, there exists a latent total ordering of the samples; when presented with a pair of samples, a noisy oracle identifies the one ranked higher with respect to the underlying total ordering. A learner observes a dataset of such comparisons and wishes to regress sample ranks from their features. We show that to learn the model parameters with ε > 0 accuracy, it suffices to conduct M ∈ Omega(dNlog3 N/ε2) comparisons uniformly at random when N is Omega(d/ε2).