Adaptive Gradient Clipping for Robust Federated Learning
Authors: Youssef Allouah
Rachid Guerraoui
Nirupam Gupta
Ahmed Jellouli
Geovani Rizk
John Stephan
Venue: ICLR 2025 Spotlight (2025)
Keywords: Federated learning
robustness
Byzantine resilience
Primary area: optimization

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.

Published as a conference paper at ICLR 2025
ADAPTIVE GRADIENT CLIPPING FOR ROBUST FEDER- ATED LEARNING
Youssef Allouah
Rachid Guerraoui'
Nirupam Gupta²
Ahmed Jellouli!
Geovani Rizk
John Stephan -f
EPFL, Switzerland
University of Copenhagen, Denmark
Correspondence to: john. w...........n...... wwwpssssephanepp..cccmm
ABSTRACT
Robust federated learning aims to maintain reliable performance despite the pres- ence of adversarial or misbehaving workers. While state-of-the-art (SOTA) robust distributed gradient descent (Robust-DGD) methods were proven theoretically op- timal, their empirical success has often relied on veeaaggegation 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 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 experiments on benchmark image classification tasks confirm these theoretical insights, demonstrating that ARC significantly enhances robustness, particularly in highly heterogeneous and adversarial settings.
Extensive
INTRODUCTION
Distributed machine learning, a.k.a. federated learning, has emerged as a dominant paradigm to cope with the increasing computational cost of learning tasks, mainly due to growing model sizes and datasets (Kairouz et al. 202I). Worker machines, holding each a fraction of the training dataset, collaborate over a network to learn optimal common model over the collection of their datasets. Workers typically collaborate with the help of a central coordinator, that we call server (McMahan al. 2017). Besides scalability, distributed learning is also helpful in preserving data ownership and sovereignty, since the workers do not have to share their local datasets during the learning.
Conventional distributed learning algorithms are known to be vulnerable to misbehaving workers that could behave unpredictably (Blanchard et al. 2017 Kairouz et al. 2021 Guerraoui et al. (023). Mishehavior may result from software and hardware bugs, data poisoning. controlling part of the network. In the parlance of distributed computing, misbehaving workers are referred as Byzantine (Lamport et al.) 1982). Due to the growing influence of distributed learning in critical public-domaie applications such as healthcare (Nguyen et al.) 2022) and finance (Long jt al., 2020), the problem of robustness to misbehaving workers, k.a. robust distributed learning. has received significant attention (Yin et al. 22018 Farhadkhani et al. 2022 Karimireddy et al. 2022
malicious players
Gorbunov et al. 2023 Allouah et al. 2023a; Farhadkhani et al. 2023 El-Mhamdi et al. 2023).
Robust distributed learning algorithms primarily rely on robust aggregation, such coordinate- wise trimmed mean (CWTM) (Yin et al. 2018). geometric median (GM) (Chen et al. 2017) and Multi-Krum (MK) (Blanchard et al, 2017). Specifically, in robust distributed gradient descent (Robust-Due DDD), the server aggregates the workers' local gradients using a robust aggregation method, instead of simply averaging them. This protects the learning from erroneous gradients sent by misbehaving workers. Recent work has made significant improvements over these aggregation techniques by incorporating pre-aggregation step such bucketing (Karimireddy et al.) 20022 Gorbunov et al. 2023) and nearest-neighbor mixing (NNM) (Allouah et al. 2023a), to tackle gradient
Authhors listed in alphahetical order.

---

Published as a conference paper at ICLR 2025
dissimilarity resulting from data heterogeneity. The learning guarantee of the resulting Robust-DGD has been proven optimal (Allouah et al., (223b), i.e., it cannot be improved without additional assumptions under the standard heterogeneity model of BG) BB)-gaddeeet dissimilarity (Karimireddy et al. 2020).
Despite its theoretical tightness, the empirical success of Robust-DGD has unknowingly relied on pre-aggregation gradient clipping (Mhamdi et al.] 2021 Farhadkhani et al. 2022 Allouah et al.) 2023a). Specifically, clipping the gradients of the workers prior to aggregation has been observed to sometimes enhance the algorithm's empirical performance in the presence of adversarial workers (as evidenced in Figure 7a). Yet, this improvement lacks a concrete explanation, raising the question of whether the observed benefits of clipping are merely anecdotal. This leads to the natural inquiry: Why, and when, does pre-agg pre-aggregation clipping improve robustness?
In particular, using constant clipping threshold, referred to as static clipping, has exhibited mixed results. Figure shows that while static clipping effectively mitigates sign-flpping (SF) attacks, it completely fails under label-flipping (LF). This indicates inherent fragility of static clipping. Indeed, we prove in our work that static clipping breaks the standard (J, robbusstssssss property of an aggregation method (Allouah et al., 2023a). This highlights key shortcoming of existing empirical results that rely on static clipping (Mhamdi et al., 2021| Farhadkhani et al., 2022 Allouah et al., 2023a). To overcome the limitations of static clipping but preserve its empirical benefits at the same time, we introduce a novel adaptive clipping scheme, termed Adaptive Robust Clipping (ARC).
ARC dynamically adjusts the clipping threshold per the gradients sent by the workers and the fraction of adversarial workers to be tolerated. We demonstrate that integrating ARC into Robust- DGD consistently improves its empirical performance (see Figures 7 and [a]. while also preserving the convergence guarantee of the original Robust-DGD algorithm. Moreover, we show that when the model initialization is good, ARC provably improves the robustness of Robust-DGD The benefits of ARC are more pronounced as the fraction of misbehaving workers approaches the system's ' breakdown poin and when the data across the workers is highly heterogeneous. Our key results are summarized below. Critical comparisons to prior work are deferred to Section 6
100
COTN 1ae
202
Cel LIDE ANN
02
Test Accuracy
60
42
22
0-
Number adversa workers
Intstiatioo Scxing Pette
(a) Improved robustness
(b) Influence of model initialization
Figure 1: Worst-case maximal accuracies of Robust-DSGG with and without ARC, across several types of misbchavior for distributed MNIST with 10 honest workers and under extreme heterogeneity, On the left, we vary the number of adversarial workers. On the right, we vary the initialization conditions by scaling a well-chosen set of initial parameters (CWTM o NNM is used, and f = 1). More details on the experimental setup can be found in Sections 3 and 5.2 and Appendix D
Main results& & contributions. We consider a system comprising n workers and a server. The goal is to tolerate up to f adversarial workers.
(I) Adaptive robust clipping (ARC). We propose ARC, wherein prior to aggregating the gradients, the server clips the largest k == 12( (n - f)] gradients using a clipping parameter given by the (Euclidean) norm of the (I: + 1) largest gradient. It is important to note that in contrast to existing adaptive clipping schemes (Diakonikolas et al.) 2020; Abdalla & Zhivotovskiy 2024), ARC does not require additional a priori information on honest workers' gradients. We prove that ARC preserves the robustness guarantee of the original robust aggregation method.
(2) Improved empirical robustness. We conduct experiments on MNIST (Deng 2012). Fashion- MNIST (Xiao et al. 2017), and CI (Krizhevsky et al. 2014), across various data heterogeneity
Breakdown point refers to the minimum fraction of adversarial workers that can break the system, making it impossible to guarantee bound on the learning error (Allouah et al. 20236
2

---

Published as a conference paper at ICLR 2025
settings and adversarial regimes. Our results demonstrate that ARC significantly enhances the performance of thtt-arft Robust-DGD methods, particularly in scenarios with high data heterogeneity (Figure Tap and a large number of adversarial workers (Figure 4b
(3) Improved learning guarantee. We demonstrate that ARC possesses an additional property that is not satisfied by classical robust aggregation methods. Specifically, ARC constrains the norm of an adversarial gradient by that of an honest (non-adversarial) gradient. Leveraging this property, we show that ARC circumvents the lower bound established under data heterogeneity in Allouah et al. (2023b), provided the honest gradients are bounded at model initialization. An empirical validation of this insight shown in Figure Ib] Such model initialization is often satisfiable in practice (Glorot Bengio 2010), highlighting the practical relevance of ARC. When the model is arbitrarily initialized, ARC recovers the original convergence guarantee of Robust-DGD the worst case.
PROBLEM STATEMENT AND RELEVANT BACKGROUND
We consider the problem of distributed learning in the server-based architecture. The system com- prises n workers represented by wi,.... Wn that collaborate with the help of trusted server. The workers hold local datasets DI...., D, respectively, each composed of m data points from an input space Z. Specifically, for any E [n). D. {21
(0) } C Z For given model parameter- ized by vector 0 E RRd d being the number of trainable parameters, each worker we incurs loss given by (0) == 1 Σm= E(0, 2()) where : R x + R is the point-wise loss. We make the m
following standard assumptions (Bottou et 2018): (i) the point-wise loss function is differentiabe
with respect to 0. (ii) For all i E n1. 2, is T.-L- ipschitz smooth, i.e., there exists E R+ such that for 1 0']l, where || refers to the Euclidean norm. In the ideal setting where all workers are honest, i.e., follow the prescribed algorithm correctly, the server aims to minimize the global average loss function given by [())= 1 Σ L3 (0). However, this objective is rendered vacuous when some workers could be adversarial, described in the following.
all 0, 0' E Rdd (0) (0))l
robust distributed learning algorithm aims output a good model despite the presence of adversarial (a.k.a., Byzantine) workers in the system (Su & Vaidya 2016 Yin et al. 2018 Allouah et al. (023a). Specifically, the goal is to design distributed learning algorithm that can tolerate up to / adversarial workers, of priori unknown identity, out of n workers. Adversarial workers need not follow prescribed algorithm, and can send arbitrary information to the server. In the context of distributed gradient descent, adversarial workers can send incorrect gradients to the server (Baruch et al.) 2019 Xie et al., 2020). We let C [r]]. with |H| = n - -f, denote the set of honest workers that do not deviate from the algorithm. The objective of the server is to minimize the average loss function of honest workers given by (f) = [H] Σien (0), A0 E Rdd While we can find a minimum of Cx((0) when Lu is convex, in general however the loss function is non-convex, and the optimization problem is NP-hard (Boyd & Vandenberghe 2004). Therefore, we aim to find a stationary poins of Lu instead, i.e., 8¹ such that [V
O. Formally, we define robustness to adversarial workers by (ʃ, -reexilienc (Allouah et al. 2023a).
Definition 2.1. A distributed learning algorithm A is said to be (f, (f,e)-resilient if, despite the presence
of f adversarial workers, A enables the server to output a model 0 such that EE
V VL Lx (0)
(1) Se
where the expectation E [-] is over the randomness of the algorithm.
If distributed learning algorithm AA is (f, -ressiiet, then it can tolerate up f adversarial workers. It is standard in robust distributed learning to design robust algorithms using f as a
parameter (Blanchard al. 2017 Yin et al. 2018 Gorbunov al. 2023 Allouah et al. 2023a).
In the context of distributed learning, data heterogeneity is characterized by the following standard no-
tion of (G, B) -raaddiett dissimilarity (Vaswani et al. 2019 Karimireddy al. 2020 2022 et al. 2023 Allouah et al. 2023b))
Gorbunov
Definition 2.2. Loss functions C,, E H. are said to satisfy (G, -)-grdiient dissimilarity if,
-V CC)(0) < G² + B² [VL(()) VO e Rd.
[ NE
General limitations on robustness. Note that (f. e) resiliene is impossible (for any E) when f/n 2 1/2 (Gupta & Vaidya 2020). Moreover, even for f/n- < 1/2, it is generally impossible
3

---

Published as a conference paper at ICLR 2025
to achieve (f, z) rresilinne for arbitrarily small due the disparity amongst the local datasets Di, iE H (a.k.a., data heterogeneity) (Liu et al. (021). Henceforth, we assume that n > 2f. Under (), -grrddintt dissimilarity, we have the following lower bound on the achievable resilience.
Lemma 2.3 (Non-convex extension of Theorem 1 Allouah a..). Under (G, (..BB)--radaa -3r-giddinnt dissimilar-
ity, a distributed learning algorithm is (f, --resilienn only if ! n 24 and & 2 2 n- G?.
1
For given distributed learning problem, the minimum fraction of adversarial workers that renders any distributed learning algorithm ineffective is called the breakdown point (Guerraoui al. 2023)
Allouah et al., 2023b). Thus, according to Lemma 2.3 there exists distributed learning problem satistying (G, B) -rradiettt dissimilarity whose breakdown point is given by 1/(2 + B²).
Robust distributed gradient descent. To tolerate adversarial workers, we replace the averaging operation in the classic distributed gradient descent (DGD) method with a robust aggregation, e.g., coordinate-wist wise trimmed mean (CWTM) and median (CWMedd (Yin et al., 2018), geometric median (GM) Chen et al. 2017), and Multi-Krum (MK) (Blanchard et al. 2017). This yields Robust-DGG presented in Algorithm[]] where robust aggregation protects the learning from incorrect gradients sent by the adversarial workers. The robustness of an aggregation method can be quantified by the following property of (f, robbuustsssssss (Allouah al. 2023a).
Algorithm 1 Robust Distributed Gradient Descent (Robust-DGD)
Initialization: Server chooses a model 02 E Rd, a learning rate y E R+ and a robust aggregation method F Raxxd -> IR..
for f = 1 to T do
Server broadcasts 0, to all workers. for each honest worker w; in parallel do
Compute local gradient g. (O,)), and send o²" Server.
// An adversarial worker w, can send an arbitrary vector in Rd for gt"
end for
Server computes R² == (
9: (n)
Server computes the updated model l(41 = 0g 7 R4 end for Output: Server outputs i chosen uniformly at random from ( 0-
Definition 2.4. F Raxd + Rd is said to be (f. x)-robust if there exists a robustness coefficient IR such that for all 3 In Rd and any set S [m]. = n f. the following holds:
F(E - =s|l² <
|x. Esll? where Is-
Σ SES
x
S
EES
(f, rooouustesssss encompasses several robust aggregations, including the ones mentioned above and more (e.g., see Allouah et al. (2023a)) It has been shown that an aggregation method is k)robut only if 2 2-27 Allouah et al. 2023a Importantly, the asymptotic eπror of Robust- DGD with (f, -)oobust aggregation, where E O(f((n 2f)), matches the lower bound (recalled in Lemma 2.3) (Allouah et al. 2023b). This testifies to the tightness of the (ff, robbusttessssss property. Note that the atorementioned aggregation methods (CWTM, CWMed, GM and MK) attain optimal robustness when composed with the pre-aggregation scheme: nearest neighbor mixing (NNM) (Allouah et al.) 2023a). Specifically, we recall the following result.
Lemma 2.5 (Lemma in Allouah al. (2023a).. For F (CWTM, CWMed, GM, MK), the composition F o NNM is (f. ro-rrttstt with k. S
8. n-プ 1 +
1
Thus, if 2 (2+ f) for 8 > 0, then FoNNM is (f. (f, -oobutt with K S 161 n-ン (5+1) E n-
Convergence of Robust-DGD. Lastly, recall the convergence result for Robust-DGD with (J, k))rbusttt aggregation F. We let Lix denote the minimum value of (0()).
Lemma 2.6 (Theorem in Allouah et al. (002bb). Consider Algorithm 7 with 7 S 1/L. Let
A, E R such that L ( Ly < A.. 11 F is (J, -robuusst with B 1, then
4

---

Published as a conference paper at ICLR 2025
T (0,l
24.
KG
T
(1 (1-1BB)yT
1- KB2
Thus, when (f/(nn 2f)) (and smaller than 1/B²), Robust-DGD is optimal, i.e., its error matches the lower bound recalled Lemma 2.3 as soon as 2 A A For 0, Lemma 2.6 recovers the convergence of DGD, provided that is tight, i..,, R E O n-27
3 ADAPTIVE ROBUST CLIPPING (ARC) AND ITS PROPERTIES
In this section, we first present a preliminary observation on the fragility static clipping, and then introduce adaptive robust clipping (i.e., ARC) along with its robustness guarantees.
For a clipping parameter C' E R+ and vector E Rd, we denote clipc = min (1,
C x. For
|z]|
a set of n vectors ..,..., E Rd, we denote Clipo Fn) (clipo(11),... .... clipo (ripo((r)) (In)
Let F be an (fobuurobust aggregation. Given Clipo(()...... (n)) = F (CI,
of n vectors 21...., Fna let F
We make the following observation.
Lemma 3.1. For any fixed C E R+ and K' 2 0, F Clipe is not (f, k..kkrrruu.
Thus, if the clipping threshold is fixed, i.e., independent from the input vectors, pre-aggregation clipping does not preserve the robustness of the original aggregation. This fragility of such static clipping is also apparent in practice, as shown by our experimental study in Section and Appendix E
adaptive clipping scheme that only makes of the standard robustness parameter f. i.c.. the tolerable number of adversarial workers. ARC is adaptive in the sense that the clipping threshold C is not fixed but depends on the input vectors. Specifically, ARC clips the largest k = [2 /n)///)( f)] vectors using clipping parameter given by the norm of the (k 1)-th largest input vector. The overall scheme is formally presented in Algorithm 2 and its computational complexity is Ond + log(n)) (see Appendix A.2). Thus, pre-composing more computationally expensive schemes like NNM and Multi-Krum, which have a complexity of Odde²) with ARC does not introduce significant overhead (see Appendix F.4). For detailed
Description of ARC. ARC
explanation of the underlying intuition behind our adaptive clipping strategy, ARC, we refer the reader Appendix A.I
Algorithm 2 Adaptive Robust Clipping (ARC)
Input: and 11; - Rd Find a permutation π [n] + [n] such that ||==0>||| > ||
|
Set k ( - f) and C = |
Output: Clip.(
Robustness Guarantee. We present below the preservation of robustness guaranteed by ARC. Let be (f, k)robutt aggregation method and ARC(ZI,..,
2., F(ARC(E)......))
Theorem 3.2. F is (f. k)-robust, then ARC is (F.*+ --27 -robust.
2
Proofs for the results presented in this section are deferred to Appendix Since n. n- (recalled in Section Theorem 3.2 implies that Fo A ARC is (f, 3xroust-,,uus,, i.e., ARC preserves the robustness of the original aggregation scheme. Therefore, convergence result for Robust-DGD with ARC follows verbatim from Lemma/2.6 replacing x with 3n. Despite this multiplicative factor of 3, we observe in Section that incorporating ARC consistently improves the empirical performance of classical aggregation methods. A more detailed theoretical explanation is provided later in Section 5.1
4 EMPIRICAL EVALUATION
In this section, we delve into the practical performance ARC when incorporated in Mobust-DSGGi (Algorithm in Appendix D), order-optimal stochastic variant of Robust-DGE (Allouah et al. 2023a). We conduct experiments on standard image classification tasks, covering different adversarial scenarios. We empirically test four aggregation methods when pre-composed with ARC. We contrast.
5

---

Published as a conference paper at ICLR 2025
these outcomes against the performance of these aggregations under static clipping and when gradient clipping is used. We show in Table and Figures and [ the metric of worst-case maximal accuracy. For each of the five Byzantine attacks executed (see Appendix accuracy achieved by Robust-DSGD during the learning procedure under that attack. The worst-case maximal accuracy is thus the smallest maximal accuracy reached across the five attacks. Furthermore, we use the Dirichlet (Hsu et al. (2019)) distribution of parameter a to simulate data heterogeneity. The comprehensive experimental setup can be found in Appendix D In this section, we focus on presenting our results for the CWTM and GM aggregation methods applied to MNIST and CIFAR- 10. As benchmark, we also execute the standard DSGD algorithm, in the absence of adversarial workers (i.e., without attack and [
record the maximal
0). Results for Tashion-MNIST, as well as for CWMed and MK, are provided Appendices and F All aggregation methods our experiments are pre-composed with NNM (Allouah et al. 2023a but we omit explicit mention of NNM in their names for simplicity.
4.1
BRITTLENESS OF STATIC CLIPPING AND SUPERIORITY OF ARC
Hestroppasily
Hesoreposity
rendurta
Test Accuracy (%)
Test Accuracy (%0
3
(b) f
Figure 2: Impact of the clipping strategy, under varying heterogeneity levels, on the worst-case maximal accuracy achieved by Robust-DSGG on MNIST with n 15 workers. CWTM NNM used as aggregation. DSGD reaches at least 98.5% in accuracy in all heterogeneity regimes.
We empirically demonstrate the brittleness of static clipping in robust distributed learning. While an exhaustive empirical study can be found in Appendix E we present findings on MNIST using CWTM, considering three heterogeneity levels: moderate (a = 1), high (a = 0.1), and extreme. We execute DDGD with = workers, among which f E {3, 4] are adversarial, and test static clipping thresholds C (0.02, 0.2. 2, 20 First, we observe that the optimal C' depends heavily on data heterogeneity. As seen in Figure performs much better under extreme heterogeneity. This dependency requires fine-tuning, which is impractical in distributed settings. Moreover, static clipping's 's effectiveness varies significantly across Byzantine attacks. While C' = 2 performs well under SF FAllen-Zhu et al. 2020). it fails under LF, causing training collapse (see Figure 7 in Appendix E}. This unpredictability makes static clipping unreliable in practice. The number of adversarial workers further affects static clipping's 's performance. In Figure 2 C = 2 is optimal for f = 3 under high heterogeneity, yet its accuracy drops below 50% making it ineffective. Unlike static clipping, ARC consistently matches or outperforms the best static threshold across all configurations, as shown in Figure 2 These results underscore the superiority of ARC over static clipping, eliminating the need for manual tuning and ensuring robustness regardless of unpredictable parameters like data heterogeneity and Byzantine attacks.
C is ideal in high heterogeneity, whereas C = 20
when f
4.2 PERFORMANCE GAINS OF ARC OVER ROBUST-DSGD
To quantify the improvement induced by ARC over Robust-DSGD without clipping, we evaluate distributed system with n - ʃ 10 honest workers while varying the number of adversarial workers f. We compare the performance of Robust-DSGD with and without ARC the MNIST dataset, highlighting the improvements achieved by our method. Additionally, we extend our analysis to larger distributed systems with 30 honest workers and
{3, 6) detailed in Appendix F.1.2
ARC boosts robustness in high heterogeneity. Figure shows the performance of against the FOE attack when using ARC opposed to clipping. In low heterogeneity (i.c., 0.5), the performances of ARC and no clipping are comparable. When the heterogeneity increases (a 0.1), CWTM and GM significantly struggle to learn, while the same aggregations composed
6

---

Published as a conference paper at ICLR 2025
with ARC almost match the final aceuracy of DSGD. In extreme heterogeneity, the improvement induced by ARC is the most pronounced, enabling both aggregations to reach a final accuracy close to 90%. Contrastingly, the same aggregations without clipping stagnate around 10% throughout the training. Interestingly, only f = adversarial worker among n = 11 (i.e., less than 10%) suffices completely deteriorate the learning when no clipping is applied, highlighting the necessity of ARC in extreme heterogeneity. These observations are also conveyed in Figure 44 which compares the worst-case maximal accuracies achieved by Robust-DSGD when = 1, with and without ARC, for varying levels of heterogeneity. While CWTM and GM yield comparable accuracies with ARC in low heterogeneity (a 2 0.5), their performance significantly degrades when a drops below that threshold. Indeed, when = 0.1, their accuracies drop below 65%, while ARC enables the same aggregations to maintain their accuracy at just below 98%. In extreme heterogeneity, the performance of the aggregations without clipping completely deteriorates with accuracies close to 15%. Contrastingly, ARC efficiently mitigates the Byzantine attacks, resulting in accuracies above 85% in the worst case for both aggregations. Similar plots for f {3, 5, 7 convey similar observations (sce Appendix F.1
Accursry
Test Accumnry
75
25
75
Test Accuum
150
50
catte 186a
25
25
200
400
600
800
1000
200
400
600
800
1000
%
200
400
600
800
1000
Step
Step
Stop
(a) 0.5
(b)
0.1
(c) extreme heterogeneity
Figure 3: Performance of Robust-DSGD when using ARC and without clipping on MNIST. There
are 10 honest workers and f 1 adversarial worker executing FOE (Xie et al. 2020).
ARC increases the breakdown point in adverse settings. Figure Ta of Section | shows that for f e [L.....51 5). DSGD with CWTM and GM completely fails to learn, consistently yielding worst-case maximal accuracies close to 15% This suggests that point for these aggregations in extreme heterogeneity. However, composing them with ARC increases the breakdown point of these aggregations to Robust-DSGD to achieve accuracies greater than 85% in the worst case. However, when f 2 3, the performance degrades, although CWTM with ARC is still able to reach a satisfactory accuracy close to 70%. Moreover, even when the heterogeneity is not large (a = 0.5), ARC still produces a significant improvement when the fraction of adversarial workers increases in the system. Indeed, in Figure 4b.. the performances of ARC and no clipping are comparable for f S 3. However, the improvement induced by ARC is much more visible when f 2 Particularly when f ARC enables CWTM and GM to reach accuracies greater than 80% in the worst case, whereas the same aggregations yield accuracies below 40% without clipping, indicating the raise of the breakdown point due to ARC. Plots for 0.1 and I convey the same observations in Appendix F.]
constitutes the breakdown
3. Indeed, for f
and 2, ARC enables
100
100
80
Test Accuracy
Test Accuracy
60
60
40
40
20
CMTTR
20
3M ARV
0.5 a= 0.1
extreme
Hoterogenelly Level
Number of adversarial workers
(a) f
(b) a 0.5
Figure 4: Worst-case maximal accuracies achieved by Robust-DSGD, with and without ARC, on heterogeneouullydistiiee distrrbuued MNIST with 10 honest workers. Left: 1 adversarial worker among n 11 for varying levels of heterogeneity. Right: a = 0.5 for varying f.
Improved robustness on CIFAR-10. We also conduct experiments on CIFAR-10 with n = 17 and f f= 1. Table [ shows the worst-case maximal accuracies achieved by ARC and no clipping for CWTM and GM. For a = 0.2, ARC consistently outputs accuracies greater than 67% for both aggregations, while clipping yields lower accuracies (with larger variance). For instance, GM achieves 41.2% on average, i.e.. 26% less than its counterpart with ARC. In the more heterogeneous setting a 0.075, ARC enables all aggregations reach worst-case maximal accuracies close to
7

---

Published as a conference paper at ICLR 2025
60% (with small variance). However, executing the same methods without clipping significantly deteriorates the performance of Robust-DSGD, with GM achieving 16% in worst-case accuracy. This also be seen in Figure 23a where FOE completely degrades the learning when ARC is not used. We further extend this experiment to a larger distributed system with 33 honest workers, as detailed where observe the same trends as reported here.
in Appendix F3
a 0.2
a 0.075
Aggregation
No Clipping
ARC
No Clipping
ARC
CWTM
51.6 - 5.1
67.8 + 0.9
40.7 1 0.5
60.5 1: 1.2
GM
41.2 +: 3.5
67.0
1.0
16.0 + 2.3
60.0 + 2.0
Table 1: Worst-case maximal accuracies (%) achieved by Robust-DSGD on heterogeneously- distributed CIFAR-10 with ARC and without. There is f = 1 adversarial worker among = 17. As a baseline, DSGD (f = 0) reaches 76.5% and 70% when a = 0.2 and 0.075, respectively.
IMPROVED GUARANTEE OF ROBUST-DGD WITH ARC
In 4 we empirically demonstrated that ARC outperforms SOTA aggregation methods without clipping. despite these methods being theoretically proven to be optimal. This naturally raises the question: why does ARC, which shares similar convergence guarantees, significantly outperform plain Robust-DSGD? To address this, we now focus on the influence of model initialization on the robustness of aggregation methods, considering both theoretical results and empirical insights.
5.1 IMPROVEMENT OF CONVERGENCE GUARANTEES
In this section, we characterize the improvement induced by ARC over the lower bound recalled in Lemma 2.3 Specifically, we consider Algorithm !
with aggregation F o ARC, i.e., in each learning
step t. RS == Fo ARC 9i (1) ...... gi We establish in Lemma 5. 1 key property of ARC, crucial to derive the improved stationarity error of Robust-DGD with ARC Theorem 5.2
Lemma 5.1 (Bounded Output). Let F be an (f, r:)rrbustt aggregation method. For any vectors Ti,- Fn Rd and set S C [n)] such that |5| n f. || ARC(E I maxes |ax]l-
This result indicates that incorporating ARC bounds the norm of the aggregated output by the largest norm of the honest gradients, i.e., max || and further demonstrate Lemma C.1 that this property is specific ARC, i.e., classic (ff, xo)-rbustt aggregation methods do not inherently exhibit this behavior. This property enables us to obtain the following improvement on the asymptotic convergence guarantee of Robust-DGD with ARC.
||. In Appendix C
we provide the proof of Lemma 5.]
In the following, we show that when the local gradients of the honest workers at the initial model 0 are sufficiently small, then Robust-DGD with ARC overcomes the lower bound recalled in Lemma 2.3
(2(f/)) We denote BP 22 C. == B/1+7 and v (G, B, p) = 640 (1 + T )² (1+ 13a
where denotes a real value. Recall from Lemma 2.3 that BP and e, are the breakdown point and the lower bound on the stationarity eиrоr when f BP, respectively, under (G, --grrdiient dissimilarity. We obtain the following theorem for Robust-DGD with ARC. Let A, be a real value
such that Lx (0,) Li S A.. The proof of Theorem 5.2 is deferred to Appendix C
Theorem 5.2. Suppose B > O and there exists E R+ such that maxiH Let F E {CWTM, CWMed, GM, MK) NNM, Y
(.,0) <
min {{ (Adg) ) 3, 1. and T KG (2+BB)) [I-E,]G" L) G. For any (0,1), if
A.L.
Consider an arbitrary real value &o E (0, 1). Let p exp
R (1 BP, where < min (VG.B,,)) }. then E V ())l
SUEO
Theorem 5.2 demonstrates that Robust-DGD with ARC improves over the lower bound E, when the ratio f/n is sufficiently close to the breakdown point (BP), provided the local gradients at model initialization are bounded. This, in turn, leads to improvement over the original learning guarantee of Robust-DGD (as stated in Lemma 2.6). which applies for arbitrary model initialization.
Influence of model initialization and data heterogeneity. Note that the smaller the bound on the initial gradients (i.e., the better the model initialization), the greater the improvement induced by ARC. Specifically, a decrease in leads to reduction in p. which subsequently lowers (G, B, p).
8

---

Published as a conference paper at ICLR 2025
As result, for fixed value of & (i.e., for fixed ratio of adversarial workers), the condition E I o/V(G, p) is satisfied for a smaller v. thereby yielding a lower stationarity error. This theoretical deduction is empirically validated in Section 5.2 A similar improvement occurs when increasing data heterogeneity, while keeping all other factors unchanged. Specifically, as G increases, (G, P) decreases, allowing for a smaller reduction factor v and thus larger improvement in performance. This trend is also validated empirically in Figures and
Influence of f/n. Additionally, for fixed model initialization, an increase of f/n towards the BP (i.e., as { + 0) allows the reduction factor v to become smaller, leading to a greater improvement, as evidenced in Figures Ia and 44b] Indeed, we show in Theorem C.4 (a more complete version of Theorem 5.2) that ARC effectively increases the BP of (f. robbust methods from 2+ to 2' provided the intial honest gradients are bounded in norm. Lastly, we would like to recall that when the workers' gradients model initialization are arbitrarily large, the convergence guarantee of Robust-DGD with ARC reduces to that of classic Robust-DGD (see Section 3
Practical scope of Theorem 5.2 Since & BP-//n and 2 (GG, B, it follows that the improvement factor V is at least (G, B, p)
BP
BP
f/m BP
For ARC to induce an improvement, we require
Since Theorem 5.2 assumes / < nBP, the improvement occurs when f E nBP 1 (G..B,p) nBBP.. The length of this interval, i.e., "VC. depends the size of the system In small systems where (G B. p). the length of the interval is smaller than since BP < 1/2. Therefore, at most one value of f. i.e., the largest integer smaller than nBPP, can lie in the improvement interval. Conversely, in large-scale systems where n E Ω (G, B, p) log L (G, p)), the improvement interval expands significantly and can be much larger than 1, thereby demonstrating ARC's effectiveness in large-scale distributed learning.
V < 1, which reduces to having / > nBP
V(G.B.p)
BP
5.2 INFLUENCE OF MODEL INITIALIZATION ON EMPIRICAL ROBUSTNESS
Figures lb and 5 illlstrate the effect of model initialization on the performance of Robust-DSGD with and without ARC, eval- uated on MNIST with 10 honest workers. We investigate two regimes of heterogeneity: extreme heterogeneity and a 0.1, and consider f = adversarial worker. The experiment pro- ceeds follows: we begin with the default model parameters initialized by PyTorch (i.c., the same ones used in Section 4 which represent well-chosen set of initial parameters. These parameters are then scaled multiplicatively by a factor where larger values of μ correspond to progressively worse initializa- tion, and vary j E {1,...,5) 5). The results show that, under well- initialized conditions (μ 1), ARC significantly enhances the performance of Robust-DSGD achieving a substantial im- provement in worst-case maximal accuracy, particularly under extreme heterogeneity. In this regime, ARC boosts accuracy by about 70% compared to plain Robust-DSGD (Figure Ib). This (u- = 1) corresponds to the initialization conditions of the empirical results presented in Section 4 As μ increases (i.e., the initialization worsens), the perfor- mance of ARC-enhanced Robust-DSGD gradually declines, with noticeable degradation starting from
Irttauaticn Scalin Facar
Figure 5: Worst-case maximal ac- curacies achieved by Robust-DSGD with CWTM, on MNIST (a = 0.1), with 10 honest workers and Byzan- tine worker. The x x-axis represents worsening model initialization.
= 4. Nevertheless, even at this point, ARC still offers a performance advantage over Robust-DSGD without clipping. By == 5, the performance of Robust-DSGH with ARC converges to that of plain Robust-DSGD. both achieving an accuracy of around 10%. Another key observation from Figures [b] and that the behavior of Bobust-DSGD with ARC. closely mirrors that of Byzantine- -ree DSGD. Both exhibit similarly poor performance when μ 5. and their accuracies are comparable when a < 3, especially when a = 0. This suggests that ARC is particularly effective at exploiting good model initialization, similar to the performance of DSGD in the absence of Byzantine workers. In contrast, plain Robust-DSGD struggles to fully leverage well-initialized models, as evidenced by its consistently lower accuracy (around 20%) in Figure [b] These findings highlight the important influence of model initialization on the robustness of aggregation methods, and empirically validate theoretical findings in Section 5.1

---

Published as a conference paper at ICLR 2025
6
RELATED WORK
Gradient clipping a well-known technique for tackling exploding gradients in deep learning (Good-
[ellow et al. 2016). It has been extensively analyzed in the centralized setting (Zhang et al. 2020b a
Koloskova et al. 2023), with applications to differential privacy (Pichapati et al. 2019). Moreover, we would like to note that gradient clipping has also been shown useful to obtain tighter convergence guarantees for stochastic gradient-descent methods in the case where the gradients have heavy-tailed
noise (Gorbunov et al. 22200] 2022; Danilova 2023). The considered proof techniques, however, do not apply directly to our adversarial distributed learning setting. A similar study on the impact of clipping also exists for distributed settings (Zhang et al. 2022 Khirirat ct al. (023).
In the context of robust distributed learning, prior work has proposed iterative clipping for robust aggregation (Karimireddy et al. 202T). The clipping scheme, however, has not been shown to induce any improvement over other SOTA robustness schemes. Recent work (Malinovsky et al. 2023) has proposed pre pre-agregation clipping using temporal gradient differences, in conjunction with variance reduction, to tackle partial worker participation when adversarial workers can form a majority. We, however, propose and study pre-aggregation clipping as a tool improve the robustness obtained by a general class of aggregation rules. Other prior work (Mhamdi et al., 2021] Farhadkhani et al. [022 Allouah al. 2023a) that used static pre-aggregation clipping to enhance the empirical robustness of Robust-DGD, did not provide any formal explanation.
While adaptive clipping schemes, similar to ARC, have been studied in the context of robust aggre-
gation (Gupta & Vaidya 2020 Liu et al. 2021 Diakonikolas et al. 2020 Abdalla & Zhivotovskiy
2024), critical differences should be noted. The robustness guarantees Gupta Vaidya (2020): Liu et al. ) only apply to strongly convex loss functions, under the specific 2 condition. We consider non-convex loss functions, as well as a generic heterogeneous setting of (G, B) -rradinett dissimilarity. In contrast to the clipping scheme proposed in Diakonikolas et al. (2020); [Abdalla & Zhivotovskiy (2024), ARC only uses the f parameter to tune the clipping threshold and does not rely on any additional priori knowledge of the distribution of honest workers' gradients. Moreover, we prove a deterministic robustness property of ARC (see Theorem 3.2). whereas Diakonikolas eet al. (2200; ; Abbdlla & Zhivotovskiy (2024) only provides probability guarantees assuming the non-adversarial inputs to be i.i.d. with the distribution satisfying certain special properties.
Lastly, prior work (Guerraoui et al. 1 Zhu & Ling 2022 Allouah al., 2023c Choffrut et al.
2024| Alllouhh et al., | 2024) has considered the challenge of privacy preservation alongside robustness in distributed learning. In this context, the gradients are assumed to have bounded norms in order to control the sensitivity of the algorithm, as is common in differential privacy (DP) (Abadi et al. 2016). This often enforced in practice through static gradient clipping. Our findings suggest that an adaptive approach, such as ARC, may provide more reliable alternative. However, a rigorous analysis of ARC in the context of DP remains an important avenue for future research.
7 CONCLUSION & DISCUSSION
We introduced Adaptive Robust Clipping (ARC), a pre-aggregation clipping scheme designed to harness the empirical benefits of gradient clipping, while preserving the worst-case optimal conver- gence guarantees of Bbbust-DGD Unlike existing adaptive clipping schemes, ARC does not require additional tuning since it only relies on the standard robustness parameter, i.e., the tolerable fraction of adversarial workers. Through theoretical analysis, we explained ARC's ability to enhance the robustness of Robust-DGD, particularly when the model is well-initialized. This phenomenon was validated through comprehensive experiments on standard image classification datasets. In short, our experiments showed that ARC consistently boosts the performance of Kobust-DGD, especially in scenarios with high heterogeneity and large fraction of adversarial workers.
Future direction. Our work also reveals a gap between theory and practice in Byzantine machine learning (ML). While Robust-DGD and ARC-enhanced Robust-DGD share the same worst-case con- vergence guarantees, their empirical performances are drastically different. fact, and unsurprisingly, Byzantine MI. theory focuses on worst-case guarantees, which, although essential, may not fully capture the practical realities of many learning settings. In practice, we often operate under favorable conditions (e.g., well-initialized models), where worst-case guarantees have limited relevance. This gap opens the door for future work that prioritizes practically-drie ddiven research in Byzantine ML, under conditions that are realizable in real-world scenarios. It encourages the development of robust distributed learning methods, like ARC, that can take full advantage of favorable practical conditions, thereby yielding relevant theoretical guarantees and superior empirical performance.
10

---

Published as a conference paper at ICLR 2025
Acknowledgment. This work supported in part by the FNS Project *Controlling the Spread of Epidemics: A Computing Perspective* (200021 200477) and the FNS Project *TruBrain* (20CH21 218778 / 1). We also extend our gratitude to the anonymous reviewers of the ICLR 2025 conference for their valuable insights and feedback.
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMAhan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Pedro Abdalla and Nikita Zhivotovskiy. Covariance estimation: Optimal dimension-liee guarantees for adversarial corruption and heavy tails. Journal of the European Mathematical Society, 2024.
Zeyuan Allen-Zhu, Facze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzantine-resilien non- convex stochastic gradient descent. In International Conference Learning Representations, 2020.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In Francisco de Meent (eds.), Proceedings The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 1232-1300. PMLR, 25-27 Apr 2023a. URL httph::t//prttt /ptoee/e/ooeeddnss
Ruiz, Jennifer Dy, and Jan-Willem
mlr. wrwss w206 2ww00//11ouaahh22mmm html
Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and Geovani Rizk. Robust distributed learning: Tight error bounds and breakdown point under data heterogeneity. In Thirty- seventh Conference on Neural Information Processing Systems, 2023b.
Youssef Allouah, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. On the privacy- robustness-utility trilemma in distributed learning. In International Conference on Machine Learning, number 202, 2023c.
Youssef Allouah, Rachid Guerraoui, and John Stephan. Robustness, or privacy: Pick two in machine learning, 2024. httphttss///axi...ooo
14712
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little enough: Cireumventing defenses for distributed learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'A'chéééBue F. Fox, and
R. Garnett (eds.), Advances Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. / neuris cttpsscccceeee ccppaper__pppeeeppppeeeeeeee.e fi Fileespappe 201//flaccccc311100eeeB6bbeeobde
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning Byzantine tolerant gradient descent. In I. Guyon, U. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 119-129. Curran Associates, Inc., 2017.
with adversaries:
Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3) 2018.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 1(2):1225, 2017.
Antoine Choffrut, Rachid Guerraoui, Rafael Pinot, Renaud Sirdey, John Stephan, and Martin Zu- ber. Towards practical homomorphic aggregation in byzantine-resillesn distributed learning. In Proceedings of the 25th International Middleware Conference, Middleware '24. pp. 431-444, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400706233. doi: 10.1 10.1145//622892.770788.
http://s/.oooooro.......//////// 370088
11

---

Published as a conference paper at ICLR 2025
M Danilova. Algorithms with gradient clipping for stochastic optimization with heavy-tailed noise. Springer, 2023.
In Doklady Mathematics, volume 108, pp.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-1) 2012.
Ilias Diakonikolas, Daniel M Kane, and Ankit Pensia. Outlier robust mean estimation with sub- gaussian rates via stability. Advances in Neural Information Processing Systems, 13:1830-1840, 2020.
El-Mahdi EI-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Lê-Nguyên Hoang. Rafael Pinot, Sébastien Rouault, and John Stephan. On the impossible safety of large ai models, 2023. BRRLtttss://axxit httttpss//axxiv.org//bbbbb
15259
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.). Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 6246-6283 PMLR, 17-23 Jul 2022.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Lë-Nguyên Hoang, Rafael Pinot, and John Stephan. Robust collaborative learning with linear gradient overhead. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), Proceedings of the 40th International Conference Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9761-9813. PMLR, 23-29 Jul 2023. URL html
mlr www.rppess//ve v202 www.aaaaaaaaaaaaaaaa
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pp. 249-256. JMLR Workshop and Conference Proceedings. 2010.
lan Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. http: //www.deeppp /ww.deepplerr..ngooo.. org
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances in Neural Information Processing Systems, 33:15042 -5003,, 2020.
Eduard Gorbunov, Marina Danilova, David Dobre, Pavel Dvurechenskii. Alexander Gasnikov, and Gauthier Gidel. Clipped stochastic methods for variational inequalities with heavy-tailed noise. Advances in Neural Information Processing Systems, 35:31319 113322,- 2022.
Eduard Gorbunov, Samuel Horváth, Peter Richtárik, and Gauthier Gidel. Variance reduction is an antidote byzantines: Better rates, weaker assumptions and communication compression cherry on the top. In The Eleventh International Conference on Learning Representations, 2023.
URL
net. fott:/orunnie worumoorumiio www.ddddodduuoeeee oot.
Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, Sébastien Rouault, and John Stephan. Differential privacy and byzantine resilience in sgd: Do they add up? In Proceedings of the 2021 ACM
Symposium on Principles of Distributed Computing, PODC'21, pp. 391-401, New York, NY, USA, 2021, Association for Computing Machinery. ISBN 9781450385480. doi: 10.1145/3465084, 3467919. URL htttps:///// wrw. 0. /45534 3467919
Rachid Guerraoui, Nirupam Gupta, and Rafael Pinot. Byzantine machine learning: A primer. ACM Computing Surveys, 2023.
Nirupam Gupta and Nitin H Vaidya. Fault-tolerance in distributed optimization: The of redundancy. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pp. 365-374, 2020.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition, 2015.
12

---

Published as a conference paper at ICLR 2025
C. A. R. Hoare. Algorithm 65: Find. Commun. ACM, 4(7):3113222 jul 1961. ISSN 0001-0782. doi: 10.1145/366622.366647 URL/tttp:://dbi wwwp:.oorg/1... wtt.://////...////.... 111.111///6.2.66662333
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification, 2019a. URL 1909. 06335
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification, 2019b.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Alcksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2): 1-210, 2021. ISSN 1935-8237. doi: 001151/2200000083.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143. PMI.R, 2020.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for Byzantine robust optimization. International Conference On Machine Learning, Vol 139, 139, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. International Conference on Learning Representations, 2022. URL
net/ forum?id= (xKKDiiivxxxx
Sarit Khirirat, Eduard Gorbunov, Samuel Horváth, Rustem Islamov, Fakhri Karray, and Peter Richtárik. Clip21: Error feedback for gradient clipping. arXiv preprint arXiv:2305. 18929, 2023.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U. Stich. Revisiting gradient clipping: stochas- tic bias and tight convergence guarantees. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org, 2023.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset. online: http:///www. cs. toronto. edu/kriz/cifar huml, 55(5), 2014.
Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans.
Program. Lang. Syst. 4(3):382-4011 401, jul 1982. ISSN 0164-0925. doi: 10. 10.1145/551172.357776 URL httph::/ org wtwp:///......111111...7........
Shuo Liu, Nirupam Gupta, and Nitin H. Vaidya. Approximate Byzantine fault-tolerance in distributed optimization. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC'21, pp. 379-389, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450385480. doi: (0.1145/44550844444799999
Guodong Long, Yue Tan, Jing Jiang, and Chengqi Zhang. Federated learning for open banking. In Federated Learning: Privacy and Incentive, pp. 240-254. Springer, 2020.
Grigory Malinovsky, Peter Richtárik, Samuel Horváth, and Eduard Gorbunov. Byzantine robustness and partial participation can be achieved simultaneously: Just clip gradient differences. arXiv preprint rxXiv22311.44122 2023.
13

---

Published as a conference paper at ICLR 2025
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication Effiicient Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282 PMLR, 20-22 Apr 2017. URL htt..htsss..... httt:p:://ppoceeeee http::::/oocceeeeeee ngs .m www..pressvvvii www5////////1111mm html
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. Distributed momentum for byzantine- resilient stochastic gradient descent. In International Conference Learning Representations, 2021.
Dinh C. Nguyen, Quoc- Quec-Viet Pham, Pubudu N. Pathirana, Ming Ding, Aruna Seneviratne, Zihuai Lin, Octavia Dobre, and Won-Joo Hwang. Federated learning for smart healthcare: survey.
ACM Comput. Surv., 55(3), feb 2022. ISSN 0360-0300. doi: 10.1 (0.1145/3501296 URL (tLhttps 7/doi /rooi.org/// 114...1111/9
Venkatadheeraj Pichapati, Ananda Theertha Suresh, Felix X. Yu, Sashank J. Reddi, and Sanjiy Kumar. Adaclip: Adaptive clipping for private SGD. CoRR, abs/1908.07643, 2019. URL
http: //tp:/aaav.../.aa/.aae.a..aaaaaa org/ abs abs//908/ 19001076433
Lili Su and Nitin H Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In Proceedings of the 2016 ACM symposium on principles of distributed computing, pp. 425 434, 2016.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pp. 1195-1204. PMLR, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 077447 2017.
Cong Xie, Oluwasammi Koyejo, and Indranil Gupta. Fall of empires: Breaking rezzantine-toleran sgd by inner product manipulation. In Ryan P. Adams and Vibhav Gogate (eds.), Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, volume 115 Proceedings of Machine Learning Research, pp. 261-270. PMLR, 22-25 Jul 2020. URL https://proceeding
mlr. wwwpppssssss...iipeeppp
html
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robuss distributed learning: Towards optimal statistical rates. International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. In Proceedings of the 34th International Conference on Neural Information Processing Systems, 20, Red Hook, NY, USA, 2020a. Curran Associates Inc. ISBN 9781713829546.
Jingzhao Zhang. Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2020b. URL http:tttt///oeeeeeviee nttp//eee//eeeeeeeeeeeeeee httperrrwwee..eee//ooooooee///nn
Xinwei Zhang, Xiangyi Chen, Mingyi Hong. Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. In International Conference on Machine Learning, pp. 26048-26067. PMIR, 2022.
Heng Zhu and Qing Ling, Bridging differential privacy and Byzantine-robustnes. via model aggregation. In Lud De Raedt (ed.), Proceedings of the Thirty-First International Joint Con- ference on Artificial Intelligence, IJCAI-22, pp. 2427-2433. International Joint Conferences on Artificial Intelligence Organization, 7 2022. doi: 10. 00.24963/ijcaa.2222/333. URL https
//doi. moeiioorg/00. /ttpa///....2233//82 249 2022/337 Main Track.
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL DETAILS ON ARC
This section provides further insights into the design and computational complexity of ARC, ex- plaining its adaptive clipping strategy and its theoretical foundations. We also analyze its efficiency compared to static clipping.
A.1 DESIGN OF ARC
Lemma B.1 in Appendix shows that F o Clipe (f. R)-robust, provided that |SS Sel 2 for all subsets S of size n Note that this condition is impossible to guarantee when using fixed clipping threshold that does not depend on the imput vectors. In order to ensure that |S \ S. 2 1 for all subsets S of size f. the clipping threshold C' should be large enough such that less than - input vectors are clipped. This motivates the design of an adaptive clipping strategy. Accordingly, we propose to choose clipping threshold such that the total number of clipped vectors is of the form [>(n - f)J, where X < Note that is natural to clip more vectors as the fraction of adversarial workers s/n increases, to control the impact of Byzantine behavior. Therefore, we set À == c where
0 S S 2. Since
< 2 and À < 1, the total number of clipped vectors S - f) < f
for all Ç E [0, 2]. This constitutes the underlying idea behind our adaptive clipping strategy ARC, presented in Algorithm 2 Notably, our theoretical results hold for all < E [0, 2]. However, empirical evaluations show that setting 2 consistently provides the best performance, leading us to adopt this value in Algorithm 2
and throughout the paper.
A.2 COMPUTATIONAL COMPLEXITY OF ARC
The computational complexity of ARC is comparable to static clipping, with the primary difference being an additional sorting step. The overall complexity can be broken down as follows:
1. Norm computation: Computing the norms of all input vectors requires ((nd) time. (This step is also required in static clipping.)
2. Sorting step: Sorting the norms incurs an additional On log n) time. n is large relative to k = (2f/n))
f) an efficient selection algorithm such quick-select (Hoare 1961)
can be used instead, reducing the complexity to O(n) in the average case.
3. Gradient clipping: Clipping vectors requires ((nd) time.
Thus, the total time complexity of ARC is: O(nd + n log
Crucially, this complexity remains dimensiin-inndependenn in the sorting step, making it scalable while maintaining robustness.
B PROOFS FOR RESULTS IN SECTION
3
Proofs for Lemma 3.1 and Theorem 3.2 are presented in B.1 and B.2 respectively.
Notation Let N Given vectors Tı, ..,...,, Fn
Rd and S [n)]. denote by Vs the mean
of the vectors in S rs [ Eies Tj. Given a clipping parameter C 2 0, let
y: = c1, = min (1,
C
||>:||
and
Σ y4-
1s =
S
EES
We denote by S. the set of clipped vectors in S,
S. (i S, > C).
(1)
15

---

Published as a conference paper at ICLR 2025
Recall that we denote by Clipe be the operator such that, for 21, ................................ 2n R
Clipo(Z1..... .n) = (clipo(z1)......... (2.p)(z))
Further, let F [aad Rd. We denote by F Clipe the aggregation rule that first clips the input vectors using parameter C, and then aggregates them using
F Clipo Fn) ( ..))
B.1 PROOF OF LEMMA 3.1
Lemma 3.1. For any fixed C TRR and 2 0, F Clipo is not (. (f, y-rouust.
Proof. We use reasoning by contradiction prove the lemma.
We first consider the case when C > 0. Let S = {I...., n f). Consider an arbitrary set of n vectors .1...., Zn in Rd such that 21
fn-f f = Øg and رل 2C. We assume that that F o Clipo is ('rrbust for some n' 2 0. This assumption implies that
n¹
| o Clipe(a,,..... ..., v.) - xsl1²
||: - x. 0.
S
EES
Therefore,
F Clipo(z1...... Ts.
However, the clipping operation results in clipe(11) _.. clipo(sn-s) LT.. Therefore, by (J, m:)robustness of F,
F (EI.. xn)
2 cln (n(lnn--+)-s)) (x -
This contradicts (2) As this contradiction holds for any value of n', F Clipe cannot be (f: 15))- robust for any n!.
The proof for the case when C = ( is similar to the above, where we choose æ1 Inn Fs such that Eg is any vector with strictly positive norm.
B.2 PROOF OF THEOREM
Our proof relies the following lemma, proof of which is deferred to B.2.1
Lemma B.1. Let C E TR+ and F be an (f. x))robust aggregation rule. Consider an arbitrary set of vectors 21, 322-..- E TR and arbitrary 5 C [m] with |S]
f. Let S. denote the set of
indices of clipped vectors in S, ie., S. = {i E S, || C}. If S Sel 2 1, then
F Clipo (l - ssll <
||4 Esl
iES
[Sel where R = K |8
Lemma B. shows that F o Clipe is (J, R)-robust, provided that |S S. > 1 for all subsets S of size n f. Note that this condition is impossible to guarantee when using a fixed clipping threshold
that does not depend on the input vectors. In order to ensure that |S \ S..l > 1 for all subsets S of size n - f, the clipping threshold C' should be large enough such that less than n - f input vectors clipped. By construction, ARC satisfies the condition of Lemma B. This brings
the proof
of Theorem 3.2 which we recall below for convenience.
2f Theorem 3.2. F is (f. ro-buusst then ARC is (F.K+ n n-28 robust.
Proof. Since we clip the largest [2(f/n)(n f)J gradients, for given S S [x] with |S| we have
SS. < (2(f/n)(n f) s 2(f/n)(n f).
16

---

Published as a conference paper at ICLR 2025
Therefore,
2 (n f) = (n -f) n2 2
SS Sel = |S| - |Sel 2 (n f)
Since it is assumed that f < nn/2, we have
S Sel
T2 n
n
Thus, the condition (S Sel 2 1 is always verified. Hence, from Lemma B.1 we obtain that Fo ARC is [, (R
[S_] [STS.
-robust where
| S Sel
I (f/n)(n-1) 2 2
(n f) m)=-2
This concludes the proof.
B.2.1 PROOF OF LEMMA B.1
We start by giving bounds on the variance (Lemmal B.2 and the bias (Lemma) B.3 and Lemma B.4 due to the clipping operation. combine these bounds to prove the theorem.
VARIANCE REDUCTION DUE TO CLIPPING
We start by giving bound on the variance of the clipped vectors. Recall from T that S. = {i
S, | > C}.
For all S [m] with |S] = n - f. the following holds Lemma B.2. Let C 2 0, n > 0 and f < n 2. true
1. If [s
$ C
then
1
Us 12 5
Fs|l
(1
C)..
S
|
iE9
iES.
2. If | ||
> C. then
1
|S Sel
11 Dsl1²
Σ
la0 Tssl
(1
C)²
Σ
[1<>|| - |Ts
S
SS]
S
VSS
EE
EES.
Proof. Note that
1
1/
US
+ Js ysll
S
IS
EE
iES
- 1sl1 2 + | - Fsll + +(21 - Ts. Ts -8s)
S
iES
1lys Ezl
|0g Tsll +
2/ -Is, Es -V9
S
|SS|
IES
iES
T
1/
Es 2- + | Fsl
(TT
3s. E5 4s)
I
Σ
1/3/
33
12
[ - Usl
SS
IES
17

---

Published as a conference paper at ICLR 2025
By the definition of Se (in (T) for all E
S Se, y: 24. Therefore,
1
Tsll
11 Isll
+
11 Tzl
S
|
S
iES
iES
SES.
|
Es|l
+
1 Es 12
S
SES.
The above can be written as
1 SS
Σ
U
Σ
Ts|l
+
Σ
(llv
- Fssl
||04 - =ssl
(4)
S
EE
iES
iESE
For i Se, have yt
C
Ty. Thus, for all i E So. we obtain that
|88 - Fsl - ||:; - Fs
+ [T 1| 2(yi, F.) - ||0:112 -1=s|1 + 2( Fs)
=02
C - | +2 (1 1- ||,0
C
(2 Fs)
(2 Its |
= -||==; - C) + C) + 2(11===| - CC
= (1<=:|1 - CC (2 (2t, (s) ||:||| c)
||=
By Cauchy-Schward inequality, we have (xi, x.) $ ||>|||| |||||| Therefore,
13y/
| ssll² s [1<=;] C) (2 |> ||>!||| C).
Substituting from the above in we obtain that
1u Esll
a. Esll
+ S
Σ
-) ||a,|| C).
S
S
ies.
Substituting from the above in
B we obtain that
luu
Usll²
<
|
æ +
Σ
(2) - -|==1| || C) - ||āT - Usll
-
S
S
1ST
EES
SES
iES.
(5)
now consider below the two cases: ||>|||
S and
| >.
In the first case, i.e.. when ||rs||| S C, we have
Σ (1|= C) (2 |> - ||=;||| - c)
(|10:|] - C)
||> C)
S
BES.
iES.
<
[|<2a|] C)
S
EES.
Substituting from the above in (
yields the following
- Us
12
<
| -
=
(||=|| CC)2 - |īs - Tsl1
S
S
S
iES
iES
NES.
-
-
(1|=;|1 C
S
S
iES
VES.
This proves the first part of the lemma.
18

---

Published as a conference paper at ICLR 2025
Consider the second case, i... | C. Note that
Σ - (2 iESc
| - C)
((| - C)² (1|zil |
[S]
|S|
EESe
|
(1ı=~|) - -C)2 |S|
Σ
[|
|| (6)
|S|
SES.
Since |sl|| C, and |iTs| ll I C, we have |T
|i 2 |
C 2 0. This, in conjunction
with the reverse triangle inequality, implies that
[ Tsll 2 2
(|
2 [| - -C).
Substituting from 6 and
7 yields the following:
Tsll
10s xs|l²
SSel
(| C)²²
1
Σ
(1|=)1 - | (1<E5| C)
IS
[S]
[
BES
SE
iESe
(IScl
-1) 1) (11081 -C)²
21 zs|1²
(||=||] | 11)
|
[S]
iES.
|S Scl
21, - 23|l² -s|
[| C22
(1<=0|1 - |T
S
[S]
S
S
xE
This proves the second part, which concludes the proof of the lemma.
BIAS DUE TO CLIPPING
We now bound the bias induced by clipping the input vectors.
Lemma B.3. Let C' 2 n 0, f 5.J and S S [n]. |S| = n f. Then,
Sel
[ss - 2
Σ [| - C)).
SS iES.
Proof. Note that
1
[s Fsl2
S
32
1
//1
S
(1 W:)
iES
iES
BES
As H; y4 for all i S% Sc. we have
| - Tsll
Σ
(xr
vi)
|
KES.
Due to Jensen's 's inequality,
|
S
|æ - 2
(x.
y:)
<
||
- y:l1?
?
S
S
iES.
#ES.
As y:
| v; for E S., substituting this in the above proves the lemma.
We now show that the bias is upper bounded by multiplicative factor of the variance of the input vectors, as long as there is at least one unclipped honest vector.
Lemma B.4 (Bias due clipping). C
O.
0,
n/2, and S C [n], |S| n f. if
SS \ S. 2 then
S
Ig
1sll
||00
F3
S
S.
iES
19

---

Published as a conference paper at ICLR 2025
Proof. We assume throughout the proof that [Sc] 0. Otherwise, if [Sel 0. the bias is 0 and the statement is trivially true.
By Lemma
B.3 we have
S
I -
(1|=:|l
C)
(8)
sES.
We distinguish two cases: ||
S C. and
||s||| > C. the first case we have that
< ||
C
|
||s|||-
Substituting the above in 8 we find
S
S
| Jsl
- |=sl)) <
[1|03|1 |Ts1))
|S|
|s
IES.
IES
Using the reverse triangle inequality, we have that (1/2;|1 -
| )
||: =s| This implies that
|Tg Vs12 -
15cl
Σ
[Tsl)² 5
|Scl
1
Σ
||
=ssll
1
S \ Sel
S
FES
EES
This proves the result for the first case.
Consider now the second case, i.e || > C. Noting that we assume that |S Sel 2 1 and using
Young's 's inequality with [SVS. we find, for any i E S.,
18.1
(||=3|| - C²² = (||=.ll | + || C)2
- (1 + (1 - | 11) + (1 + (/c)( - -)²)
S + |S) Scl
(1|= || - | + Sc + |S\ Scl
[|ās| C)
S Sel
|Scl
Recall from I that S. = {i E S, |
> C}. This implies that |Sel + 1S Sel = -|S Therefore
(|==]| C)² < |S|
(1|=;| |=sl)) +
|| -C²)
(9)
S Sc
S.
Substituting in
we find
[S&l
1
(|ara/l - ||= S [|>5|] - -c)²)
|
Vsll
|S|
| 2
\ Sal
VES.
|Scl
(1| |>>>||> + (1|>>| - c)2
(10)
|s|
S 1 Scl
iES.
Since ||>|||
C, we have for any E Se
0 0 |
C [ - ||aa||
Therefore
|S \ Scl (|æ=|| - C)² < Σ
(|ı>|| ||>1|)2²
iES
Which gives the bound
(| - -7)² < |S S.
Σ
(|T 1|x.11)
(LI)
iESYS.
Substituting
in 10p, we find
| Fsll <
[S.]
1
Σ
(1<x:|| |T + |.S Sal
Σ (||xa|)
| 1))
|S|
[S Sal
iES.
Vesiis
|.Srl
|5cl
Σ
[(1=:1)
2|=
Σ
||=; xsl1
iES |S\
S.
|S|
S \ S.
|S|
ieS
This proves the result for the second case and concludes the proof.
20

---

Published as a conference paper at ICLR 2025
PROOF OF LEMMA B.1
Let us recall the lemma below.
Lemma B.1. Let C E IRt and F be (f, k)-obuut aggregation rule. Consider arbitrary set of n vectors ž1, .,,,..,,,y In E TR and an arbitrary 5 _ [n] with ||| f. Let Se denote the set of
indices of clipped vectors in S, Le., fi S, || C}- S Sel 1, then
Fo
- Tsll v
Es
S
iES
where R = K. +
[5.]
Proof. We assume throughout the proof that [S.] > O. Otherwise, the statement is trivially true by (f, roobuuseess of F and the fact that the vectors in S remain unchanged after the clipping operation.
Consider first the case x = 0. Since & 2 2- we have that f 0. Recall that we denote
Y/ (x;) and Us [s] Eies Vs. Since 0, the output of F will correspond to the average of its input, which implies that
| Cli In) Jsll F((1..... ...) Fsll = 0.
Therefore
Fo Clipo(EI....,, Vs.
We find then
| Clipo kn) T ||Ms Es Es|
The result for the case 0 follows from lemma B.4
Suppose now that x > 0. Using Young's inequality with c x|
18.1
we find
|F (li mn) -Esl F Clipo(en.....
Us + Us Issl
+ F Clipo Fsl1 2 (1+
1 Fsl
(12)
On the one hand, by (f, (ff.)))ro robuuustsss of F, we have
(1 +1+ F Clipo ..,,,,,, (li.,()).....,.). -- (1 [(n,, ......... vn)) Vsll'
< (1 + (1+c)
Σ
1
Us
12
|
iES
S
1
k
1ly.
(13)
S Sz
S
iES
On the other hand, we have
Us! 12 (1 (1+ n: # Scl [So]
x (
|Sa|
|5 \
(1 1/4) |as
||Ts Usll2 =
||
Us|l
Scl
[Scl
(14)
Substituting 13 and 14 in 12
we obtain that
JScl
1
|S Sc
FF o Clip mn) Eg < K +
11
Fsll
| Us
I
S.
[.S]]
iES
(15)
Proposition dAllouah et al. 2023a
21

---

Published as a conference paper at ICLR 2025
We consider below the two cases
|
C' and |
C' separately.
In the first case, use the the first part of lemma B.2 and lemma
B.3 obtain that
|S
Sel
Dsll2
+
[E
Vsll
1S
|.S]
SES
1
15 Sel
ss|l
(1
C)
(1
|| - C)²
|S|
S
|S|
S
JES.
|Scl 1
24 - Es|l
E(1=a11- -
Σ
|| - E3 11?
S
|||
S|]
S
iES
iES
SE
This proves the result for this case.
Consider the second case, ie || C. Following the proof of corollary B.4 until 10 we have
Sel
1Ts Usll2 s
Σ
(11a3 - |==l)) (1 0)3
|S|
\ Sel
iES.
Therefore,
J Sel |
\
1
[3g
Us|1? <
(||=;|| - |> + [1 C)2
[S]
[S Sel iES.
1 S
|.S Sel
S
|| 2 +
[| - C)
|S|
S.S.
Using the above in conjunction with lemma the second case, which concludes the proof.
B.2 for the case
||
C 15) proves the result for
C PROOFS OF THE RESULTS IN SECTION 5
In this section, we first prove the Bounded Aggregation Output property of ARC in Lemma 5.1 and show that the other SOTA aggregation rules do not satisfy Lemma C.I Then, to prove Theorem 5.2 we first prove Lemma
C22 We assume throughout this appendix that for any set of
vectors I1,..., Fn E Rdd F (I1...... Fr.
I maxie(1]
|| This assumption can be made without
loss of generality, see Appendix C.I
Lemma 5.1 (Bounded Output). Let F be an (5, k)robusttt aggregation method. For any vectors T1, Fn Rdd and set S C [m]] such that |5| = n J. ||F ARC(x),..., Tx)]l S maxies |
Proof. Without loss of generality and for the sake of simplicity, let us suppose that the vec- tors Z1,..., In are indexed such that |æ||| 2 ||= > ... 2 ||r,]|. Let (fI,...,ā.) Zn). = ARC(21..... vx)) be the clipped version of these vectors after applying ARC.
Case 1: When f = 0, S = [n] and we clip all the vectors by || maxies ||as|]. hence for any J. || S max |ar:]. Using the fact that for any set of vectors æ1..... In Rd.
|F (Z1,..... Zn. ll S max || we have
FF ARC(EI.... = | 2.
max
||
max
|
(16)
JEIn]
ES
Case 2: When 0< f < 2. as presented in Algorithm 2
ARC clips all the vectors 21...., Ty, to
|| || where à == [2 (n f)]- Hence, for any j E [n].
| || < |
(17)
We have that l: + 12 (n [] + 1 24(n J)
22

---

Published as a conference paper at ICLR 2025
One can show that
2f (n f) - f f(1 2f _)
0, Aʃ E 2
(18)
Hence, 3f (n-f) f. which gives k k > f. and since is + is an integer. have ++1 f n Hence we know that at least f + 1 vectors have their norm greater equal to the clipping threshold
C |
b || 2
|
||
at least
1 vectors
at most
vectoos
Hence, at most n f - vectors will not be clipped. For any subset of S C [n] of size n at least one of the vectors has its norm equal to the clipping threshold (i.e. maxtes ||a | or will be clipped (i.e. maxęs || >
|x++1|] [D. Hence, we have that
max iES
| 2 ||x++1|l
(19)
Combining (17) and (19), have that for all [n].
|
S max
||ax|||
VES
Using the fact that for any set of vectors 2i.... In E Rd, | .... S max,e(m] | have
we
FF o ARC(Z)...., [( E,)Il s max
||ر
S max |ل
(20)
JE[m]
ES
Lemma C.1. For any aggregation rule F (CWTM, CWMed, GM, MK, CWTM CWMedoNNM, GMoNNM, MK.NNM), there exists f E [0, ) a aset oe 21,..., and a subset C [n]. |S] such that
In) E max |x;||
(21)
EES
Proof. Let us consider (I1, xz) = ((0, 1). (1,0), (1, 1)), and S= (x1,22)
For F E (CWTM, CWMed, GM). we have [2,,,,,2, = [I(1,1)]I = V2 maxies ||~||| ||ا||| 1.
For F E (MK, CWTM NNM, CWMed o NNM, GM NNM, MK NNM), we have [[ 22, m3) = (0.55 1)| vI.25 > maxies ||x;|| = |||||| =.
Lemma C.2. Let be (f. -)rbbut. Let Do and p be real values such that Cx((,) Ci S A. and maxiex [L,(0,) exp (- der T.) p. 1f7 min { (AAo) T }}. then
T (V
2004
Σ
T + 5x (G2 + B2
T
1=1
Our proof for Lemma C.2
relies on the following sub-result.
Lemma C.3. For all i [T). we obtain that
max
V., < exp (TLT) max (V,,
NEW
23

---

Published as a conference paper at ICLR 2025
Proof. Consider an arbitrary E [T]. Let (Z1,..., In) ARC
St 9i ) As n > 2f and
(1)
[7]] = n - f. the clipping threshold C' used in ARC (see Algorithm is bounded by maxęe
9: (0)
(see 19 Lemma 5.1 Therefore.
max sE(n]
| S max FERL
96
max SEH
(0,)l
(22)
Since for any set of vectors 21,..... E RR, |F ..., an)ll S maxie[m] obtain that
| from 22 we
| = F ARC of 1o.ry sh )
max sE|n]
|x,|| S max [L,(0,))
Recall that 2+1 0 RR. Thus, from above obtain that
|| - 0.1l $ Y max
[VC,
(23)
E
Due to I.-Lipschitz smoothness of (0) for all E H. the above implies that
VL.(0.+11 - (L.( < 7 max iEN
[V)10,)
Vi H.
This, in conjunction with the triangle inequality, implies that
VLC(0++) s ||,C, + + max [VL,(()l))
Vi E H.
Therefore,
max EEH
(C,(0+))) S max VV.(0,) + max EEH
IVC (1 L)
max
|VC(
iEH
EE
As was chosen arbitrarily from [T]. the above holds true for all E [T]. For an arbitrary T T [T],
using the inequality recursively for t r,.... obtain that
VL. $ + +D max max EEM
VVL(0,, S (1+ max
(L)(0,,)
EE
NEH
Since (1 T.) < exp (TT,T), the above concludes the proof.
We are now ready to present our proof Lemma C.2
Proof of Lemma C.2
For simplicity, we write Lx as L throughout the proof.
Consider an arbitrary E [T]. Due to I--Lipschitz smoothness L(0), we obtain that
L
[(0,+1) < ((0,) + (0.11 -,, vC(e,)) + 00+1 0,112
Substituting 04+1 = 02 - RR, and using the identity: 2 (a, b) = ||a|| + ||b||2 - ||a - b11 we obtain
that
C(0(41) S L(8,) ? |VC(0,11 ? |R VC(0))1 2 (1 7L) |1
Since 7 3,1 (1 2 0. Therefore, from above we obtain that
((0 < C(0,) VC + -C
Recall that is chosen arbitrarily from [T) Thus, the above holds true for all t E [T]. Taking summation on both sides from i to T we obtain that
[V(,0)) < L(,)) - [(0
RR VL(A,)11
1=1
24

---

Published as a conference paper at ICLR 2025
Multiplying both sides by 2/(rT) we obtain that
T Σ VL(00)) 2 (c(()) [(0T+1))
1
T Σ R VL((,))
7T
Note that [(0,) [(0T+1) = ((0,) - -6" - (C(00++) - s [(0,) - l S D.. Using this above obtain that
T Σ
26. |2((0)11 S
Σ R VC(O))
7T
Recall, by Theorem | V2(0,))
3.2
that F ARC is (robust Therefore, by Definition 2.4 EH (2, (2,)1) for all t. Using this above we obtain that
I
3x
H
T
T
I
24, TT
3k
1
V2(0,)1
[VL(0,) - V
(24)
T
T
H
1=1
Note that, since 7
and (1,(0)))1 S exp
(-
k
by Lemma C.3
we have
L
max E
(L,( 2
exp
max iEN
VL.(0,1 s..
e [Z].
This, in conjunction with triangle inequality, implies that
VL S
1
Σ EIVC( sp. [T].
77
Therefore, under (G, -gaaddieett dissimilarity, for all / E [T].
- x +
7
Using this in 24
we obtain that
1
Σ IVC
2A. TT
+ 3n (G2 + B²p²)
(25)
T
Consider the two cases: (i) T > implies that
Ael and (ii) T KG
A.L
case (i), 7 nO Using this in 25
kG
T T
VC(O)
< 2k + 3x (B²+ < 5x (G² + B2
(26)
In case (ii), + Using this in (5 implies that
1 T
20OL
Σ
<
T + 3x (G² + p²
(27)
T
2m1
Combining 26 and 27
concludes the proof.
We now prove Theorem C.4 stated below, which immediately implies Theorem 5.2 Specifically, Theorem 5.2 follows immediately from Part of Theorem C.4 upon substituting D.
Theorem C.4. Suppose > and there exists Ç E R+ such that max ( S S. Let E (CWTM, CWMed, GM, MK), 7 = min (xxz)) 4, + and T 2 Act. Consider an arbitrary real value &o E (0, 1). Let p = exp (1-Ew)0²
(2+B²)a Ao L Ç. Then, the following holds true:
1. If (1 B), where & Col, then, E VL (0)] < VG. (G. E
25

---

T Published as a conference paper at ICLR 2025
|| (0)
2. I/BP S f/n < 1/2, then IE
B(G
In order prove Theorem C.4 we first obtain the following corollary of Lemma C.2 and Lemma 2.6
Corollary C.5. For the parameters given in Lemma achieves
C.2
if
then Robust-DGD ARC NG
AoL
[1]]= S 5% min fc + B²p²
G
BB max (1 kB²),
where E [-] denotes the expectation over the choice of
Proof of Corollary C.S.
For simplicity, we write LH as L. throughout the proof.
Since T
A.b
xG S T. Therefore, from Lemma C.2 we obtain that
KG
|VC(0,) S 5x (G² + B²P
(28)
In the specific case when xB²
1, y
A. RG from Lemma 2.6 we obtain that
2A
kG²
3xG
VCOM S
(29)
T
(1
RB kyT
1
RB
xB
Combining (28 and
29
obtain that
1
[VC(0)1 s 5x min
{ {o+ + B²p'
BBPB'
G
T
1- BB²
Since I [|VC())) = E [V(22) (see Algorithm I, the above concludes the proof.
We ready prove Theorem C.4 Recall that
(2(5/n)
BP
2 B
Ea
(2+
B2)(
and
B²p²
(G, B) 640
1 1
1+ G
B²
Proof of Theorem C.4
For simplicity, we write Lu as throughout the proof.
In the proof, we substitute BP
24
We first consider the case when L 1-g
In this particular case,
n 2-Br.
Ba
B²
n
f2
2 1
f.
1- g 1-
Therefore, thanks to Lemma
2.5
(f, fi)-uuuust with
16f
1
1-
5
16(1 {)
1+ 1-5)
16(1 () (1+
R < n f
1+
B
=
1 B +
B2
<
1 B²
B
S ko - E),
where Ko =
Bz (1 +
16
1 )² Also, recall from the limitations of (f, -obuusttsss in Section that
f
f
1 E.
K
n 2--22
2f
n
2 2 B
26

---

Published as a conference paper at ICLR 2025
Summarizing from above, we have
1- Eo
S S ko(1-E) E)).
(30)
+ B
This implies that
0 exp
(2+ (9)
(1- G2 (1-E.)7"
L < exp
) 5.
Therefore, since [V, < & for all E H. the condition: max (0,( exp L) in Lemma
C.2
is satisfied. Thus, by Corollary C.5 and (30)
obtain that
E [[ & 55 - ()2 B²p²)= 5l
() + B²P²)
fG²
(31)
fG2
(2 B²)
n=(2+B91
Since = B+ we obtain that
5kr - (G) + B²p))
E(2 B²)
B²p²²
5k E) B² p²)
5%%
1+ G
(2 B²) (2+B²)
FG2
G² - E)
n-(2+B2)f
Substituting Ko from above, we obtain that
51 (G² + B²
2 B²
1
(1 1+
B² B²D²
80
1 1+ B²
FG2
1+ B2
G2
a-(2+B2)
1
(1
B²p²
S $100
160
1
E.
Ba
Substituting from above in (31 concludes the proof for the first part of Theorem C.4
The second part of Theorem C.4 follows immediately from the first inequality in using the fact that Ko (1 {) S Ko. This concludes the proof.
C.I ASSUMING || (I1.... ................................ zn)il maxig[m] || is WITHOUT Loss OF GENERALITY
Recall that we assume || (#1,...,, 2n S max,e[]] ||x for all set of vectors 21, Fn Rd. In case this is not true, we can instead use the aggregation rule F given by
F' (ri,..,, In) = clipe (F (#I,...,, xn)), where C = max ||0|||
iE(m]
This modification to the aggregation rule does not affect the learning guarantee. Specifically, due to the non-expansion property of c-)p for any non-empty set C [n], we have
|t (II,..., (n) æ s ||F (21,....,,, Fn) æsll
where Es = 1 2. Thus, if is (f, rrrbuut then F is also (f. k)-rousst. Hence, we can 24. FES
make the above assumption on | (I1,..., Fn)Il without loss of generality.
27

---

Published as a conference paper at ICLR 2025
D COMPREHENSIVE EXPERIMENTAL SETUP
In this section, we present the comprehensive experimental setup considered in our paper.
D.1 DATASETS AND HETEROGENEITY
In our experiments, we consider three standard image classification datasets, namely MNIST (Deng 2012), Fashion-MNIST (Xiao et al. 2017), and CIFAR- 10 (Kizzhesky et al. 2014). To simulate data heterogeneity in experiments, using a Dirichlet distribution of parameter a (Hsu et al.] (019a), as done in (Hsu et al. 2019b] Allouah et al. 2023a Farhadkhani et al.) 2023). The smaller the a, the more heterogeneous the setting. In our empirical evaluation, we set a E {0.1. 0.5, 1} on (Fashion-)Mie {0.05, 0.075, 0.1, 0.2, 0.5} on CIFAR-10 (refer Figure 6p. Furthermore, on MNIST and Fashion- MNIST, we also consider an extreme heterogeneity setting where the datapoints are sorted by increasing labels (0 9) and sequentially split equally among the honest workers.
make the honest workers sample from the datasets
and a E
The input images of MNIST are normalized with mean 0.1307 and standard deviation 0.3081, while the images of Bushion-MNISS are horizontally flipped. Moreover, CIFAR-10 10 is expanded with horizontally flipped images, followed by per channel normalization with means 0.4914, 0.4822, 0.4465 and standard deviations 0.2023, 0. 0994 0.2010.
2004
Worber
Horest
Honest Worker
(a) a 0.1
(b) 0.5
(c) (=)=11
12 14
Honest Worker
Honest Worker
(d) 0.075
(e) a = 0.2
Figure 6: Distribution of labels across honest workers MNIST (row 1) and CIFAR-10 (row 2).
D.2 ALGORITHM, DISTRIBUTED SYSTEM, ML MODELS, AND HYPERPARAMETER
We perform our experiments using Robust-DSGDD, order-optimal robust variant of Robust-
DGD (Allouah et al. 2023a) (see Algorithm 3) in distributed systems of varying sizes. On MNIST and Fashion-MNISTT we train convolutional neural network (CNN) of 431,080 parameters with batch size = 25, T = 1000, = 0.1, and momentum parameter / = 0.9. Moreover, the negative log likelihood (NLL) loss function is used, along with an Eg-regularization of 10 On CIFAR-10, we train a CNN of 1,310,922 parameters. We set = 50, T = 2000, 3 = 0.9, the NI.I. loss function with an e
and 7 0.05 decaying once step 1500. Finally,
28

---

Published as a conference paper at ICLR 2025
regularization of 10-2. In order to present the architectures of the ML models used in experiments, we adopt the following compact terminology introduced in Choffrut et al. (2024).
L(#oouppts)) represents fully-connected linear layer, R stands for ReLU activation, S stands for log-softmax, C(#channels) represents a fully-connected 2D-convolutional layer (kernel size 5, padding O, stride 1), M stands for 2D-maxpool (kernel size 2), B stands for batch-normalization. and D represents dropout (with fixed probability 0.25).
The comprehensive experimental setup and the architecture of the models are presented in Table 2
Algorithm 3 Robust Distributed Stochastic Gradient Descent (Robust-DSGiD)
Input: Server chooses initial model 0, Rd. learning Roxd - Rd, momentum parameter B E Rt. Each honest worker Wi sets an initial
RR,, robust aggregation
momentum mg (6) = E Rdd.
fo to do
Server broadcasts 0, all workers.
for each honest worker w; in parallel do
Sample random data point 200) uniformly from Dj,
Compute stochastic gradient 9. ve(0,, (1)) (+).
Update momentum: m == (1 8)g + Bmm
(8)
Send m to Server.
(4)
// An adversarial worker wy can send an arbitrary vector in Rd for mi (3)
end for
Server computes R; = (m ....: mi (n)
Server updates the model: 0.+1 0r 7 Rs end for
Output: Server outputs 0 chosen uniformly at random from .0..... 0r}
Dataset
(FASSI
CIFAR-10
Data heterogeneity
a E {0.1, 0.5, 1} and extreme
a E 0.075, 0.1, 0.2.
Model type
CNN
CNN
Model architecture
CC20)RR-MCC10O-R-MM L(500)-R-L(10)-S
G.2339--C(44RBBBBCAA))A)AB (CC12))- B-M-D- L(128)-R-D-L(00-
Number of parameters
431,080
1,310,922
Loss
NLL
NLL
l Iz-regularization
10-4
10-2
Number of steps
T = 1000
T = 2000
Learning rate
0.1
0.05
t S 1500
7
0.00082
1500 < f S 2000
Momentum parameter
0.9
0 0.9
Batch size
b 25
= 50
Table 2: Comprehensive experimental setup.
29

---

Published as a conference paper at ICLR 2025
D.3 BYZANTINE ATTACKS
In our experiments, the adversarial workers execute five state-of-the-art adversarial attacks from the Byzantine ML literature, namely sign-flipping (SF) (Allen-Zhu al., 2020), label-flipiigg
(LF) (Allen-Zhu et al. 2020), mimic (Karimireddy et al. 2022). Jall of empires (FOE) (Xie et al. 2020). and a little enough (ALIE) (Baruch et | 2019). The exact functionality of the attacks detailed next. In every step t, let my be an estimation of the true honest momentum at step t. In our experiments, we estimate my by averaging the momentums sent by the honest workers step of
[ Σien m; m where mi is the momentum computed by Robust-DSGD. In other words, mh honest worker w; in step t.
SF: the adversarial workers send the vector -7, to the server.
LF: the adversarial workers compute their gradients on flipped labels, and send the flipped gradients to the server. Since the original labels / for (Fashion- MNNIST and CIFAR- 10 are in {o.... ..., 9}. the adversarial workers execute label flip/rotation by computing their gradients on the modified labels 1' = 1.
Mimic: the adversarial workers mimic certain honest worker by sending its gradient to the server. In order to determine the optimal honest worker for the adversarial workers to mimic, we use the heuristic in Karimireddy al. (2022).
FOE: the adversarial workers send (1 mm, in step to the server, where > 0 is fixed real number representing the attack factor. When r = 2, this attack is equivalent to SF.
ALIE: the adversarial workers send m, + тo, in step to the server, where т 2 0 is a fixed real number representing the attack factor, and d is the coordinate-win standard deviation of m,
Since FOE and ALIE parametrized by T E IR, implement in experiments enhanced and adaptive versions of these attacks, where the attack factor is not constant and may be different in every iteration. In every step f, we determine the optimal attack factor Tr through grid search over predefined range of values. More specifically, in every step i, Ti takes the value that maximizes the damage inflicted by the adversarial workers, i.e., that maximizes the lg f2-norm of the difference between the average of the honest momentums M, and the output of the aggregation RG at the server.
D.4 BENCHMARKING AND REPRODUCIBILITY
We evaluate the performance of ARC compared to no clipping within the context of Robust-DSGD. Accordingly, choose Fo NNM as aggregator in Algorithm 3 where F (CWTM, GM, CWMed, MK) is an aggregation method proved to be (J, k)-robust (Allouah et al. 2023a). Pre-composing these aggregation schemes with NNM provides them with optimal (J, roobuuttsss (Allouah et al. a023a). As benchmark, we also execute the standard DSGD algorithm in the same setting, but in the absence of adversarial workers (i.e., without attack and 0). We use the metric of worst-case maximal accuracy to evaluate the performance of our algorithm. In other words, for each of the aforementioned five Byzantine attacks, we record the maximal accuracy achieved by Robust-DSGD during the learning under that attack. The worst-case maximal accuracy is thus the smallest maximal accuracy encountered across the five attacks. As the attack executed by adversarial workers cannot be known in advance in a practical system, this metric is critical to accurately evaluate the robustness of aggregation methods, as it gives us an estimate of the potential worst-case performance of the algorithm. Finally, all our experiments are run with seeds I to 5 for reprodueibility purposes. We provide standard deviation measurements for all our results (across the five seeds).
30

---

Published as a conference paper at ICLR 2025
E ARC vs. STATIC CLIPPING
In this section, we present empirical results on static clipping when used as a -re-aggegttion technique in Robust-DSGD, and compare its performance to our proposed adaptive algorithm ARC.
E.I COMPARISON WITH STATIC CLIPPING ON MNIST
On MNIST, execute Robust-DSGD in distributed system composed of 15 workers, among which f E {3. } are adversarial. We consider three different levels of heterogeneity; moderate (ar 1), high (a- 0, 1), and extreme (as explained in Appendix(D) D). In experiments, we examine a wide range of static clipping parameters C' {0.02, 0.2, 2, 20
1.00
Test Accuracy
Test Accuracy
0.75
75
0.50
50-
DSD - 0)
0.25
25
CNNT NNN
CWTT C
0.00
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(a) Sign-fipping (SF) (Allen-Zhu et
2020
(b) Label-fiiping (LF) (Allen-Zhu et al.
2020
Figure 7: Impact of pre-aggregation clipping, specifically static clipping with C = 2 and our adaptive clipping algorithm ARC, on Robust-DGD with CWTM NNM, under the SF and LF attacks. We consider the MNIST (Deng, 2012) dataset distributed amongst 10 honest (non-adversarial) workers with extreme heterogeneity, and there are three adversarial workers.
Unreliability due to the attack. First, the efficacy of static clipping is significantly influenced by the type of Byzantine attack executed during the learning process. To illustrate, while C' = 2 exhibits the best performance under the SF attack (Allen-Zhu et al. (2020). depicted in Figure 7 it leads to complete collapse of learning under LF (Allen -hu et al.) 2020). Consequently, identifying a static clipping threshold C' that consistently performs well in practice against any attack is difficult (if not impossible). This highlights the fragility of static clipping, as the unpredictable nature of the Byzantine attack, parameter that cannot be a priori known, can significantly degrade the performance of the chosen static clipping approach.
Unreliability due to the heterogeneity model. Second, the robustness under static clipping is notably influenced by the level of heterogeneity present across the datasets of honest workers. To illustrate this impact, we present in Figure the performances of Robust-DSGD for different levels of heterogeneity (moderate, high, and extreme) and different values of C. In Figure 2a C = 2 emerges as the best static clipping threshold when the heterogeneity is high whereas C 20 appears to be sub-optimal. On the other hand, under extreme heterogeneity. the accuracy associated to C = 2 diminishes drastically while C 20 becomes a better choice. Intuitively, in heterogeneous scenarios, honest gradients become large in f2-norm, due to the increasingly detrimental effect of Byzantine attacks. Consequently, we must increase the static clipping threshold. This highlights the intricate dependence of the performance of static clipping on data heterogeneity, and emphasizes the necessity to fine-tune static clipping strategies prior to the learning.
Unreliability due to the number of adversarial workers. Last but not least, the number of adversarial workers ff also affects the efficacy of static clipping. As seen in Figure 2 C = 2 leads to the highest accuracy among static clipping strategies when f = 3 in high heterogeneity, but cannot be used when f = as corresponding accuracy drops below 50% (see Figure 2h).
Overall, our empirical findings reveal that there is no single value of C' for which static clipping consistently delivers satisfactory performance across the various settings. We have also shown that the performance of static clipping is greatly influenced on typically uncontrollable parameters, such as data heterogeneity and the nature of the Byzantine attack. Indeed, it should be noted that explicitly estimating these parameters is challenging (if not impossible) in distributed setting. First, since the server does not have direct access to the data, it cannot estimate the degree of heterogeneity. Second, as (by definition) adversarial worker can behave in unpredictable manner, cannot adjust C
31

---

Published as a conference paper at ICLR 2025
to the attack(s) being executed by the adversarial workers. This highlights the necessity for robust clipping alternative that can naturally adapt to the setting in which it is deployed.
In contrast to static clipping, ARC is adaptive, delivering consistent performance across diverse levels of heterogeneity, Byzantine attacks, and number of adversarial workers.
Adaptiveness. ARC dynamically adjusts its clipping parameter C based on the norms of honest momentums at step t, avoiding static over-clipping or under-clipping. This adaptability is evident in Figure 8 where C₁ consistently decreases with time under all attacks, expected behavior when reaching convergence. Moreover, Figure 8 also illustrates that any surge in the norm of the honest mean corresponds to direct increase in C, highlighting the adaptive nature of ARC.
Robust performance across heterogeneity regimes. The efficacy of our solution is illustrated in Figure 2 showcasing consistently robust performance for all considered heterogeneity levels. Specifically, in scenarios of moderate heterogeneity where clipping may not be essential, ARC matches the performance of No clipping as well static strategies Figure 2a shows that under high and extreme heterogeneity, ARC surpasses the best static clipping strategy terms of accuracy, highlighting the effectiveness of our approach.
and C' 20. Conversely,
Robust performance across Byzantine regimes. ARC exhibits robust performance across diverse Byzantine scenarios, encompassing variations both the type of Byzantine attack and the number of adversarial workers f. As depicted in Figures 7 a ARC consistently yields robust performance, regardless of the Byzantine attack. In extreme heterogeneity with f = 3, ARC maintains an accuracy of 75%, while C' = demonstrates a subpar worst-case accuracy of 25% (also refer to Figure 7b). Furthermore, despite the increase in the number of adversarial workers to f 4, ARC remains the up-performing clipping approach among all considered strategies.
This analysis underscores the empirical superiority of ARC over static clipping methods, eliminating the reliance data heterogeneity and the specific Byzantine regime. Similar trends also observed in Figure 9 when executing Robust-DSGD using other aggregation methods such as CWMed NNM, GM NNM, and Multi-Krum NNM.
ALIE
SF
C₁
C
7.5
xxll
5.0
2.5
0.0
200
400
600
800
1000
0
200
400
600
800
1000
FOE
LF
C₁
7.5
1xl
5.0
2.5
0.0
200
400
600
800
1000
200
400
600
800
1000
Figure 8: Evolution of the adaptive clipping parameter C, of ARC compared the norm of the honest mean during the learning on heterogeneous MNIST (a 1). There are f = 3 adversarial workers among n 15. CWTM NNM is used as aggregation.
32

---

Published as a conference paper at ICLR 2025
100
extreme
0.1
80
Accuracy (%6
50
20
0.02
C=0.2
C-2
C- 20
No clipping
ARC
(a) CWMed NNM
100
Test Accuracy
70
40
10
0.0.2
C-
C-2
20
No clipping
ARC
(b) GM NNM
90
Test Accuracy
60
30
10
clipping
(c) MK NNM
Figure 9: Impact of the clipping strategy on the worst-case maximal accuracy achieved during the learning against five Byzantine attacks on heterogeneous MNIST, with f = 3 and n 15.
33

---

Published as a conference paper at ICLR 2025
E.2 COMPARISON WITH STATIC CLIPPING ON CISHION-MNISH
On Fashion-MNIST, we execute Robust-DSGD a distributed system composed of n 15 workers, among which f - adversarial. See Figure T0
Test Accuracy
C-0.02
C-02
C+2
C
No ciiping
ABC
C-
C+2
C-
cipping ABC
extrew
Accuracy
Test Accuracy
10
C-
C-02 C
C- C-02
C+2
C=
ARC
Figure 10: Impact of the clipping strategy and heterogeneity level on the worst-case maximal accuracy achieved during the learning against five Byzantine attacks Fashion-MNIST. f 3 and n 15, and the heterogeneity levels considered are extreme, high (a = 0.1), and moderate (a = 1). Aggregation methods used: CWTM NNM (top left), CWMed NNM (top right), GM NNM (bottom left), and Multi-Krum o NNM (bottom right). DSGD reaches 85% in accuracy in all settings.
34

---

Published as a conference paper at ICLR 2025
E.3 COMPARISON WITH STATIC CLIPPING ON CIFAR-10
For this particular experiment, we execute Robust-DSGD using the ResNet-18 (He et al. 2015) model, in distributed system comprising n 9 workers among which {1, 2] are adversarial. We set = 128, 7 2000, 3 = 0.9, and = 0.1 decaying once by 10x at step 1500. Finally, we use the cross- entropy loss function with an é2 regularization of 5 10 4, See Tables
and
Attack
C== 0.05
C'= 0.5
C'= 5
C' 50
No clipping
ARC
FOE
26.4 + 1.2
52.6 + 2.0
76.4 +: 5.4
47.0 8.0
43.0 + 6.2
79.1 + 1.6
ALIE
34.6 + 1.3
43.3 - 1.1
47.2 3.4
47.2 = 4.2
47.2 + 4.2
51.8 + 3.5
LF
33.7 +: 1.5
58.4 + 1.8
83.6 +: 1.2
85.7 + 0.5
85.9 + 0.4
81.5 + 1.4
SF
32.3 + 1.4
57.9 1.2
77.2 + 4.6
68.6 8.5
66.4 + 9.0
82.0 + 1.1
Mimic
38.2 + 1.6
68.3 1.4
85.6 0.42
85.7 + 0.4
85.7 + 0.4
85.4 0.5
Worst-case
26.4 + 1.2
43.3 1.1
47.2 3.4
47.0 8.0
43.0 + 6.2
51.8 3.5
Table 3: Maximum accuracy (%) achieved by CWTM o NNM on CIFAR-10 under moderate heterogeneity (a 1). for various clipping strategies and attacks. There are 2 adversarial workers among = 9. We highlight in blue the highest accuracy achieved per attack (i.e., per row).
Attack
C 0.05
C= 0.5
C = 5
50
No clipping
ARC
FOE
28.9 + 1.7
56.8 + 1.9
75.6 + 2.8
35.5 + 11.6
34.9 + 12.2
75.9 + 3.0
ALIE
34.9 + 1.3
43.4 1.0
47.4 + 4.1
44.9 + 3.8
44.9 3.8
54.6 3.6
LF
33.7 + 1.4
58.4 1.8
77.4 12.9
85.8 + 0.6
85.6 = 0.7
80.5 + 1.8
SF
32.5 + 1.4
57.5 + 1.4
77.7 5.0
63.0 + 12.0
55.4 + 18.9
82.5 + 0.3
Mimic
38.1 + 1.3
68.5 1.4
85.5 + 0.5
85.9 = 0.5
85.9 = 0.5
85.4
Worst-case
28.9 + 1.7
43.4 1.0
47.4 + 4.1
35.5 + 11.6
34.9 12.2
54.6 = 3.6
Table 4: Maximum accuracy (%) achieved by CWMed o NNM on heterogeneous CIFAR-10 (a = 1), for various clipping strategies and attacks. There are ʃ = 2 adversarial workers among 9. We highlight in blue the highest accuracy achieved per attack (i.e., per row).
35

---

Published as a conference paper at ICLR 2025
F PERFORMANCE GAINS OF ARC OVER ROBUST-DSGD
In this section, we present additional experimental results demonstrating the performance improve- ments achieved by ARC in Robust-DSGD on the MNIST, Fashion-MNIST, and CIFAR-10 datasets. These results could not be included in the main paper due to space constraints.
F.1 MNIST
F.1.1
INITIAL SYSTEM (MAIN PAPER): 10 HONEST WORKERS
We consider training on MNIST in a system comprised of n f 10 honest workers. These results complement the ones presented in Section of of the main paper.
100
100
CWMiidd MMM
Mulh Chum NAH
Vulu Suu MAM ARC
Test Accuracy
Test Accuracy
60
60
20
20
CWiteed MMM
CWWedd 18/ ARC
MiBiicmm - ARY
M.Birom
3
5
Number of adversarial warkers f
Number adversarial workers
extreme
(b) 0.5
100
CWTT NHH
CANNeS KNM
CWTV MM- ABCC
CANtec NMM ARC
80
80
-tran WIN
Test Test Accuracy
Test Accuracy
40
40
20
4
2
6
Number adversarial workers
Number adversarial workers
(c) 0.1
(d) = 0.1
100
100
80
Test Accuracy
Test Accuracy
60
40
MIN
MB3 AR
Kit.Kum A8P 4A2
Number of adversarial workers f
Number of adversarial workers
a=)==1
(f a
Figure 11: Worst-case maximal accuracies achieved by Robust-DSGD when using ARC compared to no clipping, on wawrrroennoouyydiiitibiuuee MNIST with 10 honest workers. We fix the heterogeneity level, and vary the the number of adversarial workers f.
36

---

Published as a conference paper at ICLR 2025
100
100
80
Test Asstuucy
Test Accuracy
60
40
40
20
CWTH - NMM
20
CUTH -MUM
OWTN . NAM ARC
CUUT NNV ABC
DM 1939
GM MIN
CM - 181M ARC
GM MIN ARC
1
a 0.5
a - 0.1
extreme
1
a 0.5
0.1 Heterogeneity Level
extreme
Heterogeneity Level
(a) =3
(h) f
100
100
100
160. Accurscy
Accursyy
40
40
40
20
20
20
Notkaa
0 5.5
0 0.1 Feteragenetty Level
0.S
0 0.1
eoltern
1
D 0.1 Hetorogencyy Level
0.5
eshreme
Heterogenchty Level
(c) ==
(d)
f
(e) f
Figure 12: Worst-case maximal accuracies achieved by Robust-DSGD when using ARC compared to no clipping, on heterogencousll-disrrbbuce MNIST with 10 honest workers. We fix the number of adversarial workers f. and vary the heterogeneity level.
100
100
Test Accuracy
75
Test Accuracy
75
CW/TM NNW
DSGD IT O)
CWTM NNIM ARC
50
DSGD - GI
50
CWTH ANM
CWTM- NWM ARC
0
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(a) ALIE
(b) SF
100
100
Accuracy
Test Accuracy
75
75
CW/MM: NNIM ABC
NNM
50
DSGD
50
GMs NNM ARC
CWTH NNM EWTM- NMM ARC
25
GM NMM
25
0
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(c) LF
Mimic
Figure 13:
Performance of Robust-DSGD when using ARC compared to no clipping, on MNIST (extreme heterogeneity) with 10 honest workers and f = 1, under several attacks. This complements Figure of the main paper.
37

---

Published as a conference paper at ICLR 2025
100
Test Accuracy
Test Accuracy
75
DSGD (1 -
75
DSGB
50
50
GM + NNM
GM NMM
25
124 NXM
ABC
25
GMs MNM . ANC
0
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(a) FOR
(h) SF
1.00
100
160
Teat ScL
75
Tost Accuaay
75
ONTN AAM
75
ONTTL
50-
25
25
Text
800
Step
Step
Step
(c) ALIE
(d)
(c) Mimic
Figure 14: Performance of Robust-DSGii when using ARC compared clipping, heteroge-
neous MNIST (a = 0.1) with 10 honest workers and f = 3, under several attacks.
1.00
Accuracy
DSED
Test Accuracy
75
0.75
GM - NMM
50
GM NNM ARC
0.50
25
0.25
0
0.00
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(a) f 3
(b) f = 4
1.00
0.75
0.50
Test
0.25
0.00
200
400
600
800
1000
Step
(c) =
Figure 15: Performance Robust-DSGD under the I.F attack when using ARC compared to no clipping, on heterroencoously-distibbuu MNIST (a 0.1) with 10 honest workers and varying number adversarial workers f.
38

---

Published as a conference paper at ICLR 2025
F.1.2 LARGER SYSTEM: 30 HONEST WORKERS
We consider training on the MNIST dataset in larger system comprised of ff- 30 honest workers, and f E {3, 6, } adversarial workers.
100
100
DG23 IT 00
Accuracy
75
Test Accuracy
75
CMTHI
CHTIM NON
CWTTM- ARC
50
25
CIRRED MI0
GM: WIN ARC
50
25
CVMRED MIM
MK. 181
CMNNEDO KAl AARC
0
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(a) ALIE
(b) SF
100
100
DSCO
"let Accuracy
Test Accuracy
CHTH RMM
75
CWTN NRM ARC
DM NAM
50
CMPECO HOM
CHV ABC
25
25
NNV ASC
0
200
400
600
800
1000
0
200
400
600
800
1000
Step
Step
(c) LF
(d) FOB
Figure 16: Performance of Robust-DSGD when using ARC and without clipping on distributed MNIST under extreme heterogeneity, There are f = 3 adversarial workers executing 4 attacks.
100
100
Tiett Accuracy
75
DSGD OF 01
Test Accuracy
75
DAGO IT OI
UWIN FIRM
CWIN HORE
50
50
CHNED NNY
CUIEED NIN CNINETI NAM AMC
25
OWNIED- MER ARC
25
19C MIN
VK- SEIM NAM
0
200
400
600
800
1000
200
400
600
800
1000
Step
Step
(a) ALIE
(b)
100
100
Accuracy
75
DSCD
OWTH RMM
CUTN NIM - ABC
Test Accuracy
75
DSGG -
50
50
CWNEED MMM ABC
CN- MIN ABC
CMNECO HUN
25
MKC 181 ABE
NNY
25
Mi
CHINED- KAS ABC
0
200
400
600
800
1000
0
200
400
600
800
1000
Step
Step
(c) I.F
FOE
Figure 17: Performance of Robust-DSGD when using ARC and without clipping on heterogencouslyy. distributed MNIST with a 0.1. There are adversarial workers executing attacks.
39

---

Published as a conference paper at ICLR 2025
100
100
Test Test Accuracy
Test Accuracy
75
CWIN RAM
75
CMTI WIN
CUTN SBH AFC
CYTI RASK ASC
50
25
25
HBC
MKC 1034
MRS N81 ABC
MBC NMM ARC
0
200
400
800
1000
200
400
600
1000
Step
Step
(a) ALIE
(b) SF
100
100
Test Accuracy
75
DSGD O'
CUTN RIRS
Test Accuracy
75
CN NNY
CNV CIII RAN
50
50
CRCY ARC
CWNEED NMY
25
IKC MIN
LWNEDD MMN AIC
25
MMC.
Vic RN5 AVC
0
200
400
600
800
200
400
600
800
1000
Step
Step
(c) LF
(d) FOE
Figure 18: Performance of Robust-DSGD when using ARC and without clipping on heterogeneously- distributed MNIST with a 0.1. There are f = 9 adversarial workers executing 4 attacks.
100
100
CWTM NIR
CWTM NAR ARC
80
GK RAN ARC
GC NAN
Test Accuracy
Test Accuracy
CVited NNM
CVited NAM ARC
MUGi KOUPS NAH
Hult--oum NAH ARC
CWNN + NKM
OWTH NKM ARC
40
CN - NAM
CM NAD - ABC
20
CWHidd - 2EV0
20
CWHied - 7800 ABC
Mulo Kium N0M
Mul: Krum NMW5 ARC
Number of adversarial workers
Number adversarial workers
0.1
(b) extreme heterogeneity
Figure 19: Worst-case maximal accuracies achieved by Robust-DSGD, with and without ARC, on anterogeneouslyyddistibuuee MNIST with 30 honest workers. We consider heterogeneous data distribution with = 0.1 (left) and extreme heterogeneity (right), and vary f E {3, 9}.
40

---

Published as a conference paper at ICLR 2025
F.2
DASHION-MNIST
100
100
CWAT NMM
CAMAid RAIR
CWTT NNM ARC
CoMiid FANR ANC
GM NNV
Mall Krum NAMM
GM MAV ARC
80
Mulli Krum - NAMM ARC
Test Accuracy
Test Accuracy
60
40
40
20
20
0
1
0
2
Number of adversarial workers
Number of adversarial workers f
(a) a 0.1
a 0.1
100
100
NAN
GeMMdd
80
80
Mull-Krum ARC
Test Accuracy
Test Accuracy
60
60
40
20
20
0
Number of adversarial workers
Number of adversarial workers f
(c) 0.05
(d) cK 0.05
100
100
CINTH NMM
CWiMied NAN
CWTTH NSM ARC
CWiteed NAN ARC
CH MAN
Muls- Kium NNM
CH MAV ABC
80
Mull Kiun - NAM ARC
Test Accuracy
Test Accuracy
60
60
40
40
20
20
0
0
1
3
2
5
Number of adversarial workers
Number of adversarial workers
(e) extreme
(f) extreme
Figure 20: Worst-case maximal accuracies achieved by Robust-DSGD when using ARC compared to no clipping, on waaarroennoousyyddsstitiie Fashion-MNIST with 10 honest workers. We fix the heterogeneity level and vary the number of adversarial workers f.
41

---

Published as a conference paper at ICLR 2025
100
100
Test Accuracy
Test Accuracy
60
40
40
20
OWTH à NAM
20
ClMlled NMM
OWTN a NAM ARC
C3UR ad -MM ARC
GM - 1R1
Muit Kjumt AMM
CM - NRAM ARC
Muiti Krum MMN ARC
0.5
a 0.1
a 0.05
extreme
0.5
a
0.1
a - 0.05
extreme
Heterageneity Level
Heterogeneily
(a) f =1
(h) f
100
100
80
80
Test Test Accuracy
Test Accuracy
60
60
40
40
0
0.5
0.05 Heterogeneity Level
0.1
extreme
0=0.5
0.05 Heterogeneity Level
0.1
extreme
(c) f =
(d) f = 3
100
CVTN - MPM
CVtttet NMM
CVTH - NBM ABC
Cvpteet NMM ARC
GM 18M
GM - 78M - ARC
80
Wutt-trumm MMN ARC
Mutt-trumm MIN
Test Accuracy
Accuracy
60
40
40
20
20
0
0
0 m 0.5
a 0.05 Heterogeneity Level
0.1
extreme
a
-
0.5
a = 0.1
a 0.05 Heterogeneity Level
extreme
(c) f
ff
Figure 21: Worst-case maximal accuracies achieved by Robust-DSGD when using ARC compared no clipping, on heterogeneouslly-istree distrribbd MossS with 10 honest workers. We fix the number of adversarial workers f and vary the heterogeneity level.
42

---

Published as a conference paper at ICLR 2025
F.3 CIFAR-10
Initial System (Main Paper): 16 Honest Workers
0.2
0.075
Aggregation
No Clipping
ARC
No Clipping
ARC
CWMed
43.4 + 4.2
69.4 = 0.8
13.7 12.1
62.7 = 1.2
MK
50.9 + 5.1
68.7 + 0.5
40.5 0.7
59.9 1.9
Table 5: Worst-case maximal accuracies (%) achieved by Robust-DSGD heterogeneously- distributed CIFAR-10 with ARC and without. There is f = 1 adversarial worker among n = 17. As baseline, DSGD (ʃ = reaches 76.5% and 70% when 0.2 and 0.075, respectively. This table complements Table in the main paper.
CW NAM
CANeed NHH
CW TM NMM ARC
CAMted NNM NNM--AC
CM NNM
Mult-Kum MMM
CM - NNV ARC
80
Mutt-Cum NMM ARC
Test Accuracy
Test Accuracy
60
60
40
40
20
20
0.5
0.2
0.075 Heterogeneity Level a
0.1
0.05
0.5
0.2
0,1 0.075
0.05
Heterogeneity Level a
(a) f=1
(b) f =1
Figure 22: Worst-case maximal accuracies achieved by Robust-DSGD when using ARC compared to no clipping, on heterogeeeoouslyddittiiivee CIFAR-IÓ with 16 honest workers. We fix the number of adversarial workers and vary the heterogeneity level.
100
100
Test Accuracy
Test Accuracy
75
CWTT
75
HNN
50
CN- KMM ABC
25
25
CWTM: MM/ ARC Gi 18-4
Ch NWV AMC
0
500
1000
1500
2000
1000 Step
2000
Step
(a) FOE with CWTM and GM
(b) ALIE with CWTM and GM
100
100
Test Test Accuracy
OWNED RAN
Test Accuracy
75
DUNED MUM AMC
75
VR: WIN
RMH
50
50
CWNED NIN CUNET RMM AAM
25
25
NK. 1812
NNN JACC
0
500
1000
1500
2000
500
1000 Step
1500
2000
Step
(c) FOE with CWMed and MK
(d) ALIE with CWMed and MK
Figure 23: Performance achieved by Robust-DSGD when using ARC compared to clipping, hetcrogencouully-issteee disttrrbte CIFAR-10 (a = 00.75) with 16 honest workers and f = 1 executing ALIE and FOE.
43

---

Published as a conference paper at ICLR 2025
We also test the performance of ARC in more adversarial regimes, with f {2,3} adversarial workers (along with n f = 16 honest workers). We consider heterogeneity regimes of a = 0.2 and 0.5, when f = 2 and 3, respectively. The results are presented in Table and we show in Figure 24 the performance of ARC compared to no clipping under the FOE attack.
2, = 0.2
f = 3, = 0.5
Aggregation
No No Clipping
ARC
No Clipping
ARC
CWTM NNM
5.2
53.0 + 4.7
52.0 + 1.3
55,4 + 1.1
GM O NNM
33.8 + 6.7
50.2 3.3
50.9 2.5
49.6 + 1.4
CWMed NNM
32.6 9.8
49.7 = 2.7
48.7 = 2.4
62.7 = 0.9
MK o NNM
4.2
51.9 2.1
50.3 + 1.4
50.2 + 2.4
Table 6: Worst-case maximal accuracies (%) achieved by Robust-DSGD on heterogeneously- distributed CIFAR-10 with ARC and without. There are f 3) adversarial workers with Y f = 16 honest workers.
100
100
DOSD It
Test Accuracy
AMM
Test Accuracy
CV AMM
50-
ge) W.M AFC
50-
D200 11
CWTN MM8
25
25%
09: NMM ABC
0
0
500
1000
1500
2000
500
1000
1500
2000
Step
Step
(=) 0.2
(b) f = 3, 0.5
100
100
Test Accuracy
Test Accuracy
75
OIVED-
75
se: 1481 JAC
OOMED
25
25
COMED WIM ABC
0
0
Step
Step
(c) f= 0.2
(d)
= 0.5
Figure 24: Performance of Robust-DSGD when using ARC and without clipping on CIFAR-10 10. There are 16 honest workers, and f 2 (left) and = (right) adversarial workers executing the FOE attack. The aggregations used are CWTM o NNM and GM o NNM (top), and CWMed NNM and MK NNM (bottom).
Larger System: 33 Honest Workers We also run experiments on CIFAR-10 in a larger system comprised of n - f = 33 honest workers and f E (2,3) adversarial workers. We consider the high heterogeneity regime of = 0.1. The results are presented in Table 7 and we show in Figure 25 the performance of ARC compared to no clipping under the FOE attack.
2
f ==3
Aggregation
No Clipping
ARC
No Clipping
ARC
CWTM NNM
45.5 # 1.3
54.2 + 1.0
41.3 0.5
47.5 + 1.5
GM o NNM
41.8 1.1
55.2 2.2
40.0 + 1.2
47.5 + 1,5
CWMed NNM
42.5 + 1.42
54.7 1.2
35.7 8.7
49.7 3.4
MK NNM
45.8 + 0.8
54.8 + 2.5
41.4 0.6
48.7 + 2.8
Table 7: Worst-case maximal accuracies (%) achieved by Robust-DSGD on heterogeneously-
distributed CIFAR-10 10 with ARC and without. There are f= (left) and f f (right) adversarial workers, along with n 33 honest workers. We consider the high heterogencity regime 0.1.
44

---

Published as a conference paper at ICLR 2025
100
0660 E- 61
Bioa if
Test Accuracy
Testi Accuracy
75
Get NIM
181
50
50
25
25
0
500
1000
1500
2000
500
1000
1500
2000
Step
Step
(a) CWTM and GM, f =
(b) CWMed and MK, f =
100
100
Accuracy
CarTHe RUM
DGGB
Testt Accuracy
EISD
CAAMED RAS
dpt. 1864
MC- AM 100
25
25
0
500
1000 Step
1500
2000
Step
(c) CWTM and GM, f 3
(d) CWMed and MK. =
Figure 25: Performance of Robust-DSGI when using ARC and without clipping on CIFAR-10. (top) and (bottom) adversarial workers executing the FOE
There 33 honest workers, and attack. We consider the high heterogeneity regime = 0.1. The aggregations used are CWTM NNM and GM o NNM (left), and CWMed NNM and MK NNM (right).
F.4 RUNTIME COMPARISON: NNM (ALLOUAH ET AL. 2023A) vs. ARC
Rundima Comparienn of ARC and WMM for Varying Mocel Stee
Sundime Companiene ABC and MMM to Varying System Steee
ABC NNM
ABC
N84M
0.20
0.25
0.15
0.15
0.05
0.05
300000
1001000
150000C
2000000
2300000
60
(a) Varying Model Size
(b) Varying System Size n
Figure 26: Computational performance of ARC NNM in two different settings. In the left plot, we fix the total number of workers n 30, the number of adversarial workers f = 3, and vary the model size d. In the right plot, we fix the model size 1310922 (the size of the model we used on CIFAR- 10) and f = 3, and vary the number of workers in the distributed system.
45


Reviews:
[{"review_id": "TKnO6M1glb", "reviewer": "Reviewer_KAQT", "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.", "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.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This paper is generally well-written. \n2. The idea of adaptive clipping intuitively makes sense and has an excellent empirical performance in the experiments of this work.\n3. 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. \n\n1. 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.\n\n2. 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.  \n- 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, \n$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.\n\nOverall, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NHOJ5LqlA3", "reviewer": "Reviewer_zvxn", "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.", "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?\n* 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?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "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,\n* 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.\n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KB1hhgvXAJ", "reviewer": "Reviewer_Ap5T", "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.\nThe 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.", "questions": "See section before. \n\nIn addition:\n\n-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.\n\n-Can you report the Adaptive C of ARC over steps in these plots?\n\n- 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?\n\n-The intuitive k is the number of potential malicious workers which is f?\n\n-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?\n\n-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  \n\n-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", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strengths are: \n\n-The authors propose Adaptive Robust Clipping (ARC), a new mechanism to enhance robustness in adversarial settings.\n\n-The authors show that ARC almost retains the theoretical robustness guarantees of existing Robust methods while enhancing their practical performance. \n\n-The authors validate ARC through several experiments.", "weaknesses": "The main weaknesses are:\n\n-Increased complexity produced by ARC in practical implementation\n\n-ARC performance depends on good model initialization which may degrade the performance in the case of poor initialization.\nDid you try some experiments to assess this?\n\n-While ARC improves robustness by adaptively clipping gradients, its thresholding could risk clipping too aggressively in certain settings, potentially discarding useful gradient information.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ryDOSDjblA", "reviewer": "Reviewer_n1Gk", "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.\n\nA 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.\n\nAs 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.", "questions": "1) Why were no experiments ran using static clipping?\n2) 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.\n3) 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?", "limitations": "", "rating": 8, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 4, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)