Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper studies the problem of privately releasing prefix sums in the adaptive continual release model via matrix factorization techniques. Their main results are 1.extension of prior work which was limited to single participation to general participation patterns and 2. a more efficient method based on fast Fourier transform. The authors conduct extensive experiments which show promising results over prior approaches.

strength_and_weaknesses: Strengths

1. The prefix-sum view of SGD and using matrix factorization techniques to privately release these have been instrumental in improving the utility in private machine learning tasks, especially in large-scale practical settings. Therefore, the problem that the authors study is important and the improvements can have immediate real-world impact in how private machine learning models are being trained.

2. The paper is mostly written-well; it gradually formulates the problem, and builds towards the key ideas and proposed approach. 

3. The experimental results showcase improvement over prior approaches; for example they get a 5\% improvement over DP-SGD with privacy amplification with sub-sampling.

Weakness

1.  The section on FFT seems half baked and not so related with the overall picture. The main goal in the paper to demonstrate empirical improvement but it seems to be that empirical results presented in the main text don't even use this method; correct me if wrong.


2. $(k,b)$ participation - I did not fully understand the choice and use of assumption that a point participates once every $b$ iterations. It seems to me that it is only used to argue that $|\Pi|=b$; in that case, why not simply explicitly assume this? If not, where is the additional structure useful?

3. At parts, I felt that some details are missing in order to completely understand the arguments, or the authors expect the reader to be familiar with Denisov et al. (2022). For example, in Corollary 3.1, the optimal dual solution computed, but how to get the primal solution from here? It also is the case with some experimental details (see below). It would be helpful if the authors can make the content more self-sufficient.

4. Experiments: I do not understand the description of algorithms MF1,6e and MF6,6e; for MF1,6e the authors say that they use Theorem 2.1 to use "the single participation optimized matrix", but Theorem 2.1 is about reducing $d$ dimensional instances to scalar instances; what am I missing here? About MF6,6e, it says, is "our approach .." -- which theorem/procedure description should I be looking at for this?
clarity,_quality,_novelty_and_reproducibility: The paper is mostly-well written but some parts have missing important details or are relegated to prior works. The extension from single participation does not seem particularly challenging and quality mainly hinges on observed empirical improvements. 
summary_of_the_review: I think the topic of the paper is timely and the authors make interesting contributions with promising empirical results. The downsides are missing/unclear details as well as lack of coherence among parts of the paper, like the one based on FFT.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel differentially private mechanism with multiple participations. Specifically, the author simplify per-iteration
vector contributions problem by using a sensitivity computing framework and rigorous proof is given. Under the problem reduction, a convex program for the construction of optimal matrix mechanisms is proposed, and a closed form solution for it is also provided. To further reduce computational consumption, a Fourier-transform-based mechanism is designed. In experimental part, full comparisons with prior matrix mechanism approaches and DPSGD demonstrates the effectiveness of the proposed method.

strength_and_weaknesses: a)  This paper emphasises their contributions/novelties on existing differentially private(DP) mechanisms. The extension is reasoned and the solution method is proved, and the effectiveness of method is proved by extensive experiments on example-level DP and user-level DP.

b)  Author applies differentially private (DP) mechanisms with matrix factorization to gradient-based machine learning, and promot the achievable privacy-utility-computation tradeoffs.

c)  The formula proof of paper is rigorous and orderly, and the diagram of the experiment is also very intuitive.

d)  In section 4,the time complexity is analyzed theoretically. Could the authors report the running time of the proposed algorithm in the experiment? In this way, we can intuitively justify that Discrete Fourier Transform helps reduce computation.

e)  The transition from the background to the formula should be elaborated in more detail so that readers can understand more quickly.

f)  In the conclusions part, the following can be added. For example, weaknesses of work and future work discussion.

clarity,_quality,_novelty_and_reproducibility: The article is well-organized and easy to follow, and the experimental results are also intuitive and clear.

The method proposed in this paper is relatively novel, especially the extension of the online matrix factorization DP mechanism to multiple participations and a Fourier-transform-based optimization.

There are little sentences with grammatical errors. 

summary_of_the_review: See "Strength And Weaknesses"
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper provides new differentially private (DP) mechanisms for gradient-based machine learning training that involves multiple epochs of a dataset, and improves on the prior results. The algorithms are based on extensions of the matrix factorisation DP mechanism for different settings, such as user-level DP and multiple epoch regime. As listed in the introductions, there are four main contributions of this paper.
1. It provides a new framework for analysing the sensitivity of the matrix mechanisms under a certain user-level DP setting. This involves proving a new theorem for high-dimensional contributions based on an extension of the Birkhoff-von Neumann theorem, allowing to reduce to a scalar problem, instead.
2. It extends the results of Denisov' 22 to the optimisation problems corresponding to generalised notions of sensitivity.
3. It also gives a computationally-efficient factorisation mechanism that is based on the Fourier transform, that it claims is near-optimal for the single-pass setting, and could be extended to multiple epochs.
4. It also provides empirical evaluations and comparisons of their algorithms with prior matrix mechanism and DP-SGD, and claims to outperform these methods.
strength_and_weaknesses: Strengths:
1. The analyses of the sensitivity of the matrix mechanisms looks quite interesting and involved to me. I like the idea of incorporating these generalised cases of multiple contributions by a single user (user-level DP) because that is a much more real-world case.
2. The reduction to the scalar case also looks cute! It appears to give a cleaner way of visualising what the sensitivity could be, and anticipating the amount of noise that would be needed for privacy.

Weaknesses:
1. My first complaint is not too severe, but it is about the writing of this paper. I think the writing looks a bit rushed and doesn't really give the best intuition of what or why something could be expected, or in other words, there are places where the technical discussion is not necessarily supported by enough "English text".I see that happening in Sections 3 and 4, mainly. It is a little hard to see in the theorems what certain expressions mean and what they entail. In Section 5, there isn't any such issue, but Figure 2 that lies on page 8, is decoded and explained at the end of page 9, which is a bit confusing and distracting.
2. I'm not completely convinced by the empirical results in the main body of this paper. Here's my issue. The optimal (but possibly computationally-inefficient) algorithm seems to work really well compared to all other prior work and this paper's FFT-based mechanism, but it is not really practical when $n$ is large because of its high runtime. I think the point of the authors here might be to show the promise of their new generalisation, but right now, it is not exactly useful in practice.
3. The more concerning issue for me is that the practical analogue (that is based on FFT) of their mechanism is not super accurate. In Figure 1, it doesn't look that impressive even for the more useful values of $\varepsilon$ ($\leq 10$). It seems to be quite close to the Kairouz'21 algorithm, except when $\varepsilon$ is between $5$ and $7$. The optimal (but slower) algorithms does notably better in this regime though, but that doesn't seem impressive because that algorithm is not really practical in real-world applications. For the multiple epoch setting, it doesn't seem that useful either. Therefore, if this is one if the highlights of this paper, I'm a bit disappointed, to be honest.
4. I don't understand why the authors chose to compare in regimes where $\varepsilon$ is more than $10$ or too high to provide any useful privacy guarantee. We do expect most non-trivial DP algorithms to become accurate in that range anyway, so what is the point exactly?
5. I wish the authors had plots in the paper comparing their FFT-based approach more with other prior work. I know they have plots in the appendix, but they're hard to read because the plots for the prior work are separate from those for this paper's algorithm.
6. I understand that the focus of this work is mainly towards practical DP ML via tools like privatised versions of SGD, but I wish that there were more about other applications, as well. Maybe, that would have asked for a separate paper, so I'm not *that* concerned about this. Would appreciate the authors' input on this though.
clarity,_quality,_novelty_and_reproducibility: Regarding the clarity, I have provided a couple of pointers on improving the presentation of this paper, but the rest of it seems alright to follow.

The results are novel in the sense that prior work was generalised here with new analyses and that a computationally-efficient analogue was provided for the same. That said, I do have concerns about the quality, which I have explained in the previous section.
summary_of_the_review: For me, the weaknesses outweigh the strengths a bit here. I am open to changing my evaluation later, but for now, I think a few improvements could help with the quality of this work.

Update: based on the responses, I have bumped the score.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors provide new differentially private (DP) mechanisms for gradient-based machine learning (ML) training involving multiple passes (epochs) of a dataset, substantially improving the achievable privacy-utility-computation tradeoff. They propose a framework for computing the sensitivity of matrix mechanisms under general participation patterns. They extend the results of Denisov et al. (2022) to the optimization problems corresponding to these generalized notions of sensitivity. They propose and analyze a computationally-efficient factorization based on the Fourier transform.


strength_and_weaknesses: Strength:
The authors prove a new theorem bounding sensitivity for multi-dimensional data contributions based on an extension of the Birkhoff-von Neumann theorem. It allows to reduce the problem to that of measuring sensitivity for scalar contributions alone. 

They show that the algorithms proposed in Denisov et al. (2022) can be extended in present setting. 

To reduce the cost, they propose and investigate an approach based on the Fast Fourier which is near optimal for the single-pass setting and can be efficiently extended to handle multiple passes.

Weakness:
The techniques applied in the present paper based on the methods in Denisov et al. (2022). The authors extend it to the multi-dimensional and multi-participation setting. I think the novelty of the paper is less. 



clarity,_quality,_novelty_and_reproducibility: I think the main part of the paper is clear. But I think the novelty is less and it seems there are not so many technical approaches.
summary_of_the_review: In this paper, the authors introduce DP mechanisms for gradient-based machine learning training involving multiple passes of a dataset, substantially improving the achievable privacy-utility-computation tradeoffs. The key contribution is an extension of the online matrix factorization DP mechanism to multiple participations. I think the novelty of the paper is little, however they significantly improves the privacy-utility tradeoffs while maintaining practically feasible computation costs.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The reviewers appreciated the changes in the revision the authors made. However, it was thought by several reviewers that the changes in the revision were quite major and substantial, in particular, major rewrites of sections, additional conditions in Corollary 2.1 and new sensitivity analysis, and it was thought that the paper would benefit from a new round of reviewing given such changes. If evaluated prior to the technical changes, the enthusiasm was a bit weaker. 
justification_for_why_not_higher_score: I think the paper was borderline after the major changes in the manuscript, and slightly below borderline beforehand. The reviewers thought the changes were quite substantial and didn't think basing the review on the quite new version of the manuscript would be fair, and thought instead that the paper would benefit from an extra round of reviewing.
Decision: Reject