summaries: This paper tackles an important problem in federated adversarial training: robustness accuracy significantly drops at the later stage of training. The authors first raise their assumption for the cause of this phenomenon: Adversarial training amplifies the heterogeneity of data distributions across different clients, and overfitted local robustness can not well generalized to other clients. Based on this assumption, the authors proposed \alpha-weighted federated adversarial training, which essentially up-weights the model trained on benign distributions and down-weights those on harsh distributions when averaging them up at the cloud center. Results show the proposed method outperforms previous state-of-the-arts under different adversarial training and federated learning settings.

summaries: This work studied the limitation of conventional Federated Adversarial Training approach, and proposed an \alpha-weighted relaxation for Adversarial Training in the federated learning setting. Then it proposed a novel \alpha-Weighted Federated Adversarial Training for minimizing a lower bound of the inner-maximization in Federated Adversarial Training. The performance of the proposed \alpha-Weighted Federated Adversarial Training were validated for both IID and Non-IID federated learning settings.

summaries: This paper introduces the alpha Weighted Federated Adversarial Training algorithm. The key of the idea is that in the aggregate step, the center prefers the local machine that yields smaller lost. Some theoretical results are delivered with numerical experiments. The paper claims that the alpha-weighted mechanism is tailored for the inner-maximization of Federated Adversarial Training, which is the rationale of the whole work.

summaries: The authors explore the adversarial robustness of federated learning. They claim that the inner-maximization optimization of AT can exacerbate the data heterogeneity among local clients. They propose an algorithm, $\alpha$--WFAT, which relaxes the inner-maximization of Adversarial Training into a lower bound friendly to Federated Learning.. The authors also experimentally establish that federated learning models are most susceptible to attacks when clients are using non-IID training sets. The experiments are performed over the CIFAR-10 , SVHN and CIFAR-100datasets.

abstractText: Federated Adversarial Training (FAT) helps us address the data privacy and governance issues, meanwhile maintains the model robustness to the adversarial attack. However, the inner-maximization optimization of Adversarial Training can exacerbate the data heterogeneity among local clients, which triggers the pain points of Federated Learning. This makes that the straightforward combination of two paradigms shows the performance deterioration as observed in previous works. In this paper, we introduce an α-Weighted Federated Adversarial Training (αWFAT) method to overcome this problem, which relaxes the inner-maximization of Adversarial Training into a lower bound friendly to Federated Learning. We present the theoretical analysis about this α-weighted mechanism and its effect on the convergence of FAT. Empirically, the extensive experiments are conducted to comprehensively understand the characteristics of α-WFAT, and the results on three benchmark datasets demonstrate α-WFAT significantly outperforms FAT under different adversarial learning methods and federated optimization methods.

authors:
Zeyuan Allen-Zhu
Yuanzhi Li

title: Towards understanding ensemble, knowledge distillation and self-distillation in deep learning

venue: arXiv preprint arXiv:2012.09816,

authors:
Nicholas Carlini
David A. Wagner

title: Towards evaluating the robustness of neural networks

venue: In Symposium on Security and Privacy (SP),

authors:
Tianlong Chen
Sijia Liu
Shiyu Chang
Yu Cheng
Lisa Amini
Zhangyang Wang

title: Adversarial robustness: From self-supervised pre-training to fine-tuning

authors:
Tianlong Chen
Zhenyu Zhang
Sijia Liu
Shiyu Chang
Zhangyang Wang

title: Robust overfitting may be mitigated by properly learned smoothening

venue: In ICLR,

authors:
Ruize Gao
Feng Liu
Jingfeng Zhang
Bo Han
Tongliang Liu
Gang Niu
Masashi Sugiyama

title: Maximum mean discrepancy test is aware of adversarial attacks

venue: In ICML,

authors:
Ian J. Goodfellow
Jonathon Shlens
Christian Szegedy

title: Explaining and harnessing adversarial examples

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Junyuan Hong
Haotao Wang
Zhangyang Wang
Jiayu Zhou

title: Federated robustness propagation: Sharing adversarial robustness in federated learning

venue: arXiv preprint arXiv:2106.10196,

authors:
Ziyu Jiang
Tianlong Chen
Ting Chen
Zhangyang Wang

title: Robust pre-training by adversarial contrastive learning

venue: In NeurIPS,

authors:
Peter Kairouz
H Brendan McMahan
Brendan Avent
Aurélien Bellet
Mehdi Bennis
Arjun Nitin Bhagoji
Kallista Bonawitz
Zachary Charles
Graham Cormode
Rachel Cummings

title: Advances and open problems in federated learning

venue: arXiv preprint arXiv:1912.04977,

authors:
Sai Praneeth Karimireddy
Satyen Kale
Mehryar Mohri
Sashank Reddi
Sebastian Stich
Ananda Theertha Suresh

title: Scaffold: Stochastic controlled averaging for federated learning

authors:
Ron Kohavi
David H Wolpert

title: Bias plus variance decomposition for zero-one loss functions

title: Learning multiple layers of features from tiny images

venue: In arXiv,

authors:
Alexey Kurakin
Ian Goodfellow
Samy Bengio

title: Adversarial machine learning at scale

venue: arXiv preprint arXiv:1611.01236,

authors:
Qinbin Li
Bingsheng He
Dawn Song

title: Model-contrastive federated learning

venue: In CVPR,

authors:
Tian Li
Anit Kumar Sahu
Manzil Zaheer
Maziar Sanjabi
Ameet Talwalkar
Virginia Smith

title: Federated optimization in heterogeneous networks

venue: arXiv preprint arXiv:1812.06127,

authors:
Xiang Li
Kaixuan Huang
Wenhao Yang
Shusen Wang
Zhihua Zhang

title: On the convergence of fedavg on non-iid data

authors:
Xiaoxiao Li
Meirui Jiang
Xiaofei Zhang
Michael Kamp
Qi Dou

title: Fedbn: Federated learning on non-iid features via local batch normalization

venue: arXiv preprint arXiv:2102.07623,

authors:
Aleksander Madry
Aleksandar Makelov
Ludwig Schmidt
Dimitris Tsipras
Adrian Vladu

title: Towards deep learning models resistant to adversarial attacks

authors:
Brendan McMahan
Eider Moore
Daniel Ramage
Seth Hampson
Blaise Aguera y Arcas

title: Communication-efficient learning of deep networks from decentralized data

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y Ng

title: Reading digits in natural images with unsupervised feature learning

venue: In NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning,

authors:
Nicolas Papernot
Patrick McDaniel
Xi Wu
Somesh Jha
Ananthram Swami

title: Distillation as a defense to adversarial perturbations against deep neural networks

venue: IEEE symposium on security and privacy (SP),

authors:
Amirhossein Reisizadeh
Farzan Farnia
Ramtin Pedarsani
Ali Jadbabaie

title: Robust federated learning: The case of affine distribution shifts

authors:
Devansh Shah
Parijat Dube
Supriyo Chakraborty
Ashish Verma

title: Adversarial training in communication constrained federated learning

venue: arXiv preprint arXiv:2103.01319,

authors:
Aman Sinha
Hongseok Namkoong
John Duchi

title: Certifying some distributional robustness with principled adversarial training

authors:
Haotao Wang
Tianlong Chen
Shupeng Gui
Ting-Kuei Hu
Ji Liu
Zhangyang Wang

title: Oncefor-all adversarial training: In-situ tradeoff between robustness and accuracy for free

venue: NeurIPS,

authors:
Jianyu Wang
Qinghua Liu
Hao Liang
Gauri Joshi
H Vincent Poor

title: Tackling the objective inconsistency problem in heterogeneous federated optimization

authors:
Yisen Wang
Xingjun Ma
James Bailey
Jinfeng Yi
Bowen Zhou
Quanquan Gu

title: On the convergence and robustness of adversarial training

authors:
Yisen Wang
Difan Zou
Jinfeng Yi
James Bailey
Xingjun Ma
Quanquan Gu

title: Improving adversarial robustness requires revisiting misclassified examples

authors:
Dongxian Wu
Shu-Tao Xia
Yisen Wang

title: Adversarial weight perturbation helps robust generalization

authors:
Hongyang Zhang
Yaodong Yu
Jiantao Jiao
Eric P. Xing
Laurent El Ghaoui
Michael I. Jordan

title: Theoretically principled trade-off between robustness and accuracy

authors:
Jingfeng Zhang
Xilie Xu
Bo Han
Gang Niu
Lizhen Cui
Masashi Sugiyama
Mohan Kankanhalli

title: Attacks which do not kill training make adversarial learning stronger

authors:
Yuchen Zhang
John C Duchi
Martin J Wainwright

title: Communication-efficient algorithms for statistical optimization

venue: The Journal of Machine Learning Research,

authors:
Giulio Zizzo
Ambrish Rawat
Mathieu Sinn
Beat Buesser

title: Fat: Federated adversarial training

venue: arXiv preprint arXiv:2012.01791,

venue: Let c : X ×X → R+ ∪ {∞},

heading: 1 INTRODUCTION

text:
To handle the data privacy and governance issues, Federated Learning (McMahan et al., 2017) as one promising paradigm of distributed training has drawn the increasing attention (McMahan et al., 2017; Kairouz et al., 2019). However, training locally in Federated Learning also introduces the vulnerability from the adversarial attacks (Goodfellow et al., 2015; Kurakin et al., 2016), which drives us to consider the model robustness in this framework. Thus, recent advances (Kairouz et al., 2019) explore to apply the Adversarial Training methods (Madry et al., 2018) into Federated Learning.
However, the straightforward combination of Adversarial Training and Federated Learning presents some potential challenges due to the communication cost and the hardware requirement. For example, Shah et al. (2021) pointed out that the communication in Federated Learning may be a constraint to Adversarial Training, and proposed a dynamic schedule on the local training epochs to achieve the expected robustness in a short communication budget. Hong et al. (2021) considered the hardware constraint where some clients are not able to participate Adversarial Training, and they proposed a federated robust propagation method to share the adversarial robustness among the clients. Although these previous works indeed addressed some realistic problems, one critical issue in the way is the performance deterioration in the combination of two paradigms as observed in (Zizzo et al., 2020).
As shown in the left panel of Figure 1, one typical phenomenon in Federated Adversarial Training (FAT) is the robust accuracy of FAT (Zizzo et al., 2020) based on FedAvg (McMahan et al., 2017) will decrease significantly at the later stage of learning compared with the centralized Adversarial Training (Madry et al., 2018) that does not. Actually, it exists in many variants of Federated Learning methods (Shah et al., 2021) under different communication rounds and different local training epochs. However, it is still lack of the sufficient algorithmic breakthrough to overcome this issue, since almost all previous works (Zizzo et al., 2020; Shah et al., 2021; Hong et al., 2021) consistently apply the conventional update framework of Federated Learning with Adversarial Training.
We dive into this phenomenon and attribute it to the inner-maximization of Adversarial Training. Compared with the centralized Adversarial Training (Madry et al., 2018), the training data of FAT is distributed to each client, which leads to the Adversarial Training in each client unaware of the data in the others. Therefore, the adversarial examples generated by the inner-maximization of Adversarial Training tend to be highly biased to each local distribution, yielding the radical optimization to pursuit the model robustness (as shown in Figure 2, it has a severe local bias to the global optimum). In
short, the inner-maximization of Adversarial Training exacerbates the data heterogeneity among local clients, which actually triggers the pain points of Federated Learning that are exploring urgently.
To handle this problem, we propose a new learning framework based on a simple but effective reweighting mechanism, namely, α-Weighted Federated Adversarial Training (α-WFAT). Concretely, we relax the objective of the inner-maximization in Adversarial Training into a lower bound by an αweighting mechanism (as Eq. (3) in Section 4.2). Similar to the bias-variance trade-off (Kohavi et al., 1996), we introduce the small bias to the original objective via a low-bound relaxation, facilitating a friendly optimization in the combination of Adversarial Training and Federated Learning. This constructs a conservative optimization for Adversarial Training that weights different population based on their adversarial losses. Then, the harsh heterogeneous update can be down-weighted with this flexible weighting mechanism, and the convergence could be accelerated at the same time. Applying the similar idea to FAT, we propose α-WFAT that emphasizes the robust clients more compared with other non-robust clients to alleviate the heterogeneous bias caused by the local adversarial generation. The right panel of Figure 1 gives a simple comparison between α-WFAT and FAT. Empirically, we conducted extensive experiments to provide a comprehensive understanding of the proposed α-WFAT, and the results of α-WFAT in the context of different adversarial learning methods and federated optimization methods demonstrate its superiority to improve the model performance.
Main Contributions
• We derive an α-weighted relaxation for Adversarial Training to relax the inner-maximization by a lower bound, which builds a mediating function to alleviate the potential radical optimization in its straightforward combination with Federated Learning (in Section 4.2).
• We propose a new learning framework, i.e., α-Weighted Federated Adversarial Training (α-WFAT), to realize the relaxation of inner-maximization in FAT, which is simple and compatible with various Federated Learning or Adversarial Training methods (in Section 4.3).
• We conduct extensive experiments to comprehensively understand the characteristics of the α-WFAT, and confirm its effectiveness on improving the model performance for both IID and Non-IID settings in the context of several federated optimization methods (in Section 5).

heading: 2 RELATED WORK

text:
Federated Learning The representative work in Federated Learning is FedAvg (McMahan et al., 2017), which has been proved effectiveness during the distributed training to maintain the data privacy. To further address the heterogeneous issues, several optimization approaches have been proposed e.g., FedProx (Li et al., 2018), FedNova (Wang et al., 2020b) and Scaffold (Karimireddy et al., 2020). FedProx introduced a proximal term for FedAvg to constrain the model drift cause by heterogeneity; FedNova proposed a general framework that eliminated the objective inconsistency and preserved the fast convergence; Scaffold utilized the control variates to reduce the gradient variance in the
local updates and accelerate the convergence. MOON (Li et al., 2021a) alleviated the heterogeneity by maximizing the agreement between the representation of the local model and that of the global model, which helps correct the local training of individual parties. Reisizadeh et al. (2020) developed a robust federated learning algorithm to against distribution shifts in clients samples. Our α-WFAT introduces the relaxation into federated adversarial training, which is orthogonal to and compatible with the previous optimization methods.
Adversarial Training As one of the defensive methods (Papernot et al., 2016; Gao et al., 2021), Adversarial Training (Madry et al., 2018; Zhang et al., 2019; Jiang et al., 2020; Chen et al., 2021) is to improve the robustness of machine learning models. The classical AT (Madry et al., 2018) is built upon on a min-max formula to optimize the worst case, e.g., the adversarial example near the natural example (Goodfellow et al., 2015). Zhang et al. (2019) decomposed the prediction error for adversarial examples as the sum of the natural error and the boundary error, and proposed TRADES to balance the classification performance between the natural and adversarial examples. Wang et al. (2020c) further explored the influence of the misclassified examples on the robustness, and proposed MART that emphasizes the minimization of the misclassified examples to boost the AT. Zhang et al. (2020) investigated the “benign adversarial examples” in AT and further improve the natural performance of robust model. In this work, our α-WFAT framework leverages the client-level measure to alleviate the heterogeneous issue in the straightforward combination of adversarial training and federated learning. It is compatible to further incorporate those centralized adversarial training methods to improve the model performance.
Federated Adversarial Training. Recently, several works have made the exploration on the Adversarial Training in the context of Federated Learning, which consider the data privacy and the robustness in one framework. To our best knowledge, Zizzo et al. (2020) take the first trial to study the feasibility of extending Federated Learning (McMahan et al., 2017) with the standard AT on both IID and Non-IID settings. Empirically, they found that there was a large performance gap existing between the distributed and the centralized adversarial training, especially on the Non-IID data. Shah et al. (2021) designed a dynamic schedule for the local training to pursue a larger robustness under the constrained communication budget of Federated Learning. Hong et al. (2021) explored how to effectively propagate the adversarial robustness when only limited clients in Federated Learning have the sufficient computational budget to afford AT. Although previous works have investigated to solve the challenges about the constrained communication or computational budget, one critical issue that affects the performance when combined Adversarial Training with Federated Learning has received only few discussion. In this work, we consider such a basic issue (see Figure 1) in the straightforward combination of AT with Federated Learning and introduce our solution to this problem.

heading: 3 PRELIMINARY

text: In this section, we will briefly formalize the notations of Adversarial Training (Goodfellow et al., 2015; Madry et al., 2018) and Federated Learning as well as FedAvg (McMahan et al., 2017).

heading: 3.1 ADVERSARIAL TRAINING

text:
Let (X , d∞) denote the input feature space X with the infinity distance metric d∞(x, x̃) = ‖x− x̃‖∞, and B [x] = {x̃ ∈ X | d∞(x, x̃) ≤ } be the closed ball of radius > 0 centered at x in X . Dataset S = {(xn, yn)}Nn=1, where xn ∈ X and yn ∈ Y = {0, 1, ..., C − 1}. The objective function of the standard adversarial training (AT) (Madry et al., 2018) is defined as follows,
min fθ∈F
1
N N∑ n=1 max x̃n∈B [xn] `(fθ(x̃n), yn), (1)
where x̃ is the most adversarial data within the -ball centered at x, fθ(·) : X → RC is a score function, ` : RC × Y → R is a composition of a base loss `B : ∆C−1 × Y → R (e.g., the CrossEntropy loss) and an inverse link function `L : RC → ∆C−1 (e.g., the Softmax). Here, ∆C−1 is the corresponding probability simplex that yields `(fθ(·), y) = `B(`L(fθ(·)), y). For the innermaximization of Eq. (1), the multi-step projected gradient descent (PGD) (Madry et al., 2018) is usually applied to find the most adversarial samples, which are then used for the outer-minimization.

heading: 3.2 FEDERATED LEARNING

text:
Let Dk denotes a finite set of samples from the k-th client, and in each round, a set of datasets {Dk}Kk=1 from K clients are involved into the training. The objective of Federated Learning is to learn a machine learning model without any exchange of the training data between the clients and the server. The current popular strategy, namely FedAvg, is introduced by McMahan et al. (2017), where the clients collaboratively send the locally trained model weights θk to the server for the global average aggregation. Concretely, each client runs on a local copy of the global model (parameterized by θt in the t-th round) with its local data to optimize the objective like Eq. (1). Then, the server receives their updated model weights {θtk}Kk=1 of all clients and performs the following aggregation
θt+1 = 1
N K∑ k=1 Nkθ t k, (2)
where Nk denotes the number of the samples in Dk and N = ∑K k=1Nk. Then, the weights θ
t+1 for the global model will be sent back to each client for another lifecycle. After the sufficient rounds of such a periodic synchronization and aggregation, we expect the stationary point of Federated Learning will approximately approach to or have a small gap with that from the centralized counterpart.
4 α-WEIGHTED FEDERATED ADVERSARIAL TRAINING
In the following sections, we will first introduce our motivation for Federated Adversarial Training through analyzing the challenges brought by the straightforward combination. Then, we relax the inner-maximization problem of Adversarial Training as a lower bound by an α-weighted decomposition, and present the theoretical understanding of such a relaxation. Finally, we will present the α-Weighted Federated Adversarial Training and the corresponding analysis.

heading: 4.1 MOTIVATION

text:
For the general FAT (Zizzo et al., 2020), in each round, the clients will receive the latest model from the server. Then, they conduct Adversarial Training with the local data and send their optimized model parameters to the server. The server will aggregate the parameters of all clients into a global model with FedAvg or other methods in Federated Learning. However, considering the characteristics of Federated Learning and Adversarial Training, it naturally brings the following critical challenge.
The inner-maximization can enlarge the data heterogeneity in Federated Learning. In terms of the combination of adversarial training and federated learning, the key point is that such adversarial examples generated by the inner-maximization exacerbate the heterogeneity, which induces the performance deterioration under the model aggregation methods. As the Figure 2 shows, the client A with large adversarial loss might make a dominating effect on the convergence of the global model, given the current model aggregation methods treat all client models indiscriminately. Thus, it might be better to selectively weight the client models in the model aggregation.
4.2 α-WEIGHTED RELAXATION OF DECOMPOSED ADVERSARIAL TRAINING
As previous analysis, the inner-maximization of Adversarial Training is not very compatible with Federated Learning due to the exacerbation of heterogeneity when combing them together. An idea to alleviate this problem is building a mediating function that keeps the original goal but is friendly to two paradigms. In this section, we present one possible solution to this intuition, which tries to find a relaxation of the inner-maximization in Adversarial Training. Formally, we decompose the inner-maximization objective into the independent K populations that corresponds to the K clients in Federated Learning, and relaxes it into a lower bound by the α-weighted mechanism as follows,
LAT = 1
N N∑ n=1 max x̃n∈B [xn] `(f(x̃n), yn) = K∑ k=1 Nk N
( 1
Nk Nk∑ n=1 max x̃n∈B [xn] `(f(x̃kn), y k n) ) ︸ ︷︷ ︸
Lk
≥ (1 + α) K̂∑ k=1 Nφ(k) N Lφ(k) + (1− α) K∑ k=K̂+1 Nφ(k) N Lφ(k) s.t. α ∈ [0, 1), K̂ ≤ K 2 . = Lα(K̂), (3)
where φ(·) is a function which maps the index to the original population sorted by {NkN Lk} in an ascending order. The following theorems provide us more analysis about the α-weighted relaxation.
Theorem 4.1. Lα(K̂) is monotonically decreasing w.r.t. both α and K̂, i.e., Lα1(K̂) < Lα2(K̂) if α1 > α2 and Lα(K̂1) < Lα(K̂2) if K̂1 > K̂2. Specifically, Lα(K̂) recovers L of adversarial training when α achieves 0, and Lα(K̂) relaxes L to a lower bound objective by increasing K̂ and α.
We can flexibly emphasize the importance of partial populations by setting the proper hyperparameters, alleviating the evenly averaging of harsh heterogeneous updates in FedAvg (McMahan et al., 2017).
Theorem 4.2. Assume the loss function `(·, ·) in Eq. (3) satisfies the Lipschitzian smoothness condition w.r.t. the model parameter θ and the training sample x, and is λ-strongly concave for all x, and E [ ||∇Lα(K̂)−∇θ`(f(x̃), y)||22 ] ≤ δ2, where x̃ is the adversarial example. Then, after the
sufficient T -step optimization i.e., T ≥ L∆δ2 , for α-weighted relaxation of decomposed Adversarial Training with the constant stepsize √ ∆
LTσ2 in PGD, we have the following convergence property,
1
T T∑ t E [∣∣∣∣∣∣∣∣∇Lα(K̂)∣∣θt∣∣∣∣∣∣∣∣2 2 ] ≤ ( 1 + α 1 T ∑T t ξ (t) N )( 4L2θx λ + 4δ √ L∆ T ) , (4)
where L = Lθθ + LθxLxθλ defined by the Lipschitzian constraints, ∆ ≥ L α(K̂)|θ0 − infθ Lα(K̂) and ξ(t) = ∑K̂ k N (t) φ(k) − ∑K K̂+1N (t) φ(k) meaning the accumulative counting difference of the t-th step.
When α = 0, Eq.(3) recovers the original loss of Adversarial Training, and the first part in the RHS of Eq. (4) goes to 1 that recovers the convergence rate of Adversarial Training (Sinha et al., 2018). When α → 1, Eq.(3) becomes more biased, while simultaneously the straightforward benefit is that we can achieve a faster convergence in Eq. (4) if 1T ∑T t ξ (t) < 0, i.e., ( 1 + α 1 T ∑T t ξ (t) N ) < 1. Actually, this is possible when the sample number is approximately similar among all clients and the top-1 choice easily has −N < ξ(t) = N (t)φ(1) − ∑K k=2N (t) φ(k) < 0 in each optimization step. Especially, a larger α has a faster convergence in this case. Therefore, the α-weighted relaxation of decomposed Adversarial Training provides us a trade-off between maintaining the robustness from the standard robust training and achieving the faster convergence with some biased approximation by α and K̂.
4.3 α-WEIGHTED FEDERATED ADVERSARIAL TRAINING
Inspired by the previous analysis of α-weighted relaxation, we propose an α-Weighted Federated Adversarial Training to combine Adversarial Training and Federated Learning. The intuition is
Algorithm 1 α-Weighted Federated Adversarial Training (α-WFAT) Input: number of clients: K, number of communication rounds: T , number of client training epochs
per round: E, initial server’s model parameter: θ0, hyper-parameter for aggregation: α, number of enhanced clients: K̂;
Output: a globally robust model with parameter θT ; 1: for t = 0, . . . , T − 1 do 2: Clients: [ perform adversarial training] 3: for client k = 1, . . . , K do 4: θtk,Lk = AT(θtk, E) (Madry et al., 2018) 5: end for 6: Server: [ performs aggregation over weight updates] 7: Lall ← [N1N L1, N2 N L2, . . . , NK N LK ]
8: Lsorted ← Ascending_Sort(Lall) 9: ∀k, Pk ← (1 + α) · 1(NkN Lk ≤ Lsorted[K̂]) + (1− α) · 1( Nk N Lk > Lsorted[K̂]);
10: θt+1 = 1∑K k=1 PkNk ∑K k=1 PkNkθ t k; . α-weighted mechanism 11: end for
applying the α-weighted mechanism into the inner-maximization in FAT, formalized as follows,
minLα−WFAT = min fθ∈F 1∑K k PkNk K∑ k=1 PkNk
( 1
Nk Nk∑ n=1 max x̃n∈B [xn] `(fθ(x̃ k n), y k n) ) ︸ ︷︷ ︸
Lk
, (5)
where Pk = (1+α) ·1(NkN Lk ≤ Lsorted[K̂])+(1−α) ·1( Nk N Lk > Lsorted[K̂]) denotes the weight assigned to the k-th client based on the ascending sort of weighted client losses compared with the K̂-th one. We summarize the procedure of α-WFAT in Algorithm 1, which consists of multi-round iterations between the local training on the client side and the global aggregation on the server side.
Concretely, on the client side, after downloading the global model parameter from the server, each client will perform the Adversarial Training on its local data. At the same time, the client loss on the adversarial examples is also recorded, which acts as the soft-indicator of the local bias induced by the radical adversarial generation. Then, when the training steps reach to the condition, the client will upload its model parameter and the loss to the server. On the server side, after collecting the model parameters {θk}Kk=1 and the losses {Lk}Kk=1 of all clients, it will first sort the losses in an ascending order to find the top-K̂ clients. Based on that, the global model parameters will be aggregated by the α-weighted mechanism in which the model parameters of the top-K̂ clients are upweighted with (1 + α) and the remaining is downweighted by (1− α). For some atypical layers (Li et al., 2021b) e.g., BN, it is outside the scope of this paper and we keep the aggregation same as FedAvg. Note that, one interesting point in α-WFAT is the top-K̂ clients with the higher weights are not fixed, and they can be routing among all clients. In Figure 3, we trace this dynamic of α-WFAT in one experiment.
In the following, we provide the theoretical analysis of α-WFAT on the convergence in the context of Federated Learning (Li et al., 2019), which is slightly different from previous centralized counterpart. Theorem 4.3. Assume the loss function `(·, ·) in Eq. (5) is L-smooth and λ-strongly concave w.r.t. the model parameter θ, and the expected norm and the variance of the stochastic gradient in each client respectively satisfy E [ ||∇θ`(f(x̃k), yk)||22 ] ≤ ς2 and E [ ||∇θ`(f(x̃k), yk)−∇θLk||22 ] ≤ δ2k. Let κ = Lλ , γ = max{8κ,E} where E is the iteration number of the local Adversarial Training with the learning rate ηt = 2λ(γ+t) . Then, after the sufficient T -step communication rounds for α-WFAT, we have the following asymptotics to the optimal point,
E[Lα−WFAT ]− L∗ ≤ κ
γ + T − 1
( 2B
λ + λγ 2 E [ ||θ0 − θ∗||2 ]) , (6)
where L∗ is the minimum value of Lα−WFAT , θ∗ is the optimal model parameter, and
B = K∑ k
( P
(T ) k
1 + α ξ (T )
N
)2( Nk N δk )2 + 6L ( L∗ − K∑ k P (T ) k 1 + α ξ (T ) N Nk N L∗k ) + 8(E − 1)2ς2.
When α = 0, we have P (t)k = 1 and Eq.( 6) becomes the convergence rate of FedAvg on non-IID data (Li et al., 2019). Different from Theorem 4.2 that concludes in the centralized training setting, when α→ 1, the convergence is indefinite compared to the standard FAT, since the emerging terms in
B, i.e., ( P (T ) k
1+α ξ (T )
N
)2 and P (T ) k
1+α ξ (T )
N
, are acted as the scalar timing by the personalized variance bound
δ2k and the local optimum L∗k of each client. One possible case is when the optimization approaches to the optimal parameter θ∗, δ2k can be in a smaller scale relative to the scale of L∗k. In this case, the increment of the first term of B can be totally counteracted by the loss of second term of B so that in sum B becomes smaller. Then, we can have a tighter upper bound for α-WFAT in Eq.( 6) to achieve a faster convergence than FAT. The completed proof of Theorem 4.3 can refer to Appendix C and the experiments in the following section will confirm α-WFAT can reach to a more robust optimum.

heading: 5 EXPERIMENTS

text: In this section, we will provide an in-depth analysis of α-WFAT and empirically verify its efficiency compared with the current methods on a range of IID and non-IID datasets.

heading: 5.1 EXPERIMENTAL SETUP

text: Dataset. We conduct the experiments on three benchmark datasets, i.e., CIFAR-10, CIFAR100 (Krizhevsky, 2009) and SVHN (Netzer et al., 2011) for Federated Adversarial Training. For the IID scenario, we just randomly and evenly distribute the samples to each client. For the NonIID scenario, we follow McMahan et al. (2017); Shah et al. (2021) to partition the training data based on their labels. To be specific, a skew parameter s is utilized in the data partition introduced by Shah et al. (2021), which enables K clients to get a majority of the data samples from a subset of classes. We denote the set of all classes in a dataset as Y and create Yk by dividing all the class labels equally among K clients. Accordingly, we split the data across K clients that each client has (100 − (K − 1) × s)% of data for the class in Yk and s% of data in other split sets. The detailed training and evaluation settings can refer to Appendix E.

heading: 5.2 ABLATION STUDY

text:
In this part, we conduct various experiments on CIFAR-10 to visualize the characteristics of α-WFAT.
Non-AT vs. AT. In the left two panels of Figure 4, we respectively apply our α-weighted mechanism to Federated Standard Training (α-WFST) and Federated Adversarial Training (α-WFAT) under K̂ = 1. We also consider both FedAvg and FedProx in this experiment to guarantee the universality. From the curves, we can see that α-WFST has the negative effect on the natural accuracy, while α-WFAT consistently improve the robust accuracy both based on FedAvg or FedProx. This indicates our α-weighted mechanism is tailored for the inner-maximization of Federated Adversarial Training instead of the outer-minimization considered by other federated optimization methods.
Impact of α and K̂. To study the effect of hyperparameter in α-WFAT, we conduct several ablation experiments to verify the model performance. Regarding the experiments of α, we set the client
number K = 5 and K̂ = 1 to upweight/downweight the client models in each communication rounds. The right middle panel of Figure 4 shows α ∈ (0, 1/6] can significantly improve the robust accuracy and the natural accuracy, while a larger αmight be inappropriate to the natural accuracy. Regarding the choice of K̂, we specially set K = 8 in this experiment to span the range of K̂ due to the constraint K̂ <= K/2. The right panel of Figure 4 presents the accuracy of α-WFAT with increasing K̂.
According to the plot, both the natural accuracy and the robust accuracy are improved even with larger K̂, which shows the effect of K̂ on the relaxation of inner-maximization in the proposed α-WFAT. In addition, we conduct the experiments about emphasizing/deemphasizing the client with smallest adversarial loss by adjusting the α, the results (in Appendix E.1) confirmed that the relaxation introduced by our α-WFAT is needed to improve performance, and is consistent with our previous analysis.
Different AT methods. In Table 1, we validate the combination of α-weighted mechanism and different Adversarial Training methods (i.e., TRADES (Zhang et al., 2019) and MART (Wang et al., 2020c)), where we switch different local Adversarial Training methods on the client side. Through the comparison with FAT, the results show that α-WFAT can consistently improve both the natural performance and the robust performance, and is general to the state-of-the-art Adversarial Training works under Federated Learning scenarios.

heading: 5.3 PERFORMANCE EVALUATION

text:
In this section, we compare our α-WFAT with FAT on various benchmark datasets to demonstrate its effectiveness. Specifically, we validate both the non-IID and IID settings with three represenative Federated optimization methods i.e., FedAvg, FedProx and Scalffold. Besides, a centralized AT baseline is provided as the reference of the IID setting. Note that, there is no such a baseline for the non-IID setting, since the centralized case is one distribution which is incomparable and meaningless. Considering the sensitivity of data selection in Non-IID settings, we also report the results with Mean and Std values in Appendix E.2 after running experiments for multiple times.
According to Table 2 on CIFAR-10, we can find that α-WFAT significantly outperforms FAT on the Non-IID data in terms of both the natural accuracy (∼2%-6%) and the robust accuracy (∼2%-5%). For the IID data, our method acquires a similar improvement on the robust accuracy without the deterioration of the natural accuracy. The reason might be because even the data is IID, Adversarial Training can still drive the independently-initialized overparameterized network (Allen-Zhu & Li, 2020) on each client side towards at the robust overfitting of different directions, yielding the model heterogeneity. Thus, the proper relaxation to the inner-maximization makes Adversarial Training more compatible with Federated Learning. Another interesting observation is that Federated Adversarial Training shows better performance than centralized Adversarial Training in the case of the IID setting. This gain could be from the distributed training paradigm that helps Adversarial Training converge
to the more robust optimum by the divide-and-conquer mechanism. This might enlighten the more explore in Adversarial Training to improve the model robustness via Federated Learning.
On CIFAR-100 and SVHN, we can find the similar improvement in Table 2 as that of CIFAR-10 under three types of federated optimization methods. Nevertheless, α-WFAT only becomes superior in terms of the robust accuracy but comparable with FAT in terms of the natural accuracy especially on CIFAR-100. It indicates that the inner-maximization of Adversarial Training when combined with Federated Learning mainly affects the model robustness, and thus the α-weighted relaxation correspondingly helps the model converge to a more robust optimum.

heading: 6 CONCLUSION

text: In this work, we explore the performance deterioration in the straightforward combination of Adversarial Training with Federated Learning. To alleviate the potential radical optimization, we apply an α-weighted relaxation into Adversarial Training to relax the inner-maximization. Based on this α-weighted mechanism, we further propose α-Weighted Federated Adversarial Training (α-WFAT). We provide the theoretical analysis and empirical evidences to understand the proposed simple but effective method. The experimental results under different settings confirm the effectiveness of α-WFAT. Nevertheless, we only move a small step on the heterogeneous issue in the combination of two paradigms and more issues in their cross field could be further explored in the future.

heading: 7 ETHICS STATEMENT

text: This paper does not raise any ethics concerns. This study does not involve any human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, potential conflicts of interest and sponsorship, discrimination/bias/fairness concerns, privacy and security issues, legal compliance, and research integrity issues.

heading: 8 REPRODUCIBILITY STATEMENT

text: To ensure the reproducibility of experimental results, we will provide a link for an anonymous repository about the source codes of this paper in the discussion forums.

heading: A PROOF OF EQ. (3) AND THEOREM 4.1

text:
We proof the Eq. (3) and Theorem 4.1 in this section.
Recall the α-weighted relaxation for the inner-maximization objective decomposition with K independent populations as follows,
LAT = 1
N N∑ n=1 max x̃n∈B [xn] `(f(x̃n), yn) = K∑ k=1 Nk N
( 1
Nk Nk∑ n=1 max x̃n∈B [xn] `(f(x̃kn), y k n) ) ︸ ︷︷ ︸
Lk
≥ (1 + α) K̂∑ k=1 Nφ(k) N Lφ(k) + (1− α) K∑ k=K̂+1 Nφ(k) N Lφ(k) s.t. α ∈ [0, 1), K̂ ≤ K 2 . = Lα(K̂), (7)
where φ(·) is a function which maps the index to the original population group sorted by {NkN Lk} in an ascending order.
proof of Eq. (3). The deduction of the inequality in Eq. (7) can be formulated in the following. Given α ∈ [0, 1) and K̂ ≤ K2 with the population sorted by {
Nk N Lk} in an ascending order, we have∑K̂
k=1 Nφ(k) N Lφ(k) ≤ ∑K k=K̂+1 Nφ(k) N Lφ(k). Then, we have the following relationship by subtraction,
K̂∑ k=1 Nφ(k) N Lφ(k) + K∑ k=K̂+1 Nφ(k) N Lφ(k) − (1 + α) K̂∑ k=1 Nφ(k) N Lφ(k) − (1− α) K∑ k=K̂+1 Nφ(k) N Lφ(k)
= α ·  K∑ k=K̂+1 Nφ(k) N Lφ(k) − K̂∑ k=1 Nφ(k) N Lφ(k)  ≥ 0. (8)
proof of Theorem 4.1. It can be naturally proved by Eq. (8). If α1 > α2, then we have,
Lα1(K̂)− Lα2(K̂) = (1 + α1) K̂∑ k=1 Nφ(k) N Lφ(k) + (1− α1) K∑ k=K̂+1 Nφ(k) N Lφ(k)
−(1 + α2) K̂∑ k=1 Nφ(k) N Lφ(k) − (1− α2) K∑ k=K̂+1 Nφ(k) N Lφ(k) (9)
= (α1 − α2)  K̂∑ k=1 Nφ(k) N Lφ(k) − K∑ k=K̂+1 Nφ(k) N Lφ(k)  ≤ 0 Similarly, we can prove Lα(K̂1) < Lα(K̂2) if K̂1 > K̂2.

heading: B PROOF OF THEOREM 4.2

text:
Based on the convergence of Adversarial Training (Sinha et al., 2018), we proof Theorem 4.2 in this section.
proof of Theorem 4.2. Let c : X ×X → R+ ∪ {∞}, where c(x, x0) is the “cost” for an adversary to perturb x0 to x. Let f(θ, x;x0) = `(θ;x)− γc(x, x0), noting that the gradient steps is preformed as
gt = ∇θf(θt, x̂;xt), where x̂ is an approximate maximizer of f(θ, x;xt) in x, and θt+1 = θt−µtgt. We assume µt ≤ 1Lψ in the rest of the proof, which is satisfied for the constant step size µ =
√ ∆L
LψTδ2
and T ≥ Lψ∆Lδ2 . By a Taylor expansion using the Lψ-smoothness of the objective Lk for k-th client, we have
Lk ∣∣ θt+1 ≤ Lk ∣∣ θt + 〈 ∇Lk ∣∣ θt , θt+1 − θt 〉 + Lψ 2 ||θt+1 − θt||22 (10)
= Lk ∣∣ θt − µt||∇Lk ∣∣ θt ||22 + Lψµ 2 2 ||gt||22 + µt 〈 ∇Lk ∣∣ θt ,∇Lk ∣∣ θt − gt 〉 = Lk ∣∣ θt − µt ( 1− 1
2 Lψµ
2 ) ||∇Lk ∣∣ θt ||22
+ µt(1− Lψµ) 〈 ∇Lk ∣∣ θt ,∇Lk ∣∣ θt − gt 〉 + Lψµ 2 2 ||gt −∇Lk ∣∣ θt ||22
Consider the function φγ(θ;x0) = supx∈Z f(θ, x;x0), we define the potentially biased errors ζt = gt −∇θφγ(θt;xt). Then we have the following relationship,
Lk ∣∣ θt+1 ≤Lk ∣∣ θt − µt ( 1− 1
2 Lψµ
2 ) ||∇Lk ∣∣ θt ||22 (11)
+ µt(1− Lψµ) 〈 ∇Lk ∣∣ θt ,∇Lk ∣∣ θt −∇θφγ(θt;xt) 〉 − µt(1− Lψµt) 〈 ∇Lk ∣∣ θt , ζt 〉 + Lψµ 2 2 ||∇θφγ(θt;xt) + ζ2 −∇Lk ∣∣ θt ||22
= Lk ∣∣ θt − µt ( 1− 1
2 Lψµ
2 ) ||∇Lk ∣∣ θt ||22
+ µt(1− Lψµ) 〈 ∇Lk ∣∣ θt ,∇Lk ∣∣ θt −∇θφγ(θt;xt) 〉 − µt(1− Lψµt) 〈 ∇Lk ∣∣ θt , ζt 〉
+ Lψµ
2 t
2
( ||ζt||22 + ||∇θφγ(θt;xt)−∇Lk ∣∣ θt ||22 + 2 〈 ∇θφγ(θt;xt)−∇Lk ∣∣ θt , ζt 〉) .
Since ±〈a, b〉 ≤ 12 ( ||a||22 + ||b||22 ) , we have
Lk ∣∣ θt+1 ≤Lk ∣∣ θt − µt
2 ||∇Lk
∣∣ θt ||22 + µt((1− Lψα)) 〈 ∇Lk ∣∣ θt ,∇Lk ∣∣ θt −∇θφγ(θt;xt) 〉 (12)
+ µt((1 + Lψµ))
2 ||ζ||22 + Lψµ2t ||∇θφγ(θt;xt)−∇Lk ∣∣ θt ||22.
Then, letting xt∗ = arg maxx f(θ t, x;xt), the error ζt satisfies,
||ζ||22 =||∇θφγ(θt;xt)−∇f(θ, x̂t;xt)||22 = ||∇θ`(θ, xt∗)−∇θ`(θ, x̂t)||22 (13)
≤ Lθx ||x̂t − xt∗||22 ≤ 2L2θx λ , (14)
where the final inequality utilize the λ = γ − Lxx strong-concavity of x 7→ f(θ, x;x0). For convenience, let ̂ =
2L2θx γ−Lxx . Taking conditional expectations in Eq. (12) and using E [∇θφγ(θ
t;xt)|θt] = ∇Lk ∣∣ θt , we have,
E [ Lk ∣∣ θt+1 − Lk ∣∣ θt |θt ] ≤ −µt
2 ||∇Lk
∣∣ θt ||22 + µt((1 + Lψµ))
2 ̂+ Lψµ
2 t ||∇θφγ(θt;xt)−∇Lk ∣∣ θt ||22
(15)
≤ −µt 2 ||∇Lk ∣∣ θt ||22 + µt̂+ Lψµ2t ||∇θφγ(θt;xt)−∇Lk ∣∣ θt ||22
Since µt ≤ 1Lψ , taking a fixed step size µ, we have,
E [ ||∇Lk ∣∣ θt ||22 ] − 2̂ ≤ 2 µ E [ Lk ∣∣ θt − Lk ∣∣ θt+1 ] + 2Lψµδ 2 (16)
Because E [ ||∇θφγ(θ;Z)−∇Lk ∣∣ ( θ)||22 ] ≤ δ2, summing over t, we have,
1
T T∑ t E [ ||∇Lk ∣∣ θt ||22 ] − 2̂ ≤ 2 µT (Lk ∣∣ θ0 − E[Lk ∣∣ θT ]) + 2Lψµδ 2
≤ 2∆ µT + 2Lψµδ 2 (17)
Since µ = √
Delta LψTδ2 , and λ = γ − Lxx, we can get the following result,
1
T T∑ t E [ ||∇Lk ∣∣ θt ||22 ] ≤ 4L 2 θx λ + 4δ
√ L∆
T (18)
Adopting our α-weighted relaxation, we have,
1
T T∑ t E [∣∣∣∣∣∣∣∣∇Lα(K̂)∣∣θt∣∣∣∣∣∣∣∣2 2 ]
= 1
T T∑ t E ∣∣∣∣∣∣∣∣(1 + α) K̂∑ k=1 N (t) φ(k) N ∇Lφ(k) ∣∣ θt + (1− α) K∑
k=K̂+1
N (t) φ(k)
N ∇Lφ(k)
∣∣ θt ∣∣∣∣∣∣∣∣2 2  ≤ 1 T T∑ t (1 + α) K̂∑ k=1 N (t) φ(k) N E [∣∣∣∣∣∣∣∣∇Lφ(k)∣∣θt∣∣∣∣∣∣∣∣2 2 ] + (1− α) K∑ k=K̂+1 N (t) φ(k) N E [∣∣∣∣∣∣∣∣∇Lφ(k)∣∣θt∣∣∣∣∣∣∣∣2 2
] ≤ 1 T T∑ t (1 + α) K̂∑ k=1 N (t) φ(k) N + (1− α) K∑ k=K̂+1 N (t) φ(k) N (4L2θx λ + 4δ √ L∆ T )
= 1
T T∑ t 1 + α∑K̂k=1N (t)φ(k) −∑Kk=K̂+1N (t)φ(k) N (4L2θx λ + 4δ √ L∆ T )
= ( 1 + α 1 T ∑T t ξ (t)
N
)( 4L2θx
λ + 4δ
√ L∆
T
) ,
(19)
where ξ(t) = ∑K̂ k=1N (t) φ(k) − ∑K k=K̂+1N (t) φ(k) to simplify the notations.

heading: C PROOF OF THEOREM 4.3

text:
Based on the convergence of FedAvg (Li et al., 2019), we proof Theorem 4.3 in this section.
First, we make the following assumptions and present some useful lemmas. Specifically, we make the following assumptions. Assumption C.1 and C.2 are standard (typical examples are the `2-norm regularized linear regression, logistic regression, or softmax classifier). Assumption C.3 and C.4 have been made by the previous works (Zhang et al., 2013; Li et al., 2019). Assumption C.1. L1, . . . , LK are all L-smooth: for all v and w, Lk(v) ≤ Lk(w) + (v − w)T∇Lk(w) + L2 ||v − w|| 2 2. Assumption C.2. L1, . . . , LK are all λ-strongly convex: for all v and w, Lk(v) ≥ Lk(w) + (v − w)T∇Lk(w) + λ2 ||v − w|| 2 2.
Assumption C.3. Let ξkt be sampled from the k-th device’s local data uniformly at random. The variance of stochastic gradients in each device is bounded: E||∇Lk(wkt , ξkt )−∇Lk(wkt )||2 ≤ δ2k for k = 1, · · · ,K. Assumption C.4. The expected squared norm of stochastic gradients is uniformly bounded, i.e., E||∇Lk(wkt , ξkt )||2 ≤ ς2 for all k = 1, · · · ,K and t = 1, · · · , T − 1.
We use the following lemmas proved by Li et al. (2019). Let θkt denotes the model parameter maintained in the k-th client at t-th step, Θ represents an immediate result of one step SGD update from θkt . For convenience, we define Θ̄t = ∑K k=1 Nk N Θt, θ̄t == ∑K k=1 Nk N θt, ḡt = ∑K k=1 Nk N ∇Lk(θ k t )
and gt = ∑K k=1 Nk N ∇Lk(θ k t , ξ k t ). Therefore, Egt = ḡt. Lemma C.1 (Results of one step SGD). Assume Assumption C.1 and C.2. If ηt ≤ 14L , we have
E||Θ̄t+1 − θ∗||2 ≤ (1− ηtλ)E||θ̄t − θ∗||2 (20)
+ η2tE||gt − ḡt||2 + 6Lη2tΓ + 2E K∑ k=1 Nk N ||θ̄t − θkt ||2,
where Γ = L∗ − ∑K k Et Nk N L ∗ k ≥ 0 Lemma C.2 (Bounding the variance). Assume Assumption C.3. It follows that
E||gt − ḡt||2 ≤ K∑ k=1 ( Nk N )2 δ2k, (21)
Lemma C.3 (Bounding the divergence of θkt ). Assume Assumption C.4, that ηt is non-increasing and η ≤ 2ηt+E for all t > 0. It follows that
E [ K∑ k=1 Nk N ||θ̄t − θkt ||2 ] ≤ 4η2t (E − 1)2ς2 (22)
proof of Theorem 4.3. Let ∆t = E||θt − θ∗||2. From Lemma C.1, Lemma C.2 and Lemma C.3, it follows that
∆t+1 ≤ (1− ηtλ)∆t + η2tB, (23) where,
B = K∑ k
( P
(T ) k
1 + α ξ (T )
N
)2( Nk N δk )2 + 6L ( L∗ − K∑ k P (T ) k 1 + α ξ (T ) N Nk N L∗k ) + 8(E − 1)2ς2, (24)
and ( P (T ) k
1+α ξ (T )
N
)2 and P (T ) k
1+α ξ (T )
N , are acted as the scalar timing by the personalized variance bound δ2k and the local optimum L∗k of each client.
For a diminishing stepsize, ηt = βγ+t for some β > 1 λ and γ > 0 such that η1 ≤ min{ 1 λ , 1 4L} = 1 4L and ηt ≤ 2ηt+E . We will prove that ∆t ≤ νγ+t , where ν = max{ β2B βλ−1 , (γ + 1)∆1}. The above can be proved by induction. Firstly, the definition of ν ensures that it holds for t = 1. Assume the conclusion holds for some t, it follows that,
∆t+1 ≤ (1− ηtλ)∆t + η2tB
≤ (1− βλ t+ γ ) ν t+ γ +
β2B
(t+ γ)2
= t+ γ − 1 (t+ γ)2 ν + [ β2B (t+ γ)2 − βλ− 1 (t+ γ)2 ν]
≤ ν t+ γ + 1 .
(25)
Then by the L-smoothness of L(·),
E[Lt]− L∗ ≤ L
2 ∆t ≤
L
2
ν
γ + t (26)
Specifically, if we choose β = 2λ , γ = max{8 L λ , E} − 1 and denote κ = L λ , then ηt = 2 λ 1 γ+t . One can verify that the choice of ηt satisfies ηt ≤ 2ηt+E for t ≥ 1. Then we have
ν = max
{ β2B
βλ− 1 , (γ + 1)∆1
} ≤ β 2B
βλ− 1 + (γ + 1)∆1 ≤
4B λ2 + (γ + 1)∆1, (27)
and
E[Lt]− L∗ ≤ L
2
ν γ + t ≤ κ γ + t
( 2B
λ + λ(γ + 1) 2 ∆1
) (28)
D LEARNING FRAMEWORK AND ALGORITHM
Here, we provide an intuitive illustration of our proposed α-WFAT in Figure 5. Based on the αweighted mechanism, we provide a new flexible framework for the combination of adversarial training with federated learning. It is orthogonal to a variety of different adversarial training (Zhang et al., 2019; Wu et al., 2020; Zhang et al., 2020; Chen et al., 2020; 2021; Wang et al., 2020a; Jiang et al., 2020; Wang et al., 2020c) methods and federated learning algorithms (Li et al., 2018; Kairouz et al., 2019; Hong et al., 2021) which gain the adversarial robustness or alleviate the data heterogeneity on the client side, and can be simply but effectively combined with other approach.

heading: E EXPERIMENTAL DETAILS

text:
Dataset. We conduct the experiments on three benchmark datasets, i.e., SVHN (Netzer et al., 2011), CIFAR-10 and CIFAR-100 (Krizhevsky, 2009) for federated adversarial training. For the IID scenario, we randomly distribute these datasets to each client. For simulating the Non-IID scenario, we follow McMahan et al. (2017); Shah et al. (2021) to distribute the training data based on their labels. To be specific, a skew parameter s is utilized in the data partition introduced by Shah et al. (2021), which enables K clients to get a majority of the data samples from a subset of classes. We denote the set of all classes in a dataset as Y and create Yk by dividing all the class labels equally among K clients. Accordingly, we split the data across K clients that each client has (100− (K − 1)× s)% of data for the class in Yk and s% of data in other split sets. In our experiments, we set s = 2 for simulating the Non-IID partition with 5 clients as Shah et al. (2021) recommended.
Training and Evaluation. In the experiments, we follow the previous works to leverage the same architectures, i.e., NIN (Lin et al., 2014) for CIFAR-10, ResNet-18 (He et al., 2016) for CIFAR-100 and Small CNN (Zhang et al., 2020) for SVHN. For the local training batch size, we set 32 for CIFAR-10, 128 for CIFAR-100 and SVHN. For the training schedule, SGD is adopted with 0.9 momentum for 100 communication rounds under 5 clients as in (Hong et al., 2021; Shah et al., 2021), and the weight decay = 0.0001. For adversarial training, we set the configurations of PGD respectively (Madry et al., 2018) for different datasets. On CIFAR-10/CIFAR-100, we set the perturbation bound = 8/255, the PGD step size 2/255 and set the PGD step number 10. On SVHN, we set the perturbation bound = 4/255, the PGD step size 1/255, and keep the same step number 10. Regarding the evaluation, the accuracy for the natural test data and that for the adversarial test data are computed
following Wang et al. (2019); Wu et al. (2020). Note that, the adversarial test data are generated by FGSM, PGD-20, C&W (Carlini & Wagner, 2017) attack with the same perturbation bound and step size as the training. All the adversarial generations have a random start, i.e, the uniformly random perturbation of [− , ] added to the natural data before attacking iterations. Besides, we also report the robustness under a stronger AutoAttack, termed as AA for simplicity.
As for our α-WFAT, different training tasks adopt different α-weighted mechanism considering different characteristic of local training data, we set α = 1/6 (i.e., 1+α1−α = 1.4) for the experiments on CIFAR-10, and α = 1/41 (i.e., 1+α1−α = 1.05) for the experiments on CIFAR-100 and α = 1/11 (i.e., 1+α1−α = 1.2) for the experiments on SVHN. As for FedProx, we set µ = 0.01 for each dataset and its α for α-weighted mechanism are 1/11, 1/41, and 1/11. As for Scaffold, the α adopted for previous datasets are 1/11, 1/101 and 1/11 respectively.
As for the choice of the hyper-parameter α, one useful way to set it might be progressively probing its effect in a value-growth manner. When the α is very small, the objective will approximately degenerate the original objective of FAT, so does the performance with no harm. Slightly enlarging α can improve the performance due to the benefit of the bias-variance trade-off, and then make a stop in one point where the performance becomes drop.
E.1 EMPHASIZE/DE-EMPHASIZE IN OUR α-WFAT
We conduct an empirical comparison between α-WFAT that emphasizes (relatively de-emphasize the other clients) the client model with the smallest loss and a contrary variant that de-emphasizes it (relatively emphasize the other clients) as follows. We find that de-emphasizing the client with smallest loss (relatively emphasize those with larger loss) consistently harm the model performance across these evaluations.
E.2 MEAN AND STD RESULTS OF THE NON-IID SETTINGS
Considering that the Non-IID results are sensitive to the selection of data in each client, we conduct our experiments on Non-IID settings for multiple times and conclude the results as follows. In summary, our α-WFAT can consistently improve the model robustness with comparable or even better natural performance than previous federated optimization methods.

title: α-WEIGHTED FEDERATED ADVERSARIAL TRAINING


summaries: In contrast to previous works on lifelong machine learning (LML) that put their focus on the supervised learning settings, this paper concentrates on the scenario that only a limited amount of data is available. The proposed method MAKO is mounted on the top of supervised LML model, without introducing additional knowledge based overhead, for better leveraging the unlabeled data. Labeling new data can be realized by using the data programming method which is supervised by the labeled data. The target of this paper is to design a SSL LML framework that minimizes the performance between using partially labeled data, and the upper-bound performance using fully labeled data. Several experiments on standard image classification data sets including MNIST, CIFAR-10 and CIFAR-100 are used to evaluate the the effectiveness of MAKO.

summaries: This paper propose a wrapper tool that mounts on top of supervised Lifelong Machine Learning (LML) frameworks, leveraging a well-known method data programming. The contributions of this paper can be summarized in three aspects. 1)  Adapting automatic label generation by semi-supervised learning/data programming to LML in some special scenario. 2) Implementing a LML wrapper that can accomplish some tasks under some restrictions. 3) Through detailed experimental results prove the superiority of its method.

summaries: This paper proposes  data programming method, named Mako,  for semi-supervised continual learning. Mako automatically generates labels for unlabeled data with a set of weak labeling functions, each of the functions is trained on subset of training set with bootstrapping. Experimental on several datasets demonstrate the effectiveness of the proposed methods.

summaries: This paper presents an interesting idea of using data programming techniques to enable continual semi-supervised learning with limited labeled data. It proposes a stage-wise pipeline where probabilistic pseudo labels are first produced by a Snuba based Data Programming framework, then calibrates them by the temperature scaling, and finally inputs into the mounted Lifelong Machine Learning (LML) tools. Experiments show that the proposed framework achieves similar performance to fully supervised methods.

abstractText: Lifelong machine learning (LML) is a well-known paradigm mimicking the human learning process by utilizing experiences from previous tasks. Nevertheless, an issue that has been rarely addressed is the lack of labels at the individual task level. The state-of-the-art of LML largely addresses supervised learning, with a few semi-supervised continual learning exceptions which require training additional models, which in turn impose constraints on the LML methods themselves. Therefore, we propose Mako, a wrapper tool that mounts on top of supervised LML frameworks, leveraging data programming. Mako imposes no additional knowledge base overhead and enables continual semi-supervised learning with a limited amount of labeled data. This tool achieves similar performance, in terms of per-task accuracy and resistance to catastrophic forgetting, as compared to fully labeled data. We ran extensive experiments on LML task sequences created from standard image classification data sets including MNIST, CIFAR-10 and CIFAR100, and the results show that after utilizing Mako to leverage unlabeled data, LML tools are able to achieve 97% performance of supervised learning on fully labeled data in terms of accuracy and catastrophic forgetting prevention. Moreover, when compared to baseline semi-supervised LML tools such as CNNL, ORDisCo and DistillMatch, Mako significantly outperforms them, increasing accuracy by 0.25 on certain benchmarks.

authors:
M. Baucum
D. Belotto
S. Jeannet
E. Savage
P. Mupparaju
C.W. Morato

title: Semi-supervised deep continuous learning

venue: In Proceedings of the International Conference on Deep Learning Technologies,

authors:
A. Bulat
J. Kossaifi
G. Tzimiropoulos
M. Pantic

title: Incremental multi-domain learning with network latent tensor factorization

venue: In Proceedings of the AAAI Conference on Artificial Intelligence

title: Multitask Learning

venue: PhD thesis,

authors:
Z. Chen
B. Liu

title: Lifelong Machine Learning. Synthesis Lectures on Artificial Intelligence and Machine Learning

title: Sinkhorn distances: Lightspeed computation of optimal transport

venue: Advances in Neural Information Processing Systems (NIPS),

authors:
C. Finn
T. Yu
J. Fu
P. Abbeel
S. Levine

title: Generalizing skills with semi-supervised reinforcement learning

venue: Proceedings of the International Conference on Learning Representations (ICLR),

authors:
Y. Gao
Q. She
J. Ma
M. Zhao
W. Liu
A.L. Yuille

title: NDDR-CNN: Layer-wise feature fusing in multi-task cnn by neural discriminative dimensionality reduction

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
C. Guo
G. Pleiss
Y. Sun
K.Q. Weinberger

title: On calibration of modern neural networks

venue: Proceedings of the International Conference on Machine Learning (ICML),

authors:
K. He
X. Zhang
S. Ren
J. Sun

title: Deep residual learning for image recognition

venue: IEEE Conference on Computer Vision and Pattern Recognition (CVPR),

title: Learning multiple layers of features from tiny images

venue: Technical report, University of Toronto,

authors:
A. Kumar
H. Daume

title: Learning task grouping and overlap in multi-task learning

venue: In Proceedings of the 29th International Conference on Machine Learning,

authors:
S. Laine
T. Aila

title: Temporal ensembling for semi-supervised learning

venue: Proccedings of the International Conference on Learning Representations (ICLR),

authors:
Y. LeCun
C. Cortes

title: Mnist handwritten digit database

venue: URL http://yann.lecun. com/exdb/mnist/

authors:
Y. Lecun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

venue: Proceedings of the IEEE,

authors:
S. Lee
J Stokes
E. Eaton

title: Learning shared knowledge for deep lifelong learning using deconvolutional networks

venue: In Proceedings of the International Joint Conference on Artificial Intelligence,

title: Lifelong machine learning: a paradigm for continuous learning

venue: Frontier of Computer Science,

authors:
Y. Lu
A. Kumar
S. Zhai
Y. Cheng
T. Javidi
R. Feris

title: Fully-adaptive feature sharing in multitask networks with applications in person attribute classification

authors:
I. Misra
A. Shrivastava
A. Gupta
M. Hebert

title: Cross-stitch networks for multi-task learning

authors:
C. Olivier
S. Bernhard
Z. Alexander

title: Semi-supervised learning

venue: IEEE Transactions on Neural Networks,

authors:
S.J. Pan
Q. Yang

title: A survey on transfer learning

venue: IEEE Transaction on Knowledge and Data Engineering,

title: Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods

venue: Advances in Large Margin Classifiers,

authors:
A. Rasmus
H. Valpola
M. Honkala
M. Berglund
T. Raiko

title: Semi-supervised learning with ladder networks

authors:
A. Ratner
S.H. Bach
H. Ehrenberg
J. Fries
S. Wu
C. Ré

title: Snrokel: rapid training data creation with weak supervision

venue: Proceedings of the VLDB Endowment,

authors:
A. Ratner
C.S. De Sa
Wu
D. Selsam
C. Ré

title: Data programming: Creating large training sets, quickly

authors:
P. Ruvolo
E. Eaton

title: ELLA: An efficient lifelong learning algorithm

venue: Proceedings of the International Conference on Machine Learning (PMLR),

title: Active task selection for lifelong machine learning

venue: Proceedings of the AAAI Conference on Artificial Intelligence,

authors:
J. Schwarz
W. Czarnecki
J. Luketina
A. Grabska-Barwinska
Y.W. Teh
R. Pascanu
R. Hadsell

title: Progress & compress: A scalable framework for continual learning

venue: In Proceedings of the International Conference on Machine Learning,

title: Active learning literature survey

venue: Technical report, Department of Computer Science, University of Wisconsin-Madison,

authors:
J. Smith
J. Balloch
Y. Hsu
Z. Kira

title: Memory-efficient semi-supervised continual learning: The world is its own replay buffer

venue: In Proceedings of the International Joint Conference on Neural Networks,

authors:
G. Sun
Y. Cong
X. Xu

title: Active lifelong learning with ”watchdog

venue: In Thirty-Second AAAI Conference on Artificial Intelligence,

authors:
A. Tarvainen
H. Valpola

title: Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results

authors:
S. Thrun
T.M. Mitchell

title: Lifelong robot learning

venue: In The Biology and Technology of Intelligent Autonomous Agents,

authors:
P. Varma
C. Ré

title: Snuba: automating weak supervision to label training data

authors:
L. Wang
K. Yang
C. Li
L. Hong
Z. Li
J. Zhu

title: Ordisco: Effective and efficient usage of incremental unlabeled data for semi-supervised continual learning

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),

authors:
S. Wang
Z. Chen
B. Liu

title: Mining aspect-specific opinion using a holistic lifelong topic model

venue: Proceedings of the International Conference on World Wide Web (WWW),

authors:
J. Yoon
E. Yang
J. Lee
S.J. Hwang

title: Lifelong learning with dynamically expandable networks

heading: 1 INTRODUCTION

text:
Since 1995, researchers have been actively seeking machine learning (ML) frameworks that can better mimic the human learning process by retaining memories from past experiences (Thrun & Mitchell, 1995; Liu, 2017). Hence, in contrast to traditional isolated ML where knowledge is never accumulated, the concept of lifelong machine learning (LML) is defined as training ML models for continual learning over task sequences, with a knowledge base to store information that could be helpful in the future. Under this definition, LML can be seen as continual transfer learning (Pan & Yang, 2015) with memory or sequential multi-task learning (Caruana, 1997).
Nevertheless, at the level of individual tasks, the current state-of-the-art of LML still remains largely supervised. A challenge that has rarely been mentioned is that labels can still be expensive and rarely available for each task, such that supervised training can hardly provide acceptable performance. For LML, performance is not only measured at task level, but also for the entire lifetime, with attributes such as resistance to catastrophic forgetting and space-efficiency of knowledge base.
We take a more generic approach to semi-supervised lifelong learning and develop a technique that can wrap around any existing continual learning algorithm. Specifically, we propose to use data programming (Ratner et al., 2016b) to label new data under the supervision of a set of weak labeling functions trained from a limited number of labeled data points. Data programming has proven successful for isolated learning, and so this is the first work integrating it with lifelong learning.
Our approach, called Mako, sits atop an existing lifelong learner to turn it into a semi-supervised learner. For each task, Mako takes as input a small labeled dataset plus an unlabeled dataset with no restriction on size, generates labels for the unlabeled data and then updates the lifelong learner supervised by both sets. This approach builds upon the widely used Snuba algorithm (Varma & Ré,
2016), and we show that its theoretical guarantees still hold in the lifelong setting. Mako’s procedure leverages automatic hyperparameter tuning, data programming and confidence calibration, in order to adapt automatic labeling to constantly varying LML tasks. We show that Mako produces adequately high performance, in terms of both task accuracy and prevention of catastrophic forgetting, that approaches that of training on fully labeled data without costing extra knowledge base space overhead.
We extensively evaluated Mako on various partially labeled LML task sequences generated from commonly used datasets including MNIST, CIFAR-10 and CIFAR-100 (LeCun & Cortes, 2010; Krizhevsky, 2009), while mounting on a diversity of supervised LML frameworks such as Deconvolutional Factorized CNN (DF-CNN), Dynamic Expandable Network (DEN) and Tensor Factorization (TF) (Lee et al., 2019; Yoon et al., 2018; Bulat et al., 2020). We compared the results to supervised learning on fully labeled data, as well as the same partially labeled data with existing semi-supervised LML tools: CNNL, ORDisCo and DistillMatch (Baucum et al., 2017; Wang et al., 2021; Smith et al., 2021). Empirically, we show that the performance of LML methods improves as giving more training data even with Mako labels, achieving at least 97% performance relative to LML methods trained on ground-truth labels and being able to beat existing semi-supervised LML tools by approximately 0.25 higher accuracy.
Contributions Summary:
1. Adapting automatic label generation by semi-supervised learning/data programming to LML in the scenario where labeled training data is expensive to obtain compared to unlabeled for all tasks. 2. Implementing a LML wrapper, namely Mako, for the scenario of expensive labels, such that, when given partially labeled data of limited size and compared to the current supervised state-ofthe-art with fully labeled data, each LML task sequence (1) requires significantly fewer labeled data to achieve high accuracy on individual tasks, (2) maintains similar resistance to catastrophic forgetting and (3) does not cost extra knowledge base storage. 3. Extensive experiments on lifelong binary and multiclass image classification on 3 commonly used datasets, including comparison to supervised and semi-supervised LML baselines, accomplishing very close performance to supervised LML on fully labeled data and significantly outperforming baseline semi-supervised LML frameworks.

heading: 2 RELATED WORK

text:
Lifelong machine learning (LML) is a concept of continual learning among a sequence of tasks. Specifically, given multiple machine learning tasks arriving continuously, the LML framework accumulates the knowledge of previous tasks and utilizes it for future ones (Chen & Liu, 2016; Ruvolo & Eaton, 2013b). The method of retaining and adopting the knowledge base varies depending on the characteristics of tasks and learning models. For instance, a latent matrix is used to keep prototypical weights for linear models (Kumar & Daume, 2012; Ruvolo & Eaton, 2013a), and for deep neural networks, either weights of layers (Yoon et al., 2018; Lu et al., 2017; Bulat et al., 2020; Lee et al., 2019) or extracted features of layers (Rusu et al., 2016; Misra et al., 2016; Gao et al., 2019; Schwarz et al., 2018) are considered as the knowledge base to transfer. Besides research on models to transfer knowledge across tasks, the LML community has also been working on task order sorting for higher overall performance (Sun et al., 2018; Ruvolo & Eaton, 2013b). Nevertheless, all these works assume that each individual task training is supervised with ground-truth labels for the entire training set. In many real-life ML tasks, obtaining labels has been and continues to be expensive (Settles, 2009). Only a few works have addressed this issue on LML in very specific domains, such as continual sentimental analysis with words partially labeled (Wang et al., 2016) and reinforcement learning in a sequence of state spaces without explicit rewards (Finn et al., 2017). Different from previous work, Mako enables high performance in continual learning on generic ML tasks given partially labeled data, with the cardinality of labels restricted at a small number.
To tackle expensive labels in ML, researchers have purposed various methods such as active learning (Settles, 2009) or semi-supervised learning (Olivier et al., 2006), which is an ML framework that takes both labeled and unlabeled data as inputs. The unlabeled data can directly assist the training, or can serve as a target data set yet to be labeled. In recent years, with the rising enthusiasm and need in deep learning, various methods have been used to assist semi-supervised learning with DNN models (Rasmus et al., 2015; Laine & Aila, 2016; Tarvainen & Valpola, 2017). One branch of
semi-supervised learning, namely data programming or weak supervision (Ratner et al., 2016b), focuses on auto-generation of labels on an unlabeled dataset with the help of a small labeled dataset. Targeting this problem, researchers leverage weak labeling functions that each can label with an accuracy slightly higher than a coin flip. Then, ensembling algorithms are able to bag these weak labelers and produce highly accurate final labels. In other words, the weak labels supervise the training of the final ensembled generative model. There exists different implementations of such generative model training such as Snorkel (Ratner et al., 2016a).
Semi-supervised learning is an underexplored problem in the LML setting; all the works mentioned above have addressed problems in isolated ML only. Early work in semi-supervised incremental learning, in which all tasks are trained simultaneously as batches of unlabeled data are incrementally observed by a classifier, has identified challenges pertaining to selection of the label generating model architecture and confidence calibration of the generated labels (Baucum et al., 2017), processes which Mako undertakes autonomously through automatic search for weak labelers before ensembling, and confidence calibration after labels are produced. Pioneering work in semi-supervised LML requires training of additional models for out-of-distribution detection (Smith et al., 2021) or generative replay (Wang et al., 2021). Conversely, by focusing on label generation through data programming, our approach achieves similar behavior through a pre-processing workflow that does not impose additional constraints on the LML approach or require additional knowledge base storage.
For data programming tools, it has been a long standing issue to obtain weak labeling functions as input. One approach is manually designing the weak labelers by domain experts (Ratner et al., 2016b;a), while other researchers seek automatic labeler generation. For instance, Snuba (Varma & Ré, 2016) outputs weak supervisors with an accuracy guarantee on the final ensembled data programming model. Thus far, Snuba has been evaluated on various isolated ML tasks, with weak labelers in form of k-nearest-neighbors, decision stumps and logistic regressors, and has been shown to ace in natural language processing and image classification. It also succeeds in more complex applications such as classifying bone tumors in medical domain. In our work, we build a weak labeling function generation module in Mako based on Snuba, aiming to support a larger variety of labeler models for LML, while maintaining the theoretical accuracy guarantee of generated labels.

heading: 3 PROBLEM FORMULATION

text:
LML: Given a sequence of ML tasks: T1, T2, . . . , Tm, where m is an unbounded integer, each task Ti has an underlying data space Xi and label space Yi. Ti has ni,train labeled training data (Xi,train, Yi,train) ∼ Di, such that Xi,train ∈ X ni,train i and Yi,train ∈ Y ni,train i , following some task-specific i.i.d. distributionDi. The task also has ni,test testing data (Xi,test, Yi,test) drawn from the same distribution.
Traditionally, an LML model encounters the tasks in order. At Ti, it trains on the full set of (Xi,train, Yi,train) with supervised learning and obtain model fi : ⋃i j=1 Xi 7→ ⋃i j=1 Yi. Immediately after this training, it predicts the j-th task with Ŷij = fi(Xj,test) for each j ≤ i. There are two objectives:
1. High test accuracy. Formally, denote testing accuracy of task Tj right after the training of task Ti on (Xi,train, Yi,train) as
aij =
∑nj,test k=1 1(ŷk = yk)
nj,test (1)
with ŷk and yk the k-th label in Ŷij and Yi,test, respectively. One LML objective in the current state-of-the-art is to maximize the peak per-task accuracy up to task i defined as
ãi = 1
i i∑ j=1 ajj (2)
Peak per task accuracy is defined on all tasks i = 1, . . . ,m , and shows the LML performance on the current training task on the basis of the accumulated knowledge.
2. Low catastrophic forgetting. A critical aspect of LML is to prevent catastrophic forgetting of previous tasks. The resistance to catastrophic forgetting can be quantified by the average testing accuracy of all tasks encountered so far. For each task Ti, denote a second objective, final accuracy
up to task i as
āi = 1
i i∑ j=1 aij (3)
The second objective is to maximize āi for all i = 1, . . . ,m.The gap between peak per-task accuracy and final accuracy expresses how much knowledge of previous tasks LML method can preserve through the streams of tasks. Therefore, we define a third metric to be maximized, catastrophic forgetting ratio up to task i, as
ci = 1
i i∑ j=1 aij ajj
(4)
This metric is less than 1 if the LML model loses its performance on the earlier tasks, and it is greater than 1 if there is positive knowledge transfer from the later tasks to the earlier ones.
Semi-supervised LML with data programming: The key challenge we want to address is the cost of labeling data in all LML tasks. That is, the number of available labeled training data is small. Therefore, we would like to split (Xi,train, Yi,train) in the traditional LML problem into disjoint (Xi,L, Yi,L, Xi,U ), where (Xi,L, Yi,L) is a set of labeled training data with restriction on size and Xi,U is a set of unlabeled data with no such restriction. In other words, |Xi,L| is small, e.g. |Xi,L| ≤ 150 for a 10-way image classification problem. Apparently, the LML model is now trained with semi-supervised learning. For task Ti, we would like to leverage data programming on (Xi,L, Yi,L, Xi,U ) to first train a generative model πi : Xi 7→ Yi. This model automatically labels Xi,U with Y πi,U = πi(Xi,U ). Then, the LML framework will be trained on (Xi,L, Yi,L, Xi,U , Y πi,U ). Denote the LML model immediately after this training as fπi : ⋃i j=1 Xi 7→ ⋃i j=1 Yi, and Ŷ πij = fπi (Xj,test) for each task j ≤ i.
In this scenario, we redefine testing accuracy in Equation 1 as
aπij =
∑nj,test k=1 1(ŷ π k = yk)
nj,test (5)
where the only difference is that ŷπk is the k-th label in Ŷ π ij instead of Ŷij . From Equation 5, we can then redefine metrics in Equations 2, 3 and 4 as
ãπi = 1
i i∑ j=1 aπjj (6) ā π i = 1 i i∑ j=1 aπij (7) c π i = 1 i i∑ j=1 aπij aπjj
(8)
Our research problem is to design a semi-supervised LML framework leveraging data programming that minimizes the performance between using partially labeled data, (Xi,L, Yi,L, Xi,U , Y πi,U ), and the upper-bound performance using fully labeled data, (Xi,L, Yi,L, Xi,U , Yi,U ), in terms of these three metrics while imposing no additional knowledge base storage overhead in the LML framework.

heading: 4 MAKO: LIFELONG MACHINE LEARNING FRAMEWORK

text: We implemented Mako, a semi-supervised LML framework that can be mounted on top of any existing LML tool, with (Xi,L, Yi,L, Xi,U ) as input for each task Ti. The automatic label generation of Y πi,U is done by data programming, consisting of generating weak labeling functions and ensembling a generative model. Nevertheless, different from data programming on isolated ML, due to the variation of tasks throughout LML, we need to actively adapt both the weak and the strong models to maximize the performance at each task. This is accomplished by automatic search on architecture and training hyperparameter search before weak labeler generation and confidence calibration after the ensembled model πi is trained. The following subsections explains the Mako workflow step-by-step, as illustrated in Figure 1.

heading: 4.1 AUTOMATIC HYPERPARAMETER SEARCH

text:
Before producing weak labeling functions, two questions must be answered: (1) How do we choose the model architecture for our weak labeling functions? (2) How do we train these models after architecture is decided? Formally, these questions lead to the decision of architectural and training hyperparameters of labelers, which Mako accomplishes automatically.
The only prior knowledge required is a search space, manually designed, of the architecture and training hyperparameters. For instance, given that the task is image classification, the search space of labeler architecture will include CNNs with the same input and output dimensions, but different configurations of hidden layers. Similarly, the training hyperparameters will be searched on different learning rates, batch sizes and number of epochs.
The automatic tuning of weak labelers therefore traverses the search space until a satisfactory configuration is found. The stopping criterion is defined as follows: after training ten labelers with a given configuration of architecture and training hyperparameters on different bootstrapped subsets of (Xi,L, Yi,L), 9 out of 10 achieves an accuracy on the entire (Xi,L, Yi,L) above some threshold a. This criterion shows the generalization capability of sampled labelers and alternative criteria can be used, such as 8 out of 10 or average accuracy ≥ a. We accept such a configuration because we train the labelers on bootstrapped subsets of data during data programming, which will be further explained in 4.2. If no configuration in the search space is satisfactory, we decrease a by 0.05 and repeat the search. Hence, we can start from a sufficiently high a such as 0.9. For efficiency, Mako selects the configuration with the smallest number of training epochs among all the acceptable ones.
There exists a efficiency-automation trade-off in this hyperparameter search. The less prior knowledge we have for the task, the larger search space we need to input to Mako and thus a larger time overhead. In contrast, more manual exploration on the task will lead to a smaller search space and therefore efficiency.

heading: 4.2 GUARANTEED DATA PROGRAMMING WITH BOOTSTRAPPING ON TRAINING SET

text:
After deciding the architecture and training hyperparameters of weak labeling functions, Mako kicks off weak labeler training and ensembling of generative model πi for each task Ti. For the training process, we are inspired by Snuba (Varma & Ré, 2016) due to the fact that it has a theoretical accuracy guarantee in the final generative model. Nonetheless, in order to increase variance among the labelers, Snuba trains them on different selected subsets of features. This procedure does little favor in LML, where we might encounter complex tasks in the sequence that requires the entire feature space. For instance, in image classification, excluding pixels in training may lead to a failure in capturing important feature-target relationships, especially when we want to take advantage of local connectivity of CNNs. Therefore, Mako uses bootstrapping on (Xi,L, Yi,L) and trains each labeler with a sampled subset. The bootstrapping size can be either manually given or searched as a training hyperparameter.
Besides bootstrapping on data, the rest of weak labeler generation process remains unchanged from Snuba in order to maintain its theoretical guarantee. Snuba has such a guarantee because it checks an exit condition on whether the committed labelers have labeled sufficient number of data points in Xi,L with acceptable confidence. If so, these labelers guarantee that the final generative model will have a learned accuracy on Xi,L close to the labeling accuracy on Xi,U . Formally, this guarantee can be stated as Proposition 1.
Proposition 1 (Theoretical Guarantee of Snuba): Given h committed weak labelers, denote the empirical accuracies of all committed weak labelers on Xi,L as a vector ai,L,w. The generative
model training outputs learned accuracies of these labelers on Xi,L as ai,L,g before ensembling. Moreover, the unknown true accuracies of the labelers on Xi,U after generative model training are denoted as ai,U,g , with ai,L,w, ai,L,g , ai,U,g ∈ Rh. We have a measured error ||ai,L,w−ai,L,g||∞ ≤ . Then, if each labeler labels a minimum of
d ≥ 1 2(γ − )2 log (2h2 δ ) (9)
data points in Xi,L with above some given confidence threshold ν for all iterations, we can guarantee that ||ai,U,g − ai,L,g||∞ < γ for all iterations with probability 1− δ. The proof of Proposition 1 from the original Snuba paper is included in Appendix A. We would like to show that our bootstrapping technique maintains this guarantee, as in Proposition 2.
Proposition 2 (Theoretical Guarantee of Mako Weak Labeler Generation): Despite the modifications from Snuba, the Mako weak labeler generation process satisfies the theoretical guarantees described in Proposition 1.
Proof of Proposition 2: Although our weak labelers are generated with (1) different model architectures and (2) sampling by bootstrapping on data instead of features, it still satisfies the definition of weak heuristics required by Snuba. That is, a function f : Xi 7→ Yi ∪ {abstain}, where abstain is a special label assigned to data points with a confidence lower than the threshold ν.
Consequently, by Proposition 2, if Mako checks the same theoretical exit condition at each iteration, the final generative model satisfies the same theoretical guarantee as in Snuba. The hyperparameter search described in 4.1 can be understood as looking for labelers with high ai,L,w. Based on this guarantee, we will have ||ai,U,g − ai,L,w||∞ ≤ + γ with probability 1 − δ, and hence we can probablistically achieve high labeling accuracy ai,U,g .
The weak labeling functions are then used to label both Xi,L and Xi,U and the labels are input for the training of generative model πi. We label Xi,L as well for confidence calibration, which will be explained in the following subsection.

heading: 4.3 CONFIDENCE CALIBRATION AND THRESHOLDING

text:
Considering the variability and complexity of LML tasks, we believe the generative model labels can be further improved to approach the ground truth. Therefore, Mako takes an extra step to adjust the trained generative model πi by confidence calibration on the produced logits on Xi,U .
Confidence calibration (Guo et al., 2017) is the process to align the confidence of labeling a data point to the accuracy, which is an estimation of the probability that the data point is labeled correctly. The procedure of confidence calibration is adjusting the logits in order to minimize the expected calibration error (ECE), formalized as
min pπk,i,U
Epπk,i,U [|Pr[y π k,i,U = yk,i,U | pπk,i,U = p]− p|] (10)
where yk,i,U is the ground truth label of the k-th data point in Xi,U , yπk,i,U is its predicted label by the data programming generative model and pπk,i,U is the associated confidence. However, since the ground truth labels ofXi,U is unknown, this approach is infeasible. This is the reason for training the generative model under the supervision of weak labels on both Xi,U and Xi,L. The model is hence expected to have the similar ECE on labeled and unlabeled data. Mako then performs temperature scaling (Platt, 1999) to minimize ECE on Xi,L, and then apply the same temperature on Xi,U to adjust the logits.
After calibration, there could still exist data points labeled with low confidence. We then threshold Xi,U with a confidence of 1/nclasses + β for some small positive β. For example, in a 10-way classification problem, pick β = 0.01. We only keep the subset of Xi,U with calibrated confidence ≥ 0.1 + 0.01 = 0.11. Denote this kept portion of unlabeled data and labels as (Xi,U,c, Y πi,U,c).

heading: 4.4 LML TASK TRAINING AND EVALUATION

text:
Finally, Xi,L, Yi,L, Xi,U,c and Y πi,U,c will be input into the mounted LML tool for the training of task Ti. The evaluation of the current model will be performed on all the hold-out testing data set (Xtest,1, Ytest,1), . . . , (Xtest,i, Ytest,i).
Mako does not alter the internal procedures of the LML tool. Instead, it generates labels for unlabeled data and then feeds it to the LML tool as a black box. This design enables high modularity and the LML tool can be easily replaced. In the experiment section, we will demonstrate Mako’s performance when mounting on various of LML paradigms such as DF-CNN, DEN and TF. This design also imposes no additional knowledge space storage in LML.

heading: 5 EXPERIMENTS

heading: 5.1 DATASETS AND LML TASK SEQUENCES

text:
We evaluate Mako on LML task sequences generated from 3 commonly-used image classification datasets: MNIST (LeCun & Cortes, 2010), CIFAR-10 and CIFAR-100 (Krizhevsky, 2009).
We mount Mako on existing supervised LML tools: DF-CNN, and TF (Lee et al., 2019; Bulat et al., 2020) to enable semi-supervised learning, and compare the performance to supervised LML on labeled data only as well as all data fully labeled. The task sequences are:
1. Binary MNIST: for each task, pick classes 0 vs 1, 0 vs 2, ..., 8 vs 9, with 45 tasks in total. 2. Binary CIFAR-10: same construction as binary MNIST.
Additionally, we compare Mako-mounted supervised LML tools to existing semi-supervised LML: CNNL, ORDisCo, and DistillMatch (Baucum et al., 2017; Wang et al., 2021; Smith et al., 2021). We generate the same task sequences as in their papers:
3. 10-way CIFAR-10: the entire CIFAR-10 as one task. 4. 5-way CIFAR-100: for each task, pick each superclass in CIFAR-100, with 20 tasks in total. 5. 5-way MNIST: for each task, pick classes 0-4 and 5-9 in MNIST, with 2 tasks in total.
Details of the tasks such as data splits, hyperparameters searched and labeling accuracy are explained in Appendix B.

heading: 5.2 COMPARISON TO SUPERVISED LML

text:
For each task, data is split into a labeled training set, an unlabeled training set and a hold-out test set. The details of data split and weak labeler models searched are included in Appendix B.
Table 1 and 2 summarize the performance of LML methods according to the amount of training data: L standing for the labeled training set and U with number denoting the number of instances in the unlabeled training set used during training of each task. These tables show peak per-task accuracy, final accuracy and catastrophic forgetting ratio up to the last task (Eqn. 6, 7 and 8, respectively). Additionally, we trained the LML methods on the same data with true labels instead of the Makogenerated labels to quantify the quality of the generated labels. LML methods achieve better peak
per-task accuracy as more Mako-labeled data is provided for training. This shows that Mako is able to generate useful labels for training while the current task, and especially data distribution, keeps changing in the lifelong learning setting. Training with Mako labels has no significant improvement in final accuracy, but, compared to LML models trained on the true data, both peak per-task accuracy and final accuracy are at least 97% of the counterparts. Learning curves for each experiment are shown in Appendix C.

heading: 5.3 COMPARISON TO SEMI-SUPERVISED LML

text:
As discussed in Section 2, there is little prior work in semi-supervised LML settings. We identify three approaches for comparison: CNNL, ORDisCo, and DistillMatch (Baucum et al., 2017; Wang et al., 2021; Smith et al., 2021). Each baseline approach contains multiple modules and networks which each require their own tuning; to enable fair comparisons, we replicate the experimental conditions (data set, amount of labeled vs. unlabeled data, task definitions, and network architecture) and compare our approach to the best results reported in each baseline’s original publication. Specifically, we replicate the instance-incremental learning experiments of CNNL on MNIST and CIFAR10, and the class-incremental learning experiments of ORDisCo and DistillMatch on CIFAR-10 and CIFAR-100, respectively. We briefly describe each experiment below; for more details, see Appendix B for data splits and the original publications for full experimental descriptions.
Instance-Incremental Experiments. We compare semi-supervised learning using Mako in an instance-incremental setting (i.e., where all tasks are present at every epoch, but subsequent epochs contain different batches of unlabeled data), using an identical two-convolutional-layer CNN as described in (Baucum et al., 2017). The MNIST experiment uses a labeled data set of 150 images, with 1000 unlabeled images introduced in each of 30 instance-incremental batches. The CIFAR10 experiment uses a labeled data set of 2000 samples, with subsequent batches of 1000 unlabeled images. Each Mako experiment was run over 10 random seeds. For additional context, we include the performance of the same network trained in the instance-incremental setting where all data is labeled with the ground truth, representing an upper bound on semi-supervised performance. As shown in Table 3, using Mako labels in place of CNNL’s semi-supervised labeler results in comparable classification accuracy with better sample efficiency (MNIST), or strictly higher classification accuracy (CIFAR-10). Learning curves for each experiment are shown in Appendix D.
Class-Incremental Experiments. We compare state-of-the-art LML methods (DF-CNN, DEN, and TF (Lee et al., 2019; Yoon et al., 2018; Bulat et al., 2020)) using Mako labels to perform semisupervised learning in a class-incremental setting (i.e., the model is sequentially presented with tasks containing new sets of classes). For all experiments below, each Mako-enabled approach was run
over 10 random seeds, and we also include the performance of the same using all ground truth labels. We first compare Mako to ORDisCo over five binary CIFAR-10 tasks using 400 labeled instances, with the remaining data unlabeled. We note that we could not directly replicate the ORDisCo classification network architecture due to a lack of details in the original publication, but instead show that using Mako labels achieve a higher total classification accuracy with DF-CNN and TF using a significantly smaller network (4 convolutional layers for the Mako approaches, compared to ORDisCo’s 9 convolutional layers), shown in Table 4. Additionally, we compare Mako to DistillMatch over the 5-way CIFAR-100 using 20% labeled data, replicating DistillMatch’s ParentClass task. As shown in Table 4, all of the LML methods enabled by Mako labeling meet or exceed DistillMatch’s performance over the learning task. Learning curves for each experiment are shown in Appendix D.

heading: 6 CONCLUSION AND FUTURE WORK

text:
In this paper, we identified the challenge that collecting task-level labeled data for LML is expensive. We address this challenge with data programming, where labels are automatically generated, and implemented the Mako framework that can be mounted on top of existing LML tools. Mako takes in a limited number of labeled data and an unlimited number of unlabeled data, aiming to minimize the performance gap to using the same data but fully labeled. We demonstrated Mako can achieve sufficiently high accuracy per task as well as resistance to catastrophic forgetting, while costing no additional knowledge base storage, over a set of common image classification LML task sequences.
Future work on this topic can consider how to better resolve the issue of expensive labels at individual LML tasks. This includes how to extend Mako to a larger variety of LML task sequences. For instance, what alternative methods can be used for labeler hyperparameter tuning other than searching, what prior knowledge of tasks could assist automatic labeling, and how should the efficiencycapability trade-off of different models be balanced. Outside of the Mako framework, alternative solutions can modify existing LML tools directly, compromising a certain degree of modularity while possibly improving the overall LML performance.
Another interesting future direction is to consider the scenario where the labeled data and unlabeled data input per task are drawn from different distributions. This can be enabled by optimal transport theory, specifically the minimization of Sinkhorn distance between two distributions (Cuturi, 2013). Ideally, this approach could allow unlabeled data from other datasets to assist LML, resolving the issue of not only expensive labels but also expensive data collection.

heading: 7 REPRODUCIBILITY STATEMENT

text: We encourage researchers to replicate our experiments. As discussed in Section 4, we have provided the step-by-step explanation of Mako workflow. We have included more experiment details in Appendix B for convenience. Additionally, we pushed a sample code to an anonymous GitHub repository (https://github.com/mako-anon/mako). All readers are welcomed to pull our code and execute Mako on the example data themselves.

heading: APPENDIX A SNUBA THEORETICAL GUARANTEE AND PROOF

text:
Proposition 1 in Section 4.2 and its proof are given by the original Snuba paper (Varma & Ré, 2016). We adapt their notations to our paper to support the propositions in Section 4.2 on an arbitrary LML task Ti. For convenience, we remove the subscript i in all notations.
Proof of Proposition 1: First, the probability of the l∞ error between the labeling accuracies of the generative model on XU and XL is greater than or equal to γ can be bounded by the following triangular inequality, with the empirical accuracy of one weak labeler in the middle.
Pr[||aU,g − aL,g||∞ ≥ γ] ≤ Pr[||aU,g − aL,w||∞ + ||aL,w − aL,g||∞ ≥ γ] ≤ Pr[||aU,g − aL,w||∞ + ≥ γ]
(11)
Then, since we have h weak labelers, the following union bound holds for an individual labeler j in the committed set and its scalar accuracy.
Pr[||aU,g − aL,w||∞ + ≥ γ] ≤ h∑ j=1 Pr[|aU,g,j − aL,w,j |+ ≥ γ] (12)
In XL, suppose there are dj data points not labeled as abstain by labeler j, the definition of the empirical accuracy of weak labeler j is
aL,w,j = 1
dj ∑ k 1(yk = ŷj,k) (13)
where yk is the ground truth label of data point k in the non-abstain subset and ˆyj,k is the label given by heuristic j. By combining Equations 12 and 13, and using Hoeffding’s inequality on the independent data points, we can get
Pr[||aU,g − aL,w||∞ ≥ γ] = Pr[||aU,g − aL,w||∞+ ≥ γ − ]
≤ h∑ j=1 Pr[|aU,g,j − aL,w,j | ≥ γ − ]
= h∑ j=1 Pr [ |aU,g,j − 1 dj ∑ k 1(yk = ŷj,k|) ≥ γ − ] ≤ h∑ j=1 2 exp(−2(γ − )2dj)
≤ 2h exp(−2(γ − )2 min(d1, . . . , dh))
(14)
Equation 14 bounds the probability of Snuba’s failure to keep ||aU,g − aL,g||∞ < γ in one iteration. Assume without loss of generality that we commit one more weak labeler per iteration, so for the all h iterations, we apply union bound again:
Pr[||aU,g − aL,w||∞+ ≥ γ − for any iteration] ≤ h∑ j=1 Pr[||aU,g − aL,w||∞+ ≥ γ − for one iteration]
≤ 2h2 exp(−2(γ − )2 min(d1, . . . , dh))
(15)
Therefore, if we denote this probability of failure in any iteration as δ, we have the bound δ ≤ 2h2 exp(−2(γ − )2 min(d1, . . . , dh)) (16) and thus obtain Equation 9 by letting d = min(d1, . . . , dh).

heading: APPENDIX B WEAK LABELER MODEL HYPERPARAMETERS IN

text:
EXPERIMENTS
The LML task configurations are listed in Table 5 for the convenience of replicating our procedure. Because even after hyperparameter search (Section 4.1), there are still differences in the architectures and training hyperparameters throughout a single LML sequence, we have provided shrunken search spaces in weak labeler architecture and training hyperparameters.
For example, to re-create our binary MNIST LML tasks, one needs to first arrange the 45 tasks as 0 vs 1, 0 vs 2, ..., 8 vs 9. Then, split the labeled training data, unlabeled training data and testing
data into 120/11880/2000. All the data splits have balanced classes. Finally, perform our procedure described in Section 4, starting from the hyperparameter search in the shrunken search space.
Figure 2 illustrates the searched architectures. The search spaces were inspired by various previous works on CNN designs (Lecun et al., 1998; He et al., 2016). Nonetheless, the final architectures are much smaller since we need fast training of multiple weak labelers. The notations of the figures are: out c: output channels/number of filters, k: size (width and height) of a filter, p: padding and s: stride.
Figure 3 shows the labeling accuracies of the Mako-labeled data input into LML.

heading: APPENDIX C ADDITIONAL SUPERVISED LML EXPERIMENT ANALYSIS

text: We visualize peak per-task accuracy and final accuracy of supervised LML experiments (Figure 4) and learning curve of final accuracies in these experiments (Figure 5), summarized in Table 1 and 2. In these plots, we used the same notation L and U of the main text to specify the training data setting, except TrueU denoting the case trained on the same instances of U but using the true labels instead.

heading: APPENDIX D ADDITIONAL SEMI-SUPERVISED LML EXPERIMENT

text:
ANALYSIS
We include learning curves for each of the instance-incremental semi-supervised LML experiments in Figure 6 and each of the class-incremental semi-supervised LML experiments in Figure 7. All training curves show final accuracy up to task i as defined in Equation 3, where task i is the current task being trained. For easier tasks with high labeling accuracy, such as CIFAR-10, the Makoenabled semi-supervised LML methods perform similarly to the equivalent supervised fully-labeled task sequence. Otherwise, the Mako-enabled semi-supervised methods approach fully supervised performance.
We additionally analyze the class-incremental semi-supervised LML baseline experiments for catastrophic forgetting, using the catastrophic forgetting ratio defined in Equation 4. Catastrophic forgetting measures are not available for the baseline methods ORDisCo and DistillMatch as they were not reported in the original publications. The results are shown in Table 6.
For a further breakdown of results, we include task-specific performance measures for all of the semi-supervised LML experiments in Tables 7, 8, 9, and 10.

title: MAKO: SEMI-SUPERVISED CONTINUAL LEARNING WITH MINIMAL LABELED DATA VIA DATA PROGRAM- MING