Year: 2021

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 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 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 clientside 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 algorithm can converge to small with chosen learning rate and communication rounds. It is noteworthy that our analysis is feasible for non-IID clients.

heading: 1 INTRODUCTION
text: Federated learning (FL) is playing an important role nowadays, as 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 easy-to-implement distributed learning method without data sharing. Specifically, it requires a central server to aggregate model updates computed by the local participants (also known as nodes or clients) using local imparticipable private data. Then the central server aggregates these updates to train a globally learned model.
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 answers (Szegedy et al., 2013). In this regard, much effort has been made to 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 samples 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 et 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 on low convergence rate, application
in non-IID 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 to theoretically study the unexplored convergence challenges that lie in the interaction between adversarial training and FL. To achieve a general understanding, we consider a 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)) 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 1.
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 convergence on over-parameterized neural network has achieved tremendous progress (Du et al., 2019a; Allen-Zhu et al., 2019b;c; 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 answer the above interesting but challenging question, we formulate FAL as an min-max optimization problem. We extend the convergence analysis on the general formulation of over-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 to 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 over-parameterized neural networks. We follow a natural and valid assumption of data separability that the training dataset are well separated apropos of the adversarial perturbations’ magnitude. After sufficient 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-IID clients.
• We are the first to theoretically formulate the convergence of the FAL problem into a minmax optimization framework with the proposed loss function. In FL, 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-parameterized assumptions, we use gradient coupling for gradient 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
Section 4. In Section 5, we present the core techniques and an overview of the proof. We summarize and conclude our results in Section 6.

heading: 2 RELATED WORK
text: Federated Learning A efficient and privacy-preserving way to learn from the distributed data collected on the edge devices (a.k.a clients) would be FL. FedAvg is a easy-to-implement 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; Li 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 to 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 et al., 2018; Li et al., 2019; 2021; 2020a). Despite the potential risk in security and unstable performance in nonIID setting, as FL mitigates the concern of data sharing, it 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; 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 defense 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 et al., 2014). It produces 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 distinguishable 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) is a popular protocol to train more adversarial robust models by inserting adversarial examples in training. The use of adversarial training in FL presents a 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 so on. To defend the adversarial attacks in federated learning, limited recent studies have proposed to include adversarial training on clients in the local 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-parameterized neural networks falls in two lines. In the first line of work (Li & Liang, 2018; Allen-Zhu et al., 2019b;c;a), data separability plays a crucial role in deep learning theory, especially in showing the convergence result of over-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 at least polynomial factor of all the parameters (i.e. m ≥ poly(n, d, 1/δ)), where n is the number of data points and d is the dimension of data. Another line of work (Du et al., 2019b; Arora et al., 2019a;b; Song & Yang, 2019; Lee et al., 2020) builds on neural tangent kernel (Jacot et al., 2018). It requires the minimum eigenvalue (λ) 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 analyzed the robustness of federated learning under noise. Yin et al. (2018) developed distributed optimization algorithms that were provably robust against arbitrary and potentially adversarial behavior in distributed computing systems, and mainly focused on achieving optimal statistical performance. Reisizadeh et al. (2020) developed a robust federated learning algorithm by considering a structured
affine distribution shift in users’ data. Their analysis was built on several assumptions on the loss functions without a direct connection to neural network.

heading: 3 PROBLEM FORMULATION
text: To explore the properties of FAL in deep learning, we formulate the problem in over-parameterized neural network regime. We start by presenting the notations and setup required for federated adversarial 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.

heading: 3.1 NOTATIONS
text: For a vector x, we use ‖x‖p to denote its `p norm, in this paper we mainly consider the situation when p = 1, 2, or∞. For a matrixW ∈ Rd×m, we useW> to denote its transpose and use tr[W ] to denote its trace. We use ‖W‖1, ‖W‖2 and ‖W‖F to denote the entry-wise `1 norm, spectral norm and Frobenius norm ofW respectively. For each j ∈ [m], we letWj ∈ Rd be the j-th column ofW . We let ‖W‖2,1 denotes ∑m j=1 ‖Wj‖2 and ‖W‖2,∞ denotes maxj∈[m] ‖Wj‖2. We denote Gaussian distribution with mean µ and covariance Σ as N (µ,Σ). We use σ(·) to denote the ReLU function σ(z) = max{z, 0}, and use 1{E} to denote the indicator function of event E.

heading: 3.2 PROBLEM SETUP
text: 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;b; Song & Yang, 2019; Lee et al., 2020), in this paper, we focus on a two-layer neural network that has m neurons in the hidden layer, where each neuron is a ReLU activation function. We define the global network as
fU (x) := m∑ r=1 ar · σ(〈Ur, x〉+ br) (1)
and for c ∈ [N ], we define the local network of client c as
fWc(x) := m∑ r=1 ar · σ(〈Wc,r, x〉+ br). (2)
Here U = (U1, . . . , Um) ∈ Rd×m is the global hidden weight matrix, Wc = (Wc,1, . . . ,Wc,m) ∈ Rd×m is the local hidden weight matrix of client c, and a = (a1, . . . , am) ∈ Rm denotes the output weight vector, b = (b1, . . . , bm) ∈ Rm denotes the bias vector. During the process of federated adversarial learning, we only update U and W , keeping a and b equal to their initialization values, so we can write the global network as fU (x) and the local network as fWc(x). For the situation we don’t care about the weight matrix, we write f(x) or fc(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.1 Let S = ∪c∈[N ]Sc where Sc = {(xc,1, yc,1), ..., (xc,J , yc,J)} ⊆ Rd × R denotes the J training data of client c. Without loss of generality, we assume that for all c ∈ [N ], j ∈ [J ], ‖xc,j‖2 = 1 and the last coordinate of each point equals to 1/2 , so we consider X := {x ∈ Rd : ‖x‖2 = 1, xd = 1/2}. For simplicity, we also assume that for all c ∈ [N ], j ∈ [J ], |yc,j | ≤ 1.2
We now define the initialization for the neural networks. 1Without loss of generality, we assume that all clients have same number of training data. Our result can be generalized to the setting where each client has a different number of data as the future work. 2Our assumptions on data points are reasonable since we can do scale-up. In addition, l2 norm normalization is a typical technique in experiments. Same assumptions also appears in many previous theoretical works like Arora et al. (2019b); Allen-Zhu et al. (2019a;b).
Definition 3.2 (Initialization). The initialization of a ∈ Rm, U ∈ Rd×m, b ∈ Rm is a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm. The initialization of client c’s local weight matrix Wc is Wc(0, 0) = U(0). Here the second term in Wc denotes iteration of local steps.
• For each r ∈ [m], ar(0) are i.i.d. sampled from [−1/m1/3,+1/m1/3] uniformly.
• For each i ∈ [d], r ∈ [m], Ui,r(0) and br(0) are i.i.d. random Gaussians sampled from N (0, 1/m). Here Ui,r means the (i, r)-entry of U .
For each global iteration t ∈ [T ],
• For each c ∈ [N ], the initial value of client c’s local weight matrix Wc is Wc(t, 0) = U(t).
Next we formulate the adversary model that will be used. Definition 3.3 (ρ-Bounded adversary). Let F denote the function class. An adversary is a mapping A : F × X × R → X which denotes the adversarial perturbation. For ρ > 0, we define the `2 ball as B2(x, ρ) := {x̃ ∈ Rd : ‖x̃ − x‖2 ≤ ρ} ∩ X , we say an adversary A is ρ-bounded if it satisfies A(f, x, y) ∈ B2(x, ρ). Moreover, given ρ > 0, we denote the worst-case adversary as A∗ := argmaxx̃∈B2(x,ρ) `(f(x̃), y), where ` is loss function defined in Definition 3.5.
Well-separated training sets In the over-parameterized regime, it is a standard assumption that the training set is well-separated. Since we deal with adversarial perturbations, we require the following γ-separability, which is a bit stronger. Definition 3.4 (γ-separability). Let γ ∈ (0, 1/2), δ ∈ (0, 1/2), ρ ∈ (0, 1/2) denote three parameters such that γ ≤ δ ·(δ−2ρ). We say our training set S = ∪c∈[N ]Sc = ∪c∈[N ],j∈[J]{(xc,j , yc,j)} ⊂ Rd×R is globally γ-separable w.r.t a ρ-bounded adversary, if ‖xc1,j1 − xc2,j2‖2 ≥ δ holds for any c1 6= c2 and j1 6= j2.
It 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-IID setting in FL.

heading: 3.3 FEDERATED ADVERSARIAL LEARNING
text: Algorithm We focus on a general FAL framework that is adapted from the most common adversarial training in the classical setting on the client. Specifically, we describe the adversarial learning of a local neural network fWc against an adversary A that generate adversarial examples during training as shown in Algorithm 1. As for the analysis of a general theoretical analysis framework, we do not specify the explicit format of A. The FAL algorithm contains two procedures: one is CLIENTUPDATE running on client side and the other is SERVEREXECUTION running on server side. These two procedures are iteratively processed through communication iterations. Adversarial training is addressed in procedure 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 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 simplicity, as is customary in prior studies Gao et al. (2019); Allen-Zhu et al. (2019a): Definition 3.5 (Lipschitz convex loss). A loss function ` : R × R → R is said to be a Lipschitz convex loss, if it satisfies the following four properties:
• non-negative;
• convex with respect to the first input of `;
• 1−Lipshcitz, which means ‖`(x1, y1)− `(x2, y2)‖2 ≤ ‖(x1, y1)− (x2, y2)‖2;
• `(y, y) = 0 for all y ∈ R.
Algorithm 1 Federated Adversarial Learning (FAL) Notations: Training sets of clients with each client is indexed by c, Sc = {(xc,j , yc,j)}Jj=1; adversary A; local learning rate ηlocal; global learning rate ηglobal; local updating iterations K; global communication round T .
1: Initialization a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm 2: For t = 0→ T , we iteratively run Procedure A then Procedure B 3: procedure A. CLIENTUPDATE(t, c) 4: Sc(t)← ∅ 5: Wc(t, 0)← U(t) . Receive global model weights update. 6: for k = 0→ K − 1 do 7: for j = 1→ J do 8: x̃(t)c,j ← A(fWc(t,k), xc,j , yc,j) . Adversarial samples. fWc is defined as (2). 9: Sc(t)← Sc(t) ∪ (x̃(t)c,j , yc,j) 10: end for 11: Wc(t, k + 1)←Wc(t, k)− ηlocal · ∇WcL(fWc(t,k),Sc(t)) 12: end for 13: ∆Uc(t)←Wc(t,K)− U(t) 14: Send ∆Uc(t) to SERVEREXECUTION 15: end procedure 16: procedure B. SERVEREXECUTION(t): 17: for each client c in parallel do do 18: ∆Uc(t)← CLIENTUPDATE(c, t) . Receive local model weights update. 19: ∆U(t)← 1N ∑ c∈[N ] ∆Uc(t) 20: U(t+ 1)← U(t) + ηglobal ·∆U(t) . Aggregation on the server side. 21: Send U(t+ 1) to client c for CLIENTUPDATE(c, t) 22: end for 23: end procedure
In this paper we assume ` is a Lipschitz convex loss. Next, we define our robust loss function of a neural network, which is based on the adversarial examples generated by a ρ-bounded adversary A. Definition 3.6 (Training loss). Given a client’s training set Sc = {(xc,j , yc,j)}Jj=1 ⊂ Rd × R of J examples, the standard training loss of a neural net fc : Rd → R is defined as L(fc, Sc) := 1 J ∑J j=1 ` (fc(xc,j), yc,j). Given S = ∪c∈[N ]Sc, we define the global loss as L(fU , S) :=
1 NJ ∑N c=1 ∑J j=1 `(fU (xc,j), yc,j). Given a ρ-bounded adversary A, we define the global loss with respect to A as
LA(fU ) := 1
NJ N∑ c=1 J∑ j=1 `(fU (A(fc, xc,j , yc,j)), yc,j) = 1 NJ N∑ c=1 J∑ j=1 `(fU (x̃c,j), yc,j)
and also define the worst-case global robust loss as
LA∗(fU ) := 1
NJ N∑ c=1 J∑ j=1 `(fU (A∗(fc, xc,j , yc,j)), yc,j) = 1 NJ N∑ c=1 J∑ j=1 max x∗c,j∈B2(xc,j ,ρ) ` ( fU (x ∗ c,j), yc,j ) .
Moreover, since we deal with pseudo-net which is defined in Definition 5.1, we also define the loss of a pseudo-net as L(gc,Sc) := 1J ∑J j=1 ` (gc(xc,j), yc,j) and L(gU ,S) :=
1 NJ ∑N c=1 ∑J j=1 `(gU (xc,j), yc,j).

heading: 4 OUR RESULT
text: The main result of this work is showing the convergence of FAL algorithm (Algorithm 1) in overparameterized neural networks. Specifically, our defined global training loss (Definition 3.6) converges to a small with the chosen communication round T , local and global learning rate ηlocal, ηglobal. It is plausible to see that we can control ηlocal according to the local update steps K to achieve convergence. We now formally present our main result Theorem 4.1.
Theorem 4.1 (Federated Adversarial Learning). Let c0 ∈ (0, 1) be a 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 = ∪c∈[N ]Sc is globally γ-separable for some γ > 0. Then, for all ∈ (0, 1), there exists R = poly((NJ/ )1/γ) that satisfies: for all m ≥ poly(d, (NJ/ )1/γ), for every K ≥ 1 and T ≥ poly(R/ ), with probability at least 1 − exp(−Ω(m1/3)) over the randomness of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, running federated adversarial learning (Algorithm 1) with step size choices ηglobal = 1/ poly(NJ,R, 1/ ) and ηlocal = 1/K will output a list of weights {U(1), U(2), · · · , U(T )} ∈ Rd×m that satisfy
min t∈[T ]
LA(fU(t)) ≤ .

heading: 5 PROOF SKETCH
text: To handle the min-max objective in FAL, we formulate the optimization of FAL in the framework of online gradient descent3 : at each local step k on the client side, firstly the adversary generates adversarial samples and computes the loss function L ( fWc(t,k),Sc(t) ) , then the local client learner
takes the fresh loss function and update Wc(t, k+ 1) = Wc(t, k)− ηlocal · ∇WcL ( fWc(t,k),Sc(t) ) .
Compared with the centralized setting, the key difficulties in the convergence analysis of FL are induced by multiple local updates on the client side and the updates on both local and global sides. Specifically, local updates are not the standard gradient as the centralized adversarial training when K ≥ 2. We used −∆U(t) in substitution of the real gradient of U to update the value of U(t). This brings in challenges to bound the gradient of the neural networks. Nevertheless, gradient bounding is 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.

heading: 5.1 EXISTENCE OF SMALL ROBUST LOSS
text: In this section, we denote Ũ = U(0) as the initialization of global weights U and denote U(t) as the global weights of communication round t. U∗ is the value of U after small perturbations from Ũ which satisfies ‖U∗ − Ũ‖2,∞ ≤ R/mc1 , here c1 ∈ (0, 1) is a constant (e.g. c1 = 2/3), m is the width of the neural network and R is a parameter. We will specify the concrete value of these parameters later in appendix.
We study the over-parameterized neural nets’ well-approximated pseudo-network to learn gradient descent for over-parameterized neural nets whose weights are close to initialization. Pseudo-network can be seen as a linear approximation of our two layer ReLU neural network near initialization, and the introducing of pseudo-network makes the proof more intuitive. Definition 5.1 (Pseudo-network). Given weights U ∈ Rd×m, a ∈ Rm and b ∈ Rm, for a neural network fU (x) = ∑m r=1 ar · σ(〈Ur, x〉 + br), we define the corresponding pseudo-network gU :
Rd → R as gU (x) := ∑m r=1 ar · 〈Ur(t)− Ur(0), x〉 · 1{〈Ur(0), x〉+ br ≥ 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 U(0) and also makes LA∗(fU∗) sufficiently small. Later in Theorem 5.6 we show that the average of LA(fU(t)) is dominated by LA∗(fU∗), thus we can prove the minimum of LA(fU(t)) is small. Theorem 5.2 (Existence, informal version of Theorem F.3). For all ∈ (0, 1), there exists M0 = poly(d, (NJ/ )1/γ) and R = poly((NJ/ )1/γ) such that for every m ≥M0, with high probability there exists U∗ ∈ Rd×m that satisfies ‖U∗ − U(0)‖2,∞ ≤ R/mc1 and LA∗(fU∗) ≤ .

heading: 5.2 CONVERGENCE RESULT FOR FEDERATED LEARNING
text: For ease of presentation, we first describe the notions of local and global gradients in our federated adversarial learning setting.
3We refer our readers to Hazan (2016) for more details regarding online gradient descent.
Definition 5.3 (Gradient). For a local real network fWc(t,k), we denote its gradient by∇(fc, t, k) := ∇WcL(fWc(t,k),Sc(t)). If the corresponding pseudo-network is gWc(t,k), then denote the pseudonetwork gradient by ∇(gc, t, k) := ∇WcL(gWc(t,k),Sc(t)).
Now we consider the global network. We define pseudo gradient as ∇(g, t) := ∇UL(gU(t),S(t)) and define FL gradient as ∇̃(f, t) := − 1N∆U(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 at least 1 − exp(−Ω(mc0)) over the initialization, for iterations t such that ‖U(t)− U(0)‖2,∞ ≤ 1/o(m), the gradients satisfy ‖∇(f, t)− ∇̃(f, t)‖2,1 ≤ 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(−Ω(mc0)) over the initialization, for iterations t such that ‖U(t)−U(0)‖2,∞ ≤ 1/o(m), the gradients satisfy ‖∇(g, t)−∇(f, t)‖2,1 . NJ · 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 ∈ (0, 1), R ≥ 1, there exists an M = poly(n,R, 1/ ), such that for every m ≥ M , for every K ≥ 1, for every T ≥ poly(R/ ), with probability at least 1 − exp(−Ω(mc0)) over the randomness of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, for all U∗ such that ‖U∗ − U(0)‖2,∞ ≤ R/mc1 , running Algorithm 1 with setting ηglobal = 1/ poly(NJ,R, 1/ ) and ηlocal = 1/K will output weights (U(t))Tt=1 that satisfy 1T ∑T t=1 LA ( fU(t) ) ≤ LA∗ (fU∗) + .
In the proof of Theorem 5.6 we first bound the local gradient ∇r(fc, t, k). We consider the pseudo-network and bound L(gU(t), S(t)) − L(gU∗ , S(t)) ≤ α(t) + β(t) + γ(t), where α(t) := 〈∇̃(f, t), U(t) − U∗〉, β(t) = ‖∇(f, t) − ∇̃(f, t)‖2,1 · ‖U(t) − U∗‖2,∞ and γ(t) := ‖∇(g, t) − ∇(f, t)‖2,1 · ‖U(t)−U∗‖2,∞. In bounding α(t), we unfold ‖U(t+ 1)−U∗‖2F and by rearranging we have
α(t) = ηglobal
2 ‖∆U(t)‖2F +
1
2ηglobal · (‖U(t)− U∗‖2F − ‖U(t+ 1)− U∗‖2F ).
We bound ‖∆U(t)‖2F ≤ ηlocalK · o(m). By doing summation over t, we have T∑ t=1 α(t) = ηglobal 2 T∑ t=1 ‖∆U(t)‖2F + 1 2ηglobal · T∑ t=1 (‖U(t)− U∗‖2F − ‖U(t+ 1)− U∗‖2F )
≤ ηglobal 2 T∑ t=1 ‖∆U(t)‖2F + 1 2ηglobal · ‖U(1)− U∗‖2F
. ηglobalηlocalTK · o(m) + 1
ηglobal mD2U∗
In bounding β(t), we apply Lemma 5.4 and have
β(t) = ‖∇(f, t)− ∇̃(f, t)‖2,1 · ‖U(t)− U∗‖2,∞ . o(m) · ‖U(t)− U∗‖2,∞ . o(m) · (‖U(t)− Ũ‖2,∞ +DU∗).
where DU∗ := ‖U∗ − Ũ‖2,∞ ≤ R/mc1 . As for the first term, we bound
‖U(t)− Ũ‖2,∞ ≤ ηglobal t∑
τ=1
‖∆U(τ)‖2,∞
= ηglobal t∑ τ=1 ‖ηlocal N N∑ c=1 K−1∑ k=0 ∇(fc, t, k)‖2,∞
≤ ηglobalηlocal N t∑ τ=1 N∑ c=1 K−1∑ k=0 ‖∇(fc, t, k)‖2,∞ ≤ ηglobalηlocaltKm−1/3
and have β(t) . ηglobalηlocaltK · o(m) + o(m) ·DU∗ , then we do summation and obtain
T∑ t=1 β(t) . ηglobalηlocalT 2K · o(m) + o(m) · TDU∗ .
In bounding γ(t), we apply Lemma 5.5 and have
γ(t) = ‖∇(g, t)−∇(f, t)‖2,1 · ‖U(t)− U∗‖2,∞ . NJ · o(m) · (‖U(t)− Ũ‖2,∞ +DU∗).
Then we do summation over t and have T∑ t=1 γ(t) . ηglobalηlocalT 2KNJ · o(m) + TNJ · o(m)DU∗
Putting it together with our choice of our all parameters (i.e. ηlocal, ηglobal, R,K, T,m), we obtain
1
T T∑ t=1 L(gU(t), S(t))− 1 T T∑ t=1 L(gU∗ , S(t)) ≤ 1 T ( T∑ t=1 α(t) + T∑ t=1 β(t) + T∑ t=1 γ(t)) ≤ O( ).
From Theorem D.2 in appendix, we have: supx∈X |fU (x)− gU (x)| ≤ O( ), and thus,
1
T T∑ t=1 L(fU(t),S(t))− 1 T T∑ t=1 L(fU∗ ,S(t)) ≤ O( ). (3)
From the definition of A∗ we have L(fU∗ , S(t)) ≤ LA∗(fU∗). From the definition of loss we have L(fU(t),S(t)) = LA(fU(t)). Moreover, since Eq. (3) holds for all > 0, we can replace O( ) with . Thus we prove that for ∀ > 0,
1
T T∑ t=1 LA(fU(t)) ≤ LA∗(fU∗) + .
Combining the results From Theorem 5.2 we 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 LA(fU(t)) is dominated by LA∗(fU∗). By aggregating these two results, we prove that the minimal of LA(fU(t)) is small and finish the proof of our main Theorem 4.1.

heading: 6 CONCLUSION
text: We have studied the convergence of a general format of adopting adversarial training in FL setting to improve FL training robustness. We propose the general framework, FAL, which deploys adversarial samples generation-based adversarial training method on the client-side and then aggregate local model using FedAvg (McMahan et al., 2017). In FAL, each client is trained via min-max optimization with inner loop adversarial generation and outer loop loss minimization. To the best of our knowledge, we are 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 ηlocal and ηglobal according to the local update steps K and global communication round T to make the minimal loss close to zero. The technical challenges lie in the multiple local update steps and heterogeneous data, leading to the difficulties of convergence. Under ReLU Lipschitz and over-prameterization assumptions, 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 assumptions 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 to other FL aggregation methods, such as sketching and selective aggregation.

heading: ETHICS STATEMENT
text: Ensuring the security and robustness of the deployed algorithms is of paramount importance in AI algorithms nowadays. Recently, machine learning training has revealed its vulnerability to adversarial 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 a theoretical work, we do not involve any human subjects or datasets. Our work has the potential positive impact on the machine learning community.

heading: REPRODUCIBILITY STATEMENT
text: We provide the proof details in the appendix to ensure reproducibility.

heading: A PROBABILITY TOOLS
text: We introduce the probability tools that will be used in our proof. First we show three lemmas about the tail bounds for random scalar variables in Lemma A.1, A.2 and A.3: Lemma A.1 (Chernoff bound Chernoff (1952)). Let X = ∑n i=1Xi, where Xi = 1 with probability
pi and Xi = 0 with probability 1−pi, and all Xi are independent. Let µ = E[X] = ∑n i=1 pi. Then 1. Pr[X ≥ (1 + δ)µ] ≤ exp(−δ2µ/3), ∀δ > 0 ; 2. Pr[X ≤ (1− δ)µ] ≤ exp(−δ2µ/2), ∀0 < δ < 1. Lemma A.2 (Hoeffding bound Hoeffding (1963)). Let X1, · · · , Xn denote n independent bounded variables in [ai, bi]. Let X = ∑n i=1Xi, then we have
Pr[|X − E[X]| ≥ t] ≤ 2 exp ( − 2t
2∑n i=1(bi − ai)2
) .
Lemma A.3 (Bernstein inequality Bernstein (1924)). Let X1, · · · , Xn be independent zero-mean random variables. Suppose that |Xi| ≤M almost surely, for all i. Then, for all positive t,
Pr [ n∑ i=1 Xi > t ] ≤ exp ( − t 2/2∑n j=1 E[X2j ] +Mt/3 ) .
Next, we introduce Lemma A.4 about CDF of Gaussian distributions: Lemma A.4 (Anti-concentration of Gaussian distribution). Let X ∼ N (0, σ2), that is, the probability density function of X is given by φ(x) = 1√
2πσ2 e−
x2 2σ2 . Then
Pr[|X| ≤ t] ∈ ( 2
3
t σ , 4 5 t σ
) .
Finally, we introduce Lemma A.5 as a concentration result on random matrices and Claim A.6 about elementary anti-concentration property of Gaussian distribution. Lemma A.5 (Matrix Bernstein, Theorem 6.1.1 in Tropp (2015)). Consider a finite sequence {X1, · · · , Xm} ⊂ Rn1×n2 of independent, random matrices with common dimension n1 × n2. Assume that
E[Xi] = 0,∀i ∈ [m] and ‖Xi‖ ≤M,∀i ∈ [m]. Let Z = ∑m i=1Xi. Let Var[Z] be the matrix variance statistic of sum:
Var[Z] = max {∥∥∥ m∑ i=1 E[XiX>i ] ∥∥∥,∥∥∥ m∑ i=1 E[X>i Xi] ∥∥∥} .
Then
E[‖Z‖] ≤ (2Var[Z] · log(n1 + n2))1/2 + M · log(n1 + n2)/3.
Furthermore, for all t ≥ 0, Pr[‖Z‖ ≥ t] ≤ (n1 + n2) · exp ( − t 2/2
Var[Z] +Mt/3
) .
We state a standard probabilistic result for Gaussian, Claim A.6. Let u ∼ N (0, Id) and β ∼ N (0, 1), which are independent. For all x ∈ X and t ≥ 0,
Pr[|〈u, x〉+ β| ≤ t] = O(t).

heading: B PRELIMINARIES

heading: B.1 NOTATIONS
text: For a vector x, we use ‖x‖p to denote its `p norm, in this paper we mainly consider the situation when p = 1, 2, or∞. For a matrix W ∈ Rd×m, we use W> to denote its transpose and use tr[W ] to denote its trace. We use ‖W‖1, ‖W‖2 and ‖W‖F to denote the entry-wise `1 norm, spectral norm and Frobenius norm of W respectively. For each j ∈ [m], we let Wj ∈ Rd be the j-th column of W . We let ‖W‖2,1 denotes ∑m j=1 ‖Wj‖2 and ‖W‖2,∞ denotes maxj∈[m] ‖Wj‖2. For two matricesA,B with the same dimensions, we denote their Euclidean inner product as 〈A,B〉 := tr[A>B]. We denote Gaussian distribution with mean µ and covariance Σ as N (µ,Σ). We use σ(·) to denote the ReLU function σ(z) = max{z, 0}, and use 1{E} to denote the indicator function of event E.

heading: B.2 TWO LAYER RELU NEURAL NETWORK AND INITIALIZATION
text: In this paper, we focus on a two-layer neural network that has m neurons in the hidden layer, where each neuron is a ReLU activation function. We define the global network as
fU (x) := m∑ r=1 ar · σ(〈Ur, x〉+ br) (4)
and for c ∈ [N ], we define the local network of client c as
fWc(x) := m∑ r=1 ar · σ(〈Wc,r, x〉+ br). (5)
Here U = (U1, . . . , Um) ∈ Rd×m is the global hidden weight matrix, Wc = (Wc,1, . . . ,Wc,m) ∈ Rd×m is the local hidden weight matrix of client c, and a = (a1, . . . , am) ∈ Rm denotes the output weight vector, b = (b1, . . . , bm) ∈ Rm denotes the bias vector. During the process of federated adversarial learning, for convenience we keep a and b equal to their initialized values and only update U and W , so we can write the global network as fU (x) and the local network as fWc(x). For the situation we don’t care about the weight matrix, we write f(x) or fc(x) for short. Next, we make some standard assumptions regarding our training set.
Definition B.1 (Dataset). There are N clients and n = NJ data in total.4 Let S = ∪c∈[N ]Sc where Sc = {(xc,1, yc,1), ..., (xc,J , yc,J)} ⊆ Rd × R denotes the J training data of client c. Without loss of generality, we assume that for all c ∈ [N ], j ∈ [J ], ‖xc,j‖2 = 1 and the last coordinate of each point equals to 1/2 , so we consider X := {x ∈ Rd : ‖x‖2 = 1, xd = 1/2}. For simplicity, we also assume that for all c ∈ [N ], j ∈ [J ], |yc,j | ≤ 1.5
We now define the initialization for the neural networks.
Definition B.2 (Initialization). The initialization of a ∈ Rm, U ∈ Rd×m, b ∈ Rm is a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm. The initialization of client c’s local weight matrix Wc is Wc(0, 0) = U(0). Here the second term in Wc denotes iteration of local steps.
• For each r ∈ [m], ar(0) are i.i.d. sampled from [−1/m1/3,+1/m1/3]6 uniformly.
• For each i ∈ [d], r ∈ [m], Ui,r(0) and br(0) are i.i.d. random Gaussians sampled from N (0, 1/m). Here Ui,r means the (i, r)-entry of U .
4Without loss of generality, we assume that all clients have same number of training data. Our result can be generalized to the setting where each client has a different number of data as the future work.
5Our assumptions on data points are reasonable since we can do scale-up. In addition, l2 norm normalization is a typical technique in experiments. Same assumptions also appears in many previous theoretical works like Arora et al. (2019b); Allen-Zhu et al. (2019a;b).
6Here the choice of m1/3 is not a must. Actually what we need is [−1/mc,+1/mc] for some c that satisfies Ω(1) ≤ c ≤ 1/3.
For each global iteration t ∈ [T ],
• For each c ∈ [N ], the initial value of client c’s local weight matrix Wc is Wc(t, 0) = U(t).

heading: B.3 ADVERSARY AND WELL-SEPARATED TRAINING SETS
text: We first formulate the adversary as a mapping. Definition B.3 (ρ-Bounded adversary). Let F denote the function class. An adversary is a mapping A : F × X × R→ X which denotes the adversarial perturbation. For ρ > 0, we define the `2 ball as B2(x, ρ) := {x̃ ∈ Rd : ‖x̃− x‖2 ≤ ρ} ∩ X , we say an adversary A is ρ-bounded if it satisfies
A(f, x, y) ∈ B2(x, ρ). Moreover, given ρ > 0, we denote the worst-case adversary as A∗ := argmaxx̃∈B2(x,ρ) `(f(x̃), y), where ` is loss function defined in Definition B.5.
In the over-parameterized regime, it is a standard assumption that the training set is well-separated. Since we deal with adversarial perturbations, we require the following γ-separability, which is a bit stronger. Definition B.4 (γ-separability). Let γ ∈ (0, 1/2), δ ∈ (0, 1/2), ρ ∈ (0, 1/2) denote three parameters such that γ ≤ δ ·(δ−2ρ). We say our training set S = ∪c∈[N ]Sc = ∪c∈[N ],j∈[J]{(xc,j , yc,j)} ⊂ Rd × R is globally γ-separable w.r.t a ρ-bounded adversary, if
min c1 6=c2,j1 6=j2 ‖xc1,j1 − xc2,j2‖2 ≥ δ.
It 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-IID setting in FL.

heading: B.4 ROBUST LOSS FUNCTION
text: We define the following Lipschitz convex loss function that will be used. Definition B.5 (Lipschitz convex loss). A loss function ` : R × R → R is said to be a Lipschitz convex loss, if it satisfies the following four properties:
• non-negative;
• convex in the first input of `;
• 1−Lipshcitz, which means ‖`(x1, y1)− `(x2, y2)‖2 ≤ ‖(x1, y1)− (x2, y2)‖2;
• `(y, y) = 0 for all y ∈ R.
The choice of this type of loss is for the sake of technical presentation simplicity, as is customary in prior studies Gao et al. (2019); Allen-Zhu et al. (2019a).
We assume ` is a Lipschitz convex loss in this paper. Next, we define our robust loss function of a neural network, which is based on the adversarial examples generated by a ρ-bounded adversary A. Definition B.6 (Training loss). Given a client’s training set Sc = {(xc,j , yc,j)}Jj=1 ⊂ Rd × R of J examples, the standard training loss of a neural net fc : Rd → R is defined as L(fc,Sc) := 1 J ∑J j=1 ` (fc(xc,j), yc,j). Given S = ∪c∈[N ]Sc, the global loss is defined as L(fU ,S) :=
1 NJ ∑N c=1 ∑J j=1 `(fU (xc,j), yc,j). Given a ρ-bounded adversary A, we define the global loss with respect to A as
LA(fU ) := 1
NJ N∑ c=1 J∑ j=1 `(fU (A(fc, xc,j , yc,j)), yc,j)
= 1
NJ N∑ c=1 J∑ j=1 `(fU (x̃c,j), yc,j)
and also define the worst-case global robust loss as
LA∗(fU ) := 1
NJ N∑ c=1 J∑ j=1 `(fU (A∗(fc, xc,j , yc,j)), yc,j)
= 1
NJ N∑ c=1 J∑ j=1 max x∗c,j∈B2(xc,j ,ρ) ` ( fU (x ∗ c,j), yc,j ) .
Moreover, since we deal with pseudo-net which is defined in Definition D.1, we also define the loss of a pseudo-net as L(gc,Sc) := 1J ∑J j=1 ` (gc(xc,j), yc,j) and L(gU ,S) :=
1 NJ ∑N c=1 ∑J j=1 `(gU (xc,j), yc,j).

heading: B.5 FEDERATED ADVERSARIAL LEARNING ALGORITHM
text: Classical adversarial training algorithm can be found in Zhang et al. (2020b). Different from the classical setting, our federated adversarial learning of a local neural network fWc against an adversaryA is shown in Algorithm 2, where there are two procedures: one is CLIENTUPDATE running on client side and the other is SERVEREXECUTION running on server side. These two procedures are iteratively processed through communication iterations. Adversarial training is addressed in procedure 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 SERVEREXECUTION procedure, the neural network’s parameters are updated to reduce its prediction loss on the new adversarial samples. These loops constitute an intertwining dynamics.
Algorithm 2 Federated Adversarial Learning (FAL). This is a 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 c is denoted as Sc = {(xc,j , yc,j)}Jj=1 4: Let A be the adversary 5: We denote local learning rate as ηlocal 6: We denote global learning rate as ηglobal 7: We denote local updating iterations as K 8: We denote global communication round as T 9: 10: /*Initialization*/ 11: Initialization a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm 12: For t = 0→ T , we iteratively run Procedure A then Procedure B 13: 14: /* Procedure running on client side */ 15: procedure A. CLIENTUPDATE(t, c) 16: Sc(t)← ∅ 17: Wc(t, 0)← U(t) . Receive global model weights update 18: for k = 0→ K − 1 do 19: for j = 1→ J do 20: x̃(t)c,j ← A(fWc(t,k), xc,j , yc,j) . Adversarial examples, fWc is defined as (5) 21: Sc(t)← Sc(t) ∪ (x̃(t)c,j , yc,j) 22: end for 23: Wc(t, k + 1)←Wc(t, k)− ηlocal · ∇WcL(fWc(t,k),Sc(t)) 24: end for 25: ∆Uc(t)←Wc(t,K)− U(t) 26: Send ∆Uc(t) to SERVEREXECUTION 27: end procedure 28: 29: /*Procedure running on server side*/ 30: procedure B. SERVEREXECUTION(t): 31: for each client c in parallel do 32: ∆Uc(t)← CLIENTUPDATE(c, t) . Receive local model weights update 33: ∆U(t)← 1N ∑ c∈[N ] ∆Uc(t) 34: U(t+ 1)← U(t) + ηglobal ·∆U(t) . Aggregation on the server side 35: Send U(t+ 1) to client c for CLIENTUPDATE(c, t) 36: end for 37: end procedure

heading: C PROOF OVERVIEW
text: In this section we give an overview of our main result’s proof. Two theorems to be used are Theorem E.3 and Theorem F.3.

heading: C.1 PSEUDO-NETWORK
text: We study the over-parameterized neural nets’ well-approximated pseudo-network to learn gradient descent for over-parameterized 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 approximates the real network uniformly well. It can be seen that the notion of pseudo-network is used for several times in our proof.

heading: C.2 ONLINE GRADIENT DESCENT IN FEDERATED ADVERSARIAL LEARNING
text: Our federated adversarial learning algorithm is formulated in the framework of online gradient descent: at each local step k on the client side, firstly the adversary generates adversarial samples and computes the loss function L ( fWc(t,k),Sc(t) ) , then the local client learner takes the fresh loss func-
tion and update Wc(t, k + 1) = Wc(t, k) − ηlocal · ∇WcL ( fWc(t,k),Sc(t) ) . We refer our readers to Gao et 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 are induced by multiple local updates on the client side and the updates on both local and global sides. Specifically, local updates are not the standard gradient as the centralized adversarial training when K ≥ 2. We used −∆U(t) in substitution of the real gradient of U to update the value of U(t). This brings in challenges to 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 in 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 in the proof of Theorem E.3.

heading: C.3 EXISTENCE OF ROBUST NETWORK NEAR INITIALIZATION
text: In Section F we show that there exists a global network fU∗ whose weight is close to the initial value U(0) and the worst-case global robust loss LA∗(fU∗) is sufficiently small. We show that the required width m is poly(d, (NJ/ )1/γ).
Suppose we are given a ρ-bounded adversary. For a globally γ-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 f∗(x̃c,j) ≈ yc,j for all data point (xc,j , yc,j) and perturbation inputs x̃c,j ∈ B2(xc,j , ρ). Then, we state Lemma F.2 which shows the existence of a pseudo-network gU∗ that approximates f∗ well. Finally, by using Theorem D.2 we show that fU∗ approximates gU∗ well. By combining these results, we we finish the proof of Theorem F.3.

heading: D REAL APPROXIMATES PSEUDO
text: To make additional remark to proof sketch in Section 5, in this section, we state a tool that will be used in our proof that is related to our definition of pseudo-network. First, we recall the definition of pseudo-network. Definition D.1 (Pseudo-network). Given weights U ∈ Rd×m, a ∈ Rm and b ∈ Rm, the global neural network function fU : Rd → R is defined as
fU (x) := m∑ r=1 ar · σ(〈Ur, x〉+ br).
Given this fU (x), we define the corresponding pseudo-network function gU : Rd → R as
gU (x) := m∑ r=1 ar · 〈Ur(t)− Ur(0), x〉 · 1{〈Ur(0), x〉+ br ≥ 0}.
From the definition we can know that pseudo-network can be seen as a linear approximation of the two layer ReLU network we study near initialization. Next, we cite a 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 in Zhang et al. (2020b)). Let R ≥ 1. For all m ≥ poly(d), with probability at least 1− exp(−Ω(m1/3)) over the choice of a(0), U(0), b(0), for all U ∈ Rd×m such that ‖U − U(0)‖2,∞ ≤ R/m2/3,
sup x∈X |fU (x)− gU (x)| ≤ O(R2/m1/6).

heading: E CONVERGENCE

heading: E.1 DEFINITIONS AND NOTATIONS
text: In Section E, we follow the notations used in Definition D.1. Since we are dealing with pseudonetwork, we first introduce some additional definitions and notations regarding gradient. Definition E.1 (Gradient). For a local real network fWc(t,k), we denote its gradient by
∇(fc, t, k) :=∇WcL(fWc(t,k),Sc(t)). If the corresponding pseudo-network is gWc(t,k), then we define the pseudo-network gradient as
∇(gc, t, k) :=∇WcL(gWc(t,k),Sc(t)).
Now we consider the global matrix. For convenience we write ∇(f, t) := ∇UL(fU(t),S(t)) and ∇(g, t) := ∇UL(gU(t),S(t)). We define the FL gradient as ∇̃(f, t) := − 1N∆U(t).
Definition E.2 (Distance). For U∗ ∈ Rd×m such that ‖U∗ − Ũ‖2,∞ ≤ R/m3/4, we define the following distance for simplicity:
Dmax := max t∈[T ]
‖U(t)− Ũ‖2,∞
DU∗ := ‖U∗ − Ũ‖2,∞
We have DU∗ = O(R/m3/4) and ‖U(t)− U∗‖2,∞ ≤ Dmax +DU∗ by using triangle inequality.

heading: E.2 CONVERGENCE RESULT
text: The goal of this section is to prove Theorem E.3. Theorem E.3 (Convergence result, formal version of Theorem 5.6). For all ∈ (0, 1), for all R ≥ 1, there exists an M = poly(n,R, 1/ ), such that for every m ≥ M , for every K ≥ 1, for every T ≥ poly(R/ ), with probability at least 1 − exp(−Ω(m1/3)) over the randomness of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, if we run Algorithm 2 with setting
ηglobal = 1/ poly(NJ,R, 1/ ) and ηlocal = 1/K,
then for every U∗ such that ‖U∗ − U(0)‖2,∞ ≤ R/m3/4, the output weights (U(t))Tt=1 satisfy
1
T T∑ t=1 LA ( fU(t) ) ≤ LA∗ (fU∗) + .
Proof. We set our parameters as follows: M = Ω ( max { (NJ)8, ( R )12 })
ηglobal = O( Nm1/3 · poly(R/ ) )
ηlocal = 1/K
Since the loss function is 1-Lipschitz, we can first bound the norm of real net gradient:
‖∇r(fc, t, k)‖2 ≤ |ar| · ( 1 J J∑ j=1 σ′(〈Wc,r(t, k), xc,j〉+ br) · ‖x̃c,j‖2 ) ≤ |ar| ≤ 1 m1/3 . (6)
Now we consider the pseudo-net gradient. The loss L(gU ,S(t)) is convex in U due to the fact that g is linear with U . Then we have
L(gU(t),S(t))− L(gU∗ ,S(t)) ≤ 〈∇UL(gU(t),S(t)), U(t)− U∗〉
= 〈∇̃(f, t), U(t)− U∗〉+ 〈∇(f, t)− ∇̃(f, t), U(t)− U∗〉+ 〈∇(g, t)−∇(f, t), U(t)− U∗〉 ≤ α(t) + β(t) + γ(t)
where the last step follows from
α(t) := 〈∇̃(f, t), U(t)− U∗〉, β(t) := ‖∇(f, t)− ∇̃(f, t)‖2,1 · ‖U(t)− U∗‖2,∞, γ(t) := ‖∇(g, t)−∇(f, t)‖2,1 · ‖U(t)− U∗‖2,∞.
Note that the FL gradient ∇̃(f, t) = − 1N∆U(t) is the direction moved by center, in contrast,∇(f, t) is the true gradient of function f . We deal with these three terms separately. As for α(t), we have
‖U(t+ 1)− U∗‖2F = ‖U(t) + ηglobal∆U(t)− U∗‖2F = ‖U(t)− U∗‖2F − 2Nηglobalα(t) + η2global‖∆U(t)‖2F
and by rearranging we get
α(t) = ηglobal
2N ‖∆U(t)‖2F +
1
2Nηglobal · (‖U(t)− U∗‖2F − ‖U(t+ 1)− U∗‖2F ).
Next, we need to upper bound ‖∆U(t)‖2F ,
‖∆U(t)‖2F = ‖ ηlocal N N∑ c=1 K−1∑ k=0 ∇(fc, t, k)‖2F
≤ ηlocal N N∑ c=1 K−1∑ k=0 m∑ r=1 ‖∇r(fc, t, k)‖22
= ηlocalKm 1/3
= m1/3. (7) where the last step follows from Kηlocal = 1. Then we do summation over t and have
T∑ t=1 α(t) = ηglobal 2N T∑ t=1 ‖∆U(t)‖2F + 1 2Nηglobal · T∑ t=1 (‖U(t)− U∗‖2F − ‖U(t+ 1)− U∗‖2F )
= ηglobal
2N T∑ t=1 ‖∆U(t)‖2F + 1 2Nηglobal · (‖U(1)− U∗‖2F − ‖U(T + 1)− U∗‖2F )
≤ ηglobal 2N T∑ t=1 ‖∆U(t)‖2F + 1 2Nηglobal · ‖U(1)− U∗‖2F
. ηglobal N Tm1/3 + 1 Nηglobal mD2U∗
where the last step follows from Eq. (7) and ‖Ũ − U∗‖2F ≤ m · ‖Ũ − U∗‖22,∞ = mD2U∗ .
As for β(t), we apply Lemma E.4 and also triangle inequality and have
β(t) = ‖∇(f, t)− ∇̃(f, t)‖2,1 · ‖U(t)− U∗‖2,∞ .m2/3 · ‖U(t)− U∗‖2,∞ .m2/3 · (‖U(t)− Ũ‖2,∞ +DU∗).
By using Eq. (6) we bound the size of ‖U(t)− Ũ‖2,∞:
‖U(t)− Ũ‖2,∞ ≤ ηglobal t∑
τ=1
‖∆U(τ)‖2,∞
= ηglobal t∑ τ=1 ‖ηlocal N N∑ c=1 K−1∑ k=0 ∇(fc, t, k)‖2,∞
≤ ηglobalηlocal N t∑ τ=1 N∑ c=1 K−1∑ k=0 ‖∇(fc, t, k)‖2,∞ ≤ ηglobalηlocaltKm−1/3
and have
β(t) . ηglobalηlocaltKm 1/3 +m2/3DU∗ .
Then we do summation over t and have
T∑ t=1 β(t) . T∑ t=1 (ηglobalηlocaltKm 1/3 +m2/3DU∗)
. ηglobalηlocalT 2Km1/3 +m2/3TDU∗
. ηglobalT 2m1/3 +m2/3TDU∗ .
As for γ(t), we apply Lemma E.5 and have
γ(t) = ‖∇(g, t)−∇(f, t)‖2,1 · ‖U(t)− U∗‖2,∞ . NJm13/24 · (‖U(t)− Ũ‖2,∞ +DU∗).
Since ‖U(t)− Ũ‖2,∞ ≤ ηglobalηlocaltKm−1/3, we have
γ(t) . ηglobalηlocaltKNJm 5/24 +NJm13/24DU∗ .
Then we do summation over t and have
T∑ t=1 γ(t) . T∑ t=1 ( ηglobalηlocaltKNJm 5/24 +NJm13/24DU∗ )
. ηglobalηlocalT 2KNJm5/24 +NJm13/24TDU∗
. ηglobalT 2NJm5/24 +NJm13/24TDU∗ .
Next we put it altogether. Note that DU∗ = O( Rm3/4 ), thus we obtain T∑ t=1 L(gU(t),S(t))− T∑ t=1 L(gU∗ ,S(t))
≤ T∑ t=1 α(t) + T∑ t=1 β(t) + T∑ t=1 γ(t)
. ηglobal N Tm1/3 + 1 Nηglobal mD2U∗ + ηglobalT 2m1/3
+m2/3TDU∗ + ηglobalT 2NJm5/24 +NJm13/24TDU∗
. ηglobal N Tm1/3 + 1 Nηglobal R2m−1/2 + ηglobalT 2m1/3
+RTm−1/12 + ηglobalT 2NJm5/24 +NJm−5/24RT.
We then have
1
T T∑ t=1 L(gU(t),S(t))− 1 T T∑ t=1 L(gU∗ ,S(t))
. ηglobal N m1/3 + 1 NηglobalT R2m−1/2 + ηglobalTm 1/3 +Rm−1/12
+ ηglobalTNJm 5/24 +NJm−5/24R.
. 1
NηglobalT R2m−1/2 + ηglobalTm 1/3 +Rm−1/12 + ηglobalTNJm 5/24 +NJm−5/24R (8)
≤ O( ).
From Theorem D.2 we know sup x∈X |fU (x)− gU (x)| ≤ O(R2/m1/6) = O( )
and thus, we get
1
T T∑ t=1 L(fU(t),S(t))− 1 T T∑ t=1 L(fU∗ ,S(t)) ≤ c · (9)
where c > 0 is a constant. From the definition of A∗ we have L(fU∗ , S(t)) ≤ LA∗(fU∗). From the definition of loss we have L(fU(t),S(t)) = LA(fU(t)). Moreover, since Eq. (9) holds for all > 0, we can replace c with . Thus we prove that for ∀ > 0,
1
T T∑ t=1 LA(fU(t)) ≤ LA∗(fU∗) + .

heading: E.3 APPROXIMATES REAL GLOBAL GRADIENT
text: 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 1 − exp(−Ω(m1/3)) over the randomness of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, for all iterations t such that ‖U(t)− U(0)‖2,∞ ≤ O(m−15/24), the following holds:
‖∇(f, t)− ∇̃(f, t)‖2,1 ≤ O(m2/3).
Proof. Notice that∇(f, t) = ∇UL(fU(t),S(t)) and
∇̃(f, t) = − 1 N ∆U(t) = − 1 N N∑ c=1 ∆Uc(t) = ηlocal N N∑ c=1 K−1∑ k=0 ∇(fc, t, k).
So we have ‖∇(f, t)− ∇̃(f, t)‖2,1 = m∑ r=1 ‖∇r(f, t)− ∇̃r(f, t)‖2
= 1
N m∑ r=1 ‖N · ∇r(f, t)− ηlocal N∑ c=1 K−1∑ k=0 ∇r(fc, t, k)‖2
≤ ηlocal N m∑ r=1 K−1∑ k=0 ‖N · ∇r(f, t) Kηlocal − N∑ c=1 ∇r(fc, t, k)‖2
= 1
NK m∑ r=1 K−1∑ k=0 ‖N · ∇r(f, t)− N∑ c=1 ∇r(fc, t, k)‖2
where the last step follows from the assumption that ηlocal = 1K . As for ‖N · ∇r(f, t)− ∑N c=1∇r(fc, t, k)‖2, we have
‖N · ∇r(f, t)− N∑ c=1 ∇r(fc, t, k)‖2
≤ |ar| · ∣∣∣( N NJ N∑ c=1 J∑ j=1 1{〈Ur(t), xc,j〉+ br ≥ 0}
− 1 J N∑ c=1 J∑ j=1 1{〈Wc,r(t, k), xc,j〉+ br ≥ 0} ) · ‖xc,j‖2 ∣∣∣ ≤ 1 m1/3 · 1 J N∑ c=1 J∑ j=1 |1{〈Ur(t), xc,j〉+ br ≥ 0} − 1{〈Wc,r(t, k), xc,j〉+ br ≥ 0}|
≤ N m1/3 .
Then we do summation and have
‖∇(f, t)− ∇̃(f, t)‖2,1 ≤ 1
NK m∑ r=1 K−1∑ k=0 ‖N · ∇r(f, t)− N∑ c=1 ∇r(fc, t, k)‖2
≤ 1 NK m∑ r=1 K−1∑ k=0 N m1/3
= m2/3.
Thus we finish the proof.

heading: E.4 APPROXIMATES PSEUDO GLOBAL GRADIENT
text: 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(−Ω(m1/3)) over the randomness of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, for all iterations t such that ‖U(t)− U(0)‖2,∞ ≤ O(m−15/24), the following holds:
‖∇(g, t)−∇(f, t)‖2,1 ≤ O(NJm13/24).
Proof. Notice that ∇(g, t) = ∇UL(gU(t),S(t)) and ∇(f, t) = ∇UL(fU(t),S(t)). By Claim E.6, with the given probability we have
m∑ r=1 1{∇r(g, t) 6= ∇r(f, t)} ≤ O(NJm7/8).
For indices r ∈ [m] such that ∇r(g, t) 6= ∇r(f, t), the following holds: ‖∇r(g, t)−∇r(f, t)‖2 = ‖∇U,rL(gU(t), S(t))−∇U,rL(fU(t), S(t))‖2
≤ |ar| · 1 NJ · N∑ c=1 J∑ j=1 ‖xc,j‖2 · ∣∣1{〈Ũr, xc,j〉+ br ≥ 0}
− 1{〈Ur, xc,j〉+ br ≥ 0} ∣∣
≤ 1 m1/3 · 1 NJ · N∑ c=1 J∑ j=1 ∣∣1{〈Ũr, xc,j〉+ br ≥ 0} − 1{〈Ur, xc,j〉+ br ≥ 0}∣∣ ≤ 1 m1/3 .
where the first step is definition, the second step follows that the loss function is 1-Lipschitz, the third step follows from |ar| ≤ 1m1/3 and ‖xc,j‖2 = 1, the last step follows from the bound of the indicator function. Thus, we do the conclusion:
‖∇(g, t)−∇(f, t)‖2,1
= m∑ r=1 ‖∇r(g, t)−∇r(f, t)‖2 · 1{∇r(g, t) 6= ∇r(f, t)}
≤ 1 m1/3 m∑ r=1 1{∇r(g, t) 6= ∇r(f, t)}
≤ 1 m1/3 ·O(NJm7/8)
= O(NJm13/24)
and finish the proof.

heading: E.5 BOUNDING AUXILIARY
text: Claim E.6 (Bounding auxiliary). With probability at least 1− exp(−Ω(m1/3)) over the initialization, we have
m∑ r=1 1{∇r(g, t) 6= ∇r(f, t)} ≤ O(NJm7/8).
Proof. For r ∈ [m], let Ir := 1{∇r(g, t) 6= ∇r(f, t)}. By Claim A.6 we know that for each xc,j we have
Pr[|〈W̃c,r, xc,j〉+ br| ≤ m−15/24] ≤ O(m−1/8). By putting a union bound over c and j, we get
Pr [ ∃c ∈ [N ], j ∈ [J ], |〈W̃c,r, xc,j〉+ br| ≤ m−15/24 ] ≤ O(NJm−1/8).
Since
Pr[Ir = 1] ≤ Pr[∃c ∈ [N ], j ∈ [J ], |〈W̃c,r, xc,j〉+ br| ≤ m−15/24], we have
Pr[Ir = 1] ≤ O(NJm−1/8). By applying concentration inequality on Ir (independent Bernoulli) for r ∈ [m], we have that with probability at least 1− exp(−Ω(NJm7/8)) > 1− exp(−Ω(m1/3)), the following holds:
m∑ r=1 Ir ≤ O(NJm7/8).
Thus we finish the proof.

heading: E.6 FURTHER DISCUSSION
text: Note that in the proof of Theorem E.3 we set the hidden layer’s width m to be greater than O( −12), which seems impractical in reality: if we choose our convergence accuracy to be 10−2, the width will become 1024 which is impossible to achieve.
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 O((R/ )c2) where c2 is some constant between −3 and −4. To be specific, we observe from Eq. (8) that the "−12" term comes from 2 3− 3 4 = − 1 12 , where 2 3 appears in Lemma E.4 and 3 4 appears in the assumption thatDU∗ ≤ R/m 3/4 in Definition E.2. As for our observations, the 23 term is hard to improve. On the other hand, we can actually adjust the value of DU∗ as long as we ensure
DU∗ ≤ R/mc3
for some constant c3 ∈ (0, 1). When we let c3 → 1, the final result will achieve
O(( R )3)
which is much more feasible in reality.
As the first work and the first step towards understanding the convergence of federated adversarial learning, the priority of our work is not achieving the tightest bounds. Instead, our main goal is to show the convergence of a general federated adversarial learning framework. Nevertheless, we will improve the bound in the final version.

heading: F EXISTENCE
text: In this section we prove the existence of U∗ that is close to U(0) and makes LA∗(fU∗) close to zero.

heading: F.1 TOOLS FROM PREVIOUS WORK
text: 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 ‖xc1,j1 − xc2,j2‖2 ≥ δ holds for each pair of two different data points xc1,j1 , xc2,j2 . Let D = 24γ
−1 ln(48NJ/ ), then there exists a polynomial q : R → R with degree at most D, size of coefficients at most O(γ−126D), such that for all c0 ∈ [N ], j0 ∈ [J ] and x̃c0,j0 ∈ B2(xc0,j0 , ρ),∣∣∣∣∣∣ N∑ c=1 J∑ j=1 yc,j · q(〈xc,j , x̃c0,j0〉)− yc0,j0
∣∣∣∣∣∣ ≤ 3 . We let f∗(x) := ∑N c=1 ∑J j=1 yc,j · q(〈xc,j , x〉) and have |f∗(x̃c0,j0)− yc0,j0 | ≤ /3.
Lemma F.2 (Lemma 6.5 from Zhang et al. (2020b)). For all ∈ (0, 1), there exist M = poly(d, (NJ/ )1/γ) and R = poly((NJ/ )1/γ) such that for m ≥ M , with probability at least 1 − exp(−Ω( √ m/NJ)) over the choice of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, there exists a U∗ ∈ Rd×m that satisfies ‖U∗ − U(0)‖2,∞ ≤ R/m2/3 and
sup x∈X |gU∗(x)− f∗(x)| ≤ /3.

heading: F.2 EXISTENCE RESULT
text: The goal of this section is to prove Theorem F.3 which is the existence result.
Theorem F.3 (Existence, formal version of Theorem 5.2). For all ∈ (0, 1), there exist
M0 = poly(d, (NJ/ ) 1/γ) and R = poly((NJ/ )1/γ)
such that for every m ≥M0, with probability at least 1− exp(−Ω(m1/3)) over the randomness of a(0) ∈ Rm, U(0) ∈ Rd×m, b(0) ∈ Rm, there exists U∗ ∈ Rd×m that satisfies ‖U∗ − U(0)‖2,∞ ≤ R/m2/3 and
LA∗(fU∗) ≤ .
Proof. From Lemma F.1 we obtain the function f∗. From Lemma F.2 we know the existence of M0 = poly(d, (NJ/ )
1/γ) and also R = poly((NJ/ )1/γ). By combining these two results with Theorem D.2, we have that for all m ≥ poly(d, (NJ/ )1/γ), with probability at least 1 − exp(−Ω( √ m/NJ))−exp(−Ω(m1/3)), there exists aU∗ ∈ Rd×m that satisfies ‖U∗−U(0)‖2,∞ ≤ R/m2/3 and also the following properties:
• ∀x ∈ X , |gU∗(x)− f∗(x)| ≤ /3
• ∀x ∈ X , |fU∗(x)− gU∗(x)| ≤ O(R2/m1/6)
We consider the loss function. For all c ∈ [N ], j ∈ [J ] and x̃c,j ∈ B(xc,j , ρ), we have
`(fU∗(x̃c,j), yc,j) ≤ |fU∗(x̃c,j)− yc,j | ≤ |fU∗(x̃c,j)− gU∗(x̃c,j)|+ |gU∗(x̃c,j)− f∗(x̃c,j)|+ |f∗(x̃c,j)− yc,j |
≤ O(R2/m1/6) + 3 +
3 ≤ ,
Thus, we have that LA∗(fU∗) = 1NJ ∑N c=1 ∑J j=1 max ` ( fU∗(x ∗ c,j), yc,j ) ≤ . Furthermore, since the m we consider satisfies m ≥ Ω((NJ)1/γ), the holding probability is at least
1− exp(−Ω( √ m/NJ))− exp(−Ω(m1/3)) = 1− exp(−Ω(m1/3)).
Thus, we finish the proof of this theorem.

Review summaries:
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.    --post rebuttal--  I 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.  

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.  Their 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.