Jul, 2011

迭代构造与私有数据发布

PDF
TL;DR本文研究在保护差分隐私的情况下近似发布图割函数的问题，并在交互和非交互设置中提出了新算法，其中交互算法是通过重新审视关于数据库上发布差分隐私，近似答案的大量查询的问题来实现的，并给出了一个新的通用框架，在其中新的（高效）IDC 算法产生了新的（高效）交互式私有查询发布机制。非交互算法则是通过随机响应和 Alon 和 Naor 的基于 SDP 的，常数因子逼近割范数的非私有实现的算法来发布保密合成数据。最后，我们给出了一个基于 IDC 框架的约简，表明计算足够精确的秩 1 矩阵逼近的高效，私有算法将导致发布保密合成数据的改进有效算法。
graph cutdifferential privacyinteractive algorithmiterative database constructionlow-rank matrix decomposition
发现论文，激发创造
  • 非交互式数据库隐私的学习理论方法

    论文证明，私人发布用于大量查询的合成数据库是可能的，但仅针对离散领域，并提供了一种新的数据隐私概念：分布隐私。

    Sep, 2011

  • 几乎线性时间的差分隐私合成图释放

    给定输入为具有 n 个顶点 m 条边的图 G，本论文提出了第一个时间复杂度为 O (m)、空间复杂度为 O (m) 的差分隐私算法，用于输出近似于 G 的所有切割和谱的顶点数为 n、边数为 O (m) 的合成图，同时实现了与非隐私设置相匹配的时间和空间复杂性以及先前工作在更实际的稀疏区域内达到相同（或更好）的效用，并且该算法能够扩展到私密图分析和持续观察下。

    Jun, 2024

  • 通过自适应投影实现差分隐私查询发布

    提出了一种新的算法，用于发布对包括 k 路边际在内的非常大量的统计查询回答，该算法采用连续松弛的投影机制，使其在隐私数据集上回答查询并尝试找到最接近噪声回答的合成数据集，并通过不断适应地发现在其（松弛的）合成数据上具有高误差的查询，以达到节省隐私预算的目的，通过使用 ML 优化技术和工具，该方法在许多情况下优于现有算法。

    Mar, 2021

  • 私人合成数据发布的新型高效算法

    提出了三种新的算法，用于构建差分隐私合成数据，且算法在最坏情况下具有差分隐私，通过理论分析和实证评估，确保准确性与隐私性。

    Jul, 2020

  • 双重查询：针对高维数据的实用私有查询发布

    提出了一种实用的差分隐私算法，可以回答高维数据集上的大量查询，并将计算困难的步骤封装为一个简洁定义的整数规划问题，以实现高效的回答。通过在 Netflix 数据集上的实验，证明了该算法的精度和隐私性定理，并提出了比现有技术显著改进的方案。

    Feb, 2014

  • 递归机制：向节点差分隐私和不受限连接迈进 [完整版本，草稿 0.1]

    本文提出了一种新的差分隐私机制，该机制支持对敏感数据库上通过一些关系代数计算的结果的线性统计量进行近似，并且支持不受限制的连接操作，其误差边界大致与查询的经验灵敏度成正比，对于任何一种子图，本文提供了能够实现节点差分隐私的第一种解决方案。

    Apr, 2013

  • Bernstein 机制：差分隐私下的函数发布

    通过开发一个适用于 Oracle 访问目标函数评估和灵敏度的功能机制，利用迭代 Bernstein 算子进行多项式逼近和多项式系数扰动，在较弱的正则条件下建立了快速的依概率均匀逼近的实用程序速率，可用于解决函数发布的差分隐私问题，并提供了任何函数机制可实现的效用下限。

    Jul, 2015

  • 一种简单实用的差分隐私数据发布算法

    该研究通过组合多项式权重方法和指数机制，实现不同隐私等级和计数查询下的差分隐私数据发布，并在实际数据集上进行了实证研究，结果表明该方法在误差和运行时间方面都优于以往的方法。

    Dec, 2010

  • 差分隐私矩阵机制下查询集的最优误差

    研究了通过矩阵机制方法，针对支持一组特定数量的问题而调整的合成数据集，在差分隐私下生成合成数据的方法及其对解析一组线性计数查询的困难度的影响，发现查询量的难度与行列式物理特性相关。

    Feb, 2012

  • 私密发布合取和统计查询障碍

    本研究提出了两个结果，第一个结果说明了在 Kearns' SQ 模型中，对一组统计查询 C 生成错误率较小的所有答案需要的统计查询次数是对偶学习复杂度；第二个结果能高效地解决问题，只要能够通过子模函数描述 C 的答案集。这两个结果对隐私保护数据分析产生了积极的应用，使其得到了重大进展。

    Nov, 2010