# When can we rank well from comparisons of O(n\log(n)) non-actively chosen pairs?

Arun Rajkumar, Shivani Agarwal
; 29th Annual Conference on Learning Theory, PMLR 49:1376-1401, 2016.

#### Abstract

Ranking from pairwise comparisons is a ubiquitous problem and has been studied in disciplines ranging from statistics to operations research and from theoretical computer science to machine learning. Here we consider a general setting where outcomes of pairwise comparisons between items i and j are drawn probabilistically by flipping a coin with unknown bias P_ij , and ask under what conditions on these unknown probabilities one can learn a good ranking from comparisons of only O(n\log(n)) non-actively chosen pairs. Recent work has established this is possible under the Bradley-Terry-Luce (BTL) and noisy permutation (NP) models. Here we introduce a broad family of ‘low-rank’ conditions on the probabilities P_ij under which the resulting preference matrix P has low rank under some link function, and show these conditions encompass the BTL and Thurstone classes as special cases, but are considerably more general. We then give a new algorithm called low-rank pairwise ranking (LRPR) which provably learns a good ranking from comparisons of only O(n\log(n)) randomly chosen comparisons under such low-rank models. Our algorithm and analysis make use of tools from the theory of low-rank matrix completion, and provide a new perspective on the problem of ranking from pairwise comparisons in non-active settings.
{"ft_lang_label":"__label__en","ft_lang_prob":0.88411826,"math_prob":0.9080895,"size":7220,"snap":"2021-21-2021-25","text_gpt3_token_len":1643,"char_repetition_ratio":0.13054323,"word_repetition_ratio":0.7655236,"special_character_ratio":0.21703601,"punctuation_ratio":0.07619048,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96048003,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-05-06T10:00:26Z\",\"WARC-Record-ID\":\"<urn:uuid:936af1c4-eda1-4fde-a1db-3d1d4a69a237>\",\"Content-Length\":\"18478\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:8203f6d5-e767-4ef8-95ea-bb2716f2953c>\",\"WARC-Concurrent-To\":\"<urn:uuid:169d2f79-cad3-41c0-bc89-576ecebb9641>\",\"WARC-IP-Address\":\"185.199.111.153\",\"WARC-Target-URI\":\"https://proceedings.mlr.press/v49/rajkumar16.html\",\"WARC-Payload-Digest\":\"sha1:HPDBWZ2AWXRO3DHWKRLOXJWXEGTO7GXH\",\"WARC-Block-Digest\":\"sha1:PLX37KUMCYLG37WFBKFPEASPJXZLRMSU\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-21/CC-MAIN-2021-21_segments_1620243988753.91_warc_CC-MAIN-20210506083716-20210506113716-00353.warc.gz\"}"}