Private Continual Counting of Unbounded Streams

Thank you for your very helpful review! We agree with you and reviewer G47C that we should do a better job of explaining the idea of smoothness and why it's important. We respond to each of your questions and concerns individually below:

Weakness 1: We go into more detail about the meaning and importance of smoothness in response to your questions, and we can incorporate these details into the final paper to make the significance of our contribution more clear.

Weakness 2: Binary-based methods achieve sub-linear space complexity, but this comes at the cost of much worse constant factors in their error. This is shown in Figure 2, where the Smooth Binary mechanism (brown line) has substantially higher error than both the original square-root matrix method (black line) and our new unbounded method (yellow line).

Because the relative importance of factors like speed, memory usage and accuracy can change a lot depending on the context, we believe that it's valuable to explore the full range of possible tradeoffs. We therefore see our primary contribution as enabling matrix methods to be used in settings where they would be practical except for the fact that $n$ is unknown.

Question 1: The biggest reason to care about smoothness is that the expected $\ell_\infty$ error generally scales with the maximum variance across all time steps. If that’s a relevant metric in a given context, then allowing your variance to fluctuate a over time is in some sense inefficient - you'll be penalized for the peaks without being rewarded for the valleys. This is also the motivation behind algorithms like Andersson and Pagh's Smooth Binary mechanism, which has comparable $\ell_2$ error to the classic binary mechanism but much lower $\ell_\infty$ error thanks to being smooth.

A secondary concern is that non-smooth error could complicate downstream analysis by introducing artifacts that look like data anomalies. For instance, if we were using DP continual counting to estimate the spread of an infectious disease, then having dramatically different variance from one time step to the next could plausibly lead to panic or overreactions if the output was shared with non-experts.

Question 2: We use 'smooth' to describe the actual variance at each time step, and not just its rate of asymptotic growth. If you look at Figure 2, you can see that both hybrid mechanisms have very sharp fluctuations in variance whenever $t$ is close to a power of 2 - this is why they’re categorized as non-smooth. We can clarify this point in the introduction when we first use the term.

Thank you for your kind comments! We address all of your questions individually below:

Question 1: Yes, all of the mechanisms we consider add zero-mean Gaussian noise, so they're all unbiased estimators.

Question 2: To upper-bound the expected $\ell_\infty$ error, there’s a standard trick based on moment-generating functions and the log-sum-exp function; if your mechanism runs for $t$ steps and the maximum variance across time steps is $\sigma^2$, then the expected $\ell_\infty$ error is at most $\sigma \sqrt{2 \log t}$. You can also derive high probability bounds using the Borel-TIS inequality, which essentially says that the maximum of Gaussians has sub-Gaussian tails.

For $\ell_2$ error, linearity of expectation means we can just add up all of the per-time-step variances, take the square root, and normalize. In the case of matrix mechanisms, this gives us error proportional to $\sqrt{\text{tr} LL^T} = \lVert L \rVert_F$. But on that note, your question helped us realize that we had a typo in our original presentation: the $1/n$ factor should be inside the square root, not outside of it. So thank you for prompting us to check over that part of the paper again!

Question 3: We use 'smooth' to describe the actual variance at each time step, and not just its rate of asymptotic growth. For the binary mechanism, the noise at time step $t$ depends on the number of '1's in the binary representation of $t$, which makes it oscillate. We actually intended to include the binary mechanism in Figure 2 for comparison, but the oscillations were so extreme that it made the rest of the figure illegible. We can clarify this point in the introduction when we first introduce the term.

Question 4: That's true, yes. We present it this way to highlight the differences in the internal structure of the various algorithms - the error of the Hybrid Binary mechanism decomposes into the error of the bounded component (which is $O(\log^2 t)$) and the error of the unbounded component (which is $O(\log t)$).

Thank you for providing so many detailed suggestions and insightful questions! We appreciate being pushed to be more mathematically precise and feel confident that the final paper will be much clearer as a result. We respond individually to each of the weaknesses and questions you raised below:

Weakness 1: Although the sequence we consider is based on generating functions that have been studied before, this is also the case for many other works in this area - for instance, Henzinger et al. (2023) use the coefficients of the generating function of $1/\sqrt{1-z}$, which were already known to Newton, and Dvijotham et al. (2024) build on known results about rational approximations of the function $1/\sqrt{1-z}$ on the unit circle that were first published in the 1960s.

Like these prior works, our contribution is not in being the first people to write down this particular sequence, but rather in A) recognizing that the analytic properties of the sequences studied in prior works are equivalent to interesting properties of differentially-private streaming algorithms, like unboundedness, B) showing that the implied algorithm can be implemented in a computationally efficient way, and C) empirically demonstrating that the resulting algorithm is a concrete improvement over the state of the art in relevant metrics.

Weakness 2: This is a great point, and it’s true that asymptotically our algorithm is slightly worse than a (well-implemented) doubling trick. But as we show in Figure 2, the slightly-worse logarithmic dependence is counterbalanced by much better constants, and so for the input sizes we evaluate, our approach does actually lead to better estimators. In particular, Figure 2 shows that the Hybrid mechanism of Chan et al. (orange line), which is based on a doubling trick, has much higher variance than our proposed algorithm (yellow line).

Weakness 3: We address this point in more detail below.

Question 1: To the best of our knowledge, no prior work in the DP literature has used similar constructions, so in that context we believe it is novel. We also aren’t aware of any earlier work that explicitly considers these functions in the context of LTT matrix factorizations.

As for how we came up with the function $f$ - we'd been working on the general problem for a few months by starting with the square-root factorization, manually perturbing coefficients to make them convergent, and trying to use Fourier analysis to derive features of the implicitly defined function. Reading Dvijotham et al. (2024) put the idea of going in the opposite direction in our heads. Later on, a search for relevant works turned up the Flajolet and Odlyzko paper and we realized that the functions that they had studied in the context of analytic combinatorics could potentially do what we needed.

Question 2: Every algorithm we design and compare against satisfies DP by adding Gaussian noise, and so all of them have exactly the same dependence on epsilon and delta. This is why we don't emphasize the dependence on privacy parameters - both our asymptotic results and our comparisons against related work would be unaffected by varying the privacy level. That said, it does make sense that readers would expect to see some sort of dependency on the privacy parameters. To fix this, we'll modify the second column of Table 1 to indicate that it represents the variance after being normalized by a data-independent value that depends on epsilon and delta, analogous to Table 1 in Andersson and Pagh (2023).

Question 3: Focusing on bits is a convention in the private counting literature, going all the way back to Chan et al. (2011) and Dwork et al. (2010). The general case can be reduced to bit-counting as follows:

First, consider $d$-dimensional bit vectors. We can construct a continual counting algorithm for that setting by applying $d$ versions of our single-bit algorithm in parallel to each coordinate. We can then use composition theorems to control the overall privacy cost, which translates to an extra factor of $d$ in the variance.

Next, consider real-valued vectors in a bounded set with $\ell_\infty$ diameter $D$. By shifting and scaling, we can convert them to vectors in $[0,1]^d$. From there, the fact that they can take intermediate values doesn't impact sensitivity, so our private $d$-dimensional bit counting algorithm will work out of the box. At the end, we rescale our estimates, increasing variance by a factor of $D^2$.

Similar reductions are possible if you instead assume your vectors are in a set with bounded $\ell_2$ diameter, or if they're contained in an ellipsoid. In particular, it doesn't matter if the original coordinates are negative or not - only the distances between them are important. To be more precise, we can revise this section to say that it's easy to generalize our results to vectors in any bounded subset of $\mathbb{R}^d$.

Question 4: Yes, high-probability bounds can be derived from the variance of each mechanism. The important point here is that the noise added for privacy follows a zero-mean Gaussian distribution. This means that knowing the variance fully determines the distribution and therefore all relevant error metrics, including both expectations and high-probability bounds.

Concretely, if you want a high probability bound on $\ell_\infty$ error, you can use MGFs to upper bound the expected maximum error across all time steps and then apply the Borel-TIS inequality, which says that the distribution of the maximum of a set of Gaussian random variables has sub-Gaussian tails. Analogous bounds can be derived for $\ell_2$ error using the fact that Borel-TIS-like inequalities hold for any Lipschitz function of a normal random variable, including vector norms (see e.g. equation 5 in "Four Talagrand inequalities under the same umbrella" by Michel Ledoux).

Question 5: The most naive doubling trick will give you $O(\log^3 t)$ variance. We don't compare against that algorithm because the Hybrid mechanism of Chan et al. (row 2 of the table 1) is a more sophisticated version of the same idea.

Asymptotically speaking, that algorithm is already optimal (i.e. it achieves $O(\log^2 t)$ variance), but it has pretty poor constants - this is shown in figure 2 (orange line), where it has the worst variance of all of the algorithms we consider. We also show that those constants can be improved substantially by replacing one of its subcomponents with our own algorithm (teal line in figure 2; 'Hybrid Matrix' in table 1). So, even if someone was primarily interested in asymptotic guarantees, they would still be better off using the version of the Hybrid mechanism based on our matrix factorization instead of the classic variant.

L136-137: You understand correctly, yes - we're sorry that it ended up being confusing. Our goal here was to make it easier for an interested reader to cross-reference our results with the original Flajolet paper, which uses $\delta$ as the exponent of the $\log\log$ term. We'll revise our definition of DP to use $\varepsilon_{*priv*},\delta_{*priv*}$ instead of $\varepsilon,\delta$ to remove the ambiguity.

L175-176: This is a good point and we will clarify - our functions are analytic on the open unit disc. The division by $z$ is there to eliminate the zero of $\ln(1/(1-z))$ at $z=0$, which makes it possible to take further logarithms or raise our function to non-integer powers without running into issues with the domain of definition.

L206: Thank you for pointing this out - the constants $n_0$ and $C$ come from the definition of big-$O$, which we will clarify.

L216-217: This model of computation comes from the Hanrot and Zimmerman note that we cite and is intended to simplify away linear and logarithmic terms that don’t matter asymptotically. The intuitive justification is that polynomial multiplication can be implemented as a divide-and-conquer algorithm, and so the cost of multiplying polynomials of degree $tk$ is asymptotically equal to the cost of multiplying $k$ pairs of polynomials with degree $t$.

The upshot of using this model of computation vs. big-$O$ is that it makes it easy to track the multiplicative constants - every parameterization of our algorithm requires $O(n \log n)$ time, but this approach lets us additionally estimate that choosing $\delta=0$ should roughly halve the actual computation required, for example.

Regardless, your counterexample definitely highlights that we were too informal in our presentation, and we'll add a clarification that $M(kt) \sim kM(t)$ should be interpreted as holding asymptotically for large $t$.

L227-240: This section is definitely very dense. Given the suggestions from other reviewers about the clarity of figures and spots where we could include more detail, we plan to move the technical exposition here to the appendix. This will give us space to make it more explicit by giving a step-by-step formula for constructing each of the sequences we consider instead of describing the process in natural language.

Thank you for your review! It was very helpful and we appreciated all of the insightful questions. We address each of them individually below:

Question 1: As long as you pick $\alpha>0$, $R$ will have a bounded matrix norm, so from a privacy perspective the exact value doesn't matter that much - we can always compute the sensitivity and add sufficient noise to guarantee whatever level of privacy we want. At a high level, we think that selecting $\alpha$ is best understood as a (fairly low-impact) tradeoff between constant factors and asymptotic growth rates in the variance.

Question 2: The biggest reason to care about smoothness is that the expected $\ell_\infty$ error generally scales with the maximum variance across all time steps. If that’s a relevant metric in a given context, then allowing your variance to fluctuate erratically over time is in some sense inefficient - you'll be penalized for the peaks without being rewarded for the valleys. This is also the motivation behind algorithms like Andersson and Pagh's Smooth Binary mechanism, which has comparable $\ell_2$ error to the classic binary mechanism but much lower $\ell_\infty$ error thanks to being smooth.

A secondary concern is that non-smooth error could complicate downstream analysis by introducing artifacts that look like data anomalies. For instance, if we were using DP continual counting to estimate the spread of an infectious disease, then having dramatically different variance from one time step to the next could plausibly lead to panic or overreactions if the output was shared with non-experts.

Question 3: We agree that this is an important consideration for very large-scale deployments. If we restrict ourselves to LTT matrix factorizations, then there isn’t any hope to improve on the space complexity: recent work by Andersson and Yehudayoff has shown that for LTT matrices like ours that correspond to irrational functions, $\Omega(t)$ space complexity is unavoidable, and generating noise with LTT matrices is fundamentally tied to convolution so we would be very surprised if it was possible to do better than $O(t \log t)$ time.

The Toeplitz part of the LTT restriction isn’t fundamental, however, and we’re aware of another recent work in this area (Andersson and Pagh, 2025, SaTML) which uses binning to approximate Toeplitz matrices in a way that only requires sub-linear space. One potential obstacle we can foresee with directly applying their results to our factorization is that their algorithm assumes efficient random access to the $L$ matrix being approximated, which isn’t obviously possible in our case. But, we speculate that this could maybe be circumvented for sufficiently large inputs by using the asymptotic expansion for the elements of $L$ alongside some robustness analysis to show that their algorithm can still work well if the input is allowed to have small errors.

Question 4: In general, we believe our empirical results are the most compelling evidence that the approximation is 'safe' from a utility perspective. But as a very rough heuristic, if we imagine that Equation 2 systematically had relative error $\eta$ across the board, then the inverse matrix would have relative error of roughly $\eta$ as well, which would imply something like a $(1+\eta)^2$ overhead in error after adjusting for sensitivity.

In practice we see that the relative error varies over time, but it does so in a smooth, monotonic way. In our view, it would be pretty surprising if that led to the behavior of the inverse matrix being qualitatively very different from the idealized case of uniform error, especially if that qualitative difference only emerged after a very long period in which it behaved exactly as we would expect.

Limitations: Thank you for the helpful feedback! We aren’t totally satisfied with that figure either and have a few ideas for improvements. In particular, for the final version we would like to split the two subfigures apart, which would make it easier to distinguish the lines and also give us more horizontal space to include longer and more informative labels in the legend. We expect that we’ll be able to find enough extra space for this by moving the more technical components of the Computability proof in Section 4 to the appendix, which will also let us expand that section in line with reviewer nSpn’s suggestions. We can also take another pass over the captions to make them more self-contained so readers won’t have to do so much jumping around.

Thank you for the very helpful review! We agree with many of your suggestions and address all of the weaknesses and questions you raised below:

Weaknesses: We definitely want our paper to be accessible to as broad an audience as possible, so this is very valuable feedback! We are happy to include both a formal statement of all cited theorems and a formal proof of Corollary 1 as additional appendices in the final version. The essential idea of the proof is described when we introduce matrix methods in the Related Work section (line 85), but we can make this more explicit.

Question 1: We don't use a doubling trick in the sense of restarting the entire private learning algorithm, which would lead to a lot of excess error.

We do, however, use a doubling trick when precomputing matrix products since it lets us amortize the computational cost. This is only relevant for speed and not for accuracy. We agree that the use of two different senses of the term ‘doubling trick’ so close together is unfortunate, and we’ll edit the indicated lines to remove the ambiguity.

Question 2: Hybrid Matrix is the Hybrid schema of Chan et al. instantiated with our unbounded matrix mechanism, so it's original to our work. To improve clarity, we'll modify the table to add a reference to the end of Section 5 where it's defined, and also edit that section to explicitly flag the fact that the algorithm discussed is the same as the 'Hybrid Matrix' in the table.