Momentum Tracking: Momentum Acceleration for Decentralized Deep Learning on Heterogeneous Data
Authors: Yuki Takezawa
Han Bao
Kenta Niwa
Ryoma Sato
Makoto Yamada
Venue: Accepted by TMLR ()

Abstract: SGD with momentum is one of the key components for improving the performance of neural networks. For decentralized learning, a straightforward approach using momentum is Distributed SGD (DSGD) with momentum (DSGDm). However, DSGDm performs worse than DSGD when the data distributions are statistically heterogeneous. Recently, several studies have addressed this issue and proposed methods with momentum that are more robust to data heterogeneity than DSGDm, although their convergence rates remain dependent on data heterogeneity and deteriorate when the data distributions are heterogeneous. In this study, we propose Momentum Tracking, which is a method with momentum whose convergence rate is proven to be independent of data heterogeneity. More specifically, we analyze the convergence rate of Momentum Tracking in the setting where the objective function is non-convex and the stochastic gradient is used. Then, we identify that it is independent of data heterogeneity for any momentum coefficient $\beta \in [0, 1)$. Through experiments, we demonstrate that Momentum Tracking is more robust to data heterogeneity than the existing decentralized learning methods with momentum and can consistently outperform these existing methods when the data distributions are heterogeneous.

Published in Transactions on Machine Learning Research (9/2023)
Momentum Tracking: Momentum Acceleration for Decen- tralized Deep Learning on Heterogeneous Data
Yuki Takezawa Kyoto University, Okinawa Institute of Science and Technology
Han Bao
baooWikyytoou..c..pp
Kyoto Universiby, Okinawa Institute of Science and Technology
Kenta Niwa
kenta. nesta.niwa.co Dentt..iww..bi@hho..r www.abbbtttotttcooooo.....
NTT Communication Science Laboratories
Ryoma Sato
r.sato@ml. isstto@mmlisttkkotooou...o
Kyoto University, Okinawa Institute of Science and Technology
Makoto Yamada
makoto. makoto.yamada @oist.jp
Okinawa Institute of Science and Technology
Reviewed on OpenReview: https: openrevveee. net/ forum? id= 8koy8QuT20
Abstract
SGD with momentum is one of the key components for improving the performance of neural networks. For decentralized learning, straightforward approach using momentum is Dis- tributed SGD (DSGD) with ummentum (DSGDm). However, DSGDm performs worse than DSGD when the data distributions are statistically heterogeneous. Recently, several studies have addressed this issuc and proposed mothods with momentum that are more robust to data heterogeneity than DSGDm, although their convergence rates remain dependent on data heterogeneity and deteriorate when the data distributions are heterogeneous. In this study, we propose Momentum Tracking, which is a method with momentum whose conver- analyze gence rate is proven to be independent of data heterogeneity. More specifically, the convergence rate of Momentum Tracking in the setting where the objective function is non-convex and the stochastic gradient is used. Then, we identify that it is independent of data heterogeneity for any momentum coefficient 3 E 1). Through experiments, we demonstrate that Momentum Tracking is more robust to data heterogeneity than the exist- ing docentralized lcarning methods with momentum and can consistently outperform these existing methods when the data distributions are heterogeneous.
1 Introduction
Neural networks have achieved remarkable success in various fields such as image processing (Simonyan & Zisserman| 2015 Chen al. 2020) and natural language processing (Devlin et al. 2019). To train neural networks, need to collect large amounts of training data, but it is often difficult to collect large amounts of data such as medical images on one server because of privacy concerns. In such scenarios, decentralized learning has altracted significant altention because it allows us to train neural networks without aggregating all the data onto one server. Recently, decentralized learning has been studied from various perspectives, including data heterogencity (Tang et al.] [2018b Esfandiari et al.) 2021), communication compression (Tang
et al. 2018a Lu & De Sa
2020
Liu al. 2021 Takezawa al.) 2022a),, and network topologies (iing
et al.
2021 Le Bars al.
2023

---

Published in Transactions on Machine Learning Research (9/2023)
One of the key components for improving the performance of neural networks is SGD with momentum (SGDm). Whereas SGD updates the model parameters using a stochastic gradient, SGDm updates the model parameters using the moving average of the stochastic gradient, which is called the momentum. Because SGDm can accelerate convergence and improve generalization performance, SGDm has become an indispensable lool, enabling neural nelworks to achieve high accuracy (He el al. 2016 Cutkosky & Mehtt 2020 Karimireddy et al. 2021; Defazio 2021]. Recently, SGDm has been improved many studies, and methods such as Adam (Kingma & Ba 2015) and RAdam (Liu et al., 2020a) have been proposed.
In decentralized learning, the straightforward approach to using the momentum is Distributed SGD (DSGD) with momentum (DSGDm) (Gao & Huang 2020). When the data distributions held by each node (i.e., the server) are statistically homogeneous, DSGDm works well and can improve the performance as well as SGDm Lin et al. 2021). However, in real-world decentralized learning settings, the data distributions may be heterogeneous (Hsich et al. 2020). In such cases, DSGDm performs worse than DSGD (i.c., without momentum) YYuan et al.) 2021
This is because, when the data distributions are heterogeneous and use the momentum instead of the stochastic gradient, each model parameter is updated in further different directions and drifts away more easily. As a result, the convergence rate of DSGDm falls below that of DSGD. To address this issue, Lin et al. 2221)) and Yuan et al. (2021) modified the update rules of the momentum in DSGDm and proposed methods that are more robust to data heterogeneity than DSGDm. However, their convergence rates remain dependent on data heterogeneity, and our experiments revealed that their performance are degraded when the data distributions are strongly heterogeneous (Sec.
Data hcterogencity for docentralized learning has been well studied from both experimental and thcoretical perspectives (Hsieh et al. 22000 Koloskova et al. 2020). Subsequently, many methods including Gradient Tracking (Lorenzo & Scutari 2016; Nedić et al. 2017) have been proposed and it has been shown that their convergence rates do not depend on data heterogeneity (Tang et al. 2018b Vogels et al.) 2021 Koloskova et al. 202Ip. However, these studies considered only the case where the momentum was not used, and it remains unclear whether these methods are robust data heterogeneity when the momentum is applied.
In the convex optimization literature, Xin & Khan (2020) and Carnevale et al. 20022 proposed combining Gradient Tracking with momentum or Adam and analyzed the convergence rates. However, they considered only the case where the objective function is strongly convex and the full gradient is used, which does not hold in the standard deep learning setting, where the objective function is non-convex and only the stochastic gradient is accessible. Hence, their convergence rates are still unknown in the setting where the objective function non-convex and the stochastic gradient used and it remains unclear whether their convergence rates are independent of data heterogeneity. Furthermore, they did not discuss data hetcrogeneity, either theoretically or experimentally.
In this work, we propose decentralized learning method with momentum, which we call Momentum Tracking, whose convergence rate is proven to be independent of data heterogencity in the setting where the objective function is non-convex and the stochastic gradient is used. More specifically, we identify that the convergence rate Momentum Tracking is independent of data heterogeneity for any momentum coefficient 3 E [0, 1). In Table [ we compare the convergence rate of Momentum Tracking with those of existing methods. To the best of our knowledge, Momentum Tracking the first decentralizod lcarning method with momentum whose convergence rale has been proven to be independent of data heterogeneity in the setting where the objective function is non-convex and the stochastic gradient is used. Experimentally, we demonstrate that Momentum Tracking is more robust to data heterogencity than the existing decentralized learning methods with momentum and can consistently outperform these existing methods when the data distributions are heterogeneous.
2

---

Published in Transactions on Machine Learning Research (9/2023)
Table 1: Comparison of the convergence rates. In the "Data--Hetrrogeneitt" column, Sv" indicates that the convergence rate is independent of data heterogeneity, and "(v)" indicates that it is independent, but there is no discussion about data heterogeneity either theoretically or experimentally. In the "Momentum, " "Stochastic," " and "Non-Conver, columns, "v" respectively indicates that the method is accelerated using momentum, the convergence rate is provided when the stochastic gradient is used, and the convergence rate is provided when the objective function non-convex.
Data- Heterreeetrry
Momentum
Stochastic
Non-Conver
DSGD [Lin et al. 2017
Gradient Tracking (Koloskova et
2021
DSGDm (Gao & Iuang
2020
QG-DSGDm (Lin et al.
2021
DecentLaM Yuan et al.
2021
ABm Xin Khan
2020
133
GTAdam Carnevale et al.
2022
Momentum Tracking (our work)
2 Preliminaries and Related Work
2.1 Decentralized Learning
GVVV, E) be an undirocted graph that represents the underlying network topology, where V denotes the set of nodes and E denotes the set of edges. Let == [V] be the number of nodes, and we label each node in V by a set of integers {1, ... ,N} for simplicity. We define Mr == {j V (i.j) E E} as the set of neighbor nodes of node and define N₁ = N; U {i}. In decentralized learning, node has a local data distribution D, and local objective function fi : Rd + R, and can communicate with node j if and only if (i, E E. Then, decentralized learning aims to minimize the average of the local objective functions follows:
Let G =
min aERd
f(x) = Σ
f(())
fi(x) = BEIND (F)
where is the model parameter, & is the data sample that follows D;, and local objective function fi(+)) is defined as the expectation of Fi(x;; & over data sample & In the following, (.; and ff(x)) = [V E.)] denote the stochastic and full gradient respectively.
Distributed SGD (DSGD) (Lian et al., 2017) is one of the most well-known algorithms for decentralized learning. Formally, the update rules of DSGD are defined as follows:
(r+1)
Σ Wi, (ar) - -(F JEN!
(1)
where 77 > 0 is the step size and Waj E [0,1] is the weight of edge (i.j). Let W E [0, N\NN be the matrix whose (ele)eelement is Wi if (i,j) E F. and 0 otherwise. In general, a mixing matrix is used for W (i.e., 1). Lian et al. (2018) extended DSGD in the case where each node
W W W1 = 1, and communicates asynchronously and analyzed the convergence rate. Koloskova et al. (2020) analyzed the convergence rate of DSGD when the network topology changes over time. These results revealed that the convergence rate of DSGD deteriorates and the performance is degraded when the data distributions held by each node are statistically heterogeneous. This is because the local gradients V are different across nodes and each model parameter x, tends to drift away when the data distributions are heterogeneous. To address this issue, 2 (Tang et al. 2018b), Gradient Tracking (Lorenzo & Scutari 2016 Nedić et al, 2017), and primal-dual algorithms (Niwa et al. 20200] 2021 Takezawa et al.) 2022b) were proposed to correct the local gradient V/z to the global gradient V/. As a different approach, Vogels et al. (2021) proposed a novel averaging method to prevent each model parameter æ, from drifting away. It has been shown that the convergence rates of these mothods do not depend on data hetcrogencity and do not deteriorate, even when
the data distributions are statistically heterogeneous. However, these methods do not consider the case in which momentum is used.
3

---

Published in Transactions on Machine Learning Research (9/2023)
2.2 Momentum
The methods with momentum were originally proposed by Polyak 1964). and SGD with momentum (SGDm)
has achieved successful results in training neural networks (Simonyan & Zisserman 2015 He et al. 2016
Wang et al., 2020b). In docentralized learning, a straightforward approach to using the momentum is DSGD
with momentum (DSGDm) (Gao & Huang
2020).
The update rules of DSGDm are defined as follows:
u;
(r+1)
But
+ VF((, (r) :4")
(2)
(r+1)
Σ JENT
Wij (2)" m m
(3)
where us is the local momentum of node i and B E 0. is momentum cocfficient. In addition, several variants of DSGDm were studied by Yu et al. (2019; Assran et al. (2019); Wang et al. (2020a); Singh et al. (2021b. When the data distributions held by each node are statistically homogeneous, DSGDm works well and can improve accuracy as well as SGDm. However, when the data distributions are statistically heterogeneous, DSGDm leads to poorer performance than DSGD. This is bocause when the data distributions held by each node statistically heterogeneous (i.e., Vi varies significantly across nodes), the difference in the updated value of the model parameter across the nodes (i.e., 17,)) is amplified by the momentum (Lin et al. 2021
To address this issue, Yuan et al. (2021) and Lin et al. (2021) proposed methods to modify the update rules of the momentum in DSGDm such that the momentum each node has close values, which are called DecentLaM and QG-DSGDm, respectively. They further experimentally demonstrated that these methods are more robust to data heterogeneity than DSGDm. However, their convergence rates have been shown to still depend on data heterogeneity and deteriorate when the data distributions are heterogeneous.
2.3 Gradient Tracking
One of the most well-known methods whose convergence rate does not depend on data heterogeneity is Gradient Tracking (Lorenzo & Scutari 2016). Whereas DSGD exchanges only the model parameter æ;, Gradient Tracking exchanges the model parameter æ; and local (stochastic) gradient Vf and then updates the model parameters while estimating global gradient V.. Nedić et al. (2017) and Qu & Li (2018) analyzed the convergence rate of Gradient Tracking when the objective function is (strongly) convex and the full gradient is used. Pu & Nedic (2021) analyzed the convergence rate when the objective function is strongly convex and the stochastic gradient is used. Recently, Koloskova et al. (2021) analyzed the convergence rates of Gradient Tracking in the setting where the objective function non-convex and the stochastic gradient is used. There is also a line of research to combine Gradient Tracking with variance reduction methods (Xin) et al. 2022) and communication compression methods (Zhao et al. 2022). They showed that the convergence rate of Gradient Tracking does not depend on data heterogeneity. However, these studies only consider the case without momentum, and the convergence analysis for Gradient Tracking with momentum has not been explored thus far in the aforementioned studies.
3 Proposed Method
In this section, we propose Momentum Tracking, which is a decentralized learning method with momen- tum whose convergence rate is proven to be independent of the data heterogeneity in the setting where the objective function is non-convex and the stochastic gradient used.
3.1 Setup
We assume that the following standard assumptions hold:
Assumption 1. There exists a constant f* > -oo that satisfies f(x) Z f for all x E Rd.
Assumption There exists a constant p E (0, 1] that satisfies for all #1,
EEN EN Rd.
XWW X < (1 p)|| x1
(4)
4

---

Published in Transactions on Machine Learning Research (9/2023)
where X == (01,... "2,..,,ay .NN) E BAxN and X == 1. XX11.
Assumption 3. There erists constant L 0 that satisfies for all i e V and a, y R
( vii(g)ll S Lile yll-
(5)
Assumption 4. There exists constant a² that satisfies for all V and a; Rd,
E D (F((aE)) (x)))))) o².
(6)
Assumptions 1
3 and 4 are commonly used for decentralized learning algorithms Lian et al., 2017 Yu
et al. 2019 Koloskova et al. 2021: Lin et al. 2021 Lu & De Sa 2022 Yuan et al. 2022). Additionally, the
following assumption, which represents data heterogeneity, commonly used in the convergence analysis of
decentralized learning algorithms (Lian al. 2017 Yu ct al. 2019 Lin et al. 2021
Assumption 5. There exists a constant Ç² that satisfies for all x ERd
(f(()) V[<
Under Assumption 5 the convergence rates of DSGD LLan al. 2017), DSGDm Gao & Huang 2020
Yuan et al. 2021), QG-DSGDm (Lin et al. 2021 and DecentLa. (uaan et al. 2021 were shown to be dependent on data heterogeneity Ç² and deteriorate as ç² increases. By contrast, in Sec. 3.3 we prove that Momentum Tracking converges without Assumption and the convergence rate is independent data we do not assume the convexity of the objective functions f(x) and fi(x). Therefore, (a)) and fi(x)) are potentially non-convex functions (e.g., the loss functions of neural networks).
heterogencity <?. In addition,
3.2 Momentum Tracking
In this section, we propose Momentum Tracking, which is robust to data heterogeneity and accelerated by the momentum. The update rules of Momentum Tracking are defined as follows:
(r+1) u;
=Bu + VFi(x! ; ) (r+1) - -1.+tt)_((")
(7)
x
(r+1)
Σ Wo - -7 "1(11
-c(")
(8)
JEN!
c
(r+1)
Σ JENT
We (c)") - u((tli) + u (r+1))
(9)
where 3 E 10, is a momentum cocfficient. The pscudo-code for Momentum Tracking presented in Soc. In Momentum Tracking, e; corrects the local momentun u, to the global momentum Σ3 Uy and prevents each model parameter x; from drifting, even when the data distributions are statistically heterogeneous (i.e., the local momentum u, varies significantly across nodes).
A
Because Momentum Tracking is equivalent to Gradient Tracking when 3 = 0, Momentum Tracking is a simple extension of Gradient Tracking. Hence, when 3 = 0, it has been shown that the convergence rate of Momentum Tracking is independent of data heterogeneity <² (Koloskova et al. 2021). However, because data heterogencity is amplified when the momentum used instead of the stochastic gradient (i.c., 8 > 0) [Lin et al.] 2021 Yuan et al. 2021]. 1, it. unclear whether the convergence rate of Momentum Tracking is independent of data heterogeneity <² for any 3 E [0, 1) or for only restricted range of B. In Sec. 3.3 we provide the convergence rate of Momentum Tracking and prove that it is independent of ç2 for any 0. 1).
3.3 Convergence Analysis
Under Assumptions and Theorem provides the convergence of Momentum Tracking. All proofs presented in Sec.
5

---

Published in Transactions on Machine Learning Research (9/2023)
Theorem 1. Suppose that Assumptions 1 3 and 4 hold, each model parameter x; is initialized with the
same parameters, and both u, and e2 are initialized as I-B (VF(( (0), - Ej= (0), :53 )). Then,
for any 3 E [0, 1) and R 2 1, there erists step size n such that the average parameter R E E V V ())
generated by Eqs. 7 g
is bounded from above by
o
(V
roo0L NR
r202L2 P2
(1 (1+
pD2
Lro
182 1+ (1- -3)
1--))
+
(10)
(1- 5)p²
where x N Ei= Di and ro = f(x(0)) f"
Remark 1. Theorem assumes that u and C₁ are initialized as I-B I (0),
1 (VF(2)) (0; :
N EE (a) ()) Thus, All-Reduce is required only once before starting the training. If
initialize ui and C₁ as zeros, data heterogeneity at initial parameters t Es (V (0) )2 appears in the convergence rate, but the same phenomenon occurs in the analysis of Gradient Tracking by Koloskovd et al. 2021)) (see Sec. B
Remark 2. Combinations of Gradient Tracking with the momentum or Adam have also been proposed by Xin E Khan (2020) and Cornevale et al. (2022). However, they considered only the setting in which the objective function strongly conver and the full gradient is used. By contrast, our study focuses on the deep learning setting. Hence, our proof strategies are completely different from those in these previous studies, and Theorem provides the convergence rale in the selling where the objective funclion is non-conver and the stochastic gradient is used.
Remark 3. Koloskova et al. (021)) provided the convergence rate of Gradient Tracking in the setting where the objective function is non-conver and the stochastic gradient is used. However, they did not consider the case where the momentum is used, and it is not trivial to provide the convergence rate of Momentum Tracking from the results in this previous work.
3.4 Discussion
Comparison with Gradient Tracking: Theorem [ indicates that the convergence rale of Momentum Tracking does not depend on data heterogeneity <² for any B E [0, 1) and does not deteriorate even when the data distributions are statistically heterogeneous (i.e., (² > 0). Therefore, Theorem [ indicates that Momentum Tracking is theoretically robust to data heterogeneity for any 3 E 1). Although Momentum Tracking is simple extension of Gradient Tracking, our work is the first to identify that the combination of Gradient Tracking and the momentun converges without being affected by data heterogeneity ç² for any 3 E [0, 1) in the setting where the objective function is non-convex and the stochastic gradient is used.
Although the convergence rate of Momentum Tracking Eq. 10 is minimized when = 0, Momentum Track- ing does accelerate its convergence with the momentum being used (5 0), as experimentally demonstratod in Sec. 4 Indeed, the convergence rates of DSGDm (Gao & Huang 2020 and QG-DSGDm [Lin et al. (2021) have the same issue. Thus, it is still open question to show the theoretical benefits of using B > 0.
Comparison with Existing Algorithms with momentum: Next, we compare the convergence rate of Momentum Tracking with those of existing decentralized learning algorithms with momentum: DSGDm Gao & Huang 2020 DeC (Yuan et al. 2021), and QG-DSGDm (Lin et al. 2021). Here, we only show the convergence rate of QG-DSGDm, but the same discussion holds for the other methods. The convergence rate of QG-DSGDm is as follows:
Theorem 2 (Lin al. 2021 ). Suppose that Assumptions 1 3 and 4 hold, and Assumption 5 also holds. Then, for any B E [0, tp and R 2 1, there erists a slep size such that Ti D E ( generated by QG-DSGDm is bounded from above bifl
o (V
T NR
2. (5 +
$ +
Lro
1
1
R²
R
p
1-
3
(1 -3)3
For simplicity, we the additional hyperparameter i QG-DSGDm B.

---

Published in Transactions on Machine Learning Research (9/2023)
where ro f()())) f
Data heterogeneity 2² appears in the second term. Thus, the convergence rate of QG-DSGDm deteriorates when the data distributions held by each node are statistically heterogeneous. By contrast, the convergence rate of Momentum Tracking Eq. (10p does not depend on data heterogeneity Ç². Therefore, Momentum Tracking is more robust to data heterogeneity than QG-DSGDm. Because the convergence rates of DSGDm and DecentLaM also depend on Ç², the same discussion holds for DSGDm and DecentLaM. Hence, Mo- mentum Tracking is more robust to data heterogeneity than these methods. To the best of our knowledge, Momentum Tracking is the first decentralized learning method with momentum whose convergence rate has been proven be independent of data heterogeneity ç in the sctting where the objective function is non-convex and the stochastic gradient is used.
Next, discuss the range of 3. The convergence rates of QG-DSGDm and DecentLaM provided by Lin et al. (2021) and Yuan et al. (2021) hold only when the range of B is restricted. For instance, Theorem 2 assumes that 8 S 21+p (< 0.05). However, these restrictions on the range of 3 do not hold in practice. (Typically, 8 is set to 0.9.) Therefore, the convergence rates of QG-DSGDm and DecentLaM are unclear in such practical cases. By contrast, Theorem | can provide the convergence rate of Momentum Tracking that holds for any 3 E 1).
Comparison with SGDm: Next, we compare the convergence rate of Momentum Tracking with that of SGDm. In a setting where the objective function non-convex and the stochastic gradient is used, SGDm has been proven to converge the stationary point with O(1/VR) (Yan et al. 2018 Liu et al. 2020b). By contrast, Theorem [ indicates that if the number of rounds R is sufficientyy large, Momentum Tracking converges with O(1/VNR). Therefore, Momentum Tracking can achieve lincar speedup with respect to the number of nodes N, which is a common and important property in decentralized learning methods (Lian et al. 2018 Koloskova et al. 2020
4
Experiment
In this section, we present the results of an experimental evaluation of Momentum Tracking and demonstrate that Momentum Tracking is more robust to data heterogeneity than the existing decentralized learning methods with momentum. In this section, we focus on test accuracy, and more detailed evaluation about the convergence rate is presented in Sec. C.7
4.1 Setup
Comparison Methods: (1) DSGD Lian et al. 2017): the method described in Sec. 2.1 (2) DSGDm
(aoo & Huang (0200;: the method described Sec. 2.2 (3) QG-DSGDm (Lin et al. 2021 :: method
which the update rule of the momentum in DSGDm modified to be more robust to data heterogeneity
than DSGDm; (4) DecentLaM YYuan et al. 2021): a method in which the update rule of the momentum
in DSGDm is modified to be more robust to data heterogeneity; (5) Gradient Tracking (Nedié et al. 2017):
method without momentum that is robust to data heterogeneity; (6) Momentum Tracking: the proposed
method described in Sec. 3
Dataset and Model: We evaluated Momentum Tracking using three 10-class image classification tasks: FashionMNIST (Xiao et al., 2017), SVHN (Netzer et al. 2001]), and CIFAR-10 (Krizhevsky) 2009). Following the previous work (Niwa al.] (2020), we distributed the data to nodes such that each node was given data of randomly selected l classes. When & 10, the data distributions held by each node can be regarded statistically homogeneous. When 10, the data distributions are regarded statistically heterogeneous, We evaluated the comparison methods by setting & to (4, 8, 10} and changing data heterogencity. Noto that a smaller l: indicates that the data distributions are more helerogeneous. For the neural network architecture, we used LeNet (LeCun et al. 1998) with group normalization (Wu & He 2018) in Sec. 4.2 In Sec. [4.3] we present more detailed evaluation by varying the neural network architecture (c.g., VGG-11 (Simonyan Zisserman 2015)) and ResNet-34 (He al.) (016)). For each comparison method, we used 10% of the training data. for validation and individually tuned the step size. For DSGDm, QG-DSGDm,

---

Published in Transactions on Machine Learning Research (9/2023)
70
60-
75-
Accuracy
50
Accuracy
50
Accuracy
70
40
65
DSGD
30
Gradient Tracking
DS60m
20
QG:D5GDm
55
DecentLaM
10
tracking
100
200
300
400
500
100
200
300 Epach
400
500
50
10
Epoch
k-class
(a) CIFAR-10 (10-class)
(b) CIFAR-10 10 (4-class)
(c) Average accuracy for datasets
Figure 1: (a) Learning curve on CIFAR-10 with LeNet in the 10-class (i.e., homogeneous) setting. We
evaluated the test accuracy per 10 epochs.
(b) Learning curve in the 4-class (i.e., heterogeneous) setting,
(c) Average test. accuracy for all datasets (i.e., FashionMNIST, SVHN, and CTFAR-10).
DecentLaM, and Momentum Tracking, set to 0.9. All experiments were repeated using three different seed values, and report their averages. More detailed hyperparameter settings are presented in Sec E
Network Topology and Implementation: Communication efficiency is one of the most important factors in decentralized learning and is determined by the maximum degree of the underlying network topology (Neglia et al. 2019 Wang et al.) 2019 Ying et al. 2021). Thus, following these prior works, we present the results of setting the underlying network topology to ring consisting of eight nodes (i.e., N 8) in Secs. 4.2 and 4.3 In Sec. C.T] present more detailed evaluation by varying the network topology. All comparison methods were implemented using PyTorch and run eight GPUs (NVIDIA RTX 3090).
4.2 Experimental Results
Table lists the test accuracy for FashionMNIST,, SVHN, and CIFAR-10. Fig. (a) and (b) present the learning curves for CIFAR-10 and Fig. I (c) presents the average test accuracy for all datasets.
Comparison of Momentum Tracking and Gradient Tracking: First, discuss the results of Mo- mentum Tracking and Gradient Tracking. Table 2 and Fig. [ indicate that Momentum Tracking achieves higher accuracy faster than Gradient Tracking and outperforms Gradient Tracking in all settings. When the data distributions are homogencous (i.c., 10-class), Momentum Tracking outperforms Gradient Tracking by 5.8% on average. When the data distributions are heterogeneous (e-g., 4-class), Momentum Tracking outperforms Gradient Tracking by 4.4% on average. Thus, the results show that Momentum Tracking can consistently outperform Gradient Tracking regardless of data heterogeneity.
Comparison of Momentum Tracking and DSGDm: Next, discuss the results of Momentum Track- ing and DSGDm. The results show that when the data distributions are homogeneous (i.e., 10-class), Momentum Tracking and DSGDm are comparable and outperform DSGD and Gradient Tracking. How- ever, when the data distributions are heterogencous (c.g., 4-class), the test accuracy DSGDm decreases even more than that of DSGD, and DSGDm underperforms DSGD by 9.9% on average. By contrast, the results indicate that Momentum Tracking consistently outperforms DSGD and Gradient Tracking by 14.9% and 4.4% respectively when the data distributions are heterogeneous. The results indicate that Momentum Tracking is more robust to data heterogeneity than DSGDm and outperforms DSGDm by 24.9% on average.
When the data distributions are homogeneous (iee, 10-class), Momentum Tracking, QG-DSGDm, and DecentLaM are comparable and outperform DSGD and Gradient Tracking, By contrast, when the data distributions are heterogeneous (e.g., 4-class), Momentum Tracking consistently outperforms QG-DSGDm and DecentLaM by 9.9% and 4.5% respectively, whereas QG-DSGDm and DecentLaM are more robust to data heterogeneity than DSGDm. Hence, these results are consistent with theoretical analysis, discussed in Secs. 3.3 and 3.4
Comparison of Momentum Tracking, QG-DSGDm, and DecentLaM:
8

---

Published in Transactions on Machine Learning Research (9/2023)
Table 2: Test accuracy on FashionMNISST, SVHN, and CIFAR-10 with LeNet. "k-class" means that each node has only the data of randomly selected l classes. Bold font means the highest accuracy.
FaShionMNIST
10-class
8-class
6-class
4-class
DSGD
85.6 + 0.49
85.6 + 0.41
82.7 + 1.12
78.1 + 1.56
Gradient Tracking
85.0 = 0.49
85.4 = 0.26
85.0 + 0.37
84.9 + 0.22
DSGDm
89.5 0.15
89.3 0.21
82.1 + 3.23
68.7 + 5.02
QG-DSGDm
89.6 + 0.10
89.5 + 0.47
86.9 + 1.59
80.8 + 2.94
DecentLaM
89.5 = 0.14
89.3 = 0.36
89.2 + 0.41
3.05 84.3 + 3.05
Momentum Tracking
89.5 = 0.36
89.4 = 0.05
88.9 + 0.47
86.8 + 1.56
SVHN
10-class
8-class
6-class
4-class
DSGD
90.1 + 0.17
89.5 + 0.61
87.6 + 1.94
78.8 + 8.55
Gradient Tracking
90.1 + 0.30
89.8 = 0.38
89.8 + 0.39
89.4 + 0.47
DSGDm
92.6 + 0.35
92.4 = 0.19
88.1 + 4.38
67.2 + 9.69
QG-DSGDm
92.5 + 0.22
92.5 + 0.17
90.9 + 1.67
83.5 + 7.14
DecentLaM
92.4 = 0.21
92.2 = 0.39
92.0 + 0.48
88.2
Momentum Tracking
92.6 = 0.32
92.4 = 0.40
92.3 + 0.23
91.7 + 0.53 0.53
CIFAR-10
10-class
8-class
6-class
4-class
DSGD
63.1 + 0.60
64.1 + 0.52
61.2 + 1.16
47.6 + 5.77
Gradient Tracking
62.3 + 0.73
62.0 = 0.80
61.9 + 0.58
61.8 + 0.82
DSGDm
72.9 + 0.41
72.5 + 0.20
63.8 + 6.24
38.8 + 1.61
QG-DSGDm
72.4 0.87
73.1 0.16
69.6 2.42
55.3 5.30
DecentTaM
73.2 + 0.36
72.9 + 0.14
71.7 + 1.10
63.1 + 5.43
Momentum Tracking
72.9 = 0.59
73.0 0.49
72.6 + 0.41
70.7 + 1.38
Table 3: Test accuracy on CIFAR-10 with VGG-11 and ResNet-34. "k-class" indicates that each node has only the data of randomly selected &or classos, and bold font indicates the highest accuracy.
CIFAR-10 + VGG-11
CIFAR-10 10 + ResNet-34
10-class
4-class
2-class
10-class
4-class
2-class
DSGD)
91.3 + 0.12
86.9 + 1.75
71.1 + 2.82
94.3 + 0.13
90.0 + 1.65
63.5 + 0.90
Gradient Tracking
88.1 0.14
86.3 0.50
83.0 + 0.04
85.9 0.71
82.6 + 0.33
76.2 - 0.30
DSGDm
92.2 0.09
77.3 + 4.05
39.6 + 5.92
95.8 + 0.26
79.0 4: 3.69
27.7 2.83
QG-DSGDm
92.0 0.02
89.5 1.08
77.8 + 1.96
95.8 0.22
94.3 + 1.13
79.9 1.59
DeM
92.1 1: 0.09
90.9 1 0.65
85.2 1 0.67
95.9 0.04
95.2 1 0.51
89.2 1 2.26
Momentum Tracking
91.9 +
90.9
87.0 + 0.48
95.0
94.4 0.52
89.9 0.73
In summary, when the data distributions are homogeneous, DSGDm, QG-DSGDm, DecentLaM, and Momen- tum Tracking are comparable and outperform DSGD and Gradient Tracking. When the data distributions are heterogeneous, Momentum Tracking is more robust data heterogeneity than DSGDm, QG-DSGDm, and Lec and can outperform all comparison methods.

---

Published in Transactions on Machine Learning Research (9/2023)
VGG-11
ResNet-34
90
70
70
Accuracy
Accuracy
50
50
DSGD
Gradient Tracking
30
QG-DSGDm
DecentLaM
10
Momentum Tracking
200
400
600
800
1000
200
400
600
750
Epoch
Epoch
Figure 2: Learning curves for CIEAR-10 with VGG-11 and ResNet-34 in the 2-class setting.
4.3 Results with Various Neural Network Architectures
Next, we evaluated Momentum Tracking in more detail by varying the neural network architecture. Table 3
lists the test accuracy with VGG-11 [Sioonyan & Zisserman, 2015) and ResNet-34 (He et al. 2016 when we to (2,4, 4, 10); and Fig. shows the learning curves.
For both neural network architectures, Table 3 reveals that when the data distributions are homogeneous (i.e., 10-class), Momentum Tracking is comparable with DSGDm, QG-DSGDm, and DecentLaM and outperforms DSGD and Gradient Tracking. By contrast, when the data distributions are heterogeneous (e.g., 2-class), Table and Fig. 2 reveal that Momentum Tracking outperforms all comparison methods for both neural network architectures. In particular, Fig. 2 indicates that DSGDm, QG-DSGDm, and DecentLaM are unstable and continue to oscillate in the final training phase, whereas Momentum Tracking converges stably. These results are consistent with those of LeNet presented Table
5 Conclusion
In this study, we propose Momentum Tracking, which method with momentum whose convergence rate is proven to be independent of data heterogeneity. More specifically, we provide the convergence rate of Momentum Tracking in the setting where the objective function non-convex and the stochastic gradient is used. Our theoretical analysis reveals that the convergence rate of Momentum Tracking is independent of data heterogeneity for any 3 E [0, Through image classification tasks, we demonstrated that Momentum Tracking consistently outperform the decentralized learning methods without momentum regardless of data heterogeneity. Morcover, we showed that Momentum Tracking is more to data heterogencity than existing recentralized learning methods with momentum and can consistently outperform these existing methods when the data distributions are heterogeneous.
Acknowledgments
Yuki Takezawa, Ryoma Sato, and Makoto Yamada were supported by JSPS KAKENHI Grant Number 23KJ1336, 21.J22490, and MEXT KAKENHI Grant Number 20H04243, respectively.
References
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastie gradient push for distributed deep learning. In International Conference Machine Learning, 2019.
Guido Carnevale, Francesco Farina, Ivano Notarnicola, and Giuseppe Notarstefano. Gtadam: Gradient tracking with adaptive momentum for distributed online optimization. In arXiu, 2022.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In International Conference on Machine Learning, 2020.
10

---

Published in Transactions on Machine Learning Research (9/2023)
Ashok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In International Conference Machine Learning, 2020.
Aaron Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non- convex optimization. In arXiv, 2021.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidi- rectional transformers for language understanding. In Conference of the North American Chapter of the Association for Computational Lònguistics, 2019.
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, 2021.
Hongchang Gao and Heng Huang. Periodic stochastic gradient descent with momentum for decentralized training. In Xrxiv, 2020.
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition, 2016.
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.
Tzu-Ming Harry Hsu, Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. In ArXiv, 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri, Sashank J. Reddi, Sebastian U Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross-device federated learning. In Advances in Newral Information Processing Systems, 2021.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Confer- ence on Learning Representations, 2015.
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.
Anastasia Koloskova, Tao Lin, and Sebastian Stich. An improved analysis of gradient tracking for decen- tralized machine learning. In Advances in Neural Information Processing Systems, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Batiste Le Bars, Aurélien Bellet, Mare Tommasi, Erick Lavoie, and Anne-Maric Kermarrec. Refined conver- gence and topology learning for raciedd sgd with heterogeneous data. In International Conference on Artificial Intelligence and Statistics, 2023.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to docu- ment recognition. In JEEE, 1998.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithmss outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Tiu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, 2018
Tao Lin, Sai Pranccth Karimireddy, Scbastian Stich, and Martin Jaggi. Quasi-global momentum: Accelerat- ing decentralized deep learning on heterogencous data. In International Conference on Machine Learning, 2021.
11

---

Published in Transactions on Machine Learning Research (9/2023)
Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu, Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and beyond. In International Conference Learning Representations, 2020a.
Xiaorui Liu, Yao Li, Rongrong Wang, Jiliang Tang, and Ming Yan. Linear couvergent decentralized opti- mization with compression. In International Conference on Learning Representations, 2021.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. Advances in Neural Information Processing Systems, 2020b.
Paolo Di Lorenzo and Gesualdo Scutari. NEXT: in-network nonconvex optimization. In IEEE Transactions on Signal and Information Processing over Networks, 2016.
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized SGD. In International Conference on Machine Learning, 2020.
Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In International Confer- ence on Machine Learning, 2021.
Angelia. Nedié, Alexander Olshevsky, and Wei Shi. Achieving geometric convergence for distributed opti- mization over time-varying graphs. In SIAM Journal on Optimization, 2017.
Giovanni Neglia, Gianmarco Calbi, Don Towsley, and Gayane Vardoyan. The role of network topology for distributed machine learning. In IEEE Conference on Computer Commmanications, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. In Advances in Neural Information Processing Systems Workshop, 2011.
Kenta Niwa, Noboru Harada, Guoqiang Zhang, and W. Bastiaan Kleijn. Edge-consensus learning: Deep learning on p2p networks with nonhornogeneous data. In International Conference Knowledge Discovery and Dala Mining, 2020.
Kenta Niwa, Guoqiang Zhang, W. Bastiaan Kleijn, Noboru Harada, Hiroshi Sawada, and Akinori Fujino. Asynchronous decentralized optimization with implicit stochastic variance reduction. In International Conference Machine Learning, 2021.
Boris T. Polyak. Some methods of speeding up the convergence of iteration methods. In USSR Computational Mathematics and Matheratical Physics, 1964.
Shi Pu and Angelia Nedic. Distributed stochastic gradient tracking methods. In Math. Program., 2021.
Guannan Qu and Na Li. Harnessing smoothness to accelerate distributed optimization. In IEEE Transactions on Control of Network Systems, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Navjot Singh, Deepesh Data, Jemin George, and Suhas Diggavi. Squarm-sgd: Commuiicttion-ffficcnn momentum sgd for decentralized optimization. Tn IEFE International Symposium on Information Theory, 2021.
Yuki Takezawa, Kenta Niwa, and Makoto Yamada. Communication compression for decentralized learning with operator splitting methods. In Xix, 2022a.
Yuki Takezawa, Kenta Niwa, and Makoto Yamada. Thcoretical analysis of primal-dual algorithm for non- convex stochastic decentralized optimization. In arxiv, 2022b.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Ji Liu. Commuicattion compression for decentral- ized training. Tn Advances in Neural Information Processing Systems, 2018 20.
12

---

Published in Transactions on Machine Learning Research (9/2023)
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. d:: Decentralized training over decentralized data. In International Conference on Machine Learning, 2018b.
Thijs Vogels, Lie He, Anastasia Koloskova, Sai Pranceth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. RelaySum for decentralized deep learning on heterogeneous data. In Advances in Newral Information Processing Systems, 2021.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speeding up docentralizod sgd via matching docomposition sampling. In Indian Control Conference, 2019.
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. SlowMo: Improving communication- efficient distributed sgd with slow momentum. In International Conference on Learning Represenlations, 2020a.
Jun-Kun Wang, Chi-Heng Lin, and Jacob Abernethy. Escaping saddle points faster with stochastic momen- tum. In International Conference on Learning Representations, 2020b.
Yuxin Wu and Kaiming He. Group normalization. In European Conference on Computer Vision, 2018
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. In arXiv, 2017.
Ran Xin and Usman A. Khan. Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking. In IEEE Transactions on Automatic Control, 2020.
Ran Xin, Usman A. Khan, and Soummya Kar. Fast decentralized nonconvex finite-sum optimization with recursive variance reduction. In SIAM Journal on Optimization, 2022.
Yan Yan, Tianbao Yang, Zhe Li, Qihang Lin, and Yi Yang. A unificd analysis of stochastic momentum methods for deep learning. International Joint Conference on Arlificial Intelligence, 2018.
Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. In Advanees in Neurol Information Processing Systems, 2021.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In International Conference Machine Learning, 2019.
Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. De- centLaM: Decentralized momentum sgd for large-batch deep training. In International Conference on Computer Vision, 2021.
Kun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang, and Pan Pan. Revisiting optimal convergence rate for smooth and non-couvex stochastic decentralized optimization. Advances in Neural Information Processing Systems, 2022.
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.
13

---

Published in Transactions on Machine Learning Research (9/2023)
A Pseudo-Codes
The pseudo-codes for Momentum Tracking, QG-DSGDm, and DecentLaM given in the following, where Transmit:-}() denotes that node transmits parameters to node j and Receive,-)() denotes that node receives parameters from node j.
Algorithm 1: Update rules of Momentum Tracking at node i.
1: Input: Step size n > 0, 3 E (0, 1], mixing matrix W. Initialize e; and u, to
I-B (ar (0). (0)
N E, (a)(a) :,))) for all V and a, with the same parameter.
for 0,... R do
u, (++1) + Bu ( (F )
for j E N, do
Transmit,-,(00
(2)
) and (a)
Transmit, (c. (r) - ui (++t)) and (e -u,tt))
6:
end for (r+1)
EjENt Wyy - "u! (u.rtt) c(()) (r)
(r+))) EjEN! Wij (g) u, l + ui (r+1)
C
10: end for
Algorithm 2: Update rules of QG-DSGDm at node i.
Input: Step size 17 > 0, 3, E (0, 1], mixing matrix W. Initialize ú; to zero for all E V and with the same parameter.
2: for r r 0,,..., do
(r+1) + -ū (r+3)
VF((
x (r) nu,
(++1)
2,
5: for j N, do
Transmit, (2, (1+b)) and Rec (1+t)). 7: end for
6:
2
((++1)
Ejent Waye (1+2)) 10 -0(t((r))))
9: d(r+1) +-
10: a. a(r+() + pú(() + +(1 --ddd+t))
11: end for
Algorithm 3: Update rules of LecentLaM node
1: Input: Step size 77 > O, 8 E (0, 1], mixing matrix W. Initialize u, to zero for all é E V and æ; with the same parameter.
2: for r 0, .... R do
x; (r+1) x (r)
for E NG do
5: Transmit,,,(22 (r+ and Receive,, (r+b))
6: end for
7: g (r+1)
+- 1 x
(r) 1 EjEN, Wyyz (r++) (r+t)
8: u (r+1)
+ Bu. (r)
(r+1)
+ gi
x (1+1) (r) mu(+t1)
nu (++1).
10: end for
14

---

Published in Transactions on Machine Learning Research (9/2023)
B Additional Discussion about Convergence Rate
B.1 Comparison with Gradient Tracking
Because Momentum Tracking is cquivalent to Gradient Tracking when B = 0, Theorem | also provides the convergence rate of Gradient Tracking. In this section, we compare the convergence rale of Gradient Tracking provided Theorem to that provided by Koloskova
(2021).
From Theorem 1 we get the following statement.
Corollary 1. Suppose that 3 = 0 and the assumptions of Theorem 1 hold. Then, for anyy R 2 1, there evists step size such that the average parameter æ = E, generated by Eqs.
7 9
satisfies
R-1
||= '00 ('0(v= roo2L NR
rooL p
Lro 1 R
(11)
where ro == f()(0))=
Then, under Assumptions 3 and Koloskova et al. 2021 provided the convergence rate of Gradient
Tracking as follows.
Theorem (Koloskova et al. 2021 Suppose that Assumptions 1 and 4 hold, each model parameter
Ds initialized with the same parameters, and C; is initialized as O. Then, for any round R 2 log }), there exists step size that satisfies that the average porameter E = N Σ. ai generated by Gradient Trucking salisfies
p log( 50
(V VT0O'L NR
R Σ
||
TOOL
L(ro + ICB) +
V
(12)
R
PVN))
pcR
where Ō.) hides the polylogarithmic factors, == VVI
:5)
E, (F E, = 1-
min Amins 0}?, and Amin is the minimum eigenvalue of W.
Comparing the convergence rates Eqs. and 12 the convergence rate in Eq. 12 is tighter than that in Eq. 11 because 2 p for any mixing matrix W. However, because the convergence rate in Eq. (12) holds only when the number of round R is larger than log( 21 + log H)), Theorem 3 can not describe the behavior of the convergence rate at the beginning of the training. In contrast, Corollary provides the convergence rate for Gradient Tracking that holds for any R 2 1.
B.2 Comparison with Other Decentralized Learning Methods
Lu & De Sa 2001 and Yuan et al. [0022 proposed DeTAG and MG-DSGD that can achieve optimal con- vergence rates by using algorithmic techniques such as gradient accumulation and multiple gossip averaging. However, Assumption 5 necessary for both analyses. Then, as the data heterogeneity becomes large, the convergence rate of DeTAG deteriorates, and the number of multiple gossip averaging increases. The goal of our study is propose a method with momentum whose convergence rate is independent of data heterogeneity. Thus, leave it to future work to compare Momentum Tracking with these methods.
C Additional Experiments
C.1 Results with Various Network Topologies
We evaluated Momentum Tracking in more detail by changing the underlying network topology. Table lists the Lest. accuracy of all comparison methods when we set the underlying network topology to be hypercube or semantic exponential graph.
Table indicates that when the data distributions held by each node are statistically homogeneous (i.e., 10-class), DSGDm, QG-DSGDm, DecentLaM, and Momentum Tracking comparable and outperform
15

---

Published in Transactions on Machine Learning Research (9/2023)
DSGD and Gradient Tracking for all network topologies. When the data distributions are heterogeneous (i.e., 4-class), the results show that Momentum Tracking is more robust to data heterogeneity than DSGDm, QG-DSGDm, and DeCentLaM and outperforms all comparison methods for all network topologies. Therefore, the results indicate that Momentum Tracking is robust to data heterogeneity regardless of the underlying network topology.
Table 4: Test accuracy on CIFAR-10 with different underlying network topologies.
CIFAR-10
Hypercube
Semantic Exponential Graph
10-class
4-class
10-class
4-class
DSGD
63.3 = 0.65
55.9 = 4.11
64.0 0.26
60.7 + 1.82
Gradient Tracking
61.0 + 1.34
60.2 + 1.13
62.4 + 0.53
62.4 + 0.89
DSGDm
73.2 + 0.09
45.0 + 5.90
73.4 + 0.13
51.5 + 7.80
QG-DSGDm
73.0 = 0.31
62.9 = 3.68
73.4 + 0.58
70.2 1.09
DecentLaM
72.9 0.24
69.1 + 4.05
72.9 0.73
71.2 + 1.72
Momentum Tracking
72.8 = 0.15
72.7 0.28
72.7 + 0.33
72.9 + 0.07
C.2 Results with Other Heterogeneous Setting
In Sec. we show the results when the data are distributed such that each node had data of randomly selected & classes. In this section, we show the results in another heterogeneous setting, where the label distributions of cach node determined by Dirichlet distributions Hsu et al. 2019).
Table lists the results when we distributed data using Dirichlet distributions. The results indicate that Momentum Tracking is more robust to the data heterogeneity than DSGDm, QG-DSGDm, and DecentLaM in both cases where we use Dirichlet distributions and where we use k-class setting.
Table 5: Test accuracy on CIFAR-10 with different a.
CIFAR-10 + VGG-11
a = 10 (homogeneous case)
a = 0.1 (heterogeneous case)
QG-DSGDm
89.7 + 0.07
87.2 + 1.54
DaM
90.1 + 0.28
88.6 = 0.99
Momentum Tracking
90.5 + 0.01
90.2 = 0.37
C.3 Initial Value Analysis
In this section, discuss the initial values of c; and u. Table 6 lists the test accuracy for Momentum Tracking when we initialize and to zero and when we initialize and as in Thcorem [ The results indicate that the Lest accuracy are almost equivalent on both settings. Hence, Theorem [ requires e and u, to be initialized to -- (v (0), (()))
E (ax initialized to zeros without any impact on accuracy.
(0), (())) However, in practice, C; and u, can be
C.4 Comparison with RelaySum
which is one of the methods that are most robust to data heterogeneity, and RelaySum with momentum (RelaySumM). Table lists the accuracy on CIFAR-10 with VGG-11. The results indicate that RelaySumM is more robust to data heterogeneily than Momentum Tracking and outperforms Momentum Tracking in the 2-class setting, However, the convergence rate of RelaySum is proven to be independent data heterogeneity only when the momentum is not applied, and it remains be unclcar whether the convergence rate of RelaySum is independent of data heterogeneity when the momentum applied. Thus, is clear advantage that the convergence rate of Momentum Tracking is proven to be independent. of data. heterogeneity for any
In this section, compare Momentum Tracking with RelaySum Vogels al. [2021
16

---

Published in Transactions on Machine Learning Research (9/2023)
Table 6: Test accuracy on Fashion.MNIST, SVHN, and CIFAR-10 with LeNet. "k-class" indicates that each node has only the data of randomly selected & classes.
FashionMNNIIT
10-class
8-class
6-class
4-class
Momentum Tracking
89.5 + 0.36
89.4 = 0.05
88.9 + 0.47
86.8 1.56
Momentum Tracking (c. u
(0)
0)
89.5 + 0.38
89.4 = 0.04
88.7 + 0.63
85.8 + 1.53
SVHN
10-class
8-class
6-class
4-class
Momentum Tracking
92.6 + 0.32
92.4 + 0.40
92.3 + 0.23
91.7 + 0.53
Momentum Tracking (c: - ui = 0)
(0)
92.5 + 0.34
92.3 + 0.50
92.2 + 0.29
92.0 + 0.81
CIFAR-10
10-class
8-class
6-class
4-class
Momentum Tracking
72.9 + 0.59
73.0 + 0.49
72.6 + 0.41
70.7 = 1.38
Momentum Tracking (c: (0)
ui (0)
0)
72.8 0.35
72.9 + 0.32
73.0 + 0.41
70.7 + 2.00
momentum coefficient 3 [0, 1). The main objective and contribution of our study not to achieve state- of-the-art, but to propose method with momentum whose convergence rate is proven to be independent of the data heterogeneity. We believe that our proof is helpful for future research that will attempt to analyze the convergence rates when the momentum is applied (e.g., the convergence rate of RelaySumM)..
Table 7: Test accuracy CIFAR-10 with VGG-11.
CIFAR-10 VGG-11 10-class
2-class
DSGD
91.3 0.12
71.1 2.82
Gradient Tracking
88.1 + 0.14
83.0 + 0.04
RelaySum
91.1 0.13
89.0 0.15
DSGDm
92.2 + 0.09
39.6 + 5.92
QG-DSGDm
9
77.8 1.96
DecentLaM
92.1
RelaySumM
92.1 + 0.13
89.3 0.76
Momentum Tracking
91.9 0.06
87.0 + 0.48
C.5 Comparision with ABm and GTAdam
In this section, we compared Momentum Tracking with ABm (Xin & Khan 2020 and GTAdam (Carnvvlee et al. 2022), showing the results in Table S The update rules of Momentum Tracking are slightly different from that of ABm and GTAdam, but the results indicate that they can achieve almost the same accuracy. However, as we mention in Remark 2 ABm and GTAdam are proven be independent of data hetcrogencity only in the strongly convex setting. Thus, Momentum Tracking is the first method with momentum whose convergence rate is proven to be independent of data heterogeneity in non-convex and stochastic settings.
C.6 Learning Curves
In this section, we present the learning curves for the results whose final accuracy are presented in Tables 2 and 3 Figs. and 5 show the learning curves for FashionMNSIT, SVHN, and CIFAR-10, respectively, with LeNet. F gg.. and 7 show the learning curves for CIFAR-10 with VGG-11 and ResNet-34, respectively.
17

---

Published in Transactions on Machine Learning Research (9/2023)
Table
Test accuracy on CIFAR-10 with LeNet.
10-class
4-class
Momentum Tracking
72.9 0.59
70.7 = 1.38
ABm
71.0 0.20
71.1 0.20
GTAdam
71.4 + 0.56
67.7 3.20
When the data distributions are statistically homogeneous (i.e., 10-class), the results indicate that DSGDm, QG-DSGDm, DecentLaM, and Momentum Tracking are comparable and can achieve high accuracy faster than DSGD and Gradient Tracking. When the data distributions are statistically heterogeneous (e.g., 2-class and 4-class), the results indicate that the learning curves for Momentum Tracking more stable than those for DSGDm, QG-DSGDm, and DecentLaM, and Momentum Tracking outperforms all comparison methods. In particular, in Figs. 6 and 7 the accuracy of DSGD, DSGDm, QG-DSGDm, and DecentLaM continue to oscillate the final training phase in the 2-class sctting, whereas the accuracy of Momentum Tracking and Gradient Tracking converge the 2-class setting as well as in the 10-class setting. Therefore, Momentum Tracking more robust to data heterogeneity than DSGDm, QG-DSGDm, and DecentLaM.
10-class
8-cless
6-cless
4-cless
90
90
90-
90
80
70-
50-
DSGD
40
40
Gradient Tracking
40
40
D560m
30
30-
QG DSGDm
30
30-
20-
20
20
20
Momentum Tracking
10-
10
10
10-
300
Epoch
Epoch
Epoch
Epoch
Figure 3: Learning curves on FashionMNIST. The accuracy is evaluated per 10 epochs.
10-class
8-class
6-class
4.class
90-
90-
90
90-
70-
70-
60-
60
60
60-
50
DSGD
50
50
40
Gradient Tracking
40
40-
DSGDm
30-
QG-D5GDm
30
30-
30-
DecentLaM
20
Momentum Tracking
10
10:
100
300
100
200
100
100
200
Epoch
Epoch
Epoch
Figure 4: Learning curves on SVHN. The accuracy is evaluated per 10 epochs.
18

---

Published in Transactions on Machine Learning Research (9/2023)
10-cless
8-cless
6-cless
4-cless
70-
60
60-
50-
50
50
40
40
40
DSGD
Gradient Tracking
30
20
DacentLaM
QG DSGDM
20
20-
20
10
Momentum Tracking
10-
10-
160
200
360
500
160
260
360 Epoch
460
160
200
360
160
2á0
360
40n
Epoch
Epoch
Epoch
Figure& 5: Learning curves on CIFAR-10. The accuracy is evaluated per 10 epochs.
10-class
4-class
2-class
90
80
80
80
70
60
Accuracy
60
Accuracy
60
Accuracy
50
DSGD
40
Gradient Tracking DSGDm
40
40
Mumy pam
30
QG-D5GDm
20
DecentLaM
Momentum Tracking
800
1000
200
1000
200
400
1000
Epoch
Epoch
Epoch
Figure 6: Learning curves on CIFAR-10 with VGG-11. The accuracy is evaluated per 10 epochs.
2-class
10-class
4-class
100
Accuracy
Accuracy
Accuracy
DSGD
Gradient Tracking DSGDm
QG-DSGDm
20
DecentLaM
20
Momentum Tracking
150
300
450
600
750
150
300
450
600
750
150
300
450 Epoch
600
750
Epoch
Epoch
Figure 7: Learning curves CIFAR-10 with ResNet-34. The accuracy is evaluated per 10 epochs.
19

---

Published in Transactions on Machine Learning Research (9/2023)
C.7 Synthetic Experiment
In this section, evaluate the convergence rate in more detail using synthetic dalaset. Following the previous work @Koloskoaa et al. 2020), we set the dimension of parameter to 50, the number of nodes to 25, and the network topology to a ring consisting of N nodes. We then defined the local objective function fz) to be 2|l A1 bill where A, == i//NN and b, are sampled from NV Ç //1²),, and we defined the stochastic gradient (a; G.) be (a) e where drawn from (0; o( /d1). For all comparison methods,
the step size r to 1.0 10-4.
Figs. and 9 illustrate |V with respect to the number of rounds when vary data heterogeneity Ç² as {0, 25, 50} and set o² to one. The results show that Momentum Tracking converges in the same manner regardless of data heterogeneity <², On the other hand, for DSGDm, QG-DSGDm, and DecentLaM, [[)]] increases as data heterogeneity 5² increases. Hence, these results are consistent with our theoretical analysis that the convergence rate of Momentum Tracking is independent of data heterogeneity.
z² =0
ç² =5=25
ç² =0
10¹
10a
10a
10a
[V((2))2
10A
[V((
10a
DSGD
Gradient Tracking
10-1
10-1
10-1.
DSGDm
10-1
DecentLaM
Momentum Tracking
500
1000
1500
2000
0
500
1000 1500
2000
500
1000
1500 2000
Round
Round
Round
Figure 8: Comparison of the convergence in the initial training phase the synthetic experiments.
g² =0
z² = 25
2² =5
10
10a
10a
10a
10a
[V/
[V/(2
[ff()))
10P
100
DSGD
Gradient Tracking
10-1
10-2
10-7.
DSGDm
QG-D5GDm
10-4
10:4.
DecentLaM
Momentum Tracking
5000
10000
15000
0
5000
10000
15000
5000
10000
15000
Round
Round
Round
Figure 9: Comparison of the convergence the synthetic experiments.
20

---

Published in Transactions on Machine Learning Research (9/2023)
D Proof of Theorem 1
D.1 Technical Lemma
Lemma 1. For any a. y E R2, y > O, it holds that
| + yll - (1+
1|=1) +1+
(13)
Lemma 2. For any a1.. aN. it holds that
N Σ a N
|a.11
(14)
Lemma 3. For any a, y E R2, 0, il holds that
2(x, y) S > 7 |1
(15)
D.2 Momentum Tracking in Matrix Notation
We define U X cit, vF(X()))))) and (x((()) as follows:
U = u1 /xx x = a
c0 = , x
(F(X();)g)) = (F (g)) ),.., (E
vf(x()) = -VFi(aaaa (VI(a)))..,,VMMM())))
Then, the update rule of Momentum Tracking then be rewritten as follows:
U(++1) (r VF(X();
(16)
((++1) = ( - -Cr)),
(17)
C(r+1) = -U( + +(+H))
(18)
where (0) and (()) initialized as follows:
U(0) 1
3 (0 N
(
3 (VF(X(); (())) - (0)
D.3 Additional Notation
We define the update rules of d, and e, as follows:
d = (d( + Vf((()))
(19)
e (++1) = Be(") + f(())))
(20)
where d 1-3 (V)( - ((()())) )) and e 0. Note that it holds that d g(r) for any round
2 0. Then, we define D and E as follows:
(r))
(
EGr = (e.")....,,
The update rules of D and E can be written as follows:
1 (D (f(x()))
(21)
Eir+1) = 3E( N \
(22)
21

---

Published in Transactions on Machine Learning Research (9/2023)
where D and (O0) are initialized as follows:
D
1 (Vf(x()) (1)
vf(x())
E E
Note that d, eis D, and E are the only variables used in the proof that do not need to be computed in practice in Alg. [ We define E, &, and D as follows:
g(r)_
1 E
x
(r) x()
N
F²
g(r)
1
R
(r--1) - c(rr) EE++1) /2
N
F²
D(r)
1
E
( D - E(r+1) + (r))
Inspired by Yu et al. (2019), we define 2 as follows:
g(r) (t())
if r 1 a 1-3 5(-1)) otherwise
for any a and t Ei as for any " av. Then, E|]] denotes the expectation over all randomness that occurs during training (i.e., (e/"),.)) the expectation over the randomness that occurs at round r (i.e., }2).
In the following, we define =a-
Jrr), and [, denotes
D.4 Proof Sketch
In this section, we briefly summarize our proof technique. Our proof is based on the analysis of DSGD Koloskova et al. (2020) that uses the upper bound of the consensus error E. We extend their technique to deal with data helerogeneity by decomposing the inequality about the consensus error into (i) the inequality of the error between global and corrected local momentum & and (ii) the inequality of the error between update values of global and uncorrected local momentum D. While bounding the latter error is momentum correction term, which makes
rather straightforward, bounding the former error requires the error recursion contractive; otherwise, the error between global and local momentum results in the heterogeneity term in the final convergence error. In the following, we show the proof sketch and explain in more detail how to bound from above without using 5²
We derive the inequality about the consensus error as follows (See Lemma 14
E(++)) s (1--)) P
9
9 Np
Σ
E u (++1))
+ E (
E represents the the error between global momentum e,(= é) and corrected local momentum (d, c;). Thus, intuitively, if we remove the tracking term c; from Momentum Tracking, & becomes n Σ; El|d, - e which causes the data heterogeneity ç² to appear in the upper bound of E. In the following, we explain how to climinate g(r) and ς from the upper bound of g(++)), which is the most important component of our proof.
To bound from above, we derive the following two inequalities (see Lemmas 15 and 16
144TA g(++1) S (1 (1- g()) + D(r)
1832
22(0)) + Cr.
p
p
2,32
+ 32L (r)
D(++1) < 1+ 3
D(r)
+ Cz.
1 f2
where C1 and C2 are variables independent of E, D, E, and 5 Here, the most important benefit to adding the tracking term G₁ is that the coefficient of gir) becomes less than 1. (i.e., {) < 1). Roughly speaking,
22

---

Published in Transactions on Machine Learning Research (9/2023)
the above two inequalities imply that & and D become gradually smaller because (1 5) 1 and hold for any 3 E [0, 1).
20
1
1+3²
Next, we derive new inequality by combining the above three inequalities. We define an auxiliary error term ② follows:
e
=(r
+
36 p
g
AB D22
pd
where A 0 is defined in Lemma 17 Then, by combining the above three incqualities, we obtain the following (see Lemnna 17
((++1) S (1 (1-
P) ( C3.
where C3 is a variable independent of E, D, and 5², and 2 defined in Lemma
Using = < Q and applying the above inequality recursively, obtain (see Lemma 18
(r+1) < (((+))) < (1- + (0) + Ca.
where C₁ is a variable independent of E, D, E, and 5²
p Using (1 - F) < 1, it holds that (1- +)++ (0(0), Finally, using this inequality and the fact that C4 and ( are independent of x² due to the assumption of initial values, we can eliminate & from the upper bound of and derive the upper bound of E that does not contain Ç² as follows (sec Lemma 19
4L
E
R
||²
+ 40L2t
10 +
29
864 p²
o o²
R - P=0
2
(1 - 3)
R=0
These are the essential techniques to bound E ((r) from above without using 2² and make the convergence rate independent of ?
23

---

Published in Transactions on Machine Learning Research (9/2023)
D.5 Useful Lemma
Lemma 4. For any round 2 0, it holds that e(r) = 0.
Proof. For any round 2 0, we have
N
(r) - -uj (
u (r+1)
+
i=1
j=1
i=1
N
(r+ 1)
u
W ij
+
u
i=1
Because W is mixing matrix, we obtain
N
N
(r+1)
(r)
jml
Since we have
N
N
1 N (0) :4:
Σ
= 1
VF
Σ
V (a) (0)
=0,
8
N ==1
we obtain the statement.
Lemma 5. For any round 2 0, it holds that
(1)) ma(++))
Proof. We have
N
N
(r+1)
W Wyyze! - (r(((++1)) - c(())
N
i=1
j=1
N
Wij - -
/=1
The fact that W is a mixing matrix gives
((++)==))
Then, using Lemma 4 get the statement.
Lemma 6. For any round 0, it holds that
N 3 N Σ
((++1) (r)
(r) (
1=1
Proof. For any 2 1, we have
g(++1 z(r)
(r(++) -((r))
1 (x(") -x (1)-
?7
ū (1++))
1 n13
3 (())
+
1 B
77 1
(E
1 3 N
24

---

Published in Transactions on Machine Learning Research (9/2023)
where we use Lemma
When r 0, have
x(1)
1
(x(1)
- (
1- B
7 ū (1))
1 B
7 N
1 3 N
where we use T 0. This concludes the proof.
Lemma 7. Suppose that Assumptions 1
2
and
hold. For any round R 2 0, it holds that
12 (1
R
N
1002112 N(1 - 3)
Σ E p
E
R.
3)4
i=1
Proof. From Lemma
we have
E (r)
z(r)
113 (x)
2
B
32172
1 N
E
Σ
3
Σ
V V. (1) c c((0))
(1 - 31-
for any r 2 1. Defining s(r) = Er= Br- we obtain
E (+) - 2<>) ||
1822
g Br-k-1 k-1 1
11) E
(1)
(8),
(1 (1-3)²
1) N
Si
(a)
8 E
1
N
(K) (1))
(1-
N
82,1²
1
fi
V
(K)
8OO31 2
gr-k-1
3)²
N
N(1 3)
k=0
where we use Jensen's 's incquality in (a). Using (r-
1-3: we obtain
E (r) - =000|²
=
B2nz
r-1
3
N
(0)
+
3²021²²
(1
3)3
N
N(1 B)
k=0
Recursive addition yields
n
E
x (r) - 2(/0|/
-
<
3292
R r-
E
1
N
(M))
+
N(1 1391 R
80021²
(1 B)3
N
3292
R-1 Σ
N
R
32022²
R
3 k-
k-1
313
N
N(1 - 3)
r=
82'7
N
8202112
E
(K)
N(1 - -331 R
25

---

Published in Transactions on Machine Learning Research (9/2023)
where use Σr gr-k-1 1 1-3 in the last incquality. From the definition of z00, we have | z 101 = 0. This yields the statement.
Lemma 8. Suppose that Assumptions
and 4 hold. For any round r 2 0, it holds that
E o ( 11:0)=5())
- 41 -
+ 2 aati
2n |/(
Proof. From Lemma have
B, ((+))) - x/1 =,
(7
(I
N
3u
1
V
fi (xo
N i=1
N
(
2n²²
[z( (r))
Then, T can be bounded from above as follows:
= V)((E()) V
T =
N
13
2
N
fi( (7)) - ()((E(()))
2 [
N
2
(f(()("))) |)(()()))|
+2 {
N
2T N
Σ
10
|22 +2 \
N
Then, we obtain the statement.
Lemma 9. For any round r 2 O, it holds that
E
(r))))
2
g k (t)))
B
Proof. We have
E 1e
=E Σ 3 (w
where we use e(()_ 0. Defining s(r) = Σx gr
gr we obtain
e((+1) 2 s E
gr-k k s(r) (E()()))
A=0
(r)
gr b
V (+))
where we Jensen's inequality. Using (r) <
3-3: we obtain the statement.
1
26

---

Published in Transactions on Machine Learning Research (9/2023)
Lemma 10. Suppose that Assumptions 1
12
2
3.
and hold. For any round 2 0, it holds that
E
D
-
L2
g
kg()) +
502
N
1
B
(1 - 3)3
k=0
Proof. We have
E
D - v((+1)
- ?
=
E
Σ rr - + U(0))
k=0
Defining s(r)= = Ek=0 gr we obtain
E p(++2) - u(++1)
= (0(1)
s(r+1] (V(( (F(X((() + s(r+1) (D(0) - -
g
g-11
4=0
(a)
(++1)
E
vf(x(() (4) - VF(X 1/- + s((+1)) ( - u
14
((( ||
k=0
(1(++
VF(X (0) ;(01) 1|2
+
(1 3)2
+
2s (1))
3r+1 E
Vf(X (0)
111
1
VF(X (0); (0) 111 ;
B)2
N
N
oor + 4s(r+1)
(r+1)
- ,)(x + (1++
ootiNo* (1- 8)2
k=
where we use Jensen's incquality for (a) and use x = (0) for the last incquality. Then, using s(r) S 1 we obtain
1-3:
_0(+1)/ 2
E
$
3 K
()( - )
+ No²
- (1-3)3 (1 - 3)3 gr-1
+
4No² 2
3
F
k=0
$E(0,1)
v)(x()) (x)) 1/2 5No2
S
8
'B
1-
3
(1-
1
(M))
x(
5No2
r + (1 933
8
This concludes the proof.
Lemma 11. Suppose that Assumptions 1
2
and hold. For any round r 2 0, it holds that
1
o²
E
u
(++1)
< 1- 3
Σ gr- kg() + N(1 - 3)2
k=
27

---

Published in Transactions on Machine Learning Research (9/2023)
Proof. We have
N - V
E
u (+)))
d
(1))
= Σ
5"
Fa
k=0
==1
where we use ())) d(0) Defining s()) E E
gr- we obtain
E
ū (r+1)
1
gr-k
=
( v)(((()))
=
8(r)
N
(1 (8) (.)) -
N
k=0
k 02
E
vi((a |)(
+ +
fr
N
N
k=0
k=0
(=())) v)((E(()) ||
+ t
go gr
N
k= 0
k=0
where Jensen's inequality in (a). Then, using s(t) s 1-B. obtain
(r+1)
dir+1)
?
w
N
a²
g
E
V
(k)
|)i(a(>)||
+
1
N
N(1 3)2
k=0
1=1
L
3
1
E
(1:
o²
N
N(1 3)2
This concludes the proof.
Lemma 12. Suppose that Assumptions
1
2
and hold. For any round 2 0, it holds that
21
20²
E
(1++)
<
3r
(K)
B [5(
+ N(1 - -3)²
1
8
k=0
k=0
Proof. We have
E
ū
(++1)
= (r+1)
+ J. d(r- 1//
13
2E
(+
+ 2E
d
From Lemmas
and
we obtain the statement.
28

---

Published in Transactions on Machine Learning Research (9/2023)
D.6
Main Proof
Lemma 13 (Descent Lemma). Suppose that Assumplions 1 2
and 4 hold. If the step size n salisfies
1 1-3 3
-
4L
then it holds that for any round r 2 0,
Ef(z(r+1)) S ()()()) +
1,2n
(x()) 100--011 --1>
1.2n g())
+
3
1-3
N
Lo
1
(1 (r))
1
E \(
E
V
+
4(1
3)
N
4(1 3)
2N - 332
Proof. From Assumption 3 and Lemma 6 we have
(x((z(+)))
{ + (V) g(++1) - 2(1)) + L Er
-0+1))=x(01 - $
2
= =(( 1- 3
"
V)(z(n).
1
N
v(((a(("))
Li7
E,
1 N
(F (())
N
2(1 3)2
N
f(z(r)
7
1- 3
N
Lap
1
N
20217
Σ
+ 2(1 - 3)2
N
2N - B)2
i=1
=)( + 1- 3
"
( -()E())
N Σ {((a)
73
N (((ao
Tap
1 N
To2212
17
V)(a()),
+ 2(1 - 992
v
(a ())
+ 2N - 3)2
1- 3
N
N
i=
72
We can bound Ti from above as follows:
T1
v (
- -
l|
1
1 N
N
v
(((
4
1=1
1 x -0) z/1l
p
+ 4
N Σ
N
(7))
We can bound- T2 from above as follows:
1 N
N
TT2 ()()(r)
1
Σ v((((((")
l|
2
1
Σ (((lo(1))
2
N
2
2
1
())) - "
V (3))
||
Vii (7)
2
2
2 N
I 1
(2 x.
-
1
|
1
{(( (m))
2 N
N
29

---

Published in Transactions on Machine Learning Research (9/2023)
Then, we can bound T3 from above as follows:
f((x )
T3
N
(i( ())) -
+2 {
2
2
\)((a(>))| +2 {( ||
5
21
Σ
|a(") - 2|1o + [(()))))|
N
By combining them, we obtain
(
S {(( +
Li x()) - -x0>//²
17
1
Σ
V {((()("))
B
4(1 3)
N i=1
12
+ In
In
||<
Lo²17² 2N - 3)2
nE
n
+
- 3 2 1-3
1 8
2 1- B
Using 1) <
1-8 27. we get the statement.
Lemma 14 (Recursion for E). Suppose that Assumplions round r 2 0,
2
3
and hold. Then, it holds that for any
E(++)) <(1 P ") + 2 + 9 n'E (i(+tt) - D(++1) 2 + Np
E(++1) 2
E
Np
Proof. Because ΣN |la; - a|12 s EN |ail? for any a... aN E Rd, we have
NE 18 = ((-1))) +
- x -
SE
< x
- xx(-1))
Then, we have
[x(++)) - x1++1|/2 < x (r++)) x(00|²
| - ((((++1)) - - - x(r)12
(1+ W xxm0|² + (1 + サ (1++1) -
F
(1+r)(1-p)) x x3 - x + (1 (1+ 1 - c(r) 2
30

---

Published in Transactions on Machine Learning Research (9/2023)
By substituting y and using p 1, we obtain
x ((+11 - -x(tt)/ ?
Σ (1 2) (x)) x((r) 1
+ 1 -
c
2
(1 P
(+)) -x(0
3 1²²
[r(++1) + D(++1) E(++1) c(r))
2
+
p
14
2) ((()) -x(1
P)
9 1 [((+))) D(++1) 11 " ((rtt)) -ct) - E6+ "" E E
+
p
This concludes the proof.
Lemma 15 (Recursion for E). Suppose that Assumptions round 0,
and hold. Then, holds that for ony
g(r+1) < (1- - 2) +
1852
D(r)
+ Np
24
R
(((+1) - D(++1) 2
2 p
144T,
1²=(()) + 72
1441?
36I2021p
+
p
p
Np
Proof. We have
(rr+2) - - E(r+2) 2
E
12(+2)-(00 (CC) U(++))) U(++1) E + D(++1) D E(++1) 2
E
(D(+t)) 11+ (D
(D(tt)) ((r)) E(++1)
+ + + 1)
(1(++)) - ((+1)) ( -I)
+ >
D(++2) D(++1) + E(++1)
(r+2)
D c E((+1)|
(1 (1+7)(11 p)
(U(+t)) ((+1))((W - -1) 2 D ((+11) E(++1) E (r+2) + 2(1 + E
+ 2 +-(1+>-1) }E
F
where we use Lemma
and E(++1)= 1/ D( the last inequality. Then, we have
D ((++2) ((++1) 2(++2) ?
E
F
(0)
B D(++1) - ((r) (
<
+2(1+
((++1) D(++1)
I -1
+ + -2(1+~1\)B D(++2) D(++1) ((--1)
E
F
(1+>)(1 p) D ( -C() E(++1)1 |2
+ 8(1 7 ')E (((+1) -
+ +2 ((++2) ((+11) + E(r-1) E
31

---

Published in Transactions on Machine Learning Research (9/2023)
where || llop denotes the operator norm. In (a), use the following definition of the operator norm: [W-Teel 2 [W-fio for any v E Rd \ {0). In (b), we use Gershgorin circle |iail
W| - oopp = (o |+ll
theorem and the fact that W is mixing matrix. Substituting ? 2 we obtain
E D D(++2)
C(++1) - E(r-2) |
S
(1
E
D(++1)
ctr) Eir+1)
+
24 -
6 E D D(++1) B(r+1) - E(r-2)
p
Then, we can bound T from above by expanding D(++2), D(++1), E(++2), and E(++1) as follows:
T
D - D E(r) - E(r+1)
+ 3
V Vf - v)((
+ 3E
V vf(X 111 N Vf(x
3 E D (()) E E 2
x ( x(0)
+ +6L2E
Using Lemma
obtain
s 3
+ E(r) E((+1)
6L2
+ , + N(24L 12 (r)
N
This concludes the proof.
Lemma 16 (Recursion for D). Suppose that Assumptions round 2 0,
1 2
and hold. Then, it holds that for any
2,22
32
B2
D(++1) <
D(r)
((r)
E (+)
82
1- 32
1
1 1-
32L211² 2
81.20211
E
32
N(1 52)
Proof. We have
E D()+2)_ - (+++) E(r+2) - 1(++1) 1|2
13
14
(1+7)
D(r+1) D(r) + E(r) (r
F
+ + ")E
+ +211+ ")
Vf(X 111 Vf(x
5
(1 + 7) ((++)) | D(r)
- D(")) + E - E
+ 4 +1 x ((++))
x -
1-s²
Substituting 7
T4.37, we obtain
E D(r+2) D(++1) 2()+2) 1(++))12
2,32
B D(++1) (()) + E(r) E(++1/
812
E (r+1) x(r)
< 1 82
32
32

---

Published in Transactions on Machine Learning Research (9/2023)
Using Lemma
g
obtain
( D(r+1) E(r+2) E(rtii|
E
2,32
E D(++1) - -((r) + E(r) Eir+t)|l
<
+ g2
F
N( 32L E(r)
+ 16
(r))
32
|
8I30211
1- E
E
1- B2
1 - fa
N
This concludes the proof.
Lemma 17 (Recursion for E, E, and D). We define E R and A E R as follows:
28²p p
648
+ 4,
A =
32
2
I+0
Nole that it holds that t 2 4 and A > satisfies
0. Suppose that Assumplions
2
and 4 hold, and step size nI 3
P
7 5
8L1
324 +
240 1-33
Them, it holds that
g(+1)
36
1/ g((+)))
AB
122(++1)
p2 p
p3
S (1
P
(E
36
g(())
Ag3
D²²((r)
p2
pa
+ "
v
(1))
2
+
1
9
864 p²
" ((++t)
- -
D(++1)
Np
2
16A484
9
B +
021²
+ n3
2592332
n
L
1 32
Np
D
Proof. From Lemmas
14 and 15
we have
g(++1) <1 ?
(=()) +
-
+
9
"
( - (r+1))
+ 9
n"
E(++)
2
Np
Np
36
1/² g((+))
< (1 - p 36
g())
+
64832
1²2 ((r)
+
5184L
(/=00)
+
259283 L2
17 $1
p
2 D
pd
ndd
Dd
Np F Ulr+1) (r+1))
864
5184L2
1296L202m7
+ p3
Np
Then, from Lemma 16 we have
A
D
(1 + 82 (())) 3
2A34
(1 33) 11 11())) 16AL2 34
"E [
pd
(1 3²)
+ (1 - 33) "B |/(
32A
N(1 - 33) 172
L'
Using 172 <
x²
and n² <
n²
_432 : we have 1-px)
128L (162+
(1
P
51841A
11 +
1
(1 (1-32 -322p33 11²
12
[(t) 5
<((1
I2 1² E(r) < (1 4 P)
2
1
4p
33

---

Published in Transactions on Machine Learning Research (9/2023)
In addition, we have
9 n² + (1 2
12 )
36
g0) (1
P. 36
8
4 p2
64852 pd
2 + (1+ + 82) 1/
2A.4
D(r) 648
20
A32
D(²
=(1
{) n3 D(2)
AB
A
+ 32
ps
Then, using 1 2 4, we obtain
AB2
[(++)) + p
7/ g((+1)
pd 11 D(((++
+
I (1 7 (E(r)
P
+
36
g(r)
AB2
D22((r)
p
pd
L
32AB2
11'E |
+ +5184
B2
9
864
1/ 2BB
[
D b(t)))
Np
p
9
Eir+1) ?
F
Np
I
2592 + 16A,34
E
u (r)
pd
1- 82
L²o²
1296 + 8A32
17
Np
1 B2
Using 1/2
p²
have
316.2 A8
1
32
1
+
5184 BBB
V
nd
1
- g2
Using 2)2 <
we obtain
(162
A02 1-
L²o² Np
8A3/2
d²12
1296 +
11¹
132
Np
This concludes the proof.
Lemma 18. We define t and as follows:
2B2pp
648
t 1 32
4,
A
2.a I+
Under the same assumptions as those in Lemma
17
it holds that
R
R
14
Σ
E
(K))
(1 - 33 R.
where (r is defined as follows:
(r)
2 ()()()))
|
+ Np
9
864
n U(++1) D (r+1)
p2
F
L?
16A84
+ 3
2592,32
17
(r)
+
E(++1)
1 8
Np
34

---

Published in Transactions on Machine Learning Research (9/2023)
Proof. We define ((r) = E()) + 20 1 + 1) From Lemma 17
we obtain
p
((++1) ] (1 ! (0(r) + w)(() +
p
r
r
s (1 - P)+ 010)
1 (1
P
((() p
- (1
P yr
p
km0
km0
Using (1-P)- p? we obtain
(1 2 yr k (1)) (B) + to?2p
(r+l)) 5 P 2 (0))
21-1))
+
p2
k=0
Then, for any R 2 1, we obtain
Σ ( <
n
(1
P r t
+
R
D 1
+
10211²
R
D²
r=1
K=
R-1
R
to²n? p2 R
Σ
(1
P y
(0)
Σ
(T)
Σ
(1
p P-r-k-1
k=
p=
<
t
+-
R-1
Vilk)
+
t0212
R,
p
p2
k=0
where we use Em1 (1 / S a and E (1 -
-)-
S 1 in the last inequality. Then, from the
definition of gir), we have
((0) ( (( - E(1) |
F
1
1
E
(0)
N VF (0)) 111 -F(X
2 + 1 : N
(1 B)2 N
14
2
1
/ (0) VF(X 00 1000
E
(1 - 8)2 N
2
N \
(0)
+ (1 - 3)2
E
N
4
B)2 02
where we use (0) - in the last inequality. From the definition of D(r), we have
1 E (8 ()-10 - VX(X()) ( 11 O.
Dio)_
F
Then using x0)) = (0) (i.c., = = =0), we have
14
) < (1 -1- 3)p
Here, the above upper bounds of g() and O(0) are attributed to how we choose the initial values 50 c.0) (()) and e (0) for i V. Then, combining them, we obtain
R R- 1
14480212
to?
Σ
(r)
<
(A)
+
(1 3)pp3
p²
km0
t
R-1
(b))
(1 33 R.
145t02
p k=
35

---

Published in Transactions on Machine Learning Research (9/2023)
where p (0, 8 [0. 1), and R 2 in the last inequality. Then, using O 2 E(r) and E 0. we obtain the statement.
Lemma 19. We define 1 E R and E IR as follows:
p p t ==
648
+
+,,
A =
1- g2
1+
Note that it holds that 2 4 and A > O. Suppose that the same assumptions as those in Lemma 17 hold. Them, iʃ slep size n salisfies
p
B)p
(1
B)p }.
S min
324
24 1-
2L,
1(5
432 p
8L, 5t
it holds that
Σ (r)) 5
Σ
v (1))
+
40L2t
10 +
29
864
0² o² + 1).
2 k=0
(1 -1- 3)
p2
r=0
Proof. We define ((() as follows:
(r(r) = =1pB V
+ Np
9 +
864
1/
((ttt) (x+1)
p2
+ 2d
1
2592332
164
A (u()))
+ No
2
|
1 32
Using e(r) e and Lemmas
10
and
12
we obtain
(r)
<
2
V
(1)
9
1)²
gr-k
V
3)p
K=0
21
16A8
2592/32
11
Σ k-
(1 p)
1- 32
L?
864 p²
9
"
- (*))
(1- 3)p
2
16A.34
+ (1 p
2
+
g k-
1-1
1 82
864 2
+ (1 8)3p
9 +
2122
16AA31
2592
2
N(1 - pp
g2
36

---

Published in Transactions on Machine Learning Research (9/2023)
for any round r 22 1. Then, we obtain
R
Σ
T
1
11
2
E
fl
(r))
2
p
R
9
(())))) 1
8r
+ 1)
(1
3)p
k=0
2L
16A.44
R
2592,32
"
Σ
(1 - 3)
1- 82
0
1.2
864
9
1/2
Σ
g
pT-K=(A)
(k)
(1 3)p
p²
K=
2L
16A3*
R r- Σ
2592
"1
8
(1 B)
1- 82
k=
864 p2
+ (1- $)
9 +
02 0²122R R
2L2
16A8**
25923 2 + 1 32
o'1)²R. R.
N(1 - B)2p3
Then, we obtain
R
(r))
< -11
1
R
E
V
(T) 2
f(
p
r=1
1=1
9
V
{)((())
Σ
gr-
3)P
k=0
r= [1.A]
21
2592
16A8*
()()(())
|?
2
Σ
gr-k-1
8)p
1- 52
k=
r=k+1
1,2
864
R
9 +
2 p2
Σ
=
Σ
gr-k
(1 B)p
r=max(1,
2T,4
16A.34
R-1
2592,32
11
Σ (()
Br-k-1
(1 - p)
1 Bz
k=0
r=
864 1
9 +
02 02 R
8)3p
21,2
16A81 2592.32
0 R.
N(1 p3
1 82
37

---

Published in Transactions on Machine Learning Research (9/2023)
1 Using Ep 8--h-1 S 1-B
and Σ Zr=max{1,h) gr s 3. we obtain
Σ
(r(r) -
1|
2
V
p
R
+ 11
(1 --DP
k=0
2L'332
2592 + 16A
RR
+
n7a
Σ
V
(1 - pppp3
1 88
k=
La
864
R Σ (R)
9
1/2 p2
(1 --ppp
2592 + 16A822
R-1 Σ k=
+
77
(k)
(1 3pp
1 88
5
864 p2
+ (1 33
9+
R²R12R
32.
16A,3
2592 +
0211² R.
N(1 pppp3
1 g3
Then, using u (0) and Lemmas
and 10
we have
(0) S
1 2
2
12
+
5
(9 9+ 864
0²n2²
(1- 3)P
(1 -ppppppppp
p²
Then, we obtain
R
V
(r)
< -17 2
E [
p
r=u
18
(( ||
2
+ 17
(1 (1-3)pp
2T2232
2592 + 16A132)
R
+ (1 1 pp
Σ
1- 1-
+ (1 1-pppp
2
9
864
R
(k)
D2
k==
2L
2592 + 16A,3²
R-1
1)
Σ E(K)
(1 pppp
1- 132
5
864
+
9
0 2
(1 3)3p
2L2
16A3² 2592 +
0²n R.
N(1 - p)2p3
1- 5z
Using 1/2 <
we have
3262
404 5 1-
2L2
2592 +
16A,32
1
R
v
R
V (
11-38pp
(1 3yp'"
38

---

Published in Transactions on Machine Learning Research (9/2023)
Using 1/2 <
p²
have
A8 1-32
16A
n-1
12
n-1
2592 +
n²
Σ (K) K=0
[1 - 3y2D" P
Σ )
(1 - p)
1 82
Using 172 - (262 A82 1-
we have
2L2
164,3²
8² N(1 - -8y2p R² R.
2592 +
R
N 3)
1 g2
Then, using E 1) and N 1, we obtain
n
R E
Σ (r)
(
1
1 -11
p
r=0
+ 17²
19
R Σ
V 2
(
(1 B)2p
k=
L?
864
+
110+
112
(1 - B)2p
p²
k=
5
864 p2
+ (1 - B)pp
10 +
( 1).
Using 8 E 10 and Lemma
18
we obtain
R
R \)( |
20t
(1
B)2p²
17
1L?
864 10+ +
R Σ =(K)
+ (1 2)
1/2
p2
5t
864 p2
14560'1²
10 +
22 +
1)
R
(1 8)3p²
18-33pp3
20
(1 pp 1²
V
V ((x
k=0
tL?
864
R Σ (())
+ (1 - 8)
10 +
11²
p2
km
5t
29
864
10 +
8² (R+1).
(1 8)3p2
p
p2
Then, using 2²= <
4t1.2(5+ e obtain
(1-9)3p²
R
20t
R
56
29
864
(r) <
10 +
+
(
2 0 (1- 8
(1 - -3)332
p2
Multiplying 8T,,, obtain
R
160L2t
R ? Σ
2
40I2t
29
864
2 Σ < (1 (1- 3)
Vf(a(())
+
10
o²
n²n² + 1).
(1 -1- 3)3p2
p2
km
Using 1/2 < 3201.4
(1-0)²²²
obtain the statement.
39

---

Published in Transactions on Machine Learning Research (9/2023)
Lemma 20. We define t R as follows:
2
t ==
+ 4.
1 -
Suppose that the assumptions of Lemma 19 hold. Then, step size n satisfies
11 1 (1 (
2/2L
it holds that
1
4(1 3)
(1(=0)) -1r)
2L
E V
2(R +
(R + 1)
N(1 B)
L
40t
29
864 p²
4,8
+ (1 B)
10 +
+
pa
p
N(1 - 3)
Proof. Using Lemmn
13
and Assumption 1
we have
n
E
||
4(1 (11-3) 3)
( - s²) + 41.
Σ
+ 41.
Σ =(r)
R
-=
R
E
1 N
Σ
V f (a (?)
+
20
(R+1)..
N
N(1 - 3)
From Lemma 7 we have
4L'B877
1 N N
AL28202'7 R.
4L
>
- -
E
(lr)
Σ
Σ
{(())("))
+
(1- B)
N(1 3)
==1
Combining them yields
R
V Vf(z (T))
E
-=
4(1 - 3)
(((2(0)) + 4L2 Σ E(r) (1
R
4L283172
n
1 N
E
N (1))
Σ
V (i((o
(1 (1-1113) By
1)
0=0
Y=1
2L
(R+1) + 4L'38'03'2
+ N(1 ()
N(1 B)1 R.
Using 1/2 <
(1-0) 8La
and B << 1, we obtain
R
Σ
IE
V ((a
4(1 3)
+ #4L2 (f(
>
R = +
2Lo'n
(R 1)+
AL'320'1'
N(1 - -3 R.
N(1 - 3)
r=0
Using Lemma
19
obtain
1 R
E V ())) 1
2/2 Σ59
2 0=
4(1 - 3) ([(=(0)))))
-5))
2L n
<
+
(R+ 1)
n
N(1 3)
I22
40tt
29
864
4,2
+ (1 8)3
10
+
+
N 3)) 02 [+++)1) 1).
p2
p
p²
This concludes the proof.
40

---

Published in Transactions on Machine Learning Research (9/2023)
Lemma 21. We define t R and A R follows:
2B3p
648
t
+,,
A =
1 82
2
14,82
Then, it holds that
(1 p)
1-3
p
(1- B)p²
(1- 3)p (1 - B)
I min
16L (1 (1-192)9p
783632
282
4L
8L
324
2A3² 1-
21/ 1(5p2 + 432)
8L
2/2L
Proof. Because
(1-3"pp + 282 > 1, (0, 1], and B E [0, 1), we have
783632
(1-B)2p²
1-
(1-
3)2
S min
16L
(1-8*pp + 282
7836882
4L
2/2L
From p S have
23 P
1
1+ g2
p
1-3
+ +
B2
1
23
1+9
Then, we obtain
1 P
2,32
P
3p
3p
t
1+ 32
t-3
t(t 3)
22
Then, we obtain
A < 216t²
Using the above inequality, we obtain
A
+ 162 < 216,3222
+ 162.
1 32
p(1 - p(1-
B2)
From the definition of 1, we obtain
A
216
301
162 <
+00 + 162
1- 82
p(1 -2)
216
2,3pp p
2
2,3² p
+ 4
30
+ 4
+ 162
p( 82)
1 f
1
216
4
16,3
2,38p
16
30
+ 4
+ 162
p(1 82)
8282
1
g2
I
I- 13
783632
+ 282,
p(1 - -3233
where we use E [0.1] and p E (0, 1] in the last incquality. Then, we obtain
(1 pp
pp
16L
783683
+ +82
16L
1-32 + 30t + 162
(1 11p
(1- B)2
(1 3)p
< min
8L
324 + 243²
2T. 2T /t(pp² + 432)
8LV50 5t
1-
This concludes the proof.
41

---

Published in Transactions on Machine Learning Research (9/2023)
Lemma 22 (Convergence Rate for Non-convex Case). Suppose that Assumptions 1 for any R 2 1, there erists step size n such that it holds that
3 and
4 hold. Then,
V |(()!))||
E
R -=0
(v
1 NR
1
(1=1 3
p3²
))
Lro
1
,32
(1-
(1 - B)p
where ro = f( fr.
Proof. From Lemmas
20 and
21
if the step size 17 satisfies the following:
(1 3)²p²
7 S
16L
7836,82
+22
(1- pppp
then we have
R
|
Σ
2(R + 1)
r=0
< 7( 1)
4
(1(310))-
+
2
L
40t p
10
+
29
864
4
0 0²17²
N
1
p
p²
N(1 - 3)
where we define 7 1-3-
Then, we can bound T from above as follows:
2
40
2
29
864
4,32
=
+4
10
1-
B
p2
1
82
p
p²
N 3)
PE(O.1]
T22
36620
2,32
4
+
+
3
p²
B2
N(1 - 3)
36120L
333pp p
+ 4
(1
F)p
1 8
Then, we obtain
R
1
())) |
2(R + 1)
2L ;j
36120L
353pp
<
(f(*(0))
-
+
+
+ 0212.
7(R 1)
N
(1 B)
1-
Using Lemma 17 in the previous work Koloskova et al.
2020 we obtain the statement.
42

---

Published in Transactions on Machine Learning Research (9/2023)
E Hyperparameter Settings
Tables 10
and list the hyperparameter settings for cach dataset. We evaluated the performance of each comparison method for different step sizes and selected the step size that achieved the highest accuracy on the validation dataset.
Table 9: Experimental scttings for FaShionMNIST..
Neural network architect.re
LeNet [eCunn et al.
1998
Normalization
Group normalization
Wu & He 2018
Step size
{0.005, 0.001, 0.0005)
L2 penalty
0.001
Batch size
100
Data augmentation
RandomCrop
Total number of epochs
500
Table 10: Experimental scttings for SVHN.
Neural network architecture
LeNet
LeCun et al.
1998
Normalization
Group normalization
Wu He 2018
Step size
{0.005, 0.001, 0.0005} 0.001
L2 penalty
Batch size
100
Data augmentation
RandomCrop
Total number of epochs
500
Table 11: Experimental settings for CIFAR-10.
Neural network architecture Normalization
LeNet [LCCnn et al.
1998)
Group normalization
Wu He 2018
Step size
10.005,0.00.. 0.00,,0000000005
L.2 penalty
0.001
Batch size
100
Data augmentation
RandomCrop, RandomHHorizottalllip
Total number of epochs
500
Table 12: Experimental settings for CIFAR-10 with VGG-11.
Neural network architecture
VGG-11 (Simonyan & Zisserman
2015
Normalization
Group normalization (Wu & He 2018
Step size
(0.5, 0.1, 0.05, 0.01, 0.005) /10 at epoch 500 and 750.
Step size decay
L2 penalty
0.001
Batch size
100
Data augmentation
RandomCrop, RancoomtHorizontalllii, Random RandomErasing
Total nunber of epochs
1000
43

---

Published in Transactions on Machine Learning Research (9/2023)
Table 13: Experimental settings for CIFAR-10 with ResNet--4.
Neural network architecture
ResNet-34 (He et al.
2016
Normalization
Group lizatiization
Wu & He 2018)
Step size
{0.5, 0.1, 0.05, 0.01, 0.005) /10 at epoch 375 and 563.
Step size decay
L2 penalty
0.001
Batch size
100
Data augmentation
RandomCrop, RandoomHorizontalFiip, Random RandomFrasing Erasing
Total number of epochs
750
44


Reviews:
[{"review_id": "vv72nDBrjn", "reviewer": "Reviewer_WFz3", "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 whole paper is clearly written, with its principal claims effectively outlined, making the text easy to read;\n2) The literature review contains pertinent papers related to the topic. The authors did a great job providing a comprehensive literature overview, perfectly fitting their paper to the study of decentralized methods;\n3) The authors propose a novel algorithm suitable for non-convex objectives that makes it possible to combine a momentum trick (which is a standard one for training deep learning modes) and gradient tracking - a famous approach to removing gradient heterogeneity from the iteration complexity for decentralized methods.\n4) Besides the solid theoretical results, the authors proposed an extensive set of experiments comparing the proposed method against multiple baselines with\\without momentum and with\\without gradient tracking. In all cases (except one (a comparison between \"Momentum Tracking\" and \"RelaySum\") ), the proposed method for a homogeneous setting shows compatible results. In contrast, for a heterogeneous one, in terms of the accuracy metric, the proposed \"Momentum Tracking\" considerably outperforms existing baselines.\n\n**Weaknesses:**\n1) Some potential updates can be considered in the revised version of this Paper. See section **Requested changes**;\n 2) When $\\beta=0$ (i.e., when momentum tracking reduces to gradient tracking), resulting complexity \n   $\\mathcal{O}\\left(\\sqrt{\\frac{r_0 \\sigma^2 L}{N R}}+\\left(\\frac{r_0 \\sigma L}{p^2 R}\\right)^{\\frac{2}{3}}+\\frac{L r_0}{p^2 R}\\right)$\n   is worse than the one \n   $\\tilde{\\mathcal{O}}\\left(\\sqrt{\\frac{r_0 \\sigma^2 L}{N R}}+\\left(\\frac{r_0 \\sigma L}{(\\sqrt{p} c+p \\sqrt{N}) R}\\right)^{\\frac{2}{3}}+\\frac{L\\left(r_0+L \\zeta_0^2\\right)}{p c R}\\right)$\n   from [1] by Koloskova et al. However, Koloskova et al. obtained this complexity under a stricter condition\n $R>\\frac{2}{p} \\log \\left(\\frac{50}{p}(1+\\right.$ $\\left.\\log \\frac{1}{p}\\right)$ )\nwhereas the former complexity works for any $R$.\n\n[1] Anastasia Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for decentralized machine learning. In Advances in Neural Information Processing Systems, 2021.", "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 authors introduce a novel approach to decentralized learning, incorporating momentum acceleration, that they've called 'Momentum Tracking'. \nUnder standard assumptions for decentralized optimization (see Assumptions 1-5 below), \nthey provided a convergence rate for the smooth non-convex regime of the form\n$\\mathcal{O}\\left(\\sqrt{\\frac{r_0 \\sigma^2 L}{N R}}+\\left(\\frac{r_0^2 \\sigma^2 L^2}{p^4 R^2(1-\\beta)}\\left(1+\\frac{p \\beta^2}{1-\\beta}\\right)\\right)^{\\frac{1}{3}}+\\frac{L r_0}{(1-\\beta) p^2 R} \\sqrt{1+\\frac{\\beta^2}{\\left(1-\\beta^2\\right)^3 p}}\\right)$\n, which is independent of the data heterogeneity parameter $\\zeta^2$ and holds for any momentum coefficient $\\beta$ within the range of 0 to 1.\n\n**Assumption 1**. There exists a constant $f^{\\star}>-\\infty$ that satisfies $f(\\boldsymbol{x}) \\geq f^{\\star}$ for all $\\boldsymbol{x} \\in \\mathbb{R}^d$.\n\n**Assumption 2**. There exists a constant $p \\in(0,1]$ that satisfies for all $\\boldsymbol{x}_1, \\cdots, \\boldsymbol{x}_N \\in \\mathbb{R}^d$,\n$$\n\\|\\boldsymbol{X} \\boldsymbol{W}-\\overline{\\boldsymbol{X}}\\|_F^2 \\leq(1-p)\\|\\boldsymbol{X}-\\overline{\\boldsymbol{X}}\\|_F^2\n$$\nwhere $\\boldsymbol{X}:=\\left(\\boldsymbol{x}_1, \\cdots, \\boldsymbol{x}_N\\right) \\in \\mathbb{R}^{d \\times N}$ and $\\overline{\\boldsymbol{X}}:=\\frac{1}{N} \\boldsymbol{X} \\mathbf{1 1}{ }^{\\top}$.\n\n**Assumption 3**. There exists a constant $L>0$ that satisfies for all $i \\in V$ and $\\boldsymbol{x}, \\boldsymbol{y} \\in \\mathbb{R}^d$,\n$$\n\\left\\|\\nabla f_i(\\boldsymbol{x})-\\nabla f_i(\\boldsymbol{y})\\right\\| \\leq L\\|\\boldsymbol{x}-\\boldsymbol{y}\\|\n$$\n\n**Assumption 4**. There exists a constant $\\sigma^2$ that satisfies for all $i \\in V$ and $\\boldsymbol{x_i} \\in \\mathbb{R}^d$,\n$$\n\\mathbb{E}_{\\xi_i \\sim \\mathcal{D}_i}\\left\\|\\nabla F_i\\left(\\boldsymbol{x}_i ; \\xi_i\\right)-\\nabla f_i\\left(\\boldsymbol{x}_i\\right)\\right\\|^2 \\leq \\sigma^2\n$$\n\n**Assumption 5**. There exists a constant $\\zeta^2$ that satisfies for all $\\boldsymbol{x} \\in \\mathbb{R}^d$,\n$$\n\\frac{1}{N} \\sum_{i=1}^N\\left\\|\\nabla f_i(\\boldsymbol{x})-\\nabla f(\\boldsymbol{x})\\right\\|^2 \\leq \\zeta^2\n$$\n\nComparison with existing methods, as shown in their study (Table 1), further solidifies the author's contributions: this is the first method that addresses Data-Heterogeneity, Momentum, Stochastic estimators, and Non-Convexity among considered baselines.\n\nIn terms of practical application, the authors provide empirical evidence to support their theoretical results, showing that Momentum Tracking displays greater robustness to data heterogeneity compared to current decentralized learning methods with momentum acceleration.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) I recommend the authors revisit their choice of line colors in the figures. For instance, in Figures 1 and 2, the differentiation between black and dark blue colors, representing DecentLaL and Momentum Tracking respectively, might pose a challenge for some viewers.\n2) For similar considerations, I would recommend that the authors employ marked lines in their figures, each representing a specific method. This would significantly assist individuals with color vision deficiency.\n3) Further, the reasons behind selecting the ring topology in the experimental section of the paper's main part could benefit from a more explicit explanation.", "broader_impact_concerns": "This work is primarily theoretical in nature. Hence, there is no identifiable potential for negative societal impact arising from this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3vfLtBcs7N", "reviewer": "Reviewer_8a5E", "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- This paper is clearly written. The comparison with existing methods and the literature review are solid.\n- Thorough discussion about the theorem, such as the initialization requirement, tuning of $\\beta$, comparison with existing theoretic results, which is appreciated and clearly demonstrates the theoretic contribution.\n- It is always nice to see a theory-inspired algorithmic modification to be effective and have practical benefits, as shown in the synthetic and real world experiments.\n\nWeaknesses:\n- The contribution is kind of incremental. Since ABm (Xin & Khan, 2020) and GTAdam (Carnevale et al., 2022) already proposes the idea of combining Gradient Tracking with momentum or Adam, is there any algorithmic modification to this idea proposed in this work? Some algorithmic comparison between Momentum Tracking and ABm/GTAdam is necessary. I'd like to see some algorithmic novelty. However, it is totally fine if the contribution is mainly theoretic, just might be of smaller practical interest in this case.", "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 proposed Momentum Tracking, a decentralized learning method with momentum acceleration whose convergence rate is proven to be independent of the data heterogeneity in the standard deep learning setting (stochastic, smooth and nonconvex objective).", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Since ABm (Xin & Khan, 2020) and GTAdam (Carnevale et al., 2022) already proposes the idea of combining Gradient Tracking with momentum or Adam, is there any algorithmic modification to this idea proposed in this work? Some algorithmic comparison between Momentum Tracking and ABm/GTAdam is necessary.", "broader_impact_concerns": "NA, mainly theoretic work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "AvrpWoE1tx", "reviewer": "Reviewer_KSER", "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\n1. The work extends the analysis of (Koloskova et al 2021) to incorporate the momentum step based on analysis of momentum in (Yu et al 2019) and (Liu et al 2020). This extension is done (essentially) for free meaning that the convergence rate is worse only by a numerical constant compared to a non-momentum version of Koloskova et al 2021. \n2. The paper provides a brief proof sketch of their result in the appendix. The proof of the theorem is well written and the (proof) sketch helps to understand it better. The statement of the main theorem makes sense to me. I have also checked a few key lemma in the appendix, which seem to be correct. \n3. The paper includes an extensive experimental comparison of their momentum tracking method to those known in the literature. The key message of experiments is clear: momentum helps in practice and the proposed scheme is robust to the increase in the level of heterogeneity of data. \n\n\n**Weaknesses:**\n\n1. The analysis in this work is heavily based on the one by (Koloskova et al, 2020) and the authors subsequently compare to this early result. However, it is unclear to me why the authors chose to base on this analysis given that there were seemingly a number of improvements and refinements of this analysis since then. In particular, the closely related works (Lu et al, 2021) and (Yuan et al, 2022b) are completely ignored and not even cited. These works seem to have better convergence rates, and the first one in particular does not require gradient similarity assumption. Other related works are missing, e.g., (Batiste Le Bars et al, 2022). \n2. The literature review related to Polyak’s momentum is also far from being complete. For instance, (Defazio, 2021), (Karimireddy et al, 2021), (Cutkosky et al, 2020, 2021). \n3. The difference of algorithms and analysis with those in (Lin et al, 2021) and (Yuan et al, 2020) are not discussed (QG-SGDm and DecentLaM). These works have similar convergence guarantees in the exact same setting, but require stronger data similarity assumptions. Is it the limitation of their analysis or the methods? Are their methods different from the one proposed in this work?\n\n**The writing and presentation** of the paper can be significantly improved.\n1. There are a number of repetitions of sentences or even entire paragraphs throughout the work. For example, this paragraph is repeated twice (in Section 1 and 2):\n“In the convex optimization literature, Xin & Khan (2020) and Carnevale et al. (2022) proposed combining Gradient Tracking with momentum or Adam and analyzed the convergence rates...”\n\nThis sentence is repeated twice (in section 1 and 2): “When the data distributions held by each node are statistically homogeneous, DSGDm works well and can improve the performance as well as SGDm.”\n\nThis sentence is almost identical to the first sentence of the abstract: “One of the key components for improving the performance of neural networks is SGD with momentum acceleration (SGDm).”\n\nI also noticed a number of unnecessary repetitions in Section 4: “when the data distributions are homogeneous, DSGDm, QG-DSGDm, DecentLaM, and Momen- tum Tracking are comparable and outperform DSGD and Gradient Tracking.”\n\nSame for this sentence: “ a method in which the update rule of the momentum in DSGDm is modified to be more robust to data heterogeneity than DSGDm”. Moreover, it is not clarified how the method “is modified to be robust to data heterogeneity”.\n\n2. Some word choices are not very precise/rigorous: For example: “When the data distributions held by each node (i.e., the server) are statistically homogeneous, DSGDm works well and can improve the performance as well as SGDm.” Improve in which sense? Theoretically/practically? Why the node is the same thing as the server? \nOn page 4, authors claim that the setting they consider is “standard DL setting”. This is not precise given that the loss in most of DL architectures (including those considered in this paper) is not smooth. \n\n3. The authors repeatedly use the word “acceleration” in the paper, which seems to be an over claim since there is no proven acceleration (in any sense) of the proposed method compared to (non momentum variant) gradient tracking method. Moreover, I would refrain from using this word to avoid confusion with acceleration in the sense of Nesterov since there is a large body of works trying to prove that Polyak’s momentum has accelerated rate compared to gradient descent beyond strongly convex quadratics. But in many important cases this question still remains an open problem. \n\n\nYucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Interna- tional Conference on Machine Learning (ICML), pages 7111–7123. PMLR, 2021.\n\nKun Yuan, Xinmeng Huang, Yiming Chen, Xiaohan Zhang, Yingya Zhang, Pan Pan . Revisiting Optimal Convergence Rate for Smooth and Non-convex Stochastic Decentralized Optimization. 2022b.\n\nBatiste Le Bars, Aurélien Bellet, Marc Tommasi, Erick Lavoie, Anne-Marie Kermarrec . Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Data. 2022.\n\nAaron Defazio. Momentum via primal averaging: Theoretical insights and learning rate schedules for non-convex optimization. arXiv preprint arXiv:2010.00406, 2021.\n\nSai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008.03606, 2021.\n\nAshok Cutkosky and Harsh Mehta. Momentum improves normalized SGD. In International Conference on Machine Learning, page 2260–2268. PMLR, 2020.\n\nAshok Cutkosky and Harsh Mehta. High-probability bounds for non-convex stochastic optimization with heavy tails. pages 4883–4895, 2021.", "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": "\nThis work considers a stochastic decentralized optimization problem. In particular, the paper focuses on a combination of two standard optimization techniques: gradient tracking (for decentralized optimization over a network) and Polyak’s momentum. Such combination has been already proposed previously in the literature (as acknowledged by the authors). The main theoretical contribution of this work is the refined analysis of such combination, which allows to remove a strong gradient similarity assumption (present in the previous works combining gradient tracking and momentum). The obtained rates of convergence recover those for non-momentum variant of gradient tracking by Koloskova et al 2021. The paper also offers an extensive numerical comparison of this method with other existing alternatives on a number of deep learning tasks. \n\nMy main concern about this work is the lack of comparison to existing works in decentralized optimization and the lack of technical novelty. In particular, it seems questionable to me that removing gradient similarity/bounded gradients assumption is a serious challenge in this setting given that such assumption is not present in Koloskova et al 2021 (for gradient tracking without momentum) and it was removed in (Liu  et al 2020) for momentum method (in the centralized setting). \n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Mentioned above. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Several suggestions were made by Reviewers KSER and WFz3, and some of them were not taken into account yet. I propose a minor revision where this is taken int account.

Further, the authors study decentralized nonconvex stochastic optimization, and their aim is to obtain a rate independent of any data heterogeneity term. However, methods that do that exist already, e.g., Koloskova et al (2021), which the authors cite and compare to, but also later works that improve previous results, such as

Li et al, BEER: Fast O(1/T ) Rate for Decentralized Nonconvex Optimization with Communication Compression, NeurIPS 22,

which the authors do not cite nor compare to. The above work does not use momentum, but momentum is not needed from a theoretical point of view as it does not improve the rate. I'd welcome a comparison with the above work.
Decision: Accept (poster)