Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles

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(4varepsilonmax) strong calls given jointly valid weak confidence intervals with maximum radius varepsilonmax, where m(·) denotes the near-tie mass around the top-k threshold. We establish a conditional lower bound of Omega(m(varepsilonmax)) 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(4varepsilonmax)) 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.