summaries: 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. 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. This 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.
abstractText: 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.
references.authors: Mahmoud Assran Nicolas Loizou Nicolas Ballas Mike Rabbat
references.title: Stochastic gradient push for distributed deep learning
references.venue: In International Conference on Machine Learning,
references.authors: Aurélien Bellet Rachid Guerraoui Mahsa Taziki Marc Tommasi
references.title: Personalized and private peer-to-peer machine learning
references.venue: Proceedings of Machine Learning Research,
references.authors: Léon Bottou Frank E Curtis Jorge Nocedal
references.title: Optimization methods for large-scale machine learning
references.venue: Siam Review,
references.authors: Stephen Boyd Arpita Ghosh Balaji Prabhakar Devavrat Shah
references.title: Randomized gossip algorithms
references.venue: IEEE transactions on information theory,
references.authors: Patryk Chrabaszcz Ilya Loshchilov Frank Hutter
references.title: A downsampled variant of imagenet as an alternative to the cifar datasets
references.venue: arXiv preprint arXiv:1707.08819,
references.authors: Ofer Dekel Ran Gilad-Bachrach Ohad Shamir Lin Xiao
references.title: Optimal distributed online prediction using mini-batches
references.venue: The Journal of Machine Learning Research,
references.authors: J.C. Duchi A. Agarwal M.J. Wainwright
references.title: Dual averaging for distributed optimization: Convergence analysis and network scaling
references.venue: IEEE Transactions on Automatic Control,
references.authors: Desmond Elliott Stella Frank Khalil Sima’an Lucia Specia
references.title: Multi30k: Multilingual englishgerman image descriptions
references.venue: arXiv preprint arXiv:1605.00459,
references.authors: Jonathan Frankle David J. Schwab Ari S. Morcos
references.title: The early phase of neural network training
references.venue: In International Conference on Learning Representations,
references.authors: Aditya Sharad Golatkar Alessandro Achille Stefano Soatto
references.title: Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Priya Goyal Piotr Dollár Ross Girshick Pieter Noordhuis Lukasz Wesolowski Aapo Kyrola Andrew Tulloch Yangqing Jia Kaiming He
references.title: Accurate, large minibatch sgd: Training imagenet in 1 hour
references.venue: arXiv preprint arXiv:1706.02677,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification
references.venue: In Proceedings of the IEEE international conference on computer vision,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Tong He Zhi Zhang Hang Zhang Zhongyue Zhang Junyuan Xie Mu Li
references.title: Bag of tricks for image classification with convolutional neural networks
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Stanislaw Jastrzebski Maciej Szymczak Stanislav Fort Devansh Arpit Jacek Tabor Kyunghyun Cho Krzysztof Geras
references.title: The break-even point on optimization trajectories of deep neural networks
references.venue: In International Conference on Learning Representations,
references.authors: David Kempe Alin Dobra Johannes Gehrke
references.title: Gossip-based computation of aggregate information
references.venue: In 44th Annual IEEE Symposium on Foundations of Computer Science,
references.authors: Anastasia Koloskova Sebastian U. Stich Martin Jaggi
references.title: Decentralized stochastic optimization and gossip algorithms with compressed communication
references.venue: In ICML 2019 - Proceedings of the 36th International Conference on Machine Learning,
references.authors: Anastasia Koloskova Tao Lin Sebastian U Stich Martin Jaggi
references.title: Decentralized deep learning with arbitrary communication compression
references.venue: In International Conference on Learning Representations,
references.authors: Anastasia Koloskova Nicolas Loizou Sadra Boreiri Martin Jaggi Sebastian U Stich
references.title: A unified theory of decentralized SGD with changing topology and local updates
references.venue: In International Conference on Machine Learning,
references.authors: Alex Krizhevsky Geoffrey Hinton
references.title: Learning multiple layers of features from tiny images
references.authors: Xiangru Lian Ce Zhang Huan Zhang Cho-Jui Hsieh Wei Zhang Ji Liu
references.title: Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Xiangru Lian Wei Zhang Ce Zhang Ji Liu
references.title: Asynchronous decentralized parallel stochastic gradient descent
references.venue: In International Conference on Machine Learning,
references.authors: Tao Lin Lingjing Kong Sebastian Stich Martin Jaggi
references.title: Extrapolation for large-batch training in deep learning
references.venue: In International Conference on Machine Learning,
references.authors: Tao Lin Sebastian U. Stich Kumar Kshitij Patel Martin Jaggi
references.title: Don’t use large mini-batches, use local SGD
references.venue: In ICLR - International Conference on Learning Representations,
references.authors: Qinyi Luo Jinkun Lin Youwei Zhuo Xuehai Qian
references.title: Hop: Heterogeneity-aware decentralized training
references.venue: In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems,
references.authors: Giorgi Nadiradze Amirmojtaba Sabour Dan Alistarh Aditya Sharma Ilia Markov Vitaly Aksenov
references.title: Swarmsgd: Scalable decentralized sgd with local updates
references.venue: arXiv preprint arXiv:1910.12308,
references.authors: A. Nedić A. Ozdaglar
references.title: Distributed subgradient methods for multi-agent optimization
references.venue: IEEE Transactions on Automatic Control,
references.authors: Giovanni Neglia Chuan Xu Don Towsley Gianmarco Calbi
references.title: Decentralized gradient methods: does topology matter
references.venue: In AISTATS,
references.authors: Shibani Santurkar Dimitris Tsipras Andrew Ilyas Aleksander Madry
references.title: How does batch normalization help optimization
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Kevin Scaman Francis Bach Sébastien Bubeck Yin Tat Lee Laurent Massoulié
references.title: Optimal algorithms for smooth and strongly convex distributed optimization in networks
references.venue: In International Conference on Machine Learning,
references.authors: Kevin Scaman Francis Bach Sébastien Bubeck Laurent Massoulié Yin Tat Lee
references.title: Optimal algorithms for non-smooth distributed optimization in networks
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Christopher J Shallue Jaehoon Lee Joseph Antognini Jascha Sohl-Dickstein Roy Frostig George E Dahl
references.title: Measuring the effects of data parallelism on neural network training
references.venue: arXiv preprint arXiv:1811.03600,
references.authors: Chhavi Sharma Vishnu Narayanan P Balamurugan
references.title: A simple and fast distributed accelerated gradient method
references.venue: In OPT2019: 11th Annual Workshop on Optimization for Machine Learning,
references.authors: Sebastian U. Stich Sai Praneeth Karimireddy
references.title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication
references.venue: CoRR, abs/1909.05350,
references.authors: John N. Tsitsiklis
references.title: Problems in decentralized decision making and computation
references.venue: PhD thesis, Massachusetts Institute of Technology,
references.authors: Ashish Vaswani Noam Shazeer Niki Parmar Jakob Uszkoreit Llion Jones Aidan N Gomez Łukasz Kaiser Illia Polosukhin
references.title: Attention is all you need
references.venue: In Advances in neural information processing systems,
references.authors: Thijs Vogels Sai Praneeth Karimireddy Martin Jaggi
references.title: Powergossip: Practical low-rank communication compression in decentralized deep learning
references.venue: In NeurIPS 2020 - Thirty-fourth Conference on Neural Information Processing Systems,
references.authors: Jianyu Wang Anit Kumar Sahu Zhouyi Yang Gauri Joshi Soummya Kar
references.title: MATCHA: speeding up decentralized SGD via matching decomposition sampling
references.venue: arXiv preprint arXiv:1905.09435,
references.authors: Jianyu Wang Vinayak Tantia Nicolas Ballas Michael Rabbat
references.title: Slowmo: Improving communication-efficient distributed sgd with slow momentum
references.venue: In International Conference on Learning Representations,
references.authors: Lin Xiao Stephen Boyd
references.title: Fast linear iterations for distributed averaging
references.venue: Systems & Control Letters,
references.authors: Yang You Zhao Zhang Cho-Jui Hsieh James Demmel Kurt Keutzer
references.title: Imagenet training in minutes
references.venue: In Proceedings of the 47th International Conference on Parallel Processing,
references.authors: Kun Yuan Qing Ling Wotao Yin
references.title: On the convergence of decentralized gradient descent
references.venue: SIAM Journal on Optimization,
references.authors: Koloskova
references.title: 2020b), Descent lemma for non-convex case). Under the given assumptions, and for any stepsize γ
references.authors: Santurkar
references.title: The estimation procedure
sections.heading: 1 INTRODUCTION
sections.text: Highly over-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 to 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., 2018; Shallue et al., 2018). These SOTA training systems in 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 on preserving users’ privacy for edge AI (Bellet et al., 2018; Kairouz et al., 2019).
  Several very recent papers aim to address the communication overhead in data-center training by compressing the gradients (Koloskova et al., 2020a; Vogels et al., 2020) or designing better a communication topology (Assran et al., 2019). However, decentralized training for deep learning models still often results in a severe loss in generalization performance, even after hyper-parameter fine-tuning (see our Table 1 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.e. the data-center case), to which very few works are dedicated (but none of them provide insights into the generalization gap).
  In this work, we theoretically identify the consensus distance, i.e. the average discrepancy between the nodes, as the key parameter that captures the joint effect of decentralization. We show that there exists a 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,
  we 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, as 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 generalization 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 training, in order to ensure high generalization 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 machine 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 in later training phases after optimization has plateaued, leading to improved generalization, which is consistent with the observations in centralized Post-Local SGD (Lin et al., 2020b).
  • Based on our findings, we 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.
sections.heading: 2 RELATED WORK
sections.text: Gossip averaging (Kempe et al., 2003; Xiao & Boyd, 2004; Boyd 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 al. (2017) combine SGD with gossip averaging for deep learning and show that the leading term in the convergence rate O ( 1 nε2 ) 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., 2017; 2018; Koloskova et 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 et al., 2019; Wang et al., 2019; Nadiradze et 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); Nedić & Ozdaglar (2009); Duchi et al. (2012); Yuan et al. (2016) 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.
sections.heading: 3 THEORETICAL UNDERSTANDING
sections.text: In this section we consider decentralized training with stochastic gradient descent (D-SGD) without momentum, but we are using the momentum version in all our DL experiments.
sections.heading: 3.1 NOTATION AND SETTING
sections.text: The agents are tasked to solve a sum-structured optimization problem f : Rd → R of the form f? := minx∈Rd [ f(x) := 1n ∑n i=1 fi(x) ] , (1)
  where the components fi : Rd → R are distributed among the n nodes and are given in stochastic form: fi(x) := Eξ∼Di [Fi(x, ξ)], where Di denotes the local data distribution on node i ∈ [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 ∈ [n] maintains local parameters x(t)i ∈ Rd, and updates them as:
  x (t+1) i = ∑n j=1 wij ( x (t) j − η∇Fj(x (t) j , ξ (t) j ) ) , (D-SGD)
  that is, by a stochastic gradient step based on a sample ξ(i)i ∼ Di, followed by gossip averaging with neighboring nodes in the network encoded by the mixing weightswij . As parameters can differ across nodes, we define x̄ := 1n ∑n i=1 xi and X := [x1, . . . ,xn] ∈ Rd×n, and X̄ := [x̄, . . . , x̄] ≡ X 1 n11
  >. Assumption 1 (Mixing matrix). Every sample of the (possibly randomized) mixing matrix W = {wij} ∈ Rn×n is doubly stochastic and there exists a parameter p > 0 such that
  EW ∥∥XW − X̄∥∥2
  F ≤ (1− p) ∥∥X− X̄∥∥2 F ,∀X ∈ Rd×n. (2)
  This assumption covers a broad variety of settings (see e.g. Koloskova et al., 2020b), such as D-SGD with fixed (constant) mixing matrix with spectral gap ρ, with parameter p = 1− (1− ρ)2 = Θ(ρ), but also for randomly chosen mixing matrices, for instance random matchings. Assumption 2 (L-smoothness). Each function fi(x) : Rd → R, i ∈ [n] is differentiable and there exists a constant L ≥ 0 such that for each x,y ∈ Rd: ‖∇fi(y)−∇fi(x)‖ ≤ L ‖x− y‖ . Assumption 3 (Bounded noise σ and diversity ζ). There exists constants σ2, ζ2 s.t. ∀x1, . . .xn ∈ Rd
  1 n ∑n i=1 Eξi ‖∇Fi(xi, ξi)−∇fi(xi)‖ 2 2 ≤ σ2 ,
  1 n ∑n i=1 ‖∇fi(xi)−∇f(xi)‖ 2 2 ≤ ζ2 . (3)
sections.heading: 3.2 DECENTRALIZED CONSENSUS OPTIMIZATION
sections.text: Under the above assumptions, which are standard in decentralized optimization, the convergence rate of (D-SGD) has been shown to be: Theorem 1 (Koloskova et al. (2020b)). Let fi be L-smooth and stepsize γ ≤ γmax = O ( p L ) . Then
  there exists an optimal stepsize γ ≤ γmax such that 1T ∑T−1 t=0 E ∥∥∇f(x̄(t))∥∥2 2 ≤ ε for
  T = O ( σ2
  nε2 +
  √ pσ + ζ
  pε3/2 + p ε
  ) · L(f(x0)− f?) .
  In comparison, for centralized mini-batch SGD (C-SGD) we are allowed to choose a potentially much larger stepsize γ ≤ O ( 1 L ) , and can bound the number of iterations by O ( σ2 nε2 + 1 ε ) . While asymptotically both these rates are 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.
  To measure differences between agents, we use the consensus distance Ξ2t := 1 n ∑n i=1 ∥∥x̄(t)−x(t)i ∥∥2. Remark 2 (Critical Consensus Distance (CCD)). If the consensus distance is bounded by
  Ξ2t ≤ ( 1
  Ln γσ2 +
  1
  8L2 ∥∥∥∇f(x̄(t))∥∥∥2 =: Γ2t) (4) for all t, then in D-SGD we may choose larger stepsizes γ ≤ γ′max = O ( 1 L ) and recover the
  convergence rate of C-SGD, that is O ( σ2
  nε2 + 1 ε
  ) (Dekel et al., 2012; Bottou et al., 2018). We denote
  Γ2t as critical consensus distance (CCD).
  The proof can be found in the Appendix A.1. Note that the CCD does not depend on the graph topology and that Γ2t > 0, which means that we do not need perfect consensus between agents to recover the C-SGD rate, but we allow consensus distance Ξ2t ≥ 0 (i.e. the Ξ2t = 0 ∀t, as we 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.
  Proposition 3 (Typical consensus distance). Let φ2t := 1n ∑n i=1 ∥∥∇fi(x(t)i )∥∥2. Then under the assumption that γ, p are constant, and the φt do not change too fast between iterations, i.e. not decreasing faster than exponentially: φ2t ≤ (1+p/4)φ2t+1, the consensus distance in D-SGD satisfies
  Ξ2t = (1− p)γ2 · O ( φ2t p2 + σ2 p ) . (5)
  We give the proof in the Appendix A.2. While these assumptions do not hold in epochs with learning rate decay, we observed in practice that when the learning rate is constant indeed the gradients do not change too fast and found it to be a reasonable approximation to capture the practical behavior (see Figure 5(b)).
sections.heading: 3.3 CONTROLLING THE CONSENSUS DISTANCE
sections.text: In this section we investigate scenarios where the typical consensus distance derived in Proposition 3 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 γ ≤ O ( 1 L ) as for C-SGD, and give a more refined discussion in the appendix.
  Learning rate decay (changing γ). We observe that when γ = O ( p nL ) then Ξ2t ≤ Γ2t (if the
  noise σ is small, especially for σ = 0, then the weaker assumption γ = O ( p L ) is sufficient). However, choosing the stepsize too small can impact performance in practice. In C-SGD the constraint on the stepsize is loose (γ ≤ 1L ). Yet, our observations show that after sufficient learning rate decay, the desired CCD can be reached.
  More gossip iterations (changing p). We observe that when 11−p = O(1 + γLn), then Ξ 2 t ≤ Γ2t (again, when the noise σ is small, especially when σ2 = 0, a weaker condition 11−p = O(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 used strategy is to use repeated gossip steps in every round.
  Lemma 4 (Repeated gossip). Suppose W = Wk . . .W1, for k (possibly randomized) mixing matrices with parameter p each. Then the mixing parameter for W is at least pW ≥ 1− (1− p)k.
  From this, we see that the mixing parameter can be improved exponentially when applying more gossip steps. To ensure pW ≥ 1− 11+γLn , at most k ≤ ln(1+γLn) p = Õ ( 1 p ) repetitions are required.
  These arguments show, that we can—at least in theory—recover 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.
sections.heading: 4 INSPECTING CONSENSUS DISTANCE FOR DECENTRALIZED TRAINING
sections.text: 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; a preliminary study on Transformer with Adam optimizer and inverse square root learning rate schedule can be found in Section 4.4.
sections.heading: 4.1 EXPERIMENT DESIGN: CONTROLLED DECENTRALIZED TRAINING PHASES.
sections.text: 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 2 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 as described in Section 4.2: thus the training can be naturally divided into phases with the corresponding learning rate, in each of which key training dynamics are significantly different from the others, such as Ξt (Figure 1), φt (Figure 5(b)) and L-smoothness (Figure 5(c)). The transformer
  (NLP task) has no well-defined training phases due to 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)1 on model parameters for the other unstudied phases. For the ease of presentation, the term “phase-x” refers to a training phase between x−1-th and x-th learning rate decay. The notation “dec-phase-x” indicates that only in “phase-x” the model is trained with a decentralized communication topology, while for other phases we 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), so as to identify when (which phase) and how decentralized training influences final generalization performance2.
sections.heading: 4.2 EXPERIMENTAL SETUP
sections.text: Datasets and models. We empirically study the decentralized training behavior on the following two tasks, on CNN and transformer architectures: (1) Image Classification for CIFAR-10 (Krizhevsky & Hinton, 2009) and ImageNet-32 (i.e. image resolution of 32) (Chrabaszcz et al., 2017), with the standard data augmentation and preprocessing scheme (He et al., 2016); 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 2× w.r.t. the base model in Vaswani et al. (2017)) is used. Weight initialization schemes follow Goyal et al. (2017); He et al. (2015) and Vaswani et al. (2017) respectively. Unless mentioned otherwise, our experiments are repeated over three random seeds.
  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 (lr) for centralized training3 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 a 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 { 12 , 3 4} and
  { 13 , 2 3 , 8 9} for CIFAR and ImageNet respectively. All results in 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 to 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, we 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 approach4): the target consensus distance Ξ for a phase is the maximum consensus distance Ξmax of the current phase in normal (uncontrolled) decentralized training, multiplied by a factor. For a given topology, the smaller the factor, the tighter consensus.
  1 All-Reduce is used for all nodes to reach an exact consensus on model parameters. 2 We demonstrate in Table 4 of Section 4.3 that the 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 not change the conclusion. E.g., no significant difference can be found for the curves at phase-1 for “ring (fine-tuned lr)” and “dec-phase-1 (Ξmax)” in Figure 2(a) and 2(b). We have similar observations in Table 11 after the sufficient learning rate tuning on phase-1.
  4 We use this one primarily since we can regulate the consensus distance in absolute values. We abuse the notation a bit by using Ξmax alone to indicate the decentralized training w/o consensus distance control.
  • adaptive consensus distance (in Appendix C.3.1): the target consensus distance Ξ for the current step is the averaged local gradient norm φavgt scaled by a factor. For stability, we use the exponentially moving averaged value φemat of φ avg t (accumulated during the corresponding phase).
  We use a ring as our (main) decentralized communication topology5 as it is a particular hard instance with large spectral gap (cf. Table 7), allowing to study a wide range of target consensus distances by modifying the number of communication rounds.
sections.heading: 4.3 FINDINGS ON COMPUTER VISION TASKS
sections.text: In this section we present our empirical findings and provide insights into how consensus distance at different phases impacts the training generalization for CV tasks (i.e. CIFAR-10, Imagenet-32).
  Critical consensus distance exists in the initial training phase and ensures good optimization and generalization. In the initial training phase, both training and generalization performance are heavily influenced by the consensus distance6 (“dec-phase-1” in Figure 2 and Table 2). A smaller 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 Ξmax for CIFAR-10), although the optimization (training performance) can eventually catch up with the centralized convergence (c.f. Figure 2(a) and 2(b)), a considerable generalization gap still remains (92.36 v.s. 92.82 for the setup in Figure 2) as shown in Table 2. This pattern is consistent7 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 Jastrzebski et al. (2020); Frankle et al. (2020); Golatkar et al. (2019) for traditional (centralized) training, where it 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 Ξmax is sufficient in CIFAR-10 experiments to approach the optimal centralized training performance in both optimization and generalization at the end. Smaller distances (e.g. 1/8 Ξmax, 1/16 Ξmax) do not bring significant gain (92.77 and 92.72 respectively in Table 9). The performance saturates (c.f. 92.74 for 1/4 Ξmax) with significantly increased communication overhead (e.g. Figure 9 of Appendix C.1). 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 Table 17 and 16. The observations are 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. 7 In the case of ImageNet-32 with n=32, 1/2 Ξmax has already been tight enough to recover the centralized
  training performance. But a significant performance drop can be observed between Ξmax and 1/2 Ξmax.
  sensible in the initial training phase: there exists a critical consensus distance for the training, beyond which the impact of decentralization is negligible.
  A non-negligible consensus distance at middle phases can improve generalization over centralized training. Surprisingly, it is not always the case that the generalization performance improves with the shrinking consensus distance. We observe that at the phase right after initial training plateaus (e.g. phase-2 for CIFAR-10, phase-3 for Imagenet-32), a non-negligible consensus distance8 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 monotonically 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 n = 32). Analogous observation can be obtained in Imagenet-32 dec-phase-3 experiments (Table 3).
  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.
sections.heading: At the last phase of training, the consensus degree marginally impacts the generalization.
sections.text: Similar to the initial training phase, the final convergence phase seems to favor small consensus 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 Ξmax) is only 0.25% and 0.37% higher than that of Ξmax for n= 32, 64 respectively (Table 2). In Imagenet-32 experiments, dec-phase-3 performance is 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 4, we control the consensus distance for both phase-1 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 Ξmax,1/4 Ξmax consensus control to phase-2 (middle column in Table 4), we can still observe that a smaller consensus distance in phase-1 results in a higher performance as in our previous finding. Hence our previous findings are valid in more general cases of decentralized training.
  8 In Table 17 and 16 in Appendix C.3.1, we show that there exists optimal consensus distance at middle phases, beyond which the gain in generalization (brought by noise injection) starts to diminish.
  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 to the optimization difficulty. Table 5 investigates whether a prolonged training on the initial phase can address this difficulty: we prolong the phase-1 for CIFAR-10 with a 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 Ξmax, which is lower than the average gain (around 0.6%) of merely reducing the consensus distance from Ξmax to 1/2 Ξmax. Table 13 evaluates cases where 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 (generalization/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 Section 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 a consensus distance lower than the CCD. A list of communication topologies with superior spectral properties, e.g. exponential graph (Assran et al., 2019) and random matching (Nadiradze et al., 2020), can be utilized9 to achieve fast convergence in gossip averaging.
  The late training phases should be less prioritized for communication resources, due to the generalization benefits from a reasonable consensus distance in the middle phases. Providing a rigorous way to quantify the optimal consensus distance is non-trivial, and we leave it as future work.
  In Table 6 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 Ξmax 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 to the performance. Table 16 in Appendix C.3.1 additionally justifies the applicability of applying this guideline on exponential graph, and we leave more complicated communication scheme design as future work.
sections.heading: 4.4 PRELIMINARY STUDY ON TRAINING TRANSFORMER MODELS
sections.text: The critical consensus distance also exists in NLP tasks. Figure 4(c) demonstrates that 1/4 Ξmax 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 4(a) and 4(b)). These justify the importance of designing an efficient communication topology/scheme in practice so as to effectively reach the critical consensus distance.
  9 The definition of the communication topology is detailed in Appendix C.1.
sections.heading: A THEORY
sections.text: In this section, we prove the claims from Section 3.
sections.heading: A.1 PROOF OF REMARK 2, CRITICAL CONSENSUS DISTANCE
sections.text: 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 assumptions, and for any stepsize γ < 14L , the iterates of D-SGD satisfy
  Et+1 f(x̄(t+1)) ≤ f(x̄(t))− η
  4 ∥∥∥∇f(x̄(t))∥∥∥2 2 + γΞ2t + L n γ2σ̂2.
  Proof. By replacing Ξt in the above inequality with (4), we simplify:
  Et+1 f(x̄(t+1)) ≤ f(x̄(t))− η
  8 ∥∥∥∇f(x̄(t))∥∥∥2 2 + 2L n γ2σ̂2.
  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 et al., 2018; Stich & Karimireddy, 2019).
sections.heading: A.2 PROOF OF PROPOSITION 3, TYPICAL CONSENSUS DISTANCE
sections.text: We need an auxiliary (but standard) lemma, to estimate the change of the consensus distance between iterations.
  Lemma 6 (Consensus distance). It holds
  Ξ2t+1 ≤ (1− p/2)Ξ2t + 3(1− p)γ2
  p
  ( φ2t + pσ 2 ) .
  We give the proof of this statement shortly below. First, let us consider how this lemma allows the proof of the claim. For this, we first consider a particular special case, and assume φt ≤ φ, for a constant φ. In this case, we can easily verify by unrolling the recursion:
  Ξ2t ≤ t−1∑ i=0 (1− p/2)i 3(1− p)γ 2(φ2 + pσ2) p ≤ 6(1− p)γ2 ( φ2 p2 + σ2 p ) .
  Now, for the claim in the main text, we use assumption that φt are changing slowly, that is, not decreasing faster than exponentially: φ2t ≤ (1 + p/4)φ2t+1. With this assumption, and observing (1− p/2)i(1 + p/4)i ≤ (1− p/4)i, we can unroll as before
  Ξ2t ≤ t−1∑ i=0 (1− p/2)i 3(1− p)γ2(φ2t−i−1 + pσ2) p
  ≤ t−1∑ i=0 (1− p/4)i 3(1− p)γ2(φ2t−1 + pσ2) p ≤ 12(1− p)γ2 ( φ2t−1 p2 + σ2 p ) .
  Proof of Lemma 6. We use the following matrix notation here X(t) := [ x (t) 1 , . . . ,x (t) n ] ∈ Rd×n ,
  X̄(t) := [ x̄(t), . . . , x̄(t) ] = X(t) 1
  n 11> , ∇F (X(t), ξ(t)) := [ ∇F1(x(t)1 , ξ (t) 1 ), . . . ,∇Fn(x(t)n , ξ(t)n ) ] ,
  ∇f(X(t)) := [ ∇f1(x(t)1 ), . . . ,∇fn(x(t)n ) ] .
  As a reminder, Ξ2t := 1 n ∑n i=1 ∥∥∥x̄(t) − x(t)i ∥∥∥2, and φ2t := 1n∑ni=1 ∥∥∥∇fi(x(t)i )∥∥∥2. nΞ2t+1 = ∥∥∥X̄(t+1) −X(t+1)∥∥∥2 F = ∥∥∥∥(X(t) − γ∇F (X(t), ξ(t)))( 1n11> −W )∥∥∥∥2
  F
  = ∥∥∥∥(X(t) − γ∇F (X(t), ξ(t)))( 1n11> − I )( 1 n 11> −W )∥∥∥∥2 F
  ≤ (1− p) ∥∥∥∥(X(t) − γ∇F (X(t), ξ(t)))( 1n11> − I )∥∥∥∥2 F
  ≤ (1− p) ∥∥∥∥(X(t) − γ∇f(X(t)))( 1n11> − I )∥∥∥∥2 F + (1− p)γ2 ∥∥∥∇f(X(t))−∇F (X(t), ξ(t))∥∥∥2 F
  ≤ (1− p)(1 + α) ∥∥∥∥X(t)( 1n11> − I )∥∥∥∥2 F + (1− p)(1 + α−1)γ2 ∥∥∥∇f(X(t))∥∥∥2 F + (1− p)γ2σ2n
  α= p2 ≤ (
  1− p 2
  ) nΞ2t +
  3(1− p) p
  γ2 ∥∥∥∇f(X(t))∥∥∥2
  F + (1− p)γ2σ2n
sections.heading: A.3 SUFFICIENT BOUNDS TO MEET CRITICAL CONSENSUS DISTANCE
sections.text: In this section, we show that the claimed bounds in Section 3.3 are sufficient conditions to reach the CCD.
  According to Remark 3, there exists an absolute constant C, (w.l.o.g. C ≥ 2) such that Ξ2t ≤ C(1− p)γ2 ( φ2t p2 + σ2 p ) By smoothness,
  φ2t = 1
  n n∑ i=1 ∥∥∥∇fi(x(t)i )∥∥∥2 ≤ 3 n n∑ i=1 ∥∥∥∇fi(x(t)i )−∇f(x(t)i )∥∥∥2 + 3n n∑ i=1 ∥∥∥∇f(x(t)i )−∇f(x̄(t))∥∥∥2 + 3n n∑ i=1
  ∥∥∥∇f(x̄(t))∥∥∥2 ≤ 3ζ2 + 3L2Ξ2t + 3
  ∥∥∥∇f(x̄(t))∥∥∥2 . Supposing (1− p)γ2 ≤ p 2
  6CL2 , we can therefore estimate Ξ2t ≤ C(1− p)γ2 ( 3 ∥∥∇f(x̄(t))∥∥2 + 3L2Ξ2t + 3ζ2
  p2 + σ2 p
  )
  ≤ 3C(1− p)γ2 (∥∥∇f(x̄(t))∥∥2 + ζ2
  p2 + σ2 p
  ) + 1
  2 Ξ2t
  and hence
  Ξ2t ≤ 6C(1− p)γ2 (∥∥∇f(x̄(t))∥∥2
  p2 + ζ2 p2 + σ2 p
  ) (6)
  The claimed bounds can now easily be 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 γ. By choosing γ ≤ p4nLC , we check that our previous constraint γ 2 C≥2 ≤ p 2
  6CL2 is satisfied, and
  (6) ≤ ∥∥∇f(x̄(t))∥∥2
  4n2CL2 + γσ2 nL C≥2 ≤ (4)
  Small p. By choosing 1 − p ≤ 15C(1+γLn) , we note that p C≥2 ≥ 910 . Moreover, our previous constraint (1− p)γ2 ≤ γ 2
  5C ≤ p2 6L2C is satisfied (note that γ ≤ 1 4L throughout). Hence
  (6) ≤ 4γ 2
  5(1 + γLn)
  ( 100 ∥∥∇f(x̄(t))∥∥2 81 + 10σ2 9 ) γ≤1/(4L) ≤ (4)
  In the above calculations we for the simplicity assumed that ζ = 0. 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.
sections.heading: A.4 PROOF OF LEMMA 4, REPEATED GOSSIP
sections.text: By the assumption stated in the lemma, it holds for each component Wi of the product W = Wk . . .W1, i ∈ [1, k] that
  EWi ∥∥XWi − X̄∥∥2F ≤ (1− p)∥∥X− X̄∥∥2F ,∀X ∈ Rd×n.
  Now lets estimate the parameter pW. Using that Wi are independent EW ∥∥XW − X̄∥∥2
  F = EW1...Wk ∥∥XWk . . .W1 − X̄∥∥2F = =EW2...WkEW1
  ∥∥YW1 − Ȳ∥∥2F , where we defined Y = XWk . . .W2 and used that Wi 1n11 > = 1n11 >, so
  Ȳ = XWk . . .W2 1
  n 11> = X
  1 n 11> = X̄.
  Therefore,
  EW ∥∥XW − X̄∥∥2
  F ≤ (1− p)EW2...Wk ∥∥XWk . . .W2 − X̄∥∥2F . Applying the same calculations to the rest, we conclude that 1− pW = (1− p)k.
sections.heading: B DETAILED EXPERIMENTAL SETUP
sections.text: Comments on large-batch training. Coupling the quality loss issue of the decentralized training with the large-batch training difficulty is non-trivial and is 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), to avoid the difficulty of extreme large-batch training.
  Multi-phase experiment justification. The averaged local gradient norm φt as well as the Lsmoothness of ResNet-20 on CIFAR-10 for a ring and a complete graph (n = 32) are shown in Figure 5 and Figure 6 respectively.
  The estimation procedure is analogous to that in Santurkar et al. (2018); Lin et al. (2020a): we take 8 additional steps long the direction of current update, each with 0.2 of normal step size. This is calculated at every 8 training steps. The smoothness is evaluated as the maximum value of L satisfying Assumption 2.
  0 50 100 150 200 250 300 Epoch
  0
  5
  10
  15
  t
  (a) The consensus distance for decentralized training.
  0 50 100 150 200 250 300 Epoch
  0.5
  1.0
  1.5
  2.0
  2.5
  3.0
  3.5
  t
  (b) The averaged norm of the local gradients for decentralized training.
  0 50 100 150 200 250 300 Epoch
  0
  10
  20
  30
  Lsm
  oo th
  ne ss
  (c) The gradient Lipschitz curve for both decentralized training.
  (a) The averaged norm of the local gradients for centralized training.
  (b) The gradient Lipschitz curve for both centralized training.
  Figure 6: Justification for our multiple-phase experimental design choice (on complete graph). We run ResNet-20 on CIFAR-10 (n=32) with the complete topology. We can again observe the three quantities most relevant to optimization all naturally form three phases, dictated by the learning rate schedule.
sections.heading: C ADDITIONAL RESULTS
sections.heading: C.1 UNDERSTANDING ON CONSENSUS AVERAGING PROBLEM
sections.text: We study a host of communication topologies: (1) deterministic topologies (ring, and complete graph) and (2) undirected time-varying 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 0 to n− 1. Each node i periodically communicates with a list nodes with rank i+ 20, i+ 21, . . . , i+ 2blog2(n−1)c. In the one-peer-per-node experiments, each node only communicates to one node by cycling through its list. The formed graph is undirected, i.e., both transmission and reception take place in each communication.
  • Bipartite exponential graph (Lian et al., 2018; Assran et al., 2019). In order to avert deadlocks (Lian et al., 2018), the node with an odd rank i cycles through nodes with even ranks i + 20 − 1, i + 21 − 1, . . . , i + 2blog2(n−1)c − 1 by transmitting a message and waiting for a response. while the nodes with even ranks only await messages and reply upon reception.
  Table 7 displays the spectral gap and node degree of studied topologies, and Figure 7 provides the convergence curves for different communication topologies on graph scales. Figure 8 in addition visualizes the spectral gap (in expectation) for different communication topologies.
  Table 8 examines these topologies on a standard deep learning benchmark with different graph scales, while Figure 9 visualizes the required communication rounds (per gradient update step) for a range of consensus distance targets.
sections.heading: C.2 UNDERSTANDING THE DECENTRALIZED DEEP LEARNING TRAINING FOR CV TASKS
sections.text: We use ring as our underlying decentralized communication topology in this subsection.
  Elaborated results on consensus distance control. Table 9 is the elaborated version of Table 2 with more evaluated consensus distances.
  SlowMo cannot fully address the decentralized optimization/generalization difficulty. Table 10 studies the effectiveness of using SlowMo for better decentralized training. We can witness that even though the performance of decentralized training can be boosted to some extent, it cannot fully address the quality loss issue brought by decentralized training.
  On the ineffectiveness of tuning learning rate. Table 11 displays the results of training ResNet20 on CIFAR-10 (32 nodes), with fine-tuned learning rate on phase-1; learning rate tuning cannot address the test quality loss issue caused by the large consensus distance (i.e. over the CCD).
  Distance control on SGD without momentum. Table 12 contains the consensus distance control results for SGD without momentum. We can observe a consistent pattern as in Table 2.
  Prolonged training for dec-phase-2 and dec-phase-3. Table 13 shows the results for prolonged dec-phase-2 and dec-phase-3 on CIFAR-10 with ResNet20. We can observe although longer training duration increases the performance, the improvement is rather small.
  The impact of half cosine learning rate schedule. Table 14 examines the existence of the critical consensus distance with half cosine learning schedule (this scheme is visited in He et al. (2019) as a new paradigm for CNN training). We can witness from Table 14 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 of Table 14) and ensures good optimization and generalization.
sections.heading: C.2.1 ADAPTIVE CONSENSUS DISTANCE CONTROL
sections.text: 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.
sections.heading: C.3 CONSENSUS CONTROL WITH OTHER TOPOLOGIES
sections.text: In Table 16, we exert consensus control with an exponential graph as the base communication topology. We can observe that our findings from main experiments with a ring base topology are valid.
sections.heading: C.3.1 THE EXISTENCE OF THE OPTIMAL CONSENSUS DISTANCE FOR NOISE INJECTION.
sections.text: Table 17 uses a different communication topology (i.e. time-varying exponential graph) for decentralized optimization. Here exponential graph with large spectral gap is applied to CIFAR-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 2 and drops at local update 4. It points out that an optimal consensus distance is required to inject proper stochastic noise for better generalization.
sections.heading: C.4 RESULTS FOR TRAINING TRANSFORMER ON MULTI30K
sections.text: 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., 2016). Figure 10 shows that the straightforward application of Adam in 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).
  0 10 20 30 40 50 60 Epoch
  1.5
  2.0
  2.5
  3.0
  3.5
  4.0
  Va lid
  at io
  n lo
  ss
  All-Reduce Decentralized (complete) Decentralized (ring) Decentralized (exponential graph)
  (a) The limitation of decentralized learning with Adam, caused by the different local moment buffers.
  0 10 20 30 40 50 60 Epoch
  1.5
  2.0
  2.5
  3.0
  3.5
  4.0
  Va lid
  at io
  n lo
  ss
  Decentralized (warmup step = 125) Decentralized (warmup step = 250) Decentralized (warmup step = 500) Decentralized (warmup step = 1000)
  (b) Tuning the learning rate cannot alleviate the issue of decentralized Adam.
  Figure 10: Learning curves for training the transformer model on the Multi30k dataset (n = 32). In Figure 10(b), we tune the the number of warmup steps as as way of tuning the learning rate, as the learning rate used in transformer training (Vaswani et al., 2017) is deterministically controlled by the model’s dimensionality, the current step index, and the number of warmup steps.