Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes the idea of using delayed preconditioning by an average of gradients. The idea is motivated by the supposed empirical observation that the gradient geometry does not change significantly over a period of time. 
strength_and_weaknesses: The strength of the paper is the novel idea of using preconditioning in this smart way. I like that. 

The main weakness of the paper is the lack of comparison with the prior work. Theorem 2 is almost impossible to interpret. Even the text following the theorem does not help the case. It would be better if the authors provide a corollary that instantiates the theorem with the parameter choice to better explain the result. 

Also, the authors claim that the paper uses adaptive optimization. Does this help them improve the rate of convergence? What effect does it have on the utility guarantee? None of this is clearly spelled out. Of course, they cannot beat the lower bound due to BST14, so what is the best utility they achieve? A proper table comparing the result in this paper in context with previous works should be given. Also, what is the SCO rate? Does their algorithm also permits a nice generalization bound? Does the algorithm have to tune the staleness parameter and the temporal gradient similarity? None of these are clear in the paper.

I haven't checked the proof thoroughly due to limited time. However, the proofs I tried to verify are written in a very difficult-to-parse manner. I will reserve my final score after the discussion with the authors and when I get to read the proofs in more details. 

I did not spend a lot of time going through the experiments. IMDB and StackOverflow are difficult to train datasets. The test accuracy for IMDB is really remarkable. I would really like to know more details here. It seems to be beating DP-SGD over all ranges of epsilon for all the datasets.  
clarity,_quality,_novelty_and_reproducibility: There are some novel aspects to the paper. 
The quality of the writing can be significantly improved. 
I did not verify the reproducibility aspect. 
summary_of_the_review: Please see above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new private gradient adaptive descent algorithm for convex and non-convex optimization. The proposed algorithm does a delayed preconditioner update and leverages an average noisy gradient to reduce noise in the preconditioner. The experiments show the proposed algorithm outperforms previous private gradient-based optimization algorithms. 
strength_and_weaknesses: Strength:
1. The proposed approach is well-motivated. It is reasonable to use a delayed preconditioner based on the empirical observation that the preconditioner value distribution is consistent between successive epochs.
2. The experiment is comprehensive. This paper has experimented on multiple datasets, comparing the proposed algorithm with existing private optimizers and very recent private algorithms with public data. This paper also empirically studies privacy/utility trade-offs, and delay parameters.
3. The writing is good. This paper is easy to follow. 


Weakness:
1. The theoretical convergence bound for convex optimization is very hard to interpret. It is unclear to understand the rate of convergence in terms of dependence on iteration time 'T', delay parameter 's' or 'v', and dimension dependence 'd'. It will be good to clarify those dependencies in the bound and compare Theorem 2 with existing bounds which can make the contribution of this paper clear. 
2. There is inconsistency regarding the dependence on noise variance in Theorem 2 and Theorem 3. In the convex case (Theorem 2), the noise variance is scaled by the preconditioner, i.e., \|N^t \|^2_{D^t}, which shows the noise is projected by the preconditioner. But in the non-convex case (Theorem 3), the noise variance is d\sigma^2 as appeared in most existing bounds. In the algorithm, the isotropic noise is added after applying the preconditioner to the gradient, which makes it more sense to have d\sigma^2 in the bound. It will be great if the authors can add some discussions about this.
clarity,_quality,_novelty_and_reproducibility: This paper is easy to follow. The quality and significance can be improved. The experiments could be reproducible with the details provided in this paper. 

summary_of_the_review: Overall, this paper is well written. It proposes an interesting algorithm and has a comprehensive empirical study. But the paper can be improved by clarifying the contribution, improving the theoretical bound presentation, and discussing the theoretical results. I recommend  6: marginally above the acceptance threshold.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Background: DP-SGD gives guarantees for the whole history of gradients. It very difficult to obtain guarantees that would hold only for the final model, so then it is natural to think, how could we use the history of gradients since due to post-processing that will not have any additional privacy cost.

The paper proposes a novel RMSprop type of preconditioner for DP-SGD. There are several key steps to reduce the effect of DP noise in the preconditioner. Commonly the preconditioners are plain non-DP SGD preconditioners applied to the noisy gradients, however this work tailors the RMSprop approach to DP-SGD. 

Important steps include 

-average the preconditioner over noisy gradients. Preconditioner here means vector v with which the gradients are scaled element-wise before clipping. Averaging over the history of gradients reduces the effect of DP noise.
-carry out the preconditioning before clipping, instead of afterwards (when e.g. using naively preconditioners to DP-SGD)
-update the preconditioner only once in a while (for a short window of iterations update the accumulator with which the preconditioned is updated), then carry out preconditioning with the old one.
strength_and_weaknesses: 
Pros:

- This seems like a novel idea and all these ideas seem like a natural thing to do for DP-SGD (averaging, using preconditioning before clipping)
- Very strong experimental results for the proposed method
- The paper is very well written and the convergence analysis seems convincing. For example, for convex problems, it shown that smaller amount of noise is added compared with DP-SGD which leads to faster convergence.

Cons:

- Slight deficit of the convergence analysis: the analysis does not seem to improve over the state-of-the-art results for adaptive DP optimizers for non-convex problems, although the same asymptotics are obtained (as far as I see). This means that the strong experimental results are not reflected in the non-convex analysis.
- I was expecting also some standard DP-SGD comparisons (MNIST, CIFAR10) etc. Could you comment, would the behaviour for this method be then similar?


clarity,_quality,_novelty_and_reproducibility: 
As said the paper is very well written. Here few additional comments:

- How big were the model sizes used in the experiments? Would this have some effect?

- Minor: to me it seems that $G^t$ is a dummy variable between from iterations $s_1$ to $s_1 + s_2$ (mod $s_1 + s_2$). This is cosmetics but perhaps that could be somehow written differently.

- It was for me a bit difficult to grasp how exactly do we benefit from the staleness of the gradients. I.e. we update the accumulator for $s_1$ steps and preconditioner after eevry $s_1 + s_2$ steps. Wouldn't the weighted summing averaging anyhow cancel the effect of DP noise? is there something more at play, that it is actually beneficial to use slightly stale preconditioners?


summary_of_the_review: All in all, I think the results (especially experimental) seem very convincing and the ideas natural, so I recommend acceptance.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper provided a differential private adaptive training with delayed preconditioners to avoid using auxiliary data for private optimization. Some theoretical results and several numerical studies are explored to demonstrate the effectiveness of the proposed method.
strength_and_weaknesses: Strength:
This paper is easy to follow, and the target problem is interesting.

Weakness:
1. Assumption 1 is quite wired. For any iteration t, this should be proved theoretical rather than simply assuming it holds for all $w^{t}$.
2. What is the definition of $\|\|\cdot\|\|_{D^{t}}$?
3. It has been discussed about the trade-offs between delay and noise, which suggest there exists an optimal $\nu$. Could the authors investigate the trade-offs numerically?
clarity,_quality,_novelty_and_reproducibility: This paper has minor technical flaws. The novelty of this paper is limited.
summary_of_the_review: This paper simply added delayed preconditioners in existing differential private algorithms. The contribution seems to be incremental.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes an algorithm for private adaptive optimization that achieves improved privacy/utility tradeoffs without using auxiliary data. The algorithm is based on two main insights: using averaging of the past gradients in order to reduce the effect of the DP noise, and applying the preconditioner before clipping.

The reviewers agree that the two main insights are novel and interesting, and the experimental evaluation is very strong. Overall, the paper makes a good contribution to the area of private optimization that is relevant to the community. 

The reviewers agree that the theoretical guarantees for the non-convex setting are a potential weakness of the paper. The reviewers were also concerned about the clarity of the exposition. The authors revised the paper based on the reviewers' feedback and addressed some of the main concerns. Although the revision is satisfactory, the reviewers encourage the authors to further revise the paper to improve the technical clarity and to make the proof more accessible. 
justification_for_why_not_higher_score: The paper has novel insights and strong experiments, but the theoretical contribution for the non-convex setting is more limited.
justification_for_why_not_lower_score: The contribution is relevant to the community and it may lead to further progress. The experimental evaluation is strong.
Decision: Accept: poster