Better Privacy Guarantees for Larger Groups

技术摘要：针对更大规模群组的更优隐私保证

问题陈述
本文探讨了由 Pujol 和 Desfontaines [2023] 提出的一个开放性问题，即关于固定且不相交群组的隐私直方图设计。标准的差分隐私机制通常会对每个计数添加固定幅度的噪声，这提供了统一的绝对隐私，但导致大群组与小群组相比，其相对误差显著减小。核心问题在于，是否可以“差异化地分配”这种多余的准确度：允许群组的误差与其计数（$x_i$）成比例缩放，从而为成员规模更大的群组提供更强的隐私保证（更小的隐私预算）。

本文在**“增加或移除一个”（add-or-remove-one）邻近模型下研究此问题。目标是找到一种机制，使得隐私预算 $v(n)$ 仅取决于群组计数 $n$，且 $v(n)$ 是非增的，并满足计数依赖型群组级零集中差分隐私（zCDP）**。这要求在所有阶数 $\alpha > 1$ 下，对相邻数据集之间的双向 Rényi 散度进行限制。

一个关键的技术障碍是零值处的边界条件。原始公式要求期望绝对误差严格小于 $r x_i$。当 $x_i = 0$ 时，这意味着 $E|\hat{x}_i| < 0$，这在数学上是不可能的。此外，如果将不等式放宽为 $\leq$，同时保持在 $0 \leftrightarrow 1$ 边上的有限双向 Rényi 散度，则会导致矛盾（迫使计数为 1 时的输出变为确定性的，从而违反误差界限）。

方法论与修复后的公式
为了解决边界问题，作者提出了一个“修复后”的效用要求：
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
这在保持所有正计数满足相对误差目标的同时，在零值处引入了一个固定的绝对容差，使问题变得可行。

本文采用了两种主要的算法路径：

1. 可行性（上界）： 作者专门化了一个现有的“偏移变换”（shifted-transformation）框架（Finley 等人 [2026]）。他们通过带有偏移量 $c$ 的对数函数（即 $\log(x_i + c)$）对计数空间进行变换，添加固定方差的高斯噪声，并在指数化和截断前应用确定性漂移。

   • 核心创新： 与使用 $-\sigma^2/2$ 漂移以确保均值无偏的标准对数正态机制不同，该机制使用了 $-\sigma^2$ 漂移。选择这一特定漂移是为了最小化期望绝对乘性误差，这与本文的效用指标相一致。
   • 隐私机制： 通过在对数空间中处理等方差问题，该机制确保了相邻计数之间的 Rényi 散度对于所有阶数 $\alpha$ 都是有限的，从而避免了因方差不等导致的“尾部阻碍”（即在某一方向上导致无限散度）问题。

2. 不可行性（下界）： 作者证明，任何满足修复后的效用要求和计数依赖型 zCDP 要求的机制，其隐私预算衰减速率都不可能快于计数的平方倒数。

   • 两计数论证： 通过对两个特定计数进行测试，确立了 $n^{-2}$ 指数。
   • 多计数论证： 通过利用一个“隐藏偏移”随机变量以及信息论论证（将期望绝对误差与互信息联系起来），作者推导出了关于隐私预算领先系数的更紧的下界。

关键结果

• 最优渐近速率： 对于任何固定的 $0 < r < 1$，最优隐私预算 $v(n)$ 以 $\Theta_r(n^{-2})$ 的速率衰减。

  • 上界： 偏移对数高斯机制实现了 $v(n) = O_r(n^{-2})$。具体而言，当 $n \to \infty$ 时，$v(n) \approx \frac{1}{2\sigma^2 n^2}$。
  • 下界： 任何满足要求的机制都必须满足 $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$。这证实了平方倒数速率是内在的，而非构造过程中的人工产物。

• 领先系数： 本文缩小了在 $r$ 趋于极小且 $n$ 极大时，最优系数 $C^*$ 的最佳上界与下界之间的差距：
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  这两个界限之间的比例约为 2.995，表明两者在三倍因子以内，说明界限已非常接近。

• 不等方差高斯的失效： 本文证明，一个朴素的机制（发布 $N(n, r^2 n^2)$，即方差随计数平方变化的高斯分布）无法满足 zCDP 定义。虽然它具有正确的误差规模，但相邻计数之间不等方差会导致在足够高的阶数 $\alpha$ 下，其中一个方向的 Rényi 散度变为无穷大，从而违反了“所有阶数”的 zCDP 要求。

• 平凡情况： 在 $r=1$ 时，一个与数据无关的发布机制（例如始终输出 $0.5$）可以满足修复后的准则，且隐私损失为零（$v \equiv 0$）。

意义与主张
本文声称提供了第一个针对此类特定形式的群组隐私，证明了该速率与机制无关的证明。

• 可行性： 它确立了“修复后”的公式是可解的，并提供了一个具体的、可组合的机制（偏移对数高斯机制）来实现该最优速率。
• 最优性： 它证明了没有任何机制（无论其复杂度或相关结构如何）能够超越 $n^{-2}$ 的衰减速率。
• 精确性： 通过采用多计数信息论证，本文通过比以往的两计数分析显著收紧了对领先常数的约束，将不确定性降低到了三倍因子以内。

作者明确指出，确定最优系数 $C^*$ 的确切值仍是一个开放性问题。他们还指出，其结果适用于固定的、不相交的群组；重叠或数据依赖型的群组需要单独的敏感性分析。由于采用了 $-\sigma^2$ 漂移，该机制是有偏的，但它是专门为最小化期望绝对误差而校准的，而非为了实现无偏性。