Sample complexity of rank regression using pairwise comparisons. (October 2022)

• Record Type: Journal Article
• Authors: Kadıoğlu, Berkan; Tian, Peng; Dy, Jennifer; Erdoğmuş, Deniz; Ioannidis, Stratis
• Is Part Of: Pattern recognition. Volume 130(2022)
• Publication Date: 2022-10
• Subjects: Sample complexity -- Rank regression -- Pairwise comparisons -- Features; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2022.108688
• Languages: English
• ISSNs: 0031-3203

Abstract

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