arXiv:2507.02842cs.DScs.LG2025-07被引 2

提出可复现假设检验的通用框架,实现高效且可靠的统计测试。

On the Structure of Replicable Hypothesis Testers

  • 设计一类规范化的可复现检验算法,基于确定性统计量与随机阈值。
  • 在均匀性、恒等性和接近性检验中获得紧致的样本复杂度下界。
  • 适用于多种测试场景,且保持多项式时间效率,适合实际应用。

假设检验算法若在来自同一分布的两个不同样本上运行时以高概率产生相同输出,则称为可复现。该概念由Impagliazzo等人定义,与算法稳定性、泛化能力及隐私密切相关。本文构建了证明可复现检验算法样本复杂度上下界的通用工具,统一并量化改进了现有结果。我们识别出一组规范性质,并证明任何可复现检验算法均可修改为满足这些性质而不降低准确率或增加样本开销。规范化的可复现算法计算输入的确定性函数(即检验统计量),并用[0,1]上的均匀随机值进行阈值判断,对样本顺序不变,若检验问题具有对称性,则对域元素标签也保持不变,解决了Liu和Ye提出的一个开放问题。通过将问题归约为此类规范形式,我们获得了均匀性、恒等性和接近性检验的新下界。系统化并改进了基于已知期望与有界方差统计量的常见设计策略。本框架使大量在非可复现设置中已分析过的测试器可被轻易转化为可复现版本,仅需极小额外开销。作为直接应用,我们得到硬币检验和接近性检验的常数因子最优界,且在大参数范围内无需额外成本即可实现可复现性;同时在可复现高斯均值检验中达到当前最优界,且算法运行时间为多项式时间。

原文摘要 · Abstract (English)

A hypothesis testing algorithm is replicable if, when run on two different samples from the same distribution, it produces the same output with high probability. This notion, defined by by Impagliazzo, Lei, Pitassi, and Sorell [STOC'22], can increase trust in testing procedures and is deeply related to algorithmic stability, generalization, and privacy. We build general tools to prove lower and upper bounds on the sample complexity of replicable testers, unifying and quantitatively improving upon existing results. We identify a set of canonical properties, and prove that any replicable testing algorithm can be modified to satisfy these properties without worsening accuracy or sample complexity. A canonical replicable algorithm computes a deterministic function of its input (i.e., a test statistic) and thresholds against a uniformly random value in $[0,1]$. It is invariant to the order in which the samples are received, and, if the testing problem is ``symmetric,'' then the algorithm is also invariant to the labeling of the domain elements, resolving an open question by Liu and Ye [NeurIPS'24]. We prove new lower bounds for uniformity, identity, and closeness testing by reducing to the case where the replicable algorithm satisfies these canonical properties. We systematize and improve upon a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our framework allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework, we obtain constant-factor optimal bounds for coin testing and closeness testing and get replicability for free in a large parameter regime for uniformity testing. We also give state-of-the-art bounds for replicable Gaussian mean testing, and, unlike prior work, our algorithm runs in polynomial time.

假设检验可复现性统计测试算法稳定性

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。