Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

技术摘要：超越局部差分隐私的私有机制之 Dobrushin 系数

问题陈述
本文探讨了使用局部差分隐私（LDP）作为衡量离散马尔可夫核（隐私机制）隐私程度指标时的局限性。虽然 LDP 被广泛采用，但作者指出存在两个主要问题：

1. 过度限制性： 在参数估计等统计应用中，为了实现严格的 LDP 保障（较小的 $\epsilon$），可能会导致估计性能（极小极大风险）出现极端的退化。
2. 在零概率情况下的反直觉行为： 标准 LDP 定义规定，如果机制对于给定的输入分配了零概率（即 $K_{Y|X=x}(y) = 0$），则会产生无穷大的隐私成本。这使得某些具有显著随机性的机制（例如本文示例中的 $K_1$）与恒等映射或平凡机制（例如 $K_2$）在 LDP 框架下被视为具有相同的隐私泄露水平，即便两者都包含零项，也无法区分“噪声化”行为与“确定性”行为在隐私泄露方面的差异。

为了解决这些问题，作者研究了针对满足**逐点最大泄露（Pointwise Maximal Leakage, PML）**而非严格 LDP 的机制的 Dobrushin 系数（全变差距离的收缩系数）。PML 是最大泄露的一种逐点适配版本，它依赖于数据分布 $P_X$。作者特别分析了输入分布 $P_X$ 具有不低于常数 $c$ 的最小概率质量（即 $\min_x P_X(x) \geq c$）的机制。该框架允许分析那些在 LDP 下会被视为“无限隐私”（或无限泄露）的具有零概率赋值的机制。

方法论
本文利用信息论工具推导了通过隐私机制后的 $f$-散度收缩界限。

• 定义： 作者定义了 $(\epsilon, c)$-PML 约束，即对于所有属于集合 $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$ 的输入分布，$PML$均受限于$\epsilon$。这推广了 LDP，因为 LDP 对应于 $c \to 0$ 的极限。
• 收缩系数： 研究的核心对象是 Dobrushin 系数 $\eta_{TV}(\epsilon, c)$，其定义为在满足 $(\epsilon, c)$-PML 的所有核函数下，全变差（TV）距离收缩的最大值。
• 简化为二元输出： 作者证明，要找到最大的 Dobrushin 系数，只需考虑输出空间为二元（$|Y|=2$）的机制。这显著简化了优化问题。
• 不等式： 推导过程利用了 Binette 不等式（Reverse Pinsker 不等式的推广），将 TV 界限扩展到一般的 $f$-散度（如相对熵和 Hellinger 散度）。

核心贡献与结果

1. 可实现的 Dobrushin 系数界限：
   本文为任何满足 $(\epsilon, c)$-PML 的核函数推导出了紧致的上界 $\eta_{TV}(\epsilon, c)$。该界限为：
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   其中 $N$ 是输入字母表的大小。

• 区间分析： 作者表明，如果 $\epsilon \geq \log(2/Nc)$，则收缩系数为 1（不发生收缩）。如果 $\epsilon < \log(2/Nc)$，则系数严格小于 1，表明存在隐私诱导的收缩。
• 恢复 LDP： 当 $c \to 0$ 时，该界限恢复了已知的 $\epsilon$-LDP 结果：$\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$。
• 机制构建： 本文提供了实现这些界限的具体机制构建方法（特别是二元输出机制），证明了这些界限是可达的。

2. 向一般 $f$-散度的扩展：
   利用 Binette 不等式，作者将 TV 界限扩展到了一般的 $f$-散度。他们推导了在 $(\epsilon, c)$-PML 约束下，相对熵和 Hellinger 散度的强数据处理不等式（SDPI）。这些界限取决于 TV 收缩因子和输出分布的极端比例。

3. 对极小极大风险的应用：
   推导出的界限被应用于私有极小极大估计风险。利用 Le Cam 两点法和 $f$-散度的张量化性质，作者表明，为了达到特定风险水平所需的样本复杂度，会按与私有 Dobrushin 系数倒数成比例的因子增加。具体而言，如果系数为 1，样本复杂度与非私有设置一致；如果系数小于 1，有效样本量则会减少。

意义与主张
本文声称提供了一个比单纯 LDP 更细致的框架来分析隐私机制。通过引入参数 $c$，作者可以量化包含零概率项的机制的隐私泄露，而这些机制在标准 LDP 下会被排除或被视为病态。

• 更紧致的界限： 对于满足 LDP 的机制，当输入分布已知其最小质量为 $c$ 时，所提出的界限比以往的结果更紧致且更具适应性。
• 超越 LDP： 该框架将收缩系数的分析扩展到了整个离散核类，包括那些不满足任何有限 LDP 保障的核。
• 操作解释： 研究结果将理论收缩系数直接与统计估计性能的退化联系起来，为量化隐私带来的“代价”（以增加的风险或样本复杂度形式体现）提供了工具。

作者强调，其工作在恢复现有 LDP 结果作为特例的同时，提供了从均匀分布约束到全 LDP 机制的连续插值，从而解决了 LDP 在特定统计语境下的“过度限制性”问题。