Edit-Neighboring Data Streams and Privacy under Continual Observation Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger, Roodabeh Safavi Institute of Science and Technology Austria
arXiv:2607.20727v1 [cs.DS] 22 Jul 2026
Abstract Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the online setting. In prior work, this formulation requires that any private mechanism when given as input two neighboring streams that differ in the value of at most one stream element must generate output streams that are almost indistinguishable. In this paper, we consider a more general notion of privacy wherein an individual’s decision to participate in the data collection process may potentially shift the entire stream by a time-step. We define a new notion of edit-neighboring streams that captures this scenario. Our findings are as follows. First, we prove that on a stream of length T , no additive-noise mechanism achieves additive error less than Ω̃(min{T 1/3 /ε2/3 , T }) when required to be ε-DP under CO for edit-neighboring streams. In particular, this includes state-of-the-art continual counters constructed via the factorization mechanism that in the standard neighboring setting incur only polylogarithmic additive error. Second, we construct the first mechanisms with polylogarithmic additive error for our more stringent notion of privacy. We show that we can recover the same additive error as in the standard notion of privacy albeit with worse constant coefficients for both arbitrary input streams and sparse streams. Third, we show that the notion of edit-neighboring streams inhabits a ‘sweet-spot’ in terms of generality and additive error incurred. More precisely, we show that the even more general notion of prefix-sum neighboring streams—which arises naturally in reductions for problems under CO—must incur additive error scaling as Ω̃(min{T 1/3 /ε2/3 , T }) for any mechanism that is ε-DP under continual observation. Finally, we show empirically on synthetic data that when compared with prior work, our mechanism achieves a superior trade-off between the success probability of a simple distinguishing attack, and the additive error incurred by the respective mechanisms.
Contact: {joel.andersson,anamay.chaturvedi,monika.henzinger}@ist.ac.at, [email protected].
1
1
Introduction
The seminal works Dwork et al. (2010) and Chan et al. (2011) introduced the notion of differential privacy (DP) under continual observation (CO), or DP-CO in short, to reason about the loss in privacy that occurs when an analyst collects sensitive data over time, and outputs the values of a sensitive function of the accumulated data iteratively. This definition has proven to be widely influential, as it captures important instances of sensitive data monitoring, such as federated learning of on-device language models (Xu et al., 2023), and continual release of aggregate web-service statistics, where the absence of any privatization has been shown to leak individual behavior (Calandrino et al., 2011). At a high level, we say that a mechanism M : X ∗ → Y ∗ is (ε, δ) DP-CO if for any pair of neighboring data streams x, x′ ∈ X ∗ , and any set of output streams Y ∈ Y ∗ , Pr[M(x) ∈ Y ] ≤ eε Pr[M(x′ ) ∈ Y ] + δ. Here, x and x′ are considered neighboring if they have the same length, and if there is at most one index t such that xt ̸= x′t - we will refer to this notion as swap-neighboring. Intuitively, this definition captures the idea that the value of an individual’s contribution at a particular time-step does not significantly perturb the output distribution of a DP mechanism. Dwork et al. (2010) motivate this notion of (event-level) adjacency by modeling the iterative process of processing a stream of inputs and generating outputs as occurring over an atomic sequence of discrete time intervals. Each stream element is the value contributed by an individual, and in each time interval a mechanism receives a value, processes it, and generates a new output. They point out that since they are studying real systems where time must be accounted for, they identify time-steps where “nothing happened”, i.e., no stream element was given to the mechanism, with receiving values of 0. Further work by Dong, Luo, and Yi (Dong et al., 2023) introduced the symbol ⊥ to depict the absence of a value received at certain time-steps; this avoids conflating the absence of an input with a 0-valued input for problem settings where the two symbols are semantically distinct. There is a large quantity of prior work (Kifer and Machanavajjhala, 2011, 2014; Kasiviswanathan and Smith, 2014; Tschantz et al., 2020) in the DP literature reasoning about the semantics of privacy and apt definitions of neighboring data sets, given the threat model and the adversary’s side information. At a high level, the analyst should be able to promise an individual that the latter’s decision to participate in the data collection process does not significantly change the output of the mechanism. More concretely, the posterior belief of an adversary after observing the mechanism’s output if the individual participates in the process should be close to the counterfactual posterior if they choose not to participate in the process. The choice of neighboring relation determines which counterfactual the privacy guarantee binds. The standard decision to model neighboring streams in the CO setting using swap neighbors ensures that the mechanism is insensitive to their value. Adding a ⊥ symbol to the data universe X to indicate non-participation is more general than just the swap-neighboring definition by itself, but we argue below that this by itself does not suffice to capture all counterfactual neighboring streams when the goal is to hide participation. For example, consider an individual who has the option to participate in the data collection, but with the constraint that they can only contribute their value x∗ at some real-world time r∗ . Following Dwork et al. (2010), we consider a DP-CO mechanism that discretizes time into atomic steps, and accepts at most one individual’s value per time-step. If the individual chooses to participate in the data collection, then the real-world time r∗ at which they may contribute their value must be mapped to some time-step t∗ . Let x = (x1 , . . . ) be the ‘default’ data stream that would be received by a mechanism in the CO setting if this individual does not participate. We consider two situations. If in the absence of the user’s contribution the time-step t∗ was such that xt∗ = ⊥, i.e., no other user participated at a real-world time which was mapped to t∗ , then the counterfactual stream for when the user does participate is defined simply by defining x′t = xt for t ̸= t∗ , and x′t∗ = x∗ . On the other hand, if the default stream were such that xt∗ ̸= ⊥, then the real-world time r∗′ of some other individual was also mapped to t∗ . Since the mechanism can process only one individual per time step, a choice must now be made the mechanism sets either x′t∗ = xt∗ or x′t∗ = x∗ . Regardless of the tie-breaking rule, we now have an extraneous value that must again be allocated a position in the stream. The natural choice would be to then set x′t+1 equal to the extraneous value, but this leads to the same problem when xt+1 ̸= ⊥. 2
We see that the counterfactual stream necessarily involves a sequence of shifts until the next ⊥ value is encountered - in the absence of a ⊥ value, potentially the whole stream, starting from the time step t, is shifted by 1 unit. This example illustrates a gap between existing notions of adjacency studied in the CO setting, and what counterfactual streams look like when the goal is to privatize an individual’s decision to participate in the data collection of a CO mechanism. In this paper, we study the significance of this shifting artifact by focusing on the continual counting problem in DP-CO. The continual counting problem was introduced by Dwork et al. (2010); Chan et al. (2011) in the very first works in DP-CO. The analyst is given a stream of real-valued inputs, and must output at each time step an estimate of the sum of all inputs seen so far. If the exact counts are released, then the counter reveals all stream values. When the privacy of the stream must be preserved, the analyst must compute some noisy outputs that balance utility and privacy over time. As a motivating example, consider a testing facility that publishes a running count of the number of positive COVID test results observed so far. Here, each input xt ∈ {0, 1} indicates whether the t-th test is positive or negative, and a value xt = ⊥ indicates that no-one tested at time-step t. Continual counting is one of the foundational problems in the study of DP-CO, and serves as an excellent starting point for our investigation of counterfactual data streams and neighboring relations.
1.1
Our contributions
I. Edit-neighboring streams. To capture the sort of counterfactual stream described above via the neighborhood relation that privatizes participation, we introduce a notion of adjacency that allows for streams with an arbitrary number of contiguous shifts to be neighboring. This captures the collision scenario and queuing phenomenon that we discuss; a single insertion at any point can lead to an arbitrary number of downstream shifts, and any ⊥ values encountered absorb and terminate this sequence of shifts. Definition 1.1 (edit neighboring, informal). Suppose a mechanism accepts input for some T timesteps. Given x, x′ ∈ (X ∪ {⊥})∗ and a time step i ∈ [T ], let j be the first time step after i with x′j = ⊥; if no such time step exists, let j = T + 1. We define x and x′ to be edit-neighboring if x′k = xk for k < i, xi ∈ X , x′k−1 = xk for i + 1 ≤ k ≤ min{j, T } and x′k = xk for j < k ≤ T , i.e. the time steps “between” i and j are shifted. The above definition captures settings where the system is run for a certain number of steps T , and thus if a shifting occurs and the last input ends up in spot T + 1, it will not be processed and is not considered part of an input. For example, if the last person of a queue reaches a COVID testing center when no more slots are available, they will not get tested. One can also consider a natural variant of edit neighboring which allows different lengths for neighbor streams and covers the scenarios where the system continues processing until the data generation process indicates that the stream has terminated. We address this as well by a simple reduction to the fixed time-horizon setting defined above, so for exposition we focus primarily on the simpler definition described here. We note that this definition can lead to the challenging setting where many bits in the input differ. For example, if (xi , xi+1 , . . . , xj ) = (0, 1, 0, 1, . . . , 0, 1, ⊥), then x and x′ differ in all values starting from i + 1 to j. Thus, this definition requires us to “hide” the difference of j − i many bits from the adversary and not just one bit as required by the classic definition of neighboring streams. The edit neighboring definition gives us the expressiveness to represent arbitrarily long time stretches where no data is recorded, and also protect settings where an insertion collision at one time step causes all entries to shift. Further, in contrast with some prior works on continual counting, in this paper we will consider real-valued inputs xt ∈ [0, 1], as opposed to just the binary setting xt ∈ {0, 1}. II. Lower bounds for private continual counting for edit-neighboring streams. At the outset it is not clear whether one can achieve a good trade-off between privacy and accuracy for continual counting when measuring privacy loss by defining adjacency via edit-neighboring streams. The privacy analyses of the state-of-the-art (Henzinger et al., 2025a) data-independent factorization mechanisms require their inputs to have low ℓ1 -sensitivity, i.e., ∥x − x′ ∥1 ≤ 1. However, when shifts are introduced, the ℓ1 -sensitivity between neighboring inputs can be as high as T , leading to polynomially scaling additive error. We find that this is not just a shortcoming of the analyses, but that in fact all data-independent additive-noise mechanisms (i.e., mechanisms which add noise to the prefix sums where the additive noise is independent of the sums) must incur polynomial error in this setting. 3
Theorem 1.2 (Lower bound, informal). Let ε ∈ (0, 1/2], δ ∈ [0, 1), and T ∈ N be sufficiently large. Let M be an (ε, δ)-DP algorithm for continual counting on {0, 1, ⊥}T with edit-neighboring streams. Suppose that M is a data-independent additive noise mechanism. Then, with probability 0.99, it incurs additive ℓ∞ error α where n 1/3 o 1. If δ = o(ε/T ), then α = Ω̃ min Tε2/3 , T . nq o T 2. If δ = 0, then α = Ω min . ε ,T III. Continual Counting Mechanisms with polylog additive error for edit-neighboring streams. The lower bounds above suggest a significant gap between the privacy-accuracy trade-offs for swap neighboring and edit-neighboring streams for data-independent additive-noise mechanisms. We address this gap by developing a meta-algorithm SimECC (Simple edit-neighboring Continual Counter) that takes as input any continual counting algorithm that preserves privacy in the standard setting as a black box, and constructs a continual counter for the edit-neighboring setting whilst incurring additive error close to that of the standard setting. Theorem 1.3 (Upper bound, informal version of Theorem 6.3 and Theorem 6.5). For privacy parameters ε > 0, δ ∈ (0, 1), there exists an algorithm ECC that is (ε, δ) DP-CO for edit-neighboring streams, p and with probability 1 − δ for all time-steps t ≥ 1, incurs additive error O( 1ε ln t ln(t/δ) ln(1/δ)) + O( 1ε log(t/δ)). In comparison, state-of-the-art (ε, δ)-DP continual counters in the swap-neighboring setting have the guarantee that for any failure probability β > 0, with probability 1 − β, for all t ≥ 1, they incur p additive error of the form O( 1ε ln(t) ln(t/β) ln(1/δ)). Given any fixed constant c > 1, if δ = β c , then the additive error SimECC incurs matches that in the standard setting up to constant factors. In real-world data collection the data generation might be bursty and sparse, leading to input streams consisting mostly of ⊥ values, which increases the additive error polylogarithmically even though most of the time no data is being collected. We show how to handle sparse streams by giving a more general mechanism ECC (edit-neighboring Continual Counter) that adapts to the sparsity s(x, t) of the data generation process, defined by the expression s(x, t) :=
t X
1(xi ̸= ⊥),
i=1
i.e., s(x, t) is the number of non-⊥ values observed. We see that in the real-valued setting wherein xt ∈ [0, 1] for all t ≥ 1, the prefix sum t X st = xi i=1
is bounded from above by the sparsity s(x, t) for all t. ECC incurs data-dependent additive error that scales primarily with the prefix sum of the input stream. Our mechanism incurs additive error that scales polylogarithmically only with st , instead of with t. The dependence of the additive error on the stream length t is relegated to a lower order log t additive term. This extends prior work by Dwork et al. (2015) for swap-neighboring streams to the edit-neighboring setting. Theorem 1.4 (Upper bound, informal version of Theorem 4.8, Theorem 4.3 and Observation 4.7). In the same setting as Theorem 1.3, there exists a mechanism that is (ε, δ) DP-CO for edit-neighboring streams that, with probability 1 − δ for all time-steps t ≥ 1, incurs additive error p 1 1 O ln st ln(st /δ) ln(1/δ)) + O( ε log(t/δ) . ε IV. Lower bounds for prefix-neighboring streams. Given that similar additive error is achievable whilst fulfilling a stronger notion of privacy, a natural question is whether it is possible to further generalize the notion of neighboring streams. In the privacy literature one such notion that is studied 4
1.0
Advantage
0.8 0.6
Per-run RMSE
BaseCC SimECC GaussianCC PartitionCC
0.4 0.2 0.0 10
1
10
2
10
3
10
4
10
3
10
2
10
1
ECC SimECC GaussianCC
10
3
10
4
10
5
10
6
Stream length T
Per-run RMSE
(b) Per-run RMSE vs T .
(a) Attacker advantage vs. per-run RMSE.
Figure 1: Plots evaluating mechanism performance on Bernoulli streams. Figure 1a uses T = 104 , δ = 10−5 , and alternating Bernoulli rates p ∈ {0.1, 0.9}T on blocks of width 10, with each point shown being the average over N = 20000 runs for ε ∈ {0.10, 0.19, 0.38, 0.73, 1.4, 2.8, 5.4, 10, 20, 40, 77, 150}. Figure 1b uses ε = 10, δ = 10−5 a constant Bernoulli rate of 0.01, with each point shown being the average over N = 100 runs for one value of T ∈ [103 , 106 ]. The error bars on the per-run RMSE are showing the standard error (SE), and the error bars on the advantage are 95% Clopper–Pearson confidence intervals; N has been set such that the error bars are small enough to be barely visible. Advantage is defined as 2 · Pr[Adversary guesses b correctly] − 1. is that of prefix-sum neighboring streams. Two streams are prefix-sum neighboring if the prefix sums of one stream always trails the other by at most 1. This property holds for certain dynamic problems when reduced to continual counting on difference sequences, e.g., as in the case of counting distinct elements (Jain et al., 2023a; Andersson et al., 2026). However, we show that no DP mechanism can achieve sub-polynomial error in this even more general setting. Theorem 1.5 (Lower bound, informal). Let ε ∈ (0, 1/2], δ ∈ [0, 1), and T ∈ N be sufficiently large. Let M be an (ε, δ)-DP algorithm for continual counting on {0, 1}T with prefix-sum-neighboring streams. Then there exist inputs for which, with probability 0.99, it incurs additive ℓ∞ error α where n 1/3 o 1. If δ = o(ε/T ), then α = Ω̃ min Tε2/3 , T . nq o T 2. If δ = 0, then α = Ω min , T . ε V. Experiments on Synthetic Data. Our first lower bound (Theorem 1.2) and upper bound (Theorem 1.3) together imply that the vast majority of existing swap-private mechanisms, when applied to edit-neighboring streams, must incur exponentially larger error to provide a privacy guarantee comparable to our mechanism. This separation is however asymptotic - it says nothing about whether it manifests for streams of moderate length seen in practice, or whether the separation requires carefully engineered, and very long, worst-case inputs. We empirically demonstrate that a separation appears already at T = 104 , on inputs drawn from a structured (and arguably realistic) distribution, under a simple attack. Recall that edit-neighboring captures a scenario where an individual’s participation inserts an event shifting subsequent events along time. In particular, if the stream x ∈ {0, 1}T is sampled from a distribution with temporal patterns, then the offset in the pattern can potentially be detected in the output of a continual counter. We instantiate this concretely: a defender draws a Bernoulli stream x(0) of length T = 104 with rate alternating between 0.1 and 0.9 in blocks of 10, samples a challenge bit b ∈ {0, 1}, and releases y = M(x(b) ) where x(1) is an edit neighbor of x(0) derived by inserting a 1 at position 1. The attacker, given knowledge of the Bernoulli rate profile and y, computes a linear statistic on y to infer the value of b. We compare two continual counters (BaseCC, PartitionCC) for swap-neighboring streams against our edit-neighboring private mechanism SimECC, and a baseline for edit-neighboring streams based on releasing the prefix sum at each step with the Gaussian mechanism (GaussianCC). On fixing δ = 10−5 and sweeping ε, we plot the trade-off between the advantage (defined as 2 Pr[b guessed correctly] − 1) 5
of the attacker, and the per-run root-mean-squared error (RMSE) of the mechanism. Intuitively, a smaller ε should promote lower advantage but comes at a cost of higher error, and the shape of this trade-off becomes our basis for comparison. We are in particular interested in comparing them at a given bound on the attack advantage - the analyst is interested in knowing what error they must pay to bound the attack success rate of the attacker. Figure 1a shows the result. To bound the attacker’s advantage at 0.1, BaseCC and PartitionCC must incur error 9× and 3× larger respectively than SimECC; GaussianCC also has to pay roughly 3×. Figure 1b sweeps T ∈ {103 , 104 , 105 , 106 } for the edit-neighboring continual counters, demonstrating that the error gap to the Gaussian baseline grows with T , in line with the predicted polylog vs. polynomial error growth. Summary. Our main theoretical findings are that the notion of edit-neighboring streams is strictly more general in terms of characterizing privacy loss than the standard setting, and still permits additive error on the same order. Further, this notion of edit neighboring seems to achieve a ‘sweet-spot’ in terms of the additive error incurred, as the only more general setting that we are aware of must provably suffer additive error that is exponentially larger. Empirically, we find that in an idealized toy model, even for randomly generated data following a schedule known to the adversary, to restrict the attack advantage of the adversary to the same value requires incurring significantly more error for private continual counters designed for swap-neighboring streams when compared with our mechanisms for edit-neighboring streams.
1.2
Related work
The issue of insertion collisions has been implicitly addressed in different ways in prior work. Most works, starting from Dwork et al. (2010) and Chan et al. (2011), assume as a fact that at every atomic time-step, at most one value is received, and that therefore the swap model suffices. In principle this could be achieved by a sufficiently fine discretization of time, depending on the rate of data generation. This approach has the caveat that a finer discretization of time invariably leads to more additive error, even for fundamental tasks like counting, and a good choice of discretization requires some prior knowledge of how high the data generation rate could be. The model assumption fails if this prior is incorrect. Cardoso and Rogers (2022) allow arbitrarily many values to be received per time-step, so the input to the mechanism is a sequence of sets, as opposed to singletons. This avoids the discretization issue but introduces a different issue. Real-world systems have capacity limits and bottlenecks; when the data generation rate exceeds the system’s per-step capacity, excess inputs are queued even prior to time-stamping, in which case the model’s per-step set no longer matches what the system processes. The natural fix is truncation, wherein if the number of inputs exceed per-step capacity, then elements that arrive once capacity is reached are simply dropped. However, truncating sets introduces data-dependent error when server capacity is below the data-generation rate, since discarded data is permanently lost. In contrast, our model buffers excess data; bursts exceeding capacity incur only temporary delay, and any induced error disappears once the buffer clears. Moreover, dropped points may be correlated. If bursts align with server time steps and contain mostly 0’s initially and 1’s later, truncation disproportionately removes 1’s, producing error that need not remain sublinear in the number of time steps. Beyond the question of per-step capacity, the choice of adjacency relation itself has been refined in prior work. The closest prior precedent for our edit-neighboring relation is the insert-delete adjacency introduced by Casacuberta et al. (2022) for the batch DP setting. Their work identifies a class of vulnerabilities in deployed DP libraries: finite-precision arithmetic (floating-point non-associativity and integer overflow) makes the implemented sensitivity of basic statistics like sums substantially larger than the idealized sensitivity used to calibrate noise, breaking the DP guarantees of essentially every major library at the time. Their definition of insert-delete adjacency is structurally similar to the edit-neighboring relation we introduce here; both define neighbors via the insertion or deletion of a single record, with downstream records shifting accordingly. However, other than the difference in setting and techniques, there is also a significant difference in motivation. In the batch setting, ordering is irrelevant to sensitivity except as a finite-precision artifact, so an ordered adjacency relation is needed only to address implementation vulnerabilities. In continual observation, ordering is intrinsic to the setting; participation shifts the 6
timing and order of downstream records even for the theoretical model.
Independent concurrent work In independent work Chan et al. (2026) study single-edit neighboring user streams. Their goal is to construct DP-CO mechanisms with adaptive adversaries, with a notion of neighboring streams which is a special case of ours: given a stream of user events (e.g. value contributions), a neighboring stream is constructed by inserting an event at some time-step t, and incrementing the index of every element from this point onward by 1, but they do not allow ⊥ values, i.e., they do not formalize non-participation. Algorithmically, their algorithm is a generalization of our SimECC mechanism. As they do not allow ⊥ values, they do not consider limited cascades of shifts, or sparsity-adaptive methods, such as our ECC mechanism. This is one of our main contributions. They also do not study any lower bounds for edit-neighboring or prefix-sum-neighboring streams. Chan et al. (2026) give a general approach towards adapting standard DP-CO mechanisms for the edit-neighboring setting, with a randomized binning wrapper that converts any standard DP-CO mechanism into an edit-neighboring DP-CO mechanism. They incur slightly p more additive error (in their setting called backlog) of O( 1ε ln(t) ln(t/δ)) compared to the O( 1ε ln(t) ln(t/δ) ln(1/δ)+ 1ε log(t/δ)) error that our continual counting method SimECC achieves.
2
Technical Overview
I. Edit-neighboring streams and the SimECC mechanism Let us consider a pair of edit-neighboring streams x = (x1 , . . . , xT ) and x′ = (x′1 , . . . , x′T ), where for simplicity, in this overview, we assume neither of x and x′ contains a ⊥, and where x is an insertion neighbor of x′ at step i ∈ [T ], i.e. x is obtained from x′ by inserting xi after x′i−1 , shifting all subsequent elements x′i , . . . , x′T one position to the right, and discarding the last element x′T . Note that insertion neighbors are also edit neighbors if there are no ⊥s. Our goal is to design a continual counter such that if the respective output streams for x and x′ are denoted y and y ′ , then the distributions of y and y ′ are (ε, δ)-indistinguishable. Further, for any fixed stream x, the output y should be “close” to the stream s = (st )t≥1 with high probability, i.e., the maximum absolute difference over all time steps maxt≥1 ∥yt − st ∥ is small, where s is the prefix sum stream defined element-wise by the expression Pt st := i=1 xi for all t ≥ 1. The starting point for our upper bounds is to try and reduce the edit-neighboring setting to the standard swap neighboring setting, and then apply standard continual counters. It will be useful to keep in mind that for a standard continual counter CC based on the factorization mechanism, if we have the promise that neighboring streams have ℓ1 -sensitivity sens, then with an appropriate choice of parameters we can achieve (ε, δ)-DP1 and the guarantee that with probability 1−β, maxt≥1 ∥yt −st ∥ ≤ ECC (t), where sens p ECC (t, β) := O ln t log(t/β) log(1/δ) . ε Let s′ denote the prefix-sum stream for x′ . We see that s and s′ are identical up to point i − 1, and starting from point i there is a potential mismatch. Standard private continual counters achieve privacy by adding a vector of noise values N = (Nt )t≥1 directly to the prefix sum stream element-wise, i.e., they set yt = st + Nt and yt′ = s′t + Nt . The magnitude of this noise vector scales with the ℓ1 sensitivity of the input stream under the neighboring relation. For edit-neighboring streams, starting from the point of difference t ≥ i, if the terms of x′ alternate in value (for instance an alternating sequence (0, 1, 0, 1 . . . )), then it is easy to see that the ℓ1 -sensitivity sens scales as Θ(t − i), and the standard analysis implies large error. One idea to reduce the ℓ1 -sensitivity of edit-neighboring streams is bucketing. Instead of releasing a fresh update at every time step, we only change the output value every B-many time steps, i.e., for j ∈ N we define yj·B = sj·B + Nj , and for t = j · B + k for some k ∈ {1, . . . , B − 1} we define yt = yj·B . This introduces some error since the running sum is only updated intermittently, but the magnitude of this error is bounded by the bucket size. We see that bucketing gets rid of some pathological examples, for instance setting the bucket size B = 2 ensures that the ℓ1 sensitivity of a 1 There are also continual counters for (ε, 0)-DP that leverage Laplace noise. Our focus is on δ > 0 where Gaussian noise achieves smaller asymptotic error as measured in t.
7
pair of edit-neighboring streams with the alternating 0, 1 sequence described above no longer scales with t. However, bucketing clearly does not suffice by itself in every case. For example, suppose x′ is defined by x′i = 1 for i = 2kB for integers k and x′i = 0 otherwise, i.e. that x′ has the value 1 at step i if and only if i is an even multiple of B. Then one can check that when x is an insertion neighbor of x′ at step 2B with x2B = 0, then the sequences of sums of the values in each bucket for x and x′ are (0, 1, 0,p 1, . . . ) and (0, 0, 1, 0, 1, . . . ) respectively. These are streams of length ≈ T /B, and have ℓ1 √ sensitivity T /B. One could set B to be so large as to offset the T scaling, but the choice of bucket size itself introduces a separate additive error of B − 1, because there is now a delay of B time-steps before the count is updated. In summary, the simple bucketing scheme described here still gives a polynomially scaling additive error. To address these pathological instances with large ℓ1 -sensitivity, we turn to randomizing the bucket size. For each bucket index ℓ we draw the bucket size Bℓ from a discrete Laplace distribution with mean parameter (simplified in this overview) of (1/ε) log(ℓ/δ), and scale parameter 1/ε; we denote this distribution DLap((1/ε) log(ℓ/δ), 1/ε). With this choice, we have that with probability 1 − δ, Bℓ is positive for all ℓ ∈ [1, T ], and that Pr[Bℓ = b] = eε Pr[Bℓ = b + 1] or Pr[Bℓ = b] = e−ε Pr[Bℓ = b + 1] for b ≥ 1. Further, with high probability, the maximum bucket size scales only logarithmically with the number of buckets generated, and the accuracy error introduced by this choice of distribution will grow roughly as E1 (ℓ), where for all ℓ ≥ 1, E1 (ℓ) = O( 1ε log ℓ/δ). For ease of expression, we define a sequence of checkpoints (tℓ )ℓ≥1 ∈ N∗ . Let t0 = 0 and tℓ = k=1 Bk for ℓ ≥ 1; we see that in our intermittent update scheme, tℓ are precisely the time-steps at which we change Ptℓ the output, and demarcate the ends of buckets. Let us define the bucket sum values intsumℓ = t=t xt to denote the sum of all stream values xt such that t falls in the ℓ-th bucket, ℓ−1 +1 i.e., t ∈ (tℓ−1 , tℓ ]. Since we have fixed a finite time horizon T , for any choice of checkpoints sequence (tℓ )ℓ≥1 , we implicitly set tℓ ← min{T, tℓ }, and adjust bucket lengths accordingly. Recall that x is an insertion neighbor of x′ at i, and let p denote the index of the bucket which contains i, i.e., i ∈ (tp−1 , tp ). If p = L is the last bucket index, then the ℓ1 -sensitivity of the intsum vector is 1. If p ̸= L, then we make the following high-level observation: if we couple the randomized ′ bucket sizes to be equal, with the exception of Bp+1 = Bp+1 + 1, then intsumℓ = intsum′ℓ , except for ℓ ∈ {p, p + 1}, where they differ by at most 1; intsump and intsum′p can vary because the insertion of xi changes the values of xk for k ∈ (tp−1 , tp ], and intsump+1 and intsum′p+1 can vary for the same reason as well as their unequal bucket lengths. In other words, under this coupling of bucket sizes, the shift introduced at i is largely absorbed in the buckets indexed p, p + 1 - there is some additional subtlety regarding the end of the stream, but at a high level, we get the guarantee that only a constant number of bucket sums are modified. This construction and randomized coupling reduces the problem of privatizing continual sums for edit neighbors x and x′ , to streams that are different at three entries by at most one unit, i.e. (intsumℓ )ℓ≥1 and (intsum′ℓ )ℓ≥1 , and consequently also O(1) apart in ℓ1 -distance. We can now use a standard private continual counter with sens = O(1) to generate privatized prefix sums (b vℓ )ℓ≥1 for (intsumℓ )ℓ≥1 , and consequently for x with minor error due to the lag introduced by bucketing. Then we have that for all l ∈ [L], with probability 1 − β, |b vℓ − intsumℓ | ≤ E2 (ℓ), where Pℓ
E2 (ℓ) := ECC (ℓ, β). However, there is one more remaining subtlety. The coupling-based privacy analysis above uses as privatizing randomness the obfuscation of the bucket sizes Bℓ . If we update the counter at time-steps tℓ , then an adversary can reconstruct Bℓ = tℓ −tℓ−1 , which violates the requirement that the privatizing randomness be hidden from the adversary. To deal with this, we use a biased continual counter (BCC) to generate privatized proxies b tj for tj , called noisy checkpoints; we refer to the original checkpoints as true checkpoints to avoid any ambiguity. Using CC, we construct this biased continual counter that always generates overestimates of the prefix sums of its input streams, and suffers additive error roughly twice the additive error compared to CC. Concretely, let (yt′ )t≥1 be the outputs of CC, when given inputs (xt )t≥1 . We define yt = max(yt′ + Pt Pt ECC (δ/2), k=1 xk ). Since |yt′ − k=1 xk | ≤ ECC (t, δ/2) with probability 1−δ/2 for all t ≥ 1, it follows that with probability 1 − δ/2, the sequence yt equals the values yt′ + ECC (δ/2). Since yt′ are generated 8
′ in an (ε, δ/2)-DP manner, it follows that with probability 1 − δ/2, the values Ptyt = yt + ECC (δ/2) are also (ε, δ/2)-DP, i.e. unconditionally (ε, δ)-DP. Further, by definition, yt ≥ k=1 xk . One small complication is that in principle, even though checkpoint t2 is defined after checkpoint t1 , the noisy checkpoint b t2 could occur before b t1 , or even collide with b t1 . We construct a schedule data structure schedList to keep track of when what updates are to be made, and we use any arbitrary tie-breaking rule to deal with noisy checkpoint collisions; since the tuples ((b ti , yti ))i≥1 are already privatized, as long as tie-breaking depends only on these values, no additional privacy is lost. We give BCC as input the difference sequence (tℓ − tℓ−1 )ℓ≥1 , and define its output sequence to be the noisy checkpoints b tℓ . Under the coupling of the randomized bucket sizes described above, this difference sequence also has constant ℓ1 -sensitivity, and we can show that with probability 1 − β, for all ℓ ≥ 1, |b tℓ − tℓ | ≤ E3 (ℓ) where E3 (ℓ) is the error introduced by the biased continual counter, i.e.
E3 (ℓ) = ECC (ℓ, δ/2) + ECC (ℓ, β). We can now completely describe SimECC, a mechanism for continual counting that achieves (ε, δ)-DP for edit-neighboring streams. SimECC generates randomized bucket sizes Bℓ ∼ DLap(1/ε log(ℓ/δ), 1/ε), Pℓ and defines the true checkpoints t0 = 0 and tℓ = i=1 Bi for ℓ ≥ 1. As it processes the input stream Ptℓ x, it computes internally the bucket sums intsumℓ = i=t xt , and, on reaching the end of each ℓ−1 +1 bucket Bℓ , itPfeeds intsumℓ toPa continual counter to generate the privatized value vbℓ , which is an ℓ tℓ estimate for k=1 intsumk = t=1 xt . In parallel, it feeds the difference sequence of true checkpoints to BCC which in turn generates the noisy privatized checkpoints b tℓ . Starting from the first output 0 at the first checkpoint t0 = 1, for every ℓ ≥ 1, the mechanism SimECC returns the same output as it did at tℓ−1 until reaching a noisy checkpoint b tℓ at which it updates it output value to vbℓ . The output of SimECC can be described entirely in terms of the tuples (b vℓ , b tℓ ); for any time-step t, the output of the mechanism is understood to be yj where j is the index such that b tj is the most recent noisy checkpoint that precedes t. The privacy loss of this routine can be bounded in terms of the coupling of the randomized bucket sizes needed to absorb insertions when comparing output distributions for edit neighbors, the privacy loss of the internal continual counter run on bucket sums, and the privacy loss of the biased continual counter that computes noisy checkpoints and schedules updates. The additive error can be bounded by the maximum bucket size E1 , the error of the internal continual counter E2 (ℓ, β), and the additional delay introduced by the randomized scheduling of the biased continual counter, i.e. E3 (ℓ, δ). This error expression is dominated by the error of the last term, so if we set β = δ, then with probability 1 − 3δ, for all t ≥ 1, p ∥y − s∥1 = O 1ε ln t log(t/δ) log(1/δ) . II. Sparsity-Adaptive Continual Counting via ECC The approach described above works well in the general case. We recall from the introduction that in our model, for time-steps where no data is received, we must record a ⊥ value. For the purposes of defining the target continual count value, these placeholders are identified with 0 and do not change the count, but they do increase the length of the stream and consequently the additive error. This is unnecessarily wasteful, and to address this we turn to the sparsity adaptive methods of Dwork et al. (2015). We recall that the sparsity of P a stream x at a time step t is defined to be the number of non-⊥ t values observed by t, i.e. s(x, t) = i=1 1(x ̸= ⊥). We see that at any given time-step t, the prefix sum st is always at most the sparsity s(x, t). We introduce a second mechanism, called the ECC mechanism, which incurs additive error that in the leading polylogarithmic term is only a function of st . At a high level, Dwork et al. (2015) introduce a stream partitioning mechanism that for sparse streams incurs lower additive error than the general case. The partitioning mechanism uses a sequence of sparse vector technique (SVT) instances to update the online continual count only once sufficiently many nonzero values have been seen since the previous most recent update to the count, i.e. to generate the ℓ-th checkpoint, it compares the interval sum st − stℓ−1 with some threshold τt , and generates a new partition of the stream (tℓ−1 , tℓ ] when indicated to do so by the SVT. The upshot of this approach is that with similar privacy guarantees, one can achieve additive error that scales polylogarithmically only with the sparsity, and reduces the dependence of the additive error on the stream length to an O((1/ε) log t) summand. 9
We introduce a subroutine Part that operates analogously to that of Dwork et al. (2015), although our privacy and accuracy analyses will now be significantly different. As in prior work, it operates by using a sequence of SVT instances to partition the stream. We first briefly recall the guarantee of the SVT. The SVT is a mechanism that compares a stream of values v = (vt )t≥1 with a stream of userdefined thresholds τt , and generates a stream of boolean outputs at ∈ {⊥, ⊤}. For each value, it either rejects the value vt , indicated by the output at = ⊥, or accepts it and halts, outputting at = ⊤ and not accepting any more values from the stream v. The outputs generated by the SVT have the promise that with probability 1 − β, for all t ≥ 1, at = ⊤ ⇒ vt ≥ τt − ESVT (t), and at = ⊥ ⇒ vt ≤ τt + ESVT (t), where ESVT (t) = Θ( 1ε log t/β). A remarkable property of the SVT is that it is ε-DP under the promise that any two neighboring streams v and v ′ are 1-Lipschitz at every time step. This is in contrast to the standard notion of neighboring mentioned before, where two neighboring streams could only differ at one time-step; here we have that for all t, |vt − vt′ | ≤ 1, but no other constraint. At a high level, we would like Part to define new checkpoints at time-steps t for which the SVT indicates that we have accumulated a large enough prefix sum value. When the ℓ-th instance of the SVT is running, it compares the running interval sum st − stℓ−1 with some sequence of threshold τt . To avoid generating buckets for empty streams, we require that seeing an arbitrarily long sequence of ⊥ values should not lead to a checkpoint declaration and bucket creation. This can be achieved by a simple modification of the SVT, by setting τt = τ + ESVT (t) for some τ > 1. The accuracy guarantee of the SVT now gives us that with probability 1 − β, for all t ≥ tℓ−1 , if at = ⊤, then st − stℓ−1 ≥ τ . In other words, with high probability, regardless of the number of values seen, a bucket is only generated when the increase in the prefix sum exceeds τ . Analyzing the privacy loss incurred by Part for edit-neighboring streams turns out to be a challenging task, primarily due to the fact that our bucketing is now data-dependent, and the coupling used before for SimECC no longer applies. To address this challenge, we first establish a simple but useful novel observation about the SVT in this problem context. If, in addition to the promise of 1-sensitivity along every time-step, one has the promise that the values being tested are 1-sensitive when compared across consecutive time-steps (i.e. for all i ≥ 1, |vi+1 − vi′ | ≤ 1), then the event that the SVT accepts a value and halts at time step t is approximate-DP indistinguishable to the event that it accepts a value at time-step t + 1 and halts. This fact allows us to construct a new data-dependent coupling between the bucket endpoints for the runs of the partitioning mechanism on two neighboring input streams. Essentially, we are able to show that under this data-dependent coupling, one can again ensure that the bucket interval sum streams intsum and intsum′ defined by the bucket sums differ only in a constant number of elements, and are consequently close in ℓ1 distance as well. The details of the data-dependent coupling and its analysis are quite involved, and we direct the reader to Section 4.2 for a more complete description. To privatize the true checkpoints defined by this routine, we use an instance of the BCC as before. To reason about the accuracy of this method, we first note that the lengths of the streams passed to CC and BCC scale only with the number of buckets, which are now generated by the partitioning mechanism Part. We would like to show that the number of buckets declared by the partitioning mechanism now grows only with the prefix sum st . The SVT guarantee gives us that when the ℓ-th instance of the SVT returns at = ⊤, then st − stℓ−1 ≥ τ . Summing over all checkpoints up to time-step t, it follows that st ≥ ℓ · τ . It will follow that for a choice of τ ≥ 1, the number of checkpoints ℓ generated by time-step t is at most st . Since the number of buckets generated by time-step t is at most st , it follows that the error incurred by the internal continual counter CC, and the biased continual counter BCC, now scale with st instead of t. However, our accounting for the delay in defining new buckets must now be modified, since the maximum bucket size can be arbitrarily large and does not give us a useful error bound, unlike the analysis for SimECC. We see that if the ℓ-th instance of the SVT returns at = ⊥, then we have the promise that st − stℓ−1 ≤ 2ESVT (t). Since ESVT (t) = O( 1ε log βt ), it now follows that we have the promise that st ≤ stℓ−1 + O( 1ε log βt ). Putting everything together, we get the error bound O
1 ε ln st
p
log(st /δ) log(1/δ) + O( 1ε log βt ).
III. Extended Edit-Neighboring Streams
10
As mentioned in the introduction, there is another plausible definition of edit-neighboring streams that permits neighboring streams to have different lengths. Concretely, here the time-horizon is determined by the data generation process, and not by the analyst. We assume that the input stream is marked by an end of stream symbol $ which indicates to the analyst that the stream has terminated, and the mechanism may halt. Extending our discussion in the introduction on the definition of editneighboring streams, we see that if a value is inserted at some time-step i which is not followed by any ⊥ values, then the length of the stream would increase by 1 and the end of stream symbol occurs one position later. In Section D, we formally define extended edit neighbors, which captures this notion of edit neighboring. In addition to the shift phenomenon that the standard definition of edit-neighboring streams tries to capture, we must now also account for variable stream lengths. We appeal to a simple padding technique that adds a randomized number of ⊥ values drawn from a Laplace distribution with scale parameter (2/ε) (if the value is negative, we set it to 0). After this padding, we appeal to any (ε/2, δ/2) edit-neighboring continual counter for the standard setting, and achieve the guarantee that the outputs of the continual counter on the padded stream are (ε, δ)-DP with respect to this notion of extended edit neighbors. We characterize the error of this counter using two values - the excess number of values generated to obfuscate the length of the stream, and the difference between the outputs of the continual counter and the true sum value. For outputs generated by the continual counter after the end of the true stream that do not correspond to any real inputs from the stream, we define the additive error in terms of the true count at the end of the stream. Our main finding is that the additive error is identical to that incurred for the fixed time-horizon notion of edit-neighboring continual counters standard setting up to constant factors. IV. Lower bounds To discuss our lower bounds, we need to first formally define prefix-sum neighboring streams, which we do next. Definition 2.1 (Prefix-Sum Neighbors). For T ∈ N, two sequences σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) in ZT (or a subset thereof) are said to be prefix-sum neighboring, written σ ∼p σ ′ , if one of the following conditions hold: Pt Pt • For every t ∈ [T ], i=1 xi − i=1 x′i ∈ {0, 1}. Pt Pt • For every t ∈ [T ], i=1 xi − i=1 x′i ∈ {0, −1}. We will use the notation Count(∼, S T ) to denote the problem of continual counting with neighboring relation ∼ and input streams from S T . Our lower bounds follow from the following chain of reductions: CountDistinct ⇒ Count(∼p , {−1, 0, 1}T ) Count(∼p , {−1, 0, 1}T ) ⇒ Count(∼p , {0, 1}T ) Count(∼p , {0, 1}T ) ⇒∗ Count(∼e , {0, 1, ⊥}T ) where CountDistinct denotes the problem of counting distinct elements in a turnstile stream of length T under item-level differential privacy (see Definition 7.2). In particular, the second reduction gives Theorem 1.5 and the third gives Theorem 1.2. The last reduction is starred to indicate that it only applies to a subclass of mechanisms. We proceed to sketch the ideas necessary to complete the chain of reductions. From CountDistinct to Count(∼p , {−1, 0, 1}T ). Andersson et al. (2026) gave a reduction from CountDistinct to (after translating their notation to ours) Count(∼p , ZT ). They considered a version of CountDistinct in which multiple updates (item insertions/deletion) are allowed per step, whereas we restrict the problem to one update per time step. With this restriction, we can refine their reduction down to Count(∼p , {−1, 0, 1}T ). To then prove our lower bound on Count(∼p , {−1, 0, 1}T ), we use a lower bound for CountDistinct from (Jain et al., 2023a, Theorem 1.7). Their version of CountDistinct has a subtly different neighboring relation, which implies that 1-neighboring outputs for them can be up to 2-neighboring for us. Nevertheless, by group privacy, any (ε, δ)-DP algorithm M for us is also a (2ε, (1 + eε )δ)-DP algorithm for them. Hence, their lower bound can be used in a black-box manner at only a constant cost in the privacy parameters. This gives us a lower bound on Count(∼p , {−1, 0, 1}T ). 11
From Count(∼p , {−1, 0, 1}T ) to Count(∼p , {0, 1}T ). To extend our lower bound from ternary to binary inputs, we use a natural idea: encode tritstreams x ∈ {−1, 0, 1}T into bitstreams s ∈ {0, 1}n . There are a few constraints on s in order for it to be a useful encoding for our lower bound: (1) prefix sums on s need to encode prefix sums on x, (2) s has to be constructible in an online manner, (3) n = O(T ), and (4) given x ∼p x′ , we need s ∼p s′ . Fortunately, a natural encoding works for our purpose. Choosing n = 2T and defining s via (0, 1), if xi = 0, (s2i−1 , s2i ) = (1, 1), if xi = 1, ∀i ∈ [T ] , (0, 0), if xi = −1, Pt P2t suffices. To decode the prefix sums, note that t + i=1 xi = i=1 si . The only property that does not obviously hold is that prefix-sum neighbors are preserved (4), and we prove this via case analysis. Equipped with this encoding, the reduction is straightforward. Namely, given an input to x to Count(∼p , {−1, 0, 1}T ), produce s and feed it into a private algorithm M for Count(∼p , {0, 1}2T ). The even-index outputs of M(s) (minus an offset) are an estimate of the prefix sums on x. Hence, the lower bound extends (up to constants). From Count(∼p , {0, 1}T ) to Count(∼e , {0, 1, ⊥}T ). For this reduction, our goal is different. Given that we have already designed an algorithm for Count(∼e , {0, 1, ⊥}T ) with polylogarithmic utility (Theorem 1.3), we cannot extend the lower bound without further qualification. Hence, the lower bound we show is for a restricted class of mechanisms, namely those which are data-independent. Informally, a private mechanism M for releasing a real-valued query f on (any) input x, is dataindependent if its output M(x) is distributionally equivalent to f (x) + Z, where Z is sampled from a distribution µ, independent of x. To prove our lower bound, we reason about sensitivity sets. Simplified, for a private estimation problem P = (f, ∼) (interpretation: privately release f (x) for inputs with neighboring relation ∼), the sensitivity set of P is SP := {f (x) − f (x′ ) | x ∼ x′ }. Given two such problems, P = (f, ∼) and P ′ = (f, ∼′ ) where SP ′ ⊆ SP , we show that, for every data-independent mechanism M for P with additive error α, there exists a mechanism M′ for P ′ that attains the same error α. Hence, an unconditional lower bound for P ′ can be translated into a lower bound for any data-independent mechanism for P . Our lower bound for the class of data-independent mechanisms solving P = Count(∼e , {0, 1, ⊥}T ) proceeds by showing the corresponding sensitivity-set containment argument for P ′ = Count(∼p , {0, 1}T ).
3
Preliminaries
We make the following notational definition. Definition 3.1 (Notation). numbers respectively.
1. We use the symbols N and R to denote the natural numbers and real
2. For n ∈ N, we write [n] to denote the set {1, . . . , n}. We recall the definition of differential privacy in both the batch and continual-observation model and introduce two well-studied mechanisms used by our mechanism. Then, we formally define the problem studied in this paper. Differential Privacy in Batch Model. Let X be a family of data records. A dataset is a multiset over X . We denote the family of all multisets over X by MS(X ). A mechanism M : MS(X ) → Y is a randomized function mapping a dataset D ∈ MS(X ) to an output in Y. The notion of differential privacy is built on the concept of indistinguishability between probability distributions: Definition 3.2 ((ε, δ)-indistinguishability Dwork et al. (2006)). Let Y be a set. For ε ≥ 0 and 0 ≤ δ ≤ 1, two random variables Y, Y ′ over Y are said to be (ε, δ)-indistinguishable if for every measurable set S ⊆ Y, Pr[Y ∈ S] ≤ eε · Pr[Y ′ ∈ S] + δ,
Pr[Y ′ ∈ S] ≤ eε · Pr[Y ∈ S] + δ. 12
Differential privacy is defined with respect to a neighbor relation ∼, which is a binary relation on the dataset space MS(X ). In a common definition, two datasets are considered to be neighboring if they differ in the presence or absence of a single record. Definition 3.3 (Differential Privacy Dwork et al. (2006)). Let X be a data universe and ∼ a neighbor relation on MS(X ). For ε ≥ 0 and 0 ≤ δ ≤ 1, a mechanism M : MS(X ) → Y is said to be (ε, δ)-DP with respect to ∼ if for every pair of datasets D, D′ ∈ MS(X ) satisfying D ∼ D′ , the random variables M(D) and M(D′ ) are (ε, δ)-indistinguishable. In the special case δ = 0, we say M is ε-DP. The Gaussian mechanism is a key primitive for (ε, δ)-differential privacy. Lemma 3.4 ((Analytic) Gaussian Mechanism (Dwork and Roth, 2014; Balle and Wang, 2018)). Let X be a data universe, ∼ be a neighbor relation on MS(X ), and f : MS(X ) → Rd a function. Define the ℓ2 sensitivity of f as sensf := maxD∼D′ ∥f (D) − f (D′ )∥2 . Then, for every ε > 0, δ ∈ (0, 1), there exists a positive constant Cε,δ such that, for every dataset D ∈ MS(X ), the mechanism that outputs fp (D) + N (0, σ 2 Id×d ) for σ = Cε,δ · sensf satisfies (ε, δ)-DP. Additionally, if ε ∈ (0, 1), then 1 Cε,δ ≤ ε 2 ln(1.25/δ). Properties of Differential Privacy. privacy.
We next state some fundamental properties of differential
Lemma 3.5 (Post-processing Dwork and Roth (2014)). For ε ≥ 0 and 0 ≤ δ ≤ 1, let Y and Y ′ be two (ε, δ)-indistinguishable random variables over Y. Let f : Y → Z be a (post-processing) function. Then the random variables f (Y ) and f (Y ′ ) are also (ε, δ)-indistinguishable. Lemma 3.6 (Basic Composition Dwork and Roth (2014)). Let ε1 , ε2 ≥ 0 and 0 ≤ δ1 , δ2 ≤ 1. Let Y and Y ′ be two (ε1 , δ1 )-indistinguishable random variables over Y, and let Z and Z ′ be two (ε2 , δ2 )indistinguishable random variables over Z. Then the joint random variables (Y, Z) and (Y ′ , Z ′ ) are (ε1 + ε2 , δ1 + δ2 )-indistinguishable. Lemma 3.7 (Group Privacy). Let ε ≥ 0 and 0 ≤ δ ≤ 1. For k ∈ N, let (Y1 , Y1′ ), . . . , (Yk , Yk′ ) be pairs of random variables over the same domain Y. Suppose, for each i ∈ [k], the random variables Yi and Yi′ are (ε, δ)-indistinguishable. Then the tuples Y = (Y1 , . . . , Yk ) and Y ′ = (Y1′ , . . . , Yk′ ) are (k · ε, k · ekε · δ)-indistinguishable. Continual Observation. The mechanisms discussed so far operate in the batch model: they map a static dataset D to a single output, estimating the value of a function f on D. In the continual observation model, data arrives sequentially and the mechanism estimates the value of f on the current dataset, updating the dataset at each time step. Let X denote the data universe and Y the output space. A continual mechanism M maps a data stream σ = (x1 , x2 , . . . ) to an output sequence M(σ) = (y1 , y2 , . . . ) over time. In the batch model, neighbor relation was defined on the family of datasets MS(X ). In contrast, in the continual observation model, the neighbor relation is defined on the family of finite sequences of data, i.e., X ∗ . For instance, two sequences might be neighboring if they differ at a single step. Definition 3.8 (Differential Privacy under Continual Observation). Let X be a data universe and ∼ a neighbor relation on X ∗ . For ε ≥ 0 and 0 ≤ δ ≤ 1, a continual mechanism M is said to satisfy (ε, δ)-DP with respect to ∼ if for every T ∈ N and every σ, σ ′ ∈ X T satisfying σ ∼ σ ′ , the output sequences M(σ) and M(σ ′ ) are (ε, δ)-indistinguishable. Neighbor Relations. In this paper, we work with the following neighbor relations. Definition 3.9 (k-Step ∆-Neighboring). Let k ∈ N and ∆ > 0. For every T ∈ N, two sequences σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) in RT are said to be k-step ∆-neighbors if there exist indices i1 , . . . , ik ∈ [T ] such that: • xj = x′j for all j ∈ / {i1 , . . . , ik }, and • |xj − x′j | ≤ ∆ for all j ∈ {i1 , . . . , ik }. 13
The sequences σ and σ ′ are said to be all-step ∆-neighbors if |xj − x′j | ≤ ∆ holds for every j ∈ [T ]. Definition 3.10 (k-Shift ∆-Neighboring). Let k ∈ N, ∆ ∈ R+ , and T ∈ N \ {1, . . . , k − 1}. For two real-valued sequences σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T −k ), we say that σ is a k-shift ∆-neighbor of σ ′ if the following conditions hold: (i) |xi+k − x′i | ≤ ∆ for all i ∈ [T − k]; (ii) |xi | ≤ ∆ for all i ∈ [k]. We note that the k-shift ∆-neighbor relation is not symmetric. Definition 3.11 (Edit Neighboring). Let T ∈ N, and let σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) be two sequences in ([0, 1] ∪ {⊥})T . We say that σ is an insertion neighbor of σ ′ at step i ∈ {1, . . . , T } if the following conditions hold: • For all t < i, we have xt = x′t . • Let j be the smallest index in {i, . . . , T } such that x′j = ⊥. If no such index exists, set j = T + 1. Then, for every t ∈ {i + 1, . . . , min{j, T }}, we have xt = x′t−1 . • For all t ∈ {j + 1, . . . , T }, we have xt = x′t . We say that σ and σ ′ are edit neighbors, written σ ∼e σ ′ , if there exists i ∈ [T ] such that one of σ and σ ′ is an insertion neighbor of the other one at step i. Private Continual Counter. One of the fundamental problems in differential privacy under continual observation is private continual counting. In this problem, a mechanism P CC receives an t input xt ∈ R at each time step t ∈ N and outputs an estimate yt of the prefix sum i=1 xi . Later, when designing a continual counter that is private with respect to the edit-neighbor relation, we restrict the input domain to the bounded range [0, 1], which is necessary because the prefix sums of two editneighboring sequences could differ by the value of a single data record, and thus must be bounded in order to ensure privacy. For α : N → R≥0 , and β ∈ [0, 1], the mechanism CC is said to be (α, β)-accurate if for every T ∈ N and input sequence (x1 , . . . , xT ), its output sequence (y1 , . . . , yT ) ∈ RT satisfies # " t X xi ≤ α(t) ≥ 1 − β. Pr ∀t ∈ [T ] : yt − i=1
When important, we write αβ to emphasize that the function α has a dependency on β. Differential privacy for the continual counting problem is well-studied under the neighbor relation in Definition 3.9. We use the following result as our baseline continual counter. Lemma 3.12. For every ε > 0 and δ ∈ (0, 1), there exists a continual counting mechanism CC that is (ε, δ)-DP with respect to the 1-step 1-neighbor relation. For any β ∈ (0, 1), it is (α, β)-accurate for p αCC (ε, δ, β, t) = O(Cε,δ ln(t) ln(t/β)) where Cε,δ is the Gaussian mechanism constant from Lemma 3.4. Lemma 3.12 follows from taking any (good) continual counter for bounded streams, based on adding correlated Gaussian noise to the true counts, and using the “doubling trick” from Chan et al. (2011). We give a proof in Section A. We also require private continual counters that in addition to being accurate, (i) never underestimate the true prefix sums and (ii) produce integer outputs. The following lemma allows us to construct such a biased continual counter from a generic continual counter. Lemma 3.13. Let CC be a continual counter such that when given any fixed ε′ > 0 and δ ′ ∈ (0, 1), it is (ε′ , δ ′ )-DP with respect to the 1-step 1-neighbor relation and such that for every β ′ ∈ (0, 1), it is (α(ε′ , δ ′ , β ′ , ·), β ′ )-accurate for some arbitrary given function α(ε, δ ′ , β ′ , ·) : N → R≥0 . Then, for any given ε > 0 and δ ∈ (0, 1), there exists a biased continual counter BCC that is (ε, δ)-DP with respect to the 1-step 1-neighbor, and which satisfies the following properties: 14
1. On receiving xt , its output yt is an integer and yt ≥
Pt
i=1 xi
2. For every β ∈ (0, 1), it is (αBCC , β)-accurate for αBCC (ε, δ, β, t) = αCC (ε, δ/2, η, t) + αCC (ε, δ/2, β, t) + 1 where η = 0.5δ/(1 + eε ) ∈ (0, 1). Both Lemmas 3.12 and 3.13 are proved in Appendix A, where we also show their respective construction. Sparse Vector Technique (SVT). The sparse vector technique (SVT), introduced by Dwork et al. (2009), is a mechanism for continually checking whether elements of a stream exceed a given threshold. In this work, we use a variant of SVT, denoted by SVT and described in Algorithm 1. The mechanism SVT is initialized with a privacy parameter ε > 0 and a threshold τ ∈ R, and processes a stream of realvalued inputs x1 , x2 , . . . . At each time step t ∈ N, it privately compares the input xt with τ + 8 ln(t)/ε, and outputs either ⊤ or ⊥ to indicate whether the input exceeds this term. The mechanism halts once it outputs ⊤ for the first time. Algorithm 1 SVT function Initialize(Privacy parameter ε, threshold τ ) Z0 ← Lap(2/ε) end function function Update(xt ∈ R) Zt ← Lap(4/ε) if xt + Zt > τ + 8 ln t + ⌈ 12 ε ⌉ /ε + Z0 then Output ⊤ and halt else Output ⊥ end if end function
▷ at time step t ∈ N
Notation 3.14. For an input stream σ of length T ∈ N ∪ {0}, we denote by SVT(σ) ∈ [T + 1] the time step at which SVT outputs ⊤. If SVT never outputs ⊤, we write SVT(σ) = T + 1. In particular, for the empty sequence () of length 0, the mechanism never outputs any value including ⊤. Thus, SVT(()) = 1 with probability 1. Lemma 3.15 (Lyu et al. (2017)). Let τ ∈ R, ε ≥ 0, and ∆ > 0. The mechanism SVT described in Algorithm 1 is ∆ · ε-DP with respect to the all-step ∆-neighbor relation in Definition 3.9. Lemma 3.16. Let τ ∈ R, ε ≥ 0, ∆ > 0, and 0 < β ≤ 1. There is an event of probability 1 − β conditioned on which, for every T ∈ N and every input sequence (x1 , . . . , xT ), the mechanism SVT described in Algorithm 1 satisfies the following accuracy guarantees for every t ∈ [T ]: 2 1. (Above threshold). If xt ≥ τ + 16 ln t + ⌈ 12 ε ⌉ /ε + 6 ln(2/β)/ε + 4 ln(π /6)/ε the mechanism ′ SVT returns ⊤ (and halts) at a step t ≤ t. 2. (Below threshold). If xt ≤ τ − 6 ln(2/β)/ε − 4 ln(π 2 /6)/ε the mechanism SVT returns ⊥. Proof. We see that the random variable Z0 ∼ Lap(2/ε) and the random variables Zt ∼ Lap(4/ε) i.i.d. From the tail bound of the Laplace distribution, we have that for zi ≥ 0, Pr[|Z0 | ≥ z0 ] = exp(−εz0 /2) and Pr[|Zt | ≥ zt ] = exp(−εzt /4). Setting z0 = (2/ε) ln(2/β) and zt = (4/ε) ln(2/βt ) for βt = π62 · tβ2 , we have that via a union bound, with probability 1−β, |Z0 | ≤ z0 and |Zt | ≤ zt for all t ≥ 1 simultaneously. Conditioning on this (1 − β)-probability event holding, it follows that for all t ∈ N, xt + Zt = xt ±
4 π 2 t2 ln ε 3β
and
15
τ + Z0 = τ ±
2 2 ln . ε β
We can write 4 π 2 t2 8 12 2 2 xt − ln ≥ τ + ln t + + ln ε 3β ε ε ε β 16 12 6 2 4 π2 ⇔ xt ≥ τ + ln t + + ln + ln . ε ε ε β ε 6 Similarly, xt +
4 π 2 t2 8 12 2 2 6 2 4 π2 ln ≤ τ + ln t + − ln ⇔ xt ≤ τ − ln − ln . ε 3β ε ε ε β ε β ε 6
We see that in the pseudocode of Algorithm 1, the values xt + Zt are compared with the threshold ⌉ /ε + Z0 . It follows that conditioned on the (1 − β)-probability event described above, τ + 8 ln t + ⌈ 12 ε the stated accuracy bounds hold. Probability theory. In this paper, we use the following probability facts: Fact 3.17. For every two events E1 and E2 , we have Pr[E1 ] = Pr[E1 ∧ E2 ] + Pr[E1 ∧ Ē2 ], where Ē2 denotes the complement of the event E2 . Fact 3.18. Let Z be a random variable with a measurable domain Z, and let Y be a random variable with a finite domain Y. Define supp(Y) = {y ∈ Y | Pr[Y = y] > 0}. For every measurable set S ⊆ Z, we have X Pr[Z ∈ S] = Pr[Y = y] Pr[Z ∈ S | Y = y]. y∈supp(Y)
An important probability distribution that we will use is the Laplace distribution: Definition 3.19 (Laplace Distribution). The Laplace distribution, centered at0 with scale parameter 1 exp b, is the distribution with probability density function fLap(b) (x) = 2b
−|x| b
. We denote a random
variable distributed according to this density as Y ∼ Lap(b) or simply Lap(b). Lemma 3.20. Let Y ∼ Lap(b). Then for every t ≥ 0, Pr[Y < −t · b] = Pr[Y > t · b] ≤
1 −t e . 2
We also need a discrete version of the Laplace distribution over Z (instead of R), which is defined as follows: Definition 3.21 (Discrete Laplace Distribution). Let Y denote a random variable drawn from the discrete Laplace distribution centered at 0 with scale parameter b ∈ R+ , denoted by Y ∼ DLap(b). Then for every y ∈ Z, we have e1/b − 1 −|y|/b Pr[Y = y] = 1/b ·e . e +1 Corollary 3.22. For b ∈ R+ , let Y ∼ DLap(b). The discrete Laplace distribution satisfies the following properties: 1. For every y ∈ Z, e−1/b Pr[Y = y − 1] ≤ Pr[Y = y] ≤ e1/b Pr[Y = y + 1]. 2. For every τ ∈ N, Pr[Y ≤ −τ ] = Pr[Y ≥ τ ] ≤ 16
1 −(τ −1)/b e . 2
4
Mechanism ECC
We now give a formal description of our sparsity-adaptive mechanism for private continual counting for edit neighboring streams ECC (Algorithm 2). The description of SimECC is almost identical, to avoid redundancy we relegate a formal treatment of the latter to Section 6. ECC accepts as input a stream P of values x1 , x2 , . . . drawn from [0, 1] ∪ {⊥} and, after each input xt , outputs an estimate yt of st = i≤t xi , with ⊥ identified with 0. Algorithm 2 ECC (input data stream (x1 , x2 , . . . ), privacy parameter ε, δ, black-box access to a continual counter CC and its biased variant BCC) function Initialize(Privacy parameters ε and δ) ℓ←1 t0 ← 0 y0 ← 0 intsumℓ ← 0 sched ← schedList.Initialize() 2
408 ln( π )
2δ ) Part ← Part.Initialize(ε/51, τ = 1 + ε −19ε/27 CC ← CC.Initialize(4ε/27, e δ/16) BCC ← BCC.Initialize(4ε/27, e−19ε/27 δ/8) end function function Update(xt ∈ [0, 1]) intsumℓ ← intsumℓ + xt if Part.Update(xt ) = ⊤ then tℓ ← t b tℓ ← BCC(tℓ − tℓ−1 ) vbℓ ← CC(intsumℓ ) sched.Update(b tℓ , vbℓ ) ℓ←ℓ+1 intsumℓ ← 0 end if yt = yt−1 if sched.Check(t) ̸= ⊥ then yt ← sched.Check(t) end if Output yt end function
We enumerate the internal variables used in this mechanism which we shall work with in the privacy and accuracy analyses. 1. xt ∈ [0, 1] ∪ {⊥} - the input received at time-step t. P 2. st ∈ R - the t-th prefix sum that equals i≤t xi , with xi = ⊥ treated as 0.
Definition 4.1.
3. at ∈ {⊤, ⊥} - the ℓ-th output of Part subroutine that indicates whether t should be marked as a checkpoint. 4. tℓ - the ℓ-th (true) checkpoint i.e. t = t1 , t2 , . . . are exactly the time steps at which at = ⊤. 5. b tℓ - the ℓ-th noisy checkpoints i.e. the privatized value of tℓ which is generated by BCC. Ptℓ 6. intsumℓ ∈ R - the ℓ-th interval sum, i.e., t=t xt . ℓ−1 +1 7. vbℓ - a privatized estimate of vℓ = stℓ generated by the subroutine CC. 8. sched - an instance of the schedList data structure used to store noisy checkpoint values. 9. yt ∈ R - the value returned by ECC in step t.
17
The construction of ECC can be broken down into three concurrent parts: (i) we use the stream partitioning algorithm Part of Dwork et al. (2015) to privately identify time-steps t1 , t2 , . . . called true checkpoints at which the prefix sum st = x1 +. . . xtℓ has changed significantly compared to the previous most recent checkpoint and an update is necessitated; (ii) we use a private continual counter CC that is given as input a stream of interval sums intsumℓ := xtℓ−1 +1 + · · · + xtℓ (one for each checkpoint), and generates an output vbℓ which is a privatized value of stℓ which is the true prefix sum at tℓ ; (iii) we use an auxiliary continual counter BCC to which we feed the difference sequence tℓ − tℓ−1 and get noisy checkpoints b tℓ , which are privatized estimates of tℓ . ECC outputs the privatized prefix sums vbℓ at the noisy checkpoints b tℓ . The continual counter CC is used in a black-box manner; we will appeal to the guarantees of the counter described in Lemma 3.12, and the continual counter BCC is a biased continual counter such as the one defined in Lemma 3.13. Concretely, the mechanism functions as follows. Upon initialization, it does the following: 1. It initializes three subroutines in turn; Part, CC, and BCC. 2. It defines an initial true checkpoint t0 := 0. 3. It defines the counter ℓ (equaling 1 at initialization) which keeps track of the index of the next checkpoint to be declared. 4. It initializes the first interval sum intsum1 to 0. 5. It initializes a schedule list, implemented here as an instance sched of the schedList data structure (a dynamically allocated array of lists, empty at initialization) which will store for every timestep t all values vbi for which b ti = t. This data structure only receives values that are generated by differentially private mechanisms and is hence just a post-processing step with regard to the privacy analysis. 6. It defines y0 = 0, the output value at the virtual time-step t0 that simply defines the default value of the sum in the absence of any input. When an input xt is received (i.e. the Update(xt ) subroutine of ECC is called), the mechanism passes xt to Part, receiving as output a boolean value at ∈ {⊤, ⊥}. If at = ⊥ then it proceeds to check the schedule list to see what the output ought to be (this will be explained further shortly). On the other hand, if at = ⊤, then t has been identified to be the ℓ-th true checkpoint tℓ . Informally, this means that the output ought to be updated, but for reasons of privacy the update is delayed to the corresponding noisy checkpoint b tℓ . The value of b tℓ is generated by BCC, which is given as anPupdate ℓ the checkpoint-difference dℓ = tℓ − tℓ−1 , and in turn outputs the privatized estimate of tℓ = i=1 di . Since an update cannot be scheduled for the past, BCC is constructed to have the property that it only ever outputs overestimates of the sum that it is privatizing. In other words, it is never the case that b tℓ < tℓ . Furthermore, the estimated prefix-sum vbℓ is generated by CC, which is given as an update the interval-sum intsumℓ = stℓ − stℓ−1 , and in turn outputs the privatized estimate vbℓ of Pℓ vℓ := stℓ = i=1 intsumi . An instance sched of the schedule list data structure schedList is then used to schedule this output update vbℓ for time step b tℓ by calling the sched.Update method of schedList on the inputs b tℓ and vbℓ . Finally, sched is queried to determine the output value yt for the current time-step. If sched.Check(t) returns a ⊥ value, then the current time-step was not identified as a noisy checkpoint, and we simply return the same value as the previous time-step, i.e. yt = yt−1 . On the other hand, if sched.Check(t) ̸= ⊥, then the value returned by the data structure is in fact the noisy sum value itself that was scheduled to be released, and yt = sched.Check(t). The following observation relates the inputs of the subroutines CC and BCC to the input of ECC and the checkpoints tℓ generated during runtime. Observation 4.2. Consider an execution of the mechanism ECC on the input stream σ = (x1 , . . . , xT ), and suppose that t1 , . . . , tk are the true checkpoints indicated by Part for some k ∈ [T ]. Then, by construction, the subroutine CC receives as input intsum = (intsum1 , . . . , intsumk ) where intsumℓ = Ptℓ x for ℓ ∈ [k]. Similarly, BCC receives as input d = (d1 , . . . , dk ) where dℓ = tℓ − tℓ−1 for t=tℓ−1 +1 t ℓ ∈ [k].
18
Algorithm 3 Part function Initialize(Privacy parameter ε, threshold τ ) ℓ←1 intsumℓ ← 0 SVTℓ ← SVT.Initialize(ε, τ + 16 ln(ℓ)/ε) end function function Update(xt ∈ [0, 1]) intsumℓ ← intsumℓ + xt if SVTℓ (intsum) = ⊤ then ℓ←ℓ+1 intsumℓ ← 0 SVTℓ ← SVT.Initialize(ε, τ + 16 ln(ℓ)/ε) Output ⊤ else Output ⊥ end if end function
I. Subroutine Part The mechanism Part, described in Algorithm 3, is initialized with privacy parameter ε and threshold τ . It first creates an instance of SVT, denoted SVT1 , with privacy parameter ε and threshold τ + 16 ln(1) = τ . Then it initializes a counter ℓ = 1 and an interval-sum variable intsum1 = 0. The counter ε ℓ keeps track of the number of SVT instances created so far, and its value is in fact the same as that of the counter ℓ in ECC (we avoid pointers for ease of comprehension). The variable intsumℓ stores the cumulative sum of inputs received since the current SVT instance, SVTℓ , was initialized. When this instance outputs ⊤ and terminates, the mechanism Part increments ℓ ← ℓ + 1, initializes the next SVT instance SVTℓ with privacy parameter ε and threshold τ + 16 ln(ℓ) , and sets intsumℓ ← 0. ε Upon receiving a new input xt (i.e., when ECC invokes the Update subroutine of Part), the mechanism Part proceeds as follows. First, it updates the running sum by setting intsumℓ ← intsumℓ + xt . It then feeds intsumℓ to the active instance SVTℓ , which in turn conducts a private threshold test and compares intsumℓ with τ + 16 ln(ℓ)/ε. If SVTℓ outputs ⊤ (informally, indicating that intsumℓ is larger than τ + 16 ln(ℓ)/ε), then Part increases ℓ by 1, initializes SVTℓ as described above, sets the new interval sum intsumℓ to 0, and returns ⊤ to ECC. Otherwise, if SVTℓ outputs ⊥, then Part returns ⊥. II. schedList data structure Algorithm 4 schedList data structure function Initialize sched ← a dynamically allocated array return sched end function function Update(b t, vb) sched[b t].append(b v) end function function Check(t) if sched[t] = ∅ then return ⊥ else return max{b v : vb ∈ sched[t]} end if end function schedList is a simple data structure that we use to keep track of all noisy checkpoints declared, and the respective privatized estimates of the prefix sum that ought to be released when a noisy checkpoint is reached. Thus it is a data structure that does not apply any randomization itself and simply post-processes the noisy input it is given. We implement this as a simple array of lists, indexed 19
over time-steps. When a checkpoint tℓ is reached, the privatized sum value vbℓ for tℓ is appended to the list stored at the index of the corresponding noisy checkpoint b tℓ . Further, when one checks the data structure to see if any updates have been scheduled for time step t (i.e. in other words, if t were marked as a noisy checkpoint one or more times). The data structure returns a ⊥ value if t were not marked as a checkpoint, and applies a tie-breaking rule if more than one checkpoints scheduled releases at this time-step. In principle, by the post-processing property of DP, we can use any tie-breaking rule, as long as it does not directly access the true checkpoint time-step values; in this case, we pick the maximum noisy prefix sum.
4.1
Accuracy Guarantee for ECC
In this section, we will prove the following theorem. Theorem 4.3. We condition on the event EPart defined in Lemma 4.4, and on the 1 − βC and 1 − βB events that the error bounds of CC and BCC hold. Conditioned on these events, for all t ∈ N, |st − yt | ≤ 2EBCC (st ) + ECC (st ) + O( 1ε ln(t/δ)). We recall some notation and internal variables of ECC that we will use often in our accuracy analysis. • tℓ , b tℓ : The mechanism ECC defines a sequence of true checkpoints tℓ for ℓ ≥ 1. It also generates privatized proxies for each true checkpoint, b tℓ . Pt • st , yt : The objective of the mechanism is to estimate the prefix sums st = k=1 xk for t ≥ 1. For every time-step t, it generates the output yt , and incurs error |st − yt |. Ptℓ • intsumℓ , vbℓ : The mechanism computes interval sums intsumℓ = k=t xk , which corresponds ℓ−1 +1 to the sum of all values received after checkpoint tℓ−1 , and before checkpoint tℓ . It computes vbℓ for ℓ ≥ 1, where vℓ is a privatized proxy of stℓ by passing to a continual counter CC the sequence of interval sums (intsumℓ )ℓ≥1 , and vbℓ is the ℓ-th value generated. • at : We will find it convenient to denote the output of the SVT instances by at ∈ {⊥, ⊤}. at = ⊥ indicates that t was not marked as a true checkpoint, and at = ⊤ indicates that t was marked as a checkpoint. P∞ • Given a probability β ∈ [0, 1], we let βt = π62 tβ2 . With this definition, t=1 βt = β. We now prove the accuracy guarantee of ECC. We start first by characterizing Part. More concretely, whether a time step is (at = ⊤) or isn’t (at = ⊥) marked as a true checkpoint internally by the algorithm allows us to determine, with high probability, bounds on the change in the prefix sum since the last checkpoint was declared. This also allows us to bound the total number of checkpoints declared by time step t in terms of the prefix sum value st . Lemma 4.4. For every β ∈ [0, 1], there exists an event EPart defined over the random coins of Part, such that Pr[EPart ] ≥ 1 − β, and such that conditioned on EPart , for all t ∈ N, the following statements hold: 1. If ℓ is the index of the active SVT instance at time step t then: (a) If the SVT returns ⊤, then st − stℓ−1 ≥ τ − O(ln(ℓ/β)/ε). (b) If the SVT returns ⊥, then st − stℓ−1 ≤ τ + O(ln(t + ⌈1/ε⌉)/ε) + O(ln(ℓ/β)/ε). 2. If ℓ denotes the number of checkpoints declared up to time step t, then ℓ ≤ st . Proof. Throughout this proof, let εp := ε/51 denote the privacy parameter with which ECC initializes Part (see Algorithm 2), which is also the privacy parameter passed to each internal SVT instance (see Algorithm 3). Since 408 = 8 · 51, the threshold τ passed to Part satisfies τ = 1 +
408 ln(π 2 /(2δ)) 8 ln(π 2 /(2δ)) = 1 + , ε εp 20
and the threshold of the ℓ-th SVT instance is τ (ℓ) = τ +
16 ln(ℓ) . εp
A checkpoint tℓ is declared at the time step at which the ℓ-th SVT instance first outputs ⊤. Recall P∞ β = β. By Lemma 3.16 and a union bound over ℓ ∈ N, there is an event βℓ := π6β 2 ℓ2 , so that ℓ ℓ=1 EPart of probability at least 1 − β conditioned on which the accuracy guarantee of Lemma 3.16 holds simultaneously for every SVT instance with its respective failure probability βℓ ; we condition on EPart for the remainder of the proof. 1. Applying Lemma 3.16 to the ℓ-th SVT instance (privacy parameter εp , threshold τ (ℓ), failure probability βℓ ), we obtain that for every t ≥ tℓ−1 + 1: 2
/6) ℓ) − 4 ln(π , then the SVT returns ⊥; (a′ ) if st − stℓ−1 ≤ τ (ℓ) − 6 ln(2/β εp εp 2
/6) ℓ) + 6 ln(2/β + 4 ln(π , then the SVT returns ⊤. (b′ ) if st − stℓ−1 ≥ τ (ℓ) + 16 ln(t+⌈12/ε⌉) εp εp εp
Substituting ln(2/βℓ ) = ln(π 2 /3) + 2 ln(ℓ) + ln(1/β) = O(ln(ℓ/β)) and taking contrapositives yields the two stated bounds (absorbing 16 ln(ℓ)/εp from τ (ℓ) into the O(ln(ℓ/β)/ε) error term). 2. For ease of exposition, we define Ck := and
6 ln(2/βk ) 4 ln(π 2 /6) + εp εp
κ := 6 ln(π 2 /3) + 4 ln(π 2 /6).
For each k ∈ [ℓ], the k-th SVT instance returned ⊤ at tk , so the contrapositive of (a′ ) gives stk − stk−1 > τ (k) − Ck . Since the inputs lie in [0, 1] ∪ {⊥} (with ⊥ treated as 0), st is non-decreasing in t, and hence st ≥ stℓ =
ℓ X
(stk − stk−1 ) >
k=1
ℓ X
τ (k) − Ck .
(1)
k=1
It therefore suffices to show that τ (k) − Ck ≥ 1 for every k ≥ 1; summing over k ∈ [ℓ] then gives st > ℓ. Expanding using ln(2/βk ) = ln(π 2 /3) + 2 ln(k) + ln(1/β), τ (k) − Ck = 1 + = 1+
8 ln(π 2 /(2δ)) 16 ln(k) 12 ln(k) + 6 ln(1/β) + κ + − εp εp εp 8 ln(π 2 /(2δ)) − 6 ln(1/β) − κ 4 ln(k) + . εp εp
Since δ ≤ β, we have ln(1/δ) ≥ ln(1/β), so 8 ln(π 2 /(2δ)) − 6 ln(1/β) = 8 ln(π 2 /2) + 8 ln(1/δ) − 6 ln(1/β) ≥ 8 ln(π 2 /2) + 2 ln(1/β) ≥ 8 ln(π 2 /2). Numerically, 8 ln(π 2 /2) > 12 and κ < 10, so 8 ln(π 2 /(2δ)) − 6 ln(1/β) − κ > 2 > 0. Combined with ln(k) ≥ 0 for k ≥ 1, this yields τ (k) − Ck ≥ 1, as required. Substituting into (1) gives st > ℓ, completing the proof.
21
Definition 4.5. Recall that for a given choice of privacy parameters ε, δ, and failure probability β, the continual counters CC and BCC are (αCC , β) and (αBCC , β)-accurate respectively for αCC and αBCC as defined in Lemma 3.12 and Lemma 3.13. Let βC denote the error probability of CC, and βB denote the error probability of BCC; let (εC , δC ) and (εB , δB ) denote the privacy parameters of CC and BCC respectively. With this notation, we define the terms ECC and EBCC as follows: ECC (i) = αCC (εC , δC , βC , i) EBCC (i) = αBCC (εB , δB , βB , i). With this notation, we see that in a run of ECC, the instance of CC is ECC (i)-accurate for an input stream of length i with probability 1 − βC , and the instance of BCC is EBCC (i)-accurate, for an input stream of length i with probability 1 − βB . Lemma 4.6. We condition on the event EPart defined in Lemma 4.4, and on the 1 − βC and 1 − βB events that the error bounds of CC and BCC hold. The following statements hold: 1. For all ℓ ∈ N, b tℓ − tℓ ∈ [0, EBCC (ℓ)]. 2. For all ℓ ∈ N, |sbtℓ − vbℓ | ≤ EBCC (ℓ) + ECC (ℓ). Proof. (1): We recall that by definition b tℓ is the last output generated by BCC when given the input stream ((t1 − t0 ), (t2 − t1 ), . . . , (tℓ − tℓ−1 )). It follows from the error bound of BCC that b tℓ − t ℓ ∈ [0, EBCC (ℓ)], which is the first statement. (2): Since we are considering a stream of values drawn from [0, 1] ∪ ⊥, it follows directly from the previous part that |sbtℓ −stℓ | ≤ EBCC (ℓ). We recall that vbℓ is the output generated by CC when given the Pti input stream (intsum1 , . . . , intsumℓ ), where intsumi = j=t xj . It follows from the error bound of i−1 +1 CC that |b vℓ − stℓ | ≤ ECC (ℓ). Applying the triangle inequality, we get the second statement. We can now prove Theorem 4.3. Proof of Theorem 4.3. We want to bound |st − yt |. By the pseudocode of ECC, yt equals the value released at the most recent noisy checkpoint b t at or before t, i.e. ybt . We know that ybt = max{b v : b b b vb ∈ sched[t]}. Let ℓ be the index of the checkpoint whose value vbℓ was released at t, i.e. tℓ = b t, and when sched[b t] was accessed at b t, vbℓ was the value released. It follows then that yt = vbℓ and |sbt − yt | ≤ EBCC (ℓ) + ECC (ℓ). Using that (1) ℓ ≤ st , (2) t ≥ tℓ , (3) st is non-decreasing in t, and (4) ECC and EBCC are non-decreasing in their arguments, we can write |sbt − yt | ≤ EBCC (st ) + ECC (st ).
(2)
Let t† := t − EBCC (st ). We have the following two cases: Case 1: b t ∈ (t† , t]. Since the input values are drawn from [0, 1] ∪ {⊥}, it follows that st − sbt ≤ EBCC (st ). Applying the triangle inequality on eq. (2) and the display above, we have |st − yt | ≤ 2EBCC (st ) + ECC (st ). Case 2: b t ̸∈ (t† , t]. First, since st − st−1 ≤ 1, we can write st − st† ≤ EBCC (st ).
(3)
We claim that ∀i ∈ (b t, t† ], ai = ⊥. This is because if ai = ⊤ for some such i then by the accuracy guarantee of BCC, the corresponding noisy checkpoint bi would be greater than b t and smaller than t, which contradicts that by definition, b t is the last noisy checkpoint to occur at or before t. Let ℓ∗ denote the index of the most recent true checkpoint at or before t† . Since tℓ ≤ b t and b t ≤ t† , ∗ † † ∗ we have ℓ ≥ ℓ. First suppose b t < t . Then since ∀i ∈ (b t, t ] ai = ⊥, we have that the (ℓ + 1)-th SVT instance is running at step t† , and this instance outputs ⊥ at step t† . Applying the accuracy guarantee of Part (Lemma 4.4, part 1(b)) to this instance, 6 ln(2/βℓ∗ +1 ) 4 ln(π 2 /6) 1 st† − stℓ∗ ≤ τ (ℓ∗ + 1) + 16 ln(t+⌈1/ε⌉) + + = O ln(t/δ) , (4) εp εp εp εp 22
where we used ℓ∗ ≤ s(x, t† ) ≤ s(x, t) ≤ t (Lemma 4.4) to absorb ln((ℓ∗ + 1)/β) into ln(t/δ). Since t ℓ∗ ≤ b t and the prefix sums are non-decreasing, (5) st† − sbt ≤ st† − stℓ∗ ≤ O ε1p ln(t/δ) . Now suppose b t = t† ; in this case Equation (5) holds trivially. Applying the triangle inequality on eq. (2), eq. (5), and eq. (3), we get |st − yt | ≤ |sbt − yt | + (st† − sbt ) + |st − st† | ≤ 2EBCC (st ) + ECC (st ) + O ε1p ln(t/δ) . Since ε = Θ(εp ), the stated bound follows. We now state a simple observation that the prefix sum st is always bounded from above by the sparsity s(x, t) of the input stream. Observation 4.7 (Sparsity). Given a stream x ∈ ([0, 1] ∪ ⊥)∗ , recall that s(x, t) denotes the sparsity of x until time t, and is defined by the following expression: s(x, t) :=
t X
1(xi ̸= ⊥).
i=1
Pt Since st = i=1 xi , and xi ≤ 1 (recall that ⊥ is identified with 0 for the purposes of defining st ), we have that st ≤ s(x, t).
4.2
Privacy Analysis for ECC
In this section, we will prove the following privacy guarantee for the mechanism ECC: Theorem 4.8. Let ε > 0 and 0 < δ ≤ 1. Suppose there exists a continual counting mechanism CC that is (4ε/27, e−19ε/27 δ/16)-DP with respect to the 1-step 1-neighbor relation, defined in Definition 3.9. Let BCC denote the biased version of CC as constructed in Lemma 3.13. Then, using CC and BCC as black boxes, the continual mechanism ECC, described in Algorithm 2, is (ε, δ)-DP with respect to the edit neighbor relation, defined in Definition 3.11. Recall that the mechanism ECC uses the partitioning mechanism Part to identify checkpoints (t1 , t2 , . . . ); executes the continual counting mechanism CC on the interval sums (intsum1 , intsum2 , . . . ), where intsumℓ denotes the sum of the real-valued inputs received during the time steps {tℓ−1 +1, . . . , tℓ }, to yield the update values (b v1 , vb2 , . . . ); and runs the biased continual counting mechanism BCC on the checkpoint-differences (t1 −0, t2 −t1 , . . . ) to compute noisy checkpoints (b t1 , b t2 , . . . ). We observe that the full output stream of ECC is a deterministic post-processing of the paired sequence (b v1 , b t1 ), (b v2 , b t2 ), . . . generated by CC and BCC: Observation 4.9. For T ∈ N, suppose the mechanism ECC is executed for T time steps. Then there exists a deterministic post-processing function Post that maps the output sequences of the subroutines CC and BCC during this execution to the output stream of ECC. Proof. For k ∈ [T ], let (b v1 , . . . , vbk ) and (b t1 , . . . , b tk ) denote the output sequences produced by the subroutines CC and BCC, respectively, during the execution of ECC for T steps. We define the function Post to map these sequences to a sequence (y1 , . . . , yT ) as follows: Initialize an empty schedule list L ← schedList.Initialize. For each ℓ ∈ [k], update the schedule list by executing L.Update(b tℓ , vbℓ ). Set y0 = 0. Then, for each t ∈ [T ], recursively define ( yt−1 , if L.Check(t) = ⊥, yt = L.Check(t), otherwise. Comparing this procedure with the definition of ECC in Algorithm 2, we see that (y1 , . . . , yT ) is exactly the output stream produced by ECC when its subroutines CC and BCC generate the sequences (b v1 , . . . , vbk ) and (b t1 , . . . , b tk ), respectively. 23
Ideally, for any two edit-neighboring input streams, we would like the induced input streams of both CC and BCC to be 1-step 1-neighbors. If this held deterministically, then the privacy guarantees of ECC would follow from basic composition together with the post-processing lemma. However, this property cannot be guaranteed deterministically since the checkpoints produced by Part and consequently the inputs of CC and BCC are random. To resolve this issue, we carefully design a coupling. Fix any pair of edit-neighboring input streams σ and σ ′ of the same length T ∈ N. We define an injective mapping fσ→σ′ that, roughly speaking, maps any feasible sequence of checkpoints (t1 , . . . , tk ) to a corresponding checkpoint sequence (t′1 , . . . , t′k ) such that the following two conditions are satisfied: • Property (I). When ECC is executed on σ and Part indicates (t1 , . . . , tk ) as checkpoints, the resulting input stream to CC (and BCC) is 1-step 1-neighbor to the corresponding input stream obtained when ECC is executed on σ ′ and Part indicates (t′1 , . . . , t′k ) as checkpoints. • Property (II). The probability that Part indicates (t1 , . . . , tk ) as checkpoints on the input stream σ is “close” to the probability that it indicates (t′1 , . . . , t′k ) as checkpoints on σ ′ . These two properties, together with the fact that CC and BCC are private mechanisms, allow us to show that, for any measurable set Y, the probability that the output sequence of ECC on input σ lies in Y and the subroutine Part identifies (t1 , . . . , tk ) as checkpoints on input σ is close to the corresponding probability for σ ′ and the mapped checkpoints (t′1 , . . . , t′k ). We then sum over all feasible checkpoint sequences and use the fact that fσ→σ′ is injective to conclude the desired privacy guarantee for ECC, as stated in Theorem 4.8. Next, we will define the function fσ→σ′ and prove the above properties as intermediate lemmas. The function fσ→σ′ is intended to be a bijection on the space of all valid checkpoint sequences. However, to guarantee that fσ→σ′ always outputs a valid checkpoint sequence—namely, a strictly increasing sequence of positive integers—we exclude a small subset of pathological sequences from its domain. These excluded cases are handled later separately by directly bounding their probability of occurrence under Part. Recall that two streams σ and σ ′ are edit-neighboring if one of them is an insertion neighbor of the other one at some time step. In the definition of fσ→σ′ , we distinguish between the case where σ is an insertion neighbor of σ ′ and where σ ′ is an insertion neighbor of σ. This asymmetry is essential to satisfy the neighborhood guarantees required in Property (I). Definition 4.10 (Function fσ→σ′ ). Let T ∈ N and define t0 = 0. Let CT = {(t1 , . . . , tk ) | k ∈ [T ], t1 , . . . , tk ∈ N, 0 < t1 < · · · < tk ≤ T } denote the set of all checkpoint sequences, and let CT+ = {(t1 , . . . , tk ) ∈ CT | ti − ti−1 ≥ 2 for all i ∈ [k]} denote the subset of checkpoint sequences whose consecutive gaps are at least 2. Let σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) be two edit-neighboring sequences in ([0, 1] ∪ {⊥})T , meaning that one of them is an insertion neighbor of the other one at some step i ∈ [T ]. We define a function fσ→σ′ : CT+ → CT as follows: • Suppose that σ is an insertion neighbor of σ ′ at step i. Let j be the smallest index in {i, . . . , T } such that x′j = ⊥, and set j = T + 1 if no such index exists. For every (t1 , . . . , tk ) ∈ CT+ and tk+1 = T + 1, let p ∈ [k + 1] be the index satisfying tp−1 < i ≤ tp , and let q ∈ [k + 1] be the index satisfying tq−1 < j ≤ tq . Define fσ→σ′ (t1 , . . . , tk ) as (t1 , . . . , tp , tp+1 − 1, . . . , tq−2 − 1, tq−1 , . . . , tk ), if p < q − 2 (t , . . . , t ), 1 k
o.w.
• Otherwise, suppose that σ ′ is an insertion neighbor of σ at step i. Let j be the smallest index in {i, . . . , T } such that xj = ⊥, and set j = T + 1 if no such index exists. For every (t1 , . . . , tk ) ∈ CT+ and tk+1 = T + 1, let p ∈ [k + 1] be the index satisfying tp−1 < i ≤ tp , and let q ∈ [k + 1] be the index satisfying tq−1 < j ≤ tq . Define fσ→σ′ (t1 , . . . , tk ) as (t1 , . . . , tp , tp+1 + 1, . . . , tq−2 + 1, tq−1 , . . . , tk ), if p < q − 2, (t , . . . , t ), 1 k
o.w. 24
Observation 4.11. Let σ and σ ′ be two edit-neighboring sequences of length T ∈ N. Then, the function fσ→σ′ , defined in Definition 4.10, is injective. Proof. We prove the observation for the case where σ is an insertion neighbor of σ ′ . The reverse case follows by symmetry. Suppose fσ→σ′ maps a checkpoint sequence (t1 , . . . , tk ) to (t′1 , . . . , t′k ). Let i, j ∈ [T ] be the indices in Definition 4.10, and define t′k+1 := T + 1. Let p∗ ∈ [k + 1] be the (unique) index satisfying t′p∗ −1 < i ≤ t′p∗ , and let q ∗ ∈ [k + 1] be the (unique) index satisfying t′q∗ −1 < j ≤ t′q∗ . By construction, the indices p∗ and q ∗ —defined with respect to the output sequence (t′1 , . . . , t′k )— are equal to the indices p and q from Definition 4.10—which are determined by the input sequence (t1 , . . . , tk ). Thus, the preimage (t1 , . . . , tk ) corresponding to a given (t′1 , . . . , t′k ) can be uniquely reconstructed as (t′1 , . . . , t′p∗ , t′p∗ +1 + 1, . . . , t′q∗ −2 + 1, t′q∗ −1 , . . . , t′k ), if p∗ < q ∗ − 2 (t′ , . . . , t′ ), 1
o.w.
k
Therefore, fσ→σ′ is injective. We use the following notations throughout this section: Notation 4.12. Consider an execution of the mechanism ECC on an input stream σ. Recall that ECC invokes Part on σ and sets the checkpoints to the time steps at which Part outputs ⊤. We denote by Part(σ) the resulting sequence of checkpoints. For convenience, we write t1:k := (t1 , . . . , tk ). Conditioned on the event Part(σ) = t1:k , the mechanism ECC feeds the deterministically defined interval-sum sequence intsum and checkpoint-difference sequence d defined in Observation 4.2 into the subroutines CC and BCC, respectively. For clarity, in this section, we denote these sequences by intsum(σ, t1:k )
and
d(t1:k ).
The following observation shows a slightly modified version of Property (I) for the mapping fσ→σ′ , where 1-step 1-neighboring input sequences are replaced with c-step 1-neighboring ones for some constant c ∈ N. This minor change is later handled by applying group privacy. Observation 4.13 follows from the definitions of edit-neighboring sequences (Definition 3.11) and interval-sum and checkpointdifference sequences (Observation 4.2 and Notation 4.12). The formal proof is provided in Appendix B. Observation 4.13. For T ∈ N, let σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) be two edit-neighboring T sequences in ([0, 1] ∪ {⊥}) . Let fσ→σ′ : CT+ → C be the mapping in Definition 4.10. Let t1:k ∈ CT+ , and define t′1:k = fσ→σ′ (t1:k ). Let i, j ∈ [T ] and p, q ∈ [k] be the indices associated with the definition of fσ→σ′ (t1:k ). Let the sequences intsum(σ, t1:k ) and d(t1:k ) denote the input streams of CC and BCC when ECC executes on σ and Part(σ) = t1:k , and let intsum(σ ′ , t′1:k ) and d(t′1:k ) denote the same sequences for σ ′ and t′1:k (see Observation 4.2 and Notation 4.12). Then, the following statements hold: • The sequences intsum(σ, t1:k ) and intsum(σ ′ , t′1:k ) are 4-step 1-neighbors (see Definition 3.9). • The sequences d(t1:k ) and d(t′1:k ) are 2-step 1-neighbors (see Definition 3.9). The next lemma shows Property (II) for the mapping fσ→σ′ . The proof of this lemma is technical and thus deferred to the end of this section.
25
Lemma 4.14. Let Part be the mechanism described in Algorithm 3 with privacy parameter ε > 0 and threshold parameter τ ≥ 3. Then there exists an event E such that Pr[E] ≥ 1 −
π 2 −ε(τ −1)/8 ·e , 4
and for every T ∈ N and every pair of edit-neighboring sequences σ = (x1 , . . . , xT ) and σ ′ = T (x′1 , . . . , x′T ) in ([0, 1] ∪ {⊥}) , the following statements hold: Define the sets CT and CT+ and the function fσ→σ′ as in Definition 4.10. (i) For every checkpoint sequence t1:k ∈ CT \ CT+ , Pr [Part(σ) = t1:k ∧ E] = 0. (ii) For every checkpoint sequence t1:k ∈ CT+ , Pr [Part(σ) = t1:k ∧ E] ≤ e17ε/3 Pr [Part(σ ′ ) = fσ→σ′ (t1:k )] . Proof of Theorem 4.8. We must show that for every T ∈ N and every pair of edit-neighboring input T streams σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) in ([0, 1] ∪ {⊥}) , the distributions of the output ′ ′ sequence of ECC on σ and σ , denoted by ECC(σ) and ECC(σ ), are (ε, δ)-indistinguishable. That is, for every measurable set Y ⊆ RT , Pr[ECC(σ) ∈ Y] ≤ eε Pr[ECC(σ ′ ) ∈ Y] + δ,
(6)
Pr[ECC(σ ′ ) ∈ Y] ≤ eε Pr[ECC(σ) ∈ Y] + δ.
(7)
and
Fix T , σ, σ ′ , and Y. In the rest of this proof, we will show Inequality (6) holds. Inequality (7) follows by symmetry. By construction, ECC instantiates Part with privacy parameter εP := ε/51 and threshold τ := 2
408 ln( 2π )
3δ . Since τ > 1, Lemma 4.14 is applicable. Let E be the event defined in that lemma. By 1+ ε 2 Fact 3.17 and that Pr[E] ≥ 1 − π4 · e−εP (τ −1)/8 , we have
Pr[ECC(σ) ∈ Y] = Pr[ECC(σ) ∈ Y ∧ E] + Pr[ECC(σ) ∈ Y ∧ E] ≤ Pr[ECC(σ) ∈ Y ∧ E] + Pr[E] ≤ Pr[ECC(σ) ∈ Y ∧ E] +
π 2 −εP (τ −1)/8 ·e . 4
Let CT and CT+ be as in Definition 4.10. We expand the first term in the above inequality by conditioning on all possible values for the checkpoint sequence produced by Part when the event E holds. Define F = {t1:k ∈ CT | Pr[Part(σ) = t1:k ∧ E] > 0} . Then, by Fact 3.18, we have Pr[ECC(σ) ∈ Y] ≤
X
π 2 −εP (τ −1)/8 Pr[Part(σ) = t1:k ∧ E]·Pr ECC(σ) ∈ Y | Part(σ) = t1:k ∧ E + ·e . 4
t1:k ∈F
The mechanism ECC executes Part as black box and only uses the checkpoints indicated by this subroutine, without accessing its local variables or depending on its internal randomness. Therefore, conditioned on the checkpoint sequence Part(σ) = t1:k , the output distribution of ECC is independent of whether the event E–which is about the local variables of Part–holds or not. Therefore, Pr[ECC(σ) ∈ Y] ≤
X t1:k ∈F
π 2 −εP (τ −1)/8 Pr[Part(σ) = t1:k ∧ E] · Pr ECC(σ) ∈ Y | Part(σ) = t1:k + ·e . 4 (8) 26
For t1:k ∈ F, let intsum(σ, t1:k ) and d(t1:k ) be the interval-sum sequence and checkpoint-difference sequence defined in Observation 4.2 and Notation 4.12. Conditioned on Part(σ) = t1:k , these sequences are the input streams to the subroutines CC and BCC. We denote the corresponding output sequences by CC(intsum(σ, t1:k )) and BCC(d(t1:k )). Let Post be the deterministic post-processing function defined in Observation 4.9. By that observation, knowing that intsum(σ, t1:k ) and d(t1:k ) are the input streams of CC and BCC, the output stream ECC(σ) equals Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))). Therefore, since Part(σ) = t1:k deterministically implies input streams intsum(σ, t1:k ) and d(t1:k ) for CC and BCC, we have Pr[ECC(σ) ∈ Y | Part(σ) = t1:k ] = Pr[Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))) ∈ Y]. Consequently, we can reformulate Inequality (8) as X Pr[Part(σ) = t1:k ∧ E] · Pr[Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))) ∈ Y] Pr[ECC(σ) ∈ Y] ≤ t1:k ∈F
+
π 2 −εP (τ −1)/8 ·e . 4
We now consider the execution of ECC on the neighbor input stream σ ′ . Define
(9)
F ′ = {t′1:k ∈ CT | Pr[Part(σ ′ ) = t′1:k ] > 0} . By Fact 3.17 and the same post-processing argument, we have X Pr[ECC(σ ′ ) ∈ Y] = Pr[Part(σ ′ ) = t′1:k ] · Pr[ECC(σ ′ ) ∈ Y | Part(σ ′ ) = t′1:k ] t′1:k ∈F ′
=
X
Pr[Part(σ ′ ) = t′1:k ] · Pr[Post(CC(intsum(σ ′, t′1:k )), BCC(d(t′1:k ))) ∈ Y].
(10)
t′1:k ∈F ′
By Inequality (9) and Equality (10), to show that Inequality (6) holds and to complete the proof, it suffices to prove π2 · e−εP (τ −1)/8 Pr[Part(σ) = t1:k ∧ E] · Pr[Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))) ∈ Y] + 4 t1:k ∈F X ≤ eε Pr[Part(σ ′ ) = t′1:k ] · Pr[Post (CC(intsum(σ ′ , t′1:k )), BCC(d(t′1:k ))) ∈ Y] + δ X
t′1:k ∈F ′
(11) By definition, F only includes checkpoint sequences t1:k satisfying Pr[Part(σ) = t1:k ∧ E] > 0. By Lemma 4.14, for every t1:k ∈ CT \ CT+ , we have Pr[Part(σ) = t1:k ∧ E] = 0. Thus, F ⊆ CT+ . Let fσ→σ′ : CT+ → CT be the function defined in Definition 4.10. By Lemma 4.14, for every t1:k ∈ F, Pr[Part(σ) = t1:k ∧ E] ≤ e17εP /3 Pr[Part(σ ′ ) = fσ→σ′ (t1:k )].
(12)
By construction, the mechanism ECC sets the privacy parameters of CC to εC := 4ε/27 and δC := e−19ε/27 δ/16, and by assumption, CC is (εC , δC )-DP with respect to the 1-step 1-neighbor relation. By Observation 4.13, the sequences intsum(σ, t1:k ) and intsum(σ ′ , fσ→σ′ (t1:k )) are 4-step 1-neighbors. Thus, by Lemma 3.7, the output sequences of CC on these inputs are (4εC , 4·e4εC δC )-indistinguishable. Furthermore, the mechanism ECC sets the privacy parameters of BCC to εB := εC and δB := 2δC . By Lemma 3.13, since CC is (εC , δC )-DP with respect to the 1-step 1-neighbor relation, BCC is (εB , δB )DP with respect to the 1-step 1-neighbor relation. By Observation 4.13, the sequences d(t1:k ) and d(fσ→σ′ (t1:k )) are 2-step 1-neighbors, and thus by Lemma 3.7, the output sequences of BCC on these inputs are (2εB , 2e2εB δB )-indistinguishable. Therefore, by Lemma 3.6, the composed random variables (intsum(σ, t1:k ), d(t1:k )) and (intsum(σ ′ , fσ→σ′ (t1:k )), d(fσ→σ′ (t1:k ))) are (4εC + 2εB , 4 · e4εC δC + 2 · e2εB δB )-indistinguishable. Therefore, by Lemma 3.5, the post-processed random variables Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))) and
27
Post (CC(intsum(σ ′ , fσ→σ′ (t1:k ))), BCC(d(fσ→σ′ (t1:k )))) are also (4εC + 2εB , 4 · e4εC δC + 2 · e2εB δB )indistinguishable. Thus Pr [Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))) ∈ Y] h i ≤ e4εC +2εB Pr Post CC(intsum(σ ′ , fσ→σ′ (t1:k ))), BCC(d(fσ→σ′ (t1:k ))) ∈ Y
(13)
+ 4 · e4εC δC + 2 · e2εB δB Combining Inequalities (12) and (13), we obtain X Pr[Part(σ) = t1:k ∧ E] · Pr[Post (CC(intsum(σ, t1:k )), BCC(d(t1:k ))) ∈ Y] t1:k ∈F
X
≤
e17εP /3 Pr[Part(σ ′ ) = fσ→σ′ (t1:k )]
t1:k ∈F
h i · e4εC +2εB Pr Post CC(intsum(σ ′ , fσ→σ′ (t1:k ))), BCC(d(fσ→σ′ (t1:k ))) ∈ Y + 4 · e4εC δC + 2 · e2εB δB X = e17εP /3+4εC +2εB Pr[Part(σ ′ ) = fσ→σ′ (t1:k )] t1:k ∈F
h i · Pr Post CC(intsum(σ ′ , fσ→σ′ (t1:k ))), BCC(d(fσ→σ′ (t1:k ))) ∈ Y X 17 17 Pr[Part(σ ′ ) = fσ→σ′(t1:k )] + (4·e 3 εP /3+4εC δC + 2·e 3 εP +2εB δB )· t1:k ∈F
By the choice of εP = ε/51, εC = εB = 4ε/27, δC = e−19ε/27 δ/16, and δB = 2δC , we have 17εP /3 + 4εC + 2εB = ε and
4 · e17εP /3+4εC δC + 2 · e17εP /3+2εB δB ≤ (4 + 2 × 2) · e19ε/27 δC = δ/2.
Thus, X
h i Pr[Part(σ) = t1:k ∧ E] · Pr Post CC(intsum(σ, t1:k )), BCC(d(t1:k )) ∈ Y
t1:k ∈F
≤ eε
X
Pr[Part(σ ′ ) = fσ→σ′ (t1:k )]
t1:k ∈F
h · Pr Post CC(intsum(σ ′ , fσ→σ′ (t1:k ))), BCC(d(fσ→σ′ (t1:k ))) ∈ Y] +
δ X · Pr[Part(σ ′ ) = fσ→σ′ (t1:k )] 2 t1:k ∈F
By the definition of F , every t1:k ∈ F satisfies Pr[Part(σ) = t1:k ∧ E] > 0. By Inequality (12), this implies that Pr[Part(σ ′ ) = fσ→σ′ (t1:k )] > 0, and therefore fσ→σ′ (t1:k ) ∈ F ′ . By Observation 4.11, the function fσ→σ′ : CT+ → CT is injective. Thus, due to the positivity of every summand, we have h i X Pr[Part(σ ′ ) = fσ→σ′ (t1:k )] · Pr Post CC(intsum(σ ′ , fσ→σ′ (t1:k ))), BCC(d(fσ→σ′ (t1:k ))) ∈ Y t1:k ∈F
≤
X
h i Pr[Part(σ ′ ) = t′1:k ] · Pr Post CC(intsum(σ ′ , t′1:k )), BCC(d(t′1:k )) ∈ Y ,
t′1:k ∈F ′
and X
Pr[Part(σ ′ ) = fσ→σ′ (t1:k )] ≤
X t′1:k ∈F ′
t1:k ∈F
28
Pr[Part(σ ′ ) = t′1:k ] = 1
Combining the last three inequalities implies h i X Pr[Part(σ) = t1:k ∧ E] · Pr Post CC(intsum(σ, t1:k )), BCC(d(t1:k )) ∈ Y t1:k ∈F
≤ eε
X
t′1:k ∈F
h i δ Pr[Part(σ ′ ) = t′1:k ]·Pr Post CC(intsum(σ ′ , t′1:k )), BCC(d(t′1:k )) ∈ Y + . 2 ′
Thus, to prove Inequality (11) and finish the proof, it suffices to show π 2 −εP (τ −1)/8 δ ·e ≤ , 4 2 which is true by the choice of τ = 1 +
2
2
408 ln( π2δ ) 4 ln( π ) = 1 + εP2δ . ε
It remains to prove Lemma 4.14. The goal of this lemma is to show that for every pair of editneighboring input streams σ and σ ′ , the probabilities Pr[Part(σ) = t1:k ] and Pr[Part(σ ′ ) = t′1:k ] are close, where t1:k ∈ CT+ is a checkpoint sequence and t′1:k = fσ→σ′ (t1:k ). Recall that the mechanism Part maintains an instance of SVT and reinitializes it whenever it outputs ⊤, determining the checkpoint steps. Consider the input streams of these SVT instances from initialization until they output ⊤. The high-level idea of the proof is to couple the output sequences of Part(σ) and Part(σ ′ ) using the function fσ→σ′ in Definition 4.10 and then show that for every pair of coupled output sequences, the corresponding input streams of all SVT instances executed by Part(σ) and Part(σ ′ ) must have been identical, except for at most four instances: the input streams of two SVT instances under σ and σ ′ were all-step neighbors as in Definition 3.9, and the input streams of the other two were 1-shift neighbors as in Definition 3.10. We apply Lemma 3.15 to show that the probabilities that SVT outputs ⊤ at the end of two neighbor streams of the former type are close. We then formalize the latter notion via a new neighbor relation and show that the probabilities that SVT outputs ⊤ at the end of two such neighboring input streams are close. Then we use this result to compare Pr[Part(σ) = t1:k ] and Pr[Part(σ ′ ) = t′1:k ]. We recall that, for an input stream σ of length T ∈ N, SVT(σ) ∈ [T + 1] denotes the time step at which the mechanism outputs ⊤, with SVT(σ) = T + 1 if the mechanism never outputs ⊤. The following lemma, proved in Section 5, is required in the proof of Lemma 4.14. Lemma 4.15 (Consecutive Output Distributions). Let SVT be the mechanism described in Algorithm 1 with privacy parameter ε > 0 and threshold parameter τ > 0. Recall the random variable Z0 ∼ Lap(2/ε) from that algorithm, and let Y ∼ Lap(4/ε) be an independent random variable. Define the event E ∗ := {Z0 ≥ −(τ − 1)/2} ∧ {Y ≤ (τ − 1)/2}. For t ∈ N, let σ = (x1 , . . . , xt+1 ) and σ ′ = (x′1 , . . . , x′t ) be two real-valued streams such that σ is a 1-shift 1-neighbor of σ ′ (see Definition 3.10). Then, (i) Pr[SVT(σ) = t + 1] ≤ e3ε/2 Pr[SVT(σ ′ ) = t], and (ii) Pr[SVT(σ ′ ) = t ∧ E ∗ ] ≤ e7ε/6 Pr[SVT(σ) = t + 1]. Proof of Lemma 4.14. Consider an execution of the mechanism Part with privacy parameter ε and threshold parameter τ . For ℓ ∈ N, the ℓ-th SVT instance (potentially) run by this mechanism has privacy parameter ε and threshold parameter τ (ℓ) := τ +
16 ln(ℓ) . ε
Recall the random variables Z0 ∼ Lap(2/ε) and Z1 ∼ Lap(4/ε) used by SVT in Algorithm 1. We denote by Z0ℓ and Z1ℓ the corresponding noise variables used by the ℓ-th (potential) instance of SVT. Let Yℓ ∼ Lap(4/ε) and define the event Eℓ := Z0ℓ ≥ −(τ (ℓ) − 1)/2 ∧ Yℓ ≤ (τ (ℓ) − 1)/2 ∧ Z1ℓ ≤ (τ (ℓ) − 1)/2.
29
Define
∞ ^
E :=
Eℓ .
ℓ=1
By Lemma 3.20, we have Pr[Z0ℓ ≥ −(τ (ℓ) − 1)/2] ≥ 1 − 21 e−ε(τ (ℓ)−1)/4 , Pr[Z1ℓ ≤ (τ (ℓ) − 1)/2] ≥ 1 − 21 e−ε(τ (ℓ)−1)/8 , and Pr[Yℓ ≤ (τ (ℓ) − 1)/2] ≥ 1 − 12 e−ε(τ (ℓ)−1)/8 . Hence, applying a union bound over all ℓ ∈ N yields Pr[E] ≥ 1 −
∞ X 3 ℓ=1 2
2
∞
· e−ε·(τ (ℓ)−1)/8 = 1 −
3 −ε(τ −1)/8 X −2 ln(ℓ) ·e e 2 ℓ=1
π −ε(τ −1)/8 =1− e , 4 P∞ 2 where we used the fact that ℓ=1 ℓ12 = π6 . By the design of Part, if an SVT instance executed by this mechanism receives its first input at time t ∈ N, then this input equals the t-th input of Part when that input is a real value, and equals 0 when the input is ⊥. Hence, if all real inputs of Part are restricted to lie in the range [0, 1], then for every ℓ ∈ N, the first input x∗ received by the ℓ-th (potential) SVT instance has magnitude at most 1. Hence, if Z0ℓ ≥ −(τ (ℓ) − 1)/2 and Z1ℓ ≤ (τ (ℓ) − 1)/2, we have x∗ + Z1ℓ ≤ 1 + (τ (ℓ) − 1)/2 ≤ τ (ℓ) − (τ (ℓ) − 1)/2 ≤ τ (ℓ) + Z0 . Therefore, if the event Eℓ holds, then the ℓ-th SVT mechanism does not output ⊤ upon receiving its first input. Fix T ∈ N and two edit neighboring sequences σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) in ([0, 1] ∪ {⊥})T . By the definition of CT+ , for every t1:k ∈ CT \ CT+ , there exists ℓ ∈ [k] such that tℓ = tℓ−1 + 1. But this implies that if Part(σ) = t1:k , then the ℓ-th SVT instance of Part must have output ⊤ upon receiving its first input, which is impossible when the event E holds. Consequently, for the input T sequence σ in ([0, 1] ∪ {⊥}) , we have Pr[Part(σ) = t1:k ∧ E] = 0, finishing the proof of part (i). To prove part (ii), fix t1:k ∈ CT+ . Let fσ→σ′ be the function defined in Definition 4.10, and define indices i, j ∈ [T ] and p, q ∈ [k] as in the definition of fσ→σ′ (t1:k ). Let t′1:k = fσ→σ′ (t1:k ). For every ℓ ∈ [k], define the sequences tℓ −tℓ−1 ′ t′ℓ −t′ℓ−1 tℓ−1 +h tℓ−1 +h X X Sℓ := xw and Sℓ′ := x′w , w=tℓ−1 +1
w=t′ℓ−1 +1
h=1
h=1
with xw = ⊥ and x′w = ⊥ treated as 0. Similarly, for the (potentially) remaining elements after index
tk , define the sequences
Sk+1 :=
tX k +h w=tk +1
!T −tk and
xw
t′k +h
′ Sk+1 :=
X
T −t′k x′w
w=t′k +1
h=1
.
h=1
By construction, Part(σ) = t1:k if and only if the following conditions hold: (a) The mechanism Part instantiates k + 1 instances of SVT. (b) For each ℓ ∈ [k], the ℓ-th instance processes the sequence Sℓ (of length tℓ − tℓ−1 ) and outputs ⊤ at its last input, i.e., SVT(Sℓ ) = tℓ − tℓ−1 . (c) The (k + 1)-st instance processes Sk+1 (of length T − tk ) and never outputs ⊤, i.e., SVT(Sk+1 ) = T − tk + 1. (Note that if tk = T , then the (k + 1)-st SVT instance is instantiated at time T but receives no inputs. In this case, Sk+1 is empty, and by Notation 3.14, we have Pr[SVT(Sk+1 ) = T − tk + 1] = 1.) 30
Recall that, by Definition 4.10, we set tk+1 := T + 1. With this notation, Sk+1 has length tk+1 − tk − 1, and condition (c) can be equivalently written as SVT(Sk+1 ) = tk+1 − tk . Therefore, Part(σ) = t1:k
⇔
SVT(Sℓ ) = tℓ − tℓ−1 for all ℓ ∈ [k + 1].
Similarly, for t′1:k ∈ CT , we have Part(σ ′ ) = t′1:k if and only if SVT(Sℓ′ ) = t′ℓ − t′ℓ−1 for all ℓ ∈ [k + 1]. Hence, the inequality of part (ii) is equivalent to "k+1 # "k+1 # ^ ^ 17ε/3 ′ ′ ′ Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ E ≤ e Pr SVT(Sℓ ) = tℓ − tℓ−1 . ℓ=1
ℓ=1
By of SVT instances, the probability term on the right-hand side equals Qk+1the independence ′ ′ ′ Pr SVT(S ) = t − t ℓ ℓ ℓ−1 . Moreover, the left-hand side is upper bounded by ℓ=1 Pr
"k+1 ^
# SVT(Sℓ ) = tℓ − tℓ−1 ∧ E = Pr
ℓ=1
≤
k+1 Y
"k+1 ^
SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ ∧
ℓ=1
∞ ^
# Eℓ
ℓ=k+1
Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ .
ℓ=1
Therefore, to prove part (ii), it suffices to show k+1 Y
k+1 Y Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ ≤ e17ε/3 Pr SVT(Sℓ′ ) = t′ℓ − t′ℓ−1 .
ℓ=1
(14)
ℓ=1
For every ℓ ∈ {1, . . . , p − 1} ∪ {p + 2, . . . , q − 2} ∪ {q + 1, . . . , k}, by Definition 4.10, tℓ − tℓ−1 = t′ℓ − t′ℓ−1 , and by Observation B.1 (1), Sℓ = Sℓ′ . Hence, Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ ≤ Pr SVT(Sℓ ) = tℓ − tℓ−1 = Pr SVT(Sℓ′ ) = t′ℓ − t′ℓ−1 . Therefore, to prove Inequality (14), it suffices to show2 Y Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ ℓ∈({p,...,q}\{p+2,...,q−2})∪{k+1}
≤ e17ε/3
Y
Pr SVT(Sℓ′ ) = t′ℓ − t′ℓ−1 .
(15)
ℓ∈({p,...,q}\{p+2,...,q−2})∪{k+1}
In the rest of this proof, we will show Inequality (15) holds. We prove this inequality for two cases: p ≤ q − 2 and p > q − 2. Case p ≥ q − 2. In this case, the set ({p, . . . , q} \ {p + 2, . . . , q − 2}) ∪ {k + 1} equals {p, k + 1} if p = q, equals {p, q, k + 1} if p = q − 1, and equals {p, p + 1, q, k + 1} if p = q − 2. In all cases, for every ℓ in this set, we have tℓ − tℓ−1 = t′ℓ − t′ℓ−1 by Definition 4.10, and the sequences Sℓ and Sℓ′ are all-step 1-neighbors by Observation B.1 (4), (5), and (6). Hence, by Lemma 3.15, Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ ≤ Pr SVT(Sℓ ) = tℓ − tℓ−1 ≤ eε Pr SVT(Sℓ′ ) = t′ℓ − t′ℓ−1 , which implies Inequality (15) as the cardinality of the set ({p, . . . , q} \ {p + 2, . . . , q − 2}) ∪ {k + 1} is at most 4. 2 In Inequality (15), we take the product over the set ({p, . . . , q} \ {p + 2, . . . , q − 2}) ∪ {k + 1} instead of the simpler set {p, p + 1, q − 1, q, k + 1} to correctly deal with border cases. The product must include the index k + 1 and the first two and last two indices in the range {p, . . . , q}, whenever they exist. For example, if p = q, then the correct index set is {p, k + 1}. However, the simpler expression {p, p + 1, q − 1, q, k + 1} would incorrectly include additional indices (such as p ± 1) that lie outside the valid range.
31
Case q > p+2. In this case, the set ({p, . . . , q}\{p+2, . . . , q−2})∪{k+1} equals {p, p+1, q−1, q, k+1}. The sequences σ and σ ′ are edit neighbors, meaning that one of them is an insertion neighbor of the other one at step i. We prove Inequality (15) separately for each case. In both cases, we apply the result of Lemma 4.15 with the following modification: For each ℓ ∈ {p + 1, q − 1}, consider an application of Lemma 4.15 to the ℓ-th SVT instance executed by Part. By definition, the event Eℓ implies the event E ∗ = Z0ℓ ≥ −(τ − 1)/2 ∧ Yℓ ≤ (τ − 1)/2 in that lemma. Consequently, the left-hand side of Lemma 4.15 (ii) does not increase if we replace E ∗ with Eℓ . Therefore, the inequality continues to hold with Eℓ in place of E ∗ . Case 1: σ is an insertion neighbor of σ ′ . In this case, by Definition 4.10, tp+1 −tp = t′p+1 −t′p +1, and by ′ Observation B.1 (2), the sequence Sp+1 is a 1-shift 1-neighbor of Sp+1 . Therefore, by Lemma 4.15 (i), Pr SVT(Sp+1 ) = tp+1 − tp ∧ Ep+1 ≤ Pr SVT(Sp+1 ) = tp+1 − tp ] ′ ≤ e3ε/2 Pr SVT(Sp+1 ) = tp+1 − tp − 1 ′ = e3ε/2 Pr SVT(Sp+1 ) = t′p+1 − t′p . Moreover, by Definition 4.10, tq−1 − tq−2 = t′q−1 − t′q−2 − 1, and by Observation B.1 (2), the sequence ′ Sq−1 is a 1-shift 1-neighbor of Sq−1 . Therefore, by Lemma 4.15 (ii), ′ Pr SVT(Sq−1 ) = tq−1 − tq−2 ∧ Eq−1 ≤ e7ε/6 Pr SVT(Sq−1 ) = tq−1 − tq−2 + 1 ′ = e7ε/6 Pr SVT(Sq−1 ) = t′q−1 − t′q−2 . Furthermore, for each ℓ ∈ {p, q, k + 1}, by Definition 4.10, tℓ − tℓ−1 = t′ℓ − t′ℓ−1 , and by Observation B.1 (4), (5), and (6), the sequences Sℓ and Sℓ′ are all-step 1-neighbors. Hence, by Lemma 3.15, Pr SVT(Sℓ ) = tℓ − tℓ−1 ∧ Eℓ ≤ Pr SVT(Sℓ ) = tℓ − tℓ−1 ≤ eε Pr SVT(Sℓ′ ) = t′ℓ − t′ℓ−1 . Combining these three inequalities implies Inequality (15). Case 2: Assume σ ′ is an insertion neighbor of σ. Then the proof is identical to the previous case with Observation B.1 (3) being used instead of Observation B.1 (2) and the arguments for p + 1 and q − 1 being swapped.
5
A key property for SVT
In this section, we will prove the following lemma. We recall that, for an input stream σ of length T ∈ N, SVT(σ) ∈ [T +1] denotes the time step at which the mechanism outputs ⊤, with SVT(σ) = T +1 if the mechanism never outputs ⊤. Lemma (Restatement of Lemma 4.15). Let SVT be the mechanism described in Algorithm 1 with privacy parameter ε > 0 and threshold parameter τ > 1. Recall the random variable Z0 ∼ Lap(2/ε) from that algorithm, and let Y ∼ Lap(4/ε) be an independent random variable. Define the event E ∗ := {Z0 ≥ −(τ − 1)/2} ∧ {Y ≤ (τ − 1)/2}. For t ∈ N, let σ = (x1 , . . . , xt+1 ) and σ ′ = (x′1 , . . . , x′t ) be two real-valued streams such that σ is a 1-shift 1-neighbor of σ ′ (see Definition 3.10). Then, (i) Pr[SVT(σ) = t + 1] ≤ e3ε/2 Pr[SVT(σ ′ ) = t], and (ii) Pr[SVT(σ ′ ) = t ∧ E ∗ ] ≤ e7ε/6 Pr[SVT(σ) = t + 1]. Proof. Recall the noise random variables Z0 ∼ Lap(2/ε) and Z1 , Z2 , · · · ∼ Lap(4/ε) used by SVT in Algorithm 1. Consider two executions of SVT on inputs σ and σ ′ . Define W := (z0 , . . . , zt+1 ) ∈ Rt+2 : SVT(σ) = t + 1 when Zi = zi for all i ∈ {0, . . . , t + 1} and
W ′ := (z0 , . . . , zt ) ∈ Rt+1 : SVT(σ ′ ) = t when Zi = zi for all i ∈ {0, . . . , t} 32
(i): By definition of W and independence of Z0 , . . . , Zt+1 , X
Pr[SVT(σ) = t + 1] =
t+1 Y
Pr[Zi = zi ],
(z0 ,...,zt+1 )∈W i=0
which can be reformulated as X
Pr[SVT(σ) = t + 1] =
Pr[Z1 = z1′ ]
z1′ ∈R
X
Pr[Z0 = z0 ] ·
(z0 ,z2 ,...,zt+1 ): (z0 ,z1′ ,z2 ,...,zt+1 )∈W
t+1 Y
Pr[Zi = zi ],
i=2
(16)
Since Z0 ∼ Lap(2/ε) and Zt+1 ∼ Lap(4/ε), the Laplace distribution satisfies 5 ε 5 Pr[Z0 = z0 ] ≤ e 3 · 2 Pr[Z0 = z0 + ], 3
and
8 ε 8 Pr[Zt+1 = zt+1 ] ≤ e 3 · 4 Pr[Zt+1 = zt+1 + ]. 3
Applying these bounds gives Pr[SVT(σ) = t + 1] ≤ e3ε/2
X
Pr[Z1 = z1′ ]
z1′ ∈R
·
X
t 5 8 Y Pr[Zi = zi ]. Pr[Z0 = z0 + ] · Pr[Zt+1 = zt+1 + ] · 3 3 i=2
(z0 ,z2 ,...,zt+1 ): (z0 ,z1′ ,z2 ,...,zt+1 )∈W
Fix z1′ ∈ R. For every i ∈ {2, . . . , t + 1}, the random variables Zi and Zi−1 are identically distributed. Thus, t X 5 8 Y Pr[Z0 = z0 + ] · Pr[Zt+1 = zt+1 + ] · Pr[Zi = zi ] 3 3 i=2 (z0 ,z2 ,...,zt+1 ): (z0 ,z1′ ,z2 ,...,zt+1 )∈W
=
X
t 5 8 Y Pr[Z0 = z0 + ] · Pr[Zt = zt+1 + ] · Pr[Zi−1 = zi ] 3 3 i=2
(17)
(z0 ,z2 ,...,zt+1 ): (z0 ,z1′ ,z2 ,...,zt+1 )∈W
=
X
8 5 Pr[(Z0 , . . . , Zt ) = (z0 + , z2 , . . . , zt , zt+1 + )]. 3 3
(z0 ,z2 ,...,zt+1 ): (z0 ,z1′ ,z2 ,...,zt+1 )∈W
We will show that 8 5 (z0 , z1′ , z2 , . . . , zt+1 ) ∈ W =⇒ (z0 + , z2 , . . . , zt , zt+1 + ) ∈ W ′ . 3 3 Assuming (18) holds and using the fact that, for fixed z1′ , the mapping 5 8 (z0 , z1′ , z2 , . . . , zt+1 ) 7→ (z0 + , z2 , . . . , zt , zt+1 + ) 3 3 is injective, we conclude that X
5 8 Pr[(Z0 , . . . , Zt ) = (z0 + , z2 , . . . , zt , zt+1 + )] 3 3
(z0 ,z2 ,...,zt+1 ): (z0 ,z1′ ,z2 ,...,zt+1 )∈W
≤
X
Pr[(Z0 , . . . , Zt ) = (z0 , . . . , zt )]
(z0 ,...,zt )∈W ′
= Pr[SVT(σ ′ ) = t]. 33
(18)
Combining this bound with (16) and (17) yields X Pr[SVT(σ) = t + 1] ≤ e3ε/2 Pr[Z1 = z1′ ] · Pr[SVT(σ ′ ) = t] = e3ε/2 Pr[SVT(σ ′ ) = t]. z1′ ∈R ′ It remains to prove that (18) holds: Let (z0 , z1 , z2 , . . . , zt+1 ) ∈ W . By definition, (a) xi + zi ≤ 12 12 τ + 8 ln i + ε /ε + z0 for all i ≤ t and (b) xt+1 + z > τ + 8 ln t + 1 + t+1 ε /ε + z0 . Using /ε + z + 1 for all i ≥ 2, and x′t + 1 + zt+1 > |xi − x′i−1 | ≤ 1, weobtain x′i−1 + zi ≤ τ + 8 ln i + 12 0 ε 12 1 τ + 8 ln t + 1 + ε /ε + z0 . It is known that ln(y + 1) − ln(y) ≤ y for every y > 0. Thus, for i ≥ 2, we have 8 8 ε 12 12 8 1 2 ≤ · ln i + − ln i − 1 + ≤ · = . 12 ε ε ε ε i−1+ ε ε 12 3 5 12 > ln t + 12 Therefore, (a’) x′i−1 + zi ≤ τ + 8 i − 1 + ε /ε + z0 + 3 . Moreover, since ln t + 1 + 12 ε ε , 8 12 ′ we have x′t +1+zt+1 > τ +8 ln t + 12 ε /ε+z0 . Consequently, (b’) xt +(zt+1 + 3 ) > τ +8 ln t + ε /ε+ 5 5 8 ′ (z0 + 3 ). Combining (a’) and (b’) shows that (z0 + 3 , z2 , . . . , zt , zt+1 + 3 ) ∈ W , finishing the proof of part (i).
(ii): Recall event E ∗ = Z0 ≥ −(τ − 1)/2 ∧ Y ≤ (τ − 1)/2. We write Pr[SVT(σ ′ ) = t ∧ E ∗ ] =
X
Pr[Y = y] ·
t Y
Pr[Zi = zi ]
i=0
y≤(τ −1)/2 z0 ≥−(τ −1)/2 (z0 ,z1 ,...,zt )∈W ′
t−1
≤ e7ε/6
X
8 Y Pr[Zi = zi ], Pr[Y = y]·Pr[Z0 = z0 +1]·Pr[Zt = zt + ]· 3 i=1
y≤(τ −1)/2 z0 ≥−(τ −1)/2 (z0 ,z1 ,...,zt )∈W ′
where the inequality uses the facts that Pr[Z0 = z0 ] ≤ eε/2 Pr[Z0 = z0 + 1] and Pr[Zt = zt ] ≤ 8 ε e 3 4 Pr[Zt = zt + 83 ]. For every i ∈ {1, . . . , t}, the random variables Zi and Zi+1 are identically distributed. By definition, Z1 and Y also have the same distribution. Therefore, Pr[SVT(σ ′ ) = t ∧ E ∗ ] X 8 ≤ e7ε/6 Pr[(Z0 , . . . , Zt+1 ) = (z0 + 1, y, z1 , . . . , zt−1 , zt + )]. 3 y≤(τ −1)/2 z0 ≥−(τ −1)/2 (z0 ,z1 ,...,zt )∈W ′
We will show that
y ≤ (τ − 1)/2, z0 ≥ −(τ − 1)/2, (z0 , z1 , . . . , zt ) ∈ W ′ 8 =⇒ (z0 + 1, y, z1 , . . . , zt−1 , zt + ) ∈ W. 3 Assuming (19) holds and using the fact that the mapping
(19)
8 (y, z0 , z1 , . . . , zt ) 7→ (z0 + 1, y, z1 , . . . , zt−1 , zt + ) 3 is injective, we obtain Pr[SVT(σ ′ ) = t ∧ E ∗ ] ≤ e7ε/6
X
Pr[(Z0 , . . . , Zt+1 ) = (z0 , . . . , zt+1 )]
(z0 ,...,zt+1 )∈W
= e7ε/6 Pr[SVT(σ) = t + 1]. It remains to prove (19) holds. Let z0 ≥ −(τ − 1)/2, y ≤ (τ − 1)/2, and (z0 , z1 , . . . , zt ) ∈ W ′ . Since σ is a 1-shift 1-neighbor of σ ′ , we have x1 ≤ 1. Thus, 12 x1 + y ≤ x1 + (τ − 1)/2 ≤ τ − (τ − 1)/2 < τ + z0 + 8 ln 1 + /ε + 1. ε 34
Moreover, as (z0 , z1 , . . . ,zt ) ∈ W ′ , we have (a) x′i + zi ≤ τ + 8 ln i + 12 ε /ε + z0 for all i ≤ t− 1 and (b) x′t + zt > τ + 8 ln t + 12 x′i | ≤ 1, we have xi+1 + zi ≤ τ + 8 ln i + 12 ε /ε + z0 . Using |xi+1 − ε /ε + z0 + 1 12 12 for all i ≤ t − 1 and xt+1 + zt > τ + 8 ln t + ε /ε + z0 − 1. We know that ln i + ε < ln i + 1 + 12 ε and, as discussed before, 12 12 2 8 ln t + 1 + − ln t + ≤ . ε ε ε 3 12 Therefore, (a’) xi+1 1 and (b’) xt+1 + zt > + zi ≤ τ5 + 8 ln i + 1 + ε /ε + (z08+ 1) for all i ≤ t − 12 . Equivalently, x +(z + ) > τ +8 ln t + 1 + /ε+z − τ +8 ln t + 1 + 12 t+1 t 0 ε 3 3 ε /ε+(z0 +1). Hence, if (Z0 , . . . , Zt+1 ) = (z0 +1, y, z1 , . . . , zt−1 , zt + 38 ), then SVT(σ) = t+1. Thus, (z0 +1, y, z1 , . . . , zt−1 , zt + 8 3 ) ∈ W , completing the proof of part (ii).
6
The SimECC mechanism
In this section, we introduce a simple partitioning subroutine, denoted by SimPart, which—unlike the partitioning subroutine Part from Section 4—does not access the private inputs of ECC. Similar to Part, the subroutine SimPart outputs either ⊤ or ⊥ upon each update call and can be used by ECC to indicate checkpoints. We then explain how to construct the simpler continual counter mechanism SimECC described in Theorem 1.3 by replacing Part in ECC with SimPart. The mechanism SimPart, described in Algorithm 5, is initialized with privacy parameter ε > 0 and step-size parameter µ ∈ N. It first draws a sample Z1 ∼ DLap(2/ε) and sets the first (future) checkpoint to t1 = max{1, µ + Z1 }. It also initializes a counter ℓ = 1, tracking the number of samples drawn so far, and a time variable t = 0. We note that since ln(1) = 0, t1 = max{1, µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ } at initialization. Upon each update call, SimPart proceeds as follows. It increments the time variable t ← t + 1, and checks whether t has reached the next checkpoint tℓ . If t < tℓ , it outputs ⊥. If t = tℓ , it increments ℓ ← ℓ + 1, draws a new sample Zℓ ∼ DLap(2/ε), sets the next checkpoint to tℓ = t + max{1, µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ }, and outputs ⊤. Note that, by construction, the current time t is always at most the next checkpoint tℓ . Notation 6.1. For T ∈ N, we denote by SimPart(T ) the sequence of time steps at which SimPart outputs ⊤ during its execution for T steps. We next show the following lemma for SimPart, which is analogous to Lemma 4.14 for the partitioning subroutine Part. Lemma 6.2. Let SimPart be the mechanism described in Algorithm 5 with privacy parameter ε > 0 and step-size parameter µ > 3. Then there exists an event E such that Pr[E] ≥ 1 −
π 2 −ε(µ−3)/2 ·e , 12
and for every T ∈ N, the following statements hold. Let CT and CT+ be as in Definition 4.10, and define CT++ = (t1 , . . . , tk ) ∈ CT+ | tℓ − tℓ−1 ≥ 3 for all ℓ ∈ [k] . Then: (i) For every checkpoint sequence t1:k ∈ CT \ CT++ , Pr [SimPart(T ) = t1:k ∧ E] = 0. (ii) For every pair of edit-neighboring sequences σ and σ ′ in ([0, 1] ∪ {⊥})T and every t1:k ∈ CT++ , Pr [SimPart(T ) = t1:k ] ≤ e2·ε Pr [SimPart(T ) = fσ→σ′ (t1:k )] , where fσ→σ′ : CT+ → CT is defined in Definition 4.10. 35
Algorithm 5 SimPart function Initialize(Privacy parameter ε > 0, mean step size µ ∈ N) t←0 ℓ←1 Z1 ∼ DLap(2/ε) tℓ ← max{1, µ + Z1 } end function function Update t←t+1 if t = tℓ then ℓ←ℓ+1 Zℓ ∼ DLap(2/ε) tℓ ← t + max{1, µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ } Output ⊤ else Output ⊥ end if end function
▷ t < tℓ
Proof. Consider an execution of SimPart with privacy parameter ε and step-size µ. For each ℓ ∈ N, let Zℓ denote the ℓ-th (potential) sample drawn by this mechanism from DLap(2/ε). Define the event E :=
∞ ^
(µ + Zℓ + ⌈4 ln(ℓ)/ε⌉ ≥ 3) .
ℓ=1
By Corollary 3.22 and a union bound, we have Pr[E] ≥ 1 − ≥1−
∞ X ℓ=1 ∞ X ℓ=1
Pr[Zℓ < −µ − ⌈4 ln(ℓ)/ε⌉ + 3] 1 ε 4 ln(ℓ) exp − µ−3+ 2 2 ε ∞
X 1 1 ε π 2 − ε (µ−3) = 1 − e− 2 (µ−3) , =1− ·e 2 2 2 ℓ 12 ℓ=1
where we used the fact that
1 π2 ℓ=1 ℓ2 = 6 .
P∞
Fix T ∈ N and consider an execution of SimPart for T steps. By construction, if the event E holds, then the gap between any two consecutive checkpoints is at least 3. Therefore, for every t1:k ∈ CT \CT++ , Pr[SimPart(T ) = t1:k ∧ E] = 0, which proves part (i). Let σ and σ ′ be two edit-neighboring sequences in ([0, 1] ∪ {⊥})T , meaning that one of these sequences is an insertion neighbor of the other one. We prove part (ii) for the case where σ is an insertion neighbor of σ ′ ; the other case follows by symmetry. Assume σ is an insertion neighbor of σ ′ at step i ∈ [T ]. Fix a checkpoint sequence t1:k ∈ CT++ , and let p, q ∈ [k +1] be the indices used in the definition of fσ→σ′ (t1:k ). If p > q −2, then fσ→σ′ (t1:k ) = t1:k ; hence, Pr[SimPart(T ) = t1:k ] = Pr[SimPart(T ) = fσ→σ′ (t1:k )]. Assume now that p ≤ q − 2. In this case, fσ→σ′ (t1:k ) = (t1 , . . . , tp , tp+1 − 1, . . . , tq−2 − 1, tq−1 , . . . , tk ). By the design of SimPart, SimPart(T ) = t1:k if and only if the following conditions hold: (a) The mechanism SimPart draws exactly k +1 samples Z1 , . . . , Zk+1 during its T steps of execution.
36
(b) Let t0 := 0. For each ℓ ∈ [k], tℓ = tℓ−1 + max{1, µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ } . (c) The last checkpoint scheduled for the future exceeds T , i.e., tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T. Therefore, Pr[SimPart(T ) = t1:k ] = Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] ·
k Y
Pr[tℓ−1 + max{1, µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ } = tℓ ] .
ℓ=1
Since t1:k ∈ CT++ , for every ℓ ∈ [k], tℓ − tℓ−1 ≥ 3 > 1. Thus, max{1, µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ } = tℓ − tℓ−1 if and only if µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ = tℓ − tℓ−1 . Therefore, Pr[SimPart(T ) = t1:k ] = Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] ·
k Y
Pr[tℓ−1 + µ + ⌈4 ln(ℓ)/ε⌉ + Zℓ = tℓ ]
ℓ=1
= Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] ·
k Y
Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉]
ℓ=1
By Corollary 3.22, for every ℓ ∈ [k], we have Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉] ≤ eε/2 Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉ + 1] , and Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉] ≤ eε/2 Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉ − 1] . Hence, Pr[SimPart(T ) = t1:k ] = Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] ×
k Y
Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉]
ℓ=1
≤ eε Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] × Pr[Zp+1 = tp+1 − tp − µ − ⌈4 ln(p + 1)/ε⌉ − 1] × Pr[Zq−1 = tq−1 − tq−2 − µ − ⌈4 ln(q − 1)/ε⌉ + 1] Y × Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉] . ℓ∈[k]\{p+1,q−1}
Since t1:k ∈ CT++ , we have (a) tℓ − tℓ−1 ≥ 3 for every ℓ ∈ {1, . . . , p} ∪ {q, . . . , k}; (b) (tp+1 − 1) − tp ≥ 2; (c) tq−1 − (tq−2 − 1) ≥ 4; and (d) (tℓ − 1) − (tℓ−1 − 1) = tℓ − tℓ−1 ≥ 3 for every ℓ{p + 2, . . . , q − 2}. Since all of these differences are strictly larger than 1, the same as above, we can drop the maximum with 1 in the following equality: Pr[SimPart(T ) = fσ→σ′ (t1:k )] = Pr[SimPart(T ) = (t1 , . . . , tp , tp+1 − 1, . . . , tq−2 − 1, tq−1 , . . . , tk )] = Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] × Pr[Zp+1 = (tp+1 − 1) − tp − µ − ⌈4 ln(p + 1)/ε⌉] × Pr[Zq−1 = tq−1 − (tq−2 − 1) − µ − ⌈4 ln(q − 1)/ε⌉] Y × Pr[Zℓ = tℓ − tℓ−1 − µ − ⌈4 ln(ℓ)/ε⌉] ℓ∈[k]\{p+1,q−1}
37
Note that since q ≤ k + 1 and the mapping fσ→σ′ leaves all checkpoints from index q − 1 onward unchanged, the final checkpoint in both sequences t1:k and fσ→σ′ (t1:k ) is tk . Consequently, the term Pr[tk + max{1, µ + ⌈4 ln(k + 1)/ε⌉ + Zk+1 } > T ] appears identically in the equality relation for Pr[SimPart(T ) = fσ→σ′ (t1:k )] and the inequality relation for Pr[SimPart(T ) = t1:k ]. Combining these two implies part (ii). SimECC. The mechanism SimECC as described before is simply an instantiation of ECC (Algorithm 2) with the Part subroutine replaced by a simplified checkpoint generating mechanism SimPart. At ini2
408 ln( π )
2δ , the mechanism ECC sets a tialization, instead of setting the threshold parameter τ = 1 + ε 2π 2 step-size parameter µ = 3 + ⌈102 ln( 3δ )/ε⌉, and instead of instantiating Part with parameters ε/51 and τ , it initializes SimPart with parameters ε/51 and µ. The update procedure remains unchanged, except that each call to Part(xt ) is replaced by a call to SimPart(), which does not access the input.
Privacy analysis for SimECC. The privacy analysis of the modified ECC is identical to that in Section 4.2, with Lemma 4.14 replaced by Lemma 6.2. Although the two lemmas slightly differ in their statements, Lemma 6.2 provides guarantees that are at least as strong as those provided by Lemma 4.14 and used in the original privacy analysis of ECC. Thus, that analysis holds for the modified ECC as well. We highlight these differences below: • Probability of the good event. Lemma 4.14 guarantees an event E with Pr[E] ≥ 1 −
π 2 −ε(τ −1)/8 e , 4
Pr[E] ≥ 1 −
π 2 −ε(µ−3)/2 e . 12
whereas Lemma 6.2 ensures
2
408 ln( π )
2
2δ For the chosen parameters τ = 1 + and µ = 3 + ⌈102 ln( 2π ε 3δ )/ε⌉, the latter bound is at least as strong as the former one (i.e., yields a smaller failure probability). Hence, the guarantee on Pr[E] in Lemma 6.2 implies the one in Lemma 4.14 and suffices for the analysis.
• Stability under neighboring inputs. Lemma 4.14 bounds Pr[Part(σ) = t1:k ∧ E] ≤ e17ε/3 Pr[Part(σ ′ ) = fσ→σ′ (t1:k )] , whereas Lemma 6.2 gives the stronger bound Pr[SimPart(T ) = t1:k ] ≤ e2ε Pr[SimPart(T ) = fσ→σ′ (t1:k )] . Since Pr[SimPart(T ) = t1:k ∧ E] ≤ Pr[SimPart(T ) = t1:k ] and 2ε ≤ 17ε/3, the guarantee of Lemma 6.2 directly implies the bound provided by Lemma 4.14 and required in the original analysis. Putting everything together, we get the following privacy guarantee. Theorem 6.3. Let ε > 0 and 0 < δ ≤ 1. Suppose there exists a continual counting mechanism CC that is (4ε/27, e−19ε/27 δ/16)-DP with respect to the 1-step 1-neighbor relation, defined in Definition 3.9. Let BCC denote the biased version of CC as constructed in Lemma 3.13. Then, using CC and BCC as black boxes, the continual mechanism SimECC, described in the text above, is (ε, δ)-DP with respect to the edit neighbor relation, defined in Definition 3.11. Accuracy analysis for SimECC. The accuracy analysis of the ECC when executed with SimPart is significantly simpler than when it is executed with Part. In Lemma 6.4 we establish that true checkpoints as defined by SimPart cannot be too far apart. Then, in Theorem 6.5, we show that it follows from the bound between the gaps between true checkpoints, and the error bound of BCC, that the next noisy checkpoint following any given time-step t cannot occur too late. In particular, this implies that the most recent update prior to t could not have been too far in the past either, and, by the 1-sensitivity of the running sum, the error at time-step t is also bounded. The caveat here is that the error does not adapt to the sparsity of the stream, as it does when we execute ECC with SimPart. 38
Lemma 6.4. Assume β ≤ 1/2, and let εp denote the privacy parameter with which SimPart is executed. There exists a (1 − β)-probability event ESimPart defined over the random coins of SimPart such that, conditioned on ESimPart , for every ℓ ∈ N, ln(ℓ/β) . tℓ − tℓ−1 ≤ µ + O εp Proof. Recall P tℓ − tℓ−1 = max{1, µ + ⌈4 ln(ℓ)/εp ⌉ + Zℓ } where Zℓ ∼ DLap(2/εp ) i.i.d. Recall βℓ := ∞ 6β/(π 2 ℓ2 ), so ℓ=1 βℓ = β and βℓ ≤ β ≤ 1/2. Define 1 2 ln ∈ N, ξℓ := 1 + εp 2βℓ where ξℓ ≥ 1 since 2βℓ ≤ 1. By Corollary 3.22 and ξℓ − 1 ≥ (2/εp ) ln(1/(2βℓ )), Pr[Zℓ ≥ ξℓ ] ≤ 21 exp(−(ξℓ − 1)εp /2) ≤ 21 · 2βℓ = βℓ . V∞ P Let ESimPart := ℓ=1 {Zℓ < ξℓ }; a union bound gives Pr[ESimPart ] ≥ 1 − ℓ βℓ = 1 − β. Condition on ESimPart , so Zℓ ≤ ξℓ − 1 (as Zℓ , ξℓ are integer-valued). Define Bℓ := µ + ⌈4 ln(ℓ)/εp ⌉ + ξℓ − 1. Since µ ≥ 3, ln ℓ ≥ 0, and ξℓ ≥ 1, we have Bℓ ≥ 3 > 1, so tℓ − tℓ−1 = max{1, µ + ⌈4 ln(ℓ)/εp ⌉ + Zℓ } ≤ Bℓ . By the definition of ξℓ , ξℓ − 1 ≤ 1 + (2/εp ) ln(1/(2βℓ )), so 2 1 4 ln ℓ + ln . Bℓ ≤ µ + 1 + εp εp 2βℓ Expanding ln(1/(2βℓ )) = 2 ln ℓ + ln(1/β) + ln(π 2 /12), it follows that Bℓ = µ + O(ln(ℓ/β)/εp ). Theorem 6.5. Consider the modified ECC using SimPart in place of Part with step-size parameter µ, and assume β ≤ 1/2 and δ ≤ β. Condition on ESimPart as defined in Lemma 6.4 and on the 1 − βC and 1 − βB events under which CC and BCC are accurate. Then for all t ∈ N, |st − yt | ≤ 2EBCC (t) + ECC (t) + µ + O 1ε ln(t/δ) . b Proof. If there is no noisy checkpoint at or before t, then yt = 0 and |st − yt | = st ≤ t. Since t < t1 , 1 t < t1 + EBCC (1) ≤ µ + EBCC (t) + O ε ln(t/δ) , using δ ≤ β and monotonicity. The stated bound follows. If there is a noisy checkpoint at or before t, then let b t denote the most recent such noisy checkpoint. Let ℓ be its index, so yt = vbℓ and by Lemma 4.6(2), monotonicity of the error terms, and ℓ ≤ tℓ ≤ t, |sbt − yt | ≤ EBCC (t) + ECC (t).
(20)
Since b tℓ+1 > t by maximality of b t, combining Lemmas 4.6(1) and 6.4 with monotonicity of EBCC and ℓ ≤ t, t−b t < b tℓ+1 − b tℓ ≤ (tℓ+1 + EBCC (ℓ + 1)) − tℓ ≤ µ + EBCC (t) + O ε1p ln(t/δ) , using δ ≤ β. By 1-sensitivity, |st − sbt | ≤ t − b t. Triangle inequality with (20) yields |st − yt | ≤ 2EBCC (t) + ECC (t) + µ + O Since εp = ε/51, the theorem statement follows.
39
1 εp ln(t/δ)
.
7
Lower bounds
In this section we will derive lower bounds for private continual counting under edit-neighboring, as well as under prefix-sum neighboring, streams. We give the latter definition (implied by the sensitivity vector set characterization in Andersson et al. (2026); we will return to this) next. Definition 7.1 (Prefix-Sum Neighbor Relation). For T ∈ N, two sequences σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) in ZT (or a subset thereof) are said to be prefix-sum neighboring, written σ ∼p σ ′ , if one of the following conditions hold: Pt Pt • For every t ∈ [T ], i=1 xi − i=1 x′i ∈ {0, 1}. Pt Pt • For every t ∈ [T ], i=1 xi − i=1 x′i ∈ {0, −1}. Intuitively, two sequences are prefix-sum neighbors iff one of the prefix sums always either equals the other one, or trails it by 1. Similarly, we will use the shorthand “∼e ” for edit-neighboring streams. Throughout this section we will also use the notation Count(∼, S T ) to denote the problem of continual counting with neighboring relation ∼ and input streams with elements S of length T . We emphasize that all lower bounds we derive are for streams of a finite length T ∈ N. This section is organized as follows: 1. First we show that Count(∼p , {−1, 0, 1}T ) requires error polynomial in T . 2. Secondly, we show that Count(∼p , {0, 1}T ) requires error polynomial in T . 3. Lastly, we show that any input-independent mechanism for Count(∼e , {0, 1, ⊥}T ) requires error polynomial in T .
7.1
A lower bound for Count(∼p , {−1, 0, 1}T )
The lower bound here is based on a reduction from the CountDistinct problem. It follows relatively straightforwardly from Jain et al. (2023a) together with Andersson et al. (2026). The only technical challenge is reconciling the subtle differences in how the two works define the problem. Our version of CountDistinct is defined next. Definition 7.2 (CountDistinct). Fix a universe U, let U± = ({+, −} × U) ∪ {⊥} and T ∈ N. Consider T . Here (+, u) is interpreted as “add item u”, (−, u) as “delete item u”, a stream σ = (x1 , . . . , xT ) ∈ U± and ⊥ as “do nothing”. We define the problem CountDistinct as the continual release problem, where, on receiving xt , we are to immediately output ) ( t t X X 1[xi = (−, u)] . 1[xi = (+, u)] > f (σ)t = u ∈ U : i=1
i=1
We say σ and σ are item-level neighboring, denoted σ ∼ σ ′ , if one can be derived from the other by replacing all updates involving one item u ∈ U by ⊥’s. ′
We make a few remarks before proceeding. Firstly, this definition of item-level neighboring is the one adopted in Andersson et al. (2026), and distinct from the one in Jain et al. (2023a), where instead two streams are item-level neighboring if we can derive one from the other by replacing any subset of updates pertaining to any one item. As remarked by Andersson et al., any two streams neighboring by the definition in Jain et al. (2023b), are at most 2-neighboring in CountDistinct. Additionally, while Andersson et al. (2026) allowed for an arbitrary number of updates per step, we restrict to at most one update per step, as in Jain et al. (2023a). We will use the following lower bound. Theorem 7.3 ((Jain et al., 2023a, Theorem 1.7 (worst-case bounds))). Let ε ∈ (0, 1/2], δ ∈ [0, 1], 1 )-accurate item-level (ε, δ)-DP mechanism for and T ∈ N be sufficiently large. Then any (α, 100 CountDistinct over T steps satisfies: n 1/3 o 1. If δ = o(ε/T ), then α = Ω̃ min Tε2/3 , T . nq o T 2. If δ = 0, then α = Ω min , T . ε 40
Proof sketch. The statement is identical to (Jain et al., 2023a, Theorem 1.7) when setting their maximum flippancy parameter w = Θ(T ), with the exception that they allow ε ∈ (0, 1]. Since any neighboring inputs in their setting are guaranteed to be 2-neighbors in ours, we have that any (ε, δ)DP mechanism M for CountDistinct is also a (2ε, 2e2ε δ)-DP for their version of the problem via group privacy. Hence, invoking their lower bound for ε′ = 2ε and δ ′ = 6δ ≥ 2e2ε δ (valid for ε ≤ 1/2), extends their lower bound to (ε, δ)-DP for CountDistinct. This restricts the range on ε accordingly. For δ, we can keep its range unchanged. If δ = o(ε/T ), then 6δ = o(2ε/T ) is implied, so the condition on δ ′ is satisfied for sufficiently large T . We have now proved the statement for ε ∈ (0, 1/2], δ ∈ [0, 1]. Counting on the difference stream. Towards proving the lower bound on Count(∼p , {−1, 0, 1}T ), by reducing from CountDistinct, we need the following concept. Let σ ∼ σ ′ be two neighboring inputs to CountDistinct, and define the two (output) difference streams d(σ) = (f (σ1 ), f (σ2 ) − f (σ1 ), . . . , f (σT ) − f (σT −1 )) , d(σ ′ ) = (f (σ1′ ), f (σ2′ ) − f (σ1′ ), . . . , f (σT′ ) − f (σT′ −1 )) . We will prove the following claim, using a result from Andersson et al. (2026). Claim 7.4. d(σ), d(σ ′ ) ∈ {−1, 0, 1}T and d(σ) ∼p d(σ ′ ). Lemma 7.5 (Andersson et al. (2026)). Let σ, σ ′ be two neighboring inputs to CountDistinct, and d(σ), d(σ ′ ) be the corresponding output difference streams. Then d(σ) − d(σ ′ ) ∈ S1 where ( S1 =
v ∈ Z : max T
i,j∈[T ]
j X
) vk ≤ 1
.
k=i
Proof of Claim 7.4. The fact that d(σ), d(σ ′ ) ∈ {−1, 0, 1}T follows from the definition of CountDistinct: at each time step, a single update to an item is made, hence the number of distinct elements from one step to the next can change by ±1, or not at all (i.e., by zero). For the neighboring relation, we will argue about the set S1 from Lemma 7.5. Note that S1 is the set of all integer vectors of length T with interval sums that are no larger than 1 in absolute value. Let v ∈ S1 . By definition, v ∈ {−1, 0, 1}T , since otherwise there would exist a k ∈ [T ] for which |vk | > 1, and so the singleton interval sum (from k to k) would exceed 1 in absolute value. Assume, towards a contradiction, that there exists i, j ∈ [T ] for which the prefix sum of v up to i and up to j assume a value of −1 and 1 respectively. Then, i X k=1
vk −
j X
max{i,j}
X
vk =
k=1
vk = 2 ,
k=min{i,j}+1
implying v ∈ / S1 , a contradiction. Hence every prefix on v lies in either {0, 1} or {−1, 0}. As d(σ) − d(σ ′ ) ∈ S1 from Lemma 7.5, we have that the difference in the prefixes on d(σ) and d(σ ′ ) satisfy the same condition. This is exactly the condition for d(σ) ∼p d(σ ′ ), and so we are done. The following theorem follows naturally by a reduction from CountDistinct. 1 )-accurate Theorem 7.6. Let ε ∈ (0, 1/2], δ ∈ [0, 1], and T ∈ N be sufficiently large. Then any (α, 100 (ε, δ)-DP mechanism for ∼p -neighboring continual counting on {−1, 0, 1} over T steps satisfies: n 1/3 o 1. If δ = o(ε/T ), then α = Ω̃ min Tε2/3 , T .
nq o T 2. If δ = 0, then α = Ω min , T . ε Proof. We prove the claim by a reduction from CountDistinct, following Jain et al. and Andersson et al.. Let CC be an (ε, δ)-DP mechanism for Count(∼p , {−1, 0, 1}T ) and suppose that CC is (α, 1/100)accurate. We construct a mechanism M for CountDistinct as follows. On input stream σ, compute the output difference stream d(σ) ∈ {−1, 0, 1}T , and output CC(d(σ)). This can be done in an online manner, as d(σ)t = f (σ)t −f (σ)t−1 . Let σ, σ ′ be neighboring inputs to CountDistinct. By Claim 7.4, we 41
have that d(σ), d(σ ′ ) ∈ {−1, 0, 1}T and that d(σ) ∼p d(σ ′ ). Hence, d(σ), d(σ ′ ) are valid, neighboring inputs to Count(∼p , {−1, 0, 1}T ). Thus, as CC is an (ε, δ)-DP mechanism for Count(∼p , {−1, 0, 1}T ), M is an (ε, δ)-DP mechanism for CountDistinct. Moreover, as prefix sums on d(σ) equals the distinct-count sequence f (σ), we have, by the (α, 1/100)-accuracy of CC, (α, 1/100)-accuracy for M for CountDistinct. Consequently, M inherits the lower bounds from Theorem 7.3, and the stated bounds on α follow.
7.2
A lower bound for Count(∼p , {0, 1}T )
Having proved a lower bound for ∼p -neighboring continual counting on {−1, 0, 1}-streams, we will next extend it to binary streams. The key idea will be to encode strings x, x′ ∈ {−1, 0, 1}T into strings s, s′ ∈ {0, 1}2T in such a way that: 1. Prefix sums on x and x′ can be derived from s and s′ respectively. 2. If x and x′ are prefix-sum neighboring, then so are s and s′ . Equipped with such an encoding, the reduction from Count(∼p , {−1, 0, 1}T ) to Count(∼p , {0, 1}T ) proceeds naturally. We give the encoding next. Subroutine TritsToBits. The procedure TritsToBits maps a sequence x ∈ {−1, 0, 1}T into a binary sequence s ∈ {0, 1}2T , where for each i ∈ [T ], (0, 1), if xi = 0, ∀i ∈ [T ]. (s2i−1 , s2i ) = (1, 1), if xi = 1, (0, 0), if xi = −1, As can be shown by a straightforward induction, by construction, for every i ∈ [T ], 2i X
i X
sj =
j=1
xj + i.
(21)
j=1
Lemma 7.7. Let x, x′ ∈ {−1, 0, 1}T be ∼p -neighboring sequences. Define s = TritsToBits(x) and s′ = TritsToBits(x′ ). Then s, s′ ∈ {0, 1}2T are ∼p -neighboring sequences. Proof. For i ∈ [T ] and k ∈ [2T ], define the prefix-differences Pi :=
i X
xt −
i X
Dk :=
x′t ,
t=1
t=1
k X
sj −
j=1
k X
s′j ,
j=1
and also set P0 = D0 := 0. Even prefixes.
By the defining property of TritsToBits, for every i ∈ [T ], 2i X
sj =
j=1
i X
xt + i
2i X
and
t=1
and hence D2i =
j=1
i X
xt + i −
t=1
i X
s′j =
i X
x′t + i,
t=1
x′t + i = Pi .
(22)
t=1
Odd prefixes. Write ai := s2i−1 and a′i := s′2i−1 . By the definition of TritsToBits, ai = 1[xi = 1] and a′i = 1[x′i = 1]. Moreover, 2i−1 X j=1
so
2(i−1)
sj = ai +
X
2i−1 X
sj ,
j=1
j=1
2(i−1)
s′j = a′i +
X
s′j ,
j=1
D2i−1 = D2(i−1) + (ai − a′i ) = Pi−1 + 1[xi = 1] − 1[x′i = 1] .
(23)
We now verify the prefix-neighbor condition for s, s′ . Since x ∼p x′ , we are in one of the following two cases. 42
Case 1: Pi ∈ {0, 1} for all i ∈ [T ]. Then by (22), D2i ∈ {0, 1} for all i. It remains to show D2i−1 ∈ {0, 1}. From (23), we have D2i−1 ∈ {−1, 0, 1, 2}, so it suffices to rule out the values −1 and 2. Suppose D2i−1 = −1 for some i. Then (23) forces Pi−1 = 0 and 1[xi = 1] − 1[x′i = 1] = −1, i.e., xi ̸= 1 and x′i = 1. Hence xi − x′i ≤ −1, and therefore Pi = Pi−1 + (xi − x′i ) ≤ 0 + (−1) = −1, contradicting Pi ∈ {0, 1}. Suppose instead that D2i−1 = 2 for some i. Then (23) forces Pi−1 = 1 and 1[xi = 1]− 1[x′i = 1] = 1, i.e., xi = 1 and x′i ̸= 1. Hence xi − x′i ≥ 1, and therefore Pi = Pi−1 + (xi − x′i ) ≥ 1 + 1 = 2, contradicting Pi ∈ {0, 1}. Thus D2i−1 ∈ / {−1, 2}, so D2i−1 ∈ {0, 1} for all i. Combined with D2i ∈ {0, 1}, this implies Dk ∈ {0, 1} for all k ∈ [2T ], i.e., s ∼p s′ . Case 2: Pi ∈ {0, −1} for all i ∈ [T ]. Then by (22), D2i ∈ {0, −1} for all i. Again it remains to show D2i−1 ∈ {0, −1}. From (23), we have D2i−1 ∈ {−2, −1, 0, 1}, so it suffices to rule out 1 and −2. If D2i−1 = 1, then (23) forces Pi−1 = 0 and 1[xi = 1] − 1[x′i = 1] = 1, so xi = 1 and x′i ̸= 1, implying xi − x′i ≥ 1 and hence Pi = Pi−1 + (xi − x′i ) ≥ 1, contradicting Pi ∈ {0, −1}. If D2i−1 = −2, then (23) forces Pi−1 = −1 and 1[xi = 1] − 1[x′i = 1] = −1, so x′i = 1 and xi ̸= 1, implying xi − x′i ≤ −1 and hence Pi = Pi−1 + (xi − x′i ) ≤ −2, contradicting Pi ∈ {0, −1}. Thus D2i−1 ∈ / {1, −2}, so D2i−1 ∈ {0, −1} for all i. Combined with D2i ∈ {0, −1}, this implies Dk ∈ {0, −1} for all k ∈ [2T ], i.e., s ∼p s′ . In both cases s ∼p s′ , proving the statement. The proof of the following lower bound is a natural reduction from Theorem 7.6. 1 Theorem 7.8. Let ε ∈ (0, 1/2], δ ∈ [0, 1], and T ∈ N be sufficiently large. Then any (α, 100 )-accurate (ε, δ)-DP mechanism for ∼p -neighboring continual counting on {0, 1} over T steps satisfies: n 1/3 o 1. If δ = o(ε/T ), then α = Ω̃ min Tε2/3 , T .
nq o T 2. If δ = 0, then α = Ω min , T . ε Proof. Assume wlog. that T is even and let n = T /2. We prove the claim by a reduction from Count(∼p , {−1, 0, 1}n ). Let CC be an (ε, δ)-DP mechanism for Count(∼p , {0, 1}T ), and suppose that CC is (α, 1/100)-accurate. Let x ∈ {−1, 0, 1}n be the input to an instance of Count(∼p , {−1, 0, 1}n ), and let s = TritsToBits(x) ∈ {0, 1}T . We define M as the mechanism performing the following routine on receiving xt : 1. Construct (s2t−1 , s2t ) from xt . 2. Feed s2t−1 followed by s2t to CC, yielding corresponding outputs a2t−1 and a2t from CC. 3. Output yt = a2t − t. Let x, x′ ∈ {−1, 0, 1}n be neighboring inputs to our problem instance, i.e., x ∼p x′ . Let s′ = TritsToBits(x′ ) ∈ {0, 1}T . By Lemma 7.7, we have that s ∼p s′ . Hence s, s′ are valid neighboring inputs to Count(∼p , {0, 1}T ). Therefore, since CC is (ε, δ)-DP for Count(∼p , {0, 1}T ), and M outputs a postprocessing of CC, M is an (ε, δ)-DP mechanism for Count(∼p , {−1, 0, 1}n ). Pt Moreover, yt = a2t − t is a noisy estimate of i=1 xi by (21). Hence, by the (α, 1/100)-accuracy of CC, we also have (α, 1/100)-accuracy for M. Consequently, M inherits the lower bounds from Theorem 7.6, where 43
n 1/3 o n 1/3 o 1. If δ = o(ε/n) = o(ε/T ), then α = Ω̃ min nε2/3 , n = Ω̃ min Tε2/3 , T . 2. If δ = 0, then α = Ω min
p n
ε,n
nq o T = Ω min . ε ,T
since n = Θ(T ). Finally, if T is odd then repeat the proof for T − 1 = Θ(T ) for the corresponding lower bound statement.
7.3
A lower bound for Count(∼e , {0, 1, ⊥}T )
Fix T ∈ N for the rest of this section. We will prove a lower bound for Count(∼e , {0, 1, ⊥}T ) for a particular class of mechanisms, namely those that are data-independent. We give a definition next in the context of continual release problems, which we first formally define. Definition 7.9 (Continual Release Problem). Let U denote an update universe, and let D denote a dataset space. Let U : D × U → D be an update operator, and fix an initial dataset D0 = ∅. For an input stream σ = (u1 , . . . , uT ) ∈ U T , define the induced datasets (Dt (σ))Tt=0 recursively by Dt (σ) := U (Dt−1 (σ), ut )
for t ∈ [T ].
Let f : D → R be a real-valued function (a query). We define the induced continual query f : U T → RT (with a slight abuse of notation) by f (σ) := (f (D1 (σ)), . . . , f (DT (σ))) . Let ∼ be a neighboring relation over input streams in U T . We call P = (f, ∼) a continual release problem. A randomized mechanism M is (ε, δ)-DP for P if it satisfies (ε, δ)-DP, under continual observation, with respect to the neighboring relation ∼ on U T for the mapping σ 7→ M(σ) ∈ RT . For convenience, when discussing a continual release problem P = (f, ∼), we assume the corresponding surrounding notation (e.g., input streams are denoted by σ). We next formalize what it means to be data-independent for such problems. Definition 7.10 (Data-Independent Mechanism). Let P = (f, ∼) be a continual release problem. Let M(σ) denote the vector of outputs produced by M on input stream σ to P . We say that M is a data-independent mechanism, if there exists a distribution µ on RT , such that, for any input stream σ of length T , d M(σ) = f (σ) + Z, where Z is drawn from µ, and the law of Z is independent of σ. Intuitively, a data-independent mechanism is distributionally equivalent to a mechanism that adds input-independent, possibly correlated across time steps, noise to the true function values. Notably, it includes all mechanisms based on matrix-factorization techniques (Li et al., 2015; Edmonds et al., 2020). We remark that the notion of data-independent mechanism, together with related ideas in this section, appear in the literature on differentially private linear queries, see e.g., (Hardt and Talwar, 2010; Li et al., 2015; Bhaskara et al., 2012; Edmonds et al., 2020; Awan and Slavković, 2021; Nikolov et al., 2013) and references therein. These works primarily deal with ℓ1 neighboring inputs, and not the more elaborate neighboring relations we do. Nonetheless, our key lemma in this section (Lemma 7.12) follows from basic properties of data-independent mechanism and sensitivity sets (sometimes also referred to as a sensitivity polytope, when appropriate). We define this last notion next. Definition 7.11 (Sensitivity Set). Let P = (f, ∼) be a continual release problem. The sensitivity set of P is defined as SP := { f (σ) − f (σ ′ ) | σ ∼ σ ′ }. Rather than constructing a full reduction, as we did previously, we will prove a lower bound based on sensitivity-set containment. More precisely, we show that if the sensitivity set of P ′ = (f ′ , ∼′ ) is contained in the sensitivity set of P = (f, ∼), then for every data-independent mechanism for P with additive error α, there exists a mechanism for P ′ with the same error α. Hence, we are able to 44
lift a lower bound from P ′ to any data-independent mechanism for P . While not all mechanisms are data-independent, it shows inherent limitations for a broad and natural class of constructions (notably including factorization mechanisms). It also highlights that any hope of achieving accuracy beyond these bounds requires mechanisms whose additive error depends on the input stream. The following lemma formalizes this observation. Lemma 7.12. Consider two continual release problems P = (f, ∼) and P ′ = (f ′ , ∼′ ). Let SP and SP ′ denote the corresponding sensitivity sets, as defined in Definition 7.11. Suppose that SP ′ ⊆ SP . For ε ≥ 0, δ ∈ [0, 1), β ∈ (0, 1), let M be a data-independent (ε, δ)-DP mechanism for P that is (α, β)-accurate. Then there exists an (ε, δ)-DP mechanism M′ for P ′ , that is also (α, β)-accurate. Proof. By M being data-independent, there exists a distribution µ on RT , such that for every σ of d length T , M(σ) = f (σ) + Z with Z distributed according to µ. Wlog assume that M(σ) = f (σ) + Z. By Definition 3.3, M is (ε, δ)-DP for P if and only if, for all σ ∼ σ ′ , and all measurable O ⊆ RT : Pr[f (σ) + Z ∈ O] ≤ eε Pr[f (σ ′ ) + Z ∈ O] + δ, Pr[f (σ ′ ) + Z ∈ O] ≤ eε Pr[f (σ) + Z ∈ O] + δ. Let σ ∼ σ ′ and measurable O ⊆ RT be arbitrary. Let O′ := {y − f (σ) : y ∈ O}. Then, f (σ) + Z ∈ O ⇐⇒ Z ∈ O′ , f (σ ′ ) + Z ∈ O ⇐⇒ Z + f (σ ′ ) − f (σ) ∈ O′ . Moreover, O 7→ O′ is a bijection on all measurable subsets of RT . Hence quantifying over all measurable O′ is equivalent to quantifying over all measurable O. Therefore (after relabeling), we have equivalent inequalities: Pr[Z ∈ O] ≤ eε Pr[Z + f (σ ′ ) − f (σ) ∈ O] + δ, Pr[Z + f (σ ′ ) − f (σ) ∈ O] ≤ eε Pr[Z ∈ O] + δ. Observe that the dependence on σ, σ ′ only appears in the term f (σ) − f (σ ′ ) ∈ SP . It follows that M is (ε, δ)-DP for P , if and only if, for all λ ∈ SP , and all measurable O ⊆ RT : Pr[Z ∈ O] ≤ eε Pr[Z − λ ∈ O] + δ, Pr[Z − λ ∈ O] ≤ eε Pr[Z ∈ O] + δ. Repeating the argument for a data-independent M′ for problem P ′ , and additive noise Z ′ ∈ RT , you arrive at corresponding equations. For completeness: M′ is (ε, δ)-DP for P ′ , if and only if, for all λ ∈ SP ′ , and all measurable O ⊆ RT : Pr[Z ′ ∈ O] ≤ eε Pr[Z ′ − λ ∈ O] + δ, Pr[Z ′ − λ ∈ O] ≤ eε Pr[Z ′ ∈ O] + δ. By the set inclusion SP ′ ⊆ SP , if the additive-noise Z provides privacy for P , then using Z ′ = Z would provide privacy for P ′ . As the noise distributions Z and Z ′ uniquely determine the additive error of M and M′ respectively, the statement follows. To prove our lower bound, we will show that the sensitivity set for continual counting on editneighboring streams, is at least as expressive as that for continual counting under prefix-sum neighboring streams. Lemma 7.13. Let P = Count(∼e , {0, 1, ⊥}T ) and P ′ = Count(∼p , {0, 1}T ). Then, 1. SP ⊇ {0, 1}T ∪ {0, −1}T . 2. SP ′ = {0, 1}T ∪ {0, −1}T . Proof. For the input stream σ = (x1 , . . . , xT ) in {0, 1, ⊥}T , recall that f (σ)t = f (Dt ) = where ⊥ summands are treated as zeros. We prove each item separately. 45
Pt
i=1 xi ,
Item 1.
We begin by proving that
SP ⊇ {0, 1}T .
Fix y ∈ {0, 1}T . Consider the two sequences σ = (1, z1 , . . . , zT −1 ) and σ ′ = (z1 , . . . , zT ) from {0, 1}T (we do not use any ⊥’s), where σ ∼e σ ′ (σ is an edit-insert neighbor at i = 1). For any t ∈ [T ], we have that f (σ)t − f (σ ′ )t = 1 − zt where, on setting zt = 1 − yt ∈ {0, 1}, we get that y = f (σ) − f (σ ′ ) ∈ SP . Hence SP ⊇ {0, 1}T . The argument for proving SP ⊇ {0, −1}T proceeds similarly. Fix y ∈ {0, −1}T , and instead consider σ = (0, z1 , . . . , zT −1 ) and σ ′ = (z1 , . . . , zT ) from {0, 1}T . Now set z1 , . . . , zT based on yt = f (σ)t − f (σ ′ )t = −zt , yielding y = f (σ) − f (σ ′ ) ∈ SP , and so SP ⊇ {0, −1}T . It follows that SP ⊇ {0, 1}T ∪ {0, −1}T , completing the proof of the first item. Item 2.
The definition of prefix-sum neighboring (Definition 7.1) explicitly enforces that: SP ′ ⊆ {0, 1}T ∪ {0, −1}T .
Towards proving the other direction, we will show that SP ′ ⊇ {0, 1}T . Fix y ∈ {0, 1}T . Next, define the sequences σ = (x1 , . . . , xT ), σ ′ = (x′1 , . . . , x′T ) in {0, 1}T via ( ( 1 if yt − yt−1 = 1 1 if yt − yt−1 = −1 ′ xt = xt = 0 otherwise 0 otherwise where we define y0 = 0. We will argue that σ ∼p σ ′ . Indeed, for any t ∈ [T ]: f (σ)t − f (σ ′ )t =
t X
xi −
i=1
t X
x′i =
i=1
t X
(xi − x′i )
i=1
t X = (yi − yi−1 ) = yt ∈ {0, 1}. i=1
Hence, we have that y = f (σ) − f (σ ′ ) ∈ SP ′ , proving SP ′ ⊇ {0, 1}T . By a symmetrical argument, we also have that SP ′ ⊇ {0, −1}T , allowing us to conclude: SP ′ ⊇ {0, 1}T ∪ {0, −1}T . This finishes the proof of the second item, and the lemma. We are now ready to give our lower bound for Count(∼e , {0, 1, ⊥}T ). 1 Theorem 7.14. Let ε ∈ (0, 1/2], δ ∈ [0, 1), and T ∈ N be sufficiently large. Then any (α, 100 )-accurate (ε, δ)-DP data-independent algorithm (see Definition 7.10) for ∼e -neighboring continual counting on {0, 1, ⊥} over T steps satisfies: n 1/3 o 1. If δ = o(ε/T ), then α = Ω̃ min Tε2/3 , T .
nq o T 2. If δ = 0, then α = Ω min , T . ε Proof. Let P = Count(∼e , {0, 1, ⊥}T ) and P ′ = Count(∼p , {0, 1}T ). Consider a data-independent (ε, δ)-DP mechanism M for P that is (α, 1/100)-accurate. By Lemma 7.13 SP ′ ⊆ SP , and so by Lemma 7.12 there exists an (ε, δ)-DP mechanism M′ for P ′ that is (α, 1/100)-accurate. Applying Theorem 7.8 to M′ yields the stated lower bound on α. 46
H1 θ
0.001 0.000
density
density
Adv = +0.200
H0
H0
0.004
0.003
H1
density
Adv = +0.960 0.002
θ 0.002 0.000
−500
0
500
1000
Adv = +0.003
H1 0.002
θ
0.001 0.000
250
500
Ŝ
750
1000
0
Ŝ
(a) BaseCC at ε = 2.78.
H0
200
400
600
Ŝ
(b) PartitionCC at ε = 2.78.
(c) SimECC at ε = 150.
Figure 2: Plots of (normalized) histograms over the statistic Ŝ from the experiment setting in Figure 1a. Each plot shows the corresponding histogram over the statistic Ŝ under H0 (blue; left-hatched) vs. H1 (red, right-hatched), based on drawing N = 20000 streams, with the strong vertical dashed line denoting the decision threshold θ. The weaker dashed lines correspond to the mean value of the statistic under H0 and H1 . No weak dashed lines are visible in Figure 2c as they overlap with the line for θ.
8
Empirical Work
We empirically substantiate the claim that swap-private continual counters are not a good substitute for an edit-private mechanism: when calibrated to defend against a natural distinguishing attack on edit-neighboring streams, they incur meaningfully larger error than our mechanisms for comparable attack success probability.3 More specifically, we construct the attack on a parametric family of structured Bernoulli streams, and sweep privacy parameters to trace the trade-off between how often an attack succeeds, and the respective errors incurred by different continual counters. Formal context for experiments. We formulate the distinguishing attack as a guessing game, a standard approach in the DP auditing literature Jagielski et al. (2020); Nasr et al. (2021); Steinke et al. (2023). The defender draws a stream σ (0) ∼ D (a distribution over input streams described below), constructs an edit-neighbor of σ (0) denoted σ (1) , samples a challenge bit b ∈ {0, 1}, and releases y = M(σ (b) ). The attacker, given knowledge of y, D, M and how σ (1) is constructed for any choice of σ (0) , outputs a guess b̂ ∈ {0, 1} for the value of the challenge bit. We measure the attacker’s performance via their advantage, as done in Cherubin (2017); Swanberg et al. (2025). We use the signed attack advantage defined by the expression Adv = 2 Pr[b̂ = b] − 1 ∈ [−1, 1]. Note that the advantage is defined over the randomness of the stream(s), in addition to the randomness of the challenge bit, and the privatizing mechanism. As such, it captures a notion of “average” performance of the attack for a distribution over streams. In contrast with work on DP auditing, we use advantage as a descriptive statistic for attacker performance under D, not as a tool for refuting DP guarantees. It captures how often a given attacker distinguishes two streams. We study the special case where D is a Bernoulli stream of rate p = (p1 , . . . , pT ) ∈ [0, 1]T , i.e., the stream σ (0) = (x1 , . . . , xT ) is drawn i.i.d. via xt ∼ Bernoulli(pt ). For constructing a neighboring stream, we use σ (1) = f (σ (0) ) = (1, x1 , . . . , xT −1 ), i.e., we insert a 1 at the first position in the stream and discard the last element. Intuitively, since we permit the attacker knowledge of p, the attacker can leverage the fact that the probability of seeing a 1 at any given point in the stream may differ across (0) (1) the two streams. More precisely, for t ≥ 2, Pr[σt = 1] = pt and Pr[σt = 1] = pt−1 . We will formalize this with a natural correlation attack. Let ∆p, ∆y ∈ RT be defined via ∆pt = pt − pt−1 and ∆yt = yt − yt−1 (with p0 = y0 = 0). The attacker computes the values Ŝ(y, p) and θ(p) defined by the expressions Ŝ(y, p) :=
T X
T
(pt − ∆yt )∆pt ,
θ(p) :=
t=2 3 Our source code is available: https://github.com/jodander/CCS26.
47
1X (∆pt )2 . 2 t=2
The attacker then outputs b̂ = 1[Ŝ(y, p) ≥ θ(p)]. To motivate the attack, consider an unbiased (b) (b) additive-noise mechanism, so E[∆yt |σ (b) ] = σt . Under b = 0 we have σt = xt , while for b = 1 and (b) t ≥ 2, we have that σt = xt−1 . Hence the residual rt := pt − ∆yt has mean 0 under b = 0, and mean ∆pt under b = 1. The attacker can thus exploit a known signal in the noise, and Ŝ is a natural linear test correlating r against the signature ∆p; the threshold θ(p) represents the midpoint of the expected value of Ŝ under the two possible values of b. Restricting the sum to t ≥ 2 makes the attack independent of the inserted bit’s value: it only measures the shift in the rate profile arising from the edit. Experimental setup. ters:
We have implemented the following (ε, δ)-DP (unbounded) continual coun-
1. BaseCC: Implementation of the 1-step-1-neighboring continual counter from Lemma 3.12, internally using the near-optimal bounded continual counter from Fichtenberger et al. (2023); Henzinger et al. (2023). 2. PartitionCC: Implementation of the 1-step-1-neighboring continual counter in (Dwork et al., 2015, Theorem 3.1), internally using BaseCC. For setting the threshold for their partitioning mechanism, we allow the mechanism knowledge of the stream length T . 3. ECC: Algorithm 2, with BaseCC as the “base” 1-step-1-neighboring continual counter. 4. SimECC: Implementation of Algorithm 2, but based on the “simple partitioning” (Algorithm 5) with BaseCC as the “base” 1-step-1-neighboring continual counter. 5. GaussianCC: An edit-private continual counter, based on at each step making a fresh release of the running sum with the Gaussian mechanism, and using Gaussian DP Dong et al. (2022) for the composition. It is presented in detail as Algorithm 6 in Section 8.1. The full pipeline - from stream generation to mechanism output to distinguishing attack - uses common random numbers. Each (pseudorandomly) generated trial (b, σ (0) ) is fed to each of the mechanisms being tested, i.e., each mechanism receives the same input stream but the pseudorandomness across mechanisms is not shared. To compare the error of different mechanisms we use the root-mean-squared error (RMSE). For a T T continual counter, taking q Pas input σP∈ {0, 1} and producing an output y ∈ R , the RMSE of its T t output is defined as T1 t=1 (yt − j=1 σj )2 . We write per-run RMSE when we want to emphasize that the error we report is the average RMSE over many trials. Attack advantage vs. error Our main empirical result is shown in Figure 1a. The plot shows the outcome of running and attacking each mechanism (with the exception of ECC) on inputs from Bernoulli streams with a block structure.4 Specifically, we consider streams of length T = 104 with a Bernoulli rate p ∈ {0.1, 0.9}T where the rate changes every 10 steps. Each point shown corresponds to running one mechanism with privacy parameters ε ∈ [0.1, 150], δ = 10−5 , with per-run RMSE and attack advantage estimated over N = 20000 runs. We proceed to make some observations. Firstly, the results suggest that our correlation attack is effective against both 1-step-1-neighboring counters BaseCC and PartitionCC. This is not too surprising in the case of BaseCC - an unbiased continual counter, against which the attack derivation directly applies - but it is arguably more surprising in the case of PartitionCC. While PartitionCC has biased error, the time steps at which it updates its output are nevertheless positively correlated with the Bernoulli rate. Our experiments indicate that this correlation is sufficient to keep the attack effective. Secondly, the same attack proves less effective against the edit-neighboring counters: when we fix a bound on the attack advantage and read off the error each mechanism incurs at that bound, the gap is substantial. From Table 1, we see that on fixing a bound on the attack advantage, the error incurred by SimECC is significantly lower than that incurred by its competitors. Asymptotically, both BaseCC and GaussianCC are input-independent additive-noise mechanisms, so by Theorem 1.2, any calibration 4 Including ECC in the comparison would yield greater error than SimECC because (1) sparsity adaptivity incurs constant-factor overhead, and (2) the stream in Figure 1a is dense (expected ≈ T /2 ones). For sufficiently long sparse streams, ECC is expected to outperform SimECC.
48
Table 1: Per-run RMSE attainable for given attack advantage 0.1 or 0.05 at 95% confidence for the experimental setup in Figure 1a. Subscript of the reported error denotes the standard error (SE). Across the privacy sweep ε ∈ [0.1, 150] BaseCC did not achieve an advantage below 0.05. Mechanism
RMSE @ Adv ≤ 0.1
RMSE @ Adv ≤ 0.05
BaseCC PartitionCC GaussianCC SimECC
280.6±0.6 107.5±0.3 84.081±0.005 31.32±0.02
N/A 188.8±0.4 325.98±0.02 31.32±0.02
that achieves privacy for edit-neighboring streams must incur polynomial ℓ∞ error in T . Our editneighboring mechanisms by contrast achieve polylogarithmic error, so a separation at sufficiently large T is predicted by theory; the empirical contribution is to show that the separation manifests at realistic T against a single, simple attack. Our particular choice of T = 104 is motivated in part by resource constraints: running the setup given in Figure 1a over N = 20000 trials takes a few hours on a commercial MacBook Air (M4). At smaller values of T , we observe that the trade-off between advantage and error is less pronounced, which is primarily explained by our large constant factors. Nevertheless, we note that our findings are largely robust to the precise parameter setting, and refer the reader to Figure 3 in Section 8.1 for evidence to this effect. To give additional insight into why the attack works, we also plot the associated (normalized) histogram over the statistic in Figure 2. In short, the statistic Ŝ is effective at separating the signal based on the secret bit b ∈ {0, 1} when applied to the 1-step-1-neighboring counters, but in the case of PartitionCC the decision threshold θ could be fine-tuned; doing so would only widen the gap with SimECC. When applied to SimECC, the statistic fails to separate the hypotheses, even at ε = 150. We emphasize that this is not to suggest that SimECC is unconditionally robust: it is resistant to this particular, natural attack. Comparing edit-neighboring counters. We finish our empirical section by briefly remarking upon the relative error of the counters for edit-neighboring streams, treated in Figure 1b. Here we make the comparison at (ε = 10, δ = 10−5 )-DP, on Bernoulli streams of length T ∈ {103 , 104 , 105 , 106 } and constant rate 0.01, and over N = 100 runs per point. SimECC achieves substantially lower error than GaussianCC and lower error than ECC, except at the smallest values of T , where ECC produces few or no updates.
8.1
Technical Details
Details on GaussianCC The baseline for edit-DP we compare against is that of at each time step releasing the full prefix sum with the Gaussian mechanism (Lemma 3.4), using that the ℓ2 sensitivity under edit neighbors for each prefix sum is 1. For this to be private on streams of unbounded lengths, however, we need to set the privacy parameters of each individual release such that they in the limit converge to our target (ε, δ)-DP guarantee. Algorithm 6 does exactly this. The only facts of Gaussian DP we leverage is that (1) the Gaussian mechanism with variance 1/µ2 is µ-GDPpfor Pnsensitivity-1 2 queries and (2) the composition of n releases at privacy levels µ , . . . , µ > 0 satisfy 1 n k=1 µk -GDP. pP∞ 2 By the square-summability of the sequence (at )t≥1 , t=1 µt ≤ µ. Hence Algorithm 6 satisfies µGDP, and therefore also (ε, δ)-DP. For the experiments, we chose the sequence (at )≥1 where at = √ 1/(1.85 t ln(t + 1)). On the applicability of Clopper–Pearson For the advantage error bars, we report 95% Clopper– Pearson confidence intervals on the success rate q of the attacker, and translate this into the advantage via the affine map Adv = 2q − 1. This is motivated by the fact that each trial is composed of three independent sampling steps (1) sampling the Bernoulli stream (2) sampling a challenge bit, and (3) sampling noise for the mechanism. As each of these sources of randomness are kept separate, and the adversary does not adapt across trials, the success probability of each attack is Bern(q) for some q,
49
hence the total number of successful attacks is Bin(N, q), which justifies Clopper–Pearson on q, and the confidence interval carrying over to Adv. On the robustness of our results. To demonstrate that our results are not sensitive to the precise parameter setting, we re-compute the results in Figure 1a at T = 1000, and vary other additional parameters. The results are given in Figure 3. The main point we want to highlight is that all four plots are qualitatively quite similar. While the curves do change shape based on the parameter tuning, they do not change by much. Compared to Figure 1a, the major change at T = 103 is that the benefit of SimECC is not as pronounced. As we have discussed, this is not surprising: we expect for the polylogarithmic error scaling of SimECC to become more impactful at larger T .
Acknowledgements This research was supported by 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) under grant DOI 10.55776/Z422. For open access purposes, the authors have applied a CC BY public copyright license to any authoraccepted manuscript version arising from this submission. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Anamay Chaturvedi was supported by an ISTA Fellowship.
References J. D. Andersson and R. Pagh. A smooth binary mechanism for efficient private continual observation. In Advances in Neural Information Processing Systems 36, 2023. J. D. Andersson and R. Pagh. Streaming private continual counting via binning. In IEEE Conference on Secure and Trustworthy Machine Learning, SaTML 2025, Copenhagen, Denmark, April 9-11, 2025, pages 575–589. IEEE, 2025. doi: 10.1109/SATML64287.2025.00038. URL https://doi.org/ 10.1109/SaTML64287.2025.00038. J. D. Andersson, P. Jain, and S. Sivakumar. Improved accuracy for private continual cardinality estimation in fully dynamic streams via matrix factorization. Proc. ACM Manag. Data, 4(2), May 2026. doi: 10.1145/3801902. URL https://doi.org/10.1145/3801902. J. Awan and A. Slavković. Structure and sensitivity in differential privacy: Comparing k-norm mechanisms. Journal of the American Statistical Association, 116(534):935–954, 2021. doi: 10.1080/01621459.2020.1773831. URL https://doi.org/10.1080/01621459.2020.1773831. Algorithm 6 GaussianCC Require: Privacy parameters ε, δ; stream x1 , x2 , · · P ·∈R Require: Square-summable sequence (at )t≥1 with t≥1 a2t ≤ 1 1: µ ← µ-GDP parameter calibrated s.t. µ-GDP implies (ε, δ)-DP 2: S0 ← 0 3: for t = 1, 2, . . . do 4: receive xt 5: St ← St−1 + xt 6: µt ← µ · at 7: sample Zt ∼ N 0, 1/µ2t 8: release Sbt ← St + Zt 9: end for 50
1.0
0.6 0.4
0.6 0.4
0.2
0.2
0.0
0.0 10
0
10
1
10
2
BaseCC SimECC GaussianCC PartitionCC
0.8
Advantage
0.8
Advantage
1.0
BaseCC SimECC GaussianCC PartitionCC
10
3
10
0
10
1
Per-run RMSE
(a) Same parameters, except T = 1000. 1.0
0.6
0.6
10
3
0.4
0.2
0.2
0.0
0.0 1
3
10
2
BaseCC SimECC GaussianCC PartitionCC
0.8
0.4
10
10
(b) Bernoulli rate flips every 50 steps.
Advantage
Advantage
0.8
0
2
1.0
BaseCC SimECC GaussianCC PartitionCC
10
10
Per-run RMSE
10
3
10
Per-run RMSE
0
10
1
10
2
Per-run RMSE
(d) δ = 10−9 .
T
(c) Bernoulli rate p ∈ {0.3, 0.7} .
Figure 3: Plots re-running the setup of Figure 1a but at T = 103 , different seeded randomness and slight parameter variations. The base setup is T = 1000, δ = 10−5 , alternating Bernoulli rates p ∈ {0.1, 0.9}T on blocks of width 10, with each point shown being the average over N = 20000 runs for one value of ε ∈ {0.10, 0.19, 0.38, 0.73, 1.4, 2.8, 5.4, 10, 20, 40, 77, 150}. The error bars on the per-run RMSE are showing the standard error (SE), and the error bars on the advantage are 95% Clopper– Pearson confidence intervals; N has been set such that the error bars are small enough to be barely visible, if at all. Figure 3a runs this precise setup, whereas each of Figures 3b to 3d change the value of one parameter. B. Balle and Y. Wang. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 403–412. PMLR, 2018. A. Bhaskara, D. Dadush, R. Krishnaswamy, and K. Talwar. Unconditional differentially private mechanisms for linear queries. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1269–1284, 2012. J. A. Calandrino, A. Kilzer, A. Narayanan, E. W. Felten, and V. Shmatikov. " you might also like:" privacy risks of collaborative filtering. In 2011 IEEE symposium on security and privacy, pages 231–246. IEEE, 2011. A. R. Cardoso and R. Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. In G. Camps-Valls, F. J. R. Ruiz, and I. Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, Proceedings of Machine Learning Research, pages 2397–2419. PMLR, 2022. URL https: //proceedings.mlr.press/v151/rivera-cardoso22a.html. S. Casacuberta, M. Shoemate, S. P. Vadhan, and C. Wagaman. Widespread underestimation of sensitivity in differentially private libraries and how to fix it. In H. Yin, A. Stavrou, C. Cremers, and E. Shi, editors, Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS 2022, Los Angeles, CA, USA, November 7-11, 2022, pages 471–484. ACM, 2022. doi: 10.1145/3548606.3560708. URL https://doi.org/10.1145/3548606.3560708. 51
T. Chan, E. Shi, M. Zhao, and M. Zhou. Continual learning with participation privacy: An auditable buffering-aggregation recipe. arXiv preprint arXiv:2607.07209, 2026. T. H. Chan, E. Shi, and D. Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3):26:1–26:24, 2011. doi: 10.1145/2043621.2043626. URL http://doi.acm.org/10. 1145/2043621.2043626. G. Cherubin. Bayes, not naïve: Security bounds on website fingerprinting defenses. Proc. Priv. Enhancing Technol., 2017(4):215–231, 2017. doi: 10.1515/POPETS-2017-0046. URL https:// doi.org/10.1515/popets-2017-0046. C. A. Choquette-Choo, A. Ganesh, R. McKenna, H. B. McMahan, J. Rush, A. Guha Thakurta, and Z. Xu. (amplified) banded matrix factorization: A unified approach to private training. Advances in Neural Information Processing Systems, 36, 2023a. C. A. Choquette-Choo, H. B. McMahan, K. Rush, and A. Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Proceedings of the 40th International Conference on Machine Learning, ICML’23, 2023b. E. Cohen, X. Lyu, J. Nelson, T. Sarlós, and U. Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In S. Agrawal and A. Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pages 1200–1222. PMLR, 2024. URL https://proceedings.mlr.press/v247/cohen24b.html. R. Cummings, A. Epasto, J. Mao, T. Mukherjee, T. Ou, and P. Zhong. Differentially private spaceefficient algorithms for counting distinct elements in the turnstile model. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025. OpenReview.net, 2025. URL https://openreview.net/forum?id=O37Pg2cm7y. S. Denisov, H. B. McMahan, J. Rush, A. Smith, and A. Guha Thakurta. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. Advances in Neural Information Processing Systems, 35:5910–5924, 2022. J. Dong, A. Roth, and W. J. Su. Gaussian differential privacy. J. R. Stat. Soc. Series B Stat. Methodol., 84(1):3–37, Feb. 2022. W. Dong, Q. Luo, and K. Yi. Continual observation under user-level differential privacy. In 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, May 21-25, 2023, pages 2190–2207. IEEE, 2023. doi: 10.1109/SP46215.2023.10179466. URL https://doi.org/10.1109/ SP46215.2023.10179466. K. D. Dvijotham, H. B. McMahan, K. Pillutla, T. Steinke, and A. Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In Foundations of Computer Science, 2024. C. Dwork and A. Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating Noise to Sensitivity in Private Data Analysis. In TCC, pages 265–284, 2006. C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In M. Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 381–390. ACM, 2009. doi: 10.1145/1536414.1536467. URL https://doi.org/10.1145/1536414.1536467. C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum. Differential privacy under continual observation. In Proceedings of the 42nd ACM Symposium on Theory of Computing, pages 715–724, 2010. doi: 10.1145/1806689.1806787. URL http://doi.acm.org/10.1145/1806689.1806787.
52
C. Dwork, M. Naor, O. Reingold, and G. 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. A. Edmonds, A. Nikolov, and J. Ullman. The power of factorization mechanisms in local and central differential privacy. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 425–438, 2020. A. Epasto, J. Mao, A. M. Medina, V. Mirrokni, S. Vassilvitskii, and P. 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. ISBN 978-3-95977263-1. doi: 10.4230/LIPIcs.ITCS.2023.48. H. Fichtenberger, M. Henzinger, and L. 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. H. Fichtenberger, M. Henzinger, and J. 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. URL https://proceedings.mlr.press/v202/fichtenberger23a.html. M. Hardt and K. Talwar. On the geometry of differential privacy. In L. J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 705–714. ACM, 2010. doi: 10.1145/1806689.1806786. URL https: //doi.org/10.1145/1806689.1806786. M. Henzinger and J. Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2025. M. Henzinger, J. Upadhyay, and S. 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. M. Henzinger, A. R. Sricharan, and T. A. Steiner. Private counting of distinct elements in the turnstile model and extensions. In Proc. APPROX/RANDOM 2024, pages 40:1–40:21, 2024a. URL https: //doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40. M. Henzinger, J. Upadhyay, and S. 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, 2024b. M. Henzinger, N. P. Kalinin, and J. Upadhyay. Normalized square root: Sharper matrix factorization bounds for differentially private continual counting. CoRR, abs/2509.14334, 2025a. doi: 10.48550/ ARXIV.2509.14334. URL https://doi.org/10.48550/arXiv.2509.14334. M. Henzinger, A. R. Sricharan, and T. A. Steiner. Differentially private continual release of histograms and related queries. In Y. Li, S. Mandt, S. Agrawal, and M. E. Khan, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2025, Mai Khao, Thailand, 3-5 May 2025, volume 258 of Proceedings of Machine Learning Research, pages 1990–1998. PMLR, 2025b. URL https://proceedings.mlr.press/v258/henzinger25a.html. J. Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27, 2015. M. Jagielski, J. R. Ullman, and A. Oprea. Auditing differentially private machine learning: How private is private sgd? In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https://proceedings. neurips.cc/paper/2020/hash/fc4ddc15f9f4b4b06ef7844d6bb53abf-Abstract.html. 53
P. Jain, P. Kothari, and A. Thakurta. Differentially private online learning. In Conference on Learning Theory, pages 24–1. JMLR Workshop and Conference Proceedings, 2012. P. Jain, I. Kalemaj, S. Raskhodnikova, S. Sivakumar, and A. D. Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. In Proc. 37th NeurIPS, 2023a. URL http://papers.nips.cc/paper_files/paper/2023/hash/ 0ef1afa0daa888d695dcd5e9513bafa3-Abstract-Conference.html. P. Jain, S. Raskhodnikova, S. Sivakumar, and A. 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 2023b. P. Jain, A. Smith, and C. Wagaman. Time-aware projections: Truly node-private graph statistics under continual observation. In IEEE Symposium on Security and Privacy, SP 2024, San Francisco, CA, USA, May 19-23, 2024, pages 127–145. IEEE, 2024. doi: 10.1109/SP54263.2024.00196. URL https://doi.org/10.1109/SP54263.2024.00196. P. Kairouz, B. McMahan, S. Song, O. Thakkar, A. Thakurta, and Z. Xu. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning, pages 5213–5225. PMLR, 2021. N. Kalinin, R. McKenna, J. Upadhyay, and C. H. Lampert. Back to square roots: An optimal bound on the matrix factorization error for multi-epoch differentially private SGD. In The Fourteenth International Conference on Learning Representations, 2026. N. P. Kalinin and J. D. Andersson. Learning rate scheduling with matrix factorization for private training. In 7th Symposium on Foundations of Responsible Computing, FORC 2026, Harvard University, Cambridge, MA, USA, June 3-5, 2026, volume 368 of LIPIcs, pages 2:1–2:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. doi: 10.4230/LIPICS.FORC.2026.2. URL https://doi.org/10.4230/LIPIcs.FORC.2026.2. N. P. Kalinin and C. H. Lampert. Banded square root matrix factorization for differentially private model training. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15, 2024, 2024. URL http://papers.nips.cc/paper_files/paper/2024/hash/ 1f7b3b0dd7710af02aac0db5be4cfc8d-Abstract-Conference.html. S. P. Kasiviswanathan and A. Smith. On the’semantics’ of differential privacy: A bayesian formulation. Journal of Privacy and Confidentiality, 6(1), 2014. D. Kifer and A. Machanavajjhala. No free lunch in data privacy. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 193–204, 2011. D. Kifer and A. Machanavajjhala. Pufferfish: A framework for mathematical privacy definitions. ACM Transactions on Database Systems (TODS), 39(1):1–36, 2014. C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB journal, 24(6):757–781, 2015. M. Lyu, D. Su, and N. Li. Understanding the sparse vector technique for differential privacy. Proc. VLDB Endow., 10(6):637–648, 2017. doi: 10.14778/3055330.3055331. URL http://www.vldb.org/ pvldb/vol10/p637-lyu.pdf. R. McKenna. Scaling up the banded matrix factorization mechanism for large scale differentially private ML. In The Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL https://openreview.net/forum?id= 69Fp4dcmJN. H. B. McMahan, Z. Xu, and Y. Zhang. A hassle-free algorithm for private learning in practice: Don’t use tree aggregation, use blts. CoRR, abs/2408.08868, 2024. doi: 10.48550/ARXIV.2408.08868. URL https://doi.org/10.48550/arXiv.2408.08868. 54
M. Nasr, S. Song, A. Thakurta, N. Papernot, and N. Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. In 42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021, pages 866–882. IEEE, 2021. doi: 10.1109/SP40001. 2021.00069. URL https://doi.org/10.1109/SP40001.2021.00069. A. Nikolov, K. Talwar, and L. Zhang. The geometry of differential privacy: the sparse and approximate cases. In D. Boneh, T. Roughgarden, and J. Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 351–360. ACM, 2013. doi: 10.1145/2488608.2488652. URL https://doi.org/10.1145/2488608.2488652. K. Pillutla, J. Upadhyay, C. A. Choquette-Choo, K. Dvijotham, A. Ganesh, M. Henzinger, J. Katz, R. McKenna, H. B. McMahan, K. Rush, T. Steinke, and A. Thakurta. Correlated noise mechanisms for differentially private learning, 2025. URL https://arxiv.org/abs/2506.08201. Y. Qiu and K. Yi. Differential privacy on dynamic data. CoRR, abs/2209.01387, 2022. doi: 10.48550/ ARXIV.2209.01387. URL https://doi.org/10.48550/arXiv.2209.01387. S. Raskhodnikova and T. A. Steiner. Fully dynamic algorithms for graph databases with edge differential privacy. Proc. ACM Manag. Data, 3(2):99:1–99:28, 2025. doi: 10.1145/3725236. URL https://doi.org/10.1145/3725236. S. Song, S. Little, S. Mehta, S. Vinterbo, and K. Chaudhuri. Differentially private continual release of graph statistics. arXiv preprint arXiv:1809.02575, 2018. T. Steinke, M. Nasr, and M. Jagielski. Privacy auditing with one (1) training run. In Advances in Neural Information Processing Systems 36, 2023. M. Swanberg, M. S. M. S. Annamalai, J. Hayes, B. Balle, and A. D. Smith. Beyond the worst case: Extending differential privacy guarantees to realistic adversaries. CoRR, abs/2507.08158, 2025. doi: 10.48550/ARXIV.2507.08158. URL https://doi.org/10.48550/arXiv.2507.08158. M. C. Tschantz, S. Sen, and A. Datta. Sok: Differential privacy as a causal property. In 2020 IEEE Symposium on Security and Privacy (SP), pages 354–371. IEEE, 2020. Z. Xu, Y. Zhang, G. Andrew, C. Choquette, P. Kairouz, B. Mcmahan, J. Rosenstock, and Y. Zhang. Federated learning of gboard language models with differential privacy. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 5: Industry Track), pages 629–639, 2023.
55
A
Results for “Standard” Continual Counters
In this section we briefly prove results for continual counting under 1-step 1-neighboring. We begin by stating the explicit construction with the tightest known bound on the (maximum) variance for the case of bounded streams. Lemma A.1. [Henzinger et al. (2025a)] For every ε > 0, δ ∈ (0, 1) and T ∈ N, there exists a continual counting mechanism CC that is (ε, δ)-DP with respect to the 1-step 1-neighbor relation for streams of length T . Given any input stream of length T , let zt denote the error of CC at time step t ∈ [T ]. Then, ln(T ) 2 + o(1) . zt ∼ N (0, σt ) where σt ≤ Cε,δ 0.846 + π Here Cε,δ is the Gaussian mechanism constant from Lemma 3.4 and the o(1) term goes to zero as T → ∞. Our work requires continual counters supported on unbounded streams; Lemma 3.12 describes such a continual counter. Before proving the lemma, we remark that the result can be derived given access to any (ε, δ)-DP continual counter with error matching Lemma A.1 up to multiplicative constants e.g., the binary tree mechanism Chan et al. (2011); Dwork et al. (2010) based on Gaussian noise - at a cost of worse constants in the error. Proof of Lemma 3.12. The construction is based on the so-called “doubling trick” from Chan et al. (2011), and essentially matches their Algorithm 4 with the exception that we consider approximate DP, and so uses Gaussian rather than Laplace noise. We sketch the argument; constants can be improved by optimizing the privacy budget split. Construction. define
Divide the timeline into dyadic intervals I1 , I2 , . . . , where Ik = [2k−1 , 2k − 1]. We X (psum) (psum) 2 pk := xt + z k where zk ∼ N (0, Cε/2,δ/2 ) t∈Ik
as the partial sum on Ik , released with the Gaussian mechanism. Define the logarithmic mechanism L as the mechanism, that, on receiving xt , outputs ⌊log(t+1)⌋
ℓt :=
X
pk .
k=1
In other words, ℓt is a noisy prefix sum up to the last completed interval. While L is an unbounded mechanism, its error grows linearly with time. To improve it, we run an instance of the continual counter from Lemma A.1 on each unfinished interval. Whenever we enter a new interval Ik , we initialize a fresh (ε/2, δ/2)-DP continual counter for streams of length 2k−1 that receives inputs (xt )t∈Ik , and produces corresponding outputs (qt )t∈Ik . We define our unbounded (ε, δ)-DP continual counter CC as the one that, on receiving xt , outputs ( ℓt if t = 2j − 1 for some j ∈ N yt = ℓt + qt o.w. Privacy. Since each partial sum used by L is (1) a (ε/2, δ/2)-DP release with the Gaussian mechanism and (2) disjoint, L itself is (ε/2, δ/2)-DP via postprocessing. Additionally, any input xt is used as input to exactly one time-bounded (ε/2, δ/2)-DP continual counter. By simple composition, the unbounded mechanism CC is (ε, δ)-DP. Accuracy. Fix t ∈ N where t ∈ Ik for k = ⌊log(t + 1)⌋. Note that by construction, the output can be written as t X yt = xj + z t j=1
56
where zt ∼ N (0, σt2 ). Assume t = 2j − 1 for some j ∈ N. Then by construction: yt =
t X
⌊log(t+1)⌋
X
xj +
j=1
(psum)
zi
i=1
√ and so σt = O(Cε/2,δ/2 log t) in this case. For the second case, we also get a contribution to the error from the time-bounded continual counter initialized for T = |Ik | = 2k = O(t): yt = ℓt + qt =
t X
⌊log(t+1)⌋
xj +
j=1
X
(psum)
zi
+ ẑt
i=1
where ẑt is the zero-mean Gaussian noise from Lemma A.1 of standard deviation O(Cε/2,δ/2 log t). As sums of Gaussians are Gaussian, and the intra-interval error dominates, we can conclude that σt = O(Cε/2,δ/2 log t) for every t. To give an ℓ∞ -error bound and finish the argument, we begin by using a standard Gaussian tail bound. For a fixed t ∈ N and β ∈ (0, 1), we have that: p Pr[|zt | ≥ σt 2 ln(2/β)] ≤ β. In particular, if we choose a failure probability of βt = π6β 2 t2 for the output at time t, then ∞ ∞ h i X p p X Pr |zt | ≥ σt 2 ln(π 2 t2 /(3β)) ≤ βt = β, Pr ∃t ∈ N : |zt | ≥ σt 2 ln(2/βt ) ≤ t=1
t=1
where the first inequality is using a union bound over all time steps, and the last inequality that P∞ 1 π2 t=1 t2 = 6 . Rearranging, we have shown that Pr[∀t ∈ N : |zt | ≤ σt
p
2 ln(π 2 t2 /(3β))] ≥ 1 − β
and so we have proved (α, β)-accuracy for CC where α(t) = σt
p
p 2 ln(π 2 t2 /(3β)) = O Cε/2,δ/2 log(t) log(t/β) .
The final statement follows from using that Cε/2,δ/2 = O(Cε,δ ). This concludes the proof. Given access to an unbounded continual counter, we are able to construct the biased continual counter. We provide the constructive proof of Lemma 3.13 next. Proof of Lemma 3.13. Consider CC instantiated to be (ε, δ/2)-DP. On receiving an input stream σ = (x1 , x2 , . . . ), let its output be CC be y1′ , y2′ , . . . . We define the new continual counter BCC, with output sequence y1 , y2 , . . . via & ( )' t X ′ ∀t ∈ N : yt = max yt + αCC (ε, δ/2, η, t) , xi . i=1
By the definition of BCC, its output is integral, and it cannot underestimate the true count. Privacy. Define another continual counter M that produces outputs ỹ1 , ỹ2 , . . . where ỹt = ⌈yt′ + αCC (ε, δ/2, η, t)⌉. M is (ε, δ/2)-DP, as it is a data-independent postprocessing of CC. From the accuracy of CC, we have that " # t X Pr ∀t ∈ N : yt′ − xi ≤ αCC (ε, δ/2, η, t) ≥ 1 − η , i=1
and so, for any input stream σ,
Pr [BCC(σ) ̸= M(σ)] ≤ η. 57
To prove privacy for BCC, fix T ∈ N and let σ, σ ′ be 1-step 1-neighboring inputs of length T and consider any measurable subset O of length-T output sequences. We write Pr [BCC(σ) ∈ O] ≤ Pr [M(σ) ∈ O] + Pr [BCC(σ) ̸= M(σ)] ≤ Pr [M(σ) ∈ O] + η.
(24)
Additionally, from M being (ε, δ/2)-DP, Pr [M(σ) ∈ O] ≤ eε Pr [M(σ ′ ) ∈ O] + δ/2 ≤ eε Pr [BCC(σ ′ ) ∈ O] + eε η + δ/2.
(25)
Combining (24) and (25), we arrive at Pr [BCC(σ) ∈ O] ≤ eε Pr [BCC(σ ′ ) ∈ O] + (1 + eε )η + δ/2 = eε Pr [BCC(σ ′ ) ∈ O] + δ , where the last step follows from η = 0.5δ/(1 + eε ). As the neighboring relation is symmetric, we are done. Accuracy. For the accuracy, note that a mechanism that directly outputs yt′ + αCC (ε, δ/2, η, t) at time t ∈ N, would be (α, β)-accurate for any β ∈ (0, 1) where α(t) = αCC (ε, δ/2, β, t) + αCC (ε, δ/2, η, t). Pt The same guarantee extends if the algorithm were to output max{yt′ + αη (t), i=1 xi }, as taking the maximum can only reduce the error. Finally, as yt additionally takes the ceiling of the maximum, it follows that BCC is (αBCC , β)-accurate for any β ∈ (0, 1) where αBCC (t) = α(t) + 1 = αCC (ε, δ/2, β, t) + αCC (ε, δ/2, η, t) + 1.
B
Missing Observations in Section 4.2
Observation (Restatement of Observation 4.13). Let T ∈ N. Define CT+ as in Definition 4.10. Let T σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) be two edit-neighboring sequences in ([0, 1] ∪ {⊥}) . Let fσ→σ′ + be the corresponding mapping. Let t1:k ∈ CT , and define t′1:k = fσ→σ′ (t1:k ). Let i, j ∈ [T ] and p, q ∈ [k] be the indices associated with the definition of fσ→σ′ (t1:k ). Let the sequences intsum(σ, t1:k ) and d(t1:k ) denote the input streams of CC and BCC when ECC executes on σ and Part(σ) = t1:k , and let intsum(σ ′ , t′1:k ) and d(t′1:k ) denote the same sequences for σ ′ and t′1:k (see Observation 4.2 and Notation 4.12). Then, the following statements hold: • The sequences intsum(σ, t1:k ) and intsum(σ ′ , t′1:k ) are 4-step 1-neighbors (see Definition 3.9). • The sequences d(t1:k ) and d(t′1:k ) are 2-step 1-neighbors (see Definition 3.9). Proof. We prove the observation for the case where σ is an insertion neighbor of σ ′ . The reverse case is symmetric. For ℓ ∈ [k], let dℓ = tℓ − tℓ−1 and d′ℓ = t′ℓ − t′ℓ−1 denote the ℓ-th entries of d(t1:k ), and Pt′ℓ Ptℓ ′ let intsumℓ = t=t xt and intsumℓ = t=t ′ +1 xt denote the ℓ-th entries of intsum(σ, t1:k ) and ℓ−1 +1 ℓ−1
intsum(σ ′ , t′1:k ). We prove this observation in two cases: p ≥ q − 2 and p < q − 2. Case 1: p ≥ q − 2. In this case, by Definition 4.10, we have t′1:k = t1:k . Hence, d(t1:k ) = d(t′1:k ). Next, we compare the interval sums. For every ℓ ∈ {1, . . . , p − 1} ∪ {q + 1, . . . , k}, the corresponding interval lies entirely outside the affected region from index i to j. Thus xt = x′t for all indices in the interval, and therefore intsumℓ = intsum′ℓ . It remains to consider ℓ ∈ {p, . . . , q}. For such ℓ, both sums are taken over the same index set {tℓ−1 + 1, . . . , tℓ }. By the edit-neighboring property, the sequences (x1 , . . . , xT ) and (x′1 , . . . , x′T ) differ only in the indices {i, . . . , j}, where the values are shifted by one 58
position. A direct comparison between intsumℓ and intsum′ℓ shows that all terms cancel except possibly at the two boundary indices, where the lower boundary is the maximum of i and the starting index of the ℓ-th interval and the upper boundary is the minimum of j and the ending index of this interval. More precisely, we have tℓ−1 = t′ℓ−1 ; tℓ = t′ℓ ; xt = x′t for every t ∈ {tℓ−1 + 1, . . . , i − 1} ∪ {j + 1, . . . , tℓ }; xt = x′t−1 for every t ∈ {max{i, tℓ−1 + 1} + 1, . . . , min{tℓ , j}}. Therefore, ′
tℓ X
|intsumℓ − intsum′ℓ | =
xt −
tℓ X
x′t
t=t′ℓ−1 +1
t=tℓ−1 +1
=
tℓ X
(xt − x′t )
t=tℓ−1 +1
= |xmax{i,tℓ−1 +1} − x′min{tℓ ,j} | ≤ 1. In the last inequality we used the fact that all xt values lie in [0, 1]. Since p ≥ q − 2, there are at most 3 indices ℓ ∈ {p, . . . , q}. Hence the sequences intsum(σ, t1:k ) and intsum(σ ′ , t′1:k ) differ in at most a 3 coordinates, each by at most 1, and thus (since 3 < 4) these sequences are 4-step 1-neighbors. Case 2: p < q − 2. By Definition 4.10, the checkpoints t′ℓ = tℓ for every ℓ ∈ {1, . . . , p} ∪ {q − 1, . . . , k} and t′ℓ = tℓ − 1 for every ℓ ∈ {p + 1, . . . , q − 2}. Therefore, the checkpoint differences dℓ = tℓ − tℓ−1 and d′ℓ = t′ℓ − t′ℓ−1 are identical for every ℓ ∈ [k] \ {p + 1, q − 1} and differ by 1 at p + 1 and q − 1. Hence, the sequences d(t1:k ) and d(t′1:k ) are 2-step 1-neighbors. As in Case 1, we have intsumℓ = intsum′ℓ for every ℓ ∈ {1, . . . , p − 1} ∪ {q + 1, . . . , k}, and |intsumℓ − intsum′ℓ | ≤ 1 for every ℓ ∈ {p, q}. For ℓ ∈ {p + 2, . . . , q − 2}, the intervals shift by one position, and we have tℓ−1 + 1 = t′ℓ−1 + 2; tℓ = t′ℓ + 1; and xt = x′t−1 for every t ∈ {tℓ−1 + 1, . . . , tℓ }. Thus, tℓ X
intsumℓ − intsum′ℓ =
′
xt −
=
xt −
tℓ X
tX ℓ −1
x′t
t=tℓ−1
t=tℓ−1 +1
=
x′t
t=t′ℓ−1 +1
t=tℓ−1 +1 tℓ X
tℓ X
(xt − x′t−1 ) = 0
t=tℓ−1 +1
Finally, we consider ℓ = q − 1 and ℓ = p + 1. Here, t′q−2 = tq−2 − 1 while t′q−1 = tq−1 . Again, we have xt = x′t−1 for every t ∈ {tq−2 + 1, . . . , tq−1 }, xt = x′t−1 . Therefore, t′q−1
tq−1
|intsumq−1 − intsum′q−1 | =
X
xt −
tq−1
X
x′t
t=t′q−2 +1
t=tq−2 +1
=
X
tq−1
xt −
t=tq−2 +1
X
x′t
t=tq−2
= | − x′tq−2 | ≤ 1, which shows the bound for ℓ = q − 1. For ℓ = p + 1 an analogous argument shows |intsump+1 − intsum′p+1 | ≤ 1. As a result, the sequences intsum(σ, t1:k ) and intsum(σ ′ , t′1:k ) are identical, except in the indices p, p + 1, q − 1, q, each by at most 1, and hence are 4-step 1-neighbors. Observation B.1. Let T ∈ N, and let σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) be two edit-neighboring sequences in ([−1, 1] ∪ {⊥})T . Let fσ→σ′ : C + → C be the function defined in Definition 4.10. Let t1:k ∈ C + and tk+1 = T + 1. Define t′1:k = fσ→σ′ (t1:k ). 59
Define indices i, j ∈ [T ] and p, q ∈ [k + 1] as in the definition of fσ→σ′ (t1:k ). For every ℓ ∈ [k], define Sℓ :=
t X
tℓ
and
xw
w=tℓ−1 +1
t X
Sℓ′ :=
t′ℓ x′w
w=t′ℓ−1 +1
t=tℓ−1 +1
, t=t′ℓ−1 +1
with xw = ⊥ and x′w = ⊥ treated as 0. Moreover, define Sk+1 :=
t X w=tk +1
!T and
xw
′ Sk+1 :=
t X
w=t′k +1
t=tk +1
T x′w
,
t=t′k +1
with ⊥ values treated as 0. 1. For every ℓ ∈ {1, . . . , p − 1} ∪ {p + 2, . . . , q − 2} ∪ {q + 1, . . . , k}, we have Sℓ = Sℓ′ . 2. Assume q > p+2 and σ is an insertion neighbor of σ ′ at step i. Then Sp+1 is a 1-shift 1-neighbor ′ ′ of Sp+1 , and Sq−1 is a 1-shift 1-neighbor of Sq−1 . ′ 3. Assume q > p+2 and σ ′ is an insertion neighbor of σ at step i. Then Sp+1 is a 1-shift 1-neighbor ′ of Sp+1 , and Sq−1 is a 1-shift 1-neighbor of Sq−1 . ′ 4. The sequences Sk+1 and Sk+1 are all-step 1-neighbors.
5. For ℓ ∈ {p, q}, the sequences Sℓ and Sℓ′ are all-step 1-neighbors. ′ 6. Assume q = p + 2. Then, the sequences Sp+1 and Sp+1 are all-step 1-neighbors.
Proof. Throughout this proof, whenever we invoke the assumption that every entry of σ and σ ′ has magnitude at most 1, we mean that each entry is either a real value in this range or the symbol ⊥, which is treated as the value 0 ∈ [−1, 1]. For ℓ ∈ [k], the sequence Sℓ has length tℓ − tℓ−1 . For h ∈ [tℓ − tℓ−1 ], we denote the h-th entry of Sℓ by Sℓ [h], which satisfies tℓ−1 +h
Sℓ [h] =
X
xw .
w=tℓ−1 +1
Similarly, for ℓ ∈ [k], the sequence Sℓ′ has length t′ℓ − t′ℓ−1 . For h ∈ [t′ℓ − t′ℓ−1 ], we denote the h-th entry of Sℓ′ by Sℓ′ [h], which satisfies t′ℓ−1 +h
Sℓ′ [h] =
X
x′w .
w=t′ℓ−1 +1
The sequences σ and σ ′ are edit-neighboring sequences, meaning that one of them is an insertion neighbor of the other at step i. By Definition 3.11 and Definition 4.10, we have: • Assume σ is an insertion neighbor of σ ′ at step i. Then j is the smallest index in {i, . . . , T } such that x′j = ⊥ (and j = T + 1 if no such index exists). By Definition 3.11, we have: – For every t ∈ {1, . . . , i − 1}, xt = x′t . – For every t ∈ {i + 1, . . . , min{j, T }}, xt = x′t−1 . – For every t ∈ {j + 1, . . . , T }, xt = x′t . Moreover, by the definition of fσ→σ′ , p, q ∈ [k + 1] are the indices satisfying tp−1 < i ≤ tp and tq−1 < j ≤ tq , and we have (t1 , . . . , tp , tp+1 −1, . . . , tq−2 −1, tq−1 , . . . , tk ), if p < q − 2, t′1:k = (t , . . . , t ), o.w.. 1 k
60
• Assume σ ′ is an insertion neighbor of σ at step i. Then j is the smallest index in {i, . . . , T } such that xj = ⊥ (and j = T + 1 if no such index exists). By Definition 3.11, we have: – For every t ∈ {1, . . . , i − 1}, x′t = xt . – For every t ∈ {i + 1, . . . , min{j, T }}, x′t = xt−1 . – For every t ∈ {j + 1, . . . , T }, x′t = xt . Moreover, by the definition of fσ→σ′ , p, q ∈ [k + 1] are the indices satisfying tp−1 < i ≤ tp and tq−1 < j ≤ tq , and we have (t1 , . . . , tp , tp+1 +1, . . . , tq−2 +1, tq−1 , . . . , tk ), if q > p, t′1:k = (t , . . . , t ), o.w. 1 k In the second case, the indices p and q indeed satisfy t′p−1 < i ≤ t′p and t′q−1 < j ≤ t′q . Moreover, in this case we have (t′1 , . . . , t′p , t′p+1 −1, . . . , t′q−2 −1, t′q−1 , . . . , t′k ), if q > p, t1:k = (t′ , . . . , t′ ), o.w.. 1 k With these observations, the relation between the sequences σ and σ ′ and the relation between the checkpoint sequences t1:k and t′1:k in the second case are identical to those in the first case, with the roles of σ = (x1 , . . . , xT ) and σ ′ = (x′1 , . . . , x′T ) as well as t1:k and t′1:k swapped. Throughout this proof, we only rely on these relations. Therefore, it suffices to prove the desired properties of Sℓ and Sℓ′ under the assumption that σ is an insertion neighbor of σ ′ . By symmetry, an identical argument applies when σ ′ is an insertion neighbor of σ, with the roles of Sℓ and Sℓ′ exchanged. Using this, we prove items (1), (4), (5), and (6) under the assumption that σ is an insertion neighbor of σ ′ . We also conclude item (3) by symmetry from item (2). (1): By the above discussion, we assume without loss of generality that σ is an insertion neighbor of σ ′ at step i. We must show that for every ℓ ∈ {1, . . . , p − 1} ∪ {p + 2, . . . , q − 2} ∪ {q + 1, . . . , k}, the sequences Sℓ and Sℓ′ have the same length and identical entries. • Case ℓ ∈ {1, . . . , p − 1}. In this case, tℓ−1 = t′ℓ−1 and tℓ = t′ℓ , so both Sℓ and Sℓ′ have length tℓ − tℓ−1 . Since i > tp−1 ≥ tℓ , the additionally inserted element xi occurs strictly after all indices contributing to Sℓ . Hence, xt = x′t
for all t ∈ {tℓ−1 + 1, . . . , tℓ }.
It follows directly that Sℓ = Sℓ′ . • Case ℓ ∈ {p + 2, . . . , q − 2}. Here, t′ℓ−1 = tℓ−1 − 1 and t′ℓ = tℓ − 1, so both sequences again have length tℓ − tℓ−1 . Moreover, since i ≤ tp ≤ tℓ−1 and j > tq−1 ≥ tℓ , the shift affects all indices in the range {tℓ−1 + 1, . . . , tℓ }. In particular, xt = x′t−1
for all t ∈ {tℓ−1 + 1, . . . , tℓ }.
Therefore, for every h ∈ [tℓ − tℓ−1 ], Sℓ [h] =
tℓ−1 +h
tℓ−1 +h
tℓ−1 +1+h
X
X
X
w=tℓ−1 +1
xw =
x′w−1 =
w=tℓ−1
w=tℓ−1 +1
t′ℓ−1 +h
x′w =
X
x′w = Sℓ′ [h].
w=t′ℓ−1 +1
Hence, Sℓ = Sℓ′ . • Case ℓ ∈ {q + 1, . . . , k}. In this case, tℓ−1 = t′ℓ−1 and tℓ = t′ℓ , so the two sequences have equal length. Since j ≤ tq ≤ tℓ−1 , the shifting finishes strictly before the indices contributing to Sℓ , and thus xt = x′t for all t ∈ {tℓ−1 + 1, . . . , tℓ }. Consequently, Sℓ = Sℓ′ . 61
(2): We have tp = tp and tp+1 = t′p+1 + 1. Moreover, since p + 2 < q ≤ k + 1, we have p + 1 ≤ k. ′ Therefore, the sequence Sp+1 has length tp+1 − tp , while Sp+1 has length tp+1 − tp − 1. We must show ′ that Sp+1 is a 1-shift 1-neighbor of Sp+1 , i.e., Sp+1 [1] ≤ 1 and |Sp+1 [h] − Sp+1 [h − 1]| ≤ 1 for every h ∈ [tp+1 − tp ]/{1}. The first condition holds because Sp+1 [1] = |xtp +1 | ≤ 1. Fix h ∈ {2, . . . , tp+1 − tp }. By definition, i ≤ tp and tp+1 < tq−1 < j. Thus we have xt = x′t−1 for every t ∈ {tp + 1, . . . , tp+1 }. Therefore, for every h ∈ [tp+1 − tp ], t′p +h−1
tp +h
X
′ |Sp+1 [h] − Sp+1 [h − 1]| =
tp +h
X
xt −
t=t′p +1
t=tp +1
X
x′t =
tp +h−1
xt −
t=tp +1
X
xt+1
t=tp +1
= |xtp +1 | ≤ 1. ′ ′ Thus, Sp+1 is a 1-shift 1-neighbor of Sp+1 . The proof that Sq−1 is a 1-shift 1-neighbor of Sq−1 follows by an identical argument.
(3): This item holds immediately by symmetry. (4): As before, we assume without loss of generality that σ is an insertion neighbor of σ ′ at step i. We have tℓ = t′ℓ for every ℓ ≥ q − 1. Thus, since q ≤ k + 1, we have tk = t′k , and both sequences Sk+1 ′ ′ and Sk+1 have length T − tk . We must show that |Sk+1 [h] − Sk+1 [h]| ≤ 1 for every h ∈ [T − tk ]. Fix h ∈ [T − tk ]. Both p and q can be equal to k + 1, thus indices i and j could potentially lie in the set {tk + 1, . . . , T }. We consider the following three cases. ′ • Case 1: tk + h < i. In this case, xt = x′t for all t ∈ {tk + 1, . . . , tk + h}, and thus Sk+1 [h] = Sk+1 [h].
• Case 2: i ≤ tk + h < j. In this case, xt = x′t for all t ∈ {tk + 1, . . . , i − 1} and xt = x′t−1 for all t ∈ {i + 1, . . . , tk + h}. Hence, ′ |Sk+1 [h] − Sk+1 [h]| =
tX k +h
t′k +h−1
xt −
tX k +h
x′t
t=t′k +1
t=tk +1
=
X
xt −
i−1 X
xt −
tk X +h−1
t=tk +1
t=tk +1
xt+1 − x′tk +h
t=i
= |xi − x′tk +h | ≤ 1, where we use the fact that xi , x′tk +h ∈ [0, 1]. • Case 3: tk + h ≥ j. In this case, xt = x′t for all t ∈ {tk + 1, . . . , i − 1, j + 1, . . . , tk + h} and xt = x′t−1 for all t ∈ {i + 1, . . . , tk + j}. Therefore, ′ |Sk+1 [h] − Sk+1 [h]| =
tX k +h
t′k +h−1
tX k +h
x′t
t=t′k +1
t=tk +1
=
X
xt −
i−1 X
xt −
t=tk +1
t=tk +1
xt −
j−1 X
xt+1 − x′j −
t=i
tX k +h
xt
t=j+1
= |xi | ≤ 1, where we use the facts that xi ∈ [0, 1] and x′j is considered as 0. (5): As before, we assume without loss of generality that σ is an insertion neighbor of σ ′ at step i. If p = k + 1, then the proof follows directly from item (4). Assume p ≤ k. Then both sequences Sp and Sp′ have length tp −tp−1 . We must show that Sp and Sp′ are all-step 1-neighbors, i.e., |Sp [h]−Sp′ [h]| ≤ 1 for every h ∈ [tp − tp−1 ]. Fix h ∈ [tp − tp−1 ]. By definition, i lies in the range {tp−1 + 1, . . . , tp }. As p and q could be equal, j could also lie in this range. We consider the following three cases. (Case three does not happen if q > p.) 62
• Case 1: tp−1 + h < i. In this case, xt = x′t for all t ∈ {tp−1 + 1, . . . , tp−1 + h}, and thus Sp [h] = Sp′ [h]. • Case 2: i ≤ tp−1 + h < j. In this case, xt = x′t for all t ∈ {tp−1 + 1, . . . , i − 1} and xt = x′t−1 for all t ∈ {i + 1, . . . , tp−1 + h}. Hence, t′p−1 +h−1
tp−1 +h
X
|Sp [h] − Sp′ [h]| =
X
xt −
t=tp−1 +1 tp−1 +h
X
=
x′t
t=t′p−1 +1 tp−1 +h−1
i−1 X
xt −
t=tp−1 +1
X
xt −
t=tp−1 +1
xt+1 − x′tp−1 +h
t=i
= |xi − x′tp−1 +h | ≤ 1, where we use the fact that xi , x′tp−1 +h ∈ [0, 1]. • Case 3: tp−1 + h ≥ j. In this case, xt = x′t for all t ∈ {tp−1 + 1, . . . , i − 1, j + 1, . . . , tp−1 + h} and xt = x′t−1 for all t ∈ {i + 1, . . . , tp−1 + j}. Therefore, t′p−1 +h−1
tp−1 +h
X
|Sp [h] − Sp′ [h]| =
X
xt −
x′t
t=tp−1 +1
t=t′p−1 +1
tp−1 +h
i−1 X
X
=
xt −
xt −
j−1 X
t=tp−1 +1
t=tp−1 +1
tp−1 +h
xt+1 − x′j −
X
xt
t=j+1
t=i
≤ |xi | ≤ 1, where we use the facts that xi ∈ [0, 1] and x′j is considered as 0. Thus, Sp and Sp′ are all-step 1-neighbors. It remains to show Sq and Sq′ are all-step 1-neighbors. If p = q, then the statement holds as shown for p. Assume q > p. Both sequences Sq and Sq′ have length tq − tq−1 . We must show that |Sq [h] − Sq′ [h]| ≤ 1 for every h ∈ [tq − tq−1 ]. Fix h ∈ [tq − tq−1 ]. Since q > p, we have i ≤ tq−1 , and also by definition, tq−1 < j ≤ tq . There are two cases: • Case 1: tq−1 + h ≤ j. In this case, xt = x′t−1 for all t ∈ {tq−1 + 1 . . . , tq−1 + h}. Hence, t′q−1 +h−1
tq−1 +h
|Sq [h] − Sq′ [h]| =
X
xt −
t=tq−1 +1
X
tq−1 +h
X
x′t =
t=t′q−1 +1
t=tq−1 +1
tq−1 +h−1
X
xt −
xt+1 − x′tq +h
t=tq−1 +1
≤ |xtq−1 +1 − x′tq +h | ≤ 1, where we use the fact that xtq−1 +1 , x′tq +h ∈ [0, 1]. • Case 2: tp−1 + h > j. In this case, xt = x′t−1 for all t ∈ {tq−1 + 1 . . . , j} and xt = x′t for all t ∈ {i + 1, . . . , tq−1 + h}. Therefore, t′q−1 +h−1
tq−1 +h
|Sq [h] − Sq′ [h]| =
X
xt −
tq−1 +h
X
x′t
t=t′q−1 +1
t=tq−1 +1
=
X
xt −
t=tq−1 +1
j−1 X
tq−1 +h
xt+1 − x′j −
t=tq−1 +1
≤ |xtq−1 +1 | ≤ 1, where we use the facts that xtq−1 +1 ∈ [0, 1] and x′j is considered as 0. 63
X t=j+1
xt
(6): As before, we assume without loss of generality that σ is an insertion neighbor of σ ′ at step i. Since p = q − 2, by definition, we have tp = t′p and tp+1 = t′p+1 . Moreover, since p + 1 = q − 1 and q ≤ ′ k + 1, we have p + 1 ≤ k. Consequently, both sequences Sp+1 and Sp+1 have length tp+1 − tp . We must ′ ′ show that Sp+1 and Sp+1 are all-step 1-neighbors, i.e., for every h ∈ [tp+1 − tp ], |Sp+1 [h] − Sp+1 [h]| ≤ 1. ′ Fix h ∈ [tp+1 − tp ]. By definition, i ≤ tp and j > tq−1 = tp+1 . Thus, xt = xt−1 for all t ∈ {tp + 1, . . . , tp + h}. Hence, t′p +h−1
tp +h ′ |Sp+1 [h] − Sp+1 [h]| =
X
X
xt −
x′t
t=t′p +1
t=tp +1
tp +h
= xtp +1 +
X
tp +h−1
xt −
t=tp +2
X
xt+1 − x′tp +h
t=tp +1
≤ |xtp +1 − x′tp +h | ≤ 1, where we use the fact that xtp +1 , x′tp +h ∈ [0, 1].
C
Related Work on Continual Counting
Throughout the related work, discussions of error pertain to the ℓ∞ error with constant probability on streams of known length, unless specified otherwise. This corresponds to α, for e.g., for an (α, 1/3)accurate mechanism. Standard Continual Counting. The concurrent works Dwork et al. (2010) and Chan et al. (2011) initiated the study of continual counting for pure DP. Their celebrated binary tree mechanism achieves an error of Oε (log2 T ), and Dwork et al. (2010) proved a lower bound of Ωε (log T ). Jain et al. (2012) adapted the binary tree mechanism to approximate DP, achieving an error of Oε,δ (log3/2 T ). While the lower bound in Dwork et al. (2010) can be extended to (ε, δ)-DP for polynomially small δ, the ℓ2 lower bound by Henzinger et al. (2023) implies an ℓ∞ error of Ωε,δ (log T ) for constant δ. Besides asymptotics, there is a rich literature on optimizing the constants in these upper bounds, see e.g., Honaker (2015); Kairouz et al. (2021); Fichtenberger et al. (2021); Denisov et al. (2022); Andersson and Pagh (2023); Henzinger et al. (2023); Dvijotham et al. (2024); Henzinger et al. (2024b); Andersson and Pagh (2025); Henzinger and Upadhyay (2025); Henzinger et al. (2025a). Common across all these constructions is that they are based on adding correlated noise, drawn independently of the input, to the counts, and are all variants of the (matrix) factorization mechanism introduced by Li et al. (2015). If the error of the mechanism is not measured over worst-case inputs, but instead is allowed to adapt to the sparsity of the input, then there are additional results. Defining n := |{xt ̸= 0 : t ∈ [n]}| as the sparsity of an input σ, Dwork et al. (2015) gave an accuracy bound of Oε (log T + log2 n) for pure DP. Their key idea was the partitioning mechanism, which decomposes the stream into Oε (n) blocks, each containing no more than Oε (log T ) updates, and then running a continual counter on the blocks. The same idea can be applied to (ε, δ)-DP, yielding an error of Oε,δ (log T + log3/2 n). The work by Henzinger et al. (2025b) extended this to the histogram setting, i.e. to higher-dimensional inputs and outputs and Qiu and Yi (2022) generalizes the technique to all linear queries over a set of elements that is modified at each time step by the insertion or deletion of one item. Finally, recent work by Cohen et al. (2024) showed a matching lower bound of Ωε,δ (n) for very sparse streams where n = O(log T ). Continual Counting under Non-Standard Neighborings To the best of our knowledge, all past work on continual counting that uses a different neighboring relation fall into one of two categories. The first category derives from implementing user-level DP under the standard neighboring relation, allowing a user to contribute multiple entries in σ. If any user is allowed to contribute up to k ∈ [T ] entries in a stream σ, then σ ∼k σ ′ if at most k of the inputs differ. This is for example a motivating example in DP machine learning (Kairouz et al., 2021), where continual counting is used as a primitive (privately summing gradients), and we would like to support users contributing more than one example 64
during training.5 To achieve better utility than what a direct application of group privacy would yield, it has become common to enforce more structure in user participation patterns. In particular, Choquette-Choo et al. (2023b,a) introduced the notion of b-min-separated k-repeated participation, where σ ∼(k,b) σ ′ if the two streams differ in at most k positions, and these positions are separated by at least b steps. There has been a considerable amount of work focusing on optimizing factorizationbased mechanisms in this setting Kalinin and Lampert (2024); McMahan et al. (2024); McKenna (2025); Kalinin et al. (2026); Kalinin and Andersson (2026). We also highlight the work of Dong et al. (2023) on user-level DP. Instead of restricting participation patterns, they dynamically track user participation to give a down-neighborhood optimal algorithm (up to polylogarithmic factors) for ε-DP. The second class of works is based on reductions from continual cardinality estimation problems to continual counting. Here the input stream σ contains updates (additions and/or deletions of items), and we maintain a set of all present items, St , over time. At each time step t, we are to output a statistic f (St ), e.g., the size of St . Rather than designing algorithms for directly releasing f , Song et al. (2018) proposed solving the continual counting problem on d = (f (S1 ), f (S2 )−f (S1 ), . . . , f (ST )− f (ST −1 )). Depending on the problem, and the neighboring relation σ ∼c σ, the induced neighboring relation d ∼r d′ for the corresponding continual counting problem may either overlap with the standard notion, or deviate significantly. E.g., releasing the number of edges or connected components under edge-insertions with edge-level DP cleanly reduces to regular continual counting Song et al. (2018); Fichtenberger et al. (2021). On the other hand, counting distinct elements in the turnstile model, even under event-level DP, requires error Ωε,δ (T 1/4 ) for worst-case inputs Jain et al. (2023a). This last result implies that continual counting under the corresponding induced neighboring ∼r suffers the same polynomial lower bound. For additional works that leverage this reduction technique, see e.g., Epasto et al. (2023); Fichtenberger et al. (2023); Jain et al. (2024); Henzinger et al. (2024a); Raskhodnikova and Steiner (2025); Cummings et al. (2025); Andersson et al. (2026) and references therein. Our work on the edit-neighboring relation, ∼e , is distinct from past works on continual counting. Firstly, we are not aware of any past work that defines neighboring inputs in terms of shifts, and, to the best of our knowledge, no neighboring notion has (semantically) treated “⊥” differently from “0”. Additionally, we are not aware of any existing algorithm for continual counting, under any neighboring relation, that both (1) is not based on adding input-independent correlated noise to the true counts, and (2) targets worst-case ℓ∞ error. For example, while the algorithm by Dwork, Naor, Reingold and Rothblum Dwork et al. (2015) based on private partitions for swap-neighboring streams is outside the class of input-independent additive noise algorithms, and allows for improved error on sparse streams, algorithms within that class still achieve a lower error on dense streams. By contrast, we give an algorithm for continual counting under ∼e -neighboring achieving polylogarithmic error, and additionally show that any algorithm based on input-independent additive noise has to incur an exponentially larger error.
D
Continual Counting under Extended Edit Neighboring
In this section, we study continual counting under an extended version of edit neighboring that allows streams of different lengths. In Definition 3.11, an insertion into a stream without ⊥ was defined by adding an element at position i and discarding the final element to preserve the length. In contrast, in the extended definition, the final element is not removed, and consequently neighboring streams may have different lengths. This introduces an additional challenge for differential privacy: a mechanism must avoid revealing the exact length of the input stream. The goal of this extension is to process all inputs without discarding any element. To achieve this, the mechanism cannot simply run for a fixed number of steps; instead, it must continue processing until it receives a special symbol $ denoting the end of the input stream, at which point it halts. Definition D.1 (Extended Edit Neighbors). Let T, T ′ ∈ N ∪ {0}, and let σ = (x1 , . . . , xT , $) and σ ′ = (x′1 , . . . , x′T ′ , $) be two sequences in ([0, 1] ∪ {⊥})∗ × {$}. We say that σ is an extended insertion neighbor of σ ′ at step i ∈ {1, . . . , T } if the following conditions hold: • For all t < i, we have xt = x′t . 5 See the recent monograph by Pillutla et al. (2025) for an in-depth treatment of this application.
65
• Let j be the smallest index in {i, . . . , T } such that x′j = ⊥. If no such index exists, set j = T + 1. – If j ≤ T , then the sequences σ and σ ′ are of the same length, i.e., T = T ′ ; for every t ∈ {i + 1, . . . , j}, we have xt = x′t−1 ; and for every t ∈ {j + 1, . . . , T }, we have xt = x′t . – If j = T + 1, then T = T ′ + 1, and xt = x′t−1 for all t ∈ {i + 1, . . . , T + 1}. We say that σ and σ ′ are length-changing edit neighbors if either σ is a length-changing insertion neighbor of σ ′ at some step i ∈ [T ], or σ ′ is a length-changing insertion neighbor of σ at some step i ∈ [T ′ ]. We now define a wrapper mechanism W that transforms any continual counter that is private with respect to the edit neighboring in Definition 3.11 (e.g., ECC from Section 4) into one that is private with respect to the extended edit neighboring in Definition D.1. Mechanism W. At initialization, the mechanism W receives privacy parameters ε and δ. It first samples U ∼ Lap(2/ε) and sets 2 ln(1/δ) + ⌈U ⌉ . C = max 0, 1 + ε It then initializes an instance of ECC with parameters ε/2 and δ/2. At each time step t, W takes one of the following actions: • If an input xt ∈ [0, 1] ∪ {⊥} arrives, it feeds xt to ECC and returns its output. • If the end-of-stream symbol $ arrives, W generates C additional inputs over the next C steps as follows: while C > 0, it decrements C, feeds ⊥ to ECC, and outputs the result. Once C = 0, W halts permanently. By construction, given an input stream σ = (x1 , . . . , xT , $), the mechanism W produces at least T outputs. Lemma D.2. Let W be the wrapper mechanism described above with privacy parameters ε > 0 and 0 < δ ≤ 1. Then, W is (ε, δ)-DP with respect to the notion of extended neighbors defined in Definition D.1. Proof. Let T, T ′ ∈ N ∪ {0}, and let σ = (x1 , . . . , xT , $) and σ ′ = (x′1 , . . . , x′T ′ , $) be two extended edit-neighboring sequences in ([0, 1] ∪ {⊥})∗ × {$}. We must show that the output distributions of W on σ and σ ′ , denoted by W(σ) and W(σ ′ ), are (ε, δ)-indistinguishable. Without loss of generality, we assume that σ is an extended insertion neighbor of σ ′ at step i ∈ [T ]. We consider two cases: T = T ′ and T = T ′ + 1. Case T = T ′ . Recall the random variable U ∼ Lap(2/ε) and the padding length C = max {0, 1 + 2 ln(1/δ)/ε + ⌈U ⌉} in the definition of W. The distribution of the padding length c is identical whether W is executed on σ or σ ′ . Therefore, to show W(σ) and W(σ ′ ) are (ε, δ)-indistinguishable, it suffices to show that for every fixed padding length c, the conditional output distributions are (ε, δ)indistinguishable. Fix c ∈ N ∪ {0}. Conditioned on the padding length being c, the outputs W(σ) and W(σ ′ ) equal the output streams of ECC on the padded inputs σ · ⊥c and σ ′ · ⊥c , respectively. We now show that these padded streams are edit neighbors under Definition 3.11. Since T = T ′ , by Definition D.1, there exists j ∈ [T ] such that: (1) x′j = ⊥; (2) xt = x′t−1 for every t ∈ {i + 1, . . . , j}; and (3) xt = x′t for every t ∈ {j + 1, . . . , T }. Comparing this with Definition 3.11 implies that the padded sequences σ · ⊥c and σ ′ · ⊥c are edit neighbors. Therefore, by Theorem 4.8 and the choice of privacy parameters in W, the output distributions of ECC on σ · ⊥c and σ ′ · ⊥c are (ε/2, δ/2)-DP (and consequently, (ε, δ)-DP) with respect to edit neighboring, completing the proof for this case. Case T = T ′ + 1. We must show that for every measurable set Y ⊆ R∗ , Pr[W(σ) ∈ Y] ≤ eε Pr[W(σ ′ ) ∈ Y] + δ, and Pr[W(σ ′ ) ∈ Y] ≤ eε Pr[W(σ) ∈ Y] + δ. 66
By Fact 3.18, the above inequalities are equivalent to X Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] z∈Z
≤ eε
X
Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z] + δ,
(26)
z∈Z
and
X
Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z]
z∈Z
≤ eε
X
Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] + δ,
(27)
z∈Z
By Lemma 3.20, Pr[⌈U ⌉ ≥ −
δ 2 ln(1/δ) 1 ε 2 ln(1/δ) =1− , ] ≥ 1 − e− 2 · ε ε 2 2
which combined with the fact that probabilities are non-negative implies X Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] z≥−2 ln(1/δ)/ε−1
≤
X
Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z]
z∈Z
X
≤
z≥−2 ln(1/δ)/ε
δ Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] + , 2
and X
Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z]
z≥−2 ln(1/δ)/ε+1
≤
X
Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z]
z∈Z
≤
X z≥−2 ln(1/δ)/ε
δ Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z] + . 2
Hence, to show Inequalities 26 and 27 and complete the proof, it suffices to prove δ Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] + 2 z≥−2 ln(1/δ)/ε X ≤ eε Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z] + δ, X
(28)
z≥−2 ln(1/δ)/ε+1
and
δ Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z] + 2 z≥−2 ln(1/δ)/ε X ≤ eε Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] + δ. X
z≥−2 ln(1/δ)/ε−1
Since U ∼ Lap(2/ε), the Laplace distribution satisfies ε Pr ⌈U ⌉ = z ≥ e− 2 Pr ⌈U ⌉ = z + 1 , and
ε Pr ⌈U ⌉ = z + 1 ≥ e− 2 Pr ⌈U ⌉ = z .
67
(29)
Therefore, to prove Inequalities 28 and 29, it suffices to show X Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] z≥−2 ln(1/δ)/ε
≤ eε/2
X
z≥−2 ln(1/δ)/ε+1
δ Pr ⌈U ⌉ = z − 1 · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z] + , 2
and X
Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z]
z≥−2 ln(1/δ)/ε
≤ eε/2
X
z≥−2 ln(1/δ)/ε−1
δ Pr ⌈U ⌉ = z + 1 · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] + . 2
By shifting the variable z in the right-hand sides, we must equivalently show X Pr ⌈U ⌉ = z · Pr[W(σ) ∈ Y | ⌈U ⌉ = z] z≥−2 ln(1/δ)/ε
≤ eε/2
X
δ Pr ⌈U ⌉ = z ·Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z+1]+ , 2
(30)
z≥−2 ln(1/δ)/ε
and
X
Pr ⌈U ⌉ = z · Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z]
z≥−2 ln(1/δ)/ε
≤ eε/2
X
δ Pr ⌈U ⌉ = z ·Pr[W(σ) ∈ Y | ⌈U ⌉ = z −1]+ . 2
(31)
z≥−2 ln(1/δ)/ε
We will show that for every z ≥ −2 ln(1/δ)/ε, the following inequalities hold: δ Pr[W(σ) ∈ Y | ⌈U ⌉ = z] ≤ eε/2 Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z + 1] + , 2
(32)
and
δ (33) Pr[W(σ ′ ) ∈ Y | ⌈U ⌉ = z] ≤ eε/2 Pr[W(σ) ∈ Y | ⌈U ⌉ = z − 1] + . 2 Multiplying Inequalities 32 and 33 by Pr ⌈U ⌉ = z , summing over all integers z ≥ −2 ln(1/δ)/ε, and applying the fact that X δ δ δ Pr ⌈U ⌉ = z · = Pr[⌈U ⌉ ≥ −2 ln(1/δ)/ε] · < 2 2 2 z≥−2 ln(1/δ)/ε
yield Inequalities 30 and 31. It remains to show Inequalities 32 and 33 hold. Fix any z ≥ −2 ln(1/δ)/ε. For every ⌈U ⌉ ∈ {z − 1, z, z + 1}, we have ⌈U ⌉ ≥ −2 ln(1/δ)/ε − 1, and thus the padding size C satisfies C = max {0, 1 + 2 ln(1/δ)/ε + ⌈U ⌉} = 1 + 2 ln(1/δ)/ε + ⌈U ⌉. Consider Inequality 32. Conditioned on ⌈U ⌉ = z and given σ = (x1 , . . . , xT +1 ) as input, W feeds the following stream to ECC: 2 ln(1/δ) + z, ε Moreover, conditioned on ⌈U ⌉ = z + 1 and given σ ′ = (x′1 , . . . , xT ) as input, W feeds the following stream to ECC: ′ 2 ln(1/δ) τ ′ = (x′1 , . . . , x′T ) · ⊥c , c′ = 1 + + z + 1. ε ′ ′ Since T = T + 1, by Definition D.1, we have xt = xt−1 for all t ∈ {i + 1, . . . , T + 1}. Since c′ ≥ 1, we also know that x′T +1 = ⊥. Comparing this with Definition 3.11 implies that the padded sequences τ and τ ′ are edit neighbors. Therefore, by Theorem 4.8 and the choice of privacy parameters for ECC, the distributions of the output sequences of ECC on τ and τ ′ are (ε/2, δ/2)-indistinguishable, which immediately implies Inequality 32. The proof of Inequality 33 follows by an identical argument. τ = (x1 , . . . , xT +1 ) · ⊥c ,
c=1+
68
Lemma D.3. Let W be the wrapping mechanism described above with privacy parameters ε > 0 and 0 < δ ≤ 1, constructed using a continual counter ECC that for any given input stream x′ , with probability 1 − β for all t ≥ 1, incurs additive error EECC (x′ , t) at time-step t. Let T ∈ N and σ = (x1 , . . . , xT ) ∈ [0, 1]T . Then, with probability at least 1 − β − δ/2, the following conditions hold: 1. The mechanism W generates T ∗ outputs (y1 , . . . , yT ∗ ), where T ∗ ∈ {T, T + 1, . . . , T + 1 + 4⌈ln(1/δ)/ε⌉}. Pt ∗ ∗ 2. For t ∈ [T ∗ ], define st = i=1 xi , where xi = 0 for i ∈ {T + 1, . . . , T }. For all t ∈ [T ], C |st − yt | ≤ EECC (σ · ⊥ , t). Proof. 1. From the Laplace tail bound on the random variable U , we have that with probability 1 − δ/2, U ≤ ⌈2 ln(1/δ)/ε⌉. It follows that when W encounters $, it sets C ≤ 1 + 4⌈ln(1/δ)/ε⌉ with probability 1 − δ/2. The claim follows. 2. We see that on the first T steps of the stream σ · ⊥C , the output of W is identical to the output of ECC on σ. For t ∈ [T + 1, T ∗ ], we see that st = sT , and from the accuracy guarantee of ECC, with probability 1 − β, for all t ≥ 1, |yt − st | ≤ EECC (σ · ⊥C , t).
69