A Fast Gaussian Mechanism under Continual Observation, with Applications
arXiv:2606.11760v1 [cs.DS] 10 Jun 2026
RASMUS PAGH, BARC, University of Copenhagen, Denmark SIA SEJER, BARC, University of Copenhagen, Denmark We consider the problem of privately releasing a 𝑘-dimensional vector under updates: Starting with a zero vector, at times 𝑡 1, 𝑡 2, . . . the vector is updated by adding 𝑥 (1) , 𝑥 (2) , . . . , respectively. For positive integers 𝑇 , 𝑘 we model the updates as a data set {(𝑡𝑖 , 𝑥 (𝑖 ) )}𝑖 , where 𝑡𝑖 ∈ [𝑇 ] and 𝑥 (𝑖 ) ∈ 𝐵𝑘 (the 𝑘-dimensional unit ball). Two such data sets are said to be neighboring if their symmetric difference has size at most 1. The continual release Í consists of the sum 𝐴 (𝑡 ) = 𝑖 : 𝑡𝑖 ≤𝑡 𝑥 (𝑖 ) for each time step 𝑡 = 1, . . . ,𝑇 . Classical continual release techniques allow us to release an approximation of 𝐴 (1) , . . . , 𝐴 (𝑇 ) with additive noise of magnitude polylog(𝑇 ), computed in time O (𝑘𝑇 ), even in the on-line, adaptive case where data is continually revealed for the current time step. Motivated by private sketching techniques, we consider the setting where only a subset of entries in 𝐴 (𝑡 ) need to be released at time step 𝑡. Our new result is that it is possible to sample any desired entry in a given noise vector in constant time while reproducing exactly the distribution of the binary tree mechanism with Gaussian noise. The improvement on the known time bound of O (log𝑇 ) comes from a new data structure that allows us to sample a new noise value with the correct correlations in constant time using Brownian bridges. We present two data management applications, of independent interest, that use our technique in conjunction with differentially private CountSketches: 1) A dynamic data structure for orthogonal range counting queries with a better privacy/accuracy/space trade-off than previous data structures, and 2) Join size estimation, where in addition we show improved high-probability bounds. CCS Concepts: • Security and privacy → Privacy protections. Additional Key Words and Phrases: Differential Privacy, Continual Observation, Sketching, Range Counting, Join Size Estimation
1
Introduction
Differential privacy provides a strong information-theoretic guarantee of privacy with a tunable trade-off between privacy and utility, measured by the magnitude of noise added to query answers. It is relevant in settings where data points may reveal sensitive information about individuals. The standard way of making a single 𝑘-dimensional vector private is by adding independent noise (e.g., zero-mean Gaussians) to its entries before release. In the continual observation setting, releases are interleaved with bounded-norm updates to the vector, and we want the whole sequence of vectors to be differentially private. One way to handle this, with good dependence on the number of queries, is to instantiate 𝑘 versions of the classical binary mechanism of Dwork, Naor, Pitassi, and Rothblum [16]. This approach yields noise of magnitude polylog(𝑇 ) over 𝑇 time steps, but updates all 𝑘 noise values at each time step and thus requires Ω(𝑘) time per release. This is optimal if we wish to release the whole vector at each step. However, updates may be sparse and full releases may be replaced by queries that release only certain vector entries. In this case we can hope to optimize query and update time to depend on the number of distinct times a vector entry is queried and updated. Sketches under continual observation. A canonical example of a sparse update/sparse query setting is private sketching. Applying continual observation to private linear sketches has previously been considered by Epasto, Mao, Medina, Mirrokni, Vassilvitskii, and Zhong [18], but their technique requires updating every sketch entry in each time step, making it inefficient in settings where sketches are large. Holland [22] developed a technique in which sketch updates are buffered and Authors’ Contact Information: Rasmus Pagh, [email protected], BARC, University of Copenhagen, Denmark; Sia Sejer, [email protected], BARC, University of Copenhagen, Denmark.
2
Rasmus Pagh and Sia Sejer
carried out in batches when the number of updates matches the sketch size. While this improves time complexity, buffering updates introduces significant error for large sketches. In this paper we show that such trade-offs are not necessary. Our main result is the Fast Gaussian Mechanism under Continual Observation (FastGaMe), a time-efficient implementation of the binary tree mechanism of [16] in the Gaussian noise setting. FastGaMe only materializes the noise values that are actually queried, and generates each such noise value in constant time. This implies that any sketch can be implemented with continual observation noise and the same asymptotic time complexity as in the non-private setting. Like in [18, 22] the space usage grows by a factor Θ(log𝑇 ), where 𝑇 is the number of time steps. Applications using CountSketch. We show two applications of FastGaMe, both based on Private CountSketch, recently studied by Pagh and Thorup [34] and Zhao, Qiao, Redberg, Agrawal, Abbadi, and Wang [40]. This sketch approximately represents a sparse vector under single-entry updates and queries, where each update and query only involves a small number of values from the sketch. The applications are key primitives in data management: • Private dynamic orthogonal range counting. Given a dynamically changing point set in [𝐵]𝑑 , we seek to maintain a differentially private index that supports orthogonal range counting queries (points satisfying a conjunction of range predicates). Past work has relied on representing sparse vectors using additive noise with thresholding, and has supported dynamic updates only through expensive rebuilding techniques. The combination of FastGaMe and Private CountSketch significantly improves the time and space complexity achievable by past techniques while also providing a stronger privacy/utility guarantee (see Figure 1 for an overview). • Continual join size estimation. Given two dynamically changing relations, we wish to privately maintain an estimate of their join size. Maintaining a CountSketch for the join attributes of each relation allows such estimates to be maintained in small space, but to our knowledge this problem has not been studied in the private setting, let alone the continual observation setting. We give bounds for the join size estimation accuracy achievable using Private CountSketch and show that the combination with FastGaMe allows such estimates to be maintained in constant time per update with space only slightly larger than in the non-private setting. 1.1
Related Work
Continual release of a counter. Continual counting is the basic problem of releasing, after each bounded size update of a scalar value, an approximation of the value while preserving the privacy of individual updates. This problem and its generalization to 𝑘-dimensional bounded-norm vector updates is one of the canonical examples of privacy under continual observation, and is often used as a primitive in other continual-release algorithms. The classical approach is the binary tree mechanism of Dwork, Naor, Pitassi, and Rothblum [16] and the closely related construction of Chan, Shi, and Song [9], in which each output is represented as the sum of a logarithmic number of noisy dyadic partial sums. Both approaches give polylogarithmic error over a horizon of length 𝑇 , forming the standard baseline for continual release. Recent work has improved these results by providing tighter constant factors, for example: Henzinger, Upadhyay, and Upadhyay [20] gave nearly tight bounds for continual counting (with noise value generation in time O (𝑇 log𝑇 )), while Andersson and Pagh [3] presented a variant that reduced the variance while allowing all 𝑇 additive noise values to be generated in time O (𝑇 ). Private Linear Sketching. Linear sketches are a central tool for summarizing high-dimensional frequency vectors under streaming updates, with CountSketch [11] being a canonical example
A Fast Gaussian Mechanism under Continual Observation, with Applications
3
that supports unbiased point queries and self-join size estimation from a small randomized linear summary. Privacy for sketches has been studied both in the pan-private streaming model, where the internal state of the algorithm must remain private against intrusions [32], and in settings where a sketch is made differentially private by perturbing its counters (this paper considers the latter). Recent work on Private CountSketch shows that adding appropriately calibrated noise to the sketch entries yields private sparse-vector representations with strong accuracy guarantees for point queries and downstream estimation tasks [34, 40]. Related private heavy-hitters methods that are not linear sketches include the private Misra– Gries algorithm of Lebeda and Tetěk [28], which combines a deterministic frequency summary with privacy-preserving noise, and the differentially private weighted-sampling framework of Cohen, Geri, Sarlós, and Stemmer [12], which provides another compact summary for private vector and frequency estimation. These methods work well in settings where data can only be inserted, in contrast to private linear sketches which also support deletions, and have not been shown to work in continual observation settings. Linear Sketching under Continual Observation. The closest prior work on private linear sketches under continual observation is due to Epasto et al. [18], who study the continual release of frequency-moment estimates in insertion-only streams. Their algorithms combine streaming sketches with continual-release primitives for counts, distinct elements, heavy hitters, and lowfrequency elements, and obtain near-optimal space bounds up to polylogarithmic factors. However, they use the standard way of applying continual observation to the sketch vector, which requires updating the noise for every sketch cell at every time step. More recently, Holland [22] considered this computational bottleneck directly and proposed a scalable framework for differentially private sketches under continual observation. Their method groups stream updates into batches and applies lazy sketch updates, reducing the per-update cost relative to maintaining a fully updated noisy sketch at every time step. This makes continual observation sketches more practical for highthroughput streams, especially for heavy-hitter detection, but the buffering step also creates an additional approximation term that grows with the sketch size, limiting what precision is possible. Private Orthogonal Range Counting Queries. An orthogonal range counting query finds the number of tuples in a database that satisfy range predicates on up to 𝑑 designated attributes. Under widely held assumptions, even the decision problem of determining whether or not a range is empty requires near-linear query time when 𝑑 = Ω(log 𝑛) and updates must be polynomial time [1, 10]. We thus focus our discussion on the more feasible case where 𝑑 is constant. Xiao, Wang, and Gehrke [38] and Chan, Shi, and Song [9] independently proposed similar solutions with error polylogarithmic in the number of queries in the static case where updates are not allowed. The size of both data structures is O 𝐵𝑑 which may in general be much larger than the size 𝑛 of the dataset. Improved space and error bounds for the “sparse data” setting were obtained by Dwork, Naor, Reingold, and Rothblum [17]. When 𝐵 ≫ 𝑛 they use a reduction that transforms points in [𝐵]𝑑 to points in [𝑛]𝑑 at the cost of additive error O (log(𝐵)/𝜀), where 𝜀 is the privacy parameter. Applied to this smaller problem, the techniques of [9, 38] have query time that grows only logarithmically with 𝐵 and use space 𝑛𝑑 . To further reduce space, they propose a pruning technique that removes all small noisy counts in the multi-dimensional tree, reducing space to O 𝑛(log 𝑛)𝑑 at the cost of increasing error. Past upper bounds were for 𝜀-differential privacy, but in this paper we focus on the more modern 𝜌-zero-concentrated differential privacy (zCDP) notion which results in better error bounds under composition. To make these bounds more easily comparable, we set 𝜌 = 𝜀 2 /2, the zCDP parameter implied by 𝜀-differential privacy. In the dynamic case we wish to provide privacy in the continual observation setting: Start with the empty point set and perform 𝑛 updates (insertion or deletion of a point) with arbitrarily many
4
Rasmus Pagh and Sia Sejer
Reference
Privacy
Maximum error
Space
[38] + [35] [17] + [35]
𝜀-DP 𝜀-DP
(log 𝐵) 1.5𝑑+1 (log 𝑛) 3+𝜂 /𝜀
𝐵𝑑 log(𝑛) 𝑛(log 𝑛)𝑑+1
[33] + [30]
1 (𝜀, 100 )-DP
This paper
𝜀 2 /2-zCDP
(log(𝐵) + (log 𝑛) 1.5𝑑+2 ) (log 𝑛) 3+𝜂 /𝜀 Ω (log 𝑛)𝑑 −1 /𝜀 Ω (log 𝐵)𝑑 −1 /𝜀 𝐸 ≥ (log 𝐵)𝑑+2 log(𝑛)/𝜀
any 𝑛(log 𝐵)𝑑+1 log(𝑛)/𝐸
Fig. 1. Overview of results on dynamic private orthogonal range counting with 𝑛 insertions/deletions of points in [𝐵]𝑑 . Lower bounds hold for worst-case static inputs and are expressed in terms of 𝑛 or 𝐵 with no restriction on the other parameter. They hold under approximate DP and in particular for 𝜀 2 /2-zCDP. For simplicity, we assume that both 𝑑 and the privacy parameter 𝜀 are O (1), and order-notation is suppressed. Maximum error upper bounds hold with probability 1 − 1/𝐵. All listed static data structures support an orthogonal range counting query in time O (log 𝐵)𝑑 or O (log 𝐵)𝑑+1 . After each update, an arbitrary number of queries can be performed with query time O (log 𝐵)𝑑+1 .
queries asked between updates, with a privacy guarantee for each point update over all query answers. Figure 1 gives an overview of data structures for dynamic private orthogonal range counting in the grid [𝐵]𝑑 . Qiu and Yi [35] recently presented a general transformation from static to dynamic data structures under continual observation for a wide class of private data structures. Applying their technique to the data structure of Chan et al. [9] and the low-space data structure of Dwork et al. [17] yields the results stated in the first two lines of Figure 1. Using the discrepancy method introduced by Muthukrishnan and Nikolov [33], lower bounds for private range counting can be derived from lower bounds on the hereditary discrepancy of axis-parallel rectangles. Building on this framework, Matoušek, Nikolov, and Talwar [30] showed that rectangle workloads over 𝑛 points in R𝑑 and over the grid [𝐵]𝑑 have hereditary discrepancy Ω (log 𝑛)𝑑 −1 and Θ((log 𝐵)𝑑 −1 ), respectively. Via the discrepancy–privacy reduction, this implies that any (𝜀, 𝛿)-DP mechanism with sufficiently small 𝛿 must incur worst-case error at least Ω (log 𝑛)𝑑 −1 /𝜀 (for some large enough 𝐵) or Ω (log 𝐵)𝑑 −1 /𝜀 (for some large enough 𝑛). Thus, the error upper bounds in Figure 1 are close to optimal up to polylogarithmic factors. Sketch-based Join Size Estimation. Sketch-based join size estimation was first studied in the seminal work of Alon, Gibbons, Matias, and Szegedy [2], who observed that the size of an equi-join can be estimated from linear sketches of the join-attribute frequency vectors. In this approach, each relation is summarized by a randomized sketch, and the join size is estimated as an inner product of the two sketches. The linearity of the sketch makes the estimator naturally compatible with dynamic updates, since insertions and deletions only require updating the sketch entries touched by the changed tuple. This idea has led to a large body of work on faster, smaller, and more accurate join-size sketches, including recent algorithms that improve the space–accuracy tradeoff and support efficient sketch maintenance under turnstile updates [21, 27, 36, 37]. These works are closest to our non-private baseline: they show that join-size estimates can be maintained quickly under dynamic updates, but do not provide privacy guarantees. Private join-size estimation has mostly been studied in different privacy models or as part of broader private query-processing systems. For example, Zhang, Liu, and Yin [39] study join-size estimation from locally randomized user reports, and PrivateSQL [25] provides a differentially private SQL engine that can answer relational queries involving join size queries. These works are complementary to ours: they address private join estimation or private SQL query answering, but not the problem of maintaining a sketch-based join-size estimator under central continual observation with dynamic updates.
A Fast Gaussian Mechanism under Continual Observation, with Applications
1.2
5
Definitions
An overview of standard privacy-related definitions used in the paper can be found in Section A. Problem definition and notation. For positive integer 𝑐, we use [𝑐] to denote the set {1, · · · , 𝑐}. For parameters 𝑝 ∈ {1, 2}, Δ𝑝 > 0 and integer 𝑛, consider a data set 𝑋 = (𝑡𝑖 , 𝑥 (𝑖 ) ) : 𝑖 ∈ [𝑛] , where 𝑡𝑖 ∈ Z, 𝑥 (𝑖 ) ∈ R𝑘 with 𝑥 (𝑖 ) 𝑝 ≤ Δ𝑝 for all 𝑖. Two data sets are ℓ𝑝 neighboring if and only if they have symmetric difference of size at most 1. In other words, we consider unbounded neighboring datasets with ℓ𝑝 -bounded updates. We will almost exclusively consider the more powerful ℓ2 updates, but discuss ℓ1 updates when comparing to the classical Laplace binary tree mechanism. Í We consider the private release of 𝐴 (𝑡 ) = 𝑖 : 𝑡𝑖 ≤𝑡 𝑥 (𝑖 ) for 𝑡 = 1, . . . ,𝑇 . This can be thought of as the continual release of a vector 𝐴 that is incremented by a vector 𝑥 (𝑖 ) at time 𝑡𝑖 (with several updates being possible at each time step). A query at time step 𝑡 for entry 𝑖 ∈ [𝑘] releases 𝐴𝑖(𝑡 ) plus an additive noise term. Any number of queries may be performed at each time step 𝑡, and we seek privacy guarantees that hold without restrictions on queries. Updates must respect the timing of queries in the sense that once a time step has been queried, updates are only possible after that timestamp. Updates can skip time steps, jumping ahead any number of steps. CountSketch. A CountSketch [11] with 𝑡 repetitions and table size 𝑏 uses random hash functions ℎ 1, . . . , ℎ𝑡 : [𝑑] → [𝑏], and random sign functions 𝑠 1, . . . , 𝑠𝑡 : [𝑑] → {−1, +1}. The CountSketch of 𝑥, Í consisting of 𝑡 “rows” CS1 (𝑥), . . . , CS𝑡 (𝑥) ∈ R𝑏 has entries defined by CS𝑖 (𝑥) 𝑗 = 𝑎:ℎ𝑖 (𝑎)=𝑗 𝑠𝑖 (𝑎)𝑥𝑎 . Given a CountSketch CS𝑖 (𝑥), an unbiased estimator for 𝑥𝑎 is median𝑖 (𝑠𝑖 (𝑎) CS𝑖 (𝑥)ℎ𝑖 (𝑎) ). The basic analysis of the error of this estimator only relies on pairwise independence of hash functions [11], but some more precise analyses assume the hash functions to be fully random [31]. In this paper we will mostly assume full randomness, since this aspect is not our main focus, but we believe that all bounds can be realized with hash functions having constant independence. Private CountSketch. A Private CountSketch is a CountSketch where each sketch entry is ˜ perturbed with independent Gaussian noise. That √ is, it has rows CS𝑖 (𝑥) = 𝐶𝑆𝑖 (𝑥) + 𝜈𝑖 where 2 𝜈𝑖 ∼ N 0, 𝜎 𝐼𝑏 . CountSketch has ℓ2 sensitivity 𝑡 and therefore Private CountSketch satisfies 𝜌-zero-concentrated differential privacy with 𝜌 = 2𝜎𝑡 2 . Its utility was first studied by [34, 40], where the latter gave a precise analysis of the error distribution of single-entry estimates 𝑥˜𝑎 obtained from Private CountSketch. 1.3
Technical Overview
New Analysis of the Binary Tree Mechanism (Section 2). Our Fast Gaussian Mechanism under Continual Observation (FastGaMe) is based on the binary tree mechanism for continual counting due to Dwork, Naor, Pitassi, and Rothblum [16]. Their method assigns independent noise values to the nodes in a complete binary tree and outputs 𝐴 (𝑡 ) with noise obtained from summing the noise of all nodes on the path from the root to leaf number 𝑡. Unlike [16] we use the binary tree mechanism with Gaussian noise rather than Laplace noise, a combination we refer to as M𝐵𝑇 . Some tree-based continual counting mechanisms have an explicit strategy matrix in the factorization (matrix) mechanism framework of Li, Miklau, Hay, McGregor, and Rastogi [29], e.g. [9]. However, the strategy matrix of M𝐵𝑇 has not been studied in the literature to the best of our knowledge, so in Section 2 we provide such an analysis. Surprisingly, this classical approach improves several binary tree-based methods that have been proposed later [3, 23]. Fast Gaussian Mechanism (Section 3). We show how to exploit the structure of noise addition in M𝐵𝑇 to efficiently simulate the mechanism when many noise values are skipped and never accessed. We assume a standard Word RAM supporting constant-time rank/select on O (log𝑇 )-bit
6
Rasmus Pagh and Sia Sejer
words (see Section A). It is simple to do “on demand” sampling of entries of M𝐵𝑇 in logarithmic time by maintaining the noise values on the path to the most recently released leaf. It is also straightforward to generate the sequence of all noise values in linear time. Our contribution is a new method for sampling from the same distribution in constant time per value, regardless of how many time steps have passed since the last noise value was released. The key idea is to maintain a data structure representing the conditional distributions implied by previous noise releases, and show how one can sample from any such conditional distribution in constant time using a combination of word-level parallelism and Brownian bridges. The latter technique has previously been used in “lossless multiple release” settings where several releases at different privacy levels must be correlated to ensure good combined privacy guarantees [5, 26]. Orthogonal range counting (Section 4). We use a standard dyadic decomposition that conceptually reduces the orthogonal range counting problem to that of representing a collection of sparse vectors containing counts for fixed dyadic ranges. Instead of relying on classical “noise and threshold” techniques [6, 13, 24] to represent these vectors, we use a collection of Private CountSketches [34, 40]. This combination, which does not seem to have been explored in the literature, has multiple advantages: 1) The estimate from each sketch is unbiased and independent, so the total error when summing estimates benefits from cancellation of errors, 2) The sketch size can be chosen such that the error from sketching matches the error from privacy noise, significantly reducing space usage, and 3) Since sketches are linear, continual observation techniques including FastGaMe can be applied. An interesting aspect of our analysis is that it relies on an ℓ1 error guarantee rather than the usual ℓ2 error guarantee of CountSketch — we show how this guarantee is a consequence of the residual ℓ2 guarantee of [34]. We stress that the improvement in Figure 1 comes from algorithmic advances rather than from adapting a relaxed privacy notion, and would persist if all results were cast in the same privacy notion. Join Size Estimation (Section 5). Our results on join size estimation in Section 5 can be seen as a private version of the CountSketch bounds of Larsen, Pagh, and Tetěk [27]. To generalize this to Private CountSketch, we need to take into account the bilinear error stemming from sketch error multiplied by noise error, as well as the error stemming from multiplying noise terms with each other. We also extend the analysis of [27] to allow high-probability bounds rather than just variance and moment bounds, even when the number of repetitions is a small constant. This enables high probability bounds on join size estimates under continual observation. 2
Binary Tree Mechanism with Gaussian Noise
We revisit the classical binary tree mechanism of Dwork, Naor, Pitassi, and Rothblum [16]. They considered the problem of privately releasing estimates of sums 𝐴 (𝑡 ) with an ℓ1 neighboring relation (𝑝 = 1) as defined in Section 1.2. Traditionally this problem was considered in the setting where all timestamps 𝑡𝑖 were distinct numbers in [𝑇 ] (so that the input can be considered an input stream) and for 𝑘 = 1, but the privacy guarantees hold even for the more general setting with repeated timestamps and vectors in R𝑘 . Without loss of generality we assume that 𝑇 > 1 is a power of two. The binary tree mechanism is defined in terms of a complete, rooted binary tree with 𝑇 leaves numbered 0, . . . ,𝑇 − 1. We associate a noise variable 𝑁 𝑣 with each node 𝑣 of the tree, and let 𝑃 𝑣 denote the set of nodes on the path from the root node to 𝑣. The mechanism releases the Í estimate 𝐴˜ (𝑡 ) = 𝐴 (𝑡 ) + 𝑣 ∈𝑃𝑡 𝑁 𝑣 . In the matrix factorization framework of [29], this corresponds to a mechanism with reconstruction matrix 𝐿 where 𝐿𝑡,𝑣 = 1 if 𝑣 ∈ 𝑃𝑡 and 𝐿𝑡,𝑣 = 0 otherwise and unspecified strategy matrix 𝑅 such that 𝐿𝑅 is the lower-triangular all-1s counting matrix. Figure 2 shows such a factorization for 𝑇 = 4.
A Fast Gaussian Mechanism under Continual Observation, with Applications
1 © 1 𝐿𝑅 = 1 «1
1 1 0 0
0 0 1 1
1 0 0 0
0 1 0 0
0 0 1 0
0 ª 0® ® 0® 1¬
1/2 © 0 1/2 1/2 1/2 0 « 0
1/2 0 1/2 −1/2 1/2 0 0
7
1/2 −1/2 0 0 0 1/2 1/2
1/2 −1/2ª® ® 0 ® ® 0 ® ® 0 ® ® −1/2® 1/2 ¬
Fig. 2. Factorization with reconstruction matrix 𝐿 and strategy matrix 𝑅 for the binary tree mechanism with 𝑇 = 4. Columns/rows follow the natural breadth-first order, input coordinates are ordered from left to right.
Dwork et al. [16] showed, without presenting a strategy matrix, that if 𝑁 𝑣 ∼ Lap((log2 (𝑇 ) +1)/𝜀) the sequence 𝐴˜ (1) , . . . , 𝐴˜ (𝑇 ) of estimates satisfies 𝜀-differential privacy under the ℓ1 neighboring relation. In turn, this implies that it satisfies 𝜌-zero-concentrated differential privacy with 𝜌 = 𝜀 2 /2 [7]. The variance of each estimate is Var[𝐴˜ (𝑡 ) ] = 2(log2 (𝑇 ) + 1) 3 /𝜀 2 = (log2 (𝑇 ) + 1) 3 /𝜌. In this paper we consider the binary tree mechanism with Gaussian noise, that is, 𝑁 𝑣 ∼ N (0, 𝜎 2 ), under 𝜌-zero-concentrated differential privacy and the ℓ2 neighboring relation (𝑝 = 2). For simplicity we present the argument for scalars (𝑘 = 1) but all arguments remain valid for vectors in R𝑘 . It is clear that Var[𝐴˜ (𝑡 ) ] = (log2 (𝑇 ) + 1)𝜎 2 , so what remains is to figure out how 𝜎 should depend on 𝜌 and 𝑇 . By describing an explicit strategy matrix (as a linear transformation) we find that 𝜎 2 = (log2 (𝑇 ) + 2)/(8𝜌) suffices. It is interesting to compare the resulting maximum variance to that of other classical binary tree-based mechanisms. For example, the mechanism of Chan et al. [9] has a less symmetric factorization where the sensitivity of leaves varies between 1 and log𝑇 , meaning that noise must be scaled to the highest sensitivity. Andersson and Pagh [3] showed how a more symmetric method, the smooth binary mechanism, achieves smaller error by only using a small subset of the leaves. Our method matches the asymptotic error of this much more complicated mechanism, and eliminates a lower-order term in the error bound that is significant for small 𝑇 . We defer the details of the factorization and its analysis to Section B. 3 Fast Gaussian Mechanism for Continual Observation For simplicity we consider the case where 𝑘 = 1 such that the maintained vector aggregate satisfies 𝐴 (𝑡 ) ∈ R at time 𝑡. Like in Section 2 we can extend the data structure to arbitrary 𝑘 > 1 by running it independently for each coordinate. The 𝑖th update has timestamp 𝑡𝑖 , where we assume monotonicity, i.e., 𝑡 1 ≤ 𝑡 2 ≤ 𝑡 3 ≤ . . . . Queries are always with respect to the aggregate 𝐴 (𝑡 ) at the time 𝑡 of the latest update. Recall that once 𝐴 (𝑡 ) has been queried, no further updates with timestamp 𝑡 are allowed. We next describe how to extend the Gaussian binary tree mechanism with a data structure that allows constant time noise generation. The idea is to maintain and lazily sample prefix sums along the current “active root-to-leaf path”: For a query at time 𝑡 ∈ {1, . . . ,𝑇 }, we define the active path as the path from the root to the leaf labeled bin(𝑡 − 1). When a query is performed at time 𝑡, the data structure is updated such that it can output noise value 𝜈 (𝑡 ) having the same joint distribution with previous noise values as in the Gaussian binary tree mechanism. Our data structure consists of: (1) the timestamp 𝑙 of the last time a query was made to 𝐴, (2) a zero-indexed bit vector 𝑤 (𝑙 ) ∈ {0, 1}log(𝑇 )+1 where 𝑤 𝑗(𝑙 ) = 1 if and only if the prefix sum at level 𝑗 on the active path has been sampled at time 𝑙, and
8
Rasmus Pagh and Sia Sejer
(3) a zero-indexed vector 𝑃 (𝑙 ) ∈ Rlog(𝑇 )+1 where 𝑃 𝑗(𝑙 ) stores the level-𝑗 prefix sum on the active path whenever 𝑤 𝑗(𝑙 ) = 1 (these are described as “valid”; entries with 𝑤 𝑗(𝑙 ) = 0 are “invalid” and undefined). (𝑙 ) Note that 𝑃log(𝑇 exactly matches the noise of the Gaussian binary tree mechanism at step 𝑙. For a ) Í bit vector 𝑣 ∈ {0, 1}∗ and 𝑐 ≤ |𝑣 | let rank𝑐 (𝑣) = 𝑐𝑖=1 𝑣𝑖 be the number of 1s in the first 𝑐 bits of 𝑣 and let select𝑖 (𝑣) = min{𝑐 : rank𝑐 (𝑣) ≥ 𝑖} be the position of the 𝑖th 1 in 𝑣. We use bin(𝑧) to denote the log2 (𝑇 )-bit string encoding 𝑧 ∈ {0, . . . ,𝑇 − 1} in binary. Based on the above data structure, whose operations are discussed below, we show the following result:
Theorem 3.1. For 𝑇 > 0 a power of 2, assume that a machine word has size Ω(log(𝑇 )) and rank/select operations on a bit vector of size O (log(𝑇 )) are supported in O (1) worst-case time. For every choice of 𝜎 2 > 0 there exists a sequence of noise values 𝜈 (1) , . . . , 𝜈 (𝑇 ) with the following properties: • For all 𝑡 ∈ [𝑇 ], 𝜈 (𝑡 ) ∼ N 0, (log(𝑇 ) + 1)𝜎 2 , • for all 𝑡 1, 𝑡 2 ∈ [𝑇 ], 𝐶𝑜𝑣 (𝜈 (𝑡1 ) , 𝜈 (𝑡2 ) ) = (|𝑚| + 1)𝜎 2 where 𝑚 is the longest common prefix of bin(𝑡 1 − 1) and bin(𝑡 2 − 1), and • for every sequence 𝑡 1 ≤ 𝑡 2 ≤ 𝑡 3 ≤ . . . , the sequence of values 𝜈 (𝑡 𝑗 ) , 𝑗 = 1, 2, 3, . . . can be computed in O (1) worst-case time per sample using a data structure DS of O (log(𝑇 )) words. We can assume without loss of generality that 𝑡 1 < 𝑡 2 < 𝑡 3 < . . . since repeated queries for (𝑙 ) the same noise value are answered by returning 𝑃log(𝑇 . It is easy to see that the noise vector ) 𝜈 = (𝜈 (1) , . . . , 𝜈 (𝑇 ) ) has the same covariance matrix as that of the Gaussian binary tree mechanism, which has covariance between two noise values determined by the number of shared nodes on the paths to the corresponding leaves. Since a Gaussian distribution is uniquely determined by its mean (in this case zero) and covariance matrix, the noise vector 𝜈 has the same distribution as in the Gaussian binary tree mechanism. As argued in Section 2 setting 𝜎 2 = (log2 (𝑇 ) + 2)/(8𝜌) ensures 𝜌-zCDP under updates with ℓ2 sensitivity 1, and in general 𝜎 2 should be scaled according to the squared ℓ2 sensitivity. Data structure and update rule. Let ℎ = log2 (𝑇 ), and index the levels of the binary tree by 𝑗 ∈ {0, 1, . . . , ℎ}, where level 0 is the root and level ℎ consists of the leaves. We use 𝑏 (𝑡) = bin(𝑡 − 1) as the label of the leaf 𝑡, and let (𝑏 (𝑡) ≤ 𝑗 denote the prefix of length 𝑗, corresponding to the ancestor on the 𝑗th level. In the Gaussian binary tree mechanism we can use these prefixes to index node Í noise such that the noise released at time 𝑡 is 𝜈 (𝑡 ) = ℎ𝑗=0 𝜂𝑏 (𝑡 ) ≤ 𝑗 , where the variables 𝜂𝑠 ∼ N (0, 𝜎 2 ) are independent over all 𝑠. Equivalently, if 𝑆𝑡 ( 𝑗) =
𝑗 ∑︁
𝜂𝑏 (𝑡 ) ≤𝑟 ,
0 ≤ 𝑗 ≤ ℎ,
𝑟 =0
then the released noise is 𝜈 (𝑡 ) = 𝑆𝑡 (ℎ). The data structure will store only partial sums along the currently active root-to-leaf path. After the most recent query time 𝑙, the state is 𝐷𝑆 = ⟨𝑙, 𝑤 (𝑙 ) , 𝑃 (𝑙 ) ⟩. If 𝑤 𝑗(𝑙 ) = 1, then 𝑃 𝑗(𝑙 ) stores the sampled value of 𝑆𝑙 ( 𝑗) on the active path to 𝑏 (𝑙), and if 𝑤 𝑗(𝑙 ) = 0, the corresponding entry of 𝑃 (𝑙 ) is undefined (and ignored). The bit vector fits in one machine word, and the vector 𝑃 (𝑙 ) uses log(𝑇 ) + 1 words. We now describe how to answer a query at time 𝑡 ≥ 𝑙. The case 𝑡 = 𝑙 was discussed above. If this is the first query (i.e., 𝑙 is not set), we sample 𝑃 0(𝑡 ) ∼ N (0, 𝜎 2 ),
𝑃ℎ(𝑡 ) = 𝑃0(𝑡 ) + 𝑍,
𝑍 ∼ N (0, ℎ𝜎 2 ),
A Fast Gaussian Mechanism under Continual Observation, with Applications
9
with 𝑍 independent of 𝑃0(𝑡 ) . Next, we set 𝑤 0(𝑡 ) = 𝑤ℎ(𝑡 ) = 1, mark all other entries invalid, store the two sampled values in 𝑃 (𝑡 ) , and return 𝑃ℎ(𝑡 ) . (An initial cost of O (log𝑇 ) for creating 𝑃 (𝑡 ) can be avoided by lazy initialization.) This is exactly the joint distribution of (𝑆𝑡 (0), 𝑆𝑡 (ℎ)). It remains to handle the case 𝑡 > 𝑙, where 𝑙 is set. We create 𝑃 (𝑡 ) by updating 𝑃 (𝑙 ) . Let 𝑢 be the longest common prefix of 𝑏 (𝑙) and 𝑏 (𝑡), and write 𝑚 = |𝑢 |. The old and new active paths agree up to level 𝑚 and are disjoint below level 𝑚. Thus, the only value from the old path that is needed for the new path is the shared prefix sum 𝑆𝑙 (𝑚) = 𝑆𝑡 (𝑚). If 𝑤𝑚(𝑙 ) = 1, this shared value is already stored as 𝑃𝑚(𝑙 ) . Otherwise, let 𝑎 = max{ 𝑗 < 𝑚 : 𝑤 𝑗(𝑙 ) = 1},
𝑐 = min{ 𝑗 > 𝑚 : 𝑤 𝑗(𝑙 ) = 1}.
The sentinel values 𝑤 0(𝑙 ) = 𝑤ℎ(𝑙 ) = 1 ensure that such indices exist whenever 𝑤𝑚(𝑙 ) = 0. By the Word RAM assumption, 𝑎 and 𝑐 are found in O (1) worst-case time using rank/select operations on 𝑤 (𝑙 ) . Conditioned on the already sampled values 𝑃𝑎(𝑙 ) = 𝑆𝑙 (𝑎) and 𝑃𝑐(𝑙 ) = 𝑆𝑙 (𝑐), the missing value 𝑆𝑙 (𝑚) is a Gaussian Brownian-bridge point (similar to the application in [5]): (𝑙 ) (𝑙 ) (𝑐 −𝑚) 2 𝑆𝑙 (𝑚) ∼ N 𝑃𝑎(𝑙 ) + 𝑚−𝑎 , (𝑚−𝑎) 𝜎 𝑐 −𝑎 𝑃𝑐 − 𝑃𝑎 𝑐 −𝑎 We sample from this conditional distribution, store the value in 𝑃𝑚(𝑙 ) , and set 𝑤𝑚(𝑙 ) = 1. This is the exact conditional distribution of the missing prefix sum in the Gaussian tree. Below level 𝑚, the new path enters a subtree that has not appeared on any previous active path. Because query times are non-decreasing, at the first bit where 𝑏 (𝑙) and 𝑏 (𝑡) differ, the old active path goes to the left subtree and the new active path goes to the right subtree (i.e. all earlier queried leaves lie in a left subtree). Consequently, conditioned on the shared prefix sum 𝑆𝑡 (𝑚), the remaining contribution on the new path is independent of the past. We therefore sample 𝑃ℎ(𝑡 ) = 𝑃𝑚(𝑙 ) + 𝑍 ′,
𝑍 ′ ∼ N (0, (ℎ − 𝑚)𝜎 2 ),
with 𝑍 ′ independent of all previously sampled values, and release 𝜈 (𝑡 ) = 𝑃ℎ(𝑡 ) . Lastly, we update the state. All valid prefix sums at levels 𝑗 ≤ 𝑚 remain valid, since they lie on the shared part of the old and new active paths. All valid levels 𝑗 > 𝑚 from the old path are invalidated, except for level ℎ, as it is set to the newly sampled value 𝑃ℎ(𝑡 ) . This update of 𝑤 requires only a constant number of word operations, and the procedure samples only a constant number of Gaussian variables. Thus, each queried noise value is generated in O (1) worst-case time using O (log𝑇 ) words. Example. Figure 3 illustrates an update. The old active path goes to 𝑏 (𝑙) = 10010, and the new active path goes to 𝑏 (𝑡) = 10111. Their longest common prefix is 𝑢 = 10, so 𝑚 = 2. The value at level 2 has not yet been stored; it is sampled by conditioning on the nearest stored prefix sums above and below it, namely 𝑝 0 and 𝑝 3 . The final value 𝑝 5′ is then obtained by adding an independent Gaussian increment for the new branch below 𝑢. The resulting state stores exactly the valid prefix sums on the new active path. Remaining details in the proof of Theorem 3.1 can be found in Section C. 4
Private Orthogonal Range Queries
Orthogonal range counting is a fundamental problem in databases, with applications in query optimization (for cardinality estimation), OLAP analytics, indexing and spatial search, and approximate query processing. Its private analogue, private orthogonal range counting, is thus a potentially central primitive in private data analysis and database systems, but private range counting data structures in the literature (with polylogarithmic error) have been rather theoretical and we are not aware of any implementations.
10
Rasmus Pagh and Sia Sejer 𝑝0
𝑃 (𝑙 )
𝑤 (𝑙 )
𝑃 (𝑡 )
𝑤 (𝑡 )
𝑝0
1
𝑝0
1
1
𝑢 = 10
0
𝑝 2′ 100
0
0
𝑝 2′
1
1
𝑝3
0
101
𝑝3
𝑝3 1001
1011
0 𝑝5 𝑝5
𝑝 5′
bin (𝑙 − 1) = 10010
bin (𝑡 − 1) = 10111
(a) The active path at time 𝑙𝑖 , where entry 𝑖 was queried last, and the new active path at time 𝑡. The green part shows where the paths are independent. The longest common prefix of bin(𝑙 − 1) and bin(𝑡 − 1) is 𝑢 = 10.
1
0 𝑝 5′
1
(b) Left, the structure of 𝑤 (𝑙 ) and 𝑃 (𝑙 ) , which corresponds to the red path in panel (a). Right, the structure of 𝑤 (𝑡 ) and 𝑃 (𝑡 ) which is the structure of 𝐷𝑆 after updating from time 𝑙 to time 𝑡. The latter corresponds to the green path in panel (a). The 𝑤 vector shows which values correspond to prefix sums in the current active path.
Fig. 3. An example of the structure saved for each index 𝑖 ∈ [𝑘] where log(𝑇 ) + 1 = 6.
We consider a point multiset in the grid [𝐵]𝑑 , where 𝑑 is considered a constant. An orthogonal range query is specified by an axis-aligned rectangle 𝑅 ⊆ [𝐵]𝑑 and asks for the number of points contained in 𝑅. Equivalently, the query is defined by 𝑑 range predicates and returns the number of points satisfying all range predicates. The problem can be considered in both the static setting where all 𝑛 points are fixed in advance and the dynamic setting where points can be inserted and deleted. Changing the viewpoint, we can consider the point set as a vector indexed by positions in [𝐵]𝑑 , where each entry contains the number of points in that position. An update either increments or decrements the vector at a single position. We do not require the data structure to enforce that deletions correspond to earlier insertions, so the vector may take negative values. Given a sequence of 1-sparse update vectors 𝑥 (1) , 𝑥 (2) , . . . , the data structure should answer orthogonal range queries Í at time 𝑡 ≤ 𝑇 on the vector 𝑖 ≤𝑡 𝑥 (𝑖 ) while ensuring privacy of point updates. 4.1
Private Orthogonal Range Queries using Private CountSketches
Static data structure. We can use a standard dyadic decomposition to construct a collection of Private CountSketches that can be used to answer 𝑑-dimensional range queries in the static setting. In each dimension, the interval [𝐵] is decomposed into log2 (𝐵) dyadic components, each a partition of [𝐵] into intervals of 2𝑘 points, for 𝑘 ∈ {0, . . . , log2 (𝐵) − 1}. Combining these across dimensions results in the 𝑑-dimensional grid being decomposed into (log2 𝐵)𝑑 dyadic components, each a partition into rectangles of size 2𝑘1 × 2𝑘2 × · · · × 2𝑘𝑑 . For each component 𝐷 we consider the vector 𝑦 (𝐷 ) that records the number of points in each rectangle. Each point belongs to exactly one rectangle in each dyadic decomposition, and thus each such vector has sensitivity 1. For each component we instantiate an independent copy of Private CountSketch (see Section 1.2) with independent noise and hash functions. We will refer to f collection. Let 𝑛 denote an upper bound on the number of points so that all these copies as the 𝐶𝑆 (𝐷 ) f 𝑦 ≤ 𝑛 for all 𝐷. Let M be the family of (log2 𝐵)𝑑 independent instances of 𝐶𝑆. 1 Answering queries. It is not hard to show that every axis-aligned rectangle in [𝐵]𝑑 can be represented as a disjoint union of at most (2 log2 𝐵)𝑑 rectangles from these dyadic components, at
A Fast Gaussian Mechanism under Continual Observation, with Applications
11
f instances and sums their most 2𝑑 from each. To answer a query, M queries the corresponding 𝐶𝑆 f estimates. The output is therefore the sum of (2 log2 𝐵)𝑑 CountSketch estimates. Each queried 𝐶𝑆 entry is an unbiased estimate of the corresponding dyadic count, since the Private CountSketch is unbiased. Therefore the sum is an unbiased estimate of the range count. Space guarantees. To bound the space usage of Private CountSketch we invoke a fact from the compressive sensing literature (reformulated to fit our notation): Lemma 4.1 ([19], Theorem 2.5). Let 𝑏 ∈ Z+ , 𝑦 ∈ R𝑑 where 𝑑 ≥ 𝑏, and let tail𝑏 (𝑦) be the vector √ obtained by removing from 𝑦 the 𝑏 largest absolute-value coordinates. Then ∥tail𝑏 (𝑦)∥ 2 ≤ ∥𝑦 ∥ 1 /(2 𝑏). We choose the sketch size to balance the noise arising from privacy and the sketching error for a f as follows: single instance of 𝐶𝑆 Lemma 4.2. Let 𝑦 be an input vector, let 𝜎 2 > 0 be a variance parameter, and let 𝐸 ≥ 𝜎 be a 2 target error. For any 𝛽 ∈ (0, 1), there is a Private CountSketch with noise parameter 𝜎 , row size 𝑏 = O 1 + ∥𝑦 ∥ 1 /𝐸 , and 𝑡 = Θ(log(1/𝛽)) repetitions such that every fixed coordinate estimate has error O (𝐸) with probability at least 1 − 𝛽. The sketch uses O 𝑡 (1 + ∥𝑦 ∥ 1 /𝐸) words and satisfies 𝜌-zero-concentrated differential privacy with 𝜌 = 𝑡/(2𝜎 2 ). If 𝐸 is a constant-factor upper bound on ∥𝑦 ∥ 1 , the sketch can be replaced by the zero estimator, which has error at most ∥𝑦 ∥ 1 and uses constant space. For 𝑏 = Θ ∥𝑦 ∥ 1 /𝐸 the CountSketch tail error is at most the target error 𝐸; in our applications, 𝐸 is chosen to be comparable to the privacy noise scale. The proof of Lemma 4.2 can be found in Appendix D.1. We can now use the fact that the estimate has at most 2𝑑 contributions from each of (2 log2 𝐵)𝑑 f which means that we can employ a Bernstein inequality to show independent instances of 𝐶𝑆, f collection concentration. The Gaussian noise must be calibrated to this ℓ2 sensitivity, so the full 𝐶𝑆 satisfies 𝜌-zCDP by the Gaussian mechanism and composition. More details can be found in Section D.2. 4.2
Private Orthogonal Range Queries under Continual Observation
One key property of Private CountSketch [34, 40] is that it is linear and can thus be updated when the vector changes. A naive release of Private CountSketch does not by itself provide scalable privacy under continual observation. Instead, by using the results in Section 3, we will extend the f that constitutes static data structure to the dynamic setting. We can model the collection of 𝐶𝑆 the mechanism described in the previous section as a single vector that supports turnstile updates. By combining the static structure and the mechanism FastGaMe described in Section 3, we get a data structure for answering 𝑑-dimensional range queries under continual observation with the following guarantees: Theorem 4.3. For any choice of positive integers 𝑑 ≤ 𝐵, 𝑛, and for any 𝛽 ∈ (0, 1/log 𝐵), 𝜌 > 0, √ let 𝐸 = Ω 𝑑 (log 𝐵)𝑑+1 log(𝑛) log(𝑑/𝛽)/ 𝜌 denote some fixed error. Let M𝐶𝐶 be the dynamic range counting mechanism supporting 𝑛 updates, combining (log2 𝐵)𝑑 instances of Private CountSketch with the FastGaMe mechanism. Then M𝐶𝐶 can be represented as a data structure with the following properties: ◦ It answers 𝑑-dimensional orthogonal range queries over [𝐵]𝑑 under continual observation with worst-case additive estimation error O (𝐸) with probability at least 1 − 𝛽. ◦ The answers to any sequence of queries satisfy 𝜌-zCDP with respect to point updates. 𝑛 (log 𝐵) 𝑑 log(𝑑/𝛽 ) log(𝑛) ◦ Its space usage is O + 1 words. 𝐸
12
Rasmus Pagh and Sia Sejer
◦ Each query and update takes O (log 𝐵)𝑑 max (log(𝑑/𝛽), 𝑑 log(𝐵)) worst-case time. f collection can be treated as a single large Theorem 4.3 follows from the observation that the 𝐶𝑆 √︁ vector of counters with ℓ2 sensitivity (log2 𝐵)𝑑 𝑡, where 𝑡 is the number of repetitions in Private CountSketch. Hence, we can combine the static mechanism from Section 4.1 with FastGaMe from Section 3 to allow continual release over 𝑇 = 𝑛 steps. To maintain the same privacy parameter, the parameter 𝜎 2 used should be increased by a factor O (log 𝑛) relative to the static case. Space increases by a multiplicative factor O (log(𝑛)) due to the space requirements of FastGaMe, storing O (log(𝑛)) noise values for each entry in the sketch. At each step, the output distribution is the same as in the static setting with these adjusted space and noise parameters. 5
Private Join Size Estimation
Join size estimation is a central primitive in streaming algorithms and database systems. Given two relations 𝑅 and 𝑆 over a common key domain, let 𝑓𝑅 (𝑎) and 𝑓𝑆 (𝑎) denote the frequency of key 𝑎 in the two relations and let 𝑥, 𝑦 ∈ R𝑑 be the frequency vectors. The join size is ∑︁ 𝐽 (𝑅, 𝑆) = 𝑓𝑅 (𝑎) 𝑓𝑆 (𝑎) = ⟨𝑥, 𝑦⟩ . 𝑎
The case where 𝑅 and 𝑆 are identical is called a self-join, and the problem then becomes that of estimating the second frequency moment (𝐹 2 ). To estimate the inner product ⟨𝑥, 𝑦⟩ from the CountSketches CS(𝑥) and CS(𝑦) (defined in Section 1.2) we use the same hash functions for both sketches [2, 37]. The standard one-row innerproduct estimator is 𝑍𝑖 = ⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩, and the overall estimator is the median: b 𝐽 = median{𝑍 1, . . . , 𝑍𝑘 }. Since CountSketches can be maintained efficiently under updates, using them is a natural approach for approximating join sizes in dynamic settings. Recent work has shown guarantees for CountSketch estimators based on taking the median of a small number of rows 𝑘 [27]. Theorem 5.1 (Larsen–Pagh–Tetěk [27]). Let 𝑍 = ⟨CS1 (𝑥), CS1 (𝑦)⟩ denote a single-row CountSketch inner-product estimator using fully random hashing, so that E [𝑍 ] = ⟨𝑥, 𝑦⟩, and let b 𝐽 denote the median of 𝑘 independent copies of 𝑍 , where 𝑘 ≥ 3 is odd. For 𝑘 = 3 ( ! !) ∥𝑥 ∥ 21 ∥𝑦 ∥ 21 ∥𝑥 ∥ 22 ∥𝑦 ∥ 22 Var( b 𝐽 ) ≤ min O ,O . 𝑏2 𝑏 More generally, for every odd 𝑘 ≥ 3 and integer 𝑞 ≥ 1: h i 𝑘 E |b 𝐽 − ⟨𝑥, 𝑦⟩| (𝑘+1)𝑞/2 ≤ √2 · E [|𝑍 − ⟨𝑥, 𝑦⟩|𝑞 ] (𝑘+1)/2 . 𝑘
Thus the median operation effectively raises the moment decay to the power (𝑘 + 1)/2. Combined with one-row moment bounds this yields tail bounds as a function of the sketch width 𝑏. 5.1
Join Size Estimation Using Private CountSketch
Pagh and Thorup [34] gave a precise analysis of the error distribution of single-entry estimates 𝑥˜𝑎 f 𝑖 (𝑥) = CS𝑖 (𝑥) +𝜈𝑖 , where 𝜈𝑖 ∼ 𝑁 (0, 𝜎 2 𝐼𝑏 ), but did obtained from a Private CountSketch with rows CS not extend this analysis to inner products. We extend the analysis of Private CountSketch to inner product estimates. Again, it is important to use the same hash functions for the sketches of 𝑥 and 𝑦, but we add independent Gaussian noise to all sketch entries, ensuring privacy of both relations. f 𝑖 (𝑦) = CS𝑖 (𝑦) + 𝜉𝑖 where 𝜉𝑖 ∼ 𝑁 (0, 𝜎 2 𝐼𝑏 ) is chosen independently of That is, for each row 𝑖, let CS f 𝑖 (𝑥), CS f 𝑖 (𝑦)⟩ the noise vector 𝜈 used for CS(𝑥). The one-row inner-product estimator is 𝑍e𝑖 = ⟨CS
A Fast Gaussian Mechanism under Continual Observation, with Applications
13
and the corresponding median estimator is e 𝐽 = median{𝑍e1, . . . , 𝑍e𝑘 }. We show the following bound on the accuracy of e 𝐽: Lemma 5.2. Let 𝑘 ≥ 3 be odd, let 𝜂 ∈ (0, 1/2), and set 𝐶𝜂 = 𝜂 −2/(𝑘+1) . Assume that 𝑏 ≥ 8𝐶𝜂 . Then Pr | e 𝐽 − ⟨𝑥, 𝑦⟩| > 𝑐 Δ𝑥,𝑦,𝜂,𝑘,𝑏 ≤ 𝜂 where 𝑐 is a universal constant and (√︂ ) √︁ √︁ 𝐶𝜂 𝐶𝜂 ∥𝑥 ∥ 2 ∥𝑦 ∥ 2 , ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 + 𝜎 (∥𝑥 ∥ 2 + ∥𝑦 ∥ 2 ) ln(1/𝜂) + 𝜎 2 𝑏 ln(1/𝜂) . Δ𝑥,𝑦,𝜂,𝑘,𝑏 = min 𝑏 𝑏 The three terms in the error bound Δ𝑥,𝑦,𝜂,𝑘,𝑏 are, respectively, the median-amplified CountSketch error, the sketch–noise cross term, and the noise–noise product term. The CountSketch term switches from an ℓ2 bound to an ℓ1 bound when 𝑏 ≈ 𝐶𝜂 ∥𝑥 ∥ 21 ∥𝑦 ∥ 21 /(∥𝑥 ∥ 22 ∥𝑦 ∥ 22 ). After this point √the CountSketch contribution decreases as O (1/𝑏), while the noise–noise term increases as O 𝑏 ; √︁ these balance at 𝑏 ≈ (𝐶𝜂 ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 /(𝜎 2 log(1/𝜂))) 2/3 . Depending on the skew of 𝑥 and 𝑦 and the noise scale 𝜎, some parameter regimes may be empty, and the sketch–noise term may dominate as a baseline privacy error. To show Lemma 5.2 we need a bound on the single-row accuracy of (non-private) CountSketch: Lemma 5.3. Fix 𝑥, 𝑦 ∈ R𝑑 and let 𝜂 ∈ (0, 1/2). For each pair of CountSketch rows CS𝑖 (𝑥) and CS𝑖 (𝑦), the following bounds simultaneously hold with probability at least 1 − 𝜂: o n√︃ 8 4 |⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩ − ⟨𝑥, 𝑦⟩| ≤ min ∥𝑥 ∥ ∥𝑦 ∥ ∥𝑥 ∥ ∥𝑦 ∥ , 2 1 2 𝑏𝜂 1 𝑏𝜂 . (1) √︃ √︃ 8 8 ∥CS𝑖 (𝑥) ∥ 22 ≤ 1 + 𝑏𝜂 ∥𝑥 ∥ 22 ∥CS𝑖 (𝑦) ∥ 22 ≤ 1 + 𝑏𝜂 ∥𝑦 ∥ 22 Proof. The lemma follows along the lines of the CountSketch analysis in [11, 27]. For every 𝑥, 𝑦 ∈ R𝑑 we have E [⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩] = ⟨𝑥, 𝑦⟩ and Var(⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩) ≤ 𝑏2 ∥𝑥 ∥ 22 ∥𝑦 ∥ 22 . Chebyshev’s inequality with failure probability 𝜂/4 gives √︃ h i 8 ∥𝑥 ∥ 2 ∥𝑦 ∥ 2 ≤ 𝜂/4. Pr |⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩ − ⟨𝑥, 𝑦⟩| > 𝑏𝜂 For the 𝐿1 bound we expand E [|⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩ − ⟨𝑥, 𝑦⟩|]: " # ∑︁ 1 ∑︁ |𝑥 𝑝 ||𝑦𝑞 | ≤ ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 /𝑏 . 1{ℎ𝑖 (𝑝) = ℎ𝑖 (𝑞)}𝑠𝑖 (𝑝)𝑠𝑖 (𝑞)𝑥 𝑝 𝑦𝑞 ≤ E 𝑏 𝑝≠𝑞 𝑝≠𝑞 h i 4 ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 ≤ 𝜂/4. Applying the Markov’s inequality gives Pr |⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩ − ⟨𝑥, 𝑦⟩| > 𝑏𝜂 same variance bound and Chebyshev’s inequality to (𝑥, 𝑥) gives the stated bound on ∥CS𝑖 (𝑥)∥ 22 , with failure probability at most 𝜂/4, and similarly for 𝑦. A union bound over the four events proves the claim. □ We now turn to the estimators 𝑍e𝑖 based on the rows of Private CountSketch. Lemma 5.4. For 𝜂 ∈ (0, 1/2), 𝑏 ≥ 1/𝜂, and 𝑥, 𝑦 ∈ R𝑑 , each row estimator 𝑍e𝑖 satisfies: h n√︃ o i priv 8 4 Pr |𝑍e𝑖 − ⟨𝑥, 𝑦⟩| > min ≤ 2𝜂, 𝑏𝜂 ∥𝑥 ∥ 2 ∥𝑦 ∥ 2 , 𝑏𝜂 ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 + Λ𝜂 √ √︁ priv where Λ𝜂 = 3𝜎 (∥𝑥 ∥ 2 + ∥𝑦 ∥ 2 + 5𝜎 𝑏) ln(4/𝜂). The lemma says that a single row fails with probability at most 2𝜂 when the error threshold is chosen at the corresponding scale. The first term is the CountSketch error from [27]. The terms in priv Λ𝜂 are privacy-related error terms.
14
Rasmus Pagh and Sia Sejer
Proof. By the triangle inequality, |𝑍e𝑖 − ⟨𝑥, 𝑦⟩| ≤ |⟨CS𝑖 (𝑥), CS𝑖 (𝑦)⟩ − ⟨𝑥, 𝑦⟩| + |⟨CS𝑖 (𝑥), 𝜉𝑖 ⟩ + ⟨CS𝑖 (𝑦), 𝜈𝑖 ⟩| + |⟨𝜈𝑖 , 𝜉𝑖 ⟩| .
(2)
By Lemma 5.3, (1) holds with probability at least 1 − 𝜂, and bounds the first term of (2). On that event (fixing all hash functions), the first term is bounded, so it suffices to show h i priv Pr |⟨CS𝑖 (𝑥), 𝜉𝑖 ⟩ + ⟨CS𝑖 (𝑦), 𝜈𝑖 ⟩| + |⟨𝜈𝑖 , 𝜉𝑖 ⟩| > Λ𝜂 event (1) holds ≤ 𝜂, from which a union bound gives the desired probability upper bound 2𝜂. Since 𝑏 ≥ 1/𝜂, the 𝐿2 rownorm bounds in (1) imply ∥CS𝑖 (𝑥)∥ 2 ≤ 2 ∥𝑥 ∥ 2 and ∥CS𝑖 (𝑦)∥ 2 ≤ 2 ∥𝑦 ∥ 2 . Thus the sum ⟨CS𝑖 (𝑥), 𝜉𝑖 ⟩ + ⟨CS𝑖 (𝑦), 𝜈𝑖 ⟩ is Gaussian with variance 𝜎 2 ∥CS𝑖 (𝑥)∥ 22 + 𝜎 2 ∥CS𝑖 (𝑦) ∥ 22 ≤ 4𝜎 2 ∥𝑥 ∥ 22 + 4𝜎 2 ∥𝑦 ∥i 22 . Thus h √︁ a Gaussian tail bound gives Pr |⟨CS𝑖 (𝑥), 𝜉𝑖 ⟩ + ⟨CS𝑖 (𝑦), 𝜈𝑖 ⟩| > 3𝜎 (∥𝑥 ∥ 2 + ∥𝑦 ∥ 2 ) ln(4/𝜂) ≤ 𝜂/2. Finally, ⟨𝜈𝑖 , 𝜉𝑖 ⟩ is a sum of products of independent 𝑁 (0, 𝜎 2 ) variables. After scaling by 𝜎 2 , this is the same random variable that arises in the Gaussian Johnson–Lindenstrauss inner-product estimate for two orthogonal unit vectors, see, e.g., [19, Lemma 9.8 and Theorem 9.9]. Each product term is sub-exponential, and Bernstein’s inequality together with ln(4/𝜂) ≤ 2𝑏 gives h i √︁ Pr |⟨𝜈𝑖 , 𝜉𝑖 ⟩| > 15𝜎 2 𝑏 ln(4/𝜂) ≤ 𝜂/2 . □ Lemma 5.5. Let 𝑘 ≥ 3 be odd, let 𝜂 ∈ (0, 1), and suppose 𝑏 ≥ 8𝜂 −2/(𝑘+1) . Then " # Pr |median𝑖 𝑍e𝑖 − ⟨𝑥, 𝑦⟩| > Δ𝑥,𝑦,𝜂,𝑘,𝑏 ≤ 𝜂 where Δ𝑥,𝑦,𝜂,𝑘,𝑏 = min
n√︃
64
∥𝑥 ∥ 2 ∥𝑦 ∥ 2 , 𝑏 𝜂 2/(𝑘+1)
32 ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 𝑏 𝜂 2/(𝑘+1)
o
√ √︃ +3𝜎 (∥𝑥 ∥ 2 +∥𝑦 ∥ 2 +5𝜎 𝑏) ln 32𝜂 −2/(𝑘+1) .
Proof. Set 𝛼 = 21 2−2𝑘/(𝑘+1) 𝜂 2/(𝑘+1) . Then 𝛼 < 1/2 and the assumption on 𝑏 implies 𝑏 ≥ 1/𝛼. Let √︃ priv 4 8 𝑇𝛼 = min and 𝐵𝑖 = 1{|𝑍e𝑖 − ⟨𝑥, 𝑦⟩| > 𝑇𝛼 }. The variables 𝐵𝑖 𝑏𝛼 ∥𝑥 ∥ 2 ∥𝑦 ∥ 2 , 𝑏𝛼 ∥𝑥 ∥ 1 ∥𝑦 ∥ 1 + Λ𝛼 are independent and Lemma 5.4 states that Pr[𝐵𝑖 = 1] ≤ 2𝛼. Since 𝑘 is odd, the median fails only if at least (𝑘 + 1)/2 rows fail. This gives ∑︁ 𝑘 e Pr |median𝑖 𝑍𝑖 − ⟨𝑥, 𝑦⟩| > 𝑇𝛼 ≤ (2𝛼) 𝑗 ≤ 2𝑘 (2𝛼) (𝑘+1)/2 = 𝜂 . □ 𝑗 𝑗 ≥ (𝑘+1)/2
5.2
Maintaining a private join estimate under updates
We now describe how to maintain the noisy join estimate under continual observation. Theorem 5.6. Let 𝑇 be the time horizon, let 𝑏 ≥ 1, let 𝑘 ≥ 3 be odd, and let 𝜌 > 0. Define 2 = 𝑘 (log (𝑇 ) + 2) 2 /(8𝜌). Consider a dynamic stream of updates to two relations 𝑅 and 𝑆, where 𝜎co 2 each update changes the frequency of a key in one relation by at most 1 (increase or decrease). There is 𝐽𝑡 of the join size 𝐽𝑡 = ⟨𝑥𝑡 , 𝑦𝑡 ⟩ at each time step 𝑡 ∈ [𝑇 ] with a data structure that maintains estimates e the following guarantees: • The worst-case update time is O (𝑘) in a Word RAM model (see Section A). • The space usage is O (𝑘𝑏 log𝑇 ) words, in addition to storing the CountSketch hash functions. • The entire sequence of released estimates is 𝜌-zCDP under continual observation. • For every fixed time 𝑡 and every 𝜂 ∈ (0, 1/2) such that 𝑏 ≥ 8𝜂 −2/(𝑘+1) , letting √︃ √ √︁ 𝜂 −2/(𝑘+1) 𝜂 −2/(𝑘+1) ∥𝑥𝑡 ∥ 1 ∥𝑦𝑡 ∥ 1 2 ∥𝑥 ∥ ∥𝑦 ∥ Δ𝑡 (𝜂) = min , + (𝜎co (∥𝑥𝑡 ∥ 2 + ∥𝑦𝑡 ∥ 2 ) + 𝜎co 𝑏) ln(1/𝜂), 𝑡 2 𝑡 2 𝑏 𝑏
A Fast Gaussian Mechanism under Continual Observation, with Applications
15
we have Pr | e 𝐽𝑡 − ⟨𝑥𝑡 , 𝑦𝑡 ⟩| > 𝑐 Δ𝑡 (𝜂) ≤ 𝜂, where 𝑐 is a universal constant. Note that if estimates are released at all times 𝑡 ∈ [𝑇 ] and 𝑏 ≥ 8(𝑇 /𝜂) 2/(𝑘+1) , then with probability at least 1 − 𝜂 the bound | e 𝐽𝑡 − ⟨𝑥𝑡 , 𝑦𝑡 ⟩| ≤ 𝑐 Δ𝑡 (𝜂/𝑇 ) holds simultaneously for all 𝑡. Unlike the point 2 is estimates in [27], we note that the error grows with the number of repetitions 𝑘, since 𝜎co −2/(𝑘+1) proportional to 𝑘. The condition 𝑏 ≥ 8𝜂 is satisfied for 𝑘 ≳ log(1/𝜂)/(2 log 𝑏), so error probability polynomially small in 𝑏 can be achieved with constant 𝑘. Proof. We consider all rows of both sketches as one large vector and apply FastGaMe (Section 3) to it. The space usage for FastGaMe is O (log𝑇 ) per sketch entry. An update to one relation changes one counter in each of 𝑘 CountSketch rows, so the combined ℓ2 sensitivity of the vectors √ of all sketch counters is at most 𝑘. Thus, setting the internal node variance in FastGaMe to 2 𝜎node = 𝑘 (log2 (𝑇 ) + 2)/(8𝜌), yields 𝜌-zCDP of the sketches for both relations under continual observation. Since the estimates are computed by post-processing the same guarantee applies to them. For an update to key 𝑎, only one bucket in each CountSketch row can change. For each of the 𝑘 rows we refresh the necessary noisy sketch entries using FastGaMe and update the maintained row inner product by replacing the affected bucket contribution. Each refresh and arithmetic update takes O (1) worst-case time, giving O (𝑘) update time, including recomputing the median. Notice that this causes the noise of sketch entries to have different timestamps according to when they were last updated. However, this does not matter: At any fixed time 𝑡, the noisy sketch entries 2 2 . used in the maintained estimator are independent Gaussians with variance 𝜎node (log(𝑇 ) + 1) < 𝜎co Thus Lemma 5.2 applies with 𝑥 = 𝑥𝑡 , 𝑦 = 𝑦𝑡 , and 𝜎 = 𝜎co . The simultaneous guarantee follows by a union bound over all 𝑇 released estimates, which holds even though noise values are correlated over time. □ 6
Conclusion and Open Questions
We have shown that dynamic data structures with bounded-norm updates, for example linear sketches, support continual observation with no asymptotic time overhead. Values are released with correlated Gaussian noise of magnitude within a small constant factor of the best continual observation techniques. It would be interesting to see if similar results hold for more sophisticated low-space matrix factorization techniques with improved error, such as the Buffered Linear Toeplitz matrices of Dvijotham, McMahan, Pillutla, Steinke, and Thakurta [14] or (perhaps more directly) for the higher-degree tree-based methods like that of Andersson, Pagh, and Torkamani [4]. Though we have focused on methods with Gaussian noise, it appears likely that analogous results hold under Laplace noise, with pure differential privacy guarantees. Our two applications show that while continual observation comes at a cost in error compared to a one-shot release, the cost in terms of processing time is constant. They also illustrate the power and versatility of Private CountSketch in data management applications such as multidimensional indexing and sketch-based join size estimation. There are many other settings in which approximate representation of sparse vectors is a key ingredient, so there are likely more such applications. Acknowledgments The authors were supported by a Data Science Distinguished Investigator grant from Novo Nordisk Fonden, and are part of BARC, supported by the VILLUM Foundation grant 54451.
16
Rasmus Pagh and Sia Sejer
References [1] Peyman Afshani, Rasmus Killmann, and Kasper Green Larsen. Hierarchical categories in colored searching. In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/LIPIcs.ISAAC.2022.25. URL https://drops.dagstuhl. de/entities/document/10.4230/LIPIcs.ISAAC.2022.25. [2] Noga Alon, Phillip B. Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. In Proceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 10–20, 1999. doi: 10.1145/303976.303978. [3] Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. In Advances in Neural Information Processing Systems, volume 36, pages 49133–49145. Curran Associates, Inc., 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/99c41fb9fd53abfdd4a0259560ef1c9d-Paper-Conference. pdf. [4] Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy. CoRR, abs/2408.07021, 2024. doi: 10.48550/arXiv.2408.07021. URL https://doi.org/10.48550/ arXiv.2408.07021. [5] Joel Daniel Andersson, Lukas Retschmeier, Boel Nelson, and Rasmus Pagh. Private lossless multiple release. In Proceedings of 42nd International Conference on Machine Learning (ICML), ICML’25. JMLR.org, 2025. [6] Martin Aumüller, Christian Janos Lebeda, and Rasmus Pagh. Representing sparse vectors with differential privacy, low error, optimal space, and fast access. Journal of Privacy and Confidentiality, 12(2), 2022. doi: 10.29012/jpc.809. [7] Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors, Theory of Cryptography, pages 635–658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. ISBN 978-3-662-53641-4. doi: 10.1007/978-3-662-53641-4_24. [8] Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. Journal of Privacy and Confidentiality, 12(1), July 2022. doi: 10.29012/jpc.784. URL https://journalprivacyconfidentiality.org/index. php/jpc/article/view/784. [9] T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur., 14(3), nov 2011. ISSN 1094-9224. doi: 10.1145/2043621.2043626. URL https://doi.org/10.1145/2043621.2043626. Appeared in Cryptology ePrint Archive 2010/076 and ICALP 2010. [10] Timothy M. Chan. Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back. In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi: 10.4230/LIPIcs.SoCG.2017.27. URL https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.SoCG.2017.27. [11] Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. Theoretical Computer Science, 312(1):3–15, 2004. ISSN 0304-3975. doi: 10.1016/S0304-3975(03)00400-6. URL https://doi.org/10.1016/S03043975(03)00400-6. Conference version in ICALP 2002. [12] Edith Cohen, Ofir Geri, Tamás Sarlós, and Uri Stemmer. Differentially private weighted sampling. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 of Proceedings of Machine Learning Research, pages 3068–3076. PMLR, 2021. URL https://proceedings.mlr.press/v130/cohen21b.html. [13] Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, and Thanh TL Tran. Differentially private summaries for sparse data. In Proceedings of the 15th International Conference on Database Theory, pages 299–311, 2012. doi: 10.1145/2274576.2274608. [14] 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. URL https://doi.org/10.1109/FOCS61266.2024.00135. [15] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211–407, aug 2014. ISSN 1551-305X. doi: 10.1561/0400000042. URL https://doi.org/10.1561/0400000042. [16] Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. STOC, 2010. doi: 10.1145/1806689.1806787. URL https://doi.org/10.1145/1806689.1806787. [17] Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. In Advances in Cryptology – ASIACRYPT 2015, volume 9453, pages 735–751, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. ISBN 978-3-662-48800-3. doi: 10.1007/978-3-662-48800-3\_30. URL https://doi.org/ 10.1007/978-3-662-48800-3_30. [18] Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. In Yael Tauman Kalai, editor,
A Fast Gaussian Mechanism under Continual Observation, with Applications
17
14th Innovations in Theoretical Computer Science Conference (ITCS 2023), volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-263-1. doi: 10.4230/LIPIcs.ITCS.2023.48. URL https://drops.dagstuhl.de/entities/document/10.4230/ LIPIcs.ITCS.2023.48. [19] Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, 2013. ISBN 978-0-8176-4947-0. doi: 10.1007/978-0-8176-4948-7. URL https://doi.org/ 10.1007/978-0-8176-4948-7. [20] 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. URL https://doi.org/10.1137/1.9781611977554.ch183. [21] Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn. Sparse dimensionality reduction revisited. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 18454–18469, 2024. URL https://proceedings.mlr.press/v235/hogsgaard24a.html. [22] Rayne Holland. Scalable differentially private sketches under continual observation. CoRR, abs/2507.03361, 2025. doi: 10.48550/arXiv.2507.03361. URL https://doi.org/10.48550/arXiv.2507.03361. [23] James Honaker. Efficient use of differentially private binary trees. Theory and Practice of Differential Privacy (TPDP), 2: 26–27, 2015. [24] Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. In Proceedings of the 18th international conference on World Wide Web (WWW), pages 171–180, 2009. doi: 10.1145/1526709.1526733. [25] Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. PrivateSQL: a differentially private sql query engine. Proceedings of the VLDB Endowment, 12(11):1371–1384, 2019. doi: 10.14778/3342263.3342274. [26] Fragkiskos Koufogiannis, Shuo Han, and George J. Pappas. Gradual release of sensitive data under differential privacy. Journal of Privacy and Confidentiality, 7(2), Jan. 2017. doi: 10.29012/jpc.v7i2.649. URL https: //journalprivacyconfidentiality.org/index.php/jpc/article/view/649. [27] Kasper Green Larsen, Rasmus Pagh, and Jakub Tetěk. Countsketches, feature hashing and the median of three. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 6011–6020, 2021. URL http: //proceedings.mlr.press/v139/larsen21a.html. [28] Christian Janos Lebeda and Jakub Tetěk. Better differentially private approximate histograms and heavy hitters using the Misra-Gries sketch. ACM Transactions on Database Systems, 50(3):9:1–9:26, 2025. doi: 10.1145/3716375. URL https://doi.org/10.1145/3716375. [29] 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, 2015. doi: 10.1007/s00778-0150398-x. [30] Jiřı Matoušek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy. International Mathematics Research Notices, 2020(3):751–780, 2020. doi: 10.1093/imrn/rny033. URL https://doi.org/10.1093/imrn/ rny033. [31] Gregory T. Minton and Eric Price. Improved concentration bounds for count-sketch. In Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 669–686, 2014. doi: 10.1137/1.9781611973402.51. URL https://epubs.siam.org/doi/abs/10.1137/1.9781611973402.51. [32] Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 37–48, 2011. doi: 10.1145/1989284.1989290. URL https://doi.org/10.1145/1989284.1989290. [33] Shanmugavelayutham Muthukrishnan and Aleksandar Nikolov. Optimal private halfspace counting via discrepancy. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1285–1292, 2012. doi: 10.1145/2213977.2214090. URL https://doi.org/10.1145/2213977.2214090. [34] Rasmus Pagh and Mikkel Thorup. Improved utility analysis of private countsketch. In Advances in Neural Information Processing Systems (NeurIPS), volume 35, pages 25631–25643. Curran Associates, Inc., 2022. URL https://proceedings. neurips.cc/paper_files/paper/2022/file/a47f5cdff1469751597d78e803fc590f-Paper-Conference.pdf. [35] Yuan Qiu and Ke Yi. Differential privacy on fully dynamic streams. In Advances in Neural Information Processing Systems (NeurIPS), 2025. [36] Nina Mesing Stausholm. Improved differentially private euclidean distance approximation. In Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 42–56, 2021. doi: 10.1145/3452021.3458328. [37] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th International Conference on Machine Learning (ICML), pages 1113–1120,
18
Rasmus Pagh and Sia Sejer
2009. doi: 10.1145/1553374.1553516. [38] Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms. IEEE Transactions on Knowledge and Data Engineering, 23(8):1200–1214, 2011. doi: 10.1109/TKDE.2010.247. URL https://doi.org/10.1109/ TKDE.2010.247. Appeared as arXiv 0909.5530 and in ICDE 2010. [39] Meifan Zhang, Xin Liu, and Lihua Yin. Sketches-based join size estimation under local differential privacy. In Proceedings of the 40th IEEE International Conference on Data Engineering (ICDE), pages 1726–1738. IEEE, 2024. doi: 10.1109/ICDE60146.2024.00140. URL https://doi.org/10.1109/ICDE60146.2024.00140. [40] Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. In Advances in Neural Information Processing Systems (NeurIPS), 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/525338e0d98401a62950bc7c454eb83dAbstract-Conference.html.
A Fast Gaussian Mechanism under Continual Observation, with Applications
A
19
Preliminaries Omitted from Paper Body
Machine model. Our data structure is presented for a variant of the standard Word RAM model with word size at least max(log 𝑛, log𝑇 , log 𝐵). In particular, this model allows rank-and-select queries on machine words to be answered in constant time. To simplify the exposition, we assume that the Word RAM is augmented with the ability to represent and add real-valued Gaussians, and that fully random hash functions are available. This This Gaussian-realization assumption can likely be removed by making use of discrete Gaussians [8]. Definition A.1 (Differential Privacy, [15]). A randomized mechanism M : X𝑐 → Y is (𝜀, 𝛿)differentially private for 𝜀 > 0 and 𝛿 ≥ 0 if for all subsets of outputs S ⊆ Y and for all neighboring 𝑥, 𝑥 ′ ∈ X𝑐 such that ∥𝑥 − 𝑥 ′ ∥ 1 ≤ 1 it holds that: Pr[M (𝑥) ∈ S] ≤ exp 𝜀 Pr[M (𝑥 ′ ) ∈ S] + 𝛿 M satisfies approximate differential privacy when 𝛿 > 0 and pure differential privacy when 𝛿 = 0. When referring to 𝜌-zCDP (or zCDP), we refer to the definition of [7]: Definition A.2 (𝜌-Zero-Concentrated Differential Privacy (𝜌-zCDP), [7]). A randomized mechanism 𝑀 : X𝑐 → Y is (𝜀, 𝜌)-zCDP if for all neighboring 𝑥, 𝑥 ′ ∈ X𝑐 such that 𝑥 and 𝑥 ′ only differ in one element and for all 𝛼 ∈ (1, ∞): 𝐷𝛼 (𝑀 (𝑥)||𝑀 (𝑥 ′ )) ≤ 𝜀 + 𝜌𝛼 where 𝐷𝛼 (𝑀 (𝑥)||𝑀 (𝑥 ′ )) is the 𝛼-Rényi divergence between the distribution 𝑀 (𝑥) and the distribution 𝑀 (𝑥 ′ ). A randomized mechanism 𝑀 : X𝑐 → Y is 𝜌-zCDP if it is (0, 𝜌)-zCDP. Moreover, we characterize the Gaussian Mechanism under zCDP: Definition A.3 (Gaussian Mechanism, [7]). A function 𝑞 : X𝑛 → R has sensitivity Δ2 if ∀𝑥, 𝑥 ′ ∈ X𝑛 differing in a single entry it holds that |𝑞(𝑥) − 𝑞(𝑥 ′ )| ≤ Δ2 . Let 𝑞 be a sensitivity-Δ2 query. Then the mechanism M : X𝑛 → R that releases a sample from N 𝑞(𝑥), 𝜎 2 satisfies Δ22 /(2𝜎 2 ) -zCDP. Definition A.3 generalizes to functions with values in R𝑘 , in which case the sensitivity bound is ∥𝑞(𝑥) − 𝑞(𝑥 ′ ) ∥ 2 ≤ Δ2 and the mechanism releases N 𝑞(𝑥), 𝜎 2 𝐼𝑘 , where 𝐼𝑘 is the identity matrix. B
Details for Section 2
Let 𝐿 be the linear map that takes a vector 𝑦 of dimension 2𝑇 − 1 indexed by the vertices in the Í complete binary tree such that for 𝑡 = 0, . . . ,𝑇 − 1 we have (𝐿𝑦)𝑡 = 𝑣 ∈𝑃𝑡 𝑦 𝑣 . As above we assign numerical indices 𝑣 = 0, . . . ,𝑇 − 1 to the leaves and use indices 𝑣 = 𝑇 , . . . , 2𝑇 − 2 for the internal nodes. Next, we describe a linear map 𝑅 such that the composition 𝐿𝑅 is the all-ones lower triangular matrix, i.e., (𝐿𝑅𝑥)𝑡 = 𝐴 (𝑡 ) . Define the sign, denoted sign(𝑣), of a non-root node 𝑣 to be −1 if 𝑣 is a left child and +1 if 𝑣 is a right child, and let sib(𝑣) denote the sibling of a non-root node 𝑣. 1 Í𝑇 −1 𝑥 if 𝑣 is the root node 2 𝑡 =0 𝑡 Í 1 (𝑅𝑥)𝑣 = 2 sign(𝑣) 𝑡 :sib(𝑣) ∈𝑃𝑡 𝑥𝑡 if 𝑣 is a non-root internal node . 1 (𝑥 𝑣 + sign(𝑣) 𝑥 sib(𝑣) ) if 𝑣 is a leaf 2 That is, the root node is associated with the sum of all inputs multiplied by 12 , each internal node 𝑣 is associated with the sum of all inputs corresponding to leaves in its sibling’s subtree multiplied by 12 sign(𝑣), and each leaf node is associated with 12 times either a sum or a difference of sibling
20
Rasmus Pagh and Sia Sejer
values. By definition (𝐿𝑅𝑥)𝑡 = (𝐿(𝑅𝑥))𝑡 = for every internal node 𝑤, ∑︁
Í
𝑣 ∈𝑃𝑡 (𝑅𝑥) 𝑣 . We argue by induction on the depth that
max{𝑖:𝑤 ∑︁∈𝑃𝑖 }
(𝑅𝑥)𝑣 =
!
! 1 2
𝑥𝑡 −
𝑡 =0
𝑣 ∈𝑃 𝑤
∑︁
𝑥𝑡
.
(3)
𝑡 :𝑤 ∈𝑃𝑡
This is clearly true when 𝑤 is the root node. For the induction step we assume that the statement is true for 𝑤’s parent and see that adding (𝑅𝑥)𝑤 exactly matches the claimed difference. In turn, for a leaf node 𝑡 with parent 𝑤 we have, using (3), ! ∑︁ ∑︁ (𝑅𝑥)𝑣 = (𝑅𝑥)𝑣 + 21 (𝑥𝑡 + sign(𝑡) 𝑥 sib(𝑡 ) ) 𝑣 ∈𝑃𝑡
𝑣 ∈𝑃 𝑤
=
max{𝑡 :𝑤 ∈𝑃𝑡 } ∑︁
! 𝑥𝑖 −
!
=𝐴
𝑥𝑖 + 12 (𝑥𝑡 + sign(𝑡) 𝑥 sib(𝑡 ) )
𝑖:𝑤 ∈𝑃𝑖
𝑖=0 (𝑡 )
∑︁
1 2
,
where the last equality is obtained by checking the cases where 𝑡 is a left and a right child, respectively. With the linear maps 𝐿 and 𝑅 defined, we see that the mechanism can be written in 2 2𝑇 −1 . To analyze the form of a factorization mechanism: 𝐴˜ (𝑡 ) = 𝐿(𝑅𝑥 + 𝑁 )𝑡 , where 𝑁 √︁ ∼ N (0, 𝜎 ) 1 the privacy we first note that the ℓ2 -sensitivity of 𝑅𝑥 is Δ2 (𝑅) = 2 log2 (𝑇 ) + 2. This is because changing one input 𝑥𝑖 by at most 1 changes exactly (log2 (𝑇 ) + 2) values (𝑅𝑥)𝑣 by at most 1/2, one changed node for each internal level and two at the leaf level. We can now apply the standard zCDP bound for the Gaussian mechanism to 𝑅𝑥. Releasing 𝑅𝑥 + 𝑁 with 𝑁 ∼ N (0, 𝜎 2 ) 2𝑇 −1 satisfies 𝜌-zCDP with 𝜌 = Δ2 (𝑅) 2 /(2𝜎 2 ) = (log2 (𝑇 ) + 2)/(8𝜎 2 ), and since 𝐿(𝑅𝑥 + 𝑁 ) is a (deterministic) post-processing of 𝑅𝑥 + 𝑁 , the released estimates satisfy the same privacy guarantee [7]. Equivalently, we can choose 𝜎 2 = (log2 (𝑇 ) + 2)/(8𝜌), resulting in Var[𝐴˜ (𝑡 ) ] = (log2 (𝑇 ) + 1)𝜎 2 < (log2 (𝑇 ) + 2) 2 /(8𝜌). This matches the asymptotic variance of the smooth Gaussian mechanism but reduces a lower-order term that is significant when 𝑇 is small. C C.1
Details for Section 3 Proof of Theorem 3.1
Proof. Let ℎ = log2 (𝑇 ), and index levels on a root-to-leaf path by 0, 1, . . . , ℎ, where level 0 is the root. For a leaf 𝑡, let 𝑏 (𝑡) = bin(𝑡 − 1) be its ℎ-bit label, and let 𝑏 (𝑡) ≤ 𝑗 denote its prefix of ≤ℎ length 𝑗. In the Gaussian binary-tree mechanism, each node 𝑠 ∈ {0, 1} has an independent noise 2 𝜂𝑠 ∼ N 0, 𝜎 , and the released noise at time 𝑡 is 𝜈 (𝑡 ) =
ℎ ∑︁
𝜂𝑏 (𝑡 ) ≤ 𝑗 .
𝑗=0
It is useful to write the partial sums on the active path as 𝑆𝑡 ( 𝑗) =
𝑗 ∑︁
𝜂𝑏 (𝑡 ) ≤𝑟
for 0 ≤ 𝑗 ≤ ℎ.
𝑟 =0
Then 𝜈 (𝑡 ) = 𝑆𝑡 (ℎ), Var[𝜈 (𝑡 ) ] = (ℎ + 1)𝜎 2 , and if 𝑢 is the longest common prefix of 𝑏 (𝑡 1 ) and 𝑏 (𝑡 2 ), then Cov(𝜈 (𝑡1 ) , 𝜈 (𝑡2 ) ) = (|𝑢 | + 1)𝜎 2 .
A Fast Gaussian Mechanism under Continual Observation, with Applications
21
The data structure is 𝐷𝑆 = ⟨𝑙, 𝑤 (𝑙 ) , 𝑃 (𝑙 ) ⟩. Here 𝑙 is the last queried time, 𝑤 (𝑙 ) ∈ {0, 1}ℎ+1 is a bit vector indexed by levels 0, . . . , ℎ, and if 𝑤 𝑗(𝑙 ) = 1 then 𝑃 𝑗(𝑙 ) is the already sampled value of 𝑆𝑙 ( 𝑗) on the path to 𝑏 (𝑙). The bit vector fits in one machine word, and 𝑃 (𝑙 ) contains ℎ + 1 = O (log𝑇 ) words. We maintain the invariant that, after processing any query sequence, the joint distribution of all released noise values together with all currently valid stored values 𝑃 𝑗(𝑙 ) is exactly the joint distribution of the corresponding variables in the Gaussian binary-tree mechanism. Initially, no values are stored, and the invariant is trivial. Consider a new query at time 𝑡. If 𝑙 = 𝑡, then the leaf has not changed, and we return the already stored value 𝑃ℎ(𝑙 ) . Assume first that this is the first query. We sample 𝑃0(𝑡 ) ∼ N 0, 𝜎 2 , 𝑃ℎ(𝑡 ) = 𝑃0(𝑡 ) + 𝑍, 𝑍 ∼ N 0, ℎ𝜎 2 , with 𝑍 independent of 𝑃0(𝑡 ) . We set 𝑤 0(𝑡 ) = 𝑤ℎ(𝑡 ) = 1, set 𝑙 = 𝑡, and return 𝑃ℎ(𝑡 ) . This is exactly the joint distribution of (𝑆𝑡 (0), 𝑆𝑡 (ℎ)), so the invariant holds. It remains to handle the case where the previous queried time is 𝑙 ≠ 𝑡. Let 𝑢 be the longest common prefix of 𝑏 (𝑙) and 𝑏 (𝑡), and set 𝑚 = |𝑢 |. The old and new active paths are identical up to level 𝑚 and disjoint below level 𝑚. If 𝑤𝑚(𝑙 ) = 1, the shared value 𝑆𝑡 (𝑚) = 𝑆𝑙 (𝑚) is already stored as 𝑃𝑚(𝑙 ) . Otherwise, let 𝑎 = max{ 𝑗 < 𝑚 : 𝑤 𝑗(𝑙 ) = 1},
𝑐 = min{ 𝑗 > 𝑚 : 𝑤 𝑗(𝑙 ) = 1}.
The sentinels 𝑤 0(𝑙 ) = 𝑤ℎ(𝑙 ) = 1 ensure that these values exist whenever 𝑤𝑚(𝑙 ) = 0. By the Word RAM assumption, 𝑎 and 𝑐 are found in O (1) worst-case time using rank/select. Conditioned on 𝑃𝑎(𝑙 ) = 𝑆𝑙 (𝑎) and 𝑃𝑐(𝑙 ) = 𝑆𝑙 (𝑐), the Gaussian random walk value at level 𝑚 has the Brownian-bridge distribution (𝑚 − 𝑎) (𝑐 − 𝑚) 2 𝑚 − 𝑎 (𝑙 ) 𝑃𝑚(𝑙 ) ∼ N 𝑃𝑎(𝑙 ) + 𝑃𝑐 − 𝑃𝑎(𝑙 ) , 𝜎 . 𝑐 −𝑎 𝑐 −𝑎 We sample from this conditional distribution, store the result in 𝑃𝑚(𝑙 ) , and set 𝑤𝑚(𝑙 ) = 1. This is the exact conditional law of the missing shared prefix sum in the Gaussian tree, so the induction invariant is preserved. Below the node 𝑢, the new path to 𝑏 (𝑡) uses tree nodes that have never appeared on any previous active path. Indeed, at the first bit after 𝑢, the path to 𝑏 (𝑙) goes left and the path to 𝑏 (𝑡) goes right; since query times are increasing, every earlier queried leaf lies in the left subtree. Thus, conditioned on 𝑃𝑚(𝑙 ) , the remaining sum on the new branch is independent of all previously released and stored values. We sample 𝑃ℎ(𝑡 ) = 𝑃𝑚(𝑙 ) + 𝑍 ′, 𝑍 ′ ∼ N 0, (ℎ − 𝑚)𝜎 2 , with 𝑍 ′ independent of the past, and release 𝜈 (𝑡 ) = 𝑃ℎ(𝑡 ) . Again, this is the exact conditional distribution of 𝑆𝑡 (ℎ) given the variables already represented in the invariant. Finally, we update the valid bits. All valid levels 𝑗 ≤ 𝑚 remain valid because they lie on the shared prefix of the old and new paths; levels 𝑗 > 𝑚 from the old path are no longer on the active path and are marked invalid, except that we set level ℎ valid for the newly sampled leaf value. This is a constant number of word operations on 𝑤, and the only numerical samples drawn are a constant number of Gaussians. Therefore, each query is processed in O (1) worst-case time, and the structure uses O (log𝑇 ) words. By induction, the complete sequence of released values has the same joint distribution as in the Gaussian binary-tree mechanism. □
22
C.2
Rasmus Pagh and Sia Sejer
Pseudocode
Algorithm 1 NoiseUpdate(𝐷𝑆𝑖 , 𝑡, 𝜎 2,𝑇 ) Require: Data structure for coordinate 𝑖 at last query: 𝐷𝑆𝑖 = (𝑙𝑖 , 𝑤 (𝑖,𝑙𝑖 ) , 𝑃 (𝑖 ) ), where ℎ = log2 (𝑇 ), 𝑤 (𝑖,𝑙𝑖 ) ∈ {0, 1}ℎ+1 , and 𝑃 (𝑖 ) ∈ Rℎ+1 are indexed by levels 0, . . . , ℎ. Ensure: Updated 𝐷𝑆𝑖′ = (𝑙𝑖′, 𝑤 (𝑖,𝑡 ) , 𝑃 (𝑖 ) ) and noise value 𝜈𝑖(𝑡 ) = 𝑃ℎ(𝑖 ) . (𝑖,𝑙𝑖 )
1: Invariant: If 𝑤 𝑗
= 1 then 𝑃 𝑗(𝑖 ) is the sampled level-𝑗 prefix sum on the active path to
bin(𝑙𝑖 − 1). 2: ℎ ← log2 (𝑇 ) 3: if 𝑙𝑖 is unset then 4: 5: 6: 7:
⊲ levels are 0, . . . , ℎ; leaf labels have ℎ bits ⊲ first query to coordinate 𝑖
𝑤 (𝑖,𝑡 ) ← 0ℎ+1 Sample 𝑃 0(𝑖 ) ∼ N (0, 𝜎 2 ) Sample 𝑍 ∼ N (0, ℎ𝜎 2 ) 𝑃ℎ(𝑖 ) ← 𝑃0(𝑖 ) + 𝑍
𝑤 0(𝑖,𝑡 ) ← 1, 𝑤ℎ(𝑖,𝑡 ) ← 1 ⊲ invariant preserved since 𝑃 0(𝑖 ) and 𝑃ℎ(𝑖 ) have been set 𝑙𝑖′ ← 𝑡 10: return (𝐷𝑆𝑖′ = (𝑙𝑖′, 𝑤 (𝑖,𝑡 ) , 𝑃 (𝑖 ) ), 𝜈𝑖(𝑡 ) = 𝑃ℎ(𝑖 ) ) 11: end if 12: if 𝑙𝑖 = 𝑡 then ⊲ already queried at this time 13: return (𝐷𝑆𝑖 , 𝜈𝑖(𝑡 ) = 𝑃ℎ(𝑖 ) ) 14: end if 15: 𝑢 ← bin(𝑙𝑖 − 1), 𝑣 ← bin(𝑡 − 1) 16: 𝑚 ← |LCP(𝑢, 𝑣)| ⊲ old and new active paths agree through level 𝑚 17: 𝑤 (𝑖,𝑡 ) ← 𝑤 (𝑖,𝑙𝑖 ) (𝑖,𝑙 ) 18: if 𝑤𝑚 𝑖 = 0 then ⊲ the shared prefix value has not yet been sampled 19: 𝑎 ← pred𝑤 (𝑖,𝑙𝑖 ) (𝑚), 𝑐 ← succ𝑤 (𝑖,𝑙𝑖 ) (𝑚) ⊲ nearest valid levels strictly above/below 𝑚 (𝑖 ) (𝑖 ) (𝑖 ) 𝑚−𝑎 20: 𝜇 ← 𝑃𝑎 + 𝑐 −𝑎 𝑃𝑐 − 𝑃𝑎 (𝑐 −𝑚) 2 21: 𝜏 2 ← (𝑚−𝑎) 𝜎 𝑐 −𝑎 (𝑖 ) 22: Sample 𝑃𝑚 ∼ N (𝜇, 𝜏 2 ) ⊲ Brownian-bridge step conditioning on endpoints 23: 𝑤𝑚(𝑖,𝑡 ) ← 1 ⊲ shared prefix value is now valid 24: end if 25: Sample 𝑍 ′ ∼ N (0, (ℎ − 𝑚)𝜎 2 ) (𝑖 ) (𝑖 ) 26: 𝑃ℎ ← 𝑃𝑚 + 𝑍 ′ ⊲ sample new independent tail from level 𝑚 to leaf bin(𝑡 − 1) 27: for 𝑗 = 𝑚 + 1 to ℎ − 1 do ⊲ can be implemented in O (1) time with a bit-mask 28: 𝑤 𝑗(𝑖,𝑡 ) ← 0 29: end for (𝑖,𝑡 ) 30: 𝑤ℎ ←1 ⊲ invariant preserved since 𝑃𝑚(𝑖 ) and 𝑃ℎ(𝑖 ) have been set ′ 31: 𝑙𝑖 ← 𝑡 (𝑡 ) (𝑖 ) 32: return (𝐷𝑆𝑖′ = (𝑙𝑖′, 𝑤 (𝑖,𝑡 ) , 𝑃 (𝑖 ) ), 𝜈 𝑖 = 𝑃ℎ ) 8: 9:
A Fast Gaussian Mechanism under Continual Observation, with Applications
Reference
23
Privacy
Maximum error
Space
[38] [9]
𝜀-DP 𝜀-DP
(log 𝐵) 1.5𝑑+1 /𝜀
[17]
𝜀-DP
𝐵𝑑 𝐵𝑑 𝑛𝑑 𝑛(log 𝑛)𝑑
[33] + [30]
1 (𝜀, 100 )-DP
This paper
𝜀 2 /2-zCDP
(log 𝐵) 1.5𝑑+1 /𝜀 (log(𝐵) + (log 𝑛) 1.5𝑑+2 )/𝜀 (log 𝑛) 2𝑑+1 log(𝐵)/𝜀 Ω (log 𝑛)𝑑 −1 /𝜀 Ω (log 𝐵)𝑑 −1 /𝜀 𝐸 ≥ (log 𝐵)𝑑+2 /𝜀
any 𝑛(log 𝐵)𝑑+1 /𝐸
Fig. 4. Overview of results on static private orthogonal range counting for a set of 𝑛 points in [𝐵]𝑑 . Lower bounds in terms of 𝑛 and 𝐵, for worst-case inputs and no restriction on the other parameter, are shown with red background, and hold in particular for 𝜀 2 /2-zCDP. For simplicity, we assume that both 𝑑 and the privacy parameter 𝜀 are O (1), and order-notation is suppressed. Maximum error upper bounds hold with probability 1 − 1/𝐵. All listed static data structures support an orthogonal range counting query in time O (log 𝐵)𝑑 or 𝑑+1 𝑑+1 O (log 𝐵) . An arbitrary number of queries can be performed with query time O (log 𝐵) .
D
Details for Section 4
D.1
Proof of Lemma 4.2
Before proving the lemma, we start by introducing a result of [34], which shows that the error of the output of a Private CountSketch (denoted 𝑥˜𝑎 for any 𝑎 ∈ [𝑛]) can be bounded in a way that extends the analysis of regular CountSketch. Recall that tail𝑏 (𝑦) is the vector obtained from removing the 𝑏 largest coordinates in absolute value from a vector 𝑦. Then in our notation: Lemma D.1 ([34], Theorem 3.3). For every 𝛼 ∈ [0, 1] and every 𝑎 ∈ [𝑛], the estimation error of Private CountSketch with 𝑡 repetitions, row size 𝑏 and noise from N (0, 𝜎 2 ) satisfies: Pr [|𝑥˜𝑎 − 𝑥𝑎 | > 𝛼 max {𝜑, 𝜎 }] < 2 exp −Ω 𝛼 2𝑡 √ where 𝜑 = ∥tail𝑏 (𝑦) ∥ / 𝑏. Based on this, we can prove Lemma 4.2: Proof. Without loss of generality we can assume 𝐸 < ∥𝑦 ∥ 1 . Choosing 𝑏 =
l
∥𝑦 ∥ 1 2𝐸
m , by Lemma 4.1,
∥tail𝑏 (𝑦)∥ 2 ∥𝑦 ∥ 1 ≤ ≤ 𝐸. √ 2𝑏 𝑏 Since the lemma assumes 𝐸 ≥ 𝜎, we have max {𝜑, 𝜎 } ≤ 𝐸. Applying Lemma D.1 with 𝛼 = 1: 𝜑=
Pr [|𝑥˜𝑎 − 𝑥𝑎 | > 𝐸] < 2 exp (−Ω(𝑡)) . Setting 𝑡 = Θ(log(1/𝛽)) makes this probability at most 𝛽. The row size is 𝑏 = O 1 + ∥𝑦 ∥ 1 /𝐸 , so the total space is 𝑠 = 𝑡𝑏 = O 𝑡 (1 + ∥𝑦 ∥ 1 /𝐸) words. □ D.2
Details and guarantees for Static Private Range Queries
We now consider the static mechanism M described in Section 4. An overview of results in the static setting and comparison with previous work is shown in Figure 4. Theorem D.2. Let 𝐵 > 1 be a power of 2. For every constant integer 𝑑 < 𝐵, 𝛽 ∈ (0, 1/2), and 𝜌 > 0, √ let 𝜏 = log(𝑑/𝛽) + 𝑑 log log 𝐵 and let 𝐸 = Ω 𝑑𝜏 (log 𝐵)𝑑+1+log𝐵 (4/𝛽 ) / 𝜌 denote some fixed estimation error. There is a mechanism that takes as input a static set of 𝑛 points in [𝐵]𝑑 , and outputs a data structure with the following properties:
24
Rasmus Pagh and Sia Sejer
• Satisfies 𝜌-zero-concentrated differential privacy. 𝑑𝑛 (log 𝐵) 𝑑 𝜏 • Space usage is O + 1 words. 𝐸 • Supports orthogonal range counting queries that – return unbiased estimators of the true range count, – have worst-case additive estimation error O (𝐸) with probability at least 1 − 𝛽, and – can be answered in worst-case time O (2 log 𝐵)𝑑 𝜏 . We summarize the mechanism M from Section 4 here: The mechanism outputs (log2 𝐵)𝑑 Private CountSketches, each representing point counts in a partition of [𝐵]𝑑 into dyadic rectangles. Each sketch is parameterized with variance parameter 𝜎 2 = 𝑡 (log 𝐵)𝑑 /(2𝜌), row size 𝑏 = O (𝑛/𝜎), and 𝑡 repetitions (to be specified). Using composition over all sketches this ensures 𝜌-zero-concentrated differential privacy. Range counting queries are answered by summing at most (2 log2 𝐵)𝑑 estimates, at most 2𝑑 from each sketch. Let 𝑋ˆ𝑖 denote the sum of estimates from sketch 𝑖, in some arbitrary numbering of the sketches. Since Private CountSketch is unbiased, E 𝑋ˆ𝑖 equals the true number of points in the queried dyadic rectangles. The following lemma bounds the error of a query. Lemma D.3. Consider any specific range counting query and let 𝑋𝑖 = 𝑋ˆ𝑖 − E 𝑋ˆ𝑖 be the signed Í estimation error from the 𝑖th Private CountSketch such that the total error is | 𝑖 𝑋𝑖 |. Then for any choice of 𝑐, for sufficiently large 𝐵, row size 𝑏 = O (𝑛/𝜎), and 𝑡 = Θ(𝑐 log 𝐵 + 𝑑 log log 𝐵) the total error satisfies: " # ∑︁ 𝑡 (log 𝐵)𝑐+𝑑+1 Pr 𝑋𝑖 ≥ ≤ 2𝐵 −𝑐 . (4) √ 𝜌 𝑖 Proof. We define the following clipped version of 𝑋𝑖 : −𝜎, if 𝑋𝑖 < −𝜎 𝑌𝑖 = 𝑋𝑖 , if 𝑋𝑖 ∈ [−𝜎, 𝜎] 𝜎, if 𝑋𝑖 > 𝜎 Í Í √ 𝑐+𝑑+1 Let 𝐾 = 𝑡 (log 𝐵) / 𝜌 be the target error in (4). Since 𝑖 𝑋𝑖 = 𝑖 𝑌𝑖 unless one of the variables 𝑋𝑖 exceeds 𝜎 in absolute value, we can bound the probability in (4) as follows: " # " # ∑︁ ∑︁ ∑︁ Pr 𝑋𝑖 ≥ 𝐾 ≤ Pr [|𝑋𝑖 | > 𝜎] + Pr 𝑌𝑖 ≥ 𝐾 . 𝑖
𝑖
𝑖
By Lemma 4.2, making the constants in the bounds for row size 𝑏 and repetition number 𝑡 large enough we have, for 𝐵 sufficiently large, ∑︁ Pr [|𝑋𝑖 | ≥ 𝜎] ≤ (2 log2 𝐵)𝑑 exp(−Ω(𝑡)) ≤ 𝐵 −𝑐 . 𝑖
To bound the second term, we use Bernstein’s inequality. We have |𝑌𝑖 | ≤ 𝜎 by definition, and since 𝑋𝑖 is symmetric around 0 we have E [𝑌𝑖 ] = 0. Bernstein’s inequality states: " # ! ∑︁ − 21 𝐾 2 Pr 𝑌𝑖 ≥ 𝐾 ≤ 2 exp Í 2 1 . (5) 𝑖 E 𝑌𝑖 + 3 𝜎𝐾 𝑖 It remains to lower bound the exponent of (5). Since 𝑌𝑖 is 𝑋𝑖 clipped to [−𝜎, 𝜎], we have E 𝑌𝑖2 ≤ 2 E 𝑋𝑖 , so to get an upper bound for the denominator it suffices to upper bound the second moment of 𝑋𝑖 . For a fixed sketch 𝑖, the range query uses at most 2𝑑 estimates from that sketch. We can write
A Fast Gaussian Mechanism under Continual Observation, with Applications
25
Í𝑞𝑖 their signed errors as 𝑍𝑖,1, . . . , 𝑍𝑖,𝑞𝑖 , where 𝑞𝑖 ≤ 2𝑑 , so that 𝑋𝑖 = 𝑗=1 𝑍𝑖,𝑗 . By Lemma 4.2 and the h i 2 choice 𝑏 = O (𝑛/𝜎), each fixed estimate has second moment E 𝑍𝑖,𝑗 = O 𝜎 2 . By Cauchy–Schwarz, ! 2 ∑︁ 𝑞𝑖 ∑︁ 𝑞𝑖 2 2 E 𝑋𝑖 = E 𝑍𝑖,𝑗 ≤ 𝑞𝑖 E 𝑍𝑖,𝑗 ≤ O 4𝑑 𝜎 2 . 𝑗=1 𝑗=1 Summing over the (log2 𝐵)𝑑 sketches and using 𝜎 2 = 𝑡 (log 𝐵)𝑑 /(2𝜌) gives ∑︁ E 𝑋𝑖2 ≤ O 4𝑑 (log 𝐵)𝑑 𝜎 2 = O 4𝑑 𝑡 (log 𝐵) 2𝑑 /𝜌 . 𝑖
The denominator of (5) satisfies ∑︁ 1 3𝑑 E 𝑌𝑖2 + 𝜎𝐾 ≤ O 4𝑑 𝑡 (log 𝐵) 2𝑑 /𝜌 + O 𝑡 3/2 (log 𝐵)𝑐+ 2 +1 /𝜌 . 3 𝑖 Since 𝑑 is constant and 𝑡 = Θ(𝑐 log 𝐵 + 𝑑 log log 𝐵), the hidden constants in 𝑡 can be chosen so that, for sufficiently large 𝐵, 𝐾2 ≥ 2𝑐 ln 𝐵 + 2 ln 2. Í 2 1 𝑖 E 𝑌𝑖 + 3 𝜎𝐾 Í Therefore Pr [| 𝑖 𝑌𝑖 | ≥ 𝐾] ≤ 𝐵 −𝑐 , finishing the proof. □ We are now ready to show Theorem D.2. Proof. Choose 𝑐 = log𝐵 (4/𝛽), so that 2𝐵 −𝑐 = 𝛽/2. Use the mechanism summarized above with 𝑡 = Θ(max {log(𝑑/𝛽), 𝑐 log 𝐵 + 𝑑 log log 𝐵}) = Θ(𝜏)
and 𝜎 2 = 𝑡 (log2 𝐵)𝑑 /(2𝜌) .
Each point update changes one counter in each repetition of each of the (log2 𝐵)𝑑 dyadic sketches, so the squared ℓ2 -sensitivity of the full released sketch vector is 𝑡 (log2 𝐵)𝑑 . By Definition A.3, the above choice of 𝜎 2 gives 𝜌-zCDP. Unbiasedness follows by linearity: Each Private CountSketch point estimate is unbiased, and each range answer is the sum of the relevant dyadic count estimates. Lemma D.3 controls the error when summing over the dyadic decomposition of a given query, giving error probability at most 𝛽/2. Hence the range-query error is √ √ O 𝑡 (log 𝐵)𝑐+𝑑+1 / 𝜌 = O 𝜏 (log 𝐵)𝑑+1+log𝐵 (4/𝛽 ) / 𝜌 . This is O (𝐸) due to the lower bound on 𝐸. It remains to account for space and query time. When 𝐸 ≥ 𝑛 (using a privately estimated count) we use the constant-space zero estimator. Otherwise, each dyadic sketch stores 𝑡 rows of size 𝑏 = O (1 + 𝑛/𝐸) by Lemma 4.2. Since there are (log2 𝐵)𝑑 sketches, the total space is 𝑑𝑛(log 𝐵)𝑑 𝜏 𝑑 O (log 𝐵) 𝑡 (1 + 𝑛/𝐸) = O +1 . 𝐸 𝑑 A query probes at most 2𝑑 entries in each of the (log2 𝐵) sketches, and each probe reads 𝑡 repetitions. 𝑑 This gives query time O (2 log 𝐵) 𝜏 . □