The Vital Role of Gradient Clipping in Byzantine-Resilient Distributed Learning
Byzantine resilience;distributed machine learning
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
* 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?
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.
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.
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.
Yes
No ethics review needed.
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
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.
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.
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.
Yes
No ethics review needed.
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?
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.
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.
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.
@inproceedings{
anonymous2024the,
title={The Vital Role of Gradient Clipping in Byzantine-Resilient Distributed Learning},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=03OkC0LKDD},
note={under review}
}
Byzantine-resilient distributed machine learning seeks to achieve robust learning performance in the presence of misbehaving or adversarial 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, the currently considered static
clipping strategy 
exhibits mixed results: improving robustness against some attacks while being ineffective or detrimental against others.
We address this gap by 
proposing a principled adaptive clipping strategy, termed Adaptive Robust Clipping (ARC).
We show that ARC consistently enhances the empirical robustness of SOTA Robust-DGD methods, while preserving the theoretical robustness guarantees. 
Our analysis shows that ARC provably improves the asymptotic convergence guarantee of Robust-DGD in the case when the model is well-initialized.
We validate this theoretical insight through an exhaustive set of experiments on benchmark image classification tasks.
We observe that the improvement induced by ARC is more pronounced in highly heterogeneous and adversarial settings.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Byzantine resilience distributed machine learning
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/1edff0639d6d0d7f61b9422fb9b09ffc1b65c0b2.pdf
optimization
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
/attachment/3789db05085a506e826567c48ddd96568a104516.zip
The Vital Role of Gradient Clipping in Byzantine-Resilient Distributed Learning
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission