Differentially Private $L_2$-Heavy Hitters in the Sliding Window Model
Authors: Jeremiah Blocki
Seunghoon Lee
Tamalika Mukherjee
Samson Zhou
Venue: ICLR 2023 notable top 25% (2023)
Keywords: differential privacy
heavy hitters
streaming algorithms
sliding window model

Abstract: The data management of large companies often prioritize more recent data, as a source of higher accuracy prediction than outdated data. For example, the Facebook data policy retains user search histories for $6$ months while the Google data retention policy states that browser information may be stored for up to $9$ months. These policies are captured by the sliding window model, in which only the most recent $W$ statistics form the underlying dataset. In this paper, we consider the problem of privately releasing the $L_2$-heavy hitters in the sliding window model, which include $L_p$-heavy hitters for $p\le 2$ and in some sense are the strongest possible guarantees that can be achieved using polylogarithmic space, but cannot be handled by existing techniques due to the sub-additivity of the $L_2$ norm. Moreover, existing non-private sliding window algorithms use the smooth histogram framework, which has high sensitivity. To overcome these barriers, we introduce the first differentially private algorithm for $L_2$-heavy hitters in the sliding window model by initiating a number of $L_2$-heavy hitter algorithms across the stream with significantly lower threshold. Similarly, we augment the algorithms with an approximate frequency tracking algorithm with significantly higher accuracy. We then use smooth sensitivity and statistical distance arguments to show that we can add noise proportional to an estimation of the $L_2$ norm. To the best of our knowledge, our techniques are the first to privately release statistics that are related to a sub-additive function in the sliding window model, and may be of independent interest to future differentially private algorithmic design in the sliding window model.

DIFFERENTIALLY PRIVATE L2- L2-HEAVY HITTERS IN THE SLIDING WINDOW MODEL
Jeremiah Blocki, Seunghoon Lee & Tamalika Mukherjee Purdue University
Samson Zhou
UC Berkeley and Rice University Houston, TX 77005, USA samsonzhoul gmail com
West Lafayette, IN 47906, USA
{iblocki, 1862 tmukher j (@purduueeddu
ABSTRACT
The data management of large companies often prioritize more recent data, source of higher accuracy prediction than outdated data. For example, the Facebook data policy retains user search histories for months while the Google data retention policy states that browser information may be stored for up to 9 months. These policies are captured by the sliding window model. in which only the most recent W statistics form the underlying dataset. In this paper. we consider the problem of privately releasing the [ hhavy hitters in the sliding window model, which include Lephhevy hitters for p s 2 and in some sense are the strongest possible guarantees that can be achieved using polylogarithmic space, but cannot be handled by existing techniques due to the sub-addicivity of the L2 norm. Moreover, existing non-private sliding window algorithms use the smooth histogram framework, which has high introduce the first differentially private
sensitivity. To overcome these barriers, algorithm for Ly-heavy hitters in the sliding window model by initiating a number of T-y-heavy hitter algorithms across the stream with significantly lower threshold. Similarly, we augment the algorithms with an approximate frequency tracking algorithm with significantly higher accuracy. We then use smooth sensitivity and statistical distance arguments to show that we can add noise proportional to an estimation of the L2 norm. To the best of our knowledge, our techniques are the first to privately release statistics that are related to sub-additive function in the sliding window model, and may be of independent interest future differentially private algorithmic design in the sliding window model.
INTRODUCTION
Differential privacy (Dwork, 2006; Dwork al., 2016) has emerged the standard for privacy in both the research and industrial communities. For example, Google Chrome uses RAPPOR (Erlingsson al., 2014) to collect user statistics such as the default homepage of the browser or the default search engine, etc., Samsung proposed a similar mechanism to collect numerical answers such as the time of usage and battery volume (Nguyên et al., 2016), and Apple uses a differentially private method (Greenberg, 2016) to generate predictions of spellings.
The age of collected data can significantly impact its relevance to predicting future patterns, as the behavior of groups individuals may significantly change over time due to either cyclical, temporary, or permanent change. Indeed, recent data is often a more accurate predictor than older data across multiple sources of big data, such as stock markets or Census data, concept which is often reflected through the data management of large companies. For example, the Facebook data policy (Facebook) retains user search histories for 6 months, the Apple differential privacy (Upadhyay, 2019) states that collected data is retained for 3 months, the Google data retention policy states that browser information may be stored for up 9 months (Google), and more generally, large data collection agencies often perform analysis and release statistics on time-bounded data. However, since large data collection agencies often manage highly sensitive data, the statistics must be released in way that does not compromise privacy. Thus in this paper, we study the (event-level) differentially private release of statistics of time-bounder data that only use space sublinear in the size of the data.
Definition 1.1 (Differential privacy (Dwork et al., 2016)). Given e > O and E (0, 1), a ran- domized algorithm A operating on datastreams is (e, -difffrrrrrlt private for every pair of

---

neighboring datasets 6 and G' for all sets E of possible outputs, we have, Pr[A(G] E S ex [A(('')) E E] +
In the popular streaming model of computation, elements of underlying dataset arrive one- one-by-one by-one but the entire dataset is considered too large to store; thus algorithms are restricted to using space sublinear in the size of the data. Although the streaming model provides theoretical means to handle big data and has been studied thoroughly for applications in privacy-preserving data analysis, e.g., (Mir al., 2011; Blocki al., 2012; Joseph al., 2020; Huang al., 2022; Dinur al., 2023) and adaptive data analysis, c.g. (Avdiukhin et al., 2019; Ben-Eliezer et al., 2022b; Hassidim et al., 2020; Braverman et al., 2021a; Chakrabarti et al., 2022; Ajtai et al., 2022; Beimel et al., 2022; Ben-Eliezer et al., 2022a; Attias et al., 2023), it does not properly capture the ability to prioritize more recent data, which is desirable quality for data summarization. The time decay model (Cohen & Strauss, 2006; Kopelowitz & Porat, 2008; Su et al., 2018; Braverman et al., 2019) emphasizes more recent data by assigning polynomially decaying or exponentially decaying weight to "older" data points, but these functions cannot capture the zero-one property when data older than a certain age is completely deleted.
The sliding window model. By contrast, the sliding window model takes large data stream as an input and only focuses on the updates past a certain point in time by implicitly defining the underlying dataset through the most recent W updates of the stream, where W > O is the window parameter. Specifically, given a stream ui,..., tm such that uy E [n]] for all i E {[mi] and a parameter W > 0 that frequency vector
we assume satisfies W < without loss of generality, the underlying dataset f E IR" induced by the last W updates of the stream Um Wm-W+1, W+1,....... Um so that fa = Ki u k}), for all e [n]. Then the goal to output private approximation to the frequency fx of each heavy-hitter, i.e., the indices & E [n]] for which ft 2 (f), which denotes the L,p norm of f for parameter p 2 1, Lpf)) = II = (
In this case, we say that streams G and G' are neighboring if there exists single update i E [m]] such that u; * u/, where u1,..., un are the updates of G and u', ... "' are the updates of G¹.
Note that if & is an heavy hitter, i.e., heavy- with respect to Lif)), then fx aLI(f) so that fa 2 a Ei= fi) 2 a (? hitter algorithm will also report the Li-heavy hitters, but the converse is not always true. Indeed, for the Yahoo! password frequency corpus (Blocki et al., 2016) (n R 70 million) with heavy-hitter threshold a = I there were 3, 977 Le-heavy hitters, but only one Ln-hevvy hitter. On the other hand, finding Leehe hitters for p > 2 requires 1nn22/p) space (Chakrabarti et al., 2003; Bar- Yossef et al., 2004), so in some sense, the Ly-heavy hitters are the best can hope to find using polylogarithmic space. Although there is large and active line of work in the sliding window model (Datar et al., 2002; Braverman & Ostrovsky, 2007; Braverman al., 2014; 2016; 2018; 2020; Borassi et al., 2020; Woodruff & Zhou, 2021; Braverman et al., 202 lb; Jayaram et al., 2022), there is surprisingly little work in the sliding window model that considers differential privacy (Upadhyay, 2019; Upadhyay& & Upadhyay, 2021).
1/2 f?? and k is also an Ly-heavy hitter. Thus, any Lz-heavy
500
1.1 OUR CONTRIBUTIONS
In this paper, we consider the problem of privately releasing approximate frequencies for the heavy- hitters in a dataset defined by the sliding window model. We give the first differentially private algorithm for approximating the frequencies of the Lz-heavy hitters in the sliding window model.
Theorem 1.2. For any a E (0, 1). > O, window parameter W on a stream of length m that induces a frequency vector f R. the sliding window model, and privacy parameter e > 1000 log there exists an algorithm such that:
/
(1) (Privacy) The algorithm is (e, -differrentt private for 8 m
(2) (Heavy-hitters) With probability at least 1 - m the algorithm outputs a list L such that & E f.for each le E [n] with fx 2 a Iz2(f) and j & f. for each j E [n) with f3 S 0 2 L2(f).
(3) (Accuracy) With probability at least 1 1. m we simultaneously have Ifre Fel < 2 for all k L. where J& denotes the noisy approximation of Sk output by the algorithm.
2

---

(4) (Complexity) The algorithm uses update where dj = m.
log" abapp
bits of space and O
log axapp
operations per
Pure differential privacy for I, -heavy hitters. Along the way, we develop techniques for handling differentially private algorithms in the sliding window model that may be of independent interest. In particular, we also use our techniques to obtain an Li-hvavy hitter algorithm for the sliding window model that guarantees pure differential privacy.
Continual release for L2-heavy hitters. Finally, we give an algorithm for continual release of L1 eyW for each estimated and L2-heavy hitters in the sliding window model that has additive error -2
heavy-hitter frequency and preserves pure differential privacy, building on a line of work (Chan et al., 2012; Upadhyay, 2019; Huang et al., 2022) for continual release. By comparison, the algorithm of (Upadhyay, 2019) guarantees O (W3/1) additive error while the algorithm of (Huang et al., 2022)
gives (e. diffferret privacy. We remark that since vW- < L2 W + +1:t) t) for any E [m]. where (2 W + 1 1) denotes the Le norm of the sliding window between times ( - W + and I, then our improvements over (Upadhyay, 2019) for the continual release of -heavy hitters actually also resolve the problem of continual release of he-heav hitters. Nevertheless, the approach is somewhat standard and thus we defer discussion to the appendix.
1.2 RELATED WORK
Dynamic structures vs, linear sketching. Non-private algorithms in the streaming model generally follow one of two main approaches. The first main approach is the transformation from static data structures to dynamic structures using the framework of (Bentley & Saxe, 1980). Although the approach has been useful tool for many applications (Dwork et al., 2010; Chan et al., 201 I; 2012; Larsen et al., 2020), it does provide a mechanism to handle the implicit deletion of updates induced by the sliding window model. The second main approach is the use of linear sketching (Blocki et al., 2012; Bassily & Smith, 2015; Bun et al., 2019; Bassily et al., 2020; Huang et al., 2022), where the data is multiplied by random matrix A to create a small-space "sketch" Az of the original dataset. Note that sampling can fall under the umbrella of linear sketching in the case where the random matrix only contains a single one as the nonzero entry in each row. Unfortunately, linear sketching again cannot handle the implicit deletions of the sliding window model, since it is not entirely clear how to "undo" the effect of each expired element in the linear sketch Az.
Adapting insertion-only streaming algorithms to the sliding window model. Algorithms for the sliding window model are often adapted from the insertion-only streaming model through either the exponential histogram framework (Datar et al., 2002) or its generalization, the smooth histogram framework (Braverman Ostrovsky, 2007). These frameworks transform streaming algorithms for either an additive function (in the case of exponential histograms) or a smooth function (in the case of smooth histograms) into sliding window algorithms by maintaining logarithmic number of instances of the streaming algorithm, starting at various timestamps during the stream. Informally, function is smooth once a suffix of a data stream becomes a (1 +)) of the entire data stream for the function, then the suffix is always (1 + a) -aprrxximation regardless of the subsequent updates in the stream. Thus at the end of the stream of say length m, two of the timestamps must "sandwich" the beginning of the window, i.c., there exists timestamps & and to such that f S m W + 1 f22 The main point of the smooth histogram is that the streaming algorithm starting at time & must output a value that is good approximation of the function on the sliding window due to the smoothness of the function. Therefore, the smooth histogram is a cornerstone of algorithmic design in the sliding window model and handles many interesting functions, such as Lp norm estimation (and in particular the sum). longest increasing subsequence, geometric mean, distinct elements estimation, and counting the frequency of a specific item.
On the other hand, there remain interesting functions that are not smooth, such as clustering (Braver- man et al., 2016; Borassi et al., 2020; Epasto et al., 2022), submodular optimization (Chen et al., 2016; Epasto et al., 2017), sampling (Jayaram et al., 2022), regression and low-rank approxima- tion (Braverman et al., 2020; Upadhyay & Upadhyay, 2021), and crucially for our purposes, heavy hitters (Braverman et al., 2014; 2018; Upadhyay, 2019; Woodruff & Zhou, 2021). These problems cannot be handled by the smooth histogram framework and thus for these problems, sliding windows algorithms were developed utilizing the specific properties of the objective functions.
3

---

Previous work in the DP setting. The work most related to the subject of our study is (Upadhyay, 2019) who proposed the study of differentially private L1 hhevy hitter algorithms in the sliding window. Although (Upadhyay, 2019) gave a continual release algorithm, which was later improved by (Huang et al., 2022), the central focus of our work is the "one-shot" setting, where the algorithm releases a single set of statisties the end of the stream, because permitting single interaction with the data structure can often achieve better guarantees for both the space complexity and the utility of the algorithm. Indeed, in this paper we present L2-heavy hitter algorithms for both the continual release and the one-shot settings, but the space/accuracy tradeoffs in the latter are much better than the former. (Upadhyay, 2019) also proposed "one-shot" algorithm, which empirically performs well, but lacks the theoretical guarantees claimed in the paper, i.e., see Section 1.3.
Privately releasing heavy-hitters in other big data models has also received significant attention. (Dwork et al., 2010) introduced the problem of I1 -heavy hitters and other problems in the pan-privacy streaming model, where the goal is to preserves differential privacy even if the internal memory of the algorithm is compromised, while (Chan et al., 2012) considered the problem of continually releasing -heavy hitters in a stream. The heavy-hitter problem has also been extensively studied in the local model (Bassily & Smith, 2015; Ding et al., 2017; Acharya & Sun, 2019; Bun et al., 2019; Bassily et al., 2020), where individual users locally add privacy to their data, e.g., through randomized response, before sending their private information central and possibly untrusted server to aggregate the statistics across all users.
1.3 OVERVIEW OF OUR TECHNIQUES
In this section, we give a brief overview of our techniques and the various challenges that they overcome. We defer full proofs to the supplementary material. We first use the smooth histogram to obtain a constant factor approximation to the L2 norm of the sliding window similar to existing heavy-hitter non-DP algorithms in the sliding window model (Braverman et al., 2014; 2018). We maintain a series of timestamps l < l2 < .... < 1, for 8 = O (logn), such that (2 : m) > (2(t2 m) > > (t,, m) and t S m - W + 1 < tz. Hence, Lz : m) is constant factor approximation to Lm(mm - W + 1 m). which is the L2 norm of the sliding window. For each timestamp i; with E [s]. we also run an L2-heavy hitter algorithm COUNTSKETCII, which outputs a list L; of size at most O + that contains the Lz-heavy hitters of the suffix of the stream starting at time 4, as well as approximations to each of their frequencies. It might be tempting to simply output noisy version of the list LI output by COUNT since 4 and l2 sandwich the start of the sliding window, m W + 1. Indeed, this is the approach by (Upadhyay, 2019), although they only consider the Li-haavy hitter algorithm COUNTMIN because they study the weaker L Li-heayy hitter problem and they do not need to run a norm estimation algorithm because L1 can be computed exactly. However, (Braverman et al., 2014; 2018) crucially note that L1 can also include a number of items that are heavy-hitters with respect to the suffix of the stream starting at time f1 but are not heavy-hitters in the sliding window because many or even all of them appeared before time m m- W +1 1. Thus although L1 can guarantee that all the L2-heavy hitters are reported by considering lower threshold, say 2. the frequencies of each reported heavy-hitter can be arbitrarily inaccurate.
Observe it does not suffice to instead report the Le-heavy hitters starting from time t2. Although this will remove the false-positive issue of outputting items that are not heavy-hitters, there is now a false-negative issue; there may be heavy-hitters that appear after time m - W + 1 but before time to that will not be detected by COUNTSKETCHY. Hence, there may be heavy- hitters of the sliding window that are not reported by Lz. See Figure 1 for an example.
Approximate counters. The fix by (Braverman et al., 2014; 2018) that is missed by (Upadhyay. 2019) is to run approximate counters for each item l E [n] reported by some heavy-hitter algorithm COUNTŠKETCH, i.e., there exists sliding window algorithm that reports constant factor approximation to the frequency of specific item & E [ra]. One way to achieve an approximate counter is to use the smooth histogram framework (Braverman & Ostrovsky, 2007), but we show that improved accuracy can be guaranteed the maintenance procedure instead considers additive error rather than multiplicative error. Given the approximate counter that reports an estimate fx as the frequency for an item & E [n)], we can then compare fa to the estimated L2 norm of the sliding window to determine whether i could possibly be an L2-heavy hitter. This rules out the false positives that can be returned in C, without incurring false negatives omitted by L2.
[s] such that k E L. An approximate counter is simply
4

---

Stream:
Active elements (sliding window)
Fig. 1: Informally, we start logarithmic number of streaming algorithms (the grey rectangles) different points in time. We call the algorithm with the shortest substream that contains the active elements the end of the stream (the blue rectangle). The challenge is that there may be heavy-hitters with respect to the blue rectangle that only appear before the active elements and therefore may be detected as heavy-hitters of the sliding window even though they are not.
Large sensitivity of subroutines. So far we have only discussed the techniques required release Ly-heavy hitters in the non-DP setting. In order to achieve differential privacy, a first attempt might be add Laplacian noise to each of the procedures. Namely, we would like add Laplacian noise to the estimate of the L2 norm of the sliding window and the frequency of each reported heavy- hitter. However, since both the estimate of the L2 norm of the sliding window and the frequency of each reported heavy-hitter is governed by the timestamps (,...., (a. then the sensitivity of each quantity can be rather large. In fact, if the frequency of each reported heavy-hitter has sensitivity Lm W + 1: m) through the approximate counters, then with high probability, the Laplacian noise added to the frequency of some reported heavy-hitter will completely dominate the actual frequency of the item to the point where it is no longer possible to identify the heavy- Thus the approximate counters missed by (Upadhyay, 2019) actually pose a significant barrier to the privacy analysis of the algorithm.
Noisy timestamps. A natural idea might be to make the timestamps in the histogram themselves noisy, e.g., by adding Laplacian noise each of the timestamps. Unfortunately, we would no longer have sketches that correspond to the noisy timestamps in the sense that if the smooth histogram maintains a heavy-hitter algorithm COUNTSKETCH, starting time & and prior to releasing the statistics, we add noise to the value of t and obtain noisy timestamp f1, then we do not actually have a streaming algorithm starting at a time f1.
Lower smooth sensitivity through better approximations. Instead, we guarantee differential privacy using the notion of smooth sensitivity (Nissim et al., 2007). The idea is the following given an a-approximation algorithm A for function with sensitivity A y. we would like to intuitively say the approximation algorithm has sensitivity ady. Unfortunately, this is not true because A(X) may report a fX) and AYY may report 1 f(Y) for adjacent datasets X and Y. However, if A is instead (1 + approxxiiitononnnn algorithm, then difference of the output of A on X and Y can be bounded by a [(X) + a S(Y) + A, through a simple triangle inequality, conditioned on the correctness of A. In other words, if a is sufficiently small, then can show that the local sensitivity of A is sufficiently small, which allows us to control the amount of Laplacian noise that must be added through existing mechanisms for smooth sensitivity. Unfortunately, if A is not correct, then even the local sensitivity could be quite large; we handle these cases separately by analyzing the smooth sensitivity of an approximation algorithm that is always correct and then arguing indistinguishabiiity through statistical distance. Therefore, we can set the accuracy of the L2 norm estimation algorithm, each Leg-heay hitter algorithm, and each approximate counter algorithm to be sufficiently small and finally we can add Laplacian noise to each procedure without significantly impacting the final check of whether the estimated frequency for each item exceeds the heavy-hitter threshold.
Pure differential privacy for Lı-heavy hitters in the sliding window model. Due to the lincarity of T. our algorithm for differentially private hh-vy hitters in the sliding window model is significantly simpler than the Lz-heavy hitters algorithm. For starters, each set of updates must contribute exactly c to the L, norm, whereas their contribution to the L2 norm depends on the particular coordinates they update. Therefore, not only do we not require an algorithm to approximate the L1 norm of the active elements of the sliding window, but also we can fix a set of static timestamps in the smooth histogram, so we do not need to perform the same analysis to circumvent the sensitivity of the timestamps. Instead, it suffices to initialize a deterministic L heavy hitter algorithm at each timestamp and maintain deterministic counters for each reported heavy-hitter. Pure differential
5

---

privacy then follows from the lack of failure conditions in the subroutines, which not possible for L2-heavy hitters.
PRELIMINARIES
For an integer O, the notation [n|] := [I.....n]] We use the notation poly(n) to represent a constant degree polynomial in and we say an event occurs with high probability if the event holds with probability
nn.
poly(x))
Differential privacy, this section, we first introduce simple or well-known results from differential privacy. We say that streams 6 and G' are neighboring. if there exists single update i E [m]] such that u, * u', where u1,..., Um are the updates of G and u',..., u/m are the updates of G'.
Definition 2.1 (L1 sensitivity). The L1 sensitivity of function U2 - R is defined by A f(y)ll
(l](x) max 110x -
The L1 sensitivity of function f bounds the amount that f can change when single coordinate of the input to changes and is often used to parameterize the amount of added noise to ensure differential privacy. We define the following notion of local L1 sensitivity for a fixed input, which can be much smaller than the (global) L1 sensitivity.
Definition 2.2 (Local sensitivity). For f U1 - R and x E U", the local sensitivity of f at is defined as LS5(2) (xx) = max (I)(=x)))((())))))))))) - f(v)lli.
Unfortunately, the local sensitivity can behave wildly for specific algorithms. Thus we have the following definition that smooths such behavior for local sensitivity.
Definition 2.3 (Smooth upper bound on local sensitivity). For 3 > 0, a function S u _ TR is a 3-smooth upper bound the local sensitivity of f uu R
(1) For all U", we have (ax) 2 (
(2) For all x. E Ut with x vll1 = 1. we have S(x) S SSy).
Even though the local sensitivity can be much smaller than the global L1 sensitivity, the Laplace mechanism adds noise scaling with the global L, sensitivity. Hence it seems natural to hope for mechanism that adds less noise. The following result shows that this is indeed possible.
Theorem 2.4 (Corollary 2.4 in (Nissim et al., 2007)). Let f U - R and S : UI" - R be 8-smooth upper bound the local sensitivity f. 3 S 2 and 8 E (0, 1), then the
mechanism that outputs f(x) + X, where X ~ Lap (2(kx) is (s, diiffernirrlll private, for 8' = (1+ exp (
Heavy hitters. We now formally introduce the Lp-heavy hitter problem and the algorithm COUNTSKETCH, which is commonly used to find the L2-heavy hitters.
Definition 2.5 (Ly--hevy hitter problem). Given an accuracythreshold parameter a E (0, 1), p and a frequency vector f E IR", report all coordinates k E [n] such that fù 2 a Lfl and no coordinates j E [m] such that f, S 8 Lf()). For each reported coordinate i [n], also report an estimated frequency fr such that Ifx ful S 7 Lp(f).
Theorem 2.6 (Heavy-hitter algorithm COUNTSKETCH (Charikar al., 2004)). Given an accuracy parameter a > O and failure probability 8 E (0, 1), there exists a one-pass streaming algo- rithm COUNTSKETCH for the Lz-heavy hitter problem that uses O ( (2. log ") words of space and update time.
O (log )
Sliding window model. In this section, we introduce simple or well-known results for the sliding window model.
Definition 2.7 (Sliding window model). Given universe U of items, which associate with [n]. let stream & of length m consist of updates UI,..., Um to the universe U, so that u, E [n] for each i [m], After the stream, window parameter W is given, which induces the frequency vector E I." so that fx = ii u, k 2 m W 1} for each l E [n]. In other words, each coordinate k of the frequency vector is the number of updates k within the last W updates.

---

We say A and B adjacent substreams of stream 6 of length m if A consists of the updates Ui....; U and B consists of the updates uj+1...., uy for some i. k [m]. We have the following definition of a smooth function for the purposes of sliding window algorithmss, not to be confused with the smooth sensitivity definition for differential privacy.
Definition 2.8 (Smooth function). Given adjacent substreams A and B, a function g uu + R is (a, smoohh if (1 B) (B) I g(B) implies (1 a)g(AUBBC)) S g C) for some parameters 0 3 < a 1 and any adjacent substream C.
Smooth functions are a key building block the smooth histogram framework by (Braverman Ostrovsky, 2010), which creates a sliding window algorithm for large number of functions using multiple instances of streaming algorithms starting at different points in time. See Algorithm I for more details the smooth histogram.
Theorem 2.9 (Smooth histogram (Braverman & Ostrovsky, 2010)). Given accuracy parameter E (0. 1). failure probability 5 (0, 1) and an (a, -mmoohh function 9 Lt + R, suppose there exists an insertion-onl streaming algorithm A that outputs a (1 + aa) approxxiiinn to with high probability using space S(a, 5, 5,m. mm,)) n) and update time T T(a, 6, m, n). Then there exists sliding window algorithm that outputs a (1 + a)pppooxiiaaooon to with high probability using
space O (S m, n) + log m) log m) and update time O ( (T 8, m, n)) logm)
Algorithm Smooth histogram (Braverman & Ostrovsky, 2010)
Input: Stream G, accuracy parameter p (0, 1), streaming algorithm A for (p,
function
Output: (1 + approxxxxiian of predetermined function with probability least 1
1: H + 0
2: for each update u, with & E [m]] do
3: + H {t)
4: for each time t, H do
5: Let v. be the output of A with failure probability poly(n,m] starting at time l, and ending
at time t.
8(p)
6:
if 13--11
Jz+1 then
7:
Delete f, from /i and reorder the indices in ll 8: Let s be the smallest index such that t, E H and t, S m W + 1.
9: Let v. the output of starting at time 4, at time
10:
return Z,
We slightly tweak the smooth histogram framework to achieve a deterministic algorithm COUNTER that can be parametrized to give additive M Maapproximation to the estimated frequency fi of particular element i E [n] in the sliding window model.
Lemma 2.10. There exists deterministic algorithm COUNTER that outputs an additive M approx- imation to the frequency of an element E [n] in the sliding window model. The algorithm uses
O M log m) bits of space.
3 DIFFERENTIALLY PRIVATE HEAVY-HITTERS IN THE SLIDING WINDOW MODEL
In this section, we give private algorithm for L2-heavy hitters in the sliding window model. Our algorithm will initially use a smooth histogram approach by instantiating a number of T- norm estimation algorithm starting various timestamps in the stream. Through sandwiching argument, these Le norm estimation algorithms will provide a constant factor approximation to the Le norm of the sliding window, which will ultimately allow heavy-hitters. Moreover, by using a somewhat standard smooth sensitivity argument, we can show that these subroutines can be maintained in way that preserves differential privacy.
determine whether elements of the stream
To identify a subset of elements that can be heavy-hitters, we also run a private L2 hitters algorithm starting each timestamp. Unfortunately, because the timestamps do not necessarily
7

---

coincide with the beginning of the sliding window, it may be possible that depending on approach, we may either output a number of elements with very low, possibly even zero, frequency, or we may neglect to output number of heavy-hitters To overcome this issue, maintain a private algorithm COUNTER that outputs an estimated frequency for each item that is reported by our private Tz2-heavy hitters algorithms, which allows us rule out initially reported false positives without incurring false negatives. We give the algorithm in full in Algorithm 2.
Algorithm 2 Differentially private sliding window algorithm for Ly -havy hitters
Input:
Stream 6, accuracy parameter a E (0, 1), differential privacy parameters e, 6 O, window
parameter W > 0, size n of the underlying universe, upper bound m on the stream length Output: A list C of L2-heavy hitters with approximate frequencies
1: Process the stream G, maintaining timestamps ,,....14 at each time & E [m]] so that for each
2 ;)
E [s]. either = 8, 1,+1 = t; + 1 or L2(t,, t) - 1+
La (f(4+11,t) through a
1000 log
smooth histogram with failure probability 2m
2: Implement heavy-hitter algorithm COUNTSKETCH on the substream starting t, for each E [s]
agg with threshold 500 and failure probability 2m
3: Set maxçi é
[s] S W
1} on window query W >> 0
4: Set L2 to be
-aproximationn to L2 () from the smooth histogram and
500 log
X + Lap
Lg
40 log
5: for each heavy-hitter & [mi] reported by COUNTSKETCH starting at la do
6: Run COUNTER with additive error 1o00 m.
a'e L2 for each reported heavy-hitter
7: Let fir be the approximate frequency reported by COUNTER
8: Y& Lap 75 m L22 Zz Lap 75 L2) fr. Jr Zx
9:
if Th 2 30
$ XX2 + YR then
+ CU [(k, fa)
11:
return L
We first describe the procedure for the approximate frequency estimation for each reported heavy- hitter. Let COUNT be Ly-heavy hitter algorithm starting at timestamp tas where max(ic E [s] : 4 S m W + 1} on window query W > For a coordinate & E [n that is reported by COUNTŠKETCH, from times i through m, use COUNTER maintain number of timestamps such that the frequency by roughly a² /16/ the same pass as the rest of the algorithm.
on the suffixes induced by the timestamps are arithmetically increasing 16. We emphasize that run the COUNTER for each reported heavy-hitter in
Lemma 3.1. Let & be the event that (1) the smooth histogram data structure does not fail, (2) all instances of COUNTSKETCH do not fail, and (3) X S - L2(f) and max (Y,, f Z,) S clalf)) Let COUNTSKETCH, be the instance of COUNTSKETCH starting at time la- Conditioned E, then for each reported heavy-hitter k by COUNTSKETCH.,, Algorithm 2 outputs estimated frequency fa log m
such that lfx fall S
500 log Lz(f). The algorithm uses O (يبي log" m) space and O
update time per instance of COUNTSKETCH.
We first show that the list L output by Algorithm 2 does not contain any items with "low" frequency. Lemma 3.2 (Low frequency items are not reported). Let be the event that (1) the smooth histogram data structure does not fail, (2) all instances of COUNTSKETCH do not fail, and (3) X < La(J) and
alz(f) Let f be the frequency vector induced by the sliding window parameter W and suppose fx Σ (2( Then conditioned on E, k & L.
maxje(n] Zy) <
10
We then show that the heavy-hittee are reported and bound the error in the estimated frequency for each reported item.
Lemma 3.3 (Heavy-hitters are estimated accurately). Let f be the frequency vector induced by the sliding window parameter W. Let & be the event that (1) the smooth histogram data structure does
8

---

6 not fail, (2) all instances of COUNTSKETCH do not (3) Laif) and ja ((n))e(((() (Y,, Zz, _
LL((f) Conditioned on &, then E for each k E [n] with f& 2 a L2(f). Moreover, for each item 10
& Ifx - Fu 500 L2(f).
We show that the event & conditioned by Lemma 3.1, Lemma 3.2, and Lemma 3.3 occurs with high probability.
Lemma 3.4. Let & be the event that (1) the smooth histogram data structure does not fail either stream, (2) all instances of COUNTSKKTCH do noif,, and (3) X < 10
Lelf) and maxje([] (M)))(())) Zz) S
oL2(f) Then Pr [r 10
2
m²
Before analyzing the privacy guarantees of Algorithm 2, must analyze the local sensitivity of its subroutines. We first show a 3--smoohh upper bound on the local sensitivity of the frequency moment. We defer this statement the supplementary material and also show the similar following 3-smooth upper bound on the local sensitivity for each estimated frequency output by Algorithm 2.
Lemma 3.5 (Smooth sensitivity of the estimated frequency). Let & be a data stream of length m. that induces frequency vector f and let füe be the estimate of the frequency of a coordinate l [n]] output by the smooth histogram. Define the function h(f) by
Fkr
if fx 1000 log (f S fk S fx
a²e
a² log L2(f),
h(f) =
fk
L2(f),
if fx
fx
1000 log L2(f), and
2
1000 log
Jk
+ 1000 log L2(s),
if f Su + 1000 log L2(J).
5
Then the function S(f)
h(s) + 2 is a B-smooth upper bound on the local sensitivity of 1000 log m and sufficiently large W. v W
a
200 log
for 3 Z
150 log
With the structural results smooth sensitivity in place, we show that Algorithm 2 is (s, 6)- differentially private.
Lemma 3.6. There exists an algorithm (see Algorithm 2) that is (eiff-diifr private for (0, 1), & VWa
lo and 8 > m²
Ta()) each Jh. with k L.
Since Algorithm 2 further adds Laplacian noise Z Lap log m
then Lemma 3.3 implies that the additive error to fie 50 log m L2(f) + Lap 75 log m E2(t) for
each reported coordinate & E [n).
Thus through Lemma 3.6 (privacy), Lemma 3.2 and Lemma 3.3 (heavy-hiter//cccuraa)) and a simple analysis for space complexity, have Theorem 1.2, our main result for differentially private L2-heavy hitters in the sliding window model.
Pure differential privacy for -heav hitters and continual release for T-zheavy hitters in the sliding window model. To achieve pure differential privacy, we use deterministic -heaay hitter algorithm MISRAGRIES at each timestamp and maintain deterministic counters for each reported heavy-hitter. Due to the linearity of L1, the global L1 sensitivity of our algorithm is at most 2 and thus suffices to use the Laplace mechanism guarantee pure differential privacy.
To achieve continual release of Le-heavy hitters in the sliding window model, our algorithm consists of L O (log W) O (log n) levels of subroutines. In each level [L]. we split the stream into continuous blocks of length S₃ := 2 av/W 100 log W Given threshold parameter a > 0, for each block in level é, we run MISRAGRIES with threshold भ At the end of the stream, we stitch together sketch of the underlying dataset represented by the sliding window through a binary tree mechanism. Due to a sharper balancing argument and analysis than previous work for continual release of L1 heavv hitters, sufficiently small error to catch the L2-heavy hitters. We defer full details both procedures to the supplementary materials.
obtain more accurate estimates of each item, which translates to

---

ACKNOWLEDGEMENTS
We would like to thank Sofya Raskhodnikova for clarifying discussions about smooth sensitivity. Jeremiah Blocki was supported in part by NSFCCF-1910659, NSF award CNS-2047272. Seunghoon Lee was supported by NSF CAREER award CNS-2047272. Tamalika Mukherjee was supported in part by Purdue Bilsland Dissertation Fellowship, NSF CCF- 1910659, and NSF CCF-2228814 14. Work done in part while Samson Zhou was Carnegie Mellon University and supported by a Simons Investigator Award David P. Woodruff and by the National Science Foundation under Grant No. CCF-1815840.
and NSF CAREER
REFERENCES
Jayadev Acharya and Ziteng Sun. Communication complexity in locally private distribution estimation and heavy hitters. In Proceedings of the 36th International Conference on Machine Learning, ICML, pp. 51-60, 2019.
Miklós Ajtai, Vladimir Braverman, S. Jayram, Sandeep Silwal, Alee Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS '22: International Conference on Management of Data,, pp. 15-27, 2022.
Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. framework for adversarial streaming via differential privacy and difference estimators. In 14th Innovations in Theoretical Computer Science Conference, ITCS, pp. 8:1-8:19, 2023.
Dmitri Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. Adversarially robust submodular maximization under knapsack constraints. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD, pp. 148-156, 2019. 2
Ziv Bar- Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. Comput. Syst. Sci., 68(4))702-732, 2004.
Raef Bassily and Adam D. Smith. Local, private, efficient protocols for succinet histograms. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC, pp. 127-135, 2015. 3,4
Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. Practical locally private heavy hitters. J. Mach. Learn. Res., 21:16:1-16:44 2020. 3,4
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1671-1684, 2022.
Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense-sparse trade-offs. In 5th Symposium on Simplicity in Algorithms, SOSA@SODA 2022, pp. 214-227, 2022a. 2
Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adversari- ally robust streaming algorithms. J. ACM, 69:2):1::1117:33, 2022b.
Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: static-to-dynamic transformation. Algorithums, 14))3001-388, 1980. 3
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-lindenstran transform itself preserves differential privacy. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 410-419, 2012. 2,3
Jeremiah Blocki, Anupam Datta, and Joseph Bonneau. Differentially private password frequency lists. In 23rd Annual Network and Distributed System Security Symposium, NDSS, The Internet Society, 2016. 2
10

---

Michele Borassi, Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghad- dam. Sliding window algorithms for k-clustering problems. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020. 2,3
Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Anmual IEEE Symposium on Foundations of Computer Science (FOCS), Proceedings, pp. 283-293, 2007. 3,4
Vladimir Braverman and Rafail Ostrovsky. Effective computations on sliding windows. SIAM J.
Comput., 396))2113-2131, 2010. 7
Vladimir Braverman, Ran Gelles, and Rafail Ostrovsky. How to catch Le-heavy-hitters on sliding windows. Theor. Comput. Sci., 554:82-995 9444 2014. 2,
Vladimir Braverman, Harry Lang, Keith Levin, and Morteza Monemizadeh. Clustering problems sliding windows. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium Discrete Algorithms, SODA, pp. 1374-1390, 2016. 2,3
Vladimir Braverman, Elena Grigorescu, Harry Lang. David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 7:1-7:22, 2018. 3,4
Vladimir Braverman, Harry Lang, Enayat Ullah, and Samson Zhou. Improved algorithms for time decay streams. In Appraximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp. 27:1 27:1-27:17, 2019. 2
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 517-528, 2020. 2.3
Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pp.
2021a.
Vladimir Braverman, Viska Wei, and Samson Zhou. Symmetric norm estimation and regression on sliding windows. In Computing and Combinatorics 27th International Conference, COCOON, Proceedings, pp. 528-539, 2021b. 2
Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. ACM Trans. Algorithms,, 15(4):51:1-51:400 2019. 3,
Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th Annual IEEE Conference on Computational Complexity, pp. 107-117, 2003. 2
Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In 13th Innovations Theoretical Computer Science Conference, ITCS, pp. 37:1-37:23,
2022."7 2
T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Trans. Inf. Syst. Secur,, (433):6:1122:222 2011.
T.-H. Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. Differentially private continual monitoring of heavy hitters from distributed streams. In Privacy Enhancing Technologies 12th International Symposium, PETS. Proceedings, pp. 140-159, 2012. 3,
Moses Charikar, Kevin C. Chen, and Martin Farach-Colton. Finding frequent items in data streams.
Theor. Comput. Sci., 312(1):3-15, 2004. 6
11

---

Jiecao Chen, Huy L. Nguyen, and Qin Zhang. Submodular maximization sliding windows. CoRR, abs/1611.000 2016. 3
Edith Cohen and Martin J. Strauss. Maintaining time-decaying stream aggregates. J. Algorithms, 59 (1):19-36, 2006. 2
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics sliding windows. SIAM J. Comput., 3166): 2002. 2,3
Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In
Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 3571-3580, 2017.
Itai Dinur, Uni Stemmer, David P. Woodruff, and Samson Zhou, On differential privacy and adaptive data analysis with bounded space. CoRR, abs/2302.05577, 2023. 2
Cynthia Dwork. Differential privacy. In Automata, Languages and Programming, 33rd International Colloquium, ICALP, Proceedings, Part II, pp. 1-12, 2006.
Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, and Sergey Yekhanin. Pan-private streaming algorithms. Innovations Computer Science ICS. Proceedings, pp. 66-80, 2010. 4
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. J. Priv. Confidentiality, 703):17-51, 2016. 1
Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam. Submodular optimization over sliding windows. In Proceedings of the 26th International Conference World Wide Web, www, pp. 421-430, 2017. 3
Alessandro Epasto, Mohammad Mahdian, Vahab S. Mirrokni, and Peilin Zhong. Improved sliding window algorithms for clustering and coverage via bucketing-based sketches. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 3005-3042, 2022. 3
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: randomized aggregatable privacy- preserving ordinal response. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pp. 1054-1067, 2014.
Facebook. https://www..faccbooo.co//pppppp
Google. https://policies.googg// http:///pdes.ooooooco////////hep
1
Andy Greenberg. Apple's 'differential privacy'is 'is about collecting your data-but not your data. Wired, June, 13, 2016.
Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems, NeurlPS, 2020. 2
Ziyue Huang, Yuan Qiu, Ke Yi, and Graham Cormode. Frequency estimation under multiparty differential privacy: One-shot and streaming. Proc. VLDB Endow., 15(10):2058-2770, 2022. 2, 3,
Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Truly perfect samplers for data streams and sliding windows. In PODS '22: International Conference on Management of Data, pp. 29-40. 2022. 2,
Matthew Joseph, Aaron Roth, Jonathan R. Ullman, and Bo Waggoner. Local differential privacy for evolving data. J. Priv. Confidentiality, 10(1), 2020. 2
Tsvi Kopelowitz and Ely Porat. Improved algorithms for polynomial decay and time-decay with additive error. Theory Comput, Syst. 42(3):349-365 2008. 2
12

---

Kasper Green Larsen, Tal Malkin, Omri Weinstein, and Kevin Yeo. Lower bounds for oblivious near-neighbor search. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1116-111 1111-11344 1134, 2020.
Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. In Proceedings of the 30th ACM NGGMOD-SGGACTSSGARRT Symposium on Principles of Database Systems, PODS, pp. 37-48, 2011.
Thông Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, and Junbum Shin. Collecting and analyzing data from smart device users with local differential privacy. CoRR, abs/1606. 05053, 2016.
Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium Theory of Computing, pp. 75-84, 2007. 6,
Shang-Y Yu Su, Pei-Chich Yuan, and Yun-Nung Chen. How time matters: Learning time-decay attention for contextual spoken language understanding in dialogues. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics:
Human Language Technologies, NAACL-IILT, pp. 2133-2142, 2018.
Jalaj Upadhyay. Sublinear space private algorithms under the sliding window model. Proceedings of the 36th International Conference Machine Learning, ICML, pp. 6363 6372, 2019. 1, 2, 4, 5
Jalaj Upadhyay and Sarvagya Upadhyay. A framework for private matrix analysis in sliding window model. In Proceedings of the 38th International Conference on Machine Learning, ICML, pp. 10465-10475, 2021. 2,
David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1183-1196. IEEE, 2021. 3
13


Reviews:
[{"review_id": "msspzEB4h2", "reviewer": "Reviewer_jYg8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of how to compute $L_2$-heavy hitters in the sliding window model under differential privacy. The main contribution is giving the first differential private algorithm for this problem using sublinear working space. ", "summary_of_the_review": "The paper provides the first sublinear space algorithm for sliding window $L_2$-heavy hitters under differential privacy. However, the guarantee on privacy is weak and thus less interesting. The writing of the paper could also be improved to be more friendly to typical ICLR audience.", "strength_and_weaknesses": "Strength:\n1. The $L_2$-heavy hitter problem in the sliding window model is important.\n2. A sublinear space algorithm under differential privacy is provided, which rigorous theoretical guarantees.\n\nWeaknesses:\n1. For the privacy guarantee, $\\delta = O(\\frac{1}{m^2})$ is somewhat weak. Often in differential privacy it is insisted that $\\delta$ is cryptographically negligible.\n2. The privacy guarantee is only for one-shot computation. I think in streaming data analysis especially under sliding window model, it is much more practical to consider online and adaptive data analysis. \n3. The paper is quite dense, and it seems to me that the writing of the paper mainly aims for theory audience and it could be difficult for a typical ICLR audience to understand the main ideas.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "I4Fexn7apJ", "reviewer": "Reviewer_EhqA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers the problem of finding $L_2$ heavy hitters in the sliding window model with differential privacy. If we relax either the privacy or the sliding window requirement, there were efficient algorithms but not with both. \nIt gives an efficient algorithm for this problem with polylog space. ", "summary_of_the_review": "The problem is interesting to the DP community, and potentially relevant in practice. My primary concern is about the restriction on $\\epsilon$, which makes the result rather limited in scope. If there is an argument for why it should degrade for smaller windows or small $\\alpha$, I might be more inclined to accept the paper. As it stands, I would lean to reject. ", "strength_and_weaknesses": "I would consider the problem important, but perhaps a little specialized. Technically, the paper seems to put together several ingredients from the literature on DP and heavy hitters in the right way.  On one hand, I think it is above the bar technically. On the other hand, I cannot put my finger on any one ingredient which strikes me as particularly novel, it appears that the contribution is to understand the literature well, select the right tools and put them together in the right way,. \n\n\nMy main concern about the result is that as I understand it, the privacy parameter $\\epsilon$ is rather large. The theorem states that $\\epsilon > log(m)/(\\alpha^3 \\sqrt{W})$. It seems that if the window size needs to be at least $(log(m))^2/\\alpha^6$ to have reasonable privacy guarantees.  This is followed by a comment about general $\\alpha, \\epsilon$ which did not make sense to me.\n1.  They say that they allow $\\alpha \\geq 1$. I thought $\\alpha$ is the fraction of the two norm $\\|f\\|_2$ coming from $f_i$, so having it greater than $1$ seems to not parse.  \n2. For general $\\epsilon$, they say something about additive error in the utility. I am not sure if they are referring to (2) which is the heavy hitters guarantee, or (3) which is the accuracy guarantee. For how small an $\\epsilon$ can the algorithm guarantee  the right list of heavy hitters?\n \nIt seems plausible that to get good estimates to the frequencies, one needs large $\\epsilon$. Even for this, it seems that the bounds here are rather large.  What is less clear is to what extent getting the set of heavy hitters correct depends on the noise parameter.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "HTMeRhxQ2L9", "reviewer": "Reviewer_1XJv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper gives a streaming algorithm for \\ell_2 heavy-hitter problem in the sliding window setting. In particular, for frequency threshold \\alpha, privacy parameter \\epsilon, stream length m, the algorithm uses poly(eps^{-1} \\alpha^{-1} log m) space, to report a list of coordinates that have real frequency between \\alpha / 2 L_2(f) to \\alpha L_2(f), where f is the frequency vector. Furthermore,  it also gives a point-wise frequency estimation with additive error \\alpha /4 L_2(f) for the reported coordinates. This algorithm only generates output at the end of the stream, hence is the so-called “one-shot” algorithm. As a secondary result, the stronger continual release algorithm is also obtained, with point-wise additive error \\alpha \\sqrt{W} / 2, where W is the size of the sliding window.\n", "summary_of_the_review": "The lack of empirical evaluation is a weakness, but I find the theoretical contribution solid, and I wish to recommend for acceptance.", "strength_and_weaknesses": "# Strength:\n\nThe paper is technically nontrivial. It starts with the smooth histogram framework which is standard in designing (streaming) algorithms in the sliding window setting. However, it is observed that the \\ell_1-sensitivity, which is a crucial complexity measure for differential privacy, may be unbounded, and thus the naive Laplacian mechanism cannot be applied. To this end, the smoothed sensitivity framework (Nissim et al., 2007) is applied, and I find the analysis of the smoothed sensitivity for (a certain implementation of) smooth histogram framework interesting, and it may be of independent interest.\n\n# Weakness:\n\nThere is no empirical evaluation. For instance, it may be interesting to see how the privacy hurts the accuracy, by comparing with the non-private \\ell_2-heavy hitter algorithms.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BbpA9FHWZ6U", "reviewer": "Reviewer_eT6L", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers differentially private algorithms for finding heavy hitters over a sliding window in the streaming model. I.e., given a stream of updates, and a parameter $W$, the goal is to be able to compute the elements whose frequency dominates the last $W$ updates of the stream. In particular, the goal is compute the elements whose frequency is an $\\alpha$-fraction of the $L_2$ norm of the frequency vector of suffix of the stream of length $W$. This is already a non-trivial problem without privacy constraints, and is even more challenging if we require the algorithm to satisfy differential privacy.\n\nThe main result of the paper is an algorithm for the problem above that uses the smooth histogram framework from streaming algorithms, and the smooth sensitivity method from differential privacy (there is no connection between the two notions of \"smooth\" here). The approximation $\\alpha$ is on the order of $\\left(\\frac{\\log m}{\\varepsilon \\sqrt{W}}\\right)^{1/3}$, where $m$ is the length of the stream. ", "summary_of_the_review": "The paper gives guarantees for the natural problem of privately computing heavy hitters over a sliding window, and does so using an interesting combination of techniques. The results are likely not tight, and the write-up can be polished further.", "strength_and_weaknesses": "Private streaming algorithms on sliding windows may be a bit of a niche area, but I think the problems are interesting and reasonably well motivated. The quantitative bounds on the accuracy $\\alpha$ and on the space complexity are probably not tight, and the dependence on several parameters is quite bad. Still, I consider the techniques interesting, and, as already mentioned, the problems are natural and motivated.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%