The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

技术摘要：二叉树机制在近似差分隐私连续计数中的最优性

问题陈述
本文探讨了**私有连续计数（private continual counting）**这一基本问题。在这种设定下，机构观察一个长度为 $n$ 的二进制流 $x \in \{0, 1\}^n$，其中时间步 $i$ 处的 '1' 表示由单个个体贡献的事件。目标是在每个时间步 $i \in [n]$ 发布运行计数（前缀和）$Ax$，同时满足$(\epsilon, \delta)$-差分隐私（DP）。这里，$A$ 是 $n \times n$ 的下三角前缀和矩阵。衡量准确性的主要指标是期望 $\ell_\infty$ 误差，定义为 $\mathbb{E}[\|M(x) - Ax\|_\infty]$，它代表了所有时间步中的最坏情况误差。

虽然**二叉树机制（binary tree mechanism）**是处理该任务的标准算法，但其在近似 DP（$\delta > 0$）设定下的最优性一直是一个悬而未决的问题。先前的分析表明，二叉树机制实现的 $\ell_\infty$ 误差为 $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$。然而，已知的最佳下界仅为 $\Omega(\log n / \epsilon)$（具体针对期望平方最坏情况误差的平方根），这留下了一个缺口，即关于 $\log^{3/2} n$ 对流长度 $n$ 的依赖关系是否是必要的。

方法论与证明概述
作者通过建立匹配的下界 $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$，证明了二叉树机制是渐近最优的。证明过程包含以下几个关键技术步骤：

1. 归约为无知机制（Oblivious Mechanisms）： 遵循前人的工作，作者将问题归约为分析形式为 $M(x) = Ax + z$的无知机制，其中$z$是独立于输入$x$的噪声向量。目标变为对$\mathbb{E}[|z|_\infty]$ 进行下界估计。
2. 树基分解（Tree Basis Decomposition）： 作者并未直接在标准基下分析噪声，而是将噪声向量 $z$ 分解到由完美二叉树诱导的基中。具体而言，他们定义了对应于子树（子树内叶节点的指示函数）的向量 $\chi_u$。在此基下，任何叶片 $i$ 处的噪声是沿从根到叶片路径上的系数 $b_u$ 之和。这使得将最大坐标误差的界限问题转化为边界根到叶路径上的噪声累积问题。
3. 噪声累积与残余不确定性： 证明引入了“残余噪声（residual noise）” $\sigma_u$ 的概念。作者指出，如果一个节点 $u$ 的噪声可以从其下方的子树噪声中被高精度地预测，那么隐私将会被破坏。作者将 $\sigma_u$ 定义为给定子树噪声的情况下，预测当前节点噪声系数的期望绝对误差。他们证明了 $\ell_\infty$ 期望误差是沿随机根到叶路径的这些残余不确定性的加权和。
4. 克服“预测”障碍： 一个主要的挑战在于，由于输入 $x$ 是未知的，对手无法直接观察子树噪声来预测当前节点的噪声。为了绕过这一点，作者采用了“孙辈（grandchildren）策略”。他们展示了通过关注特定的子树并利用三个独立的机制副本（利用 DP 的组合性质），对手可以使用**三数取中法（median-of-three trick）**来降低噪声方差。这允许构建一个派生机制，使对手能够计算形式为 $x_i \nu_i + q$ 的线性测量，其中 $q$ 具有受控的方差。
5. 线性测量与哈尔小波（Haar Wavelets）： 最后一步构建了一个受哈尔小波基启发的线性测量对手。通过选择正交测量向量，作者将对手估计的平方误差之和与残余噪声的 $\ell_2$ 范数联系起来。他们证明，如果残余噪声 $\sigma_u$ 过小，对手就能以高概率区分相邻的输入，从而违反差分隐私。这迫使残余噪声必须足够大，即 $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$。
6. 求和： 将这些残余不确定性沿路径求和，得出最终的 $\Omega(\log^{3/2} n)$ 下界。

核心贡献与结果

• 二叉树机制的最优性： 本文证明了对于近似 DP，任何用于连续计数的机制都必须承受 $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$ 的期望 $\ell_\infty$ 误差。这与二叉树机制的上界（在常数因子范围内）相匹配，解决了关于 $\log^{3/2} n$ 依赖性是否必要的悬而未决的问题。
• 收紧纯 DP 界限： 对于纯 DP（$\delta = 0$），该结果收紧了已知上界 $O(\log^2 n / \epsilon)$ 与下界之间的差距，显示出 $\Omega(\log^{3/2} n / \epsilon)$ 的下界。
• 与遗传差异（Hereditary Discrepancy）的分离： 作为推论，作者推导出了遗传差异与私有线性查询误差之间可能的最大分离。他们表明，通用的上界 $err_{\epsilon, \delta}^\infty(A) = O(\log^{3//3} m \cdot \text{herdisc}_\infty(A))$ 在其对查询数量 $m$ 的依赖关系上是紧致的，因为前缀和矩阵的遗传差异为 1，但却需要 $\Omega(\log^{3/2} n)$ 的误差。

意义
本文声称通过证明二叉树机制在近似 DP 设定下对于连续计数是渐近最优的，解决了一个差分隐私领域的中心开放问题。文中开发的各种技术，特别是结合树基噪声分解、残余噪声分析以及处理线性测量攻击的三数取中法，被视为可能在证明差分隐私下界方面具有进一步应用价值的新颖思想。该结果证实，当前的尖端算法在关于流长度 $n$ 的依赖关系上无法得到显著改进。