详细内容或原文请订阅后点击阅览
如何验证任何（合理的）分发属性：分布的计算声音参数系统
随着统计分析对科学，工业和社会的核心越来越重要，因此越来越需要确保其结果的正确性。可以通过复制整个分析来验证近似正确性，但是我们可以在不复制的情况下验证吗？在最新工作的基础上，我们研究了允许概率验证者确定分析结果的证明系统近似正确，同时绘制较少的样本和使用较少的计算资源来复制分析所需的计算资源。我们专注于分发测试问题：验证…
来源:Apple机器学习研究随着统计分析在科学、工业和社会中变得越来越重要，确保其结果正确性的需求也越来越大。可以通过复制整个分析来验证大致的正确性，但是我们可以在不复制的情况下进行验证吗？在最近的工作基础上，我们研究了证明系统，该系统允许概率验证者确定分析结果大致正确，同时抽取更少的样本并使用比复制分析所需的更少的计算资源。我们专注于分布测试问题：验证未知分布是否接近拥有已声明的属性。
我们的主要贡献是验证者和不受信任的证明者之间的交互协议，它可用于验证可以在多项式时间内确定的任何分布属性，前提是给出完整且明确的分布描述。如果分布与具有该属性的统计距离为 ε，则验证者以高概率拒绝。假设存在抗碰撞散列函数（密码学中的标准假设），这种健全性属性反对作弊证明者可能遵循的任何多项式时间策略。对于大小为 N 的域上的分布，协议由 4 条消息组成，通信复杂度和验证者运行时间大致为 O~(N/ε2)Õ(\sqrt N / ε^2)O~(N/ε2)。验证者的样本复杂度为 O~(N/ε2)Õ(\sqrt N / ε^2)O~(N/ε2)，这是最优的，最高可达 polylog(N)polylog(N)polylog(N) 因子（对于任何协议，无论其通信复杂性如何）。即使对于简单的属性，近似确定未知分布是否具有该属性也可能需要准线性样本复杂性和运行时间。对于任何此类属性，我们的协议提供了比复制分析更快的二次方加速。
O~(N/ε2)Õ(\sqrt N / ε^2)O~(N/ε2) O~(N/ε2)Õ(\sqrt N / ε^2)