提出可自适应追踪分布偏离均匀性的新算法，样本效率显著提升。
Instance-Optimal Uniformity Testing and Tracking
- 设计一种基于泊松混合结构的自适应检测方法
- 样本复杂度仅与最优算法的对数相关，性能逼近理论下界
- 适合分布未知且需高效检测异常的场景
在均匀性测试任务中，算法从未知概率分布中获取样本，需判断该分布是否为均匀分布，或其与均匀分布的总变差距离是否超过给定阈值。该问题已得到充分研究，复杂度基本明确。然而，我们指出其预设距离阈值的设定无法覆盖实际应用场景，且可能导致性能不佳。为此，本文提出均匀性追踪问题：要求算法以最少样本发现任何偏离均匀性的模式，并在事后表现上与已知分布真实形态的最优算法相竞争。核心贡献是构建了一个关于opt的polylog( opt)竞争比的均匀性追踪算法。该结果得益于对泊松混合的新结构分析，我们相信这些分析本身具有独立价值。
原文摘要 · Abstract (English)
In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a $\operatorname{polylog}(\operatorname{opt})$-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。