Adaptive Gradient Clipping for Robust Federated Learning

Authors: Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Ahmed Jellouli, Geovani Rizk, John Stephan
Primary area: optimization
Keywords: federated learning, robustness, byzantine resilience

Abstract:
Robust federated learning aims to maintain reliable performance despite the presence of adversarial or misbehaving workers. While state-of-the-art (SOTA) robust distributed gradient descent (Robust-DGD) methods were proven theoretically optimal, their empirical success has often relied on pre-aggregation gradient clipping.
However, existing static clipping strategies yield inconsistent results: enhancing robustness against some attacks while being ineffective or even detrimental against others.
To address this limitation, we propose a principled adaptive clipping strategy, Adaptive Robust Clipping (ARC), which dynamically adjusts clipping thresholds based on the input gradients. We prove that ARC not only preserves the theoretical robustness guarantees of SOTA Robust-DGD methods but also provably improves asymptotic convergence when the model is well-initialized. Extensive experiments on benchmark image classification tasks confirm these theoretical insights, demonstrating that ARC significantly enhances robustness, particularly in highly heterogeneous and adversarial settings.

Decision: accept (spotlight)
Reviewer scores: 8, 6, 8, 8

Reviews and discussion:
<thread>
creation date:
1729623635506

thread_type:
official_review

<thread_object>
creator: reviewer_n1gk

<content>
summary:
The authors introduce a variation on the static clipping technique used to overcome byzantine attacks in federated learning. Their algorithm makes the process dynamic by adapting the clipping value to the input gradients themselves; this algorithm, called ARC, or Adaptive Robust Clipping, is proved to be robust: (f, 3k)-robust. More importantly, the authors prove that static clipping breaks the standard (f,k)-robustness, which highlights the shortcomings of the empirical results demonstrated in the papers highlighted in paragraph five of the Introduction. These reasons motivate the need for a dynamic approach to gradient clipping. ARC was paired with and tested using the following techniques: coordinate-wise trimmed mean, geometric median, multi-Krum, and nearest-neighbor mixing. Various simulations were ran by the authors to show the utility of ARC, these include: simulations on varying degrees of data heterogeneity, simulations on varying f (the number of malicious agents), simulations showing the improved breakdown point. All of these simulations show how ARC can provide robustness.

A current problem point is that the authors perform simulations and demonstrate against not using gradient clipping. In paragraph 5 of the Introduction, the authors clearly state that static methods are a problem that their approach, ARC, solves. Then, the authors proceed to perform simulations and do not compare their results against static clipping, but compare against no clipping. It is known, and evidenced by the cited work, that not clipping is a problem that is overcome by using some form of clipping. Therefore, results compared against not clipping yields no additional information. While the authors have shown that ARC has obvious utility that could help overcome known issues, readers cannot determine the excess utility over using static clipping. While I believe the paper holds merit, as the empirical results show, I do not believe the paper can proceed without the authors running the experiments again and showing the results with static gradient clipping. The comparison between static and dynamic clipping is the fundamental point of the paper and not having a comparison of the two makes the paper unqualified to proceed. If the authors can show those results, so readers, such as myself, can see how much improvement is gained by using a dynamic choice for clipping, then I believe the paper will contain enough merit to be accepted and to receive a higher score.

As a final, syntactic, comment, I believe the authors should move the Related Works section to an earlier spot in the paper so readers can more easily understand the historical context and how the motivation for the novel work. This swap will increase flow of understanding for the reader who will have to exert less mental effort to juggle the chronological and intellectual pieces together.

strengths:
The paper introduces dynamic gradient clipping as an improvement to its static counterpart. More importantly it proves that the static approach is not robust, in accordance with the definition of robustness given in the paper. Furthermore, the authors prove the robustness of their approach and provide empirical evidence of the utility of their algorithm.

weaknesses:
The major weakness of the paper, which is a critical one, is the complete lack of comparison of ARC versus static clipping. The authors run experiments against not using clipping; this is rendered moot by prior work and therefore is not a necessary point of comparison. The authors must go back and run the same experiments they ran with with static gradient clipping and plot that against their dynamic approach. Without doing this, it is not possible to determine the benefit their work over prior work.

questions:
1) Why were no experiments ran using static clipping?
2) What is the reason for only using a network with 10 agents? Typically, networks with more agents that test for heterogeneity have a harder time than those with networks because there is a wider gap on intra and inter-class datasets.
3) What was the reason for selecting 17 agents for the simulations in the section "Improved robustness on CIFAR-10"? Can you expand to more agents?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730494363564

thread_type:
official_review

<thread_object>
creator: reviewer_ap5t

<content>
summary:
This paper explores enhancing the robustness of distributed machine learning in the presence of Byzantine clients. The authors propose  Adaptive Robust Clipping (ARC) that improves the robustness of Robust-DGD beyond traditional static clipping techniques. ARC dynamically adjusts clipping thresholds based on gradient magnitudes, allowing it to better counteract adversarial impacts.
The authors provide experiments to demonstrate that ARC improves model robustness against various attacks compared to static clipping methods as well as theory showing that ARC has a similar convergence rate as the classical ones known in the literature.

strengths:
The main strengths are: 

-The authors propose Adaptive Robust Clipping (ARC), a new mechanism to enhance robustness in adversarial settings.

-The authors show that ARC almost retains the theoretical robustness guarantees of existing Robust methods while enhancing their practical performance. 

-The authors validate ARC through several experiments.

weaknesses:
The main weaknesses are:

-Increased complexity produced by ARC in practical implementation

-ARC performance depends on good model initialization which may degrade the performance in the case of poor initialization.
Did you try some experiments to assess this?

-While ARC improves robustness by adaptively clipping gradients, its thresholding could risk clipping too aggressively in certain settings, potentially discarding useful gradient information.

questions:
See section before. 

In addition:

-In Figure 1, C=2 for static clipping (SC) is too small. I think that is why you have a very bad performance of SC. You need to test with bigger values of C as well for SC.

-Can you report the Adaptive C of ARC over steps in these plots?

- Line 94, can you justify why one needs to clip this exact k number gradients? what happens if one clip less or more than this number of gradients?

-The intuitive k is the number of potential malicious workers which is f?

-Line 238, you require \kappa B^2 < 1, (which means B should be small) can you give an example of loss where B is small?

-Line 264, I disagree with the comment that "ARC does not introduce a significant overhead" especially in the case of large models. It will be good to have some experiments with runtime on the x-axis  

-ARC theory requires that the model is well-initialized, it will be good to assess numerically the impact of the initialization on the performance of ARC
</content>
</thread_object>

</thread>
<thread>
creation date:
1730577684721

thread_type:
official_review

<thread_object>
creator: reviewer_zvxn

<content>
summary:
The paper introduces an adaptive gradient clipping method applied to worker outputs before passing them through a robust aggregator in heterogeneous synchronous Byzantine settings. The authors address a practical issue, as they observe that while fixed gradient clipping can enhance performance in some cases, it may also impair it in others. To ensure robustness while utilizing gradient clipping, they propose an adaptive strategy that adjusts the clipping threshold according to the magnitude of worker outputs, applying clipping selectively to only a subset of them. Experimental results across various Byzantine scenarios and robust aggregators, tested on MNIST and CIFAR-10 datasets, demonstrate the effectiveness of this adaptive approach when combined with the established NNM method. The authors further support their method with theoretical guarantees.

strengths:
The paper proposes an adaptive method that maintains the robustness guarantees of the aggregators it employs while improving their practical performance, especially under high heterogeneity. The authors provide valuable insights into selecting the clipping threshold, demonstrating that a fixed threshold for all workers, commonly used in practice, may be inefficient in some cases and does not meet robust criteria. They also emphasize the gap between Byzantine theory and practical applications, highlighting that existing theory may not fully capture real-world performance.

weaknesses:
Considering the critical role that numerical evaluation plays in supporting the paper’s claims,
* The paper introduces an adaptive clipping approach designed to work with any robust aggregator independently of NNM. However, the numerical results primarily showcase its effectiveness only when combined with the NNM aggregator (and it is unclear if NNM was also used in Figure 6; if so, this single example may be insufficient). Since NNM has a computational complexity of $O(dn^2)$, it would be valuable to assess the performance of this approach with other robust aggregators (without integrating NNM) to explore potentially lower computational costs. For instance, the CWTM ($O(dn \log{n})$) or the $\epsilon$-approximation GM ($O(dn + d\epsilon^{-2})$) might offer alternatives that may retain robustness in practice while reducing time complexity. Conducting such experiments could provide a more comprehensive evaluation and emphasize the approach’s practicality.
* The CIFAR-10 evaluation is somewhat limited, with only one Byzantine worker out of 17. Expanding the evaluation to include a higher proportion of Byzantine workers and testing on more complex datasets could better demonstrate the method’s effectiveness in more practical scenarios.

questions:
* How does NNM contribute to achieving the guarantees outlined in Theorem 5.2? Is it possible to attain similar results on robust aggregators without incorporating NNM?
* Using a fixed clipping threshold can often be effective in homogeneous Byzantine settings. How does the adaptive approach perform compared to a fixed threshold in such cases?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730723895167

thread_type:
official_review

<thread_object>
creator: reviewer_kaqt

<content>
summary:
This paper proposes a novel strategy called Adaptive Robust Clipping (ARC) for Byzantine-resilient distributed machine learning. Empirical results show that using ARC can significantly enhance Byzantine resilience compared to the methods without clipping. Theoretical analysis of convergence is also provided to show the effect of ARC.

strengths:
1. This paper is generally well-written. 
2. The idea of adaptive clipping intuitively makes sense and has an excellent empirical performance in the experiments of this work.
3. Byzantine resilience in distributed learning is an important and timely topic.

weaknesses:
Although the proposed ARC strategy is generally not hard to implement and has a good empirical performance, there are major concerns about the theoretical analysis in this paper, which I specify point by point below. 

1. The theoretical results in section 3 show that $F\circ ARC$ is $(f,3\kappa)$-robust when $F$ is $(f,\kappa)$-robust (Theorem 3.2). Although the property of $ARC$ is much better than trivial clipping (as shown in Lemma 3.1), the convergence guarantee obtained from Theorem 3.2 for $F\circ ARC$ is worse than that for $F$ (without $ARC$). In other words, the theoretical results in section 3 show that $ARC$ has a better property than trivial clipping, but do not show that using $ARC$ can improve the convergence guarantees.

2. The improvement of convergence guarantees for $ARC$ is mainly shown by Theorem 5.2. Theorem 5.2 says that when the maximum gradient norm of the initial point is not larger than $\zeta$, using $ARC\circ F$ can guarantee to find a point $\hat{\theta}$ such that the square norm of the gradient at $\hat{\theta}$ is not larger than $v \epsilon_0$ in expectation. However, $v \epsilon_0$ can be much larger than $\zeta^2$ (which is specified in the next paragraph). Briefly speaking, the result of Theorem 5.2 can be even weaker than the conditions, which makes the theorem meaningless.  
- Since $\xi \leq \min(\frac{v}{\Phi(G,B,\rho)},\xi_0)$, it is obtained that $\xi \leq \frac{v}{\Phi(G,B,\rho)}$, and thus $v\geq \xi \cdot \Phi(G,B,\rho)=\xi\cdot 640(1+\frac{1}{B^2})^2(1+\frac{B^2\rho^2}{G^2}).$ Therefore, 
$v\epsilon_0 \geq [\xi\cdot 640(1+\frac{1}{B^2})^2(1+\frac{B^2\rho^2}{G^2})]\cdot[\frac{1}{4}\cdot\frac{G^2(f/n)}{1-(2+B^2)(f/n)}].$ The term $\rho^2=\exp (2\frac{(2+B^2)\Delta_0}{(1-\xi_0)G^2}L)\zeta^2$ can be much larger than $\zeta^2$. Thus, $v\epsilon_0$ can be much larger than $\zeta^2$, which will make Theorem 5.2 meaningless.

Overall, the idea of ARC is interesting. The ARC method is easy to implement and has a good empirical performance. However, the theoretical analysis in the current version does not show the improvement of convergence guarantees, and can be misleading.

questions:
Please focus on the weakness of Theorem 5.2 in the rebuttal. Specifically, please compare the value of $v\epsilon_0$ with $\zeta^2$ in Theorem 5.2 (or address the concern in some different ways). I am willing to raise the score if the concerns are properly addressed.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731923374969

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

We are pleased to inform you that the additional experiments requested have now been completed. These experiments, which address the specific points raised in the reviews, have been incorporated into the revised version of the paper. For ease of reference, we have included these results in Appendix G, and highlighted all additions and revisions in blue.

The new results further reinforce the claims made in the paper and provide additional clarity on the robustness and adaptability of ARC in various settings. We encourage you to review these updates and welcome any further comments or suggestions you may have.

Thank you once again for your time and consideration.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732707660956

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We sincerely thank all the reviewers for their constructive comments and insightful suggestions. Your feedback has been invaluable in improving the quality and clarity of the paper.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new method for adaptive gradient clipping in Byzantine-resilient distributed setting. It provides both theoretical and empirical support for the method. The discussion during the rebuttal for this paper centered on theoretical rigor, experimental breadth, and practical applicability of Adaptive Robust Clipping (ARC) in Byzantine-resilient distributed learning. Reviewers raised concerns about the limitations of the theoretical guarantees, particularly in highly adversarial regimes, the dependence of ARC on robust initialization, and the lack of direct comparisons to static clipping in the main text. Authors addressed these points by providing detailed clarifications on theoretical underpinnings, incorporating additional experiments comparing ARC to static clipping, and demonstrating ARC's scalability through new larger-scale experiments. Finally, all reviewers were very positive and hence I recommend acceptance.