Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerant Asynchronous ML
Authors: Tehila Dahan
Kfir Yehuda Levy
Venue: NeurIPS 2024 poster (2024)
Keywords: stochastic convex optimization
byzantine robust learning
online convex optimization
Primary area: optimization
TL;DR: A novel fault-tolerant framework and strategies that, for the first time, achieve optimal convergence rate in asynchronous machine learning against Byzantine failures.

Abstract: We address the challenges of Byzantine-robust training in asynchronous distributed machine learning systems, aiming to enhance efficiency amid massive parallelization and heterogeneous compute resources. Asynchronous systems, marked by independently operating workers and intermittent updates, uniquely struggle with maintaining integrity against Byzantine failures, which encompass malicious or erroneous actions that disrupt learning. The inherent delays in such settings not only introduce additional bias to the system but also obscure the disruptions caused by Byzantine faults. To tackle these issues, we adapt the Byzantine framework to asynchronous dynamics by introducing a novel weighted robust aggregation framework. This allows for the extension of robust aggregators and a recent meta-aggregator to their weighted versions, mitigating the effects of delayed updates. By further incorporating a recent variance-reduction technique, we achieve an optimal convergence rate for the first time in an asynchronous Byzantine environment. Our methodology is rigorously validated through empirical and theoretical analysis, demonstrating its effectiveness in enhancing fault tolerance and optimizing performance in asynchronous ML systems.

Weight for Robustness: A Comprehensive Approach towards Optimal Fault-Tolerae Asynchronous ML
Tehila Dahan
Kfir Y. Levy
Department of Electrical Engineering
Department of Electrical Engineering Technion
Technion
Haifa, Israel
Haifa, Israel
t. www.aaanccmmuss.eer tec.epion.ttecmiio...
kfirylery@teecmionn.cc.
Abstract
We address the challenges of Byzantine-robust training in asynchronous distributed machine learning systems, aiming to enhance efficiency amid massive paralleliza- tion and heterogeneous computing resources. Asynchronous systems, marked by independently operating workers and intermittent updates, uniquely struggle with maintaining integrity against Byzantine failures, which encompass malicious erroncous actions that disrupt learning. The inherent delays in such settings not only introduce additional bias the system but also obscure the disruptions caused by Byzantine faults. To tackle these issues, we adapt the Byzantine framework to asynchronous dynamics by introducing novel weighted robust aggregation framework. This allows for the extension of robust aggregators and recent meta- aggregator to their weighted versions, mitigating the effects of delayed updates. By further incorporating recent variance-reduction technique, achieve optimal convergence rate for the first time in an asynchronous Byzantine environment. Our methodology is rigorously validated through empirical and theoretical anal- ysis, demonstrating its effectiveness in enhancing fault tolerance and optimizing performance in asynchronous ML systems.
Introduction
In recent years, there has been significant growth in the development of large-scale machine learning (ML) models and the volume of data they require [Zhao et al., 2023]. To efficiently accelerate large- scale training processes, Distributed MI. has emerged as crucial approach that be categorized into synchronous and asynchronous paradigms. In synchronous learning, workers update the model simultaneously using the average of their outputs, similar to the Minibatch approach [Dekel et al., 2012]. Asynchronous learning, however, allows workers to operate independently, sending updates as they are ready without waiting for others [Arjevani al., 2020]. This prevents slow workers from hindering the process, making it especially practical as the number of workers increases.
A major challenge of distributed ML is fault- tolerncce, and Byzantine ML [Alistarh al., 2018, Lamport et al., 2019, Guerraoui et al., 2023] is a powerful framework for tackling this aspect. Byzantine ML captures broad spectrum of failures within distributed environments, including random malfunctions or even malicious workers aiming to disrupt the training process. This makes Byzantine MI. widely applicable across various domains ensure robust performance.
Addressing the Byzantine problem in synchronous distributed learning well-established [Karim- ireddy et al., 2020, 2021, Allouah et al., 2023, Farhadkhani et al., 2022, Alistarh et al., 2018, Dahan and Levy, 2024]. Two primary ingredients were found be crucial towards tackling Byzantine ML in synchronous settings: (i) Robust Aggregators [Yin et al., 2018, Blanchard et al., 2017, Chen et al., 2017]: such aggregators combine the gradient estimates sent by the workers to a single estimate
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

while filtering out the outliers which may hinder the training process, While the use of robust aggregators crucial, it was found be insufficient, and an additional ingredient of (ii) learning from history was shown to be vital in mitigating Byzantine faults [Karimireddy et al., 2021]. And, the performance of robust aggregators was systematically explored within a powerful generic framework [Karimireddy et al., 2020, 2021, Allouah et al., 2023, Farhadkhani et al., 2022, Dahan and Levy, 2024]. Moreover, due to the diversity of Byzantine scenarios [Xie et al., 2020a, Allen-Zhu et al., 2020, Baruch et al., 2019], it was found that relying variety of robust aggregators essential. Unfortunately, many existing aggregators have sub-optimal performance. This drawback was elegantly resolved by the design of meta-aggreggtoos [Karimireddy et al., 2020, Allouah et al., 2023, Dahan and Levy, 2024], that enable to boost the performance of baseline aggregators. Unfortunately, in the asynchronous case, the use of robust aggregators is not straightforward, as updates are typically applied individually per-worker, rather than averaging outputs from all workers at once [Arjevani et al., 2020].
single aggregator is insufficient, making the
Despite its advantages, asynchronous distributed learning presents unique challenges, particularly when dealing with Byzantine faults. The delays inherent in asynchronous settings introduce additional bias to the system and obscure the disruptions caused by Byzantine faults. In fact, in contrast to the synchronous Byzantine setting, all existing approaches towards the asynchronous Byzantine case do not ensure generalization error (excess loss) that diminishes with the number of honest data-samples and updates. This applies to works for both convex [Fang et al., 2022] well as non-convex scenarios [Xie et al., 2020b, Yang and Li, 2023]; as well as to works that further assume the availability of trusted dataset possessed by the central-server [Xie et al.. 2020b, Fang et al., 2022]. Furthermore, the performance guarantees of all existing approaches towards that setting include an explicit dependence the dimension of the problem drawback that does not exist for SOTA synchronous Byzantine approaches.
Contributions. We explore the asynchronous Byzantine setting under the fundamental framework of Stochastic Convex Optimization (SCO) [Hazan et al., 2016]. Our work is the first to achieve convergence rate that diminishes with the number of honest data samples and updates and does not explicitly depend on the problem's 's dimension. In the absence of Byzantine workers, our rate matches the optimal performance of Byzantine-free free asynchronous settings. This stands in contrast to previous efforts on Byzantine, which did not attain diminishing rates or dimensionality independence. even without Byzantine workers. We also show the effectiveness of our approaches in practice. Our contributions:
We quantify the difficulty in asynchronous scenarios by considering the number of Byzantine updates, which is more natural than the standard measure of number of Byzantine workers.
We identify the need to utilize weighted aggregators rather than standard ones in favor of asyn- chronous Byzantine problems. Towards doing so, we extend the robust aggregation framework to allow and include weights and develop appropriate (weighted) rules and a meta-aggregator.
Achieving Optimal Convergence: We incorporate our weighted robust framework with a recent double momentum mechanism, leveraging its unique features to achieve an optimal convergence rate for the first time in asynchronous Byzantine MI.
Related Work. A long line of studies has explored the synchronous Byzantine setting (see e.g., Al- istarh al. [2018], Karimireddy et al. [2020. 2021], Allouah et al. [2023]. Farhadkhani al. [2022]. Allen-Zhu et al. [2020], EI Mhamdi et al. [2021]. Dahan and Levy [2024]). Alistarh et al. [2018]. Karimireddy et al. [2021] demonstrated that historical information is crucial for optimal performance in Byzantine scenarios; and Karimireddy et al. [2021] introduced the idea of combining generic aggregation rules, together with standard momentum with a parameter of 1/ VT to effectively incor- porates VT iterations of historical gradients. Additionally, Dahan and Levy [2024] showed that double momentum approach is effective by taking a momentum parameter of 1/T,, capturing the entire gradient history.
Robust aggregators such as Coordinate- -iite Trimmed Mean (CWTM) [Yin et al., 2018), Krum [Blanchard et al., 2017], Geometric Median (GM) [Chen et al.. 2017]. CWMed [Yin et al., 2018], and Minimum Diameter Averaging [Guerraoui et al., 2018] have also proven to be highly beneficial in synchronous settings and have been evaluated within robust frameworks [Allouah et al., 2023, Karimireddy et al., 2020, Farhadkhani et al., 2022, Dahan and Levy, 2024]. However, not all robust aggregators achieve optimal performance, leading to the development of angr-agggrs

---

[Karimireddy et al., 2020, Allouah et al., 2023, Dahan and Levy, 2024] to enhance their effectiivnesss. While standard aggregation works well in synchronous settings, where outputs are averaged across all workers, it is less suitable for asynchronous settings, where updates are processed individually as they arrive [Arjevani et al., 2020].
To adapt these approaches to asynchronous settings, Yang and Li [2023] devised BASGDm, an extension of BASGD (Yang and Li, 2021], that groups worker momentums into buckets that are then aggregated using robust aggregator. Other methods, like Zeno++ [Xie et al., 2020b] and AFLGuard [Fang et al., 2022], rely on a trusted dataset on the central server, which hinders their practicality. Kardam [Damaskinos et al., 2018] uses the Lipschitzness of gradients to filter out outliers. Unfortunately, none of these approaches ensure generalization error (excess loss) that diminishes with the number of honest data-samples and updates, and suffers from an explicit dependence on the problem's s dimension. And this applies even in the absence of Byzantine faults.
Asynchronous Byzantine MI. faces unique challenges as inherent delays add bias that obscures Byzantine disruptions. To mitigate this delay-bias in asynchronous, non-Byzantine scenarios, Cohen et al. [2021], Aviv et al. [2021] propose methods to keep model weights relatively close during iterations. Other approaches [Stich and Karimireddy, 2019, Arjevani al., 2020, Mishchenko et al., 2022] suggest adjusting the step size proportionally to the delay. These strategies have proven useful in reducing the negative impact of delays, and achieve optimal performance.
Our work extends several concepts from Dahan and Levy [2024] to the asynchronous scenario. We devise novel generalization of their Centered Trimmed Meta Aggregator (CTMA) towards weighted meta-aggregation, making it amenable to asynchronous scenarios. In the spirit of Dahan and Levy [2024], also adopt a recent variance reduction technique called 2S2D [Levy, 2023]. Nevertheless, while Dahan and Levy [2024] used this technique in a straightforward manner, we found crucial to appropriately incorporate individual per-worker weights overcome the challenge of asynchronicity in Byzantine ML.
2 Setting
Our discussion focuses on the minimization of a smooth convex objective f: +
f(x) == Ef
where IC C R2 a compact convex set and D denotes an unknown distribution from which we can draw i.i.d samples {z, ~ Dh. Our work considers first-order methods that iteratively utilize gradient information to approach an optimal point. Such methods output a solution Xy, which is evaluated by the expected excess loss:
ExcessLoss == [E(((T)) - f(x")],
where x" is a solution that minimizes o over IC and Xy E K. approximates this optimal solution.
Asynchronous Training. We explore these methods within distributed environment involving multiple workers. Our discussion focuses on a centralized distributed framework characterized by central Parameter Server (PS) that may communicate with m workers. Each of these workers may draw i.i.d. samples z ~ D: and based on these samples, compute unbiased gradient estimate g E Rd point K. Concretely, worker may compute g := fx;; z); implying that Efgix] = fx().. Specifically, our main focus is on Asynchronous systems, where the PS does not wait to receive the stochastic gradient computations from all machines; instead, it updates its model whenever a worker completes a (stochastic) gradient computation. That worker then proceeds to compute a gradient estimate for the updated model, while the other workers continue compute gradients based on 'stale' models. This staleness leads to the use of staled (and therefore biased) gradient estimates, which is a major challenge in designing and analyzing asynchronous training methods.
Asynchronous Byzantine Framework. We assume that an unknown subset of the m workers are Byzantine, implying that these workers may transmit arbitrary malicious information during the training process, and these "Byzantine" workers may even collaborate to disrupt the training. We assume that the fraction of updates that arrive from Byzantine workers during the asynchronous training process is bounded and strictly smaller than 1/2 and denote this fraction by X.
Remark 2.1 (Fraction of Byzantine Updates vs. Byzantine Workers). In both synchronous and asynchronous settings, it is common consider bound the fraction of Byzantine workers (up
3

---

to 1/22 [Allouah et al., 2023, Farhadkhani er al., 2022, Karimireddy et al., 2020, 2021, Yang and Li, 2023, 2021, Damaskinos al., 2018]. In synchronous scenarios this is meaningful since the server equally treats the information from all workers; which is done by equally averaging gradients of all workers in each iteration in a mini-batch fashion [Dekel et al., 2012]. Conversely, asynchronous scenarios, faster workers contribute to more updates than slower workers, leading to an unequal influence on the training process. In such scenarios, the fraction of Byzantine workers less relevant; and it is therefore much more natural to consider the fraction of Byzantine updates. Interestingly, our definition aligns with the standard one (for the synchronous case), which considers the number of Byzantine workers.
Notation. For each worker i [m]] and iteration 8 (c) represents the total number of updates by worker é up to t, and T is the delay compared to the current model. z(0) is the last update before making 7 the time since the second last update (Figure 1). 7: denotes the delay for the worker arriving at iteration t, i..., worker j arrives at iteration t then T = T4
(9)
(3) for worker i iteration marking (current iteration), Figure 1: Illustration of the delay interval Tr
(() (most recent update from worker i), and ( - Tz (previous update from worker i).
For given time (iteration) t,, let ((9) be the last iteration when worker made an update. We denote dl := d,o), gi : gxo,, gi := gee. and x = X,t., where the latter are individual vectors that we will later define for any worker i. Throughout, |1-Il represents the L2-norm. For any natural
N, [N] = [1,..... .., N). We use the compressed sum notation a = Ek-n Ogg. For every x E Rd. the orthogonal projection of onto set IC is denoted by IIx(x) arg minyex lly x|2.. We denote B and G as the subsets of Byzantine workers and honest workers, respectively, such that [m| 9 + [B]
Assumptions. We use the following conventional assumptions:
Bounded Diameter: we assume there exists D > such that max
||x - y/1 S D. x.E
(1)
Bounded Variance: there exists a > such that Vx E K. 2 Support(D),
E
0²
(2)
Expectation over Smooth Functions: we assume that f(-) is expectation of smooth functions, ic. Vx, y E IC,, z E Support( (D} there exist L > 0 such that,
[} - Vf(y:))) S L[[x yll.
The above assumption also implies that the expected loss f(-) is L smooth.
Bounded Smoothness Variance [Levy, 2023]: in Appendix A we show that Eq. (3) implies that, Vx,y E K., E Support(D) there exists o2. E [0, L such,
E IKV (x; vx(x)) - (V](y;)) - V)(y))|1 S x - 2
(4)
Bounded Delay: 3K such that for each worker i [m]. Tman
S T ( K
T
(5)
where min is the minimum delay of worker i. K bounds the variance of the delay for each worker.
(6)
Bounded Byzantine Iterations: there exists s < 7/2 such that t [T]: tB S At
(6)
where tg is the total number of iterations made by Byzantine workers up to iteration t. Sample-Arrival Independence: we assume that the delays in the system (i.e. - -(0))) are indepen- dent of the data samples. This standard assumption asynchronous training scenarios, see e.g., Arjevani et al. [2020], Aviv et al. [2021].

---

3 Weighted Robust Aggregation Rules
As have mentioned, robust aggregation rules have played major role in designing fault-tolerant ML training methods for synchronous settings (see, c.g., Allouah et al. [2023], Karimireddy et al. [2020, 2021], Dahan and Levy [2024]). These existing aggregation rules treat inputs from all workers equally, which makes sense in synchronous cases where all workers contribute the same number of updates and data samples. Conversely, this symmetry breaks down in asynchronous settings, where faster (honest) workers contribute more updates and samples compared to slower workers.
Inspired by this asymmetry. have identified the need to define notion of weighted robust aggregators that generalizes the standard definition of robust aggregators. In this section, we provide such definition, derive weighted variants of standard aggregators that satisfy our new definition, and design a generic meta-approach to derive optimal weighted aggregation rules. Later, in Section 4, we demonstrate the benefits of using weighted robust aggregators crucial building block in designing asynchronous fault-tolerant training methods (see Alg. 2).
3.1 Robust Weighted Aggregation Framework
Below, we generalize the definition introduced by Dahan and Levy [2024), Karimireddy et al. [2020, 2021] to allow and associate weights to the inputs of the robust aggregation rule, therefore allowing the aggregator to unequally treat its inputs.
Definition 3.1. ( weighted robust. Assume we have m random vectors X1:-..; : Xm
E Rd
and corresponding weights $1....,$m, Sm > O. Also assume have an "honest" subset G C [m]] implying {x4} are independent of each other. Finally, assume that there exists À E [0, 1/2) such that Zieg $4 (1 X)51:m- Moreover, assume that for any i E G there exist pi 2 0 such that,
E||x - 3012= S p. ViEg.
Then an aggregation rule A is called (cx, >)-weithted robust if for any such m random vectors and weights and X 2 0, it outputs & + (x1, Xmi , 8m) such that,
E| Rgll S cxp²
for some Cx 2 O. Above, Xg := Eieg Eieg 8;X,, p² = Eieger Eieg sipt, and the expectation 1
W.E. { and (possible) randomization in the Au.
Here, À represents the fraction the sum of the non-honest vectors' weights, unlike the unweighted definition (in synchronous cases) (Karimireddy et al., 2020, 2021, Allouah et al., 2023, Farhadkhaní al., 2022] where it indicates the fraction of non-honest vectors. These definitions align when all weights equal [Dahan and Levy, 2024]. Similarly to the unweighted version, the optimal cx should be cx S O()) [Dahan and Levy, 2024].
Remark 3.1. Note that definition is generic and may be applied in both convex and non-convex scenarios. Moreover, it is natural to consider such weighted aggregators beyond asynchronous settings. For example, in synchronous settings where workers have varying batch sizes, weighted aggregation based on batch sizes may be more effective than uniform aggregation.
Next, we present two weighted variants of standard (non-weighted) aggregators that satisfy the above definition (we defer the proof into Appendix C). Table 1 summarizes their ey values.
3.2 Weighted Variant of Geometric Median and Coordinate-Win
Weighted Geometric Median (WeightedGM)) The Weighted Geometric Median (WeightedGM) minimizes the weighted sum of Euclidean distances of points. Formally, for points m and corresponding weights (8s [m WeightedGM E arg minyer* Σiemm) 8: x:I
Weighted Coordinate- Wise Median Mee)) The Weighted Coordinate- Wise Median (WeightedCWMedl aggregates multi-dimensional data by finding the weighted median of each coordinate separately. Thus, for given coordinate if {x,]². 1 are sorted and weights { the weighted median Xj- is the element where: j = arg minze|m)
(EvELA) 8, 1/2 Exe(m) 8i
Σ 84 Em s; for some j. then: WeightedMedian x
5

---

Aggregation
w- GM
w-CWMed
w-GM W-CTMA
w-CWWMd W-CAMA
(1 1+ T
1-2X
1-23
1-2A
Table Summary of weighted aggregation rules and their respective C values.
Algorithm 1 Weighted Centered Trimmed Meta Aggregator (w-CTMA)
1: Input: Set of vectors {x: J weights {s threshold parameter E [0, 1/2),
2:
(cx, wJ-weiht robust aggregated vector Xo A ((x,) Jm J==1i
3: Sort the sequence { |x - x ) in non-decreasing order, and then reindex (x))ee(m) and their
corresponding weights {5; ]ejm according to this new order.
4: Define S f- set of indices corresponding to the first j" elements in the sorted sequence, where
j* is the smallest j E [m] for which Σieg] 8; 2 (1 (1- EiEm) 8i-
5: Set 8m-1 + (1 - A) Zie(m) 8t -iel--11 Si, Xm+1 + Xx', S ( + 1}.
6: Compute the weighted sum: X < (1/Excs:) Eieg 8,2,
7: Output: &
3.3 Weighted Centered Trimmed Meta Aggregator (w-CTMA)
Table 1 illustrates that w w-GM and w-CWMed fail to achieve the desired optimal cΛ OA): typically for S 1/3, their Cx remains I O(1). To address this suboptimality, we propose w-CTMA, weighted extension of the Centered Trimmed Meta Aggregator (CTMA) [Dahan and Levy, 2024]. This extension enables us to achieve the optimal bound cx O(A) for X s 1/3 (see Table 1).
The w-CTMA algorithm (Algorithm 1) operates on a set of vectors along with their associated weights, a threshold À E [0, 1/2), and (cx. -e-ehitt robust aggregator. It sorts the distances between each vector and the weighted robust aggregator, trims the set based on the threshold to satisfy Eies S, (1 11ms and calculates a weighted average of the vectors, excluding outliers based on their proximity to anchor point- the weighted robust aggregator.
Lemma 3.1. Under the assumptions outlined in Destnition 3.1, if w-CTMA receives a (ex, A)- weighted robust aggregator. Awi then the output of w-CTA, &, is (60X(1 + cx), Aorrbusst
For the complete analysis, please refer to Appendix C.2. Like CTMA [Dahan and Levy, 2024], w-CTMA highly efficient, with a computational complexity of ( +m log m)) similar to w-GM, w-CWMed, and weighted averaging, differing by at most an additional logarithmic factor.
4 Asynchronous Robust Training
We leverage the y²-SGD algorithm [Levy, 2023], double momentum mechanism that enhances variance reduction. By seamlessly incorporating our weighted robust framework as black box into the 2-SGD derive optimal asynchronous Byzantine convergence rate.
SGD: The 2SGG is a variant of standard SGD, incorporating several key modifications in its update rule:
Wi+1 = 11 (w: na;d)), Xt+1
Σ
agWa;
W1 = E IC, Vt>
a14+1
kE[++1]
Here, {a, > 0}2 are importance weights that emphasize different update steps, with a x f place more weight on recent updates. The sequence {x+}: represents weighted averages of the iterates (Welt, and d, is an estimate of the gradient at the average point, fx(x), differing from standard SGD, which estimates gradients at the iterates, (ww:).
This approach relates to Anytime-GD [Cutkosky, 2019], which is strongly connected momentum and acceleration concepts [Cutkosky, 2019, Kavis et al., 2019]. While the stochastic version of Anytime- GD typically anism to produce a corrected momentum estimate d, [Cutkosky and Orabona, 2019]. Specifically, d (i); and for
the estimate Vf(x; 2,), 2DDDG employs variance reduction mech-
d: vf(xiiz) 21) + (1 (d, Vf(x)-1;z))).

---

Algorithm 2 Asynchronous Robust u²-SGD
1: Input: learning rate т)t > O, starting point X1 K, number of steps T, importance weights {or tt, momentum correction weights {Ge)., (cx; A)-robust weighted aggregation function A...
2: Initialize: Vi E [m]] set ( O. Set W = X1. Each honest worker E G draws (0) and
set ( Vf(x)
3: for = to I do
D Server update
4: Receive d. from worker E [m]] and update:
5: d = d s; 5/1 1;
Vj set s = =())) and for t > 1: d. = (
6:
Update server model:
We+1 = IIx (w m. ot (3m & x.+1 Ei=l -k=1 W.
7:
8: Send x, to worker i. If is an honest worker, it performs the following update:
undwate
9:
Worker draws 2, ~ DD computes gr V V[(x;z))) & gi-r VX(xx- 24))
10:
and updates: d, = g: - (d, 8L-7.)
t Worker update
11: end for
12:
Output: XT
Here, 8, 1] are corrected momentum weights. It can be shown by induction that E/d,) (xx)( however, in general, [Ed [4] + (xt),, unlike standard SGD estimators. Nevertheless, [Levy, 2023] demonstrates that choosing corrected momentum weights 3r 1/t results in significant error reduction, with / 2 == E d, V fx+)] < O /t) at step t. where 8² < O(a² DDoo)) This indicates that variance decreases with i, contrasting with standard SGD where the variance E| = Egg fxx))] remains uniformly bounded.
4.1 Asynchronous Robust 2SD
Building upon these, we integrate the 2SGD with (cx, A)-weighted robust aggregator A., as described in Alg. 2. At each iteration t E [T]. the global PS receives an output from a certain worker and aggregates all workers' recent updates
(d."
m by employing weights accordingly to i=1
the number of updates of each worker { (1) m
Jim
An honest worker i arriving at iteration & returns
its corrected momentum d to the PS, computed as:
de- = -t- (1 (d -BI-T-----)
where g: V V[(x;; n.), and gr-r, (x(x 2.). Afterwards, the PS performs the AnyTime update step as follows:
W = 11. (w:- mand (6) (00 )m=))))))))))))mm)()))))) Xi+1 01:+1
Σ
ag W
kE[t+1
In the spirit Levy [2023]. Dahan and Levy [2024], we suggest employing 3, l/st. which effectively considers the entire individual gradient's history of each worker; this translates to stochastic error bound of ||e{" || < (6ō/ (x) for honest worker i arriving iteration L. To achieve an error corresponding to the total number of honest iterations (g. specifically ||e,|| < O (tā/lg in the -indiitributed setting [Levy, 2023], weighted collective eитor across all honest workers should be considered with weights determined by the number of honest worker arrivals, as detailed in Theorem 4.1. The unique characteristies of SDD make well-suited for the asynchronous Byzantine setting, where À < 1/2 relates to the fraction of Byzantine iterations. The total iteration number matches the sum of the workers' frequencies (Ee(o) e( tg), aligning with the weighted robust definition Definition 3.1. Using other approaches like momentum [Karimireddy al., 2020, 2021, Allouah et al., 2023] is less straightforward in the asynchronous Byzantine setting with the weighted robust definition. This complexity arises because an individual honest error || & 06//v55 implics that weights should be /sa instead of st, which can be more challenging. Remark 4.1 (Memory and Computational Overhead Algorithm 2). Algorithu 2 incurs additional memory and computational costs compared to the asynchronous Byzantine-free setting [Arjevani et al..
/tgg/.),,..)))))) ). as
7

---

2020], where the server stores only one worker's output and the global model. Algorithm 2 stores the latest outputs from all workers, increasing memory usage to O(dm). Robust aggregation methods like w-CWMed [ Yin et al., 2018| and (e-appraximate) w-GM [Chen et al., 2017, Acharya et al., 2022] add a computational cost of Odm log m) and ((dm + de dd- respectively. This is in contrast to Byzantine-free settings where worker outputs are used directly without aggregation. Comparable overheads are observed in synchronous outputs from all workers. This reflects a necessary trade-off: achieving robustness inherently requires leveraging information from all workers to counteract the influence of potentially faultyy ones.
Fraantine-resiliee
methods, which similarly aggregate
Theorem 4.1. For a convex set K. with bounded diameter D and function f K + IR and assume the assumptions in Equations (2).(3)((4) Then Alg. 2 with parameters {a+ the and {3, 1/srhe ensures the following for every t E [T] and each honest worker i E EG:
1
(1)
E
E
Et
(
( Eieg St SEg
tg
where et iterations up to the th iteration.
dee v
) 0² 20² 32D K2ot and lg is the total number of honest
Proof Sketch of Thmm, 4.1. The complete analysis is provided in App. B.I. It involves several key steps for an honest i worker who arrives at iteration t:
1. Following Lemma B.I, the distance between successive query points: (0)
4K D
2. We analyze the recursive dynamics of the error term Et by setting 3: and obtain:
(1) = (g) f(( ( + (0 - 1) + (s - 1))
5t e1
where Z!00 = gi
( fxx (0) (gi
(1) vf(x )). Unrolling this recursion provides an vf(x()) + (s: 1)2 (0) ExEls(") M where ( gt (c)
explicit expression: 8
thus, (M )
is a martingale difference sequence.
3. Employing the above with Eq. (2) and (4), we have: E
11 & 12 < 20 +222 02.
4. Leveraging the properties of martingale difference sequence, we have:
E
s
Et
E
M
Σ
B
< <02 (1)
5t
ME
RE
E
S
( Et
(1)
E
Σ RE9 kE
Σ
M
Σ iEg KE
Σ
E
8/ (3)
821g
3cg
8E9
Remark 4.2. Compared to synchronous scenarios [Levy, 2023, Dahan and Levy, 2024]. the variance in Thm. additionally includes the variance in the delay, denoted as K (Eq. (5)). In balanced scheduling methods, like Round Robin [Langford et al., 2009], the impact of K on the error becomes (3)
m constant. In the case of constant delays, the factor K equals 1. Lemma 4.1. Let A,, be (cx, 2)-weightte robust aggregation rule and let f K. + R, where K. is a convex set with bounded diameter D, and presume that the assumption in Equations (3)) hold. Then invoking Alg, 2 with {ar = f)ee and 13. = 1/8t)t ensures the following for any E [T).
minor, as the delay Tt
E El(à. - Vf(xi) 50
02
cxmō²
(Imaz DL)²
CA(TmaaDD 2L)
f2
t2
Variance
Bias
8

---

where d, (sd )m Ti rim = mm (0) and 0² = =20² +32D2
Lemma 4.1 shows that the error between our gradient estimator d, and the true gradient includes a bias term arising from the aggregation of delayed momentums. This is in contrast to the synchronous scenario [Dahan and Levy, 2024] where the error is solely variance-dependen without any bias component. However, this bias does not affect the overall excess loss (Theorem 4.2), which remains comparable to the optimal rate achieved in synchronous Byzantine settings (see Remark 4.5).
By integrating the weighted robust aggregator with the double momentum mechanism, we achieve the optimal convergence rate for the first time in an asynchronous Byzantine setting-a significant advancement over previous efforts.
Theorem 4.2 (Asynchronous Byzantine S²D Guarantees). Let A_ be (cx, A--weihhted robust aggregation rule and let f be a convex function. Also, let us make the same assumptions as in Thm. 4.1, and let us denote G == [V )l, where x' E arg minxek, (x). Then invoking Alg. 2 with {ar- = l)2 and {B:- = 1/ and using learning rate 1) S 1/4LT guarantees,
G LD' Pmaa (V1+ +
[[[(xT) - =(w')
T
VT
where ō² 20 32D2 Mmax = Eimm ot Time and T-maz = maxic(m] (Te (8)
Remark 4.3. In the absence of Byzantine iterations (A 0), the parameter ex of (cx, We-wethteed robust aggregator can diminish to O when we use w-CTMA (see Table 1). This aligns with the asynchronous SGD analysis [Arjevani et al., 2020] and represents the first work to achieve optimal convergence without Byzantine workers compared to previous efforts [Yang and Li, 2021, 2023, Fang et al., 2022, Zhu al., 2023, Damaskinos al., 2018, Xie al., 2020b, Zhu et al., 2024].
Remark 4.4. Unlike previous works (Yang and Li, 2021, 2023, Fang al., 2022, Zhu et al., 2023, Damaskinos et al., 2018, Xie et al., 2020b, Zhu et al., 2024], our convergence rate is independent of data dimensionality d and is sublinear at T, even in the presence of Byzantine workers.
Remark 4.5. This result is consistent with the synchronous scenario [Dahan and Levy, 2024], where the delay is constant T₁ = m as in Round Robin [Langford et al., 2009]. In this case, the proportion of Byzantine workers is X, and the asynchronous excess loss S O LD Da /T
In compari- son to the synchronous case, where m workers perform rounds, here we make R query point updates
and = Run data-samples, resulting in synchronous excess loss S O
LD2
De 28/1//m /1mmtes
/R.
LD
DavT+mee /T
[Dahan and Levy, 2024].
Experiments
To evaluate the effectiveness of our proposed approach, we conducted experiments on MNIST [LeCun et al., 2010] and CIFAR- 10 [Krizhevsky et al., 2014] datasets-two recognized benchmarks in image classification tasks. We employed a two-layer convolutional neural network architecture for both datasets, implemented using the PyTorch framework. The training was performed using the cross-entropy loss function, and all computations were exccuted on an NVIDIA L40S GPU. To ensure the robustness of our findings, each experiment was repeated with three different random seeds, and the results were averaged accordingly. Our experimental results demonstrate consistent performance across both datasets. Further details about the experimental setup and the complete results are provided in Appendix D.
Weighted vs. Non-Weighted Robust Aggregators. We evaluated the test accuracy of weighted and non-weighted robust aggregators in imbalanced asynchronous Byzantine environments. Our experiments show that weighted robust aggregators consistently achieved higher test accuracy than the non-wen weighted ones (see Figure and Figure 5). This highlights the benefit of prioritizing workers who contribute more updates in asynchronous setups.

---

Lece 21 Ohine
Lobel Ttc. Bleeee
23t lec (Chmel Racckidd
Sig figstir uid
Figure 2: CIFAR-10. Test Accuracy of Weighted vs. Non-Weighted Robust Aggregators. This scenario involves 17 workers, including 8 Byzantine workers, with workers' arrival probabilities proportional to the square of their IDs. We used the SGD in this scenario. Left: label flipping, À 0.3. Right: sign flipping À 0.4.
Effectiveness of w-CTMA. We evaluated the test accuracy of weighted robust aggregators with and without the integration of w-CTMA, as shown in Figure 3 and Figure 6. The results demonstrate that w-CTMA can enhance the performance of weighted robust aggregators in various Byzantine scenarios for both datasets.
Libet
sir Hlgcing Chcoreedd
LES Civeedd
Figure 3: CIFAR-IO. Test Accuracy Comparison of Weighted Robust Aggregators With and Without MACM This scenario involves 9 workers, including either or 3 Byzantine workers. The arrival probabilities of workers are proportional to their IDs, and we employed SSGD On the left, the label flipping and sign flipping attacks are depicted with 0.3 and 0.4, respectively, using 3 Byzantine workers. On the right, the little attack shown with 0.1 and Byzantine worker, and empire attack is shown with = 0.4 and Byzantine workers.
Performance of SSD Standard Momentum and SGD. We evaluated the test accuracy of 2D-SGD in comparison to standard momentum [Polyak, 1964] and SGD [eon Bottou, 1998] within an asynchronous Byzantine setup. Figure 4 and Figure 7 show that 2 performs on par with standard momentum, while SGD generally exhibits poorer performance relative to both. These results underscore the importance of utilizing historical information when addressing Byzantine scenarios.
Tig
Figure 4: CIFAR-10. Test Accuracy Comparison Among Different Optimizers. This scenario involves workers Byzantine) with 0.4, and workers' arrival probabilities are proportional their IDs. Left: sign flipping. Right: label flipping.
Conclusions and Future Work
This paper shows that using a double momentum approach, which incorporates the entire history of each honest worker, improves the stochastic error bound be proportional to the total number of updates when considering their weighted average in asynchronous settings. By integrating this method with a weighted robust framework, 2² 2DD achieves an optimal convergence rate, making it particularly effective for asynchronous Byzantine environments. However, integrating other optimization algorithms, like momentum, into this weighted robust framework can be challenging, as they do not achieve error bound proportional to the total number of updates and may complicate the adjustment of weights based on the update count. This highlights the need for further research to adapt different methods to the spirit of this framework in non-convex and convex settings.
10

---

Acknowledgement
This research was partially supported by Israel PBC-VATAT, the Technion Artificial Intelligent Hub (Tech.Al), and the Israel Science Foundation (grant No. 3109/24).
References
Anish Acharya, Abolfazl Hashemi, Prateek Jain, Sujay Sanghavi, Inderjit S Dhillon, and Ufuk Topeu. Robust training in high dimensions via block coordinate geometric median descent. In International Conference on Artificial Intelligence and Statistics, pages 11145-11168 PMLR, 2022.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018.
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilien non-convex stochastic gradient descent. arXiv preprint arXiv:2012. 14368, 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 International Conference on Artificial Intelligence and Statistics, pages 1232-1300. PMLR, 2023.
Yossi Arjevani, Ohad Shamir, and Nathan Srebro. A tight convergence analysis for stochastic gradient descent with delayed updates. In Algorithmic Learning Theory, pages 111-132. PMLR, 2020.
Rotem Zamir Aviv, Ido Hakimi, Assaf Schuster, and Kfir Yehuda Levy. Asynchronous distributed learning: Adapting gradient delays without prior knowledge. In International Conference on Machine Learning, pages 436-445. PMLR, 2021.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is 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.
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.
Alon Cohen, Amit Daniely, Yoel Drori, Tomer Koren, and Mariano Schain. Asynchronous stochastic optimization robust to arbitrary delays. Advances Neural Information Processing Systems, 34: 9024-9035, 2021.
Ashok Cutkosky. Anytime online-to-batch optimism and acceleration. In International conference on machine learning. pages 1446-1454. PMLR, 2019.
Ashok Cutkosky and Francesco Orabona. Momentum- based variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Tehila Dahan and Kfir Yehuda Levy. Fault tolerant ml: Efficient aggreggggng and synchronous training. In Forty-first International Conference Machine Learning, 2024.
Georgios Damaskinos, Rachid Guerraoui, Rhicheck Patra, Mahsa Taziki, al. Asynchronous byzantine machine learning (the case of sgd). In International Conference on Machine Learning, pages 1 115--1544 PMLR, 2018.
Ofer Dekel, Ran Gilad -aacd-Ba Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Louis Alexandre Rouault. Distributed momentum for byzantine-resilien stochastic gradient descent, In 9th International Conference on Learning Representations (ICLR), number CONF, 2021.

---

L eon Bottou. Online learning and stochastic approximations. Online learning in neural networks, 17(9))142, 1998.
Minghong Fang, Jia Liu, Neil Zhenqiang Gong, and Elizabeth S Bentley. Afluuar: Byzantine- robust asynchronous federated learning. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 632-646, 2022.
Sadegh Farhadkhani, Rachid Guerraoui, Nirupam Gupta, Rafael Pinot, and John Stephan. Byzantine machine learning made easy by resilient averaging of momentums. In International Conference Machine Learning, pages 6246-6283. PMLR, 2022.
Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability of distributed learning in byzantium. In International Conference Machine Learning, pages 3521-3530. PMLR, 2018.
Rachid Guerraoui, Nirupam Gupta, and Rafael Pinot. Byzantine machine learning: A primer. ACM Computing Surveys, 2023.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- fion, 2(3-4): 2016.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine-robust learning on heterogeneous datasets via bucketing. arXiv preprint arXiv:2006.0995
2020.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pages 5311-5319. PMLR, 2021.
Ali Kavis, Kfir Y Levy, Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar- 10 dataset. online: https: // www. cs. toronto. edu/ "kriz/ cifar. html, 55(5), 2014.
Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. In Concur- rency: the works of leslie lamport, pages 203-226. 2019.
John Langford, Alexander Smola, and Martin Zinkevich. Slow learners are fast. arXiv preprint arXiv:0911.0491, 2009.
Yann LeCun, Corinna Cortes, Chris Burges, et al. Mnist handwritten digit database, 2010. URL http://yann. /ltp:///aanneeeuunn..m lecun. com/ wwwp///wwpp//////////wwtww/wwttt Licensed under CC BY-SA 3.0, available at https: //creativecommons wwwploccesss/byy-aaaeeee
Kfir Y Levy. sdds Stable stochastic optimization via double momentum mechanism. arXiv preprint drXiv:2304.04172. 2023.
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake E Woodworth. Asynchronous sgd beats minibatch sgd under arbitrary delays. Advances in Neural Information Processing Systems, 35:420-433, 2022.
Boris T Polyak.
Some methods of speeding up the convergence of iteration methods. Ussr computa- tional mathematics and mathematical physics, 4(5):1-17, 1964.
Sebastian Stich and Sai Praneeth Karimireddy. The freob-feedback framework: Better rates for sgd 2019,
with delayed gradients and compressed communication. arXiv preprint
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty Artificial Intelligence, pages 261-270. PMLR, 2020a.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous sgd. In Interna- tional Conference on Machine Learning, pages 10595- PMLR, 2020b.
Yi-Rui Yang and Wu-Jun Li. Basgd: Buffered asynchronous sgd for byzantine learning. In Interna- tional Conference on Machine Learning, pages 11751-11761. PMLR, 2021.
12

---

Yi-Rui Yang and Wu-Jun Li. Buffered asynchronous sgd for byzantine learning. Journal of Machine Learning Research, 24(204):1-62, 2023.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pages 5650-5659. PMLR, 2018.
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. A survey of large language models. arXiv preprint arXiv:2303. 18223, 2023.
Zehan Zhu, Yan Huang, Chengeheng Zhao, and Jinming Xu. Asynchronous byzantine-robust stochastic aggregation with variance reduction for distributed learning. In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 151-158. IEEE, 2023.
Zehan Zhu, Yan Huang, Chengcheng Zhao, and Jinming Xu. Asynchronous byzantine-robust stochastic aggregation with variance reduction for distributed learning. 2024.
13

---

A Bounded Smoothness Variance Assumption
We show that Eq. (3) implies that Eq. (4) holds for some of. E [0,
[l((V((x - fx())
(V)()z)) - ((fl:)))V((y)))))) ff()))
f(]V)((xz) V [VV ff()))
- [ -yl
Here, we also used E (x; V/(y;=) V (y)), and followed Eq. (3). Therefore, we establish that of E [?].
B Asynchronous Robust Convex Analysis
B.1 Proof of Thm. 4.1
Proof of Thm, 4.1. To simplify the discussion, let's introduce some notations for a worker i E G, who arrives at time t:
(7)
Xx, == -t = x;
X,, 1 X4 X4- 7e-7
Xi-Ts
(i) E - Et-Te
6, = êt-Ti Et
h, gi-Ti
ge
h gi -1-1
Bt-71
Next, we will employ the following lemma that bounds the distance between the averages Xx, Xt-ri Recall that x, and Xt-7, are consecutive query points for the worker that arrives at time
Lemma B.1 (Aviv et al. [2021]). Let f : R. where K. is a convex set with bounded diameter D. Then invoking Alg. 2 with {ar = tht ensures the following for any [T]
4DT
|x 18-xx4 x1-
For completeness, we provide proof in Section B.1.1.
Next, we define 14 be the average delay of the worker i that arrives at iteration f, i.e.,
Tt
St
8t 81-
14
From Equation (5), we infer that,
(1) min
Me 5 K
(5) Tmin
Following this, analyze the upper bound the distance between two successive query points for an honest worker that arrives at time t:
AT D
4T D
4K
sy X2, 1ll = X Nt-Te-ue
D
(8)
(J4-,,, 1)
8t
where the first inequality follows Lemma B.I. The second equality utilizes the relation 8t - The final inequality stems from the assumptions in Eq. (5) and Eq. (7).
P- TL
Pe-
Remark:
Before proceeding with the analysis, shall condition the (possible randomization) in the delays of all workers; and recall that the data-samples are independent of the delays. Thus, the expectations that take are only with respect to the randomization in the data-samples and conditioned on the delays. Thus, this conditioning allows us to treat the delays - (8)s 's and number of updates 8 (i) s as fixed and predefined.
We proceed analyze the recursive dynamics E,, for each E g. Based on the definitions of d, and E,, we can present the recursive relationship in the following way:
E = B, v)(x,))) Z.) + (1 - B.)&..-1
14

---

where Z. = ha, Vf(x,,) (hs, (f(.,. Upon choosing 3r the above equation as follows:
1 we can reformulate
St,, (h,, vs((,,)) + (st 1) + (s: - 1)6,, -1-
Unrolling this recursion yields an explicit expression for any 2 1:
S1E Σ M
(9)
kE[sa]
where we have defined,
M (1) = h2: V + (A: 1)
(10)
and l is a counter for the iterations where worker makes an update.
Following this, derive upper bound for the expected square norm of M follows:
0 s 2E | h V |12 + 2(k 1) vf((x)) (ha-1- ((((
s 20 + 20
1) x11
=222=32 0²
(11)
where the first inequality uses la + bl12 - 2||a|| 2 which holds Va, b R The second inequality aligns with the assumptions outlined in Equations (2) and (4). The third inequality uses Eq. (8).
Establishing the First Part of the Theorem: Before continuing, it natural to define an ordered ..... Zig J such that these samples associated with honest and consecutive updates (or iterates) of the PS, and tg is the total number of honest updates up to time t. Concretely, honest worker that utilizes fresh sample z,,
set of samples (z1, z2.....
the 7h honest update of the PS is based
Now, for given worker we shall define the filtration associated with his updates. Concretely, let (5) k E {l.... ST J. Then we define F(8) to be the sigma-algebra induces by the sequence of samples
(2), 22, ........ Neg) } up to the hth update of worker And it is easy to see that (Fx [ is filtration. Moreover, it can be directly shown that for given worker i, then the above defined sequence ) (
(M
(see Eq. (10)) a martingale difference sequence with respect ( ) This allows us to directly employ Lemma B.2 below, which yields.
E
E
2
(
= Σ
50 S
kE [1000]
KE
where have also used Equations (9) and (11). Thus, the above bounds establish the first part of the theorem.
Lemma B.2 (See e.g. Lemma B.1 in Levy [2023]). Let {Me)e be martingale difference sequence with respect to a filtration {Fih. then the following holds for any t,
E
Σ TE
M
E EIM,
rE(1]
Establishing the Second Part of the Theorem: As before, we define an ordered set of samples {z). .... Zeg } such that these samples are associated with honest and consecutive updates (or iterates) of the PS, and &g is the total number of honest updates up time t. Concretely, the th honest update of the PS is based on an honest worker that utilizes fresh sample Z,. We shall also define (Fr)re]ts) be the natural filtration induced by the ordered sequence of data samples.
Moreover, for a given sample z, E {Zz, Zz,... Zto J. let i E [m] be the worker that is associated with the th honest update of the PS, with a fresh sample z,. In this case, we shall define:
M, := (i-) (4)
15

---

where M is defined in Eq. (10). is immediate to show that (M,rrEjt, is a martingale difference sequence with respect to (F+) rEtte) Moreover, the following holds directly be the definition of M,;
to Σ M, ==1
Σ EEG KE
M
(12)
(8)
Now using Eq. (9) the following holds,
Σ
Σ
Σ
M [(
(13)
REg
$E9 KE
Combining Equations (12) and (13) together with Lemma B.2 establishes the second part of the theorem,
10
E
Et
(2)
E
Σ
Σ
M
E
Σ
M
Σ 1=1
E
- ö"tg.
kEG
iEG
ke
where the inequality uses the bound Eq. (11).
B.1.1 Proof of Lemma B.1
Proof. We borrowed the following steps from Aviv al. [2021]. Let's define y E K. as the average of x, over the interval [t Tr, f]. i.c.
a,W,
Ot i=t-1++1
Then have the following relationship:
t-
Σ a.w,
Σ a.w, +
Σ
a1;x:
a,W; 01:--1,X--1 + at-retlay
i-
Hence,
011--.. (xi X1- -y x1)
By setting a₂ t, we have that,
02- y Xx
1xx
Xt-
01:7-
Tell- - + 1 + 1)
Ily - -xel
[t) Ti + 1)
7t - Ti 1++1 1)
|ly - x + (1 tT:
ly xzl
(1 Te)(1 +
)2
tr.
Ily xx
lly x
T
(1 (1-r,)
For 2 37,, we have that,
3r,l)
97,1)
47,l)
Ix - X 5
-
21. 41.
Given that the domain is bounded, ||x; - 144-11 D Vt, for t 3T, we have D << 4n.D Combining these results, we conclude:
|x; X,- < 47:l
16

---

B.2 Proof of Lemma 4.1
Proof of Lemma 1.
Lemma B.3. Let K + R. where K. is convex set with bounded diameter D. Then invoking Alg. 2 with {ar = f)z ensures the following for any E [T', and every i, [m].
(0) + (5)
4D
x(2)
X
-x(
5
Proof.
4D (9
AD-
xx
x
|xx
x
xx
x
where the first inequality a result the triangle inequality, and the second follows Lemma B.1.
Bias Bounds. Here's refined version:
We begin by analyzing the upper bound of the bias in the collective gradients of honest workers up to time in relation to the gradient at that time, denoted as B/. Following this, we derive the upper bound for the bias between the collective gradients of these honest workers and the gradient of an individual honest worker, also up to time f, which we denote as B,. For clarity, we define
V gg. == Eleos 25
Eieg ot
f(x())) (1)
||||| = E
[x(x))]
G.t
1
[x(()) v/(m))
=E
Eieg
(
iEg
Σ
(1)
- vs(x)||
< E
Σ
(
81
iEG
(8)
E
x
Dieg 81
Lieg
4DL
(2)
(6)
Eieg 8t
Lieg
47 man DL
(14)
Here, the first inequality leverages Jensen's inequality, and the second follows the smoothness assumption in Eq. (3). The third follows Lemma B. and the last inequality follows that T T-
maxie(m) (T( (5)
}.
17

---

For the second bias B3 we have:
|Bss| = v.((x;) - V..e
vf(x; 10)
1
Σ
300 (xx (x)
Ejeg 8t
55)
jEg
E
Σ
(5)
Vf(xx())
Ejer st
1EG
E
Σ
St
5
X
Ejeg 88
jEg
4DL
: + (3)
(0)
E
Σ
Ejeg 8t
(5)
t
jEG
8T DL
(15)
Like before, the first inequality leverages Jensen's inequality, and the second follows the smoothness assumption in Eq. (3), the third inequality follows Lemma B.3, and the last one follows that Te man maxie(m] (T(()).
Variance Bound.
We start by determining P: outlined in Definition 3.1:
Elid! dl s 3Elld
(x 12
33 V.. g.
dg.ell + 3E |?11
3E
(8)
2
+
3E
Eieg 81 (1)
8t Et
(i) (0)
3E |?
$Eg
36
3
192(Tpmaz DL)²
tg
f²
8/
60
192(
(T DL)²
81
where dg,, = Ee Eier (1) a The first and inequality uses ||a + b + clI < 3|
3 +|||cl? which holds Va, b, c Rdd. The second inequality follows Theorem 4.1 and employs the second bias bound in Eq. (15). The third uses the fact that (1) < tg. Vi G. Accordingly, we set pf
6 192(r max DI.)"
Following this, derive p as outlined in Definition 3.1:
0²
1
(i)
66
192 (T,
DL)²
6m2²
192(r,mas DL)
E,eg*
8
Ps
=
tg
S
(i)
22
tg
f2
St
iEG
(16)
18

---

Next, we establish an upper bound for E
B 11
E d.
V [xx)
< 21
d. dg.t
+ 21
dg.t
4 [x(x))]
6m8²
192(T DL)²
$ 2ca
+ + dg.t
Vg,e|l
+ 4E |
tg
f²
6mo?
192( Ft 2
20x
+ +I 41R
(0) ct
+ 4 | ||
ΣiEo
(8)
88
lEg
12cxmö²
4
(TEER (384c) + 64)
fg
tg
t2
80
24c
64(T(mar DL)
384cA (TiMOz DL)
12
12
which holds Va, Rd. The second inequality utilizes the same inequality and is further supported by Definition 3.1 and Equation (16). The third aligns with Theorem 4.1, and employs the first bias bound in Eq. (14). The last one utilizes the fact that ig 2 (1 d)t 2 1/2, given À < 1/2.
where the first inequality uses la + bll2 < 2||a|2 + 2
B.3
Proof of Thm. 4.2
Proof of Thm. 4.2. Following Lemma 4.1 and applying Jensen's 's inequality, we derive the following bound:
[oV++ max
maR DLVI+
E = =VEE= VEI SO
(17)
Vl
where the third inequality uses va+b Va + vb for non-negative a, E R. The explanation behind this can be seen through the following steps:
(Va + vb) = =a
a
whereby taking the square root of both sides of this equation, obtain the desired inequality.
Next, let's revisit the AnyTim guarantee as outlined in Cutkosky [2019] and proceed delve into the regret analysis of the update rule.
Theorem B.1 (Rephrased from Theorem in Cutkosky [2019]). Let f K. + R be a convex
with minimum x" E arg minwek I' (ww). Also let (or 2 0} and (wr E KK), {x, E K.)., such that {xe)e an {at) weighted averuged of [w.) iee. such that X1 = W1, and for any 2 1,
Σ OtW7
X++1 =
a1:+11 rE[(+1]
Then the following holds for any 2
(1x(((();)) f(xx)) V Σ V.(,)) -x))
rElA]
Lemma B.4. Let f: K R be a convex function with a minimum x* arg minwek f(w), and assume that the assumption in Eq. (1) holds. Also let {a, 2 0h, and {we E K)e. Then, for any I 1, an arbitrary vector d, Rdd and the update rule:
W IIx (wr mand))
we have,
D
1
ar (d., Wr+1 xx)=
<
|w, 3r
2nj
21
19

---

Lemma B.5. let f: K + R be an L-smooth and convex function, and let E arg minxex f(x),
then for any x E Red we have,
[Vf(x) S - f(xx))
Next, for every iteration t S T, we define:
d, == Audd ( pm I== St & = dr (x()))
Thus, combining Theorem B.1 with Lemma B.4, we have that,
(xx([(x)) f(x')) s
Σ ar (Vf(x))), Wr -xx)
tEi1]
Σ
a (dy, W - xx)++ + Σ
ar (dr, Wr -Wr+1) - Σ
a (E,, W - x*)
TE
TE/t]
rE|d]
D
||,, w,+1 12 + Σ
ar (d,, W - -w++1)
Σ
ar (E,, W
W - -x")
2n
21
TE(!]
rE((]
rE((]
D2
|| wr+1 +
Σ
ar (Vf(x,), - - -wr+1) - Σ
a (7 Wo+1 - x*)
2n)
21
rE(t)
rE(t]
rE(t)
D
Σ
|W-
W 1 +
Σ
a+ (+((V[())) Wr (F- +D Σ
a
27
21
7E(d]
7E(0]
rE(d]
(A)
(18)
where the first inequality is derived from the Anytime guarantee, as outlined in Theorem B.1. The second inequality follows Lemma B.4. The third inequality is result of applying the Cauchy-Schwarz inequality and the assumption in Eq. (1).
(A)
W
Σ
a, (V)(x,), W, w
2n rEtt
rE[t]
Σ
||, 1
Σ ar (V((x) Vf(x'), w, - -w++1) +
Σ
a. (V(((x)), w, -W++1)
2n rE|(]
TE(e]
rE|(]
11 Σ
a (V)(() vf(x)) 112 + Σ (+((V((x'), Wt - -W+11
$
rEll
TE(t]
< 1n Σ
a1 A, +
Σ
(ar - 10------VV/- wx) -o((V((x'), werl)
TElt]
rE(()
-2nL
Σ
A +
Σ
(ar 01 (V)(xx) w. - w
TEJK]
rE(()
< 22L
Σ
a1
A +
Σ
(ar a2 a.- () ||| -
TE
rE(t]
01 + GaG
2T
TE(T]
Here, the first inequality employs the Young's inequality. For the second inequality, we introduce the notation A, := f(x;) fxx)), ), and we follow Lemma B.5, which relates to the smoothness of the function f. In this step, we also set ag = and utilizes the property o² < 201 given that a, = т. The third inequality uses the Cauchy-Schwarz inequality. The last inequality follows the assumption in Eq. (1). It uses the fact that < and A, 2 O, Vt. This step also incorporates the choice of an appropriate learning rate parameter 1/4LT.
20

---

Plugging (A) into Eq. (18), gives us,
D2 + D D Σ
a1 S
Σ
O1 A, +
a+11ET11
(19)
2T
2mj
TE(T]
TEld
Lemma B.6 (Lemma C.2 in Levy [2023]). ler (Athe(T)) ( (BeheeTT be sequences of non-negative elements, and assume that for any < T,
A $ BT +
Σ A
2T
(E[T]
Then the following bound holds,
Ar S 2BT
In the next step, let us define two terms: A, a1 [f(x)) f(x)) and B, == D² 2n
+ a2G
D Eree or B| Note that the series {B.}, forms a non-decreasing series of non-negative values, implying Br for any [T]. As result of Eq. (19), have that A, BT + य Erem Ar.
Leveraging Lemma B.6, Eq. (17), and acknowledging that 01.7 = ) as ar = t, it follows that:
2
B[f(xT) - [(x)] -
T2 TT B
D
2G D
2D
Σ
+
T
T
T
LE|T]
D
GD
D
00
Σ
VtovI+
max + miz DL
T2
T
T
1E|2
D
G
Dōv1+
mcx
max D Da
00
T2m
VT
where p mar = 1 T EiE[T] Tt
maa, Finally, choosing the optimal
1) I/ ATI gives us:
E[f(xT) - f(x') T.DDyymar max
(
V G'D
Dē Dā mas
+
T
VT
B.3.1
Proof Lemma B.4
Proof of Lemma B.4. The update rule w w,+1 1lx(w, - na,dd) can be expressed as convex optimization problem within the set K::
W,+1 11x (w, dd
arg min |/w,, - ma,, 2, w|1 wek
arg min (a, (d,, w www,)) + 2n
w w, 112]
wek
Here, the first equality is derived from the definition of the update rule, the second stems from the property projection, and the final equality obtained by reformulating the optimization problem in way that does not affect the minimum value.
Given that w,+1 is the optimal solution of the above convex problem, by the optimality conditions, we have that:
a- + (W++1 -W>), Wr+1 20, V.e..
21

---

Rearranging this, summing over t 2 1 iterations, and taking w x", we derive:
Σ 7E(0]
ar (dr, w,+1 - x*) 5 -
[ W++1 W++1 - x")
17 rEl(
1
(|/w> [| W|++ -x11 |w, wr+1ll3)
21
rE((]
|| - x 112 - - -x-12--
Σ rE(1
||, wr+1ll
21j
D
w,
w
2n
21
TE
The first equality equality is achieved through algebraic manipulation, and the last incquality follows the assumption in Eq. (1).
B.3.2 Proof of Lemma B.5
Proof of Lemma B.5.
Lemma B.7 (Lemma C.1 in Levy (2023]). let f RRd + R be an L-smooth function with a global minimum x", then for any IRd we have,
[ 2 f(x)))
Let us define the function = we have the gradient inequality f(x) (vxx2 x*). which implies h(x) 2 0. As
x Due to the convexity of f(x).
f(xx) = 0, this implies that x" is the global minimum of h. Applying Lemma B.7, gives us.
[VS(x) [(xx) (x)]
(x)( - (T.((()) f(x*))
- (V
where last inequality holds due to the convexity of f, which implies that (Vf(x)) 20. 0
C Robust Aggregators Analysis
C.1 Weighted Robust Aggregators
C.1.1 Weighted Geometric Median (WeightedGM)
The Weighted Geometric Median (WeightedGM)) is aggregation method that seeks point mini- mizing the weighted sum Euclidean distances to set of points. Formally, for given set points {x, he and corresponding weights [s) the WeightedGM aggregator is defined as follows:
WeightedGM arg min Σ s:lly x;
YER (e(m]
Lemma C.I. Let & be WeightedGM aggregator then & is (cx, we-weihte robust with ex 2
(1 1-2X
22

---

Proof.
|| X6l = x
Eieg 81
8:X;
iE9
1
5
81 ||8 x:|
L
81
169
1
8/ | x;||
8 || x;
Eieg
Eieg 8: iEB
iE(m]
1
8/ [8g x1,|
Σ iEB
84 //1/x x,|
Zieg
$1
Dieg
velml
1
81 ||8g x:|l
|Xg x:|
Σ 8: |
x;
Eieg 8t
Σ 81 iEB
Eveg 8t iEB
84 ||8g x;1l + Eveg
|8g-
&1
Eveg 81
81
iEg
iEB
X
81 ||g
x;11
Xg x||
Eveg 84
The first inequality leverages Jensen's inequality. The second inequality follows the WeightedGM definition. The third is derived using the following triangle inequality: |[gg x,1l S ||gg
x|| + | x,||- The final inequality is based on the assumptions that Eies 8; As1.m and
Eieg 8, 2 (1 1)
By rearranging, we obtain:
|| x-xxxll S
(
A
8g
-xi|
1-2X 2A
Eieg 88
$Eg
Taking the square of both sides and applying Jensen's inequality gives us:
||*
x
1 1 22
A
Σ
||g
xx,1
Eieg
Si iEg
Taking the exception of both sides gives us the following:
A
2
E|ix Xg 1 <
1 +
p²
22
C.1.2 Weighted Coordinate-Wiic Median (WeightedCWMee))
The Weighted Coordinate-Wi Wise Median (WeightedCWMed) is an aggregation technique that operates on a per-coordinate basis, For a given set of weights { the WeightedCWMed is computed by independently finding the weighted median of each coordinate across all points. Formally, for the hth dimension, the WeightedCWMMd aggregator is defined as:
data points {x.)m and corresponding
WeightedCWMedI
(eiighedMMedian((([))13333 ((s))))))
where [x]ı is the tt element of vector and the WeightedMedian is defined as follows: given the elements {xi,..., xm } of each dimension are sorted in ascending order and their corresponds weights (si,..., the weighted median is the element Xj+, where j* is determined by the condition:
j E arg min
8;
[[(m]
E mm)
23

---

If there exists value j such that:
Σ
Σ
8 2
sebi
Then, the WeightedMediaa is the average of the j-th and (j + 1)-th elements:
WeightedMedian X, + x
Here, we extend the theoretical guarantee of the Coordinate- Wise Median (CWMed) to its weighted version, following the procedure in Allouah al. [2023].
Lemma C.2. Let Aw Rd Rd be a weighted coordinate-wise aggregation function. Given
set of points {x; 1im and corresponding weights 1:121 this function incorporates d real-valued
functions A ....... Ad, where each [Ax {st)=))) = (H ([=))))))) for
each 1 E [d] A is (cx, AJeeghttd robust that satisfies:
E | ((xx:) ([s.k (xol//
CA
Σ ie0
S |x,
Eieg 8
Then Aw is (cx, A)-weighted robust.
Proof. Since A is a coordinate-wise aggregator, it applies the same aggregation rule across each dimension. Therefore.
1s xgl1²
Σ
(
([ss)));1 - [xglx]
AEId]
Given that each A for [d]. is (cx, A) weighted robust that satisfies:
E (1[x) Mi ([s:)<]
[Xc]a]
s,E
[xi]a [8g]a]2
Eieg 8t
ieg
We can express the overall aggregation function Aw as follows:
E (f[x {[s)))m))
[xgla| Σ
s [xx]k
[xg]<|
iigg
84 iEG
kE|d]
kEld
CA
8 E
[xi]a=
[xgla| 2
Eieg
iEG
kE|d
CA
E ||x;
Xg l|
Eieg
8i
iEg
< cxp²
where the first inequality derived from the assumption stated this lemma. The second aligns with the definition of (cx, weihhte robust as detailed in Definition 3.1.
Lemma C.3. Let x be WeightedCWMMd aggregator then & is (cx, A) wweighted robust with cx (I+ 1-2X
Proof. In the context of the tthh coordinate, [WeightedCWMed]j functions equivalently to Weight- edGM for dieenninnionnl case. Consequently, each coordinate of the WeightedCWMed aggregator
2
is (cA. weiihhet robust with сλ = [ + 2 as established in Lemma C. Furthermore, since the WeightedCWMed functions coordinate-we wise basis, it follows from Lemma C.2 that the entire
WeightedCWMed aggregator is (cx, w)-weighted robust with Cx = (1 1-2X
2
24

---

C.2 Proof of Lemma 3.1
Proof of Lemma 3.1. We denote y; :=x; - Xu. Eg == Eieg Si, Es := Lies Si, Es == Lies 8,
and E.m= Die(m) 88. Recall that Fig 2 (1 A)5m. and big = =1 -m) (Alg. 1).
& - Xg
1 Ls
Σ
8:x; - X5
iES
1
= X0
Xg
+
xx(x; - xo)
Σs
iES
Σ
Sx x0) + Es iES
Σ
8;(x; -xo)
Eg iEG
Σ s:ys
S +
Eg iEG
Es iES
Σ
Σ s:Y: +
1
Σ siyi
8:Y:
Es
Eg
Σs
Σs
1E9
iES
1
1
Σ
1
Σ
Σ
s
8 +
s:y;
Eg
Eg
Σs
Es NESYI
IEG
iEgYS
Eg Σs
Σ
1
Σ
1
Σ s.ys
stY:
s
+
ΣgΣg
Σs
Es
icG
iE
Taking the squared norm of both sides, we obtain:
||x - Xg|12
Eg Es
Σ
8,y
1
Σ
&
+
1
Σ
siYi
Eg
Eg
Σg
EEG
iEg'S
BESYg
Eg Σg
< 3
Σ
s:Yi
+3
Σ
syy
+3
s.y;
Es V
Σs
EEG
sES,g
(Vg- Es>
2
3Σ
LiSSig 81
3 > iEgis 83
< <ggg
8:
s:|1y:112
8: 1111y
+
8: b|y::
Eg
Σ
VES
iEg/S
(20)
where the first incquality follows the inequality ||a+b+c|| م 33/aa|/+3|b//+33]ll Va. b, c R² and the second follow Jensen's inequality.
Note that,
Es Eg
2
Σ.m. Eg (1 2)
2
EgEg
EgEg
Amm ΣB
A
2
A) Eg
21
2
Σg
2
(21)
23
where the first inequality holds because Eg S AEn and Esg = (1 - -)) The second inequality
follows from the fact that 1 - x 2 1/2, and the last since X < 1/2.
25

---

In addition, we have that,
Eiegig 8;
Eiesug Lieg
Σ
2
--))m
AEm
AΣm
(1 -
4X
Σm
41
(22)
Eg
where the first inequality follows the facts that S SUg C [m], fsx 2 0) and Eg 2 (1 X)Em. The second inequality is based on that À 2 1/2, and the last since Eg S Em. And in similar way.
Eiegrs
41 Eg
(23)
D
Applying Eq. (21), Eq. (22) and Eq. (23) into Eq. (20), gives us,
6A
12X
12A
{ - 1111
silly
s1llya1?+
+
sillyall
2 +
silly:l1?
Eg
Eg
Eg
iEgis
12A
18A
8:||x:
xol12
si
[|||;
xol1?
Σgg
Σg
where the latter holds since Eiegis sillyill2 S Exeg 8: 1111y.112.
Next, we define:
S UiE
iES
seg
- Note that =
= |X
1 We'll show that there exists an injective
function & St G + S** such that, vi E St g+, [ x 2
| - -xoll is satisfied. This follows from selection of S, which consists of the closest elements {xi)ies to xo (see Alg. 1), and from:
G-
Σ S -
S
Σ
Σ iEG
8 <
Σ 1
s 15
SESIg
iES
iEg'.
where the last inequality follows that Eies
Eieg 8, = (1 - A)Σm
Eg 5.
26

---

Thus,
||x - xzll² -
12X
Σ
8:||x; x
8:
x0l1²
18A
8i X; - xo11 -xo1
Eg
Σg $E9
1E8
12X
18A
Σ
|X xoll
8/ si||x: Xo /12
Eg
Σg
ig"
iEg
12X
181
Xi((i))
X
11?
+
8:||x: - -xol
Eg
Eg
1E0
12X
|
X 11
181
Σ
8:
||2 xoll /|
Dg
Eg
$E9*
SE9
12X
8: b:||x: - xol1 +
18A
Σ
8i||x; - xol1
Eg
Σg
iEg
30X
Σ
s; 31||x; - xoll2
Dgg
iEG
60A
60A
8:|1x: - x
+
81||8g - xoll3
Eg
Eg
iEg
.69
where the second inequality follows from the definition of the injective funetion $ The third inequality justified by the fact that Eieg-,.- I|y:ll S Eieg- lly: Finally, the last inequality leverages the property ||a + bl|² 2||a||2 2||b which holds Va, b E Rd.
Taking the expectations of both sides gives us the following:
60A
601
B| - xol12 -
s
x - xzl12
s,EE| X - xol1
Eg kEg
Σg iEg
- p 2 + 60Acpp2
60 + cx)p²
where the last inequaility stems from Def. 3.1.
D Experiments
D.1 Technical Details
Datasets. We simulated over the MNIST [LeCun et al., 2010] and CIFAR-10 10 [Krizhevsky et al., 2014] datasets. The datasets were accessed through torchvision (version 0612).
MNIST Dataset. MNIST is widely used benchmark dataset in the machine learning community, consisting of 70,000 grayscale images of handwritten digits (0-9) with resolution of 28x28 pixels. The dataset is split into 60,000 training images and 10,000 test images.
CIFAR-10 Dataset. CIFAR-10 is widely recognized benchmark dataset in the machine learning community, containing 60,000 color images categorized into 10 different classes. Each image has resolution of 32x32 pixels and represents objects such as airplanes, automobiles, birds, cats, and more. The dataset evenly split into 50,000 training images and 10,000 test images.
Imbalanced Arrival Scenarios. We simulated two types of imbalanced arrival scenarios:
Proportional Arrival Probability: The probability of arrival for the i-th worker in the honest group was set proportionally to i/ Ejeg j. ensuring that workers with higher indices had a higher chance of arriving. The same distribution method was applied to Byzantine workers.
Squared ID Arrival Probability: In a more skewed scenario, the arrival probability was pro- portional to the square of the worker's ID, i.e., 82/ J². This setup further accentuated the imbalance by favoring workers with larger IDs.
27

---

Parameter
MNIST
CIFAR-10
Model Architecture
C, ReLU, MaxPool(2X2), Con,(20,50,5), ReLU, MaxPoo((222),, FC(800->50) BatchNorm, ReLU, FC(50-+10)
20,5,,,20,5), ReLU, (2xx),l( Conv(20,50,5),
ReLUU, MaxPool(2x2),, FC(1250-550) BatchNorm,
ReLU, FC(50->100
Learning Rate
0.01
0.01
Batch Size
8
Data Processing & Augmentation
Normalzee(man=((01100 std=(0.3081))
RamdomCroo(size=22,
padding=2).
Random//HorzzonaaalPipqp0003;;;
(ormmalize(meam-:00444444,
0.4822, 0,4465), std=(0.2023, 0.1994, 0.2010)
Table 2: Experimental Setup for MNIST and CIFAR-10
For simplicity, Byzantine workers were introduced after a fixed number of iterations, controlled by a parameter A. However, it is worth noting that when Byzantine iterations concentrated, they can cause significant performance degradation. Such patterns can lead to increased delays for honest updates, ultimately affecting the overall convergence of the algorithm.
We optimized the cross-entropy loss across experiments. For comparisons, we configured y -DGGG with fixed parameters = 0.1 and 3 = 0.25. This was tested against Standard SGD, and Momentum-basee SGD, where the momentum parameter was set 0.9 as recommended by Karimireddy et al. [2021].
Optimization Setup.
Attack Simulations. We simulated four types of attacks to evaluate the robustness of approach:
1. Label Flipping [Allen-Zhu al., 2020]: The labels of the data were flipped incorrect values, by subtracting the original labels from 9.
2. Sign Flipping [Allen-Zhh et al., 2020]: The signs the workers' output were flipped.
3. Little [Baruch et al., 2019]: Adapted from the synchronous case. It computes the maximum allowable deviation 2max based on iterations count rather than the number workers. Then, it perturbs the honest updates by subtracting the product of the weighted standard deviation and 2max from the weighted mean of the honest updates.
Byzantine_updee _uttttteeepdeeeeeeeeee weighted_ weighted_mean (neenhoones_mmmmeuuus))
[tggheed_tt(hhonss_____ satiressssmmmeuummmsmm 2max
4. Empire [Xie et al., 2020a]: Adapted from the synchronous case. This attack scales the weighted mean of the honest momentums by factor in the negative direction,
srrantine_updatee = -- weighted weighted_mman(honnee (naatboones_mmmmentmm)
In the two latter attacks, the mean and standard deviation calculated coordinate-wise with respect to weights, setting 0.1.
AnyTime Update Formulation. Regarding the AnyTime update, defined as
caw 116-1 we employed a momentum- based formulation that equivalent to the standard Any AnyTime update. Specifically, we updated the model parameters according to the formula:
ond
X = w. + (1 (11-)))xe- x)xx-1
where Yt difined as 7h. cirt
_t_ By setting a. Ca with C > 0 being constant, derived
that Ø. and remains consistent across all time steps 2 1.
For more details, please visit our GitHub repository.'
www./a/aan9///aaaaaaaaaaaaaaaaee http:///h.t...oooaa..///////oona tolerat-mn
28

---

D.2 Experimental Results on MNIST
[lppnng
0.:00
0.40
0.5
oemed
soited
Scnioon
Strbbon
Dontben
Figure 5: MNIST. Test Accuracy of Weighted vs. Non- Woi-Weighted Robust Aggregators. This secnario involves 17 workers, including 8 Byzantine workers, The arrival probabilities of workers are proportional to the square of their IDs, with À 0.4. We employed y -SG in this sctup, Left: label flipping attack. Right: sign flipping attack.
Mltpping Cimimeddd
Ersprr (M-CWmed
Empre wiIFA
0.913
0.200
11:00
0.03
0.00
0.000
000
0.755
0.58
0.800
0.00
0.25
0.255
1ogt/wt.. Jlc Way 3mm
1307
Weg rogee ni meytolddt
veptool/te naditel.ate m
Figure 6: MNIST. Test Accuracy Comparison of Weighted Robust Aggregators With and Without w CTMA. This scenario involves 9 workers, with very fast Byzantine worker, and workers' arrival probabilities proportional their IDs. We used the SSD in this scenario. On the left we have label flipping 0.4) and littl (A 0.3) attacks. On right we have an empire (A 0.4) attack.
Sign Flippnn 1 OWmed
Sign Fiipingg
Label taping Io OWimed
Latel Flipping
09915
01911
oree
0.03
8.30
0:00
0.23
mungg
Figure 7: MNIST. Test Accuracy Comparison Among Different Optimizers. This scenario involves workers, with very fast Byzantine worker, À 0.4, and workers' arrival probabilities proportional their IDs. Left: sign flippigg Right: label flipping.
29

---

NeurIPS paper checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected generalize to other settings.
It is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution low or images are taken low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should diseuss possible limitations of their approach address problems of privacy and faireess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
30

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model is limited some way (e.g.. registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
31

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that paper does include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips...
healiic/gudes////e Saaieees/ooeSSumiiieeee ssiissolccyyyoooooooccccooooiipi for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
wttpppblcc/ggcieecceceeecoocecce Soniedee//CodSuummii sssisssiinii assionoliccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental
material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main
claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar the standard deviation or the standard error of the mean.
32

---

is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / /ttp///eerrp..eeeee//ee/ee ct.ppp.cc......oooo..op.
Answer: [Yes]
Justification: we ensured that our paper conforms with the NeurlPS Code of Ethics
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special considera- tion due laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: we do not foresee any special societal impact that arise due work
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance). fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it legitimate to point out that improvement in the quality of generative models could be used to generate
33

---

deepfakes for disinformation. On the other hand. it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
34

---

Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: work does not involve crowdsourcing research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "l4UdXfR1wg", "reviewer": "Reviewer_yddM", "summary": "The authors investigate asynchronous training of convex models based on a parameter server in the Byzantine failure setting, evaluating their method on MNIST", "questions": "- Which convex model did you implement and are you evaluating in Section 5 and Appendix D?", "limitations": "- The proposed method and associated guarantees do not apply to non-convex models", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Author's method achieves the optimal convergence rate, which they claim prior work in asynchronous Byzantine ML has not achieved.\n- Authors extend the standard measure considered in the Byzantine failure literature (number of Byzantine workers) to a setting more natural for asynchronicity by considering the number of Byzantine updates", "weaknesses": "- Authors do not motivate scenarios in which asynchronous convex optimization is relevant/applied in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:\n                   \nRegarding the **Convex Setting**:                 \nThe convex case is important for two main reasons:\nIt captures classical ML problems like linear and logistic regression, and it serves as a theoretical testbed for analyzing and developing novel ideas and algorithms in various machine-learning scenarios. These new algorithms often induce novel heuristics that are very useful in the context of general ML problems, including non-convex ones and specifically in Deep Learning scenarios.\nIndeed, this approach is prevalent and has led to many important contributions in ML. Two prominent examples are the well-known Adagrad and Adam algorithms, which were conceived and analyzed under the convexity assumption. Other influential examples are the many works on convex synchronous/asynchronous training, and works on Byzantine-resilient algorithms for convex problems, see e.g.:\n\n- Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018.\nhttps://arxiv.org/pdf/1803.08917\n- Minghong Fang, Jia Liu, Neil Zhenqiang Gong, and Elizabeth S Bentley. Aflguard: Byzantine robust asynchronous federated learning. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 632–646, 2022.\nhttps://arxiv.org/pdf/2212.06325                                                    \n\nFor the asynchronous Byzantine problem, the convex framework enables the development of a more intuitive and naturally weighted scheme.  It provides a foundational basis for extending these findings to non-convex settings, which is a challenging and ongoing research area. In fact, extending our weighted scheme to the non-convex setting requires less straightforward analysis and necessitates a careful adaptation to accommodate the stochastic error inherent in non-convex scenarios. For further details, please refer to lines 259-271 and the Future Work section of our paper.\n\nPlease note that in our work, we empirically examine the ideas developed in the non-convex setting, specifically focusing on non-convex deep learning problems. Our empirical study demonstrated the practicality and usefulness of our approach in deep learning scenarios, complementing our theoretical findings. Additionally, we conducted further experiments using the CIFAR-10 dataset to validate the effectiveness of our methods in a more complex, non-convex machine learning task.\n\n\nRegarding the **Experiments Setup**: \n\nAs with other optimization algorithms like ADAGrad, which were analyzed in convex settings and\nemployed in non-convex scenarios, we demonstrated the performance of our approach in a non-convex context. We used a 2-layer convolutional network designed for the MNIST dataset. The network includes two convolutional layers (20 filters and 50 filters, both 5x5), followed by ReLU activation and 2x2 max pooling. This is followed by a fully connected layer with 50 units, batch normalization, and a final fully connected layer with 10 units. Similarly, for the new CIFAR-10 experiments, we applied an analogous architecture. \n\nThank you for highlighting this. We will add further details about the setup and implementation of our experiments in the final version of the paper to enhance the clarity of the experimental configuration.\n\n\n- ADAGrad Paper:\nDuchi, John, Elad Hazan, and Yoram Singer. \"Adaptive subgradient methods for online learning and stochastic optimization.\" Journal of machine learning research 12.7 (2011). https://www.jmlr.org/papers/volume12/duchi11a/duchi11a.pdf", "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": "MZ7XzmF9ip", "reviewer": "Reviewer_6iKY", "summary": "The paper introduces the Asynchronous Robust μ^2-SGD algorithm, designed to address the challenges of Byzantine-robust training in asynchronous distributed machine learning (ML) systems. The method extends the standard μ^2-SGD by incorporating a robust weighted aggregation framework that mitigates the effects of delayed updates and faulty, potentially malicious contributions from distributed workers. This novel approach claims to achieve an optimal convergence rate for the first time in an asynchronous Byzantine environment, enhancing fault tolerance and performance optimization in such systems.", "questions": "See weakness section.", "limitations": "No potential negative societal impact.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- **Innovative Approach to Fault Tolerance**: The paper successfully introduces a novel robust aggregation framework that extends existing methods to accommodate asynchronous dynamics and Byzantine faults. This framework allows for the application of robust aggregators and meta-aggregators to their weighted versions, effectively handling the challenges posed by asynchronous updates and unreliable data sources.\n- **Clear Presentation and Insightful Analysis**: The paper provides a clear presentation, offering good insights into the differences between synchronous and asynchronous settings, which is crucial for understanding the impact and novelty of the proposed method. The authors provide detailed proofs, and the preliminary results presented look promising, indicating potential for significant contributions to the field.", "weaknesses": "While I am not an expert in this specific area of asynchronous Byzantine environments, I recognize the significant value this paper offers to the NeurIPS audience. Its innovative approaches to fault tolerance in distributed ML systems are both relevant and timely (such as in the distributed Federated learning where updates can be fuzzy or even malicious). Nevertheless, there are a few areas where further clarification could enhance the paper's impact and applicability.\n\n- **Assumptions on Byzantine Behavior**: The paper introduces an interesting perspective by suggesting that it is more natural to consider the fraction of Byzantine updates rather than the fraction of Byzantine workers in asynchronous environments. While this approach aligns well with the dynamic nature of such systems, it raises questions about whether alternative, potentially simpler solutions could be explored. For instance, could the parameter server utilize mechanisms like monitoring update frequencies to identify and mitigate the impact of Byzantine workers? Further exploration into whether these alternative approaches might offer comparable robustness with potentially reduced complexity could enrich the discussion and provide a more comprehensive understanding of the trade-offs involved.\n- **Impact on System Metrics**: The paper could benefit from a discussion on how the proposed method impacts other critical system metrics, such as the additional memory consumption required by the parameter server and the overall impact on training speed. Understanding these implications could help in assessing the practical viability of implementing this method in real-world systems.\n- **Temporal Distribution of Byzantine Updates**: A minor yet intriguing question arises regarding the assumption that Byzantine updates are uniformly distributed over time. What if these updates are not uniformly distributed but are instead concentrated within specific periods? Exploring the effects of such scenarios could provide deeper insights into the robustness of the proposed method under different types of Byzantine behaviors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:\n\nRegarding the **Assumptions on Byzantine Behavior**: *“... it raises questions about whether alternative, potentially simpler solutions could be explored”*\n\nThis is a very good question. Our goal was to develop the simplest approach for which we could draw provable guarantees for the general Byzantine asynchronous setting, and our approach indeed ensures such guarantees.\nIt is an important open question to understand whether a simpler approach can work in this case, and we believe that this is an interesting future direction. \n\nMonitoring update frequencies can potentially assist, for example, in an extreme case where we have a dominant worker who appears more than half times in some of the iterations, then this worker can be identified as an honest worker and might serve as an honest reference for anomaly detection. While this can lead to a simple approach for this specific case, we believe the guarantees will coincide with ours. In less extreme cases, however, relying solely on update frequencies to detect outliers becomes more challenging within the general Byzantine framework. This framework assumes only a majority of iterations are honest, without prior knowledge of additional characteristics of Byzantine updates. The generality of this framework allows us to develop an approach applicable to a wide range of scenarios. Nevertheless, this broad applicability makes it difficult to set definitive criteria for identifying anomalous behavior based on frequency alone. For example, a Byzantine worker could adapt their behavior to mimic honest patterns, making identification more difficult. Leveraging additional prior knowledge might be useful in developing simpler approaches, and this is a future work to investigate.\n\nWe will add this discussion to the final version of the paper.\n\n\nRegarding the **Impact on System Metrics**: \n\nThank you for pointing this out. We will include this discussion in the final version of the paper.\n\nRegarding memory requirement and computational complexity, our approach scales similarly to standard approaches for the synchronous byzantine case. Nevertheless, recall that the advantage of the asynchronous setting is that slow workers may not become bottlenecks in the training process, which enhances overall efficiency and flexibility.\n\nCompared to the asynchronous case without Byzantine workers, the parameter server only needs to maintain memory for a single worker's output along with the global model. However, to ensure robustness against failures, our method requires storing the latest outputs of all workers in addition to the global model. This results in increased memory consumption, which scales with $O(dm)$, where  $m$ represents the workers’ number and $d$ represents the dimensionality of the model. Regarding time complexity, the use of a robust aggregation procedure requires an additional computation (e.g. applying the coordinatewise median aggregator requires an additional  $O(dm\\log(m))$  complexity per round). Note that such additional computation also arises in synchronous Byzantine scenarios. In asynchronous Byzantine-free scenarios, these additional processing costs are absent. \n\nThe additional memory overhead and time complexity is a trade-off for enhanced robustness, as it enables the system to apply robust aggregation rules and more effectively mitigate the influence of Byzantine workers. This trade-off is justified by achieving an optimal convergence rate and an improved performance of the training process in the presence of adversarial behavior.\n\n\nRegarding the **Temporal Distribution of Byzantine Updates**: \n\nWe would like to clarify that our analysis does not assume uniform updates for Byzantine workers. The generality of our framework enables us to handle scenarios where Byzantine iterations are concentrated within specific periods, as long as the majority of iterations are honest, in the sense that $t_{honest}\\geq(1-\\lambda)t, \\forall t\\in[T]$. \n\nIn our experiments, we used a uniform distribution of Byzantine updates primarily for simplicity. However, we acknowledge that concentrated Byzantine iterations can indeed cause severe degradation in performance. Such scenarios can significantly increase the honest delays, potentially degrading the overall convergence. We will include this discussion on the behavior of Byzantine updates and their implications in the final version of our paper.", "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": "jitWA77V6n", "reviewer": "Reviewer_hh1u", "summary": "The paper addresses the challenges of Byzantine-robust training in asynchronous distributed machine learning systems. The authors propose a novel weighted robust aggregation framework to mitigate the effects of delayed updates and enhance fault tolerance in such environments. They incorporate a recent variance-reduction technique to achieve optimal convergence rates in asynchronous Byzantine settings. The methodology is validated through empirical and theoretical analysis, demonstrating its effectiveness in optimizing performance and fault tolerance.", "questions": "* While your theoretical analysis is robust, have you identified any discrepancies or limitations when translating these theoretical results into practical implementations? How sensitive is the proposed methodology to the assumptions made (e.g., bounded delays, fraction of Byzantine updates)? What happens if these assumptions are violated in real-world scenarios? An additional experiment should help.\n* How does the proposed framework scale with an increasing number of workers? Either increase or decrease Byzantine workers. Are there any scalability issues or bottlenecks that need to be addressed?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The introduction of a weighted robust aggregation framework adapted to asynchronous settings is a significant contribution. This innovation allows for more efficient handling of Byzantine faults, which are critical in distributed systems.\n* The paper provides both empirical and theoretical validation of the proposed methodology. This dual approach strengthens the credibility of the results and demonstrates the practical applicability of the proposed techniques.\n* Achieving an optimal convergence rate in asynchronous Byzantine environments is a noteworthy accomplishment. The incorporation of a recent variance-reduction technique adds further value to the research.\n* The paper provides a thorough review of existing approaches to Byzantine-robust training, both in synchronous and asynchronous settings. This contextualization helps in understanding the advancements made by the current work.", "weaknesses": "* __Complexity of Methodology__: While the proposed framework is innovative, it is also quite complex. The introduction of weighted aggregators and the double momentum mechanism might be challenging for practitioners to implement and integrate into existing systems.\n* __Limited Practical Examples__: The paper lacks of sophisticated experiments to demonstrate the effectiveness of the framework, at least to show it in practical ways. \n* __Dependency on Assumptions__: The effectiveness of the proposed method relies heavily on several assumptions, such as bounded delays and the fraction of Byzantine updates. These assumptions might not hold in all practical settings, potentially limiting the method's applicability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:\n\n\nRegarding the **Complexity of Methodology**: \n\nWhile our approach may not be trivial to code, conceptually, it can be implemented as a combination of several quite simple modules, which simplifies the implementation. And indeed, this is how we translated our method into a rather simple Python code.  To assist in implementing our methods, we will share our code with the community, which includes a detailed implementation of the proposed framework. It is worth noting that many widely-used optimization algorithms, such as the Adam optimizer, also involve intricate components (momentum, and per-feature learning rate) but are popular in practice due to their effectiveness. \n\nReferences:\n- Adam paper: Kingma, Diederik P., and Jimmy Ba. \"Adam: A method for stochastic optimization.\" arXiv preprint arXiv:1412.6980 (2014).\n https://arxiv.org/pdf/1412.6980\n- Adam Pytorch documation: https://pytorch.org/docs/stable/generated/torch.optim.Adam.html\n\n\nRegarding the **Practical Examples**: \n\nWe have conducted additional experiments using the CIFAR-10 dataset, in addition to our earlier experiments on MNIST. These experiments further validate the robustness and performance of our proposed methods in more complex and diverse settings.\n\nThe results from the CIFAR-10 experiments align closely with those observed on MNIST, showcasing the consistency and effectiveness of our framework across different types of data. We believe these additional experiments provide a more comprehensive evaluation of our approach and highlight its practicality.\n\nRegarding the **Dependency on Assumptions**: \n\nWe would like to clarify that while our analysis assumes a bounded delay model for theoretical analysis, our algorithmic approach *does not* rely on this assumption. This assumption is used primarily to facilitate the mathematical analysis and to derive performance guarantees under controlled conditions. In practice, our method can handle varying levels of delay, including scenarios with significant delays. As demonstrated in Figure 1 of the paper, we tested our approach in a setting with heavy delays, and the results show that it performs robustly even under these challenging conditions.\n\nRegarding the assumption of bounded Byzantine iterations, apart from the weighted CTMA, which relies on knowledge of the parameter $\\lambda$ (the fraction of Byzantine iterations), our approach with weighted double momentum, as well as robust aggregation rules like the weighted geometric median or the weighted coordinate-wise median, \\emph{do not} require knowing the fraction of Byzantine iterations. These methods can perform effectively without this additional knowledge. While knowing the fraction of Byzantine iterations is beneficial for achieving theoretical optimality, our proposed methods can remain robust and practical in the absence of this information.\n\nAdditionally, it is quite standard in the synchronous literature to assume knowledge of the fraction of Byzantine workers or to have a reliable approximation of this parameter. In scenarios where such an assumption is not made, alternative solutions often rely on knowing the bound of the stochastic variance, which can be less practical and more challenging to estimate than the fraction of Byzantine workers. This adaptation to the fraction of Byzantine iterations is intended to be reasonable and practical, given that a parallel assumption is widely accepted in the literature on synchronous systems.\n\n\nRegarding the **Further Empirical Evaluation**: \n\nWe have conducted further experiments for different values of the fraction of the Byzantine iterations and additional experiments on the CIFAR-10 dataset, complementing our existing results from the MNIST dataset. These experiments provide a more comprehensive evaluation of our approach and highlight its practicality.\n\nRegarding the **Scalability of Our Approach**:\n\nThank you for pointing this out. We will include this discussion in the final version of the paper.\n\nRegarding memory requirement and computational complexity, our approach scales similarly to standard approaches for the synchronous byzantine case. Nevertheless, recall that the advantage of the asynchronous setting is that slow workers may not become bottlenecks in the training process, which enhances overall efficiency and flexibility.\n\nCompared to the asynchronous case without Byzantine workers, the parameter server only needs to maintain memory for a single worker's output along with the global model. However, to ensure robustness against failures, our method requires storing the latest outputs of all workers in addition to the global model. This results in increased memory consumption, which scales with $O(dm)$, where  $m$ represents the workers’ number and $ d$ represents the dimensionality of the model. Regarding time complexity, the use of a robust aggregation procedure requires an additional computation (e.g. applying the coordinatewise median aggregator requires an additional $O(dm\\log(m))$  complexity per round). Note, that such additional computation, also arises in synchronous Byzantine scenarios. In asynchronous Byzantine-free scenarios, these additional processing costs are absent. \n\nAlso, it is worth noting that the number of Byzantine workers, whether increasing or decreasing, does not affect the scalability of our approaches for a fixed number of $m$ workers.\n\nOverall, the additional memory overhead and time complexity are a trade-off for enhanced robustness, as they enable the system to apply robust aggregation rules and more effectively mitigate the influence of Byzantine workers. This trade-off is justified by achieving an optimal convergence rate and improved performance of the training process in the presence of adversarial behavior.", "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": "cATrB3CwCl", "reviewer": "Reviewer_y4Tu", "summary": "This work introduces a weighted robust aggregation framework and extends traditional robust aggregators to asynchronous Byzantine environments. By integrating the proposed framework with a recent double momentum mechanism, the authors achieve optimal convergence rates in asynchronous Byzantine ML under the convex setting.", "questions": "While a vast variety of attacks have been designed for the synchronous case, they may not be as impactful in the asynchronous case. While the authors adapt Little and Empire to the asynchronous scenario, are there other attacks specific to asynchronous settings? Can the authors comment on the significance of evaluated attacks in the asynchronous case?", "limitations": "Empirical assessments should be conducted on at least one more dataset to show the effectiveness of the proposed approach. The paper can benefit from restructuring to at least retain important experimental details in the main paper, such as details on the evaluated attacks. Currently, all experimental details have been deferred to Appendix except the name of the dataset.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The authors address an important problem of Byzantine robustness in asynchronous distributed environments.\n- Novel combination of $\\mu^2$-SGD with weighted robust aggregation to achieve optimal convergence rates for the first time. In contrast to existing works, the obtained convergence rate is independent of data dimensionality and matches the rates of asynchronous settings in the absence of Byzantine workers.\n- The paper is well written and well contextualized w.r.t to existing work in both synchronous and asynchronous Byzantine literature.", "weaknesses": "- Empirical evaluations are limited, spanning only a single dataset\n- Currently only convex scenario is considered", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:\n\nRegarding the **Empirical Evaluation**: \n\nWe agree that including experiments on additional datasets would strengthen the empirical validation of our proposed approach. In response, we have conducted experiments on the CIFAR-10 dataset, complementing our existing results from the MNIST dataset. We believe these additional experiments provide a more comprehensive evaluation of our approach and highlight its practicality. Furthermore, we will ensure that important experimental details are retained in the main paper in the final version.\n\nRegarding the **Convex Setting**:     \n            \nThe convex case is important for two main reasons:\nIt captures classical ML problems like linear and logistic regression, and it serves as a theoretical testbed for analyzing and developing novel ideas and algorithms in various machine-learning scenarios. These new algorithms often induce novel heuristics that are very useful in the context of general ML problems, including non-convex ones and specifically in Deep Learning scenarios.\nIndeed, this approach is prevalent and has led to many important contributions in ML. Two prominent examples are the well-known Adagrad and Adam algorithms, which were conceived and analyzed under the convexity assumption. Other influential examples are the many works on convex synchronous/asynchronous training, and works on Byzantine-resilient algorithms for convex problems, see e.g.:\n\n- Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems, 31, 2018.\nhttps://arxiv.org/pdf/1803.08917\n- Minghong Fang, Jia Liu, Neil Zhenqiang Gong, and Elizabeth S Bentley. Aflguard: Byzantine robust asynchronous federated learning. In Proceedings of the 38th Annual Computer Security Applications Conference, pages 632–646, 2022.\nhttps://arxiv.org/pdf/2212.06325                                                    \n\nFor the asynchronous Byzantine problem, the convex framework enables the development of a more intuitive and naturally weighted scheme.  It provides a foundational basis for extending these findings to non-convex settings, which is a challenging and ongoing research area. In fact, extending our weighted scheme to the non-convex setting requires less straightforward analysis and necessitates a careful adaptation to accommodate the stochastic error inherent in non-convex scenarios. For further details, please refer to lines 259-271 and the Future Work section of our paper.\n\nPlease note that in our work, we empirically examine the ideas developed in the non-convex setting, specifically focusing on non-convex deep learning problems. Our empirical study demonstrated the practicality and usefulness of our approach in deep learning scenarios, complementing our theoretical findings. Additionally, we conducted further experiments using the CIFAR-10 dataset to validate the effectiveness of our methods in a more complex, non-convex machine learning task.\n\n\nRegarding the **Attacks Adaptation to the Asynchronous Case**: \n\nThe attacks of Little and Empire are designed to hide under the variance among the workers' outputs. In asynchronous settings, delays can increase this variance, providing an opportunity for Byzantine workers to blend in more effectively with honest outputs. Therefore, we believe that these attacks also may be effective in the asynchronous setting. Moreover, we have adapted these attacks to directly tackle the weighted robust aggregation rules that we utilize in our algorithmic approach, thus making them more comparable to the synchronous case. Nevertheless, the exploration of attacks specific to asynchronous settings is still underexplored. Further investigation into asynchronous-specific attacks is necessary to better understand their impact.", "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": "F1D9XmMNQP", "reviewer": "Reviewer_ApUX", "summary": "The paper address the challenges of Byzantine-robust training in asynchronous distributed machine learning systems, aiming to enhance efficiency amid massive parallelization and heterogeneous compute resources, by introducing a novel weighted robust aggregation\nframework.\nQuantify the difficulty in asynchronous scenarios, by considering the number of Byzantine updates, which is more natural than the standard measure of number of Byzantine workers.\nIdentify the need to utilize weighted aggregators rather than standard ones in favour of asynchronous Byzantine problems. Towards doing so, they extend the robust aggregation framework to allow and include weights, and develop appropriate (weighted) rules and a meta-aggregator. Achieving Optimal Convergence: They incorporate weighted robust framework with a recent double momentum mechanism, leveraging its    unique features to achieve an optimal convergence rate for the first time in asynchronous Byzantine ML.", "questions": "The paper introduced a novel weighted robust aggregation framework to address the challenges of Byzantine-robust training in asynchronous distributed machine learning systems, but there is no detailed explanation on how the weight coefficients of the  framework are calculated.", "limitations": "The author did not discuss its limitations in the paper.\nThis paper's work generally does not bring the potential negative social impacts, including privacy issues, algorithmic biases, and the risk of technology abuse.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a new solution for Byzantine robust training in asynchronous distributed machine learning systems, with rigorous research methods and reliable experimental results.\nThe paper has a reasonable structure, coherent logic, and clear expression.\nThe research findings have significant implications for asynchronous distributed machine learning.\nThey incorporate weighted robust framework with a recent double momentum mechanism, leveraging its unique features to achieve an optimal convergence rate for the first time in asynchronous Byzantine ML.\nThey adopts a method similar to attention mechanism, assigning different weights to different parts.", "weaknesses": "The experiment is not sufficient, why not compare it with the weighting methods mentioned in the article.\nThe paper quantified the difficulty in asynchronous scenarios, by considering the number of Byzantine updates, which is more natural than the standard measure of number of Byzantine workers, but the experimental results did not prove this point.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We wish to address some points raised to provide further clarification and insight into our work:\n\nRegarding the **Weighted Approach Experiment**: \n\nWe would like to clarify that we addressed the comparison with weighting methods in Figure 2 of our paper. This figure presents a comparison between weighted and non-weighted robust aggregators, demonstrating that the weighted approach outperforms the non-weighted approach, which is equivalent to using the fraction of Byzantine workers.\nAlso, we have conducted further experiments for various values of the fraction of Byzantine iterations with a fixed number of Byzantine workers to evaluate the impact of the fraction of Byzantine iterations. Our findings demonstrate that as the proportion of Byzantine iterations increases, there is a degradation in the training performance. You can see this in Figure 4, in the experiments that we attach in the pdf for the rebuttal.\n\nRegarding the **Weight Coefficients**: \n\nThe weight coefficients in our framework are determined based on the total number of updates of each worker, a factor known in an asynchronous system (see lines 259-267 and Algorithm 2). These weight coefficients align elegantly with the asynchronous dynamics by prioritizing workers with more frequent updates. \n\nRegarding the **Limitations**: \n\nThank you for pointing this out. We will include this discussion in the final version of the paper.\n\nThe paper does not introduce additional negative social impacts beyond the standard Byzantine synchronous settings. In fact, our work enables us to enhance the robustness of asynchronous training. \n\nIn terms of memory consumption, asynchronous systems without Byzantine workers typically require the parameter server to maintain memory for a single worker's output along with the global model. However, to ensure robustness against failures, our method requires storing the latest outputs of all workers in addition to the global model. This results in increased memory consumption, which scales with $O(dm)$, where  $m$ represents the workers’ number and $d$ represents the dimensionality of the model. \n\nRegarding time complexity, the use of a robust aggregation procedure requires an additional computation (e.g., applying the coordinatewise median aggregator requires an additional $O(dm\\log(m))$  complexity per round). Note that such additional computation also arises in synchronous Byzantine scenarios. In asynchronous Byzantine-free scenarios, these additional processing costs are absent. \n\nIt is worth noting that, compared to the synchronous case, our approach scales similarly to standard approaches for the synchronous byzantine case. Nevertheless, recall that the advantage of the asynchronous setting is that slow workers may not become bottlenecks in the training process, which enhances overall efficiency and flexibility.\n\nThe additional memory overhead and time complexity, compared to the asynchronous Byzantine-free scenario, represent a trade-off for enhanced robustness, as it enables the system to apply robust aggregation rules and more effectively mitigate the influence of Byzantine workers. This trade-off is justified by achieving an optimal convergence rate and an improved performance of the training process in the presence of adversarial behavior.", "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:
**Dear reviewers**,

We appreciate your valuable feedback and have included additional results on the CIFAR-10 dataset. CIFAR-10 is a more complex dataset consisting of 60,000 32x32 color images in 10 classes, with 6,000 images per class. These results demonstrate the effectiveness of our proposed approaches in a more complex and challenging scenario.

We have used the same setup as described for the MNIST dataset in Appendix D, with a similar architecture: two convolutional layers (20 filters and 50 filters, both 5x5), followed by ReLU activation and 2x2 max pooling. This is followed by a fully connected layer with 50 units, batch normalization, and a final fully connected layer with 10 units. Our experiments were conducted on an NVIDIA GeForce RTX 3090 GPU using the PyTorch framework. The results were averaged over three random seeds for robustness, with each worker computing gradients based on a batch size of 64.

Our results on CIFAR-10 align with those obtained on the MNIST dataset, confirming the robustness of our proposed approaches and demonstrating performance improvements across different scenarios.

We have also conducted further experiments for different values of the fraction of the Byzantine iterations with a fixed number of Byzantine workers (see Figure 4 in the attached PDF) to demonstrate the impact of the proportion of Byzantine iterations on model performance within our approaches.


Reference:
- CIFAR-10 dataset:
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar-10 dataset. online: http://www. cs. toronto. edu/kriz/cifar. html, 55(5), 2014.

Meta-review: Based on the current reviews and follow-up discussions, I recommend acceptance of this paper. Here is a summary of the main comments on the paper. The strengths outweigh the weaknesses, and the authors tried to address reviewers' concerns during the rebuttal.

Strengths
+ Novel problem formulation considering the interplay between asynchronous aggregation in distributed ML and byzantine robustness.
+ The algorithm is supported by theoretical analysis that gives convergence guarantees.

Weaknesses
- Analysis is limited to convex settings
- Experiments are limited to the MNIST dataset. In the rebuttal, the authors did provide additional results on CIFAR 10.
Decision: Accept (poster)