Neighborhood Gradient Mean: An Efficient Decentralized Learning Method for Non-IID Data
Authors: Sai Aparna Aketi
Sangamesh Kodge
Kaushik Roy
Venue: Accepted by TMLR ()

Abstract: Decentralized learning algorithms enable the training of deep learning models over large distributed datasets, without the need for a central server. The current state-of-the-art decentralized algorithms mostly assume the data distributions to be Independent and Identically Distributed (IID). In practical scenarios, the distributed datasets can have significantly different data distributions across the agents. This paper focuses on improving decentralized learning on non-IID data with minimal compute and memory overheads. We propose Neighborhood Gradient Mean (NGM), a novel decentralized learning algorithm that modifies the local gradients of each agent using self- and cross-gradient information.  In particular, the proposed method averages the local gradients with model-variant or data-variant cross-gradients based on the communication budget. Model-variant cross-gradients are derivatives of the received neighbors’ model parameters with respect to the local dataset. Data-variant cross-gradient derivatives of the local model with respect to its neighbors’ datasets. The data-variant cross-gradients are aggregated through an additional communication round. We theoretically analyze the convergence characteristics of NGM and demonstrate its efficiency on non-IID data sampled from various vision and language datasets. Our experiments demonstrate that the proposed method either remains competitive or outperforms (by 0-6%) the existing state-of-the-art (SoTA) decentralized learning algorithm on non-IID data with significantly less compute and memory requirements. Further, we show that the model-variant cross-gradient information available locally at each agent can improve the performance on non-IID data by 3-20% without additional communication costs.

Published in Transactions on Machine Learning Research (11/2023)
Neighborhood Gradient Mean: An Efficient Decentralized Learning Method for Non-IID Data
Sai Aparna Aketi"
saketi@purdue.de edu
Deportment of Electrical and Computer Engineering
Purdue Universily
Sangamesh Kodge
skodge&ppurding edu
Department Electrical and Computer Engineering Purdue University
Kaushik Roy
kaushikkBuurduc edu
Department of Electrical and Computer Engineering
Purdue University
Reviewed on OpenReview: https: /ppe:////peeeeveeee net/ forum? uktK225G3e
Abstract
Decentralized learning algorithms enable the training of deep learning models large distributed datasets, without the need for central server. The current state-of-the-art de- centralized algorithms mostly assume the data distributions to be Independent and Identi- cally Distributed (IID). In practical scenarios, the distributed datasets can have significantly different data distributions across the agents. This paper focuses on improving decentral- ized learning on non-IID data with minimal compute and memory overheads. We propose Neighborhood Gradient Mean (NGM), novel decentralized learning algorithm that modifies the local gradients of each agent using self- and cross-gradient information. In particular, the proposed method averages the local gradicnts with model-variant data-variant cross- gradients based on the communication budget. Model-variant cross-gradients are derivatives of the received neighbors' model parameters with respect to the local dataset. Data-variant cross-gradient derivatives of the local model with respect to its neighbors' datasets. The data-variant cross-gradients are aggregated through an additional communication round. We theoretically analyze the convergence characteristics of NGM and demonstrate its ef- ficieney on non-lID data sampled from various vision and language datasets. Our exper- iments demonstrate that the proposed method either remains competitive outperforms (by 0 6%) the existing state-of-the-art (SoTA) decentralized learning algorithm non-III) data with significantly less compute and memory requirements. Further, we show that the model-variant cross-gradient information available locally at each agent can improve the performance on non-IID data by 2 - 20% without additional communication cost.
1 Introduction
The remarkable success of deep learning mainly attributed the availability of humongous amounts of data and computing power. Large amounts of data are generated on daily basis at different devices all over the world which could be used to train powerful deep learning models. Collecting such data for centralized processing is not practical because of communication and privacy constraints. To address this concern, a new interest in developing distributed learning algorithms (Agarwal & Duchi 2011) has emerged. Federated learning (centralized learning) (Knneny et al. 2016) is a popular setting in the distributed machine learning
These authors contributed equally to this work

---

Published in Transactions on Machine Learning Research (11/2023)
paradigm, where the training data is kept locally at the edge devices and a global shared model is learned by aggregating the locally computed updates through a coordinating central server. Such a setup requires continuous communication with a central server which becomes potential bottleneck (Haghighat et al. 2020 This has motivated the advancements in decentralized machine learning.
Decentralized machine learning branch of distributed learning that focuses on learning from data dis- tributed across multiple agents/devices Unlike Federated learning, these algorithms assumee that the agents are connected peer to peer without a central server. It has been demonstrated that decentralized learning al- gorithms (Lian et al. 2017 can perform comparably to centralized algorithms on benchmark vision datasets. Lian et al. (2017) present Decentralised Parallel Stochastic Gradient Descent (D-PSGD) by combining SGD with gossip averaging algorithm (Xiao & Boyd 2004). Further, the authors analytically show that the conver- gence rate of D-PSGD is similar to its centralized counterpart (Dean et al. 2012 Decentralized Momentum Stochastic Gradient Descent (DMSGD) which introduces momentum to D D-PSGD was proposed and analyzed in Balu et al. (2021). Assran al. (2019) introduce Stochastic Gradient Push (SGP) which extends D-PSGD to directed and Lime-varying graphs. (Tang et al. (2019); Koloskova el. al. 2019 explore error-comppensated compression techniques (Deep-Squeeze and CHOCO-SGD) to reduce the communication cost of D D-PSGD significantly while achieving the same convergence rate as centralized algorithms. Aketi et al.
2021 com-
bined Seee-Squeeze with SGP to propose communication-efinn
decentralized learning over time- vareviayyig
and directed graphs. [u & De Sa (2020): Liu et al. (2020b): Zhao et al. (2022); | Takezawa et al.
2023 g also
explore communication compression in decentralized setups. Recently, Koloskova et al. (2020) proposed a
unified framework for the analysis of gossip-basee based decentralized SGD methods and provide the best-known
convergence guarantees.
The key assumption to achieve state-of-the-ar performance by all the above-mentioned decentralized algo- rithms is that the data is independent and identically distributed (IID) across the agents. In particular, the data is assumed to be distributed in a uniform and random manner across the agents. This assumption does not hold in most of the real-world applications as the data distributions across the agents are significantly different (non-IID) based on the user pool (Hsieh el al., 2020). The effect of non-IID data in a peer-to-peer decentralized setup is a relatively under-studied problem. There are only a few works that try to bridge the performance gap between IID and non-IID data for decentralized sctup. Note that, mainly focus on
common type of non-IID data, widely used in prior works (Tang et al.] 2018 Lin et al. 2021 Esfandiari et al. 2021 ) a skewed distribution of data. labels across agents. 'Tang et al. 2018)) proposed D algorithm
that extends D-PSGD to non-lll) data. However, the algorithm was demonstrated on only a basic LeNet5
[LcCnn et al.] 1998) model and is not scalable to deeper models with normalization layers. SwarmSGD proposed by Nadiradze el al. (2019) leverages random interactions between participating agents in a graph to achieve consensus. [in et al. (2021) | replace local momentum with Quasi-Global Momentum (QGM) and improve the test performance by 20%. However, the improvement in accuracy is only 1 2% in case of highly skewed data distribution as shown in Aketi et al. (0022). Tracking mechanisms such as Gradient Tracking (Di Lorenzo & Scutari 2016 Pu & Nedić 2001 Koloskova et al.) 2021 and Momentum Tracking Takezawa et al., (022) have been proposed to tackle nOn-III data in decentralized settings at the cost of 2x communication overhead. Most recently, Esfandiari et al. [2021] proposed Gross-Gradien Aggregation (CGA) and a compressed version of CGA (CompCGA), claiming state-of performance for decen- tralized learning algorithms over completely non-IID data. CGA aggregates cross-gradient information, i.c., derivatives of its model with respect. to its neighbors' datasets through an additional communication round. It then updates the model using projected gradients based on quadratic programming. CGA and CompCGA require very slow quadratic programming step (Goldfarb & Idnani 1983) after every iteration for gradient projection which is both compute and memory intensive. This work focuses on the following question: Can we improve the performance of decentralized learning on non-IID data with minimal compule and memory overhead?
In this paper, we propose Neighborhood Gradient Mean (NGM) algorithm with two variants to handle non-IID data in peer-to-peer decentralized learning setups. Firstly, we classify the gradients at each agent into three types, namely self-gradients, model-variant cross-gradients, and data-variant cross-gradients (sce Section 3). The self-gradients (or local gradients) are the derivatives computed al each agent on its model parameters with respect to the local dataset. The model-variant cross- coss-ggaddents are the derivatives of the
2

---

Published in Transactions on Machine Learning Research (11/2023)
received neighbors' model parameters with respect to the local dataset. These gradients computed locally at each agent after receiving the neighbors' model parameters. Communicating the neighbors' model parameters is a necessary step in any gossip-based decentralized algorithm (Lian et al. 2017]. The data- variant rross-gradients are the derivatives of the local model with respect to its neighbors' datascts. These gradients are obtained through an additional round of communication, We then cluster the gradients into a) model-variant cluster with self-gradients and model-variant gross-gradients, and b) data-variant cluster with self-gradients and data-variant cross-grasd poiss-gradietss. Finally, the local gradients are replaced with the model- variant chuster means in NGMm where the communication budget is 1x, and with the data-variant cluster means in NGMay where the communication budget is 2x. The main motivation behind this modification is to account for the high variation in the computed local gradients (and in turn the model parameters) across the neighbors due to the non-III nature of the data distribution.
The proposed NGM& has two rounds of communication at every iteration to send model parameters and data-variant cross- gusssgraddents. This incurs 2x communication cost compared traditional decentralized al- gorithms (D-PSGD). To reduce this communication overhead, show that NGMds can be combined with error feedback- compression methods to compress the additional round of cross-gradient communica- tion. Note that NGMme has no communication overhead. We provide detailed convergence analysis of the proposed NGMds algorithm and show that the analysis can be trivially extended to NGMm.. We validate the performance of the proposed algorithm on various datasets, model architectures, and graph topologies. We compare the proposed algorithm with several baselines such as D-PSGD (Lian et al. 2017), QG-DSGDm (Lin al. 2021), Momentum Tracking (Takezawa et al., 2022), and CGA (Esfandiari al., 2021). Our experiments show that NGM can achieve superior performance state-of-the-art approaches. We also report the order of communication, memory, and compute overheads required for various decentralized algorithms as compared to D-PSGD.
non-III data compared to the current
Contributions: In summary, we make the following contributions.
We propose the Neighborhood Gradient Mean (NGM) algorithm with two variations for decentral- ized learning on non-IID) data. NGMm utilizes self-gradients and model-variant cross-gradients to improve the performance on non-lID data. NGM improves this performance further by utilizing self-gradients and data-variant cross-gradients the cost of 2x communication overhead.
We theoretically show that the convergence rate of NGM is O ((7RR) ), which is consistent with the state-of-the-art decentralized learning algorithms.
NGMmy outperforms the QG-DSGDm baseline by 2 20% without any communication overhead.
NGMa, either remains competitive or outperforms by 0 - 6% with significantly less compute and memory requirements compared to the current state-of-the-art at iso-communication.
2 Background
In this section, we provide the background on decentralized learning algorithms with peer-to-peer connec- tions.
The main goal of decentralized machine learning is to learn global model using the knowledge extracted from the locally generated and stored data samples across N edge devices/agents while maintaining pri- vacy constraints. In particular, we solve the optimization problem of minimizing global loss function F(x) distributed across agents as given in equation. 1
min F(x) Σ f(z))
ZERR
(1)
and f((x) = ExED [((x; Vi
This typically achieved by combining stochastic gradient descent (Bottou 2010) with global consensus-
based gossip averaging (Xiao & Boyd 2004). The communication topology in this setup is modeled
3

---

The overview of Published in Transactions on Machine Learning Research (11/2023)
graph G= [[)], with edges {i.s} E if and only if agents i and j are connected by communication link exchanging the messages directly. We represent Ni as the neighbors of i including itself. It is assumed that the graph G is strongly connected with self-loops i.e, there is a path from every agent to every other agent. The adjacency matrix of the graph G is referred to as a mixing matrix W where Wij is the weight associated with the edge {i. Note that, weight indicates the absence of a direct edge between the agents. We assume that the mixing matrix doubly-stochastic and symmetric, similar to all previous works in decentralized learning. For example, in a undirected ring topology, Wij - if E (i-1, (i-1,i,i+1) 1J. Further, the initial models and all the hyperparameters are synchronized at the beginning of the training. Algorithm. 2 in the
appendix describes the flow of D-PSGD with momentum. The convergence of the Algorithm. 2 assumes the data distribution across the agents to be Independent and Identically Distributed (IID).
3 Neighborhood Gradient Mean
We propose the Neighborhood Gradient Mean (NGM) algorithm and a compressed version of NGM which improve the performance of decentralized learning on non-IID data. We define the concepts of self-gradients and cross- goos-ggaaseenss below.
Geaf-Gradient: For agent with the local dataset D' and model parameters x', the self-gradient is the gradient of the loss function fi with respect to the model parameters x', evaluated on mini-batch d' sampled from dataset D
g" d=F
(2)
For an agent with model parameters æ² connected to neighbor j that has local dataset Dd, the cross-gradient is the gradient of the loss function fy with respect to the model parameters x², evaluated on mini-batch dl sampled from dataset DJ
Cross- Gradient:::
= VoF(((d))
(3)
At each agent i, we further divide the cross-gradients into two calegories. 1) Model-varianl cross-grudienls: The derivatives that are computed locally using its local data on the neighbors' model parameters (g²)). 2) pross-gradients: The derivatives (received through communication) of its model parameters on the neighbors' dataset (g"). Note that an agent computes the gross-gradients gd that act as model-variant variant cross-gradients for i and data-variant cross-gradients for j. In particular, the data-variant cross-gradient of i i.e,, g" is computed by agent j using its local data dj after receiving the model parameters x² from and is then communicated to agent i if needed.
3.1 The NGM algorithm
The pseudo-code of the Neighborhood Gradient Mean (NGM) is shown in Algorithm. the algorithm is illustrated in Figure. 5 of Appendix A.3
The main contribution of the proposed NGM algorithm is the local gradient manipulation step (line 12 in Algorithm. D. We first introduce a syper-parameter a called NGM miring weight which is either set to or 1. In the tthh iteration of NGM, each agent calculates its self-gradient g² Then, agent i's model parameters are transmitted are calculated by the neighbors. These cross- cross-gradiee gradients communication round if a is set to 1. At every iteration after the first communication round, each agent has access to self-gradients (g*) and model-variant rross-gradicnts. When is set to 1, the agents get access to data-variant cross-gradients through a second round of communication. Now, we group these cross-gradients into two clusters: a) Model-variant cluster {g"Vj e Ni that includes self-graddents and model-variant cross-gradients, and b) Data-variant cluster (gD E N,} that includes self coff-gradients and data-variant cross- gradissradssss. The local gradients at each agent are replaced with either of the clusters' mean based value shown in Equation. 4 which assumes uniform mixing matrix (wy 1/m; (Wl))-
all other agents (j) in its neighborhood, and the respective cross-gradients
transmitted back to agent i through an additional
4

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm Neighborhood Gradient Mean (NGM)
Each agent i E [1, N] initializes model weights z(o)= step size v, momentum coeflicient 8, averaging rate ", mixing matrix W = (wcgls.eeu. NGM mixing weight a {0,1); and lū are elements of N x identity matrix, Mf represents neighbors of including itself.
Input:
Each agent simultaneously implements the TRAIN() procedure
1. procedure TRAIN() )
2.
for k-0, 1, 1,.., K - do
3.
D' 9t = [V..((
4.
5.
SENDRECEIVE(TL]
6.
for each neighbor j E (N₂ i) do
7.
12 vafi(d
8.
if 0: SENDRECEIVE(S""
11.
end
12.
93 EjEr:(11 a)w + awijgk
13.
o = Bo(R-1) 199
14.
I ot +uk
I
15.
I (k+1) Th +7 EiEN 15))
16.
end
17.
return
When is set to zero, the proposed algorithm modifies the local gradient with model-variant cluster mean and this is referred to as NGMm.. This version of the algorithm does not incur any communication overhead The a = version of the algorithm replaces local gradient with data-variant cluster mean and is referred to as NGM Setting a to any non-zero value requires an additional round of communication and we experimentally determine that gives the best results (refer section. for more details).
1 m JEN,
Σ oh
gh = (1 a)
gh
a
m JEN,
(4)
(a) Model-variant cluster mean
(b) Data-variant cluster mean
The motivation for this modification is to reduce the variation of the computed local gradients across the agents. In IID settings, the local gradients should statistically resemble the cross-gradients and honce simple gossip averaging is sufficient to reach convergence. However, the non-lID case, the local gradients across the agents are significantly different due the variation in datasets and hence the model parameters on which the gradients computed. The proposed algorithm reduces this variation in the local gradients it is equivalent to adding the bias term for NGM and the bias term for NGM as shown in Equation.
=
+ +(1 a:)
Σ JEN;
Co 9
-
Σ JEN.
9
model variance hias ej
data variance bias w
1 Σ V (VF(dd::()) v.F(d(iz() x
(5)
m
JEN;
W
(v.F(d); v=F(d(:)))
JEN,

---

Published in Transactions on Machine Learning Research (11/2023)
The bias term compensates for the difference in neighborhood's self-gradients caused due to variation in the model parameters across the neighbors. Whereas, the bias term w compensates for the difference in a neighborhood's self-gradients caused due to variation in the data distribution across the neighbors. We hypothesize and show through our experiments that the addition of one of these bias terms to the local gradients improves the performance of decentralized learning on non-IID data by accelerating global convergence.
4 Convergence Analysis of NGM
In this section, provide convergence analysis for NGM We assume that the following statements hold:
Assumption 1 Lipschitz Gradients: Each function fi(z) is L-smooth.
Assumption 2 Boonnddd Variance: The variance of the stochastic gradients is assumed to be bounded.
E&-D, (V-D, (=(() S o² [1,N]
(6)
[V/((=) - VFF=)) <² [I,
Assumption 3 Doubly Stochastic Mixing Matrix: The mixing matrix W is real doubly stochastic matrix with (W)) = 1 and
maxx([>e())) (w))) S <
where (WW is the ht largest cigenvalue of W and is constant.
The above assumptions are commonly used in most decentralized learning setups.
Lemma Given assumptions 1-3, we define g' = VFi(r;;) and the NGM gradient update g.. For all i, we have:
N
8)
E
Σ gg'
S 4( N
+ +
A.1 This lemma bounds the difference between self-gradients and the proposed gradients terms inter- and matra-gradient variance bounds. The inter- gradient variation bounded by <² determines the heterogeneity the data distribution i.e., the non- Innes.. The intra-gradicnt variation bounded by o² determincs the stochastic noise across the mini-batches within an agent. Int untuviivll the distance between the self- self-gradients g and the NGMa, gradient update g' increases with increase in the degree of heterogeneity in data distribution which is expected. Note that the convergence bounded by a positive constant which rale for NGMm, remains the same as CGA where E [[] - gg) is of the order of +.
A complete proof for Lemma 1 can be found in Appendix.
Theorem presents the convergence of the proposed NGMa, algorithm and the proof is detailed in Ap- pendix A.2.2
Theorem 1. (Convergence of NGMás algorithm) Given assumptions 1-3 and lemma 1 the following conditions:
let step size satisfy
(1) S 4(1 vD)² +6+ 6(1
vP) - 2(1 vD)
6L
Ta
(2) 1
2 (v
1 Ln
-1)
For all K 2 1, we have
K-1
1 C₁K
0² + +
(02 +2) (1 vp)²
<
(10)
K
where 3
momentum coefficient, 3t
1 Σ 2

---

Published in Transactions on Machine Learning Research (11/2023)
C = 3 ) C2 = ( 1,72 (1- (1-p)3 /C1
20n 20 [1 (1-8)
1 and C3 = (1 (1)8) (1-8))
The result of the theorem. [ shows that the magnitude of the average gradient achieved by the consensus model upper-bounded by the difference between the initial objective function value and the optimal value, the sampling variance, and gradient variations across the agents representing data heterogeneity. A detailed explanation of the constraints on step size and momentum coefficient is presented in the Appendix. [.2.3]] Further, we present corollary to show the convergence rate of NGMd, in terms of the number of iterations.
) For a suficcienll Corollary Suppose that the slep size salisfies 1) = O 0(v K and that (² = 0 (1-W
large K 2 36NL2 and
r == ((1 vp)² + 6(1 - (1 - B)2 2(1 VD), we have, for some constand C>0 0,
K-1 (xx)))
sc (VVRR k)
Σ [VFF
K
VNK
The proof for Corollary. | can be found Appendix, A.2.4 Here, the constant C' depended on the spectral gap P; stochastic noise bound o² and the inter gradient variance bound c2. The bound on (² the result of the assumption that the graphs with higher connectivity (lower spectral gap) can tolerate more non- IIDness. Corollary. 1 indicaaes that the proposed algorithm achieves lincar speedup (with convergence rate of 0 ((NR)) when K is sufficiently large. This convergence rate is similar to the well-known best result. for decentralized SGD algorithms in the literature as shown in Table.
Table 1: Convergence rate comparison between decentralized learning algorithms.
Method
Rate
Assumption
Simplified Rate
D-PSGD
O
1-0²
Nº0²
N2C²
0
VNK
K(I-p) K(I vD)²
VNK
K
CGA
VNK
l-a2
N(62+02+02)
R(I
vpy²
+ VNN
1/K
+ VNN VR
2 = (
O
VNK
+ K + Rid + x
NGMa. (ours)
VNK
l-o"
K(I-vp)
N(
(²)
./V
2 0 (1-VPNN
O
VNK
+
R
5 Experiments
In this section, we analyze the performance of the proposed NGM and NGMar techniques and compare them with the corresponding baseline i.e., D-PSGD algorithm (Lian et al. 2017), QG-DSGDm (Lin et al. Momentum Tracking (akezaaw et al. 2022) and state-of-the-arr CGA method (Esfandiari et al.
2021
2021
5.1
Experimental Setup
The efficiency of the proposed method is demonstrated through our experiments on a diverse set of datasets, model architectures, tasks, topologies, and numbers of agents. We present the analysis
(a) Datasets
(Appendix A.5): vision datascts (CIFAR-10, CIFAR-100, Fashion MNIST and Imagenette (Husain 2018
and language datasets (AGNews (Zhang et al. ). (b) Model architectures (Appendix A.6 5-layer
CNN, VGG-11, ResNet-20, LeNet-5, MobileNet- V2, ResNet-18, BERTumn and DistilBERT, base (c) Tasks:
Image and Text Classification. (d) Topologics: Ring, Chain, and Torus. (c) Number of agents: varying from
to 20. Note that we use low-resolution (32 x 32) images of the Imagenette dataset for the experiments in
Table. The results for high resolution (224 224) Imagenette are presented in Table.
"Ou Torch code available at hhttps://githhin http://tww....eeppppeeeeeeeeeeea htwphrhhoodddrdeeteeeeeee claetteritutttttnnggcc

---

Published in Transactions on Machine Learning Research (11/2023)
We consider extreme case of non-IID distribution where no two neighboring agents have the same class. This is referred to complete label-wise skew or 100% label-wise non-IIDness (Hsich et al. 2020 Tn particular, for a 10-class dataset such as CIFAR-10 each agent in a 5-agent system has data from 2 distinct classes, and each agent in a 10-agent system has data from a unique class. For a 20-agent system, two agents that are maximally apart share the samples belonging a class. We report the lest accuracy of the consensus model averaged over three randomly chosen seeds. The details of the hyperparameters for all the experiments are present in Appendix. [A.10] We compare the proposed method with iso-communication baselines. The experiments NGM my compared with D-PSGD and QG-DSGDm, NGM with Momentum Tracking and CGA. The communication cost for each experiment in this section is presented in Appendix A.9
5.2 Results
Firstly, evaluate variants of NGM and compare them with respective baselines in Table. 2 for training different models trained on CIFAR-10 over various graph sizes and topologies. We observe that NGM consistently outperforms QG-DSGDm for all models and graph sizes over ring topology with significant performance gain varying from 2 20%. For the torus topology, NGMm. outperforms D-PSGD by 14 18% and QG-DSGDm fails to converge. Our experiments show the superiority of NGM over CGA. The performance gains are more pronounced when considering larger graphs (with agents) and compact models such ResNet-20. We observe that CGA and NGM perform better than Momentum Tracking in most cases. We further demonstrate the generalizability of the proposed method by evaluating it various image datasets (refer Table. 3) such Fashion MNIST, and Imagenette and challenging datasets such as CIFAR-100. Table. 3 show that NGM outperforms QG-DSGDm by - 18% across various datasets whereas NGMaa remain competitive with an average improvement of ~ 1%.
Table 2: Average test accuracy comparisons for CIFAR-10 with non-llD data using various architectures and graph topologics. The results averaged over three seeds where std is indicated.
5layer CNN
5layer CNN
VGG-11 Ring
ResNet-20 Ring
Method
Agents
Ring
Torus
5
76.00 + 1.44
67.04 + 5.36
82.13 = 0.84
D-PSGD
10
47.68 + 3.20
55.34 + 6.32
44.14 + 3.30
31.66 + 6.01
20
44.85 + 1.94
50.12 + 1.91
38.92 + 2.99
31.94 + 2.91
5
78.77 = 0.69
81.71 = 0.45
82.59 2.66
QG-DSGDm
10
47.83 + 3.39
14.48 + 0.50
57.77 + 0.33
46.09 7.90
20
46.57 + 4.80
17.25 5.81
32.32 + 7.61
44.78 3.39
5
82.20 + 0.34
83.65 + 0.38
85.88 0.58
NGMmv (ours)
10
67.43 + 1.15
73.84 + 0.33
59.92 2.12
66.02 2.86
20
58.80 + 1.30
64.55 + 1.16
52.704 1.63
50.74 2.36
5
80.34 + 0.67
79.62 + 7.42
85.65 = 0.30
Momentum Tracking
10
58.54 + 7.51
67.46 + 1.10
73.51 + 1.42
66.37 + 7.72
20
36.58 + 11.5
56.71 1.96
36.12 + 13.8
44.35 11.7
5
82.20 + 0.43
84.41 = 0.22
87.52 0.50
CGA
10
72.96 + 0.40
76.04 0.62
79.66 0.46
79.98 1.23
20
69.88 + 0.84
73.21 0.27
79.30 + 0.12
75.13 1.56
5
83.36 = 0.65
85.15 + 0.58
88.52 0.19
NGMas (ours)
10
75.34 = 0.30
78.53 + 0.56
79.55 + 0.30
84.02 + 0.44
20
73.36 + 0.88
75.11 + 0.07
79.43 + 0.62
81.26 + 0.69
To show the effectiveness of the proposed method across different modalities, we present. results on the text classification task in Table 4 We train on the BERT model with the AGNews dataset distributed over and agents and DistilBertsase distributed over agents. For NGM we see maximum improvement of 2.1% over the bascline D-PSGD algorithm. Even for the text classification task, we observe NGM be competitive with CGA. These observations consistent. with the results of the image classification
8

---

Published in Transactions on Machine Learning Research (11/2023)
Table 3: Average test accuracy comparisons for various datasets with non-lID sampling trained over undi- rected ring topology. The results averaged over three seeds where std is indicated.
Fashion MNIST
CIFAR-100
Imagenette (32x32)
Method
Agents
(LeNet-5)
(ResNet-20)
(MobileNett V2)
5
86.43 + 0.14
44.66 = 5.23
47.09 + 9.20
D-PSGD
10
75.49 + 0.32
19.03 = 13.27
32.81 + 2.18
5
89.28 + 0.52
49.60 = 3.30
43.70 + 2.80
QG-DSGDm
10
84.38 + 0.58
41.28 + 0.61
17.80 + 2.66
5
90.03 + 0.11
55.96 + 0.95
60.15 + 2.17
NGM (ours)
10
87.10 + 0.47
49.30 + 1.02
36.13 + 1.97
5
90.52 + 0.56
49.52 + 2.36
38.79 + 2.21
Momentum Tracking
10
87.82 + 0.19
37.74 + 4.74
23.07 + 11.3
5
90.03 = 0.39
56.43 = 2.39
72.82 = 1.25
CGA
10
87.61 + 0.30
53.61 + 1.07
61.97 + 0.58
5
90.61 + 0.18
56.50 + 3.23
74.49 + 0.93
NGMas (ours)
10
87.24 + 0.23
53.77 + 0.15
64.06 = 1.11
tasks. Finally, through this exhaustive set of experiments, we demonstrate that the NGM can serve as a simple plugin boost the performance of docentralized learning on non-IID data without significant memory and compute overheads. Further, NGMmm demonstrates that locally available model-variant cross-gradient information at each agent can be efficiently utilized to improve decentralized learning with no communication overhead.
Table 4: Average test accuracy comparisons for AGNows dataset (left side of the table) and full resolution (224 x 224) Imagenette dataset (right side of the table). The results are averaged over three seeds where std is indicated.
AG.swws- BERe-BERTTiii
Imagenette (24xx24))ResNoe
Method
Agents
Agents
Agents Ring Topology
Agents 5
Ring Topology
Ring Topology
Chain Topology
D-PSGD
89.21 +: 0.41
85.48 t 0.71
91.54 = 0.07
65.43 i 4.60
42,02 + 1.25
QG-DSGDm
87.38 + 5.29
76.61 3.63
93.55 = 0.23
74.22 + 2.30
43.35 + 4.57
NGMM (ours)
89.40 + 0.13
87.58 = 0.07
93.60 + 0.12
78.26 = 0.67
47.87 0.99
Momentum Tracking
82.45 + 6.19
87.82 = 0.047
93.87 = 0.15
81.11 + 0.29
22.12 : 2.93
CGA
91.43 + 0.11
89.15 = 0.45
93.42 = 0.04
85.00 + 0.67
65.96 1.84
NGMa. (ours)
92.24 + 0.29
89.02 + 0.39
94.11 + 0.01
85.85 = 0.60
67.77 + 1.76
ring
2.25
ring colleccddde
Validation Loss
1.4
fu conneccc
Validation Loss
2.00
Validation Loss
d-psgd
1.75
1.50
1.0
1.25
1.00
0.75
0.50
0
50
100
200 Epochs
150
250
300
50
100
150 Epochs
200
250
300
50
1.00
150
200
250
300
Epochs
(a) NGM on data
(b) NCM on Nou-IID data
(c) Non-lID, ring topology
Figure Average Validation loss of NGMmp during training CIFAR-10 on a 5-layer CNN with agents.

---

Published in Transactions on Machine Learning Research (11/2023)
2.25
ring conlecco
ring
ngm
2.00
Validation Loss
1.1
Validation Loss
conneccodd
Validation Loss
2.00
cga
1.0
1.75
1.75
1.50
0.9
1.25
1.25
0.7
1.00
1.00
0.6
0.75
0.5
0.50
0.50
60
120
180 Epochs
240
300
60
120
180
240
300
60
120
180
240
300
Epochs
Epochs
(a) NGMa ITD data
(b) NGM Non-ITD data
(c) Non-IID, ring topology
Figure 2: Average Validation loss of NGMdy during training CIFAR-10 5-layer CNN with 5 agents.
Model-Variance Bias
0.10
mgMmv
Modet-Variance Bias
ngmdv
Data-Variance Bias
0.040
ngm
0.08
cga
cga
0.035
0.014
0.06
0.030
0.012
0.04
0.025
0.010
0.02
0.020
0.008
0.00
150
300
160 Epochs
300
60
160
300
Epochs
Epochs
(a) Model variance blas of NGMms
(b) Model variance blas of NGM
(c) Data variance bias of NGMa
Figure 3: Ablation study: CIFAR-10 dataset trained on a 5-layer CNN over ring graph 5 agents.
5.3 Analysis
We empirically show the generalization characteristics terms of validation loss convergence for the proposed algorithm on ITD and Non-IID data in Figures. [(a] ((a) and Figures. [(b) 2(b] respectively. For Non-IID data, we observe that there is slight difference in convergence (as expected) with slower rate for sparser topology (ring graph) compared to denser counterpart (fully connected graph). Figure. [[c] 2 shows the comparison of the generalization characteristics of the NGM and NGM,, algorithm with the respective baselines. For the same decentralized sctup, We observe that NGM and NGMa, have lower validation loss
than D-PSGD and CGA respectively. Analysis for 10 agents is presented in Appendix A.7
Then we proceed to analyze the model variance and data variance bias terms when training with various docentralized methods. Figure. 3(a] that the model variance bias of NGM is much lower than of the D-PSGD baseline resulting in the better performance of NGM We then compare the model variance and data variance bias terms of NGMap with CGA as shown in Figure. 3(b) and 3(c) respectively. We observe that both the model variance and the data variance bias for NGM are significantly lower than CGA. This is because CGA gives more importance to self- salf-gradients as it updates in the descent direction that is close In contrast, NGM accounts for
to self-gradients and positively correlated to data-variant cross-gradient the biases directly and gives equal importance self-gradients and data-variant cross-gradients, thereby achieving superior performance. Further, Figure ((a) presents the average consensus error i.e., A| - -x l time for training CIFAR-10 dataset on 5-layer CNN with respect to various algorithms. This empirically shows that the proposed NGM algorithm reaches the consensus at the same rate as CGA.
Additionally, we show that NGM can be used in synergy with QGM [Li et al. 2021] to further improve the performance of decentralized learning on non-lID Data. Figure. [(b) shows the test accuracy on the CIFAR-10 datasct trained on ResNet-20 over ring topology. We obscrve that the QGM version of NGM performs better than NGM by 16 27%. Similarly, the QGM version of NGM performs 1.3 2.5% better than the local momentum version of NGMa-
10

---

Published in Transactions on Machine Learning Research (11/2023)
90
76
dg
QG DSGDm
Consensus Error
75
cga
Test Test Accuracy (%)
ngmh
74
nimm
70
73
0.2
72
60
Validation
71
nigmy (2x comm.)
ngm (2x comm.)
0.1
70
cga (2x comm.)
50
69
ngmav (1x comm.)
50
100
150 Epochs
200
250
300
40
10 nodes
20 nodes
0.00
0.75 NGC mixing weight
0.25
0.50
1.00
(a) Consensus Error with 5-layer CNN (b) Training ResNett-2 by combining
(c) Ablation study with 5-layer CNN over 5 agents
5 agents
NGM with Quasi Global Momentum
Figure 4: Training CIFAR-10 distributed in non-llD) fashion ring topology
5.4 Communication Compression
In this section, we discuss the impact of communication compression the proposed NGM algorithm. At every iteration, the NGMds algorithm involves two rounds of communication with the neighbors: 1) communicate the model parameters, and 2) communicate the cross-gradients. This communication overhead can be a bottleneck in a resource-constrainee environment. Hence, we explore a compressed version of NGM referred to as Comp.NGM using Error Feedback SGD (EF-SGD) (Karimireddy al., 2019) to compress the cross-gradients. CoMP compresses the crmpr-coeeensteed cross-gradients from 32 bits (floating point precision of arithmetic operations) to 1 bit by using scaled signed gradicnts. The pscudo-code for CompNGM is shown in Algorithm. 3 in the Appendix. Additional results and analysis on CompNGM are presented in the Appendix. A.4
Table 5: Test Accuracy of CompNGM, Accuracy drop compared NGM4 and communication reduction in Giga Bytes compared to NGMav for various datasets trained on ring topology.
Dataset
Model
Acc (%)
Ace. Drop (%)
agents
Comm. Drop (GB)
Acc (%)
Acc. Drop (%)
10 agents
Comm. Drop (GB)
Fashion MNIST
LoNet-6
90.48
0.19
0.13
16.71 (1.4x)
83.38
0.39
3.86
8.35 (1.94x)
CIFAR-10
ResNet-20
87.56 + 0.31
0.96
123.11 (1.1x)
78.50 = 0.98
5.52
61.75 (1.94)
CIFAR-100
ResNel-20
57.51
D.48
-1.01
100.49 (1.9x)
43.07 0.32
10.7
50.27 (1.94)
Imagenetse (32x32)
MobileNet-Ve V2
72.91
1.06
99.80 (1.9x)
61.91
49.98 (1.9x)
Table. 5 shows that CompNGM reduces the communication cost by 1.94x by trading off 0.1 - 1.57% test accuracy for 5 agents and 2 - 10% test accuracy for 10 agents. This shows that NGM can be combined with communication compression techniques to achieve a tradc-off between accuracy boost and communication overhead. Further, NGM can be combined with stronger compression methods such as EF21 (Richáárik) et al. 2021 to have a better trade-off between accuracy and communication cost.
5.5 Hardware Benefits
The proposed NGMa, algorithm superior terms of memory and compute efficiency (see Table. and Appendix. A.8 while having equal communication cost compared to CGA. NGM replaces the com- plicated quadratic projection step of CGA with simple weighted averaging step. Since NGM,, involves weighted averaging, additional buffer to store the cross-gradie goos-gradsents is not required. CGA stores all the cross- gradients in a matrix form for quadratic programming projection of the local gradient. Therefore, NGM has no memory overhead compared to the baseline D-PSGD algorithm, while CGA requires additional memory equivalent to the number of neighbors times model size. Moreover, the quadratic programming projection step (Goldfarb & Idnani 1983) in CGA is much more expensive compute and latency than the weighted averaging step of cross- gradients in NGM. Our evaluation clearly shows that NGM is superior to CGA in terms of test. accuracy, memory efficiency, compute efficiency, and latency.
11

---

Published in Transactions on Machine Learning Research (11/2023)
Table 6: Comparison of communication, memory, and compute overheads per mini-batch compared to D- PSGD. my: model size, ny: number of neighbors, b: floating point precision, Q: compute for Quadratic
Programming, B: compute for Backward Pass. Note that ((Q) >> O(nm))) (Nostrrov & Todd 1997)
Method
Comm.
Memory
Compute
QG-DSGDm
0
((ma)
O(n,m,))
NGM
0
On,m, + n; (n.m,,)
Momentum Tracking
(mams)
(2mg)
CGA
(n:ma)
(nem))
O +nBB)
NGM
(n:mg)
O n;
CompCGA
(n
OQ + n
CompNGM
(n.m,,
O On.m, + nz B)
6 Discussion and Limitations
As mentioned in Section. 3.1 the NGM mixing weight a is either set to 0 or 1 resulting in NGMms or NGMa respectively. This implies that NGMm utilizes model-variant cross-raddients whereas, NGM utilizes data- variant cross-gradients. However, the NGM variant of the algorithm has access to both model-variant and data-variant cross-gra gradders.sssss. So, we conduct an ablation study mixing these two cross gradients by varying NGM mixing weight a in the range of [0, 1]. Figure. [[c] depicts the change in average validation accuracy 1 performs best. Further, Figure. 3(b) shows that the model variant bias
with and we observe that reduces for NGMa, even though it does not explicitly utilize the model-variant gross-gradients. We hypothe- size that, in NGMdv, the use of nata-variant cross- gradients for local updates followed by gossip averaging of coossgradieetss reducing model variance. Hence, explicitly
model parameters inherently adds model-variant mixing the two sets of cross-gradients is not necessary. In summary, for 1x communication constraints i.c., when agents do not have access to data-variant cross-gradients, NGMmm effectively utilizes locally available model-variant cross gradients to improve the accuracy. On the contrary, when 2x communication is allowed (non-zero a),, the best performance is achieved by only utilizing the data-variant cross-gradients.
Table 7: Test Accuracy and Latency of ImageNet (non-IID) trained on ResNet- 18 over 10-agent Ring. Note, LM: Local Momentum, QGM: Quasi Global Momentum.
Trained for
D-PD
QG-DSGDm
NGMp..
NGM
NGMms
Momentum Tracking
CGA
NGM + LM
NGMa.
60 epochs
+LM
+ -GGM
-GGM
Accuracy (%)
25.02
45.19
42.66
49.22
51.00
43.65
49.12
54.31
Epoch Time (min)
7.6
7.9
18.6
18.8
19.1
10.7
406
21.5
22.2
NGMmp has one patential limitation compared to D-PSGD and QG-DSGDm i.e., compute overhead. NGM me has to compute model-variant cross- gooss-erasentss which requires every agent i to compute n, additional forward and backward passes. However, NGMa, is significantly better in terms of latency, compute, and memory requirements compared to CGA as it simplifies the complicated quadratic projection step. Running the CGA algorithm on larger datasets like ImageNet impractical due to the significant latency associated with the quadratic projection step. Table. reports the accuracy and latency of training ImageNet in a non-lID fashion over ring topology of 10 agents. We observe that CGA is 20x slower than NGM for the ImageNet dataset on ResNet-18. We estimate the training time for one simulation of CGA ImageNet (90 epochs with 10-agent ring topology) to be around 26 days on 4 Nvidia A100s (80 GB) with Intel(R) RR) Xcon(R) Gold 6338 CPU. Further, it has been shown in the literature (Koloskova el al. 2019 Tang el. al.) 2019)) that the communication compression with error feedback only affects the higher-order terms of the convergence rate. Hence, decentralized compression algorithms have linear speedup similar to D-PSGD. Following this, our future efforts go towards showing that CompNGM has a similar convergence rate NGM. We would also like to explore efficient. methods to compute cross- cross-gradients for NGM.
12

---

Published in Transactions on Machine Learning Research (11/2023)
7 Conclusion
Enabling decentralized training non-lID data is key for ML applications to efficiently leverage the hu- mongous amounts of gger-generated private data. In this paper, we propose the Neighborhood Gradient Meon (NGM) algorithm with two variants that improve decentralized learning on non-IID data. NGM improves the performance of decentralized learning utilizing model-variant cross-gradients without any com- munication overhead. NGMa. further increases these gains by operating on data-variant cross-gradients. Additionally, we present a compressed version of our algorithm (CompNGMM) reduce the communication overhead associated with data-variant cross-gradients of NGM We thcoretically analyze the convergence characteristic and empirically validate the performance of the proposed techniques over different model ar- chitectures, datasets, graph sizes, and topologies. Finally, we compare the proposed algorithms with the current state-of-the-art decentralized learning algorithm on non-llD data and show superior performance with significantly less compute and memory requirements sctting the now state-of-tho-art for decentralized learning on non-IID data.
Authors' Contributions:
Sai Aparna Aketi and Sangamesh Kodge, both worked on developing the algorithm. The experiments for Computer Vision tasks were designed by Sai Aparna Aketi and the experiments for Natural Language Processing tasks were designed by Sangamesh Kodge. The theory for the convergence analysis and consensus error bounds was developed by Sai Aparna Aketi and was verified by Sangamesh Kodge. All the authors contributed equally in writing and proofreading the paper.
Acknowledgments
This work was supported part by, the Center for Brain-inspired Computing (C-BRIC), the Center for the Co-Design of Cognitive Systems (COCOSYS), DARPA-sponsored JUMP center, the Semiconductor Research Corporation (SRC), the National Science Foundation, and DARPA ShELL.
References
Alckh Agarwal and John Duchi. Distributed delayed stochastic optimization. Advances in neural infor- malion processing systems, 24, 2011.
Sai Aparna Aketi, Amandeep Singh, and Jan Rabaey. Sparse-push: Communication-& energy-efficient de- centralized distributed learning over directed & time-varying graphs with non-iid datasets. arXie preprint arXiv:2102.0571: 2021.
Sai Aparna Aketi, Sangamesh Kodge, and Kaushik Roy. Low precision decentralized distributed training over iid and non-iid data. Neural Nelworks, 2022. ISSN 0893-6080. doi: https///to.oorr/1..000fj..ee 2022.08.032.
Mahmoud Assran, Nicolas Loizon, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp. 344-353. PMLR, 2019.
Aditya Balu, Zhanhong Jiang, Sin Yong Tan, Chinmay Hedge, Young M Lee, and Soumik Sarkar. Decen- tralized deep learning using commentum--cccleaatted consensus. In ICASSP 2021-2021 IEEE International Conference Acoustics, Speech and Signal Processing (TCASSP), pp- 0675-667. IEFE, 2021.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMP- STAT'2010, pp. 177 186. Springer, 2010.
Joffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthicu Devin, Mark Mao, Marc'aurclis Ranzato, Andrew Senior, Paul Tucker, Ke Yang, al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
13

---

Published in Transactions on Machine Learning Research (11/2023)
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional 2018.
transformers for language understanding. orXiv preprinl
Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2(2):120-136, 2016.
Yasaman Esfandiari, Sin Yong Tan, Zhanhong Jiang, Aditya Balu, Ethan Herron, Chinmay Hegde, and Soumik Sarkar. Cross-gran gross-gradient aggregation for decentralized learning from non-iid data. In International Conference on Machine Learning, pp. 3036 3046. PMLR, 2021.
Donald Goldfarb and Ashok Idnani. A mumerically stable dual method for solving strictly convex quadratic programs. Mathematical programming, 27(1):1-33, 1983.
Arya Ketabchi Haghighat, Varsha Ravichandra- Mouli, Pranamesh Chakraborty, Yasaman Esfandiari, Saeed Arabi, and Anuj Sharma. Applications of deep learning in intelligent transportation systems. Journal of Big Data Analylies in Transportation, 2(2):115 145, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on compuler vision and pallern recognilion, pp. 770-778, 2016.
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-IID data quagmire of de- centralized machine learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 4387 4398. PMLR, 13 18 Jul 2020.
Hamel Husain. Imagenette a subset of 10 casily classified classes from the imagenct dataset. 2018.
https:// http://tttttbbbog httggggiii.ommm.m.. hom//fstaiiimmagen
Sai Pranceth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252 3261. PMLR, 2019.
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXi::1907.0033 2019.
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 Machine Learning, pp. 5381-5393. PMLR, 2020.
Anastasiaa Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for docentralizod machine learning. Advances in Neural Information Processing Systems, 34:11422-11435, 2021.
Jakub Koneeny, H Brendan McMahan, Daniel Ramage, and Peter Richtarik. Federated optimization: Dis- tributed machine learning for on-device intelligence. arXie preprint arXin:1610.0255 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar (canadian institute for advanced research). toroottoo.ddu http://uwn....torntto.cce/ kriz/cifor.hhir html, 2014.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to docu- ment recognition. Proceedings of the IEEE, 86(11):2278-2) 2324, 1998.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Aduances in Neural Information Processing Systems, 30, 2017.
Tao Lin, Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Quasi-global momentum: Accelerat- ing decentralized deep learning on heterogencous data. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 6654-6665. PMLR, 18-24 Jul 2021.
14

---

Published in Transactions on Machine Learning Research (11/2023)
Hanxiao Liu, Andy Brock, Karen Simonyan, and Quoe Le. Evolving normallzaaton-acctittttn layers. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Newral Information Processing Systems, volume 33, pp. 13539 13550. Curran Associates, Inc., 2020a.
Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear convergent decentralized opti- mization with compression. arXiv preprint arX::2007.00252, 2020b.
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized sgd. In International Conference on Machine Learning, pp. 6415-64255 PMLR, 2020.
Giorgi Nadiradze, Amirmojtaba Sabour, Dan Alistarh, Aditya Sharma, Ilia Markov, and Vitaly Aksenov. Swarmsgd: Scalable deccnttaliied sgd with local updates. arXiv preprinl Xrx: 10.00.2..0 12308, 2019.
Yu E Nesterov and Michael J Todd. Self-scaled barriers and interior-point methods for convex programming. Mathemalics of Operalions research, 22(1):1-442 1997.
Shi Pu and Angelia Nedié. Distributed stochastic gradient tracking methods. Muthematicul Programming, 187:409 457, 2021.
Peter Richtárik, Tgor Sokolov, and Tyas Fatkhullin. E121: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neurol Information Processing Systems, 34:4384 04148844499,,,, 2021.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chich Chen. Mobilenetv2: Inverted residuals and lincar bottlenccks. In Proceedings of the IEEE conference on computer vision and pallern recognilion, pp. 4510 4520, 2018.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint wxXi:1910.01100 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409. 1556, 2014.
Yuki Takezawa, Han Bao, Kenta Niwa, Ryoma Sato, and Makoto Yamada. Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data. arXiv preprint arXiv:2209.1 15505, 2022.
Yuki Takezawa, Kenta Niwa, and Makoto Yamada. Commuicattion compression for decentralized learning with operator splitting methods. IEEE Transactions on Signal and Information Processing over Networks, 2023.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d²: Decentralized training over decentralized data. In International Conference on Machine Learning, pp. 4488. PMLR, 2018.
Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Liu. Deepsqueeze: Decentralization meets error-coppensated compression. arXiv preprint 1xXx:1907.00333 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist machine learning algorithms. arXiv preprint arXiv: Nae:1708.077 708.07747, 2017.
novel image dataset for benchmarking
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems 6 Control Letters, 53 (1):65 78, 2004.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. arXiv preprint (xXi::905.00811 2019.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. Advances in neural information processing systems, 28, 2015.
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejie Chi. Beer: Fast o(l/t) rate for decentralized nonconvex optimization with communication compression. Advances in Neural Information Processing 2022.
Systems,
15

---

Published in Transactions on Machine Learning Research (11/2023)
A Appendix
A.1 Proof of Lemma. 1
This section presents detailed proof for Lemma. [ follows
The NGM algorithm modifies the local gradients as
9' = (1 - a)
Σ
Wjsgh + a
Σ
wiyg = g"
Σ
wislg - g¹) (NGMav uses a = 1)
JEN:
JEAr
JEN;
g" - g* Σ
Wiyl (V, d²) - (2;(2,d'))
JEN:
Now we prove the lemma.
by applying expectation to the above inequality
1 N
17
N (sF(V(((,,)) -VF(e.)
E
g
g')
E
N
JEM
N
E
wiy (z)(VF
JEN;
Wij (E, -VF(2,,
JEN
Σ (z)(VF (VVc)))- -VAte)))
JEN
Wij Wiy -V - VACO)
E
JE
Win -V -
No
JEN
Σ JEN
w/y (z) -
VF d²) - - (VF.(2, -
Σ wiylE
JEA;
N
- TA(T
B E
#= jeN;
N
(()(2) - vA(o) |
Wey 402
B E
N2
N
1=
JEN;
1=1 JEN;
2
N
V.(lo) + VF(x) - -V 1/
Σ
Wiy E
(1)(2)
(:: Σ
Wij wiy= 11)
N2
N
i=1
JEV:
JEN,
( 40
N
Σ
We
2E
V1((2) - -
+2E [/(00- VF() (T)
N
1=1
JEN,
40²
Σ
whi
N
N
j=
16

---

Published in Transactions on Machine Learning Research (11/2023)
4
N + 45²
(a) identity 2[ 21|l - B[] holds for any random vector Z; (b) the fact (I = Vf(()): (c) VFi(z, d') - Vf((x) are independent random vectors with 0 mean and Elll Σ Z Σ Bill 211 holds when Z, are independent with mean zero; (d) jensen's incquality;
(e) follows from assumption 2 Ba-D, d) {=(a))11 < o² vi E [1, (f) the basic inequal-
ity ||1 + azll < 2/ 1 + |22l2 for any vectors a1, 02: and (g) follows from assumption 2 that
[Vf(()) [F())| < ( [1
we have following bound given by lemma.
I 1l
g'l - 4 + (2)
A.2 Convergence Analysis
In this section, we present the proof for our main theorem. indicating the convergence of the proposed NGM algorithm. Before we proceed to the proof of the theorem, we present a lemma showing that NGM achieves consensus among the different agents.
A.2.1 Bound for Consensus Error
Lemma 2.
Given assumplions 1-3 and lemma 1 the dislance belween the averoge sequence ilerale T and the sequence iterates x. 's generated NGM (i.e., the consensus error of the proposed algorithm) is given by
(0" + +²) 8)-1 vp2 (1- 3)
6n
K
N
B
+
K +
E N
Σ
(11)
vp)
k=
k=0
where K 2 and BE (0 is the momentum coefficient.
To prove Lemma and Theorem. we follow the similar approach as (Esfandiari al., 2021 Hence, we also define the following auxiliary sequence along with Lemma
3
3
2
8
(12)
8
1 B
Where le > 0 and X is obtained by multiplying the update law by N 11 (1 is the column vector with entries being 1).
1 N
Vx = BV 1]
8k-1
(13)
X X
If & = 0 then z² = x For the rest the analysis, the initial value will be directly set to 0.
To prove Lemma. we use the following facts.
2
17
(14)
1
N
K
32
K
7 x4 11
Σ
(15)
(1 - 3)
k=0
Note that the proof for Eq. respectively.
14 and Eq. can be found in
(Esfandiari al.
2021 as lemma-3 and lemma-4
17

---

Published in Transactions on Machine Learning Research (11/2023)
Before proceeding to prove Lemma 2 the Lemma similar to [sfandiari et al.
introduce some key notations and facts that serve to characterize
2021
We define the following notations:
G2 bb 8K 8k
V
V b: l: 1..
X
X X x
2
(16)
G₂ BL Sk gk
H (f( Vfa( V(x(()
We can observe that the above matrices are all with dimension d N such that any matrix A satisfies |||| 3 E ||a:l?, where a; is the i-th column of the matrix A. Thus, we can obtain that:
N
Xx -I Q)I
| x
(17)
Define Q 11 For each doubly stochastic matrix W, the following properties can be obtained
(1) QW = WQ:
(ii) (I- Q) = W(I - Q);
(18)
(itt) For any integer & 2 1, -I Q] S (Vp) where || lle is the spectrum norm of matrix.
Let A,, E (1,2,.., N} be N arbitrary real square matrices. It follows that
|
(19)
We present the following auxiliary lemmas to prove the lemma. 2
Lemma 3. Let all assumptions hold. Let g² be the unbiased estimate of fi(')) at the point x' such that Elg") = [xx(x)), for all E [N] = (1,2, .... N). Thus the following relationship holds
N
10o²
N V(((x))
N + 8 +
2F
(20)
N
N
Proof for Lemana
N
E
Σ
Σ
g
11
1=1
1
1
2E
g")
21E
g
N
1=1
i=1
b
+ 20²
1
N
$ 8(
+ +
+ 2E
(x((
N
N
N
10o2
N
+ 8 + 2E
Σ Vf((t))
N
N
18

---

Published in Transactions on Machine Learning Research (11/2023)
(a) refers to the fact that the incquality |a + bll² 2||a|12 + the second term uses the conclusion of Lemma. 1 in Yu et al. 2019
b (b) The first term uses Lemma and
Lemma 4. Let all assumplions hold. Let ge be the unbiased estimate of fi(x)) of the point x² such that Elg"] = (x')),, for all E [M] == {1, ..., N}. Thus the following relationship holds
G 1..-GG.. G. (.13]
<NN(O² +(3)
(21)
Proof for Lemma 4 is similar to Lemmal and is follows:
Wij (VF VViie.)))))))
E
G
G.
E
JEN;
- (V(A))) -V(G)
E
Wij Wiy
JEN;
wiy (V)((() V)(C))
JEN
Σ Wi E
(F,( - - (VF(xx vA(a))
JEN;
(F(+)) -V |
Vf((z))
Wiy E
< (o
(follows from assumption 2)
The properties shown in Eq. 18 and 19 have been well established and in this context, we skip the proof
here. We are now ready to prove Lemma
Proof for Lemma g Since X = X W V we have:
X Q) X x QJW V. QQ)
(22)
Applying the above equation times we have:
(I = Xo ( + Σ V, Q) X,=0 Σ
V, (I [I-QQ=*++ Q)
(23)
1=1
As V₁ = -
- , Σソ N
GK k-1
Va=0
- ΣN Gi k-1 we can get:
- [I- -I-Q)* -K+
G -
1 Σ G.l Σ
--1-- Q)
(24)
1=++l
gk
(1
-
B
19

---

Published in Transactions on Machine Learning Research (11/2023)
Therefore, for k 2 we have:
2
g
B
Xx
Q
E
G. - Q) --
gk-
22
21/²E
(G, G1)(I- Q) w
B
0
8
(25)
3h
2n
Σ
-I
- Q)
B
r=0
(a) follows from the inequality | - B 2 A + B
We develop upper bounds of the term
gh-r G. Q)
8K-T
E
Σ E
(G, -G -
1- 3
3
7=0
h-1
G, - G
(1 8)
4N + (2)
A-I-TN(O
+ + v
(1 - B)2
(1 3) p)
(26)
(a) follows from Jensen's inequality. (b) follows from the inequality 1- Lemma and Frobenius norm. (d) follows from Assumption 3.
I I-3
(c) follows from
I-3
We then proceed to find the upper bound for term II.
k- gh-r
3 -
E
G Q)
E
G, (I- QJ--))
B
B
7=0
7=0+'=0
1 gh-
G
Q
W
1 1-B
k- 1 k-1
E
|
Gr
8)2
G
+
B[|
(1 8)
k- k-1
G
(1 3)3
7=0+==0
k-1
G
(1 - 3) vp)
==0
(27)
(a) follows from Eqq. 19
(b) follows from the inequality zy S {x² + 2²) for any two real numbers 2, y. (c)
--1
is derived using Σ -
p
1-10
20

---

Published in Transactions on Machine Learning Research (11/2023)
We then proceed with finding the bounds for ||| G 13):
E B| |1 = = H, + H, H,
S [3 G - H + - +3|
(28)
N
3 3NO2 + 3N + 3|3
Σ {((()))
(a) holds because
[ H Q
EIl Σ {x(
Substituting
28
in
27
gk-r
k-1 S (1 (1) Vp)
E
GI Q) Q 1-r
3No + +3N5² + 3
1 B
T=0
3N2
3N
k-1
Σ
V V((((
(1 11 vp)²
(1 ()
vp)
T=0
1=1
(29)
substituting 29
and 26 into the main inequality 25
N (3)
2n²
3N2
3N((2))
E
X [I Q
$
11 ()2 (1- p)
(1- 3)
vp)
1 vp
VP
N
3N
{x(+))111
N
21²²
[NN(22 + +33)
3No²
3NC²
(1 B1-
1-p P
(1
vp)²
(1 vp)²
6N
k-1
E|l
Σ (
(1 - 3) vp)
T=0
14
0²
2
6N
Σ
+ (1 vp)
+
(1- 8)² (1 vp)²
(1- 3)
vp)
0
(30)
2
Summing over ie fl...., K 1} and noting that Xo
Q)
0:
K-1k-1
N
E
< CK +
Elll N
{x(
(1-B)a(1 vp)
6N
<CK (1 - 83 vp)
E[I N
Σ
v
(31)
6N1
N
2 CKK+ + (1- () vp)
Blll Σ V(((
21

---

Published in Transactions on Machine Learning Research (11/2023)
Where 14 (1-3)²
n²
(i-vayy
+
Dividing both sides by N:
27
14n²
0²
G²
X
Q)
K+
(1 - B)²
(1 vp)
(1 vp)²
(32)
6n²²
k
N
Bll Σ [x(())1
(1- 31-
vp)
k=
Hence, we obtain the following as the lemma. 2
N
x 17
S 14 +2)
6r7
E
K +
T
{((x))111
(33)
(1 3)2(1
vp)
(1 - 3)2
p
N
k=
k=
1=1
A.2.2
Proof for Theorem.
1
Proof: Using the L-smoothness properties for F we have:
B [((
B((F(()))))) Za+1 - 2c)] + + EEll 26+1
- =x11?]
(34)
Using Eq.
we have:
N
V 26+11 -x)] = -1
1 - (Vss))
N
1 N
N
(35)
1-8 ((VF(E)) -FF(E))
1|
Σ
الحه
"
E
(
Σ &
N 2m1
1-
N
x=1
T2
We proceed by bounding Ti:
1-3 - (VFF(())) VF(X)),
-1
8k
N
( (1- 3)
LL12²
N
El VF(ae)
VF({))] +
[1
(36)
23L
2(1 - 3)3
(60
(1 L
BLn²²
N Σ |P
Ell - Xx 11++
El|
233
2(1
3)3
N
81-8
(i) holds as (a, b) < ||a2|/2 + 1|bb122 where a uses the fact that F is T-smooth.
VF((z) vf(Xx)) and b
(1-3) N 1 gi and
>>
V
22

---

Published in Transactions on Machine Learning Research (11/2023)
We split the term T2 as follows:
N (xx):
1
VF
8k
(FF
(xk)
Bk
gk
+
gi))
N
N
i=1
N
N
(37)
(VF(X))
1
Σ
(Bk
g
|F
(Xxs
1
gh
N
N
73
Now, We first analyze the term T3:
NY Σ
(1 (1- (XA))(X)
(g) gi.)
(38)
(1 (1- 3) [ +
TL
N
$
Blll
Σ gi 1
2BL
2(1 3)3
N
This holds as (a, b) < |||a|12 + 1 |b|2 where a
-V1-DVF(Xx) and b
OVEL
(1- NV レm - -g))
VsL
Analyzing the term T4:
E
VF (Rx);
1
1 N gi) = E (VF(E))
v(((()
(39)
N i=1
Using the equity (a, b) _|||a112 + ||b||2
||a -b]l,, we have
N | (I+) +1
(V)(
fc (xx))= = 1/2
N -I1F())))))
1 Σ
v(((x()11
N
(40)
N
N
2/
|VF 2 + N
v(((x))11
- 12 N
Σ
|| - x
2
1=1
(a) holds because
[xxx))
1 ト
vf = Vf(xH - MΣ vx((2111 S
EN - < 1.
Σm L2 1x -x 12.
Substituting
400
into
39
we have
N
E
(Rs)))
N
gk
2
+1+++
1,2
Σ Bl|xx - - (41)
Substituting
38
41
into
37
we have
17
(VF(())
E
Σ
(1
- ()
17
E
VJ
113 + T23L
E||
(g)
-
N
23L
2(1
3)
2(1 3)3
17
[||
1
V)((t))
nL2
1 N
Σ
R
B|| - x
2(1
3)
N
2(1 - 3) N
(42)
23

---

Published in Transactions on Machine Learning Research (11/2023)
Now, finally substituting
42
36
into
35
have
(1
B
N
(1- [)
[[(VF(Zz), Zk+11 z+)1 -
B
Z1 x1+1 +
EII N
Σ
23
2(1 - B)
23L
2(1 - 3)
([) 2(1 33
71
B[1l
1
Σ
9)3 B111
1
Σ
BB
+
T122²
1 N
Σ Bl| x
N
N
2(1 - (3)
N
(43)
Equation. 14 states that:
n/2
Elll 1 N
E Z1 2z|1 =
Σ I...
(44)
(1-
N
Substituting 43
44
in
434
B[F(2++1)] S [[F(2 + (1 B
Elllz xxx + 3Ln²
N Σ
(11 (3)
2(1 - B)3 B1Il
+
2
N i=1
23L
2(1 3)
"
Bill 1
vf(( + 37.
Bll
1
Σ
Bi 1
2(1 B)
2(1 3)3
NV
1=1
T/222 1
172
1
Σ
E|| x 17 + (1 3)2
Fill
Σ |7
2(1 - 3) N
N
We find the bound for ( =1 by rearranging the terms and dividing by C₁ 2(1-9)
(1-9))
28T.
N
E| [[ 1 Ci
[[F((z)] - E(F(E)))))
+ C2 ETI E11
Σ 1 + T₂ E[|Z - 13
N
C
N
- Co Elll N
f + E Bill
[g)
+
E Bl||x - 1
N
N
1=1
[=l
Where Ö₂ = ALa²² 211-0
+
n't (1-
/C1, Ö. = (1-8)L 23
CC, Č2
n BL 2(1-9)3
C1, Ōs = 91
/C,, Čo 211- /c.
2(1
Summing over & E I0.,,...,, K-11 - -1}:
K-1
Σ E (x+)))
1
B (2o)] [[o()
- E J (2m)] )
To
E
1
N
V
(xit
Σ E
N
k=
k=0
i=1
k=0
K-1
K-1
K-1
N
+
C
|ل
C4
R
g
Bi)
|
C
Σ
R
-
[=]
N
N
k=
k==0
k=
1=1
Substituting Temma
Lemma
Lemma and Equation.
15 into the above equation, we have:
24

---

Published in Transactions on Machine Learning Research (11/2023)
( [ (Zo)) (B (ōs 2Ō2 - 282--2220 -2Ōs 1/2
61A² 2
| {xx) |x)))
~ o
(1 3) - C (1 - 3) vp)
1 N
Σ
Vie (xx)
17 + {(²x + Ö3 1/-3²
( (1o0² + 882) K + 10, ( 00²
+ + )²)r
N
(1 - 3)4
k=
i=1
14n + (2)
+ +0s (1- 3)2 vp)² K
Dividing both sides by K and considering the fact that 2n = xo and (7o - 20²
220 n²g²
[1-3]²
C. (1- (1-8)(1-V)) VDJ
612 20: 0:
F((x) -F()))=) + (Ōx + E (1- 1-50
) (110²
Σ |V
- CKK
N + 882)
K
0²
+ +(²) + +0s 10" +²²
+ 4C²
N
(1 -1 vp)2
1
(F (xx) - -F*)+ + (1062 + 1100g (1 3y- + 4C2
(x² = + +C5 (1- 3)²(1 vp)²
147) + (2)
CKK
1 (F(39)
- -F)) + (107s 100g
8/
+ 4C,
0²
+ {3)
+ 05 (1 - 3)2(1 vD)
14 + (2)
GK
(1 (1- (1-
Now, we simplify the coefficients:
32
10n + 18))
200)2 + (3)
10C2+ + 10C' (1 (1-3)- B)1
+ +40.5
/01
3)3
(1 - (3)(11 - - -3)-
14n/
14/3
03 (1- (1 (1- - (1 (1--3())--(1133))))
Now we redefine the coefficients:
200 +3)
C2 (1 3)((1L - (1 3)2)
143
C (1 - (nn - -1-1)) 3)2)
Therefore we arrive at the bound given by the theorem.
K Σ
K-1
1 (+ CK
Ca( 0² N
+(+)+
+ C2 (0" (1 - vp)
(45)
A.2.3 Discussion on the Step Size
In the proof of Thcorem 1 assumed the following -02
n²3² 20s
Cs (1 (1-8)2(1 vp)
6n
2 0.
The above equation is true under the following conditions:
C > 0
4L
61
(M) (1 - (1-33)² "1
11 122 20
(1- vp)
(1-
25

---

Published in Transactions on Machine Learning Research (11/2023)
Solving the first inequality gives us 1-
La 2
In - 1). / 1+
4
We can simply this further by using the Taylor series approximation i.e. 1 < Now, solving the second incquality, combining the fact that > 0, we have then the specific form 1)*
In
vD)² + 6(1 - vP)( - 3)2 2(1 vp) 4 (1]-vp)
69
Therefore, the step size ni is defined
S 4(1 vpl² + 6(1 vP)(1
B3² 2(1 vP)
61.
A.2.4 Proof for Corollary
We assume that the step size is O v/N vK
and (² is 0 ((²)).
Given this assumption, we have the following
N
VN
C3 0 VK
VN C. =0 VN
C c 0
C2 0
VK ) ) 03 0
This implies that
C2 = O V
N C3 = 0
Now we proceed to find the order of each term in Equation.
45
To do that we first point out that
F(xo) F CiK
0
1 VNK
For the remaining terms we have,
22 C2
VN
C2
0
C2
0
N
VNK
σ²
N
5²
C
= O
CO
= 0
[1
2
K
vp)
K1.5
Therefore, by omitting the constant N in this context, there exists a constant C such that the overall convergence rate as follows:
so s
Σ E VF [x))
VNK + K K
(46)
K
which suggests when K is sufficiently large, NGM enables the convergence rale of O (NR))
A.3 Decentralized Learning Setup
The traditional decentralized learning algorithm (d-psgd) is described as Algorithm. For the decentralized setup, we use an undirected ring and undirected torus graph topologies with a uniform mixing matrix. The undirected ring lopology for any graph size has 3 peers per agent including itself and each edge has a weight of _.. The undirected torus topology with 10 agents has peers per agent including itself and each edge has agents have 5 peers per agent including itself and cach edge has weight of J. Finally, Figure 5 depicts the overview of the proposed NGM algorithm. Note that we do not have step of the Figure in NGM algorithm.
weight of 4. The undirocted torus topology
26

---

Published in Transactions on Machine Learning Research (11/2023)
4-agent Ring Topology
Neighborhood Gradient Clustering
Self Gradients
Gy
G21
Communicate model parameters
Compute model-variant cross-gradients
G.2
Receive data-variant cross-gradients
G.
Gei
Gradient Aggregation (mean)
5
Model update- Local
Model update Global
Figure 5: NGM algorithm overview. In the proposed algorithm, (1) each agent computes self-gradients of model parameters on its own data set; (2) each agent sends its model parameters to its neighbors; (3) each agent computes the model-variant cross-gradients of its neighbors' models on its own data set; (4) each agent receives the data-variant cross- goas-gradsents from its neighbors; (5) update the local gradient using the mean of self gelf-gradients and cross-gradiee pross-gradients ; (6) update the model parameter using local SGD step with updated gradients; (7) and update the model parameter using global gossip averaging step.
Algorithm Decentralized Peer-to-Peed Training (D-PSGD with momentum)
Input: Fach agent N] initializes model weights */oy step size n, averaging rate 7, mixing matrix W [w]]kke((),) and Iy are elements N x N identity matrix.
Each agent simultaneously implements the TRAIN() procedure
1. procedure TRAIN()
2. for k=0,1 1,... K - do
3.
d D
// sample data from training dataset.
4.
// compute the local gradients // momentum step // update the model // share model parameters with neighbors N()..
5.
1i Beta-1) - ngi
6.
b. ot + oi
7.
SENDRECEIVE(21)
8.
<//41)> 34 + Eyexi - 1,
// gossip averaging step
9.
end
10.
return
27

---

Published in Transactions on Machine Learning Research (11/2023)
A.4 CompNGM
The section presents the pscudocode for CompNGM (compressod version of NGMaa) in Algorithm 3 The aG algorithm at every iteration involves two rounds of communication with the neighbors: 1) communi- cate the model parameters, and 2) communicate the cross- pross-gradients. This communication overhead can be a bottleneck in a resource-constrainod environment. Hence we propose compressed version of NGMd, using Error Feedback SGD (EF-SGD) (Karimireddy et al., 2019) to compress gradients. We compress the error- compensated self-gradients and cross-gradients from 32 bits (floating point precision of arithmetic operations) to bit by using scaled signed gradients. The error between the compressed and non-compressed gradient of the current iteration is added as feedback to the gradients in the next iteration before compression.
Tables. 9 10 compare the proposed CompNGM with CompCGA and show that our method outperforms CompCGA. We also analyze the impact compression on consensus error, validation loss, and validation accuracy with respect to communication bits the top panel of Figure. [ We present the consensus error, validation loss, and validation accuracy with respect. to epochs in the bottom panel of Figure. G Note that epochs are proxics for communication rounds. In Figure. each epoch contains 157 communication rounds. For the Figure. 8 experiment,
use step-lr scheduler for the learning rale schedule whereas the experiments in Tables. 8| 10 use the multistep-Ir scheduler. We observe that both for iso- aso-ommmmication cost and iso-epochs, NGMdv performs better than CompNGM in terms of validation accuracy.
Algorithm 3 Compressed Neighborhood Gradient Mean (CompNGM)
Input: Each agent i [1, N] initializes model weights z(o)= step size 77, averaging rate y dimension of the gradient d, mixing matrix [W)]kJe([,,)] NGM mixing weight a, and Ii are elements of N N identity matrix.
Each agent simultancously implements the TRAIN() procedure
1. procedure TRAIN() )
2. for k=0, 1,...., do
3.
d
// sample data from training dataset // compute the local self celf-gradients // error compensation for self-gradients // compress the compensated self-gradients // update the error variable // share model parameters with neighbors N N())
4.
91 (afi(dh:zz))
5.
Ph gh c
6.
7.
k+1 Pk oi
8.
SENDRECEIVE(21)
9.
for each neighbor j E (N(1) - ii do
10.
g vaf((di;
// compute neighbors' cross-gradients // error compensation for cross-gradients // compress the compensated cross-gradients // update the error variable
11.
Pg Dk
1 +el
12.
& (lld"ll/dssgn(p)))
13.
1+1 = ph
14.
if a # 0 do
15.
SENDRECEIVE(6))
1/ share compressed cross- cross-gradients between and j
16.
end
17.
end
18.
g. = (1 a) E
EjEN, wfiohh + EjEN. Wi
// modify local gradients
19.
v Bo(k-1) 199h
// momentum step
20.
H = t + Uk
// update the model // gossip averaging step
21.
k(++1) Ix + Ejen 1z)
22.
end
23.
return
28

---

Published in Transactions on Machine Learning Research (11/2023)
Table 8: Average test accuracy comparisons for CIFAR-10 with non-lID data using various architectures and graph topologies. The results averaged over three seeds where std is indicated.
5layer CNN
5layer CNN Torus
VGG-11
ResNet-20
Method
Agents
Ring
Ring
Ring
82.00 + 0.25
83.65 0.41
86.73 + 0.34
CompCGA
10
71.41 + 0.94
75.95 + 0.41
73.96 + 0.31
73.63 + 0.55
20
68.15 = 0.79
71.71 = 0.54
73.72 = 2.74
66.34 = 0.98
5
82.91 = 0.21
84.03 = 0.32
87.56 = 0.34
CompNNG (ours)
10
74.36
+: 0.42
77.82 + 0.20
77.02 + 0.14
78.50 + 0.98
20
71.46 = 0.85
73.62 + 0.74
73.76 + 0.20
72.62 = 0.71
Table 9: Average test accuracy comparisons for various datasets with non-III sampling trained over undi- rected ring topology. The results are averaged over three seeds where std is indicated.
Fashion MNIST
CIFAR-100 (ResNet-20)
Imagenette(32x32)
Method
Agents
(LeNet-5)
(MobileNet- V2)
90.45
0.34
55.74 = 0.33
72.76 = 0.44
CompCGA
10
81.62
0.37
38.84 0.54
59.92 = 0.72
90.48
0.19
57.51
0.48
72.91 1.06
CompNGM (ours)
10
83.38
0.39
43.07 + 0.32
61.91 + 2.10
Table 10: Average test accuracy comparisons for AGNews dataset (left side of the table) and full resolution (224 x 224) Imagenette cataastt (right side of the table). The results are averaged over three seeds where std is indicated.
Method
AGNews- CGNNws-BERT mini
AGNews- DistilBERT base
Imagenette (
Agents 4
Agents =
Agents = 4
Agents = 5
Ring Topology
Ring Topology 93.54 + 0.03 93.50 + 0.16
Ring Topology
Chain Topology
CompCGA
91.05 + 0.29
88.91 + 0.25
84.65 + 0.57
62.93 + 1.33
CompNGM (ours)
91.24 + 0.43
89.01 + 0.13
85.44 + 0.10
62.64 + 0.85
A.5 Datasets
In this section, we give a brief description of the datasets used in our experiments. We use a diverse set of datasets each originating from a different distribution of images to show the generalizability of the proposed techniques.
CIFAR-10: CIFAR-10 Krizhevsky et al. 2014 is 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 (Krizhevsky et al. 2014b is an image classification dataset. with 100 classes. The image samples are colored (3 input channels) and have a resolution of 32 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 a harder task compared CIFAR-10 as has 100 classes with very less samples per class
to learn from.
Fashion MNIST: Fashion MNIST Xiao et al. 2017] is an image classification dataset with 10 classes. The image samples are in greyscale (1 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.
Imagenette (Husain 2018) is 10-class subset of the ImageNet datasct. 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. We conduct. experiments on two different resolutions of
Imagenette:
29

---

Published in Transactions on Machine Learning Research (11/2023)
ng compnimm
6
ag
Consensus Error
2.5
Validation loss
compngm
Validation accuracy
50
2.0
mwy
40
1.5
1.0
ngm
0.5
20
comp
0.0
6
6
Communication (.1e10)
Communication (.ee10)
Communication (.1e10)
(a)
Consensus error Communication (b)
Validation loss Communication (c) Validation accuracy Communica-
bits
bits
tion bits
Validation accuracy (%)
70
ngm#v
ngm
Consensus Error
2.5
compngm
Validation loss
compngm
60
2.0
50
1.5
40
30
ngmav
20
comp
150
200
200
100
150
200
Epochs
Epochs
Epochs
(d) Consensus Epochs
(e) Validation loss
Epochs
(f) Validation accuracy Epochs
Figure 6: Consensus error, validation loss, and validation accuracy against communication bits (top panel) and epochs (bottom panel) for training CIFAR-10 (non-IID) on ResNet-20 architecture over ring topology with 10 agents.
the Imagenette dataset a) a resized low resolution of 32 x and, b) a full resolution of 224 x 224. The Imagenette experimental results reported in Table. 3 use the low-resolution images whereas experimental results in Table. 4 use the full resolution images.
AGNews: We use AGNews (Zhang et al. 2015) dataset for Natural Language Processing (NLP) task. This is text classification dataset where the given text news is classified into 4 classes, namely 'World', "Sport', 'Business' and 'Sci/Tech', The dataset has a total 120000 and 7600 samples for training and testing respectively, which are equally distributed across each class.
A.6 Network Architecture
We replace it was shown to be better suited for decentralized learning on non-lID data (Lin et al. 2021).
layers of all the model architectures with EvoNorm-SO [Lu et al. 2020a
5 layer CNN: The 5-layer CNN consists of 4 convolutional with EvoNorm-SO (Liu et al. 2020a as an activation-norrmallztiioon layer, 3 max-pooling layers, and one linear layer. In particular, has convolutional layers with 32 filters, a max pooling layer, then more convolutional layers with 64 filters each followed by another max pooling layer and a dense layer with 512 units. It has total of 76K trainable parameters.
VGG-11:
We modify the standard VGG-11 (Simonyan & Zisserman 2014) architecture by reducing the number of filters in each convolutional layer by 4x and using only one dense layer with 128 units. Each con- volutional layer is followed by EvoNorm-SO as the activation-normaaizzliiin layer and it has 0.58M trainable parameters.
ResNet-20: For ResNet-20 HH et al. 2016 ; we use the standard architecture with 0.27M trainable pa- rameters except. that. R layers replaced by EvoNorm-SO.
30

---

Published in Transactions on Machine Learning Research (11/2023)
LeNet-5: For LeNet-5 eters.
[eCCnn et al. 1998). we use the standard architecture with 61, 706 trainable param-
MobileNet- V2: We use the the standard MobileNet-V2 (Sandler et al. 2018 architecture used for CIFAR dataset with 2.3M parameters except that BatchNorm- ReLU layers are replaced by EvoNorm-SO.
ResNet-118 For ResNet-18 (He et al. 2016), we use the standard architecture with 11M trainable param- eters except that BatchNorm++ReLU layers are replaced by EvoNorm-SO.
2018 we use the standard model from the paper. We restrict the sequence length of the model to 128. The model used in the work hence has 11.07M paramcters.
BERT mini: For BERT mini (Devlin et al.
DistilBERT base: For DistilBERT hase (Sanh et al. 2019) we use the standard model from the paper. We restrict the sequence length the model to 128. The model used in the work hence has 66.67M parameters.
2.00
ring
ring
ngm
Validation Loss
torus
Validation Loss
torus fully-connected
Validation Loss
cga
1.75
fully coine-con
4
1.25
4
1.00
0.75
0.50
60
120
180 Epochs
240
300
60
120
180
240
300
60
120
180
240
300
Epochs
Epochs
(a) NGM on IID data
(b) NGMa, on non-IID InD data
(c) Non-IID) for ring topology
Figure 7: Validation loss for CIFAR-10 dataset trained on 10 agents ring graph with 5-layer CNN.
A.7 Analysis for 10 Agents
We show the convergence characteristics of the proposed NGM algorithm over IID and Non-IID data sampled from the CIFAR-10 dataset in Figure. ((a) and 7(b) respectively. For Non-IID distribution, we observe that there is a slight difference in convergence rate (as expected) with slower rate for sparser topology (undirected ring graph) compared to its denser counterpart (fully connected graph). Figure. 7(c) shows the comparison of the convergence characteristics of the NGMar technique with the current state- of-the-art CGA algorithm. We observe that NGMas has lower validation loss than CGA for the same docentralized sctup indicating its superior performance over CGA. We also plot the model variance and data variance bias terms for both NGMd and CGA techniques as shown in Figure. 8(a) and [(b) respectively. We observe that both model variance and data variance bias for NGMav are significantly lower than CGA.
A.8 Resource Comparison
The communication cost, memory overhead, and compute overhead for various decentralized algorithms are shown in Table. 6 The D-PSGD, QG-DSGDm, and NGM algorithms require each agent to communicate model parameters of size m, with all the n, neighbors for the gossip averaging step and hence has a commu- nication cost of Onnm..) In the case of NGM and CGA, there an additional communication round for sharing data-variant cross gradients apart from sharing model parameters for the gossip averaging step. So, both these techniques incur communication cost of O(2n,m,)) and therefore an overhead of O(n,m,) com- pared to D-PSGD. Momentum Tracking also needs additional communication to communicate the tracking variable. CompNGM compresses the additional round of communication involved with NGM from b bits to bit. This reduces the communication overhead from O(n...)) to O n.m,
communication
CGA algorithm stores all the received data-variant cross-gradients the form of a matrix for the quadratic projection step. Hence, CGA has a memory overhead of O(n,m.) compared D-PSGD. NGM does not require any additional memory it averages the received data-variant. cross-gradients into the self-gradient
31

---

Published in Transactions on Machine Learning Research (11/2023)
Model-Variance Bias
0.016
ngM
Data-Variance Bias
0.025
ngmav
cga
cga
0.014
0.020
0.012
0.010
0.015
0.008
0.006
0.010
0.004
0.005
0.002
0
60
120
180 Epochs
240
300
0
60
120
180
240
300
Epochs
(a) Average L1 norm of
(b) Average L1 norm w.
Figure 8: Average L1 norm of model variance bias and data variance bias for 10 agents trained on CIFAR-10 dataset with 5 layer CNN architecture over undirected ring topology.
Table 11:
Memory overheads for various methods trained different model architectures with CIFAR-10 dataset over undirected ring lopology with 2 neighbors per agent.
CGA
NGMd (MB)
CompCGA
CompNGM
Architecture
(MB)
(MB)
(MB)
layer CNN
0.58
0
0.58
0.60
VGG-11
4.42
0
4.42
4.56
ResNet-20
2.28
0
2.28
2.15
buller. The compressed version of NGMdo requires an additional memory O(nem.) store the error variables eÿx (refer Algorith. 3. CompCGA also needs to store error variables along with the projection matrix of compressed gradients. Therefore, CompCGA has a memory overhead of O(nm, + mam=)). Note that memory overhead depends the type of graph topology and model architecture but not on the size of the graph. The memory overhead for different model architectures trained undirected ring topology is shown in Table. 11
The computation the cross-grade gross-gradsents (in both CGA and NGM algorithms) requires n, forward and back- ward passes through the deep learning model at each agent. This reflected as O(n,)) B) the compute overhcad Table. D We assume that the compute effort required for the backward pass twice that of the forward pass. CGA algorithm involves quadratic programming projection step (Goldfarb & Idnani 1983) to update the local gradients. Quadratic programming solver (quadprog) uses Goldfarb/IInann I dual algorithm. CGA uses quadratic programming to solve the following (Equation 47 2021 optimization problem in an iterative manner:
sce Equation 5a in (Esfandiari et al.
min,
{ ot GG u + o
(47)
8.b.
u20
where is the matrix containing cross-gradients, g is the self-gradient, and the optimal gradient direction g* in terms of the optimal solution of the above equation u² is g" GT +g. The above optimization takes multiple iterations, resulting in compute and time complexity of polynomial(degree) 2) order. In contrast, NGM involves simple averaging step that requires O(n,m,)) addition operations.
A.9 Communication Cost
In this section we present the communication cost per agent in terms of Gigabytes of data transferred during the entire training process (refer Tables. 12
13
15
The D-PSGD and NGM me have the lowest
32

---

Published in Transactions on Machine Learning Research (11/2023)
communication cost (1x). We emphasize that NGM outperforms D-PSGD in decentralized learning over label-wise non-IID data for the same communication cost. NGMdr and CGA have 2x communication overhead compared to D-PSGD where as CompNGM and CompCGA have 1.03x communication overhead compared to D-PSGD. The compressed versions of dGMds and CGA compress the second round of cross- gradient communication bit. We assume the full-precision cross-gradients be of 32-bit precision and hence the CompNGM reduces the communication cost by 32x compared to NGM
Table 12: Communication costs per agent in GBs for experiments in Table and B
5layer CNN
5layer CNN
VGG-11
ResNet-20
Method
Agents
Ring
Torus
Ring
Ring
D-PSGD,
5
17.75
270.64
127.19
QG-DSGDm and
10
8.92
13.38
135.86
63.84
NGMmy
20
4.50
6.65
68.48
32.18
Momentum Tracking,
5
35.48
541.05
254.27
CGA and
10
17.81
26.72
271.50
127.59
NGMd
20
8.98
17.95
136.72
64.25
CompOGA
5
18.31
279.09
131.16
and
10
9.20
13.79
140.10
65.84
CompNGM
20
4.64
9.28
70.61
33.18
Table 13: Communication costs per agent in GBs for experiments in Table and
Fashion MNIST
CIFAR-100
Imagenette
Method
Agents
(LeNet-5)
(ResNet-20)
(MobileNet- V2)
D-PSGD, QG-DSGDm and NGM,.
5
17.25
103.74 74
103.12
10
8.61
51.89
51.60
Momentum Tracking,
5
34.50
207.47
206.23
CGA and NGMav (ours)
10
17.23
103.79
103.19
CompCGA and
5
17.79
106.98
106.34
CompNGMM (ours)
10
8.88
53.52
53.21
Table 14: Communication costs per agent in GBs for experiments in Table 4 and 10 right)
Method
Ring topology
chain topology
D-PSGD, QG-DSGDm and and NGMm²
501.98
401.59
Momentum Tracking, CGA and NGMa,
1003.96
803.17
CompCGA and CompNGM
517.67
414.14
Table 15: Communication costs per agent in GBs for experiments in Table
and 10 (left)
BERT mini
DistilBERT base
Method
Agents
4
Agents
8
Agents
D-PSGD, QG-DSGDm and NGMmy
234.30
118.20
1410.39
Momentum Tracking, CGA and NGM
486.59
236.40
2820.77
CompCGA and CompNGM
241.6
121.89
1454.46
A.10 Hyper- paper-parameters
This section presents the hyper-parameters for the experimental results presented Scc. 5 All the experi- ments were run for three randomly chosen seeds. We decay the step size by 10x after 50% and 75% of the training for all the experiments except for figures. To generate the figures, the simulations for 300
33

---

Published in Transactions on Machine Learning Research (11/2023)
Table 16: in Table 2 and g
used for CIFAR-10 10 with non-IID data using various model architecture presented
Layer CNN
VGG-11
ResNet-20
Method
Agents (n)
Ring
Torus
Ring
Torus
(3, 17, 7)
(3. 1/ 7)
(B, V. 7:)
[9. 7. 7)
5
(0.0, L.0)
(0.0, 0.01, 1.0)
(0.0, 0.1, 1.0)
D-PSGD
10
(0.0, 1.0)
(0.0, 1.0)
(0.0, 0.01, 1.0)
(0.0, 0.1, 1.0)
20
(0.0,0.1,1.0 1.0)
(0.0,0.1,1.0)
00.0,0.01,1.0
(0.0, 0.1, 1.0)
(0.9, 0.01,
00.9,0.01,
(0.9, 0.1,
QG-DSGDm
10
(0.9, 0.0,0.01,,10)
(0.9, 0.00, 0.1)
(0.9,0.01,
(0.9, 0.1,
20
(0.9, 1.0)
(0.0, 0.000,0 0.1)
00.9,0.01,
(0.9,0.1,1.0)
5
0010,
(0.9,0.01,
(0.0, 1.0,
NGM
10
(0.0, 0.1,
(0.0, (0.0,0.1, 1.0) (0.0,0.1,
00.0,
(0.0, 1.0,
20
(0.0, 00,,
(0.0,0.01,10)
(0.0, 1.0,
0.01,,
00.9,0.01,
(0.9,0.1, 1.0)
Momentum Tracking
10
1.0
(0.0,0.01, (0.9,0.01, 0.01, L.0)
(0.9,
(0.
20
(0.9, 0.00,
00.9,0.01,
(0.9,0.1,
5
(0.9, 0.)
00.9,0.1,0.5)
(0.9,0.1,1.0)
CGA and NGM
10
(0.9,0.01.0.5)
(0.9,0.01, 0.11
(0.9.0.1.0.5)
00,
20
00.9)
(0.9, 0.01.0.1)
00.9,0.1.0.5
1..9)
5
(0.9, 0.0,
(0.9,0.01.0.1 00.9,0.01,0.1)
CompCGA and CompNGM
10
(0.9, 0.0,0.01,,033 0.5)
(0.9, 0.000..1.111 0.1)
(0.9,0.01.0.1)
(0.9,0.01,
20
(0.9, 0.0.1.051.. 0.5)
0.9.0.01.0.11
0..9.0.0..01)
(0.9.0.01.0.) 0.1)
epochs with the StepLR scheduler where the learning rale is decayed by 0.981 after every epoch. We have used a momentum of 0.9 for all QG-DSGDm, Momentum Tracking, CGA, and NGM experiments. How- ever, for D-PSGD and NGMme, the momentum is set to either 0.9 or 0.0 based on the validation accuracy. The averaging rate is always set to 1.0 for the Momentum Tracking algorithm.
Hyper-paramcters for CIFAR-10 : All the experiments that involve 5-layer (Table. 2 have stopping criteria set to 100 epochs. We decay the step size by 10x in multiple steps at 50th and 75th epoch. All the experiments for the CIFAR-10 dataset trained on VGG-11 and ResNet-20 (Table. 2 have stopping criteria set to 200 epochs. We decay the step size by 10x in multiple steps at 100 and 150th epoch. Table 16 presents the 3, 17, and y corresponding to the momentum, step size, and gossip averaging rate.
Hyper-parameters used for Table. 3 All the experiments in Table. 3 have stopping criteria set to 100 epochs. We decay the step size by 10x in multiple steps at 50th and 75th epoch. Table 17 presents the B, n, and y corresponding to the momentum, step size, and gossip averaging rate. For all the experiments related to Fashion MNIST and Imagenette (low resolution of (32 x 32)), we use a mini-batch size of 32 per agent. For all the experiments related to CIFAR-100, we use a mini-batch size of 20 per agent. For all the experiments, use mini-batch size of 32 per agent.
Hyper-parameters used for Table. 4 (right): All the experiments in Table. (right) have stopping
criteria set to 100 epochs. We decay the step size by 10x at 50th 75th epoch. Table 18 (right) presents the B, T,, and 7 corresponding to the um, step size, and gossip averaging rate. For all the experiments, we use a mini-batch size of 32 per agent.
Hyper-parameters used for Table. 4 (left): All the experiments Table. 4 (left) have stopping criteria set to 3 epochs. We decay the step size by 10x at 2nd epoch. Table 18 (left) presents the B, f) and y corresponding to the momentum, step size, and gossip averaging rate. For all the experiments, use mini-batch size of 32 per agent on the AGNews dataset.
Hyper-parameters used for Table. 7 All the experiments in Table. 7 have stopping criteria set to 60 epochs. The initial learning rate is set to 0.01 and is decayed by 10x at 20th 40th, 54 epoch. For all the experiments, we use a mini-batch size of 64 per agent. The values used for the learning rate, momentum coefficient, and averaging rate are presented in Table, 19
34

---

Published in Transactions on Machine Learning Research (11/2023)
Table 17: Hyper-parametton used for Table. 3 and
9
Agents
Fashion MNIST
CIFAR-100
Imagenette
Method
(n)
(3, 77, 7)
(B, 1, 7)
(B, 1) 7)
(0.0, 0.01,
(0.0,
(0.0, 0.1, 1.0)
D-PSGD
10
(0.0, 0.0,0.01,1.0)
(0.0,0.1,1.0)
(0.0, 0.1,
(0.9,0.01,1.0)
(0.9,0.1,1.0)
00.,,
QG-DSGDm
10
00.9,
(0.9,0.1,1.0)
(0.9,0.01,1.0)
5
(0.9,0.01,,.0)
(0.0,0.1,1.0)
(0.0,0.1,
NGM
10
(0.9,0.01,1.0)
(0.9,0.1,100)
00.0,0.1,1.0)
5
00.9,
00.9,0.1,100
00.,
Momentum Tracking
10
(0.9,0.01,1.0)
(0.9.0.1,100)
(0.9,0.01,
5
00.9,
0099,..1,
(0.0,0.01,0.5)
CGA and NGMa.
10
(0.9,0.01,
(0.9,0.1,110)
(0.0,0.01,0.5)
5
(0.9,0.01,00
00.9,
(0.0,0.01,0.1)
CompCGA and CompNGM
10
(0.9, 0.010.00,0011
(0.9,0.01, 0.010.011
(0.0,0.01.0.5)
Table 18: Hyper-parameters used for Table. 4 and
10
BERT mini
DistilBERT base
Imagenette (ResNet-18)
Method
Agents 4
Agents 8
Agents 4
Ring topology
Chain topology
(3, m,
(3, 7, 7)
(3, n, 7)
(3, T,
[3, v,
D-PSGD
(0.0, 0.01, 1.0)
(0.0, 0.00, 1.0)
(0.0, 0.01, 1.0)
(0.0, 0.01, 1.0)
(0.0, 0.01, 1.0)
QG-DSGDm
(0.9, 0.01, 1.0)
00.9,0.01,100)
(0.9, 0.01,,
(0.9, 0.01, 1.0)
(0.9, 00.9, 1.0)
NGMms (ours)
10.0,0.01, 1.0)
(0.0, 00.0,0.01,1.0
(0.9,0.01,,.0)
(0.9,0.01,,
100,0
Momentum Tracking
(0.9, 0.005, 1.0)
0.0
10.9,
(0.9,0.01,
CGA
(0.9, 00.9,0.01,0.5)
(0.9, 00.9,..01.0.5)
(0.9,0.01,
(0.9,0.01,0.5)
(0.9,0.01,0.1)
NGMa
(0.9.0.01.0.3
(0.9, 00.
(0.9.0.01.
(0.9.0.01.0.5)
(0.9,0.01.0.1)
CompCGA
0001,
(0.9, 0.9,0.01,0.5
(0.9,
(0.9,0.01,0.1)
(0.9,0.01,0.1)
CoMpNGM
(0.9, 0.000.00,0.5
(0.9, 0.01,
(0.9. 0.000.00.055
(0.9,0.01,0.1
(0.9,0.01,0.1)
Table 19: hyperparameters for Table.
Trained for
D-PSGD
QG-DSGDm
NGM
NGM mm
NGM mm
NGM + LM
NGM4
60 epochs
+LM
+ QGM
+ QGM
Learning rate (1))
0.01
0.01
0.01
0.01
0.01
0.01
0.01
Momentum coefficient (8)
0.0
0.9
0.0
0.9
0.9
0.9
0.9
Averaging rate (7)
0.5
1.0
0.5
1.0
1.0
1.0
1.0
35


Reviews:
[{"review_id": "a8xCtoCUKY", "reviewer": "Reviewer_Uzo9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nThe paper is well written and easy to follow. The presentation in this paper is clear, while it requires a little more technical details and clarifications on explaining the proposed algorithm. The theory looks good and empirical results are comprehensive and promising, which include different tasks, datasets, and models. \n\nWeaknesses:\n\nThe novelty of this paper is marginal. It looks like the authors develop their methodologies on top of the paper proposing CGA. Comparing these two papers, the only theoretical difference is that the authors relax the assumption for the difference between the original and included gradient and present Lemma 1 to bound it. Other than that, the theoretical analysis looks pretty similar, in terms of convergence rate and proof techniques, regardless of different terminologies and coefficients. I don’t think this would add great values to the paper. Though we can observe the slight improvements brought by NGC for the accuracies, the significance of the proposed algorithm is not that much.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a novel decentralized learning algorithm that leverages neighborhood gradient clustering in a network to mitigate the issue of poor performance due to non-IID data distributions among different agents. The authors propose NGC in which the local gradients are modified using self- and cross-gradient information, which includes model-variant cross-gradients and data-variant cross-gradients. They also develop a compressed version of NGC, termed CompNGC to reduce the communication overhead. The authors present the theoretical analysis to show the convergence rate of the proposed algorithm. To validate NGC/CompNGC, the authors show thorough empirical results to demonstrate the outperforming capability over the baselines using different datasets and models, with different topologies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please add some theoretical analysis or discussion for the CompNGC.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "04TRQokt4x", "reviewer": "Reviewer_Xvci", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n1) The main paper is clearly written, with its principal claims effectively outlined, making the text easy to follow;\n2) The literature review includes pertinent papers related to the topic;\n3) The authors propose novel algorithms suitable for non-convex objectives, with provable convergence rates;\n4) The authors conducted a comprehensive set of experiments on vision tasks (5-layer CNN, VGG-11, ResNet-20, LeNet-5, MobileNet-V2, ResNet-18 on CIFAR-10, CIFAR-100, Fashion MNIST, and Imagenette datasets) as well as language problems (BERT and DistilBERT on AGNews). Furthermore, they varied different topologies: Ring, Chain, and Torus. In most cases, the proposed methods improved over existing baselines.\n\n**Weaknesses**:\n1) While the paper indeed addresses quite relevant problems of data heterogeneity [3, 4] that are commonly found in the federated learning setting [5], it overlooks some recent advancements in the topic of decentralized optimization, both with and without communication compression. In particular, the authors overlooked a well-known approach called Gradient Tracking [6, 7], which provably removes the dependence on $\\zeta^2$ [8,9,10]. Recently, gradient tracking was also combined with momentum [11].\n2) Unlike methods involving gradient tracking, the rate of the proposed method (NGCdv) depends on the heterogeneity parameter. This means that, in the worst case, the proposed method is still impacted by the non-iid'ness of the data.\n3) The authors presented proof only for the NGCdv algorithm in the manuscript, whereas the convergence rate for the other two methods (NGCmv and CompNGC) is absent. A general analysis for an arbitrary $\\alpha \\in [0,1]$ mixing constant is also missing. Could the authors please clarify this point?\n4) The authors also introduced a compressed version of the NGC algorithm named CompNGC. However, they missed pertinent references to recent decentralized methods with compression [12-15].\n5) Theorem 1 introduces an additional (and rather restrictive) assumption on the step size: \n   $$1-\\frac{6 \\eta^2 L^2}{(1-\\beta)^2(1-\\sqrt{\\rho})}-\\frac{4 L \\eta}{(1-\\beta)^2} \\geq 0.$$\nNevertheless, there's no discussion on its feasibility. Multiple studies on similar topics, such as [3,10,11], do not impose on this assumption.\n6) In Corollary 1, it's assumed that data dissimilarity $\\zeta = O(1/\\sqrt{K})$, while $K$ can be considerably large, as it's required that $K \\geq \\frac{36 N L^2}{r^2}$. This setting aligns more with the homogeneous scenario, which seems to contradict the paper's primary objective. Furthermore, in real-world settings, $\\zeta^2$ can be substantially large, and its value, which depends on the data, is beyond user-level control.\n7) The authors claim to have compared their proposed methods to the existing state-of-the-art. However, the baselines they used for comparison are from 2017 [2] and 2021 [1], which are somewhat outdated.\n\n**References:** \n\n[3] 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, 2020.\n\n[4] Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-IID data quagmire of decen- tralized machine learning. In International Conference on Machine Learning, 2020.\n\n[5] Wang, Jianyu, et al. \"A field guide to federated optimization.\" _arXiv preprint arXiv:2107.06917_ (2021).\n\n[6] Paolo Di Lorenzo and Gesualdo Scutari. NEXT: in-network nonconvex optimization. In IEEE Transactions on Signal and Information Processing over Networks, 2016.\n\n[7] Angelia Nedić, Alexander Olshevsky, and Wei Shi. Achieving geometric convergence for distributed opti- mization over time-varying graphs. In SIAM Journal on Optimization, 2017.\n\n[8] Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d2: Decentralized training over decentralized data. In International Conference on Machine Learning, 2018b.\n\n[9] Thijs Vogels, Lie He, Anastasia Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. RelaySum for decentralized deep learning on heterogeneous data. In Advances in Neural Information Processing Systems, 2021.\n\n[10] Anastasia Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient  tracking for decen- tralized machine learning. In Advances in Neural Information Processing Systems, 2021.\n\n[11] Takezawa, Yuki, Han Bao, Kenta Niwa, Ryoma Sato, and Makoto Yamada. \"Momentum tracking: Momentum acceleration for decentralized deep learning on heterogeneous data.\" _arXiv preprint arXiv:2209.15505_ (2022).\n\n[12] Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtarik, and Yuejie Chi. Beer: Fast O(1/t) rate for decentralized nonconvex optimization with communication compression. In Advances in Neural Information Processing Systems, 2022.\n\n[13] Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In International Conference on Machine Learning, 2020.\n\n[14] Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear convergent decentralized opti- mization with compression. In International Conference on Learning Representations, 2021.\n\n[15] Yuki Takezawa, Kenta Niwa, and Makoto Yamada. Communication compression for decentralized learning with operator splitting methods. In arXiv, 2022a.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces and evaluates several novel decentralized learning algorithms, including NGCmv, NGCdv, and CompNGC, specifically tailored for a non-iid data distribution setting.\nUnder the standard assumptions for decentralized optimization (outlined in Assumptions 1-3), a convergence rate is provided for the smooth non-convex regime, expressed as:\n\n$$\\begin{aligned} \\frac{1}{K} \\sum_{k=0}^{K-1} \\mathbb{E}\\left[\\left\\|\\nabla \\mathcal{F}\\left(\\bar{x}_k\\right)\\right\\|^2\\right] \\leq & \\frac{1}{C_1 K}\\left(\\mathcal{F}\\left(\\bar{x}^0\\right)-\\mathcal{F}^*\\right)+\\left(10 C_2+10 C_3 \\frac{\\eta^2 \\beta^2}{(1-\\beta)^4}+4 C_4\\right)\\left(\\frac{\\sigma^2}{N}+\\zeta^2\\right)+ \\\\ & C_5 \\frac{14 \\eta^2\\left(\\sigma^2+\\zeta^2\\right)}{(1-\\beta)^2(1-\\sqrt{\\rho})^2},\\end{aligned}$$\n\nwhich, given specific choices for parameters $\\eta$ and $\\zeta^2$, can be simplified to:\n\n$\\frac{1}{K} \\sum_{k=0}^{K-1} \\mathbb{E}\\left[\\left\\|\\nabla \\mathcal{F}\\left(\\overline{\\mathbf{x}}_k\\right)\\right\\|^2\\right] \\leq C\\left(\\frac{1}{\\sqrt{N K}}+\\frac{1}{K}+\\frac{1}{K^{1.5}}\\right)$\n\n**Assumption 1 - Lipschitz Gradients:** Each function $f_i(x)$ is L-smooth.\n\n**Assumption 2 - Bounded Variance:** The variance of the stochastic gradients is assumed to be bounded.\n$$\n\\begin{gathered}\n\\mathbb{E}_{d \\sim D_i}\\left\\|\\nabla F_i(x ; d)-\\nabla f_i(x)\\right\\|^2 \\leq \\sigma^2 \\forall i \\in[1, N] \\\\\n\\left\\|\\nabla f_i(x)-\\nabla \\mathcal{F}(x)\\right\\|^2 \\leq \\zeta^2 \\forall i \\in[1, N]\n\\end{gathered}\n$$\n\n**Assumption 3 - Doubly Stochastic Mixing Matrix:** The mixing matrix $W$ is a real doubly stochastic matrix with $\\lambda_1(W)=1$ and\n\n$$\n\\max ( |\\lambda_2(W)| , |\\lambda_N(W)| ) \\leq \\sqrt{\\rho}<1\n$$\n\n\nThe paper's primary contribution is the NGC mechanism (an acronym for Neighborhood Gradient Clustering). NGC categorizes gradients at each decentralized agent into three distinct classes:\n\n1. **Self-gradients (local gradients)**: These are the derivatives computed locally at each agent based on its own dataset and model parameters.\n\n2. **Model-variant cross-gradients**: These gradients are calculated by taking the derivatives of the model parameters received from neighboring agents with respect to the agent's local dataset. This computation is done after the agent receives model parameters from its neighbors, a step common in gossip-based decentralized algorithms.\n\n3. **Data-variant cross-gradients**: These are computed by determining the derivatives of an agent's local model with respect to its neighbors' datasets. Getting these gradients requires an additional round of communication.\n\nThe NGC method then clusters these gradients into two groups:\n\na. **Model-variant cluster:** This merges the self-gradients and model-variant cross-gradients. \n\nb. **Data-variant cluster:** This group integrates the self-gradients and data-variant cross-gradients.\n\nThe ultimate aim is to to account for the high variation of local gradients across neighboring agents due to the non-IID data distribution. In NGCmv, the local gradients are substituted with the averages from the model-variant cluster. In NGdv, they are replaced with the averages from the data-variant cluster.\n\nFor experimental validation, the proposed methods (NGCmv, NGCdv, and CompNGC) are compared against established algorithms such as D-PSGD [1], CGA, and CompCGA [2] across a range of machine learning tasks.\n\n**References:** \n\n[1] Xiangru Lian, et al. _Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent_. Advances in Neural Information Processing Systems, 30, 2017. \n\n[2] Yasaman Esfandiari, et al. _Cross-gradient aggregation for decentralized learning from non-iid data_. In International Conference on Machine Learning, pp. 3036–3046. PMLR, 2021.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "1) Consider enhancing the literature review (according to the points listed in the Weaknesses section).\n\n2) Add the missing proofs.\n\n3) Conduct experimental comparisons with recent methods. One might look at the experimental setups from [11] and [12] for baseline methods.", "broader_impact_concerns": "This work is primarily theoretical. Hence, this work has no identifiable potential for negative societal impact.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "D9UnkRvljK", "reviewer": "Reviewer_FMV6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n===\n\nThis work nicely builds upon the work and setting of Esfandiari et al. (2021). It yields similar guarantees as the work of Esfandiari et al. (2021), using a similar set of assumptions, while requiring a much smaller computation time.\nThe overall claims seem sound.\nLastly, the experimental setup is quite extensive, illustrating the interest of $NGC$ algorithms on standard datasets.\n\nWeaknesses\n===\nFirst, it is unclear in several parts of the paper whether it is about the optimization aspect of $NGC$, or its generalization aspect. In particular, the theoretical part (Section 4) seems to solely focus on the optimization aspect (see for example Table 1); while the experiments (Section 5) focus on the validation loss. The gap between these two aspects does not seem to be mentioned once in the paper, and should be explored more vastly in my opinion. I indeed believe that the reason for the good empirical performance of $NGC$ might not be because it quickly converges towards some stable point, but rather because this convergence point has some nice property.\n\nApart from that, my other concerns are not only specific to this work but shared with Esfandiari et al. (2021) and concern the theoretical part. First, I find Theorem 1 poorly stated and hard to fully understand. I think it would require a rewriting and further discussion on its implication:\n - it seems that $C_1$ can be negative (or zero). Is there a condition on $\\beta$ to avoid this? (no condition on $\\beta$ is actually stated in the theorem)\n - it is not totally clear whether the constants $C_2,C_3,C_4,C_5$ become small when $\\eta$ is small (which I believe is the regime of interest). Indeed, the division by $C_1$ makes it unclear. Actually, I think more constants should be put into the variables $C_1,C_2,C_3,C_4,C_5$ to make the equation (11) clearer. \n\nFrom Theorem 1, the authors deduce Corollary 1, which I also find poorly stated. Is $C$ in Corollary 1 a universal constant or does it depend in some of the problem constants? In particular, the spectral gap $1-\\sqrt{\\rho}$ is often a quantity of interest in the convergence rate of decentralized optimization schemes. Does $C$ depend on this quantity?\nAlso, where does the assumption $\\zeta^2=\\mathcal{O}(1/\\sqrt{K})$ comes from? It seems very arbitrary to me, just because it yields some nice rate. Actually, I believe such an assumption is not verified in practice: such a small $\\zeta$ should actually correspond to (nearly) iid data between the users.\n\nSimilarly, the comparison in Table 1 is unclear: I believe some important quantities such as $\\rho, \\zeta$ are hidden here.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work studies decentralized optimization in the presence of non-iid data between the users. Following the lines of Esfandiari et al. (2021), it proposes a much more efficient way to aggregate the gradients of the neighbors (crossed gradients). While Esfandiari et al. (2021) aggregate through a hard to compute quadratic program, the algorithm presented in this work simply averages with the neighbors' gradients. From this idea, three different algorithms are proposed:\n - $NGC_{dv}$, for which the crossed gradients correspond to the gradient, with the local model and neighbors' data ($\\nabla f_j(x_i)$ where $j$ is the neighbor and $i$ is the agent)\n - $NGC_{mv}$, for which the crossed gradients correspond to the gradient, with neighbors' model and local data ($\\nabla f_i(x_j)$)\n - $CompNGC$ which is a corresponding version of $NGC_{dv}$ with compression of the sent information\n\nThe authors then yield a convergence rate of the optimization scheme, when following the algorithm $NGC_{dv}$. Finally, they compare the three proposed algorithms in an extensive numerical study with standard decentralized optimization algorithms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As explained above, I would like a clearer Theorem 1, as well as further explanations on it and Corollary 1. I would also like additional information in Table 1 (following all my remarks above).\n\nHere are some last remarks:\n - in the abstract \"without breaking the privacy constraints of the decentralized setting\". I would remove the word privacy here, as such phrasing is sometimes used (by non-experts) to claim that decentralized optim implies privacy, while the leakage of gradients and model parameters are clearly not guarantee of privacy\n - \"the word clustering is used as a synonym for grouping\": why not directly use grouping then?\n - At the beginning of Section 3.1 \"The flow of the neighborhood\". *Flow* is inappropriate here, as it also has a mathematical, different meaning in optimization\n - why using the star for scalar multiplication all along the paper?\n - you use cross gradients as either $g^{ij}$ or $g^{ji}$. Have you considered using the $g^{jj}$ terms instead? I believe this is a known algorithm\n - I do not understand the compression scheme in Algorithm 3. In particular, when reading line 6, I do not get why $\\delta$ could be sent as a single bit. It instead seems to be a (non binary) vector in $\\mathbb{R}^d$.", "broader_impact_concerns": "See my remark on the mention of privacy in the abstract", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers felt that the advancements over Esfandiari et al. (2021) were somewhat incremental, but they were unique. As such, we determined that the submission meets the TMLR acceptance standards.

### Minor revision
- Please note that the references are not only hard to distinguish from the text (as in "D-PSGD Lian et al. (2017), QG-DSGDm
Lin et al. (2021), Momentum Tracking Takezawa et al. (2022), and CGA Esfandiari et al. (2021)"), but also do not follow the TMLR style file (Section 4.1). Please update accordingly for the final version.

- Please (if possible) simplify the conditions on the stepsize (Equations (1), (2)). One of the reviewers pointed this out in the internal discussion.
Decision: Accept (poster)