B-ary Tree Push-Pull Method is Provably Efficient for Distributed Learning on Heterogeneous Data
Authors: Runze You
Shi Pu
Venue: NeurIPS 2024 poster (2024)
Keywords: Distributed Learning
Distributed Optimization
Stochastic Optimization
Primary area: optimization

Abstract: This paper considers the distributed learning problem where a group of agents cooperatively minimizes the summation of their local cost functions based on peer-to-peer communication. Particularly, we propose a highly efficient algorithm, termed ``B-ary Tree Push-Pull'' (BTPP), that employs two B-ary spanning trees for distributing the information related to the parameters and stochastic gradients across the network. The simple method is efficient in communication since each agent interacts with at most $(B+1)$ neighbors per iteration. More importantly, BTPP achieves linear speedup for smooth nonconvex objective functions with only $\tilde{O}(n)$ transient iterations, significantly outperforming the state-of-the-art results to the best of our knowledge.

B-ary Tree Push-Pull Method is Provably Efficient for Distributed Learning on Heterogeneous Data
Runze You' Shi Pu
'The Chinese University of Hong Kong, Shenzhen runzeyou@l ink. cuhk. edu. en, pushi @cuhk. edu. cn
Abstract
This paper considers the distributed learning problem where a group of agents cooperatively minimizes the summation of their local cost functions based on peer-to-peer communication. Particularly, we propose highly efficient algorithm, termed "B-ary Tree Push-Pull" (BTPP), that employs two B-ary spanning trees for distributing the information related to the parameters and stochastic gradients across the network. The simple method is efficient in communication since each agent interacts with at most (B + 1) neighbors per iteration. More importantly, BTPP achieves linear speedup for smooth nonconvex and strongly convex objective functions with only (n) and (11 transient iterations, respectively, significantly outperforming the state-of-the-ee art results to the best our knowledge. Our code is available at https:://ithhu.. httpa///ooooooooo//////1
Introduction
In this paper. we consider group of agents, labeled as N {1, 21,2.... nz, in which each agent i holds own local cost function f. : Rº E and communicates only within its direct neighborhood. We investigate how the agents collaborate to locate x E 12 that minimizes the average of all the cost functions:
1 n (
-
min f(x) #ERP
where fi(z) = BEEND, [F)( Here denotes the local data of agent that follows the local distribution D:, Data heterogeneity exists if (Di are not identical.
To solve problem (T). we assume each agent queries stochastic oracle (SO) to obtain noisy gradient samples. Stochastic gradients appear many areas including online distributed learning
23 3 Assumption 1.1 ensures that the gradient estimator (2; Ex) remains unbiased with a bounded variance for any given while independent samples & are gathered continuously over time. In addition, the assumption is critical simulation-bas bbased optimization as gradient estimation often encounters noise from multiple sources, such as modeling and discretization errors, or limitations due to finite sample sizes in Monte-Carlo methods 77]
reinforcement learning [17 [5], generative modeling [5] 6). and parameter estimation 27
Modern optimization and machine learning typically involve tremendous data samples and model parameters. The scale of these problems calls for efficient distributed algorithms across multiple computing nodes. Recently, distributed algorithms dealing with problem (T) have been studied extensively the literature; see, e.g., [19
34 Traditional distributed Tearbbinnnnerrnnnn approaches typically follow centralized master worker setup, where each worker node communicates with (virtual) central server
[12]. However, such communication pattern incurs significant communication overheads and long latency, especially when the training requires a large number of computing nodes.
*Corresponding Author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Decentralized learning is an emerging paradigm to save communication costs, where the computing nodes are connected through a certain network topology (e.g., ring, grid, hypercube). Decentralized algorithms do not rely on central servers: the agents maintain the similarity among their copies of model parameters through peer-to-peer messages passing by communicating locally with immediate neighbors in the network. Such setup allows each node to communicate with only a few peers and hence incurs much lower communication overhead [T. Moreover, it offers strong promise for new applications, allowing agents to collaboratively train model while respecting the data locality and privacy of each contributor.
Specifically, in decentralized stochastic gradient methods, the agents share their local stochastic gradient updates through gossip communication [32]. At every iteration, the local updates are sent to the neighbors of each agent who iteratively propagate the information through the network. Typically, the agents employ iterative gossip averaging of their neighbors' models with their own, where the averaging weights are chosen to ensure asymptotic uniform distribution of each update across the network. However, local averaging less effective in "mixing" information which makes decentralized algorithms converge slower than their centralized counterparts. Generally speaking, the network topology determines both the number of per-iteration communications and the convergence rates of decentralized algorithms, leading to a trade-off. For example, a densely-connected graph enables decentralized methods to converge faster but results in less efficient communication since each node needs to communicate with more neighbors. By contrast, results in a slower convergence rate but also reduces the per-iteration communication cost [9 21 B5]. In particular, for smooth and non-convex objective functions, it has been shown that decentralized stochastic gradient methods (with arbitrary topology) can achieve the same convergence rate as the centralized SGD method, but only after initial period of iterations has passed [14 34 20)
pparsely-conneete topology
The number of transient iterations (transient time) heavily depends on the network topology, and thus practical decentralized stochastic gradient algorithm should aim minimize the transient time while keeping the number of per-iteration communications small (e.g., over a a sparsely- connected topology). Such an observation has motivated several recent works, which consider network topologies with ((1) per-iteration communications (or degree) for each node; see, e.g..
34 26
This work considers an alternative mechanism to gossip averaging, called "B-ary Tree Push-Pull" (BTPP), inherited from the Push-Pull method in [2 33 Rather than relaying the messages over one graph at every iteration, BTPP uses two B-ary trees (GR and Gc) to spread the information about the parameters and the stochastic gradients, respectively. Each agent assigned in the B-ary tree acts as a worker on an assembly line. The model parameters are transmitted through the graph GR from the parent nodes the child nodes. Meanwhile, the stochastic gradients are computed under the current model parameters and accumulated through the inverse graph of GR denoted as Gc. BTPP can be viewed as a edeeetddeeeet approach given the critical role of node Notably, the corresponding mixing matrices of GR and Ge only consist of O's and I's, which together with the B-ary Tree topology design, results in high algorithmic efficiency. We show BTPP achieves an (()) transient time under smooth nonconvex objective functions with ((1) per-iteration communications for each agent. By comparison, the state-of-the-a transient time is O ((z²) (see Table
1.1 Related Works
Decentralized Learning Decentralized Stochastic Gradient Descent (DSGD) type algorithms are increasingly popular for accelerating the training of large-scale machine learning models 14 34] 10)
These algorithms have been adapted under a range of practical settings, including those discussed in 16). However, DSGD suffers from data heterogeneity [9], which triggers more advanced techniques such as EXTRA (25), Exact-Diffusion/DD [13], and gradient tracking [19]. The Push-Pull method 22 [33 which enjoys broad topological requirements
introduced for deterministic
decentralized optimization under strongly convex objectives. This work particularly takes advantage of the flexibility in the network design of Push-Pull, utilizing the B-ary tree family, while considering stochastic gradients for minimizing smooth nonconvex objectives.
Topology Design Decentralized stochastic gradient algorithms often rely on gossip averaging over various topologies such as rings, grids, and tori [18] The hypercube graph (30) strikes a balance
between the communication efficiency and the consensus rate, but the network size constrained to be the power of two. The work in [34] re-examined the static exponential graph with ((I((z))

---

ALGORITHM
PER-ITER COMM.
SIZE n
BASED GRAPH
TRANS. ITER.
Dd (RING)
29
@(1)
ARBITRARY
((n
DSGD (RING)
@(1)
ARBITRARY
((m²)
HYPERCUBE
30
((m(n))
POWER OF 2
O
STATIC EXP.
(In(n)
ARBITRARY
(n
O.-P. EXP.
34
POWER
(lu(m))
RELAYSGD
@(1)
ARBITRARY
O(n
OD(OU)-
26
ARBITRARY
((n)
O
DSGD-CECA
@(1)
ARBITRARY
(Iu(n))
BASE-(k:
28
((1)
ARBITRARY
(In(m))
O(
BTPP (OURS)
(1) ARBITRARY
Table 1: Comparison of different algorithms for distributed stochastic optimization under smooth nonconvex objectives. "Per-iter Comm." " denotes the number of per-iteration communications or neighbors (degree) for each agent. "Based Graph" represents the number of required graph topologies during the entire training procedure. "Trans. Iter." represents the number of transient iterations. The notation (.) hides all the polylogarithmic factors.
ALGORITHM
PER-ITER COMM.
SIZE
BASED GRAPH
TRANS. ITER.
DSGD (RING)
@())
ARBITRARY ARBITRARY
Ön
STATIC EXP.
34
(Iu(n))
1
O.-P. EXP.
POWER OF 2
((m(m))
(
RELAYSGD
@(1)
ARBITRARY
((n)
26
ARBITRARY
@(n)
Ó(n)
BTPP (OuRS)
(1)
ARBITRARY
2
Ö(1)
Table 2: Comparison of different algorithms for distributed stochastic optimization under smooth strongly convex objectives. The notation (-) hides all the polylogarithmic factors inheriting from 26 9].
degree and introduced one-peer exponential graph with @(1) degree while preserving the consensus properties under the specific requirement of n. The paper [28 proposed a base-(k: 1) graph as an enhancement that achieves similar convergence rate as 34 under arbitrary network size by sequentially employing multiple graph topologies (splitting an all-connected graph into (In(n)) different subgraphs). DSGD-CEĆA 4 requires roughly [nog rounds of message passing for global averaging with ((n) network topologies. OD(OU)-EquiDyn [26) introduces algorithms that employ various topologies achieve network-size independent consensus rates. RelaySGD
31 offers relay-based algorithm that ensures @(1) per-iteration communication across different topologies.
The Above-mentioned methods all enjoy comparable convergence rates with centralized SGD (and thus achieves linear speedup) when the number of iterations T is large enough. The transient times are generally in the order of (n²3) under smooth nonconvex objectives (see Table 1 and ((n) under smooth strongly convex objectives (see Table 2
Note that the above works and this paper generally consider training machine learning modes within high-pperformacc data-center clusters, in which the network topology can be fully controlled: any two nodes can directly communicate over the network when necessary. comparison, some other scenarios, the underlying network topology is fixed, and the communication between two nodes is constrained (c.g., wireless sensor networks, internet of vehicles, etc).
1.2 Main Contribution
This paper introduces a novel distributed stochastic gradient algorithm, termed "B-ary Tree Push-Pull" (BTPP), which provably efficient for solving the distributed learning problem 1 under arbitrary network size. The main contribution is summarized as follows:

---

BTPP incurs (1) communication overhead per-iteration for each agent. Specifically, any agent in the network communicates with most (B + 1) neighbors, where B can be freely chosen to fit different settings. Generally speaking, larger B increases the per-iteration communication cost but reduces the transient time at the same time.
We show BTPP enjoys an (n) transient time iteration complexity under smooth non- convex objectives and an (1) transient time iteration complexity under smooth strongly convex objectives, Such results outperform the baselines: see Table 1 and Table 2 The im- provement is significant since the transient time greatly impacts the algorithmic performance. especially under large n.
The convergence analysis for BTPP is non-trivial, partly due to the fact that the algorithm admits two different network topologies for communicating the model parameters and the (stochastic) gradient trackers respectively. Instead of constructing the induced matrix norms || || and || ||c in (22), the analysis is performed under ||-1|2 and |I-I|,- only by carefully treating the matrix products and related terms.
1.3 Notation and Preliminaries
Throughout the paper, vectors default to columns if not otherwise specified. Let each agent i hold
a local copy I; E R2 of the decision variable and an auxiliary variable y: E Rp. Their values at iteration & are denoted by z (k) and 0i*,), respectively. We let X [21, ,Tn] E <Rx Y = [y1, .2. yn]] E R=x,, and 1 denotes the column vector with all entries equal to 1. We also define the aggregated gradients at the local variables as VF(X) == (V fi (x1), Vf2(22), ... fn.,)))] E Rexp, where F(X) = Ei=Is((;;). Ji(x;). In addition, denote == [5, ... G(X, == (ii,,i),g2(00 E2), ... :9n (2n; En)]" E "R* For the conciseness of presentation, we also use G to represent (( ())). The term (a, b) stands for the inner product of two vectors a, b E RP. For matrices, I|-II, and ||-IIr represent the spectral norm and the Frobenius norm respectively, which degenerate to the Euclidean norm for vectors. For simplicity, any square matrix with power 0 is the unit matrix I with the same dimension if not otherwise specified.
We assume each agent is able to obtain noisy gradient samples of the form g, (2, {,) that satisfies the following assumption.
Assumption 1.1. For all i E N and R', each random vector & is independent and
BgwD (a, [x] = fi(),, EA [loc(2, Et) - ff((2)) |x] s s²²
for some 2² 0.
Regarding the individual objective functions fi, make the following standard assumption. Assumption 1.2. Each fx()) R + R is lower bounded with L-Lipschitz continuous gradients, i.e., for any x, x' E R".
I (x) - (x(')l < L | x'1l
We also consider the following standard assumption regarding strongly convexity. Assumption 1.3. For any v,y RRP
1 1ly - x x112. 2
f(v) 2 f(x) + (Vf(z), y - x)
Denote f minzeRs f(x). Let x = arg ming fz) if Assumption 1.3 holds.
directed graph G(N,E) consists of a set of n nodes A and a set of directed edges & C W x M, where edge (j, E indicates that node j can directly send information to node i. To facilitate the local averaging procedure, each graph can be associated with a non-negative weight matrix W = [way] x whose element Wij is non-zero only if (j, i) E E. Similarly, non-negative weight matrix W corresponds to a directed graph denoted by Gw. For given graph Gw. the in- neighborhood and ouihheigboorhood of node N are given by NW. := ti e N (j, E} and Nout : [j E (i,j) E E), respectively. The degree of node i the number of its in-neighbors or neighoog,. For example, in one-peer graph, the degree of each node is at most 1.

---

1.4 Organization of the Paper
The rest of this paper is organized as follows. In Section we introduce the B-ary Tree Push-Pull
algorithm and present its main convergence results. The sketch of analysis is presented in Section 3
and numerical experiments are provided in Section 4 We conclude the paper Section F
2 B-ary Tree Push-Pull Method
2.1 Communication Graphs
The proposed B-ary Tree Push-Pull method makes use of two spanning trees communication graphs: GR and Gc, which correspond to two mixing matrices R and C, respectively. Specifically, we consider B-ary tree graphs with arbitrary number of nodes n and depth d. The root node is labeled as 1 for convenience, and we index the nodes layer-by-layer. The additional nodes are placed at the last layer if the tree is not full. Figure I Tree GR (the left ones), each node has parent node and B child nodes (except the ones in the last layer). The root node has parent node. In the Push Tree Ge (the right ones), each node has 1 child node and B parent nodes (except the ones in the last layer). It can be seen that the tree Ge is identical GR with all the edges reversing directions. Note that only node has self-loop.
Tillustrates the assignment of 10 nodes when B 2. In the Pull
Figure I: Two spanning trees with 10 nodes when B On the left GR, and the right one is Gc-
2.2
Algorithm
We consider the following distributed stochastic gradient method (Algorithm | for solving problem [ At every iteration t. each agent pulls the state information from its in-neighborhood N pushes its (stochastic) gradient tracker ys to the out-neighborhood Nout and updates its local variables v; and y; based on the received information. The agents aim to find the e-stationary point jointly by performing local computation and exchanging information through two spanning trees.
More specifically, in the pull tree GR. each node i pulls the updated model from its parent node along the tree. Note that Nan consists of only one node, the parent node. The Push Tree Se is R. the inverse of the Pull Tree, which each node collects and aggregates the gradient trackers from its parent nodes. Due to the tree structure, only yi aggregates and tracks the stochastic gradients across the entire network, which will be made clear from the analysis. The implementation of the algorithm is rather simple. Taking node 2 in Figure as an example, we have x2
(t+1) x1 - ry/"
and y/2 (t+1) 1 + ys
(t) + 02(2x g/ ( g2 (2 (0) (
We can write Algorithm in the following compact form:
x R ((()) - y
(2)
(t- = -CY()) + G(X(++1) g( - (9 -(X() (())
where ( = G (0) (())), and R.C. pxxn are non-negative matrices whose elements are given by
(1
if [Bj - B BB [n] or j-1
[R), {1 otherwise
and - which corresponds to Gc, the inverse tree of GR. can be seen that R. is row-stochastic matrix that only consists 0's and 1's and C is column stochastie. For example, the mixing matrices corresponding to the graphs in Figure are given by
5

---

Algorithm B-ary Tree Push-Pull Method (BTPP)
1: Each agent i initializes with any arbitrary but identical x; (0) x0) RR, RR,,y,
(0)
9r (2. (0)
(1)
Rº after drawing random sample ( stepsize y > 0 and number of iterations T. . 0.1,2....;
2: for iteration t
do
3:
for agent i in parallel do
4: Pull /j 7My (t) from each Ain R.
5: Push yi each j Ne..
6:
Independently draw random sample Update parameters through
< ((++1)
7:
((-1) = Σ
(2)
-10
JEN Ri
(1-1) Σ
(1)
+ ge(2 (x(x,tt)) ; ;
Vi
Vj
JENS
8:
end for
9:
end for
Output 21 (T)
1
11
R
C
1
1
1
where the unspecified elements are zeros.
2.3
Main Results
The main convergence properties of BTPP are summarized in the following two theorems, where the second result assumes strongly convexity on
Theorem 2.1. For the BTPP algorithm outlined in Algorithm
7 implemented on B-ary
tree graphs GR. and Gc, assume Assumption T.I and Assumption
1.2 hold.
Let 7
min
The following convergence result holds:
La
100
32 32 240 (0²L2A3)
V ff 1
800d LA,
())
E
T+1
(n(T+1) (Vn(T 1))
T+1
n(T + 1)
L=0
where A, = [(x] f and d [log](n)] represents the diameter of the graphs.
Remark 2.2. Based on the convergence rate in (3) of BTPP, we can derive that when
On 12 (n)), the term O vnr dominates the remaining terms up to a constant scalar. This
implies that BTPP achieves linear speedup after O (n)) transient iterations.
Remark 2.3. The convergence rate (3) is related to the branch size B. For larger B. the diameter = [log becomes smaller, which results in more efficient transmission of information and
fewer transient iterations. However, the per-iteration communication cost is relatively larger. When B is smaller, the communication burden for each agent at every iteration is lighter, but the transient time is larger. Therefore, practice, the communication cost and convergence rate can balanced by considering a proper B.

---

Theorem 2.4. For the BTPP algorithm outlined in Algoritim 7 implemented on B-ary tree graphs GR. and Gc, assume Assumption
1.1 Assumption 1.2 and Assumption L.3 hold. Let
16log(((T+13)
y min 100ndReL
and T 2d. The following convergence result holds:
a(T+1)p
2240 log(n(T + 1)3)
26880000d" (log(n(T + +1)2))²
B
x¹
n (T + -1) 12
m2 (T" + 1)a 42
(4)
exp( 800d2 ) 40
T
(1|470)
VF(X
+ max
+ nL?
(T 1)²
Remark 2.5. The convergence rate in
implies that EE 1 x=
(NT nT2 + exp (-T)) where Ô hides the constants and polylogarithmic factors. The transient time is thus ((), i..., the number of iterations before the term O dominates the remaining terms. Such transient time also outperforms the state-of-the-art results.
3 Analysis of B-ary Tree Push-Pull
In this section, we study the convergence of BTPP and prove Theorem 2.1 by analyzing the properties of the weight matrices R and C, the evolution of the aggregated consensus error Σ E |I, (t) 2 and the expected inner products of the stochastic gradients between different layers. The approach is different from those employed in [22] 19 [26]. where the analysis considers two special matrix norms related to R. and C, respectively. Such distinction is because BTPP works with two B-ary trees and iterates in layer-wise manner, while most other works consider connected graphs.
g'
Our analysis starts with characterizing the weight matrices R and C, as delineated in the following lemmas. important note that for any given and a specific integer B, we can determine an integer d satisfying Bd
B-T I B-T which is the diameter of the graphs.
Bd+1_
Notice that R has unique non-negative left eigenvector u (w..t. eigenvalue 1) with u More specifically, u [nz, O.... .0] eigenvalue 1), denoted by v for the clarity of presentation, Following the above observations, is revealed in Lemma 3.1 that the 2-norm of the matrix R R- 1 lu with exponent & remains bounded
0]
which is also the unique right eigenvector of C. (w.rt.
by v and equals zero when is exceeds d -
Lemma 3.1. Given positive integer k, the 2-norm of the matrix Rk 1uu satisfies
S nn
$ d-1
IIR
LuT
lu
12
k d
Similar result applies to the matrix C² 1 T. Consequently, we introduce the mixing matrices Iy, II based on the eigenvectors u, v, which play crucial role in the follow-up analysis.
1 IVIT.
I1
lu N.
n
n
The following lemmas delineate the critical elements for constraining the average expected norms of the objective function as formulated in (I). i.c.,
- Σt E [V/a" Lemma 3.2 and
Lemma 3.3 provide bounds on the expressions Et (++1) X and En
II,
X 2
where ( 1 (t)
Lemma 3.2. Suppose Assumption I.1 holds and 7 10ndL
1
have the following inequality:
II, x() 2
Σ B x (+1) (+)
2 (T 1) + 50 d
+ n6?2nd ) + 2 V (9
7

---

Lemma 3.3. Suppose Assumption 1.1 holds and 40nd2L. we have for d 2 2
that
T
T
- 20000'n2d + 1)o² + 20, d II (8)
+ n VF(X (0)
+ 6nd
From the design of BTPP, there is an inherent delay in the transmission of information from layer to layer 1. As information traverses through the B-ary trees, the delay becomes evident. Specifically. for nodes at layer k, their information requires an additional k: iterations to successfully reach and impact node 1, as demonstrated in Lemma 3.4
Lemma 3.4. For any integert > 1, we have
min(t.d)
(o), u 17
Σ E
Am (G(l-m) ( 0,
where Am = Cm- and A1 C
Building on the preceding lemmas, we are in a position to establish the main convergence result for the BTPP algorithm. This involves upper bounding the expected norm for the gradient of the objective function evaluated at =1 To show the result, we integrate the findings from Lemma 3.2
Lemma 3.3 and Lemma 3.4, as detailed in Lemma 3.5
Lemma 3.5. Suppose Assumption
1.1 and Assumption
1.2 hold and 5 100nd we have
80, + +4400² L + ond
S
T+1
(T + 1)
400d 2 II,
56yd L VI )
T+1
T+1
Remark 3.6. Lemma 3.5 implies that the transient time of BTPP under Assumption 1.2 influenced
by the fourth term in the upper bound: 100d" L² [I,,
which is related to the initial consensus
T+1
error. Therefore, we initialize all the agents with the same solution 20))
Under strong convexity of f. we have the following key lemma. Lemma 3.7. Suppose Assumption we have
1.1 Assumption 1.2 and Assumption
1.3 hold, and r S To
E
x (T)
x²'
$ (1 10--y |
nap T
+ no² (T + 1) + 21000 n r2Lo² (T+
n2
+ ndd (1 (1-44) 177 T-d
|| VF(X + 420 30 2
I1, x
where K == L/p is the conditional number.
4
Numerical Results
This section presents experimental results to compare the B-ary Tree Push-Pull method with other popular algorithms on logistic regression with synthetic data and deep learning tasks with real data.
4.1 Logistic Regression
We compare the performance of BTPP against other algorithms listed in Table [ for logistic regression
with non-convex regularization (26.. The objective functions fa RRP - R are given by
f(())
1 =
Σ
In (1 exp(- + R
k
8

---

where 2|g] is the k-th element of and { ((e,).Bt,5)) )t To control the data heterogeneity across the nodes, we first let each node i be associated with v/s where ~ (N Ip) common random vector, and v; of) are random vectors generated independently. Therefore, { decide the dissimilarities between ž4. and larger σn generally amplifies the difference. After fixing { local data samples are generated that follow distinct distributions. For node the feature vectors are generated as h4.5 ~ (0, Ip), and 2t, ~ (0, 1). Then, the labels Vi,j E f-1,11
represent the local data kept by node i.
local logistic regression model with parameter ã; generated by म
are set to satisfy 2..j S 1 + exp(-Mt,hh.,,)
In the simulations, the parameters set follows:
100, p 500, J 1000, R = 0.01, and Th = 0.8. All the algorithms initialize with the same stepsize y = 0.3, except BTPP, which employs modified stepsize 7/n. Such an adjustment is due to BTPP's update mechanism, which incorporates a tracking estimator that effectively accumulates n times the averaged stochastic gradients as the number of iterations increases. This can also be Additionally, we implement a stepsize decay of 60% every 100 iterations to facilitate convergence.
from the stepsize choice in Theorem 2.1
In Figure 2 the gradient norm is used metric to gauge the algorithmic performance of each algorithm. The left panel of Figure iilustrates the comparative performance of various algorithmss highlighting that BTPP (in red) achieves faster convergence than the other algorithms with (1) degree and closely approximates the performance of the centralized SGD algorithm (i.e., DSGD- TullyConnected). The right panel of Figure demonstrates the behavior of BTPP when increasing the branch size B. is observed that with larger B, the convergence trajectory of BTPP more closely aligns with that of centralized SGD, corroborating the prediction of the theoretical analysis.
STW (8-2)
000
OSGO Dopentaa
07T 19-230
05653
0520-
Fabu5500 6:
Figure 2: Left: performance of algorithms for logistic regression with nonconvex regularization, where the dotted lines correspond to algorithms whose degrees are not ((1). We let the branch size B 2 in BTPP, 17 0.5 in OD-EquiDyn, k 2 in Base-(k + 1), and perform RelaySGD on a binary tree graph for fairness. Right: performance of BTPP with different branch size B.
4.2 Deep Learning
We apply BTPP and the other algorithms to solve the image classification task with CNN over MNIST dataset [II). We all experiments server with eight Nvidia RTX 3090 GPUs. The network contains two convolutional layers with max pooling and ReLu and two feed-forward layers. In particular, we consider heterogeneous data setting, where data samples are sorted based on their labels and partitioned among the agents. The local batch size is set to 8 with 24 agents in total. The learning rate is 0.01 for all the algorithms except BTPP (which employs a modified stepsize 7/n) for fairness. Additionally, the starting model is enhanced by pre-training using the SGD optimizer on the entire MNIST dataset for several iterations. Figure illlustaates the training loss and the test accuracy curves. Comparing the performance of different algorithms, it can be seen that BTPP (in red) and DSGT with ODEquiDyn (based on (nn) graphs) achieve faster convergence than the
Note that this particular configuration results in slower convergence for BTPP during the initial O(d) iterations, which can be improved by using larger initial stepsizes.

---

other algorithms with (1) degree and closely approximate the performance of centralized SGD(i.e., (SGD-FullyCoomeeteee).
Train Loss
Test Accuracy
0.86
h:00 Rag
14
0.80
14
DIPP
og
PANT
DSGD Cop
02
0.63
D500 Roee (3+1)
D5GT-20EquDyn B34ingg
64
B500-Ge:
2000
4000
6000
10000
12000
Ilrrtoon
Boration
Figure 3: Train loss and test accuracy of different algorithms for training CNN on MNIST, where the dotted lines correspond to the algorithms whose degrees not (1). We perform BTPP with 2, Oyn with rj = 0.5, Base-(k + 1) with and RelaySGD on a binary tree graph for faimess..
Remark 4.1. Higher accuracy can achieved for BTPP and other methods when using the momentum technique, or when the data heterogeneity is removed, meaning that samples are randomly assigned to each agent. Additional experiments demonstrating the performance of various algorithms across different tasks and scenarios are provided in Appendix B
5
Conclusions
This paper proposes a novel algorithm for distributed learning over heterogeneous data, named BTPP. The convergence is theoretically analyzed for smooth non-convex stochastic optimization. The results demonstrate that, at the minimal communication cost per iteration, BTPP achieves linear speedup in the number nodes n, and the transient times behaves as (n)) and Ô(1) respectively for smooth nonconvex and strongly convex objectives, outperforming the state-of-the-aar art results, Numerical experiments further validate the efficiency of BTPP.
10

---

References
[1] M. ASSRAN, N. LOIZOU, N. BALLAS, AND M. RABBAT, Stochastic gradient push for distributed deep learning, in International Conference Machine Learning, PMLR, 2019, pp. 344-353.
[2] L. BOTTOU, Stochastic gradient descent tricks, in Neural Networks: Tricks of the Trade: Second Edition, Springer, 2012, pp. 421-436.
[3] J. DEAN, G. CORRADO, R. MONGA, K. CHEN, M. DEVIN, M. MAO, M. RANZATO,
A. SENIOR, P. TUCKER, K. YANG, Al.., Large scale distributed deep networks, Advances in neural information processing systems, 25 (2012).
[4] L. DING, K. JIN, B. YING, K. YUAN, AND W. YIN, Dsgd-ceca: Decentralized sgd with communication-opiin exact consensus algorithm, arXiv preprint arXiv:2306.00256, (2023).
[5] I. GOODFELLOW, J. POUGET-ABADIE, M. MIRZA, B. XU, D. WARDE-FARLEY, S. OZAIR, A. COURVILLE, AND Y. BENGIO, Generative adversarial nets, Advances in neural information processing systems, 27 (2014).
[6] D. P. KINGMA, M. WELLING, ET AL., An introduction to variational autoencoders, Founda- tions and Trends@ in Machine Learning, 12 (2019), pp. 307-392.
[7] P. KLEIJNE, Design and analysis of simulation experiments, Springer, 2018.
[8] A. KOLOSKOVA, T. LIN, AND S. U. STICH, An improved analysis of gradient tracking for decentralized machine learning, Advances in Neural Information Processing Systems, 34 (2021), pp. 11422-11435.
[9] A. KOLOSKOVA, N. LOIZOU, S. BOREIRI, M. JAGGI, AND S. STICH, unified theory of decentralized sgd with changing topology and local updates, in International Conference on Machine Learning, PMLR, 2020, pp. 5381-5393.
[10] A. KOLOSKOVA, S. STICH, AND M. JAGGI, Decentralized stochastic optimization and gossip algorithms with compressed communication, in International Conference Machine Learning, PMLR, 2019, pp. 1478-3487.
[11] Y. LECUN, C. CORTES, C. BURGES, ET AL., Mnist handwritten digit database, 2010.
[12] M. LI, G. ANDERSEN, W. PARK, A. J. SMOLA, A. AHMED, V. JOSIFOVSKI, LONG, E. J. SHEKITA, AND B.-Y. SU, Scaling distributed machine learning with the parameter server, 11th USENIX Symposium on operating systems design and implementation (OSDI 14), 2014, pp. 583-598.
[13] Z. LI, W. SHI, AND M. YAN, A decentralized proximal- -rraiiintt method with network indepen- dent step-sizes and separated convergence rates, IEEE Transactions on Signal Processing, 67 (2019), pp. 4494 4506.
[14] X. LIAN C. ZHANG, H. ZHANG, C.-J. HSIEH, W. ZHANG, AND J. LIU, Can decentralized algorithms oufperform centralized algorithms? ? case study for decentralized parallel stochastic gradient descent, Advances in neural information processing systems, 30 (2017).
[15] T. P. LILLICRAP, J. J. HUNT, A. PRITZEL. N. HEESS, T. EREZ, Y. TASSA, D. SILVER, AND D. WIERSTRA, Continuous control with deep reinforcement learning, arXiv preprint arXiv:1509.02971, (2015).
[16] T. LIN, S. P. KARIMIREDDY, S. U. STICH, AND M. JAGGI, Quasi-global momentum: Accel- erating decentralized deep learning on heterogeneous data, arXiv preprint arXiv:2102.04711. (2021).
[17] V. MNIH, K. KAVUKCUOGLU, D. SILVER, A. GRAVES, I. ANTONOGLOU, D. WIER- STRA, AND M. RIEDMILLFR, Playing atari with deep reinforcement learning, arXiv preprint arXiv:1312.5600 (2013).
11

---

[18] A. NEDIĆ, A. OLSHEVSKY, AND M. G. RABBAT, Network topology and communication computation tradeoffs in decentralized optimization, Proceedings of the IEEE, 106 (2018), pp. 953-976.
[19] S. PU AND A. NEDIĆ, Distributed stochastic gradient tracking methods, Mathematical Pro- gramming, 187 (2021), pp. 409-457.
[20] S. PU, A. OLSHEVSKY, AND I. C. PASCHALIDIS, Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent, IEEE signal processing magazine, 37 (2020), pp. 114-122.
[21] S. PU, A. OLSHEVSKY, AND I, C. PASCHALIDIS, A sharp estimate on the transient time of distributed stochastic gradient descent, IEEE Transactions on Automatic Control, 67 (2021),
pp.
[22] S. Pu, W. SHI, J. XU, AND A. NEDIĆ, Push-pull gradient methods for distributed optimization networks, IEEE Transactions on Automatic Control, 66 (2020), pp. 1-16.
[23] B. RECHT, C. RE, S. WRIGHT, AND F. NIU, Hogwild!: A lock-free approach to parallelizing stochastic gradient descent, Advances in neural information processing systems, 24 (2011).
[24] S. RESNICK, A probability path, Springer, 2019.
[25] W. SHI, Q. LING, G. WU, AND W. YIN, Extra: An exact first-order algorithm for decentralized consensus optimization, SIAM Journal on Optimization, 25 (2015), pp. 944-966.
[26] 7. SONG, W. LI, JIN, L. SHI, M. YAN, W. YIN, AND K. YUAN, Communication-effee topologies for decentralized learning with (11) consensus rate, Advances in Neural Information Processing Systems, 35 (2022), pp. 1073-1085.
[27] N. SRIVASTAVA, G. HINTON, A. KRIZHEVSKY, 1. SUTSKEVER, AND R. SALAKHUTDINOV, Dropout: a simple way to prevent neural networks from overfitring The journal of machine learning research, 15 (2014), pp. 1929-1958.
[28) Y. TAKEZAWA, R. SATO, H. BAO, K. NIWA, AND M. YAMADA, Beyond exponential graph: Communication-effin efffccienn lopologies for decentralized learning via finite-time convergence, arXiv preprint ar3iv:2305. 1420, (2023).
[29] H. TANG. X. LIAN, M. YAN, C. ZHANG, AND LIU, A Decentralized training over decentralized data, in International Conference on Machine Learning, PMLR, 2018, pp. 4848 4856.
[30] L. TREVISAN, Lecture notes on graph partitioning, expanders and spectral methods, University of California, Berkeley, https://people. eecs. berkeley, ect//uca/books//xxpndeee--- pdf, (2017).
[31] T. VOGELS, L. HE, A. KOLOSKOVA, S. P. KARIMIREDDY, T. LIN, S. U. STICH, AND M. JAGGI, Relaysum for decentralized deep learning heterogeneous data, Advances in Neural Information Processing Systems, 34 (2021), pp. 28004-28015.
[32] L. XIAO AND S. BOYD, Fast linear iterations for distributed averaging, Systems & Control Letters, 53 (2004), pp. 65-78.
[33] R. XIN AND A. KHAN, linear algorithm for optimization over directed graphs with geometric convergence, IEEE Control Systems Letters, 2 (2018), pp. 315-320.
[34] B. YING, K. YUAN, Y. CHEN, H. HU, P. PAN, AND W. YIN, Exponential graph is provably efficient for decentralized deep training, Advances Neural Information Processing Systems, 34 (2021), pp. 13975-13987.
[35] K. YUAN, S. A. ALGHUNAIM, AND X. HUANG, Removing data heterogeneity influence enhances network topology dependence of decentralized sgd, Journal of Machine Learning Research, 24 (2023), pp. 1-53.
12

---

A Convergence Analysis of BTPP
In this section, aim demonstrate the convergence results of BTPP through three-step process. First, we explore the key properties matrices R and C, acquainting readers with several operations that will be frequently utilized in the subsequent parts. Then, we introduce various technical tools essential for the analysis. Finally, we delve into proving the convergence results supported by series of pertinent lemmas.
A.1 Properties of the Weight Matrices
In this part, we first demonstrate that E R possesses a set of properties (the matrix R. T shares similar properties). Then, utilize the established tools to prove the crucial result presented in Lemma 3.1 Lastly, we provide clarifications on certain matrix operations that will be frequently employed in deriving the convergence results.
is important note that for any given and specific integer B, the diameter of the corresponding
B-ary tree graph d (the distance from the last layer node to node 1) satisfies B-I ="-1 < S _1+1-1
--1
To investigate the properties of R and C, we will introduce the column vector eg E R", where each element of ez is equal to 1 for indices E I and 0 otherwise. Define the index sets
B
I 1:
B -
Ii, {(
B
+ (i- 2)B* +1)
B++1 B B-1
+ (i 1)B*
B-1
where k1 kog is the arithmetic progression from k to l2 with difference 1. We can then define the matrix Z₁ Raxx as a composite of several column vectors arranged in the following format:
Z (er,,. "I,, ez,,e)
This closed-form expression of R with any power k is shown in Lemma A.1 which aids in developing further properties.
Lemma A.1. For the pull matrix R corresponding to the B-ary GR. given any positive index k. we have
R
Zμ.
Proof. We prove the lemma by induction. First, it is obvious that R = Z₁ by the definition of R:
R.j = 1 iff E [Bj +1 B + [3] (n) ori =-==j=1 iff B - 1) 2 Bj +1, i [n] jroi=j=1
iff [Z]]; = 1.
Now assume the statement is true for 1: j. Then, for 1: = j 1, have
R R² R Z,Z1-
Denote IZ, Z1]: as the i-th column of Z, Z₁ To establish the result, only need to demonstrate that the two matrices, R and Z++1. have the same column entries. For i = 1,
B Σz1
B+1
- 2[
Σ
eT,, = - eT.
For > 1, we have
1B+1 Σ
Σ
[2,1m
[Zy]m
meI.1
m=
iB-1
Cl
= CyyB-1
m=(t-118 188 Tmm.
CLi
1=
Thus, conclude that R Zb+1.
13

---

Corollary A.2 below reveals that when the power & exceeds d, R transforms into matrix where the first column entirely composed ones, while all the other columns consist of zeros.
Corollary A.2. For k d, we have
R lu" =0
where 0 is the matrix with all entries equal O.
Proof. From Lemma A.1
we have for the i-th column of R
11u" that
nh+ lin
Ra
eT,,x i> 1
For h = d, the first elements of all the columns remain 0, which implies the desired result.
Now, we are ready prove Lemma
Proof of Lemma 3.1 For any integer k S d 1, define
B++1 n
B-1
10g
B
This ensures that 1t1l-1 + no B* n and B-1
(no 1)B (no + 2)-th columns of R² consist of non-zero elements. Note that
B
that only the first
B-1
{ R
{1(TR*
|| (R*
lu x
max |x||a=1
lu
x
max
|x|
Then, focus the non-zero elements of the matrix R*
lu
(R
1 1uu" x11
no+1
Bk+1 -
Σ
B²
22)
Bdno (Inotz 22)²
||x|12
|
= T Σx
||
where x = (I1, ... Ino+2) is the truncated x, and
n
-1+1-1
B-1
Bk
n
B++1-1 B-1
B² Bknn
- Bk
B
Σ
B++1 -1
BBno
B Bt-1 B-1
B no
where the unspecified elements all zeros. Since Σ is symmetric, all the eigenvalues real. We show by contradiction that any eigenvalue À of Σ is upper bounded by n. Otherwise, if there exists A n, we denote x the corresponding eigenvector of A. Then, have from Σx Ax that
11 Bk+1
B
Az
31 -B" x2
n
BBno
2no+2
-
-
Az = - BB xı + Bºxz
Ara - B² xι + Bkx3
Bk+1
B
AIno+2
n1
B*
I1 +
n
Bk
Ino+2.
B -
B
14

---

Without loss of generality, assume 21 # 0. Then, by substituting the other relations into the first one, we have
B
no
B
B B++i_1
B-1
B=nn nd
B
B
Bk+l
B-1
With the fact that
> n. there holds
B
no B2b 2k
B+11
B-1
BL
2
A In
+
--1
n1
B
11
11
Bhil
B-1
-B
Be+1 -1
Tie B²k
n²²
B
2n
+ B
B B-1 1
B
Bkil-1
+ Bkno
B
B-1
n Bh+1_1 -1 B²no)
nB*
BE
B Bk-1 -1
+ Bk
B
nB 110
n
B++1
B² BBno no
+
11
B
Bh
B 8-1
gk-1
B
B
which is contradiction. Thus, we have À S n. follows that
x
T
Σx
Amax (2) S n.
|
From the fact that the square root function is monotonically increasing on (o), we have
{11
1 lu x1 S n
I k
lu
11
max x
which implies that | 1 1u Corollary A.2
lle
/n for k S and
||
1 1u 22
1|2 otherwise by
The transformations described in Corollary A.3
below are straightforward.
Corollary A.3. For any integer >> have
1
I = II
R
lu T
R
1u
T
II,,
1 lu
m
I, II
Rm
II
R
lu
R
lu
II,.
n
To simplify the convergence analysis, we introduce the matrix A, defined as follows:
Ci-1
for i 1,,,...., d. Specifically, A C - I. Consequently, Corollary A.4 below can be directly deduced from Lemma A.I and Corollary A.3
Corollary A.4. For 1.... d, we have
i s カ-
T
A;
+1m i=d d
Intuitively, Corollary A.4 illustrates that u - 17) A; serves indicator vector representing the (i 1)-th layer of the graph.
15

---

A.2 Supporting Inequalities and Lemmas
Lemma A.5 and Lemma A.6 below are frequently employed for bounding the norms of matrix summations and multiplications. Their proofs rely on the Schwartz inequality and the definitions of matrix norms || ll2 and [[..
Lemma A.S. For an arbitrary set of m matrices {Ai)
with the same size, we have
m
Σ
A
m
Aill
Proof. By the definition of Frobenius norm, we have
Σ
A S Σ A.llr
Taking squares on both sides and invoking the Cauchy-Schie -Shwwrz inequality, have
2
2
m
m
m
Σ
A
I
m
A
Lemma A.6. Let A, B be two real matrices whose sizes match. Then,
||B|| F S || |
Proof. Let A USVH be the singular value decomposition of A, with the largest singular value mmax and hence |A||2 max Then, we have
AB F
|
H BI| trace ((UVV"B)* (UNV"B)
trace (EV " (EV"B)) = |[
2 VV B 2 trace
B vV"B)
Practrace
(B B) 22 B ||
|| [B
which implies the desired result.
Lemma A.7 below will be used in the last step for deriving the convergence rate of BTPP.
Lemma A.7. Let A, B, C' and a be positive constants and T a positive integer. Define function
A
g(7)
By CB?
(T+1)
Then,
AB
aA T+1
inf g(7)
<
+ 2c's
yE(O, 11
T+1
T+I
where the upper bound can be achieved by choosing ? min
(c7+)) :af
B(T-1)
Proof. See Lemma 26 in g for reference.
Lemma technical result related to random variables.
Lemma A.8. Consider three random variables X, Y, and Z. Assume that Z is independent with (X,Y). Let h and g be functions such that the conditional expectation Elg(Y, Z) Y] = We have
E (h((X)gYY, Z)) 0.
16

---

Proof. It implies by the condition Z TT (X,Y) that (2) 11 oxX, Then,
[ Y E [ h X
E { [o() (X),
It suffices to show
E [o Y| = B (o((, 2) 0).
Let fg(v) = E (g(v. 2)). Since ( 11 a oXx, Y), we have a (2) 11. oY)) Then,
fa(Y) = (Y Y) = gg XX,
which follows directly from (10.17) in 24 Thus, by the Tower Rule, we reach the statement as follows:
(((())g =
= 0.
A.3
Proofs of Key Lemmas
In this section, we prove several key lemmas for proving the main convergence result of BTPP.
A.3.1 Preparation
Algorithm matrix form:
as encapsulated by the equations in 22. can be succinctly expressed in the following
X(++)
) =
R C
X
( 0
)
Y ((+1)
(
(5)
By repeatedly applying equation the following relation:
starting from time step t and going back to time step 0, arrive
(
X ( ) (P
R
RR C
) ( (
Σ m==
[-1
R
R
t-m-1 )
() ((m) )
0
C
G (m++1)-
For the sake of clarity, start with introducing some simple definitions. Any matrix raised the power of is defined as the identity matrix I, which matches the original matrix in dimension. The only exceptions are (R ! Iu = II, and (C- T) II, for convenience. Furthermore,
we introduce the following terms:
lu (0) (
v1 (
Note that, for any given integer 0,
(
R
R )
(8e
Rm
R²
0
C
As result, given the initial condition Y() (0)) as follows.
we can deduce the outcomes of ( and (
1-2 1-m-1
X = R
Σ
Σ R-c - G((m] - Σ
RiC
(6)
j=1
Y() = Σ cl-m-1
((m+1) - (m)) + (O))
(7)
m=0

---

Then, after multiplying Hu and Hl to equation 6 and equation
respectively, and invoking
Corollary A.3
we have
min(d-1.0
I2,(()
R
lu
X
7
Σ
1 lu R
c G
n
n
==1
(8)
2-2
min
m 1-d-11
7
Σ
R
_ lu T
ct-m-1-j
G G ((m)
n
j=1
II, Y
C- c-
1-m-1
[((+1)) - -G(m)] (c
C-
1 -v1 G(
n
m=
min(t.d)11
Σ m==0
c n
(Qut-))-Gtt-ma Glt-m-li) +
(Glt-m) -
-v1_v1 vv- G 99)
n1
min(t.d)
Am (t-m) + II.
A.3.2 Analysis of the Variance
Denote by Fe the o-algebra generated by (Eo: E..1) and define E [-FF]] as the conditional expectation given Ft. Lemma A.9 provides an estimate for the variance of the gradient estimator G(X(1), (())).
Lemma A.9. Under Assumption
1.1 for any given power k S d - 1, we have for all 2 0 that
2
(->nv))) 1 n
111) (cIX)) VF(X
E
FF
S 2no2
Proof. For any given t and + j. due the independently drawn sample e! we have that c/
is independent of (F+, and thus (()) is independent of oxx)) xy .5) . Hence, invoking Lemma A.8 and Assumption T.I yields
(2)
E
VF(2 (1) ( v.((a
(F VV = 0, 1 =E VF(C
E (VF(
( (0) v/((x.))
VF (59)) V(b(g))) = O.
Then, for any index set I C 21, ... nn. we have E (G VF(X 11 = 1Z
Notice that
2v1) & (G" VF(X
gktt +1m (G (G(O- VF(X (1) )
+
2=2
Thus, we obtain the desired result by invoking Lemma A.I and Corollary A.2 after taking expectation on both sides of the above relation:
2
E (c---17) ( (CV-VP(X())
Bb+1
22
n
0² < 2no
B -
18

---

Under Assumption 1.] and the randomly selected samples, Lemma A.9 and Corollary A. below provide an initial estimation for the variance terms. The proof of Corolary A.10 is directly from the analysis in Appendix A.3.2 and Corollary
Corollary A.10.
Under Assumption
1.1 we have for all 2 0 that
11 1 A& (G(X(), -())-(F((()) 113 s (n 1)02.
E
-
n
A.3.3
Proof of Lemma 3.2
Proof. Notice that
( x(0) - 1
lu ((1)- =my lu II, Y + 1 v1 y(t)
n
n
lu Y 711 TY(! = --1 (4-11) II, Y())
711 TYO
Multiplying 1" on both sides of equation light equation we have
we have 1 [Y(t) 1 G(O for any integer t. Thus, in
((+1)) x0) =-1
II, Y -11
min (t.d)
Am (t-m)) -1 ("_ 17) G( - -011
--
T
71
m=1
min min(t.a)
--7
1
Σ
Am (((-m))- (F(X((-ml)
11
(in(C.d)
71
1
Σ
Am A (F(
-11 u G
m=
--1
Σ
Am
G((-m) - (f(
m=1
n 1v-
71
T
Σ
VF(x(m+1) - vF(X(m))
m=
71 TT)
(c- n
v1T
VF(X +
[ ( - 1T
VF(X(t)
7 GO
Hence, taking the F-norm and expectation on both sides, we have from Lemma A.5 that
min(t,d)
u T
B ((1)) x1 13 < 55
Σ
17)
Am (((--m) - VFF mm))
+ nE
u TT
Σ
cc 1-1
t-m-1
VF(X (m
( mm)
n1
n
m m=max (0,--d)
iu - 1T ) + 5y
v--111) VF(X
n
n
u (VF(X(t))G(1))
/|
+ 5n
+5
F
(10)
19

---

Note that, invoking Lemma A.9
and Corollary A.10 yields
E
miuft.d}
u
T
1
Am ((l-m)- VF (F(((()
n
m==
min(t.d}
u
E
1T)
Am (FFI-m)-F((((--1)))
n
(n1
l)o²
From Assumption
1.2
Lemma A.6 and Lemma A.5
we have
1-m-1
E
T
Σ
VF FF(X - VF(((m))
n
n
m (=
1-m-1
12
<d
Σ
E
u
1"
1 (c-
=v1
VF(X(m+1)) VF (mm1)
11
n
m==ax (0,t-d)
Σ
1-1
E
-1'
1-m-1 (
=
1
VF(x(m+11) - (
n2
n
m==ax (0,t-d)
x x(m))|
SndT.
(0,t-)(0,
3 R -
x(m+1] | + E (((m)
x(m) | + (((+1)) -
SndT.
F
Thus, summing over in 10 from 0 T. combining all the inequalities above, and invoking Assumption I.I and Assumption 1.2
we have
2 E II, (t)
E x
((+))
x
1| S
1 30
F
+ 15 2 2
Σ
B x((+1)
-
min f.d-1
+ n2
E
+ +5y 2 + 1)
1=
+572n n Σ
VF(X (0) 2E 1 [VF(X())
||3
+ 2
[VF((((1))
n
T
I 55.2no02(T + +)++4)722d
II,xX00 (0)
+ =157"n"d2'"
>
((+))
x'0
F
P
t=0
1=0
T
+ +5y2n' VF(X (0)
/|
+ +10 2 n
E
V
(11)
Since < TondL we have 15 2 <
B. and the desired result follows.
A.3.4 Proof of Lemma 3.3
Proof. We show the upper bound for II, 2 by studying equation ( and bound the F-norm
of each term respectively. From Corollary
A.2
can change the power of R 11u to at most
20

---

d-2:
1-2
mlofttm-Ldd-1
I1 =(R'
-l
1 lu (x(
-7 Σ
Σ
(R (R-11u lu pC-
1
G (m++1)
(.mm)
n
n
5=1
minft.d-1)
In 1
n
(12)
Then, we derive the following decomposition by pairing the gradients with each of the stochastic gradients in order to use Assumption 1.I
min(t,d-1)
t-j ( ( )
II, II, -(RJ
_ lu )
-7
Σ
R- R--a n
7
Ø=1
min(t,d-1} 1}
R ln
1
v1
T
(1 -VP(X())
n
n
j=1
min (t.d-1 1)
R 1 luu )
(c- h VF(X
min (t.dd-11))
lu n
- -v1 -F(
1
R
n
min(t (in(t---1dd-))
(R - Tu (c- -v1T) 1-m-1-j
Σ
m 11t-m-d m-
((m+t)) - VF(X (m) + (F(X(m)) (m))
2-2 min (t- m 1,d-11
--- 1-m-1-s (m) - vF(x(())
Σ
RR Tu
c C-
m=0 max [1,--
min(t-m-11ff 1,d-1)
i vI
Σ
R lu T
[((+1)) - (m) VF(x(m)) G (())
1=1
1-2 min (t-int---lle mim(t-mm-,dd1) 1,d-1]
j
v1
Σ
Σ
R - lu
-
VF(X(m))
n
n
j=1
- Iu
(0)
Qo.,,1
Qo,t2 - 7 Qo.1.3 Q0.t.4
n
Q1, 72, 70,, -Q1
(13)
where the terms from Q0,,, Qo,c4 and from Q1, to Q4, correspond each term following (R (R-114) 11u (0) byneey-
We assume that 2, since makes the summation illegal (summing over j from positive number non-positive number), in which case II, degenerates (R' -llu' (x(()) and hence by Corollary A.2 there is no consensus error, i.e.
"
Σ |1, =.
For 2, Lemma A. Lemma A. A. below introduce the upper bounds for the F-norms of Q
Q2. and Q3, + Qn, summing from / to 7. Lemma A. A. establissss a similar upper bound for the F-norm of Qo..1 + Q0,13- Furthermore, Lemma A.15 provides the upper bound for the F-norm of Q0.4 + Q
21

---

Lemma A.11. For any iteration number T, we have
T
Σ
QI 32n 1)o?
Proof. To make the summation legal given d 2 2, we need d - 1 2 t - m d, which implies that
m +++1 2d. Then,
1-2 min --m m 1,d-1)
R -u-= - (c- t-m-1-j
Q1 Σ E
m=
m-
((m+l)
VF(x(m=1) + VF(X(m)) - G (m)
min win(t-m-1,d-
R R--1ul -
m=max - 2d,0) == -m
- v1 c
2-m-1-3
((++1)= VF (F(((m+1)
VF(X(m))
G (m)
n
Invoking Lemma A.5
Lemma 3.1
and Lemma A.9 have
min (t m 1,d-13
511
1u,le s 2(d - 1)2
Σ
Σ
E
R
-
1
lu
2d.0 max
t-m-1-j
(c
1 -
G ((m+1)_
(m -(m+t)_ VF(X + VF(X(m)) ((m)
n
t-
minft-m-L,d-1)
< 22n(d 1)²
Σ
Σ
8no²
(r=max(t+]
2d.0)
j=
32nndd'
Summing over from 0 to we get the desired result.
Lemma A.12. For any 7 20ndL we have
22 < T2 E
II,
X
(0)
(4 1)T??02
|| +300m2n'012 ()
360 2
E
t=0
Proof. Similar to the proof of Lemma A.11
we have
Q2
Σ
1-1
min (t- m- 1,d-1}
R (R-
Iuu
(c-
t-m 1-m-1-3 1-j
(m(x()+1)) - [
n
n
m==ax (1+
2d.0 max [1.4 1.4-mm-- m- d}
Invoking Lemma A.5 and Assumption 1.2
we obtain
E 22122111 < d
Σ
E
m= 22.00
< 1
Σ
E ( - (m++))
+ (m) (m) + (m+1)) x(()) 12
m=max [++11 - 2d,03
Σ
II, (1)
+ 122
Σ
E ( {(m)
F
== (1+1-14400)
m=max 10-mmx(2+11-111 1+1-26,03
22

---

It follows by summing over from 0 to T and applying Lemma 3.2 that
T
T
Ql,ll. & 48n d L2
E
I
+
24n 2 d L2
E x (e+1) - x(11
F
1=0
1=0
T
x (48n + 1200 2 d L4)
E
Il
(()
+ +1447 + +))L30
F
1=0
+ 360 2 2
L
E
(1))
2
+
144 nd VF(X /
Hence, under the condition that 7 which implies the desired result.
20ndL there holds 1200 2n 1) S 4nd - 1)*12
Lemma A.13. For any T, we have
Σ Q3, + Q0,12218 S (T'(TT + 1102. t=
Proof. By definition, we have
min min-1.
QI, + Q0
Σ
R
1u1
-v ( +
n
n
#=1
2-2 min(t-m 1-1--11
v1 T
Σ
R
lu
G (m++)) -
(F(x(m+1)) + (F(X(m)) G (m)
j=l
1-1
m-m m
v1
Σ
R
lu
G (m)) VF(X(m))
n
(=max(t-d.0)
Thus, invoking Lemma
A.5
and Lemma
we have
Σ
E Q S nd
E
V
2 |11
11 - dnno?
m= 4.03
After summing over from 0 to T, we get the desired result.
Lemma A.14. For any T, we have
T
E 1|o0...11 + Qo..311 S 022 + 4n2d
V 10)
Proof. Note that
1QQ...1 + Q0, < 2 Qa. + 2
We show the upper bounds for Et il where = 1,3 respectively. Based on Corollary A.2
Lemma A.5 and Lemma A.9 we have the following result:
(t.--1
I
(c
n (-- 431 (FO)-V((XX)
QQ
Σ
R n
min (t.d-1) 1]
R n -1=² (c- 4
Σ
- VF(X (C
1}
(c- (c- (FF
S nd
Σ
j=maa(1.1-d4
23

---

Then, recall that the summation is legal only when t v 2 - 2). We have
T
miad(T2((d-2)
min (t.d-1}
(c (c- =v1T) (-j
E 10.4.11
K
Σ
nd Σ
-VFXX))))))
n
1=
maxx d+1-++1>
S on
Similarly,
Q0,.3l1
min(TT2(dd1)}
min(t.d-1}
1-1
Σ
(R-
lu
(-
v1
|F(X
n2
n
mmax d+1}
S 2nn VF(X (0)
Combining the above upper bounds leads to the final result.
Lemma A.15. For any T, we have
T
T Σ
Σ
E 10o. + Quell 2nn
BI
+ 2n Σ (z) (m)) 112.
t=0
t=0
t=
Proof. Note that
min(t-m--1d--
Q0,4, + Q1,1
Σ
Σ
R
lu T
1
vI
( - (F(X -
n
n
min(t,d-13
Σ
R
lu
v1
(F(X (0)
n
n
v1 T
R
lu
(m))
(t- d,0)
where the last equality comes from extending the summation in the first line and telescoping the summation. Consequently, have
RR (R-21U²)
v1
Qo,c.1 +1,1-
Σ
VF(X
VF(X( + (())
(-
Then, taking the F-norm on both sides and invoking Lemma A.6 Lemma A.5 and Lemma 3.2 as before, we have
|QQ. Que dn Σ
v1 2
- 11
VF(X(m))
v1 21 211 n
VF (m) (m))
n
m= (-d,0)
2dn 2
X
2dn
VV (m) 112
m=mmx (t-00)
m==mx (t-d0)
Taking expectation on both sides and summing over t from 0 to T, we get
E Qo.4 + Qa,ll < 2n of
E "
2n d
E ( (T) 113.
0
24

---

Back to equation 13 note that
1
10) 2 (R T
6
lu )'x
(0) (0)
+ 67² || QQ...1 + Q0,1,31
6, 1Q 1| 6,2 1|Q + 67² 1Qat + Q0 6-² QQ Quell
Taking full expectation on both sides, summing over t from to T and combining Lemma we have
A.11 to
Lemma A.14
min min-7
T
E
II
6
E
R
lu
+ 6, 2
E Q + 6y E 12
0
1=0
r=0
6y² 2
E ||,,r + Q0
67
E Q0,1, + Qaill + 6,
E Q0,,,1 + Q0,1.31
1=0
1=
I 6nd
I (0)
+ 192 n22 1)o² + 312
I1 X1
[z (1) 2
+ 1)
1
1=0
22100"nn''0
|
+ + #
+ 1)o² + n
+ n2
VF(X + 1277"
E
I1 X(,
+2 d²
E
(14)
For S T0n2TT. which implies that 312 + 22 < 14p as follows:
1. we can simplify equation
Σ t=0
I1 x (0)
| 300 "I +12))=++++00> d
20722'
E B
II, x 2 + no (F(
+ 6nd
F²
which implies the desired result.
A.3.5 Proof of Lemma 3.4
Proof. Notice that
21 = 1 -011 2 -7
(t-1) (1-1) (1-1)
Σ
3i
(t-
79h (2 (2) (1-1) _e(t-1)) + 79n (2) (t- 21)
11T1,1
Therefore,
11 does not depend on _t11 for i * 1. We iterate the above procedure to get
(1) (t-1) 1)
(1f (t-1) ((-11) 7 (x² (1) :21 e((-2))
791
Σ (1-3)
fe(2s1-20 (e-2) 2004222)_1 ,(((-21) + Σ (x(2 (1-3) .(ll-3)
VEI..2
VET1.1
1EI..1
Similar to (0) we know that Φ1 (t-1) 1) does not depend on e! 2) + 1. Hence 2 is independent with e(t-2) for & Ir,1. By iterating the procedure, we conclude that (1(() is independent with e!! e(t-R) k) for & Iy
Consequently, by choosing Z = - ((((t=)),, ,EE i IIA--I). Lemma A.8 Z is independent with (X,Y), get
a 20 - (2( 1,,,),e ii [n]] in
E E(VS(1)9) eI,
=0.
25

---

Then, invoking Corollary
A.4 we have
(in(t.d)
(u'
E [
(m-1
17) Am ( -FF
m=1
min(t.d)
(1) fI../ (QF--))-((((-m)))) =
E
A.3.6
Proof of Lemma
3.5
Proof. By Assumption 1.2 the function f f= = fo is L-smooth. Then,
Bf(x1 ( S Ef(o{" + E(V [(V]((]))) (((())))(xxx)))) (+(+1))) x11) + L B1aa
(e+1) - 19"11
(15)
2
For the last term, we have
B|aa ((+1) - (1( B1| _
12
E lu (x (x(++1)-x(()) -
n
n
For the second last term, we have
(1+1) - 2(1) -<(V)(= T
(x (--11)xx' -x()): = -[(V)(= (x -7 u T
{(V)(2 (1) 1
y(1))
=E(VS -7 (u- -17 y(y)) + EVV -7 T
(16)
We now bound the terms in the above equation. Firstly,
E J
17) r(0) = 1V
u 17) 1I Y(0).
Recall that by equation
T
1
II, Y(1)
72
min min(r.d)
(1i-mm_(u__ - -17 17 (()))
{"(
T
Σ
An (t-mm)
n
m=1
1
((())
VF(
72
min(t.d}
(17)
19)
u
T
Σ
Am (G - -FF-)))-FFFXX (t
m=1
V)(2())
T
VF (1)
n
min(t.d]
-EE
()))()),
uu
1T
Am VF ( ml)))
We bound the four terms above one by one. For the first term,
{(V - T - 17) -CFD-(F((())) = =0.
(--
26

---

For the second one, invoking Lemma 3.4
we have
min (t.d)
uui
V)(a)))
):
Σ
Am (G
72
m=1
min(t.d}
u
Σ E
IT A. (CII-M)-F((((-))
VF VF(
= 0.
n
For the last two terms in 17p. we have as:
-B -E
1T)
TuT VF(X -E E (Vf(af").
n (--1-)
17
min(t.d}
Σ
Am VF (t
n
min(t.d)
n1 -(= -1- c- , (0-= m-1
Σ E
Vf(o
17
(VF( -F--1)//)-F---
VF( (x(())
m==
By the Cauchy-Schwartz inequality, we have
(ind
Σ m==1
E
( - 17)
(c
m-1
(i.dt.d)
n
E
||
2
d
E
(u- -1"
( - -VF(X(
2d
2
2n
n
n
(in(t.d)
n2
E
vf(((()) (1)
2
2L2
E
((=m+11) - (1m-m) 2
min(r,a)
f[(z (1)
//
+
3dL
Σ
E
(1T,
2
[ + x((-m+1)
1
x( 13 FF)
2
m=1
Thus, combining the above inequalities together yields
T
T Σ
BB [(x())
-1
II 100
10)
n7
(+)) 1
2
0=
+ 3yd L²
T
E
I x()) (1)
2
+ +zdd L2
T
E3
x00
1=0
Secondly, for the second term in
(6
E "
- VVF - ))
-- V -
my 1"
(1 -
(8)
s Vf |12 + - 2'
Summing over t from to T, we have
E(V](= -1 (0)
3ny Σ
E
1| + 2
2
E (1)
1=0
It yields by summing over from 0 to T both sides of equation (15)
that
3f(a(rt1) - Ef(zi) < Σ
((11) - x1
(1)
L 2n
E (++1) -((+)xx()))) xx
t=0
T
- \x
Σ
T
(B((((a()) - ("
-11 II,
1T
Y(0)g
+
L T
E
x (+1)
- 1x
2n 1=0
1=0
27

---

With the results above, given A = f(x²)
f", we have
E
fz( (1))
1|2
L
E
E
1|
4
2n
t=U
1=
T + +3d L
+ d L
E
Hu
Σ
E
((++1)
x(10
Invoking Lemma 3.2 we have for y I 100nd (5
that
T0ndT.
S sm
45 + 8ynL
Σ E
f(
(1)
t=
(1500~"2d"* nd 5 1??
E
I I1, x10
18 L2 1)o²
+18" + VF(X 122
where it holds that 150 L
25 25 nd La 5y L S Gyd L??.
Invoking Lemma
3.3 we have for S 100n I (5 40nd=t ) that
T
- , my
1207"n2d'1." 45y 45y2 12, 8 1
Σ
R
t=
+3²2n(T + + +
1800 "800 1)021²
1)0²
+ 2d (2 |
|F(X
+ +33mmd Xn
Thus, for S 100nd97, we have
1
2 + 45 + 8ynL 4 8
? 2n 1.2 + 1 nd 1 + 3yL. S ndd
nnd T...
After re-arranging the terms, we conclude that
T
1
Σ
E vf(a
(0)
84, + + 22
T+1
400d 1,2
II, x ( |
56yd T. ||
T ++1
T
A.3.7 Proof of Lemma 3.7
Let x² Lemma It holds that
arg ming f(x). We start with analyzing the behavior of ||x]1) x²1 after obtaining
(++1) x²
- 1|
+2(2" ---1- +
x=" (t+1) -2:00 20())
| (++) (0) 12
(18)
To deal with the critical inner product, similar to the decomposition in Equation (6).. we have, by replacing V (x with 2.(1) x= in Equation [7). and invoking Lemma 3.4 have done in
Lemma 3.5 that
(1)
(1+1) (1))
x" x², .
11
(t)
x", x",
T II, r(0) -x" -2,x1-10
--1
1
(19)
28

---

and
11' T
E
x. 7
1 T
II, Y
(8)
VF(X(0)
n
min(t,d)
7/
x²
1
Σ
Am VF(X
m=11
(in(r.d)
(0)
3dL²
Σ
E (IIx--=-11
+ I 12
m12)
21
x²
4
1
(20)
Notice that, first by strong convexity of f (Assumption 1.3 and then by L-smoothness (Assump- there holds
tion 1
11 x², V
(0)
s -
11 (0)
x² 1
2 11
(21)
1
(1) - x²1
2L
Then.
(1) -> 21 - x², 1 T -> (2 2/)0) - x² 1 vF(
-- - (z)0) - xx,, [ 7E 11 x,, 1 VF(X - -1 VF(X
"iil B
(2 x² ||= 2- "y
(1)
2 || +
mill E 12(0) 1=1
21.27
B
2L
8
(22)
Thus, plugging the above results into Equation holds that
18
with == L/P i as the conditional number, it
E
(1+1)
x=
S
(1
17//44
E (c)
2
x² || 2
ny
R
1|2 2 E x(+1) - x(1) 2
4
L
mingt,d}
min(t,d)+1
2
+ 6dKLy
E
11= (t-mm) m)
+ 20dxLy
E II.'"
m=1
M==
(23)
We derive the convergence result by several standard steps as follows.
Step Unwinding the above recursion, it follows by
1 S 2
< 1 for
7 S 10nd that
(T) x
1 (1
T
(0)
my
) |
E
x
Ij
x
4
2L
T Σ
+
(= + 6el mxl)
4
T-t
E
- x (1)
(24)
1=0
+ 60d2
T
ny
T-t
E |
1=0
we start with Equation II multiplied by the coefficient (1 - m7 T-t
Step 2. To refine Lemma 3.2
1
before summing over f in Equation (10) from 0 to T. Then, we have, for 7 S TondPNL ( 5
1
1 for < Tond that
ni 4
EXX
50 28
(1
17/11 T-t
E
II x
F
d
n7/44 T-t VF(X
12 + +157
+ 6 2m
2n
V V 12)
2
t=
(25)
29

---

where we get the result which only modifies the coefficient of the term (F)
Implementing the above result, we have, for 7 S TondxxL (S TondL )
E
()
xx 112
11
(0)
xx1 I|
T
(-277
ny
+ n5 n
+ 6y²no² (T+ +1 + 36 kLo (T+1)
+ (60yd + 50 nd I?2 300 n
T
(1
n7p
T-t
E
II,
t=
T-d + (672nd + 36- ' n²dd kL) (1 -1
Step 3. Similarly, we refine Lemma over in Equation (4). have
3.3 as follows. By multiplying (1- "7(
T-1
before summing
Σ 0=
1 4
II,
S 3000 (T 1)0² + 20 d
B f (x 1
+ 6nd
X (0)
|| + 2n"d (1- my
VF (0)
Implementing the above result, we have for 7 < A0 that
60yd kL + 507 5 nd 2 3000~"n2 nt 707dkII,
and
(T) x² | $ <(1--
NyH T'
(0) x²1
4
T
(-
n? 2L
+ +15 + 90, n 3 82 kT. + 1400 1100
Σ
R
|
1=0
no 3 Lo (T+1) - 21000 KLo2 (T 1)
+ (6 + 36 2800
T-d
VF ( |
n20
I X (0)
1==0 (f(((())
Step 4. Note that the coefficient of the term derived as follows:
is smaller than 0 for S 100nd4eL
n
+ 157 2 + 90 of +
27.
ny
(-1 + 30 180
2nd k:L))
2L
my
30
180
2800
nn
+
<
< 0.
2T.
100
10a
10
20T.
Thus, it holds that
E
(T)
x²
(1 myp
1
(0)
+ 7 no²
(T + 1) + 21000 2nd xno (T (T+1)
+ nd (1
1a T-d
+
420
30

---

A.4
Proof of the Convergence Results
A.4.1
Proof of Theorem 2.1
Invoking Lemma 3.5
with identical initial values 2; that implies
[I
11 x (0)
0. we have
T
8 = (T + + 24 L +2 10 nd 0² 56 L VF(X (0))
1
EE
T+1
T T+1
t=0
Referring Lemma 26 in stated in Lemma A.7
by taking A 100nd when considering ?
8A1
n
B
240²L,
C
20000nd 22 and
min(
Lo-Ln[
15
100nd have
240d (D2L2A7)
T
32 A 1
800d LA, (F T+1
E
7+1
(n 1)
(vπ(T + 1))
n(T +
t=0
A.4.2 Proof of Theorem 2.4
Invoking Lemma 3.7. with identical values
(0)
that implies
II, X (0)
0, we have
x 1| 5 55(1
n7 T
E
x
4
7 n02 (T + 1) + 21000 3
2ndd
LL (T+
+ 80 nd (1 (1- myu T-d
VF(X
4
Considering 7 min
16 (log(n((++1)))
jr for T 2d we get that
kT,
x(7+1]p
(1 nury T
T
(1
4 log(n (T + 1)3)
(1))
T
< max
400d2
T
T
40
< max
exp(
400d x2
(T 1)²
and
(1 (1-747)
muy T-d
T/2
4log(n (T + 1)3)
2/2
< max
1
1
k0
T+1
10
< max
exp(
800d2
n1 (T + 1)²
where we use the fact (1 - 1)2 < Se- and - < cxp(-23 for any R4. Then,
2240o² log(n((T 1)2)
26880000d 202 (log(n(T + 1)2))² n (T 1)2 42
1 x=
n (T + 11 11
exp( 800d n (T (12 } (11-1 - =21 nL? (1
40
+ max
B Additional Experiments
For the problem of training CNN on the MNIST dataset, we have further compared the real-time performance of BTPP with other representative methods. The experiments are conducted on server equipped with eight Nvidia RTX 3090 GPUs and two Intel Xeon Gold 4310 CPUs, where the
31

---

22
Trann
0.59
Aucuracy
0080 Br2
Dmo, Dm15
Do6n Trling
0.00
12
RIPP
DIT9) Deo
64
0500 6op--241)
DSCD-CrehweCC
D550 Pope
02
0.65
Figure 4: Real-time performance of BTPP (with different branch size B) compared with related methods when training CNN over MNIST.
communication between GPUs follows the topology requirement of each algorithm. We measure the running time including GPU computation and communication for 13,000 iterations. The experimental settings consistent with those described in Section 4.2 From Figure 4 BTPP outperforms the other algorithms concerning the running time. Additionally, we evaluate ВTPP with various branch sizes B, concluding that for relatively small values of branch size of B 2 is most effective.
Furthermore, we consider training VGG13 on CIFARIO dataset, with n = and batch size of 16. The learning rate and topology configurations are consistent with those described in Section 4.2 Additionally, the case of BTPP with meaning that they produce identical outputs when using the illustrate that BTPP beats competing algorithms in terms of the convergence rate (against iteration number) and running time. Morcover, branch size of B 2 is optimal.
equivalent to DSGD a fully connected setting, random seed. Figure and Figure
Train
Text Ausuracy
0.85
BTRO Bn2 Gme D5GTORn USctt-ine "eabic
0.75
1.6
1.4
2.0
1.2
AISP: DITI) Dee
0.45
D50D-Crehhetto
0.
04
0.85
Figure 5: Performance of BTPP (with different branch size B) compared with related methods for training VGG13 over CIFARIO.
We further demonstrate that the performance of BTPP can be improved by incorporating momentum term (with momentum parameter set 0.9) when data heterogeneity exists or by removing the data heterogeneity, which involves randomly assigning samples to each agent; see Figure 7 and Figure g
32

---

Trann
0.85
Text Aucuracy
0080 Br2
Heagg
Exconeldd
200
0.59
BITT
BTPP:
DSOT
0.45
BSAD CeePeeFi
06
DSCD Eupc
DSCD FuB/
04
0.85
Figure 6: Real-time performance of BTPP (with different branch size B) compared with related methods when training VGG13 over CIFARIO.
vathodd Dara Hetargeendyy
1.5
36
06
2030
4000
0000
3000
10000
12000
0000
2000
4000
6000
9000
10000
17000
18000
Figure 7: Performance of BTPP with branch size B = 2 under various configurations when training CNN over MNIST.
DTS0
BliThuated Data Hadrogendty
57
0.
with Monoroann
2030
4000
0000
8020
10000
19000
3000
2000
4000
1000
1020
10000
12000
15000
Figure 8: Performance of BTPP with branch size B = under various configurations when training VGG13 over CIFAR10.
NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our paper meticulously delineates its primary contributions in both the abstract (lines 8-9) and the introduction (subsection 1.2, lines 105-121).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
33

---

The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
At the end of section 1.1, lines 100-104.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions are in subsection 1.3, lines 129-132. The proofs of all theoretical results are the Appendix and subsection 2.1.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch provide intuition.
34

---

Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We present the experiment details in section 4 and upload our code in the link shown in the abstract.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open- open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We provide our code with the link shown in lines 10-11.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cd cc/
for more details.
35

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https for more details.
7 //nips. http::/cpppppccccceeeeeeee/e/eee
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide all the experimental details and settings in Section and our code link.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We have repeated some experiments with different seeds and reported the averaged performance. See Section 4 for details.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
36

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: See line 255 for reference.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:pp://..rrrsss.ccppppcc/eeea
Answer: [Yes]
Justification: The research conducted in the paper conforms, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended
(e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
37

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
We have cited the original paper that produced the code package or dataset.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, haperswwthcode cwm/ com/datasete has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:[NA]
Justification:
The paper does not release new assets.
38

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the datasct/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "zbQUrZ8P6E", "reviewer": "Reviewer_JWsy", "summary": "This paper introduces B-ary Tree Push-Pull (BTPP), an extension of the push-pull framework for distributed learning across a network of agents. The algorithm employs two B-ary tree communication graphs - one for distributing model parameters and one for aggregating gradients. This approach allows each agent to communicate with at most B+1 neighbors per iteration. The main contribution is an analysis demonstrating that BTPP achieves linear speedup with O(n) transient iterations for smooth nonconvex objectives, improving upon previous results for related methods while maintaining lower per-iteration communication.", "questions": "- How does BTPP compare to other extensions of push-pull in the literature?\n- Can this B-ary tree approach be applied to other distributed optimization algorithms? What are the main limitations?\n- How sensitive is the performance to the choice of B? Is there an optimal B value?\n- Can the analysis be extended to strongly convex or convex objective functions?", "limitations": "The authors acknowledge a fundamental limitation common in this area of research: the assumption of a controlled network environment typical of high-performance data-center clusters. This assumption, where network topology can be fully manipulated, is inherent to the proposed BTPP algorithm and many related works in the literature. It's recognized that this limits applicability to scenarios with fixed or constrained network topologies, such as wireless sensor networks or IOT applications.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Novel use of B-ary tree topologies within the push-pull framework\n- Improved theoretical results showing O(n) transient time", "weaknesses": "- The experimental evaluation could be more comprehensive, particularly given that the analysis extends to smooth non-convex problems. Empirical evaluations on deep learning tasks or other practical non-convex optimization problems would strengthen the paper's claims and demonstrate real-world applicability.\n- While the improvement in transient time is theoretically significant, the paper could benefit from a more thorough discussion of how this translates to practical advantages in real-world distributed learning scenarios, especially for large-scale or long-running optimization tasks.\n- The approach is primarily applicable to controlled network environments like high-performance data-center clusters, limiting its relevance to scenarios with fixed or constrained network topologies (e.g., wireless sensor networks, internet of vehicles).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We provide response to your concerns and questions below.\n\n1. **Enhanced experiments.** For the problem of training a CNN on the MNIST dataset, we have further compared the real-time performance of BTPP with other representative methods (see the attachment). The experiments are conducted on a server equipped with eight Nvidia RTX 3090 GPUs and Intel Xeon Gold 4310 CPU, where the communication between GPUs follows the topology requirement of each algorithm. We measure the running time including GPU computation and communication for 13,000 iterations. The experimental settings are consistent with those described in Section 4.2 of the original paper. From Figure 1, BTPP outperforms the other algorithms concerning the running time. Additionally, we evaluate BTPP with various branch sizes $B$, concluding that for relatively small values of $n$, a branch size of $B=2$ is most effective.\n\n    Furthermore, we consider training VGG13 on the CIFAR10 dataset, with $n=8$ and a batch size of 16. The learning rate and topology configurations are consistent with those described in Section 4.2. Figures 2 and 3 illustrate that BTPP beats competing algorithms in terms of the convergence rate (against iteration number) and running time. Moreover, a branch size of $B=2$ is optimal.\n    \n2. **Comparison to other Push-Pull extensions.** There are several major differences between BTPP and the other extensions of the Push-Pull method. First, all the other extensions consider communication graphs that satisfy certain assumptions, rather than any specific network topologies. Second, BTPP employs network weights which are only 0’s and 1’s. This does not satisfy the assumptions in previous works that require non-zero weights for diagonal elements of the mixing matrices. Finally, most extensions of Push-Pull method assume deterministic gradients. Note that the first two differences contribute to the huge advantage of BTPP compared to the other extensions regarding the convergence guarantees. Particularly, linear speedup has not been demonstrated in previous works that consider stochastic gradients; see e.g., [1-2].\n\n    [1] Xin, Ran, et al. ``Distributed stochastic optimization with gradient tracking over strongly-connected networks.\" 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.\n\n    [2] Nguyen, Duong Thuy Anh, Duong Tung Nguyen, and Angelia Nedic. ``Distributed Stochastic Optimization with Gradient Tracking over Time-Varying Directed Networks.\" 2023 57th Asilomar Conference on Signals, Systems, and Computers. IEEE, 2023.\n\n3. **B-ary tree approach.** To our knowledge, only Push-Pull type methods allow the use of two spanning trees and the corresponding mixing matrices in the algorithm design. Other popular distributed optimization algorithms, such as DSGD, EXTRA and ADMM type methods, require a strongly connected graph and the corresponding mixing matrix for implementation. Thus they are not compatible with the B-ary tree approach.\n\n    BTPP has the potential to incorporate other gradient-based methods such SGD with momentum (SGDM), random-reshuffling type methods, and proximal stochastic gradient methods. For example, BTPP with SGDM works as follows:\n        $$\n        \\begin{aligned}\n            x_i^{(t+1)} & = \\sum\\_{j \\in \\mathcal{N}\\_{\\mathcal{R},i}^{in}} ({x\\_j^{(t)} - \\gamma y\\_{j}^{(t)}}) \\\\\\\\\n            z_i^{(t+1)} & = \\beta z\\_i^{(t)} + (1-\\beta) g\\_i(x^{(t+1)}_i;\\xi\\_i^{(t+1)})\\\\\\\\\n            y\\_i^{(t+1)} & = \\sum\\_{j\\in\\mathcal{N}\\_{\\mathcal{C},i}^{in}} y\\_j^{(t)} + z\\_i^{(t+1)} -  z\\_i^{(t)}\n        \\end{aligned}\n        $$\n        with $\\beta\\in(0,1)$. We expect that such extensions of BTPP can also enjoy preferable performance.\n\n4. **Choice of $B$.** From Figure 2, increasing $B$ can accelerate the convergence of BTPP, especially when $B$ is small. As $B$ becomes larger, the acceleration effect degrades. This can be explained by the bound given in Theorem 2.1, which depends on $d$, the diameter of the graphs. For large $B$, $d$ is close to $1$ and thus increasing $B$ only has marginal effect. \n\n    From Figure 2 and Theorem 2.1, the optimal $B$ is equal to $n$ considering the number of required iterations. \n    If we instead consider the real running time, the optimal $B$ may not be equal to $n$. The running time can be computed as:\n\n    Running time = (iteration number)$\\times$(per-iteration running time)\n\n    Given a required accuracy, the running time is a nonlinear function of $B$, and the optimal $B$ can be determined through experiments. For instance, we can start with a small $B$, and increase $B$ until the best performance is achieved. Noting that only when $B$ is small, increasing $B$ has significant impact, the optimal $B$ is usually small. In the additional experiments (see the attachment in \"global\" response), we find that $B=2$ achieves the best performance in real-time.\n\n5. **Analysis under (strongly) convex objective functions.** The analysis of BTPP can be extended to $\\mu$-strongly convex function $f$, that is, for any $x,y\\in \\mathbb{R}^p$,\n    $$\n    f(y) \\ge f(x) + \\langle\\nabla f(x), y-x \\rangle + \\frac{\\mu}{2}\\\\| y-x \\\\|^2.\n    $$\n    We are able to obtain the following convergence result (a sketch of analysis is provided in the \"global\" response):\n    $$\n      \\mathbb{E}\\left\\\\|x_1^{(T)} - x^* \\right\\\\|^2 = \\tilde{\\mathcal{O}} \\left( \\frac{1}{nT} + \\frac{1}{nT^2} + \\exp\\left( - T\\right) \\right).\n    $$\n    where $\\tilde{\\mathcal{O}}$ hides the constants and polylogarithmic factors.\n\n    The transient time is thus $\\tilde{O}(1)$, which also outperforms the state-of-the-art results.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tcRZ4e0h1S", "reviewer": "Reviewer_C42p", "summary": "The paper introduces a method for distributed learning, for the common scenario that various \"agents\" each hold part of a data set locally, and aim to coordinate to find the minimizer of some criterion. Here, the criterion consists of the average of local cost functions, which are assumed to be smooth but non-convex, and each agent is assumed to able to compute a \"gradient estimator\". By communicating information concerning these gradient estimators, the agents together minimize global criterion (i.e. averaged local criteria).\n\nThe method consists of both a specific network architecture/topology, combined with an algorithm for what each agent computes and communicates throughout the network. Unbiased estimators of the local gradients are generally assumed to be available. The authors consider possibly heterogenous data, but this plays no role beyond just extending generality it seems.\n\nThe analysis of the authors focusses mainly on the number of transient iterations required by the algorithm. Communication cost does not take into account the actual size of the gradient estimator, but concerns the number of neighbors that a message is to be passed onto by a node, for every node and at every iteration.\n\nThe authors provide a main theorem describing the convergence properties of the algorithm and simulations. Both are used for comparison with existing methods in the literature.", "questions": "* The role of $n$ is somewhat surprising in (3), making many of the terms smaller as the data gets distributed across more servers. Do the authors have an interpretation for these terms / an intuition as to why this is? In principle, I would say that the more servers one considers, the more difficult the problem should get in principle. Is the appearance of $n$ in the dominator a consequence of total communication increasing as $n$ increases?\n\n* The authors comment on the choice of B in Remark 2.3 in terms of the upper bound given in (3); ending with the sentence \"..the communication cost and convergence rate can be balanced by considering a proper B\". How should this be done in practice? Is there a practical guideline that the authors have here? The insight provided by (3) seem rather limited here, as it is only an upper bound.\n\n* If one does not have full control when designing the network topology, what are the take-aways from the current design?", "limitations": "* The assumptions on the gradient estimator (mean 0, uniformly bounded variance) are very strong.\n* The interpretation of the quantities appearing could be somewhat more extensive.\n* The attention spent on //why// this network design considered by the authors leads to such an improvement in terms of transient times is limited.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The paper provides a rigorous theoretical analysis, providing clear convergence guarantees\n\n* The method described by the paper has clear advantages in comparison to various existing algorithms in the literature, in terms of the number of transient iterations and in terms of total communication cost.\n\n* The method is practically relevant in distributed settings where one has control over the design of the network nodes.\n\n* The numerical results are well-chosen, and provide convincing support for the theoretical guarantees in small samples / finite iterations, in comparison to many existing methods in the literature.\n\n* The paper is well written (up to some punctuation mistakes), from the introduction lasting into the appendix, and its analysis appears sound to me.", "weaknesses": "My main grief with setup considered by the authors is the (in my opinion very strong assumption) that there is no bias in the gradient estimator. Since the authors seem to target high-dimensional setups, this is often not case, unless one has access to the original gradient. Furthermore, it is difficult to verify whether one has zero bias. \n\nIt would be a great improvement if the authors captured the importance having (very) small bias in their theory. Is 0 bias strictly necessary? How much bias can one get away with here?\n\nSimilarly, the uniform bound on the variance of the gradient estimator seems rather strong. Going through the analysis provided by the authors, I also wonder whether uniformity is generally necessary here. Since this appears as a constant in the main theorem (i.e. in (3)), it might in fact significantly impact the convergence of the algorithm, and I think it would be wise for the authors to comment on this further.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments.\n\n1. **Assumptions on the stochastic gradients.**\n    The unbiasedness of the stochastic gradients is a result of the sampling strategy.\n    Note that this work mainly focuses on the scenario where computing the full gradients is expensive due to large datasets. Specifically, in empirical risk minimization,\n    $$\n    f\\_{i}(x)=\\frac{1}{|\\mathcal{D}\\_{i}|}\\sum_{\\xi\\in\\mathcal{D}\\_{i}}F_i(x;\\xi),\n    $$\n    where $\\mathcal{D}\\_{i}$ denotes the dataset of node $i$.\n    Thus exactly computing $\\nabla f_i(x)$ requires sampling all the data points in $\\mathcal{D}\\_{i}$, which is costly.\n    In practice, node $i$ may select a mini-batch of data points $\\mathcal{B}\\_{i}$ uniformly randomly from $\\mathcal{D}\\_{i}$ for estimating $\\nabla f\\_{i}(x)$ at every iteration. Given $x$, the stochastic gradient is given by \n    $$\n    \\frac{1}{|\\mathcal{B}\\_{i}|}\\sum_{\\xi\\in\\mathcal{B}\\_{i}}\\nabla F_i(x;\\xi),\n    $$\n    which is naturally an unbiased estimator of $\\nabla f_i(x)$.\n\n    The unbiasedness condition is commonly assumed in related works such as [1-2] and the other references of this paper (see Table 1).\n\n    The assumption of bounded variance can be relaxed. For example, we can consider the relaxed growth condition:\n    $$\n    \\mathbb{E}\\_{\\xi\\_{i} \\sim \\mathcal{D}\\_{i}} (\\\\|{g\\_{i}(x,\\xi\\_{i}) - \\nabla f\\_{i}(x)}\\\\|^2 |x)  \\le \\sigma^2 + \\eta \\\\|\\nabla f\\_{i}(x)\\\\|^2\n    $$\n    for some $\\eta>0$, or more generally,\n    $$\n    \\mathbb{E}\\_{\\xi_i \\sim \\mathcal{D}\\_i} (\\\\|{g_i(x,\\xi_i) - \\nabla f_i(x)}\\\\|^2 |x)  \\le \\sigma^2 + C(f_i(x)-f_i^*)\n    $$\n    for some $C>0$, where $f_i^*=\\inf_x f_i(x)$. The latter is currently the most general assumption in the distributed optimization literature (see [3]). Under the condition, it can be derived that BTPP maintains similar convergence result with some additional constants. For instance, the constant $\\sigma^2$ in (3) becomes $\\sigma^2+C(f^*-\\sum_{i=1}^n f_i^*/n)$ with $f^*=\\inf_x f(x)$.\n\n    In this paper, we let $\\eta=0$ for simplicity to focus on the transient time analysis of BTPP. The bounded variance condition was also commonly assumed in related works (see the works in Table 1).\n\n    [1] Ying, Bicheng, et al. \"Exponential graph is provably efficient for decentralized deep training.\" Advances in Neural Information Processing Systems 34 (2021): 13975-13987.\n\n    [2] Vogels, Thijs, et al. \"Relaysum for decentralized deep learning on heterogeneous data.\" Advances in Neural Information Processing Systems 34 (2021): 28004-28015.\n\n    [3] Huang, Kun, Xiao Li, and Shi Pu. \"Distributed stochastic optimization under a general variance condition.\" IEEE Transactions on Automatic Control (2024).\n\n2. **Role of $n$.** \n    The appearance of $n$ in the denominator in (3) implies the \"linear speedup\" property of the BTPP method and other related algorithms (see Table 1), that is, increasing the number of workers/machines accelerates the algorithmic convergence with respect to the number of iterations. Intuitively, as $n$ increases, more stochastic gradients are acquired at every iteration, which helps reduce the variances through implicit averaging (network mixing). Particularly for BTPP, the decision variables $x_i^{(t)}$ for different agents are similar (following $x_1^{(t)}$), and $y_1^{(t)}$ effectively tracks the summation of the stochastic gradients across the network. By properly choosing the stepsize that is decreasing in $n$, node $1$ is approximately performing stochastic gradient descent for minimizing $f(x)$ using the average of $n$ stochastic gradients per iteration. Thus the variances of the stochastic gradients have been divided by $n$ because of averaging.\n\n    From another perspective, if we measure the performance of BTPP and related distributed stochastic gradient algorithms against the number of stochastic gradients (rather than the iteration number), the dominant term $\\mathcal{O}(1/\\sqrt{nT})$ is the same as for a centralized algorithm using one stochastic gradient per iteration (noting that $nT$ represents the total number of stochastic gradients for distributed algorithms).\n\n3. **Choice of $B$.** \n    From (3) and Figure 2, increasing $B$ can accelerate the convergence of BTPP with respect to the number of iterations, especially when $B$ is small. At the same time, larger $B$ increases the per-iteration communication cost, and thus there is trade-off.\n    In practice, the actual running time can be roughly estimated as follows:\n\n    Running time = (iteration number)×(per-iteration running time)\n\n    Given a required accuracy, the running time is a nonlinear function of $B$, and the optimal value can be determined by experiments. For example, we can start with a small $B$, and increase $B$ until the best performance is achieved. Noting that only when $B$ is small, increasing $B$ has significant impact on the convergence rate (w.r.t the number of iterations), the optimal $B$ is usually small. In the additional experiments (see the attachment in \"global\" response), it can be seen that $B=2$ achieves the best performance in real-time.\n\n4. **Extension to fixed networks.** \n    Given a fixed directed network $\\mathcal{G}$ with arbitrary topology, following the idea of BTPP, we can locate a spanning tree $\\mathcal{G}\\_R$ and a reversed spanning tree $\\mathcal{G}\\_C$ which are subgraphs of $\\mathcal{G}$, such that $\\mathcal{G}\\_R$ and $\\mathcal{G}\\_{C^{\\top}}$ share a common root. Then the mixing matrices $R$ and $C$ are constructed accordingly with $0$'s and $1$'s, and an algorithm similar to BTPP can be designed following (2). We anticipate that, although such an algorithm would not enjoy $\\tilde{O}(n)$ transient time due to potentially longer network diameter in the order of $\\mathcal{O}(n)$, linear speedup can be expected for large $T$, and the transient time would be shorter compared to existing distributed stochastic gradient methods over a general fixed network.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g9FHKuNDjR", "reviewer": "Reviewer_rZsK", "summary": "This paper reduces transient time in decentralized optimization algorithms by introducing the B-ary Tree Push-Pull (BTPP) algorithm, derived from the Push-Pull method. The authors assume a setup where any type of communication network can be established among the nodes. They employ two distinct communication networks: the network represented by graph $R$ for pulling parameter information, and the network represented by graph $C$ for pushing stochastic gradient information towards node 1. The method achieves linear speedup for smooth nonconvex objective functions with only $O(n)$ transient iterations, significantly outperforming existing state-of-the-art methods.", "questions": "1. Refer to weaknesses. \n\n2. Could you please elaborate on how the BTPP algorithm addresses data heterogeneity problems? Specifically, which term in equation (3) demonstrates that data heterogeneity decreases as the algorithm progresses?\n\n3. I am interested in the fixed point analysis of BTPP. The Push-Pull algorithm has a comprehensive fixed point analysis. In your algorithm, if all nodes converge to a stationary solution, will the algorithm maintain that state? Additionally, to which points do the other nodes converge, apart from node 1?", "limitations": "Refer to Weaknesses and Questions.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Reduction of transient time in decentralized optimization\n - Novel convergence approach\n - Demonstrating the use of B-ary trees to balance between communications per iteration and transient time", "weaknesses": "1. The introduction lacks cohesion and focus, with unnecessary information in the second paragraph. The significance of the transient time problem, a key contribution of the paper, could be better defined to highlight its importance.\n\n 2. The paper demonstrates that only node 1 converges to the local solution. However, it is not entirely clear what happens to the variables at other nodes or whether the nodes achieve consensus similar to classical decentralized algorithms. \n\n 3. The proposed setup appears to be limited to high-performance data-center clusters where a B-ary spanning tree communication network can be established among nodes. This might limit the applicability of the algorithm in other environments.\n\n 4. Additionally, the analysis is focused on smooth nonconvex objective functions, and there is no discussion on strongly convex functions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We provide response to your concerns and questions below.\n\n1. **Consensus properties.** \n    In BTPP, the nodes achieve consensus similar to classical decentralized algorithms. Specifically, noting the definition of $\\Pi_{\\mathbf{u}}$ on page 7, Lemma 3.3 bounds the summation of the expected squared distances between $x_i^{(t)}$ and $x_1^{(t)}$. Dividing both sides of the inequality by $(T+1)$, in light of the condition on $\\gamma$ and the convergence result given in Theorem 2.1, we can derive that the consensus error (averaged over the history) converges to $0$ in the order of $\\mathcal{O}(1/T)$.\n\n2. **Extension to fixed networks.** \n    This work focuses on the setting where the network topology is fully controllable. If instead an arbitrary fixed directed network $\\mathcal{G}$ is given, inspired by BTPP, we can locate a spanning tree $\\mathcal{G}\\_{R}$ and a reversed spanning tree $\\mathcal{G}\\_{C}$ which are subgraphs of $\\mathcal{G}$, such that $\\mathcal{G}\\_{R}$ and $\\mathcal{G}_{C^{\\top}}$ share a common root. Then the mixing matrices $R$ and $C$ are constructed accordingly with $0$'s and $1$'s, and an algorithm similar to BTPP can be designed following (2). We anticipate that, although such an algorithm would not enjoy $\\tilde{O}(n)$ transient time due to potentially longer network diameter in the order of $\\mathcal{O}(n)$, linear speedup can be expected for large $T$, and the transient time would be shorter compared to existing distributed stochastic gradient methods over a general fixed network.\n\n3. **Analysis under (strongly) convex objective functions.** \n    The analysis of BTPP can be extended to $\\mu$-strongly convex function $f$, that is, for any $x,y\\in \\mathbb{R}^p$,\n\n    $$\n    f(y) \\ge f(x) + \\left\\langle \\nabla f(x), y-x \\right\\rangle + \\frac{\\mu}{2}\\left\\\\| y-x \\right\\\\|^2.\n    $$\n\n    We are able to obtain the following convergence result (a sketch of analysis is provided in the \"global\" response):\n\n    $$\n    \\mathbb{E}\\left\\\\|x_1^{(T)} - x^* \\right\\\\|^2 = \\tilde{\\mathcal{O}} \\left( \\frac{1}{nT} + \\frac{1}{nT^2} + \\exp\\left( - T\\right) \\right).\n    $$\n\n    where $\\tilde{\\mathcal{O}}$ hides the constants and polylogarithmic factors. The transient time is thus $\\tilde{O}(1)$, which also outperforms the state-of-the-art results.\n\n4. **Addressing data heterogeneity.** \n    In BTPP, $y_1^{(t)}$ effectively tracks the summation of (possibly delayed) stochastic gradients across the network. By properly choosing the stepsize that is decreasing in $n$, node $1$ is approximately performing stochastic gradient descent for minimizing $f(x)$ using the average of $n$ stochastic gradients per iteration. Therefore, the performance of BTPP is similar to a centralized SGD algorithm whose performance does not degrade due to data heterogeneity. In (3), only the last term is affected by the data heterogeneity. Noting that $\\\\|\\nabla F(\\mathbf{X}^{(0)})\\\\|^2 = \\sum_{i=1}^n \\\\|\\nabla f_i(x^{(0)})\\\\|^2$, even if $x^{(0)}$ is a stationary point of $f(x)$ (i.e., $\\nabla f(x^{(0)}) = 0$), $\\nabla f_i(x^{(0)})$ are non-zero in general and may differ vastly for different $i$ because of different $f_i$. The last term decreases in the order of $\\mathcal{O}(1/T)$, faster than the dominant term. This implies that the influence of data heterogeneity vanishes faster compared with the stochastic gradient variances.\n\n5. **Fixed-point analysis.** \n    Since BTPP applies stochastic gradients with a constant stepsize, convergence in the common sense cannot be achieved. We thus study the fixed points of BTPP assuming deterministic gradients. From (2), assuming $\\mathbf{X}^{(t)}$ and $\\mathbf{Y}^{(t)}$ converge to $\\mathbf{X}^{\\infty}$ and $\\mathbf{Y}^{\\infty}$ respectively, we have\n\n    $$\n    \\mathbf{X}^{\\infty} = R\\mathbf{X}^{\\infty} - \\gamma\\mathbf{Y}^{\\infty}, \\quad \\mathbf{Y}^{\\infty} = C\\mathbf{Y}^{\\infty}.\n    $$\n\n    Therefore,\n\n    $$\n    (I-R)\\mathbf{X}^{\\infty} + \\gamma\\mathbf{Y}^{\\infty} = 0, \\quad (I-C)\\mathbf{Y}^{\\infty} = 0.\n    $$\n\n    Since $\\text{span}(I-R) \\cap \\text{null}(I-C) = \\emptyset$ (from the design of $R$ and $C$), we have $(I-R)\\mathbf{X}^{\\infty} = 0$ and $\\mathbf{Y}^{\\infty} = 0$. The former implies consensus of $x_i^{\\infty}$, i.e., $x_i^{\\infty} = x^{\\infty}$ for all $i$. Noting that $\\frac{1}{n} \\sum_{i=1}^n y_i^{\\infty} = \\frac{1}{n} \\sum_{i=1}^n \\nabla f_i(x_i^{\\infty})$, the latter leads to $\\frac{1}{n} \\sum_{i=1}^n \\nabla f_i(x^{\\infty}) = 0$. Therefore, $x^{\\infty}$ is a stationary point of $f(x)$. In conclusion, the fixed points $x_i^{\\infty}$ achieve consensus and equal to a stationary point of $f(x)$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OtTi8UTXon", "reviewer": "Reviewer_KerT", "summary": "The paper proposes the B-ary Tree Push-Pull (BTPP) algorithm for distributed learning over heterogeneous data. The BTPP algorithm introduces 2 spanning directed trees as communication graphs: Pull Tree $G_R$ and Push Tree $G_C$. BTPP has only $\\Theta(1)$ communication overhead per iteration and $O(n)$ transient time complexity but outperforms the baseline. The paper also theoretically shows that BKPP is of sublinear convergence rate. The experimental results shown in the paper also support that BTPP outperforms the SOTA baseline.", "questions": "See weaknesses.", "limitations": "See weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. BTPP combines two directed trees, the Pull Tree and the Push Tree, for distributed learning. \n2. Since the degree for the Tree is at most $O(n)$ with n nodes, the communication time complexity for BTPP is lower than other methods. At the same time, the result outperforms other methods.\n3. The paper provides theoretical guarantees for the BTPP algorithm.", "weaknesses": "1. BTPP algorithm is derived from the Push-Pull gradient method in [1] by defining the communication graph as B-ary trees. The mathematical formulation and pseudocode Algorithm 1 looks the same as that in [1]. What is the main difference between the two algorithms? \n\n2. In the paper, the authors state that the Pull graph $G_R$ is the inverse of the Push graph $G_C$. What is the reason that the two graphs must have the same structure?\n\n3. The authors claim that the advantage of BTPP is that it could reach better performance than the SOTA with lower communication costs. However, in section 4, the paper only shows iteration-wise test performance rather than the time-wise performance.\n\n[1] Push-Pull Gradient Methods for Distributed Optimization in Networks", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comments. We provide response to your concerns and questions below.\n\n1. **Comparison between BTPP and Push-Pull method.** \n    There are three main differences between BTPP and the original Push-Pull method. First, the Push-Pull method assumes a general condition on the communication graphs but does not consider any specific network topology. By contrast, BTPP makes use of two $B$-ary trees to achieve accelerated convergence. Second, BTPP employs network weights which are only 0's and 1's. This does not satisfy the assumption in Push-Pull that requires non-zero weights for diagonal elements of the mixing matrices. The special design of BTPP greatly improves the efficiency of information propagation and aggregation compared to Push-Pull. Finally, Push-Pull considered deterministic gradients while BTPP works with stochastic gradients.\n\n2. **Graph structure.** \n    We consider $\\mathcal{G}_R$ to be the inverse of $\\mathcal{G}_C$ for simplicity (since the network topology is fully controllable). If $\\mathcal{G}_R$ and the inverse of $\\mathcal{G}_C$ have different structures, as long as they are still $B$-ary trees ($B$ can be different for the two graphs), we can show a similar convergence result for BTPP following almost identical analysis (noting that matrices $R$ and $C$ preserve the desired properties).\n\n3. **Real-time performance.** For the problem of training a CNN on the MNIST dataset, we have further compared the real-time performance of BTPP with other representative methods (see the attachment). The experiments are conducted on a server equipped with eight Nvidia RTX 3090 GPUs and Intel Xeon Gold 4310 CPU, where the communication between GPUs follows the topology requirement of each algorithm. We measure the running time including GPU computation and communication for 13,000 iterations. The experimental settings are consistent with those described in Section 4.2 of the original paper. From Figure 1, BTPP outperforms the other algorithms concerning the running time. Additionally, we evaluate BTPP with various branch sizes $B$, concluding that for relatively small values of $n$, a branch size of $B=2$ is most effective.\n\n    Furthermore, we consider training VGG13 on the CIFAR10 dataset, with $n=8$ and a batch size of 16. The learning rate and topology configurations are consistent with those described in Section 4.2. Figures 2 and 3 illustrate that BTPP beats competing algorithms in terms of the convergence rate (against iteration number) and running time. Moreover, a branch size of $B=2$ is optimal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We provide some general feedback corresponding to the common concerns/questions raised by the reviewers. These points will be incorporated in the revision.

1. **Enhanced experiments.** For the problem of training a CNN on the MNIST dataset, we have further compared the real-time performance of BTPP with other representative methods (see the attachment). The experiments are conducted on a server equipped with eight Nvidia RTX 3090 GPUs and Intel Xeon Gold 4310 CPU, where the communication between GPUs follows the topology requirement of each algorithm. We measure the running time including GPU computation and communication for 13,000 iterations. The experimental settings are consistent with those described in Section 4.2 of the original paper. From Figure 1, BTPP outperforms the other algorithms concerning the running time. Additionally, we evaluate BTPP with various branch sizes $B$, concluding that for relatively small values of $n$, a branch size of $B=2$ is most effective.

    Furthermore, we consider training VGG13 on the CIFAR10 dataset, with $n=8$ and a batch size of 16. The learning rate and topology configurations are consistent with those described in Section 4.2. Figures 2 and 3 illustrate that BTPP beats competing algorithms in terms of the convergence rate (against iteration number) and running time. Moreover, a branch size of $B=2$ is optimal.

2. **Extension to fixed networks.** Given a fixed directed network $\mathcal{G}$ with arbitrary topology, following the idea of BTPP, we can locate a spanning tree $\mathcal{G}\_R$ and a reversed spanning tree $\mathcal{G}_C$ which are subgraphs of $\mathcal{G}$, such that $\mathcal{G}\_R$ and $\mathcal{G}\_{C^{\top}}$ share a common root. Then the mixing matrices $R$ and $C$ are constructed accordingly with $0$'s and $1$'s, and an algorithm similar to BTPP can be designed following (2). We anticipate that, although such an algorithm would not enjoy $\tilde{O}(n)$ transient time due to potentially longer network diameter in the order of $\mathcal{O}(n)$, linear speedup can be expected for large $T$, and the transient time would be shorter compared to existing distributed stochastic gradient methods over a general fixed network.

3. **Analysis under (strongly) convex objective functions.** The analysis of BTPP can be extended to $\mu$-strongly convex function $f$. The transient time is $\tilde{O}(1)$, which also outperforms the state-of-the-art results. We provide a sketch of analysis below.

   Let $x^* = \arg\min_x f(x)$. We start with analyzing the behavior of $\\|x_1^{(t)} - x^*\\|^2$ after obtaining **Lemma 3.4** (boldface represents result from the original paper). It holds that
   $$
   \left\\|x_1^{(t+1)} - x^* \right\\|^2 = \left\\|x_1^{(t)} - x^* \right\\|^2 + 2 \left\langle x_1^{(t)} - x^*, x_1^{(t+1)} - x_1^{(t)} \right\rangle + \left\\|x_1^{(t+1)} - x_1^{(t)} \right\\|^2.
   $$
   To deal with the critical inner product, similar to the decomposition in **Equation (14)**, we have, by replacing $\nabla f(x_1^{(t)})$ with $x_1^{(t)} - x^*$ in **Equation (15)**, and invoking **Lemma 3.4** as we have done in **Lemma 3.5**,
   $$
   \begin{aligned}
               &-\mathbb{E}\left\langle x\_1^{(t)} - x^*,\gamma \left(\frac{\mathbf{u}^\top}{n} - \mathbf{1}^\top \right)\mathbf{\Pi}\_{\mathbf{v}}\mathbf{Y}^{(t)} \right\rangle \le  \frac{n\gamma \mu}{4} \mathbb{E} \left\\|x\_1^{(t)} - x^* \right\\|^2 \\\\
              &\quad  + \frac{3dL^2}{\mu} \gamma \sum\_{m=1}^{ \min\\{t,d\\} } \mathbb{E} \left( \left\\|\mathbf{\Pi}\_{\mathbf{u}} \mathbf{X}^{t-m+1}  \right\\|^2 + \left\\|\mathbf{\Pi}\_{\mathbf{u}} \mathbf{X}^{t-m}  \right\\|^2 + \left\\|\bar{\mathbf{X}}^{t-m+1} - \bar{\mathbf{X}}^{t-m} \right\\|^2\right).
           \end{aligned}
   $$
    In light of the strong convexity and $L$-smoothness of $f$, 
    for $\gamma \le \frac{1}{10 nd^3\kappa L}$ ($\kappa:=L/\mu$), we have
   $$
       \begin{aligned}
       & \mathbb{E}\left\\|x_1^{(t+1)} - x^* \right\\|^2 \le \left(1 - \frac{n\gamma \mu}{4} \right)\mathbb{E}\left\\|x_1^{(t)} - x^* \right\\|^2  -\frac{1}{L} \mathbb{E}\left\\|\nabla f(x_1^{(t)} ) \right\\|^2 + \frac{1}{n}\mathbb{E}\left\\|\bar{\mathbf{X}}^{(t+1)} - \bar{\mathbf{X}}^{(t)} \right\\|^2_F \\\\
       &\quad + 3 d\kappa L \gamma \sum_{m=1}^{ \min\\{t,d\\} } \mathbb{E}\left\\|\bar{\mathbf{X}}^{(t-m+1)} - \bar{\mathbf{X}}^{(t-m)} \right\\|^2_F + 10d\kappa L \gamma \sum_{m=0}^{ \min\\{t,d\\}+1 } \mathbb{E} \left\\|\mathbf{\Pi}_{\mathbf{u}} \mathbf{X}^{t-m}  \right\\|^2_F.
       \end{aligned} 
   $$
   Unwinding the above recursion, and following several standard steps (implementing **Lemma 3.2** and **Lemma 3.3**, picking $\gamma := \min\\{\frac{1}{10nd^3\kappa L}, \frac{1}{n\mu(T+1)}\\}$, we get
   $$
         \mathbb{E}\left\\|x_1^{(T)} - x^* \right\\|^2 = \tilde{\mathcal{O}} \left( \frac{1}{nT} + \frac{1}{nT^2} + \exp\left( - T\right) \right).
   $$
   where $\tilde{\mathcal{O}}$ hides the constants and polylogarithmic factors.

4. **Choice of $B$.** From (3) and Figure 2, increasing $B$ can accelerate the convergence of BTPP with respect to the number of iterations, especially when $B$ is small. At the same time, larger $B$ increases the per-iteration communication cost, and thus there is a trade-off. In practice, the actual running time can be roughly estimated as follows:

   Running time = (iteration number)$\times$(per-iteration running time)

   Given a required accuracy, the running time is a nonlinear function of $B$, and the optimal value can be determined by experiments. For example, we can start with a small $B$, and increase $B$ until the best performance is achieved. Noting that only when $B$ is small, increasing $B$ has significant impact on the convergence rate (w.r.t the number of iterations), the optimal $B$ is usually small. In the additional experiments (see the attachment), it can be seen that $B=2$ achieves the best performance in real-time.

Meta-review: This paper examines the push-pull method using a B-ary tree topology. Its most significant contribution is demonstrating a linear speedup for the push-pull algorithm over this specific network structure. Prior to this work, it was unknown whether stochastic push-pull could achieve linear speedup on any network topology. For this reason, I recommend accepting this paper. 

However, the authors are strongly encouraged to pay attention to the following points in experiments: 

1. The reported accuracy on MNIST is below 95%, which falls short of the typical 98% accuracy found in the literature. Similarly, the accuracy on CIFAR-10 is less than 85%, significantly lower than the standard >90% accuracy typically reported. These discrepancies substantially diminish the validity of the experiments. It is crucial to investigate whether the proposed algorithm can outperform all baselines when achieving the normally expected accuracy levels.

2. The additional experiments on wall-clock time raise questions. Many important details are omitted from the figure. For instance, it is unclear how centralized SGD performs global averaging—does it employ ring-allreduce? According to existing literature (e.g., Table 3 in [A1]), ring-allreduce over 8 nodes should not be twice as slow as decentralized communication with one-peer communication, as depicted in Fig. 1 of your attachment. Moreover, compared to DSGD, the proposed push-pull method requires two communications per iteration, which should further increase communication overhead. It is not evident why the proposed algorithm achieves convergence twice as fast in wall-clock time as centralized SGD using All-reduce.

The authors are strongly encouraged to clarify:
1. The time incurred for each iteration of each algorithm
2. The iteration complexity of each algorithm
3. The final wall-clock time for each algorithm

These clarifications would significantly strengthen the paper's experimental validation and address the reviewers' concerns. Please involve them when preparing the camera-ready version. 

[A1] Exponential Graph is Provably Efficient for Decentralized Deep Training
Decision: Accept (poster)