A Smooth Binary Mechanism for Efficient Private Continual Observation
Authors: Joel Daniel Andersson
Rasmus Pagh
Venue: NeurIPS 2023 poster (2023)
Keywords: differential privacy
continual observation
binary mechanism
TL;DR: Reducing peak variance by up to 4x while retaining the space and time efficiency of the binary mechanism.

Abstract: In privacy under continual observation we study how to release differentially private estimates based on a dataset that evolves over time. The problem of releasing private prefix sums of $x_1, x_2, x_3,\dots\in${$0,1$} (where the value of each $x_i$ is to be private) is particularly well-studied, and a generalized form is used in state-of-the-art methods for private stochastic gradient descent (SGD).

The seminal binary mechanism privately releases the first $t$ prefix sums with noise of variance polylogarithmic in $t$. Recently, Henzinger et al. and Denisov et al. showed that it is possible to improve on the binary mechanism in two ways: The variance of the noise can be reduced by a (large) constant factor, and also made more even across time steps. However, their algorithms for generating the noise distribution are not as efficient as one would like in terms of computation time and (in particular) space.

We address the efficiency problem by presenting a simple alternative to the binary mechanism in which 1) generating the noise takes constant average time per value, 2) the variance is reduced by a factor about 4 compared to the binary mechanism, and 3) the noise distribution at each step is identical. Empirically, a simple Python implementation of our approach outperforms the running time of the approach of Henzinger et al., as well as an attempt to improve their algorithm using high-performance algorithms for multiplication with Toeplitz matrices.

A Smooth Binary Mechanism for Efficient Private Continual Observation
Joel Daniel Andersson
Rasmus Pagh
Basic Algorithms Research Copenhagen University of Copenhagen jda@di... ku. dk
Basic Algorithms Research Copenhagen University of Copenhagen pagh@di. ku. dk
Abstract
privacy under continual observation we study how to release differentially private estimates based on dataset that evolves over time. The problem of releasing private prefix sums of T3, ... E {0, 1} (where the value of each n, is to be private) is particularly well-studied, and generalized form is used in state-of-the-ar methods for private stochastic gradient descent (SGD). The seminal binary mechanism privately releases the first / prefix sums with noise of variance polylogarithmic in f. Recently, Henzinger et al. and Denisov et al. showed that it possible improve the binary mechanism in two ways: The variance of the noise can be reduced by (large) constant factor, and also made more even across time steps. However, their algorithms for generating the noise distribution are not as efficient as one would like in terms of computation time and (in particular) space. We address the efficiency problem by presenting simple alternative to the binary mechanism in which 1) generating the noise takes constant average time per value, 2) the variance is reduced by factor about compared the binary mechanism. and 3) the noise distribution at each step is identical. Empirically, a simple Python implementation of our approach outperforms the running time of the approach of Henzinger et al., as well as an attempt to improve their algorithm using gigh-performacc algorithms for multiplication with Toeplitz matrices.
Introduction
There many actors in society that wish to publish aggregate statistics about individuals, be it for financial or social utility. Netflix might recommend movies based on other users' preferences, and policy might be driven by information on average incomes across groups Whatever utility one has in mind however, it should be balanced against the potential release of sensitive information. While may seem anodyne publish aggregate statistics about users, doing it without consideration to privacy may expose sensitive information of individuals (Dinur & Nissim, 2003). Differential privacy offers framework for dealing with these problems
mathematically rigorous way.
particular setting is when statistics are updated and released continually, for example a website releasing its number of visitors over time. Studying differential privacy in this setup is referred to as differential privacy under continual observation (Dwork et al., 2010; Dwork & Roth, 2013). A central problem in this domain referred to differentially private counting under continual observation (Chan et al., 2011: Dwork et al., 2010), continual counting for short. It covers the following problem: binary stream J1, 22, -..--- --- is received one element at time such that x, is received in round t. The objective is to continually output the number of Is encountered up to each time step while maintaining differential privacy. We consider they are identical except for a single index where v, j x/. It suffices to study the setting in which there known upper bound T on the number of prefix sums release algorithms for the case of unbounded streams then follow by general reduction (Chan et al., 2011).
streams æ and x' as neighboring
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: Comparison between different p-zCDP mechanisms for continual counting.
Mechanism M
Var[M(tt]
2p Tog. T
Time to produce
Space
Matrix
all T outputs
type
Binary mech.
O(T)
O T)
sparse
Honaker Online
0.5 + o
Ollog T"
sparse
Denisov et al.
0.0487 ... + o(1)
(
(
dense
Henzinger et al.
0.0487 ... + o(1)
(T log T)"
O(T)
Toeplitz
Our mechanism
0.25 + o(1)
((T)
O T) sparse
"Honaker Online" refers to the "Estimation from below" variant in Honaker (2015) as implemented Kairouz, et al. (2021). There no explicit bound on variance in Denisov et al. (2022), but the method finds an optimal matrix factorization so it should achieve same variance as Henzinger et al. (2023) up to lower order terms. As to their efficiency, Denisov et al. (2022) contains empirical work for reducing the time and space usage by approximating the matrices involved sum of banded matrix and a low-rank approximation, but without formal guarantees. The time usage in assumes implementing the matrix-vector product using FFT. Leveraging FFT continual observation is not a novel approach ( (Choquette- Choo et al., 2023). All sparse matrices have O Olog T) nonzero entries per row column, and all dense matrices have (2(T nonzero entries- a Toeplitz matrix can be seen as intermediate in the sense of having ( unique diagonals, allowing for efficient storage and multiplication.
Aside from the natural interpretation of continual counting as the differentially private release of user statistics over time, mechanisms for continual counting (and more generally for releasing prefix sums) are used as subroutine in many applications. Such mechanism is for example used in Google's privacy-preeerving federated next word prediction model (McMahan & TThakuraa, 2022; Kairouz al., 2021; Choquette- Choou Choo et al., 2023), non-interactive local learning (Smith et al., 2017), in stochastic convex optimization (Han et al., 2022) and in histogram estimation (Cardoso & Rogers, 2022; Chan al., 2012; Huang et al., 2022: Upadhyay, 2019) among others.
Given the broad adoption of continual counting as a primitive, designing algorithms for continual counting that improve constants in the error while scaling well in time and space is of practical interest.
1.1 Our contributions
In this paper we introduce the Smooth Binary Mechanism, differentially private algorithm for the continual counting problem that improves upon the original binary mechanism by Chan al. (2011);
Dwork et al. (2010) in several respects, formalized in Theorem 1.1 and compared to Table
Theorem 1.1 (Smooth Binary Mechanism). For any p > 0, T > 1, there is an efficient p-zCDP continual counting mechanism M, that receiving binary stream of length T satisfies
Var[M[[1] 1 (1) (T)
8p
where M(t) is the ousput prefix sum at time f, while only requiring Ollog T) space, O(T) time to output all T prefix sums, and where the error is identically distributed for all 1 S S T.
Our mechanism retains the scalability in time and space of the binary mechanism while offering an improvement in variance by a factor of 4 - o(1). It also has the same error distribution in every step by design, which could make downstream applications easier analyze.
Sketch of technical ideas. Our starting point is the binary mechanism which, in nutshell, uses a complete binary tree with T + 1 leaves (first T leaves corresponding to .1,..... .T) in which each node contains the sum of the leaves below, made private by adding random noise (e.g. from Gaussian distribution). To estimate prefix sum Σi= we follow the path from the root to the leaf storing F1+1. Each time we go to a right child the sum stored in sibling node is added to a counter. An observation, probably folklore, is that it suffices to store sums for nodes that are left children, so

---

suppose we do not store any sum in nodes that are right children. The number of terms added when computing the prefix sum is the number of is in the binary representation bin(t) of t. which encodes the path to the leaf storing 2-+-1- The sensitivity of the tree with respect to Ft, i.e., the number of node counts that change by if xe changes, is the number of Os in bin(t 1). Our idea is to only use leaves that have balanced binary representation, i.e. same number of Os and Is (assuming the height of the tree is an even integer). To obtain I useful leaves we need to make the tree slightly deeper - it turns out that height h slightly more than logz(T)) suffices. This has the effect of making the sensitivity every leaf h/2, and the noise in every prefix sum a sum of h/2 independent noise terms.
Limitations. As shown in Table I and Section 4, the smooth binary mechanism, while improving on the original binary mechanism, cannot achieve as low variance as matrix-based mechanisms such as Henzinger et al. (2023). However, given that the scaling of such methods can keep them from being used in practice, our variant of the binary mechanism has practical utility in large-scale settings.
1.2 Related work
All good methods for continual counting that we are aware of can be seen as instantiations of the factorization mechanism (Li et al., 2015), sometimes also referred to as the matrix mechanism. These methods perform a linear transformation of the data, given by matrix R, then add noise according to the sensitivity of Rr, and finally obtain the sequence of estimates by another linear transformation given by a matrix L. To obtain unbiased estimates, the product L.R needs to be equal to the vector of prefix sums, that is, LR must be the lower triangular all is matrix.
Seminal works introducing the first variants of the binary mechanism are due to Chan, Shi, and Song (2011) and Dwork, Naor, Pitassi, and Rothblum (2010), but similar ideas were proposed independently in Hay, Rastogi, Miklau, and Suciu (2010) and Gehrke, Wang, and Xiao (2010). Honaker (2015) noticed that better estimators are possible by making use of all information in the tree associated with the binary tree method. A subset of their techniques can be leveraged to reduce the variance of the binary mechanism by up to a factor 2, at some cost of efficiency, as shown from their implementation in Kairouz, Mcmahan, Song, Thakkar, Thakurta, and Xu (2021).
A number of recent papers have studied improved choices for the matrices I,, R. Denisov, McMahan, Rush, Smith, and Thakurta (2022) treated the problem of finding matrices leading to minimum largest variance on the estimates as convex optimization problem, where (at least for T up 2048) it was feasible to solve it. To handle a larger number of time steps they consider a similar setting where a restriction to banded matrices makes the method scale better, empirically with good error, but no theoretical guarantees are provided.
Fichtenberger, Henzinger. and Upadhyay (2023) gave explicit decomposition into lower triangular matrices, and analyzed its error in the fox metric. The matrices employed are Toeplitz (banded) matrices. Henzinger, Upadhyay, and Upadhyay (2023) analyzed the same decomposition with respect to mean squared error of the noise, and showed that it obtains the best possible error among matrix decompositions where L and R are square matrices, up factor + o(1) where the o(1) term vanishes when I' goes to infinity.
A breakdown of how our mechanism compares to existing ones is shown in Table 1. While not achieving as small an error as the factorization mechanism of Henzinger et al. (2023), its runtime and small memory footprint allows for better scaling for longer streams. For concreteness we consider privacy under p-zero-Corr Conee-Coneedteteed Differential Privacy (zCDP) (Bun & Steinke, 2016), but all results can be expressed in terms of other notions of differential privacy.
2 Preliminaries
Binary representation of numbers. We will use the notation bin(n) to refer to the binary repre- sentation of number n E [2*], where h > 0 is an integer, and let bin(n) be padded with leading zeros to h digits. For example, bin(2) 0b010 for tree of height h = 3. When indexing such a number we let index i refer to the tth least significant bit, e.g. bin(2); 1. We will also refer to prefixes and suffixes of binary strings, and we use the convention that a prefix of a binary string includes its most significant bits.
3

---

Partial sums (p-sums), To clear the notation we use the concept of p-sums ][ij]] where E(i Ei=s Tt. We will furthermore the concept of noisy p-sums
E[t = | [i, Xiij]
where F a suitable distribution for the DP paradigm, e.g. Laplacian or Gaussian. For convenience we also define i = Eit, f i.c. T is the single stream element with noise added.
2.1 Continual observation of bit stream
Given an integer T 1 we consider finite length binary stream ( (2,,,, ,TT) where Ie E [0, 1). & i S T, denotes the bit appearing in the stream at time f.
Definition 2.1 (Continual Counting Query). Given a stream æ E (0, 13", the count for the stream a mapping c: (1....,T) + Z such that c(t) E Zz.
Definition 2.2 (Counting Mechanism), A counting mechanism M takes a stream r E 1) and produces (possibly random) vector Mr E IR" where (Ma)e is a function of the first elements of the stream. For convenience we will write M(I) for (Ma), when there is little chance for ambiguity.
To analyze a counting mechanism from the perspective of differential privacy, we also need a notion of neigboring streams.
Definition 2.3 (Neighboring Streams), Streams x, x' E {0, 13 are said to be neighboring, denoted x ~ x', if Hi x; & xtH 1.
Intuitively, for counting mechanism to be useful given time t, want it to minimize (.((t) c(t)]. We consider unbiased mechanisms that return the true counts in expectation and we focus on minimizing Var[M[t) c(t)].
2.2 Differential privacy
For a mechanism to considered differentially private, we require that the outputs for any two neighboring inputs are are indistinguishable. We will state our results in terms of p-ZCDP:
Definition 2.4 (Concentrated Differential Privacy (zCDP) (Bun & Steinke, 2016)). For p > 0, randomized algorithm A X + y is p-zCDP if for any D D', (a(()))))))((')) S pa for all 1, where (A( (I)(()((())))) A(D))) is the a- a-Rényi divergence between A(D) and A(D').
In the scenario where we are looking to release real-valued function fD) taking values in Rd, we can achieve zCDP by adding Gaussian noise calibrated the éz-sensitivity of f.
Lemma 2.5 (Gaussian Mechanism (Bun & Steinke, 2016)). Let X RRd be function with global fz-sensitivity A == maxD~D (IS(D) - S(D')l For a given data set D E X", the mechanism that releases ((D) N00 4²yd satisfies p-zCDP.
is known that p-zCDP implies (p 2/ (ll0)))))) 0) diffferrrttia privacy for every ó > 0 (Bun & Steinke, 2016).
Lastly, when comparing counting mechanisms based on Gaussian noise, we note that it is sufficient to look at the variance. For a single output M(t), the variance Var[M(tt] is the only relevant metric, as it completely describes the output distribution. For series of outputs My, and related norms [|MM we note that a mechanism with lower variance will be more concentrated each coordinate and have lower th moment, allowing for tighter bounds the norm.
2.3 Differentially private continual counting
We next describe two approaches continual counting.
Binary mechanism. The binary mechanism (Chan et al., 2011; Dwork et al., 2010; Gehrke et al., 2010; Hay et al., 2010) can be considered the canonical mechanism for continual counting. this section we present variant of it where only left subtrees are used. The mechanism derives its name

---

from the fact that binary tree is built from the input stream. Each element from the stream is assigned leaf in the binary tree, and each non-leaf node the represents a p-sum of all elements in descendant leaves. All values are stored noisily in nodes, and nodes are added together to produce a given prefix sum. Such a binary tree is illustrated in Figure (a))
8/1.8
$114
E[L.4]
E|5.8
Ejj.
2
333.4]
E,S,
E. S)
Qkarr
06011
BAL
Gb111
M(6)
Sp,4] 4] + $/5, 6)
(a) Binary mechanism tree for T
Computation M(6) using Algorithm
Figure Binary trees for sequence of length T In Figure 1(b) each leaf labeled by bin(t- (ifft-1).. 1), and it illustrates how the prefix sum up to t 6 can be computed from bin(t). Blue nodes describe the path taken by Algorithm 1. and the sum of red nodes form the desired output M(6).
We will return for closer analysis of the binary mechanism in Section 3.1. For now we settle for stating that the p-zCDP binary mechanism achieves Var (t)] O(logT)?) and known be computationally efficient: to release all prefix sums up to given time < T requires only O(log(T)) space and (1) time.
Factorization mechanism. The binary mechanism belongs more general class of mechanisms called factorization mechanisms (Li et al., 2015), sometimes also referenced as matrix mechanisms. Computing prefix sum is linear operation sums up to given time can therefore be represented by a matrix A is here a lower-triangular matrix of all 1s. The factorization mechanism characterizes solutions to the continual counting problem by factorizing as A = LR with corresponding mechanism M2 L(Rz + 2), F where is the dimension of Rz.
the input stream E R² and computing all prefix
RTx,, where c(t) = (Ax),
Intuitively represents linear combinations of the stream, which are made private by adding noise 2, and which then are aggregated by L. To achieve p-zCDP for this mechanism, we let ~ NO, A )" 2p
where A max; || e, being the 7th unit vector. follows that the corresponding output noise becomes Lz with coordinates (Lz), ~ N(0, A 111) where Lj is the jth row in L.
Extension to multidimenssonall input. While we have so far assumed one one-dimensional input, any one-dimensional p-xCDP factorization mechanism naturally generalizes to higher dimensions. This fact enables factorization mechanisms to be applied to the problem of private learning where gradients are summed. We sketch an argument for this fact Appendix
Our mechanism
To introduce variant of the binary mechanism, need to return to the original mechanism.
3.1 Closer analysis of the binary mechanism
As has been pointed out earlier work (Denisov et al., 2022; Henzinger et al., 2023), naive implementation of the binary mechanism will lead to variance that is non-uniform with respect to time: the number of in the bitwise representation of determines the variance. To underline this, consider the pscudo-code in Algorithm I for computing prefix sum given binary mechanism tree structure. The code assumes that the tree has 2 t + leaves, detail that only matters when is power of and allows us to never use the root node. To illustrate simple case, see Figure 1(b).
5

---

Algorithm Prefix Sum for Binary Mechanism
Input: binary tree of height h storing Σ(a, b] for & t, time I 2"
2: outpul f- 0
3: bin(() (padded to h bits by adding zeros}
4: f- 1; 2A
5: for = to do
6: d -
7: if'
then
8:
output + output + E(a, d] + d
9:
10: else
11: b <- d
12:
end if
end for
14:
return output
We make the following two observatons:
bin(t - 1) encodes path from the root to the leaf where æ; is stored.
To compute prefix sums using Algorithm I, we only need to store values in "left children".
Combining these observations, we get the following result:
Proposition 3.1. The squared (2-sensitivity A of xt is equal to the number of Os in bin(L 1).
To see this, note that the number of Os in bin(t - 1) is equal to the number of left-children that are passed through to reach the given node. Changing the value of z; impacts all its ancestors, and since only left-children are used for prefix sums, the result immediately follows. This does not address the volatility of variance with respect time. However, studying Algorithm 1 gives the reason:
Proposition 3.2. Var(M(1) is proportional to the number of Is in bin(t).
The result follows from the fact that the number of terms added together for a given prefix sum e(() equal to the number of Is in bin(t), since Line is executed for each such 1. In this view, each node that is used for the prefix sum at time t can be identified as a prefix string of bin(t) that ends with a I.
We will return to Proposition 3.1 and Proposition 3.2 when constructing our smooth mechanism, but for now we settle for stating that combined they give the exact variance at each time step for the binary mechanism. Following Li et al. (2015), to make the mechanism private we have to accommodate for the worst sensitivity across all leaves, which yields Theorem 3.3.
Theorem 3.3 (Exact Variance for Binary Mechanism (Chan et al., 2011; Dwork et al., 2010)). For any > 0, T 1, the p-zCDP binary mechanism M based on Algorithm I achieves variance
Var[M(t)] [log(T (T +1] [|bin(t]]l
2p
for all 1 < T, where [[bin(t]], is equal to the number of is bin(t).
3.2 A smooth binary mechanism
Based on the analysis, a naive idea to improve the binary mechanism would be to only consider leaves with "favorable" time indices. To make this bit more precise, we ask the following question: could there be a better mechanism in which we store elements in only a subset of the leaves in the original binary tree, and then use Algorithm
compute the prefix sums? We give an affirmative answer.
Consider a full binary tree of height h where we let the leaves be indexed by i (1-indexed). Given sequence of elements E {0, 1 (we assume great enough height h to accommodate for all elements) and an integer < < h, we conceptually do the following for each leaf with index i:
If bin(i- 1) has & Os, store the next element of the stream in the leaf.
Otherwise store token ( in the leaf.

---

More rigorously stated, we are introducing an injective mapping from time to leaf-indices m (I...., + 1 + [2 + 11. such that m(t) is the (t 1)st smallest h-bit integer with &s Os in its binary representation. gets stored in the leaf with index m(), and to compute M((), we would add p-sums based bin(m(t + 1)). The resulting algorithm is listed as Algorithm where Eit is the noisy count of leaf through
Algorithm 2 Prefix Sum for Smooth Binary Mechanism
1: Input: binary tree of height /t storing Da,, bj for & z m(t), time where m(t + 1) - 2
2: output 0
3: bin(m(t 1)) (padded h bits by adding zeros}
4: a - 1;b+ 2
5: for
do
7: s; then
8: output + output + Ela,d) d]
9: ++++1
10:
else
1--d)
12:
end if
13:
end for
14:
return output
It follows that the fy-sensitivity is equal to Vk, and that any prefix sum will be sum of k nodes. Importantly, the latter fact removes the dependence on for the variance.
Choosing k. The optimal choice of k depends on the differential privacy paradigm. Here we only consider p-zCDP where A = Vk. Since each prefix sum is computed as a sum of h - k nodes, & which for = h/22 gives the variance for a given prefix sum becomes Var[M[tt)] = (h - k) "p" leading constant of 1 1/4 compared to the maximum variance of the binary mechanism. This choice of is valid if the tree has an even height h, and maximizes the number of available leaves. Such tree together with computation is shown in Figure 2.
EIL.8
E[L. 4
E.9.
12
E11
E 6
Ejoo
Obenoo
0b6001
086010
bin (Tm()) 060011
080100
gr010 mroea 101
bind binfin 4)) =n ded
Con 6)) in 000
bont (onfon()) (0)) e0ttti
1900
bio (mm))
bin (3))
M(5) E]1.8 $19. 12]
Figure 2: Computation of M(5) using the smooth binary mechanism where T = 5. The figure illustrates how the prefix up to can be computed from bin(m(t + 1)). Blue nodes describe the path taken by Algorithm 2, and the sum of red nodes form the desired output M(t). All values shown in nodes are stored noisily, and E[i,]] is here defined as the of leaves through Observe that the noise in each node is drawn from the same distribution and that each query is formed by adding together h/2 2 noisy nodes, implying an identical distribution of the error at each step.

---

A penalty in height. The analysis above assumes that we have tree of sufficient height. If we before had a tree of height [log(T 1)], we now need a tree of height h 2 [log(T + 1)] to have enough leaves with the right ratio of is in their index. To account for this, we let h be the smallest even integer such that [log(T)] a log log T, where is constant. For our new tree to support as many prefix sums, we need that (1/2) 2 T + This holds for a > 1/2 and sufficiently large T, but we show it for = next. Using Stirling's approximation in the first step, we can establish that 2 T+log log
h
2h
log
T
h/2
22h
[og 71 V2v
loglog log
V2 /2/noo T + log log T
which is at least T + 1 for T 2 13.
Resulting variance. This height penalty makes Var[M(t)] longer scale as log(T + 1) but (Iog(T) a log log(T))² Nevertheless, we can state the following: Lemma 3.4. For any p 0, T 13, the p-aCDP smooth binary mechanism M achieves variance
Var[M(U)] = 1 o(1
log(T)²
8p
where s T, and the o(1) term is at most
2 log log(T) log(?)
log log(T)) (Tog(T)) Tog(T)
which is an improvement over the original binary mechanism by a factor of 1/4 with regard the leading term. This improvement is shown empirically in Section 4.
Constant average time per output. When outputting T prefix stream, we only have to store the noise of the nodes, not the p-sums themselves. To make this more explicit, let S, describe the set of nodes (p-sum indices) that the smooth mechanism adds together to produce the output at time t. To produce Mit + given MMt), we effectively do:
continuously while reading
M(t + M(t) I4+1+
Σ (K.))SS
X
Σ Xi,J1
(5.))88,
To quantify the cost, we need to deduce how many nodes are replaced from to t + 1, which means reasoning about St and S1+1. Recalling that each element in S, can identified by a prefix string of bin(m(t++ (f(++++)) 1)) terminating with a 1, consider Figure 3. Based on the pattern shown in Figure 3, where the leaf indices only differ in their least significant bits, we get that SS++1 \ \ |S, \ Se+1 = n, where n is the number of is in the least significant block of 1s. We formalize this observation next to give bound on the average cost when outputting a sequence of prefix sums.
Lemma 3.5. Assuming the cost of replacing a node in prefix sum is 1, then the cost to release all
(2k) - 1 prefix sums in the tree of height 2k using the smooth binary mechanism is at most 2 (2k).
Proof. As argued before, to compute M(t + 1) given M(t) we need to replace a number of nodes equal to the size of the least significant block of is in bin (mi(t + 1)). We can therefore directly compute the total cost by enumerating all valid indices with different block sizes as
b 2k-n-1
k
2h k-n
cost = k Σ
Σ
n
= =
Σ
n
(+=++1)
k n2
n=1
k-n
n=1
- Σ
k
1-1+)
- 2k
1)
2k 1) -
(2k
(2k
(2k
1
11
where the initial term comes from excluding the last balanced leaf index tree.
bin(m(t + 1)) =
0 bin(m(t + +2)
0
n
Figure 3: The least significant bits of two leaf indices in a full binary tree that are neighboring with respect time when used in the smooth binary mechanism. If the first cluster of Is in bin(m(t + 1)), counted from the least significant bit, has n Is then nodes in total will be replaced from t to

---

In particular, this implies that the average cost when releasing all prefix sums in a full tree is S 2. For T that does not use all leaves of a tree, comparing to the closest T where T T 22 also implies an average cost of I 4 for arbitrary T. For a single output the cost is (log((T)) It is not hard to check that computing bin(m(( + 1)) from bin(m((() be done in constant time using standard arithmetic and bitwise operations on machine words.
Logarithmic space. The argument for the binary mechanism only needing (log((T) space extends to our smooth variant. We state this next in Lemma 3.6, and supply a proof in the appendix.
Lemma 3.6. The smooth binary mechanism computing prefix sums runs in OTlog(T)) space.
Finishing the proof for Theorem 1.1. The last, and more subtle, property of our mechanism is that the eπror at each time step not only has constant variance, but is identically distributed. By fixing the number of 1s in each leaf index to k, the output error at each step becomes the k-fold convolution of the noise distribution used in each node, independently of what that distribution is. Our mechanism achieves this by design, but note that this can be achieved for any other mechanism (e.g. the regular binary mechanism) by adding fresh noise in excess of what gives privacy (at the expense of utility). Combining Lemmas 3.4, 3.5 and 3.6 together with this last property, we arrive Theorem I.I.
4 Comparison of mechanisms
In this section we review how the smooth binary mechanism compares to the original binary mechanism, and the factorization mechanism of Henzinger et al. (2023). A Python implemen- tation of our smooth binary mechanism (and the classic binary mechanism) can be found on https:// ttts:///gttttttt htt//ooommeeeeeee htwtteerr//o//heeeeeeee mamooothbbinryyymehhhhe et al. (2022) since their method is similar to that of Henzinger et al. (2023) in terms of error, and less efficient in terms of time and space usage. We also do not compare to the online version of Honaker (2015) as it is less efficient in time, and its improvement in variance over the binary mechanism is at most a factor of 2, and can therefore be estimated from the figures.
imm We do not compare to Denisov
Variance comparison. To demonstrate how the variance behaves time for smooth binary mechanism, see Figure 4. Given a fix T, the tree-based mechanisms compute the required tree height
Henoleges
25
Our Mechonien
Binary Mochanien
40
400 00:00
250
Our Mecharion
Biurry Madiunion
mix, ST Var M(())
20
VarlMie)]
150
100
10
50
100
160
200
260
100
10.
10a
10a
10a
10
107
time
opper bound on time
(a) Running variance for T 250.
(b) Maximum variance vs. upper bound on time.
Figure 4: Comparison of variance between the mechanism in Henzinger et al. (2023), the standard binary mechanism and our mechanism. Figure 4(a) shows Var Var[M(t)),fo < S T for T 250. whereas Figure 4(b) shows the maximun variance that each mechanism would attain for a given upper bound on time. At the last time step in Figure 4(b), our mechanism reduces the variance by factor of 3.27 versus the binary mechanism.
to support all elements, and the factorization mechanism a sufficiently large matrix. The volatility of the error in the regular binary mechanism is contrasted by the stable noise distribution of our smooth binary mechanism, as demonstrated in Figure 4(a). In terms of achieving the lowest variance, the factorization mechanism in Henzinger et al. (2023) is superior, as expected. This result is replicated in Figure 4(b) where our mechanism offers substantial improvement in terms of maximum variance over the original binary mechanism, but does not improve on Henzinger et al. (2023).

---

Computational efficiency comparison. While our mechanism does not achieve as low noise as the mechanism Henzinger al. (2023), scales well time and space, and with respect the dimensionality of the stream elements. This is empirically demonstrated in Figure 5. Since the matrix
Hentinger motredl soepl2
*65
max # of floats nesded to be stored
10"
Housinge et
Biraay Mechasion
Bizary Mechaniiz
Our Mezhoriom
Our Mechanien
insfoupuu
10a
10"
10a
10a
10f
10a
10a
10a
10a
10a
10a
10
number d-dimensional vectors
upper hound on time
(a) Average computational time per output.
(b) Maximum space needed vs upper bounds on time.
Figure 5: Comparison of computational efficiency between the mechanism in Henzinger et al. (2023), the binary mechanism and our mechanism. Figure 5(a) shows the computation time spent per d- d-dimensional input. The simulation was run times for each method, meaning each method has 5 data points in the plot per time step. The computation was performed for elements of dimension d = 10*, was run on Macbook Pro 2021 with Apple M1 Pro chip and 16 GB memory using Python 3.9.6, scipy version 1.9.2, and numpy version 1.23.3. Figure 5(b) shows the maximum number of floats that has to be stored in memory when outputting all prefix sums up to given time, assuming binary input.
used in Henzinger et al. (2023) is Toeplitz matrix, the scipy method "matmul toeplitz" (based on FFT and running in time Odd log T) to produce dddimensional output) was used to speed up the matrix multiplication generating the noise Figure 5(a).
The discrepancy the computation time scaling can largely be attributed to space: the needed space for these tree-based methods scales logarithmically with T, and linearly with T for matrix- multiplication based methods. This is demonstrated in Figure 5(b). As to the difference in computation time between the tree-bat tree-based methods, the smooth binary mechanism generates twice much fresh noise per time step on average, which likely is the dominating time sink in this setup.
Conclusion and discussion
We presented improved "smooth" binary mechanism that retains the low time complexity and space usage while improving the additive error and achieving stable noise at each time step. Our mechanism was derived by performing a careful analysis of the original binary mechanism, and specifically the influence of the binary representation of leaf indices in the induced binary tree. Our empirical results demonstrate the stability of the noise and its improved variance compared to the binary mechanism. The factorization mechanism of Henzinger et al. (2023) offers better variance, but is difficult scale large number of time steps, especially if we need digh-diimesional noise.
We note that the smooth binary mechanism can be extended to e-DP. The optimal fraction of 1s in the leaves of the binary tree would longer be 1/2. An interesting problem is to find mechanisms that have lower variance and attractive computational properties. It is possible that the dependence on T can be improved by leaving the factorization mechanism framework, but in absence of such result the best we can hope is to match the variance obtained by Henzinger et al. (2023).
10

---

Acknowledgments and disclosure of funding
We would like to thank Jalaj Upadhyay for useful discussions about our results and their relation to previous work. We would also like to thank the reviewers for their comments and suggestions which have contributed to a clearer paper. The authors are affiliated with Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582, and are also supported by Providentia, Data Science Distinguished Investigator grant from Novo Nordisk Fonden.
References
Bun, M. and Steinke, Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Hirt, M. and Smith, A. D. (eds.), Theory of Cryptography 14th International Confer- ence, TCC 2016-B, Beijing, China, October 31 November 3, 2016, Proceedings. Part I, volume 9985 of Lecture Notes in Computer Science, pp. 658, 2016. doi: (0.1007/978-3--62-5666 24. URL wtthttsss///oo org/ 1007 / 990/ -22-666225---22220
Cardoso, A. R. and Rogers, R. Differentially private histograms under continual observation: Streaming selection into the unknown. In Camps-Valls G., Ruiz, F. J. R., and Valera, (eds.), International Conference
Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pp. 2397-2419. PMLR, 2022. URL httptt:p:/pppooceeeiiie
mlr preas//111//rivvre-crroooo
html.
Chan, T.-H. H., Shi, E., and Song, D. Private and Continual Release of Statistics. ACM Transactions on Information and System Security, 14(3):26:1-26:222)) November 2011. doi: 10. 10.1 00.1145/2043621. 2043626. URL https://dol //to:///dooooe/ /tt/doi.or//////////// org/oogg/// 10. 1145/2043621111111 2043626.
Chan, T. H. H., Li, M., Shi, E., and Xu, W. Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams. In Fischer-Hübner, S. and Wright, M. (eds.), Pri- vacy Enhancing Technologies, Lecture Notes in Computer Science, pp. 140-159, Berlin, Heidel- berg, 2012. Springer. doi: 10. (0.1007/978-3--42-36668 178-3-642-31680-77-5
URL https: (eeddoi.og////// wrw.o..../........oooooo.... 1007/
Choquette-Choo, C. A., Ganesh, A., McKenna, R., McMahan, H. B., Rush, K., Thakurta, A. G., and Xu, Z. (Amplified) banded matrix factorization: A unified approach to private training, 2023. URL https://arxiv org/ abs /236. 08153. Appears NeurlPS 2023.
Proquette-Choo A., McMahan, H. B., Rush, J. K., and Thakurta, A. G. Multi-epoch matrix factorization mechanisms for private machine learning. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 5924-5963. PMLR, 2023. URL /ttps::/proceede:e v202/ choquette-choo23...... html.
mlr. alr.press/
Denisov, S., McMahan, H. B., Rush, J. Smith, A. D., and Thakurta, A. G. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In NeurlPS, 2022. URL http://papers mips cctpaper_fillleecceeee sacpeerfflls/paeeee httpee/teeeeeappe///////aaaaae/ /ppper//0222/aah/ 27 27
Confctt-oooeefeeeeee html.
Dinur, I. and Nissim, K. Revealing information while preserving privacy. In Proceedings of the !wenly-second ACM SIGMODD-SGAACT-SIGAAA PODS '03, pp. 202-210, New York, NY, USA, June 2003. Association for Computing Machinery. doi: 10.11457773133.773173 URL https://doi. org/ wwtpg/....../////1 1145/773153. 1155/7711113..77777.. 773173.
symposium on Principles of database systems,
Dwork, C. and Roth, A. The Algorithmic Foundations of Differential Privacy. Foundations and Trends@ in Theoretical Computer Science, 9(3-4):211-407 2013, doi: 10.156//0400000042. URL
bttps:///or org/19 10. 1561/0440000044..
Dwork, C., Naor, M., Pitassi, T., and Rothblum, G. N. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium Theory of computing, STOC 10, pp. 715- 724, New York, NY, USA, June 2010. Association for Computing Machinery. doi: 10.1 145/ 1806689. 1806787. URL https: //op::://oo.... /twii///i..o//// http://doo..o/////// 10//10..1 0114//1106688 1806787.

---

doi: 10. 10000//0777--01-033000 Fichtenberger, H.. Henzinger, M., and Upadhyay, J. Constant matters: Fine aene-graied error bound on differentially private continual observation. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference on Machine Learning, ICMI, 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 10072-10092. PMLR, 2023. URL https: /ppoe//e////c/ssssss mlr, www.mmrer..//...e.....e..e press/v202) fichtenberger23a.. htm..
Gehrke, J., Wang, G., and Xiao, X. Differential privacy via wavelet transforms. In 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), pp. 225-236, Los Alamitos, CA, USA, mar 2010. IEEE Computer Society, doi: 10.1 10.1109/CDDE22200.544400 2010 5447831.
URL https:
//doi. www.eccnpterssroceerr.....o org/or..///.
Han, Y., Liang, Z.,, Liang, Z., Wang, Y., Yao, Y., and Zhang. J. Private Streaming SCO in lp geometry with Applications in High Dimensional Online Decision Making, In Proceedings of the 39th International Conference on Machine Learning, pp. 8249-8279. PMLR, June 2022. URL https://proceeding: mlr wwt.:mml.....e..eeeeeemee hww.1///hhan...... htm.m2m2........
Hay, M., Rastogi, V., Miklau, G., and Suciu, D. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow. 3(1-2):1021-1032 sep 2010. doi: 10. 14778/ 1920841.1920970. URL https: //dii. org/ 14778/1920844 1920970.
Henzinger, M., Upadhyay, J., and Upadhyay, S. Almost tight error bounds differentially private continual counting. In Proceedings of the 2023 Anmual ACM-SIAM Symposium on Discrete Algorithums (SODA), pp. 5003-5039, 2023. doi: 090111377.778111117775444444
URL https:
//epubs. sernsbbssiia...m siam. httgg/do/abb///ee 100 1117711197111119775555444 ch183.
Honaker, J. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26-27, 2015.
Huang, Z., Qiu, Y., Yi, K., and Cormode, G. Frequency estimation under multiparty differential pri- vacy: one-shot and streaming. Proceedings of the VLDB Endowment, 15(10):2058 2070, Septem- ber 2022. doi: 10. 10.14478/354730533447312 URL
3547312.
Kairouz, P., Mcmahan, B., Song. S., Thakkar, O.,, Thakurta, A., and Xu, Z. Practical and Private (Deep) Learning Without Sampling or Shuffling. In Proceedings of the 38th International Conference Machine Learning, pp. 5213-5225 PMLR, July 2021. URL https://proceedingss mlr.
press/v139/kairouzz2
html.
Li, C., Miklau, G., Hay, M.. McGregor, A., and Rastogi, V. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24(6)7757-781, December 2015. URL https: /tt. orgg
McMahan, H. B. and Thakurta, A. Federated Learning with Formal Differential Privacy Guarantees, 2022. URL https: / //ai.//aa/// googleblog.
html. Accessed online 2023-05-15.
Smith, A., Thakurta, A., and Upadhyay. J. Is Interaction Necessary for Distributed Private Learning? In 2017 IEEE Symposium on Security and Privacy (SP), pp. 58-77, May 2017. doi: 10.//O 2017.35. URL
1109/SP .017 35.
Upadhyay, J. Sublinear Space Private Algorithms Under the Sliding Window Model. In Proceedings of the 36th International Conference on Machine Learning, pp. 6363-6372, PMLR, May 2019. URL https://proceedings. mlr. .resss/ /v97 htt//v9//////// ht97//paaaayy19a...m html.
12

---

A Proof of Lemma 3.6
The proof of Lemma 3.6 was omitted from the main text, is given next.
Proof. The critical observation to make is that once a given p-sum is removed from prefix sum, then will never re-appear. Let its associated prefix string at time be 8 of length If we look the same bit positions in bin(m(()) as l increases and interpret it as number, then it is monotonously increasing with This implies that once given prefix-strnng s in bin(m(()) disappears then it will not be encountered again. We can therefore free up the memory used for storing any p-sum the moment it is no longer used. Because of this, it suffices to only store the p-sums in the active prefix sum at any time, of which there are most (log(T))) proving the statement.
>
B Factorization mechanisms on multidimensional input
Assuming a d-dimensional input stream with elements I; E Rdd let two streams x, x' be neigboring if they differ at exactly one time step t where || xz I 1. Given one-dimensional p-zCDP factorization mechanism for continual counting with factorization A = LR, we want to argue that running it along each dimension separately gives a p-zCDP factorization mechanism for releasing prefix sums on x.
To this, consider the new, flattened vector input z E Rd where I [(æ1)1, (x1)2...., (æ1)a: (IT) i... (xe)) = ((--1)a4j- Analogously for these new inputs, we can define counting matrix À = A @ laxd E IRd xd-T that sums each dimension separately, where @ is the Kronecker product and Iaxa is the d-dimensional identity matrix. We get a corresponding factorization À LR where L = + Laxd and R + laxd-
follows immediately that, Ż, R gives a factorization mechanism for privately releasing Až, and from it we can extract all private prefix sums on the original stream Letting H' be the vector representation the stream x' x., we will reason about the fz-sensitivity A next. First observe that for neighbouring inputs and x' that differ at time we have:
R(E x') .>|12 = =|eeell2 1 - 1e-5lla 8'll2
and therefore
R(E و)|| max |Rell2
sup ビーン
sup Bmal!
|| F'll2 max |e
which equates the fz-sensitivity of the mne-dimnnsionl case. Recapitulating, any one-dimensional p-zCDP factorization mechanism for continual counting is also a p-zCDP counting mechanism for inputs of higher dimension, as long as the neighoring relation is appropriately extended.
13


Reviews:
[{"review_id": "jXwzoxitZ3", "reviewer": "Reviewer_3m6M", "summary": "This paper studies the problem of releasing private prefix sums in the continual release model of differential privacy. A continual release mechanism for prefix sums receives a binary stream $x_1, x_2, x_3, ...$ one element at a time and continually outputs, at each time step, the number of ones received so far.  This problem can be solved by deploying the binary tree mechanism introduced by the concurrent works of Dwork et. al. and Chan et al. from 2010. In this manuscript the authors provide a variant of the binary tree mechanism that preserves its asymptotic space complexity while achieving better variance than the base mechanism. While the variance of the proposed smooth binary tree mechanism is higher than that of the matrix mechanism proposed by Henzinger et. al., the smooth binary tree scales better in time and space, with respect to the dimensionality of the stream elements. Finally, the authors claim that the error of this mechanism is identically distributed for all outputs of the mechanism.", "questions": "Is there a reason that you do not consider any specific notions or provide any formal statements and proofs about the error of the smooth mechanism? \n\nIn line 221 you say that the maximum sensitivity is proportional to $k$. I understand that this is true for your choice of $k=h/2$ but as far as I can tell, it need not be true in general, right? (Since the maximum sensitivity of a particular node is technically proportional to $h-k$, which need not be proportional to $k$?)\n\n-------------------\n\n-------------------\n\nTypo(s) and minor comments:\n\nOn line 112 you say “let $\\mathsf{bin}(n)$ be padded with leading to $h$ digits.” This sentence is missing the word zeroes.\n\nThere seems to be a mistake in line 68: It says that the sensitivity of some node $x_t$ is the number of zeroes in  $\\mathsf{bin}(t-1)$. Isn't it actually $\\mathsf{bin}(t-1) + 1$? (Also, line 68 occurs prior to the definition of $\\mathsf{bin}(\\cdot)$ which doesn’t appear till line 113.) A similar problem to that in line 68 occurs in the statement of proposition 3.1 on line 190, which is a formal statement of line 68.\n\nIn table 1, the column ‘identically distributed’ does not indicate that it is about error, or which error notion(s) it is about.", "limitations": "yes", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of private prefix sums is a fundamental problem which is used as a subroutine in various private algorithms. Therefore the smooth binary tree mechanism with improved variance and similar asymptotic space and time complexity is an interesting contribution. The paper provides a clear explanation of the proposed mechanism as well as the naive binary tree mechanism. These explanations are supported by helpful diagrams.", "weaknesses": "-The text in the paper is very clear but the formal portions of the paper are (in several instances) not well specified.\n\n-While the proposed mechanism is nice, the analysis of the mechanism could use much more detail.\n\n-In particular, the paper makes several claims about the error of the proposed mechanism in the text of the paper, even adding this value to a table in the introduction. However the manuscript does not specifically define their notion of error or make any formal verifiable statements about the error of the proposed mechanism in either the main paper or the supplementary material. While the notion of error they are talking about can be inferred from the text, the distribution of the error of the mechanism is key selling point that the authors mention several times. This omission and the lack of detail in the analysis would make the paper fairly inaccessible for many readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading and questions.\n\n*W1: [...] formal portions of the paper are (in several instances) not well specified.*\n\nWe disagree with the claim that the formal portions are not well-specified, see answer to Q1 below.\n\n*W2: [...] analysis of the mechanism seems incomplete.*\n\nCan you elaborate on where you feel that the analysis is incomplete?\n\n*Q1: Is there a reason that you do not consider any specific notions or provide any formal statements and proofs about the error of the smooth mechanism?*\n\nWe disagree that we do not consider any specific notion of error and that we lack formal statements. Our error at a given time step is Gaussian with mean zero, meaning that it is fully specified by its variance. As written in lines 133-135 and further motivated in lines 149-153, we are interested in optimizing the variance at each single time step. The main theorem expresses the properties of our mechanism in these terms too. Since our mechanism has constant variance at each time step, the expected $\\ell_p$ norm can be expressed as a function of the variance.\n\n*Q2: In line 221 you say that the maximum sensitivity is proportional to $k$. I understand that this is true for your choice of $h=k/2$ but as far as I can tell, it need not be true in general, right? (Since the maximum sensitivity of a particular node is technically proportional to $h-k$, which need not be proportional to $k$?*\n\nNo, our claim is true in general. $k$ is the number of 0s in $\\mathrm{bin}(i)$, so therefore $k$ describes the number of ancestors to the corresponding leaf that are “left-children”. Only left-children are ever used, therefore the squared $\\ell_2$-sensitivity for that leaf is equal to $k$. On the other hand, $h-k$ gives the corresponding number of 1s in $\\mathrm{bin}(i)$, which fixes the number of nodes added together when the path to said leaf is used to compute a prefix sum.\n\n*Q3: There seems to be a mistake in line 68: It says that the sensitivity of some node $x_t$ is the number of zeroes in $\\mathrm{bin}(t-1)$. Isn't it actually $\\mathrm{bin}(t-1)+1$?*\n\nThe text is correct, it is the number of 0s in $\\mathrm{bin}(t-1)$. It would be $\\mathrm{bin}(t-1)+1$ if the root node was ever used, but our analysis assumes it is not, as stated in lines 184-185.\n\n*Q4: Also line 68 occurs prior to the definition of $\\mathrm{bin}(\\cdot)$ which doesn’t appear till line 113.*\n\nWe opted to give a (partial) definition on line 66 in this initial section outlining the technical ideas."}, {"review_id": "UZYxftsKLK", "reviewer": "Reviewer_kh8m", "summary": "This paper studies the important problem of optimizing continual observation algorithms while also making them efficient.  There has been some recent advances in the classical binary mechanism for releasing a streaming counter subject to differential privacy.  One of the main issues with the binary mechanism is that is add varying levels of noise to each count, since the number of noise terms that are added at each round depends on the number of 1’s in the binary representation of the length of the stream.  Work from Henzinger et al. shows how the variance of the noise need not change drastically at each round and overall the variance can be significantly reduced.  However, this approach has runtime that scales linearly with the length of the stream, which can be prohibitive, especially when wanting to release counts in a streaming setting.  This work shows that it is possible to get closer to the benefits of Henzinger et al. while also having runtime that is similar to the binary mechanism, making it a great replacement for the classical binary mechanism.", "questions": "Can you give a better presentation for the algorithm and how it works?  The whole algorithm seems to only be two itemized bullets in lines 214 and 215.  ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "There are impressive results with this work, where variance is almost constant across rounds and the overall variance is similar to the optimal approaches.  Table 1 nicely summarizes the results and how they compare to existing approaches. ", "weaknesses": "The new algorithm in Section 3.2 is not clearly presented.  As this is the main contribution of this work, I would expect the algorithm to be clearly presented, but it is pushed to the supplementary file.  There is a nice figure to explain the binary mechanism, but not the new algorithm.  Providing an example here would help, as is done with the binary mechanism.  I even went to the supplementary code file to better understand what the algorithm is doing, but there are few comments so it is not very readable.  Will increase my score if the paper can be updated with a better description of the main algorithm.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading and positive comments.\n\n*Q1: Can you give a better presentation for the algorithm and how it works?*\n\nWe will add further details about how the algorithm works, including a graphical illustration of how the algorithm functions reminiscent of Figure 1(b) for the conventional binary mechanism, to our revised paper. See the PDF in our global response where we have added two such examples where we compute $\\mathcal{M}(2)$ and $\\mathcal{M}(5)$ when $T=5$."}, {"review_id": "AcnxTzWF50", "reviewer": "Reviewer_aGJ1", "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.\n\nThe 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.\n\nDespite 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]).\n\nTo understand the techniques, we need to discuss the binary tree mechanism in more detail. There are two important parameters that affect the error:\n1. *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.\n2. *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.\n\nFor 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.\n\n## Post-Rebuttal Comments\n\nThank 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.", "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?)\n\n- 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.)\n\n- 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?\n\n- 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$.)\n\n## Minor comments\n\nBelow are minor comments to help the authors improve their revision. Please do *not* reply to them during rebuttal.\n\n- Line 49: \"algoritm\" -> \"algorithm\"\n\n- 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.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Continual counting is a basic problem in literature and this paper provides a significant improvement over the classic binary tree mechanism.\n\n- 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.\n\n- The writing is not ideal:\n  - Main algorithm (Algorithm 2) is not presented in the main body.\n  - 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.\n  - \"Streaming support\" and \"same error distribution\" is discussed in a possibly misleading manner (see the first two questions below in more detail).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading and insightful questions.\n\n*W1: [...] a tradeoff between time-space efficiency and privacy-utility tradeoff. In my opinion, the latter is typically more important in practice.*\n\nWhile often true, time-space efficiency is the reason why papers based on matrix mechanisms rarely go beyond $T=10^6$, and efficiency is in fact a real consideration for large-scale applications, e.g. private learning.\n\n*W2: No analogous proof for when $x_i$ is multi-dimensional despite showing such an experiment.*\n\nWhile true, the feasibility of the algorithm for this case follows trivially by composition.\n\n*Q1: Why is it a big deal that the error at each step is identically distributed when for a Gaussian mechanism this can always be achieved by adding extra fresh noise to match the worst case variance?*\n\nThis is indeed correct for Gaussian mechanisms, and any other mechanism based on a stable distribution, and will be further emphasized in the paper. For mechanisms based on non-stable distributions it is non-trivial to achieve this property. In particular, if we want pure DP, then using our mechanism with Laplace noise will yield a pure DP mechanism where the error at each step is identically distributed.\n\n*Q2: Why does the precomputation of noise render Henzinger et al.'s algorithm a non-streaming algorithm?*\n\nGood observation, it does not -- the text is wrong. We use the convention that \"streaming support\" implies being able to compute the output at time $t$ using only inputs $x_i$ where $i\\leq t$. Precomputing the noise can be done independently of the input for a given upper bound $T$, and therefore poses no obstacle to supporting streaming. We will correct the writing in the revised version: Henzinger et al.'s algorithm can release $T$ prefix sums in time $O(T\\log T)$, but the space needed is much higher than for our method.\n\n*Q3: [...] is there any (informal) reason why one should think that it is hard to implement their algorithm using say polylogarithmic space and time?*\n\nTheir algorithm’s output at time $t$ requires the computation of a linear combination of $t$ random choices. The coefficient of each past random choice changes at each new time step, making it (seemingly) impossible to (productively) reuse past linear combinations to construct new ones. Because of this, it seems likely that you are forced to store all $t$ random choices in memory to produce the output at time $t$, which bars a polylogarithmic space/time implementation.\n\n*Q4: Can you not leverage the binary representation of the leaves that store an $x_i$ to have at most $h/2$ zeros and the binary representation of every queried time step leaf to have at most $h/2$ ones?*\n\nYou are correct, that would allow you to reduce the height of the tree while keeping our constant improvement in the leading term as an upper bound. We investigated this but opted to not include it as:\n1. We wanted to make our algorithm as simple as possible.\n2. The improvement in the leading term for the variance at a given time step is unchanged.\n3. The reduction you get in height is not that substantial.\n4. Although, as you correctly point out in *Q1*, we could pad with Gaussian noise to achieve identical error distribution at each step for Gaussian mechanisms, we cannot do the same for non-stable noise distributions.\n\n\n"}, {"review_id": "LxuFD5jCfO", "reviewer": "Reviewer_pQUM", "summary": "The binary mechanism is a simple, efficient and well-known method to answer linear prefix queries (like counting) when a database of size T is not given in advanced, but rather in each time point $t \\in [T]$ we are given a new row $x_t$, and we are required to update our result based on the new row (while taking into account that the previous estimations were already released). For the prefix sum (or counting) problem where each row is 0 or 1, the binary mechanism in the zCDP model results with an additive error of Gaussian noise for each observation, where the maximal noise variance is $0.5 \\cdot \\log_2^2 T$. The noise variance is not identical for every observation, as it is a function of the number of zeros in the binary representation of $t-1$ (the observation index). This can also be change to be depend on the number of ones instead of the number of zeros.\nThe main contribution of this work is to develop a (simple but clever) variant of the binary mechanism that balances between the different noises such that each observation will get the same noise variance, and this variance will be only $(0.125 + o(1)) \\cdot \\log_2^2 T$, which is almost $4$ times better than the maximal variance of the binary mechanism (which translates to factor $2$ in the resulting noise magnitude).\nThis work does not improve upon the best-known variance, as Henzinger et al. (SODA 2023) and Denisov et al. (NeurIPS 2022) have managed to get variance of $0.04865 \\cdot \\log_2^2 T$, which is $10.2$ times better than the standard binary mechanism and $2.57$ times better than this work. However, these works are much more complex, and more importantly, much less efficient in terms of running time and space. \n", "questions": "No questions to the authors.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "At the bottom line, this paper improves a factor of $4$ in the variance of the Binary Mechanism with almost no additional cost in its complexity. Therefore, it potentially can be useful in practice. It does not achieve the best accuracy, but definitely provides a simpler and more efficient alternative to the more accurate but complex algorithms of Henzinger et al. (SODA 2023) and Denisov et al. (NeurIPS 2022).", "weaknesses": "The improvement is clever and simple, but perhaps too simple for a NeurIPS submission. I lean towards accepting this paper mainly because it might be useful in practice.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their reading and agree that the algorithm has the potential of being useful in practice.\n\n*W1: The improvement is clever and simple, but perhaps too simple for a NeurIPS submission.*\n\nWhile we agree that our algorithm is simple, we would argue that this is a strength of the algorithm rather than a weakness. It being a simple algorithm may come as a surprise given that no streaming algorithm using sublinear space for the problem has achieved a constant improvement in the variance since the seminal binary mechanism (Chan et al., 2011; Dwork et al., 2010).\n\nThe question of whether there are algorithms for continual counting that combine the efficiency of the binary mechanism with a lower variance has also been raised earlier. It was for example raised during a presentation of the work (Denisov et al., 2022) at a Google workshop last year."}]

Author rebuttal:
In response to reviewer kh8m's request for a better explanation of how the final algorithm, Algorithm 2, works, see the attached PDF below containing two graphical examples of how the algorithm computes $\mathcal{M}(2)$ and $\mathcal{M}(5)$ when $T=5$.

We commit to including at least one of the examples in the revised paper.

Meta-review: The reviewers were all positive about this paper and its contributions, and felt that the authors sufficiently addressed all their concerns in the discussion phase.
Decision: Accept (poster)