Neighborhood Gradient Clustering: An Efficient Decentralized Learning Method for Non-IID Data Distributions
Authors: Sai Aparna Aketi
Sangamesh Kodge
Kaushik Roy
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Distributed Machine Learning
Decentralized Learning
Communication Efficient
Energy Efficient
Non-IID Data Distribution
Convergence

Abstract: Decentralized learning algorithms enable the training of deep learning models over large distributed datasets generated at different devices and locations, without the need for a central server. In practical scenarios, the distributed datasets can have significantly different data distributions across the agents. The current state-of-the-art decentralized algorithms mostly assume the data distributions to be Independent and Identically Distributed (IID). This paper focuses on improving decentralized learning over non-IID data distributions with minimal compute and memory overheads. We propose Neighborhood Gradient Clustering (NGC), a novel decentralized learning algorithm that modifies the local gradients of each agent using self- and cross-gradient information. Cross-gradients for a pair of neighboring agents are the derivatives of the model parameters of an agent with respect to the dataset of the other agent. In particular, the proposed method replaces the local gradients of the model with the weighted mean of the self-gradients, model-variant cross-gradients (derivatives of the received neighbors’ model parameters with respect to the local dataset - computed locally), and data-variant cross-gradients (derivatives of the local model with respect to its neighbors’ datasets - received through communication). The data-variant cross-gradients are aggregated through an additional communication round without breaking the privacy constraints of the decentralized setting. Further, we present CompNGC, a compressed version of NGC that reduces the communication overhead by $32 \times$ by compressing the cross-gradients. We demonstrate the empirical convergence and efficiency of the proposed technique over non-IID data distributions sampled from the CIFAR-10 dataset on various model architectures and graph topologies. Our experiments demonstrate that NGC and CompNGC outperform the existing state-of-the-art (SoTA) decentralized learning algorithm over non-IID data by $1-5\%$ with significantly less compute and memory requirements. Further, we also show that the proposed NGC method outperforms the baseline by $5-40\%$ with no additional communication. 

Under review as a conference paper at ICLR 2023
NEIGHBORHOOD GRADIENT CLUSTERING: AN EF- FICIENT DECENTRALIZED LEARNING METHOD FOR NON-IID DATA DISTRIBUTIONS
Anonymous authors Paper under double-bling review
ABSTRACT
Decentralized learning algorithms enable the training of deep learning models over large distributed datasets generated at different devices and locations, with- out the need for a central server. In practical scenarios, the distributed datasets can have significantly different data distributions across the agents. The current state-of-the-art decentralized algorithms mostly assume the data distributions to be Independent and Identically Distributed (IID). This paper focuses on improv- ing decentralized learning over non-IID data distributions with minimal compute and memory overheads. We propose Neighborhood Gradient Clustering (NGC), a novel decentralized learning algorithm that modifies the local gradients of each agent using self- and pross-gradient information. Cross-gradient for a pair of neighboring agents are the derivatives of the model parameters of an agent with re- spect the dataset the other agent. In particular, the proposed method replaces the local gradients of the model with the weighted mean of the self-gradients, -vaiin- cross- gradientssssss (derivatives of the received neighbors' model pa- rameters with respect to the local dataset computed locally), and data-vare variant cross-gradients (derivatives of the local model with respect to its neighbors' datasets received through communication). The data-variant cross pross-gradient are aggregated through an additional communication round without breaking the pri- vacy constraints of the decentralized setting. Further, present CompNGC, compressed version of NGC that reduces the communication overhead by 32x through cross pross-gradient compression. We demonstrate the efficiency of the pro- posed technique over non-lID data sampled from various vision and language datasets trained diverse model architectures, graph sizes and topologies. Our experiments demonstrate that NGC and CompNGC either remain competitive or outperform (by 6%) the existing state-of-the-art (SoTA) decentralized learn- ing algorithm over non-IID data with significantly less compute and memory re- quirements. Further, our experiments show that the model-variant cross- cross-gradiin gradientsss information available locally at each agent can improve the performance over non- IID data by 35% without any additional communication cost.
INTRODUCTION
The remarkable success of deep learning is mainly attributed to the availability of humongous amounts data and compute power. Large amounts of data is generated on daily basis different devices all over the world which could be used to train powerful deep learning models. Collect- ing such data for centralized processing is not practical because the communication and privacy constraints. To address this concern, new interest in developing distributed learning algorithms Agarwal & Duchi (001I) has emerged. Federated learning (centralized learning) Konečný et al. (2016) is a popular setting in the distributed machine learning paradigm, where the training data is kept locally at the edge devices and a global shared model learnt by aggregating the locally computed updates through coordinating central server. Such setup requires continuous commu- nication with a central server which becomes a potential bottleneck Haghighat et al. (2020). This has motivated the adyancements in decentralized machine learning.

---

Under review as a conference paper at ICLR 2023
Decentralized machine learning is branch of distributed learning which focuses on learning from data distributed across multiple agents/devices. Unlike Federated learning, these algorithms assume that the agents connected peer to peer without a central server. It has been demonstrated that decentralized learning algorithms Lian et al. (2017) can perform comparable to centralized algo- rithms benchmark vision datasets. [Lian al. (2117) 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 convergence rate of D-PSGD is similar to its centralized counterpart Dean et al. (2012). Balu et al. (202T) propose and analyze Decentral- ized Momentum Stochastic Gradient Descent (DMSGD) which introduces momentum to D-PSGD. Assran et al. (2019) introduce Stochastic Gradient Push (SGP) which extends D-PSGD to directed and time varying graphs. [Tang et al.] (2019); Koloskova et al. (2019) explore coroo-commenstteed compression techniques (Deep-Squeeze and CHOCO-SGD) to reduce the communication cost of P-DSGD significantly while achieving same convergence rate as centralized algorithmss Aketi et al. (02T combined Deep-Squeeze with SGP to propose communication efficient decentralized learn- ing over iime-narying and directed graphs. Recently, Koloskova et al. (2020) proposed a unified framework for the analysis of gossip based decentralized SGD methods and provide the best known convergence guarantees.
The key assumption to achieve state-of-the-art performance by all the above mentioned decentral- ized algorithms is that the data is independent and identically distributed (IID) across the agents. In particular, the data is assumed 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 agent are significantly different (non-IID) based on the user pool HHieh et al. (2020). The effect of non-III data in a peer-to- -eer- decentralized setup is relatively under-studied problem. There are only a few works that try to bridge the performance gap between IID and non-IID data distri- butions for decentralized setup. Note that, we mainly focus widely used in prior works TTag et al. (2018): Hsieh et al. (2020): Lin et al. 20 [sfandiari et al.) 20211;: skewed distribution of data labels across agents. Tang et al. (2018) proposed D= algorithm that extends D-PSGD to non-lID data distribution. However, the algorithm was demonstrated on only a basic LENET model and is not scalable to deeper models with normalization layers. Lin eet al. (202T) replace local momentum with Quasi-Global Momentum (QGM) and improve the test performance by 1 20%. But the improvement in accuracy is only 1 -2 in case of highly skewed data distribution as shown in Aketi et al. (2022). Most recently, Esfandiari et al. (2021) proposed Aggregation (CGA) and a compressed version of CGA (CompCGA), claiming state- of-the-an art performance for decentralized learning algorithms over completely pon-IID data. CGA aggregates cross- grasiegr information, i.e., 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. The pross-gradient and self-gradien terms are formally defined in Section 3 CGA and CompCGA require very slow quadratic programming step Gold-| farb & 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 decen- tralized learning over non-IID data with minimal compute and memory overhead?
common type of non-lID data,
In this paper, we propose Neighborhood Gradient Clustering (NGC) to handle non-llI data distri- butions in peer-to-peer decentralized learning setups. Firstly, we classify the gradients available at each agent into three types, namely self-gradients, model-variant cross-gradients, and lata-variant cross- pross-gradients (see Section(3) 33 The self-gradients (or local gradients) are the derivatives computed each agent on its model parameters with respect the local dataset. The model-variant cross- gradients are the derivatives of the received neighbors' model parameters with respect to the local dataset. These gradients are computed locally at each agent after receiving the neighbors' model pa- rameters. Communicating the neighbors' model parameters is a necessary step in any gossip based decentralized algorithm [ian et al. (2017). The data-variant cross- cross-gradee gradientss are the derivatives of the local model with respect to its neighbors' datasets. These gradients are obtained through an additional round of communication. We then cluster the gradients into a) model- variillvariant cluster with -ilf-gradients and model-variant cross- graddenrsdstts, and b) data- varia-v cluster with celf-gradients and data-variant cross-gradients. Finally, the local gradients are replaced with the weighted average of the cluster means. 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-IID nature of the data distribution.
2

---

Under review as a conference paper at ICLR 2023
The proposed technique has two rounds of communication every iteration to send model pa- rameters and data-variant coos-ggaddients which incurs 2x communication cost compared to tra- ditional decentralized algorithms (D-PSGD). To reduce the communication overhead, compressed version of NGC (CompNGC) by compressing the additional round of cross-gradient communication. Moreover, if the weight associated with dara-variant cluster is set then NGC does not require an additional round of communication. We validate the performance of proposed algorithm on CIFAR-I0 dataset over various model architectures and graph topologies. We compare the proposed algorithm with D-PSGD, CGA, and CompCGA and show that we can achieve superior performance over non- -on-IID data compared the current state-of-the-ans approach. We also report the order of communication, memory and compute overheads required for NGC and CGA compared to D-PSGD.
propose
Contributions: In summary, we make the following contributions.
We propose Neighborhood Gradient Clustering (NGC) for decentralized learning setting that utilizes self-gradients, model-variant cross-gradients and data-variant cross-gradients improve the learning over non-IID data distribution (label-wise skew) among agents.
We present compressed version of Neighborhood Gradient Clustering (CompNGC) that
reduces the additional round of cross cooss-gradients communication by 32x.
Our experiments show that the proposed method either outperforms by 0 6% or remains competitive with significantly less compute and memory requirements compared to current state-of-ther -ftth---th decentralized learning algorithm over non-IID data at iso-communication cost.
We also show that when the weight associated with dara-variant cross roos-ggrddeens is set to 0, .GC performs 35% better than D-PSGD without any communication overhead by utilizing locally available model-variant cross-gradient information.
2 BACKGROUND
In this section, we provide the background on decentralized learning algorithm with peer-to-peer connections.
The main goal of the decentralized machine learning is to learn a global model using the knowledge extracted from the locally generated and stored data samples across n edge devices/agents while maintaining the privacy constraints. In particular, we solve the optimization problem of minimizing global loss function fxx) distributed across agents as given in equation. Note that f, is local loss function (for example, cross entropy loss) defined in terms of the data sampled (d:) from the local dataset D, at agent with model parameters Ti.
min ((x) DERd
F(DD::)),
(1)
i=1
and Fi D.) = EdLED (d; Vi
This is typically achieved by combining local stochastic gradient descent Bottou (211 with global consensus based gossip averaging Xiao & Boyd (2004). The communication topology in this peer- to-peer setup is modeled as a graph G ([v), E) with edges {i,j} E E if and only if agents and j are connected by communication link exchanging the messages directly. We represent (ii) as the neighbors of including itself. It is assumed that the graph G is strongly connected with self loops i.e., there a path from every agent to every other agent. The adjacency matrix of the graph G' is referred that, weight 0 indicates the absence of a direct edge between the agents. We assume that the mixing matrix is doubly-stochastic and symmetric, similar to all previous works in decentralized learning. For example, in a undirected ring topology, Wiy = if j E {i (i- 1, 1). Further, the initial models and all the hyperparameters in appendix describes the flow of D-PSGD with momentum. The convergence of the Algorithm. assumes the data-distti across the agents be Independent and Identically Distributed (IID).
mixing matrix W where Wiy is the weight associated with the edge [i.j]. Note
synchronized in the beginning of the training. Algorithm.
3

---

Under review as a conference paper at ICLR 2023
3 NEIGHBORHOOD GRADIENT CLUSTERING
We propose the Neighborhood Gradient Clustering (NGC) algorithm and a compressed version of NGC which improve the performance of decentralized learning non-llD data distribution. NGC utilizes the concepts of self-gradient and cross-gradient [Esfandiari et al. (2021). The following are the definitions of self-gradient and cross-gradient.
Seff-Gradient: For an agent with the local dataset D; and model parameters T,, the self-gradient is the gradient of the loss function fa with respect to the model parameters 2;, evaluated on mini-batch d; sampled from dataset D;.
gh. - v=fi(d;;a))
(2)
Cross-Gradients For an agent i with model parameters x; connected to neighbor j that has lo- cal dataset Dj, the cross-gradient is the gradient of the loss function fy with respect to the model parameters 2;, evaluated on mini-batch d, sampled from dataset Dj.
gif V (dfz(d):z))
(3)
Note that the cross cross-gradient 9ij is computed on agent j using its local data after receiving the model parameters z; from its neighbouring agent and is then communicated to agent i.
3.1 THE NGC ALGORITHM
The flow of the Neighborhood Gradient Clustering (NGC) is shown in Algorithm. Land the form of the algorithm is similar D-PSGD Lian et al. 2017) presented in Algorithm.
Algorithm Neighborhood Gradient Clustering (NGC)
Input:
(0) learning rate 1) averaging rate % Each agent E [1, n] initializes model weights x.
mixing matrix W = [wgg]k,e],,.]] NGC mixing weight a, and lij are elements of identity matrix, (i) represents neighbors of including itself.
Each agent simultaneously implements the TRAIN() ) procedure
1. procedure TRAIN()
2. for (=0, I.....T do Dr
I/ sample data from training dataset // compute the local self-gradient I/ shares model parameters with neighbors N N(i)
4. Pu = v.fid a!)
SENDRECHIVE(Z.)
6.
for each neighbor j E (W(i) - do g/ = ((ff(())
compute neighbors' cross-gradients
8.
if a + 0 do SENDRECEIVE(SS)) end
I| share cross cross-gradin goasi-gradiens between and
10.
end
11.
12.
0
-1- a)
EjEN(O) Wij * 9). a ESEN() Waj oi
I/ modify local gradients
13.
of
30 (1-1)
// momentum step I/ update the model
14.
r. xt + vi
15.
r; (1+1) Fi
EjeN(o Izj) * wat
|/ gossip averaging step
end 17. return
The main contribution of the proposed NGC algorithm is the local gradient manipulation step (line 12 in Algorithm.] []). In the tt iteration of NGC, each agent calculates its self- -rffigradeett Ga. Then, agent i's model parameters are transmitted to other agents (j) in its neighborhood, and the re- spective cross-gradients are calculated by the neighbors and transmitted back agent i. At every iteration after the communication rounds, each agent i has access to self- aeff-gradeents (gx) and two sets of cross- graddengts 1) Model-variant cross grass-gaddents: The derivatives that computed locally using its local data on the neighbors' model parameters (gHz). 2) Data-vart variant cross- goass-gradeents: The derivatives (received through communication) of its model parameters the neighbors' dataset
4

---

Under review as a conference paper at ICLR 2023
(Gty). Note that each agent computes and transmits cross cross-gradients (gjz) that act model-variam cross- gooss-gradients for i and as data-variant cross peoss-gaddeets for j. We then cluster the gradients into two groups namely: a) Model-variant cluster {ojzV E .Vii)) that includes self-gradient and model- variant cross-graad wooss-gradients, and b) Data-variant cluster {giyV) E (N))) that includes self- grrddrrddittss and data-variant cross-grabd gooss-gradiens.. The local gradients at each agent replaced with the weighted average of the above defined cluster means as shown in Equation. 4 which assumes uniform mixing matrix (wij 1/m; m Wi)). The mean of model-variant cluster weighted by a) and the mean of data-variant cluster is weighed by where a E [0, 1] is a paramm-t referred as NGC mixing weight.
x. = (1 a)
Σ
93
+
a
- Σ
sh
m
JEN(
JEN(()
(4)
(a) Model-variant cluster mean
(b) Data-variant cluster mean
The motivation for this modification to reduce the variation of the computed local gradients across the agents. In IID settings, the local gradients should statistically resemble the cross gros--gradsens and hence simple gossip averaging is sufficient to reach convergence. However, in the non-llD case, the local gradients across the agents significantly different due the variation in datasets and hence the model parameters on which the gradients are computed. The proposed algorithm reduces this variation in the local-gradients
is equivalent adding two bias terms e and w with weights (1 - a)) and respectively as shown in Equation. 5
5 =1 - a)*
Σ (EN(()
(of - -bh
+
a
git
+
1
Σ
1
libe
jEN(()
9h a1
Σ
(0t: glill
+a
Σ JEN(
1
وواا
9
m
m
JEN(()
model variance bias e!
data variance bias w/
(5)
c Σ
V (vf(dt:a)) v=f(d;=
JEN(()
3 * Σ (v v=f(d;=
(note that f ft =f)=f)
JEN(()
The bias term e compensates for the difference in neighborhood's self-gradient caused due to variation in the model parameters across the neighbors. Whereas, the bias term w compensates for the difference in a neighborhood's d's self- ceff-gradients caused due to variation in the data distribution across the neighbors. We hypothesis and show through our experiments that addition of these bias terms to the local gradients improves the performance of decentralized learning over non-lID data by accelerating the global convergence. Note that we set a = 0 the NGC algorithm then it does not require an additional communication round (no communication overhead compared to D-PSGD).
3.2 THE COMPRESSED NGC ALGORITHM
The NGC algorithm at every iteration involves two-steps of communication with the neighbors: 1) communicate the model parameters, and 2) communicate the pross-gradients. This communi- cation overhead can be bottleneck in a resource-constrained environment. Hence we propose compressed version of NGC using Error Feedback SGD (EF-SGD) Karimireddy et al. (2019) to compress gradients. We compress the error-compensated self 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 (e); in the algo- rithm) added as feedback to the gradients in the next iteration before compression. The pseudo code for CompNGC is shown in Algorithm. 2
5

---

Under review as a conference paper at ICLR 2023
Algorithm 2 Compressed Neighborhood Gradient Clustering (CompNGC)
Each agent E [1, n| initializes model weights Ty dimension of the gradient d, mixing matrix W [e(j).) NGC mixing weight a, and lij are elements of n X n identity matrix.
Input:
(0) learning rate y, averaging rate 7
Each agent simultaneously implements the TRAIN( ) procedure 1. procedure TRAIN()
for t= 1..... T
do
d D.
I/ sample data from training dataset
4.
9 - =!)
compute the local self-gradients I/ error compensation for self self-gradde gradients I/ compress the compensated self-gradients // update the error variable share model parameters with neighbors N(i)
P ghi ei
6.
O =
7.
a pia 6%
SENDRECEIVE(22)
9.
for each neighbor j E {N(() if do
gf. V=I((d);))))
compute neighbors' cross-gradients |/ error compensation for cross-gradients
11.
P gi. + + " (Iesjall//dsggmpp)))
12.
50
I| compress the compensated cross-gradients // update the error variable
13.
++ p'j 5/
14.
if a + do
15.
SENDRECH)
share compressed cross-gradients between i and j
16.
end
17.
end
18.
0
(1 a)
EjEN() Wy * +6 + Eser(s) my oi
I/ modify local gradients
o 301 (t-1)
n
// momentum step
20.
2. xt vt
// update the model
2; (1+1) zt + EjEN(s 15) * xt
21.
I/ gossip averaging step
22.
end return
23.
4 EXPERIMENTS
In this section, we analyze the performance of the proposed NGC and CompNGC techniques and compare them with the baseline D-PSGD algorithm Lian al. (2017) and state-of-the-an CGA and CompCGA methods Esfandiari et al. (2021)
Experimental Setup:
The efficiency of the proposed method is demonstrated through our exper- iments on diverse set of datasets, model architectures, tasks, topologies and numbers of agents.
We present the analysis on (a) Datasets (Appendix [A.2]: vision datasets (CIFAR- 10, CIFAR-
100, Fashion MNIST and Imagenette Husain (2018) and language datasets (AGNews Zhang et al. (215 (b) Model architectures (Appendix A.3p. 5-layer CNN, VGG-11, ResNet-20, LeNet-5, MobileNet- ResNet-18, BERT mini and DistilBERT (c) Tasks: Image and Text Classification. (d) Topologies: Ring, Chain and Torus.
(e) Number of agents: varying from 4 to 20. Note that low resolution (32 x 32) images Imagenette dataset for the experiments in Table. The results for high resolution (224 x 224) Imagenette are presented in Table. 3 We consider an extreme case of non-IID IID distribution where no two neighboring agents have same class. This referred as complete label-wise skew or 100% label-wise non- non-IsDDess Hsich et al. (2020). In particular for 10-class dataset such as CIFAR-10- each agent in 5 agents system has data from 2 distinct classes, each agent in 10 agents system has data from an unique class. For a 20 agent system two agents that are maximally apart share the samples belonging to a class. We report the test 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.4 We compare the propose method with iso- communication baselines. The experiments NGC (a 0) are compared with D-PSGD, NGC with CGA, and CompNGC with CompCGA. The communication cost for each experiment this section presented in Appendix A.6

---

Under review as a conference paper at ICLR 2023
Results: We evaluate variants of NGC and CompNGC and compare them with respective baselines in Table. for training different models trained on CIFAR- 10 over various graph sizes and topolo- gies. We observe NGC with = 0 consistently outperforms D-PSGD for all models, graph sizes and topologies with a significant performance gain varying from 3 - -35% Our experiments show the superiority of NGC and CompNGC over CGA and CompCGA respectively. The performance gains are more pronounced when considering larger graphs (with 20 agents) and compact models such as ResNet-22. We further demonstrate the generalizability of the proposed method by evaluating on various image datasets such as Fashion MNIST, Imagenette and on challenging dataset such as CIFAR-108 100.R-00.T0 Table. show that NGC with a outperforms D-PSGD by 2 13% across various datasets where NGC and CompNGC remain competitive with an average improvement of ~ 1%. To show the effectiveness of the proposed method across different modalities, we present results on text classification task in Table E
We train on BERT mini model with AGNews dataset distributed over 4 and agents and a larger transformer model (DistilBerthase)) distributed over 4 agents. For NGC a 0 we for the text classification task, we observe NGC and CompNGC to be competitive with CGA and CompCGA methods. These observations
maximum improvement of 2.1% over the baseline D-PSGD algorithm. Even
consistent with the results the image classification tasks. Finally, through these exhaustive set of experiments, we demonstrate that the weighted av- eraging of data-variant and model-variant cross-gradients the performance of decentralized learning over label-wise non-IID data. Further, locally available model-variant cross- gradients information each agent can be efficiently utilized improve the decentralized learning with no communication overhead.
be served as a simple plugin boost
cross-gradients
Table 1: Average test accuracy comparisons for CIFAR- 10 with non-lID data using various archi- tectures and graph topologies. The results are averaged over three seeds where std is indicated.
Method
Agents
Slayer CNN Ring
5layer CNN Torus
VGG-11 Ring
ResNet-20 Ring
76.00 + 1.44
67.04 5.36
82.13 1 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
82.20 + 0.34
79.27 + 0.39
85.88 + 0.58
NGC (ours)
10
67.43 = 1.15
73.84 + 0.33
59.92 2.12
66.02 + 2.86
(a 0)
20
58.80 = 1.30
64.55 + 1.16
52.701 1.63
50.74 + 2.36
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
NGC (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
5
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
73.72 + 2.74
66.34 + 0.98
5
82.91 1 0.21
84.03 1 0.32
87.56 + 0.34
CompNGC (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
Analysis: We show the convergence characteristics of the proposed algorithm over IID and Non-IID data distributions Figure. Lal and respectiil. For Non-IID distribution, we observe that there is a slight difference in convergence (as expected) with slower rate for sparser topology (ring graph) compared denser counterpart (fully connected graph). Figure. Ic shows the comparison of the convergence characteristics of the NGC algorithm with the current state-of-the-art CGA algorithm. We observe that NGC has lower validation loss than CGA for same decentralized setup. Analysis for 10 agents is presented in Appendix A.5 The change in average validation accuracy with NGC mixing weight a is shown in Figure. 2 We observe that a close to has the best performance as the model variance bias is taken and data variance bias terms for both NGC and CGA techniques as shown in Figure. [3a and (3b
the gossip averaging step. We also plot the model variance
respectively. We observe that both the model variance and the data variance bias for NGC
7

---

Under review as a conference paper at ICLR 2023
Table Average accuracy comparisons for various datasets with non-IID sampling trained over undirected ring topology. The results are averaged over three seeds where std is indicated.
Method
Agents
Fashion MNIST (LeNet-5)
CIFAR-100 (ResNet-20)
Imagenette (MobileNet- V2)
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
NGC (ours)
88.49 0.18
55.96 + 0.95
60.15 2.17
(a (a=00 0)
10
82.85 + 0.24
35.34 + 0.32
36.13 + 1.97
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
90.61 0.18
56.50 + 3.23
74.49 1 0.93
NGC (ours)
10
87.24 + 0.23
53.77 + 0.15
64.06 + 1.11
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 1 0.48
72.91 1.06
CompNGC (ours)
10
83.38 + 0.39
43.07 = 0.32
61.91 - 2.10
Table 3: Average test accuracy comparisons for full resolution (224 x 224) Imagenette dataset with non-IID data trained on ResNet-18 over agents. The results are averaged over three seeds.
Method
Ring topology
Chain topology
D.PSGD
65.43 4.60
42.02 1.25
NGC a = 0 (ours)
73.15 + 0.38
47.87 + 0.99
CGA
85.00 = 0.67
65.96 1.84
NGC (ours)
85.85 + 0.60
67.77 + 1.76
CompCGA
84.65 + 0.57
62.93 + 1.33
CompNGC (ours)
85.44 0.10
62.64 = 0.85
significantly lower than CGA. This is because CGA gives more importance to self-gradients as it updates in the descent direction that is close to self- gradiensss and is positively correlated to data- variant cross- cross-gradiens gradients. contrast, NGC accounts for the biases directly and gives equal importance gradiess,,,,ss, thereby achieving superior performance.
to self-gradients and
2.25
1.2
2,00
ring colnecco
ngo
Validation Loss
1.1
colmecco
1.75
Validation 9
2.00
cps
1.0
Validation
1.50
0.9
1.50
0.8
1.25
1.25
0.7
1.00
0.8
0.75
0.75
0.5
0.50
0.50
60
120
180 Epochs
240
300
0
60
120
180
240
300
300
Epochs
Epochs
NGC method IID data.
(b) NGC method on Non-IID data.
(c) Different methods on Non-IID for ring topology.
Figure Average Validation loss during training of 5 agents on CIFAR-10 with layer CNN.
Hardware Benefits: The proposed NGC algorithm is superior in terms of memory and compute efficiency (see Table. 5). while having equal communication cost as compared to CGA. Since NGC involves weighted averaging, we do not need any additional buffer to store the cross-gradients. Weighted cross- pooss-gradient can be added to the the self self-gradient buffer. CGA stores all the cross- gradients in matrix form for quadratic programming projection of local gradient. Therefore, NGC has no memory overhead compared to the baseline D-PSGD algorithm, while CGA requires addi- tional memory equivalent the number of neighbors times model size. Moreover, the quadratic
8

---

Under review as a conference paper at ICLR 2023
Table 4: Average test accuracy comparisons for AGNews dataset with non-lID data trained over undirected ring topology. The results are averaged over three seeds where std is indicated.
Method
BERT
mini
DistilBERT base
Agents 4
Agents = 8
Agents 4
D-PSGD
89.21 + 0.41
85.48 + 0.71
91.54 + 0.07
NGC a = 0 (ours)
89.40 + 0.13
87.58 = 0.07
91.70 + 0.11
CGA
91.43 0.11
89.15 = 0.45
93.42 0.04
NGC (ours)
92.24 + 0.29
89.02 + 0.39
94.11 + 0.01
CompCGA
91.05 = 0.29
88.91 = 0.25
93.54 0.03
CompNGC (ours)
91.24 + 0.43
89.01 0.13
93.50 + 0.16
Validation Accuracy (%)
76
Moddel-Variancee Blas
0.010
nge
Data- Variaaciec Bias
ngc
75
0.016
74
73
0.030
0.012
72
0.025
71
0.020
70
0.008
69
0
120
240
300
120 180
240 300
Epochs
Epochs
0.00
0.25
0.50
0.75
1.00
Alpha
(a) Average Ll norm of
(b) Average Ll norm of w.
Figure 2: NGC mixing weight a Figure Average LI norm of model variance bias and data variation for 10 agents trained on ring graph with 5 layer CNN.
variance bias for 5 agents trained on ring graph with 5 layer CNN.
programming projection step Goldfarb & Idnani (1883 in CGA is much more expensive in terms of compute and latency as compared to weighted averaging step of goos-ggrddeets NGC. Our experiments clearly show NGC' is superior to CGA in terms of test accuracy, memory efficiency, compute efficiency and latency.
Table 5: Comparison of communication, memory and compute overheads per mini-batch compared D-PSGD. m,; model size, N;: number of neighbors, floating point precision, QP: compute for Quadratic Programming, FP: compute for Forward Pass. (see Appendix A.7 for more details)
Method
Comm. (m,,N) O M,N:
Memory ((Nams)
Compute
CGA
O(3N + QP)
CompCGA
((11 + Nom)))
O(3N, QP)
NGC = (ours)
O3N,FF + m,NN, O(3N 1 M,) O(3NFF Ni,N,)
NGC (ours)
Omm,N:) M.Ni
O
CompNGC (ours)
O(Na.))
5 CONCLUSION
Enabling decentralized training over non-lID data is key for ML applications to efficiently leverage humongous amounts of user-generated private data. this paper, we propose the Neighbor- hood Gradient Clustering (NGC) algorithm that improves decentralized learning over non-III IID data distributions. Further, we present a compressed version of our algorithm (CompNGC) to reduce the communication overhead associated with NGC. We validate the performance of the proposed techniques (NGC and CompNGC) over different model architectures, graph sizes and topologies. Finally, we compare the proposed algorithms with the current state-of-the-arn decentralized learning algorithm over non-IID data and show superior performance of our algorithm with significantly less compute and memory requirements.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal and John C Duchi. Distributed delayed stochastic optimization. Advances in neural information processing systems, 24, 2011.
Sai Aparn Aketi, Amandeep Singh, and Jan Rabaey. Sparse-push: Communication-& energy-
efficient decentralized distributed learning over directed & time-varying graphs with non-iid 2021.
datasets. arXiv preprint arXiv:2
Sai Aparna Aketi, Sangamesh Kodge, and Kaushik Roy. Low precision decentralized distributed training over iid and non-iid iid data. Neural Networks, 2022. ISSN 0893-6080. doi: https://doi.or org// n..1016f..eumee.2222.....88
Mahmoud Assran, Nicolas Loizou, 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. Decentralized deep learning using momentum-acced accellrrae consensus. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3675- 3679. IEEE, 2021.
Léon Bottou. Lcrge-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010 pp. 177-186. Springer. 2010.
Jeffrey Dean, Greg Corrado. Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in neural information processing systems, 25, 2012.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04880 2018.
Yasaman Esfandiari, Sin Yong Tan, Zhanhong Jiang, Aditya Balu, Ethan Herron, Chinmay Hegde, and Soumik Sarkar. Cross-gradient aggregation for decentralized learning from non-iid data. In International Conference on Machine Learning, pp. 3036-3046. PMLR, 2021.
Donald Goldfarb and Ashok Idnani. A numerically 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 Esfandi- ari, Saeed Arabi, and Anuj Sharma. Applications of deep learning in intelligent transportation systems. Journal of Big Data Analytics in Transportation, 2(2): 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016
Kevin Hsieh, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-IID data quagmire of decentralized 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 subset of 10 easily classified classes from the imagenet dataset. https://githhb.co https://gituub.comfffsttt cowfffsttai/mmageeeteet 2018.
Sai Praneeth 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, Sehastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv: 0et0:0900959500 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 Confer- ence on Machine Learning, pp. 5381-5399 PMLR,, 2020.
10

---

Under review as a conference paper at ICLR 2023
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. 2016.
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar (canadian institute for advanced research). http://www.cs.toromtt..ek edu/ kriz/cffar.tml, 2014.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11):2278-2322 1998.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Tao Lin, Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In Proceedings of the 38th In- ternational Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 6654-6665, PMLR, 18-24 Jul 2021.
Hanxiao Liu, Andy Brock, Karen Simonyan, and Quoe Le. Evolving normalization-activation lay- ers. In H. Larochelle, M. Ranzato, Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13539- 13550. Curran Associates, Inc., 2020.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and -tang-Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 4510-4520, 2018.
Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. Distilbert, a distilled version of bert: smaller, faster, cheaper and lighter. arXiv preprint arXiv: 1910.01 108, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint ArXivv1409.155: 2014.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d: Decentralized training decentralized data. In International Conference on Machine Learning, pp. 4848-4856. PMLR, 2018.
Hanlin Tang, Xiangru Lian, Shuang Qiu, Lei Yuan, Ce Zhang, Tong Zhang, and Ji Liu. Deepsqueeze: Decentralization meets error-compensated compression. arXiv preprint arXiv: 10XX:v:907007366 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
Xiang Zhang. Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. Advances in neural information processing systems, 28, 2015.

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 DECENTRALIZED LEARNING SETUP
The traditional decentralized learning algorithm (d-psgd) described Algorithm. For the decentralized setup, we use undirected ring and undirected torus graph topologies with uniform mixing matrix. The undirected ring topology for any graph-size has 3 peers per agent including itself and each edge has weight of 3' The undirected torus topology with 10 agents has 4 peers per agent including itself and each edge has weight of }. The undirected torus topology 20 agents has 5 peers per agent including itself and each edge has weight of 5
Algorithm 3 Decentralized Peer-to-Peet Training (D-PSGD with momentum)
(0) learning rate 1), averaging rate % Input: Each agent E [1, n] initializes model weights z; mixing matrix W [w.,]kje(L..)) and lij are elements of identity matrix.
Each agent simultaneously implements the TRAIN( procedure procedure TRAIN(
1.
for t=0 1.... T do
3.
d D;
II sample data from training dataset. Il compute the local gradients
9
V (e;
5.
Bul (1-1) no!
// momentum step update the model I1 share model parameters with neighbors (1).
o = xt o
7.
SENDRECEIVE(2))
x (t-1) 7 + EsEN(O -1s) * x3
I/ gossip averaging step
9.
end return
10.
We highlight the various assumptions required for the convergence of the proposed NGC and Comp- NGC algorithm.
The graph topology of the agents strongly connected and symmetric. 2. Doubly stochastic mixing matrix: The mixing matrix W is real doubly stochastic matrix i.e. 1' W1 = W, where 1 is the vector of all 1's.
1. Graph Structure:
Lipsehitz Gradients: Local loss functions fi(.) has L-lipschitz gradients for all i [1,m] i.e. [1] [x(1) L|| vll Va,, E IRd
4. Bounded Variance: The variance of the stochastic gradients are assumed to be bounded. Ed.D. f d.) [2) < o², (Inner variance).
E [z)((z - V f(=)]l < ? Vi, x (Outer variance).
5. Initialization: The model parameters on all the agents are initialized to the same random values.
It may be noted that assumptions 1-5 are similar to that of CGA algorithm Esfandiari et al. (2021) and are commonly used in most decentralized training algorithms.
A.2 DATASETS
In this section, we give brief description of the datasets used in our experiments. We use diverse set of datasets each originating from different distribution of images to show the generalizability of the proposed techniques.
CIFAR-10: CIFAR-IO Krizhevsky et al. (2014) is a image classification dataset with 10 classes.
The image samples colored (3 input channels) and have resolution of 32 32. There 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. (2014) is a image classification dataset with 100 classes. The image samples colored (3 input channels) and have resolution of 32 32. There are 50, 000
12

---

Under review as a conference paper at ICLR 2023
training samples with 500 samples per class and 10, 000 test samples with 100 samples per class. CIFAR- 1-0 classification is harder task compared to CIFAR-10 as it has 100 classes with very less samples per class to learn from.
Fashion MNISTXias et al. (017) is image classification dataset with 10 classes. The image samples are in grey scale (1 input channel) and have resolution of 28 x 28. There 60, 000 training samples with 6000 samples per class and 10, 000 test samples with 1000 samples per class.
Fashion MNIST:
Imagenette: Imagenette Husain 2018) is a 10 class subset of the ImageNet dataset. The image samples in colored (3 input channel) and have resolution of 224 x 224. There 9469 training samples with roughly 950 samples per class and 3925 test samples. We conduct our experiments on two different resolutions of Imagenette dataset a) resized low resolution of 32 32 and, full resolution of 224 x 224. The Imagenette experiments reported in Table. use the low resolution images where as experiments in Table. use the full resolution images.
We use AGNews Zhang et al. (015)) 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 total of 120000 and 7600 samples for training and testing respectively, which are equally distributed across each class.
AGNews:
A.3 NETWORK ARCHITECTURE
We replace ReLU+BatchNorm layers of all the model architectures with EvoNorm-SD Liu et al. 2020) it was shown to be better suited for decentralized learning over non-IID distributions Lin et al. (202)).
5 layer CNN: The 5 layer CNN consists of 4 convolutional with EvoNorm-SD Liu al. (2020) as intivation-nommalizann
layer, max pooling layer and one linear layer. In particular, has convolutional layers with 32 filters, a max pooling layer, then 2 more convolutional layers with 64 filters each followed by another max pooling layer and a dense layer with 512 units. It has a total of 76K trainable parameters.
VGG-11:
We modify the standard VGG-1 Simonyan & Zisserman (0144) architecture by reducing
the number of filters each convolutional layer by 4x and use only one dense layer with 128 units. Each convolutional layer is followed by EvoNorm-St as iitivationnnommlizatiii layer and it has 0.58M trainable parameters.
ResNet-20: For ResNet-20 He et al. parameters except that BatchNorm+RRLJU layers are replaced by EvoNorm-SO.
2016 we use the standard architecture with 0.27M trainable
LeNet-5: For LeNet-5 LeCun et al. 1998 we use the standard architecture with 61, 706 trainable parameters.
We use the the standard MobileNet-Ve V2 Sandler et al. (2018) architecture used for CIFAR dataset with 2.3M parameters except that BatchNorm+RRLU layers are replaced by EvoNorm-SO.
MobileNet-V22
ResNet-18: For ResNet- 18 He et al. (0016), we use the standard architecture with 1 trainable parameters except that -atchNorm+ ReI.U layers are replaced by EvoNorm-SO.
BERT mini: For BERT mini Devlin et al. (018) 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 parameters.
DistilBERT h DistilBERT have Sanh et al. 2019) 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 66.67M parameters.
A.4 HYPER- PARMMEERR
All the experiments were run for three randomly chosen seeds. We decay the learning-rate rate by 10x after 50% and 75% of the training, unless mentioned otherwise.
13

---

Under review as a conference paper at ICLR 2023
Table 6: Hypeer-aaaaeteess used for CIFAR-10 with non-IID data distribution using 5-layer CNN model architecture presented in Table 1
Agents
Ring
Torus (a. B. n. 2
Method
(n)
(a. 5, ?)
(- 0.0, 0.1,
D-PSGD
10
0.1, (-, 0.0,0.
(-0.00 0.0, 0.1, 1.0) 0.0, (.0.0,
20
0.1,1.0) 1.0)
(0.0, 0.0, 0.0,
NGC (ours)
10
0..1
(0.0, 0.0, 0.1,
(a= 0)
20
(0.0,0.0,0.111.0))
(0.0, 0.0, 0.1,
5
(-,0.9,0.01.0.1)
CGA
10
(=.0.9,.001.0.5)
20
(..0...0.01.003)
(-, (-.0990001..011
5
0..00.
NGC (ours)
10
0.0,0.9,0001,0.3
(1.0, 0.010.
20
(..0,..,..01,..5)
0.9,0.9.0001.00
(-,0.9,0.01.0.))
CompCGA
10
0..00..0.01.005)
(-,0990.01,0..1
20
(=.0.9,0.01.0.))
0..00.0.011.0.1
0.0,0,9,0011,00.
CompNGC (ours)
10
(1.0, 0.9, 0.0....)
L.0,0.9.0001.0. 1.0.0.9.0001.00
20
(1.0, 0.9, 0.51
Table 7: Hyper-parameters used for CIFAR-I0 with non-IID data distribution using ResNet and VGG-11 model architecture presented in Table
Agents
VGG-IT
ResNet
Method
(n)
(a, B, m)
(a,, B, m. ?
5
0.0,0.
(-,0000.1, 1.0)
D-PSGD
10
(-, 0.0,
0-,000,0.1,1.00
20
(=,0.0,0.01,,10
(-,0.0,0.1,..0)
00.0,0.0,011,1.00
NGC (ours)
10
00.0,..0,000111..0
(0.0,0.0,0.11100))
(a = 0)
(0.0,0.0,0.1,100)))
0.9.00..1,0055
(-,0.9,0.1,1.0)
CGA
10
(- 0...0...110055
1.0.).
20
0.0..,0.110055
(-,0.9,0.1,
5
0...0.9,0.1.003))
0.01
NGC (ours)
0.0.0.990.11005.)
(1.0,0.9...1, 1.0)
20
01.0,..9..1....))
(1.0,0.9,0.11110)))
5
0,0.9)0.01.0.11
0.00,,..011,00)
CompCGA
10
0..0..0001.0..1)
0.0000..011)01)
20
0-.0.0.0.01.0.))
0.0.0.0001
0.9,0.9,0001,,
(1.0,09,..0110...
CompNGC (ours)
10
0.9, 0.10
(1.0,.9.0.00.0..)
20
0.9,0.990.01..00. 0.01.
(1.0.0.9.0.01.00.
Hyper-parameters for CIFAR-10 on 5 layer CNN: All the experiments that involve 5layer CNN model (Table. [I) have stopping criteria set to 100 epochs. We decay the learning rate by 10x in multiple steps 50th and 75th epoch. Table 6 presents the a, 3, 77, and corresponding to the nge mixing weight, momentum, learning-rate and gossip averaging rate. For all the experiments, we use mini-batch size of 32 per agent. The stopping criteria is fixed number of epochs. We have used Nesterov momentum of 0.9 for all CGA and NGC experiments where as D-PSGD and NGC with has no momentum.
14

---

Under review as a conference paper at ICLR 2023
Hyper-parameters for CIFAR-10 on VGG-11 and ResNet-20: All the experiments for CIFAR-10
dataset trained on VGG-11 and ResNet-20 architectures (Table. 1 have stopping criteria set to 200 epochs. We decay the learning rate by 10x in multiple steps 100th and 150th epoch. Table 7 presents the o, 8, and 7y corresponding to the nge mixing weight, momentum, learning-rate and gossip averaging rate. For all the experiments,
mini-batch size of 32 per agent.
Hyper-parameeerss used for Table. 2 All the experiments in Table. 2 have stopping criteria set 100 epochs. We decay the learning rate by 10x in a multiple steps 50th and 75 epoch. Table 8 presents the o, B. 7,, and 7 corresponding to the nge mixing weight, momentum, learning- rate and gossip averaging rate. For all the experiments related to Fashion MNIST and Imagenette (low resolution of (32 x 32)), we use mini batch size of 32 per agent. For all the experiments related CIFAR-I01 100, we use mini-batch size of 20 per agent.
Table 8: Hyper-parameters used for Table.
Agents
Fashion MNIST
CIFAR-100
Imagenette
Method D>PSGD
(n)
(a, B, n). ?)
(a, B. 17.
(a, B. n,, ?)
5
0.01,
(-, 0,0,000.11110)
0.0,
(-, 0.0, 1.0)
(-,0.0,0.1,1.00
0.00000.1,1100)
NGC (ours)
5
0.01, 1.00
(..0,0.0,0111110))
0.00000.111100
(a = 0)
10
0,0,0,0000011,1.00
(0.0,0.0,0.1,100)
(,0000,0.1,100
CGA
5
(-,0.9,0.01,1.0
(-,0.9,0.1,100)
00.0,0.0,0.01,.55)
10
(=,0.9,0.01,1.00
(-.0.9,0.1,055)
(0.0.....0.01..555)
NGC (ours)
5
(1.0, 0.9,0
(.0,0.9,0.1,1..0)
00.0,0.0,0.01.02.
10
(..0,.99...01,..
(..0,).9,0111055)
00.00......01.0..5)
CompCGA
5
(-, 0.000,000,
(- 0,0.9,0.01,0.1.
(0.0,0.0,0.01.0..)
(-, 0.9, 0.11,
(-,0.9. 0.01
(0.0,
CompNGC (ours)
5
(1.0, 0.9,0.9,0.011,000
(1.0,0.9,0001..0)
00.0,0.0,0.01,00. 00.0,0.0,0.01...55
10
(1.0, 0.000.
(1.0,0.9,0.01.0.1 0.1)
used for Table. 3 All the experiments in Table. have stopping criteria set to 100 epochs. We decay the learning rate by 10x at 50th 75th epoch. Table 9 and 7 corresponding to the nge mixing weight, momentum, learning-rate and gossip averaging rate. For all the experiments, we use a mini-batch size of 32 per agent.
presents the a, B, n7.
Table 9:
used for Table, 3
Ring topology (a, 3, m, 7)
Chain topology
Method
(a, B, 17. 7)
D-PSGD
(=,0.0,0.01, 1.0)
0.,0.0,00 0.01, 1.0)
NGC 0 (ours)
00.0,0.0,0.01,1..0 1.00)
CGA
(-, 0.0..
(-,0.9, 0.01,00.)
NGC
0.9,
(1.0,..9.0.01...1
CompCGA
(-,0.9, 0.0.0.00 (1.0,0.9.0.01,000 0..00.....001...1)
(5.0.9,0.01.0.1
CompNGC
Hlpper-parameters used for Table. 4 All the experiments in Table. 4 have stopping criteria set to 3 epochs. We decay the learning rate by 10x at 2nd epoch. Table presents the a, 3, 7), and r corresponding to the nge mixing weight, momentum, learning-rate and gossip averaging rate. For all the experiments, we use a mini-batch size of 32 per agent on AGNews dataset.
for Figures: The simulations for all the figures are run for 300 epochs. We scale the learning-raid rate by a factor or 0.981 after each epoch to obtain smoother curve. All the experiment in Figure I | and use 5 layer CNN network. Experiments in Figure I and use 5 agents while the experiments Figure 2 E and 5 use 10 agents. The hyper- apper--arameters for the
simulations for all the plots mentioned in Table 11
15

---

Under review as a conference paper at ICLR 2023
Table 10: Hyper-parametee used for Table.
BERT mini
DistilBERT base
Method
Agents 4
Agents
Agents 4
(a, [3, 7)
(a, 5, 17, 7)
(a, 3, 17. ?)
D-PSGI
0.0, 0.01, 1.0)
(-,0.0 0.01, 1.0)
(- 0.000. 0.01, 1.0)
NGC a = (ours)
(0.0, 0.01,
00.0,0.0, 0.01,,
(0.0, 00.0,0.000001,100)
CGA
(-,0.9, 0.01,
0.,0,,,0011,03
NGC
(1.0, 0.01,0.5)
0.900.9.0.01..3 0..0,..,,0001.355
CompCGA
0..0.9.0001.03
(=,0.9,0.01.0.5)
CompNGC
0.900.9.0.011,1
(1.0,0.9,0.01...3.
(1.0, 0...0.0.0)11
Table 11: Slpeer-pramettes used for Figures
3
and
Figure
3
17
la
skew=O, NGC)
1.0
0.9
0.01
1.0
lb
(skew=1, NGC)
1.0
0.9
0.01
0.1
Lonand
(skew=1, ring topology)
0.9
0.01
0.1
0.0
1.0
(skew=1,NCr
0.25
1.0
ring topology
0.5
0.9
0.01
0.5
0.75
0.5
1.0
0.25
4a
skew=0, NGC)
1.0
0.9
0.1
1.0
4b
skew=1, NGC)
1.0
0.9
0.1
0.5
4c (skew=], ring topology)
1.0
0.9
0.1
0.5
A.5 ANALYSIS 10 AGENTS
We show the convergence characteristics of the proposed NGC algorithm over IID and Non-IID data sampled from CIFAR-10 dataset in Figure. 4a| and respectively. For Non-IID distribution. we observe that there 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. 4c shows the comparison of the convergence characteristics of the NGC technique with the current -fate-of-the-art CGA algorithm. We observe that NGC has lower validation loss than CGA for same decentralized setup indicating its superior performance over CGA. We also plot the model variance and data variance bias terms for both NGC and CGA techniques as shown in Figure. 5a and 5b respectively. observe that both model variance and data variance bias for NGC are significanlly lower than CGA.
2.00
ring
ring connected
Validation Loss
fully conmected
Validation Loss
Validation Loss
cga
1.50
1.25
w
0.75
0.50
2
60
120
180 Epochs
240
300
60
120
180
240
300
60
120
180
240
300
Epochs
Epochs
(a) NGC method IID data.
(b) NGC method on Non-IID data.
(c) Different methods Non-IID for ring topology.
Figure 4: Average Validation loss during training of 10 agents CIFAR-10 dataset with 5 layer CNN network.
16

---

Under review as a conference paper at ICLR 2023
Model-Variance Bias
0.016
ngc
0.025
ngc
Data-Variance Bias
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 Epochs
240
300
(a) Average Ll norm of
(b) Average L1 norm of
Figure 5: Average LI norm of model variance bias and data variance bias for 10 agents trained on CIFAR-10 dataset with 5 layer CNN architecture over an undirected ring topology.
A.6 COMMUNICATION COST:
In this section we present the communication cost per agent in terms of Gigabytes of data trans- ferred during the entire training process (refer Tables. 12
15 14). The D-PSGD and NGC with a = 0 have the lowest communication cost (1x). We emphasize that NGC with a = out- performs D-PSGD in decentralized learning over label-wise non-III data for same communication cost. NGC and CGA have x communication overhead compared to D-PSGD where as CompNGC and CompCGA have 1.03x communication overhead compared to D-PSGD. The compressed ver- sion of NGC and CGA compresses the second round of cross-gradien communication to I bit. We assume the full cell-precision gross-gradient to be of 32-bit precision and hence the CompNGC reduces the communication cost by 32 compared to NGC.
I3
Table 12: Communication costs per agent in GBs for experiments in Table
Method
Agents
Slayer CNN
Slayer CNN Torus
VGG-11
ResNet-20 Ring
Ring
Ring
D-PSGD
5
17.75
270.64
127.19
and
10
8.92
13.38
135.86
63.84
NGC
20
4.50
68.48
32.18
CGA
5
35.48
541.05
254.27
and
17.81
26.72
271.50
127.59
NGC
20
8.98
17.95
136.72
64.25
CompCGA
5
18.31
279.09
131.16
and
10
9.20
13.79
140.10
65,84
CompNGC
20
4.64
9.28
70.61
33.18
A.7 RESOURCE COMPARISON
The communication cost, memory overhead and compute overhead for various decentralized algo- rithms are shown in Table. 5 The D-PSGD algorithm requires each agent to communicate model parameters of size m, with all the N, neighbors for the gossip averaging step and hence has com- munication cost of Omm,N,). In case of NGC and CGA, there is additional communication round for sharing data-variant cross gradients apart from sharing model parameters for gossip averaging step. So, both these techniques incur communication cost of ((2m,N.) and therefor overhead of N;) compared to D-PSGD. CompNGC compresses the additional round of communication involved with NGC from bits bit. This reduces the communication overhead from O(m,N.)
O
17

---

Under review as a conference paper at ICLR 2023
Table 13: Communication costs per agent in GBs for experiments in Table
Method
Agents
Fashion MNIST
CIFAR-I00 (ResNet-20)
Imagenette (MobileNet- V2)
(LeNet-5)
D-PSGID and
5
17.25
103.74
103.
NGC
10
8.61
51.89
51.60
CGA and
5
34.50
207.47
206.23
NGC (ours)
10
17.23
103.79
103.19
CompCGA and
5
17.79
106.98
106.34
CompNGC (ours)
10
8.88
53.52
53.21
Table 14: Communication costs per agent in GBs for experiments in Table
Method
Ring topology
chain topology
D-PSGD and
501.98
401.59
NGC a =
CGA and
1003.96
803.17
NGC
CompCGA and CompNGC
517.67
414.14
CGA algorithm stores all the received data-variant cross-gradients in the form of a matrix for quadratic projection step. Hence, CGA has memory overhead of O(m,N:) compared D- PSGD. NGC does not require any additional memory as it averages the received data-variant cross- gradients into self-grate celf-gradient buffer. The compressed version of NGC requires additional memory of NM) to store the eтror variables ej (refer Algorith. 2 CompCGA also needs to store error variables along with the projection matrix of compressed gradients. Therefore, CompCGA has memory overhead of Om,,N; + Nz ). Note that memory overhead depends on the type of graph topology and model architecture but not on the size of the graph. The memory overhead for different model architectures trained on undirected ring topology is shown in Table. [6
The computation of the cross- coss-gradients (in both CGA and NGC algorithms) requires N₂ forward and backward passes through the deep learning model at each agent. This is reflected as (3NN,FP) in the compute overhead in Table. [5] We assume that the compute effort required for the backward pass is twice that of the forward pass CGA algorithm involves quadratic programming projec- tion step Goldfarb & Idnani (1983) to update the local gradients. Quadratic programming solver (quadprog) uses Goldfarb/ldnani dual algorithm. CGA uses quadratic programming to solve the fol- lowing (Equation[]-see -see Equation 5a in Eslandiari et al. (202T) optimization problem in iterative manner:
GG ut ttgg G
min
2 u
(6)
s.t.
u20
Table 15: Communication costs per agent in GBs for experiments in Table
Method
BERT mini
DistilBERT base Agents =
Agents 4
Agents =
D-PSGD and
234.30
118.20
1410.39
NGC a =
CGA and
486.59
236.40
2820.77
NGC
CompCGA and
241.6
121.89
1454.46
CompNGC
18

---

Under review as a conference paper at ICLR 2023
Table 16: Memory overheads for various methods trained on different model architectures with
CIFAR-10 10 dataset over undirected ring topology with 2 neighbors per agent.
Architecture
CGA (MB)
NGC
CompCGA
CompNGC
(MB)
(MB)
(MB)
layer CNN
0.38
0.58
0.60
VGG-11
4.42
0
4.42
4.56
ResNet-20
2.28
2.28
2.15
where, G is the matrix containing cross-gradients, the self-gradient and the optimal gradient direction g" terms the optimal solution of the above equation u" is g" = GT + g. The above optimization takes multiple iterations which results in compute and time complexity to be of polynomial(degree> 2) order. contrast, NGC involves simple averaging step that requires Omm,N,) addition operations.
19


Reviews:
[{"review_id": "y0N6pfW0CIW", "reviewer": "Reviewer_b2jc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a new decentralized learning algorithm that bases on the proposed cross gradient aggregation (CGA) algorithm. Specifically, the authors leverage the existing self-gradient and cross-gradient concepts to develop the neighborhood gradient clustering (NGC) algorithm. This proposed method replaces the local gradients of the model with the weighted mean of the self-gradients, model-variant cross-gradients, and data-variant cross-gradients, which is better able to handle the parameter variations in non-IID scenarios. To reduce the communication bottleneck, the authors develop the compressed version of NGC, CompNGC. To validate both algorithms, the authors utilize a benchmark dataset with various model architectures and the results show the superiority of the proposed algorithms.", "summary_of_the_review": "This paper presents a new decentralized learning algorithm called NGC to cope with the issues in decentralized learning settings. The authors provide algorithm design and empirical evidence to show case the superiority. This work seems incremental, failing to providing good novelties. The authors should analyze the proposed algorithms theoretically and present more experimental result to validate.", "strength_and_weaknesses": "Strength: this paper presents a novel algorithm on top of an existing one and shows the better model performance compared to the existing baseline. The investigated topic is quite interesting as non-IID remains a challenging problem in the decentralized learning area. The paper is easy to follow and the presentation is clear.\n\nWeaknesses: the novelty in this work is quite marginal. It looks the only novelty is to replace the gradient calculation step in CGA with the weighted mean of self-gradients, model-variant cross-gradients, and data-variant cross-gradients. Such a change is just a minor incremental work, which fails to provide sufficient contributions. Also, concepts are just based on the existing works. Given this, if the authors could provide detailed theoretical analysis on NGC and CompNGC, that may make this paper technically solid and sound. However, the authors only provide empirical results, which to me is not promising as well. If this paper is posited as an applied paper, then comprehensive results are necessarily required, including diverse model architectures, datasets, tasks, topologies and numbers of agents. Through these, if NGC and CompNGC remain competitive and outperform baselines, then the work will look very technically solid and sound. However, the existing experimental results to me are not very comprehensive and promising. \n\n*******************************Post-rebuttal************************************\nI appreciate the detailed response and additional results in the revised paper from the authors. After carefully reviewing the responses, I think the additional results have made the work better. However, the overall novelties in this work is still low to me and it still has much room for improvement in terms of theory. Though I would raise my score given the much better empirical evidences for the proposed algorithm in the revised version, the paper with the current form is still marginally below the acceptance standard. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "_tr9Zlred4", "reviewer": "Reviewer_y4qJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a new algorithm that utilizes groups of stochastic gradients collected from neighborhood nodes in a decentralized learning environment with heterogeneous data distributed in different locations. The proposed algorithm is communication efficient and achieves better empirical performance on non-IID data sampled from the CIFAR-10 Dataset.", "summary_of_the_review": "The paper is very well written but the supporting evidence for the model performance is not sufficient.", "strength_and_weaknesses": "Strength: the paper is quite well-written and easy to follow.\nWeakness: the working mechanism of the proposed method is not fully demonstrated. Other than the empirical performance on a benchmark data set, it is not clear to me why this method work or under what circumstances the proposed method will work best.\n\n1. The paper has emphasized the concept of \"non-IID\" data. But what types of data can this method handle? It would be very ambitious to claim that it will work for any type of setting. So it is necessary to clarify or at least give some concrete examples of the non-IID data types under consideration.\n\n2. What types of models are most suited for the proposed method? Regression problems? Classification problems? or other tasks? Different models have very different structures on the gradients and one needs to be more specific.\n\n3. The term \"clustering\" in the title implies some sort of unsupervised learning algorithms which I do not see in the paper.  To the best of my understanding, the paper seems to assume that the data distributions among the neighboring nodes are somehow \"homogeneous\". Otherwise, I do not understand why taking a weighted average of a bunch of inhomogeneous gradients will help improve the model's performance.  Please clarify.\n\n4. Since there are no theoretical justifications for the proposed method, I think carefully designed synthetic experiments are necessary to study the advantages and limitations of the proposed method. Otherwise, I have little confidence in the generalizability of the method.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KNlfeQ20fRx", "reviewer": "Reviewer_LFjx", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the decentralized distributed training under the non-iid data distribution setting. Different from the baseline method D-PSGD, it leverages self- and cross-gradient information to modify the gradient update for each agent. ", "summary_of_the_review": "The paper proposed an interesting method for decentralized learning but it has several weaknesses. ", "strength_and_weaknesses": "Strength\n1. The motivation of this paper is clear and interesting.\n2. The proposed method looks reasonable.\n3. Experiments have some promising results.\n\nWeaknesses\n1. As pointed out in Introduction section, the idea of leveraging cross-gradient information has already been used in Esfandiari et al. (2021). Therefore, the novelty of this paper is limited in this sense.\n2. It would be great to include some convergence analysis in this paper. Many decentralized learning methods have convergence analysis, such as D-PSGD. Actually, Esfandiari et al. (2021) which also uses cross-gradient information, has convergence analysis as well.\n3. The experiments are only conducted on one dataset, i.e., CIFAR10. It’s better to use more datasets. Decentralized learning algorithms are particularly useful for training large models on large distributed datasets. The authors are encouraged to use large datasets (such as ImageNet).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject