MixTailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attacks
Authors: Ali Ramezani-Kebrya
Iman Tabrizian
Fartash Faghri
Petar Popovski
Venue: Accepted by TMLR ()

Abstract: Implementations of SGD on distributed and multi-GPU systems creates new vulnerabilities, which can be identified and misused by one or more adversarial agents. Recently, it has been shown that well-known Byzantine-resilient gradient aggregation schemes are indeed vulnerable to informed attackers that can tailor the attacks (Fang et al., 2020; Xie et al., 2020b). We introduce MixTailor, a scheme based on randomization of the aggregation strategies that makes it impossible for the attacker to be fully informed. Deterministic schemes can be integrated into MixTailor on the fly without introducing any additional hyperparameters. Randomization decreases the capability of a powerful adversary to tailor its attacks, while the resulting randomized aggregation scheme is still competitive in terms of performance. For both iid and non-iid settings, we establish almost sure convergence guarantees that are both stronger and more general than those available in the literature. Our empirical studies across various datasets, attacks, and settings, validate our hypothesis and show that MixTailor successfully defends when well-known Byzantine-tolerant schemes fail. 

Published in Transactions on Machine Learning Research (10/2022)
Mix Tailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attacks
Ali Ramezani-Kebrya' Aalborg University
olir@es.aos nou. dk
Iman Tabrizian"
sman.tabrizzamn@@maa.. com
University of Toronto and Vector Institude
Fartash Faghri
faghri@cs.toronto edu
University of Toronto and Vector Institute
Petar Popovski
petarp nou, dk
Aulborg University
Reviewed on OpenReview:
Abstract
Implementations of SGD on distributed systems create new vulnerabilities, which can be identified and misused by one or more adversarial agents. Recently, it has been shown that well-known Byzantine-resilien gradient aggregation schemes are indeed vulnerable to informed attackers that can tailor the attacks (Fang et al., 2020; Xie et al., 2020b). We introduce MixTailor, a scheme based on randomization of the aggregation strategies that makes it impossible for the attacker to be fully informed. Deterministic schemes be integrated into MixTTailor the fly without introducing any additional hyperparameters. Randomization decreases the capability of a powerful adversary to tailor its attacks, while the resulting randomized aggregation scheme is still competitive in terms of performance. For both iid and non-iid settings, we establish almost sure convergence guarantees that are both stronger and more general than those available in the literature. Our empirical studies across various datasets, attacks, and settings, validate our hypothesis and show that MixTailor successfully defends when well-known Byzantine-tolerant schemes fail.
1 Introduction
As the size deep learning models and the amount of available datasets grow, distributed systems become essential and ubiquitous commodities for lcarning human-like tasks and beyond. Mcanwhile, new scttings such as federaled learning deployed to reduce privacy risks, where deep model is trained on data distributed among multiple clients without exposing that data (MeMahan et al., 2017; Kairouz et al., 2021; Li et al., 2020a). Unfortunately, this is only half the story, since in distributed setting there is opportunity for malicious agents to launch adversarial activities and disrupt training or inference. In particular, adversarial agents plan to intelligently corrupt moainin//inferene and tailored attacks (Lamport et al., 1982; Goodfellow et al., 2015; Blanchard et al., 2017; Bagdasaryan et al., 2020; Fang et al., 2020; Xie al., 2020b). Development of socure and robust learning algorithms, while not compromising their efficiency, is one of the current grand challenges in large-scale and distributed machine learning.
through adversarial examples, backdoor, Byzantine,
It is known that machine learning models are vulnerable to adversarial examples at test time (Goodfellow et al., 2015). Backdoor or edge-case attacks target input data points, which are either under-represented or
"Equal contributions.
This work was done while first. three authors were Vector Institute the University of Toronto.

---

Published in Transactions on Machine Learning Research (10/2022)
unlikely to be observed through training validation data (Bagdasaryan et al., 2020). Backdoor attacks happen through data poisoning and model poisoning. The model poisoning attack is closely related to Byzantine model, which is well studied by the community of distributed computing (Lamport et al., 1982).
In a distributed system, honest and good workers compute their correct gradients using their own local data and then send them to a server for aggregation. Byzantines are workers that communicate arbitrary messages instead of their correct gradients (Lamport al., 1982). These workers are either compromised by adversarial agents or simply send incorrect updates due to other causes. In machine learning, Byzzinnie--resllence is typically achieved by robust gradient aggregation schemes (Blanchard et al., 2017). These robust schemes are typically resilient against attacks that are designed in advance, which is not a realistic scenario since the attacker will eventually learn the aggregation rule and tailor its attack accordingly. Recently, it has been shown that well-known reziliete-resilientt gradient aggregation schemes are vulnerable to informed and tailored attacks (Fang et al., 2020; Xie et al., 2020b). Fang ct al. (2020) and Xic et al. (2020b) proposed efficient and nearly optimal attacks carefully designed to corrupt training (an optimal training-time attack is formally defined in Section 4). A tailored attack is designed with prior knowledge of the robust aggregation rule used by the server, such that the attacker has provable way to corrupt the training process.
failures, power outages, and
Establishing successful defense mechanisms against such tailored attacks is a significant challenge. As a dividend, an aggregation scheme that is immune to tailored attacks automatically provides defense against untargeted or random attacks.
In this paper, we introduce MixTailor, a scheme based on randomization of the aggregation strategies. Randomization is principal way to prevent the adversary from being omniscient and in this way decrease its capability to launch tailored attacks by creating an ignorance at the side of the allacker. We address scenarios where neither the attack method is known in advance by the aggregator nor the exact aggregation rule used in each iteration is known in advance by the attacker (the attacker can still know the set of aggregation rules in the pool).
The proposed scheme exhibits high resilience to attacks, while retaining efficient learning performance. We emphasize that any deterministic Byzantine-resilient algorithm can be used in the pool of our randomized approach (our scheme is compatible with any deterministic robust aggregation rule), which makes it open for simple extensions by adding new strategies, but the essential protection from randomization remains.
1.1 Summary of contributions
We propose an efficient aggregation scheme, MixTailor, and provide a sufficient condition to ensure its robustness according to a generalized notion of Byzantine-resllence in non-iid settings."
For both iid and non-iid settings, we establish almost sure convergence guarantees that are both stronger and more general than those available in the literature.
Our extensive empirical studies across various datasets, attacks, and settings, validate our hypothesis and show that Mix successfully defends when prior Byzantine-toleran schemes fail. MixTailor reaches within 2% of the accuracy of an omniscient model on MNIST.
1.2 Related work
Federated learning. Federated Averaging (FedAvg) and its variants have been extensively studied in the literature mostly as optimization algorithms with a focus on communication efficiency and statistical heterogeneity of users using various techniques such as local updates and fine tuning (McMahan al., 2017; Li et al., 2020b; Wang al., 2020b; Fallah al., 2020). Bonawitz et al. (2017); So et al. (2020) studied secure aggregation protocols to ensure that average value of multiple parties is computed collectively without revealing the original values. Secure aggregation protocols allow server to compute aggregated updates without being able to inspect the clients' local models and data. In this work, we focus on tailored training-time time attacks and robust ion schemes.
Non-ldd settings refer settings with heterogeneous data aver workers. In this paper, we focus on non-identical and independent settings.
2

---

Published in Transactions on Machine Learning Research (10/2022)
Data poisoning and model poisoning. Adversaries corrupt traning via data poisoning and model poisoning. In the data poisoning, compromised workers replace their local datasets with those of their interest (Huang et al., 2011; Biggio et al., 2012; Mei & Zhu, 2015; Alfeld et al., 2016; Koh & Liang, 2017; Mahloujifar et al., 2019; Gu et al., 2019; Bagdasaryan et al., 2020; Xie et al., 2020a; Wang ct al., 2020a). Data poisoning can be viewed as a relatively restrictive attack class since the adversary is not allowed to perturb gradient/model updates. In the model poisoning, the attacker is allowed to tweak and send its preferred gradient/model updates to the server (Bhagoji et al., 2019; Bagdasaryan et al., 2020; Wang et al., 2020a; Sun et al., 2021). These model replacement attacks are similar to Byzantine and tailored attacks. In this paper, we focus on tailored training-time attacks, which belong to the class of poisoning availability attacks based on the definition of Demontis et al. (2019). We do not study poisoning integrity attacks (Demontis el al., 2019), and MixTailor is not designed to defend against backdoor or edge-case altacks aiming to modily predictions on a few targeted points.
Robust aggregation and Byzantine resilience. Byyzantine-resilenn mechanisms based on robust ag- gregations and coding theory have been extensively studied in the existing literature (Su & Vaidya, 2016;
Blanchard et al., 2017; Chen et al., 2017; 2018; Yin et al., 2018; Alistarh et al., 2018; El Mhamdi et al., 2018;
Damaskinos et al., 2019; Bernstein et al., 2019; Yin et al., 2019; Yang & Bajwa, 2019; Rajput et al., 2019;
Baruch et al., 2019; Xie et al., 2019; Pillutla et al., 2022; Li et al., 2019; Xie et al., 2020c; Sohn et al., 2020;
Peng & Ling, 2020; Karimireddy et al., 2022; Allen-Zhre et al., 2021; Gorbunov et al., 2022; Zhu al., 2022).
Under the assumption that the server has access to underlying training datasct or the server can control and arbitrarily transfer training samples across workers, a server can successfully output correct model (Xie et al., 2019; Chen et al., 2018; Rajput et al., 2019; Xie et al., 2020c; Sohn et al., 2020). However, in a variety of settings including federated learning, such assumptions do not hold. Alternatively, Yin et al. (2018) proposed to use coordinate-wise median (comod). Bernstein et al. (2019) proposed a variant of signSGD as a robust aggregation scheme, where gradients are normalized before averaging, which limits the effect of Byzantines as the number of Byzantines matters rather than the magnitude of their gradients. It is well known that signSGD is not guaranteed to converge (Karimireddy et al., 2019). Alistarh et al. (2018) proposed different scheme, where the state of workers, i.e., their gradients and particular estimate sequences, is kept over time, which is used to update the set of good workers at each iteration. This technique might be useful when Byzantines send random updates. However, the server has to keep track of the history of updates by each individual user, which is not practical in large-scale systems. Blanchard et al. (2017) proposed Krum, which is a distance-based gradient aggregation scheme over L.2. El Mhamdi et al. (2018) showed that distance-based schemes are vulnerable to leeway attacks and proposed Bulyan, which applies an aggregation rule such as Krum iteratively to reject number of Byzantines followed by a variant of coordinate- wise trimmed mean. Karimireddy et al. (2021) proposed using momentum to defend against time-couples attacks in an iid setting with a fixed set of Byzantines, which is a different setting compared to our work. While most of the existing results focus on homogeneous data over machines, i.e., iid settings, robust aggregation schemes have been proposed in non-iid settings (Pillutla et al., 2022; Li et al., 2019; Karimireddy et al., 2022). Pillutla et al. (2022) proposed using approximate geometric median of local weights using Smoothed Weiszfeld algorithm. Li et al. (2019) proposed a model aggregation scheme by modifying the original optimization problem and adding an Ln penalty term. Karimireddy et al. (2022) showed that, in non-iid settings, Krum's 's selection is biased toward certain workers and proposed method based resampling to homogenize gradients followed by applying existing aggregation rules. Recently, it has been shown that well-known Byzantine-resilien gradient aggregation schemes are vulnerable to informed and tailored attacks (Fang et al., 2020; Xie et al., 2020b). Tn this paper, we propose a novel and efficient aggregation scheme, MixTailor, which makes the design of successful attack strategies extremely difficult, if not impossible, for an informed and powerful adversary.
Allen-Zhn Zhu et al. (2021) proposed a method where the server keeps track of the history of updates by each individual user. Such additional memory is not required for MixTailor. Recently, Gorbunov et al. (2022) and Zhu et al. (2022) proposed robust methods under bounded global Hessian variance and local Hessian variance, and strong convexity of the loss function, respextively. Such assumptions are not required for Mix
Robust mean estimation. The problem of robust mean estimation of a high-dimensional and multi-variate Gaussian distribution has been studied in (Huber, 1964; 2011; Lai et al., 2016; Diakonikolas et al., 2019; Data
3

---

Published in Transactions on Machine Learning Research (10/2022)
& Diggavi, 2021), where unlike corrupted samples, correct samples evenly distributed in all directions. We note that such strong assumptions do not hold in typical machine learning problems in practice.
Game theory. Nash (1950) introduced the notion of mixed strategy game theory. Unlike game theory, our setting, the agents, i.e., the server and adversary do not have a complete knowledge of their profiles and payoffs.
Notation: We use [[[] to denote the expectation and || || to represent the Euclideon norm of a vector. We use lower-case bold font to denole vectors. Sets and scalars are represented by calligraphic and slandard fonts, respectively. We use [n] to denote [1....,n} for on integer n.
2 Gradient aggregation, informed adversary, and tailored attacks
Let w E Rd denote digh-dimensional machine learning model. We consider the optimization problem
1 F((w)
min F(w) WERU
(1)
72
where F; RR + R can be 1) finite sum representing empirical risk of worker or 2) - Ez-D, [e(w; in an online setting where Dj and f(w;2) denote the data distribution of worker i and the loss of model example 2, respectively. In federated learning settings, each worker has its own local data distribution, which models e.g., mobile users from diverse goographical regions with diverse socio-cconomical status (Kairouz et al., 2021).
iteration t, a good worker i computes and sends its stochastic gradient g (wr) with ED, (w,). = (w.). A server aggregates the stochastic gradients following a particular gradicnt aggregation rule AGG. Then the server broadcasts the updated model W to all workers. A Byzanline worker returns an arbitrary vector such that the basic gradient averaging converges to an ineffective model even if it converges. Byzantine workers may collude and may be omniscient, i.e., they are controlled by informed adversary with perfect knowledge of the state of the server, prefect knowledge of good workers and transferred data over the network (El Mhamdi et al., 2018; Fang et al., 2020; Xie et al., 2020b). State refers to data and code. The adversary does not have access to the random seed generator at the server. Our model of informed adversary is described in the following.
2.1 Informed adversary
We assume an informed adversary has access to the local data stored in compromised (Byzantine) workers. Note that the adversary controls the output (i.e., computed gradients) of Byzantine workers in all iterations. Those Byzantine workers may output any vector at any step of training, possibly tailor their attacks to corrupt. training. Byzantine workers may collude. The adversary cannot control the output of good workers. However, an (unomniscient) adversary may be able inspoct the local data or the output of good workers. On the other hand, an informed adversary, has full knowledge of the local data the oulput of all good workers. More importantly, an informed adversary may know the set of aggregation rules that the server applics throughout training. Nevertheless, if the set contains more than one rule, the adversary does not know the random choice of a rule made by the aggregator at a particular instance."
Byzantine workers can optimize their attacks based on gradients sent by good workers and the server's aggregation rule such that the output of the aggregation rule leads to an incffective model even if converges. It is shown that well-known Byzantino-resihhee to such tailored attacks (Fang al., 2020; Xie et. al., 2020b).
aggregation rules with deterministic structure are vulnerable
Thhe exact rule will be determined the time of aggrogation after the updates reccived. We assume the server has source of entropy or secure seed generate random number each iteration, which mild assumption (common in cryptography).
4

---

Published in Transactions on Machine Learning Research (10/2022)
2.2 Knowledge of the server
We assume that the server knows upper bound on the number of Byzantine workers denoted by f and that n 2 2f + 1, which is a common assumption in the literature (Blanchard et al., 2017; El Mhamdi et al., 2018; Alistarh et al., 2018; Rajput et al., 2019; Karimireddy et al., 2022).
Suppose there no Byzantine worker, i.e,, I = At iteration i, good workers compute (g:(w:)). The update rule is given by
W = -
where tp is the learning rate at step & and AGG is an aggregation rule at the server.
Remark 1. To improve communication efficiency, user may opt to update its copy of model locally for iterations using its own. local data and oulput wi. Then the server aggregates local models, updates the global model Wt+1 = AGG((w())a)) and broadcasts the updated model. In this work, we focus on gradient aggregation following the robust aggregation literature. Note that, to improve communication efficiency, a number of efficient gradient compression schemes have been proposed (Alistarh et al., 2017; Faghri et al,, 2020; Benneznn-Kebbrye et al., 2021). Furthermore, optimizing over T challenging problem and, the best of our knowledge, there are very special problems for which local SGD is provably shown to oulperform minibatch SGD. Finally, MirTailor is plug and play scheme, which is compotible with local updating ond fine taming tricks to further improve commanication efficiency and fairness.
2.3 Tailored attacks against given aggregation rule
A tailored attack is designed with prior knowledge of the robust aggregation rule AGG used by the server. Without loss of generality, we assume an adversary controls the first f workers. Let AGG .gn) denote the aggregated gradient under no allack. The Byzantines collude and modily their updates such that the aggregated gradient becomes
= AGG
g/+1 ".).:/........-.........
gn).
A lailored attack is an attack towards the inverse of the direction of g without attacks:3
max A 8 E
subject to g' = AGG( .. .g/.8/1.."" .g))
--=
If feasible, this attack moves the model toward local marima of original objective F(w). This altack requires the adversary to have access to the aggregation rule and gradients of all good workers. In Appendix A. we extend our consideration to suboptimal tailored attacks, tailored attacks under partial knowledge, and model-based tailored attacks, where the server aggregates the local models instead of gradients.
3 Mixed gradient aggregation
It shown that an informed adversary can efficiently and succossfully attack standard robust aggregation rules such as Krum, Mean, and comed. In particular, Fang et al. (2020); Xie et al. (2020b) found nearly optimal attacks, which are optimized circumvent aggregation rules with a deterministic structure by exploiting the sufficiently large variance of stochastic gradients throughout training deep neural networks. Randomization is the principal way to decrease the degree by which the attacker is informed and thus ensure some level of security.
We propose that, at each itcration, the server draws a robust aggregation rule from a set M computationally efficient (robust) aggregation rules uniformly at random. We argue that such randomization makes the design
3Thhis tailored attack shown sufficient against several aggregation rules (Fang al., 2020); however, not necessarily optimal attack.
5

---

Published in Transactions on Machine Learning Research (10/2022)
of successful and tailored attack strategies extremely difficult, if not impossible, even if an informed adversary has perfect knowledge of the pool of aggregation rules. The specific pool we used for MixTailon is described in Section 5. We should emphasize that our pool is not limited to those aggregation rules that are developed so far. This makes it open for simple extensions by adding new strategies, but the essential protection from randomization remains.
Intuitively, MixTailor creates sufficient uncertainty for the adversary and increases computational complexity of designing tailored attacks, which are guaranteed to corrupt training. To see how MixTailor provides robustness in practice, consider the standard threat model in Byzantine robustness literature: The attack method is decided in advance and the server applics an aggregation strategy to counter this attack. This is lavorable for deterministic aggregations such as Krum and comed, but is hardly realistic, as after some time the attacker will find out what the aggregation rule is and use a proper attack accordingly.
An alternative threat model is the aggregation method is known in advance and the attacker applics an attack that is tailored to degrade the chosen aggregation rule. This is realistic case. To counter it, we introduce MixTailor. By introducing randomization in the aggregation method, the knowledge of the exact aggregation rule used in each iteration from the attacker but the attacker still know the set of aggregation rules in the pool. As we prove, randomization is a principled approach to limit the capability of an attacker to launch tailored attacks in every iteration.
assume we can withhold
We propose to use a randomized aggregation rule with M candidate rules where AGG,, is selected with probability 1/M such that an informed adversary cannot take advantage of knowing the exact aggregation rule to design an effective attack. Formally, let Vi(w) g: (w,,)) E Rd be independent random vectors for E [n].* 4 Let G(w, z) denote random function that captures randomness w.r.t. both an honest node drawn uniformly at random and also an example
D; of that node such that B[G((w,))] VV((). Let AGG denote a random aggregation rule, which selects a rule from (AGG,.... AGG J uniformly at random. Let B = (B..... By} denote arbitrary Byzantine gradients, possibly dependent on V/'s. We note that the indices of Byzantines may change over training iterations.
The output of MixTailor algorithm is given by
U(w) = AGG(()(w)) ......,, .B. VV(w))
(2)
where AGG = AGGm with probability 1/M.
In the following, we define a general robustness definition, which leads almost sure convergence guarantees to local minimum of F in (1), which is equivalent to being immunc to training-time attacks. Note that our definition covers a general non-iid setting, general mixed strategy with arbitrary set of candidate robust. aggregation rules, and both omniscient and unomniscient adversary models.
Definition 1. Let w E Rdd Let Vi(w) = 2), E I2d be independent random vectors for [n]. Let G(w,z) denote random function that captures randomness w.r.t. both an honest node i drawn uniformly at ) Let AGG denote a mixed
random and also an erample z ~ D, of that node such that E(G(w,z)] = FF()). aggregation rule, which selects a rule from (AGG,... AGGG,, uniformly at random. Let B = (Bi,... ... BB} denote arbitrary Byzantine gradients, possibly dependent on V₁'s.
A mixed aggregation rule AGG Byzantine-resillen (w) satisfies E[U(w)] > 0 and ([]lU()))II < K, K,E[] 2))l"] for r = 2, 3, 4 and some constand K,. Note that the expectation w.r.t. the randomness in both sampling and aggregation.
The analysis of computational complexity of MixTailor discussed in Appendix A.2.
4n the following, we remove the index for simplicity.
6

---

Published in Transactions on Machine Learning Research (10/2022)
4 Theoretical guarantees
We first provide a sufficient condition to guarantee that MixTailor algorithm is Byzantine-resilent according to Definition 1. Proofs are in appendices. Let
.I, 1. By.... Um (w) = AGGm(WV(W)) ,
VV(())
denote the output of AGG, for m [M]-
Let E Q and 0 < q < M. Let G(w,zi z) denote a random function that captures rondomness w.r.t. both honest node i drawn uniformly at random and also erample DD of that node such that E[G(w,z)) = (w) Let L > 0 denote the Lipschitz parameter of F. Let B denote attack against q aggregation rules such that [w)) VF(w) < <0 for some w and E [q]. Suppose that aggregation rules AGGm 's are resilient against this allack, i.e.,
Proposition 1.
(w)] VF(() (FF) 2 Am >
and (I)l S (,I, 2)]l"] with (w) in (2) for 2,3,4, 4, some constant Kr, and m' E {q + 1, 1. "..",,M,..... Suppose that M is large enough such that
M >
AL
9
minm! Bm
where max4elg supwen [[][U,(W)]Il then the mixed aggregation rule AGG is resilient against any such B.
Proof. See Appendix A.3.
Proposition 1 shows resilience of the mixed aggregation rule when only subset of rules are resilient against an attack no matter how the attack is designed (it could be computationally expensive).
Remark 2. There are possibly tailored attacks agoinst any individual aggregation rule. On the other hand, all aggregation rules are not vulnerable to the same attack. In sum, robustness is achieved as long we have a sufficiently diverse set of aggregation rules in our pool. In (Fang et ol., 2020, Theorem 1), an upper bound is eslablished on the norm of the allack veclor that is tailored against Krum. In (Xie el al., 2020b, Theorem 1), a lower bound is established on the norm of the attack that is tailored against comed. Theoretical results are consistent with the attacks developed empirically in (Fang et al., 2020; Xie et al., 2020b) and conform that Krum and comed are indeed vulnerable to different lypes of allacks, so they are diverse w.r.l. their vulnerobilities. We emphosize that the key element that provides robustness is randomization.
Remark 3. Let v E Rd. To foil the conditions specified in Proposition 1, an adversary should have sufficient computational resources to find an attack (if erists) such that [[ < for i E [g] where should be large enough. Suppose that the adversary has sufficient random samples from each honest client to compute the expectation over the output of an aggregation rule AGG; and has access to an accurate estimate of (W).. An aggregation AGG; is typically a nonconver function of the attack B in Proposition 1. Instead of designing an optimal attack, suppose that the adversary plans to verify an attack, which is a computationally simpler problem. By verifiontion, we mean computing the output of AGG; under an allack and computing the sign of [W)] VF(W). The verification runtime increases monotonically as q increases. We note that due to noncowerrity of baseline aggregation rules such as comed and Krum, we are unaware of any polynomiaal time algorithm with provable guerantees to efficiently corrupt multiple aggregation rules at the same time.
In Appendix A.4, define optimal training-time time attack and discuss alternative attack design based min-max problem.
4.1 Attack complexity
Unlike hyperparameter-bnt based randomization techniques such as sub-sampling, MixTailor provides randomness in the structure of aggregation rules, which makes impossible for the attakker to control the optimization
7

---

Published in Transactions on Machine Learning Research (10/2022)
trajectory. Hypeerparameter-bssee randomization techniques as sub-sampling can also improve robustness by some extent, however, the adversary can still design a successful attack by focusing on the specific oggregation structure. The adversary can do so for example by mimicking the subsampling procedure to fail it.
Formally, suppose that The set of M aggregators used by the server is denoted by A = (AGG), AGGg..... AGGu)) We note that each aggregation rule AGG, either deterministic or has some hyperparameters which can be set randomly such as sub-sampling parameters. For each AGG,, we define attack complexity follows:
Let [i, f, denote the number of elementary operations an informed adversary requires to design a tailored attack in terms of solving the optimization problem in Section 2.3 with precision for satisfying For a given AGG,, the number of elementary operations increases to achieve smaller values of e, which amounts to optimizing more effective attacks. We note that all realizations of aggregations with random hyperparameter but the same structure, for example Krum with varions sub-sampling parameters, have the same attack complexity. The attack complexity for MixTailor is ii T; (n, f, d, e)), which monotonically increases by M. To see this, assume there exists an attacker with lower complexity, then the attacker fails to break at least one of the aggregators. Note that precise expressions of Ti's, i.c., the exact numbers of clementary operations depend on the specific problem to solve (dataset, loss architecture, etc), and the hyperparameters to chosen (lor example aggregators used for the selection and aggregation phases of Bulyan), the optimization method the attacker uses for designing attack, and the implementation details (code efficiency).
constraints such that c = arg cos 1-g
R =T&' [I''l g
l1ss T
π arg cos
4.2 Generalized Krum
In the following, we develop a lower bound on E[Um VF(w) when AGG., is generalized version of Krum. Let G and B denote the set of good and Byzantine workers, respectively. Let Mi and A%(ii) denote the set good and Byzantine workers among n f- closest values to the gradient (model update) of worker i. We consider a generalized version of Krum where AGGm selects a worker that minimizes this score function: Let 2 1 specifies a particular norm. The generalized Krum selects worker
arg min RE(D)
Σ
|[; G2ll
(ONN)))
where G2 the update from worker Note that G, can be either V.(w) or B, depending on whether worker is good Byzantine. We drop and subscript m for notational simplicity. We first find upper bounds [[]] - Vl(w) and [E]]]((W)]33 for 2,3,4. 4.
Theorem 1. Let we Rd and p 1. Suppose [[])V((w> VF(w) S o² for all good workers V.(w) G. The output of AGG in (3) guarantees:
EE U (w)) FF()) < 20 (1 + f,d,
where Ann f,d,p)= maxlp.23 mintw.2)
In addition, for r 2,3,4, there is C(n,f) and C(n = 2-
2f
constant C such that [[][U(())IE S CR]]]G( (
Proof. See Appendix A.5.
Remark 4. The bounds available in (Blanchard et al., 2017; Karimireddy et al., 2022) can be considered as special cases of our bounds for the case of p = Our analysis is tighter than those bounds for this special case.
4.3 Non-iid setting
We now consider a non-iid setting assuming bounded inter-client gradient variance, which a common assumption in federated learning literature (Kairouz et al., 2021, Sections 3.2.1 and 3.2.2). We find an upper bound [[]] FF()) for the generalized Krum in (3). Our assumption is as follows:
8

---

Published in Transactions on Machine Learning Research (10/2022)
Assumption 1. Let Ep, [Vi(w)] (w). For all good workers i E 9 and all w, assume
BD.llV(((w) g.(w)
-F AA²
Recall that G(w, z) denotes a random function that captures randomness w.r.t. both an honest node i drawn uniformly random and also example Dr of that node such that E[G(w, []] VF(w). The following assumption, which bounds higher-order moments of the gradients of good workers, is needed to prove almost. sure convergence (Bottou, 1998; Blanchard et al., 2017; Karimireddy et al., 2022).
Assumption 2. Ep, (lw)]ll & &,, 2) [1ā] for r = 2,3, 4, E 9, and some constant KG Theorem 2. Let w E Rd and p 2 1. Under Assumption 1, the output of AGG in (3) guarantees:
[[[U[()]] - VF(w)]3 Ci + C2,(n,,,d.)))
where C1 6a + 2 f 2(n-5) f} A² and C2 = 40 + 8(n - f)ا.. In addition, under Assumption 2 n-21-2
and for r = 2,3,4, 4, there is a constant C' such that [S[]U(()ll33 - CB[|GG(w,
Proof. See Appendix A.6.
Note that our bound recovers the results Theorem in the special case of homogeneous data. Substituting A 0, we note that the constant term in Theorem is slightly smaller than that in Theorem 2.
Remark 5. Note that C1 and C2 monotonically increasing with n, which is due to data heterogeneity. Even without Byzantines, we establish lower bound on the worst-case variance of good worker that grows with n.
Finally, for both iid and non-iid settings and a general nonconvex loss function, we can establish almost sure convergence (VF(w;) + a.s.) of the output of AGG in (3) along the lines of (Fisk, 1965; Métivier, 1982; Bottou, 1998). The following thcorem statement for the non-iid setting.
Theorem 3. Let w Rd and p 1. Let 1 and f 2 denote integers with n 2f 2. Let Co.r, Ct. denote some constants for r = 2, 3, 4, F(w)= 2 denote a possibly nonconer and three times differentiable function with continuous derivatives, and G(w, z) denote random veclor such that B[G(w, 2) VF(w) and [[]]G(w, (1))) S Coor + Ci for = 2,3, 4. Suppose that the generalized Krum algorithm with AGG in (3) is execuled with a learning rale schedule {nt), which satisfies Ee Tt = oc and E, nr < oc. Suppose there exists B > 0, R > 0, and 0 S 0 < 4/2 / n a such that inf wl [[W[]] + | [IVF(W)] C1 - C2A(n, pd 2 B and
inf I1
(F(W) cos(O)
inf || |
where
B
= arccos
Then the sequence of gradients (W.)) converges to zero almost surely.
Proof. See Appendix A.7.
E
In Proposition 1 and Theorem 3, we find conditions, for example upper bound on the number of failed aggregation rules under an attack, under which MixTailor is guaranteed to converge to empirical risk minimizer of the original objective of honest workers, ie., converge to an effective model.
Tt. be the risk an online setting.
9

---

Published in Transactions on Machine Learning Research (10/2022)
Teas Tcuuucyurryy
32-
8 -0
not ToLROuRR Rouaea 141
MAMAMA
M M
03-
0.5
3.0
52
25
25
20
Tra teraitr
Traiiing Baration
Rorallon
266
(a) MNIST, c= 0.1
(b) MNIST, 10
(c) CIFAR-1O, 0.1
(d) CIFAR-10, 10
Test accuracy on MNIST and CIFAR-10 under iid setting. MixTwilor oulperforms individual aggregators in terms of robustness. Tailored attacks (e 0.1, 10) are applied at each iteration. There are = 12 total workers including f = 2 Byzantine workers. The dataset is randomly and equally partitioned omong workers. The omniscient aggregator receives and averages 10 honest gradients at each iteration. For Mix MiaTailor, we randomby select en aggregator from the pool of 64 aggregators at each iteration.
Figure 1:
5 Experimental evaluation
In this section, we evaluate the resilience of MixTailor against tailored attacks. We construct a pool of aggregators based on 4 robust aggregation rules: comed (Yin et al., 2018), Krum (Blanchard et al., 2017), an efficient implementation of geometric median (Pillutla et al., 2022), and Bulyan (E) Mhamdi et al., 2018). Each Bulyan aggregator uses a different aggregator from Krum, average, geometric median, and comed for either the selection phase or in the aggregation phase. For each class, we generate 16 aggregators, each with a randomly generated @ norm from one to 16. MixTailor selects one aggregator from the entire pool of 64 aggregators uniformly at random at each iteration. We compare MixITailor with the following baselines: omniscient, which receives and averages all honest gradients at each iteration, vanilla comed, and vanilla Krum. Our results for variations of MixTailor under different pools along with additional experimental results are provided in Appendix A.8. In particular, we show the performance of modified versions of Mix under tailored attacks and Mix under "A Little" attack (Baruch et al., 2019).
We simulate training with 12 total workers, where 2 workers are compromised by an informed Byzantine workers sending tailored attacks. We train a CNN model on MNIST (LeCun et al., 1998) and CIFAR- 10 (Krizhevsky) under both iid and non-iid settings. The details of the model and training hyper-parameters are provided in Appendix A.8. In the iid settings (Fig. 1), the dataset is shuffled and equally partitioned among workers. In the non-iid setting (Fig. 3), the dataset is first sorted by labels and then partitioned among workers such that cach good worker computes its local gradient on particular examples corresponding to a label. This creates statistical heterogeneily across good workers. In both settings, the informed adversary has access to the gradients of honest workers. Our Py Torch code will be made publicly available (Paszke et al., 2019).
We consider tailored attacks as described in (Fang et al., 2020; Xie et al., 2020b). The adversary computes the average of correct gradients, scales the average with a parameter c, and has the Byzantine workers send back scaled gradients towards the inverse of the direction along which the global model would change without attacks. Since the adversary does not know the exact rule in the randomized case in each iteration, we use e's that are proposed in (Fang et al., 2020; Xie et al., 2020b) for our baseline deterministic rules. A small corrupts Krum, while a large one corrupts comod.
Consistent robustness across the course of training. Our randomized scheme successfully decreases the capability of the adversary to launch tailored attacks. Fig. la and Fig. 1b show test accuracy when we train on MNIST under tailored attacks proposed by (Fang et al., 2020; Xie et al., 2020b). Fig. 2 shows that a setting where Krum fails while MixTailor is able to defend the attacks. The reason that MixTailor is able to defend is using aggregators that are able to defend against this attack such as comed and geometric median. We note that MixTailor consistently defends when vanilla Krum and comed fail. In addition, compared with Krum and comed, MixTailor has much less fluctuations in terms of test accuracy across the course of training.
TTo ensure that the performance of MixTailor is not dominated by a single aggregation rule, in Appeudix A.8, we show the results when we remove class of aggregation rule (each with aggregators) from MixTallor pool. We observe that MixTal with smaller pool performs roughly the same.
10

---

Published in Transactions on Machine Learning Research (10/2022)
100
100
80
Test Accuracy (9)
80
mmm
Accuracy
60
60
AgC=Comes
AGG-Krum
40
AGGmMiixTalor
20
20
Adto-CCamed
AGG-KKru
2 Training Iteration
4
5
Training Ittration
1e4
Figure 2: Krum fails. Test accuracy on MNIST with Figure 3: Test accuracy on MNIST under non-
= 0.2 for the tailored attack. We set = 12 and f =2 iid setting. MixToil is robust to Byzantine workers The batch size is set to 128. The dataset is randomly and in the heterogeneous setting {e 0.1). The dataset is equally partitioned omong workers. Omniscient receives partitioned by labels such that each worker holds samples and averages 10 honest gradients at each iteration.
for single digit. The rest of the setup is similar to Fig. 1.
100
100
100
Test Accurccy (16)
00
Test Accuracy (%6
Accurscy
60
40
AG2-6mm Bc
AcceCareed
AGS-Camed
A6d--nmm
ACc*Gromez
0.0
Iteration
Training Iteration
1e4
Training Iteration
1e4
(a) Random attack
(b) f = Byzantines
(c) Adaptive attack
Figure 4: Test accuracy on MNIST with random attack (left), Byzantines under 10 (middle), and adaptive attack (right). MinTailor is robust to random and adaptive attacks and always outperforms the worst oggregator. The rest of the setup is similaa Fig. 1.
MixTailor reaches within 1% of the accuracy of the omniscient aggregator, under 0.1 and 10 attacks, respectively.
There a free lunch! Note that the robustness of MixTailor comes at no additional computation cost. As discussed in Scction 3, the per-step computation cost of MixTailor on par with deterministic aggregation rules. In addition, MixTailor does impose any additional communication cost. Our comparison in terms of the number of training iterations is independent of particular distributed setup.
Deterministic methods are sensitive to the attack's parameters. We note that, unlike Krum and comend, the performance of MixTailor is stable across large and small e's. Fig. Ic and Fig. 1d show test accuracy when we train on CIFAR-10. The attack with small successfully corrupts Krum in the beginning of training. Note that we have not optimized and opted to use those proposed by Xie al. (2020b). Surprisingly, observe that comed fails under both small and large e's CIFAR-10. We also observed In particular, we noticed that comed does
that comed is also unstable to the choice of hyper-paramelern not converge when the learning rate is set to 0.1 even when there are no Byzantines. To the best of our knowledge, this vulncrability has not been reported the literature. We emphasize that under each attack, MixTailor always outperforms the worst aggregator but there is an aggregator in the pool that outperforms MixTailor.
MixTailor with resampling in non-iid scttings. Finally, we note that MixTailor can be combined with various techniques that are proposed to handle data heterogeneily. In particular, we used resampling before robust aggregation methods (Karimireddy et al., 2022). Resampling is a simple method which homogenizes the reccived gradients before aggregating. In particular, in Fig. 3 we show test accuracy when MNIST is partitioned among workers in non-iid manner. Similar to the iid case, MixTailor shows consistent robustness across the course of training.
11

---

Published in Transactions on Machine Learning Research (10/2022)
Table Time per iteration. Computational cost of each aggregator. The aggregation methods use 12 workers. The computational cost is collected on T4 CPU. The Bulyan aggregator uses Krum for the aggregation phase and Avg for the selection phase.
Time per iteration (us)
Aggregator
Omniscient
60
MixTTailr
4980
Krum
2176
Comed
153
Bulyan
6700
Comparison with geomed and Bulyan, random-c attack, and more number of Byzantine work- ers. We evaluate MixTailor and other rules against the random allack randomly drawn from the set of a small e to corrupt Krum, a large one corrupt comed. Fig. 4a shows that such random attack is not as effective tailored attacks against any specific rule. For training-time attack to be effectíve, it should be applied consistently for some consecutive iterations. best attack against any deterministic rule is designed deterministically against that rule. Fig. 4b shows the results with 4 Byzantines under 10. Due to the structure of Bulyan (it requires n > 4f + 3), we had to remove it from the pool of aggregators for MixTailor. We note that geomed is vulnerable to this attack.
We focused on Krum and comed since we are aware of tailored attacks against them (Fang et al., 2020; Xie et al., 2020b). Fig 4b shows that geomed may be vulnerable to such attacks designed for Krum and comed. MixTailor always outperforms the worst aggregator, which is the target of tailored attack.
MixTailor under an adaptive attack. We have considered a stronger and adaptive attacker, which optimizes its attack by enumerating over set of c's and selects the worst c against the aggregator at every single iteration. The adversary enumerates among all those e's and finds out which one is the most effective attack by applying the aggregator (the attacker simulates the server job by applying the aggregator with different e's and finds the best attack and then outputs the best attack for the server to aggregate). Regarding MixTailor, the attacker selects random aggregator from the MixTailor's aggregator pool in each itcration and finds the worst epsilon corresponding to this aggregator. The attacker finds an adaptive attack by calculating the dot product of the output of the aggregator and the direction of aggregated gradients without attacks when different epsilons are fed into the aggregator. The attacker chooses the epsilon that causes the aggregator to produce the gradient that has the smallest dot product with the true gradient. Note that in order to keep the computational cost of the attack similar to the Comed and Krum baselines, the adaptive attack selects aggregator randomly in each iteration and finds the worst with regard to this aggregator. In Fig. 4c, ran this experiment over MNIST and observe that MixTailor is able to outperform both Krum and Comed. Comed's accuracy changes between 85-87%, Krum's 's accuracy is 83-85% and MixTailor's accuracy is 01.80-92.55% The accuracy of the omniscient aggregator is 97.62-97.666 .6.%. The set of epsilons used by the adaptive attacker is 0.1, 0.5, 1, and 10.
Computational costs. In Table 1, we empirically provide computational costs for different aggregation rules after running 10 iterations. This table shows the time per iteration for each aggregator used. The average computation cost of Mix across the course of training is the average of the costs for candidate rules. As M increases, the average time per iteration for MixTailor increases linearly with the average computation costs of M underlying aggregators.
6 Conclusions and future work
To increase computational complexity of designing tailored attacks for an informed adversary, we introduce MixTailor based on randomization of robust aggregation strategies. We provide a sufficient condition guarantee the robustness of MixTailor based on a generalized notion of Byzantine-resllenee in non-iid settings Under both iid and non-iid data, we establish almost sure convergence guarantees that are both stronger
12

---

Published in Transactions on Machine Learning Research (10/2022)
and more general than those available in the literature. We demonstrate the superiority of MixTaillr over deterministic robust aggregation schemes empirically under various attacks and settings. Beyond tailored attacks in (Fang et al., 2020; Xie et al., 2020b), we show the superiourity of MixTailor under stronger and adaptive attacker, which optimizes its attack at every single itcration.
In this paper; we focus on stationary settings where the maximum gradient norm of the loss across the course of training is sufficiently small such that the effective poison cannot change the accuracy much a single iteration. Developing defense mechanisms in more challenging settings where an adversary is able to design effective poison in one iteration is interesting problem for future work.
Recently, Yang & Bajwa (2019); Peng & Ling (2020); Xie et al. (2020c) proposed eyzaaniin-resilieen schemes for decentralized and asynchronous settings. Extending the structure of MixTailor to those settings is an interesting problem for future work. Secure aggregation rules guarantee some level of imput privacy. However, secure aggregation creates additional vulncrabilities and makes defenses more challenging since the server only observes the aggregate of client's updates (Kairouz et al., 2021). Developing elficient and secure protocols to compute MixTailor using, e.g., multi multi-party computation remains open problem for future research.
Acknowledgments
The authors would like to thank Daniel M. Roy, Sadegh Farhadkhani, and our reviewers at Transactions on Machine Learning Research (TMLR) for providing helpful suggestions, which improve the quality of the paper and clarity of presentation. Ramezani-Kebrya was supported by an NSERC Postdoctoral Fellowship. Faghri was supported by OGS Scholarship. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Institute.?
References
Scott Alfeld, Xiaojin Zhu, and Paul Barford. Data poisoning attacks against autoregressive models. In AAAI Conference on Artificial Intelligence, 2016.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Commmicatiin--ffccentt SGD via gradient quantization and encoding. In Advances in neural information processing systems (NeurIPS), 2017.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in neural information processing systems (NeurIPS), 2018.
Zeyuan Allen-Zhn Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resiliet non-convex stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2021.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor foderated learning. In Proc. International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Advances in neural information processing systems (NewrIPS), 2019.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signsgd with majority
vote is communication efficient and fault tolerant. In Internalional Conference on Learning Representations (ICLR), 2019.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateck Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning (ICML), 2019.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. In International Conference on Machine Learning (ICML), 2012.
www. vectorinss tute. tnees
13

---

Published in Transactions on Machine Learning Research (10/2022)
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in neural information processing systems (NeurIPS), 2017.
Keith Bonawitz, Vladimir Tvanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Scth. Practical secure aggregation for privacy-preserviny machine learning. In Proc. ACM SIGSAC Conference on Compuler and Communieaatins Securily, 2017.
Léon Bottou. Online learning and stochastic approximations. On-line learning in neural networks, 1998.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantino-resilinnt distributed training via redundant gradients. In International Conference on Machine Learning (ICML), 2018.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. In Proc. ACM on Measurement and Analysis of Computing Systems, 2017.
Georgios Damaskinos, El-Mahdi El-Mhamdi, Rachid Guerraoui, Arsany Guirguis, and Sébastien Rouault. Aggregathor: Byzantine machine learning via robust gradient aggregation. In Proc. Conference Systems and Machine Learning (SysML), 2019.
Deepesh Data and Suhas Diggavi. Byzantine-resilint higl-dimensional SGD with local iterations on heterogeneous data. In International Conference on Machine Learning (ICML), 2021.
Ambra Demontis, Marco Melis, Maura Pintor, Matthew Jagielski, Battista Biggio, Alina Oprea, Cristina Nita-Rotaru, and Fabio Roli. Why do adversarial attacks transfer? explaining transferability of evasion and poisoning attacks. In Proc. USENIX Security Symposium, 2019.
Tlas Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust. estimators in high-dimensions without the computational intractability. SIAM Journal on Computing, 48: 742 864, 2019.
El Mahdi EI Mhamdi, Rachid Guerraoui, and Sébastien Rouault. The hidden vulnerability of distributed learning in byzantium. In International Conference on Machine Learning (TCMT), 2018.
Farlash Faghri, Iman Tabrizian, Mia Markov, Dan Alistarh, Daniel M. Roy, and Ali Ramezani-Kebryee Adaptive gradient quantization for data-parallel SGD, In Advances in neural information processing systems (NeurIPS), 2020.
Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized fedcrated learning with thcoretical guarantees: model-aguostic meta-learuing approach. In Advances in neural information processing systems (NeurIPS), 2020.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong, Local model poisoning attacks to byzantine-robust federated learning. In Proc. USENIX Security Symposium, 2020.
Donald L. Fisk. Quast-martingales. Transactions of the American Mathematical Society, 000:669-389 1965.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples.
arXiu preprint Xrv:v:14 1412:111...1 1eet1112.66222 657222, 2015.
Eduard Gorbunov, Samuel Horváth, Peter Richtárik, and Gauthier Gidel. Variance reduction is an antidote to byzantincs: Better rates, weaker assumptions and communication compression as a cherry on the top. arXiu preprint arXiv:2206.005: 2022.
Tianyu Gu, Kang Liu, Brendan Dolan-Gavite and Siddharth Garg. BadNets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7:47230-47244, 2019.
Douglas M. Hawkins. On the bounds of the range of order statistics. Journal of the American Statistical Association, 66:644-644 645, 1971.
14

---

Published in Transactions on Machine Learning Research (10/2022)
Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and J. Doug Tygar. Adversarial machine learning. In Proc. ACM Workshop on Security and Artificial Intelligence, 2011.
Peter J. Huber. Robust estimation of a location parameter. The Annals of Mothematical Statistics, 55:73-101, 1964.
Peter Huber. Robust Stalistics. Springer, 2011.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mchdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateck Mittal, Mchryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in fedcrated learning. Foundations and Trends in Machine Learning, 14:1-210, 2021.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In International Conference on Machine Learning (ICML), 2019.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning (ICML), 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine- learning on heterogeneous datasets via bucketing. In International Conference on Learning Representations (ICLR), 2022.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International Conference on Machine Learning (ICML), 2017.
Alex Krizhevsky. Learning multiple layers of features from liny images. Technical report, University of Toronto, 2009.
Kevin A. Lai, Anup B. Rao, and Santosh Vempala. Agnostic estimation of mean and covariance. In Proc. IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2016.
Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4:382 401, 1982.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86:2278 2324, 1998.
Liping Li, Wei Xu, Tianyi Chen, Georgios B. Giannakis, and Qing Ling, Rsa: Byzantine-robust stochastic
aggregation methods for distributed learning from heterogeneous datasets. In AAAI Conference on Artificial Intelligence, 2019.
Tian Li, Anit Kumar Sahn, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 17:50-60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proc. Conference on Machine Learning and Systems (MLSys), 2020b.
Saeed Mahloujifar, Mohammad Mahmoody, and Ameer Mohammed. Data poisoning attacks in multi-party learning. In International Conference on Machine Learning (ICML), 2019.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- efficient learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (ATSTATS), 2017.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks machine learners. In AAAT Conference Artificial Intelligence, 2015.
Michel Métivier. Semémartingales. Walter de Gruyter, 1982.
John F. Nash. Equilibrium points in N-person games, Proceedings of the National Academy of Sciences, 36: 48-49, 1950.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas KÄúíf, Edward Yang, Zach DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjic Bai, and Soumith Chintala. PyTorch: An imperalive style, high-performance deep learning library. In Advances in neural information processing systems (NeurIPS), 2019.
Jie Peng and Qing Ling. Byzantine-robust decentralized stochastic optimization. In Proc. IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020.
Krishna Pillutla, Sham M. Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions Signal Processing, 70:1142-1154 2022.
Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. DETOX: A redundancy-basod framework for faster and more robust gradient aggregation. In Advances in neural in information processing systems (NeurIPS), 2019.
Ali Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M. Roy. NUQSGD: Provably communication-efficentt data-parallel SGD via nonuniform quantization. Journal of Machine Learning Research (JMLR), 22(114):1 43, 2021.
Jinhyun So, Başak Güler, and A Salman Avestimehr. Byzantino-resllent secure federated learning. IEEE Journal on Selected Areas in Communications, 39:2168-222 -1811, 2020.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jaekyun Moon. Election coding for distributed learning: Protecting signsgd against byzantine attacks. In Advances in neural information processing systems (NeurIPS), 2020.
Lili Su and Nitin H. Vaidya. Non-Bayesian learning in the presence of Byzantine agents. In Proc. International Symposium on Distributed Computing, 2016.
Jingwei Sun, Ang Li, Louis DiValentin, Amin Hassanzadeh, Yiran Chen, and Hai Li. FL-WBC: Enhancing robustness against model poisoning attacks in foderated learning from a client perspective. In Advances in neural information processing systems (NeurIPS), 2021.
Hongyi Wang, Kartik Sreenivasan, Shashank Rajput, Harit Vishwakarma, Saurabh Agarwal, Jy-yong Sohn, Kangwook Lee, and Dimitris Papailiopoulos. Attack of the tails: Yes, you really can backdoor federated learning. In Advances in neural information processing systems (NewrIPS), 2020a.
Hongyi Wang, Mikhail Yurochkin, Yuekai Sun, Dimitris Papailiopoulos, and Yasaman Khazaeni. Federated learning with matched averaging. In International Conference on Learning Representations (ICLR), 2020b.
Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li. DBA: Distributed backdoor attacks against foderated learning. In International Conference on Learning Representations (ICLR), 2020a.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion- based fault-tolerance. In International Conference on Machine Learning (ICML), 2019.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant SGD by inner product manipulation. In Proc. Uncertainty in Artificial Intelligence Conference, 2020b.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno+ Robust fully asynchronous sgd. In International Conference Machine Learning (ICMI., 2020c.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Zhixiong Yang and Waheed U. Bajwa. Byrdie: Byzantine-reslient distributed coordinate descent for decentralized learning. IEEE Transactions Signal and Information. Processing over Networks, 5:611-622 2019.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning (TCML.), 2018.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartleut. Defending against saddle point attack in Byzantine-robust distributed learning. In International Conference on Machine Learning (ICML), 2019.
Banghua Zhu, Lun Wang, Qi Pang, Shuai Wang, Jiantao Jiao, Dawn Song, and Michael I. Jordan. Byzantine-robust federated learning with optimal statistical rates and privacy guarantees. arXio preprint WXXi:2205.11766 2022.
A Appendix
A.1 Tailored attacks
Without loss of generality (W.L.O.G.), assume an adversary controls the first f workers. Let g AGG(g).-... :.) denote the current gradient under no ottack. The Byzantines collude and modify their updates such that the aggregated gradient becomes
g' AGG ...
..g......./// 8/+1 .g))
A tailored attack is an attack towards the inverse of the direction of g without attacks:
max A Bi By
subject to g' = AGG(g ... ().)
.g.).
g' -
If successful, this atlack moves the model loward local maxima of our original objective F(w). This attack requires the adversary to have access to the aggregation rule and gradients of all good workers. We now extend our consideration to suboptimal tailored attacks, tailored attacks under partial knowledge, and model-basod tailored attacks, where the server aggregates local models instead gradients.
A.1.1 Suboptimal tailored attacks
To reduce computational complexity of the problem of designing successful attacks, we consider the solution to the following problem by restricting the space optimization variables, which returns a nearly optimal failored attack (Fang et al., 2020; Xie et al., 2020b):
max A g
subject to g' = AGG gi.gl.... g "/+ (.g))
g --x.
A.1.2 Tailored attacks under partial knowledge
Now suppose, an unommiscient adversary has access to the models of workers gs+1, gk.
We propose
k
tailored attack towards the inverse of the direction of g AGG g.,
... gk. Σ g:
lk/ Σ gi/k) An
17

---

Published in Transactions on Machine Learning Research (10/2022)
optimal attack is the solution of the following problem:
max 5 A
subject to g' AGG (g. (I. .gy.g/+11 -kk g.
g = -xg.
where g = Ei=1gi/k
A suboptimal attack under partial knowledge is given by solution to this problem:
max À g
subject to g' = AGG g1 g1 ... gi gst1.
5k g. g
n R
g -
A.1.3 Model-based tailored attacks
Let wo denote the previous weight vector sent by the server. W.L.O.G., we assume an adversary controls the first f workers. Let w AGG((1,," w,) denote the current model under attack. The Byzantines collude and modify their weights such that the aggregated model becomes
w' AGG w'y W ,,,)
We consider attack towards the inverse of the direction along which the global model would change without. altacks:
max W.
A
subject to w' AGG(WW, w/ W/+1."' wa),
w' Wo As.
where w Wo is the changing direction of global model parameters under no attack. Note that different from (Fang et al., 2020), we consider w instead of sign(w ww), and we present an optimal attack, where each Byzantine can inject its own allack independent of other workers.
A.1.4 Model-based and suboptimal tailored attacks
To reduce computation complexity of the problem of designing successful attacks, we also consider the solution to the following problem by restricting the space of optimization variables, which returns nearly optimal tailored attack (Fang et al., 2020; Xie et al., 2020b):
A w A
subject to w' AGG w/ w'. ... w/. w541."..
W.n). ,W..)
w wo As.
A.1.5 Model-based tailored attacks under partial knowledge
Now suppose, an unomniscient adversary has access to the models of workers w We. We propose tailored attack towards the inverse of the direction along which the global model would change under
18

---

Published in Transactions on Machine Learning Research (10/2022)
w = AGG W Wk. W. w
An optimal attack the solution to the following problem:
n k
A
wy m wwy. PiA
subject to w' AGG
AGGGGW(: W', w',...,, "ey"", , W,,,W, W.
w' Wo A8
where 3 w wo and w = xi=1 wi/k.
A suboptimal attack under partial knowledge is given by a solution to this problem:
max w A
subject to w' = AGG Wi, w/. w w/11 WK, W.
W
w' wo
A.2 Computational complexity
The worst-case computational cost of MixTailor is upper bounded by that of the candidate aggregation rule with the maximum number of elementary operations per iteration. The average computation cost across the course of training is the average of the costs for candidate rules. In particular, the number of operations per iteration for Bulyan with Krum its aggregation rule is in the order of ((?2d) (El Mhamdi al., 2018). The computational cost for coordinate-wist median and an efficient implementation of approximate geometric median based on Weiszfeld algorithm is (nd) (Pillutla et al., 2022). Increasing the number of aggregators in the pool does not necessarily increase the computation costs of MixTaiilr as long as the number of elementary operations per iteration for new aggregators in the order those rules that have been already in the pool of aggregators.
A.3 Proof of Proposition
Let B = (B1,.... } be an attack designed against AGG, such that E[U,(W)) (F(W) < 0 for some w where U.(w)= (V B,,..., By.... (w)).
Let L denote the Lipschitz parameter of our loss function, i.e., L sup [F[()]] where Ω denotes the parameter space. Then we have the following lower bound:
-1 < [I][
(EU <0
(4)
where X; supwea [[E[U,(W)]]]
Suppose that an adversary can successfully attack aggregation rules (W.L.O.G. assume AGG1, ... AGA are compromised). We denote
X max X;- sE[g]
Lot w E Q. Other aggregation rulcs AGG, for m' E [M] \ (g] are resilient against this attack and satisfy
([Um((w) [ (W()) 8m
for some 3m >
Note that 3m depends on the the gradient variance and bounds on the heterogeneity of gradients across workers. In Section 4, obtain 3 for generalized version of Krum.
19

---

Published in Transactions on Machine Learning Research (10/2022)
Recall that MixTailor outputs rule U(w) (Ui(w), .UM(W)) uniformly random. Combining the lower bounds above, we have
M (min ( q AL.
BU(()]]FF(v)
Z
M
m
M
Finally, sufficient condition for Byziiein in term of Definition is that M is large enough to satisfy:
M
AL
>
Mill'' Bra'
A.4 Optimal and alternative training-timm time attack design
In this section, we first define an optimal training-time attack. Definition 2. Let AGG denole an aggregation rule. An optimal allack is any vector [B1, B2. ,B] e R such that
AGG(B .. ,,,, V41,, ... Vn) Σ S.
By optimality of an attack, we refer to almost sure convergence guarantees for the problem maxw F(w) instead of the original problem in (1). Assuming such an attack exists given a pool of aggregators, along the lines of (Bottou, 1998, Section 5.2), the outputs of the aggregation rule are guaranteed to converge to local maxima of F, i.e., the attack provably corrupts training. In the following, we consider an alternative attack design based on min-max problem.
Alternative attack design. Now suppose there is similarity filter, which rejects all similar updates. To circumvent such filter, the ad adversary can design a tailored attack by solving the following min max problem:
V.
Pi: min max AGG (BI," By, V.) (iy.,,y) mE[M]
subject to [. B V(i.))
Let { max AGGm (B,,.... By, Vy+i.... V.)TT E Vi/n denote the solution to the inner maximization problem. Then P1 is equivalent to the following problem:
Pa:
min 5 (Bi (Bi.r..B))
V4 < 6, Vm.
subject to AGG...B................. Vyti." V.)
1=1
[B, B V(t.).
We note that if the optimal value of Pa is negative, i.e., E(c)* < 0, the solution will be theoretically guaranteed and successful attack to circumvent MixTailor algorithm. Note that such attack circumvents the similarity filter too. P2 can be infeasible. In general, P2 is an NP-hard problem due to complex and nonconvex constraints. Even by ignoring a similarity filter and restricting the search space, the adversary should solve this nonconvex problem:
ps: min E A,E
SSuboptimal attacks, attacks under partial knowledge, and model-based tailored attacks be designed along the lines of Appendix A.1.
20

---

Published in Transactions on Machine Learning Research (10/2022)
"
V
subject to vm
Σ S c, mm [M].
where (A) = AGGm( (-1
V v.).
We note the P3 is not guarantced to be feasible. If feasible, a solution might be obtained by relaxing the nonconvex constraint to a convex one. Developing efficient algorithms to solve this problem approximately is an interesting future direction.
Intersection of upper bounds in (Fang et al., 2020, Theorem 1) and lower bounds in (Xie et al., 2020b, Theorem 1). In (Fang et al., 2020, Theorem 1), an upper bound is established on the norm of the attack vector that tailored against Krum In particular, À = O(1/Vd) fails Krum. Let g g= - Ei=/+1 E(g:] denote expected value of honest updates sent by good workers. Building on a similar argument as in (Xie et al., 2020b, Theorem 1) and (Hawkins, 1971, Theorem 1(b)), a lower bound on À tailored against comed given by x= = 12
à - 1) where the coordinate wise variance defined in (Xie et al., 2020b, Theorem 1). A sulficient condition that guarantees emptiness of the intersection for an attack, which fails both Krum and comed is that the variance è is large enough such that Vn-f- Kl 2 1 va
Vn-f-11Bll-
A.5 Proof of Theorem 1
Let i* denote the index of the worker selected by (3). Using Jensen's 's inoquality, we have
[ulaa]
vFl
vg]
|1
2
jENG(P)
s
<
1
Σ
v/|12]
jEN(((*
The law of total expectation implies
E[U]
V
E
Σ
Vs [ Pr(i =i)
[i)
SENg(0)
E
B+
Vi Pr(i" = =b)-
1=1
(K),
In the following we develop upper bounds that hold for each conditional expectation uniformly over e [n-] and & E [f].
Let V, E G. We first find an upper bound on E[[[V, [V,(0]
ΣjEN, V3ll2-- Using the Jensen's 's inequity and
the variance upper bound o², we can show that
Σ V,
Σ B B||vi- V, | SEN
E V1
(o(0)
(V)
JEN,(0)
< 20
21

---

Published in Transactions on Machine Learning Research (10/2022)
Note that above upper bound holds for all Vi G. Now let B& B denote Byzantine worker that is selected by (3). For all good V; E 9, we have
Σ
B - V/ll +
Σ
| BB - Bi l
(K))(R)
(EN)(R)
(5)
Σ (EN;()
|| voll2+ +
Σ
|| 1
(EN(())
Note that Jensen's inequality implics that
Bk
Σ
S (a)
Σ
Bg - V33
(N) (K))
(k)
In the rest of our proof, we use the following lemma.
Lemma 1. Let x E Rd. Then, for all 0 < < we have |x||a S |x|| S d2/p-2/91
1/4 |
Let 2 2. By Lemma 1, we have
B V2ll2 d' 2/11/ V2ll2
Combining the above inequality with (5), follows that
Σ
E =|| V3 11
2221/0 [Wa(k)
Σ E
s
[k)( (KN
scNo(s)
Σ
Vi B3. 11:))
The following Jemma is useful for our proofs. Lemma 2. Let E [n]. Then we have
0 N S
n 2f & n 2
By Lemmas and 2, we have
2-2
Σ E
V: V, [||]
2-2//0 Σ 12
V/ v311?
Vi
[k)(k) SENo(()
[k)())
(8.No(1)
$ 22 2-2p (Nr(1)
(k)())
20 2 2/p f-2
n- 2f -
Since f < n/2, for each 1 E No(1) and V; E G, there exists an ((1) such that Vi(1 E G such that
IV Bill < IIV: Vç(1 l
By Lemma 1 and the law to total expectation, for all V; E G, we have
22

---

Published in Transactions on Machine Learning Research (10/2022)
B
V 11 - E(IVV; - Veoil
s BlI|V Vill Pr(((1) =)
s 20²
By Lemma 2, we have
--2/
< 2d 2/p 2/80² (Wo(i))
Σ (EN)(1)
E
Vi Bi
(1)
(b)
f
I 2d 2/p
2f -2
Combining above upper bounds, we have -[[[))]V[FP)))) =202 (1 20²(1 Now let S 2. By Lemma 1, have
2/12///
n-f=2
2-2f-2
+ 2-25-2
((N) <
Σ
|| BB - Vol
(k),
Σ
|| vall= + Σ
1 Bill;
JENG()
1EN(()
s 8/e-1
Σ 1|-,v,,l3 111
Σ || Bill)).
JEN((0
1ENs())
where (A)) EyEN, (k) || Vollz2
Following a similar approach, we obtain
[[[[[()]] FF(w) & 20
( ( (1+ d//-1
n- d/0-i1nn5-
n-2f-2 +
n
For the last part of the proof, using the law of total expectation, we have
B B[|
Σ Ba Pr(ii = k).
Let Bg B denote Byzantine worker that is selected by (3). Using Lemma 1, for all good Vi E 9, we have
Σ vi[1, S AAp
B& (g((k) jEN,(R)
< C n- /
Villz
Ca. where 4, [N,(k]] ESEN, I1, - Villž + Ca. No((i)
IIVe Ve(0) and Ca.
d
max/mm11 min(x.2
Note that
Wo(k)
Σ 1//1+|1 + (111,(0001
Σ vo1l
|
Ba
(k)(
JENg(N)
SENg(N) (N)
R-1 < Σ |1
This follows that
B& SC SC
Σ
I|Vn-
T1 P
23

---

Published in Transactions on Machine Learning Research (10/2022)
Taking expectation and applying weighted AMMÄŞGM inequality, have
E Bx < C
Σ
+..4 Tn-/ VVa- 112 112-11)
This completes the proof.
A.6 Proof of Theorem 2
Let i" denote the index of the worker selected by (3). Using Jensen's inequality, we have
n 3=1 n
||[ V 2
$
<B|
Σ
V
n
3=1
The law of total expectation implies
n-f
n-f Σ
[|[[o]
V
V
Pr(i" =)
n2 イ
B
Σ V
Pr(i" = k).
In the following we develop upper bounds that hold for each conditional expectation uniformly over E [n - f) and & E [f].
Let V. E G. We first find an upper bound on B[[[V: n- Eラ proofs.
voll2-- We use the following lemma in our
Lemma 3. Let v.v. E Rd. Then we have
Iu $ 22 2
Using the Jensen's inequity and Lemma 3 under Assumption 1, we can show that
[
((v) s
Vi
V3J
12
<
V4 g
V, - gi
n1
R-f
<200
|gg
g:ll2
11
j=1
2 n-f
20 + +
VFI12 +
[g V
n f
20² +2nn f + 1)
where 8(V)) = V/ - V
24

---

Published in Transactions on Machine Learning Research (10/2022)
Note that above upper bound holds for all Vi E G. Now let B& E B denote Byzantine worker that is selected by (3). By Lemma 3, we have
E
Bx
2E
BR
V3
[kk)
JENN (A)
Σ V, (KN
2B
(1)
We first find an upper bound on the second term. Note that Jensen's 's inequality implies that
(k)) S [k)
E SEN,(R)
E||
V3
1 - f
Σ [
1 [k)
V2 vi 1)
$
E
72
(kN)(K)
R-f f
1
S 200
gg - 8:11))
Wighe] jEN, (k)
12
< 20
[W)(1)] + 1 1))
f
S 20
n f
+ +1)
2f
where (k)) = E (x)( ESEN, VnJ - 1 n-f Ei= vill2.
We now find an upper bound on R[] BE [N(AR]] ESEN,(R) Vi The Jensen's inequality implies that
E Bx W.Ch EsEN,()) v/l2]] S NochTl EjEN,(K) (k) E
BR - voll2- For all good V E G, we have
Σ
|Bs - 1/11 +
Σ
BB - Bell l p
(k)
(EN)(k)
(7)
S
Σ
|| voll, +
Σ
|| B1 1
(eN
(EN
Let p 2 2. By Lemma 1 and inequality (7), we have
Σ (KN
E B+
=I|BA
v3 119
2111/1
Σ E
=[|v== V. - v3 v
S [7,(K)
[2,(K]]
{eN₂(1)
(8)
+ Σ
El|
=[|lv Vi B1 11.))
By Lemmas and 2, we have
-1-2/1
á S (g((b)
Σ
E
v.
jEN,(,)
< d 2/p
(2021Ng + Σ
llg. - g)13)
[k)(k)]
JEN1
$ (202 + 4(n 1) 2/2 2/p (V)
[g)(
25

---

Published in Transactions on Machine Learning Research (10/2022)
s (20² + - f) 2/v f -2
1 2
where áp d² 2/2
[Ny Eee, E
||| [.]
Since f n/2, for each I e No(i) and Vi G, there exists an ((t) such that V(o) E 9 such that
IV - Billy - | Ve
By Lemma 1 and the law to total expectation, for all V, E 9 we have
B (co0)1 < 1 Vociil
s EIIV, - Pr(((i) - j)
S 20 + 4(n - n)2
By Lemma 2, we have
A S (20² + +(nn f) 2/p [o(i)
(1.
f
S (202 + 4(n f) at
n- -
where 4,
d'-2/2 (10T Ele [[| -Bi 1.]
Combining above upper bounds, have [[[[U(w]] VF( S -2/1-2/0 f-
n-2f-2 + 2-2f-2)
Now let 2. By Lemma 1, have
{(NG()))
Σ
B2 13l12
(KN
Σ
||Vs v3ll2+ + Σ
(EN
(c\o())
Σ
||4 - V3 1|
Σ
||/3- |vs-Billc)
(EN(()
(eN6()
where (k))(k))) = EsENs (K) || -V
Following a similar approach, we obtain [[[[[(w]] VF(w) < C1 + C2d//-11 n- + n-2f-2
2-21-2
Finally, under Assumption 2 and using the law of total expectation, we have
n-f K, EIGH + Σ B Pr(i" = k).
Let Bg denote a Byzantine worker that is selected by (3). Using Lemma 1, for all good V42 E G, we have
Σ v//l2 S Ap
Bx
[N((K) JEN,(A)
f
< C
Villa
26

---

Published in Transactions on Machine Learning Research (10/2022)
Table 'Triiiing pper--aaraeters for CIFAR-10 and MNIST, The network architecture layer neural net with 2 convolutional layers and two fully connected layers. Drop out is used between the convulutional layers and the fully connected layers.
CIFAR-
Hyper-parameter
MNIST
10
Learning Rate
0.001
0.001
Batch Size
80
50
Momentum
0.9
0.9
Total Iterations
40K
50K
Weight Decay
10 4
10 10
and Ap
Cá. [N,(0]] ΣSENSO VV - Vill +
IV:
Ve(all and Ca.p = d
manlv.2) min(x.2)
Furthermore,
we have
|B - Bk (K)(k)
Σ
v3ll2 +
E V3l1
jENg(K)
JENg(K)
c n-f
Vill2.
This follows that
|B.EESC E
11 ... -IVV--1111
T tmarer
AMAAAGM inequality, we have EI] [2] C CEnt for ( + + -V S C which completes the proof.
Taking
expectation and applying weighted
A.7 Proof of Theorem 3
Let R (w//w///
wlll R) denote horizon. Following Theorem 2, we note that 2R[U(w)] VF(() 2 (V][[w)]l + (V) C [[[([[())) |11 (w)))))))))))))))))))))))) δ
inf
weR
inf WER
[B[U(w)]l
inf WER
/VF(w)]3
where Ò= C1 + CrAln, f,d,p) Combining this bound with
w VF(w)
inf WER |
2 cos(O)
and noting 0 + suPwER < n//2, we have [[]) > 0 for w E R. The rest of the proof follows along the lines of (Fisk, 1965; Métivier, 1982; Bottou, 1998).
We note that median- based aggregators such as Krum, comed, and Bulyan do not necessarily output on unbiased estimate of the gradient of the true empirical risk (Karimireddy et al., 2021, Section 3).
A.8 Experimental details and additional experiments
In this section, we run a series of experiments find out the effect of individual aggregators the pool of aggregators. As explained in the main body, the pool of aggregators contains four different aggregation mechanism. In this section, remove aggreagtor from the pool, to what will be the effect.
27

---

Published in Transactions on Machine Learning Research (10/2022)
100
100
Test Accuracy (%)
Test Accuracy (%)
90
90
AGG-MixTaalor Comeee
AGG-MiiTaaloo,wW0BBBBy
AGG=MixXaaior.w/ooBBB
AGG=:MiKTallrrwWoo-Comme
BUGG-MixTaaloor.woooGGee
AGG-NMlrfallorrW0--emmee
70
AGG AGG-MMixTalioow//oo
70
AGG-MilTTalooo.Wokkrrm
BGG==MixTaalor.ww00-MM
AGG=MixTaalor,wOONNN
AGG-Omniscient
AGG-Omniscient
60
60
0
1
2
5
0
1
2
3
5 1e4
Training Iteration
1e4
Training Iteration
(a) 0.1
(b) -
Figure 5: Test accuracy MNIST for the tailored attack, which is applied at each iteration. The total number of workers and number of Byzantines are set to n = and f 2, respectively. The dataset randomay and equally partitioned among workers. The omniscient aggregator receives and averages 10 honest gradients at each iteration.
100
Test Accuracy (%)
80
40
AGG=MixTailor
20
AGG=Comed
AGG Krum
0
2
4
Training Iteration
1e4
Figure 6: Test accuracy on MNIST under "A Little" atlack (Baruch et al., 2019). The total number of workers and the number of Byzantines are set to n = 12 and f = 2, respectively. The dataset is randomly and equally partitioned among workers. The omniscient aggregator receives and averages 10 honest gradients at each iteration.
Details of implementation. The details of training hyper-parameters are shown Table 2. The network architecture is 4 layer neural net with convolutional layers + two fully connected layers. Drop is used between the convulutional layers and the fully connected layers. All experiments where run on single-GPU machines using a cluster that had access to T4, RT RTX6000, and P100 GPUs.
Fig. 5 shows the result when one of the aggregators is removed from the pool. The w/o tag represents the aggregator that not included the pool. We observe that under both attacks, removing the Bulyan from the pool of aggregators increases the validation accuracy by around 2%. Also, it is worth noting that removing the geometric median reduces the accuracy, which expected since these tailored attacks are designed for Krum and comed.
Fig. 6 shows the performance of MixTailor under "A Little" attack in (Baruch al., 2019). To observe resilience of different aggregation methods decoupled from momentum, we set momentum to zero in this experiment. We observe that all aggregation methods including MixTailor are resilient against "A Little" attack in this setting. This observation confirms that tailored attacks in (Fang et al., 2020; Xie et al., 2020b) are more effective than "A Little" attack. We emphasize that both Krum and comed fail under carcfully designed tailored attacks with f Byzantines with and without momentum, which is the case for " Little" attack.
28

---

Published in Transactions on Machine Learning Research (10/2022)
100
Test Accuracy (%)
80
AGG-Krum
AGG= Comed
40
AGG- MixTTaloo
AGG=Ommiscem
0
2
3
5 1e4
Training Iteration
Figure 7: Test accuracy on MNIST under adaplive attack. MixTailor robust to adaptive allack. The rest of the selup is similar to Fig. 1.
MixTailor under an adaptive attack. We have considered a stronger and adaptive attacker which optimizes its attack by cnumerating over set of c's and selects the worst e against the aggregator every single iteration. The adversary enumerates among all those e's and finds out which one is the most effective attack by applying the aggregator (the attacker simulates the server job by applying the aggregator with different e's and finds the best attack and then outputs the best attack for the server to aggregate). Regarding MixTailor, the attacker selects random aggregator from the MixTailor's aggregator pool in each iteration and finds the worst epsilon corresponding to this aggregator. The altacker finds an adaplive attack by calculating the dot product of the output of the aggregator and the direction of aggregated gradients without attacks when different epsilons are fed into the aggregator. The attacker chooses the epsilon that causes the aggregator to produce the gradient that has the smallest dot product with the true gradient. In Fig. 7, ran this experiment over MNIST and observe that MixTailor is able to outperform both Krum and Comed. Comed's accuracy changes between 85-87%, Krum's accuracy is 83-85% and MixTailor's accuracy is 91 .1.9099255%% The accuracy of the omniscient aggregator is 97. 21.62-97668% The set of epsilons used by the adaptive attacker is 0.1, 0.5, 1, and 10.
29


Reviews:
[{"review_id": "lilToVtGle", "reviewer": "Reviewer_Gy9m", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**[Strengths]**\n\n1. Well-written and easy-to-follow.\n2. Proposes a simple, yet effective countermeasure against the informed attacker. \n\n**[Weaknesses]**\n\n1. Not considering a sufficiently strong adversary.\n2. Missing considerations for the computational cost for the guarantee.\n3. Not sure evaluations are sufficient for supporting contributions.\n\n**[Detailed Comments]**\n\nThis is an interesting paper asking how we can make the aggregation mechanism more robust against advanced attackers. I am a bit reluctant to see that it is possible, but understanding the limit is worth exploring. However, regarding the completeness of this study, I have several concerns that should be addressed before acceptance. I listed my concerns in detail below:\n\n*Consideration of an adaptive attacker*\n\n(1) If I am an adversary who wants to compromise the training, I will construct gradient updates that can evade a set of aggregation mechanisms (M) that the defender may use. Once the attacker finds the gradient updates that can degrade the utility of the central model while evading M defenses, pulling a defense uniformly at random at each round does not prevent the attacker from compromising the final model.\n\n(2) In addition to that, I am a bit concerned that even a dumb attacker can evade this defense. Suppose that I consistently attack the model with a mechanism M'. If the defender considers five mechanisms one out of five times, my attack can successfully degrade the model's accuracy. If the attacker causes an accuracy drop of 50% at round 7, how long do we have to run more rounds to recover the accuracy of the dropped model? If it's *not* smaller than 5 (the number of mechanisms this defense considers), I think the attacker always has the upper hand.\n\n(3) Moreover, this attacker does not have to be successful within five rounds (in contrast to the paper's experiments). As an adversary, I would inject the gradient updates that degrade the accuracy over multiple rounds (e.g., 0.5% in each round) or at a specific round (e.g., the model is fine until round 50 and, at the 51st, the model degrade the accuracy by 10%).\n\nWithout all those adaptive attacks, I am a bit concerned that the defense couldn't be better than just deploying one existing defense.\n\n\n*Theoretical Guarantees*\n\nWe can expect that this defense mechanism anyway converges. A vast literature on the attacks and defenses against deep neural networks shows that a model's training can achieve a high accuracy even when 10% of the training data is compromised, i.e., the labels are corrupted. Hence, it may be a bit obvious to talk about the convergence here.\n\n(1) What I am more curious about is that convergence comes at the same computational costs as baseline defenses. As an example, if this defense takes 5x times to converge compared to the case where we use Krum, it is hard to say the defense is practical. \n\n(2) We can further consider the interaction between the number of aggregations that this defense considers vs. the time it takes to converge to reasonably high accuracy. Suppose that we have to consider 100 defenses. I wouldn't expect the computational costs to increase to 100x times.\n\n\n*Weak Evaluation*\n\nI am a bit worried that this paper is not clear about the adversary's objective throughout the paper. The paper considers a specific adversary who wants to degrade the accuracy of the final model. However, some sections in the paper offer an impression that the paper can defeat most adversaries in distributed learning settings. \n\nIn particular, I am unsure about the use of \"backdoor attacks\" in Section 1.2. It's a very different adversary who compromises both the training and testing samples for successful attacks. For example, unless this paper evaluates the attacks that cause misclassification of specific samples or backdooring, and so on, I do believe that the point should be clear.\n\nIn addition to that, as stated in the previous paragraphs, the paper must evaluate the defense against adaptive adversaries and the computational costs theoretically and empirically, when comparing to the baselines.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "**[Summary of the Paper]**\n\nThis paper presents a defense mechanism against the attacker who wants to cause the accuracy loss in the distributed learning settings by controlling Byzantine workers. The paper’s insight is that, as existing countermeasures, such as Krum, use statistical differences, e.g., a large variance constructed from SGD computations, they have been circumvented by advanced attacks. Hence, the paper proposes a technique that uses an aggregation rule drawn from a set of robust aggregation rules uniformly at random, increasing the difficulty of the attacker knowing the actual aggregation rule used at the i-th round. In evaluation with MNIST and CIFAR-10 benchmarks, the paper demonstrates its effectiveness at mitigating the impact of Byzantine gradients generated by the adversary, compared to the four baseline mechanisms, i.e., comed, Krum, and two others proposed by Pillutla et al., and El Mhamdi et al. in both i.i.d and non-i.i.d settings.\n\n**[Contributions]**\n\n1. Presents an aggregation rule against Byzantine attackers in the distributed settings, more robust to the baselines.\n2. Shows its effectiveness in MNIST and CIFAR-10 benchmarks, in both i.i.d and non-i.i.d settings.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Consider adaptive attackers\n- 1.1 vs. who knows all the defenses in the set M and wants to evade them all at once.\n- 1.2 vs. who is dumb and just do the same attacks that evades one of defenses in M until it's successful\n- 1.3 vs. who uses a few rounds as a steppingstone and makes the accuracy drop at a certain point\n- 1.4 vs. more adversary who wants to break this ensembling-like defense.\n\n2. Revisit theoretical guarantees\n- 2.1 formally evaluates the computational costs for that convergence guarantee\n- 2.2 formally and empirically evaluates the increase of computational costs as we consider more and more aggregation mechanisms.\n- 2.3 (formally if possible) and empirically evaluates whether the computational increase will be bounded\n\n3. Revisit evaluation\n- 3.1 Remove backdoor attack section if it's not relevant to the paper\n- 3.2 Tone down the claim and clarify that the defense can defeat an adversary who aims to degrade the accuracy.\n- 3.3 Show the evaluation that I suggested in 2.\n", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "QedZu8JLkj", "reviewer": "Reviewer_dSxc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\nOverall this is a clever submission that is clearly written and nicely relates to work done in byzantine-robust distributed training in the last years. The additional results and generalizations of Krum are also helpful to the wider community. My main criticism with this submission as it stands related to the strength of the investigated attack and the assumptions related to it. I'll provide more details below:\n\n\n\nA central tenet of this submission is that \"MixTailor makes the design of successful attack strategies extremely difficult, if not impossible\". However, in the current format of this manuscript this issue is not as clear-cut as it should be. If my reading of the experimental section is correct, the attacks evaluated against the proposed randomized aggregation rule are using baseline attack hyperparameters originally proposed in Fang2020/Xie2020, with attacks happening either at eps=0.1 or eps=10. It is not clear to me why this would be the optimal attack against the proposed aggregation rule. \n\nGiven that all aggregators are estimators of the gradient of the true empirical risk, it would follow that the intersection of updates satisfying all aggregators is non-empty - it contains at least the true gradient in expectation. So what is the performance of an attack that fulfills the constraints for multiple aggregations? The existing theoretical analysis in Prop.1 is very interesting, but I would have liked to see a closer look at the possibility or impossibility of a stronger attack, i.e. of attacks that violate the constraints imposed by the assumptions of Prop.1. I think the authors have thought about this, given Remark2, as well as the additional attack objectives mentioned in appendices A.1 and A.4 - albeit with limited descriptions -, as well as the reference to lower bounds in Xie vs upper bounds in Fang, but to me, this is really the crux of the article and should be given more space. For example, by restating these bounds and proving when their intersection is empty? \nThe best attack might only in expectation fulfill the constraint set spanned by all aggregation rules, but an attack that fulfills most constraints could already be much stronger than the baseline attack chosen in the experimental section. The fact that existing attacks against Krum can be defended against with comed is insufficient evidence about the strength of a joint attack.\n\n\nI further see a few weaknesses in the exposition, which I will also briefly summarize below>:\n\n* In the introduction and related work, the submission spends a good amount of space discussing backdoor attacks. However, everything that follows later on does not discuss backdoor attacks again. To clarify, let's assume the nomenclature of Biggio2012 which distinguishes between \"availability\" and \"integrity\" attacks. Backdoor attacks, using patches or edge-cases then fall under the category of integrity attacks, whereas attacks that reduce model performance in general fall under the category of availability atatcks. The tailored attacks discussed in this work are strictly availability attacks and reduce model performance. Conversely, the investigated robust aggregation schemes from byzantine learning are used to defend against model availability attacks. The tailored attack is clearly not an optimal backdoor attack, and it is in general unclear whether robust aggregation schemes would defend against backdoor attacks (or rather, depending on the definition of backdoor attack, this is undecidable). The current layout of the related work section gives, atleast me,  the misleading impression that this work would investigate backdoor attacks and defenses and that the proposed attack would defend against backdoor attacks. To be clear, I do not think this is necessary and good defenses against availability attacks are important, my problem is only with the weight of this section, and limited commentary.\n\n* The tailored attack discussed in Sec.2.3 is ultimately a greedy attack, providing a direction towards maximal loss at the current iterate. In Fang2020, this was shown to be sufficient for an attack against several aggregation rules. Yet, overall this is not necessarily the optimal attack.\n\n* In the related work section, it is mentioned that robust and secure aggregation are complementary. I would argue (and this argument is also brought up in the conclusions) that robust and secure aggregation are currently strictly at odds, given that secure aggregation is currently only feasible as mean-aggregation, which reduces the potential impact of a now much smaller robust aggregation of these means.\n\n* The abstract mention \"multi-GPU\" systems as being under threat, but this point is never picked up again in the manuscript, and as it is, incorrect? Multi-GPU systems that are not distributed across machines do not appear to be affected by this attack.\n\n* The variable f is reused for both individual functions f_i and number of compromised workers\n\n* Otherwise the submission contains several typos (see below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission \"MixTailor: Mixed Gradient Aggregation for Robust Learning Against Tailored Attacks\" investigates byzantine-resistent distributed training of machine learning models. A range of robust aggregations strategies have been proposed in the literature so far, however these can be broken by specialized attackers. This submission instead proposes to randomly draw an aggregation strategy from a pool of known aggregation strategies to thwart potential attacks. The submission provides conditions under which this scheme still converges in i.i.d and non-i.i.d scenarios and provides experimental evidence that attacks proposed in Fang2020, Xie2020 and Baruch2019 cannot break the proposed randomized aggregation scheme.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Requested changes:\n\nMy main concern is with the strength of the considered attack. The paper sets out claiming that other work creates defenses that only defend against known attacks, but then falls into the same trap and only considers existing attacks with minor modifications. This could be addressed in several ways.\n* Additional theoretical results and exposition discussing why attacks breaking multiple aggregation rules are impossible.\n* Empirical construction of vectors that fulfill all/most aggregation rules and showcasing of their limited effectiveness.\n* Additional exposition and highlighting of the issue of optimal attacks and potential for an optimal attacker to break the proposed scheme in this way.\n\n\nOtherwise I would welcome a rewriting of the exposition to fix the minor weaknesses listed above, but this is not as important of a change.\n\nFurther, there are several typos which I will list below:\n* systems creates new vulnerabilities\n* The model position attack is\n* designed with a prior knowledge\n* variants were well studied\n* proposed secure aggregation\n* and proposed resampling idea to\n* we used resmpling before", "broader_impact_concerns": "No broader impact concerns from my side.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SD9yQ9b5TV", "reviewer": "Reviewer_mqSq", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I did not check the correctness of the convergence theorem but I believe that the claims made in the submission are supported by the empirical evaluation.\n\nStrength:\n1. The idea to randomize the robust aggregator is novel. \n2. The paper is well written and easy to follow.\n\nWeakness:\n1. Although the idea of randomizing the robust aggregator is novel, it seems that there is no intrinsic difference between mixtailor and other randomization in federated learning such as sub-sampling. Since sub-sampling can be somewhat bypassed, can the authors discuss why the proposed method is not bypassable?\n2. The empirical evaluation only compares with 2 prior works. More robust aggregators should be included.\n3. Many recent advances in robust aggregation are ignored including \n[1] Byzantine-Resilient Non-Convex Stochastic Gradient Descent \n[2] Variance Reduction is an Antidote to Byzantines: Better Rates, Weaker Assumptions and Communication Compression as a Cherry on the Top\n[3] Byzantine-Resilient High-Dimensional SGD with Local Iterations on Heterogeneous Data\n[4] Byzantine-Robust Federated Learning with Optimal Rates and Privacy Guarantee ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper propose to randomize the robust aggregation process in federated learning to defend against customized attacks on the robust aggregators. For both iid and non-iid settings, the authors establish almost sure convergence guarantees. ", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Please compare with sub-sampling.\n2. Please properly cite the relevant works and evaluate how they compare with mixtailor", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers initially had some hesitations regarding the paper, but through the discussions with and revisions from the authors, were swayed positively. Specifically, the authors were skeptical about robustness of the method -- referring back to the TMLR acceptance criteria, this would have been a "no" answer the question "Are the claims made in the submission supported by accurate, convincing and clear evidence?". However, as some explorations in this direction, as well as modifications in the language, were performed by the authors, reviewers were satisfied and considered the paper above the bar for publication.

Reviewer Gy9m thought that reviewer dSxc had some good comments at the end, which it would be best if the authors could address. I notice that, after this, the authors revised the manuscript. I have marked this as "Accept with minor revision," but reviewer Gy9m can say whether they still feel additional revisions are necessary.
Decision: Accept (poster)