我们研究了差分隐私下的二阶矩阵估计问题，并提出了一种新的算法，该算法在数据的子样本可采样性假设下，即使在最坏情况下也能实现强隐私与效用的权衡。我们称输入为 $(m,\eta,\eta)$-子可采样，如果大小为 $m$（或更大）的随机子样本以概率 $\text{w.p} \geq 1-\eta$ 保留原始二阶矩阵的谱结构，且误差乘以因子 $1\pm\eta$。
基于子可采样性，我们给出了一种递归算法框架，类似于 Kamath 等人 2019 年的方法，遵循零集中差分隐私（zCDP），同时以高概率保持二阶矩估计的准确性，允许任意因子 $(1\pm\eta)$ 的误差。接下来，我们展示了如何将该算法应用于近似分布 $\text{D}$ 的二阶矩阵，即使输入中存在显著比例的离群值。
博主点评： 本文提出的算法在差分隐私和二阶矩估计之间找到了良好的平衡，尤其适用于数据中存在离群值的情况。这一研究为实现高隐私性的统计估计提供了新的思路，具有广泛的应用潜力。算法的递归框架也为后续研究提供了良好的基础。