Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
It gives an efficient algorithm for this problem with polylog space. 
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,. 


My 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.
1.  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.  
2. 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?
 
It 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.

clarity,_quality,_novelty_and_reproducibility: Good.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: Strength:
1. The $L_2$-heavy hitter problem in the sliding window model is important.
2. A sublinear space algorithm under differential privacy is provided, which rigorous theoretical guarantees.

Weaknesses:
1. 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.
2. 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. 
3. 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.
clarity,_quality,_novelty_and_reproducibility: See "Strength And Weaknesses" section.
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

strength_and_weaknesses: # Strength:

The 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.

# Weakness:

There 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.

clarity,_quality,_novelty_and_reproducibility: # Clarity:

1. You also mentioned \ell_1-heavy hitters in “our contributions” section. I don’t really get the improvement/context. Please clarify. In general, why do we care much about the \ell_1 case if the paper is mostly about \ell_2 (and I find it a bit confusing)?
2. In Sec 1.3, you used notations “L_2(t_1 : m)” — I guess it means the L_2 norm of the frequency vector defined with the items arriving between time step [t_1, t_1 + m). But I cannot find where this is defined in the discussion.
3. Page 6, the paragraph “Sliding window model”, you started with “in this section”, which sounds weird since it is already in the middle of the section
4. A minor comment: Algorithm 2 has inconsistent styles — “Set” is in capitalized, while “for/if” is not.

# Quality:

This is a theoretically solid paper. However, considering the audience in ICLR, it may be better to also provide an empirical study.

# Originality:

The \ell_2-heavy hitter is a central problem in the analysis of the frequency vector. The study of the problem in the sliding window is well motivated, and given the context, I find it timely. Even though the paper uses previous frameworks, but I find making them to fit nontrivial, which requires a certain level of technical novelty.

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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.

The 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. 
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.
clarity,_quality,_novelty_and_reproducibility: The write-up can be unclear in some places. One issue that's not explained carefully is why the instances of the Counter algorithm can be run in the same pass as the rest of the algorithm. The issue is that the CountSketch will report heavy hitters at different time steps, so are the Counter-s started at these different time steps? Why is that not an issue for approximating the frequencies of these elements accurately? Presumably because they were light before the Count Sketch identified them as heavy? I did not find a clear explanation of this in the main submission, and also not in supplementary material after skimming it, although I may have missed something. 
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper addresses a recently standard program in DP analysis. It develops some new techniques for doing so, and the analysis is non-trivial.

justification_for_why_not_higher_score: I do not think the subject is of a lot of interest to the general audience.
justification_for_why_not_lower_score: It's good to reward a well-crafted paper with at least a spotlight slot.
Decision: Accept: notable-top-25%