An improved analysis of per-sample and per-update clipping in federated learning

We thank the reviewer for the interesting and helpful comments. You can find our replies below:

W1. The experiments would be stronger if continued for more communication rounds.

Thanks for the suggestion. We agree with the reviewer and have updated Fig.2 (c) in the revised manuscript. With the updated Fig.2 (c), we clearly see that even when $c=0.15$, we can still reach the target accuracy but at the cost of more communication rounds.

W2. The "assumptions" column of Table 1 needs formatting

Thank you for providing suggestions for better formatting. We have improved Table 1 in the revised manuscript.

Q1. The meaning of the dotted line in Figs 1/2c

The dotted lines represent the target accuracy $||\nabla f(\mathbf{x}_t)||=0.18$. We have clarified this in the caption for Fig.1 and 2.

Q2. It is unusual as far as I know to obtain a DP guarantee with per-sample clipping. Does that come from bounding the sensitivity by taking the worst case ||y_i|| given the fixed number of local steps \tau? That seems like it would be really weak.

We refer to Appendix C.6 and D.5 for further detailed discussions (especially regarding the notion of privacy, sensitivity and how to analyze the trade-off for both algorithms). Please let us know if there is anything unclear.

Q2. I'm surprised that "per-update is no better than per-sample in terms of the optimal privacy/utility trade-off". Can you provide any intuition there?

Thank you for your question. We refer to the Privacy discussion section of per-update clipping in the main text. More detailed information can be found in Appendix C.6.3 and Appendix C.6.4.

Q3. Could there be any utility in doing both per-sample and per-update clipping? How hard would it be to extend the analysis to that case, and if you can, what does it say?

Thank you for the interesting question. We, unfortunately, are not sure what you mean by doing both per-sample and per-update clipping. If you refer to using two stepsizes in Algorithm 1, here is the answer:

Let us first focus on the convergence behaviour without considering the DP noise. Then, adding an inner stepsize to per-sample clipping makes it better, as the resulting algorithm can converge to any accuracy given any clipping threshold. Also, a larger stepsize can be used when $L_1\neq 0$ compared with per-update clipping.

However, when we add DP noise, adding an inner stepsize into Algorithm 1 is unlikely to improve the best privacy-utility trade-off. We refer to Appendix C.6.4 for details.

We hope we have addressed your concern. If not, we would like to engage in further discussion if the reviewer could elaborate more on this question

General

We thank the reviewer for the positive feedback. If you believe this paper should be accepted, please consider increasing your score - this would boost our chances! Thank you!

We thank the reviewer for the constructive evaluation of our paper. We provide an answer to your concerns below:

W1: The contribution is mainly on the theoretical exploration, and does not lead to practical guidance for hyperparameter tuning

Indeed, we agree that the contribution is mainly on the theoretical improvements.

• Suppose there is no DP noise. We provide explicit formulas for the optimal choices of stepsize to reach $\epsilon$-accuracy in sections C.5 and D.4 in the appendix.

• When considering DP noise, we provide the optimal choices of stepsize and clipping thresholds for reaching optimal privacy-utility trade-off in sections C.6 and D.5 in the appendix.

Although setting theoretically optimal hyperparameters can be complex and unlikely in practice, we could still gain some vague insights or ideas from the theories.

W2: There has been some theoretical exploration on this topic, and it seems that many proof techniques of this work come from Koloskova et al. (2023).

We agree with the reviewer that there has been some theoretical exploration on this topic already. However, there is no tight analysis for these two algorithms under standard assumptions so far. Presenting tight convergence results and providing detailed privacy-utility discussion for the two popular clipping algorithms with relaxed assumptions can open further research directions for analyzing differential private federated learning.

Similar to many local SGD literature [Stich 2019, Koloskova et al. 2020] that are built upon the proof techniques used in mini-batch SGD, we are also greatly inspired by the case distinction discussion from Koloskova et al. (2023). However, analyzing the algorithms in decentralized settings is non-trivial. Please see section 3.3 (relation with Koloskova et al. 2023) for a more detailed comparison in the revised manuscript.

General

We thank the reviewer for the very positive comments. We hope that we have addressed your concerns. If not, we would like to engage in further discussion.

We thank the reviewer for the constructive and helpful comments. Your every comment is important to us. You can find our replies below:

W1. The authors proved drastically different convergence results under per-sample clipping and per-update clipping, even though the two clipping methods are equivalent when $\tau=1$. This needs more clarification.

We hope the discussion of the two algorithms in Appendix E has addressed your concern.

Intuitively speaking, in per-update clipping, the local stepsize can control the norm of the model update $\Delta_i := -\eta_l\sum\nabla F_i(\mathbf{y}_i)$ such that $\Delta_i$ might not be clipped. However, if we remove $\eta_l$, we can no longer control the norm of $\Delta_i$ given a fixed $c$ and may risk converging to the neighbourhood. Please let us know if anything is unclear.

W2. Although the analysis holds for arbitrary clipping threshold, satisfying convergence to an accurate solution still relies on setting a large enough clipping threshold. This insight makes sense theoretically, yet it is quite different from practice.

Thanks for this interesting question and the references!

• Indeed, when we do not add any noise, the large clipping threshold allows Algorithm 1 to converge to a desired solution.
• When we consider DP training, the noise scale should be proportional to the clipping threshold, i.e. $\sigma_{\text{DP}}^2 \ge \Omega(c^2)$. In other words, if we use a large clipping threshold, a large noise should be added, which might break the utility. In the DP setting, the optimal choice of $c$ is no longer $+\infty$. Instead, it depends on the privacy budget and many other factors. The optimal choice of $c$ can be found in Appendix C.6.3 and D.5.3. Therefore, as you pointed out, a small clipping threshold might often be a good choice in practice.

W3. Another less critical weakness is that the main theorems (Theorem 1 and Theorem 2) seem to be direct extensions of the prior work [Koloskova 2023]. Consequently, it needs to be clarified how non-trivial are the additional efforts made in this work.

Please see section 3.3 (relation to Koloskova et al. 2023) in the updated manuscript for a more detailed comparison against Koloskova et al. 2023.

Q1. Could the author explain why this local update step-size would contribute to significantly different convergence behaviors between per-sample and per-update clipping? See weakness 1 for details.

We hope our answers to your W1 has addressed this question.

Q2. Could the authors comment on this discrepancy between recommended large clipping threshold in this paper and the small clipping threshold used for practical DP learning?

We hope the clarification in W2 has addressed your concern. When we consider DP training, the optimal choices of clipping threshold depend on the privacy budget and other factors. Please see Appendix C.6.3 and D.5.3 for detailed optimal choices of $c$.

Q3: Is there a reason why, in the experiments of Figures 1 and 2, the clipping threshold for per-sample clipping is chosen to be much larger than the clipping threshold for per-update clipping?

Thank you for your question.

In the MNIST experiment, we observed that the norm of the mini-batch gradient i.e., $\nabla F_i(\mathbf{y}_i)$ (Line 8, Algorithm 1) is much larger than the norm of the model update, i.e., $\Delta_i:=-\eta_l\sum\nabla F_i(\mathbf{y}_i)$ (Line 11, Algorithm 2). Using a smaller clipping threshold than 1.5 will possibly give a similar convergence behaviour as when $c=1.5$ in Fig.1 (c), i.e., the norm of the gradient can not reach the target accuracy $||\nabla f(\mathbf{x}_t)||=0.18$.

Q4. L, M are not defined

Thank you for pointing these out. We have clarified the meaning of $L$, $M$, and $g_{i,t}$ in our revised manuscript.

General:

If you agree that we addressed all issues, please consider raising your score--this would boost our chances. If you believe this is not the case, please let us know, and we will try our best to answer further question.

We thank the reviewer for the evaluation of our paper. Your every comment is important to us. We did our best to understand and reply to your constructive feedback. Most updates are made into privacy discussion and section 3.3 in the revised manuscript. We provide answers to your concerns below:

W1. This make the comparison between Algorithm 1 and 2 in Section 3.3 very confusing, given that after incorporated with the inner learning rate, both of them can achieve arbitrary accuracy. So, what do the analysis want to tell? Which clipping method should we apply in practice? Overall, this makes the practical impact of the theoretical results weak.

We sincerely apologize for making you feel puzzled about the story and the motivation. Here is the clarification.

Algorithms 1 and 2 with DP noise are commonly used to protect different levels of privacy. We study Algorithm 1 because it is a widely used algorithm [Liu et al. 2022, Yang et al. 2022, Koloskova et al. 2023] for achieving example-level local DP. Our rigorous analysis on per-update clipping (Algorithm 2) opens directions for designing a new per-sample clipping algorithm by incorporating an inner stepsize. However, this strategy is new and non-trivial. We will explore this in our future work.

Nevertheless, these two algorithms still share some similarities from a pure algorithmic point of view. Comparing these two algorithms using our analysis is still meaningful. Please see section 3.3 in the updated manuscript.

W2. optimal utility-privacy tradeoff

We thank the reviewer for the reference and appreciate the insightful questions and suggestions. We refer the reviewer to the paragraphs Privacy discussion under Corollary I and II, section 3.3, for discussing the optimal privacy-utility trade-off and practical implications (see more detailed information in Appendix C.6 and D.5) in our updated manuscript. Please let us know if there is anything still unclear from your side.

W3. Test accuracy. We do not know under the corresponding optimal parameter selection which one performs better in practice.

Thank you for the suggestion. We have provided the test accuracy in sections H and I in the appendix.

We agree with the reviewer that practical performance can vary depending on the choices of many other factors, as demonstrated in N. Ponomareva, 2023. We have clarified this at the beginning of section 3.4 in the revised manuscript.

Q1. What is the optimal utility-privacy tradeoff/ utility bound under the optimal parameter selection of Algorithm 1 and 2 (in particular, Algorithm 1 with both inner and outer leaning rate)? In particular, what is the tradeoff considering the bias caused.

We refer the reviewer to paragraph Privacy discussion under Corollary I and II, section 3.3, and more detailed information in Appendix C.6.3 and D.5.3 for all the discussions.

Note that when $\tau=1$, Algorithm 2 (the same as Algorithm 1 but with both inner and outer stepsize) achieves the same optimal privacy-utility trade-off as Algorithm 1 (single stepsize). Therefore, there is no obvious benefit in terms of optimal privacy-utility bound in using two stepsizes for DP training.

Q2. Which clipping method we should use in practice?

Both algorithms are commonly used for protecting different levels of privacy. We should choose the algorithm according to the specific purpose, e.g., based on the definition of the neighbouring datasets.

Q3. Can the different clipping methods produce better performance compared to existing works?

We hope our answer in W1 has addressed your concern. We theoretically study the same clipping algorithms as the existing works [Liu et al. 2022, Zhang et al. 2022, Yang et al. 2022]. Therefore, we do not expect to achieve a better practical performance than them.

General

If you agree that we addressed all issues, please consider raising your score--this would boost our chances. If you believe this is not the case, please let us know, and we will try our best to answer your every question.

Thanks so much for your response and additional experiments. But I would like to keep my score since my practice concerns still remain. On one one hand, I still did not see any concrete comparisons between the two algorithms with their respective optimal parameter selections in general. Currently, the authors seem to claim that when $\tau=1$, their asymptotic performance is the same. So, still, I did not see insights from the theory which can be used to guide the practical hyper-parameter selection. On the other hand, I did not see the concrete experimental improvements. I did not see the $\epsilon, \delta$ parameters in the experiments or certain proper learning rate selections (the inner-outer one suggested by the author) can improve the practical DP-SGD performance. Hopefully, those issues can be addressed in your future revision.

We thank the reviewer for the constructive and helpful comments. Your every comment is important to us. You can find our replies below:

W2 and Q1. It seems that when we choose $c\rightarrow\infty$, the results (e.g., Theorem I) cannot be reduced to the unclipped results. The results cannot recover the unclipped results when the clipping parameters goes to infinity.

We apologize for the confusion. The complete convergence results of two algorithms, including the case where $c$ is extremely large, are presented in Theorem III and Theorem IV in the Appendix. Theorem III and IV recover the unclipped FedAvg when $c\to \infty$ (please see the explanation below Corollary III and Theorem IV).

Please let us know if there is anything that is unclear about recovering the standard unclipped results.

W1 and Q2. I'm not sure how the results can be applied to the differentially private setting. The authors consider the stochastic setting, and thus the authors need to specify what is the dataset you want to protect when you apply Corollary I and Corollary II. From my understanding, it would be more meaningful if the authors can provide the finite sum results with bounded stochastic gradient assumption instead of the stochastic setting with bounded variance assumption for the application of differentially private setting.

Thank you for your question. We first refer to paragraph Privacy discussion under Corollary I and II, together with more detailed information in Appendix C.6 and D.5 for a comprehensive discussion in private settings.

• We totally agree that finite-sum is ideal for the DP-training settings. We hope the study in Appendix C.6 and D.5 has addressed this concern.
• We, unfortunately, do not understand why the bounded gradient assumption is better than the bounded variance assumption. We agree that, in practice, knowing the gradient norm may give some insights into choosing the clipping thresholds. However, as far as we understand, the bounded gradient assumption is a more restricted and less practical assumption theoretically, which can exclude simple quadratics. We refer to Table 1 for analysis that uses bounded gradient assumption.

We hope we have addressed your concern. If not, we would like to engage in further discussion if the reviewer could elaborate more on this question.

Q3. On page 5, comparison to the previous works, why you can claim that the established results can recover the rate of the centralized clipped mini-batch SGD?

We apologize for the confusion. Please see Section E in the Appendix for a more detailed explanation for recovering the centralised clipped mini-batch SGD by discussing the relation between $\sigma$ and $c$.

Q4. I'm wondering when you consider the finite sum with bounded stochastic gradient assumption, how the lower bound result will look like in terms of the clipping parameter and the bounded gradient norm?

We hope our response in Q2 has addressed this question.

Under the bounded gradient norm assumption, there is no clipping bias if we pick $c$ to be larger than the bounded norm. See Zhang et al. 2022 for more detailed information.

Q5. According to Corollary I and Corollary II, it seems to me that there is no need to use any local update. If this is the case, why don't you just use the private variant of the Minibatch SGD?

Thanks for the interesting question! Yes, this is one of the main weaknesses of most distributed optimization algorithms for addressing non-convex problems.

Let us consider the problem that minimizes $f(\mathbf{x}):=\frac{1}{n}\sum_{i=1}^n f_i(\mathbf{x})$, where $\{f_i\}$ have non-zero heterogeneity. The current distributed algorithms with/without variance reduction can best achieve the same convergence guarantee as gradient descent (gradient norm squared decays as $\frac{LF_0}{R}$ [Karimireddy et al. 2019]), which shows no benefit in doing multiple local steps.

However, doing multiple local steps in practice might still be better due to the potential similarities among the individual functions. The same story applies here. Although we do not observe the benefit of using multiple local steps theoretically, we can possibly reduce communication costs when we use multiple local steps in some scenarios in practice (e.g., see Fig.1 (b)).

General

If you agree that we addressed all issues, please consider raising your score--this would boost our chances. If you believe this is not the case, please let us know, and we will try our best to answer your further questions.