Hybrid Local SGD for Federated Learning with Heterogeneous Communications
Authors: Yuanxiong Guo
Ying Sun
Rui Hu
Yanmin Gong
Venue: ICLR 2022 Spotlight (2022)
Keywords: Federated Learning
Communication Efficiency
Heterogeneity
Local SGD

Abstract: Communication is a key bottleneck in federated learning where a large number of edge devices collaboratively learn a model under the orchestration of a central server without sharing their own training data. While local SGD has been proposed to reduce the number of FL rounds and become the algorithm of choice for FL, its total communication cost is still prohibitive when each device needs to communicate with the remote server repeatedly for many times over bandwidth-limited networks. In light of both device-to-device (D2D) and device-to-server (D2S) cooperation opportunities in modern communication networks, this paper proposes a new federated optimization algorithm dubbed hybrid local SGD (HL-SGD) in FL settings where devices are grouped into a set of disjoint clusters with high D2D communication bandwidth. HL-SGD subsumes previous proposed algorithms such as local SGD and gossip SGD and enables us to strike the best balance between model accuracy and runtime. We analyze the convergence of HL-SGD in the presence of heterogeneous data for general nonconvex settings. We also perform extensive experiments and show that the use of hybrid model aggregation via D2D and D2S communications in HL-SGD can largely speed up the training time of federated learning. 

Published as a conference paper at ICLR 2022
HYBRID LOCAL SGD FOR FEDERATED LEARNING WITH HETEROGENEOUS COMMUNICATIONS
Yuanxiong Guo
Ying Sun Pennsylvania State University State College, PA 16801 USA ysun@psu.edu
The University of Texas at San Antonio San Antonio, Texas 78249 USA yuanxiong.co www.gu....s...oooom suannut.ng..uuuut.sss...
Rui Hu & Yanmin Gong
The University of Texas San Antonio
San Antonio, Texas 78249 USA
(rui. hww.my.um...mmmmmmmm yanmin, n. gongê Jut.a. edu
ABSTRACT
Communication is a key bottleneck in federated learning where large number of edge devices collaboratively learn a model under the orchestration of central server without sharing their own training data. While local SGD has been pro- posed to reduce the number of FL rounds and become the algorithm of choice for FL, its total communication cost is still prohibitive when each device needs to communicate with the remote server repeatedly for many times over bandwidth- limited networks. In light of both device-to-device (D2D) and device-to-server (ID2S) cooperation opportunities in modern communication networks, this paper proposes a new federated optimization algorithm dubbed hybrid local SGD (HL- SGD) FL settings where devices are grouped into set of disjoint clusters with high D2D communication bandwidth. HL-SGD subsumes previous proposed al- gorithms such as local SGD and gossip SGD and enables us strike the best balance between model accuracy and runtime. We analyze the convergence of HL-SGD in presence of heterogeneous data for general nonconvex settings. We also perform extensive experiments and show that the use of hybrid model aggregation via D2D and D2S communications HL-SGD can largely speed up the training time of federated learning.
INTRODUCTION
Federated learning (FL) is a distributed machine learning paradigm in which multiple edge devices clients cooperate learn machine learning model under the orchestration of central server, and enables wide range of applications such as autonomous driving, extended reality, and smart manufacturing (Kairouz et al.] (022I. Communication typically connected to the central server over bandwidth-limited networks. Standard optimization methods such distributed SGD are often not suitable in FL and can cause high communication costs due to the frequent exchange of large-size model parameters or gradients. To tackle this issue, local SGD, in which clients update their models by running multiple SGD iterations on their local datasets before communicating with the server, has emerged as the de facto optimization method in Fl. and can largely reduce the number of communication rounds required to train a model (MeMahan al.
critical bottleneck in FL the clients are
2017
Stich 2019).
However, the communication benefit of local SGD highly sensitive to non-iid data distribution as observed in prior work (Rothchild et al. 2020 Karimireddy et al. 2020). Intuitively, taking many local iterations of SGD on local dataset that is not representative of the overall data distribution will lead to local over-fitting, which will hinder convergence. In particular, it is shown in (Zhao al.) 2018) that the convergence of local SGD on non-iid data could slow down as much as proportionally to the number of local iteration steps taken. Therefore, local SGD with large aggregation period

---

Published as a conference paper at ICLR 2022
converge very slow on non-iid data distribution, and this may nullify its communication benefit (Rothchild et al. 2020).
Local SGD assumes star network topology where each device connects to the central server for model aggregation. In modern communication networks, rather than only communicating with the server over slow communication links, devices are increasingly connected to others over fast com- munication links. For instance, in fe--and-beyond mobile networks, mobile devices can directly communicate with their nearby devices via device-to-device links of high data rate (Asadi et al.) 2014 Yu et al. 2020). Also, edge devices within the same local-area network (LAN) domain can communicate with each other rapidly without traversing through slow wide-area network (WAN) Yuuan et al. 2020). This gives the potential to accelerate the FL convergence under non-iid data distribution by leveraging fast D2D cooperation so that the total training time can be reduced FI. over bandwidth-limitee networks.
Motivated by the above observation, this paper proposes hybrid local SGD (HL-SGD), new dis- tributed learning algorithm for FL with heterogeneous communications, to speed up the learning process and reduce the training time. HL-SGD extends local SGD with fast gossip-style D2D com- munication after local iterations to mitigate the local over-fitting issue under non-iid data distribution and accelerate convergence. A hybrid model aggregation scheme is designed in HL-SGD to inte- grate both fast device-to-device (D2D) and slow device-to-sen to-everrr (D2S) cooperations. We analyze the convergence of HL-SGD in the presence of heterogeneous data for general nonconvex settings, and characterize the relationship between the optimality error bound and algorithm parameters. Our algorithm and analysis are general enough and subsume previously proposed SGD variations such as distributed SGD, local SGD and gossip SGD. Specifically, we consider the FL setting in which all devices are partitioned into disjoint clusters, each of which includes a group of connected devices capable of communicating with each other using fast D2D links. The clustering can be a natural result of devices belonging to different LAN domains so that those devices connected to the same LAN domain are considered as one cluster. In another example, clustering is based on the geographic locations of mobile devices so that devices in cluster are connected to each other through D2D communication links.
In summary, the paper makes the following main contributions:
We propose a novel distributed learning algorithm for FL called HL-SGD to address the commu- nication challenge of FL over bandwidth- limited networks by leveraging the availability of fast D2D links to accelerate convergence under non-iid data distribution and reduce training time.
We provide the convergence analysis of HL-SGD under general assumptions about the loss func- tion, data distribution, and network topology, generalizing previous results on distributed SGD, local SGD, and gossip SGD,
We conduct extensive empirical experiments on two common benchmarks under realistic network settings to validate the established theoretical results of HL-SGD. Our experimental results show that HL-SGD can largely accelerate the learning process and speed up the runtime.
2 BACKGROUND AND RELATED WORK
Large-scale machine learning based on distributed SGD has been well studied in the past decade, but often suffers from large network delays and bandwidth limits (Bottou et al.) 2018). Considering that communication is a major bottleneck in federated settings, local SGD has been proposed recently to reduce the communication frequency by running SGD independently in parallel on different devices and averaging the sequences only once in a while (Stich, 2019: Lin et al. 2019 Haddadpour et al.) 2019 Yu et al. 2019. Wang et al., 20 However, they all assume the client-server architecture and do not leverage the fast D2D communication capability in modern communication networks. Some studies (Liu et al. 2020 Abad et al. 2020; Castiglia et al. [02T] develop hierarchical FL algorithms that first aggregate client models at local edge servers before aggregating them at the cloud server or with neighboring edge servers, but they still rely on D2S communication links only and suffer from the scalability and fault-tolerance issues of centralized setting. On the other hand, while existing works on decentralized or gossip SGD consider D2D communications (Tsitsiklis [194] (oydd et al. 2006), they assume connected cluster with homogeneous communication links and will converge
2

---

Published as a conference paper at ICLR 2022
very slow the large and sparse network topology that is typically found in FL settings. Unlike previous works, HL-SGD leverages both D2S and D2D communications in the system.
Some recent studies aim to encapsulate variants of SGD under unified framework. Specifically, a cooperative SGD framework is introduced in (Wang & Joshi 202I) that includes communica- tion reduction through local SGD steps and decentralized mixing between clients under iid data distribution. A general framework for topology-changee data distributions is proposed in (Koloskova al. 2020). Note that all of the above works assume undirected network topology for communications in every iteration. In comparison, our proposed HL-SGD different: the D2S communication is asymmetric due to the use of device sampling and model broadcasting in each global aggregation round and cannot be modeled in an undirected graph. Therefore, the convergence analysis of HI--SG does not fit into the prior frameworks and is much more challenging. Moreover, our major focus is on the runtime of the algorithm rather than its convergence speed iterations.
gossip SGD under both iid and non-iid
SYSTEM MODEL
In this section, we introduce the FL system model, problem formulation, and assumptions we made.
Notation. All vectors in this paper are column vectors by default. For convenience, we use 1 to denote the all-ones vector of appropriate dimension, 0 to denote the all-zeros vector of appropriate dimension, and [r]] to denote the set of integers 11.2.....1) with any positive integer n. Let ||-Il denote the l vector norm and Frobenius matrix norm and ||112 denote the spectral norm of matrix.
We consider a FL. system consisting of a central server and K disjoint clusters of edge devices. Devices in each cluster & [K] can communicate with others across an undirected and connected graph G* (V, Ex), where V4 denotes the set of edge devices in the cluster, and edge (i,j) E En denotes that the pair of devices j E VA can communicate directly using D2D as determined by the communication range of D2D links. Besides, each device can directly communicate with the central server using D2S links. Denote the set of all devices the system as V := Uke[k] VR. the number of devices in each cluster E [K] as n == [Vkl. and the total number of devices in the system as N _ n
The FL goal of the system is solve optimization problem of the form:
min
f(x)
1 N
Σ [((=) NEV
Σ fa(2),
#ER
K
RETK]
(n-D,(((x;; is the local objective function of device i, fx (1/n) Eier. fi(x) is the local objective function of cluster k. and D; is the data distribution of device i. Here l is the (non-convex) loss function defined by the learning model and z represents a data sample from data distribution D,,
where f((x))
When applying local SGD to (T) in FL with heterogeneous communications, the communications between the server and devices FL are all through D2S links that are bandwidth-limitd, particu- larly for the uplink transmissions. Therefore, the incurred communication delay is high. Due to the existing of high-bandwidth D2D links that are much more efficient than low-bandwidth D2S links, it would be highly beneficial if we can leverage D2D links to reduce the usage of D2S links such that the total training time can be reduced. This motivates us design new learning algorithm for FL. with heterogeneous communications.
4 HYBRID LOCAL SGD
In this section, we present our HL-SGD algorithm suitable for the FL setting with heterogencous communications. Algorithm provides pseudo-code for our algorithm.
At the beginning of r-th global communication round, the server broadcasts the current global model x" to all devices in the system via cellular links (Line 4 Note that in typical FL systems, the down-
For presentation simplicity, we assume each cluster contains the same number of devices here. The results of this paper can be extended to the case of clusters with different device numbers well.
3

---

Published as a conference paper at ICLR 2022
Algorithm HL-SGD: Hybrid Local SGD
Input: initial global model æ², learning rate 7, communication graph 95. and mixing matrix W₁ for all clusters & E [ and fraction of sampled devices in each cluster p.
Output: final global model x
1: for each round
O..... .. do
2:
for each cluster E [K] in parallel do
3:
for each device i V2 in parallel do 0. x²
4:
5:
for 8 = O,.... -- do
6:
Compute stochastic gradient 9i over mini-batch & sampled from 2)
not1 o/ n9((x!"") 1
7:
D local update
1et1 = E JJENT (Wx Wo note
8:
gossip averaging
9:
end for end for end for
10:
12:
for each cluster A: E [K] do
m f max(p n, S% (random set of m clients in VA)
14:
>> device sampling
end for
16:
x1+1 K [EEEK] 2 Eies "
& global aggregation
17:
end for
18:
return RR
link communication is much more efficient than uplink communication due to the larger bandwidth allocation and higher data rate. Therefore, devices only consume a smaller amount of energy when receiving data from the server compared with transmitting data to the server.
After that, devices in each cluster initialize their local models to be the received global model and run 7 iterations of gossip-based SGD via D2D links to update their local models in parallel (lines D). Let =F denote the local model of device each gossip-basee based SGD iteration consists of two steps: (i) SGD update, performed locally on each device (lines 7 followed by (ii) gossip averaging. where devices average their models with their neighbors (line 8). In the gossip averaging protocol, Noch denotes the neighbors of device i, including itself, on the D2D communication graph 9% of cluster k, and Wx E [0, 1]mxn denotes the mixing matrix of cluster & with each element (W&)..j being the weight assigned by device to device j. Note that (W+)a,, > 0 only if devices and j are directly connected via D2D links.
the r-th local iteration of s-th round. Here
Next, set S of devices are sampled uniformly random (u.a.r.) with probability without replacement from each cluster & [K] by the server (lines 13 13,14), and their final updated local models {x Vi (S) sent the server via D2S links. After that, the server updates the global model ++1 by averaging the received local models from all sampled devices (line 16). Note that only devices per cluster will upload their models to the server in each round expensive D2S uplink transmissions. The intuition is that after multiple iterations gossip-based SGD, devices have already reached approximate consensus within each cluster, and the sampled average can well represent the true average. By trading D2D local aggregation for D2S global aggregation, the total communication cost can be reduced. We will empirically validate such benefits later in the experiments.
the usage of
It is worth noting that HL-SGD inherits the privacy benefits of classic FL schemes by keeping the raw data on device and sharing only model parameters. Moreover, HL-SGD is compatible with existing privacy-preserving techniques in FL. such as secure aggregation (Bonawitz et al. 2017 Guo & Gong 2018), differential privacy (McMahan et al. 2018) Hu et al. [2000] 2021). and shuffling (Girgis et al. 202I) since only the sum rather than individual values is needed for the local and global model aggregation steps.
Runtime analysis of HL-SGD. We now present a runtime analysis of HL-SGD. Here we ignore the communication time of downloading models from the server by each device since the download bandwidth is often much larger than upload bandwidth for the D2S communication in practice (?). In each round of HL-SGD, denote the average time taken by a device to compute local update,
4

---

Published as a conference paper at ICLR 2022
perform round of D2D communication and round of D2S communication as Cups Gazd and Cazs, respectively. Assume the uplink bandwidth between the server and devices is fixed and evenly shared among the sampled devices in each round, then cazs is linearly proportional the sampling ratio Similarly, Cep depends on the D2D network topology 95 and typically increases with the maximum node degree (G))). The total runtime of HL-SGD after R communication rounds is
R x TT x (Cop + caza) + ca2s].
(2)
The specific values of Cop- cazd and cazs depend on the system configurations and applications. In comparison, the total runtime of local SGD after R communication rounds is R x [T X Cup + cazs].
Previous algorithms as special cases. When devices do not communicate with each other, i.c., W₂ = T,,... vk [K], and sampling ratio p 1, HL-SGD reduces to distributed SGD (when T 1) or local SGD (when
1) where each device only directly communicates with the server with D2S links. Also, when - x., HL-SGD reduces gossip SGD where devices only cooperate with their neighboring devices through gossip-based communication protocol with D2D links to update their models without relying the server. Therefore, HL-SGD subsumes existing algorithms and enables us to strike the best balance between runtime and model accuracy by tuning т, Ws, and p. However, due to the generality of HL-SGD, there exist significantly new challenges in its convergence analysis, which constitutes one the main contributions of this paper as elaborated in the following section.
5 CONVERGENCE ANALYSIS OF HL-SGD
In this section, we analyze the convergence of HL-SGD with respect to the gradient norm of the objective function f(),, specifically highlighting the effects of t and p. Before stating our results, make the following assumptions:
Assumption (Smoothness). Each local objective function IRd R L-smooth for all i V, i.e,, for all x, RA,
[V V S L||x - yll, ViEV.
Assumption 2 (Unbiased Gradient and Bounded Variance). The local mini-batch stochastic gra- dient in Algorithm is unbiased, i.e., Eg [g)( f((x), and has bounded variance, i.e., Eeg (elllg((1)) (=()) < O², v2 E Rd, i E V, where the expectation is over all the local mini-
butches.
Assumption (Mixing Matrix), For any cluster k E [K], the D2D network is strongly connected and the mixing matrix W₁ [0, 1jmxn satisfies W. 1, 1 1 null(T We) (1).
We also assume IIW - (1/n)11* ll2 S for some E 1).
Assumption 4 (Bounded Intra-Clusse Cluster Dissimilarity). There exists constant Eg 0 such that (L/n)Eiev [[)) - V f=x)) < e,, for any I E gd and k [K]. If local functions are identical to each other within cluster, then we have Ej =0.
Assumption (Bounded Inter-Cluster Dissimilarity). There exist constants a 2 1, 2 0 such that (1/K) ΣkETKn ft (z)11 < a² [=) for any x Rd local functions are identical to each other across all clusters, then we have a cg
Assumptions S are standard the analysis of SGD and decentralized optimization (Bottou et al. 2018 Koloskova al. 2011)). Assumptions 4 commonly used in the federated optimization literature to capture the dissimilarities of local objectives (Koloskova et al. 2020 Wang et al. 2020).
5.1 MAIN RESULTS
We now provide the main theoretical results of the paper Theorem and Theorem proofs provided in the appendices. Define the following constants:
The detailed
K
r
Pmax
max Pl:: KE(K]
Dr.p min
Pmax
L
K
(3)
k=
5

---

Published as a conference paper at ICLR 2022
and let
= 8(f(((()))))) - -(((2)))(x")) = 16L
N
= 16016 160, (P Dr + To²
( +
Theorem (Full device participation). Let Assumptions 7 hold, and let L, ELo Eg. Dr.p Pmax. ro, Tı, and be as defined therein. If the learning rate Satisfies
)²²
1 TL'
=
min
4C1a
(1TR
(5)
then for any R > the iterates of Algorithm with full device participation for HL-SGD satisfy
(r' T Dr + + Pinax) 0²)
min [
+
(6)
VNTR
(TR)
R
where Zr.
Σ N Di=1 z.
In the following, analyze the iteration complexity of HL-SGD and compare it with those of some classic and state-of-the-art algorithms relevant to our setting in Table [ First, we consider
two extreme cases of HL-SGD where Pmax 0 and Pk L, vk [K], and show that our analysis recovers the best known rate of local SGD.
Fully Connected D2D networks. In this case, Pmax 0, and each cluster can be viewed single device, and thus HL-SGD reduces to local SGD with K devices. Substuting Punx 0 into (6)
(r2e, + (0² (o²/n)) 1/3 R2/ + 1/R). This coincides with the complexity of local SGD provided Table [ with device number K and stochastic gradient variance o² /n thanks to the fully intra-cluster averaging.
the iteration complexity of HL-SGD reduces to
this case, HL-SGD reduces to local SGD with N devices. Substituting Pmax = 1 into (6). the iteration complexity of HL-SGD becomes O(a/ /NNR + (r + + To?) 1/3 /TTR)2/3 + 1/R). This coincides with the complexity of local SGD with N devices, stochastic gradient variance o², and gradient heterogeneity of order eg + 22.
Disconnected D2D networks.
Table I: Comparison of Iteration Complexity.
Local SGD
6
VNrH
(r
7R
pš.3
p
Gossip SGD
VNrfi
(FR) (1-
(1-))
+ (1-8)TR
C D DJ 30
Chopio3
Ca
pDzyd
Gossip PGA
(Chen et al. 2021
0
VNTR
(T
(rR)
( + Dr.
(T(++ )o2)
HL-SGD (this work)
VNTR
(rR)
(r
Next, we compare the complexities of HI-SGD, local SGD, gossip SGD and gossip PGA.
Comparison Local SGD. Comparing (6) and the complexity of local SGD, cluster D2D communication provably improves the iteration complexity by reducing the transient iterations. This is reflected in the smaller coefficient associated with the O((TR) -2/3) term. In par- ticular, improving D2D communication connectivity will lead to smaller Pmax and consequently, mitigate the impact of both local data heterogeneity and stochastic noise on the convergence rate.
the intra-
'The convergence rates for gossip SGD and local SGD are from Koloskooa al. 2020 The parameters in the table are given by the following: o²: stochastic gradient variance; network connectivity; e:: data heterogeneity of order eg Ez; Cr,p Et-1 p², Dr m1n p), 7). Note that Dr,p # D..t/

---

Published as a conference paper at ICLR 2022
p Comparison to Gossip SGD. Under the condition that p = Pmax= ie., the connectivity of D2D network in gossip SGD is the same as that of HL-SGD, T HL-SGD outperforms gossip SGD when r/n p² (1 (1-p)) In other words, HL-SGD is beneficial for weakly connected networks, which the case in FL. settings where a large number of devices are often loosely connected or disconnected into several disjoint clusters via D2D communications only.
Comparison to Gossip PGA. Gossip PGA improves local SGD by integrating gossiping among all devices in one round using connected network. Compared to gossip SGD, gossip PGA has one extra full averaging step with period т. The complexity of gossip PGA improves both by reduc- ing the transient iterations. HL-SGD (full participation) differs from gossip PGA the sense that gossiping is performed within multiple clusters instead of a single one. The benefit comes from the fact that for many commonly used D2D network topologies, the spectral gap
decreases as the network size decreases, see Table 2 Therefore, when employing the same D2D network topology, HL-SGD enjoys a smaller connectivity number Pmax than p. Considering the scenario where T and are fixed while the cluster number K grows, the total device number N nk grows and hence + for gossip PGA. the case when T = Dr.p' R3 Cr.pr the fastest decaying ((1/T/t) terms are comparable for both algorithms. However, the (((TR) term of gossip GPA can be larger than that of HL-SGD since P increases with N. This observation shows for large-scale networks, is advantageous to use HL-SGD with multiple connected clusters instead gossip GPA with a single cluster under the D2D network topology.
Our next result shows the iteration complexity of HL-SGD with partial device participation. We assume the devices participate in synchronizing their models the end of each FL round following the sampling rule given by Assumption 6
Assumption 6 (Sampling strategy). Each St. contains subset of m indices uniformly sampled from
(1..... n) without replacement. Furthermore, St. is independent of Si for all (k, r) # (K, r'). Theorem 2 (Partial device participation). Let Assumptions
hold, and let L, εL, Cg. Dr.p. Pmax: To. rı, and r2 be as defined therein. If the network connectivity satisfies
6
Pmax S 1 1/T,
(7)
then for suitably chosen learning rate n) the iterates of Algorithm 7 with partial device participation for HI-SGD satisfy
min 18 {(*"")1
1.5
+ Eleg, Er, a. Pmax))
(T'eg TPiax Dr +r pinax) 0²)
max (1, GpDr,ppmax))
VNTR
(TR)
R
(8)
where Jni
N 2i=1E,
1 N
E² (cg EL, O. Pmmx)) (e, r. + Pmax Dr.p + o²) Drp N 1
m m=
-Pmax
and
n m
1 G₂ Gp 72
G, m(n 1)
(10)
I Theorem shows partial device participation deteriorates the rate by (E((e εL, G. Pmax NT).. From the expression of E, we observe that as Pmax + O. E(Cg, EL, G. Pmax) vanishes, which indicates that the loss caused by device sampling can be com- pensated by increasing network connectivity uniformly for all clusters.
Compared to Theorem
The next corollary finds the critial Pmax so that 8 = O(1,, and the order of convergence rate of partial device participation matches that of the full participation case.
Corollary 1. Under the same assumptions as Theorem 2 if the network connectivity satisfies
1
Pmax
min m, 1}.
(11)
4N
then
(r T Dr.n 77 T + prnax) 02)
a late++ +EL VNTR
min V| r.5
+ R
(12)
R)))

---

Published as a conference paper at ICLR 2022
Corollary reveals the tradeoff between sampling intensity and network connectivity. More nected D2D networks result in smaller Puax. and thus (TT) can be satisfied by a smaller m. This means sample fewer devices at the end of each round and reduce the D2S communication delay when the D2D network is more connected.
EXPERIMENTAL EVALUATION
6.1
EXPERIMENTAL. SETTINGS
We two common datasets in FL literature (McMahan et al. 2017 Reddi et al. [202]] Wang al. Federated Extended MNIST (Caldas et al. 2019) (FEMNIST) and CIFAR-IO (Krizheskky
2020):
al.
2009). The 62-class FEMNIST built by partitioning the data in Extended MNIST (Cohen
jet al.
2017) based on the writer of the digit/character and has a naturally-arising device partition-
ing.
CIFAR- is partitioned across all devices using Dirichlet distribution Dir(0.1) as done in
(Hsu et al. 2019 Yurochkin et al. 2019 Reddi et al. 2021 Wang et al. 2020p. We evaluate our algorithms by training CNNs both datasets, and the CNN models for FEMNIST and CIFAR-I0 were taken from (Caldas et al. 2019) and (McMahan et al. 2017) with around 6.5 and 1 million parameters, respectively. For each dataset, the original testing set (without partitioning) is used to evaluate the generalization performances of the trained global model.
We consider FL system consisting of central server and 32 devices. The devices are evenly divided into four clusters, and each cluster has ring topology by default, which provides a con- servative estimation for cluster connectivity and convergence speed. In our experiments, the mixing matrix of each cluster W; is set according to the Metropolis-Hatingg weights (Nedić al.) 2018 According to the real-world measurements in (Yuan et al., 2020; Yang et al., 2021). we set the average time for device to perform a local update, round of D2D communication under ring topology, and a round of D2S communication with one device sampled per cluster to be Cep 0..0hh, Gaza( A 2) 0.005h and cazs (p 1/8) 0.05h, respectively, in the runtime model 2 For
bitrary device sampling ratio and D2D network topology, we consider a linear-scaling rule (Wang
al. 2019) and let caza () = (A/2) x 0.005h and (a2s(p) 8p 0.05h.
We compare HL-SGD with local SGD in the experiments. For local SGD, devices will only com- municate with the central server periodically. In all experiments, we let the local iteration period to be the same for both local SGD and HL-SGD to have a fair comparison. On the FEMNIST dataset, we fix the batch size 30 and tune the learning rate 17 from {0.005, 0.01, 0.02, 0.05, 0.08} for each algorithm separately. On the CIFAR-10 dataset, we fix the batch size as 50 and tune from (0.01, 0.02, 0.05, 0.08, 0.13 for each algorithm separately. We run each experiment with 3 random seeds and report the average. All experiments in this paper conducted on Linux server with NVIDIA RTX 8000 GPUs The algorithms are implemented by PyTorch. More details are provided in Appendix F
6.2 EXPERIMENTAL RESULTS
TO
014330
20
40
23
42
60
30
360
60
100
43
66
80
185
(a) FEMNIST
(b) FEMNIST
(c) CIFAR-10
(d) CIFAR-10
Figure 1: Convergence rate and runtime comparisons of HL-SGD and local SGD under ring topology when 50 and 1 for FEMNIST and CIFAR-10 datasets. (a) and (c) show how the accuracy changes over communication round; (b) and (d) show how the accuracy changes over runtime.
We first compare the convergence speed and runtime of HL-SGD and local SGD while fixing r 50 and 1. We measure the best test accuracy of the global model on the server in every FL round. Figure shows the convergence process. From the figure, accelerate the model convergence while improving model accuracy in FL. On FEMNIST, the best accuracy of HL-SGD achieved over 100 rounds is 4.78% higher than that of local SGD (i.e., 83.76%
observe that HL-SGD can largely
8

---

Published as a conference paper at ICLR 2022
79.94%), and its runtime necessary achieve a target test accuracy of 75% is only 17.64% of that of the baseline (i.e., 5.67 speedup). On CIFAR-10 10, the best accuracy of HL-SGD achieved over 100 rounds is 9.32% higher than that of local SGD (i.e.. 68.71% vs. 63.68%). and its runtime necessary to achieve a target test accuracy of 60% is 15.67% less than that of local SGD (i.e., 1.186x speedup).
60
Test Accuracy
50
HG
Test Accuracy
IT
(T
HL NL556
40
HL 5G2
HL-5DD (1- 501
HL.0D 501
30
Lacal (7
Lacal (7)
Local 5GD 15 101
Local 56D IT 101
10
Local 5030 301
Local 560 301
50
100
150
200
50
100
150
200
250
Round Number
Runtime (Hour)
Figure 2: Convergence rate (left) and runtime (right) comparisons of HI-SGD and local SGD on CIFAR-10 under different and ring topology when p
Next, to give a more comprehensive analysis on the runtime benefits of HL-SGD, we vary from {5, 10, 20, 50} and compare the performances of HL-SGD and local SGD on CIFAR-10 in Figure From the figure, we can observe that HL-SGD can consistently outperform local SGD across wide range of т. In particular, on CIFAR-10. 10, the best accuracy of HL-SGD achieved over 100 rounds 2.49%, 3.99%, 4.05% and 7% higher than that of local SGD, respectively, as T increases from 5 to 50. At the same time, the runtime of HL-SGD needed to achieve a target test accuracy of 60% 9.66%, 19.76%, 33.46% and 45.88% less than that of local SGD, respectively.
Sant ACOUPNCY
160 Ui- L20
A60 (211
16/02 1-11
20
(m
050 (mndi
88-00 --13
20
40
50
23
42
60
50
100
20
40 60
43 E0
50
(a) FEMNIST
(b) FEMNIST
(c) CIFAR-10
(d) CIFAR-10
Figure 3: Effect of sampling ratio on the convergence rate and runtime of HL-SGD under ring topology when
= 50 for FEMNIST and CIFAR- 10 datasets. (a) and (c) show how the accuracy changes over communication round in HL-SGD: (b) and (d) show how the accuracy changes
runtime.
Finally, we investigate how the sampling ratio p affects the performance of HI-SGD. We select p from (0.125, 0.25, 0.5, 1). corresponding to sampling {1, 4, 8) devices from each cluster to upload models to the server. Figure depicts the best value of test accuracy achieved over all prior rounds. As can be observed from the figures, sampling one device per cluster only results in slightly lower model accuracy, e.g., neligible and 1.92% drop compared to full participation on FEMNIST and CIFAR-10, respectively. This matches the theoretical result in Corollary [ that device sampling does not affect the order of convergence rate under certain conditions. However, decreasing p can lead to faster training speed due to its shorter D2S communication delay as observed Figures 3b and In practice, the optimal value of p needs to be tuned to strike good balance between model accuracy and runtime.
7 CONCLUSION
In this paper, we have proposed a new optimization algorithm called HL-SGD for FL with heteroge- neous communications. Our algorithm leverages the D2D communication capabilities among edge device to accelerate the model convergence while improving model accuracy in FL. We have pro- vided the theoretical convergence analysis of HL-SGD and conducted experiments to demonstrate the benefits of HL-SGD. In the future, we plan to extend HL-SGD to handle straggler issues under device heterogeneity and provide rigorous privacy protection for HL-SGD.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The work of Y. Guo was supported in part by NSF under the Grant CNS-2106761. The work of Y. Sun was partially supported by the Office of Naval Research under the Grant N00014-21-1-2673. The work of Hu and Y. Gong was supported in part by NSF under the Grants CNS-2106761.
and
REFERENCES
Mehdi Salehi Heydar Abad, Emre Ozfatura, Deniz Gunduz, and Ozgur Ercetin, Hierarchical fed- erated learning across heterogeneous cellular networks. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8866-888 8870. IEEE, 2020.
Arash Asadi, Qing Wang, and Vincenzo Mancuso. A survey on device-to-device communication in cellular networks. IEEE Communications Surveys & Tutorials, 1814)11001-181,, 2014.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508 2530,, 2006.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. LEAF: A benchmark for federated settings. In Work- shop on Federated Learning for Data Privacy and Confidentialityy 2019.
Timothy Castiglia, Anirban Das, and Stacy Patterson. Multi-Level Local SGD: Distributed SGD for heterogeneous hierarchical networks. In International Conference on Learning Representations,
2021.
Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip SGD with periodic global averaging. In Proceedings of the 38th International Conference Machine Learning, pp. 1791-1802. PMLR, 2021.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. EMNIST: Extending MNIST to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN, pp. 2921-2926. IEEE, 2017.
Antonious Girgis, Deepesh Data, Suhas Diggavi. Peter Kairouz, and Ananda Theertha Suresh. Shuf- fled model of differential privacy in federated learning. In International Conference Artificial Intelligence and Statisties, pp. 2521-2529. PMLR, 2021.
Yuanxiong Guo and Yanmin Gong. Practical collaborative learning for crowdsensing in the internet of things with differential privacy. In 2018 IEEE Conference on Communications and Network Security (CNS), pp. 1-9. IEEE, 2018.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Local SGD with periodic averaging: Tighter analysis and adaptive synchronization. In Advances in Neural Information Processing Systems, pp. 11082-1 1094, 2019.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint 1rXXiv1909.063320 2019.
Rui Hu, Yuanxiong Guo, Hongning Li, Qingqi Pei, and Yanmin Gong. Personalized federated learning with differential privacy. IEEE Internet of Things Journal, 7(10):530-95533 2020.
Rui Hu, Yanmin Gong, and Yuanxiong Guo. Federated learning with cewpsfiication-mmpiiit pri- vacy and adaptive optimization. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 1463-1469, 2021.
10

---

Published as a conference paper at ICLR 2022
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning, Foundations and Trends@ in Machine Learning,
14(1-2):1-210, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 1132-5143, PMLR, 2020.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference Machine Learning, pp. 1478-3487, 2019.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sehastian Stich. unified theory of decentralized SGD with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381 1-393. PMLR, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Tao Lin, Sebastian U Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large use local SGD. International Conference on Learning Representations, 2019.
Lumin Liu, Jun Zhang, SH Song. and Khaled B Letaief. Client-edge-cloud hierarchical federated learning. In IEEE International Conference on Communications, pp. 1-6. IEEE, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficceen learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In International Conference on Learning Representations, 2018.
Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradcoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-976. 2018.
Sashank J. Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In International Conference Learning Representations, 2021.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. FetchSGD: Communication-eficce federated learning with sketching. In International Conference Machine Learning, pp. 8253-8266 8265. PMLR, 2020.
Sebastian Urban Stich. Local SGD converges fast and communicates little. In International Con- ference on Learning Representations, 2019.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of update SGD algorithms. Journal of Machine Learning Research, 22(213):1-50, 2021.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: Speed- ing up decentralized SGD via matching decomposition sampling. In 2019 Sixth Indian Control Conference, pp. 299-300. IEEE, 2019.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H Vincent Poor. Tackling the objective inconsistency problem in heterogeneous federated optimization. Advances in Neural Information Processing Systems, 33:7611-7665 2020..
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to feder- ated optimization. arXiv preprint arXiv:2107.06911 2021.

---

Published as a conference paper at ICLR 2022
Chengxu Yang, Qipeng Wang, Mengwei Xu, Zhenpeng Chen, Kaigui Bian, Yunxin Liu, and Xu- anzhe Liu. Characterizing impacts of heterogeneity in federated learning upon large-scale smart- phone data. In Proceedings of the Web Conference 2021, pp. 935-946, 2021.
Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34, 2021.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Zhe Yu, Yanmin Gong, Shimin Gong, and Yuanxiong Guo. Joint task offloading and resource allocation in UAV-enabled mobile edge computing. IEEE Internet of Things Joumna,, 7(4):3147- 3159, 2020.
Jinliang Yuan, Mengwei Xu, Xiao Ma. Ao Zhou, Xuanzhe Liu, and Shangguang Wang. Hierarchical federated learning through LAN-WAY WAN orchestration. arXiv preprint arXiv:2010.11612 2020.
Mikhail Yurochkin, Mayank Agarwal, Soumya Ghosh, Kristjan Greenewald, Nghia Hoang, and Yasaman Khazaeni. Bayesian nonparametric federated learning of neural networks. In Interna- tional Conference on Machine Learning, pp. 7252-7261. PMLR, 2019.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data, arXiv preprint wrXiv1186600058) 2018.
A PRELIMINARIES
Intra-cluster dynamics. To facilitate the analysis, we introduce matrices X Rxd and Gs gaxd constructed by stacking respectively I; and gi for i E V4 row-wise. Similarly, we define the pseudo-gu -orddintt (Xx,) E Raxd associated to cluster ie by stacking (z(zz) for i E Vk riwewise. In addition, define the following intra-cluster averages for each cluster k:
and
9k
A
Σ 9:-
(13)
BEV3
VEV
The update within each cluster then can be written compactly matrix form as
x
( G
Wk
K.
(14)
Since each W₁ stohhssa,,,,,, we obtain the following update of the intra intra-cluster average
zr F 17.77.. -
(15)
We proceed derive the update of the intra-cluster consensus error. Define the averaging matrix
n with
1
(16)
Multiplying both sides of error:
[4 from the left by (J- leads to the following update of the consensus
( - ()x x0x++11111 = = -1 W ryCr
x
(17)
(Wa - J) - (W₂ - J)(X)1 - n).)))
Global average dynamics. Define the global average among all 2, 's
N
Tx.
(18)
N
1=1
12

---

Published as a conference paper at ICLR 2022
Then accordingly to
15
we have the following update of for all O...., 1:
K
K
gre+t
N
n.
ni+1
k
N
1
Σ
175
k=
1=
(19)
1
19;
xr
91
N
N
Filtration. Let G [G.....; Gk] RRxx be the matrix constructed by stacking all the stochastic gradients. We introduce the following filtration
Fr, = (G - So G ,.... Gl.7-1 ...,....G..T111 ," G".., So,
(20)
F, = a (G G Sy. GLD Gl.7-1 S.-1)
Therefore we have oz x² Fr for r 2 1, and x² E Fr,--1 for 1 < & S 7. For simplicity the conditional expectation IE( (Frs)) denoted as Ens, and we define the noise the stochastic gradient as
5 9fth f((2f"))
(21)
Since at the end of round all nodes picked with equal probability, the sampling procedure preserves average in expectation:
++
E(E(x (1
K
E
|Fr,t22
k=1
SEST
(22)
Σ
lli (
[Frs-1
(Frr-2)
K
m
k=1
E, (
where the last equality holds since P(i E Sili Va)
B CONVERGENCE ANALYSIS
To prove the convergence first establish in Sec. B. that the objective value (z") is descending at each round r. up to some consensus error terms. Subsequently, bounds on the error terms are provided in Sec. B.2 B.4 Based these results, the proof of convergence of Algorithm with full and partial device participation are given in Sec. / and [.6] respectively. The proofs of the main propositions are given in Sec. C and that of the supporting lemmas are deferred Sec.
13

---

Published as a conference paper at ICLR 2022
B.1 OBJECTIVE DESCENT
Lemma 1. Let { be the sequence generated by Algorithm under Assumptions 6 then the following inequality holds for all E N4:
Ifn 0.
Ef
<Ef(x
Σ
Σ
||=
Σ
E
1
(T
k
2 (23)
N
K
i=1
S=0
k=1
Σ
[((["()))
1
Σ
fi
(5
K
_ | - 11:
I.
Σ E
+
2
Proof. The proof is a standard application of the descent lemma and the sampling rule applied at iteration r to obtain 11+1, See Appendix D.1
Lemma I
shows the objective value f(x") is descending in expectation up to the following error
terms:
1 K
()( Σ
V T- T2=B|VVSE*M
K Σ (i(
K
N
f((xx"))) 2
|
(24)
T3 E
K
T4
E E - 1
TB
In the sequel, will show these quantities can be bounded by the optimality gap measured in terms of the gradient norms [/V](=*))) _ Vfa and [(L/N) (=("""))
B.2 BOUNDING Ti, Th AND T3.
Define
Pmax
max Pk. kl.....K
(25)
Therefore it holds 0 S Pmax I 1 by Assumption
14

---

Published as a conference paper at ICLR 2022
Since each fi is L-smooth by Assumption 1 have fo and f are also L-smooth. Using this fact and the convexity of || 1|2 we can bound Ti. T2 and Ty as
7i = E
V V
1 K
S
Σ
1 i
- -
I
K
iEVn
(26)
(i( ||
1
T3 E
(f(
5
L E
K
k=1
N
T3
Σ
T,2 F
xx,-01
LEV2
Clearly, in order bound 2,, first need to bound the inter-cluster consensus error | - x1 and the intra-cluster consensus error | x =1
Lemma 2 (Inter-Cluster Consensus Hrror Bound). Let {x, be the sequence generated by Algo-
rithm 7 under Assumptions and 5
If the learning rate rj O satisfies
12 S 24T 1)12'
(27)
then for all O.....5 it holds
Fx
xrist112
12=
< C+
s
xx 11
K
K
K
+ 12Tm L2
x k
+ 12T1/
( +
+ +1²
o²
(28)
N
N
K=1
where
3 1 2 47
C, 2 1+
(29)
Proof. See Appendix D.2
Lemma 3 Catra-Cluuter Consensus Error Bound). Let {x,'*} } be the sequence generated by Algo-
rithm D Junder Assumptions 1 If 0, then for all s = O...., T 1 holds
K
K
E
max P2 + kE[K]
+ PP
4T?
E
X k
112
N
N
1=1
k=1
1 K
+ 2L
B
"
+
4n PLEt, + 120020 pmax.
(30)
where Pmax defined in
25 and
K
PL
max k=
{p
+ (
2,
(31)
K
with So > 0 being free parameter to be chosen properly for all k = 1, I,...,K K.
Proof. See Appendix D.3
15

---

Published as a conference paper at ICLR 2022
obtain the following bound the sum of intra- and inter- consensus errors using gradient [
Combining Lemma 2 and
Proposition
Let {xr
"r } be the sequence generated by Algorithm 7 under Assumptions
the
learning rate 1j > 0 satisfies
2J 24T(4T 1)
(32)
then for all O...., it holds
E Blasttt xfitt + Σ N xxx11 |2
Fx
K
Σ
Cini (T Pmax Dr.R)
+ +g) ||1
Cinx D
(33)
8=
+ CiTTi Pmax + Ci(T + DT -1 pmnx)) Dr
where
1
Dr.o - min T,
(34)
Pmax
and C₁ > 0 is some universal constant.
Proof. See Appendix C.1
Notice that according to 266
the gradient difference terms in Lemma can be bounded as
3|²
2
"
(a 2
K
N
"B
E
v
vi(af
(F
K
i=1
k=
<7
- -"
+
L L'E - x 24-"11
(35)
K
k=1
iEV:
1-.5 - 255" 2
+
I.zE
I. E - -
K
N
k=1
k=
iEV
K
SnL² 2
Bl - 11 +
r. 1|?
K
1=1
k=
for all s = 1.....7. Therefore Proposition immediately leads to the following result. Corollary 2. Under the same setting as Proposition it holds
N
K
fa
(5
N
K
==0
k=1
ΣN (((
(
(36)
Σ CL' (72 + +p T DT,0) (a 2 Vf +
+
p Dr
==0
+ + P 02 + CT2 D2 2 )n 0
p2
16

---

Published as a conference paper at ICLR 2022
We conclude this section by providing separate bound N
the consensus
E k== X
that will be useful in bounding Tg-
Proposition 2. Under the same setting as Proposition 1 if Pmax I
then we have
X 11 < 2C
(a +eg)
DDDe +
+2DD op m + C2
P PrixtDr.pioo (37)
7 7
for some universal constant C2 > 0.
Proof. See Appendix C.2
Proposition 2 shows that the average intra-cluster consensus error 1 Σ k= [X the network connectivity improves, and vanishes if fmax goes to zero.
decreases as
B.3 BOUNDING T4
Proposition 3. Under the same setting as Lemma we have
1 2
+ +1220=
E E =/1011
(38)
N
N
for 0,..., and r E N4-
Proof. Recall the algorithmic update at iteration s for all s = =0,.. T 1:
X r
W k
G
(39)
x ns+
x//² 19
r.e
Therefore, holds under Assumption that
E 1 xh. ||2
+ 1/2 02
(40)
7
A t + (.(('
N
B.4 BOUNDING T3
We provide the bound on T3 separately for the full device participation and partial participation cases.
Full participation.
When the sampling probability p we have
1
In this case, it follows from Proposition that
N
E Bl
112
=
+
1 N.
(41)
Partial participation.
17

---

Published as a conference paper at ICLR 2022
We proceed to bound T₃ for Define m/n. Recall the algorithmic update at iteration r -- 1:
1 m 1n-1.
(42)
x
Wx
(43)
and
K
K Np 1E
(44)
k=
Therefore, with (Wa)s being the ij-th element of matrix W₁ we have under Assumption r r+
1712-112
K
-
Np
1=liEs
Σ
Σ
(We)is(a) - ngn 1195"-11) 5-
1ESt
JEV
(45)
K
E
E(iE ST) Σ (WW -n (W - --T--1
1= LEV2
JEV.
12.1
2
22 E
Ilie
S Σ (Vf -9, 9)
Np
K=
JEVI
A2.2
Proposition 4. Let {x, } be the sequence generated by Algorithm under Assumptions 6 If the learning rate 1) 0 satisfies
12 < 24T 1)1.2
(46)
then we have the following bounds on A2.1
2
1 ) (N K
(EEIII)))))
A2,1 2
+8 Gp + 72
(47)
K
where
Gp A m
(48)
m(n 1)
Proof. See Appendix C,3
Proposition 5. Under the same setting as Proposition 4 A2,2 can be bounded as
o² (2+ m Pmmxx)
A
(49)
Proof. See Appendix C.4
n
18

---

Published as a conference paper at ICLR 2022
B.5 PROOF OF THEOREM (FULL PARTICIPATION)
We first prove the descent of the objective value under suitable choice of 7/.
Proposition If the learning rate satisfies
1 40 7L'
1 S
(50)
then we have
{ Bf(x²')
E |f(*')]] + R
(51)
8
where
Dr,) RTal(1) =C;2'yp Pro) og 2CgLL')
( (remssDr + T²00 (
+++xxx
71 Pmnxs)
))
+ 1/ LT o² N
(52)
C > 0 is some universal constant.
Proof. See Appendix
C.S
To attain the expression of the convergence rate, we sum (51) over r -..... R:
min min FE|R ==0....-1 \)
8(f(x") - f(x²)) (Rau((n) R1 1) 8(f(z)) - f(x*))
(T(++1) 16 o²
(53)
N
centralized SGD
1 - n
16C 16C,, PPmoxDr,pf + TO?
Pinax
netwark effect
The first two terms of (53) corresponds to the impact of stochastic noise and is of the same order the centralized SGD algorithm. The last term of order 1 and corresponds to the deterioration of convergence rate due to the fact that we are not computing the average gradients all devices at each iteration.
Denote
0²
= =(f[((xx))-- -
f(x))), -(f())))((x'),
16L
N
(54)
1=C,, + 16C, (TrimxDr Dr + To? (1 Pinax )):
The rest of the proof follows the same argument as (?, Appendix B.5) and thus we omit the details.
B.6 PROOF OF THEOREM 2 AND COROLLARY (PARTIAL PARTICIPATION
1x. be the sequence generated by Algorithu under Assumption 7 If the learning rate n and the network connectivity satisfies
Proposition 7. Let fa.
"1 - CgarL"
1
min {
aG,Dr Pmax } and Pmax S $1-2
(55)
19

---

Published as a conference paper at ICLR 2022
then
Bf(x+t)) S <Ef(2²)
Σ B (IVff(">))) + Rpprr (1) + +R Rpare (1)
(56)
with
(PomneDrott + 7202 (1 + Pimax) ))
R pare
(17) =C (++ Pinax Dr.)) + ++22(ii))
+ LTij² o²
N
(57)
R part (11)
(8C2G,, 1 Pmax) e
+ +4C2LG' nn
(Drn +
1 Dre + +1) Pinax T DD
+
L
n
n2
Pmax
P
17
0²
2
m
N
C1 C3 > 0 are some universal constants, and
G. Gp 73
with
Gp m(n 1)
y71.
(58)
Proof. See Appendix C.6 C.6
Comparing 56 to 51 we can see that R R (1) is of the same order as (1) (1)), while R R (1) is
an extra loss term introduced by sampling.
Following the steps as the proof of Theorem gives
min rE( 0=.....,-1
min EFV'(="')
-0 σ + Elgg, EL, o. Pmax))
(r2 + Tp Dr.p. + (2 + Pmax)) 02)
(59)
VNTR
(TR)
+ R
max GID,
where
(Eg, εL, Pmax)
(r) + Drapet, + + G,Dropuna N + n 1
-maxx
(60)
Our last step simplifies the overall conditions on Pmax so that E (Eg. εL, a. Pmaa)) = 0(1):
Pmax $1 -1- - PiDip N Pmax S n
(61)
We claim to fulfill 61 it suffices to require
Pmax
minfm,77 1}.
(62)
4N
When T 1, the condition trivially requires Pmax definition, it can be verified that
0. We then consider the case for 7 2 2. By
1
G
<
+
(63)
72'
First notice that
m
T
m
< <
-
and
(64)
4NV
4N
Therefore, remains to prove
62 implies
DDD²
P
<
(65)
N
20

---

Published as a conference paper at ICLR 2022
Using the fact that under 662 Pmax I 1/4 we have
D T.ppmax
G GyPunxx"
(1
Praax)
(66)
16
1
16
1
1
Piaxx
+
+
min 7) -
72
9
72
4N
N
This proves the claim.
C
PROOF MAIN PROPOSITIONS
C.I PROOF OF PROPOSITION 1
Denote for short
K
E
E1 1??
N
M A
k=
(67)
K
-
K
k=1
Invoking Lemma 2 and Lemma satisfies
3 we obtain that under the condition that the learning rate >
1² S 24T(47 4T 1)
(68)
the following inequality is satisfied for all ......T
M < G M + Bris,
(69)
where
G maxke]K] P1 + S
+ 1p 4L2 TPLL 4L2
(70)
12TH L
C₁
(4Pln 2 f=
(g) + 4n + n p 02
B
(71)
12T (a (f 1| +gg + 17
The inequality in (69) defined elementwise.
Unrolling (69 yields
M
Σ G² t=0
(72)
where we have used the fact that M due full synchronization of the x, 's the beginning of each round r.
We first provide a bound on the sum of the two elements of Br.s-- For simplicity we omit the round index in the superscript for the rest of this section.
Lemma 4. Let b and by-² be the first and second element of Be-t respectively. Suppose the learning rate nj > 0 then
X6 X n
(1,1) Xb(19- by
(12TL 4p2
(73)
A A1
where \ S X2 are the eigenvalues of G: and PL is defined in 31
Proof. See Appendix D.4
21

---

Published as a conference paper at ICLR 2022
From Lemma we immediately get
2 (1,1) Br
(74)
X/ X1 172 (122TI,00-
$ Σ
12 + 1 +
4pr (.2
22 A1
8=
Since A2 2 C. >
we have
X/2 - X1
8-1
A1
x2
A22 -x1 21 e)
X2
Σ
s 1
min
N/
min
(75)
A2 \1
X2
x2 X1
and thus
11, G-B=-
t=
(76)
Σ
Σ
A/ min
A2 d1 1))0²
12. (12 44prL2b5
t=
8=0
Recall the definition of Pr. given by (11
PL
p (te) k= K
max
By the Gershgorin's theorem, since
0, we can upperbound X
2 S max
max KE[K]
pi (1 + 4% 1) + T2P 8L2, Cr + 12Tm 1
(78)
2
< max
max
Sk
+
1 +
[E[K]]
(47 1)3r
4r
where the last inequality is due to the bound on
n² < 24T (4T - 1)
(79)
Define constant
Dr.p min T,
(80)
Puax
We consider two cases.
Case
Pmax 1
S
(81)
7
Pmax
Thus Dr.pp 1/(1 Praax)) We let Ca pkk(11 - pk)) and gives
Pk
Pinxx
max p (1 + C% KE[K]
Pmaxi
PL
max
Pinax Dr.pp
(82)
b=.....KK K
Pk
Pmax
Substituting into the bound of X2 [ef. 788 gives
A2 max
Pmax +
Viax
1
2
(1 Pmax 33r(47 1)
47
(1-1) 1
(83)
1 +
2
3
max
1
1
1
7
3(47 1)
4T
4T
22

---

Published as a conference paper at ICLR 2022
where in the second inequality used the condition 88 Since s S T and 22 2 L, we obtain the following bound
Σ 126--22 S
(11+
3
Σ
by
33
Σ
bf
(84)
4T
2=0
Moreover, since
(1 1 2) 2
Pmax -pprr. 4L2 S Pmax
Cr,
(85)
(1
Pmax (4T 16T
6(4r - 1)
can bound A2 A1
A A1 C Pmax 1/ 4I,
p
2 C+ Pumax +
(1 Pmax (4T 1)67
81
1 1-
Cj |mmxx + Pmax 6(4T 1)
(86)
1
2 1 +
|mmax + Pmax
4T
4T
1
= (1 - pmax)
11 4T 1
2 11- Pmaxx.
Collecting and (86) we can bound (76)
(1.1)
Σ (b) + b)) 3 Σ n² (12-L + (b)) min { 12 X1 :1)
0
0=
Σ (6) + 69) 3+
2 L22 + Dr DrppPrnnx 4L AL2bb)
3Dr.p
E=
(87)
70
16 66).)3331 3+ Σ (12rbf + Dr.pPiax 4bb) 3D..p (4T - 1)24T
1
1 Dr
Σ
(bf (3)3)333 34 Σ (12Tb/ DripPhaxx Ab/))
8 72
E0
t=
1 Dr.o
Σ
(b) + (g)
3 +
(127b) + D P
4b9)
8 -2
E=U
8=
23

---

Published as a conference paper at ICLR 2022
Substituting the expression of bf and by gives
D
11 G B
1h 5+
TsP
x2
1=
2=
8=
Σ
(PL + 37) )| ( + 4nj² PLE.. + Prnne +
172 32-02 n
t=
D2
(2r)" + +2g) + 1 _0²
+
-maxx
72
n
C1
C1
(88)
1/ (ps. +
PraxDDy -
1) (a + 2 T'T
2
E=
C1 2
C1 (T D² -- Pmax )2² 0²
"rppPuxx 0² +
D
T1j
Pmax
2
2 (T + Pinax Dr.)) (a + C Dr.p
t=
+ Ci o + Ci(T - Pmnx )r² _²
n
where C1 is some universal constant. The last inequality holds since PL Praxx Dr.p and Dr S T.
Case 2:
Pmax
+ Dr.p= =T
(89)
In such case, we let &. = (4r 1) and thus
max (1 + 1) Pmax (1 + (4r (4--1) 1)- kE[K]
PL 4 4mpaa
4pmax Dr.r-
(90)
Substituting into the bound of A2 given in 778. applying again the learning rate condition using the fact that Dr.p= T:
79 and
2 3(4T 1) (47 1)
4p 1 +
A2 S max
Prnux (1 (47 1)-1) +
(91)
< 1 +
4
Therefore by (76).
79
84 and the fact that
A2 A1 c)
1)
min
ST=
Dr.p
(92)
we obtain
(1,1)
E=0
(bf + bb) 3+ Σn n¹² (12FL22 + +166 Dr (3bb) -DD
==0
t=
(93)
D
Σ (bf + bb) 3+ Σ (12Tb) + 16p D2)
72
0m
Rm0
D2 P 14.
Σ (bf + bb) 5+
Σ 8=
2
Substituting the expression of b, and by and using the fact that
PL p ApmmsDr
arrive the same bound in Case possibly with different constant C1.
24

---

Published as a conference paper at ICLR 2022
C.2 PROOF OF PROPOSITION
We are in Case described in the proof of Proposition 1
By letting Ca ph/(1 - pk) we have
Pumax + Piaxx -12 4L2
Punxx 2 .4L2
G =
1- 12Tn L²
Panax
(94)
Cj
and the following bound the difference of the eigenvalues of G:
A A 2 1
Pmax.
(95)
Notice that according to 72 and (48)
K
X 11 1
2-6
N
det(T)
k=1
t=0
Therefore
K
X R.L
||
N
R=1
(1 -1 -G,
12rn/2 12 X1)
k=
7-2
((12 C+) (161277) Xg(C, (1165----9)
(96)
1,2 A1)
T-2
((C, A1) A (12TT L 1 (A2 Cr)bb 2-))
12 [2
pmax)
t=
7-2
Σ
((2 -,) 2/ (12TT² L207 120--22 2- (C, - -1)b2 2-))
12np Pmax)
E=
In the following, we bound λ₁ and X2 C, as a function of Pmax- For notation simplicity we omit the subscript of Pmax in the rest of the proof. Further, we introduce the following shorthand notation for the clements of G:
1² 1-p 172 4T.2
f(p) p 1-p 1-p
(()) =
and M(T) = 12rr2 r.2.
(97)
Applying the Gershgorin's 's theorem we obtain
min {p, 1,2 2 2p20. 0,
(98)
and
max hh)) C
(99)
Under the learning rate condition
79 we can show
(()) C, (f(p) + MP))
0²
n72 4L + C, - p 1-p
1/ .4.2 12Tn² 2 1
(100)
p
= 1 + 2 4T
- 12T1 212 2 0.
Therefore,
A C, $(().
25

---

Published as a conference paper at ICLR 2022
Substituting the bounds into (96) gives
K
1
1|
R
N
T-2 (C-11 L26 2-E (A2 - CG) 2-
12 L2T p)
0=
2-2
Σ
(O12 - --)
X/ (127)) + 02,5-2-99)
122 - p)
t=
(C-f(p) (167
12- p)
8=
(101)
(o(p){) 120 2- + C-6g-2-
12n L2r p)
2=
T-2
x-2
C
Σ by
+
Σd
1-p p
E==
1=
O
T-2
+ 12n L2T(1 p)
0(0)1
Σ
1=0
CD+OCr
b9 Σd
+ +12D 1 21?22
Σ
b9
+ C
p² TmP
Σ 1/
2
P=
2=
E=0
where we have used the bound X S ((0) < 1. 1. > 1 and 1/ <3
Plug in the expression of by and by and using the fact that C, < 2, pr. = DT gives
1
1
x
N
2-2
<(2Dr.p
+ 12D2 ",
21. p²) 2
(a + 2g)) + +r + + 120²)
D2
T-2
[+) 2
+
117m 2 (a
==U
D2
T-2
<(2Dr, r.p +
T.p
p²)
Σ p² (2 + 4n Dr +
72
#=0
D2
+2 T.P
(127H" (a² +++
s=0
<3D pp
2
(4n) D Da 2 |V + + + 4nj D, 2 + 1202)
$=0
T-2
+ +2D2
+
+ +
n
(102)
26

---

Published as a conference paper at ICLR 2022
Tidy up the expression gives
K
x-2
12 5
Σ
3Dr pD
(M1" + Eg) + 4n Dr Dr - - x/00)
==0
(12T)) (
2D
-gg) -
#=
S C2
DD*
(103)
==0
+ +C2(Dr
C2T C2TD 1 C2(
202 Σ
D 2 V + (T'1))
C2
==0
1 DD +1 p'TDr
+ +C2
for some C2 > 0.
C.3 PROOF OF PROPOSITION 4
We prove 47
by splitting the terms A2 follows:
K
A
(a)
E
Iiie ( Σ
(W (t Fo
-n -- -
15--1)
Np
JEV/
(104)
2
K
<2
p nn fn
+ 2E
Np Σ Σ
1(i stmil
Np
k=
where
Tik
Σ (WW)
-V - Via
(105)
JEV
Equality (a) holds since
K ΣΣΣ
m 3
k=1VEST JEV.
k= VES
(106)
N NNr TT-1
p
x
k=1
and similarly,
ΣΣ Vi up F KEST JeV
(107)
Since samples are taken according the rule specified by Assumption 6 the following probabilities hold:
P(i E $ e Vo) = P(ij E 1,iji E Vk) =
npp n n-
(108)
P(i E St.j e Sp e e ( p²
(109)
Consequently, we can evaluate the second term in 104 and obtain
K
1 =2F
n fx
-1
K
27

---

Published as a conference paper at ICLR 2022
+
E (Np)²
p
| 1 +p- 11 A= i.
T&p Σ
Tectih
k=liEV
ΣΣΣ Σ
+ (Np)2
legh LEVE JEV
1
=2F
V
K
+
B
p. np
K
Tik +
2
p(1
p)n
Σ k=
K
|rall
(N
1
k=liEV
p(1 p(1-p)
ΣΣ Σ KELiEV& JEV
+
TikTze
(Np)²
K
1
<2E
V
Fa(
K
k=1
p. np 1
K
2
p( p)n
K
+
(Np)²
E
Tik
+
n 1
||aa
k=liEVe
A= iEV
+ (N
p(1 p(1-p)
E -
ΣΣ Σ KFLiEV JEV,
|
+ +2222 Ilrsell
K
<2E
K
k=1
K
K
p npp 1
2
p(1 p)n
+
(Np)2
E
Tik
+
1
||aa 1|
k=IiEV
1= 1EV
K
p(1 - p)
+ (Np)² n (K 1)m
E B11r:
(110)
k=
By substituting the expression of Tik we can bound
terms
|E Eien, rull? and
ΣK Eier, || as
ΣΣ Σ (Wh) shr-1 (V \((
Tik
VEV
K=liEV JEV
(Wi),, (Wa), Fia
iEV
K
n
ΣΣ (WA)s(V( (5,(F(
Amm LE JEV
< N N
Σ Σ (W)),,L3110 1---1 2/4 112
A= JEV.
K
K
< 2 N
11 = n² 2
(111)
28

---

Published as a conference paper at ICLR 2022
and
K
Σ |raal
1= LEVE
Σ
(Wi))s
(2) -F -V
VV - V
JEVE
nVV - [E 1) |
1 Σ (Wa)s.)
2-
LEV, JEV
(Wa)es (2/10)7-1 (2110)r--
x/--1|1 1|
+ 22²
VE JEV
K
x p--- - 11
-
+ 2 L
|: - 12
k= 1EW
k=1 VVV.
= Σ 2(1 + 12)+
(112)
Tidy up the expression leads to the following bound of A2,1:
K
2
np
1
52B
K
k
(Np)²
p
71
Tikk
k=1
A=m LEVE
N
(Np)
p(1
p)
El|ra 1
E
n
1= LEVE
1 K
K
<2E
2
p npp "
N 2
E3 X 1 113
K
(Np)²
11
K
N
+ (Np)
p(1
p) -
Σ
2(1 +
2,1 112 (1
k=1
1 K
K
2
221 E
V (
2
E 11 1|2
K
N
#=1
+ 4 1 p
[1+n
X 112
N p(n - 1)
1 K
8
1-p +
1
2
Σ
7z)
(113)
K
where the last inequality holds under the learning rate condition
1/ < 24T(4T-1))
(114)
This completes the proof of (47
29

---

Published as a conference paper at ICLR 2022
C.4 PROOF OF PROPOSITION 5
We bound 2 in following the same rationale as Proposition
K Np Jemn
22.2 =E
Σ
I(iE
SD) (
Σ
(W))),((V 07;²))
iEV4
JEV.
Psk
(Np)²
p np
E
Eik
2
+ +p(1 p))
13 Bleew 12
11
k= V
k= 1 V/
(115)
p(1 p) E
Σ
exkeje
(Np)2
Agptt LEVE JEV
K
K
up - 1 E p
esk
+
+
p)
n
E Eleax
(N
n
k=
k= V
where the last equality is due to fact that the inter-cluster stochastic noise is zero mean and indepen- dent.
Recall the definition 4
gf
(x
Using again the independence of the Et's we get
K
K =
N =
(Wa)asg)
Σ
5i
= No²
(116)
A= 1 3
k=
JEV
1=1
and
Σ
E Gall
Σ
Σ
(W (Wa)isff of = = 122
(W
22
A=VVEV
k=
VEV.
JEV
Σ 02 dz
(117)
k=1
1=1
K
1 1 (n 1) S Ko² + (n 1) K Kpmax
k=1
(1 + 1) pmaxx Ko².
where di 5d S ... S dn are the singular values of Wt. Therefore,
A2, 5
1
p:
npp 1
2o² + p(1 p) n
- (1 (n - 1) P Ko²
(Np)2
1
np 0
+ Np 1-1 (1 + (n - 1) Pinax o²)
1-p
(118)
Np
2
o²
o²
(1 (n 1) mmax) S N (2 12+p") Prax))
N
N
The last inequality is due to p 1/n.
30

---

Published as a conference paper at ICLR 2022
C.5 PROOF OF PROPOSITION 6
Invoking the descent inequality Lemma D and the error bound for Ti-Ts given by Corollary 2 Proposition 3 and Eq. 41
{)(x*t! <BS(x")
N
2
E Σ
v
? ==0
Σ
(ot
1=1
+0,L211 (T Dr.0) E(a"IV/(>>0)1 +gg) +CLL318722
P Dr.PEL
+C, Pax 0² C,22(22 + D2 Di 1y )
(119)
n
L 0² 2
2
<Bf(x')
Σ
E V {(
+ +CLL11)' (T + Pmnxx Dr.p) Σ
V + +2y) + 72 Pmax D Pr.
==0
)n 30
L + LT 0²
+ C P' ou + Cr2 + Di
N
The last inequality holds under the condition that
1
(120)
2T.
If we further enforce
C.P.11²7 (T + PinxxDr.)) a² 5 71
o2
(121)
8C,L2 (r + Pinxx Dr.p) a²
then
B/(x+t1)
<Bf(x") - !1
Σ
E V
8
+CL (T Maxx Dr.r) C
P Dr 2
+ + Pmnxx 0² + C,L2(92 D2 p Prxx )ny 00²
+ 11 LT 0²
N
-B/(x") - " 8
(T Praxx Dr.p)
(122)
0²)
0² N
+CLL3n
(2 (Dr +z) + (72 + D² Drp
DD
+ +
nh.
/² N (2i
<Ef(x")
" 2 E n
8
+ C, Pinx Dr.r) 2 + L3,
(2
702 Prnux) (h+
( 11
the last inequality is due to Dr T and Pmnax $1. 1.
31

---

Published as a conference paper at ICLR 2022
C.6 PROOF OF PROPOSITION 7
Invoking the descent inequality Lemma D and the error bound for Ti-Ts given by Corollary 2
Proposition 3 and
4
t1
N V
s BBf(2') ) 7
B
V
"E E Σ
4
K
K
E
fi(a
-
7
4
1
Σ
v
fa(( ||
(((
Σ
v
K
Σ
E
gr =
+ E
1
- 111
-
Σ
SEf(x')
E
N
1=1
"
E
E
(x
4 K
+ T (T + Pmnxx Dr.p)
[(2"\V/6>>0)11 + + +1 Praxx D
max 113 ) 0²
+ + 12'1² 1 O 2 +CTT2 + D2 Dr,p
n1
N
L
0²
2 (T 1)
2
N 1=1
N
K
+
LipE
V
J&
(xt 1
K
k=1
+
L
Gp
+
1
Σ
B 12
+ 2 N
L 20
(2+ n
Pmaxx)
(123)
2
N
m
k=1
Denote for short
G, G -
1
(124)
Further applying the bounds on the consensus error derived in Proposition 2
1
N >
2
<kf(x')
)
K
1=1
+ +C,L2n3 - (T + 2 Dr R
++))
Pr Dr Dr.peT.
0=0
32

---

Published as a conference paper at ICLR 2022
+ +GT
+ D² m
L Σ E
N
+ 1/ -1) 0²
+ "
N
s=0
K
+ LIp²E
K
+ 44L,,
202 Σ
D² 7 max 1 (a {2 + tg))
==0
1 Dro + Praxx D Dr
+ +4LG,
C2D Sp Tmmax G.. + C2
L o²
+ ""
2
n
Pmax
(125)
N
m
Rearranging terms and tidy up the expression we have
11(
<Bf(x') - 2/2 Σ E
K
||
N
E
N Σ v((af())))
k=1
1 K
+ LT2²TE
K
k=1
+ +CIL'1j'T (T + + Dra
(a² [1= +
(126)
s=0
&8CG,,LD ppppppp.pp max 2
Σ E(O'VV/6>00)1++ +22)
0²
tGL 7 DrDrppPmaxe EL +2 Prase (72 D2 pmpx
Ti
L (T 1)12
L
(2+ n
22+- - Pmax 11² 220
N+ 2
m
( Dr +1 Prnnx
AC2LG, PD +
T Drip0?2
Notice that the following conditions on the learning rate are satisfied
1 2 I
4
(127)
(T (r+/) 1,'2"
(ronDro)) a² LCD mmaxii
8
33

---

Published as a conference paper at ICLR 2022
then the terms associated to the gradients will be negative and
Bf(x
<Bf(x")
V ((
==
(Pannx Dr + + (2) + +mmax )
+ +CLL (T + Pinax Drip) Eg + 22
TTpp 20²
N (8 p. 1/22
+ +4C2LG,pp D2 (DioTPinn +
Dre + +1) Pimax T
L ( 2
172 o²
Pmax
m
N
In the last step we clean the condition on the learning rate 17. Collecting all the conditions on r7:
1/2 2 24L 11)
(128)
7 2 12 L,
(129)
2 T (r
Prox a² SC2G, 7
(130)
Clearly, 128
implies
129
To ensure
130 it suffices to require
7
T (r + Praax Dr.)) a²
16
(131)
7
2
8C2G' LD2 p.pp " ?²a²
16
Recall the definition of G
G - Gp
1
and Gp
12 m
(132)
72
m(n
It can be verified that if for some Cj2- large enough, then
n 7
(133)
CjaFTL'
"
2
C
(T + P Dr.)) a²
16
?
2
8C2
LD2
Top max 1/2 2 22
32
7
remains guarantee
1
> SC2G,LD2
T.p P 222
(134)
32
Rearranging terms gives the condition
1 256C2G D2.g Prane 2
(135)
Combining with 133 and using the fact that Dropfmax S provides the final condition 1)
{1, Dr.pr.p Punax
17 S
min
(136)
CzarL
34

---

Published as a conference paper at ICLR 2022
D SUPPORTING LEMMAS
D.1 PROOF OF LEMMA
I
Since the global average of the local copies follows the update [cf. 19
gnott x
vs .
(137)
Under Assumption we can apply the descent lemma points Frist and t for 0...., --2 conditioned on Fr,s-1:
Er,s- En S f((--)) ( (shotl- - -xre) + Ena-1
El - 2t.0113
2
@ f(("1)) ((
Vf((e)+)) + +.
- 0mal13 -
( (
= =f(3")) 2 SAl
N
Σ v(((f(t))
K
1
N Σ [((aaa')))
Σ
v + - -11rrttt - -21011
2
K
((3r0)-
Σ v(((a))))
-1 -
1 Σ
2
ト Σ
1
1
1
Σ
(
K
+ 7
ト/
Σ [)((o
Σ
2
K
k=
(1 -oppotl-rrap =11112
+ +E
(c)
<f(="))
2 N
Σ (x(
122
2
V
K k=1
K
+ 2
1 N
Σ VA(aa'))
|| + 7 Vi
1
Tcc 2
K
k=1
K
(
/| + +,,
|| - -
groppp))
K
-=1
where (a) is due to Assumption
2 (b) is due to 2ah = ||a|12 + ||b112 ||a b1I and ab S ||a||]|
and (c) is due to ||a|||b|||
<
b|laa + ||bb1 Notation a = stands for adding and subtracting, i.c.,
b = + 6 b.
For the pair (# +1) we have according to
19 and 22
N
1
E, Epr-2a -2" 2x = Er, g-
17
g.
N
Applying the descent lemma in the same way as before yields
En
<f(a"T-1) + V)( TE, - x2 + I.
E,,r-2
=1 r+1
2
35

---

Published as a conference paper at ICLR 2022
N
K
<((
21
1
1|² |
4/4 K k=1
V fu (T
$1? |
-
-
N
+ 7
V v((
N
1
fi(a
||
+
#
?
V ff
K
1
V
( 2
N
K
1
Σ
+ E Fr,
L
x- 12)
K
Taking expectation, summing over the iterations in round over 8 = 0, .,...,-- 1 and using the fact that x² -r. completes the proof.
D.2 PROOF OF LEMMA 2
Recall the average update of the k-th cluster and that of the global average given by 15 and 19 respectively, for . J
ah.+1
=x/²² -
(138)
N x N 1=1
gratt
9
(139)
Taking the difference gives
B
I
||
- 1 N
-E
(zri
x
17
1 Σ
Σ (((ao
n2
N
iEVi
1
+ ,/²B
Σ t
(140)
VEVE
N
<(1 + +)++BB|\=>** - 2
+ + E
V - N Σ ((ffo))
IEV
1
+ +
N
iEVe
where 0 is some constant be chosen.
Averaging over k = 1, 1...., K:
K
T g1,011
zr.eth gr.s+1p 1|2
K
1=1
K
K K
N
1
<(1 +
E
J.
2/ + (1 + e
E
N Σ
K
k=1
k=1
iEV
1
+ 11 K
n1 3
N
(4)
(1+c)
1
K
E
اri - 37.51 2
K
k=1
+ +(I+ 2
1 KW
Vi(lo!"))
-E
1
Σ
IEV
36

---

Published as a conference paper at ICLR 2022
1 K
N
+ 1p
Σ VeVV
E
5:
|2)
K 1=1
-=1
1 K
1
k -
5(1 +
E -
+ nn²
k
Σ
+ 172
N 0²
K 1=
k=1
iEV
=(1
E B - 1
K
k=1
+ (1 + 6 1)1?
R
+ + V/ +
+ + -1 - 0²
K
N
LEVE
1
スΣ Σ
(VS(('+') -
<(1+
E
K
k=1
IEV2
K
K
+1+ 6 -)) )n 2
E (b(
+
3
Σ
K
K
K- 1 0²
+ +1p N
(6) 1
<(++6
B - 11 + (1 E|)?
3
Σ
L'B
K
N
k=1
k=1
3 +11+ )) 2
1 xk - |
+ (1 + 1mp
3
Σ
K
E
V S [2 /|
+ + 1 K -
N 0²
K
k=1
K
3 K
| x3
=(1+e+
31' +1++6+3L77(1++ -1)
+
B1 - क 112 + (1+ nn?
Σ L'
N
+ +1+
2 3 m
Σ R
+ +1z K - 1
N 2
(141)
In (a) we used the fact that
K
N Σ
K
VA(T!))
Σ
Σ
5h
1
c
(142)
K k=1 VEVL
N
K
N
==1
k=
LVV
and
K Σ || - 51|2 Σ
1 K
||:; - with
3= Ti-
Σ
(143)
K
k=1
In (b) applied the T-smoothness of Ji and Fr.
Choosing c = 17-1 and using the condition that
1 1² S 24T(4T - 1)12
we have
E
5x
11
k=1
2(47 )
1
K Σ
K
< 1+
+
El -x + 12T 2 I
NN
- -1 1
K
37

---

Published as a conference paper at ICLR 2022
k
12T12²
E
Vfk (T t,p
K 1 N
-02
K
k=1
K
1
SC,
B
Bl|
1 +
L2
Σ
E
x
K
k=1
K - 0².
+ 127m/
(a'
(
N
In the last inequality applied Assumption
5 on the inter-cluster heterogeneity.
D.3 PROOF OF LEMMA 3
We follow the perturbed average consensus analysis. Recall the update equation of the consensus error given in (1)
X = (W2 - [xx - ,/(%))
(144)
Squaring both sides and conditioning:
E x 1|2
E (B(IIWW, JX + -
(W, -X - V 1| + PEn2
< p + - - (1 + E pnn
0 is some free parameter to be properly chosen. Next, we bound the norm of the pseudo-gradient (
where So
Σ [V LV
Σ [V)(() +VAG))
VEVE
Σ (4IIV V + vfa(=")))13
VeVe
Σ f
(145)
iEV
(4IV))(E)))
(f + 4L - x5 + 11 - - + ([
VEVE
4L 2 + 4L 1L - x + 4n fa(' + 4
The last inequality is due to Assumption 4 on the intra-cluster heterogeneity.
Averaging over k = I...., K clusters:
E
12
N
K
K
1 K
1
pt + So
V
(1+
2
N
N
K
k=1
K
K
P +
co
B3
21 + (x)
4L
N
N
1=1
k=1
2
Σ
F +11
+ (
K
K
2
Σ
p1 + (c) + P P ²
(146)
K
38

---

Published as a conference paper at ICLR 2022
1 K
max PI + 5x 1 + kE[A]
4T.
max ke[R]
{ + [w))
k
+ 2 max {PX + (h) -422
D0 E ks
- 2T:011?
k
K
k=1
max {p {k)) V + + + kE[K]
1 K
p + Cx) + iipin Σ
k=1
D.4 PROOF OF LEMMA 4
To simplify the notation we omit the superscript in Br in this section.
Let A diag( A1, A2) and the eigendecomposition of TAT-1, we can obtain the closed form expression of I as
A1 Cr A C- T
12T1T"L2
12T1ド
and
T det(T) (
12T1}²
22 + +C, \1 Ct
(-12T177
where
det(T) =
22).
(147)
Consequently
det(T) G B dTl
TA
C 12 1.2
A2 C2
0
12Tr
- + C.
bi
2
X/
L2
\ι - C₁ /
(b2
A1 C,
A2= C₁ 12T
(>g
0
L2b (->2 + C+ bb2 -127r" + (l1 Cz)
12Tri 1.2
X
(148)
C 12T121?
A2 C.
(112217 L
Xf(-xx + C+)62
12
1/112m 1,2b, + 25(A1 C2)
h1
t2
with
4 (A: (4---- Cc)b2)
(149)
L2 = - X/ C+
+ C7)b2)
(150)
+ +127, 1,2 (- + 1g(11, Cz)b1)
Therefore
( + + (A1 (x
C7)b2)
+ ()2 - C+) (- + >b(>1 Cz)b2)
(151)
+ 12 (X C7)62)
+ 12211 (-XgL3122Ty + X5(1 C+)b2).
Substituting the expression of de) and dividing both sides of the equality by 12Th (A1 A2) we
have
1.2 (1,1))ATT-1B
39

---

Published as a conference paper at ICLR 2022
(11 - C.) (2) + +1f(-12 + C7)62)
12T1i(A; (A1 - X2)
+ 12T1/ (A1 - x22
(A2 - -C) (-2, + +2((1 - C2)b2)
1
11² 11 (- + Cr)bb)
+ (A1 -22
+ (A1 -x2)
1.² (-XgLP12T/ + 12(11 -C,)b2
1
-1 (12 C+) 22LL
(A1 - M1 b1 + (71 - X2)
(A1 - x2)
1
+ (A1 -22)
_22$120 12T
L22g 11122t/2b
(A1 -22)
1
(A1 (C+- -f (->2 + Cr) + 12Tm x2)
(A2 - CA) C-)b2
12Tm/ (A1 - x2)
+ (A1 -2)
T,21(( P A2 + Cr)b2 + (A1 -12)
1,2 - -Cr)b2
1
(-12(d2- - C.) - XS(C, - -A1)) L²bb + (\1 - -22)
12Tm (Af - -b)
(A1 -2)
1
1
+
(11 - Cy 22 + CT)62 + 12T1 (A1 - -12)
(A2 -C,) 12 C,)62
12T12 (λ1 22)
+ (A1 22)
I 1221(-2x *2x+ +
I²2g((A1 - -C+)b2
(Λ1 -2)
<XyL2by + N/2 21
N/2 Xi
1
-12772 +
(A2 - -C,)(C, - A11
b2 + XgLLbe,
(152)
X2 A1
x2 d
12T7/2
where in the last inequality we used the fact that \1 S Cr S A2.
Note that
-2-C,)(C -11) C A1d2 + (A1 + A2)C
= C² det(G) + Tr(G)C,
= C² (C, (mnxx P1(1 + C% + + 1LPL AL?) 1.*)
(153)
kE[K]
+ C2 (max pî (1 + 55 + 11 PL 4L2 +C2 kE(K]
48 I
Therefore, we further obtain
(1
- 1,² (127LA4) + +4pr.Lbb2)
(154)
<b + b2) + A₂ X1
Dividing both sides by L completes the proof.
E NETWORK CONNECTIVITY CONDITIONS IN THEOREMS AND COROLLARY
Both Theorem 2 and Corollary I impose some sufficient conditions on the network connectivity Pmax for convergence. This can be satisfied in practice follows. For Theorem 2 as long as Piaax < 1, we can choose T large enough so that ( is fulfilled. Dorollaay[[strengtheee
the result of Theorem by requiring no loss in the order of convergence rate compared to full device participa- tion. This naturally leads to a more stringent condition on Pmax given by (IT). For any given D2D network topology, this can be satisfied by running multiple D2D gossip averaging steps per SGD
40

---

Published as a conference paper at ICLR 2022
update in Algorithm Since the right hand side of (II) depends only the algorithmic parame- ters, we can choose the suitable gossip averaging steps to fulfill this condition before launching the algorithm.
F MORE EXPERIMENTAL DETAILS
In this section, we provide additional experimental results on CIFAR-10 dataset. We follow the same CNN model and non-iid data partition strategy as before and run each experiments for 3 times with different random seeds to report the mean values of best test accuracy. Instead of using constant learning rate, we decay the local learning rate y by half after finishing 50% and 75% of the communication rounds and tune the initial learning rate from (0.01, 0.02, 0.05, 0.08, 0.1) for each algorithm.
lest Accuracy
lest Accuracy
50
50
40
40
(Prea
(Pear 0.9394)
30
HL-SGD (Prcer 0.844)
30
HL-SGD (Pear 0.844)
(/reay
0.5357)
(Pear
HL-SGD (Prex 0)
HL-5GD (Pezr 0)
Local
10
0
20
40
60
80
25
50
75
100
125
Round Number
Runtime (Hour)
(a)
(b)
Figure 4: Convergence and runtime comparisons of HL-SGD and local SGD CIFAR-10 under ER
random D2D network topology. device sampling ratio p 1/8 and local iteration period = 50.
60
60
lest Accuracy
50
Test Accuracy
50
40
40
HL-SGD
HL-SGD
30
30
HL-SG
HL-SGD (i-
IIL-GG ()=5)
IIL-SGD (i=
HL-SGD (1-10)
HL-SGD (i=10)
10
Local SGD
10
Local SGD
20
20
Round Number
Runtime (Hour)
(a)
Figure 5: Convergence rate and runtime comparisons of HL-SGD and local SGD on CIFAR-10 under ring topology and multiple SGD updates before gossip averaging. The device sampling ratio 1, and the local iteration period 50.
First, we evaluate the convergence processes of HL-SGD and local SGD under varying D2D network topologies in Figure 4 We generate random network topologies by Brdöss-Réng model with edge probability from (0.2, 5, 0.8, }} and use Cetropolis-Hastiine spectral norm Pmax (0.9394, 0.844, 0.5357, 0). As observed in Figure more connected D2D network topology (i.c., smaller value of Pmax) generally accelerates the convergence and leads to a higher model accuracy achieved over 100 communication rounds in HL-SGD. However, in terms of runtime, more connected D2D network topology corresponds to a larger D2D communication delay Cuza per round, and hence the total runtime is larger well, which in Figure 4bb] Therefore, to achieve a target level of model accuracy within the shortest time in HL- SGD, sparse D2D network topology could work better than the fully connected one in practice.
weights set Wh. corresponding to
be clearly observed
41

---

might be Published as a conference paper at ICLR 2022
Second, consider an extension of HL-SGD by allowing each device perform multiple SGD updates before the gossip averaging step in Algorithm | and empirically evaluate its performance. Specifically, each device performs with their neighbors the same cluster. Note that = 1 corresponds to the original version of HI.- As observed in Figure 5a when communicating and aggregating models with
{1, 5, 10) steps of SGD update before aggregating models
SGD in Algorithm[] [ neighbors more frequently, HL-SGD with
has the best convergence speed and will converge the highest level of test accuracy. In terms of runtime, choosing a value of favorable in some cases due to the reduced D2D communication delay per round. For instance, to achieve target level of 60% than = 1. It is an interesting direction to rigorously analyze the convergence properties of HL- SGD with arbitrary and find the best hyperparameter tuning method for minimizing the runtime to achieve target level of model accuracy in the future.
accuracy, HL-SGD with
needs 5.22% less amount time
G RELATIONSHIP BETWEEN SPECTRAL GAP AND NETWORK TOPOLOGY
2D-grid 1 1 P O(/nn²) 0(1((n (n n)) 0(1/n)
ring/path
2-D torus
Erdös-Rény:
exponential
0(1)
0(1/ [l/log(n))
Table 2: Spectral gap of some commonly used graphs, where denotes the number of nodes. Results taken from (Nedić (2018): Ying (202I)).
42


Reviews:
[{"review_id": "rJ7TkBg9rkC", "reviewer": "Reviewer_6z2f", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1. The paper adds a new dimension to the federated learning setup by combining local and decentralized SGD approaches and showing that doing so can give more accurate models than those obtained with just local SGD.\n\n2. The theoretical results are intuitive and the convergence analysis explores and highlights the important tradeoffs between intra-cluster connectivity, device sampling rate and convergence rate.\n\nWeaknesses:\n\n1. My main concern is that the evaluation is a bit unfair to local SGD. It seems fairly apparent that averaging models within a cluster after every iteration will outperform local SGD where models are only averaged after $\\tau$ iterations. Moreover while D2D communication over LAN or across nearby devices may be cheap it is potentially more expensive than averaging computations in a single node or a datacenter network. I also find considering a single choice of $W_k$ in experiments to be a bit limiting (since it seems like the mixing matrix really depends on the setting). Therefore I would suggest the following performing the following additional experiments:\n\na) D2D communication after multiple SGD updates (the analysis for this may be complicated but it would be instructive to see the empirical performance).\n\nb) Experiments with varying $W_k$ (also do mention the value of $\\rho_{\\max}$ corresponding to the choice of $W_k$)\n\n2. A couple of claims rely on being able to tune the intra-cluster communication parameters -  $W_k$ (as in Corollary 1) and $c_{\\text{d2d}}$ (as in the results in Fig. 3) - to obtain improved performance. Is it really possible to tune these parameters in real world settings? I would suggest adding a citation to support this.", "summary_of_the_paper": "The paper introduces a new hybrid scheme combining local and decentralized SGD by considering a network with one central node (server) and multiple worker nodes (devices) grouped into clusters with fast intra-cluster communication but slow device to server communication. The authors show that in such settings replacing local SGD with intra-cluster averaging of iterates after each SGD update can lead to faster convergence. Theoretical analysis explores the tradeoff between intra-cluster connectivity, device sampling rate, and convergence rate, while experiments on CIFAR10 and FEMNIST with non-iid splits shows that the proposed approach yields higher test accuracy than local SGD for a given runtime/number of rounds.", "summary_of_the_review": "The paper definitely adds to the discussion in Federated Learning and by introducing an interesting new setting of hybrid local SGD. Therefore I am leaning towards accepting it. However while the analysis captures the important tradeoffs, the experiments are a bit limited and seem slightly unfair to the local SGD baseline. If these can be rectified (following my suggestions above or otherwise) I would be completely convinced about accepting it\n\nComments after Rebuttal: Thank you for adequately responding to my queries. I am satisfied with the revisions made to the paper and have updated my score to reflect the same.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "bQCxtRGvVQ", "reviewer": "Reviewer_y58n", "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": "The presentation of the paper is very clear and easy to follow. The strength of the paper lies in the theoretical analysis, where combining decentralization and federated average is not straightforward at all. The theoretical result is a bit hard to digest, further clarification and comparison with existing method would make it more readable. The experimental section is also less convincing. My detailed comments are as follows. \n\n1 Theoretical discussion:  it is not clear from the current presentation how to choose the parameter $\\tau$ (number of decentralized updates per rounds) Ideally, it would need to balance (i) the D2S communication cost and the D2D communication cost (ii) intra-cluster convergence and outer-loop (round) convergence. In other words, is there any tradeoff between improving the heterogeneous communication versus having better convergence rate. For the discussion on $\\rho_{max}$, how it scales with $n$ in a non-extreme situation. The current discussion mostly focus on it being 0 (fully connected) or 1 (no connection), it would be good to discuss its scaling with $n$ in a less trivial situation.\n\n2 Empirical study:  the experiments are performed with a fixed $\\tau$. However, the local SGD may have a different regime on the dependency of $\\tau$. I encourage the authors to provide more comparison on how $\\tau$ influence the performance in figure, for instance with $\\tau =5, 10, 20$. The ablation study in Figure 4& 5 is also not convincing as it seems no difference. In particular, changing $\\rho$ does not lead to any performance or run time change. This might suggest that the local problem is too simple that be efficiently solved even the connectivity is bad.  \n\n3 Privacy concern: the lack of discussion on the privacy issue is a major omission in the paper. The decentralized communication within cluster requires client to exchange information with others, raising potential concerns on leaking informations. I believe this need to be carefully addressed as privacy is one of the major difference in Federated Learning compared to traditional distributed training.\n\nOverall, the theoretical study has merit while the empirical study is less convincing,   ", "summary_of_the_paper": "The paper proposes a new method to address the heterogeneous communication setting in a hierarchical distributed system.  The system consists of a central server and several disjoint clusters, and each cluster is a local network connection between multiple edge devices. The communications are heterogeneous in the sense that in cluster device to device (D2D) communication are much faster than the device to server (D2S) communication. The proposes algorithm is a hybrid method where decentralized method is applied within clusters (on edge devices) and federated average is applied between cluster and server. Convergence analysis is provided showing the benefit of variance reduction using decentralization within cluster. Empirical studies are conducted to demonstrate the improvement under synthetic federated learning environment.", "summary_of_the_review": "The theoretical study has merit while the empirical study is less convincing,   ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "KgC53hbMukO", "reviewer": "Reviewer_87Gc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\nThe proposed algorithm takes good advantage of the fast local connectivity among the nodes to improve the convergence. It is a novel contribution. \n\nDetailed convergence analysis of the proposed algorithm is provided. \n\nWeakness:\nWhile the Theoretical results emphasize the role of the local topology in each cluster, the corresponding numerical analysis to understand the impact of topology is missing. It would be interesting to see how the connectivity parameter $\\rho$ impacts the results in Figure 1 to 5, instead of just taking a ring topology. ", "summary_of_the_paper": "This paper proposes a new Federated learning algorithm which can take advantage of the fast D2D (Device-to-Device) connections among the devices. In particular, it is shown that the proposed algorithm has better performance in terms of convergence rate and accuracy compared to the existing algorithms such as 'Local SGD'-based FL which rely only on the slow D2S connections for model updating. The convergence of the proposed algorithm is theoretically characterized in terms of the D2D connectivity (topology). Numerical results are provided to show the improved performance compared to the local sgd-based FL.\n", "summary_of_the_review": "The proposed algorithm is novel and the the performance is rigorously characterized. The improvement compared to existing algorithms is significant and hence I believe it should be accepted for publication. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "Ci5HzH30-9e", "reviewer": "Reviewer_4Rc7", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes to use a hybrid model aggregation to conduct federated learning leveraging both high-speed D2D network and low-speed D2S network. \n\nPros:\n1. The idea proposed in the paper is easy to follow, and the research direction of enhancing the communication efficiency of federated learning is potentially impactful. \n2. Both theoretical analysis and empirical results are provided to justify the effectiveness of HL-SGD. \nCons: \n1. The main concern I have for the paper is that the proposed idea lacks novelty. Hierarchical federated learning has been studied extensively in the literature [1,6] as well as hierarchical local SGD [3]. Why is HL-SGD fundamentally novel? \n2. The theoretical analysis also seems to make sense, but it would be valid to show the comparison among the convergence rates among this work and the prior methods. \n3. The scale of the experiments is too small. What are the sizes of the CNNs used for training EMNIST and CIFAR-10 in the experiments? I won’t assume the authors are using large CNNs, but for small-scale models, why will train them to incur communication bottlenecks? \n4. Apart from communication efficiency, another big motivation for federated learning is data privacy. Does HL-SGD come with any privacy guarantee? If not, can it be compatible with existing privacy-preserving methods, e.g., Secure Aggregation [4]? \nMinor comments:\nTypo: “no-iid” —> “non-iid”\n\nMissing references: [4-5]\n\n[1] https://arxiv.org/pdf/1905.06641.pdf\n\n[2] https://arxiv.org/pdf/1909.02362.pdf\n\n[3] https://arxiv.org/abs/2007.13819\n\n[4] https://eprint.iacr.org/2017/281.pdf\n\n[5] https://arxiv.org/abs/2107.06917\n\n[6] https://arxiv.org/pdf/2103.10481.pdf", "summary_of_the_paper": "This paper introduces HL-SGD, a method to design a hybrid federated learning method to leverage a hybrid high-speed D2D and low-speed D2S network and speed up the communication of federated learning applications. Both theoretical analysis and empirical results are provided to show the effectiveness of HL-SGD.", "summary_of_the_review": "Overall I think the proposed method is a natural extension from the previous work. And the novelty is quite marginal. The experimental evaluation can be largely improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper contributes to the literature on federated learning by introducing a hybrid local SGD (HL-SGD) method. HL-SGD is motivated by the setups where edge devices are grouped into clusters with fast connections within the cluster, but slower connection between the devices and the server. HL-SGD uses hybrid updates: decentralized updates within the clusters and federated averaging steps between the clusters and the server. 

Initially, the reviews expressed concerns regarding comparison to prior work, empirical results, and privacy of the proposed scheme. However, the authors adequately addressed all of the concerns, added relevant discussions and results to the paper, and a consensus was reached that the paper should be accepted.
Decision: Accept (Spotlight)