Apr, 2024

高效且近似最优的流式差分隐私噪声生成

PDF
TL;DR差分隐私持续计数任务中，我们接收到一系列增量，并旨在输出这些增量的近似累加和，同时不泄漏关于任何特定增量的过多信息。我们提出了两种方法，一种基于空间高效的流式矩阵乘法算法，另一种将我们的第一种方法与类似于二叉树机制的递归构造相结合。这些方法在差分隐私持续计数中实现了近乎最优的效用，并且只需要对数或多对数的空间和时间。
differentially private continual countinggaussian noisestreaming matrix multiplication algorithmtoeplitz matricesapproximation theory
发现论文，激发创造
  • 差分隐私的离散高斯

    本研究探讨了在差分隐私框架下，使用离散高斯噪声可以提供与连续高斯噪声相同的隐私性和准确性保证，而且还提出了可用于准确采样的简单高效算法，表明其适用于私密回答计数查询或低敏感度整数值查询。

    Mar, 2020

  • 高效私密延续观察的平滑二元机制

    研究在随时间不断变化的数据集上发布差分隐私估计值的问题，提出了一种替代二进制机制的简单方法，该方法生成噪声的平均时间为常数，噪声方差比二进制机制少约 4 倍，并且在每个步骤中具有相同的噪声分布。

    Jun, 2023

  • 连续观测下的差分隐私求和统一框架

    我们研究在连续观测下如何保持差异隐私衰减和的问题，提出了一个统一的框架和一个高效的算法，该算法适用于任何足够平滑的函数。我们的算法是首个在多项式衰减权重情况下没有乘法误差的差异隐私算法，并改进了之前的工作，并在连续计数中恢复了 Henzi......

    Jul, 2023

  • 来自匿名消息的私人计数：凭借消失通信开销的接近最优准确性

    本文介绍了中心模型、本地 DP 模型和洗牌 DP 模型，并提出了在洗牌 DP 模型下用于机器学习的两种基本聚合方法，其精度接近中心 DP 算法，而通信效率与不加隐私约束的通信需求基本匹配。

    Jun, 2021

  • 通过偏微分隐私实现敌对抗性强鲁棒的分布式计数跟踪

    研究了分布式跟踪模型，包括功能性监控、通信成本、适应性对手和鲁棒计数跟踪，提出了一种具有最佳通信的鲁棒算法，并通过引入 “部分差分隐私” 和证明一个新的推广定理来解决分布式问题的挑战。

    Nov, 2023

  • 具有相关噪声的差分隐私在线联邦学习

    我们提出了一种新颖的差分隐私算法，用于在线联合学习，通过使用时间相关的噪声来提高效用并确保连续发布的模型的隐私性。

    Mar, 2024

  • 有限计算机上的差分隐私

    提供严格多项式时间的离散算法，用于近似分类数据集的直方图，同时保留与拉普拉斯机制相同的（纯）差分隐私保证，并基于受限离散计算模型，避免了基于实际算术的不同隐私算法攻击实现的可能性。

    Sep, 2017

  • PrivStream: 流式差分隐私数据的算法

    我们提出了一种用于在线流式数据生成的差分隐私合成算法，重点针对空间数据集。此外，我们提供了一个针对多个查询的在线选择性计数的通用框架，为查询回答和合成数据生成等多个任务提供基础。我们验证了算法在现实世界和模拟数据集上的实用性。

    Jan, 2024

  • 流式差分隐私下 $L_2$ 均值估计的通信隐私权衡改进

    在本研究中，我们通过引入一种新的隐私账户方法，将稀疏高斯机制中的稀疏性所固有的随机性结合到差分隐私噪声中，解决了 $L_2$ 均值估计在中心差分隐私和通信约束下的两个关键挑战，并扩展了稀疏化方案到流式差分隐私的矩阵分解框架，为 DP-FTRL 类型的优化器提供了一个精确的账户方法。

    May, 2024

  • 相关噪声在差分隐私学习中明显优于独立噪声

    在研究中，我们表征了任意关联函数的渐进学习效用，并给出了线性回归的精确分析边界以及对于一般凸函数问题的凸优化问题的解。我们通过这些界限展示了关联噪声相对于基本 DP-SGD 在问题参数（如有效维度和条件数）上的可证明改进。此外，我们的近乎最优关联函数的解析表达，绕开了先前工作中用于优化噪声关联矩阵的半正定程序的立方复杂性。我们通过隐私深度学习实验验证了我们的理论，在计算和内存方面都与之前的工作相匹配或超越。

    Oct, 2023