Simple Minimax Optimal Byzantine Robust Algorithm for Nonconvex Objectives with Uniform Gradient Heterogeneity
Authors: Tomoya Murata
Kenta Niwa
Takumi Fukami
Iifan Tyou
Venue: ICLR 2024 poster (2024)
Keywords: Byzantine Robustness
Nonconvex Optimization
Federated Learning
Primary area: optimization
TL;DR: We propose a new simple minimax optimal Byzantine robust algorithm for nonconvex federated learning under uniform gradient heterogeneity assumption.

Abstract: In this study, we consider nonconvex federated learning problems with the existence of Byzantine workers. We propose a new simple Byzantine robust algorithm called Momentum Screening. The algorithm is adaptive to the Byzantine fraction, i.e., all its hyperparameters do not depend on the number of Byzantine workers. We show that our method achieves the best optimization error of $O(\delta^2\zeta_\mathrm{max}^2)$ for nonconvex smooth local objectives satisfying $\zeta_\mathrm{max}$-uniform gradient heterogeneity condition under $\delta$-Byzantine fraction, which can be better than the best known error rate of $O(\delta\zeta_\mathrm{mean}^2)$ for local objectives satisfying $\zeta_\mathrm{mean}$-mean heterogeneity condition when $\delta \leq (\zeta_\mathrm{max}/\zeta_\mathrm{mean})^2$. Furthermore, we derive an algorithm independent lower bound for local objectives satisfying $\zeta_\mathrm{max}$-uniform gradient heterogeneity condition and show the minimax optimality of our proposed method on this class. In numerical experiments, we validate the superiority of our method over the existing robust aggregation algorithms and verify our theoretical results.

Published as a conference paper at ICLR 2024
SIMPLE MINIMAX OPTIMAL BYZANTINE ROBUST AL- GORITHM FOR NONCONVEX OBJECTIVES WITH UNI- FORM GRADIENT HETEROGENEITY
Tomoya Murata
Kenta Niwa!
Takumi Fukami
Lifan Tyon
ABSTRACT
In this study, consider nonconvex federated learning problems with the existence of Byzantine workers. We propose new simple Byzantine robust algorithm called Momentum Screening. The algorithm is adaptive the Byzantine fraction, i.e., all its hyperparameters do not depend on the number of Byzantine workers. We show that our method achieves the best optimization error of O ( (axx) for nonconvex smooth local objectives satisfying -mix-rniform gradient heterogeneity condition under 5-Byzantine fraction, which can be better than the best known error rate of O( for local objectives satisfying Smean heterogeneity condition when ô S (Suesa/ (Guesa/Cmax)² Furthermore, we derive an algorithm independent lower bound for local objectives satisfying Smax moixx-uniformm gradient heterogeneity condition and show the minimax optimality our proposed method on this class. In numerical experiments, validate the superiority of method over the existing robust aggregation algorithms and verify our theoretical results.
INTRODUCTION
In distributed machine learning, some workers, called Byzantine workers (Lamport et al., [2019). may behave abnormally, so using the naive average aggregation of the workers' gradients to train a single global model can catastrophically degrade the model's 's accuracy. Examples of abnormal behavior include hardware crashes, message corruption, well as the presence of poisoned data and the transmission of false information based on adversarial intent, and so on.
To tolerate the possibility of arbitrary malicious acts of Byzantine workers and to mitigate the degradation of the model accuracy, many robust aggregation rules have been proposed and analyzed in IID settings. Specifically each worker's dataset randomly sampled from a common population
(Blanchard et al., [2017] Yín et al., 2018)] Alistarh et al. 20088) Guerraoui et al.) 2018; Xie et al.,
2019: Allen-Zhu al. 2021 Karimireddy al. 2021) Blanchard al. (2017) theoretically studied Byzantine robustness for machine learning problems for the first time and analyzed KRUM, which is distance-based robust aggregation. (Yin et al. (2018) analyzed Coordinate Median (CM) and Trimmed Mean (TM) and derived statistically optimal rates with respect to the Byzantine fraction and the sample size, but they still explicitly depend on the problem dimension. Alistarh et al. (2018) developed a more sophisticated aggregation algorithm and derived an optimal error with less dependence on the problem dimension than CM and TM, for convex cases. The algorithm has been further extended to nonconvex cases (Allen-Zhu al., 2021). Karimireddy al. (2021) theoretically showed that the existing historyless aggregations including KRUM, CM, and TM do not converge to the optimum for stochastic cases. In fact, they reported empirical failures of the historyless aggregations against time coupled attacks such as Inner Product Manipulation (IPM) (Xie et al. (020) and A Little Is Enough (ALIE) (Baruch et al.) 2019). To overcome this problem, they proposed new aggregation called Centered Clipping (CClip) combined with momentum stochastic gradient descent (SGD) that exploits the history of the previous gradient information.
mmurata@msi.c co. ip, NTT DATA Mathematical Systems Inc.
connta.niiw@ntee com, NTT Communication Science Laboratories. NTT Corporation Itakumi. fukamiintt. com, NTT Social Information Laboratories, NTT Corporation i i fan. tww.uytt..ttt.... com, NTT Social Information Laboratories, NTT Corporation

---

Published as a conference paper at ICLR 2024
In the progress of federated learning Konečný al. (2015); Shokri & Shmatikov (011)) McMahan
et al.] (2017). much attention has been given to the development of Byzantine robust algorithms, especially for non-IID cases, where the local datasets of the workers are heterogeneous. However, as shown in Li et al. 2003), the standard aggregations such as KRUM, CM, and TM empirically fail in non-Ill) cases due the data heterogeneity. Many researchers have developed new robust
aggregations for non-IID In-IID settings (Li ct al. 2019; Data & Diggavil 2021 Pillutla et al.) [002]]
Karimireddy al. 2022, Allouah et al.) 2023 Liu al. 2023). Pillutla al. (2022) proposed Robust
Federated Averaging (RFA) based on Geometric Median (GM) aggregation for Federated Averaging
(FedAvg), which is standard optimizer in federated learning. In Data & Diggavi (202T), FedAvg is combined with a robust mean estimation algorithm. Karimireddy et al. (2022); y: Allouah et al. (2023);
Liu et al. (023) proposed general robustness amplification technique for heterogeneous data.
Recent research on Byzantine robust algorithms can be categorized into three main directions: (i) asymptotic optimization accuracy improvement in non-Ill) eases, (ii) computational and communica- tion efficiency improvement, and (iii) extensions of problem settings. In direction (i), Karimireddy ct al. (202)) derived an algorithm independent optimization error lower bound and showed that no robust algorithms can reach the optimum in non- IID cases. Thus, it is crucial to investigate the best achievable optimization error of the robust algorithms in non-llD cases. Karimireddy et al. (2022) also gave a unified analysis of momentum SGD with a class of robust aggregators including KRUM, CM, and RFA wrapped by their proposed bucketing, and CClip and showed that these algorithms achieve minimax optimal asymptotic optimization errоr for nonconvex local objectives satisfying the mean gradient heterogeneity condition introduced in Section 2 (Assumption (6). In direction (ii), many studies have proposed efficient robust algorithms by combining with variance reduction, multiple local updates, gradient compression and their combinations (Wu et al.. 2020 Zhu & Ling 2021 Data & Diggavi 2021; Pillutla al.] 2022; Gorbunov et al..) In direction (iii), several extensions of the standard Byzantine robust optimization setting have been studied; learning on decentralized networks
(Guo et al.
2020; EI-Mhamdi et al.) 2021 He et al. 2202), personalized federated learning (Li et al.
2021 Lin et al.
2022: Werner et al. (2223).. combination with differential privacy (He et al. 2020
Guerraoui et al.
2021:
Zhu
Ling 2022). ) and so on.
This study particularly focuses on (i) optimization accuracy improvement for specific class of nonconvex local objectives by developing a new simple robust algorithm in non-IID settings, because of its fundamental importance.
Main Contributions. We propose new Byzantine robust algorithm called Momentum Sereening (MS) for nonconvex federated learning. Its main features follows:
(Algorithmic simplicity) MS uses a simple screening test to detect Byzantine workers and combines it with the standard momentum SGD.
(Adaptivity Byzantine fractions) Theoretically, MS does not need to know the number of Byzantine workers in advance, i.c., all hyperparameters of our algorithm are independent of Byzantine fraction E [0, 0.5), which is highly desirable in practice.
(Minimax optimality for (Smax))))) Thanks to the screening scheme, MS achieves the minimax optimal optimization error of 0 for local objectives class CUH (Smaa)) that can be better than the previously known minimax optimal rate of (8CGeea)) for class
CMH (Smeau
To show the minimax optimality of MS, we derive not only an upper bound of the optimization error of MS, but also an algorithm independent lower bound for Cun((max)) and show that the obtained upper and lower bounds match in order sense. To the best of our knowledge, no lower bounds have been known for CUH (Smax), and MS is the first minimax optimal algorithm for (Sux)) ). The obtained rate has a better dependence on Byzantine fraction ó than previous ones, and thus MS can be more robust against Byzantine attacks for small 8 on CUH (Smax).
Related Work. Here, we discuss the connections between this study and the most relevant previous studies. Our screening idea is inspired by the pioneering work of Alistarh et al. (2018). However, the
RRughly speaking, CUn (Smax) denotes the class of nonconvex smooth local objectives satisfying that the maximum L2 distance of the local gradients from the global gradient is bounded by (max. Similarly, Cxn (Smean) denotes the class of nonconvex smooth local objectives satisfying that the mean 1.2 distance of the local gradients from the global gradient is bounded by (mean- For their formal definitions, see Definition in Section 2
2

---

Published as a conference paper at ICLR 2024
algorithm presented in Alistarr et al. (2018) is more complex than ours because it does not rely the momentum technique and needs to aggregate three variables, and their problem setting is limited to IID cases, which are not standard in federated learning. Although the objective functions considered in Alistarh et al. (2018) are convex, the algorithm and the analysis have been extended to nonconvex cases (Allen-Zhu al. 202T). CClip first proposed in the context of III settings (Karimireddy et al. 2021). After that, Karimireddy et al. (2022) gave unified analysis of momentum SGD with their so-called robust aggregators, which includes KRUM, CM, and RFA wrapped by bucketing and CClip on non-IID settings. CClip clips the difference in each input from some guess of the true mean and efficiently mitigates the Byzantine behavior even for heterogeneous local objectives. Bucketing first makes a random partition of input variables, takes the average on each bucket, and then applies traditional robust aggregations to the averaged results. Karimireddy et al. (202T) showed that these algorithms achieve the minimax optimal rate (( for local objectives satisfying Smean -mean gradient heterogeneity condition (Assumption (). In contrast, this study focuses on another local objectives class satisfying -uniform gradient heterogeneity condition (Assumption 5 and derives the minimax optimal rate O(82 of our method, which implies that our method achieves better optimization accuracy than CClip and bucketing when 5 (Smean/ (maax) )² hold Also, CClip and bucketing are not adaptive to Byzantine fraction ó, which means that the theoretically justified hyperparameters of the algorithms depend on the true 8. In contrast, our method is adaptive 8. Very recently, Alllouhh et al. (2023) proposed a general robustness amplification technique called Nearest Neighbor Mixing (NNM), which first creates new input variables by mixing each input point with its nearest neighbor and then feeds the results into standard robust aggregation algorithms. This increases the aggregation accuracy, and NNM has been shown to achieve optimization error of O(8Chean) which is the same as that of CClip and bucketing, for Smean -mean gradient heterogeneous local objectives. Also, very recently Liu et al. (2023) has proposed another general robustness amplification called GrAdient Splitting (GAS), which first splits the coordinates into p subsets and then applies standard robust aggregations to the input variables on each split coordinate. GAS with splitting size p has been shown to achieve optimization error of ((662 + |9] (S/a) + +))) for Smax--uiite -unifrnn gradient heterogeneous local objectives, which is worse than our obtained rate due to the additional dependence the number of honest workers [g] and stochastic gradient variance o². Also, neither NNM nor GAS is adaptive to Ó.
NOTATION AND PROBLEM SETTINGS
In this section, some notations used in this paper are introduced. Then, our problem settings and theoretical assumptions are given.
Notation. || denotes the Euclidean L2 norm || ||=||| - VI, 2 for vector For matrix X, ||X]] denotes the induced norm by the Euclidean Le norm. For a natural number m, [m] denotes the set {1, 2,....,.,,, m). For finite set A. |A| denotes the number of elements. For any number a, b, V b denotes max(a, b) and a A b denotes min(a, b).
Problem Settings. Let n be the number of workers. We assume that on workers can be Byzantine (5 E [0, 0.5)) and can send arbitrary vectors to the central server in the training. Let G be the set of non-Byzantine workers ([G) (1 8)m). We want to minimize nonconvex objective f(x) := [G] Eveg fi(z), where fi(z) := E.-D, [((xx,) Here, D; denotes the local data distribution of worker i. Since the objective function is nonconvex, we set our goal to find approximate first-order optimal points x. i.e., ffx()] < = given the desired optimization error E > O. It is not assumed that D. - Dj for i # and thus the local data distributions can be heterogeneous. In this case, can no longer generally expect the asymptotic optimization error lim V [xx)) )22 to be zero in the presence of Byzantine workers, due to the bias from the data heterogeneity (Karimireddy et al. 2022). Therefore, we focus on finding that satisfies [x)]] for as small > 0 as possible.
2.1 ASSUMPTIONS
In this subsection, several assumptions used in Section are introduced. Assumption 1. ft is T-smooth for each E G.
Forr the discussions of this condition, see Sections
and
3

---

Published as a conference paper at ICLR 2024
Assumption 2. There exists global minima I. of f-
Assumption 3. Minibatch stochastic gradient 9i at x of fú with Elgd] fi(x)), satisfies the following norm Gaus-Gansiinn property with parameter o² for every x E R and i G: I PSDD,(llg) [z(( 2 2 /220²))(())))))))))))))))))))/ ( for any 2 O.
Assumption 3 is necessary to obtain high probability bounds and is often assumed in the stochastic optimization literature (Jin et al. (202I).
Assumption 4. [V((z, 2) & G holds for every Z E R a.s. with respect to a ~ Dj for each i E G.
Assumption 4 is only used in the application of Azuma-Hoeftding' 's inequality for norm-sub SonnssubGaussian martingales (Jin et al. 2019). Very importantly, G depends only log log order on the iteration complexity of our algorithm to achieve the best optimization error and G never depends on the final
optimization error in our theory (see Theorem in Section 4 Hence, Assumption is not so limited.
Assumption 5. {filveg satisfies the following Smax tiiffoun gradient heterogeneity condition:
max fi(z) ff(()]]] - Siaxes Vx E Rdd.
iEG
Assumption 6. (filieg satisfies the following Smean -eean gradient heterogeneity condition:
< Sheans Vo E Idd
G
some heterogeneity of the non- Son-Byyantine local objectives (fi).es. Assumption 5 is stronger than Assumption 6 because Smax 2 Smean always holds. In general, the relationship between Smean and Emax depends on the structure of the local datasets. For example, consider learning model CIFARIO dataset with 20 workers in scenarios. In the first scenario, workers through 19 have a local dataset randomly sampled from CIFARI 10 in an IID manner, and worker 20 has only a local dataset consisting of random samples with class label O. Then we expect that Smax/ Smax//mean Smean > 1 due to the presence of outlier worker 20. In the second scenario, each worker has local dataset consisting of random samples from two random classes {0. .0.....9 9]. In this case, we expect Smax/ /Smenn to be much smaller than in the first scenario, even though the local datasets are still highly heterogeneous. Thus, the quantity Smax/ Fouxx//mone /mean describes property of the heterogeneity rather than its strength. We empirically observed that for several neural networks, including VGGI1, Smax/ Smean was not so large (roughly 1.0 ~ 3.0) on MNIST and CIFARIO with heterogencous allocation and even on realistic federated learning dataset (see Section E
Note that both 5
Definition 1. CUH(Smaxe is defined as the set of local objectives (filteg that satisfies Assumptions 7 2
and 5 Similarly, CAaH (Smean) is defined as the set of local objectives (fiteg that satisfies
A Assumptions
2 and 6
Observe that CUH(() C. CM) Most previous work has essentially focused on CMH((Smean). In our theory, we focus CLH (Smuxx) improve the asymptotic optimization error obtained so far.
3 APPROACH AND PROPOSED ALGORITTM
In this section, we illustrate our ideas and the proposed algorithm.
Review of Centered Clipping. The algorithm most closely related to this work is Centered Clipping (CClip) Karimireddy et al. (2021; 2022), which is state-of-the-ann art robust aggregation algorithm that empirically works much better than the traditional ones like KRUM, CM, and RFA for Byzantine robust federated learning. The simplest CClip takes independent random vectors {m]) 1a as input and returns v + (1/n) E == min(1, T 7/|lm! e vl] v), where e is an initial guess of the ideal aggregation (1/19)) Eieo m.. and often set to the previous aggregation result m but we repeatedly apply CClip by replacing the initial guess with the current aggregation m' The clipping radius derived theoretically as @(p/Vo), where p == max,,jeg V /Elmm m I? and 8 < 0.1 is the Byzantine fraction. A key observation of CClip's update rule is that even for the theoretically determined T, the individual component m may be clipped and biased toward zero for Byn-Byzantine worker This means that CClip is conservative in sense:
mitigate the effect
4

---

Published as a conference paper at ICLR 2024
Algorithm 1: Momentum Screening(#", 17, a, (Ta)
1: for t- = 1 to T do
2: for E [n]] in parallel do
3: if E G then
4:
Compute minibatch stochastic gradients gf at x'=1
5:
Send m = (1 - a)m; 1-1 + ag! (m = g to the server.
6:
else
7:
Send arbitrary vector E IRd to the server. Worker i is Byzantine. end if
8:
9:
end for
m Screen( (i Te).
11: x' =x =x'-l mym..
end for Return: xt (i (Ti.
13:
Algorithm 2: Screen( 1m.)...7 7)
1: 9 = fi [n]] : Kij E [m]: [|m, myll s T 2 0.5m}.
2: m [9] Eieg m
3: Return: m.
of adversarial variables at the expense of the clipping bias for non-Byzantine workers. For the more details of CClip, see Karimireddy et al. (202 2022).
Our Approach: Momentum Screening. One feature of CClip is to allow clipping bias for non- Byzantine workers. Another possible approach is to use safe detection test remove adversarial variables {m/ (etgggg where all the non-Byzantine workers must pass the detection test, and hope- fully many more Byzantine workers will be detected by the test and their variables screened out (i.e., removed). If this type of detection test is available, the non- Byzz-ninniine variables will not be affected by the aggregation. In this case, the aggregation error only comes from the bias of the adversarial vectors that could not be detected by the test. To realize such a detection test, we consider simple screening approach: an input vector m is screened out (i.e., removed) if the d-dimensional sphere with center mi and radius does not contain at least half of the {m ) A similar idea to screening already appeared Alistarh et al. (2018), but the paper only gave a theoretical analysis in the context of homogencous settings that not standard in federated learning, and importantly the whole algorithm is very complex because their algorithm aggregates three quantities (i) the current gradients; (ii) the accumulated gradients; and (iii) the accumulated inner products between the previous gradients and the updated differences, and screening is applied to both (i) and (ii). In contrast, we simply apply screening to the momentum {m; } only once per round.
Concrete Procedures. The concrete procedures of our proposed algorithm Momentum Screening (MS) are described in Algorithm [ For each iteration each worker computes minibatch stochastic gradient of and updates the momentum m in parallel. Then, the central server receives the updated momentums {m/] and aggregates them using Screen (Algorithm 2 The aggregated momentum is then used to update the global model parameter. In Algorithm we screen "malicious" momentum m; by measuring the distance to the other momentums my: if the sphere with center m, and radius т contains only less than half of the other momentums, m; is judged to be anomalous and decided to be rejected. Then, the output is the average of the momentums that pass this screen test. As shown in Section 4 it is thcoretically nice to set T; to ((Gmax) + Õ((1- ((a))² + )..5 a to avoid removing the output of Byzantinnn workers, where is the momentum parameter. In practice, we use some decay scheduling for {re)T= For our experimental settings of {Te)T= see Section 6 and D.2
Remark 1 (Efficient implementation of Algorithm 2). A naive implementation of Algorithm 2 Bl which is worse than ((nd) of CClip and sometimes forbidden.
requires On)-d) computational cos However, we can efficiently implement Algorithm 2 with only ((dd) expected computational cost. The
This because we need check [|m,- myll |l S for every i.j E [n].
5

---

Published as a conference paper at ICLR 2024
concrete procedure of the efficient implementation of Algorithm 2 is given in Algorithm 3 in Section C
due to space limitations. We can show that the aggregation error Im m with Algorithm is only nearly 1.5 times worse than that with Algorithm 2 where m := (1/1g)) Eieg m means the ideal
aggregation result. For more details, see Proposition 2 in Section Also, we empirically observed
that the performance of Algorithm 7 with Algorithm 3
was similar to that with 2 (the empirical
comparison can be found in Section D.5.
4 CONVERGENCE ANALYSIS
In this section, we provide theoretical analysis of Algorithm Ö and Ô abbreviate extra poly- logarithmic factors depending on d, 1/q, T, log [g], log(L/o"). and log G for simple presentation, where q (0, 1) is the confidence parameter of high probability bound. All the proof's can be found in Section A
Overview of Analysis. Lemma I and Proposition [ give the standard bounds for stochastic gradient methods with momentum. These are very similar to Lemmas 9 and 10 in Karimireddy et al. (2022). but our results give high probability bounds instead of the expectation bounds proved in Karimireddy et al. 2022). This is important for the analysis of our screening algorithm because evaluating the aggregation error || mn) I|? in expectation is difficult since Algorithm 2 relies on the observed
value of diameter [[m - mn, |l without expectation. To derive high probability bounds, we use Azuma- Hoeffding's inequality for norm-subGaussian martingales (Jin et al. 2019). Proposition 2 gives the aggregation error bound 0(8'p plnax) for Algorithm 2 with appropriate T = O(pmax) under the uniform diameter bound max ||m - m Pmaxx which is better than that of Karimireddy et al.
(2022) thanks to the screening scheme, and this part is the most important in our analysis. Proposition gives a high probability bound for the diameter ||mm m2ll, [l. which is required in Proposition 2 and roughly we show that maxi.jeg ||mmf- m²) S O(Gmax) + +0((110))))))))))00000
by essentially using Assumption S This means that the theoretically justified 7, is ((mmax) + @(((1 - a)* + a))²) and thus the setting of Tx is adaptive the Byzantine fraction 5. In Theorem 1 we combine all the results and derive a convergence rate of Algorithm] and show an asymptotic optimization error of (1/T) E [='((='))) 2122 < O )2ax), studies.
) which can be better than that of 0 in the previous
Lemma (Descent Lemma), Suppose that Assumption 7 holds. Let a E (0. 1]. n S 1/L. Then, for )11 + n/ll' 12 1/|mm m lp. Here,
every t > 1 it holds that f fxx²) S f(x--1) (n/2)
= m² ( and m² == (1/191) Eieg m.
Proposition 1. Suppose that Assumptions 7 3 and f hold. Let q (0, a (0, and
n S (a/(1881 + 1/a))((1LL) = (((aL)) Then, it holds that for fixed 1 2 1
2 12-1 < A Σ (1 -1- -
- - + B Σ (1-9) 4) t-T
1-T ||m
|V [V )112 C.
r=2
with probability least 1 - 2q. Here, = = L B := a(1/16 + 4cy(1 a)) and
L2
C. = =0((((1 - a/4) + a/7)0² (2)))2/10 /191)), where 7 == 1/ - a)) and is some universal constant.
Proposition 2 (Aggregation Error Bound). Suppose that Assumption 5 holds. Let E [T] If mmf 12 < Pinax every i, E G. under T 2 Pinaxe Algorithm satiffis |l - m² 1|2 < T8
and for E (0, 1), with probability at least 1- 9 Jagiiiss mlm m'l1 < 4(1+s)
where s 2 8 + 3 3/loog(2/)) (())(22 is a parameter of Algorithm 3
Proposition 3 (Diameter Bound). Let q E 10,) and a E (0, 1/2). Suppose that Assumptions
and hold. Then, it holds that for fixed 2 1, with probability at least
for any i, EG,
((
Il m S 0(52 +
+ +a 02
4
Theorem 1. Suppose that Assumptions /
2 4 and S hold. Let 1 S 1/(8V6L.) a= AAA
1/2) and Ti O(Srrax) + @(((1 -a)" + 2)) be appropriately chosen. Algorithml I |satisfies
1
V 112 50 (I((e))
( -((x.)
-
0 (62x2ax) +0 (((1 nIT + nT.) nn.)
1
62
o²
T
T/T
9
6

---

Published as a conference paper at ICLR 2024
with probability at least 1 - 5q for any q E (0. 1/5). In particular, if we set (1/(8v6L) A (L/(VTL)), for sufficiently large II' we obtain (L/T) E [vf(2' - (
Remark The best achievable optimization error O (mnee) can be better than the state-of-the-art one O(8 of CClip and bucketing (Karimiredyy et al. 2022) when ô S (Smeon/ /oanm)/mmxx))
Remark 3. From Theorem 7 we can conftrm that the hyperparameters a and T are independent of 8. In this sense, our algorithm adaptive Byzantine fraction 6.
LOWER BOUND FOR (Smax)
In this section, we discuss lower bound for CUH (Smaxx) and the optimality of MS (Algorithm D
The basic approach is based on Karimireddy et al. (2022). However, for the construction of algorithm- independent worst-case local objectives contained in Cun(Smax)) we need carefully construet quadratic functions on IR and rely on their smoothed versions, which is not necessary for the analysis of Karimireddy et al. (2022). The following theorem gives lower bound 12 mmax) for CUH(Sman and combining the lower bound with Theorem Iimplies the minimax optimality of Algorithm terms of asymptotic optimization error.
Theorem 2. Let å E [0, 0.5). For any optimization algorithm A, there exists sequence of local E CuH((mux) such that for objective function f(x) == (1/191) Eieg fi(x) with G == [(1 - 8)m} it holds that Ey I (O)(((())
objectives {fs (fs)
2 (()2 Here, π is random
permutation over [mi] and the expectation is taken w.r.t the randomness of π.
Remark 4. In Karimireddy al. 2202). a lower bound (8 is essentially derived for function class Can (Smean)))) ). Theorem? 2 does not contradict this lower bound because Theorem 2 gives the
lower bound for Cun (Smas) rather than CMn (Smean))
NUMERICAL EXPERIMENTS
In this section, we provide the results of our numerical experiments to verify that our algorithm is superior to the previous algorithms.
Data preparation. We used two standard 10-class classification datasets MNIST and CIFARI In our experiments, we set the total number of workers to n = 20 and the number of non- -on-Byzantine workers to 20(1 - 5) for Byzantine fraction 8. To construct 20(1 - 5) heterogeneous local datasets, we adopted the procedures used in Karimireddy et al. (2022). First, the training dataset was randomly divided into 50%. Next, one 50% dataset was equally divided and distributed to each non-Byzantine worker. Finally, the other 50% dataset was sorted by labels and divided sequentially into 20 equal parts" parts"land and distributed to each non-B Byz-Byzantine worker. This means that each non-By non-Byyantine worker had 50% TID samples and 50% highly non-IlD samples. These procedures were done independently for MNIST and CIFAR1O.
Models. Our experiments were conducted using three neural newtorks: (i) one-hidder layer fully connected neural network (FC), (ii) a convolutional neural network with two convolutional layers and two fully connected layers (CNN), and (iii) VGG11 (Simonyan & Zisserman 2014). The details of the network architectures are found in Section D.I Due to space limitations, we only report the results on (i) FC and (iii) VGGI1, and the results on (1i) CNN can be found in Section
Implemented aggregation algorithms. We implemented six aggregation algorithms: simple averaging (Avg). Coordinate Median (CM), KRUM (Blanchard al. 2017). RFA (Pillutla al. 2022). Centered Clipping (CClip) (Karimireddy et al. 2022) and our proposed Momentum Screeming (MS, Algorithm[]] with Algorithm 2b. The details them are found Section We fixed learning rate 1) to 0.01, minibatch size to 32. We set the number of epochs to 20 for FC and CNN, and 100 for VGG11. Also, we decided to apply a momentum technique with a 0.1 for every algorithm because
'The source code our experiment will be publicly available after the paper is published.
http:://yam: I lecun
Itttps:/ /www//wwwwoooo//.oo//////. cs. waasstoronte toronto............... edu-kkiz// aiffar.hmm...
From the construction procedures, we can expect that Çmax/ /Smean will not be so large, because each local dataset treated approximately equally in sense, and there were outlier local datascts.
7

---

Published as a conference paper at ICLR 2024
Motel/Data
AGG
BF
LF
Mimic
IPM
ALIE
Worst
Avg
9..1
95.5
0.3
0.3
94.8
8.33
89.3 1 0.7
CM
9..6
93.3+
94.1
9..4+0.6
8.2
88.2 + 3.2
FC/
KRUM
9..0
9.4
94.5=100
92
96.1 06.1
92.8 0.3
MNIST
RFA
9..7
0.3
9
9..
9..2
90.2 1 0.5
CClip
94.8
0.3
9.3
9.2
9.4
93.2 - 0.4
MS (ours)
95.2+:0.2 0.2
0.34
95.5
95.5
94.5
94.9
94.5 + 0.1
Avg
0.1
0.1
9..4
99.3 0.1
30.3
30,8 15.1
CM
9..2
99.1
99.3 0.1
99.1
67.0
67.0 10.5
VGGHI/ MNIST
KRUM
98.
99.2
99.0=
98.
99.2
98.7
RFA
99.3
9..
99.3=0.1
9.1
7288+34.7
+4.8
CClip
9.1
9.1
99.3=
99.
9.
95.3
MS (ours)
99.3
9.0
99.3
0.3
09.3
99.0
Avg
46.7
4..9
46.1
46.7 11.3
25.2
25.2 3.3
CM
2.26
3..
40.2 1.6
37.6
1.7
27.4
FC/
KRUM
19
1.2
384
1.
2.5
33.7 2.1
CIFARIO
RFA
46.2
0.8
4.0
45.8
29.0
29.0 + 3.7
CClip
1.2
45.7 0.6
3.5
40.9
35.4 15.4+08
35.4 = 0.8
MS (ours)
1.1
46.2
1 1.3
45.8
45.0 = 2.5
44.6 + 2.0
Avg
0.9
85.0
0.4 0.4
85.1
0.8
84.5 0.3
19.2 1.3
19.2 = 1.3
CM
2..6
43.7 4.3
9.2
34.9 3.7
19.1 1.111.1
19.1 1.9
VGGII/ CIFARIO
KRUM
2.5
04.21.
70.3 2.2
40.614488
71.9 1 8.3
40.6
4.8
RFA
0.3
83.9 0.2
0.4
81.
20.3 + 1.3
20.3
= 1.3
CClip
0.7
$1.3
81.3
64.2
22.7 1 2.3
22.7
- 2.3
MS (ours)
84.2 0.4
84.6 0.6
84.8 0.9
83.5 11 0.8
83.3 + 3.4
82.8 1 2.5
Table 1: Comparison of 95% confidence intervals of the best test accuracy (%) against five attacks (6 = 3/20) for each model and dataset ("Worst" shows the confidence interval of the worst best test accuracy among five attacks). Bucketing technique combined with CM, KRUM, and RFA.
it consistently improved the optimization accuracy in our experiments For CM, KRUM, and RFA, we tested the aggregation with the bucketing technique. contrast, the bucketing technique was not applied to CClip and MS The bucketing parameter was set to 2 in accordance with Karimireddy al. (2022). For the clipping parameter CClip, we followed the suggested parameter described in Karimireddy et al. (2022). For MS, we set the screening parameter as (T + (1-1x/4))-- ax/4)=-1100 2 where Too was chosen for each model and dataset, but was fixed for each Byzantine fraction d and each random trial. The details of the settings of Too can be found in Section D.2
Implemented attack algorithms. We implemented standard five different types of attacks: Bit Flipping Attack (BF), Label Flipping Attack (LF), Mimic Attack (mimic) (Karimireddy et al. (022) Inner Product Manipulation (IPM) Attack (Xie et al.) 2020), and A Little Is Enough (ALIE) Attack (Baruch et al. 2019). The details of these algorithms are found in Dection[..3
Evaluation. We compare the test accuracy the implemented aggregation algorithms. The results of other metrics (train loss, train accuracy, and test loss) can be found in Section D.4 We ran five experimental trials independently and report their 95% confidence intervals.
Comparison of the six aggregations for fixed Byzantine fraction. Here, compare the test accuracy of the six aggregations against the five attacks for the case of 3/20. Thoos the best test accuracy comparison of the six aggregations against five attacks. From the "Worst" column, MS outperformed the other methods, including the state-of-the-ard CClip and the standard robust aggregations with bucketing, in terms of the worst best test accuracy against the five attacks for each model and dataset. This strongly suggests the remarkable robustness of MS. Note that the performances of Avg were severely degraded against ALIE, although Avg worked well against the other attacks, probably because of the relatively small size of the Byzantine fraction = 3/20. In the experiments, ALIE seemed to be the strongest attacker, but MS was still robust against
Experiment 1:
Experiment 2: Comparison of MS with CClip for varied Byzantine fractions. To further investigate the superiority our proposed method over the ofate-of-the-art existing algorithm CClip,
*Our decision is supported by the empirical effectivity of momentum reported in Karimireddy al. 2022 9This is because it was reported in Karimireddy et al. (2022) that CClip performed similarly with and without bucketing (probably because CClip without bucketing was already minimax optimal in their settings), and MS with bucketing is not analyzed theoretically, although the analysis will he similar.
8

---

Published as a conference paper at ICLR 2024
10g1olTess Acc Gap)
logiulTest Acc Cap)
log1o(Testi Acc Gap)
lo (TTet Acc Cap)
3mm
o 2
Ars
2
AGG
C13ip
0
M5
0.5
1.0 [1/])
0.5
1.0
log]o(1/5)
log]o(L/6)
log1o[1/6]
(a) FC on MNIST
(b) VGGII on MNIST (c) FC on CIFARIO (d) VGG11 on CIFARIO
Figure Comparison of the worst relative test accuracy to AVG without Byzantine workers of CClip and MS against the Byzantine fractions 5 E {1/20, 2/20, 202 4/20, 5/20, 7/20, 9/20} for five attacks (BF, LF, mimic, IPM, and ALIE) for each model and dataset (lower is better). The z-axis shows 1/8 (i.e., the further to the right on the x-axis, the smaller 8), and both axes are plotted on logarithmic scales.
which is a natural comparator of our method, in particular for relatively small 6, we compare the worst value of the best test accuracy against the five attacks for each Byzantine fraction 5 e (1/20, 2/20, 30,,3/200 3/20, 4/20, 5/20, 7/20, 9/20). Figure | compares the worst value of the best test accuracy relative to the best test accuracy of Avg aggregation without Byzantine workers, i.e., the difference between the ideal best test accuracy and the worst best test accuracy against five attacks, for each Byzantine fraction. We plotted both axes as logarithmic scales. The results show that MS consistently outperformed CClip by large margin, particularly for small 5. This matches theoretical findings because the optimization error of CClip has a factor of 5 but that of MS has a factor of 62. We can also see that our method with the fixed clipping radius scheduling performed well for different å on each model and dataset thanks to its adaptivity to 5 3Remark
In summary, conclude that MS outperformed the existing robust algorithms in our experimental settings and the numerical results support our theoretical findings.
7 LIMITATIONS AND FUTURE WORK
Here, we briefly discuss some limitations and future directions of this study. First, from theoretical point of view, our method has no minimax optimal guarantees for CAHH (Gmeaa), although the minimax optimality for CUH (Smaa))) has been shown. Thus, if (max/ >> 1 (e.g., due to the presence of an outlier worker) or 8 2(1), our method may perform worse than CClip. In general, which of MS and CClip performs better depends on the type of heterogeneity of the local datasets and Byzantine fraction 5. important to construct an algorithm that is minimax optimal for both CUn (Gmax) and CмH (aaaameen)) without naively combining MS with CClip standard aggregations with bucketing. Second, MS requires a communication per model update, which imposes a large communication cost. Therefore, for practical federated learning, our algorithm needs to be extended to allow multiple local updates to reduce the communication cost. In general, multiple local updates may increase the aggregation error because the outputs of honest workers may be very different compared with the case of a single local update when the local datasets are heterogeneous. Thus, it is important to investigate the effect of multiple local updates and the possibility of reducing the communication cost without harming the best optimization error O of the single local update case.
8 CONCLUSION
In this study, we have considered nonconvex federated learning problems with the existence of Byzantine workers. We have proposed a new simple Byzantine robust algorithm called Momentum Screening (MS), which is adaptive to Byzantine fraction 8 < 0.5, and shown that it achieves the best optimization error of O 2 for function class CUH(Smax), which can be better than the best known error rate of O
for function class CxHHSmeaad when Byzantine fraction d satisfies 5 & (Smean/ SSaax ? Furthermore, we have also derived a lower bound for CUH(Smase) (Smax) and shown the minimax optimality of our proposed method for SUH(Smax)) In numerical experiments, MS outperformed the existing robust aggregations and the results verified our theoretical findings. Finally, discussed some limitations of this study and future directions.
9

---

Published as a conference paper at ICLR 2024
REFERENCES
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018.
Zeyuan Allen-Zhu, Faeze Ebrahimianghazani, Jerry Li, and Dan Alistarh. Byzinnine-resilient non- convex stochastic gradient descent. In International Conference on Learning Representations. 2021. URL htttttss//ppeeeeiiieeeee/ wtt.ppppweeeeeeeeeeeeooooraaaaaa htt.:e/eoooruaaaaaP...c.c.o.....
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 International Conference Artificial Intelligence and Statistics, pp. 1232-1332 130-0 PMLR, 2023.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little enough: Circumventing defenses for distributed learning, Advances in Neural Information Processing Systems, 32, 2019.
Peva Blanchard, Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017.
Deepesh Data and Suhas Diggavi. Byzantine-resilion high nigh-dimensional sgd with local iterations on heterogeneous data. In International Conference on Machine Learning, pp. 2478-2488. PMLR. 2021.
El Mahdi El-Mhamdi, Sadegh Farhadkhani, Rachid Guerraoui, Arsany Guirguis, Lê-Nguyên Hoang, and Sébastien Rouault. Collaborative learning in the jungle (decentralized, byzantine, hetero- geneous, asynchronous and nonconvex learning). Advances in Neural Information Processing Systems, 34:25044-25057, 2021.
Eduard Gorbunov, Samuel Horváth, Peter Richtárik, and Gauthier Gidel. Variance reduction is antidote to byzantine workers: Better rates, weaker assumptions and communication compression as cherry on the top.
Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability of distributed learning in byzantium. In International Conference Machine Learning, pp. 3521-3530. PMLR, 2018.
Rachid Guerraoui, Nirupam Gupta, Rafaël Pinot, Séhastien Rouault, and John Stephan. Differential privacy and byzantine resilience in sgd: Do they add up? In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pp. 391-401, 2021.
Shangwei Guo, Tianwei Zhang, Xiaofei Xie. Lei Ma, Tao Xiang, and Yang Liu. Towards byzantine- resilient learning decentralized systems. arXiv preprint 0rXiv:2002.08569, 2020.
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Secure byzantine-robust machine learning. arXiv preprint arXiv:2006.04447, 2020.
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Byzantine-robust decentralized learning via
clippedgossip. arXiv preprint arXiv:2202.00 012.002..5555,,00000
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham Kakade, and Michael Jordan. short note on concen- tration inequalities for random vectors with subgaussian norm. arXiv preprint arXiv: 1902.03736.
2019.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2):1-29, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pp. 5311-53119 PMLR, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogencous datasets via bucketing. International Conference on Learning Representations, 2022. URL https:://ppentt wtt.:/ewwweeeeeeeeeeeeeeeeeeeeee wwt.eeeeeee.oeooomeeenarooaaaaa 5v
10

---

Published as a conference paper at ICLR 2024
Jakub Konečný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint arXiv:1511.03575, 2015.
Leslie Lamport, Robert Shostak, and Marshall Pease The byzantine generals problem. In Concur- rency: the works of leslie lamport, pp. 203-226. 2019.
Liping Li, Wei Xu, Tianyi Chen, Georgios Giannakis, and Qing Ling. Rsa: Byzantinerrobust stochastic aggregation methods for distributed learning from heterogeneous datasets. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544-1551, 1551, 2019.
Shenghui Li, Edith C-H Ngai, and Thiemo Voigt. An experimental study of byzantinc-robust aggregation schemes in federated learning. IEEE Transactions Big Data, 2023.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization. In International Conference on Machine Learning, pp. 6357-6368, PMLR, 2021.
Shiyun Lin, Yuze Han, Xiang Li, and Zhihua Zhang. Personalized federated learning towards communication efficiency, robustness and fairness. Advances in Neural Information Processing Systems, 35:30471-30485, 2022.
Yuchen Liu, Chen Chen, Lingjuan Lyu, Fangzhao Wu, Sai Wu, and Gang Chen. Byzantine-robust learning heterogeneous data via gradient splitting. 2023.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiiennn learning of deep networks from decentralized data. In Artifiiial Intelli- gence and Statistics, pp. 1273-1282, PMLR, 2017.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions Signal Processing, 70:1 142-1154, 2022.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pp. 1310-1321, 2015.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
Mariel Werner, Lie He, Sai Praneeth Karimireddy, Michael Jordan, and Martin Jaggi. Provably personalized and robust federated learning. arXiv preprint arXiv:2306.083933 2023.
Zhaoxian Wu, Qing Ling, Tianyi Chen, and Georgios B Giannakis. Federated variance-reduced
stochastic gradient descent with robustness to byzantine attacks. IEEE Transactions on Signal Processing, 01:453334966 2020.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In International Conference on Machine Learning, pp. 6893-6901. PMLR, 2019.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270. PMLR, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference Machine Learning, pp. 5650-5659, PMLR, 2018
Heng Zhu and Qing Ling. Broadcast: Reducing both stochastic and compression noise to robustify communication-effiieentt federated learning. arXiv preprint arXiv:2104.06683, 2021.
Heng Zhu and Qing Ling. Bridging differential privacy and byzantine via model aggrega- tion. arXiv preprint arXiv:2205.00107, 2022.
11

---

Published as a conference paper at ICLR 2024
A CONVERGENCE ANALYSIS
In this section, convergence analysis of Algorithm is given. Ô and ① abbreviate extra poly- logarithmic factors depending on d, 1/q. T. log [9], ( ( log G, log(1/a), where (0. 1) is the confidence parameter of high probability bound. From the definition can see that log(1 (1a) O(log 7').
and Theorem we
Lemma (Azume Hoeuee-oefddingss inequality for norn-subGaussian (Jin et al. 2019)). Let X1,-.. X be random vectors in Rd. Suppose that (X:)== satisfies the following conditions:
E X = 0 and P [X,I| 2 2) 2e
20 4s E.
for {or)i= Then, for any g E (0, 1), with probability at least q it holds that
2d
X,
C
Σ i=1
0
log
for some universal constant 0.
Lemma 3 (Martingle version of Azume Hoene-Hoeffding's inequality for norm-subGaussian (Jin al. 2019 ). Let X1,...,X, Xx, be random vectors in Rd. Suppose that (X:)== and corresponding filtra-
hons (3:)= satisfy the following conditions:
E[X; 8:-1] = O and P( X(| 2 11-1) 2e 20
ER [n]
for random variables {a.}²= with o; 3:-1(t (i [n]). Then, for any q E (0,1) and a with probability at least 1 q it holds that
2d + loglog A log q
2 A or
Σ
X;
S C
max
of
1=1
i=1
for some universal constant 0.
A.1 PROOF OF LEMMA
Let t 2 1. From L-smoothness of f, we have
f(x') S 5(x (VS(x'-)) - x1-1 + 1|=" x²- 111
2
f(x (z ),m²) + 2 ||
5f(x'-1) V )mm²) + " 111m"11
=s(o'11) IV)(2* ( 1>12 + !
2 2'lm* vf(xxt [| 1]12
< < | |11² + 1 +
Here, the second inequality used n S L/L. This finishes the proof of Lemma Lemma 4, For every 2 1, holds that [| || S 2G almost surely.
Proof. When /. = 1, Assumption 4 immediately implies the desired result because m² = g. Let f 2 2. Observe that ||m/|| = [omn]]==(([]]]]]]))) =1(1-a)m;-+ s (1 -1-=)))m;;-11111 I s (1-a)--1 mm
Σ El=2 a(1 - +
12

---

Published as a conference paper at ICLR 2024
A.2 PROOF OF PROPOSITION |
First observe that || = Ilø' - |1
Let 2 2. Observe that
1ee = ||m - \)(
= [I(1 a)m² - + ag' - Vf(x'-1)1
(1
+ 2a(1 - a))'t - v5(x
+ + \1
< (1-a))le--11 + [+
+ +2a(1 a) g vf(a + - ff(=''))11
5 ((1-a)lee + L 1+ 1 ||m--112
+2a(1 - am 1m gg vf(x 1)) a² 11g vf(x"
< (1- a 3/1²1,2 [+
_ (1+
||e ||: 1,2 | a
1
=
|| |lm--1- 11
(1 (1+3)) _ [| + 20(1 a) a) (m- .g' ((((x-11))
)
+ +,322,
+ a (f(x211)11
Here, for the first inequality, we used Young's inequality. The second inequality holds from L- smoothness of f.
Now, we set 1) to be 3 (,7 + 1/0) S a/16 (5 a/2). In this case, note that ry = O(a/L). Then, we have
|2-1 = |m - vf(x"~1)11 !12
< (1 9 || 1 + +372 3 2
[+ -
mlm :-1 - -m'=1p"
+ L3 L2 (1+ ! | | |~ + 2a(1 - am) -V((x(-1)
+a'll'' "イ(0"~1)1
(1 4) ||--1112 - タ
-| + 21 (1+ || - 11
+ 3,2 21 |5
+ 20 - a)(m- " - vs(x()1))
+ a =2ll''' vf(x"~1111
13

---

Published as a conference paper at ICLR 2024
Recursively using this inequality, we obtain
|e 1= = |lm fx(x ||
< (1 a 1-1
4
| 1|
a Σ
[1 (1- d)
| |/
1=2
+ L3
1+ a
Σ
(1 (1- -)
|| 1m--1-m 1
T=2
+ 312
(1+2) Σ
(1
+) V5 211
(I)
T=2
+ +2a(1 a) Σ
(1
a)
(m~-11 .g' ()(x-11))
r=2
4) b-
a² وو v ||
2=2 4
To further bound the right hand of ① we apply concentration inequalities.
Bounding the first and the last term of the rh..s. of I Since g is independent norm sub-Gaub Gaussann with parameter o² for every i E G, applying Lemma 2
gives
c²o² log 2d
l
ff(=-11)12 v
|9]
with probability at least 1 q. Using union bound for 1 E [T]. we obtain
o²a² log 2
V1 E [7] 11g'
[ 5
9
with probability at least q.
Bounding the 5th term of the rh.s. of 1 Let X3 (1 (1-3) 4) (m--1, of Vf((a--)) and
X, = (1/[g) Eveg X3. We apply Lemma of Lemma 3 At first, is easy to see that E E F,-] = 0 because Blg [Fr-]] = (a
3 ( TE To so, we check the assumptions
Also, from the norm sub- nub-Gaussian properties of g we have
P(X 2 s(F+-1) S
-V((1
|||
2
(1 a/4) F | [r-1
s²
< exp
20 - a 2) +) 1 1122
Thus, the assumptions of Lemma are satisfied with a +- a(1 a/ 4)
||m= ||- Apply Lemma with
Observe that | Σt= of < 16|9]=²G* /ax almost surely from Lemma
A o /a and yields
2d + loglog A (log"
X S
Σ oz +
q
g
log 2d + loglog 1) +
1
o² Σ
a/2)2(t-)) 11-m1|1111) 112
V
q
T=2
<
2a2
log
2d
+ loglog
1
)
+ cy
(1 (1-a/4) | 11 +((V))
7 [
q
< 2
log 2d
A
+ loglog
2207
Σ
(1 a/4) - |/ + +ō (V}).
7 g
q
2=2
14

---

Published as a conference paper at ICLR 2024
Here, for the third inequality, used vab I (2² a/7 + for any 0. We choose 7 such that 4a(1 a)ey S a/4 cancel out the second term of the r.h.s. of Σ X by the second term of the r.h.s. of ①T.
Combining these bounds, we obtain
||E`|/ 00
Σ
1
a
1m-
r=2
Σ (1 )
+ +0y(111 (all-a)) (
-) |Vf
ta
16
(((1-2) 1-
a 0²
+
+0 (VE).
+
Finally, taking E + (o2//>)(o22///)))) and substituting y 1/(11// 1 a)) finishes the proof of Proposition T
A.3 PROOF OF PROPOSITION 2
In the following proof, we fix E [T] and omit index as long it does not cause confusion for simple presentation.
First we show that G C 9 for Algorithm To do so, we fix any i E G and show that i g. First note C i E [n] [|m, - m, I T} since T 2 Pmax Then, since 8 < 0.5, we know that [9] n/2. Thus, K E [n] [|, m,I S r) n/2. Hence, from
that g C [j E [n]] [|m, - m, S Pmax
the definition of Ç. S.
Next, we show that G C 9 for Algorithm 3 Note that Algorithm aaways terminates in a finite number of iterations because T 2 Puax assumed. Let E & be fixed. Let p = PP E B). Observe that random variable X₁ == es independently follows Bernuuli distribution with parameter p for
k K. Then, from Hoeffding's inequality, we have E (X2 p)1 - (KK2) log(2/8) with probability least 1 - q. Observe that
|m - -mrofll s
(m- myter
+
(m² my
ki EJNG
kistar
9 Prmax +
| (TBB) (Prax +7)
K
1 + 2
n
K
- Here, for the second incqualities, we used the fact that for jks E B3 [1,||mmmm,,p m [|m, mj.. |l S Pmax T, where j' E G is worker index such that [|my m || S and its existence can be guaranteed from the procedures of Algorithm Then, from the high probability bound, we have |J n < (1 - p)K + Using these results and p < 8, we obtain
||m; - my +
and [J n B < pk (KK22) log(2/8)
log (2g(2/6)
m, m < 1+8+ 118+33 8/
T S (1+
2K
with probability at least - 8 when
log(2/8)
2 8 8
2K
Hence, for both Algorithms
2 and have i & and thus g c g.
15

---

Published as a conference paper at ICLR 2024
Now, analyze the aggregation error. Let B be the set of all the Byzantine workers.
I/m-
ml
m;
19
ieg
lEg
|
m4
(1
m
m2
[9
9
iEg
9 a B
1
19
|91
9
iEÚ
(m=
m)
kEGNB
2
Σ
[m mell
Here, for the third and fourth equality, we used the fact that 9 \g & B and thus | - [9]
I 9 = 1 B).
Thus, for Algorithm 2 have
2
|l ml
Σ
(l]m; mj.ll 1l +lmm, mill)
9
iEgnB
Here, in the first inequality, ja is some index satisfying j. E 9 and 1mm-mm,) || S т. Note that for each i G, such j, always exists because | [n] |m myll < TH > 0.5n and [|] < 0.5n. The last
inequality holds from ||m, m, S and m, ml| = (1/1g)) Exeg ||m, m& $ Pmax S
and و BI/1G| 1 |
//// < 6.
Similarly, for Algorithm 3 we have
2
[m ml|2 <
(1)m; myell + [| - mll)
| EEâNB
< 4 (1 + 5) 82,2
with probability at least 1-9. 9.
Here, in the last inequality, used ||m; meaell S (1 s)7 for & (note that c 9), and
I n /)/lỘ|
| < 1 | <
This completes all the proofs of Proposition
A.4
PROOF OF PROPOSITION 3
Observe that
|| m1I1 = [1 - () [- m agg) 0/
(1 a) 1m m 112 2xx a) -m
- 19. , - -5) + + - 0311
||2 + aa(1 a)
< ((1-a) a)² + a(( 11) 11
+ 2a² Craxx
7'
+ 40 V/( (1,
+ 2a(1 am -1 vf((=-11) 1)+ +  -
m
16

---

Published as a conference paper at ICLR 2024
Here, we set/ / := 1/2. Then, the coefficient of the first term is bounded by 1 a/2. We decompose
this as (1 - a/4) - a/4 and then recursively use the inequality:
||m] - mm}1 $ ((1 a)² + 7 - amm m1 + (2a(1- - a) + -222) Smax
+ +aa(1 - a) - mm- . V[((=''') + 18 v5z(x('1))
+ 4a² (11g) v[(( + |lo] - (x)(
$ (1 - a/ -1) 1
-
|mm 1mm
a
my 11 + (2a(1 - a) + 2a²) Suaxx + 42202
+ +a - a) - - m .6
-m)
vf((='-1) + oo - (fz(x(-1))
+ +119 (x+ + 110} (0 1)133)
5(1 - a/4)" l|m! - m3]1
a Σ
(1 4)/ - - -m, -112- + 122
r=2
+ +2a(1 - a) Σ (1 a/4) '- {m3 -1
m -- 99 vf((a-11) 4 vfz(a--11)
2=2
+ 4a² 2
Σ 2
- a1-) (11s)- - V/((E- + 110] - [((()+)))13)
(2)
To bound the first term, last term, and the fourth term, again apply Lemma 2 and Lemma Similar to the arguments of the proof of Lemma we have
2Td
VI E [T] 11
v < 00 log
with probability at least - Also, defining X = (1 - ()) -) {m? 1- - m 1 .9. V)((I-11).. with A 4 64o²G2 /a and 4- we have
X
co2
log
2d
+ loglos + ey Σ (1 aa4)a44)
mm T-1 - mj --1 112 +O(E)
2
where 7" > 0 is arbitrary. Similar arguments for X == (1 (1-
- m -- 9j (z gives the same bound as Er= X We choose 7" (1) such that 4a z a/4 4 to cancel out the second terms of the r.h.s. of , X and Σ X by the second term the r.h.s. of (2). Note that such 7" can be ((1) since assume a s 1/2. Finally, we take union bounds for i, J E G and set e t- a2ot. Then, we obtain the desired result.
A.5 PROOF OF THEOREM 1
First, observe that 77 S V (4/44((11//a)//44 O(a/L) from the definitions of n and a. Combining Proposition
with Proposition 3 results in
|lm - mm112 < 00022²2 Smax) + Ō(((1 -
and thus
T
Imm m < ( Smax +6 + (2 0202)
Σ
with probability at least - 3g.
From Lemmal I we have
T
T Σ
+ (/ (=+ af') 8²22
0 <
2
17

---

Published as a conference paper at ICLR 2024
Then, from Proposition
|
with probability at least
2q we have
T
T.2
1
0
|m-
m
11-
a²
|
T
+
+
1607 1
1 a)
V
4
1=1
((=
1 aT
σ²
Let = 1/(18c( - a)). Note that 7 (1) since a S 1/2. Then, since
3 1607(1 -a) S 8'
we obtain
T Σ
((a4))((* ((att)
+0 (0(((1))
[12L2 (112L)
|
00
+
82
Smax
T
1/T
a²
(((1)
o²
+ō
+1
82
+ a
0² +
+
t
a2
aT
aT
n
with probability at least 1 - 5q. Substituting the definition of a gives the desired results.
B LOWER BOUND FOR CUH((mmas
Lemma 5. Let Fo > 0 and h: R IR be L-smooth, and G-Lipschitz on | S xo- we define hn as
h(()) (((o)) zo) + 1(22)) ((-30) + ma) + h((r))
(|x| S xn)
h(x)
(x > ro)
(xr -
h is L-smooth and G-Lipschitz on R.
Proof. It is obvious that h is G-Lipchitzness because h is linear on |x] (2o)),, |t (-zzol < G.
zo and
We show L-smoothness of h. To show this, pick any v, R and show that [1( 7v(v)) L|2 y/.
H E e mo) or e mo} z, {a E [r] < }
L-smoothness is trivial because of the L-smoothness of h and linearity of on |x 2 20. Without loss of generality, we assume < y. Then, we only need to consider the following three cases:
|z| < Zg and y > zo: In this case, we have [h((x) - F((z)) = [1'(z) h1(ro)) 5
L|z zol s L r yl-
x vg and |y| < xn: In this case, we have (w(xx) N((w)) (W((=0) [((w)l <
Lyy + mul. Observe that ly + vul + jx + val = y + - (xr + 2o) = = 1 and
thus ly + zol < I yl.
x 20 and y > No: In this case, have (i((x) R'(w)) (W())) 12 (x(-xo) 5
2L < L - y/-
This finishes the proof of Lemma 5
18

---

Published as a conference paper at ICLR 2024
B.1 PROOF OF THEOREM 2
Let = and G 2 2mmax. We define the following two local objectives (f1) and (f2)
f1 = (x) Ei (l,...,,,,))),
(2) (otherwise)
and
hx(x)) (iE (1-...,(1-)))]))) (x)) (a(()) (otherwise)
Here, ha is defined as the smoothed function of (x) == 1/2 Smax by Lemma with 20 = G/(2L). Similarly, h2 is defined as the smoothed function of ho(z) x²² by Lemma with To == (2L). Note that ha and hy is smooth on I and G-Lipschitz on |o| S 20.
Then, the objective functions become
(1- 1-8)m
2
x²
1-3 Smaxx:
8
(|rl S ao)
(x) (1 - 118)
(x)
(Lay I- Smax) (x vo) + 4
I-8 Smax
(x > No)
-LL0 I-8 Smaxx)
(x + xo) + L 2/
+ 1- Imaxaa
(x: -Fo)
and
(1-8)n
4x2
(|r) S ro)
(x) (1 8)m
Σ
ff(x)
Log(x - 20) + 1 Looo( x + x00) + =
(x > xo)
(æ > To)
Moreover, we assume that stochastic gradient 9: 1 matches ftth itself, i.e., the deterministic oracle considered for each k = 1,22
Now, we check {Jt [ee Cun((mmx).
(Assumption 1 L-smoothness is immediately satisfied from Lemma 5 since ha and by are L-smooth.
(Assumption Observe that f attains minimum - maxx/ (2I(1 8)2) at
8mmax L) S zo. and f² attains minimum 0 at x = 0.
(Assumption 3 Since 9, matches f for each k 1,2, arbitrary o² 0 satisfies the
sub-Gaussian property.
(Assumption We check G-Lipschitzness of ha and h& on |a|| < mn- [x(()) Lax Smaxl < L| Smax I G/2 + G/2 = G for |x| I zo from the definition Zip == G/(2L)
and G 2 2Cmax. Similarly, we can see that [k((2)) L|x| s G/2 < G. Hence, Lemma 5
gives the G-Lipschitzness of h2 and has
(Assumption 5) First we show that (ee satisfies Smax gradient heterogeneity ( (x) = (1- (1-26)
(max & Smax for any x E IR. Also, for E (8n+1...., 1,...,,. (1-8))) - (x) = 8/(1 8) Smax < Smax for any E R. Thus, [ Neg is mhaax-unnfomm gradient heterogeneous. Cmax -niform gradient heterogeneity of (f heg is immediately obtained because f? f for every
condition. For 2 E [[,....,5r)
v/
E = (l...., (1 8)m}. i.e., (z) (f2(x) s Smax-
Hence, we have shown that Uf (fe e CCH(Smax).
Now, we show that
1
82 max 4(1 5)
E.
2
k=1
If 3 is shown, we immediately have
max ES (A(US))))))))
2 Σ ES v (A(1SH())E
kE(1,2)
k=1
82
>
22 (2
4(1 6)
19

---

Published as a conference paper at ICLR 2024
Proof of (3)
Let be A( )im1) for each & E {1.2}. Then, observe that
V Ex /max/ (1 - 6)12116!1 S mo| P( S mo)
+ E 1I [1: To 12 (-x)) 6maxx / (1 5)12118! > zo)P((221 > md)
B. | S x0] 1-
2L6
Smax [+ |جا xo) P(LE! S zo)
+
[1/00ll -1-8 Smaxtto)
2Ld
P(|S21 rn) + (1 5)2 Smax
8²
1. 1T
[ S x0ol2
2LD
Smax F.z [+ S mo)
P(li'l s m0)
1
2L8 + L'| 1 - 8 SmaxToo
82
P((E!) > mu) + (1 8)2 Smax.
For the last inequality, we used Jensen's inequality.
Also, we observe that
Fx V - [1 S mn) P(I+2) S mo) + 1,2 |cr P([12) > mD)
= 2 [ S - S zо) + L |ro 1 P( > zo).
S, denotes the set of all the permutation on [m]. Now, let T1-22
Sn the permutation
1 +1 (a-J)++1
ôn ôn -
n
n 1
(1 (1-6)n)
Then, we can see that (2))) =
for any random permutation т E Sn. Since 1o and x follow the same distribution, we have E, [q()) E, [g [xق for any function q. Then, by setting Tt == E, [=:11=11 I zol = E. [+2 1123 holds that
< æo) and == P( - zo) = P( - zo), it
E, (
[2'22 - 2L5
1 8 Smaxe p+ [19100 2
1 SmaxTo
2L8
(1 - ppp +
(1 8)2 Smax
8²
and
B. { T.2 p+ 1,2 1000021111 - -p).
Combining these results, we obtain
Ld
L8
8²
2
1.222
1-
Smaxtt
p+
1.22g
8 Smax
(1 (1-
2(1 8)2 Smax
L8
8²
min ZER
L2
Smax
+
2(1 8)2 Smax
1
Finally, since x2
L8 1-8 & attains the minimum
55 -
52/mmxx/ / (4(1 8)2) at a = DGmmax/(2T.
6)), we obtain
3) This finishes the proof of Theorem
20

---

Published as a conference paper at ICLR 2024
C EFFICIENT IMPLEMENTATION OF SCREEN
Here, we provide an efficient implementation of Screen introduced in Section 3 The concrete procedures are given by Algorithm Observe that the expected running time is ((d) rather than O(n²d) when K O(1). Theoretically, K Ō(1) is sufficient guarantee the best optimization
emoor of O 2 ) our experiments Section D.5 we used $ = 1.5 and K 10.
Algorithm 3: Efficient Implementation of Screen( (m, J 8, K)
1: # Server conservatively estimates the set of non non- non-Byzantine workers.
2: # The expected runtime is only ((n)) when K is (1).
3: Set J = 6.
4: for
K do 5: Jfet = Search Reference Worker (m,
6: Append sfet to J.
7: end for
8: Set Myel
K ER=1 ""
9: 9 Eie [n] I||m= mrefll 7)
[o] Lieg my
11: Return:
Algorithm 4: Search Reference Worker( 1= 7)
1: # Serch worker j such that H [m] ||m; myl <T||> n/2.
2: # The expected runtime is only O(nd).
3: repeat
4: Randomly pick from [n]].
5: until Ki [n] ||m, myll S ST) S n/2
6: Return: j.
21

---

Published as a conference paper at ICLR 2024
D SUPPLEMENTARY OF NUMERICAL EXPERIMENTS
D.1 DETAILS OF THE MODEL ARCHITECTURES
The architectures of FC and CNN were as follows:
FC: Linear (output size: 100) - Softplus -> Linear (output size: 10)
CNN: Conv2d (# filters: 32, kernel size: 3) + ReL.U - Conv2d (# filters: 64, kernel size: 3) MaxPool2d (kernel size: Linear (output size: 128) ReLU Linear (output
size: 10)
VGG11: We used the official pytorch implementation of VGG11
We used the default initialization implemented in pytorch.
D.2 DETAILS OF THE IMPLEMENTED ROBUST ALGORITTMS
Here, we provide the details of the implemented robust aggregations and their hyperparameter settings.
Avg: The aggregation rule is defined as Avg((m)) = (1/n) m,
(M((m)]_)) = (Med((m.))))../)) of the input.
where Med returns the one dimensional median
KRUM (Blanchard et al. 2017): The aggregation rule is defined as KRUM((m:)) =
mE minsc (1 (1-6mmx)) Ejes ||m -myll? where 8maxs which is an upper bound 5, was set to 1/4
RFA (Pillutla al., 2022): : The aggregation rule is defined REA (m)))))
Smoothed Weiszfeld( m, 1;-1: Iv),, where the Smoothed Weiszfeld algorithm returns an approximate solution the geometric median argmin Di=1 [lm m4]]. [I. T and are the hyperparameters of Smoothed Weiszfeld and were set to and 0.1 respectively.
CClip Karimireddy et al. (002)): The aggregation rule is defined as (Clip([m)]".) (T/n) Ei=1 min 11 7/ 7/|mm (m, v), where v is initialized the previous
aggregation result and this process is recursively executed for iterations, where 7 was set 10. These hyperparameters were taken from the public source code of the authors of Karimireddy et al. (2022).
MS (proposed): The aggregation rule is provided Algorithm I We adopted Algorithm rather than Algorithm B for simple implementations. Screening radius 100 where Tao was set to 20 for FC and VGG11 on MNIST, 30 for CNN on MNIST, 75 for FC and CNN on CIFAR10, and 100 for VGG11 I on CIFAR1O.
set to
(To + (1
For each iteration, was increased by 1.5 times from the original 7 as long as 9 < n/2 in order stabilize the performance.
D.3 DETAILS OF THE IMPLEMENTED ATTACK ALGGORITHMS
Here, give the details of the five implemented attacks. In the following, of denotes a stochastic gradient of worker used at iteration
Bit Flipping (BF) attack: Byzantine worker sends -9 instead of g
Label Flipping (LF) attack: Label of the local datasets of Byzantine workers is flipped by for every y E (0,...,9).
Mimic attack (Karimireddy et al. 2022): Each Byzantine worker picks honest worker i. e G and copies its output 9f, as g.
mode
vggi
1.hmm
Note that this conservative choice of &max is justified when KRUM is combined with hucketing (see Section
C.2 of (Karimireddy et al. 2022
22

---

Published as a conference paper at ICLR 2024
Motel/Data
AGG
BF
LF
Mimic
IPM
ALIE
Worst
Avg
0.2
98.6
0.2
98.7 U.1
0.1
57.61 66.0
66.6
CM
98.0+0.4
97.8+ 0.3
98.1
9..6
73.4
76.4 73.0
CNN/
KRUM
97.6
0.1
9.3
9..4
98.5
0.2
97.4 0.3
MNIST
RFA
9..6
9..
98.6 1 0.1
9..
83.7
41.7
CClip
98.6
98.6+
98.8 0.2
0.3
49.6 86.3
49.6 86.3
MS (ours)
98.7 #.2
98.7 #
-
9.14
9.24
98.4 0.1
Avg
6.97
69.6
69.1
68.6
16.0 12.4
16.0 12.4
CM
1.0
52.1
55.0 1.7
16.83333
19.9-1113
19.9 11.3
CNN/ CIFARIO
KRUM RFA
0.9
5.0
52.7 4.4
4..9
53.4
42.9 =
1.0
6.5
67.9 1.6
0.8
18.6
18.6 11.4
CClip
2.3
6..0
65.5 1.6
51.7
18.0
18.0
MS (ours)
17.7
L.
67.6
1.7
67.6
65.6 + 1.7
Table 2: Comparison of 95% confidence intervals of the best test accuracy (%) against five attacks 3/20) for CNN on each dataset ("Worst" shows the worst test accuracy among five attacks).
Inner Product Manipulation (IPM) attack (Xie et al. 2020): Byzantine workers send (E//G)) Eieg gi where was set 1.0 in our experiment.
A Little Is Enough (ALIE) attack (Baruch al. 2019): Byzantine workers compute the mean Hgg and the standard deviation og of {g.hee and send Pg 20g, where 2 was set to 2.0 in our experiment.
D.4 ADDITIONAL NUMERICAL RESULTS
Here, we provide additional numerical results not shown in the main paper due to space limitations.
D.4.1 ADDITIONAL NUMERICAL RESULTS OF EXPERIMENT 1
First, we provide the best accuracy comparison results on CNN (Table From these results, we confirm that MS still outperformed the other methods for CNN.
Next, we report the learning curve four metrics; train loss (Figures 2 (ndd5)) train accuracy (Figures 4 Mand55) 55. test loss (Figures and 7 and accuracy (Figures 8 and [9) complement the results of
Experiment in the main paper. The experimental settings were the same as in the main paper except that we added CM, KRUM, and RFA without bucketing.
D.4.2 ADDITIONAL NUMERICAL RESULTS EXPERIMENT 2
Here, we show the results of four metries under the same setting in the main paper: train loss, train acc, test loss, and test acc (Figures and to to complement the results of Experiment
D.5 COMPARISON OF ALGORITHM| 2 AND ALGORITHM 3
Here, we compare the performances of Algorithm | with Algorithm to that with Algorithm
The general settings of MS were the same described in Section D.2 except for the settings of T we used 15 for FC, CNN and VGG11 on MNIST, 50 for FC and CNN on CIFARIO 10, and 70 for VGG11 CIFAR1O. In Algorithm
3 we set 1.5 and K = 10. In the until loop, T increased by 1.1 times from the original 7; the termination condition is not satisfied for five randomly picked j. After computing Myef by applying Algorithm for times, we reset тę to the original value. Then, 7, was increased by 1.1 times from the original 7, as long as | < n/2 order to stabilize the performance.
We ran _S_ (Algorithm) I with Algorithm 3) in the settings of Experiment 1. The performance comparison is shown in Figures 12 and 13 From these results, the similar test accuracy to MS.
that MS _FF still achieved
23

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Train Loss
1.0
Train Loss
1.0
Train Loss
1.0
0.5
0.5
0.5
0.0
0.0
0.0
LF
LF
LF
Train Loss
1.0
Train Loss
1.0
Train Loss
1.0
0.5
0.5
0.5
0.0
0.0
0.0
AGG
AVG
mimic
mimic
mimic
Train Loss
1.0
Train Loss
1.0
Train Loss
1.0
KRUM
CM
0.5
0.5
0.5
CClip
RFA
0.0
0.0
0.0
MS
IPM
IPM
IPM
S
Train Loss
1.0
Train Loss
1.0
Train Loss
1.0
0
0.5
0.5
0.5
2
0.0
0.0
0.0
ALIE
ALIE
ALIE
Train Loss
1.0
Train Loss
1.0
Train Loss
1.0
0.5
0.5
0.5
0.0
0.0
0.0
0
1000
1000
0
5000
Iterations
Iterations
Iterations
(a) FC on MNIST
(b) CNN on MNIST
(c) VGG11 1 on MNIST
Figure Comparison of the train loss of the implemented algorithms against the number of iterations for five attacks for three models on MNIST: BF, LE, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when
24

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Train Loss
2
Train Loss
Train Loss
2
2
LF
LF
mimic
Train Loss
Train Loss
Train Loss
2
2
mimic
mimic
LF
AGG
Train Loss
Train Loss
Train Loss
AVG
2
2
KRUM
CM
CClip
RFA
IPM
IPM
IPM
MS
Train Loss
Train Loss
Train Loss
2
2
ALIE
ALIE
ALIE
Train Loss
Train Loss
Train Loss
2
2
2
1000
0
1000
5000
Iterations
Iterations
Iterations
(a) FC CIFARIO
(b) CNN CIFAR10
(c) VGG11 CIFAR10
Figure 3: Comparison of the train loss of the implemented algorithms against the number of iterations for five attacks for three models on CIFAR10: BF, LF. mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when = 0.
25

---

Published as a conference paper at ICLR 2024
BF
BF
BF
100
100
100
Train Acc.
Train Acc.
Train Acc.
90
90
90
LF
LF
LF
Train Acc.
100
Train Acc.
100
Train Acc.
100
90
90
90
AGG
mimic
mimic
mimic
AVG
Train Acc.
100
Train Acc.
100
Train Acc.
100
KRUM
CM
90
90
90
CClip
RFA
MS
IPM
IPM
IPM
Train Acc.
100
Train Acc.
100
Train Acc.
100
2
90
90
90
ALIE
ALIE
ALIE
Train Acc.
100
Train Acc.
100
Train Acc.
100
90
90
90
0
1000
1000
0
5000
Iterations
Iterations
Iterations
(a) FC MNIST
(b) CNN on MNIST
(c) VGG11 1 on MNIST
Figure 4: Comparison of the train accuracy of the implemented algorithms against the number of iterations for five attacks for three models on MNIST: BF, LF, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when s = 0.
26

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Train Acc:
Train Acc.
Train Acc.
75
75
75
50
50
50
25
25
25
LF
LF
mimic
Train Acc.
75
Train Acc.
75
Train Acc.
75
50
50
50
25
25
25
AGG
mimic
mimic
LF
AVG
Train Acc.
Train Acc.
Train Acc.
KRUM
75
75
75
CM
50
50
50
CClip
25
25
25
RFA
MS
IPM
IPM
IPM
Train Acc.
Train Acc:
Train Acc.
75
75
75
2
50
50
25
25
25
ALIE
ALIE
ALIE
Train Acc.
Train Acc.
Train Acc.
75
50
50
50
25
25
25
1000
0
1000
0
5000
Iterations
Iterations
Iterations
(a) FC CIFAR10
(b) CNN on CIFAR10
(c) VGG11 on CIFAR10
Figure 5: Comparison of the train accuracy of the implemented algorithms against the number of iterations for five attacks for three models on CIFAR10: BF, LF, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when = 0.
27

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Test Loss
1.0
Test Loss
1.0
Test Loss
1.0
0.5
0.5
0.5
0.0
0.0
0.0
LF
LF
LF
Test Loss
1.0
Test Loss
1.0
Test Loss
1.0
0.5
0.5
0.5
0.0
0.0
0.0
AGG
AVG
mimic
mimic
mimic
Test Loss
1.0
Test Loss
1.0
Test Loss
1.0
KRUM
CM
0.5
0.5
0.5
CClip
RFA
0.0
0.0
0.0
MS
IPM
IPM
IPM
S
Test Loss
1.0
Test Loss
1.0
Test Loss
1.0
0
0.5
0.5
0.5
2
0.0
0.0
0.0
ALIE
ALIE
ALIE
Test Loss
1.0
Test T Loss
1.0
Test Loss
1.0
0.5
0.5
0.5
0.0
0.0
0.0
0
1000
1000
0
5000
Iterations
Iterations
Iterations
(a) FC on MNIST
(b) CNN on MNIST
(c) VGG11 on MNIST
Figure 6: Comparison of the test loss of the implemented algorithms against the number of iterations for five attacks for three models on MNIST: BF, LE, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when
28

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Test Loss
Test Loss
2
Test Loss
2
0
LF
LF
mimic
Test Loss
Test Loss
Test Test Loss
2
2
2
0
mimic
mimic
LF
AGG
Test Loss
2
Test Loss
2
Test Loss
2
AVG
KRUM
CM
CClip
0
RFA
IPM
IPM
IPM
MS
Test Loss
2
2
Test Loss
2
Test
2
ALIE
ALIE
ALIE
Test Loss
Test Loss
2
Test Test Loss
2
1000
0
1000
0
5000
Iterations
Iterations
Iterations
(a) FC on CIFAR10
(b) CNN on CIFARIO
(c) VGG11 1 on CIFAR10
Figure 7: Comparison the test loss of the implemented algorithms against the number iterations for five attacks for three models CIFAR10: BF, LF, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when s =
29

---

Published as a conference paper at ICLR 2024
BF
BF
BF
100
100
100
Test Test Acc.
Acc. Acc.
Acc.
90
90
90
LF
LF
LF
100
100
100
Test Acc.
Test Acc.
Test Acc.
90
90
90
AGG
mimic
mimic
mimic
AVG
Test Acc.
100
Test Acc.
100
Test Acc. Acc.
100
KRUM
CM
90
Test
90
90
CClip
RFA
MS
IPM
IPM
IPM
100
100
100
Test Acc.
Acc.
Test Acc.
90
90
90
ALIE
ALIE
ALIE
100
100
100
Test Acc.
Acc.
Acc.
90
90
90
0
1000
1000
0
5000
Iterations
Iterations
Iterations
(a) FC MNIST
(b) CNN on MNIST
(c) VGG11 on MNIST
Figure 8: Comparison of the test accuracy of the implemented algorithms against the number of iterations for five attacks for three models on MNIST: BF, LF, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when s = 0.
30

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Test Acc.
75
Test Acc.
75
Test Acc.
75
50
50
50
25
25
25
LF
LF
mimic
Test Acc.
75
Test Acc.
75
Test Acc.
75
50
50
50
25
25
AGG
mimic
mimic
LF
AVG
Test Acc.
75
Test Acc.
75
Test TestAco Acc.
75
KRUM
CM
50
50
50
CClip
25
25
25
RFA
MS
IPM
IPM
IPM
Test Acc.
75
Acc, Acc.
75
Acc.
75
50
50
50
25
25
25
ALIE
ALIE
ALIE
Test Acc.
75
Acc, Acc:
Aest.Acc
50
Test
50
50
25
25
25
1000
0
1000
0
5000
Iterations
Iterations
Iterations
(a) FC CIFAR10
(b) CNN on CIFAR10
(c) VGG11 on CIFAR10
Figure 9: Comparison of the test accuracy of the implemented algorithms against the number of iterations for five attacks for three models on CIFAR10: BF, LF, mimic, IPM, and ALIE. denotes the bucketing size, and bucketing was not applied when = 0.
31

---

Published as a conference paper at ICLR 2024
Iogio Loss Gap)
logia(Train Loss Gap)
1ogio(Train Loss Gap)
2.5
2.5
2,5
AGG
0.0
0.0
0.0
CCIip
-2.5
-2.5
-2.5
MS
0.5
1.0
0.5
1.0
0.5
1.0
l091)(1/5)
(0//)
l0g2a(1/6)
(a) FC on MNIST
(b) CNN on MNIST
(c) VGGII on MNIST
ITrinn Acc Gap)
loganlTrain Acc Gap)
logio(Traln Acc Gap)
2
Rmy
2
2
AGG
0
0
CClip
MS
0.5
1.0
0.5
1.0
0.5
1.0
(0g1o(1/6)
10g1o(1/6)
1og1o(1/6)
(e) FC on MNIST
(f) CNN on MNIST
(g) VGGII on MNIST
logan(Test Test Loss Gap)
logra(Test Loss Gap)
logio(Test Loss Gap)
2.5
2.5
2.5
AGG
0.0
0.0
0.0
CClip
-2.5
-2.5
-2.5
MS
0.5
1.0
0.5
1.0
0.5
1.0
log1o(1/5)
log1o(1/8)
logıa(1/5)
(i) FC on MNIST
(i) CNN on MNIST
(k) VGG11 on MNIST
log (Tstt Acc Gap)
lognalTest (Test Acc Gap)
logıo(Test Aoc Gap)
Rmy
2
2
AGG
0
0
0
CClip
MS
0.5
1.0
0.5
1.0
0.5
1.0
(1/1)(1/5)
l0g1o(1/6)
l0g1o(1/6)
(m) FC on MNIST
(n) CNN on MNIST
(o) VGGI I on MNIST
Comparison of the worst relative metrics to AVG without Byzantine workers (lower is better) of CClip and MS against the Byzantine fractions 8 E (1/20, 2/20, 3/20, 4/20, 5/20, 9/20} for five attacks for three models on MNIST: BF, LF, mimic, IPM, and ALIE. (a)-(c) correspond to relative train loss, (e)-(g) to relative train accuracy, (i)-() to relative test loss, and (m)-(o) relative test accuracy. The a-axis shows 1/5 (i.e., the further to the right on the x-axis, the smaller 8), and both axes are plotted on logarithmic scales.
Figure 10:
32

---

Published as a conference paper at ICLR 2024
logio(Train Loss Gap)
Iorio Loss Gap)
logio(Train Loss Gap)
2.5
2.5
2.5
AGG
0.0
0.0
X-x
0.0
CCIlp
-2.5
-2.5
-2.5
MS
0.5
1.0
0.5
1.0
0.5
log1o(1/6)
log1a(1/6)
log:a(1/6)
(a) FC CIFARIO
(b) CNN CIFARIO
(c) VGG11 CIFARI0
log1o(Train Acc Gap)
lognolTrain Acc Gap)
logio(Trainn Acc Gap)
Re Miw.ggggee
2
AGG
CClip
you
0
0
MS
0.5
1.0
0.5
1.0
0.5
1.0
(1/))
(
log1o(1/6)
(c) FC on CIFAR10
(f) CNN on CIFARIO
(g) VGGI1 on CIFARIO
log1olTest Loss Gap)
lTgt Loss Gap)
logi Loss Gap)
2.5
2.5
2.5
AGG
0.0
0.0
0.0
CClip
-2.5
-2.5
MS
0.5
0.5
1.0
0.5
1.0
log1o(1/6)
log1o(1/6)
log1o(1/6)
(i) FC on CIFARIO
(i) CNN on CIFAR10
(k) VGGI1 on CIFARI0
logno(Test Test Acc Gap)
log (Test Acc Gap)
(Tet Acc Gap)
2
2
Ke
2
AGG
Am
CClip
Xi
0
0
MS
0.5
1.0
0.5
1.0
0.5
1.0
log1o(1/6)
(1//)(1/5)
l0g/)(1/6)
(m) FC on CIFARI0
(n) CNN CIFARIO
(o) VGGI1 on CIFARI0
Comparison of the worst relative metrics to AVG without Byzantine workers (lower is better) of CClip and MS against the Byzantine fractions 8 (1/20, 2/20, 3/20 4/20, 5/20, 9/20} for five attacks for three models on CIFAR10: BF, LF, mímic, IPM, and ALIE. (c)-(c) corresponds to relative train loss, (e)-(g) to relative train accuracy, (i)-(k) to relative test loss, and (m)-(o) to relative test accuracy. The zr-xxs shows 1/8 (i.e., the further the right on the x-axis, the smaller 8), and both axes are plotted on logarithmic scales.
Figure 11:
33

---

Published as a conference paper at ICLR 2024
BF
BF
BF
100
100
100
Test Acc.
Test Acc.
Test
Test Acc.
90
90
90
LF
LF
LF
100
100
100
Test Acc.
Acc.
Test Acc.
Test Acc.
90
90
90
mimic
mimic
mimic
100
100
100
Test Acc.
Acc. Aco.
Test Acc.
90
90
AGG
IPM
IPM
IPM
100
100
100
MS
Test Acc.
Test Acc.
Test Acc.
MS_EFF
90
90
90
ALIE
ALIE
ALIE
100
100
100
Test Acc.
Test Acc.
Test Acc.
90
90
90
1000
0
1000
5000
Iterations
Iterations
Iterations
(a) FC MNIST
(b) CNN MNIST
(c) VGGI1 MNIST
Figure 12: Comparison of the test accuracy of MS EFF (Algorithm I with Algorithm to MS (Algorithm 7 with Algorithm [ against the number of iterations for five attacks for three models on MNIST: BE, LF, mimic, IPM, and ALIE.
34

---

Published as a conference paper at ICLR 2024
BF
BF
BF
Test Acc:
75
Test Acc.
75
Test Acc.
75
50
50
50
25
25
25
LF
LF
LF
Test Acc.
75
Test Acc.
75
Test Test Acc.
75
50
50
50
25
25
25
mimic
mimic
mimic
Test Acc.
75
Test Acc.
75
Test T Acc.
75
50
50
25
25
25
IPM
IPM
IPM
AGG
MS
Test Acc.
75
Test Test Acc.
Test Acc.
MS_EFF
50
50
50
25
25
25
ALIE
ALIE
ALIE
Test Aoc.
75
Test Acc. Acc.
Acc.
Test Acc.
75
50
50
25
25
1000
0
1000
0
5000
Iterations
Iterations
Iterations
(a) FC CIFARIO (b) CNN CIFARIO
(c) VGG11 CIFARIO
Figure 13: Comparison of the test accuracy of MS EFF (Algorithm I with Algorithm B) to MS (Algorithm) with Algorithm 2 against the number of iterations for five attacks for three models on CIFAR10: BF, LF, mimic, IPM, and ALIE.
35

---

Published as a conference paper at ICLR 2024
0.9
FC
0.9
FC
0.7
CNN
CNN
0.6
0.8
0.7
0.8
0.077
CNN
VG311
06
2000
6200
2000
5000
2500
7500
10000
12500
Banations
(a) MNIST
(b) CIFARIO
(c) Fed-EMNIST
Empirical values of Smean/ / along the trajectories of momentum SGD without Byzantine workers for each model and dataset. MNIST and CIFARTO, we ran epochs (1, 200 iterations) for FC and CNN, and 100 epochs (6, 000 iterations) for VGGII. On Fed-EMNIST, 200 epochs (12, 000 iterations) for every model. Momentum parameter a 0.1, and learning rate ? 0.01 were commonly used. Minibatch size b was fixed as 32 except for VGG11 -MN-S.. For VGG11 on Fed- Fed-EMNIST, we used a smaller batch size b 8
Figure 14:
E EMPIRICAL VALIDATIONS OF S (Smean/ Smax) )2
Here, we give empirical validations of the condition 5 < (Smean (Smean/Smax)) which is implicitly assumed in the main paper for the theoretical superiority of MS over the other existing methods, including CClip.
Observations Smean/ Smax the Scenarios Section 6 We report the observed values of Chean//Sman of local objectives (fi)iej on MNIST and CIFARIO in the settings of Section 6 Gusing momentum SGD without Byzantine workers. We observed that {mean/ /Smx were not too small (about 0.50 0.93) and 8 S (Smean/ ) was satisfied for 5 < 1/4. These results support the empirical superiority of our method over the other methods described in Section 6
Observations of Smean/ Smax in a Real Federated Learning Dataset We further investigate the behavior of Smean/ / of local objectives (EiNEP on Fed-EMNIST which is real federated learning dataset. Due to memory constraints, we sampled 50 clients Tor training. We found that Smesa/ / Smax ranged in 0.34 0.70 even with these settings, and these results suggest that the condition 8 < (Smean/ / ) would not be so restrictive even in practical federated learning.
In summary, the condition å S Smax) is not restrictive from an empirical point of view.
"https: thu..hhu..aaa. com/ walkkklaakkakaaeeee
WWhen minibatch size b 32 was used, we observed that SGD tended to approach bad stationary point for VGG1 on Fed-EMNIST, which made the convergence quite slow. To avoid this phenomenon, used smaller batch size = 8.
36

---

Published as a conference paper at ICLR 2024
Model/Data
AGG
Mimic
ALIB
Worst
Avg
66.5 0.8
66.0 = 0.8
66.0 0.6
0.7
38.7
38.7
5.0
CM
4.2
02.4
00.4
59.1
38.4+128
37.3 + 10.8
FC/
KRUM
16.2
5.0
1.3
1..7
17.2
15.7 2.4
Fed-MNIST
RFA
59.4 4.0
65.7 1.1
1.7
6.8
5.21
52.1 7.2
CClip
41.7 11.76.9
27.4
3.2
21.8
21.0 -..0+311
MS (ours)
65.4
62.148888
1.5
61.6
0.9
61.6 1.5
Avg
0.3
0.70
79.8 1.4
1.2
33.3 29.8
33.3 29.8
CM
78.2
1..
78.5
1.6
6..7
0..7
CNN Fed-EMNIST
KRUM
66.6
67.6
68.0
6.62
7.3
66.4
RFA
79.2+
79.8
7..6
65.5 22.5
65.5 + 22.5
CClip
79.3
79.6 0.8
1.07
31.3
79.9
71.3 30.0
MS (ours)
78.8
1.1
7.0
74.5
78.9
Avg
80.6 1.8
8..
S..
2.1
15.5
CM
80.4
80.6 2.0
80.7
8.9
2..2
28.2
VGG11/ Fed-MNIST
KRUM
$8.42.44
71.5
1:2
1.5
76.4 1.1
68.4
RFA
80.7 + 1.7
82.0 1.9
81.8 1.4
81.9
42.2 1 7.9
42.2 7.9
CClip
81.7 + 1.1
82.5 = 1.5
81.5 1.0
80.6 1.6
64.9 + 3.5
64.9 3.5
MS (ours)
79.4 1 2.9
81.7
AL.7111 1.8
80.8
2.2
78.3 3
1.7
80.7 + 1.7
78.2 1.4
Table Comparison of 95% confidence intervals of the best test accuracy (%) against five attacks (ō 5/50) for FC, CNN, and VGG11 on Fed-EMNIST ("Worstt" shows the worst test accuracy among five attacks).
F ACCURACY COMPARISON ON FED-EMNIST
In this section, we provide empirical comparison of our method with the existing methods on Fed-EMNIST, which is a 62-class classification dataset for realistic federated learning scenario.
F.1 EXPERIMENTAL SETTINGS
Due to the memory constraints, we sampled 50 clients for training, and 10 clients for testing. We ran 200 epochs (12, 000 iterations) for every model. Momentum parameter a 0.1, and learning rate 0.01 were commonly used. Minibatch size was fixed as 32 for FC and CNN, and was fixed as for VGGII. For MS, we used Tso 75 for FC and CNN, and Too 50 for VGG11. The number of Byzantine workers was set to 5, i.e., 8 = 5/50 = 0.1. The other experimental settings were the same as Section i
F.2 EXPERIMENTAL RESULTS
Table showws the best accuracy comparison results Fed-EMNIST. From Table 3] that MS consistently outperformed the other methods in terms of the worst best test accurary against the five attacks.
shows
37


Reviews:
[{"review_id": "AaPWvT7b7P", "reviewer": "Reviewer_p51w", "summary": "The paper studies nonconvex federated learning (FL) in the presence of byzantine workers with a fraction of  $\\delta$ out of the workers. Then the authors proposed the Momentum Screening (MS) algorithm for such setting, achieving $O(\\delta^2 \\zeta^2_{max})$ error rate for $\\zeta_{max}$-uniform gradient heterogeneity, and showed the minimax optimality of the proposed method in such setting. Experimental results are then given to validate the MS algorithm.", "questions": "Please see weaknesses.", "limitations": "", "rating": 3, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The algorithmic structure of the MS algorithm is simple and can adapt to the Byzantine fractions $\\delta$, all of which can be practically attractive. Furthermore, the minimax optimality results seem like the first of its kind for such setting of $\\zeta_{max}$-uniform gradient heterogeneity.", "weaknesses": "1. The consideration of algorithmic design for uniform gradient heterogeneity as in this paper has been done in the literature. In fact, the rate achieved here seems to be the same as the CCLIP method (Karimireddy et al. (2022)) (ref [1] as below for convenience). Yet, such literature was not well discussed enough in the paper. \n2. Following up the above point, many results in the paper are quite the same as those in CCLIP without improvement, and the analysis is quite natural and motivated from previous work. The true technical novelty of the paper, besides the MS method with simplicity, is perhaps the fact that they proved lower bound in the minimax sense for uniform gradient heterogeneity. However, this is quite a natural extension from the first work that proved such results for the case of mean gradient heterogeneity.\n3. Systematic typo throughout the paper: note that yours is better than CCLIP when $\\delta \\leq ( \\zeta_{mean}/ \\zeta_{max})^2$. Can you give a sense of what $\\zeta_{mean}/ \\zeta_{max}$ can be in real datasets, especially those considered in your experiments? Because I think such fraction can be very small in practice, which is also acknowledged in your Section 2.1. So the regime in which MS provides benefits is in fact quite limited. \n\n\n\n\n\n[1] https://arxiv.org/pdf/2006.09365.pdf", "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": "dtunMNYo8y", "reviewer": "Reviewer_BeSt", "summary": "This paper considers the problem of federated learning with Byzantine workers who can send arbitrary responses to the central server. In the non-IID case where the local distributions of non-Byzantine workers are heterogeneous, the standard aggregations will fail empirically, as shown in previous works. In this paper, the authors developed a new, simple byzantine robust algorithm that have better minimax optimal optimization error compared to the best previous algorithm when the maximum gradient heterogeneity is not much larger than the average gradient heterogeneity, whose optimality in this parameter regime is demonstrated by establishing a lower bound result. Moreover, the authors conducted numerical experiments to support their theoretical analysis.", "questions": "Will the convergence rate of the algorithm remain unchanged if the momentum is removed? Or, is there a better momentum-based algorithm that has better convergence rate?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The algorithm is novel and simple, makes it relatively easy to be implemented in practice. Moreover, the improvement in the minimax optimal optimization error is significant in the parameter regime where the maximum gradient heterogeneity is around the same order as the average gradient heterogeneity, which seems like a common assumption in various practical situations. The performance of the algorithm is also well demonstrated in the various numerical experiments.", "weaknesses": "The convergence rate in terms of the number of steps $T$ might not be optimal. In particular, the algorithm is a momentum-based method, however, the convergence rate exhibits the form of a non-momentum based method, and it is unclear to me why the momentum is needed here.", "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": "vUR6ZHDfKM", "reviewer": "Reviewer_uTUe", "summary": "This paper proposes a new Byzantine robust algorithm called Momentum Screening (MS) for nonconvex federated learning. MS uses a simple screening test to detect and remove potentially malicious gradients from Byzantine workers. The remaining gradients are aggregated using standard momentum SGD. The algorithm is adaptive to the Byzantine fraction $δ$.\n\nThis paper gives theoretical analysis on the proposed algorithm, showing that MS achieves an optimization error of O($δ^2 ζ^2_{max}$) for the class $C_{UH}(\\zeta_{max})$. A matching minimax lower bound is also provided for $C_{UH}(\\zeta_{max})$. This rate differs from the rate $O(\\delta \\zeta_{mean}^2)$ for the class $C_{MH}(\\zeta_{mean})$.\n\nExperiments on MNIST and CIFAR10 with neural nets demonstrate MS outperforms existing methods like Centered Clipping, especially for small $δ$. This aligns with the better dependence on $δ$.", "questions": "1. Could the authors comment more on the relation between $\\zeta_{max}$ and $\\zeta_{mean}$, particularly with some real datasets?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The proposed algorithm (MS) is simple to implement yet performs well. It also does not need to know the Byzantine fraction $\\delta$ in advance, which is practical.\n1. The rate of convergence of MS is better than the previous best known rate of $O(δζ^2_{mean})$ under the (corrected) condition when $\\delta \\leq (\\zeta_{mean}/\\zeta_{max}/)^2$, so the method is preferred if Byzantine workers are very few.\n1. The author also provide a computationally efficient algorithm for their proposed MS method, whose performance is only worse than the original one by a constant factor.\n1. Some experiments on MNIST and CIFAR10 with neural nets shows that MS outperforms other method.", "weaknesses": "1. In the literature the rate $O(δζ^2_{mean})$ is derived from $C_{MH}(\\zeta_{mean})$, while this paper gives the rate O($δ^2 ζ^2_{max}$) for $C_{UH}(\\zeta_{max})$. Now, to give a better rate, one needs\n$$δ^2 ζ^2_{max} \\leq δζ^2_{mean}  \\Leftrightarrow \\delta \\leq (ζ_{mean} / ζ_{max})^2, $$\nwhere the RHS is $\\leq 1$ since $ ζ_{max} \\geq ζ_{mean}$. \nTherefore, **the requirement of $\\delta$ is wrong throughout the paper** (the authors give $\\delta \\leq ( ζ_{max}/ ζ_{mean})^2$).\nThe authors even did not notice this mistake when they write $\\delta = \\Omega(1)$ (in Section 7) but in fact Byzantine fraction  $\\delta < 0.5$.\nSuch mistake makes me doubt the correctness of the proof in this paper, but I do not have enough time to check the whole proof.\n\n1. As argued in this paper, $ ζ_{max} \\gg ζ_{mean} $, meaning that the method is only favourable when $\\delta$ is very small, which seems to be not practical in the Byzantine workers setting. Moreover, since $C_{UH}(\\zeta_{max})$ and $C_{MH}(\\zeta_{mean})$ are different hypothesis classes, directly comparing rates seems to be improper. An analysis of MS in $C_{MH}(\\zeta_{mean})$ is also needed.\n\n1. Although the hyperparameter $\\tau_t$ is adaptive to the Byzantine fraction $\\delta$, it has to be be chosen according to $\\zeta_{max}$, which is unknown in priori, so an inproper choice of $\\tau$ could harm the performance of the algorithm. \nIt would be favourable to provide an empirical way to choose $\\tau_t$.\n\n1. For the presentation of the paper, it would be clearer if the author provides a sketch of the proof rather than presenting directly some propositions.", "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)