研究按需采样中样本量与轮次的权衡，揭示了算法效率的极限。
Sample-Adaptivity Tradeoff in On-Demand Sampling
- 提出新框架OODS抽象采样适应性权衡，统一现有多分布学习算法。
- 在非可实现情形下，用近似√k轮完成近最优样本复杂度。
- 理论证明：更低轮次需突破固有难题，适合算法设计者参考。
我们研究按需采样中样本复杂度与轮次复杂度的权衡，学习算法在有限轮次内从k个分布中自适应采样。在可实现设置下，r轮算法的最优样本复杂度约为dk^{Θ(1/r)} / ε。在一般不可实现情形下，提出一个算法，在~O(√k)轮内达到~O((d + k) / ε²)的近最优样本复杂度。引入新框架优化通过按需采样（OODS），抽象出该权衡并涵盖大多数现有多分布学习算法。建立接近紧致的轮次复杂度界：上界直接导出针对不可实现MDL的~O(√k)轮算法，下界表明要实现亚多项式轮次复杂度，需突破OODS的固有困难，依赖全新技术。
原文摘要 · Abstract (English)
We study the tradeoff between sample complexity and round complexity in on-demand sampling, where the learning algorithm adaptively samples from $k$ distributions over a limited number of rounds. In the realizable setting of Multi-Distribution Learning (MDL), we show that the optimal sample complexity of an $r$-round algorithm scales approximately as $dk^{Θ(1/r)} / ε$. For the general agnostic case, we present an algorithm that achieves near-optimal sample complexity of $\widetilde O((d + k) / ε^2)$ within $\widetilde O(\sqrt{k})$ rounds. Of independent interest, we introduce a new framework, Optimization via On-Demand Sampling (OODS), which abstracts the sample-adaptivity tradeoff and captures most existing MDL algorithms. We establish nearly tight bounds on the round complexity in the OODS setting. The upper bounds directly yield the $\widetilde O(\sqrt{k})$-round algorithm for agnostic MDL, while the lower bounds imply that achieving sub-polynomial round complexity would require fundamentally new techniques that bypass the inherent hardness of OODS.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。