Pure-DP Statistical Query Release at the Conjectured Square-Root Rate

技术摘要：在推测的平方根速率下实现纯 DP 统计查询发布

问题陈述
本文研究了**纯差分隐私（pure DP）**下的统计查询发布问题。给定一个大小为 $n$、定义域为 $D$（大小为 $T$）的私有数据库 $x$，以及一组 $k$ 个有界查询 $Q$，目标是发布一个随机向量，该向量能同时逼近所有查询的真实答案 $F(x)$。误差度量为期望最差坐标误差（$\ell_\infty$ 范数）。

近似 DP 机制（允许一个小的失败概率 $\delta > 0$）可以实现 $O(\sqrt{\frac{\log T \log k}{\varepsilon n}})$ 的误差率，而已知的纯 DP 机制（其中 $\delta = 0$）此前被限制在立方根速率 $O((\frac{\log T \log k}{\varepsilon n})^{1/3})$。Nikolov 和 Ullman [NU21] 曾推测，对于期望误差，平方根速率在纯 DP 下也是可以实现的。本文证明了这一推测。

方法论
所提出的机制是信息论性质的，由三个主要阶段组成：

1. 仅选择型 PMW 转录（Selection-Only PMW Transcript）：
   该构造始于标准的私有多权重算法（PMW），但修改了输出方式。该机制不再于每轮发布带有噪声的数值答案，而是生成一个由指数机制所选查询的索引和符号组成的转录（transcript） $\omega$。这个“仅选择型”转录是准确的，并且具有良好的有限阶隐私损失矩（Rényi 散度界），但其本身并不满足纯 DP。

2. 隐私包络构造（Privacy Envelope Construction）：
   为了将矩受限的转录转换为纯 DP 机制，作者使用**距离惩罚似然包络（distance-penalized likelihood envelope）**替换了原始的转录概率质量函数 $p_x(\omega)$。对于固定的数据库 $x$，转录 $\omega$ 的未归一化概率定义为：
   $$\tilde{p}_x(\omega) = \max_{y \in D^n} e^{-(\varepsilon/2)d_H(x,y)} p_y(\omega)$$
   其中 $d_H$ 是汉明距离。该包络确保了当输入数据库改变一行时，似然度的变化最多为 $e^{\varepsilon/2}$ 倍因子。通过总质量 $Z_x$ 进行归一化后，所得机制满足纯 $\varepsilon$-DP。

3. 公开解码（Public Decoding）：
   所选的转录决定了整个 PMW 更新的合成轨迹。机制输出的是基于平均合成分布的查询答案。该解码步骤是确定性的，不会引入额外的隐私代价。

关键技术挑战与解决方案
主要的困难在于确保包络修改不会破坏原始 PMW 转录的效用（准确性）。包络会为可能解码出不准确答案的转录分配概率。证明过程通过以下方式管理此问题：

• 似然层级的 Maurey 论证： 为了限制汉明半径为 $R$ 的球内的最大似然度，作者使用了一种 Maurey 型论证。他们证明了所有数据库中的最大似然度可以被一个较小的“代理”目标向量族（通过随机行替换构造）的最大似然度所上界约束。这避免了对所有数据库进行求和导致的指数级爆炸。
• 两阶段分析：
  • 邻近数据库： 对于较小的汉明距离，作者使用有限阶 Rényi 矩界和 Hölder 不等式来控制似然比。
  • 远端数据库： 对于较大的距离，矩界变得过于昂贵。相反，最大似然度通过似然之和（混合界）来限制，利用了每个似然都是一个概率分布的事实。
• 分块求和（Blocked Summation）： 朴素地对所有整数汉明半径进行求和会引入不希望看到的 $1/\varepsilon$ 因子。作者将半径分为宽度为 $\Theta(1/\varepsilon)$ 的块。在每个块内，似然度的增长由外半径控制，而隐私惩罚由内半径控制。这种技术消除了额外的 $1/\varepsilon$ 损失，从而保留了平方根速率。

主要结果
本文确立了以下定理：

定理 1.1： 存在一常数 $C > 0$，使得对于任何有限定义域 $D$（$|D|=T$）、有限查询集 $Q$（$|Q|=k$）、数据库大小 $n$ 以及隐私参数 $\varepsilon > 0$，存在一个纯 $\varepsilon$-差分隐私机制 $M$，满足：
$$\sup_{x \in D^n} \mathbb{E} \|M(x) - F(x)\|_\infty \leq C \min\left(1, \sqrt{\frac{\log(2T) \log(2k)}{\varepsilon n}}\right)$$

该结果与标准高维场景下的已知下界相匹配，证实了在纯 DP 下对于期望误差的推测最优速率。

意义与主张

• 解决开放问题 1： 本工作解决了 Nikolov 和 Ullman [NU21] 在 DifferentialPrivacy.org 上提出的开放问题 1，缩小了统计查询发布中近似 DP 与纯 DP 速率之间的差距。
• 信息论保证： 该机制是信息论性质的，这意味着转录空间和包络中的最大化过程是有限的（尽管可能呈指数级增长）。论文明确指出，实现具有该速率的多项式时间算法仍是一个开放问题。
• 形式化验证： 该构造和证明已使用 Lean 4 进行了机器检查，验证了有限构造、纯隐私属性以及显式的误差界。
• 适用范围： 该结果在所有参数选择下都是统一的。使用 "min" 函数和偏移后的对数确保了即使在退化情况（例如较小的 $n$ 或 $k$）下的有效性，尽管论文并未声称在这些退化场景下也匹配下界。

论文得出结论，包络技术成功地将仅选择型 PMW 的局部效用转化为全局纯 DP 律，且没有引入此前限制纯 DP 机制的“数据集数量惩罚”或 $1/\varepsilon$ 因子。