# Instance-Optimality in the Noisy Value-and Comparison-Model --- Accept, Accept, Strong Accept: Which Papers get in?

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2018.

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

- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)
- [Regret Minimization with Noisy Observations](https://mlsanity.com/paper/2207.09435/) (2022)

## Abstract (arXiv)

Motivated by crowdsourced computation, peer-grading, and recommendation systems, Braverman, Mao and Weinberg [STOC'16] studied the query and round complexity of fundamental problems such as finding the maximum (textscmax), finding all elements above a certain value (textscthreshold-v) or computing the top-k elements (textscTop-k) in a noisy environment. For example, consider the task of selecting papers for a conference. This task is challenging due the crowdsourcing nature of peer reviews: the results of reviews are noisy and it is necessary to parallelize the review process as much as possible. We study the noisy value model and the noisy comparison model: In the noisy value model, a reviewer is asked to evaluate a single element: "What is the value of paper i?" (eg accept). In the noisy comparison model (introduced in the seminal work of Feige, Peleg, Raghavan and Upfal [SICOMP'94]) a reviewer is asked to do a pairwise comparison: "Is paper i better than paper j?" In this paper, we show optimal worst-case query complexity for the textscmax,textscthreshold-v and textscTop-k problems. For textscmax and textscTop-k, we obtain optimal worst-case upper and lower bounds on the round vs query complexity in both models. For textscthreshold-v, we obtain optimal query complexity and nearly-optimal round complexity, where k is the size of the output) for both models. We then go beyond the worst-case and address the question of the importance of knowledge of the instance by providing, for a large range of parameters, instance-optimal algorithms with respect to the query complexity. Furthermore, we show that the value model is strictly easier than the comparison model.