Abstract
In the task of differentially private (DP) continual counting, we receive astream of increments and our goal is to output an approximate running total ofthese increments, without revealing too much about any specific increment.Despite its simplicity, differentially private continual counting has attractedsignificant attention both in theory and in practice. Existing algorithms fordifferentially private continual counting are either inefficient in terms oftheir space usage or add an excessive amount of noise, inducing suboptimalutility. The most practical DP continual counting algorithms add carefully correlatedGaussian noise to the values. The task of choosing the covariance for thisnoise can be expressed in terms of factoring the lower-triangular matrix ofones (which computes prefix sums). We present two approaches from this class(for different parameter regimes) that achieve near-optimal utility for DPcontinual counting and only require logarithmic or polylogarithmic space (andtime). Our first approach is based on a space-efficient streaming matrixmultiplication algorithm for a class of Toeplitz matrices. We show that toinstantiate this algorithm for DP continual counting, it is sufficient to finda low-degree rational function that approximates the square root on a circle inthe complex plane. We then apply and extend tools from approximation theory toachieve this. We also derive efficient closed-forms for the objective functionfor arbitrarily many steps, and show direct numerical optimization yields ahighly practical solution to the problem. Our second approach combines ourfirst approach with a recursive construction similar to the binary treemechanism.