closeness testing | BriefGPT

关键词closeness testing

搜索结果 - 7

通过 Ramsey 理论来测试多变量分布的紧密度
我们研究了多维分布的相似性（或等价性）检测的统计任务，并提出了第一个解决这个问题的具有子学习样本复杂度的相似性检测器，其样本复杂度为 $O ((k^{6/7}/poly_d (ε)) log^d (k))$，同时建立了近似匹配的样本复杂度下
PDF7 months ago
高概率离散分布的最佳测试
研究总变差距离下的离散分布测试问题，提出可用于样本较高概率区域的属性测试的算法，包括相应参数的样本复杂度与正确性保障。
PDF4 years ago
离散分布的差分隐私身份和相似性测试
研究了利用随机样本对离散人群进行身份和相似度测试的问题，目标是开发出高效的测试器，并保证对个人的差异性隐私，提出了一种新的方法，可以产生样本有效的差异私有测试器用于解决这些问题，实验评估证明了我们的方案能够实现与非隐私测试器几乎相同的测试效
PDF7 years ago
离散分布身份和接近性的差分隐私测试
该研究提供了关于差分隐私下 k 个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界，同时通过构建精心选择的先验概率来证明隐私算法的下界。
PDF7 years ago
测试贝叶斯网络
本文研究了 Bayesian 网络的身份测试和相似性测试的性质，提出了第一个非平凡的高效测试算法，并给出了相应的信息理论下界，其测试样本复杂度在维度上是亚线性的，适用于各种参数设置，是样本的最优解，直到常数因子。
PDF8 years ago
使用不均等大小的样本进行接近度测试
考虑从一个未知分布 $p$ 取 $m_1$ 个样本，从另一个未知分布 $q$ 取 $m_2$ 个样本的情形，介绍了一种测试是否有 $p=q$ 的快速算法，并分析了测试的样本复杂度，同时提出了估计马尔科夫链混合时间的算法及其初始样本个数的选择
PDF9 years ago
离散分布相似度检测的最优算法
本文研究了对于两个离散分布的近似度检测问题，给出了一些用于信息理论最优的简单测试方法，并且在 $n$ 和 $\eps$ 的依赖关系上都达到了常数因子。
PDF11 years ago