On the Effect of Consensus in Decentralized Deep Learning
Authors: Tao Lin
Lingjing Kong
Anastasia Koloskova
Martin Jaggi
Sebastian U Stich
Venue:  (2021)

Abstract: Decentralized training of deep learning models enables on-device learning over networks, as well as efficient scaling to large compute clusters. Experiments in earlier works revealed that decentralized training often suffers from generalization issues: the performance of models trained in a decentralized fashion is in general worse than the performance of models trained in a centralized fashion, and this generalization gap is impacted by parameters such as network size, communication topology, and data partitioning.

We identify the changing consensus distance between devices as a key parameter to explain the gap between centralized and decentralized training. We show that when the consensus distance does not grow too large, the performance of centralized training can be reached and sometimes surpassed. We highlight the intimate interplay between network topology and learning rate at the different training phases and discuss the implications for communication efficient training schemes. Our insights into the generalization gap in decentralized deep learning allow the principled design of better training schemes that mitigate these effects.
    

Under review as a conference paper at ICLR 2021
ON THE EFFECT OF CONSENSUS IN DECENTRALIZED DEEP LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Decentralized training of deep learning models enables on-device learning over networks, as well as efficient scaling large compute clusters. Experiments earlier works revealed that decentralized training often suffers from generalization issues: the performance of models trained in a decentralized fashion is in general worse than the performance of models trained in a centralized fashion, and this generalization gap is impacted by parameters such as network size, communication topology and data partitioning.
We identify the changing consensus distance between devices as a key parameter to explain the gap between centralized and decentralized training. We show that when the consensus distance does not grow too large, the performance of centralized training can be reached and sometimes surpassed. We highlight the intimate interplay between network topology and learning rate at the different training phases and discuss the implications for communication efficient training schemes. Our insights into the generalization gap in decentralized deep learning allow the principled design of better training schemes that mitigate these effects.
INTRODUCTION
Highly pver-parametrized deep neural networks show impressive results in machine learning tasks, which also lead to a dramatic increase in the size, complexity, and computational power of the training systems. In response these challenges, distributed training algorithms (i.e. data-parallel
large mini-batch SGD) have been developed for use in data-center (Goyal et al. 2017 You et al. 20188 Shallue et al. 2018). These SOTA training systems general use the All-Reduce communication primitive to perform exact averaging on the local mini-batch gradients computed on different subsets of the data, for the later synchronized model update. However, exact averaging with All-Reduce is sensitive to the communication hardware of the training systems, causing the bottleneck in efficient deep learning training. To this end, decentralized training has become an indispensable training paradigm for efficient large scale training in the data-center alongside its orthogonal benefits preserving users' privacy for edge AI (Bellet et al. 2018 Kairouz et al.) 2019).
Several very recent papers aim address the communication overhead in data-center training by compressing the gradi- ents (Koloskova et 2020a Vogels al. 2020 or designing better communication topology (Assran et al. 2019). How- ever, decentralized training for deep learning models still often results in severe loss in generalization performance, even after papee-paramettr tine-tuning (see our Table [ as well as Tables 1, 2, 3 in Assran et al. 2019). This phenomenon is poorly understood even in relatively straightforward i.i.d. data distribution scenarios (i.c. the data-center case), to which very few works are dedicated (but none them provide insights into the generalization gap).
Complete 92.91 0.12
Ring
n=16
92.51 + 0.19 91.74 0.15
n=32
92.82 - 0.27
n=64
92.71 0.11
89.87 + 0.12
Table 1: The generalization issues for decentralized deep learning on two topologies (ResNet-20 on CIFAR-I0 with (16, 32, 64] workers). The test top-1 accuracies over three seeds with fine-tuncd learning rates.
In this work, we theoretically identify the consensus distance, i.e. the average discrepancy between the nodes, the key parameter that captures the joint effect of decentralization. We show that there exists critical consensus distance: when the consensus distance is lower than this critical value, the optimization is almost unhindered. With the insight derived from optimization convergence,

---

Under review as a conference paper at ICLR 2021
further question the existence of the critical consensus distance for deep learning in terms of generalization, and identify the training phase when the critical consensus distance matters. We believe that the answers to these questions are valuable in practice, they offer the possibility to design training strategies that strike appropriate trade-off between targeted generalization performance and affordable communication resources.
We show that tracking the consensus distance over the training phases can explain the generaliza- tion gap between centralized and decentralized training.
We show theoretically that when the consensus distance does not exceed a critical value, then decentralization exerts negligible impact to the optimization. We argue how this critical value depends crucially on the learning rate and the mixing matrix.
Through the lens of consensus distance, we empirically investigate what is the desirable level of consensus distance during different phases of Iraining, in order to ensure high generaliza- tion performance. Our extensive experiments on Computer Vision (CV) tasks (CIFAR-10 and ImageNet-32) as well as Natural Language Processing (NLP) tasks (transformer models for ma- chine translation) do confirm that a critical consensus distance indeed exists, and that consensus distances higher than this critical value heavily penalize the final generalization performance. Surprisingly, we find that large consensus distance might be beneficial later training phases after optimization has plateaued, leading to improved generalization, which is consistent with the observations centralized Post-Local SGD (Lin et al. 2020b).
Based our findings, propose practical guidelines on how to achieve favorable generalization performance with low communication expenses, on arbitrary communication networks.
While our numerical study mainly focuses on the data-center setting with homogeneous nodes, our findings also apply to decentralized training over time-varying topologies and the more difficult heterogeneous setting alike. Our findings not only explain previously proposed ad-hoc solutions (e.g. using All-Reduce in the first training phase as in Assran et al., 2019) but our insights will allow the principled design of better decentralized training systems in future work.
2 RELATED WORK
Gossip averaging (Kempe et al. 2003 Xiao & Boyd 2004; [oyd et al. 2006) forms the backbone of many decentralized learning algorithms. The convergence rate of gossip averaging towards consensus among the nodes can be expressed in terms of the (expected) spectral gap of the mixing matrix. Lian et (2017) combine SGD with gossip averaging for deep learning and show that the leading term in the convergence rate O ngz is consistent with the convergence of the centralized mini-batch SGD (Dekel et al. 2012) and the spectral gap only affects the asymptotically smaller terms. Similar results have been observed very recently for related schemes (Scaman et al. [017] 2018)] Koloskoval al. 2019 2020a b). As the communication topology also impacts the cost per round (number of peer-to-peer communications) sparse topologies have been proposed and studied recently (Assran al. 2019 Wang et al., 2019 Nadiradze al. 2020). Whilst a few recent works focus on the impact of the topology on the optimization performance (Luo et al., 2019; Neglia et al., 2020), we here identify the consensus distance as a more canonical parameter that can characterize the overall effect of decentralized learning, beyond only the topology, through which we are able to provide deeper understanding on the more fine-grained impact of the evolution of the actual consensus distance, on the generalization performance of deep learning training.
Prior work identified the consensus distance as an important parameter that can affect optimization performance and convergence, and provide approaches to increase consensus: for instance Scaman et al. (2017); Sharma et al. (2019) perform multiple consensus steps per round, and Tsitsiklis (1984); Nedič & Ozdaglar (209)); Duchi et al. (2012); Yuan et al. (016) choose carefully tuned learning rates. However, these work do not provide insights into how consensus distance at different training phases impacts the decentralized training, which is the main target of this work.
3 THEORETICAL UNDERSTANDING
In this section we consider decentralized training with stochastic gradient descent (D-SGD) without momentum, but are using the momentum version in all our DI. experiments.
2

---

Under review as a conference paper at ICLR 2021
3.1 NOTATION AND SETTING
The agents are tasked to solve sum-structured optimization problem f: R4 - IR of the form
f == minxeR" [f(x) := [i
(I)
where the components S; Rd - IR are distributed among the nodes and are given in stochastic form: fi(x) := Rg-D; [F: E)), where DD denotes the local data distribution on node i E [n]-
For data-center settings, where data is re-shuffled periodically among nodes, these distributions are identical, but in other scenarios there can be differences between nodes. In D-SGD, each agent i e [n] maintains local parameters x E RRd and updates them as:
(++1) و Waj (x)+) (x) (0)))))))))))) ..)))
(D-SGD)
that is, by stochastic gradient step based on sample e!0)) D. followed by gossip averaging with neighhoring nodes in the network encoded by the mixing weights wij- As parameters can differ across nodes, we define x := Ei= x; and X == .x.. ] E Rd and := [x....,x| x] = , 11
Assumption 1 (Mixing matrix). Every sample of the (possibly randomized) mixing matrix W {wsy} E R is doubly stochastic and there exists parameter p > such that
Ew XW - -X| S (1 - p) |||| XI| VX E Rdxx.
(e1-p)ll
This assumption covers broad variety of settings (see e.g. Koloskova al. 2020b), such D-SGD with fixed (constant) mixing matrix with spectral gap p. with parameter = (1- O but also for randomly chosen mixing matrices, for instance random matchings.
Assumption (L-smoothness), Each function (x): Rd - R, E [n]] is differentiable and there exists a constant L 2 O such that for each x, Rd: [[V - fx(()) S L L|xx yll
Assumption 3 (Bounded noise a and diversity (). There exists constants o², -² s.l. VxI, Xn E Rd
T2 i== Eg, [V,,, fxx))l S 0², 1
vf(x)) 2 5 (3)
3.2 DECENTRALIZED CONSENSUS OPTIMIZATION
Under the above assumptions, which are standard in decentralized optimization, the convergence rate of (D-GGD) has been shown to be:
Theorem Koloskova et al. (2020b)). Let fs be L-smooth and stepsize 7 S 7max = =f,). Then there exists an optimal stepsize 7 S Tmax such that + ET E [x( s for
0²
v/a+t + + 2 -(S(x)) 1*).
T T=
ng? pea/2
In comparison, for centralized mini-batch SGD (C-SGD) we are allowed to choose a potentially much larger stepsize 7 < O(+), and can bound the number of iterations by ( asymptotically both these rates equivalent, they differ in low accuracy setting when is not too small. That is, especially in the first phase of optimization where the lower order terms matter.
_ nez + 2). While
To measure differences between agents, we use the consensus distance =i := a. E ||000 x 101
Remark 2 (Critical Consensus Distance (CCD)). If the consensus distance is bounded by
E
In 10000
1
||=
(4)
81,2
for all t, then in D-SGD we may chooge larger stepsizes 7 < 2 = O and recover the convergence rate of C-SGD, that is O( mE? + (Dekel et al. 2012 Bottou al. 2018 We denote
I&? as critical consensus distance (CCD).
The proof can be found in the Appendix A.I Note that the CCD does not depend the graph topology and that r? > O, which means that we do not need perfect consensus between agents to recover the C-SGD rate, but we allow consensus distance E? 2 0 (i.e. the E? 0 Vt, have for centralized optimization is sufficient, but not necessary).
We now estimate the magnitude of the consensus distance in D-SGD and compare it to CCD.
3

---

Under review as a conference paper at ICLR 2021
Proposition 3 (Typical consensus distance). Let of - assumption that 7.P are constant, and the or do not change too fast between iterations, i.e. not decreasing faster than exponentially: of S (1+ p/ 2)0 the consensus distance in D-SGD satisfies
Then under the
2
0²
- = (1 - p)> 0
P
We give the proof in the Appendix A.2
While these assumptions do not hold in epochs with learning rate decay, we observed practice that when the learning rate is constant indeed the gradients do change too fast and found it to be a reasonable approximation to capture the practical behavior (see Figure 5
3.3 CONTROLLING THE CONSENSUS DISTANCE
In this section we investigate scenarios where the typical consensus distance derived in Proposition can be smaller than its critical value (CCD). This reveals two orthogonal strategies to control the consensus distance in D-SGD. We here assume diversity Ç 0 as with iid training data, and that the stepsize I (+,)) as for C-SGD, and give more refined discussion in the appendix.
Learning rate decay (changing 7). We observe that when y O ((t)) then E S I (if the noise a is small, especially for a = O, then the weaker assumption 7 = O 4 is sufficient). However, small can impact performance in practice. In C-SGD the constraint on the stepsize is loose (7 I }). Yet, our observations show that after sufficient learning rate decay, the desired CCD can be reached.
choosing the stepsize
More gossip iterations (changing p). We observe that when (again, when the noise a is small, especially when o² = 0, a weaker condition 1 +L) is sufficient). Whilst designing new mixing topologies to control p might not be possible due to practical constraints (fixed network, denser graphs increase latency, etc.) a simple and commonly repeated gossip steps in every round.
011 + then =? r?
used strategy is
Lemma 4 (Repeated gossip). Suppose W W.... WL for k (possibly randomized) mixing matrices with parameter each. Then the mixing parameter for W is at least pw 2 11
From this, we see that the mixing parameter can be improved exponentially when applying more gossip steps. To ensure pw 2 1 I+yLn at most k < In(1+7Ln) (()) repetitions are required.
These arguments show, that we can-at least in theory-recove the convergence behavior of C-SGD by controlling the consensus distance. We will now present numerical evidence, that corroborates these findings for deep learning tasks.
4 INSPECTING CONSENSUS DISTANCE FOR DECENTRALIZED TRAINING
Motivated by theoretical analysis in Section 3 we empirically investigate to what extent our theory holds and how consensus distance interacts with deep learning training. First we introduce and justify our experimental design in Section 4.1 We describe the implementation in Section 4.2 In Section 4.3 we present our findings on image classification benchmark with standard SGD optimizer, which is the main focus of this work; preliminary study Transformer with Adam optimizer and inverse square root learning rate schedule can be found in Section
4.1 EXPERIMENT DESIGN: CONTROLLED DECENTRALIZED TRAINING PHASES.
Phase-wise training. As consensus distance evolves throughout training. identifying its impact at every training step is infeasible. Also, since consensus distance and critical consensus distance (CCD) have different but significant dependencies on learning rate (Remark and Proposition 3 we would expect observations to be distinct over different learning rate phases but rather consistent within each phase. On CV tasks, stage-wise learning rate schedule is the common practice for SOTA training described in Section 4.2 thus the training
be naturally divided into phases with the corresponding learning rate, in each of which key training dynamics are significantly different from the others, such E, (Figure T). dh (Figure 5(b) and T-smoothness (Figure 5(c).. The transformer
4

---

Under review as a conference paper at ICLR 2021
(NLP task) has no well-defined training phases due the conventional inverse square root learning rate, thus for the sake of simplicity, we consider the entire transformer training as one phase as a preliminary study.
Individual phase investigation. In order to eliminate the coupling of effects from other phases, in each experiment we place only one phase under consensus distance control, while performing exact averaging (All-Reduce I on model parameters for the other unstudied phases. For the ease of presen- tation, the term "phase-z" refers to a training phase between - 1-th and x-th learning rate decay. The notation "dec-phase-x" indicates that only in "phase-z" the model is trained with a decentralized communication topology, while for other phases perform All-Reduce on model parameters. We compare the result of individual decentralized investigation with that of All-Reduce centralized training (on all training phases), to identify when (which phase) and how decentralized training influences final generalization performance 2
4.2 EXPERIMENTAL SETUP
Datasets and models. We empirically study the decentralized training behavior on the following
Iwo tasks, on CNN and transformer architectures: (1) Image Classification for CIFAR-10 (Krizhevsky
Hinton 2009) and ImageNet-32 (i.e. image resolution of 32) (Chrabaszez et al. 2017). with the standard data augmentation and preprocessing scheme (He et al. (0166]; and (2) Neural Machine Translation for the Multi30k dataset (Elliott et al., 2016). For Image Classification, ResNet-20 (He) et al. 2016) with different widths are used on CIFAR (default width of 1) and ImageNet-32 (width factor of 3). For Neural Machine Translation, a down-scaled transformer architecture (by 2x w.r.t.
the base model in Vaswani al. (2017)) is used. Weight initialization schemes follow Goyal et al.
2013) and Vaswani et al. (2017) respectively. Unless mentioned otherwise, our experiments are repeated over three random seeds.
(2017); He et al.
Training schemes. We use mini-batch SGD with a Nesterov momentum of 0.9 without dampening for image classification task, and Adam for neural machine translation task. Unless mentioned otherwise we use the optimal learning rate (Ir) for centralized training in order to observe the impact of decentralization on normal centralized training.
For image classification experiments, unless mentioned otherwise the models are trained for 300 and 90 epochs for CIFAR- 10 and ImageNet-32 respectively; the local mini-batch size are set to 32 and 64. By default, all experiments use learning rate scaling and warmup scheme (Goyal et al. 2017). The learning rate is always gradually warmed up from relatively small value (i.e. 0.1) for the first 5 epochs. Besides, the learning rate will be divided by 10 when the model has accessed specified fractions of the total number of training samples (He et al. 2016); we use { )) and
1 3. } for CIFAR and ImageNet respectively. All results tables are test top-1 accuracy. For experiments on neural machine translation, we use standard inverse square root learning rate schedule (Vaswani et al. 2017) with local mini-batch size 64. The warmup step is set 4000 for the mini-batch size of 64 and is linearly scaled down by the global mini-batch size.
Consensus distance control. For consensus control, adopt the "more gossip iterations" strategy introduced in Section 3.3 That is, we perform multiple gossip steps (if needed) until reaching the desired target consensus distance value. Two metrics are considered to set the consensus distance target value during the specified training phase:
constant consensus distance (main approact"): the target consensus distance for a phase the maximum consensus distance Emax of the current phase in normal (uncontrolled) decentralized training, multiplied by factor. For a given topology, the smaller the factor, the tighter consensus.
1 All- All-Reduce is used for all nodes reach an exact consensus model parameters. We demonstrate in of Section 4.3 that decentralization impacts on different phases are rather orthogonal, which justifies our design of examining one phase at a time.
3 We do tune the learning rate, but its choice does change the conclusion. E.g., no significant difference
he found for the curves at phase-1 for "ring (fine-tuned Ir)" and "dec-phase-1 (Em.))" Figure 2(a] and (b)
We have similar observations in Table Tafter the sufficient learning rate tuning on phase-1.
We use this one primarily since we can regulate the consensus distance in absolute values. We abuse the notation bit by using Emax alone indicate the decentralized training w/o consensus distance control.
5

---

Under review as a conference paper at ICLR 2021
0.5
Cereoradi phoce Gaa!l
114
Traning
craas (14
02
30
105
1.50
200
250
102
150
202
252
302
100
1.50
200
250
200
Epoch
Epoch
(a) Training loss.
(b) Training top-1 I accuracy.
(c) Test top-1 accuracy.
Figure 2: Learning curves for ResNet-20 on CIFAR-I0 (n 32). We compare tuned decentralized training (i.e.
"ring") ") with dec-phase-I on different target consensus distances.
Table 2:
The impact of consensus distance of different phases on generalization performance (test top- accuracy) of training ResNet-20
10. The All-Reduce performance for 32 and 64 92.82 + 0.27 and 92.71 0.11 respectively. The tuned decentralized performance (all phases on a fixed ring and w/o consensus distance control) for n = =32 and n= 64 are 91.74 + 0.15 and 89.87 + 0.12 respectively.
larget
dec phuse- 1
dec phase 2
dec phase
nodes
Fes
1/2 Ees
Ens
1/2 Emss
1/4 Ems
1/2 Ers
1/4 Fas
n=32
91.78 + 0.35 92 = 1121
92.71 2 0.10 93.01 0:011 92.99 # 0,30 92.87 0.11
92 22.60 + 0.00 92.82 4 0.21
92.85 0.21
90.31
0:04
02.60 0.10
adaptive consensus distance (in Appendix C.3. the target consensus distance E for the cur- rent step is the averaged local gradient norm @ exponentially moving averaged value o of Øt (accumulated during the corresponding phase).
scaled by a factor. For stability, we use the
We use a ring as our (main) decentralized communication topology as a particular hard instance with large spectral gap (cf. 7). allowing to study wide range of target consensus distances by modifying the number of communication rounds.
Epach
4.3 FINDINGS ON COMPUTER VISION TASKS
Figure The consensus distance for
ResNet-20 on CIFAR- (n=32) with ring.
In this section we present our empirical findings and pro- vide insights into how consensus distance at different phases impacts the training generalization for CV tasks (i.e. CIFAR-10, 10, Imagenet-32).
Critical consensus distance exists the initial training phase and ensures good optimization and generalization. In the initial training phase, both training and generalization performance in Figure 2 and Table 2). A smaller
heavily influenced by the consensus distance consensus distance in the early phase results in considerably faster optimization (training loss) and higher generalization performance (test accuracy) and these advantages persist over the entire training.
When the consensus is more loose (e.g. 1/2 Emax for CIFAR-10), although the optimization (training performance) can eventually catch up with the centralized convergence (c.f. Figure 2(a) and ((b)). considerable generalization gap still remains (92.36 v.s. 92.82 for the setup in Figure as shown in Table 2 This pattern is consistent" 77 in ImageNet-32 experiments, as shown in Table 3 These observations to some extent are also consistent with the insights of the critical learning phase described in Jastrzeskki et al. (2020); Frankle et al. 2020)) Golatkar et al. (2019) for traditional (centralized) training, where is argued that the initial learning phase is crucial for the final generalization.
Notably, perfect consensus distance is not required to recover the centralized training performance. For instance, 1/4 Emax sufficient in CIFAR- 10 experiments to approach the optimal centralized training performance in both optimization and generalization at the end. Smaller distances (c.g. 1/8 Emax 1/16 Emax) do not bring significant gain (92.77 77 and 92.72 72 respectively in Table 9 The performance saturates (c.f. 92.74 for 1/4 Emax) with significantly increased communication overhead (e.g. Figure 9 of Appendix C.I). This confirms that our analysis and discovery in Section 3 are
5 We also study the effect of using different communication topologies as the base communication topology in TTblleT7]and T6 The observations consistent with those of our main experiments with a ring topology.
6 Equivalent results for SGD without momentum can be found in Table 12 in the appendix.
In the case of ImageNet-32 with n 32, 1/2 Ema has already been tight enough recover the centralized training performance. But a significant performance drop can he observed between Emu and 1/2 E

---

Under review as a conference paper at ICLR 2021
Table 3: The impact of different consensus distances on generalization for different phases of training
ResNet-22033 on ImageNet-32. The centralized baseline performances for = 16 and n = 32 are 51.74 0.06 and 51.98 + 0.37 respectively, while those of decentralized training (on a fixed ring) are 51.04 = 0.06 and 50.17 + 0.04. The reported test top-1 accuracies are over two seeds.
lega 5
doc-phae-11
dec dsc-phaac-2
dec-phonc-3
das-pieee-4
modes
10
164
164
144
5-10
Table 4: Quality propagation across training phases with different consensus distances on ResNet-20 for CIFAR-I0 (Ring with n ===33 32). In phase-l and phase-2. the model parameters reach inexact consensus controlled by different target consensus distance E, while phase-3 performs All-Reduce on model parameters.
plase-2
phuse
Fea
E
92.48
92.46
92.31 + 0.23
1/4 Emss
92.73 0.111
92.66
0.08
92.69 + 0.19
93.10
0.22
0.15
92.91 + 0.06
Table 5: The impact of different numbers of training epochs (at phase-1) on generalization, for training ResNet-20 on CIFAR-10 (dec-phase-1 with n = 32). The number of epochs at phase-1 is chosen from (150, 200, 250), while the rest of the training reuses our default setup.
training epochs at phase-1
target E
150
200
250
91.78
0.35
91.91 + 0.19
92.04 0.14
1/2 Exax
92.36
1: 0.21
92.55 + 0.07
92.67 +: 0.13
max
92.74
0.10
92.91
0.15
92.84 0.20
sensible in the initial training phase: there exists critical consensus distance for the training, beyond which the impact of decentralization is negligible.
A non-negligible consensus distance middle phases can improve generalization over central- ized training. Surprisingly, it is not always the case that the generalization performance improves with the shrinking consensus distance. We observe that the phase right after initial training plateaus (e.g. p for CIFAR-IO, -O., phase-3 for Imagenet-32), non-negligible consensus distance actually boosts the generalization performance over the centralized training which has been deemed optimal. In CIFAR-10 dec-phase-2 experiments (Table 2 the generalization performance increases monoton- ically with the evaluated consensus distance and is consistently superior to that of the centralized training (e.g. 93.04, 92.99, 92.87 over 92.82 for 32). Analogous observation can be obtained in Imagenet-32 32 dec-phase-3 experiments (Table
It coincides with the observations firstly introduced in post-local SGD Lin et al. 2020b). where for better generalization, consensus distance is created among local machines by less frequent model parameter synchronization (All-Reduce) in late training phases (e.g. phase-2, phase-3 for CIFAR). Thus non-negligible consensus distance at middle phases can be viewed as a means of injecting proper noise as argued in Lin et al. (2020b), which reduces communication cost and in the meanwhile benefits generalization.
At the last phase of training, the consensus degree marginally impacts the generalization. Similar the initial training phase, the final convergence phase seems to favor small consen- sus distances in CIFAR- 10 experiments. However, its impact is less prominent in comparison: for dec-phase-3, performance of a smaller consensus distance (1/4 Emax) is only 0.25% and 0.37% higher than that of Emax for n = 32, 64 respectively (Table 2p. In Imagenet-32 experiments, dec-phase-3 performance not even affected by changes in consensus.
Quality propagation across phases. Our previous experiments only considered a single phase of decentralized training. We now evaluate the continued impact of consensus across the sequence of multiple phases. In Table we control the consensus distance for both phase-l and phase-2 when training CIFAR-10. When one phase is held under every specific consensus control, our previous findings for the other phase still hold. For instance, when we apply 1/2 Emax, 1/4 Emax consensus control to phase-2 (middle column in Table[4), we can still observe that smaller consensus distance in phase- results in a higher performance as in our previous finding. Hence our previous findings are valid in more general cases of decentralized training.
In Table 17 and 16 in Appendix C.3.1 phases, beyond which the gain in generalization (brought by noise injection) starts diminish.
we show that there exists optimal consensus distance at middle
7

---

Under review as a conference paper at ICLR 2021
Table 6: The importance of phase-1 for training ResNet-20 on CIFAR-10 10 (n 32), in terms of (1) target consensus distance and (2) the number training epochs. In phase-2 and phase-3, we perform decentralized training (w/o consensus distance control).
Iarget
1/2 S
1/4 Ea
1/8 Fea
# of epochs
150
91.74 + 0.15
92.31 + 0.12
02.81 + 0.22
02.91 + 0.15
92.94 0.07
200
91.81 0.22
92.88
0.20
93.00
0.18
93.01 + 0.10
92.90
0.17
250
92.09 = 0.23
92.74 0.11
93.15 4 0.26
92.99 = 0.24
93.31 = 0.06
Longer training cannot close the generalization gap caused by large consensus distances in initial training phase. As discussed above, large consensus distances in the initial phase can result in significant generalization loss due the optimization difficulty. Table [5) investigates whether a prolonged training on the initial phase can address this difficully: we prolong the phase-1 I for CIFAR-10 10 with range of consensus distances and leave the other training phases centralized. We can observe that although longer training is beneficial for each consensus distance, it cannot recover the generalization gap resulting from large consensus distance. For instance, the maximum gain (among all evaluated cases) of increasing the epoch number from 150 to 250 is 0.31% % at 1/2 Emix. which is lower than the average gain (around 0.6%) of merely reducing the consensus distance from Emax to 1/2 mmax Table 13 evaluates cases where dec- dec-phase-2 and dec-phase-3 are prolonged. We find that longer training in these two phases bring about negligible performance gain.
Practical guidelines: prioritizing the initial training phase. Apart from effectiveness (general- ization/test performance), efficiency (time) stands as the other crucial goal in deep learning, and thus how to allocate communication resource over the training becomes a relevant question.
As indicated by our first empirical finding (and theory in Sec- tion 3). initial training phase bears the greatest importance over all other training phases; therefore the communication expenditure should be concentrated on the initial phase to maintain consensus distance lower than the CCD. A list of communication topologies with superior spectral proper- ties, e.g. exponential graph (Assran et al., 2019) and random matching (Nadiradze et al. (020), can be utilized to achieve fast convergence in gossip averaging.
ospencrGalgiaah randm matering
Hiarrtee caponends gro?
10
10-4
gossip stops
Figure 3: Understanding the consensus av- eraging problem for different communica- tion topologies (n= 32). Results differ- communication scales are deferred to Appendix C.T
The late training phases should be less prioritized for com- munication resources, due to the generalization benefits from reasonable consensus distance in the middle phases. Pro- viding a rigorous way to quantify the optimal consensus distance is non-trivial, and we leave it as future work.
In Table we show that the above mentioned guideline is practically feasible: as long as the quality of the initial phase is ensured, we can afford to slacken the consensus control for later phases, in particular the middle phase. For instance, when the number of epochs is 150, a consensus control of 1/4 Emmx in the initial phase with uncontrolled middle and final phase is adequate to recover the centralized training performance (92.81 v.s. 92.82). Note that here the noise injection from the uncontrolled middle phase also contributes positively the performance. Table Appendix C additionally justifies the applicability of applying this guideline on exponential graph, and we leave more complicated communication scheme design as future work.
4.4 PRELIMINARY STUDY ON TRAINING TRANSFORMER MODELS
The critical consensus distance also exists in NLP tasks. Figure 4(c) demonstrates that 1/4 Emix target control on a ring is sufficient to recover the centralized training performance. Besides, the target consensus distance in this case can be reached by exponential graph (and thus target test performance, as shown in Figure (bd) These justify the importance of designing an efficient communication topology/scheme in practice so to effectively reach the critical consensus distance.
The definition of the communication topology detailed in Appendix C.1
8

---

Under review as a conference paper at ICLR 2021
4.5
Via wwi.eatttooo took
ouland lndd
20
2.4
3.5
30
38
Sporh
Epoch
(a) Decentralized baseline.
(b) Consensus distance E.
(c) Different target Es.
Figure 4: Learning curves for training Transformer on Multi30k (n = 32).
REFERENCES
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp. 344-353. PMLR,
2019.
Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Marc Tommasi. Personalized and private
peer-to-peer machine learning. volume 84 of Proceedings of Machine Learning Research, pp. 471-481, Playa Blanca, Lanzarote, Canary Islands, 09-11 Apr 2018. PMLR. URL http:
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311 2018.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions information theory, 52(6):2508-255) 2530, 2006.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arXiv:1707.0833 2017.
Ohad Shamir, and Lin Xiao. Optimal distributed online prediction Ofer Dekel, Ran The Journal of Machine Learning Research, 13:165-202. 202, 2012. using
J. C. Duchi, A. Agarwal, and M. J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3): 592-606, 2012. doi: 10. 1190//AC.2011.226111
Desmond Elliott. Stella Frank, Khalil Sima' an, and Lucia Specia. Multi30k: Multilingual english- german image descriptions. arXiv preprint arXiv:1605.0045 2016.
Jonathan Frankle, David J. Schwab, and Ari S. Morcos. The early phase of neural network training. In International Conference on Learning Representations, 2020. URL htttttts///peerrviiiie net / F RNFWS
Aditya Sharad Golatkar, Alessandro Achille, and Stefano Soatto. Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence. In Advances in Neural Information Processing Systems, pp. 10678-10688, 2019.
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 I hour. arXiv preprint arXiv:1706.02677 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- performance on imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026- 1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Tong He, Zhi Zhang, Hang Zhang, Zhongyue Zhang, Junyuan Xie, and Mu Li. Bag of tricks for image classification with convolutional neural networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 558-567, 2019.

---

Under review as a conference paper at ICLR 2021
Stanislaw Jastrzebski, Maciej Szymezak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho and Krzysztof Geras*. The break-even point on optimization trajectories of deep neural networks. In International Conference on Learning Representattons, 2020. URL https://
openrevies wwt.eeewwwweeeeeeeeeeeeeee.eeeee feret//ooumiiee wiw.rrmmidirrroom 9C44KWB
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo. Tancrède Lepoint, Yang Liu, Prateck Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. arXiv preprint arXiv: arXiv:/912.044 19/2.04977 2019.
David Kempe, Alin Dobra, and Johannes Gehrke Gossip- based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., PP. 482-491 IEEE, 2003.
Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In ICML 2019 Proceedings of the 36th International Conference on Machine Learning, volume 97, pp. -479-3487. PMLR, 2019. URL 9a html
http:://rroceedings... ml.. htt.eedddnnn.........p..sss/e//e /vtsss///////eee https/ss/www/////oooooosooo
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations, 2020a.
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, 2020b.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
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 in Neural Information Processing Systems, pp. 5330-5340, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. International Conference on Machine Learning, pp. 3043-3052. PMLR, 2018.
Tao Lin, Lingjing Kong, Sebastian Stich, and Martin Jaggi. Extrapolation for large-batch training in deep learning. In International Conference Machine Learning, 2020a.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-batches, use local SGD. In ICLR International Conference on Learning Representations, 2020b. URL
hittps://openree
net / www.mmiidduaoiooooooooo forumm11-BBeyy011997
Qinyi Luo, Jinkun Lin, Youwei Zhuo, and Xuchai Qian. Hop: Heterogeneity- decentralized training. In Proceedings of the Twenty- Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 893-907, 2019.
Giorgi Nadiradze, Amirmojtaba Sabour, Dan Alistarh, Aditya Sharma, Ilia Markov, and Vitaly Ak- senov. Swarmsgd: Scalable decentralized sgd with local updates. arXiv preprint arXiv:1910.12300. 2020.
A. Nedić and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE 2009.
Transactions on Automatic Control,
Giovanni Neglia, Chuan Xu, Don Towsley, and Gianmarco Calbi. Decentralized gradient methods: does topology matter? In AISTATS, 2020.
10

---

Under review as a conference paper at ICLR 2021
Shibani Santurkar, Dimitris Tsipras, Andrew Ilyas, and Aleksander Madry. How does batch normal- ization help optimization? In Advances Neural Information Processing Systems, pp. 2493, 2018.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In International Conference on Machine Learning, 2017.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Laurent Massoulié, and Yin Tat Lee. Optimal algorithms for non-smooth distributed optimization in networks. In Advances in Neural Information Processing Systems, pp. 2740-2749, 2018.
Christopher Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George E Dahl. Measuring the effects of data parallelism neural network training. arXiv preprint arXiv: 2018.
Chhavi Sharma, Vishnu Narayanan, and P Balamurugan. A simple and fast distributed accelerated gradient method. In OPT2019: 11th Annual Workshop on Optimization for Machine Learning. 2019.
Sebastian U. Stich and Sai Praneeth Karimireddy. The crror-feedback framework: Better rates for SGD with delayed gradients and compressed communication. CoRR, awsp/109.0033000 05355, 2019, URL
http:/ /ttp///axvvvvv/.. org/ abs 1909.99... 05350
John N. Tsitsiklis. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Advances neural information processing systems, pp. 5998-6008, 2017.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powergossip: Practical low-rank commu- nication compression in decentralized deep learning. In NeurlPS 2020 Thirty-fourth Conference Neural Information Processing Systems, 2020.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. MATCHA: speeding up decentralized SGD via matching decomposition sampling. arXiv preprint arXiv: 190500905 2019.
/tgg/bs//1/......bb 09435
Jianyu Wang, Vinayak Tantia, Nicolas Ballas, and Michael Rabbat. Slowmo: Improving
communication--fficcenn distributed sgd with slow momentum. In International Confer- ence on Learning Representations, 2020. URL httts::/
forrforum?id
SkxJ8REYPH
Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
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, pp. 1-10, 2018.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 1835)1885-1184, 2016. doi: 10.1 10.11337/10 URL https
//
11

---

Under review as a conference paper at ICLR 2021
A
THEORY
In this section, we prove the claims from Section S
A.1 PROOF OF REMARK 2 CRITICAL CONSENSUS DISTANCE
The proof of this claim follows by the following Lemma:
Lemma 5 Koloskova et al. 2020b), Descent lemma for non-convex case). Under the given assump- tions, and for any stepsize y AL" the iterates of D-SGD satisfy
Ex11 f(x s f(x
v
+ + 27202
Proof. By replacing E, in the above inequality with 4 we simplify:
E f(x(+1)) s f(x(1)
"
2L 7 7002
This inequality now matches (up to differences in the constants) the standard recursion that one can
derive for C-SGD (Dekel et al. 2012 Bottou al. 2018 Stich & Karimireddy 2019).
A.2 PROOF OF PROPOSITION 3. TYPICAL CONSENSUS DISTANCE
We need auxiliary (but standard) lemma, estimate the change the consensus distance between
iterations.
Lemma (Consensus distance). It holds
E (1- p/2) 3(1 p)>?
p
We give the proof of this statement shortly below. First, let us consider how this lemma allows the proof of the claim. For this, first consider a particular special case, and assume di S á, for constant 6. In this case, we can easily verify by unrolling the recursion:
3(1-))> (0² + +
3(1
E (1- p/2) 1=0
< p)>
p
Now, for the claim in the main text,
assumption that 6, changing slowly, that is, not
decreasing faster than exponentially: of < (1 + p/ p/4)ož+1- With this assumption, and observing
(1 (1-p/2) p/4)* < (1- - (1-p/4)', we can unroll as before
3(1 - 1p)>>(pp + po²) p/2)
E <
P
[-1
3(1 pp) + poo2)
(
( p2 p
+ )
$
Σ
p/4)
S 1 p)T²
p
Proof of Lemma 6
We use the following matrix notation here
())
(1)
(9)
E RRd
x1
x1) = x(0 x(1)
= = (1) 11001117 11
(0
(()))
(x) (8) (1)
vf(x())
Vx((x vfn(x!"))
12

---

0²) Under review as a conference paper at ICLR 2021
As reminder, =7 = 1
13 - [x()) -
-x,0 x and -= = 1 Σ. / //
n5 = X (1-1) x (1+1) x (x >VF((( (1) (1)) (_11T- w) 11
(x(0) ~VF(X ((01)
1111 -1) 1
- 11 - - w 11
2 (1 - P)
( 7P( ((1)))
-11 -
x (1-- p)
( [)(((())
1 -11 - 1)
|x(x10) VF(X | + +(1 (1-Dh> - ,5")) ||
7
< - (1-p)(1+0) x
1 11 11T-->[[
-1)
+ +11- 10(1+a |/(x'>> +11 - p)220n
12
(1- n 3(1 - p) 72 |
| + - -p)
?
p
A.3 SUFFICIENT BOUNDS TO MEET CRITICAL CONSENSUS DISTANCE
In this section, we show that the claimed bounds in Section 3.3 are sufficient conditions reach the CCD.
According to Remark there exists an absolute constant C, (w...o.g. C2 2) such that
2
0²
=t < C p)>²
+
p2
P
By smoothness,
0f V)i((
i=1
< 2 Σ [)(((x()) V
Σ
3 Vs(x!") -
+
3 -
Σ
+
< <35² + 31,23 3 {x)
Supposing -1- (1-ph²² <
लटT, we can therefore estimate
/²
3 [
2 +
33 + 33²
o²
E s C(1 ((1-ph" p)/
+
D2
p
|V[({(())]
2
2
g²)
< <30(1 - -2h
+
+ +
p2
p
and hence
[[(((()) 2
5
E < 6C - p)>
(6)
p²
2
p
The claimed bounds can now easily verified, by plugging the provided values into (6) For simplicity in the main text we assume that Ç 0 (we are in the datacenter training scenario).
Small and
By choosing 7 S inLO. we check that our previous constraint 72 2
6C12 is satisfied,
p²
|)((())1
7a2 C>2
Cn2C12
nL
13

---

Under review as a conference paper at ICLR 2021
C22
Small p. By choosing
- p S 50(1+yZn)) we note that p 2 TO
Moreover, our previous
constraint (1 -1-21 (1- 2
2² p²
.. is satisfied (note that S
I throughout). Hence
50
aI
422
[
10o² 9
r51/(41)
5 + Lm)
81
In the above calculations we for the simplicity assumed that < For the general non-iid data case when Ç > 0 we can calculate similar bounds on p. These bounds would have similar dependence on parameters, and would be stricter. Indeed, the typical consensus distance would be also influenced by non-iidness of the data and it is therefore harder to satisfy the CCD condition.
A.4 PROOF OF LEMMA 4 REPEATED GOSSIP
By the assumption stated in the lemma, it holds for each component W, of the product W W WT, i [1, k) that
Ew. XW,- | S (1 - (1-p) X p VX
E Raxn
Now lets estimate the parameter pw. Using that W. are independent
Ew XW I| Ew.... W. XW: k: ... W, X||
F W. Ew, YWW, - Y | F
where we defined Y = XW W2 and used that W 111 _111,
Y = XW W2 11 x 1 11 = =X.
Therefore,
Ew XW X S -ll Bw w. XWW... W₂ x
Applying the same calculations to the rest, we conclude that 1 pw = (1 - k))
14

---

Under review as a conference paper at ICLR 2021
B DETAILED EXPERIMENTAL SETUP
Comments on large-batch training. Coupling the quality loss issue of the decentralized training with the large-batch training difficulty non-trivial and out of the scope of this paper. Instead, we use reasonable local mini-batch sizes (together with the number of workers (denoted as n)), as well as the well-developed large-batch training techniques (Goyal et al., 2017). avoid the difficulty of extreme large-batch training.
Multi-phase experiment justification. The averaged local gradient norm di as well as the L- smoothness of ResNet-20 on CIFAR-IO for ring and complete graph (n 32) are shown in Figure 5 and Figure respectvvls....
The estimation procedure analogous that in Santurkar al. (2018); Lin al. (2020a): we take additional steps long the direction of current update, each with 0.2 of normal step size. This calculated at every training steps. The smoothness is evaluated as the maximum value of satisfying Assumption 2
355
30
67
2.0
15
120
232
230
1.00
(a) The consensus distance for de- centralized training.
(b) The averaged of the local
The gradient Lipschitz for both decentralized training.
gradients decentralized training.
Figure 5: Justification for our multiple-phase experimental design choice (on ring graph). We run ResNet-20 on CIFAR- 10 (n = 32) with the ring topology. We observe the three quantities most relevant to optimization all naturally form three phases, dictated by the learning rate schedule.
Lomoothness
0
100
150
200
250
300
50
100
150
200
250
300
Epoch
Epoch
(a) The averaged norm of the local gradients for centralized training.
(b) The gradient Lipschitz curve for both cen- tralized training.
Figure Justification for our multiple-phase experimental design choice (on complete graph). run ResNet-20 on CIFAR-10 (2= with the complete topology. We can again observe the three quantities most relevant optimization all naturally form three phases, dictated by the learning rate schedule.
C ADDITIONAL RESULTS
C.I UNDERSTANDING ON CONSENSUS AVERAGING PROBLEM
We study host of communication topologies: (1) deterministic topologies (ring, and complete graph) and (2) undirected time- timevvarying topologies (illustrated below).
Random matching (Boyd et al. 2006). At each communication step. all nodes are divided into
non-overlapping pairs randomly. Each node connects all other nodes with equal probability.
Exponential graph (Assran et al. 2019). Each is assigned a rank from to n 1. Each node i periodically communicates with list nodes with rank + 20, i ..... + [n 1) In the pe--peerrrr-odoe experiments, each node only communicates to node by cycling through its list. The formed graph undirected, i.e., both transmission and reception take place in each communication.
15

---

Under review as a conference paper at ICLR 2021
Bipartite exponential graph (Lian al. 2018 Assran et al. 2019). In order to avert dead- locks (Lian et al. 2018), the node with an odd rank i cycles through nodes with even ranks ........ + 2 21lgg( 1j] by transmitting message and waiting for
i + 20 1, response. while the nodes with even ranks only await messages and reply upon reception.
Table @ displays the spectral gap and node degree of studied topologies, and Figure 7 provides the convergence curves for different communication topologies graph scales. Figure in addition visualizes the spectral gap (in expectation) for different communication topologies.
Table 7: Spectral gap and node degree of studied topologies.
Topologies
Spectral Gaps (in expectation) Node degrees (n nodes)
Complete
Fixed ring
0
2
Exponential graph
0(1
2
Bipartite exponential graph Random matching
((1)
0(1)
sadomn gran
matcing
maichng patto (appeaa
30-0
20-1
10
10-
10-1
10
16-4
16
(b)
32
(c) 64
Figure 7: The convergence curves for the consensus averaging problem on different communication topologies and different scales (i.c., n= 16, n= 64 and n = 128). This figure complements the Figure in the main text.
spectral gap (1- A [w))
1.000
1.000
ring
0.975
0.975
exponential graph
spectral gap Aal
random matching
0.950
0.950
bipartite exponential
0.925
0.925
0.900
ring exponential graph
0.900
0.875
0.875
bipartite exponential graph
20
60
80
100
120
50
100
150
200
250
gossip steps (t)
gossip steps
(a) n 16
(b) n 32
Figure 8: The spectral gap (in expectation) of different communication topologies on different graph scales.
Table 8 examines these topologies on a standard deep learning benchmark with different graph scales, while Figure / visualizes the required communication rounds (per gradient update step) for range of consensus distance targets.
Complete
Fixed ring
Exponential graph Bipartite exponential graph Random matching
n=16 n=32
92.91
0.12
92.51 0.19
92.63 + 0.30
92.76 + 0.04
92.65 + 0.15
92.82 1 0.27
91.93 + 0.05
92.64 + 0.04
92.29 + 0.15
92.27 + 0.17
Table The effect of communication topologies and scales (ResNet-20 on CIFAR-10 with 32) The test top-1 accuracies are over three seeds with fine-tuned learning rates.
C.2
UNDERSTANDING THE DECENTRALIZED DEEP LEARNING TRAINING FOR CV TASKS
We ring our underlying decentralized communication topology in this subsection.
16

---

Under review as a conference paper at ICLR 2021
# of comm. rounds to reach the distance
30
random matching exponential graph
ring
20
10
0
2
3
6
7
Consensus distance =
Figure Target consensus distance v.s. the required communication rounds (per gradient update step), for training ResNet-20 on CIFAR-10 with different communication topologies. We focus on the setup of dec-phase-1 and vary the target consensus distance for different communication topologies. Due to the changing consensus distance over the training (of the interested phase-1), ), consider the averaged consensus distance. The topologies of exponential graph and random matching, empower the capability of fast convergence in gossip averaging and thus only few steps are required to reach the target consensus distance.
Elaborated results on consensus distance control. Table 9 is the elaborated version of Table with more evaluated consensus distances.
Table 9: The impact consensus distance of different phases on generalization performance (test top-1 accuracy) of training ResNet-20 on CIFAR-10, 10. The centralized baseline performance for n 32 and n= 64 are 92.82 + 0.27 and 92.71 + 0.11 respectively. The performance of decentralized training (all phases ring and w/o consensus distance control) for 32 and 64 91. 0.15 and 89.87 0.12 respectively.
fixed
looptanc
Jacehmos
@ooyleac2 dooylase
144
102
14
180
10
1922
11 10.00
TUUN BOI 1030 10.0
10.50
0100 1231
4464 (0:31 2.1.2 00.18 a 600
00uii 0.17
16.14 BUN 90.94 0.10 10.99-0
10
1.12 0050 m
00.00 2..0
10:00000 (255 92.5 1010
SlowMo cannot fully address the decentralized optinizattonndgeerraiiatoon difficulty. Ta- ble 10 studies the effectiveness of using SlowMo for better decentralized training. We can witness that even though the performance of decentralized training can boosted to some extent, it cannot fully address the quality loss issue brought by decentralized training.
Table 10: The effect of SlowMo for decentralized learning, for training ResNer20 CIFAR-10 (л = 32). The results (over three random seeds) the tuned hyper- parameter of SlowMo mentioned in the original paper (Wang et al. 2020). The centralized baseline performance 92.82 + 0.27.
topology
w/o SlowMo
w/ SlowMo
exponential graph
92.63 + 0.22
92.42 + 0.36
ring
91.74 = 0.15
92.53 + 0.10
On the ineffectiveness of tuning learning rate. Table displays the results of training ResNet- 20 on CIFAR-10 (32 nodes), with fine-tune tne-tuned learning rate phase-1; 1; learning rate tuning cannot address the test quality loss issue caused by the large consensus distance (i.e. over the CCD).
Table 11: Phase-1 consensus distance control performance with fine-tuned learning rates of training ResNet-20 on CIFAR-10 (n 32). Setup this table is identical to of Table except that we fine- tune the learning rate for each case from a grid of linear scaling-up factors {30, 28, 26, 24, 22). The results are over three seeds.
1/2 3
1/4 E
tuned Ir from the search grid w/ default Ir
91.95 0.26
92.35 0.24
92.54 0.08
91.78 + 0.35
92.36 0.21
92.74 + 0.10
Distance control on SGD without momentum. results for SGD without momentum. We can observe consistent pattern in Table
Table 12 contains the consensus distance control
17

---

Under review as a conference paper at ICLR 2021
Table 12: The impact of consensus distance generalization performance with vanilla SGD (without momentum) (test top-1 accuracy) training ResNet-20 on CIFAR-I0. The All All-Reduce performance and n- 64 are 90.64 + 0.19 and 90.58 + 0.26 respectively. The tuned decentralized performance (all phases on a fixed ring and w/o consensus distance control) for n = and n 64 are 90.30 + 0.14 and 88.92 + 0.23 respectively. We repeat experiments for n = 32 for 3 seeds and = 64 for 2 seeds.
=2
target E
dec-phase:
dec-phase-2
nodes
1/2Emax
1/43
1/22 max
1/4
max
max
32 =
90.51 + 0.05
90.74 + 0.14 90.88 + 0.37
90.64
0.18
90.55 + 0.19
90.57 + 0.17
64
88.8 + 0.03 89.89 + 0.03 90.43 = 0.05
90.63
0.37
90.46 = 0.15 90.63 + 0.25
Prolonged training for dec-phase-2 and dec-phase-3. Table [3 shows the results for prolonged dec-phase-2 and dec-phase-3 on CIFAR-10 with ResNer20. We can observe although longer training duration increases the performance, the improvement is rather small.
Table 13: The impact of different numbers of training epochs (at phase-2 and phase-3) on generalization. for training ResNet-20 on CIFAR-I0 10 (ring topology with 32). The number of epochs at phase- I chosen from (75, 100, 125), while the rest of the training reuses our default setup. Experiments are run over 2 seeds. target 3
dec- 2
dec dec-phase-3
# nodes
max
1/2 max
1/4 max
mmax
1/2 Emax
1/4 max
75 epochs
93.04 + 0.01
92.99 + 0.30 92.87 + 0.11
92.60 + 0.00 92.82 + 0.21 92.85 + 0.24
100 epochs
93.08 + 0.08
93.05 0.16
92.94 + 0.03
92.86 0.16 92.90 + 0.18
92.93
0.19
125 epochs
93.19 + 0.16 93.11 + 0.17 93.06 + 0.07
92.87 + 0.23 92.99 + 0.25 92.97 + 0.20
The impact of half cosine learning rate schedule. Table examiines the existence of the critical consensus distance with half cosine learning schedule (this scheme is visited in He et al. (2019) as new paradigm for CNN training). We can witness from Table[[]thal that the effect of critical consensus distance can be generalized to this learning rate schedule: there exists a critical consensus distance in the initial training phase (as revealed in the inline Figure Table 14 and ensures good optimization and generalization.
Table 14: The impact of half cosine learning rafe schedule on generalization, for training ResNec20 on CIFAR-10 (ring topology with 32). The inline figure depicts the uncontrolled consensus distance the whole training procedure through the half-cosine learning rate schedule. Only one training phase is considered for the consensus distance control and the numerical results in the table are averaged over seeds.
15.0
12.5
10.0
6
7.5
0
2000
4000
6000
8000
10000
12000
14000
epach
Ring (Emax)
Ring (1/2Emax)
Ring (1/ (1/45max)
Ring (1/8Emax)
Complete
92.10 + 0.06
92.40 + 0.10
92.83 0.11
92.78 0.05
92.84 + 0.22
18

---

Under review as a conference paper at ICLR 2021
C.2.1 ADAPTIVE CONSENSUS DISTANCE CONTROL
In Table 15| we apply the adaptive consensus distance control in the experiments. The observations are consistent with those in constant consensus distance control experiments.
Table 15:
The impact of different consensus distances on optimization and/or generalization, for different
phases of training ResNet-20 on CIFAR-I0 (n = 32). The table is almost identical to Table 2 except the consensus distance is controlled by the (runtime) averaged norm of the local gradients (i.c. adaptive consensus distance).
Emax
4
2
cma 2
0.5gpmm
Phase 1
91.78 + 0.35
91.65 + 0.31
92.47 + 0.18
92.63 + 0.04
92.80 = 0.16
Phase 2
93.01 = 0.01
93.05 + 0.18
93.01 + 0.03
93.03 + 0.08
92.95 = 0.10
Phase 3
92.94 + 0.07
92.87 + 0.18
92.83 + 0.20
C.3 CONSENSUS CONTROL WITH OTHER TOPOLOGIES
In Table T6 we exert consensus control with an exponential graph as the base communication topology. We can observe that our findings from main experiments with ring base topology are valid.
Table 16: The impact of quality propagation across phases (in both phase 1 and phase 2) on an undirected vary-ng exponential graph (n2 32), similar Table 4
pluse
local update
local updnl
local updais step
plase
12 30.8
97-51
0.006
72
02.50
02.70
10.0 0.10
0.22 1255 1Ers 200 92 22.5
02.22
10.0 0221 92.0 12.0 0.20 5011 02. 0.35 92.5 M2.7
C.3.1 THE EXISTENCE OF THE OPTIMAL CONSENSUS DISTANCE FOR NOISE INJECTION.
Table 17 uses a different communication topology (i.e. varying exponential graph) for decentral- ized optimization. Here exponential graph with large spectral gap is applied to CIFAR-10 10 dec-phase-2 training. We apply the adaptive consensus distance control in this set of experiments. We can observe that increasing consensus distance further by taking local steps improves generalization, however, too many local steps diminish the performance. For instance, for ratio=2, the performance peaks at local update steps and drops local update 4. It points out that optimal consensus distance is required to inject proper stochastic noise for better generalization.
Table 17: The impact of different consensus distances at phase 2, for training ResNet-20 on CIFAR-10 with time-varying exponential graph (n 32). The baseline performance of using exponential graph for the entire decentralized training 92.64 0.04. The reported test top-1 accuracies are averaged over three seeds.
local update step =1
local update step =
local updise step
20
0.5
20p
0.5
20
0.5
82.83 = 0.12
92.80 + 0.00
32.74 0.27
92.77 + 0.19
90.04 = 0.08
52.85 + 0.37
92.50 + 0.02
92.87 0.10
92.90 = 0.12 52.88 0.19
C.4 RESULTS FOR TRAINING TRANSFORMER ON MULTI30K
We additionally report the decentralized training results, for a downsampled transformer models (by the factor of 2 w.r.t. the base model in Vaswani et al. (2017)) on Multi30k (Elliott et al. 2006) 6). Figure T0 shows that the straightforward application of Adam the decentralized manner does encounter generalization problems, which are attributed to the fact that the different local moment buffers (in addition to the weights) become too diverse. Tuning the learning rate schedule cannot address the issue of decentralized Adam, as shown in the Figure 10(b)
19

---

Under review as a conference paper at ICLR 2021
4.0
4.0
Al Reduco Decentral (complate) Decentralized (rig)
Decontraizo lood (wanmuo stcs 125)
Validation loss
3.5
Validation loss
3.5
Decentrulon kusd tearmup
Decentralio loed [wsmmup
Decontralzed
Decantra
2.5
2.5
2.0
2.0
1.5
10
20
30
40
50
60
10
20
30
40
Epoch
Epoch
(a) The limitation of decentralized learning with Adam, (b) Tuning the learning rate cannot alleviate the issuc caused the different local moment buffers.
of decentralized Adam.
Figure 10: Learning curves for training the transformer model on the Multi30k dataset (n = 32). In Figure T0rb) we tune the the number of warmup steps as as way of tuning the learning rate, as the learning rate used transformer training (Vaswani al. (017)) deterministically controlled by the model's dimensionality. the current step index, and number of warmup steps.
20


Reviews:
[{"review_id": "_NdYak17A7a", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies decentralized gradient methods for training deep networks. It focuses on the so-called \"critical consensus distance\" and how disagreement during different stages of training ultimately effects optimization (training loss) and learning (generalization error). Theory is provided for the case of synchronous symmetric averaging methods, and the paper is complemented with detailed experiments on CIFAR and tiny-ImageNet.\n\nThis is a nice contribution to the growing literature on decentralized training for deep neural networks. The connection between consensus distance and performance has previously been studied to a limited extent in various settings, so the contribution of this work is somewhat incremental. However, this paper makes the connection somewhat more rigorous through the theoretical developments in Section 3, and it provides a more detailed empirical investigation than previous work. I expect the results to be useful to those working on decentralized training and am supportive of accepting it.\n\nI have a few suggestions and comments, about which I look forward to hearing from the authors.\n1. You mention that consensus distance has previously been investigated to some extent (e.g., Fig 2 in Assran et al. 2019). Are there connections between consensus distance and other quantities that have been considered in the literature to relate training to performance (e.g., gradient diversity as in Yin et al. 2017, or the closely related gain ratio in Johnson et al., 2020). Similarly, is there a connection to stochastic weight averaging (Izmailov et al. 2018) and it's parallel version (Gupta et al., 2020)?\n2. It is not clear if there are specific aspects of the tasks considered that are important for the findings to hold. CIFAR-10 and ImageNet-32 are both relatively small datasets. Is it possible that in the centralized setting, ResNet-20 is overfitting, and the error from decentralized SGD has a regularizing effect, leading to better generalization? It would be interesting to perform further experiments to explore if this is the case. \n3. It would also be interesting to know if the results similarly carry over to the standard (higher-resolution) ImageNet training and models (e.g., ResNet-50), to know if the phenomena observed are relevant to large-scale training. While I appreciate that CIFAR and ImageNet-32 experiments are useful for quick experimentation, and running experiments on the standard ImageNet task are much more computationally expensive, CIFAR and ImageNet-32 are not very reflective of tasks where one would normally use distributed or decentralized training, since one can easily train a model on them using a single GPU in a reasonable amount of time (~1 hour).\n4. Regarding the experiments in Table 5 (longer training), why focus on prolonging training in phase 1? I would expect that extending later phases would potentially allow to overcome issues due to large consensus distances in phase 1. Did you explore this?\n5. The analysis focuses on symmetric (push-pull) mixing. Do you expect the same trends to carry over to push-only methods such as those considered in Assran et al., 2019?\n6. Nowadays, the half-cosine learning rate schedule is also commonly used for CV tasks (He et al. 2018). How do you expect this to affect CCD and the analysis leading to Remark 2?\n7. How does using more gossip iterations impact the practical utility of these methods? In particular, standard implementations of all_reduce only require that each node communicate 2 copies of the parameters per iteration. Now that we need to potentially perform multiple rounds of gossip between each optimizer update, are decentralized methods still attractive for reducing overall training time? On a related note, Tsianos and Rabbat (2014) also proposed to use multiple rounds of gossip to essentially reduce the CCD for convex problems, and show that it can lead to overall less communication overhead to reach a desired level of accuracy. Is it possible to show something similar in this setting?\n\nAdditional references mentioned:\n* Gupta, Serrano, DeCoste, \"Stochastic weight averaging in parallel: Large-batch training that generalizes well,\" ICLR 2020 and arxiv:2001.02312\n* He, Zhang, Zhang, Zhang, Xie, and Li, \"Bag of tricks for image classification with convolutional neural networks,\" CVPR 2019 and arxiv:1812.01187\n* Izmailov, Podoprikhin, Garipov, Vetrov, and Wilson, \"Averaging weights leads to wider optima and better generalization,\" arxiv:1803.05407\n* Johnson, Agrawal, Gu, and Guestrin, \"AdaScale SGD: A user-friendly algorithm for distributed training\" ICML 2020 and arxiv:2007.05105\n* Tsianos and Rabbat, \"Efficient distributed online prediction and stochastic optimization with approximate distributed averaging\" IEEE Trans Signal and Information Procesing over Networks 2016 and arxiv:1403.0603\n* Yin, Pananjady, Lam, Papailiopoulos, Ramchandran, and Bartlett, \"Gradient diversity: A key ingredient for scalable distributed learning,\" AISTATS 2018 and arxiv: 1706.05699\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9-xu4M2Atva", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work investigated a very interesting topic about generalization in decentralized deep learning. The authors identify the consensus distance as the key factor that affects the generalization performance of decentralized training. In general, the paper is well written and there are several interesting observations and discoveries involved regarding the generalization performance of decentralized learning. But the quality and significance of the work seem not very high.\n\n1. There is no clear link between the theory part and the numerical results. (Th1 is based on previous work.) The other results, e.g., remark 2, proposition 3, and lemma 4 cannot claim how the consensus distance affects the generalization error. All the statements are based on the observations in terms of consensus distance shown in eq4. I can only agree that the distance is related to the generalization error.\n\n2. Also, Th1 quantified the convergence rate for SGD, while in the numerical results the authors used accelerated SGD and adam. \n\n3. How did the critical distance be calculated? For example, what are L and sigma approximated?\n\n4. From the numerical results, the authors at least claim two points of linking the critical consensus distance and the performance: i) the critical distance is important to the initial training phase; ii) a non-negligible consensus distance can improve the generalization performance. There is no convincing explanation that the critical distance contributes to the generalization. Also, there is no clear definition of either the initial training phase or middle phase, since the learning rate is chosen by the authors so that it might not reflect the true convergence phases. (especially in this case a warm-up scheme was used). In all, the discussion about the relation between the general error and critical distance is vague.\n\n5. Except for the ring case, the generalization error of the most decentralized learning results might be worse than the centralization learning within 0.5%, which seems not that significant. Comparing the linear speed up benefited from the decentralized training, is this loss significant?  \n\nIn summary, I don’t think the theory part is very strong in this paper, and the relation between the critical distance and the generalization error needs to be further justified. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "77U6-cjQ-Z", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper studies the problem of decentralized training where several computing units are used simultaneously to process the data, and computing units are assumed to be connected over a network. The main focus is to better understand the role of consensus, or lack there of, into the generalization abilities of decentralized training. The authors describe an upper bound for dissimilarity of local variables that guarantees the performance of decentralized training is as good as centralized one. Moreover, some heuristic guidelines are proposed to control consensus during training process. Some numerical evidence is also provided.\n\nReasons for score:\n\nI believe the paper is well written and the results are useful for the literature. There are a couple of issues that need to be addressed. Moreover some context item that need to be elaborated more carefully.\n\nSome items that need to be elaborated.\n\n1. The main argument of the paper sees to be that generalization might be affected by decentralized training, as initially pointed out by Table 1.  However, at some point there is a conceptual leap and the discussion transforms into analyzing convergence rates. Although there is a connection between rates and generalization, one is not equivalent to the other. The provided analysis is done on rates, I do not think one can translate that into generalization so straightforward.\n\n2. The authors claim to analyze the problem theoretically. However, wha seems to be the main result is left as Remark 2. I believe  Remark 2 is a statement that needs to proven, as represents the main issues addressed in the paper, namely, how consensus affects convergence rates.\n\n3. The authors mention that the analysis is made on non-momentum algorithm, but experiments are made with the momentum version. This is an issue, as the translation of the obtained results into the momentum method needs to be proven. How are the authors sure that momentum does not play a role into the dependency on consensus?\n\n4.  One main concept seems to be that \\phi_t does not change too fast. This is left for the appendix. Such a main concept needs to be spelled out in the main text.\n\n5. Is there a cite for Lemma 4?,  there seems to be studied in the literature before.\n\n6. I read Remark 2 as the main result rather than Proposition 3.\n\n7. I value the experimental results,  they are rather informative and complete.\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4O-8uRk2zaZ", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors consider the decentralized optimization problem and explain the generalization gap using the consensus distance. They show that when the consensus distance does not grow too large, the performance of centralized training can be reached and sometimes surpassed. The conducted experiments are extensive and the delivered message is pretty clear -- Critical consensus distance exists in the initial training phase and ensures good optimization and generalization, while a non-negligible consensus distance at middle phases can improve generalization over centralized training.\n\nOn the theory side, the main contribution is Remark 2 and proposition 3, but why remark 2 relates to generalization are unclear (it only shows the convergence rate), neither does proposition 3 (it only shows the consensus distance). How do we relate the convergence rate differences with the generalization capability is unclear. So I would say the abstract is a bit overclaiming, the authors better tune down their claims to practical only, without any theoretical guarantees -- \"We identify the changing consensus distance between devices as a key parameter to explain the gap between centralized and decentralized training. We show that when the consensus distance does not grow too large, the performance of centralized training can be reached and sometimes surpassed.\"  \n\nOn the literature side, besides the gossip-based decentralized methods, there are also many primal-dual based decentralized optimization methods [1,2]. In those methods, there will be no mixing matrix and hard to run multiple mixing steps, the authors better also comment on those and discuss how the proposed findings can help these works. \n\nOverall speaking, I feel the motivation and message delivering is clear, though I am afraid that the main contribution falls into the practical findings (they are also important though) instead of the theoretical guarantees -- there is a mismatch between theory and implementations. \n\n[1] Mingyi Hong, Davood Hajinezhad, and Ming-Min Zhao. \"Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks.\" International Conference on Machine Learning. 2017.\n[2] Haoran Sun and Mingyi Hong. \"Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms.\" IEEE Transactions on Signal Processing 67.22 (2019): 5912-5928.\n\n------\nupdate after rebuttal\n\nAfter reading the author's response, the authors stated that they indeed identify the optimization difficulty and consensus distance in theory, while only empirically justify its generalization on training performance. As also pointed out by reviewers 1 and 3, the gap between the convergence rate/consensus distance and the generalization capability still exists, causing the mismatch between the theory and the simulations. But at the same time, the work can also serve as an initial good start and raises good points for the literature. I will keep my score unchanged.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study the problem of (insufficient) generalization in gossip-type decentralized deep learning. Specifically, they establish an upper bound on the square of the consensus parameter distance, which the authors identify as a key quantity that influences both optimization and generalization. This upper bound (called the critical consensus distance) can be monitored and controlled during the training process via (e.g.) learning rate scheduling and tweaking the amount of gossip. A series of empirical results on decentralized image classification and neural machine translation are presented in support of this observation.

Initial reviews were mixed. While all reviewers liked the approach, concerns were raised about the novelty of the results, the lack of theoretical depth, and the mismatch between theory and experiments. Overall, the idea of tracking consensus distance to control generalization seems to be a practically useful concept.  During the discussion phase the authors were been able to (convincingly, in the area chair's view) respond to a subset of the criticisms. 

Unfortunately, concerns remained regarding the mismatch between the theoretical and empirical results, and in the end the paper fell just short of making the cut. 

The authors are encouraged to carefully consider the reviewers' concerns while preparing a future revision.
Decision: Reject