Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a communication-efficient distributed gradient clipping algorithm for federated learning, which is called EPISODE. The algorithm works particularly well with the heterogenous data and under the nonconvex and relaxed smoothness setting. The novelty consists in two techniques: episodic gradient clipping and periodic resampled corrections. Another contribution of this paper is to provide a convergence proof for the proposed algorithm under several assumptions. Empirical studies show that EPISODE outperforms other federated learning algorithms on the both synthetic and real datasets, which include SNLI and ImageNet.
strength_and_weaknesses: Strength:

1. This work seems to be the first to study the federated learning under heterogeneous data setting with relaxed smoothness assumption, and provide a provable algorithm to solve the problem.
2. The paper is well motivated by giving examples why existing algorithms (CELGC and SCAFFOLD) do not work in the setting.
3. The theoretical results come with well sounded implications, making the results convincing (theoretically).

Weaknesses:

1. I am not sure if the given setting is realistic. Like many other distributed optimization papers, this paper put quite a few constraints to the scenarios, such as heterogeneity of the data. But in reality, do we really need to solve such a problem?
2.  While the paper proposes a distributed algorithm, which implies the problem scale is large enough. However, in the experiments, the data/model scale is not that big that a single machine can easily hold them. It is like motivating the paper by solving a very difficult problem but it turns out the problem is not that challenging.    
clarity,_quality,_novelty_and_reproducibility: 1. The paper is well written and the quality is good. 

2. The paper is novel in that it proposes two new techniques to solve the distributed optimization with heterogenous data. And the algorithm has theoretical convergence guarantee.

3. Given that the algorithm is intrinsically simple, it won't be difficult to reproduce the results.
summary_of_the_review: The major contribution of this paper is to propose an algorithm to solve the distributed optimization with heterogenous data. Although the setting might not be realistic, the theoretical contribution should still be appreciated.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposes a new algorithm called EPISODE for Federated learning with clipping. The algorithm at every round first computes the full gradient from all the clients and after that either clips all of the local updates, or doesn't clip it based on the norm of this full gradient. 

Authors prove the convergence under (L_0, L_1) smoothness assumption. Authors also provide an experimental comparison of their algorithm to the previous baselines. 
strength_and_weaknesses: + Paper provides the algorithm that can achieve theoretically faster convergence than previous algorithms under (L_0, L_1)-smoothness. 

- It is not compared in the paper how does proved convergence rate compare to FedAvg and to Scaffold convergence rates. 

Experimental evaluation is limited:

- IMAGENET and SNLI datasets are not Federated Learning datasets. Would be more interesting to see comparison for some classical FL datasets, e.g. from LEAF benchmark. 

- in Imagenet experiments the learning rate was fixed to be the same value for all of the algorithms: this might be not a fair comparison of the algorithms, as optimal stepsizes might be different for different algorithms. 

- Paper did not provide experimental comparison to other clipping baselines, such as e.g. adaptive clipping [Andrew et al 2021]. 

- Every round of the proposed algorithm requires communicating gradients twice. Thus it can be considered that every round has effectively two rounds of communications. This was not taken into account during experimental comparison. 

- It is also unclear if the experimental speedup comes from clipping, or from better estimating correction terms G_r and G_r^i. 
clarity,_quality,_novelty_and_reproducibility: The paper is well written, theoretical result is novel. However experimental evaluation is limited. 
summary_of_the_review: The paper is well written, theoretical result is novel, but not well compared to the literature. Experimental evaluation is limited.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposed the EPISODE method for clipping in federated learning. Each algorithmic round in EPISODE consistents two communication rounds: (1) a “global” gradient is estimated by sampling and averaging the gradient over all clients; (2) the estimated gradient is then used for two purposes, as control variable similar to SCAFFOLD, and as an indicator for gradient clipping; the indicator will determine whether the gradient (calibrated by control variable) for each local step will be clipped. Experiments on SNLI, ImageNet and CIAFR-10 show that EPISODE outperforms FedAvg, SCAFFOLD and CELGC. 

strength_and_weaknesses: I did not check the full details of the proof, but the results look reasonable to me. The proposed EPISODE method appears to be novel to me. Compared to CELGC (Liu et al. 2022), EPISODE studies heterogeneity in federated learning, and introduced control variates similar to SCAFFOLD (Karimireddy et al., 2020). Compared to SCAFFOLD, EPISODE studies the assumption of relaxed smoothness functions and applies gradient clipping. 

I did not see obvious flaws in the draft. However, I also want to see more discussion connecting theory and practice: in the relaxed smoothness setting, could the authors comment on the theoretical advantage of EPISODE over SCAFFOLD, and how does that connect to the empirical results? 

FedAvg is a strong baseline, but I am a little surprised to see that in Figure2, both CELGC and SCAFFOLD underperform FedAvg for accuracy, but EPISODE (the conceptual combination of CELGC and SCAFFOLD) outperforms FedAvg. 

I would encourage the authors to discuss application scenarios. Assuming all clients participate in training every round seems to suggest the algorithm is more applicable to cross-silo setting. See [A Field Guide to Federated Optimization https://arxiv.org/abs/2107.06917 Section 3.1]. 


clarity,_quality,_novelty_and_reproducibility: The paper is generally well written and easy to follow. 

The algorithm seems to be easy to implement for reproducibility, though releasing code if possible could be a bonus. 

Clipping has been studied in federated learning for robustness [Learning from History for Byzantine Robust Optimization], and privacy [Understanding clipping for federated learning: Convergence and client-level differential privacy ] with convergence proof. The authors may cosinder weaken the claim on clipping in FL. 

summary_of_the_review: As the main contribution seems to be theoretical, I would see more discussion on the theory advantage and the connection between theory and practice.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper introduces a new optimization algorithm for the federated learning setting with heterogeneous data, limited communication, and a relaxed smoothness condition. The algorithm uses two new ideas: episodic gradient clipping and periodic resampled corrections. They prove that the algorithm has improved performance for heterogeneous data compared to prior methods, and matches prior results for homogeneous data. They demonstrate the effectiveness of the algorithm empirically, on both synthetic and realistic data.


strength_and_weaknesses: The task studied in the paper is natural and relevant and has been studied in prior works. The paper significantly improves the state-of-the-art results, and thus the contribution is significant. The algorithm is based on novel ideas, and its theoretical analysis is non-trivial. Finally, the experiments demonstrate the effectiveness of the algorithm compared to prior approaches.  

I cannot point to weaknesses, although I should mention that I am not familiar enough with the relevant literature, and hence this review has low confidence.

clarity,_quality,_novelty_and_reproducibility: The paper is well-written and presents the contributions clearly. The results seem novel, and the experiments are well documented.
summary_of_the_review: For the reasons discussed above, I recommend acceptance.

----------------------------------------------------------

Post rebuttal: I have read the other reviews and responses, and I will stick with my original score.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a federated learning with clipping of gradients, in the realistic heterogeneous data setting. The algorithm at every round first computes the full gradient from all the clients and depending on the norm of the full gradient decides to clip all local updates. Convergence is shown under the (L_0, L_1) smoothness assumption. Communication is thus doubled compared to the naive FedAvg baseline.

Reviewers liked the clear presentation and ideas, and mostly found the results convincing, both in theory and experiments. Some reviewers would have liked to see more discussion on connecting theory and practice.

We hope the authors will incorporate the several points mentioned by the reviewers in the final version. 
justification_for_why_not_higher_score: Some reviewers would have liked to see more discussion on connecting theory and practice.
justification_for_why_not_lower_score: No major concerns remained
Decision: Accept: poster