Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers the effect of gradient clipping in Federated Learning and how it affects the convergence rate. They focused on the relaxed-smooth loss function. Each worker uses local gradient clipping and runs multiple steps of SGD before communicating and averaging the local models. The authors theoretically analyzed the algorithm and showed that for $N$ workers, the algorithm has $O(1/N\\epsilon^4)$ iteration complexity to find an $\\epsilon$-stationary point. Finally, the theoretical results are experimentally verified on CIFAR-10 (Resent-56 model), Penn Treebank and WikiText (LSTM models).
main_review: Gradient clipping is known to be an effective tool in training RNNs and mitigating the gradient explosion. However, there is not much work on analyzing its effect in distributed or federated learning scenarios. This paper is among the few ones that tries to theoretically analyze the behavior of FedAvg and similar algorithms when the workers use gradient clipping in their local SGD updates.
The paper is generally well-written and the claims are well-supported. One missing recent paper in this area (which was published recently and I don't expect the authors to be aware of it) is the "Understanding Clipping for Federated Learning ..." by Xinwei Zhang, et. al., published recently at ICML'21 Workshop on Federated Learning. It would be nice if the authors can comment and compare their results with the findings in that paper and other similar works.

Some minor suggestions:
 - One nice addition to the paper might be to show empirically how tight the theoretical bounds are (at least for a toy example).
 - Assumption 1, iii, $\\nabla$ is missing in the first equation.
 - The paragraph after Lemma 2, last sentence, the error is quadratic in $I$, not linear.
summary_of_the_review: The paper has theoretically analyzed the effect of gradient clipping in local SGD updates in Federated Learning and FedAvg. To the best of my knowledge, the technical analysis and results are incrementally novel and improves the results of existing works.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: Gradient clipping is an important technique in training deep neural network. Typically, ones need to use the globally averaged gradient to estimate the norm. However, it requires gradient synchronization for every iterations, which is not practical in federated learning. In practice, practitioners only apply local gradient clipping to the local iterates while the theoretical analysis is lacking. This paper analyzes the convergence of the local gradient clipping. The theoretical results show that the convergence is guaranteed when both the number of workers and the number of local iterations are not too large.
main_review: Gradient clipping has become a de facto approach in training the deep neural networks especially for LSTM and Transformer. When communication bandwidth is limited and sharing gradient can leak privacy in federated learning, global gradient clipping is impractical. In this case, practitioners use local gradient clipping as workaround. However, there is no theoretical understanding on this approach, This paper bridges the gap between theory and practice. Overall, I think the paper is well written and easy to understand. But the contribution is incremental. In addition, I have a few comments regarding theory and experiments:

1. Theorem 1 holds when $N \leq O(1/\epsilon)$ and $I \leq O(1/(\epsilon N))$. On one hand, if we need to use many workers such as $N = 1/\epsilon$, then $I \leq O(1)$, which means there is no local iterations at all. On the other hand, if we just need a rough solution (e.g., a moderate $\epsilon$), which is typically the case in deep learning, then $N$ has to be small. It seems to me the theory does not apply to common cases in practice. It is good to plot the norm of the gradient to see how many cases in the experiments satisfy the assumption.

2. All the experiments focus on homogeneous local data in classic distributed settings. There is no experiment considering federated learning settings where the local data is heterogeneous and only a subset of clients participate in each training round. For the classic distributed training, global gradient clipping is applicable because of high-speed InfiniBand on the cloud and fast NCCL implementation.

summary_of_the_review: The paper provides theoretical analysis for local gradient clipping under the federated learning settings. However, the practical cases where the theoretical analysis can be applied is unclear. And, the experiments are based on homogeneous local data in classic distributed settings. The contribution is also incremental.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper propose a novel distributed optimization method CELGC. CELGC adopts normalized gradient for local training (e.g., FL) so that it achieves better performance than SGD.
main_review: The proposed CELGC is simple yet effective. The only difference from local sgd is that CELGC adopts normalized gradient if the norm of gradient is large. The authors also prove its convergence rate for relaxed smooth and non-convex functions.

In addition to convergence theorem, I care more about the practicality of the proposed algorithm and I have the following questions:
1. CELGC has many hyper-parameters, e.g., learning rate, clipping threshold and batch size. I notice that in the three experiments, these hyper-parameters are quite different. How to tune these hyper-parameters in a new training problems if we do not have any previous experience (In the experiments, authors often set parameters according to other papers). Is it possible to give an approximate range for these parameters?
2. The authors claim that CELGC can achieve the linear speedup with proper setting. But they seems do not conduct speedup experiment.
3. What the difference between the naive version of the parallel gradient clipping algorithm and CELGC with i=1?. I think they are the same one, i.e. \kappa = 0, so that the performance of the baseline should be better than CELGC with I>1 in the comparison of epochs. This is not consistent with Figure1(a). Besides, I think the authors should set a large batch size for the baseline in the experiments. Normalized gradients may lead to a bad performance when the batch size is small [1]

[1] Beyond convexity- Stochastic quasi-convex optimization. NIPS, 2015.
summary_of_the_review: This paper has many things to be improved.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a new variant of SGD with clipping and infrequent communications (local updates) called Communication Efficient Local Gradient Clipping (CELGC) aimed at solving non-convex federated learning problems under the generalized smoothness ($(L_0, L_1)$-smoothness) assumption. The authors derive ergodic convergence guarantees for the convergence of CELGC to the first-order $\epsilon$-stationary point assuming additionally that the noise in stochastic gradients is bounded with probability $1$ and heterogeneity of the local data on clients is also bounded. Although the authors claim that their result shows that CELGC achieves linear speed-up and has better communication complexity than the naive version of parallel Clipped SGD, the proofs contain several significant inaccuracies making the main result of the paper incorrect in general. Moreover, several assumptions about the parameters such as the number of workers $N$ and the number of local steps between two consequent communication steps $I$ are restrictive.
main_review: ## Strengths
1. **Motivation and clarity.** The paper is well-motivated and easy to follow. The authors also provide a sketch of the proof in the main text which is useful.

2. **Related work** section provides a good summary of existing works relevant to the topic. However, Table 1 is not accurate and should be improved (see **General questions and comments** below).




## Weaknesses
1. **The proofs contain mathematical mistakes that break the main result of the paper.** In the proof of Lemma 2 the authors rely on the following formula (page 15, the third step at formula (12)): $\mathbb{E}\left[ \sum_{i\in \overline J(t)} \nabla F_i(x_t^i, \xi_t^i) | \xi^{[t-1]}\right] = \sum_{i\in \overline J(t)} \nabla f_i(x_t^i)$. This is not true since the set $\overline J(t)$ depends on the stochasticity at iteration $t$ of the algorithm. Moreover, the authors repeat this mistake several times throughout the proof when "move" the factor $|\overline J(t)|$ outside the expectations (e.g., later in the same formula and also when applying (12) to (9) in (14)). Due to the same issue, one cannot use second-moment representation in the fourth row of the formula (13). Finally, even if we assume that everything is correct before the last step in formula (13), there is another issue: in the last row of (13), the second term should be $2\frac{\eta^2 |\overline J(t)|^{\color{red}2}}{N^2}$. Therefore, in the final bound, instead of the term $\frac{AL_0\eta^2\sigma^2}{N}$ one should have $AL_0\eta^2\sigma^2$. As the result, in the last upper bound from the proof of Theorem 1 the third term should be $\frac{AL_0\eta^2\sigma^2}{\epsilon}$ instead of $\frac{AL_0\eta^2\sigma^2}{{\color{red}N}\epsilon}$. Therefore, the number of iterations $T$ is not proportional to $\frac{1}{N}$, i.e., **linear speed-up is not proven**. Since it is claimed as one of the main contributions of the paper, the described issue is a very strong reason for the rejection of the paper.

2. **Assumptions on the parameters in Theorem 1** are strong and not well-defined for some special cases. First of all, the condition $N \leq \frac{1}{\epsilon}$ is strong and in FL-applications, where $N$ can be large, it is typically satisfied for very small values of $\epsilon$, meaning that the problem should be solved with too high accuracy. In practice, it is often sufficient to solve the optimization problem with not too high accuracy. Next, the authors also assume that the number of local steps between two subsequent communications satisfies $I \leq \frac{1}{2N\epsilon}$. Since $I$ is a positive integer one should have $N \leq \frac{1}{2\epsilon}$. So, in fact, it means that either $\epsilon$ is extremely small, or $I = O(1)$, or $N$ is small. The drawbacks of the first and the third options are covered above. The second option describes a theoretically simple case since the number of local steps is small. Moreover, in this case, $N\epsilon = \Omega(1)$ meaning that the derived communication complexity bound is not better than for Naive Parallel SGD with clipping. Finally, the assumptions on $\gamma$ and $\eta$ are not well-defined when $\sigma = 0$ and $\kappa = 0$: the condition $\frac{\gamma}{\eta} = 5(\sigma + \kappa)$ implies that $\frac{\gamma}{\eta} = 0$ in this case meaning that either $\gamma = 0$ (no clipping) or $\eta = \infty$. This means that the assumptions on $\gamma$ and $\eta$ are incorrect.

3. **Numerical experiments** are conducted for the system with $N = 2$ workers, which is a too small number to demonstrate parallel speed-up properly. Moreover, it would be better to show the dependence on the number of communications rounds in the experiments. Moreover, to have a fair comparison of the method with local updates and the method without them (Naive Parallel SGDClip) one should use I times larger batchsizes for Naive Parallel SGDClip. It seems that the authors used the same batchsizes for local and non-local methods for each iteration.



## General questions and comments
1. **Page 2, "... and hence is communication-efficient".** This sentence should be rewritten since in the current form it implicitly says that local steps ensure communication efficiency. In fact, it is not true for highly heterogeneous or arbitrary heterogeneous cases (e.g., see Woodworth et al. (2020a) and Gorbunov et al. (2020)).

2. **Table 1** requires clarifications. First of all, Ghadimi & Lan (2013) do not use the bounded gradients assumption. They derive the results under classical smoothness and bounded variance assumptions. This should be explicitly stated either in the table or in the caption of the table. The complexity guarantee should contain two terms: one is proportional to $\epsilon^{-2}$ and the second one is proportional to $\epsilon^{-4}$. Moreover, their result can be easily generalized to the naive parallel settings without any assumptions on bounded data. Secondly, in the current form, the complexity bounds for the methods are incorrect for the special case when $\sigma = 0$ or/and $\kappa = 0$ since the terms with better dependence on $\epsilon$ are omitted. This should be fixed. Next, the table should contain the results for Local-SGD under the classical assumptions to have a clear comparison (e.g., from Koloskova, Anastasia, et al. "A unified theory of decentralized SGD with changing topology and local updates." International Conference on Machine Learning. PMLR, 2020). Finally, I have not found the rate presented in the row "Naive Parallel of (Zhang et al., 2020)" in (Zhang et al., 2020). This should be clarified (ideally, rigorous proof should be provided).

3. **Missing references.** I believe the authors should at least mention the work Reddi, Sashank, et al. "Adaptive federated optimization." arXiv preprint arXiv:2003.00295 (2020) since this paper considers very relevant methods such as Federated Adam.

4. **Assumption 1 and the remark after it.** Assumption (iii) is too restrictive: it is not satisfied for the noise with the unbounded domain such as Gaussian noise. The authors claim that "it is a normal assumption when encountering relaxed smoothness". However, this claim is not explained. I do not see any evidence of why this assumption is reasonable in this case. I understand that it is used in prior works, but I guess it is because of the difficulty of analyzing the methods under relaxed smoothness. Next, assumption (iv) is also quite restrictive. For example, in the convex case, one can analyze Local SGD and its variants without this assumption. I understand that in the non-convex case it is used in prior works, but it is better to write about this explicitly.

5. **Page 5, "... our algorithm is expected to have better performance."** This is not true when $\kappa$ is large: even Local SGD does not benefit from local steps in this case.

6. **Additional comments about Theorem 1.** Assuming that the formula for the communication complexity is correct, it is still not clear why it is better than the mentioned complexity of Naive Parallel SGD with clipping since $\kappa$ can be large.

7. **Page 6, "Another interesting fact is that both iteration complexity and communication complexity only depend on $L_0$."** Most likely it means that the authors just omitted some important dependencies in the complexity estimates.

8. **Page 18, lower bound for $T$.** The detailed derivation should be added after fixing all mistakes in the proof.


## Minor comments
1. **Lemma 2, "If $2\gamma I \leq c/L_1$ for some $c > 0$, then $\gamma \leq 2\gamma I \leq \frac{c}{L_1}$".** This is a trivial statement.

2. **Page 14, "For each iteration $t$, We"** $\longrightarrow$ "For each iteration $t$, we"

3. **Page 15, "and (b) holds due to Lemma 1 and Lemma 5"** $\longrightarrow$ "and (d) holds due to Lemma 1 and Lemma 5"

4. **Lemma 3 restated, page 16:** in the RHS one should have $\|\nabla f(\overline x_t)\|$

5. **Inequality (17), the second part**: dependencies on $\sigma + \kappa$ are missing.

6. **Page 18, definition of $V(x)$:** $\widetilde{A} \longrightarrow A$
summary_of_the_review: To sum up, several parts of the proof should be corrected and the theory should be extended to support more general choices of $N$ and $I$. Moreover, several parts of the paper such as the comparison of the known complexity results with the derived ones and numerical experiments require improvements.

Unfortunately, the current version of the paper cannot be accepted to the conference. If the authors resolve the mentioned issues during the rebuttal, I will increase my score.
review_title: null

Meta-review: This paper made a solid contribution studying the convergence rate of a simple distributed gradient clipping algorithm. The proposed algorithm simply clips the gradients on each local machine and then do simple distributed update of the parameters. 

The result, if correct, is quite strong and significant: The proposed algorithm is simple, and shows some benefit comparing to previously proposed algorithms -- The strongest part of the paper is that it comes with a convergence rate bound (which is typically hard to prove for gradient clipping methods).


However, during the rebuttal period it was discovered that a number of places in the proofs are not well-supported, the paper has to go through major revision in order to meet the publication standard.
Decision: Reject