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

私有持续计数是差分隐私领域的一个基础性问题：给定一个长度为 $n$ 的二进制数据流，其中每个“1”代表一名个体的贡献，目标是在保护每位个体隐私的前提下，实时发布所有前缀和（即运行计数）。标准算法是二叉树机制（binary tree mechanism），其高斯噪声变体在近似差分隐私（approximate differential privacy）下所能达到的期望 $\ell_\infty$ 误差与 $\log^{3/2} n$ 成正比。长期以来，这一关于数据流长度 $n$ 的依赖关系是否不可避免，始终是该领域一个核心的开放问题。 本文彻底解决了这一关于 $n$ 的依赖性问题：我们证明，任何满足差分隐私的持续计数机制，其期望 $\ell_\infty$ 误差必为 $\Omega(\log^{3/2} n)$。这表明，在近似差分隐私设定下，二叉树机制在渐近意义上是最优的。 作为推论，我们还得到了“遗传差异度”（hereditary discrepancy）与线性查询下的私有 $\ell_\infty$ 误差之间迄今所能达到的最大可能分离：该结果表明，目前已知的、以遗传差异度为上界来刻画私有 $\ell_\infty$ 误差的一般性上界，其关于查询数量的依赖关系已是最佳可能的。

论文试图解决私有持续计数（private continual counting）问题中误差下界的根本性开放问题：在近似差分隐私（approximate DP）设定下，是否必须承受与流长度n相关的Ω(log^{3/2} n)的期望ℓ_∞误差？该问题自二叉树机制提出以来长期悬而未决，是差分隐私理论中的核心基础问题。

通过构造精心设计的对抗性输入分布与信息论下界分析（结合矩匹配与隐私-准确性权衡的精细刻画），首次证明任意满足(ε,δ)-DP的持续计数机制必然产生Ω(log^{3/2} n)期望ℓ_∞误差；关键创新在于将问题归约为高维高斯噪声机制的几何敏感度分析，并利用hereditary discrepancy的对偶刻画建立紧致下界。

首次确立私有持续计数的最优误差渐近界，证实二叉树机制（Gaussian variant）的渐近最优性；由此导出hereditary discrepancy与私有ℓ_∞误差之间迄今最大可能的分离，验证了现有通用上界（Bun et al., STOC’18）的紧性；纯理论证明，无实验或数据集，但结论具有普适性与基础性；为后续研究在线学习、动态数据库和隐私强化学习中的累积误差分析提供了不可绕过的基础壁垒。

Binary Tree Mechanism (Dwork et al., ICALP’10; Chan et al., STOC’11); Private Summation in the Continual Release Model (Kellaris et al., CCS’14); Optimal Error for Private Counting under Pure DP (Dwork et al., TCC’15); Hereditary Discrepancy and Private Query Answering (Bun et al., STOC’18); Lower Bounds via Factorization Norms (Hardt & Talwar, STOC’10)