Jul, 2017

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

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

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

    Jul, 2017

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

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

    Jan, 2016

  • 高维分布的私密身份测试

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

    May, 2019

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

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

    Mar, 2017

  • 差分隐私聚类：紧密逼近比率

    本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。

    Aug, 2020

  • 高概率离散分布的最佳测试

    研究总变差距离下的离散分布测试问题，提出可用于样本较高概率区域的属性测试的算法，包括相应参数的样本复杂度与正确性保障。

    Sep, 2020

  • 重新审视针对分类数据的差分隐私假设检验

    本文提出了一种新型假设检验方法，能够应用于含有隐私保护的差分隐私数据，并且其偏置较小、效果较好，解决了传统差分隐私假设检验方法中的问题。

    Nov, 2015

  • 离散分布相似度检测的最优算法

    本文研究了对于两个离散分布的近似度检测问题，给出了一些用于信息理论最优的简单测试方法，并且在 $n$ 和 $\eps$ 的依赖关系上都达到了常数因子。

    Aug, 2013

  • 高概率优化身份测试

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

    Aug, 2017

  • 可辨识性、差分隐私和互信息隐私之间的关系

    研究三种不同的隐私：可识别性、差分隐私和互信息隐私之间的关联关系，并确定它们之间的基本联系。

    Feb, 2014