技术摘要：针对任意可子采样输入的二阶矩矩阵的隐私近似

问题陈述

本文研究了在高维空间（$\mathbb{R}^d$）中对数据集进行差分隐私（DP）二阶矩矩阵（等价于协方差矩阵）估计的问题。虽然估计此类矩阵是机器学习和统计学中的基础任务，但现有的 DP 方法通常依赖于严格的假设，例如输入数据需服从高斯分布或具有良好的条件数特征。

作者关注的是一种更通用的场景，即输入数据在不同轴向可能表现出显著的方差差异（大的条件数），并且可能包含离群点（outliers）。在这种情况下，标准的集中不等式往往会失效，传统的 DP 算法（例如依赖于每个点具有受限杠杆得分的算法）可能会产生极高的样本复杂度，或者如果离群点具有高杠杆率，则会完全失效。核心挑战在于：如何在不假设底层分布为高斯的条件下，针对满足特定结构属性的最坏情况输入，实现强大的隐私-效用权衡。

方法论

子采样性假设 (The Subsamplability Assumption)

其核心理论贡献是对 $(m, \alpha, \beta)$-subsamplability（可子采样性） 的形式化定义。一个数据集 $X$ 被定义为 $(m, \alpha, \beta)$-subsamplable，是指规模为 $m$（或更大）的随机子样本能够以至少 $1 - \beta$ 的概率，在 $(1 \pm \alpha)$ 的乘性因子范围内保持原始二阶矩矩阵 $\Sigma$ 的谱结构。

• 该假设比标准的矩阵集中不等式更弱，后者要求对于任何 $\alpha, \beta$，只要 $m$ 足够大即可实现这种保持。在此，作者仅要求存在某些特定的 $\alpha, \beta$ 以及对应的 $m$。
• 这一属性使得算法能够处理带有离群点的分布，前提是这些离群点不会在随机子样本中主导全局谱结构。

算法框架

作者提出了一个递归算法框架，该框架构建在 Kamath 等人 (2019) 的方法之上，但将其从高斯场景适配到了可子采样场景。该算法在 零集中差分隐私 (zCDP) 框架下运行。

1. 初始化： 算法假设输入在 $L_2$ 范数下受限于 $R$，且二阶矩矩阵 $\Sigma$ 满足 $I \preceq \Sigma \preceq R^2 I$。这是通过使用现有的 DP 工具来估计范围 $R$ 和最小特征值 $\lambda_{\min}$ 来实现的。
2. 递归预处理 (Recursive Preconditioning)：
   • 在每次迭代中，向经验二阶矩矩阵中添加噪声以确保隐私。
   • 算法识别出对应于大特征值（特征值 $\ge \psi \kappa$，其中 $\kappa$ 是当前的特征值上限）的子空间 $V$。
   • 应用线性变换 $\Pi$ 来将数据点在 $V$ 上的投影缩小一个因子 $\eta$（具体为 $\eta = 1/2$）。
   • 至关重要的是，与高斯情况中所有点均匀缩小不同，作者必须处理在变换后超出新界限的点的范数。他们定义了一个“尾部集合” $P_{tail}$，其中包含了违反子采样性界限的点。
   • 算法对 $P_{tail}$ 中的点应用收缩函数 $S$，以强制它们进入新的半径界限（$\sqrt{3/7}R$）。
3. 尾部分析 (Tail Analysis)： 分析证明，需要收缩的点属于 $P_{tail}$，而 $P_{tail}$ 仅占数据集的一小部分（约 $\beta/m$）。此外，移除或收缩这些点不会显著降低剩余“良好”数据的二阶矩矩阵的下界。
4. 终止： 递归持续进行，直到条件数 $\kappa$ 降低到常数水平（$O(m)$）。此时，仅需添加噪声即可实现 $(1 \pm \gamma)$ 近似。

基准对比

论文使用 子采样并聚合 (Subsample-and-Aggregate) 框架（Nissim 等人, 2007）结合 Ashtiani & Liaw (2022) 的凸半度量空间技术建立了一个基准。该基准提供 $(1 \pm 2\alpha)$ 近似，但在处理离群点时需要显著更高的样本复杂度。

核心贡献与结果

1. 针对可子采样输入的递归算法： 作者提出了一个递归算法，能够为任何 $(m, \alpha, \beta)$-subsamplable 输入实现二阶矩矩阵的 $(1 \pm \gamma)$ 近似。该算法满足 $\rho$-zCDP。
2. 处理离群点： 该方法被证明对一定比例的离群点具有鲁棒性。具体而言，对于由良态分布 $D$ 和 $\eta$ 比例的离群点组成的混合分布，只要离群点的二阶矩矩阵满足 $\Sigma_{out} \preceq O(1/\eta)\Sigma_D$，算法即可成功。
3. 改进的样本复杂度：
   • 对于一般分布（包括重尾分布），所提算法实现的样本复杂度约为 $\tilde{O}\left(\frac{d}{\gamma^2} + \frac{d^{3/2}}{\gamma\sqrt{\rho}}\right)$。
   • 相比之下，子采样并聚合基准需要 $\tilde{O}\left(\frac{d^2}{\epsilon \gamma^3}\right)$，这明显更高，尤其是在存在离群点的情况下，基准对离群点比例 $\eta$ 的要求也更为严格（基准为 $\eta = O(1/m)$，而本文方法容忍度更高）。
4. 子采样性的形式化： 论文提供了子采样性的严谨定义，并展示了它如何作为控制尾部行为的有效代理，而无需严格的高斯假设。

重要性与主张

作者声称，其工作弥合了针对良态（高斯）输入的隐私估计与针对更具挑战性的、可能具有重尾特征及离群点的通用分布之间的差距。

• 鲁棒性： 该算法专为具有大条件数的二阶矩估计场景而设计。在这些场景下，以往的方法（如 Brown 等人, 2023）如果离群点与小特征值方向相关，可能会产生显著误差。
• 更弱的假设： 通过依赖子采样性而非统一的杠杆得分界限，该方法可以容忍多个离群点的存在，只要这些离群点不会主导随机子样本的整体谱结构。
• 效用： 论文表明，即使在输入范围显著大于最小特征值的场景下（这是标准 DP 技术通常难以应对的场景），也能实现强效用保证（任意 $(1 \pm \gamma)$ 近似）。

作者明确指出，虽然其分析需要一个依赖于范围 $R$ 的 $\beta$ 参数界限，但这是处理带有离群点的良态分布的一种权衡。他们指出，将此依赖关系替换为 $O(1)$ 界限是一个有趣的研究课题。该工作并未提出在真实世界数据集上的实验验证，而是为包括截断帕累托分布和凸椭球上的均匀分布在内的特定分布模型提供了理论保证和样本复杂度界限。