差异隐私(DP) 是一种通过数学保证用户数据隐私来实现数据分析和机器学习 (ML) 的方法。DP 量化了算法的“隐私成本”，即如果在给定数据集中添加或删除单个用户的数据，算法对给定数据集的输出分布不会发生显着变化的保证水平。该算法由两个参数 ε 和 δ 表征，其中两个值越小表示“越私密”。隐私预算 (ε, δ) 和算法的效用之间存在天然的矛盾：较小的隐私预算要求输出更“嘈杂”，通常导致效用降低。因此，DP 的一个基本目标是在期望的隐私预算下实现尽可能多的效用。
DP 的一个关键属性通常在理解隐私成本方面起着核心作用，即组合性，它反映了将 DP 算法组合在一起作为单一算法时的净隐私成本。一个值得注意的例子是差分隐私随机梯度下降(DP-SGD) 算法。该算法通过多次迭代（每次迭代都是差分隐私的）训练 ML 模型，因此需要应用 DP 的组合属性。DP 中的一个基本组合定理指出，一组算法的隐私成本最多是每个算法隐私成本的总和。然而，在许多情况下，这可能是一个严重高估，而几个改进的组合定理可以更好地估计组合的隐私成本。
2019 年，我们发布了一个开源库（在GitHub上），使开发人员能够使用基于 DP 的分析技术。今天，我们宣布将Connect-the-Dots添加到该库中，这是一种新的隐私核算算法，基于一种离散化隐私损失分布的新方法，是理解组合隐私成本的有用工具。该算法基于在PETS 2022上发表的论文“ Connect the Dots：隐私损失分布的更紧密离散近似” 。该核算算法的主要新颖之处在于它使用间接方法来构建更精确的隐私损失分布离散化。我们发现，与文献中的其他隐私核算方法相比，Connect-the-Dots 在准确性和运行时间方面具有显着的提升。该算法最近还被应用于训练广告预测模型中 DP-SGD 的隐私核算。
差异隐私和隐私损失分布
如果一个随机算法的输出“不显著依赖于”其训练数据集中的任何一个条目（用参数 (ε, δ) 进行数学量化），则该算法被认为满足 DP 保证。例如，考虑 DP-SGD 的激励示例。当使用（非私有）SGD 进行训练时，神经网络原则上可以在其权重内编码整个训练数据集，从而允许人们从训练模型中重建一些训练示例。另一方面，当使用 DP-SGD 进行训练时，我们可以正式保证，如果人们能够以非平凡的概率重建训练示例，那么即使该示例不包含在训练数据集中，人们也将能够重建相同的示例。
曲棍球棒散度用 ε 表示，是两个概率分布之间距离的度量，如下图所示。大多数 DP 算法的隐私成本由两个相关概率分布 P 和 Q 之间的曲棍球棒散度决定。如果 P 和 Q 之间 ε 的曲棍球棒散度值最多为 δ，则该算法满足具有参数 (ε, δ) 的 DP。(P, Q) 之间的曲棍球棒散度，表示为 δ P||Q (ε)，又完全由其相关的隐私损失分布表征，表示为 PLD P||Q。
分布 P 和 Q 之间的曲棍球棒散度 δ P||Q (ε) 的图示（左），其对应于P 的概率质量高于 e ε Q，其中 e ε Q 是Q 的概率质量的e ε缩放（右）。
处理 PLD 的主要优势在于算法的组成与相应 PLD 的卷积相对应。利用这一事实，先前的工作设计了有效的算法，只需使用快速傅里叶变换算法对各个 PLD 进行卷积，即可计算出与各个算法的组成相对应的 PLD 。
然而，处理许多 PLD 时的一个挑战是它们通常是连续分布，这使得卷积运算在实践中难以处理。因此，研究人员经常应用各种离散化方法来使用等距点来近似 PLD。例如，Privacy Buckets 算法的基本版本将两个离散化点之间的间隔的概率质量完全分配给间隔的较高端。
通过四舍五入概率质量进行离散化的图示。此处，通过四舍五入连续点之间的概率质量，将连续 PLD（蓝色）离散化为离散 PLD（红色）。
连点：一种新算法
我们新的 Connect-the-Dots 算法提供了一种更好的方法来离散化 PLD，以实现估算曲棍球棒散度的目标。这种方法是间接的，首先离散化曲棍球棒散度函数，然后将其映射回由等距点支持的离散 PLD。
连接点算法中的高级步骤的说明。
这种方法依赖于“主导 PLD ” 的概念，即如果前者的曲棍球棒散度大于或等于后者的曲棍球棒散度（对于所有 ε 值），则 PLD P'||Q'优于 PLD P||Q。主导 PLD 的关键特性是它们在组合后仍然占主导地位。因此，出于隐私核算的目的，使用主导 PLD 就足够了，这为我们提供了确切隐私成本的上限。
我们对连点算法的主要见解是离散 PLD 的特征，即当且仅当相应的曲棍球棒散度作为 e ε的函数在连续的 e ε值之间呈线性时，PLD 才在给定的有限 ε 值集上受支持。这使我们能够通过简单地连接点来离散曲棍球棒散度，从而获得一个分段线性函数，该函数精确等于给定 e ε值处的曲棍球棒散度函数。查看算法的 更详细解释。
通过 Connect-the-Dots 与 Privacy Buckets 对曲棍球棒散度进行离散化的比较。
实验评估
DP-SGD 算法涉及一个噪声乘数参数，该参数控制每个梯度步骤中添加的噪声量，以及一个采样概率，该概率控制每个小批量中包含的示例数量。我们在隐私会计 DP-SGD 任务上将 Connect-the-Dots 与下面列出的算法进行了比较，其中噪声乘数 = 0.5，采样概率 = 0.2 x 10 -4和 δ = 10 -8。
Renyi DP：DP-SGD 隐私核算的原始方法。Google -DP 库也支持此核算方法。
隐私桶：Google-DP 库中以前使用的基于 PLD 的方法，它对离散化点之间的概率质量进行四舍五入。
Microsoft PRV Accountant：此方法通过保留PLD 平均值的离散化改进了隐私存储桶方法。
我们绘制了每种算法计算出的 ε 值与组合步骤数的关系图，此外，我们还绘制了实现的运行时间图。如下图所示，使用 Renyi DP 的隐私核算提供了隐私损失的粗略估计。但是，当比较使用 PLD 的方法时，我们发现在此示例中，Connect-the-Dots 的实现对隐私损失的估计更为严格，运行时间比 Microsoft PRV Accountant 快 5 倍，比 Google-DP 库中的隐私桶的先前方法快 200 倍以上。
左图：不同算法返回的 DP-SGD 不同步数的隐私参数 ε 的上限（固定 δ = 10 -8）。右图：不同算法的运行时间。
结论和未来方向
本研究提出了Connect-the-Dots 算法，这是一种用于计算差分隐私算法组合的最佳隐私参数的新算法。在 DP-SGD 任务上进行评估时，我们发现该算法对隐私损失的估计更为严格，并且运行时间明显更快。
到目前为止，该库仅支持 Connect-the-Dots 算法的悲观估计版本，该版本为 DP 算法的隐私损失提供了上限。但是，本文还介绍了该算法的变体，该变体提供了 PLD 的“乐观”估计，可用于推导DP 算法隐私成本的下限（前提是这些算法承认“最坏情况” PLD）。目前，该库确实支持 Privacy Buckets 算法给出的乐观估计，我们希望也能纳入 Connect-the-Dots 版本。
致谢
这项工作是与 Vadym Doroshenko、Badih Ghazi 和 Ravi Kumar 合作完成的。我们感谢 Galen Andrew、Stan Bashtavenko、Steve Chien、Christoph Dibak、Miguel Guevara、Peter Kairouz、Sasha Kulankhina、Stefan Mellem、Jodi Spacek、Yurii Sushko 和 Andreas Terzis 的帮助。
评论