Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper considers the problem of differentially privately learning deep neural networks. In order to improve the accuracy and reduce the communication cost, this paper proposes to randomly freeze a progressively increasing subset of parameters, which results in sparse gradient updates. Empirical results also show that the new algorithm can largely reduce the communication cost, while maintaining the performance. Furthermore, the extra computation cost is negligible.
main_review: I think this paper has made the following contributions:
1. This paper proposes a new algorithm of differentially privately training neural networks, which randomly freezes a progressively increasing subset of parameters. This light-weight algorithm can be easily implemented, which dramatically reduces the communication cost while maintaining the accuracy. The idea of gradual cooling and inversely proportional scaling rule are also very interesting.
2. The paper justifies its statement with detailed experiments.

I think the paper can be improved in the following ways:
1. First, the idea of the random freezing is not complex. Therefore, I am not sure how much algorithmic contribution it has made. Besides, this idea is not fully novel, at least it has appeared in other papers. For example, in this paper (https://arxiv.org/pdf/2103.01294.pdf), I remember they also used some similar approach in the experiment section.
2. Personally I am very curious about the performance comparison between random freeze and ranked freeze, which is not provided in this paper. The paper justifies why they do not adopt the ranked freeze in section 2.3, which I do not fully follow. I do not think it is enough to just show they have a similar histogram. Consider the following example, in each iteration, each coordinate is 1 with prob 0.5; else 0. Note that the random freeze and ranked freeze with constant gamma = 0.5 give you exactly the same histogram. However, there is much more information left in the ranked freeze.
3. Some related work is missing, at least the paper I just mentioned, and this paper (https://scholar.google.com/citations?view_op=view_citation&hl=en&user=m8NUgw0AAAAJ&sortby=pubdate&citation_for_view=m8NUgw0AAAAJ:u_35RYKgDlwC).


summary_of_the_review: Overall, I think it is a borderline paper. So I am fine with either accepting or rejecting this paper.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper aims to improve the effectiveness of deep learning under differential privacy. It proposes a simple dimension reduction method that could potentially improve model accuracy as well as mitigate the computational and memory overhead of some previous power method. 
main_review: This paper proposes a dimension reduction technique for private machine learning called random freeze. The basic idea is to randomly select a subset of model parameters and zero out corresponding gradients during the training process. Another contribution is a method to counter the residual effect of added noise when momentum is used for gradient updates.

Strength: 
+ The problem the paper aims to address is an important one. Machine learning with differential privacy is a very active research area, and this paper is a valuable addition to the literature in this field.

+ The proposed method is simple to understand and implement. It is also general and applicable to all types of neural networks. If proven effective, it could be adopted into many existing frameworks to improve the utility private machine learning.

Weakness:
- The experiments do not sufficiently demonstrate the benefits of the proposed method. As a dimension reduction technique, random freeze could be compared with other similar techniques (e.g., [1]) for private learning in terms of utility. Among the four models used in the experiments, only one (GEP) is a belongs to this category, and random freeze shows a drop in utility (from 73.5 to 73.4, third row of table 1). As such, it is unclear if random freeze can be used in place of, or together with other dimension reduction techniques. 

- The proposed scaling of gradient clipping bound is not convincing. The paper argues that, because of the use of momentum in gradient updates, the noise added in previous iterations has residual effects in later iterations. Therefore, the noise scale needs to be adjusted to counter this effect. In the paper, the way to adjust the noise is to use a single constant to scale all noises, and this constant is inverse to the cumulative effect when the number of iterations go to infinity. However, this method for adjusting the noise does not make sense to me. For example, the noise added in the first iteration of training would have much more cumulative effect than the noised added in the final interaction. Also, due to random freeze, fewer and fewer (and different) parameters are receiving updates as the training progress. Thus, while the concern raised by the paper is a valid one, I am not sure the proposed method is the right solution.

- The paper claims (in Section 1.2, Our Contribution) that the proposed method “reduce the computational cost and memory footprint induced by the power method”. However, this claim is neither theoretically analyzed nor empirically demonstrated using experiments.

- Discussion on related work is missing.


Typos:
Page 8 footnote: “There exist too ways…”-> “There exist two ways…”
Page 9 last paragraph: “It is interested to observe…” -> “It is interesting to observe…”

References:
[1] LoRA: Low-Rank Adaptations of Large Language Models.

summary_of_the_review: This paper has two core contributions: a dimension reduction technique (random freeze) and a method to scale gradient clipping norm. However, as mentioned in the discussion on weakness, this paper does not sufficiently demonstrate the benefits of the proposed methods. Therefore, it does not meet the standard for publication at a top conference like ICLR in my opinion.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work introduces the idea of randomly pruning gradients in order to reduce the dimensionality, which, in turn, results in greater efficiency for DP-SGD. The work provides an empirical analysis to support the method.
main_review: Strengths:
The method boasts empirical success 
Paper is well-written 

Weakness:
The proposed method, although reasonable, seems rather ad hoc. Thus, without a guiding first-principles motivation for the method, one should wonder how generally the method works and why it works.
The paper does not do a sufficiently thorough job at the systems considerations of the work.

summary_of_the_review: Overall, this method seems purely heuristic. Without a theoretical or first-principles explanation, this paper relies mostly on an empirical analysis. Theorem 1 is included, but the Gaussian assumption for SGD is extremely limiting and deviates from the accepted standards of analysis for SGD, which generally assume unbiased estimates with bounded variance, but not Gaussian shape in particular. Furthermore, the connection between Theorem 1 and the proposed method of random freezing does not seem that solid.

For the systems analysis, the authors do not report two key quantities: (1) the memory consumption (in bytes) of the method and (2) the runtime of the method. For (1), sparse representations must generally pay a memory overhead because an index is also required. A sparsity % of X% does not imply X% of the memory used. For (2), it seems that although a sparse representation can reduce memory, I am not sure how the runtime of the sparse gradient computations might also be affected here in the DP-SGD. It is important to also benchmark and report this, or at least mention that the runtime is not significantly affected if that is the case.

To summarize, the work is neither a complete systems analysis nor provides a sufficient fundamental analysis. I feel that at least one of these two aspects should be present.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes to use sparse gradients in combination with differential privacy techniques in order to mitigate performance drop that comes from applying DP to a large number of parameters. 
main_review: Strengths: 
- A relevant problem is addressed in this work. 
- The idea is simple but interesting and shows potential. 

Weaknesses:
- The appendix proves a result for the MSE, but there is no insight or discussion into how this result would look for the proposed method.
- The "curse of dimentionality" is not explored in detail (i.e. performance of the method for different numbers of parameters). Relatedly, the conclusion mentions "... random freeze can reduce the computational cost and memory footprint of the power method in GEP" but this is not explored in much detail in the results. 
- While the inversely proportional scaling rule is mentioned, more results would be beneficial about the choices of hyperparameters and also how robust the method is to certain parameter choices. Similarly: how many gradients can we drop before we start losing accuracy? 
- In the results in Table 1 the proposed method does not improve on the accuracy and a significant accuracy improvement is also only shown for one model. It thus remains unclear if a higher DP-guarantee be obtained with higher/similar accuracy. Test accuracy as a function of privacy loss would be interesting to see. 

Comments: 
- A very minor comment: I am not sure I understand the positioning of section 2.5; if you see it as numerical, better to have it in the numerical section; if it is part of the discussion then let it be in the discussion. 
summary_of_the_review: Interesting idea but numerical experiments are not yet fully convincing and a lack of theory and discussion
review_title: null

Meta-review: This paper provides a new differentially private training method. The key idea is sparse gradient updates---that is, their variant of differentially private SGD (DP-SGD) only updates on a random subset of the parameters in each iteration. The authors argued that their method has a benefit in terms of memory and communication efficiency. The reviews suggested that the paper may require further evidence to motivate and justify the novelty of the proposed method. First, the reviewers are not fully convinced that the proposed method reduced both memory and communication. In particular, would the technique of random freeze require running DP-SGD for more iterations? Even though the authors added a new theoretical result (mostly adapted from Chen et al.), the newly added Theorem 2 does not explain the benefits of the freezing technique. Thus, the paper can benefit from more extensive theoretical analyses or justification. The authors should also consider including the additional related work brought up by the reviewers. In summary, the paper is not ready for publication at ICLR.
Decision: Reject