Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
This work addresses efficiency in ranking tasks for applications like expert verification or simulation, but it is incremental as it builds on prior two-oracle models with adaptive improvements.
The paper tackles the problem of identifying top-k items when exact valuations are expensive by using a combination of noisy weak and scarce strong oracles, with ACE and ACE-W algorithms achieving strong call bounds of O(m(4ε_max)) and reducing costs in practice.
Identifying the top-$k$ items is fundamental but often prohibitive when exact valuations are expensive. We study a two-oracle setting with a fast, noisy weak oracle and a scarce, high-fidelity strong oracle (e.g., human expert verification or expensive simulation). We first analyze a simple screen-then-certify baseline (STC) and prove it makes at most $m(4\varepsilon_{\max})$ strong calls given jointly valid weak confidence intervals with maximum radius $\varepsilon_{\max}$, where $m(\cdot)$ denotes the near-tie mass around the top-$k$ threshold. We establish a conditional lower bound of $Ω(m(\varepsilon_{\max}))$ for any algorithm given the same weak uncertainty. Our main contribution is ACE, an adaptive certification algorithm that focuses strong queries on critical boundary items, achieving the same $O(m(4\varepsilon_{\max}))$ bound while reducing strong calls in practice. We then introduce ACE-W, a fully adaptive two-phase method that allocates weak budget adaptively before running ACE, further reducing strong costs.