Timezone: »

Talk
Maximum Selection and Ranking under Noisy Comparisons
Moein Falahatgar · Alon Orlitsky · Venkatadheeraj Pichapati · Ananda Theertha Suresh

Mon Aug 07 09:24 PM -- 09:42 PM (PDT) @ C4.1
We consider $(\epsilon,\delta)$-PAC maximum-selection and ranking using pairwise comparisons for \nobreak{general} probabilistic models whose comparison probabilities satisfy strong stochastic transitivity and stochastic triangle inequality. Modifying the popular knockout tournament, we propose a simple maximum-selection algorithm that uses $\mathcal{O}\left(\frac{n}{\epsilon^2} \left(1+\log \frac1{\delta}\right)\right)$ comparisons, optimal up to a constant factor. We then derive a general framework that uses noisy binary search to speed up many ranking algorithms, and combine it with merge sort to obtain a ranking algorithm that uses $\mathcal{O}\left(\frac n{\epsilon^2}\log n(\log \log n)^3\right)$ comparisons for $\delta=\frac1n$, optimal up to a $(\log \log n)^3$ factor.
{"ft_lang_label":"__label__en","ft_lang_prob":0.5127408,"math_prob":0.99627477,"size":5722,"snap":"2022-27-2022-33","text_gpt3_token_len":1648,"char_repetition_ratio":0.14498076,"word_repetition_ratio":0.48383373,"special_character_ratio":0.23663054,"punctuation_ratio":0.08495145,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9980608,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-06-30T02:16:36Z\",\"WARC-Record-ID\":\"<urn:uuid:195d1ece-cbb1-49a8-9003-598c8f9cf35e>\",\"Content-Length\":\"49152\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:860e48ed-d9fd-445e-9529-971be4dc477d>\",\"WARC-Concurrent-To\":\"<urn:uuid:dd7b6603-1e03-4025-b5ec-d8c5463752e3>\",\"WARC-IP-Address\":\"198.202.70.65\",\"WARC-Target-URI\":\"https://icml.cc/Conferences/2017/ScheduleMultitrack?event=1307\",\"WARC-Payload-Digest\":\"sha1:7ZBVUNH2HEEETLLQVNT5YHOEHGRBSYGY\",\"WARC-Block-Digest\":\"sha1:JIG7KURXYDHW2IZS5IWKF5CIMX36JF6B\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-27/CC-MAIN-2022-27_segments_1656103646990.40_warc_CC-MAIN-20220630001553-20220630031553-00601.warc.gz\"}"}