Provable Federated Adversarial Learning via Min-max Optimization
Authors: Xiaoxiao Li
Zhao Song
Jiaming Yang
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning
Adversarial Training
Optimization
Non-Convex

Abstract: Federated learning (FL) is a trending training paradigm to utilize decentralized training data. FL allows clients to update model parameters locally for several epochs, then share them to a global model for aggregation. This training paradigm with multi-local step updating before aggregation exposes unique vulnerabilities to adversarial attacks. Adversarial training is a trending method to improve the robustness of neural networks against adversarial perturbations. First, we formulate a \textit{general} form of federated adversarial learning (FAL) that is adapted from adversarial learning in the centralized setting. On the client side of FL training, FAL has an inner loop to optimize an adversarial to generate adversarial samples for adversarial training and an outer loop to update local model parameters. On the server side, FAL aggregates local model updates and broadcast the aggregated model. We design a global training loss to formulate FAL training as a min-max optimization problem. Unlike the convergence analysis in centralized training that relies on the gradient direction, it is significantly harder to analyze the convergence in FAL for two reasons: 1) the complexity of min-max optimization, and 2) model not updating in the gradient direction due to the multi-local updates on the client-side before aggregation. Further, we address the challenges using appropriate gradient approximation and coupling techniques and present the convergence analysis in the over-parameterized regime. Our main result theoretically shows that the minimal value of loss function under this algorithm can converge to $\epsilon$ small with chosen learning rate and communication rounds. It is noteworthy that our analysis is feasible for non-IID clients.

Under review as a conference paper at ICLR 2022
PROVABLE FEDERATED ADVERSARIAL LEARNING VIA MIN-MAX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) is trending training paradigm to utilize decentralized training data. FL allows clients update model parameters locally for several epochs, then share them to global model for aggregation. This training paradigm with multi-local step updating before aggregation exposes unique vulnerabilities to adversarial attacks. Adversarial training is trending method to improve the robustness of neural networks against adversarial perturbations. First, we formu- late general form of federated ad adversarial learning (FAL) that is adapted from adversarial learning in the centralized setting. On the client side of FL training, FAL has inner loop to optimize an adversarial to generate adversarial samples for adversarial training and an outer loop to update local model parameters. On the server side, FAL aggregates local model updates and broadcast the aggregated model. We design a global training loss to formulate FAL. training as a min-max optimization problem. Unlike the convergence analysis centralized training that relies on the gradient direction, it is significantly harder to analyze the convergence in FAL. for three reasons: 1) the complexity of min-max optimization, 2) model not updating in the gradient direction due to the multi-local updates on the client- side before aggregation and 3) inter-client heterogeneity. Further, we address the challenges using appropriate gradient approximation and coupling techniques and present the convergence analysis in the over-parameterized regime. Our main result theoretically shows that the minimal value of loss function under this al- gorithm can converge to e small with chosen learning rate and communication rounds. It is noteworthy that analysis is feasible for non-III clients.
INTRODUCTION
Federated learning (FL) is playing an important role nowadays, it allows different parties or clients to collaboratively train deep learning models without sharing private data. One popular FL paradigm called FedAvg (McMahan et al., 2017) introduces an masy-to-implena without data sharing. Specifically, it requires a central server to aggregate model updates computed by the local participants (also known nodes or clients) using local imparticipable private data. Then the central server aggregates these updates to train a globally learned model.
distributed learning method
Nowadays deep learning model are exposed to severe threats of adversarial samples. Namely, small adversarial perturbations on the inputs will dramatically change the outputs or output wrong an- swers (Szegedy et al., 2013). this regard, much effort has been made improve neural networks' resistance to such perturbations using adversarial learning (Tramèr et al., 2017; Samangouei et al., 2018: Madry et al., 2018). Among these studies, the adversarial training scheme in Madry et al. (2018) has achieved the good robustness in practice. Madry et al. (2018) proposes an adversarial training scheme that uses projected gradient descent (PGD) to generate alternative adversarial sam- ples as the augmented training set. Generating adversarial examples during neural network training is considered as one of the most effective approaches for adversarial training up to now according to the literature (Carlini & Wagner, 2017; Athalye al., 2018; Croce & Hein, 2020).
Although adversarial learning has attracted much attention in the centralized domain, its practice in FL is under-explored (Zizzo et al., 2020). Like training classical deep neural networks that use gradient-based methods, FL paradigms are vulnerable to adversarial samples. Adversarial learning in FL. brings multiple open challenges due to FL properties low convergence rate, application

---

Under review as a conference paper at ICLR 2022
in non-lll environments, and secure aggregation solutions. Hence applying adversarial learning in an FL paradigm may lead to unstable training loss and a lack of robustness. However, a recent practical work Zizzo et al. (2020) observed that although there exist difficulties of convergence, the federation of adversarial training with suitable hyperparameter settings can achieve adversarial robustness and acceptable performance. Motivated by the empirical results, we want to address the provable property of combining adversarial learning into FL from the theoretical perspective.
This work aims theoretically study the unexplored convergence challenges that lie in the interac- tion between adversarial training and FL. To achieve a general understanding, we consider general form of federated adversarial learning (FAL), which deploys adversarial training scheme on local clients in the most common FL paradigm, FedAvg (McMahan et al.. 2017) system. Specifically, FAL. has an inner loop of local updating that generates adversarial samples (i.e., using Madry et al. (2018) 8)) for adversarial training and an outer loop to update local model weights on the client side. Then global model is aggregated using FedAvg (McMahan et al., 2017). The algorithm is detailed in Algorithm I.
We are interested in theoretically understanding the proposed FAL scheme from the aspects of model robustness and convergence:
Can federated adversarial learning fit training data robustly and converge with a feasibly sized neural network?
The theoretical convergence analysis of adversarial training itself is challenging in the centralized training setting. Tu et al. (2018) recently proposed a general theoretical method to analyze the risk bound with adversaries but did not address the convergence problem. The investigation of conver- gence on over wee-pparmeterrize neural network has achieved tremendous progress (Du et al., 2019a; Allen-Zhu et al., 201 10;;;;; Du et al., 2019b; Arora et al., 2019b). The basic statement is that training can converge to sufficiently small training loss in polynomial iterations using gradient descent or stochastic gradient descent when the width of the network is polynomial in the number of training examples when initialized randomly. Recent theoretical analysis (Gao et al., 2019; Zhang et al., 2020b) extends these standard training convergence results to adversarial training settings. To an- swer the above interesting but challenging question, we formulate FAL as min-max optimization problem. We extend the convergence analysis on the general formulation of weer-parameterized neural networks in the FL setting that allows each client to perform min-max training and generate adversarial examples (see Algorithm 1). Involved challenges are arising in FL convergence analysis due to its unique optimization method: 1) unlike classical centralized setting, the global model of FL does not update in the gradient direction; 2) inter-client heterogeneity issue needs to be considered.
Despite the challenges, we give an affirmative answer the above question. To the best of our knowledge, this work is the first theoretical study that examines these unexplored challenges on the convergence of adversarial training with FL. The contributions of this paper are:
We propose a framework to analyze a general form of FAL in wer-paarmeeterized neural networks. We follow natural and valid assumption of data separability that the training dataset are well separated apropos of the adversarial perturbations' magnitude. After suffi- cient rounds of global communication and certain steps of local gradient descent for each t, we obtain the minimal loss close to zero. Notably, our assumptions do not rely on data distribution. Thus the proposed analysis framework is feasible for non-IlID clients.
We are the first to theoretically formulate the convergence of the FAL problem into a min- max optimization framework with the proposed loss function. In FI., the update in the global model is no longer directly determined by the gradient directions due to multiple local steps. To tackle the challenges, we define a new 'gradient', FL gradient. With valid ReLU Lipschitz and over wee-parameterized assumptions, we use gradient coupling for gra- dient updates in FL to show the model updates of each global updating is bounded in federated adversarial learning.
Roadmap The rest of the paper is organized as follows. We overview the related work on federated learning and adversarial training in Section 2. We describe the problem formulation for the federated adversarial learning algorithm and introduce the notations, assumptions to be used, and conditions to be considered to ensure convergence in Section 3. Our main convergence result is presented in
2

---

Under review as a conference paper at ICLR 2022
Section 4. In Section 5, we present the core techniques and an overview of the proof. We summarize and conclude our results in Section
RELATED WORK
Federated Learning efficient and privacy-preservee way to learn from the distributed data collected on the edge devices (a.k.a clients) would be FL. FedAvg is easy-to mas-tooimplemmnt distributed learning strategy by aggregating local model updates on the server side and transmitting the averaged model back to local clients. Later, many FL methods are developed baed on FedAvg. Theses FL schemes can be divided into aggregation schemes (McMahan et al., 2017: Wang et al., 2020; et al., 2021) and optimization schemes (Reddi et al., 2020; Zhang et al., 2020a). Nearly all the them have the common characteristics that client model are updating using gradient descent-based methods, which is venerable adversarial attacks. In addition, data heterogeneity brings in huge challeng in FL. For IID data, FL has been proven effective. However, in practice, data mostly distribute as non-IID. Non-IID data could substantially degrade the performance of FL models (Zhao al., 2018; Li al., 2019; 2021; 2020a). Despite the potential risk in security and unstable performance in non- IID setting, as FL mitigates the concern of data sharing, is still a popular and practical solution for distributed data learning in many real applications, such as healthcare (Li et al., 2020b; Rieke et al., 2020), autonomous driving (Liang et al., 2019), IoTs (Wang et al., 2019; I Lim et al., 2020).
Learning with Adversaries Since the discovery of adversarial examples (Szegedy et al., 2013), to make neural networks robust to perturbations, efforts have been made to propose more effective de- fense methods. As adversarial examples are an issue of robustness, the popular scheme is to include learning with adversarial examples, which can be traced back to (Goodfellow al., 2014). It pro- duces adversarial examples and injecting them into training data. Later, Madry et al. (Madry et al., 2018) proposed training on multi-step PGD adversaries and empirically observed that adversarial training consistently achieves small and robust training loss in wide neural networks.
Federated Adversarial Learning Adversarial examples, which may not be visually distinguish- able from benign samples, are often classified. This poses potential security threats for practical machine learning applications. Adversarial training (Goodfellow et al., 2014; Kurakin et al., 2016) a popular protocol to train more adversarial robust models by inserting adversarial examples in training. The use of adversarial training in FL presents number of open challenges, including poor convergence due to multiple local update steps, instability and heterogeneity of clients, cost and security request of communication, and on. To defend the adversarial attacks in federated learning, limited recent studies have proposed to include adversarial training on clients in the lo- cal training steps (Bhagoji et al., 2019; Zizzo et al., 2020). These two works empirically showed the performance of adversarial training. The theoretical analysis of convergence is under explored. In addition, (Zhang et al., 2021) proposed an adversarial training strategy in classical distributed setting, not meeting the specialty in FL.
Convergence via over-parameterization Convergence analysis on over-parameterrize neural networks falls in two lines. In the first line of work (Li & Liang, 2018; Allen ZZu et al., 2019b;c;a), data separability plays crucial role in deep learning theory, especially in showing the convergence result of over-vvrraeee wver-parameterized neural network training. Denote ó as the minimum distance between all pairs of data points. Data separability theory requires the width (m) of the neural network is least polynomial factor of all the parameters (i.e. m 2 poly (n, d. 1/5)). where n is the number of data points and is the dimension of data. Another line of work (Du al., 2019b; Arora al., 2019a;;; Song & Yang, 2019; Lee et al., 2020) builds on neural tangent kemel (Jacot et al., 2018). It requires the minimum eigenvalue (A) of the neural tangent kernel to be lower bounded. Our analysis focuses on the former approach based on data separability.
Robustness of Federated Learning Previously there were several works that theoretically ana- lyzed the robustness of federated learning under noise. Yin et al. (2018) developed distributed opti- mization algorithms that were provably robust against arbitrary and potentially adversarial behavior in distributed computing systems, and mainly focused on achieving optimal statistical performance. Reisizadeh al. (2020) developed robust federated learning algorithm by considering a structured
3

---

Under review as a conference paper at ICLR 2022
affine distribution shift in users' data. Their analysis was built several assumptions the loss functions without a direct connection to neural network.
PROBLEM FORMULATION
To explore the properties of FAL in deep learning, we formulate the problem wver-parameterized neural network regime. We start by presenting the notations and setup required for federated adver- sarial learning, then we will describe the loss function we use and our FAL algorithm.
The rest of this section is organized as follows. In Section 3.1 we introduce the notations to be used. In Section 3.2 we state the assumptions on the dataset and initialization values. In Section 3.3 we formally describe our FAL algorithm (Algorithm 1) to be investigated.
3.1 NOTATIONS
For vector x, we use ||>||p to denote its lp norm, in this paper we mainly consider the situation when p 1, 2, or co. For matrix W E Rdxm we use W T to denote its transpose and use tr[W] to and [ p denote the entry-wise & norm, spectral norm and Frobenius norm of W respectively. For each j E [m]. we let W, E R be the j-th column of W. We let ||W]|2,1 denotes Σラ= [|W and 2 denotes maxje[m) [|W We denote Gaussian distribution with mean y and covariance Σ as M(,, E). use (-) to denote the ReLU function (2)) max 0}, and use 1 {E) to denote the indicator function of event E.
denote its trace. We use [| ||
3.2 PROBLEM SETUP
Two-layer ReLU network in FAL Following recent theoretical work in understanding neural networks training in deep learning (Du et al., 2019b; Arora et al., 2019a;;; Song & Yang, 2019; Lee et al., 2020), in this paper, we focus on two-layer neural network that has m neurons in the hidden layer, where each neuron a ReLU activation function. We define the global network as
fo(x) = = ar ((U,, b,)
(1)
and for e E [N], we define the local network of client as
fw. fw. := Σ ar ((Wer,, x)) + br).
Here U (UI...., Un) E Rdxm is the global hidden weight matrix, We (We......, W.m. Rdxm the local hidden weight matrix of client c, and (aI...., am) 1T denotes the output weight vector, b = (bi...., bm)) E R denotes the bias vector. During the process of federated adversarial learning, we only update U and W, keeping and equal their initialization values, so we can write the global network as fo (I) and the local network as fw, (I). For the situation we don't care about the weight matrix, we write [=) or fe(x) for short.
Next, we make some standard assumptions regarding our training set. Definition 3.1 (Dataset), There are N clients and n NJ data in total. Let S = UcENN where }} C Rd x R denotes the J training data of client c. Withou loss
S. = ( Ve.,)...., (F..J, J) of generality, we assume that for all e [N]. [J], || ll2 and the last coordinate of each point equals to 1/2, so we consider X {i Bd || 1, FA 1/2). For simplicity, we also assume that for all E [N].j E [J], |y-g 1.2
We now define the initialization for the neural networks.
Without loss of generality, assume that all clients have same number of training data. Our result can be generalized the setting where each elient has different number of data as the future work.
*Our assumptions on data points are reasonable since can do scale-up. In addition, l2 norm normalization is typical technique in experiments. Same assumptions also appears in many previous theoretical works like Arora et al. (2019h); Allen-Zhu et al. (2019a;h).
4

---

Under review as a conference paper at ICLR 2022
Definition 3.2 (Initialization). The initialization of R U E Rdxm, E Rm is a(0) R", (0) E Raxmm b(0) E RR.. The initialization of client c's local weight matrix We is (0,00) = U()). Here the second term in W. denotes iteration of local steps.
For each [m], (0) are i.i.d sampled from [-1/m , //mm uniformly.
For each E [d]r [m]] (2) and by (0) are i.i.d. random Gaussians sampled from (O, 1/m). Here Ug.r means the (d, -entryy of
For each global iteration t
[T].
For each e E [N], the initial value of client c's local weight matrix We is Wa(t, 0) = (t).
Next we formulate the adversary model that will be used.
Definition 3.3 (p-Bounded adversary). Let F denote the function class. An adversary is mapping A: F x X x + X' which denotes the adversarial perturbation. For p > O, we define the & ball as B2 p) [I Rd 1 x|I2 S p} N, say adversary A is p-bounded if satisffes Aff E B2(x.p). Moreover, given p > O, we denote the worst-case adversary as A" = (r.. (((()),)) v), where l is loss funcctinn defined in Definition 3.5.
Well-separated training sets In the over over--aramees parameterized regime, it is standard assumption that the training set is well-separated. Since we deal with adversarial perturbations, we require the fol- lowing 7-separability, which is bit stronger.
Definition 3.4 (y-separabilitty. Let E (0, 1021 ā E (0, (0,1/2) denote three parame- ters such that y S 6--65-p)), We say our training set S = U = (ee Ve.)} c Rd x & is globally 7-separable w.rt p-bounded adversary, if | Tenda ll2 2 8 holds for any C1 02 and j1 + jz.
is worth noting that, our problem setup does not require the assumption on independent and identically distribution (IID) on data, thus such formation be applied unique challenge of the non-llD setting in FL.
3.3 FEDERATED ADVERSARIAL LEARNING
Algorithm We focus general FAL framework that is adapted from the most common adver- sarial training in the classical setting on the client. Specifically, we describe the adversarial learning of a local neural network fw. against an adversary A that generate adversarial examples during training as shown in Algorithm 1. As for the analysis of general theoretical analysis framework, we do not specify the explicit format of A.
The FAI. algorithm contains two procedures: one is CLJENTUPDATE running client side and the other is SERVER EXECUTION running on server side. These two procedures are iteratively processed through communication iterations. Adversarial training addressed in procedure CLIENTUPDATE. Hence, there are two loops CLIENTUPDATE procedure: the outer loop iteration for local model updating: and the inner loop is iteratively generating adversarial samples by the adversary A. In the outer loop in SERVEREXEcUTION procedure, the neural network's parameters are updated to reduce its prediction loss on the new adversarial samples.
Adversary and robust loss We set the following loss for the sake of technical presentation sim- plicity, customary in prior studies Gao et al. (2019); Allen-Zhu al. (2019a):
Definition 3.5 (Lipschitz convex loss), A loss function &. IR x IR I is said to be Lipschitz convex loss if satisfies the following four properties:
non-negative;
convex with respect to the first input of
1 Lipshcitz, which means [[((11, v1) - l(x2, U2) (1(1,,1)) - (x2, v2)
Evy v) 0 for all y E IR.
5

---

Under review as a conference paper at ICLR 2022
Algorithm Federated Adversarial Learning (FAL)
Notations: Training sets of clients with each client is indexed by c, S, {( Me.i [ adver- sary A; local learning rate Mocali global learning rate Nglobal's local updating iterations K; global communication round T.
1: Initialization a(0) E _. (0) E 1dxm b(0) 1n
2: For = - T, we iteratively run Procedure then Procedure B
3: procedure A. CLIENTUPDATE(t...
4: S.(t) <
5: Woll, 0) U()
Receive global model weights update.
6: for = K-1 do
7:
for j=j=1 =
8:
[2j - A((fw. Beft Ve.))
Adversarial samples. fw. is defined as (2).
9:
S,(t) + S.(t) U (32) (....B. ye.5)
end for
11:
Wo(t, k 1) + (o(t, Mocal Vw. (((())
12: end for
13: AUA(t) We(t, K) ((t)
14:
Send (t) to SERVEREXECUTION
15:
end procedure
16: procedure B. SERVEREXECUTIONG]
for each client e in parallel do do
18:
AU.(t) + CLIENTUPDATE(C))
Receive local model weights update.
(U - N ECEIN (t.(t)
20:
Ult - 1) +- (t)) Nglobal (U
Aggregation on the server side.
21:
Send (tt 1) to client for CLIENTUPDATE(C..)
22:
end for
23:
end procedure
In this paper assume is Lipschitz convex loss. Next, define robust loss function of neural network, which is based on the adversarial examples generated by a p-bounded adversary A.
Definition 3.6 (Training loss). Given client's training set Se { { Mes'l C Rd TR. of
examples, the standard training loss of a neural net fe .dd + defined as L(Se, S.) =
$ E e ((fo(ee)) (((ee)) No.).. Given S = SeeINISo we define the global loss as L(fu, S) == NJ Em Ej=1 (ff((Te)) Mes)- Given p-bounded adversary A, we define the global loss with respect to A as
N
J
1 N J
Ca(fu) = NJ
Σ
Σ
Be.)), (e.))
(fu Ve.5)
NJ
c=ii=1
and also define the worst-case global robust loss
C.. (fv) NJ ΣΣ
1 -I ((fo Iess Ies: Ves)). Ne.) NJ ΣΣ 22, (Be
l (fu(x'a)) (.ea))))))
Moreover, since we deal with pseudo-net which is defined Definition 5.1, we also de- fine the loss of pseudo-net as L(ge,Se) = 5 8l (go(xas) Mos) and L(gu, NJ EN Ejen Elgu (Fe.), Veg).
OUR RESULT
The main result of this work is showing the convergence FAL algorithm (Algorithm 1) in overpa- rameterized neural networks. Specifically, our defined global training loss (Definition 3.6) converges to small with the chosen communication round T,, local and global learning rate Mocal, Nglobal- plausible to see that we can control Moral according to the local update steps K to achieve convergence. We now formally present main result Theorem 4.1.

---

prove the minimum of Under review as a conference paper at ICLR 2022
Theorem 4.1 (Federated Adversarial Learning.. Let co E (0.1) be fixed constant. Let N denotes the total number of clients and J denotes the number of data points per client. Suppose that our training set S S is globally y-separabble for some & 0. Then, for all (0,1), there exists R = poly((NJJfe)//) that satisfies: for all m 2 poly(d, (NJ/e) for every K 2 and T 2 poly(R/e), with probability at least exp( exp(-S((m1/3) over the randomness of a(0) E RR", (0)) E Rddm b(0) E IR", running federated adversarial learning (Algorithm 1) with step size choices Nglobal = 1/ (, R,,,R111 1/e) and Mocal = 1/K will output a list of weights (2) ((()) Rdxm that satisfy
min Ca(fo() Sc. [E[T]
5 PROOF SKETCH
To handle the min-max objective in FAL, we formulate the optimization of FAL in the framework of online gradient descent at each local step on the client side, firstly the adversary generates adversarial samples and computes the loss function & (Jw. (t.k) (t)). then the local client learner takes the fresh loss function and update (t, k 1) W.(t, k) nocal Vw. C (fw.(t.)) S,(t))-
Compared with the centralized setting, the key difficulties in the convergence analysis of FL are induced by multiple local updates the client side and the updates both local and global sides. Specifically, local updates are not the standard gradient as the centralized adversarial training when K 2. We used (t) in substitution of the real gradient of U update the value of (t). This brings in challenges to bound the gradient of the neural networks. Nevertheless, gradient bounding challenging in adversarial training solely. To this end, we use gradient coupling method twice to solve this core problem: firstly we bound the difference between real gradient and FL gradient (defined below), then we bound the difference between pseudo gradient and real gradient.
5.1 EXISTENCE OF SMALL ROBUST LOSS
In this section, denote Ô (0) the initialization of global weights U and denote Utt as the global weights of communication round I. U is the value of U after small perturbations from U which satisfies - - Ü 2, < R/mm", here E (0, 1) is a constant (e.g. C1 = 2/3), m is the width of the neural network and R is parameter. We will specify the concrete value of these parameters later in appendix.
We study the over- over-parannnn peer-parameerizeed neural nets' -pp-xxppro pseudo- descent for over- peeettrraeter neural nets whose weights are close to initialization. Pseudo-network can be seen as a linear approximation of our two layer ReLUU neural network near initialization, and the introducing of pscudo-netwee network makes the proof more intuitive.
learn gradient
Definition 5.1 PPscudo-networks Given weights U E Idxm, a E Ih'h and b E , a neural nerwork fo (x) m ar (UUr, x) by). we define the corresponding pseudo-network gu Fd RR as gu = Em= O, (U) (,) ((),- x) + b, 2 0}.
Existence of small robust loss In order to obtain our main result, we first show that we can find a U which is close to (0) and also makes LA (fu-) sufficiently small. Later in Theorem 5.6 we show that the average of La(fu()) is dominated by LA- (fu-), ), thus (A(S)() is small.
Theorem 5.2 (Existence, informal version of Theorem F.3). For all e (0, 1), there exists Mo poly(d, (/e)))//) and R (o))((NJ/e))/)) such that for every 2 Mo. with high probability there exists U* E [ddxm that satisfies ||U* U (0) S R/mm> and L (fu-) S..
5.2 CONVERGENCE RESULT FOR FEDERATED LEARNING
For ease of presentation, we first describe the notions of local and global gradients in our federated adversarial learning setting.
We refer our readers Hazan (2016) for more details regarding online gradient descent.
7

---

Under review as a conference paper at ICLR 2022
Definition 5.3 (Gradient). For a local real network fwa(t.)), we denote its gradient by (ifes t,.,kk))
Vw, Tw.f(J.ct..s S.())) If the corresponding pseudo-network is Iw.lt.k) then denote the pseudo- network gradient by (ge: k) == Vw. [W
Now we consider the global network. We define pseudo gradient as V(g.t) = Vo S(t)) and define FL gradient as (J,( == N (t)... which is used in the proof of Theorem 5.6. We
present our gradient coupling methods in the following two lemmas.
Lemma 5.4 (Bounding the difference between real gradient and FL gradient, informal version of
Lemma E.4). With probability least 1 exp(-9(mm")) over the initialization, for iterations I
such that (t) - 2,) I 1/((m), the gradients satisfy [[V(f.t V 1l222 S o(m).
Lemma 5.5 (Bounding the difference between pseudo gradient and real gradient, informal version of Lemma E.5). With probability at least 1 exp(- (() over the initialization, for iterations I such that ([((()) - (0) S 1/o(m), the gradients satisfy (g. (J, 112, S N. o(m).
The above two lemmas are essential in proving Theorem 5.6, which is our convergence result.
Theorem 5.6 (Convergence result, informal version of Theorem E.3). For all E (0, R 2 1, there exists an M = poly(n, R, 1/e), such that for every m Z M, for every K 2 1, for every )) over the randomness of a()) R ((0) E Rdxm b(0) E R.,, for all U such that -| - (0))l2..c S R/m", running Algorithm J, R, 1/c) and nocal = 1/K will output weights (U(t)) that satisfy # - CA (fo(o)= S LA. (fu.)+E.
T 2 poly(R/ (R/c), with probability at least 1
with setting Ngglbbll = 1/
In the proof of Theorem 5.6 we first bound the local gradient (f k:). We consider the pseudo-network and bound ((gu S(t) L(ge- S(t)) I a(t) + 3(t) + rt), where a(t) ==
(V(, (tt) - B(t) = (]) - tl.. (t)
- 12 and 7()) = (V
((l,))l,, (1) - U 12,00 In bounding a(I), we unfold [U + 1) - U and by rearranging
we have
att)
Ngglbbll
(tU()
1 ([)((t) - UI | + -)
2
Mgglobal
We bound
| I Mocal o(m). By doing summation over t, we have
T
(t)
Nglobal
(AU())) +
Σ
(()((t) - 1)) 1)(
2
MMglobal
t=1
E=1
T/global
((U + Mgglobal
[1((1) - -
S Aglobal//ocall TK o(m) +
mD
Nglobal
In hounding B(1,, we apply Lemma 5.4 and have
(()) (f. VJ, [[((t) - U 1|2,00
2 (m) [[U(t) - U
S (()) (I)U(L) 12,00 Du-).
where Do. = 1||-~Ullee -1122.00 < R/mm As for the first term, we bound
[1U(()= - 112,00 < Ngiobal
[TU(2))
K-1
Ngioball
Σ
Mocal
Σ
V 1, k3)22,0
N
K-1
Mglobal/local
ΣΣΣ
[V t, 1,
N
k=
< TglobalMoocall Mt Km
8

---

Under review as a conference paper at ICLR 2022
and have B(t) S Nglobal Jllbba/oocaatK o(m) o(m). Du., then do summation and obtain
T
Σ
B(t) S Nglobal?ooca T o(m) + o(m) TDv..
t=1
In bounding 7(),, we apply Lemma 5.5 and have
(t)) = (V - V(f00l21 ([T(t) U2 S NJ. o()) ((U(()) U11,, + DU-).
Then we do summation over and have
7()
Ngglobal/hocal T2KNJ o(m) TNJ ((m)DD-
Putting together with our choice of our parameters (i.e. Mocall Nglobaly Rg K, m), we obtain
Σ Flov,,, S(t)
1 T Σ clou,, S(t)
1
E ((t) Σ ((t) Σ 7()) O(c). t=1
T
From Theorem D.2 appendix, we have: suPREx (f( gu (x) s 0(),, and thus,
T E t=1
C(foa),S(t) 1
E C(fu-,8(t)) < O()). T
T
From the definition of A have L(fc-, S (f-(fe-). From the definition of loss we have (() LA (a(fo)) Moreover, since Eq. (3) holds for all > 0, can replace O(t) with Thus we prove that for Ve 0.
T
Σ Ca(fv() s Ca-(fu-)
T
Combining the results From Theorem 5.2 obtain U that is close to U(0) and makes LA-(fu-) close to zero, from Theorem 5.6 we have that the average of (A(fv() dominated by L (fu-). By aggregating these two results, we prove that the minimal of Ca(fr() is small and finish the proof of our main Theorem 4.1.
CONCLUSION
We have studied the convergence of general format adopting adversarial training in FL setting to improve FL training robustness. We propose the general framework. FAL, which deploys adver- sarial samples generation-bel local model using FedAvg (McMahan et al., 2017). In FAL, each client is trained via min-max opti- mization with inner loop adversarial generation and outer loop loss minimization. To the best of our knowledge, we the first to present the comprehensive proof of theoretical convergence guarantee for over-parameterized ReLU network on the presented FAL strategy, using gradient descent. Unlike the convergence of adversarial training in classical settings, we consider the updates on both local client and global server sides. Our result indicates that we can control learning rates Mocal and Tgglobal according to the local update steps K and global communication round 7 make the minimal loss close to zero. The technical challenges lie in the multiple local update steps and heterogeneous data, leading to the difficulties convergence. Under ReLU Lipschitz and over-prameterization assump- tions, we use gradient coupling methods twice. Together, we show the model updates of each global updating bounded in our federated adversarial learning. Note that we do not require IID assump- tions for data distribution. In sum, the proposed FAL formulation and analysis framework can well handle the multi-local updates and non-IID data in FL. Moreover, our framework can be generalized other FL aggregation methods, such sketching and selective aggregation.
adversarial training method on the client-side and then aggregate

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
Ensuring the security and robustness of the deployed algorithms is of paramount importance in AT algorithms nowadays. Recently, machine learning training has revealed its vulnerability to adver- sarial attacks and tendency to generate wrong predictions. The tread cannot be underestimated in FL, where the heterogeneity among clients and requirement for efficient communication brings in challenges in stable gradient updates. In this regard, our work theoretically shows the feasibility of FAL. As theoretical work, we do not involve any human subjects or datasets. Our work has the potential positive impact on the machine learning community.
REPRODUCIBILITY STATEMENT
We provide the proof details in the appendix to ensure reproducibility.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameter- ized neural networks, going beyond two layers. In NeurIPS. https://arxiv..rgg 1811. 04918.11111100 pd., 2019a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. On the convergence rate of training recurrent neural networks. In NeurlPS. https: / wawxiviviivve//ii//.aaaaaaaaavva ott/ http//df//1/// 1tt.e//111....1...111111
12065.22252 pdf, 2019b.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. ICML. https: /tt.tpss///rxii...// hwtpa/awww..ggp/////1..11111 pdf,, 2019c.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In NeurIPS. https://arxii:
pdf/1904. 11945..195..... pdf, 2019a.
Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML. 901 20110880 08w88888.... pdf, 2019b.
https:: //arxiv. http:/aawvvvrrrrr///////// brgg/pf///
Anish Athalye, Nicholas Carlini, and David Wagner. Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples. arXiv preprint 1rXiv:1802.0044 2018.
Sergei Bernstein. On a modification of chebyshev's 's inequality and the error formula of laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math, 1(4):38-49 1924.
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Scraphin Calo. Analyzing federated learning through an adversarial lens. In International Conference on Machine Learning, pp. 634 643. PMLR, 2019.
Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 39-57. IEFF, 2017
Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics,, pp. 493 507, 1952.
Francesco Croce and Matthias Hein. Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks. In International Conference on Machine Learning, pp. 2206- 2216. PMLR, 2020.
Simon S Du, Jason D Lee. Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In JCML. https: watpvvivvvvv////////./a/aaaaa wttp://www/////////////// 03800 2019a.
Simon S Du, Xiyu Zhai, Baraabas Poczos, and Aarti Singh. Gradient descent provably optimizes weer-paraeterrized neural networks. In ICLR. https: : wwtpaawwww..g..aaa/a////////paae 11g//p 02054. fd 2019b.
10

---

Under review as a conference paper at ICLR 2022
Ruiqi Gao, Tianle Cai, Haochuan Li, Cho-Jui Hsich, Liwei Wang, and Jason D Lee. Convergence of adversarial training in overparametrized neural networks. Advances Neural Information Processing Systems, 12:13029-13040, 2019.
lan J Goodfellow, Jonathon Shlens, and Christian Szegedy, Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6577 2014.
Elad Hazan. Introduction online convex optimization. Foundations and Trends in Optimization, 2(3-4):157-325, 2016.
Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30 1963.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks. In Advances in neural information processing systems (NeurIPS), pp. 8571-8580 2.18.
Alexey Kurakin, Ian Goodfellow, and Samy Bengio. Adversarial machine learning scale. arXiv preprint 1..iv22611.0123000 2016.
Jason D Lee, Ruoqi Shen, Zhao Song, Mengdi Wang, and Zheng Yu. Generalized leverage score sampling for neural networks. In NeurlPS, 2020.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Conference on Machine Learning and Systems, 2020a, 2020a.
Xiang Li. Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv: /907.02/99,, 2019.
Xiaoxiao Li, Yufeng Gu, Nicha Dvomek, Lawrence Staib, Pamela Ventola, and James Dun- can. Multi-site fmri analysis using privacy-preserving federated learning and domain adaptation: Abide results. Medical Image Analysis, 2020b.
Xiaoxiao Li, Mcirui JIANG, Xiaofei Zhang, Michael Kamp, and Qi Dou. Fedbn: Federated learn- ing non-iid features via local batch normalization. In International Conference on Learning Representations, 2021. URL https: https:: wwtp///www.....oo/o/pp/p. net/ htt.://formmiideoeee 11g
Yuanzhi Li and Yingyu Liang. Learning overparameteriized neural networks via stochastic gradient descent on structured data. NeurlPS. htttps://arxxv.orr//ee 2018.
0120080112200 01204. .dff
Xinle Liang, Yang Liu, Tianjian Chen, Ming Liu, and Qiang Yang. Federated transfer reinforcement learning for autonomous driving. arXiv preprint
2019.
Wei Yang Bryan Lim, Nguyen Cong Luong, Dinh Thai Hoang, Yutao Jiao. Qiang Yang, Dusit Niyato, and Chunyan Miao. Federated learning in mobile edge networks: A comprehensive survey. IEEF Communications Surveys Tutorials, 223) 2020.
Liang,
2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. In ICLR. pttts:///rxiit /xg//df/De /1006 6. 06083, pdf, 2018
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiiie learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and H Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00225, 2020.
Amirhossein Reisizadeh, Farzan Farnia, Ramtin Pedarsani, and Ali Jadbabaie. Robust federated learning: The case of affine distribution shifts. arXiv preprint arXiv:2006.08907 2020.
11

---

Under review as a conference paper at ICLR 2022
Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni. Spyri- don Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier- et al. The future of digital health with federated learning. NPJ digital medicine, 3(1):1-7,
Pouya Samangouei, Maya Kabkab, and Rama Chellappa. Defense-gan- Protecting classifiers against adversarial attacks using generative models. arXiv preprini 180.:06005006005 2018.
Zhao Song and Xin Yang. Quadratic suffices for wver-parametrization via matrix chernoff bound. In arXiv preprint. https: pppas///axxiie /awxivaxiiv//..////i//aaa/aaaai. org/ httg//df/100 /0906 03593. pdf, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. In arXiv preprint. https://aarts brggpdf/13tt
pdf. 2013.
Florian Tramèr, Alexey Kurakin, Nicolas Papernot, Ian Goodfellow, Dan Boneh, and Patrick Mc- Daniel. Ensemble adversarial training: Attacks and defenses. arXiv preprint wrXiv:1705.07266 2017.
Joel A Tropp. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1-2)11-300 2015.
Zhuozhuo Tu, Jingwei Zhang, and Dacheng Tao. Theoretical analysis of adversarial learning: A minimax approach. arXiv preprint 11X00:181. 2018.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective in- consistency problem in heterogeneous federated optimization. arXiv preprint arXiv:2007.072 077484 2020.
Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. Adaptive federated learning in resource constrained edge computing systems. IEEE 2019.
Journal on Selected Areas Communications, 37(6):1205-11)
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed
learning: Towards optimal statistical rates. In International Conference Machine Learning, pp. 5650-5659, PMLR, 2018.
Gaoyuan Zhang, Songtao Lu, Sijia Liu, Xiangyi Chen, Pin- Yu Chen, Lee Martic, and Mingyi Horesh, Lior abd Hong. Distributed adversarial training to robustify deep neural networks at scale. 2021. URL https: /openreveew net ppff/pff// a fid=kmiFHdJsSSS
Xinwei Zhang, Mingyi Hong. Sairaj Dhople, Wotao Yin, and Yang Liu. Fedpd: A federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005. 2020a.
Yi Zhang, Orestis Plevrakis, Simon S Du, Xingguo Li, Zhao Song, and Sanjeev Arora. Over- parameterized adversarial training: An analysis overcoming the curse of dimensionality. In NeurIPS, arXiv preprint arXiv:2002.06668,, 2020b.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint 10Xivv/806.0000 2018.
Giulio Zizzo, Ambrish Rawat, Mathieu Sinn, and Beat Buesser. Fat: Federated adversarial training. Xrxiv preprint arX1::001..01791, 2020.
12

---

Under review as a conference paper at ICLR 2022
Roadmap The appendix is organized as follows. We introduce the probability tools to be used in our proof in Section A. In addition, we introduce the preliminaries Section B. We present the proof overview in Section C and additional remarks used in the proof sketch in Section D. We show the detailed proof for the convergence in Section and the detailed proof of existence in Section correspondingly.
A PROBABILITY TOOLS
We introduce the probability tools that will be used in proof. First we show three lemmas about the tail bounds for random scalar variables in Lemma A.I, A.2 and A.3:
Lemma A.1 (Chernoff bound Chernoff (1952)). Let X = Ei= X where X; with probability p; and X, 0 with probability 1 Ps. and all X; are independent. pe [[
Ps. Then
1. Pr X > (1 5) I m/3)), v6 > 0; X S 5)1( S (xp(-68p//2)
8 <1
Lemma A.2 (Hoeffding bound Hoeffding (1963)). Let X1,
Xn denote n independent bounded
variables in (as, bi]. Let X = Σi= X,, then we have
212
Pr[[X [[X] 20 S exx
Ei=1 - a,)2
Lemma A.3 (Bemstein inequality Bernstein (1924)).. Let X1.... Xnn be independent zero-mean random variables. Suppose that [X,] S M almost surely, all Then, for all positive t.
12/2
Pr
X
1
exp (EE) B[X]| Mt/3
Next, we introduce Lemma A.4 about CDF of Gaussian distributions:
Lemma A.4 (Anti-concentrattoon of Gaussian distribution), Let X o0(0, that is, the proba- bility density function of X is given by Φ(x) v/no02
2 207
Then
4t
Pr < t E
30
5
Finally, we introduce Lemma A.5 concentration result random matrices and Claim A.6 about elementary anti-concentraatio property of Gaussian distribution.
Lemma A.5 (Matrix Bernstein, Theorem 6.1.1 in Tropp (2015)). Consider finite sequence
(X1,... ".m C RRaxx of independent, random matrices with common dimension ny x n22
Assume that
E[ = 0, Vi [m] and |XII| & M, [m].
Let Z = Em, Xt. Let Varl be the matrix variance statistic of sum:
Σ B xall]
Varl max Σ BIXxXT
Then
E|][ < (2Var[Z] log(mr n2)) log(mi n2)/33
Furthermore, for all 1 2 0,
f/22 (-arl[ + M1/3
Pr|]| < (ni + +22) exp
We state a standard probabilistic result for Gaussian,
Claim A.6. Let (N0 Ia) and B ~ A/ 1), which are independent. For all X and t 2 0.
Pr[ (u, + 3 s O(1)
13

---

Under review as a conference paper at ICLR 2022
B PRELIMINARIES
B.I NOTATIONS
For vector 2, we use ||>||p to denote its ep norm, this paper we mainly consider the situation when p 2, or oo.
For matrix W E Rdxm, we use WT to denote its transpose and use tr[W] to denote its trace. We use [[W],, ||W|] 22 and |[W] || to denote the entry-wise & norm, spectral norm and Frobenius norm of W respectively. For each j E [mll we let W E R be the j-th column of W. We let |||| t denotes ش [[W , l22 and W2 denotes ma ||W For two matrices A, B with the same dimensions, we denote their Euclidean inner product as (A, B) == tr(AT B).
We denote Gaussian distribution with mean and covariance E as (n, E). We use a(.) to denote the ReLU function o (z) = max 0}. and use { to denote the indicator function of event E.
B.2 TWO LAYER RELU NEURAL NETWORK AND INITIALIZATION
In this paper, we focus on a two-layer neural network that has m neurons in the hidden layer, where each neuron is ReLU activation function. We define the global network
fu (x) = Σ or ((U,, br)
(4)
and for e E [N], we define the local network of client css
fw.(z): = Σ or o((Wer x) + by).
(5)
Here U (U1..... Um) E Rdxm is the global hidden weight matrix, W. (We,..... W w.
Rdxm is the local hidden weight matrix of client c, and (aI,..., Qm) E ET denotes the output weight vector, b = (b....., 6m) E Rn denotes the bias vector. During the process of federated adversarial learning, for convenience update U and W, so we can write the global network as fu (x) and the local network as fw. (r). For the situation don't care about the weight matrix, we write f(x) fo(x) for short. Next, make some standard assumptions regarding our training set.
keep and equal to their initialized values and only
Definition B.1 (Dataset). There are N clients and n = NJ data in total.* Let S = Uc where } C Rd x R denotes the J training data of client c. Without loss
S. = f( ve..).... (Ie.J, }e.J)} of generality, we assume that for all e [N]. [J], || ll2 and the last coordinate of each point equals to 1/2, so we consider X {i R ||>||| 1, Fd 1/2]. For simplicity, we also assume that for all [N].j E [J], |ye,s 1.5
We now define the initialization for the neural networks.
Definition B.2 (Initialization). The initialization of a E R Rm (0) Rdxm b(0) E R The initialization of client c's local weight matrix W. is (0, 0) = (O)). Here the second term in W. denotes iteration of local steps.
_ U E Rdxm,
b E R" is a(0) E
For each r E [m], (0) are i..dd sampled from [-1/m 1/3m uniformly.
For each i E [d],r [m]. (0) and by (0) are i.i.d. random Gaussians sampled from ((001/m) Here Us, means the (i, -entryy of U.
"Without loss of generality, assume that all clients have same number of training data. Our result can be generalized to setting where each client has different number data as future work.
*Our assumptions on data points are reasonable since can do scale-up. In addition, la norm normalization typical technique in experiments. Same assumptions also appears in many previous theoretical works like Arora et al. (2019b): Allen-Zhu et al. (2019a:b).
6 Here the choice of mm 4/3 is not must. Actually what we need is [-1/m,, 111mm,+/mmm +1/m²] for some that satisfies
2211 c 1/3.
14

---

Under review as a conference paper at ICLR 2022
For each global iteration t [T),
For each c [N], the initial value of client c's local weight matrix We is Wo(t, U()).
B.3 ADVERSARY AND WELL-SFPARRTEE TRAINING SETS
We first formulate the adversary as mapping.
Definition B.3 (p-Bounded adversary). Let F denote the function class. An adversary is mapping A: F X x TR. + X which denotes the adversarial perturbation. For p 0, we define the &2 ball as (2) = - Rdd::: | æ|12 S p) n, we say an adversary A is p-bounded if is satisfies
A(f, v) E P)-
Moreover, given p > O, we denote the worst-case adversary as A == argmax ((f(z),)) v). where is loss function defined in Definition B.5.
In the over-param per-paarameterized regime, it is standard assumption that the training set is well-separated. Since we deal with adversarial perturbations, we require the following 7-separability, which is bit stronger.
Definition B.4 (1-separability). Let E (0, 1/2), E (0,1/2), 10,) denote three parame- ters such that y S 6-(0-2p). We say our training set S S = Jee No.a)} Rdd R globally "-separable w.rl a p-bounded adversary, if
min || Foa.ialle aa arechh #12
is worth noting that, our problem setup does not require the assumption on independent and identically distribution (IID) on data, thus such a formation can be applied to unique challenge of the non-llD setting in FL.
B.4 ROBUST LOSS FUNCTION
We define the following Lipschitz convex loss function that will be used.
Definition B.5 (Lipschitz convex loss). loss function R x > is said be Lipschitz.
convex loss, if satisfies the following four properties:
non-negative;
convex in the first input of E;
Lipishcitz which means [[((z1,11) - f(22, 12) S (1(11,11) - (x2, 12)
Ely, y) = 0 for all y E IR.
The choice of this type of loss is for the sake of technical presentation simplicity, is customary in prior studies Gao et al. (2019); Allen-Zae Zhu et al. (2019a).
We assume é is Lipschitz convex loss in this paper. Next, define our robust loss function of neural network, which is based on the adversarial examples generated by a p-bounded adversary A. Definition B.6 (Training loss). Given client's training set S. { Je,))//=1 C Rd R of examples, the standard training loss of a neural net fo Rdd + R defined as L(fo,S))
3 + E (elKes)sWeed) Given S = Ue the global loss is defined as L(JU,S) = NJ EN Ej= respect to A as
Nes). Given a p-bounded adversary A, we define the global loss with Ca(fu) =
N
1
{ffo(A(fer Feijr Ne.g)): Vc.))
NJ
N
Σ
{fo (Te.).
=
NJ
==
15

---

Under review as a conference paper at ICLR 2022
and also define the worst-case global robust loss
(A-( NJ
(Ju Fee Fe Ve.i yo.))
N
ΣΣ Fes
(F
max (B
NJ
Moreover, since deal with pseudo-net which is defined in Definition D.I, also de- fine the loss of pseudo-net S.) 3 Nas) and L(
Σ N Ej=1 (lgu(Fos): Mes)-
B.5 FEDERATED ADVERSARIAL LEARNING ALGORITHM
Classical adversarial training algorithm can be found in Zhang al. (2020b). Different from the classical setting, our federated adversarial learning of a local neural network fw. against an adver- sary A is shown in Algorithm 2, where there are two procedures: one is CLIENTUPDATE running on client side and the other is SERVEREXECUTION running server side. These two procedures are iteratively processed through communication iterations. Adversarial training is addressed in proce- dure CLIENTUPDATE. Hence, there are two loops in CLIENTUPDATE procedure: the outer loop is iteration for local model updating; and the inner loop is iteratively generating adversarial samples by the adversary A. In the outer loop in SERVEREXECU ters are updated to reduce its prediction loss on the new adversarial samples. These loops constitute intertwining dynamics.
procedure, the neural network's 's parame-
16

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Federated Adversarial Learning (FAL). This is complete version of Algorithm 1.
1: /*Defining notations and parameters*/
2: We use c to denote the client's index
3: The training set of client is denoted as S. = (FFe Vo. yos))
4: Let A be the adversary
5:
We denote local learning as Moocl
6: We denote global learning rate as Nglobal
7: We denote local updating iterations as K
8: We denote global communication round as T
9:
10: /
11:
Initialization (0) R", ("",U()) E gdxm b(0) E R"
12:
For t 0 + T. iteratively run Procedure A then Procedure
13:
14: /* Procedure running client side *
15: procedure A. CLIENTUPDATE(,, c)
S.(1)
17:
We(t, 0) + (t) for
Receive global model weights update
K-K - do
19:
for j = + do
20:
= A() Fegt Mag)
Adversarial examples, fw. is defined (5)
21:
S.(() (.( U (Te) Hn.)
22:
end for
23:
Walt, k 1) + We(t, k) Mocal
24:
end for
25: AU.(t) + W.(t, K) - U(t)
26:
Send (U,(!) to SERVEREXECUTION
27:
end procedure
29: P*Poceeurre running on server /
procedure B. SERVEREXECUTIONNN)) for each client e in parallel do
31:
32:
AU.(t) + CLIENTUPDATE(C,.
Receive local model weights update
33:
(U <- N EnE(N AU.(t)
34:
U(l - 1) +- (L) Nglobal AU())
Aggregation the server side
35:
Send Utt + 1) to client for CLIETUPPATT((C..
end for
37: end procedure
17

---

Under review as a conference paper at ICLR 2022
C PROOF OVERVIEW
In this section we give an overview of our main result's proof. Two theorems to be used are Theo- rem E.3 and Theorem F.3.
C. PSEUDO-NETWORK
We study the over- parameteratteed neural nets' well-approximated pseudo-network to learn gradient descent for over-varammnn peer-paramtteiieed neural nets whose weights are close to initialization. The introducing of pseudo-network makes the proof more intuitive.
To be specific, we give the definition of pseudo-network in Section D, and also state Theorem D.2 which shows the fact that the pseudo-network network approximates the real network uniformly well. It can be seen that the notion pseudo-network network is used for several times in our proof.
C.2 ONLINE GRADIENT DESCENT IN FEDERATED ADVERSARIAL LEARNING
Our federated adversarial learning algorithm is formulated in the framework of online gradient de- scent: at each local step & on the client side, firstly the adversary generates adversarial samples and computes the loss function (fw.,t,&), (t)). then the local client learner takes the fresh loss func- tion and update Wa(t, + 1) = Wt(t, k) - Mocal Vw. C (fw.,t,k). (t)).. We refer our readers to Gao al. (2019); Hazan (2016) for more details regarding online learning and online gradient descent.
Compared with the centralized setting, the key difficulties in the convergence analysis of FL induced by multiple local updates on the client side and the updates on both local and global sides. Specifically, local updates not the standard gradient the centralized adversarial training when K 2 2. We used (t) in substitution of the real gradient of U to update the value of (t).. This brings in challenges bound the gradient of the neural networks. Nevertheless, gradient bounding is challenging in adversarial training solely. We use gradient coupling method twice to solve this core problem: firstly we bound the difference between real gradient and FL gradient Lemma E.4, then we bound the difference between pseudo gradient and real gradient in Lemma E.5. We show the connection of online gradient descent and federated adversarial learning the proof of Theorem E.3.
C.3 EXISTENCE OF ROBUST NETWORK NEAR INITIALIZATION
In Section F we show that there exists global network fo- whose weight is close the initial value (0) and the worst-case global robust loss L (Jv-)) is sufficiently small. We show that the required width m is poly(d, (/7).
given a p-bounded adversary. For globally 7-separable training set, in order to prove Theorem F.3, we first state Lemma F.1 which shows the existence of function f* that has "low complexity" and satisfies ("((aa)) Ye. for all data point (Ie.. Mo..) and perturbation inputs Tef E B2 p). Then, we state Lemma F.2 which shows the existence of pseudo-network. gu- that approximates f well. Finally, by using Theorem D.2 we show that for approximates gu- well. By combining these results, we we finish the proof of Theorem F.3.
Suppose
18

---

Under review as a conference paper at ICLR 2022
D REAL APPROXIMATES PSEUDO
To make additional remark to proof sketch in Section 5, in this section, we state a tool that will be used our proof that related our definition of pseudo-network,, First, we recall the definition of pseudo-network.
Definition D.1 (Pseudo-network). Given weights U E Rdxm, a E R and b E R the global
neural network function fu IR + R defined as
fv(x) = Σ a (0U,, + bb).
Given this fz()). we define the corresponding pseudo-network, function gu R lR
(v) = ar - (0,) (((,())))) 2 0}.
From the definition we can know that pseudo-network can be seen as linear approximation of the two layer ReLU network we study near initialization. Next, cite Theorem from Zhang et al. (2020b), which gives a uniform bound of the difference between a network and its pseudo-network.
Theorem D.2 (Uniform approximation, Theorem 5.1 Zhang et (2020b)). Let 1. For all m poly(d), with probability at least exp((S((m1/5) over the choice of (0)), (O),, b(0) for all U E Rdxm such that I (0) 22.00 1 R\/m2/3.
sup ff - gu (x)) - O(R² OOR2/m//0) #EX
19

---

Under review as a conference paper at ICLR 2022
E
CONVERGENCE
Section
Statement
Comment
Statements Used
E.1
Definition E.1 and E.2
Definition
E.2
Theorem E.3
Convergence result
Lem. E.4, E.5, Thm. D.2
E.3
Lemma E.4
Approximates real gradient
E,4
Lemma E.5
Approximates pseudo gradient
Claim E.6 Claim A.6
E.5
Claim E.6
Auxiliary bounding
Table 1: List of theorems and lemmas Section The main result of this section is Theorem E.3. By saying "Statements Used" mean these statements are used in the proof in the corresponding section. For example, Lemma E.4, E.5 and Theorem D.2 are used in the proof of Theorem E.3.
E.1 DEFINITIONS AND NOTATIONS
In Section E, we follow the notations used in Definition D.I. Since we are dealing with pseudo- network, we first introduce some additional definitions and notations regarding gradient.
Definition E.1 (Gradient). For a local real network fWatt,y), we denote its gradient by
(fest t, k) = ((...(t.))))))).......
the corresponding pseudo-network is (W.(t.k) then we define the pseudo-network gradient as V (ge, L, k) = Vw. Cww.(o.. S.()).
Now consider the global matrix. For convenience write V(f.t) Vuf(fur), S(t) and (gg,t) = Ligunn, We define the FL gradient as (f,tt) = (U)
Definition E.2 (Distance). For U* E Rdxm such that I U1,,,0 R/m3/1, we define the following distance for simplicity:
Dmax := max (t) 12, NE[T]
Du- : | U11
have Du- O(R/m8/9) and [IU(t) - U S Dmax + Dy- by using triangle inequality.
Notation
Meaning
Satisfy
((0) Ú
Initialization of U
Wo 0) (0)
Utt)
The value of U after iterations
Dmax max UU((t Ü 2,,000
U
The value of U after small perturbations from U
I0 -rl-Ull,.0 I R m33 3/4
Table 2: Notations of global model weights in federated learning to be used in this section.
E.2 CONVERGENCE RESULT
The goal of this section is to prove Theorem E.3.
Theorem E.3 (Convergence result, formal version of Theorem 5.6). For all E (0, 1), for all R 2 1, there exists an M = poly(n, R, 1/c), such that for every m 2 M, for every K 2 1, for every T 2 poly( R R/e), with probability at least 1 - exp(-S((m /3)) over the randomness of a(0) E R.m. (() ddx b(0) TM if we run Algorithm with setting
Aglobal 1/ poly (N R, 1/e) and Thocal 1/K,
then for every UH such that U - 2(0))l2,5 S R/ 3/4, the output weights (U(t))=_ satisfy
1 T
Σ LA (Fu()) < LA (fu-) te.
T 1=1
20

---

Under review as a conference paper at ICLR 2022
Proof. We set parameters as follows:
M = 2 max {(NJ)), R (1)))
Igllohal = O( N/ poly(R/c)
Mocal 1/K
Since the loss function is 1-Lipschitz, first bound the norm of real net gradient:
I ( Jarl- [ (l, + b.) || S |arl S m/
1
(6)
Now we consider the pseudo net gradient. The loss C(gr, convex in U due to the fact that g is linear with U. Then we have
L(gv()) S(t)) - ((g)-
U*)
S at)) + 3(t) + (tt)
where the last step follows from
at) = ((f,)),
B(t) [V(f.t) ((f. [[((t) U U2
>(t) == (V v(f.t) |[U(() - -U*Il2,0.
Note that the FL gradient (f. t) = + (t) is the direction moved by center, in contrast, ((f.t)
the true gradient of function f. We deal with these three terms separately. As for att), we have
[U 1) - 1
[IU(t) Tglobbal (t) U
(t((t) 1²B 2N 2gNglobala(() + Nglobal (t)
and by rearranging get
(1))
Ngloobal
|AU!)) + 2N nglobal
(1)U(1) - U 13- 1) 11+)
2N
Next, we need to upper bound (AU P
K-1
AA (1) =
nocal
N
k=
N K-1 m ΣΣΣN
Mocal
N
= Km 1/3
m 1/3
where the last step follows from K KTocaal = 1. Then we do summation over and have
Σ
a(l)
nglobal
(AU()
Σ(1(() U 1)
2N
Tiglobaal
Iglobal
2N
2N 2ighobbal
Nglobal
[[((1) U
2N
2N 2N Nygllobll
Nglobal
T' 1/3
1
mD..
N
NTgllbbll
21

---

Under review as a conference paper at ICLR 2022
where the last step follows from Eq. (7) and - - m. I/Ü As for (()), we apply Lemma E.4 and also triangle inequality and have
12 mD
B(1) (V V1, [1(()) - U 22,,0
S mm/3 [|U(t)
U 12,00
$ m/3
2/3 (t) Ü 12,000 + Du.).
By using Eq. (6) bound the size of [tU U 12
(tt(t) - 122,00 S Nglobal
(T
r=1
K-1
Mglobal
Mocal N
V(fe, t, 1)12,,
K-1
7loca
ΣΣ>
Σ
[V(f,t t, 22022
N
k=0
S /global//ocatt
1/3
and have
((t) S Agglobal/oocall Km Kma/3 1/3 + 2/3 Du
Then we do summation over and have
T
3(1)
V 1/3 + m/33 Du-)
T Km m² 2/3TDD-
Nglobal T m 1/3 + m DD.
As for 7t), we apply Lemma E.5 and have
(t) [V 1) vfftt)ll,. [t((t)) U21122,00
S NJ 13/24 (1) - U11,,00 + Dv.).
U11,,00 < Iglobal 1/3, have Since [|U(t)
(l) S M 5/24 + NJm 13/24 Du
Then we do summation over and have
Σ 7t) (Tglobal 1 13/21 Dv-)
S Mglobal/locaa? KN 5/24 + N.Jm 13/24// Du- Agloball
2 Jm 5/24 N. 13/21
1 TTV.
22

---

Under review as a conference paper at ICLR 2022
Next put it altogether. Note that Du- O
R
thus obtain
m3/a
((ur)),,(11)
Aigu-, ,())
a(l) + Σ
3(1) + Σ (()
1=1
1=1
t=1
Ngloball
T'm 1/3
mD + Aglobal m/3
N
Nyglobal
+ m
2/3
TDy- + Tiglohal
T NJm 5/24
N.m 13/ 3//2// Du-
Nglobal
Tm +
1
R2m 11m22/2 1/2 + Tiglobal T 1/3
N
Nyglobal
+ RTm 1/12 + Agllbbll
N + NNm -5/24 HT.
We then have
L(go()) S(t)
Σ ((gv-,((()
T
Nglobal
N m 1/3
m/33
R² m 1/2 + Ngloballmm 1/3 + Rm 1/122
Niglobal T
TN Jmm 5/24 NJm 5/24 R.
Tglobal
1
R2 m 1/2 + Nglobal Tm + Rm 11/12 + Nglobal TN TN + N 5/24 R (8)
1/12
Nigloobl < (c)).
From Theorem D.2 we know
sup xex
(x) = O(c)
and thus, get
1 T Σ C(fu-, S(t)) s.c
C(fva), S(t))
(9)
where 0 is constant. From the definition of AA" have L(fu-, (fu-). From the definition of loss we have L(fo(), S(t)) = LA (fvo)) Moreover, since Eq. (9) holds for all e >> 0, can replace & with Thus we prove that for Ve > 0.
T
Callv()) < CA-(fU-) te.
T
E.3 APPROXIMATES REAL GLOBAL GRADIENT
The goal of this section is to prove Lemma E.4.
Lemma E.4 (Bounding the difference between real gradient and FL gradient). With probability at least exp(-S((m)) 1/3) over the randonness of (()) R", U()) E dx b(0) R" for all
iterations such that [|U(t)) (00)]2,, I O(m 15/244, the following holds:
[[)(ftt - (f. fl22 S (mm2/3))
Proof. Notice that V(f.t) VvC(fo() S(t)) and
N v(S1)) ~ Σ
K-1
AU,())
Mocal
Σ K=
V(Se, t,)).
N
23

---

Under review as a conference paper at ICLR 2022
So have
T
[V((1)) V = E (V. (.(,0ii
N K-1
N (.(f,) Mocal
V, (fe, k)l22
k=0
K-1
N N (.(ftt)
Mocal
t,
N
K Mooaa
m K-1
Σ
IN V.(f.t)
NK
where the last step follows from the assumption that Moral K.
As for II v.(s()) E V,(So, 12222, we have
N
IN (f.tt) Σ
kr(fett
N
S |arl 1 (NJ
Σ
(((U)(t), +b, 20
c=1 1=1
N J
1 tc,)) 2 07) |
1
(((U)(t), + 2 20} 1[ Fe) + b, 2 0}
m/3
N
m//3
Then we do summation and have
K-1
N
(V()t) ((, S
|N v.(.t)) Σ V, (fe, t, k)
NK
k=0
m
N
NK
m//3
m 2/3
Thus we finish the proof.
E.4 APPROXIMATES PSEUDO GLOBAL GRADIENT
The goal of this section is to prove Lemma E.5.
Lemma E.5 (Bounding the difference between pseudo gradient and real gradient). With probability
at least 1 exp(-9(m 1/3) over the randomness of a(0) 1R U()) e ddxm 6(0) E 1 for
all iterations such that (t) - 2, < 0(m -11224,, the following holds:
[V () v(,,))2,, S OmNNmm3222
Proof. Notice that (gg = Vo Vo and v(f.t) = S(t).. By Claim E.6,
with the given probability have
24

---

Under review as a conference paper at ICLR 2022
For indices E [m]] such that (. (f, the following holds:
(g, V.(1,4)l2 = VV, ((000)
S(1) ((
N
s |aa||
1
و 1l | kas) + + 2 0}
NJ
= Ø=
1[UU, Teg) + b, 2 0H
I((Ü,,)as)) + 203 [((U,, b, 2 20}
1/3
NJ
m/3
where the first step is definition, the second step follows that the loss function is 1-Lipschitz, the third step follows from |a,| I - and || = the last step follows from the bound of the indicator function. Thus, we do the conclusion:
(V (ff.
Σ (g. - 4
m
m 1/3
1
O(NJm3/ 7/8)
1/3
and finish the proof.
E.5 BOUNDING AUXILIARY
Claim E.6 (Bounding auxiliary). With probability least exp(- over the initializa- tion, we have
(V.(0.))++ (... SN(N
Proof. For r E [m], let Ir == 1(V + (f( By Claim A.6 we know that for each Te.j have
Pril( Fest + byl E 15/24 500
By putting a union bound over and j. we get
Pr [3ce [N].j E [V], (Wer, cr: Nos) + bel S 15//24 I Jm 1/5).
Since
Pr[/, = 1] S Pr[ee E [N].j E [J], KW o. tas) + brl S m 10-mm11551 -15/24]
we have
Pr = 1] S O(NJm
By applying concentration inequality on I, (independent Bernoulli) for E [m]. we have that with 2x)(-)(m!/3)), the following holds:
probability at least 1 exp( 1 7/8))
T < ONNmm
Thus finish the proof.
25

---

Under review as a conference paper at ICLR 2022
E.6 FURTHER DISCUSSION
Note that in the proof of Theorem E.3 we set the hidden layer's width m to be greater than O (E)-)) which seems impractical in reality: if choose convergence accuracy be 10-2, the width will become 10a4 which impossible to achieve.
-22),
However, we want to claim that the "-12" term is not intrinsic in our theorem and proof, and we can actually further improve the lower bound of m to ((R/ee(*) where C2 is some constant between -3 and -4. To specific, we observe from Eq. (8) that the 1- term comes from - 12. where 3/2 appears in Lemma E.4 and 3 appears in the assumption that Dy- S R/m3/41 in Definition E.2. As for our observations, the & term hard improve. On the other hand, we can actually adjust the value of Du as long as we ensure
Du- S R/mm S
for some constant C3 E (0, 1). When we C3 - 1, the final result will achieve
R on )
which is much more feasible in reality.
As the first work and the first step towards understanding the convergence of federated adversarial achieving the tightest bounds. Instead, our main goal is to
learning, the priority of our work show the convergence of a general federated adversarial learning framework. Nevertheless, we will improve the bound in the final version.
26

---

Under review as a conference paper at ICLR 2022
F EXISTENCE
In this section we prove the existence of U** that is close to (0)) and makes L (fc.) close to zero.
F.1 TOOLS FROM PREVIOUS WORK
In order to prove our existence result, we first state two lemmas that will be used.
Lemma F.1 (Lemma 6.2 from Zhang et al. (2020b)). Suppose that [l - -Eez.jall lll 2 ā holds for each pair of two different data points Lerdu. Londs Let D = 24- In(48NJ/e), then there exists a polynomial q R + IR with degree at most D, size of coefficients at most 007 1226D), such that for all co E jo E [J] and Feo.jo B2(FFeo.o: P),
N
yos ((( Teo.ol) - yoo 3
We let (*(x) = Ee Ej-1 Yas (((Feag) x)) and have 1f (TrooJo) - Yensol S e/3.
Lemma F2 (Lemma 6.5 from Zhang et al. (2020b)). For all E (0, there exist M poly(d, (NJ and R = poly((NJ/e)///) such that for m 2 M, with probability at least 1 exp( (o Mm/JJ)) over the choice of (0)) E Rm, U(0) RRdx,, b(O) E R there exists U Bdxm that satisfies U(0]l2,,> I R/m2/3 and
sup lg0. (z) (x(x) S e/3. mex
F.2 EXISTENCE RESULT
The goal of this section to prove Theorem F.3 which is the existence result.
Theorem F.3 (Existence, formal version of Theorem 5.2). For all e E (0, 1), there exist
Mg poly(d, (NJ and R poly((NNJ(c"))
such that for every m > My. with probability at least 1 - exp(pxX(mm 1/3) over the randomness of a(0) TR. U()) Rd b(0) E R.T,, there exists U Rdxm that satisfies I (0) S R/m2/3 and
(A-( Se.
Proof. From Lemma F.1 we obtain the function f*, From Lemma F.2 we know the existence of
Mo = poly(d, (N1) and also
/oe)((NJ/e))/)). By combining these two results
with Theorem D.2, we have that for all m 2 poly(d, (N)))) with probability at least 1 cxp(-S((/m/NV) exp(( 1/3), there exists a IRdx that satisfies [U))- S
R/m22/3 and also the following properties:
Vx E X' 1gu- (x) f²x)
Va e x, (fu- - gu-
-u- (x)) & /ORR/mm/6)
We consider the loss function. For all e [N]. E [J] and Fag E (B.agj p): we have
(Tas), vo.) 5 1.v- (Tc,)) Vo.j
< f.u- (To.) gu- (To,)) + 1gu- (Fes) f= (Tas) - yeul
< RR² 1/6)
3
SC
27

---

Under review as a conference paper at ICLR 2022
Thus, have that L. (fu-)) NJ Ee= Σj=1 max l (fu- (x% Ne.)) Furthermore, since the m we consider satisfies m 2 ((((N)) ), the holding probability is at least
1 - cxp((22(ymmmm))
exp( exp(-s((m
(xp(-S(())1)).
Thus, we finish the proof of this theorem.
28


Reviews:
[{"review_id": "tko-PVLCOA", "reviewer": "Reviewer_KhJu", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Strength:\n1\\ This paper provides rigorous analysis and all the details are well written.\n2\\ Adversarial learning and federated learning are both becoming more and more important in ML area. This paper is the first works to give theoretical guarantees on AFL which I believe has some significance.\n3\\ Their proposed AFL framework also shows many promising directions for future analysis.\n\nWeakness:\n1\\  As the authors claimed in the paper, their analysis is not tight. They argue that their main focus is to give the first step for AFL convergence analysis.\n2\\ Their technical contributions, despite rigorous analysis, is limited:\na. They use many assumptions include lie overparameterization, separability, and bounded adversarial samples. Although I understand this is somehow standard in much previous analysis, I still think it simplifies a lot of proofs.\nb. Many of their proofs are built upon previous results. For example, the first part of their analysis -- the existence of small robust loss, is mostly a small modification from existing methods (as the authors show in the appendix. F) and has little relation with FL. In the second part, although they emphasize their analysis on the newly defined FL gradient, to me it is a very natural definition. And the analysis to bound those differences is also expected.\n\nQuestion:\nIn Definition B.4 ($\\gamma$-seperability), it seems to me in order to satisfy $\\gamma \\leq \\delta(\\delta-2\\rho)$, we requires $\\rho < \\delta/2 < 1/4$.  And I wonder will this assumption simplifies the analysis a lot? Can you give more justification for this assumption？ What if you have a weaker assumption like allows the adversary to be even stronger, is it still possible to prove the convergence?\n ", "summary_of_the_paper": "This paper proposes a federated adversarial learning (FAL) framework with strong theoretical guarantees. Compared to the centralized model, the federated model allows each local client to generate the adversarial samples and updates the gradient themselves for several iterations and then communicate to the centralized model for global updating.  This is the first work that gives convergence guarantees for FAL.\n\nTheir technical analysis mainly involves two parts In the first part, they utilize the overparameterization and separability assumption to ensure the initialized model is close to some model U^* which can achieve the small robust loss. Then in the second part, by using such property on the initialized model and by bounding the difference between real gradient and the FL gradient, they are able to show the convergence. As the authors stated, this FL gradient is a new gradient they use to tackle the difference between global and local updates. ", "summary_of_the_review": "Overall I think the author proposes a useful framework with rigorous analysis but I am somehow concerned with the technical novelty of this paper. I think it would be better if the author can get a higher bound and make more efforts to relax some assumptions (or give more discussion on the necessity/difficulty of those assumptions)", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "p-wn5seeUeH", "reviewer": "Reviewer_e6rQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "Strengths:\n* The robustness of neural networks is an important problem and how the distributed learning will converge under adversarially robust training is also crucial in practice.\n* The authors have clarified most assumptions and conclusions.\n* The proposed analysis method, pseudo gradient based on a pseudo-network, is interesting, which may be inspiring for other theoretic work.\n\nWeakness\n* The challenges caused by the interaction of the federated optimization and the min-max optimization are not clear enough. It is not specific enough to mention that local update steps and global communication are novel settings. The authors may need to elaborate on why the integration is hard in terms of convergence analysis. Specifically, how the problem is different from traditional federated with distributional shift [A] if the adversarial noise is simply treated as a bounded noise?\n* The discussion of related work on federated convergence seems missing, either in the introduction or related work sections. For example, both [A] and [B] theoretically analyze the federated learning under noise.\n* The technical implications of the main theorem (4.1) are not elaborated, either in Section 4 or later. The authors only vaguely mention that controlling local/global learning rates will be helpful for convergence (in Section 6) but not clear how. Actually, I believe it is folk knowledge that decreasing the learning rate is important merely for FedAvg [C]. Lacking useful implications apparently lowers the value of the work in the community of ICLR.\n\nReferences:\n* [A] Reisizadeh, A., Farnia, F., Pedarsani, R., & Jadbabaie, A. (2020). Robust Federated Learning: The Case of Affine Distribution Shifts. NeurIPS.\n* [B] Yin, D., Chen, Y., Kannan, R., & Bartlett, P. (2018). Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates. ICML\n* [C] Li, X., Huang, K., Yang, W., Wang, S., & Zhang, Z. (2020). On the Convergence of FedAvg on Non-IID Data. ICLR", "summary_of_the_paper": "The paper formulate a general form of federated adversarial learning (FAL), based on which the authors theoretically analyze the convergence of FAL. They concluded that convergence is possible with chosen learning rate and communication round for distribution-agnostic clients.", "summary_of_the_review": "The studied problem is interesting and important. However, the related work is not well discussed and the conclusion is weak for me. The authors should try to clarify and establish the novelty of the problem contradicting related robust federated learning. ", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "_XdtMop2DG2", "reviewer": "Reviewer_Gk6a", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Pros:\n\n1. This paper is well written and organized, which allows a clear read.\n2. This work is well motivated by the challenge of applying adversarial training into federated learning.\n3. This paper provides a framework to analyze federated adversarial training in over-parameterized neural networks.\n\nCons:\n\n1. The first reason for harder to analyze the convergence of federated adversarial training seems to be not unique in the federated learning paradigm, and (in my opinion) the second reason is the cause of the former. Thus, it may be better to consider the Non-IID setting in federated learning as one important research focus when analyzing the plain combination of adversarial training with federated learning or to give more insights about the challenge of adversarial training with the Non-IID setting. \n2. Although this paper provides the comprehensive proof of theoretical convergence guarantee for over-parameterized ReLU network on the presented federated adversarial training, it is limited in the term of showing other insights for the unique challenge of adversarial training will meet in federated learning, which may be more significant and interesting for other future research.  \n\nMinor:\n\n1. The two reasons in the abstract seem to be not consistent with the \"involved challenges\" in the latter of the introduction, are they refer to the same focus?", "summary_of_the_paper": "This paper studies the provable property of applying adversarial training into federated learning from the theoretical perspective. Specifically, the authors provide a framework for analyzing federated adversarial training and present the convergence analysis in the over-parameterized regime, the main results theoretically show that the minimal value of loss function in this learning paradigm can converge to $\\epsilon$ small under certain circumstances.", "summary_of_the_review": "This paper provides convergence analysis for federated adversarial training, which theoretically shows the feasibility of applying adversarial training to federated learning. However, it may be not easy to see some in-depth insights or huge novelty in the current submission.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SBpbe3PK74r", "reviewer": "Reviewer_vGrK", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "Strengths: combining adversarial robustness with federated learning is definitely a new setting, and has the potential of training robust models collaboratively against perturbation. This paper aims to study FedAvg theoretically in this setting, and it gives theoretical results for the convergence, by controlling the noise from local updates, from the two-layer network, and from the adversarial perturbation.\n\nWeakness: one of my major concerns is the novelty against Zhang et al 2020b. Specifically, \n\n1) Def 3.1, 3,2 are the same as Sec 3.2 from Zhang et al. (They are not definitions per se but Assumptions)\n2) Def 3.3 is the same as Def 3.2 from Zhang et al.\n3) Def 3.4 is the same as Def 3.4 from Zhang et al.\n4) Def 3.5 is the same as Def 3.1 from Zhang et al.\n5) Def 3.6 resembles Def 3.3 from Zhang et al.\n6) Thm 4.1 resembles Thm 4.1 from Zhang et al.\n\nThe techniques such as pseudo-network is also from Zhang et al. \n\nThe improvement is not strong either. Since Zhang et al. proposed linear pseudo-network to approximate the two-layer over-parametrized ReLU, using FL gradient to approximate the gradient is nothing but adding another approximation error term. \n\nGiven that the theoretical contribution is not quite strong, I would expect the authors to conduct experiments in FL adversarial training, to verify their theory. However, no experiment is provided. The reason might be because the theory analyzed does not exactly match the common experimental setting in FL, e.g., two-layer neural networks, polynomial hidden units, convex Lipschitz loss, and gamma-separability. \nI doubt whether such theory could be of any use to the FL community. \n\nIn fact, many adversarial attacks are not small perturbation, e.g., adversarial patch:\n\n[1] Brown et al, Adversarial patch, NIPS 2017.\n\nHowever, the current theory requires very small perturbation in order to control the approximation error (Table 2, Appendix E). \n ", "summary_of_the_paper": "This paper is a direct follow-up of Zhang et al 2020b. With assumptions including overparametrized two-layer ReLU network, normalized dataset, gamma-separability, and Lipschitz convex loss, it proves the convergence of FedAvg under adversarial perturbation. These assumptions are easy adaptations from Zhang et al 2020b. \n\n\n--post rebuttal--\n\nI would like to thank the authors for the response. However, after reading the author response my opinion remains the same, as the authors acknowledge that this work is an extension of Zhang et al 2020b and there is no experiment after the revision. My main concern is still the novelty. I would encourage the authors to work on the future direction for empirically verifying their general framework.\n\n", "summary_of_the_review": "Given the above novelty concern and the lack of experiments, I would recommend rejection. I would suggest the authors rethink the practicability of the assumptions considered, rather than directly borrow these assumptions from existing literature. It would be much more interesting if the authors could give some experiments to demonstrate the proposed algorithm.", "strength_and_weaknesses": "", "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": "Not applicable"}, "extra_text": {}}, {"review_id": "7UoAPS98Hzp", "reviewer": "Reviewer_Pwgr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "\n1) It is unclear what are the technical difficulties to extend classical centralized adversarial training to the federated setting. Given current researches on adversarial learning, federated learning and deep learning theory, what are the contributions of this submission?  What are the gaps that this paper addresses? \n\n2) There is a lack of experiments, which makes the proposed methods unconvincing. Can the proposed framework really enhance the robustness of the federated learning? Have the data heterogeneity issue really get solved? And so on.  \n\n3) It would be very helpful that the authors give some concrete application examples in federated learning where a specific data generating algorithm  \\mathcal{A} can help to fix a certain type of robust concern, by both theory and experiments.\n\nI would like to see these concerns can be addressed by the authors' feedback.", "summary_of_the_paper": "This paper proposes a federated adversarial learning framework where clients generate adversarial data and do local updates while the server aggregate the local models to do global updates. ", "summary_of_the_review": "I tend to vote for a rejection due to the lack of novelty, clear theoretical justifications and experiments. ", "strength_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: The reviewers had a number of concerns which seem to remain after the authors response. In particular, the reviewers were concerned about the validity of the paper's assumptions in real-world applications and lack of experimental results. Also, while the reviewers acknowledge the novelty in technical contributions, they suggested that the authors explain more clearly how the results of this paper are distinguishable from prior art.
Decision: Reject