AI Insight
This theoretical computer science paper proves that the binary tree mechanism for differentially private continual counting—tracking running totals in data streams while protecting individual privacy—is mathematically optimal. The researchers establish lower bounds showing that the mechanism's error rates of O(log^(3/2) n) for approximate differential privacy and O(log^2 n) for pure differential privacy cannot be improved, resolving a long-standing open question in the field. The proof techniques also yield insights about the relationship between hereditary discrepancy and privacy error in linear queries.
Why it matters
These findings provide theoretical guarantees for privacy-preserving systems that need to continuously release statistics, such as disease surveillance systems or website analytics. By proving optimality, the work confirms that practitioners using the binary tree mechanism are achieving the best possible privacy-utility tradeoff, and that searching for fundamentally better algorithms would be futile.
Understand the Science
⚠️ Preprint – Noch nicht peer-reviewed
Dieser Artikel wurde noch nicht von unabhängigen Experten begutachtet. Die Ergebnisse sind vorläufig und sollten mit Vorsicht interpretiert werden.
-cross
Abstract: 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. For fixed privacy parameters, the standard binary tree mechanism achieves expected $ell_infty$ error $O(log^{3/2} n)$ under approximate differential privacy and $O(log^2 n)$ under pure differential privacy. Whether these dependences on the stream length are necessary has remained a central open problem.
For fixed $varepsilonin(0,1)$, we prove a lower bound of $Omega(log^{3/2} n)$ under approximate DP with sufficiently small fixed $delta>0$, and a lower bound of $Omega(log^2 n)$ under pure DP. These bounds establish the optimality of the binary tree mechanism in both settings. The bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. Both proofs use the same decomposition and accumulation of residual noise along a tree.
As a consequence of the approximate-DP bound, 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.
Source: The Binary Tree Mechanism is Optimal for Differentially Private Continual Counting