保持稀疏性的差分隐私训练

大型嵌入模型已成为推荐系统 [ 1 , 2 ] 和自然语言处理 [ 3 , 4 , 5 ] 中各种应用的基本工具。此类模型通过使用嵌入层将具有大词汇量的分类或字符串值输入属性映射到固定长度的表示向量，从而将非数值数据集成到深度学习模型中。这些模型广泛应用于个性化推荐系统，并在语言建模、情感分析和问答等语言任务中取得了最先进的性能 。在许多这样的场景中，隐私是部署这些模型时同样重要的特性。因此，人们提出了各种技术来实现隐私数据分析。其中，差异隐私（DP）是一种被广泛采用的定义，它限制个人用户信息的暴露，同时仍允许分析人口级别的模式。

对于训练具有 DP 保证的深度神经网络，最广泛使用的算法是DP-SGD（DP随机梯度下降）。DP-SGD 的一个关键组成部分是在训练期间向梯度向量的每个坐标添加高斯噪声。然而，当应用于大型嵌入模型时，这会带来可扩展性挑战，因为它们依赖梯度稀疏性进行高效训练，但向所有坐标添加噪声会破坏稀疏性。

为了缓解这种梯度稀疏性问题，我们在“大型嵌入模型的稀疏性保留差异隐私训练”（将在NeurIPS 2023上展示）中提出了一种称为自适应过滤稀疏训练(DP-AdaFEST) 的新算法。从高层次上讲，该算法通过仅选择在每次迭代中添加噪声的特征行子集来保持梯度的稀疏性。关键是使此类选择具有差异隐私性，以便在隐私成本、训练效率和模型效用之间实现三方平衡。我们的实证评估表明，与标准 DP-SGD 产生的密集梯度相比，DP-AdaFEST 实现了明显更稀疏的梯度，梯度大小减少了 10 5倍以上，同时保持了相当的准确度水平。这种梯度大小的减少可以转化为 20 倍的挂钟时间改进。

概述

为了更好地理解梯度稀疏性问题所面临的挑战和解决方案，我们首先来概述一下 DP-SGD 在训练过程中的工作原理。如下图所示，DP-SGD 的工作原理是剪裁当前随机样本子集（称为小批量）中每个示例的梯度贡献，并在随机梯度下降(SGD)的每次迭代中将坐标高斯噪声添加到平均梯度中。DP-SGD 已证明其在保护用户隐私的同时，在各种应用中保持模型效用 [ 6 , 7 ] 。

DP-SGD 工作原理的说明。在每个训练步骤中，都会抽取一小批示例，并用于计算每个示例的梯度。这些梯度通过高斯噪声的裁剪、聚合和求和进行处理，以产生最终的私有化梯度。

将 DP-SGD 应用于大型嵌入模型的挑战主要来自 1) 非数字特征字段，例如用户/产品 ID 和类别，以及 2) 通过嵌入层转换为密集向量的单词和标记。由于这些特征的词汇量，该过程需要具有大量参数的大型嵌入表。与参数数量相比，梯度更新通常非常稀疏，因为每个小批量示例仅激活一小部分嵌入行（下图可视化了不同批量大小下梯度的零值坐标比率，即稀疏性）。这种稀疏性在有效处理大规模嵌入训练的工业应用中得到了充分利用。例如，Google Cloud TPU是一种定制设计的 AI 加速器，针对大型 AI 模型的训练和推理进行了优化，具有专用 API来处理具有稀疏更新的大型嵌入。与在 GPU 上进行训练相比，这显著提高了训练吞吐量，因为当时 GPU 还没有针对稀疏嵌入查找进行专门的优化。另一方面，DP-SGD 完全破坏了梯度稀疏性，因为它需要向所有坐标添加独立的高斯噪声。这为大型嵌入模型的私人训练设置了障碍，因为与非私人训练相比，训练效率会显著降低。

在Criteo pCTR模型中嵌入梯度稀疏度（零值梯度坐标的分数）（见下文）。该图报告了桶数最多的前五个分类特征（总共 26 个）的梯度稀疏度（平均超过 50 个更新步骤），以及所有分类特征的稀疏度。随着更多示例命中嵌入表中的更多行，稀疏度会随着批次大小而降低，从而产生非零梯度。但是，即使对于非常大的批次大小，稀疏度也高于 0.97。这五个特征都一致遵循这种模式。

算法

我们的算法是通过扩展标准 DP-SGD 来构建的，每次迭代时都会添加一个额外的机制来私下选择“热门特征”，这些特征是由当前小批量中的多个训练示例激活的特征。如下所示，该机制分为几个步骤：

计算每个特征桶中贡献了多少个示例（我们将分类特征的每个可能值称为“桶”）。

通过限制计数来限制每个示例的总贡献。

在每个特征桶的贡献计数中添加高斯噪声。

仅选择计数高于给定阈值（稀疏性控制参数）的特征以包含在梯度更新中，从而保持稀疏性。此机制是差分隐私的，隐私成本可以通过将其与标准 DP-SGD 迭代组合来轻松计算。

算法在具有 20 个存储桶的合成分类特征上的过程说明。我们计算对每个存储桶有贡献的示例数量，根据每个示例的总贡献（包括对其他特征的贡献）调整值，添加高斯噪声，并仅保留那些噪声贡献超过（噪声）梯度更新阈值的存储桶。

理论动机

我们将 DP-AdaFEST 视为使用随机梯度预言机进行优化，以此提供其理论动机。理论环境中随机梯度下降的标准分析将模型的测试误差分解为“偏差”和“方差”项。DP-AdaFEST 的优势可以看作是以略微增加偏差为代价来降低方差。这是因为与 DP-SGD（会将噪声添加到所有坐标）相比，DP-AdaFEST 会将噪声添加到较小的坐标集。另一方面，DP-AdaFEST 会给梯度引入一些偏差，因为嵌入特征上的梯度会以一定的概率被丢弃。感兴趣的读者可以参阅本文第 3.4 节了解更多详细信息。

实验

我们在公共数据集上通过大型嵌入模型应用评估了我们算法的有效性，其中包括一个广告预测数据集（Criteo-Kaggle）和一个语言理解数据集（SST-2）。我们使用带有指数选择的 DP-SGD作为基线比较。

DP-AdaFEST 的有效性在下图中显而易见，它在保持相同效用水平（即，仅有最小的性能下降）的同时，实现了比基线明显更高的梯度尺寸减小（即，梯度稀疏性）。

具体来说，在 Criteo-Kaggle 数据集上，DP-AdaFEST 将常规 DP-SGD 的梯度计算成本降低了 5x10 5倍以上，同时保持了可比的AUC（我们将其定义为损失小于 0.005）。这种降低意味着训练过程更加高效且更具成本效益。相比之下，如下面绿线所示，基线方法无法在如此小的效用损失阈值内实现合理的成本降低。

在语言任务中，减小梯度大小的潜力并不大，因为使用的词汇通常较小且已经非常紧凑（如下图右侧所示）。但是，采用稀疏性保留的 DP-SGD 有效地避免了密集梯度计算。此外，根据理论分析中提出的偏差-方差权衡，我们注意到，当梯度大小的减小最小时，DP-AdaFEST 偶尔会比 DP-SGD 表现出更好的效用。相反，当结合稀疏性时，基线算法在保持效用方面面临挑战。

比较 DP-AdaFEST（我们的算法）和基线算法（具有指数选择的 DP-SGD）在 ε =1.0 下实现的最佳梯度大小缩减（常规 DP-SGD 和稀疏性保持算法之间的非零梯度值计数比率），并与不同效用差异阈值下的 DP-SGD 进行比较。曲线越高，表示效用/效率权衡越好。

实际上，大多数广告预测模型都在不断进行训练和评估。为了模拟这种在线学习设置，我们还使用时间序列数据进行评估，由于非平稳性，这些数据非常具有挑战性。我们的评估使用 Criteo -1TB数据集，该数据集包含 24 天内收集的真实用户点击数据。DP-AdaFEST 始终将常规 DP-SGD 的梯度计算成本降低 10 4倍以上，同时保持可比的 AUC。

比较 DP-AdaFEST（我们的算法）和采用指数选择的 DP-SGD（以前的算法）在 ε =1.0 下实现的最佳梯度尺寸减小，并与不同阈值下的 DP-SGD 进行比较，以了解效用差异。曲线越高，表示效用/效率权衡越好。DP-AdaFEST 的表现始终优于以前的方法。

结论

我们提出了一种新算法 DP-AdaFEST，用于在差分隐私训练中保持梯度稀疏性——特别是在涉及大型嵌入模型的应用中，这是推荐系统和自然语言处理中各种应用的基本工具。我们的算法在保持真实基准数据集准确性的同时，显著减少了梯度大小。此外，它通过稀疏控制参数提供了平衡效用和效率的灵活选项，而我们的提案提供了更好的隐私效用损失。

致谢

这项工作是与 Badih Ghazi、Pritish Kamath、Ravi Kumar、Pasin Manurangsi 和 Amer Sinha 合作完成的。