基于Gaussian Graphical Models的私有自适应协方差估计

# 基于高斯图模型的私有自适应协方差估计
来源：https://arxiv.org/html/2605.24295
Cecilia Ferrando Miguel Fuentes Brett Mullins Cameron Musco Daniel Sheldon 马萨诸塞大学阿默斯特分校信息与计算机科学学院

###### 摘要

我们提出**PACE-GGM**，一种数据自适应的差分隐私协方差估计方法，它将隐私预算集中在经验协方差矩阵信息量最大的元素上，而不是扰动所有元素。这适用于模型提供者为每个变量提供独立边界这一自然场景，使得单个元素可以用比完整矩阵更少的噪声来测量。在每一轮中，我们的方法选择一个近似较差的元素，使用高斯机制对其进行测量，然后通过最大熵重构目标重建完整的协方差矩阵，从而得到高斯图模型结构。在多样化的真实世界数据集上的实验表明，相对于高斯机制和其他基线方法，特别是在高维和低到中等隐私预算场景下，我们的方法在估计误差方面有一致的改进。

## 1 引言

协方差估计是统计学和机器学习中的一个基本原语，支撑着回归、主成分分析和多变量建模等任务。在涉及敏感数据的场景中，差分隐私（DP）为释放协方差估计值同时保护个体层面信息提供了一个严格的框架。私有协方差估计的一种经典方法是使用高斯机制，向维数据记录的维经验协方差矩阵的个不同元素添加噪声，其灵敏度根据对数据记录范数的假设界计算得出。这种方法由[13]首创，并作为许多其他算法的核心例程[26, 29, 1, 4, 18]。

然而，在许多应用中，假设*逐坐标*边界比假设完整数据记录范数的先验边界更为自然，并且在这种设置下，从隐私角度来看，测量单个元素可能比扰动整个矩阵便宜得多。例如，假设每个数据记录的第个坐标的幅度至多为1，则协方差矩阵单个元素的灵敏度比完整矩阵小一个因子，因此对于相同的隐私预算，可以比完整矩阵更精确地测量它。这一观察引发了一个自然的问题：我们能否设计一种算法，选择性地测量经验协方差矩阵的一个子集，并使用它们重建完整矩阵？选择性测量方法在差分隐私中广泛用于查询应答和合成数据生成，并且通常在实际的隐私预算下实现最先进的性能[20, 19, 2, 33, 8, 21, 14]。将此原理应用于协方差估计需要一种自适应选择程序和一种有原则的重建方法。

我们提出*基于高斯图模型的私有自适应协方差估计*（PACE-GGM），它迭代地选择最差近似的元素，通过高斯机制私下测量它们，并使用一种新的最大熵重建方法重建完整的协方差矩阵。这连接到Dempster[11]的经典协方差选择问题，从而产生具有稀疏精度矩阵的估计。经验上，PACE-GGM优于高斯机制和其他现有方法，其增益在高维或低到中等隐私预算场景下最为显著。

## 2 相关工作

#### 差分隐私协方差估计

私有协方差估计的经典方法是Dwork等人[13]引入的高斯机制：向经验协方差添加对称高斯噪声矩阵，噪声应用于所有元素，噪声规模仅通过全局灵敏度根据数据进行校准。在私有参数统计估计中，特别是线性回归[29]，相同的方法通常被称为“充分统计量扰动”（SSP），为简洁起见，我们常使用此名称。虽然简单且计算高效，但SSP本质上是数据无关的：无论元素的大小或重要性如何，都使用相同的噪声规模扰动每个元素，并且输出不能保证是正半定的（PSD）。

Biswas等人[4]提出了CoinPress，它建立在[16]的基础上，假设总体协方差有一个保守的先验谱界，并迭代地裁剪数据并缩小此界以降低灵敏度，但每次迭代仍然通过高斯机制私有化完整的矩阵。Wang和Xu[28]研究了高维稀疏场景并提出了DP-Thresholding：向经验协方差的所有元素添加高斯噪声，并在后处理中应用确定性硬阈值以利用真实协方差的假设稀疏性。隐私预算花费在完整矩阵上，稀疏性仅用于减少估计误差。Dong等人[12]提出了SeparateCov和AdaptiveCov，通过解耦特征值和特征向量估计，在高维场景下改进了SSP。AdaptiveCov进一步在两个不同的估计器之间进行最佳选择。尽管有结构上的分解，这两种算法仍然包含一个步骤来私有化完整的协方差矩阵，并且自适性是在估计器选择层面，而不是元素测量层面。

相比之下，PACE-GGM是第一个根据数据私下自适应选择要测量的元素的方法。通过将隐私预算集中在当前估计值近似最差的元素上，并通过最大熵重建恢复剩余元素，PACE-GGM避免了将预算花费在无法有效测量的元素上。

#### 高斯图模型与协方差选择

PACE-GGM核心的最大熵重建直接连接到高斯图模型的经典理论[17]。Dempster[11]表明，在精度矩阵上受固定稀疏模式约束的高斯分布的最大似然估计量，等价于中观测元素的最大熵PSD补全，且对于所有，自动为零。这就是*协方差选择*问题，其解已知为一个高斯图模型，其独立图由[17]确定。PACE-GGM将此经典框架扩展到私有自适应测量场景，其中算法使用指数机制私下迭代地选择，并观测带有高斯噪声的元素而非精确值。

## 3 背景

我们在有界DP模型下采用零集中差分隐私（zCDP）[6]，其中表示来自数据域的个记录的数据集。

###### 定义3.1（相邻数据集）。

如果两个数据集仅在一个记录上不同，则它们是*相邻*的。

###### 定义3.2（-zCDP [6]）。

一个随机化机制满足-zCDP，如果对于所有和所有，

其中是和分布之间的-雷尼散度。

###### 定义3.3（灵敏度）。

的灵敏度是。

###### 命题3.4（高斯机制 [6]）。

设是一个具有灵敏度的函数。机制满足-zCDP。

###### 命题3.5（指数机制 [22, 6]）。

设是一个具有灵敏度的质量分数。以与成正比的概率选择的机制满足-zCDP。

###### 命题3.6（组合与后处理 [6, 30]）。

如果满足-zCDP且满足-zCDP，则它们的（可能是自适应的）组合满足-zCDP。的任何后处理都满足-zCDP。

###### 引理3.7（zCDP到近似DP [6]）。

如果满足-zCDP，则对于任何，它满足-DP。

## 4 方法

### 4.1 问题设置与动机

#### 设置

假设我们有一个数据集，其中行对应于个体记录，用户提供的逐坐标边界对于每个可能的数据记录和坐标。用户必须使用领域知识保证这些边界，或者通过裁剪数据或丢弃违反它们的记录。如果为每个坐标提供了不同的边界，则可以将的列重新缩放以使用公共边界。我们专注于在-zCDP下估计经验二阶矩矩阵。在整个工作中，我们假设数据中心化（或者等价地，总体均值为零），因此与经验协方差矩阵一致。更一般地，我们可以私下估计均值并使用插件协方差估计量，但为了简单起见，我们省略此步骤。虽然我们专注于估计经验协方差，但在许多情况下，此类例程对于在统计模型下估计总体协方差也很有用，其中是总体协方差的自然估计量。

#### 选择性测量的动机

我们的逐坐标有界假设等价于边界。当特征独立有界时，这是很自然的，例如，具有裁剪或标准化属性的表格数据集、具有已知参考范围的测量值，或者每个特征被预处理以位于固定区间（重新缩放后映射到）的任何设置。在此设置下，单个元素的灵敏度是，而完整矩阵的灵敏度是（见附录A），因此对于相同的隐私预算，单个元素可以用比完整矩阵小一个因子的噪声标准偏差来测量。这激发了选择性地测量最重要元素子集的想法。

大多数先前的协方差估计方法假设数据有界。在这种情况下，单个元素的灵敏度与完整矩阵大致相同（与），因此测量元素子集似乎没有帮助。为了理解明显的不一致，假设建模者只知道并且需要推导出一个界。由于每个元素都可能具有幅度，最紧的界是：这为完整矩阵产生了相同的灵敏度，但现在为单个元素产生了一个松散的界。

总结来说，如果用户开始时只知道逐坐标边界，这是一个非常自然的设置，那么测量单个元素可以相对于测量完整矩阵节省隐私预算。然而，如果用户使用边界转换为边界，这种可能性可能会被掩盖。另一方面，如果用户确实知道一个紧的界，例如，其中比边界大很多——非正式地说，这要求预先知道不可能同时有很多元素很大——那么测量单个元素相比测量完整矩阵可能没有帮助。

### 4.2 PACE-GGM算法

我们提出的*基于高斯图模型的私有自适应协方差估计*（PACE-GGM）方法如算法1所示。PACE-GGM基于整个自适应查询发布和合成数据生成文献[20, 19, 2, 33, 8, 21, 14]中使用的*选择-测量-重建*范式，特别是基于AIM（*自适应迭代机制*），一种最先进的合成数据和边际查询应答方法[21]。PACE-GGM最初使用一部分隐私预算来测量的所有对角元素，并形成初始估计（算法2）。在整个算法中，它维护一组矩阵元素的带噪测量以及表示每个测量精度（逆方差）的值。