技术摘要：用于回归与聚类的差分隐私非参数模态学习

问题陈述

密度模态（即概率密度函数的局部极大值点）的估计是统计学中的一个基本问题，它为复杂的、多峰值的分布提供了局部化且具有解释性的总结。与全局总结（如均值或中位数）不同，模态揭示了异质的子群体，在从聚类、分类到计算机视觉等广泛的应用领域中至关重要。然而，恢复模态本质上是非正则的；密度的微小扰动可能会产生或消除临界点，这使得估计过程对局部平滑度、曲率和分离度非常敏感。

尽管在差分隐私（DP）均值、回归和聚类方面已有大量研究，但隐私模态估计（private mode estimation）在很大程度上仍未被探索。现有的方法（例如 Pacchiano 等人于 2021 年提出的基于最近邻的方法）仅限于单模态设置，或者缺乏依赖于平滑度的最优性保证。本文旨在解决从敏感数据中恢复多个密度模态的挑战，并提供严格的 $(\varepsilon, \delta)$-差分隐私保证。

方法论：DP-GRAMS

作者提出了 DP-GRAMS（差分隐私梯度上升寻模算法），这是一个将经典的均值漂移（mean-shift）程序适配到差分隐私环境下的多阶段算法。该方法利用了均值漂移与对数密度（得分函数）上的梯度上升之间的等价性。

1. 稳定得分估计

为了确保隐私，算法并不直接作用于原始的对数密度梯度 $\nabla \log \hat{p}(x)$，因为后者对极端观测值可能高度敏感。相反，它采用了一种稳定的得分估计器：
$$\hat{s}_{A, p_{floor}}(x) = \frac{\text{clip}_A(\nabla \hat{p}(x))}{\max\{\hat{p}(x), p_{floor}\}}$$
其中 $\hat{p}(x)$ 是核密度估计（KDE）。分子被裁剪至水平 $A$ 以限制敏感度，分母则在 $p_{floor}$ 处进行下限截断，以防止除以接近零的值。

2. 三阶段流水线

该算法分为三个不同的阶段进行：

• 密度感知隐私（DAP）初始化：
  寻找模态需要良好的初始化。作者引入了一种 DAP 方案，从公共网格中采样初始点。它使用指数机制，其效用函数基于局部经验质量（近似局部密度）。关键在于，它采用了局部抑制规则：在选择一个锚点后，所有位于半径 $\rho_{init}$ 范围内的网格点都会从候选集中移除。这确保了对高密度区域（模态盆地）的多样化覆盖，而不会重复选择同一个邻域，从而以 $k \asymp M \log n$ 次抽取实现对所有真实模态的高概率覆盖。

• 相关噪声梯度上升：
  从每个初始化点出发，算法在稳定的得分估计器上执行随机梯度上升。为了满足隐私要求：

  • 梯度裁剪： 得分贡献被进行裁剪。
  • 相关噪声： 由于多个轨迹从不同点开始但可能收敛到同一个模态，如果为每个轨迹添加独立的噪声，将会产生难以承受的隐私成本。因此，DP-GRAMS 在每次迭代中添加相关高斯噪声。这种相关结构是由基于当前迭代点空间邻近性的指数核诱导的。这使得在单一隐私预算下联合发布多个轨迹成为可能。

• 合并：
  最后一步是将上升轨迹产生的附近候选模态进行合并。如果模态数量未知，则使用基于半径的合并；如果已知，则应用 Ward 联动层次聚类。这一后处理步骤是确定性的，不消耗额外的隐私预算。

3. 扩展

该框架被扩展到两个下游任务：

• DP-PMS： 一种私有模态回归方法，通过在响应方向进行更新来估计条件模态。
• DP-GRAMS-C： 一个聚类流水线，释放私有模态中心并将数据点进行确定性分配。

理论贡献

在真实密度局部属于平滑参数为 $\beta > 2$ 的 Hölder 类假设下，本文建立了严格的统计与隐私保证。

隐私保证

完整的 DP-GRAMS 流水线满足 $(\varepsilon, \delta)$-差分隐私。隐私预算在初始化阶段 ($\varepsilon_{init}$) 和上升阶段 ($\varepsilon_{modes}$) 之间进行分配。使用指数机制进行初始化以及使用相关高斯机制进行上升，确保了隐私成本随模态数量和迭代次数高效缩放。

误差率与最优性

作者推导了估计模态的均方误差（MSE）上界。误差率的形式为：
$$O\left( \left(\frac{\log n}{n}\right)^{\frac{2(\beta-1)}{d+2\beta}} \right) + O\left( \left(\frac{\text{polylog}(n, \delta)}{n^2 \varepsilon^2}\right)^{\frac{\beta-1}{d+\beta}} \right)$$

• 第一项代表非隐私统计误差，符合已知的模态估计极小极大率（例如 Tsybakov, 1990）。
• 第二项捕捉了由于隐私约束导致的性能退化。

此外，本文推导了私有模态估计的极小极大下界，表明所提估计器是近乎极小极大最优的（在 MSE 意义上，仅差对数因子）。这是一个重要的结果，因为它证明了只要密度足够平滑，隐私成本不会从根本上改变对样本量 $n$ 和维度 $d$ 的收敛率依赖关系。

实验结果

在合成数据集和真实世界数据集上的广泛实验验证了理论发现：

• 合成数据： 在二元高斯混合模型和重尾 $t$-混合模型上，DP-GRAMS 成功恢复了多个模态。隐私-效用权衡曲线显示，随着样本量 $n$ 和隐私预算 $\varepsilon$ 的增加，该方法在性能上能与非隐私均值漂移法相媲美。
• 模态回归： 在正弦和分段常数混合数据上，私有模态回归（DP-PMS）成功追踪了均值方法（如 LOWESS）无法捕捉的多模态条件结构。
• 聚类： 在 MNIST 和癌症 RNA-Seq 数据集上，DP-GRAMS-C 在中等隐私预算下，其调整兰德指数（ARI）和归一化互信息（NMI）的表现优于差分隐私 $k$-means（DP-$k$-Means）。该方法有效地保留了高维降维空间的聚类几何结构。

意义与主张

本文声称提供了第一个针对差分隐私非参数模态估计的全面框架，该框架：

1. 处理多个模态： 不同于以往侧重于单模态或最近邻方法的研究，该方法旨在恢复一组分离的模态。
2. 实现近乎最优性： 通过利用高阶核并结合平滑度 ($\beta > 2$)，该方法实现了近乎极小极大最优的误差率，克服了无法利用高阶平滑性的最近邻估计器的局限性。
3. 实用的隐私机制： 引入 DAP 初始化和相关噪声机制，为“获取精细数据分布（以寻找模态）”与“保护个体数据点（隐私需求）”之间的矛盾提供了切实可行的解决方案。
4. 下游效用： 该框架自然地扩展到模态回归和聚类，为隐私约束下的非参数任务提供了一个统一的方法。

作者总结道，尽管由于临界点的非正则性质，模态估计问题具有挑战性，但所提出的 DP-GRAMS 算法提供了一个统计上可靠且在实践中可实现的解决方案，并具有良好的隐私-效用权衡。