Conceptio › Archive › arXiv CS

arXiv CSopen access

Optimizing Stochastic Gradient Push under Broadcast Communications

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

arXiv:2604.15549v1 [cs.LG] 16 Apr 2026

Optimizing Stochastic Gradient Push under Broadcast Communications Tuan Nguyen

Ting He

Pennsylvania State University State College, PA, USA [email protected]

Abstract

1 Introduction

We consider the problem of minimizing the convergence time for decentralized federated learning (DFL) in wireless networks under broadcast communications, with focus on mixing matrix design. The mixing matrix is a critical hyperparameter for DFL that simultaneously controls the convergence rate across iterations and the communication demand per iteration, both strongly inﬂuencing the convergence time. Although the problem has been studied previously, existing solutions are mostly designed for decentralized parallel stochastic gradient descent (D-PSGD), which requires the mixing matrix to be symmetric and doubly stochastic. These constraints conﬁne the activated communication graph to undirected (i.e., bidirected) graphs, which limits design ﬂexibility. In contrast, we consider mixing matrix design for stochastic gradient push (SGP), which allows asymmetric mixing matrices and hence directed communication graphs. By analyzing how the convergence rate of SGP depends on the mixing matrices, we extract an objective function that explicitly depends on graph-theoretic parameters of the activated communication graph, based on which we develop an eﬃcient design algorithm with performance guarantees. Our evaluations based on real data show that the proposed solution can notably reduce the convergence time compared to the state of the art without compromising the quality of the trained model.

Decentralized federated learning (DFL) [14] is an emerging machine learning paradigm that allows distributed learning agents to collaboratively learn a shared model from the union of their local data without directly sharing the data or relying on centralized parameter servers. Compared to centralized federated learning (FL) [18], DFL agents directly exchange model updates with their neighbors, which leads to better robustness by avoiding a single point of failure and better load balancing by spreading the communication loads across nodes without increasing the computational complexity [14]. Meanwhile, DFL still faces signiﬁcant challenges in bandwidthlimited edge networks. In such networks, communication cost often dominates the total training cost [3], triggering the need to reduce the cost of repeated parameter sharing between learning agents without compromising convergence. The problem has attracted signiﬁcant attention from the research community, which proposed solutions that focused on either reducing the amount of data per communication through compression methods (e.g., [12]) or reducing the number of communications through hyperparameter optimization (e.g., [5, 9]) or adaptive communications (e.g., [20]). In this work, we focus on hyperparameter optimization by designing a critical hyperparameter called mixing matrix. Our solution can be combined with compression methods for further improvement. As a square matrix containing the weights used in local parameter aggregation, the mixing matrix plays a crucial role of controlling both the convergence rate in the number of iterations and the inter-agent communication demand per iteration, where each nonzero oﬀ-diagonal entry activates an inter-agent communication. While a denser mixing matrix can better approximate the ideal mixing matrix for perfect consensus and hence allows DFL to converge in fewer iterations, it also activates more inter-agent communications that increases the wall-clock time per iteration, causing a nontrivial tradeoﬀ. There is thus an active line of work on designing mixing matrices to minimize the total wall-clock time until convergence. Most existing works assumed simplistic measures of the communication time, e.g., the maximum degree [10, 13] or the minimum number of matchings [5, 28] of the activated communication graph. While proportional to the communication time in wired networks under certain assumptions (e.g., all communications take equal time), such simplistic measures cannot capture the communication time in wireless networks with broadcast communications. To our knowledge, this problem only started to be addressed recently in [9], which proposed design algorithms to minimize the total number of collision-free transmission slots until convergence. In this work, we consider mixing matrix design for

CCS Concepts • Computing methodologies → Distributed algorithms; Machine learning; • Mathematics of computing → Continuous optimization.

Keywords Decentralized federated learning, mixing matrix design, stochastic gradient push. ACM Reference Format: Tuan Nguyen and Ting He. 2026. Optimizing Stochastic Gradient Push under Broadcast Communications . In . ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnn Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for proﬁt or commercial advantage and that copies bear this notice and the full citation on the ﬁrst page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior speciﬁc permission and/or a fee. Request permissions from [email protected]. Conference’17, Washington, DC, USA © 2026 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-x-xxxx-xxxx-x/YYYY/MM https://doi.org/10.1145/nnnnnnn.nnnnnnn 1

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

rate (in #iterations) and the amount of communications per iteration. For D-PSGD [14], the impact of mixing matrices on the convergence rate is usually captured through the spectral gap [11, 14, 19] or equivalent parameters [5, 28, 34], although recent studies have pointed out additional parameters that can also aﬀect convergence, such as the eﬀective number of neighbors [26] and the neighborhood heterogeneity [13]. Based on the identiﬁed convergence parameters, several mixing matrix designs have been proposed to optimize the tradeoﬀ between the convergence rate and the cost per iteration for D-PSGD [5, 9, 10, 13, 28]. In comparison, the impact of mixing matrices on the convergence rate of SGP is less understood, where existing works only analyzed the convergence rate for given mixing matrices [2, 22, 35], but did not optimize the mixing matrices. This work ﬁlls the gap by addressing the mixing matrix design for SGP for the ﬁrst time, with the objective of minimizing the convergence time measured by the total number of transmission slots under collision-free constraints. While there are other training algorithms that allow asymmetric communications (e.g., stochastic push-pull [33] and push-diging [15]), we leave the mixing matrix design problem therein to future work.

minimizing the convergence time, measured by the total number of collision-free transmission slots as in [9], under broadcast communications. However, instead of using decentralized parallel stochastic gradient descent (D-PSGD) [14] as the learning algorithm as in [9], we adopt stochastic gradient push (SGP) [2], which allows asymmetric mixing matrices and hence directed inter-agent communications. Our solution is built upon a new convergence theorem for SGP that extracts the convergence impact of mixing matrices into an explicit function of simple graph-theoretical parameters of the activated communication graph, which then allows tractable algorithm design. To our knowledge, this is the ﬁrst work that addresses the optimization of mixing matrices for SGP.

1.1

Related Works

Decentralized federated learning. First explored by [14] through Decentralized Parallel Stochastic Gradient Descent (D-PSGD), DFL removes the central server in [18] and enables model training over peer-to-peer networks. Subsequent studies such as [17, 24, 31] advance DFL in both algorithms and theories, with the main focus on improving the convergence rate measured in #iterations. Communication cost reduction. There are two general approaches for reducing the communication cost: reducing the cost per communication through compression, e.g., [12, 16, 23], and reducing the number of communications, e.g., [25, 27, 29]. The two approaches can be combined for further improvement [20, 21]. Instead of either activating all the links or activating none, it has been observed that better performance can be achieved by activating suitable subsets of links. To choose such subsets, [20, 21] proposed an event-triggered mechanism and [5, 28] proposed to design randomized activation strategies with optimized probabilities. The latter approach was then extended to wireless networks by activating nodes instead of links under broadcast communications and interference constraints [9]. In this work, we aim at optimizing the activated communication topology under broadcast communications and interference constraints as in [9], with the objective of minimizing the total wall-clock time until convergence. While minimizing the convergence time has been studied in a number of works [5, 10, 13, 28], doing so in a wireless setting with broadcast communications and interference was only addressed recently in [9], which designed undirected (i.e., bidirected) communication graphs to minimize the total number of transmission slots under collisionfree constraints. We adopt the same objective as [9], but enlarge the solution space to arbitrary directed communication graphs by using SGP as the learning algorithm. As SGP uses the Push-Sum algorithm to correct bias [2], it allows asymmetric inter-agent parameter sharing, which is particularly beneﬁcial in wireless networks due to eﬀects like hidden terminals. As shown later (Section 6), the enlarged solution space allows our solution to reach the same level of convergence in fewer transmission slots than [9], under the same interference constraints. While a few other works have also considered broadcast-based DFL [4, 5, 34], they had diﬀerent objectives (e.g., maximizing #successful links [4] or minimizing the energy consumption [5, 34]). Mixing matrix design in DFL. The mixing matrix, i.e., the matrix containing the local aggregation weights, is a critical hyperparameter in DFL that controls the tradeoﬀ between the convergence

1.2 Summary of Contributions We consider the mixing matrix design for broadcast-based DFL via SGP, with the objective of minimizing the wall-clock time until convergence measured by the total number of collision-free transmission slots. Our contributions are: 1) We derive a new convergence theorem for SGP that explicitly summarizes the dependency of the number of iterations to reach convergence on the mixing matrices. 2) Based on the theorem, we extract a tractable objective for mixing matrix design as a closed-form function of several graphtheoretic parameters of the activated communication graph, including the maximum in/out-degree and the diameter. 3) Based on the extracted objective function, we develop an efﬁcient design algorithm that can construct a strongly-connected directed communication graph with guaranteed performance in terms of the objective value. 4) We evaluate the proposed solution against benchmarks based on real wireless network topology and training data. Our results show that eﬃciently utilizing asymmetric parameter sharing as in the proposed solution can notably reduce the convergence time (by 11–45%) compared to only using symmetric parameter exchanges as in existing works, without compromising the accuracy of the trained model. Roadmap. Section 2 provides background information and the problem formulation, Section 3 presents our convergence theorem, based on which Section 4 extracts a tractable design objective, Section 5 presents our design algorithm, Section 6 provides the performance evaluation, and Section 7 concludes the paper. All the proofs are provided in Appendix A.1–A.2.

2 Background and Problem Formulation 2.1 Learning Objective Consider a network of 𝑛 nodes connected via a base topology 𝐺 = (𝑉 , 𝐸), where 𝑉 is the set of nodes (|𝑉 | = 𝑛) and 𝐸 is the set of node pairs which can communicate directly. We assume that 𝐺 is 2

Optimizing Stochastic Gradient Push under Broadcast Communications

Conference’17, July 2017, Washington, DC, USA

However, the requirement of symmetry signiﬁcantly restricts the ﬂexibility in mixing matrix design. From a communication per(𝑡 ) (𝑡 ) spective, requiring𝑊𝑖 𝑗 = 𝑊 𝑗𝑖 means that node 𝑖 needs to send its parameter vector to node 𝑗 whenever it wants to include 𝑗’s parameter vector in its local parameter aggregation. Referring to setting 𝑊𝑖(𝑡𝑗 ) ≠ 0 as activating (directed) link ( 𝑗, 𝑖), this means symmetric mixing matrix design can only activate links at the granularity of bidirected pairs {(𝑖, 𝑗), ( 𝑗, 𝑖)}, which limits the solution space.

bidirected, i.e., (𝑖, 𝑗) ∈ 𝐸 if and only if ( 𝑗, 𝑖) ∈ 𝐸; we also assume each node to have a self-loop to indicate its access to local information. Each node 𝑖 ∈ 𝑉 is associated with a (possibly non-convex) local objective function 𝑓𝑖 (𝒙), which is a function of the parameter 𝒙 ∈ R𝑑 and the local dataset at node 𝑖. The objective of DFL is to collaboratively minimize the global objective function 1Õ 𝑓𝑖 (𝒙), 𝑛 𝑖=1 𝑛

𝑓 (𝒙) :=

(1)

2.2.2 SGP. To remove the above limitation, we consider a diﬀerent learning algorithm called Stochastic Gradient Push (SGP) [2]. The diﬃculty with asymmetric mixing matrices is that it is often impossible to converge towards global averaging through mixing alone. Fortunately, this problem can be addressed by an algorithm called Push-Sum, which only requires the mixing matrices to be column-stochastic (i.e., each column sums to one), but not necessarily symmetric. For such matrices, it is still possible to ensure conÎ vergence lim𝐾→∞ 𝑡𝐾=0 𝑾 (𝑡 ) = 𝝅1⊤ for some probability vector 𝝅 under mild conditions, but 𝜋𝑖 may not equal 1/𝑛 (∀𝑖 ∈ 𝑉 ), causing a bias in the averaging. Push-Sum solves this problem by maintaining an additional scalar parameter 𝑤𝑖(𝑡 ) at each node 𝑖, with the initial value 𝑤𝑖(0) = 1. The update equation changes from (2) to

which averages the local objectives across all nodes. Remark: Bidirected (or equivalently undirected) base topology is a common assumption in DFL. We inherit this assumption in this work (which allows us to orient activated links arbitrarily as in Alg. 1), and leave the case of arbitrary directed base topology to future work.

2.2

Learning Algorithms

2.2.1 D-PSGD and its Limitation. Decentralized learning algorithms typically work by combining local stochastic gradient descent with decentralized approximations of cross-node parameter averaging. In a commonly-used algorithm known as Decentralized Parallel Stochastic Gradient Descent (D-PSGD) [14], this combination leads to an iterative algorithm which performs the following update in parallel at every node 𝑖: 𝒙𝑖(𝑡 +1) =

𝑛 Õ 𝑗=1

𝑊𝑖 (𝑡𝑗 ) (𝒙 𝑗(𝑡 ) − 𝜂𝑔 𝑗 (𝒙 𝑗(𝑡 ) ; 𝜉 𝑗(𝑡 ) )),

𝒙 (𝑡 ) 𝑗 © ª 𝑊𝑖 (𝑡𝑗 ) 𝒙 𝑗(𝑡 ) − 𝜂𝑔 𝑗 (𝑡 ) ; 𝜉 𝑗(𝑡 ) ® , 𝑤𝑗 𝑗=1 « ¬ 𝑛 Õ 𝑤𝑖(𝑡 +1) = 𝑊𝑖 (𝑡𝑗 ) 𝑤 𝑗(𝑡 ) , 𝒙𝑖(𝑡 +1) =

(2)

Here 𝒙𝑖(𝑡 ) denotes the model parameter vector at node 𝑖 at the start (𝑡 ) (𝑡 ) of iteration 𝑡, 𝑔(𝒙𝑖 ; 𝜉𝑖 ) denotes the stochastic gradient computed at that node using a minibatch 𝜉𝑖(𝑡 ) drawn from its local data, 𝜂 > 0 𝑛 is the 𝑛×𝑛 mixing denotes the learning rate, and 𝑾 (𝑡 ) = (𝑊𝑖(𝑡𝑗 ) )𝑖,𝑗=1 matrix used for parameter aggregation at iteration 𝑡, which should be topology-compliant (i.e., 𝑊𝑖 (𝑡𝑗 ) ≠ 0 only if ( 𝑗, 𝑖) ∈ 𝐸). The mixing matrix plays a crucial role in the learning performance. On one hand, since node 𝑖 requires communication from node 𝑗 in iteration 𝑡 only if 𝑊𝑖 (𝑡𝑗 ) ≠ 0, the mixing matrix controls the communication pattern and hence the communication cost. On the other hand, the mixing matrix also controls the convergence rate. According to [14], the mixing matrix should be symmetric and doubly stochastic, which simpliﬁes its design. For example, if all iterations use the same deterministic mixing matrix 𝑾, then having a positive spectral gap, i.e.,1 𝜌 := max(|𝜆2 (𝑾)|, |𝜆𝑛 (𝑾)|) < 1,

(4) (5)

𝑗=1

where 𝑤𝑖(𝑡 ) tracks the cumulative bias and 𝒛𝑖(𝑡 ) := 𝒙𝑖(𝑡 ) /𝑤𝑖(𝑡 ) is the de-biased parameter used in gradient computation. Compared to (2), the SGP update only requires the communication of one extra scalar 𝑤 𝑗(𝑡 ) for each 𝑊𝑖 (𝑡𝑗 ) ≠ 0, which incurs negligible cost compared to the communication of parameter vector, but it allows mixing matrix design to activate directed links individually, i.e., allowing 𝑊 𝑗𝑖(𝑡 ) = 0 while 𝑊𝑖(𝑡𝑗 ) ≠ 0. As shown later, such increased ﬂexibility can lead to notably better cost-convergence tradeoﬀ.

2.3 Assumptions for Convergence

Í Let 𝒙 (𝑡 ) := 𝑛1 𝑛𝑖=1 𝒙𝑖(𝑡 ) denote the learned global model at iteration 𝑡, i.e., a global average of local models at this iteration. As the objective function 𝑓 is often non-convex for deep learning, the convergence criterion is based on gradient norm: for any required level of convergence 𝜖 > 0, we say that SGP achieves 𝜖-convergence if2

(3)

1Õ E[k∇𝑓 (𝒙 (𝑡 ) )k 2 ] ≤ 𝜖, 𝑇 𝑡 =0

is suﬃcient to ensure that the cumulative eﬀect of local averaging weighted by 𝑾 converges to the eﬀect of global averaging with uniform weights, i.e., lim𝑡 →∞ 𝑾 𝑡 = 𝑛1 11⊤ , which leads to a guaranteed convergence for D-PSGD [14]. Moreover, the smaller the 𝜌-parameter, the faster the convergence. This observation has inspired a line of works on mixing matrix design for D-PSGD [5, 9, 10, 13, 28], which aim at optimizing the cost-convergence tradeoﬀ by designing mixing matrices to minimize 𝜌 or equivalent parameters under a budget on the cost per communication round. 1 Here 𝜆 (𝑾 ) denotes the 𝑖 -th largest eigenvalue of 𝑾 . 𝑖

𝑛 Õ

𝑇 −1

(6)

which ensures the learned model to be suﬃciently close to a local minimum of the global objective function. −1 , we use 𝐸 (𝑡 ) := {( 𝑗, 𝑖) ∈ 𝐸 : Given mixing matrices (𝑾 (𝑡 ) )𝑡𝑇=0 (𝑡 ) 𝑊𝑖 𝑗 ≠ 0} to denote the set of links activated at iteration 𝑡, and 𝛿 2 In this work, we use k𝒂 k to denote ℓ -2 norm if 𝒂 is a vector, and spectral norm if 𝒂 is a matrix.

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

2.5 Design Objective

to denote the minimum nonzero mixing weight, deﬁned as 𝛿 := min 𝑡

min

(𝑡 )

( 𝑗,𝑖 ):𝑊𝑖 𝑗 >0

𝑊𝑖 (𝑡𝑗 ) .

Generally, mixing matrix design faces an inherent tradeoﬀ between (i) communicating more per iteration in order to converge in fewer iterations and (ii) communicating less per iteration at the cost of converging in more iterations. To accelerate learning, we aim at de−1 to minisigning possibly time-varying mixing matrices (𝑾 (𝑡 ) )𝑡𝑇=0 mize the total number of transmission slots, i.e.,

(7)

The convergence of SGP can be guaranteed under the following assumptions: (1) (𝐿-smooth) Each local objective function 𝑓𝑖 (𝒙) is 𝐿-Lipschitz smooth, i.e., k∇𝑓𝑖 (𝒙) − ∇𝑓𝑖 (𝒙 ′ )k ≤ 𝐿 k𝒙 − 𝒙 ′ k, ∀𝒙, 𝒙 ′ ∈ R𝑑 . (2) (Bounded variance) There exists a constant 𝜎 2 such that E[k𝑔𝑖 (𝒙; 𝜉) − ∇𝑓𝑖 (𝒙)k 2 ] ≤ 𝜎 2 , ∀𝑖 and ∀𝒙 ∈ R𝑑 . (3) (Bounded heterogeneity) There exists a constant 𝜁 such that 2 1 Í𝑛 2 𝑑 𝑖=1 k∇𝑓𝑖 (𝒙) − ∇𝑓 (𝒙)k ≤ 𝜁 , ∀𝒙 ∈ R . 𝑛 (4) (Mixing connectivity) There exist ﬁnite positive integers 𝐵 Ð and Δ, such that the graph (𝑉 , 𝑡(𝑙+1)𝐵−1 𝐸 (𝑡 ) ) is strongly =𝑙𝐵 connected with diameter at most Δ for every 𝑙 ∈ N.

min

𝑇Õ −1

−1 (𝑾 (𝑡 ) )𝑡𝑇=0 𝑡 =0

𝜏 (𝐺 (𝑡 ) ),

(8)

until SGP reaches 𝜖-convergence for a given 𝜖 > 0.

2.6 Motivating Experiment Center node Other nodes Undirected link

Center node Cluster head Other nodes Bidirected active link Directed active link

The same assumptions were made in [2, 35]. While SGP can be extended to guarantee convergence under bounded communication delays [2], we assume the synchronized version as deﬁne in (4)–(5) in this work to focus on mixing matrix design. (a) Base topology

Cost Model

(b) Activated graph for SGP

Figure 1: Topology for motivating experiment: each undirected link in (a) represents two directed links in opposite directions; (b) contains all the links in (a), except that only one node per cluster (highlighted) communicates to the hub.

We focus on communication time as the cost measure, which usually dominates the computation time in decentralized settings and determines the overall convergence time. Speciﬁcally, let 𝐺 (𝑡 ) = (𝑉 , 𝐸 (𝑡 ) ) denote the activated communication graph at iteration 𝑡 and 𝜏 (𝐺 (𝑡 ) ) denote the required number of transmission slots to complete the activated parameter transmissions. We use 𝜏 (𝐺 (𝑡 ) ) to measure the cost of iteration 𝑡, assuming one transmission slot as the time to complete a set of parallel parameter transmissions under a feasible communication schedule. We assume that each node has a half-duplex omnidirectional transceiver capable of broadcasting to all neighbors or receiving from one neighbor in any slot. Two directed links (𝑖, 𝑗) and (𝑘, 𝑙) can be scheduled in the same slot if and only if they satisfy

0.6

Testing Err r

Training L sses

0.8

0.01

0.005

Training L sses

0.003

(1) (Half-duplex constraint) 𝑖 ≠ 𝑙 and 𝑗 ≠ 𝑘, and (2) (Interference constraint) (𝑖, 𝑙), (𝑘, 𝑗) ∉ 𝐸 if 𝑖 ≠ 𝑘. This is consistent with the communication model in [9] and [32]. Under the above assumption, we can construct a conﬂict graph of the activated links, denoted by 𝐺𝑐(𝑡 ) = (𝐸 (𝑡 ) , 𝐶 (𝑡 ) ), where (𝑖, 𝑗), (𝑘, 𝑙) ∈ 𝐶 (𝑡 ) if and only if the links (𝑖, 𝑗) and (𝑘, 𝑙) cannot be scheduled in the same slot. Then 𝜏 (𝐺 (𝑡 ) ) is given by the minimum number of vertex-independent sets in 𝐺𝑐(𝑡 ) whose union covers all its vertices, i.e., the chromatic number of the conﬂict graph. Remark: While the above model does not explicitly consider runtime dynamics such as transmission failures and retransmissions caused by noise or external interference, it can incorporate the mean eﬀect of such dynamics by interpreting one transmission slot as the average time to successfully complete a set of parallel parameter transmissions under constraints (1–2). Moreover, while the above model implicitly assumes the interference graph to be the same as the connectivity graph (i.e., 𝐺), this assumption can be easily relaxed by deﬁning the interference constraint according to a separate interference graph, and our solution still applies.

0.4

0.2

0.15

20000 40000 60000 80000 100000 120000

Total transmissi n sl ts

20000 40000 60000 80000 100000 120000

T tal transmissi n sl ts

0.8 0.6

Testing Err r

2.4

0.01

0.005 0.003

0.4

0.2

0.15

Ep chs

Vanilla D-PSGD

Vanilla SGP

BASS

Ep chs

SGP designed

Figure 2: Motivating experiment based on FMNIST over the topology in Fig. 1 (23 slots per iteration for ‘BASS’ and ‘SGP designed’). As a motivating example, we compare the convergence performance of state-of-the-art solutions and SGP based on a designed mixing matrix. Our experiment is based on the FMNIST dataset [30], randomly distributed across the 61 nodes in a (3,21)-windmill graph shown in Fig. 1a, which contains three 21-node cliques sharing a common node. For example, this can model a wireless network with partitioned dense clusters bridged by a hub with line-of-sight links to all the other nodes. The learning task is to train a 4-layer CNN with 1,663,370 parameters as in [18], with a batch size of 64 4

Optimizing Stochastic Gradient Push under Broadcast Communications

Conference’17, July 2017, Washington, DC, USA

and a learning rate of 0.02. We evaluate four solutions: (1) ‘Vanilla D-PSGD’ using the base topology as the communication graph (i.e., all neighbors communicate) and Metropolis-Hastings weights; (2) ‘Vanilla SGP’ using the base topology as the communication graph and column-wise uniform weights (i.e., equally spitting the unit weight of each column among the out-neighbors); (3) ‘BASS’ [9], a state-of-the-art mixing matrix design for D-PSGD under broadcast communications (based on ‘heuristic design’); (4) ‘SGP designed’, which is SGP based on the communication graph in Fig. 1b and column-wise uniform weights. This design activates all the directed links in the base topology, except for the incoming links to the hub from all but one node in each cluster (which functions as a “cluster head” to share information with other clusters through the hub). This is the design produced by our proposed algorithm (Alg. 1); see Fig. 3e for the detailed explanations based on a simpler topology of the same type. The results, shown in Fig. 2, suggest that: (i) while communicating according to the base topology as in ‘Vanilla D-PSGD/SGP’ is good for maximizing the convergence rate measured in epochs, using a sparser communication graph like ‘BASS’ or ‘SGP designed’ can achieve faster convergence in wall-clock time (measured in slots), and (ii) suitably utilizing the asymmetric parameter sharing capability of SGP can substantially reduce the convergence time compared to the state-of-the-art designs based on D-PSGD (speciﬁcally, ‘SGP designed’ reduces the convergence time by 40% compared to ‘BASS’ and 62% compared to ‘Vanilla DPSGD/SGP’ in achieving 85% testing accuracy).

Remark: In large-scale learning, the minimum mixing weight 𝛿 is usually small and the diameter Δ of the activated communication graph is usually large, implying that 𝛿 Δ𝐵 ≪ 1, 𝐶 ≫ 1, and 1 − 𝑞 ≪ 1. Thus, the condition (9) holds easily. In this case, Corollary 3.2 states that the number of iterations till convergence only depends on mixing matrices through: the number of iterations 𝐵 to reach strong connectivity, the diameter Δ of the communication graph over 𝐵 iterations, and the minimum mixing weight 𝛿, in the form of (10).

4 Simpliﬁcation of Design Objective The clean bound in Corollary 3.2 provides us an explicit objective function for mixing matrix design. Considering periodic mixing matrix design, where 𝑾 (𝑙𝐵+𝑡 ) = 𝑾 (𝑡 ) for all 𝑙 ∈ N and 𝑡 ∈ {0, . . . , 𝐵 − 1}, our goal is to design 𝐵 mixing matrices (𝑾 (𝑡 ) )𝑡𝐵−1 =0 with the corresponding activated graphs (𝐺 (𝑡 ) )𝑡𝐵−1 =0 , such that the total number of transmission slots, given by 𝐵−1 Õ 𝑇 𝐵−1 Δ2𝐵 Õ 𝜏 (𝐺 (𝑡 ) ) ∝ 4Δ𝐵 𝜏 (𝐺 (𝑡 ) ), 𝐵 𝑡 =0 𝛿 𝑡 =0

(11)

is minimized. However, directly optimizing (11) is intractable as it mixes topology design with weight design and involves an unknown number of topologies. Below, we will simplify this objective into a more tractable objective function to facilitate a solution.

4.1 Optimal Weight Assignment As the objective (11) depends on mixing weights only through the minimum weight 𝛿, it is easy to show that uniform weight assignment, i.e., equally splitting the unit weight of each column among the activated out-neighbors, is optimal. Speciﬁcally, given an activated graph 𝐺 (𝑡 ) , we deﬁne the activated out-neighborhood of node 𝑗 (excluding the self-loop) as:

Convergence Analysis

While the convergence of SGP has been analyzed in [2, 22, 35], the existing convergence bounds have multi-term, highly complicated dependencies on the mixing matrices, which fail to provide a tractable objective for mixing matrix design. To ﬁll this gap, we derive a new convergence bound for SGP based on the assumptions in Section 2.3 as follows.

𝑁𝑡+ ( 𝑗) := { 𝑖 ∈ 𝑉 \ { 𝑗 } : ( 𝑗, 𝑖) ∈ 𝐸 (𝑡 ) },

Theorem 3.1. Let 𝐴 := 2𝑓 (𝒙 (0) )−2𝑓 ∗ +𝐿𝜎 2 and 𝑆 := (max𝑖 ∈𝑉 𝒙𝑖(0) ) 2 p (1)–(4) in +𝑛 2𝜎 2 + 3𝑛 2𝜁 2 . SGP with 𝜂 = 𝑛/𝑇 under assumptions 2 1 Í𝑇 −1 Section 2.3 achieves 𝜖-convergence (i.e., 𝑇 𝑡 =0 E ∇𝑓 (𝒙 (𝑡 ) ) ≤ 2 2

24𝐿 𝐶 𝜖) if the number of iterations 𝑇 satisﬁes T ≥ (1−𝑞) 2 𝜖 𝑆 for any 𝜖 satisfying 2(1 − 𝑞) 2𝐴2 4𝑆 24𝐿2𝐶 2𝑆 , (9) ≤ 𝜖 ≤ min , 3𝐿2𝐶 2𝑛𝑆 3𝑛 2 𝑛(1 − 𝑞) 2

and the activated out-degree as 𝑑𝑡+ ( 𝑗) := |𝑁𝑡+ ( 𝑗)|. We have the following observation. Lemma 4.1. Under given activated graphs (𝐺 (𝑡 ) )𝑡𝐵−1 =0 and columnstochastic mixing, the conditionally optimal value of 𝛿 is 1 , (12) max 𝛿 = min min 𝑡 ∈ {0,...,𝐵−1} 𝑗 ∈𝑉 𝑑𝑡+ ( 𝑗) + 1 (𝑡 )

achieved when 𝑊𝑖 𝑗 ( 𝑗, 𝑖) ∈ 𝐸 (𝑡 ) .

(𝑡 )

= 𝑊𝑗 𝑗

= 1/(𝑑𝑡+ ( 𝑗) + 1) for all 𝑗 ∈ 𝑉 and

Remark: Lemma 4.1 implies that once the activated graphs are given, it suﬃces to simply assign mixing weights to the activated links uniformly as in Lemma 4.1.

4 and 𝑞 := (1 − 𝛿 Δ𝐵 ) Δ𝐵 are the only parameters where 𝐶 := 𝛿 Δ𝐵

depending on mixing matrices, 𝒙𝑖(0) is the initial parameter vector at node 𝑖, and 𝑓 ∗ is the optimal objective value.

4.2 Optimal Period Length

Corollary 3.2. For 𝛿 Δ𝐵 ≪ 1 and 𝜖 satisfying (9), SGP under assumptions (1)–(4) in Section 2.3 achieves 𝜖-convergence when the number of iterations 𝑇 reaches 2 2 24𝐿2𝐶 2 Δ𝐵 𝑆 = 𝑂 𝑇 := , (10) (1 − 𝑞) 2𝜖 𝛿 4Δ𝐵 where the big-𝑂 notation hides input parameters independent of the mixing matrices. 5

We will further show that instead of considering all the possible periods, it suﬃces to consider the special case of 𝐵 = 1, i.e., all the iterations use the same activated graph for parameter sharing. Ð (𝑡 ) ) denote the per-period activated graph. Let 𝐺𝑎 := (𝑉 , 𝑡𝐵−1 =0 𝐸 We will use the following graph-theoretic notions in our derivation: • 𝑑𝑎+ ( 𝑗) and 𝑑𝑎− ( 𝑗) denote the out/in-degree of node 𝑗 in 𝐺𝑎 ;

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

• 𝐷𝑎+ and 𝐷𝑎− denote the maximum out/in-degree of 𝐺𝑎 . First, we show that for a given 𝐺𝑎 and a given 𝐵 ≥ 1, splitting the outgoing links in 𝐺𝑎 at the node with the maximum outdegree evenly among the 𝐵 iterations helps to optimize the minimum weight 𝛿.

Base on Brooks’ Theorem [6], the conﬂict graph 𝐺𝑐 can be colored with at most 𝐷𝑐 colors except for two cases, complete graphs and cycle graphs of odd length, which require 𝐷𝑐 + 1 colors. Hence, we always have

Lemma 4.2. Given the period 𝐵 and the per-period activated graph 𝐺𝑎 , we have that 1 . (13) max 𝛿 ≤ ⌈𝐷𝑎+ /𝐵⌉ + 1

What remains is to connect 𝐷𝑐 to the structure of 𝐺𝑎 , which will depend on the speciﬁc communication model. Under the broadcast communication model assumed in Section 2.4, two links (𝑖, 𝑗) and (𝑘, 𝑙) conﬂict if and only if they violate the halfduplex constraint or the interference constraint, which leads to the following bound on 𝐷𝑐 .

𝜏 (𝐺𝑎 ) = 𝜒 (𝐺𝑐 ) ≤ 𝐷𝑐 + 1.

Plugging the bound in (13) into (11) yields a lower bound on the objective in (11) under period length 𝐵, denoted by + 4Δ𝐵 𝐵−1 Õ 𝐷𝑎 𝜏 (𝐺 (𝑡 ) ) Δ2 𝐵 𝐹 (𝐵) := +1 . (14) 𝐵 𝑡 =0

Lemma 4.4. Under the communication model assumed in Section 2.4, the maximum degree of the conﬂict graph is bounded by 𝐷𝑐 ≤ (𝐷 + 1) 𝐷𝑎+ + 𝐷𝑎− . (18)

Next, we show that this lower bound is minimized at 𝐵 = 1.

4.4 Closed-form Design Objective

Lemma 4.3. Given a graph 𝐺𝑎 = (𝑉 , 𝐸𝑎 ) to be activated over a 𝐵-iteration period, 𝐹 (𝐵) deﬁned in (14) satisﬁes 𝐹 (𝐵) ≥ 𝐹 (1) = 𝜏 (𝐺𝑎 )Δ2 (1 + 𝐷𝑎+ ) 4Δ

(17)

Combining (17) and (18) yields a per-iteration cost bound of 𝜏 (𝐺𝑎 ) ≤ (𝐷 + 1)(𝐷𝑎+ + 𝐷𝑎− ) + 1 ≤ 2(𝐷 + 1)(𝐷𝑎+ + 𝐷𝑎− ).

(15)

Replacing 𝜏 (𝐺𝑎 ) in (16) by this upper bound leads to a new design objective: (19) min 𝐷𝑎+ + 𝐷𝑎− Δ2 (1 + 𝐷𝑎+ ) 4Δ ,

for any integer 𝐵 ≥ 1 and any 𝐺 (𝑡 ) = (𝑉 , 𝐸 (𝑡 ) ) (𝑡 ∈ {0, . . . , 𝐵 − 1}) Ð (𝑡 ) = 𝐸 . such that 𝑡𝐵−1 𝑎 =0 𝐸

𝐺𝑎

Given a per-period activated graph 𝐺𝑎 = (𝑉 , 𝐸𝑎 ), activating all the links in 𝐺𝑎 in the same iteration and assigning weights uniformly achieve the lower bound on the objective function (11) given by (15). This observation greatly simpliﬁes our mixing matrix design problem from designing 𝐵 𝑛 × 𝑛 matrices to designing a single graph 𝐺𝑎 that connects all the nodes in 𝑉 , with the objective of

which is an explicit, easily computable function of the activated communication graph 𝐺𝑎 that only depends on 𝐺𝑎 through three of its graph-theoretic parameters: the maximum in-degree 𝐷𝑎− , the maximum out-degree 𝐷𝑎+ , and the diameter Δ.

5 Communication Graph Design

after which we can construct a mixing matrix 𝑾 via uniform weight assignment as in Section 4.1 to use in each iteration.

The simpliﬁed objective (19) reduces our mixing matrix design problem to a graph-theoretic problem of constructing a directed subgraph of 𝐺 to minimize (19), subject to the strong connectivity constraint imposed by assumption (4) in Section 2.3.

4.3

5.1 Design Algorithm

min 𝜏 (𝐺𝑎 )Δ (1 + 𝐷𝑎+ ) 4Δ , 𝐺𝑎

(16)

Computable Cost Bound

While our problem has an application-speciﬁc objective function (19) diﬀerent from the objectives of classical graph algorithms, the need of optimizing the graph-theoretic parameters 𝐷𝑎+ , 𝐷𝑎− , and Δ motivates a 4-step algorithm as shown in Alg. 1. We will leverage the following notions from graph theory. We use “edge” to refer to an undirected link and “link” to refer to a directed link.

The main diﬃculty in optimizing the new objective (16) is that the per-iteration communication cost 𝜏 (𝐺𝑎 ) is not an explicit function of 𝐺𝑎 and is diﬃcult to evaluate. In fact, for the cost model considered in Section 2.4, even evaluating 𝜏 (𝐺𝑎 ) for a given 𝐺𝑎 is NP-hard: by deﬁnition, 𝜏 (𝐺𝑎 ) is the chromatic number of the conﬂict graph of 𝐺𝑎 , which is NP-hard to compute [8]. This motivates us to relax 𝜏 (𝐺𝑎 ) into a computable bound that explicitly depends on the structure of 𝐺𝑎 . Let 𝐺𝑐 = (𝐸𝑎 , 𝐶𝑎 ) denote the conﬂict graph of 𝐺𝑎 , where each vertex denotes an activated link and each edge (𝑖, 𝑗), (𝑘, 𝑙) ∈ 𝐶𝑎 denotes a scheduling conﬂict3 . Let 𝜒 (𝐺𝑐 ) denote the chromatic number of 𝐺𝑐 , which by deﬁnition equals 𝜏 (𝐺𝑎 ). We will use a few more graph-theoretic notions in the following derivation: • 𝐷𝑐 denotes the maximum degree of the conﬂict graph 𝐺𝑐 (note that 𝐺𝑐 is undirected); • 𝐷 denotes the maximum in/out-degree of the base topology 𝐺 (note that the maximum in-degree equals the maximum out-degree as 𝐺 is bidirected).

Deﬁnition 1. Given an undirected graph 𝐻 = (𝑉 (𝐻 ), 𝐸 (𝐻 )), • a minimum-degree spanning tree 𝑇 of 𝐻 is a spanning tree of 𝐻 that minimizes the maximum node degree; • a bridge (a.k.a. cut edge) of 𝐻 is an edge in 𝐸 (𝐻 ) whose removal will increase the number of connected components, and a bridge-connected component of 𝐻 is a maximal subgraph not containing any bridge; • the preorder number 𝑝𝑟𝑒 (𝑣) of a vertex 𝑣 in 𝐻 is the order in {1, . . . , |𝑉 (𝐻 )|} that 𝑣 is ﬁrst visited by a depth-ﬁrst search (DFS) of 𝐻 from some root vertex. Step 1: Construct a minimum-degree spanning tree. Motivated by the need to achieve connectivity with the minimum degrees, we start with the minimum-degree spanning tree of the base

3 We use “edge” to refer to an undirected link in the graph-theoretic sense.

Optimizing Stochastic Gradient Push under Broadcast Communications

Conference’17, July 2017, Washington, DC, USA

topology. However, since existing algorithms for constructing (approximate) minimum-degree spanning trees are designed for undirected graphs, we initially construct a spanning tree for the undirected version of the base topology (denoted by 𝐺𝑢 ), which will be converted into a directed graph later (Step 3). Step 2: Add 𝐾 extra edges based on distance. Motivated by the need to minimize the diameter (i.e., the maximum distance between any two nodes), we add extra edges to connect nodes with the maximum distance, under connectivity constraints speciﬁed by the base topology. Since adding edges may increase the maximum degree, we use a design parameter 𝐾 to control this tradeoﬀ, which can be optimized according to our design objective (16) or (19). Step 3: Orient the edges. Using the connected undirected graph from Steps 1–2 as a basis, we construct a directed communication graph 𝐺𝑎 by orienting the edges. Edges inside each bridgeconnected component are oriented according to preorder numbers (lines 12–16): edges in the DFS tree are oriented in ascending preorder numbers (parent-to-child edges); edges not in the DFS tree are oriented in descending preorder numbers (back edges). We will show that such orientation turns each bridge-connected component into a strongly connected subgraph. Then we connect these components with bidirected links (line 17) to form a strongly connected graph 𝐺𝑎 . Step 4: Cost-preserving link augmentation. It is possible that there are directed links not selected in Steps 1–3 that can also be activated without increasing the per-iteration communication cost. That is, given a feasible communication schedule for the 𝐺𝑎 constructed so far as a slot assignment S = {𝑆 1, . . . , 𝑆𝜏 } (where each 𝑆𝑡 is a subset of the activated links that can be scheduled in the same slot without conﬂict), there may be other links that can be added to the schedule without causing conﬂict or increasing the schedule length. Intuitively, adding such links to 𝐺𝑎 will further accelerate convergence without costing more time per iteration. Thus, we augment 𝐺𝑎 with such non-conﬂicting links, prioritizing the link that minimizes the factor Δ2 (1 + 𝐷𝑎+ ) 4Δ in our design objective that represents the iteration count (line 22). However, since adding links to 𝐺𝑎 may degrade Δ2 (1 + 𝐷𝑎+ ) 4Δ due to the potential increase in 𝐷𝑎+ , we record the objective value achieved by Step 3 (line 20) and only add a non-conﬂicting link if it will not make the objective value worse (lines 23–26).

5.2

Algorithm 1: Communication Graph Design for SGP input : A bidirected base topology 𝐺 = (𝑉 , 𝐸 ) and its undirected version 𝐺𝑢 = (𝑉 , 𝐸𝑢 ), #added edges 𝐾 output :A strongly connected communication graph 𝐺𝑎 for SGP 1 2

Step 1: Construct a minimum-degree spanning tree; Compute a (possibly approximate) minimum-degree spanning tree 𝑇 of 𝐺𝑢 , with edges 𝐸 (𝑇 );

Step 2: Add 𝐾 extra edges based on distance; for 𝑘 = 1 to 𝐾 do 5 Select (𝑢 ★, 𝑣★ ) ∈ 𝐸𝑢 \ 𝐸 (𝑇 ) with the maximum distance between 𝑢 ★ and 𝑣★ in 𝑇 ; 6 Add edge (𝑢 ★, 𝑣★ ) to 𝑇 ;

3 4

Step 3: Orient the edges; Decompose 𝑇 into bridge-connected components, denoted by C, connected by bridges 𝐸𝑏 ; 9 Initialize an empty digraph 𝐺𝑎 on the vertex set 𝑉 ; 10 foreach bridge-connected component 𝐶 ∈ C do 11 Perform DFS on 𝐶 from any vertex to compute a DFS tree 𝑇𝐶 and a preorder number 𝑝𝑟𝑒 (·) for each vertex in 𝐶; 12 foreach edge (𝑢, 𝑣) in 𝐶 with 𝑝𝑟𝑒 (𝑢 ) < 𝑝𝑟𝑒 (𝑣) do 13 if (𝑢, 𝑣) is in 𝑇𝐶 then 14 Add directed link (𝑢, 𝑣) to 𝐺𝑎 ; 15 else 16 Add directed link (𝑣, 𝑢 ) to 𝐺𝑎 ; 17 Add the directed links in both directions for each bridge in 𝐸𝑏 to 𝐺𝑎 ; 7

Step 4: Cost-preserving link augmentation; Compute a feasible communication schedule for 𝐺𝑎 in terms of slot assignment S = {𝑆 1, . . . , 𝑆𝜏 }; 20 Compute 𝛾 ← Δ2 (1 + 𝐷𝑎+ ) 4Δ ; 21 while ∃a candidate link 𝑒 in 𝐸 \ 𝐸 (𝐺𝑎 ) that can be added to the schedule S without conﬂict do 22 Select the non-conﬂicting candidate link 𝑒 ∗ that will minimize Δ2 (1 + 𝐷𝑎+ ) 4Δ if added to 𝐺𝑎 ; 23 if adding 𝑒 ∗ to 𝐺𝑎 will make Δ2 (1 + 𝐷𝑎+ ) 4Δ ≤ 𝛾 then 24 Add 𝑒 ∗ to 𝐺𝑎 and assign it to a non-conﬂicting slot; 25 else 26 Break; 27 return 𝐺𝑎 ;

18 19

Algorithm Analysis

5.2.1 Performance Analysis. Alg. 1 is guaranteed to provide a feasible solution with guaranteed performance in terms of our design objective, as stated below.

this case, the performance guarantee in Theorem 5.1 still holds, except that 𝐷 ∗ and Δ∗ denote the maximum degree and diameter of the spanning tree constructed in Step 1. Remark 2: While the link augmentation in Step 4 may degrade our simpliﬁed design objective (19) due to the potential increase in 𝐷𝑎+ and 𝐷𝑎− , it is guaranteed to maintain or improve the original design objective (16). More importantly, our ablation study conﬁrms that this step can signiﬁcantly improve the actual convergence rate; see Appendix A.3.

Theorem 5.1. Let 𝐷 ∗ /Δ∗ denote the maximum degree/diameter of the minimum-degree spanning tree of the undirected version of the base topology. Suppose that the optimal minimum-degree spanning tree is computed in Step 1. Then under an input parameter 𝐾 that minimizes (19), a simpliﬁed version of Alg. 1 that skips Step 4 returns a strongly connected graph 𝐺𝑎 , for which ∗

the value of (19) ≤ 2𝐷 ∗ (Δ∗ ) 2 (1 + 𝐷 ∗ ) 4Δ .

(20)

Remark 1: Since ﬁnding the optimal minimum-degree spanning tree is NP-hard [7], in practice we can only compute an approximation to the minimum-degree spanning tree in Step 1. In 7

5.2.2 Complexity Analysis. Let 𝑛 = |𝑉 | and 𝑚 = |𝐸| for the base topology. Step 1 runs in time 𝑂 (𝑛𝑚 2) using the heuristic minimumdegree spanning tree algorithm from [7]. Step 2 can be completed in time 𝑂 𝐾𝑛(𝑛 log 𝑛+𝑚) by computing all-pair shortest paths for each 𝑘 before selecting (𝑢 ★, 𝑣 ★). Step 3 runs in 𝑂 (𝑛 + 𝑚) because

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

6.1 Evaluation Setting

all its operations run in linear time. In Step 4, computing a feasible communication schedule can be completed in 𝑂 (𝑚 2 ) time as the conﬂict graph construction and the vertex coloring of the conﬂict graph (by a greedy algorithm) both take 𝑂 (𝑚 2 ) time. During each loop in line 21, each of the 𝑂 (𝑚) candidate links is checked against 𝑂 (𝑚) activated links for conﬂict, and if a non-conﬂicting slot is found, we need to recompute Δ and 𝐷𝑎+ after adding this link, which takes 𝑂 (𝑛(𝑚 + 𝑛 log 𝑛)) time. This means each loop can complete in 𝑂 (𝑚𝑛(𝑚 + 𝑛 log 𝑛)) time. As at most 𝑚 links can be added, the running time for Step 4 is 𝑂 (𝑚 2𝑛(𝑚 + 𝑛 log 𝑛)). The overall time complexity of Alg. 1 is 𝑂 (𝑚 2𝑛(𝑚 + 𝑛 log 𝑛)), dominated by the while loop in Step 4. Thus, the complexity of Alg. 1 is polynomial in the size of the base topology.

5.3

6.1.1 Problem Setting. We consider the standard task of image classiﬁcation based on CIFAR-10, which consists of 60,000 color images in 10 classes. We train a lightweight version of ResNet-50 with 1.5M parameters over its training dataset with 50,000 images, and then test the trained model on the testing dataset with 10,000 images. We set the learning rate to 0.01, and the batch size to 64. We stop training when the average testing accuracy over 5 consecutive epochs reaches 80%. We randomly distribute the training data over nodes in two base topologies: (i) a random geometric (RG) graph as shown in Fig. 4a, generated by uniformly distributing 33 nodes in a unit area and forming links according to a communication radius of 0.5 (resulting in 267 undirected links), which models a free-space wireless network with identical nodes; (ii) the topology of Roofnet [1] as shown in Fig. 4b, which is a wireless mesh network with 33 nodes and 187 undirected links.

Illustrative Example

Fig. 3 illustrates the main steps of Alg. 1 on a (2, 6)-windmill graph. Starting from the base topology in Fig. 3a, the algorithm ﬁrst constructs a spanning tree that minimizes the maximum node degree, as shown in Fig. 3b. Next, in Fig. 3c, we add 𝐾 = 2 edges to reduce the diameter while preserving a sparse structure. The resulting undirected graph is then oriented in Fig. 3d to produce a strongly connected directed graph. Finally, Fig. 3e augments this directed graph with non-conﬂicting links while preserving the communication cost in terms of the required number of transmission slots, which yields the designed communication graph 𝐺𝑎 .

(a) RG

(b) Roofnet

Figure 4: Base topology used in evaluation. Center node Cluster head Other nodes Bidirected link Directed link Undirected link

6.1.2 Benchmarks. We compare the proposed solution with the following benchmarks: • ‘Vanilla D-PSGD’ [14], which is a baseline that uses the base topology as the communication graph and Metropolis–Hastings weights; • ‘Vanilla SGP’ [2], which uses the base topology as the communication graph but assigns weights according to Lemma 4.1; • ‘MATCHA’ [28], which aims at minimizing the communication time but assumes communications on disjoint links can occur in parallel (ignoring interference); • ‘BASS’ [9] a state-of-the-art mixing matrix design for minimizing the communication time under broadcast communications by activating collision-free subsets of nodes with designed probabilities, which proposed a lightweight solution called ‘BASS heuristic’ and a computationally heavy solution called ‘BASS optimized’.

(a) Base topology

(b) Step 1

(d) Step 3

We note that all but the proposed solution and ‘Vanilla SGP’ are based on D-PSGD and hence must use bidirected communication graphs and symmetric mixing matrices. For the solutions [5, 9, 28] with conﬁgurable communication cost per iteration, we align their per-iteration cost with the proposed solution4 . We set the number of candidate mixing matrices for ‘BASS optimized’ to 100, comparable to the setting in [9].

(e) Step 4

Figure 3: Illustration of Alg. 1 based on (2,6)-windmill graph.

Performance Evaluation

4 As ‘MATCHA’ [28] are unaware of the interference constraint, we conﬁgure their

We evaluate the proposed solution against benchmarks on a real dataset under realistic settings.

per-iteration cost as a percentage of the maximum cost under their assumption and align the percentage with our solution. 8

Optimizing Stochastic Gradient Push under Broadcast Communications

Conference’17, July 2017, Washington, DC, USA 400

Natural log of objective (Eq. 19)

400 300

200

100

125

150

175

300

200

100

200

K Figure 5: Design objective vs. design parameter 𝐾 for RG (𝐾 ∗ = 6).

100

125

150

175

200

K Figure 8: Design objective vs. design parameter 𝐾 for Roofnet (𝐾 ∗ = 8).

Bidirected active link Directed active link Inactive link

Figure 6: Designed communication graph based on RG.

Figure 9: Designed communication graph based on Roofnet.

0.3

0.005

50000 100000 150000 200000 250000 300000 350000

Total transmissi n sl ts

0.5

0.01

0.3

0.005

0.2 0

Testing Err r

Training L sses

0.5

0.01

0.003

0.8

Testing Err r

Training L sses

0.8

0.003

50000 100000 150000 200000 250000 300000 350000

T tal transmissi n sl ts

0.2 0

Total transmissi n sl ts

0.003

0.3

100

200

300

Ep chs

Vanilla DPSGD Vanilla SGP

400

500

MATCHA BASS heuristic

0.003

100

BASS ptimized

200

300

Ep chs

400

500

pr p sed

0.3 0.2

100

Vanilla DPSGD

Figure 7: Training performance on RG.

6.2

0.5

0.01

0.005

0.2 0

T tal transmissi n sl ts

Testing Err r

Training L sses

Testing Err r

Training L sses

0.5

0.005

50000 100000 150000 200000 250000 300000 350000

0.8

0.01

50000 100000 150000 200000 250000 300000 350000

200

300

Ep chs

Vanilla SGP

400

MATCHA

500

100

BASS heuristic

200

300

Ep chs

400

BASS ptimized

500

pr p sed

Figure 10: Training performance on Roofnet. while all the designs except for ‘BASS heuristic/optimized’ have similar logical convergence rates measured in epochs, they diﬀer substantially in the actual convergence rates measured in slots; (ii) our proposed solution notably outperforms the state-of-the-art solution ‘BASS optimized’ in terms of the convergence time in slots, which in turn outperforms the other benchmarks.

Evaluation Results

6.2.1 Results on Random Geometric (RG) Graph. We ﬁrst use the random geometric graph in Fig. 4a as the base topology. Fig. 5 evaluates the impact of the design parameter 𝐾 in Alg. 1 on our design objective (19), which guides the selection of an optimal parameter value 𝐾 ∗ . Under this parameter, Alg. 1 designs an activated communication graph as shown in Fig. 6, which contains both bidirectional and unidirectional links. We then evaluate the actual learning performance in terms of training loss and testing error in Fig. 7. The results show that: (i)

6.2.2 Results on Roofnet. We repeat the above experiments on the Roofnet topology shown in Fig. 4b. The results in Fig. 8–10 show qualitatively similar observations as before, indicating the generalizability of our previous observations. In this case, 𝐾 = 0 and 𝐾 = 8 9

Conference’17, July 2017, Washington, DC, USA

Base RG Roofnet

D-PSGD 290,976 311,808

MATCHA 362,502 262,314

BASS heu 229,824 212,688

Nguyen et al.

BASS opt 228,528 192,528

Proposed 179,712 170,688

[6] Reinhard Diestel. 2017. Graph Theory (5 ed.). Springer. [7] M. Fürer and B. Raghavachari. 1992. Approximating the Minimum Degree Spanning Tree to Within One from the Optimal Degree. In Proceedings of the 3rd Annual ACM–SIAM Symposium on Discrete Algorithms (SODA). 317–324. [8] Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. [9] Daniel PÉRez Herrera, Zheng Chen, and Erik G. Larsson. 2025. Faster Convergence With Less Communication: Broadcast-Based Subgraph Sampling for Decentralized Learning Over Wireless Networks. IEEE Open Journal of the Communications Society (2025), 1–1. doi:10.1109/OJCOMS.2025.3540133 [10] Yifan Hua, Kevin Miller, Andrea L Bertozzi, Chen Qian, and Bao Wang. 2022. Efﬁcient and reliable overlay networks for decentralized federated learning. SIAM J. Appl. Math. 82, 4 (2022), 1558–1586. [11] Zhida Jiang, Yang Xu, Hongli Xu, Lun Wang, Chunming Qiao, and Liusheng Huang. 2023. Joint Model Pruning and Topology Construction for Accelerating Decentralized Machine Learning. IEEE Transactions on Parallel and Distributed Systems (2023). [12] Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jagg. 2020. Decentralized Deep Learning with Arbitrary Communication Compression. In The International Conference on Learning Representations (ICLR). [13] Batiste Le Bars, Aurélien Bellet, Marc Tommasi, Erick Lavoie, and Anne-Marie Kermarrec. 2023. Reﬁned convergence and topology learning for decentralized SGD with heterogeneous data. In International Conference on Artiﬁcial Intelligence and Statistics. PMLR, 1672–1702. [14] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. 2017. Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent. In Proceedings of the 31st International Conference on Neural Information Processing Systems. 5336–5346. [15] Liyuan Liang, Xinmeng Huang, Ran Xin, and Kun Yuan. 2025. Understanding the Inﬂuence of Digraphs on Decentralized Optimization: Eﬀective Metrics, Lower Bound, and Optimal Algorithm. SIAM Journal on Optimization 35, 3 (2025), 1570– 1600. [16] Yucheng Lu and Christopher De Sa. 2020. Moniqua: Modulo Quantized Communication in Decentralized SGD. In International Conference on Machine Learning (ICML). [17] Yucheng Lu and Christopher De Sa. 2021. Optimal Complexity in Decentralized Training. In International Conference on Machine Learning (ICML). [18] H. McMahan, Eider Moore, D. Ramage, S. Hampson, and Blaise Agüera y Arcas. 2017. Communication-Eﬃcient Learning of Deep Networks from Decentralized Data. In AISTATS. [19] Giovanni Neglia, Chuan Xu, Don Towsley, and Gianmarco Calbi. 2020. Decentralized gradient methods: does topology matter?. In International Conference on Artiﬁcial Intelligence and Statistics. PMLR, 2348–2358. [20] Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. 2020. SPARQSGD: Event-Triggered and Compressed Communication in Decentralized Optimization. In IEEE CDC. [21] Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. 2021. SQuARMSGD: Communication-Eﬃcient Momentum SGD for Decentralized Optimization. IEEE Journal on Selected Areas in Information Theory 2, 3 (2021), 954–969. [22] Artin Spiridonoﬀ, Alex Olshevsky, and Ioannis Ch. Paschalidis. 2020. Robust Asynchronous Stochastic Gradient-Push: Asymptotically Optimal and NetworkIndependent Performance for Strongly Convex Functions. Journal of Machine Learning Research 21, 58 (2020), 1–47. [23] Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. 2018. Communication compression for decentralized training. In Advances in Neural Information Processing Systems (NeurIPS). [24] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. 2018. 𝐷 2 : Decentralized Training over Decentralized Data. In Proceedings of the 35th International Conference on Machine Learning, ICML. [25] Nguyen H. Tran, Wei Bao, Albert Zomaya, Minh N.H. Nguyen, and Choong Seon Hong. 2019. Federated Learning over Wireless Networks: Optimization Model Design and Analysis. In IEEE INFOCOM. [26] Thijs Vogels, Hadrien Hendrikx, and Martin Jaggi. 2022. Beyond spectral gap: The role of the topology in decentralized learning. Advances in Neural Information Processing Systems 35 (2022), 15039–15050. [27] Jianyu Wang and Gauri Joshi. 2019. Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-oﬀ in Local-Update SGD. In Systems for ML. [28] Jianyu Wang, Anit Kumar Sahu, Gauri Joshi, and Soummya Kar. 2022. MATCHA: A Matching-Based Link Scheduling Strategy to Speed up Distributed Optimization. IEEE Transactions on Signal Processing 70 (2022), 5208–5221. [29] Shiqiang Wang, Tiﬀany Tuor, Theodoros Salonidis, Kin K. Leung, Christian Makaya, Ting He, and Kevin Chan. 2019. Adaptive Federated Learning in Resource Constrained Edge Computing Systems. IEEE Journal on Selected Areas in Communications 37, 6 (2019), 1205–1221. doi:10.1109/JSAC.2019.2904348

Table 1: Convergence Time for 80% Accuracy (in slots) yield similar results in both the abstract design objective (19) and the actual learning performance (the curve for 𝐾 = 0 is omitted in Fig. 10 for better visibility). A quantitative diﬀerence from the results on RG is that the performance gap between our solution and the state of the art (‘BASS optimized’) in terms of convergence rate in slots appears smaller for Roofnet. Intuitively, this is because the Roofnet topology is sparser than the RG graph used in our evaluation, which reduces the degree of freedom in the design. Nevertheless, in both cases, our design notably improves upon the state of the art by strategically selecting the communication links based on a theory-backed objective function. 6.2.3 Summary. Table 1 summarizes the convergence times from these experiments, measured by the total number of transmission slots until the average testing accuracy over 5 consecutive epochs reaches 80%. The results show that the proposed solution reduces the convergence time by 11–21% compared to the state-of-the-art solution ‘BASS optimized’, and 38–45% compared to the baseline solution ‘Vanilla D-PSGD’. Notably, ‘Vanilla SGP’ performs worse than ‘Vanilla D-PSGD’ (omitted in Table 1 due to space limitation), indicating that the above improvement is not from simply switching the learning algorithm from D-PSGD to SGP, but from suitably utilizing the additional communication ﬂexibility enabled by SGP in communication graph design.

Conclusion

We considered the mixing matrix design for minimizing the convergence time in decentralized federated learning (DFL) under broadcast communications and interference constraints. Motivated by the ability of stochastic gradient push (SGP) in utilizing asymmetric parameter sharing, we developed a solution to optimize its mixing matrix by analyzing the dependency of its convergence rate on the mixing matrix and extracting a tractable design objective based on graph-theoretic parameters of the activated communication graph. Our solution not only has guaranteed performance in terms of the theoretical design objective, but also demonstrates notably faster convergence than the state of the art in evaluations based on real data, signaling the value in eﬃciently utilizing asymmetric communications for learning in wireless networks.

References [1] Daniel Aguayo, John Bicket, Sanjit Biswas, Glenn Judd, and Robert Morris. 2004. Link-level Measurements from an 802.11b Mesh Network. In SIGCOMM. [2] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. 2019. Stochastic Gradient Push for Distributed Deep Learning. In Proceedings of the 36th International Conference on Machine Learning, Vol. 97. 344–353. [3] Xianhao Chen, Guangyu Zhu, Yiqin Deng, and Yuguang Fang. 2022. Federated learning over multihop wireless networks with in-network aggregation. IEEE Transactions on Wireless Communications 21, 6 (2022), 4622–4634. [4] Zheng Chen, Martin Dahl, and Erik G. Larsson. 2023. Decentralized Learning over Wireless Networks: The Eﬀect of Broadcast with Random Access. In 2023 IEEE 24th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC). 316–320. doi:10.1109/SPAWC53906.2023.10304514 [5] Cho-Chun Chiu, Xusheng Zhang, Ting He, Shiqiang Wang, and Ananthram Swami. 2023. Laplacian Matrix Sampling for Communication- Eﬃcient Decentralized Learning. IEEE Journal on Selected Areas in Communications 41, 4 (2023), 887–901. doi:10.1109/JSAC.2023.3242735 10

Optimizing Stochastic Gradient Push under Broadcast Communications

Conference’17, July 2017, Washington, DC, USA

[30] Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017. Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms. arXiv preprint arXiv:1708.07747 (2017). [31] Ran Xin, Usman Khan, and Soummya Kar. 2021. A Hybrid Variance-Reduced Method for Decentralized Stochastic Non-Convex Optimization. In Proceedings of the 38th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 139), Marina Meila and Tong Zhang (Eds.). PMLR, 11459– 11469. https://proceedings.mlr.press/v139/xin21a.html [32] Hong Xing, Osvaldo Simeone, and Suzhi Bi. 2021. Federated learning over wireless device-to-device networks: Algorithms and convergence analysis. IEEE Journal on Selected Areas in Communications 39, 12 (2021), 3723–3741. [33] Runze You and Shi Pu. 2025. Stochastic Push-Pull for Decentralized Nonconvex Optimization. arXiv:2506.07021 [math.OC] https://arxiv.org/abs/2506.07021 [34] Xusheng Zhang, Tuan Nguyen, and Ting He. 2026. Mixing Matrix Design for Energy-eﬃcient Decentralized Federated Learning. In IEEE INFOCOM. [35] Yiming Zhou, Yifei Cheng, Linli Xu, and Enhong Chen. 2025. Adaptive Weighting Push-SUM for Decentralized Optimization With Statistical Diversity. IEEE Transactions on Control of Network Systems 12, 3 (2025), 2337–2349. doi:10.1109/TCNS.2025.3566329

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

n o p p 1−𝑞 Now let 𝜂 = 𝑇𝑛 and assume that 𝑇𝑛 ≤ min √ √ , 1 . We 3 2 𝐶𝐿 𝑛 have 𝑇 −1 2 4(𝑓 (𝒙 (0) ) − 𝑓 ∗ ) 2𝐿𝜎 2 1Õ + √ E ∇𝑓 (𝒙 (𝑡 ) ) ≤ √ 𝑇 𝑡 =0 𝑛𝑇 𝑛𝑇

A Appendix A.1 Proof of Theorem 3.1 Let 𝒙 (𝑡 ) := 𝑛1 A.1.1

Í𝑁

(𝑡 ) 𝑗=1 𝒙 𝑗 .

Main Theorem Proof.

Proof. Assume 𝜂 ≤ min

1−𝑞 √ √ ,1 . 3 2 𝐶𝐿 𝑛

Moreover, since 𝑛 ≥ 2,

it suﬃces to choose

which implies 18𝜂 2𝐿2𝐶 2 9𝜂 2 𝐿2𝐶 2 1 ≤ ≤ . 2 𝑃 (1 − 𝑞) (1 − 𝑞) 2 2 Hence,

By Lemma A.7, 𝑇 −1 2 2(𝑓 (𝒙 (0) ) − 𝑓 ∗ ) 𝐿𝜂𝜎 2𝑇 9𝜂 2𝐿2𝐶 2 Õ (𝑡 ) ) ≤ E ∇𝑓 (𝒙 + 𝑃 (1 − 𝑞) 2 𝑡 =0 𝜂 𝑛 +

𝑃 (1 − 𝑞) 2

3𝜂 2𝐿2𝐶 2𝑛𝜎 2𝑇 𝑃 (1 − 𝑞) 2

9𝜂 2 𝐿2𝐶 2𝑛𝜁 2𝑇 𝑃 (1 − 𝑞) 2

A.1.2

2 4(𝑓 (𝒙 (0) ) − 𝑓 ∗ ) 2𝐿𝜂𝜎 2𝑇 ≤ E ∇𝑓 (𝒙 (𝑡 ) ) + 𝜂 𝑛 𝑡 =0

𝑇Õ −1

(1 − 𝑞) 2

where 𝐶 :=

12𝜂 2𝐿2𝐶 2𝑛𝜎 2𝑇 36𝜂 2 𝐿2𝐶 2𝑛𝜁 2𝑇 + . (1 − 𝑞) 2 (1 − 𝑞) 2

(0)

) − 𝑓 ∗)

2 1 4(𝑓 (𝒙 ≤ E ∇𝑓 (𝒙 (𝑡 ) ) 𝑇 𝑡 =0 𝜂𝑇

12𝐿2𝐶 2 (max𝑚

(0) 𝒙𝑚

(1 − 𝑞) 2𝑇

2𝐿𝜂𝜎 2 𝑛

12𝜂 2𝐿2𝐶 2𝑛𝜎 2 36𝜂 2𝐿2𝐶 2𝑛𝜁 2 + . (1 − 𝑞) 2 (1 − 𝑞) 2

𝑞 := (1 − 𝛿 Δ𝐵 ) Δ𝐵 ∈ (0, 1)

(0) 𝒙 (𝑡 ) − 𝒛𝑖(𝑡 ) ≤ 𝐶𝑞𝑡 max 𝒙𝑚 + 𝜂𝐶 𝑚

4 , 𝛿 Δ𝐵

(23)

Lemma A.2 (Max form of the consensus bound). Under the same assumptions as Lemma A.1, for 𝑡 ≥ Δ𝐵,

Dividing both sides by 𝑇 , we obtain 𝑇 −1 Õ

! 1/2 𝑛 𝑡 2 𝜂𝐶 Õ 𝑡 −𝑠 Õ (𝑠 ) (𝑠 ) 𝑞 +√ 𝑔𝑖 (𝒛𝑖 ; 𝜉𝑖 ) . 𝑛 𝑠=0 𝑖=1 𝑖=1

9𝜂 2 𝐿 2 𝐶 2

Supporting Lemmas.

Lemma A.1 (Consensus bound; Corollary 4 in [35]). Under columnstochastic and Assumption (4). Then for 𝑡 ≥ Δ𝐵, ! 1/2 𝑛 √ 𝑡 Õ (𝑡 ) (0) 2 (𝑡 ) 𝒙 − 𝒛𝑖 k𝒙𝑖 k ≤ 𝑛𝑞

Substituting the bound 𝑃 ≥ 12 and 1 − 𝑃 (1−𝑞) 2 ≥ 12 into the above inequality, we obtain

(0) 2 12𝐿2𝐶 2 (max𝑚 𝒙𝑚 )

(

then the fourth term in (22) dominates the other three terms. Hence, it suﬃces to satisfy 24𝐿2𝐶 2 𝑆. 𝑇 ≥ (1 − 𝑞) 2𝜖

9𝜂 2 𝐿2𝐶 2 1 ≥ . 𝑃 (1 − 𝑞) 2 2

(0) 2 3𝐿2𝐶 2 (max𝑚 𝒙𝑚 )

(21)

) 18𝐶 2𝐿2𝑛 2 16 2 24𝐿2𝐶 2 , 𝐴, 𝑆 , (22) 𝑇 ≥ max 𝑛, (1 − 𝑞) 2 𝑛𝜖 2 (1 − 𝑞) 2𝜖 o n p 1−𝑞 where the ﬁrst two bounds ensure 𝑇𝑛 ≤ min √ √ , 1 , and 3 2 𝐶𝐿 𝑛 the last two bounds ensure that each of the terms in (21) is bounded by 𝜖/2. If 2(1 − 𝑞) 2 𝐴2 24𝐿2𝐶 2 𝑆 4 ≤ 𝜖 ≤ min 𝑆, , 3𝐿2𝐶 2𝑛𝑆 3𝑛 2 (1 − 𝑞) 2 𝑛

1−𝑞 1−𝑞 𝜂≤ √ , √ ≤ 6𝐿𝐶 3 2 𝐶𝐿 𝑛

1−

12𝐿2𝐶 2𝑛 2𝜎 2 36𝐿2𝐶 2𝑛 2𝜁 2 + (1 − 𝑞) 2𝑇 (1 − 𝑞) 2𝑇

(0) 2 Let 𝐴 := 2𝑓 (𝒙 (0) ) − 2𝑓 ∗ + 𝐿𝜎 2 and 𝑆 := (max𝑚 𝒙𝑚 ) + 𝑛 2𝜎 2 + 2 Í −1 3𝑛 2𝜁 2 . To achieve 𝜖-convergence, i.e., 𝑇1 𝑇𝑡 =0 E ∇𝑓 (𝒙 (𝑡 ) ) ≤ 𝜖,

9𝜂 2𝐶 2𝐿2𝑛 1 𝑃 := 1 − ≥ . (1 − 𝑞) 2 2

1−

(1 − 𝑞) 2𝑇 2 =√ 2𝑓 (𝒙 (0) ) − 2𝑓 ∗ + 𝐿𝜎 2 𝑛𝑇 12𝐿2𝐶 2 (0) 2 (max 𝒙𝑚 ) + 𝑛 2𝜎 2 + 3𝑛 2𝜁 2 . + 2 𝑚 (1 − 𝑞) 𝑇

Then

(0) 2 12𝐿2𝐶 2 (max𝑚 𝒙𝑚 )

𝑠=0

𝑞𝑡 −𝑠 max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) .

Proof. By the inequality ! 1/2 𝑛 Õ √ 2 𝑎𝑖 ≤ 𝑛 max 𝑎𝑖 , 𝑖=1

𝑡 Õ

𝑖

𝑗

(24)

Optimizing Stochastic Gradient Push under Broadcast Communications

we have

𝑛 Õ 𝑖=1

and for each 𝑠, 𝑛 Õ

(0) k𝒙𝑖 k 2

(𝑠 ) (𝑠 ) 𝑔𝑖 (𝒛𝑖 ; 𝜉𝑖 )

𝑖=1

! 1/2

Conference’17, July 2017, Washington, DC, USA

2 . Lemma A.4 (Consensus error recursion). Let 𝑄𝑖(𝑡 ) := E 𝒙 (𝑡 ) − 𝒛𝑖(𝑡 )

√ (0) ≤ 𝑛 max 𝒙𝑚 ,

Under Assumptions (1)–(4), for all 𝑡 ≥ 0,

𝑚

3𝜂 2𝐶 2𝑛𝜎 2 9𝜂 2𝐶 2𝑛𝜁 2 + (1 − 𝑞) 2 (1 − 𝑞) 2 𝑛 𝑡 𝑡 2 9𝜂 2𝐶 2 𝐿2 Õ 𝑡 −𝑠 Õ (𝑠 ) 9𝜂 2𝐶 2 Õ 𝑡 −𝑠 𝑄𝑖 + 𝑞 𝑞 E ∇𝑓 (𝒙 (𝑠 ) ) . + 1 − 𝑞 𝑠=0 1 − 𝑞 𝑠=0 𝑖=1 (26)

(0) 2 𝑄𝑖(𝑡 ) ≤ 3𝐶 2𝑞 2𝑡 (max 𝒙𝑚 ) + 𝑚

√ (𝑠 ) (𝑠 ) ≤ 𝑛 max 𝑔 𝑗 (𝒛 𝑗 ; 𝜉 𝑗 ) . 𝑗

√ Substituting these into the previous lemma cancels the factor 1/ 𝑛 and yields the result. Lemma A.3 (Maximum local gradient bound). Under Assumptions (1) and (3), for any 𝑡 ≥ 0,

E max ∇𝑓 𝑗 (𝒛 𝑗(𝑡 ) ) 𝑗

Apply lemma A.2 

 𝑄𝑖(𝑡 ) ≤ E  𝐶𝑞𝑡 max 𝑚

𝑛 Õ 2 (𝑡 ) (𝑡 ) 2 E 𝒛𝑖 − 𝒙 ≤3𝐿 + 3𝑛𝜁 2

𝑖=1

+ 3E ∇𝑓 (𝒙

(𝑡 )

)

𝑗

max

𝑠=0

𝑗

𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) )

! 2     

𝑗

2  𝑡 Õ   (𝑠 ) (𝑠 ) (𝑠 ) (0) 𝑡 −𝑠  ª © 𝐶𝑞𝑡 max 𝒙𝑚 𝑔 (𝒛 ; 𝜉 ) − ∇𝑓 (𝒛 ) + 𝜂𝐶 𝑞 max 𝑗 𝑗 𝑗 𝑗 𝑗 ®  𝑚 𝑗 ®  | 𝑠=0 {z }  | {z }®®   𝑎 ®  𝑏 (𝑡 ) 𝑄𝑖 ≤ E  ® 𝑡 ®  Õ (𝑠 ) ®  + 𝜂𝐶 𝑡 −𝑠 𝑞 max ∇𝑓 𝑗 (𝒛 𝑗 ) ®  𝑗 ®  𝑠=0 ®  | {z }   « ¬  𝑐  We have 𝑄𝑖(𝑡 ) ≤ E 3𝑎 2 + 3𝑏 2 + 3𝑐 2 = 3E 𝑎 2 + 3E 𝑏 2 + 3E 𝑐 2 .

+ ∇𝑓 (𝒙 (𝑡 ) ) 2

≤3 ∇𝑓𝑖 (𝒛𝑖(𝑡 ) ) − ∇𝑓𝑖 (𝒙 (𝑡 ) ) + 3 ∇𝑓 (𝒙 (𝑡 ) )

+ 3 ∇𝑓𝑖 (𝒙 (𝑡 ) ) − ∇𝑓 (𝒙 (𝑡 ) )

Applied assumption (1): (𝑡 )

∇𝑓𝑖 (𝒛𝑖 )

(𝑡 )

≤3𝐿2 𝒛𝑖

− 𝒙 (𝑡 )

+ 3 ∇𝑓 (𝒙

(𝑡 )

)

+ 3 ∇𝑓𝑖 (𝒙 (𝑡 ) ) − ∇𝑓 (𝒙 (𝑡 ) )

Where

(0) 𝑎 := 𝐶𝑞𝑡 max 𝒙𝑚 , 𝑚

Taking the maximum over node 𝑗 on both sides gives max ∇𝑓 𝑗 (𝒛 𝑗(𝑡 ) )

≤3𝐿2 max 𝒛 𝑗(𝑡 ) − 𝒙 (𝑡 )

+ 3 ∇𝑓 (𝒙

(𝑡 )

)

+ 3 max ∇𝑓 𝑗 (𝒙 (𝑡 ) ) − ∇𝑓 (𝒙 (𝑡 ) )

𝑗

∇𝑓 𝑗 (𝒛 𝑗(𝑡 ) )

≤ 3𝐿

𝑛 Õ 𝑖=1

≤

𝑁 Õ 𝑖=1

𝑐 := 𝜂𝐶

. We have 𝒛𝑖(𝑡 ) − 𝒙 (𝑡 )

𝒛𝑖(𝑡 ) − 𝒙 (𝑡 )

𝑡 Õ

𝑠=0 𝑡 Õ 𝑠=0

Apply Assumption (3) max 𝒛 𝑗(𝑡 ) − 𝒙 (𝑡 )

𝑏 := 𝜂𝐶

𝑗

𝑞

𝑡 −𝑠

which follows from triangle inequality, we obtain

∇𝑓𝑖 (𝒛𝑖(𝑡 ) ) ≤ ∇𝑓𝑖 (𝒛𝑖(𝑡 ) ) − ∇𝑓𝑖 (𝒙 (𝑡 ) ) + ∇𝑓𝑖 (𝒙 (𝑡 ) ) − ∇𝑓 (𝒙 (𝑡 ) )

max

+ 𝜂𝐶

𝑡 Õ

max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) ≤ max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) +max ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) ,

Proof.

∇𝑓𝑖 (𝒛𝑖(𝑡 ) )

(0) 𝒙𝑚

 

Using

(25)

2 𝑄𝑖(𝑡 ) = E 𝒙 (𝑡 ) − 𝒛𝑖(𝑡 )

Proof.

≤ 𝑛𝜁 2

2 2

𝑏 =𝜂 𝐶

𝑡 Õ

+ 3𝑛𝜁 + 3 ∇𝑓 (𝒙

(𝑡 )

)

2 2

=𝜂 𝐶

𝑗

𝑞𝑡 −𝑠 max ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) . 𝑗

(0) 2 E 𝑎 2 = 𝐶 2𝑞 2𝑡 (max 𝒙𝑚 ) . 𝑚

𝑞

𝑡 −𝑠

𝑠=0

𝑞𝑡 −𝑠 max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) ,

max 𝑗

𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) )

𝑡 p Õ p 𝑞𝑡 −𝑠 𝑞𝑡 −𝑠 max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) 𝑠=0

𝑡 Õ

𝑗

𝑡 Õ

2 Cauchy Taking expectation on both sides yields the lemma: (𝑠 ) (𝑠 ) (𝑠 ) ≤ 𝜂 2𝐶 2 𝑞𝑡 −𝑠 𝑞𝑡 −𝑠 max 𝑔 𝑗 (𝒛 𝑗 ; 𝜉 𝑗 ) − ∇𝑓 𝑗 (𝒛 𝑗 ) 𝑗 𝑛 Õ 2 2 2 𝑠=0 𝑠=0 E 𝒛𝑖(𝑡 ) − 𝒙 (𝑡 ) +3𝑛𝜁 2+3E ∇𝑓 (𝒙 (𝑡 ) ) ≤ 3𝐿2 E max ∇𝑓 𝑗 (𝒛 𝑗(𝑡 ) ) . 𝑡 2 2 Õ 2 𝑗 𝜂 𝐶 𝑖=1 𝑞𝑡 −𝑠 max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) . ≤ 𝑗 1 − 𝑞 𝑠=0

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

𝑡 2 𝜂 2𝐶 2 Õ 𝑞𝑡 −𝑠 E max 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) E 𝑏2 ≤ 𝑗 1 − 𝑞 𝑠=0 𝑛 𝑡 2 𝜂 2𝐶 2 Õ 𝑡 −𝑠 Õ ≤ E 𝑔 𝑗 (𝒛 𝑗(𝑠 ) ; 𝜉 𝑗(𝑠 ) ) − ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) 𝑞 1 − 𝑞 𝑠=0 𝑗=1 𝑡 Assumption (2) 𝜂 2𝐶 2𝑛𝜎 2 Õ

≤

1−𝑞

𝑐 =𝜂 𝐶

𝑡 Õ

2 2

=𝜂 𝐶

𝑞𝑡 −𝑠

𝑞

𝑡 −𝑠

𝜂 𝐶

𝑗

∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) )

𝑀 (𝑡 ) :=

𝑡 Õ

𝑞

𝑡 −𝑠

𝑗

𝑡 Õ 𝑠=0

𝑞

𝑡 −𝑠

max 𝑗

2 𝜂 2𝐶 2 Õ 𝑡 −𝑠 𝑞 max ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) . 𝑗 1 − 𝑞 𝑠=0

3𝜂 2𝐶 2𝑛𝜎 2 9𝜂 2𝐶 2𝑛𝜁 2 + 𝑚 (1 − 𝑞) 2 (1 − 𝑞) 2 𝑛 𝑛 𝑡 𝑡 2 9𝜂 2𝐶 2𝐿2 1 Õ Õ 𝑡 −𝑠 Õ (𝑠 ) 9𝜂 2𝐶 2 Õ 𝑡 −𝑠 𝑄𝑖 + 𝑞 𝑞 E ∇𝑓 (𝒙 (𝑠 ) ) + 1 − 𝑞 𝑛 𝑖=1 𝑠=0 1 − 𝑞 𝑠=0 𝑖=1 ≤

∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) )

3𝜂 2𝐶 2𝑛𝜎 2 9𝜂 2𝐶 2𝑛𝜁 2 + 𝑚 (1 − 𝑞) 2 (1 − 𝑞) 2 𝑡 𝑡 2 9𝜂 2𝐶 2𝐿2𝑛 Õ 𝑡 −𝑠 (𝑠 ) 9𝜂 2𝐶 2 Õ 𝑡 −𝑠 . 𝑞 𝑀 + 𝑞 E ∇𝑓 (𝒙 (𝑠 ) ) + 1 − 𝑞 𝑠=0 1 − 𝑞 𝑠=0 Now Summing from t=0 to T-1, we have: 𝑇Õ −1

𝑡 2 𝜂 2𝐶 2 Õ 𝑞𝑡 −𝑠 E max ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) ) E 𝑐2 ≤ 𝑗 1 − 𝑞 𝑠=0 𝑡 𝑛 Õ 2 lemma A.3 𝜂 2𝐶 2 Õ 𝑡 −𝑠 + 3𝑛𝜁 2 𝑞 ≤ E 𝒛𝑖(𝑠 ) − 𝒙 (𝑠 ) 3𝐿2 1 − 𝑞 𝑠=0 𝑖=1 2 +3E ∇𝑓 (𝒙 (𝑠 ) )

𝑡 2 2 Õ

(0) 2 𝑀 (𝑡 ) ≤ 3𝐶 2 (max 𝒙𝑚 ) 𝑚

𝑡 =0

2 2 2

𝑇Õ −1 Õ 𝑡

𝑇Õ −1 𝑡 =0

𝑞 2𝑡 +

3𝜂 2𝐶 2𝑛𝜎 2 9𝜂 2𝐶 2𝑛𝜁 2 𝑇 + 𝑇 (1 − 𝑞) 2 (1 − 𝑞) 2

9𝜂 𝐶 𝐿 𝑛 𝑞𝑡 −𝑠 𝑀 (𝑠 ) 1 − 𝑞 𝑡 =0 𝑠=0 𝑇 −1 𝑡 2 9𝜂 2𝐶 2 Õ Õ 𝑡 −𝑠 + . 𝑞 E ∇𝑓 (𝒙 (𝑠 ) ) 1 − 𝑞 𝑡 =0 𝑠=0 +

𝑛 𝑡 𝑡 3𝜂 2𝐶 2 𝐿2 Õ 𝑡 −𝑠 Õ (𝑠 ) 3𝜂 2𝐶 2𝑛𝜁 2 Õ 𝑡 −𝑠 𝑄𝑖 + 𝑞 𝑞 1 − 𝑞 𝑠=0 1 − 𝑞 𝑠=0 𝑖=1 𝑡 2 3𝜂 2𝐶 2 Õ 𝑡 −𝑠 (𝑠 ) + 𝑞 E ∇𝑓 (𝒙 ) 1 − 𝑞 𝑠=0

𝑛 𝑡 3𝜂 2𝐶 2 𝐿2 Õ 𝑡 −𝑠 Õ (𝑠 ) 3𝜂 2𝐶 2𝑛𝜁 2 𝑄𝑖 + 𝑞 ≤ 1 − 𝑞 𝑠=0 (1 − 𝑞) 2 𝑖=1

(0) 2 3𝐶 2𝑞 2𝑡 (max 𝒙𝑚 ) +

(0) 2 ≤ 3𝐶 2𝑞 2𝑡 (max 𝒙𝑚 ) +

≤

1 Õ (𝑡 ) 𝑄 𝑛 𝑖=1 𝑖

Lemma A.4

p 𝑞𝑡 −𝑠 𝑞𝑡 −𝑠 max ∇𝑓 𝑗 (𝒛 𝑗(𝑠 ) )

𝑠=0

𝑡

Then,

max

𝑡 p Õ

2 2

3𝜂 2𝐶 2𝑛𝜎 2 3𝐶 2 (0) 2 (max 𝒙𝑚 𝑇 ) + 2 𝑚 𝑃 (1 − 𝑞) 𝑃 (1 − 𝑞) 2 𝑇 −1 2 9𝜂 2𝐶 2𝑛𝜁 2 9𝜂 2𝐶 2 Õ (𝑡 ) + ) . (27) E 𝑇 + ∇𝑓 (𝒙 𝑃 (1 − 𝑞) 2 𝑃 (1 − 𝑞) 2 𝑡 =0

𝑛

𝑠=0

Cauchy

𝑀 (𝑡 ) ≤

Proof.

𝑠=0

≤

𝑡 =0

𝜂 2𝐶 2𝑛𝜎 2 . (1 − 𝑞) 2

2 2

≤

𝑇Õ −1

𝑠=0

Similarly, 2

lemma A.4 and for 𝑃 > 0, we have

Using the geometric-series bounds: 𝑇Õ −1 𝑡 =0

𝑞 2𝑡 ≤

1 , 1 − 𝑞2

𝑇 Õ 𝑡 Õ 𝑡 =0 𝑠=0

𝑞𝑡 − 𝑗 𝛽 (𝑠 ) ≤

𝑇 1 Õ (𝑠 ) 𝛽 , 1 − 𝑞 𝑠=0

valid for 0 < 𝑞 < 1 and 𝛽 (𝑠 ) ≥ 0, we obtain 𝑇Õ −1

2 3𝜂 𝐶 𝑞𝑡 −𝑠 E ∇𝑓 (𝒙 (𝑠 ) ) . 1 − 𝑞 𝑠=0

𝑡 =0

𝑀 (𝑡 ) ≤

Combine all the term, we have 3𝜂 2𝐶 2𝑛𝜎 2 9𝜂 2𝐶 2𝑛𝜁 2 + 𝑚 (1 − 𝑞) 2 (1 − 𝑞) 2 𝑛 𝑡 𝑡 2 9𝜂 2𝐶 2𝐿2 Õ 𝑡 −𝑠 Õ (𝑠 ) 9𝜂 2𝐶 2 Õ 𝑡 −𝑠 𝑄𝑖 + 𝑞 𝑞 E ∇𝑓 (𝒙 (𝑠 ) ) + 1 − 𝑞 𝑠=0 1 − 𝑞 𝑠=0 𝑖=1

(0) 2 𝑄𝑖(𝑡 ) ≤ 3𝐶 2𝑞 2𝑡 (max 𝒙𝑚 ) +

Now subtract

9𝜂 2 𝐶 2 𝐿 2 𝑛 Í𝑇 −1 1 (𝑡 ) from both sides. Using 𝑡 =0 𝑀 (1−𝑞) 2 1−𝑞 2

1 we obtain (1−𝑞) 2

Lemma A.5 (Average consensus error bound). Deﬁne 𝑀 (𝑡 ) := 9𝜂 2 𝐶 2 𝐿 2 𝑛 (𝑡 ) 1 Í𝑛 𝑖=1 𝑄 𝑖 . Let 𝑃 := 1 − (1−𝑞) 2 . Under the same conditions as 𝑛

9𝜂 2𝐶 2𝑛𝜁 2 3𝜂 2𝐶 2𝑛𝜎 2 3𝐶 2 (0) 2 (max 𝒙𝑚 𝑇+ 𝑇 ) + 2 2 𝑚 1−𝑞 (1 − 𝑞) (1 − 𝑞) 2 𝑇 −1 𝑇 −1 2 9𝜂 2𝐶 2𝐿2𝑛 Õ (𝑠 ) 9𝜂 2𝐶 2 Õ (𝑠 ) + ) . 𝑀 + E ∇𝑓 (𝒙 (1 − 𝑞) 2 𝑠=0 (1 − 𝑞) 2 𝑠=0

1−

≤

𝑇 −1 9𝜂 2𝐶 2 𝐿2𝑛 Õ (𝑡 ) 3𝜂 2𝐶 2𝑛𝜎 2 3𝐶 2 (0) 2 𝑀 ≤ (max 𝑇 𝒙 ) + 𝑚 (1 − 𝑞) 2 𝑡 =0 (1 − 𝑞) 2 𝑚 (1 − 𝑞) 2 𝑇 −1 2 9𝜂 2𝐶 2 Õ 9𝜂 2𝐶 2𝑛𝜁 2 (𝑡 ) E ∇𝑓 (𝒙 ) 𝑇+ . + (1 − 𝑞) 2 (1 − 𝑞) 2 𝑡 =0

Optimizing Stochastic Gradient Push under Broadcast Communications

9𝜂 2 𝐶 2 𝐿 2 𝑛 Let 𝑃 := 1 − (1−𝑞) 2 . If 𝜂 ≤ 𝑇Õ −1 𝑡 =0

Conference’17, July 2017, Washington, DC, USA

1−𝑞 √ √ then 𝑃 ≥ 1 . Therefore, 2 3 2 𝐶𝐿 𝑛

Thus, 𝑇 −1 2 9𝜂 2𝐿2𝐶 2 Õ 2(𝑓 (𝒙 (0) ) − 𝑓 ∗ ) 𝐿𝜂𝜎 2𝑇 (𝑡 ) 1− ) ≤ E ∇𝑓 (𝒙 + 2 𝑃 (1 − 𝑞) 𝑡 =0 𝜂 𝑛

3𝜂 2𝐶 2𝑛𝜎 2 3𝐶 2 (0) 2 (max 𝒙𝑚 𝑇 ) + 𝑃 (1 − 𝑞) 2 𝑚 𝑃 (1 − 𝑞) 2 𝑇 −1 2 9𝜂 2𝐶 2 Õ 9𝜂 2𝐶 2𝑛𝜁 2 (𝑡 ) . E ∇𝑓 (𝒙 ) 𝑇+ + 𝑃 (1 − 𝑞) 2 𝑃 (1 − 𝑞) 2 𝑡 =0

𝑀 (𝑡 ) ≤

(0) 2 3𝐿2𝐶 2 (max𝑚 𝒙𝑚 )

𝑃 (1 − 𝑞) 2

3𝜂 2 𝐿2𝐶 2𝑛𝜎 2𝑇 9𝜂 2𝐿2𝐶 2𝑛𝜁 2𝑇 + . 𝑃 (1 − 𝑞) 2 𝑃 (1 − 𝑞) 2

A.2

Lemma A.6. (Cumulative inequality). The same summation argument as in [2, Lemma 8, Eq. (28)] implies " 2# 𝑇 −1 𝑇 −1 𝑛 2 𝜂Õ 𝜂 − 𝐿𝜂 2 Õ 1Õ (𝑡 ) (𝑡 ) E ∇𝑓 (𝒙 ) E ∇𝑓𝑖 (𝒛𝑖 ) + 2 𝑡 =0 2 𝑛 𝑖=1 𝑡 =0 ≤ 𝑓 (𝒙 (0) ) − 𝑓 ∗ +

Proof of Collorary 3.2. We have 4 𝐶 = Δ𝐵 , 𝑞 = (1 − 𝛿 Δ𝐵 ) 1/(Δ𝐵 ) . 𝛿 Let 𝑥 := 𝛿 Δ𝐵 .

𝐿𝜂 2𝜎 2 𝜂𝐿2 Õ (𝑡 ) 𝑀 . (28) 𝑇+ 2𝑛 2 𝑡 =0 𝑇 −1

When 𝑥 ≪ 1, a ﬁrst-order Taylor expansion gives 𝑥 (1 − 𝑥) 1/(Δ𝐵 ) = 1 − + 𝑂 (𝑥 2 ). Δ𝐵 Hence 𝑥 1 − 𝑞 = 1 − (1 − 𝑥) 1/(Δ𝐵 ) = + 𝑂 (𝑥 2 ), Δ𝐵 which implies 2 2 2 2 Δ𝐵 Δ𝐵 1 = 𝑂 = 𝑂 . (1 − 𝑞) 2 𝑥2 𝛿 2Δ𝐵

where 𝑀 (𝑡 ) is deﬁned as in Lemma A.5. Lemma A.7. (Cumulative gradient bound). Under the same conditions as Lemma A.5, we get

1−

𝑇 −1 2 2(𝑓 (𝒙 (0) ) − 𝑓 ∗ ) 𝐿𝜂𝜎 2𝑇 9𝜂 2𝐿2𝐶 2 Õ (𝑡 ) ) ≤ E ∇𝑓 (𝒙 + 𝑃 (1 − 𝑞) 2 𝑡 =0 𝜂 𝑛 (0)

3𝐿2𝐶 2 (max𝑚 𝒙𝑚 ) 2 𝑃 (1 − 𝑞) 2

3𝜂 2𝐿2𝐶 2𝑛𝜎 2𝑇 9𝜂 2 𝐿2𝐶 2𝑛𝜁 2𝑇 + . 𝑃 (1 − 𝑞) 2 𝑃 (1 − 𝑞) 2 (29)

Proof. Substituting the bound on into (28) yields

Í𝑇 −1

𝑡 =0 𝑀

On the other hand,

𝐶2 =

Substituting this into the expression for 𝑇 , we obtain 2 2 Δ𝐵 24𝐿2𝐶 2 𝑆 = 𝑂 𝑇 = , (1 − 𝑞) 2𝜖 𝛿 4Δ𝐵

(0) 2 2 𝐿𝜂 2𝜎 2𝑇 3𝜂𝐿 𝐶 max𝑚 𝒙𝑚 3𝜂 3𝐿2𝐶 2𝑛𝜎 2𝑇 (0) ∗ ≤ 𝑓 (𝒙 ) − 𝑓 + + + 2𝑛 2𝑃 (1 − 𝑞) 2 2𝑃 (1 − 𝑞) 2 𝑇 −1 2 9𝜂 3 𝐿2𝐶 2𝑛𝜁 2𝑇 9𝜂 3𝐿2𝐶 2 Õ (𝑡 ) + + E ∇𝑓 (𝒙 ) . 2𝑃 (1 − 𝑞) 2 2𝑃 (1 − 𝑞) 2 𝑡 =0

where the big-𝑂 notation hides parameters independent of the mixing matrices. Proof of lemma 4.1. Fix an iteration 𝑡 and a node 𝑗. Let 𝑈𝑡 ( 𝑗) := (𝑡 ) 𝑁𝑡+ ( 𝑗)∪{ 𝑗 } and 𝛿𝑡 ( 𝑗) := min𝑖 ∈𝑈𝑡 ( 𝑗 ) 𝑊𝑖 𝑗 . Under column-stochastic mixing, we have Õ Õ 𝛿𝑡 ( 𝑗) = |𝑈𝑡 ( 𝑗)|𝛿𝑡 ( 𝑗), 𝑊𝑖 (𝑡𝑗 ) ≥ 1=

For 𝜂 ≤ 1/𝐿, the second term on the left-hand side is nonnegative. 𝜂 Hence, dropping it and dividing both sides by 2 , we obtain

𝑡 =0

E ∇𝑓 (𝒙

(𝑡 )

)

𝑖 ∈𝑈𝑡 ( 𝑗 )

2(𝑓 (𝒙 (0) ) − 𝑓 ∗ ) 𝐿𝜂𝜎 2𝑇 ≤ + 𝜂 𝑛 (0) 2 ) 3𝐿2𝐶 2 (max𝑚 𝒙𝑚

16 . 𝛿 2Δ𝐵

2 2 𝐶2 Δ𝐵 = 𝑂 . (1 − 𝑞) 2 𝛿 4Δ𝐵

Therefore, (𝑡 ) from Lemma A.5

" 2# 𝑇 −1 𝑇 −1 𝑛 2 𝜂Õ 𝜂 − 𝐿𝜂 2 Õ 1Õ (𝑡 ) (𝑡 ) + E ∇𝑓 (𝒙 ) E ∇𝑓𝑖 (𝒛𝑖 ) 2 𝑡 =0 2 𝑛 𝑖=1 𝑡 =0

𝑇 −1 Õ

Other Supporting Proofs

which implies min 𝑊𝑖 (𝑡𝑗 ) = 𝛿𝑡 ( 𝑗) ≤

3𝜂 2𝐿2𝐶 2𝑛𝜎 2𝑇

𝑖 ∈𝑈𝑡 ( 𝑗 )

+ 𝑃 (1 − 𝑞) 2 𝑃 (1 − 𝑞) 2 2 2 2 2 9𝜂 𝐿 𝐶 𝑛𝜁 𝑇 + 𝑃 (1 − 𝑞) 2 𝑇 −1 2 9𝜂 2𝐿2𝐶 2 Õ (𝑡 ) + . E ∇𝑓 (𝒙 ) 𝑃 (1 − 𝑞) 2 𝑡 =0

1 1 = . |𝑈𝑡 ( 𝑗)| 𝑑𝑡+ ( 𝑗) + 1

Equality holds if and only if 𝑊𝑖 (𝑡𝑗 ) = 1/(𝑑𝑡+ ( 𝑗) + 1) for all 𝑖 ∈ 𝑈𝑡 ( 𝑗). Then taking the minimum over all 𝑡 and all 𝑗 yields 𝛿=

min

min 𝛿𝑡 ( 𝑗) ≤

𝑡 ∈ {0,...,𝐵−1} 𝑗 ∈𝑉

min

𝑡 ∈ {0,...,𝐵−1} 𝑗 ∈𝑉

achievable under uniform weight assignment. 15

1 , 𝑑𝑡+ ( 𝑗) + 1

Conference’17, July 2017, Washington, DC, USA

Nguyen et al.

Proof of Lemma 4.4. Consider any vertex 𝑒 := (𝑖, 𝑗) ∈ 𝐸𝑎 in the conﬂict graph 𝐺𝑐 . Under the half-duplex constraint, (𝑖, 𝑗) conﬂicts with all links whose receiver is 𝑖 and all links whose transmitter is 𝑗. Hence, the number of conﬂicts from this condition is 𝑑𝑎− (𝑖) +𝑑𝑎+ ( 𝑗). Under the interference constraint, (𝑖, 𝑗) further conﬂicts with any link (𝑘, 𝑙) ∈ 𝐸𝑎 with 𝑘 ≠ 𝑖 such that {𝑘, 𝑗 } ∈ 𝐸 or {𝑖, 𝑙 } ∈ 𝐸. Let 𝑁𝐺 (𝑖) denote the neighborhood of node 𝑖 in 𝐺 (excluding 𝑖). The number of such conﬂicts is bounded by Õ Õ 𝑑𝑎− (𝑙) + (𝑑𝑎− ( 𝑗) − 1), 𝑑𝑎+ (𝑘) +

Proof of lemma 4.2. Within each 𝐵-iteration window with a ﬁxed activated graph 𝐺𝑎 , activating the same link multiple times is suboptimal, because it does not change 𝐵 or Δ, but may decrease 𝛿 or increase the required communication schedule length. Therefore, without loss of generality, we assume that no link is activated more than once within a 𝐵-iteration window, i.e., ∀ 𝑠 ≠ 𝑡, 𝑠, 𝑡 ∈ {0, . . . , 𝐵 − 1}.

𝐸𝑠 ∩ 𝐸𝑡 = ∅,

Under this assumption, the neighbor sets are disjoint across iterations, i.e., 𝑁 + ( 𝑗) ∩ 𝑁𝑡+ ( 𝑗) = ∅ for all 𝑠 ≠ 𝑡. Consequently, 𝑑𝑎+ ( 𝑗) = Í𝐵−1 + 𝑠 𝑡 =0 𝑑𝑡 ( 𝑗). It follows that

𝑘 ∈𝑁𝐺 ( 𝑗 )\{𝑖 }

where the last term counts other activated incoming links to 𝑗. Combining the two conditions, the degree of 𝑒 in 𝐺𝑐 satisﬁes Õ Õ 𝑑𝑎− (𝑙) 𝑑𝑎+ (𝑘) + 𝑑𝑐 (𝑒) ≤ 𝑑𝑎− (𝑖) + 𝑑𝑎+ ( 𝑗) +

𝑑 + ( 𝑗) 1Õ + ≥ , 𝑑𝑡 ( 𝑗) = 𝑎 𝐵 𝑡 =0 𝐵 𝐵−1

max

𝑡 ∈ {0,...,𝐵−1}

𝑑𝑡+ ( 𝑗)

and hence max

max 𝑑𝑡+ ( 𝑗) ≥

𝑡 ∈ {0,...,𝐵−1} 𝑗 ∈𝑉

𝐷𝑎+ , 𝐵

𝑘 ∈𝑁𝐺 ( 𝑗 )\{𝑖 }

𝑡

𝑗

𝑘 ∈𝑁𝐺 ( 𝑗 )\{𝑖 }

Proof of lemma 4.3. First, we prove that

𝑡 =0

(30)

Taking the maximum over all 𝑒 ∈ 𝐸𝑎 yields the result.

(33)

Proof of Theorem 5.1. We ﬁrst prove the strong connectivity of the constructed 𝐺𝑎 . After Step 2, 𝑇 must be a connected undirected graph. We will show that the way Step 3 orients the edges must turn this graph into a strongly connected directed graph. To this end, we will show that the orientation of edges in each bridgeconnected component 𝐶 will turn it into a strongly connected subgraph. Let 𝑟 denote the root of the DFS tree for 𝐶. We observe the following:

(𝑡 )

(𝐺 ) uled in the 𝑠-th transmission slot of iteration 𝑡 and {𝐸𝑡,𝑠 }𝜏𝑠=1 (𝑡 ) denote an optimal communication schedule for 𝐺 . Then concatenating these schedules for 𝑡 = 0, . . . , 𝐵 − 1 provides a feasible comÍ Ð 𝜏 (𝐺 (𝑡 ) ) (𝑡 ) ) for of length 𝑡𝐵−1 munication schedule 𝑡𝐵−1 =0 𝜏 (𝐺 =0 {𝐸𝑡,𝑠 }𝑠=1 𝐺𝑎 . Therefore, the length of the optimal communication schedule Í (𝑡 ) ). for 𝐺𝑎 , i.e., 𝜏 (𝐺𝑎 ), must be no greater than 𝑡𝐵−1 =0 𝜏 (𝐺 Next, we prove that + 4Δ𝐵 𝐷𝑎 𝐵 +1 ≥ (1 + 𝐷𝑎+ ) 4Δ . (31) 𝐵

(1) There must be a directed path from 𝑟 to any vertex 𝑣 in 𝐶 along the DFS tree since all the tree edges are oriented away from 𝑟 . (2) For any tree edge (𝑢, 𝑣) with 𝑝𝑟𝑒 (𝑢) < 𝑝𝑟𝑒 (𝑣), there must be a directed path from 𝑣 to 𝑢, as 𝑢 and 𝑣 must lie on a cycle in 𝐶 (since 𝐶 is 2-edge-connected) which must contain a back edge from some descendant of 𝑣 to some ancestor of 𝑢. (3) Repeatedly applying the argument in (2) implies that there is a directed path from any vertex 𝑣 in 𝐶 back to 𝑟 .

By Bernoulli’s inequality, for any 𝑢 ≥ 0 and integer 𝐵 ≥ 1, (1 + 𝑢)𝐵 ≥ 1 + 𝐵𝑢. Taking 𝑢 = 𝐷𝑎+ /𝐵 gives 𝐷+ 𝐵 1+ 𝑎 ≥ 1 + 𝐷𝑎+ , 𝐵 4Δ𝐵 𝐷 + 4Δ𝐵 𝐷𝑎+ +1 ≥ 1+ 𝑎 ≥ (1 + 𝐷𝑎+ ) 4Δ . 𝐵 𝐵

Combining observations (1) and (3) proves that our edge orientation turns each bridge-connected component into a strongly connected subgraph. Then connecting these subgraphs with bidirected links as in line 17 must yield a strongly connected graph. We now prove the bound in (20). When 𝐾 = 0, the graph 𝑇 in line 8 is a tree (i.e., the minimum-degree spanning tree), for which every edge is a bridge and each bridge-connected component is just a single vertex. In this case, the directed graph 𝐺𝑎 produced

Combining the above with 𝐵 ≥ 1 yields (31). Combining (30) with (31) yields 𝐹 (𝐵) ≥ 𝜏 (𝐺𝑎 )Δ2 (1 + 𝐷𝑎+ ) 4Δ , which is exactly 𝐹 (1).

𝑑𝑎− (𝑙) ≤ |𝑁𝐺 (𝑖) \ { 𝑗 }| 𝐷𝑎− ≤ (𝐷 − 1) 𝐷𝑎− .

𝑑𝑐 (𝑒) ≤ 𝐷𝑎− + 𝐷𝑎+ + (𝐷 − 1)𝐷𝑎+ + (𝐷 − 1)𝐷𝑎− + 𝐷𝑎− = (𝐷 + 1) 𝐷𝑎+ + 𝐷𝑎− .

Our cost model in Section 2.4 measures the communication cost of an activated graph by the length of the optimal (i.e., shortest) communication schedule. Let 𝐸𝑡,𝑠 denote the set of links of 𝐺 (𝑡 ) sched-

and hence

𝑙 ∈𝑁𝐺 (𝑖 )\{ 𝑗 }

Therefore, 𝜏 (𝐺 (𝑡 ) ) ≥ 𝜏 (𝐺𝑎 ).

(32)

𝑑𝑎− (𝑖) ≤ 𝐷𝑎− , 𝑑𝑎+ ( 𝑗) ≤ 𝐷𝑎+ , 𝑑𝑎− ( 𝑗) − 1 ≤ 𝐷𝑎− , Õ 𝑑𝑎+ (𝑘) ≤ |𝑁𝐺 ( 𝑗) \ {𝑖}| 𝐷𝑎+ ≤ (𝐷 − 1) 𝐷𝑎+ ,

1 1 1 = ≤ . 𝑑𝑡+ ( 𝑗) + 1 max𝑡 max 𝑗 𝑑𝑡+ ( 𝑗) + 1 ⌈𝐷𝑎+ /𝐵⌉ + 1

𝐵−1 Õ

𝑙 ∈𝑁𝐺 (𝑖 )\{ 𝑗 }

+ 𝑑𝑎− ( 𝑗) − 1.

We can bound each term as follows:

where the ceiling is because 𝑑𝑡+ ( 𝑗) is an integer. Therefore, max 𝛿 =min min

𝑙 ∈𝑁𝐺 (𝑖 )\{ 𝑗 }

Optimizing Stochastic Gradient Push under Broadcast Communications

Conference’17, July 2017, Washington, DC, USA

by Step 3 is just the bidirected version of 𝑇 . This implies that its maximum in/out-degree 𝐷𝑎− /𝐷𝑎+ and diameter Δ satisfy (34)

Plugging (34) into (19) yields the right-hand side of (20). The proof completes by noting that optimizing 𝐾 can further reduce the achieved value of (19).

0.3 0.2

0.003 0

50000 100000 150000 200000 250000 300000 350000 400000

Total transmissi n sl ts

50000 100000 150000 200000 250000 300000 350000 400000

T tal transmissi n sl ts

Bidirected active link Directed active link Inactive link

Testing Err r

0.8

Additional Evaluation Results

Bidirected active link Directed active link Inactive link

0.5

0.01

0.005

Training L sses

A.3

Testing Err r

Δ = Δ∗ .

Training L sses

𝐷𝑎− = 𝐷𝑎+ = 𝐷 ∗ ,

0.8

0.5

0.01

0.3

0.005

0.2

0.003 0

100

200

300

Ep chs

Vanilla DPSGD Vanilla SGP

400

MATCHA BASS heuristic

500

100

200

BASS ptimized pr p sed with ut step 4

300

Ep chs

pr p sed

Figure 13: Ablation study on Roofnet. (a) RG

(b) Roofnet

Figure 11: Designed communication graph without Step 4. As an ablation study to evaluate the value of Step 4 in Alg. 1, we evaluate the learning performance of a variation of the proposed solution without this step (i.e., directly using 𝐺𝑎 obtained after Step 3 of Alg. 1 as the communication graph). Fig. 11 shows the resulting designs, which are much sparser than the communication graphs designed with Step 4 (Fig. 6 and 9). The training results in Fig. 12–13 show that omitting the cost-preserving link augmentation in Step 4 causes a clear performance degradation in terms of both the logical convergence rate (in epochs) and the physical convergence rate (in slots). This observation validates the value of Step 4 in improving the actual learning performance, even though it is not guaranteed to improve the abstract design objective (19).

Testing Err r

Training L sses

0.8

0.5

0.01

0.3

0.005 0.003

0.2 0

50000 100000 150000 200000 250000 300000 350000

Total transmissi n sl ts

50000 100000 150000 200000 250000 300000 350000

T tal transmissi n sl ts

Testing Err r

Training L sses

0.8

0.5

0.01

0.3

0.005 0.003

0.2 0

100

200

300

Ep chs

Vanilla DPSGD Vanilla SGP

400

MATCHA BASS heuristic

500

100

200

BASS ptimized pr p sed with ut step 4

300

Ep chs

400

500

pr p sed

Figure 12: Ablation study on RG.

400

500

Record · ID 31251 · SHA-256 ba4c3f99ad61e889
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.