Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper analyzes convergence of DP-SGD using the NTK framework. The general idea is that the learning dynamics of SGD converge when the NTK matrix is positive-semi-definite.  They  characterize the effect of clipping and noise and Propose global clipping strategy. The global clipping idea consists of eliminating samples that have gradient norm bigger than some threshold and then applies a common clipping multiplier for each sample gradient. The authors claim that global clipping reduces gradient bias. 


Gradient Clipping Summary: DP-SGD consist of the following steps: Over T rounds: 1) the algorithm samples a batch of samples from a dataset I_t. 2) it computes the gradient of each individual samples. 3) Each gradient sample is multiplied by a number such that the final gradient has norm bounded by R. 4) Finally, all clipped gradients are aggregated, noise is added to the average clipped gradient and the result is applied to update the model.

Difference between local and global clipping:  In local clipping, the gradient of each sample is multiplied by a factor specific to that sample such that the gradient  norm  of each sample is bounded by R. In global clipping, there is an additional parameter Z, each sample in a batch with gradient norm smaller than Z are multiplied by a constant factor R/Z and samples with gradient norm bigger than Z are not used. Therefore in global clipping each sample in a batch has gradient norm bounded by R. The intuition behind global clipping is that each gradient in a batch gets multiplied by a constant factor, this means that the direction of the aggregated gradient should be preserve. 


Convergence Analysis: The convergence analysis uses the Neural Tangent Kernel (NTK) framework. The premise is that, the convergence of SGD is controlled by the NTK matrix in that the condition for convergence is that the NTK matrix is positive-semi-definite. The paper provides two main theorems: The first one claims that local clipping cannot guarantee convergence because local clipping can break the conditions for convergence under the NTK framework. The second theorem says that when the parameter Z is large then global clipping can guarantee convergence because each gradient is multiplied by a constant factor and does not affect the positive-semi-definitess of the NTK matrix. 

Experiments: The paper empirically evaluates global clipping on the MNIST and CIFAR10 dataset. They 

main_review: I think that using the NTK framework to analyze the converge of DP-SGD is a very interesting direction. However, the theoretical claims seem not surprising and I question how useful the global clipping strategy is for practical purposes. First, according to theorem 2, the convergence of SGD with global clipping is only guaranteed when we can find a parameter Z big enough such that all sample gradients have norm less than Z. However, it is not possible to choose such a Z in advance before running the algorithm, therefore theorem 2 it’s not very informative for the practical algorithm (i.e., what should we set Z too?). In practice, Z is a hyperparamter that needs to be tune before running the algorithm since, according to figure 3 (rightmost plot), the choice of Z has a big influence in the final model accuracy. By using the original local clipping strategy, one does not need to worry about finding an optimal Z, thus one could claim local clipping is more practical. 

On the empirical evaluation results are also unsatisfactory in my view. Somehow, using global clipping results in lower test loss that using local clipping but local clipping seems to give better accuracy, this phenomenon is not explained in the paper. Specially in the hard CIFAR10 setting, using global clipping does not seem to make a big difference. Furthermore, running global clipping requires knowledge of the Z parameter but that’s not required for local clipping. Therefore, I’m not convince that I should use global clipping vs local clipping for practical applications. 



Questions:
- The paper makes then case that global clipping reduces the clipping bias that occurs with local clipping. However when Z is small, removing samples from the batch can also creating a bias. How can we compare then bias of both methods and can one create an example where global clipping would change the gradient direction more than (or add more bias) local clipping would?

- I don’t understand what figure 1 is trying to convey. My understanding is that the figure is comparing the average clipped gradient with global and local clipping. However it would be good to compare against some baseline. For example, we could compare against  the gradient of the average gradient without clipping. 





Other comments: 
I was confused by definition 4.3. Is the definition 4.3 equivalent to positive-semi-definite matrix?
summary_of_the_review: The paper has a very interesting theme but I find the analysis and conclusion unsatisfactory. Furthermore, the empirical evaluation is not more convincing.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper analysis differentially private (DP) optimization convergence in neural networks by examining the neural tangent kernel (NTK). In particular, the papers analysis focuses on DP optimization which utilize gradient clipping and the Gaussian mechanism for gradient updates. Through the analysis of the NTK, an alternative clipping operation is proposed which has guarantees for convergence of the loss function. In addition, this alternative clipping operation provides a DP guarantee. Experiments in the paper then verify that the proposed clipping performs well in practice.
main_review: Strengths:
  - The proposed global clipping is very simple and intuitive to implement.
  - The (lack-of) effects of Gaussian noise on the gradient flow is a very neat fact.
  - The analysis of the proposed global clipping is analysed in various settings (with even more details in the appendix).
  - Experiments are very promising.

Weaknesses:
  - Claims on convergence rely heavily on the NTK matrix being positive-definite. However, is this the case in practice? I know that the Fisher information matrix has mostly close to zero eigenvalues (e.g. "Universal Statistics of Fisher Information in
Deep Neural Networks: Mean Field Approach 2019"), but are there similar characterizations of the spectrum for NTK?
  - Similarly to the above, does the positive-definiteness hold in practice?
  - Theorem 2 relies on the global maximum norm bound $ Z $ for the batch gradients. How often does this happen in practice?
  - The claim of Theorem 3 seems to be worded quite strongly. My initial interpretation of it was that local clipping is $(\varepsilon, \delta)$-DP iff global clipping is $(\varepsilon, \delta)$-DP. However, I don't believe this is the case given the proof.

Other / Minor:
  - Inconsistent use of oxford comma (abstract + intro versus rest of paper).
  - For Figure 1, it would help to emphasis the global clipping by making the grey circle smaller.
  - Algorithm 2 mentioned in main text needs a pointer to appendix.
  - It would be worth stating that you are looking at fair loss function where no loss is incurred for perfect prediction (e.g. "Information, Divergence and Risk for Binary Experiments 2011"). Especially so since this is key to the proof of Theorem 1 statement 4.
  - A few typos in the appendix:
       - Proof of Theorem 2 statement 1: at $ x^{T} x \mathbf{H} x $;
       - "citep" above Lemma B.1;
       - Lemma B.1 "supreme" -> "supremum".
  - Top of Section 4 "yet and our" -> "yet our".
summary_of_the_review: Overall I would recommend an accept. The simplicity of the approach and the improvements shown in the experiments show that the global clipping has promise. However, there are a couple of aspects in the paper which need to be addressed. In particular, I believe that the text of Theorem 3 is worded too strongly.

---

Edit: I have changed my score from 6 -> 5 as a result of reviewer discussion. In particular, due to how the assumptions of Theorems 1 & 2 are not the same due to the assumption on the gradient norm bounds. Further discussion / analysis is needed for the violation or removal of this particular assumption (following the critics presented in LL2P and b1Rw's reviews).
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies the problem of understanding the convergence of differentially private deep learning models. The most common technique to ensure differential privacy (DP) in deep learning is to adapt the SGD algorithm by clipping the gradient at each learning step before perturbing it with Gaussian noise. The present work proposes to study the impact the clipping step and the noise injection can have on the convergence of the algorithm. In doing so, the authors claim to make several contributions summarized below.

1. Provide a characterization of the training dynamics of differentially private gradient descent methods through the lens of gradient flow theory, using neural tangent matrices (NTK).  The authors claim that this framework enables a fine-grained analysis of the impact of clipping and noise injection on the convergence of deep learning algorithms. 
2. Develop a new clipping method called "global clipping" that improves convergence and mitigates the lack of calibration of differential private gradient descent methods. Moreover, this new approach does not change the DP guarantees of the gradient descent algorithm, is easy to implement and is as computationally efficient as the previous clipping methods (called "local clipping" in the paper). 

main_review: ### ***Overall merit of the paper.***

The problem of better understanding the properties of differentially private optimizers is an important topic within the ML community, as it would allow building more robust techniques with provable convergence guarantees. Moreover, the possibility of analyzing the dynamics using the continuous gradient flow seems to be an interesting idea, especially if it allows the introduction of new clipping methods improving the convergence of the algorithms. 

### ***Concerns and remarks to authors.***

My main concerns with this work are the technical quality and relevance of the contributions. I detail below the most important ones I have. 

**Relevance of studying GD instead of SGD.** At first glance, it seems that the authors are studying the well-known DP-SGD procedures and trying to improve the existing knowledge of this widely used algorithm. In fact, this is the method that is presented in Algorithm 1 and that is being used in most of the experiments (Sections 6.1, 6.2, 6.3). However, the theoretical contribution only studies full gradient descent, which is much less relevant in the context of deep learning because it is never used in practice due to its computational complexity. As a result, I think the authors overstate their contribution by stating that they provide a "convergence theory for deep learning DP". I think their analysis is more applicable to simple classification or regression tasks with small datasets. 

**Regarding the NTK framework.** The idea of studying the convergence dynamics of differentially private deep learning through the lens of gradient flow seems like a good idea, but I am not sure the authors properly used and analyzed existing tools from control theory. Here are some of my comments below. 

1. To build their whole theoretical framework, the authors explain that the derivative of the loss function is characterized by $\dot{L} = \frac{\partial L}{\partial f} HC \frac{\partial L}{\partial f}^{T}$. Then, they introduce a set of new concepts extending the notion of matrix positivity to non-symmetric matrices (Definition 4.3), to analyze HC (because it might not be symmetric). However, from my understanding of the literature, it is not relevant to study HC directly. In fact, we can always rewrite the derivative of the loss function as $\dot{L} = 1/2 \frac{\partial L}{\partial f} (HC + (HC)^T) \frac{\partial L}{\partial f}^{T}$. Therefore, the analysis of $(HC + (HC)^T)$ is sufficient to characterize $\dot{L}$ and does not require the introduction of new concepts since $(HC + (HC)^T)$ is indeed symmetric. 
2. It is unclear to me how certainty equivalence can be applied to provide a proof for Fact 4.1. I think that certainty equivalence is related to the fact that the optimal control is the same; that is, the system with zero-mean additive noise has the same optimal control law as the system without noise. But, as I understand it, equivalence of optimal control laws does not mean equivalence of dynamics. Moreover, certainty equivalence does not hold true when the dynamical system is nonlinear, which is indeed the case here.

**Unfair comparison between global and local clipping.** The paper presents a new method of clipping called global clipping and compares it to local clipping (previous method) both theoretically and empirically.  I have some concerns on both sides, explained below.

1. From a theoretical point of view, the authors claim that global clipping offers better convergence guarantees than local clipping. To justify this claim, they present two theorems stating that local clipping can have a bad impact on convergence (Theorem 1) while global clipping does not (Theorem 2). However, the comparison does not seem fair to me. Indeed, in order to show that global clipping does not have a bad impact on convergence, the authors make the additional assumption that $Z$ (one of the clipping parameters) is large enough so that no vector is dropped during the procedure.  In fact, this assumption is equivalent to saying that there exists a real number $M < \infty$ such that for all $i$ and $t$, $\Vert v_t^{(i)} \Vert \leq M$. In this particular case, taking $Z \geq M$, the global clipping amounts to rescaling each gradient with a fixed constant; therefore, it does not hinder the convergence (it is actually equivalent to changing the learning rate). As the authors point out in Footnote 5, this assumption is central to the proof of Theorem 2 and cannot be relaxed. But if we were to assume the existence of such an upper bound $M$ on the gradients in Theorem 1 as well, then we could also show that local clipping does not impede the learning procedure simply by taking $R \geq M$. As a result, the paper does not present a fair comparison of the two clipping methods, and as I understand the results at this point, there is no way to argue that global clipping is better than local clipping from a theoretical viewpoint.
2. From an empirical standpoint, while I agree that global clipping seems to help in classifier calibration, I do not think it can be considered to have similar performance as local clipping. Looking at the experimental results (e.g., Figures 3 and 5), it appears that DP-SGD with global clipping generally takes longer to converge than DP-SGD with local clipping. While this may not be very important in standard deep learning, it is critical when considering privacy because each learning step increases the final privacy budget. Therefore, DP-SGD with global clipping will use a larger privacy budget to achieve the same level of accuracy as DP-SGD with local clipping.



summary_of_the_review: 
Overall, while I think this paper explores an interesting question, I also think it overstates its contributions and impact. In particular, I think that the utility of global clipping is not sufficiently well supported by theory or experiments. In addition, I think that the use of gradient flow to analyze the dynamics of DP-SGD is interesting but lacks clarity at this time. For the above reasons, I will argue for rejection.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a new clipping method for DP-SGD. It is shown that this new clipping method performs favorably empirically. Furthermore, the paper analyzes the clipping method using NTK.
main_review: - Simple and elegant clipping
- Nice theoretical analysis 
- Nice empirical showing
summary_of_the_review: I am in favor of this work. The global clipping is simple but elegant. Furthermore, the NTK analysis is nice and helps support the intuition behind the method. I think that using NTK to analyze differential privacy is actually a method with potentially widespread applicability. Furthermore, the empirical analysis of the method seems sound. The issue of calibration with DP-SGD is also interesting and understudied. I find few faults in this work, and the brevity of this review is a consequence of having little to critique.
review_title: null

Meta-review: The major concern with this paper is the unfair comparison between global and local clipping (at least from the theoretical point of view). The assumption that the norms of the gradients are bounded in Theorem 2 is too strict for the following reasons. Clipping has been introduced exactly because we cannot assume the norm of the gradient to be bounded by a fixed constant  in the first place. Accordingly, comparing two clipping methods under the bounded gradient assumption does not seem relevant. Further, the two methods are not studied under the same set of assumptions (In Theorem 1, the norm of the gradient is not assumed to be bounded, but in Theorem 2 it is). 
A fair comparison needs to be presented to make the case for the proposed method.
Decision: Reject