Statistical Properties of Nonparametric MLE under Laplace Noise

论文技术摘要：拉普拉斯噪声下的非参数极大似然估计（NPMLE）统计性质

问题陈述

本文研究了从局部差分隐私（LDP）观测中恢复未知潜在分布 $g_0$ 的问题。在 LDP 设置下，单个数据点 $\theta_i$ 在发布前通过加性拉普拉斯机制进行隐私化处理：$X_i = \theta_i + Z_i$，其中 $Z_i \sim \text{Lap}(0, b)$。分析师仅能观测到私有化后的样本 $X_1, \dots, X_n$，这些样本是从潜在分布与拉普拉斯核的卷积中抽取的。

这一设置构建了一个反卷积问题，其目标是对 $g_0$ 进行非参数估计。研究中识别出的核心矛盾是隐私与效用之间的权衡：更强的隐私（更大的噪声尺度 $b$）使得卷积的反转变得更不稳定，从而增加了恢复潜在分布的难度。本文重点研究了该问题的非参数极大似然估计（NPMLE），特别是分析了其计算可处理性以及在 1-Wasserstein 距离下的统计收敛速率。

研究方法

1. 计算重构（支撑集缩减）
作者首先解决了在概率测度空间 $\mathcal{P}([-a, a])$ 上进行 NPMLE 优化的无限维问题。

• 支撑集特征化： 利用拉普拉斯核的特定形状（在原点处不可微，且在 $(0, \infty)$ 上严格凸且递减），作者证明了任何 NPMLE 解的支撑集必须包含投影到潜在域 $[-a, a]$ 上的观测值集合。
• 有限维缩减： 这一结果将优化问题从在所有混合分布中搜索，简化为对 $n$ 个投影观测值分配的混合权重进行的严格凸优化。
• 算法： 基于此缩减，作者提出了一种期望最大化（EM）算法（算法 1），该算法迭代更新固定支撑点的权重，保证收敛至缩减对数似然函数的唯一全局最大值。

2. 统计分析（反卷积不等式）
为了分析收敛速率，作者开发了一种专门针对拉普拉斯机制的反卷积不等式。

• 度量指标： 估计误差使用 1-Wasserstein 距离 ($W_1$) 来衡量，这是因为即使 $g_0$ 是连续的，NPMLE 仍然是离散的。
• 反转论证： 通过借鉴先前工作（特别是 [30]）中的频率分割策略，作者推导出了私有化密度估计的 $L_1$ 误差（$\|m_g - m_{g_0}\|_1$）与 $W_1(g, g_0)$ 之间的界限。
• 显式依赖关系： 推导出的不等式明确追踪了对噪声尺度 $b$ 和支撑半径 $a$ 的依赖关系。它涉及平衡平滑偏差项与高频项，从而得出优化的带宽选择。

3. 收敛速率
作者将反卷积不等式与通过凸类极大似然论证得到的私有化密度的 Hellinger 收敛速率相结合，从而确立了潜在分布的 NPMLE 收敛速率。

关键结果

1. 噪声增长下的相合性
本文证明了即使当隐私噪声水平 $b_n$ 随样本量 $n$ 增加时，NPMLE 仍保持相合性。

• 充分条件： 如果噪声尺度增长速度慢于 $n^{3/16}(\log n)^{-1/2}$，则估计量是相合的（即 $W_1(\hat{g}_n, g_0) \xrightarrow{P} 0$）。
• 收敛速率： 对于固定的 $a$ 和 $b$，收敛速率为 $O_p(n^{-3/16}\sqrt{\log n})$。当 $b_n$ 增长时，速率由涉及 $b_n n^{-3//16}\sqrt{\log n}$ 的项主导。

2. 不可能结果（逆命题）
作者提供了一个下界，展示了在高噪声下的恢复极限。

• 不可能区域： 如果噪声尺度 $b_n$ 以 $\Omega(\sqrt{n})$ 的速率增长（等价于隐私预算 $\epsilon_n$ 比 $n^{-1/2}$ 衰减更快），则没有任何基于私有化样本的估计量能在有界分布类 $\mathcal{P}([-a, a])$ 上实现一致性。
• 这建立了一个关于相合性充分条件（$n^{3/16}$）与不可能性的必要条件（$n^{1/2}$）之间的清晰差距。

3. 经验发现
数值实验验证了理论上的缩放行为：

• 误差行为： 1-Wasserstein 误差随样本量 $n$ 的增加以及隐私预算 $\epsilon$ 的增加而减小。
• 支撑集大小： 与已知 NPMLE 支撑集大小为 $O(\log n)$ 的高斯混合模型不同，在测试范围内，拉普拉斯混合模型的经验活跃支撑集随 $n$ 呈多项式级增长（快于对数级）。
• 噪声缩放： 实验确认，当噪声增长指数 $\alpha$（其中 $b_n \propto n^\alpha$）超过 $3/16$ 时，收敛速度会变慢；而在 $\alpha = 1/2$ 时，误差不再衰减，这与不可能结果相吻合。

意义与主张

本文声称提供了第一个用于从拉普拉斯私有化连续数据中恢复潜在分布的似然框架，并明确表征了隐私-效用权衡。

• 计算贡献： 通过证明支撑集被限制在投影观测集内，解决了拉普拉斯噪声下 NPMLE 的计算难解性问题，从而实现了高效的 EM 算法。
• 统计贡献： 在 1-Wasserstein 距离下推导了 NPMLE 的显式收敛速率，将恢复速率直接与隐私噪声尺度联系起来。
• 理论极限： 确定了一个特定的区域（$n^{3/16}$ 对比 $n^{1/2}$），在该区域内可以实现一致性恢复与不可能恢复之间的区分，强调了局部差分隐私的统计代价。

作者指出，虽然其分析缩小了“存在一致估计量”与“不可能实现”之间的差距，但 $n^{-3/16}$ 与 $n^{-1/2}$ 之间的精确最优速率仍是一个开放性问题。此外，他们强调拉普拉斯噪声下的 NPMLE 支撑集行为与高斯情况有着本质的不同，这表明了似然函数具有截然不同的几何特性。