PopSGD: Decentralized Stochastic Gradient Descent in the Population Model
Authors: Giorgi Nadiradze
Amirmojtaba Sabour
Aditya Sharma
Ilia Markov
Vitaly Aksenov
Dan Alistarh.
Venue:  (2020)
Keywords: Distributed machine learning
distributed optimization
decentralized parallel SGD
population protocols

Abstract: The population model is a standard way to represent large-scale decentralized
distributed systems, in which agents with limited computational power interact
in randomly chosen pairs, in order to collectively solve global computational
tasks. In contrast with synchronous gossip models, nodes are anonymous, lack a
common notion of time, and have no control over their scheduling. In this paper,
we examine whether large-scale distributed optimization can be performed in this
extremely restrictive setting. 

We introduce and analyze a natural decentralized variant of stochastic gradient
descent (SGD), called PopSGD, in which every node maintains a local parameter,
and is able to compute stochastic gradients with respect to this parameter. 
Every pair-wise node interaction performs a stochastic gradient step at each
agent, followed by averaging of the two models. We prove that, under standard
assumptions, SGD can converge even in this extremely loose, decentralized
setting, for both convex and non-convex objectives.  Moreover, surprisingly, in
the former case, the algorithm can achieve linear speedup in the number of nodes
n. Our analysis leverages a new technical connection between decentralized SGD
and randomized load balancing, which enables us to tightly bound the
concentration of node parameters. We validate our analysis through experiments,
showing that PopSGD can achieve convergence and speedup for large-scale
distributed learning tasks in a supercomputing environment.

Under review as a conference paper at ICLR 2020
POPSGD: DECENTRALIZED STOCHASTIC GRADIENT DESCENT IN THE POPULATION MODEL
ABSTRACT
The population model is a standard way to represent large-scale decentralized distributed systems, in which agents with limited computational power interact in randomly chosen pairs, in order to collectively solve global computational tasks. contrast with synchronous gossip models, nodes anonymous, lack common notion of time, and have no control over their scheduling. In this paper, we examine whether large-scale distributed optimization can be performed in this extremely restrictive setting.
We introduce and analyze natural decentralized variant of stochastic gradient descent (SGD), called PopSGD, in which every node maintains a local parameter, and is able compute stochastic gradients with respect to this parameter. Every pair-wise node interaction performs a stochastic gradient step at each agent, fol- lowed by averaging of the two models. We prove that, under standard assumptions, SGD can converge even in this extremely loose, decentralized setting, for both convex and non-convex objectives. Moreover, surprisingly, in the former case, the algorithm can achieve linear speedup in the number of nodes n. Our analysis leverages new technical connection between decentralized SGD and randomized load-balancing, which enables us to tightly bound the concentration of node pa- rameters. We validate our analysis through experiments, showing that PopSGD can achieve convergence and speedup for large-scale distributed learning tasks in a supercomputing environment.
INTRODUCTION
Distributed machine learning has become commonplace, and it is not unusual to encounter systems which distribute model training among tens or even hundreds of nodes. In this paper, we take this trend to the extreme, and ask: would it be possible to distribute basic optimization procedures such as stochastic gradient descent (SGD) to thousands of agents? How could the dynamics implemented in such large-scale setting, and what would be with the resulting convergence and speedup behavior?
To get some intuition, let us consider the classical data-parallel distribution strategy for SGD Bottou (2010). We in the classical empirical risk minimization setting, where we have a set of samples S from a distribution, and wish to minimize the function f IRd + R. which is the average of losses over samples from S by finding nodes which can process samples in parallel. Data mata-parallel SGD consists of parallel iterations, in which each node computes the gradient for one sample, followed by a gradient exchange. Globally, this leads to the iteration:
argmin E.es (z)/15) Assume that we have 1 compute
P
Ft-1 = It Tr Σ (x.))
where n, is the learning rate, Fe is the value of the global parameter, initially 0%, and (1x) is the stochastic gradient with respect to the parameter obtained by node i at time t.
When extending this strategy to high node counts, two major bottlenecks are communication and synchronization. In particular, to maintain a consistent view of the parameter I;, the nodes would need broadcast and receive all gradients, end of every iteration. Recently, tremendous amount of work has been dedicated to address these two barriers. In particular, there has been significant progress on communication--eddee
would need to synchronize with all other nodes, the
variants of SGD (e.g. (Seide et al./ (2014) Strom (2015): Alistarh et al. (2017)); Wen et al. (201 7); Aji and Heafield Dryden et al. (2016); Grubic et al. (2018) )) asynchronous variants (e.g. g. Recht et al. (2011); Sa et al. (205);; Duchi al. (211)); Alistarh et al. (2018b)), well as large-batch or periodic model averaging methods, which aim to reduce the frequency of communication Goyal et al.
(2017) You et al. (2017) and Chen and Huo (2016); Stich (018)), ), even decentralized synchronous

---

Under review as a conference paper at ICLR 2020
variants(e.g, Lian et al. (2017a); : Tang al. (2018); Koloskova et al. (2019)). Using such techniques. it is possible to scale SGD to hundreds of nodes, even for complex objectives such as the training of deep neural networks. However, in systems with node counts in the thousands larger, some of the communication and synchronization requirements of these algorithms become infeasible.
In this paper, we consider the classic population model of distributed computing [Angluin et al. (2006), defined as follows. We are given a population of n compute agents, each with its own input, which cooperate to perform some globally meaningful computation with respect to their inputs. Interactions occur pairwise, where the two interaction partners randomly chosen in every step. Thus, algorithms are specified in terms of the agents' state transitions upon an interaction. The basic unit of time is single pairwise interaction between two nodes, whereas global (parallel) time is measured as the total number of interactions divided by n, the number of nodes. Parallel time corresponds intuitively to the average number of interactions per node to reach convergence. Population protocols have a rich history in distributed computing (e.g. (e.g. AAglluin et al. (2006) 2007] 2008a b c): Alistarh al. (2017a 20T8a)), and are standard in modelling distributed systems with millions or billions of nodes, such as Chemical Reaction Networks (CRNs) Bower and Bolouri (2004); Chen al. 2017) and synthetic DNA strand displacement cascades Chen et (2013). The key difference between population protocols and the synchronous gossip models (e.g. Xiao and Boyd (2004); [Lian et al. (2017a): Koloskova et al. (2019) previously used to analyze decentralized SGD that nodes are not synchronized: since interactions occur randomly at arbitrary times, there are no global rounds, and nodes lack a common notion of time.
While the population model is theoretical construct, we show that it can be efficiently mapped to large-scale super-computing scenarios, with large numbers of compute nodes connected by a fast point-to-point interconnect, where we can avoid the high costs of global synchronization.
An immediate instantiation of SGD in the population model would be to initially assign one sample 8 from the distribution to each node i, and have each node maintain its own parameter estimate xf. Whenever two nodes interact, they exchange samples, and each performs gradient update with respect to the other's 's sample. If we assume interaction pairs are uniform random (with replacement), each node would obtain stochastic gradient upon each interaction, and therefore each model would converge locally. However, this instance would not have any parallel speedup, since the SGD instances each node essentially independent.
In this context, a natural change to the above procedure is to have nodes and first perform gradient step, and then also average their resulting models upon every interaction. Effectively, node i interacts with node j, node i's updated model becomes
+ x 1j"
9 (x')
+ (x*)
x²
(1.1)
2
2
where is the interaction partner, and the stochastic gradients 9e and g are taken with respect to each other's samples. The update for node j is symmetric. In this paper, we analyze a variant of the above protocol, which call PopSGD, in the population protocol model.
We show that, perhaps surprisingly, this simple decentralized SGD averaging dynamic provides strong convergence guarantees for both convex and non-convex objectives. First, we prove that, under standard convexity and smoothness assumptions, PopSGD has convergence speedup that linear in the number of nodes n. Second, we show that, if the objective non-conver but satisfies the Polyak-Lojasiewice (PL) assumption, PopSGD can still ensure linear convergence in the number of nodes. Third, we show a @(yn) speedup in the non-convex case in the absence of this assumption, matching slightly improving results from previous work which considered similar models (Lian et al. 2017b).
On the practical side, we provide convergence and speedup results using an efficient implementation of PopSGD using Pytorch/MPI applied to regression tasks, but also to the standard CIFAR/ImageNV classification tasks for deployments on a multi-GPU nodes, and on the Piz Daint supercomputer (Piz). Experiments confirm the scalability of PopSGD. We also observe an improvement in convergence versus number of SGD iterations per model at higher node counts, in both convex and non-convex settings. In particular, using PopSGD, (2016) models to full accuracy using only 1/8 the number of SGD updates per model, compared to the sequential baseline, resulting in fast convergence with nearly linear scalability.
are able to train the ResNet18 and ResNet50 He et al.)
2

---

Under review as a conference paper at ICLR 2020
This suggests that, even though interactions occur only pairwise, uniformly at random, and in an uncoordinated manner, as long as the convergence time is large enough to amortize the information propagation, the protocol enjoys the full parallel speedup of mini-batch SGD with batch size proportional to the number of nodes. While similar speedup behaviour has been observed in various synchronous models for the convex case- e.g. Stich (2018); Koloskova al. (2019), or for complex accelerated algorithms Hendrikx et al. (2118) we are the first to show that SGD does not require the existence of globally synchronized rounds or global communication.
Central to our analytic approach is new technical connection between averaging decentralized SGD and the line of research studying load-balancing processes in computer science (c.g. |Azar et al. (1999); ; Mitzenmacher (2000); "Tllwar and Wieder (2007); Peres et al. (2015)); [Boyd et al. (2006)). Intuitively, we show PopSGD can be viewed as a composition between a set of instances of SGD each corresponding to one of the local parameters x' z'whh are loosely coupled via pairwise averaging, whose role is to "balance" the models by keeping them well concentrated around their mean, despite the random nature of the pairwise interactions. Our analysis characterizes this concentration, showing that, in essence. the averaging process propagates enough information to globally "simulate" SGD with a batch of size ((n), even though communication is only performed pairwise. We emphasize that the convexity of the objective function in isolation would not be sufficient to prove this fact: simply averaging n independent SGD models at the end of training would not lead to speedup in the objective (please see e.g. |Stich (2018) for a detailed discussion). Along the way, we overcome non-trivial technical difficulties, such as the lack of a common notion of time among nodes, or the fact that, due to the structure of SGD, this novel load-balancing process exhibits non-trivial correlations within the same round.
Related Work. The study of decentralized optimization algorithms dates back to Tsitsiklis (1984). and is related to the study of gossip algorithms for information dissemination Kempe et al. (2003); Xiao and Boyd (2004); [Boyd et al. (2006). Gossip is usually studied in one of two models Boyd et al. (2006): synchronous, structured in global rounds, where each node interacts with a randomly chosen neighbor, and asynchronous, where each node wakes up at times given by a local Poisson clock, and picks a random neighbor to interact with. The population model is functionally equivalent to the asynchronous gossip model, since the interaction times in the latter model can be "discretized" to lead to pairwise uniform interactions. The key difference between our work and averaging in the gossip model, e.g. Boyd et al. (2006), is that their input model is static (node inputs are fixed, and node estimates must converge to the true mean), whereas we study the a dynamic setting, where the models are updated in each round by SGD, and should remain concentrated around the parameter mean as it converges towards the optimum. Several optimization algorithms have been analyzed in this setting Nedic and Ozdaglar (2009); Johansson et al. (2009); /hamir and Srebro (2014). (Tang et al. 20:8); Koloskova et al. (2019) analyze quantization in the synchronous gossip model.
Lian et al. b)) Assran et al. (2018) consider SGD-type algorithms in the gossip model. Specifically, they analyze the same SGD averaging dynamic in the non-convex setting. Table 2 in the appendix summarizes their assumptions, results, and rates. Their results are phrased in the synchronous gossip model, in which nodes interact in sequence of perfect matchings, for which they provide ((I/VTn) convergence rates (under analytical assumptions). Further, they extend their results to a variant of the gossip model where updates can be performed based on stale information.
Upon careful examination, we find that their results can be extended to the population proto- col/asynchronous gossip model, although at the cost of slower convergence relative to the synchronous case. For et al. (2017b), the convergence rate bound requires that the total number of iterations is 2(2)), while in case only O(n²) iterations are needed. The difference comes from the fact that our bound on the potential I is tighter. For Assran et al.] (2018), speedup with respect to the number of nodes depends on the parameter C. Which in turn, depends on the dimension of the objective function, number iterations for the graph given by edge sets of all matrices used in averaging to be connected and the diameter of aforementioned graph. Unfortunately, in the population model parameter C' will not be a constant and this will eliminate the speedup. Further, these references present scalability results for training neural networks using both synchronous and asynchronous variants of their algorithms, thereby slightly relaxing their analytic assumptions.
Relative to this prior work, our contributions are as follows. First, we consider both convex and non-convex objectives. We the first to show linear speedup in the objective for convex objectives in this decentralized asynchronous model. Our bounds in the non-convex case match or slightly improve those presented above, under similar assumptions. Furthermore, under the PL condition,
3

---

Under review as a conference paper at ICLR 2020
are the first to show linear convergence speedup in the non-convex case. Our analysis technique relies on a fine-gr ane-grained analysis of individual interactions, which is different than that of previous work. From the implementation perspective, the performance of our algorithm is competitive with that of previous methods, notably DA-PSGI Lian et al. (2017b) and SGP Assran et al. (2018).
Other instances in the literature which consider dynamic interaction models are Nedic et al. Nedic et al. (2017), who present a gradient tracking algorithm in a different dynamic graph model, and Hendrickx et al. |Hendrikx et al. (2018), who achieve exponential convergence rates in a gossip model where transmissions are synchronized across edges. The algorithm they consider is more complex instance of accelerated coordinate descent, and is therefore quite different from the simple dynamics consider. Neither reference considers large-scall deployments for non-convex objectives.
2 PRELIMINARIES
The Population Protocol Model. We consider a variant of the population protocol model which consists of a set of 2 2 anonymous agents, or nodes, each executing a local state machine. (Our analysis will make use of node identifiers only for exposition purposes.) Since our application is continuous optimization, we will assume that the agents' states may store real numbers. The exccution proceeds in discrete steps, where in each step a new pair of agents is selected uniformly at random interact from the set of all possible pairs. (To preserve symmetry of the protocols, will assume that a process may interact with a copy of itself, with low probability.) Each of the two chosen agents updates its state according to a state update function, specified by the algorithm. The basic unit of time is a single pairwise interaction between two nodes. Notice however that in a real system (n) of these interactions could occur in parallel. Thus, standard global measure is parallel time, defined as the total number of interactions divided by n. the number of nodes. Parallel time intuitively corresponds to the average number of interactions per node to convergence.
Stochastic Optimization. We assume that the agents wish to minimize a d-dimensional, differen- tiable and strongly convex function ʃ Rd IR with parameter l >>> 0, that is:
(I (x- y) (VF (2) f (v)) 2 f| Vx, VIl. R..
(2.1)
Specifically, we will assume the empirical risk minimization setting, in which agents are given access set of data samples S .si...., Sm } coming from some underlying distribution D, to function fi : Rdd + F which encodes the loss of the argument at the sample st. The goal of the agents is to converge on model x= which minimizes the empirical loss, that is
x argming (x) argmin, , (1/m) Σ fi(x).
(2.2)
In this paper, we assume that the agents employ these samples to decentralized variant of SGD, described in detail in the next section. For this, we will assume that agents have access to stochastic gradients ğ of the function f, which are functions such that [[] V fx). Stochastic gradients can be computed by each agent by sampling i.i.d. the distribution D, and computing the gradient of at 0 with respect that sample. In the population model, we could implement this by procedure either by allowing agents to sample in each step, or by assigning a sample 8; to each agent i, and having agents compute gradients of their local models with respect to each others' samples. We will assume the following about the gradients:
Smooth Gradients: The gradient (((x) is L-Lipschitz continuous for some L > 0, i.e. for all r, y E Rd.
[Vf(z) - f s -|x-~/l - y|l-
(2.3)
Bounded Variance: The variance of the stochastic gradients is bounded by some x² > 0, i.e. for all x E Rdd:
E (z) - - 0².
(2.4)
Bounded Second Moment: The second moment of the stochastic gradients is bounded by some M > 0, f.e. for all x E IR::
E (x) 12 < 2
(2.5)
4

---

Under review as a conference paper at ICLR 2020
3 THE POPULATION SGD ALGORITHM
Algorithm Description. We now describe a decentralized variant of SGD, designed to be executed by a population of n. nodes, interacting in uniform random pairs as per the population protocol model. We assume that each node has access to local stochastic gradients g', and maintains a model estimate X', well as a local learning rate 1j'. For simplicity,
will assume that this initial estimate is 0f at each agent, although its value may be arbitrary. We detail the way in which the learning rates updated below. Specifically, upon every interaction, the interacting agents and perform the following steps:
and j are chosen uni uniforlly at random, with replacement upon each interaction between agents and each agent performs local SCD step
--x'-117 - -''''('((XX))
agents average their estimates coordinate-wise
ang (X* X2)
X aug
X - avg
Algorithm 1: Population SGD pseudocode for each interaction between arbitrary nodes and j.
We are interested in the convergence of local models: x','" ."...""" after T interactions occur in total. For the theoretical reasons, in the case when f is convex, we derive convergence for yr which weighted average of average values of local models per step(See Theorem 4.T. In the beginning of section 5 we show that by performing single global averaging step at time step 0 < t < T, which carefully chosen from specified distribution, we can make sure that in expectation local models converge with the same rate as y/r.
Estimating Time and the Learning Rate. In parallel with the above algorithm, each agent maintains a local time value V*, which is estimated using a local "phase clock" protocol. These local times are defined and updated as follows. The initial value at each agent is V = O. Upon each interaction, the interacting agents i and j exchange their time values. The agent with lower time value, say V V will increment its value by 1(ties are broken arbitrarily). The other agent keeps its local value unchanged. (We break ties arbitrarily.) Although intuitively simple, the above procedure provides strong probabilistic guarantees on how far individual values may stray from the mean: with high probability all the estimates V are in the interval [t/n clog T, l/n + log T). where is constant.
Given the current value of V at the agent, the value of the learning rate at is simply 1/² b/(nV +a). where a and are constant parameters which we will fix later. This will ensure that the gap between two agents' learning rates will be in the interval [0.5, 2}. w.h.p. (See Lemma 4.2
4 THE CONVERGENCE OF POPSGD IN THE CONVEX CASE
This section is dedicated to proving that the following result holds with high probability:
Theorem 4.1. Let f be an L-smooth, E-strongly convex function satisfying conditions (2.3) (2.5), whose minimum x² we are trying find via the PopSGD procedure given in Algorithm 7 Let the learning rate for process at local time t = nV; be ni = b/(t' + a), where a max(2en log T, 18n, 256L/E) and
An/l l are fixed(for some constant c). Let the sequence of weights we be given by wa = (a+ t)2. Define μt = Ei= X ST = Σt- w; 2 $T and yr ST ET= WeHt. Then. for any time T, we have with probability
0(1 poly T)) that
a36
64T(T + 2a) 0² 9216Tn2
B[f(rr) f(x))] 2ST I|Ho ---1=-1 x=1
M
(4.1)
CST
S
Discussion. We first emphasize that, in the above bound, the time T refers the number of interactions (as opposed to parallel time). With this in mind, we focus on the bound the case where T' > n, and the parameters M, L, and are assumed to be well-behaved. In this case, since ST 2 2 /3, the first and third terms are vanishing as T grows, and we get that convergence is
An event holds with high probability (w.h.p) if it occurs with probahility 2 1 - 1/T", for constant > 0 and the total number of interactions- T.
5

---

Under review as a conference paper at ICLR 2020
dominated by the second term, which can be bounded as O /T). It tempting to think that this is roughly the same rate as sequential SGD; however, our notion of time is different, as we are counting the total number of SGD steps executed in total at all the models. (In fact, the total number of SGD steps up to 7 is 2T', since each interaction performs two SGD steps.)
It interesting to interpret this from the perspective of an arbitrary local model. For this, notice that the parallel time corresponding to the number of total interactions T, which is by definition T = T/n, corresponds (up to constants) to the average number of interactions and SGD steps performed by each node up time T. Thus, for any single model, convergence with respect to its number of performed SGD steps Tp would be O /nTT))])) which would correspond to running SGD with batch size of n. Notice that this reduction in convergence time is solely thanks to the averaging step: in the absence of averaging, each local model would converge independently at a rate of O /Tp). We note that our discussion assumes batch size of 1, but it would generalize to arbitrary batch size b, replacing o² with o²/ /b. We note that, due to the concentration properties of the averaging process, the claim above can be extended to show convergence behavior for arbitrary individual models (instead of the average of models pr).
Proof Overview. The argument, given in full in the Additional Material, can be split into two steps. The first step aims to bound the variance of the local models X; at each time and node i with respect to the mean μ4 = Σ; X supermartingale-iie behavior, which enables us to bound its expected value as Onin). This shows that the variance of the parameters is always bounded with respect to the number of nodes, but also, importantly, that it can be controlled via the learning rate. The key technical step here Lemma 4.3 which provides careful bound for the evolution of the potential at a step. by modelling SGD as a dynamic load balancing process: each interaction corresponds to a weight generation step (in which gradients generated) and load balancing step, in which the "loads" of the two nodes (corresponding to their model values) are balanced through averaging.
n.. It views this quantity as a potential Hs, which we show has
In the second step of the proof, we first bound the rate at which the mean μr converges towards x*, where we crucially (and carefully) leverage the variance bound obtained above. This is our second key technical lemma. Next, with this in hand, we can apply a standard argument to characterize the rate at which the quantity (yf( - f(x") converges towards O.
Notation and Preliminaries. In this section, we overview the analysis of the PopSGD protocol. We begin with some notation. Recall that is the number of nodes. We will analyze sequence of time steps 1= = 1,2,.... ... T, each corresponding to an individual interaction between two nodes, which are
usually denoted by i and j. Recall the definition of parallel time Tp T/n, where T counts the number of pairwise interactions. For any time t, define by 1)t = b/ [a + t) the "true" learning rate at time t, where a and b are constants to be fixed later, such that 2 2en log n for some constant c. We denote by x² the optimum of the function f.
Learning Rate Estimates. Our first technical result characterizes the gap between the "global" learning rate л = ba(a + t) (in terms of the true time t), and the individual learning rates at an arbitrary agent i at the same time, denoted by ni.
Lemma 4.2. Let Tp. = b/(a )V be the learning rate estimate of agent i time step t, in terms of its time estimate Vi. Then, there exists constant >> such that, with probability at least 1 1/77 (Here, T is a total number of steps our algorithms takes), the following holds for every T 2 1 0 and agent i:
1
111 2.
(4.2)
2 m/
Step 1: Parameter Concentration. Next, let X, be vector of model estimates at time step t, that
is X, (X), (2,,X?,..,, X?") Also, let f4: - Xj, be average estimate time step L. The following potential function measures the concentration of the models around the average:
r =
Σ | - 11.
With this in place, one of our key technical results is to provide a supermartingall-type bound on the evolution of the potential Dr, in terms of M, Mts and the number of nodes

---

Under review as a conference paper at ICLR 2020
Lemma 4.3. For any time step t and fixed learning rate Nr used at t, have the bound
B - (1- 4n, M
1/2
+ 8
71
Next, we unroll this recurrence to upper bound Fe in expectation for any time step t, by choosing an appropriate series of non-constant learning rates.
Lemma 4.4. If 2 18n, then the potential is bounded follows
B[T,] S 36nb² /(L +a) M = 36mm M
Step 2: Convergence of the Mean and Risk Bound. The above result allows us characterize how well the individual parameters are concentrated around their mean, in terms of the second moment of the gradients, the number of nodes, and the learning rate. In turn, this will allow to provide a recurrence for how fast the parameter average is moving towards the optimum, in terms of the variance and second-moment bounds of the gradients:
Lemma 4.5. For A) I 61L' we have that
E M++1 - x* ||=
T/E
El|m - x-1
Th - 2n
-
16 288 M
n²
n
Finally, we wish to phrase this bound as a recurrence which will allow us to bound the expected risk of the weighted sum average. We aim to use the following standard result (see e.g. Stich (2018) ): Lemma 4.6. Let {a:)120 az 0, fea)22, e be sequences satisfying
las a a a
a1+1
for at E[tta]
A> 0, B, C 2 0, 8 > then
A
la
2T + +a)
16T
wiet <
00
B
C,
(4.3)
ST
4ST
eST
S2
1=0
for wi = (a t) and ST = Lt=0 2 1T.
To use the above lemma, we set T)t n0
4n and the parameter b 4n/l. We also
z(e-af
use A = 1/2, B = 1602, and C = 288M 2 Ln 2 Let yr nST Σn 2 w. W.Y Also, let &, = B[f( - f(x")] and a, E 11 - x²
Using convexity and Lemma 4.6 above we obtain the following final bound:
1=2 64T + 2a) 0² 9216Tn2
Elf(yr fxx)]]
2
(4.4)
28T
ES
S2S
To complete the proof of the Theorem, we only need to find the appropriate value the parameter For that, we list all the constraints
2 2cn log T, 2 18n and F(r+aj
4n
S 647. These
inequalities can be satisfied by setting a = max (2on log T, 18n, 25 This concludes our proof.
EXTENSIONS
Convergence of local models and alternative to computing yr. Notice that Theorem 4.1 measures
T- we Σn X; ET- we Sy He, is a weighted average of Me-S per step. Notice that actually computing yr can be expensive, since we need values of local models over T steps and it does not necessarily guarantee convergence of each individual model. In order to circumvent this issue, we can look the following inequality, which combination with the Jensen's 's inequality gives us the proof of Theorem 4.1 (Please see Appendix for details):
convergence of fyr), where yr -TT-1
ST
a²
x1 64T (T + 2a) 0²
9216Tn
w.E[f(m))) f(x*)]
M (5.1)
ST t=0
2ST
SST
(2ST
What we can do is, instead of computing yr, we just sample time step <tsT with probability and compute f(e) = f( n Xi/n), by using single global averaging procedure. Observe that E, [F,,( is exactly the left hand side of the above inequality.
7

---

Under review as a conference paper at ICLR 2020
Hence, get the convergence identical to the one in Theorem 4.1 and additionally, since using global averaging, we also guarantee the same convergence for each local model. Finally, we would like to emphasize that in practice there is no need to compute yr to global averaging, since local models are already converged after T interactions.
General Interaction Graphs. Our analysis can be extended to general interaction graphs by tying the evolution of the potential in this case. In the following, we present the results for a cycle, leaving the exact derivations for more general classes of expander graphs for the full version. In particular, we assume that each agent is node on cycle, and that it is allowed to interact only with its neighbouring nodes. Again, the scheduler chooses interaction edges uniformly at random. In this setting, we can show the following result, which is similar to Theorem 4.1
Theorem 5.1. Let f be an L-smooth, E-strongly convex finction satisfying conditions (2.3)-2255) whose minimum x² we are trying to find via the PopSGD procedure on a cycle. Let the learning rate for process at local time t' = nV, be ni = b/t'++a) where a = max(2cn log T, 18n, 256L/ and b = An/E are fixed(for some constant c). Let the sequence of weights wi given by Wt (a + 1)2. WeHs. Then, for any time T,
Define lr = > X;, ST = Et=o We 2 $ and = =, IT-1
we have with probability 1 O(1/ poly T) that
a
64 + 2a) 11 - +1
2
Elf(yr) - f(x")( = 2ST
0²
2
SST
ST
Notice that for T >> n." the second term dominates convergence and we repeat the same argument as for Theorem 4.1 to show O(o2/T) convergence (where T is the total number of interactions). Next provide the sketch of proof for the PopSGD on cycle case. See section ?? in the appendix for the proof sketch.
The Non-Convex Case. Next, we show convergence for non-convex, but smooth functions. The Following theorem deals with the bounded gradient case:
Theorem 5.2.
Let f be an non con-coneex, L-smooth, function satisfying assumption 2.5 whose minimum we are trying find via the PopSGD procedure given in Algorithm Let the learning rate use be n/ VT. Then, for any T F21 n²:
T-1 BIV]((u)) (f(mo) [(x))) Σ
36LM2
2LM
VT
VT
VT
Next, we show the similar result for the case when gradient is not bounded, but it's variance is. This can be achieved by carefully following steps given in the Lian et al. (20175).
Theorem 5.3. Let f be an non-comvex, L-smooth, function satisfying condition 2.4 whose minimum xx we are trying to find via the PopSGD procedure given in Algorithm Let the learning rate we use be 1j = n/VT. Then, for any T 2 4624 ( 1nn,, we have
T-1 1 EIS(M)I T
B[S(Ho)) - [=[((=))
402
32T.02
768I20²
Σ
VT
VT
Observe that, since T is the total number of interactions and equal to nTp, where Tp is a parallel time, in both theorems, we get convergence O(L/vT) O(1/ /T,m). Which gives us 1/ Vn speedup over O(I/VT) convergence of the sequential version. (Note that in the sequential parallel time and the total number of interactions are the same.)
Finally, we derive convergence for the case where gradient bounded and function we are trying to optimize satisfies the Polyak-Lojasiewiin (PL) assumption with constant More formally, function satisfies the PL assumption with constant a if:
E E a(f(pz) - f(x))).
(5.2)
We use a similar approach to Haddadpour et al. (2019) but, our tighter analysis of I potential allows us to remove global synchronization.
Theorem 5.4. Let f be an non-comve,, L-smooth, function satisfying assumption 2.5 and PL- assumption with constant 5.2..) 5.2). whose minimum x. we are trying to find via the PopSGD procedure
8

---

Under review as a conference paper at ICLR 2020
given in Algorithm
I
Let the learning rate time step t be n a(taa) learning rates at time Then 2 2cn log I and time T, with probability 1 - (1/ poly T) we
T; are vi
An
a(T'+0)
have
a²
4.08L.
64LM²
B[f(uT)] f(x')
(a + T)s -
a (T+ a)3
a² + (T
Observe that as in Theorem 4.1 this gives us a linear speedup over the sequential version.
6 EXPERIMENTAL RESULTS
In this section, we validate our results numerically by implementing PopSGD in Pytorch, using MPI for inter-node communication MPI We are interested in the convergence behavior of the algorithm, and in the scalability with respect to the number of nodes. Our study is split into simulated increases andasess-ndddd large-
experiments for convex objectives- to examine the validity of our analysis scale real-world experiments for non-convex objectives (training neural networks), aimed to examine whether PopSGD can provide scalability and convergence for such objectives.
Convex Objectives. To validate our analysis in the convex case, we evaluated the performance of PopSGD on three datasets: (1) real-world linear regression problem (the Year Prediction dataset Chang and Lin (2011)) with a 463, 715/51. 630 test/train split, and d = 90; (2) a real- world classification problem (gisette Chang and Lin (201 ) with 6, 000/1, 000 test/train split, and d = 5000; (3) a synthetic least-squares problem of the form 2.2 with f(z) 111Azz bll², where A E IR mxd and b E R"", with m = 10 and variable d. As a baseline, we employ vanilla SGD with manual learning rate tuning. The learning rate adjusted in terms of the number of local steps each node has taken, similar to our analysis.
PopSCD Year Prediction batch 25ze=256
PooSGD batch size=128
05
Hppors-1 100
rppuss-1 1000
300
0.4
135
134
0.5
133-
132
131
PepI --4000
---000---1000
130
10
15
20
10
Epachs
Epochs
(a) PopSGD test loss vs. n on Year Prediction.
(b) PoDSGD test loss vs. n on Gisette.
Figure 1: PopSGD convergence (test loss at the step versus parallel time) for various node counts real linear regression (left) and logistic regression (right) datasets. The baseline is sequential SGD, which is identical to PopSGD with node count 1.
Our first set of experiments examines train and test loss for PopSGD on the real-world tasks specified above. We examine the test loss behavior with respect to the number of nodes n, and execute for powers of 10 between 1 and 10000. Each node obtains a stochastic gradient by sampling 128 elements from the training set in a batch. We tuned the learning rate parameter for each instance independently, through line search, and obtained learning rates in the interval [0.0005, 0.015] for Gisette, and [0.05, 0.2) for Year Prediction.
Please see Figure I(b) for the results. (The number of epochs is cropped to maintain visibility, but the trends are maintained in general.) The results confirm our analysis; notice in particular the clear separation between instances for different n, which follows exactly the increase in the number of nodes, although the X axis values correspond to the same number of gradient steps for the local model. In Appendix B we present additional experiments which precisely examine the reduction in variance versus the number of nodes on the synthetic regression task, confirming our analysis.
Training Neural Networks. Our second set of experiments tests PopSGD on the CSCS Piz Daint supercomputer, which is composed of Cray XC50 nodes, each with a Xeon E5-2690v3 CPU and an NVIDIA Tesla P100 GPU, using state-of-the-art Aries interconnect. For this, we implemented

---

Under review as a conference paper at ICLR 2020
PopSGD in Pytorch using MPI one-sided primitives MPI models for averaging without explicit synchronization. We used PopSGD to train ResNets on the classic CIFAR-10 and ImageNet datasets.
which allow nodes to read eachothers'
Training proceeds in epochs, each of which is structured as follows. At the beginning of each epoch, we shuffle the dataset and partition it among processes. Notice that, in data-pane Sata-parallel SGD, an epoch ends after each process iterates exactly once over its partition, i.e. each sample is seen once. However, Theorem J.J.s.ggesssttt that, for PopSGD, processes should iterate several times over their partitions, for the corresponding gradient information to be propagated. To match this, introduce multiplier constant mult, which counts the number times each process will iterate through its partition before an epoch is complete. At the same time, scale down the total number of epochs executed by n, the number of nodes. In practical terms, if sequential SGD trains ResNet50 in 90 epochs, decreasing the learning rate at 30 and 60 epochs, then PopSGD with 32 nodes and multiplier 4 would use 90 * 4/32 = 12 epochs per node, decreasing the learning rate at 4 and 8 epochs.
Since PopSGD scales almost linearly terms of time per epoch (see Figure middle), this should ensure end-to-end speedup for PopSGD. In particular, for ResNet50, we obtain a 2x end-to-end time-to-convergence speedup versus data-parallel SGD. Figure 2 shows the test and train accuracies for the ResNet18 model trained the ImageNet dataset, with 32 Piz Daint nodes and mult 4, as well as scalability versus number of nodes. The hyperparameters used for model training are identical to the standard sequential recipe (batch size 128 per node), with the number of epochs scaled down to 12 per node.
Test accuracy
Scalability graph
T-222 3-
Stepe
SATTDR NAVEETS
06-508 Re
Figure 2: PopSGD test accuracy using 32 nodes on Piz Daint, measured at fixed arbitrary node. The X axis measures SGD steps per model, whereas the Y axis measures Top-1 accuracy. The dotted red line is accuracy the Torchvision baseline. PopSGD surpasses the test accuracy of baseline by 0.34%, although processes each sample 4x less times, and each model sees 8x less gradient updates. The third graph shows the average runtime per batch for PopSGD (center) versus DA-PSGD (Lian et al. 2017b) and SGP [Assran al. 2018 the same setup.
The results suggest that PopSGD indeed preserve convergence, while being scalable and competitive with state-of-the-art algorithms. Appendix B presents additional experiments for ResNee50//magene and ResNer20/CIFAR-D which further substantiate this claim.
7 DISCUSSION AND FUTURE WORK
We have analyzed the convergence of decentralized SGD in the population model of distributed computing. We have shown that SGD is able to still converge in this restrictive setting, and moreover, under parameter and objective assumptions, can even achieve linear speedup in the number of agents in terms of parallel time. The empirical results confirmed our analytical findings. The main surprising result is that PopSGD presents speedup behavior roughly similar to mini-batch SGD, even though node only sees one gradient update and single model time. Our work opens several avenues for extensions. One natural direction is to study PopSGD with quantized communication, or allowing the interactions present inconsistent (stale) model views to the two agents. Another avenue is to tighten the bounds in terms of their dependence on the problem conditioning, and on the objective assumptions.
REFERENCES
Mpich: high performance and widely portable implementation of the message passing interface (mpi) standard. http: //www mpichhorge Accessed: 2018-1-25.
10

---

Under review as a conference paper at ICLR 2020
The CSCS Piz Daint supercomputerr http::/ww..ccc.cc////cooooo cessed: 2018-1-25
_diintt Ac-
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. arXiv preprint (ate::700.000000 2017.
Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L Rivest. Time-space trade-offs in population protocols. Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 2560-2579, 2017a.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Randomized quantization for communictionn-ffiiieni stochastic gradient descent. In Proceedings of NIPS 2017, 2017b.
Dan Alistarh, James Aspnes, and Rati Gelashvili. Space-optimal majority in population protocols. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 2221- 2239, 2018a.
Dan Alistarh, Christopher De Sa, and Nikola Konstantinov. The convergence of stochastic gradient descent asynchronous shared memory. In PODC, pages 169-178, 2018b.
Dana Angluin, James Aspnes, Zoë Diamadi, Michael Fischer, and René Peralta. Computation in networks passively mobile finite-state sensors. Distributed computing, 18(4):235-253, 2006.
Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-300 304, 2007.
Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority. Distributed Computing, 21 (222)877-00 2008a.
Dana Angluin, James Aspnes, and David Eisenstat. Fast computation by population protocols with a leader. Distributed Computing, 21(3):883-199 2008b.
Dana Angluin, James Aspnes, Michael J Fischer, and Hong Jiang. Self-stabilizing population protocols. ACM Transactions on Autonomous and Adaptive Systems, 3(4):13:1-13:28, 2008c.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Michael Rabbat. Stochastic gradient push for distributed deep learning. arXiv preprint arXiv: /8/1. 1079. 2018
Yossi Azar, Andrei 7. Broder, Anna R Karlin, and Eli Upfal. Balanced allocations. SIAM Journal Computing, 29(1):180-200) 1999.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of 20MPSTAT' pages 177-186. Springer, 2010.
James M Bower and Hamid Bolouri. Computational modeling of genetic and biochemicul networks. MIT press, 2004.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE/ACM Trans. Netw,, 14(S)):2508 2530, June 2006. ISSN 1063-6692, doi: 10.1109/TIT.200 874516.
http://ooooogogooooo/oo 1109/TIT. 2006 874516
Chih-Chung Chang and Chih-Jen Lin. Libsym: A library for support vector machines. ACM Trans.
Intell. Syst. Technol., 2(3):27:122::77, May 2011. ISSN 2157-6904. doi: 10.1149/196118, 1961199, URL /RL acm. org. 11w.:.111111111111111
Ho-Lin Chen, Rachel Cummings, David Doty, and David Soloveichik. Speed faults in computation by chemical reaction networks. Distributed Computing, 30(5):373-390, 2017.
Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering. In 2016 ieee international conference on acoustics, speech and signal processing (icassp), pages -880-5884. IEEE, 2016.
11

---

Under review as a conference paper at ICLR 2020
Yuan-Jyue Chen, Neil Dalchau, Niranjan Srnivas, Andrew Phillips, Luca Cardelli, David Soloveichik, and Georg Seelig. Programmable chemical controllers made from dna. Nature Nanotechnology, (10):755-76,, 2013.
Nikoli Dryden, Sam Ade Jacobs, Tim Moon, and Brian Van Essen. Communication quantization for data-parallel training of deep neural networks. In Proceedings of the Workshop on Machine Learning High Performance Computing Environments, pages 1-8. IEEE Press, 2016.
John C Duchi, Sorathan Chaturapruek, and Christopher Ré. Asynchronous stochastic convex optimization. arXiv preprint arXiv: 00880, 2015.
Priya Goyal, Piotr Dollár, Ross Girshick. Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv: Stdi::/706.02677. 2017.
Demjan Grubic, Leo Tam, Dan Alistarh, and Ce Zhang. Synchronous multi-gpu deep learning with low-precision communication: An experimental study. In EDBT, 2018.
Farzin Haddadpour. Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck R. Cadambe. Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization. arXiv e-prints, art. arXiv:1910. 13598, Oct 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
Hadrien Hendrikx, Laurent Massoulié, and Francis Bach. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. arXiv preprint arXiv: 180000260, 2018.
Bjöm Johansson, Maben Rabi, and Mikael Johansson. randomized incremental subgradient method for distributed optimization in networked systems. SIAM Journal on Optimization, 20(3): 1157-1170, 2009.
David Kempe, Alin Dobra, and Johannes Gehrke. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pages 482-491. IEEE, 2003.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. arXiv preprint arXiv: 2019.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jio Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallcl stochastic gradient descent. arXiv preprint (05.:170500056,, 2017a.
Xiangru Lian, Wei Zhang, Ce Zhang, and Liu. Asynchronous decentralized parallel stochastic gradient descent. arXiv preprint arXiv: 171000671 2017b.
Sébastien Marcel and Yann Rodriguez. Torchvision the machine-vision package of torch. In Proceedings of the 18th ACM international conference on Multimedia, pages 1485-1488. ACM, 2010.
Michael Mitzenmacher. How useful old information? IEEE Transactions on Parallel and Distributed Systems, 1 11(1):6-0,, 2000.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48, 2009.
Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time- varying graphs. SIAM Journal Optimization, 27(4):257-2233, 2017.
Yuval Peres, Kunal Talwar, and Udi Wieder. Graphical balanced allocations and the one plus beta- choice process. Random Struct. Algorithms, 47(4):760-775, 2015a. doi: 10.1008//..20555. URL
https://doi. .org/10 1002./ rsa. 20558
12

---

Under review as a conference paper at ICLR 2020
Yuval Peres, Kunal Talwar, and Udi Wieder. Graphical balanced allocations and the + beta-choice
process. Random Struct. Algorithms, 47(4):760-775, -75, December 2015b. ISSN 1042-9832. doi: 10.1002/tsa.25558 utLhttp:
dx doi wwt.0ooog/0..... wttp:///..........1.0 20558
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild: A lock-free approach to parallelizing stochastic gradient descent. In NIPS, pages 693-701, 2011.
C. M. De Sa, C. Zhang, K. Olukotun, and C. Re. Taming the wild: A unified analysis of hogwild-style algorihms. In Advances Neural Information Processing Systems, 2015.
Seide, H. Fu, L. G. Jasha, and D. Yu. 1-bit stochastic gradient descent and application to data- parallel distributed training of speech dnns. Interspeech, 2014.
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 850- 857. IEEE, 2014.
Sebastian Stich. Local sgd converges fast and communicates little. arXiv preprint arXiv: 2018.
Nikko Strom. Scalable distributed dnn training using commodity gpu cloud computing. In Sixteenth Annual Conference of the International Speech Communication Association, 2015.
Kunal Talwar and Udi Wieder. Balanced allocations: the weighted case. In David S. Johnson and Uriel Feige, editors, Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, Califormia, USA, June 11-13, 2007, pages 256-265. ACM, 2007. ISBN 978-1-59593-6311 doi: (0.1144/12507900125555
URL https: doi or..org//////.. /1/. 114./ 12501255799 1050022
Hanlin Tang, Ce Zhang, Shaoduo Gan, Tong Zhang, and Ji Liu. Decentralization meets quantization. CoRR, abs//803. 0044336643,....0 2018.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Wei Wen, Cong Xu, Feng Yan. Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terggrdd: Ternary gradients reduce communication distributed deep learning. Advances in Neural Information Processing Systems, pages 1508-1518, 2017.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1)665-7, 2004.
Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size to 32k for imagenet training. arXiv preprint arXiv: 1708.000..000 038888 2017.
13

---

Under review as a conference paper at ICLR 2020
A SUMMARY AND COMPARISON OF RESULTS
In this section compare convergence rates of existing algorithms, while specifying the bounds they require for convergence. In the tables 7 rccorresponds to the parallel time and n is number of processes. We use the following notations for needed bounds:
1. o² bound on the variance of gradient.
2. M bound on the second moment of gradient.
3. PL
assumption.
4. d bounded dimension.
5. p bounded spectral gap of the averaging matrix.
6. T bounded message delay.
Global synchronization
Assumptions
Convergance Rate
PopSGD
NO
02 M 0² M
0(1/T))
Local SGD
YES
O(/TT))
Table I: convex case
Global synchronization
Assumptions
Convergance
Rate
PopSGD
NO
0 M
0(1v
PopSGD
NO
0² M PT.
0(1/Tn)
PopSGD
NO
0²
0(1/TTn)
LUPA-SGD
YES
0², M PL
O(1TTn)
AD-SGD
NO
0² P, o²,d,T
0(1/TT
SGP
NO
0(1/TT
Table non-convex case
B ADDITIONAL EXPERIMENTS
Convex Losses. these experiments, we examine the convergence of PopSGD versus parallel time for different node counts, and compared it with the sequential baseline. More precisely, for PopSGD, we execute the protocol by simulating the entire sequence of interactions sequentially, and track evolution of train and test loss at arbitrary fixed model of with respect to the number of SGD steps it performs. Notice that this is practically equivalent to tracking with respect to parallel time. this case, the theory suggests that loss convergence and variance should both improve when increasing the number of nodes. Figure (aa) presents the results for the synthetic linear regression example with d 32, for various values of n. for constant learning rate 1) 0.001 across all models, and batch size 1 for each local gradient. Figure(((b) ((b))compare PopSGD convergence (with local batch size 1) against sequential mini-batch SGD with batch size equal the number of nodes n.
Examining Figure 3(a) we observe that both the convergence and loss variance improve as we increase the number nodes n, even though the target model executes exactly the same number of gradient steps at the same point on the axis. Of note, variance decreases proportionally with the number of nodes, with n = 128 having the smallest variance. Compared to mini-batch SGD with batch size (Figure 3(b). PopSGD with 128 has similar, but notably higher variance, which follows the analytical bound in Theorem 4.I
CIFAR-10 Experiments. We illustrate convergence and scaling results for non-convex objectives by using PopSGD to train a standard ResNet20 DNN model on CIFAR-10 10 in Pytorch, using 8 GPU nodes, comparing against vanilla and local SGD performing global averaging every 100 batches (we found this value necessary for the model to converge). We measure the error/loss at an arbitrary process for PopSGD. We the parallel versions 4 and 8 nodes.
14

---

Under review as a conference paper at ICLR 2020
(a) PopSGD convergence VS.
(b) PopSGD convergence vs. mini-batch SGD.
Figure 3: PopSGD convergence (training loss the step versus parallel time) on the synthetic regression task the number of nodes (left), and versus sequential SGD with different batch sizes (right). Sequential SGD identical to PopSGD with node count The cutouts represent zoomed views.
040
LocatiCD-ge
Pepttippt
08)
500
0314
030
Loca1500pp
LocattCC>
090
Rep35
055
SGD
(a) Train accuracy for ReSFFRR0C
(h) Test error for ResNec20/CIFAR10.
520
Papiap-2
AppiChppp
Lcca 5cb p4
perafill-gdd po
puro kd spd p1
600
Sendnd a0t Aue 10% t1:n
(c) Time to 90% train accuracy.
The results Figure 4(c) show that (a.b) PopSGD does indeed converge faster as we increase population size, tracking the trend from the convex case; and (c) PopSGD provide non-trivial scalability, comparable or better than data-parallel and local SGD.
Training ResNet50 on ImageNet. Figure 4 shows the test and train accuracies for the ResNet50 model trained on the ImageNet dataset, with 32 Piz Daint nodes and mult = 4. PopSGD achieves test accuracy within < 0.5% relative to the Torchvision baseline, despite the vastly inferior number of iterations, in total of 29 hours. By way of comparison, end-to-end training using standard data-pare parallel SGD takes approximately 48h on the same setup.
C COMPLETE CORRECTNESS ARGUMENT
Lemma 4.2 Let Tp. = -b/(a+ VV)), be the learning rate estimate of agent i at time step t, in terms of its time estimate Vi Then, there exists constant 7i such that, with probability at least - 1/T
15

---

Under review as a conference paper at ICLR 2020
Train accuracy (Resnet50)
Test accuracy (Resnet50)
M~m
60-
Accurscy
-0-
Mam
22-
buseirn
busdrn
X0003
<30m
20003
10000
30000
re0m
Steps
Steps
Figure 4: PopSGD train and test accuracy using 32 nodes on Piz Daint, measured at lixed arbitrary node. for training ResNet50 ImageNet. The round multipler value is mult 4. The X axis measures SGD steps per model. whereas Y measures Top-1 I accuracy. dotted line is accuracy of the Torchvision baseline (Marcel and Rodriguez 2010). PopSGD below the test accuracy of the baseline by < 0.5%.
(Here, T is total number of steps our algorithms takes), the following holds for every T 2 1 and agent i:
1 U1
<
2.
(C.1)
2 π
Proof. Let G³ = exp (s(Vi- 4) +
Σ exp
for some fixed constant Ç. The
following lemma is proved as Theorem 2.10 in Peres et al. (20156)
Lemma C.1. For any 2 and some fixed constants and 0, B[G.] < 48 Subsequently, we can show that for any 2 and agent i:
( n.
Pr t
Markor
40 n S
V
log T < Pr|G's 2 Td]
(C.2)
Çe T
Hence, for large enough constant g, using union bound over T steps,
show that there exists
constant 7 > 0 such that for every T > t 2 and agent i, 1 Vi < & log I" with probability at
least 1 - 1/777
Let c be . thus a 2 2en log T = 2 log T"
This allows us to finish the proof of the lemma:
log
a+t+ logT
Me
<
I
a+t 2.
(C.3)
att
mc
This allows to bound the per step change of potential Т, in terms of global learning rate T)t- Lemma 4.3 For any time step and fixed learning rate Tt used at t, we have the bound
ETTe//Td] < (1-1)), 4n M
T; 1/2
8n8 M².
Proof. First we bound change in potential A, P(+1 - T, for some time step / 0. Let A be change in potential when we choose different agents and j at random and let A be change in potential when we select the same node i. We get that
E A
ΣΣ
Σ E [
16

---

Under review as a conference paper at ICLR 2020
We proceed by bounding a change in potential for fixed i + j. Observe, that in this case
14 (X)) + ml (X/))/ and X141 = X/+1 (X + x2) - (x/)
M++1
n/ (x;))/2.
Hence,
2 (ni9)( + ( - prc.
Xi+1 pe+1 = X/+1 - Mt+1 = (xj + x/)/2 -
2n
For k & {i, since X = X2 we get that
1 (1/9 + +x Pr.
X Me+1 = X +
This gives us that
S|A t x.] = Ex + x2)/22 n n
(m) + + - mell ||x 1ell
2n
+ E
(xF + x2)/2
(X:)
mull? - -11X 1 11
2n
E [B|x + (n/.. + (x,) - ml| || | - || - mell²)
Σ
2 /2/22 ( |x| - uell 1 -1x3 - mell
n - +x) (x; - m4) + +xx me)
+ 2
n 2 2
(I 12
2n
Σ
(1 x na) + 1 +
2
+
n
(i.))
Observe that
B (x))) (x:)iI < (40)2 Fact 2.3
2M² (n1))+((72²²
Lomma 42
167 M2.
and
+ + - - =0
Thus, we have that
1 E
A
x.
<
2 211(x; - (x)
|| - Holl? - -IIX/ - -1el
- (x)) -m) + +xx: -m,)
+
+ +321%
n nn=2) M² + Σ
ne M2
16
2n
S
-1Ix: 1:ll-ml11/221111 - 1ell 12/22 (X, 14,, X1, pa)
- (x))) (X) - -w:) + -Xx: - -mr))
+ 8n8 M².
C.6
similarly we can prove that
E.
X < - En (x: + V.. (X:), (X. - -4) + (x;-
- pc)) + M22
By using inequalities C.6 and C.7 in inequality C.4 we get that
E
ΣΣ
Σ [
(Ix:-
mel + ||* 12)
+ ΣΣ
(X) Me, X² pp))
n²
17

---

Under review as a conference paper at ICLR 2020
ΣΣ
3 E00(( -x) -u,) + Sn/
+
Observe that
ΣΣ igf
(x; 2
Me. x²- me)
Σ n
n
(X
pe:
Σ
x
Σ
| -Mell
1
re-
n2a
n2
j&t
and
ΣΣ it)
-
14
1x - 1ell/12
n1
Σ || - mel1
n
n
n2
n²
Hence, we get that
< T ΣΣ
1 n2
E
A
[X -xa)0 (C.9)
Further, we have that
(x;) + v (X)), (X) -x) (X} -x+)
n
2n (() x; - -ma
E( (X;), (x} - -e)) + ΣΣ ( (x:- - 14)) + Σ
n
n
1=1
2n
Cauchy Schwarz
2n E | ||x -xel
[ (X X - Me}
S
2 E
19 (x;)))
|x -
Hell
Jensen
2n
(X;(())))
11x uill 5
2m M
x - Hell
n
n
n
i=1
i=1
Lomma
47
4m M
12
Cauchy Schwarz M
xx - mell3) 1/2
rí 1/2
X pell
An
M
n
n
By plugging above inequality in inequality C.9 get that
r, n
Te
1/2
E[A < + 4m M
8n M2.
Hence, considering the definition of A. and the fact that the above inequality implies
E < -r.r, 4n,M M
L' 1/2
+ 8m/M²
n
we get the proof of the Lemma.
Lemma 4.4. Ifa 2 18n, then the potential is bounded follows
BTT.] S 36nb² /(t + a)² M² = 36mm) M².
Proof. We prove the lemma using induction. Base case t = 0 trivially holds, since I, 0. For induction step, we assume that at time step t, EE[T,] < 36mb2 M2 (( + a)2. Our goal is to prove that E[ < 36nd2 M² /(t + a + 1)?.
ET E[ 241 [T]]
Lemma
(1-
1
1
B[r
ME
ME
(E)
Pe 1/2
8n 2
71
Jensen
1
E[Ti]+ + 4m (E)
1/2
+ Sm
n
n 22
1 36nb2 M2
862
+ (1 + a)+
n
(I (1+ aa2
(1 (1+
36nb2 M²
36nb2 M²
36nb M2
M2
+
(1+ 1)
(t + a)²
(t + 1)2
a)+
18

---

Under review as a conference paper at ICLR 2020
36nb M2 (2 2(t + +))
3612
M12M²
(t+ a + 1)2
(t+ (t + - 1)²
(t+a)²
36nb2 M²
72nb M (t + +1
M22
(1+ + 1)3
a1+a) (1 a + 1)
(1 ((+a) a)+
Using the fact that t + 12 2 a 2 18n in the above inequality allows us to get
36nb2 M
M2
M2
36mb M²
E[r--l <
(t + + 1)2
(t+ a++
(t at+
(t+ a + 1)2
Lemma 4.5 For :t $ 64I we have that
E M++1 - x² |p S (1- ne
Bllle - x=1 - 1)t
B[f(m) - f(x")] +
16
n² +
288n M
2n
n
Proof. Let F, be the amount by which μ4 decreases at step t. So, Fe is a sum of (X;) and n
"
nd (xx)) for agents and j. which interact at step t. Also, let F. be the amount by which f would decrease if interacting agents used true gradients. That is, for agents and j which interact at step 4,
Fj is sum of z' (X()) and Li (X()).
E |++1 - x² 1|2 = E Mr - Pg - x²
14 - Fe - x² - F² + r:ll"
= EE
E
1r x=- Fy
2
+ E
P² F.l + 2E Me - x² - F1, Fi F.
C.
Observe that [P] = Fl, hence the last term in the equation above is O. This means that in order to
upper bound E
M++1 x* we need upper bound B | x=' F/ and E. Fi F
For the latter, we get that
- vf(x;) -
+ The (x,)) - vF(x;1)| |
E
Fl
F+
E
n
2
E ق
(X))
v((x))) +
Tr.
B B (XF) - vF(x/)112
n
Fact 4
Lemma F.
o²ni
E
(x;)
|x(3)1
0²
16
72
n
2
For the former, we have that
E Me x² - F³ Elipe
2²1
2B(H4 - x², Fi))
+ V/d
= =Ellm- - xx $112 +
E 7
(X(+)
n2
n
jml
x" (x()) + Thd v((x)))
2E
n
i=1 j=1
4
< Bllm x11 +
2
V
Σ
Re 1l - x², V ((x:))
3
n²
i=1
1=1
4 n
Elim 14 - x= 1|2
+
-
-
2 Σ E mh
x
+
xi
x², x,
3
19

---

Under review as a conference paper at ICLR 2020
Bll
x=1 x=11
4
( V((=)]]
4
B pr X (x()))
n
n
B
x -x,, vs(x;))
C.11
n
1=1
In order to bound V - in the following form
V (1² we can use the L smooohhnnss property for convex functions,
f(y) 2 f(x) + (Vf(z). +)+ 1
2L [Vf(0) Vffa
(C.12)
By setting y X and = x²' we get
[V \)(=")) = (I(((X)) ((x)))
(C.13)
Additionally, by é strong convexity, we have that
x", x: x", vx(x;)) s -(f(x))) - f(x²)) - = - x²1
(C.14)
By Cauchy-Schward inequality, we get that
-2( pr X ) S 2 1 + - |VV (2L)
=2 11 + (x;)) vf
Using L- smoothness property
C.I3 in the above inequality gives that
2(m- 22(1- x V ((x)))
< 2T
- 11 + (f(x)) f(x)))
(C.15)
By plugging inequalities 1.13)).
C.14 and 15.15 in inequality C..1I. we get
E 144e - x²= - Fi|
S E
144
x=1 1|?
+
4L.
E X; -mel?
n
+
8L
(ntt
E (xx:) - f(x')\
n2 Σ
2
B)x( f(x))
n
2
x x=1 x²112.
n
Observe that x 112, X - 14 112 and Ex(( - [xxt)] are non-negative terms, Thus, by
using Lemma 4.2 in the above inequality we have that:
E |4 x== - F!
a 8LA/
S E
1=1 + ||
E|x
mell
n²
+
32
n
B(f(X;) f(x='1
1)t
Σ
-
n
n
mll
B E| 1011
n²
EEl
x" x11
+
8LM n²
Σ
E||; pell
1=1
17 +
32
1)EIF(X)) - -<)"))=EEI"X"" - =x-112
n
By using The S Biz in the above inequality we get that
20

---

Under review as a conference paper at ICLR 2020
B |e x²
&Bll
x²1
8LIT
B||x; pell
n
7/t +
((x'] - x² x²11?
n
1=1
By Jensen's inequality and convexity of f and square of norm we have that
Ui x="
Tt Fy
Bl - x² x=1 + S
81/ L
Σ
E - Mell
E
n²
1=1
1tt
B[f(Hr)
f(x*)] - CE||K - 2011
n
2
"1t Elf(He) fx(x')] )]+ + 81)
Ellsee x²1 112
ETT
n
2n
n²
Lemmal 4.4
(1
1
Bll
x² 1²1
1 R[f(He) - f(x²)]
n
2n
2881/² 2
n
Finally, by using the above inequality in inequality
(C 10 we get
Pc+1 x²
S (1
nel
Bllme
T1 x=11--
[ff(()) f(x*))
16
288n M
2n
n²
Theorem 4.1
Let be T-smooth, E-strongly convex function satisfying conditions (2.3) (2.5), whose minimum x² we are trying to find via the PopSGD procedure given in Algorithm 7 Let the learning rate for process i at local time t = =VV be ni b/(tt + a). where a max(2en log T, 18n, 25)L/E) and = 4n/l l are fixed(for some constant c). Let the sequence of weights we be given by = (a + t)2 Define Hr = Ei= X ST = Σt= 2 JT and yr ST T-- WeHte. Then, for any time T, we have with probability
011 poly T) that
al
64T + 2a)
0² 9216Tn2 2 L.
(lf( {(x))]
I1m0 2²112
2ST
eST
S2
Proof. We use Lemma 4.6 to solve the recurrence given by Lemma 4.5 For this we 1): 110; 4n
That is, we set parameter 4n/E. E. We also use A = 1/2, B 16o2, and C = 288 2 Lnd
Eltaj
This way we can rewrite Lemma 4.5 as
p0|pe41-x*1
101 S (1 Bllue 211 AA, - f(x*)) Bag + Caş.
Further, let yr nSr Σm= ETD w.Xi Also, let be Eff(p) - f(x*) and a. EE
EE|m | x²
By convexity of f we have that
1 T-1
Σ
w.
((f f(x*))
(C.16)
ST
1=
Using this fact and the Lemma 4.6 we obtain the following.
a²e
64T(T + 2a)
9216Tn2
Bif(yr {(
1| x²112+ +
0²
M
(C.17)
2S,
21 EST
R2S

---

Under review as a conference paper at ICLR 2020
what is left is to find the appropriate
For that we remember all the constraints on
a 2 2en log a 2 18n and [(1+a)
S n
These inequalities can be satisfied by setting
61.
max 22n log I, 18n, 2
D NON CONVEX ANALYSIS WITH PL-ASSUMPTION
In this section we deal with the case when the function we are trying to optimize is non con- vex but it satisfies PL-assumption (5.2) with constant a. More formally, function f satisfies PL- assumption 5.2 with constant a.
Theorem 5.4 Let f be an non-convex, I-smooth, function satisfying assumption 2.5 and PI-
assumption 5.2) with constant a, whose minimum x² we are trying to find via the PopSGD procedure
given in Algorithm Let the learning rate at time step t be Tt altta)
in Then, for any time T, we
have
a² (a + Tja
4608L.2
64LM2 aT +a)
B[ f(x') S
(B][(Ho)]
f(x)))))xx)))))))))
(T + aa)
Proof.
T- smoothness
B[f(H)+))
S
B[f(me)] + B (VV M++ - me) + Bllle+1 - Mell 2
(D.1)
n
2 (x+))
1/ Øz (x!))
=B[S(u+]]
(w+):
(D.2)
n
n
j=1
L
(x;)) + Thé
El|
(x
(D.3)
2n²
i=1
2 (x,)
Lhd -xحر
$ E[f(m+)] +
BV
(D.4)
==
(x:))1 + Th n
(D.5)
= =[[((m)] Σ
2 BVV fm)) (x,)
E
Σ
21 E (x)))
(D.6)
n
n
i=1
Using [x] = fzx) and property
2.5 we can rewrite the above inequality as
2 B(VS(M),
Th V(((X))
2L )2
B[((+++1]] S BBf(ue))
M²
(D.7)
n
n
2n n²
= E[f(He)]
E f(r) v.(()) - vx({i))
(D.8)
2nt n
2L(n))²
Bl
n3 M
(D.9)
1=1
< E[f(Po)
E
[V 2 + (V/) [[(})|]
(D.10)
n²
2n
Σ 2L(n))²
B[V
2
(D.11)
n²
n²
n
(m
= =[f((e)]
-
v
M
n
(D.12)
22

---

Under review as a conference paper at ICLR 2020
Lemma 4.2
B[s(M)))
2nh
E
V ( V
T
B
V
S
(1+)l
+
LLi
M
2n
n
1=1
(D.13)
L --mooohhness
21
8Lmg
B[ +
Σ
Bllla - x;11
B
E
V [(+))
+
M (D.14)
n²
2n
n²
==1
Recall that by Lemma inequality becomes:
4.4 we have that [[T
Ei= Ellse
X;11 f 36mn/ M
hence the above
(((()))) B[s(N))
72L 72
Th
8L M
n
2n
n2
Next use PL PL-assumption 5.2
which says that
V ((e))l 2 alf(we) f(xx))
Hence, we get that
- 72L3n1 M² nha (s(me) -(xx)) + 8LM
M
n²
This can be rewritten as:
(B[f(m=) - f(x))(())))))))))))))())())))f + 72I.21 M
8LNp
Bif(p(+)) f(xt) (1
+ n²
M
(D.15)
Next as in the proof for convex case, define wt (a + t)² and we set f/ =
4n
We get that
a(l+a)
(a (a+t)
4
(a + t) a
(1
(1
T
71
4n
t+
4n
< (a 1)3
a
Wt-1
4n
By using this in inequality D.15 and unrolling recursion we get that
WT (E([(UT) - f(xx)) s aojo (B[f(Ho)) f(x)))
1
Wi STa M
7r
n
no
1)t
n
T)
n²
t=
= - 2)
4 a²a
1152L2222
32(1 + a) LM
(R[s( f(xx))
a 4n
a
an
a (B[f(uo)] - f(x))) + 1152L2M2nT 16(T + LM? <
4n
a²
an
Next we divide the above inequality by wr
aatry'a = in
We get that
or
a
4608L2M2222
64LM
-[ f(x') S (a + TJ3 [B[((ro)--S00 - ((x)))
(T
(T + +
E NON-CONVEX ANALYSIS WITH CONSTANT LEARNING RATE
In this section we address the case when function we want to optimize is non-convex by using constant learning rate over all iterations and process. Let our learning rate eta. Observe that since oi = 1/: < 27,, Lemma 4.3 holds. So, we get that
E S (1- )r-)r, + 4nM (T:) 1/2 + M
(E.1)
n
Using induction as the proof of Lemma 4.4 we can prove that the similar results holds for the constant learning rate as well:
Lemma F. For any constant learning rate 1) and t. > O, we have
ET] < 36nn² 2
(E.2)
Theorem 5.2
Let f be an non non-convex, L-smooth, function satisfying assumption 2.5 whose minimum we are trying find via the PopSGD procedure given in Algorithm 7 Let the learning
23

---

Under review as a conference paper at ICLR 2020
rate use be n/ VT. Then. for any T 2 n²: v (f(mo) - f(x'))
T-1
36LM2 2LM
VT
VT
VT
Proof.
-- smoothnees
Bis(+++1)
B[f((n) + R (V(S)) - -14) + 121 - Mell
(E.3)
B(V)(u)) (x:) 7 (x/1)
(E.4)
1
n
j=1
(x:) + (x)))
(E.5)
2n
12
1=1 j=1
n
I {E[f(m)] +
EV f())) (xx(x " (x²))
(E.6)
n
12
n2
i=1
j=1
7 + (x)0))
+
(E.7)
1=1
Σ 21 ~
= [[((M))) +
- -x)())
(E.8)
1=1
Using [x)] = fxx)
and property 2.5 we can rewrite the above inequality
B[((+++)] S (((( +
Σ E(V((A), "V((x)) +
Σ
2
M
(F.9)
n
i=1
2/
=Eis(m+) +
E Vf(m) vs(()))
(E.10)
n
V (w)))()) 11 Σ 2L
E
M²
(E.11)
n²
< B[f(p)) +
| 2 + [mm) [{(())
(E.12)
n
27
[| + Σ 2La
M
(E.13)
n13
1=1
12
2Lm²²
E[f(pe)) + (IV) - {((x)))1
E (
M²
n3
(E.14)
T- smoothhnsss Eff(p:)] +
Σ
II'm n²
E
El X 7 [ + n
2Lm²
M
(E.15)
recall that by Lemma E.1 we have that E[T.] Ei Ellme X1112 < 36n7² 2 M hence the above
inequality becomes:
[[(((())) B[S(m)) < 3612,33 M2 " E 11:))
2L M
(E.16)
n
n²
by summing the above inequality for t = 0 to = T - 1, we get that
Elf(ur)) f(Ho) <
1 B [BIlf(
2L M²)
(E.17)
n
n
n²
1=0
24

---

Under review as a conference paper at ICLR 2020
From this get that
36 M 2 (B.18)
"EIVS("))" S f(vo) -[ n
n² M
n
Note that ([ 2 fx=) hence after multiplying the above inequality by tT we get that
E Bl n(f(po) - 36LM2 2LM n
T
TT
Observe that 17 n/ VT S 1/n, since T 2 n². This allows to finish the proof:
T f v n n(((p)) - [(x)))
36LM
2LM
+
+
n
n
(f(Ho) - -f(x))
36LM² VT
2LM²
+
VT
VT
Next we replace assumption 2.5 with assumption 2.4
We start by proving the following lemma:
Lemma F.2. For any time step L, we have:
Tt
4n²²
X <
+
B (x;)
2n
n
Proof. First we bound change in potential A, r++1 Т3 for some time step t > 0. Let A be a change in potential when we choose different agents and j at random and let A be a change in potential when we select the same node i. We get that
E [ = ΣΣ#EAAMX, + Σ D [AA.I.
E.19
We proceed by bounding a change in potential for fixed * j. Observe, that in this case [4++1 = Pe- (ng: (i and X X24 (x) + (x2
(x;)
Hence,
X M++1 X - P1-1 (X)+ x2)/2
n 2
(119. (xt) + nā (x{)) pc-
2n
For l & {i,j}, since X = X we get that
X p4+1 = Xxx + -nā + +x²x((()) - pc.
This gives us that
E
A 3 1x. = [x; xx///2
2
(n... (Xx) + no (xx)) - mell || 1ill
2n
(X
+ x²)12
2
(nā (X)) + (x²)) mxl1 - -|X1 m..1" 11?
2n
Σ
[ x
1
(nā (x.) + (x - u4 nal || - 1|* 1tll3)
+
x
#z/2 + (X) 221 || M4 12-2 1| Hell
n 2
E(ng + (x,) (X; (. + (x} pr)
n 2 (X:)
+ 2
2n
2
EEl (X:) (x)) x m4)
1 7o ElI no. (x{))))
(E()
25

---

Under review as a conference paper at ICLR 2020
Observe that
n (ngg(( + (X) X me) = O.
Thus, we have that
E [ 2 xx
(x) well 11x - m
-X;) + nū; (X)), (X) mba)
+ 4n7 (n-2) 2
+ Σ
(B (x)) Bli (X/)12
2n
n²
(+
s ||x pelll/12 || me 1//1//2 -x; - X?- pp)
((n):((;)) + (x/), (x- - (4) + (X- - -10)
+ (Xx))
(x))
E.21
similarly we can prove that
E A x
ك - ((ū + 79. (x- - me) + (X- p4) + 2n² (x))))
E.22
By using inequalities E.21 and E.22 in inequality E.19 we get that
E [ = ΣΣ
E
E |
(1x + || 121l122) + ΣΣ
(x) -xe X² me)
nz
itj
211² n
Σ
E(ng. + nx)) - mx)++ me))
Σ
E
1 x2)113
n
n
Observe that
Ex pc: X -1))
Σ 5 (X) M4: Σ
n
X -1))
-X/- -uell
1 r
n2
n
its
j&1
and
( 112 -nell/2)
Σ
|x
mell2
n² Te.
112
Hence, we get that
B
E
Dt n
ΣΣ
1 n
E (x²)) -m0))+
2n² n
Σ
B (x))).
1=1
(E.24)
Further, we have that
-x)) (x)) + (X/(, (x, - + (X/ pc))
2
2n
(X.). (X8- pc)) +
B (xi- mx)) +
B(G (X)) ), xi
-Ma)
i=1
7
2/ [ x pa)
2nj
B
1
1x:
mell²)
2nF
Σ
E Bl (X.) |12
n
n
2n
n
2n
By plugging above inequality in inequality
E.24
we get that
r,
4np
EA|X|
+
Σ (X)()
2n
n
Hence, considering the definition of A, we get the proof of the Lemma.
26

---

Under review as a conference paper at ICLR 2020
Lemma E.3.
Σ (x))( s 2no² 127E[T.] 6nEj
(H.25)
Proof.
E 91
Σ
( V
2
(X)
V +2
+2
B [x
2
+2 2 Σ [((x vf(m)) VVf(m) > vf(())// vf((X)//nl
8
< 2
Bll (X:) - V +6 Σ B([V VS(4))1 + Σ
B1 Σ
-
1=1
+6 6
E
|/1|
j=1
6L
< 2no + 6L Σ
Bllm
x
Ellse
x 12 + 6nE
i=1
1=1
1=1
2no² + +12LE[[r]] 6nL
/nx3)/
Notice that for 17 S 16VL the above two lemmas give
1 + + 24 E
B < (1
/(x))//111
(E.26)
4n
Observe that since E 1/4n)* 4n, the above equation results in Lemma E.4.
T
[ < Σ t=
327 3n 00
96nm E
(xx))/
(E.27)
Now, we are ready to prove the following theorem
Theorem 5.3
Let f be an non-convex, L-smooth, function satisfying condition 2.4 whose minimum x= trying to find via the PopSGD procedure given in Algorithm Let the learning
be n n/VT. Then, for any T 2 4624 max 1 1nm we have
T-1 Σ
B[f(uo) - [[f()")
40
32I
768I20² 2
Bl
VT
VT
VT
VT
Proof.
L. smoothness
L
Bff(p++1)
E[f(p() + (VVFf(H) 1441 - 1i) E1t1 - mell
27

---

Under review as a conference paper at ICLR 2020
=[[[(N)] +
((V](()::- -xx())
R
" (x²))
i=
13
L
(Xi)
+ " (x))1
2n²
n2
j=1
- <Bf((M) +
- -x - (xx))
12
j=1
[1
9x + (x)()
B[((M))) + Σ
(V -x + Σ
2L
E
T. (X)il
1=1
-Bf((m)] + Σ - -2v(())) +
2L
B
1
(x;)
9:
n
n
B[S(m)]] + "E
2 E
/ (mx))l
- "E
v)(X))/n113
2L Σ
E
(x;))
i=1
1=1
S {[f(MA]] +
1
E[T]]
" E
V (14))
"E
Tx(x)//nl1
n
n
40
2
12L n²
E[T,]
+
B
n
n²
Next, we sum the above inequality from = 00 T - and divide by T.
We get:
T
E[f(no)] - [[((NT]]
402n7
T-1
T
24 1?2
+
+
E[T
+
E[r
Tn
T
n²
2T
T3
t=0
T-1
12
n
Σ
E
Σ
/
E
//l
n2T
nf
t=
1=1
Lemma
[[S()o)
(UT))
10211
+
32n 120
96np2
nT El
L22
//(x:)/n11
T
n
n
768
L220
T-1
2304 L22
+
E|
//
12
nT
T-1
Σ
7
/((x)//1l13
0=
Next we assume that 7
E5L and 7 1. This allows us to eliminate terms with E (((x)//m|| multiplicative factor from the above inequality. hence we get:
Tn (E(())) E[f(Ho)] E[f(wr)] T
40 n²
+ 3 L222 7
n
n²
next, we divide the above inequality by Y:
+ Ell((n))1 < m(B[f(Ho)] - (HT((
40 + 32n 2²00=
76877 L2
Tn
28

---

Under review as a conference paper at ICLR 2020
Further, assuming that 17 I 1/n, get:
B (EE[((mo)] - [[(((r))
400n
32n
768nL20 o²
Tn
n
n
n
n(B[s(Ho)] B[f(x")]]
40
76 32n
+
Tn
n
n
n
B[J(Ho)] - -B[((x))
402
32
768L2
VT
VT
VT
VT
Observe that all the assumptions 1) satisfied for T > 4624 ma24max 1)m*,
F GENERAL INTERACTION GRAPHS
The erucial difference between interactions on arbitrary graph and interactions on clique graph comes from the fact that we get different bound on Gamma potential. In the case arbitrary graph we can show that:
E < (1 ((2emm) + 4m [
1/2 + 8ny M2
Where 22 a second smallest eigenvalue of the Laplacian of the interaction graph and m is the number of it's edges. This allows to bound I and then can follow analysis of clique case get the convergence rate. For example, in case of cycle
E[T < (1 1011((nn))))) + 4
Tt 1/2 + 81 M
-
n2
and hence
E ET, < Onn'n??))
and this allows us to prove Theorem
5.1
29


Reviews:
[{"review_id": "SklpaUAaKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 considers scaling distributed stochastic gradient descent to large number of nodes.  Paper proposes novel asynchronous variant to decentralized SGD, called PopSGD. It models asynchrony with the population model. Paper theoretically analyzes the proposed method and shows that in the convex case PopSGD has a linear speedup in the number of nodes compared to the sequential training on one node. However, in the non-convex setting, the PopSGD rate doesn’t have a linear speedup. The paper also provides experimental evaluation of PopSGD where they scale PopSGD up to 1000 of nodes in the convex optimization; and also apply PopSGD to neural network training on ImageNet.\n\nMy score is weak reject. The major reason is that it is not clear how does this work theoretically and experimentally compares to the previous asynchronous variants of decentralized SGD (Lian et al. (2017b) AD-PSGD and Assran et al. (2018) SGP) or to the centralized SGD (parallel mini-batch SGD) baseline; and what are the benefits of the proposed method. \n\nConcerns that should be addressed: \n\n1. No theoretical and experimental comparison with the baselines (see above).\n\n2. Extension to the non-convex case: there is no linear speedup in the number of nodes n. Does this mean that it is better to use Centralized SGD (which has speedup in the number of nodes)? The comparison should be made explicit. \n\n\n3. The paper is a bit too long (10 pages) and contains some repetitions. Consider to shorten a bit. (e.g. procedure of splitting data between nodes was described twice on page 2 and 4; proof overview on page 6 could be merged with two steps on page 7)\n\n\n4. The procedure how to sample nodes uniformly was not discussed in the paper. Moreover, it is also not clear why \\Theta(n) updates could be done in parallel. When intersection happens, many nodes would have to wait for the previously selected pairs to finish computation.  \n\n\n5. Why are the local learning rates required? When scheduler samples the nodes uniformly it can also transmit them the global time count.\n\n\n6. In the description of data distribution (page 2, paragraph 4-5, page 4, last paragraph): what if there is more samples than available nodes? do the nodes exchange samples or only gradients? Is it possible to have part of the full dataset on every node without sharing it with anyone? \n\n\n7. Page 3, line 3: Lian et al. (2017b) and Assran et al. (SGP) also showed that they don’t require global synchronization. \n\n\n8. Page 4, line 2: The AD-PSGD rate does have a linear speedup in the number of workers n, so the claim should be corrected. \n\n\n9. Page 7: all lemmas and theorems hold only for the global stepsize \\eta_t. Would it also hold with local stepsizes \\eta_t^i? \n\n\n10. Extensions for arbitrary graphs: would it be possible to have one theorem for all possible graphs and see how graph parameters (e.g. spectral gap or others) influence the convergence rate? \n\n\n11. Experiments: I didn’t understand the definition of mult constant and what does it control. Re-phrase this paragraph. \n\nMinor comments: \n- page 1, last line of the paragraph 2: “parameter obtained by node i at time t“ -> “stoch. gradient obtained by node i at time t“? \n- page 2, line 4: “variants(e.g.” -> “variants (e.g.”\n- Usually \\mu is used for strong convexity parameter. \n- page 3, paragraph 2, “we emphasize that convexity is not enough…” the purpose of this sentence is unclear, what is enough then or why is that important to know? \n- page 3, related work: Nedic at al. Nedic et al. (2017) -> Nedic et al. (2017). The same for the other citation. \n- page 3, related work: PP model is not defined. \n- How can PP model result in a multigraph? If two samples pairs have the same nodes, then they need to be processed sequentially, so it can be modeled with two graphs for different time steps. \n- Population protocol model (page 4): “states store real numbers” -> can they store vectors instead? \npage 5, estimating time and the learning rate section: what happens if the V^i is equal to V_j? Who updates its value? \n- Figure 1(a) was not discussed at all in the text. \n- Page 6, Notation and preliminaries: why it is required that T = O(poly n) is not explained.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BkeHxzS0Kr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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 proposes to use population algorithms as a mechanism for implementing distributed training of deep neural networks. The paper makes some claims about the relationship to previous work on (asynchronous) gossip algorithms that appear to be incorrect. In fact, the proposed PopSGD algorithm is very closely related to other methods in the literature, including AD-PSGD (Lian et al. 2017b) and SGP (Assran et al. 2018). I recommend it be rejected due to lack of novelty and missing connections to much related work.\n\nThe introduction (page 3) mentions that the \"matrix characterization is not possible in the population model.\" Here the \"matrix characterization\" refers to the typical approach in which gossip algorithms (synchronous or asynchronous) are formulated and analyzed. I'd appreciate if the authors could elaborate on this claim. In the study of gossip algorithms, the organization of time into \"global rounds\" is purely for the sake of analysis; a global, synchronized clock is not required to implement these methods. In fact, the description of the setup appears to be very similar to the asynchronous time model described used to analyze \"randomized gossip algorithms\" (see the well-cited paper by Boyd, Ghosh, Prabhakar, and Shah). In the PopSGD case, the choice is simply to allow the complete graph (i.e., any agent can interact with any other agent) rather than restricting interactions of a given agent to be among a subset of the other agents (i.e., its neighbors).\n\nLet me elaborate on the ways in which PopSGD is similar to AD-PSGD and SGP. PopSGD involves interactions between randomly drawn pairs of agents. The AD-PSGD algorithm of Lian et al. (2017b) also performs updates between pairs of agents drawn randomly at every step. The definition of the PopSGD interaction in (1.1) (or equivalently Alg 1) implies that when agents i and j interact, neither i nor j can interact with another agent until the current interaction completes. The main difference appears to be that in Lian et al. (2017b) agents are organized into a bipartite graph where $n/2$ nodes are \"active\" and initiate interactions with one of the other $n/2$ \"passive\" nodes (drawn randomly). This is done for practical reasons - to avoid deadlocks.\n\nI also believe that PopSGD can be viewed as a particular instance of the overlap-SGP algorithm proposed in Assran et al. (2018). Overlap-SGP, the way it is described, makes use of one-directional interactions (agent i may receive and incorporate information from agent j without the reverse happening simultaneously). This was also introduced for practical reasons. It is possible for multiple interactions to happen simultaneously, and the pattern of iteractions may vary over time. There is nothing in the analysis, however, that prevents one from restricting to symmetric interactions, in which case one could recover the symmetric updates of PopSGD. To compensate for one-directional interactions, Overlap-SGP tracks an additional variable (the weight, or denominator). However, in the case where interactions are always symmetric as in PopSGD, the corresponding update matrices will always be doubly-stochastic, and in this case the weights are always equal to 1. Thus PopSGD really is identical to Overlap-SGP in this special restricted case where interactions are always pair-wise and symmetric. Moreover, Assran et al. (2018) prove that Overlap-SGP achieves a linear speedup in the smooth non-convex setting.\n\nThe experiments don't provide any comparison with other related methods, and the discussion in the introduction isn't sufficient to convince me that there are significant differences between these methods. In the experiments, I also wanted to ask about the mult constant. If it is really possible to achieve linear scaling, wouldn't one hope to be able to get away with mult=1?\n\nThe decreasing learning rate schedule used in the description and analysis of PopSGD seems very restrictive. Specifically, in the training of deep neural networks it is common to use much different learning rate schedules. Is it fundamentally not possible to do so with PopSGD-type models, or is it just a limitation of the current analysis approach (specifically for convex functions)? What learning rate scheme was used in the experiments?\n\nFinally, the introduction (p3) emphasizes that it is the population gradient perspective, and the connection to load-balancing processes, which enable one to achieve linear scaling. I disagree with this statement. While I do agree that convexity alone is not sufficient, the key assumption made here (as well as in other work, such as that of Lian et al.), is that all agents draw gradients from the same distribution; i.e., that all agents have access to independent and identically distributed stochastic gradient oracles. In fact, this is stronger than the assumptions made in Lian et al. (2017a and 2017b), and Assran et al. (2018), where it is only assumed that the gradient oracles at each agent are similar, but not necessarily identical.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This manuscript studies scaling distributed stochastic gradient descent to a large number of nodes. Specifically, it proposes to use algorithms based on population analysis (relevant for large numbers of distributed nodes) to implement distributed training of deep neural networks. 

In reviews and discussions, the reviewers and AC note missing or inadequate comparisons to previous work on asynchronous SGD, and possible lack of novelty compared to previous work. The reviewers also mentioned the incomplete empirical comparison to closely related work. On the writing, reviewers mentioned that the conciseness of the manuscript could be improved.

Decision: Reject