# On the Sample Complexity of Rank Regression from Pairwise Comparisons

arXiv: https://arxiv.org/abs/2105.01463 · HTML: https://mlsanity.com/paper/2105.01463/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 70 references that are in the map.
- First posted on arXiv 4 May 2021.

## Builds on (most cited first, 7 of 7)

- [Deep Learning the City : Quantifying Urban Perception At A Global Scale](https://mlsanity.com/paper/1608.01769/) (2016)
- [Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues](https://mlsanity.com/paper/1510.05610/) (2015)
- [Active classification with comparison queries](https://mlsanity.com/paper/1704.03564/) (2017)
- [Minimax-optimal Inference from Partial Rankings](https://mlsanity.com/paper/1406.5638/) (2014)
- [Efficient active learning of sparse halfspaces](https://mlsanity.com/paper/1805.02350/) (2018)
- [Inductive Pairwise Ranking: Going Beyond the n log(n) Barrier](https://mlsanity.com/paper/1702.02661/) (2017)
- [How Many Pairwise Preferences Do We Need to Rank A Graph Consistently?](https://mlsanity.com/paper/1811.02161/) (2018)

## Built on by (most cited first, 1 of 1)

- [Differentially Private Regression with Unbounded Covariates](https://mlsanity.com/paper/2202.11199/) (2022)

## Abstract (arXiv)

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).