Sample complexity of rank regression using pairwise comparisons. (October 2022) - Kadıoğlu, Berkan; Tian, Peng; Dy, Jennifer; Erdoğmuş, Deniz; Ioannidis, Stratis
Highlights: We propose an estimator for the parameters of a generalized linear parametric model, which encompasses classical preference models such as Bradley-Terry [13] and Thurstone [14]. We overcome the violation of independence and prove a sample complexity guarantee on model parameters. In particular, assuming Gaussian distributed features, we characterize the convergence of the estimator to a rescaled version of the model parameters w.r.t. the ambient dimension d, the number of samples N, and the number of comparisons M presented to the oracle. We show that to attain an accuracy ϵ > 0 in model parameters, it suffices to conduct Ω ( d N log 3 N / ϵ 2 ) comparisons when the number of samples is Ω ( d / ϵ 2 ) . Finally, we confirm this dependence with experiments on synthetic data. Abstract: We consider a rank regression setting, in which a dataset of N samples with features in R 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 ∈ Ω ( d N log 3 N / ϵ 2 ) comparisons uniformly at random when N is Ω ( d / ϵ 2 ) .