Global Update Tracking: A Decentralized Learning Algorithm for Heterogeneous Data
Authors: Sai Aparna Aketi
Abolfazl Hashemi
Kaushik Roy
Venue: NeurIPS 2023 poster (2023)
Keywords: Federated Learning
Decentralized Learning
Non-IID Data
Heterogeneous data distribution
Peer-to-peer connectivity
TL;DR: Proposed a novel decentralized learning algorithm to improve the performance over non-IID data via tracking mechanism without any communication overhead

Abstract: Decentralized learning enables the training of deep learning models over large distributed datasets generated at different locations, without the need for a central server. However, in practical scenarios, the data distribution across these devices can be significantly different, leading to a degradation in model performance. In this paper, we focus on designing a decentralized learning algorithm that is less susceptible to variations in data distribution across devices. We propose Global Update Tracking (GUT), a novel tracking-based method that aims to mitigate the impact of heterogeneous data in decentralized learning without introducing any communication overhead. We demonstrate the effectiveness of the proposed technique through an exhaustive set of experiments on various Computer Vision datasets (CIFAR-10, CIFAR-100, Fashion MNIST, and ImageNette), model architectures, and network topologies. Our experiments show that the proposed method achieves state-of-the-art performance for decentralized learning on heterogeneous data via a 1-6% improvement in test accuracy compared to other existing techniques.

Global Update Tracking: A Decentralized Learning Algorithm for Heterogeneous Data
Sai Aparna Aketi Abolfazl Hashemi Kaushik Roy
Department of Electrical and Computer Engineering Purdue University
West Lafayette, IN 47906
(saketi, abolfazl, kaushik @purdue. edu
Abstract
Decentralized learning enables training of deep learning models over large dis- tributed datasets generated at different locations, without the need for a central server. However, in practical scenarios, the data distribution across these devices can be significantly different, leading to degradation in model performance. In this paper, we focus on designing decentralized learning algorithm that is less sus- ceptible to variations in data distribution across devices. We propose Global Update Tracking (GUT), novel tracking-baas based method that aims mitigate the impact of heterogeneous data in decentralized learning without introducing any commu- nication overhead. We demonstrate the effectiveness of the proposed technique through an exhaustive set of experiments on various Computer Vision datasets (CIFAR-IO, CIFAR-I00, Fashion MNIST, and ImageNette), model architectures, and network topologies. Our experiments show that the proposed method achieves state-of-the-art performance for decentralized learning on heterogeneous data via a 6% improvement in test accuracy compared to other existing techniques.
Introduction
Decentralized learning is branch of distributed optimization which focuses on learning from data distributed across multiple agents without a central server. offers many advantages over the traditional centralized approach in aspects such data privacy, fault tolerance, and scalability
[8]. It has been demonstrated that decentralized learning algorithms [15] can perform comparable centralized algorithms on benchmark vision datasets. Decentralized Parallel Stochastic Gradient Descent (DSGD) presented in [1]] combines SGD with a gossip averaging algorithm
(26]. Further, the authors analytically show that the convergence rate of DSGD similar to its centralized counterpart
[5 A momentum version of DSGD referred to as Decentralized Momentum Stochastic Gradient
Descent (DSGDm) was proposed in ( The authors in 2 introduce Stochastic Gradient Push (SGP) which extends DSGD to directed and time-varying graphs. Recently, a unified framework for analyzing gossip-based decentralized SGD methods and the best-known convergence guarantees was presented in
One of the key assumptions to achieve state-of-the-arr performance by all the above-mentioned decentralized algorithms is that the data is independently and identically distributed (IID) across the agents. In particular, the data is assumed be distributed in uniform and random manner across the agents. This assumption does not hold in most real-world settings where the data distributions across the agents are significantly different noon-IlD/heterogeeeeoss) [9] The effect of heterogeneous data in a peer-to-peer decentralized setup is relatively under-studied problem and an active area of research.
Recently, there have been few efforts to bridge the performance gap between IID and non-IID data for a decentralized setup [6
Cross Gradient Aggregation 7 and Neighborhood
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Gradient Clustering [ algorithms utilize the concept of cross cross-gradients to reduce the impact of heterogeneous data and show significant improvement in performance (test accuracy). However, these techniques incur 2 communication cost than the standard decentralized algorithms such as DSGD. D2 algorithm proposed in [23] is shown to be agnostic data heterogeneity and can be employed in deep learning tasks. One of the major limitations of D2 is that its convergence requires mixing topologies with negative eigenvalue bounded from below by Additionally, it has been
shown that D performs worse than DSGD in some cases 16.
Tracking mechanisms such as Gradient Tracking (GT) 6 19 and Momentum Tracking (MT) [2 have been proposed to tackle heterogeneous data in decentralized settings. But these algorithms improve the performance at the cost of 2 communication overhead. The authors in [16] intro- duce Quasi-Global Momentum (QGM), decentralized learning method that mimics the global synchronization of momentum buffer to mitigate the difficulties of decentralized learning on hetero- geneous data. Recently, RelaySGD was presented in [24] that replaces the gossip averaging step with RelaySum. Since RelaySGD deals with the gossip averaging step, it is orthogonal to the afore- mentioned algorithms and can be used in synergy with them. QG-DSGDm [16] which incorporates QGM into DSGDm sets the current state-of-the-ar for decentralized learning heterogeneous data without increasing the communication cost. This work investigates the following question: Can we improve decentralized learning heterogeneous data through tracking mechanism without any communication overhead?
To that effect, we present Global Update Tracking (GUT), a novel decentralized learning algorithm designed to improve performance under heterogeneous data distribution. Motivated by, yet distinct from, the gradient tracking mechanism, we propose to track the consensus model (x') by tracking global/average model updates, where æę is the model parameters on agent at time step and is the averaged model parameters. In the traditional tracking-based methods [19 [2) that track average gradients, each agent communicates both model parameters xt and the tracking variable of with its neighbors resulting in 2 communication overhead. The proposed GUT algorithm overcomes this bottleneck by allowing agents to store a copy of their neighbors' model parameters and then tracking the model updates instead of the gradients. This results in communicating only the tracking variable of that yields the model update (x) x 1) We demonstrate the effectiveness of the proposed algorithm through an exhaustive set of experiments on various datasets, model architectures, and graph topologies. We also provide detailed convergence analysis showing that the convergence rate of GUT algorithm is consistent with the state-of- ofttt--rttttttt decentralized learning algorithms. Further, show that QG-GUTm Global Update Tracking with Quasi-Global momentum beats the current state-of-the of-te-o-thh-arr decentralized learning algorithm (i.c., QG-DSGD)) on heterogeneous data under iso iso-communication cost.
1.1 Contributions
In summary, we make the following contributions.
We propose Global Update Tracking (GUT), a novel tracking-based decentralized learning algorithm to mitigate the impact of heterogeneous data distribution.
We theoretically establish the non-asymptotic convergence rate of the proposed algorithm to a first-order solution.
Through an exhaustive set of experiments on various datasets, model architectures, and graph topologies, establish that the proposed Global Update Tracking with Quasi-Globa momentum (QG-GUTm) outperforms the current state-of-the-art decentralized learning algorithm on spectrum of heterogeneous data.
2 Background
In this section, we provide the background the decentralized setup with peer-to-peer connections.
The main goal of decentralized machine learning is to learn a global model using the knowledge ex- tracted from the locally stored data samples across n agents while maintaining privacy constraints. In particular, we solve the optimization problem of minimizing the global loss function (xx distributed across n agents as given in (I. Note that F; is a local loss function (for example, cross-entropy loss)

---

defined in terms of the data (d,) sampled from the local dataset D, at agent i.
[(x) 1 Σ fi()),
min ZER
(1)
i=1
where = (B((; for all i.
The optimization problem is typically solved by combining stochastic gradient descent global consensus-basee gossip averaging [26). The communication topology is modeled as graph G ([N], with edges {i, E E if and only if agents and are connected by communication link exchanging the messages directly. We represent (i)) as the neighbors of agent i including itself. is assumed that the graph G strongly connected with self-loops i.c., there path from every agent to every other agent. The adjacency matrix of the graph G is referred to as mixing matrix W where Wiy is the weight associated with the edge j.. Note that, weight 0 indicates the absence of direct edge between the agents, and the elements of the Identity matrix are represented by Iıj- Similar to the majority of previous works in decentralized learning, the mixing matrix is assumed to be doubly stochastic. Further, the initial models and all the hyperparameters are synchronized at the beginning the training. The communication among the agents is assumed to be synchronous.
4 with
Traditional decentralized algorithms such as DSGD 15 assume the data across the agents to be Independent and Identically Distributed (IID). In DSGD, each agent maintains local parameters xf E Id and updates them as follows.
DSGD: 27
Σ JEN(()
Wiyla) - ng9); gf (Fy(2,
We focus on a decentralized setup with oon-IID/heterogeneous data. In particular, the heterogeneity in the data distribution comes in the form of skewed label partition similar to [9]. Decentralized learning with the DSGD algorithm on heterogeneous data distribution results in performance degradation due to huge variations in the local gradients across the agents. To tackle this, authors in [16] propose momentum based optimization technique (QG-DSGDm) introducing Quasi-Global momentum as shown in 3
QG-DSGDm:
2 1+1
Σ JEN()
Wiylaf - n(gg + Bmg )]; my -um + (1 1-1)
QG-DSGDm improves the performance of decentralized learning on heterogeneous data without any communication overhead and is used baseline for comparison in this work.
Gradient Tracking (GT) mechanisms 19 22 are also known to improve decentralized learning on heterogeneous data by reducing the variance between the local gradient and the averaged (global) gradient. To achieve this, the gradient tracking algorithm introduces a tracking variable of that approximates the total gradient and is used to update the local parameters x² (refer to (4)
GT: 2
Σ (ny myf); of JEN(O
Σ JEN())
W
gi
gi.
(4)
The update rule of tracking variable is such that it recursively adds a correction term (EjENTI) Wiybi 1-1 11 to the local gradient of pushing vf be closer the global gradi- ents C Ej= g This requires each agent to communicate two sets of parameters xf and y with its neighbors. Thus, the gradient tracking algorithm improves the decentralized learning on non-lID data at the cost of 2x communication overhead.
3 Global Update Tracking
We present Global Update Tracking (GUT), a novel algorithm for decentralized deep learning on non-IlI data distribution. GUT is a communication- the difficulties of decentralized training when the data distributed across the agents is heterogeneous.
tracking mechanism that aims mitigate
In order to attain the benefits of gradient tracking without communication overhead, we propose to apply the tracking mechanism with respect to the model updates zद x!-- instead of the gradients
3

---

Algorithm Global Update Tracking (GUT)
Input: Each agent i E [1, ni initializes model parameters zy and neighbors' copy æy. step size n GUT scaling factor ft, mixing matrix W = [w]]kJE[L.)) (i)) represents neighbors of including itself, and note द = z
Each agent simultaneously implements the TRAIN( ) procedure 1. procedure TRAIN()
for t = 0, 1..,...,T T
1 do
3.
d' D;
4.
9. = V V.Fi(E :2)
5.
of ot [ Wes Wi)( x/)
6.
of = of + M
Σ why "es(U}] -03 - x()) 8 8
(EN(())
SENDRECEIVE(!)
8.
x 1+1 1
9.
$ i141 = J. - nny A j JEN(
10.
end
11. return 1 _i ITT
g. Firstly, to design tracking mechanism without additional communication cost, each agent i communicates model updates instead of model parameters to its neighbors. An agent stores copy of its neighbor's parameters as द and updates using the received model updates retrieve the current version of the neighbor's parameters as shown in line-9 of Algorithm [ A memory- efficient implementation of the algorithm (Algorithm 4 in Appendix B requires each agent to store 8; = Σ JeN( Wi instead of storing each neighbor's 's copy separately requiring only O(1) additional memory 12].
Now, we define variable 83 each agent i that accumulates the local gradient update of and the gossip averaging update Σ,(w; - Liy ) as shown in line-5 Algorithm Note that we can recover the DSGD update defined in 2 by using of in the update rule i.e., 2i xf 77 We then proceed to compute the tracking variable v/. as described in line-6 of Algorithm I using the combined model update (local gradient part and gossip averaging part) reflected by 8% The gossip averaging part of the update for each agent i i.e., Ej Wiy( (á) x;) is computed with respect to its own model weights. To account for this in the computation of tracking variable yf. the agents have to adjust the information received from the neighbors (i.e., vf ')) to change the reference to itself. This is reflected an additional term } ( 2!) in the update rule given by line-6 of Algorithm Further, we scale the correction term of the tracking variable by a factor μa, hyper-parameter, which is tuned to extract the maximum benefits of the proposed algorithm.
In summary, the update scheme of GUT can be re-formulated in the following matrix form where X = [n]] E Rdxa are the model parameters and G Ig1..... gnl Rd are stochastic gradients.
x++1 X²- r
1
(5)
yt+ 1-- - (W 1IX*t p|WY"=G' -0-
- (W -)(x+t1-x**) 1)
Finally, we show that integrating the proposed GUT algorithm with Quasi-Global Momentum improves the current state-of-the-arr significantly without any communication overhead. The pseudo-
code for the momentum version of our algorithm (QG-GUTm) is presented in Appendix B
4 Convergence Guarantees
This section provides the convergence analysis for the proposed GUT Algorithm. We assume that the following standard assumptions hold:

---

Assumption (Lipschitz Gradients). Each function f((x) is L-smooth i.e., |I (VVV) - fi(2))l
y z||-
Assumption 2 (Bounded Variance). The stochastic gradients are unbiased and their variance is assumed to be bounded.
Ea=D, [V V.fi(>))1 o² Vie [1,
(6)
Vf((z) v((=))
(7)
Assumption 3 (Doubly Stochastic Mixing Matrix). The mixing matrix W is real doubly stochastic matrix with >1 and
max (12((W)), AA, (W)I 51-
where AWW is the ith largest eigenvalue of W and p is the spectral gap.
The above assumptions commonly used in most decentralized learning setups. Theorem presents the convergence of the proposed GUT algorithm and the proof is detailed in Appendix A
Theorem 1. (Convergence of GUT algorithm) Given Assumptions 7 and
step size 1j S 7
and the scaling factor I-p < 12.
For all T 2 1, we have
Σ BI - (1(
2L 1248L2
+
+ 1/
(c² 6²+ pp),
(9)
n
where ((x) f is the sub-optimality gap, T. is the average/consensus model parameters.
The result of the Theorem ! shows that the averaged gradient of the averaged model is upper- bounded by the sub-optimality gap (the difference between the initial objective function value and the optimal value), the sampling variance (a), and gradient variations across the agents representing data heterogeneity ((). Further, we present a corollary to show the convergence rate of GUT in terms of the number of iterations.
(OV
Corollary 1. Suppose that the step size satisfies 7j
For sufficiently large T have,
T-1 Σ T
BI 00
(10)
VnT T
Corollary I indicates that the GUT algorithm achieves linear speedup with a convergence rate of when T is sufficiently large and is independent of communication topology. In other words, O v
the communication complexity find an e-first order solution, i.e., [ < i O a² This convergence rate is similar to the known best result for decentralized SGD algorithms 15 in the literature.
Experiments
In this section, we analyze the performance of the proposed GUT and QG-GUTm techniques and compare them with the baseline DSGD algorithm [13] and the current state-of-the-ar QG-DSGDm [66] respectively. The source code is available at https:::/ggtaaaaae com/ aparna- global update Secaate_traackk tracking
5.1 Experimental Setup
The efficiency of the proposed method is demonstrated through our experiments on diverse set of datasets, model architectures, graph topologies, and graph sizes. We present the analysis on (a) Datasets: CIFAR-10, CIFAR-100, Fashion MNIST, and Imagenette. (b) Model architectures: VGG-11, 20, LeNet-5 and, MobileNet-V2. All the models use Evonorm [77 as the activation- normalization layer as it is shown to be better suited for decentralized learning heterogencous data.
5

---

Figure 1: Ring Graph (left), Dyck Graph (center), and Torus Graph (right).
Ring graph with 2 peers per agent, Dyck graph with 3 peers per agent, and Torus graph with peers per agent (refer Figure T). (d) Number of agents: 16-40 agents. We the Dirichlet distribution to generate disjoint non-lllD data across the agents. The created data partition across the agents is fixed, oon-olerl,,,ing, and never shuffled across agents during the training. The degree of heterogeneity is regulated by the value of a the smaller the a the larger the non-IIDness across the agents. We report the test accuracy of the consensus model averaged over three randomly chosen seeds. The details of the decentralized setup and hyperparameters for all the experiments are presented in Appendix
(c) Graph topologies:
5.2 Average Consensus Task
We first consider an average consensus task that is isolated from the learning through stochastic gradient descent. Here the aim is that all the agents should reach consensus which is the average value of the initial information each agent holds. The following equations show the simplified version of GUT 11 and QG-GUTm (12) after removing the gradient update part.
X++1 = x + Y Y (W - I)XX' + p[WY ( 1)(x--1-XX))
(11)
X X X M = 3M--1 + -1- -
(12)
1/. 33 + (1 [) f)x* + (u (W - () -X)]]
-
Note that setting the hyper-parameter as 0 in the (II. 12 gives simple gossip[26) and quasi-global gossip [6] respectively and all the agents communicate
X at iteration with their neighbors.
F shows the average consensus error i.e., -|| XI over time for the average consensus task on The Ring topology with respect various algorithms. We observe that the gossip averaging with GUT converges faster than simple gossip averaging. Figure illustrates that for graphs with smaller spectral gap (which corresponds more agents), the proposed QG- GU'm can converge faster than quasi-global gossip (gossip with QGM) resulting in better decentralized optimization.
almalk pouip with OUT
100-
107
1o-1
geald
cimple gorco
20
G.T
16-1
00.0.mm
20-1
00:00 with 06 GUrm
mih OCN
250
550
750
1000
375
750
1125
1500
550
1000
1503
2000
Ieeation
Iteration
Iteration
64 agents
(b) 128 agents
(c) 256 agents
Figure 2: Decentralized average consensus problem undirected ring topology
5.3 Decentralized Deep Learning Results
We evaluate the efficiency of GUT and its quasi-global momentum version QG-GUTm with the help of an exhaustive set of experiments. We compare GUT with DSGD and the momentum version QG- GUTm with QG-DSGDm to show that the proposed method outperforms the current state-of-the-art

---

Table.[sshove the average test accuracy for training ResNet-20 and VGG-11 models on the CIFAR-10 dataset with varying degrees of non-IIDness over ring topology of 16 and 32 agents. We observe that GUT consistently outperforms DSGD for all models, graph sizes, and degree of heterogeneity with a significant performance gain varying from 18%. The quasi-global momentum version of our algorithm, QG-GUTm, beats QG-DSGDm with 3.5% improvement in the case of the CIFAR-10 dataset partitioned with a higher degree heterogeneity (a = 0.1, 0.01).
Table 1:
Test accuracy of different decentralized algorithms evaluated CIFAR-10, 10, distributed with different degrees of heterogeneity (non-IlD) for various models over ring topologies. The results are averaged over three seeds where the standard deviation is indicated. We also include the results of the IID baseline as DSGDm (IID where the local data is randomly partitioned independent of a.
ResNet-22 20
Agents (n)
Method
a =
a = 0.1
a = 0.01
DSGDm (IID)
89.75 + 0.29
DSGD 15
84.77 0.32
72.21 + 2.37
54.66 + 4.74
GUT (ours)
84.72 0.20
81.86 1.99
70.16
QG-DSGDm 16
88.23 + 0.51
84.21 2.12
79.85 2.11
QG-GUTm (ours)
88.22 + 0.36
86.44 + 0.36
81.04 + 1.66
DSGDm (IID)
0.223
DSGD 15
78.25 + 0.42
62.97 1.90
42.58 + 1.84
GUT (ours)
79.24 0.33
76.07
60.72 1.03
QG-DSGDm 16
87.15 + 0.33
83.50 1.04
69.99 0.60
QG-GUTm (ours)
87.48 = 0.33
84.94 + 0.60
72.04 1::00+00 3.18
VGG-11
Agents (n)
Method
= 0.1
0.01
DSGDm (IID)
85.76 0.28
DSGD [15]
81.78 0.29
76.20 0.81
68.93 1.23
16
GUT (ours)
82.12 0.09
81.24 0.95
76.62 - 1.37
QG-DSGDm 16
84.23 + 0.47
81.70 + 0.79
77.08 + 3.19
QG-GUTm (ours)
84.46 = 0.33
83.05 + 0.48
78.32 + 1.03
DSGDm (II))
84.75 0.30
DSGD
79.75 0.56
73.37 1.02
59.93 1.60
32
GUT (ours)
80.37 0.33
79.55 + 1.00
73.59 1.26
QG-DSGDm
16
83.67 + 0.28
80.82 - 0.19
74.25 - 2.02
QG-GUTm (ours)
84.32 = 0.11
83.39 + 0.38
77.41 3.44
Table 2: Average test accuracy of different decentralized algorithms evaluated on CIFAR-10 dataset trained ResNet-20 over various graph topologies
Dyck Graph (32 agents)
Torus (32 agents)
Method
Q = 0.1
Q = 0.01
Q = 0.1
a = 0.01
DSGDm IIS]
77.31 1 1.72
51.27 2.51
75.37 3.11
49.32 1 2.88
QG-DSGDm
86.49 + 0.81
81.32 1.50
86.88 0.30
85.20 + 0.56
QG-GUTm (ours)
86.93 + 0.53
84.80 = 0.47
87.75 - 0.42
86.20 0.82
Table 3: Average test accuracy of different decentralized algorithms evaluated various datasets, distributed with different degrees of heterogeneity over 16 agents ring topology
Fashion (LNNe())N
CIFAR- (ResNet-20))
Imagenette (MobileNet-V)
Method
0.1
0.01
01.1
0.01
01.
0.01
DSGDm [15]
86.59 + 0.92
77.00 3.53
47.93 + 1.69
42.56 2.71
66.02 = 4.59
38,69 11.8
QG-DSGDm 16
89.94 1: 0.44
83.43 + 0.94
53.19 1: 1.68
3.66
63.60 +: 4.50
39.49 4.57
QG-GUTm
90.11 + 0.02
84.60 1.00
53.40
1.23
50.45
66.52 3.68
43.85 -: 8.24
present the experimental results on various graph topologies and datasets to demonstrate the scalability and generalizability of QG-GUTm. We train the CIFAR-10 dataset ResNet-20 over the Dyck graph and Torus graph to exemplify the impact connectivity on the proposed technique. As shown in Table. 2 we obtain 0.5 0.5% performance gains with varying connectivity (or spectral gap).

---

Further, we evaluate QG-GUTm on various image datasets such as Fashion MNIST, and Imagenette and on challenging datasets such as CIFAR-106 100. Table. Bable.B]howw shows that QG-GUTm outperforms QG- DSGDm by 0.2 6. 6.2% across various datasets. Therefore, in decentralized deep learning setup, the proposed GUT and QG-GUTm algorithms are more robust to heterogeneity the data distribution and can outperform all the comparison methods with an average improvement of 2%.
5.4 Ablation Study
First, we analyze different ways of utilizzng or tracking model update information as shown in Table. We present two different update rules apart from GUT and DSGD(15) and also compare them with gradient tracking [99] Rule-a applies the proposed tracking mechanism on model updates but does not change the reference of tracking variable Uj received from the neighbors to itself (refer sec. for details on changing the reference). the case of Rule-b, each agent computes the difference between the averaged neighborhood model update (W (W(X* - x)) along with its own model update (X' (<'-x--) x and adds the difference between the two as a bias correction. Table, shows that such naive ways of tracking or bias correction update rules (rule-a,b) do not improve the performance of decentralized learning on heterogeneous data. This confirms our findings that the GUT technique is an effective and provable way track the consensus model and can outperform the gradient tracking mechanism without any communication overhead.
Table Analyzing the different variations of model updates. Evaluating test accuracy on CIFAR-10 dataset trained on ResNet-20 over 16 agent ring topology with = 0.1
Update
Communication Parameters (Cost)
Test
Method
Rule
accuracy
x111 n yt =G¹ -1W-
DSGD
x (1x)
72.21 2.37
x++ -x--V
Rule-a
y (LX)
72.78 + 0.80
y =0
x =x- -x--
Rule-h
re =r¹ =0--
(1x)
72.62 1.16
x -x--n(
GUT
yf (1x)
81.86 + 1.99
-0 - (W--0
Gradient Tracking
X (2x)
80.61 + 2.41
Y -0++
Table 5: Evaluating Global Update Tracking (GUT) with various versions of momentum using CIFAR-10 dataset trained on ResNet-20 architecture over 16 agents ring topology
Local
Quasi-Globar Momentum
Global Update Tracking
Test Accuracy
Method
Nesterov
Momentum
DSGD
X
72.21 2.37
DSGDm
X
X
79.87 + 1.73
DSGDm-N
X
X
81.31 0.51
QG-DDGDD
X
84.21 + 2.12
QG-DSGDM-N
x
V
X
85.12 + 1.11
GUT
X
X
V
81.86 + 1.99
GUTm
X
V
79.95 + 1.67
GUTm-N
V
X
V
82.08 + 1.74
QG-GUTm
X
V
V
86.44 + 0.36
QG-GUTm-N
X
V
86.55 55 + 0.49
We then proceed investigate the effect of different variants of momentum with GUT. From Table. (refer to Appendix for more results), we can conclude that the quasi-global variant of Global Update Tracking always surpasses the other methods. This indicates that the proposed GUT algorithm accelerates decentralized optimization and can be used in synergy with quasi-globe momentum to achieve maximal performance gains.
Furthermore, Figure 3(a) illustrates the effect of scaling y on the test accuracy with QG-GUTm and note that shows the test accuracy for QG-DSGDm. Figure 3(b) 3(c) showcase the scalability

---

of QG-GUTm on different graph sizes and model sizes. QG-GUTm outperforms QG-DSGDm by 1.7 over different graph sizes and 1.4% over different model sizes.
skowldw22 skowle/-3.d
QC-GUF 0S00m)
Q0-000 Gu--
08
07-
DSK0m
86-
Accurac
85
87
02-
84-
80-
03-
02
66
01-
76
2.54
00-
Scaling value
Number of agents
Depth of Reshet
(a) n = 16, ResNet-20
(b) a = 0.1, ResNet-20
(c) a = 0.1, n = 16
Figure 3: Ablation study on the hyper-parameter μt, number of agents n. and model size. The test accuracy is reported for the CIFAR-10 dataset trained on ResNet architecture over ring topology.
Discussion and Limitations
We demonstrated the superiority of the Global Update Tracking (GUT) algorithm through elaborate set of experiments and ablation studies. In our experiments, we focused on doubly doubly-stochastic and symmetric graph structures. The proposed GUT algorithm be easily extended to directed and time-varying graphs by combining it with stochastic gradient push (SGP) (2. Further, the additional terms added by GUT can also be interpreted pushes the local model towards the consensus (averaged) model. The matrix representation of this interpretation of GUT'S is given by (13). and analyzed in Lemma [
bias correction mechanism where the added bias
X++1 W r((G" + +B*); B+ 1 [(W - T)(X*+1 -x)) + G/
(13)
Lemma 1. Given assumptions 3, we define B' 11 where a vector of all ones. For all t, we have: Te = =ubt11
complete proof for Lemma can be found in Appendix A.2 Lemma [ [iihhlghhs that the average bias added by GUT is zero as 6 is zero. Hence, the GUT algorithm crucially preserves the average value of the decentralized system. A feature we leverage to establish Theorem
There are two potential limitations of the GUT algorithm a) memory overhead and b) introduction of an additional parameters of their neighbors which adds an extra memory buffer of the size of model parameters. The storage the tracking variable also adds to the memory overhead, requiring additional memory equivalent to the size of model parameters. We also introduce a new hyper-parameter which has to be tuned similarly to the learning rate or momentum coefficient tuning. Besides, the thcorctical analysis presented for the GUT algorithm does not consider momentum and assumes the communication to be synchronous. We leave the theoretical analysis of QG-GUTm and formulation of the asynchronous version of GUT as future research direction.
GUT requires the agents to keep a copy of the averaged model
7 Conclusion
Decentralized learning on heterogeneous data is the key to launching ML training on edge devices and thereby efficiently leveraging the humongous amounts of user-generated private data. In this paper, we propose Global Update Tracking (GUT), a novel decentralized algorithm designed to improve learning over heterogeneous data distributions. The convergence analysis presented in the paper shows that the proposed algorithm matches the best-known rate for decentralized algorithms. Additionally, the paper introduces a quasi-global momentum version of the algorithm, QG-GUTm, to further enhance the performance gains. The empirical evidence from experiments on different model architectures, datasets, and topologies demonstrates the superior performance of both algorithms. In summary, the proposed algorithm and its quasi-global momentum version have the potential to facilitate more scalable and efficient decentralized learning edge devices.

---

Acknowledgements
This work was supported in part by, the Center for the Co-Design of Cognitive Systems (COCOSYS), DARPA-sponsored JUMP center, the Semiconductor Research Corporation (SRC), and the National Science Foundation.
References
[1] Sai Aparna Aketi, Sangamesh Kodge, and Kaushik Roy. Neighborhood gradient cluster- ing: An efficient decentralized learning method for non-iid data distributions. arXiv preprint arXiv::209. /4390, 2022.
[2] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pages 444-333.
PMLR, 2019.
[3] Aditya Balu, Zhanhong Jiang, Sin Yong Tan, Chinmay Hedge, Young M Lee, and Soumik Sarkar. Decentralized deep learning using momentum-accelerated consensus. In ICASSP 202 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3675 3675-3679. IEEE, 2021.
[4] Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pages 177-186. Springer, 2010.
[5] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks.
Advances neural information processing systems, 25, 2012.
[6] Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2): 12111000-6662000001 2016.
[7] Yasaman Esfandiari, Sin Yong Tan, Zhanhong Jiang, Aditya Balu, Ethan Herron, Chinmay Hegde, and Soumik Sarkar. Cross-gradient aggregation for decentralized learning from non-iid data. In International Conference on Machine Learning, pages 3036-3046. PMLR, 2021. [8] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[9] Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-IlI data quagmire of decentralized machine learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4387- 4398. PMLR, 13-18 Jul 2020.
[10] Hamel Husain. Imagenette subset of 10 easily classified classes from the imagenet dataset. http:///github.com/fffe wtt..//ssssssaimmmeeeetttee 2018.
[11] Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393. PMLR, 2020.
[12] Anastasia Koloskova, Scbastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3478-3488 -7887 PMLR, 09-15 Jun 2019.
[13] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar (canadian institute for advanced research). http://www.cs.torooee edu/ kriz/cifar.tmll. 2014.
[14] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227-223)
1998.
[15) Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
[16] Tao Lin, Sai Pranceth Karimireddy, Sebastian Stich, and Martin Jaggi. Quasi-global momen- tum: Accelerating decentralized deep learning on heterogeneous data. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6654-6665. PMLR, 18-24 Jul 2021.
[17] Hanxiao Liu, Andy Brock, Karen Simonyan, and Quoe Le. Evolving pormalization-activaino layers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances
10

---

in Neural Information Processing Systems, volume 33, pages 15539-135555 Curran Associates, Inc., 2020.
[18] Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 37(3):92-101, 2020.
[19] Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. Mathematical Programming. 187:409-45 45009-457,10 2021.
[20] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4510-4520, 2018.
[21] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
[22] Yuki Takezawa, Han Bao, Kenta Niwa, Ryoma Sato, and Makoto Yamada. Momentum tracking: Momentum accelcration for decentralized deep learning on heterogeneous data. arXiv preprint arXiv:2209.1555 15505, 2022.
[23] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d:: Decentralized training over decentralized data. International Conference on Machine Learning, pages 4848 4856.
PMLR, 2018.
[24] Thijs Vogels, Lie He, Anastasiia Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. Relaysum for decentralized deep learning on hetcrogeneous data. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 28004-28015. Curran Associates, Inc., 2021.
[25] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 77080077477 2017.
[26] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems Control Letters, 53(1 --)6778777 2004.

---

A Convergence Rate Proof
In this work, we solve the optimization problem of minimizing global loss function f()) distributed across n. agents as given below. Note that F, local loss function (for example, cross-entropy loss) defined in terms of the data sampled (d,) from the local dataset D, at agent i.
n Σ fi(x),
min f(x) =ER
i=1 and f((x) Ed [2; Vi.
We reiterate the update scheme of GUT presented Algorithm, iin a matrix form:
X x - y = A + M|WW 1 -W 1)x - -
(14)
A' G (W- T)x;
where W is the mixing matrix, 1 is the identity matrix, X [1] 22, ................................ Inl E [R is the matrix containing model parameters, 2; E R is model parameters of agent Y = [V] 3/2........ Vnl E Rdxx is the matrix containing tracking variables, G = 191.92..... ........ghe Inl E Id is the matrix containing local gradients, μ is the GUT scaling factor, 17 the learning rate. Now, we rewrite the above equation in the form of a bias correction update,
X W +BB²)
B = - - -1x'- -x G)
(15)
A.1 Assumptions
We assume that the following statements hold:
Assumption 1 Lipschitz Gradients: Each function f((x) is L-smooth i.e., (1V [x(lll L - z|I. Equivalently,
L f( S f((x) + (Vf((). x) ? 11 x||
(16)
Assumption 2 Bounded Variance: The variance of the stochastic gradients is assumed to be bounded.
Ra-D, (2;))d)) { o² vi v [1,m)
-
Assumption 3 Doubly Stochastic Mixing Matrix: The mixing matrix W is a real doubly stochastic matrix with (WW and
mari max (())
< - <1
where X;WW) is the 7th largest eigenvalue W and p is the spectral gap. The mixing matrix satisfies Ew IZW
Z } < (1 ZW Z12 where Z 2-117. We also have W1 and
WT 1 1.
Further, we define the average gradients g' + VF(aat, d') where dj is sampled mini-batch of data node i
12

---

A.2 Proof of Lemma 1
Lemma 1 Given assumptions we define B' B¹ 117, where is a vector of all ones. For all t,
we have: B' = =
Proof. Starting from the definition of B
B
[2W - 1) - -X
+ G
T/
multiply
_1 on both sides
1
8' = at x'-1 ng 1 (:: (2W 1)1 = 1)
1
now, multiplying
11" to x WX n/G²" + HB²)
71
x++1 = x¹ "19*
nub² = 8' x²- + ng = -npb'-
7 Be = =1bb²
Given that 5 the average bias is zero at each iteration. This indicates that the proposed algorithm GUT preserves the average of the system in an average consensus task.
A.3 Proof of Theorem
This section presents the detailed proof of the convergence bounds of GUT algorithm given by Theorem Firstly, we analyze the one-step progress of the averaged model parameters ž. Note that, 3']
X ....,""] E Rd and I' Di=1 z/
Lemma 2. Given assumptions 1-3 and S Z7. we have
> < -
| -
Lnfo² + 3Ld² | 89... T Σ VS(+!)|12
Proof. From the definition of X we have
x x++1 = W
G/ + +uB]
- = x' ng (:: D'
Ofrom Lemmall 1
using L-smoothness assumption given by 16
L
+ x++1
z²)
E
x111
2
Ln
+ ((("">EE(SCE -
E
J-11
Ln
1
= =Ef(#') BB ( E(g')) +
E
VE(2D1'
2
n
1=1
1 n
Tup
Ef(E))
v((2))
(VF())) + V1(E-))12
π
(4)
Lnd
(f(()a))1 12 LoPoz
2 Ef(3') (V(('))) vf((x))
B1I Σ
71
i=1
(M)
Ef(F') +
Ln
18I
- -"
(((4)))
2
B
v(( + =BBI
Σ (77(())-\((7>)
2
13

---

(c)
(T() + LIfo²
+ 2
LTf
1
2
Σ
- "
2
+
7
Vf((z)) - {
2n
(4)
S (3(('')
+
Lni"0²
2 -
Lxp
-
- -()
| n
n
1.31
n
+
Σ
E 1 - 1
2n
(e)
7
- Lnpa²
I Ex(
3 +
E|| 1
n
(a) uses assumption-2 2 (6))
(b) uses the fact that 2( = -||||| - [|b]] + lla - B11.. (c)
uses Jensen's inequality. (d) uses L-smoothness condition. (e) follows from the assumption that
n S 4T.
Now, we proceed to bound the consensus error through Lemma Lemma 3. Given assumptions 1-3 and 1 S fL. we have
- X S 1 E|| 1 12n + 2n202 + 6x2n2² on
E B"1
Proof. Starting from the update step 15
1
- -|| - 8 112
EllW X - n/ + [B²] - -XX' -X* - )|?
n2
1 EIJWx* x - X - n (²) - -nuB'13
71
1
<
D' - 8- ([((G" B
1| + 4n)²0²
12
(0) 1+ p/2 EIIWx - 11 + 1 + 2/p)
- 1B
n
+ 447202
(6) (1( p/2) E||x 111 +
3r7
-
n
np
+ +4720²
(1 ()( tp/2)
6n7
El|x 11 + 022 +
-
n 6n722²
np
EE BIIB"
np
p/2) E E - 1 + 411202
6n² np
E -
6n221
B||B"1|
np
-//2) E E - 11 + 4170²+
61²21²
E B
np
612 2 n
1 (()E))
np
1=1
14

---

2 - p/2)
(1-
X -1 + 41700² + 12
Grj² B|B
np
12
[l]V)((z)) - -
npp
( (1 p/2)
1| + +41/202 + 12
6n/² 2²
1||
BI|B'1
11
np
12 1.2
Σ
-
- 1'1
np
i=1
p/2
12 T.2
B| - X11 +n)20² 12
n
np
6n/²u²
E B
nip
(e) 1 p/4
E|xx - -x1 + -47202 + 12n/²²
6n/21² np
E 13'1
n
P
(a) follows from the fact that ||a + b112 - (1+a))laa) + (1+ b]16611 Ya > 0 and let a = 2. (b)
uses Ew Z 3 S (1 - | 3 and 1 3 < 3. (c) uses assumption-2 (d) uses
L-smoothness condition. (e) follows from the assumption that 7) S F
The next step is to find an upper bound for the bias term BBI Lemma 4, Given assumptions 1-3 and
1 1
S 12
we have
6r222² pnll
E 1
2n 6n
B
+
81113 + n26e 1'02p(1- -
pm(1-pp
pn
Proof. starting from the update step
15
B = (2W - [)(x++1 - -x- -)(x(+1-X)) + n
[(2W D(WX n/G² nnBt - x*) n/
1)
[W(2W - -1)- + +(( - I)G + M(2 - -1)B*.
=
Now,
11B++110
113-
B||
(2W - 1) 1)X' + 2(W - 1)G" + #2W 1)B813
n
71
17
B1|
(W(2W- 1) I)x* + 2(W T)GT G*) + M(2W - 1)
17
1
1
B1|
(2W -1) -)X* + 2(W D)E - 69 + # 1)
17
+
EE]((W -T) E|G') (G¹ E(G'
7
Bl| [ (T W(W I)Xx 2(W T)B[G* - G w(2W - 11
72
1)
+ 2
(4)
1 11
- -1) 802
n
+ 1
Bll 1 (1- - w2W - +2( - G)E - G'
1
15

---

" B|1B"P + +80²+ +
2
E E - 1
n(1 1I)
2
BII(1 - W2W 11
(1 11)
1- (1 11)
E B" 113 80 + n21 μi)
E|| 1/
n
2
+ 2 (4)
B2|(2W + T)(T - 11
(6) 1 (1 (1)
E
| 3/- + 80²
El E - G
n(1 μ)
18
+ (1 11)
EI[(1 - 1
(1 - 11)
E B //- + 808 + n(1 11)
E| - 1/
18
B][(T W)(X - x1
21 (1)
(1 11)
36
1 P + So² + 11 11)
E8 1 111
-
+ n(1 p))
E| V5(3') - E
(1 p)
36
F So²
E|| - -IIX- 111
n
m1 14)
8
41.
| 1
- J
n(1 11)
(1 - p)
4(9 17
862
E
B" 1/ + S0² +
B1|x -x113 + 1- P
m1 14)
Multiplying both sides with un²
x1-
67²² 212
6n2 p1²
61
24(9 1,?
E||B++111
11 =
B||B"| 11
E E 11
np(1 - 1))
npp11 - 4)
np
np(1 - 11)
48y 21 02
2222
+
p(1 - 14)
p(1 - 11)2
6n²² n₂²
6n/²μ²
E1IB"11 + -
-
np(1 11)
np
8n
7" po (1 - (4)
8
Note that W - I I I, I- W < 21, (W - -1\ = 0 and (W- - I) = 0. (a) follows from the
fact that ||a + b122 < (1 + a)]la|a 12 (1 + 1)1Bb12 Va > 0 and let a p
1- (b) uses the fact that
||AB|| 1/- S o ma BA) where A = 2W + B (I W and o (A) 9. (c) uses the
assumption I- ft and 7 S z/4 This implies that 24 y of and 48
p(1
We present the proof for Theorem | using Lemmas. and Adding Lemmas. and and simplifying, we get
16

---

24I2'1
14 B|B++11 S
24
3T.21 B B
x
x
X'1
n
n12 -H)
72
n
(17)
144 2 (1-1) BIBBI
3121"1/
(c2 + 0² (2 pt)
p²
Finally, define function of as shown below
24T.'
14 n12 - p))
Φ'
E X
+ f*1
(18)
Now adding Lemma and 17 we have the following
LIj²O² 312L21/
D1+1
<Φ.-
7
E
2
(52 + o² 1d)
P²
Lnj 312L3n
<Φ.
"
(G2 02 (2 11)
n
p²
Tnpo²
312121p
-01-
(c2 + 02 (2 H))
p²
Summing over
4 EIVs
nr (1(6
4Lo²
+ 122
124822
(52 + n)) (19)
+
n
p²
This concludes the proof of the Theorem
A.4
Proof of Corollary. J
In the proof Theorem we assumed the following the following constraints on learning rate ry and scaling factor μı:
1 (L
17 S min
7L
< 8
ii
μ 42
We assume that the step size 7) (( T ) where is the total number of agents and T is the number of iterations. Given this assumption, we have the following order of each term in (19) of Theorem
n/T (5(30 - 1*) -
VnT
For the remaining terms we have,
4Lo² O
1248I2 Ø
(5² +
0 4)) 0
n2 T
1 n
Therefore, by omitting the constant n in this context of higher order terms, there exists a constant C > O such that the overall convergence rate is as follows:
(+==+) 1 7)
E [
T
VnIl
which suggests when I' is sufficiently large, GUT enables the convergence rate of O 1
Vnl
17

---

B
Algorithmic details
In this section, we present the pseudo-code for QG-GUTm which combines the proposed GUT algorithm with quasi-global momentum Algorithm 2 and its PyTorch implementation version shown Algorithm also summarize memory-efficiet implementation GUT in Algorithm
Algorithm 2 Global Update Tracking with momentum (QG-GUTm)
Input: Each agent [1, ni] initializes model weights (0) and neighbors' copy =/0) momentum
buffer mi (0) step size 1/, momentum coefficient B, mixing matrix W [usy]kJee(.m)) GUT scaling factor μ4, Iy are elements of identity matrix, (((i) represents neighbors of including itself, and note f = x/.
Each agent simultaneously implements the TRAIN( ) procedure 1. procedure TRAIN()
for t= 1....,T do
d D
4.
9. Vzfi(di; Ejer()) wij * 25)
of di - (wis (ig) * :..
of 8 + +1| Σ
Wis (m)(m)) 1 (2g x!)) 8:-11
jEN(()
m = Bmt
+11 B)y!
8.
SENDRFCHIVE(In))
9.
1/ 1+1 1 -nm
10.
1++ 23) nmn A j N(IV
11.
end
12.
return
Algorithm Global Update Tracking with momentum (QG-GUTm) Pytorch Implementation
Input: Each agent E [1, n2] initializes model weights x and neighbors' copy $ (0) momentum
buffer m (0) step size momentum coefficient B, mixing matrix W [wiylije(1,n (1..)) GUT scaling factor Lg are elements of n x identity matrix, Aiii represents neighbors of including itself, and note ff x/.
Each agent simultaneously implements the TRAIN() procedure 1. procedure TRAIN( ) for t=0, ....... T 1 do
3.
d' D;
g. V V.lidd EjEN(H) Whj * :455)
5.
σ of E (wij 11Ú) Jt.
6.
o 8 + m1
Σ
wiy (my 1+8 (3) x!)) 61-
jEN(1)
7.
m Amt -- + y
SENDRECHiVE(m'))
x1t 1+1 = 1/ mm
10.
# = 83 nmm A j N(O)
11.
end
12.
return
18

---

Algorithm 4 Global Update Tracking (Memory Efficient Implementation)
Input: Each agent i E [1, ril initializes model parameters x and weighted model parameters of neighborhood s,. step size 7), GUT scaling factor μ. mixing matrix W [wig]kJe(1,n] (i) represents neighbors of i including itself.
Each agent simultaneously implements the TRAIN() ) procedure
1. procedure TRAIN( for = 0,
do
3.
d D;
4.
9. = v Fy (s d:)
(s
of = gi 1 (s - x!)
6.
of of + 1
Σ WiyUh
(s) xt)) 0:-1
(i)
7.
SENDRECHITT(U))
8.
x ++1 _ ny!
9.
++1 5 - )E))(()))))) Wiylij
10.
end
11. return
1 - x
C Decentralized Learning Setup
For the decentralized setup, graph topologies with a uniform mixing matrix. The undirected ring topology for any graph size has 3 peers per agent including itself and each edge has weight of 3. The undirected Dyck topology with 32 agents has 4 peers per agent including itself and each edge has a weight of 1. The undirected torus topology with 32 agents has 5 peers per agent including itself and each edge has weight of } All our experiments were conducted on system with Nvidia GTX 1080ti card with 4 GPUs except for ImageNette simulations. We used NVIDIA A40 card with GPUs for ImageNette simulations.
undirected ring, undirected Dyck graph, and undirected torus
C.1 Datasets
In this section, we give brief description of the datasets used in experiments. We use diverse set of datasets each originating from a different distribution of images to show the generalizability of the proposed techniques.
CIFAR-10: CIFAR-10 [13] an image classification dataset with 10 classes. The image samples are colored (3 input channels) and have resolution of 32 x 32. There are 50, 000 training samples with 5000 samples per class and 10, 000 test samples with 1000 samples per class.
CIFAR-100: CIFAR-100 13 is an image classification dataset with 100 classes. The image samples are colored (3 input channels) and have a resolution of x 32. There are 50, 000 training samples with 500 samples per class and 10, 000 test samples with 100 samples per class. CIFAR-100 classification is harder task compared CIFAR- as it has 100 classes with very few samples per class to learn from.
an image classification dataset with 10 classes. The image samples are in greyscale (I input channel) and have a resolution of 28 x 28. There are 60, 000 training samples with 6000 samples per class and 10, 000 test samples with 1000 samples per class.
Fashion MNIST:
Fashion MNIST 25
Imagenette: Imagenette T0 is 10-class subset of the ImageNet dataset. The image samples are colored (3 input channels) and have resolution of 224 224. There are 9469 training samples with roughly 950 samples per class and 3925 test samples.
C.2 Network Architecture
We replace Borth layers of the model architectures with EvoNorm-SO as was shown to be better suited for decentralized learning over non-lID distributions.
19

---

We modify the standard VGG-11 [2T] architecture by reducing the number of filters in each convolutional layer by 4x and using only one dense layer with 128 units. Each convolutional layer is followed by EvoNorm-SO as the activation-normalizaaa layer. VGG-11 has 0.58M trainable parameters.
VGG-11:
ResNet-20: For ResNet-20 [8] we use the standard architecture with 0.27M trainable parameters except that BatchNorm+ReLU layers are replaced by EvoNorm-SO.
LeNet-5: For LeNet-5 14 we use the standard architecture with 61, 706 trainable parameters.
MobileNet-V2: We use the the standard MobileNet- V2 [20] architecture used for CIFAR dataset with 2.3M parameters except that BatchNomm+ReLU layers are replaced by EvoNorm-SOO.
C.3 Hyper-parameters
This section presents a detailed description of the ppper--arameterss used in our experiments. All the experiments were run for three randomly chosen seeds. We decay the step size by 10x after 50% and 75% of the training, unless mentioned otherwise. The hyper-paramett j is set to 0.9 for all the experiments using GUT optimizer. We used grid search to choose the hyper-parameter l for QG-GUTm.
for experiments in T All the experiments have the stopping criteria set to 200 epochs. The initial learning rate set to 0.1. We decay the step size by 10x multiple steps at 100th and 150th epoch. 6able presents values of the scaling factor μ used in the experiments. For all the experiments, we use mini- batch size of 32 per agent. The stopping criteria a fixed number of epochs. We have used momentum of 0.9 for all QG-DSDm and QG-GUTm experiments.
Table 6: The value of scaling factor y used for training CIFAR-10 with non-llI data using ResNet-20 and VGG-11 model architectures presented in Table
ResNet-20 0.1
Agents (n)
Method
Q
a 0.01
DSGD
0.0
0.0
0.0
GUT (ours)
0.9
0.9
0.9
16
QG-DSGDm
0.0
0.0
0.0
QG-GUTm (ours)
0.04
0.06
0.04
DSGD
0.0
0.0
0.0
GUT (ours)
0.9
0.9
0.9
32
QG-DSGDm
0.0
0.0
0.0
QG-GUTm (ours)
0.04
0.04
0.04
VGG-11
Agents (n))
Method
a =
0.1
a
0.01
DSGD
0.0
0.0
0.0
GUT (ours)
0.9
0.9
0.9
16
QG-DSGDm
0.0
0.0
QG-GUTm (ours)
0.06
0.08
0.09
DSGD
0.0
0.0
0.0
GUT (ours)
0.9
0.9
0.9
32
QG-DSGDm
0.0
0.0
QG-GUTm (ours)
0.08
0.08
0.08
Hyper-parameters for experiments in Table All the experiments have the stopping criteria set to 200 epochs. The initial learning rate is set to 0.1. We decay the step size by 10x in multiple steps at th and 150th epoch. Table presents values the scaling factor μ used in the experiments. For all the experiments, number of epochs. For all QG-DSDm and QG-GUTm experiments, we have used momentum of 0.9 and Nesterov is set to False. We did not use any regularization in experiments non-IID data i.e., weight decay is set to zero. We set the weight decay to be le for experiments on IID data (DSGDm case in Table. D.
use mini-batch size of 32 per agent. The stopping criteria is fixed
Hyper-parameters for experiments in Table 3 All the experiments with Fashion-MNIS" and Imagenette datasets have the stopping criteria set to 100 epochs where as CIFAR- 100 experiments
20

---

Table 7: The value of scaling factor used for training CIFAR-10 with non-lID data using ResNet-20 model architecture over varies graph topologies presented in Table
Dyck Graph (32 agents)
Torus (32 agents)
Method
0.1
a = 0.01
0.1 a = 0.01
QG-DSGDm
0.0
0.0
0.0
0.0
QG-GUTm
0.05
0.05
0.05
0.05
have the stopping criteria 200 epochs. The initial learning rate is set 0.1 for experiments CIFAR- 100 and Fashion MNIST datasets. The initial learning rate is set to 0.01 for experiments on the Imagenette dataset. We decay the step size by 10x in multiple steps 50th and 75th epoch. Table 8 presents values of the scaling factor μ used in the experiments. For all the experiments, we use mini-batch size of 32 per agent. The stopping criteria is fixed number of epochs. We have used a momentum of 0.9 for all JG-DSDm and QG-GUTm experiments.
Table 8: The value of scaling factor μ used for training different datasets over 16 agents ring topology presented in Table 3
Fashion MNIST (LeNet-5)
CIFAR (ResNet-20)
Imagenette (MobileNet-V2
Method
= 0.1
a 0.01
= 0.1
= 0.01
a = 0.1
a = 01.01
QG-DSGDm
0.0
0.0
0.0
0.0
0.0
0.0
QG-GUTm
0.01
0.005
0.005
0.005
0.03
0.04
D Additional Results
Table. 9 shows that the quasi-global variant of Global Update Tracking surpasses the other existing methods even for higher degree of heterogeneity i.e., 0.01. We also observe that the Nesterov momentum hurts the performance when the heterogeneity in the data distribution is high. Table TO compares the DSGDm baseline with the proposed GUT and QG-GUTm. It shows that for higher degree of heterogeneity, GUT outperforms even the momentum version DSGD. Table. Table.[[Tevallatee. the proposed method on various datasets trained
model architecture (ResNet-20).
Table 9: Evaluating Global Update Tracking (GUT) with various versions of momentum using CIFAR-10 dataset trained on ResNet-20 architecture over 16 agents ring topology for a 0.01.
Local Momentum
Quasi-Global Momentum
Global Update Tracking
Test Accuracy
Method
Nesterov
a 0.01
DSGD
54.66 + 4.74
DSGDm
X
X
65.62 + 4.95
DSGDm-N
V
V
63.66 + 4.44
QG-DSGDm
X
X
4
79.85 + 2.13
QG-DSGDm-N
78.64 + 2.14
GUT
70.16 + 4.94
GUTm
V
X
X
64.25 + 5.31
GUTm-N
V
63.42 2.74
QG-GUTm
X
X
81.04 + 1.66
QG-GUTm-N
80.09 + 3.82
E Hardware Efficiency
In this section, we present the quantitative results on communication, memory, and compute overheads of the various decentralized algorithms. The communication cost incurred by the proposed GUT
21

---

Table 10: Average test accuracy of different decentralized algorithms evaluated on CIFAR- 10,
distributed with different degrees of heterogeneity (non-IID) for various models over ring topologies.
ResNet-20
Agents (m)
Method
a 0.1
0.01
GUT (ours)
84.72 - 0.20
81.86 1 1.99
70.16 = 4.94
16
DSGDm [S
86,60 = 0.54
79.87 + 1.73
65.62 = 4.95
QG-GUTm (ours)
88.22 0.36
86.44 + 0.36
81.04 1.66
GUT (ours)
79.24 = 0.33
76.07 + 0.23
60.72 = 1.03
DSGDm 15
86.12 = 0.32
77.43 + 1.71
52.82 = 4.02
QG-GUTm (ours)
87.48 0.33
84.94 +: 0.60
72.04 3.18
VGG-11
Agents (n)
Method
0.1
0.01
GUT (ours)
82.12 = 0.09
81.24 1: 0.95
76.62 = 1.37
DSGDD 15
81.77 = 0.38
74.20 + 1.89
58.44 14.58
QG-GUTm (ours)
84.46 0.33
83.05 + 0.48
78.32 1.03
GUT (ours)
80.37 = 0.33
79.55 + 1.00
73.59 = 1.26
32
DSGDm 05
81.89 = 0.29
74.73 + 0.73
61.60 = 2.80
QG-GUTm (ours)
84.32 0.11
83.39 + 0.38
77.41 3.44
Table 11: Average test accuracy of different decentralized algorithms evaluated with various datasets trained on ResNet-20 architecture, distributed with different degrees of heterogeneity over 16 agents ring topology.
Method
Fashion MNIST
CIFAR-II 100
Imagenette
0 0.0T
0.01
DSGDD 15
87.89 +: 2.34
79.41 +: 3.29
47.93 4: 1.69
42.57 2.71
66.89 +: 3.12
47.87 : 4.03
QG-DSGDm
16
92.21 +: 0.01
90.59 + 0.92
53.19
+: 1.68
3.64
73.93 + 2.01
56.30 +: 5.43
QG-GUTm
92.55 + 0.16
91.70 : 0.36
53.40 = 1.23
50.45 + 1.30
7
57.47 = 5.33
and QG-GUTm methodologies is the same as the DSGD or QG-DSGDm techniques. All the above- mentioned algorithms communicate vector with the size same the model parameters. However, gradient tracking incurs 2x communication cost in terms of model size. The communication cost and memory requirements for all the experiments are reported in Table. 12 and 13
We report the numbers for communication, memory, and compute overheads for the memory- implementation of GUT Algorithm, in Table. 14 Memory overhead is reported the percentage of additional memory required per agent during training with a batch size of 32.
Memory overhead Additional memory due GUT
Total Memory
The total memory includes the memory required to store model parameters, activations, gradients, gossip buffer, tracking variable (yi), and weighted neighbors' parameters (s:). We observe that for compact models such as ResNet and MobileNet, the memory overhead is less than 2%. However, for larger models such as VGG-11, the memory overhead shoots up to 14%. The computational overhead reported the percentage of additional FLOPs required per sample per agent during training.
Compute overhead Additional compute due to GUT
Total Compute
The total compute includes the forward pass. backward pass, model updates, gossip averaging. and tracking variable computation flops. We observe that for compact models such as ResNet and MobileNet, the compute overhead is around 2%. However, for larger models such as VGG-11, the compute overhead shoots to 15%.
22

---

Table 12: Communication cost and memory requirement per agent during training of CIFAR-I0 dataset on various model architectures and graph topologies.
Comm. Cost
Memory
Model
Graph
Graph Size
Method
(GB)
(MB)
Gradient Tracking
83,66
129.60
ResNet-20
Ring
16
QG-DSGDm
41.83
128.56
QG-GUTm
41.83
130.64
Gradient Tracking
41.93
129.60
ResNet-20
Ring
32
QG-DSGDm
20.97
128.56
QG-GUTm
20.97
130.64
Gradient Tracking
83,86
129.60
ResNet-20
Torus
32
QG-DSGDm
41.93
128.56
QG-GUTm
41.93
130.64
Gradient Tracking
62.90
129.60
ResNet-20
Dyck
QG-DSGDm
31.45
128.56
QG-GUTm
31.45
130.64
Gradient Tracking
178.02
31.84
VGG-11
Ring
QG-DSGDm
89.01
29.63
QG-GUTm
89.01
34.05
Gradient Tracking
89,22
31.84
VGG-11
Ring
32
QG-DSGDm
44.61
29.63
QG-GUTm
44.61
34.05
Table 13: Communication cost and memory requirement incurred per agent during training of various dataset and model architectures over 16 agents ring topology.
Comm. Cost
Memory (MB)
Dataset
Model
Method
(GB)
Gradient Tracking
11.42
4.86
Fashion MNIST
LcNet-5
QG-DSGDm
5.71
4.62
QG-GUTm
5.71
5.10
Gradient Tracking
85.46
129.72
CIFAR-100
ResNet-20
DG-DSGDm
42.73
128.66
QG-GUTM
42.73
130.78
Gradient Tracking
68.86
3774
Imagenette
MobileNet- V2
QG- QG-DSGDm
34.43
3765
QG-GUTm
34.43
3782
Table 14: Communication, memory, and compute overhead incurred per agent during training of various datasets and model architectures for the proposed GUT algorithm. Note that the overheads are independent of the graph topology and graph size.
Dataset
Model
Communication Overhead
Memory Overhead
Compute Overhead
Fashion MNIST
LcNet-5
0.00
0.099
0.275
CIFAR-10 -10
ResNet-20
0.00
0.016
0,021
CIFAR-10
VGG-11
0.00
0.138
0.149
CIFAR-100
ResNet-20
0.00
0.016
0.022
Imagenette
MobileNet-V2
0.00
0.005
0.021
23


Reviews:
[{"review_id": "lxiYWPOjMQ", "reviewer": "Reviewer_LUfd", "summary": "The authors propose an algorithm for decentralized learning, where training datasets with heterogenous distributions are collected across different devices. They propose a global update tracking (GUT)-based approach where the IID assumption for the data is removed, and aim to generalize their method to non-IID data by tracking the consensus model while reducing the communication overhead by their GUT algorithm, at the expense of additional memory for storing the parameters for the neighboring model. They validate their method by experiments on various  datasets.\n", "questions": "Please refer to the questions in the weaknesses section. Since I am not an expert in this field, my positive and negative opinions are mixed.\n\nAdditionally, repeating the full paper in the supplementary materials seems unnecessary.\n", "limitations": "The authors included a separate discussions and limitations section in their paper, with adequate explanations and descriptions on the weaknesses and possible future directions.\n", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Proposed method is applicable to more realistic settings for decentralized learning, where non-IID heterogeneous distribution is more common for the real world data.\n\n- Their GUT-based approach adds minimal computational overhead on the overall agents, and they show the performance of their algorithm on multiple datasets in the experimental results.\n\n- They provide ablation studies for further analysis on the hyperparameter sensitivity, different levels of heterogeneity, and various implementations of momentum.\n\n- Authors provide the source code for their implementation in the supplementary materials.\n", "weaknesses": "- Since one of the main claims of this approach is its generalizability to non-IID heterogeneous data distributions for each agent, what aspect in the proposed formulation corrects the gap between the individual distributions?\n\n- Compared to previous decentralized learning approaches where the agent tracks gradients, momentum of gradients, or gloabl gradient obtained from the adjacent agents, proposed GUT tracks model updates. What statistical characteristic/effect makes the model update ($x^{t+1}_i - x^{t}_i$) beneficial for tracking? A simple toy (e.g. Gaussian) example experiment with update with/without model update tracking would suffice.\n\n- Are there any visualizations for non-IID characteristic on the datasets under varying degree of $\\alpha$? Also, are there experimetal results of additional memory consumption and computational overhead due to the additional update terms?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback. We answer the questions raised in the weakness section here.\n1. In the proposed methods, the local model parameters are updated using the tracking variable $y_i$ instead of the local gradient $g_i$. The key idea is that the tracking variable $y_i$ corrects for the bias in the gradient computation and hence is closer to the true/average gradients compared to $g_i$. The update rule for $y_i$ is given in line-6 of algorithm 1 in the main paper. In the given update rule, $\\delta_i^t$ indicates the default/DSGD update vector (without GUT), and $y_i^t$ is the update vector with GUT. The difference between $\\delta_i^t$ and $y_i^t$ is the scaled correction/tracking term. For simplicity (easier understanding), let's ignore the correction term $ \\implies y_i^t - \\delta_i^t = \\sum\\limits_{j\\in \\mathcal{N}(i)}w_{ij}y_j^{t-1}  - \\delta_i^{t-1}$. We compute the difference between the default update $\\delta_i^{t-1}$ and the averaged updates of the neighborhood i.e., $\\sum\\limits_{j\\in \\mathcal{N}(i)}w_{ij}y_j^{t-1}$ from the previous iteration and add it as a bias correction to the current iteration update. This bias term corrects for the gap between the individual distributions. \n2. The goal of this work is to track the average/global gradient without incurring additional communication overhead. To achieve this, we communicate and track the model updates i.e., $x_i^{t+1} - x_i^t$. The term  $(x_i^{t+1} - x_i^t)$ can be split into two components - (a) the gradient update $(g_i^t)$ and (b) the correction added through gossip update $(\\sum\\limits_{j\\in \\mathcal{N}(i)}w_{ij}*(x_j^t-x_i^t))$. So by tracking model updates, we are inherently tracking global gradient i.e., $\\frac{1}{n} \\sum\\limits_j g_j^t$, and also the global gossip error i.e., $\\frac{1}{n} \\sum\\limits_j(x_j^t-x_i^t)$. Hence, GUT benefits from tracking both global gradients and gossip error. The statistical effect of the tracking is shown in Figure. 2 of the main paper. We set up a simple gossip averaging task -- each agent is initialized with a random vector $x_i$ and the goal is to compute the average value of $x$ i.e., $\\frac{1}{n} \\sum\\limits_jx_j$ through gossiping with neighbors. Figure. 2 plots the consensus error over time with and without model update tracking. We observe that gossip with model update tracking converges (reaches lower error) faster than simple gossip. Note that $n$ is the total number of agents and $\\mathcal{N}(i)$ is the neighbors of agent $i$.\n3. (a) We use the standard Dirichlet distribution to generate the non-IID Data. The visualization of the CIFAR-10 dataset with varying degrees of alpha on a 16-agent ring topology can be found in Figure.1,8 of [1]. We will add similar bubble plots for all our experiments in the appendix. \n(b) The memory overhead for GUT is equivalent to 2*model-size and the computation overhead comes from the computation of tracking variable $y_i$. Table 1 below reports the numbers for memory and computational overheads for the memory-efficient implementation of GUT presented as Algorithm. 4 in the appendix. \n\nTable 1: Communication, memory, and compute overhead incurred per agent during training of various datasets and model architectures for the proposed *GUT* algorithm. Note that the overheads are independent of the graph topology and graph size.\n|Dataset| Model | Memory Overhead | Compute Overhead | Communication Overhead|\n|---------|---------|:---------:|:---------:|:---------:|\n|Fashion MNIST| Lenet-5|0.099|0.275|0.00|\n|CIFAR-10| ResNet-20|0.016|0.021|0.00|\n|CIFAR-10|VGG-11|0.138|0.149|0.00|\n|CIFAR-100|ResNet-20|0.016|0.022|0.00|\n|ImageNette| MobileNet-V2| 0.005|0.021|0.00|\n\n$\\text{Memory overhead} = \\frac{\\text{Additional memory due to GUT}} {\\text{Total memory}}$\n\nMemory overhead is reported as the fraction of additional memory required per agent during training with a batch size of 32 per agent. The total memory includes the memory required to store model parameters, activations, gradients, gossip buffer, tracking variable, and weighted neighbors’ parameters. We observe that for compact models such as ResNet and MobileNet, the memory overhead is less than 2%. However, for larger models such as VGG-11, the memory overhead shoots up to 14%.\n\n$\\text{Compute overhead} = \\frac{\\text{Additional compute due to GUT}} {\\text{Total compute}}$\n\nThe computational overhead is reported as the fraction of additional FLOPs required per sample per agent during training. The total compute includes the forward pass, backward pass, model updates, gossip averaging, and tracking variable computation flops. We observe that for compact models such as ResNet and MobileNet, the compute overhead is around 2%. However, for larger models such as VGG-11, the compute overhead shoots up to 15%. \n\nWe have answered all the questions raised by the reviewer and would be happy to answer any further questions.\n\n[1]. Lin, T., Karimireddy, S.P., Stich, S. & Jaggi, M.. (2021). Quasi-global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data. Proceedings of the 38th International Conference on Machine Learning.\n\n\n"}, {"review_id": "AeoSMQcKIs", "reviewer": "Reviewer_NsAw", "summary": "The paper proposes a new decentralized learning algorithm called Global Update Tracking (GUT) that can mitigate the impact of heterogeneous data in decentralized learning without introducing any communication overhead. The proposal was demonstrated 4 computer vision datasets.", "questions": "Please see weaknesses.", "limitations": "There are several limitations that the authors should address: \n\n1. The data partition across agents is not clearly explained. Necessary details for all datasets is required. For example, number of samples per class per agent. Implementation details are also missing from the main paper.\n\n2. Detailed comparison with the related methods is missing. For example, Table 3 compare performance on 3 datasets but no related method is shown.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper proposes an important and useful application for training deep learning models in decentralized way. There are many strengths of the proposal including the following: \n\n1. GUT is less susceptible to variations in data distribution across devices as shown by different experiments and ablation study\n\n2. The performance is better than DSGD and DSGDm. However, it is shown only for CIFAR-10.", "weaknesses": "There are several questions: \n\n1. The paper claims that GUT does not introduce any communication overhead but no results are shown to justify that. However using Figure 2, authors have claimed that their method converges faster than quasi global gossip. The comparison/improvement is not clear from the figure. \n\n2. The author claim that agents in GUT store copy of their neighbors. How often this copy is updated? What is the communication overhead in that?\n\n3. Performance comparison with related methods is not shown on all 4 datasets.\n\n4. The data partition is fixed, non-overlapping and never shuffled across agents during training. How does this partition is defined?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback. We answer each of the questions raised in the weakness section here. \n1. (a) GUT/QG-GUTm communicates model updates $(x^{t}-x^{t-1})$ whereas DSGD/QG-DSGDm communicates model parameters $x^{t}$. Both these vectors are of the same size i.e., model size. We present the communication cost in terms of the data transferred per agent during training in **Table.R3** in the attached rebuttal pdf. \n(b) Figure 2 plots the consensus error for a simple gossip averaging task with varying graph sizes (spectral gap). We compare gossip with GUT (dotted blue curve) with simple gossip (dotted red curve). The figure shows that gossip with GUT reaches a lower consensus error than simple gossip. We also plot the consensus error for the quasi-momentum version of both algorithms. Simple gossip with QGM is shown by the solid red curve and GUT with QGM is shown by the solid blue curve. Figure.2(c) illustrates that for graphs with a smaller spectral gap (which corresponds to more agents), the proposed QG-GUTm can converge faster than quasi-global gossip (gossip with QGM).\n2. The neighbors’ copy is updated in every iteration (line 9 in Algorithm 1) and does not require additional communication. The main difference between DGSD and GUT is the type of information that the agents communicate but both algorithms communicate vectors of the same size. In the DSGD algorithm, a given agent $i$ receives the model parameters $x_j^t$ at each iteration from its neighbors and uses it for gossip averaging. Whereas in GUT,  a given agent $i$ receives the model updates $(x_j^{t}-x_j^{t-1})$ at each iteration from its neighbors and recovers $x_j^{t}$ by adding the received model update $(x_j^{t}-x_j^{t-1})$ to the stored copy of $x_j^{t-1}$. Now we use the recovered $x_j^t$ for gossip averaging and model updates for bias computation or tracking.\n3. We compare CIFAR-10 with DSGD, DGSDm, and QG-DSGDm. However, for the remaining datasets in Table. 3, we compare with QG-DSGDm as it is the existing state-of-the-art baseline for heterogenous data with no communication overhead. For more baselines, we report DSGDm along with QG-DGSDm in **Table.R2** in the attached rebuttal pdf. \n4. At the beginning of the training, we divide the dataset across the agents where the label distribution follows the Dirichlet distribution and the non-iidness or the skew is controlled by the factor $\\alpha$. The dataset is sampled without replacement and hence is non-overlapping across the agents i.e., each agent has a different part of the training dataset. We don't shuffle the dataset across the agents during the training. The visualization of the CIFAR-10 dataset with varying degrees of alpha on a 16-agent ring topology can be found in Figure.1,8 of [1]. We will add similar bubble plots for all our experiments in the appendix. \n\nWe answer each of the questions raised in the Limitations section here. \n1. For the interest of the space in the main paper, we added the implementation details of our experiments in Appendix C. We will include the class distribution across agents in the appendix and also add bubble plots for visualization. \n2. We compared the results in Table 3 with QG-DSGDm which gives the best accuracy among the existing works and show that the proposed algorithm outperforms it. For more baselines, we report DSGDm along with QG-DGSDm in Table.R2 of the attached rebuttal pdf and also presented below as Table. 1.\n\nTable 1: Average test accuracy of different decentralized algorithms evaluated on various datasets, distributed with different degrees of heterogeneity over 16 agents ring topology.\n|Method | Fashion MNIST |Fashion MNIST |CIFAR-100 | CIFAR-100| Imagenette |Imagenette|\n|----------|----------|----------|----------|----------|----------|----------|\n| | $\\alpha=0.1$ | $\\alpha=0.01$ | $\\alpha=0.1$ | $\\alpha=0.01$ | $\\alpha=0.1$ | $\\alpha=0.01$|\n | DSGDm  | $86.59 \\pm 0.92$ | $77.00 \\pm 3.53$ | $47.93 \\pm 1.69$ | $42.56 \\pm 2.71$ |$66.02 \\pm 4.59$ | $38.69 \\pm 11.8$ |\n |QG-DSGDm  | $ 89.94 \\pm 0.44 $ | $ 83.43 \\pm 0.94 $ | $ 53.19 \\pm 1.68 $ | $ 44.17 \\pm 3.64 $ | $ 63.60 \\pm 4.50 $ | $ 39.49 \\pm  4.57$|\n |*QG-GUTm (ours)*| $ \\mathbf{90.11} \\pm 0.02 $ | $ \\mathbf{84.60} \\pm 1.00 $ | $ \\mathbf{53.40} \\pm 1.23 $ | $ \\mathbf{50.45} \\pm 1.30 $ | $ \\mathbf{66.52} \\pm 3.68 $ | $ \\mathbf{43.85} \\pm 8.24 $ |\n\nWe have answered all the questions raised by the reviewer and would be happy to answer any further questions.\n\n[1]. Lin, T., Karimireddy, S.P., Stich, S. &amp; Jaggi, M.. (2021). Quasi-global Momentum: Accelerating Decentralized Deep Learning on Heterogeneous Data. Proceedings of the 38th International Conference on Machine Learning."}, {"review_id": "6oqYuCh5yc", "reviewer": "Reviewer_tQhr", "summary": "The performance of decentralized learning is limited to the different distribution over devices. To address this issue, this paper proposes a method that is less susceptible to variations in data distribution, named GUT. The proposed GUT tracks the global/average model updates. Experiments show GUT achieves good performance on some benchmarks with various models. The paper also analyzes the convergence of the proposed method.", "questions": "In rebuttal, the reviewer hope to see the response to 2),4)-7) in weaknesses.", "limitations": "The paper provides a compelling discussion about the limitation.", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1) The issue of heterogeneous data on devices in decentralized learning is critical, the paper shows a good motivation to address this.\n2) On the given benchmarks and models, the proposed method seems to perform well.\n3) The analysis of convergence of the method is detailed.", "weaknesses": "1) There are too many descriptions of related work in the introduction, making it difficult for readers to find the gist.\n\n2) The analysis of method strengths is not clear enough. Why the proposed method is better than previous methods? Why tracking the model updates instead of the gradients can save twice the communication overhead? Can differences in the data distribution of all agents be mitigated by communicating with neighboring agents?\n\n3) References to employed benchmarks (CIFAR-10, CIFAR-100, Fashion MNIST, and Imagenette) and models (VGG-11, ResNet-20, LeNet-5 and, MobileNet-V2) are missed.\n\n4) The evaluated benchmarks are relatively small. More large-scale benchmarks should be supplemented, such as ImageNet.\n\n5) Some larger and state-of-the-art models should be evaluated to verify the effectiveness of the proposed method, such as ResNet-50, ResNet-100, ViT.\n\n6) The evaluations on Fashion MNIST, CIFAR-100, Imagenette employ different model. The models should be unified. \n\n7) Since one of the main contributions of the method is to reduce overhead, the article lacks a quantitative analysis of overhead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback. We answer each of the questions raised in the weakness section here.\n1. We will update the literature review to only include decentralized learning works on heterogeneous data.\n2.  The difference in data distribution across agents results in a huge variation in the local gradients and hence results in poor performance of decentralized learning. These differences can not be completely mitigated by communicating with neighboring agents. However, we can reduce this variance in local gradients through mechanisms such as gradient tracking. In these techniques, the key idea is to track the global/averaged gradient through a tracking variable. The tracking variable will have less variance across agents than the local gradient and is closer to the global gradient. But tracking mechanisms have a communication overhead of 2x as they communicate the tracking variable along with the model parameters to/from the neighbors at every iteration. Note that model parameters from neighbors are required for the gossip averaging step and tracking variables of the neighbors for updating the current agent’s tracking variable (bias correction). The goal of this work is to design an algorithm similar to gradient tracking but without communication overhead. To achieve this, every agent i communicates model updates i.e., $x_j^{t}-x_j^{t-1}$ which is the same as the tracking variable. Now, agent $i$ can recover the neighbor’s model parameters $x_j^t$ from the model updates by adding them to the local copy of $x_j^{t-1}$. The recovered neighbors’ parameters can then be used for the gossip averaging step. As for the tracking part, the model updates $x_i^{t}-x_i^{t-1}$ include two components -- (a) the gradient update $g_i^t$ and (b) the gossip update  $\\sum\\limits_{j \\in N(i)}w_{ij} * (x_j^t -x_i^t)$. \nIdeally, we would like $g_i^t$ to be the average gradient i.e., $\\frac{1}{n}\\sum\\limits_jg_j^t$ and $\\sum\\limits_{j \\in N(i)}w_{ij} * (x_j^t -x_i^t)$ to be $\\frac{1}{n}\\sum\\limits_n(x_j^t -x_i^t)$ -- as if the graph is fully connected. This implies that tracking the model updates not only inherently tracks the global gradient but also tracks the ideal gossip update. Hence the proposed GUT performs better than the previous methods at no additional communication overhead. Note that $n$ is the total number of agents and $\\mathcal{N}(i)$ is the neighbors of agent $i$. We hope we clarified the contributions of the proposed methods and would be happy to provide more details if needed.\n3. The reference for all the benchmark datasets and models are presented in Appendix C. We will add them to the main paper as well.\n4. We provide the results on the ImageNet dataset trained on ResNet-18 architecture over 16 agents ring topology with alpha = 1 and 0.1 in below Table 1. We use an initial learning rate of 0.1 and decay it by a factor of 10 at epochs 15 and 37. The stopping criterion is set to 50 epochs.\n\nTable 1: Average test accuracy of decentralized algorithms evaluated on ImageNet with ResNet-18 over 16 agents ring.\n|Method|Test ACC ($\\alpha=1$)| Test Acc ($\\alpha=0.1$)|\n|-------------|-------------|-------------|\n|DSGD|$53.15$|$45.09$|\n|*GUT* (ours)|$53.57$|$46.33$|\n|QG-DSGDm|$60.85$|$57.17$|\n|*QG-GUTm* (ours)|$60.88$|$57.85$|\n\n5.  Our current computational power cannot handle large ViT models. However, we do present experiments on Mobilenet-V2 which is more suitable for the edge applications.\n6. Table 3 of the main paper uses the standard models that are usually employed for the respective datasets. We provide the results on ResNet-20 for all the datasets in the below table 2 \n\nTable 2: Test accuracy of decentralized algorithms evaluated on ResNet-20 over 16 agents ring.\n|Method|Fashion MNIST|Fashion MNIST| CIFAR-100| CIFAR-100| Imagenette|Imagenette|\n|-------------|-------------|-------------|-------------|-------------|-------------|-------------|\n| | $\\alpha=0.1$ | $\\alpha=0.01$ | $\\alpha=0.1$ | $\\alpha=0.01$ | $\\alpha=0.1$ | $\\alpha=0.01$|\n |DSGDm  | $87.89 \\pm 2.34$ | $79.41 \\pm 3.29$| $47.93 \\pm 1.69$ | $42.57 \\pm 2.71$| $66.89 \\pm 3.12$ | $47.87 \\pm 4.03$|\n |QG-DSGDm  | $92.21 \\pm 0.01$ | $90.59 \\pm 0.92$ | $ 53.19 \\pm 1.68 $ | $ 44.17 \\pm 3.64 $ | $73.93 \\pm  2.01$ | $56.30 \\pm  5.43$|\n| *QG-GUTm* (ours) | $\\mathbf{92.55} \\pm 0.16$| $\\mathbf{91.70} \\pm 0.36$ | $ \\mathbf{53.40} \\pm 1.23 $ | $ \\mathbf{50.45} \\pm 1.30 $ | $\\mathbf{75.44} \\pm 2.22$ | $ \\mathbf{57.47} \\pm 5.33$|\n\n7. We provide the quantitative results on communication cost and memory requirements of training for all the experiments in **Table R3** in the attached rebuttal pdf. We also provide the compute and memory overheads in **Table R4** in the attached rebuttal pdf. In Table R4, memory overhead is reported as the fraction of additional memory required per agent during training with a batch size of 32 per agent, and the computational overhead is reported as the fraction of additional FLOPs required per sample per agent during training.\n\n$\\text{Memory overhead} = \\frac{\\text{Additional memory due to GUT}} {\\text{Total memory}}$\n\n$\\text{Compute overhead} = \\frac{\\text{Additional compute due to GUT}} {\\text{Total compute}}$\n\nWe have answered all the questions raised by the reviewer and would be happy to answer any further questions.\n\n"}, {"review_id": "ZCwiIf480j", "reviewer": "Reviewer_b7eV", "summary": "This work proposes a novel decentralized learning algorithm based on gradient tracking mechanism, called Global Update Tracking (GUT), which aims to mitigate the impact of heterogeneous data distribution. The proposed GUT algorithm overcomes the bottleneck of communication overhead by allowing agents to store a copy of their neighbors’ model parameters and then tracking the model updates instead of the gradients. Numerous experiments have proven that the proposed Global Update Tracking with Quasi-Global momentum (QG-GUTm) outperforms the current state-of-the-art decentralized learning algorithm on a spectrum of heterogeneous data.", "questions": "Please refer to the weaknesses section.", "limitations": "This paper does not have any specific societal impact, other than the ones associated with other algorithms.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tThis paper proposes a powerful global update tracking method and achieves good performance on multiple benchmarks.\n2.\tThe authors provide a detailed sensitivity study of the method's performance with respect to model architecture and hyper-parameters.\n3.\tThe paper is well written and easy for the reader to read and understand.\n", "weaknesses": "1.\tIn the experimental part, the quantitative experiments about communication parameters(cost) are not clear enough. Can the authors provide specific quantitative results for comparison so that readers can easily understand them?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their time and feedback.\nThe following Table 1 provides the communication cost for the experiments on 16 agents ring topology measured in terms of the total amount of data transferred in GB during training per agent. The communication costs for the remaining experiments are presented in **Table R3** of the rebuttal pdf. \n\nTable 1: Communication cost per agent for training various datasets on different model architectures over 16 agents ring topology.\n | Dataset   | Model |  Method| Communication Cost (GB) |\n| ------------------ | ----------------- | ------------ |  :--------: |  \n|CIFAR-10 | ResNet-20   |Gradient Tracking| 83.66|\n|CIFAR-10 | ResNet-20  |QG-DSGDm| 41.83|\n|CIFAR-10 | ResNet-20  |QG-GUTm| 41.83|\n|CIFAR-100 | ResNet-20  |Gradient Tracking| 85.46|\n|CIFAR-100 | ResNet-20  |QG-DSGDm| 42.73|\n|CIFAR-100 | ResNet-20  |QG-GUTm| 42.73|\n|Fashion MNIST | LeNet-5  |Gradient Tracking| 11.42|\n|Fashion MNIST | LeNet-5  |QG-DSGDm| 5.71|\n|Fashion MNIST | LeNet-5  |QG-GUTm| 5.71|\n|ImageNette | MobileNet-V2 |Gradient Tracking| 68.86|\n|ImageNette | MobileNet-V2  |QG-DSGDm| 34.43|\n|ImageNette | MobileNet-V2  |QG-GUTm| 34.43|\n\nThe communication cost for the proposed GUT or QG-GUTm algorithm is the same as DSGD or QG-DSGDm methods i.e., the proposed methods have no additional communication overhead. \n\nWe have answered all the questions raised by the reviewer and would be happy to answer any further questions."}]

Author rebuttal:
We present the additional results and the quantitative results on the overheads in the attached pdf. 

We reiterate the contributions of the proposed methodology. 

Decentralized machine learning on heterogeneous data has poor performance due to huge variations in the local gradients across the agents. Methods such as gradient tracking reduce this variation by tracking the global/averaged gradient at the cost of $2\times$ communication. The goal of this work is to employ tracking mechanisms without any communication overhead. To achieve this, we propose to track and communicate model updates at the cost of an additional memory buffer of model size. Tracking model updates inherently tracks global gradients. 
We recover the model parameters of the neighbors from the received model updates by maintaining a local copy of the neighbors' model parameters.

1. How does *GUT* recovers neighbors' model parameters by communicating model updates?
   * Let's consider $n$-agents ring topology with adjacency matrix W. Say agent $i$ has neighbors $j,k$. In DSGD algorithm, agent $i$ receives $w_{ij}x_j^t, w_{ik}x_k^t$ from its neighbors $j,k$ respectively and uses them for the gossip averaging step i.e., $w_{ii}x_i^t+w_{ij}x_j^t+w_{ik}x_k^t$. However, in the proposed *GUT* method, agent $i$ receives $w_{ij}(x_j^t-x_j^{t-1}), w_{ik}(x_k^t-x_k^{t-1})$ from its neighbors $j,k$ respectively instead of model parameters. We recover model parameters using the variable $s_i^{t-1}$ which keeps track of the averaged model parameters of the neighbors i.e., $s_i^{t}=s_i^{t-1}+w_{ii}(x_i^t-x_i^{t-1})+w_{ij}(x_j^t-x_j^{t-1})+w_{ik}(x_k^t-x_k^{t-1})$. Note that $s_i^0=x_i^0=x_j^0=x_k^0$ as all the models are initialized to the same values at the beginning of training and $w_{ii}+w_{ij}+w_{ik}=1$ as W is doubly stochastic. By unrolling the recursion, we get $s_i^t=w_{ii}x_i^t+w_{ij}x_j^t+w_{ik}x_k^t$.
2. How does the proposed tracking mechanism work? Why does it not require additional communication?
   * Ideally we would want $g_i^t = \frac{1}{n}\sum\limits_{j=1}^n g_j^t$ = global gradient or the gossip averaging step to be $ \frac{1}{n}\sum\limits_{j=1}^n x_j^t$ as if the graph is fully connected. However, the decentralized graph structures are sparse and agents only have access to their neighbors' model parameters/gradients. The gradient tracking mechanism introduces a variable $y_i^t$ which tracks the global gradient by correcting the local gradient computation i.e., $y_i^t = g_i^t + (\sum\limits_{j \in \mathcal{N}(i)}w_{ij}y_j^{t-1} -g_j^{t-1})$. The gradient tracking algorithm uses $y_i$ for the local SGD step rather than $g_i$. Since the gradient tracking algorithm requires $y_j$'s for tracking variable update and $x_j$'s for the gossip averaging, it incurs $2 \times$ communication. In contrast, the proposed GUT algorithm takes advantage of the fact that we can recover $x_j$'s from $y_j$'s if we track model updates i.e., $x_i^t-x_i^{t-1}$ instead of gradients and hence have only $1 \times$ communication. In any decentralized algorithm, the local model is updated with two components at every iteration -- (a) local gradient and (b) gossip averaging. For example, DSGD update: $x_i^t = x_i^{t-1} - \eta g_i^t + \sum\limits_{j \in \mathcal{N}(i)}w_{ij}(x_j^{t-1}-x_i^{t-1})$. Therefore tracking the model updates inherently tracks global gradients similar to gradient tracking algorithm. However, the model updates do have a gossip error term i.e., $\sum\limits_{j \in \mathcal{N}(i)}w_{ij}(x_j^{t-1}-x_i^{t-1})$ as residual. We apply reference correction so that the gossip part of the model update tracks the global gossip i.e.,  $ \frac{1}{n}\sum\limits_{j=1}^n (x_j^{t-1}-x_i^{t-1})$. Therefore, the proposed algorithm successfully tracks global gradients and residual global gossip by tracking model updates without any communication overhead.

We present the memory requirements and communication parameters in Table. 1.

Table 1: The parameters that are communicated and variables that need storage by various decentralized learning algorithms.
|Method| Communicate| Storage|
|----------|:-------------------:|:--------------:|
|DSGD| $x_i$| $x_i, a_i, g_i$|
|Gradient Tracking| $x_i, y_i$ | $x_i, a_i, g_i, y_i$|
|*GUT* (ours)| $y_i$ | $x_i, a_i, g_i, y_i, s_i$|

Where $x_i$ = model parameters at agent $i$, 

$a_i$ = activations at agent $i$, 

$g_i$ = gradients at agent $i$, 

$y_i$ = tracking variable at agent $i$ (which is model updates for GUT), 

$s_i$ = $\sum\limits_{j \in \mathcal{N}(i)}w_{ij}x_j$ i.e., copy of the averaged model parameters of the neighborhood

Note that size($x_i$) = size($y_i$) = size($s_i$).       $\mathcal{N}(i)$ = neighbors of agent $i$.

We hope this clarifies the contributions and limitations of the proposed *GUT* method. 


Meta-review: This paper's limited discussion with the authors might be attributed to the relatively low confidence scores. However, it's important to acknowledge the novelty of the proposed mechanism compared to the (standard) gradient tracking baseline, and the intriguing nature of the idea of a "global update tracking". The application of the tracking mechanism to parameters, along with the use of buffers, effectively reduces overhead while potentially eliminating the necessity for 'global' shared updates, as the method relies on local neighbor state estimates. While an analysis in the smooth and strongly convex setting could further help to understand the approach's limitations, the experiments present strong evidence. I thus recommend accepting this paper.
Decision: Accept (poster)