Summary
This paper studies the continual counting with differential privacy problem. Here there are $T$ time steps; at time step $t \\in [T]$, we receive a $x_t \\in \\{0, 1\\}$ and we have to output an estimate to the sum so far $x_1 + \\cdots + x_t$. We would like to entire stream of output to be differentially private (DP) w.r.t. changing a single entry $x_t$. Below we will discuss the privacy guarantees in terms of concentrated DP (CDP) but this can be easily translated to standard approximate-DP guarantee.
The classic binary tree mechanism [Chan et al., 2011; Dwork et al., 2010] solves this problem by building a complete binary tree with $T$ leaves, each representing $x_t$ for $t \in [T]$. Each node in the tree represents the sum of all leaves below. Appropriate noise are added to each node to make sure this data structure is private. When we want to output an estimate, we take the sum of the appropriate nodes; it is not hard to see that then number of nodes required are at most $O(\\log T)$. This gives error (standard deviation) for each estimate that is $O(\\log T)$, a significant improvement over the trivial algorithm (that release each estimate with independent noise)--which has error $O(\sqrt{T})$. The binary tree mechanism belongs to a class of mechanism called matrix mechanism based on a factorization of the "workload" matrix, which is the lower triangular all-1 matrix in the continual counting case. [Denisov et al., 2022] experimented with matrix mechanism and showed significant error improvement (more than 3x) over the binary tree mechanism. [Henzinger et al., 2023] gave an elegant factorization based on Toeplitz matrices and prove that it is asymptotically optimal.
Despite the (asymptotic) optimality of [Denisov et al., 2022, Henzinger et al., 2023], the algorithms are harder to implement than the binary tree mechanism. In particular, the noise generation requires $O(T)$ time and $O(T)$ space (for each update), whereas the binary tree mechanism (by keeping the noise only of the "active" node) requires only $O(1)$ amortized time (or $O(\\log T)$ worst case time) and $O(T)$ space. On the other hand, as stated above, the error of the binary tree mechanism is more than 3x larger than those of [Denisov et al., 2022, Henzinger et al., 2023]. This brings us to the contribution of this work: **the authors give an algorithm with the same time / space complexity as binary tree mechanism but with error reduced by a half** (so it is now only ~1.6x more than [Denisov et al., 2022, Henzinger et al., 2023]).
To understand the techniques, we need to discuss the binary tree mechanism in more detail. There are two important parameters that affect the error:
1. *Sensitivity*: This is the amount of contribution from each $x_t$ to the datastructure (measured in $\ell_2$ norm), which directly determines the scale of the noise needed to provide privacy.
2. *Number of nodes to combine*: This is the number of nodes that needs to be summed together to produce an estimate; the larger this number is, the larger number of noises get added together--leading to a larger error.
For 1., the observation (which is perhaps folklore) to start with is that we never use the right children when computing the estimates anyway, so we can remove these from the trees. This leaves us with an interesting situation: each $x_t$ does not have the same sensitivity. In particular, the number of nodes $x_t$ contributes to is now the number zeros in the binary representation of $t - 1$. For 2., it can be seen that different estimates requires adding up different number of nodes: specifically, the number of nodes needed for $x_1 + \\cdots + x_t$ is the number of ones in the binary representation of $t$. This leads to a rather natural and elegant strategy that the authors propose: instead of using all leaves, only use those that have equal number of zeros and ones in their binary representations. This reduces the sensitivity by $\\sqrt{2}$ and reduces the number of node to combined by a factor of $2$, leading to a total of $2$ saving in the standard deviation of the estimates compared to the vanilla binary tree mechanism. Note that since there are only $\\Theta(1/\\sqrt{T})$ fraction of leaves with equal zero-one in their binary representations, we actually have to look at a slightly higher tree than before, but this only contributes to $O(\log \log T)$--which is a lower order term--in the error.
## Post-Rebuttal Comments
Thank you the authors for the responses. As stated in my reply, I'd still strongly encourage the authors to clarify W2 and Q1 in more detail in the revision.
Strengths
- Continual counting is a basic problem in literature and this paper provides a significant improvement over the classic binary tree mechanism.
- The approach is very elegant is likely practical.
Weaknesses
- Although this paper's algorithm is more efficient than those in [Denisov et al., 2022, Henzinger et al., 2023], the error is still quite noticeably larger (by ~1.6x factor) for the same privacy level. Therefore, this is a tradeoff between time-space efficiency and privacy-utility tradeoff. In my opinion, the latter is typically more important in practice.
- The writing is not ideal:
- Main algorithm (Algorithm 2) is not presented in the main body.
- Despite discussing and using the high-dimensional version (where each $x_i$ is a $d$-dimensional vector) in the experiments, the main proof sections only consider the case where $x_i$ is a binary scalar.
- "Streaming support" and "same error distribution" is discussed in a possibly misleading manner (see the first two questions below in more detail).
Questions
- Line 57-58: "Unlike existing mechanisms it has the same error distribution in every step, which could make downstream applications easier to analyze." I am not sure why this is a big deal, since the noise distribution is just a Gaussian we can always just add another independent Gaussian to make it the same, right? (For example, if at the $t$-time step, my variance is $\\sigma_t^2$ whereas my worst case variance is $\\sigma_{\\max}^2$, then I can just add a noise drawn from $\\mathcal{N}(0, \\sigma_{\\max}^2 - \\sigma_t^2)$ to get the error distribution to be the same, right?)
- In Table 1, it is said that if we precompute the noise for Henzinger et al.'s algorithm, then we would not be able to support streaming setting. I do not understand why this is the case. Can you please elaborate? (Note that we have to be talking about fix time horizon $T$ anyway, since even your algorithm would need this to be able to set the noise magnitude.)
- Since Henzinger et al.'s factorization is pretty explicit (and has very nice form), is there any (informal) reason why one should think that it is hard to implement their algorithm using say polylogarithmic space and time?
- It seems like for your algorithm we only need the binary representation of every contributed time step minus one to have *at most* $h/2$ zeros and the binary representation of every queried time step to have *at most* $h/2$ ones. Since about half of the leaves have at most $h/2$ zeros (or $h/2$ ones), can you use this, instead of *exactly* $h/2$ to reduce the extra height to just $O(1)$ instead of the current $O(\\log \\log T)$? (Note that I think you do not need the contributed / queried leaves to be exactly equal; you only need a sequence $t_1, \dots, t_T$ for contribution and $q_1, \dots, q_T$ for queries that are interleaved, i.e. $t_1 \leq q_1 < t_2 \leq q_2 < \cdots < t_T \leq q_T$.)
## Minor comments
Below are minor comments to help the authors improve their revision. Please do *not* reply to them during rebuttal.
- Line 49: "algoritm" -> "algorithm"
- Line 91 - 94: I believe the fact that finding the optimal matrix mechanism can be formulated as a convex optimization problem was well known before [Denisov et al.]. See for example, the paper "Factorization Norms and Hereditary Discrepancy" by Matousek et al. and references therein.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.