Accelerating Gossip SGD with Periodic Global Averaging

Communication overhead hinders the scalability of large-scale distributed training. Gossip SGD, where each node averages only with its neighbors, is more communication-efficient than the prevalent parallel SGD. However, its convergence rate is reversely proportional to quantity $1-\beta$ which measures the network connectivity. On large and sparse networks where $1-\beta \to 0$, Gossip SGD requires more iterations to converge, which offsets against its communication benefit. This paper introduces Gossip-PGA, which adds Periodic Global Averaging into Gossip SGD. Its transient stage, i.e., the iterations required to reach asymptotic linear speedup stage, improves from $\Omega(\beta^4 n^3/(1-\beta)^4)$ to $\Omega(\beta^4 n^3 H^4)$ for non-convex problems. The influence of network topology in Gossip-PGA can be controlled by the averaging period $H$. Its transient-stage complexity is also superior to Local SGD which has order $\Omega(n^3 H^4)$. Empirical results of large-scale training on image classification (ResNet50) and language modeling (BERT) validate our theoretical findings.


Introduction
The scale of deep learning nowadays calls for efficient largescale distributed training across multiple computing nodes in the data-center clusters. In distributed optimization, a network of n nodes cooperate to solve the problem where each component f i is local and private to node i and the random variable ξ i denotes the local data that follows distribution D i . We assume each node i can locally evaluate stochastic gradients ∇F i (x; ξ i ) where ξ i ∼ D i , but must communicate to access information from other nodes. (1−β) 2 ) Ω( n 3 β 4 (1−β) 4 ) Ω(n 3 β 4 C 2 β ) Ω( LARGE OR SPARSE NETWORK (WHEN 1 1−β ≥ H ) Ω( n 3 β 4 (1−β) 2 ) Ω( n 3 β 4 (1−β) 4 ) Ω(n 3 β 4 C 2 β ) Ω(n 3 β 4 C 2 β H 2 )   Table 3. The lengths of the transient stages of Local SGD and Gossip-PGA. Gossip-PGA always has shorter transient stages than Local SGD since β < 1 and C β < H. Such superiority becomes more significant on well-connected networks where β → 0.
may nullify its communication efficiency and result in even more training time (see Table 1). Local SGD with a large averaging period meets the same issue.
This paper proposes Gossip-PGA, which adds periodic All-Reduce global averaging into Gossip to accelerate its convergence especially on large and sparse networks. Gossip-PGA also extends Local SGD with fast gossip-style communication after local updates. When the same averaging period H is used, the additional gossip communication in Gossip-PGA endows it with faster convergence than Local SGD.
Challenges. Gossip-PGA can be regarded as a special form of the topology-changing Gossip SGD (Koloskova et al., 2020) and SlowMo (Wang et al., 2019) (in which the base optimizer is set as Gossip SGD, and the momentum coefficient β = 0). However, its theory and practical performance were not carefully investigated in literature. Unanswered important questions include how much acceleration can PGA bring to Gossip and Local SGDs, in what scenario can PGA benefits most, how to adjust the averaging period effectively, and how Gossip-PGA performs in large-scale deep learning systems. Providing quantitative answers to these questions requires new understanding on the interplay between gossip communication and global averaging period. Simply following existing analysis in (Koloskova et al., 2020) will result in incomplete conclusions, see Remark 5. Also, the analysis in SlowMo (Wang et al., 2019) does not consider heterogeneous data distributions and cannot cover our results.

Main Results
This paper proves that Gossip-PGA converges at for both smooth convex and non-convex functions f i (the metrics used for both scenarios can be referred to Theorems 1 and 2), where n is the network size, T is the total number of iterations, σ 2 denotes gradient noise, b 2 gauges data heterogeneity, β ∈ (0, 1) measures how well the network is connected, H is the global averaging period, and we define C β = H−1 k=0 β k and D β = min{H, 1/(1 − β)}. Linear speedup. When T is sufficiently large, the first term 1/ √ nT dominates (2). This also applies to Parallel, Local, and Gossip SGDs. Gossip-PGA and these algorithms all require T = Ω(1/(n 2 )) iterations to reach a desired accuracy , which is inversely proportional to n. We say an algorithm is in its linear-speedup stage at T th iteration if, for this T , the term involving nT is dominating the rate.
Transient stage. Transient stage is referred to those iterations before an algorithm reaches its linear-speedup stage, that is iterations 1, . . . , T where T is relatively small so non-nT terms (i.e., the extra overhead terms in (2)) still dominate the rate. We take Gossip-PGA in the non-iid scenario (b 2/3 ≥ σ) as example. To reach linear speedup, T has to satisfy T  Table 2. Since C β = (1 − β H )/(1 − β) < min{H, 1/(1 − β)}, we conclude Gossip-PGA always has a shorter transient stage than Gossip SGD for any β and H. Moreover, the superiority of Gossip-PGA becomes evident when the network is large and sparse, i.e., 1 − β → 0. In this case, the transient stage of Gossip SGD can grow dramatically (see the second line in Table 2) while Gossip-PGA is controlled by the global period H because C β < H. As a result, Gossip-PGA improves the transient stage of Gossip-SGD from O(n 3 /(1 − β) 4 ) (or O(n 3 /(1 − β) 2 in the iid scenario) to O(n 3 ) when β → 1.
Shorter transient stage than Local SGD. The transient stage comparison between Local SGD and Gossip-PGA is shown in Table 3. Using C β < H, we find Gossip-PGA is always endowed with a shorter transient stage than Local SGD. Moreover, when the network is well-connected such that β → 0, it holds that C β → 1. Gossip-PGA will have a significantly shorter transient stage than Local SGD.

Contributions
• We establish the convergence rate of Gossip-PGA for both smooth convex and non-convex problems. Our results clarify how gossip communication and periodic global averaging collaborate to improve the transient stage of Gossip and Local SGDs. We also established shorter wall-clock training times of Gossip-PGA.
• We propose Gossip-AGA, which has adaptive global averaging periods. Gossip-AGA automatically adjusts H and has convergence guarantees.
• We conduct various experiments (convex logistic regression and large-scale deep learning tasks) to validate all established theoretical results. In particular, the proposed Gossip-PGA/AGA achieves a similar convergence speed to parallel SGD in iterations, but provides 1.3 ∼ 1.9× runtime speed-up. The introduced global averaging steps in Gossip-PGA/AGA remedy the accuracy degradation in Gossip SGD and Local SGD.

Related Work
Decentralized optimization algorithms can be tracked back to (Tsitsiklis et al., 1986). After that, decentralized optimization has been intensively studied in signal processing and control community.  , 2020) proposes a unified framework to analyze algorithms with changing topology and local updates. While it covers Gossip-PGA as a special form, the theoretical and practical benefits of periodic global averaging were not studied therein. The data heterogeneity issue suffered in Gossip SGD is discussed and addressed in (Tang et al., 2018;Yuan et al., 2020;Lu et al., 2019;Xin et al., 2020). Gossip SGD is also extended to asynchronous scenarios in (Lian et al., 2018;Luo et al., 2020).
Local SGD can be traced back to (Zinkevich et al., 2010) which proposed a one-shot averaging. More frequent averaging strategy is proposed in (Zhang et al., 2016), and the convergence property of Local SGD is established in (Yu et al., 2019;Stich, 2019;Bayoumi et al., 2020). Local SGD is also widely-used in federated learning (McMahan et al., 2017;Li et al., 2019a).

Gossip SGD with Periodic Global Average
Assume all computing nodes are connected over a graph G = {V, E} where V = {1, 2, · · · , n} denote the node index and E denote the communication links between all nodes. Similar to existing decentralized algorithms (Nedic & Ozdaglar, 2009;Chen & Sayed, 2012;Lian et al., 2017;Assran et al., 2019), information exchange in the gossip step is only allowed to occur between connected neighbors. To characterize the decentralized communication, we let W ∈ R n×n be a doubly stochastic matrix, i.e., W ≥ 0, W 1 n = 1 n and 1 T n W = 1 T n . The (i, j)-th element w ij is the weight to scale information flowing from node j to node i. If nodes i and j are not neighbors then w ij = 0, and if they are neighbors or identical then the weight w ij > 0. Furthermore, we define N i as the set of neighbors of node i which also includes node i itself.
The Gossip-PGA algorithm is listed in Algorithm 1. In the gossip step, every node i collects information from all its connected neighbors. For global average step, nodes synchronize their model parameters using the efficient All-Reduce primitives. When H → ∞, Gossip-PGA will reduce to standard Gossip SGD; when W = 1 n 11 n , Gossip-Algorithm 1 Gossip-PGA Require: Initialize learning rate γ > 0, weight matrix W , global averaging period H, and let each x (0) i to be equivalent to each other. for k = 0, 1, 2, ..., T − 1, every node i do Sample ξ 2 ) j one gossip step PGA will reduce to vanilla parallel SGD; when W = I, Gossip-PGA will reduce to Local SGD.
All-Reduce v.s. multiple Gossips. In a computing cluster with n nodes, global averaging is typically conducted in an efficient Ring All-Reduce manner, rather than via multiple gossip steps as in (Berahas et al., 2018). The communication time comparison between a single gossip and Ring All-Reduce step is listed in Appendix H. In the one-peer exponential network, the exact global average can be achieved via ln(n) gossip communications, which generally takes more wall-clock time than a single Ring All-Reduce operation. Therefore, we recommend exploiting All-Reduce to conduct global averaging in Gossip-PGA.
Data-center v.s. wireless network. This paper considers deep training within high-performance data-center clusters, in which all GPUs are connected with high-bandwidth channels and the network topology can be fully controlled. Under such setting, the periodic global averaging conducted with Ring All-Reduce has tolerable communication cost, see Appendix H. For scenarios where global averaging is extremely expensive to conduct such as in wireless sensor network, the global averaging can be approximated via multiple gossip steps, or may not be recommended.

Assumptions and analysis highlights
We now establish convergence rates for Gossip-PGA on smooth convex and non-convex problems. For all our theoretical results we make the following standard assumptions.
Assumption 1 (L-SMOOTHNESS). Each local cost function f i (x) is differentiable, and there exists a constant L such that for each x, y ∈ R d : Assumption 2 (GRADIENT NOISE). Recall g (k) i is the stochastic gradient noise defined in line 2 of Algorithm 1. It is assumed that for any k and i that for some constant σ 2 > 0. Moreover, we assume ξ (k) i is independent of each other for any k and i. Filtration is defined as Assumption 3 (WEIGHTING MATRIX). The network is strongly connected and the weight matrix W satisfies W 1 n = 1 n , 1 T n W = 1 T n , null(I − W ) = span(1 n ). We also assume W − 1 n 11 T 2 ≤ β for some β ∈ (0, 1). Remark 1. Quantity β ∈ (0, 1) indicates how well the topology is connected. Smaller β indicates better-connected network while larger β implies worse-connected topology.
Analysis highlights. To derive the influence of periodic global averaging, we have to exploit all useful algorithm structures to achieve its superiority. These structures are: This structure relieves the influence of network topology; • Gossip communications within each period also contribute to consensus among nodes. This structure is crucial to establish superiority to Local SGD; • When network is large and sparse, i.e., H < 1 1−β , the global averaging is more critical to drive consensus. This structure is crucial to establish superiority to Gossip SGD when H < 1 1−β .
• When network is small or dense, i.e., H > 1 1−β , gossip communication is more critical to drive consensus. This structure is crucial to establish superiority to Gossip SGD when H > 1 1−β .
Ignoring any of the above structures in the analysis will result in incomplete conclusions on comparison among Gossip-PGA, Gossip SGD and Local SGD.
Definition 1 (DATA HETEROGENEITY). When each f i (x) is convex, we let b 2 = 1 n n i=1 ∇f i (x ) 2 denote the data heterogeneity.
When each local data follows the same distribution, it holds that f i (x) = f (x) ∀i and hence ∇f i (x ) = ∇f (x ) = 0 which also implies b 2 = 0. With Assumption 4, we let x be one of the global solutions to problem (1). Table 4. Convergence rate comparison between Gossip SGD and Gossip-PGA for smooth convex/non-convex problems. We use notation b 2 to indicate the data heterogeneity for both convex and non-convex scenarios.

Comparison with Gossip SGD
To better illustrate how periodic global averaging helps relieve the affects of network topology in Gossip SGD, we list convergence rates of Gossip SGD and Gossip-PGA for smooth convex or non-convex problems in Table 4. The first line is the general rate expression for both algorithms. In the second line we let D β = min{H, 1/(1 − β)} = 1/(1 − β) for Gossip-PGA, and in the third line we let D β = H. According to this table, we derive the transient stages of Gossip SGD and Gossip-PGA for each scenarios (i.e., large/small network, iid/non-iid data distributions) in  Table 6. Convergence rate comparison between Local SGD (L-SGD) and Gossip-PGA (G-PGA) over smooth convex/non-convex problems. The rate for Local SGD is from (Koloskova et al., 2020;Yu et al., 2019;Li et al., 2019b). the structures listed in Sec. 3.1.
Transient stage in runtime. But what people really care about in practice is runtime. Since both Gossip SGD and Gossip-PGA have the same computational overhead per iteration, we will focus on communication time spent in the transient stage.
Given the bandwidth in a computing cluster with size n, we let α denote the point-to-point latency in the network, and θ denote the communication time cost to transmit a scalar variable. Since variable x in problem (1) has dimension d, it will take θd time to transmit x between two nodes. Under this setting, the All-Reduce global averaging step will take 2θd + nα = O(θd + nα) time (see section 2.5 in (Ben-Nun & Hoefler, 2019)). The gossipstyle communication time varies with different network topologies. For the commonly-used ring or grid topology, it takes |N i |θd + α = O(θd + α) for one gossip communication, where |N i | is the neighborhood size of node i, and |N i | = 3 for the ring and 5 for the grid. As to Gossip-PGA, if we amortize the periodic All-Reduce cost into each communication, it will have |N i |θd + α + (2θd + nα)/H = O(θd + √ nα) when we set H = √ n. With the formula Total time = transient stage (in iteration) × comm. per iter. We calculate and compare the transient time between noniid Gossip-PGA and Gossip-SGD (over the grid topology) in Table 5. Other comparisons for iid scenario or the ring topology can be found in Appendix D. It is observed in all tables that Gossip-PGA has shorter transient time.

Comparison with Local SGD
The convergence rates of Gossip-PGA and Local SGD are listed in Table 6, from which we derive the transient stages of them in Table 3 (details are in Appendix D). As we have explained in the introduction, it is observed from Tables 3 and 6 that (i) Gossip-PGA always converges faster (or has shorter transient stages) than Local SGD for any β and H value, and (ii) Such superiority gets more evident for well-connected network where β → 0.
As to the wall-clock transient time of Local SGD, if we amortize the periodic All-Reduce cost into each local up-date, it will take (2θd + nα)/H = O(θd/H + nα/H) communication time per iteration. Using the transient iteration derived in Table 3, the total transient time for Local SGD (non-iid scenario) will be O(n 3 H 3 (θd + nα)). Comparing it with the total transient time O(n 3 HC 2 β β 4 (Hθd + nα)) for Gossip-PGA, we find Gossip-PGA always has shorter transient runtime for a large H > β 4 C 2 β . Remark 6. While we discuss in detail that the transient time of Gossip-PGA is shorter than Gossip and Local SGDs, it is worth noting that the communication time during the linear speedup stage (i.e., after the transient stage) also contributes to the total training time. In this stage, Gossip-PGA is less efficient due to its periodic global averaging. However, we illustrate that Gossip-PGA is always endowed with shorter total training time than Gossip and Local SGDs with extensive deep learning experiments in Sec. 5.

Gossip SGD with Adaptive Global Average
Gossip-PGA suffers from the burden of tuning H by hand.
A small H will incur more communication overhead while a large value can slow down the convergence. We further propose Gossip-AGA, an adaptive extension of Gossip-PGA.

Intuition. A small consensus variance
for each iteration, then Gossip-PGA reduces to parallel SGD and can reach its fastest convergence. Recall from Lemma 8 in the appendix that the averaged consensus 1 T k=0 E ∇f (x (k) ) 2 +d 2 γ 2 where d 1 and d 2 are constants. It is observed that the initial consensus variance (when T is small) can be significant due to large γ and E ∇f (x (k) ) 2 . In the later stage when T is sufficiently large, both the diminishing step-size γ and gradient E ∇f (x (k) ) 2 go to 0 and hence leading to a small consensus variance naturally. With these observations, it is intuitive to take global synchronizations more frequently in initial stages to reduce the overall consensus variance.

Convergence.
We denote H ( ) as the duration of the -th period. The following corollary establishes convergence for Gossip-PGA with any time-varying but finite global averaging period sequence {H ( ) }: Corollary 1. Suppose Assumptions 1-3 and 5 hold and the time-varying period H Adaptive Strategy. This subsection will propose an adaptive strategy that is inspired by (Wang & Joshi, 2019). If we recover the influence of the initial value F 0 = Ef (x (0) ) on convergence rate (8), Gossip-PGA for non-convex problems will converge at O σF For a fixed T , a period H = σ 3 2 T 1 4 /(βbF 1 4 0 n 3 4 ) will guarantee the linear speedup. Therefore, the initial period H (0) can be chosen as Similarly, for the -th period, workers can be viewed as restarting training at a new initial pointx (T −1 ) where T −1 = H (0) + · · · + H ( −1) . As a result, the -th period H ( ) can be chosen as Since Ef (x (k) ) will decrease as k increases, (9) will generate an increasing sequence of period H ( ) . We list Gossip-AGA as Algorithm 2 in Appendix G and elaborate on implementation details there.

Experimental Results
In this section, we first examine how the transient stage differs for Gossip-PGA, Gossip and Local SGDs on networks with different topology and size on convex logistic regression. Next, we systematically evaluate the aforementioned methods on two typical large-scale deep learning tasks: image classification (over 256 GPUs) and language modeling (over 64 GPUs). See Appendix F for implementation details.

Logistic Regression
We consider a distributed logistic regression problem with are local data samples at agent i with h i,m ∈ R d being the feature vector and y i,m ∈ {+1, −1} being the corresponding label. Each h i,m is generated from the normal distribution N (0; 10I d ). To generate y i,m , we first generate an auxiliary random vector x i ∈ R d with each entry following N (0, 1). Next, we generate y i,m from a uni- We let x i = x ∀i to generate data for iid scenario and x i = x j ∀i, j for non-iid scenario. Each x i is normalized.   Table 7. Comparison of Top-1 validation accuracy (Column 2) and wall-clock training time (Column 3) on different methods after finishing all epochs. We also report the epochs and training time required to reach 76% accuracy (Column 4). "N.A." implies that the target accuracy is not reached when all epochs are completed.
standard deviation with shaded area. It is observed that both Gossip SGD and Gossip-PGA will asymptotically converge at the same rate as parallel SGD (i.e., the linear speedup stage), albeit with different transient stages. Gossip-PGA always has shorter transient stages than Gossip SGD, and such superiority gets more evident when network size increases (recall that 1 − β = O(1/n 2 )). For experiments on different topologies such as grid and exponential graph, on iid data distribution, and comparison with Local SGD, see Appendix F. All experiments are consistent with the theoretical transient stage comparisons in Tables 2 and 3.

Image Classification
The ImageNet-1k (Deng et al., 2009) 1 dataset consists of 1,281,167 training images and 50,000 validation images in 1000 classes. We train ResNet-50 (He et al., 2016) model (∼25.5M parameters) following the training protocol of (Goyal et al., 2017). We train total 120 epochs. The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 90 epochs. We set the period to 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the period is set to 4 initially and changed adaptively afterwards, roughly 9% iterations conduct global averaging. Table 7 shows the top-1 validation accuracy and wall-clock training time of aforementioned methods. It is observed both Gossip-PGA and Gossip-AGA can reach comparable accuracy with parallel SGD after all 120 epochs but with roughly 1.3x ∼ 1.4x training time speed-up. On the other hand, while local and Gossip SGD completes all 120 epochs faster than Gossip-PGA/AGA and parallel SGD, they suffer from a 2.06% and 0.92% accuracy degradation separately. Moreover, both algorithms cannot reach the 76% top-1 accuracy within 120 epochs. We also compare with OSGP (Assran et al., 2019), which adding overlapping on the Gossip SGD. We find OSGP ×2, while faster than Gossip SGD×2, still needs more time than Gossip-PGA to achieve 76% accuracy. To further illustrate how much time it will take local and Gossip SGD to reach the target accuracy, we run another Local SGD and Gossip SGD experiments with extended epochs (i.e., Gossip SGD ×2 trains total 240 epochs and the learning rate is decayed at 60, 120, and 180 epoch. Local SGD ×3 trains total 360 epochs and the learning rate is decayed at 90, 180, and 270 epochs). It is observed that Gossip-SGD ×2 can reach the target with notably more time expense than Gossip-PGA/AGA and parallel SGD, and Local SGD ×3 still cannot reach the 76% accuracy. All these observations validate that periodic global averaging can accelerate Gossip SGD significantly. Figure 2 shows the iteration-wise and runtime-wise convergence in terms of training loss. In the left figure, it is observed Gossip-PGA/AGA converges faster (in iteration) and more accurate than local and Gossip SGD, which is consistent with our theory. In the right figure, it is observed that Gossip-PGA/AGA is the fastest method (in time) that can reach the same training loss as parallel SGD.
Compare with SlowMo. Gossip-PGA is an instance of SlowMo, in which the base optimizer is set as Gossip SGD, slow momentum β = 0, and slow learning rate α = 1. We made experiments to compare Gossip-PGA with SlowMo. It is observed the additional slow momentum update helps SlowMo with large H but degrades it when H is small. This observation is consistent with Fig. 3 Ring Topology. While the convergence property of Gossip-PGA is established over the static network topology, we utilize the dynamic one-peer exponential topology in the above deep experiments because it usually achieves better accuracy. To illustrate the derived theoretical results, we make an additional experiment, over the static ring topology, to compare Gossip-PGA with Gossip SGD in Table 9. It is observed that Gossip-PGA can achieve better accuracy than Gossip SGD after running the same epochs, which coincides with our analysis that Gossip-PGA has faster convergence.
Scalability. We establish in Theorem 2 that Gossip-PGA can achieve linear speedup in the non-convex setting. To  and BookCorpus datasets. We set the period to 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the period is set to 4 initially and changed adaptively afterwards, roughly 9.6% iterations conduct global averaging.  Figure 3 shows the iteration-wise and runtime-wise convergence w.r.t training loss of the aforementioned methods. The left plot shows Gossip-PGA/AGA has almost the same convergence as Gossip SGD in iterations; the right plot shows that Gossip-AGA is the fastest method in training time that can reach the same accuracy as parallel SGD.

Conclusion
We introduce Gossip-PGA/AGA to mitigate the slow convergence rate of Gossip SGD in distributed training. Theoretically, we prove the convergence improvement in smooth convex and non-convex problem. Empirically, experimental results of large-scale training validate our theories.

A. Preliminary
Notation. We first introduce necessary notations as follows.
• Given two matrices x, y ∈ R n×d , we define inner product x, y = tr(x T y) and the Frobenius norm x 2 F = x, x .
Gossip-PGA in matrix notation. For ease of analysis, we rewrite the main recursion of Gossip-PGA in matrix notation: Gradient noise. We repeat the definition of filtration in Assumption 2 here for convenience.
• With Assumption 2, we can evaluate the magnitude of the averaged gradient noise: where (a) holds because ξ • We define gradient noise as s and (a) holds due to the law of total expectation.
• For any 0 ≤ k < , it holds that Smoothness. Since each f i (x) is assumed to be L-smooth in Assumption 1, it holds that f (x) = 1 n n i=1 f i (x) is also L-smooth. As a result, the following inequality holds for any x, y ∈ R d : Smoothness and convexity. If each f i (x) is further assumed to be convex (see Assumption 4), it holds that f (x) = 1 n n i=1 f i (x) is also convex. For this scenario, it holds for any x, y ∈ R d that: Network weighting matrix. Suppose a weighting matrix W ∈ R n×n satisfies Assumption 3, it holds that Submultiplicativity of the Frobenius norm. Given matrices W ∈ R n×n and y ∈ R n×d , it holds that To verify it, by letting y j be the j-th column of y, we have W y
Next we establish the consensus lemmas in which Gossip-PGA is fundamentally different from Gossip SGD. Note that Gossip-PGA takes global average every H iterations. For any k = 0, 1, · · · , we define τ (k) = max{ : ≤ k and mod( , H) = 0} (21) as the most recent iteration when global average is conducted. In Gossip-PGA, it holds thatx τ (k) = x can only happen when k = 0.
For Gossip-PGA, the real challenge is to investigate how the periodic global averaging helps reduce consensus error and hence accelerate the convergence rate. In fact, there are two forces in Gossip-PGA that drive local model parameters to reach consensus: the gossip communication and the periodic global averaging. Each of these two forces is possible to dominate the consensus controlling in different scenarios: Scenario I. Global averaging is more critical to guarantee consensus on large or sparse network, or when global averaging is conducted frequently.
Scenario II. Gossip communication is more critical to guarantee consensus on small or dense network, or when global averaging is conducted infrequently.
Ignoring either of the above scenario will lead to incomplete or even incorrect conclusions, as shown in Remark 5. In the following, we will establish a specific consensus lemma for each scenario and then unify them into one that precisely characterize how the consensus distance evolves with iterations in Gossip-PGA.
Lemma 2 (CONSENSUS LEMMA: GLOBAL AVERAGING DOMINATING). Under Assumptions 1-4, it holds for k = τ (k), τ (k) + 1, · · · , τ (k) + H − 1 that Observing Lemmas 2 and 3, it is found that bounds (22) and (23) are in the same shape except for some critical coefficients. With the following relation: we can unify Lemmas 2 and 3 into: , and D β = min{ 1 1−β , H}. Remark 8. This lemma reflects how the network topology and the global averaging period contribute to the consensus controlling. For scenario I where the network is large or sparse such that 1/(1 − β) > H, Lemma 4 indicates that the consensus error is mainly controlled by the global averaging period (i.e., D β = H). On the other hand, for scenario II where the network is small or dense such that 1/(1 − β) < H, Lemma 4 indicates that the consensus error is mainly controlled by gossip communication (i.e., D β = 1/(1 − β)).
Using Lemma 4, we derive the upper bound of the weighted running average of E x k −x k 2 F : Lemma 5 (RUNNING CONSENSUS LEMMA). Suppose Assumptions 1-4 hold and step-size γ < 1/(4LβD β ), it holds for T > 0 that where c 2 and c 3 are constants defined as With Lemmas 1 and 5, we can establish the final convergence Theorem 1, see the proof in Sec. B.5.

B.2. Proof of Lemma 1.
This lemma was first established in (Koloskova et al., 2020, Lemma 8). We made slight improvement to tight constants appeared in step-size ranges and upper bound (20). For readers' convenience, we repeat arguments here.
Recall the algorithm in (10). By taking the average on both sides, we reach that By taking expectation over the square of both sides of the above recursion conditioned on F (k−1) , we have Note that the first term can be expanded as follows.
We now bound the term (A): where (a) holds because of the inequality (15) and (17). We next bound term (B) in (31): Substituting (33) and (32) into (31), we have where the last inequality holds when γ < 1 4L . Substituting the above inequality into (30) and taking expectation over the filtration, we reach the result in (20).
To simplify the notation, we define Using these notations, we rewrite (22) for any k = 0, 1, 2, · · · that We next define By taking the running average over both sides in (48) and recalling A (τ (k)) = 0, it holds that We further define With these notations, we have where (a) holds because To guarantee 1 − c 1 D β ≥ 1 2 , it is enough to let γ ≤ 1/(4LβD β ).
B.5. Proof of Theorem 1 Following the notation in (47), we further define F (k) := E x (k) − x 2 F . With these notations, the inequality (20) becomes Taking weighted running average over the above inequality to get where the last inequality holds when γ ≤ 1/(12LβD β ). Substituting c 3 into the above inequality, we have The way to choose step-size γ is adapted from Lemma 15 in (Koloskova et al., 2020). For simplicity, we let and inequality (56) becomes Now we let γ = min C.1. Proof Outline for Theorem 2.
The proof outline for Theorem 2 is similar to that for Theorem 1. The descent lemma (Koloskova et al., 2020, Lemma 10) was established follows.

C.2. Proof of Lemma 6.
This lemma was first established in (Koloskova et al., 2020, Lemma 10). We made slight improvement to tight constants appeared in step-size ranges and upper bound (64). For readers' convenience, we repeat arguments here. Recall that where (a) holds because Note that and Substituting (72) and (73) into (70), taking expectations over F (k) and using the fact that γ < 1 4L , we reach the result in (64).

C.4. Proof of Lemma 8.
We first simplify the notation as follows: With these notations, we can follow the proof of Lemma 5 to get the final result.
Following the notation in (80), we further define F (k) := Ef (x (k) ). With these notations, the inequality (64) becomes Taking the weighted running average over the above inequality and divide T + 1 to get where the last inequality holds when γ ≤ 1 9LHβ . Substituting c 3 into the above inequality, we have By following the arguments (57) -(63), we reach the result in (8).
Hmax k=0 β k = C β , we follow Appendix C.3 and C.4 to reach the consensus distance inequality: where c 2 and c 3 are constants defined as and D β = min{1/(1 − β), H max }, C β = Hmax k=0 β k . With Lemma 6 and inequality (90), we can follow Appendix B.5 to reach the result in Corollary 1.
We implement all the aforementioned algorithms with PyTorch (Paszke et al., 2019) 1.5.1 using NCCL 2.5.7 (CUDA 10.1) as the communication backend. Each server contains 8 V100 GPUs in our cluster and is treated as one node. The inter-node network fabrics are chosen from 25 Gbps TCP (which is a common distributed training platform setting) and 4×100 Gbps RoCE (which is a high-performance distributed training platform setting).
All deep learning experiments are trained in the mixed precision using Pytorch extension package NVIDIA apex (https://github.com/NVIDIA/apex). For Gossip SGD related training, we use the time-varying one-peer exponential graph following (Assran et al., 2019). Workers send and receive a copy of the model's parameters to and from its peer, thus keeping the load balancing among workers. All data are stored in the cloud storage service and downloaded to workers using HTTP during training.

Image Classfication
The Nesterov momentum SGD optimizer is used with a linear scaling learning rate strategy. 32 nodes (each node is with 8 V100 GPUs) are used in all the experiments and the batch-size is set as 256 per node (8,192 in total). The learning rate is warmed up in the first 5 epochs and is decayed by a factor of 10 at 30, 60 and 90 epochs. We train 120 epochs by default (unless specified otherwise) in every experiment and record the epoch and runtime when a 76% top-1 accuracy in the validation set has reached. 25 Gbps TCP network is used for inter-node communication in ResNet-50 training. In 4×100 Gbps RoCE network, the communication overhead is negligible given the high computation-to-communication ratio nature of ResNet models and Parallel SGD with computation and communication pipeline is recommended. We use a period 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the averaging period is set to 4 in the warm-up stage and changed adaptively afterwards, roughly 9% iterations conduct global averaging.
Language Modeling All experiments are based on NVIDIA BERT implementation with mixed precision support and LAMB optimizer (You et al., 2019). 8 nodes are used in all the experiments with a batch-size 64 per GPU (4096 in total). We do not use gradient accumulation as it is not vertical with Local SGD. We only do phase 1 training and indicate the decreasing of training loss as convergence speed empirically. The learning rate is scaled to 3.75e −4 initially and decayed in a polynomial policy with warm-up. The phase 1 training consists of 112,608 steps in all experiments. We use a period 6 for both Local SGD and Gossip-PGA. In Gossip-AGA, the averaging period is set to 4 in the warm-up phase and changed adaptively afterwards, roughly 9.6% iterations conduct global averaging. O(θd + α) O(θd + √ nα) TRANSIENT TIME O(n 11 θd + n 11 α) O(n 5 θd + n 5.5 α) Table 13. Transient time comparison between Gossip SGD and Gossip-PGA for non-iid scenario over the specific ring (1 − β = O(1/n 2 )) topologiy. We choose H = √ n as the period in Gossip-PGA.
GOSSIP SGD GOSSIP-PGA O(θd + α) O(θd + √ nα) TRANSIENT TIME O(n 7 θd + n 7 α) O(n 4 θd + n 4.5 α) Table 14. Transient time comparison between Gossip SGD and Gossip-PGA for iid scenario over the specific ring (1 − β = O(1/n 2 )) topologiy. We choose H = √ n as the period in Gossip-PGA. In this subsection we will test the performance of Gossip-PGA with iid data distribution and on different topologies. We will also compare it with Local SGD.
Experiments on iid dataset. Figure 4 illustrates how Gossip SGD and Gossip-PGA converges under the iid data distributed setting over the ring topology. Similar to the non-iid scenario shown in Figure 1, it is observed that Gossip-PGA always converges faster (or has shorter transient stages) than Gossip SGD. When network size gets larger and hence β → 1, the superiority of Gossip-PGA gets more evident. Moreover, it is also noticed that the transient stage gap between Gossip SGD and Gossip-PGA is smaller than the non-iid scenario in all three plots in Figure 4. All these observations are consistent with the transient stage comparisons in Table 2.
Experiments on different topologies. Figure 5 illustrates how Gossip SGD and Gossip-PGA converges over the exponential graph, grid and ring topology. For all plots, it is observed that Gossip-PGA is no worse than Gossip SGD. Moreover, as the network gets sparser and hence β → 1 from the left plot to right, it is observed that the superiority of Gossip-PGA gets more evident, which is consistent with the transient stage comparisons between Gossip SGD and Gossip-PGA in Table 2.
Comparison with Local SGD. Figure 6 illustrates how Local SGD and Gossip-PGA converges over the exponential graph, grid and ring topology. The period is set as H = 16. In all three plots, Gossip-PGA always converges faster than Local SGD because of the additional gossip communications. Moreover, since the exponential graph has the smallest β, it is observed Gossip-PGA has almost the same convergence performance as parallel SGD. Figure 7 illustrates how Local SGD and Gossip-PGA converges over the grid topology with different periods. It is observed that Gossip-PGA can be significantly faster when H is large. All these observations are consistent with the transient stage comparisons in Table 3.

F.3. More experiments on image classification.
Training accuracy. Figure F.3 shows the iteration-wise and time-wise training accuracy curves of aforementioned algorithms separately. In the left figure, it is observed Gossip-PGA/AGA converges faster (in iteration) and more accurate than local and Gossip SGD, which is consistent with our theory. In the right figure, it is observed that Gossip-PGA/AGA is the fastest method (in time) that can reach the same training accuracy as parallel SGD.
The effect of averaging period.  Experiments on SGD optimizer (without momentum). In previous Imagenet training, Nesterov momentum SGD optimizer is used. Following common practice (Lian et al., 2017;Assran et al., 2019;Tang et al., 2018), we establish the convergence rate of the non-accelerated method while running experiments with momentum. For the sake of clarity, we further add a new series of experiments on Gossip-SGD without momentum, see Table 16. Gossip-PGA still outperform Gossip-SGD utilizing the SGD optimizer. G. Implementation of Gossip AGA Practical consideration. The Gossip-AGA algorithm is listed in Algorithm 2. We use a counter C to record the number of gossip iterations since last global averaging. The global averaging period H is initialized to a small value H init (e.g. 2∼4).
Once C equals to current H, global averaging happens. In practice, we sample loss scores for the first fewer iterations and get a F init estimation in a running-average fashion. We remove the exponential term in the loss score ratio for flexible period adjustment. Algorithm 2 Gossip-AGA Require: Initialize x 0,i = x 0 , learning rate γ > 0, topology matrix W for all nodes i ∈ {1, 2, ..., n}, global averaging period H = H init , C ← 0, F init ← 0, warmup iterations K w for k = 0, 1, 2, ..., T − 1, every node i do C ← C + 1 Sample mini-batch data ξ ) and loss