summaries: The paper introduces a non-parametric approach, STAM, for unsupervised progressive learning (UPL), a variant of continual unsupervised learning with a single-stream requirement. STAM is developed for visual tasks. It comprises several components: (1) online clustering of hierarchical visual features (2) novelty detection (3) dual-memory for prototypical features. Experiments show STAM performs better than GEM, MAS in specific scenarios.

summaries: The authors propose an approach (architecture + algorithms) to unsupervised progressive learning in a non-stationary environment (the number of classes grows gradually) by keeping centroids at several hierarchies, using a combination of techniques from online clustering, via computing and updating centroids, with novelty detection, and dropping (forgetting those deemed outliers).  A variety of experiments are performed on several image datasets (MNIST, EMNIST, SVHN, CIFAR-10) with comparisons to other adapted methods. They evaluate performance in a supervised setting where they describe how they learn centroid to label(s) mappings.

summaries: This paper presents an "Unsupervised progressive learning" (UPL) problem, where a model is exposed to data in an non-iid manner, and each training example is presented once. Simple to continual learning, but a little more explicit in the connections to the way biological agents learn. They present a model that uses clustering and long-term memory (buffered) and compare on a few UPL tasks with additional supervision signal (classification) or unsupervised (clustering).

abstractText: We first pose the Unsupervised Progressive Learning (UPL) problem: learning salient representations from a non-stationary stream of unlabeled data in which the number of object classes increases with time. If some limited labeled data is also available, those representations can be associated with specific classes, thus enabling classification tasks. To solve the UPL problem, we propose an architecture that involves an online clustering module, called Self-Taught Associative Memory (STAM). Layered hierarchies of STAM modules learn based on a combination of online clustering, novelty detection, forgetting outliers, and storing only prototypical representations rather than specific examples. The goal of this paper is to introduce the UPL problem, describe the STAM architecture, and evaluate the latter in the UPL context.

authors:
F. Gregory Ashby
W. Todd Maddox

title: Human category learning

venue: Annu. Rev. Psychol.,

authors:
Yoshua Bengio
Aaron Courville
Pascal Vincent

title: Representation learning: A review and new perspectives

venue: IEEE Trans. Pattern Anal. Mach. Intell.,

authors:
Kevin S. Beyer
Jonathan Goldstein
Raghu Ramakrishnan
Uri Shaft

title: When is ”nearest neighbor

venue: Proceedings of the 7th International Conference on Database Theory, ICDT

authors:
Mathilde Caron
Piotr Bojanowski
Armand Joulin
Matthijs Douze

title: Deep clustering for unsupervised learning of visual features

venue: In The European Conference on Computer Vision (ECCV),

authors:
Adam Coates
Andrew Y Ng

title: Learning feature representations with k-means, pages 561–580

authors:
Adam Coates
Andrew Ng
Honglak Lee

title: An analysis of single-layer networks in unsupervised feature learning

venue: In Proceedings of the fourteenth international conference on artificial intelligence and statistics,

authors:
Gregory Cohen
Saeed Afshar
Jonathan Tapson
André van Schaik

title: Emnist: an extension of mnist to handwritten letters

venue: ArXiv,

authors:
Yuwei Cui
Subutai Ahmad
Jeff Hawkins

title: Continuous online sequence learning with an unsupervised neural network model

venue: Neural Comput.,

authors:
S.M. Ali Eslami
Nicolas Heess
Theophane Weber
Yuval Tassa
David Szepesvari
Koray Kavukcuoglu
Geoffrey E. Hinton

title: Attend, infer, repeat: Fast scene understanding with generative models

venue: In Proceedings of the 30th International Conference on Neural Information Processing Systems,

authors:
Li Fei-Fei
R. Fergus
P. Perona

title: One-shot learning of object categories

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Chelsea Finn
Pieter Abbeel
Sergey Levine

title: Model-agnostic meta-learning for fast adaptation of deep networks

venue: In Proceedings of the 34th International Conference on Machine Learning Volume 70,

authors:
R. Geirhos
P. Rubisch
C. Michaelis
M. Bethge
F.A. Wichmann
W. Brendel

title: Imagenettrained cnns are biased towards texture; increasing shape bias improves accuracy and robustness

venue: International Conference on Learning Representations (ICLR),

authors:
Alexander Gepperth
Cem Karaoguz

title: Incremental learning with self-organizing maps

venue: Visualization (WSOM),

title: Perceptual learning

venue: Annual review of psychology,

authors:
Alexander Hinneburg
Charu C. Aggarwal
Daniel A. Keim

title: What is the nearest neighbor in high dimensional spaces

venue: In Proceedings of the 26th International Conference on Very Large Data Bases,

authors:
Devon Hjelm
Alex Fedorov
Samuel Lavoie-Marchildon
Karan Grewal
Phil Bachman
Adam Trischler
Yoshua Bengio

title: Learning deep representations by mutual information estimation and maximization

venue: In ICLR 2019

authors:
Yen-Chang Hsu
Yen-Cheng Liu
Anita Ramasamy
Zsolt Kira

title: Re-evaluating continual learning scenarios: A categorization and case for strong baselines

venue: In NeurIPS Continual learning Workshop,

authors:
Gabriel Huang
Hugo Larochelle
Simon Lacoste-Julien

title: Centroid networks for few-shot clustering and unsupervised few-shot classification

authors:
X. Ji
J. Henriques
A. Vedaldi

title: Invariant infromation clustering for unsupervised image classification and segmentation

venue: In Proceedings of the International Conference on Computer Vision (ICCV),

authors:
Zhuxi Jiang
Yin Zheng
Huachun Tan
Bangsheng Tang
Hanning Zhou

title: Variational deep embedding: An unsupervised and generative approach to clustering

venue: In Proceedings of the 26th International Joint Conference on Artificial Intelligence,

authors:
Ronald Kemker
Marc McClure
Angelina Abitino
Tyler Hayes
Christopher Kanan

title: Measuring catastrophic forgetting in neural networks

venue: AAAI Conference on Artificial Intelligence,

authors:
Diederik P. Kingma
Jimmy Ba

title: Adam: A method for stochastic optimization, 2014. cite arxiv:1412.6980Comment: Published as a conference paper at the 3rd International Conference for Learning Representations

venue: San Diego,

authors:
Diederik P. Kingma
Danilo J. Rezende
Shakir Mohamed
Max Welling

title: Semi-supervised learning with deep generative models

venue: In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2,

authors:
Adam Kosiorek
Hyunjik Kim
Yee Whye Teh
Ingmar Posner

title: Sequential attend, infer, repeat: Generative modelling of moving objects

venue: Advances in Neural Information Processing Systems

authors:
Dharshan Kumaran
Demis Hassabis
James L McClelland

title: What learning systems do intelligent agents need? complementary learning systems theory updated

venue: Trends in cognitive sciences,

authors:
Y. Lecun
L. Bottou
Y. Bengio
P. Haffner

title: Gradient-based learning applied to document recognition

authors:
David Lopez-Paz
Marc’Aurelio Ranzato

title: Gradient episodic memory for continual learning

venue: In Proceedings of the 31st International Conference on Neural Information Processing Systems,

authors:
Takeru Miyato
Shin-ichi Maeda
Shin Ishii
Masanori Koyama

title: Virtual adversarial training: a regularization method for supervised and semi-supervised learning

venue: IEEE transactions on pattern analysis and machine intelligence,

authors:
Yuval Netzer
Tao Wang
Adam Coates
Alessandro Bissacco
Bo Wu
Andrew Y. Ng

title: Reading digits in natural images with unsupervised feature learning

venue: In NIPS Workshop on Deep Learning and Unsupervised Feature Learning

authors:
Avital Oliver
Augustus Odena
Colin Raffel
Ekin D. Cubuk
Ian J. Goodfellow

title: Realistic evaluation of deep semi-supervised learning algorithms

authors:
German I. Parisi
Ronald Kemker
Jose L. Part
Christopher Kanan
Stefan Wermter

title: Continual lifelong learning with neural networks: A review

venue: Neural Networks,

authors:
Cengiz Pehlevan
Alexander Genkin
Dmitri B Chklovskii

title: A clustering neural network model of insect olfaction

venue: 51st Asilomar Conference on Signals, Systems, and Computers,

authors:
Sylvestre-Alvise Rebuffi
Alexander Kolesnikov
Georg Sperl
Christoph H. Lampert

title: icarl: Incremental classifier and representation learning

venue: IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Mengye Ren
Eleni Triantafillou
Sachin Ravi
Jake Snell
Kevin Swersky
Joshua B. Tenenbaum
Hugo Larochelle
Richard S. Zemel

venue: In Proceedings of 6th International Conference on Learning Representations ICLR,

authors:
Andrei A. Rusu
Neil C. Rabinowitz
Guillaume Desjardins
Hubert Soyer
James Kirkpatrick
Koray Kavukcuoglu
Razvan Pascanu
Raia Hadsell

title: Progressive neural networks, 2016

authors:
Hanul Shin
Jung Kwon Lee
Jaehong Kim
Jiwon Kim

title: Continual learning with deep generative replay

authors:
Jake Snell
Kevin Swersky
Richard S. Zemel

title: Unsupervised and semi-supervised learning with categorical generative adversarial networks

authors:
Gido M. van de Ven
Andreas S. Tolias

title: Three scenarios for continual learning

authors:
Rajasekar Venkatesan
Meng Joo Er

title: A novel progressive learning technique for multi-class classification

authors:
Takeo Watanabe
José E Náñez
Yuka Sasaki

title: Perceptual learning without perception

authors:
Jason Yosinski
Jeff Clune
Yoshua Bengio
Hod Lipson

title: How transferable are features in deep neural networks

authors:
Chen Zeno
Itay Golan
Elad Hoffer
Daniel Soudry

title: Task agnostic continual learning using online variational Bayes, 2018

heading: 1 INTRODUCTION

text:
We start by posing a challenging problem, referred to as Unsupervised Progressive Learning (UPL) (see Figure 1). In the UPL problem, the agent observes a sequence (or stream) of unlabeled data vectors {xt}t∈N with xt ∈ Rn. Each vector xt is associated with a class k(xt) and the vectors of class k follow a distribution Fk. The class information, however, is hidden from the agent. Occasionally, the agent may be given a small number of labeled examples of one or more classes. These examples are meant to associate “names” (i.e., class labels) with the learned representations enabling classification tasks in which the set of output classes stays constant (“persistent tasks”) or increases (“expanding tasks”).
We denote asLt the set of class labels the agent has seen up to time t. This set is gradually increasing, meaning that the agent progressively learns about more classes. In the UPL context, the goal is to learn in an online manner salient representations of the unlabeled input stream so that the agent can, at any point in time t, classify a given set of test data based on the set of classes Lt it knows about so far. We require an online learner for pragmatic reasons: it would not be possible or desirable in practice to store and/or process all previously seen data and learn a new model offline every time there is a change in Lt. The online nature of the problem constraints the solution space: methods that require multiple passes over the training data and/or randomly sampled minibatches are not applicable in the UPL context.
We assume that the distribution Fk associated with class k may also change with time – but this is a slow and gradual process so that an online learner can track changes in Fk. Abrupt changes would require that the agent forgets what was previously learned about class k – we do not consider that possibility in this paper.
We do not add any further constraints on the structure of the data sequence. For instance, it is possible that the learner first observes a labeled example of class k at time t (and so k ∈ Lt) even though it has not seen any unlabeled examples of that class prior to t – this would require a transfer-learning capability so that the learner can classify k based on representations it has previously learned from other classes. Another interesting scenario is when the unlabeled data arrive in separated class phases, which are unknown to the agent, so that each phase includes data from only few new classes – this is a challenging task from the perspective of catastrophic forgetting because the learner should not forget previously learned classes for which it does not see any new examples. We consider such UPL scenarios in Section 3.
It is plausible that UPL represents how animals learn, at least in the case of perceptual learning (Goldstone, 1998): they observe their environment, which is predominantly “unlabeled”, and so they learn to gradually distinguish between a growing number of different object categories even when they do not have a way yet to name them. Later, some of those classes may be associated with words (in the case of humans) (Ashby and Maddox, 2005), or more generally, with a specific taste, odor, reward, fear, etc. (Watanabe et al., 2001).

heading: 1.1 UPL VERSUS SIMILAR LEARNING PARADIGMS

text:
1. Unsupervised and self-supervised learning: There have been great strides recently in learning data representations (Bengio et al., 2013) via clustering (Caron et al., 2018), generative models (Jiang et al., 2017; Eslami et al., 2016; Kosiorek et al., 2018; 2019), and information theory (Hjelm et al., 2019; Ji et al., 2019). While these methods can learn representations without data labels, they still require prior information about the number of classes present in a given dataset (to set the number of cluster centroids or class outputs) and, in the continual learning case, they suffer from catastrophic forgetting unless some form of replay is used.
2. Few-shot learning (FSL) and Meta-learning: Such methods attempt to recognize object classes not seen in a training set with only a single (or handful) of labeled examples (Fei-Fei et al., 2006; Snell et al., 2017; Finn et al., 2017; Ren et al., 2018). FSL requires labeled data to learn good representations - whereas UPL only requires labeled data to associate already learned representations with new classes.
3. Semi-supervised learning (SSL): SSL addresses scarcity of available labeled data for model training by leveraging large amounts of unlabeled training data to boost performance (Springenberg, 2015; Oliver et al., 2018; Miyato et al., 2018; Kingma et al., 2014). SSL requires both labeled and unlabeled data during the training process and in most cases it needs to store and process the labeled data repeatedly during the training process.
4: Continual learning (CL): Most CL methods rely on labeled data and knowledge of which tasks are learned or performed at any point in time(Hsu et al., 2018; Parisi et al., 2019; Kemker et al., 2018; van de Ven and Tolias, 2019; Lopez-Paz and Ranzato, 2017). Further, the most effective CL mechanisms address catastrophic forgetting using stored examples or generative replay (Gepperth and Karaoguz, 2017; Shin et al., 2017).
5. Transfer learning (TL): Such methods require pre-training on a large labeled dataset and so they are not applicable to UPL (Yosinski et al., 2014).
6. Progressive learning/networks: In (labeled) progressive learning, a supervised classification model must be able to learn in an online manner without prior knowledge of the number of classes (Venkatesan and Er, 2016; Rusu et al., 2016). However, the existing approaches in this area require supervision when a new class appears, and they suffer from catastrophic forgetting if they do not see data from a previous class for long periods of time.

heading: 2 STAM ARCHITECTURE AND LEARNING ALGORITHM

text:
The learning approach that we pursue in this work is based on online clustering, novelty detection, two separate short-term and long-term memories, and storing only prototypical representations rather than specific examples. In the following, we describe the STAM architecture as a sequence of its seven major components.
The notation is summarized in Appendix A. The image preprocessing pipeline is minimal and is described in Appendix B. The reasons we decided to not pursue a deep learning approach are discussed in Appendix C.
1. Hierarchy of increasing receptive fields: An input vector xt ∈ Rn (an image in all subsequent examples) is analyzed through a hierarchy of Λ layers. Instead of neurons or hidden-layer units, each layer consists of STAM units – in its simplest form a STAM unit functions as an online clustering module. Each STAM processes one ρl × ρl patch (subvector) of the input at that layer. The patches are overlapping, with a small stride (set to one pixel in our experiments), to accomplish translation invariance (similar to CNNs). The patch dimension ρl increases in higher layers – the idea is that the first layer learns the smallest and most elementary patterns while the top layer learns the largest and most complex patterns.
2. Online clustering: Every patch of each layer is clustered, in an online manner, to a set of centroids. These time-varying centroids form the prototypical patterns that the STAM architecture gradually learns at that layer. All STAM units of layer l share the same set of centroids Cl(t) – again for translation invariance.1 Given the m’th input patch xl,m at layer l, the nearest centroid of Cl selected for xl,m is
cl.j = arg min c∈Cl d(xl,m, c) (1)
where d(xl,m, c) is the Euclidean distance between the patch xl,m and centroid c.2 The selected centroid is updated based on a learning rate parameter α, as follows:
cl,j = αxl,m + (1− α)cl,j, 0 < α < 1 (2) A higher α value makes the learning process faster but less predictable. We do not use a decreasing value of α because the goal is to keep learning in a non-stationary environment rather than convergence to a stable centroid. If the centroid cl,j is selected by more than one patches of the same input, the centroid is updated based on the closest patch to that centroid.
An online clustering algorithm that is similar to our approach (and asymptotically equivalent to k-means) can be implemented with a simple recurrent neural network of excitatory and inhibitory spiking neurons using strictly Hebbian learning, as shown recently (Pehlevan et al., 2017).
3. Novelty detection: When an input patch xl,m at layer l is significantly different than all centroids at that layer (i.e., its distance to the nearest centroid is a statistical outlier), a new centroid is created in Cl based on xl,m. We refer to this event as Novelty Detection (ND). This function is necessary so that the architecture can learn centroids associated with new classes after they appear in the unlabeled data stream.
To do so, we estimate in an online manner the distribution of the Euclidean distance between input patches and their nearest centroid (separately for each layer). We sample a randomly chosen patch from each input vector, only considering the last 1000 inputs. The novelty detection threshold at layer l is denoted by D̂l and it is defined as the 95-th percentile (β = 0.95) of the distance distribution.
1We drop the time index t from this point on but it is still implied that the centroids are dynamically learned over time.
2We have also experimented with the L1 distance metric with only minimal differences.
4. Dual-memory organization: New centroids are stored temporarily in a Short-Term Memory (STM) of limited capacity ∆ (separate for each layer). Every time a centroid is selected as the nearest neighbor of an input patch, it is updated based on (2). If an STM centroid cl,j is selected sl,j > θ times, it is copied to the Long-Term Memory (LTM) for that layer. We refer to this event as memory consolidation. The LTM has (practically) unlimited capacity and the learning rate is much smaller (in our experiments, set to zero).
This memory organization is inspired by the Complementary Learning Systems framework (Kumaran et al., 2016), where the STM role is played by the hippocampus and the LTM role by the cortex. This dual-memory scheme is necessary to distinguish between infrequently seen patterns that can be forgotten, and new patterns that are frequently seen after they first appear.
We initialize the pool of STM centroids at each layer using randomly sampled patches from the unlabeled stream (a single patch from each image to maximize diversity).
When the STM pool of centroids at a layer is full, the introduction of a new centroid (created through novelty detection) causes the removal of an earlier centroid. We use the Least-Recently Used (LRU) policy to remove atypical centroids that have not been recently selected by any input. Figure 2 illustrates this dual-memory organization.
5. Associating centroids with classes: Suppose that we have seen some labeled examples XL(t) from a set of classes L(t) up to time t. In the UPL context, we only use such labeled examples to associate existing LTM centroids at time t (learned strictly from unlabeled data) with the set of classes in L(t).
Given a labeled example of class k, suppose that there is a patch x in that example for which the nearest centroid is c. That patch contributes the following association between centroid c and class k:
fx,c(k) = e −d(x,c)/D̄l (3)
where D̄l is a normalization constant (calculated as the average distance between input patches and centroids).
The class-association vector gc between centroid c and any class k is computed aggregating all such associations, across all labeled examples in XL:
gc(k) =
∑ x∈XL(k) fx,c(k)∑
k′∈L(t) ∑ x∈XL(k′) fx,c(k ′) , k = 1 . . . L(t) (4)
Note that ∑
k gc(k)=1.
6. Class informative centroids: If a centroid is associated with only one class k (gc(k) = 1), only labeled examples of that class select that centroid. At the other extreme, if a centroid is equally likely to be selected by examples of any labeled class, (gc(k) ≈ 1/|L(t)|), the selection of that centroid does not provide any significant information for the class of the corresponding input.
We identify the centroids that are Class INformative (CIN) as those that are associated with at least one class more than expected by chance. Specifically, a centroid c is CIN if
max k∈L(t)
gc(k) > 1
|L(t)| + γ (5)
where 1|L(t)| is the chance term and γ is an additional significance term.
7. Classification using a hierarchy of centroids: At test time, we are given an input x of class k(x) and infer its class as k̂(x). The classification task is a “biased voting” process in which every patch of x, at any layer, votes for a single class as long as that patch selects a CIN centroid.
Specifically, if a patch xl,m of layer l selects a CIN centroid c, then that patch votes vl,m(k) = maxk∈L(t) gc(k) for the class k that has the highest association with c, and zero for all other classes. If c is not a CIN centroid, the vote of that patch is vl,m(k) = 0 for all classes.
The vote of layer l for class k is the average vote across all patches in layer l (as illustrated in Figure 3):
vl(k) =
∑ m∈Ml vl,m(k)
|Ml| (6)
where Ml is the set of patches in layer l. The final inference for input x is the class with the highest cumulative vote across all layers:
k̂(x) = arg max k′ Λ∑ l=1 vl(k) (7)

heading: 3 EVALUATION

text:
To evaluate the STAM architecture in the UPL context, we consider two different scenarios: Incremental UPL and Uniform UPL. In the Incremental UPL case, small groups of classes appear in successive phases. In the following results, new classes are introduced two at a time in each phase, and they are only seen in that phase. STAMs must be able to both recognize new classes when they are first seen in the stream, and to also remember all previously learned classes without catastrophic forgetting. In the Uniform UPL case, all classes appear with equal probability in the stream. The Uniform UPL scenario is more relevant when the distribution Fk of each class k may gradually change over time. The results for the Uniform scenario are presented in Appendix D.
The classification task that we focus on in the Incremental UPL case is expanding, meaning that in each phase we need to classify all classes seen so far. Given a few labeled examples for the classes that have been present in the stream up to time t, the algorithm is asked to perform object classification on a 1000-image test dataset. The datasets we evaluate on are MNIST (Lecun et al., 1998), EMNIST (balanced split with 47 classes) (Cohen et al., 2017), and SVHN (Netzer et al., 2011).
For each classification task, we average results over five trials (different unlabeled data streams). In each trial, we have a randomly sampled hold-out set of 1500 images. Then, we sample from the remaining data to form the unlabeled stream. We perform each classification task five times, using randomly sampled test inputs from the hold-out set. So, each result is the average of 25 classification evaluations.
We use a 3-layer STAM hierarchy – all hyperparameters values are reported in Appendix A. The robustness of the results as we vary these hyperparameter values is shown in Appendix E.

heading: 3.1 INCREMENTAL UPL

text:
As we introduce new classes to the incremental UPL stream (see Figure 4), the architecture recognizes previously learned classes without any major degradation in classification accuracy (left column). The average accuracy per phase is decreasing, which is due to the increasingly difficult expanding classification task. For EMNIST, we only show the average accuracy because there are 47 total classes. In all datasets, we observe that layer-3 (corresponding to the largest receptive field) contains the highest fraction of CIN centroids (center column). The ability to recognize new classes
is perhaps best visualized in the LTM centroid count (right column). During each phase the LTM count stabilizes until a sharp spike occurs at the start of the next phase when new classes are introduced. This reinforces the claim that the LTM pool of centroids (i) is stable when there are no new classes, and (ii) is able to recognize new classes via novelty detection when they appear. In the EMNIST experiment, as the number of classes increases towards 47, we gradually see fewer “spikes” in the LTM centroids for the lower receptive fields, which is expected given the repetition of patterns at that small patch size. However, the highly CIN layer-3 continues to recognize new classes and create centroids, even when the last few classes are introduced.

heading: 3.2 ABLATIONS

text: Several ablations are presented in Figure 5. On the left, we remove the LTM capabilities and only use STM centroids for classification. During the first two phases, there is little (if any) difference in classification accuracy. However, we see a clear dropoff during phases 3-5. This suggests that, without the LTM mechanisms, patterns from classes that are no longer seen in the stream are forgotten over time, and STAMs can only successfully classify classes that have been recently seen. We also investigate the importance of having static LTM centroids rather than dynamic centroids (center). Specifically, we replace the static LTM with a dynamic LTM in which the centroids are adjusted with the same learning rate parameter α, as in STM. The accuracy suffers drastically because the introduction of new classes “takes over” LTM centroids of previously learned classes, after the latter are removed from the stream. Similar to the removal of LTM, we do not see the effects of “forgetting” until phases 3-5. Note that the degradation due to a dynamic LTM is less severe than that from removing LTM completely. Finally, we look at the effects of removing layers from the STAM hierarchy (right). We see a small drop in accuracy after removing layer 3, and a large drop in accuracy after also removing layer 2. The importance of having a deeper hierarchy would be more pronounced in datasets with higher-resolution images or videos, potentially showing multiple objects in the same frame. In such cases, CIN centroids can appear at any layer, starting from the lowest to the highest.

heading: 3.3 EFFECT OF UNLABELED AND LABELED DATA

text:
We next examine the effects of unlabeled and labeled data on the STAM architecture (Figure 6). As we vary the length of the unlabeled data stream (left), we see that STAMs can actually perform well even with much less unlabeled data. This suggests that the STAM architecture may be applicable even where the datastream is much shorter than in the experiments of this paper. A longer stream would be needed however if there are many classes and some of them are infrequent. The accuracy “saturation” observed by increasing the unlabeled data from 20000 to 60000 can be explained based on the memory mechanism, which does not update centroids after they move to LTM. As showed in the ablation studies, this is necessary to avoid forgetting classes that no longer appear in the stream. The effect of varying the number of labeled examples per class (right) is much more pronounced.
We see that the STAM architecture can perform well above chance even in the extreme case of only a single (or small handful of) labeled examples per class.

heading: 4 RELATED WORK AND DISCUSSION

text:
Even though clustering has been used successfully in the past as a representation learning scheme (Coates et al., 2011; Coates and Ng, 2012), its effectiveness gradually drops as the input dimensionality increases (Hinneburg et al., 2000; Beyer et al., 1999). In the STAM architecture, we avoid this issue by clustering smaller subvectors (patches) of the input data. If those subvectors are still of high dimensionality, another approach is to reduce the intrinsic dimensionality of the input data at each layer by reconstructing that input using representations (selected centroids) from the previous layer – we have experimented with this approach but not included it here because it is not required in the datasets and tasks we work with in this paper.
This paper does not compare the performance of STAMs with other methods because, to the extent of our knowledge, none of the existing approaches in the literature are directly applicable to the UPL problem. In a follow-up study, we plan to adapt the most relevant approaches so that they can be applied in the UPL context. One of these approaches is Incremental Classifier and Representation Learning (iCaRL) (Rebuffi et al., 2017), which learns representations and classifiers from a progressive stream of labeled data and stores training examples for each class. In (Huang et al., 2019), the goal is to do unsupervised few-shot classification and the authors evaluate various methods in a similar manner to UPL but without learning from a non-stationary stream. FearNet (Kemker et al., 2018) replaces the storage of training examples with a generative model but still processes a labeled stream for both the classifier and generator. Bayesian Gradient Descent (BGD) (Zeno et al., 2018) is a method for preventing catastrophic forgetting when the learner is unaware of the task schedule and so it cannot take any special action when the input data distribution changes. A comparison of methods for continuous online sequence learning, including the Hierarchical Temporal Memory model, was conducted by Cui et al. (Cui et al., 2016) – those methods do not address the UPL problem however.
We firmly believe that in order to mimic human intelligence, learning methods should be able to learn in a streaming manner and in the absence of supervision. Animals do not “save off” labeled examples to train in parallel with unlabeled data, they do not know how many classes exist in their environment, and they do not have to replay/dream periodically all their past experiences to avoid forgetting them. The proposed STAM architecture addresses the desiderata that is often associated with Lifelong Learning:
1. Online learning: STAMs constantly update their centroids with every example. There is no separate training stage, and there is no specific task for which the network optimizes the features it learns. Any tasks that require classification will of course require one or few labeled examples so that the corresponding clusters that were formed previously are now associated with the name of a class. However, STAMs do not need these labeled examples to learn efficient data representations.
2. Transfer learning: The hierarchical nature of the proposed architecture means that features learned (in an unsupervised manner) at lower-level STAMs can be reused in different tasks that higher-level STAMs perform.
3. Resistance to catastrophic forgetting: The introduction of a new class or prototype will lead to the creation of new clusters at some STAMs in the hierarchy (e.g., layer-1 STAMs will learn new elementary visual features if we start feeding them natural images instead of MNIST examples – while a STAM at a higher-level would create a new cluster when it first starts seeing examples of scooters but without affecting the cluster associated with bicycles).
4. Expanding learning capacity: The learning capacity of a STAM architecture depends on two factors: the number of STAMs and the maximum number of centroids that each STAM can store in STM and LTM. The limited capacity constraint in the STM pool requires to forget recently created centroids that have not been recently updated with new examples. The unlimited capacity of the LTM pool of centroids, on the other hand, allows the system to gradually learn an unlimited number of classes, even if it does not see examples of all classes learned earlier.
5. No direct access to previous experience: A STAM only needs to store the centroids of the clusters it has learned so far. Those centroids correspond to prototypes, allowing the STAM to generalize. All previously seen exemplars are discarded.

heading: A STAM NOTATION AND HYPERPARAMETERS

text:
Table 3: MNIST/EMNIST Architecture
Layer ρl ∆ (incremental) ∆ (uniform)
1 8 400 2000 2 13 400 2000 3 20 400 2000
Table 4: SVHN Architecture
Layer ρl ∆ (incremental) ∆ (uniform)
1 10 2000 10000 2 14 2000 10000 3 18 2000 10000
B IMAGE PREPROCESSING
Given that each STAM operates on individual image patches, we perform patch normalization rather than image normalization. We chose a normalization operation that helps to identify similar patterns despite variations in the brightness and contrast: every patch is transformed to zero-mean, unit variance before clustering.At least for the datasets we consider in this paper, grayscale images result in higher classification accuracy than color.
We have also experimented with ZCA whitening and Sobel filtering. ZCA whitening did not work well because it requires estimating a transformation from an entire image dataset (and so it is not compatible with the online nature of the UPL problem). Sobel filtering did not work well because STAM clustering works better with filled shapes rather than the fine edges produced by Sobel filters.

heading: C WHY NOT USE DEEP LEARNING?

text:
Given that deep neural networks have become the new orthodoxy in machine learning, we need to address the question: why not use a deep learning approach to solve the UPL problem? Why to rely on online clustering instead?
1) With few exceptions, deep learning approaches have a fixed architecture and capacity (measured in terms of their hidden unit parameters) and so they are not able to automatically grow as the network is presented with new classes or tasks. Methods such as Progressive Networks (Snell et al., 2017) allow the network to grow but only when instructed that a new task/class is given – and by a pre-determined growth factor. The STAM architecture, on the other hand, grows by creating new centroids only when needed and by a growth factor that is determined in a self-supervised manner by the “degree of novelty” in the data.
2) Deep learning approaches require multiple passes over the training data, and thus they would need to either store and replay previously seen data or to learn a generative model that synthesizes realistic data when needed. Especially in semi-supervised methods such as VAT (Miyato et al., 2018), it is critical that the limited given labeled data are processed repeatedly. In the STAM architecture, data is never stored both because that may be impractical and because the data distribution in the UPL context may gradually shift – storing old data can be misleading.
3) A neural network (deep or shallow) learns a nonlinear embedding of the input data in a lowdimensional continuous space in which it is more efficient, presumably, to perform classification, clustering, generative modeling, or other tasks. This compression of the input dimensionality however comes at a high cost: the latent features learned by a neural net are not interpretable, they may be derived from properties that are unrelated to the causal/defining properties of the corresponding classes (Geirhos et al., 2019), and they can make the network susceptible to adversarial attacks. STAMs, on the other hand, use clustering to learn common patterns at a hierarchy of increasing receptive fields. These patterns can be easily interpreted by humans because they represent prototypes (common patterns) at each layer.
4) The embedding that a neural network learns is typically assumed to be time-invariant. This is problematic in the UPL context because the number of classes or tasks increases with time, without external supervision whenever that happens. It is not clear how to gradually adjust an embedding in an online manner without any external supervision when the classes/tasks change.
5) Learning in deep neural networks requires iterative nonconvex optimization processes, such as SGD, that can get stuck in local minima. Online clustering is a much simpler computation in which we only need to compute a certain distance metric between the input vector and all existing centroids – and then to update the nearest centroid based on the corresponding input.

heading: D UNIFORM UPL

text:
In order to examine if the STAM architecture can learn all classes simultaneously, but without knowing how many classes exist, we also evaluate the STAM architecture in a uniform UPL scenario (Figure 5). Note that LTM centroids converge to a constant value, at least at the top layer, Each class is recognized at a different level of accuracy, depending on the similarity between that class and others.
E ADDITIONAL HYPERPARAMETER SWEEPS AND ABLATIONS
We examine the effects of STAM hyperparameters in Figure 8. (a) As we decrease the rate of α, we see a degradation in performance. This is likely due to the static nature of the LTM centroids - with low α values, the LTM centroids will primarily represent the patch they were intialized as. (b) As we vary the rates of γ, there is little difference in our final classification rates. This suggests that the maximum gl,j(k) values are quite high, which may not be the case in other datasets besides SVHN. (c) We observe that STAM is robust to changes in Θ. (d,e) The STM size ∆ has a major effect on the number of learned LTM centroids and on classification accuracy. (e) The accuracy in
phase-5 for different numbers of layer-3 LTM centroids (and correspnding ∆ values). The accuracy shows diminishing returns after we have about 1000 LTM centroids at layer-3. (g,h) As β increases the number of LTM centroids increases (due to a lower rate of novelty detection); if β ≥ 0.9 the classification accuracy is about the same.

heading: F COMPARISON WITH AUTO-ENCODER APPROACH

text:
Even though the goal of this paper is not to present an extensive comparison between STAM and deep-learning methods, in this section we perform a limited such comparison with a simple autoencoder. Specifically, we train a convolutional autoencoder (CAE) with the images from the unlabeled data stream. The number of training epochs and the batch size are both set to 1, so that each unlabeled example is only used once. The encoder consists of three convolution layers with ReLU activations, embedding inputs into a 64-dimension latent space. The decoder consists of three transposed convolution layers with ReLU activations. The final layer uses linear activations and the network is trained to optimize Euclidean reconstruction error. The representations at the 64-dimension latent space are used to perform K nearest-neighbor (KNN) classification. The CAE architecture, given in Figure 10, is trained using Adam optimization (Kingma and Ba, 2014) with a learning rate of 1−4 and no decay.
The STAM architecture outperforms the CAE approach by a large margin (Figure 9, Incremental UPL, SVHN dataset). In follow-up work we plan to develop more sophisticated deep learning approaches for solving the UPL problem and compare them with STAMs under different conditions.

heading: G MEMORY FOOTPRINT ANALYSIS

text:
The memory requirement of the STAM model can be calculated as:
M = Λ∑ l=1 ρ2l · (|Cl|+ ∆) (8)
For the 3-layer SVHN architecture with |Cl| ≈ 3000 LTM centroids in every layer and ∆ = 2000, the memory footprint is 5, 064, 000 pixels, equivalent to roughly 5000 grayscale SVHN digits. This memory requirement can be significantly reduced however. Figure 8(f) shows that the accuracy remains almost the same when ∆ = 500 and |Cl| ≈ 1000. With these values the memory footprint reduces to about 950,000 pixels, equivalent to roughly 930 grayscale SVHN digits.
By comparison, the CAE architecture has 4, 683, 425 trainable parameters, which should be stored at floating-point precision. With four bytes per weight, then STAM model would require 9500004683425×4 ≈ 5% of the CAE’s memory footprint. Future work can decrease the STAM memory requirement further by merging similar LTM centroids.


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.

summaries: 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.

summaries: 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.

authors:
Mahmoud Assran
Nicolas Loizou
Nicolas Ballas
Mike Rabbat

title: Stochastic gradient push for distributed deep learning

venue: In International Conference on Machine Learning,

authors:
Aurélien Bellet
Rachid Guerraoui
Mahsa Taziki
Marc Tommasi

title: Personalized and private peer-to-peer machine learning

venue: Proceedings of Machine Learning Research,

authors:
Léon Bottou
Frank E Curtis
Jorge Nocedal

title: Optimization methods for large-scale machine learning

venue: Siam Review,

authors:
Stephen Boyd
Arpita Ghosh
Balaji Prabhakar
Devavrat Shah

title: Randomized gossip algorithms

venue: IEEE transactions on information theory,

authors:
Patryk Chrabaszcz
Ilya Loshchilov
Frank Hutter

title: A downsampled variant of imagenet as an alternative to the cifar datasets

venue: arXiv preprint arXiv:1707.08819,

authors:
Ofer Dekel
Ran Gilad-Bachrach
Ohad Shamir
Lin Xiao

title: Optimal distributed online prediction using mini-batches

venue: The Journal of Machine Learning Research,

authors:
J.C. Duchi
A. Agarwal
M.J. Wainwright

title: Dual averaging for distributed optimization: Convergence analysis and network scaling

venue: IEEE Transactions on Automatic Control,

authors:
Desmond Elliott
Stella Frank
Khalil Sima’an
Lucia Specia

title: Multi30k: Multilingual englishgerman image descriptions

venue: arXiv preprint arXiv:1605.00459,

authors:
Jonathan Frankle
David J. Schwab
Ari S. Morcos

title: The early phase of neural network training

venue: In International Conference on Learning Representations,

authors:
Aditya Sharad Golatkar
Alessandro Achille
Stefano Soatto

title: Time matters in regularizing deep networks: Weight decay and data augmentation affect early learning dynamics, matter little near convergence

venue: In Advances in Neural Information Processing Systems,

authors:
Priya Goyal
Piotr Dollár
Ross Girshick
Pieter Noordhuis
Lukasz Wesolowski
Aapo Kyrola
Andrew Tulloch
Yangqing Jia
Kaiming He

title: Accurate, large minibatch sgd: Training imagenet in 1 hour

venue: arXiv preprint arXiv:1706.02677,

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Delving deep into rectifiers: Surpassing human-level performance on imagenet classification

venue: In Proceedings of the IEEE international conference on computer vision,

title: Deep residual learning for image recognition

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Tong He
Zhi Zhang
Hang Zhang
Zhongyue Zhang
Junyuan Xie
Mu Li

title: Bag of tricks for image classification with convolutional neural networks

authors:
Stanislaw Jastrzebski
Maciej Szymczak
Stanislav Fort
Devansh Arpit
Jacek Tabor
Kyunghyun Cho
Krzysztof Geras

title: The break-even point on optimization trajectories of deep neural networks

authors:
David Kempe
Alin Dobra
Johannes Gehrke

title: Gossip-based computation of aggregate information

venue: In 44th Annual IEEE Symposium on Foundations of Computer Science,

authors:
Anastasia Koloskova
Sebastian U. Stich
Martin Jaggi

title: Decentralized stochastic optimization and gossip algorithms with compressed communication

venue: In ICML 2019 - Proceedings of the 36th International Conference on Machine Learning,

authors:
Anastasia Koloskova
Tao Lin
Sebastian U Stich
Martin Jaggi

title: Decentralized deep learning with arbitrary communication compression

authors:
Anastasia Koloskova
Nicolas Loizou
Sadra Boreiri
Martin Jaggi
Sebastian U Stich

title: A unified theory of decentralized SGD with changing topology and local updates

authors:
Alex Krizhevsky
Geoffrey Hinton

title: Learning multiple layers of features from tiny images

authors:
Xiangru Lian
Ce Zhang
Huan Zhang
Cho-Jui Hsieh
Wei Zhang
Ji Liu

title: Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent

authors:
Xiangru Lian
Wei Zhang
Ce Zhang
Ji Liu

title: Asynchronous decentralized parallel stochastic gradient descent

authors:
Tao Lin
Lingjing Kong
Sebastian Stich
Martin Jaggi

title: Extrapolation for large-batch training in deep learning

authors:
Tao Lin
Sebastian U. Stich
Kumar Kshitij Patel
Martin Jaggi

title: Don’t use large mini-batches, use local SGD

venue: In ICLR - International Conference on Learning Representations,

authors:
Qinyi Luo
Jinkun Lin
Youwei Zhuo
Xuehai Qian

title: Hop: Heterogeneity-aware decentralized training

venue: In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems,

authors:
Giorgi Nadiradze
Amirmojtaba Sabour
Dan Alistarh
Aditya Sharma
Ilia Markov
Vitaly Aksenov

title: Swarmsgd: Scalable decentralized sgd with local updates

venue: arXiv preprint arXiv:1910.12308,

authors:
A. Nedić
A. Ozdaglar

title: Distributed subgradient methods for multi-agent optimization

authors:
Giovanni Neglia
Chuan Xu
Don Towsley
Gianmarco Calbi

title: Decentralized gradient methods: does topology matter

venue: In AISTATS,

authors:
Shibani Santurkar
Dimitris Tsipras
Andrew Ilyas
Aleksander Madry

title: How does batch normalization help optimization

authors:
Kevin Scaman
Francis Bach
Sébastien Bubeck
Yin Tat Lee
Laurent Massoulié

title: Optimal algorithms for smooth and strongly convex distributed optimization in networks

authors:
Kevin Scaman
Francis Bach
Sébastien Bubeck
Laurent Massoulié
Yin Tat Lee

title: Optimal algorithms for non-smooth distributed optimization in networks

authors:
Christopher J Shallue
Jaehoon Lee
Joseph Antognini
Jascha Sohl-Dickstein
Roy Frostig
George E Dahl

title: Measuring the effects of data parallelism on neural network training

venue: arXiv preprint arXiv:1811.03600,

authors:
Chhavi Sharma
Vishnu Narayanan
P Balamurugan

title: A simple and fast distributed accelerated gradient method

venue: In OPT2019: 11th Annual Workshop on Optimization for Machine Learning,

authors:
Sebastian U. Stich
Sai Praneeth Karimireddy

title: The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication

title: Problems in decentralized decision making and computation

venue: PhD thesis, Massachusetts Institute of Technology,

authors:
Ashish Vaswani
Noam Shazeer
Niki Parmar
Jakob Uszkoreit
Llion Jones
Aidan N Gomez
Łukasz Kaiser
Illia Polosukhin

title: Attention is all you need

venue: In Advances in neural information processing systems,

authors:
Thijs Vogels
Sai Praneeth Karimireddy
Martin Jaggi

title: Powergossip: Practical low-rank communication compression in decentralized deep learning

venue: In NeurIPS 2020 - Thirty-fourth Conference on Neural Information Processing Systems,

authors:
Jianyu Wang
Anit Kumar Sahu
Zhouyi Yang
Gauri Joshi
Soummya Kar

title: MATCHA: speeding up decentralized SGD via matching decomposition sampling

venue: arXiv preprint arXiv:1905.09435,

authors:
Jianyu Wang
Vinayak Tantia
Nicolas Ballas
Michael Rabbat

title: Slowmo: Improving communication-efficient distributed sgd with slow momentum

authors:
Lin Xiao
Stephen Boyd

title: Fast linear iterations for distributed averaging

venue: Systems & Control Letters,

authors:
Yang You
Zhao Zhang
Cho-Jui Hsieh
James Demmel
Kurt Keutzer

title: Imagenet training in minutes

venue: In Proceedings of the 47th International Conference on Parallel Processing,

authors:
Kun Yuan
Qing Ling
Wotao Yin

title: On the convergence of decentralized gradient descent

venue: SIAM Journal on Optimization,

title: The estimation procedure

heading: 1 INTRODUCTION

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.

heading: 2 RELATED WORK

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.

heading: 3 THEORETICAL UNDERSTANDING

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.

heading: 3.1 NOTATION AND SETTING

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)

heading: 3.2 DECENTRALIZED CONSENSUS OPTIMIZATION

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)).

heading: 3.3 CONTROLLING THE CONSENSUS DISTANCE

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.

heading: 4 INSPECTING CONSENSUS DISTANCE FOR DECENTRALIZED TRAINING

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.

heading: 4.1 EXPERIMENT DESIGN: CONTROLLED DECENTRALIZED TRAINING PHASES.

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.

heading: 4.2 EXPERIMENTAL SETUP

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.

heading: 4.3 FINDINGS ON COMPUTER VISION TASKS

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.

heading: At the last phase of training, the consensus degree marginally impacts the generalization.

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.

heading: 4.4 PRELIMINARY STUDY ON TRAINING TRANSFORMER MODELS

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.

heading: A THEORY

text: In this section, we prove the claims from Section 3.

heading: A.1 PROOF OF REMARK 2, CRITICAL CONSENSUS DISTANCE

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).

heading: A.2 PROOF OF PROPOSITION 3, TYPICAL CONSENSUS DISTANCE

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

heading: A.3 SUFFICIENT BOUNDS TO MEET CRITICAL CONSENSUS DISTANCE

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.

heading: A.4 PROOF OF LEMMA 4, REPEATED GOSSIP

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.

heading: B DETAILED EXPERIMENTAL SETUP

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.

heading: C ADDITIONAL RESULTS

heading: C.1 UNDERSTANDING ON CONSENSUS AVERAGING PROBLEM

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.

heading: C.2 UNDERSTANDING THE DECENTRALIZED DEEP LEARNING TRAINING FOR CV TASKS

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.

heading: C.2.1 ADAPTIVE CONSENSUS DISTANCE CONTROL

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.

heading: C.3 CONSENSUS CONTROL WITH OTHER TOPOLOGIES

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.

heading: C.3.1 THE EXISTENCE OF THE OPTIMAL CONSENSUS DISTANCE FOR NOISE INJECTION.

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.

heading: C.4 RESULTS FOR TRAINING TRANSFORMER ON MULTI30K

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.