Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of private data analysis in the adaptive/streaming setting. More specifically, the authors provide a matrix factorization based method in this setting and apply it to SGD. The proposed method seems to be novel, and the empirical results look promising.
strengths_and_weaknesses: Strengths:
1. The proposed matrix factorization based method seems novel and can recover many existing methods for SGD.
2. The authors provide an efficient algorithm to estimate the optimal factorization.

Weaknesses:
1. It is unclear how the general factorization will affect the privacy and utility trade-off when applying it to SGD.
2. The method seems to be limited in the case that only one data pass.
3. The extension of the current method to the FedAvg in the experiments is unclear.
questions: The proposed method is novel, and I have the following concerns about the current paper:
1. How the different factorizations will affect the privacy and utility trade-off?
2. How the different factorizations will affect the convergence of SGD?
3. Whether the method can be extended to the case with multiple data passes?
4. In the experiments, how do you apply your method to FedAvg? Do you run several local steps and communicate the parameters, or do you just communicate the gradients? Do you only use one pass of the data? What is the number of communications of different methods?
limitations: Yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The work analyzes the matrix mechanism in the adaptive streaming setting that Gaussian noise addition mechanism can be private in the adaptive streaming setting and designs a parameter-free ﬁxed-point algorithm to compute optimal factorizations for summation-style problems. Furthermore, the work provides user-level privacy experiment to see the improvement via the approach.

strengths_and_weaknesses: 1. Adaptive privacy analysis is essential and inevitable while most works on continual release analyzed privacy only in a nonadaptive setting.
2. Theoretical results are solid to demonstrate efficiency and convergence of the proposed algorithm on the matrix mechanism, and DP in the adaptive streaming settings.

questions: I have no questions on the paper
limitations: The paper is well writing but not easy to understand, since the structure of it is not very clear.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This work studies matrix mechanism which guarantees differential privacy over adaptive streams. The authors prove that Gaussian mechanism and $(\epsilon, 0)$-DP mechanisms that are private for non-adaptive inputs are also private for adaptive inputs. The authors further characterize the expression for optimal matrix factorization. Based on the theoretical intuitions, the authors design a matrix mechanism for SGD which has superior performance than previous algorithms.
strengths_and_weaknesses: Strengths
- Designing private algorithms for adaptive streaming is an important problem in differential privacy. The authors prove fundamental theoretical results for the matrix mechanism that lead to a practical algorithm for SGD which empirically outperform existing methods.
- The paper is well structured and clearly written.

Weakness
- Some algorithms do not have formal theoretical guarantee.
  - Convergence guarantee for the fixed-point optimization algorithm used in experiments.
  - Effect of a sub-optimal matrix factorization on algorithm performance.
  - Convergence rate for DP Factorization for SGD (Algorithm 1)
questions: Questions 
- For the fixed-point algorithm, what's the rough convergence rate, and what's the main difficulty in proving a formal convergence guarantee?
- How would a sub-optimal matrix factorization affect algorithm performance? For example, if $\phi$ is some distance $\Delta$ away from the true optimum, is it possible to characterize the performance degredation?
- Is it possible to prove convergence for SGD with matrix factorization on say, convex and strongly convex loss functions?

Typos
- Second to last line in Figure 1 caption: mechaism -> mechanism
limitations:  Limitations and potential negative societal impact are adequately addressed.
review_title: null

Meta-review: metareview: The paper applies the idea of matrix mechanism to the problem of DP learning which releases sequences of adaptively chosen gradients. This can be viewed as a generalization (and refinement) of the DP-FTRL approach. The approach is interesting and the empirical results are stronger than existing alternatives such as DP-SGD and DP-FTRL.

The idea is similar to a recent work [FHU22] https://arxiv.org/abs/2202.11205 on the problem of continual release of counting queries, but the authors have claimed independence and carefully explained the differences.

All reviewers are supporting acceptance and so do I.
confidence: Certain
Decision: Accept