Tight Lower Bounds for Differentially Private Continual Counting

The Binary Tree Mechanism is a standard algorithm for differentially private continual counting, but its asymptotic optimality under pure differential privacy has remained unresolved since its introduction. We resolve this question. For fixed $0<\epsilon \le 1$, we prove asymptotically tight lower bounds of $\mathrm{\Omega }({\log }^{2}n)$ for worst-case expected ${\mathrm{\ell }}_{\mathrm{\infty }}$ error and $\mathrm{\Omega }({\log }^{3}n)$ for mean and maximum per-coordinate expected squared error. These bounds hold for arbitrary mechanisms, even when the entire stream is available in advance. The same lower bounds hold under approximate differential privacy whenever $\delta \le n^{-c}$, for any fixed $c>0$. Our lower bounds match the Binary Tree Mechanism instantiated with Laplace noise, establishing its asymptotic optimality under both pure differential privacy and approximate differential privacy in the standard regime of $\delta \ll 1\mathrm{/}n$. Our proof uses a single hard distribution with a bounded exponential score on a tree. A simple modification of the score allows the same framework to establish tight lower bounds for all three error measures.