Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper combines local sgd with gradient clipping. Local sgd is a communication-efficient method by skipping some aggregation rounds. Gradient clipping is a common technique to address the gradient exploding issue for some neural networks such as RNN and LSTM. By combining these two techniques, this paper achieves communication-efficiency and resolves the gradient exploding issue.
strengths_and_weaknesses: Strengths:
* The motivation is clear. I think combining local sgd and gradient clipping makes sense.
* Theoretical analysis is provided. Especially, the communication complexity of the proposed method is proved to be better than the naive parallel method of the baseline gradient clipping. 
* Experiments demonstrate that the proposed method is faster than the baseline in terms of wall-clock time in some cases.

Weaknesses:
* LSTM used to be the default method for processing sequential data such as in Natural Language Processing (NLP). However, now we can see the trend that transformer-based methods such as BERT has become the dominating method in NLP and related sequential data tasks. The benefits of transformer-based methods are obvious: easier parallelism leading to faster wall-clock time for training, and no need for back propagation via time (which would cause issues like gradient exploding). Given the current state-of-the-art established by transformer-based methods, I am afraid that the usefulness of the proposed method in this paper may be limited. 
* Local SGD is primarily used in federated learning where the communication between clients and central server has a very high cost. I think it’s better if more experiments on federated learning (heterogeneous data distribution across clients, partial precipitation, etc) can be included.

==========after author response==========      
I appreciate the authors' response. I understand there are some merits for the proposed method. I intend to keep my score unchanged mainly because I am still concerned with the usefulness of the proposed method due to the more recent transformer-based models as the current dominant methods in sequential data processing. 
questions: In addition to my concerns as mentioned in the weaknesses above, I have the following questions:
* In Table 1 where the iteration and communication complexity of different methods are compared. Will the communication frequency I impact the communication complexity of the proposed method? I don’t see I in the table. 
* In Figure 1a (right) where test accuracy vs epoch is shown, it looks like all methods (baseline and proposed methods with different I) converge to the same test accuracy. When I is very large (i.e., communication is less frequent), should the converged performance become worse? I noticed that same phenomenon in Figure 2a(right) and 3a(right).


limitations: none
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors provide a decentralized gradient clipping algorithm. The authors show that under some conditions the algorithm will converge to the $\epsilon$-stationary point with sample complexity $O(1/(N\epsilon^4))$ and communication complexity $O(1/\epsilon^3)$. And the algorithm performance shows the benefit of the proposed algorithm against naive parallel SGDclip.
strengths_and_weaknesses: Strengths:
1. Instead of using L-smoothness, the algorithm can converge under a weaker condition (L0,L1)-smoothness.

2. The experiments compare with the algorithm with wall clock time, which shows the speed up in the training phase.

Weaknesses:
1. With L-smoothness, [1] show the lower bound of communication iterations is lower bounded by $1/\epsilon^2$. But even when $L_1 = 0$, the number of communication iterations is still in the order of $1/\epsilon^3$.

2. (iv) in Assumption 1 is somehow strong. Even it can be shown in some layers for some experiments in Appendix E. Maybe change of Lemma 1 will be more important.

3. The hardest part of showing the result under the heterogeneous setting. in the homogenous setting, it seems that the most difficult part is dealing with I, the rest part will be the same as [51](ref in the paper).

4. The experiment would compare with more algorithms (e.g. clipping version of FedAVG)


Ref
[1] Zhang, X., Hong, M., Dhople, S., Yin, W., & Liu, Y. (2020). Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005.11418.
questions: See weaknesses.
limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper studied the local stochastic gradient clipping method for nonconvex distributed optimization. Meanwhile, it provided the convergence analysis of the proposed CELGC algorithm under i.i.d. setting. It also conducted the empirical experiments to verify the efficiency of the proposed algorithm. 
strengths_and_weaknesses: This paper studied the local stochastic gradient clipping method for nonconvex distributed optimization. Meanwhile, it provided the convergence analysis of the proposed CELGC algorithm under i.i.d. setting. It also conducted the empirical experiments to verify the efficiency of the proposed algorithm. 

1)	From algorithm’ view, the proposed CELGC algorithm only extend the classic FedAvg algorithm to  gradient clipping setting.

2)	From theoretical analysis’ view, although the given convergence analysis relax the smoothness condition, it strictly relies on the i.i.d. setting. In convergence analysis, the given relaxation of the smoothness condition is also popular, so it does not take any challenge.  

Overall, the novelties and contributions of this paper do not reach the level of NeurIPS.  
questions: 1)	From algorithm’ view, the proposed CELGC algorithm only extend the classic FedAvg algorithm to  gradient clipping setting.

2)	From theoretical analysis’ view, although the given convergence analysis relax the smoothness condition, it strictly relies on the i.i.d. setting. In convergence analysis, the given relaxation of the smoothness condition is also popular, so it does not take any challenge.  

3)	In the experiments, the given comparative methods only including gradient clipping methods are not reasonable. You should add some existing standard gradient-based methods such as FedAvg as comparative methods. 
limitations: Yes
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper focuses on training neural networks in the infrequent-communication setting (such as Local-SGD) with gradient clipping. Prior works have shown that gradient clipping is an important technique to stabilize the training of neural networks. Local-SGD is a communication-efficient distributed training algorithm that can significantly reduce the communication overhead and lead to totraining speedup. However, using the two is not straightforward as gradient clipping is applied on the averaged gradient whereas Local-SGD conducts several local steps before executing any communications.

To overcome this issue the paper proposes CELGC, which relies on prior work by [1]. The paper provides a theoretical and empirical study of CELGC. The experiments include an evaluation of the ResNet-34 and AWD-LSTM neural architectures.


[1] Zhang, Bohang, et al. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.
strengths_and_weaknesses: > **TL;DR:**
The paper presents an algorithm called CELGC that makes gradient clipping compatible with the Local-SGD setting. The paper provides both a theoretical and an empirical study of the algorithm. However, the algorithm is lacking novelty due to the high similarity with [1] and completely disregards very relevant papers such as [2]. Furthermore, the empirical results are hard to read and not convincing enough.
---
**Update Following Rebuttal with imageNet Results**
Throughout the rebuttal process, the authors have responded to my concerns and I appreciate the answers. The authors have made great efforts to improve the paper by adding confidence intervals to the figures and clearly listing the final accuracies. The authors also added ImageNet experiments that both show strong empirical results and the usefulness of the proposed CELGC algorithm. I'm still concerned about usefulness of the CELGC, since it requires re-tuning the $\gamma$ hyper-parameter. However, I believe that CELGC is robust and provides both strong empirical and theoretical results. Therefore, I think that this paper should accepted after its rebuttal improvements.
---

**Pros:**
1. The paper is well written and addresses an important problem that allows Local-SGD to use gradient clipping.
2. The theoretical analysis seems correct with no significant errors.
3. The experiments include many different configurations, such as a federated learning experiment with homogenous data (although heterogeneous data would be preferable in this configuration).
4. The experiments used a learning-rate hyperparameter grid search for tuning each algorithm.

**Cons:**
1. The Figures in the experiment section are hard to read and often confusing. For example, in the two left plots in Figure 4 the comparison of convergence speed or final accuracy to the single GPU (baseline) is not possible. This specific figure is also misleading, as the X-axis is not the amount of processed data but rather some sort of execution time combined with iterations. Adding a zoomed-in figure and listing the final results in a table would significantly improve this. Furthermore, many figures are missing a valid comparison to the single GPU scenario (baseline) in order to show true linear scalability.
2. The figures do not have error bars or any confidence intervals. This is crucial for justifying the empirical results. Furthermore, I expect a robustness evaluation as listing the best-tuned results does not provide the whole picture.
3. The two right plots in Figure 4 are not described and can only be understood after collecting the pieces of information myself and solving the puzzle. It is not clearly stated which plot refers to which neural network. Figure 4 should be split into two separate plots (the two right and two left) with proper sub-captions.
4. A comparison to known scalable architecture-dataset combination is required. Figure 10 does not convince the scalability as it is not evaluated on a scalable configuration, such as ResNet-50 on Imagenet that was used in [1].

**Typos:**
1. Line #32: "in federated" --> "in the federated"
2. Algorithm 1 Line #3: "it" --> "its"
3. Line #239: "the iteration" --> "iteration"

[1] Zhang, Bohang, et al. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.

[2] Zhang, Xinwei, et al. "Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy." arXiv preprint arXiv:2106.13673 (2021).
questions: 1. It is common today to train neural networks with more advanced optimizers ( such as Momentum or Adam) than vanilla SGD which was used in the paper. What is the compatibility of CELGC with these relatively newer optimizers?
2. Today, it is common to apply gradient clipping locally in the Local-SGD or federated setting. Why was CELGC not compared to this simple approach?
3. The Naive Parallel SGDClip was defined as using [3] and synchronizing at every iteration. Why can't [3] simply be applied locally when training in the Local-SGD setting?
4. In Figure 1 the Naive Parallel SGDClip is much more volatile compared to CELGC, why is that?

[1] Kingma, Diederik P., and Jimmy Ba. "Adam: A method for stochastic optimization." arXiv preprint arXiv:1412.6980 (2014).

[2] Zhang, Xinwei, et al. "Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy." arXiv preprint arXiv:2106.13673 (2021).

[3] Zhang, Bohang, et al. "Improved analysis of clipping algorithms for non-convex optimization." Advances in Neural Information Processing Systems 33 (2020): 15511-15521.

---
> Improving the empirical study would help improve the score:
- Stronger empirical results, such as ResNet-50 on ImagNet.
- Comparison to the "naive" algorithms stated above (2 and 3).
- Adding zoomed-in figures to see the convergence rate.
- Listing the final results in a table.
- Hyperparameter robustness tests.
- Confidence intervals for figures. 

limitations: The paper addresses some of the limitations of CELGC in the conclusion section. For example, the limitation of being restricted to homogenous data makes it incompatible with the federated setting where the data is often heterogeneous.  A second limitation, which is not discussed, is that the CELGC requires tuning \gamma as it cannot be directly inferred from the existing gradient clipping hyperparameter. This adds additional computational cost when using CELGC on an existing neural architecture.
review_title: null

Meta-review: metareview: The paper presents a natural idea to combine local SGD with gradient clipping for communication efficient distributed training. Authors have addressed concerns from reviewers well (e.g., they included a ImageNet experiment). Overall well-motivated theoretical contribution with sufficient empirical validation. My recommendation is to accept this paper.
confidence: Certain
Decision: Accept