On the Effect of Batch Size in Byzantine-Robust Distributed Learning
Authors: Yi-Rui Yang
Chang-Wei Shi
Wu-Jun Li
Venue: ICLR 2024 poster (2024)
Keywords: distributed learning
Byzantine robustness
batch size
Primary area: optimization

Abstract: Byzantine-robust distributed learning (BRDL), in which computing devices are likely to behave abnormally due to accidental failures or malicious attacks, has recently become a hot research topic. However, even in the independent and identically distributed (i.i.d.) case, existing BRDL methods will suffer a significant drop on model accuracy due to the large variance of stochastic gradients. Increasing batch sizes is a simple yet effective way to reduce the variance. However, when the total number of gradient computation is fixed, a too-large batch size will lead to a too-small iteration number (update number), which may also degrade the model accuracy. In view of this challenge, we mainly study the effect of batch size when the total number of gradient computation is fixed in this work. In particular, we show that when the total number of gradient computation is fixed, the optimal batch size corresponding to the tightest theoretical upper bound in BRDL increases with the fraction of Byzantine workers. Therefore, compared to the case without attacks, a larger batch size is preferred when under Byzantine attacks. Motivated by the theoretical finding, we propose a novel method called Byzantine-robust stochastic gradient descent with normalized momentum (ByzSGDnm) in order to further increase model accuracy in BRDL. We theoretically prove the convergence of ByzSGDnm for general non-convex cases under Byzantine attacks. Empirical results show that when under Byzantine attacks, compared to the cases of small batch sizes, setting a relatively large batch size can significantly increase the model accuracy, which is consistent with our theoretical results. Moreover, ByzSGDnm can achieve higher model accuracy than existing BRDL methods when under deliberately crafted attacks. In addition, we empirically show that increasing batch sizes has the bonus of training acceleration.

Published as a conference paper at ICLR 2024
ON THE EFFECT OF BATCH SIZE IN FIZANTINE-ROBUS DISTRIBUTED LEARNING
Yi-Rui Yang Chang-Wei Wei Shi
Wu-Jun Li
National Key Laboratory for Novel Software Technology.
Department of Computer Science and Technology.
Nanjing University, Nanjing, China {yangyr, shicw) smail. nju. edu. cn, liwujunênju. edu. on
ABSTRACT
Byzantine-robust distributed learning (BRDL), in which computing devices are likely to behave abnormally due to accidental failures or malicious attacks, has recently become hot research topic. However, even in the independent and identically distributed (i.i.d.) case, existing BRDL methods will suffer a significant drop on model accuracy due to the large variance of stochastic gradients. Increasing batch size a simple yet effective way to reduce the variance. However, when the total number of gradient computation is fixed, too-large batch size will lead too-small iteration number (update number), which may also degrade the model accuracy. In view of this challenge, we mainly study the effect of batch size when the total number of gradient computation is fixed in this work. In particular, we show that when the total number of gradient computation is fixed, the optimal batch size corresponding to the tightest theoretical upper bound in BRDL increases with the fraction of Byzantine workers. Therefore, compared the case without attacks, larger batch size is preferred when under Byzantine attacks. Motivated by the theoretical finding, we propose a novel method called Byzantine-robust stochastic gradient descent with normalized momentum (ByzSGDnm) in order to further increase model accuracy in BRDL. We theoretically prove the convergence of ByzSGDnm for general non-convex cases under Byzantine attacks. Empirical results show that when under Byzantine attacks, using a relatively large batch size significantly increase the model accuracy, which is consistent with our theoretical results. Morcover, ByzSGDnm can achieve higher model accuracy than existing BRDL methods when under deliberately crafted attacks. addition, we empirically show that increasing batch size has the bonus of training acceleration.
INTRODUCTION
Distributed learning has attracted much attention (Haddadpour et al. 2019 Jaggi et al. 2014 I Lee et al. 2017: Lian al. 2017 Ma al. 2013 Shamir al. 2014 Sun et al. [018]] Yang 2013
Yu et al. 2211 9a b Zhao et al. 2017:2012 Zhou et al. 20188 Zinkevich et al. 2010) for years due its wide application. In traditional distributed learning, it is typically assumed that there is no failure or attack. However, in some real-world applications such as edge-computing (Shi et al. 2016) and federated learning (McMahan & Ramagel (017). the service provider (also known as the server) usually has weak control over computing nodes (also known as workers). In these cases, various software and hardware failures may happen on workers (Xie et al. 2019). Worse even, some workers may get hacked by malicious third party and intentionally send wrong information to foil the distributed learning process (Kirouu et al. 202I). The workers under failure or attack also called Byzantine workers. Distributed learning with the existence of Byzantine workers, which is also known as Byzantine-robust distributed learning (BRDL), has recently become a hot Chen et al. 2018: Damaskinos al.
research topic (Bernstein et al.] 2019 Bulusu al.
2021
2018: Diakonikolas et al.) [017]] Diakonikolas & Kane
2019
Konstantinidis & Ramamoorthy 2021
Lamport al. 2019 Rajput et al. 2019 Sohn et al.
2020
Wu al. 2020 Yang & Li 202 2023
Yang et al. 20200) Yin et al. 2019
"Corresponding author.

---

Published as a conference paper at ICLR 2024
A typical way to obtain Byzantine robustness is to substitute the mean aggregator with robust aggregators such as Krum (Blanchard et al. 2017), geometric median (Chen et al. 2017). coordinate- wise median (Yin et al. 2018), centered clipping [Karimireddy et al. 202 D. and so on. However, when there are Byzantine workers, even if robust aggregators are used, it is inevitable that an aggregation error will be introduced, which is the difference hetween the aggregated result and the true mean value. Furthermore, even in the independent and identically distributed (i.id.) cases, the aggregation error could be large due to the large variance of stochastic gradients (Karimireddy et al.) 2021) which are typical values sent from workers to the server for parameter updating. The large aggregation error would make BRDL methods fail (Xie et al. 2020)
It has been shown in existing works that the variance of the values from non Byzantine workers can be reduced by using local momentum on workers (Allen-Zhu et al. 2020 MI-Mhamdi et al., 202T
Farhadkhani et al. 2022 Karimireddy et al. 2021). However, as the empirical results in our work will show, even if local momentum has been used, existing BRDI. methods will suffer significant drop model accuracy when under attacks. Therefore, more sophisticated techniques are required to further reduce the variance stochastic gradients.
Increasing batch size is simple yet effective way to reduce the variance. However, when the total number of gradient computation is fixed, a too-large batch size will lead to a too-small iteration number (update number), which may also degrade the model accuracy (Goyal et al. 2017: Hoffer et al. 2017; Keskar et al., 2017: You et al. 2020) /haoo et al. 2020 2023). In view of this challenge, mainly study the effect of batch size in i.i.d. cases when the total number of gradient computation is fixed. The main contributions of this work are listed as follows:
We show that when the total number of gradient computation is fixed, the optimal batch size corresponding to the tightest theoretical upper bound in BRDL increases with the fraction of Byzantine workers.
Motivated by the theoretical finding, propose novel method called Byzantine-robust stochastic gradient descent with normalized momentum (ByzSGDnm) in order to further increase model accuracy in BRDL.
We theoretically prove the convergence of ByzSGDnm for non-convex cases under attacks.
We empirically show that when under Byzantine attacks, compared to the cases of small batch size, setting relatively large batch size can significantly increase the model accuracy. Moreover, ByzSGDnm can achieve higher model accuracy than existing BRDL methods when under deliberately crafted attacks.
In addition, increasing batch size has the bonus of training acceleration, which is verified by our empirical results.
PRELIMINARY
In this paper, we mainly focus on the following optimization problem:
min F(w) = E [g-p[J(w,Ei) WERd
where E Rd is the model parameter and D is the distribution of training data. In addition, mainly focus on the widely-used parameter-server (PS) framework in this work, where there are m computing nodes (workers) that collaborate to train the learning model under the coordination of a central server. Each worker can independently draw samples & from data distribution D. That is to say, we focus on the i.i.d. cases in this paper. Moreover, among the workers, fraction of 8 workers are Byzantine, which may behave abnormally and send arbitrary values to the server due to accidental failure or malicious attacks. The other workers, which are called non-Byzantine workers, will faithfully conduct the training algorithm without any fault. Formally, we use G S 21, m} denote the index set of non-B -yzaanine workers where |g] = (1 8).. The server has no access to any training data and does not know which workers are Byzantine. In this work, we mainly consider the loss functions that satisfy the following three assumptions, which are quite common in distributed learning. For simplicity, we use the notation || || to denote the Euclidean norm of vector.
Assumption (Bounded variance). There exists a 2 such that Eę [/ E) VF(w)]I o² for all E Rd.
2

---

Published as a conference paper at ICLR 2024
Assumption 2 (Lower bound of F()).. There exists F E R such that F(w) F for all R.. Assumption 3 (L-smoothness). The loss function F-)) is differentiable everywhere on R.. Moreover [[VF(w) VF(w")ll S -w'l all w, w' E R4.
typical and widely-used algorithm solve the optimization problem ①T with potential Byzantine workers is Byzantine-robust stochastic gradient descent with momentum (ByzSGDm) (Farhadkhani al., 2022; Karimireddy al. 2021). Compared with vanilla stochastic gradient descent with momentum (SGDm), the main difference in ByzSGDm is that the mean aggregator on the server is substituted by robust aggregator. Specifically, in ByzSGDm, the server updates the model parameter at the f-th iteration by computing
W++1 W. - Agg(
(m))
(k) received
where n is the learning rate and Agg()) a robust aggregator. Local momentum u from the k-th worker (k 1, 2, ..,,, m.. For each non-Byzantine worker k E G.
RR)
80
(k)
t= 0;
+
B)
(k)
t t> 0,
where 3 is the momentum hapareparameter and gt (k) = Σ Vi( is the mean value of
mini-batch of stochastic gradients with size B. For each Byzantine worker k E [m] \. u, can be an arbitrary value. For space saving, more details about ByzSGDm are moved Algorithm and Algorithm in Appendix
(k)
For a 'good' aggregator, the aggregated result Agg(u!) ,...., u, m)) should be close the true mean of the momentums on non- Non-BByantine workers, which can be written as |š] Ekeg (b: To quantitatively measure robust aggregator, the definition of (Ōmax. c)-robust aggregator has been proposed in existing works (Karimireddy et al. 202T). which we present in Definition D below.
Definition ((8max, ro-robust aggregator (Karimireddy et al. 2021)). Let S 8max < and 2 Random vectors Xg..... Xm E IRd' satisfy that B||x X
S p² for all fixed k, k E G. where (-) is called (ōmax; c)-robust aggregator
C (I,..., m) and |9] = 8)m. An aggregator Agg(.) if we always have that
e||e|| < cōp².
when 8 5 8max- Here, e Agg ................................ Xm)
Σ Ekeg X called the aggregation error.
In addition, it has been proved that for any potential robust aggregator, there is inevitably an aggregation error of (66p²) in the worst case (Karimireddy et al. 2021 It has also been proved that
some existing aggregators such as centered clipping (Karimireddy et al. 2021 satisfy Definition
3
METHODOLOGY
3.1 EFFECT OF BATCH SIZE ON CONVERGENCE
As shown in existing works on Byzantine- -oouutt distributed learning (Blanchard et al. 2017 Chen et al. 2017: Li al. 2019 Yin et al. 2018), even if robust aggregators have been used, there is typically a drop on model accuracy under Byzantine attacks due to the aggregation error. Therefore, we attempt alleviate the drop on model accuracy by reducing the aggregation error.
According to Definition | there are three variables related to the upper bound of aggregation error. The fraction of Byzantine workers is determined by the problem, which can hardly be reduced. The constant is mainly related to the specific robust aggregator. There have been many works (Blanchard al. 2017 Chen et al. 2017, Karimireddy al.) 2222 [i et al. 2019 Yin et al. 2018) that propose various robust aggregators. In this work, we mainly attempt to reduce Moreover, we focus on the i.i.d. setting in this work. Since [[(x)] E[xx]] in this case, according to Assumption we have
Xx Xx 112 (xx E[xx]) (xxr - E [xxx<) 1)
E |
E[xx]] ]| +1 X TMy-EEp x
1| < 20 (2)
3

---

Published as a conference paper at ICLR 2024
which implies that p² < 2o in i.id. cases under Assumption Therefore, reducing the variance 0² in i..dd cases. A simple but effective way to reduce the variance is increasing the batch size each worker, which is denoted by B in this paper. For simplicity, all workers adopt the same batch size in this work. Compared to the case with batch size 1, the variance of stochastic gradients will be reduced to 1/B of the original if the batch size is set B. However, to make the total number of gradient computation unchanged, the total iteration number will be reduced B/B of the original, leading fewer times of model updating. Formally, C = [m 5) to denote the total number of gradient computation on -yzanninnn workers, where the total iteration number. Thus, we have T = Bmi(188 It implies that a larger batch size B will lead to smaller total iteration number I' when the total number of gradient computation is fixed. In many BRDL applications with deep learning models, can be used to approximately evaluate the computation cost since the computation cost of robust aggregation and model updating is negligible compared to that of gradient computation.
reduce by
assume that
use
We first recall the convergence of ByzSGDm, which has been adequately studied in existing works (Karimireddy et al. 202I). We restate the convergence results of ByzSGDm in Theorem below. For space saving, the details of how Theorem is obtained from existing results (Karimireddy
et al. 2021) are presented in Appendix B
Theorem (Convergence of ByzSGDm Karimireddy et al. 2021)). Suppose that F'(w))-F S Fo- Under Assumptions
and when A-g(.) is (duax, c)-robust and d S 5max, setting f) 1)
min
Fo
and 1 B 8Lm, we have the following result for ByzSGDm:
+c8)
a² l + cdm)
(VOOTF +
3cdo² B
32LF,
20 + côm)
E
FF::))
< 1
+
T
TBm
T
TBm
(3)
When C is fixed, inequality 3 can be re-written as FVW(w)1 s ((B) since = C
Bm(1-55+ where L (B) is valued function with respect to batch size B. Specifically,
@2 + cdm)(1-)) (1-6) u(B) = 16V
(VIOLTO +
3cdoz B
32LFoBm(1 (1
C
C
20 + +00m 8)
C
Please note that (B)) originally defined on the set of positive integers No since B denotes the batch size. We here extend the definition of ((B) to B E (0, +o0) for simplicity. The results will be interpreted back to N at the end of our analysis. Then we attempt to find the optimal batch size B* that minimizes the theoretical upper bound (B) when C = T Bm(11 - 8) is fixed. Formally, B* defined by the following optimization problem:
B arg argmin U(B). BE(0,+
We present Proposition below, which provides explicit expression of B". Please refer to Appendix B for the proof details.
Proposition U(B) strictly convex on (0, +o0). Moreover when 8 > O, we have
$ (vof) + cōm)
8" = 1612(FF))
oict
(4)
m(1 - 8)
and
u(B"= = 16 11/10LF((11 + c0m) 8) +
24 [12c5 + com) 1.
C²
C²
20(1 + cdm) - 5)0²
+
C
4

---

Published as a conference paper at ICLR 2024
Algorithm 1 Srrzantine-Robuse SGD with Normalized Momentum (ByzSGDnm)
Input: initial model parameter wo, worker number mh, iteration number T, learning rates (m ) batch size B, momentum hyper-parameter 3 E [0, 1), robust aggregator Agg(-); for t 0 to T - 1 do
12-1
Broadcast wy to all workers;
worker & {1,..., m) in parallel do Receive We from the server;
Independently draw B samples (k:11)
St ....,
(k.B) from distribution D;
Compute g(( 1 ΣB b= V
c(h.b));
(1)
Update local momentum u, (K)
8u
t = 0;
3u (k)
+ (1
g) (k)
1 > 0:
Send (8) to the server (Byzantine workers may send arbitrary values this step); end on worker
Receive (u, k= from the workers, and compute u, Agg(u, (1)
(m))
..... u
Update model parameter with normalized momentum: Wr-1 = W; 1/t ur
end for
Output model parameter WT-
Please note that (BB has no more than one global minimizer due the strict convexity. Thus,
8* is well-defined when 8 > O. Furthermore, the term (0((1+c5m) in 44 is monotonically increasing with respect to 6. It implies that when the total number of gradient computation non- Byzantine workers C = Tm (1 - 8) fixed, 8 will increase as the fraction of Byzantine workers ó increases. Then, we interpret the above results back to B E N Due to the strict convexity, U(B) monotonically decreasing when B E (0, B²) and monotonically increasing when B (B" +o0). Thus, the optimal integer batch size that minimizes (BB) equals either B" or B + 1, which also increases with 8. The notation B*) represents the largest integer that is not larger than B". In addition, the conclusion will be further supported by the empirical results in Section
m([-6)
Meanwhile, although B - 0 as 5 > 0+, it should not be interpreted as recommending a batch size that is close to 0 when there is attack. In fact, since C is fixed, too-small batch size B implies a too-large iteration number T. which will lead to a large communication cost. Moreover, the computation power of some devices (e.g., GPUs) will not be effectively utilized when
small. Thus, the setting of B is trade-off between model accuracy and running time when d = O, which has been studied for years (Goyal et 2017 You et al.) [2020] Zhhoo et 2220 2023). In addition, please note that although smaller (IB) does not necessarily ensure a better empirical performance given the complexity and variety in real-world applications, it provides a better worst-case guarantee.
3.2 BYZANTINE- ROBUST SGD WITH NORMALIZED MOMENTUM
Proposition I shows that the optimal batch size B" that minimizes ((B) increases with the fraction of Byzantine workers. Hence, a relatively large batch size preferred when under Byzantine attacks. In existing works traditional large-batcs batch training without attacks (Goyal et al.) 2017 Hoffer et al., 2017; Keskar et al.) 2017] Zhao et al.) 2020 2023), the normalization technique is widely used to increase model accuracy. Motivated by this, we propose novel method called Byzantine-robust stochastic gradient descent with normalized momentum (ByzSGDam), by introducing a simple normalization operation. Specifically, in ByzSGDnm, the model parameters are updated by:
Agg U
(m)
Wr+1 Tj
Agg u, (1)
The details of ByzSGDnm are illustrated in Algorithm I Please note that there are some existing methods using layer-wise normalization (You al. 2020). However, these methods might suffer from degradation of model accuracy without additional training tricks such as warm-up (Zhao et al. 2023). Furthermore, shown in (Zhao et al. 2023). the layer-wise (block-wise normalization might slow down the convergence rate, Hence, we follow the way of performing normalization on the whole
momentum (Zhao al. 2020 2023 CCutkosky & Mehta 2020).
5

---

Published as a conference paper at ICLR 2024
Moreover, please note that the purpose of traditional large-batch training (Goyal et al. 2017 You et al. 2020 Zhao et al. 2020; 2023) is mainly to accelerate the training process by reducing communication cost and utilizing the computation power more efffectively. However, in this work, the main purpose of increasing batch size and using momentum normalization is to enhance the Byzantine robustness and increase the model accuracy under Byzantine attacks. The acceleration effect of adopting large batch size is viewed as a bonus in this work. Please refer to Section S for the empirical results about the wall-clock time ByzSGDm and ByzSGDnm with different batch size.
CONVERGENCE
In this section, theoretically analyze the convergence of ByzSGDnm under Assumptions and 3 The assumptions are common in distributed learning. For space saving, we only present the main results here. Please refer to Appendix B for the proof details.
Theorem 2. Suppose that F(wo) F I Fu and let a ===1- - 3. Under Assumptions 7 and 3
when Agg(:) (6max: c)-ruusst I 8max and πe = 1, we have the following result for Gymm:
T-1 Σ EEIF(WWol)
2Fo T/T
10nL
9 2cmd (1
va va)o
T
a
/Bm(1 8)
aT
Finally, we show that when the learning rate 1) and the momentum properly set, ByzSGDnm can achieve the convergence order of O by Proposition 2 below.
/ a are
T
Proposition 2. Under Assumptions 7 and when Agg(-) is (6max c)-robust and 8 S 8max setting v /S0LFo Fo Brn 1-8)
1 = min
and 1/t = 7) =
aF GLT
have that
Ov 20m8(1 8)+9 1
( (Bm((18))
5LFoo²
5LFo + 12
VV (w:)l
S6 (w:)ll
2omom11 5)}1]
TBm(1 -8))
T
27
/2cmm
0².
(5)
51 LFo
Moreover, when C = Bmm(1 8) is fixed, the optimal batch size B" that minimizes the right-hand
side of 5 is B" 9) (2cmm[1-6)+1)
In this case (B- B²), we have:
/2cm0(1 - 5) + (5LFoo?)+ 18
[[2cmm(1- - 6) + +13
Bl <
C²
C²
Inequality (5) illustrates that after T iterations, ByzSGDnm can guarantee that
0 (LFo)
min
E V
+
T
T
Therefore, ByzSGDnm has the same convergence order as vanilla SGD with normalized momen- tum (Cutkosky& & Mehta 2020) without attacks. The extra factor [v [2eemō(1 - 8) + 11 8)+ in the haght side (RHS) of (5) is due to the existence of Byzantine workers and increases with 5. The extra factor vanishes (equals 1) when there is no Byzantine worker (6 0). Moreover, it has been
shown in existing works (Arjevani et al. 2023 Cutkosky & Mehta 2020) that under Assumptions 1
and 3 the convergence order O(L/T*) is optimal for SGD. Siz-VR--MRRNG (Gorbunov et al. 2023) achieves a better convergence order by intermittently using full gradients. However, full gradients are computationally expensive, especially in real-world applications with large number of training instances. We detailedly compare ByzSGDnm with Byz-VR-M VR-MARINA in Appendix [D] The empirical results show that ByzSGDnm significantly outperforms Byz- ByZ-VR-MARINA, In addition, 3* also increases with ă since both 5(1 8) and T increase with 8 when å E [0, }

---

Published as a conference paper at ICLR 2024
The analysis in this paper is based the definition of (6max. c)-robust aggregator (Definition There also another criterion of robust aggregators in existing works called the (f. x) robuustesss (Al louah et al. 2023). Similar results can also be obtained under the (f, robuustessss. Please refer to Appendix C for more details.
5 EXPERIMENT
Task and platform. In this section, will empirically test the performance of ByzSGDm and ByzSGDnm on image classification tasks. Each algorithm will be used to train a ResNet-20 (He) et al. 2016) deep learning model CIFAR-10 dataset (Krizhevsky et al. 2009). All the experiments presented in this work are conducted on a distributed platform with 9 dockers. Each docker is bound to an NVIDIA TITAN Xp GPU. One docker is chosen as the server while the other 8 dockers are chosen as workers. The training instances are randomly and equally distributed to the workers.
Experimental settings, In existing works (Allouah et al.) 2023 Karimireddy et al. 2021 2022) on BRDL, the batch size is typically set to 32 or 50 on the CIFAR-I0 10 dataset. Therefore. We set ByzSGDm (Karimireddy et al.) 202T) with batch size 32 as the baseline, and compare the performance of ByzSGDmm with different batch size (ranging from 64 to 1024) to the baseline under ALIE attack (Baruch et al., 2019). In our experiments, we use four widely-used robust aggregators Krum (KR) (Blanchard et al. 22117) geometric median (GM) (Chen et al.) (017). coordinate-wiss median (CM) (Yin et al. 2018) and centered clipping (CC) (Karimireddy et al. 202T) for ByzSGDm. Moreover, set the clipping radius to 0.1 for CC. We train the model for 160 epochs with cosine annealing learning rates (Loshchilov & Hutter 2017). Specifically, the learning rate at the i-th epoch will be 7)s from {0.1. 0.2, 0.5, 2.0, 5.0, 10.0, 20.0), and the best final top-1 test accuracy is used as the final metrics. The momentum hyper-parametee ,9 is set to 0.9. Please note that the total number of gradient computation on non-Byzantine workers C' is independent of batch size. Specifically, C 160 50000 (1 8) since we train the model for 160 epochs with 50000 training instances.
(1 + cos( x for
,.... 159. The initial learning rate too is selected
Evaluation on the effect of batch size. We first evaluate the performance of ByzSGDm with different batch size when the fraction of Byzantine workers is 0 (no attack), 1 and S respectively. As the results in Table and Table 2 show, the batch size corresponding to the best top-1 accuracy increases with 6, which consistent with our theoretical results. Moreover, when 5 I. using relatively large batch size greatly increases the test accuracy. Meanwhile, the test accuracy decreases with the batch size when there is no attack (6 = 0), which is consistent with existing works (Goyal et al. 2017 Hoffer et al. 2017
Keskar et al. 2017 You et al. 2020 Zhao et al. 2020 2023).
Table The final top-1 test accuracy of ByzSGDm with various batch size under ALIE attack when Krum (KM) and geometric median (GM) are used as the robust aggregator
ByzSGDm with KR
Batch size
8 5=0
8 = 1/8
= 3/8
32x8 (baseline)
91.08% %
55.84%
38.55%
64x8
89.98% (-1.10%)
63.22% (+7.38%)
54.15% (+15.60 %)
128x8
89.71% (-1.37%)
75.06%
(+19.22%)
55.98%
(+17.43%)
256x8
89.15% (-1.93%)
84.47% (+28.63%)
59.28% (+20.73%)
512x8
86.15% (-4.93%)
85.68%
(+29.84%)
83.42% (+44.87%)
1024x8
84.97% (-6.11%)
83.48% (+27.64%)
83.45% % (+44.90%)
ByzSGDm with GM
Batch size
8= 0
8 1/8
3=3/
32x8 (baseline)
92.02%
83.81% %
63.11%
64x8
91.50% (-0.52%)
87.92% (+4.11%)
70.88% (+7.77%)
128 8
90.85% (-1.17%)
89.68% (+5.87%)
82.08% (+18.97%)
256x8
89.26% (-2.76%)
87.99% (+4.18%)
87.62%
(+24.51 %)
512x8
88.21% (-3.81%) %)
87.70% (+3.89%)
86.95% (+23.84%)
1024x8
86.52% (-5.50%)
85.94% (+2.13%)
84.75% (+21.64%)
7

---

Published as a conference paper at ICLR 2024
Table 2: The final top-1 test accuracy of ByzSGDm with various batch size under ALIE attack when coordinate-wise median (CM) and centered clipping (CC) are used as the robust aggregator
ByzSGDm with CM
Batch size
= 0
8= 1/8
= 3/8
32x 8 (baseline)
92.30%
86.46%
33.11%
64x8
91.79% (-0.51%)
88.09% (+1.63%)
55.66% (+22.55%)
128x8
90.43% (-1.87%)
89.16% (+2.70%)
66.38%
(+33.27%)
256x8
89.84% (-2.46%)
88.60% (+2.14%)
82.47%
(+49.36%)
512x8
87.27% (-5.03%)
87.20% (+0.74%)
83.25%
(+50.14%)
x024x8
84.06% (-8.24%)
83.71% (-2.75%)
80.94% (+47.83%)
ByzSGDm with CC
Batch size
8 8= O
8 = 1/1/
8= 3/8
32 x8 (baseline) x8
92.52%
86.55%
72.83%
91.74% (-0.78%)
88.59% (+2.04%)
79.45% (+6.62%)
x28x8
90.63% (-1.89%
88.94% (+2.39%)
84.94% (+12.11%)
256x8
89.40% (-3.12%)
88.46% (+1.91%)
87.25% (+14.42%)
512x8
88.78% (-3.74%)
88.29% (+1.74%)
87.46% % (+14.63%)
x024x8
85.50% (-7.02%)
84.88% (-1.67%)
83.70% (+10.87%)
Table 3: The final top-1 test accuracy when there are 3 Byzantine workers under ALIE attack
Method
with KR
with GM
with CM
with CC
ByzSGDm, batch size 32 (baseline)
38.55%
63.11%
33.11%
72.83%
ByzSGDnm, batch size = 32 x 8
43.47%
69.45%
61.28%
78.50%
ByzSGDm, batch size 512 x
83.42%
86.95%
83.25%
87.46%
ByzSGDnm, batch size = 512 8
85.12%
89.13%
86.03 %
88.53%
Table 4: The final top-1 test accuracy when there are 3 Byzantine workers under FoE attack
Method
with KR
with GM
with CM
with CC
ByzSGDm, batch size 32 8 (baseline)
10.00%
78.36%
83.97%
83.60%
ByzSGDnm, batch size = 32 x
10.00%
88.55%
84.12%
88.99%
ByzSGDm, batch size 512
10.00%
84.09%
79.16%
86.24%
ByzSGDnm, batch size = 512 x
10.00%
89.12%
84.65 %
89.32% %
Effectiveness of large batch size and momentum normalization. In this paper. propose to (i) a relatively large batch size and (ii) the momentum normalization technique. Here, we empirically evaluate the effectiveness of these improvements. Specifically,
will compare the performance of the following four methods: (a) ByzSGDm with batch size 32 x 8 (baseline),
(b) ByzSGDnm with batch size 32 8, (c) ByzSGDm with batch size 512 8, and (d) ByzSGDnm with batch size 512 x 8. The performances of the methods are compared when there are 3 workers under ALIE attack (Baruch al. 2019) and FoE attack (Xie et al. 2020), respectively. As presented in Table and Table among the four methods, ByzSGDnm with batch size 512 8 has the best top-1 test accuracy except for the case of using aggregator KR under FoE attack. All the methods fail when using KR under FoE attack mainly because the KR aggregator is not robust against FoF attack, as shown in existing works (Karimireddy al. 2021 (02T)220 Xie et al.) 2020). The empirical results of ByzSGDm and ByzSGDnm with more different batch size are deferred to Appendix[E for space saving. In addition, we also compare the performance of ByzSGDm and ByzSGDnm under no attack (or failure) and under bit- -t-flipping failure (Xie et al. 2019 respectively. ByzSGDnm has comparable performance to ByzSGDm in these two cases. P Please refer to Appendix for the detailed results.
More evaluation when NNM is used. We also compare the empirical performance of different methods when the nearest neighbour mixing (NNM) (Allouah et al., (2023) technique is used. NNM originally proposed to enhance the robustness of aggregators in general non-i.i.d. cases but can
8

---

Published as a conference paper at ICLR 2024
Table 5: The final top-1 test accuracy when there are Byzantine workers under ALIE attack and the nearest neighbour mixing (NNM) technique is used
Method
with KR
with GM
with CM
with CC
ByzSGDm, batch size 32 x 8 (baseline)
58.61 %
72.58%
71.51%
76.48%
ByzSGDnm, batch size = 32 x
80.41 %
79.50%
79.81%
79.91 %
ByzSGDm, batch size = 512 x 8
85.26%
85.37%
86.95%
85. 85.98%
ByzSGDnm, batch size = 512
87.68 %
88.09%
87.69%
87.59
Table 6: The wall-clock time of ByzSGDm and ByzSGDnm for 160 epochs (in second)
Batch size
32x8
64x8
128x8
256x8
512x8
985.52s
522.27s
366.98s
314.80s
ByzSGDm
2007.39s
(x2.04 faster)
(x3.84 faster)
(x5.47 faster)
(x6.38 faster)
978.50s
515.46s
376.70s
327.62s
ByzSGDnm
1985.78s
(x2.03 faster)
(x3,85 faster)
(x5.27 faster)
(x6.06 faster)
also be used in i.i.d. cases. As the results in Jssle, ByzSGDnm with batch size 512 x 8 still has the best final top-1 test accuracy under ALIE attacks when NNM is used. In addition, we find it interesting that when combined with NNM, the performance of KR and CM is improved, but the performance of GM and CC is degraded. Since NNM is originally proposed for general non-i.i.d cases, it requires further study to understand this behavior of NNM in i.i.d. cases. However, since we mainly focus on the effect of batch size, it is beyond the scope of this work.
The bonus of training acceleration. Existing works Gooaa et al. 2017 Hoffer et al. 2017 Keskar et al. 2017 You al., 2020 Zhao et al. 2020 2023) have shown that increasing batch size can accelerate the training process by reducing the communication cost and utilizing the computing power of GPUs more effectively. We present the wall-clock time for 160 epochs when using CC as the robust aggregator under no attack in Table 6 Please note that whether there are attacks or not has almost no effect on the computation cost non non-BByantine workers. For both ByzSGDm and ByzSGDnm, the running time decreases as the batch size increases. It verifies that increasing batch size has the bonus of training acceleration. In addition, ByzSGDnm has comparable running time to ByzSGDm, which shows that the computation cost of the momentum normalization is negligible.
Comparison with Byz-VR-MA VR-MARINA. Byz- VE--VRRAARINA (Gorbunov et al. 2023) originally proposed for non-i.id. cases, but can also be used in i.i.d. cases. Therefore, also empirically compare ByzSGDnm with ByZ-VR-MARIN outperforms Byz- BYZARR-MARINA in i.i.d. cases. Detailed results are deferred to Appendix D
Empirical results show that ByzSGDnm significantly
Although we mainly study the effect of batch size in BRDL for i.i.d. cases in this work, we also provide some empirical results under non-i..dd settings in Appendix E.2 The empirical results show that ByzSGDnm still outperforms cxisting methods the non-i.i.d setting. However, further work is required to detailedly discover the effect of batch size and the behavior of ByzSGDnm in non-i.i.d. cases, which we will study in the future.
6 CONCLUSION
In this paper. we theoretically show that when the total number of gradient computation is fixed, the optimal batch size corresponding to the tightest theoretical upper bound in BRDL increases with the fraction of Byzantine workers. The theoretical results indicate that a relatively large batch size is preferred when there are Byzantine attacks. Furthermore, we propose novel method called ByzSGDnm and prove the convergence of ByzSGDnm. Empirical results show that when under Byzantine attacks, setting a relatively large batch size can significantly increase the model accuracy compared to the case of small batch size, which is consistent with our theoretical results. Moreover, ByzSGDnm achieve higher model accuracy than existing BRDL methods when under attack. In addition, increasing batch size has the bonus of training acceleration, which is verified by the empirical results.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
For the theoretical results of our work, the assumptions are presented in Section 2 and the detailed proof' are deferred to Appendix [ For the empirical results, the experimental platform and the nyper-paramen settings are described Section 5 The core code for our experiments can be found in the supplementary material.
ACKNOWLEDGMENTS
This work is supported by National Key R&D Program of China (No. 2020YFA0713900 1900), NSFC Project (No. 12326615, No. 62192783), and Fundamental Research Funds for the Central Universities (No. 020214380108).
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems, pp. 1709-1720, 2017.
Zeyuan Allen-Zhus Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex stochastic gradient descent. arXiv preprint arXiv:2012.14366 2020.
Youssef Allouah, Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, and John Stephan. Fixing by mixing: A recipe for optimal byzantine ml under heterogeneity. In Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 1232-1300. PMLR,, 2023.
Yossi Arjevani, Yair Carmon, John C Duchi, Dylan J Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Progrumming, 199(1-2): 165-214, 2023.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, pp. 8635-8645, 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In Proceedings of the International Conference on Learning Representations, 2019.
Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pp. 119-129, 2017.
Saikiran Bulusu, Prashant Khanduri, Swatantra Kafle, Pranay Sharma, and Pramod K Varshney. Byzantine resilient non-convex scsg with distributed batch gradient computations. IEEE Transac- tions on Signal and Information Processing over Networks, 7:754-766, 2021.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. In Proceedings of the International Conference on Machine Learning, pp. 903-912, 2018.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 122):1-25, 2017.
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized sgd. In Proceedings of the International Conference on Machine Learning, pp. 2260-2268, 2020.
Georgios Damaskinos, Rachid Guerraoui, Rhicheck Patra, Mahsa Taziki, et al. Asynchronous Byzantine machine learning (the case of SGD). In Proceedings of the International Conference Machine Learning, pp. 1 1145-11544 1154, 2018.
Aaron Defazio and Léon Bottou. On the ineffectiveness variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, 32, 2019.
10

---

Published as a conference paper at ICLR 2024
Ilias Diakonikolas and Daniel M Kane. Recent advances in algorithmic high-dimensional robust statistics. arXiv preprint 11Xi::9111009111, 2019.
Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In Proceedings of the International Conference on Machine Learning, pp. 999-1008, 2017.
El-Mahdi El-Mhamdi, Rachid Guerraoui, and Sébastien Rouault. Distributed momentum for byzantine-resilien stochastic gradient descent. Proceedings of the International Conference on Learning Representations, 2021.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzan- tine machine learning made easy by resilient averaging of momentums. In Proceedings of the International Conference on Machine Learning, pp. 6246-624 6283, 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 Proceedings of the International Conference on Learning Representations, 2023.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch SGD: Training imagenet hour. arXiv preprint (00.::1700006660 2017.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 2545-2554, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In Advances in Neural Information Processing Systems, volume 30, 2017.
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In Proceedings of the International Conference Machine Learning, pp. 4387-4398, 2020.
Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael I Jordan. Communication--cficee distributed dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 3068-3076, 2014.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, pp. 115-323, 2013.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends in Machine Learning. 14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for Byzantine robust optimization. In Proceedings of the International Conference Machine Learning, pp. 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. In Proceedings of the International Conference on Learning Representa- tions, 2022.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In Proceedings of the International Conference Learning Representations, 2017.
11

---

Published as a conference paper at ICLR 2024
Konstantinos Konstantinidis and Aditya Ramamoorthy, Byzshield: An efficient and robust system for distributed training. Proceedings of Machine Learning and Systems, 3:812-82 828, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. In Concur- rency: the works of leslie lamport, pp. 203-226, 2019.
Jason D Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed stochastic variance reduced gradient methods by sampling extra data with replacement. Journal of Machine Learning Research, (8(1):440444446, 2017.
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceed- ings of the AAA/ Conference on Artificial Intelligence, volume 33, pp. 1544-1551, 2019.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the International Conference on Machine Learning, pp. 0286-6295, 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances Neural Information Processing Systems, pp. 5330-5340, 2017.
Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. In Proceed- ings of the International Conference Learning Representations, 2017.
Chenxin Ma, Virginia Smith, Martin Jaggi, Michael Jordan, Peter Richtárik, and Martin Takác. Adding vs. averaging in distributed primal-dual optimization. In Proceedings of the International Conference on Machine Learning, pp. 1973-1982, 2015.
Brendan McMahan and Daniel Ramage. Federated learning: Collaborative machine learning without centralized training data. Google Research Blog, 3, 2017.
Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy- based framework for faster and more robust gradient aggregation. In Advances in Neural Informa- fion Processing Systems, pp. 10320-10330, 2019.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiieenn distributed optimization using an approximate newton-type method. In Proceedings of the International Conference on Machine Learning, pp. 1000-1008, 2014.
Weisong Shi, Jie Cao, Quan Zhang, Youhuizi Li, and Lanyu Xu. Edge computing: Vision and challenges. IEEE Internet of Things Journal, 3(5):637-646 2016.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jackyun Moon. Election coding for distributed learning: Protecting signsgd against Byzantine attacks. In Advances in Neural Information Processing Systems. pp. 14615- 14625, 2020.
Shizhao Sun, Wei Chen, liang Bian, Xiaoguang Liu, and Tie- Yan Liu. Slim-dp: multi-agent system for communication-eficcii distributed deep learning. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pp. 721-729, 2018
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European Conference on Computer Vision, pp. 3-19, 2018
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced stochastic gradient descent with robustness Byzantine attacks. IEEE Transactions on Signal Processing, 68:4583-4599 2020.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-base fault-tolerance. In Proceedings of the International Conference on Machine Learning, pp. 6893-6901, 2019.
12

---

Published as a conference paper at ICLR 2024
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking Byzantine-tolerant sgd by inner product manipulation. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp- 261-270, 2020.
Tianbao Yang. Trading computation for communication: Distributed stochastic dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 629-637, 2013.
Yi-Rui Yang and Wu-Jun Li. BASGD: Buffered asynchronous SGD for Byzantine learning. In Proceedings of the International Conference on Machine Learning, pp. 11711-11761, 2021.
Yi-Rui Yang and Wu-Jun Li. Buffereed asynchronous SGD for Byzantine learning. Journal of Machine Learning Research, 24(204):1-66 2023.
Zhixiong Yang, Arpita Gang, and Waheed U Bajwa. Adversary-resilienr distributed and decentralized statistical inference and machine learning: An overview of recent advances under the Byzantine threat model. IEEE Signal Processing Magazine, 37(3): 146-159, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In Proceedings of the International Conference on Machine Learning, pp. 5650-5659, 2018.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in Byzantine Byzantine-robust robust distributed learning. In Proceedings of the International Conference Machine Learning, pp. 7074-7084, 2019.
Yang You, Jing Li, Sashank J. Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song. James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In Proceedings of the International Conference on Learning Representations, 2020.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 7184-7193, 2019a.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 5693-5700, 2019b.
Shen- Yi Zhao, Ru Xiang, Ying- Hao Shi, Peng Gao, and Wu-Jun Li. SCOPE:
scalable composite optimization for learning on spark. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 2928-2934, 2017.
Shen-Yo Yi Zhao, Gong-Duo Zhang, Ming-Was Wei Li, and Wu-Jun Li. Proximal SCOPE for distributed sparse learning. In Advances in Neural Information Processing Systems, pp. 6551-6560, 2018.
Shen- Yi Zhao, Yin-Peng Xie, and Wu-Jun Li. Stochastic normalized gradient descent with momentum for large batch training, arXiv preprint 20X0:20007.1388, 2020.
Shen-Yo Zhao, Chang-Wer Wei Shi, Yin-Peng Xie, and Wu-Jun Li. Stochastic normalized gradient descent with momentum for large-batch training. Science China Information Sciences, 2023.
Yi Zhou, Yingbin Liang, Yaoliang Yu, Wei Dai, and Eric P Xing. Distributed proximal gradient algorithm for partially asynchronous computer clusters. Journal of Machine Learning Research, 19(1):733-764, 2018.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex J Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 2595-26008 2010.
13

---

Published as a conference paper at ICLR 2024
A BYZANTINE-ROBUST SGDM
The detailed algorithm of Byzantine-robust SGDm (ByzSGDm) the server and workers presented in Algorithm 2 and Algorithm 3 respectively.
Algorithm 2 ByzSGDm (Server)
T-1 Input: worker number iteration number T, learning rates {7/ tt= robust aggregator Agg(-) Initialization: model parameter Wo:
Broadcast
all workers;
for 0 7 do
Receive {u, ym ) from all workers, and compute u, Agg(", ( ....,
,..., u
(m));; );
Update model parameter Wx+1 We U,
Broadcast 1 to all workers; end for
Output model parameter Wy-
Algorithm 3 ByzSGDm (Worker_k)
Input:
iteration number T, batch size B, momentum hyper paramee B E [0,1); 1);
Receive initial model parameter wo from the server; for = to T do
Independently draw B samples St Compute g:
(R..1)
(k.B) from distribution D;
EE
(R.)))
B
(k)
Update local momentum 11;
(k)
80
t 0:
Bu, (k)
(1 3) (8)
0;
Send u, to the server (Byzantine workers may send arbitrary values at this step); Receive the latest model parameter We+ from the server; end for
(R)
B PROOF DETAILS
B. PROOF OF THEOREM
Proof. It has been proved in (Karimireddy et al. 2021) that for ByzSGDm, we have
T F < 161
82(1 + cōm) (10LF, + 3c803) + 32LF, I'm
200 (1 + cōm)
(6)
T
T
I'm
where 8² the variance of stochastic gradients. the setting of this work, we have Ø² 0² /B where B is the batch size on each worker. Therefore, we have
T-1
@1 + cōm)
3eda² (ILFot+ +
32LFo
20 + cōm) (7)
E (W:)( ) < 1
B +
+
TBm
T TBm
Moreover, since for all y 0,
v + / S Vx V (Vz)2 (VD)2 < V VB.
(8)
we have that
1 \
$1
2
x + v
14

---

Published as a conference paper at ICLR 2024
Therefore, we can replace the term the convergence order. Consequently, have
10LFo + 3 with VIOLFo +
30da2 B
without changing
8² + cdm)
VIOLLO +
3cdo²
32LFo
20 + côm)
[W:)F(: < 161
T
TBm
TBm
(10)
B.2
PROOF OF PROPOSITION 1
Proof. Since
0 cdm)(1 - 6)
(VIOLFS +
3c5o² B
10LFoBm(1 -5)
U(B) 161
V
+
C
20 + cdm) -)) (11)
is not hard to find that (B) continuous and differentiable on (0, +x0). Then we analyze the convexity of (B) by showing that it has positive second-order derivative. For simplicity, we define constants A₁, Ag and A3 as follows:
10L + c5m) 8)02
20(1 cdm))( 8)0²
A 16V
+
(12)
C
330(1 + cdm (1 -10)a
A2 = 16
(13)
C
Ag 32LFom(1
(14)
C
According to the definition of UBB), we have
u(B) A1 A AsB,
Be (0,+
(15)
Therefore,
U'BB) ラ A2 A3,
B (0,+00).
(16)
Thus,
(B = A2B > 0,
(0, +o0).
(17)
which implies that U(B) is strictly convex. According to 16.. the equation (BB 0 has the only solution
$
A2
16
3c6( 3c6(1+c5m) (1-6)
/300(1 + com)otc
B"
(18)
2Ag
2
32L.om( (1mm(11)))
ALFomvI-0
+ *(0011
+ c5m)
(5m m(1 6)
cict.
(6))
(19)
Thus, B" is the only global minimizer of (BB). The minimum value L((B)) is:
u(B)= =u (
A2
(20)
2Ag
(A2)
A₁ +3
(21)
4
15

---

Published as a conference paper at ICLR 2024
16 16/100FF(11 + (1 8)0
20(1 + cdm)(1 5000
C²
2
16
3rd(1 +.om)) 6)
+ 3
(22)
4
107.Fo + com)( (1 - 8)0
20(1 + cdm) -8)0²
C#
24
[1200(1 + -1m))(15))
-
+
(23)
C3
B.3 PROOF OF THEOREM 2
Firstly, we present Lemma below, which quantitatively shows that the variance of stochastic gradients can be reduced by increasing the batch size B.
Lemma (Mini-batch variance reduction). Under Assumption
we have that Vk G.
gr (k)
VF(w:)]
o²
E
AI 20
(24)
B
(k) Proof. By the definition of g:
1 B
gt
(k)
(25)
Since for all & E G, B with bounded variance a² have that
(W,,,
(w,, c/ (8.00)
= F(w.) and V.(W,, (k:B)) is independent to each other
o²
g
(k) v F
F(w:)
(26)
Moreover, by using
inequality, it is obtained that
E
g1
(k)
VF(w:))
E
(k)
VF(W.)
VB"
(27)
We define
1
Σ
(k) u
(28)
kEG
which represents the exact averaging local momentum all non-faulty workers e G. Then we provide upper bound for the aggregation error of (fmax, c)-robust aggregator in Lemma The notation of a, is only used for theoretical analysis, which does not appear in the algorithm.
The proof of Lemma is inspired by the existing work (Karimireddy al. 2021). Moreover, have improved the analysis details, and the upper bound of aggregation error in Lemma is tighter than that in (Karimireddy et al. 202Ip.
Lemma (Aggregation bias). Let 1- B. Under Assumption
when Agg(.) is (6max. robustt
and 8 < 8max we have that
2c502 2
E U - 12 <
ja + (1 -
a1
(29)
B
16

---

Published as a conference paper at ICLR 2024
Proof. Let a 1- 3. For all 2 0 and fixed k, k 9, since gi is independent to g: and (k)
(k)
(R)
4
u u (k')
(R)
(1 a) u
gi
gi
|/1
(30)
(1 a:) (K)
+ E
olgi
(k)
g1
1
(31)
(1 a))
(R)
2
g1
(k)
VF(wi)
(32)
(1 2E
(K)
2a²0
(33)
Recursively using the inequality above, we have that
(k)
u1 < - a
(K')
2
up
20
[1 + (1 a)) + +...+
+ (1
B
(34)
= (1 a)
80
(K)
80
(k))
2
+
1- (1-1-a) a 2t
(35)
B
1 1- a1-a)
20
2a 2
1
(1 a)2²
(36)
B
B
a - a)
20
20002 2
<1 a)a
(37)
B
B
20 a + a1
(38)
According to the definition of (8max; ro-uut aggregator,
E
Agg(u
(1 (1)
u (m))
(k)
2cdo²
(a (1 =a)
(39)
kES
Namely,
20ōg
El u ū. 12 <
aa+ + (1 - 22)
(40)
B
By using Cauchy-Schward inequality, it is obtained that
200 a + (1-aa) (1-a)22jo
11 ü.l || S / u. 1 &
(41)
B
Based on Lemma 2 we can further obtain Lemma 3 which provides an upper bound for the difference between the aggregated momentum u, and the global gradient (W..).
Lemma 3. Under Assumptions ] andd when Agg(-) (8max, co-bousst. 8max and ne 17, we have the following result for ByzSGDmm:
nL a
V 2cmo(1 8) [(1-a) vo 0. Wt 2
E u VF(ww)l
(42)
v Bm(1 8)
Proof. Vt 2 we have that
ū, VF(w.) 9
u
(k)
VF(w:)
(43)
kEg
gu
(k)
+ (1
() (k))
-V((w)
(44)
|
keg
17

---

Published as a conference paper at ICLR 2024
11-3
= = +
(19)
Σ
Bi
(k)
FW(w))
(45)
[
kEG
= =B/ū,-1- [F((w)]
gi
(k)
VF(w))
(46)
[
kEg
= = -
+VF VF((
3 [g(h)
VF(w.))
)
|9
kEg
(47)
Recursively using the equation above and substituting 3 with 1 a, we have that
ü - VV((w) = (1 - a) VP(wo)] +
Σ (1 (V
VVF(w-II)
P=1
- -VF(we)) (k)
+
a) t-t
Be
(48)
t=1
kEg
Noticing that up 80 we have that Un VF(wo) T ExeglBe (1) VP(wo)]. Therefore,
(k) (k)
u, VF(w.) Σ
(VF(w))) Vf(We-1)]
1 (1 a) 1 (x) VF(ww)] + D (1 a) 1 (g VF(w
g
kEg
['=1
(49)
According to Assumption 3
- VF(we-1)l - S L El We-1ll = L- LE 1 ure
ue-
nLL
(50)
Since gi (k) 's are independent each other, by using Lemma
and | (1 8)m, we have that
(1 - ()(
g (M)
[F(w))] + a
a)--
(k)
<F(We))]
-
kEg
E
(1 - 18
(k)
VF(wo)] + Σ
(1
a)
1- (k)
g
- VF(w:)]
G
KEG
p=1
(51)
(1 - a) 2 |s0" - vF(mo))
+ +
Σ
a)
20
ge
_
(k)
VF(we)
12
#=1
(52)
1
19662
(1 ))2 aa Σ (1 xz) 2 22
(53)
6
B
1==1
- (1 x 21
11 20 2
(54)
/Blg|
1 - (1 a) 2
1 (1 a) 2
(1 k + 0
(55)
/lg
- )
18

---

Published as a conference paper at ICLR 2024
(1 0² + 01
(56)
/Blg
a(2 a)
(1 a) + a
(57)
2
(1 a)' val
(58)
Bmm(1-0]
Consequently,
E u
VF(w))ll nT
Σ (1--a)-- a)
[11 [11- az)² val
(59)
Bmm(1 - 8)
r'=l
nL
+
[(1 -a)* + val
(60)
v Bmm(1-
Since Bllu: u S v u; ú, 2 according to Lemma we have that
u, [F((w)) $ E Elu, VF(w:))l +E|| [ üel
(61)
1
V Bmm(1 -8) 8) [(1 - a) + vol + 200 a + (1
a)
(62)
VB
71
(1-a)) + val 220 + (1 a)
+
(63)
a
v Brn(1 -0)
vB
n1
22emō(1 - -6) +0
[(1 a) + Vala. o.
(64)
a
v /Bm(1-4 -)
Then we present the descent lemma for SGD with normalized momentum. The proof of Lemma is inspired by the existing work (Cutkosky & Mehta 2020), but the result in Lemma 4 is more general than that in (Cutkosky & Mehta 2020).
Lemma 4 (Descent lemma). Under Assumptions 7 and for any constant 7 (0, 1), we have the following result for ByzSGDnm:
2 |u VF(w:)) F(we+1) S F(w.) 11 ++ VF(w)))l + m 7(1 + 77)
(ne)
(65)
2
Proof. According to Assumption
we have that
u, m
F(we-1) = F(w:: T
(66)
$ F(w)) F(W))
17t
W1
+
L
1)
U
(67)
|
[u
VF(w,)"
2
F((w)) TJ
(68)
|
Let E 1) be an arbitrary constant. Then we consider the following two cases:
(i) When [u
VF(w:)] S <>:))F(w:)]l we have
F((:))
"u
v F((we) ): (V.(). + (u, - VF(w.))
1/
7)t
(69)
[1e]
VF W:) + (u, VF(w.))
FF 2 - |VF(()))) (2)) | VF(w.))
<-
(70)
[FF(w)]] + Iu: VF(w:)l
19

---

Published as a conference paper at ICLR 2024
VF (1, -/
S - 71
(71)
(1+))]VF((w))
7 (w.]l
// 1 +7
(72)
1-? ?
2 I 7(1 + 7)
S 71 +
[F(())ll + ?
VF(w))ll
(73)
(ii) When - VF(w:)]l > 7 (w.)ll we have
VF(w,,) 7
1/1
/nelVF((w.))
(74)
uell
71t +
7
( + "1t
2
VF(()))]
(75)
1-
2
11 177
VF + 70
| VF(w))ll
(76)
7(1
+
In summary, we always have
(W(w))
Iuu
uu
1-
2
1/1
1/1
VF(w:))
7/6 7(1 77)
||u VF(w)ll
(77)
11l
1+7
Therefore,
1 - 7 VF + m
2
(nt)²L (78)
F(W(+1) S F(wi) 1)6
|u VF(w:)) +
7(1 + +7)
2
Finally, we can obtain Theorem by recursively using Lemma taking expectation on both sides and using Lemma 3 The proof details are presented below.
Proof. Recursively using Lemma 4 from O - and letting T) 1}. have that
(1- VF(())l +
T-1
2n
T-1
TT²2L
F(WT) & F(wo)
| F(()))l
(79)
1 1
7(1 +7)
2
Therefore,
T-1
[VF(W) < (1+1) - F(WT)) (1 v)ri
T-1 Σ - VF(())
(1+ 7)
T t=
Ty(1 -7)
2(1 - 7)
(80)
According to Assumption we have that F(Wr) 2 F*. Furthermore, by taking expection on both sides, letting ? and using Lemma 3 is obtained that
w.)l \| < 2(F( - F=]
9 T
Elu, VF(w;)] +
(81)
T/T
T
1=0
2(F(wo) F=]
9LL +
9 2c +9 ( aT + +va o + nL
+
nT
v Bm(1 - -)
(82)
2F
10nL
9 9 2cmo (1 8) +
1
+
VBm(1 aT' + va
(83)
T
a
20

---

Published as a conference paper at ICLR 2024
B.4 PROOF OF PROPOSITION 2
Proof. Learning rate 1) appears only in the first two terms of the RHS of inequality 2
Thus,
T-1
2Fu
10nL
9y 2emom - 8) +
1
E
(W:lll
-
+
T
n/"
BBm(1 -)
aT
2Fo
10nL
aT vā
1
(84)
T/
VBm(1 -mm(l-6)
80LFo
9 /2mm(1 6) +
af + va o.
(85)
oT
v VBm(1 6)
The second equation holds only and only if 25 Furthermore, since a = min
10nL which is equivalent to that =
F
7/
527
p 2cmm(11 ()) 90)--))0++""""") oVT 1)
801 Bm(111)))
we consider the following two cases.
S0LFo Bm
(i) When a 9 2cmo(1 1 -6)49 6)+9
we have that
( 2cmoml -8 +1]
5LFoo²
TBm(1 -5)
27
/2cmmm1 - 8) +
+
/v m22 - -F) 0².
(86)
(ii) When a 1, it implies
80L Bmi1-
2 Namely,
9 122mm8(1-044
/OLFF VT
In
9 20mb(1 +9
o OVT
v BBm(1-8)
this case,
80LFo aT
9 2cmo(1 - 8) +9 ( 1
va va)o
(w:)l
(87)
BBm(1 - 8)
aT
80LFo T
SOLFo
S
T +1)
(88)
T
5LFo
<
12
(89)
T
In summary,
T-1 Σ
B/VF < /2cmm((1 ( -8)
5LFo02
5LFo
TBm(1- (1-8))1)) -8)
+ +12
T
T
1=0
3
27 22c2 - 5) +
+
(90)
4 5T ml (100(11-11111
8/2
In addition, when C = T'mm11 - 8) is fixed, we have
BllVF(w.)]l < 6 220mm(11 6) 113
3 5LFoo 1/2
Σ
C
A=0
5m(1 8)LFoB
27
v /2cmo(1 - 58
+ 12
0².
(91)
C
4/5m(1 - 5)LFFCB
21

---

Published as a conference paper at ICLR 2024
Moreover,
5m F)..FBB
27
2cmo - 8) +1
12
0²
C
4/5m(( - O)LFBBB
5m(1 - 5)LFoBB
27
22mo0(1 -
2
2
121
02
(92)
55/mm( (1- 5)LFGCB
18
2cmo - 8) +1
(93)
C
The equation holds if and only if
27 /2cmm 6) 1
5m - o)LFoB
1
4/5m(1 5)I.FoBB 0²,
(94)
C
which is equivalent to that
9 2emo(1 - 6) + +112 0²
B
(95)
80m(1 L.u
C DISCUSSION ABOUT THE ()) -R.-BOBUUSSESS
The theoretical analysis in the main text is based on the definition of (6max, c)-robust aggrega- tor (Karimireddy et al., 202T). In this section, we show that similar results can be obtained under the definition of (f. k) robuustssss (Allouah et al. [2023). In existing works [1] f is defined to be the number of Byzantine workers. However, we have used the notation f to denote the loss function in this paper. In order to avoid misunderstanding. we will use mo to denote the number of Byzantine workers in the following text, where m is the total number of workers and is the fraction of Byzan- tine workers. Firstly, present the definition of (8, x) rrobust aggregator, which is equivalent to the (f, rob-ustsssssss (Allouah et al. 2023) since the worker number m is deterministic this paper.
Definition 2 ((5, robusttsssss Let 5 [0, }) and K. 2 O. aggregator Agg(:) is called (8, k) k)-robust aggregator for any vectors X1...., Xm E IRd and any set G C (1,...,, ,,] satisfying [9] (1 5)m, have that
Agg (x1, XI....,, .I,....,,.) xol12 5
K
|x
xol1?
(96)
kEg
where Xg = [8] Eneg X
Thus, for (5, -rouutt aggregator Agg(:), when (xx )eer is a set of i.i.d. random vectors where
C (1....,m) m.) satisfying 9 = (1 - 5)m and E|[x+ | = o² for each h: E G. we have:
Aggggx X1, xm) Xgl 2 <
X
Xg
RO² =
kO²
[
(1 6)m
REG
(97)
Mcanwhile, for (fmax: -obuut aggregator Agg(-). ),, when {xx keeg is set of i.i.d. random vectors
where G C {l...., m) satisfying G 5)m and [E|[x - B[x+]1" = o² for each E G, we
have E xx 2 < 2 according to 2 and thus
E Agg X1, ......y Xm) xo11² < 20502
(98)
22

---

Published as a conference paper at ICLR 2024
find that in i..d. cases, the upper bounds of aggregation the two definitions are of the same order O(a²). Moreover, the other factors [9]. Ki e and 6 will not change during the distributed learning process. Thus, to obtain the optimal batch size that minimizes the theoretical upper bound under the (ő, k) robbbussssss we can simply replace the factor of with
Comparing (97 and 198)
under
(1-
Recall that the optimal batch size that minimize the theoretical upper bound for ByzSGDm and ByzSGDrm under the definition of (Ōmax: robussssss are
co(1 + cdm) ) oick (mml1--0) m(1 (((1-))) 5)
B = (16L2(F))M))
(99)
and
B 21 - 8) +1
2²
9
22mB (1-8)8
(1-6) 1665
(100)
80m(1-8)LFF
80m
respectively. Thus, under the definition of (ô, k)-rrouustness, the optimal batch size that minimize the theoretical upper bound for ByzSGDm and ByzSGDnm are
$
[6( +mmm $ oick.
3
16L2 (Fo)
m - 8)
and
26m (1-8)6
(1-6)
80m L.o
respectively. Notice that the term I-8 is monotonically increasing w.rt. d. Thus, in order to prove that the optimal batch size monotonically increasing w.r.t. 8, we only need to prove that is monotonically increasing w.r.t. 5.
8ym
has been shown in existing works (Allouhh al. 2023 that (i)
I-28 for Krum, (ii)
1-26 (1 + 1-26/ for coordinate- wise trimmed-mean (iii) (1+ +
5
)2 for coordinate-wise
1-26
median and geometrie median, and that (iv) the lower bound for и 1-26- Then we prove that monotonically increasing w.r.t. ö for these four cases separately.
Case (i). For Krum, we have K = 1
5
(0
5 < }), and thus,
1-26
1
5
(
1
τ(6)
1
(101)
28
(1
8)m
1- 8
1
(102)
1 25
(1 8)m
8
26 m
(103)
2
Therefore, the derivative of č(8) is
1 -(1 - 26) + 2(1 8-
(6)
(104)
2
(1-25)2
2m - 28)2
Since the fraction of Byzantine workers is smaller than J. Byzantine worker can appear only when the total worker number m > 2. Thus, we have m 2 > 0. In addition, (1 28)2 > since 0 < 8 < }.
Therefore, we have 8' (6) 0. and ē(5) monotonically increasing w.r.t. 5.
Case (ii). For coordinate-win trimmed-mean, have
8 1-28 (1 1-22) Thus,
8
(1+
8
(1
1
{())
(105)
2 1 25
25
(1
1-8mm
23

---

Published as a conference paper at ICLR 2024
(1- (1 8)m ) (1- 26
1 1 28
(106)
2
It has been proven in case (i) that the first term (1 5
1-28 (1-
is monotonically )]
increasing w.r.t. 8. Since both ó and 1-26 increase ó E [0, 2 increases, the second term 1-25 is also monotonically increasing w.r.t. 5. Moreover, the two terms are both positive. Thus, have that o(6) is monotonically increasing w.rt.
Case (ii). For coordinate- wise median and geometric median, we have = (1 + 1-28)
)2. Thus,
1
8
c(6)
= 2
1
1
28
-
(1 8)m
(107)
1
(
]
8
1+
+
(108)
2
1 - 28
(1 8)m
1 28
has been proven in case (i) that the first term increasing w.r.t 5. Since both d and 1-28 increase as 8 [0, })) increases, the second term
1 1-28
5
monotonically
(1-5)m
(I+ 1-28 is also monotonically increasing w.r.t. 8. Moreover, the two terms are both positive. Thus, we have that č(6) is monotonically increasing w.r.t.
Case (iv). The lower bound for x: is K = 1- 28
Thus, the lower bound for č(6) is
5
a(6)
1
(109)
1 25
(1 - 18)mmm
8
(1- (1- 1
1
1
1)
1
(110)
2
26
(1- (1-8)m
2
(1 8)m
has been proven in case (i) that the first term
2
(1+122)
1
1-28
(1)mm
is monotonically )]
is also monotonically increasing w.r.t. d. Thus, for the lower bound of k, č(6) is also monotonically increasing w.r.t. 5.
increasing w.r.t. d. The second term 1 [1-8)m -1)
In summary, under the definition of (f, robuusstss, the optimal batch size that minimize the theoretical upper bound for ByzSGDm and ByzSGDnm increase with the fraction of Byzantine workers 5. The results consistent with those under the definition of (6max, c)-robust aggregator.
D COMPARISON WITH BYZ- -
We compare ByzSGDnm with BAAARRAMA GGorbunov et al. 2023) in this section.
D. VARIANCE REDUCTION TECHNIQUES
We first compare the techniques for variance reduction in ByzSGDnm and Byz- Byz-VR-Me VR-MARINA. As presented in the main text, in ByzSGDnm, the variance of stochastic gradients is reduced mainly by using (i) large batch size and (ii) local momentums. The two techniques introduce little extra computation cost but are empirically effective, as the empirical results in the main text show. However, the techniques work only in the i.i.d. cases that focus on in this work.
Byz-VR-MARING adopts PAGE et 2021) for variance reduction. In contrast to the techniques in ByzSGDnm, PAGE can reduce the bias in general non-i.i.d. cases but introduces much more computation cost (as we will shown in Appendix D.3).
D.2 COMMUNICATION COST
ByzSGDnm and Byz- -R-MARINA take different ways to reduce the communication cost in dis- tributed learning. ByzSGDnm uses large-batch training (Cutkosky & Mehta 2020 Goyal al.
24

---

Published as a conference paper at ICLR 2024
2017 You et al., 2020) reduce the number communication round while Byy--R-MARRE uses communication compression such as quantization (Alistarh et al. 2017) to reduce the transmitted bits in each communication round.
D.3 COMPUTATION COST
Since the computation cost mainly comes from gradient computation in many real-world distributed learning applications, we use number of gradient computation on non-Byzantine workers to estimate the computation cost for both methods. In ByzSGDnm, each of the mn(1 - 5) non-Byzantine workers will draw a mani-batch B samples and compute the corresponding stochastic gradients at each iteration. Thus, the total number of gradient computation in each iteration for ByzSGDnm is Bm 8). In each iteration of ByZ-VR-MARINA each of the m(1 6) non- -n--Byzantine workers computes the full gradient with probability p and computes a mini-batch estimation of gradient differences with probability 1 p. Since the estimation with batch size B requires 2B times of gradient computation, the expectation of the total number of gradient computation in each iteration for ByZ-VR-MARINA is (1 - 8'm + 2B - 6) p) where ni is the total number of training instances. Therefore, the number of gradient computation in Byz- VR-MARINA for each iteration ke times that of ByzSGDnm in expectation, where
lic A (1 - 8mmp + 2Bm(1 (1 -) npp + 2Bm(1 - -p) 2 + Bm -2)-
n
2):
Bm(11 6)
Bm
n Since Bm is the total batch size of each iteration and n is the total number of instances, Bm is the number of iteration per epoch, which is typically much larger than 2. Therefore, the number of gradient computation for ByZ-VR-MARINA is more than twice that of ByzSGDam in expectation.
D.4 THEORETICAL CONVERGENCE ORDER
As we have proved in Section in the main text, under Assumptions and
we have
min E| V/ s
T
or equivalently
1 0
E VF
T
for ByzSGDnm with (6max; c) robust aggregators. Meanwhile, the results in Gorbunov al. (2023) show, under similar conditions, we have
V <o t=
min
T
Byz- VA-IAN. has been shown in existing works (Arjevani al., 2023] Cutkosky & Mehta 2020) that convergence order min, E[[VF((w,)) < (1/TTt) optimal for SGD under Assumptions and Byz- MRAAIIA achieves the faster convergence order mainly because of intermittently using full gradients for variance reduction. The strategy of intermittently using full gradients also adopted in some traditional methods such SVRG (Johnson & Zhang (013). Although using full gradients improves the theoretical convergence order, also increases the expected number of gradient computation as discussed in Appendix above.
In summary, compared to ByzSGDnm, ByZ-VR-MARINA has faster theoretical convergence order with respect the iteration number, but also requires more times of gradient computation per iteration. Moreover, the number of gradient computation for Byz- VR- MR-MARINA depends on p and n.
D.5 EMPIRICAL PERFORMANCE
Finally, we empirically compare the performance of ByzSGDnm and ByZ-VR-MARINA, The experimental settings the same those presented in Section 5 of the main text. Specifically, we use cosine annealing (Loshchilov & Hutter 2017) learning rates for each method. The initial learning rate for SIZ-VR-MARINA is selected from {0.005, 0.01, 0.02, 0.05, 0.1, 0.2, 0.5, 1.0), and
25

---

Published as a conference paper at ICLR 2024
the best final top-1 test accuracy is used the final metrics. We set the batch size to 512 x 8 for ByzSGDnm. We use the top-1 test accuracy w.I.t gradient computation number as final metrics. For fairness, we do not use communication compression for ByZ-VR-MARINA, The empirical results of Byz- -R-MIIA when the batch size is 32 x 8, 64 x 8, 128 x 8, 256 x 8 and 512 x 8 are presented in Figure T Figure 2
Figure 3 Figure and Figure 5 respectively.
100
100
90
50
80
80
Mpl
ByphaBBee with
-yyestOrnn with
Bg MAR RA with CR BB-22 pob.25 Bpa-VR--AA VAR BA BB-22 prb.l)
Bye- MARIMA a GM Bi42 2
20
SyE-HR-ARRIA with GN p-dll
GoSSERtCOTOUUE number
Too 10tace90
20
To 10022009
70
Bybtibrre with C.N.
EycSGDrmaih CC
Byn (462 MA with Bul2 pub.2)
Eyp MARRIAA with BB 2i02)
Byo S.------AA MAAINA with 10
Eya MARINA CC 18452 25
3 Grstentccorp///inn tumber
Gradere.comppuiiee FLIVOO
115
Figure 1: 1 test accuracy w.r.t. gradient computation number of different methods when there 3 workers under ALIE attack. The batch size for ByZ-VR-MARINA is set 32 8.
60
60
50
500
40-
Bys3 with KR Byniilk- MAR -d
-yesSOrm with GM
BNA pot.2
Eyc-vi with GN B--4 p-t
MARRIA ME--IRAAAAAAAAAAAA w ON Buide n5
Byr--v-- VAR W.S with BR p15.15
Gossiettcorouuttoo number
CoOSU number
xad
100
100
132
MM Mappoaanaaa po
Tox b0000
Tox bocoo
2
12
TystDrmaatcc
Byn- AMA NN with CM B pi6.1) Byritt MMA5 BR pi5.05
Eyp MARIMA CEYCE 1 p16.1)
Twp.R- MARIAAARAAA CRICC (Ritt 210RSS
-12
Figure 2: Top-1 test accuracy w.r.t. gradient computation number of different methods when there are 3 workers under ALIE attack. The batch size for Byz- -RRRAA is set to 64 x 8.
26

---

Published as a conference paper at ICLR 2024
100
100
50
50
80
80
Dystiliire KR
Sap-/R--MAARB with ER 10 prb.2)
20
Bye-Bn----- MARMA with GM 8-120 pro Dpe MARRAA DM 1- p
BeeSSDDen with GM
1pe-/R-MMAR.B with 10-220 pre.l)
Gootent number
M
Top 10taacoi
11220000 100 1200000
Eyc522tere with CH
Byp5 C00EC
Bae-ttt--44 MAB with B-
pmo.)
EXAAR-RARIIN cC 1 21021 MARING ByoaR MARIING with CC 184188.4 055
By.-va 1866 Wi with B-028-00 oi (5
3 Grutenccoompiiiinn number
Gradkeniccmm pu biiion FLIVO
Figure 3: Top-1 test accuracy w.r.t. gradient computation number of different methods when there 3 workers under ALIE attack. The batch size for ByZ-VR-MARINA is set 128 8.
70
70
60-
60
50
50
GBre wD KR
5yc30Cmm with
MAR-BA with 220
Danii MARRRA
Bap VE. MARINA with 19250
Byg MARINA ON
Goddiett www.uetiis
Tos busocuuq
Tos lusoccuq
82
33
B-256
MARIN with B-256vd
Byz Iik N4l Mi with Ba256 pa0.3
Byg vi MARINN with CC 3 1-61))
Byg (e. Mi4 with Bw256-08 ES
Byp VR (44 wtt Ba256 156055
corrp
Figure 4: T test accuracy w.r.t. gradient computation number of different methods when there are 3 workers under ALIE attack. The batch size for Byz- VR-MARINA is set to 256 x 8.
As illustrated in Figure I Figure 2 Figure 3 Figure 4 and Figure 5 ByZ-VR-MARINA converges much more slowly and has a much lower final top-1 accuracy than ByzSGDnm. There are mainly two reasons. Firstly, the full gradients in Byz- MR-MARINA is used to alleviate the bias in non-i.i.d. cases and is computation expensive. However, in i.i.d. cases that we focus on in this work. the full gradient is unnecessary and requires large number times of gradient computation. Secondly, it
27

---

Published as a conference paper at ICLR 2024
100
100
50
50
80
80
Dyttiitres KR
Sap-1/R-MMA-BBA with ER 10-532 prb.2)
Dye-2 MARRA with GM 8-522 pro21
MAR-BAA with 10-012244 pre.l)
104
Dpedit 1-512NE p
GOSEERCTOOEE number
Top 2astxcae
10)
Eypt2ttere with CH
Byp5 SDers 6.
Bae M48 with 18-522 pm0.)
Exp-NT-RORII LB-532 21221
MARING with 4 05
By.- 1666 Wi with B8532 cB (5
MARING BypAR-
3
3
Gradeeniccmm pu bidion FLIVO
Gruiencccompuiiinn numbe
Figure 5: Top-1 test accuracy w.r.t. gradient computation number of different methods when there 3 workers under ALIE attack. The batch size for ByZ-VR-MARINA is set 512 8.
has been shown in existing works (Defazio & Bottou 2019) that using full gradients for variance reduction does not improve over SGD on deep learning models.
E
MORE EXPERIMENTAL RESULTS
E. INDEPENDENT AND IDENTICALLY DISTRIBUTED (LLDD.) CASE
Final top-1 test accuracy when using different batch size. We present the empirical results of ByzSGDm and ByzSGDnm with different batch size (ranging from 32 x 8 to 1024 x 8) under no attack or failure, under bit- fitppiiii failure (Xie al., 2019)), ALIE attack and FoE attack in Table 7 T8 Table and Table TO respectively. Specifically, workers under bit-fipping failure will send the vectors that are -10 times the true values. The final top-1 test accuracy the two methods under ALIE attack when NNM technique (Allouah et al. 2023) is used is presented in Table below.
Table 7: The final top-1 1 test accuracy of ByzSGDm and ByzSGDnm with different batch size when there is no attack or failure
Batch size
32x8
64x8
128x8
256x8
512x8
1024x8
ByzSGDm + KR
91.08 %
89.98%
89.71%
89.15%
86.15%
84.97%
ByzSGDnm + KR
91.00 %
90.15%
89.23%
88.76%
87.83%
84.71%
ByzSGDm GM
92.02 %
91.50%
90.85%
89.26%
88.21% %
86.52%
ByzSGDnm + GM
92.18%
91.81%
91.22%
89.93%
90.01 %
88.08%
ByzSGDm + CM
92.30 %
91.79%
90.43%
89.84%
87.27%
84.06%
ByzSGDnm + CM
92.29%
91.70%
91.15%
90.20%
89.06%
88. 11%
ByzSGDm + CC
92.52% %
91.74%
90.63%
89.40%
88.78%
85.50%
ByzSGDnm + CC
92.51%
91.91%
91.50%
90.00%
89.33%
88.47%
28

---

Published as a conference paper at ICLR 2024
Table 8: The final top-1 test accuracy of ByzSGDm and ByzSGDnm with different batch size when there are 3 Byzantine workers under bit-flipping failure
Batch size
32x8
64x8
x28x8
256x8
512x8
x024
ByzSGDm + KR
91.09%
90.30%
89.55%
88.37%
87.52%
85.68%
ByzSGDnm KR
90.71% %
90.14%
89.59%
88.89%
85.76%
82.22%
ByzSGDm + GM
88.97%
89.18 %
88.61% %
87 87,43%
85.72%
83.56%
ByzSGDnm + GM
88.64%
89.16 %
88.89
88.22%
87.78%
86.21%
ByzSGDm + CM
86.80%
87.11 %
87.40 %
86.37%
85,40%
81.23%
ByzSGDnm CM
87.39%
88.12 %
87.66%
86.76%
86.33%
85.52%
ByzSGDm + CC
88.92%
88.97 %
88.78% 88.96%
88.02%
86.54%
83.93%
ByzSGDnm CC
88.81 %
88.89%
88.45%
87.56%
85.53%
Table 9: The final top-1 1 test accuracy of ByzSGDm and ByzSGDnm with different batch size when there are 3 Byzantiie workers under ALIE attack
Batch size
32x8
64x8
128x8
256x8
512x8
1024
ByzSGDm KR
38.55%
55.15%
55.98%
59.28%
83.42%
83.45 %
ByzSGDnm KR
43.47%
70.88%
80.20%
82.83%
85.12%
85.93 %
ByzSGDm + GM
63.1 11%
70.88%
82.08%
87.62 %
86.95%
84.75%
ByzSGDnm GM
69.45%
83.23%
86.63%
88.66%
89.13%
88.16%
ByzSGDm + CM
33.11%
55.66%
66.38%
82.47% 83.55%
83.25 %
80.94%
ByzSGDnm CM
61.28%
71.46%
80.24%
86.03% %
85.74%
ByzSGDm CC
72.83%
79.45%
84. 94%
87 97.25%
87.46
83.70%
ByzSGDnm + CC
78.50%
83.91%
86.56%
88.32%
88.53%
87.89%
Table 10: The final top-1 test accuracy of ByzSGDm and ByzSGDnm with different batch size when there are 3 Byzantine workers under FoE attack
Batch size
32x8
64x8
128x8
256
512x8
1024x8
ByzSGDm + KR 10.00%
10.00%
10.00%
10.00%
10.00%
10.00%
ByzSGDnm KR
10.00%
10.00%
10.00%
10.00%
10.00%
10.00%
ByzSGDm GM
78.36%
81.98%
82.69%
82.20%
84.09
78.90%
ByzSGDnm + GM
88.55%
88.75%
90.99%
90.23%
89.12%
88.38%
ByzSGDm + CM
83.97%
84.28 %
84.01%
83.48%
79.16%
78.76%
ByzSGDnm CM
84.12%
84.77%
85.23%
85.74%
84.65%
83.36%
ByzSGDm + CC
83.60%
84.26%
87.45%
88.48 %
86.24%
81.36%
ByzSGDnm CC
88.99%
90.07%
90.69%
90.54%
89.32%
88.20%
Table 11: The final top-1 test accuracy of ByzSGDm and ByzSGDnm with different batch size when there are 3 Byzantine workers under ALIE attack and NNM technique is used
Batch size
32x8
64x8
128x8
256x8
512x8
1024x8
ByzSGDm KR
58.61 %
65.96%
78.37%
85.71 %
85.26%
83.97%
ByzSGDnm KR
80.41 %
83.85%
85.88%
87.15%
87.68%
87.09%
ByzSGDm + GM
72.58%
73.64%
78.02%
85.73
85.37%
85.32%
ByzSGDnm GM
79.50%
83.96%
86.42%
86.91 %
88.09% %
87.23%
ByzSGDm + CM
71.51%
78.15%
82.95%
86.06%
86.95%
85.24%
ByzSGDnm CM
79.81%
84.14%
85.69%
87.65%
87.69%
87.11%
ByzSGDm CC
76.48%
81.18%
84.63%
86.65
85,98%
85.36%
ByzSGDnm + CC
79.91%
83.50%
87.00%
87.4 87.48%
87.59%
87.78% %
29

---

Published as a conference paper at ICLR 2024
More results about wall-clock time. In Section in the main text, have reported the wall-clock time of different methods for 160 epochs, which empirically shows that using large batch size has the bonus of training acceleration. To further support the conclusion, that different methods require to reach 50%, 75% and 85% top-1 test accuracy in Table 12] Table 13 and Table [4] respectively. As the target accuracy than ByzSGDm in most cases. Moreover, setting a relatively large batch size can significantly accelerate the training process.
also present the wall-clock time
from the results, ByzSGDnm requires less time reach
Table 12: The wall-clock time for different methods to reach 50% top-1 test accuracy when there are 3 Byzantine workers under ALIE attack. The missing values mean that the target test accuracy not reached in 160 epochs for the corresponding methods.
Batch size
32x8
64x8
128x8
256x8
512x8
1024
ByzSGDm KR
157.10s
34.04s
33.93s
31.32s
70.77s
ByzSGDnm KR
408.89s
31.46s
26.27s
27.66s
33.35s
44.31s
ByzSGDm + GM
74.21s
42.70s
26.27s
28.90s
38.77s
55.85s
ByzSGDnm GM
61.09s
24.92s
17.43s
24.18s
23.24s
38.24s
ByzSGDm + CM
303.55s
110.69s
28.52s
37.20s
36.52s
73,44s
ByzSGDnm + CM
475.48s
41.17s
22.32s
27.35s
27.16s
45.66s
ByzSGDm CC
102.17s
37.60s
17.89s
29.08s
27.11s
67.76s
ByzSGDnm + CC
63.56s
25.20s
20.75s
10.86s
21.45s
27.22s
Table 13: The wall-clock time for different methods reach 75% top-1 test accuracy when there 3 Byzantine workers under ALIE attack. The missing values mean that the target test accuracy is not reached in 160 epochs for the corresponding methods.
Batch size
32x8
64x8
128x8
256x8
512x8
1024x8
ByzSGDm KR
133.69s
148.70 748
_
ByzSGDnm + KR
328.49s
123.12s
130.45s
134.09s
ByzSGDm + GM
114.38s
59.19s
90.74s
124.03s
ByzSGDnm GM
252.19s
66.13s
54.12s
45.07s
76.49s
ByzSGDm + CM
202.97s
110.25s
204.425
ByzSGDnm CM
322.83s
150.25s
63.85s
109.23s
ByzSGDm CC
727.07s
77.19s
87 87.42s
86.53s
I 150.59s
ByzSGDnm + CC
1465.07s
112.49s
109.18s
56.20s
61.30s
81.28s
Table 14: The wall-clock time for different methods to reach 85% top-1 test accuracy when there are 3 Byzantine workers under ALIE attack. The missing values mean that the target test accuracy is not reached 160 epochs for the corresponding methods.
Batch size
32x
64x8
128x8
256x8
512x8
1024x8 8
ByzSGDm KR
ByzSGDnm KR
279.88s
248.95s
ByzSGDm + GM
269.31s
218.80s
ByzSGDnm + GM
408.89s
201.76s
176,06s
171.29s
ByzSGDm CM
ByzSGDnm + CM
240.10s
257.50s
ByzSGDm CC
292.38s
207.57s
ByzSGDam + CC
426.95s
216.13s
176.83s
188.12 12s
30

---

Published as a conference paper at ICLR 2024
Top-1 test accuracy w.r.. gradient computation number / wall-clock time. We present the top-1 test accuracy w.r.t. gradient computation number and wall-clock time for different methods when there are 3 workers under ALIE attack in Figure 6 and Figure respectively. The empirical results show that using a relatively large batch size (B 512 x 8) can lead to a stabler training process and higher final top-1 test accuracy. Moreover, under each setting of aggregators and batch size in the experiment, ByzSGDnm outperforms ByzSGDm in final top-1 test accuracy.
Ryp Golie with 1517
Pyrschm with 101539
O Ryp Eepli with CR Pil
RprStiii with GM 1
Gradent compusttor FARTORT
Topa amrncyy
Byc5 G. WiT CMI 28
Dyc50Dres with CC Beil8 vd
5 with 1.
Syc550m ARN CC Bel28
Bye5 with 00
Byc500n CC Bedd
100
XIP
Figure 6: Top-1 test accuracy w.r. gradient computation number of ByzSGDam and ByzSGDm with different batch size when there are 3 workers under ALIE attack
120
100
Too- Tanttaatacunnyy
Tyrs with 537
Soud Dirin w Bedlta0
DarStiiime CM (n will
200
300
703
60
60-
50
20.
60
40.
30
Ryyt D.n with CHil 3-432 31
20
SyctGBm WIN CE 88
20
Bysk cem CNI cB
10
4yc500m CC 8-028
Bydd bm wiP CNI 8-30--1
10e
Syc3iGres With CC B-
Walkeizkic
Figure 7: Top-1 test accuracy w.r.t. wall-clock time of ByzSGDnm and ByzSGDm with different batch size when there are workers under ALIE attack
31

---

Published as a conference paper at ICLR 2024
ByeSoom de (ad Byesabur
DycsOORm DE 18:533
SySsonAAl CO 99532-99
Byc50D wit CCI B
EyE5 Dan WiT CNI (wdl
Zyc5dBre EI (Bedknd)
0.
03-
Codeoccampuainn Fumber
Gradken.copp.tdonn namber
Figure 8: Training loss F(w) w.r.t. gradient computation number of ByzSGDnm and ByzSGDm with different batch size when there are 3 workers under ALIE attack
Meanwhile, we also present the training loss w.r.t. gradient computation number in Figure The results further verify the effectiveness of large batch size and ByzSGDnm.
32

---

Published as a conference paper at ICLR 2024
E.2 NON-LLD. CASE
Although we mainly focus on the i.i.d. case in this paper, we also provide some empirical results in non-i.i.d. cases in this section. Specifically, we randomly sample from the training set of CIFAR-10 dataset according to the Dirichlet distribution with hyper-parameter 1.0. The number of training instances for each class on each worker is presented in Table E.1 below.
Table 15: The number of training instances for each class on each worker
Class label
2
4
5
7 8
Total
Worker 0
523
334
62
582
491
2502
721
148
568
319
6250
Worker
492
898
697
159
83
92
787
2415
67
560
6250
Worker
754
465
459
426
2365
167
815
678
6250
Worker 3
0
0
61
1599
749
304
364
671
688
3254
6250
Worker 4
1106
515
1692
652
593
611
553
70
0
458
6250
Worker S
2004
105
105
2608
29
0
0
345
1054
6250
Worker
2146
1561
314
564
395
135
752
6250
Worker 7
62
537
363
100
126
929
2130
401
1193
409
6250
Total
5000
5000
5000
5000
5000
5000
5000
5000
5000
5000
50000
Moreover, we replace the batch normalization layers in the ResNet-20 deep learning model (He et al. 2016) with group normalization layers (Wu & He 2018) suggested in existing works (Hsieh et al. 2020 We empirically compare ByzSGDnm with ByzSGDm and Byz-VR- VR-MARINA (Gorbunov) et al. (023). We try the batch size 32 8, 128 x 8 and 512 x 8 for each method. Among the 8 workers, one worker (worker 0) is under ALIE attack. The other hyper-paramett
settings for ByzSGDm and ByzSGDnm are the same as those in Section of the main text. The other hyper-parameter settings for Byz-VR-MARIN are the same as those in Appendix D.5
Comparison among the methods in the non-i.i.d. case. The top-1 test accuracy w.r.t. gradient com- putation number is illustrated in Figure g We also present the final top-1 test accuracy of ByzSGDm and ByzSGDnm with different batch size in Table [6] As the empirical results show, ByzSGDnm still outperforms ByzSGDm and Byz- VR-MARIAAA under this non-i.i.d setting. Moreover, for ByzSGDam and ByzSGDm, increasing batch size still increase top-1 test accuracy under this non-i.i.d. setting.
Further comparison when NNM technique is used. We also test the empirical performance of the three methods (ByzSGDnm, ByzSGDm and Byz- CERM-RRMMAAAAAA under the non-i.i.d. setting when nearest neighbour mixing (NNM) (Allouah al. 2023) technique is used. The top-1 test accuracy w.r.t. gradient computation number when there is worker under ALIE attack is illustrated in Figure 10 We also present the final top-1 test accuracy of ByzSGDm and ByzSGDmm with different batch size in Table Compared to the case without NNM, the final top-1 accuracy of ByzSGDnm and ByzSGDm significantly increases (from about % to about 80%) when using NNM technique. On the contrary, the final top-1 test accuracy of Byz- -R-MARINA is still around 20% when NNM is used. In addition, for ByzSGDm and ByzSGDnm, the batch size that leads to the best top-1 test accuracy decreases when combined with NNM. A possible reason is that when combined with NNM, the term in equation 4 decreases, leading to the decrease of B* However, since the bias should also be taken into consideration, it requires further work to study the effect of batch size in non-i.idd cases.
Mcanwhile, the results in Table 17 and in Figure 10 show, ByzSGDnm still outperforms ByzSGDm when combined with NNM non-i.i.d, cases. The empirical results show that in non-i.i.d. cases, ByzSGDnm is still promising choice. Since mainly focus the i.i.d. case in this work, will further study the behavior of ByzSGDnm in non-i.id. cases in future work.
33

---

Published as a conference paper at ICLR 2024
Table 16:
The final top-1 test accuracy of ByzSGDm and ByzSGDnm with GM in the non-i.i.d. setting when there is Byzantine worker under ALIE attack.
Batch size
32x8
64x8
128x8
256x8
512x8
1024x8
ByzSGDm
10.16%
23.33%
27.78%
29.63%
32.90%
32.53%
ByzSGDnm
23.87%
26.78%
28.42%
30.04%
35.24%
36.25%
by Myp
5255Drm with GM 8-512
Byz VAA NARINAA GM (B-32 pww.
Eyz VA MARINA GM B8-22 po0.05
25
Byz VR NARINA GM 48-22 po0.05
Tool
Tood
20
Ryps & Dem with GM 18651 8
201
Dm
B-:32-44
with GM BB226
15
Dm with 6M 0m020
15
- Blys Dem with Git Bm32 x8
- Ryss & bm with GM B-32 .B3
108
10
Gradient computaioon number
K10
Gradient computaton number
x10
(a) ByzSGDam v.s. ByzSGDm
(b) ByzSGDnm V.s. ByZ-VR-MARING (p = 0.05)
Ao ony on W Mamm
Mm My ww
Byz56Drm B-512-8)
Byz5
Top-3 lect accuray
CA---UR-AARRAA GN
MARIN with GN (B-32
Dyz GN (B-612
GN
MARINN with GN (s 12
30
100
Gradient computation
x100
Gradient computattcomuuaaooor number
<100
(c) ByzSGDnm v.s. Byz- "R-MARINA (p=00) 0.1)
(d) ByzSGDnm v.s. Byz- VR-MARINA (p= 0.2)
Figure 9: Top-1 test accuracy w.r.t. gradient computation number when there is 1 worker under ALIE attack under the non-i..dd setting
34

---

Published as a conference paper at ICLR 2024
Table 17: The final top-1 test accuracy of ByzSGDm and ByzSGDnm with GM in the non-i.i.d. setting when there is Byzantine worker under ALIE attack and NNM technique is used.
Batch size
16x8
32x8
64x8
128x8
256x
512x8
ByzSGDm
80.46%
80.56 %
78.29%
74.10%
66.71%
58.78%
ByzSGDnm
81.11% %
81.74% %
80.08%
77.98%
74.65%
69.05%
90
90
70
70
Too-1 10020001001
Syr5 Dnn with GM .
50
Syevv MARINA GM :8-26.8, par.0s
Sye MARINA with GM -2 p5
80
Top-1
Sye.VR BM p-0.5
By:5GDim with GN (B-512.8)
Bya5GDm with GM 5-512-8
RyotGDem (B)28.8)
Rps5GD with GM 8-138.88
Bye5GDam
Bym5G0m
Gradient computatio number
X00
Endentcommubbeer rumber
<10
(a) ByzSGDnm v.s. ByzSGDm
(b) ByzSGDnm v.s. Byz- VR-MARRAAAINA (p 0.05)
90
80
70
30
TO0 lestacuues
ByrSC Ore with GM 6817-
Byg NARINA with GN (8-22x8 p-0.1
Byg MARINA with EM B- -B, p-02)
petll
-0- Www.-yy----R-i with p-0.1
Bye
p-01)
p-0.2
40
40
20
10
10
Grudiett computsiin
<10
Grocient computation nurrber
>10"
(c) ByzSGDam v.s. Byz-VR VRZ-RIAAARINA (p = 0.1)
(d) ByzSSDDm v.s. ByZ-VR-MARING (p 0.2)
Figure 10: Top-1 test accuracy w.r.t gradient computation number when there is 1 worker under ALIE attack under the non-i..d. setting and NNM technique is used
35


Reviews:
[{"review_id": "R9udhdQvkq", "reviewer": "Reviewer_jRhg", "summary": "In this paper, the authors show the effect of batch size on the performance of robust algorithm against Byzantine attacks. More specifically, they characterize the optimal batch size $B^\\star$ to choose when the number of gradient computations is fixed. In addition, they present ByzSGDnm, a robust algorithm that uses stochastic gradient descent with normalized momentum. The authors provide a theoretical guarantee of the algorithm on non-convex functions and provide empirical results showing the efficiency of the proposed method.", "questions": "Table 6 shows the execution time of the different algorithms for different batch sizes, for a specific and fixed number of epochs. Can the authors explain why they chose to show the results for a fixed number of epochs and not for a specific accuracy achieved? As far as I know, the speed gain obtained by choosing a larger batch size is naturally explained by the fact that we can benefit from the parallelization of computations (in the system side). However, I would find it interesting to understand whether the methods presented are faster to reach a given accuracy with a larger batch size.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clear and easy to follow.\n- Increasing the batch size and normalizing the gradient significantly improve the empirical performance of the model in the i.i.d case.", "weaknesses": "- The proposed algorithm is only studied in a homogeneous setting (\"i.i.d. case\" in the paper), which is generally not the case in real applications where data between different clients are heterogeneous. Does the author have any ideas or perhaps experimental results on the behavior of the proposed algorithm in the presence of heterogeneous data?", "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": "FcudhLo7VM", "reviewer": "Reviewer_Rysg", "summary": "In this paper, the authors study the optimization problem of Byzantine-robust distributed learning in an i.i.d. case. They propose a new method, called Byzantine-robust stochastic gradient descent with normalized momentum. They prove the convergence guarantee for this algorithm and theoretically analyze the optimal value of batch size.  Also, the dependence of the rate on the batch size is studied experimentally.", "questions": "1. There is no theoretical comparison between ByzSGDnm and ByzSGDm. Are there any theoretical benefits of ByzSGDnm compared to ByzSGDm? \n\n Please see the weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The presentation of results is written well.\n2. Good deep learning experiments.", "weaknesses": "1. In the experimental part of the work, the experiments do not support theoretical analysis. The authors do not compare the performance of the method with optimal batch size value and with another possible choice of it. It would be better if such experiments were in the work. \n2. Also, the experiments with the comparison of convergence rates of the proposed method and previous methods. It would be better to provide some experiments like in this paper https://arxiv.org/pdf/2206.00529.pdf (see Figure 1). \n3. In the work the authors consider a homogeneous setting. Some results in heterogeneous setup can improve the contribution of this work dramatically.", "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": "pWJGdGNLnH", "reviewer": "Reviewer_tTch", "summary": "This work studies Byzantine-robust distributed learning for the i.i.d. non-convex smooth case. The paper proposes two tricks to improve the existing methods, i.e., large batch size and normalized momentum. The authors provide theoretical arguments to show the benefits of large batch size (variance reduction) and prove the convergence of normalized momentum trick. Empirical experiments show that the combination of these two tricks outperforms existing start-of-the-art methods.", "questions": "1. SGDm is not defined before first used. \n2. In proposition 2, equation (5), why the last term has a $\\sigma^2$ term, while in the work (Cutkosky & Mehta, 2020), this term is only in $\\sigma$. Can you briefly explain why? \n3. Can you explain why KR fails all cases? Is that because KR does not satisfy the definition 1? \n4. Why does CM have degraded performance in table 4 after increasing batch size, this batch size should be right based on its performance in ByzSGDnm, can you provide some comments on that? \n5. In the comparison with Byz-VR-MARINA, why do you use $512\\times 8$ batch size for ByzSGDnm, but never uses that for Byz-VR-MARINA?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The proposed normalized momentum shows significant empirical improvement in the small batch size case as shown in table 3 and table 4. \n2. The use of large batch size also significantly boosts the test accuracy under ALIE attack and FoE attack except for KR and CM for the FoE attack cases. \n3. The combination of large batch size and normalized momentum achieves the best empirical performance in nearly every case. \n4. The use of large batch size significantly reduce the wall-clock running time for training fixed number of epochs.", "weaknesses": "1. There exist little theoretical improvements regarding to existing BRDL methods in terms of problem assumptions or convergence rates. In addition, this work only considers i.i.d. cases, which is kind of restrictive if not enough theoretical improvements are obtained.\n2. The variance reduction trick using large batch size is a direct consequence of (Karimireddy et al., 2021)), so it is hard to claim that this is one of the main contributions of the current work. Furthermore, the optimization of B is conducted on the upper bounds of the convergence rates, so it does not necessarily leads to faster convergence if we set optimal B. This probably should be made clear in the paper. \n3. The technical elements in proving the convergence of ByzSGDnm are closely related to references such as (Cutkosky & Mehta, 2020), so I am not clear whether there are substantial contributions therein.", "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 (poster)