Computationally tractable robust differentially private mean estimation

技术摘要：计算可行的鲁棒差分隐私均值估计

问题陈述
本文解决了在高维分布下同时满足两个约束条件的均值估计挑战：差分隐私（DP）和对离群值的鲁棒性。该设定涉及 $n$ 个在 $\mathbb{R}^d$ 中的向量样本，这些向量来自未知的椭圆分布 $\nu = EC(\mu, \Sigma, F)$，且该分布受到 $\eta$-污染。在此模型中，对手可以用任意值替换最多 $\lfloor \eta n \rfloor$ 个观测值，这些值可能依赖于原始样本。目标是在满足零集中差分隐私（zCDP）的同时，在重尾分布和对抗性污染的情况下，估计总体均值 $\mu$，并保持统计准确性。

该领域的现有方法面临显著的权衡。许多鲁棒隐私估计器依赖于计算密集型技术，如马尔可夫链蒙特卡洛（MCMC）、平方和松弛或基于梯度的优化，这使得它们在处理高维数据时变得不切实际。其他方法虽然高效，但往往依赖于近似差分隐私，或者在强隐私概念（如纯 DP 或零集中 DP）下缺乏鲁棒性保证。此外，许多现有方法需要难以解释或随维度扩展性较差的参数调节。

方法论：气球均值（The Balloon Mean）
作者提出了一种新的估计器——气球均值，它避免了复杂的优化子程序，转而采用简单的线性代数运算。该算法迭代运行，交替执行两个步骤：

1. 均值更新（投影与加噪平均）： 给定当前的中心估计值 $\tilde{\mu}_{m-1}$ 和半径 $\tilde{R}_{m-1}$，算法将所有数据点投影到马氏球 $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$ 上。然后计算这些投影的样本均值，并添加根据投影灵敏度（取决于半径）校准的高斯噪声。这产生了一个新的私有均值估计 $\tilde{\mu}_m$。
2. 气球更新（私有半径扩张）： 算法在新的估计值 $\tilde{\mu}_m$ 处“吹大”球体，直到它包含目标比例 $\tau_m$ 的数据。这是通过使用私有的 AboveThreshold 算法实现的。算法查询一系列由几何网格（$R_{min} + \beta^i - 1$）定义的半径，并私密地统计落在每个半径内的点数。算法会在第一个噪声计数超过对应于目标比例 $\tau_m$ 的噪声阈值的半径处停止。

该过程重复 $M$ 次。最终的估计值是投影到最终气球上的均值。该方法依赖于几个可解释的调节参数：初始半径、网格扩张因子 $\beta$、迭代次数 $M$ 以及目标比例 $\tau$。

核心贡献

1. 算法创新： 引入了气球均值，这是一种计算高效的估计器，通过迭代地识别包含大部分数据的马氏球来定位均值。它避免了 MCMC、平方和、以及梯度下降。
2. 理论保证： 本文为气球均值在重尾模型（仅存在二阶矩）和对抗性污染椭圆模型下提供了有限样本误差界。分析假设协方差矩阵 $\Sigma$ 是已知的（尽管作者指出可以代入鲁棒的私有 $\Sigma$ 估计值）。
3. 隐私与复杂度： 该估计器满足 $\rho$-零集中差分隐私（zCDP），并能自然扩展到纯 DP。其计算复杂度为 $O(d^3 + nd^2 + Mnd + Mn \log n)$，在标准假设下（$n > d$ 且 $M < \log n$）可简化为 $O(nd^2)$。

理论结果
主要理论结果（定理 4.4）确立了马氏距离误差 $|\tilde{\mu}_M - \mu|_\Sigma$ 的上界。以高概率，误差规模为：
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
其中 $\rho_-$ 是每次迭代分配的最小隐私预算。

• 重尾设定 ($\eta=0$)： 估计器达到了在对数因子意义下的极小极大（minimax）最优收敛速率。
• 对抗性污染 ($\eta > 0$)： 误差包含一个随 $\sqrt{d\eta}$ 缩放的项。作者指出，虽然现有的下界表明可能实现与 $\sqrt{\eta}$（独立于 $d$）相关的依赖关系，但目前的 $\sqrt{d}$ 依赖关系可能是结构性的，因为算法无法显式处理放置在高维壳层中的单方向污染物。他们承认这一差距，但强调目前尚无算法能同时实现最优的污染依赖性、强隐私性和计算效率。

实证评估
在不同维度（$d \in \{2, \dots, 128\}$）、样本量和隐私预算（$\rho \in \{0.01, 1\}$）下的广泛模拟证明了该方法的性能：

• 鲁棒性： 在污染和重尾设定下，气球均值的表现显著优于现有的计算可行私有估计器（如 COINPRESS、私有 Huber M-估计器和实例最优均值）。
• 参数敏感性： 该方法对初始均值猜测、初始半径和网格大小 $\beta$ 的敏感度较低。参数 $\tau$ 作为鲁棒性控制；较小的 $\tau$ 值（即不包含更多数据）在污染设定下能提高性能，但在干净设定下可能会略微增加误差。
• 迭代次数： 误差在 3–4 次迭代后趋于稳定，这表明在大多数实际应用中 $M=4$ 就足够了。

意义与主张
本文将气球均值定位为解决鲁棒性、隐私性和计算可行性这一“三难困境”的实用解决方案。作者声称，尽管该方法在对抗设定下可能无法达到理论上最优的污染依赖性（由于结构性限制），但它提供了一种独特的结合：

1. 计算简单性： 它可以在高维环境下实现，无需复杂的优化。
2. 强隐私性： 它满足 zCDP，这是一种比在鲁棒设定中常用的近似 DP 更强的隐私概念。
3. 统计最优性： 它在重尾设定下实现了极小极大速率，并在其他高效方法失效的污染设定下提供了鲁棒的表现。

作者总结道，对于涉及高维、潜在重尾且受污染数据的现实场景，气球均值是进行私有均值估计的可行工具，它在理论保证和实际可行性之间取得了平衡。