Would decentralization hurt generalization?
Authors: Tongtian Zhu
Fengxiang He
Kaixuan Chen
Mingli Song
Dacheng Tao
Venue: Submitted to ICLR 2023 (2023)
Keywords: decentralized SGD
flat minima
generalization
implicit regularization
large batch training

Abstract: Decentralized stochastic gradient descent (D-SGD) allows collaborative learning on massive devices without controlling of a central server. Existing theory suggests that the decentralization degrades the generalizability, which conflicts with experimental results in the large-batch settings that D-SGD generalize better than centralized SGD (C-SGD). This work presents new theory that reconciles the conflict between the two perspectives. We prove that D-SGD introduces an implicit regularization that simultaneously penalizes (1) the sharpness of the learned minima and (2) the consensus distance between the consensus model and local models. We then prove that the implicit regularization is amplified in the large-batch settings when the linear scaling rule is applied. We further analyze the escaping efficiency of D-SGD, which suggests that D-SGD favors super-quadratic flat minima. Experiments are in full agreement with our theory. The code will be released publicly. To our best knowledge, this is the first work on the implicit regularization and escaping efficiency of D-SGD.

Under review as a conference paper at ICLR 2023
WOULD DECENTRALIZATION HURT GENERALIZATION?
Anonymous authors
Paper under double-blind review
ABSTRACT
Decentralized stochastic gradient descent (D-SGD) allows collaborative learning massive devices without the control of a central server. Existing theory suggests that decentralization degrades generalizability. which conflicts with experimental results in large-batch settings that D D-D generalizes better than centralized SGD (C-SGD). This work presents a new theory that reconciles the conflict between the two perspectives. We prove that D-SGD introduces implicit regularization that simultaneously penalizes (1) the sharpness of the learned minima and (2) the consensus distance between the global averaged model and local models. We then prove that the implicit regularization is amplified in large-batch settings when the linear scaling rule is applied. We further analyze the escaping efficiency of D-SGD and show that D-SGD favors super-quadratic flat minima. Experiments are in full agreement with our theory. The code will be released publicly. To our best knowledge, this is the first work on the implicit regularization and escaping efficiency of D-SGD.
INTRODUCTION
Decentralized stochastic gradient descent (D-SGD) enables simultaneous model training on massive workers without being controlled by a central server, where every worker communicates only with its directly connected neighbors (Xiao & Boyd, 2004; Lopes & Sayed, 2008; Nedic & Ozdaglar, 2009; Lian et al., 2017; Koloskova et al., 2020). This decentralization avoids the requirements of a costly central server with heavy communication and computation burdens. Despite the absence server, existing theoretical results demonstrate that the massive models on the edge converge to unique steady consensus model (Shi et al., 2015; Lian al., 2017: Lu et al., 2011) 1), with asymptotic linear speedup in convergence rate (Lian et al., 2017) as the distributed centralized SGD (C-SGD) does (Dean et al., 2012; Li et al., 2014). Consequently, D-SGD offers a promising distributed learning solution with significant advantages in privacy (Nedic, 2020), scalability (Lian et al., 2017), and communication efficiency (Ying et al., 2021b).
central
However, existing theoretical studies show that the decentralization nature of D-SGD introduces an additional positive term into the generalization error bounds, which suggests that decentralization may hurt generalization (Sun al., 2021; Zhu al., 2022). This poses crippling conflict with empirical results by Zhang et al. (2021) which show that D-SGD generalizes better than C-SGD by a large margin in large batch settings; see Figure 1. This conflict signifies that the major characteristics were overlooked in the existing literature. Therefore,
would decentralization hurt generalization?
This work reconciles the conflict. We prove that decentralization introduces implicit regulariza- tion in D-SGD, which promotes the generalization. To our best knowledge, this is the first paper that surprisingly shows the advantages of D-SGD in generalizability, which redresses the former twofold.
misunderstanding. Specifically, our contributions
We prove that the mean iterate of D-SGD closely follows the path of C-SGD regularized loss, which is the addition of the original loss and a regularization term introduced by decentralization. This regularization term penalizes the largest eigenvalue of the Hessian matrix, well as the consensus distance (see Theorem 1). These regularization effects are shown to be considerably amplified in larce-batch settings (see Theorem 2), which is consistent with our visualization (see

---

Under review as a conference paper at ICLR 2023
salidatio accuracy (%6
Noon accuracy (%)
0.9
validation accuracy
0.9
0.9
0.8
1024
0.8
D-SGD_101 1024
0.8
D-SGD_ _196
D-SGD_80 8196
D-SGD_8193 _896
0.7
G-SGD_ 1024
C-SGD_100 1024
0.7
C-50D_1024
C-SGD_8133 8196
0.7
C-SGD_815 8196
C-SGO __196
0.6
2000
4000
6000
2000
4000
6000
2000
4000
6000
iteration
iteration
iteration
(a) AlexNet
(b) ResNet-18
(c) ResNet-34
Figure 1: Comparison of the validation aceuracy of C-SGD and D-SGD on CIFAR-10. The number of workers (one GPU worker) is set 16; and the local batch size is set 64, and 512 per worker (1024 and 8196 total batch size). The training setting is included Section 5.
Figure 4) and the empirical results (Zhang et al., 2021). To prove the above results, we apply second-order multivariate Taylor approximation (Königsberger, 2013) the gradient diversity (see Equation (5)) to derive the regularized loss. Then, we prove that the regularization term contained in the regularized loss scales positively with the largest Hessian eigenvalue, which suggests that D-SGD implicitly minimizes the sharpness of the learned minima (see Lemma C.2).
We prove the first result on the expected escaping speed of D-SGD from local minima (see Theorem 3). Our results show that D-SGD prefers super-quadratic flat minima sub-quadratic minima with higher probability (see Proposition 4). The proof is based on the construction of a stochastic differential equation (SDE) approximation (Jastrzebski al., 2017; M al., 2017; Li et al., 2021) of D-SGD.
RELATED WORK
Flatness and generalization. The flatness of minimum commonly used concept the opti- mization and machine learning literature and has long been regarded as a proxy of generalization (Hochreiter & Schmidhuber, 1997; Izmailov al., 2018: Jiang et al., 2020). Intuitively, the loss around flat minimum varies slowly in large neighborhood, while a sharp minimum increases rapidly in small neighborhood (Hochreiter & Schmidhuber, 1997). Through the lens of the mini- mum description length theory (Rissanen, 1983), flat minimizers tend to generalize better than sharp minimizers, since they are specified with lower precision (Keskar et al., 2017). From a Bayesian per- spective, sharp minimizers have posterior distributions highly concentrated around them, indicating that they are more specialized on the training set and thus are less robust to data perturbations than flat minimizers (MacKay, 1992: Chaudhari et al., 2019).
Generalization of large-batch training. Large-batch training is of significant interest for deep learning deployment, which can contribute to a significant speed-up in training neural networks (Goyal et al., 2017; You et al., 2018; Shallue et al., 2019). Unfortunately, it is widely observed that in the centralized learning setting, largh-batch training often suffers from drastic generalization degradation, even with fine-tuned hyper-parametens from both empirical (Chen & Huo, 2016; Keskar al., 2017; Hoffer et al., 2017: Shallue et al., 2019; Smith al., 2020) and theoretical (Li al., 2021) aspects. An explanation of this phenomenon is that arge-batch training leads to "sharper" minima (Keskar et al., 2017), which are more sensitive to perturbations (Hochreiter & Schmidhuber, 1997).
Development of D-SGD. The earliest work of classical decentralized optimization can be traced back to Tsitsiklis (1984), Tsitsiklis et al. (1986) and Nedic & Ozdaglar (2009). D-SGD, typical decentralized optimization algorithm, has been extended to various settings in deep learning, including time-varying topologies (Lu & Wu, 2020; Koloskova et al., 2020), asynchronous settings (Lian et al., 2018; Xu et al., 2021: Nadiradze et al., 2021), directed topologies (Assran et al., 2019; Taheri et al., 2020), and data- hettroeeteoog scenarios (Tang et al., 2018; Vogels al., 2021).
Generalization of D-SGD. Recently, Sun et al. (2021) and Zhu et al. (2022) have established generalization bounds of D-SGD and have shown that decentralized training hurts generalization.
2

---

Under review as a conference paper at ICLR 2023
& (Wa)
C-SGD
D-SGD (Ring)
D-SGD (Grid)
D-SGD (Exponential)
Figure 2: An illustration of C-SGD and D-SGD.
However, these works do not analyze the sharpness reduction effect of D-SGD and cannot explain why D-SGD can generalize better than C-SGD in large batch settings. Another work by Zhang et al. (2021) demonstrates that D-SGD introduces an "additional" landscape-dependent noise, which improves the convergence of D-SGD. However, the direction, magnitude, and shape of the noise remain unexplored. In contrast, we rigorously prove that the additional noise of D-SGD (i.e., the gradient diversity in Equation (4)) biases the trajectory of D-SGD towards flatter minima, which may play distinct role in shaping the generalizability of D-SGD.
3 PRELIMINARIES
Suppose that X' C Rd and y C are the input and output spaces, respectively. We denote the training / (21,...,,2, 2N where 2ę = (xc, . . 1,.-.; N sampled independent and identically distributed (i.i..)) from an unknown data distribution D defined on X' x y. The goal of supervised learning is to learn a predictor (hypothesis) g(: w), parameterized by w(z1, 22, IN) E IRd, to approximate the mapping between the input variable E X' and the output variable y E based the training set μ. Let e y x y + R$ be function that evaluates the prediction performance of hypothesis The loss of hypothesis with respect to (w.rt.) the example 2- (Iç;. 3/() denoted by L(w; 2ς) c(g(xç; w). yç). which measures the effectiveness of the learned model. Then, the empirical and population risks of are defined as follows:
N
('(w)= = N
Σ L(w;zc). I(w) [[,; C=1
Distributed learning. Distributed learning jointly trains a learning model w on multiple workers (Shamir & Srebro, 2014). In this framework, the j-th worker (j (1...,m). can access |μy] independent and identically distributed (i.i.d)) training examples μ4j = (2j,1..... Filug) drawn from the data distribution D. In this case, the global empirical risk of is
m
L (w),
m 1=1
where L (w) 1 luyl L(w; 25.)) denotes the local empirical risk on the j-th worker and [ey] E
Zj.C E M4j (S 1, (1y]) stands for the local training data.
Distributed centralized stochastic gradient descent (C-SGD). In C-SGD, there is only one centralized model (.()). C-SGD (Dean al., 2012: Li al., 2014) updates the model by
gradient computation
m m
A (t)) (wa(t)
Wa(+1) (.())
n
where 7) denotes the learning rate, (t) 1., Ziln, (0)} denotes the local training batch independent and identically distributed (i.i.d)) drawn from the data distribution D at the t-th iteration,
'The word "centralized" indicates that in C-SGD, there is central server receiving gradient information from local workers (see Figure 2).

---

Under review as a conference paper at ICLR 2023
and (L) Te
[1) C(t)=1 23.cce)) stands for the local mini-batch gradient of L
w.r.t the first argument w. The total batch size of C-SGD at f-th iteration is [p(e]] = - [py(o)-
In the next section, we will show that C-SGD equals the single-worker SGD with a larger batch size.
Decentralized stochastic gradient descent (D-SGD). The goal of D-SGD learn a consensus model (t) 2j=1 Wj(t) on m workers, where (+(+) stands for the d-dimensional local model on the j-th worker. We denote P [P E R a doubly stochastic gossip matrix (see Definition A.1) that characterizes the underlying topology G. The vanilla Adapt- WWhile-Communiatt (AWC) version of the mini-batch D-SGI (Nedic & Ozdaglar, 2009; Lian al., 2017) updates the model on the j-th worker by
Communication
Local gradient computation
W
Σ
PLAW -7-
VL
(2)
For a more detailed background of D-SGD, please refer to Appendix A.
THEORETICAL RESULTS
This section shows the implicit regularization effect and the escaping efficiency of D-SGD. We start by showing that D-SGD can be interpreted as C-SGD on a regularized loss. Then we prove that the regularization term in the new loss scales positively with the largest Hessian eigenvalue (see Theorem 1), which suggests that D-SGD implicitly minimizes the sharpness. Next, we prove that the regularization effect will increase with the total batch size if apply the linear scaling rule (see Theorem 2), which justifies the superiority of D-SGD in large-batch settings. Finally, we prove the escaping efficiency of D-SGD beyond the quadratic assumption (see Theorem 3) and show that D-SGD favors super-quadratic minima (see Proposition 4).
4.1 D-SGD IS EQUIVALENT TO C-SGD ON A REGULARIZED L.OSS
In this subsection, we theoretically compare D-SGD and C-SGD. We prove that D-SGD equivalent to C-SGD on regularized loss with an extra positive regularization term, as shown in the following theorem.
Theorem 1 (Implicit regularization of D-SGD). Given that the loss L is continuous and has fourth-order partial derivatives, denote the weight diversity matrix as E(t) = its diagonal matrix as (0, and the d-dimensional all-ones
in DT (Ww)())Ww(t))(ww)))))
vector as 1. With a probability greater than 1 - (n)) the mean iterate of D-SGD becomes Epsjee>D[Wadd (Wa((++))
3-1, 3=1....
V
L (Wa(t) t (H. +0 (vll,,(0)wllw (3)
the regularized loss
Under mild assumptions in Lemma C.2, D-SGD implicitly regularizes
reg( wy(0) ) = 1=
XH (t)))(t)) (f)).
Tr(E
maximum Hessian eigenvalue
consensus distance
The first term (t).. is commonly regraded sharpness measure (Jastrzebski et al., 2017; Wen et al., 2020). It is related to the (C., A) -h-sharpssss (i.e., maxw L(w + Aw') - L(w)) in Keskar et al. (2017) and is an equivalent measure to the Sharpness Aware Minimization (SAM) loss proposed by Foret et al. (2021) at local minimum (Zhuang et al., 2022). Theorem shows that the decentralization navigates D-SGD towards the flatter directions, in order to lower the regularization term (t)).. The second term, the trace of E(o, equals to the consensus distance, key component measuring the overall effect of decentralized learning (Kong et al., 2021),
consensus distance
m Σ
1
m
(w(()-wa(0).
4

---

Under review as a conference paper at ICLR 2023
Consequently, Theorem also suggests that D-SGD implicitly controls the discrepancy between the global averaged model (a( and the local models wy(() (j = l,..... m) during training.
Our derived implicit regularization the sharpness of learned minima is similar to how label noise (Blanc et al., 2020; Damian et al., 2021) and artificial noise (Orvicto et al., 2022) smooth the loss function in centralized gradient methods, including distributed centralized gradient methods (C-SGD) and single-worker gradient methods. To the best of our knowledge, this is the first work that shows D-SGD is equivalent C-SGD on a regularized loss with implicit sharpness regularization. In the existing literature, initial efforts have viewed D-SGD as C-SGD in a higher-dimensional space that penalizes the weight norm [ where W [WI.... wm] I E Rmxd stands for all local models across the network (Yuan et al., 2021; Gurbuzbalaban et al., 2022).
We summarize the proof sketch below. The full proof is given in Appendix C.
Proof sketch.
(1) Deriving the dynamics of the global averaged model 2, We first start by rewriting the update of the global averaged model Wa( of D-SGD as follows,
Wa(++1) (1 L (walt) + V (w.(t)) - L (w.(t))
unhiased gradient
gradient noise the superhatch p(()
m
L
(Wa(t))]
m
gradient diversity among workers
Remark. The equality shows that decentralization introduces an additional noise, which char- acterizes the gradient diversity between the global averaged model Wa(() and the local models Wy(+) (j == 1,.... m.) It implies that distributed centralized SGD, which has constant zero gradient diversity, is equivalent to standard single-worker worker SGD with larger batch size. Note that the gradient diversity also equals to zero quadratic loss L (see Corollary C.I). Consequently, the quadratic approximation in the analysis of mini-batch SGD (Zhu et al., 201 9b; Ibayashi & Imaizumi, 2021; Liu al., 2021) fails to capture how decentralization affects the training dynamics of D-SGD.
(2) Performing Taylor expansion on the gradient diversity. Analyzing the effect of the gradient diversity on the training dynamics of D-SGD on the general non-convex losses is highly non-trio non-trivial. Technically, we perform a second-order Taylor expansion on the gradient diversity around wa(t), omitting the high-order residuals R:
V Lzy (y(t)
(W,(t) -V (Wa(t)]
1
H H
(Wa(t)) (W((+) (w(())aa(()
Tuy (Wa(t)) [wy(t)
(a(t) (Wy)))-Wa(t)(ww) W.
m
2m
Here HP5 Wa()) A
[0)(0)
H (wa()); 2j,(()) stands for the empirical Hessian at walt)
(1)
c()==
and T (w)())
T(w, (e); denotes the empirical third-order partial derivative tensor at Wo(l), where (1) and Zj,((e) follows the notation in Equation (1).
[0,
Analogous to the works investigating the SGD dynamics (M et al., 2017; Zhu et al., 2019b; Ziyin et al., 2022: Wu et al., 2022), we will calculate the expectation and covariance of the gradient diversity. The expectation of gradient diversity is calculated first as follows. We defer the analysis of its covariance to Subsection 4.3. Taking expectation over all local mini-batches (L((t) e) (j = 1.....,0. m) provides
E D
Σn ( (W5(0) - -V (wato)]] J=1
m
Note that there is central server D-SGD. In the following we analyze the training dynamics of the global averaged model (.( D-SGD, which has been proved to close to the individual models wj(( = 1,..., m) (Yuan et al., 2016; Fallah et al., 2022).
TTaking expectation over (o means taking expectation all 25,0(0) (Cto 1,..., (pg))-
5

---

Under review as a conference paper at ICLR 2023
1 m
(ww(t))
w wy(0 wj(0)-W(t) +TT((a()))
Σ
Ww
The i-th entry of the above equation will be
m
E up
Σ
-0, (wali)l]
M
1=1
Set (Wa(t))
(5)
2
m78
k
Ent 0f ((..) mn Σ (w,)
where (t) (f)) denotes the k-th entry of the vector due to Clairaut's theorem (Rudin et al., 1976).
The equality in the brace is
Then we prove that with probability greater than 1n) the iterate of D-SGD can be written as B (atc))/(Waa(ta [Wa(++)]
=WalD-nV L (w.()) 22 (w)) (0) (
the regularized loss
(3) Controlling the top Hessian eigenvalue with Tr H (w.(t) 3 (t)). According to Lemma C.2, we obtain
< (t)))
AH
Tr
S di (r))
sharpness
consensus distance
where À HH(w.. ( denotes the largest eigenvalue of H (wa(t)) and di stands for the marginal contri- bution of (0),, the full spectrum of H (w) (i.e.. ((),())). d (T(H(w. Therefore, combined with Equation (3), we conclude that D-SGD also implicitly regularizes {H(w.((). (0).1 (r))
4.2 AMPLIFIED REGULARIZATION OF D-SGD IN LARGE-BATCI SETTING
In practice, the decentralization (and also distribution) ordinarily implies an equivalent large total batch size, since massive number of workers involved in the system in many practical scenarios. Moreover, large-batch training can enhance the utilization of super computing facilities and further speeds up the entire training process. Thus, studying the large-batch setting is of significant interest for fully understanding the application of D-SGD.
Despite the importance, theoretical understanding of the generalization of large-batch training in D-SGD remains an open problem. This subsection examines how the total batch size affects the sharpness reduction effect of D-SGD if the linear scaling rule, as presented below, is applied.
Linear scaling rule (LSR). The linear scaling rule is a widely used apper-parameter free rule for deep learning (Krizhevsky. 2014; He al.. 2016a; Goyal et al., 2017; Bottou et al., 2018: Smith et al., 2020), which states that fixed learning rate to total batch size ratio allows maintaining generalization performance when the total batch size increases.
Theorem 2. Suppose that the averaged gradient norm satisfies m E VV (w)(1))
(1+1-A) En IIVL (W)(++D))l,, where 1-X denotes the spectral gap (see Definition A.2). The sharpness regularization coefficient of D-SGD (i.e., Tr(3(t)) at t-th iteration is Olucol + + E (ny(es) )) which increases with the total batch size |p(o) if we apply the linear scaling rule.
RReall that Theorem 1 implies that the loss function D-SGD optimizes is close to the original loss L plus Tr (S()) (H,,, The second term (H(w., is sharpness measure, and the first term Tr(E(t)) is the "regularization coefficient" which characterizes the strength of the sharpness regularization.

---

Under review as a conference paper at ICLR 2023
Theorem 2 states that the sharpness regularization effect of D-SGD is amplified in large-batch settings we apply the linear scaling rule. It is worth noting that this amplified sharpness regularization effect requires no additional communication and computation, which verifies that significant advantages in generalizability surprisingly exist the large-batch D-SGD. The proof is included in Appendix C.
4.3 ESCAPING EFFICIENCY OF D-SGD FROM LOCAL MINIMA
This subsection presents an analysis of the escaping efficiency of D-SGD, based the construction of a stochastic differential equation (SDE) approximation (Jastrzebski et al., 2017; M et al., 2017: Li al., 2021) of D-SGD. This escaping efficiency analysis shows that D-SGD favors super-quadratic minima.
To construct the SDE approximation of D-SGD, we combine Equation (3) and Equation (4) and write the iterates of D-SGD as follows,
Wa(++1)
1 Wa(t) -1 (W(((t))))) +2 TT(H(Wa()) mm (wl, 1), (6)
where (c) denotes the zero-mean noise D-SGD. Applying Lemma C.4, Equation (6) can be viewed as the discretization of the following SDE
(w)(t) = - [ (wa(t)) + ((wa(t) @ E'
E'(o] dt + (ndddWa
where denotes the tensor product (see Appendix A.2), Ex(() denotes the covariance matrix of the total noise ED(() 1 Pn
j= (5 (Wy(t)) -VL (w.( and (()) is standard Brownian motion (Feynman, 1964) in Rd We then utilize the SDE approximation of D-SGD to study the escaping efficiency of D-SGD, defined as follows.
Definition (Escaping efficiency). Let w denote one of the local minimum of the loss function L. Then, we call Bw, L((())(((()))) - L(w"]] the escaping efficiency of the dynamic ( w where E (t) denotes the expectation with respect to the distribution of Wa(t).
Suppose that Wa(++) gets stuck in a minimum w*5 the escaping efficiency characterizes the probability that the dynamics Wa(++1) escapes w", since Markov's inequality guarantees V8, P(L(Wa(++D)- L(w") 2 5) S (ew,(e)[((w.((t1)) - L(w") )I] /8.
We then have the following theorem on the escaping efficiency of D-SGD.
Theorem 3 (Escaping efficiency of D-SGD). If the loss L is continuous and has fourth-order partial derivatives, the escaping efficiency of D-SGD from minimum w" satisfies
(w) (LWa(t)) L(w")]
1'" Fw (VL VL VV
1
( 2
J. " (t.(t) dt,
where O denotes the Hadamard product (Davis, 1962), and grandsum(() (Merikoski, 1984) of matrix M satisfies grandsum M) Ei, Myj.
A detailed proof and the escaping efficiency of C-SGD (see Proposition C.5) are given in Appendix C.
Comparing Theorem and Proposition C.5, we can see that the main difference between the escaping efficiency of D-SGD and C-SGD lies in the integral of grandsum (T(w (w.(t))) V L(w.(t)) O = (0). which correlates with the gradient diversity in Equation (4). We then study how this term affects the escaping efficiency of D-SGD on super- quarr-quadratic minima, typical class of minima as defined below.
Definition (Super-quadratic minimum). Given that the loss L is continuous and has second-order partial derivatives, we call the mimimum w" of L 8-locally super-quadratic if for any w in the open punctured neighbourhood of w" (i.e., w E Üw"", .8)). the following condition holds: (1) H (w*) &
H (w); and (2) 3 a (w),, B(w) g+ s.I. H (w)(ww-w)) - ww) a(w) w w1 [[[)
[()) (w
w")).
Note that there guarantee that D-SGD can converge to any local minimum in the non-convex settings.
7

---

Under review as a conference paper at ICLR 2023
Super-quadratic minimum
Sub-quadratic minimum
Figure 3: An illustration of super-quadratie and sub-quadratic minimum.
The super-quadratic growth implies that the losses become flatter when the parameters get closer to minima. We then present the intuition the second condition in Definition A second-order Taylor approximation of L around w" reads,
[(w) L(w") = (L(() w") (w w")² H0HH(WW (W(W((W-.) - w"),
and the second condition in Definition 2 further guarantees that,
L(w) - L(w") = ( (w - w") + a(w)ll w ((()) (w w )" (w
quadratic growth
which suggests that the growth of L(w) is ò-locally super-quadratic as long as a(w), ((w) > O.
A related study by Ma et al. (2022) observes that the minima learned by centralized gradient descent methods obey "sub-quadratic growth" (i.e., the loss becomes sharper as parameters get closer the minimum). We also give a formalization of the sub-quadratic minima in Definition C.I. Intuitively, super-quadratic minima are flatter than sub-quadratic minima with the same depth, as illustrated in Figure 3. The following proposition studies the sign of grandsum (T (TW..(()VLWW... on the super-quadratic and sub-quadratic minima.
= (o)
Proposition 4. Suppose that Wa(() is sufficiently close grandsumi (w.(t))VV( tive if w" is 8-locally super- super-quadte quadratic minima, and (3) negative w" is ô-locally sub-quadratic minima.
local minimum w", @ ()) is (I) zero if w" a quadratic minima, (2) posi-
Combined with Theorem 3, Proposition 4 shows that D-SGD favors super-quadratic minima over sub-quadratic minima with a higher probability. The proof included in Appendix C.
Theorem I and Proposition 4 indicate that the additional noise (i.c., the gradient diversity in Equa- tion (4)) of D-SGD may play distinct role in shaping the generalizability of D-SGD.
EMPIRIAL RESULTS
This section empirically validates our theory. We first introduce the experimental setup and then study how decentralization favours the flatness of minima.
Implementation settings. Vanilla D-SGD and C-SGD employed train image classifiers CIFAR-10 (Krizhevsky et al., 2009) with AlexNet (Krizhevsky et al., 2017), ResNet-18 18 and ResNet- 34 (He al., 2016b), three popular neural networks. Batch normalization (loffe & Szegedy, 2015) is employed in training AlexNet. The number of workers (one GPU as a worker) is set as 16; and the local batch size is set as 8. 64, and 512 per worker in three different cases. For the case of local batch size 64, the initial learning rate is set as 0.1 for ResNet-1 8 and 0.01 for AlexNet. The learning rate is divided by 10 when the model has passed the 2/5 and 4/5 of the total number of iterations (He et al., 20). We apply the linear scaling law to avoid different total batch sizes caused by the different local batch size (see Subsection 4.2). In order to understand the effect of decentralization on the flatness of minima, all other training techniques are strictly controlled. The code is written based on Py Torch (Paszke et al., 2019).
Hardware enviornment. The experiments are conducted computing facility with NVIDIA Tesla" V100 16GB GPUs and Intel Xeon @ Gold 6140 CPU @ 2.30GHz CPUs.
We plot the minima learned by C-SGD and D-SGD in Figure using the loss landscape 3D visual- ization tool in Li et al. (2018). See more plots in Appendix B. Two observations are obtained from these figures: (1) the minima of D-SGD are flatter than those of C-SGD; and (2) the gap in flatness becomes larger as the total batch size increases. These observations support the claims Theorem and Theorem 2 that D-SGD favors flatter minima than C-SGD, especially in the large-batch settings.
8

---

Under review as a conference paper at ICLR 2023
22
130
21
225
80
00
0.2
6.2
0.2
44
(a) C-SGD, 128 total batch size
(b) C-SGD, 1024 total batch size
(c) C-SGD, 8196 total batch size
200
268
250
215
215
275
15.
150
33.5
25
325
280
100
388
75
C4
0.
-02
-02
(d) D-SGD, 128 total batch size
(e) D-SGD, 1024 total batch size
(1 D-SGD, 8196 total batch size
Figure 4: Minima 3D visualization of C-SGD and D-SGD with ResNet-18 on CIFAR-10.
DISCUSSION AND FUTURE WORK
Scalability to complex or sparse topologies. Our theory holds for arbitrary topologies (see Defini- tion 1. We also conduct experiments on grid-like and static exponential topologies (Ying et al., 2021a) and obtain results similar to Figure and Figure B. For spare topologies, which has a very small spectral gap, the regularization term in Theorem I would be extremely large during training, which may hinder optimization and lead to large total excess risk of D-SGD. Can we design new decentralized training algorithm that can alleviate the optimization issue on spare topologies while maintaining the generalization advantage in hurge-batch, setting?
Non-IIDness and the flatness minima. In real-world settings, fundamental challenge in distributed learning is that data may not be i.i.d. across workers (Tang et al., 2018; Vogels et al., 2021; Mendieta al., 2022). In this case, different workers may collect distinct or even contradictory samples (i.c., data cetta-heterogeniity (Criado et al., 2021). it widely observed that the non-IIDness hurts the generalizability D-SGD. Can we rigorously analyze how the degree of data-heterogeneity affects the flatness of minima and design theoretically motivated algorithms promote the generalizability of D-SGD in non-IID settings?
CONCLUSION
This work provides a new theory that reconciles the conflict between the empirical observations showing that D-SGD can generalize better than centralized SGD (C-SGD) in large-batch settings and the existing generalization theories of D-SGD which suggest that decentralization degrades generalizability. We prove that D-SGD introduces implicit regularization that penalizes the learned minima's 's sharpness and this effect will be amplified large-batch settings if we apply the linear scaling rule. We further analyze the escaping efficiency of D-SGD, which shows that D-SGD favors quadratic flat minima. To our best knowledge, this is the first work on the implicit sharpness regularization and escaping efficiency of D-SGD.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning. 2019.
Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant. Implicit regularization for deep neural networks driven by omstein-uhlenbeck like process. In Conference learning theory. PMLR, 2020.
Leon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):124018, 2019.
Kai Chen and Qiang Huo. Scalable training of deep learning machines by incremental block training with intra-block parallel optimization and blockwise model-update filtering. In 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5880-5884. IEEE Press, 2016.
Marcos F Criado, Fernando E Casado, Roberto Iglesias, Carlos V Regueiro, and Senén Barro. Non-iid data and continual learning processes in federated learning: A long road ahead. arXiv preprint arXiv:2111.13394 2021.
Alex Damian, Tengyu Ma, and Jason Lee. Label noise sgd provably prefers flat global minimizers. Advances in Neural Information Processing Systems, 2021.
Ch Davis. The norm of the schur product operation. Numerische Mathematik, 4:343-344, 1962.
Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances in neural information processing systems, 2012.
Alireza Fallah, Mert Gurbuzbalaban, Asuman Ozdaglar, Umut Simsekli, and Lingjiong Zhu, Robust distributed accelerated stochastic gradient methods for multi-agent networks. Journal of Machine Learning Research, 23(220)::199) 2022.
Richard Feynman. The brownian movement. The Feynman Lectures of Physics, 1:41, 1964.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur. Sharpness-aware minimization for efficiently improving generalization. International Conference on Learning Representations, 2021.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is it to break privacy in federated learning? In Advances in Neural Information Processing Systems, 2020.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv: neeeri1660777777 2017.
Mert Gurbuzbalaban, Yuanhan Hu, Umut Simsekli, Kun Yuan, and Lingjiong Zhu. Heavy-tail phenomenon in decentralized sgd. arXiv preprint 2xXiv:2205.06663 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2016a.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European conference computer vision. Springer, 2016b.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):1-42, 1997.
10

---

Under review as a conference paper at ICLR 2023
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. Advances in neural information processing systems, 2017.
Hikaru Ibayashi and Masaaki Imaizumi. Exponential escape efficiency of sgd from sharp minima in non-stationary regime. arXiv preprini 1eXiv:2111004000 2021.
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning. 2015.
Pavel Izmailov, Dmitrii Podoprikhin, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson, Av- eraging weights leads to wider optima and better generalization. arXiv preprint 2018.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint 1711.04131...3 2017.
Yiding Jiang, Behnam Neyshabur*, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. In International Conference on Learning Representations, 2020.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. International Conference on Machine Learning, 2020.
Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian Stich. Consensus control for decentralized deep learning. In International Conference on Machine Learning. PMLR, 2021.
Konrad Königsberger. Analysis 2. Springer-Verlaa 2013.
Alex Krizhevsky, One weird trick for parallelizing convolutional neural networks. arXiv preprint 49X1v:1404.5997, 2014.
Alex Krizhevsky, Hinton, et al. Learning multiple layers of features from tiny images (tech. rep.). University of Toronto, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. Communications of the ACM, 60(6):44-90, 2017.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in neural information processing systems, 2018.
Mu Li, David G Andersen, Alexander J Smola, and Kai Yu. Communication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 2014.
Zhiyuan Li, Sadhika Malladi, and Sanjeev Arora. On the validity of modeling sgd with stochastic differential equations (sdes). Advances in Neural Information Processing Systems, 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances Neural Information Processing Systems, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning. 2018
Kangqiao Liu, Liu Ziyin, and Masahito Ueda. Noise and fluctuation of finite learning rate stochastic gradient descent. In International Conference on Machine Learning. PMLR, 2021.
11

---

Under review as a conference paper at ICLR 2023
Cassio G Lopes and Ali H Sayed. Diffusion least-mean squares adaptive networks: Formulation and performance analysis. IEEE Transactions on Signal Processing, 2008.
Jie Lu, Choon Yik Tang, Paul R Regier, and Travis D Bow. Gossip algorithms for convex consensus optimization over networks. IEEE Transactions on Automatic Control, 2011.
Songtao Lu and Chai Wah Wu. Decentralized stochastic non-convex optimization over weakly connected time-varying digraphs. In ICASSP 2020-2020 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), 2020.
Stephan M, I, Matthew D. Hoffman, and David M. Blei. Stochastic gradient descent as approximate bayesian inference. Journal of Machine Learning Research, 18(134):1-35, 2017.
Chao Ma, Lei Wu, and Lexing Ying. The multiscale structure of neural network loss functions: The effect optimization and origin. arXiv preprint arXiv:2204.11326, 2022.
David JC MacKay. A practical bayesian framework for backpropagation networks. Neural compula- tion, 4(3):448-477 472, 1992.
Matias Mendieta, Taojiannan Yang, Pu Wang. Minwoo Lee, Zhengming Ding, and Chen Chen. Local learning matters: Rethinking data heterogeneity in federated learning. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 8397-8406, 2022.
Jorma Kaarlo Merikoski. On the trace and the sum of elements of matrix. Linear algebra and its applications, 60: 60:177-185, 1984.
Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan Alistarh. Asynchronous decentralized sgd with quantized and local updates. Advances in Neural Information Processing Systems, 2021.
Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 2020.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-61, 2009.
Bernt Øksendal. Stochastic differential equations. In Stochastic differential equations, pp. 65-84. Springer, 2003.
Antonio Orvieto, Hans Kersting, Frank Proske, Francis Bach, and Aurelien Lucchi. Anticorrelated noise injection for improved generalization. In International Conference on Machine Learning. PMLR, 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 2019.
Jorma Rissanen. A universal prior for integers and estimation by minimum description length. The Annals of statistics, 11(2):4164433 1983.
Walter Rudin et al. Principles of mathematical analysis. McGraw-hill New York, 1976.
Eugene Seneta. Non-negative matrices and Markov chains. Springer Science & Business Media, 2006.
Christopher J. Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George F. Dahl. Measuring the effects of data parallelism neural network training. Journal of Machine Learning Research, 20 (0112)):149) 2019.
Ohad Shamir and Nathan Srebro. Distributed stochastic optimization and learning. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2014.
Wei Shi, Qing Ling, Gang Wu, and Wotao Yin. Extra: An exact first-order algorithm for decentralized consensus optimization. SIAM Journal Optimization, 2015.
12

---

Under review as a conference paper at ICLR 2023
Samuel Smith, Erich Elsen, and Soham De. On the generalization benefit of noise in stochastic gradient descent. In International Conference on Machine Learning. PMLR, 2020.
Tao Sun, Dongsheng Li, and Bao Wang. Stability and generalization of decentralized stochastic gradient descent. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9756-9764, 2021.
Hossein Taheri, Aryan Mokhtari, Hamed Hassani, and Ramtin Pedarsani. Quantized decentralized stochastic learning over directed graphs. In International Conference on Machine Learning, 2020.
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D2: Decentralized training decentralized data. In International Conference on Machine Learning, 2018.
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31(9): 803-812, 1986.
John Nikolas Tsitsiklis. Problems in decentralized decision making and computation. Technical report, Massachusetts Inst of Tech Cambridge Lab for Information and Decision Systems, 1984.
Thijs Vogels, Lie He, Anastasiia Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. Relaysum for decentralized deep learning on heterogeneous data, Advances in Neural Information Processing Systems, 34:28004-28015, 2021.
John Von Neumann. Some matrix-inequaliitie and metrization of matric space. 1937.
Stefanie
Hartmut Schultze, Krishnaprasad Lingadahalli Shastry, Sathyanarayanan Manamohan, Saikat Mukherjee, Vishesh Garg. Ravi Sarveswara, Kristian Händler, Peter Pickkers, N Ahmad Aziz, et al. Swarm learning for decentralized and confidential clinical machine learning. Nature, 2021.
Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba. An empirical study of stochastic gradient descent with structured covariance noise. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108, pp. 3621 3621-3631. PMLR, 2020.
Lei Wu, Mingze Wang, and Weijie Su. When does sgd favor flat minima? quantitative characteriza- tion via linear stability. arXiv preprint arXiv:2207.02628, 2022.
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 2004.
Jie Xu, Wei Zhang, and Fei Wang. Agdp) Asynchronous decentralized parallel stochastic gradient descent with differential privacy. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Hongxu Yin, Arun Mallya, Arash Vahdat, Jose M. Alvarez, Jan Kautz, and Pavlo Molchanov. See through gradients: Image batch recovery via gradinversion. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. In Advances in Neural Information Processing Systems, 2021a.
Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin. Bluefog: Make decentralized algorithms practical for optimization and deep learning. arXiv preprint arXiv:2111.04285 2021b.
Yang You, Zhao Zhang, Cho-Jui Hsieh, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proceedings of the 47th International Conference on Parallel Processing. Association for Computing Machinery, 2018
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal Optimization, 26(3):1835-1854, 2016.
13

---

Under review as a conference paper at ICLR 2023
Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Decentlam: Decentralized momentum sgd for large-batee batch deep training. In Proceedings of the IEEE/CVF International Conference Computer Vision, pp. 3029-302233 2021.
Wei Zhang, Mingrui Liu, Yu Feng, Xiaodong Cui, Brian Kingsbury, and Yuhai Tu. Loss landscape dependent self-adjusting learning rates in decentralized stochastic gradient descent. arXiv preprint arX1v:2112.01133, 2021.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. Advances in Neural Information Processing Systems, 2019a.
Tongtian Zhu, Fengxiang He, Lan Zhang, Zhengyang Niu, Mingli Song, and Dacheng Tao. Topology- aware generalization of decentralized sgd. In International Conference on Machine Learning. PMLR, 2022.
Zhanxing Zhu, Jingfeng Wu, Bing Yu, Lei Wu, and Jinwen Ma. The anisotropic noise stochastic gradient descent: Its behavior of escaping from sharp minima and regularization effects. In International Conference on Machine Learning. PMLR, 2019b.
Juntang Zhuang, Boqing Gong, Liangzhe Yuan, Yin Cui, Hartwig Adam, Nicha Dvornek, sekhar tatikonda, James Duncan, and Ting Liu. Surrogate gap minimization improves sharpness-aware training. In International Conference on Learning Representations, 2022.
Liu Ziyin, Kangqiao Liu, Takashi Mori, and Masahito Ueda. Strength of minibatch noise SGD. In International Conference Learning Representations, 2022.
14

---

Under review as a conference paper at ICLR 2023
A ADDITIONAL BACKGROUND
A.1 DECENTRALIZED LEARNING
To handle an increasing amount of data and model parameters, distributed learning across multiple computing workers emerges. A traditional distributed learning system usually follows centralized setup. However, such a central server-basee learning scheme suffers from two main issues: (1) A centralized communication protocol significantly slows down training since central servers easily overloaded, especially in ww-bbandwidth or high-latency cases (Lian et al., 2017); (2) There exists potential information leakage through privacy attacks on model parameters despite decentralizing data using Federated Learning (Zhu et al., 2019a; Geiping et al., 2020; Yin et al., 2021). As an alternative, decentralized training allows workers balance the load on the central server through the gossip technique (Lian et al., 2017), as well as maintain confidentiality (Warnat-Herresthl et al., 2021).
We then summarize some commonly used notions regarding decentralized learning.
Definition A.1 (Doubly Stochastic Matrix), Let G (V,E) stand for the decentralized communica- tion topology where V denotes the set of m. computational nodes and & represents the edge set. For any given topology = (V.E), the doubly stochastic gossip matrix P PP mxx is defined on the edge set that satisfies
P=P7 (symmetric);
If * k and (j,k) & E, then P = (disconnected) [ddcoddccneeee)))) and otherwise, P > 0 (connected);
Py.k E (0, 1] Vk, and Σx P,, Σ, Pj (standard weight matrix for undirected graph).
In the following we illustrate some commonly-used communication comiii topologies.
Ring
Grid
Exponential
Fully-connected
Figure A.1: An illustration of some commonly used topologies.
The intensity gossip communications is measured by the spectral gap (Seneta, 2006) of P.
Definition A.2 (Spectral Gap). Denote X = max (1eel Amml where X; (i = 2. mm) is the i-th largest eigenvalue of gossip matrix P mm The spectral gap of a gossip matrix can be defined as follows:
spectrol gap == A.
According to the definition of doubly stochastic matrix (Definition l), we have 0 S X 1. The spectral gap measures the connectivity of the communication topology, which is close to 0 for sparse topologies and will approach 1 for well-connected topologies.
Assumption A.1. We assume that the sum of the off off-diagonal entries of E(t) is smaller than d - times of the sum of the diagonal entries of (()) in expectation:
m
& Bugor
(3())-W.(1)3))
Kgl
where d stands for the dimensionality of W,(t)- Wa(t).
15

---

Under review as a conference paper at ICLR 2023
A.2 EXPLANATION TENSOR PRODUCT
The tensor product between a third-order tensor T E Rdxdxdd and a second-order tensor (matrix) M Raxd in this paper is defined
T
M); grandsum T, O M),
the 2-th entry
where T, RRddd second-order tensor (matrix), @ denotes the Hadamard product (Davis, 1962), and the grandsum(-) (Merikoski, 1984) of a second-order tensor (matrix) satisfies grandsum(M) = Eig" Myj-
16

---

Under review as a conference paper at ICLR 2023
B ADDITIONAL MINIMA VISUALIZATION
We plot the minima learned by C-SGD and D-SGD as follows using the 2D loss landscape visualiza- tion tool in Li et al. (2018).
02
(a) C-SGD, 128 total batch size
(b) C-SGD, 1024 total batch size
(c) C-SGD, 8196 total batch size
-12
-02
(d) D-SGD, 128 total batch size
(e) D-SGD, 1024 total batch size
(1) D-SGD, 8196 total batch size
Figure B.I: Minima 2D visualization C-SGD and D-SGD with ResNet-18 on CIFAR-10.
From Figure B.1, we observe that (1) the minima of D-SGD is flatter than those of C-SGD; and (2) the gap in flatness becomes larger as the total batch size increases. Similar results are obtained with AlexNet and ResNet-34 on CIFAR-10.
17

---

Under review as a conference paper at ICLR 2023
C PROOF
Corollary C.1. The gradient diversity in Equation (4) equals to zero in the following cases: (1) the loss L = w Hw is quadratic; and (2) the optimization algorithm is distributed centralized SGD (Equation (1)).
Proof of Corollary C.I.
On quadratic loss, we have
7
1 m
m
(y (Wy()) VD (wo(t))] = Σ
(w, = H w (1) W
wo
m
m j=1
m
==1
==1
In distributed centralized SGD, the gradient diversity statisfies
VL V L (Wa(t))] =0
(t.
Lemma C.2. We denote ( 2i=1 Wal)) wa(t)) (Wa()))))))) the weight diversity ma-
trix and (1) Ei=i fe,e"" E() e.e".. We assume that d1 (dj < d), the marginal contribu- tion of (H(w((t)). the full spectrum of (W.())) is non-negative and satisfies AH(w,(().. da (T(H(Wa(t)) Then the product Tr(((())) and the maximum eigenvalue of ((wa(t) is upper d
and lower bounded
0 I (r((H(a(())))) S (H((.(())
(r(
S dj (r()((.()))
sharpness
consensus distance
Proof of Lemma C.2.
On the one hand, von Neumann's 's trace inequality (Von Neumann, 1937) guarantees
Tr (O) (0) S Σ AH(w.(t)). )g)())) S AH(..(()) (r(E
(C.1)
where (0),, and A represent the r-th largest eigenvalue of H(w and (().. respec- tively. On the other hand, we will prove that (H(w.())) Tr(E(t)) S O (w.(() ( Since
E'(0) (t) 1 B() p c.o a diagonal matrix, Tr (r(H( (0) can be lower bounded as (T(H(w.::)E)) (0) 2 Tr H (w:)))))
where e² is the lower bound of Σ (w5(t) (k l,..,d),, d).
Knowing that Tr(=*(t) (1) (r)) (0). can bound the right hand side of Equation (C.1) follows:
(r) Tr (w.(t)) Tr( = d, Tr H [w, 0 S (0)1
E* (0))
Note than also obtain
0 < Tr H (w.tt) (+) < (w.(t)) Tr) < di Tr(H (w.(s))
which shows that D-SGD also implicitly regularizes Tr H (w..
Lemma C.3 (Kong et al., 2021)). Suppose that the averaged gradient norm satisfies j=1 LVL (w s (1 )
1 E [VL (w,(++1)))+ then the the consensus distance
of D-DGD satisfies
Tr(E
Th
1 m
Σ
-
18

---

Under review as a conference paper at ICLR 2023
أ=ز V
1 - (00D VL (wy(t) -V W w
where X equals to spectral gap (see Definition A.2). Lemma C.4. D-SGD is approximated by the following SDE
(w)(t) = - VL (wa(t)) (TW(())tt & Et VijEntedW (0)
where & denotes the tensor product (see Appendix A.2), En(t) denotes the covariance matrix of the unbiased noise e(t), and W (t) is a standard Brownian motion (Feynman, 1964) in Rd.
Proof of Lemma C.4.
If omit the residual terms, the iterate of D-SGD becomes
(a(t+1) wa(t)- (w.(o) (.w.(0)+TTT
(0) 7)D(())
1 - ( (w.. & (n ( ( VL (wa(t) (V
where ED(!) N (0, Ep) (Gaussian approximation) and e² is standard Gaussian random variable. For small enough constant learning rate 7), we arrive
(+) L (w. (t) + T((a(()) +
& E' Vn)En(eddW (m)
The stochastic processes give a way model D-SGD as continuous-time evolution (i.e., SDE) without ignoring the role of mini- noise if the learning rate is infinitesimal.
Theorem 1 (Implicit regularization of D-SGD). Given the loss L is continuous and has fourth-order partial derivatives. Denote the weight diversity matrix as E(o) (W)(())aa()) its diagonal matrix as E' (1), and the d-dimensional all-ones vector as 1. With probability greater than (1)). the mean iterate of D-SGD becomes
m Eラ=
E Epg:o=D(Wa(t- ((W)(( m
= L (wa())) Tr(H (.) +0 (nl (nl
the regularized loss
Under the mild assumptions in Lemma C.2, D-SGD implicitly regularizes
reg( w ) ) j=L....m
{H(w.(())
Tr(E(t)
Hessian eigenvalue
consensuu distance
Proof of Theorem 1.
We start by rewriting the update of the global averaged model wa(0) of D-SGD as follows,
Wa(++1) -w, I V (w.(t) VL = (w)(t)
unbiased gradient
gradient noise over the superbuich pite)
V 5550 (w)())-VDDC (wa(ti)]].
gradient diversity among workers
Analyzing the effect of the gradient diversity on the training dynamics of D-SGD on the general non-convex losses is highly non-trivial. Technically, perform second-order Taylor expansion (see Appendix A.2) on the gradient diversity around w.(0), omitting the high-order residuals Rt
1
(t((t)
(wy(0)- L550 (wa(t)]
m
19

---

in Under review as a conference paper at ICLR 2023
1 m
1
H H
(Wa()))W)(())ww.)
T (Wa(t) (W)))) (..
2m
[p Σ [ny(
Here HiS (Wa()) and T
H ( (.(t)) Pj.((s) stands for the empirical Hessian at Watt)
((0=1
(w.( (w,()((
E c(t==1 (() 23,0()) denotes the tensor containing all empirical
(2)
(C]
third-order partial derivatives at Wa(O), where (y(() and 2j,0(s) follows the notation in Equation (1).
Analogous to the works investigating the SGD dynamics (M al., 2017; Zhu al., 2019b; Ziyin et al., 2022; Wu et al., 2022), we will calculate the expectation and covariance of the gradient diversity. The expectation of gradient diversity first calculated as follows. We defer the analysis of its covariance to Subsection 4.3. Taking expectation over all local mini-batches (1(0)) (j 1,.... m) provides
E BRgOOD
LL (W5(0)-VLLSC L (watt)]l
m
=H(wa(t)
m
(w,(0) (w)(0- + ((wa(t) (((aa)))))(())))
Σ m
1
m
wy w,
The i-th entry of the above equation will be
E E
1 (wy(t)) - - L'50 (wa())]]
Bds ((w
Wy(th ( (+)) (w)()) +0 (IW,(()-wwo))))))
(C.2)
=0, Eu ((=)
E (w, (1) w. (wa())))))))
where (w, (()-)((()))))))))))))))))) denotes the k-th entry of the vector w,(0) The equality in the brace is due to Clairaut's 's theorem (Rudin et al., 1976).
According to Markov's 's inequality and Assumption A.I, obtain
Pr
Wy(t) W,)))-Wa))a(w)(00
n23
E
Py(e)DD CEeyt 1 (w) Lu
1
E Pyle)D ((d 1) mm 1
m Σグ (w)(0)
1-1
1
E pyte)D ((d (r((()
1
(dn)²
27a
(dn)),
where d stands for the dimensionality of wy(0)-a(() and the penultimate equality is due to Lemma C.3.
For sufficiently small 7 o(d-2), 50: En 02 (zn) + Ej Equation (C.2) is of the order O(n).
20

---

Under review as a conference paper at ICLR 2023
Then derive that with probability greater than 1-0(1), the iterate of D-SGD can be written E Bagco-D[Wa(ttt)) [Wa(++)]
-wat L (wa(t) 1 (w))( -00
2
the regularized loss
where (1) = E (efef F e is the diagonal of E(t).
According to Lemma C.2, (())((()) (r(E(t) scales positively with Tr(H (
S Tr(H (wa(H) E (0) S AH(... (o).
Tr(3(t) S (T) (0),
sharpness
consensus distance
where AFr(w. (t),.1 denotes the largest eigenvalue of H (Wa(t) and d, stands for the marginal contri- bution of (HW.(.())) on the full spectrum of (t) (i.e., (t), = d (w.(t)) Therefore, combined with Equation (3), we conclude that D-SGD also implicitly regularizes (0), (r)) The proof is complete.
Theorem 2. Suppose that the averaged gradient norm satisfies 1. - (w,t))) S (1 1 Em I (w)(t+1))ll, where 1 x denotes the spectral gap (see Definition A.2). The
sharpness regularization coefficient of D-SGD t-th iteration Olpcrr) + 1 m Ee= (y)( which increases with the total batch size |ptt if we apply the linear scaling rule.
Proof of Theorem 2.
Theorem states that the regularization coefficient of (H(wa(()) is v Tr(Et). According to Lemma C.3, Tr(E(t)) satisfies
Tr(E())) = 12 O
1 Σ VVL (V
B VL (w5(o) VL (w, (w)
noise covariance, O( |nyter (M 2017)
independent total batch size [(се]]
(C.3)
Given that apply the linear scaling rule (see Subsection 4.2), have = Olpces)), which completes the proof.
Theorem 3 (Escaping efficiency D-SGD). If the loss L is continuous and has fourth-order partial derivatives, the escaping efficiency of D-SGD from minimum w" satisfies
Ew.. (W(w(()) L(w")
2
J. 1l Tr 2
dt,
where @ denotes the Hadamard product (Davis, 1962), and the grandsum()) (Merikoski, 1984) of matrix M satisfies grandsum( Ei, Mij.
Proof of Theorem 3.
Since is continuous and has second-order partial derivatives, we can write
dL(wa(t) = "VLw..))"VVLLw... 1
(L(wa!)) @ Et))) dt
grandsum (L)) (WW))T/.(((WWLL..()))))))))..)
21

---

Under review as a conference paper at ICLR 2023
" + 2
EE (ww(()) dt VL(wa())) (o(edd
according to the Ito's 's lemma (Oksendal, 2003). The term VL(W.(()) ( (n( (t) will be averaged we take the expectation with respect to the distribution Wa(t). Finally, integrating over t will provide
Bwa(h) (1) [[(w()))]
=L(w") + ! Tr (H(( df
Fo. VL( VL((w(())
@ E*))]dd,
which completes the proof.
Proposition C.S (Escaping efficiency C-SGD). 1hehe loss L has second-order partial derivatives, the escaping efficiency of C-SGD from minimum w satisfies
B i ((Wa(t+1) - L(w")]
[ Tr (HWa(t))Ecol dt,
=- (V(Wall))"LL(M
where Ee0) denotes the covariance matrix of the gradient noise of C-SGD (Equation (1)).
The proof is analogous to Theorem
Definition C.1 (Sub-quadratic minimum). Given that the loss is continuous and has second-order partial derivatives, we call the mimimum w" of L 8-locally sub-quadratic for any in the open punctured neighbourhood of w* (i.e., w U(w"), the following condition holds: (1) H H(w") 7 (8(w)
(w): and (2) 3 a(w) E R 3(ww) R s.t. H (w))ww -ww-ww)-- = =aww) w [ (w- ww")
Proposition 4. (T(udsum((((watt))) L( @ (t) is (1) zero quadratic minima, (2) posilive on super-quadrutic minima, and (3) negative on sub-quadratic minima.
Proof of Proposition 4. (1) quadratic minima.
It is obvious that on quadratic loss, gradient diversity (see Corollary C.1).
(0)) 0 due to zero
(2) super-quadratic minima.
Performing the Taylor expansion of H() H(w") around w provides
H(w) (w") T(w)(w w") >
According to the definition of super-quadratic minima, we know that 3 a(w) E Aet,t((0 e Rt s.t.
(WW)(((W)(W) - w")) = a(w)]lw - 11 ((W) -w)- > Another Taylor expansion of VL(w) VL(w*) around w will give
(VW)) VL(w")) ~ T(W) (w])))))www)---------- = - ( wwwwwww)--
Then we arrive at with all positive entries.
@ =+())) > 0 since E*()) a diagonal matrix
(3) sub-quadratic minima.
By the same token, prove that (Fandsm((((..ee)))L(v..))) < sub- quadratic minima.
22


Reviews:
[{"review_id": "wVpaPsdamOQ", "reviewer": "Reviewer_m7pE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies whether decentralized stochastic gradient descent (D-SGD) can lead to better generalization compared to the centralized SGD. The authors showed that D-SGD implies an implicit regularization and used this result (Theorem 1) to argue that the implicit regularization promotes the generalization. The authors also study the escaping efficiency of D-SGD and showed that D-SGD favors the so-called super-quadratic flat minima.  ", "summary_of_the_review": "The paper studies an important and interesting topic. But I have doubt about the mathematical rigor and main results in the paper. ", "strength_and_weaknesses": "In my view, the paper studies a very important topic. Whether decentralization can help or hurt generalization is a very interesting research topic. The authors' idea to show that the decentralized SGD can introduce an implicit regularization, which might help generalization is a novel idea, and has some potential.\n\nHowever, I am not satisfied with the overall quality of the paper. \n\nFirst of all, there is little technical novelty or contribution here. The authors only looked at the average of iterates, instead of the individual iterates, and as a result, when you average out over the doubly stochastic matrix, it disappears from the analysis, and makes the analysis easy. However, it is well known that the average iterates are close to the individual iterates (see e.g. Yuan et al. \"On the convergence of decentralized gradient descent\" for the deterministic gradient case and Fallah et al. \"Robust distributed accelerated stochastic gradient methods for multi-agent networks\" for the stochastic gradient case). It would be nice if the authors can obtain some results for individual iterates instead of the average iterates. \n\nSecond, some conclusion and implication from the main result are not convincing to me. For example, in Theorem 1, the authors claim that D-SGD implicitly regularizes $\\lambda_{H(w_{a}(t)),1}\\cdot\\text{Tr}(\\Xi(t))$. However, if you look at the proof, this term is only an upper bound. It is not very convincing to me. Also, Theorem 1 looks like writing D-SGD as centralized SGD plus some additional term, and this idea is not new, see e.g. Fallah et al. \"Robust distributed accelerated stochastic gradient methods for multi-agent networks\". \n\nWhat's even more disappointing is that I am not 100 percent sure that the main result, i.e. Theorem 1 is correct. The proof is not rigorous. For example, in the proof of Theorem 1 in the Appendix, the authors did not explain how to control the remainder term R. What's even more troublesome to me is that in the proof, the authors wrote that \"Assuming for the sake of intuition, we expect each dimension of $(w_{j}(\\tau)-w_{a}(\\tau))$ to be uncorrelated.\" Why? Please explain. This is not clear to me at all. You cannot simply assume something that you do not know how to prove. Also in the proof, the authors wrote that \"if the topology is symmetric\". Please explain what you meant by saying \"if the topology is symmetric\". It seems the authors lack mathematical rigor and basic training in mathematics. In the statement Lemma C.4., the authors wrote that \"D-SGD can be viewed as the discretization of the following SDE...\" This is not a rigorous mathematical statement at all. It is okay to write this sentence as an informal discussion within a paragraph in the main body of the paper, but one cannot write a statement like that in a lemma. If you want to state it in a lemma, you should make the statement formal and rigorous. For example, see Li et al. \"Stochastic modified equations and adaptive stochastic gradient algorithms\", where they used weak convergence of certain order to describe SGD being approximated by an SDE. \n\nFinally, there is a disconnection of Theorem 1 and the other results in the paper, like escaping efficiency in Theorem 3. You should make the connections more clear.  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "UJUHxyPk2o", "reviewer": "Reviewer_qFYy", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors did theoretical analysis for the D-SGD algorithm and the results are claimed to show an implicit regularization during D-SGD optimization process that penalizes the learned minima’s sharpness. The escaping efficiency of the D-SGD algorithm is also analyzed.", "summary_of_the_review": "See section \"Strength And Weaknesses\"", "strength_and_weaknesses": "The topic is very interesting and it has important implications for understanding the impact of decentralized algorithms on optimization problems. However the main result (Theorem 1) confuses me, since it says with high probability, the expectation of w(t+1) = w(t) - \\eta * gradient & regularization term + O(\\sqrt{\\eta}) + O(\\eta * weight diversity related term). This does not seem to make sense because when \\eta (which is the step length) becomes very small, the result seems to indicate w(t) will diverse and the gradient related term becomes minor compared to the other terms. This contradicts with our common intuition that a smaller step size leads to easier convergence.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9r9SgoFTaJ", "reviewer": "Reviewer_Phej", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the generalization performance of decentralized training compared with the centralized one, especially for the large batch setting. The authors show that there is an implicit regularization that penalizes the sharpness of the learned minima and the consensus violation, and this regularization is amplified by the large batch size. Also, the authors claim that decentralized SGD is more likely to find the super quadratic local minima. ", "summary_of_the_review": "In summary, this paper considers a critical issue of addressing the generalization performance of decentralized SGD, however, the provided argument is not direct linking the consensus violation and generalization error. The theoretical argument is not rigorously justified even with good intuitions. ", "strength_and_weaknesses": "The major strength of this work is studying the generalization performance of decentralized SGD compared with the centralized case by analyzing the eigenvalues of the hessian. The technical contributions include implicit regularization analysis, amplified regularization by large batches, escaping efficiency, and numerical evaluations.\n\nThe most concerns of this work are as follows:\n\n1) This is straightforward to see that the consensus violation would serve as the implicit regularization during the training phase, but how much this play on the generalization error is not analyzed. There is a gap between this observation and generalization performance.\n\n2) The large batch amplification is not clear. On page 20, it said that the regularization coefficient is $\\eta\\textrm{Tr}$. Please let me know when it was mentioned in the Thm.1. Note that the consensus error defined in this work is not dependent on the step size. Also, even it was true, $\\eta^3$ is overclaimed as at least the size of the gradient of the original loss is at least proportional to $\\eta^2$. Again, this issue originated from which metric the authors want to compare, weight, loss function, gradient, or generalization error.\n\n3) Even more problematic is that def.1 is rather weak. Is it from a theoretical analysis or just empirical observation? either one is fine, but here it serves as a definition. Assume this was a definition. It said a fixed learning rate to batch size ratio. From the equation shown in the proof of thm 2 (page 20. please use equation indices), there is no batch size. Def. 1 does not imply that here the learning rate can be replaced by the batch size. Also, the larger the $\\eta$ is, the less likely the thm 1. holds as claimed by the authors on page 6.\n\n4) It does not make sense to have a $w^*$ here as the authors consider the nonconvex problems. There is no clue that DSGD can converge to this point, even it is a local minimum. \n\n\n  ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8aF_xy3-rm", "reviewer": "Reviewer_baeM", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies decentralized stochastic gradient descent (D-SGD), in which different nodes have different subsets of the training data and communicate with their neighbors (through a graph structure) in order to minimize a loss function. The paper makes the case that D-SGD has an implicit regularization effect that causes it to minimize the sharpness (largest eigenvalue of the Hessian of the loss) and therefore prefer flatter minima.", "summary_of_the_review": "In summary I found the paper to be very unclear, and it based upon unclear reasoning. Hence I recommend rejection.", "strength_and_weaknesses": "The strength of the paper is that it tackles a relevant problem (generalization in decentralized settings) and makes an interesting claim about the solutions that D-SGD finds.\n\nThe main weakness of the paper is that the argument presented therein is sketchy and not at all convincing. I have the following questions:\n- In eq. (3), are we considering the regime where the step size η is large or small? If η is small, then wouldn’t the O(η^{½}) term dominate the main “regularized loss” term? In any case, the last term also seems to be of order O(η), so why is it not considered part of the “regularized loss”? It is completely unclear why we ignore certain parts of eq. (3) and focus on others, and **this point alone completely invalidates the reasoning of the paper**.\n- In step (3) at the end of section 4.1, how is the upper inequality established? Please provide a proof.\n- In the SDE after eq. (6), why does the noise involve η? When deriving an SDE limit, aren’t we taking η to zero?\n- The definition of escaping efficiency does not capture the notion of escaping at all. First of all, the definition of escaping efficiency only talks about the value of the loss, it does not talk about whether or not we “escape” (i.e., travel away from) w^*. Second, the escaping efficiency does not “characterize” a probability, because Markov’s inequality is not guaranteed to be tight. Third, what is the interpretation of escaping efficiency? Is a large escaping efficiency supposed to mean that we are more likely to escape? If so, Prop. 4 seems to indicate that D-SGD escapes from super-quadratic minima, which is the opposite conclusion as asserted in the text.\n\nEssentially this paper makes a lot of claims based on extremely shoddy or missing reasoning, which makes this paper **not rigorous**.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "7zdZ_X3l7S9", "reviewer": "Reviewer_hoUP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper investigates the existing conclusion that decentralized stochastic gradient descent (D-SGD) degrades the generalizability, which conflicts with experimental results in large-batch settings that D-SGD generalizes better than centralized distributed SGD (C-SGD). Specifically, the authors present new theoretical analysis to reconciles the conflict. They show that D-SGD introduces an implicit regularization to enable the escaping of the sharpness of the learned minima. Additionally, they theoretically prove that the implicit regularization is amplified in large-batch settings when the linear scaling rule is used. In their work, they also show that D-SGD converges to super-quadratic flat minima eventually. To validate the analysis presented in the paper, the authors utilizes a benchmark dataset with a few models to show empirical results, compared to C-SGD.", "summary_of_the_review": "This paper investigates the existing conclusion that decentralized stochastic gradient descent (D-SGD) degrades the generalizability, which conflicts with experimental results in large-batch settings that D-SGD generalizes better than centralized distributed SGD (C-SGD). The authors provided theoretical analysis for the implicit regularization in D-SGD and showed that D-SGD can avoid the sharpness of the learned minima. They also presented some preliminary experimental result to support their findings. The paper looks good, but more work is required for clarity and novelty. ", "strength_and_weaknesses": "I think overall the investigated topic in this paper is quite interesting. Basically the implicit regularization in D-SGD has not sufficiently been investigated based on the empirical results obtained by using D-SGD and C-SGD. Most existing works have paid much attention to the convergence analysis, while ignoring some findings from the experimental results. The authors have showed some new analysis to explain the better generalizability in D-SGD and tried to explain mathematically why this happened. The paper is also easy to follow and well written. However, in the current form, there are quite a few confusions in the paper that require more works from the authors to make it technically solid and sound.\n\n1. It looks like the definition in this paper for C-SGD, namely the centralized SGD, still involves the communication, which is basically the star-network or Federated Learning setting. While this could somehow be confusing. As centralized SGD typically is referred to as a setting that has no local agents or workers, but just only one agent (could be the centralized server) WITHOUT any communication happening during training. Thus, the C-SGD in this work can be more appropriately replaced with \"distributed\" to avoid confusion. Or some more clarification needs to be detailed in the work.\n\n2. Eq. (1) shows the update for the centralized distributed SGD (C-SGD). It should be noted that from the network topology in Figure 2, communication happens between the server and local agents. The authors should detail this part as well. Distributed learning can involve either just data parallelism, model parallelism or FL. Based on what has been shown in the work, I think it is exactly the FL setting, in which communication would be there between server and agent. Also, there is a typo below Eq.(1) at the bottom of page 3, it should be C-SGD.\n\n3. After Theorem 1, the authors mentioned that \"Theorem 1 shows that the decentralization navigates..., in order to lower the regularization term...\" How? It is not obviously observed from the theorem statement. The authors should give more detail on this. Additionally, the authors claimed that this is the first work to show the equivalence between D-SGD and C-SGD on a regularized loss with implicit sharpness regularization. Again, the authors should give more technical detail to show instead of just saying that. Where is the regularized loss?\n\n4. How to arrive at Eq.(4)? Where is the gossip matrix \\mathbf{P}? It doesn't look like the update of the consensus model for D-SGD. I don't see communication in the formula.\n\n5. The authors mentioned in the paper that the quadratic approximation in the analysis of mini-batch SGD fails to capture how decentralization affects the training dynamics of D-SGD. I am confused here. Based on the statement from the author, then D-SGD performs poor for all scenarios where quadratic losses are there. Note that a lot of regression task is based on mean square error, which is a quadratic loss.\n\n6. The authors repeatedly claimed D-SGD to implicitly regularize the regularization term in the work. It is not obvious for readers, I believe. Can the authors clarify by presenting more detail?\n\n7. How to justify the assumption in Theorem 2? Is it generic in D-SGD? I don't think so.\n\n8. Eq.(6) is obtained by combining Eq.(3) and Eq.(4). How to get that? Substituting Eq.(4) into Eq.(3)?\n\n9. Why did the authors define a new notation in the paper, the so-called escaping efficiency? Such a measure has widely been used in evaluating various stochastic optimization algorithms. Any particular reason to call it so here?\n\n10. In Definition 3, please define all notations necessarily to make the statement clear.\n\n11. For experimental results, though we see the validation for the analysis, to me it is not that promising due to only one dataset. Can the authors add more datasets to validate? Also, I don't think the authors need to impose open problems in the main contents. Instead, they can add them as future directions in the last section. Without any preliminary discussion for these two open problem, that looks a bit weird. For different topologies, the authors have said in the paper that they observed the similar trends. Please add them into the paper to provide more evidence for the theory. \n\n12. Overall, this paper did really try to show some new and good analysis for D-SGD. However, it looks like the span in this work is way too big. Each subsection in Section 4 can be expanded into a standalone paper with comprehensive and thorough theoretical analysis and experimental results. I understand the authors may want to present their findings in time. While with the limit of space, this might hurt the soundness of the work.\n\n******************************Post-rebuttal*****************************\nThanks much for the authors' responses and revisions. I appreciate that. After carefully reviewing the responses from the authors and other reviewers' comments, I will keep my current score. Though additional changes have been made to the draft, it still didn't look technically sound and solid. Particularly, the empirical evidences to validate the theory are still weak, and some analysis in the work still requires more clarification. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "1gjJPtXKHM", "reviewer": "Reviewer_ZZMZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides theoretical and empirical justification of decentralized stochastic gradient descent achieves better validation accuracy than distributed centralized stochastic gradient descent. This paper first proves that D-SGD is equivalent to C-SGD with regularization In Theorem 1. In particular, this regularization term is penalizing both the global model curvature and the consensus distance between the global model and local models. The proof idea is by characterizing the gradient diversity between the global model and local models with second-order Taylor expansion. This paper studies the regularization effect under large batch setting in Theorem 2. In particular, when linear scaling rule is applied, the regularization coefficient of $\\lambda_{H,1}$ is cubicly depending on the batch size under the assumption that average local models gradient norm is not decreasing faster than exponent. This paper studies the escaping efficiency of D-SGD in Theorem 3 and Proposition 4. In particular, the grandsum is positive on super-quadratic minima and negative on sub-quadratic minima. ", "summary_of_the_review": "This paper studies an interesting research problem of D-SGD generalization based on recent advances. But before we can trust the insight of this paper, I believe some justification of the results needs to be done. Please see my questions in Strength And Weaknesses.", "strength_and_weaknesses": "Strength:\n1. First work on the implicit sharpness regularization and escaping efficiency of D-SGD.\n\nWeaknesses:\n1. Theoretical justification. Rather than weakness, I would like to raise several questions on the theorem provided. Firstly, in Theorem 1, how does the communication part affect the model update? It seems that the consensus model is merely an average over local models why local models are communicated. I do not see how the later affects the reformulation of Eq. (4). Secondly, in Theorem 2, how does the largest eigenvalue of the Hessian matrix change according to the batch size? Since Theorem 1 suggests the implicit regularization depends on two terms multiplicatively, I think it is necessary to consider the effect of batch size on both of them rather than just one. If $\\lambda$ is not constant, it is hard to draw the conclusion that \"the sharpness regularization effect of D-SGD is amplified in large-batch settings\". \n2. Lack of necessary D-SGD examples. While there are at least 4 different topologies and doubly stochastic matrices for D-SGD, I am not sure which one is considered in theorems and experiments. Firstly, Theorem 2 is apparently depending on the spectral gap, which supposes to be different when the topology changes. Can the author provide some characteristics on the scale of $\\lambda$? Secondly, it seems that experimental results for sparse topologies can not be found in the current material, while this paper claims \"we also conduct experiments on grid-like and static exponential topologies\". \n3. The empirical evaluation in Figure 1 is not convincing enough. Firstly, the validation accuracy is way below the known accuracy based on the same network structures (e.g.  ResNet-18 can achieve 94% and at least 90%), while the curves seem saturated already. Especially this paper claims that \"C-SGD equals to the single-worker SGD with a larger batch size\". While I understand the purpose of this paper is not to pursuit SOTA accuracy, but the gap is huge makes me question about the training setup and tuning. Secondly, smaller batch (1024) significantly outperforms larger batch (8192) for both C-SGD and D-SGD. While this paper argues that \"these regularization effects are shown to be considerably amplified in large-batch settings\" for D-SGD at least and \"flat minimizers tend to generalize better than sharp minimizers\", I doubt the logic in this paper is complete. Overall, I do not see the empirical evaluation in this paper matches the results in (Zhang et al., 2021), while the later one serves as the motivation of this work. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject