用少量高成本验证，高效找出前k个最优项
Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles
- 自适应地聚焦关键边界项，减少高成本验证次数
- 理论证明最多调用O(m(4εₘₐₓ))次强验证，与最优下界一致
- 适合资源受限的排名场景，如人工评估或昂贵仿真
识别前k个最优项是基础任务，但当精确评分代价高昂时难以实现。本文研究一种双预言机设置：快速但嘈杂的弱预言机与稀缺且高保真的强预言机（如人工专家验证或昂贵仿真）。首先分析简单的筛选-认证基线（STC），并证明在弱置信区间联合有效、最大半径为εₘₐₓ的前提下，其强预言机调用次数不超过m(4εₘₐₓ)，其中m(·)表示靠近前k阈值的近似并列质量。我们建立了给定相同弱不确定性下的条件性下界Ω(m(εₘₐₓ))。主要贡献是ACE算法，通过自适应聚焦于关键边界项，达到相同的O(m(4εₘₐₓ))上界，且实际中显著降低强验证开销。随后提出ACE-W，一种完全自适应的两阶段方法，在运行ACE前动态分配弱预算，进一步减少强成本。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。