May, 2019

高维分布的私密身份测试

PDF
TL;DR本文提出了对于自然广泛应用的多元产品分布，包括在已知协方差下的 Gaussians 和值域为 {±1}^d 的产品分布的新型差分私有（适合性）测试器。这些测试器相比于之前的技术得出了样本复杂度的改进，并且是第一个样本复杂度在许多参数区域与阶优化极小值样本复杂度相匹配的测试器。我们构建了两种类型的测试器，展示了样本复杂度和计算复杂度之间的权衡。最后，我们提供了多元产品分布的子类测试和单变量分布测试之间的双向约简，并因此获得了此类产品分布测试的上下界。
differentially private identity testersmultivariate product distributionsgaussianssample complexityminimax sample complexity
发现论文，激发创造
  • 离散分布身份和接近性的差分隐私测试

    该研究提供了关于差分隐私下 k 个元素分布的标识检测和接近度检验的上下界。他们提出了一般框架以建立隐私统计任务的样本复杂度的下界，同时通过构建精心选择的先验概率来证明隐私算法的下界。

    Jul, 2017

  • 离散分布的差分隐私身份和相似性测试

    研究了利用随机样本对离散人群进行身份和相似度测试的问题，目标是开发出高效的测试器，并保证对个人的差异性隐私，提出了一种新的方法，可以产生样本有效的差异私有测试器用于解决这些问题，实验评估证明了我们的方案能够实现与非隐私测试器几乎相同的测试效率，同时达到了样本规模亚线性的领域大小下限。

    Jul, 2017

  • 高维分布私密学习

    本文介绍了用于两种基本高维学习问题的新型、计算有效和差分隐私算法：学习多元高斯分布和在布尔超立方体上学习乘积分布。我们的算法的样本复杂度几乎与这些任务的最优非隐私学习器的样本复杂度相匹配，表明隐私在这些问题上是几乎免费的。

    May, 2018

  • 对离散分布属性进行测试的新方法

    研究了分布检测的样本测试的复杂度问题，提出了两种技术方法，一种是提供样本最优测试器，另一种是提供匹配样本下界。作者解决了大量重要的测试问题并证明了样本最优性，并且得到了第一个样本最优的对应测试器。

    Jan, 2016

  • 高概率优化身份测试

    本研究主要研究了如何在高置信度条件下，通过有限样本同时检验分布 $q$ 和 $p$ 是否相同，其结果给出了最优样本复杂度并表明了经验分布在均匀性检测中的高效性。

    Aug, 2017

  • 测试 Ising 模型

    在高维分布的建模中，结构性多元分布的检测可以避免样本复杂度曾出现的问题。通过研究 Ising 模型，我们证明了在这种结构化场景中可以获得样本和时间高效的独立性和拟合优度测试。

    Dec, 2016

  • 作为双样本检验代理的分类准确性

    探究在高维情况下对分类器的精度验证，证明一种基于排列组合的测试方法具有连续性及德克斯特拉极限分布的高斯近似测试也具有连续性，并以高斯分布为例进一步研究了线性判别分析和 Hotelling's 测试等方法的功率。

    Feb, 2016

  • Priv'IT：私密且样本高效的身份验证

    本研究利用差分隐私方法进行小样本假设检验，以得出隐私参数、准确性参数和错误要求等信息，实现在保证样本大小和错误率时的差分隐私保护

    Mar, 2017

  • 通过 Ramsey 理论来测试多变量分布的紧密度

    我们研究了多维分布的相似性（或等价性）检测的统计任务，并提出了第一个解决这个问题的具有子学习样本复杂度的相似性检测器，其样本复杂度为 $O ((k^{6/7}/poly_d (ε)) log^d (k))$，同时建立了近似匹配的样本复杂度下界 $Ω(k^{6/7}/poly (ε))$，该问题在一维设置中的样本复杂度为 $Θ(k^{4/5}/poly (ε))$。我们的研究结果还衍生出了对于共同未知分区上的 $k$ 个直方图对和支持在 $k$ 个未知不相交轴对齐矩形的均匀分布对的 $d_{TV}$- 相似性检测器，并且在算法和下界的构建中，我们都借助了 Ramsey 理论的工具。

    Nov, 2023

  • 分布属性的最佳测试

    研究如何通过样本来鉴别未知分布是否属于某个分布类，提出了一种可获得最优样本和计算效率的通用方法，并为分布的基本属性提供了测试方法。

    Jul, 2015