Venue: NeurIPS 2022 Conference

Reviews:

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: (I have been added as a reviewer only very late in the review process. Even though I am adding a few questions below I am fully aware that the authors cannot respond appropriately. Nevertheless, I believe these remarks might still be useful for the internal discussion an AC).

This paper studies stochastic gradient descent in a distributed/federated learning setting under the assumption that the $\alpha$-th moment ($\alpha \in (1,2]$) is bounded. This generalizes standard analyzes, that typically assume bounded variance (second moment).

Earlier work [22] studied SGD in a centralized setting ($m=1$ worker) under the same bounded moment assumptions. This work showed that gradient clipping allows SGD to converge, and this earlier work also showed that this approach is optimal by proving matching lower and upper bound.

The paper under review generalizes the results from [22] to a distributed setting. The main results are:

(i) an asymptotic convergence analysis for two version of clipping (per-iteration or per-epoch) with local steps under the assumption that the functions on the $m$ workers are identical (homogenenous), for the strongly convex and non-convex settings. The convergence guarantee of one of the presented algorithms matches the lower bound presented in [22] and is thus optimal.

(ii) the paper makes the conjecture -- which I find very interesting -- that clipping can also be used to overcome non-iid-ness when the functions on the $m$ workers are different (without resorting to variance reduction techniques such as SCAFFOLD or similar). However, this claim is only verified in one numerical experiment and the presented results are thus not yet conclusive enough to prove this claim.

strengths_and_weaknesses: The paper is well written and easy to follow. In terms of originality, it seems the paper combines the clipping technique from [22] with other known analyzes for local SGD/fedAvg. It would have been nice if the paper could have pointed out the technical difficulties a bit more to explain to the reader the significance of the contribution regarding these aspects. 

As mentioned above, I particular liked the discussion of the general heterogeneous setting as this seems to cover some novel aspects. Unfortunately, the evaluation fell a bit short.

The convergence results are presented from an asymptotic point of view and only hold for sufficiently large iteration counter $T$. I tried to estimate a lower bound on $T$: by the first two conditions stated in Theorem 1 on the term $\eta \eta_L K$, it must hold $\frac{c \ln T}{mK} \geq 1$, i.e. $T \geq e^{mK}$ when ignoring $c$. An exponential dependence on $m$ and $K$ seems very strong here, as the asymptotic regime might never be reached in practical settings where $m$ and $K$ are typically large. I was missing a discussion these limitations of the theoretical result. This strong dependence makes me doubt the practical relevance of the current theory (and might also hint that these results could probably be improved).

Calling Theorem 5 a theorem seems a bit overclaimed, as the result is a direct corollary of [22]. 

A theoretical analysis of the heterogeneous setting would strengthen the paper considerably and would allow the contribution to be clearly distinguished from previous work.
questions: - it is not so evident that $c$ is constant. (The expression that $c$ must satisfy depends on parameters like $T,K$, etc.). Please show here that $c$ is indeed constant.

- why does the paper introduce two algorithms (PR, PI), when apparently one is dominated by the other (at least in theory). Please make it more clear what would be the advantages of using the suboptimal algorithm in practice (or why it is included in the paper).

- to get the correct dependency on $K$ for the case $\alpha = 2$ a separate proof is needed (Theorems 6&7). One could expect to recover the result by letting $\alpha \to 2$, which is not the case. Is this an artefact of the proof, or is there a deeper reason that the case $\alpha < 2$ is behaving differently?

- how is the parameter $\alpha$ estimated in Figure 2? Please explain the method.
limitations: Already mentioned above that limitations of theoretical results, and practical guidelines for choosing PR vs. PI could have been emphasized better.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: It has previously been shown that cross-device federated learning (FL) can exhibit unstable convergence and experiences a sudden catastrophic failure. The current work posits that this instability is due to fat-tailed nature of the client updates. They provide some empirical evidence for this hypothesis, and proceed to show how to combine clipping with FedAvg to derive a new algorithm which converges under such fat tailed noise.
strengths_and_weaknesses: ## Strengths

1. The problem of unstable convergence is an important aspect, and the hypothesis that this may be a result of fat tailed noise is mathematically sound. Such noise would indeed explain the catastrophic failure seen in federated learning.

2. I very much appreciate the experiments in Section 3 (Figs. 1, 2, and 3) to establish the presence of fat tailed noise in FL. The setup is carefully thought through and indeed shows that fat tailed noise increasingly becomes a problem as heterogeneity increases. This explains why we see unstable training in non-iid setting, but not in an iid setup.

3. The algorithms derived to deal with fat tailed noise FAT-CPR (where the client pseudo gradient is clipped), and FAT-CPI (where each local update is clipped) are both intuitive and shown to have strong convergence guarantees as well.

4. The theory shows that FAT-CPI has a faster convergence rate than FAT-CPR. This is exactly reflected in practice as well where the former seems to perform better. Overall, FAT-CPI is a simple, intuitive algorithm which is provably more stable under fat tailed noise.

## Weakness

The paper does still leave a lot of questions unanswered however.

1. The estimated alpha in Fig. 2 seems to indicate that increasing the number of local steps makes the distribution less fat tailed. However, we know from experience that more local steps makes the convergence more brittle. In fact, Fig 2 seems to indicate that standard single-SGD is very fat tailed, but empirically converges without any issues. This is not discussed in the text.

2. Previous work on large cohort training [Z. Charles et al. 2021] shows that the updates seem to become orthogonal as we increase number of local steps. How does that explanation fit in with the current fat-tailed explanation? More generally, there is no investigation of why such fat tailed distributions seem to arise in federated learning.

3. Assumption 3 makes no distinction between the local variance within a client vs. variance across the clients due to heterogeneity. Thus, the theory is not useful to shed light on the effects on non-iid ness. Further, unlike previous work of [J. Zhang et al. 2020], the current work does not investigate adaptivity.

4. Finally, the experimental results are very limited - only CIFAR 10 with a CNN is tried. It is unclear how this observation and algorithm would generalize to other settings.



questions: Since this is an emergency review for which the authors may not be able to respond in time, I will only use this space to summarize my review.

Overall, this work proposes a new hypothesis of why non-iid-ness is challenging in cross-device federated learning - they claim it is due to fat tailed noise. While there is some preliminary evidence for this, the results are far from conclusive. Some of the authors' own experiments contradict this and further fat-tailed-ness does not explain other empirical phenomenon observed. Finally, there are places where both the experiments and the theory can be improved. 

Despite such shortcomings, the paper provides a valuable new perspective on FL and advances the conversation. I feel that these shortcomings are worth investigating by the community in future work. However, I **strongly recommend** that the authors to replicate their experiments on a few other datasets / models in the final version of their paper. I recommend acceptance trusting the authors to follow through on this.
limitations: No societal limitations.
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 observe that federated learning setting creates gradients that are fat-tailed and that these schemes are often marred by divergence of the training. They propose two gradient clipping schemes that aim to mitigate this, the difference being where the gradient clipping is applied. The authors present convergence results for the two algorithms. The authors compare their results with an existing algorithm on synthetic and CIFAR-10 data. 
strengths_and_weaknesses: Distributed learning schemes present crucial avenues of development for machine learning, especially with respect to topics such as privacy and scalability. Recent research on deep learning theory demonstrated the pervasive involvement of heavy-tailed distributed parameters and/or gradient noises in determining of various aspects of deep learning models such as convergence and generalization. Extension of these results to such crucial areas is an important endeavour. The most important contribution of the paper seems to the convergence rate results they present when their algorithms are used.

However I feel that the paper is insufficient in terms of both justifying the grounds for their methodology, as well as their effectiveness. This is also exacarbated by problems in the presentation which I will present below. The first problem is that the authors present insufficient evidence imprecisely when making a case for the existence of heavy tailed gradients in federated learning, and that these heavy-tailed gradient noise actually leads to divergence. The following questions remain unanswered or unclear in the text, which is problematic given the centrality of these matters for the article:

- How is pseudo-gradient noise calculated? How is the expected value for the pseudo-gradient computed during experiments?
- How does p relate to data heterogeneity exactly? How do we know it is a authoritative measure of data heterogeneity?
- Does Single SGD case refer to a normal training scheme in Fig. 2? If so, in what specific ways does a federated learning scheme differ from the known results of heavy-tailed noise in the literature?
- The authors use the divergence events as a motivation for gradient clipping. Is there a theoretical or empirical evidence to assume that the fat-tailed pseudogradient noise necessarily cause or even is statistically associated with divergence? The results on heavy-tailed parameter / gradient statistics in deep learning show that not only that this is not the case, but that heavy-tailed parameter / gradient statistics lead to better generalization.
- The authors analyze the pseudogradient noise and find it to be heavy-tailed. Do we know the tail index statistics of the expected-pseudogradient? (which can itself be heavy-tailed.)
So much so that it is not clear in the text distribution of which variable they are addressing. , the authors do not explicitly specify how they compute the pseudo-gradient noise (e.g. how do they compute the expected pseudo-gradient). The experiments in Fig. 1 and 2 seem 

In addition to problems in the justification of the method, the authors do not demonstrate enough empirical evidence to show that their method is superior. The experiments are very small scale - the largest experiment setting only includes 5 trials for each setting. Given the weak evidence regarding the existence and/or the effects of heavy tailed gradient noise in federated learning, extensive empirical evidence can be expected to verify that the authors' methods are viable and advantageous. Especially important is the following question:

- Given the benevolent effects of heavy-tailed parameter statistics in deep learning, how do we know that the claimed advantages of the presented clipping schemes do not come with a negative effect on generalization performance?
- Given the importance of training hyperparameters in presence or absence of heavy-tailed parameter/gradient noise, how do the authors results change with respect to hyperparameters such as learning rate or batch size?

I would recommend a much more involved discussion of at least some of the questions presented above and as well as more extensive introduction to authors' terminology (e.g. the authors never explicitly state that x are their parameter vector.) The authors relegate some content to supplamentary material for lack of space: I believe a lot of space can be gained by not repeating Algorithms 2 and 3, and instead just describing the clipping operation in the text, referring to the original algorithm.
questions: I presented my questions within my assessment of the paper above.
limitations: The authors present very little discussion of the weaknesses of their approach, which I think is not appropriate given the discussion presented above.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: In this paper, the authors discussed the problems of the presence of fat-tailed noise in the stochastic gradient noise in the federated learning algorithm. The authors provided the empirical results that fat-tailed gradient noise can be induced by data heterogeneity and local update steps in the federated learning algorithm. And the fat-tailed gradient noise will lead to catastrophic training failures when applying GFedAvg algorithm. In order to fix that problem, the authors developed a clipping-based algorithmic framework called GAT-Clipping and provided the convergence rate bound of the algorithm.
strengths_and_weaknesses: Strengths:
1) The paper is well-written and easy to follow the idea of the paper.
2) Related works have been fully discussed.
3) The idea is interesting and the proof of the theorem is solid.

Weakness:
1) The experiments are not enough to verify the claim.
questions: 1) In the assumption the \alpha is defined between 1 and 2. But in the experiments of Figure 5, \alpha=0.5, which violates the assumption.
2) In both FAT-Clipping-PR and PI, there is an extra hyperparameter \lambda, and in the experiment part the value of \lambda is not mentioned. How to choose a proper \lambda value, is it related to the value of \alpha? If so, when we start the training, \alpha is not known, then how to choose \lambda.
3) The current experiments are not enough to validate the claim in the paper. Maybe providing extra experiments result can help the validation of the paper.
limitations: Yes, the authors adequately addressed the limitations and potential negative sociteal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers tackling fat-tailed noise in in federated learning, where the local gradients may not even have finite covariance. It is shown that in both theory and experiments, prior approaches can fail in this setting. The paper provides a simple solution to this problem by clipping the local updates. On the theory side, they show that the algorithms achieve near optimal convergence. The paper also provides numerical experiments to validate their results.
strengths_and_weaknesses: Strengths
----
The paper is generally well-written. 

The main approach of the paper is simple and can be easily implemented in practice. 

I have not checked the proofs in appendix, but the main theorem claims are strong, in the sense that they are optimal in $T,m$.

Weaknesses
---
It may be argued that the main algorithmic technique of this paper is not novel. It is mostly applying a known idea (clipping) to this problem. 

Comparing the upper bound Theorem 1,2 and lower bound Theorem 5, the paper does not achieve optimal rate in terms of $K$, though the dependence on the more important factors of $T$ and $m$ is tight. 

Minor 
---
Line 252: constructing the lower fundamental bounds -> proving the following lower bounds

questions: It seems that the algorithms require knowledge of $\alpha$? (I noticed that $\lambda$ and $\eta$ settings in Theorem 1,2 both require $\alpha$) Is that an assumption that we can get rid of? Alternatively, what would be a good heuristic to set $\alpha$ in practice?
limitations: I do not see where the author(s) addressed the limitations of their work. 

Federated learning itself may have potential negative societal impact, but I do not consider this work particularly risky in that regard. It's mostly theoretical.
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: This paper considers federated learning with stochastic gradient-based algorithms being run on each local machine, where the gradients may be potentially heavy-tailed in the strong sense that only a bounded $\alpha \in (1, 2]$ moment assumption is placed on the random gradient norms. Since traditional analysis of SGD makes use of bounded second moments, the authors consider the general technique of norm-clipped gradients, with two variants, namely clipping at each local iteration (per-iteration, PI variant), and clipping just before integrating the parameters from all local machines to the central server (per-round, PR variant).

The main contributions are theoretical. Their main results are in the form of excess error bounds in the strongly convex case, and approximate stationarity guarantees in the non-convex case, for both the PR and PI variants. As it turns out, clipping at each local iteration turns out to be the "better" strategy in terms of overall dependence on the number of samples used, an intuitive result, since without controlling the gradients at each iteration in the local processes (even with finite variance), we can say very little about what we'll get from the $K$ non-clipped local updates, and thus given the resolution of the standard analytical tools, such updates are essentially wasted. The authors share some lower bounds which give some perspective on these results, and complement their theory with some empirical tests that highlight the impact of the gradient noise on the convergence rate of each procedure. The overall story has "FedAvg" as the standard algorithm against which performance guarantees are compared, and the final message is that the PI variant is the natural robustification of FedAvg, since it recovers the rates achieved by FedAvg in the $\alpha = 2$ case.
strengths_and_weaknesses: Overall, the paper is well-written, the main assumptions, learning algorithm details, and key results are stated clearly, and given a concise but transparent discussion. The empirical test results, while basic, do provide a very clear example highlighting how the degree of noise makes a big difference in the PR case, whereas the PI variant is less sensitive.

On the other hand, I had some concerns about how this work compares with some of the past literature on robust stochastic gradient methods. For example:

> High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails, Ashok Cutkosky and Harsh Mehta, NeurIPS 2021

In this previous work, the setting is "centralized" (i.e., just one machine, rather than $m >1$ clients), but the authors obtain results for the non-convex, smooth objective case with $1 < \alpha \leq 2$ moment bounds on the stochastic gradients. These results hold with high probability, and can be shown to hold for the last iterate. The algorithm used takes advantage of clipping, normalizing, and momentum. As such, the state of the art for the centralized, smooth, non-convex, fat-tailed gradient learning problem has high-probability guarantees without random stopping. In comparison, the current work has results in expectation with random stopping (or the unknown best candidate). There seems to be a gap here, and I wonder if it is an unnecessary gap?

For example, set $K=1$, run the C and M (2021) sub-routine to process the noisy gradients from each local machine, and then average over these $m$ robust gradient estimators and update the central server parameters as in the current FAT-Clipping-* procedures. Or, alternatively, average over the non-clipped local gradients and then run the C and M robustification procedure before updating the central parameters. This latter case seems like it is just the C and M procedure with a mini-batch, and one would expect this to yield high-probability guarantees (I have not checked this carefully).

Of course, I know that in the federated learning setting we want the local machines to do the bulk of the work for us, and thus we'd like to take both $m > 1$ and $K > 1$ large; can we not modify the above robust procedure with $K=1$ to deal with the $K>1$ setting? If not, why not? The interplay between algorithmic decisions and the guarantees we can obtain are precisely the point of interest when moving from centralized to federated learning, and yet I feel these questions are sort of swept under the rug in the current analysis.

By the way, it is unclear to the reader if the error bounds in the convex case (e.g. Thm 1) are in expectation or are high-probability. 

To summarize, it seems like the current paper is somewhat narrow-sighted in terms of the aggregation procedures (and the local procedures, for that matter) being considered, and state-of-the-art guarantees in the one-machine setting, which makes it somewhat difficult to evaluate the significance of this current work.
questions: Please consider the points I raised in the previous field; if I have misconstrued the scenario considered in this paper, or misread any results, please let me know.

**Update:** the authors have clarified some concerns I had, and I have revised my score.
limitations: Overall, the authors are clear about what they intend to prove, what they do prove, and how the learning procedures tend to be have in practice.
review_title: null

Meta-review: metareview: This is a borderline paper, and we ended up soliciting two additional reviewers (4F3m and Eovh) for additional feedback after the main review/author discussion period. 

The general sentiment shared by the reviewers (including the two additional ones) is that the paper studies an interesting/important problem and provides some interesting discussion and results -- albeit largely based on natural extensions of existing methods (e.g. in the centralized setting). Some of these results could also be improved (both in terms of better discussion on novelty and just stronger guarantees), but the reviewers generally appreciate that the authors have started discussion and work in this area. 

Multiple reviewers think that the hypothesis relating non-iidness with fat tailed distributions is interesting, but are underwhelmed by the supporting analysis and commentary. It would be great if the authors could improve this discussion, either with more concrete analysis or with better empirical evidence.

The biggest criticism of this paper that is shared by most if not all of the reviewers is that the current experimental section is severely lacking. The authors mentioned that they would add in more experiments in the final draft of the paper (e.g. https://openreview.net/forum?id=8SilFGuXgmk&noteId=ShuBB-7e3B-). This response seemed satisfactory to the reviewers, so this paper will be accepted based on the premise that the authors will follow up on that promise. In particular, it is expected that the authors will go over the reviews and try to carefully address all comments about the experiments (e.g. replicating experiments on at least a few other datasets and models -- ideally at larger scale, using experiments to better verify the non-iid hypothesis, designing experiments that verify the theoretical guarantees). 
confidence: Certain
Decision: Accept