Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proves that Indyk's classical Fp streaming algorithm for frequency moments satisfies the differential privacy (DP) requirements whenever p is in (0,1).

This leads to the first DP streaming algorithm for this problem with polylog space.

The new proof is based on a novel analysis of the sensitivity of this algorithm: how much does the output change when the input changes by a bit.


main_review: The result is interesting and satisfying. The problem is important and it's good to have DP algorithms for it. The technical contribution is strong.

The main weakness is that the result only works for p in (0,1) and therefore feels incomplete. 
summary_of_the_review: Strong and interesting results. Slightly incomplete, but still a good contribution.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The main result of the paper is that Indyk’s p-stable distribution sketch of the $\ell_p$ norm of a stream itself preserves differential privacy, without any additional randomization. The privacy loss parameter is a function of the length of the stream, the maximum value of any update, and the universe size. The privacy loss improves when the length of the stream goes to infinity with respect to the other parameters. 
main_review: There has been a growing literature showing that different sketching techniques from the streaming literature preserve differential privacy. By now this is known for the Johnson-Lindenstrauss sketch of the $\ell_2$ norm, and the Flajolet-Martin distinct counts sketch. This paper adds to this line of work by showing that Indyk’s p-stable distribution sketches, which can be seen as an extension of the Johnson-Lindenstrauss sketch to $\ell_p$ norms for $p \in (0,2]$, also preserve differential privacy. The main idea is to first bound the *multiplicative* sensitivity of the $\ell_p$ norm, and then bound the ratio of the pdfs of the sketch for two neighboring streams in terms of this sensitivity. 

The result is technically interesting, and provides further evidence that techniques from sketching are inherently privacy preserving. For this reason, I think the paper makes a nice conceptual contribution. Unfortunately, the authors don’t really give applications of their result. I would’ve liked to see an example scenario when would one want to publish a p-stable sketch of a stream? Since the randomness of the sketch itself must be kept hidden in order to protect privacy, this result is not applicable in a distributed setting, or in the pan-privacy setting, and I would like to see an example in which it is applicable. 

Further detailed comments:

* Often these sketches are applied to the difference of two streams, in order to estimate the $\ell_p$ distance between them. In such cases the $v_i$ values might be negative. Can the analysis techniques here be extended to handle this situation?

* What is $\alpha$ in Definition 2?

* In Definition 3 and Theorem 1 you could just talk about functions rather than deterministic mechanisms.

* The RHS of (3) is also a direct application of Holder’s inequality.

* The authors claim that Theorem 2 was previously proven by Mir et al's PODS 2011 paper, but I cannot find any such result there. What theorem in that paper gives this result?

* In the proof of Theorem 2, please specify that the ratio of pdfs is a decreasing function *of $x$*.

* I can’t fully follow the proof of Theorem 3. Some comments:
- give a reference or prove that $\mathcal{D}_{p,1}(x)$ is increasing for $x \le 0$ and increasing for $x \ge 0$; also, I don’t understand how the upper bound on the ratio of pdfs follows from this fact;
- why is it sufficient to show (4), and how does this follow from the second derivative of $(1+u^{1/2})e^{-u^{1/2}}$?

* Instead of subsampling, can’t you improve the privacy loss parameter by padding the stream in order to increase $n$?
summary_of_the_review: This paper makes an interesting technical contribution, giving further evidence that sketching techniques from the streaming literature preserve differential privacy without further randomization. The paper can be accepted, although it would be stronger if the authors gave applications of their results.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers the problem of computing the p'th frequency moment for p\in (0,1] with \eps-Differential Privacy (or \eps-DP). I.e. it presents a randomized algorithm that given a stream of key-values pairs estimates the p-th frequency moment (of a vector indexed by the key and whose entry is the sums of values for the given key) that satisfies the property that given two key-value pair streams \S and \S' of the same size such that they differ in exactly on key-value pair, the probability that the output of the mechanism on \S and S' fall in the same measurable subset of the output space differ by a multiplicative e^{\eps} factor.

In fact the paper shows that an existing data stream algorithm due to Indyk based on p-stable distributions gives \eps-DP guarantees. Using standard techniques from DP literature, the paper shows how to amplify the privacy guarantee by subsampling. The space complexity of the algorithm in the paper is only a log factor away from the optimal space complexity of non-private frequency moment estimation.

The main technical ingredient is the use of what the paper calls _pure multiplicative sensitivity_ of the p'th frequency moment function (this notion was used for p=1 in Mir et al. (2011)). The bound on the pure multiplicative sensitivity follows from (fairly) simple algebra. Converting the sensitivity bound into \eps-DP guarantee reduces to showing a certain exponential depending on the p-th frequency moment is positive definite (which is done using the Laplace transform of the exponential).

The paper also presents some experimental results on the accuracy bounds for the algorithm on real and synthetic data.
main_review: The following are the strengths of the paper:

(+) The paper presents a solid theoretical result for a very (at least mathematically) natural problem.

(+) The paper shows that an existing algorithm for the frequency moment problem in the data stream literature is also \eps-DP. This is really nice since it shows that an existing algorithm is more powerful than what was already known.

(+) It seems like the notion of pure multiplicative sensitivity is new or perhaps more accurately not that well explored in the DP literature.

The main weakness of the paper are mostly from motivational/presentation for me:

(-) The paper starts off with some applications of p'th moment for p=1 and p=2 but from what I can tell there are no applications given for p\in (0,1), which is the range where the results in the paper are new. While it is mathematically natural to study the DP of this problem, one thing missing is to show (if possible) what _potential_ practical applications exists from having an \eps-DP algo for computing the p-th frequency moments for p\in (0,1).

(-) It would be useful to have a sense for why proving the results in the paper are hard? Or put another way what are the new technical ideas that are unique to this paper that was not present before that prevented previous works to solve the current problem? The paper states that the notion of pure multiplicative sensitivity is new but it also seems like the definition was already used for p=1 in Mir et al. (2011).

(-) From a theoretical point of view one potential drawback is that the result only holds for the turnstile model: i.e. where each update is positive. It seems like this is needed in proof of Thm 3 in the paper but it's not clear to me if this assumption is reasonable for potential applications of the results in the paper.

(-) The presentation of the paper is not ideal, though the issues I found (see details below) should be easily fixable.

(*) This is not really a concern but the paper did not have an ethics statement. While I can understand that the authors think that since the results in this paper are theoretical there are not ethical issues. While it is correct that there are no direct ethical issues, I would encourage the authors to think about potential mis-uses of the the algorithm by someone who potentially uses the results in this paper. Listing those in an ethical statement could be of use to others.

Below are some comments for the authors to improve on the presentation:

[Pg. 3, Def 2] \alpha (in the last line of def) is not defined.

[Algo 1] Is \delta needed? Also at this point "accuracy constraint" is not defined.

[Thm 1] When you say \M calculates F_p "accurately" what does it mean? Do you mean exactly? Another Q: is the \rho_M the same as \rho_p that is used in Thm 3? Finally the bound on \rho_M should have \le instead of =.

[Proof of Thm 1, para 1] The setting seems different from that on Def 3: why does this not affect the final bounds/results? Please justify.

[Pg. 6, line below first display eq] The claim after "Observe that" is not clear: the p-stability does not mention the constant of proportionality while the claimed equality uses the the fact that the constant of proportionality is \zeta^{-1/p}. Some justification of this would be nice.

[Pg. 6, proof of Thm 3] If there is space it would be nice to define the Laplace transform as well.

[Algo 2] \delta not required?

[Comparison with Kane et al. above Thm 5] When claiming that the space requirement of Algo 2 is close to Kane et al. is it for the same accuracy requirement on Kane et al.?

summary_of_the_review: Theoretically, the paper seems nice but it could be made stronger by providing motivations for the specific problem being studied in the paper, giving better intuition for what technically is new in this paper and by possibility solving the problem for the case when the updates can be negative. These reason being the paper a bit below a clear accept for me.

Post rebuttal comments
----------------------------

The authors have addressed most of my concerns about the paper. I'm still not super-convinced about the usefulness of the result for the entire range $p\in (0,1]$ since the entropy applications seems only to need values $p=1-\Delta$ for $\Delta\to 0$. However, _theoretically_ studying the whole range still makes sense. After the rebuttal the paper is more of a 7 for me.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors show that the $\mathbb{F}_p$ sketch for frequency moments estimation is differentially private, as is,
for $p\in (0, 1]$. Other special cases for frequency moments estimation have been studied previously in the
literature (e.g., Choi et al., 2020, Smith et al., 2020, who study cases for $p = 0, 1, 2$).

For $p\in (0, 1]$, the authors build upon the $\mathbb{F}_p$ sketch of (Indyk, 2006) and show DP properties.
Specifically, they show, in Theorem 3,
that the $\mathbb{F}_p$ sketch of Indyk is $1/p\cdot \ln\rho_p$ where
$\rho_p$ is the **multiplicative sensitivity** of the $p$-th frequency moment.

The authors also present basic experimental evaluation of their algorithm (see Figure 3).
They also claim (wrongly, in my opinion) that their algorithm is the first with polylog space complexity
for $F_p$ estimation.
main_review: **Updated my review to be more positive**

Strengths: They provide reasonable bounds to show that the $\mathbb{F}_p$ sketch of (Indyk, 2006) is
$(1/p\cdot \ln\rho_p)$-DP.  I like the flow of the exposition. This is a valuable contribution to the DP literature.

Weaknesses: The privacy parameter is not a constant but the DP guarantee should be a constant.
e.g., $\epsilon \in(0, 1])$. But this is not the case with this paper, rendering the paper
a little bit dangerous for the DP research community. There are other (perhaps minor) details about
proofs I'd like the authors to clarify. Also, the "real-world" dataset is not specified well (where is it from?). The description of the experiments on Page 9 should be a lot more detailed!

Their algorithm
provides, sometimes, vacuous privacy guarantees and inadequate accuracy.
We ideally want privacy of $\epsilon \leq 1$ but this seems to
only happen when $p$ is very close to 1.
If $\rho_p$ is the **multiplicative sensitivity** of the $p$-th frequency moment, then the
algorithm (the $\mathbb{F}_p$ sketch of Indyk) is $1/p\cdot \ln\rho_p$-DP, which is not a constant.

As described in several DP surveys, $\epsilon$ should be
a constant (ideally between 0 and 1).  But it appears this is not the case for the $\mathbb{F}_p$ sketch of
Indyk. I still think that certain improvements could help make this $\epsilon$ a constant.
As a baseline, the algorithm that uses sampling, to amplify privacy, can maintain polylogarithmic space complexity.
A $\epsilon$-DP algorithm (for $\epsilon\leq 1$)
that chooses, uniformly and at random, $\gamma n$ entries out of $n$ becomes $2\gamma\epsilon$-DP. Clearly,
if the algorithm uses polylog space for storing the samples, then this could serve as a baseline for
comparison for the $F_p$ sketch. (I recognize the authors also use privacy amplification by sampling but on top of the $F_p$ sketch.)

Also, the authors claim to give the first DP frequency estimation protocol with polylog space complexity
but this is clearly not the case. It is known, in the streaming literature, that for $p  > 2$,  the
space for $F_p$ estimation must be polynomial whereas polylogarithmic factors are achievable for
$p\leq 2$. And since there are DP algorithms for $p=0, 1, 2$, polylog space complexity has already
been achieved previously.


Other technical comments:

- In proof for Theorem 1 (page 4): in the first line after "to lower bound expression (1)", the
$(m-1)^{1-p}$ changes to $(m-1)^{p-1}$ in the next line. Is this a typo?

- The proof of Theorem 3 assumes that $\rho_p\geq 1$. Is this always the case?

- Proof of Theorem 5: How did you derive the variance of the sub-sampling process? Doesn't seem quite right to me.

## Post-Rebuttal Comments
The authors have addressed all my concerns.
summary_of_the_review: 1) They provide reasonable bounds to show that the $\mathbb{F}_p$ sketch of (Indyk, 2006) is $(1/p\cdot \ln\rho_p)$-DP.  I like the flow of the exposition. This is a valuable contribution to the DP literature.

2) Inadequate privacy guarantee: In the literature, it is recommended that the privacy parameter be a constant. But instead it is $(1/p\cdot \ln\rho_p)$ which might provide no privacy at all for small $p$. [mostly addressed]

3) Experimental Evaluation: the experiments are rather sparse; also the "real-world" dataset is not specified. Where is it from? [addressed]

4) There might be some typos in the proofs. Also one calculation (Theorem 5) isn't fully specified. [now addressed]
review_title: null

Meta-review: The reviewers agreed that this is a technically novel and interesting paper with results for a very natural problem and all voted for acceptance. The paper gives more evidence for the wide-ranging compatibility between the goals of sketching and of privacy.
Decision: Accept (Poster)