技术摘要：面向准确性的 Rényi 差分隐私与后处理免疫性

问题陈述

差分隐私（Differential Privacy, DP）是隐私保护数据分析的金标准，但其严格的“事前”（ex-ante）定义要求在算法运行前必须指定一个固定的数值隐私界限（$\epsilon$）。这种僵化性阻碍了那些需要根据数据敏感性或效用需求自适应调整隐私界限的工作流（例如：如果数据变得不那么敏感，则降低保护强度；或者如果效用过低，则增加保护强度）。

由 Ligett 等人（2017）提出的“准确性优先”（accuracy-first）视角解决了这一问题，它允许隐私界限依赖于私有数据，被称为“事后隐私”（ex-post privacy）。在这种框架下，分析师设定一个最小效用（准确性）阈值，并寻找在经验上满足该阈值的最强隐私界限。然而，现有的事后定义忽略了标准 DP 的一个关键属性：后处理免疫性（post-processing immunity）。该属性确保了攻击者无法通过对输出进行后处理来削弱隐私保证。如果没有这一特性，隐私保证可能会因为输出被转换而变得比承诺的更弱。

目前的文献缺乏对哪些事后定义具有后处理免疫性的全面分析，且唯一被证明具有该属性的定义（纯粹事后隐私）缺乏实用的工具，例如事后高斯机制（ex-post Gaussian mechanism）或在独立私有数据集上验证准确性的算法。

研究方法

1. 重构事后隐私表示法

作者指出，标准的事后隐私表示法中，隐私界限 $E$ 是输出 $y$ 的函数（即 $E: \mathcal{Y} \to \mathbb{R}_{\geq 0}$），这在定义后处理免疫性时会产生逻辑不一致。如果机制被函数 $f$ 进行后处理，隐私界限函数的定义域必须发生变化，从而导致难以定义等价性。

为了解决这个问题，本文提出了一种新的表示法，将隐私界限视为机制输出的显式组成部分。一个机制 $M$ 被定义为一个随机函数 $M: \mathcal{X} \to \mathcal{Y} \times \mathbb{R}_{\geq 0}$，返回一个对子 $(y, \epsilon)$。后处理被定义为应用于输出对的随机函数 $f$，其中隐私界限 $\epsilon$ 保持不变（即 $M'(X)_\epsilon = M(X)_\epsilon$）。

2. 现有定义分析

利用这种新表示法，作者分析了现有的定义：

• 纯粹事后隐私 (Pure Ex-Post Privacy, Ligett et al., 2017)： 已证明对于连续/离散分布具有后处理免疫性。然而，它缺乏用于实际应用的实用工具，例如事后高斯机制。
• $\delta$-概率事后隐私 ($\delta$-Probabilistic Ex-Post Privacy, Whitehouse et al., 2022)： 被证明在 $\delta > 0$ 时不具备后处理免疫性。作者表明，该定义泛化了已知无法满足后处理免疫性的 $(\epsilon, \delta)$-概率差分隐私。

3. 提出事后 Rényi 差分隐私 (Ex-Post RDP)

为了弥合后处理免疫性与实际效用之间的差距，作者提出了一种基于 Rényi 差分隐私（RDP）的新定义。

• 定义： 机制 $M: \mathcal{X} \to \mathcal{Y} \times \mathbb{R}_{\geq 0}$ 是 $\alpha$-事后 RDP，如果对于所有相邻数据集 $X \sim X'$，由返回的隐私界限加权的隐私损失随机变量的矩生成函数的期望满足：
  $$\mathbb{E}_{(y, \epsilon) \sim M(X')} \left[ e^{(1-\alpha)\epsilon} \left( \frac{p_{M(X)}(y, \epsilon)}{p_{M(X')}(y, \epsilon)} \right)^\alpha \right] \leq 1$$
• 性质： 作者证明了该定义满足后处理免疫性。他们还建立了基本性质，包括自适应组合以及构建具有完全自适应隐私界限的机制的能力。

4. 布朗机制 (The Brownian Mechanism)

作者证明了布朗机制（Whitehouse et al., 2022，一种高斯机制的准确性优先模拟物）满足 $\alpha$-事后 RDP。

• 机制： 它发布带有相关高斯噪声的函数 $f(X)$ 的噪声输出。如果后续发布的隐私预算增加，则噪声方差会降低。最终输出是所有中间发布结果的精度加权平均值。
• 证明： 作者没有依赖随机过程（布朗运动），而是通过将该机制建模为“序列精度加权高斯机制”，并证明其在新事后 RDP 定义下的等价性，提供了一个初等证明。

5. 数据依赖型停止规则

一个重要的理论贡献是关于具有数据依赖型停止准则的自适应组合算法（算法 1）。不同于以往仅检查训练集准确性的工作，该算法使用一个不相交的私有验证集来确定何时达到准确性阈值。这使得机制能够提前停止，在确保验证准确性足够的同时，最小化隐私预算。

核心贡献

1. 表示法重构： 引入了一种新的事后隐私表示法，将隐私界限作为输出的一部分，从而能够对后处理免疫性进行严谨且优雅的定义。
2. 免疫性分析： 证明了纯粹事后隐私具有后处理免疫性，而 $\delta$-概率事后隐私则不具备。
3. 新定义： 提出了 $\alpha$-事后 RDP，该定义具有后处理免疫性，并支持布朗机制。
4. 理论工具： 开发了事后 RDP 的基本理论，包括自适应组合定理以及使用私有验证集构建具有数据依赖型停止规则的机制的方法。
5. 机制验证： 证明了布朗机制满足 $\alpha$-事后 RDP，为该机制的后处理免疫性提供了首个理论证明。
6. 实际应用： 在两个应用场景中展示了该框架：
   • 合成数据生成： 生成表格数据，在分类器在私有验证集上达到目标准确率之前，持续最小化隐私预算。
   • 图像分类器微调： 调整隐私界限直到满足最小准确性阈值。

结果

• 理论界限： 作者将基于事后 RDP 的布朗机制界限与 Whitehouse 等人 (2022) 的概率事后隐私界限进行了比较。结果表明，当优化自由参数时，两者非常接近（在浮点误差范围内可能在数学上相等），这表明获得后处理免疫性并不会以牺牲效用为代价。
• 实验表现： 在使用 UCI Adult 数据集进行合成数据生成的实验中：
  • 布朗机制成功地在满足私有验证集准确性阈值的同时，最小化了隐私成本。
  • 该机制使用了一系列候选 $\epsilon$ 值列表，从最低值开始，仅在未达到准确性阈值时才增加。
  • 测试了两种在 DP 下检查准确性阈值的方法：普通高斯机制的组合和稀疏向量技术 (SVT)。SVT 通常导致更小的总隐私预算 ($\epsilon$)，而普通高斯方法则能产生略高的验证准确性。
  • 系统成功实现了自适应调整隐私界限，证明了该理论的实用性。

意义与主张

本文声称填补了差分隐私中“准确性优先”视角的关键空白。通过识别出现有定义要么缺乏后处理免疫性，要么缺乏实用工具，作者提供了一个同时具备这两者的统一框架。

其意义在于实现了此前在理论上不可靠或在实践上难以实现的自适应隐私工作流。具体而言：

• 它允许分析师仅在必要时（为了达到效用阈值）才减少隐私保护（增加 $\epsilon$），同时不会损害针对后处理攻击的保证。
• 它为在事后设置中使用具有后处理免疫性的布朗机制提供了首个理论依据。
• 它引入了一种在私有验证集而非训练集上验证准确性的方法，这对于防止过拟合以及确保隐私保护机器学习中的泛化至关重要。

作者保持了谦逊的态度，指出虽然他们的 RDP 界限提供了灵活性和免疫性，但也继承了 RDP 与 $f$-DP 或高斯 DP 相比在可解释性方面的局限性。他们建议，开发这些替代定义的后验版本是未来研究的一个有前景的方向。