证明二叉树机制在近似差分隐私下持续计数最优
The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting
- 通过理论证明二叉树机制误差下界为Ω(log^{3/2} n)
- 首次证明任意机制都需至少该量级的ℓ∞误差
- 适合研究差分隐私机制极限与查询复杂度的学者
私有持续计数是差分隐私中的基础问题：给定长度为n的二进制流，每个1代表一个个体的贡献，目标是在保护个体隐私的前提下发布所有累计计数。标准算法为二叉树机制，其高斯噪声版本在近似差分隐私下可实现期望ℓ∞误差与log^{3/2} n成正比。这一依赖关系是否必要长期未解。本文证明，任何差分隐私机制进行持续计数时，期望ℓ∞误差至少为Ω(log^{3/2} n)，从而表明二叉树机制在近似差分隐私设置下渐近最优。作为推论，我们还得到了线性查询中继承离散性与私有ℓ∞误差之间最大的可能差距，说明基于继承离散性的已知上界对查询数量的依赖已达最优。
原文摘要 · Abstract (English)
Private continual counting is a fundamental problem in differential privacy: given a binary stream of length $n$, where each $1$ corresponds to the contribution of one individual, the goal is to release all running counts while protecting the privacy of each individual. The standard algorithm is the binary tree mechanism, whose Gaussian-noise variant achieves expected $\ell_\infty$ error proportional to $\log^{3/2} n$ for approximate differential privacy. Whether this dependence on the stream length is necessary has remained a central open problem. In this work, we resolve the dependence on $n$ by proving that every differentially private mechanism for continual counting must incur expected $\ell_\infty$ error $Ω(\log^{3/2} n)$. This shows that the binary tree mechanism is asymptotically optimal in the approximate-DP setting. As a consequence, we also obtain a largest-possible separation between hereditary discrepancy and private $\ell_\infty$ error for linear queries, showing that the known general upper bound in terms of hereditary discrepancy has the optimal dependence on the number of queries.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。