Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper claims that sufficient statistics can be generated from which a wide range f norm estimations can be differentially privately computed.
strength_and_weaknesses: Intuitively, the idea sounds very plausible to me, but the text is insufficiently rigorous for me to be able to follow the proof.
clarity,_quality,_novelty_and_reproducibility: On page 1, please define more precisely “maximum modulus of concentration”.  The current definition refers to a median without saying from which set the median should be taken.

While in the beginning of Sec 1 x is called a vector, early in Sec 2 it is called a frequency vector (without clear definition for these frequencies).  The text next immediately starts discussing level sets without defining what level sets are being considered.

Section nicely defines classic notations such as [n] but then again is vague about “frequency vector x over a data stream”.  I suggest to give in one or two lines the structure of and notation for the data stream and the definition of x in terms of it (and possibly time parameters if the frequency only covers a certain time window).

Does the AMS algorithm choose \sigma uniformly at random?

In def 3.1, specify H\subseteq [n] 
In def 3.1 (3), just setting \hat x_k = x_k seems to meet the requirement, nothing seems to say exact equality is not allowed.
In fact, def 3.1 seems to be more an algorithm than a definition.

Later, it becomes more and more difficult to follow the text as i get more and more uncertain about the definition of all concepts used.



summary_of_the_review: The paper suggests a nice idea for which probably a proof exists, but the elaboration is insufficiently rigorous.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies preserving differential privacy in when releasing information of streaming models. The authors propose a new DP mechanism that can release a set of sufficient statistics which can be used to estimate any symmetric norm of the data. 
strength_and_weaknesses: This paper studies a very important problem, i.e., releasing the norms of data while protecting the differential privacy in streaming cases. Previous work many focus on limited settings (i.e., p<1), while this paper proposes a universal mechanism which works for any symmetric norms with low space complexity. This idea for coordinate parathion to my knowledge is novel and very interesting. 

I have a hard time reading this paper. I think the following advices may be helpful:

1.	A more clear and detailed definition of the streaming model. Currently, it is not very clear to the readers what the exact streaming model is. The authors only mentioned the model with one sentence (“The simplest streaming model is perhaps the insertion-only model,…”). Is this the only model the authors study, or the model can be more general? 

2.	The preliminary should be put before Section 2, since many definitions of Section 3 are used in Section 2. 

3.	It would be great if the authors can add a related work section to compare with other work (especially smith et al., 2020, wang et al., 2021, blocki et al., 2012) and illustrate the differences. 

4.	“We emphasize that prior to our work, there is no algorithm that can handle private symmetric norm estimation”I am not sure if it is an overclaim, since previous can handle the cases when p<1.

clarity,_quality,_novelty_and_reproducibility: See above. 
summary_of_the_review: I think this paper is novel and the results are significant. But the writing can be improved.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a general algorithmic framework for differentially privately releasing a number of sufficient statistics on a data stream. With the released statistics, all symmetric norms can be approximated simultaneously, which makes the algorithm especially suitable for a large number of queries.
strength_and_weaknesses: I found the idea of classifying and separately handling high, medium and low frequency levels novel and interesting. It makes sense to release approximate frequencies for the high frequency levels while release approximate level sizes for the light frequency levels for better utility. The theoretical analysis for the accuracy and privacy guarantee looks sound to me.
clarity,_quality,_novelty_and_reproducibility: Yes 
summary_of_the_review:  
I found the idea of classifying and separately handling high, medium and low frequency levels novel and interesting. It makes sense to release approximate frequencies for the high frequency levels while release approximate level sizes for the light frequency levels for better utility. The theoretical analysis for the accuracy and privacy guarantee looks sound to me.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposed a framework to release the family of symmetric norms with differential privacy. The mechanism permits (1+\alpha)-approximation to each norm.
strength_and_weaknesses: Strength: 
The targeted problem is interesting. This paper provides many theoretical results.

Weakness:
1. In general, the manuscript is not very well written. I noticed a lot of typographical and grammatical errors that made reading and understanding the manuscript a bit difficult. This paper is not easy to follow. There are many technical phrases that lack sufficient explanations.
2. No exact definition of (1+\alpha)-approximation in the main manuscript.
3. It would be better to provide PRICOUNTSKETCH instead of the sketching algorithms in Section 3.
4. The level thresholds T_1 and T_2 to separate the data is important. Algorithm 1 gives some theoretical order of the thresholds. However, how to choose them numerically?
5. There is no experimental evaluation of the proposed algorithms in this paper.
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is somewhat clear, but some important details are missing or unclear.

Quality: The paper has minor technical flaws. For example, the experimental evaluation is weak.

Novelty: The paper contributes some new ideas or represents incremental advances.
summary_of_the_review: This paper proposed a framework to release the family of symmetric norms with differential privacy.  However, some important details are missing or unclear.  I may have missed some crucial details.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Paper proposes a novel mechanism to release symmetric norms in a differential private manner. Authors propose an interesting idea to separately handle high "frequency"  and low "frequency" dimensions. Former dimensions are approximately revealed while latter dimensions are revealed through level sizes. This way the proposed algorithm is able to release sufficient statistics for all Lp norms at one go. Unfortunately the paper is very hard to read. For example, notations are used before defining (e.g. mmc) and some of the vaguely defined terms may not be standard or familiar to ICLR community (e.g. "frequency vector"). In the response to reviewers authors claim that
> we state that in the streaming model, the vector x is called a frequency vector when x_i denotes the number of times i has appeared in the stream.

However, this statement wasn't found in the main text. Discussion of related work is absent from main text. Paper might need a re-write to relegate unimportant lemmas/results to appendix to make space for discussion for clarity. I also highly encourage the authors make the main text and supplementary text of the same format in terms of section ordering, numbering and citation style. Current mismatch is very hard to follow. It is also noted the paper does not provide any empirical results and validations.
justification_for_why_not_higher_score: Writing is very hard to follow and might require re-writes. Lack of empirical evaluation.
Decision: Reject