On the Sample Complexity of Rank Regression from Pairwise Comparisons

Berkan Kadioglu, Peng Tian, Jennifer Dy +2

We consider a rank regression setting, in which a dataset of $N$ samples with features in ${\mathbb{R}}^d$ is ranked by an oracle via $M$ pairwise comparisons. Specifically, there ex…