Federated Learning Based on Dynamic Regularization
Authors: Durmus Alp Emre Acar
Yue Zhao
Ramon Matas
Matthew Mattina
Paul Whatmough
Venkatesh Saligrama
Venue: ICLR 2021 Oral (2021)
Keywords: Federated Learning
Deep Neural Networks
Distributed Optimization

Abstract: We propose a novel federated learning method for distributively training neural network models, where the server orchestrates cooperation between a subset of randomly chosen devices in each round. We view Federated Learning problem primarily from a communication perspective and allow more device level computations to save transmission costs. We point out a fundamental dilemma, in that the minima of the local-device level empirical loss are inconsistent with those of the global empirical loss. Different from recent prior works, that either attempt inexact minimization or utilize devices for parallelizing gradient computation, we propose a dynamic regularizer for each device at each round, so that in the limit the global and device solutions are aligned. We demonstrate both through empirical results on real and synthetic data as well as analytical results that our scheme leads to efficient training, in both convex and non-convex settings, while being fully agnostic to device heterogeneity and robust to large number of devices, partial participation and unbalanced data.

Published as a conference paper at ICLR 2021
FEDERATED LEARNING BASED ON DYNAMIC REGULARIZATION
Durmus Alp Emre Acar* alpacar@bu.
Yue Zhao yue. 2hao@arm.r com
Ramon Matas Navarro ramon. www.maaaaassaaaaaam. arm. com
Matthew Mattina matthew weechh..mattiieeet www.mmmatttiaan.m com
Paul N. Whatmough
Venkatesh Saligrama" srv@bu. edu
paul wwll.wwhtmouugheee com
ABSTRACT
We propose novel federated learning method for distributively training neural network models, where the server orchestrates cooperation between a subset of randomly chosen devices each round. We view Federated Learning problem primarily from communication perspective and allow more device level computa- tions to save transmission costs. We point out fundamental dilemma, in that the minima of the local-device level empirical loss are inconsistent with those of the global empirical loss. Different from recent prior works, that either attempt inexact minimization utilize devices for parallelizing gradient computation, we propose a dynamic regularizer for each device at each round, so that in the limit the global and device solutions aligned. We demonstrate both through empirical results real and synthetic data as well as analytical results that our scheme leads to efficient training, in both convex and non-convex settings, while being fully agnostic device heterogeneity and robust to large number of devices, partial participation and unbalanced data.
INTRODUCTION
In (MeMahan al.) 2017), the authors proposed federated learning (FL), concept that leverages data spread across many devices, to learn classification tasks distributively without recourse to data sharing. The authors identified four principle characteristics of FL based on several use cases. First, the communication links between the server and devices are unreliable, and at any time, there may only be small subset of devices that are active. Second, data is massively distributed, namely the number of devices are large, while amount of data per device is small. Third, device data is heterogeneous, in that data in different devices are sampled from different parts of the sample space. Finally, data is unbalanced, in that the amount of data per device is highly variable.
The basic FL problem can be cast as one empirical minimization is decomposable as a sum of device-level empirical loss objectives. The number of communication rounds, along with the amount of bits communicated per round, has emerged as a fundamental gold standard for FL problems. Many mobile and IoT devices are bandwidth constrained. and wireless transmission and reception is significantly more power hungry than computation (Halgamuge et al.. 2009). As such schemes that reduce communication are warranted. While distributed SGD viable method in this context, it is nevertheless communication inefficient.
global loss objective, which
A Fundamental Dilemma. Motivated by these ideas, recent work has proposed to push optimization burden onto the devices, in order to minimize amount of communications. Much of the work in this context, propose optimize the local risk objective based on running SGD over mini-batched device data, analogous to what one would do in a centralized scenario. On the one hand, training models on local data that minimize local empirical loss appears be meaningful, but yet, doing so,
Bosson University, Boston, MA
Arm MI. Research Lab, Boston, MA

---

Published as a conference paper at ICLR 2021
is fundamentally inconsistent with minimizing the global empirical loss" (Malinovsky al. 2020 Khaled et al. 2020a) Prior works (McMahan et al. 2017; Karimireddy et al. 2019 Reddi et al. 2020p attempt to overcome this issue by running fewer epochs rounds of SGD on the devices, or attempt to stabilize server-side updates so that the resulting fused models correspond to inexact minimizations and can result in globally desirable properties.
Dynamic Regularization. To overcome these issues, we revisit the FL problem, and view it primarily from a communication perspective, with the goal of minimizing communication, and as such allowing for significantly more processing and optimization at the device level, since communication is the main source of energy consumption (Yadav & Yadav 2016 Latré et al., 201T). This approach, while increasing computation for devices, leads to substantial improvement in communication efficiency methods, uniformly across the four FL. scenarios (unreliable links, massive distribution, substantial heterogeneity, and unbalanced data). Specifically, in each round, we dynamically modify the device objective with a penalty term so that, in the limit, when model parameters converge, they do so to stationary points of the global empirical loss. Concretely, we add linear and quadratic penalty terms, whose minima is consistent with the global stationary point. We then provide analysis of our proposed FL algorithm and demonstrate convergence of the local device models to models that satisfy conditions for local minima of global empirical loss with a rate of O (+) where T is number of rounds communicated. For convex smooth functions, with devices, and P devices active per round, our convergence rate for average loss with balanced data scales as O (+ / //F) substantially improving over the state-of-art (SCAFFOLD O (4 (+))). For non-convex smooth functions, we establish a rate of O (7 )
over existing state-of-the-e
We perform experiments on both visual and language real-world datasets including MNIST, EMNIST, CIFAR-10, 100 and Shakespeare. We tabulate performance studying cases that are reflective FL scenarios, namely, for (i) varying device participation levels, (ii) massively distributed data, (iii) various levels of heterogeneity, as well as (iv) unbalanced local data settings. Our proposed algorithm, FedDyn, has similar overhead to competing approaches, but converges at a significantly faster rate. This results in a substantial reduction in communication compared to baseline approaches such as conventional FedAvg (MeMahan al., 2017), FedProx (Li et al., 2020) and SCAFFOLD (Kariiiredyy et al. 2019), for achieving target accuracy. Furthermore, our approach is simple to implement, requiring far less hyperparameter tuning compared to competing methods.
Contributions. We summarize our main results here.
We present, FedDyn, novel dynamic regularization method for FL. Key FedDyn is new concept, where in each round the risk objective for each device is dynamically updated so as to ensure that the device optima is asymptotically consistent with stationary points of the global empirical loss,
We prove convergence results for FedDyn both convex and non-convex settings, and obtain sharp results for communication rounds required for achieving target accuracy. Our results for convex case improves significantly over statc-of-art prior works. FedDyn in theory is unaffected by heterogeneity, massively distributed data, and quality of communication links,
On benchmark examples FedDyn achieves significant communication savings over competing methods uniformly across various choices of device heterogeneity and device participation on massively distributed large-scale text and visual datasets.
Related Work. FL is fast evolving topic, and only describe closely related approaches here. Comprehensive field studies have appeared in (Kairouz et al.) 2019 Li et al. 2020). The general FL setup involves two types of updates, the server and device, and each of these updates associated with minimizing some local loss function, which by itself could be updated dynamically over different rounds. At any round, there are methods that attempt to fully optimize or others that propose inexact optimization. We specifically focus on relevant works that address the four FL scenarios (massive distribution, heterogeneity, unreliable links, and unbalanced data) here.
'To see this consider the situation where losses are differentiable. As such stationary points for global empirical loss demand that only the sum of the gradients of device empirical losses are zero, and not necessarily that the individual device gradients are zero. Indeed, in statistically heterogencous situations, such where we have heterogeneous dominance of classes, stationary points of local empirical functions do not coincide.
2

---

Published as a conference paper at ICLR 2021
One line of work proposes local SGD (Stich 2019) based updates, wherein each participating device performs a single local SGD step. The server then averages received models. In contrast to local SGD, our method proposes to minimize local penalized empirical loss.
FedAvg (McMahan et al. 2017) is a generalization of local SGD, which proposes a larger number of local SGD steps per round. Still, FedAvg inexactly solves device side optimization. Identifying when to stop minimizing so that one gets a good accuracy-communicatin
trade-off is based on tuning the number of epochs and the learning rate (McMahan al., 2017; Li al. 2020b). Despite the strong empirical performance of FedAvg in IID settings, performance degrades in non-lID scenarios (Zhao
al. 2018).
Several modifications of FedAvg have been proposed to handle non-llD settings. These variants in- clude using& decreasing learning rate (Li et al. 2020b); modifying device empirical loss dynamically (Li et al. 2020a): or modifying server side updates (Hsu et al. 2019: Reddi et al. 2020). Methods that use a decreasing learning rate or customized server side updates still rely on local SGD updates within devices. While these works do recognize the incompatibility of local and global stationary points, their proposed fix is based on inexact minimization. Additionally, in order to establish convergence for non-IID situations, these works impose additional Phounded-non-Ile conditions.
FedProx (Li et al.) 2020a) is related to our method. Like us they propose a dynamic regularizer, which is modified based server supplied models. This regularizer penalizes updates that are far away from the server model. Nevertheless, the resulting regularizer does not result in aligning the global and local stationary points, and as such inexact minimization is warranted, and they do so by carefully choosing learning rates and epochs. Furthermore, tuning requires some knowledge of statistical heterogeneity.
In a similar vein, there are works that augment updates with extra device variables that are also transmitted along with the models (Karimireddy et al., 2019 Shamir al. 2014). These works prove convergence guarantees through adding device-dependen regularizers. Nevertheless, they suffer additional communication costs and they are not extensively experimented with deep neural networks. Among them, SCAFFOLD (Karimiredyy et al. 2019) is a closely related work even though transmits extra variables and more detailed comparison is given in Section 2
Another line of distributed optimization methods (Konečný et al. 2016; Makhdoumi & Ozdaglar I
2017 Shamir et al. 20044) Yuan & Ma 2020) Pathak & Wainwright 2020) Liang et al., 2019; Li
et al. 2020c: Condat et al. 2020) could be considered in this setting. Moreover, there are works that
extend analysis of SGD type methods to FI. settings (Gorbunov al.
2020) Khaled et al., 2020b; Li
& Richtárik 2020). However, these algorithms are proposed for full device participation case which fails to satisfy one important aspect of FL, FedSVRG (Konečný et al. 2016) and DANE (Shamir et al.)
2014] need gradient information from all devices at each round and they
not directly applicable to partial FL settings. For example, FedDANE (Li et al., 2019) is a version of DANE that works in partial participation. However, FedDANE performs worse than FedAvg empirically with partial participation (Li et al., (019)). Similar to these works, FedPD (Zhang et al. 2020) method is proposed in distributed optimization with different participation notion. FedPD activates either all devices or no devices per round which again fails to satisfy partial participation in FL.
Lastly, another of works aims decrease communication costs by compressing the transmitted models (Dutta et al. 20199 Mishchenko et al. 2019, Alistarh et al. (017).. They save communication costs through decreasing bit-rate of the transmission. These ideas are complementary to our work and they can be integrated to our proposed solution.
2
METHOD
We assume there is a cloud server which can transmit and receive messages from m client devices. Each device, k E [m] consists of N₂ training instances in the form of features, x E X and corresponding labels E y that are drawn IID from a device-indexed joint distribution, (z.y) ~ Pa.
Our objective is to solve
arg min
((0)
1
Σ kc
(0)
0ER4
m
kc(m]]
3

---

Published as a conference paper at ICLR 2021
Algorithm 1: Federated Dynamic Regularizer (Feddyyn)
Input: T, 00 a > 0, (L) O. for f = ..2....Td
Sample devices Pe C [m] and transmit 8- to each selected device, for each device & E Pt. and in parallel do
Set 0:
argmin LA (0) (VLi (0 (0)-))))))) 0) 2 0² 113.
Set VL = Ln (6% a (0) 0 0²-1).
Transmit device model 0 to server, end for for each device i & Pe, and in parallel do
Set 0 = 0 1-1 (O)) (0%
end for
Set h
= h2 11 - a (Eke,, 0 -0' 11
Set 0 = (1 0% Lh²
end for
B(m,,)) 16x : (a, y))] is the empirical loss of the kth device, and 0 are the parameters of our neural network, whose structure is assumed to be identical across the devices and the server. We denote by 0* a local minima of the global empirical loss function.
where, LA (0)
FedDyn Method. Our proposed method, FedDyn, is displayed in Algorithm [1] In each round, a subset of devices Pi C [m]] are active, and the server transmits its current model, e²-1 to
t e [T], these devices. Each active device then optimizes a local empirical risk objective, which is the sum of its local empirical loss and penalized risk function. The penalized risk, which is dynamically updated, is based on current local device model, and the received server model:
0 argmin
Ri (0; o 0 1² a (0) - (V 0) + a ブ 0² 11].
(I)
Devices compute their local gradient, V (0%-1) recursively, by noting that the first order condition for local optima must satisfy,
(L) (LL(0 + a(O)) -0"-1)=
Stale devices do not update their models. Updated device models, 0 k E Pr are then transmitted to server, which then updates its model 0' displayed in Algorithm
Intuitive Justification. To build intuition into our method, we first highlight a fundamental issue about the Federated Dynamic Regularizer setup. It is that stationary points for device losses, in general, do not conform to global losses. Indeed, a global stationary point, 0" must necessarily satisfy,
Ve((0)=
(O.)
Σ Be (0. v)) 0. AE[m]
(3)
M. RE|M)
In contrast a device's ' stationary point, 0f satisfies, (O,) 0, and in general due to heterogeneity
of data (Px * P, for lt + j), the individual device-wise gradients are non-zero VL + 0. This
means that the dual goals of (i) seeking model convergence to a consensus, namely, 0 - 0 - 0., and (ii) the fact that model updates are based optimizing local empirical losses is inconsisten
Dynamic Regularization. Our proposed risk objective in Eq. [ dynamically modifies local loss functions, that, if in fact local models converge to a consensus, the consensus point consistent with stationary point of the global loss. To see this, first note that we initialize at consensus point,
namely, 0% = -1 we have, VR(0, 0% _0" _ = 0 for f = l Thus our choice can be
As pointed in related work prior works based on SGD implicitly account for the inconsistency by performing inexact minimization, and additional hyperparameter tuning.
4

---

Published as a conference paper at ICLR 2021
seen modifying the device loss that the stationary points of device risk is consistent with server model.
Key Property of Algorithm 7 If local device models converge, they converge to the server model. and the convergence point is a stationary point of the global loss. To see this, observe from Eq 2 have O - 0% In turn this implies that 0 - - iie., is independent of k. Putting all of this together with our server update equations have that 0' convergence implies h² + 0. Now the server state h' A E. (L.())) and such in the limit are left with Ex V2
that if f 0% generally follows that, (O%) - (0, and consequence,
En (Lx 0.
This implies that we converge to a point that turns out to be a stationary point of the global risk.
2.1 CONVERGENCE ANALYSIS OF FEDDYN.
Properties outlined in the previous section, motivates our FedDyn convergence analysis of device and server models. We will present theoretical results for strongly convex, convex and non-convex functions.
Theorem 1. Assuming constant number of devices are selected uniformly random in each round, [P&l = P. for a suitably chosen of a > 0, Algorithm 7 satisfies,
μ strongly convex and smooth { mm functions.
E l
Σ
B 01100 0.112
Σ IVL.
nt
P
m ke(m]
Convex and L smooth {Lx Jk= functions,
E
i
l o
1
L 0 -.11
+
1 Σ IVLN(0.)11))
T
T
m kc(m)
Nonconvex and L smooth { ym functions
E [[( = (
m L (E(0") -c.) +12
Σ kE(m)
100 0013
where 7'= -'=P 0
0 a.=arg min (()), 4--((0.) r= (1+
R= R=
8=max (5% 30L) and F is a random variable that takes values {r> [T= with equal prob- ability.
Theorem gives rates for strongly convex, convex and nonconvex local losses. For strongly convex and smooth functions, in expectation, a weighted average of active device averages converge at linear rate. For convex and smooth functions, in expectation, the global loss of active device averages, converges at rate O F #V P Following convention, this rate is for the empirical loss averaged across devices. As such this would hold with moderate data imbalance. In situations with significant imbalance, which scales with data size, these results would have to account for the variance in the amount of data/device. Furthermore, the / factor might appear surprising, but note that our bounds hold under expectation, namely, the error reflects the average over all random choices of devices. Similarly, for nonconvex and smooth functions, in expectation, average of active device rate. The expectation is taken over randomness
models converges to stationary point O in active device set at each round. Similar to known convergence theorems, the problem dependent constants are related to how good the algorithm is initialized. We refer to Appendix for detailed proof.
FedDyn SCAFFOLD (Krimireddy et al., 2019). While SCAFFOLD appears to be similar to our method, there are fundamental differences. Practically, SCAFFOLD communicates twice many bits FedDyn or Federated Dynamic Regularizer, transmitting back and forth, both
5

---

Published as a conference paper at ICLR 2021
Table I: Number of parameters transmitted relative one round of FedAvg to reach target test accuracy for moderate and large number of devices in IID and Dirichlet .3 settings. SCAFFOLD communicates the current model and its associated gradient per round, while others communicate only the current model. As such number of rounds for SCAFFOLD is one half of those reported.
Device Number
Dataset
Accuracy
FedDyn
SCAFFOLD
FedAvg
FedProx
III)
84.5
637
1852(2.9x)
1000+(>1.6x)
1000+(>1.6x)
CIFAR-10
82.3
240
512(2.1x)
994(4.1x)
825(3.4x)
51.0
522
1854(3.6x)
1000+((>1.xx)
1000+((>1.xx)
CIFAR-100
40.9
159
286(1.8x)
822(5.2x)
873(5.5x)
Moderate
Dirichlet (.3)
82.5
444
1880(4.2x)
1000+(>2.3x)
1000+(>>.3x))
CIFAR-10
80.7
232
594(2.6x)
863(3.7x)
930(4.0x)
51.0
561
1884(3.4x)
1000+(<1.8x)
1000-(>188x)
CIFAR-100
42.3
170
330(19x))
959(5.6x)
882(5.2x)
IID
80.0
840
4000+((>488)
2000+(>244))
2000+(>244X)
CIFAR-10
62.3
305
928(3.0x)
1277(4.2x)
1274(4.2x)
50.1
1445
3982(2.8x)
2000+ (44)
2000++ 1.4x)
CIFAR-1O0
38.3
477
1408(3.0x)
1997(4.2x)
1974(4.1x)
Massive
Dirichlet (.3)
80.0
831
4000+((2488)
2000+(22244)
2000+(>224x)
CIFAR-10
70.6
350
2138(6.1x)
1962(5.6x)
1517(4.3x)
47.0
969
4000(4.1x)
+02.
2000+
CIFAR-1OW
39.9
467
2266(4.9x)
1913(4.1x) 1794(3.8x)
a model and its gradient. The 2x increase in bits can be substantial for many low-power IoT applications, since energy consumption for communication dominates computation. Conceptually, we attribute the increased bit-rate to algorithmic differences. risk incorporates linear term, (0%) (which
the device-level, our modified compute readily (Eq. 2 Applying
perspective to SCAFFOLD, full participation setting, we see SCAFFOLD as replacing our linear
term (VL) O) with (O') 1 ExE(m) (L))) 0)). While (L+(O") can be locally
m
m computed, after 0* is received, the term 1 ExE(m) LL2 (Of) is unknown and must be transmitted by the server, leading to increased bit-rate. Note that this is unavoidable, since ignoring this term, 0¹) ) + 2 |@ 0¹1 results in 0² This extra term is surrogate for Ve(0"), which unavailable. As such we believe that these differences are responsible for FedDyn's improved rate (in rounds) in theory as well as practice.
leads to freezing device updates (optimizing La (+) (V
Finally, apart from conceptual differences, there are also implementation differences. SCAFFOLD runs SGD, and adapts hyperparameter tuning for given number of rounds to maximize accuracy. In contrast, our approach, based on exact minimization, agnostic to specific implementation, and as such we utilize significantly less tuning.
EXPERIMENTS
Our goal in this section is evaluate FedDyn against competing methods on benchmark datasets for various FL scenarios. Our results will highlight tradeoff's and benefits of our exact minimization relative prior inexact minimization methods. To ensure a fair comparison, the usual SGD procedure is adapted for the FedDyn algorithm in the device update as in FedAvg rather than leveraging an off the shelf optimization solver. We provide brief description of the datasets and the models used in the experiments. A detailed description of our setup can be found in Appendix A. Partial participation was handled by sampling devices at random in each round independent of previous rounds.
Datasets. We used benchmark datasets with the same train/test splits as in previous works (McMahan ct al. 2017; Li et al. 2020a) which are MNIST (LeCun et al., 1998). CIFAR-I0, CIFAR- (Krizhevsky et al. 2009). subset of EMNIST (Cohen et al. (017) (EMNIST-L), Shakespeare Shakesseaare 1994h as well as a synthetic dataset. The IID split is generated by randomly assigning datapoints to the devices. The Dirichlet distribution is used label distributions among devices for non-lID splits as in (Yurochkin et al. 2019). For example, in MNIST, 100 device experiments, each device has about and 3 classes that consume 80% of local
the label ratios to ensure uneven

---

Published as a conference paper at ICLR 2021
data at Dirichlet parameter settings of 0.6 and 0.3 respectively. To generate unbalanced data, sample the number of datapoints from a lognormal distribution. Controlling the variance of lognormal distribution gives unbalanced data. For instance, in CIFAR-I0, 100 device experiments, balanced and unbalanced data settings have standard deviation of device sample size of and 0.3 respectively.
Models. We use fully- connected neural network architectures for MNIST and EMNIST-L with 2 hidden layers. The number of neurons in the layers are 200 and 100; and the models achieve 98.4% and 95.0% test accuracy in MNIST and EMNIST-L respectively. The model used for MNIST is the same as used in (McMahan et al., 2017). For CIFAR-I0 and CIFAR-100, we use a CNN model, similar to (McMahan et al. (017), consisting of 2 convolutional layers with 64 5 X filters followed by 2 fully connected layers with 394 and 192 neurons. and a softmax layer. The model achieves 85.2% and 55.3% test accuracy for CIFAR- 10 and CIFAR- 100 respectively. For the next character prediction task (Shakespeare), we use stacked LSTM, similar to (Li et al. (020a). This architecture achieves a test accuracy of 50.8% and 51.2% in IID and non-IID settings respectively. Both IID and non-IID performances are reported since splits are randomly regenerated from the entire Shakespeare writing. Hence centralized data and the centralized model performance is different.
In passing, we note that while the accuracies reported are state-of-art for our chosen models, higher capacity models can achieve higher performance on these datasets. As such, our aim is to compare the relative performance of these models in FL using FedDyn and other strong baselines.
Comparison of Methods. We report the performance of FedDyn, SCAFFOLD, FedAvg and FedProx on synthetic and real datasets. We also experimented with distributed SGD, where devices in each round compute gradients on the server supplied model on local data, and communicate these gradients. Its performance was not competitive relative other methods. Therefore, we do not tabulate it here. We cover synthetic data generation and its results in Appendix A.
The standard goal in FL. is to minimize amount of bits transferred. For this reason, adopt the number of models transmitted to achieve target accuracy as our metric in our comparisons, This metric is different than comparing communication rounds since not all methods communicate the same amount of information per round. FedDyn, FedAvg and FedProx transmit/receive the same amount of models for fixed number of rounds whereas SCAFFOLD costs twice due transmission of states. We compare algorithms for two different accuracy levels which we pick them to be close to performance obtained by centralizing data. Along with transmission costs of each method, we report the communication savings of FedDyn compared to each baseline in parenthesis. For methods that could not achieve aimed accuracy within the communication constraint, we append transmission cost with + sign. We observe FedDyn results in communication savings compared to all baselines to reach a target accuracy. We test FedDyn under the four characteristic properties of FL which are partial participation, large number of devices, heterogeneous data, and unbalanced data.
Moderate vs. Large Number of Devices. FedDyn significantly outperforms competing methods in the practically relevant massively distributed scenario. We report the performance of FedDyn on CIFAR- and CIFAR-100 with moderate and large number of devices in Table [ while keeping the participation level constant (10%) and the data amounts balanced. Specifically, the moderately distributed setting has 100 devices with 500 images per device. The massively distributed setting has 1000 devices with 50 images per device for CIFAR-10, as well as 500 devices with 100 images per device for CIFAR- 100. In each distributed setting, the data is partitioned in both IID and non-llI) (Dirichlet 0.3) fashion. FedDyn leads to substantial transmission reduction in each of the regimes.
First, the communication saving in the massive setting is significantly larger relative to the moderate setting. Compared to SCAFFOLD, FedDyn leads to 4.8x and 2.9x gains respectively on CIFAR-10 IID setting. SCAFFOLD is not able to achieve 80% within 2000 rounds in the massive setting (shown in Figure 4a), thus actual saving more than 4.8x. Similar trend is observed in the non-lll setting of CIFAR-I0 and CIFAR- 100. Second, all the methods require more communications to achieve a reasonable accuracy in the massive setting as the dataset is more decentralized. For instance, takes FedDyn 637 rounds to achieve 84.5% with 100 devices, while it takes 840 rounds to achieve 80.0% with 1000 devices. Similar trend is observed for CIFAR-100 100 and other methods. FedDyn always achieves the target accuracy with fewer rounds and thus leads significant saving. Third, higher target accuracy may result in a greater saving. For instance, the saving relative to SCAFFOLD increases from 3x to 4.8x in the CIFAR- 10 IID massive setting. We may attribute this the fact that FedDyn aligns device functions to global loss and efficiently optimizes the problem.
7

---

Published as a conference paper at ICLR 2021
Full vs. Partial Participation Levels. FedDyn outperforms baseline methods across different device participation levels. We consider different device participation levels with 100 devices and balanced data in Table where part of CIFAR-10 10 and CIFAR- 100 results omitted since they reported in moderate number of devices section of Table The Shakespeare non-III results are separately shown, since it has natural non-IlI split which does not conform with the Dirichlet distribution. The communication gain, with respect to best baseline, increases with greater participation levels from 2.9x to 9.4x; x.0x to 12.8x and 4.2x 7.9x for CIFAR-IO in different device distribution settings. We observe a similar performance increase in full participation for most of the datasets. This validates our hypothesis that FedDyn more efficiently incorporates information from all devices compared to other methods, and results in more savings in full participation. Similar to previous results, a greater target accuracy gives a greater savings most of the settings. We also report results for 1% participation regime with different device distribution settings (See Table S in Appendix A.I).
Balanced vs. Unbalanced Data. FedDyn more robust to unbalanced data than competing methods. We fix number of devices (100) and participation level (10%) and consider effect of unbalanced data (Table 1 (Appendix A. FedDyn achieves 4.3x gains over the best competitor, SCAFFOLD to achieve the target accuracy. As before, gains increase with the target accuracy.
IID vs. non-IID Device Distribution. FedDyn outperforms baseline methods across different device distribution levels. We consider heterogeneous device distributions in the context of varying device numbers, participation levels and balanced-unbalaneee settings in Table 1 and 4 (Appendix 1A.1) respectively. Device distributions become more non-IID as we go from III, Dirichlet 6 to Dirichlet... 3 splits which makes global optimization problem harder. We see a clear effect of this change in Table for 10% participation level and in Table 4 for unbalanced setting. For instance, increasing non-llI level results in greater communication saving such as from 2.9x, 4.0x to 4.2x in CIFAR-10 10% participation. Similar statement holds for MNIST, EMNIST-L and Shakespeare Table and for CIFAR-10 10 unbalanced setting in Table We do not observe a significant difference in savings for full participation setting Table 2
Summary. Overall, FedDyn consistently leads to substantial communication savings compared to baseline methods uniformly across various FL regimes of interest. We realize large gains in the practically relevant massively distributed data setting.
4 CONCLUSION
We proposed FedDyn, a novel FL method for distributively training neural network models. FedDyn is based on exact minimization, wherein each round, each participating device, dynamically updates its regularizer so that the optimal model for the regularized loss is in conformity with the global empirical loss. Our approach is different from prior works that attempt to parallelize gradient computation, and in doing so they tradeoff target accuracy with communications, and necessitate inexact minimization. We investigate different characteristic FL settings to validate our method. We demonstrate both through empirical results on real and synthetic data as well as analytical results that our scheme leads to efficient training with convergence rate as O (+) where in both convex and non-convex settings, and a linear rate in strongly convex setting, while being fully agnostic to device heterogeneity and robust to large number of devices, partial participation and unbalanced data.
number of rounds,
8

---

Published as a conference paper at ICLR 2021
Table 2: Number of parameters transmitted relative one round of FedAvg to reach target test accuracy for 100% and 10% participation regimes in the IID, non-llD settings. SCAFFOLD commu- nicates the current model and its associated gradient per round, while others communicate only the current model. As such number of rounds for SCAFFOLD is one half of those reported.
Participation
Dataset
Accuracy
FedDyn
SCAFFOLD
FedAvg
FedProx
IID
85.0
198
1860(9.4x)
1000+(>5.1x)
1000+(>5.1x)
CIFAR- 10
81.4
67
320(4.8x)
754(11.3x)
655(9.8x))
51.0
2559
1744(6.7x)
1000+(2339x)
1000+(2339x))
CIFAR-100
39.4
55
172(3.1x)
(000-(>18.2x))
741(13.5x)
98.2
38
72(1.9x)
194(5.1x)
445(11.7x)
MNIST
97.2
18(2.0x)
31(344x)
28(3.1x)
94.6
414(6.4x)
307(4.7x)
1000+(>115x)
EMNIST-L
93.6
16
36(2.2x)
66(4.1x)
62(3.9x)
46.4
33
74(2.2x)
96(2.9x)
113(3.4x)
Shakespeare
45.4
28
64(2.3x)
59(2.1x)
56(2.0x)
Dirichlet (.6)
84.0
148
189X1228X)
(000+(>6.8))
CIFAR-10
80.3
64
392(6.1x)
869(13.6x)
724(1133))
51.0
468
1838(3.9x)
(000+(>21X))
1000++>2.Xx)
CIFAR-100
40.6
206(2.8x)
998(13.7x)
592(8.1x)
100%
98.1
39
108(2.8x)
157(4.0x)
416(10,7x)
MNIST
97.1
11
24(2.2x)
38(3.5x)
34(3.1x)
94.9
207
552(2.7x)
410(2.0x)
1000+(>448x)
EMNIST-L
93.9
20
42(2.1x)
73(366x)
61(3.0x)
Dirichlet (.3)
83.5
223
1762(7.9X)
1000+(>4.5x)
1000+(+4.5x)
CIFAR-10
80.2
70
504(7.2x)
705(10.1x)
(0.3x(>14.3x)
50.5
1940(4.8x)
1000+(>233x)
1000+((223x)
CIFAR-100
41.0
224(2.8x)
911(11.4x)
1000+(>12.5x))
98.1
35
76(2.xx)
313(8.9x)
458(13.1x)
MNIST
97.1
10
24(2.4x)
49(4.9x)
44(4.4x)
94.5
63
210(322X)
492(7.6x)
1000+(>11x))
EMNIST-L
93.5
23
46(2.0x)
78(3.4x)
69(3.0x)
Non-IID
47.3
33
70(2.1x)
134(4.1X)
150+(>4.5x)
Shakespeare
46.3
62(2.2x)
53(1.x))
64(2.3x)
98.2
100
142(1.4x)
388(5.9x)
362(3.6x)
MNIST
97.2
52(1.7x)
49(1.6x)
43(1.4x)
94.6
104
1,0(1.5x)
330(3,2x)
210(2.0x)
EMNIST-L
93.6
58
84(1.xx)
69(1.2x)
65(1.1))
46.9
63
94(1.5x)
138(22Xx)
190(3.0x)
Shakespeare
45.9
56
76(1 14x)
96(1.7x)
75(1.3x)
Dirichlet (.6)
83.5
403
1618(4.0X)
(000+(>2.3x)
1000+(22.5x)
CIFAR-10
81.3
189
486(2.6x)
977(5.2x)
943(5.0x)
51.0
1910(3.7x)
1000+(>1.9x))
1000+<>1.9x))
CIFAR-100
41.6
170
302(1.8x)
931(5.5x)
748(4.4x)
10%
98.1
129
194(1.5x)
581(4.5x)
361(2.8x)
MNIST
97.1
37
60(16x))
57(1.5x)
57(1.5x)
94.9
192
296(1.5x)
306(1.6x)
(000+(>332X)
EMNIST-L
93.9
55
102(1.9x)
95(1.7x)
86(1.6x)
Dirichlet (.3)
98.2
208(2.3x)
428(4.8x)
858(9.5x)
MNIST
97.2
68(1.8x)
76(2.1x)
61(16xx)
94.4
107
178(1.7x)
804(7.5x)
1000+((>933x)
EMNIST-L
93.4
58
100(L.7x)
81(14x)
86(1.5x)
Non-IID
47.6
63
[02(L.6)
169(2.7x)
133(2.1x)
Shakespeare
46.6
56
82(1.5x)
80(1.4x)
66(1.2x)

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
This research was supported by a gift from ARM corporation (DA), and CCF-2007350 (VS), CCF- 2022446(VS), CCF-195596 (VS), the Data Science Faculty Fellowship from the Rafik B. Hariri Institute.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Sebastian Caldas, Peter Wu, Tian Li, Jakub Konecný, H. Brendan McMahan, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. CoRR, abs/1812.01097,, 2018. URL
http://arxiv/ http//bsss/112/ 01009
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference Neural Networks (IJCNN), pp- 2921-2926. IEEE, 2017.
Laurent Condat, Grigory Malinovsky, and Peter Richtárik. Distributed proximal splitting algorithms with rates and acceleration. arXiv preprini urXiv:2010.00952, 2020.
Aritra Dutta, El Houcine Bergou, Ahmed M Abdelmoniem, Chen-Yu Yu Ho, Atal Narayan Sahu, Marco Canini, and Panos Kalnis. On the discrepancy between the theoretical analysis and practical implementations of compressed communication for distributed deep learning. arXiv preprint arXiv:1911.08250, 2019.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of sgd: Variance reduc- tion, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, pp. 680 690.. PMLR, 2020.
Malka N Halgamuge, Moshe Zukerman, Kotagiri Ramamohanarao, and Hai L Vu. An estimation of sensor energy consumption. Progress in Electromagnetics Research, 12:259 2959 2009.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition.
pp. 770-778, 2016.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. CoRR, 0bss/199900633. 2019, http
f/a 1/arxiv. //aaxivvorg/aabaa.. abts///b///// /1 0009006333
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. arXiv preprint pet.iit92277977 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for on-device federated learning. CoRR, abs/1910.06378, 2019. URL http:::::/axxii.rgg//aassa/////a wttps//www..rg/aa///.//././
06378
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtarik. Tighter theory for local sgd on identical and heterogeneous data. In Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, pp. 4519-4529, Online, 26- 28 Aug 2020a. PMLR. URL htllhttpp/pppccceiingg. mlr.mmmr... wrwps wttpppppeeeeeeoooaauuoo.......aa html
Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint arXiv:2006. /573, 2020b.
Jakub Konečny, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint 1XX0:/600.002211 2016.
10

---

Published as a conference paper at ICLR 2021
Alex Krizhevsky et al. Learning multiple layers of features from tiny images. Technical report, 2009.
Benoft Latré, Bart Braem, Ingrid Moerman, Chris Blondia, and Piet Demeester. A survey on wireless body area networks. Wireless networks, 17(1):1-18, 2011.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, (6(11):2277-2324, 1998.
T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3)550-60, 2020.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smithy, Feddane: A federated newton-type method. 2019 53rd Asilomar Conference on Signals, Systems, and Computers, pp. 1227-1231. IEEE, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems 2020, pp. 429-450, 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. International Conference on Learning Representations, 2020b. URL
net neet/Forumm1ld<tXXNaaa
Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint (rXiv:2006607013. 2020.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv: 1364, 2020c.
Xianfeng Liang. Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local sgd with lower communication complexity. arXiv preprint
2019.
Ali Makhdoumi and Asuman Ozdaglar. Convergence rate of distributed admm over networks. IEEE Transactions on Automatic Control, 62(10):502255093 2017.
Grigory Malinovsky, Dmitry Kovalev, Elnur Gasanov, Laurent Condat, and Peter Richtarik. From local sgd local fixed point methods for federated learning. arXiv preprint arXiv:2004.011 01442. 2020.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. coammunication-effiiien learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 190//1000000 /.09699 2019.
Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky. Primal-dua accelerated gradient methods with mmall-dimensional relaxation oracle. Optimization Methods and Software, pp. 1-38, 2020.
Reese Pathak and Martin J Wainwright. Fedsplit: An algorithmic framework for fast federated optimization. arXiv preprint arXiv:2005.052.: 2020.
Sashank Reddi, Zachary Charles, Manzil Zaheer. Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
William Shakespeare.
The complete works of william shakespeare, 1994. URL http:/ttt///. www outeeberr..ogg/flleee..
111111199-01110000 zip
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effinn distributed optimization using an approximate newton-tys type method. In International conference on machine learning, pp. 1000-1008, 2014.
11

---

Published as a conference paper at ICLR 2021
Sebastian Urban Stich. Local SGD converges fast and communicates little. International Conference on Learning Representations (ICLR), pp. arXiv:1805.09767, 2019. URL htttps://axxt
prq/abs/Lee 1805. 09767
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp. 3-19, 2018.
Sarika Yadav and Rama Shankar Yadav. A review energy efficient protocols in wireless sensor networks. Wireless Networks, 22(1):335-3500 2016.
Honglin Yuan and Tengyu Ma. Federated accelerated stochastic gradient descent. arXiv preprint arXiv:2006.08995 2020.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In International Conference on Machine Learning, pp. 7252-7261, 2019.
Xinwei Zhang, Mingyi Hong, Sairaj Dhople, Wotao Yin, and Yang Liu, Fedpd: federated learning framework with optimal rates and adaptivity to non-iid data. arXiv preprint arXiv:2005. 14188, 2020.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:1806.00530 2018.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 EXPERIMENT DETAILS
A.1.1 SYNTHETIC DATA
Dataset. We introduce synthetic dataset to reflect different properties of FL by using similar process as in (Li et al. 2020a). The datapoints (z,, yj) of device i are generated based on y = arg magmax(" (0, + b;) where æ; E R Dj E 21. 5). tuple represents the optimal parameter set for device and each element of these tuples are randomly drawn from (M4 1) where μ4 ~ (O0 71). The features of datapoints are modeled as (æ) ~ ((),, where a is a diagonal covariance matrix with elements k 1-1.2 and each element of 142 is drawn from (B,, 1) where B, ~ N(0,72) The number of datapoints in device i follows a lognormal distribution with variance 73- In this generation procees, 71, 72 and "3 regulate the relation of the optimal models for each device, the distribution of the features for each device and the amount of datapoints per device respectively.
0 E R5x30, and bj E R (0) by)
We simulate different settings by allowing only one type of heterogeneity at time and disabling the randomness from the other two. For instance, if we want to disable type heterogeneity, we draw one single set of optimal parameters (0", b²) (0, and use it to generate datapoints for all devices. Similarly, V44 is set to 0 to disable type heterogeneity and y is set to 0 to disable type 3 well as a homogeneous setting. The number of devices is set to 20 and the number of datapoints per device on average 200 in the generation process.
heterogeneity. We consider four settings in total, including type 1, 2, and 3 heterogeneous
Models. We test FedDyn, SCAFFOLD, FedAvg and FedProx using a multiclass logistic classification model with cross entropy loss. We keep batch size be 10, weight decay to be 10-5
We test learning rates in 11] and epochs in [1, 10, 50) for all three algorithms. a parameter of
FedIDyn is chosen among [_1, 11,,-0100000 -001]; K parameter of SCAFFOLD is searched in [20, 200, 1000] which corresponds to the same amount of computation using above epoch list; and μ regularization hyperparameter of FedProx in [0.01, .0001).
Table reports the number models transmitted relative to one round of FedAvg to achieve the target training loss for best hyperparameter selection in various settings with 10% device participation. As shown, FedDyn leads to communication savings in each of the settings in range 1.1x to 7.6x.
A.2 REAL DATA
Datasets. MNIST, EMNIST-L, CIFAR-10 and CIFAR-I00 are used for image classification tasks and Shakespeare dataset is used for a next character prediction task. The image size is (1 x 28 x 28) in MNIST and EMNIST: (3 x 32 x 32) in CIFAR-10 and CIFAR- 100 with overall 10 classes in MNIST and CIFAR-10; 62 classes in EMNIST: and 100 classes in CIFAR-100. We choose the first 10 letters from the letter section of EMNIST (named it as EMNIST-L) similar (Li al. (020a) work. Features in Shakespeare dataset consists of 80 characters and labels are the following characters. Overall, there are 80 different labels for datapoints.
We use the usual train and test splits for MNIST, EMNIST-L, CIFAR-IO and CIFAR-100. The number of training and test samples of the benchmark datasets are summarized in Table S
To generate IID splits, we randomly divide training datapoints and assign them to devices. For non-III splits, we utilize the Dirichlet distribution as (Yurochkin et al. 2019). Firstly, a vector of size equal to the number of classes are drawn using Dirichlet distribution for each device. These vectors correspond to class priors per devices. Then one label sampled based on these vectors for each device and an image is sampled without replacement based on the label. This process is repeated until all datapoints are assigned to devices. The procedure allows the label ratios of each device to follow a Dirichlet distribution. The hyperparameter of Dirichlet distribution corresponds to statistical heterogeneity level in the device datapoints. Overall, for a 100 device experiment, each device has 600, 480, 500 and 500 datapoints in MNIST, EMNIST-L. CIFAR-10 and CIFAR- 1-00 respectively. For these datasets, three different federated settings are generated including an IID and two non-IID Dirichlet settings with 66 and 33 priors. Figure shows the heterogeneity levels for MNIST dataset in
13

---

Published as a conference paper at ICLR 2021
these different settings. The amount of most occurred class labels that consume 40%, 60% and 80% of device data are shown in the histogram plots. For example, every class label is equally represented in IID setting hence 4. 6 and 8 classes occupy 40%, 60%, and 80% of the local datapoints for each device. If we consider non-Ill> settings, we see 80% of local data belongs to mostly 4 or 5 different classes for Dirichlet .6; and or 4 different classes for Dirichlet 33 settings.
To generate unbalanced data, we sample datapoint amounts from a lognormall distribution. Controlling the variance of lognormal distribution gives unbalanced data per devices. For instance, in CIFAR-IO, balanced and unbalanced data settings have standard deviation of data amounts among devices as 0 and 0.3 respectively.
LEAF Caldas et al. 2018 is used to generate the Shakespeare dataset used in this work. The LEAF framework allows to generate IID as well as non-IID federated settings, The non-IID dataset the natural split of Shakespeare where each device corresponds to a role and the local dataset contains this role's sentences. The IID dataset is generated by combining the sentences from all roles and randomly dividing them into devices. In this work, we consider 100 devices and restrict number of datapoints per device to 2000.
Models. We use fully connected neural network architectures for MNIST and EMNIST-L. Both models take input images as a vector of 784 dimensions followed by 2 hidden layers and a final softmax layer. The number of neurons in the hidden layers are 200 and 100 for MNIST and EMNIST- respectively. These models achieve 98.4% and 95.0% test accuracy in MNIST and EMNIST-L trained on datapoints from all devices. The model considered for MNIST is the same model used in original FedAvg work (McMahan et al. 2017).
For CIFAR-10 10 and CIFAR- 100, we use CNN consisting of two convolutional layers with 64 5 x 5 filters, two x 2 max pooling layers, two fully connected layers with 394 and 192 neurons, and finally a softmax layer. The models achieve 85.2% and 55.3% test accuracy in CIFAR-10 and CIFAR- 100 respectively. Our CNN model is similar to the used for CIFAR-10 in the original FedAvg work (McMahan et al. 2017]. except that we don't use Batch Normalization layers.
For the next character prediction task (Shakespeare), we use an LSTM. The model converts an 80 character long input sequence to x sequence using an embedding. This sequence is fed two layer LSTM with hidden size of 100 units. The output of stacked LSTM is passed to softmax layer. Overall, this architecture achieves a test accuracy of 50.8% and 51.2% in IID and non-IID settings, respectively, if trained on data from all devices. We report both III) and non-llI) performance here because the datasets are randomly regenerated out of the whole Shakespeare writing hence train and test split is different for both cases. This Neural Network model is the same model used in the original FedProx study (Li et al. 2020a).
In passing, we note here that, we are not after state of the art model performances for these datasets, our aim is to compare the performances of these models in federated setting using FedDyn and other baselines.
Hyperparameters. We consider different hyperparameter configurations for different setups and datasets. For all the experiments, we fix batch size as 50 for MNIST, CIFAR-10, CIFAR-100 and EMNIST-L datasets and as 100 for Shakespeare dataset.
We note here that μr, a and K hyperparameters respectively. K is the equivalent of epoch for SCAFFOLD algorithm and we searched K values to have the same amount of local computation in other methods. For example, if each device has 500 datapoints, batch size is 50 and epoch is 10, local devices apply 100 SGD steps which is equivalent to K being 100.
used only in FedProx, FedDyn and SCAFFOLD
MNIST. As for the 100 devices, balanced data, full participation setup, hyperparameters are searched for all algorithms in all IID and Dirichlet settings for fixed 100 communication rounds. The search space consists of learning rates in [01], epochs in [10, 20, 50], Kss in [120, 240, 600), μr in .01, .0001] and as in [.001, .01,100000.0..... .03,.... .1.. Weight decay of 10 - is applied to prevent overfitting and no learning rate decay across communications rounds is used. The selected configuration for FedAvg learning rate and 20 epoch: for FedProx is 1 learning rate and .0001 μé; for FedDyn is .1 learning rate, 50 epoch and .01 and for SCAFFOLD is .1 learning rate and 600 K for all IID and Dirichlet settings. These configurations are fixed and their performances are obtained for 500 communication rounds.
14

---

Published as a conference paper at ICLR 2021
For the partial participation, 100 devices, balanced data setup, the selected configuration for FedAvg is .1 learning rate and 10 epoch; for FedProx is .1 learning rate and .0001 μt for FedDyn is .1 learning rate, 50 epoch and .01 a; and for SCAFFOLD is .1 learning rate and 600 K for all IID and Dirichlet settings except that a is chosen to be .03 for 10% IID setting. 0.998 learning rate decay per communication round is used and weight decay of 10-1 is applied to prevent overfitting for all methods.
For the centralized model, we choose learning rate as .1, epoch 150 and learning rate is halved in every 50 epochs.
EMNIST-I- We used similar hyperparameters as in MNIST dataset. The configuration for FedAvg is .1 learning rate and 20 epoch: for FedProx is .1 learning rate and 10 for FedDyn is . learning rate, learning rate and 500 K for all IID and Dirichlet
50 epoch and 0.005 at and for SCAFFOLD full participation settings.
The selected configuration for FedAvg is .1 learning rate and 10 epoch: for FedProx is .1 learning rate and ,0001 μ4; for FedDyn is ,1 learning rate, 50 epoch; and for SCAFFOLD is .1 learning rate and 500 K for all IID and Dirichlet partial settings. a is chosen to .003 for 10% and 1% IID; .005 for 10% Dirichlet 6 and 1% Dirichlet 3 ; .001 for 1% Dirichlet .6 and .01 for 10% Dirichlet 3 settings. 0.998 learning rate decay per communication round used and weight decay of 10-4 is applied to prevent overfitting for all methods.
For the centralized model, we choose learning rate as .1, epoch as 150 and learning rate is halved in every 50 epochs.
CIFAR-1O. The same hyperparameters are applied to all the CIFAR-10 experiments, including: 0.1 for learning rate, 5 for epochs, and 10 for weight decay. The learning rate decay is selected from the range of [0.992, 0.998, 1.0]. The a value is selected from the range of [10 33 1,102, 9,10" ,,10-,10" for
FedDDyn. The las value is selected from the range of [10-2 2, 10-3 10
For the centralized model, we choose learning rate as .1, epoch as 500 and learning rate decay as .992.
CIFAR-100. The same hyperparameters are applied to the CIFAR-100 experiments with 100 de- vices. including: 0.1 for learning rate, 5 for epochs, and 10 3 for weight decay. The learning rate decay is selected from the range of [0.992, 0.998, 1.0]. The a value is selected from the range of [10 3, 1, 10 for FedDyn. The μss value is selected from the range of [10 2, 10 4)
As for 500 device, balanced data, 10% participation, IID setup, .1 learning rate, .0001 14, 10-3 weight decay applied. Epochs in [2. 5] and corresponding Kss in [4,10] searched. as in [.1, 11,, .001] are considered for FedDyn. Epoch of 2 is selected for FedDyn, FedAvg and FedProx. K of 4 is selected for SCAFFOLD. .01 value is selected for FedDyn. The same parameters are chosen for 500 device, balanced data, 10% participation, Dirichlet .3 setup.
As for 100 device, unbalanced data, 10% participation, IID and Dirichlet .3 settings, epoch of is selected for FedDyn, FedAvg and FedProx, K of 20 is selected for SCAFFOLD.. .1 a value is applied for FedDyn. .0001 μ is used in FedProx.
For the centralized model, we choose learning rate as .1, epoch as 500 and learning rate decay as .992.
Shakespeare. As for 100 devices, balanced data, full participation setup, the hyperparameters are searched with all combinations of learning rate in [1], epochs in [1,5]. Kss in [20, 100), jas in [001] and as in 1,001, .009, .01, and no learning rate decay across communications rounds is used. The selected configuration for FedAvg is 1 learning rate and 5 epoch; for FedProx is learning rate, 5 epoch and .0001 μı for FedDyn is learning rate, epoch and .009 a; and for SCAFFOLD is 1 learning rate and 100 K in IID and non IID settings.
01,..10)) .015.. Weight decay of 10 is applied to prevent overfitting
For the partial participation, 100 devices, balanced data setup, we choose 1 learning rate and 5 epoch for FedAvg; learning rate, 5 epoch and .0001 μ for FedProx; learning rate and 100 K for SCAFFOLD; and learning rate and 5 epoch for FedDyn in all cases. a is .015 and .001 for 10% and 1% settings respectively. No learning rate decay is applied for 10% settings and decay of .998 is applied for 1% settings. Weight decay of 10-4 is applied to prevent overfitting.
15

---

Published as a conference paper at ICLR 2021
For the centralized model, we choose learning rate as 1, epoch as 150 and learning rate is halved in every 50 epochs.
Additionally, performed gradient clipping to prevent overflow in weights for all methods. We found out that, this increases stability of algorithms.
Convergence Plots. We give convergence plots of experiments. The convergence plots of moderate and large number of devices in different device distributions are shown in Figure | and 3 for CIFAR- 10 and CIFAR- 100 datasets. Similarly, convergence curves of different participation levels and distributions are plotted in Figure 6 7 T0
10 for all datasets. Finally, Figure 12 and 13 convergence plots for balanced data and unbalance data in different device distributions.
We emphasize that convergence curves show accuracy achieved with respect to rounds communicated. However, the metric we want to minimize, the amount of information transmitted, is not the same as number of communication rounds. For instance, SCAFFOLD transmits two models including state of devices per communication round. This difference is accounted in the tables.
We observed that averaging all device models gives more stable convergence curves hence we report the performance of the average model from all devices in each communication round. We note that we do not modify the algorithms, this part is only for reporting purposes.
Additional experiments stated, we test our algorithm with a more complex model. We consider ResNet18 (He et al. (016) structure on CIFAR-10 IID, 100 devices, balanced data, 10% participation setting. Batch normalization layers have inherent statistics which can be problematic FL. Therefore, we use group normalization (Wu & He. 2018) instead of Batch normalization in ResNet18. The convergence curves are shown in Figure FedDyn still outperforms the baseline methods in a higher capacity model setup.
A.3 a SENSITIVITY ANALYSIS OF FEDDYN
is important parameter of FedDynn Indeed, it is the only hyperparameter of the algorithm when devices have access to an optimization solver. In theory, a balances two problem dependent constants as shown in Theorem 2 Theorem 3 and Theorem 4 Consequently, optimal value of a depends on these constants. Since these constants are independent of T, the value of a does not asymptotically affect convergence rate.
To test sensitivity, we consider 10, IID, 100 devices, 10% participation setting. Figure la shows convergence plots for different configurations while keeping all other parameters constant in FedDynn Figure Tb presents the best achieved test accuracy with respect to different a values. We see that best test performance is obtained when a 10-1, We note that all configurations converge, but some of them converges to better stationary points. This aligns with the theory because we guarantee convergence to a stationary point.
IIFARLD 10%
CIFARIO IDD 10%
0,850
0.825
0.800
0.775
0.750
8.700
0.675
0.001
8.675
0,550
8.650
10
10:2
10
30
Communication Rounds
(a)
(b)
Figure 1: CIFAR- 10 sensitivity analysis of FedDyn.
A.4 COMPARISON TO A FULL PARTICIPATION METHOD
Recently, FedSplit Pathak & Wainwright 2020) is introduced to target non IID data distributions among devices. The work simplifies FL. setting by considering full device participation. It charac-
16

---

Published as a conference paper at ICLR 2021
terizes FedAvg convergence and shows that FedAvg should do only step update per device in each round to achieve global minima if device losses are different. such cases, FedAvg becomes decentralized SGD. After pointing out this inconsistency, FedSplit is given potential solution.
In this work, we aim to solve FL problem with four principle characteristic which are partial participation due to unreliable communication links, massive number of devices, heterogeneous device data and unbalanced data amounts per device. Partial participation is a critical property, because, it is inconceivable that will not be in situation where have all devices participating in each round. However, FedSplit does not support partial participation.
Nevertheless, we adapt FedSplit to partial participation setting with the following changes. If device not active in the current round, its model = zf and its intermediate state 2 (+ frozen. For the server model, we have two options. First option is to keep the server model as average of all device models, x' m kem zi.- which named FedSplit All. Second option is to have the server model the average of only current round's active devices xf |P.l EkEp, 2 which is named as FedSplit Act. In passing, we not claim that these modifications are optimal.
2k 1-1+
For empirical evaluation, we consider CIFAR-10, 10, 100 devices, 100% and 10% participation settings. Figure and 2b show comparison between FedSplit and FedDyn for 100% and 10% participation levels respectively. FedSplit All and FedSplit Act are the same in full participation setting hence shown as one method. We observe that FedDyn performs better than FedSplit in both cases. We see that FedSplit All where the server model averages all device models is significantly underperforming than FedSplit Act where the server only averages active devices. This is due to the fact that the server model is too slow to change when all devices are averaged because most of the devices the same across consecutive rounds. We further note that it might not be easy to get convergence theory of FedSplit in the partial participation setting.
0.750
0.750
0.725
0.725
0.700
0.700
FedDyn
0.675
FedDym
0.75
Tedtallh Act
FodSolttAi
0.500
400
1000
0.50
200
460
800
800
1000
Communication Bounds
Communicatenn Rounds
(a)
(b)
Figure 2: CIFAR- 10 FedSplit and FedDyn comparison in full and 10% participation settings.
A.5 FIGURES OMITTED IN THE MAIN TEXT
Table 3: Datasets
Dataset
Train Samples Amount
Test Samples Amount
CIFAR-10
50000
10000
100
50000
10000
MNIST
60000
10000
EMNIST-L
48000
8000
Shakespeare
200000
40000
17

---

Published as a conference paper at ICLR 2021
Table 4: Number of parameters transmitted relative one round of FedAvg to reach target test accuracy for balanced data and unbalanced data in IID and Dirichlet .3 settings with 10% participation. SCAFFOLD communicates the current model and its associated gradient per round, while others communicate only the current model. As such number of rounds for SCAFFOLD is one half of those reported.
Local Data
Dataset
Accuracy
FedDyn
SCAFFOLD
FedAvg
FedProx
IDD
84.5
637
1852(2.9x)
1000+(>1.6x)
[000+(>1.6x)
CIFAR-10
82.3
240
512(2.1x)
994(4.1x)
825(3.4x)
51.0
522
1854(3.6x)
1000-(>1.9x)
(000+(>1.9x)
CIFAR-100
40.9
159
286(1.8x)
822(5.2
873(5.5x)
Balanced
Dirichlet (.3)
82.5
444
1880(42xx)
1000+(>>.3x)
1000+(>2.3x)
CIFAR-10
80.7
232
594(2.6x)
863(3.7x)
930(4.0x)
51.0
561
1884(3.4x)
(000=(>1.8x)
[000+(2188x)
CIFAR- 100
42.3
170
330(1.9x)
959(5.6x)
882(5.2x)
IID
84.0
1152(3.4x)
[000+(>3.0x)
1000+(>3.0x)
CIFAR-10
82.3
213
548(2.6x)
834(3.9x)
834(3.9x)
53.0
386
1656(4.3x)
1000=(>2.6x)
(000+((2266))
CIFAR-100
48.2
209
800(3.8x)
968(4.6x)
945(4.5x)
Unbalanced
Dirichlet (.3)
82.5
1998(38xx
[000-(>>..9x)
[000+(>11.X)
CIFAR-10
80.1
274
652(2.4x)
893(3.3x)
1000+(>33.x))
52.0
503
1928(3.8x)
1000=(>2.0x)
1000+(>2.0X)
CIFAR- 100
47.3
234
942(4.0x)
871(3.7x)
1000+(>433X)
18

---

Published as a conference paper at ICLR 2021
Table 5: Number of parameters transmitted relative one round of FedAvg to reach target test accuracy for 1% participation regime in the IID, non-lll settings. SCAFFOLD communicates the current model and its associated gradient per round, while others communicate only the current model. As such number of rounds for SCAFFOLD is one half of those reported.
Participation
Datasct
Accuracy
FydDyn
SCAFFOLD
FedAvg
FedProx
IID
82.6
660
(544(.3x)
892(1.4x)
1000+((>1.5x)
CIFAR-10
81.6
543
1150(2.1x)
603(1.1x)
707(1.3x)
39.8
409
1982(4.8x)
428(1.0x)
512(1.3x)
CIFAR-100
38.8
396
1862(4.7x)
392(1.0x)
454(1.1x)
98.3
529
956(L8x)
644(1.2x)
451(0.9x)
MNIST
97.3
145
290(2.0x)
151(1.0))
143(1.0x)
483
1136(2.4x)
826(1.7x)
1000+((2.1x))
EMNIST-L
93.9
210
554(2.6x)
216(1.0x)
238(1.1x)
43,0
170
460(2.7x)
188(11X)
151(0.9))
Shakespeare
42.0
342(2.3x)
149(1.0x)
142(1.0x)
Dirichlet (.6)
81.0
561
1510(2.7x)
977(L.7x)
841(L.5x)
CIFAR- 10
80.0
436
1100(2.5x)
673(1.5x)
623(1.4x)
36.6
355
1996(5.6x)
341(1.0x)
352(1.0x)
CIFAR-10 100
35.6
342
1876(5.5x)
317(0.9x)
342(1.0x)
1%
98.2
486
1502(3.1x)
863(188)
754(1.6x)
MNIST
97.2
180
332(188)
199(1.1x)
166(0.9x)
405
1230(30xx)
504(1.2x)
1000+(>2.5x)
EMNIST-L
93.8
195
576(3.0x)
256(L_3x)
294(1.5x
Dirichlet (.3)
79.0
590
1580(2.7x)
955(1.6x)
738(L.3x)
CIFAR- 10
78.0
452
1272(2.8x)
653(1.4x)
497(1.1x)
36.1
343
1990(5.8x)
317(0.9x)
342(1.0x)
CIFAR-100
35.1
321
1866(5.8x)
294(0.9x)
314(1.0)
98.2
521
954(L88)
951(L88)
974(1.9x)
MNIST
97.2
157
318(2.0x)
169(L.1))
177(1.1))
94.4
442
1860(4.2x)
48I(1.I)
1000+(>2.3x)
EMNIST-L
93.4
241
694(2.9x)
286(1.2x)
279(1.2x)
Non-IID
43.8
158
388(2.5x)
159(1.0x)
153(100))
Shakespeare
42.8
143
318(2.2x)
146(1.0x)
145(1.0x)
data
100
100
200
Utard COATT
20
20
20
30
30
2
100
(a)
(b)
(c)
Figure 3: MNIST- Histogram of device counts whose 40%
3ap.
60%
3b
and 80%
(3c
datapoints
belong to & classes.
19

---

Published as a conference paper at ICLR 2021
Table 6: Number of parameters transmitted relative one round of FedAvg to reach target test accuracy for convex synthetic problem in different types of heterogeneity settings. SCAFFOLD communicates the current model and its associated gradient per round, while others communicate only the current model. As such number of rounds for SCAFFOLD is one half of those reported.
Loss
FedDyn
SCAFFOLD
FedAvg
FedProx
Homogeneous
0.0603
32
70(2.2x)
(36(4.2x)
x9(xx)
Type Hetcrogencous
1.5717
17
88(52x)) 20(12xx) 18(I.1x)
T ype Heterogemeous
0.1205
150
164(1.1x) 274(18x) 275(L8x)
Type Heterogeneous 260(7.6x)
0.0854
34
79(2.3x)
106(3.1x)
CIFARLL HID 1000 Devicus
CIFRRO DiricHet 0.3 1000 Devices
0.8
0.7
0.7
FedDyn
FedByn
0.4
fedfug
0.4
Fed/ug
Fedivox
Fed
0.3
250
500 750 200125015000199000
0.3
250 500 750 1000 5000550000000000
Communiicatin Rounds
Commaniczaion Rounds
(a)
CIRAR10 ID 100 Dovioes
CIFARLO Dirichie 033 100 Devices
0.850
0.550
0.825
0.825
0.800
_0.000
0.775
0.775
0.750
0.750
FosAvg
FodAug
FesProx
FedP nox
400
Communicatio
(c)
(d)
Figure 4: CIFAR-IO- 10- Convergence curves for different 100 and 1000 devices in the IID and Dirichlet (.3) settings with 10% participation level and balanced data.
20

---

Published as a conference paper at ICLR 2021
CIFR100 LD 500 Devices
0.55
QFAR100 Dirichis 0.3 Devices
Feddyn
SCAFFOLD
Feditoo
0..00
0.35
0.25
FedDyn
SCAFFOLD
0.30
0.30
0.25
1806
0.25
Communicciiion Rounds
Commart commankktionn Rounds
(a)
(b)
0.45
0.45
0.40
0.40
0.33
Feddig
FwdAvg
Fedito
FedProx
0.25
200
400
600
800
1000
200
400
800
1000
Figure 5: CIFAR-100 100- Convergence curves for different 100 and 500 devices in the IID and Dirichlet (.3) settings with 10% participation level and balanced data.
21

---

Published as a conference paper at ICLR 2021
GFFALO HD 100%
CIFRRO ID DIrICNNE 0.6 100%
QFARLO Dricht 100%
0.027
0.825
0.000
0.000
0.03
0.775
0.775
0.775
0.750
0.750
0.750
0.725
FedDyn
f 0.725
TedDyn
0.725
FedDym SCAFFOLD
0.700
SCAFFOLD
0.700
SCAFPOLD
0.700
FesAvg
FedAug
FedAug
FedPrix
TedPPrx moc
Fed
200
4.00
800
1000
0.650
200
400
600
800
1000
200
400
600
800
1000
(b)
GIFRRI 10%
OFARLO Drichlet
OFARLO HD Dirchiet 6.3 10%
0.150
0.850
0.850
0.825
0.825
0.825
0.800
00800
0.800
0.775
0.750
FedDyn
TedDyn
FedDyn
SCAFFOLD
LC
SCAFFOLD
0.675
Fedkyg
a.mo
0.50
0,650
Communicatin Rounds
Communicatin Rounds
Communisaton Hounds
(d)
(c)
(f)
CIFAR1O 10
OFAR1O ID Dirchlet
OFAR1O Dirichet
0.850
0.775
0,750
0.750
FeeDyn
0.725
FodDyn
0.725
FodDyn SCN TOLD
0,700
SCAFTOLD
0.700
SCAFToLD
0.700
0.675
FesAvg
FesProx
0475
Feshing
FedPhox
0.75
FedPrix
FodAvg
0.650
200
400
600
500
1000
0.500
200
400
600
800
1000
0.650
0
200
400
600
200
1000
Communication Rounds
Communication Rounds
Communication Rounds
(g)
(h)
Figure 6: CIFAR- 10- Convergence curves for participation fractions ranging from 100% to 10% to 1 % the IID, Dirichlet (.6) and Dirichlet (.3) settings with 100 devices and balanced data.
22

---

Published as a conference paper at ICLR 2021
CIFAR100 100%
CIFARLOD t0 OtichNt 0.6 100%
CIFARLOO Dzrchat 1008
0.55
0.55
g
0..43
0.40
0.40
0.35
Fedlyn SCAFFOLD
0.35
0.35
FedDyn
SCAFFOLD
SCAFTOLD
0.30
0.30
0.30
0.25
0.25
Communication Rounds
Communication
Communication Rounds
(b)
(c)
0.50
0.50
0.50
0.45
0.45
0.45
0.40
0.40
0.40
0.35
0.35
Fedling
Fed/ig
FosAvg
Fedrrox
Fedd Prxx
FedProx
0.25
200
400
600
800
1000
0
200
4.00
600
800
1000
0.25
200
400
600
800
1000
Communication
Cxmmaritation
Commanica
(d)
0.55
DI HD 2%
0.55
CIFARIDO ID Difichitt 0.6 18
0.55
CIFAR100 IID Difichtet 0.3
FodDyn
FodDyn
FodDyn
0.50
SCAFFOLD
0.50
SCAFFOLD
0.50
SCAFFOLD
FedAvg
Feddvg
Fedding
0.45
FodProx
0.45
FodProx
0.45
FedFFrx
0.30
0.30
0.30
6.25
200
430
600
800
1000
6.25
0
200
450
600
800
2000
0.25
200
400
600
800
1000
Communication Rounds
Communication Rounds
Commanication Rounds
(h)
Figure 7: CIFAR- 100- Convergence curves for participation fractions ranging from 100% to 10% to % in the IID, Dirichlet (.6) and Dirichlet (.3) settings with 100 devices and balanced data.
23

---

Published as a conference paper at ICLR 2021
0.990
MMST 10 100%
0.990
MN&T DiricNet 100%
0.990
MMST 0.ric 100%
Accurneyy
0.950
Lest Accunats
0.975
Text
Fediyn
0.970
FedDyn SCAFFOLD
Fedbyn
SC
SCAFFOLD
0.955
FedAug
0.965
PedAug
0.965
Fedhig
FodProx
FodProx
FodProx
0.980
400
500
6,950
100
200
300
4.00
505
0.900
100
Communication Rounds
Communical ion Rounds
Communication Rounds
(a)
(b)
(c)
0.500
NNST IDD 10%6
0.900
MNST DiiiHNt 0.6 10%
0.990
MNST Diichit 0.3 10%
0.905
0.901
2.0.50
0.5500
2.0580
0.975
Ted
FedDyn
FedDyn
TedDyn SCAFOLDD
SCAFFOLD
SCAFFOLD
FesAug
FodAvg
FodAug
FedProx
TedPPros
Fed
0360
200
400
6.0
500
1000
200
400
500
500
1000
0
200
400
600
200
1000
commancaaionn
Communication
Communication
(d)
0.960
MMST 1%
0.500
0.500
MNIST Dirchlet
0.085
0.985
0.985
0.900
Po.90
0.480
Tett
8.975
0.975
0.975
0.570
0.700
FodDwn
0.570
0.965
0365
TedAug
0365
0.960
0.60
0.90
Communication Rounds
Communication Rounds
Communicatio Rounds
(h)
(i)
Figure 8: MNIST- Convergence curves for participation fractions ranging from 100% to 10% to 1% in the IID, Dirichlet (.6) and Dirichlet (.3) settings with 100 devices and balanced data.
24

---

Published as a conference paper at ICLR 2021
0.96
EMNIST ID 100%
EMNIST Dirichiet 0.6 100%
0.96
EMNIST Dirichet 0.3 100%
0.94
0.94
0.94
Tost ACCUISS
0.90
0.90
0.90
Teas
FeoDyn
FedDyn
0.88
0.88
0.88
Fackug
PecAug FedProx
PedAog
0.86
FeoProx
FedPrrx
100
200
300
400
500
100
200
300
400
500
100
200
300
400
500
Communicatioo Nounds
Commarication Rounds
Communicatton Rounds
(a)
(c)
0.95
EMMSST HD 10%
0.95
ENNIST Dischee 0.5 19%
0.96
EMINST Dirahiee 0.3 10%
Accurery
0.92
0,92
0.92
0.90
1eal
FodDyn SCAFFOLD
FedDyn SCAFFOLD
FodDyn
0.88
0.88
0.88
SCAFFOLD
Feddug
FedAvg
FedAvg
0.86
FedProx
0.86
0.86
600
600
800
1000
200
400
600
1000
400
600
800
1000
Communication Rounds
Communication Rounds
Communication Rounds
(d)
(c)
(f)
ENMST 1%
EMNIST Dinchlet 1%
ENNIST Dirchlet 0.3
0.94
0.94
0.94
Accurccy
Acurneyy
Rccunccy
0.90
0.90
0.90
Fedayn
Fed
FwdDyn
SCAFFOLD
SCAFFOLD
Fedfig
0.86
Fedihox
0.86
0.86
FedProx
800
Communication
Communication
Commanication
(h)
Figure 9: EMNIST-L- Convergence curves for participation fractions ranging from 100% to 10% to 1% in the IID, Dirichlet (.6) and Dirichlet (.3) settings with 100 devices and balanced data.
25

---

Published as a conference paper at ICLR 2021
Shicespeare HD 100%
0.55
Stakespeare Non-lID 100%
0.50
0.50
0.45
0.45
Teat
0.35
0.30
FedDyn SCAFFOLD
0.30
FeeDyn
SCAFFOLD
0.25
FesRvv
0.25
FecAvg
FedProx
FeoProx
20
40
60
60
100
120
140
20
40
60
100
120 140
Communication Bouncs
Communication Rouncs
(a)
(b)
0.55
Shakespcare HD 10%
0:55
Shakesspore Non HD 19%
0.50
0.50
Accurs
Teck Accumsc
0.40
0:40
Fedbyn SCAPOOLD
0.30
SCAFOOLD
FedDyn
0.25
Fudling
0.25
FedAvg
FodProx
FedProx
50
1.00
150
250
0.20
100
150
200
250
Communication
Communication Rounds
Shakespeare 1D 1%
Shakespeare Nen-IDD 1%
0.55
0.55
0.445
0.40
0.40
Test
0.35
0.30
FedDyn SCAFFOLD
0.30
SCAFFOLD
FedDyn
0.25
Fedling
0.25
FedAvg
FedProx
FedProx
0.20
150 Communication Rounds
Communicatin
(e)
Figure 10: Shakespeare- Convergence curves for participation fractions ranging from 100% to 10% 1% in the IID, and non-lID settings with 100 devices and balanced data.
CIPAR10 ID 10% Resket18
0.85
Accunety
Dyd
SCAFFOLD
0.65
FadAvg
0.60
0
200
400
600
800
1000
Communication Rounds
(a)
Figure 11: Convergence curves for ResNet18 with 1000 devices and balanced data.
26

---

Published as a conference paper at ICLR 2021
OFARLO ID (Unbalanoedi 100 Devicos
0.825
0,800
0.800
0.775
0.775
0,750
0.710
0.725
FedDyn
0.723
FodDyn
0.700
SCAFFOLD
0.700
FesArg
Fedhvg
TedPPrx
FedProx
0.650
1000
(a)
(b)
GFAR18 HD (alanced) 100 Dexices
CIFAR1D ID D richet (Balaned)) 100 Decies
0,850
0.850
0.825
0.825
0.800
0.800
0.715
0.750
TedDyn
FedByn
SCAFFOLD
6.700
SCATTOLD
FesAvg
0.675
Foddug
0,550
0.650
800
1000
Communicaten Hounds
Communicall on Rounds
(c)
Figure 12: CIFAR-10. 10- Convergence curves for balanced and unbalanced data distributions with 10% participation level as well as 100 devices in the IID and Dirichlet (.3) settings.
QIEAROM Dirteviet 0 (Unoalancedi 100 Device
0.55
0.50
0.45
0.45
0.40
0.40
0:35
SCAFFOLDD
0.30
Feddug
0.30
FedProx
0.5
Communication Rounds
(a)
(b)
0.60
OFAR100 IDD (Ralancedi 100 Devires
0.00
CIEAR100 HD Dinchint 3.1 (Balanced) 102 Desires
0.50
0.50
0.40
0.40
Fediyn
SCAFFOLD
0.30
Fedfug
0.30
FedAig
Fedihox
FeaProx
0.25
200
45c
6ön
850
1000
Commurication Rounds
(c)
(d)
Figure 13: CIFAR-100- Convergence curves for balanced and unbalanced data distributions with 10% participation level as well as 100 devices the IID and Dirichlet (.3) settings.
27

---

Published as a conference paper at ICLR 2021
B PROOF
B.I CONVEX ANALYSIS
Definition 1. La is L smooth if
[VLx(v) VL*(D)II S L| yll Vo, y
Smoothness implies the following quadratic bound,
L
(x S (x(x) (VLa(w), y x) 2 11y x01 Vx, y
(4)
If (a 8 are convex and L smooth we have
Σ
[VLx(x) - vLx(x=)11 S {(x)) - Elxr,) Vx
(5)
20m
kE[mi
L || x/| Vx, y 2
(VLx(z), 3) S -L((z) Lx(())
(6)
where ((x) m
Em (x) and V((x..) O.
We state convergence as,
Theorem 2. For convex and L. smooth (Tx) Im functions and > 25I, Algorithm
saatisfies
E
T T-1
Σ
7t
e(0.))
S 10a 1000 -0.11
1-00 m 1
Σ IIZZato)1P)
P a
m kE(m)
1=u
where 7t + EkEP, 0% 0. arg min (0))
If / p. we get the statement in Theorem Throughout the proof, we utilize similar techniques as in SCAFFOLD (Karimireddy et al. (019) convergence. We define a set of variables which are useful in the analysis. Algorithm I ffreezes 0g and its gradients if the device not active.
Let's define virtual (0)) variables
0% arg min LA (0) (
-11-00011
a = 0'-10
Vk E [m],
We see that 0 0 if k E Pt and 0 doesn't 't depend on Pe. First order condition in Eq. and in device optimization give
0. 0--1 0
1 (V (O.)) Ak [m]; 0% 0 1 ( -V Ak P.
0¹ consists of active device average and gradient parts. Let's express active device average and its relation with the server model as,
Σ 0
>'= = o¹ h'
(9)
kEP.
Due to linear update of L h state in the server becomes as h' 1 m Exe(m) (L)
Let's define some quantities that we would like control.
C Σ (IV),(0 (L. 6 kE[m]
Σ AE[m)
E - 112
m
m
C. tracks how well local gradients of device models approximate the gradient of optimal model. models converge to 0.. C, will be 0. e, keeps track of how much local models change compared to average of device models from previous round. Again, upon convergence e, will be O.
After these definitions, Theorem can be
direct consequence of the following Lemma,
28

---

Published as a conference paper at ICLR 2021
Lemma 1. For convex and smooth {L k functions, if 2 25L, Algorithm satiisies
El 0.11 nC2 - E 0.11 kCt-1 E (((7--1) -E(0-)
L+a where K 8 a a² 2012 Ku 2 a² 2000--000 a² a=-201,2 2012
Lemma D can be telescoped in the following way,
Ko - - (B 0.11 --112++003 +x00-1) -
-0.11 + -6.12--0011-- kC,)
T
KO Σ 1 - (B1 0.112 + kCo) - (Ell>" - -0.11 xCT)
If 2 25L, Kg and x. become positive. By definition, we also have C sequences as positive. Eliminating negative terms RHS gives,
- s Ell 0.11 + nCu
KO
Applying Jensen on LHS gives.
E
E
1 E(O.)
S
1 T kg
(1h -0.12 + +nC))= :0 =0())
which proves the statement in Theorem
Similar to fundamental gradient descent analysis, | 0.11 l is expressed as // - 7--1 +
and expanded in the proof of Lemma The resulting expression has ( 1 and |1 - 11
terms. To tackle these extra terms, we state the following Lemmas and prove long ones at the end.
Lemma 2. Algorithm satisfies
E [T' -
Σ E k[[m]
VL2 [b))
Proof.
E [7'
11
E
Σ 0%
0--1 h-11
0 r-1
1 h 2
a
a
kEP.
REP.
E
(VLx VL+(O() - h 1
aP
NEP
(VL (L) h2- 1ー1)
kEP.
Σ VL,(0t (L, - h hh-1) am
Σ kE(m)
(
am
k[[m]
where first equation is from definition in Eq. The following equations come from Eq. and o. 0% if E P, respectively. Fifth equation is due to taking expectation while conditioning on randomness before time t. If conditioned on randomness prior to f, every variable except P. is revealed and each device is selected with probability P. Last one is due definition of m
h' 1 m ΣtE(m) (O n
Similarly, 1| - is bounded with the following.
Lemma 3. Algorithm satisfies
El
111 < 6
29

---

Published as a conference paper at ICLR 2021
Proof.
Elly' - 7-
1 =E
Σ
(0%
- P
Σ kEPt
110% - 11
0 - --1
kEP,
REPt
P
Σ
0
= C
P m
ke|m]
where first equality comes from Eq. The following inequality applies Jensen. Remaining relations
are due to 0- 0 if k E P., taking expectation by conditioning on randomness before time t and definition of +.-
We need to further bound excess term arising in Lemma 3 We introduce two more Lemmas to handle this term.
Lemma 4, For convex and L smooth {== functions, D Aaatississsssteetaataa
satisfies
(1-AL3
1 C--1 8L
1
a² E S 5
e(0-))
a
Lemma 5. For convex and Li smooth {I functions, Algorithm 7 satissies
P C. S (1-P) m
P er + 4L P E (((7--1)- {(0.)]
C- C--1+ 22
m
m
E [[((7--)) - [(0.)] terms constitute LHS of the telescopic sum. Let's express 1 0. 112 term as,
Ely - - - 0, + + -7 111
=E|la-1 0.11 +2 K7
00,77
Elly - 112
-Ell - 0.112
2
Σ E (7 0.: -VL(((()) + =E1l>' ---211"
am
kE[m]
-EIl -0,11 +
12
2
E (x(0,)- - ) 2 010 - 71-
am
kE(m]
+ E 11
(( La Elly 111
= -Elly
0.1 11
(10)
where we first expand the square term and use Lemma 2 Following inequality is due to Inq. 6
Let's scale Lemma 4 and 5 with a a= coefficients are positive due to the condition on a. Summing Inq. T0 Lemma scaled versions of
Lta Lta and 8 a 2012 respectively. We note that the
Lemma and gives the statement in Lemma D
We give the omitted proofs here.
Lemma 6. V(Ør}ī= Rd, triangular inequality satisfies
a
Σg
2
V
==1
j=1
Proof.
2 03
Using Jensen we get,
1 n
Σド= |0,112
Multiplying both sides with n² gives the
n
inequality. O
Lemma 7. Algorithm I satisfies
E I 1 Ct
30

---

Published as a conference paper at ICLR 2021
Proof.
E
hh
=E
Σ [m[m]
=E 1 Σ m ke|m/
(VL(())-VV<(0.)))
- VL)(
E ( [0.(
m kE|m]
First equality is due server update rule of h vector; second adds (Ve(0.) =0); third applies Jensen Inq.: and last one is the definition of C.. J
Proof of Lemma 4
Et.
1
E
0
11
1 m
Σ
E
0
1 hh a
m
KE [m]]
KE
[m(m
1 1
E
V (0% vLx(0)) - 11
a² m
kc(m]
1 1
(O (L.(0.) (L. VLL(T ) VLL((()) - 112
22 m7
km(m]
4 41 Σ
VL (0) ) VL.(0-)1
EIV - (L.))))1
0 m k[(m)
a² m kE(m)
4 1 Σ V (0)) (
4
+ a m
+
El E11h"-111
a
k[|m]
4 1
4 Σ
V VLL(0,112
EI|VLa(T*")) - (O.)))
a m7
a² m kE(m)
kE[m]
+
4
1
E
VIL(T )11 + a Cz-1 VL (0,)
4
a m
KE kE|ma
8 C
4L2
8L /
- [(0.)]
a
where first and second come from Eq.
g and Following inequalities come from Lemma 6 7
smoothness and Inq. Rearranging terms gives the Lemma.
Proof of Lemma 5
C.
Σ
( - (0.)1
kEIm]
P
EIV - (L. P1
Σ E - (L.
m
m
M m k6(m]
kE[m]
P
P Σ (0') - VIN("')) -V
m
m m kEim
P
2P 1
Σ ( VLa(>~-111
m
m m kE/mJ
2P 1
V (O.(1
m
kE[m]
P
C 1,-I+
2L2P
Ex +
2P 1
Σ EIV - (L.(1))
kE[m]
P
2LPP
4LP
C,-1+
+
62 +
E. (((
-
31

---

Published as a conference paper at ICLR 2021
where first equality comes from taking expectation with respect to Pæ: second equality comes from definition of Ct. Inequalities follow from Lemma smoothness and Inq. respectively.
B.2 STRONGLY CONVEX ANALYSIS
We state convergence for μ strongly convex and L smooth { functions as,
Theorem 3. For y strongly convex and smooth {L functions and Z max 15 30L). Algorithm 7 satisfies
E
e
-e(0.) -
e(0.)
1 -- 200r|100 -0.11= 400
m Pa
1 Σ [V
R
t=
kE/m)
where 7t $ kEP,, f% r= (1 (1+ #) R
T-1 Et t= r², 0, = arg min {(O).
0
If max (5 μr, 30I) we get the statement in Theorem variables defined in Eq.
We will use the same (0)), r Ct c
With these definitions in mind, Theorem 3 can be seen as a direct consequence of the following Lemma,
Lemma 8. For μ strongly convex and L smooth {Lx )m functions, if max 14, 30L).
Algorithm 7 satisfies
r (Elh" - 0.11² + kC2) S E 1-1 0.11 +
- -o [e((] {(0))
where 8m((L-a) Ku 2a P+20" Pu-2a 2ai my 400 2P P-0-0007 P00 mpp 80t PM
0z
a a² PP m² 20aL2 - Pp, #)
Let's multiply Lemma g with 1 and telescope as,
Kur
18(7 "()==1)= E(0.) --1 (Ell 0,11 + kx((1) r² (Ellr' -0.12 + KC,)
T
10(7 - {(.)) )] s (Elh> 1.12 2 + nCb) -ht (Eli - 0111 xCC)
Ko
If o 2 max 14, 30T.), Ki and i become positive. Dividing both sides with R = - ,d and eliminating negative terms on RHS gives,
T
1 - (Eih - 0.11 + +nC))
E - - & R
KO R
Applying Jensen on LHS gives,
i
x-1 ((0.)
S
R kip (11 0.11 +Coo)
R
We have π.
r-1
..
Combining two inequalities, we get,
1
) ((0.)
E.
-0.11 + xCo) T Ro (17
R
which proves the statement in Theorem
The proof of Lemma 8 is similar to the convex analysis. We generalize In. c to strongly convex functions for L m are a strongly convex and L smooth as,
- (VVL y) < (z) + (x( +
2 [|
zx|2
H
x y11
Vx, y. z
(11)
2
32

---

Published as a conference paper at ICLR 2021
Since strongly convex functions convex functions and we only change In. 6 directly
Lemma 2
3
and
5 Let's rewrite 1|
0xll expression as,
E 0.1
= -- 0, +
|2
=Fll>'1 - 0.1 + 2
0., - -p(-1) Elly -/1-111
=
11 + 2
E
0.. -VLx(())))) + +E -11-11
am
kE/m]
2 Σ E (+.) (7
L _
=10% -7--111
1100 0 0.13
0.71
kE|m]
+ E
1x + E -12
-EIly 1-1 1 E [1( - e(o.)) + --6
L
μ 1
El 0.11
kE|m]
+ Bly - 11
SEIl 0 11 -
- + -
L
Elnn' - -0
a
+ B
'12
(12)
where we first expand the square term and use Lemma
Following inequalities use Inq. II and
Lemma 9 Rearranging In. 12 gives.
(1
L c + Elyy - 112 - [(0.)] + 11 a E 0. 12 < E 0.11²
a
(13)
Let's define x P a² Pp a²mp 20a 4L'mp 20L3 Let's scale Lemma and 5 with Pa+ and 8m(L+a)(a+1) respectively. We note that the coefficients are positive due to the condition gives the statement in Lemma Summing Inq.
13 Lemma scaled versions of Lemma and
We give Lemma and its proof here.
Lemma 9, Algorithm satisfies
E 0.12 -EIl - -0,11
kE(m)
Proof.
2
-
-0
=E'
Σ (0)
0.)
S
10%
0.11?
E
0 1
0,
1
kEP,
LEE:
LkEP,
E
0
0.
m
kE[m]
where first equality comes from Eq.
g The following inequality applies Jensen. Remaining relations
are due to 0 = 0 if E Pr and taking expectation by conditioning on randomness before time t. Rearranging the terms gives the statement Lemma.
B.3 NONCONVEX ANALYSIS
We state convergence for nonconvex I. smooth [ as, Theorem 4, For nonconvex and L smooth {Lx 1m functions and a: 2 20L p. Algorithm 7 satisfies
E T 1ee 1 <
1 1/
3a (l(0") f.) + 307,3 1 Pa m
Σ E F
0/
=0
kg[m
where nt EkEp, 0% l, min (()).
33

---

Published as a conference paper at ICLR 2021
If p. we get the statement in Theorem We will use (0)) and 7 variables as defined Eq. Since we aim to find stationary in the nonconvex case, let's define new C₁ and keep the
same as,
C
E REIM
-
- >113, E
Σ 11 REIm]
m
Similarly, Ct tracks how well local models approximate the current active device average. Upon convergence C2 and e will be O.
Theorem can be seen as a direct consequence of the following Lemma, Lemma 10. For L smooth } mm functions, if 2 20L p, Algorithm satisfies
E [(((>>)] kC, S [[(((--)]]] + kC Kgg |e(r""))
where K = 4 patppat- 2m-P Ko 20
-2 -00L-"--2---0 3212 161 2 22
22p2 -212- 2m + 16 - 20
Lemma 10 can be telescoped as,
KgE |((()~ = (E [(((--1)] -4 + xC,-1) - (E (E(((7)) - + k(C)
T
E
vE(T">>)' |1 s E [(G))] - -. nCo) - (E(((T)) - xxTT)
If 20L we have Ko and positive quantities. By definition, we also have C₁ sequences as positive. Eliminating negative terms on RHS and summing over time give,
E T
||?
1 Ko
E(00) la
E10 -011
17
ke|ml
which proves the statement Theorem
The proof of Lemma 10 builds on Inq. where we upper bound e(>²) with E()(-1). Inq. gives on RHS. We state a Lemmas to tackle these terms. We note here that Lemma 2 and 3 holds since the same as in convex case.
(7* - and V
To bound excess é, term, we introduce two more Lemmas as
Lemma 11. For L smooth {= functions, Algorithm satisfies
m.
(I- (1-41" 11-41211
4L2 a
S 8L2 a
C.-1
[e( |
a
Lemma 12. For L smooth {Lx) functions, Algorithm |satisfies
C. < 2 m P
2m p Ct + 2m p Et + 2 m7 E' 11 - 112
Using Inq. 4 we get,
L
E [[(rr)]] E [e(r
1]]
Ell - 1112 [(V((T 1,,'' ---1
2
Σ -VZn )
E
V 1-1
Ac(m)
1
1 (VL(('') - VLa(>(-1))
E
E ()(("=-)\1"
2a
m
2a
kE(m)
1
Σ
F
(l.) - \/n(
1
F )
2a
2a
kE[m)
34

---

Published as a conference paper at ICLR 2021
1
S
E
(14)
2a
2a
where first equality uses Lemma? Jensen Inq. and smoothness.
2
The following inequalities are due to (a. b) - b1bb+a) 2al2-13 ||a|]?
Let's define 2 = p²p² - 32L 16L2Pm - 200 and scale Lemma 12 and
11 with
20 p... 2m
L. + 20 p and 22 = 2 Lta respectively. We note that the coefficients are positive due to
2m
21 2
2
the condition on a. Summing Inq. [4] scaled versions of Lemma 3
and 12 gives the statement in
Lemma 10
Lastly, note that the convergence analysis is given with respect to L.2 norm in the gradients.
L2 norm arises in the analysis because In. 4 has L2 norm due to our definition of smoothness. Furthermore, the analysis can be extended to different norms. To do so, smoothness needs to be defined with respect to primal and dual norms as in Eq. 3 in Nesterov et al. (2020).
We give the omitted proofs here.
Proof of Lemma
11
6t.
1
Σ
E
- 11-
1
Σ
E
p--
1 α
m
m
KE [m]]
KE [m]]
1 1
E V 1) (0)) - -2' 11
a²
kE[m]
1 1
V VLa(>~-1 VLW -
h²' 112
a² m
kE(m)
4
(O )) VLN || v² kE[m)
Σ
EI - -
a2
kE [m]
V )11 EIVE( - h 112
+
4 1
4 Σ VI - (L.(1()12
E VL2 (0 1- VLL(7 (- 112 +
a m
a² m
Ke
kE/ml
4
41 Σ -
E "
a² m
kE[m]
8L2 a²
2
4 o
C--1+
+
a²
where first, second and third come from definition of e,, Eq. 9 and 8 The following inequalities are due to Lemma Jensen Inq. and smoothness. Rearranging terms gives the Lemma.
Proof of Lemma
12
C. m
1
Σ
7112=
1
Σ
0
7-1 + x-1 - -2-12
m
KE [m]
AE[m]
1
P
1
0
- + |+ 2m P
Σ
2m P
m
p
m
KE
[m]
[m|m
P
P
1
+
E110%
122
m
2m
kE[m)
P
+
P
1
0 -1 1 + (1
2m P
Elly" - 1111
m
2m
P
P
kc(m]
P
P
P
2m - P
+
6 +
C--1+ +
[1
Flll - -1111
m
2m
P
m
2m P
P
35

---

Published as a conference paper at ICLR 2021
where we start with definition of C.. First inequality is due ||a + b1l² I (1 + 2) ||a|| (1+ ||b|| for 0. The following equality takes expectation conditioned on randomness before time Since each device is selected with probability f. 0% a random variable that equal 0 with probability &. Otherwise, it is 0%-1_ Final equality due to definitions of c and Ct..J
m
36


Reviews:
[{"review_id": "rjFhSoSae8n", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes a new optimization method named FedDyn to handle data heterogeneity inherent in FL via a dynamic regularization. Such a dynamic regularization modifies each local objective by adding a linear and quadratic term that makes the local stationary point is asymptotically consistent with that of global objectives. The authors prove convergence results for FedDyn in both general convex and non-convex cases and test FedDyn on synthetic and real-world datasets. \n\nPros:\n1. The paper is well written and easy to follow. All proof seems correct.\n2. The experiment setup follows many previous works, which facilitate comparisons, and I appreciate a lot. Besides, a lot of details are given, which helps reproduction.\n3. The proposed method has great superiority over other baselines in communication efficiency, shown by a lot of experiment results.\n\nCons:\n1. I think the author could also analyze FedDyn in a strongly-convex case since in that well-conditioned case the convergence performance of FedDyn could give more insights for researchers. I expect FedDyn would converge to the optima with a rate exponential in communication rounds. \n2. The author declare that FedDyn has great advantages over competing methods in cases of a large number of devices. However, from the main theorem, I couldn't figure out the reason.\n3. The author declare that FedDyn is more robust to unbalanced data than baseline methods. From experiments, it seems correct as  FedDyn achieves a larger factor of gains over others in unbalanced data. However, again, no theoretical analysis is given. The main theorem is about the convergence of balance data in terms of communication rounds not about the effect of unbalance data.\n4. Since the proof mainly follows from that of SCAFFOLD and many empirical findings have no theoretical support, I would regard the main contribution as the algorithm itself. The experiment indeed did well, however, there is still some shortcomings. There are other algorithms proposed to (or able to) handle data heterogeneity like FedPD [1], FedSplit [2] and VRL-SGD [3]. However, the authors didn’t consider these competing methods and even didn’t mention them.\n\n[1] Zhang, Xinwei, et al. \"FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data.\" arXiv preprint arXiv:2005.11418 (2020).\n[2] Pathak R, Wainwright M J. FedSplit: An algorithmic framework for fast federated optimization[J]. arXiv preprint arXiv:2005.05238, 2020.\n[3] Liang, Xianfeng, et al. \"Variance reduced local SGD with lower communication complexity.\" arXiv preprint arXiv:1912.12844 (2019).\n\nOther points:\n1. The description of SCAFFOLD’s linear term seems imprecise. The subtracted term is not $\\frac{1}{m} \\sum_{k \\in[m]} \\nabla L_{k}\\left(\\boldsymbol{\\theta}_{k}^{t}\\right)$, since SCAFFOLD only activates a small fraction of devices and this term is impossible to compute. But I can understand what the author wants to convey: their affine function saves communication costs.\n2. The authors mention that at each communication round SCAFFOLD communicates the current model and its associated gradient while others communicate only the former. So, if I want to say FedDyn is more effective in saving communication rounds, I would expect it to achieve at least 2x gains over SCAFFOLD. However, this is a rare case when the participation rate is 10% (see Table 2). It seems that FedDyn is not so effective in saving communication rounds and the main reason for its effectiveness seems to be that the modified affine function requires once communication per round.\n\n\n--------------------------------------------------------------------\nI have read the authors' responses and almost all my concerns have been well addressed. \nSo I increase my point to 8.", "extra_scores": {}, "extra_text": {}}, {"review_id": "bEnICX0_67", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper proposes FedDyn, a dynamic regularization method for federated learning. In FedDyn, the objective function of each active device in each round is dynamically updated, so that the device optimum is asymptotically consistent with the global optimum. The authors consider both the convex and non-convex case, and give convergence rates with theoretical guarantees. In the convex case the proposed algorithm converges faster than the SOTA algorithm SCAFFOLD. In the experiments the authors show that their algorithm takes less communication cost to achieve the same performance than existing algorithms. \n\nThe main contribution of the paper includes:\n\n- Proposing the dynamic regularization method to tackle the inconsistency issue in federated learning.\n\n- Proving the convergence rate of the proposed algorithm.\n\n- Saving communication cost compared to existing algorithms, both theoretically and experimentally. \n\n\nPros:\n\n- The problem of finding locally consistent distributed algorithms is well motivated. I appreciate the authors' discussion in the introduction. \n\n- The experimental results seem comprehensive. This includes the comparison between FedDyn, SCAFFOLD, FedAvg and FedProx using both synthetic and real datasets in four regimes of interest. The extensive experiments make the claim (saving communication costs) more convincing.  \n\n- Overall the paper is well written. The proposed algorithm is well justified with the discussion on the so-called fundamental dilemma. Also the comparison between the proposed algorithm and SCAAFFOLD makes the claim (saving communication costs) much clearer. \n\n\nCons:\n\n- What can be said about the computational time of each device during each iteration, compared to that of existing algorithms (say, SCAFFOLD)? This is also mentioned on Page 2 (\"This approach, while increasing computation for devices...\"). This would be interesting, although I understand the authors focus on a communication point of view. \n\n- The proof techniques of the main theorem somehow seem standard. I did not check other proofs though.\n\n-----------------------------------------\n\nPost-rebuttal:\n\nI appreciate the authors' feedbacks and I keep my evaluation unchanged.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4SKnM8yBATM", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a new federated learning algorithm called FedDyn, which was motivated by the observation that the local objectives for each device might lead to inconsistent models between devices for heterogeneous data. Such observation is already observed in SCAFFOLD, and this paper further improves over SCAFFOLD with better communication efficiency. Both theoretical convergence rates and empirical  results about communication efficiency are presented to support the advantages of FedDyn methods. \n\nI have the following comments on the paper:\n1. The choice of alpha: it seems alpha is an important hyperparameter which can largely affects the theoretical convergence and empirical efficiency of the proposed FedDyn method. Unfortunately, I could not find much discussion in the paper about alpha: I think how alpha affect the convergence rates, and how alpha is chosen in the empirical results should be discussed, it would be better if the authors could provide an empirical study about the parameter sensitivity in alpha.  \n\n2. How the local objective is optimized: since at each round FedDyn requires each device to solve a local optimization problem which would requires iterative algorithms (such as SGD) to find an approximate solution, how to solve the local optimization problem, and how the accuracy of the local optimization affects theoretical communication efficiency as well as empirical results should be discussed.   \n\n3. Related work: there is a related paper (to appear in NeurIPS 2020) which proposes to solve a similar local objective, it would be good to discuss the differences: FedSplit: an algorithmic framework for fast federated optimization https://arxiv.org/abs/2005.05238.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "4J9CEtjWwj", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "* Context: the authors propose a new distributed optimization algorithm, called FedDyn, to minimize a sum of smooth functions. Their motivation is the context of federated learning, in which each function is the loss of one user corresponding to its data stored locally. The goal is to reduce the communication burden to achieve the true global solution (not an approximation thereof) to a given accuracy.\n\n* Strengths: \n1. The main strength of the algorithm is its robustness to partial collaboration, in which only a subset of the devices participate at every iteration. Indeed, in case of full participation, it is not clear that the algorithm has any advantage in comparison with classical (S)GD-type methods.\n2. The experiments are extensive, well described, and convincing: the method achieves the goal of convergence to a given accuracy with a speed and total communication load competitive w.r.t other methods.\n\n* Weaknesses:\nThe comparison to methods based on local steps, like FedAvg and Scaffold, is somewhat unnatural: these methods go along the idea of doing more computations between communication rounds. This is not the case of the proposed method, which is much closer in spirit to the class of SGD methods. Thus, I find the discussion, which turns around 'correcting' the drawbacks of  methods based on local steps, in particular the fact that FedAvg converges to an approximate solution, convoluted.  Moreover,\n1. No regularizer at the master in the objective function. \n2. The local loss functions must be smooth and in addition, their proximity operators must be computable (see point 5. below).\n3. No comparison to accelerated SGD-type method with accuracy in O(1/T^2) instead of O(1/T).\n4. No discussion of possible linear convergence in case of strong convexity.\n5. alpha, the inverse of the stepsize, must be large (>25L) for Theorem 1 to apply. This shows that the analysis is not tight at all.\n\n* assessment: I think the paper deserves publication, since the proposed algorithm is new, comes with some convergence guarantees, and shows good performance in practice. However, I view the theoretical analysis as a preliminary one, and several aspects would deserve to be investigated more in depth. \n\nMore detailed discussion:\n\n1. There should be a discussion about the literature of SGD type methods. Indeed, partial participation takes the weak form, in Theorem 1, of a subset selected uniformly at random. Some papers by Richtarik et al coming to my mind: \"A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and Coordinate Descent\", \"Unified analysis of stochastic gradient methods for composite convex and smooth optimization\", \"A unified analysis of stochastic gradient methods for nonconvex federated optimization\".\n\n2. You should talk, even very shortly, about the other strategy to decrease the communication burden: compression, see for instance the recent papers and refs therein: \"On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning\", \"Distributed learning with compressed gradient differences\".\n\n3. Further on, one could view the proposed method as GD with unbiased compression: all devices compute their new gradient/model but then with probability P/m it is sent to the master, otherwise it is not sent. It would be good to investigate this relationship more closely.\n\n4. When mentioning prior work on methods using local steps of SGD, which is \"inconsistent with minimizing the global loss\" (or later when mentioning that \"performance degrades in non-IID scenarios\"), you can cite the paper \"From Local SGD to Local Fixed Point Methods for Federated Learning\", ICML 2020, which gives a precise characterization of this \"inconsistency\" in the strongly convex case (Theorem 2.14). For the non-strongly convex case, you can refer to the paper \"Tighter theory for local SGD on identical and heterogeneous data\".\n\n5. Each local computation step is actually a call to the proximity operator of L_k: we have theta_k^t = prox_{L_k/alpha}(theta^{t-1}+grad.L_k(theta_k^{t-1})/alpha). This should be mentioned clearly, as well as the assumption that L_k is proximable (in addition of being smooth). The operation is not a proximal gradient descent step, since there is a + and not a - in front of the gradient. Still, the variable h has the flavor of a dual variable. So, the relationship to proximal splitting algorithms should be investigated, since there seems to be a connection there. \nThinking a bit about this connection, I found out the \"distributed Davis-Yin algorithm\" in the paper \"Distributed Proximal Splitting Algorithms\nwith Rates and Acceleration\", see p. 22 of https://arxiv.org/pdf/2010.00952.pdf. Rewritten in your context, its iteration is:\n|for each device in parallel do\n|\ttheta_k^t = prox_{L_k/alpha}(2.theta^{t-1}-s_k^{t-1}\n|\t\t-grad.L_k(theta^{t-1})/alpha)\n|\ts_k^t = s_k^{t-1} + theta_k^t - theta^{t-1}\n|\ttransmit theta_k^t to server\n|end for\n|s^t = s^{t-1} +  1/m.sum_k (theta_k^t - theta^{t-1})\n|theta^t = s^t\nThere seem to be several differences between this algorithm and yours, but still, they look similar in spirit. It would be very interesting to compare them. \n\n6. In the last two steps of your algorithm (set h^t=..., set theta^t=...) you can remove the multiplication and division by alpha.\n\n7. For the nonconvex case, the rate in Theorem 1 is with respect to the gradient norm. You should tell a bit about the literature, see e.g the discussion in \"Primal-dual accelerated gradient descent with line search for convex and nonconvex optimization problems\" by Nesterov et al.\n\nTypos:\n* convergences -> converges  \n* non convex -> nonconvex\n* Table 1: I guess the \"Acc.\" column is to provide the accuracy. This should be said, since the reader might be confused and think that this is an accelerated method included in the comparison\n* theta_k^infty triangle theta^infty: what does the triangle mean?\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new federated learning algorithm that ensures that the objective function optimized on each device is asymptotically consistent with the global loss function.    Both theoretical analysis and empirical results, evaluating communication efficiency, demonstrate the advantages of the proposed FedDyn method over the baselines. 

All the reviewers recommend accepting the paper. To summarize the discussion:

- R1 mentioned a very recent (NeurIPS 20) related paper and asks several questions. I believe that the authors nicely answered the questions and discussed the relation to the previous paper in detail. 

-  R2 mentioned that the paper focuses solely on minimizing communication costs, ignoring costs of local computations. The authors argued that the local computation costs are comparable to those of the baselines, and, in general, communication costs are the main source of computation energy costs (pointing to previous work), and, thus, are a natural objective to optimize.  I believe that this adequately addressed this (and other) reviewer's concerns and the reviewer kept their score unchanged.

- R3 had several concerns, which according to the reviewer were addressed in the rebuttal (they increased the score).

- R4 points out several limitations of the method and theoretical analysis and believes that the rebuttal did not quite address the concerns. Nevertheless, remains positive about the paper, and believes that the shortcomings can be addressed in follow-up work.

We share the reviewers' sentiment: it is a very nice and interesting paper, and should be accepted.

Decision: Accept (Oral)