# ScaleCom: Scalable Sparsified Gradient Compression for Communication-
Efficient Distributed Training

Chia-Yu Chen1, Jiamin Ni2, Songtao Lu2, Xiaodong Cui1, Pin-Yu Chen2,
Xiao Sun1, Naigang Wang1, Swagath Venkataramani2,
Vijayalakshmi Srinivasan1, Wei Zhang1, and Kailash Gopalakrishnan1
IBM T. J. Watson Research Center
Yorktown Heights, NY 10598, USA
1{cchen, cuix, xsun, nwang, viji, weiz<EMAIL_ADDRESS>
2{jiamin.ni, songtao, pin-yu.chen<EMAIL_ADDRESS>
Chia-Yu Chen1
Jiamin Ni2
Songtao Lu2
Xiaodong Cui1
Pin-Yu Chen2
Xiao Sun1
Naigang Wang1
Swagath Venkataramani2
Vijayalakshmi Srinivasan1
Wei Zhang1
Kailash Gopalakrishnan1
IBM T. J. Watson Research Center
Yorktown Heights, NY 10598, USA
1{cchen, cuix, xsun, nwang, viji, weiz<EMAIL_ADDRESS>
2{jiamin.ni, songtao, pin-yu.chen<EMAIL_ADDRESS>
Chia-Yu Chen1 Jiamin Ni2 Songtao Lu2 Xiaodong Cui1 Pin-Yu Chen2 Xiao Sun1
Naigang Wang1 Swagath Venkataramani2 Vijayalakshmi Srinivasan1 Wei Zhang1
Kailash Gopalakrishnan1
IBM T. J. Watson Research Center
Yorktown Heights, NY 10598, USA
1{cchen, cuix, xsun, nwang, viji, weiz<EMAIL_ADDRESS>
2{jiamin.ni, songtao, pin-yu.chen<EMAIL_ADDRESS>
Chia-Yu Chen1, Jiamin Ni2, Songtao Lu2, Xiaodong Cui1, Pin-Yu Chen2
Xiao Sun1, Naigang Wang1, Swagath Venkataramani2
Vijayalakshmi Srinivasan1, Wei Zhang1, Kailash Gopalakrishnan1
IBM T. J. Watson Research Center
Yorktown Heights, NY 10598, USA
1{cchen, cuix, xsun, nwang, viji, weiz<EMAIL_ADDRESS>
2{jiamin.ni, songtao, pin-yu.chen<EMAIL_ADDRESS>

###### Abstract

Large-scale distributed training of Deep Neural Networks (DNNs) on state-of-
the-art platforms is expected to be severely communication constrained. To
overcome this limitation, numerous gradient compression techniques have been
proposed and have demonstrated high compression ratios. However, most existing
methods do not scale well to large scale distributed systems (due to gradient
build-up) and/or fail to evaluate model fidelity (test accuracy) on large
datasets. To mitigate these issues, we propose a new compression technique,
Scalable Sparsified Gradient Compression (ScaleCom), that leverages similarity
in the gradient distribution amongst learners to provide significantly
improved scalability. Using theoretical analysis, we show that ScaleCom
provides favorable convergence guarantees and is compatible with gradient all-
reduce techniques. Furthermore, we experimentally demonstrate that ScaleCom
has small overheads, directly reduces gradient traffic and provides high
compression rates (65-400X) and excellent scalability (up to 64 learners and
8-12X larger batch sizes over standard training) across a wide range of
applications (image, language, and speech) without significant accuracy loss.

##  1 Introduction

Over the past decade, DNNs have surpassed traditional Machine Learning models
on a wide range of applications including computer vision [1][2], speech [3],
and natural language processing (NLP) [4][5]. As models and datasets have
grown in complexity, training times have increased significantly [2][4]. To
tackle this challenge, data-parallelism approaches are widely used to
accelerate the training of DNN models [6]. In order to scale data-parallelism
techniques to more workers while preserving the computational efficiency in
each worker, it is important to increase the overall batch size proportionally
with the number of workers. However, increasing the batch size often leads to
a significant loss in test accuracy–remedied by a number of recent ideas
including increasing the learning rate during the training process as well as
a learning rate warm-up procedure [7][8][9]. Using these techniques, large
batch size training has been successfully applied to state-of-the-art
distributed systems [10][11]. However, increasing evidence seems to suggest
that there is a maximum mini-batch size beyond which the number of iterations
required to converge increases [12]. Furthermore, driven by recent advances in
low-precision arithmetic [13][14][15], there has been a renaissance in the
computational capability of deep learning training hardware resulting in
accelerator throughputs exceeding 100s of TeraOps/s [16][17][18][19]. This
dramatic increase in throughput can cause an imbalance between computation and
communication, resulting in large scale training platforms that are severely
communication constrained.

To mitigate these communication bottlenecks in DNN training, several gradient
compression techniques have been proposed [20][21][22][23]. Most of these
techniques exploit error feedback or ‘local memory’ (preserving gradient
residues from compression) to demonstrate significant compression rates and
good convergence properties. However, current error-feedback gradient
compression techniques cannot be directly applied to large-scale distributed
training. There are two primary challenges. (a) Gradient build-up: As
addressed in [24][25][26][27], compressed data can be gathered, but not
reduced. This results in a dramatically decreased compression rate as the
number of workers increases. (b) Large batch size with scaled learning rate:
As shown in [28], for a convex problem, the noise term in the error-feedback
gradient increases as the cube of the learning rate ($\alpha^{3}$). [29] also
shows that the increased learning rate could add large noise for error-
feedback gradient compression in non-convex and distributed settings. Thus,
scaled learning rates needed for large batch-sized training can significantly
increase gradient noise and cause performance degradation (or even
divergence), particularly for complex models and datasets.

In this paper, we propose a new gradient compression algorithm, ScaleCom, that
provides solutions to both of these challenges. ScaleCom provides significant
compression rates (65-400X) while enabling convergence in large-scale
distributed training (64 workers). To the best of our knowledge, this is the
first compression algorithm that has been extensively evaluated in large
datasets and batch sizes and shown to be fully compatible with conventional
all-reduce schemes, as shown in Table 1.

Table 1: Comparing different compressors for error-feedback SGD

Compressor | scalability | overhead (FLOPs/element) | compr. rate | convergence | empirical exp. |  LBe
---|---|---|---|---|---|---
Top $K$[21][30] | $\mathcal{O}(n)$ |  $\mathcal{O}(log~{}p)$ (sort)a | >100X |  not guaranteedb | broadly tested | no
AdaComp[22] | $\mathcal{O}(n)$ |  $\sim 4$ (quasi-sort) | 40-200X | not guaranteed | broadly tested | no
DGC[23] | $\mathcal{O}(n)$ |  $\mathcal{O}(1)$ (sample based-sort) | 270-600X | not guaranteed | broadly tested | no
PowerSGD[26] | $\mathcal{O}(\log(n))$ | low-rank approximation | 40-128X | not guaranteed | small datasets | yes
gTop-$k$[27] | $\mathcal{O}(\log(n))$ |  local top-$k$ merge | >100X | not guaranteed | up to 6% degrad. | no
SketchSGD[24] | constant |  $2*H(.)*r$ (sketch table)c | 40X | guaranteed | transformer | no
ScaleCom (ours) | constant |  $\sim 3$ (chunk-wise sort) | 65-400X | guaranteed | broadly testedd | yes
|  |  |  |  |  |

a $p$ is mode size. bunless explicit assumption is made. cH(.) is hash
function computation and r is rows of sketch table. d include a wide range of
applications with large datasets. e large batch size training/scaled learning
rate.

###  1.1 Challenges and Related Works

Error-feedback gradient compression and all-reduce: Error-feedback gradient
compression was first introduced by [20] and later widely applied to various
application domains [21][22][23][30]. Error-feedback gradient (also referred
to as "residues" [22] or local memory) is the difference between a worker’s
computed gradient and it’s compressed gradient. When compressed gradients from
multiple workers are sent to a centralized parameter server (for reduction),
they cause a "gradient build-up" problem. Specifically, as shown in Figure
1(a), since different workers pick different gradients during compression, the
overall compression ratio for the accumulated gradients decreases linearly
with the number of workers $n$, i.e., $\mathcal{O}(n)$. This effect is
especially dramatic in large-scale distributed systems as shown in Figure
1(b). Recently, there has been a body of work focused on the gradient build-up
issue. [25] emphasizes the importance of commutability in gradient compression
to enable efficient aggregation in ring all-reduce. [31] proposed low-rank
methods for error-feedback gradient compression that reduces the complexity to
$\mathcal{O}(\log n)$. [24] used the reduction property of sketch tables to
achieve 40X compression rates. [32] did double compression to achieve linear
speedup. [27] merged each worker’s top elements to approximate the all-reduce
of global top elements. In spite of all these efforts, none of these
techniques have been shown to comprehensively work on large models, datasets
and high number of learners, with the desired $\mathcal{O}(1)$ constant
complexity.

Large batch size training: Furthermore, many of these compression techniques
have not shown to work well in large batch size training scenarios where
communication bottlenecks limit system performance and scalability. [22] and
[23] scaled mini-batch sizes by 8X and achieved baseline accuracies for
CIFAR10 models. Similarly, [31] linearly scaled the learning rate and batch
size by 16X and reduced communication time by 54% in ResNet18 (CIFAR10).
Overall, most recent studies have primarily focused on small datasets, and it
remains unclear if gradient compression techniques work well on large models
and datasets. As shown in Figure 1(c), we observe that a naive error-feedback
gradient compression [21] scheme can cause significant accuracy degradation in
large batch size training scenarios (Transformer in WMT14 En-De).

Convergence analyses of error-feedback gradient compression: In addition to
empirical results, [28] and [29] provided convergence analyses for error-
feedback gradient compression in both convex and non-convex optimization
contexts and show convergence similar to traditional stochastic gradient
descent (SGD). The results suggest that the essence of network convergence is
the contraction property of compressors, defined as the “energy” preserved in
the compressed gradients relative to the full gradients as shown in Eqn.(4) of
[28]. The results show that both random-$k$ and top-$k$ compression could
achieve similar convergence properties as SGD. Later on [33] reported the
advantages of the top-$k$ compressor. Recent analyses [34] also proved that
error feedback can enable biased gradient compressors to reach the target test
accuracy with high compression rates. In theory, compressors are quite
flexible (biased or unbiased).

Figure 1: Challenges for gradient compression in large batch size training:(a)
Illustration of ’gradient build-up’ issue for compressed gradients. Compressed
gradients cannot be reduced directly; instead they are gathered. Gather
operation does not scale well to worker number (red). (b) Communication
bottlenecks due to gradient build-up; as worker number increases,
communication from parameter server to workers becomes a server bottleneck. In
this experiment, ResNet50 (ImageNet), bandwidth=32GBps, and compression rate
112X are used. Performance model is based on [35]. (c) In large batch size
training, standard local top-$k$ gradient compression [21] could cause model
divergence: Transformer in WMT14 En-De for 288k batch size with 64 workers.

###  1.2 Contributions

In this paper, we introduce a new gradient compression technique, ScaleCom,
that resolves the two important issues central to scalability: (i) enable
compression to work effectively with all-reduce and (ii) applicable to large
batch size training for large datasets. In comparison to existing compression
methods, our primary contributions include:

  1. 1.

We explore local memory (error feedback) similarity across workers and use
this property to design a commutative compressor, which we call cyclic local
top-$k$ (CLT-$k$). The CLT-$k$ operator solves the gather (gradient build-up)
issue and is compatible with all-reduce operations.

  2. 2.

To apply gradient compression in large batch size training, we propose a novel
low-pass filter during local memory updates. This filter cleans out disruptive
noise and enhances local memory similarity. Thus, our filter scales the
CLT-$k$ compressor to much larger-scale distributed training.

  3. 3.

We present theoretical analysis to show that ScaleCom can guarantee the same
convergence rate as SGD and enjoys linear speedup with the number of workers.
ScaleCom mitigates gradient noise induced by scaled learning rates and keeps
communication cost constant with the number of workers. Moreover, we have also
observed that ScaleCom has similar convergence properties as the ideal (but
impractical) true top-$k$ compression.

  4. 4.

Experimentally, we have verified that ScaleCom shows no degradation across a
wide range of applications (datasets) including vision (ImageNet), language
(WMT), and speech (SWB300), in both standard (8 workers) and large batch size
(64 workers) training.

##  2 Gradient Sparsification in All-Reduce

A commutative compressor between gradient averaging and sparsification
following definition (1) is desired for communication-efficient distributed
training. There are two advantages for commutative compressors: (i)
theoretically, with this setting, error-feedback gradient compression has
convergence guarantees [29], and (ii) this resolves the ‘gradient build-up’
issue and keeps communication cost constant with the number of workers [25].

$\textrm{sparse}\left(\frac{1}{n}\sum^{n}_{i=1}\mathbf{x}_{i}\right)=\frac{1}{n}\sum^{n}_{i=1}\textrm{sparse}(\mathbf{x}_{i})\vspace{-1px}\;$
(1)

Besides commutativeness, recent studies [23][28][29][33] suggest that the
top-$k$ compressor has good contraction properties and test accuracies from
both theoretical and empirical perspectives. Thus, an optimized compressor
should have both (i) commutative property and (ii) top-$k$ contraction
property. To satisfy these, we designed our compressor based on the following
two observations:

(i) Memory similarity: Although local memory (gradient residue) is never
exchanged amongst workers, it is correlated in the sense that local gradients
are computed from samples drawn from the same training set. Figure 2(a) shows
the pairwise cosine distance (worker 0 and 1)111The cosine distance of two
real-valued vectors $\mathbf{x}$, $\mathbf{y}$ $\in\mathbb{R}^{p}$ is defined
as $1-\frac{x^{T}y}{\|\mathbf{x}\|_{2}\|\mathbf{y}\|_{2}}$.  of local memory
in the first 90 iterations of ResNet18 (CIFAR10) with conventional local top-k
compressor (top-0.1% is used)[21]. The cosine distance decreases fast over the
iterations, i.e., local memory similarity is improved quickly and stays
correlated over much of the training process. (Appendix-A shows different
statistical metrics.) Finally, we observe that this phenomenon is agnostic to
increasing worker number when learning rate and per-worker batch size stays
the same as shown in Figure 2(a).

(ii) True vs local top-$k$: The local memory similarity amongst workers offers
a critical insight: the local worker’s top-$k$ indices may be used to
approximate the true top-$k$ indices. In Figure 2(b), area under blue curve
represents all-reduced error-feedback gradient magnitudes222Sum of local
memory and new computed gradients, among which, the area to the right of grey
line corresponds to its top $k$ (i.e. true top-$k$).333Top-$2\%$ is used here.
The true top-$k$ area overlaps more than 70% with the red histogram
representing local top-$k$ of worker 0, suggesting that true top-$k$ and local
top-$k$ have sufficiently overlapping indices and similar contraction
properties.

#### Cyclic Local Top-$k$ (CLT-$k$) Compressor:

Based on the similarity between local memories, we propose a novel efficient
commutative compressor for all-reduce distributed training, cyclic local
top-$k$ (CLT-$k$). It works as follows: In each iteration, we sequentially
select a leading worker in a cyclical order. The leading worker sorts its
error-feedback gradient and obtains its local top-$k$ indices. All other
workers follow the leading worker’s top-$k$ index selection for compressing
their own local error-feedback gradients. Formally, CLT-$k$ compressor is
described as follows.

Figure 2: Similarity analysis of error-feedback gradient compression on
ResNet18 (CIFAR10): (a) Cosine distance between workers’ memories over
iterations; (b) Histogram (in log scale) of element-wise residual gradient
magnitude at iteration 90 in epoch 0. (c) Cosine distance between workers’
memories with varying learning rate and low pass filter’s $\beta$ in CLT-$k$.
(d) Histogram (in log scale) of element-wise residual gradient magnitude at
iteration 90 in epoch 0 with scaled learning rate ($\alpha$=1) and low-pass
filter ($\beta$=0.1).

Let $\mathcal{I}^{k}(\mathbf{x}_{i})$ denote the index set corresponding to
the indices of the $k$ largest entries (in magnitude) of vector
$\mathbf{x}_{i}$. To be more specific, the set is defined by

$\mathcal{I}^{k}(\mathbf{x}_{i})=\\{m:|(\mathbf{x}_{i})_{m}|\geq|(\mathbf{x}_{i})_{k}|;~{}|(\mathbf{x}_{i})_{k}|\textrm{~{}is
the $k$th largest entry in magnitude of $\mathbf{x}_{i}$}\\}$ (2)

Suppose that there are $n$ vectors $\\{\mathbf{x}_{i}\\}_{i=1}^{n}$ Then, we
have $n$ local top-$k$ sets, i.e.,
$\\{\mathcal{I}^{k}(\mathbf{x}_{i})\\}_{i=1}^{n}$. For a vector
$\mathbf{x}_{j}$, the proposed CLT-$k$ compressor with worker $i$ as the
leader, denoted by
$\textrm{CLT}^{k}_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$, is defined
entry-wise as

$[\textrm{CLT}^{k}_{i}(\mathbf{x}_{j})]_{m}=\begin{cases}(\mathbf{x}_{j})_{m},\quad\textrm{if}\quad
m\in\mathcal{I}^{k}(\mathbf{x}_{i})\\\
0,\quad\quad\textrm{otherwise}.\end{cases}$ (3)

_Remark 1_. Note that when $i=j$, CLT${}^{k}_{i}(\mathbf{x}_{j})$ is reduced
to the classical top-$k$ operator on $\mathbf{x}_{i}$. When $i\neq j$,
CLT${}^{k}_{i}(\mathbf{x}_{j})$ sets $\mathbf{x}_{j}$’s entries whose indices
belong to $\mathcal{I}^{k}(\mathbf{x}_{i})$ as 0.

_Remark 2_. It is easy to verify that (3) satisfies the commutative property
in (1). Moreover, Figure 2(b) suggests the histogram of error-feedback
gradient of CLT${}^{k}_{i}(\mathbf{x}_{j})$ highly overlaps with that of
top-$k$ $(\frac{1}{n}\sum_{j=1}^{n}\mathbf{x}_{j})$. Thus, proposed CLT-$k$
compressor features efficient implementation in all-reduce, has desirable
commutative properties and shares a similar contraction property with true
top-$k$.

_Remark 3_. We note that the proposed compressor can naturally be extended to
ring all-reduce settings.

#### Low-Pass Filtering in Memory Accumulation:

Large batch size training schemes usually require to significantly scale up
learning rate. As shown in Figure 2(c), when learning rate is increased from
0.01 to 1 (100X), cosine distance becomes much larger (orange line),
suggesting drastically reduced local memory similarity, which may degrade the
performance of the CLT-$k$ compressor. Besides, scaled learning rate causes
rapid model changes and incurs larger gradient noise, which makes it more
difficult to compress gradients in large batch size settings. To address these
challenges, we propose to apply low-pass filtering [36] to local memory
accumulation. This low-pass filtering is one kind of weighted error feedback
techniques [37][38], but it focuses on large batch size training and aims to
mitigate noise from the incoming residual gradients. Our filter passes the
signals of computed gradients with smoother changes and attenuates the
gradient noise caused by rapid model changes, which (i) mitigates undesirable
noise caused by scaled learning rate, and (ii) improves local memory
similarity among workers. Formally our method is described as follow. Assuming
$n$ workers, the distributed training problem is

$\displaystyle\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}f(\boldsymbol{\theta}):=\frac{1}{n}\sum^{n}_{i=1}f_{i}(\boldsymbol{\theta})$
(4)

where
$f_{i}(\boldsymbol{\theta})=\mathbb{E}_{\xi_{i}\sim\mathcal{D}}F(\boldsymbol{\theta},\xi_{i})$
denotes the objective function at the $i$th worker, $\boldsymbol{\theta}$ is
the optimization variable (weights of the neural net), $\xi_{i}$ represents
the sample at node $i$, $\mathcal{D}$ stands for the data distribution. This
work focuses on fully-synchronized distributed training so data distributions
at different nodes are identical. Let $\mathcal{B}_{i}$ denote the mini-batch
at the $i$th worker; gradient estimate is written as
$\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})=|\mathcal{B}_{i}|^{-1}\sum_{j\in\mathcal{B}_{i}}\nabla_{\boldsymbol{\theta}}f_{i,j}(\boldsymbol{\theta}),$
where $\nabla_{\boldsymbol{\theta}}f_{i,j}(\boldsymbol{\theta})$ denotes the
gradient of loss function $f_{i}(\boldsymbol{\theta})$ w.r.t. the $j$th sample
at node $i$, and $|\mathcal{B}_{i}|$ is the batch size of the sampled data at
the $i$th worker. Here we use $\mathbf{m}_{i}$ as gradient residues (local
memory) in the $i$th worker and $\mathbf{g}_{i}$ as the compressed gradient
after scaling by step size $\alpha$. These parameters are computed locally,
where $\mathbf{g}_{i}$ will be sent to update shared weight $\mathbf{x}$.
Then, the low-pass filter on memory can be written as

$\displaystyle\mathbf{m}^{t+1}_{i}=(1-\beta)\mathbf{m}^{t}_{i}+\beta(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta}^{t})-\mathbf{g}^{t}_{i})$
(5)

where $\beta$ is the discounting factor ($0<\beta\leq 1$), and $t$ is the
number of iterations. Empirically, we verify that the use of low-pass filters
can improve the similarity among local memory for CLT-$k$ in the case of
scaled learning rate as shown in green and red lines in Figure 2 (c). Figure 2
(d) shows that when the learning rate is significantly increased (100X), with
the use of the low-pass filter, our CLT-$k$ compressor can still maintain
sufficient area overlap in the histograms with true top-$k$ compressors,
providing a necessary and desirable contraction property for robust and
scalable training. One thing should be noted that intuitively, this filtering
method has a connection to momentum SGD: momentum SGD can be viewed as a form
of filtering (moving average) on current and past gradients, which smooths out
noisy gradients to update weight more accurately. Analogously, we perform
filtering on the residual gradients to improve signal integrity in local
memory.

Algorithm 1 ScaleCom: Scalable Sparsified Gradient Compression

1:Input: initialize shared variable $\boldsymbol{\theta}$ and
$\mathbf{m}^{t}_{i}=0,\forall i$

2:for $t=1,\ldots,T$ do

3: for $i=1,\ldots,n$ in parallel do

4: Select $\mathcal{B}_{i}$$\triangleright$ set up mini-batch

5: Compute a stochastic gradient
$\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta}^{t}))$$\triangleright$
each worker computes gradients

6:
$\mathbf{g}^{t}_{i}=\textrm{CLT}^{k}_{\textrm{mod}(t,n)}(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta}^{t}))$$\triangleright$
CLT-$k$ compression (3)

7:
$\mathbf{m}^{t+1}_{i}=(1-\beta)\mathbf{m}^{t}_{i}+\beta\left(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta}^{t})-\mathbf{g}^{t}_{i}\right)$$\triangleright$
low-pass filtering (5)

8: end for

9: Upload $\\{\mathbf{g}^{t}_{i}\\}$ to the server $\triangleright$ comm. from
workers to parameter

10: $\mathbf{g}^{t}=\frac{1}{n}\sum^{n}_{i=1}\mathbf{g}^{t}_{i}$
$\triangleright$ gradient reduction

11: Download $\\{\mathbf{g}^{t}\\}$ to the each worker $\triangleright$ comm.
from parameter-server to workers

12: $\boldsymbol{\theta}^{t+1}=\boldsymbol{\theta}^{t}-\alpha\mathbf{g}^{t}$

13:end for

##  3 Scalable Sparsified Gradient Compression (ScaleCom)

In this section, we will describe the details of our algorithm, ScaleCom, and
its convergence properties. In ScaleCom, each worker first applies the CLT-$k$
compressor as shown in (3). Sparsified data is directly added (reduced) across
workers (integrated with all-reduce) avoiding ‘gradient build-up’. After all-
reduce, each worker applies a low-pass filter in local gradient accumulation,
improves workers’ memory similarity and smooths out abrupt noise induced by
scaled learning rates. For simplicity, we used the parameter server protocol
to explain our algorithm, but it can naturally be extended to all-reduce ring
implementations. The whole process is summarized in Algorithm 1. 444$t$
denotes the index of iterations. In the rests of this section, we provide
formal convergence properties for ScaleCom. 555Check Appendix-C for proof and
Appendix-D for details in convergence analysis and theory exposition.

#### Contraction Property:

We establish the contraction property of the CLT-$k$ compressor based on the
Hamming distance. The Hamming distance measures the overlap of the two index
sets. Suppose $\mathcal{I}^{k}$ is a set of $k$ indices of a vector
$\mathbf{x}$. Define a binarized vector $\mathbf{x}_{\mathcal{I}^{k}}$ as the
following: $\mathbf{x}_{{\mathcal{I}^{k}},m}=1$, if $m\in\mathcal{I}^{k}$,
otherwise, $\mathbf{x}_{{\mathcal{I}^{k}},m}=0$. Suppose $\mathcal{I}_{1}^{k}$
and $\mathcal{I}_{2}^{k}$ are two sets of $k$ indices. The Hamming distance
between the two sets given a vector $\mathbf{x}$ and an auxiliary variable $d$
are defined as:

$\displaystyle\mathbf{H}(\mathcal{I}_{1}^{k},\mathcal{I}_{2}^{k})\triangleq\mathbf{H}(\mathbf{x}_{\mathcal{I}_{1}^{k}},\mathbf{x}_{\mathcal{I}_{2}^{k}})=2d,\
\ \ \ 0\leq d\leq k.$ (6)

######  Lemma 1.

Suppose $\mathbf{y}$ is a vector and its top-$k$ index set is
$\mathcal{I}^{k}$. $\mathbf{y}$ is sparsified by another index set
$\tilde{\mathcal{I}}^{k}$. If
$\mathbf{H}(\mathcal{I}^{k},\tilde{\mathcal{I}}^{k})=2d$, we have the
following contraction property for this compressor $\text{comp}(\mathbf{y})$ :
$\mathbb{E}\parallel\\!\mathbf{y}-\textrm{comp}(\mathbf{y})\\!\parallel^{2}\leq\gamma\parallel\\!\mathbf{y}\\!\parallel^{2}$,
where

$\displaystyle\gamma\triangleq\frac{d}{k}+\left(1-\frac{d}{k}\right)\cdot\gamma_{0}$
(7)

and $\gamma_{0}$ is the contraction coefficient of top-$k$ sparsification
$\mathbb{E}\parallel\\!\mathbf{y}-\textrm{top}_{k}(\mathbf{y})\\!\parallel^{2}\leq\gamma_{0}\parallel\\!\mathbf{y}\\!\parallel^{2}.$

We can see that depending on $\frac{d}{k}$, the contraction coefficient
$\gamma\in[\gamma_{0},1]$. Specialized to the proposed CLT-$k$ compressor, for
each iteration $t$ an index set is generated from a local worker $i$ in a
cyclic fashion. Let
$\mathbf{y}=\frac{1}{n}\sum^{n}_{j=1}(\mathbf{m}^{t}_{j}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{j}}(\boldsymbol{\theta}^{t}))$
which is the averaged error-feedback gradients among all workers. We assume
$d\leq d_{0}<k$ which indicates there exists a minimal overlap $k\\!-\\!d_{0}$
between the local top-$k$ indices from worker $i$ and global true top-$k$
given by $\mathbf{y}$. Therefore,

$\displaystyle\gamma\leq\frac{d_{0}}{k}+\left(1-\frac{d_{0}}{k}\right)\cdot\gamma_{0}<1.$
(8)

It follows that
$\mathbb{E}\parallel\\!\mathbf{y}-\text{CLT}^{k}_{i}(\mathbf{y})\\!\parallel^{2}\leq\gamma\parallel\\!\mathbf{y}\\!\parallel^{2}$.

#### Convergence Analysis:

Before showing the theoretical results, we make the following assumptions.

A. 1 We suppose that the size of gradient is upper bounded, i.e.,
$\|\nabla_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta})\|\leq G,\forall i$,
and the objective function is gradient Lipschitz continuous with constant $L$
and it is lower bounded, i.e.,
$f^{\star}=\inf_{\boldsymbol{\theta}}f(\boldsymbol{\theta})>-\infty$.

A. 2 We assume that gradient estimate is unbiased, i.e.,
$\mathbb{E}[\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})]={\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta})$,
and has bounded variance, i.e.,
$\mathbb{E}[\|\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})-{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta})\|^{2}]\leq\sigma^{2}$.
By leveraging the contraction property of CLT-$k$, we can have following
convergence rate guarantees.

######  Theorem 1.

Under assumptions A.1-A.2, suppose the sequence
$\\{\boldsymbol{\theta}^{t}\\}$ is generated by CLT-$k$. Then, when learning
rate $\alpha$ and discounting factor $\beta$ are chosen as

$\alpha\sim\mathcal{O}\left(\frac{\sqrt{n}}{\sigma\sqrt{T}}\right),\quad\frac{1+\gamma-\sqrt{1-\gamma^{2}}}{2(1+\gamma)}<\beta<\frac{1+\gamma+\sqrt{1-\gamma^{2}}}{2(1+\gamma)},$
(9)

where $T$ denotes the total number of iterations and $0\leq\gamma<1$, we have

$\displaystyle\frac{1}{T}\sum^{T}_{t=1}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}\leq$
$\displaystyle\frac{\left(f(\boldsymbol{\theta}^{1})-f^{\star}\right)\sigma}{2\sqrt{nT}}+\frac{2L\sigma}{\sqrt{nT}}+\mathcal{O}\left(\frac{1}{T}\right).$
(10)

_Remark 4_. Theorem 1 showcases the linear speedup that can be achieved by
CLT-$k$, meaning that the optimiality gap (i.e., size of gradient) is
decreased as the number of workers increases. Next, we will give the analysis
to show how the number of workers $n$ and corresponding correlation between
the workers jointly affect the convergence in terms of $\gamma$, especially
for the case when $n$ is large.

######  Lemma 2.

Let $\mathbf{x}_{i}$ denote
$\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})$
and
$\mathbb{E}\|\textrm{CLT}^{k}_{i}(\mathbf{x}_{j})-\mathbf{x}_{j}\|^{2}\leq\gamma_{j}\mathbb{E}\|\mathbf{x}_{j}\|^{2},\forall\mathbf{x}_{i},\mathbf{x}_{j}$.
Assume that gradients at different workers are positively correlated, (i.e.,
exists a positive constant $\kappa$ such that
$\mathbb{E}[\mathbf{x}^{T}_{i}\mathbf{x}_{j}]\geq\kappa\|\mathbf{x}_{i}\|\|\mathbf{x}_{j}\|,\forall
i,j$), and
$\mathbb{E}\|\mathbf{x}_{i}\|^{2}=\mathbb{E}\|\mathbf{x}_{j}\|^{2},\forall
i,j$, then if $\kappa>(n\sum^{n}_{i=1}\gamma_{i}-1)/(n(n-1))$ we have
$\gamma=\frac{n\sum^{n}_{i=1}\gamma_{i}}{1+\kappa n(n-1)}<1$ such that
$\mathbb{E}\|\mathbf{y}-\textrm{CLT}^{k}_{i}(\mathbf{y})\|^{2}\leq\gamma\mathbb{E}\|\mathbf{y}\|^{2}$,
where $\mathbf{y}=\frac{1}{n}\sum^{n}_{i=1}\mathbf{x}_{i}$.

_Remark 5_. It can be seen that if $\sum^{n}_{i=1}\gamma_{i}\sim o(n)$ and
$\kappa\sim\mathcal{O}(1)$, then $\gamma\sim\mathcal{O}(1/n)$, implying that
the contraction constant is decreased w.r.t. $n$. If
$\sum^{n}_{i=1}\gamma_{i}\sim\mathcal{O}(n\kappa)$, we will have
$\gamma\sim\mathcal{O}(1)$, showing that in this case ScaleCom is able to find
the first-order stationary point for any $\kappa>0$.

#### Discussion:

Given a pre-defined $k$, the contraction coefficient of CLT-$k$ given in (7)
depends on the top-$k$ contraction coefficient $\gamma_{0}$ and the Hamming
distance $d$. The top-$k$ contraction property has been widely investigated in
literature. Theoretically, the upper bound of top-$k$ contraction $\gamma_{0}$
is $1-{d}/{n}$, which is the same as random-$k$ when the components of
gradient are uniform. Practically, $\gamma_{0}$ is observed to be a much
smaller value [33].

Figure 3: Normalized hamming distance between true top-$k$ and CLT-$k$, which
is observed to be between 0.6-0.8. This is measured using ResNet18 on CIFAR10
with learning rate 0.1 and compression rate=400X at epoch 0. Per-worker batch
size is 32.

On the other hand, the Hamming distance $d$ measures the overlap between two
top-$k$ index sets. Figure 3 shows the normalized Hamming distance ${d}/{k}$
over iterations and various number of workers. The smaller the $d/k$, the
closer the $\gamma$ to $\gamma_{0}$. It demonstrates that empirically the
overlap between local top-$k$ indices from one worker and the global true
top-$k$ indices after all-reduce is reasonable (${d}/{k}$ is in the range of
0.6-0.8), which indicates a good contraction property of the CLT-$k$
compressor in practice. This will further affect the discounting factor
$\beta$ in low-pass filtering as shown in Theorem 1.

Large datasets and small batch size: Large dataset/small batch size introduces
more noise in gradients decreasing statistical similarity between workers and
is thus harder to deal with. In the analysis above, we’ve assumed that the
minimum overlap of Hamming distance between workers to guarantee contraction <
1, which is a mild assumption in practice. Figure 3 shows that when the per-
worker batch size is 32, the Hamming distance is still above 0.32 - which is
consistent with our pilot experiments, where we tried a minibatch per-worker
of 8 with 128 workers on CIFAR10 without any noticeable degradation. This
indicates ScaleCom’s applicability in challenging training conditions (large
datasets/small mini-batch size).

##  4 Experimental Results

We apply ScaleCom to three major applications: vision (ImageNet, CIFAR10),
language (WMT14 En-De), and speech (SWB300). Experiments are run on IBM POWER
System AC922 systems using implementations in PyTorch.666See Appendix-E for
experimental details. We adopt [39] to accelerate sorting, which divides the
whole buffer into chunks and parallelizes sorting in each chunk. As suggested
in [22][23], we use 1-5 warm-up epochs (<10$\%$ total training epochs) for
compression.777No compression is applied during the warm-up period. A
conservative engineering guidance is proposed for compression rate settings in
each layer based upon the ratio FLOPs$/$gradient: 25X for ratio in the range
$[196,\infty]$; 50X for $[128,196]$, and 400X for (0, 128]. It should be noted
that this guidance is based on the per-worker mini-batch size, 32 for vision
and speech and 4.5k for language. As per-worker mini-batch size changes, the
compression rate is adjusted accordingly. In addition, to demonstrate the
robustness of ScaleCom, a much more aggressive compression rate for
Transformer-based language model is tested in both standard and large batch
size.

Standard Batch Size: In these experiments, we adopt hyper-parameter settings
from [1][3][5] (including learning rates and momentum) to achieve excellent
baseline accuracy (listed in Table 2). The same hyper-parameters are used in
ScaleCom experiments, in which we set $\beta$=1 in the low-pass filter, as
there is no need to filter the gradients in standard batch size experiments.
The experimental results are summarized in Table 2, and convergence curves are
shown in Figure 4. With compression rates of 65-400X, ScaleCom achieves
accuracies very close to the baseline for all workloads.

Table 2: Baseline vs. compression standard batch size training on image,
language and speech models

Model (Dataset) Accuracy or [other metrics] | #GPU | BSZ | Comp. Rate | Baseline | Comp.
---|---|---|---|---|---
ResNet34 (CIFAR10) | 4 | 128 | 92X | 93.78 | 93.98
ResNet18 (ImageNet) | 8 | 256 | 112X | 70.482 | 70.172
ResNet50 (ImageNet) | 8 | 256 | 96X | 76.442 | 75.988
MobileNetV2 (ImageNet) | 8 | 256 | 155X | 71.644 | 71.524
Transformer-base (WMT14 En-De) [BLEU] | 8 | 36K |  47X (65X∗) | 27.64 |  27.27 (27.24∗)
4-bidirectional-LSTM Speech (SWB300) [WER] | 4 | 128 | 400X | 10.4 | 10.1
|  |  |  |  |

∗More aggressive compression is applied without significant degradation.

Figure 4: Standard batch size training curves with ScaleCom on (a) ResNet18
for ImageNet dataset (b) MobileNetV2 with width-multiplier 1.0 on ImageNet (c)
Transformer-base machine translation (ScaleCom∗ corresponds to 65X in Table 2)
(d) LSTM-based speech model for the SWB300 dataset. Convergence and accuracy
are preserved across various models and datasets. Final training results are
summarized Table 2.

Large Batch Size Scaling: To evaluate the scalability of our methods, we
follow [7][11][40] to achieve state-of-the-art baseline accuracy with large-
scale distributed settings (listed in Table 3). Compression experiments use
the same hyper-parameters as baselines. From Section 2.2, as we scale up the
mini-batch size and learning rates in large-scale distributed training, the
gradient noise increases and local memory similarity becomes weaker among
workers, which could damage network performance. As shown in the gray lines of
Figure 5, when the low-pass filter is not applied ($\beta$=1), although small
dataset (CIFAR10) still shows good accuracy, large datasets (ImageNet, WMT14,
and SWB300) start to show degradation. Once the proposed low-pass filter is
applied ($\beta$=0.1), ScaleCom achieves almost identical test accuracies when
compared to the non-compressed baseline on every large network studied as
shown in Table 3 and Figure 5 888We observed that $\beta$ is robust to
different networks’ convergence in the range of 0.1-0.3.

Table 3: Baseline vs. compression large batch size training on image,
language, and speech models

Model (Dataset) Accuracy or [other metrics] | #GPU | BSZ | Comp. Rate | Baseline | Comp.
---|---|---|---|---|---
ResNet34 (CIFAR10) | 32 | 1024 | 92X | 93.75 | 93.36
ResNet18 (ImageNet) | 64 | 2048 | 112X | 70.285 | 69.879
ResNet50 (ImageNet) | 64 | 2048 | 96X | 76.473 | 75.895
MobileNetV2 (ImageNet) | 64 | 2048 | 155X | 71.487 | 71.014
Transformer-base (WMT14 En-De) [BLEU] | 64 | 288K |  47X (115X∗) | 27.79 |  28.03 (27.59∗)
4-bidirectional-LSTM Speech (SWB300) [WER] | 12 | 1536 | 100X | 9.9 | 10.0
|  |  |  |  |

∗More aggressive compression is applied without significant degradation.

Figure 5: Large batch size training curves with ScaleCom on (a) ResNet18 for
ImageNet dataset (b) MobileNetV2 with width-multiplier 1.0 on ImageNet (c)
Transformer-base machine translation (ScaleCom∗ corresponds to 115X in Table
3) (d) LSTM-based speech model for SWB300 dataset.

##  5 End-to-end System Performance

In this section, we quantify the improvement in end-to-end training time
achieved by ScaleCom. We considered a distributed training system comprised of
multiple accelerator chips connected to a parameter server. Each accelerator
chip consists of multiple cores with private scratchpad memory. The systematic
performance analysis framework presented in [35] is used to estimate
performance. Given a system configuration (compute throughput, memory
capacity, interconnect topology and bandwidth), the framework analytically
explores possible ways to map DNN computations on to the accelerator system
and provide performance estimations.999Appendix-F provides further details on
end-to-end system performance.

We present the performance impact of ScaleCom by varying 3 key factors: (i)
peak compute capability per worker (100 and 300 TFLOPs) (ii) the size of mini-
batch per worker (8 and 32), and (iii) the number of workers (8, 32 and 128).
When the mini-batch per worker is increased, the gradient/weight communication
becomes less frequent, limiting the scope of end-to-end performance benefits
from ScaleCom. This is evident from Figure 6a, where the communication time
(as a fraction of total time) decreases from 56% to 20%, when the mini-batch
per worker is increased from 8 to 32. Consequently, with 100 TFLOPs peak
compute per worker, ScaleCom achieves total training speedup of 2$\times$ to
1.23$\times$ even with $\sim$100$\times$ compression ratio. Fraction of
communication time grows with increase in peak TFLOPs (100 to 300), resulting
in speedup of 4.1$\times$ to 1.75$\times$.

The key trait of ScaleCom is its _performance scalability to larger number of
workers_ independent of minibatch per worker. This is shown in Figure 6b,
where the communication cost of prior top-k approaches increase linearly with
number of workers, whereas that of ScaleCom remains constant. With Scalecom,
the gradient/weight communication is < 3% of total training time even with
large number of workers (128) and small mini-batch per worker (8), leaving the
training throughput limited only by the computation inefficiency.

Figure 6: Stacked bar chart for Resnet50 (ImageNet dataset): (a) different per
worker mini-batch sizes and (b) different worker numbers.

Cost of index communication and synchronization: To enable all workers to
select the same gradients, ScaleCom incurs an additional overhead for
communicating the top-k indices. As the index vector has the same degree of
compression as the gradient vector, it occupies only 0.5% of baseline
communication time. Also, the cost remains constant ($\mathcal{O}(1)$)
independent of the number of workers. ScaleCom also incurs an additional
synchronization during the index communication. Similar to fully synchronous
SGD the slowest worker determines when the gradient communication can begin.
Once this point is reached by all workers, the additional synchronization
costs little extra time.

##  6 Conclusion

Gradient compression is a promising technique to resolve communication
bottlenecks, but has not been widely adopted in today’s training systems. The
two primary reasons for this include lack of demonstrations on large batch
sizes (and datasets) and the incompatibility of compression techniques with
all-reduce schemes. In this paper, we propose a new compression algorithm,
ScaleCom, that resolves both of these issues. We theoretically analyze
ScaleCom needs as well demonstrate scalability, robustness and excellent
compression rates (65-400X) using experiments on a spectrum of models,
datasets and batch-sizes - laying the foundation for its introduction in large
scale systems.

## Broader Impact

The amount of compute for DNNs training doubles every 3 to 4 months [41]; this
is faster than Moore’s law that doubles the number of transistors every 2
years. The latest language model GPT3 [42] takes 175 billion parameters to
achieve state of the art performance on several NLP tasks such as common sense
reasoning and word prediction. Training, designing, and optimizing these
gigantic models require tremendous time (cost) and computation power. Our
research results on compression in large-scale distributed training have two
broad benefits:

(i) Reducing time and cost to train DNN models: We believe that communication
times will bottleneck training times of distributed systems and this will
become even more severe with recent significant improvements in the
computational capability of deep learning training hardware. To address this
bottleneck, in the past few years, compression techniques have been eagerly
researched and implemented in some practical training systems [43]. Our
research results on scalability of gradient compression aim to push this to
larger scale distributed training systems, which is needed for the training of
expensive and powerful gigantic models. We believe that the scalable
compression solution can accelerate machine learning research and save the
cost for company and research institutes to develop state-of-art DNNs in real
applications and complicated datasets.

(ii) Energy consumption for environment concerns: Training DNNs especially for
big models consumes tremendous energy and starts to cause concerns in CO2
emission. As indicated in [44], Transformer training with neural architecture
search could cause CO2 emission as much as 5 cars’ lifetime. Today most DNNs
training runs in distributed systems and energy is mainly consumed in data
communication: 32-bit I/O communication took 3-4 orders of more energy (pJ)
than 32-bit float ADD computation [45]. Thus, efficient communication is
crucial to reduce energy consumption and mitigate concerns in carbon footprint
of DNNs training, especially for large-scale distributed training of gigantic
DNNs. Our research cuts communication data size by 65-400X and scale this
method to larger scale distribution, which will reduce energy consumption and
mitigate environment concerns in gigantic DNNs training. This helps to fight
climate change and global warming.

Meanwhile, we would like to point out, although our compression scheme
guarantees theoretical convergence and shows no accuracy loss compared to
baseline training over the tested models and applications, there could still
be concerns about the impact of lossy gradient compression on neural network
convergence performance. Especially when gradient compression is applied
directly without fine tuning hyper-parameters, training could still be subject
to instability, and thus it is recommended to examine the compression scheme
over a wider range of models and applications. Our conservative compression
selection rules (described in section 4) help mitigate this concern, however
task-specific robustness studies are recommended for special applications.

## Acknowledgments

The authors would like to thank Jintao Zhang and Ashish Ranjan for helpful
technical discussions, Kim-Khanh Tran, Anthony Giordano, I-Hsin Chung, Ming-
Hung Chen, Kaoutar El maghraoui, and Jeffrey Burns for the computing
infrastructure, and Leland Chang, Arvind Kumar, Yulong Li, Shubham Jain, Sunil
Shukla, Ankur Agrawal, Marcel Schaal, Mauricio Serrano, Wei Wang and the team
for the chip platform targeted in this work. This research is realized by
generous collaborations across IBM Research. Funding of this work is fully
supported by IBM Research.

## References

  * [1] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proc. of IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778, 2016.
  * [2] M. Tan and Q. V. Le, “Efficientnet: Rethinking model scaling for convolutional neural networks,” arXiv preprint arXiv:1905.11946, 2019.
  * [3] X. Cui, V. Goel, and G. Saon, “Embedding-based speaker adaptive training of deep neural networks,” arXiv preprint arXiv:1710.06937, 2017.
  * [4] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” arXiv preprint arXiv:1810.04805, 2018.
  * [5] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,”
  * [6] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, M. Mao, M. Ranzato, A. Senior, P. Tucker, K. Yang, et al., “Large scale distributed deep networks,” in Proc. of Advances in Neural Information Processing Systems, pp. 1223–1231, 2012.
  * [7] P. Goyal, P. Dollár, R. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He, “Accurate, large minibatch sgd: Training imagenet in 1 hour,” arXiv preprint arXiv:1706.02677, 2017.
  * [8] Y. You, I. Gitman, and B. Ginsburg, “Scaling SGD batch size to 32k for imagenet training,” arXiv preprint arXiv:1708.03888, vol. 6, 2017.
  * [9] Y. You, J. Li, S. Reddi, J. Hseu, S. Kumar, S. Bhojanapalli, X. Song, J. Demmel, K. Keutzer, and C.-J. Hsieh, “Large batch optimization for deep learning: Training bert in 76 minutes,” in Proc. of International Conference on Learning Representations, 2019.
  * [10] X. Jia, S. Song, W. He, Y. Wang, H. Rong, F. Zhou, L. Xie, Z. Guo, Y. Yang, L. Yu, et al., “Highly scalable deep learning training system with mixed-precision: Training imagenet in four minutes,” arXiv preprint arXiv:1807.11205, 2018.
  * [11] M. Ott, S. Edunov, D. Grangier, and M. Auli, “Scaling neural machine translation,” in Proceedings of the Third Conference on Machine Translation: Research Papers, pp. 1–9, 2018.
  * [12] S. Ma, R. Bassily, and M. Belkin, “The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning,” arXiv preprint arXiv:1712.06559, 2017.
  * [13] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan, “Deep learning with limited numerical precision,” in Proc. of International Conference on Machine Learning, pp. 1737–1746, 2015.
  * [14] N. Wang, J. Choi, D. Brand, C.-Y. Chen, and K. Gopalakrishnan, “Training deep neural networks with 8-bit floating point numbers,” in Proc. of Advances in Neural Information Processing Systems, pp. 7675–7684, 2018.
  * [15] X. Sun, J. Choi, C.-Y. Chen, N. Wang, S. Venkataramani, V. V. Srinivasan, X. Cui, W. Zhang, and K. Gopalakrishnan, “Hybrid 8-bit floating point (HFP8) training and inference for deep neural networks,” in Proc. of Advances in Neural Information Processing Systems, pp. 4901–4910, 2019.
  * [16] B. Fleischer, S. Shukla, M. Ziegler, J. Silberman, J. Oh, V. Srinivasan, J. Choi, S. Mueller, A. Agrawal, T. Babinsky, et al., “A scalable multi-teraops deep learning processor core for ai trainina and inference,” in 2018 IEEE Symposium on VLSI Circuits, pp. 35–36, IEEE, 2018.
  * [17] R. Krashinsky, O. Giroux, S. Jones, N. Stam, and S. Ramaswamy, “Nvidia ampere architecture in-depth,” NVIDIA blog: https://devblogs.nvidia.com/nvidia-ampere-architecture-in-depth/, 2020.
  * [18] J. Dean, “1.1 the deep learning revolution and its implications for computer architecture and chip design,” in 2020 IEEE International Solid-State Circuits Conference-(ISSCC), pp. 8–14, IEEE, 2020.
  * [19] J. Oh, S. Lee, M. K. Kang, M. Ziegler, J. Silberman, and A. e. Agrawal, “A 3.0 tflops 0.62v scalable processor core for high compute utilization ai training and inference,” in Proc. of Symposia on VLSI Technology and Circuits, 2020\.
  * [20] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu, “1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns,” in Proc. of Annual Conference of the International Speech Communication Association, 2014.
  * [21] N. Strom, “Scalable distributed dnn training using commodity gpu cloud computing,” in Proc. of Annual Conference of the International Speech Communication Association, 2015.
  * [22] C.-Y. Chen, J. Choi, D. Brand, A. Agrawal, W. Zhang, and K. Gopalakrishnan, “Adacomp: Adaptive residual gradient compression for data-parallel distributed training,” in Proc. of AAAI Conference on Artificial Intelligence, 2018.
  * [23] Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally, “Deep gradient compression: Reducing the communication bandwidth for distributed training,” arXiv preprint arXiv:1712.01887, 2017.
  * [24] N. Ivkin, D. Rothchild, E. Ullah, I. Stoica, R. Arora, et al., “Communication-efficient distributed SGD with sketching,” in Proceedings of Neural Information Processing Systems (NeurIPS), pp. 13144–13154, 2019.
  * [25] M. Yu, Z. Lin, K. Narra, S. Li, Y. Li, N. S. Kim, A. Schwing, M. Annavaram, and S. Avestimehr, “Gradiveq: Vector quantization for bandwidth-efficient gradient aggregation in distributed cnn training,” in Proc. of Advances in Neural Information Processing Systems, pp. 5123–5133, 2018.
  * [26] T. Vogels, S. P. Karimireddy, and M. Jaggi, “Powersgd: Practical low-rank gradient compression for distributed optimization,” in Proc. of Advances in Neural Information Processing Systems, pp. 14236–14245, 2019.
  * [27] S. Shi, Q. Wang, K. Zhao, Z. Tang, Y. Wang, X. Huang, and X. Chu, “A distributed synchronous sgd algorithm with global top-k sparsification for low bandwidth networks,” in 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pp. 2238–2247, IEEE, 2019.
  * [28] S. U. Stich, J.-B. Cordonnier, and M. Jaggi, “Sparsified sgd with memory,” in Proc. of Advances in Neural Information Processing Systems, pp. 4447–4458, 2018.
  * [29] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli, “The convergence of sparsified gradient methods,” in Proc. of Advances in Neural Information Processing Systems, pp. 5973–5983, 2018.
  * [30] N. Dryden, T. Moon, S. A. Jacobs, and B. Van Essen, “Communication quantization for data-parallel training of deep neural networks,” in 2016 2nd Workshop on Machine Learning in HPC Environments (MLHPC), pp. 1–8, IEEE, 2016.
  * [31] T. Vogels, S. P. Karimireddy, and M. Jaggi, “PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization,” in Proc. of Advances in Neural Information Processing Systems, 2019.
  * [32] H. Tang, X. Lian, C. Yu, T. Zhang, and J. Liu, “Doublesqueeze: Parallel stochastic gradient descent with double-pass error-compensated compression,” arXiv preprint arXiv:1905.05957, 2019.
  * [33] S. Shi, X. Chu, K. C. Cheung, and S. See, “Understanding Top-k Sparsification in Distributed Deep Learning,” 2019.
  * [34] S. P. Karimireddy, Q. Rebjock, S. U. Stich, and M. Jaggi, “Error feedback fixes signsgd and other gradient compression schemes,” arXiv preprint arXiv:1901.09847, 2019.
  * [35] S. Venkataramani, V. Srinivasan, J. Choi, P. Heidelberger, L. Chang, and K. Gopalakrishnan, “Memory and interconnect optimizations for peta-scale deep learning systems,” in 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC), pp. 225–234, IEEE, 2019\.
  * [36] A. V. Oppenheim and R. W. Schafer, “Discrete-time signal processing, 3rd edition,” 2009.
  * [37] A. Abdi and F. Fekri, “Quantized compressive sampling of stochastic gradients for efficient communication in distributed deep learning,” in Proc. of AAAI Conference on Artificial Intelligence, 2020.
  * [38] J. Wu, W. Huang, H. Junzhou, and T. Zhang, “Error compensated quantized sgd and its applications to large-scale distributed optimization,” in 2018 International Conference on Machine Learning (ICML), pp. PMLR 80:5325–5333, 2018\.
  * [39] P. Kipfer, “Chapter 46. improved gpu sorting,” 2005.
  * [40] W. Zhang, X. Cui, A. Kayi, M. Liu, U. Finkler, B. Kingsbury, G. Saon, Y. Mroueh, A. Buyuktosunoglu, P. Das, et al., “Improving efficiency in large-scale decentralized distributed training,” in Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3022–3026, IEEE, 2020.
  * [41] D. Amodei, D. Hernandez, G. Sastry, J. Clark, G. Brockman, and I. Sutskever, “Ai and compute,” OpenAI blog: https://openai.com/blog/ai-and-compute/, 2018.
  * [42] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al., “Language models are few-shot learners,” arXiv preprint arXiv:2005.14165, 2020.
  * [43] S. H. K. Parthasarathi, N. Sivakrishnan, P. Ladkat, and N. Strom, “Realizing petabyte scale acoustic modeling,” IEEE Journal on Emerging and Selected Topics in Circuits and Systems, vol. 9, no. 2, pp. 422–432, 2019.
  * [44] E. Strubell, A. Ganesh, and A. McCallum, “Energy and policy considerations for deep learning in nlp,” arXiv preprint arXiv:1906.02243, 2019.
  * [45] A. Ishii, D. Foley, E. Anderson, B. Dally, G. Dearth, L. Dennison, M. Hummel, and J. Schafer, “Nvswitch and dgx-2 nvlink-switching chip and scale-up compute server,” 2018.
  * [46] W. Zhang, X. Cui, U. Finkler, G. Saon, A. Kayi, A. Buyuktosunoglu, B. Kingsbury, D. Kung, and M. Picheny, “A highly efficient distributed deep learning system for automatic speech recognition,” arXiv preprint arXiv:1907.05701, 2019.

##  Appendix A Observations in Local Memory Similarity

We observed local memory’s similarity through Q–Q (quantile-quantile) plots as
shown in Figure A1(a)-(c). In Figure A1(a), the linearity of the points in Q-Q
plot suggests that the worker 1’s local memory (accumulated gradient)
magnitudes have very similar statistical distributions as worker 2. The red
line is the linear regression fitting for the blue dots; overall its $R^{2}$
score is 0.99; indicates their local memory magnitude distributions (worker 1
and 2) are very similar. This is consistent to our observations in pairwise
cosine distance shown in Figure 2(a). The memory accumulation (accumulate
gradients over iterations) reduces gradient variation and enhances the
similarity across workers. On the other hand, when plotting the computed
gradients (right after backward computation) in Q-Q plot, we do not observe
the excellent similarity between worker 1 and 2 as shown in Figure A1(b). In
this case, the linear regression fitting $R^{2}$ score is 0.89. In Figure
A1(c), we compare worker 1’s error-feedback gradients (local memory + computed
gradients) magnitudes with global all-reduced error-feedback gradient
magnitudes. From the plot, we can observe that their distribution quantiles
are highly correlated ($R^{2}$ linear regression fitting score is 0.99). The
Spearman’s rank correlation coefficient between worker 1 and all-reduced
error-feedback gradient magnitudes is 0.657 (p-value=0). This indicates that
we can possibly use local worker’s top-$k$ to approximate true top-$k$
selections.

Figure A1: Q-Q plots for local memory and gradient magnitudes on ResNet18
(CIFAR10) with 8 workers at iteration 100 in epoch 0. Local top-$k$ [1] (top
0.1%) and learning rate 0.01 are used in the experiments. Red lines are the
linear regression fitting results. (a) worker 1’s local memory magnitudes
quantile versus worker 2; (b) worker 1’s computed gradient magnitudes versus
worker 2. (c) worker 1’s error-feedback gradient (local memory + computed
gradients) magnitudes versus all-reduced (global) error-feedback gradient
magnitudes.

##  Appendix B Preliminaries

Before showing the convergence proofs, we give the following table to
highlight the notations and definitions of the variables used in the proofs.

Recall the optimization problem is

$\min_{\boldsymbol{\theta}\in\mathbb{R}^{p}}f(\boldsymbol{\theta}):=\frac{1}{n}\sum^{n}_{i=1}f_{i}(\boldsymbol{\theta}),\vspace{-1px}\;$
(A1)

and the gradient estimate is as the following

$\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})=\frac{1}{|\mathcal{B}_{i}|}\sum_{j\in\mathcal{B}_{i}}\nabla_{\boldsymbol{\theta}}f_{i,j}(\boldsymbol{\theta}).$
(A2)

Table A1: Definition of parameters used in the proofs Parameter | Expression/Definition | Representation
---|---|---
$p$ | $\mathbb{R}$ | problem dimension
$d$ | (6) | Hamming distance
$n$ | $\mathbb{R}$ | total number of workers
$\alpha$ | $\mathbb{R}$ | step size
$\beta$ | $\mathbb{R}$ | discounting factor of low-pass filter
$\gamma$ | $\mathbb{R}$ | contraction parameter
$\boldsymbol{\theta}$ | $\mathbb{R}^{p}$ | optimization variable
$f_{i}(\cdot)$ | $\mathbb{E}_{\xi_{i}\sim\mathcal{D}}F(\cdot,\xi_{i})$ | individual function
$f(\cdot)$ | (A1) | objective function
$\mathcal{I}^{k}(\cdot)$ | (2) | index set of top entries $k$
$\mathcal{B}_{i}$ | n/a | mini-batch set at worker $i$
$\widehat{\nabla}f_{\mathcal{B}_{i}}(\mathbf{x})$ or $\widehat{\nabla}f_{i}(\mathbf{x})$ | (A2) | gradient estimate by $\mathcal{B}_{i}$
$\mathbf{m}_{i}$ | $\mathbb{R}^{p}$ | memory at the $i$th node
$t$ | $\mathbb{R}$ | index of iteration
$T$ | $\mathbb{R}$ | total number of iterations
$G$ | A.1 | upper bound of gradients’ size
$L$ | A.1 | gradient Lipschitz constant
$f^{\star}$ | A.1 | global minimum of $f(\mathbf{x})$

We also use several standard inequalities as follows:

1, Young’s inequality with parameter $\epsilon$ is

$\langle\mathbf{x},\mathbf{y}\rangle\leq\frac{\epsilon}{2}\|\mathbf{x}\|^{2}+\frac{1}{2\epsilon}\|\mathbf{y}\|^{2}$
(A3)

where $\mathbf{x},\mathbf{y}\in\mathbb{R}^{p}$ are vectors.

One variant of Young’s inequality is

$\|\mathbf{x}+\mathbf{y}\|^{2}\leq\left(1+\epsilon\right)\|\mathbf{x}\|^{2}+\left(1+\frac{1}{\epsilon}\right)\|\mathbf{y}\|^{2}$
(A4)

2, The quadrilateral identity is

$\langle\mathbf{x},\mathbf{y}\rangle=\frac{1}{2}\left(\|\mathbf{x}\|^{2}+\|\mathbf{y}\|^{2}-\|\mathbf{x}-\mathbf{y}\|^{2}\right).$
(A5)

##  Appendix C Proof of Lemma 1 on Contraction Property

###### Proof.

Suppose $\mathbf{y}$ is an $p$-dimensional vector and $\mathcal{I}^{k}$ is its
top-$k$ index set. $\mathbf{y}$ is sparsified by the compressor
$\textrm{comp}(\cdot$) via another index set $\tilde{\mathcal{I}}^{k}$ and
$\mathbf{H}(\mathcal{I}^{k},\tilde{\mathcal{I}}^{k})=2d$.

We have

$\displaystyle\parallel\\!\mathbf{y}-\textrm{comp}(\mathbf{y})\\!\parallel^{2}$
(A6) $\displaystyle=$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\sum_{i=1}^{p}\mathbf{y}^{2}_{i}I\\{i\in\tilde{\mathcal{I}}^{k}\\}$
(A7) $\displaystyle=$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\sum_{i\in\mathcal{I}^{k}}\mathbf{y}^{2}_{i}I\\{i\in\tilde{\mathcal{I}}^{k}\\}-\sum_{i\in\setminus\mathcal{I}^{k}}\mathbf{y}^{2}_{i}I\\{i\in\tilde{\mathcal{I}}^{k}\\}$
(A8) $\displaystyle\leq$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\sum_{i\in\mathcal{I}^{k}}\mathbf{y}^{2}_{i}I\\{i\in\tilde{\mathcal{I}}^{k}\\}.$
(A9)

Since $\mathbf{H}(\mathcal{I}^{k},\tilde{\mathcal{I}}^{k})=2d$, there is an
overlap of $k\\!-\\!d$ indices between $\mathcal{I}^{k}$ and
$\tilde{\mathcal{I}}^{k}$. Taking the expectation over the all possible
combinations and permutation, we have

$\displaystyle\mathbb{E}\parallel\\!\mathbf{y}-\textrm{comp}(\mathbf{y})\\!\parallel^{2}$
(A10) $\displaystyle=$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\sum_{i\in\mathcal{I}^{k}}\mathbf{y}^{2}_{i}\frac{C_{k-1}^{k-d-1}}{C_{k}^{k-d}}$
(A11) $\displaystyle=$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\frac{k-d}{k}\sum_{i\in\mathcal{I}^{k}}\mathbf{y}^{2}_{i}$
(A12) $\displaystyle=$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\frac{k-d}{k}\left(\parallel\\!\mathbf{y}\\!\parallel^{2}-\parallel\\!\mathbf{y}\\!-\\!\textrm{top}_{k}(\mathbf{y})\\!\parallel^{2}\right)$
(A13) $\displaystyle\leq$
$\displaystyle\parallel\\!\mathbf{y}\\!\parallel^{2}-\frac{k-d}{k}\parallel\\!\mathbf{y}\\!\parallel^{2}+\frac{k-d}{k}\gamma_{0}\parallel\\!\mathbf{y}\\!\parallel^{2}$
(A14) $\displaystyle=$
$\displaystyle\left(\frac{d}{k}+\left(1-\frac{d}{k}\right)\cdot\gamma_{0}\right)\parallel\\!\mathbf{y}\\!\parallel^{2},$
(A15)

which completes the proof. ∎

##  Appendix D Convergence Performance Analysis of CLT-$k$

######  Lemma 3.

Under assumptions A.1-A.2. Suppose the sequences
$\\{\boldsymbol{\theta}^{t},\mathbf{m}^{t}_{i},t\geq 1\\}$ is generated by
CLT-$k$. Then, when
$\beta\in(\frac{1+\gamma-\sqrt{1-\gamma^{2}}}{2(1+\gamma)},\frac{1+\gamma+\sqrt{1-\gamma^{2}}}{2(1+\gamma)})$,
we have

$\displaystyle\mathbb{E}\|\mathbf{m}^{t}\|^{2}\leq\beta^{2}(1+\gamma)G^{2}\left(1+\frac{1}{C_{\epsilon}}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}$
(A16)

where $\mathbf{m}^{t}=n^{-1}\sum^{n}_{i=1}\mathbf{m}^{t}_{i}$, and
$C_{\epsilon}>0$ and $0<\lambda<1$ are some constants.

###  D.1 Proof of Lemma 3

###### Proof.

Define a “virtual” sequence $\mathbf{v}$ as the following

$\mathbf{v}^{t+1}=\mathbf{v}^{t}-\alpha\underbrace{\frac{1}{n}\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta}^{t})}_{:=\widehat{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})}.$
(A17)

For simplicity of notation, we denote
$\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta})$ as
$\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})$.
When $\mathbf{v}^{0}=\boldsymbol{\theta}^{0}=\mathbf{m}^{0}=0$, it is easy to
check that

$\boldsymbol{\theta}^{t}-\mathbf{v}^{t}=\frac{\alpha}{\beta}\underbrace{\frac{1}{n}\sum^{n}_{i=1}\mathbf{m}^{t}_{i}}_{:=\mathbf{m}^{t}},$
(A18)

so we have

$\|\boldsymbol{\theta}^{t}-\mathbf{v}^{t}\|^{2}=\frac{\alpha^{2}}{\beta^{2}}\|\mathbf{m}^{t}\|^{2}.$
(A19)

From A. 2, we have

$\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta})-\widehat{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta})\|^{2}\leq\frac{\sigma^{2}}{n}$
(A20)

since
$\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta})-\widehat{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta})\|=\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta})-n^{-1}\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{i}}(\boldsymbol{\theta})\|$.

Then, we are able to quantify $\|n^{-1}\sum^{n}_{i=1}\mathbf{m}^{t}_{i}\|$ as
follows:

$\displaystyle\|\mathbf{v}^{t+1}-\boldsymbol{\theta}^{t+1}\|$
$\displaystyle\mathop{=}\limits^{\eqref{eq.defv}}$
$\displaystyle\left\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}+\alpha\frac{1}{n}\left(\sum^{n}_{i=1}\textrm{CLT}^{k}_{\textrm{mod}(t,n)}(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t}))-\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})\right)\right\|$
(A21) $\displaystyle=$
$\displaystyle\left\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}+\frac{\alpha}{\beta}\mathbf{m}^{t}-\frac{\alpha}{\beta}\mathbf{m}^{t}+\alpha\frac{1}{n}\left(\sum^{n}_{i=1}\textrm{CLT}^{k}_{\textrm{mod}(t,n)}(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t}))-\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})\right)\right\|$
(A22) $\displaystyle\mathop{\leq}\limits^{\eqref{eq.xvm}}$
$\displaystyle\alpha\left\|\frac{1}{n}\left(\sum^{n}_{i=1}\textrm{CLT}^{k}_{\textrm{mod}(t,n)}(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t}))\right)-\frac{1}{n}\left(\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})+\mathbf{m}^{t}_{i}\right)\right\|+\alpha\left(\frac{1}{\beta}-1\right)\|\mathbf{m}^{t}\|^{2}$
$\displaystyle\mathop{=}\limits^{\eqref{eq.coneq}}$
$\displaystyle\alpha\left\|\textrm{CLT}^{k}_{\textrm{mod}(t,n)}\left(\frac{1}{n}\sum^{n}_{i=1}(\mathbf{m}^{t}_{i}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t}))\right)-\frac{1}{n}\left(\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})+\mathbf{m}^{t}_{i}\right)\right\|+\alpha\left(\frac{1}{\beta}-1\right)\|\mathbf{m}^{t}\|^{2}$
$\displaystyle\mathop{\leq}\limits^{(a)}$
$\displaystyle\alpha\sqrt{\gamma}\left\|\frac{1}{n}\sum^{n}_{i=1}\left(\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})+\mathbf{m}^{t}_{i}\right)\right\|+\alpha\left(\frac{1}{\beta}-1\right)\|\mathbf{m}^{t}\|^{2}$
(A23)

where in $(a)$ we apply Lemma 1.

Squaring both sides of (A23), we have

$\displaystyle\|\mathbf{v}^{t+1}-\boldsymbol{\theta}^{t+1}\|^{2}\mathop{\leq}\limits^{(a)}$
$\displaystyle\left(1+\frac{1}{\gamma}\right)\alpha^{2}\gamma\left(\left(1+\epsilon\right)\left\|\frac{1}{n}\sum^{n}_{i=1}\mathbf{m}^{t}_{i}\right\|^{2}+\left(1+\frac{1}{\epsilon}\right)\left\|\frac{1}{n}\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})\right\|^{2}\right)$
$\displaystyle+(1+\gamma)\alpha^{2}\left(\frac{1}{\beta}-1\right)^{2}\|\mathbf{m}^{t}\|^{2}$
(A24) $\displaystyle\mathop{=}\limits^{\eqref{eq.xvm}}$
$\displaystyle\left(1+\gamma\right)\left(1+\epsilon\right)\beta^{2}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}+\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\left\|\frac{1}{n}\sum^{n}_{i=1}\widehat{\nabla}_{\boldsymbol{\theta}}f_{i}(\boldsymbol{\theta}^{t})\right\|^{2}$
$\displaystyle+\alpha^{2}(1+\gamma)\left(\frac{1}{\beta}-1\right)^{2}\|\mathbf{m}^{t}\|^{2}.$
(A25)

where in $(a)$ we use Young’s inequality with parameter $1/\gamma$.

Taking expectation on both sides of (A25), we have

$\displaystyle\mathbb{E}\|\mathbf{v}^{t+1}-\boldsymbol{\theta}^{t+1}\|^{2}$
$\displaystyle\leq$
$\displaystyle\left(1+\epsilon\right)(1+\gamma)\beta^{2}\mathbb{E}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}+\alpha^{2}\gamma\left(1+\frac{1}{\epsilon}\right)\mathbb{E}\left\|\widehat{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})-\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\right\|^{2}$
$\displaystyle+\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}+\alpha^{2}(1+\gamma)\left(\frac{1}{\beta}-1\right)^{2}\|\mathbf{m}^{t}\|^{2}$
(A26) $\displaystyle\leq$
$\displaystyle\left(1+\epsilon\right)(1+\gamma)\beta^{2}\mathbb{E}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}+\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}+\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\frac{\sigma^{2}}{n}$
$\displaystyle+\alpha^{2}(1+\gamma)\left(\frac{1}{\beta}-1\right)^{2}\|\mathbf{m}^{t}\|^{2}.$
(A27)

Since the size of the gradients is bounded by $G$, we have

$\displaystyle\mathbb{E}\|\mathbf{v}^{t+1}-\boldsymbol{\theta}^{t+1}\|^{2}\leq$
$\displaystyle\left(1+\epsilon\right)(1+\gamma)\beta^{2}\mathbb{E}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}+\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)$
$\displaystyle+\alpha^{2}(1+\gamma)\left(\frac{1}{\beta}-1\right)^{2}\|\mathbf{m}^{t}\|^{2}$
(A28) $\displaystyle\mathop{=}\limits^{\eqref{eq.xvre}}$
$\displaystyle\left(1+\epsilon\right)(1+\gamma)\beta^{2}\mathbb{E}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}+\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)$
$\displaystyle+(1+\gamma)\left(\beta-1\right)^{2}\mathbb{E}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}.$
(A29)

It is obvious that when

$\left(1+\epsilon\right)(1+\gamma)\beta^{2}+(1+\gamma)\left(\beta-1\right)^{2}:=\lambda<1,$
(A30)

then sequence $\mathbb{E}\|\mathbf{v}^{t+1}-\boldsymbol{\theta}^{t+1}\|^{2}$
will be upper bounded by a constant. Therefore, we request

$\frac{1}{1+\gamma}>(1-\beta)^{2},$ (A31)

i.e., $\beta>1-\sqrt{1/(1+\gamma)}$ such that $1-(1+\gamma)(\beta-1)^{2}>0$.
Then, we can choose $\epsilon$ small enough, i.e.,

$\epsilon<\underbrace{\frac{1-(1+\gamma)(\beta-1)^{2}}{(1+\gamma)\beta^{2}}-1}_{:=C_{\epsilon}},$
(A32)

so that $\lambda<1$ when $C_{\epsilon}>0$.

Next, in order to get $C_{\epsilon}>0$, we need

$1-(1+\gamma)(\beta-1)^{2}>(1+\gamma)\beta^{2},$ (A33)

which is equivalent to

$2(1+\gamma)\beta^{2}-2(1+\gamma)\beta+\gamma<0.$ (A34)

Therefore, when

$0<\frac{1+\gamma-\sqrt{1-\gamma^{2}}}{2(1+\gamma)}<\beta<\frac{1+\gamma+\sqrt{1-\gamma^{2}}}{2(1+\gamma)}<1,$
(A35)

and $\beta>1-\sqrt{1/(1+\gamma)}$, we have $\lambda<1$. Note that here
$\frac{1+\gamma-\sqrt{1-\gamma^{2}}}{2(1+\gamma)}$ is always greater than
$1-\sqrt{1/(1+\gamma)}$. The reasons are as follows: first, we know that

$2(1+\gamma)>2\sqrt{1-\gamma^{2}}(1+\gamma).$ (A36)

Adding $2(1+\gamma)$ on both sides, we will get

$4(1+\gamma)>1-\gamma^{2}+2\sqrt{1-\gamma^{2}}(1+\gamma)+1+2\gamma+\gamma^{2},$
(A37)

which implies

$2\sqrt{1+\gamma}>\sqrt{1-\gamma^{2}}+(1+\gamma).$ (A38)

Dividing $2(1+\gamma)$ on both sides, we can arrive at

$\sqrt{\frac{1}{1+\gamma}}-\frac{\sqrt{1-\gamma^{2}}}{2(1+\gamma)}>\frac{1}{2},$
(A39)

which is the desired result.

Then, iterate (A29) gives

$\displaystyle\mathbb{E}\|\mathbf{v}^{t+1}-\boldsymbol{\theta}^{t+1}\|^{2}\mathop{\leq}\limits^{(a)}$
$\displaystyle\alpha^{2}(1+\gamma)\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\sum^{t}_{\tau=1}\lambda^{\tau}$
(A40) $\displaystyle\mathop{\leq}\limits^{(b)}$
$\displaystyle\alpha^{2}(1+\gamma)G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}$
(A41)

where $(a)$ holds since $\mathbf{v}^{0}=\boldsymbol{\theta}^{0}$, and $(b)$ is
true because of $\lambda<1$. ∎

###  D.2 Proof of Theorem 1

###### Proof.

By the gradient Lipschitz continuity of the objective function, we have

$\displaystyle f(\mathbf{v}^{t+1})\leq$ $\displaystyle
f(\mathbf{v}^{t})+\left\langle\nabla
f(\mathbf{v}^{t}),\mathbf{v}^{t+1}-\mathbf{v}^{t}\right\rangle+\frac{L}{2}\left\|\mathbf{v}^{t+1}-\mathbf{v}^{t}\right\|^{2}$
(A42) $\displaystyle\mathop{\leq}\limits^{\eqref{eq.defv}}$ $\displaystyle
f(\mathbf{v}^{t})-\alpha\left\langle\nabla
f(\mathbf{v}^{t}),\widehat{\nabla}f(\boldsymbol{\theta}^{t})\right\rangle+\frac{\alpha^{2}L}{2}\|\widehat{\nabla}f(\boldsymbol{\theta}^{t})\|^{2}$
(A43) $\displaystyle\leq$ $\displaystyle
f(\mathbf{v}^{t})-\alpha\left\langle\nabla
f(\mathbf{v}^{t}),\widehat{\nabla}f(\boldsymbol{\theta}^{t})\right\rangle+\alpha^{2}L\|\widehat{\nabla}f(\boldsymbol{\theta}^{t})-{\nabla}f(\boldsymbol{\theta}^{t})\|^{2}+\alpha^{2}L\|{\nabla}f(\boldsymbol{\theta}^{t})\|^{2}.$
(A44)

Taking expectation on both sides of (A44), we have

$\displaystyle\mathbb{E}[f(\mathbf{v}^{t+1})]\mathop{\leq}\limits^{(a)}$
$\displaystyle\mathbb{E}[f(\mathbf{v}^{t})]-\alpha\left\langle\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t}),{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\right\rangle+\frac{\alpha^{2}L^{2}}{2}\mathbb{E}\|\widehat{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}$
(A45) $\displaystyle\mathop{=}\limits^{(b)}$
$\displaystyle\mathbb{E}[f(\mathbf{v}^{t})]-\frac{\alpha}{2}\left(\|\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|^{2}+\|{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}-\|\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})-{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}\right)$
$\displaystyle+\alpha^{2}L\mathbb{E}\|{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}+\frac{\alpha^{2}L\sigma^{2}}{n}$
$\displaystyle\mathop{\leq}\limits^{(c)}$
$\displaystyle\mathbb{E}f(\mathbf{v}^{t})-\frac{\alpha}{2}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|^{2}-\left(\alpha-\alpha^{2}L\right)\mathbb{E}\|{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}$
$\displaystyle+\frac{\alpha
L^{2}}{2}\mathbb{E}\|\mathbf{v}^{t}-\boldsymbol{\theta}^{t}\|^{2}+\frac{\alpha^{2}L\sigma^{2}}{n}$
(A46)

where $(a)$ is true due to the unbiasedness of the gradient estimate, in $(b)$
we use the quadrilateral identity, in $(c)$ we use the gradient Lipschitz
continuity.

Combining (A41) and (A46), we have

$\displaystyle\mathbb{E}[f(\mathbf{v}^{t+1})]\leq$
$\displaystyle\mathbb{E}[f(\mathbf{v}^{t})]-\left(\alpha-\alpha^{2}L\right)\mathbb{E}\|{\nabla}_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}-\frac{\alpha}{2}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|^{2}$
$\displaystyle+\frac{\alpha^{3}}{2}(1+\gamma^{2})L^{2}G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}+\frac{\alpha^{2}L\sigma^{2}}{n}.$
(A47)

When $\alpha\leq 1/L$, we have

$\frac{\alpha}{2}\mathbb{E}\|{\nabla}_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|^{2}\leq\mathbb{E}[f(\mathbf{v}^{t})]-\mathbb{E}[f(\mathbf{v}^{t+1})]+\frac{\alpha^{3}}{2}(1+\gamma)L^{2}G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}+\frac{\alpha^{2}L\sigma^{2}}{n}.$
(A48)

Applying the telescoping sum over iterations $t=1,\ldots,T$, we can get

$\frac{1}{T}\sum^{T}_{t=1}\alpha\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|^{2}\leq\frac{f(\boldsymbol{\theta}^{1})-f^{\star}}{2T}+\alpha^{3}(1+\gamma)L^{2}G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}+\frac{2\alpha^{2}L\sigma^{2}}{n},$
(A49)

so we have

$\frac{1}{T}\sum^{T}_{t=1}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|^{2}\leq\frac{f(\boldsymbol{\theta}^{1})-f^{\star}}{2T\alpha}+\alpha^{2}(1+\gamma)L^{2}G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}+\frac{2\alpha
L\sigma^{2}}{n}.$ (A50)

Since
$\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})-\nabla_{\boldsymbol{\theta}}f(\mathbf{v}^{t})\|\leq
L\|\boldsymbol{\theta}^{t}-\mathbf{v}^{t}\|$ and the upper bound of
$\|\boldsymbol{\theta}^{t}-\mathbf{v}^{t}\|$ shown in (A41), we have

$\frac{1}{T}\sum^{T}_{t=1}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}\leq\frac{f(\boldsymbol{\theta}^{1})-f^{\star}}{2T\alpha}+3\alpha^{2}(1+\gamma)L^{2}G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}+\frac{2\alpha
L\sigma^{2}}{n}.$ (A51)

Let $\alpha:=\frac{\sqrt{n}}{\sigma\sqrt{T}}$. We can get

$\displaystyle\frac{1}{T}\sum^{T}_{t=1}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}\leq$
$\displaystyle\frac{\left(f(\boldsymbol{\theta}^{1})-f^{\star}\right)\sigma}{2\sqrt{nT}}+\frac{3n^{2}}{\sigma^{2}T}(1+\gamma)L^{2}G^{2}\left(1+\frac{1}{\epsilon}\right)\left(G^{2}+\frac{\sigma^{2}}{n}\right)\frac{\lambda}{1-\lambda}$
$\displaystyle+\sqrt{\frac{1}{nT}}2L\sigma.$ (A52)

When $T$ is large, $1/T$ decreases faster then $\sqrt{1/T}$, so we have

$\displaystyle\frac{1}{T}\sum^{T}_{t=1}\mathbb{E}\|\nabla_{\boldsymbol{\theta}}f(\boldsymbol{\theta}^{t})\|^{2}\leq$
$\displaystyle\frac{\left(f(\boldsymbol{\theta}^{1})-f^{\star}\right)\sigma}{2\sqrt{nT}}+\frac{2L\sigma}{\sqrt{nT}}+\mathcal{O}\left(\frac{1}{T}\right).$
(A53)

which shows a linear speed-up w.r.t. $n$. ∎

###  D.3 Proof of Lemma 2

###### Proof.

Let $\mathbf{x}_{j}$ denote
$\mathbf{m}^{t}_{j}+\widehat{\nabla}_{\boldsymbol{\theta}}f_{\mathcal{B}_{j}}(\boldsymbol{\theta})$
for simplicity in this proof. Then, by leveraging the linear property of
CLT-$k$ operator, we have

$\displaystyle\left\|\textrm{CLT}^{k}_{i}\left(\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right)-\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2}$
$\displaystyle=$
$\displaystyle\left\|\frac{1}{n}\sum^{n}_{j=1}\textrm{CLT}^{k}_{i}(\mathbf{x}_{j})-\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2}\mathop{\leq}\limits^{(a)}\sum^{n}_{j=1}\frac{\gamma_{j}}{n}\left\|\mathbf{x}_{j}\right\|^{2},\forall
i,j.$ (A54)

where $(a)$ is true since
$\mathbb{E}\|\textrm{CLT}^{k}_{i}(\mathbf{x}_{j})-\mathbf{x}_{j}\|^{2}\leq\gamma_{j}\mathbb{E}\|\mathbf{x}_{j}\|^{2},\forall\mathbf{x}_{i},\mathbf{x}_{j}$

On the other side, we can expand $\|n^{-1}\sum^{n}_{j=1}\mathbf{x}_{j}\|^{2}$
directly by

$\displaystyle\left\|\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2}=\frac{1}{n^{2}}\left(\sum^{n}_{j=1}\|\mathbf{x}_{j}\|^{2}+2\sum^{n}_{i=1}\sum^{n}_{j\neq
i}\mathbf{x}^{T}_{i}\mathbf{x}_{j}\right).$ (A55)

Next, we try to have an upper of
$n^{-1}\sum^{n}_{j=1}\gamma_{j}\|\mathbf{x}_{j}\|^{2}$ by
$\|n^{-1}\sum^{n}_{j=1}\mathbf{x}_{j}\|^{2}$.

When $\mathbf{x}_{i}$ and $\mathbf{x}_{j}$ are positively correlated and
assume

$\frac{\mathbb{E}[\mathbf{x}_{i}^{T}\mathbf{x}_{j}]}{\mathbb{E}\|\mathbf{x}_{i}\|\mathbb{E}\|\mathbf{x}_{j}\|}\geq\kappa,\quad\forall
i,j.$ (A56)

Then, we can have

$\mathbb{E}[\mathbf{x}_{i}^{T}\mathbf{x}_{j}]\geq\kappa\min\\{\mathbb{E}\|\mathbf{x}_{i}\|^{2},\mathbb{E}\|\mathbf{x}_{j}\|^{2}\\},\quad\forall
i,j.$ (A57)

Since all the data follow the same distribution, we assume that the sizes of
the gradients at each work are very similar, i.e.,
$\mathbb{E}\|\mathbf{x}_{i}\|^{2}=\mathbb{E}\|\mathbf{x}_{j}\|^{2},\forall
i,j$. Thus, we can obtain

$\mathbb{E}\left\|\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2}\geq\frac{1}{n^{2}}\left((1+\kappa
n(n-1))\sum^{n}_{j=1}\mathbb{E}\|\mathbf{x}_{j}\|^{2}\right).$ (A58)

where $n\geq 2$.

Combining (A54), we can obtain

$\sum^{n}_{j=1}\frac{\gamma_{j}}{n}\mathbb{E}\|\mathbf{x}_{j}\|^{2}\leq\underbrace{\frac{n\sum^{n}_{j=1}\gamma_{j}}{1+\kappa
n(n-1)}}_{:=\gamma}\mathbb{E}\left\|\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2}.$
(A59)

Therefore, when $\kappa>(n\sum^{n}_{j=1}\gamma_{j}-1)/(n(n-1))$, we have

$\mathbb{E}\left\|\textrm{CLT}^{k}_{i}\left(\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right)-\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2}\leq\gamma\mathbb{E}\left\|\frac{1}{n}\sum^{n}_{j=1}\mathbf{x}_{j}\right\|^{2},\forall
i$ (A60)

so that $\gamma<1$. ∎

###  D.4 Connections between theoretical proofs and experiments

We provided the following table to explain section 3’s main results and
connected them to other parts of paper. For Remark 4, linear speedup refers to
that when $T$ is large enough, $1/\sqrt{nT}$ leads convergence rate. As worker
number $n$ increases, required iteration $T$ linearly decreases to achieve the
same convergence [14]. Our theorem 1 shows this; indicates its applicability
in distributed training.

|  Lemma1: contraction property |  Lemma2: contraction in distributed setting |  Theorem1: ScaleCom’s convergence rate same as SGD ($1/\sqrt{T}$)
---|---|---|---
Intuition |  Higher correlation between workers brings CLT-$k$ closer to true top-$k$ |  Require positive correlation between workers in distr. setting |  Ideally ScaleCom’s noise does not impact final conv. results
Connect to exp. |  Fig.2 and 3 show high correlation so our contraction is close to true top-$k$ |  Fig.2 and 3 show positive correlation between workers |  Table 1,2 (Fig4,5) verified ScaleCom’s convergence same as baseline
|  |  |

##  Appendix E Experimental Details

Our standard batch size experiments are performed on IBM servers where each
node is equipped with 2 Intel Xeon E5-2640 V4 processors at 2.40 GHz, each
having 10 cores, and 16 NVIDIA Tesla V100 GPUs 16 GB. The large batch size
experiments are performed on IBM DCS supercomputer with 268 nodes. Each node
is equipped with 2 IBM Power 9 processors clocked at 3.15 GHz. Each processor
contains 20 cores with 4 hardware threads (160 logical processors per node).
Within the total cluster, 252 nodes each contains 6 NVIDIA Tesla V100 GPUs 32
GB, and other nodes each contains 4 NVIDIA Tesla V100 GPUs 16 GB. All nodes
are connected with EDR Infiniband.

The software platform is based upon PyTorch [2] and we implement in-house
communication scheme with the compression method defined Algorithm 1. For
distributed training, instead of using PyTorch DistributedDataParallel (DDP)
[3], we implement our own scheme on top of OpenMPI (v3.0.2) and NVIDIA NCCL.
Our communication scheme initiates process group through MPI, and uses
customized average_gradients function defined in our communication package to
compress and average the gradients (through both NVIDIA NCCL and MPI). The
average_gradients function does the following: In each iteration, we
sequentially select a leading worker in a cyclical order. The leading worker
does chunk-wise quasi-sorting [4], and obtains its local top-k indices, that
are broadcast to the other workers. Each worker follows the indices to
compress its own local error-feedback gradients (the sum of computed gradients
and local memory). Then, the selected gradients are averaged across workers
through all-reduce function for model updates. Figure A2 is a demonstration of
ScaleCom on MNIST dataset.

Figure A2: Demonstration of ScaleCom with a simple model on MNIST dataset. The
model contains two convolution layers and two linear layers. For
demonstration, only the first 8 gradients of iteration 0 are printed here. In
iteration 0, leading worker is ’cuda:1’. It selects index 0 of the first chunk
and index 1 of the second chunk from chunk-based sorting, and sends them to
the other three workers. All four workers used the selected indices of
’cuda:1’ for error-feedback gradients compression.

###  E.1 ResNet34/CIFAR10

We adapt a PyTorch implementation of ResNet34 and the standard pre-processing
of CIFAR10 dataset [5]. We use learning rate of 0.1 with decay 0.1 at epoch 82
and 122. We use non-Nesterov SGD optimizer with momentum of 0.9. For the
standard batch size experiment, we use 32 per-worker batch size and 4 workers.
The test accuracy at epoch 160 is 93.78% for baseline without compression.
Following our compression guideline in Section 4 and with 5 epochs of
compression warmup, the test accuracy achieves 93.98% at epoch 160 with
compression rate of 92X. Note the first convolution layer is not compressed as
it is very sensitive to compression. We keep per-worker batch size constant at
32 and increase the number of workers to 32 for CIFAR10 large batch size
experiment. We linearly warm up learning rate from 0.1 to 0.8 in the first 5
epochs, and follow the same learning rate decay rule as in the standard batch
size setting. The test accuracy achieves 93.75% at epoch 160 when compression
is not applied. Keeping all the hyper-parameters the same as no-compression
experiment, ScaleCom achieves test accuracy of 93.36% with 10 epochs of
compression warmup without applying low-pass filtering ($\beta$=0). Training
curves are shown in Figure A3.

Figure A3: (a) Standard and (b) large batch size training curves with ScaleCom
on ResNet34 for CIFAR10 dataset.

###  E.2 ResNets/ImageNet

We adapt ResNets v1 including ResNet18 and ResNet50 from the models of
torchvision [6] and the standard pre-processing of ImageNet ILSVRC2012 dataset
[7]. We use learning rate of 0.1 with decay 0.1 at epoch 30, 60, and 90. We
use non-Nesterov SGD optimizer with momentum of 0.9 and weight decay of 1e-4.
In the standard batch size experiment, we use 32 per-worker batch size and 8
workers. The baseline test accuracy at epoch 100 is 70.482% and 76.442% for
ResNet18 and ResNet50 respectively. With ScaleCom and 5 epochs of compression
warmup, ResNet18 achieves test accuracy of 70.172% with compression rate of
112X, and ResNet50 achieves 75.988% with compression rate of 96X. Our large
batch size setting keeps per-worker batch size constant at 32 and uses a total
of 64 workers, achieving 2048 total batch size. We linearly warm up learning
rate from 0.1 to 0.8 in the first 5 epochs of training. Without compression,
ResNet18 and ResNet50 achieve test accuracy of 70.285% and 76.473% at epoch
100. Hyper-parameters for compression experiments are kept the same as the no-
compression experiments. For ResNet18, with 5 epochs of compression warmup, if
no filtering is applied, test accuracy is 68.121% at epoch 100, showing about
2.164% degradation. If $\beta$ is set to 0.1 for low-pass filtering, ScaleCom
achieves 69.879% test accuracy. $\beta$=0.1 low-pass filtering helps improve
test accuracy by 1.758% for ResNet18. For ResNet50, with 10 epochs of
compression warmup, we achieve test accuracy of 75.641% when $\beta$ is set to
0.1. We then further tune $\beta$ by increasing it to 1 at epoch 60, and
achieves a better accuracy of 75.895%. The reason behind this is as we decay
learning rate over the training process and low-pass filter the gradients, the
network becomes less responsive in the later epochs. To prevent that, we
increase $\beta$ to 1 at epoch 60 for ResNet50. Training curves at shown in
Figure A4.

Figure A4: Training curves with ScaleCom for ImageNet dataset: (a) standard
batch size on ResNet18 (b) large batch size on ResNet18 (c) standard batch
size on ResNet50 and (d) large batch size on ResNet50.

###  E.3 MobileNetV2/ImageNet

We adapt a PyTorch implementation of MobileNetV2 and the standard pre-
processing of ImageNet ILSVRC2012 dataset [8]. We use learning rate 0.0045
with 0.98 decay each epoch. We use RMSPROP optimizer with $\epsilon$ 1.0,
momentum 0.9, and weight decay 4e-5. We use the full size model with width-
multiplier 1. In the standard batch size experiment, we use 32 per-worker
batch size and a total of 8 workers. The baseline test accuracy achieves
71.644% at epoch 250. Following compression guidelines and with 5 epochs of
compression warmup, ScaleCom achieves test accuracy of 71.524% with
compression rate of 155X. In the large batch size experiment, we scale the
number of workers to 64 workers while keeping per-worker batch size at 32,
achieving 2048 total batch size. We linearly warm up learning rate from 0.0045
to 0.036 in the first 5 epochs, and then follow the same decay factor of 0.98
per epoch. Keeping the other hyper-parameters the same as in the standard
batch size settings, we achieve test accuracy of 71.487% at epoch 250 without
applying compression. Then following the same compression guidelines and with
5 epochs of compression warmup, if no filtering is applied, test accuracy is
70.976%. With $\beta$=0.1 low-pass filtering, ScaleCom achieves 71.014%.
Training curves are shown in Figure A5

Figure A5: (a) Standard and (b) large batch size training curves with ScaleCom
on MobileNetV2 for ImageNet dataset.

###  E.4 Transformer/WMT14 En-De

We adapt the implementation of FairSeq [9] and use the Transformer Base model
for the WMT14 En-De translation task. We use Adam optimizer. BLEU score is
calculated at each epoch with beam 4, length penalty of 0.6, and remove bpe
option after compound splitting [10]. In the standard batch size experiment,
learning rate is 0.0007 and we use 500 updates for warmup. Per-worker batch
size is 2250 and update frequency is 2. Baseline achieves BLEU score of 27.64
at epoch 40, and ScaleCom achieves 27.27 with compression rate 47X following
our compression guidelines. To demonstrate the robustness of ScaleCom, we
apply a more aggressive compression rate of 65X, and achieve BLEU score of
27.24. In the large batch size experiment, the number of workers is increased
to 64 while per-worker batch size kept the same. We use 4000 updates for
learning rate warm up to 0.0007. Without compression, we achieve 27.79 BLEU
score at epoch 40. Following our compression guideline, if no filtering is
applied, we observe degradation, getting 25.65 BLEU score. With $\beta$=0.1
filtering, we achieve 28.03 with compression rate of 47X, showing big
improvement in BLEU score. A more aggressive compression is applied with 115X
compression rate, and BLEU score 27.59 is achieved. Training curves are shown
in Figure A6.

Figure A6: (a) Standard and (b) large batch size training curves with ScaleCom
on Transformer Base model for WMT14 En-De translation task.

###  E.5 LSTM/SWB300

We adapted the acoustic LSTM model of IBM speech [11] that contains 4 bi-
directional LSTM layers and 2 fully-connected layers in the main network; each
LSTM layer contains 1024 cells with 512 on each direction. On top of the LSTM
layers, there is a linear bottleneck layer with 256 hidden units followed by a
SoftMax output layer with 32K units corresponding to continuous density hidden
Markov model (CD-HMM) states. We used input dimensions 140 and 260 in the
standard and large batch size experiments respectively. For large batch size
training, our learning rate schedule follows [12]; the learning rate starts at
0.1 and gradually reaches 0.8 (increase 0.07 in each epoch). Then learning
rate starts to decrease by the ratio of $1/\sqrt{2}$ in each epoch. For
standard batch size, we follow [11], which keeps learning rate as 0.1 for the
first 9 epoch (annealing); then decrease $1/\sqrt{2}$ in each epoch. In
standard batch size, per-worker batch size is 32 and 4 workers are used (total
batch size=128). For large batch size experiments, per-worker batch size
increases to 128 and 12 workers are used (total batch size=1536). LSTMs are
unrolled 21 frames and trained with non-overlapping feature sub-sequences of
that length. The 300-hour switchboard data set (SWB300) is used to train
network. The training set consists of 262 hours of Switchboard 1 audio with
transcripts. The test set is the 2.1-hour switchboard (SWB) data from 40
speakers. Based on our conservative compression ratio rules (described in
section 4), 400X and 100X compression rate are selected for standard and large
batch size respectively and 2 epoch warm up (no compression) are applied.
Training curves are shown in Figure A7(a) and (b).

We evaluated word error rate (WER) at epoch 20. 4-gram language models (LMs)
are used in decoding and acoustic weight is chosen as 0.05. In standard batch
size, our baseline (no compression) obtains 10.4% WER on SWB300 test set and
17.9% on the CallHome (CH) test set. ScaleCom reaches 10.1% WER on SWB300 and
17.9% on CH test set. For large batch size experiments, our baseline achieves
9.9% WER on SWB300 test set and 17.6% on the CH test set; ScaleCom reaches
10.0% WER on SWB300 test set and 17.6% on the CH test set.

Figure A7: Training curves with ScaleCom on 4-bidirectional LSTM acoustic
model for 300-hour switchboard (SWB300) dataset: (a) standard and (b) large
batch size.

##  Appendix F Performance Benefits with ScaleCom

In this section, we quantify the improvement in end-to-end training time
achieved by ScaleCom on large-scale deep learning systems. To this end, we
considered a distributed training system comprised of multiple accelerator
chips connected to a parameter server. Each accelerator chip is comprised of
multiple cores with private scratchpad memory, delivering $\sim$100 TFLOPS
FP16 peak performance. To demonstrate the scalability benefits of ScaleCom, we
study systems with varying number of accelerator chips from 8 to 128
increasing the peak compute from 800 TFLOPS to 12.8 PFLOPS. Further, we also
analyze performance impact under two different accelerator $\leftrightarrow$
parameter server bandwidths _viz._ 32 GBps (PCIe Gen4) and 64 GBps (PCIe
Gen5).

We utilized the systematic performance analysis framework for DNN accelerators
presented in [35] to estimate performance. Given a system configuration
(compute throughput, memory capacity, interconnect topology and bandwidth),
the framework analytically explores possible ways to map DNN computations on
to the accelerator system. It systematically captures computations executed in
each chip and data communicated through each interconnect link using a
bandwidth-centric performance model to provide an estimate on performance. The
key optimizations explored by the framework include the choice of data vs.
model parallelism, data-structure placement in on-chip memory to optimize
intra- and inter-layer data reuse, and software pipelining to overlap
communication with compute. In addition to conventional uncompressed gradient
reduction scheme, the framework models performance under 2 different gradient
compression schemes _viz._ Local top-$k$ [1] (which encounters the gradient
build-up problem outlined in Section 1) and ScaleCom.

###  F.1 End-to-end Training Performance

Figure A8 shows the normalized performance improvement in end-to-end training
time using different gradient compression schemes for the ResNet50 (ImageNet)
benchmark as the number of workers in the system and the accelerator-to-
parameter server bandwidth are varied. The performance is normalized to the
case where no compression is employed with 8 workers and 32 GBps bandwidth. We
present performance under _strong scaling_ _i.e._ , the minibatch size is
increased proportional to the number of workers keeping minibatch/worker
constant (=8 in this experiment). To provide a fair performance comparison, we
assume the same gradient compression ratio of 112$\times$ for both local
top-$k$ and ScaleCom gradient compression schemes.

Figure A8: Speedup using different gradient compression schemes for Resnet50
DNN

As expected the conventional uncompressed gradient reduction scheme scales
quite well with the number of workers because the gradients are reduced in the
parameter server and so the accelerator to parameter server communication cost
remains constant. We observe about 1.35$\times$ improvement in performance
when the bandwidth is increased from 32 to 64 GBps. Given the high compute
throughput of the accelerator chip, the communication between the parameter
server and accelerator is the key bottleneck to performance accounting for
$\sim$55% of the total execution time. The gradient compression schemes are
targeted to address this bottleneck yielding significant performance gains.
Local top-$k$ scheme achieves about 1.92$\times$ performance improvement
relative to the conventional scheme especially when the number of workers is
small. However, with increase in the number of workers, each worker could
select a different gradient index during compression, resulting in a linear
increase in the amount of data communicated between the parameter server and
the accelerators. This leads to the overall performance benefits due to
compression dropping from 1.92$\times$ with 8 workers to 1.2$\times$ with 128
workers. In contrast, ScaleCom overcomes the gradient-build up issue, by
forcing all workers to select the same set of indices during compression,
albeit incurring a small overhead for communicating the indices beforehand.
This results in 2$\times$ speedup relative to the conventional scheme, which
is maintained independent of the number of workers. With 128 workers, ScaleCom
achieves 1.65$\times$ and 1.37$\times$ performance gain over local top-$k$ at
32 and 64 GBps, respectively.

###  F.2 System Performance in different mini-batch sizes and worker numbers

Appendix-F.1 shows ScaleCom’s scalability in system performance; more details
here for practical applicability in different per-worker mini-batch sizes and
worker numbers. The fraction of time expended in gradient/weight communication
limits the overall end-to-end training time improvement achieved with
ScaleCom. As shown in Figure A9a, when minibatch/worker is increased from 8 to
32, the communication time (as a fraction of total time) decreases from 56% to
20%. Consequently, for a 100 TFLOPs/worker peak compute capability, ScaleCom
achieves total training speedup of 2$\times$ to 1.23$\times$ even with
$\sim$100$\times$ compression. Fraction of communication time grows with
increase in peak TOPs (100 to 300), resulting in speedup of 4.1$\times$ to
1.75$\times$. The key trait of ScaleCom is its _performance scalability to
larger number of workers_ independent of minibatch/worker. As shown in Figure
A9b, the communication cost of prior top-k approaches increase linearly with
number of workers, whereas ScaleCom remains constant. ScaleCom offers
scalability even with large number of workers independent of per-worker
minibatch size and effectively reduces communication cycles (< 3% of total
training time) leaving the training throughput to be limited by the
computation efficiency.

Figure A9: Staked bar chart for Resnet50 DNN: (a) different per worker mini-
batch sizes and (b) different worker numbers

## References

  * [1] N. Strom, "Scalable distributed DNN training using commodity GPU cloud computing", in Sixteenth Annual Conference of the International Speech Communication Association, 2015.
  * [2] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, "PyTorch: An imperative style, high-performance deep learning library," in Advances in Neural Information Processing Systems pp. 8024-8035, 2019.
  * [3] L. Shen, "Pytorch toturial: GETTING STARTED WITH DISTRIBUTED DATA PARALLEL", in Pytorch website: https://pytorch.org/tutorials, 2020.
  * [4] P. Kipfer, "Chapter 46. Improved GPU Sorting",  NVIDIA blog, 2005.
  * [5] K. Liu, "Train CIFAR10 with PyTorch", in https://github.com/kuangliu/pytorch-cifar, 2020.
  * [6] "Torchvision github", in  https://github.com/pytorch/vision/tree/master/torchvision/models, 2020.
  * [7] "PyTorch ImageNet github", in https://github.com/pytorch/examples/blob/master/imagenet, 2020.
  * [8] J. Lin, "PyTorch open source github: A PyTorch implementation of MobileNetV2", in https://github.com/tonylins/pytorch-mobilenet-v2, 2018.
  * [9] M. Ott, S. Edunov, A. Baevski, A. Fan, S. Gross, N. Ng, D. Grangier and M. Auli, "fairseq: A Fast, Extensible Toolkit for Sequence Modeling", in Proceedings of NAACL-HLT 2019: Demonstrations, 2019.
  * [10] M. Ott, url=https://gist.github.com/myleott/da0ea3ce8ee7582b034b9711698d5c16
  * [11] X. Cui, V. Goel, G. Saon, "Embedding-based speaker adaptive training of deep neural networks," arXiv preprint arXiv:1710.06937, 2017.
  * [12] W. Zhang, X. Cui, U. Finkler, G. Saon, A. Kayi, A. Buyuktosunoglu, B. Kingsbury, D Kung, M. Picheny, "A Highly Efficient Distributed Deep Learning System For Automatic Speech Recognition," arXiv preprint arXiv:1907.05701, 2019.
  * [13] S. Venkataramani, V. Srinivasan, J. Choi, P. Heidelberger, L. Chang, K. Gopalakrishnan, "Memory and Interconnect Optimizations for Peta-Scale Deep Learning Systems," in 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC), pp. 225-234, IEEE, 2019.
  * [14] X. Lian, Zhang, C., Zhang, H., Hsieh, C. J., Zhang, W., Liu, J., "Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.," in Advances in Neural Information Processing Systems, pp. 5330-5340. 2017.