Continual Counting with Gradual Privacy Expiration
Authors: Joel Daniel Andersson
Monika Henzinger
Rasmus Pagh
Teresa Anna Steiner
Jalaj Upadhyay
Venue: NeurIPS 2024 poster (2024)
Keywords: differential privacy
continual observation
privacy expiration
Primary area: privacy
TL;DR: We consider a variant of the continual counting problem in which privacy loss is allowed to grow over time.

Abstract: Differential privacy with gradual expiration models the setting where data items arrive in a stream and at a given time $t$ the privacy loss guaranteed for a data item seen at time $(t-d)$ is $\epsilon g(d)$, where $g$ is a monotonically non-decreasing function. We study the fundamental *continual (binary) counting* problem where each data item consists of a bit and the algorithm needs to output at each time step the sum of all the bits streamed so far. For a stream of length $T$ and privacy *without* expiration continual counting is possible with maximum  (over all time steps) additive error $O(\log^2(T)/\varepsilon)$ and the best known lower bound is $\Omega(\log(T)/\varepsilon)$; closing this gap is a challenging open problem. 

We show that the situation is very different for privacy with gradual expiration by giving upper and lower bounds for a large set of expiration functions $g$. Specifically, our algorithm achieves an additive error of $O(\log(T)/\epsilon)$ for a large set of privacy expiration functions. We also give a lower bound that shows that if $C$ is the additive error of any $\epsilon$-DP algorithm for this problem, then the product of $C$ and the privacy expiration function after $2C$ steps must be $\Omega(\log(T)/\epsilon)$. Our algorithm matches this lower bound as its additive error is $O(\log(T)/\epsilon)$, even when $g(2C) = O(1)$.

Our empirical evaluation shows that we achieve a slowly growing privacy loss that has significantly smaller empirical privacy loss for large values of $d$ than a natural baseline algorithm.

Continual Counting with Gradual Privacy Expiration
Joel Daniel Andersson
Monika Henzinger
Basic Algorithms Research Copenhagen University of Copenhagen jda@di ku. dk
Institute of Science and Technology Austria Klosterneuburg, Austria
monika www.ingerriit..acc.mmm ac.at
Rasmus Pagh
Teresa Anna Steiner University of Southern Denmark
Basic Algorithms Research Copenhagen University of Copenhagen pagh@di. ku.dk
steiner@imada, sdu, dk
Jalaj Upadhyay
Rutgers University
jalaj www.hyyyyyruuggrr.ccooo edu
Abstract
Differential privacy with gradual expiration models the setting where data items arrive a stream and at given time / the privacy loss guaranteed for data item seen time d) is eg()), where is monotonically non-decreasing function. We study the fundamental continual (binary) counting problem where each data item consists bit, and the algorithm needs output at each time step the sum of all the bits streamed so far. For stream of length 7 and privacy without expiration continual counting possible with maximum (over all time steps) additive error (log)(T))e) and the best known lower bound is (Tlog()))))) closing this gap is a challenging open problem.
We show that the situation is very different for privacy with gradual expiration by giving upper and lower bounds for large set expiration functions g. Specifically, our algorithm achieves an additive error of (log([)) f=) for a large set of privacy expiration functions. We also give lower bound that shows that if the additive emor of any e-DP algorithm for this problem, then the product of C' and the privacy expiration function after 2C steps must (T)o(())))) Our algorithm matches this lower bound as its additive error is (l)o()))=z) even when (2C) O(1). Our empirical evaluation shows that achieve slowly growing privacy loss with significantly smaller empirical privacy loss for large values of d than natural baseline algorithm.
Introduction
Differential privucy under continual observation [6] has seen a renewed interest recently
2
15
21
25
26
27
24
due to its application in private learning [10] [ 13 44 34] and statisties 6
7
19
32). In this model, the curator gets the database in the form a stream and required to output given statistic continually. Chan et al. (8) and Dwork et al. [16] introduced the binary (tree) mechanism which allows us to estimate the running count of a binary stream of length with additive error Olog" (T)/s) under e-differential privacy.
30
37
40
20
The traditional definition of continual observation considers every single entry in the stream equally important for analysis and has equal confidentiality. However, in many applications of continual observation, the data becomes less sensitive with time. For example, consider the case where the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

stream tracks visits to certain location or website: it being visited minute ago may constitute more sensitive information than if it was visited week ago. To capture such scenarios. Bolot al. [ defined privacy with expiration, where the privacy of streamed data item decreases as a function of the time elapsed since it was streamed. However, known algorithms for privacy with expiration work
only in the setting when we expect no privacy after certain time has elapsed 4 Section 6].
This lack of algorithms for privacy with expiration influences some real-world design choices D. In particular, real-world deployments either allocate every user a "privacy budget" that is diminished every time their data is used, such that their data should not be used once the privacy budget reaches zero, or they account for privacy loss over the time. However, since the data can still be useful, another common approach in these deployments use the heuristic of "refreshing the privacy budget". i.., the privacy budget is reset to a positive default value after a prescribed time period, irrespective of how much privacy budget has been used so far. This, for example, was pointed out by Tang et al. (38] in Apple's 's first large-scale deployment. However, refreshing the privacy budget is very problematic as the privacy loss is, in the worst case, multiplied by the number of refreshes, for example, if the old data is reused (i.e., the privacy expiration is linear).
In this paper, we study continual counting with gradual privacy expiration, generalizing the result in Bolot et al. Our main contributions are algorithms with the following assets:
Improve accuracy. We achieve an additive error of (llog(T)/E) for a large class of privacy expiration functions and show that this is optimal in a particular sense. This is in contrast to continual counting without expiration, where there is gap of a log T factor [16]. Our work generalizes the (log((T)e)) lower bound for continual counting to wide class of privacy expiration functions and shows that for any additive error C, the product of C and the privacy expiration function after 2C steps must be 2(oog T). We match this lower bound our additive error is Oloo (T)og)T)))) even when the expiration function after 2C steps is constant.
Scale well. Our algorithms work for unbounded streams, run in amortized (1) time per update, log(T)) space, and offer different trade-offs than conventional continual counting algorithms. In allowing for a growing privacy loss, we show that polylogarithmic privacy expiration is sufficient for optimal additive error, and parameterize the algorithm by the speed of the privacy expiration; as expected, faster privacy expiration yields a smaller error.
We supplement these theoretical guarantces with empirical evaluations.
Related Works. Before presenting our contributions in detail, we give brief overview of the most relevant related work. Since Chan et al. [ and Dwork al. [16. several algorithms have been proposed for privately estimating prefix-sum under continual observation, i.e., given a stream of inputs 3 , ...... from some domain X, output 3/+ = Eist D; for all 2 1. Continual binary counting is a special case of prefix sum when X' = {0, 1} and F; is provided at time t.
When the input is given as stream, carlier works improved on the basic binary mechanism under (i) distributional assumptions on data 33) (ii) structural assumptions on data (36), and (iii) that the importance of data (both with respect to utility and sensitivity) decreases with elapsed time (4) or (iv) by enforcing certain conditions on the behavior of the output 9 In recent work, Fichtenberger et al. (21] gave algorithms to improve the worst-case conmasymtooiic guarantees under continual observation using the matrix mechanism (33] and Denisov et al. [14 used similar approach to provide empirical results that minimize the mean-square error. Subsequently, Henzinger et al. (25] showed that the algorithm in Fichtenberger et al. (1 achieves almost optimal mean-squared error.
These earlier works are in the traditional definition of privacy under continual observation, i.c., they consider data privacy to be constant throughout the stream. The only exception is the work of Bolot et al. 4.. which defined differentially private continual release with privacy expiration parameterized by a monotonically non -ecceaseg function g and gave an algorithm for the special case that the data loses all its confidentially after prescribed time. Our work is in this privacy model. There is another line of work motivated by applications in private learning that studies privacy-preservin without restricting access to the data points (such as allowing multiple passes) [13 31 and providing preeccppreeevving. estimates under various privacy models like shuffling [12]. Since we focus on
prefix sum
continual observation, we do not compare our results with this line of work.

---

The work whose techniques are the most related to ours is the algorithm in Dwork et al. [16] for continual counting satisfying pan-privacy [T7] Roughly speaking, an algorithm pan-priiaate if is resilient against intruders who can observe snapshots of the internal states of the algorithms.
1.1 Our Contributions
We start by first formally stating the problem. As mentioned above, the focus of this work is privacy with expiration given as Definition 3 in Bolot et [4]
Definition 1.1. Let g g.:. N + Rz0 be a non-decreasing function D Let A be a randomized online algorithm that takes an imput a stream x1, T2,,..... and every time step L oulputs ,(ri,...,3 Ft). A satisfies s-differential privacy with expiration (function) g if for all T 2 1, for all measurable S C range(A) all possible inpuls ,1,-.., Lr, all T and all x/y with [rj x'y [0.1]
PP.. 2:)T S] S <
Pr((A(E)...... (e(t=))-P((AA(EE....
(.....,,)))))- S),
20)
where the probability is over the coin throws of A. We refer to g(T - 5) as the privacy loss.
Letting T' be the length of the input stream, the best known bound on the -eror for continual counting under e-differential privacy is Ologg (T))),, achieved by the algorithms in [6] 8 Al- ternatively, the analysis of g can used to show that running this algorithm with g' (og( achieves e-differential privacy with expiration function g(d) log(T) for all d = 1,.... T. and error (E)) Our main contribution is to show that better trade-offs are possible: can achieve the same error with strictly smaller function g. i.e. we can get an (log(T))/s bound on the -eror with an expiration function of g(d) R log d. More generally, our algorithm provides a trade-off between privacy loss and both -erorr and expected E -e-rrror for all expiration functions (d) that satisfy (roughly) (d) 2 ldg for any À > 0. The exact expiration function g is stated below in Theorem 1.2 It also includes a parameter that allows the privacy loss to be "shifted" by B time steps, i.e., there is privacy loss in the first B time steps. If the length T of the stream is unknown, then B is a constant. If I' is given to the algorithm, then B can be a function of T.
particular, we
By Definition 1.1 any algorithm satisfying differential privacy with expiration g also fulfills differen- tial privacy with any expiration function that is pointwise at least as large as g. Specifically, for two functions and g defined the same domain D, we say f > 9 if fx) 2 g(z) for all D. We are now ready to state our main theorem:
Theorem 1.2. Let E R \{3 be constant. and let parameters & E Rs0 and B E N be given. There exists algorithm A that approximates prefix sums of a (potentially unbounded) input sequence F ...... with x; E [0, 1] satisfying e-differential privacy with any expiration ppnnttooofunntton f
such that f 2 9, where
( s(d) 00( + log (d- B 1)) for 2 B
for d < B
Considering all releases up to and including imput t, the algorithm A uses O(B + log f) space and O(1) amortized time per input/output pair and has the following error guarantees at each individual time step for B 0,
EA (AAxx) (A(x))-i -iin 2;)2 O(B² +log 2-gg)22(t))/
EA
A(x) - Ei 2z5 = O(B + (t) (lol(//))))(1/))/// with probability 3 where q max 11/2,3/2-1
The case when x E (0,3/2) is covered in Appendix C.3 Note that choosing À > 3/2 implies constant expected squared error at each time step if B (1). Parameter À controls the trade-off between the asymptotic growth of the expiration function and the error, while æ controls the trade-off between initial privacy (after B time steps which is e g(B) and the error, which is inversely Also, for releasing outputs we have the following corollary.
proportional
We believe g heing non-in non-increasing a typo in Bolot et 2ea" is the Kleene operator: given a set Σ, 2 is the (infinite) of all finite sequences of elements in Σ.
3

---

Corollary 1.3. The algorithm A with B = ((log(T)/)) and X 2 1 incurs a maximum (over all time steps) additive Lo -erorro of (log( when releasing T outputs with probability 1/T", for constant > 0, and achieves privacy with expiration function g as in Theorem 1.2
In Section 6 we provide empirical evidence to show that we achieve significantly smaller empirical privacy loss than a natural baseline algorithm. Finally, we complement our upper bound with the following lower bound shown in Appendix C.4
Theorem 1.4. Let A be algorithm for binary counting for streams of length T which satisfies e-differential privacy with expiration h. Let C' be an integer such that A incurs a maximum additive error of most C < /2 over T time steps with a probability of at least 2/3. Then
log(T/(6C)
20 . h(2C - 1)
28
Note that Theorem 1 gives a lower bound for h()) for specific j. namely = 2C - 1, and as h is non-decreasing by Definition 1.1 the lower bound also holds for all l(j²)) with j' 2 j.
Note that Theorem 1.4 shows that our algorithm in Corollary L.3 achieves a tight error bound for the (lo)())/E)) Assume A'' is an algorithm that approximates prefix sums in the continual setting and which satisfies differential privacy with expiration function h and maximum error C S B/2 + all time steps with probability at least 2/3 for an even B. When run on binary input sequence, A'' solves the binary counting problem. Thus, by Theorem 1.4 we have that 2C' h(B + 1) 2 2C h(2C 1)
expiration functions À 2 1 and
log(T/166)) [og(T/(3B+6)
22( ()
26
2s
Now consider the algorithm AA given in Corollary 1.3 and note that, by definition of the expiration
function g B + +1 O(1) and that Corollary 1.3 shows that C' = (log(T)/e). This is tight as
Theorem 1.4 shows that for such an expiration function C = (loo((T)E))
1.2 Technical Overview
Central to our work is the event-level pan-private algorithm for continual counting by Dwork et
al. [16]. Similarly to the binary tree algorithm of Dwork et al. (8), noise variable 21 is assigned to every dyadic interval I (see Section 3.2 for a formal definition) contained in [0. T 1]. Let this set of dyadic intervals be called I. In the version of the binary tree algorithm of Chan et al. [8], the noise added to the sum of the values so far (i.e. the non-private output) at any time step S t < T is equal to EiED 1) 21, where Dio.t-1] C I is the dyadic interval decomposition of the interval [0, 1---11 1]. The pan-private algorithm adds different noise to the output: it adds at time / the noises for all intervals containing t 1, i.e., Ere(ret:(-Ie)) (-1e)) 21- This pan-private way of adding noise helps us bound the privacy loss under expiration. For two neighboring streams differing time step j. we can get the same output at r 2 j by shifting the values of the noises of a set of disjoint intervals covering [j. 7] each by at most 1. Using that [Di-=] = O(log(T + 1)). we show that the algorithm satisfies a logarithmic privacy expiration.
In our algorithm, we make four changes to the above construction (i.e., the pan- pan-private construction in Dwork et al. [6)): (i) We do not initialize the counter with noise separately from that introduced by the intervals. (ii) We split the privacy budget unevenly across the levels of the dyadic interval set instead of uniformly allocating it. This allows us to control the asymptotic growth of the expiration function, and the error. This change, however, requires a more careful privacy analysis. (iii) At time t we add noise identified by intervals containing I, not / 1. While this is subtle difference, it allows us exclude intervals starting from Z, leading to our algorithm running on wnbounded streams with utility that depends on the current time step t. Said differently. our algorithm does not need to know the stream length in advance. This in contrast to Dwork et al. [16) where the construction requires an upper bound I on the length of the stream so that the utility guarantee at each step is fixed and function of T' (iv) We allow for a delay of B, meaning we output for the initial B steps. This gives perfect privacy for the first B steps, and, since each element of the stream is in [0. 1]. the delayed start leads only to an additive error of OBB).
2 Preliminaries
Let Nyo denote the set 21, and R2z0 the set of non-negative real numbers. We use the symbol g to denote the function that defines the privacy expiration, i.c., g N - Rzo. We fix the symbol

---

A(x) to denote the randomized streaming algorithm that, given an imput 2 = 21, T2....... as a stream, provides e-differential privacy with expiration g. All algorithms lazily draw noise, meaning that a "noise" random variable is only drawn when first used and is re-used and nol re-drawn when referenced again. For a random variable, Z, we use support(2 Z) to denote its support, For sequence of random variables Z = 7,,, 22 .2....... we use support ()) to denote support (1)) X support (Z2) x
Helpful lemmas. We now collect some helpful lemmas shown formally in Appendix C To show privacy with expiration in the following sections, we repeatedly use the following observation: a similar lemma has been used to show the standard definition of differential privacy, e.g., in the proof
of Theorem 2.1 of Dwork et al. [18]. Informally, it says that if there exists a map between random choices made by algorithm AA such that for any input x and fixed sequence of random choices, the map returns sequence (z) such that (1) the output A(z, 2) equals the output A(x', (()) and (2) the probability of picking z is similar to the probability of picking ((=), then A private. The notion of "similar probability" is adapted to the definition of differential privacy with expiration and depends on the function g. All the results in this section are shown formally in Appendix C.T.
Fact 2.1. Consider an algorithm A that uses a sequence of random variables Z Z1, Z2. ... as the only source of randomness. We can model A X x support(Z) as (deterministic) function of its actual inpul from the universe X and the sequence of its random variables Z. Suppose that for all T E Nxo- j S T and all neighboring pairs of input streams I = 2.j....2f..... R........ and x' = Ii...., F....., there exists a function q support(Z) + support(Z) such that A(x; = A(z): and
Pr 1 c-9(T-5) Pr lr E c(N)] 2'-2
for all N "sspport(Z)
Then A satisfies e-differential privacy with expiration 9-
Lemma 2.2. Let Z Z,, Zz.....: Zy be sequence of independent Laplace random variables, such that Zi Lap(b.) for b; > 0, for all i E [k], Let be bijection q : support(Z) - support(Z) of the following form: For all A = (Ai A2
A&) E IR*,, and for all a E support(Z) ()), we have (()) + A support(Z) (Z). Then for all N C (suppor(2]) we have
[r EM S e9 Pr E q(N),, where 8 2E2
=E2
b
3
Warmup
As a warm-up, we give two simple algorithms for two obvious choices of the expiration function: the linear expiration function g(d) and the logarithmic expiration function g(d) 2 log(d (d 1) 2.
3.1 A Simple Algorithm with Linear Privacy Expiration
First, we consider a simple algorithm which gives e-differential privacy with expiration g : N + Rxo. where g(d) = d. The maximum error of this algorithm over T' time steps is bounded by Ole-"log log(33)), with probability at least - 3. The algorithm Asimple is given in Algorithm It adds fresh Laplace noise to any output sum. Note that this is the same algorithm as the Simple Counting Mechanism I from Chan et al. [8] However, we show that for the weaker notion of differential privacy with linear expiration, Laplace noise with constant scale suffices, even though the sensitivity of Asiple running on a stream of length T is T. To prove this, we show that for two neighbouring streams differing time step j, we obtain the same output by "shifting" the values of the Laplace noises for all outputs after step j by at most 1. We defer the proof of the following lemma to Appendix C22)
Lemma 3.1. The algorithm Asimptes given in Algorithm 7 is s-disferentially private with expiration g. where g N -> P is the identity fanction g(d) = d for all d N. It incurs maximum additive error of (( (og(T/B) over all T time steps simultaneously with probability at least 1 B.
5

---

4,
12 3
4,
(6.
2
[
6
0
0
0
0
Figure I: An example of the noise structure for Algorithm and Algorithm 3 for B = on two neighbouring streams x and y differing in position 3. The nodes correspond to the dyadic intervals. The filled nodes mark the intervals / for which the noise Z, is shifted by one between a and to get the same outputs for 7 6. The fat nodes mark the intervals corresponding to the Z₁ which are used in the computation of the fourth prefix sum $1.
Algorithm 1 Asimple:
Continual counting under
Algorithm 2 Alogi
Continual counting under loga-
linear gradual privacy expiration
rithmic gradual privacy expiration
1: Input: A stream 22,"2,''', privacy pa-
1: Input: A stream Z1, "2,""", privacy param e
2: Let I be the dyadic interval set on [1, oc)
rameter e
2: Lazily AazilyS1ran Iraw ZT-1 Lap (t)
3: VI lazily draw i.i.d. Zr Lap (1)
3: At time / - 1, output O
4: Set I, [1 E I :
4: for = 2 to oo do
5: for t = 1 to xo do
5: At time t, output Ei=l 24 Z:-1
6: At time output E/ T4 Eiez, Z1
6: end for
7: end for
3.2 A Binary-Tree-Based Algorithm with Logarithmic Privacy Expiration
Next, we show how an algorithm similar to the binary tree algorithm [66] gives e-differential privacy with expiration N- + R2. where g(d) 2 log (d + 1) 2. This result can also be derived from Theorem 1.2 by setting À = and B = 0. As in the case when g(d) = d, the maximum error of this algorithm over T time steps is again bounded by O log (B))), with probability at least - B. Similarly to the binary tree algorithm. we define a noise variable for every node in the tree, but we do this in the terminology of dyudic intervals. We consider the dyadic interval ser I on [1, oc) (formally defined shortly), associate a noise variable that contains t. This is similar to the construction Dwork al. (16), with the
with each interval E T, and at time step / add noise
21 for each exception that they instead consider the dyadic interval set on [0, T - 1], add noise 2 at time t if - E 1, and initialize their counter with noise from the same distribution. Our choice of Z allows the algorithm to run on unbounded streams, and leads to adding up 1 [log(t) noise terms at step t rather than 1 log(T)) For privacy, we will argue that if two streams differ at time j. then we get the same outputs up to time 7 2 by considering subset of disjoint intervals in I covering [j. r]. and shifting the associated Laplace random variables appropriately. the following, we describe this idea in detail. We start by describing the dyadic interval decomposition of an interval.
divide (1, into disjoint intervals of length 2 I {[k 2 (k + 1) 2 1], k E N We call I = Ur I' the dyadic interval set oo), and I the f-th level of the dyadic interval set. We show the following two facts in Appendix[[]
Dyadic interval decomposition. For every non-negative integer
Fact 3.2. Let I be the dyadic interval set on oo). For any interval (a, b,. 1 < a S b, there exists a set of intervals Dia,5) S I, referred to as the dyadic interval decomposition of [u, b). such that (i) the sets in D(a,0) are disjoint; (ii) UIED 1= (a, b); and (ūi) D D(o,5) contains at most 2 intervals per level, and the highest level l of an interval satisfies S log(b a
By "lazily", we we draw random variable the first time it is used by the algorithm.

---

Fact 3.3. Let I be the dyadic interval set on [1. x),, and E Nso define I, fI the intersection of with I. Then [I,] [ogt +1.
Lemma 3.4. The algorithm Alog given in Algorithm satisfies E e-differential privacy with expiration 9. where g I + defined as g(z) 21og(= + + It incurs maximum additive ervor of Oss-llog(TT (og(T/3)) over all T time steps simulluneously with probubility at least 1 -
Privacy. We Fact 2.1 and Lemma 2.2 argue privacy of Alog: Let and x' differ at time j.
Note that the prefix sums fulfill the following properties: (i) Σ H4 = Ei= 24 for all < and (ii) Ei 44 - Ei 2i + for all 2 j. where - = x'j E [-1,
In the following, we refer to the output of the algorithm run on input and with values of the random variables = as Alag (z;; z). Let 2 j be given, and consider S S range(AAog)". Let = (Zz) be the sequence of Laplace random variables used by the algorithm. For any fixed output sequence s E S, let 2 = (æI)rez be a sequence of values that the Laplace random variables need to assume to get output sequence 8 for input x. That is Di Ki + Eiez,
for / 2 1. Let Dü.r1 be the decomposition of [J, r] as defined in Fact 3.2 We define a bijection satisfying the properties of Fact 2.1 as follows: ((2) z' (z/)tez such that
2
21
VI $ Pjjr
+y 21
VI D [.r)
We show the two properties needed to apply Fact 2.1
(1) Note that (Atog (z; = E 2i-1 I; + LieT, 2r. For t < j. we have $ [i. and therefore & for any E Dij,r) Therefore, we have
Σ x
Σ IEI.
21
21
Σ x
2/.-
JEZI
i=1
IEI.
For j S we have that is contained in exactly one E D Dj.rr) Thus, 2/1 21 y for exactly one
I E Ir, and z/i. zn for all I' E ZA.... Further, since 2 have that Σ Ji Σi o² - Together, this shows the first property of Fact 2.1 as
2/
y
Σ ビ
z
IEL
im1
IEI.
2m1
IEI:
(2) By Fact 3.2
D Pitt) S <2(log(T - + + 1). Thus, by Lemma 2.2 for any N support(Z).
Pr N1 S Eiempal lue Pr q(N)] ((0n((= j++1)+1ee Pr q(N),,
Pr 2EZ
so the second property of Fact 2.1 is fulfilled with g(z) = 2 llgg( + +1 1) + 2. By Fact 2.1 we have
differential privacy with privacy expiration g(x) log [ + 1) + 2.
Accuracy. To show accuracy at step t, let Y, = ΣlEZ, Zı, i.e. the noise added
at time step t. By Fact 3.3 we add i = I = [logt] | + Laplace noises with
scale 1. Let Mr, max [log + lm(2/B) By Corollary B.4 we have that
Pr [Y9] 2 22 S 3, for any 3 < 1. Setting = BB/TT, it follows that with
probability at least 1 - B', [ = O log(T) /3)) for all time steps t < T simultaneously.
Proof of Theorem 1.2 and Corollary 1.3
shows that we can obtain an error smaller than the binary mechanism by using differential privacy with a logarithmic expiration function. Here we show a general trade-off between the expiration function's growth and the error's growth. Two techniques are needed to show the theorem:
Section 3.2
Delay, All outputs are delayed for B steps. That is, in the first B steps, the mechanism outputs thereafter, it outputs private approximation of i x;- Delay introduces an extra additive error of up to B, but ensures perfect privacy for the first B time steps after receiving input.
7

---

Algorithm 3 Continual counting, gradual privacy expiration
1: Input: A stream 22 " privacy parameter E, parameters B E N. À E R>o'> {3/2]
2: Let I be the dyadic interval set [1, oo) and I f Bel
3: vl, E I lazily draw i..dd Z1 Lap (1+6)'
4: for = 1 to do
5: At time output
6: end for
7: for f B to do
8: At time I, output St-B -Ei 2i + Σier 21
9: end for
Budgeting across levels. The privacy budget is split unevenly across levels of the dyadic interval set in order to control the asymptotic growth of the expiration function. Specifically, the budget at level & chosen to be proportional to (& + 1)^-1___-- The case X = corresponds to the even distribution used
in the construction of Section 3.2
Our algorithm shown as Algorithm 3 the following, we refer to the output of the algorithm run on input z and with values of the random variables as A(x;; z).
Privacy. We now show that A satisfies Definition 1.1 For and x' that differ (only) at time j S T, the prefix sums fulfill the following properties:
E 23 Ei= x for all < and
El 2 E 23 for all t T, where y = x/J- -2, 2j e1-1,1]
Let j and 7 be defined as in Definition 1.1 Due to the delay, if = T- B < (corresponding to BB the privacy claim is immediate since the output distributions of A up to step are identical on the two inputs. Otherwise, for 7 = B 2 j. i.e., for d 2 B, we wish to use Fact 2.1 and Lemma 2.2 Let Z (Zi)sez be the sequence of Laplace random variables used by A. For input consider fixed length-T output sequence consisting of B zeros followed by ....... Syr. Let = = (=1)tez be a sequence of values for the Laplace random variables order to produce this output sequence with input x. That is, St = Ei= z. +EEI, 21 for t 2 Let Dij,71] be the decomposition of [j. r'l as defined Fact 3.2 We define a bijection satisfying the properties of Fact 2.1 as follows:
(2)) 2' (2f)1ez such that
=
VI $ Durr
1 - = +
VI E Du.r
We show the two properties needed to apply Fact 2.1
Lemma 4.1. The function g(z) satisfies A(a; x) = A(x'; 1())) and for g(d) = 0(1 + log
B + 1)) we have Pra-z(z A] ( Pr|z' E for all N support(ZZ.
Space and time. Algorithm can update the sums Σt= at and Eier, Z, in each time step / using the following idea: The B most recent inputs are kept in a buffer to allow calculation prefix sums with delay and also the [log(t)] + 1 random variables of those values that were added to the most recent output. At a given step, each random value that is no longer used subtracted from the most recent output, and each new random value is added. An amortization argument as in the analysis of the number of bit flips in a binary counter yields the (1) amortized bound.
Accuracy. To show the accuracy guarantee, we need to account for the error due to delay well as the noise required for privacy. It is easy to see that the delay causes an error of at most B, since the sum of any B inputs is bounded by B. Thus, for both error bounds it remains to account for the error due noise. At every time step after B, the output the delayed prefix sum plus a sum of Laplace distributed noise terms as indicated by I,-B with parameters by (e 1) 1)1->/e /s, where

---

i = O..... [log(t - B- To bound the variance of the noise, 2 by we compute:
log(t- (o((-B))
B)1
(tog(t-B)) BB)
log(0)+
Σ 0=
=
2²
(C 1)20-)1))
- E2
1+
22 dx
t=0
1 1 g²
1+ 3
1
3
3-2A
x= logg(())+2
0
1 log 1tg(t)3-22)
2X
e²
x=1
This calculation assumes À # 3/2, proving the statement the squared error in Theorem
1.2 For the
high probability bound we invoke Lemma B.3 with bas max. (bę) = max(1, log(2f)
3/s)
O((1 + log(())-))/s) For says that the error from the noise O log (1/B)) = O( (v (1/B) log(t) ( m with
vE. b bm Aog/ = O /og (), applying Lemma B.3
probability 1 - 3, proving Theorem
Proof of Corollary 1.3
For releasing T' outputs, choosing / 1/Tc*1, c being con- stant, and using union bound over all outputs gives a bound on the maximum noise equal to (Togg(T) (log(())mxx(122 ()) /e) with probability - 1/T", proving Corollary 1.3
5 Lower Bound on the Privacy Decay
The lower bound follows from a careful packing argument. The proof is deferred to Appendix C.4
Theorem 5.1. Let A be algorithm for binary counting for streams of length T which satisfies E-differential privacy with expiration Let C be an integer and assume that the additive error of A is bounded by C < T T/2 all time steps with probability of at least 2/3. Then
20-1
Σ
g(5) > log(T/6C))e
The lower bound extends to mechanisms rumning unbounded streams. By Definition 1.1 9()) is non-decreasing in j. This immediately gives Theorem T.4
Empirical Evaluation
We empirically evaluated (i) how the privacy loss increases the elapsed time increases for Algo- rithm (ii) how tightly the corresponding theoretical expiration function of Theorem 1.2 bounds this privacy loss, and (iii) how this privacy loss compares to the privacy loss of a realistic baseline. As different algorithms have different parameters that can affect privacy loss, we use the following approach perform fair comparison: In the design of e-differentially private algorithms the error of different algorithms is frequently measured with the same value of the privacy loss parameter e. Here, we turn this approach around: We compare the privacy loss (as a function of elapsed time) of different algorithms whose privacy parameter E is chosen to achieve the same error.
We empirically compute the privacy loss for Algorithm by considering the exact dyadic decomposi- tions used for the privacy argument (see Appendix A for details). As a baseline to compare against, break the input stream into intervals of length W. run the 'standard' binary mechanism An of Chan et al. [ with a privacy parameter cea on the current interval, and compute the sum of all prior intervals with different privacy guarantee Epost. As for both algorithms that we evaluate is straightforward to compute the mean-squared error (MSE) for all outputs on a stream of length T. while the corresponding maximum absolute error can only be observed empirically, we fix the MSE for T dmaz + 1, where dmaz is the greatest d (on the x-axis) shown in each plot. We normalize each plot to achieve the same MSE over the first T outputs, across all algorithms and parameter choices. For all runs of Algorithm 3 we used B = 0, as for larger values of B, the primary effect would to shift the privacy loss curve to the right. We picked the MSE be 1000 for all plots as leads to small values of the empirical privacy loss. As for both algorithms, the privacy loss does not depend on the input data; we used an all-zero input stream, standard approach in the industry (see, for example, Thakurta's 's [39] plenary talk at USENIX, 2017).

---

W 127
10a
W 1023
Privacy loss
Privacy loss
10*
À
10
Tempincel)
Theorem
10-1
500
1000
10
10
10a
10a
10
10
10
d
d
(a) Alg. vs. g in Theorem
1.2
(b) Alg.
and baseline for various A, resp., W.
Figure 2: Plots the privacy loss for our Algorithm 3 and a baseline algorithm.
Figure 2(a) shows that from Theorem 1.2 is good approximation of the empirical privacy loss, and that both exhibit the same polylogarithmic growth. Figure shows that for large enough our algorithm has lower privacy loss than the baseline algorithm. See more details in the appendix.
7 Conclusion
In this work, we give the first algorithm for the continual counting problem for privacy with expiration for wide range of expiration functions and characterize for which expiration functions it is possible get an -error of (log(T))/e) We also give general lower bound for any such algorithms and show that ours is tight for certain expiration functions. It would be interesting to study this model further, e.g., with slower-grows groowng expiration functions, and also algorithms for other problems in continual observation, such as maintaining histograms and frequency- based statics over changing data. Specifically, would be an interesting direction for future research to study problems this model, where a polynomial error gap between the batch model and the continual release model is known to exist (for example max sum (29) and counting distinct elements [28] 23]), and to see this model allows for new trade-offs. Further, one of the main applications of continual counting algorithms is in descent (see e.g. [14 30 34)). It would be interesting to explore how algorithm can be deployed
federated learning algorithms, specifically in stochastic gradient
in this setting.
Though the concept of privacy expiration has not been defined for approximate differential privacy. it natural wonder there exist analogous results in this setting, which, in general, allows better privacy-utility trade-offs. We note that for p-zerro-oncentraaee differential privacy (5) there is natural analog Definition [.] for which seems possible to prove results analogous to those shown here for pure differential privacy. In that context it would also be interesting to see whether the matrix mechanism can be used to improve the constants in the error, similar to 21 24
Acknowledgements
Monika Henzinger: This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/7422, grant DOI 10.55776/15982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung. 2020-2024.
Joel Daniel Andersson and Rasmus Pagh are affiliated with Basic Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation grant 16582, and are also supported by Providentia, a Data Science Distinguished Investigator grant from Novo Nordisk Fonden.
Teresa Anna Steiner is supported by a research grant (VIL51463) from VILLUM FONDEN. This work was done while Teresa Anna Steiner was Postdoc the Technical University of Denmark.
Jalaj Upadhyay's 's research was funded by the Rutgers Decanal Grant no. 302918 and an unrestricted gift from Google.
10

---

References
[1] Kareem Amin, Alex Kulesza, and Sergei Vassilvitskii. Practical considcrations for differential privacy. arXiv preprint (rXiv:2408.00614 2024.
[2] Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. Neural Information Processing Letters, 2023.
[3] Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Count on your elders: Laplace vs Gaussian noise. arXiv preprint (tt.::2200.0020221 2024.
[4] Jean Bolot, Nadia Fawaz, Shanmugavelayuthan Muthukrishnan, Aleksandar Nikolov, and Nina Taft. Private decayed predicate sums on streams. In Proceedings of the 16th International Conference on Database Theory, pages 284-284222 244-295,22 2013.
[5] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam D. Smith, editors, Theory of Cryptography 14th International Conference, TCC 2016-B, Beijing, China, October 31 November 2016, Proceedings, Part I, volume 9985 of Lecture Notes in Computer Science, pages 635-658, 2016.
[6] Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. In International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2022.
[7] T-H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially private continual monitoring of heavy hitters from distributed streams. In International Symposium on Privacy Enhancing Technologies Symposium, pages 140-159. Springer, 2012.
[8] T.-H. Hubert Chan, Flaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur, 14(3):26:1-255 1-2::24, 2011.
[9] Yan Chen, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. Pegasus: Data-adaptive differentially private stream processing. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1375-1388, 2017.
[10] Christopher A Choquette- Choo, Krishnamurthy Dvijotham, Krishna Pillutla, Arun Ganesh, Thomas Steinke, and Abhradeep Thakurta. Correlated noise provably beats independent noise for differentially private learning. In International Conference on Learning Representation, 2023.
[11] Christopher A Choquette-Chow Arun Ganesh, Saminul Haque, Thomas Steinke, and Abhradeep Thakurta. Near exact privacy amplification for matrix mechanisms. arXiv preprint arXiv:2410.06266, 2024.
[12] Christopher A Choquette-Chonn Arun Ganesh, Ryan McKenna, H Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: unified approach to private training. Advances in Neural Information Processing Systems, 36. 2024.
[13] Christopher A. Choquette-Choo H. Brendan McMahan, Keith Rush, and Abhradeep Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, 2023.
[14] Sergey Denisov, H Brendan McManan, John Rush, Adam Smith, and Abhradeep Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators adaptive streams. Advances in Neural Information Processing Systems, 35:59 10-5924, 2022.
[15] Krishnamurthy (Dj) Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In Foundations of Computer Science, 2024.
[16] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 715-724, 2010.
11

---

[17] Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. Pan- private streaming algorithms. ics, pages 66-80, 2010.
[18] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N Rothblum. Pure differential privacy for rectangle queries via private partitions. In International Conference on the Theory and Application of Cryptology and Information Security, pages 735-751. Springer, 2015.
[19] Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially Private Continual Releases of Streaming Frequency Moment Estimations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251, pages 48: 1-48:24, 2023.
[20] Hendrik Fichtenberger, Monika Henzinger, and Lara Ost. Differentially private algorithms for graphs under continual observation. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), 2021.
[21] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In International Conference on Machine Learning, ICML, volume 202 of Proceedings of Machine Learning Research, pages 10072-10092. PMLR, 2023.
[22] Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Differentially private data struc- tures under continual observation for histograms and related queries. CoRR, abs/2302. 1341, 2023.
[23] Monika Henzinger, A. R. Sricharan, and Teresa Anna Steiner. Private counting of distinet elements in the turnstile model and extensions. In Proc. APPROX/RANDOM 2024, pages 40:1-40:21 2024.
[24] Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2025.
[25] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003-5039. SIAM, 2023.
[26] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. A unifying framework for differentially private sums under continual observation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 995-1018. SIAM, 2024.
[27] James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK. 2:26 27, 2015.
[28] Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. In Proc. 37th NeurIPS, 2023.
[29] Palak Jain, Sofya Raskhodnikova, Satchit Sivakumar, and Adam Smith. The price of differential privacy under continual observation. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 14654 14678. PMLR, 23-29 Jul 2023.
[30] Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213-5225. PMLR, 2021.
[31] Anastasiia Koloskova, Ryan McKenna, Zachary Charles, John Rush, and H Brendan McMahan. Gradient descent with linearly correlated noise: Theory and applications to differential privacy. Advances in Neural Information Processing Systems, 36, 2023.
[32] Max Dupré la Tour, Monika Henzinger, and David Saulpic. Making old things new: A unified algorithm for differentially private clustering. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024.
12

---

[33] Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the twenty-ninth ACM SIGMOD--IGACT-SIGAAR symposium on Principles of database systems, pages 123-134. ACM, 2010.
[34] Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential privacy guarantees. Google Al Blog, 2022.
[35] Victor Perrier, Hassan Jameel Asghar, and Dali Kaafar. Private continual release of data streams. In Network and Distributed Systems Security (NDSS) Symposium, 2019.
[36] Vibhor Rastogi and Suman Nath. Differentially private aggregation of distributed time-series with transformation and encryption. In Proceedings of SIGMOD International Conference on Management of data, pages 735-746, 2010.
[37] Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. Is interaction necessary for distributed private learning? IEEE Symposium on Security and Privacy, pages 58-77. IEEE, 2017.
[38] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Pri- vacy loss in Apple's implementation of differential privacy macos 10.12. arXiv preprint arXiv:1709.02753 2017.
[39] Abhradeep Thakurta. Differential privacy: From theory to deployment, https: htpps://wwt /www youtube. orr.laa..ooo..cccccaaaaaaag/aeee chtpreeebbbccaaameeeeeSS.... 2017.
[40] Jalaj Upadhyay. Sublinear space private algorithms under the sliding window model. In International Conference on Machine Learning, pages 6363-6372, 2019.
[41] Jalaj Upadhyay, Sarvagya Upadhyay, and Raman Arora. Differentially private analysis on graph streams. In International Conference on Artificial Intelligence and Statistics, pages 1171-1179. PMLR, 2021.
13

---

A Empirical Evaluation
In this section, we empirically review (i) how the privacy loss increases as the elapsed time increases for Algorithm 3] (ii) how tightly the corresponding theoretical expiration function of Theorem 1.2 bounds this privacy loss, and (iii) how this privacy loss compares the privacy loss of realistic baseline. Note that different algorithms have different parameters that can affect privacy loss; thus, it not clear how to perform a fair comparison at first. We use the following approach: In the design of e-differentially private algorithms the error is frequently bound as a function of the privacy loss, ie.. the error of different algorithms is measured with the same value of the privacy loss parameter Here, we turn this approach around: We compare the privacy loss (as a function of elapsed time) of different algorithms whose privacy parameter E chosen to achieve the same error. As for both algorithms that we evaluate it is straightforward to compute the mean-squared error (MSE) for all outputs on a stream length T. while the corresponding maximum absolute error can only be observed empirically, we fix the MSE for T dmax + 1, where dmaz is the greatest d shown in each plot. We normalize each plot to achieve the same MSE over the first T outputs, across all algorithms and parameter choices. For all runs of Algorithm 3 we used B 0, as for larger but practical values of B, the primary effect would be to shift the privacy loss curve to the right. We picked the MSE to be 1000 for all plots it leads small values of the empirical privacy loss. Any other choice would simply rescale the values of the y-axes.
Note that for both algorithms the privacy loss does not depend on the input data and, thus, we used an all-zero input stream, a standard approach in the industry (see, for example, [39's plenary talk at USENIX, 2017). We also emphasize that all computations producing the plots shown are deterministic, and so there is no need for error bars.
Empirical privacy expiration for Algorithm| 3 For our evaluation we empirically compute the privacy loss for Algorithm by considering the exact dyadic decompositions used for the privacy argument. More specifically, to compute the empirical privacy expiration function g (for d 2 B) of Algorithm 3 we use the proof of Theorem 1.2 to reason that for A E support (2), Przez(z W is bounded by eq. (1) There we bound the exponent, i.e. the privacy loss, as function of the size of the interval d - B + = T' - + 1, and this yields the g stated. However, this might not be exact, as the decomposition of an interval of size d B + does not necessarily involve using 2 intervals per level up to 8' = [log(d d B + 1)]. Instead, for given d 2 and X, we can for all 2 j. where T' r--j+1 d - B + 1, compute the exact associated dyadic decomposition Pj.r and the resulting privacy loss. For each value of d taking the maximum over these losses over all r' S t gives the worst-case privacy loss at time + for an input streamed time f.
31
Prosacy loss
Privacy loss
Privacy loss
127
2 Compiisl
dion Thooeen
302
102
(a) Alg. 3 vs. in Theorem 1.2
(b) Algorithm for multiple A. (c) Baseline for multiple W.
Figure 3: Worst-case privacy loss computed empirically for a data item streamed d steps earlier.
Figure 3(a) demonstrates how the privacy loss compares to what is predicted by Theorem 1.2 The main observation is that g from Theorem 1.2 is a good approximation of the empirical privacy loss, and that both exhibit the same polylogarithmic growth.
Figure ((b plots the empirically computed privacy loss for different choices of X. It demonstrates that the choice of À equates to a trade-off between short-term and long-term privacy. The larger À the higher the privacy loss for large values of d, which is to be expected. also shows that a smaller X provides greater privacy loss early
baseline. As baseline to compare against, we break the input stream into intervals of length W. run the 'standard' binary mechanism An of [8] with a privacy parameter Soar on the current interval, and compute the sum of all prior intervals with a different privacy guarantee Epast- More exactly, the baseline outputs Ag(Ecur, t) for all time steps t in the first round, i.c., t E [1, WJ. For
14

---

each later round r 1, it does the following: (1) Compute 6, 3past + (r--1)- where Spast ~ Lap(1/Epast) (2) For ( W + +1, W]. output er AB.AA(CCuus (Bcur,
Intuitively, this models what is currently done in the software industry: Each user is given a "privacy budget" for a fixed time interval with the guarantee that their data no longer used whenever the budget reaches O within the current interval. However, at the beginning of the next interval, the privacy budget is being reset. Thus the total privacy loss is the sum of the privacy losses in all intervals.
What fraction of the privacy budget is spent the binary mechanism (Eeur) and what is spent on releasing the prefix of the past (épast) can be chosen in multiple ways. For our experiments, we choose fixed fraction of épast/Ecur a stronger privacy guarantee compared to what is used in the binary tree. Other choices and their implication are discussed in Appendix A.1
0.1, implying that release sums from past rounds with
Figure shows underline that, after W time steps, the privacy expiration becomes linear in the number of rounds (and therefore in d). This is a direct consequence of privacy composition: An input ø, impacts the [t/W]] it participates in, and then is subsequently released in each outputs of Ag in the round future round r' > r as part of C,--
shows the privacy loss of the baseline for a selection of round sizes, The main feature to
3 is compared to the baseline in Figure 4 Qualitatively the results align with our expectations. For large enough d W, the baseline enters the region where the degradation in privacy is dominated by the number of rounds that given input participates in, yielding linear expiration. Notably, the baseline generally achieves a lower privacy loss for smaller d compared to method. This is largely decided by how épast/Ecur is picked. Choosing a smaller fraction would lower the slope in the linear regime at the expense of the early privacy loss incurred from Ag. By contrast, Algorithm 3 exhibits comparable initial privacy loss that grows more slowly never reaching linear privacy loss as predicted by our theorem.
Comparing Algorithm 3 to the baseline. Algorithm
127
W 1023
10a
À
Privacy loss
A =
10a
10a
10
100
10a
102
10a
10
Figure 4: Worst-case privacy loss for data item streamed steps earlier, shown for Algorithm
(with/ x = 1,2,3) versus the baseline (W 127 and W 1023).
A.1 Technical Details
Choosing /psst/Eeur for the baseline For our experiments above, we choose fraction Epost/ / eear 0.1 for our baseline, but, as we state, other choices are possible. In particular, one appealing choice the fraction that minimizes the privacy loss at d T - 1, making the baseline privacy preserving
as possible for the last shown Figures 3(c) and 4 Note that the privacy loss for the largest value
of d will be, roughly, Eour + Epast (N 1). where N is the total number of rounds, corresponding to the privacy loss for an input participating in the first round. We can compute the fraction Epeet/ / cour that minimizes this privacy loss under the constraint of having a fix mean-squared error, yielding solution that is a function of the round length W and input stream length T.
The Figures 3(c) and 4 from Section X are shown below as Figures 5(a) and ((b) where we instead of using
0.1, we use the fraction minimizing the maximum privacy loss. Note that Figure ((a) almost identical to Figure 3(c) This is due to the fact that for this choice of W and T, the optimal fraction is close 0. the case of Figure [(b))ooever however, there is notable difference. The minimizing fraction is here considerably smaller, resulting in tangible reduction of the final privacy
15

---

W
127
W
W
1093
127
Privacy loss
1.5
Privacy
0.0
108
10
10
10
(a) Baseline for multiple W.
Algorithm baseline
Figure 5: Worst-case privacy loss computed empirically for data item streamed d steps earlier.
Figure ((a) is re-computation of Figure 3(c) where the ratio Spast/Ecus is set to minimize the maximum privacy loss, yielding ratio 0.069 for W 31, 0.08 for W 63 and 0.095 for W 127. Figure 5(b) is a re-computation of Figure 4 where the ratio Enast/Ecur is set to minimize the maximum privacy loss, yielding a ratio of 0.0064 Tor W 127 and 0.010 for W 1023.
loss, but at the expense of the privacy loss early on. This line with expectations: spending more of the privacy budget on releasing sums from past rounds implies spending less on releasing the binary tree in each round, which dominates the privacy loss for small d.
While the fraction Fpast/ has an impact, rumning the baseline for fix round length W will always result in linear privacy expiration for great enough stream length T, where Epast affects the slope.
A.2 Exact Parameters for the Experiments
In all the plots, choose the privacy parameter(s) achieve mean-squared error of 1000 over the stream length T in each figure shown, where T 10 for Figure 3(a) 3(b) and 3(c) and 7 = 10 in Figure The corresponding privacy parameters
listed in Table refers the privacy parameter
used by Algorithm 3] and Eeurs Spast are the ones used by the baseTine.
Table 1: Table over the privacy parameters used in each of the plots.
Figure
Algorithm
Ecur
Epaat
3(a)
A = 2
0.05542
= 1
0.1341
3(b)
2
0,05542
3
0.04651
W 31
0.5678
0.05678
3(c)
W 63
0.6372
0.06372
W 127
0.7197
0.07197
W 127
0.7387
0.07387
W 1023
1.096
0.1096
1
0.1947
2
0.05645
3
0.04652
W
0.7328
0.05048
5(a)
0.7031
0.05796
W 127
0.7170
0.07252
W 127
6.973
0.04488
W = 1023
4,413
0.04589
5(b)
1
0.1947
2
0.05645
3
0.04652
16

---

B Background on Random Variables
Definition B.1 (Laplace Distribution). The Laplace distribution centered with scale is the distribution with probability density function
1
(ap()) = 2b
exp
We use Lap(b) or just Lap(b) denote a random variable X distributed according to fLap(b) (z).
Fact B.2 (Laplace Tailbound). X ~ Lap(b), then
Pr[[X] > L. b. Se
Lemma B.3 (Measure Concentration Lemma in [8). Let YI...., Ys be independent variables with
Y; Lap(b;) for all [k:] Denote bM max4e[K] by and Y Ei= Yz. Les O 3 and
max VV bf, bas vin(2/5) Then,
Pr
[M | SB.
Corollary B.4. Let Yi...., Y3 be independent variables with distribution Lap(b) and let Y Σ Y, Leto < B Then
Pr [ > 2by 20n/2ln(22 (11(2 max {VT, vln(2/81}] sB.
Proof. Apply Lemma B.3 to bj by
C Omitted proofs
C.1 Omitted proofs from Section
2
Proof of F.c1 Given æ, x' and any set of output sequences set S, let W's be the set of all choices of random variables such that A(x;2) E S. Note that for all E N's A(r'; E S, i.c. for all z' E ((Ns), A(x': z') E S. Then
Pr (A(;))) z~
S]=
Pr E Ns) s ca(T-5) 20
Pr Pr E g(Vs)] 2/2
{ Pr
[A(1 A((2
This completes the proof of Theorem 2.1
Proof of Lemma 2.2 Let fLap (b) denote the density function of Lap(b). For all x, y E l::
(b))
|=1/b
yl -1 elul/b 1 (lttv///bb
wl/b fLop (b) + v).
26
2b
where the inequality follows from the triangle inequality + yl S |x| +lyl In the following integral, let z' = q(2). Let be as defined in the lemma statement. Then we have
à Il
Pr 12 EM = / II (b) #EZ
Pr
<
d xl/bb;
d
fLaP (bx)2)))a
*EN 2ml
*EN xm1
k
A II [tmp(bs) (2:) =Eq(N) f=1
e*
II SLmP (b=)((d)))
SEN i=1
e Pr 12 q(\)
This completes the proof of Theorem 2.2
17

---

C.2 Omitted proofs from Section 3
Proof of Lemma 3.7 Privacy. We use Fact 2.1 and Lemma 2.2 to argue privacy of our simple
algorithm, Asimple: Let x and x' differ at time j. Note that the prefix sums fulfill the following properties:
Ei= 2j Ei== of for all < and
E x Eisr Ti y for all 2 j. where y = = -/--
- zj [-1,1]]
Let S S raine(Asimple)". For any 2 j. consider the output distribution of length-T prefixes. There are two cases: For j = I and any S т, the output on æ is given by Σ x; + Z,-1 with t t- thus get equal output distributions and z'. That is,
Pr[A(E1,..... r.)T E ES] Pr(A(< +T E S] cg(0)=
E S).
For j < T. let Z = ZI...., - be the sequence of Laplace random variables used by the algorithm. For any fixed output sequence E S, note that the algorithm guarantees that 81 0 and let == 21, 22,,,,2--11 be the values that the Laplace random variables need to assume to get output sequence 8 with input x. That is, Σi= 2. + 2t St+1 for 2 1. We define a bijection satisfying
the properties of Fact 2.1 1.1el follows. Define q(2) z' such that
i isj
2
2i +
i>j
This gives === ohe #
81+1. All Laplace noises have the same distribution Lap(1/e). By Lemma 2.2 we have for any N support(2),
Pr fr E e M =E2
(T-))e f)s |z g(V)).
Thus, y fulfills the properties of Fact 2.1 and therefore our algorithm satisfies e-differential privacy with expiration g(() = I.
Accuracy. The error at time step t is given by æt + Ze-1. By the Laplace tail bound (Fact B.2 we have that
Pr Lapp/p(1/E)
[2/ x (og(TT/B]] < B/T
for any i [T 1].
Therefore, by a union bound, |Z,] S log(T/3) simultaneously for all E [1- with probability at least 1 - B. This implies that, with probability at least 3, the maximum error over the entire stream is bounded by = 1og(T/3).
Proof sketch of Fact 3.2 For b, the claim is immediate and so we prove for a b. First, consider the case where a 2 and b < 2 2 1. We show that in this case, there exists a set Dia,ij with the properties above, only it contains most one interval per level. If b 2 2
then Dia. = [[ab]], b]). Else, we have - a + < 2 thus there exists binary representation (go...., 1.- E (0, 1 such that b h- + = + 2q + 22 +... 2 -t-1- Note that for any j S É, there is an interval I of level j starting at a = 2 We now show how to construct the set D(o, In the first step, choose the largest such that g 1 and add the interval [26 2 + 2 1] to Dia,i-- Then, set fj 0. Next, assume we already cover the interval [a, s] for some b 2 a. We then again pick the largest remaining j such that q By an inductive argument, this interval will be in I, since s is the ending position of an interval of a higher level in I. We do this until more zj with gj remains, at which point
and add the interval [s. + 2 1] D Dja.o)-
have covered
[a, b). The same argument general case, pick l = [log(b)] and 2 -1 and define D Dio.b) Dia.e| U UD D|o+1.0)-
be repeated for the case where b 2 1 and 2 1. Now, for the
D
18

---

Proof sketch of Fact 3.3 First note that in our definition of Z, we exclude all intervals starting at O.
For given t, let E N be the greatest interval level satisfying 2
follows that for every
j > & E [0, 2 1] I. Analogously, for every j S we have $ [0, 1], and therefore
there must exist a unique T E I' such that T. Taken together, we have that [Z + where
t = llog t..
L
C.3 Omitted Proofs from Section
In this section, we give the detail proof for privacy analysis for all À E Ryo and accuracy analysis for 3/2, which is not covered in Section 4
C.3.1 Privacy proof for all X
Rgo
Proof of Lemma 4.1 We prove a slightly more general result; i.c. for all À R20, have the following bound on the privacy expiration function:
for d < B
2 1+ ((log(d - 1)+ 1)* -1))
1)]
g(d)
for B S and À *
2(1 log logld B B+ 1))
for B S and À
We wish use Theorem 2.1 satisfied.
For that, we first show that both the requirements in Theorem 2.1 are
By definition, A(x1x2............... ... Zz22 = therefore & I for all I E Djj.-- follows that for all I E Iz it holds that & D D(jrr-- Therefore, we have
21. For < j. we have $ [j 7') and
2/1
21
IEI.
TEL.
i=1
IET.
For t 2 j. we have that is contained in exactly one I E D Thus, 2/ 21 + y for
exactly one I In, and z/z. = 2y for I' E IX)[). Further, since 2 j. we have that E Ij = Ei=ra y. Together, we have
+ 21
y
Σ IEI.
+
Σ 1=1
2
Σ IEL.
2/1
IeIx
i=1
so the first property of Fact 2.1 is fulfilled.
2. By Fact 3.2
Di.-7 consists of most two intervals from each of I ......, where
I
E" = llog(7 ++++ 1)]. Thus, by Lemma 2.2 we have for any N E support (Z), then
log T
ly/E (1+ 0)1-X
Pr 1z M S exp
Σ
Pr Pr c(A)]
Ł=
(1)
< exp
28
Σ (1+
Pr E q(N)) =E2
19

---

Using Fact 2.1 with d = -- B+' -
-
we conclude differential privacy with privacy expiration
g(d)
0
Log d- B+1]] (1 f)^-1, Next we bound:
[log(d- B+1JJ
g(d) =
Σ
(1+
log B+11+1
1
x
dx
I= B+1)+1
= 1+
x=1
0(1 + log (d 1-++14 11)
Note that we use the assumption >> 0.
In the À 0 it instead holds that g(d) (log log(d B + 1)) by setting the value of À the first inequality and then using the bound on the Harmonic sum.
This is not point of discontinuity as the O(-) notation would imply. We treated À as a constant and derived the last equation in the above. If instead, we treat À as a parameter, have the following
g(d) 2 1+ (log(( - B B+ 1)²
f(A)
We can now evaluate the f(A) as À + 0 as follows: Since f(A) as an indeterminate form and noting that it satisfies the condition required apply the L.'Hôpital rule. Therefore, an application of I. L'Hôpital rule gives us
dx ((log(d B 1) 1)a 1)
lim f(A) = lim A
X-0
dx
lim log log(log(d - B + 1)) log (d B+ X
log(log(d B 1)).
That is, we have the desired bound on the privacy expiration. This completes the proof of Theorem 4.1
C.3.2 Accuracy proof when À 3/2
Recall that in the main text, we stated that for À = 3/2, we achieve
log(t- B3]
log
log log(t)
12
0
22
t=0
ビ=ル
This follows from straightforward computation by setting À = 3/2:
log
logt
(e
1)2(1-))
logt Σ
1
(011111o0 log(t)
=0
2 +1)
E2
Ž=U
20

---

While it seems like a point of discontinuity based on what we showed in Section 4 we now show that is not the case. Recall the following computation in Section
logt
log!
( 1)20-1))
82
ビ=
122(
1+
x 21 da dx
g²
2 (og(t)+2
1
3-2A
8²
2X
2=
Note that we did not include the last step. Now, setting the limits, get
Σ
1
(1 1
(log(t) 2
E²
3 -
Just as in the case of the privacy proof, we can compute the limit by applying L'Hôpital rule to get the desired expression.
C.4 Omitted Proofs from Section
Proof of Theorem 5.7 We define (0) = 0² to be the 0 stream of length T. Let TT such that 2C
divides T', and T T 2C, Since T 2C we have T" 2C and 7" > T/2. We define T" (2CC)
data sets (1). ,...,,.. (T' ((20)) as follows:
10 : {
te [2C 1, 1,
otherwise
For E (2C)) let S. be the set of all output sequences 01,..., oT E range(AA satisfying 02ch C, and #ack < for all k < i. Note that S; Sj 0 for i j where i, [T' (2()) Further, since by assumption A has error at most C' at all times steps with probability at least 2/3, we have that
Pr[A(T]) (
20 E S.] 2 2/3.
Recall that (9) and z:()) differ in exactly the positions f E [2C(i 1) 1, 2C%]. By the assumption that A satisfies e-differential privacy with expiration g.
2/3 S Pr(A(x11 (8)
(1) (2)) E S;
< DIO 20-1 a(i)s Pr[A(z] ..... _ 10) E S.]
= - a6))= Pr[A(2]
) E S.
Now, since the S,'s are disjoint, we have
T' ((2C)
Pr[A(z] ,...,, It ( E S.]
(0)
T' ((2C)
Σ (2/3)e (2/3)e-I,
E7 - g6)e
=1
(T' (22C))22/3) 235 '000
follows that
2C-1
Σ
g(i)= 2 (og(2TT 2 1og(T/6C)
1=
completing the proof of Theorem
5.1
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: All thcoretical results claimed are backed up by Theorems and I.4 both which have complete proofs, and our claims about empirical results are backed up by experiments, which can be reproduced using the code in the supplementary material. We also believe we accurately contextualize our contribution in the existing literature.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Yes, we believe we do. For our theoretical results, the clearest limitation is that it only holds for pure DP, not for approximate DP. We note that our techniques should extend to zero-concentrated DP Section 7 The other practical limitation is likely to be whether a framework that allows for a privacy loss that increases with time is of practical interest. We argue for its relevance in Section by pointing out that (i) it exists in practice, and, (ii) actively taking privacy expiration into account allows for better trade-offss between privacy and error (our Theorem than what is achieved in practice.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
22

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: All our theoretical results are provided with the full set of assumptions and are backed up by proofs, which, not in the main part of the paper, can be found in Appendix C
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The full experimental setup, together with the results, is given in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
23

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code for reproducing the result is provided as a zip file containing documentation and Python code. In particular, executing the included Jupyter Notebook will reproduce our figures.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co Dublic/guides Caaiae//CooSSuumisssccc oot.osoiiisiiooocooooooooooociil for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurIPS code and data submission guidelines (https / wtppps.ccppublic.. htapllic/gggiieee httpg//uuddeeeoeecuuiiiiieei wwtoobiissnooooiiiiiioo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The details provided in Section 6 should be sufficient to understand our empirical results, which involve training data.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our experiments involves exact computations of bounds the privacy loss for different algorithms. These computations are exact and involve no randomness, so no error bars are necessary, and this information is stated in Section
24

---

Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative етгог rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification: Our empirical results plots bounds on privacy loss for different algorithms, but it does not any of them. As the resources needed to produce the figures is not related to actually running the algorithms considered, these resources are not of interest nor reported.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ate::/nneuuipppe httpippp..ccppbbbpp hwtppubbicc.thhccciiiiieeeell.ed
Answer: [Yes]
Justification: Yes, our research involves no data and we otherwise conform to every other aspect in the Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
25

---

Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work has the potential expand the applications of differential privacy, the societal impact of which depends on the particular use case.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. dep.lymelm of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Not relevant to our research.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: We use standard open-source Python environment for experiments.
Guidelines:
26

---

The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release any new assets.
Guidelines:
The answer NA means that the paper does release assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
No crowdsourcing nor research with human subjects are involved in our paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing research with human subjects involved in paper.
27

---

Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
28


Reviews:
[{"review_id": "sPbkeJMo7j", "reviewer": "Reviewer_nwES", "summary": "This paper studies the DP counting problem in the continual release setting. The difference between the problem studied by this paper and the standard problem is that it allows earlier change of the element has a more relaxed privacy budget. The high level idea is to follow the previous pan-private continual counting framework but with different noise setup.", "questions": "Can authors provide any discussion of the tight bound when the function g grows as log^{o(1)}(.)?", "limitations": "There is no obvious potentially negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I believe the problem is fundamental and have a lot of potential application in the world. The DP continual release model with gradual privacy expiration would be a good tradeoff between accuracy and the potential privacy risk by classic refresh of privacy budget.\n\nThe algorithm is clean and easy to understand but the theoretical analysis requires solid work.\n\nAuthors also show almost matching lower bounds.", "weaknesses": "When the function g grows faster than a constant but slower than log^{o(1)}, then it is not clear what the tight error bound would be.", "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 question.\n\n*Q1: error bound for expiration growing as $\\log^{o(1)}(d)$.*\n\nOur algorithm also supports privacy expiration $g(d) = O(\\log\\log(d))$ when $\\lambda = 0$, which is shown in Appendix C.3.1. The accuracy guarantees for this case is given by setting $\\lambda=0$ in Theorem 1.2. For this case our lower bound is not tight. Achieving tightness for sublogarithmic privacy expiration is an interesting future direction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "u8jwIxlHbe", "reviewer": "Reviewer_RM2S", "summary": "This paper studies a variant of the continual release model of differential privacy where the privacy parameter degrades (potentially smoothly) with time, i.e., the $\\epsilon$ associated with changing a datapoint at time $t$ is $\\epsilon g(T-t)$ (the model was introduced by Bolot et al.). This model makes sense when a datapoint becomes less important to hide with time. This model also makes sense in the face of two facts about vanilla differential privacy under continual release: a) natural problems are subject to strong lower bounds, b)  In practical implementations, it is often assumed that the privacy budget 'renews' each day, and a privacy expiration function could allow for a more smooth decay of the privacy of a datapoint.\n\nThe main results of the authors are as follows:\na) They show that assuming a logarithmic privacy loss function ($g(d) \\approx \\log d$), a variant of the binary tree mechanism gives $O(\\log T)$ error (absolute difference). In contrast, in the vanilla privacy model, the best known error is $O(\\log^2 T)$ and a long open problem is whether $O(\\log T)$ is achievable. This paper shows that under the weaker notion of privacy, this error is achievable. They use a variant of the binary tree mechanism inspired by pan-privacy (adding $Lap(1/\\epsilon)$ noise to each interval). Intuitively, a change at tilmestep $t$ would only affect intervals between timestep $t$ and $T-t$ that include datapoint $t$, which is roughly $\\log (T-t)$ intervals so composing over these intervals would give privacy degradation $g(d) \\approx \\log d$. \n\nb) They also show a richer tradeoff between privacy degradation functions (which are roughly offset polylogarithmic functions) and error via a more careful variant of the binary tree mechanism.\n\nc) They use a packing argument to argue that these tradeoffs are tight in the worst case.", "questions": "1. I wonder if the pan-private inspired counting algorithm is needed? In particular, I wonder if the vanilla binary tree mechanism would give you the same bounds given the intuition in the summary (this might be formalizable using post-processing functions that depend on the pair of neighboring datasets but not on the individual dataset within the pair, and noise couplings similar to what the authors do- but perhaps I am mistaken). If such an argument worked, it might be nice to write some general 'composition' theorems that can be used in followup work that prove privacy in this model.\n\n2. Do the authors have any thought on whether this model could help plug larger gaps between the continual release and batch models? Some discussion on this and an open problems section would be good to include in the final version of the paper.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) The privacy model is interesting and merits further work, since it suggests a way to get around lower bounds/gaps in the continual release model of differential privacy while giving meaningful privacy. It's nice that the longstanding logarithmic gap in accuracy for continual counting can be plugged under this relaxation.\n\n2) The paper is well written and easy to follow.", "weaknesses": "1) The results presented seem relatively unsurprising given the intuition based on composition discussed in the summary\n\n2) The $\\log T$ vs $\\log^2 T$ gap is relatively small; it would be much more interesting if larger (say, polynomial) gaps could be plugged using this model with reasonable privacy expiration functions.", "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*Q1: why not use the vanilla binary mechanism*\n\nIt can be shown that the vanilla binary mechanism satisfies the same error/privacy expiration as our algorithm for $\\lambda=1$. We however do *not* believe that the vanilla binary mechanism can be easily adapted (by varying the noise distributions across levels) to match our guarantees on error and privacy expiration for $\\lambda \\neq 1$. We sketch an argument for why we believe so next.\n\nOur privacy argument relies on the fact that shifting noise values covering the interval $[j, \\tau]$ can hide the value of $x_j$ for $t\\in[j, \\tau]$. It is important that the noise values used in the cover are from level at most $\\ell = O(\\log(\\tau - j))$. For the vanilla binary mechanism however, to hide the exact value of an input $x_j$, we need to shift all ancestors to $x_j$ that are used when producing outputs for $t\\in[j, \\tau]$, and for this set of noise values we do not have the same guarantee on what level in the tree they are from. For example there exists $1 < j=\\tau$ where the single node needed to shift will be at level $\\ell = \\Omega(\\log(\\tau))$. This makes the privacy proof in Appendix C.3.1 breaks down when $\\lambda \\neq 1$.\n\n*Q2: privacy expiration for other problems*\n\nWe believe it is plausible that the model could be useful to get new trade-offs in other continual problems. Specifically, it would be an interesting direction for future research to study problems in this model, where there is known to be a polynomial error gap between the batch model and the continual release model (for example max sum and counting distinct elements). We will include a discussion of this direction as potential future work in the final version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZeuLJRlvQU", "reviewer": "Reviewer_naYA", "summary": "Modern DP solutions are often working in the setting where the new data is coming daily. However, DP doesn't allow querying the data indefinitely; therefore, all of these solutions are either treating database as partitioned by time, or refresh the budget on some schedule. \n\nBoth of these approaches are not ideal, this paper studies an alternative solution: it assumes that older data is less sensitive, therefore releasing more information about the past is ok. Using this definition, it proposes continual release schemes that gives better utility guarantees than solutions in the case where there is no privacy expiration.", "questions": "On line 21: Here and further down the text, there are a lot of references given as a list: it would be either cite an overview or say something about each reference. \nOn line 30: As it was mentioned before, information about visiting some websites could be less sensitive if they happened a week ago, but information about visiting others is not diminishing in sensitivity.\nOn line 35: Such strong statements require more than personal communication.\nOn line 36: Usually not users, but datasets are allocated budget.  \nOn line 39: It would be appropriate to give some references on systems that refresh budgets. \nOn line 42: While I agree that refreshing budgets could be problematic, it is worth to note that it is e ssentially equivalent to the setting with linear expiration.\nOn line 54: Claim about O(1) run-time is not supported by a theorem in the text. \nOn line 111: Why do you need f, wouldn't it be enough to define everything with g? \nOn lines 152-157: This section is supposed to give intuition to the proofs, but it is not clear what it says. \nOn line 187: You need to define q(N)\nOn line 235: I_t is infinite, how can you bound its size? \nOn line 242: It should be y=x_j - x'_j\nOn line 254: It doesn't seemed to be true that z_I' = z_i + y only for one I", "limitations": "NA", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The setting the paper studies is very important and it is the first paper that was able to achieve better guarantees in this regime.", "weaknesses": "In most of the settings where the data is sensitive, sensitivity doesn't diminish with time or at least not diminish uniformly; e.g., ads information might reveal some information about sexual orientation and sensitivity of this information is not guaranteed to expire, while it could also reveal the fact that a person is looking for a new job and sensitivity of this information is decreasing with time (however, it is not clear how quickly it decreases).", "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 their exact questions/comments. We will incorporate the comments into the final version, and address a subset of them below.\n\n*line 42: refreshing budgets means linear expiration*\n\nWe agree; we will state this explicitly in the introduction.\n\n*line 54: no theorem for time/space complexity*\n\nThis is true but the argument for it is direct, and it is sketched out on lines 293-298.\n\n*line 111: why $f$*\n\nIt is only to say that if $f$ dominates $g$, then by definition the algorithm is also private with expiration function $f$. See lines 105-108.\n\n*line 235: how we bound $|\\mathcal{I}_t|$*\n\nThe critical observation is that the dyadic interval set $\\mathcal{I}$ excludes every interval containing $0$, and so $t$ intersects intervals up to level $\\ell = \\lceil\\log t\\rceil$. A proof sketch is given in Appendix C.2.\n\n*line 254: about $z_I’$*\n\nThe statement is true. For each $I$ in the decomposition $D_{[j, \\tau]}$, we shift its corresponding noise $z_I$. By definition of $D_{[j, \\tau]}$, it cannot contain overlapping intervals, and so $\\mathcal{I}\\_t$ cannot intersect with more than one interval from $D_{[j, \\tau]}$. There is therefore a unique interval $I\\in\\mathcal{I}_t$ where $z_I’ = z_I + y$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BtSFR8Bjsm", "reviewer": "Reviewer_V4mB", "summary": "The paper studies differential privacy with gradual expiration models, gives upper and lower bounds for a large set of expriation functions $g$. The proposed algorithm can achieve an additive error of $O(log(T) / \\epsilon)$, matching the lower bound. Empirical evaluationshows that the algorithm can achieve smaller privacy loss.", "questions": "1. Is it possible to use the matrix mechanism (techniques from references [8], [10], [11]) to improve the constant term in the error analysis? Could you discuss the challenges of applying these techniques in differential privacy models with gradual expiration?", "limitations": "See Weakness and Question", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. An analysis of upper and lower bounds for privacy with gradual expiration is provided. The proposed algorithm has an error that matches the lower bound, theoretically guaranteeing its performance.\n\n2. The algorithm can run on unbounded streams, unlike previous methods that require a fixed $T$. This adds more flexibility to its usage.", "weaknesses": "1. I find the description in Section 3.2 very abstract. Providing examples similar to those in [2] could help readers understand the descriptions better.\n\n[2] Bolot, Jean, Nadia Fawaz, Shanmugavelayutham Muthukrishnan, Aleksandar Nikolov, and Nina Taft. \"Private decayed predicate sums on streams.\" In Proceedings of the 16th International Conference on Database Theory, pp. 284-295. 2013.", "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 question.\n\n*W1: Section 3.2 is too abstract*\n\nWe will include examples to make the related concepts in Section 3.2 more intuitive.\n\n*Q1: matrix mechanisms with privacy expiration*\n\nIt is possible that techniques related to matrix mechanisms can be leveraged to improve the constant term in the error analysis. In the case of our algorithm, it is not clear how it could be expressed as a matrix mechanism, nor is it clear what the structure of the matrices must be to implement a given privacy expiration function. We believe it is an interesting future direction and will include a discussion of it.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ba8NyeVkvL", "reviewer": "Reviewer_L11a", "summary": "This paper studies the continual counting problem, under a “relaxed” privacy notion, where the privacy budget is a function of time, aka differential privacy with expiration functions. This notion, proposed by Bolot et al.[2], captures the settings where data becomes less sensitive with time. The paper proposes an algorithm based on the pan-private tree-based mechanism of Dwork et al. [12]. They show that this algorithm verifies DP with expiration function $g(d) \\sim 1 + \\log^\\lambda(d)$, which improves on the constant $g(d) = \\log(T)$ expiration function of directly using the analysis of Chan et al [6], or the $g(d) = 2\\log(d + 1) +2$ of directly analysing the pan private tree-based mechanism of Dwork et al. [12].", "questions": "- How should $\\lambda$ in Algorithm 3 be chosen?\n\n- Can the techniques/ideas proposed to analyse Algorithm 3 be adapted to improve the analysis of the pan-private algorithm of Dwork et al. [12] for the classic setting without expiration?\n\nMinor comments/typos:\n\n- In Definition 1.1, shouldn’t S be of length $\\tau$?\n\n- In the algorithms pseudo codes, shouldn’t the noise drawing steps (Line 2 in Algorithm 1 and Line 3,4 in Algorithm 2) be inside the “for t “ loop?  Or do you draw all the noises beforehand, i.e. the whole sequence $(Z_t)_{t = 1}^\\infty$?\n\n- In algorithm 3, shouldn’t Line 8 be $\\sum_{I \\in \\mathcal{I}_t} Z_I$, since $\\mathcal{I}_t$ defined in Line 2 only includes steps $t-B$? \n\n- It would be better if the paper included a proper definition of the accuracy of a counting task and the different types of errors.", "limitations": "As noted by the authors, the only limitation is that the \"gradual expiration\" setting may only be relevant for specific applications. As expressed in the weakness section, a better motivating example would give better intuitions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem is well-motivated and interesting\n\n- The paper is well-written and easy to follow\n\n- The analysis is complete (upper/lower bounds, different types of expiration functions), and the main ideas are stated clearly\n\n- The experiments validate the theoretical findings.", "weaknesses": "- The technical gap is limited compared to Dwork et al. and Chan et al..\n\n- Algorithm 3 is less intuitive, especially the role of $\\lambda$, and its analysis is less clear.\n\n- There is a need for better/more examples to motivate the setting. The example of tracking visits to a location/website arguably does not capture the definition used. For example, if the website changes its content from offensive to less offensive content, one may argue that visiting the website in the old version is even more revealing and more sensitive than visiting the new version, which is the opposite setting to yours.", "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*Q1: how to set $\\lambda$?*\n\n$\\lambda$ is provided by the user together with the input, and should reflect their privacy goals. The larger we make $\\lambda$, the weaker the asymptotic privacy guarantee becomes to the benefit of the error, as outlined by Theorem 1.2. Ultimately, running the algorithm with some $\\lambda$ is more private than a direct non-private computation.\n\n*Q2: can our analysis improve Dwork et al.’s analysis?*\n\nOur idea of not including the left-most intervals in the dyadic interval set can be used to add $O(\\log t)$ noise terms at time $t$, instead of $O(\\log T)$. This translates into a constant improvement for their mean squared and $\\ell_\\infty$ error. We however note that it would be interesting future work to formalize a notion of privacy expiration with pan-privacy.\n\n*C1: length of $S$*\n\n$S$ is a set of tuples of outputs. The probability of any tuple of length $\\neq \\tau$ is $0$, so the definition is valid.\n\n*C2: drawing of noise*\n\nWe assume the noise is ‘drawn on demand’ inside the for-loops, not before entering them. Lines 175-177 describe how noise is drawn for our algorithms, but we will try to make this more clear.\n\n*C3: Line 8 algorithm 3*\n\nCorrect, we will fix it.\n\n*C4: proper definition of accuracy*\n\nWe will include a formal definition in the full paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper considers a continual counting problem in the privacy expiration model of [Bolot et al., ICDT 2013]. The input here is a stream $x_1, \\dots$; the goal is to, after receiving each $x_t$, release an estimate of the sum $x_1 + \\dots + x_t$. The privacy expiration model states that, for each $x_i$, the privacy loss after step $t$ can increase as $t - i$ increases; namely, it can be $\\epsilon \\cdot g(t - i)$ for some non-decreasing function $g$. The main result of this paper is that, for a large class of function $g$, there is an algorithm with ($\\ell_{\\infty}$-)error $O(\\log T / \\epsilon)$, which improves on the standard model (where $g$ is a constant) whose best known error is $O(\\log^2 T / \\epsilon)$. The algorithm is based on the so-called binary tree mechanism [Dwork et al.; Chan et al.] with two main changes: (i) delaying the release of recent $x_i$ by ignoring them completely as long as $t \\leq i + B$ for some $B$ and (ii) adjusting the privacy budget allocation of each level of the tree. In addition to this, the authors also provide a lower bound which is tight for some setting of $g$.

Overall, even though the algorithm is a simple modification of a known algorithm, the algorithm is clean & practical and it demonstrates the power of the privacy expiration model, which might offer an alternative solution to the standard continual release setting. Furthermore, given that the continual counting algorithm is a subroutine for many algorithms, it is likely that the result in this paper can be used to build other algorithms in this model. Due to this, we recommend accepting this paper as a poster.
Decision: Accept (poster)