Communication-Efficient and Drift-Robust Federated Learning via Elastic Net
Authors: Seonhyeong Kim
Jiheon Woo
Daewon Seo
Yongjune Kim
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated learning
Data heterogeneity
Optimization

Abstract: Federated learning (FL) is a distributed method to train a global model over a set of local clients while keeping data localized, which reduces risks of privacy and security. FL framework faces important challenges including expensive communication cost and client drift problem. Leveraging the elastic net, we propose a communication-efficient and drift-robust FL framework to improve the communication efficiency and resolve the client drift problem. We repurpose two types of the elastic net regularizers (i.e., $\ell_1$ and $\ell_2$ penalties on the local model updates): (1) the $\ell_1$-norm regularizer sparsifies the local updates to enhance the communication efficiency and (2) the $\ell_2$-norm regularizer attempts to resolve the client drift problem by limiting the impact of drifting local updates due to data heterogeneity. Our framework is general; hence, it can be integrated with prior FL techniques, e.g., FedAvg, FedProx, SCAFFOLD, and FedDyn. We show that our framework effectively resolves the communication cost problem and the client drift problem simultaneously.

Under review as a conference paper at ICLR 2023
COMMUNICATION-EEFICENN AND DRIFT-ROBUST FEDERATED LEARNING VIA ELASTIC NET
Anonymous authors Paper under double-blind review
ABSTRACT
Federated learning (FL) is distributed method train global model over set of local clients while keeping data localized. It reduces the risks of privacy and security but faces important challenges including expensive communication costs and client drift issues. To address these issues, we propose FedElastieNet, a communication- efficient and drift-robust FL framework leveraging the elastic net. It repurposes two types of the elastic net regularizers (i.e., & and lz penalties on the local model updates): (1) the l fn-ormm regularizer sparsifies the local updates to reduce the communication costs and (2) the f--norm regularizer resolves the client drift problem by limiting the impact of drifting local updates due to data heterogeneity. FedElasticNet is general framework for FL; hence, without additional costs, it can be integrated into prior FL techniques, e.g., FedAvg, FedProx, SCAFFOLD, and FedDyn. We show that our framework effectively resolves the communication cost and client drift problems simultaneously.
INTRODUCTION
Federated learning (FL) is collaborative method that allows many clients contribute individually to training global model by sharing local models rather than private data. Each client has local training dataset, which it does not want to share with the global server. Instead, each client computes an update to the current global model maintained by the server, and only this update is communicated. FL significantly reduces the risks of privacy and security (McMahan al.) [017 Li al., (020aa). but it faces crucial challenges that make the federated settings distinct from other classical problems (Li
al.
2020a) such as expensive communication costs and client drift problems due to heterogeneous
local training datasets and heterogencous systems (McMahan et al.) 2017 Li ct al. 2020a Konečný
ct al. 2016a
Communicating models is critical bottleneck in FL, in particular when the federated network
comprises a massive number of devices (Bonawitz et al.) 2019 Li et al.. 2020a) Konečný et al. 2016b). In such a scenario, communication in the federated network may take longer time than that of local computation by many orders of magnitude because of limited communication bandwidth and device power (Li et al., (020a). To reduce such communication cost, several strategies have been proposed (Konečný et al., 2016bb] Li et al., (2020a). In particular, Konečný et al. (2016b) proposed several methods form structured local updates and approximate them, c.g., subsampling and quantization. Reisizadeh et al. 2020);; Xu et al. (2020) also proposed an efficient quantization method for FL to reduce the communication cost.
Also, in general, as the datasets that local clients own are heterogeneous, trained models on each local data are inconsistent with the global model that minimizes the global empirical loss (Karimireddy et al. 2020 Malinovskiy et al., 2020) Acar et al. 2021). ). This issue is referred to as the client drifi problem. In order to resolve the client drift problem, FedProx (Li et al. (2020b) added a proximal term to local objective function and regulated local model updates. Karimireddy et al. (2020) proposed SCAFFOLD algorithm that transfers both model updates and control variates to resolve the client drift problem. FedDyn (Acar et al. 2021) dynamically regularizes local objective functions resolve the client drift problem.
Unlike most prior works focusing either the communication cost problem the client drift problem, we propose a technique that effectively resolves the communication cost and client drift problems simultaneously.

---

Under review as a conference paper at ICLR 2023
FedAvg
FedProx
SCAFFOLD
Fe
FedElasticNet
Communication efficiency Robustness to heterogeneous data
A
A
x
A
x
A
Table 1: Comparison of prior methods and the proposed FedElasticNet.
Contributions In this paper, we propose FedElasticNet, a new framework for communication: efficient and drift-robust FL. repurposes the é -n-or and l norm regularizers the elastic net (Zou & Hastie 2005), by which it successfully improves (i) communication efficiency by adopting the 2--norm regularizer and (ii) robustness heterogeneous local datasets by adopting the fo-m regularizer.
FedElasticNet is a general framework; hence, it can be integrated with prior FL algorithms such as FedAvg (McMahan et al.] (017)). FedProx (Li et al., 2020b), SCAFFOLD (Karimireddy et al. 2020), and FedDyn (Acar et al. 2021) so as to resolve the client drift problem as well as the communication cost problem. Further, it incurs show that FedElasticNet enhances communication efficiency while maintaining the classification accuracy even for heterogeneous datasets, i.e., the client drift problem is resolved. Theoretically, we characterize the impact of the regularizer terms. Table [ compares the prior methods and the proposed FedElasticNet if integrated with FedDyn (Algorithm
additional costs in training. Empirically,
RELATED WORK
To address the communication cost and client drift problems, numerous approaches were proposed. Here, we describe closely related works that we consider baseline methods. The comprehensive reviews can be found in Kairouz et al. (2021) Li et al. (2020a).
FedAvg McMMaan et al. 2017) is one of the most commonly used methods. FedAvg tackles the communication bottleneck issue by performing multiple local updates before communicating to the server. It works well for homogeneous datasets across clients (McMahan et al., 2017 Karimireddy et al.
2020 but it is known that FedAvg may diverge when local datasets heterogeneous (Zhao
et al.
2018 Li et al. 2020a).
FedProx LLi et al. 2020b) addressed the data heterogeneity problem. FedProx introduces fo-morm regularizer to the local objective functions to penalize local updates that are far from the server's model and thus limit the impact of variable local updates (Li et al. (0200)). Although FedProx is more robust to heterogeneous datasets than FedAvg, the regularizer does not result in aligning the global and local stationary points (Acar al. 202T). T). Also, note that FedProx does not improve communication efficiency compared to that of FedAvg.
SCAFFOLD (Karimireddy et 2020 defined client drift that the model created by aggregating local models and the optimal global model is inconsistent because of heterogeneous local datasets. SCAFFOLD communicates the trained local models and the clients' control variates so as to resolve the client drift problem. Hence, SCAFFOLD requires twice the communication cost compared to other FL algorithms.
FedDyn (Acar et al., 2021) dynamically updates its local regularizers at each round to ensure that the local clients' optima are asymptotically consistent with stationary points of the global empirical loss. Unlike SCAFFOLD, FedDyn resolves the client drift problem without incurring additional communication costs. However, FedDyn's communication cost is not improved compared to FedAvg and FedProx
Zou & Hastie (2005) proposed the elastic net to encourage the grouping effect, in other words, to encourage strongly correlated covariates be in out of the model description together (Hu et al.) 2018). Initially, the elastic net was proposed to overcome the limitations of Lasso (Tibshirani 1996) imposing foomm penalty on the model parameters. For instance of linear least square problem,
2

---

Under review as a conference paper at ICLR 2023
the objective of Lasso is to solve
min ly x011 + A ||0|]
(I)
where y is the outcome and X is the covariate matrix. Lasso performs both variable selection and regularization to enhance the prediction accuracy and interpretability of the resulting model. However, has some limitations, especially for high-dimensional models. If a group of variables is highly correlated, then Lasso tends to select only selected (Zou & Hastie, 2005). The elastic net overcomes these limitations by adding an fo-m penalty. The objective of the elastic net is to solve
variable from the group and does not which one
A2 10012 + 1101
min lly X
The elastic net simultaneously enables automatic variable selection and continuous shrinkage by the & --nrm regularizer and enables to select groups correlated variables by its f2-norm regularizer (Zou & Hastie 2005). We will leverage the elastic net approach to resolve the critical problems of FL: expensive communication cost and client drift problems.
PROPOSED METHOD: FEDELASTICNET
We assume that m local clients communicate with the global server. For the kthh client (where k E [ml) participating in each training round, we assume that training data feature x E X and its corresponding label y y are drawn IID from a device-indexed joint distribution, i.e. (2r, v) Ps (Acar et al. 2021 The objective is to find
arg min OER
R
= m
Σ Lx (0) kE(m)
where LA -0)= Ee~ 14 (0; (z, v))l is the local risk of the kth clients over possibly heterogeneous data distributions Ps. Also, represents the model parameters and 4 (-) is loss function such as cross entropy (Acar et al. 2021).
FedElasticNet The proposed method (FedElasticNet) leverages the elastic net approach to resolve the communication cost and client drift problems. We introduce the & -oom and f2-norm penalties on the local updates: In each round E (T), the kth local client attempts to find 0% by solving the following optimization problem:
A2
8 arg min La (0)
0
0r 10- A1
8¹ 8'-1
where 0²-1 denotes the global model received from the server. Then, it transmits the difference Ai. 0% 0²~1 to the server.
Inspired by the elastic net, we introduce two types of regularizers for local objective functions; however, each of them works in different way so as to resolve each of the two FL problems: the communication cost and client drift problems. First, the fn-norm regularizer resolves the client drift problem by limiting the impact of variable local updates as in FedProx (Li et al.) 2020b). FedDyn (Acar et al. 2021) also adopts the f2-mo regularizer to control the client drift.
Second, the é norm regularizer attempts to sparsify the local updates A - 0- We consider two ways of measuring communication cost: One is the number of nonzero elements in A (Yoon) al. 2021 Jeong et al. 2022), which the -norm sparsifies. 'he other is the (Shannon) entropy since is the theoretical lower bound on the data compression (Cover Thomas 2006).. We demonstrate effectively reduce the number of nonzero elements as well as the entropy in Section 4 To boost sparseness Af. = 0% 0 we sent (i = [x) < where A (i) denotes the ith element of A.. The parameter is chosen in range that does not affect classification accuracy.
that the fn-nrrm penalty on the local updates
Our FedElasticNet approach can be integrated into existing FL algorithms such as FedAvg (McMahan cet al. 2017). SCAFFOLD (Karimireddy et al.) 2020), and FedDyn (Acar et al. 2021) without additional costs, which will be described in the following subsections.
3

---

Under review as a conference paper at ICLR 2023
Algorithm FedElasticNet for FedAvg & FedProx
Input: T, T, A
0, X2
1: for each round = 1, 2.... T do
2: Sample devices P. - [m] and transmit 6t each selected local client
3:
for each local client & E Pe do in parallel
4:
Set 8
arg min L3 (6) + 2/2 ||e 0- X1
-r '11
5: Transmit A = 0 g to the global server
6: end for
7: Set 0f = 0t-1 + ENEP. A
8:
end for
Algorithm 2 FedElasticNet for SCAFFOLD
Input: T, T000, A > 0, X2 > 0, global step size ng. and local step size T)
1: for each round
2, ..., T do
2: Sample devices P. C [m]] and transmit 0t-1 and c² to each selected device
3:
for each device k E P, do in parallel
4:
Initialize local model 0% = 6
5: for b 1,... B do
6:
Compute mini-batch gradient V (0)) 0f < 0g 1n1 (V (0))
7:
ch 1-1 ct-1
+ >2 - -00-- + Aisign(Of 01-1))
8:
end for
9:
Set of
c 1-1 c² + 1 (8--1 0%
Byj
10: Transmit A = 0% -0-- 0h-1 and Dcı ch Ch
1-1
to the global server
end for
12: Set H = g + to EkEP. DB ΣkEP, Ack m
P:
13: Set c² 11 + 1
14:
end for
3.1 FEDELASTICNET FOR FEDAVG & FEDPROX (FEDAVG & FEDPROX ELASTIC NET)
Our FedElasticNet be applied to FedAvg (McMahan et al. 2017) by adding two regularizers the local updates, which resolves the client drift problem and the communication cost problem. As shown in Algorithm the local client minimizes the local objective function (4) In Step 7, and mg denote the total numbers of data points of all clients and the data points of the kth client, respectively.
It is worth mentioning that FedProx uses the 2--norm regularizer to address the data and system heterogeneities (Li et al., (020b). By adding the ---norm regularizer, we can sparsify the local updates of FedProx and thus effectively reduce the communication cost. Notice that Algorithm [ can be viewed as the integration of FedProx and FedElasticNet.
3.2 FEDELASTICNET FOR SCAFFOLD (SCAFFOLD + ELASTIC NET)
In SCAFFOLD, each client computes the following mini-batch gradient V (+ and control variate ck (Karimireddy et al. 2020):
0% 0% 1p V LE (0%) dt- + +
(5)
& + c 1-1 c
(0' -6)).
(6)
Bm:
where n is the local step size and B is the number of mini-batches at each round. This control variate makes the local parameters of updated in the direction of the global optimum rather than each local optimum, which effectively resolves the client drift problem. However, SCAFFOLD incurs twice
much communication cost since it should communicate the local update A 0 gt-1 and the control variate Ac₃ ct dt1 which are of the same dimension.
In order to reduce the communication cost of SCAFFOLD, we apply our FedElasticNet framework. In the proposed algorithm (see Algorithm 2, each local client computes the following mini-batch
4

---

Under review as a conference paper at ICLR 2023
gradient instead of 5
0 - 8% LV (0) + 22 - 0 A0 - 1))
where A sigig g 0² corresponds to the gradient & norm regularizer \1 - 0 1 This --rmr regularizer sparsifies the local update D = 0f 0f= hence, reduces the communication cost. Since the control variate already addresses the client drift problem, we can remove the norm regularizer X2 small value.
3.3 FRDELASTICNET FOR FEDDYN (FEDDYN + ELASTIC NET)
In FedDyn, each local client optimizes the following local objective, which is the sum of its empirical loss and penalized risk function:
arg min L (0) (O
A2
10 0" 112
(8)
where the penalized risk is dynamically updated so as to satisfy the following first-order condition for local optima:
L (0 Lx + -
This first-order condition shows that the stationary points of the local objective function are consistent with the server model (Acar et al. 2021). That is, the client drift is resolved. However, FedDyn makes no difference from FedAvg and FedProx in communication costs.
By integrating FedElasticNet and FedDyn, we can effectively reduce the communication cost of FedDyn well. In the proposed method (i.e., FedElasticNet for FedDyn), each local client optimizes the following local empirical objective:
1 = arg min L (0) - (V ),0)
10 1' + A1 0 0- 11
(10)
which is the sum of (8) and the additional f--norm penalty on the local updates. The corresponding first-order condition is given by
(o)( - VL
>2 0²-1) + sign - =0
(11)
Notice that the stationary points of the local objective function are consistent with the server model in 99. If 0% # gt-1 (i.c., sign(ff, or 1- 1). then the first-order condition is
(Lx(0)) L (0t A2 0² =
(12)
where A is a vectorized one. Our empirical results show that the optimized hyperparameter is A1 10-4 10-6 and the impact of +\1 in (12) would be negligible. Hence, the proposed FedElasticNet for FedDyn resolves the client drift problem. Further, the local update A = 0% - f--1
sparse due the -nomm regularizer, which effectively reduces the communication cost the same time. The detailed algorithm described in Algorithm 3
Algorithm FedElastieNet for FedDyn
Input: T, 00 A > A2 > 0, h = 0, VL (80) 0.
for each round 1, ..., do
2: Sample devices P: C [m]] and transmit (t-1 to each selected device
3:
for each device E P; do in parallel
4: Set 0% arg min L3 (0) (V (()-)))))) 8) + 2 1 gr- 112 + A1 ||0 0² 0r-11l,
5: Set V L (0
V T. (0)
A2 (0f 0C-1) Ansign (0) - -1-
6: Transmit A 0g g-~1 to the global server
7:
end for
8:
for each device & P. do in parallel
9:
Set 8% 8:_ and V La (0%)
LL (0%-1)
10:
end for
11:
Set l = ht-11 d Σ
ΣtEp, (0) -0-
A1 m
ExEp, sign(Of 01-1)
12:
Set 0- P.T ΣkEP, 0g L
13:
end for
5

---

Under review as a conference paper at ICLR 2023
Convergence Analysis We provide a convergence analysis FedElasticNet for FedDyn (Algo- rithm B).
Theorem 3.1. Assume that the clients are uniformly randomly selected at each round and the local loss functions are convex and B-smooth. Then Algorithm 3 satisfies the following inequality:
E
R
1
Σ 7 1=0
RR(O)
S
1 1
(B1l?"
0.12 xxCo) + K²
.2d
T K0
K0
T
2
7 1-1
0.: m
Σ
E
Blsign 0% 0² 00-111 (13)
T X2
1=1
kE(m]
where 0. = arg ming R(0), P = Iptl 7¹ = p Ep, P. 0g d = dim (0), k p A2 15- 25,87 Ko
10m 1 A=+
Aa
2. x3 -50/2
X/ 25/52
K X x
26,
= R
2m'
P.
Co = m
1
>kE(m) L (82) - VL (0+) and
22 0 0 1| \1 |00 0 -0'-01111 1 4k E [m].
8 arg min La (0) V L (0% ) 0) +
2
Theorem 3.1 provides a convergence rate of FedElasticNet for FedDyn. If + 0o, the first term of 13) converges to O at the speed of (1)T)). The second and the third terms of (13) are additional penalty terms caused by the f-oor regularizer. The second term is negligible constant in the range of hyperparameters of our interest. Considering the last term, notice that the summand at each I includes the expected average of sign vectors where each element is #1. If a coordinate of the sign vectors across clients is viewed as an IID realization of Bern()), it can be thought of as a small value with high probability by the concentration property (see Appendix B.3 In addition, -d - 0. characterizes how much the average of local models deviates from the globally optimal model, which tends to be small as training proceeds. Therefore, the effect of both additional terms is negligible.
4 EXPERIMENTS
In this section, we evaluate the proposed FedElasticNet on benchmark datasets for various FL scenarios. In particular, FedElasticNet is integrated with prior methods including FedProx (Li et al.) 2020b), SCAFFOLD (Karimireddy et al. 22020), and FedDyn (Acar et al. 2021). The experimental results show that FedElasticNet effectively enhances communication efficieccy while maintaining classification accuracy and resolving the client drift problem. We observe that the integration of FedElasticNet and FedDyn (Algorithm 3) achieves the best performance.
We use the same benchmark datasets as prior works. The evaluated datasets include MNIST (LeCun et al. [1988, subset of EMNIST (Cohen et al. 2017 EMNIST-L), CIFAR- 10, CIFAR-100 (Krizhevsky & Hinton| 2009), and Shakespeare (Shakespeare) 1914). The IID split is generated by randomly assigning datapoint to the local clients. The Dirichlet distribution is used on the label ratios to ensure uneven label distributions among local clients for non-IID splits as in Zhao eet al. (2018); Acar et al. (2021). For the uneven label distributions among 100 experimental devices, the experiments are performed by using the Dirichlet parameters of 0.3 and 0.6, and the number of data points obtained by the lognormal distribution as in Acar et al. (2021). The data imbalance is 2021).
Experimental Sctup
controlled by varying the variance of the lognormal distribution (Acar et al.
We use the same neural network models of FedDyn experiments (Acar et al.
2021). For MNIST and EMNIST-L, fully connected neural network architectures with 2 hidden layers are used. The numbers of neurons in the layers are 200 and 100, respectively (Acar al. (02II) Remark that the model used for MNIST dataset is the same as in Acar et al. (2021 McMahan et al. (2017). For CIFAR-10 and CIFAR-100 datasets, we use a CNN model consisting of convolutional layers with 64 5 x filters followed by 2 fully connected layers with 394 and 192 neurons and a softmax layer. For the next character prediction task for Shakespeare, we use a stacked LSTM as in Acar et al. (2021).
For MNIST, EMNIST-L, CIFARIO, and CIFAR 100 datasets, we evaluate three cases: IID, non-III with Dirichlet (.6), and non- with Dirichlet (.3). Shakespeare datasets are evaluated for IID and non-IID cases as in Acar et al. (2021). We use the batch size of 10 for the MNIST dataset, 50 for 10, CIFAR-ION I00, and EMNIST-L datasets, and 20 for the Shakespeare dataset. We optimize the hyperparameters depending on the evaluated datasets: learning rates, X2, and X1-

---

Under review as a conference paper at ICLR 2023
Dataset
Rounds
FedProx
Algorithm/ |
SCAFFOLD
Algorithm
FedDyn
Algorithm
CIFAR-10
200
163.82
124.56
327.64
313.04
163.82
34.23
500
413.37
249.26
826,74
803.33
413.37
132.95
ID
MNIST
100
20.3
7.51
40.58
36.98
20.3
EMNIST-L
200
18.4
11.23
36.78
34.90
18.4
2.12
Shakespeare
100
1.99
1.93
3.32
3.31
1,99
1.28
CIFAR-10
200
163.82
I16.96
327.64
310.31
163.82
29,96
CIFAR-
500
247.87
826.74
798.21
413.37
Dirichlet (.6)
MIIST
100
20.3
6.66
40.58
35.20
20.3
2.55
EMNIST-L
200
18.4
11.18
36.78
34.45
18.4
2.05
CIFAR-10
200
163.82
112.1
527.64
308.15
163.82
26,99
CIFAR-100
500
413.37
255.97
826.74 74
804,47
413.37
124.02
Dirichlet (.3)
MNIST
100
20,3
6.49
40.58
34.95
20.3
2.53
E.NISTL
200
18.4
11.29
36.78
34,22
18.4
2.07
Shakespeare
Table 2: Number of non-zero elements cumulated over the all round simulated with 10% client participation for IID and non-IID settings in FL scenarios. The non-IID settings of MNIST, EMNIST- I., CIFAR-10, and CIFAR-10 datasets are created with the Dirichlet distribution of labels owned by the client. Algorithm| D is FedElasticNet for FedProx, Algorithm ii FedElasticNet for SCAFFOLD, and Algorithm iis FedElasticNet for FedDyn. The unit of the cumulative number of elements is 107.
Dataset
Rounds
FedProx
Algorithm
SCAFFOLD
Algorithm
Fyd
Algorithm
CIFAR-JŌ
200
586.42
232.77
685.17
236.76
639,59 (221
140.71
CIFAR-100
500
1712.84
470.78
2225 98
1173.01
1964.63 (511.14)
423.53
IID
MITST
100
266.26
47.29
286.88
83.51
308.27 (27.76)
24.76
EMNIST-L
200
657.64
166.07
764.39
344.94
704.57 (132 50)
96.37
Shakespeare
100
646.33
403.63
520.60
226.68
576. (348.11
225.44
CIFAR 10
200
564.57
203.61
663.23
198.53
616.69 (197.62)
121.97
Dirichlet (.6)
CIEAR
1119.91
(478.60)
398.87
MINIST
100
249 63
45.51
293.22
75.57
304.00 (26. 75)
21.24
EMNIST-L
200
646
163.24
755.75
347.31
704.63 (134.31)
89.92
CIFAR-10
200
550.15
187.01
636.90
115.26
602.80 (122001880.00 (180.99)
108.69
CIFAR-TO0
428.77
2170.14
1078.97
1937.09 (463 67)
382.44
Dirichlet (.3)
MNIST
100
244.49
45.24
291.88
73.12
300.76 (26.71)
19.03
EMNIST-
200
636.21
162.57
747.72
328.21
700.38 (128.34)
91.55
Non-IID
Shakespeare
100
593.21
440.99
628.32
470.22
619.1 (348.11)
419.99
Table Cumulative entropy values of transmitted bits with 10% client participation for IID and non-
IID settings in FL scenarios. The non-llD settings of MNIST, EMNIST-L, CIFAR-10, 10, and CIFAR-100
datasets are created with the Dirichlet distribution of labels owned by the client. Algorithm is FedElasticNet for FedProx, Algorithm 2 FedElasticNet for SCAFFOLD, and Algorithm 3 FedElasticNet for FedDyn. The left-side numbers of FedDyn are the entropy values when the local models of transmitted and the right-side numbers in parentheses are the entropy values when the local updates A 0 00-1 are transmitted.
Evaluation of Methods We compare the baseline methods (FedProx, SCAFFOLD, and FedDyn) and the proposed FedElasticNet integrations (Algorithms D and B respectively. We evaluate the communication cost and classification accuracy for non-lll settings of the prior methods and the proposed methods. The robustness of the client drift problem is measured by the classification accuracy of non-lII settings.
We report the communication costs in ways: (i) the number of nonzero elements in transmitted values as in (Yoon et al. 2021 Jeong et al. 2021) and (ii) the Shannon entropy of transmitted bits. Note that the Shannon entropy the theoretical limit of data compression (Cover Thomas 2006), which can be achieved by practical algorithms; for instance, Han et al. (2016) used Huffman coding for model compression. We calculate the entropy of discretized values with the bin size of 0.01. Note that the transmitted values are not discretized in FL., and only the discretization is considered to calculate the entropy. The lossy compression schemes (e.g., scalar quantization, vector quantization, etc.) have not been considered since they include several implementational issues which are beyond our research scope.
Table reports the number of non-zero elements of the baseline methods with/without FedElasticNet. Basically, the communication costs per round FedProx and FedDyn are the same; SCAFFOLD suffers from the doubled communication cost because of the control variates. The proposed FedElas- tieNet integrations (Algorithms I and 3) can effectively sparsify the transmitted local updates, which enhances communication efficiency.
7

---

Under review as a conference paper at ICLR 2023
Dataset
Rounds
FedProx
Algorithm
SCAFFOLD
Algorithm
Fyd
Algorithm
CIFAR-10 10
200
595. 16
151.28
875.24
252.33
680. (259.31 (239.31)
57.70
CIFAR-IO0
500
1721.53
466.21
2774.60
1068.47
2038.07 (689.24)
447.18
I1D
MINSTT
100
325 86
39.55
389.52
71.57
324.88 (20.47)
12.33
EMNIST-L
200
728.34
123.74
1018.11
263.95
797.39 (55.46) 46)
40.71
Stukespeare
100
640.69
279.51
529.05
476.81
343.32 (298.58
277.21
CIFAR
200
577.74
127.14
839.41
236.48
656,48 (223.46)
47.52
Dirichlet
CIFAR- TOU
500
1697.18
453.87
2682.15
1033.22
1974.65 (651.78)
431.54
MINIST
100
298, 99
30.94
530.72
106.08
314.64 (20. 29)
11.67
EMNIST-L
200
721
121.76
1020.32
251.65
779 (286.
40.71
CIFAR-10
200
563 563.15
105.89
806,73
214.31
635.78 (215.821188
39,58
Dirichlet (.3)
CIFAR-I00
1060.83
(627.
422.46
MINIST
100
295 80
42.94
466.65
85.06
314.96 (19.98)
12.35
EMNIST-L
40.70
Non-IID
Stukespeare
100
595.69
409.64
684.79
897.67
560.8 (316.64)
318.92
Table 4: Cumulative entropy values of transmitted bits with 100% client participation for IID and non-
IID settings in FL scenarios. The non-llI settings of MNIST, EMNIST-L, CIFAR-10, and CIFAR-100
datasets are created with the Dirichlet distribution of labels owned by the client. Algorithm T is FedElasticNet for FedProx, Algorithm is FedElasticNet for SCAFFOLD, and Algorithm 3 is
FedElasticNet for FedDyn. The left-side numbers of FedDyn are the entropy values when the local
models of are transmitted and the right-side numbers in parentheses are the entropy values when the local updates A ff f are transmitted.
In particular, the minimal communication cost is achieved when FedElasticNet integrated with FedDyn (Algorithm 3). It is because the classification accuracy is not degraded even if the transmitted values are more aggressively sparsified Algorithm 3 Fig. 2 shows the transmitted local updates A of Algorithm are sparser than FedDyn and Algorithm Hence, Algorithm (FedElasticNet for FedDyn) achieves the best communication efficiency.
MNIST accuracy
EMNIST accuracy
1.00
0.98
Test Accuracy
Teat Accuracy
00.92
0.96
0.90
0.94
0.88
0.86
0.90
100
100
175
Communication Rounds
Communication Rounds
CIFAR-10 accuracy
CIFAR-100 accuracy
0.78
0.45
Test Accuracy
0.76
Accurasy
0.72
0.35
0.70
0.66
0.25
75
100
125
150
175
200
Communication Rounds
Communication Rounds
FedProx
Algorithm 1
SCAFFOLD
Algorithm 2
Feddyn
Algorithm 3
Figure I: Classification accuracy performance evaluated in MNIST, EMNIST-L, CIFAR-10, CIFAR- 100 dataset settings (10% participation rate and Dirichlet (.3)).
Tables 3 and report the Shamnon entropy of transmitted bits for the baseline methods with/without FedFlasticNet.. The communication costs of baseline methods are effectively improved by the
8

---

Under review as a conference paper at ICLR 2023
Distribution of local updates
FedDyn
Algorichm
Algorithm
100
0
-0.010
-0.005
0.000
0.005
0.010
0.015
Figure 2: Comparison of distributions of transmitted local updates A = -0--1 (10% participation rate and Dirichlet (.3)) for CIFAR-10.
FedElasticNet approach. Algorithms and reduue the entropy compared to the their baseline methods. We note that FedElasticNet integrated with FedDyn (Algorithm 3 achieves the minimum entropy, i.e., the minimum communication cost.
For FedDyn, we evaluate the Shannon entropy values for two cases: (i) transmit the updated local models of as in Acar et al. (2021) and (ii) transmit the local updates Aj 0 - as in Algorithm 3 We observe that transmitting the local updates A instead of the local models of can reduce the Shannon entropy significantly. Hence, it is beneficial to transmit the local updates A even for FedDyn if it adopts an additional compression scheme. The numbers of nonzero elements for two cases (i.e., 0% and A are the same for FedDyn.
Fig. T shows that the FedElasticNet maintains the classification accuracy or incurs marginal degra- dation. We observe classification gap between FedProx and Algorithm for CIFAR-10 and CIFAR-100. However, the classification accuracies of FedDyn and Algorithm are almost identical in the converged regime.
In particular, Algorithm significanty reduces the Shannon entropy, which can be explained by Fig Fig 2 compares the distributions of the transmitted local updates A for FedDyn, Algorithm 2 and Algorithm
3 Because of the fı-norm penalty on the local updates, Algorithm makes sparser local updates than FedDyn. The local updates of FedDyn can be modeled by the Gaussian distribution, and the local updates of FedFllatticeet can be modeled by the non-Gaussian distribution (similar to the Laplacian distribution). It well-known that the Gaussian distribution maximizes the entropy for a given variance in information theory Cover & Thomas (2006). Hence, FedElasticNet can reduce the entropy by transforming the Gaussian distribution into the Gaussinnn one.
CONCLUSION
We proposed FedElasticNet, a general framework to improve communication efficiency and resolve the client drift problem simultaneously. We introduce two types of penalty terms on the local model updates by repurposing the classical elastic net. The -o-mr regularizer sparsifies the local model updates, which reduces the communication cost. The norm regularizer limits the impact of variable local updates to resolve the client drift problem. Importantly, our framework can be integrated with prior FI. techniques so to simultaneously resolve the communication cost problem and the client drift problem. By integrating FedFlastiiNet with FedDyn, we can achieve the best communication efficiency while maintaining classification accuracy for heterogeneous datasets.
9

---

Under review as a conference paper at ICLR 2023
REFERENCES
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based dynamic regularization. In International Conference on Learning Representations (ICLR), May 2021.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloé Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards federated learning at scale: System design. In A Talwalkar, Smith, and M Zaharia (eds.), Proceedings of Machine Learning and Systems, volume 1, pp. 374-388, 2019.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: handwritten letters. In International Joint Conference on Neural Networks (IJCNN), pp. 2921-2926. 2017.
Extending mnist to
Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-Interscience, New York, 2006.
Rick Durrett. Probability: Theory and Examples. Cambridge University Press, Cambridge, UK fifth edition, 2019. doi: 10.1017/9781 108599034,
Song Han, Huizi Mao, and William J. Dally. Deep compression:
Compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representations (ICLR), volume abs/1 15 510.0, October 2016.
Jianhua Hu, Jian Huang, and Feng Qiu. A group adaptive elastic-net approach for variable selection in high- digh-dimensional linear regression. Science China Mathematics, 61(1):173 188-188,, 2018.
Wonyong Jeong, Jaehong Yoon, Eunho Yang, and Sung Ju Hwang. Federated semi-supervised learning with inter-client consistency & disjoint learning. In International Conference on Learning Representations (ICLR), 2021.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning (ICML), pp. 5132-5143, 2020.
Jakub Konečný, H. Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXiv: 201 6a.
Jakub Koneëný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492, 2016b.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, (6(11))2278-2322 1998.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization heterogeneous networks. In Proceedings of Machine Learning and Systems, volume 2, pp. 459- 2020b.
Grigory Malinovskiy, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd to local fixed-point methods for federated learning. In International Conference on Machine Learnin (ICMI). pp. 6692-6701, 2020.
10

---

Under review as a conference paper at ICLR 2023
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication efafuuication-effiientt learning of deep networks from decentralized data. In International Conference Artificial Intelligence and Statistics (AISTATS), pp. 1273-1282 PMLR, 2017.
Y. Nesterov, Lectures convex optimization, volume 137. springer, 2018. URL buttss://lin: springer. com content tttp:/pp.t..//./..... 3- 319 -199-11 91578 4 .ddf]
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A communication-effcieen federated learning method with periodic averaging and quantization. In International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108, pp. 2021-2031, August 2020.
William Shakespeare. The complete works of William Shakespeare. Humphrey Milford, Ox- ford University Press, 1914. URL httt::/wwwie http://gteeeeeerrooooggoeee/e///
1994-01-100.21
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series (Methodological), 58(1):267-288) 1996.
Jinjin Xu, Wenli Du, Yaochu Jin, Wangli He, and Ran Cheng- Ternary compression for communication-efficie federated learning. IEEE Transactions Neural Networks and Learning Systems, 2020.
Jaehong Yoon, Wonyong Jeong, Giwoong Lee, Eunho Yang, and Sung Ju Hwang. Federated continual learning with weighted inter-client transfer. In Marina Meila and Tong Zhang (eds.), International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pp. 12073-12086, 2021.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv: 1rXiv:/806.00582 2018.
Hui Zou and Trevor Hastie. Regularization and variable selection via the elastic net. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 67(2)3001-3200 2005.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 EXPERIMENT DETAILS
We provide the details our experiments. We select the datasets for our experiments, including those used in prior work on federated learning (McMahan et al., 2017 Li et al., 2020b Acar et al. (021). To fairly compare the non-IID environments, the datasets and the experimental environments are the same as those of Acar et al. (2021).
We describe the hyperparameters used in our experiments in Section We perform a grid search find the best X and used in the proposed algorithms. Each hyperparameter was selected to double the value as the performance improved. We use the same X as in Acarr et al. (202I). SCAFFOLD has the same local epoch and batch size other algorithms, and SCAFFOLD is not included in Table 4 because other hyperparameters are not required. Table 5 hyperparameters used in our experiments.
Hyperparameters.
shows the
Dataset
Algorithm
A
Ag
FedProx
Algorithm
10-6
10-4
10-3
CIFAR-10
Algorithm 2
10
0
10-4
FedDyn
10
Algorithm
10
10-2
5 10-3
FedProx
10-4
Algorithm
10-6
10-4
10-3
CIFAR-100
Algorithm
10
10-4
FedDyn
10-2
Algorithm 3 10
10-2
10-3
FedProx
10
Algorithm
10-6
10-6
10-3
MNIST
Algorithm
10-4
10-1
FedDyn
5 x 10
Algorithm 3
10
5 10
5 10
FedProx
10-4
Algorithm
10-6
10-6
10-3
EMNIST-L
Algorithm 2
10-4
0
10-1
FedDyn
4 10
Algorithm
10
10
10 3
FedProx
10-a
Algorithm
10-6
10-6
9 x 10-3
Shakespeare
Algorithm 2
10-6
0
9 10-4
FedDyn
10-2
Algorithm 3
10-6
10-2
10-2
Table 5: Hyperparameters.
A.2 REGULARIZER COEFFICIENTS
We selected λ (10-2, 2, 10-4, 10-6 10-8) to observe the impact of X the classification accuracy. We prefer larger \ to enhance communication efficiency unless the fn-mrrm regularizer does degrade the classification accuracy. Figures and 5 show the classification accuracy depending on A₁ in the CIFAR- 10 dataset with 10% participation rate and Dirichlet (.3). The unit of the cumulative number of elements 107.
In Algorithm|] | we selected A 10-6 6 to avoid degradation of classification accuracy (see Fig. 3
and maximize the sparsity of local updates. In this way, we selected the coefficient values X (See Fig 4 for Algorithm 2 and and Algorithm
12

---

Under review as a conference paper at ICLR 2023
Algorithm accuracy according value
Algorithm 1 entropy according to À value
0.75
0.0
Test Accuracy
0.65
Entropy
125
0.50
0.30
0.45
0.4
182
104
16
168
A Value
A Value
Number of non-zero elements algorithm 1 according 11 value
Number of non-zero elements
Àι Value
Figure 3: Classification accuracy and sparsity of local updates depending on a1 (Algorithm)
Algorithm 2 accuracy according
value
Algorithm 2 entropy according to òı value
0.70
Test Accuracy
0.67
Entropy
0.00
0.50
53
0.40
162
164
1e-6
164
A; Value
A Value
Number of non-zero elements algorithm according 1₃ value
Number of non-zero elements
320
310
300
290
280
270
Aι Value
Figure 4: Classification accuracy and sparsity of local updates depending on A (Algorithm)
13

---

Under review as a conference paper at ICLR 2023
Algorithm 3 accuracy according to A value
Algorithm 3 entropy according to À value
Test Arcuracy
Entropy
6.5
0.4
6.3
0.2
1n2
164
165
16:3
162
1641
1+
16
À Value
Y₁ Value
Number of non-zero elements algorithm 3 according À1 value
Number of non-zen con-zero elements
26
À Value
Figure 5: Classification accuracy and sparsity of local updates depending on Å₁ (Algorithm)
14

---

Under review as a conference paper at ICLR 2023
A.3
EMPIRICAL RESULTS CLASSIFICATION ACCURACY
MNIST Dirichlet (.6) accuracy
MNIST IID accuracy
1.00
1.00
0.98
0.98
Test Accuracy
Accuracy
0.94
0.94
0.92
0.92
0.90
0.90
20
40
100
100
Communicatiin Rounds
Communication Raunds
EMNIST-L L Dirichlet (.6) accuracy
EMNIST L IID accuracy
0.94
Test Accuracy
0.92
Accuracy
0.92
0.90
0.90
0.88
0.88
0.86
0.86
100
125
150
175
200
100
125
175 200
Communication Rounds
Communication Rounds
CIFAR 10 Dirichlet (.6) accuracy
CIFAR 10 IID accuracy
0.78
0.80
Test Accuracy
0.76
0.78
0.76
0.74
0.72
0.72
0.70
0.70
0.68
0.68
0.66
0.66
25
50
75
100
125 150
175
200
200 25
50
75
100 125
150
175
Communication Rounds
Communication Rounds
CIFAR 100 Dirichlet (.6) accuracy
CIFAR 100 IID accuracy
0.50
0.45
0.45
Test Accuracy
Accuracy
0.35
0.35
0.30
0.30
0.25
0.25
100
200
300
400
500
100
200
300
400
500
Communication Rounds
Communication Rounds
FedProx
Algorithm 1
SCAFFOLD
Algorithm 2
Feddyn
Algorithm 3
Figure 6: Classification accuracy performance evaluated in MNIST, EMNIST-L, CIFAR-10, and CIEAR- 100 datasets (10% participation rate).
15

---

Under review as a conference paper at ICLR 2023
Shakespeare Non-IID accuracy
Shakespeare accuracy
0.45
0.45
Test Accuracy
Accuracy
0.35
0.35
0.25
0.25
20
40
60
80
100
20
40
60
80
100
Communication Rounds
Communication Raunds
(a) 10% participation rate
(b) 10% participation rate
Shakespeare Non-IID accuracy
Shakespeare accuracy
0.55
0.50
0.45
Test Accuracy
0.45
Accuracy
0..40
0.10
0.35
0.35
0.30
0.25
0.25
0.20
0.20
20
40
60
80
100
20
40
100
Communication Rounds
Communication Rounds
(c) 100% participation rate
(d) 100% participation rate
FedProx
Algorithm 1
SCAFFOLD
Algorithm
Feddyn
Algorithm 3
Figure 7: Classification accuracy performance evaluated in IID Shakespeare and Non-IID -ID Shakespeare datasets.
16

---

Under review as a conference paper at ICLR 2023
MNIST Dirichlet (.3) accuracy
MNIST Dirichlet (.6)
1.00
1.00
0.98
0.98
Test Accuracy
Accuracy
0.96
0.96
0.92
0.92
20
40
60
80
100
20
40
60
80
100
Communication accuracy
Communication
EMNIST Dirichlet (.3) accuracy
1.00
0.96
0.94
Test Test Accuracy
Accuracy
0.92
0.96
0.90
0.88
0.92
0.86
0.90
100
25
50
75
100
125
150
175
200
Communication Rounds
Communication
EMNIST-L Dirichlet (.6) accuracy
EMNIST-L HID accuracy
0.96
0.96
0.94
0.94
Test Test.Acci Accuracy
Accuracy
0.92
0.92
0.90
0.90
0.88
0.88
0.86
0.86
50
75
100
125
150
175
200
25
50
200
Communication Rounds
Communication Rounds
FedProx
Algorithm 1
SCAFFOLD
Algorithm
Feddyn
Algorithm 3
Figure 8: Classification accuracy performance evaluated in MNIST, EMNIST-L datasets (100% participation rate).
17

---

Under review as a conference paper at ICLR 2023
CIFAR-10 Dirichiet (.3) accuracy
CIFAR-10 Dirichlet (.6) accuracy
0.850
0.850
0.825
Test Accuracy
0.800
Accuracy
0.800
0.775
0.775
0.750
0.750
0.725
0.725
0.700
0.700
0.675
0.675
0.650
0.650
100
125
150
175
200
50
75
100
125
150
175
200
Communication Rounds
Communication Rounds
CIFAR-10 accuracy
CIFAR-100 Dirichlet (.3) accuracy
0.850
0.825
0.50
Test Accuracy
0.800
Accuracy
0.45
0.775
0.40
0.725
0.35
0.700
0.30
0.675
0.650
100
125
150
175
200
0.25
100
200
Communication Rounds
Communication Rounds
CIFAR-100 Dirichlet (.6) accuracy
CIFAR-100 IID accuracy
0.55
0.50
0.50
0.45
Accuracy
AcctAccuracy
0.45
0.40
0.40
0.35
0.30
0.25
0.25
100
200
300
400
500
160
Communication Rounds
Communication Rounds
FedProx
Algorithm 1
SCAFFOLD
Algorithm 2
Feddyn
Algorithm 3
Figure 9: Classification accuracy performance evaluated in CIFAR-10 and CIFAR-100 datasets (100% participation rate).
18

---

Under review as a conference paper at ICLR 2023
B PROOF
We utilize some techniques in FydDyn (Acar et al. 2021
B. DEFINITION
We introduce a formal definition and properties that we will use. Definition B.0.1. A function L is B-smooth if satisfies
[v)x (=) 81|--101 - vll Vz,y.
(14)
function L convex and f-smooth, it satisfies
f (VLx(r), v) - - [x)=)) [x(v) + ? se| Vxx, y,
(15)
As consequence of the convexity and smoothness, the following property holds (Nesterov 2018 Theorem 2.1.5):
(x) - VLL S R(x) R(x.) Vx
(16)
2,m
RE [m
where R(x) J.
Ex= (x(r) and VR(x.) = 0.
We will also use the relaxed triangle inequality Karimireddy et al. 2020
Lemma 3):
|1 12
(17)
j=1
B.2 PROOF OF THEOREM 3.1
The theorem that we will prove is as follows.
Theorem B.1 (Full statement of Theorem 3.1). Assume that the clients are uniformly randomly selected at each round and the individual loss functions {Lx Lb are convex and B-smooth. Also
assume that x2 >> 273. Then Algorithm 3 satisfies the following inequality: Letting R(0) =
1 Eke(m) (m] (f) and 02 arg (0).
m
0
R
T-1
7'
- R(O.)
s
1
(Ell> - 0.112 + +xCO) + K²
X2d
T 150
Kg
1=0
1 2 T
Σ
(7 -0.),
0.), m
Σ
Elsign (0) - 02-1))
T X2
[=1
km[m]
(18)
where
Σ 0% 8¹ + xa
hh' ht
with P IPel.
P
REP:
10m
1 A2 B
P
X₂ X2- 25,32*
2 X3 25 - 50,32
K0 A
X3 25.2
5
X2 + 3
P
K'
Xe X3
25,32
2m
Co
Σ
E - (e.)).
RE(M)
d d0)
19

---

Under review as a conference paper at ICLR 2023
To prove the theorem, define variables that will be used throughout the proof.
0 arg min La (0) (O 10 X2 00 0-~111 + 110 01
vk [m]] (19)
C.
(0.) VL
(20)
m ke
C =
B -
(21)
m kE|mJ
Note that 0g optimizes the kth loss function by assuming that the kth client (A: [ml] is selected at round t. It is obvious that oj 0% if l Pt. C refers to the average of the expected differences between gradients of each individual model and the globally optimal model. Lastly & refers the deviation of each client model from the average of local models. Remark that Ct and approach zero if all clients' models converge the globally optimal model, i.e., 0% 0..
The following lemma expresses h', how much the averaged active devices' model deviates from the global model.
Lemma B.2. Algorithm satisfies
ht 1 Σ (L)( m k[(mm]
(22)
Proof. Starting from the update of he in Algorithm
A2
he h1-11
(
11-1)
sfg - 82-1)
m
m
k mm)
kEmm)
h1
1
(4 (Ok-)) (4 Aisign(Of - -0--1))
A1
Σ sign 0--1)
m
m ke(m]
[m]
1111
(VL(((-1)) (O)))
m kEIm
where the second equality follows from 11 By summing hi recursively, we have
ht = 12
Σ (L)
1 Σ
(L 1 Σ (Ln(
171
[m]
m [m)]
m
kE(m)
The next lemma provides how much the average of local models changes by using only t round parameters.
Lemma B.3. Algorithm satisfies
E(y
1111
Σ E
[[-
A
E(sign 0(--))]
Agm
Agm
k[[m)
ke [m]]
20

---

Under review as a conference paper at ICLR 2023
Proof.
Starting from the definition of y
1 Σ
1
[76
11
E
0
-0--1
h'11
P
X2
keP,
E
(0% - 1)
1
h²a 1-1
P
A2
kEP:
1
E
(V (O,) A1sign(0z 00-11)
/1-1
(23)
A2P
22
(VLx(0% - (6) Aisign(0) - -1--1))
ht h11
(24)
PgP
kEP:
1
E
(VL((0) (L) Assign(O; - -0-
/1"
A2m
A2
kE[m)
(25)
A1
E V(-V)+
Elsign (0) - -0-
(26)
A2m
Xmm
kE(mi
kEmm]
where 23 follows from 11 24) follows since 0%
8 if E Pr, and (5) follows since clients are
randomly chosen. The last equality is due to Lemma B.2
Next, note that Algorithm iis the same that of FedDyn except for the f--ormm penalty. As this new penalty does not affect derivations of Ct, and El|"" - 111= in FedDyn (Acar et al. 2021 can obtain the following bounds them. Proofs omitted for brevity.
11 < C.
(27)
1 (1- m
P
C--1 2,32p
43P E[R(-* R(O..)
5
Es +
(28)
m
m
B11y" - 111
11 11
(29)
k[(m)
Lemma B.4. Given model parameters the round (t 1), Algorithum
satisfies
2 EER(("-1) -R(()))) + A2
E1by" 0.11 -E|(>~11 - 00112
+ Elly - 11
(30)
Ao
2λ1 (7 0o)
Σ
B(sign(0 -0--1))
(31)
Aam
kE(m
where the expectations taken assuming parameters at the round (1 1) are given.
21

---

Under review as a conference paper at ICLR 2023
Proof.
B1yy 0.1 = EE17"-1 0. + 7 7 112
1EIl 11 12 2| + 2E ( 1-1 0..7 - - " B1ly" - 112
(1
1BIlT 11 12 + 1B11 - 11
2 E 11-1 0,, LL X1 (sign(0) -1-11)>
(32)
A2m
KE mm
$ 1B - 12 + 1B1 - 112
+ 2
Σ (0.) - (x( + - 2 - 11
A
kE ml
2
E 1/>- 10-1--0.- 0., -issiin 0% 01-1)}]
(33)
Amm
0a11 + E1l" - 70- 2 E|R(7* - R()))] +
B
E11y" -1
22
A2
221
Σ E [ 0., sign( - -0--1))
(34)
A2m
kE kc(m)
2 EIR((" 1-1 -R(00]] +
B
= -E1l7~-1 -1 - 0211 + 1E|1"* - -11-111
-
22
Aa
2A1
70-1 0.: m
Σ
Elsign (0% - 02-111)
(35)
A2
kE [m]]
follows from Lemma B.3 R.(.) and c.
where (32)
33 follows from 15). and (34 follows from the definitions of
Lemma B.5. Algoritiu satisfies
82 (1 (1-
1
5X?
4
S
10
1
C-1
+
10,3
X
E(R()=-1) R(0-)]
+
X2"
d
22

---

Under review as a conference paper at ICLR 2023
Proof.
Starting from the definitions of et and y²,
Bll0g 1/=1112
4
km
Bl10%
0
1
111
71 kE[m]
A2
Vo - (0(( - 1 -n1 112
(36)
X mm))
(o - (0.) + (L)( VLa(T(-1)
2 k[(m]
( (0) Alsign(0f 01-1) - 11-
5
5 EIVVLA(T (l.(0.))
$
V - VZ.(1.11 +
X2
km|m]
kc/ml
+
5 1
Σ
E VL +
5 2
E Aisign 0/- +
5
BBlhh-11
X2 m
X
kmm
(37)
$ 51 Σ
5 V - (0.)11) +
Σ
EI (L.(11)1
XA kE(m)
X m
kc(m
5 1 Σ
527
5
+
V (0))
VL || +
+
Cc-1
(38)
X m
22
kE[m)
5,82 1
5X
5
< 1
C--I+ +
2B ( 1 R(O-)]
+
E1 - +
+
C--1
X2
X/ m kE(m)
22
X
(39)
10
10,9
5
5 X2
C--++ X3
R(O0) + c
+
d
X2
X3
where (36) follows from T., (37) follows from the relaxed triangle inequality (7). (38) follows
from 27p. and (39) follows from the definition of C₁ the smoothness, and (16). The last equality follows from the definition of e,.
After multiplying (28) by x(= 10th 1 A2t and scaled version of
Xa 26522, obtain the following theorem by summing (B.4)
Theorem B.6. Given model parameters at the round (t - 1), Algorithm 3
satisfies
P 22
xoB[R(>**)) - -R(O,)) =
- 00112 (B11
(xC(-1) (BBlh - 0.11 + x(O)) 1
x²
2
9 A_,
1
Elsign -80-111
A
m
ke|m]
where k 10 1 A2ta
Au X 25,3 Ko =
Xa
2
33 25 50
X3
25,32
Note that the expectations taken above are
conditional expectations given model parameters at time (t ().
23

---

Under review as a conference paper at ICLR 2023
Proof. Summing Lemma B.4 and k-scaled version of (2 have
E - 0-112 + kOC
P
2
43P
- - 0.112 + +xC R K- C.
+
+ K
B[R(7/ - R((0))
2 E[R(>~-1) - -R(0.)] +
8
- 1 2x1
c + EBly*
(7/-1 - -0a) Σ
Elsign (0 - 0--1)]-
22
X2
A2m
kmmm]
(40)
As B11 - 112 1 <t by (29). we have
2
B
2
4 +
+ Elly' - -01-112
S k
Et + c2.
(41)
A2
m
X2
This can be further bounded as follows.
1
A2 + 3
2B2p
8
10
+
+ Et
P A2 X3
25.32
m
X2
1
(20()2 - B)B² + 3(x3 25.0%) + A2 - -25,3))
x2 - 25,32)
Az(22 + B)
32
X3 25,32
1 1
X2
E2
A2(A2 + B)
10
103
512
Ct-1
B[R((" -
X3 25,32
X3
X2
2
P
3P
P
C.-1 +
E[(( R(0,)) + Xjd.
2m
where the inequality follows from Lemma B.5
Then, 40
term will be
_.PP A2d
P
E1ly' 0.1 xC, S Elhh/11
0-
11 + KK0-1 Ko R((==] + K
"2m
2A1
1
7
1-1
00,
Σ
Elsign (0% - 0
A2
m
ke(m)
Rearranging terms, we prove the claim.
Now we are ready to prove the main claim by combining all lemmas. Let us take the sum on both sides of Lemma B.6 & 1...., T. Then, telescoping gives
P (R(()"=))- R(0.)] (Bll7² - 0.11 + xCo) (Ell>T 0.12 kOT) + T(r:
2m xi)
2m
2
1-1 O.: m
Σ
Eisign 011111
2
REIM
Since is positive if A2 > 273, we can eliminate the negative term in the middle. Then,
P
E[R( - -((O.) < E 0.112 + kCo -T(K X3d)
2m
2
1-1
0.. m
1
Σ
Elsign 0¹ 0r-11]]
Aa
kE ml
24

---

Under review as a conference paper at ICLR 2023
Dividing by T and applying Jensen's inequality,
T-1 R(O.)
E R. Σ
-
$
1 (B]17)
0.11 =Coo)
1 P
(1i 21d)
T nio
K50 2m
12
7 x-
0+:
Blsign(01 - 00-11
X2
m
RE RE(m
(42)
which completes the proof of Theorem B.1
B.3 DISCUSSION ON CONVERGENCE
In this section, we revisit the convergence stated in Theorem 3.1
Recall the bound
E
R
T-1
R(OO)
1 1 (E11) - 0.11 + xCo) +
(K Ald)
T
T
KO
2m
t=
1 2A T
E Elsign
-(-1)]
771
kE[m]
As we discussed in the main body, the second term is a negligible constant in the range of our hyperparameters as d₁ is of order of 10-1 or 10
Consider the last term where the summand is the inner product between two terms: 1) 7/-1- 0,, the deviation of the averaged local models from the globally optimal model and the average of sign vectors across clients. The deviation term characterizes how much the averaged local models are different from the global model; thus, we can assume that as training proceeds it vanishes or least is bounded by constant vector. To argue the average of sign vectors, assume special case where the sign vectors sign(0, - 1(-1) are III) across clients. To further simplify the argument, let us consider only single coordinate of the sign vectors, say X₃ sig f (i)). and suppose XA = 11 with probability 0.5 each. Then, the concentration inequality (Durrett 2019) implies that for any 8 > 0.
1 m
1 m
ma²
P
sign(()))
0r-1
=
X kE(m]
8
ke[m]
holds, which vanishes exponentially fast with the number of clients m. Since m is large in many FL scenarios, the average of sign vectors is negligible with high probability, which in implies the last term is also negligible.
25


Reviews:
[{"review_id": "vavP5wskNd", "reviewer": "Reviewer_9ArF", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes FedElasticNet which applies elastic net to federated learning (FL) of deep neural nets. The paper proposes two variants based on FedAvg and FedDyn, and provides the convergence analysis of the latter. Experiments are conducted to show the benefits of the proposed methods.", "summary_of_the_review": "In general, the paper is not very well written, and the motivation and performance of the proposed algorithm is poor. Thus, I think the paper does not meet the bar of ICLR.", "strength_and_weaknesses": "Strength:\n1. The topic of improving the efficiency and reducing client shift in FL is important.\n\nWeakness:\n1. The novelty is not significant. Both $l_1$ and $l_2$ regularizations are mature techniques in statistics, and deep neural network training. I do not find this method very interesting. Using Lasso to get sparsity is doable, but is very tricky to tune and leads to biased gradient estimation which would hurt the model performance. Indeed, the theory (Theorem 3.1) containg a nonvanishing constant is worse than the baseline FL rate, and emprical performance might also be worse in some cases as we see from the figures. Thus, the proposed method seems not very valuable both theoretically and empirically. Also, elastic net introduces two more hyper parameters $\\lambda_1$ and $\\lambda_2$ which make the method harder to tune. Thus, much stronger motivation is needed.\n\n2. The related work section should be improved. The paper misses many recent papers on communication-efficient FL.\n\n3. The presentation is not satisfactory. \n\n(i) In Algorithm 1, why is the local update presented in this way? How do you solve that optimization problem locally? In practice we may use SGD as in Algorithm 2? Why are they inconsistent? Are we using stochastic optimziation?\n(ii) In the theory part, there is no formal statement of the assumptions. I do not know the setting of this analysis. Particularly, which part is related to the client drift? The assumptions should be stated very clearly.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "u2Gkzbx5w2o", "reviewer": "Reviewer_odbQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Federated Learning trains a global model collaboratively over a set of clients , where the data is kept locally at the clients and only local gradients or parameters are communicated periodically with the server. Communicating large number of bits mights often slow down convergence and thus various compression schemes are used to deal with communication latency. Another challenge in the federated framework is heterogenous data distribution across clients. \n\nThis paper tries to tackle both these issues. In particular, they propose FedElasticNet a new framework for communication- efficient and drift-robust FL. They exploit $\\ell_1, \\ell_2$ regularization to deal with communication efficiency ( since $\\ell_1$ regularizer ensures sparse solution ) and client drift respectively. ", "summary_of_the_review": "Overall, while I feel the idea is nice - the paper in its current state lacks to establish the proposed claims -\nEmpirically we need ablations on: \n( a ) How does it compare with existing drift robust algorithms \n( b ) How does it compare with  existing algorithms that can deal with data heterogeneity. \n( c ) No mention of compression + EF in the paper - which is the standard practice in any FL setting. Why would I use this method and not C + EF ? ", "strength_and_weaknesses": "#### Strengths\n1. The idea is simple and intuitive.\n2. The paper is overall well written and motivated.  \n3. The authors show $O(\\frac{1}{T})$ convergence in the smooth, convex setting \n\n#### Concerns \n1. Table 1 - what do these symbols mean ? Please update the caption for readability.\n2. Theorem 3.1 The second term depends on d -  will it be negligible when we are dealing with practical large models ? A supporting plot simulating the convergence rates would be helpful. \n\n*Client Drift*\n\n3. Results on non-IID: One claim of the paper is that it can effectively deal with both client drift and communication compression. However, non-IID exp is extremely limited, only Shakesepeare and one non-iid setting; To support the drift robust claims - there needs to be more experiments on multiple dataset , models, and across different strength of heterogeneity comparing with multiple method that only deal with client drift / data heterogeneity.  \n\n4. In the non-iid setting, SCAFFOLD which is a standard approach to deal with client drift seems to perform equally well or even better than the proposed solution; Can you add more discussion on this and what are the scenarios when SCAFFOLD is better and when the proposed algorithm is better. \n\n5. The theory is based off FedDyn. Now, FedDyn and SCAFFOLD already deal with the client drift / heterogeneity and thus it is hard to flesh out the roles of the regularization penalty introduces in this paper.\n\n6. Analysis on FedAvg + $\\ell_1$ + $\\ell_2$ i.e. Algorithm 1 needs to be done - to clearly show if there is any advantage from these penalty terms. \n\n*Communication Compression*\n\n7. One effective way to deal with communication compression is to use contractive compression operators ex. quantization, top-k etc. To deal with the slow convergence due to additional terms appearing in the convergence result due to compression, it is standard practice to use an error feedback mechanism that ensures linear convergence at the same rate. One can simply use any of the drift robust algorithm (SCAFFOLD e.g.) apply communication compression with EF and be communication efficient.\nFor fair comparison, you need to compare with different drift robust algo + compression + EF with the proposed solution.\nEmpirically, for different compression rate ( using Top-k, Sign, Quantization etc compressor + Error Feedback compression operation C ) a clean experiment is to compare : FedAvg + C + EF vs FedAvg + $\\ell_1$ + $\\ell_2$ \n\n8. Also in theory, it is beneficial to discuss the convergence rate obtained (additional terms) with that in case of EF + Compression (Quantize, top k , q sparse etc several available approaches )\n \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jxir013F8l", "reviewer": "Reviewer_jTwe", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes adding an elastic net penalty while calculating client updates to the server model. The authors show that this augmentation can be implemented with a variety of standard FL optimization methods, provide theoretical convergence analysis for well behaved (convex, smooth) objective functions, and show empirically that adding this loss produces better results, both in terms of model update communication cost, and accuracy. ", "summary_of_the_review": "The work is accurate, but does not add sufficiently novel ideas. Utilizing elastic loss while training server side is already well established, and the loss function is well studied. Adding this loss to regularize the difference between the server model and client updated model is a fairly simple extension, and neither the theory nor experimental results are super exciting. ", "strength_and_weaknesses": "Strength\n- For one variant authors provide theoretical evidence that the augmentation does not harm convergence\nWeakness\n- Theory makes very strong assumptions \n- Theory does not prove improvement over baseline method, nor does it help much with practical questions (selecting tuning parameters etc). \n- Experiments show only marginal improvements over the baseline in terms of both compression and quality. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZYYiw0bZjF8", "reviewer": "Reviewer_Rp9d", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The papers shows how to apply elastic net [Zou & Hastie 2005] to existing federated learning (FL) schemes. Specifically, three FL schemes are selected: FedProx (already incorporates $\\ell_2$ regularization) [Li et al. 2020], SCAFFOLD [Karimireddy et al. 2020], and FedDyn [DAE Acar et al. 2021. At a high-level, elastic net is a regularization technique that combines $\\ell_1$ and $\\ell_2$ regularization.\n\nThe paper supports the claim that applying elastic net to the aforementioned FL schemes resolves the client drift and communication cost problem, in one fell swoop, through the following empirical evaluations:\n\n1. Sparsity (communication cost): Table 2: \"number of non-zero elements cumulated (accumulated?) over all round simulated with 10% client participation for IID and non-IID settings in FL scenarios.\"\n\n2. Entropy (client drift): Table 3 and Table 4: \"cumulative entropy values of transmitted bits with 10%\" and \"100% client participation for IID and non-IID settings in FL scenarios.\"\n\nAdditionally, test accuracy, as a function of communication rounds, results are also provided.\n\nFurthermore, the paper utilizes a distribution plot (Figure 2 -- FedDyn, elastic net applied to SCAFFOLD & FedDyn), and reference to the text by Cover & Thomas 2006 to substantiate the claim that \"FedElasticNet can reduce the entropy by transforming the Gaussian distribution into the non-Gaussian one.\"\n\n\n", "summary_of_the_review": "The novelty of this paper is scarce since the main idea is to show how to use elastic net under a limited set of FL schemes. The claims in the paper are also informal.", "strength_and_weaknesses": "Main concerns:\n1. FedProx and FedDyn are also FL schemes that utilize regularization ($\\ell_2$-like), thus this paper adds the $\\ell_1$ term with a sign adjustment.\n2. The last sentence in page 6: \"We optimize the hyperparameters depending on the evaluated dataset: learning rates, $\\lambda_2$, $\\lambda_1$\" is dubious as it relates to novelty since it can come down to the task of tuning these parameters to achieve the desired result, which is acceptable for application.\n3. Table 2 shows that the number of non-zero elements are reduced across the board, but it does not show \"when\" the non-zero elements become zero. This can be shown by a plot of non-zero elements vs communication round.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject