A Simulation-based Framework for Robust Federated Learning to Training-time Attacks
Authors: Wanyun Xie
Thomas Pethick
Ali Ramezani-Kebrya
Volkan Cevher
Venue: Submitted to ICLR 2023 (2023)
Keywords: Robust federated learning
training-time attacks
game theory

Abstract: Well-known robust aggregation schemes in federated learning (FL) are shown to be vulnerable to an informed adversary who can tailor training-time attacks [Fang et al., Xie et al.]. We frame robust distributed learning problem as a game between a server and an adversary that is able to optimize strong training-time attacks. We introduce RobustTailor, a simulation-based framework that prevents the adversary from being omniscient. The simulated game we propose enjoys theoretical guarantees through a regret analysis. RobustTailor improves robustness to training-time attacks significantly while preserving almost the same privacy guarantees as standard robust aggregation schemes in FL. Empirical results under challenging attacks show that RobustTailor performs similar to an upper bound with perfect knowledge of honest clients.

Under review as a conference paper at ICLR 2023
A SIMULATION-BASER FRAMEWORK FOR ROBUST FEDERATED LEARNING TO TRAINING-TIME ATTACKS
Anonymous authors Paper under double-blind review
ABSTRACT
Well-known robust aggregation schemes in federated learning (FL) are shown be vulnerable to an informed adversary who can tailor training-time attacks (Fang et al., 2020; Xie et al., 2020). We frame robust distributed learning problem as a game between server and an adversary that is able to optimize strong training- time attacks. We introduce Robust Tailor,, a simulation- based framework that prevents the adversary from being omniscient. The simulated game we propose enjoys theoretical guarantees through a regret analysis. RobustTailor improves robustness to training- time attacks significantly while preserving almost the same privacy guarantees as standard robust aggregation schemes in FL. Empirical results under challenging attacks show that Robust Tailor performs similar to upper bound with perfect knowledge of honest clients.
INTRODUCTION
In federatted learning (FL), a global/personalized model is learnt from data distributed on multiple clients without sharing data (McMahan et al., 2017; Kairouz et al., 2021). Clients compute their (stochastic) gradients using their own local data and send them to central server for aggregating and updating a model. While FL offers improvements in terms of privacy, it creates additional challenges in terms of robustness. Clients are often prone the bias the stochastic gradiens updates, which comes not only from poor sampling or data noise but also from malicious allacks of Byzantine clients who may send arbitrary messages to the server instead of correct gradients (Guerraoui et al., 2018). Therefore, in FL, it is essential to guarantee some level of robustness to Byzantine clients that might be compromised by an adversary.
Compromised clients are vulnerable to data/model poisoning and tailored attacks (Fang al., 2020). Byzzantie-resilleene is typically achieved by robust gradient aggregation schemes e.g., Krum (Blanchard et al., 2017), Comed (Yin et al., 2018), and trimmedmean (Yin et al., 2018). These aggregators are resilient against attacks that are designed in advance. However, such robustness insufficient in practice since a powerful adversary could learn the aggregation rule and tailor its training-time attack. It has been shown that well-known Byzantine-resilient gradient aggregation schemes are susceptible to an informed adversary that can tailor the attacks (Fang et al., 2020). Specifically, Fang et al. (2020) and Xie et al. (2020) proposed efficient and nearly optimal training- time attacks that cireumvent Krum, Comed, and trimmedmean. tailored attack is designed with a prior knowledge of the robust aggregation rule used by the server, such that the attacker has provable way to corrupt the training process, Given the information leverage of the adversary, it is a significant challenge to establish successful defense mechanisms against such tailored attacks.
In this paper, we formulate robust distributed learning problem against training-time attacks as a game between a server and adversary. To prevent the adversary from being omniscient, we propose to follow a mixed strategy using the existing robust aggregation rules. In real-world settings, both server and adversary have number of aggregation rules and attack programs. How to utilize these aggregators efficiently and guarantee robustness is a challenging task. We address scenarios where neither the specific attack method is known in advance by the aggregator nor the exact aggregation rule used in each iteration is known in advance by the adversary, while the adversary and the server know the set of server's aggregation rules and the set of attack programs, respectively.'
While this assumption is essential to frame game, provide experimental results on challenging settings where the server does not know the of attack programs in Scction 5.

---

Under review as a conference paper at ICLR 2023
Due to information asymmetry between the server and the adversary, we assume every client do- nates a small amount of honest data to the server as the price to achieve some level of security more proactively and efficiently. Providing such public dataset to achieve robustness is common assumption in FL. (Fang& & Ye, 2022; Huang et al., 2022; Kairouz et al., 2021; Yoshida et al., 2020; Zhao et al., 2018; Fang et al., 2020; Xie et al., 2020; Cao & Lai, 2019; Chang et al., 2019; Cao et al., 2020). We propose Robust'Tailor a scheme based on simulating aggregation rules under different attacks. With minimal privacy leakage, Robust Taillr realizes high resilience to training-time attacks. RobustTailo maintains stable performance under a challenging mixed attack, a strategy we propose for the adversary to simulate and design a successful attack when a smart server uses mixed strategy to make the problem of attack design computationally harder. We emphasize that any deterministic Byzantine-resilient algorithm can be added in server's aggregation pool. Similarly, any attack can be used in the set of adversary's s attack programs.
1.1 SUMMARY OF CONTRIBUTIONS
We frame robust distributed learning problem as a game between a server and an adversary that tailors training-time attacks.
We propose simulation-base based framework Robust Tailor to improve robustness by prevent- ing the adversary from being omniscient.
The simulated game we propose enjoys theoretical guarantees through a regret analysis.
Empirical studies validate our theory and show that Robusttaaioo preforms similar to an upper bound with perfect knowledge of all honest clients over the course of training. Even under a challenging mixed attack strategy, RobustTailor outperforms the robust baselines in terms of robustness and accuracy.
1.2 RELATED WORK
In this section, we provide a summary of related work. See Appendix A for complete related work.
Training-time attacks in FL. Federated learning (FL) usually suffers from training- time attacks (Biggio al., 2012; Bhagoji al., 2019; Sun et al., 2019; Bagdasaryan al., 2020) because the server trains the model across various unreliable clients with private datasets. A strong adversary can potentially participate in every training round and adapt its attacks to an updated model. In model update poisoning, a class of training-time attacks, adversary controls some clients and directly manipulates their outputs aiming to bias the global model towards opposite direction of honest training (Kairouz et al., 2021). If Byzantine clients have access the updates of honest clients, they can tailor their attacks and make them difficult to detect (Fang et al., 2020; Xie et al., 2020).
Robust aggregation and Byzantine resilience. To improve robustness under general Byzantine clients, a number of robust aggregation schemes have been proposed, which are mainly inspired by robust statistics such as median median--bseed aggregators (Yin et al., 2018; Chen et al.. 2017), Krum (Blan- chard et al., 2017), trimmed mean (Yin al., 2018). Moreover, Fang et al. (2020); Xie et al. (2020); Cao & Lai (2019); Cao et al. (2020) propose server-side verification methods using auxiliary data. Karimireddy et al. (2021) 1) and Alistarh et al. (2018) propose history-aided aggregators. Ramezani- Kebrya et al. (2022) propose framework based on randomization of multiple aggregation rules. However, none them selects a proper aggregation rule proactively during training as our framework RobustTailor, and all of them can be used in Robust while mainly focus on statistical- based aggregators in this paper. Although past work has shown that these aggregators can defend successfully under specific conditions (Blanchard et al., 2017; Chen al., 2017: Su & Vaidya, 201 6), Fang et al. (2020) and Xie et al. (2020) argue that Byzantine-resilien aggregators can fail when an informed adversary tailor a careful attack and Gouissem al. (2022) proves that such aggregation rules are vulnerable. Therefore, developing robust and efficient algorithm under such strong tailored attacks is essential improve security of FL, which is the goal of this paper.
Game theory in FL. Online convex optimization (OCO) framework (Zinkevich, 2003) is widely influential in the learning community (Hazan et al., 2016; Shalev-Shwart et al., 2012), and bandit convex optimization (BCO) as an extension of OCO was proposed by Awerbuch & Kleinberg (2008) for decision making with limited feedback. Bandit paradigms paralleling FL framework are proposed by Shi & Shen (2021) and its extension under Byzantine attacks is proposed by Demirel et al. (2022). However, they account for uncertainties from both arm and client sampling rather than robust
2

---

Under review as a conference paper at ICLR 2023
aggregation in this paper. In this paper, frame robust distributed learning problem game and consider the bandit feedback model.
2 PROBLEM SETTING
Under a synchronous setting in FL, clients compute their updates on their own local data and then ag- gregate from all peers update model parameters. Consider general distributed system consisting of parameter server and clients (Chen et al., 2017; Abadi et al., 2016; Li et al., 2014). Suppose that Byzantine clients are controlled by an adversary and behave arbitrarily. Let x E RR denote machine learning model, e.g. it represents all weights and biases of neural network. We consider minimizing an overall empirical risk of multiple clients, which can be formulated as finite-sum problem:
min F(x) XER
Σ F((x)
(FL)
n
where F:: Rdd + R denotes the training error (empirical risk) of x on the local data of client i.
At iteration honest clients compute and send honest stochastic gradients gx(x, = V (x,) for i [n while Byzantine clients, controlled by an informed adversary, ouiput attacks b, Ra for j E [ The server receives all updates and aggregates them following a particular robust aggregation rule, which outputs an aggregated and updated model X E Rd Finally, the server broadcasts X to all clients.
2.1 GAME CONSTRUCTION
We frame this distributed learning problem under training-time attack as game played by the adver- sary and the server. The informed adversary and training-time attacks are described in Section 2.1.1. The details of aggregators for the server are provided in Section 2.1.2. Though our formulation seems natural and intuitive, to the best of our knowledge, our work is the first work that frames robust learning problem under training-time tailored attacks as a game. The adversary aims at corrupting training while the server aims at learning an effective model, which achieves a satisfactory overall empirical risk over honest clients.
2.1.1 INFORMED ADVERSARY WITH ATTACKS
The adversary controls f out n clients where these Byzantine clients collude aiming at disturbing the entire training process by sending training-timm attacks (Biggio et al., 2012; Bhagoji et al., 2019; Sun et al., 2019; Bagdasaryan et al., 2020). We assume n 2 2f 2f+11 which is a common assumption in the literature (Guerraoui al., 2018; Blanchard et al., 2017: Alistarh al., 2018; Rajput et al., 2019; Karimireddy et al., 2022); otherwise the adversary will be able to provably control the optimization trajectory and set the global model arbitrarily (Lamport al., 1982).
An informed adversary controls the outputs of those compromised clients, e.g. their gradients throughout the course of training. Moreover, the informed adversary has full knowledge the outputs of n honest clients across the course of training. Having access to the gradients of honest nodes, the adversary can compute the global aggregated gradient of an omniscient aggregation rule, which is the empirical mean of all honest updates without an attack:
n
g
g:
n
When an adversary knows a particular server's aggregation rule, it is able design tailored attacks using n - honest gradients (Fang et al., 2020). .aa.......nIll gn-s} denote the set of honest updates computed by honest clients. The adversary designs f Byzantine updates using an AT algorithm:
Definition (Attack algorithm). Let (gi....,
(bn-ftt...., bR} == AT(g....., gn-
where A denotes the set of aggregators formally defined in Section 2. 1.2.
3

---

Under review as a conference paper at ICLR 2023
It is shown that several tailored attacks can be designed efficiently and provably fail weol-known aggregation rules with a specific structure e.g., Krum, Comed, and Krum + resampling (Fang et al., 2020; Xie et al., 2020; Ramezani-Kebre Kebrya et al., 2022). Suppose that the adversary has set of S computationally tractable programs to design tailored attacks:
F (ATI, AT,, ATs).
(3)
2.1.2 SERVER WITH AGGREGATORS
The server aims at learning an effective model, which achieves satisfactory overall empirical risk over honest clients comparable to that under no attack. To update the global model, the server aggregates all gradients sent by clients at each itcration.
Definition (Aggregation rule). Let g3 E R2 denote an update received client which can be either an honest or compromised client for E [n]. The server aggregates all updates from n clients and outputs a global update E R. using an aggregation rule AG:
g = AG (..
(4)
where F denotes the set of attacks defined in Section 2.1.1.
We assume that the server knows the number of compromised clients or an upper bound on f. which is a common assumption in robust learning (Guerraoui et al., 2018; Blanchard et al., 2017; Alistarh al., 2018; Rajput et al., 2019; Karimireddy al., 2022).
However, the server does not know the specific Byzantine clients among n clients in this distributed system such that the server cannot compute g' in Eq. (1) directly. To learn and establish some level of robustness against training-time attacks, several Byzantine-resilient aggregation rules have been proposed e.g., Krum (Blanchard et al., 2017) and Comed (Yin et al., 2018). These methods inspired by robust statistics provide rigorous convergence guarantees under specific settings and have been shown to be vulnerable to tailored attacks (Fang et al., 2020; Xie et al., 2020). The set of M aggregators used by the server is denoted by
A = {AG1, AG2,.... AGM]
(5)
Note that the pool of aggregators A and the set of attacks F are known by both the server and the adversary, but the specific AT are AG chosen at iteration l. are unknown. Moreover, such powerful but not omniscient adversary does not have access to the random seed generator at the server. This mild and common assumption in cryptography, which requires secure source of entropy to generate random numbers at the server (Ramezani-Kebry' et al., 2022).
To avoid trivial solutions, we assume each aggregation rule robust (formal definition of robustness is provided in Appendix B) against a subset of attack al algorithms in F while no aggregation rule immune all attack algorithms. Similarly, each attack program can provably fail one or more aggregation rules in A while no attack program can provably fail all aggregation rules.
2.2 PROBLEM FORMULATION
To evaluate the performance of an updated global model, i.e., the output of AG in Eq. (4), we define a loss function, which measures the discrepancy of the output of AG and omniscient model update under no altack.
Definition 3 (Loss function). The loss function associated with using aggregation rule AG under attack AT is defined as:
|| .n. AT 8n Bn-j, F), -g'll ||A gg. b, fh.-tt....... bn A) g*ll. ((AG, (g
(6)
where g" is the ideal model under no attack which is computed in Eq. (1).
To train the global model, the server takes multiple rounds of stochastic gradient descent by aggregat- ing the stochastic gradients from clients. However, some gradients might be corrupt at each round, which are sent by compromised clients controlled by the adversary. We frame this robust distributed
4

---

Under review as a conference paper at ICLR 2023
learning scenario game between the adversary and the server. The server wants to minimize the loss defined in Definition 3, while the adversary aims to maximize it. This game as a minimax optimization problem is formulated as:
min (AAG, (g AGEATTES
(MinMax)
The entire process of model aggregation with rounds is shown in Algorithm 1. Note that Eg denotes the expectation with respect randomness due to stochastic gradients. Ideally, the game in MinMax can reach a Nash equilibrium (NE) (Nash, 1950). However, the loss is not computable for the server, since the server cannot distinguish honest gradients such that g" is unknown for it. Therefore, we will simulate the game in the following Section 3.
Algorithm 1 Update model from the perspective of server
Input:
Initial weight vector xo, learning rate tp. iteration rounds T, number of clients n, set of aggregation
rules A, set attack algorithms F, and public dataset.
for t= to I" do
Server sends X to all clients.
io 1 to
do
Honest client computes local gradient gi (xxe) (xx))
Compromised clients send attacks AT" ((g, H=
Sever receives gradients from all clients {g. Jmm.
Server chooses AG' by solving
min mAX Eg[E(AG', ,TT', (s)))))) AG EF
Server updates the model X
3 ROBUST AGGREGATION
Because MinMax cannot be solved during the process of updating the model, we propose to simulate it instead and obtain optimized aggregator for model updates. As mentioned in Section 2, the informed adversary has an advantage over the server since it can perfectly estimate g" in Eq. (1) while the server does not have such knowledge and cannot identify honest clients a priori. We assume that each client donates a small amount data as a public dataset to the server to achieve some level of security by controlling the information gap between the server and adversary. Let g denote the update computed at the server using the public dataset, which a rough estimate of g"
Remark The server may obtain such public dataset from other sources not necessarily the current clients. It is sufficient as long as the collected public dataset represents the clients' data distribution by some extent. To guarantee convergence, we only require that the update from the public dataset is a rough estimate of the ideal g". In particular, the quality of such estimate directly impacts the convergence of our proposed algoritim (see Section for details). As the quality of such estimate improves, the convergence of the global model to an effective model improves. The existence of such public dataset is a valid and common assumption FL (Fang & Ye, 2022: Huang al., 2022: Kairouz et al., 2021; Yoshida et al., 2020; Chang et al., 2019; Zhao et al., 2018).
For the simulation, the server generates the simulated gradients {g, The loss function in the simulated game becomes
n- based on the public dataset. J==
?(AG, AT, (-))) ||AG ... B B.-,, AT...................... B..
Σ
Let L E R.MS denote the loss of M aggregators corresponding to S attacks, and L(AG,, represents the loss associated with aggregation rule in A under attack j in in the simulation. After the adversary has committed to a probability distribution over S attack algorithms, the server chooses a probability distribution p over M aggregation rules. Then, the server incurs the loss We will solve Mim-MinMax below instead of MinMax.
E(, q) = pEg[[Cq]
min max pEg T.
(Sim-MinMax)
PEAM qEds
5

---

Under review as a conference paper at ICLR 2023
where AM and As denote the probability simplex in [M] and [S], respectively.
In practice, it computationally expensive to compute LMxS and meanwhile there is noise due to the gradients. Therefore, we consider bandit feedback model with limited feedback, in which the server and adversary can only observe the loss through exploration. To solve Mim-MinMax in the bandit feedback model, one player could implement the well-known Exponential weight Algorithm for Exploration and Exploitation (Exp3) (Seldin et al., 2013) whose detailed description is deferred Appendix C.
Due to two players (the server and the adversary) in our model, we propose an algorithm which simuitaneously executes Exp3. We term our proposed robust aggregation scheme Robust,Tailor which outputs an optimized AG at each iteration. The specific algorithm from perspective of the server shown in Algorithm 2. Using the public dataset, the server generates n -f noisy stochastic gradients gi = (x,) for [n - at iteration L. After K rounds of simulation on { the server obtains a final probability distribution and selects an aggregation rule by sampling from p. The steps for our robust training procedure are summarized in Algorithm 3. Note that Appendix H demonstrates both theoretical analysis and empirical results of Robust computation complexity.
Algorithm 2 Robust Tailor
Input: Updating rates Å1, X2, Å1 and λ2, simulation rounds K, simulated gradients {g) (8.) A, Initialize weight vector w(()) (t) for E [M] and (i) for j [S].
for to K do
Set 1epp""(A (AG.) = (1 - X1) (()
IM (²(() A1 M for i E [M].
Set q" (AT,) =
(1 (1 22)
ES x(() + A2 for E (S).
(1(
ΣS
Sample AG ~ p* and AT* q" respectively.
Estimate the loss 1t H(A ,AT H-))
Set (1) =AG,=AG") ptc D*(AG:)
(1) = w (1) exp( (1)MM) for [M].
Set (j) 1(AT, =AT*) gh: 0²) - exxxx (J)/S) for (S).
(ATT))
Set p: El= p² (AGx) for i [M].
10 Sample AG ~ Output: AG.
Algorithm 3 Server's aggregation
Input: Learning rate v/. clients, / compromised clients, iteration rounds T,, A and F Initialize model Xg- for l= = to T do
Send x, to all clients.
Receive gradients from clients [g/]=--
Calculate simulated gradients )
Call Algorithm to aggregate AG' Robust Robust Tailor (AF)).
Update the global model by x
The adversary can also perform simulation to optimize its attack each iteration. The main differences for an adversarial simulation compared to Robust Tailor include: 1) the adversary can use perfect
honest stochastic gradients {g.) /7 instead of noisy estimates; 2) the probability output is q which is calculated by the weight vector of attacks u(j) for E [S]. The details of the adversarial simulation provided in Appendix D.
THEORETICAL GUARANTEES
To show convergence of the inner optimization in Algorithm 2, first show how to turn two simul- taneously played no-regret algorithms for a minimax problem into convergence to a Nash equilibrium (NE). To make the optimization problem shown in Algorithm more general, define new loss

---

Under review as a conference paper at ICLR 2023
function L [M] [S] - R., Consider simultaneously running two algorithms on the objective
L, such that their respective expected regret is upper bounded by some quantities Rix and Rx i.c.
K 2
K
K
K Σ L(kx jie)
E L(i,, jK) - Σ L(2.5k)
S
Rk,
E
Σ
((
S Rk
(8)
1=1
for any i [M and [S] where the expectation is taken over the randomness of the algorithms.
Lemma 1 (Folklore). Assume
algorithms simultaneously with regret in (8) to obtain Ju) By playing i uniformly sampled from {ix 1KK we can guarantee
E [L(,5)] S S [L(E" 11'' + K (R'x + Rkk,
(9)
for any j E [S] where q"), is Nash equilibrium of Bp j [L("",
This kind of result is well-known in the literature (see for instance Dughmi et al. (2017. Cor. 4)). When the algorithms have sublinear regrets, we refer them as no-regrel algorithms. This condition ensures that the enror term in (9) vanishes as K + co. Exp3 (Auer et al., 2002), employed by both the attacker and aggregator Algorithm 2, enjoys such no-regret property.
Lemma (Hazan et al. 2016, Lemma 6.3). Let be the horizon, N be the number of actions, and LA [N] + R+ be non-negative losses for all k. Then Exp3 with stepsize X = =v log KN
enjoys the
following regret bound,
K La (ix)
E
Σ
E s 22/KNlog N,
(10)
for any i [N], where the expectation is taken over the randomness of the algorithm.
Note that any two simultaneously played no-regret algorithms for a minimax problem can be turned into convergence to a NE following Lemmas 1 and 2. We obtain guarantees for the aggregation rule returned from Algorithm 2 as a direct consequence of Lemmas and Considering a specific situation in Algorithm 2, L is replaced by the simulation loss shown in Eq. (7).
Lemma 3. Let f. be the simulation loss in Eq. (7). Sample AG p as defined in Algorithm 2 with X1 as.
log M and πσ = KM
log 5 KS
Then the loss is bounded in expectation for any attack ATK F
S "p) L M + /SlogS
EAG.9 AT,
(11)
VK
where "p",q") AM As is a Nash equilibrium of the zero-sum game with stochastic payoff matrix Eg(C] as defined in Sim-MinMax.
Lemma 3 implies that the simulated loss approaches the NE value even under the worst-case attack. The proofs of Lemma I and Lemma are provided in Appendix E and Appendix F respectively. Impor- tantly, sufficient condition for almost sure convergence for the outer loop is provided in Appendix B.
5 EXPERIMENTAL EVALUATION
In this section, we evaluate the resilience of Robust Tailor against tailored attacks. To provide intuitive results and show benefits of simulation in terms of robustness, we first construct a simple pool of aggregators including only Krum (Blanchard et al., 2017) and Comed (Yin et al., 201 8). Concerning the adversary's tailored attacks, we consider two different types of attacks, which can successfully ruin Krum and Comed, respectively. As described in (Fang et al., 2020; Xie et al., 2020), an adversary with c-reverse attack computes the average of honest update, scales the average with a parameter c, and sends scaled updates to the server induct the global model towards the inverse of the direction along the one without attacks. known that a small corrupts Krum, while a large one comupts Comed (Fang et al., 2020; Xie et al., 2020).

---

Under review as a conference paper at ICLR 2023
We simulate training with total of 12 clients, 2 of which are compromised by informed adver- sary. We train a CNN model on MNIST (Lecun et al., 1998) under both iid and non-iid settings and meanwhile training CNN models on MNISST (FMNIST) (Xiao et al., 2017) and CI- FARI0 (Krizhevsky et al., 2009) is under iid setting. Note that the dataset is shuffled and equally partitioned among clients in the iid settings (Fig. 1). In addition, all honest clients donate 5% of their local training dataset to the server as public dataset as specified in Remark 1, and the informed adversary has access the gradients of honest clients. Note that the details of the model and training hyper-paramenn are provided in Appendix G.I, and all experiments below without specific clarification have same setup with Fig. la, Fig. 1b, and Fig. 3.
Single tailored attacks. Robust successfully decreases the capability of the adversary to launch tailored attacks. PobustTTailo, maintains stability in Fig. la when Krum fails catastrophically under a small attack. Fig. lb shows that Robust Tailor has much less fluctuations in terms of test accuracy compared to Comed when facing large attack. In addition, 70.68% probability of choosing Comed under c = 0.5 attack while 65.49% probability of choosing Krum under 100 attack, which proves that the server successfully learns how to defend. Training on FMNIST shows consistent results as seen in Fig. Ic and Fig. 1d and further results on CIFARIO Appendix G.2. Note that Rabust will outperform both Krum and Comed if there is larger pool to select aggregators, which results are shown in Appendix G.2.
average, Robust has
(a) MNIST. c 0.5
(b) MNIST, e 100
(c) FMNIST, C. 0.1
(d) FMNIST, C 100
Test accuracy on MNIST and FMNIST under iid setting. Tailored attakks (c = 0.1/0.5, 100) are applied. Robust selects on aggregator from Krum and Comed based the simulation at each iteration.
Figure 1:
Mixed attacks. We now consider additional and stronger attack strategies beyond vanilla e-reverse attacks. We assume the adversary has set of attacks including 0.5 and 100 attacks. StochasticAttaad shown in Fig. picks an attack from its set uniformly at random at each iteration. AttackTailor in Fig. 3 optimizes detailed algorithm is in Appendix D. Compared to all previous attacks including StochasticAttack, AttackTailor is much stronger since it can pick a proper attack under perfect knowledge of honest updates. The poison of Attack Tailor shown in Fig. 3 is almost as effective as the most targeted attack tailored against single deterministic aggregator. Importantly, Robust Tailor shows impressive robustness when facing such a strong adversary like AttackTailoo
attack based on simulation at each iteration, whose
CHNALOR
Marc
00
62
3.5
06
0.0
30
60
32
Figure 2: Stochastic Stochastic
Figure 3: AttackTailor. Attack Tailor applies
applies 0.5 and e 100 uniform randomly.
<= 0.5 and = 100 based on the simulation.
Poisoned data mixed in the public dataset. Byzantine clients may be able to donate poisoned data to the public dataset. We assume 16.7% of data in the public dataset is poisoned due to 16.7% of malicious clients. Two normal data poisoning methods we choose are label flipping (LF) (Muñoz- González et al., 2017) and random label (LR) (Zhang et al., 2021). Fig. 4 demonstrates that poisoned data mixed in has little impact on Robust Tailor, which also proves that a small gap between the public dataset and true samples does not reduce the effectiveness of Robust substantially.
8

---

Under review as a conference paper at ICLR 2023
120
(a) 0.5
(b) 100
AttackTailor
Figure 4: Poisoned data mixed in the public dataset.
Unknown attacks for the server. In our assumption, the server knows all attacks in the adversary's pool. What will happen if there is attack of the server's expectation? Fig. gives the results. In particular, = 0.1 in Fig. 5a and é 150 in Fig. 5b are the same rype of attacks as = 0.5/100, 100, and Mimic (Karimireddy al.. 2022) in Fig. 5c and Alittle (Baruch et al., 2019) in Fig. 5d are the different type of attacks. Note that we expand the set of Robust. and Bulyan (Guerraoui al., 2018) as Fig. and decrease the learning rate to 0.005 for against Alittle and Mimic. It shows that RobustTailo can defend against not only the attacks similar to expectation but also those totally different. As a mixed framework, KobusttTailos is hard to be ruined since the adversary hardly designs tailored attack ruining several aggregation rules simultaneously.
with GM (Pillutla et al., 2022)
(a) 0.1
(b) 150
(c) Mimic
(d) Alinle
Figure 5: Attacks out of the server's expectation.
Aggregators with auxiliary data. Public dataset can be used not only for simulation but also to assist with aggregation. Fang et al. (2020) have proposed server-side verification methods: error rate based rejection (ERR) and loss function based rejection (LFR), which reject potentially harmful gradients using error rates or loss values before aggregation. We provide experiments with the setup as in Fig. 3, and Krum/Comed assisted by ERR/LFR is totally ruined by Attcck Tailor with around 10% accuracy while Robust reaches 90.28%. %. These results provide further evidence that Robust Tailor delivers superior performance over existing techniques. By additional experiments, we observe that ERR/LFR helps aggregator achieve around 97% accuracy when facing e = 0.5 attack while it is totally ruined when against = 100. In this more sensitive situation, Attack is easily to break single aggregation rules but Robust still performs well.
Additional experiments. To further validate the performance of Robust Tailor, we set up additional experiments in Appendix G.2 including 1) three datasets; 2) non-iid settings; 3) more Byzantines; 4) more aggregation rules added in Robust 5) the impact of the proportion of public data; 6) subsampling by the server; 7) dynamic strategy of the adversary; 8) adversary with partial knowledge.
CONCLUSIONS AND FUTURE WORK
We formulate the robust distributed learning problem game between server and an adversary. We propose Tabbustaiilo: which achieves robustness by simulating the server's 's aggregation rules under different attacks optimized by informed and powerful adversary. Robust theoretical guarantees for the simulated game through a regret analysis. We empirically demonstrate the significant superiority of Robust over baseline robust aggregation rules. Any Byzantine- resilient scheme with a given structure can be added to moobustaailon 's framework.
provides
Although the increased computation complexity of Robust is acceptable for the great ro- bustness which is analyzed in Appendix H, it is also a future work to develop efficient and secure protocols apply RobustTailor e.g., using multi-party computation (Boneh et al., 2019).

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. (TensorFlow): A System for [Large-Scale} Machine Learning. In 12th USENIX symposium on operating systems design and implementation (OSDI 16), 2016.
Scott Alfeld, Xiaojin Zhu, and Paul Barford. Data poisoning attacks against autoregressive models. In AAAI Conference on Artificial Intelligence, 2016.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems (NeurIPS), 2018
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantinn--rsilieee non-convex stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2021.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 32(1))48-77) 2002.
Baruch Awerbuch and Robert Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. How to backdoor federated learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little enough: Cireumventing defenses for distributed learning. 2019.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Leurning (ICML), 2019.
Battista Biggio, Blaine Nelson, and Pavel Laskov. Poisoning attacks against support vector machines. arXiv preprint 1206. 2012.
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 Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017.
Dan Bonch. Elette Boyle, Henry Corrigan-Gibe Gibbs, Niv Gilboa, and Yuval Ishai. Kero-knowledge proofs on secret-shared data via fully linear PCPs. In Annual International Cryptology Conference, 2019.
Léon Bottou. Online learning and stochastic approximations. On-line learning in neural networks. 1998.
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. FLTrust: Byzantine-robus federated learning via trust bootstrapping. arXiv preprint a1Xiv:2012.13995, 2020.
Xinyang Cao and Lifeng Lai. Distributed gradient descent algorithm robust to arbitrary number of Byzantine attackers. JEEE Transactions on Signal Processing, 67(22):5850-586 2019.
Nicholas Carlini and Andreas Terzis. Poisoning and backdooring contrastive learning. arXiv preprint arXiv:2/06. 096677 2021.
10

---

Under review as a conference paper at ICLR 2023
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks, In 2017 ieee symposium on security and privacy (sp), 2017.
Hongyan Chang, Virat Shejwalkar, Reza Shokri, and Amir Houmansadr. Cronus: Robust and heteroge- neous collaborative learning with black- box knowledge transfer. arXiv preprint arXiv:1912.1127) 2019.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM Measurement and Analysis of Computing Systems, 122) 2017.
Deepesh Data and Suhas Diggavi. Byzantine-resilient high-dimensional SGD with local iterations heterogeneous data. In International Conference on Machine Learning (ICML), 2021.
I1ker Demirel, Yigit Yildirim, and Cem Tekin. Federated multi-armed bandits under byzantine attacks. arXiv preprint arXiv:2205.041: 2022.
Shaddin Dughmi, Omkar Thakoor, and Umang Gupta. CSCI699; Topics in learning & game theory: Lecture 6. pp. 11, 2017. URL https::/viitrrbiiweeet usc. usc. hwt.////haadin//s669f11177 lectures/lec6. pdf.
El Mahdi El Mhamdi, Rachid Guerraoui, and Séhastien Louis Alexandre Rouault. Distributed momentum for Byzantine-resilient stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2021.
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to Byzantine-robust federated learning. In 29th USENIX Security Symposium (USENIX Security 20), 2020.
Xiuwen Fang and Mang Ye. Robust federated learning with noisy and heterogeneous clients. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2022.
Donald L. Fisk. Quasi-martingales. Transactions of the American Mathematical Society, 120(3): 369-389, 1965.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. arXiv preprint 4rXiv:1412.6572, 2014.
Ala Gouissem, Khalid Abualsaud, Elias Yaacoub, Tamer Khattab, and Mohsen Guizani. Federated learning stability under Byzantine attacks. In 2022 IEEE Wireless Communications and Networking Conference (WCNC), 2022.
Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Badnets: Evaluating backdooring attacks on deep neural networks. IEEE Access, 7:47230-472444 2019.
Rachid Guerraoui, Sébastien Rouault, et al. The hidden vulnerability of distributed learning in Byzantium. In International Conference on Machine Learning (ICML), 2018.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Optimiza- tion, 233-4):1573355, 2016.
Ling Huang, Anthony D Joseph, Blaine Nelson, Benjamin IP Rubinstein, and Doug Tygar. Ad- versarial machine learning. In Proceedings of the 4th ACM workshop on Security and artificial intelligence, 2011.
Wenke Huang, Mang Ye, and Bo Du. Learn from others and be yourself in heterogeneous federated learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, 2022.
Matthew Jagielski, Alina Oprea, Battista Biggio, Chang Liu, Cristina Nita-Rotaru and Bo Li. Manipulating machine learning: Poisoning attacks and countermeasures for regression learning. In 2018 IEEE Symposium Security and Privacy (SP), 2018.

---

Under review as a conference paper at ICLR 2023
P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji. K. Bonawitz, Z. Charles,
G. Cormode, R. Cummings. R. G. L. Oliveira, S. E. Rouayheb, D. Evans. J. Gardner, Z. Garrett, A. Gascón, B. Ghazi, P. B. Gibbons, M. Gruteser, Z. Harchaoui, C. He, L. Hc, Z. Huo, B. Hutchin- son, J. Hsu, M. Jaggi, T. Javidi, G. Joshi, M. Khodak, J. Konečný, A. Korolova, F. Koushanfar, S. Koyejo, T. Lepoint, Y. Liu, P., M. Mohri, R. Nock, A. Özgür, R. Pagh, M. Raykova, H. Qi, D. Ra- mage, R. Raskar, D. Song, W. Song, S. U. Stich, Z. Sun, A. T. Suresh, F. Tramèr, P. Vepakomma, Wang, L. Xiong, Z. Xu, Q. Yang, X. Yu, H. Yu, and S. Zhao. Advances and open problems in federated learning. Foundations and Trends R in Machine Learning.
2021.
Sai Pranceth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning (ICML), 2020.
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-robust 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.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-4000 1982.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86:2278-2322 1998.
Sam Leroux, Steven Bohez, Elias De Coninck, Tim Verbelen, Bert Vankeirsbilck, Pieter Simoens, and Bart Dhoedt. Multi-fidelity matryoshka neural networks for constrained IoT devices. In International Joint Conference Neural Networks (IJCNN), 2016.
Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorobeychik. Data poisoning attacks factorization- based collaborative filtering. In Advances in Neural Information Processing Systems (NeurIPS), 2016.
Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski, James Long, Eugene Shekita, and Bor- Yoing Su. Scaling distributed machine learning with the parameter server. !/th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), 2014.
Saeed Mahloujifar, Mohammad Mahmoody, and Ameer Mohammed. Data poisoning attacks in multi-party learning. In International Conference on Machine Learning (ICML), 2019.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficin learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Shike Mei and Xiaojin Zhu. Using machine teaching to identify optimal training-set attacks on machine learners. In AAAI Conference on Artificial Intelligence, 2015.
Michel Métivier. Semimartingales. Walter de Gruyter, 1982.
Luis Gonzzzzz,,zález, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli. Towards poisoning of deep learning algorithms with back gradientt optimization. In Proceedings of the 10th ACM workshop on artificial intelligence and security, 2017.
12

---

Under review as a conference paper at ICLR 2023
John F. Nash. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36(1):48-44 49, 1950.
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. IEEE Transactions on Signal Processing, 10:1142-11540 2022.
Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. DETOX: A redundancy-based framework for faster and more robust gradient aggregation. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ali Ramezani-Kebrya Iman Tabrizian, Fartash Faghri, and Petar Popovski. Mixtailor: Mixed gradient aggregation for robust learning against tailored attacks. Transactions on Machine Learming Research (TMLR), 2022.
Yevgeny Seldin, Csaba Szepesvári. Peter Auer, and Yasin Abbasi Yadkori.. Evaluation and analysis of the performance of the EXP3 algorithm in stochastic environments. In European Workshop on Reinforcement Learning, 2013.
Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 1(2):107-194, 2012.
Chengshuai Shi and Cong Shen. Federated multi-armed bandits. In AAAI Conference on Artificial Intelligence, 2021.
Jinhyun So, Başak Güler, and A Salman Avestimehr. Byzinttn secure federated learning. IEEE Journal on Selected Areas in Communications, 39(7):2168-211) 21811 2020.
Lili Su and Nitin H Vaidya. Fault-tolerant multi-agent optimization: optimal iterative distributed algorithms. In Proceedings of the 2016 ACM symposium on principles of distributed computing, 2016.
Jingwei Sun, Ang Li, Louis DiValentin, Amin Hassanzadeh, Yiran Chen, and Hai Li. FL-WBC: En- hancing robustness against model poisoning attacks in federated learning from client perspective. Advances in Neural Information Processing Systems (NeurIPS), 34:12613-12624, 2021.
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H. Brendan McMahan. Can you really backdoor federated learning? CoRR, 1..7966,, 2019.
Hao Wang. Zakhary Kaplan, Di Niu, and Baochun Li. Optimizing federated learning on non-iid data with reinforcement learning. In IEEE INFOCOM 2020-IEEE Conference on Computer Communicationss, 2020a.
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 (NeurIPS), 2020b.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking 2017.
machine learning algorithms. arXiv preprint
Chulin Xie, Keli Huang, Pin- Yu Chen, and Bo Li. Dba: Distributed backdoor attacks against federated learning. International Conference on Learning Representations (ICLR), 2019.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking Byzantine-tolerant SGD by inner product manipulation. In Uncertainty in Artificial Intelligence, 2020.
Yi-Rui Yang and Wu-Jun Li. BASGD: Buffered asynchronous SGD for byzantine learning. In International Conference on Machine Learning (ICML), 2021.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robuss distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning (ICML.), 2018.
13

---

Under review as a conference paper at ICLR 2023
Naoya Yoshida, Takayuki Nishio, Masahiro Morikura, Koji Yamamoto, and Ryo Yonetani. Hybrid-FL for wireless networks: Cooperative learning mechanism using non-lID data. In ICC 2020-2020
IEEE International Conference Communications (ICC), 2020.
Syed Zawad, Ahsan Ali, Pin-Yu Chen, Ali Anwar, Yi Zhou, Nathalie Baracaldo, Yuan Tian, and Feng Yan. Curse or redemption? How data heterogeneity affects the robustness of federated learning. In
AAAI Conference on Artificial Intelligence, 2021.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:/806.0000 00582, 2018.
Zhuangdi Zhu, Junyuan Hong, and Jiayu Zhou. Data-free knowledge distillation for heterogencous federated learning. In International Conference on Machine Learning (ICML), 2021.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference on Machine Learning (ICML), 2003.
14

---

Under review as a conference paper at ICLR 2023
ll.. and || ||+ to denote the expectation operator, Euclidean norm, number of nonzero elements of vector, and dual norm, respectively. We use |. to denote the length of binary string, the length of vector, and cardinality of set. We use lower-case bold letters to denote vectors. Sets are typeset in a calligraphie font. The base-2 logarithm is denoted by log, and the set of binary strings is denoted by {0, We use [n|] to denote {I,'" } for integer n. We use AM to denote the probability simplex in R
Notation. We use Ei.], || ||. ||
A COMPLETE RELATED WORK
Federated learning (FL). FL (McMahan et al., 2017; Konečný et al., 2016) keeps training data decentralized in multiple clients which collaboratively train a model under the orchestration of server (Kairouz et al., 2021). For the server, such clients are often more unpredictable and especially more vulnerable to the attacks. Secure aggregation protocols (Bonawitz et al., 2017: So al., 2020) ensure that the server computes aggregated updates without revealing the original data. In this paper, we focus on training-time attacks and corresponding aggregation rules.
Training-time attacks. Standard attacks can be broadly classified into training-time attacks (poison- ing attacks) (Biggio al., 2012: Li al., 2016; Jagielski et al., 2018: Bhagoji al., 2019; Huang et al., 2011; Mei & Zhu, 2015; Alfeld et al., 2016; Koh & Liang, 2017: Mahloujifar et al., 2019; Gu
al., 2019; Xie et al., 2019; Wang et al., 2020b: Yang& & Li, 2021; Karimireddy al., 2021; Data &
Diggavi, 2021: Carlini & Terzis, 2021; Allen-Zhu et al., 2021) and inference-time attacks (evasion attacks) (Goodfellow
al., 2014; Carlini & Wagner, 2017). Because the server in FL trains the model across various unreliable clients with private datasets, FL usually suffers from training-time attacks (Biggio et al., 2012; Bhagoji et al., 2019; Sun et al., 2019; Bagdasaryan et al., 2020). A strong adversary can potentially participate in every training round, and meanwhile it can adapt its attacks to an updated model. One class of training-time attacks concerned in this work is model update poisoning. In model poisoning attack, an adversary can control some clients and can directly manipulate their outputs trying to bias the global model towards the opposite direction (Kairouz et al., 2021). If Byzantine clients have access to the updates of honest clients, they can tailor their attacks and make them difficult to detect (Fang et al.. 2020; Xie et al., 2020; Lamport et al., 1982; Blanchard et al., 2017; Goodfellow et al., 2014; Bagdasaryan et al., 2020).
Robust aggregation and Byzantine resilience. To improve robustness under general Byzantine clients, a number of robust aggregation schemes have been proposed, which are mainly inspired by ro- bust statistics such as median- based aggregators (Yin al., 2018; Chen et al., 2017), Krum (Blanchard et al., 2017), trimmed mean (Yin et al., 2018). Krum (Blanchard et al., 2017) and coordinate-wist median (Comed) (Yin al., 2018; Chen et al., 2017) are two main aggregation rules used in this paper. aggregation rule and it aggregates the gradients that minimize
Krum is a gquaredddistance-biee the sum of squared distances to its n f 2 closest vectors where n denotes the total number of clients and f is the number of adversarial ones. Comed is redian-based aggregator and it selects the gradient closest to the median of each dimension.
Except of statistical aggregation rules, there are still many related works like server-side verification, client-side self-clipping etc. From the perspective of the server, Fang et al. (2020); Xie et al. (2020); Cao & Lai (2019); Cao et al. (2020) propose some server-side verification methods using auxiliary data. Specifically, Fang et al. (2020) assume the server has small validation dataset and uses error rates to reject harmful gradients. In (Xie et al., 2020; Cao & Lai, 2019), the server asks small clean dataset from clients and filters out unreliable gradients. Cao et al. (2020) utilize the ReLU- clipped
between local gradients and the standard one calculated by a small clean dataset as the weight for aggregation. Moreover, Karimireddy et al. (2021) and Alistarh et al. (2018) propose history-aided aggregators, and an expandable framework proposed by Ramezani- Kebrya et al. (2022) utilizes randomization to improve robustness. None of them selects a proper aggregation rule proactively during training as our framework Robust We note that all aggregation rules shown here can be added to the pool of Robust Tailor because public dataset is available in our assumption and any aggregation rule can use it. In addition, side clipping methods are proposed by Sun et al. (2021) and Sun et al. (2019), and client-side momentum SGD is considered by Karimireddy et al. (2021) l) and El Mhamdi et al. (2021). However, the ability of clients is not the focus of our paper and we will consider it in future work.
15

---

Under review as a conference paper at ICLR 2023
Past work has shown that these aggregators defend successfully under specific conditions (Blanchard et al., 2017; Chen et al., 2017; Su & Vaidya, 2016). However, Fang et al. (2020) and Xie et al. (2020) argue that Byziitine-resilient aggregators can fail when an informed adversary tailors a careful attack. Therefore, developing a robust and efficient algorithm under such strong tailored attacks is essential to improve security of FI., which is the goal of this paper.
Heterogeneous data. In the real world applications, many issues such as heterogeneous data become significant (Kairouz et al., 2021; Karimireddy et al., 2020). Karimireddy et al. (2022) find that robust learning algorithms of FL may fail under iid setting. Several algorithms are proposed to tackle non-iid data (Yoshida et al., 2020; Zhao et al., 2018; Karimireddy et al., 2022: Wang et al., 2020a; Data & Diggavi, 2021; Zhu et al., 2021). Besides, data heterogeneity easily leads to backdoor attacks, which can be viewed as a kind of training-time time attacks (Xie et al., 2019; Bagdasaryan et al., 2019; Zawad et al., 2021). Therefore, establishing robustness under non-iid setting is also an important indicator for aggregator.
Game theory in FL. Online Convex Optimization (OCO) framework (Zinkevich. 2003) is widely influential in the learning community (Hazan et al., 2016; Shalev-Shwartz et al., 2012), and Bandit Convex Optimization (BCO) as an extension of OCO was proposed by Awerbuch & Kleinberg (2008) for decision making with limited feedback. Bandit paradigms paralleling FL framework are proposed by Shi & Shen (2021) and its extension under Byzantine attacks is proposed by Demirel et al. (2022). However, they account for uncertainties from both arm and client sampling rather than robust aggregation in this paper. In this paper, we frame robust distributed learning problem as a game and consider the bandit feedback model.
B ROBUSTNESS OF Robust
In this section, we define general robustness definition of an aggregation rule against attack. Note that our definition covers a broad range of settings with general pure and mixed aggregation along with general pure and mixed attack strategies. Our robustness notion leads to almost sure convergence guarantees to a local minimum of F in FL, which is equivalent to being immune to training-time time attacks.
Definition 4 (Robustness of an aggregator to an attack program). Lei x E Rd denote machine learning model. Lei (x) = V Fx; E Rd be independent honest updates for i E [n]. Let G(x) denote a function that draws an honest client uniformly at random followed by outputting an unbiased stochastic gradient of F,(x), over that client such that B[G(x)] VF(x) where E is over both random client and samples. Let AG denote an arbitrary aggregation rule, which can be mixed aggregation strategy selecting an aggregator from A = [AG1,..., AG 3 based on simulation. The output of AG is given by ğ(x) = (Gg (=)) Note that {g'}²= includes both honest and compromised updates. The compromised updates are the output of an attack program A / A). Note that AT can be pure or mixed attack strategy.
The mixed aggregation rule AG is Byzantine- to AT if g(x) satisfies Blğ(x)) VF()) 0 and [x)] S (xx]
= 2,3, 4 and some constant Ky.
Suppose {2 in Algorithm satisfies Σ, 17, = 0 and E, th < co. For a nonconvex loss function, which is three times differentiable with continuous derivatives, bounded from below, and satisfies global confinement assumption in (Bottou, 1998, Section 5.1), general pure and mixed aggregation and attack strategies satisfying Definition 4, and general non-iid data distribution across clients, we can establish almost sure convergence (V F(x)) - a.s.) of the output of AG in Algorithm along the lines of (Bottou, 1998; Fisk, 1965; Métivier, 1982).
Note that to achieve [x]( T Fx(x) > 0 shown above, requires both the distance between (x) and the estimate of the honest update g and the distance between g and the expected output of Algorithm 2, i.e., Ex) are small. Let 02 denote the angle between F(x) and g. and let 8g de-
note the angle between g and Elg(x)), given by arg cos (
( and arg cos
Ela(x) [ ((Il)()(()))
respectively. If 01 + 0g < 4/2, then we have E[](x)] [F > 0. Following the arguments in Appendix B. almost sure convergence of Algorithm 3 is guaranteed
long as 01 + Oz < 4/2. This condition can be satisfied assuming 1) the public data donated by clients is representative of the underlying data distribution of honest clients, which controls 0,, and 2) the number of Byzantine
16

---

Under review as a conference paper at ICLR 2023
clients is sufficiently small, which controls 8z. We defer derivation of the explicit necessary condition for almost sure convergence to future work.
C DETAILS OF EXP3
The bandit feedback model considers the following iterate game.
Definition (Bandit setting). The player is given decision set [NV] At each iteration k I,..., K:
1. the player picks in E [AV].
2. the adversary picks loss vector gh.
3. the player observes and suffers the loss at index ig, i.e. th (ix).
Exp3, shown abstractly in Algorithm 4, enjoys employ Exp3 from both the perspective of a simulated server and simulated attacker to find a robust aggregation rule in Algorithm 2. In Appendix E we show how to convert the no-regret properties into a convergence guarantee.
called no-regret property in this setting. We
Algorithm 4 Exp3
Input: Updating rate À and X, iteration rounds K, N Initialize weight vector w w ()) = for 1,..., N.
for k 1 to K do
Set W Ei= (i), and for 1,..., N
w (2) W
1 N
p(i) = (1 A)
A
Draw randomly accordingly the probabilities p.
Receive loss ck:
Set for = 1....,N N
(1) = ( 1 (p/p()),
ifi= is otherwise.
0,
w w² (1)
D SIMULATION OF ADVERSARY
In this section, we show the simulation of the adversary. We term adversarial simulation as Attack Tailor, which outputs an appropriate AT at each iteration. The specific steps from the perspective of the adversary is shown in Algorithm 5. After observing n - honest gradients, server performs K-round simulation and obtains final probability distribution q. By sampling from q, the server selects an attack. Then, f Byzantine clients create and send the compromised gradients to the server. The steps for simulating the attack procedure summarized in Algorithm 6.
Importantly, the main difference between the adversary's 's simulation compared with that server is that the adversary does simulation based realistic honest gradients while the server has access only to noisy estimates of true gradients. Hence, unlike typical games and simulation setups, the adversary has an additional advantage the server, which is due information asymmetry.
17

---

Under review as a conference paper at ICLR 2023
Algorithm 5 AttackTaille
Input:
Updating rates λ1, λz, a1 and λ2 simulation rounds K, gradients of honest clients (g: Mi-1 A and F Initialize weight vector wi) = for E [M]] and wi for E [S]. for k = 1 to do
Set p (AG.) = (1 X1) (1)
for i L..... M. 21 (1) A1 M
Set q (AT,) = (1 - de) ΣS (*] + A for j = ,,..., S. Sample AG ~p" and AT* q² respectively.
(1()
Estimate the loss ex E(AG ATT, (g.).
for I....,M M
(i) I(AG, = AG"]
wI w (1) (1)
D*GA))
Set for = I....,S
G IÇTT, >T*
w2 w w (i) exx(((
("(AT)
Set for I....,M M
Σ (AT,) 9
K
Sample AT q. Output: AT.
Algorithm 6 Adversary's attack
Input: Learning rate 7h. workers, compromised workers, iteration rounds T, A and F
for t 1 to 1 do
Observe all gradients of honest workers {g: M
Call Algorithm to attack AT Attack Tailor( (g. J A.F).. Produce gradients for compromised clients. Set j E [f]
by (1' (2
Send compromised gradients (b,} to the server
E PROOF OF LEMMA
Proof. Defined i ~ P to be uniformly sampled from (ix) and ~ to be uniformly sampled from [ie) Using the no-regret property from (8),
1 K
E[((E,)) E
SE
L(ie. Jk)
+
R
K
k=1
(12)
K
1 R
EI = E
((i.i))
2E E
L(in, jk)
K
k=1
for any i [M] and j [S), where the expectation is taken over 7 and and the randomness of the algorithms. Subtracting the two equations,
1 K (Rk + Rkx =:
[(L().)) E.T())
(13)
Observe that by first evoking the incquality with ~ p and secondly with j ~ q. we see that (p. q) an e-approximate Nash equilibrium, i.c..
E(L(G,) E(L().)) ((L().)) +
(14)
18

---

Under review as a conference paper at ICLR 2023
We are interested in the i-players performance (() which relate the mixed strategy Nash equilibrium defined as Ei . & B j*)] & [[,(i,j*) where 1" ~ p and j q² By picking i ~ p" in (13) get,
B[L(,,) s B[L((,)) + (Rkx + Rkx)
K
1
B[T(("))) .5)
(R's RRk)
(15)
S B|
K (Rk + Rk),
where the last inequalities follows by the definition of a Nash equilibrium above. The claim follows by writing the expectation the RHS in terms of p" and q²
F PROOF OF LEMMA 3
Proof. Let both player and player in Lemma 1 employ the no-regret algorithm Exp3 such that Lemma 2 applies and consequently R and R. in (8) reduce
R2x 2 Mog M
(16)
R 2 KS log S.
Substituting (16) into Lemma 1, we have
Eg [L(1,)] & Eu-pra [166" ,"']l + Mog M + / log
(17)
K
Notice that Algorithm 2 is an instance of two simultaneously played Exp3 algorithms where = AG, j AT and ((i,j) = (AG, AT, (=/) It follows from (17) that
EaG,9 [T(AG, (1)) < EAG AT ~g 9 ((AG",AT AT", (E/H=
(18)
log M + Volog
VK
where AG is the average iterate defined in Algorithm 2. We concisely write the Nash equilibrium on the R.H.S. of (18) in terms of the payoff matrix L from Sim-MinMax defined componentwise as C(AG,AT = É(AG, AT, {g)" This completes the proof.
G EXPERIMENTAL DETAILS AND ADDITIONAL EXPERIMENTS
In this section, we provide the training hype-parameters and show a series of additional experiments.
G.1 DETAILS OF IMPLEMENTATION
Both MNIST (Lecun al., 1998) and FMNIST (Xiao al., 2017) datasets contain 60000 training samples and 10000 test samples. Each sample is 28 by 28 pixel grayscale image. The details of training sope-parameters are shown in Table The network architecture neural network with two fully connected layers (Leroux et al., 2016). The number of neurons is 100 and 10 for the first and second layer, respectively. All experiments have been run on cluster with Xeon-Gold processors and V100 GPUs.
fully connected
G.2 ADDITIONAL EXPERIMENTS
To further validate the performance of RobustTailor,, we set up additional experiments:
Training on datasets.
Non-iid settings with 3 different heterogeneous degree.
19

---

Under review as a conference paper at ICLR 2023
Table 1: Training Hyper parameters for Fashion- and MNIST
MNIST
FMNIST
CIFARIO
Learning Rate
0.01
0.003
0.002
Batch Size
50
50
80
Total Iterations
15K
10K
10K
Simulation Rounds
10
10
10
Å1. A2
0.3
0.3
0.3
d1. Ag
0.3
0.3
0.3
More Byzantines.
More aggregators (Geomed, Trimmedmean, Bulyan) added against single attack.
The impact of the proportion of public data.
Subsampling by the server
Dynamic strategy of the adversary.
Adversary with partial knowledge.
Different datasets. We train a CNN model on MNIST (Lecun et al., 1998), Fashion-MNIST (FMNIST) (Xiao et al., 2017) and CIFAR1O (Krizhevsky al., 2009) under iid setting. We summarize the training results against attacks here and they are consensus with the results shown in Section
(a) MNIST, 0.5
.NMSTS 100
(c) MNIST, Aailor
OPASCER
ORINORTT
(d) FMNIST, 0.1
(e) FMNIST, 100
(f) FMNIST, Attack Tailor
Caner
Creet
Croeet
(g) CIFARIO, e 0.1
(h) CIFARIO, 100
(i) CIFARIO, AttackTaile
Figure 6: iid setting three datasets. RobustTailor includes Krum and Comed. AttackTailor includes
0.1 0.1 5 and
100.
Non-iid settings. We also extend our consideration to more realistic settings with non-iid data distribution across clients. We the heterogeneous degree μ [0, 1] to represent the level of disparity among clients' local data. To be specific, we construct a setting, which 100p % of local data for each client is drawn in non-identical but independent manner from particular class
20

---

Under review as a conference paper at ICLR 2023
corresponding to the client index and 100(1 (4) % of the local data is drawn iid from all classes. A small j represents low disparity while large means significant disparity among clients. Fig. shows three non-iid settings including 0.1, 0.5, 0.9. We surprisingly observe that RobustTailor shows a satisfactory level of robustness even under heterogeneous data settings.
ROALE 3000
(a) 0.1, c 0.5
(b) μz = 0.1. c = 100
(c) μ = 0.1, TailorTailor
100
24
(d) 1r 0.5, 0.5
(e) μz 0.5,
J = 0.5, Attack
0.9. 0.5
(h) μ 0.9,
100
(i) p 0.9, AttackTTaiae
Figure 7: Non-iid setting, Larger μu means higher heterogeneous degree.
More Byzantines. Fig, 8 shows the results when there are 4 Byzantines in 12 total clients under three different attacks. Except the number of compromised clients, which is four instead of two, the setting is same as that in Fig. 1. We observe that both Krum and Comed are sensitive to the number of Byzantine clients while Robust is much more stable. Specifically, Krum has lower accuracy closing zero, and Comed shows more obvious fluctuations.
TSh-1 Ainton
1989 Wriden
(a) 0.5
(b) 100
Attack
Figure Byzantines. There are n = 12 total workers including f 4 Byzantine workers.
More aggregators against single attacks. To show the intuitive results of Robust we just construct the server's ' pool with two aggregators including Krum and Comed in the main text. However, Robust could outperform both Krum and Comed simultaneously when additional aggregators are put into the server's 's pool. Trimmedmean (TM) (Yin et al., 2018), Geomed (GM) (Pillutla et al., 2022), and Bulyan (Guerraoui et al., 2018) are also statistic-based -esiienn aggregators
21

---

Under review as a conference paper at ICLR 2023
and all of them can be added in RobustTailor. When Bulyan is included, each Bulyan aggregator uses different aggregator from Krum, Comed, TM, and GM for either the selection phase or in the aggregation phase. For each class, generate 16 aggregators, each with randomly generated 4 norm from one to 16. RobustTailor selects one aggregator from the entire pool of 64 aggregators based the simulation at each iteration. Moreover, centered clipping (CC) (Karimireddy al., 2021) as a history-aided aggregator was proposed recently and it can also be added in TobuustTailoo framework. Fig. shows results when more aggregators added into Robust framework and they perform better.
100
380
7021 ACCu/CO/111
Comed
63
Catt RocustbiorttGG0
110
Robuzthhlon
Robustlakori THI
RobustTboor Bulyon)
50
1/2
50
(a) 0.5
(b) 100
Figure More aggregators added into to Robust structure against single attacks.
Proportion of public data. Because Robust.ailor ask for clients to donate a small amount of data as the public dataset, we want to minimise data leakage as much possible while maintaining effectiveness. Therefore, detecting the impact of the proportion of public data is necessary. In our experiments, we assume every client donates 5% of data the server. Fig. 10 shows the performance of Robust Tailor with different proportion of public data under 3 attacks. Note that except for the proportion of public data, other settings of 3 figures Fig. 10 are the same as Fig. 1a, Fig. 1b, and Fig. 3 respectively. It is obvious that the amount of public data has little impact on Robust Tailor and even very small proportion of data donated by clients (e.g., 0.1% can help Robust Tailor achieve great performance. This also strongly proves Remark that the public dataset just need to represent clients' data distribution.
21
22
12
02
(a) é 0.5
(b) é 100
(c) AttackTailoo
Figure 10: The impact of the proportion of public data.
Subsampling by the server. Subsampling, a common technique in large-scale FL, can also increase the complexity of attacks. The server picks a subset of clients randomly and asks for updates at each iteration. The adversary can know which clients are selected and leverage the selected honest updates to design the attack for the compromised clients which are also chosen. Due to subsampling usually used in FL with large amount of clients, we run additional experiments with 120 clients, in which clients are Byzantines. The server chooses 10% of clients randomly for aggregation each iteration, and it assumes that 2 of 12 clients are compromised every iteration. Note that other settings of experiments are same as Fig. 1a, Fig. 1b, and Fig. in the paper except for learning rate. We decrease the learning rate from 0.01 to 0.001 because all aggregation methods are too unstable under the original setting. The results are shown in Fig. 11, which is consistent with the results without subsampling.
22

---

Under review as a conference paper at ICLR 2023
Creed
(a) 0.5
(b) c 100
(c) Attack Tailor
Figure Subsampling by adversary.
Dynamic strategy of the adversary. The adversary can also use a dynamic strategy that changes the number of malicious updates dynamically. The adversary picks 1-3 clients randomly to control at each iteration while the server still considers 2 Byzantines in 12 clients. Other settings are the same as Section Fig. 12 shows the results and Table compares them with the results without dynamic attack strategy in Section 5. Although some aggregation rules are impacted lightly by such dynamic attack strategy, RRobustTailo has good performance which is consistent with the original results.
Dlaed
(a) 0.5
(b) 100
(c) AttackTailor
Figure 12: Dynamic attack strategy of the adversary.
Table 2: Comparison between the adversary with and without dynamic strategy.
Attack
Aggregator
With dynamic attack
Without dynamic attack
RobustTailon
87. 97.49%
90.54%
c 0.5
Krum
84.37%
82.13%
Comed
72.80% 90.57%
72.07% 90.74%
Robust.Tailo
85.26% 91.62%
91.72%
100
Krum
93.88
94.74%
Comed 71.80% 88. 15%
71.72% 89.01 %
RobustTailor
90.17%
90.54%
AttackTailor
Krum
75.75%
81.68%
Comed
77.37% 88.05%
74.69% 89.69%
Adversary with partial knowledge. What we want to demonstrate in the main text is that RobustTailor can keep a great and stable performance even when facing a very strong adver- sary who has full knowledge of all honest clients. However, it is very hard for the adversary to have full knowledge of the model updates of all honest clients in reality. Although Fang et al. (2020) show that the partial knowledge attacks are weaker than the full knowledge attack's, s, it is still significant to consider more realistic attacks. For the partial knowledge setting, assume the adversary only knows the updates of two honest clients and design compromised gradients based them. Note that other settings are the same as Section We show the empirical results under both iid and non-iid (the heterogenous degree μ 0.9) settings in Fig. 13 and compares them against the adversary with full knowledge in Table 3. Most aggregation rules can perform least the same as the scenario of the adversary with full knowledge.
23

---

Under review as a conference paper at ICLR 2023
DRCNOOR Crreed
Creedd
(a) 0.3, iid
(b) 100, itd
(c) AttackTailor, itd
(d) c 0.5, non-iid
(c) 100, non-iid
(f) AttackTailor, non-iid
Figure 13: Adversary with partial knowledge.
Table Comparison between the adversary partial knowledge and with full knowledge.
(a) = 0.5
Attack
Aggregator
Partial
Full
Robust/aailr
89.27%
90.54%
iid
Krum
79.58%
82.
Comed
66.69% 90.65%
72.07% 90.74%
Robust
88.93%
87.54%
non-iid
Krum
73.50%
66.96%
Comed
80.85% 90.54%
81.84% 90.48%
(b) 100
Attack
Aggregator
Partial
Full
Robust.ailor
85.18% 92.31 %
91.72%
iid
Krum
94.74%
94.74%
Comed
69.83% 89.32%
71.72% 89.01%
RobustTailor
86.27% 92.03%
90.62%
non-iid
Krum
92.85%
92.85%
Comed
73.71% 89.75%
75.73% 89.38%
(c) AttackTailo
Attack
Aggregator
Partial
Full
RobustTailor
91.67%
90.54%
iid
Krum
91.77%
81.68%
Comed
67.13% 90.06%
74. 44.69% 88.69%
RobustTailor
91.51% %
90.26%
non-iid
Krum
90.60%
80.97%
Comed
73.53% 90.12%
74.39% 89.99%
H COMPUTATIONAL COMPLEXITY
The computational complexity bound depends the simulation of the inner loop (including sim- ulation rounds K, aggregator set A. and attack set F) and problem dimensions the outer loop (including number of clients and the dimension of gradients). We show the theoretical analysis
24

---

Under review as a conference paper at ICLR 2023
below and utilize empirical results to prove that it is worth to trade little more computational complexity for a great robust model.
Theoretical analysis For Mobusttaailo with K simulation rounds, our algorithm approaches a min-max equilibrium the best aggregation rule at the rate O OK-1//2). In addition, the computational cost of RobustTailor is influenced by the server's aggregation rules and the adversary's ss attacks. If clients submit d-dimensional vectors, Krum's 's expected time complexity is O(n²d) d) (Blanchard et al., 2017) and Comed's is O(nd) (Pillutla et al., 2022).
For more fine-graine complexity analysis, suppose (Ti...., TM } denote the number of elementary operations to run each aggregation rule within the set of M aggregation rules. The worst-case runtime complexity of Robust Tailor per simulation round is determined by max4e[M] T. However, the average complexity per round is the expected value of the number of elementary operations where the expectation is over the distribution of how likely each aggregator is chosen during simulation, which can be estimated empirically. Let us use p. to denote the probability of choosing A, The average complexity per round is given by T = ΣM 1= T.P:. Finally, the overall time complexity of Robust is given by O-/22)
Moreover, the number of elementary operations for simulation can be much smaller than applying the actual aggregator on the model during training assuming the size of the public data is very small, which is typically the case practice( (ooshida al., 2020; Zhao et al., 2018). Note that our algorithm just adds computation complexity to the server while all clients remain the same cost based on their models and datasets. Therefore, it is worthwhile to trade slightly longer training time for significantly improved training procedure w.r.t. robustness.
Empirical results We show computation costs and accuracy for different aggregation rules after running 15k iterations in reality, whose results are also shown in Fig. 1. We can see that Robust still maintains stable and high accuracy when facing powerful adversary although it needs more computation time. However, Krum cannot reach a high accuracy and Comed shows a very unstable performance with lots of fluctuations when facing strong adversary with AttackTailor. We note that compared with undesirable models of Krum and Comed, Robust Tailor improves accuracy and stability drastically at the cost of slightly increased training time.
Table 4: Computational Complexity based MNIST after running 15k iterations
Aggregator
Time
Accuracy
Omniscient
34 min
96.63%
Robust
96 min
85,87%
Krum
37 min
82.13%
Comed
52 min
90.74%
(a) = 0.5
Aggregator
Time
Accuracy
Omniscient
34 min
96.63% %
RobustTaailo
96 min
92.03%
Krum
37 min
94.74%
Comed
52 min
60.39%-88.80 88%
(b) c 100
Aggregator
Time
Accuracy
Omniscient
34 min
96.63%
Robust
190 min
89.72%
Krum
90 min
80.98%
Comed
121 min
11.34%--9.775%
(c) AttackTailor
25


Reviews:
[{"review_id": "xjsNhdnzX9", "reviewer": "Reviewer_vXe3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose an attack on federated learning where a subset f clients are compromised. The problem is formulated as a game where both players use a no-regret learning algorothm to converge to the NE. The game is simulated, as the defender does not know the true updates of compromised clients.", "summary_of_the_review": "A good overall idea, but I am not sure of claims made in the paper being novel or interesting.", "strength_and_weaknesses": "I am surprised that no-regret algorithm converging to NE in a two player zero-sum game is presented as a new result. This is a very well-known result, and appears in lecture notes and tutorials also, e.g., see page 33 in https://algo.cs.uni-frankfurt.de/lehre/agt/winter1920/folien/correlated.pdf\n\nI believe a main purpose of federated learning is to preserve privacy of private data-sets. The assumption of the server having access to a dataset from every client (even one that mimics client data distribution but is not the actual data) is a loss of privacy. The authors have cited a number of previous works to support this (sorry, I have not read these cited papers), but have not really discussed why this kind of access to dataset is fine from a privacy perspective. Please provide a detailed response to this question.\n\nI am bit lost in notations, but is there some assumption about \\tilde{g} such as unbiased estimate? Along similar lines, isnt there some assumption about the simulation that could relate Sim-MinMax to MinMax. Solving Sim-MinMax is fine only if that is close (close in some sense that must be defined) to MinMax.\n\nMinor point: the footnote on page 1 refers to an experiment in the appendix, if this point was important to mention in Introduction, maybe this experiment should be in main paper.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "vX2wrHD09y", "reviewer": "Reviewer_rcbh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a game theoretic model to study defense against adversarial attacks in federated learning. The task of designing a robust learning algorithm against potential attacks is formulated as the problem of computing a good strategy in a game. The authors presented bandit algorithms to compute the equilibrium of the game as well as several results about the theoretical guarantee of the algorithm. Experiments were also conducted to evaluate the performance fo the algorithm and the quality of solutions it generates.", "summary_of_the_review": "A well-presented paper on a well-motivated problem, with some novelty in the specific literature. Results look sound but a bit thin on the theoretical side. ", "strength_and_weaknesses": "Strength: The paper studies an interesting and well-motivated problem and takes effort to model it and formulate it as a game. The paper is clear and easy to follow and results look complete.\n\nWeakness: Theoretical contribution is a bit thin. The model looks a bit simplistic and hence more like one \"on paper\". Some assumptions are a bit too strong. For example, the assumption that both players choose their algorithms from finite sets known to each other is a bit too strong, and seems more for the sake of formulating the problem as a normal-form game. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lf-nyta09cq", "reviewer": "Reviewer_GvuQ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a two-player zero-sum game for model poisoning attack and defense in federated learning. A powerful attacker with full knowledge of the FL system is considered, where the attacker controls a set of malicious devices that can share manipulated model updates with the server to lower the accuracy of the global model. In each FL iteration, the defender picks a defense rule randomly from a pool of robust aggregation-based defense algorithms by simulating the attacker's behavior using a small set of public data shared by honest devices. Similarly, the attacker picks an attack algorithm from a pool of attacks by simulating the defender's behavior using its knowledge of honest devices and the FL system. The paper formulates the attack-defender interaction in each FL iteration as a zero-sum game and adapts the Exp3 algorithm to solve the game on each side. Convergence analysis is provided together with a set of empirical results. ", "summary_of_the_review": "The paper proposes a game-theoretic framework to model poisoning attacks and defenses in federated learning where both the attacker and the defender adapt their behavior dynamically by simulating the behavior of the other side. Similar ideas have been considered in cybersecurity and adversarial learning. Although its application in federated learning seems new, the proposed method has strong limitations and relies on unrealistic assumptions. \n", "strength_and_weaknesses": "The idea of switching defense policies dynamically to increase the attacker's uncertainty in adversarial machine learning has been considered before, although in a slightly different context [1]. The game theoretic model seems straightforward but reasonable. The main novelty of the paper is to simulate malicious devices' behavior using a small amount of honest data. However, the proposed method has some strong limitations. \n\nFirst, from Algorithm 1, it is clear that the paper only considers non-adaptive attacks and defenses where a fixed rule is applied in each iteration. This can also be seen from the myopic loss function defined in (6). However, adaptive algorithms have been developed for both defenses [2,3] and attacks [4] in federated learning. Neither the algorithmic framework nor the analytic result in the paper applies to adaptive attacks or defenses.  \n\nSecond, the paper ignores that most poisoning attacks and defenses have a set of adjustable hyperparameters that significantly affect their strength, making the possible attacks (and defenses) a very large or infinite set. The proposed solution only works for the finite case and suffers from a high complexity for large sets of attack and defense strategies. The experiments in Section 5 only consider a very small configuration with two defenses and two attacks with fixed parameters. Although more defenses are considered in Figure 8 in the appendix, the defense strategy is sampled from the pool uniformly at random without using the proposed solution. \n\nThird, the game formulation ignores subsampling, a commonly used technique in large-scale federated learning. An advanced attacker will adapt its strategy according to the subset of malicious devices sampled in each iteration, creating another level of complexity unconsidered in the paper. \n\n[1] Sengupta, Sailik, Tathagata Chakraborti, and Subbarao Kambhampati. Mtdeep: Moving target defense to boost the security of deep neural nets against adversarial attacks. International Conference on Decision and Game Theory for Security. 2019. \n\n[2] Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. Advances in Neural Information Processing Systems(NeurIPS), 31, 2018\n\n[3] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning(ICML), 2021\n\n[4] Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. Fltrust: Byzantine-robust federated learning via trust bootstrapping. In NDSS, 2021\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "SPJwa_cGp9", "reviewer": "Reviewer_ovJ3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a minimax formulation to model the attacks and defenses in federated machine learning. The aggregator is an agent who wants to maximize the accuracy in presence of Byzantine clients, where the Byzantine clients want to corrupt the performance of the aggregated model. Therefore, federated learning with Byzantine attacks can be viewed as a two-player zero-sum game. To estimate the loss value for the two players, the paper proposed using public dataset to construct a simulator of the environment. To further reduce the computational time, the authors considered using bandit feedback, in which only the loss for the selected aggregator and tailored attack is observed. Fortunately, by using no-regret bandit algorithms, the averaged historical policy converges to some Nash Equilibrium, and thus the output aggregator selection policy is optimal in the sense of NE. The paper provided extensive experimental results and demonstrate that the proposed defense can indeed improve the robustness of federated learning against Byzantine attacks.", "summary_of_the_review": "I worked in related areas.", "strength_and_weaknesses": "Strength:\n\n(1) This paper captured a very interesting observation in game theory that the averaged historical policy produced by no-regret learners can approximate a Nash Equilibrium when the game is played repeatedly. This is a very cute idea that naturally matches the federated learning problem in presence of Byzantine attacks. The methodology is also novel in the federated learning domain.\n\n(2). The paper provided strong and extensive empirical results and demonstrated that the proposed defense indeed enhances the robustness of federated learning against training-time attacks.\n\nWeaknesses:\n\n(1). Most theoretical results in this paper are not novel. In particular, The Lemma 1 and 2 are both existing results in the game theory and multi-armed bandit domain. The Lemma 3 is somewhat novel, but it seems to be an easy application of Lemma 1 and 2. Therefore, while the paper provided theoretical guarantees, the results are not surprising or novel enough to me. Besides that, I think in a lot of places, the paper missed a min operator, e.g., in the regret definition (8) and also (10). Please add the min operator to avoid confusion.\n\n(2). The paper relied on a public dataset to construct some simulator, and then uses the simulator to obtain estimated loss/reward for the aggregator and attacker. Therefore, the regret that Algorithm 2 tries to minimize is actually the objective on the public dataset, instead of the ground-truth environment. Although the authors provided several papers to support this assumption of having a simulator, I am kind of \ncurious what if there is a distribution gap between the public dataset and the global environment. It would be interesting to discuss this problem and provide some empirical study.\n\n(3). I believe the authors should consider using EXP3.P instead of EXP3 to do experiments. This is because although EXP3 achieve no regret, it requires an important condition that the loss functions over time are pre-determined before the game starts. However, in this paper, the attacker can be adaptive to the behavior of the aggregator over time. That means the policy q_t selected by the adversary can depend on the historical p_t selected by the aggregator. As a result, the loss function for the aggregator at time t is p*E(L)*q_t^T also depends on the historical p's (i.e., p_1, ..., p_{t-1}), and thus is not determined beforehand. The EXP3 does not provide strict theoretical guarantee in this case. Instead, the EXP3.P would work.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject