提出首个近乎线性依赖可靠性的均匀性测试算法，提升科学实验可复现性。
Replicable Uniformity Testing
- 设计可在任意分布下保持结果一致的可复现测试方法
- 仅需约√n·ε⁻²·ρ⁻¹样本，接近理论最优
- 适用于关注实验可复现性的统计与机器学习研究者
均匀性测试是分布测试中最基础的问题之一。给定对未知分布 𝒑 在 [n] 上的样本访问权限，需判断 𝒑 是否为均匀分布或与均匀分布的总变差距离至少为 ε。已有研究确立其样本复杂度为 Θ(√n ε⁻²)。然而当输入分布既非均匀也非远离均匀时，现有算法可能表现出高度不可复现的行为，若用于科学研究，可能导致矛盾结果并削弱公众对科学的信任。本文在算法可复现性框架（STOC '22）下重新审视均匀性测试，要求算法在任意分布下均具可复现性。尽管可复现性通常导致样本复杂度增加 ρ⁻² 倍，本文仅用 Õ(√n ε⁻² ρ⁻¹) 样本实现可复现测试，为首个近乎线性依赖 ρ 的可复现学习算法。最后，我们针对一类‘对称’算法（包括所有现有均匀性测试器）证明了几乎匹配的样本复杂度下界。
原文摘要 · Abstract (English)
Uniformity testing is arguably one of the most fundamental distribution testing problems. Given sample access to an unknown distribution $\mathbf{p}$ on $[n]$, one must decide if $\mathbf{p}$ is uniform or $\varepsilon$-far from uniform (in total variation distance). A long line of work established that uniformity testing has sample complexity $Θ(\sqrt{n}\varepsilon^{-2})$. However, when the input distribution is neither uniform nor far from uniform, known algorithms may have highly non-replicable behavior. Consequently, if these algorithms are applied in scientific studies, they may lead to contradictory results that erode public trust in science. In this work, we revisit uniformity testing under the framework of algorithmic replicability [STOC '22], requiring the algorithm to be replicable under arbitrary distributions. While replicability typically incurs a $ρ^{-2}$ factor overhead in sample complexity, we obtain a replicable uniformity tester using only $\tilde{O}(\sqrt{n} \varepsilon^{-2} ρ^{-1})$ samples. To our knowledge, this is the first replicable learning algorithm with (nearly) linear dependence on $ρ$. Lastly, we consider a class of ``symmetric" algorithms [FOCS '00] whose outputs are invariant under relabeling of the domain $[n]$, which includes all existing uniformity testers (including ours). For this natural class of algorithms, we prove a nearly matching sample complexity lower bound for replicable uniformity testing.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。