Multi-Level Local SGD: Distributed SGD for Heterogeneous Hierarchical Networks
Authors: Timothy Castiglia
Anirban Das
Stacy Patterson
Venue: ICLR 2021 Poster (2021)
Keywords: Machine Learning
Stochastic Gradient Descent
Federated Learning
Hierarchical Networks
Distributed
Heterogeneous
Convergence Analysis

Abstract: We propose Multi-Level Local SGD, a distributed stochastic gradient method for learning a smooth, non-convex objective in a multi-level communication network with heterogeneous workers. Our network model consists of a set of disjoint sub-networks, with a single hub and multiple workers; further, workers may have different operating rates. The hubs exchange information with one another via a connected, but not necessarily complete communication network. In our algorithm, sub-networks execute a distributed SGD algorithm, using a hub-and-spoke paradigm, and the hubs periodically average their models with neighboring hubs. We first provide a unified mathematical framework that describes the Multi-Level Local SGD algorithm. We then present a theoretical analysis of the algorithm; our analysis shows the dependence of the convergence error on the worker node heterogeneity, hub network topology, and the number of local, sub-network, and global iterations. We illustrate the effectiveness of our algorithm in a multi-level network with slow workers via simulation-based experiments.

Published as a conference paper at ICLR 2021
MULTI-LEVEL LOCAL SGD: DISTRIBUTED SGD FOR HETEROGENEOUS HIERARCHICAL NETWORKS
Timothy Castiglia, Anirban Das, and Stacy Patterson"
ABSTRACT
We propose Multi-Level Local SGD, distributed stochastic gradient method for learning a smooth, non-convex objective in a multi-level communication network with heterogeneous workers. Our network model consists of set of disjoint sub- networks, with a single hub and multiple workers; further, workers may have dif- ferent operating rates. The hubs exchange information with one another via a connected, but not necessarily complete, communication network. In our algo- rithm, sub-networks execute a distributed SGD algorithm, using a hub-and-spoke paradigm, and the hubs periodically average their models with neighboring hubs. We first provide a unified mathematical framework that describes the Mulei-Level Local SGD algorithm. We then present theoretical analysis of the algorithm; our analysis shows the dependence of the convergence error on the worker node heterogeneity, hub network topology, and the number of local, sub-network, and global iterations. We illustrate the effectiveness of our algorithm in a multi-level network with slow workers via simulation- basedd experiments.
INTRODUCTION
Stochastic Gradient Descent (SGD) is key algorithm in modern Machine Learning and optimiza- tion (Amari, 1993). To support distributed data as well as reduce training time, Zinkevich et al. (2010) introduced distributed form of SGD. Traditionally, distributed SGD is within hub- and-spoke network model: a central parameter server (hub) coordinates with worker nodes, At each iteration, the hub sends model the workers. The workers each train their local data, taking gradient step, then return their locally trained model to the hub to be averaged. Distributed SGD can be an efficient training mechanism when message latency is low between the hub and workers, allowing gradient updates to be transmitted quickly at each iteration. However, as noted in Moritz al. (2016), message transmission latency is often high in distributed settings, which causes large increase in overall training time. A practical way to reduce this communication overhead is to allow the workers to take multiple local gradient steps before communicating their local models to the hub. This form of distributed SGD is referred to as Local SGD (Lin et al., 2018; Stich, 2019). There is a large body of work that analyzes the convergence of Local SGD and the benefits multiple local training rounds (McMahan et al., 2017; Wang & Joshi, 2018; Li et al., 2019).
Local SGD is not applicable to all scenarios. Workers may be heterogeneous in terms of their com- puting capabilities, and thus the time required for local training not uniform. For this reason, it can be either costly or impossible for workers to train in a fully synchronous manner, as stragglers may hold up global computation. However, the vast majority previous work uses synchronous model, where all clients train for the same number of rounds before sending updates to the hub (Dean et al., 2012: Ho al., 2013; Cipar et al.. 2013). Further, most works assume a hub-and-spoke model, but this does not capture many real world settings. For example, devices in an ad-hoc network may not all be able to communicate a central hub in a single hop due network or communication range limitations. In such settings, multi-level communication network model may be beneficial. In fly- ing ad-hoc networks (FANETs), a network architecture has been proposed to improve scalability by partitioning the UAVs S into mission areas (Bekmezci et al., 2013). Here, clusters of UAVs have their own clusterheads, or hubs, and these hubs communicate through an upper level network, e.g., via satellite. Multi-level networks have also been utilized in Fog and Edge computing, paradigm de-
*T. Castiglia, A. Das, and S. Patterson are with the Department of Computer Science, Rensselaer Polytech- nic Institute, 110 8th St, Troy, NY 12180, castitêre eddu, dasa28rpi eddu, sepêcs. rpi edd.

---

Published as a conference paper at ICLR 2021
signed to improve data aggregation and analysis in wireless sensor networks, autonomous vehicles, power systems, and more (Bonomi et al., 2012; Laboratory, 2017; Satyanarayanan, 2017).
Motivated by these observations, we propose Multi-Level Local SGD (MLL-SGD), distributed learning algorithm for heterogeneous multi-level networks. Specifically, we consider a two-level network structure. The lower level consists of disjoint set of hub-and-spokk sub-networks, each with a single hub server and a set of workers. The upper level network consists of a connected, but not necessarily complete, hub network by which the hubs communicate. For example, in a Fog Computing application, the sub-network workers may be edge devices connected to their local data center, and the data centers act as hubs communicating over a decentralized network. Each sub- network runs one or more Local SGD rounds. in which its workers train for a local training period, followed by model averaging at the sub-network's hub. Periodically, the hubs average their models with neighbors in the hub network. We model heterogeneous workers using stochastic approach; each worker executes a local training iteration in each time step with a probability proportional to its computational resources. Thus, different workers may take different numbers of gradient steps within each local training period. Note since MLL-SGD averages every local training period, regard- less of how many gradient steps each worker takes, slow workers do not slow algorithm execution.
We prove the convergence of MLL-SGD for smooth and potentially non-convex loss functions. We assume data is distributed in an IID manner to all workers. Further, we analyze the relationship between the convergence error and algorithm parameters and find that, for a fixed step size, the error is quadratic in the number of local training iterations and the number of sub-network training iterations, and linear in the average worker operating rate. Our algorithm and analysis are general enough to encompass several variations of SGD as special cases, including classical SGD (Amari, 1993), SGD with weighted workers (McMahan et al., 2017), and Decentralized Local SGD with an arbitrary hub communication network (Wang & Joshi, 2018). Our work provides novel analysis of a distributed learning algorithm in a multi-level network model with heterogeneous workers.
The specific contributions of this paper are as follows. 1) We formalize the multi-level network model with heterogeneous workers, and we define the MLL-SGD algorithm for training models in such a network. 2) We provide theoretical analysis of the convergence guarantees of MLL- SGD with heterogeneous workers. 3) We present an experimental evaluation that highlights our theoretical convergence guarantees. The experiments show that in multi-level networks, MLL-SGD achieves marked improvement in convergence rate over algorithms that do not exploit the network hierarchy. Further, when workers have heterogeneous operating rates, MLL-SGD converges more quickly than a algorithms that require all workers to execute the same number of training steps in each local training period.
The rest of the paper is structured follows. In Section 2, discuss related work. Section introduces the system model and problem formulation. We describe MLL-SGD in Section 4, and present our main theoretical results in Section 5. Proofs of these results are deferred to the appendix. We provide experimental results in Section 6. Finally, we conclude in Section 7.
RELATED WORK
Distributed SGD is a well studied subject in Machine Learning. Zinkevich et al. (2010) introduced parallel SGD in a hub-and-spoke model. Variations on Local SGD in the hub-and-spoke model have been studied in several works (Moritz et al., 2016; Zhang et al., 2016; McMahan al., 2017). Many works have provided convergence bounds of SGD within this model (Wang et al., 2019b; Li al., 2019). There is also a large body of work on decentralized approaches for optimization using gradient based methods, dual averaging, and deep learning (Tsitsiklis et al., 1986; Jin et al., 2016; Wang et al., 2019a). These previous works, however, do not address a multi-level network structure.
In practice, workers may be heterogeneous in nature, which means that they may execute training iterations at different rates. Lian et al. (2017) addressed this heterogeneity by defining a gossip- based asynchronous SGD algorithm. In Stich (2019), workers are modeled to take gradient steps at an arbitrary subset of all iterations. However, neither of these works address a multi-level network model. Grouping-SOC SGD (Jiang et al., 2019) considers scenario where workers can be clustered into groups, for example, based on their operating rates. Workers within a group train in a synchronous manner, while the training across different groups may be asynchronous. The system model differs
2

---

Published as a conference paper at ICLR 2021
significantly from that in MLL-SGD in that as the model parameters are partitioned vertically across multiple hubs, and workers communicate with every hub.
Several recent works analyze Hicrarchical Local SGD (HL-SGD), algorithm for training model in a hierarchical network. Different from MLL-SGD, HL-SGD assumes the hub network topology is hub-and-spoke and also that workers are homogeneous. Zhou & Cong (2019) and Liu et al. (2020) analyze the convergence error of HL-SGD, while Abad et al. (2020) analyzes convergence time. Unlike HL-SGD, MLL-SGD accounts for an arbitrary hub communication graph, and MLL-SGD algorithm execution does not slow down in the presence of heterogeneous worker operating rates.
Several other works seek encapsulate many variations of SGD under a single framework. Koloskova et al. (2020) created a generalized model that considers gossip-based decentralized SGD algorithm where the communication network is time-varying. However. this work does not account for multi-level network model nor worker heterogeneity. Wang et al. introduced the Co- operative SGD framework (Wang Joshi, 2018), a model that includes communication reduction through local SGD steps and decentralized mixing between homogeneous workers. Cooperative SGD also allows for auxiliary variables. These auxiliary variables can used to model SGD in a multi-level network, but only when sub-network averaging is immediately followed by hubs averag- ing with their neighbors in the hub network. Our model is more general; it considers heterogeneous workers and it allows for arbitrary number of averaging rounds within each sub-network be- tween averaging rounds across sub-networks, which is more practical in multi-level networks where inter-hub communication is slow or costly.
3 SYSTEM MODEL AND PROBLEM FORMULATION
In this section, we introduce our system model, the objective function that we seek to minimize, and the assumptions we make about the function.
We consider a set of D sub-networks D {l...., D). Each sub-network d E D has single hub and set of workers ((d), with |. (d), Workers in (M only communicate with their own hub and not with any other workers or hubs. We define the set of all workers in the system as M = U M(4)) Let [M| N. Each worker holds set S(i) of local training data. Let = U s(0 The set of all D hubs is denoted C. The hubs communicate with one another via an undirected, connected communication graph G = (C, E). Let N₂ = {i ed.j E E} denote the set of neighbors of the hub sub-network in the hub graph G.
Let the model parameters be denoted by E R". Our goal is to find an x that minimizes the following objective function over the training set:
F(x)
f((;))
(I)
S
where f(-) is the loss function. The workers collaboratively minimize this loss function, in part by executing local iterations of SGD over their training sets. For each executed local iteration, a worker samples a mini-batch of data uniformly at random from its local data. Let & be a randomly sampled
mini-batch of data and let g(x; {) [c] Exes vf(x; s) be the mini-batch gradient. For simplicity, we use g(x) instead of g( from here on. Assumption 1. The objective function and the mini-batch gradients satisfy the following:
la The objective function F : IT + is continuously differentiable, and the gradient is Lipschitz with conslant L > 0, ie., [VV - VF(y)]l2 S L||e -yll all x. IR..
1b The function F is lower bounded, i.e., F(x) > Fins co for all x E R". gradients are unbiased, i.e., Eg [=(=)] v F(x) ) all R".
Ic The
1d There exist scalars 3 2 0 and a 2 O such that Egje (l((x) V F(=) < VVF() 12 for all E R.
Assumption Ia requires that the gradients do not change too rapidly, and Assumption lb requires that objective function is lower bounded by some Fing- Assumptions Ie and 1d assume that
3

---

Published as a conference paper at ICLR 2021
Algorithm 1 Multi-Level Local SGD
Initialize: v(()) for hubs d I....,D
2: for k 1. K do
3: parallel for d D do
4: parallel for MM do
(d)
5:
yk
Workers receive updated model from hub
6:
for j k....,
do
7:
#++1
(6) +- Ktk
199
Di Local iteration (probabilistic)
8:
end for
9:
end parallel for (4)
10:
Eiemie 20 (
Hub d computes average of its workers' models
11:
if k mod q. 0 then
12:
yk+l EjENio H Hz,a
(d)
Hub d averages its model with neighboring hubs
13:
else
14:
y + (()
(d)
15:
end if
16:
end parallel for
17:
end for
the local data at each worker can be used as unbiased estimate for the full dataset with the same bounded variance. These assumptions are common in convergence analysis of SGD algorithms (e.g., Bottou et al. (2018)).
ALGORITHM
We now present our Multi-Level Local SGD (MLL-SGD) algorithm. The pseudocode is shown in Algorithm 1. Each sub-network trains in parallel and, periodically, the hubs average their models with neighboring hubs. The steps corresponding to Local SGD shown in lines 5-10. Each hub and worker stores copy of the model. For worker i MM()) we denote its copy of the local model by z(0)) We denote the model at hub d by y( The hub first sends its model to its workers, and the workers update their local models to match their hub's model. Workers then execute multiple local training iterations, shown in line 7, to refine their local models independently. To represent the different rates of computation at each worker, we use a probabilistic approach. We assume that, in expectation, a worker exccute 7()) local iterations for every T time steps (7(1) I T). We thus define the Nevector where each entry p, 2(6)) is the probability with which worker executes local gradient step in each iteration Worker i updates its local model at iteration & as follows:
(8) æ
#k41
ng
where 77 the step size and g (6)
a random variable such that
g g(((())
w/ probability ps
(3)
w/ probability 1 1-p:.
After т time steps, the hub updates its model based on the models of its workers (line 10). For each worker assign positive weight w(+), Let e(() be the weight for worker i normalized
within its sub-network: p(t)) Σ Eeeaiae w where d(i) denotes the sub-network of worker
w
Each hub's 's updates its model to be a weighted average over the workers' models in its sub-network:
y (d) Mi))( (1) Weights may be assigned for different reasons. all worker gradients
are treated equally, then ( 1 and p(i)) N We may also weight worker's gradient
proportional its local dataset size, in which case ( ||(() and p(t) E.EM(ton |801 The
|8(0)
latter approach is used in Federated Averaging (MeMahan al., 2017).
After q iterations of Local SGD in each nub-network (q.7 T time steps), the hubs average their models with their neighbors in the hub communication network (line 12). The weight assigned to each hub's
4

---

Published as a conference paper at ICLR 2021
model is defined by D D matrix H so that:
y (d)
Σ
H H,
JEN(()
Define the total weight in the network be whot LIEM w() Let b be a D-vector with each component d given by ba = (EiEmta) w(())/ Assumption 2. The matrix H satisfies the following:
/Wrott We assume H meets the following requirements.
2a If (i.j) E E, then Haj > 0. Otherwise, H =
2b H is column stochastic, i.e., Σ Hij=1. =1
2c For all i, E DD we have b, b, b, H2
Assumption 2 implies that H has one as a simple eigenvalue, with corresponding right eigenvector b and left eigenvector 1p. Further, all of its other eigenvalues have magnitude strictly less than (since is connected) (Rotaru & Nägeli, 2004). By defining H in this way, we ensure that the contributions from the workers' gradients in each hub are incorporated in proportion the workers' weights. This weighted averaging approach allows us to naturally extend Federated Averaging to the multi-level network model.
ANALYSIS
We note that hubs are essentially stateless in MLL-SGD, the hub models are copied to all workers after each sub-network or hub averaging. Thus, our analysis focuses on how worker models evolve. We first present equivalent formulation of the MLL-SGD algorithm in terms of the evolution of the worker models. We then present our main result on the convergence of MLL-SGD.
The system behavior can be summarized by the following update rule for worker models:
X = (X, Gx) Ta
(5)
where n x N matrix X, [ (3)) n N matrix G. = 19 . 9 (N) and N x N matrix Ta is a time-varying operator that captures the three stages in MLL-SGDD local iterations, hub-and- spoke averaging within each sub-network, and averaging across the hub network. We define Tç as follows:
(1)
Z if k mod qT 0
Te v if k mod 7 0 and l mod qT + otherwise.
interactions between workers or hubs. For sub-network averaging, V is an N x N block diagonal matrix, with each block (dd) corresponding to a single sub-network The matrix v(d) an Nid) x (d)) matrix where each entry is v!d) = v(() Finally,
For local iterations, Tr
there
we define an N x N matrix Z. that captures the sub-network averaging and hub network averaging in one operation that involves all workers. The components of Z are given by
Zij (((
Let be N-vector with each component a; went representing the weight of worker i, nor- malized over all worker weights. We observe that Z and V satisfy the following: each have right eigenvector of and left eigenvector of I/y with eigenvalue and all other eigenvalues have magni- tude strictly less than 1. The proof of these properties can be found in the appendix. These properties necessary (but not sufficient) to ensure that the worker models converge to consensus model, where each worker's updates have been incorporated according to the worker's weight.
As is common, study averaged model over all workers in the system (Yuan al., 2016; Wang & Joshi, 2018). Specifically, we define a weighted average model:
Uk
X
(8)
5

---

Published as a conference paper at ICLR 2021
We identify the recurrence relation of ug. If we multiply on both sides of (5):
X (Xi: -n -nG),) Tx
(9)
uk+1 = U2 G a
(10)
N
ui+1 = uu
(11)
where (10) follows from being right eigenvector of V and Z with eigenvalue 1. We note that us is updated via a stochastic gradient descent step using a weighted average of several mini-batch gradients. Since F-) may be non-convex, SGD may converge local minimum saddle point. Thus, we study the gradients uy as increases.
We next provide the main theoretical result of the paper.
Theorem 1. Under Assumptions and 2, if satisfies the following for all i E M:
(4p- - p² -2 n (33 + +) -a.p. + +p?) + 1f -
(12)
where r = + ---y and Ç max ( (1) I (H)l,, then the expected square norm of the average model gradient, averaged over iterations, is bounded as follows:
K
2 (F((1) - Fonsl) + Σd
E
VF VF(uu))
a;p:
4/K
k=1
i=1
1)
2²
1- (1 C)2 )P
2
1
4LL
+
QT
K
(2
(2 (2-9) 5)
72/9
1)(24 +1)
(T- (1-1)(27+))) +12
4L'1102
+
P
(13)
6
K-+00
NLyL Σ 1=1
N
a
p + 4L 1L2 1//7/00 0222
+
25
+
1-
1-
(1- c)²
4L' (2-5)
(-2(9
1) + 1)
(r- 1) + 1)
P
(14)
6
6
where P = ENN a.p:
The proof of Theorem is provided in the appendix. The first term in (13) is the same as in central- ized SGD (Bottou et al., 2018). As + oo, this term goes to zero. The second term is similar to centralized SGD as well If the stochastic gradients have high variance, then the convergence error will be larger. This term also related to the convergence error in distributed SGD (Bottou et al., 2018), which is equivalent to MLL-SGD when there is one sub-network, 9 = 1, a, 1/N, and p, = 1 for all i. MLL-SGD has a dependence on the probabilities of gradient steps and worker weights, replacing the N in the equivalent term in distributed SGD.
The third and fourth terms in (13) are additive errors that depend on the topology of the hub network. The value of { is given by the second largest eigenvalue of H, by magnitude, which is an indication of the sparsity of the hub network. When worker weights are uniform, a fully connected hub graph G will have only depends on H, and not Z or V, meaning the convergence error does not depend on how worker weights are distributed within sub-networks.
O. while a sparse G will typically have Ç close to It is interesting note that
We also note the third and fourth terms depend on P. the weighted average probability of the work- ers. The convergence error increases as the average worker operating rate increases. This relation is expected as more local iterations will increase convergence enror (Wang & Joshi, 2018). It is interestingg to note that the convergence error does not depend on the distribution of p, meaning that skewed and uniform distribution with the same average probability would have the same conver- gence error. We observe that the condition on r in (12) cannot always be satisfied given certain probabilities. Specifically, when there exists a P: < 2 - v2 z 0.59, then the left-hand side will be non- non-positive, and the inequality tive bound, intuitively, when p, 's are below this threshold, the algorithm may not make sufficient progress in each time step to guarantee convergence.
longer be satisfied. Although this may be conserva-

---

Published as a conference paper at ICLR 2021
1.0
1.0
Euiled SGD
0.9
0.6
MLL-SGD rw8
Local SGi r=32
Accuracy
0.9
MLL-SGD
0.8
Distributed SGD
0.4
Local 5GD
0.2
0.7
MLL 5G0 q-8 T-4
q
0.0
0.6
4000
(a) Training loss of CNN trained on EMNIST.
(b) Test accuracy of CNN trained EMNIST.
2.0
0.50
Distributed SGD
1.5
Local SGD t-32
0.45
Accurac
2
qu8
Distributed SGD
Local SGD 1-32 MLL-5000 q=4
0.35
MLL-SG0 qm8
0.0
2000
4000
6000
0.30
2000
6000
(c) Training loss of ResNet- 18 trained on CIFAR-10. 10. (d) Test accuracy of ResNet-18 trained on CIFAR-I0.
Figure 1: Effect a hierarchy with different values and q.
The third and fourth terms also grow with 9 and т. the number of local iterations per hub network averaging and sub-network averaging steps, respectively. The longer workers train locally without reconciling their models, the more their models will diverge, leading larger convergence error. We can see that plays slightly larger role in convergence enror than q. For given & т, meaning given number of time steps between hub averaging steps, a larger leads to higher convergence error than larger g would. Thus, there is slight penalty to performing more local iterations between sub-network averaging steps. We explore this more Section 6.
We note that when setting a; 1/N and p; 1 for all workers i, and setting q 1, MLL-SGD reduces to Cooperative SGD. However, the bound in Theorem differs from that of Cooperative SGD. Specifically, Theorem 1 has error terms dependent on 72 opposed in Cooperative SGD. This discrepancy is due to accommodating all possible values of pi. More details can be found in Appendix C.4.
In the following corollary, we analyze the convergence rate of Algorithm when 1) LVK
Corollary 1. Let
- and let q2 < K. If < K, then
LvK
o²
E
V
up
11
0
(F(x))-FF +0
(15)
VK
VK
Under the conditions given in Corollary 1, MLL-SGD achieves the same asymptotic convergence rate Local SGD and HL-SGD.
EXPERIMENTS
In this section, we show the performance of MLL-SGD compared to algorithms that do account for hierarchy and heterogeneous worker rates. We also explore the impact of the different algorithm parameters that show up in Theorem
We use the EMNIST (Cohen et al., 2017) and CIFAR-10 (Krizhevsky et al., 2009) datasets. For all experiments, we provide results for training a simple Convolutional Neural Network (CNN) on EMNIST and training ResNet-18
CIFAR-10. 10. The CNN has two convolutional layers and two fully connected layers. We train the CNN with a step size 0.01. For ResNet, we use a standard approach of changing the step size from 0.1 to 0.01 to 0.001 over the course of training (He al., 2016). We conduct experiments using Pytorch 1.4.0 and Python 3.
We compare MLL-SGD with Distributed SGD, Local SGD, and HL-SGD, Distributed SGD is equiv- alent to MLL-SGD when there is one hub, = T = 1, and a, = 1/N and p; = 1 for all i, which means Distributed SGD averages all worker models every iteration. Thus, Distributed

---

Published as a conference paper at ICLR 2021
1.0
Distributed SGD
Distributed SGD
0.8-
Local SGD
Hubs-5 Workers=20
Hubses Workers
5
Hubi-10 Workens-
0 1.0
Nuby-10 Workers-10
0.4
Hubi=20 WorkerseS
0.3
Nlubs Workers
0.2
0.0
2000
4000
6000
2000
4000
6000
Figure 2: Effect of worker distribution on CNN
Figure 3: Effect of worker distribution on ResNet-
trained on EMNIST.
18 trained on CIFAR-IO.
1.0
Probi1 Fixed
0.0
Fixed
Uniform
Uniform Dist
g08
0.4
Scewed
Skowed
02
2000
6000
6000
Figure 4: Effect of heterogeneous operating rates on CNN trained on EMNIST.
Figure 5: Effect of heterogencous operating rates on ResNet-18 trained on CIFAR-10.
SGD as a baseline for convergence error and accuracy in some experiments. Local SGD is equiva- lent to MLL-SGD when a; = 1/N and p; 1 for all i, when the hub network is fully connected, and g = 1. HL-SGD extends Local SGD to allow q > 1. For all experiments, we let = 32 for Local SGD, We let gT 32 for all HL-SGD and MLL-SGD variations to be comparable with Local SGD. In all experiments, we measure training loss and test accuracy of the averaged model ut every 32 iterations.
We first explore the effect of different values of r and in MLL-SGD. We configure a multi-level network with fully connected hub network and with 10 hubs, each with 10 workers. We use two configurations for MLL-SGD, one with r = and g = 4, and one with r = 4 and 8. Distributed SGD and Local SGD treat the hubs pass-throughs, and average all workers every iteration and every 7 iterations respectively. Workers are split into five groups of 20 workers each. Each group is assigned a percentage of the full dataset: 5%. 10%, 20%, 25%, and 40%. Workers within group partition the data evenly. The workers weights are assigned based on dataset sizes. In Figures la and we plot the training loss, and in Figures 1b and Id we plot the test accuracy for the CNN and ResNet, respectively. We observe that increases, while keeping q7 = 32, MIL-SGD improves and approaches the Distributed SGD baseline. Thus, increasing the number sub-network training rounds improves the convergence behavior of MLL-SGD. The benefit is more pronounced in training ResNet on CIFAR.
We next investigate how the number and sizes of the sub-networks impacts the convergence of MLL- SGD. From a pool of 100 workers, we distribute them across 5, 10, and 20 sub-networks. The hub network is path graph, which yields the largest < while keeping the network connected. This hub network topology the worst-case scenario in terms of the convergence bound. Note that as the number of hubs increases, the larger becomes. We let a, 1//N and p. 1 for all workers i. We set q = 4 and 7 = 8. We also include results using Local SGD with 1 hub and 100 workers. The results of this experiment are shown in Figures and 3. In the case of the CNN, the difference in training loss is minimal among the MLL-SGD variations. In the case of ResNet we can see that as the number of hubs increase, the convergence rate decreases. This is line with Theorem since an increased number hubs corresponds with an increased Ç. Interestingly, despite the low hub network connectivity, MLL-SGD outperforms Local SGD. This shows that MLL-SGD still benefits from hierarchy even when hub connectivity is sparse.
Next, we explore the impact of different distributions of worker operating rates. According to The- orem 1, the average probability across workers plays role in the error bound. To see if this holds in practice, we compare four different MLL-SGD setups, all which includes a complete hub net- work, 10 hubs, each with 10 workers,
1/N, and an average probability amongst workers of 0.55: (i) all workers with P; = 0.55 (Fixed); (ii) workers in each sub-network with probability ranging from 0.1 to steps of 0.1 (Uniform Distribution); (iii) 90 workers with p: 0.5 and 10 workers with p; = (Skewed 1); (iv) 90 workers with p, = 0.6 and 10 workers with p. = 0.1 (Skewed 2). We include where all workers have p. 1 as baseline (Prob=1). In Figures
8

---

Published as a conference paper at ICLR 2021
1.0
MUL-SOn m-
0.8
SGD
Accuracy
8 000
HL-500 qud mag
0.8
Local T-32
0.4
0.7
MLL-SG0 q:44 T
02
HL-SE02 qo4 red
2000
6000
6000
0.6
4000 Time slats
Time siots
(a) Training loss of CNN with respect time slots.
(b) Test accuracy of CNN with respect to time slots.
2.0
MIL-5G0 q=1 1232
0.45
1.3
Local SGD 1-52
g
MLL-SGD q-4 re8 q-4
Accuary
0.40
q=1 Local 5CD n-32
0.5
0.35
MIL-SGD qmd x-0 HL-5GD gm4 c-8
0.30
2000
4000
6000
6000
Time slcts
(c) Training loss of ResNet with respect to time slots. (d) Test accuracy of ResNet with respect time slots.
Figure 6: Comparing convergence time of Local SGD, HL-SGD, and MLL--GD.
and 5 we can see that in all cases except the baseline, the convergence rate is similar in both models. This is in line with our theoretical results, since all cases have the same average worker probability.
Finally, compare the convergence time of MIL-SGD against algorithms that wait for slower workers: Local SGD and HL-SGD. We simulate real-time with time slots. In every time slot, each worker will take a gradient step with a probability p;- Note when p; 1 for worker i, the number of gradient steps taken will match the number of time slots T. Otherwise, the number of gradient steps taken will be T p; in expectation. MLL-SGD will wait time slots before averaging worker models in a sub-network, regardless of the number of gradient steps taken, while Local SGD and HI-SGD will wait for workers to take gradient steps. This approach allows us compare the progress of each algorithm over time. In this experiment, we set p; = 0.9 for 90% of workers and p, = 0.6 for 10% of the workers. As in the previous experiments, we use a multi-level network with fully connected hub network and with 10 hubs, each with 10 workers. We study MLL-SGD with two parameter settings, = 32, q = and = 8, = 4. We also include results for Local-SGD 32, q with Local-SGD, we can evaluate the
and HL-SGD. By comparing MLL-SGD with impact using a local training period based on time rather than a number of worker iterations. By comparing MLL-SGD with 8. q 4 with HL-SGD, can evaluate this impact in a multi-level network.
In Figures 6a and 6c, we plot the training loss, and in Figures 6b and 6d, plot the test accuracy for the CNN and ResNet, respectively. We can see that MLL-SGD with in both loss and accuracy, than Local SGD, and that MLL-SGD with q = 4 converges more quickly than HL-SGD. These trends hold in both the CNN and ResNet models. The results show that in this experimental setup, waiting for slow workers detrimental to the overall convergence time.
converges more quickly,
7 CONCLUSION
We have introduced MLL-SGD, a variation of Distributed SGD in a multi-level network model. Our algorithm incorporates the heterogeneity of worker devices using a stochastic approach. We provide theoretical analysis the algorithm'' convergence, and we show how the convergence error depends on the average worker rate, the hub network topology. and the number of local, sub- network averaging, and hub averaging steps. Finally, we provide experimental results that illustrate the effectiveness of MI.L-SG over Local SGD and HI-SGD. In future work, we plan to analyze the effects of non-III data on convergence error.
ACKNOWLEDGGEETSS
This work is supported by the Rensselaer-IBM AI Research Collaboration (http://airc.rii.edd), part of the IBM AI Horizons Network biz/Aolor,zzosss and by the National Science Foun- dation under grants CNS 1553340 and CNS 1816307.

---

Published as a conference paper at ICLR 2021
REFERENCES
M. Abad, E. Ozfatura, D. Gunduz, and O. Ercetin. Hicrarchical federated learning across heteroge- neous cellular networks. In ICASSP 2020, pp. 8866-8870. IEEE, 2020.
Amari. Backpropagation and stochastic gradient descent method. Neurocomputingg 5(4-5):185- 196, 1993.
1. Bekmezci, O. Sahingoz, and $. Temel. Flying ad-hoc networks (fanets): A survey, Ad Hoc Networks, 113):1254-1270, 2013.
Bonomi, R. Milito, J. Zhu, and S. Addepalli. Fog computing and its role in the internet of things. In Proceedings of the First Edition of the MCC Workshop on Mobile Cloud Computing, 2012.
I.. Bottou, C. Cortes, J. Denker, H. Drucker, I. Guyon, I.. Jackel, Y. LeCun, U. Muller, E. Sackinger, P. Simard, et al. Comparison of classifier methods: a case study in handwritten digit recognition. In Proceedings of the 12th IAPR International Conference on Pattern Recognition, volume 2, pp. 77-82. IEEE, 1994.
I.. Bottou, F. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-3)) 2018.
J. Cipar. Q. Ho, J. Kim, S. Lee, G. Ganger, G. Gibson, K. Keeton, and Xing. Solving the straggler problem with bounded staleness. In 14th Workshop on Hot Topics in Operating Systems, 2013.
G. Cohen, S. Afshar, J. Tapson, and A. van Schaik. Emnist: Extending mnist handwritten letters. In 2017 International Joint Conference on Neural Networks, pp. 2921-2926, 2017.
J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, et al. Large scale distributed deep networks. In Advances in neural information process- ing systems, pp. 1223-1231, 2012.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In CVPR 2016, pp. 770-778, 2016.
Q. Ho, Cipar, H. Cui, S. Lee, J. Kim, P. Gibbons, G. Gibson, G. Ganger, and Xing. More effective distributed ml via a stale synchronous parallel parameter server. In Advances in neural information processing systems, pp. 1223-1231, 2013.
W. Jiang, G. Ye, L. Yang, J. Zhu, Y. Ma, X. Xie, and H. Jin. A novel stochastic gradient descent algorithm based grouping over heterogeneous cluster systems for distributed deep learning. In CCGRID 2019, pp. 391-398. IEEE, 2019.
P. Jin, Q. Yuan, F. landola, and K. Keutzer. How to scale distributed deep learning? arXiv preprint arXiv:1611.04581. 2016.
A. Koloskova, N. Loizou, S. Boreini, M. Jaggi, and S. Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprint arXiv:2003. 10422, 2020.
A. Krizhevsky et al. Learning multiple layers of features from tiny images. 2009.
National Renewable Energy Laboratory. Demonstrating distributed grid-edge control hierarchy.
https:: http://www./rtre nrel www. gov http//cc///////ooooooooocct fy1 Posti//7707 .pff, 2017. Accessed: 2020-07-24.
X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of fedavg on non-iid data. arXiv preprint arXiv:1907.02//11 2019.
X. Lian, W. Zhang, C. Zhang, and J. Liu. Asynchronous decentralized parallel stochastic gradient descent. arXiv preprint
2017.
T. Lin, S. Stich. K. Patel, and M. Jaggi. Don't use large mini-batches local sgd. arXiv preprint arXiv:1808.072111 2018
L. Liu, J. Zhang, S. Song, and K. Letaief. Client-cdge-cloud hierarchical federated learning. In ICC 2020, pp. 1-6. IEEF, 2020.
10

---

Published as a conference paper at ICLR 2021
B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Aguera Arcas. Communication--ffinn learning deep networks from decentralized data. In Proc. of the 20th Intl. Conf. on Artificial Intelligence and Statistics, 2017.
Moritz, Nishihara, I. Stoica, and M. Jordan. Sparknet: Training deep networks in spark. 4th International Conference on Learning Representations, 2016.
T. Rotaru and H. Nägeli. Dynamic load balancing by diffusion in heterogeneous systems. Journal of Parallel and Distributed Computing, 64(4):481-497, 2004.
M. Satyanarayanan. The emergence of edge computing. Computer, 50(1):30-39, 2017.
S. Stich. Local SGD converges fast and communicates little. In International Conference Learn- ing Representations, 2019.
J. Tsitsiklis, D. Bertsekas, and M. Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9):803-812, 1986.
Wang and G. Joshi. Cooperative sgd: unified framework for the design and analysis of communication-efficiii sgd algorithms. arXiv preprint arXiv:1808.07557 070.0777, 2018.
Wang, A. K. Sahu, Z. Yang, G. Joshi, and Kar. Matcha: Speeding up decentralized sgd via matching decomposition sampling. arXiv preprint 1rXiv:1905.09433 2019a.
S. Wang, T. Tuor, T. Salonidis, K. Leung, C. Makaya, T. He, and K. Chan. Adaptive federated learning resource constrained edge computing systems. IEEE Journal on Selected Areas in Communicationns 2019b.
K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835-1855 2016.
J. Zhang, C. De Sa. I. Mitliagkas, and C. Ré. Parallel sgd: When does averaging help? arXiv preprint arXiv:1606.07366 2016.
F. Zhou and G. Cong. A distributed hierarchical sgd algorithm with sparse global reduction. arXiv preprint arXiv:1903.051.. 2019.
M. Zinkevich, M. Weimer, L. Li, and A. Smola. Parallelized stochastic gradient descent. Advances in Neural Information Processing Systems, 2010.
A CODE REPOSITORY
The code used in our experiments can be found at: simulates a multi-level network with heterogeneous workers, and trains a model using MLL-SGD.
This code
B ADDITIONAL EXPERIMENTS
Our experiments in Section 6 explore how changing MIL-SGD parameters affect training on a non- convex function. In this section, show the results of the same experiments on a convex loss function. We train a logistic regression model on the MNIST dataset (Bottou al., 1994). We train binary classification model with half the classes being 0 and the other half being and use step size of 0.2. We run all experiments for 32,000 iterations.
We rerun first experiment from Figure 1 with logistic regression trained on MNIST. Figures 7a and show the training loss and test accuracy, respectively. As with the non-convex functions, we that MLL-SGD with larger q approaches the Distributed SGD baseline.
We rerun our second experiment comparing different hub and worker distributions with logistic regression trained on MNIST. Figure 8 shows the training loss. The three variations of MLL-SGD do not show much difference terms of convergence rate, indicating that Ç has little effect this case. However, they still outperform Local SGD due q being larger.
11

---

Published as a conference paper at ICLR 2021
Distributed
Local SGD x=32
MLL q=0 v=4
0.326
0.86
Distributed SGD
0.374
0.85
MLL-SGD q-4 T-8
q-8
0.322
10000
0.84
10000
20000
(a) Training loss of logistic regression trained
(b) Test accuracy of logistic regression trained MNIST.
MNIST.
Figure 7: Effect of a hierarchy with different values of T and 9.
Distribuied SGD
Probm]
Local SGD Tm32 Hubs-5 Workers=20
Fieed
Uniform Dist
Hubs-10 10 Workers-10
Skewed
Hubs-20 Workers-5
0.327
Skewed
0.326
0.325
0.324
0.323
10000
30000
20000
Figure 8: Effecct of worker distribution on logistic regression trained on MNIST.
Figure 9: Effect of heterogeneous operating rates on logistic regression trained on MNIST.
We rerun our third experiment comparing different worker operating rates distributions with logistic regression trained on MNIST. Figure 9 shows the training loss. As with the non-convex functions, all MLL-SGD variations with the same average probability have similar convergence rate.
We rerun our first experiment from Figure 6 with logistic regression trained on MNIST. Figures 10a and 10b show the training loss and test accuracy, respectively. We can see an improvement in convergence rate of MLL-SGD over both Local SGD and HL-SGD.
C PROOF OF THEOREM
For our proof we adopt similar approach that in Wang & Joshi (2018). This section is structured as follows. We first define some notation and make some observations in Section C.I. Our support- ing lemmas are stated Section C.2. We close with the full proof of Theorem in Section C.3.
C.1 PRELIMINARIES
For simplicity of notation, we let || denote the l vector norm. Let the weighted Frobenius norm of N M matrix X with an N-vector be defined as follows:
X 2 (T((diag(aa) 1/2 x T (diag(a))
a
| 2
(16)
j=1
The matrix operator norm for a square matrix Q is defined as:
| = V Amax Q)
(17)
12

---

20000 Published as a conference paper at ICLR 2021
0.37
MLL-SGD q-1 3m32
local SGD T-3?
0.86-
0.36
MIL-SGD q-4 1-8
HI-SGD q=4
Accuracy
0.84
1095
0.35
0.34
0.02
MLL-SGD q-1 T-32
Local SGD
0.33
0.80
MLL-SGD q-4 T-8
HL-SGD q-4 T-8
0.32
10000
30000
10000
20000
30000
slots
Time
(a) Training loss of logistic regression with
(b) Test accuracy of logistic regression with re- spect to time slots.
spect time slots.
Figure 10: Comparing convergence time of Local SGD and MLL-SGD.
We define the set of Bernoulli random variables θ = {0) [0): where
ON
with probability p. with probability (1 - Pt).
0 0
Let =. (c loss of generality, we assign a mini-batch to each worker, even if it does not execute a gradient step in that iteration. An equivalent definition of gk is then
..... "...,"".''')) be the set of mini-batches used by the N workers at time step k. Without
(
(18)
LE
For simplicity of notation, let E. be equivalent to Ee, Ee We note that Assumption Ic implies:
EA [g (8) = [p (0) )3
(19)
= -P.VF(a("))
(20)
Further, when i * j:
Ex (0)T
gk (1)
= Exp,Exl (0) [x)
(21)
-P.P, V1 (F(
(22)
We also note that Assumption 1d implies:
Ex
g
A
(
E.
61) 9
+
V (T -
-((g 2)
(23)
V= 1| -2E (1) (FF(")
E2
9
+
(24)
112 + VF (0) 12 (2
-,
10(0
(25)
1002
(1)
1| + p: (F /|
2
2p. (1) " (1) (1 -p:) (1-p)) (F(a
2 (26)
Ep,E, (0(2(0) - VF(a (2) ) 1| 2 + (1 - pi) ) ??
(27)
s ppp (F(a(() /2
2
+ + +(1 [FF({
(28)
(p.(3 - 1)) + 1) |F(a ||] + +p.02.
(29)
13

---

Published as a conference paper at ICLR 2021
Finally, we define the weighted average stochastic gradient and the weighted average batch gradient as:
N
N
G%
a:gk
HA
Σ 1=1
C.2 LEMMAS AND PROPOSITIONS
Next, we state our supporting lemmas and propositions.
Proposition The matrices and satisfy the following properties:
1. Z and V each have right eigenvector of with eigenvalue I.
2. Z and each have a left eigenvector of 1 with eigenvalue
3. All other eigenvalues Z and V have magnitude strictly less than 1.
Proof. Assumption indicates that is a Generalized Diffusion Matrix as defined Rotaru & Nägeli (2004).
Recall Assumption 2:
Assumption 2. The matrix H satisfies the following:
2a (i.j) E, then Ha, > O. Otherwise, HJs
2b H is column stochastic, i.e., E Hij
2c For all i,j DD we have b, H b, H
If we show this implies that Z and V are Generalized Diffusion Matrices with the same properties those Assumption 2 with vector a, then the properties in the proposition are satisfied.
Since H and b are non-negative, then Z is also non-negative. It is also clear that Z is column stochastic by construction. left to prove that:
Z,j a; Zj a.
(30)
Applying the definition of Z to the left side, we have:
Zij a Hyy aj
(31)
Since we know that H is a Generalized Diffusion Matrix with vector b, we know that:
H,, H
(32)
b
H H b,
(33)
Plugging this in for Ha()),()), we have:
ba(t) (00)
Zi aj Ha()) ba(o)
aj
(34)
Σ ErEMiano (r)
(i(
w6)
What
Hag)),())
(35)
ErEMROGN w(r)
Erespraion w whot
Whot
(()
Hag)ad() Whot Σ ErEMiGOD wir)
(36)
Haj a; = Zz,0 ai.
(37)
(38)
Therefore, Z is Generalized Diffusion Matrix.
14

---

Published as a conference paper at ICLR 2021
We show that V is also Generalized Diffusion Matrix with the vector a. V is constructed to be non-negative and column stochastic. is left to prove that
Vi. aj = 5,s a,
(39)
When j are outside a block v(d), then Vi, J,ر so the equation is trivially satisfied. When within a block, in terms of w, we have:
1.j aj = V,i a;
(40)
w(t
w(f)
w(
w(()
(41)
EreMC w((r Whot ErEMiOGN w(r) Whot
Noting that we are within a block, therefore d(i) = d(j), we can see that both sides are equal:
w w w00) (1))
(42)
Therefore, V is Generalized Diffusion Matrix.
Proposition 2. Given diffusion matrix H with the properties in Assumption 2. i constructed as follows,
Zi,- (6)
(43)
then the largest eigenvalues of are the eigenvalues of H. and zero otherwise.
Proof. In order to prove the relationship of the eigenvalues of Z and H, we prove the following two points separately:
1. The rank of Z is the same as H.
2. All non-zero eigenvalues of H are eigenvalues of Z. with the same multiplicity.
For the rank of Z, we take look at how each column is constructed. Consider column j of Z:
Z3 = [H ( 1 ..... H (,) (2 ,.... HD.ag)u(())
(44)
For two columns and j where d(i) d(j), these columns are identical. Therefore, the rank of Z. will be, at most, the number of hubs, D. Further, are simply scaled elements of column d(j) in H. So any linearly dependent columns H will also be linearly dependent in Z. Therefore, the rank of the two matrices are the same.
can see that the elements of column j in Z
For the second point, we show there a bijective mapping from eigenpairs of to eigenpairs of Z. Let (X, y) be eigenpair of H (with À + 0), i..
Hy xy.
(45)
Define the N-vector x with components x; = (+) Yd(s)- We will show that Zæ = Ax. Looking at the i-th entry of the vector Z x. have
(Zx), = Σ Za Vj.
(46)
Applying the definition of Z and we obtain
N Σ
(Zx);
H
H ya(s)
(47)
vi)
j=1
H 13)
(R)
(48)
1=1
kEMO
D
H 11
(49)
0
1=1
15

---

Published as a conference paper at ICLR 2021
Note that the m-th entry of the vector Hy equals El= iy Aym- Applying this equality, obtain
(Z.:);; = u(t) Aya())
(50)
(51)
Therefore, for any eigenpair (A. v) of H, we can find an eigenpair (X, x:) of Z. It left to prove that this mapping is bijection.
Suppose eigenvalue À of H has multiplicity k > We consider any two of the & eigenpairs (A, c)
and (A, d). Let the corresponding eigenpairs of Z be (A, e) and (A, f). We know that & f because and d unique, and there must exist index i such that v(()) ca(s) * vl0 dats) Therefore, the
mapping of eigenpairs of H to eigenpairs of Z is a bijection.
L
Proposition Given definition o Z and Proposition the case that
2V VZ Z.
(52)
Proof. First, we prove that VZ = Z. Note that the i-th row of V contains either or zero. Looking
an arbitrary entry i,j of V Z we have:
(V (V 2(() Σ Zr.j
(53)
Ma(e)
(VZ),, = H Ha())
(54)
(VL).. Zi.j.
(55)
Next prove that ZV Z. Note that for any row i in Z. Zii.j
Zi when d(j) d(k).
N
(ZV) = Zio Σ
Vng.
(56)
r=1
Since V is column stochastic:
(Z (ZV) = -Zig
(57)
Proposition Lei A a 1d Given our definition Tu in (6),
A AT: =A
(58)
for all
Proof. We prove each of the three cases of Ty: I, V, and Z. Clearly, IA AI A. It left to prove VA= AV ZA AZ A.
We that ZA A since is right eigenvector of Z with eigenvalue 1: ZA Za Za a 1d = A. Similarly, we that AZ a a a1" A as 1 is left eigenvector of Z. The same holds for V.
Lemma 1. Under Assumptions Ie and 1d, the variance of the weighted averuge stochastic grudient bounded as follows:
a (p.(3 - 1) 11 //F +
Eg 1
H4.1
<
1
alay(1 p,)(1 11011-P)VARA ( (59)
16

---

Published as a conference paper at ICLR 2021
Proof.
N
Ex - Hxll3]= = Ex
Σ
a: (g - vF(x+))
(60)
N
N N
ana {gk²) - (F(0 - vm(a()))
Ex
a 9
VF(xx))11
Σ
(61)
1=1 j+l
N
N N
a E&
9
(1)
F<(x)))
a a (005) ) 11 - vF(2
jy!
(62)
Looking at the cross-terms in (62):
(F(2)))99( ( - VF(a(/))
Ex
9k
Ex [ook )T 9 ] - E& (
- Es VF (1) (1) +
(63)
- -P.VF( - "
(64)
(1-P,) - V ())
(65)
Plugging (65) into (62) we have:
Ex 9 - Hull
a L
[F(x))11
(66)
N
|/ || + -pi02
(pi(3 - 1) + 1)
ΣΣ
ala,(1 p;)(1 (
(67)
FA
where (67) follows from Assumption 1d and (29).
Lemma 2. Under Assumptions Ic and Id, the squared norm of the stochastic gradients is bounded
by:
N
N
Ex | S
a (p:(+11) 1) -p? + +appil
VF(2
(2)) 1|
+ > a
p.o2
(68)
1=1
1=1
Proof.
Ex
[1[92]] [12]
Ep [119 [x]11
||Ex|
(69)
N
Ex
1h Σ a.p.Vr(a0
(2) 12 Σ a.p. V.
(70)
2
Ex
Gk
(F Σ
a.
p.) VF)
a.p.
VF
(71)
17

---

Published as a conference paper at ICLR 2021
Applying the definition of G3 to (71) we get:
Ex
|
|2]
N
N
Ex
a.ga (8) - VVV((a +a,(1 - VP.VF(a
+ Σ
C.P.V (0))
(72)
N
a: - a.VF(a + +a 1-a(11-p.ll) VA. (0)))))) //]
N +
= Ex
Σ V.(a
aaj ( (0 - VF (1) + (1 (1-P;) V=
+ Ex
I= 1,tgs
( vF (1-p))
(73)
Let the cross-terms in (73) be
CR Ex Σ Σ
anaj (19k v)(a())) + +1-- VF)a)
- VF(x +(1 (1 (1-))//(00)
(74)
We can simplify CR as follows:
CR Σ Σ
a.
- -f
-VF('=())
|=1
+ (gk
-L- " -
+ -(= (75)
Ep ( -F(aa))) (9 - -
Σ Σ aga
|=1
+ (
+ +1 - -
+ (1 - (1) V ())
(76)
Applying Assumption 1c to (76), we get:
N
N
CR
Σ
Σ
a.aj
Eg
[0000
() - vF(a
i=1.71
+ (p,
()(1 -
+ (p: 1)(1 - (
+ +(1 (1 " (77)
N
N Σ
Σ
aja;
Ex
[(6
vF(m6))) ( ( - vF
|=1
(1 - VFF (78)
18

---

Published as a conference paper at ICLR 2021
Applying (78) to (73) we have:
aigk (1) a. VF(a)) + (1 - p.) v()aF() )| |
E& [[] E&
Σ
ajaj Ex [(ob"' (F 19 vF(a -f
t- 1,j
N
Σ -.P.))
+
(79)
Expanding the first term in (79) we have:
B3 [[[[x][]]= = FE
Σ
a:9k
(1)
a.
(F
|
+ + a11 -p:)² ()) }|²
N
+
Ex
(aigk a. V.
aill (.)
CRI
N
aiil - p:) VF ). a. a.VF(()))) |1
+
E*
a.g
C12
Σ
E& [00
(i) - (F((a (
vF(a }
0,aj
j=1 1=1,1
(1;)))(11))
(
N
Σ V. (0)
+
(80)
We simplify CRI:
CRI
(81)
Kall: - 1)VF(a (0) (
(82)
=a a, - pi)² (F 1
(83)
Similarly, for CR2
CR2 -2,= pp.) (2)
(84)
19

---

Published as a conference paper at ICLR 2021
Plugging (83) and (84) back into (80):
N a.V /|/ Upp
E& [|| |]]
Ex
Σ
aigk
-aa(l af (0)) [|(a
N
Σ
a.a
Ex [
vF (1) ))² )
(g]
j=1 1=1|
(1 -1)pp)((1 p3)
N +
Σ
a.p. VF (1)
(85)
We can simplify by observing that:
E& [[|9 - -x = Ex
Σ
N
a:9k
(2)
a. VFF((( |1
Σ
Σ
0:aj BB [06)] -FF(a v
(86)
|=
which gives us:
N
[F(2(") (3)) 2 /| + Σ a. a.P.
N
Es || = E& [1G - Ha
ai p1)
i=1
Σ
Σ 01a,(1 pi)(1 - ( (87)
1=1|=1,1
Applying Lemma to (87):
Ex [||9k]
S Σ
a
(Di(3 10(3-) + 1) 1F/
+ +Di02
1=1
N
Eatt ppi)² VF(a )| +
Σ
a.p,
(88)
i=1
N
(pi(B 1) + 1) 1 ||
+ +
a
1=1
N
- af pp:²² ()) 1|
2
+ Σ a.p;
||
(89)
1=1
Σ a (p:(B (B+ p2) + tap
|V((o (1)
11²
+
Σ
a
2.2
(90)
where equation (89) follows from Jensen's 's inequality.
Lemma 3. Under Assumption Ic, the expected inner product of the batch gradient and the weighted average stochastic gradient is equal to:
Eg (VF(())) 2 1
|VF(ux)) +
ai
{?)
p
2
N
Σ
a:
- - (P. () (91)
2
20

---

Published as a conference paper at ICLR 2021
Proof.
Es (VF(us)) = Ex (( (FFlus).. Dash
aakk (i) VPia
(92)
VF((k):
(93)
N
Σ a
(94)
i=1
N
Σ
a
||F
12 + -P [VF(u)) PF
2
t=1
(95)
(V=()))
+
ai
ps
2
N Σ
a: 2 DAV
(96)
where (93) follows from (20), and (95) follows from the fact that, for arbitrary vectors y and 2,
2y²= 2 = =1 + ||=1|2 - lly - =1?
Lemma 4. Under Assumption 1, following the update rule given in (5), if all model parameters are initialized at the same Ii, the expected weighted average gradient is bounded as follows:
2 (F(x1) - Finsl) +O2nLL 2
N
2L
K
E
[VF(u2)1
Σ
+
E
Xx
-
A)
nnK
K
k=
1=1
k=
1 K
N
a: ((4p: - -2) (a:p:(8+11) a.pp p?) E (F || (97)
KL
k=1==1
where A = a.".
Proof. According to Assumption la,
E+ - F(u)) S E& (VF(u))), uk+1 ux) + T
2 1 - us
(98)
(V + 122
E& [11
(99)
2
Plugging in Lemmas 2 and 3, we get:
Eg [F(4++1]] - F(ux)
s 1
VF (F(())) + Σ
a pp |F
Σ
a 2
VF
pp VF (1)
)1
2
+
1 L
Σ
N
(app. (3 1)- -ppp? +.pp
(2)
||
+
L N
Σ
a p: (100)
2
1=1
1=1
N +
a; VF(uu) - v + 0
N
-- V (2=))))
Σe
Σ
a;P:
2
2
2 1=1
i=1
a, (p² nL
+p:)) VF(10 (1)
(101)
2 1=1
21

---

Published as a conference paper at ICLR 2021
After some rearranging, we obtain:
| FF(uu)]] < (F((s) Ex [x(F((x+)))) +o'nL Σ ap + Σ a: - PP:
N
1=1
i=1
ai (p: nL (L.pppp(8+1) + - + +bi)) / |F(
(102)
Taking the total expectation over all iterations:
2 (F((2) - Finfl)
N
E
(F
+ +nnnL Σ
a;p:
K
k
1=1
K N
(Fluu) - V. 11
K N
a. (p: nL (a.p: + 1) -a.p? + +p?)) E (z (1)
)
|
K
(103)
The third term in (103) can be bounded as:
N
a -A
0, - +(1 p.) V=) (3) )12
(104)
Va. (F(a(())12 + 2a 3 ||
(105)
N
2a B|lla
2a - (1)p))) ( 10 Σ 2
(106)
where (105) follows from the fact that [1 212 < 2|/y/ +1|1=112 by Assumption la.
and (106) follows from (105)
Recalling the definition of the weighted Frobenius norm and the definition of u, we can simplify the first term in (106):
2a, L - a 12 = 2 1 __ -Xx 112
(107)
=2L²E X a1 -X 1 F.
(108)
=2L X (1 AA)l
(109)
22

---

Published as a conference paper at ICLR 2021
Plugging (106) and (109) back into (103), we obtain:
2 ( Fins))
E
VF(u)))l
+ Σ ai
nK
2L
K
1
K N
Xx (I Al
+
2a, (1 - p.) V ||
K
K
k=1
ai (p² - 11 (a:p:(3 + 1) - a:pp +x))) E VF k > ||
(110)
K
k= im1
2 (F(
Finfl)
2L K
+ Σ aip: +
Σ
EE Xx A)llA
nnK
K
K
N
0, ((4p: - -2 7n (a:p. +1 a.p. + +Pt)) E VF(a (111)
K
Lemma 5. Given the properties of Z and V given in Propositions and 2, it is the case that:
2 - op =C¹, V olop 1,
|
A Alop op
(112)
where A a1 and Ç = max A2 (H). ((H))-
Proof. According to the definition of the matrix operator norm,
7z' A Allop
Amar (7) - A)7 (7' - -))
(113)
V Amaa (z2) -ZZ - Z A A+
(114)
Aman (722 A)
(115)
where (114) follows from A A, and (115) follows from A Z ZA A. We can simplify (115) further:
Amaz - AA² 21
(116)
Amaz (Z 2
(117)
where (117) follows from the commutability of Z and A.
Based on Proposition 2, the non-zero eigenvalues of are the same as H. As shown in Lemma of Rotaru & Nägeli (2004), for matrix Z with the properties in Proposition the spectral norm of A is equal to Ç.
Therefore:
7 A op 2
(118)
= 5d
(119)
Similarly for V:
I - Allop V Amaz ((V AVT(V- A))
(120)
Amar V AV VA+A)
(121)
Amaae V A)
(122)
(123)
23

---

Published as a conference paper at ICLR 2021
where (121) follows from A A and V V, and (122) follows from V VA=AA =.
Note that the eigenvalues of each block v(d) are A(d) zeros and a one. The set of eigenvalues of will include D ones. If > 1, then based on Lemma of Rotaru & Nägeli (2004) and Proposition I, the spectral norm of V - A is 1,
A op vI |
(124)
=1
(125)
Since the cigenvalues of I are all 1, and I commutable with A, we can similarly say:
Allop 1.
(126)
Lemma 6, Given two matrices C E R NxM and D E RMN, and an N-vector a,
(T(((daa(aa)) CD (diag(a)) s || ll..
(127)
Proof.
We define the i-th row of C as of and the i-th column of D as d, We can rewrite the trace
as:
Tr((dia((a)) 1/2 CD (diag((a)) 1/2
a,
Ci. Djs
(128)
i=1 ==
Σ
a.c de
(129)
1=1
Placing a squared norm around (129), we can apply the Cauchy-Schward inequality:
N
N
N Σ
Σ
c
di
S
Σ
a:ildill?
a:
(130)
1=11
1=1
N
M
N M
ΣΣ
a. Ci,s)
Σ
as
D
(131)
1=1
1=1 1=1
CI.
D E
(132)
Lemma 7, Given two matrices C E R M and D E NNN and an N-vector a, then
|| CC lr S C 1r D llop-
(133)
Proof. We define the i-th row of as cf and the set I = (i [1, M] ||cT| + 0}. We can rewrite the squared Frobenius norm as:
CD l2.. =
Σ lc (diag(a))) 1/2 1|2
(134)
M
lc D (diag (a) 1/2 1/2 |2
(135)
iEI
c| (diag(a)) 1/2 112 ||c D (diag (a)) /22 1?2
Σ
(136)
|eT (diag(a) (a) 1/2 112
M
<
||c] (diag(a)) 1/2 12
(137)
||
D 1
(138)
24

---

Published as a conference paper at ICLR 2021
C.3 PROOF OF THEOREM 1
We recall Theorem 1.
Theorem 1. Under Assumptions 1 and 2, 1f satisfies the the following for all E M:
(4p: - pp - 2 n (3 + -a.p. + p.) + 18
(12)
where r 1-22 - + (1-c)= and Ç max A2 IAN H))), then the expected square norm of the average model gradient, averaged over K iterations, is bounded as follows:
2 (F(x1) Fins))
E
V (u=))
app:
K
nK
1
1)
2
2
1
+
+ (1 - ()2
QT
K
1- (2
1-
2 (2-5)
(
(,219
1)(22
+
(T- (r-1)(27+)) +1)
1T?212002
(1-
(
(13)
6
K-00
o l. Σ
N
aip: +
2
2²
+
2
+ (1 (1-
1- G2
1 1-
1=1
2 (2-5)
(,219
1)
+ 1)
(T-
1) + 1)
4L 112
P
(14)
6
6
where P = Σm a:P:
We now give the proof of Theorem using Lemmas 2-7.
Proof. Using our intermediate result from Lemma 4, we decompose (1 A) using our recursive definition of X5:
(1 - A) = (
(139)
Xp-1(I (1 Gk A)
(140)
- -1-
A]] T 1 G
(141)
[x-2 (I- Tx-2 G (T T -
A)
(142)
(x-- T Ta-2TT1-11- - (T 2 TT-1- - G (T A).
(143)
where (140) follows from the commutability of Tr and A by Proposition 4. Continuing this, end up with:
k-1 G.
K-1
I T A)
k-1
X - -I
(144)
Since all workers initialize their models to the same vector, (1 A) IIK= Tx = and thus we have:
= =1² Σ G,
I T
(145)
F.
Let jgg +1 f, where is the number of hub network averaging rounds, / is the number of nub-network averaging rounds since the last hub network averaging round, and f is the number of local iterations since the last sub-network averaging round. Define:
$
T P
T
25

---

Published as a conference paper at ICLR 2021
Noting that V and VZ = ZV Z by Proposition 3, 22,k-1 can be expressed as:
I
jqT + + < <
jqr + lT +
V
jqT < <s +
+
Z (j 1)qT < S jęT
s
z
(j 2)gr < < S (j 1)qT
(146)
Z 15
For r < j. let
(++1)gr
(n+1]gr
Y,
Σ
G. Q
Σ
VF(),)
#=rg++1
jor+ir We also let ,, 2s=jgr+1
G,, y,,
G., Q,,
jor++r =
VF(X)), and Qj
2eejorthrt1 VF(X.). With this in mind, we can split the sum in (145) into batches for each hub network averaging period:
2r
- A) Yo(Z' A)
(147)
2qr
Σ
G, (Da,k-1 - A) - = 11(2'-1-A)
(148)
#=g++1
jqr
Σ
G2 (2 Yz-1 (2
(149)
8= - 1)r++1
+g++I++f
Σ
(0, = (V +Y,
(150)
Summing this all together, we get:
k-1
j-1
Σ G. ( -)
A)
Σ -) (1 A).
(151)
r=0
Plugging (151) into (145):
X A) 11. = F
- A)+ + (V +)+ 1
(152)
Fa
j-1
E Σ YY, (Z) +)+ (Y,, -V,)(VA))
1-1 + (Y, 12 - (I- - A) + -A) -
2
A)+ (I-A) A)
(153)
7=0
F.
< 2
Σ (Y, OZ) - A) (X,, - OV A) + (Y,, 21 A))
r=0
T
3-1
+ 2E
Q (V A) + Q (I-A)
(154)
==0
Ta
26

---

Published as a conference paper at ICLR 2021
where (154) follows from the fact that |yy + x12 s 2| + 2|121|
We first put a bound on Ti:
2
Ti = 21
Σ(Y, -A) - -)) - (I,) A)
(155)
1=0
Fa
j-1
21/
Σ
B| Q,) A)] + B 22 (6.(V--A)] -A)l
+B - -Q,) -1)))
j-1 ΣΣ E 'r (diag(a)) (Zi---A((Y, O., Q,) A) (diag(a))
+ 2x)² 2
1=0.1y
TR
TRo
+ 41)²
E Tr (diiag(a))
AV))) (V-A))
-Y) (diag(a))
1=0
TRi
+ 4n) 2
E Tr
Oy, (I))
(Z) (ding(a))
1=0
TRa
4ny E
Tr (d A), Q (Y, 52 -Q,, (I)) (I-A) (diag(a)) 1/2)
(156)
TRs
TR can be bounded as:
TR ~ (Z) " A)(Y, Qm) F. ||Y; - (-A))--A))]
(157)
$ (Z) 7 A) Yn - -22l Pa | - QillF. 1| - -A)l
(158)
s 2 2-- -1 I|,, QuIFF | - QillF
(159)
1 2) 20 ||Y 1.1 + I Q [P..]
< 2
(160)
where (157) follows from Lemma 6, (158) follows from Lemma 7, and (159) follows from Lemma 5.
We can similarly bound TR; and RR:
3-1
TR S 2n²²
Σ
3
E Y,, Q +EI 0.12a.]
(161)
1=0
j-1
TR2 S 2n²²
Σ
E
Y 1グ - 11 F. +E 0.1/2.
(162)
1=0
TR3 < 2n²
E
Y,, Q 1 Y 0pall
(163)
27

---

Published as a conference paper at ICLR 2021
Summing TR, through T R23, we get:
TR S 2
2-
E Y, Q...1.. +E ||||Y [E|||,,Q// -Q.laa
1=,,41
+ 2 2
E 51 1. FA
+E Q:1l
i-1
+ 2n)
Σ C
E
Y J/2 2,
1 Fa
+ Y Q:1l
1=0
+ +2 E
Y, 2 + 21 Y وز 2
(164)
j-1
S 2r/²
Σ
2 E Y, Qn F.
n=0 t= 0
j-1
j-1
+ 21
2
Y1 2.1 + +212 2
Σ
' | -ull..
1=0
1=0
+ 2m
5 |,, j -Q Oj
+ 2
5 YY= -Qja
F. (165)
Fa
1=0
1=0
5-1 2n7²
j-1
j-1
" Y, Quli.
Σ
5 + 2
E Y Qull.
1m0,//n
j 1
+ E Y,, Q,,ll²,
E0'+22
12
Esi (166)
Fa
where (165) follows from the symmetry of the n and indices. Plugging (166) back into (156):
Ti S 2m
2 Σ
EII
Q
(Z''--A)ll: -A)l( +21/2 1|(Y, - -1. | - ll
0=0
J-1
j-1
+ 2/ (Y 52 222) F.
||| A + 2n1² 2
Σ
5-=B |,, 1.1
Σ
1=0//$
j
+ + Y,,
11. F. Σ
م + 2 E
Y1 12 F.
Σ
55-
1=0
1
+ 4n
2
- ' Y Quil
(167)
1=0
< 2nj² 2 Σ
E EI( - Q.)1 20- 21 (Y v
j-1
+ 2n7
[Y jز 1 022,1 F. + 2nn 2
Σ
S- Y, - 11
Σ مi-2
n=0
1=0,
+ E Y,, - -2, Fa
Σ
اا + 27
Y1a 2E PE
1 r.
1=0
1=0
+ 4n² 2
5 E Y:
111
(168)
l=0
28

---

Published as a conference paper at ICLR 2021
where (167) follows from Lemma 7, and (168) follows from Lemma 5.
We further bound Ti:
5-1
2 Ti S 2m
B I( - -Q))le (26-1) + B (X - 0,,)
7=
21 (| j2 2/2) 211² Σ
E Y Qu.lis C
0
+ 2 Y, 0
+ 2B E
Y 1/
- Fa 1 1-5
1|2
1 5-
j-1
+ 4n
2
J E Y - -i
(169)
1=0
j-1
(2(5-1)+((5 - 55-rt1) 1- E |Y,,,, Q.)11
21)² 2
((1--) +
+ 2n72
(1-5) ( E V Q Il..
+ 227 (2
(1-5)
IF Y 8,
(170)
where (169) follows from the summation formulae of a power series:
ΣS''
1
Σ J c-
1 Σ S Σ
j-1
5- < 5
(171)
1-(
1=0
1=0
(m-00
Taking a closer look
[YY, S.X,-Qy Q,) for Srrkjt j:j:
(r+1)gr
E [Y, - -Q,)
=E
Σ
(G. -FF()(
(172)
s=
Fo
N
(x+1)gr
a
Σ
( - VF(x
(173)
1=1
#=rg++1
N
(r+1)gr
(9% - vF(a 2
a:qr
Σ
E
(174)
smrgr+1
N
(x+1)gr
N
< QT
Σ
a
Σ 10(3-1)+11)
+ 7 00
a.P:
1=1
+=
1=1
(175)
N
(m+1)er
qr
Σ a
Σ
-)
1)
\E(o!))
+ 7 P. (176)
s=rgT+1
where (175) follows from Assumption 1d and (29). Similarly, for r j1 and r
f2:
N
E EI 1 F. Sl
Σ a
Σ
(p:(8 1) + 1) |
+12200P (177)
$=j+++1
N
f- f-1 Σ
E B|I(Y,, 1, F. (f
Σ
(p.(8 1) + 1) VF VF(
1=1
+ (f - 1
(178)
29

---

Published as a conference paper at ICLR 2021
Plugging (176), (177), and (178) into (170), we can bound 7i as follows:
(26-1) + +25--+ + +-1-5)
(--5) (1722 + (s (8(2+11-11)) ((1-119) P
Ti S 20
r=
5-1
(t-tt (1+1)gr N
+ 217 qT
Σ
(21)-T) + +2 + 1-
Σ
Σ
a (p: - 1) + 1) |F( |
r=0
+ im1
+ +2n/
(2=5) lT
Σ
N
juu+lr
(p:
(p: - 1) + 1) FF \F(a
a
1=1
+=j
N
Jqr++++--1
+ 2n/
2 S 1-
(s 1)
Σ
Σ
(pi(3 + 1) 1) (/
(179)
Referring back to Lemma 4, our goal is sum Ti over k I,..,, K iterations. First, we sum over the j-th sub- network update period up to the j-th hub network averaging, for 1 = .,.... . 1 and .....,. T:
+ ()-
Th S 21 2000020 3
Σ
(2(0-)) + +2
1 1 P
/=
(2-5) (1-()
7 (2 + +1)
T(T - 1)(2T + 1) +1) P
+2n20²
+
6
6
1-1
(r+ (++1)gr N
+ +20
(()-T)) + +2(5-
Σ
Σ a: (p. - 1) 10)0
1-
r=
s=
1=1
+ 2
2 - 5
9(a 1)7² 2
Σ
N
a Σ
Har++1)
(p:(3 - 1) + 1) [F( | |
1 (
i=1
8=
+ 1² (2-5)
(
(T((T - 1)
Σ
N
a
j(g
Σ
(p - + +1) [
(180)
-=1
#=)(g
Let:
(--rt)) r,= ((U)))) + + + 1-
(181)
Note that 1 3-26
2-6 I-
Using this inequality, we can bound the sum of the last three terms of
I-c
(180) to get 72 Z/ Ppi
2-1
r
1-1
55-rt1 P
Σ
Ti S 217202
Σ
+ +20 (2
1- (
/=1
0=
2 (2-6)
7. 3g9 - 1)(2g 11
T(T - 1)(TT + 1) P
+2100²²
T-
6
+ q
(r+1)gr N
+ +222 7
T
Σ
Σ
a: (p.
( 1) /
(182)
r=0
-=
30

---

Published as a conference paper at ICLR 2021
Summing (182) over the hub network averaging periods j = ......, -O...,K((9FT) - 1, we obtain:
k/(g)--10 1--1 r
k/(g))-1,5
( + +250 + 5--rt1
S
2
Σ 1=0
P
1 1-
1=
/=1
P=0
2--
2
2 (g - () + 1)
(T - 1) (T- + +11 P
+ +2 K
1-
k/(ar)-1
(n+1)ar N
+ +21/
Σ1,
rr
Σ
Σ
a. (p:(3 1) + 1) E v 1
(183)
1=
P=0
s=rg++1 t=1
K/(gr)-2 - K1
(2())) + 25/ :ン-r+t P
= 22
Σ
Σ
1-5
r=0
jer+l
2 (2-5)
)
(
72 1)( +1)
(T (T- + 1)
O
6
K1
K/(gr)-1
(r+1)gr N srggr+ii=l
q2
Σ r2
Σ
Σ
a. (p: 1) 1) |F(a!")
j=r
(184)
Applying the following summation formula to sum over J, we obtain
k/(gr)-1
00
+2 5r-+11
Σ
(225-))
(00-))+2(" +20-++
Σ
(()-T)
(185)
1 1-
1-c
1=
|=
1
2 + C
+
(186)
1 - c²
1 1-5
(1 ()-
We let r =
+
I-6
2 + (1-().-
We can also apply this following summation formula to the first
term in (184):
K/(gT)-1
(f-r+1 1-(
20
55-+t1 (200-))+255 +
Σ
20-r) + 25- +
Σ
+ +55
(187)
1-
j=++1
j=rt1
2
2 + 1
< 1-
+
(188)
1- (1 (1-c)² 2)
Applying the summation formula in (188), plugging I' in, and indexing the iterations in terms of k. we bound (184) as:
K Σ Ti < 2222 3
K -1)
(1)
(
22
2
+ (1- 5)2 )
1 1-
+
qT
1-
1=1
2
7 22(9-1)(24+)
1)(2q + 1)
(T-
1-(2) + 1) P
+ 2 2
+
1
6
6
K N
(8) 2
+ 2
(p:(3 - 1) + 1)
VF
(189)
k=1 2=
31

---

Published as a conference paper at ICLR 2021
Now bound T2:
i-1
T2 = 21
Σ
-A)+ (V- ()- 2₁ (I (--A) -A)
(190)
j-1
2nj 2
Σ
E
(Z'-~~
+2y2E Q4. (V- -A)ll F. + 2 11 (1 A)
+ 21 2
Σ
E
Tr (diag(a)) 1/2 (7/- A) QT Q, A) (diag(a))
1=0,=0
TR
TR,
+ 4n/ 2
Tr (diag(a)) 1/2 A) Q, A) (diag(a)))
TR
E
Tr (diag(a)) (I- A) Q% QZ (diag(a))
1=0
TR
+ 2 Tr (( (V) Q Qj A) (diag(a)))/)) (191)
TR4
TR' can be bounded as:
TR < (Z' A) A
1Q' -A)ll Pb
(-)--i-A/ll
(192)
Fa
|| -A)l op
Qm.llr 11Qilla 1Z/-1- A
(193)
$ 1 26 110.111.. + +1011
(194)
2
where (192) follows from Lemma 6. We can similarly bound TR2 through TR3:
J-1
TR < 2n² 2
Σ 5
E B 11:. + E EE P.
(195)
1=0
j-1
TR; < 27²"
5
Q jz
2 F.
+ E Q
2 Fa
(196)
1=0
TR; < 27
+ 2m
21 E 1 2
(197)
F.
32

---

Published as a conference paper at ICLR 2021
Summing TR2 through T T we get:
3
Σ TR S qt
Σ
Σ
E 1l.. - E |E 2 F.
t=0
n=0 10,1y
j-1
+ 2x)²
E QQ1
+21 Σ
5 EE 1 Pa
1=0
1=0
+ 21/
2
R
+ 21)
5- |0 F.
(198)
Fa
1=0
1=0
1-1 Σ
j-1
S 211² 2
5 55-" E
Σ
+ 411
E
Qu1i
a
|=0,1/
1=0
j
2n
0 1l.
Σ
+ 27 E
Q22
2
Σ
(199)
Fa
1=0
where (199) follows from the symmetry of the indices n and I.
Plugging (199) back into (191):
j-1
Te S 2ny²
E
Q (Z
(r A)1 F. + +21 Q3 (V -)]l" + +2 1 (I A)]1
j-1
j-1
j-1
+ 2n/
Σ
5 "E
" ||
Q
2 FA
Σ 1=0,6n
اا + 477
Σ
SE 111 F..
n=0
1=0
+ 21
Q3 1|
Σ
55
+ 27
j/ Fo Σ
ل (200)
1=0
1=0
1-1
< 2n²²
Σ r=0
E ||Q P. -t)---A)]l: + 2 E 1
|
A
+
II- A 1
F.
op
j2 F.
j-1
j-1
j-1
+ 2n²² 2
Σ
"
" ||
1
1 F.
Σ
55 4n/
Si 1
n=
1=0,155
1=0
+ 2272 1 1 F. Σ
122
1| F. 1=0
c (201)
1=0
j-1
< 2n²
Σ 0=0
F. + 1/
2
|0₂,
2 F.
2 Q0 I.
f-1
2n²
Σ
5 E E Q.ll
Σ
ا + 4n²
Σ
J | 2
n=
1=0,14m
1=0
+
21
| |
Σ
5
2 E
1
2
Σ
s-t (202)
Fa
F.
1=
I=0
where (201) follows from Lemma 7, and (202) follows from Lemma 5.
33

---

Published as a conference paper at ICLR 2021
We further bound T2:
7-1
T2 S 2m
E 1
+ +2
Q 11 + +21n'E
1z l1
r=0
j-1
5
+ 2nj 2
Σ
2 E
E Qm Pa
+ 41²
c E Q
1- c
==
1=0
+ +
||
Q ll
+
21
Q2
2
1
(203)
1 5
1-5
< 2m
(2) + +20² -25-++
+ 1-
E 11Q
+ 277²
2 (2-5)
E
l..
+ 2n²
2
E
(204)
1/2
where (203) follows from the summation formulae of power series in (171).
After applying the definition of Q to (203), we obtain:
j-1 Σ
+ 5d-rt1
Or
T- = 2n²²
+ +200 (20-))
E
FF(
X
Xrerts)
1
1-
r=
Fa
2
2n²²
2
E
Σ
V X jnr+s)
221
2 C
Σ VF
(205)
C-C)
(
Fg
Fg
$ 27 qr
Σ
(26)))) + 25-
+
5d-r+1
E V X + I|
1 1-6
r=0
1=1
(2 (2-
+ 27 1T
Σ V 111+
(
+ 2 - 1)
2
Σ E VF (X
(206)
where (206) follows from (205) by Jensen's 's incquality.
Summing over all iterates in the j-th sub-network update period, we obtain:
T2 T S 2T
Σ
j-1
(
(2()-))+ + -- + 1-
55
gr
E V (X rg )=) 112
+ 12'9(q -1) (2-6)
9r
(-- Σ
V X f
(2-
+ n"99(( - 1)
(207)
1-
qr
< 21j
q
E V X
(208)
Summing over all iterations and applying the summation bound in (186) to (208):
k/(m))-q-1
K
To <
2
VVF(X))
(209)
1=0 1=1
34

---

Published as a conference paper at ICLR 2021
Summing T1 and T2, we obtain
2L
Σ
k
E
2L K
Σ T1 +
2L K
Σ T2
(210)
K
K
K
k=1
k=1
k=1
1
5²
2
1
44
22
17
K
1 1-
1 1-
+
(1 - 4)
P
(2-5)
(2299 - 1) + 1)
(T- (2T +11 P
+
(-
K
81. 9/
1
ΣΣ
a4 (p: - (1-11) 1)
( |?
(211)
K
Plugging T1 and T3 back into Lemma 4, we arrive at
(F(xi) - Fins))
N + + >
2L K
2L K
(1))
a
Ti +
K Σ T2
n
K
K N
EF F }|²
12
ai ((4p: - -;;- - -2 (T.p(((+++)) a + p²))
a.p.
(212)
K
k=
(F((1) - Fenyl)
N
+ +O¹nL Σ
aip:
i=1
2
2
1-
1 1-( (1- (1-{)) 5)2
97
+ +4L37700² 22 (2-5)
(,299-1)29
1) + 1) (T-
12( + 11) p
+
6
K N
- a.p; pp:) - 8133) E VF (0)) |²
a, ((4p: -p; - 2) - nn (a:p: + 1)-
K k=
(213)
If 17 satisfies the following for i = N, (4p; p 2) 2 nL (8 a,p; + +p:) + 88
+1
(214)
then we can simplify (213):
K
2 (F((a)) Finsl)
E
V vl
<
+ Σ a:p:
K
n7
i=1
+ 17
0 7
23
1
1
2
2ç
1
QT
K)
1 1-
1-6 Ç
(1 C)2
2
(-2
(g(g
12 + 1)
+ (T- 1) 1)
22
P. (215)
6
C.4 COMPARISON TO COOPERATIVE SGD
We note that when setting a, I/N and p; = 1 for all workers i, and setting q 1, MLL-SGD reduces to Cooperative SGD (Wang& & Joshi, 2018). However, the bound in Theorem 1 differs when compared to the bound of Cooperative SGD. Specifically, Theorem I has error terms dependent on ?2 as opposed to T.
This is due to the formulation of g
(8) Namely:
EA 9 (6)
= p. F. (1r (2))
(216)
-P (1)
(217)
35

---

Published as a conference paper at ICLR 2021
Because cannot assume p; there cross terms in the expressions in equations (156) and (173) that do not cancel out. Thus, we needed to use a more conservative amalysis at these steps the proof. This is the reason that plugging in a value of p; 1 is not enough recover the same bound as in Cooperative SGD. similar discrepancy can be observed when comparing with Koloskova al. (2020).
36


Reviews:
[{"review_id": "i7VPprTwIh", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper extends (Wang & Joshi, 2018) and proposes MLL-SGD for training models in hierarchic networks, where the network consists multiple sub-networks, and each sub-network contains multiple workers. In the level of sub-networks, models can be averaged. In the level of workers, the local copies of models can be averaged within a sub-network; however, workers cannot communicate directly with those from a different sub-networks. In such setting, MLL-SGD is proved to enjoy certain convergence property.\n\n\n# Pros\nHierarchic networks are a common object in practice, but current SGD algorithms fail to cover it due to the hierarchic communication restrictions. Though MLL-SGD itself is a quite naïve extension of existing local SGD methods for handling hierarchic networks, the convergence theory is not a trivial work. I think this paper can serve as a ground work for developing more efficient algorithms for training models in hierarchic networks.\n\n\n# Cons\n- Theorem 1 only considers constant step size and shows a (at least) constant upper bound for MLL-SGD. A theorem that involves decreasing step size and a upper bound that decreasing to zero can be more favorable.\n\n- Eq. (2) and (3). Though here the authors claim they take a probabilistic approach, but actually they treat $tau^(i)$ as constants, where they should be random variables. Can you explain what would be a counterpart of Theorem 1 if $tau^(i)$ are random variables?\n\n- The proof mainly follows (Wang & Joshi, 2018) and the technical contribution is limited. With that being said, I appreciate the formal theory for MLL-SGD in the setting of hierarchic networks.\n\n- Weak experiments. It can be great if there are some experiments that involve training models in real hierarchic networks.\n\n\nIn sum, I think this work is OK but not very significant. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hOZLVglJbmT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper extends the idea of hierarchical local SGD by extending the top hierarchy level to decentralized communication. The multi-level local SGD is achieved by the edge devices (performing all-reduce per \\tau local edge steps in terms of the corresponding hub) and hubs (gossip averaging per q local hub steps with the neighboring hubs).\n\n### pros\n* the paper considers a probabilistic form of the local edge update, making the whole system formulation more realistic.\n* A convergence analysis is given for the provided system formulation.\n\n### cons\n1. the formulated problem can be seen as a decentralized optimization problem with specifically designed time-varying communication topology and local edge update steps. It is better to compare the derived rate with the existing rate (e.g. in [1]) for the case of $p_i=1$, otherwise, it is unclear the tightness of the derived rate.\n2. the claim 'if the gradient of F has a large Lipschitz constant, the step size in the algorithm is large' looks strange to me; normally we have stepsize <= 1/L.\n3. the motivation example of the system is formed by edges devices and data-center hubs. however, in both theoretical analysis and numerical results, only the iid data case is been investigated. It somehow contrasts motivation.\n4. the numerical evaluation setup might be unfair. \n    1. the evaluated decentralized communication over the hubs is unclear to me and why it is a manually generated graph with $\\zeta=0.74$.\n    2. only the learning curves w.r.t. update step k are visualized. due to the extra gossip averaging steps over hubs, the current observations (i.e. improved convergence speed over local SGD) are reasonable but it is hard to identify the exact benefits of the proposed algorithm. is it possible to use a communication model to simulate some important metrics, e.g. time-to-target-loss? is it possible to include the numerical results of hierarchical local SGD e.g. in Lin et al (i.e. All-reduce is performed for hubs) as an extra baseline?\n5. The provided numerical results are limited to the toy problems and may not be sufficient to justify the effectiveness of the proposed algorithm, due to the existing large amount of local SGD work (either empirical or theoretical).\n\n### reference\n1. A Unified Theory of Decentralized SGD with Changing Topology and Local Updates, ICML 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "h2kaDsr4b0y", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposed a multi level SGD algorithm, where workers are assigned to different groups, and each group averages local workers' model. \n\nThe idea is a natural extension on existing SGD algorithms (and should be beneficial in heterogeneous networks). The proof should not be hard based on existing asynchronous/decentralized SGD proof. My concern about this paper is that it seems to me the algorithm has a similar motivation with grouping SGD:\n\nW. Jiang et al., \"A Novel Stochastic Gradient Descent Algorithm Based on Grouping over Heterogeneous Cluster Systems for Distributed Deep Learning,\" 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), Larnaca, Cyprus, 2019, pp. 391-398, doi: 10.1109/CCGRID.2019.00053.\n\nwhich is a straightforward extension of AllReduce SGD. I suggesting also comparing with it in the experiments. My first thought is that this paper should be faster than grouping-SGD when the network between hubs is not good (and that benefit comes from the fact that communication between hubs in this paper is decentralized).\n\nThe hub in this paper does not seem necessary to me also, since it is used to average all local workers' model. Why not just do an AllReduce on all local workers and have one of the worker responsible for averaging with other groups? That should be easier to implement and more efficient.", "extra_scores": {}, "extra_text": {}}, {"review_id": "SGTfo51KHWE", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis paper proposes a new variant of local SGD algorithm to make it be more realistic. In particular, (1) it allows workers to perform different number of local steps, depending on their computational resources; (2) workers are organized in a multi-level structure. Workers connected to one central hub can synchronize frequently and hubs are communicated in an infrequent and decentralized manor.\n\nThe authors provide convergence analysis under non-convex, iid data partition settings, and conduct preliminary experiments to validate their theoretical findings.\n\n## Pros\n1. This paper is easy to follow and very well-written.\n2. It makes a non-trivial extension of (Wang & Joshi, 2018). By introducing probability of taking local updates, the framework allows different workers to take different local steps within a given time interval. This is a realistic setting typically ignored by related literature.\n3. The analysis of the proposed algorithm is not trivial. It is nice to see how the authors model the complex algorithm in a simple way, although the formulation is roughly the same as (Wang & Joshi 2018).\n\n## Cons\n1. It seems that the results of MTL-SGD cannot recover local SGD? In particular, the additional error terms (the last two terms in (13)) increase with $q^2 \\tau^2$. However, in local SGD, the additional error terms increases linearly with $\\tau$, as shown in (Wang & Joshi, 2018). I didn't find any discussions on this discrepancy.\n2. The experimental results are too limited. Especially, it is hard to see the advantages of MTL-SGD over other two baselines. I encourage the authors to redefine the x-axis in experiments to time slots. Within one time slot, each worker has a probability $p_i$ to perform one local step. In local SGD, in order to finish one round of $\\tau$ local updates, the time slots required for one worker is $\\tau/p_i$, and hence, the time slots used for one round is $\\max_i \\tau/p_i$. However, in MTL-SGD, the time slots used per round can be exactly $\\tau$ by allowing workers to have different number of local steps. By doing this, MTL-SGD might have much faster convergence than local SGD, in terms of loss versus time slots.\n\n## Post-rebuttal\nI've read the authors' response and other reviewers' comments. The response and the updated version clarify my concerns. So I slightly increase my score.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies a hierarchical or multi-level version of local SGD, extending earlier work by (Wang & Joshi, 2018), (Lin et al, 2018) and  (Jiang et al. 2019) among others. It gives novel convergence rates in relevant settings, such as by allowing different workers to take different numbers of local steps within a given time interval. The current analysis is restricted to the IID data case, but still insightful, and might serve as a useful building block for follow-up research in the future.
Smaller concerns remained that the presented multi-level results cannot exactly recover local SGD as a special case. Nevertheless the consensus remained that the overall contributions and relevance of the paper remain above the bar. In the discussion phase, several concerns were clarified and additional deep learning experiments have been added to the paper, which is appreciated.
Decision: Accept (Poster)