测试泊松二项分布
研究了无监督学习中的一个基本问题:学习未知的泊松二项式分布,并提出高效的算法,其时间复杂度与数据大小呈对数关系,可以学习到精度为ε的结果。同时,提出一个适当的学习算法来学习泊松二项式分布的加权和。
Jul, 2011
该研究提供了一种改进的A/B测试性能的分布依赖性下限方法,特别是在高斯分布和伯努利分布下,为固定置信度和固定预算的情况下提供了复杂性的证明和比较,同时还提供了停止规则。
May, 2014
考虑从一个未知分布$p$取$m_1$个样本,从另一个未知分布$q$取$m_2$个样本的情形,介绍了一种测试是否有$p=q$的快速算法,并分析了测试的样本复杂度,同时提出了估计马尔科夫链混合时间的算法及其初始样本个数的选择方法。测试算法主要依靠一种表现较为优异的统计量。
Apr, 2015
该研究提供了关于差分隐私下k个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界,同时通过构建精心选择的先验概率来证明隐私算法的下界。
Jul, 2017
本文提出了对于自然广泛应用的多元产品分布,包括在已知协方差下的Gaussians和值域为{±1}^d的产品分布的新型差分私有(适合性)测试器。这些测试器相比于之前的技术得出了样本复杂度的改进,并且是第一个样本复杂度在许多参数区域与阶优化极小值样本复杂度相匹配的测试器。我们构建了两种类型的测试器,展示了样本复杂度和计算复杂度之间的权衡。最后,我们提供了多元产品分布的子类测试和单变量分布测试之间的双向约简,并因此获得了此类产品分布测试的上下界。
May, 2019
使用新技术,我们证明了通过涉及所讨论分布的bin概率的不等式定义的性质的分布测试下界。利用该技术,我们对离散六面体上的单调性测试获得了新的下界,并对对数凹性测试获得了严格的下界。
Jul, 2023
在标准访问模型和条件访问模型中,当测试算法的内存受到限制时,我们研究分布测试。我们提供了一个样本复杂性和空间复杂性之间的权衡,用于在根据条件访问预言进行抽样时测试身份。我们还展示了我们可以有效地学习具有几乎最优的样本存储限制的单调分布的简洁表示。此外,我们还展示了单调分布的算法可以扩展到更大的可分解分布类。
Sep, 2023