Count on Your Elders: Laplace vs Gaussian Noise

Andersson, Joel Daniel; Pagh, Rasmus; Steiner, Teresa Anna; Torkamani, Sahel

doi:10.4230/LIPIcs.FORC.2025.10

Count on Your Elders: Laplace vs Gaussian Noise

Joel Daniel Andersson

BARC, University of Copenhagen, Copenhagen, Denmark Rasmus Pagh

BARC, University of Copenhagen, Copenhagen, Denmark Teresa Anna Steiner

University of Southern Denmark, Odense, Denmark Sahel Torkamani

University of Edinburgh, Edinburgh, United Kingdom

Abstract

In recent years, Gaussian noise has become a popular tool in differentially private algorithms, often replacing Laplace noise which dominated the early literature on differential privacy. Gaussian noise is the standard approach to approximate differential privacy, often resulting in much higher utility than traditional (pure) differential privacy mechanisms. In this paper we argue that Laplace noise may in fact be preferable to Gaussian noise in many settings, in particular when we seek to achieve $(\varepsilon,\delta)$ -differential privacy for small values of $\delta$ . We consider two scenarios:

First, we consider the problem of counting under continual observation and present a new generalization of the binary tree mechanism that uses a $k$ -ary number system with negative digits to improve the privacy-accuracy trade-off. Our mechanism uses Laplace noise and whenever $\delta$ is sufficiently small it improves the mean squared error over the best possible $(\varepsilon,\delta)$ -differentially private factorization mechanisms based on Gaussian noise. Specifically, using $k=19$ we get an asymptotic improvement over the bound given in the work by Henzinger, Upadhyay and Upadhyay (SODA 2023) when $\delta=O(T^{-0.92})$ .

Second, we show that the noise added by the Gaussian mechanism can always be replaced by Laplace noise of comparable variance for the same $(\varepsilon,\delta)$ -differential privacy guarantee, and in fact for sufficiently small $\delta$ the variance of the Laplace noise becomes strictly better. This challenges the conventional wisdom that Gaussian noise should be used for high-dimensional noise.

Finally, we study whether counting under continual observation may be easier in an average-case sense than in a worst-case sense. We show that, under pure differential privacy, the expected worst-case error for a random input must be $\Omega(\log(T)/\varepsilon)$ , matching the known lower bound for worst-case inputs.

Keywords and phrases:

differential privacy, continual observation, streaming, prefix sums, trees

Funding:

Joel Daniel Andersson: Supported by a Data Science Distinguished Investigator grant from the Novo Nordisk Fonden and VILLUM FONDEN grant 54451.

Rasmus Pagh: Supported by a Data Science Distinguished Investigator grant from the Novo Nordisk Fonden and VILLUM FONDEN grant 54451.

Teresa Anna Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN.

Copyright and License:

2012 ACM Subject Classification:

Security and privacy

\rightarrow

Privacy-preserving protocols

Related Version:

Full Version: https://arxiv.org/abs/2408.07021

Earlier Version: https://arxiv.org/abs/2408.07021v1 [3]

Acknowledgements:

We are grateful to Monika Henzinger and Jalaj Upadhyay for discussions on continual counting that inspired part of this work.

DOI:

10.4230/LIPIcs.FORC.2025.10

Event:

6th Symposium on Foundations of Responsible Computing (FORC 2025)

Editors:

Mark Bun

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In private data analysis the goal is to release the result of computations on datasets while safeguarding the privacy of the individuals whose data make up the dataset. A popular framework for achieving this is differential privacy [17], which gives probabilistic guarantees on how much can be learned about an individual’s data from the result of a computation. Algorithms providing differential privacy (DP) guarantees conceptually introduce noise, randomly perturbing the result of a corresponding exact, non-private computation. The trade-off between utility and privacy guarantees depends on the nature of the computation.

Let $\mathbf{x},\mathbf{x}^{\prime}\in\{0,1\}^{T}$ be input datasets. We say $\mathbf{x}$ and $\mathbf{x}^{\prime}$ are neighboring if they are equal except for a single bit. We want to compute all prefix sums of $\mathbf{x}$ with differential privacy under this neighboring relation, i.e., we want to privately release $A\mathbf{x}$ where $A$ is the lower-triangular all 1s matrix. If we add the restriction that the bits $\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{T}$ are received one by one as a stream, and we are to output $(A\mathbf{x})_{i}$ on receiving $\mathbf{x}_{i}$ , then this problem is referred to as counting under continual observation or continual counting for short [18, 8].

The standard solution to this problem is the factorization mechanism [35], and it involves (1) factorizing $A$ into matrices $L, R$ such that $A=LR$ , (2) privately releasing $R\mathbf{x}$ by adding noise $\mathbf{z}$ and then (3) multiplying the private release by $L$ from the left: $L(R\mathbf{x}+\mathbf{z})=A\mathbf{x}+L\mathbf{z}$ . Defining the $\ell_{p}$ sensitivity as $\Delta_{p}=\max_{i\in[T]}\left\lVert R\mathbf{e}_{i}\right\rVert_{p}$ , where $\mathbf{e}_{i}$ is the $i$ ^th unit basis vector, classical results on DP say that adding Laplace noise scaled to $\Delta_{1}$ yields $\varepsilon$ -DP (also called pure DP), and adding Gaussian noise scaled to $\Delta_{2}$ yields $(\varepsilon,\delta)$ -DP (also called approximate DP). The scheme rests on the observation that while the sensitivity of $A$ may be large, the sensitivity of $R$ can be much smaller, and so adding noise $L\mathbf{z}$ to the final result may result in better accuracy than adding noise directly to $A\mathbf{x}$ .

While continual counting is a deceptively simple problem, we note that it still has significant gaps between upper and lower bounds [18, 29, 21, 19, 11]. The problem is used as a subroutine in various applications ranging from private learning [37, 33, 10, 14, 9] to histogram estimation [6, 7, 32, 41], so any improvement in upper bounds affect these applications.

1.1 Our contributions

Our first contribution is an easy-to-implement tree-aggregation-based mechanism for continual counting under $\varepsilon$ -DP, and based on Laplace noise, with properties stated in Theorem 1.

Theorem 1.

Given a constant odd integer $k\geq 3$ and integer $T\geq 2$ , there exists an $\varepsilon$ -DP algorithm for continual counting that for a stream $\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{T}$ achieves mean squared error $\frac{k(1-1/k^{2})}{2\varepsilon^{2}\log(k)^{3}}\cdot\log(T)^{3}+o(\log(T)^{3})$ , computing all outputs in time $O(T)$ and space $O(\log T)$ .

We denote the base $k$ logarithm by $\log_{k}$ , and define $\log(\cdot)=\log_{2}(\cdot)$ . To the best of our knowledge, this is the best bound on the mean squared error known for any $\varepsilon$ -DP mechanism, up to lower-order asymptotically vanishing terms. It improves the error achieved by applying techniques in [31] to the binary tree mechanism (as implemented in [33] and referred to elsewhere as “Honaker Online”) by a factor 4 when $k=19$ . While this is interesting in its own right, we note that this improvement in the leading constant has implications for how the error compares to $(\varepsilon,\delta)$ -DP mechanisms. Henzinger, Upadhyay and Upadhyay [29] produce a factorization with a bound on the mean squared error of $C_{\varepsilon,\delta}^{2}\big{(}1+\frac{\ln(4T/5)}{\pi}\big{)}^{2}$ , where $C_{\varepsilon,\delta}=\frac{2}{\varepsilon}\sqrt{\frac{4}{9}+\ln\big{(}\frac{% 1}{\delta}\sqrt{\frac{2}{\pi}}\big{)}}$ , and show that no factorization mechanism based on Gaussian noise can asymptotically improve on this error.¹¹1As the constant $C_{\varepsilon,\delta}$ is valid for all $\varepsilon,\delta\in(0,1)$ , it seems plausible that it can be reduced via a tighter analysis of the Gaussian mechanism, as done in for example [4]. We improve on their error using Laplace noise for small enough $\delta$ .

Theorem 2.

Given an integer $T\geq 2$ , there exists an $\varepsilon$ -DP algorithm for continual counting, based on Laplace noise, that improves on the mean squared error bound given in [29], up to lower-order asymptotically vanishing terms, whenever $\delta=O(T^{-0.92})$ .

Given that $\delta$ is commonly set to be $o(1/T)$ , this result is surprising. The phenomenon is discussed in Section 5, but in a nutshell a sufficiently small $\delta$ must cause the error to greatly increase if the mechanism is based on Gaussian noise. While improving constants for $\varepsilon$ -DP is of independent interest, Theorem 2 implies that further improvements also have implications for $(\varepsilon,\delta)$ -DP.

Motivated by the dominance of Gaussian noise in applications, and the moral in Theorem 2 for Laplace noise, our second contribution is $(\varepsilon,\delta)$ -DP guarantees for the Laplace mechanism for given $\ell_{1}$ and $\ell_{2}$ sensitivities.

Theorem 3 (Approximate DP for the Laplace Mechanism).

Let $f:\mathcal{X}^{n}\to\mathbb{R}^{d}$ be a function with $\ell_{p}$ -sensitivity $\Delta_{p}\coloneqq\max_{\mathcal{D}\sim\mathcal{D}^{\prime}}\left\lVert f(% \mathcal{D})-f(\mathcal{D}^{\prime})\right\rVert_{p}$ . For a given dataset $\mathcal{D}\in\mathcal{X}^{n}$ , $\delta\in(0,1)$ and $\lambda>\Delta_{1}$ , the output $f(\mathcal{D})+\mathsf{Lap}(\lambda)^{d}$ , satisfies $(\varepsilon,\delta)$ -differential privacy where

\varepsilon=\min\bigg{\{}\frac{\Delta_{1}}{\lambda},\frac{\Delta_{2}}{\lambda}% \bigg{(}\frac{\Delta_{2}}{2\lambda}+\sqrt{2\ln(1/\delta)}\bigg{)}\bigg{\}}\,.

Essentially we can implement $(\varepsilon,\delta)$ -DP for the Laplace mechanism where the resulting $\varepsilon$ is never worse than what simple composition gives, while also being competitive with the Gaussian mechanism in the regime where it is advantageous.

Finally, in Appendix D we show the following lower bound, which matches the classical packing lower bound for continual observation under pure differential privacy [18, 20] in the case where the input is random.

Theorem 4.

Let $\mathcal{U}$ be the distribution of strings of length $T$ where every element in the string is drawn from $B(1/2)$ (Bernoulli distribution with $p=1/2$ ). Let $\mathcal{M}$ be an $\varepsilon$ -differentially private algorithm that solves the continual counting problem for strings from $\mathcal{U}$ with error at most $\alpha$ with probability at least $3/4$ (probability over random input and random choices of the algorithm). Then $\alpha=\Omega(\varepsilon^{-1}\log T)$ .

1.2 Overview of technical ideas

Improved tree-based mechanism

We start out by building a complete $k$ -ary tree of height $h=\lceil\log_{k}(T+1)\rceil$ on top of the input $\mathbf{x}\in\{0,1\}^{T}$ , see Figure 1. To analyze this, it turns out that expressing a time step $t$ as a $k$ -ary number, i.e., as $h$ digits in $\{0,\dots,k-1\}$ , i.e. $\mathbf{t}\in\{0,\dots,k-1\}^{h}$ , gives a direct means of computing which vertices contribute to a given prefix sum. Increasing the arity of the tree reduces the height, which reduces the $\ell_{1}$ -sensitivity and levels of vertices that might get added, but increases the number of vertices to add per level. To mitigate the increase in number of vertices to add, we leverage subtraction, see Figure 2.

To analyze the structure of the resulting prefix sums when subtraction is introduced, it turns out that rather than expressing $t$ in digits from $0$ to $k-1$ , we should instead allow for negative digits. Focusing on the case of odd $k$ , we thus represent $t$ as $\mathbf{t}\in\{-\frac{k-1}{2},\dots,\frac{k-1}{2}\}^{h}$ . The interpretation of $\mathbf{t}$ becomes: if $\mathbf{t}_{\ell}\geq 0$ , add $\mathbf{t}_{\ell}$ leftmost children on level $\ell$ , otherwise, subtract $|\mathbf{t}_{\ell}|$ rightmost children on level $\ell$ . Identifying that $\left\lVert\mathbf{t}\right\rVert_{1}$ is equal to the number of vertices used to produce the estimate at time $t$ , we can analyze the average number of vertices added for an estimate from this representation by studying $\mathbf{t}$ for $t\in[1,T]$ . This gives, roughly, a factor-2 reduction in the mean squared error versus not using subtraction.

Figure 1: Complete 5-ary tree with 25 leaves containing inputs

\mathbf{x}_{1},\dots,\mathbf{x}_{25}

and inner vertices containing subtree sums. To compute the sum of the first 24 inputs we can add 4 inner vertices and 4 leaves (shown in green) – in general, the worst-case number of vertices for

k

-ary trees is

k-1

per level. When subtree sums are made private by random (Laplace) noise the variance of a prefix sum estimator is proportional to the number of terms added. In Section 3.2 we analyze the privacy and utility of this natural generalization of the binary tree mechanism to

k

-ary trees, among other things showing that the mean number of terms is about half of the worst case.

(a) Prefix sum with only vertex addition.

(b) Prefix sum with vertex subtraction.

Figure 2: Complete ternary trees, each with 9 leaves containing inputs

x_{1},\dots,x_{9}

and inner vertices containing subtree sums. The trees illustrate two different possibilities for computing the sum of the first 8 inputs: (2(a)) add two inner vertices and two leaf vertices, or (2(b)) subtract one vertex (shown in red) from the sum stored in the root vertex (shown in green). The variance of using the latter method, with subtraction, is half of the former method, assuming the noise distribution for each vertex is the same. In Section 3.3 we analyze the privacy and utility of our new generalization of the binary tree mechanism to

k

-ary trees that makes use of subtraction. Among other things we show that the worst-case number of terms needed per level is

\lfloor k/2\rfloor

, and the mean number of terms is about half of the worst case.

Factorization mechanism with Laplace noise

To derive the $(\varepsilon,\delta)$ -DP guarantee of the Laplace mechanism (Theorem 3), we make use of a heterogeneous composition theorem [34]. Given two arbitrary multidimensional neighboring inputs, we argue for the privacy loss in each coordinate when one of them is released with respect to its neighbor. To get the aggregate privacy guarantee for the entire vector, we apply the composition theorem over the individual coordinates being released, and show that the guarantee must hold for any two neighboring outputs. It turns out that, as in the case of the Gaussian mechanism, the $(\varepsilon,\delta)$ -DP guarantee for Laplace noise naturally depends on the $\ell_{2}$ -sensitivity of the function being released.

Lower bound for random inputs

Finally, the lower bound of Theorem 4 is shown by a variation of the packing argument that has been used to show an $\Omega(\log(T)/\varepsilon)$ lower bound for worst-case inputs. The core idea is to construct a set of correlated input strings that are individually close to uniformly random, but a continual observation mechanism that has low maximum error on all of them would be able to reliably distinguish these input strings. More precisely, for integers $T$ , $B$ , $m=T/B$ and $k\leq B/4$ , we construct our collection of strings $\mathbf{x}^{(0)},\mathbf{x}^{(1)},\dots,\mathbf{x}^{(m)}$ by first decomposing $[T]$ into blocks of size $B:B_{1}=[1,B],B_{2}=[B+1,2B],\dots,B_{m}=[T-B+1,T]$ and then doing the following sampling process: $\mathbf{x}^{(0)}$ is sampled uniformly from $\{0,1\}^{T}$ conditioned on each block $B_{i}$ containing between $B/4$ and $3B/4$ 1s, and for $i\in[m]$ , $\mathbf{x}^{(i)}$ is derived from $\mathbf{x}^{(0)}$ by flipping $k$ 0s to 1s in block $B_{i}$ . We show that each individual string has $o(1)$ total variation distance to the uniform distribution over $\{0,1\}^{T}$ , and thus a mechanism accurate on the uniform distribution will also be accurate on our random strings. Also, pairs of our random strings will be $2k$ -neighboring with probability 1. The key insight is that the difference of the true count of $\mathbf{x}^{(i)}$ minus $\mathbf{x}^{(0)}$ is $k$ at the end of $B_{i}$ , and zero at the end of each preceding $B_{j}$ for $j<i$ , and this event is detectable if the mechanism is sufficiently accurate on both inputs. Choosing parameters carefully, a packing-like argument in the end shows that a too low error on uniformly distributed inputs contradicts differential privacy.

1.3 Related work

Throughout this section, we focus on unbiased mechanisms for continual counting with “good error”. Here “error” is a shorthand for mean squared error over $T$ outputs, and “good” is an error of $O(\log(T)^{3})$ for $\varepsilon$ -DP mechanisms and $O(\log(T)^{2}\log(1/\delta))$ for $(\varepsilon,\delta)$ -DP mechanisms. We note that there exists some biased mechanisms [19], but they focus on reducing the error for sparse inputs and give no improvement for dense streams. Unless stated otherwise, constant factor improvements are always for $\varepsilon$ -DP.

Historically, the first mechanisms with good error are typically credited to Chan, Shi, and Song [8] and Dwork, Naor, Pitassi, and Rothblum [18], though similar constructions were proposed independently by others [25, 22]. These results are commonly referred to as binary tree mechanisms. Honaker [31] observed that the full tree used by the binary tree mechanism can be used to produce more efficient estimates since each prefix query can be computed using different combinations of vertices. A subset of Honaker’s techniques can be used to reduce the mean squared error by up to a factor 2, at some cost in efficiency. Rather than leveraging the density of the tree to improve the error, Andersson and Pagh [1] identified that making the tree sparser – only using a subset of the leaves to store inputs – allowed for a factor 2 reduction in the error while keeping the variance of outputs constant, for $(\varepsilon,\delta)$ -DP. Although they do not state a result for it, using their technique for $\varepsilon$ -DP yields a factor 4 improvement over the binary tree mechanism, which is still more than a factor 2 away from our improvement. We also mention the work of Qardaji, Yang, and Li [38] which, while focusing on range queries, did investigate reducing the mean squared error by means of considering trees of higher arity. They claim an optimal arity of $k=16$ , but average over a different set of queries, and do not leverage the subtraction of vertices. Cardoso and Rogers [6] used $k$ -ary trees for prefix sums as a subroutine for $(\varepsilon,\delta)$ -DP and investigated choosing $k$ to minimize the maximum variance.

Many recent papers [26, 2, 28, 16, 14, 29, 21] have focused on improving the error for continual counting for $(\varepsilon,\delta)$ -DP by directly searching among factorizations of $A$ , the lower-triangular all-1s matrix. Most notably, Henzinger, Upadhyay, and Upadhyay [29] showed that there exists a near-optimal factorization $L=R=\sqrt{A}$ (also identified by Bennett [5]) whose error is optimal up to the leading constant across all factorizations. But, importantly, this is for $(\varepsilon,\delta)$ -DP and assumes using Gaussian noise. Due to the high $\ell_{1}$ sensitivity of $R=\sqrt{A}$ , the noise needed to release $R\mathbf{x}$ with the (conventional) Laplace mechanism results in an $\varepsilon$ -DP matrix mechanism with worse error than that of the binary mechanism.

The second part of our paper explores the use of Laplace noise for $(\varepsilon,\delta)$ -DP, especially in the small $\delta$ regime – a regime we are not the first to investigate [40]. We claim no novelty in pointing out that the Gaussian mechanism scales poorly for small $\delta$ (see e.g. [15]). We do note that there is a rich literature investigating alternative (non-Gaussian) noise distribution for approximate DP [24, 30, 36, 13, 23, 42]. In [39] they compare how Laplace and Gaussian noise behaves over many compositions, and especially observe that eventually they will both converge to Gaussian privacy loss distributions.

Finally, we turn to lower bounds. While [29] recently established a $\Omega(\log(T)^{2})$ lower bound on the mean squared error, the strongest known lower bound for $\ell_{\infty}$ error remains the $\Omega(\log T)$ result of [18]. The hard inputs in [18] (see the proof in [20] for details) are very sparse vectors with a single block of 1s that can be reliably distinguished by any algorithm that outputs prefix sums with noise significantly smaller than the block size, yet are close to each other in neighbor distance. This structure means that a “packing argument” can be used to show a lower bound on the amount of noise needed. One might wonder if most inputs are easier and allow a smaller error – our lower bound shows that this is not the case. Some algorithmic problems have the property that worst-case problem instances can be reduced to random instances (for example [27]). Though we are not aware of such a reduction for continual counting, our lower bound can be seen as an instantiation of this general principle.

2 Preliminaries

Before introducing any mechanism, we first introduce some notation and background. We use $\mathbb{N}$ to denote all positive integers, and for $a,b\in\mathbb{N}$ let $[a,b]\subset\mathbb{N}$ refer to the set of integers $\{a,a+1\dots,b\}$ . A vector-valued quantity $\mathbf{y}\in\mathbb{R}^{n}$ is expressed in bold notation and its scalar entries are written as $\mathbf{y}_{i}$ for $i\in[1,n]$ . Standard definitions for $\varepsilon$ -DP and $(\varepsilon,\delta)$ -DP are given in Appendix A.

As the main goal of this paper is the study and design of differentially private algorithms for counting queries, we will first formalize the problem. Let vector $\mathbf{x}\in\{0,1\}^{T}$ be an input stream, where $\mathbf{x}_{t}$ is received at time $t$ . Then, two input streams $\mathbf{x},\mathbf{x}^{\prime}$ are neighboring inputs, denoted $\mathbf{x}\sim\mathbf{x}^{\prime}$ , if they take on the same value at every time step except one. The target function we wish to privately release is $f:\{0,1\}^{T}\to\mathbb{R}^{T}$ where $f(\mathbf{x})_{t}=\sum_{i=1}^{t}\mathbf{x}_{i}$ . We say that a random algorithm $\mathcal{M}:\{0,1\}^{T}\to\mathbb{R}^{T}$ is a differentially private mechanism for continual counting if it satisfies either $\varepsilon$ -DP or $(\varepsilon,\delta)$ -DP under this neighboring relation.

For the entirety of this paper, we will express the utility of an algorithm in terms of its mean squared error defined as: $\operatorname{MSE}(\mathcal{M},\mathbf{x})=\frac{1}{T}\operatorname{\mathbb{E}% }\big{[}\left\lVert\mathcal{M}(x)-f(x)\right\rVert_{2}^{2}\big{]}=\frac{1}{T}% \sum_{t=1}^{T}\operatorname{Var}[\mathcal{M}(\mathbf{x})_{t}]\,,$ where the second equality only holds if $\forall\mathbf{x}\in\{0,1\}^{T}:\operatorname{\mathbb{E}}[\mathcal{M}(\mathbf{% x})]=f(\mathbf{x})$ , which is the case for all factorization mechanisms in general, and all mechanisms covered in this work in particular. That is to say, for unbiased mechanisms $\mathcal{M}$ , their mean squared error will be equal to the average variance. Moving forward, any mention of error without further qualification will refer to the mean squared error.

3 Mechanisms

In this section, we will gradually build up towards the algorithm outlined in Theorem 1. We begin by describing the binary tree mechanism, which will be our starting point. Then we will consider how the utility improves when we extend to $k$ -ary trees, and we give an algorithm and results for this case. Finally, our main contribution will be to incorporate subtraction of vertices in $k$ -ary trees to further improve the utility. The formal proofs leading to Theorem 1 are given in the next section.

3.1 Binary Tree Mechanisms

The first algorithms [8, 18, 22, 25] with good utility are based on binary trees and are referred to as the binary tree mechanism. Implementation details vary, but we will consider a formulation of it where only the left subtrees are used, and in particular not the root vertex, structurally most similar to Algorithm 2 in [8]. The main idea for the algorithm is to build a binary tree of height $h=\lceil\log(T+1)\rceil$ on top of the input stream $\mathbf{x}$ where each leaf stores an input $\mathbf{x}_{t}$ , and each vertex higher up in the tree stores the sum of its children. Having such a tree, it is possible to add together vertices in the tree in such a way that at most $1$ vertex per level in the tree is used, up to $h$ in total, where the sum corresponds to a prefix sum up to $t\in[1,T]$ . In particular, which vertices that get summed to produce a given prefix sum is described exactly by the $h$ -bit binary representation of the current time step, where each $1$ corresponds to adding a vertex in the tree to the output. To make this private, we add i.i.d. Laplace noise $\mathsf{Lap}(\Delta_{1}/\varepsilon)$ to each vertex in the tree, where $\Delta_{1}=h$ since the trees for two neighboring inputs will differ in one vertex per level, excluding the root which is not used in computations. We defer making exact statements about the corresponding utility to Section 3.2, where this description of the binary tree mechanisms is a special case of Algorithm 1 for $k=2$ .

3.2 $𝒌$ -ary Tree Mechanisms

We will next consider trees of greater arity $k\geq 2$ to improve constants for the error. We note that using trees of higher arity has already been studied [38, 12, 6]. With a greater arity tree, a lesser height is needed to accommodate a given number of leaves. However, it might also require adding more vertices per level to generate a given prefix sum estimate. To explore this trade-off, we introduce notation for $k$ -ary trees next.

Definition 5 ( $k$ -ary trees).

For integers $k\geq 2$ and $h\geq 1$ , we define a $k$ -ary tree of height $h$ with $k^{h}$ leaves as $\mathcal{T}_{k,h}$ . Then for integer $1\leq\ell\leq h+1$ , let $\mathcal{T}_{k,h}^{\ell}=\{[1+j\cdot k^{\ell-1},(j+1)\cdot k^{\ell-1}]:j\in% \mathbb{N},\,0\leq j<k^{h-\ell+1}\}$ be the set of vertices on level $\ell$ , where a vertex $I\in\mathcal{T}_{k,h}^{\ell}$ is a child of $I^{\prime}\in\mathcal{T}_{k,h}^{\ell+1}$ if $I\subset I^{\prime}$ , and where $\mathcal{T}_{k,h}=\bigcup_{1\leq\ell\leq h+1}\mathcal{T}^{\ell}_{k,h}$ .

Additionally, let $\Sigma(I)=\sum_{i\in I}\mathbf{x}_{i}$ for $I\in\mathcal{T}_{k}$ when such a tree is used to store partial sums on $\mathbf{x}$ , $\widehat{\Sigma}$ for the case where a vertex in the tree stores a partial sum, plus independent noise. Also, we will find it expedient to express integers using $k$ -ary digits, which we define next.

Definition 6 ( $k$ -ary representation of integer).

Let $k$ , $w$ and $t\leq k^{w}-1$ be positive integers. We then define $\mathbf{t}=\operatorname{\mathsf{rep}}_{k}(t,w)\in[0,k-1]^{w}$ as the unique vector in $[0,k-1]^{w}$ satisfying $\sum_{i=1}^{w}k^{i-1}\mathbf{t}_{i}=t$ .

The intuition behind using $k$ -ary to analyze $k$ -ary tree mechanisms is the same as in the case where $k=2$ – there is a clean analogue between the two. The $h$ -digit $k$ -ary representation of a time step $t$ , $\mathbf{t}=\operatorname{\mathsf{rep}}_{k}(t,h)$ , encodes a set of vertices in $\mathcal{T}_{k,h}$ whose sum (when interpreted as partial sums) equals the prefix sum up to $t$ . In particular, $\mathbf{t}_{\ell}$ gives the number of vertices that get added at level $\ell$ of the tree. With this observation in mind, we introduce Algorithm 1.

Algorithm 1

k

-ary Tree Mechanism.

Now we state the properties of Algorithm 1. We begin by discussing the privacy of the output of the algorithm. Subsequently, we examine the variance and average number of used vertices to analyze the mean squared error. Finally, we analyze the time and space complexity of the algorithm.

Lemma 7.

The output from Algorithm 1 satisfies $\varepsilon$ -DP.

Proof.

Note that line 11 always adds the noisy count from a vertex in the tree at level $\ell\in[1,h]$ since $p=p_{n}\overset{\pmod{k^{\ell-1}}}{=}0$ , and since $\mathbf{t}$ is a valid representation of a time step $t\leq T$ , we also have $p\leq t$ , and so the vertex must be contained in the tree. Note further that everything after line 4 can be considered post-processing of privately releasing the tree $\mathcal{T}_{k,h}$ storing partial sums. Since we never use the root vertex of the tree at level $h+1$ , any two neighboring inputs will differ at exactly $h$ vertices which we use, therefore $\Delta_{1}=h$ , implying that releasing the individual counts in the tree with $\mathsf{Lap}(h/\varepsilon)$ gives privacy. $\hfill\blacktriangleleft$ For the utility, note that the output from Algorithm 1 at time $t$ has variance $(2h^{2}/\varepsilon^{2})\cdot\left\lVert\operatorname{\mathsf{rep}}_{k}(t,h)% \right\rVert_{1}$ , since $\left\lVert\operatorname{\mathsf{rep}}_{k}(t,h)\right\rVert_{1}$ vertices with variance $(2h^{2}/\varepsilon^{2})$ are added up. Consequently, we can conclude this subsection with the following Lemma and Theorem.

Lemma 8.

Algorithm 1 achieves a mean squared error of $\frac{(k-1)h^{3}}{\varepsilon^{2}(1-1/k^{h})}$ over $T=k^{h}-1$ outputs.

Proof.

Identifying that the mean squared error over $T$ steps is equal to the average number of vertices added together to produce an output, call this number $a_{[1,T]}$ , times the variance of each vertex, $2h^{2}/\varepsilon^{2}$ . Observe that $a_{[1,T]}=\frac{1}{T}\sum_{t=1}^{T}\left\lVert\operatorname{\mathsf{rep}}_{k}(% t,h)\right\rVert_{1}$ and that $T$ is the greatest integer possible to represent with $h$ digits from $\{0,1,\dots,k-1\}$ . This implies that we can compute the average $\ell_{1}$ -weight over $\{0,1,\dots,k-1\}^{h}$ , $a_{[0,T]}=h\cdot\frac{1}{k}\sum_{d=0}^{k-1}|d|=\frac{h(k-1)}{2}$ . Since $T\cdot a_{[1,T]}=(T+1)\cdot a_{[0,T]}$ , we have that $a_{[1,T]}=(1+1/T)\cdot a_{[0,T]}=\frac{h(k-1)}{2(1-1/k^{h})}$ . Plugging this in gives a mean squared error of $\frac{(k-1)h}{2(1-1/k^{h})}\cdot\frac{2h^{2}}{\varepsilon^{2}}=\frac{(k-1)h^{3% }}{\varepsilon^{2}(1-1/k^{h})}$ . $\hfill\blacktriangleleft$

Theorem 9.

Given integer $T\geq 2$ and constant integer $k\geq 2$ , there exists an $\varepsilon$ -DP mechanism for continual counting that on receiving a stream $\mathbf{x}_{1},\mathbf{x}_{2},\dots,\mathbf{x}_{T}$ achieves a mean squared error of $\frac{k-1}{\varepsilon^{2}\log(k)^{3}}\cdot\log(T)^{3}+o(\log(T)^{3})$ , computes all outputs in time $O(T)$ and $O(\log T)$ space.

As Theorem 9 is not our main contribution, we provide a proof sketch in Appendix B. Before continuing and including subtraction as a technique, we note that Theorem 9 describes the standard binary tree mechanism for $k=2$ , and that the leading constant in the error is minimized for $k=17$ , in which case it equals $\approx 0.234$ .

3.3 $𝒌$ -ary trees with subtraction

Next, we will investigate what further improvements are possible if we allow for the subtraction of vertices to produce outputs. The reason for doing so is rather simple: if you need to add $\geq\lceil k/2\rceil$ left-children for an estimate, you might as well add the parent and subtract the $\leq\lfloor k/2\rfloor$ right-most children. Figure 2 provides a visual example that further illustrates how incorporating vertex subtraction can effectively reduce the number of vertices required to compute the prefix sum. Intuitively this should buy us another factor 2 improvement, as instead of adding a maximum of $(k-1)$ vertices per level to produce an estimate, we should now instead combine at most $\lceil(k-1)/2\rceil$ .

To analyze (and efficiently implement) such a mechanism, the previous integer representation using digits in $[0,k-1]$ is no longer the natural choice. Instead, when we open up the possibility of subtracting vertices, the solution becomes to allow for negative digits.

Definition 10 (Offset $k$ -ary representation of integers).

Let $k$ , $w$ and $t$ be positive integers, with $k$ also being odd, satisfying $t\leq(k^{w}-1)/2$ . We then define $\mathbf{t}=\operatorname{\mathsf{\widehat{rep}}}_{k}(t,w)\in[-\frac{k-1}{2},% \frac{k-1}{2}]^{w}$ as the unique vector with integer entries in $[-\frac{k-1}{2},\frac{k-1}{2}]^{w}$ satisfying $\sum_{i=1}^{w}k^{i-1}\mathbf{t}_{i}=t$ .

We will return to the fact that Definition 10 only considers odd $k$ and first focus on providing intuition for why we are using offset digits. As in the case for $k$ -ary trees using only subtraction, there is a natural connection between $\mathbf{t}=\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)$ and vertices in $\mathcal{T}_{k,h}$ . Put simply: if $\mathbf{t}_{\ell}>0$ , then to produce the prefix sum for $t$ , we will be adding $\mathbf{t}_{\ell}\leq(k-1)/2$ left-most children from $\mathcal{T}_{k,h}^{\ell}$ , as in the case without addition except we add fewer vertices in the worst-case. If $\mathbf{t}_{\ell}<0$ , then we will instead subtract $|\mathbf{t}_{\ell}|\leq(k-1)/2$ right-most children from $\mathcal{T}_{k,h}^{\ell}$ . In either case, the worst-case number of vertices added or subtracted is reduced to being at most $(k-1)/2$ .

Now, we only consider the case of odd $k$ for a few reasons: (1) if $k$ is odd, then we have symmetry in the digits, meaning we add at worst as many things as we may subtract. This makes the analysis easier. (2) even $k$ is not optimal, see Appendix C for more details. (3) if $k$ is odd, then there is a simple relation for when the root vertex of a tree is used to produce an output: the root vertex is used if $t$ is in the right half of the tree. This gives an intuitive condition on the height to support $T$ inputs: $h=\lceil\log_{k}(2T)\rceil$ – set the height such that there is a sufficient number of left-half leaves. This can be compared to standard $k$ -ary trees, where the same condition is to use every leaf of the tree except the right-most one.

We are now ready to introduce our main contribution: Algorithm 2.

Algorithm 2

k

-ary Tree Mechanism with Subtraction.

Structurally the algorithm releases prefix sums with a correlation in the noise that depends on the representation $\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)$ of each time step $t$ .

4 Proving Theorem 1

In this section, we will prove the properties of Algorithm 2, as summarized in Theorem 1, starting with privacy.

4.1 Privacy

Instead of arguing about the privacy of Algorithm 2, we will argue it for another algorithm with the same output distribution, Algorithm 3, whose connection to trees is more immediate. We proceed by establishing the equivalence of the output distributions in Algorithms 2 and 3.

Algorithm 3 More tree-like version of Algorithm 2 for analysis.

The following proposition will be helpful in establishing that the outputs are identically distributed.

Proposition 11.

When iterating over $t$ , let $count_{n}$ and $p_{n}$ be the value of $c o u n t$ and $p$ after $1\leq n\leq\left\lVert\mathbf{t}\right\rVert_{1}$ updates in Algorithm 3. Then $count_{n}$ stores a noisy prefix sum up to $p_{n}\in[1,(k^{h}-1)/2]$ .

Proof.

We show this by induction on $n$ . Observe that $p_{n}\in[1,(k^{h}-1)/2]$ for all valid $n$ since the first non-zero digit in $\mathbf{t}$ has to be positive, and since the greatest possible integer we can represent in these digits is $(k^{h}-1)/2$ . We therefore have that $p_{1}\geq 1$ and $count_{1}=\widehat{\Sigma}[1,p]$ is a noisy prefix sum up to $\mathbf{x}_{p}$ . Assuming that after $n$ updates $c o u n t$ represents a noisy prefix sum up to $p$ , we will argue that this still holds after the $n+1$ ^st update to $p$ . Just before $c o u n t$ is updated, observe that $p=p_{n}\overset{\pmod{k^{\ell-1}}}{=}0$ , thus implying that the corresponding partial sums added or subtracted on lines 12 and 13 exist in the tree, and that the result will be a noisy prefix sum up to $p_{n+1}$ . $\hfill\blacktriangleleft$ We can now prove that the two algorithms produce identically distributed outputs.

Proposition 12.

The output distribution of Algorithms 2 and Algorithm 3 are equal.

Proof.

First, observe that Algorithm 3 like Algorithm 2 outputs the correct prefix sum on expectation which follows from Proposition 11 for $n=\left\lVert\mathbf{t}\right\rVert_{1}$ . We thus only have to argue for the equivalence of the noise added. With this target in mind, note that each time a vertex is used on lines 12 and 15 in Algorithm 3, it can be uniquely identified by the $p$ after it is updated on the next line. The uniqueness can be inferred from the uniqueness of expressing the corresponding $\mathbf{p}=\operatorname{\mathsf{\widehat{rep}}}_{k}(p,h)$ , where $p\in[1,(k^{h}-1)/2]$ can be interpreted as a time step. Following up, note that for any time step $t$ , the sequence of $p$ ’s that are computed on line 10 for Algorithm 2 are the same as the sequence of $p$ ’s obtained after lines 13 and 16 for Algorithm 3. Since Algorithm 2 explicitly indexes the noise terms by the same $p$ , and since each term is identically distributed across the algorithms, it follows that each individual noise term that is added to the output at each step is identical up to their sign.

What remains to account for is the lack of a factor “ $\operatorname{sgn}(\mathbf{e}_{\ell})$ ” on line 11 in Algorithm 2. The reason why it is not needed comes from the fact that a given vertex in Algorithm 3 always contributes with the same sign: we always subtract right-most children and always add left-most children to produce prefix sum estimates. Since Laplace noise is symmetric, subtracting or adding noise has the same effect, and we can therefore drop the sign on line 11 in Algorithm 2 and still have the same output distribution, proving the statement. $\hfill\blacktriangleleft$ We are now ready to prove that Algorithm 2 satisfies $\varepsilon$ -DP.

Lemma 13.

Algorithm 2 satisfies $\varepsilon$ -DP.

Proof.

We proceed by proving the privacy of Algorithm 3, the privacy of which implies the privacy of Algorithm 2 in the offline setting via Proposition 12. The privacy proof is standard and follows from identifying that if all $\widehat{\Sigma}(I)$ on line 4 are released privately, then the remaining computations are a post-processing of that release. For neighboring inputs $\mathbf{x}^{\prime}\sim\mathbf{x}$ , let $i$ be the index at which they differ. Let $\mathbf{y}\in\mathbb{R}^{|\mathcal{T}_{k,h}|}$ be a vector where each entry is identified by a unique interval from $I\in\mathcal{T}_{k,h}$ equal to $\Sigma(I)$ given $\mathbf{x}$ . Define $\mathbf{y}^{\prime}$ analogously for $\mathbf{x}^{\prime}$ . Since any $i\in[1,T]$ is included in exactly $h$ intervals $I\in\mathcal{T}$ , intentionally excluding the root vertex which is not used, it follows that the sensitivity for releasing $\mathbf{y}$ is $\Delta_{1}=\left\lVert\mathbf{y}-\mathbf{y}^{\prime}\right\rVert_{1}=h$ . As $\mathbf{y}$ is released on line 4 using the Laplace mechanism with appropriate scale, and all computations afterward are post-processing of $y$ , Algorithm 3 satisfies $\varepsilon$ -DP.

To extend the privacy analysis to the online case where $\mathbf{x}$ is streamed (non-adaptively), note that the output distribution of Algorithm 2 can be expressed as $A\mathbf{x}+L\mathbf{z}$ for suitable matrices $A, L$ . On receiving $\mathbf{x}_{t}$ , $(A\mathbf{x})_{t}+(L\mathbf{z})_{t}$ is output. Since $L\mathbf{z}$ is generated independently of the input, the output distribution of the algorithm is not impacted by having $\mathbf{x}$ gradually revealed. It follows that the algorithm is also $\varepsilon$ -DP under continual observation. $\hfill\blacktriangleleft$ The online argument in the proof is explicit about $\mathbf{x}$ being chosen before any outputs are produced. We note that every non-adaptive $\varepsilon$ -DP algorithm for continual counting is also adaptive (see Proposition 2.1 in [14]). Privacy in the online setting can also be proved directly using a “shifting” argument for the Laplace variables $\mathbf{z}$ , as done in for example [18].

4.2 Utility

As intuited, allowing for the subtraction of vertices does indeed improve utility. Before stating the improvement, note that, analogous to the case without subtraction, the variance of the output from Algorithm 2 at time $t$ will be equal to $(2h^{2}/\varepsilon^{2})\cdot\left\lVert\operatorname{\mathsf{\widehat{rep}}}_% {k}(t,h)\right\rVert_{1}$ , since line 11 is executed $\left\lVert\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)\right\rVert_{1}$ times.

Lemma 14.

Algorithm 2 achieves a mean squared error of $\frac{k(1-1/k^{2})h^{3}}{2\varepsilon^{2}(1-1/k^{h})}$ over $T=(k^{h}-1)/2$ outputs.

Proof.

First note that the mean squared error over $T$ steps is equal to the average number of noise terms added together to produce an output, call this number $a_{[1,T]}$ , times the variance of the noise in each vertex. We thus want to compute $a_{[1,T]}=\frac{1}{T}\sum_{t=1}^{T}\left\lVert\operatorname{\mathsf{\widehat{% rep}}}_{k}(t,h)\right\rVert_{1}$ . Note that $T$ is the greatest positive integer that can be expressed using $h$ digits in $\{-\frac{k-1}{2},\dots,\frac{k-1}{2}\}$ , and $-T$ the most negative integer. For any representation $\mathbf{t}=\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)$ where $t\in[1,T]$ , note that we have a bijection where $-\mathbf{t}$ encodes a unique negative integer $\geq-T$ . We therefore have that $a_{[1,T]}=a_{[-T,-1]}$ , and $a_{[-T,T]}=(1-1/k^{h})\cdot a_{[1,T]}$ , where the extra factor comes from not including $0$ . Since $a_{[-T,T]}=h\cdot\frac{1}{k}\sum_{d=-(k-1)/2}^{(k-1)/2}|d|=\frac{h(k^{2}-1)}{4k}$ , by noting that every digit occurs the same amount of times in each position, we also have that $a_{[1,T]}=\frac{kh}{4}\frac{1-1/k^{2}}{1-1/k^{h}}$ . Since $\operatorname{Var}[\mathbf{z}_{p}]=2h^{2}/\varepsilon^{2}$ , we arrive at a mean squared error of $\frac{kh}{4}\frac{1-1/k^{2}}{1-1/k^{h}}\cdot\frac{2h^{2}}{\varepsilon^{2}}=% \frac{kh^{3}(1-1/k^{2})}{2\varepsilon^{2}(1-1/k^{h})}$ . $\hfill\blacktriangleleft$ We follow up with a corollary that states how the error scales and what constant the optimal $k$ gives.

Corollary 15.

Algorithm 2 achieves a mean squared error that scales as $\frac{k(1-1/k^{2})}{2\varepsilon^{2}\log(k)^{3}}\log(T)^{3}+o(\log(T)^{3})$ , and which is minimized for $k=19$ yielding $(0.1236/\varepsilon^{2})\log(T)^{3}+o(\log(T)^{3})$ .

In relation to Honaker Online, this is a constant improvement by more than a factor 4.

4.3 Space and time complexity

Finally, it turns out that extending to $k$ -ary trees with subtraction does not impact the efficiency of tree-based aggregation. We will need the following proposition to prove both the space and time complexity.

Proposition 16.

Each noise term $\mathbf{z}_{p}$ used by Algorithm 2 will only be used for outputs in a time interval $[t_{1},t_{2}]\subseteq[1,T]$ .

Proof.

Let the value of the iterate $\ell$ be $q$ when $\mathbf{z}_{p}$ is added on line 11. Consider first the case when $q<h$ . Note that for any time step $t$ with representation $\mathbf{t}=\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)$ , $\mathbf{z}_{p}$ is only used if the $h-q$ most-significant digits are identical across $\mathbf{p}=\operatorname{\mathsf{\widehat{rep}}}_{k}(p,h)$ and $\mathbf{t}$ . Interpreting any fixed number of most significant digits of $\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)$ as an integer, as $t$ is incremented, will produce a sequence of monotonically increasing integers, implying that any noise value $\mathbf{z}_{p}$ will start to get used at some $t_{1}$ , and then after some time step $t_{2}\geq t_{1}$ will never be used again, proving the claim for $q<h$ . If $q=h$ , then once $\mathbf{z}_{p}$ is added for the first time at $t_{1}$ , it will be added at every future time step including $t_{2}=T$ , proving the claim fully. $\hfill\blacktriangleleft$

Lemma 17.

Algorithm 2 runs in $O(k\log_{k}T)$ space.

Proof.

Note that at any time step $t$ , we need to store noise values used for the current time step $t$ , of which at most $h(k-1)/2$ are at most needed. Let $\mathbf{z}_{p}$ be an arbitrary noise value kept in memory at time $t$ , and then no longer used starting from $t^{\prime}\geq t$ . By Proposition 16, $\mathbf{z}_{p}$ will never be used again after $t^{\prime}$ , and it can therefore be removed from memory. It follows that no noise values besides those used at a current time step need to be stored in memory, thus we need to store at most $h(k-1)/2=O(k\log_{k}T)$ noise values. $\hfill\blacktriangleleft$

Lemma 18 states the time complexity of Algorithm 2, which assumes that (1) Laplace noise can be generated, and (2) $\operatorname{\mathsf{\widehat{rep}}}_{k}(t,h)$ can be computed, both in $O(k)$ time. Note that the cost of (1) is unavoidable, and that (2) can be efficiently computed by incrementing the digits at each step, where an argument analogous to the analysis for incrementing a binary counter implies a time of $O(kT)$ for incrementing the counter $T$ times as measured in digit flips.

Lemma 18.

Algorithm 2 can be implemented to run in $O(kT)$ time.

Proof.

First let $T=(k^{h}-1)/2$ , meaning we support as many inputs as possible using $h$ digits. Note that there are exactly $T$ unique noise variables used by Algorithm 2, since $p$ will take on all values in $[1,T]$ when iterating over $t$ . Rather than resetting $n o i s e$ on each iteration of $t$ , we can instead update it, removing noise terms that are no longer used and adding new noise as needed. Each of them will be added exactly once and subtracted at most once (Proposition 16), therefore we run in time $O(T)$ for this case. For $(k^{h-1}+1)/2\leq T<(k^{h}-1)/2=T^{\prime}$ , note that $\frac{T^{\prime}}{T}\leq\frac{(k^{h}-1)/2}{(k^{h-1}+1)/2}\leq k$ , and therefore if we estimate the runtime of $T$ by that for $T^{\prime}$ , we get a runtime of $O(kT^{\prime})$ in this case. $\hfill\blacktriangleleft$ Finally, combining Lemmas 13, 14, 17 and 18 gives us Theorem 1.

5 Laplace vs Gaussian noise

Having designed an efficient $\varepsilon$ -DP algorithm for continual counting with a state-of-the-art bound on the error, a natural question arises: how does it compare to $(\varepsilon,\delta)$ -DP mechanisms?

Since the noise of the Gaussian mechanism grows as $\delta$ approaches zero, it is clear that for any given bounds on $\ell_{1}$ and $\ell_{2}$ sensitivity, using the Gaussian mechanism with sufficiently small $\delta$ will result in more noise than the Laplace mechanism. We will see that for current continual counting methods this change happens for surprisingly large values of $\delta$ , with the exact threshold depending on the number of time steps $T$ .

Furthermore, we adapt the Laplace mechanism to work with $\ell_{2}$ sensitivity and show that it provides a meaningful $(\varepsilon,\delta)$ -DP guarantee with variance close to that of the Gaussian mechanism.

5.1 Laplace vs Gaussian noise for continual counting

We start by stating a lemma that compares the currently best continual counting mechanisms under pure and approximate differential privacy.

Lemma 19.

For constants $B_{\varepsilon},B_{\varepsilon,\delta}>0$ , let $(B_{\varepsilon}/\varepsilon^{2})\log(T)^{3}+o\big{(}\log(T)^{3}\big{)}$ be a bound on the $\operatorname{MSE}$ of an $\varepsilon$ -DP mechanism and $(B_{\varepsilon,\delta}/\varepsilon^{2})\log(T)^{2}\log(1/\delta)+o\big{(}\log% (T)^{2}\log(1/\delta)\big{)}$ be a bound on the mean squared error of an $(\varepsilon,\delta)$ -DP mechanism, both for continual counting. Then the $\varepsilon$ -DP mechanism achieves equivalent or better mean squared error, up to lower-order asymptotically vanishing terms, for $\delta=O(1/T^{B_{\varepsilon}/B_{\varepsilon,\delta}})$ .

Proof.

Comparing the leading terms of the errors and solving for $\delta$ yields the statement. $\hfill\blacktriangleleft$

Proof of Theorem 2.

Algorithm 2 has a leading constant of $B_{\varepsilon}<0.124$ for $k=19$ under $\varepsilon$ -DP, and the corresponding constant in [29] is $B_{\varepsilon,\delta}=4/(\pi^{2}\log(e)^{3})>0.1349$ , so we have $B_{\varepsilon}/B_{\varepsilon,\delta}<0.92$ . Lemma 19 thus implies that the pure mechanism has a smaller bound on the noise for $\delta=O(T^{-0.92})$ . $\hfill\blacktriangleleft$

5.2 Laplace noise scaled to $\ell_{2}$ sensitivity

We next consider how we may extend the Laplace mechanism with an approximate DP guarantee similar to the Gaussian mechanism, i.e., with noise scaled to the $\ell_{2}$ sensitivity. Since the proof of this is straightforward using known results we suspect this fact may be known, but we are not aware of it appearing in the literature. The technique for extending the Laplace mechanism to approximate DP relies on the following heterogeneous composition theorem [34].

Lemma 20 (Simplified version of Theorem 3.5 in [34]).

For any $\varepsilon_{j}>0$ for $j\in\{1,,\dots,k\}$ , and $\delta\in(0,1)$ , the class of $\varepsilon_{j}$ -differentially private mechanisms satisfy $(\tilde{\varepsilon},\delta)$ -differential privacy under $k$ -fold adaptive composition for

\tilde{\varepsilon}=\min\bigg{\{}\sum_{j=1}^{k}\varepsilon_{j},\,\sum_{j=1}^{k% }\frac{(e^{\varepsilon_{j}}-1)\varepsilon_{j}}{e^{\varepsilon_{j}}+1}+\sqrt{2% \ln(1/\delta)\sum_{j=1}^{k}\varepsilon_{j}^{2}},\bigg{\}}\enspace.

Using Lemma 20, we can derive the following approximate DP guarantee for the $\ell_{2}$ Laplace mechanism.

Lemma 21 ( $\ell_{2}$ Laplace Mechanism).

Let $f:\mathcal{X}^{n}\to\mathbb{R}^{d}$ be a function with $\ell_{2}$ -sensitivity $\Delta_{2}\coloneqq\max_{\mathcal{D}\sim\mathcal{D}^{\prime}}\left\lVert f(% \mathcal{D})-f(\mathcal{D}^{\prime})\right\rVert_{2}$ . For a given dataset $\mathcal{D}\in\mathcal{X}^{n}$ and $\varepsilon,\delta\in(0,1)$ , the output $f(\mathcal{D})+\mathsf{Lap}(\Delta_{2}/a_{\varepsilon,\delta})^{d}$ , where $a_{\varepsilon,\delta}=\sqrt{2\ln(1/\delta)}(\sqrt{1+\varepsilon/\ln(1/\delta)% }-1)$ , satisfies $(\varepsilon,\delta)$ -DP.

Proof.

For $x_{1},\dots,x_{j}\in(0,1)$ , since $\frac{e^{x_{i}}-1}{e^{x_{i}}+1}\leq x_{i}/2$ it follows from Lemma 20 that $(\tilde{\varepsilon},\delta)$ -differential privacy is also satisfied for

\tilde{\varepsilon}=\min\bigg{\{}\sum_{j=1}^{k}\varepsilon_{j},\,\frac{1}{2}% \sum_{j=1}^{k}\varepsilon_{j}^{2}+\sqrt{2\ln(1/\delta)\sum_{j=1}^{k}% \varepsilon_{j}^{2}},\bigg{\}}\enspace.

(1)

It suffices to establish the privacy of the Laplace mechanism when restricted to arbitrary neighboring inputs $x$ , $x^{\prime}$ . We will reason about the privacy loss for each coordinate of $\mathbf{y}=f(x)$ separately relative to the neighboring output $\mathbf{y}^{\prime}=f(x^{\prime})$ . Focusing on one coordinate $\mathbf{y}_{j}$ and its private release, we have that its release must satisfy $\varepsilon_{j}$ -differential privacy where $\varepsilon_{j}=(a_{\varepsilon,\delta}/\Delta_{2})\cdot\lvert\mathbf{y}_{j}-% \mathbf{y}_{j}^{\prime}\rvert$ . Composing the $d$ private releases of each coordinate using the bound (1) and noting that $\sum_{j=1}^{d}\varepsilon_{j}^{2}\leq(a_{\varepsilon,\delta}/\Delta_{2})^{2}% \sum_{j=1}^{d}(\mathbf{y}_{j}-\mathbf{y}_{j}^{\prime})^{2}\leq a_{\varepsilon,% \delta}^{2}$ therefore gives an $(\varepsilon,\delta)$ -guarantee where $\varepsilon=a_{\varepsilon,\delta}(\frac{a_{\varepsilon,\delta}}{2}+\sqrt{2\ln% (1/\delta)})$ . Proceeding to solve for (positive) $a_{\varepsilon,\delta}$ gives the statement. $\hfill\blacktriangleleft$ The variance needed for $\ell_{2}$ -scaled Laplace noise compared to Gaussian noise for $(\varepsilon,\delta)$ -DP is only a constant factor greater whenever $\varepsilon\leq\log(1/\delta)$ , and the constant approaches $2$ as $\varepsilon$ approaches zero.

Corollary 22.

Let $\mathbf{y}^{\mathrm{lap}}$ and $\mathbf{y}^{\mathrm{gauss}}$ be outputs based on the $\ell_{2}$ Laplace mechanism (Lemma 21) and the Gaussian mechanism (Lemma 25) respectively, both to achieve the same $(\varepsilon,\delta)$ -DP guarantee where $\varepsilon\leq\ln(1/\delta)$ . Then $\operatorname{Var}[\mathbf{y}^{\mathrm{lap}}_{j}]\leq\frac{(\varepsilon/\ln(1/% \delta))^{2}}{2(\sqrt{1+\varepsilon/\ln(1/\delta)}-1)^{2}}\cdot\operatorname{% Var}[\mathbf{y}^{\mathrm{gauss}}_{j}]$ . Also, $\lim_{\varepsilon\to 0}\frac{(\varepsilon/\ln(1/\delta))^{2}}{2(\sqrt{1+% \varepsilon/\ln(1/\delta)}-1)^{2}}=2$ .

Proof.

Using Lemma 21 and noting that the variance of the noise added is twice the square of the scale parameter for Laplace noise, we get that

\frac{\operatorname{Var}[\mathbf{y}^{\mathrm{lap}}_{j}]}{\operatorname{Var}[% \mathbf{y}^{\mathrm{gauss}}_{j}]}=\frac{2\Delta_{2}^{2}/(2\ln(1/\delta)(\sqrt{% 1+\varepsilon/\ln(1/\delta)}-1)^{2})}{2\ln(1.25/\delta)\Delta^{2}_{2}/% \varepsilon^{2}}\leq\frac{(\varepsilon/\ln(1/\delta))^{2}}{2(\sqrt{1+% \varepsilon/\ln(1/\delta)}-1)^{2}}\enspace.

To show the limit, note that for positive $w\leq 1$ we have that $\frac{w}{\sqrt{1+w}-1}\leq\frac{w}{w/2-w^{2}/8}=\frac{2}{1-w/4}\to 2$ as $w\to 0$ , and $\frac{w}{\sqrt{1+w}-1}\geq 2$ , both based on truncated Taylor expansions of $\sqrt{1+w}$ . $\hfill\blacktriangleleft$

Finally we prove Theorem 3 from the introduction.

Proof of Theorem 3.

From the proof of Lemma 21, we have that adding noise $\mathsf{Lap}(\Delta_{2}/a)$ gives an $(\varepsilon^{\prime},\delta)$ -guarantee where $\varepsilon^{\prime}=a(\frac{a}{2}+\sqrt{2\ln(1/\delta)})$ if $\varepsilon^{\prime},\delta\in(0,1)$ . Note that our setup is the same if we set $a=\frac{\Delta_{2}}{\lambda}$ , and that adding noise $\mathsf{Lap}(\lambda)$ gives an $\frac{\Delta_{1}}{\lambda}$ -DP guarantee. We can therefore always guarantee $(\varepsilon,\delta)$ -DP where $\varepsilon=\min\{\frac{\Delta_{1}}{\lambda},\varepsilon^{\prime}\}<1$ if we enforce $\lambda>\Delta_{1}$ . $\hfill\blacktriangleleft$ Note that while functions with low $\ell_{1}$ sensitivity also have low $\ell_{2}$ sensitivity, the converse does not hold. In principle we can replace Gaussian noise with Laplace noise at a limited loss in utility for approximate DP (Corollary 22), but the corresponding $\varepsilon$ -DP guarantee afforded by the noise will be weak unless $\Delta_{1}$ is small. Theorem 3 can alternatively be seen as adding an approximate DP guarantee to pure DP mechanisms built on top of the Laplace mechanism.

6 Discussion

While there are no known fundamental reasons ruling out asymptotic improvements in the mean squared error for $\varepsilon$ -DP – it might be possible to match the $\Omega(\log(T)^{2})$ lower bound of [29] – there have been no asymptotic improvements since the binary tree mechanism [18, 7]. This state of affairs motivates exploring how much leading constants can be improved using the factorization mechanism framework. Algorithm 2 falls into the framework, is easy to implement, efficient, and offers the best known error-scaling to date.

Our paper also reveals that using Laplace noise improves the best possible $(\varepsilon,\delta)$ -differentially private factorization mechanisms based on Gaussian noise whenever $\delta$ is sufficiently small. An interesting future direction is to investigate, for fixed $\varepsilon,\delta$ and a given factorization: which noise distribution achieves optimal error? It seems unlikely that Laplace or Gaussian noise is always best – indeed, Vinterbo [42] has results of this flavor in more restricted settings.

Finally, while we show a lower bound for random inputs that matches the best lower bound known for worst-case inputs, it is still possible that random inputs are easier and allow lower error than what can be achieved for worst-case inputs.

References

[1] Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/paper/2023/hash/99c41fb9fd53abfdd4a0259560ef1c9d-Abstract-Conference.html.
[2] Joel Daniel Andersson and Rasmus Pagh. Streaming private continual counting via binning. CoRR, abs/2412.07093, 2024. To appear in the proceedings of SaTML 2025. doi:10.48550/arXiv.2412.07093.
[3] Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy. CoRR, abs/2408.07021v1, 2024. Earlier (non-archival) version with a different title and set of authors. Presented at TPDP 2024. arXiv:2408.07021v1.
[4] Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 394–403. PMLR, 10–15 July 2018. URL: https://proceedings.mlr.press/v80/balle18a.html.
[5] G. Bennett. Schur multipliers. Duke Mathematical Journal, 44(3):603–639, 1977. doi:10.1215/S0012-7094-77-04426-X.
[6] Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 2397–2419. PMLR, 2022. URL: https://proceedings.mlr.press/v151/rivera-cardoso22a.html.
[7] T. H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams. In Simone Fischer-Hübner and Matthew Wright, editors, Privacy Enhancing Technologies, Lecture Notes in Computer Science, pages 140–159, Berlin, Heidelberg, 2012. Springer. doi:10.1007/978-3-642-31680-7_8.
[8] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and Continual Release of Statistics. ACM Transactions on Information and System Security, 14(3):26:1–26:24, November 2011. doi:10.1145/2043621.2043626.
[9] Christopher A. Choquette-Choo, Arun Ganesh, Ryan McKenna, H. Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A unified approach to private training. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/paper/2023/hash/ecc28b4ce9b39f5f23c3efb03e25b7bf-Abstract-Conference.html.
[10] Christopher A. Choquette-Choo, Hugh Brendan McMahan, J. Keith Rush, and Abhradeep Guha Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 5924–5963. PMLR, 2023. URL: https://proceedings.mlr.press/v202/choquette-choo23a.html.
[11] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Shipra Agrawal and Aaron 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.
[12] Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Answering range queries under local differential privacy. Proc. VLDB Endow., 12(10):1126–1138, June 2019. doi:10.14778/3339490.3339496.
[13] Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 625–661. PMLR, 02–05 July 2022. URL: https://proceedings.mlr.press/v178/dagan22a.html.
[14] Sergey Denisov, H. Brendan McMahan, John Rush, Adam D. Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In NeurIPS, 2022. URL: http://papers.nips.cc/paper_files/paper/2022/hash/271ec4d1a9ff5e6b81a6e21d38b1ba96-Abstract-Conference.html.
[15] Jinshuo Dong, Weijie J. Su, and Linjun Zhang. A central limit theorem for differentially private query answering. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 14759–14770, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/7c2c48a32443ad8f805e48520f3b26a4-Abstract.html.
[16] Krishnamurthy Dj Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 2306–2317. IEEE, 2024. doi:10.1109/FOCS61266.2024.00135.
[17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, TCC’06, pages 265–284, Berlin, Heidelberg, 2006. Springer-Verlag. doi:10.1007/11681878_14.
[18] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, STOC ’10, pages 715–724, New York, NY, USA, June 2010. Association for Computing Machinery. doi:10.1145/1806689.1806787.
[19] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Proceedings, Part II, of the 21st International Conference on Advances in Cryptology — ASIACRYPT 2015 - Volume 9453, pages 735–751, Berlin, Heidelberg, 2015. Springer-Verlag. doi:10.1007/978-3-662-48800-3_30.
[20] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4):211–407, 2013. doi:10.1561/0400000042.
[21] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 10072–10092. PMLR, 23–29 July 2023. URL: https://proceedings.mlr.press/v202/fichtenberger23a.html.
[22] J. Gehrke, G. Wang, and X. Xiao. Differential privacy via wavelet transforms. In 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), pages 225–236, Los Alamitos, CA, USA, March 2010. IEEE Computer Society. doi:10.1109/ICDE.2010.5447831.
[23] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Optimal noise-adding mechanism in additive differential privacy. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 11–20. PMLR, 2019. URL: http://proceedings.mlr.press/v89/geng19a.html.
[24] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 89–99. PMLR, 2020. URL: http://proceedings.mlr.press/v108/geng20a.html.
[25] Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow., 3(1–2):1021–1032, September 2010. doi:10.14778/1920841.1920970.
[26] Monika Henzinger, Nikita P. Kalinin, and Jalaj Upadhyay. Binned group algebra factorization for differentially private continual counting, 2025. arXiv:2504.04398.
[27] Monika Henzinger, Andrea Lincoln, and Barna Saha. The complexity of average-case dynamic subgraph counting. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 459–498. SIAM, 2022. doi:10.1137/1.9781611977073.23.
[28] Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2951–2970. SIAM, 2025. doi:10.1137/1.9781611978322.95.
[29] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003–5039, 2023. doi:10.1137/1.9781611977554.ch183.
[30] Naoise Holohan, Spiros Antonatos, Stefano Braghin, and Pól Mac Aonghusa. The bounded laplace mechanism in differential privacy. J. Priv. Confidentiality, 10(1), 2020. doi:10.29012/JPC.715.
[31] James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27, 2015.
[32] Ziyue Huang, Yuan Qiu, Ke Yi, and Graham Cormode. Frequency estimation under multiparty differential privacy: one-shot and streaming. Proceedings of the VLDB Endowment, 15(10):2058–2070, September 2022. doi:10.14778/3547305.3547312.
[33] Peter Kairouz, Brendan Mcmahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and Private (Deep) Learning Without Sampling or Shuffling. In Proceedings of the 38th International Conference on Machine Learning, pages 5213–5225. PMLR, July 2021. ISSN: 2640-3498. URL: https://proceedings.mlr.press/v139/kairouz21b.html.
[34] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1376–1385, Lille, France, 07–09 July 2015. PMLR. URL: https://proceedings.mlr.press/v37/kairouz15.html.
[35] Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24(6):757–781, December 2015. doi:10.1007/s00778-015-0398-x.
[36] Fang Liu. Generalized gaussian mechanism for differential privacy. IEEE Trans. Knowl. Data Eng., 31(4):747–756, 2019. doi:10.1109/TKDE.2018.2845388.
[37] H. Brendan McMahan and Abhradeep Thakurta. Federated Learning with Formal Differential Privacy Guarantees, 2022. Accessed online 2023-05-15. URL: https://ai.googleblog.com/2022/02/federated-learning-with-formal.html.
[38] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. Proc. VLDB Endow., 6(14):1954–1965, September 2013. doi:10.14778/2556549.2556576.
[39] David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proc. Priv. Enhancing Technol., 2019(2):245–269, 2019. doi:10.2478/POPETS-2019-0029.
[40] Thomas Steinke and Jonathan R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2016. doi:10.29012/JPC.V7I2.648.
[41] Jalaj Upadhyay. Sublinear Space Private Algorithms Under the Sliding Window Model. In Proceedings of the 36th International Conference on Machine Learning, pages 6363–6372. PMLR, May 2019. ISSN: 2640-3498. URL: https://proceedings.mlr.press/v97/upadhyay19a.html.
[42] Staal Amund Vinterbo. Differential privacy for symmetric log-concave mechanisms. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 6270–6291. PMLR, 2022. URL: https://proceedings.mlr.press/v151/vinterbo22a.html.

Appendix A Definitions for Differential Privacy

Here are the standard definitions for differential privacy which we have use for in the paper.

Definition 23 ( $(\varepsilon,\delta)$ -Differential Privacy [20]).

A randomized algorithm $\mathcal{M}:\mathcal{X}^{n}\to\mathcal{Y}$ is ( $\varepsilon,\delta)$ -differentially private if for all $S\subseteq\mathsf{Range}(\mathcal{M})$ and all neighboring inputs $\mathcal{D},\mathcal{D}^{\prime}\in\mathcal{X}^{n}$ , the neighboring relation written as $\mathcal{D}\sim\mathcal{D}^{\prime}$ , we have that:

\Pr[\mathcal{M}(\mathcal{D})\in S]\leq\exp(\varepsilon)\Pr[\mathcal{M}(% \mathcal{D}^{\prime})\in S]+\delta\,,

where $(\varepsilon,0)$ -DP is referred to as $\varepsilon$ -DP.

Lemma 24 (Laplacian Mechanism [20]).

Let $f:\mathcal{X}^{n}\to\mathbb{R}^{d}$ be a function with $\ell_{1}$ -sensitivity $\Delta_{1}\coloneqq\max_{\mathcal{D}\sim\mathcal{D}^{\prime}}\left\lVert f(% \mathcal{D})-f(\mathcal{D}^{\prime})\right\rVert_{1}$ . For a given data set $\mathcal{D}\in\mathcal{X}^{n}$ and $\varepsilon>0$ , the mechanism that releases $f(\mathcal{D})+\mathsf{Lap}(\Delta_{1}/\varepsilon)^{d}$ satisfies $\varepsilon$ -DP.

Lemma 25 (Gaussian Mechanism [20]).

Let $f:\mathcal{X}^{n}\to\mathbb{R}^{d}$ be a function with $\ell_{2}$ -sensitivity $\Delta_{2}\coloneqq\max_{\mathcal{D}\sim\mathcal{D}^{\prime}}\left\lVert f(% \mathcal{D})-f(\mathcal{D}^{\prime})\right\rVert_{2}$ . For a given data set $\mathcal{D}\in\mathcal{X}^{n}$ and $\varepsilon,\delta\in(0,1)$ , the mechanism that releases $f(\mathcal{D})+\mathcal{N}(0,2\ln(1.25/\delta)\Delta_{2}^{2}/\varepsilon^{2})^% {d}$ satisfies $(\varepsilon,\delta)$ -DP.

Appendix B $𝒌$ -ary Tree Mechanisms: Proofs

In this subsection, we will briefly discuss the proof sketch for Theorem 9. It is important to note that while this proof is included, it is not considered a main contribution of this paper.

Proof sketch of Theorem 9.

The utility and privacy follow from Lemmas 7 and 8, and the online nature of the mechanism follows from the partial sums being added on Line 11 involving inputs $\mathbf{x}_{i}$ with $i\leq p\leq t$ . For the argument about space usage, a standard argument [8, 1] can be extended from the binary tree mechanism to $k$ -ary tree mechanism to yield $O(k\log_{k}T)$ . Similarly, the time needed to release $T$ prefix sum will be $O(kT)$ (assuming noise can be generated in constant time) based on extending the analysis of incrementing a binary counter to incrementing a $k$ -ary counter. $\hfill\blacktriangleleft$

Appendix C Leveraging subtraction for even $𝒌$

In the main part of the paper we only considered subtraction for $k$ -ary trees when $k$ was odd. This part of the appendix is intended for motivating that choice.

First note that for even $k$ we lose the symmetry in the offset digits, so we need to make a decision if the digits in the offset representation are $\{-k/2+1,\dots k/2\}$ or $\{-k/2,\dots,k/2-1\}$ . We pick the first one as that allows for supporting more inputs, giving Definition 26.

Definition 26 (Offset (even) $k$ -ary representation of integers).

Let $k$ , $w$ and $t$ be positive integers, with $k$ also being even, satisfying $t\leq\frac{k(k^{h}-1)}{2(k-1)}$ . We then define $\mathbf{t}=\operatorname{\mathsf{\widetilde{rep}}}_{k}(t,w)\in[-\frac{k}{2}+1,% \frac{k}{2}]^{w}$ as the unique vector with integer entries in $[-\frac{k}{2}+1,\frac{k}{2}]^{w}$ satisfying $\sum_{i=1}^{w}k^{i-1}\mathbf{t}_{i}=t$ .

Substituting the representation used in Algorithm 2 by the one in Definition 26 and setting the height appropriately gives a valid algorithm using a $k$ -ary tree. However, it performs worse than using odd $k$ .

Claim 27.

For even $k\geq 4$ , $h\geq 1$ , and $T=\frac{k(k^{h}-1)}{2(k-1)}$ , Algorithm 2, with $h$ correctly set, achieves a mean squared error of $\frac{kh^{3}}{2\varepsilon^{2}}\frac{1}{1-1/k^{h}}+o(h^{2})$ when producing $T$ outputs.

Proof sketch..

The same proof as for Lemma 14 does not work due to the asymmetry in the digits. Instead, we can express a recursion for the number of terms needed. Let $c_{h}$ be the total number of vertices combined to produce all prefixes that a tree of height $h$ can support. Then we have

c_{h}=\bigg{(}\frac{k+2}{4}+\frac{k(h-1)}{4}\bigg{)}\frac{k}{2}k^{h-1}+c_{h-1}\,,

where $c_{0}=0$ . The idea behind the recursion is as follows: the first term corresponds to all the integer representations with positive leading digit, of which there are $k/2\cdot k^{h}$ , and the leading digit contributes $(k+2)/4$ , the remaining $k(h-1)/4$ on average. The second term is the case where the first digit is zero, in which case the contribution is $c_{h-1}$ . Solving the recursion and dividing by $T$ yields the average number of vertices added, $c_{h}/T=\frac{kh}{4}\frac{1}{1-1/k^{h}}+o(1)$ , which when multiplied by the variance of a vertex, $2h^{2}/\varepsilon^{2}$ , gives the statement. $\hfill\vartriangleleft$ Ignoring the lower order terms, this is worse by a factor $1-1/k^{2}$ over the odd case, and we can also find the optimal $k$ here.

Corollary 28.

Algorithm 2, with modifications for even $k$ , achieves a mean squared error that scales as $\frac{k}{2\varepsilon^{2}\log(k)^{3}}\log(T)^{3}+o(\log(T)^{3})$ , and which is minimized for $k=20$ yielding $(0.1238/\varepsilon^{2})\log(T)^{3}+o(\log(T)^{3})$ .

As the analysis is less elegant, we get more lower order terms and the scaling is worse, we focus on odd $k$ in the paper.

Appendix D Lower bound for continual observation on random inputs

In this section we consider continual observation in the “offline” setting where a mechanism has access to the entire input and has to output a differentially private approximation of all prefix sums. This of course implies a lower bound for the “online” setting. We show Theorem 4 which achieves the same lower bound that was previously known for worst-case inputs, in the setting where the input is a random string.

Proof of Theorem 4.

We will prove the theorem via a packing argument applied to a carefully constructed collection of random strings. Without loss of generality, let $B=\sqrt{T}$ be an integer divisible by $4$ , $k\leq T^{1/5}$ be an even integer, and $T$ be large enough such that $k\leq B/4$ . Also divide the timeline $[1,T]$ into blocks of length $B$ : $B_{1}=[1,B],B_{2}=[B+1,2B],\dots,B_{m}=[T-B+1,T]$ , $m=T/B$ . For an arbitrary string $\mathbf{y}\in\{0,1\}^{T}$ , we use the notation $\mathbf{y}_{B_{i}}\in\{0,1\}^{B}$ for the substring of $\mathbf{y}$ formed from the indices in $B_{i}$ . We use $\mathrm{err}(\cdot)$ , taking as input the output of a mechanism, to denote the (random) maximum additive error over all the outputs. The argument is outlined below:

$\blacksquare$

Construct random strings $\mathbf{x}^{(0)},\dots,\mathbf{x}^{(m)}$ that are near-neighboring and have small total variation distance to random strings from $\mathcal{U}$ .
$\blacksquare$

Argue that $\mathcal{M}$ assumes additive error $\leq\alpha$ on these inputs with constant probability by virtue of the small total variation distance.
$\blacksquare$

Show that for $i\neq i^{\prime}$ $\mathcal{M}$ can be used to distinguish $\mathbf{x}^{(i)}$ from $\mathbf{x}^{(i^{\prime})}$ unless $\alpha=\Omega(\varepsilon^{-1}\log T)$ .

The intuition behind the argument is that an accurate mechanism $\mathcal{M}$ on $\mathcal{U}$ will also be accurate on our random (but highly correlated) strings $\mathbf{x}^{(0)},\dots\mathbf{x}^{(m)}$ . Being accurate on these strings implies the ability to distinguish between them. However, since $\mathcal{M}$ satisfies $\varepsilon$ -DP, distinguishing between the inputs with good confidence is impossible, implying a lower bound on the additive error $\alpha$ .

To this end, we define the random variables $X^{(i)}_{j}=\left\lVert\mathbf{x}^{(i)}_{B_{j}}\right\rVert_{1}=\sum_{\ell\in B% _{j}}\mathbf{x}^{(i)}_{\ell}$ , i.e., as the sum of 1s in the block $B_{j}$ of $\mathbf{x}^{(i)}$ . With the argument outlined, consider the random strings $\mathbf{x}^{(0)},\mathbf{x}^{(1)},\dots,\mathbf{x}^{(m)}$ formed by the following process:

1.

Draw $\mathbf{x}^{(0)}$ from $\mathcal{U}$ conditioned on $X^{(0)}_{j}\in[\frac{B}{4},\frac{3B}{4}]$ for all $j\in[m]$ . Call this distribution $\mathcal{D}^{(0)}$ .
2.

For $i\in[m]$ derive $\mathbf{x}^{(i)}$ from $\mathbf{x}^{(0)}$ by choosing $k$ 0s in $B_{i}$ uniformly at random and flipping them to 1s. Call these distributions $\mathcal{D}^{(i)}$ .

We next define the algorithm $\mathrm{Alg}(\mathbf{y},\mathbf{y}^{\prime})$ outputting the difference between private sums on two arbitrary inputs $\mathbf{y},\mathbf{y}^{\prime}\in\{0,1\}^{T}$ . Formally, on receiving $\mathbf{y}$ and $\mathbf{y}^{\prime}$ , it runs $\mathcal{M}$ on each, producing outputs $\mathbf{a}_{1},\dots,\mathbf{a}_{T}$ and $\mathbf{a}_{1}^{\prime},\dots,\mathbf{a}_{T}^{\prime}$ respectively, and at time $t$ , the algorithm outputs $\mathrm{Alg}(\mathbf{y},\mathbf{y}^{\prime})_{t}=\mathbf{a}_{t}-\mathbf{a}_{t}% ^{\prime}$ . We will show, step-by-step, that the accuracy guarantee of $\mathcal{M}$ on $\mathcal{U}$ will imply distinguishing between our random strings $\mathbf{x}^{(0)},\dots,\mathbf{x}^{(i)}$ .

Consider $\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})$ for $i\in[1,m]$ . Note that the true prefix sums of $\mathbf{x}^{(i)}$ and $\mathbf{x}^{(0)}$ at the end of each block will be identical up until block $B_{i}$ , at the end of which they will differ by exactly $k$ . We leverage this observation by introducing the following disjoint events $E_{j}$ . For $j\in[1,m]$ and arbitrary input strings $\mathbf{y}$ , $\mathbf{y}^{\prime}$ , we define $E_{j}$ as the event that the following two statements are true: (1) for all $\ell\in[1,j-1]:\mathrm{Alg}(\mathbf{y},\mathbf{y}^{\prime})_{\ell B}\leq k/2$ , and (2) $\mathrm{Alg}(\mathbf{y},\mathbf{y}^{\prime})_{jB}>k/2$ . In other words, $E_{j}$ is the event that, when tracking only the outputs at the end of blocks, $\mathrm{Alg}(\mathbf{y},\mathbf{y}^{\prime})$ outputs a value greater than $k/2$ for the first time at the end of block $B_{j}$ . Set $\alpha=k/4$ . By our construction, if $\mathcal{M}(\mathbf{x}^{(0)})$ and $\mathcal{M}(\mathbf{x}^{(i)})$ each assumes additive error at most $\alpha$ when running $\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})$ , then $\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})$ has additive error at most $2\alpha=k/2$ , and $E_{i}$ happens with probability $1$ . We thus have

\Pr[\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})\in E_{i}]\geq\Pr[\mathcal{% M}(\mathbf{x}^{(i)})\leq\alpha]\cdot\Pr[\mathcal{M}(\mathbf{x}^{(0)})\leq% \alpha]\enspace.

We want to argue that $\mathcal{M}$ is accurate on $\mathbf{x}^{(0)},\dots,\mathbf{x}^{(m)}$ , with constant probability for each input taken separately, and we will argue via the total variation distance between each of these random strings, and the random string $\mathbf{x}\sim\mathcal{U}$ . In general, for a (possibly randomized) algorithm $\mathcal{A}:S\to\mathbb{R}$ , distributions $\mathcal{D},\mathcal{D}^{\prime}$ over $S$ with total variation distance $\operatorname{TV}(\mathcal{D},\mathcal{D}^{\prime})\leq\Delta$ , and an event $E$ over the output, we have that if $\Pr_{\mathcal{A},x\sim\mathcal{D}}[\mathcal{A}(x)\in E]\geq p\geq 0$ , then $\Pr_{\mathcal{A},x\sim\mathcal{D}^{\prime}}[\mathcal{A}(x)\in E]\geq p-\Delta$ . This follows from the observation that, in the extreme case, $\Delta$ probability mass can be shifted from inputs $x\in S$ where $\Pr_{\mathcal{A}}[\mathcal{A}(x)\in E]=1$ to inputs $x^{\prime}\in S$ where $\Pr_{\mathcal{A}}[\mathcal{A}(x^{\prime})\in E]=0$ . If we manage to show that, for $i\in[0,m]$ , $\operatorname{TV}(\mathbf{x},\mathbf{x}^{(i)})=o(1)$ , then we can lower bound $\Pr[\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})\in E_{i}]$ by a positive constant. We derive bounds on these total variation distances in the next two lemmas.

Lemma 29.

Let $\mathbf{x}\sim\mathcal{U}$ and $\mathbf{x}^{(0)}\sim\mathcal{D}^{(0)}$ . Then we have $\operatorname{TV}(\mathbf{x},\mathbf{x}^{(0)})\leq\Delta$ , where $\Delta=2\sqrt{T}\exp(-\sqrt{T}/8)$

Proof.

Let $S$ be the support of $\mathcal{U}$ and $S^{(0)}\subseteq S$ the support of $\mathcal{D}^{(0)}$ . We have that $X\sim\mathrm{Bin}(B,1/2)$ describes the number of 1s in an arbitrary block $B_{i}$ of $\mathbf{x}$ . Hoeffding’s inequality gives $\Pr[\frac{B}{4}\leq X\leq\frac{3B}{4}]\geq 1-2\exp(-B/8)$ whereby it follows that $\Pr[\mathbf{x}\in S^{(0)}]\geq\big{(}1-2\exp(-B/8)\big{)}^{T/B}$ . Observing that $\mathbf{x}^{(0)}$ is uniformly distributed over $S^{(0)}\subseteq S$ , we proceed to directly compute the total variation distance:

	$\displaystyle\operatorname{TV}(\mathbf{x},\mathbf{x}^{(0)})$	$\displaystyle=\frac{1}{2}\sum_{\mathbf{s}\in S}\|\Pr[\mathbf{x}=\mathbf{s}]-\Pr% [\mathbf{x}^{(0)}=\mathbf{s}]\|$
		$\displaystyle=\frac{1}{2}\|S^{(0)}\|\bigg{(}\frac{1}{\|S^{(0)}\|}-\frac{1}{\|S\|}% \bigg{)}+\frac{1}{2}(\|S\|-\|S^{(0)}\|)\cdot\frac{1}{\|S\|}=1-\Pr[\mathbf{x}\in S^{(% 0)}]$
		$\displaystyle\leq 1-\big{(}1-2\exp(-B/8)\big{)}^{T/B}\leq\frac{2T\exp(-B/8)}{B% }=2\sqrt{T}\exp(-\sqrt{T}/8)\enspace,$

where the last inequality is using Bernoulli’s inequality and holds for $T$ larger than an absolute constant. $\hfill\blacktriangleleft$ We prove that the remaining random strings $\mathbf{x}^{(1)},\dots,\mathbf{x}^{(m)}$ are closely distributed to strings in $\mathcal{U}$ next.

Lemma 30.

Let $\mathbf{x}\sim\mathcal{U}$ and $\mathbf{x}^{(i)}\sim\mathcal{D}^{(i)}$ for $i\in[m]$ . Then $\operatorname{TV}(\mathbf{x},\mathbf{x}^{(i)})\leq\Delta^{\prime}$ where $\Delta^{\prime}=10\cdot T^{-1/20}$ .

Proof.

As the total variation distance satisfies the triangle inequality, we can write

\operatorname{TV}(\mathbf{x},\mathbf{x}^{(i)})\leq\operatorname{TV}(\mathbf{x}% ,\mathbf{x}^{(0)})+\operatorname{TV}(\mathbf{x}^{(0)},\mathbf{x}^{(i)})\enspace.

The first term we have already computed in Lemma 29. To bound the second term, we will use a property of total variation distance: it cannot increase if one applies the same transformation to both arguments. Let $f:[m]\times[0,B]\to\mathcal{F}$ be a mapping to a family of distributions where $f(i,\ell)$ denotes the distribution described by a process where (1) a string $\mathbf{y}\sim\mathcal{D}^{(0)}$ is sampled and then (2) $\mathbf{y}_{B_{i}}$ is overwritten by a uniformly sampled string in $\{0,1\}^{B}$ , conditioned on it having $\ell$ 1s. For $i\in[m]$ , we claim that ( $f(i,X^{(i)}_{i})$ , $\mathcal{D}^{(i)})$ and $(f(i,X^{(0)}_{i}),\mathcal{D}^{(0)})$ are pairs of identical distributions. To see this for the first pair of distributions, consider $\mathbf{y}\sim f(i,X^{(i)}_{i})$ . By definition $\mathbf{y}_{B_{j}}$ is identically distributed to $\mathbf{x}^{(i)}_{B_{j}}$ for $j\neq i$ , and so the only special case to consider is $j=i$ . For this case, we note that $X^{(i)}_{i}$ is defined as the number of 1s in $\mathbf{x}^{(i)}_{B_{i}}$ , and that symmetry implies that any substring with $\ell$ 1s is equally likely, thus $\mathbf{y}_{B_{i}}$ must be identically distributed to $\mathbf{x}^{(i)}_{B_{i}}$ as well, and we are done. An analogous argument can be used for showing that $f(i,X^{(0)}_{i})$ and $\mathcal{D}^{(0)}$ are identically distributed.

We thus have $\operatorname{TV}(\mathbf{x}^{(0)},\mathbf{x}^{(i)})=\operatorname{TV}(f(i,X^{% (0)}_{i}),f(i,X^{(i)}_{i}))\leq\operatorname{TV}(X^{(0)}_{i},X^{(i)}_{i})$ , and so our problem reduces to bounding this quantity.

	$\displaystyle\operatorname{TV}(X^{(0)}_{i},X^{(i)}_{i})$	$\displaystyle=\frac{1}{2}\sum_{\ell=0}^{B}\lvert\Pr[X^{(0)}_{i}=\ell]-\Pr[X^{(% i)}_{i}=\ell]\rvert$
		$\displaystyle=\frac{1}{2}\sum_{\ell=0}^{B}\lvert\Pr[X^{(0)}_{i}=\ell]-\Pr[X^{(% 0)}_{i}=\ell-k]\rvert$
		$\displaystyle=\frac{1}{2}\bigg{(}\sum_{\ell=B/4}^{B/4+k-1}\Pr[X^{(0)}_{i}=\ell% ]+\sum_{l=3B/4+1-k}^{3B/4}\Pr[X^{(0)}_{i}=\ell]$
		$\displaystyle+\sum_{\ell=B/4+k}^{3B/4}\lvert\Pr[X^{(0)}_{i}=\ell]-\Pr[X^{(i)}_% {i}=\ell]\rvert\bigg{)}$
		$\displaystyle\leq k\cdot\Pr[X^{(0)}_{i}=B/4+k]+\frac{1}{2}\sum_{\ell=B/4+k}^{3% B/4}\lvert\Pr[X^{(0)}_{i}=\ell]-\Pr[X^{(0)}_{i}=\ell-k]\rvert$

The last step follows from the symmetry of $X^{(0)}_{i}$ : $\Pr[X^{(0)}_{i}=B/2+\ell]=\Pr[X^{(0)}_{i}=B/2-\ell]$ , and that the probability is greater for values closer to $B/2$ . Observe that the first $B/4-k/2$ terms in the second sum of the last step are equal to the last $B/4-k/2$ terms by the symmetry of the distribution around $B/2$ (for $\ell=B/2+k/2$ , the term in the sum is equal to zero). Continuing the derivation and leveraging this symmetry, we get

	$\displaystyle\operatorname{TV}(X^{(0)}_{i},X^{(i)}_{i})$	$\displaystyle\leq k\cdot\Pr[X^{(0)}_{i}=B/4+k]+\sum_{\ell=B/4+k}^{B/2+k/2-1}(% \Pr[X^{(0)}_{i}=\ell]-\Pr[X^{(0)}_{i}=\ell-k])$
		$\displaystyle=k\cdot\Pr[X^{(0)}_{i}=B/4+k]$
		$\displaystyle+\sum_{\ell=0}^{k-1}(\Pr[X^{(0)}_{i}=B/2-k/2+\ell]-\Pr[X^{(0)}_{i% }=B/4+\ell])$
		$\displaystyle\leq 2k\cdot\Pr[X^{(0)}_{i}=B/2]$

where the first equality follows from the sum telescoping and the second inequality follows from bounding each term in the sum. Continuing, letting $X\sim\mathrm{Bin}(B,1/2)$ , we have that

	$\displaystyle 2k\cdot\Pr[X^{(0)}_{i}=B/2]$	$\displaystyle=2k\cdot\Pr\bigg{[}X=B/2\,\bigg{\|}\,\frac{B}{4}\leq X\leq\frac{3B% }{4}\bigg{]}=\frac{2k\cdot\Pr[X=B/2]}{1-2\Pr[X<B/4]}$
		$\displaystyle\leq\frac{2k\cdot\Pr[X=B/2]}{1-2\exp(-B/8)}\leq 6k\cdot\Pr[X=B/2]% =6k\cdot 2^{-B}\binom{B}{B/2}$
		$\displaystyle\leq 6k\cdot 2^{-B}\cdot\frac{\sqrt{2}\cdot 2^{B}}{\sqrt{\pi B}}=% \frac{6\sqrt{2}}{\sqrt{\pi}}\cdot\frac{k}{\sqrt{B}}=\frac{6\sqrt{2}}{\sqrt{\pi% }}\cdot T^{-1/20}\enspace,$

where all inequalities are valid for $T$ greater than some absolute constant, and the last inequality is a variant of Stirling’s inequality. We finally get

\operatorname{TV}(\mathbf{x},\mathbf{x}^{(i)})\leq\operatorname{TV}(\mathbf{x}% ,\mathbf{x}^{(0)})+\operatorname{TV}(\mathbf{x}^{(0)},\mathbf{x}^{(i)})\leq 2% \sqrt{T}\exp(-\sqrt{T}/8)+\frac{6\sqrt{2}}{\sqrt{\pi}}\cdot T^{-1/20}\leq 10% \cdot T^{-1/20}\enspace,

where the last inequality is true for $T\geq 400$ , thus proving the lemma. $\hfill\blacktriangleleft$ Using Lemma 29 and Lemma 30, we arrive at

	$\displaystyle\Pr[\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})\in E_{i}]$	$\displaystyle\geq\Pr[\mathrm{err}(\mathcal{M}(\mathbf{x}^{(i)}))\leq\alpha]% \cdot\Pr[\mathrm{err}(\mathcal{M}(\mathbf{x}^{(0)}))\leq\alpha]$
		$\displaystyle\geq\big{(}\Pr[\mathrm{err}(\mathcal{M}(\mathbf{x}))\leq\alpha]-% \operatorname{TV}(\mathbf{x}^{(i)},\mathbf{x})\big{)}$
		$\displaystyle\times\big{(}\Pr[\mathrm{err}(\mathcal{M}(\mathbf{x}))\leq\alpha]% -\operatorname{TV}(\mathbf{x}^{(0)},\mathbf{x})\big{)}$
		$\displaystyle\geq(3/4-\Delta^{\prime})(3/4-\Delta)\geq 1/2\enspace.$

where the last inequality holds for $T$ greater than an absolute constant. Next observe that $\mathbf{x}^{(i)}$ and $\mathbf{x}^{(0)}$ are $k$ -neighboring with probability 1, and so we have $\Pr[\mathrm{Alg}(\mathbf{x}^{(i)},\mathbf{x}^{(0)})\in E_{i}]\leq e^{k% \varepsilon}\Pr[\mathrm{Alg}(\mathbf{x}^{(0)},\mathbf{x}^{(0)})\in E_{i}]$ , and therefore $\Pr[\mathrm{Alg}(\mathbf{x}^{(0)},\mathbf{x}^{(0)})\in E_{i}]\geq e^{-k% \varepsilon}/2$ . Since all $E_{j}$ are disjoint, we get

\displaystyle 1\geq\sum_{j=1}^{m}\Pr[\mathrm{Alg}(\mathbf{x}^{(0)},\mathbf{x}^% {(0)})\in E_{j}]\geq m\cdot e^{-k\varepsilon}/2\enspace,

and therefore

\displaystyle k\geq\varepsilon^{-1}\log(m/2)\enspace.

Recalling that $m=T/B=\sqrt{T}$ , we thus have $k=\Omega(\varepsilon^{-1}\log T)$ and therefore $\alpha=k/4=\Omega(\varepsilon^{-1}\log T)$ . $\hfill\blacktriangleleft$

[bib.bib1] [1] Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/paper/2023/hash/99c41fb9fd53abfdd4a0259560ef1c9d-Abstract-Conference.html.

[bib.bib2] [2] Joel Daniel Andersson and Rasmus Pagh. Streaming private continual counting via binning. CoRR, abs/2412.07093, 2024. To appear in the proceedings of SaTML 2025. doi:10.48550/arXiv.2412.07093.

[bib.bib3] [3] Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy. CoRR, abs/2408.07021v1, 2024. Earlier (non-archival) version with a different title and set of authors. Presented at TPDP 2024. arXiv:2408.07021v1.

[bib.bib4] [4] Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 394–403. PMLR, 10–15 July 2018. URL: https://proceedings.mlr.press/v80/balle18a.html.

[bib.bib5] [5] G. Bennett. Schur multipliers. Duke Mathematical Journal, 44(3):603–639, 1977. doi:10.1215/S0012-7094-77-04426-X.

[bib.bib6] [6] Adrian Rivera Cardoso and Ryan Rogers. Differentially private histograms under continual observation: Streaming selection into the unknown. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 2397–2419. PMLR, 2022. URL: https://proceedings.mlr.press/v151/rivera-cardoso22a.html.

[bib.bib7] [7] T. H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams. In Simone Fischer-Hübner and Matthew Wright, editors, Privacy Enhancing Technologies, Lecture Notes in Computer Science, pages 140–159, Berlin, Heidelberg, 2012. Springer. doi:10.1007/978-3-642-31680-7_8.

[bib.bib8] [8] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and Continual Release of Statistics. ACM Transactions on Information and System Security, 14(3):26:1–26:24, November 2011. doi:10.1145/2043621.2043626.

[bib.bib9] [9] Christopher A. Choquette-Choo, Arun Ganesh, Ryan McKenna, H. Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A unified approach to private training. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL: http://papers.nips.cc/paper_files/paper/2023/hash/ecc28b4ce9b39f5f23c3efb03e25b7bf-Abstract-Conference.html.

[bib.bib10] [10] Christopher A. Choquette-Choo, Hugh Brendan McMahan, J. Keith Rush, and Abhradeep Guha Thakurta. Multi-epoch matrix factorization mechanisms for private machine learning. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 5924–5963. PMLR, 2023. URL: https://proceedings.mlr.press/v202/choquette-choo23a.html.

[bib.bib11] [11] Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Lower bounds for differential privacy under continual observation and online threshold queries. In Shipra Agrawal and Aaron 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.

[bib.bib12] [12] Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. Answering range queries under local differential privacy. Proc. VLDB Endow., 12(10):1126–1138, June 2019. doi:10.14778/3339490.3339496.

[bib.bib13] [13] Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 625–661. PMLR, 02–05 July 2022. URL: https://proceedings.mlr.press/v178/dagan22a.html.

[bib.bib14] [14] Sergey Denisov, H. Brendan McMahan, John Rush, Adam D. Smith, and Abhradeep Guha Thakurta. Improved differential privacy for SGD via optimal private linear operators on adaptive streams. In NeurIPS, 2022. URL: http://papers.nips.cc/paper_files/paper/2022/hash/271ec4d1a9ff5e6b81a6e21d38b1ba96-Abstract-Conference.html.

[bib.bib15] [15] Jinshuo Dong, Weijie J. Su, and Linjun Zhang. A central limit theorem for differentially private query answering. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 14759–14770, 2021. URL: https://proceedings.neurips.cc/paper/2021/hash/7c2c48a32443ad8f805e48520f3b26a4-Abstract.html.

[bib.bib16] [16] Krishnamurthy Dj Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 2306–2317. IEEE, 2024. doi:10.1109/FOCS61266.2024.00135.

[bib.bib17] [17] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, TCC’06, pages 265–284, Berlin, Heidelberg, 2006. Springer-Verlag. doi:10.1007/11681878_14.

[bib.bib18] [18] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Proceedings of the forty-second ACM symposium on Theory of computing, STOC ’10, pages 715–724, New York, NY, USA, June 2010. Association for Computing Machinery. doi:10.1145/1806689.1806787.

[bib.bib19] [19] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Proceedings, Part II, of the 21st International Conference on Advances in Cryptology — ASIACRYPT 2015 - Volume 9453, pages 735–751, Berlin, Heidelberg, 2015. Springer-Verlag. doi:10.1007/978-3-662-48800-3_30.

[bib.bib20] [20] Cynthia Dwork and Aaron Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends® in Theoretical Computer Science, 9(3-4):211–407, 2013. doi:10.1561/0400000042.

[bib.bib21] [21] Hendrik Fichtenberger, Monika Henzinger, and Jalaj Upadhyay. Constant matters: Fine-grained error bound on differentially private continual observation. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 10072–10092. PMLR, 23–29 July 2023. URL: https://proceedings.mlr.press/v202/fichtenberger23a.html.

[bib.bib22] [22] J. Gehrke, G. Wang, and X. Xiao. Differential privacy via wavelet transforms. In 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010), pages 225–236, Los Alamitos, CA, USA, March 2010. IEEE Computer Society. doi:10.1109/ICDE.2010.5447831.

[bib.bib23] [23] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Optimal noise-adding mechanism in additive differential privacy. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Naha, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 11–20. PMLR, 2019. URL: http://proceedings.mlr.press/v89/geng19a.html.

[bib.bib24] [24] Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. Tight analysis of privacy and utility tradeoff in approximate differential privacy. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 89–99. PMLR, 2020. URL: http://proceedings.mlr.press/v108/geng20a.html.

[bib.bib25] [25] Michael Hay, Vibhor Rastogi, Gerome Miklau, and Dan Suciu. Boosting the accuracy of differentially private histograms through consistency. Proc. VLDB Endow., 3(1–2):1021–1032, September 2010. doi:10.14778/1920841.1920970.

[bib.bib26] [26] Monika Henzinger, Nikita P. Kalinin, and Jalaj Upadhyay. Binned group algebra factorization for differentially private continual counting, 2025. arXiv:2504.04398.

[bib.bib27] [27] Monika Henzinger, Andrea Lincoln, and Barna Saha. The complexity of average-case dynamic subgraph counting. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 459–498. SIAM, 2022. doi:10.1137/1.9781611977073.23.

[bib.bib28] [28] Monika Henzinger and Jalaj Upadhyay. Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 2951–2970. SIAM, 2025. doi:10.1137/1.9781611978322.95.

[bib.bib29] [29] Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003–5039, 2023. doi:10.1137/1.9781611977554.ch183.

[bib.bib30] [30] Naoise Holohan, Spiros Antonatos, Stefano Braghin, and Pól Mac Aonghusa. The bounded laplace mechanism in differential privacy. J. Priv. Confidentiality, 10(1), 2020. doi:10.29012/JPC.715.

[bib.bib31] [31] James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP 2015), London, UK, 2:26–27, 2015.

[bib.bib32] [32] Ziyue Huang, Yuan Qiu, Ke Yi, and Graham Cormode. Frequency estimation under multiparty differential privacy: one-shot and streaming. Proceedings of the VLDB Endowment, 15(10):2058–2070, September 2022. doi:10.14778/3547305.3547312.

[bib.bib33] [33] Peter Kairouz, Brendan Mcmahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and Private (Deep) Learning Without Sampling or Shuffling. In Proceedings of the 38th International Conference on Machine Learning, pages 5213–5225. PMLR, July 2021. ISSN: 2640-3498. URL: https://proceedings.mlr.press/v139/kairouz21b.html.

[bib.bib34] [34] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 1376–1385, Lille, France, 07–09 July 2015. PMLR. URL: https://proceedings.mlr.press/v37/kairouz15.html.

[bib.bib35] [35] Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy. The VLDB Journal, 24(6):757–781, December 2015. doi:10.1007/s00778-015-0398-x.

[bib.bib36] [36] Fang Liu. Generalized gaussian mechanism for differential privacy. IEEE Trans. Knowl. Data Eng., 31(4):747–756, 2019. doi:10.1109/TKDE.2018.2845388.

[bib.bib37] [37] H. Brendan McMahan and Abhradeep Thakurta. Federated Learning with Formal Differential Privacy Guarantees, 2022. Accessed online 2023-05-15. URL: https://ai.googleblog.com/2022/02/federated-learning-with-formal.html.

[bib.bib38] [38] Wahbeh Qardaji, Weining Yang, and Ninghui Li. Understanding hierarchical methods for differentially private histograms. Proc. VLDB Endow., 6(14):1954–1965, September 2013. doi:10.14778/2556549.2556576.

[bib.bib39] [39] David M. Sommer, Sebastian Meiser, and Esfandiar Mohammadi. Privacy loss classes: The central limit theorem in differential privacy. Proc. Priv. Enhancing Technol., 2019(2):245–269, 2019. doi:10.2478/POPETS-2019-0029.

[bib.bib40] [40] Thomas Steinke and Jonathan R. Ullman. Between pure and approximate differential privacy. J. Priv. Confidentiality, 7(2), 2016. doi:10.29012/JPC.V7I2.648.

[bib.bib41] [41] Jalaj Upadhyay. Sublinear Space Private Algorithms Under the Sliding Window Model. In Proceedings of the 36th International Conference on Machine Learning, pages 6363–6372. PMLR, May 2019. ISSN: 2640-3498. URL: https://proceedings.mlr.press/v97/upadhyay19a.html.

[bib.bib42] [42] Staal Amund Vinterbo. Differential privacy for symmetric log-concave mechanisms. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 6270–6291. PMLR, 2022. URL: https://proceedings.mlr.press/v151/vinterbo22a.html.

Count on Your Elders: Laplace vs Gaussian Noise

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

1.1 Our contributions

Theorem 1.

Theorem 2.

Theorem 3 (Approximate DP for the Laplace Mechanism).

Theorem 4.

1.2 Overview of technical ideas

Improved tree-based mechanism

Factorization mechanism with Laplace noise

Lower bound for random inputs

1.3 Related work

2 Preliminaries

3 Mechanisms

3.1 Binary Tree Mechanisms

3.2 𝒌-ary Tree Mechanisms

Definition 5 (k-ary trees).

Definition 6 (k-ary representation of integer).

Lemma 7.

Proof.

Lemma 8.

Proof.

Theorem 9.

3.3 𝒌-ary trees with subtraction

Definition 10 (Offset k-ary representation of integers).

4 Proving Theorem 1

4.1 Privacy

Proposition 11.

Proof.

Proposition 12.

Proof.

Lemma 13.

Proof.

4.2 Utility

Lemma 14.

Proof.

Corollary 15.

4.3 Space and time complexity

Proposition 16.

Proof.

Lemma 17.

Proof.

Lemma 18.

Proof.

5 Laplace vs Gaussian noise

5.1 Laplace vs Gaussian noise for continual counting

Lemma 19.

Proof.

Proof of Theorem 2.

5.2 Laplace noise scaled to ℓ𝟐 sensitivity

Lemma 20 (Simplified version of Theorem 3.5 in [34]).

Lemma 21 (ℓ2 Laplace Mechanism).

Proof.

Corollary 22.

Proof.

Proof of Theorem 3.

6 Discussion

References

Appendix A Definitions for Differential Privacy

Definition 23 ((ε,δ)-Differential Privacy [20]).

Lemma 24 (Laplacian Mechanism [20]).

Lemma 25 (Gaussian Mechanism [20]).

Appendix B 𝒌-ary Tree Mechanisms: Proofs

Proof sketch of Theorem 9.

Appendix C Leveraging subtraction for even 𝒌

Definition 26 (Offset (even) k-ary representation of integers).

Claim 27.

Proof sketch..

Corollary 28.

3.2 $𝒌$ -ary Tree Mechanisms

Definition 5 ( $k$ -ary trees).

Definition 6 ( $k$ -ary representation of integer).

3.3 $𝒌$ -ary trees with subtraction

Definition 10 (Offset $k$ -ary representation of integers).

5.2 Laplace noise scaled to $\ell_{2}$ sensitivity

Lemma 21 ( $\ell_{2}$ Laplace Mechanism).

Definition 23 ( $(\varepsilon,\delta)$ -Differential Privacy [20]).

Appendix B $𝒌$ -ary Tree Mechanisms: Proofs

Appendix C Leveraging subtraction for even $𝒌$

Definition 26 (Offset (even) $k$ -ary representation of integers).