Contractive error feedback for gradient compression
Authors: Bingcong Li
Shuai Zheng
Parameswaran Raman
Anshumali Shrivastava
Georgios B. Giannakis
Venue: ICLR 2022 Submitted (2022)

Abstract: 
On-device memory concerns in distributed deep learning are becoming more severe due to i) the growth of model size in multi-GPU training, and ii) the adoption of neural networks for federated learning on IoT devices with limited storage. In such settings, this work deals with memory issues emerging with communication efficient methods. To tackle associated challenges, key advances are that i) instead of EFSGD that inefficiently manages memory, the sweet spot of convergence and memory usage can be attained via what is here termed contractive error feedback (ConEF); and, ii) communication efficiency in ConEF should be achieved by biased and allreducable gradient compression. ConEF is validated on various learning tasks that include image classification, language modeling, and machine translation. ConEF saves 80% – 90% of the extra memory in EFSGD with almost no loss on test performance, while also achieving 1.3x – 5x speedup of SGD.

Under review as a conference paper at ICLR 2022
CONTRACTIVE ERROR FEEDBACK FOR GRADIENT COMPRESSION
Anonymous authors Paper under double-blind review
ABSTRACT
On-device memory concerns in distributed deep learning are becoming more se- vere due to i) the growth of model size in multi-GPU training, and ii) the adoption neural networks for federated learning on loT devices with limited storage. such settings, this work deals with memory issues emerging with communication efficient methods. To tackle associated challenges, key advances are that i) instead of EFSGD that inefficiently manages memory, the sweet spot of convergence and memory usage can be attained via what is here termed contractive error feed- back (ConEF); and, ii) communication efficiency in ConEF should be achieved by biased and allreducable gradient compression. ConEF is validated on various learning tasks that include image classification, language modeling, and machine translation. ConEF saves 80% 90% of the extra memory in EFSGD with almost no loss on test performance, while also achieving 1.3x- 5x speedup of SGD.
INTRODUCTION
Many modern machine learning tasks can be cast as an optimization problem
1 N
min f(x) xERd
Be
BenD [fxx([((x [)]
(I)
N
Typically, the possibly nonconvex loss function f((x.) is continuously differentiable with respect to (w.rt.) x. We assume that f* > - is a global minimum of (T). In this work, we will focus on training neural networks (NN) by solving ① two important scenarios: i) data parallelism in multi-GPU setting, and ii) federated learning where clients could be edge devices such as smart phones. In both cases, N denotes the number of workers (GPUs or devices) and f no smaller than 0 given common choices of loss functions such cross entropy and mean square.
While training NNs is a resource-humee -untery task, bandwidth and memory prevent us from fully har- vesting the merits of parallelism. Limited bandwidth slows down the speed of information (e.g., gradients) exchange among workers. In multi-GPU settings, is observed that communication of gradients becomes bottleneck that significantly drags down the training speed. While for feder- ated learning, the system capacity is usually confined by communication latency between the server and workers. Memory constraints are less studied compared with bandwidth (Sohoni et al. 2019) However, given the trend of an increasing model size in both computer vision and natural lang language processing, e.g.. ViT (0.6B) (Dosovitskiy al. 2020), Megatron- (8.3B) (Shoeybi et al. 2019). T5 (11B) (Raffel et al.) 2019), it evidences that memory is becoming an unavoidable constraint for training large models in current GPU generation with 16/32GB memory. For federated learning, is also necessary to reduce the memory footprint on workers especially for those IoT applications.
In this work, we will focus on the parsimonious setting, jointly dealing with limited bandwidth and memory. The priority is still communication efficiency for speeding up training time, otherwise one can simply rely on SGD with almost no additional memory consumption. Many existing works are unable to cope with such a challenging problem because memory is not carefully taken care of.
Communication efficiency. A vell-documented approach to alleviate communication bottleneck is to compress the (stochastic) gradients such that training can be made faster with reduced overhead (Seide et al. 2014; Alistarh et al.] [0177] Karimireddy et al. 2019). Depending on whether the gradient compressor biased, these schemes categorized as follows.

---

Under review as a conference paper at ICLR 2022
Unbiased compressors maintain the unbiasedness of stochastic gradients the price of enlarged
variance. For example, uniform quantization of stochastic gradients is studied in QSGD (Alistarh)
et al. 2017). A concurrent work (Wen et al. (017)) focuses special case of QSGD by quantizing
each entry of the gradient into [+1,0]. Other variants include natural quantization (Horvath et al.
2019), non-uniform quantization (Ramezani-Kebryy et al. (02T) and adaptive quantization (Faghri
ct al. 2020). Another route to obtain an unbiased compressor is through (scaled) gradient sparsi-
fication (Wangni et al. 2018) its generalized form, atomic decomposition (Wang et al. 2018
However, such methods may be practically slow with performance degradation (Vogels et al.
2019)
Biased gradient compressors, on the other hand, have been more successful in practice since not only do they support more impressive compression ratio, but also a test accuracy comparable with SGD can be obtained in many scenarios. Examples of such compressors contain top-k or (unscaled) random-k sparsification (Lin et al. 2018 Alistarh et al. 2019), signSGD (Bernstein et al. 2018a b and PowerSGD (Vogels et al. 2019). Due to the bias, such compressors typically rely on error feedback (EF) schemes ensure convergence (Stich et al., 2018 Karimireddy et al.. 2019).
Memory concerns in communication efficient methods. Memory concerns are highly entangled with communication efficiency in distributed training. On the one hand, memory footprint can be alleviated through a smaller batchsize (Krause et al. 2016 Spring et al., (019),, leading to increased iterations as well as communication rounds per epoch. Hence, communication efficient methods are particularly useful for accelerating training time in such cases. On the other hand, existing communication efficient methods are challenged by limited memory due several reasons. First, a smaller batch size, which enlarges the variance, degrades the applicability of unbiased gradient compressors. Confirmed in our experiments, the exploded variance typically calls for small step size which decelerates convergence. Unbiased gradient compressors such quantization, are also hindered by the need of AllGather (Xu et al.) 2020), since peak memory proportional to the number of workers is required. This renders them inefficient for the parsimonious setting, especially when the number of workers is large. Memory is also not handled well in methods with biased gradient compressors due the need of error feedhack, where additional memory the same as model size has to be consumed to keep track of accumulated compression error. Note that although no memory footprint is introduced in Local SGD (Stich 2019), it suffers from variance blown problem as well. More importantly. local SGD cannot be integrated with ZeRO (Rajbhandari et al. (2020). state-of- the-art method for coping with limited memory, due partitioned optimizer states among workers.
In this work, we will focus on EF-based methods because of the capability of adopting biased gradient compressor, which typically contractive thus more robust to the gradient variance in a small batchsize setting. The additional memory consumption of EFSGD over SGD is the local error vector, which is delicate and critical for ensuring convergence. Meanwhile, the designed manner for memory efficiency can only come with lightweight and negligible runtime overhead, otherwise it violates the ultimate goal of communication efficient methods. Contractive error feedback is thus introduced to address these challenges. In nutshell, our contributions can be summarized as:
To the best of our knowledge, this is the first work that systematically studies memory concerns in communication efficient methods. Contractive error feedback (ConEF), is introduced to effec- tively manage memory given the preference of allreducable and biased gradient compressor.
Convergence of ConEF is established. Our theoretical results suggest a tradeoff between memory efficiency and faster convergence, and ConEF finds the sweet spot.
ConEF is capable of saving 80% - 90% additional memory of EFSGD various learning prob- lems such as image classification, language modeling, and machine translation. With almost the same runtime of EFSGD, ConEF achieves 1.3x 5x speedup over SGD. Though test perfor- mance slightly drops on smaller models, the proposed method is more useful and reliable for larger networks where improved test accuracy over EFSGD is observed.
Notation. Bold lowercase (uppercase) letters denote vectors (matrices); ||x|| stands for lg norm of x; and (x, y) denotes the inner product of x and y. In addition, we use [x] (X]i,)) to denote the i-th entry of vector (i. j-th entry of matrix X).
2 PRELIMINARIES
This section briefly recaps EFSGD (Stich et al. 2018 Karimireddy et al. 2019) listed under Alg. We use gi to denote the stochastic gradient at x, on worker é, and assume that the stochas- tie gradients mutually independent among different workers per iteration. In line 5, the scaled
2

---

Under review as a conference paper at ICLR 2022
Algorithm EFSGD
Algorithm 2 ConEF
1: Initialize: Xn E _2 ej = 0 R Vi,
1: Initialize: Xo E IR 0 E R Vi,
2: for f 0, 1...., T do
......,. 1....... for == 0,
do
3: assert = x; for every worker i
3: assert X x; for every worker
4: for worker i ,,.... N parallel do
4: for worker = I,..., in parallel do
5:
pj 1/1: + ej
5:
p 7/B: 1j
6:
A; = Q(pi)
6:
A Q(pi)
7:
A, Aggregate A (, Vi)
7:
A, Aggregate( A Vi)
8:
X = x; A
8:
X = X, A
9:
e/11 P A
9: e C(p) A
10: end for
10: end for
end for
11: end for
stochastic gradient is augmented via accumulated compression error c₁, then compressed and communicated. There is no restriction to the biasedness of gradient compressor Q. Examples of Q include (scaled) sign, random/top-ks, and powerSGD. The "aggregate" in line 7 refers to A N E, A and the compression eπror eit1 is recomputed in line 9 after updating model X₁. More implementation details on communication of gradients, and reasons for the preference of AllReduce, are deferred to Apdx. A. to save space.
Besides the widely appreciated allreducable gradient compressors, those biased ones more tai- lored for settings where the inclination to rely on smaller batchsize for memory saving. This is because biased gradient compressors
usually contractive; tion 4 However, due to the need of eтror feedback to ensure convergence, the additional memory consumption of et confine the applicability of biased compressors as well as EFSGD in parsi- monious setups, and this issue is somehow omitted by existing works. Other error feedback variants, e.g., (Wu et al. (2018) Basu al. 2019 Xu al. [021 Richtárik et al. [202I), also rely on additional vectors for the compression error, hence may benefit from the proposed technique as well.
more details shortly in Assump-
MEMORY SAVING VIA CONTRACTIVE ERROR FEEDBACK
To endow EFSGD with memory efficiency, contractive error feedback is introduced in this section. The key idea is to apply another compressor C on the error vector e such that the memory footprint can be mitigated. The proposed method is summarized Alg. 2 where the name contractive error feedback (ConEF) originates from the fact that the error vector is represented in its compressed format. Note that the encoding and decoding of compression in Alg. 2 are omitted for notational convenience. Q and C are adopted to denote the gradient and error compressors, respectively, to highlight their different roles. The gradient compressor Q is general and biased one is more rec- memory out. An unbiased error compressor
ommended for small batchsizes that can squeeze C is preferable since it is helpful for generalization as we shall discuss later in Section Moreover, the implementation of C has to be lightweight avoid slowing down runtime. We will focus theoretical properties first, and practical guidances for the choice of C are deferred to Section
3.1 CONVERGENCE
Convergence of Alg. 2 is established in this subsection under standard assumptions for communi- cation efficient algorithms in the distributed setting (Alistarh et al. [2017, Karimireddy et al.) 2019
Stich et al. 2018 Zheng et al.) 2019 Abdi & Fekri 2020; Basu et al. [219]]4 Alistarh et al.) 2019).
Assumption 1. The objective function f R - R has L-Lipchitz continuous gradients; that is, (r/(x)-V[(y)) & [ilx-xx f1l xx, TRd_
Assumption 2. The stochastic gradient g, is unbiased with bounded variance F3. g x = (xx))) and E[]lg] [x(x))]] < o². The gradient is also upper bounded E[[[ (xx) G².
Assumption 3. (Unbiased error compressor C). For any given x, E[[(x))xxi = x. In addition, there exist 0 0 such that [x][[((x) xx|||x] (|
Assumption 4. (Contractive gradient compressor Q). For any given there exists ō E (0,1) such that [()) - x|| < 6|
Holding true for many allreducable and biased gradient compressors such as unscaled random- (block)-k and powerSGD, Assumption implies contractivity the compression error is always smaller than the norm square the compressed vector. Such compressors are more preferable when working with small batchsizes (for memory saving) since they do not amplify the gradient variance
3

---

Under review as a conference paper at ICLR 2022
explained in Apdx. A.2 and (Stich et al. 2018). Unbiased compressors satisfying Assumption
are usually not allreducable; see also Apdx.
A.2 The convergence of Alg. 2 is established below.
Theorem 1. Suppose that Assumptions 7
hold and I is large. Choosing rj = O UVTYN+TU/B
Alg. guarantees that
[(IV so( 50( [[((x))) - ++++ + (o² + (9) ) +0 60(0² + G3)
VNT
VNT
The dependence on N demonstrates that linear speedup is achieved by ConEF. The second term in the right hand side of 2 is the additional error term incurred by compression. Next, we compare it with existing works to gain deeper understanding of ConEF. Upon relating Theorem with EFSGD (Karimireddy et al. 2019), the price paid for memory efficiency can be clearly visualized. Since only the single worker case is considered in the EFSGD paper, we let N 1 in Theorem for it is observed that
fair comparison. From the additional error term of EFSGD, i.e., O 0(" ConEF converges slower. However, ConEF still benefits from the locally compressed error vector when further compared to QSGD which does not employ error feedback schemes (Alistarh et al, 2017). Suppose that Q is unbiased with Assumption 3 satisfied, then the emror term in QSGD is [1+0)("* Therefore, ConEF improves the dependence on l over QSGD. In addition, The- VNT
orem is also tighter than (Horváth Richtárik 2020) since their error term is O (1+00
VNT ConEF finds the sweet spot. The comparisons above suggest tradeoff between memory efficiency and a fast convergence. QSGD is at one extreme where no extra memory is needed at the price of slower convergence due the blown variance introduced by unbiased gradient compressors. Note also that in general biased gradient compressors cannot be applied in QSGD. EFSGD is at another extreme, where the extra memory consumption induced by ef with the benefit of small error term in the convergence rate. Our proposed Alg. 2 livess in between EFSGD and QSGD, it saves memory compared to EFSGD, but incurs an error term smaller than QSGD yet larger than EFSGD.
3.2 IMPROVED CONEF
In this subsection, show that when Q (or C) is accurate, the dependence on 6 (resp. d) in Theorem [ can be improved. The basic idea is to apply contractive eтror feedback on top of contractive error feedback such that the compression eтror can be further re- duced. The resultant algorithm, improved ConEF (iConEF), is summarized in Alg. 3 Depending on whether Q is used twice, there are two versions of iConEF as marked in lines - 13.
Algorithm iConEF
Initialize: xo, e 0, q 0,
2: for t = 0, I....,
do
3:
assert x; x for every worker
4:
for worker i = 1...., N in parallel do
P = 7g; + +
6:
A = 2(p:)
A. = (ggregate(Ai,11) Vi)
8:
Xx+1 X, A,
9:
if version then:
10:
c4+ C(p)
)
iConEF-vl
Equipping with accurate C with 0 < 1, the compression error can be reused to re- tain performance. Mathematically. this error P - A e is once again compressed
11:
else:
12:
e Q(p:
iiConEF-v2
13:
end
14:
4'41 C(p A
el e
and added back to Pi+1 in the next iteration
15: end for
to reduce the variance of (0i=1 + q'+1); see
16:
end for
20 However, this approach might require
to store both ē/+1 and q'+1, thus less efficient in terms of memory consumption compared to Alg.
2 with the exception of cases where C is linear compressor such as count sketch.
Theorem 2. Suppose that Assumption 3 holds with S 1. Given Assumptions
7 2
and and
choosing 17 O UVT/N+TVS)> iConEF-vl guarantees that
R [[VS(()) O (oRP)=/O(/U
(L1((0)) - 1*) + (0" +G)
(
602 + G2) + +0
T
VNT
VNT
The 8² in the last term tightens Theorem sshowasiing the benefit of the third compressor. Examples of accurate C satisfying 0 < 0 < include quantization working in "dense regime" (Alistarh)
4

---

Under review as a conference paper at ICLR 2022
al. 2017). In particular, when the quantization level is chosen also that it Is possible to encode a compressed vector with less than 3.44d 32 bits (Alistarh et al, 2017 Lemma A.6). This means the memory reduction is almost 90%. Another example natural compression that can offer at least 3.5x memory saving with 0 < (Horvath et al. 2019).
2vd, we have 0 == Note
Similarly, when Q satisfies Assumption 4 which amounts to most of commonly adopted biased gradient compressors with 5 < 1, the dependence on 5 can be improved through iConEF-v2.
Theorem 3. Suppose that Assumptions 7 4 hold. Choosing O
AITT/N+TU/S ) iConEF-v2
guarantees that
T-1
E [[[Vf(x)11] & =0 ( - ff* +02
l0 VNT
+ )
180((02 2 + +G9)
Σ
VNT
4 A CLOSER LOOK AT ERROR COMPRESSORS
Previous sections have coped with contractive error feedback in its general form. what follows, will discuss the error compressor C in detail gain more insights and practical guidances.
4.1 GENERALIZATION PROPERTIES
The merits of an unbiased C over a biased one come from generalization properties. To see this point, consider overparameterized least square problems (Wilson et al. 2017) as an example
min fxx
1 Ax - y
(3)
where A E Raxd with >> the data matrix and y E IRd denotes the labels. Since d is larger than the number of data samples n, this overparameterized problem has multiple global minima with zero loss collected in the set X : fxi (x) 0}. Define R(X) as the range of X. Given the fact that any stochastic gradient of (3) lies in R(A it is straightforward that SGD converges to point in Rí A when initialized well. is further shown that the solution SGD converges has smallest norm among X i.c., x arg min A (AAA)) ) This x* is also known the maximum margin solution, which Ieads to potential generalization benefits (Valiant) 1984, Cortes & Vapnik 1995). In fact, for problem (3) if the iterates of converging algorithm lie in R(A
finding the maximum margin solution is ensured (Karimireddy et al. 2019 Lemma 9).
EFSGD converges to point that is sufficiently close R(AT) (Karimireddy al. 2019 This gives the potential generalization benefit when adopting biased gradient compressors Q compared
with e.g., sign-SGD (Bernstein et al.) 2018a b). Next, show that such generalization merit is maintained in Alg. and its variants when C is unbiased.
Theorem 4. If Assumptions
/ 4 hold, initialized at xo E R(AT). ConEF ensures E [xx ef R(A T); moreover, iConEF-vl and v2 guarantee E E(x, Σ q -- R(AT).
This implies that X, is close the maximum margin solution at convergence. We are unable to obtain such a property for biased C. The potential generalization merits justify the unbiased choice for C.
Note that for ConEF, we have E e]]l <
E 1== = 0(7²).
4.2 CHOICES OF ERROR COMPRESSOR
Recall that a prudent error compressor for ConEF should: satisfy Assumption 3 and, ii) have lightweight implementation to avoid runtime overhead. Two representative examples, quantization and count sketch, will be discussed detail in this subsection.
4.2.1 QUANTIZATION
Quantization is large family of compression schemes. For the ease of presentation, here we only describe the basic version (Alistarh et al. (017). Given s uniformly distributed quantization levels in [0. 1]. this approach quantizes the i-the entry of as
C((c),) ||e|| sign((c).) ((e)))
5

---

Under review as a conference paper at ICLR 2022
e
10
W
#Past
PORCN
7
kggh
(a)
(b)
(c)
Figure 1: (a) An illustration of count sketch compressing the first 4 entries of ef- A collision is at
[$]2.5 (index starts with 1); (b) magnitude of e in EFSGD; (c) magnitude ej in partial EFSGD.
where (.) is random variable designed to ensure the unbiasedness of C((cl:). In particular, let integer / E [0, s] such that |[e| |ell [ + and then ((e].) ) is set to [+1 with probability [[e|
and g otherwise. Assumption 3 is naturally satisfied according to the proposition below.
Proposition (Alistarh er al. 2017) For any e, the quantization in (4) satisfies: i) E[C(c)] = e; ii) B[llC(e) e| I min d g2, Ō(s² dv bits in expectation to represent C(e).
yd Hell? and, iii) there exists encoding scheme that requires
When setting quantization level O(1), the memory saving is impressive since it only requires ((vd) bits for d-dimensional vector at the cost of additional implementation burden of e.g., Elias encoding. Stochastic quantization is also suitable for the error compressor in iConEF-vl since can ensure when s O(vd)
Other quantization approaches can also be applied as the error compressor. For instance, one can use int-quantization (Mishchenko et al. 2021), where a fp32 number is compressed into int8 or int and non-uniform quantization Sarnezani-Kebbyye et al. (02T) is also valid choice.
4.2.2 COUNT SKETCI
While quantization is straightforward to come up with, relies on bit operations for compression rather than working on float numbers directly. Therefore, we introduce count sketch (Charikar al., 2002) in this subsection, whose implementation is simply incrementing entries in matrix.
Count sketch compresses vector e by maintaining a matrix S of size v X w d, i... C(e) S. Both v and w are chosen according to some desirable accuracy guarantees discussed shortly. Count f1.2..... w) and random sign functions 8; : (1.2...., d} + {+1, -1 in i-th row of S. Count sketches leverage [e]p to update each row i of by incrementing (p) column by {:())))pp Compression of can obtained by updating with {(p, d p= see Fig. (a). To decompress and estimate [e]p from S, one needs ( Vi). Replacing median with mean also works, but typically median performs better. Count sketch satisfies Assumption 3 as shown in the following proposition. Proposition 2. CCharikar et al. 2002) Count sketch is unbiased, i.e., E[C(c)] c. With w O(22) and v = (log ), count sketch ensures l|e - C(e) S <||e|| with probability at least 1 - p.
sketch relies on hash functions h4 {1, 2, ......d. d}
calculate Median (p; (p)
Proposition 2 Spring et al. 2019) suggests that count sketch is unbiased. Using inequality ||a|| S
||al| < Vd|allec it is not difficult to verify |/ - C(e)]] < evd]jel|. Although count sketch satisfies a high probability variant of Assumption 3 with 0 = edd, works well our experimental studies with the recommendation of e = 1 or
3. Hence, this emor compressor is more practical relative to the theoretical bounds. Another useful property of count sketch is the lincarity, i.c., C(ei + e2) C(er) + C(ez). This is helpful since i) it opens the possibility to squeeze ē.+1 and 4:41 in iConEF-v1 to further reduce the memory consumption by adding these two count sketches; and ii) it eases
reset (Basu et al., 2019 Xie et al.) 2020), which synchronizes the local errors every a few iterations among all workers. The second merit is because count sketch is small in size and allreducable, and more this can be found in Apdx. G.4
Empirically, count sketch performs best when the compressed vector follows power law We train ResNet18 on CIFARIO, and plot the magnitude of e on the first worker at the end of epochs
Thhe magnitude-index plot roughly line in log-log scale.

---

Under review as a conference paper at ICLR 2022
Table 1: 3 vs. sketch size for convergence
B3 smallest sketch size
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
0.9
0.8
0.7
0.6
0.4
0.4
0.3
0.2
0.1
(00,20, 30, 40} in Fig. [b). It is observed that power law is not satisfied. However, in Fig. Cc) we find that the error vectors in a variant of EFSGD, termed partial EFSGI (Abdi & Fekri 2020) (see Alg. Fin Apdx. dud to space límitation)), follow broken power law, that is, a piece-wise linear function in the log-log plot. Partial EFSGD adds part of the compression error, i.e., (1 - e) for
E [0, 1), to stochastic gradients before compressing. As we shall see in numerical experiments, the update in partial EFSGD is helpful to save more memory when working with count sketch.
NUMERICAL RESULTS
In this section, experimental studies are carried out to validate the proposed algorithms. Since our major goal is push the limit of memory saving, we will mostly focus on ConEF, and experi- ments of iConEF can be found in Apdx. G.4 Overall, the experiments are designed to answer three research questions (RQs): 1) how should we choose hyperparameters in ConEF. Since quan- tization is well-known in community, we put more efforts on the less understood count sketch; 2) when the gradient is aggressively compressed, how much memory can be saved; and, 3) how will the proposed method perform on different learning tasks. Although allreducable gradient compres- sors are advocated, we also include numerical results for scaled-sign, which requires AllGather for communication, to mimic parameter-server scenarios in RQI. Testing various gradient compres- sors is also helpful to demonstrate the generality of ConEF. We follow common practice where both gradient and error compressors are applied in their layerwise form. Our implementation uti- lizes torch. Dist r ribut eibut edDat aP aaParllllll so that the bucket trick can be leveraged to overlap gradient computation and communication, and NCCL is chosen communication backend.
5.1 RQI: GUIDANCE ON HYPERPAAAMETTO CHOICE
In this subsection, we focus on the parameter choices of count sketch and quantization in ConEF us- ing scaled-sign gradient compressor (gg) |لll
& sign(g) (g) as an example. About 97% communi- cation overhead can be reduced. As AllGather is required for communication, the peak memory consumption is increased. Such gradient compressor adopted to simulate the parameter-ser setting, where there is enough memory capacity on the server side. We test this setting with 4 GPUs on an Amazon EC2 p3. 8xlarge instance, where more implementation details are put into Apdx. G.I given the page limitation. When using allreducable gradient compressors, the general guidance for parameter choices similar, although the numbers might change; see Apdx. Apdx.GG.iforr additional illus- tration of this point. Most of experiments are tested on CIFAR 10 which consists of 60000 32x32 images in classes with 50000 training samples and 10000 test ones. Standard data augmentation and preprocessing techniques are employed (He et al. 2016).
We start with comparing contractive error feedback for vanilla and partial EFSGD using count sketches. With = 1, the sketch size has to be 0.95x model size ensure a good convergence for compressing the error vector in vanilla EFSGD. On the other hand, the error vector of partial EFSGD follows the broken power law, and hence more suitable for count sketches. We list the choice of 3 and the smallest sketch size for convergence in Table. I Note that only (0.9, 0.8, 0.7, 0.6, 0.5, 0.4, 0.3, 0.2, 0.1} are tested, though there is barrier choose other values. It is observed that larger /3 leads to more saved memory. This is possibly because that larger 33 helps to suppress the error accumulation count sketches; see Apdx. F
Next we focus on choices for v and w in count sketches We implement the partial EFSGD variant of ConEF (see Alg. in Apdx. [F) with memory budget as 0.6x model size. Two specific sketches,
1, w 0.6x model size and e 3, w 0.2x model size, are tested. It can be seen in performs better. This sug- gests that a larger w, leading to less collision of hash functions, is more numerically beneficial compared with increased v. Simi- lar observations also appear on allreducable compressors. Hnece,
Fig. that the first sketch with
v is adopted in most of our experiments.
Figure 2: ConEF with different count sketches
hhtps://www.s..ce www.oeto.ooooooooooooooooooo edu/ kmiz

---

Under review as a conference paper at ICLR 2022
Performance of ConEF on ResNet18 8 and MobileNetv2. From left to right: (a) train loss and (b) test accuracy on ResNet18; and (c) train loss and (d) test accuracy on MobileNetv2.
Figure 3:
After clarifying the parameter choices, the effectiveness of ConEF in parameter-server settings is tested with ResNet18 on CIFARIO 10 for 150 epochs as shown in Fig. 3 The detailed parameter choices deferred to Apdx. G.1 We use ConEF-CS, ConFF-Q11 and ConEF-Q8 to denote Alg. 2 with error compressors C being count sketch, 16-1evel quantization, and 8-level quantization, respectively. Note that when C is a stochastic quantizer, we follow common practice to replace the lg norm in 4 with max-norm for superior performance (Alistarh et al. 2017). It is observed that on ResNet18, ConEF-Q16 achieves a test accuracy that is almost the same as SGD and EFSGD, demonstrating EFSGD uses unnecessary memory. On the other hand, 44Mb is saved on a 50Mb model with count sketch, while only incurring slight drop with SGD. To further validate the potential of ConEF in smart phone based applications, we test MobileNetv2 (Sandler et al. 2018), a more tailored model for the targeted setting. We set w = 0.1x model size to save 8Mb a 14Mb model compared with EFSGD, while almost losing no test accuracy. Another interesting observation is that the convergence of COnEF-CS tends to be faster in the first 80 epochs before decreasing the learning rate. This might be useful in federated learning with loT devices where each worker may not participate in training for too many iterations.
0.24 on test accuracy compared
5.2 RQ2: MEMORY SAVING WITH AGGRESSIVELY COMPRESSED GRADIENTS
Next we focus on allreducable gradient compressors. We use 16 GPUs on 4 Amazon EC2 p3. 8xlarge instances for experiments.
To investigate the performance of ConEF under aggressively compressed gradients, powerSGD is selected (Vogels et al.) 2019). PowerSGD finds a rank-r approximation to the gradient matrix G. It allreducable and different levels of communication efficiency can be achieved by tuning r. This is a challenging setting for ConEF given that i) the performance of the heuristic powerSGD highly depends on e/, and ii) et plays a more important role when the gradient is aggressively compressed.
ResNet18 is trained on 10 with r = 4 in powerSGD, which reduces 98.5% communication overhead. Unlike (Vogels et al. 2019. a small batchsize, e.g., 16 per worker, considered here for reducing memory requirement Krause et al. 2016). Mixed precision trick is also adopted to facil- itate memory saving, where we use fp16 numbers on count sketches instead of fp32 (Micikevicius) et al. 2018). Two more benchmarks compared with. qSGD (Vogels et al.) 2019): SGD with an unbiased and allreducable gradient compressor that has the same communication overhead as pow- erSGD. In particular, the gradient matrix G E R is approximated by (GU)UT for random matrix U E XR Small-sized matrices GU and U are communicated. We term such a scheme as qSGD to distinguish with QSGD (Alistarh al., 2017). Another benchmark hEFSGD, which is a heuristic method by keeping the top-k elements of e; in EFSGD for memory saving.
The results can be found in Fig. where we mark the percentage of saved memory with ConEF in the figure legend. There are several observations. ConEF-CS has a similar runtime as EFSGD, and both are 10% faster than SGD. This demonstrates the benefit of reduced communication overhead in distributed training. ConEF- CS significantly outperforms qSGD, which confirms the necessity of additional memory to enable good convergence in memory constraint setting with small batchsizes. When 60% memory is saved, ConEF-CS also outperforms hERSGD by large margin in terms of both runtime and test accuracy, validating the general- ization merits of unbiased error compressor (cf. Theorem 4). ConEF-CS has a comparable performance with EFSGD, and more saved memory leads to larger accuracy loss.
Cerdf 21355
Figure 4: ConEF with a pow- erSGD gradient compressor.
8

---

Under review as a conference paper at ICLR 2022
300
3M
500 29120
0210 87%
653
139
55.00%
10.0
Figure 5: Performance of ConEF with unscaled random block gradient compressor on: ResNet- 18. WideResNet-28- 10, and LSTM (left to right).
5.3 RQ3: MEMORY SAVING ON VARIOUS LEARNING TASKS
In this subsection, ConEF is tested different learning tasks. The unscaled random block gradient compressor adopted, where a continuous block of k coordinates are chosen a uniformly ran- dom fashion improve 90% communication efficiency. When using the same random seed among GPUs, AllReduce is readily applied. Such a gradient compressor is more suitable for ConEF, since the error vector ej has d k zeros. Three different training tasks considered: ResNet- 18 on CIFARIO: ii) WedeResNett28--1 on CIFAR 10; and iii) LSTM for language modeling on Wikitest-2 (Merity et al., 2016). To demonstrate the necessity of additional memory, an unbiased variant of ran- dom block gradient compressor enabled by scaling with importance sampling is also implemented. We term the corresponding method rbSGD. A setting with small batchsizes is still the main focus here, and the results can be found in Fig. 5
On ResNet-18 18, it is observed that EFGSD and ConEF save 22% and 21% training time compared with SGD. The percentage of time saving improves over powerSGD even with smaller compres- sion ratio here. This is because more time is spent on the complicated encoding in powerSGD. It observed that ConEF significantly outperforms rbSGD, once again demonstrating the need of ad- ditional memory when training with small batchsize of 16. Compared with EFSGD, ConEF-CS drops 0.04 and 0.5 on test accuracy to save 60% and 90% memory, respectively.
For WideResNet-28-- 10, EFSGD and ConEF are 49.0% and 48.6% faster than SGD. Algorithms with (contractive) error feedback again considerably outperform rbSGD. EFSGD does not catch up with the test accuracy of ConEF-CS with 60% memory saving at a difference of 0.6, suggesting that EFSGD consumes memory inefficiently. ConEF-CS C- with 90% memory saving only drops 0.1 test accuracy compared with EFSGD. In light of the results on ResNet-18, 18, larger model (WideResNet) appears be more robust when used jointly with contractive error feedback.
Next focus on language modeling with LSTM on Wiki'Tex-22. All tested algorithms reduce about 78% training time of SGD. rbSGD fails to match the performance of both ConEF-CS and EFSGD. When 60% memory is saved, ConEF-CS has 0.3 lower perplexity compared to EFSGD. ConEF-CS with 80% memory saved performs slightly worse than EFSGD with 0.2 higher test perplexity.
We also train a transformer for machine translation on Multi30K (Elliott et al. 2016 in Apdx. Adam based heuristic methods with (contractive) eтror feedback are adopted. In such case, even 90% memory saved CoNEF-CS has slightly better performance than EF-Adam.
Additional experiments. Performance of iConEF-vl and v2 can found in Fig. In this experiment, another allreducable gradient compressor, unscaled random-k, is adopted to reduce 90% commu- nication. Both versions of iConEF outperform ConEF, validating our findings in Theorems and Due to space limitation, more im- plementation details and numerical results regarding random-k gra- dient compressor are deferred to Apdx. G.4, where we observe that EF can reduce 95% additional memory of EFSGD on ResNet18.
Figure 6: iConEF with ran- dom l gradient compressor.
CONCLUSION AND FUTURE WORK
Contractive error feedback (ConEF) is introduced to alleviate memory concerns in communication efficient methods. The key insight is that the error vector can be compressed and an effective error compressor, such count sketch, saves memory with almost no accuracy drop. ConEF is tested on various image classification and language processing tasks, reducing 80% 90% of additional memory footprint in EFSGD. Our next step will foeus saving memory more aggressively.
9

---

Under review as a conference paper at ICLR 2022
ETHICS STATEMENT
The main topic of this work is speeding up distributed training on devices with limited memory. Since this work focuses on an algorithmic perspective, the impact would be mainly scientific rather than ethical.
REPRODUCIBILITY STATEMENT
All missing proofs be found in Appendix. Detailed choices for hyperparameters and additional experiments are deferred to Appendix G due to space limitation, and publicly available code will be provided after review process ensure anonymity.
REFERENCES
Afshin Abdi and Faramarz Fekri. Quantized compressive sampling of stochastic gradients for effi cient communication in distributed deep learning, In Proc. of the AAAI Conf. on Artificial Intelli- gence, volume 34, pp. 3105-3112, 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication--ffiiinn SGD via gradient quantization and encoding. Proc. of Neural Infor- mation Processing Systems, 30:1709-1720 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Kririrat, Nikola Konstantinov, and Cedric Renggli. The convergence of sparsified gradient methods. Proc, of Neural Information Processing Systems, pp. 5973-5983, 2019.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGD: Distributed sgd with quantization, sparsification and local computations. Proc. of Neural Information Processing Systems, 32, 2019.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimization for non-convex problems. In Proc. of Intl. Conf. on Machine Learning, pp. 560-569. PMLR, 2018a.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In Proc. of Intl. Conf. on Learning Representationss 2018b
Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In Intl. Colloquium on Automata, Languages, and Programming, pp. 693-703. Springer, 2002.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273-297, 1995.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image worth 16x16 words: Transformers for image recognition scale. In Proc. of Intl. Conf. on Learning Representations, 2020.
Desmond Elliott, Stella Frank, Khalil Sima' an, and Lucia Specia. Multi30k: Multilingual english- german image descriptions. In Proc. of the 5th Workshop on Vision and Language, pp. 70-74. Association for Computational Linguistics, 2016.
Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M Roy, and Ali Ramezani- Kebrya. Adaptive gradient quantization for data-parallel SGD. Proc. Neural Information Processing Systems, 33:3174-3188 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proc. of the IEEE Conf. on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
10

---

Under review as a conference paper at ICLR 2022
Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication- efficient distributed learning. arXiv preprint arXiv:2006.11077, 2020.
Samuel Horvath, Chen-Yu Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv: 10988, 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sehastian Stich, and Martin Jaggi. Error feedback fixes signSGD and other gradient compression schemes. In Proc. of Intl. Conf. on Machine Learning, pp. 3252-3261. PMLR, 2019.
Ben Krause, Liang Lu, lain Murray, and Steve Renals. Multiplicative LSTM for sequence modelling. arXiv preprint arXiv: (609907959) 2016.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reduc- ing the communication bandwidth for distributed training. In Proc. of Intl. Conf. on Learning Representations, 2018.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture 2016.
models. arXiv preprint
Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, et al. Mixed precision training. In Proc. of Intl. Conf. on Learning Representations, 2018.
Konstantin Mishchenko, Bokun Wang, Dmitry Kovalev, and Peter Richtárik. IntSGD: Floatless compression of stochastic gradients. arXiv preprint arXiv:2102.00837,, 2021.
Yanghua Peng, Yibo Zhu, Yangrui Chen, Yixin Bao, Bairen Yi, Chang Lan, Chuan Wu, and Chuanx- iong Guo. A generic communication scheduler for distributed dnn training acceleration. In Proc. of ACM Symposium on Operating Systems Principles, pp. 16-29, 2019.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910. 10683, 2019.
Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase and Yuxiong He. Zero: Memory optimizations toward training trillion parameter models. In Proc. Intl. Conf. High Performance Computing, Networking, Storage and Analysis, pp. 1-16. IEEE, 2020.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. arXiv:2102. 2021.
Ali Ramezani- Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M data-parallel SGD via nonuniform quantiza- tion. Journal of Machine Learning Research, 22(1 14):1-43, 2021.
Roy. NUQSGD: Provably communication-efiae
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint arXiv:2106.05203, 2021.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510-4520, 2018.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Proc. of Annual Conf. of the Intl. Speech Communication Association, 2014.
Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan
Catanzaro. Megatron-Im: Training multi-billion parameter language models using model par- allelism. arXiv preprint arXiv: /909:.v::99000000 aate::/9990...3 2019.
Nimit Sharad Sohoni, Christopher Richard Aberger, Megan Leszezynski, Jian Zhang, and Christopher Ré. Low-memory neural network training: A technical report. arXiv preprint arXiv: /904. 10631, 2019.
11

---

Under review as a conference paper at ICLR 2022
Ryan Spring, Anastasios Kyrillidiss, Vijai Mohan, and Anshumali Shrivastava. Compressing gradient optimizers via count-sketches. Proc. of Intl. Conf. on Machine Learning, pp. 5946-5955 PMLR, 2019.
Sebastian Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. Proc. of Neural Information Processing Systems, 31:4447-4458, 2018.
Sebastian Urban Stich. Local SGD converges fast and communicates little. In Proc. of Intl. Conf. on Learning Representations, number CONF, 2019.
Leslic G Valiant. A theory the learnable. Communications of the 2711) 1984.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. Proc. of Neural Information Processing Systems, 32: 14259-14268, 2019.
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. ATOMO: Communication-efiicee learning via atomic sparsification. Proc. of Neural Information Processing Systems, 31 3199500-9661, 2018.
Jiangiao Wangni, Jialei Wang. Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. Proc. of Neural Information Processing Systems, 31:1299- 1309, 2018.
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning. Proc. of Neural Infor- mation Processing Systems, 30, 2017.
Ashia Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning, In Proc. of Neural Information Processing Systems, pp. 4151-4161, 2017.
Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized sgd and its applications large-scale distributed optimization. In Proc. of Intl. Conf. Machine Learning, pp. 5325-5333. PMLR, 2018.
Cong Xie, Shuai Zheng, Oluwasanmi O Koyejo, Indranil Gupta, Mu Li, and Haibin Lin. CSER: Communication-efficie SGD with error reset. Proc. of Neural Information Processing Systems, 33, 2020.
An Xu, Zhouyuan Huo, and Heng Huang. Step-Ahead Eлtor Feedback for Distributed Training with Compressed Gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10478 10486, 2021.
Hang Xu, Chen-Y Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, 2020.
Mingchao Yu, Zhifeng Lin, Krishna Narra, Songze Li, Youjie Li, Nam Sung Kim, Alexan- der Schwing, Murali Annavaram, and Salman Avestimehr. Gradiveq: Vector quantization for bandwidtt-eeffiieet gradient aggregation in distributed enn training. Proc. of Neural Information Processing Systems, 31:5123-5113 2018.
Shuai Zheng, Ziyue Huang, and James Kwok. Communication-effiien distributed blockwise mentum SGD with error-feedback. Proc. of Neural Information Processing Systems, 32:1 1450- 11460, 2019.
12

---

Under review as a conference paper at ICLR 2022
Supplementary Document
A MISSING DETAILS
A.1 HOW GRADIENTS ARE COMMUNICATED
While the "aggregation" in line 7 of Alg. T is a highly abbreviated term, in practice (compressed) gradients are communicated through AllReduce, AllGather, or parameter-server, among which allre- ducable compressors
widely appreciated. In contrast AllGather, AllReduce enjoys low com- munication cost that is nearly independent of the number of workers (Vogels et al. 2019 Peng et al., 2019). In addition, compressed gradients that are allreducable relieve runtime since only needs to be decoded once. In AllGather, a worker receives N compressed gradients that not only take addi- tional space but also need to decompressed individually. This has negative impact on memory and runtime scalability given the number of workers can be large Vogels et al. (2019). When com- pared to parameter-server, AllReduce bypasses the need of double compression, where compression is applied to the bidirectional communication of clients and server. Parameter-server structure can also introduce communication congestion due to the centralized aggregation at the server side Yu ct al. 2018).
A.2 BIASED GRADIENT COMPRESSORS ARE MORE SUITABLE FOR SMALL BATCHSIZES
Suppose that is a stochastic approximation of V (x) satisfying Assumption We show that
compressors satisfying Assumption 4 typically biased, are more robust to the large variance (a²) in the small batchsize settings. Consider gradient compressor Q satisfying Assumption 4 with 8 < 1. The compression error of Q can be calculated as
Qn(g) gl 21 < SE |gll <
OE Vf + 80
(5)
Let 22 denote an unbiased compressor satisfying Assumption sion ratio, we have 0 > The compression error is bounded by
Typically to get good compres-
Ell - g - (E || - ([( + 6o².
(6)
Given 0 > 1, the bound in (6) amplifies the variance; while the bound in (5) shrinks the variance. Therefore, a contractive compressor satisfying Assumption 4 which typically biased, more suitable for small batchsize setting due to the large o². Although some of unbiased gradient compressors, such as QSGD working in "dense regime" (Alistarh et al. (017)) and natural dithering (Horvath et al. 2019).. ensure 9 < 1, unfortunately they are not allreducable, and hence are not suitable for our setting.
Other works such (Stich et al. 2018) also observe the variance blow-up in unbiased gradient compressors.
A.3 APPLYING CONEF TO ZERO
ZcRO (Rajbhandari et al. 2020) can be used to address memory issues for training large models in distributed fashion. Mathematically, ZeRO is equivalent to Adam or other chosen optimizers, while the memory issues are addressed by partitioning optimizer states, gradients, and even model parameters among different workers. Here we consider the case of ZeRO3, where all aforementioned parts are partitioned among different workers.
Being most memory efficient, ZeRO3 increases the communication overhead. Hence, it is helpful to use gradient compression to speed up training. However, EF based approach cannot be applied here due to the requirement of model-sized local error vector that is burdensome to GPU memory. In addition, because of the partitioned gradients, it is impossible to employ the memory trick in (Ramesh et al. 2021) where one puts local error vector gradient buffer save space.
We believe ConEF is helpful to reduce the runtime of ZeRO3 while respect constraints on GPUs memory. In this paper, first demonstrate the feasibility and convergence of ConEF to clear up the theoretical barrier of integrating ConEF to ZeRO3. The detailed implementation is left for future work.
13

---

Under review as a conference paper at ICLR 2022
B PROOF OF THEOREM 1
Proof. For convenience, define the compression error of C worker i Ci c/41 Following Assumption we have
-Pi
Ai-
E [ A 0,
(7)
B[IGI| A:]
EE [[[[(p]
A AIl
A S <0PP Ail?
(8)
Next, we rewrite local error e/41 using Ç?
e = p A +
7B: + ej A +
where (a) follows from p ng! + c//
Then summing over N workers, we have
e
N
N
N Σ
7
g
2
N
i=1
1=1
E=1
N
N
(
+
Xx+1
x
+
c
N
1=1
where (b) is because + E .V
A
X
X141.
Rearranging the terms and define z,
X; N Dim ei, we arrive at
N
24+1
g
(9)
N
N
1=1
The analysis will rely on (9). By Assumption
we have
[(2++1) - ((ze)
(10)
S (VI(2)), 20+1 - -z+) + |1241 2:112
N
N
N
(f((2)) ())
VV fZ()), g/) +
1
Σ
c
N
N
N i=1
N
1=1
(f(22)) ())
(Z)) Vf(x)), gi:)
N
N
(V(())) +
Σ g +
Given 7 and taking expectation w.r.t the randomness of Q we arrive at E[C/pp |/ e
0. Then conditioning on X₁ and taking expectation w.r.t. the randomness of g/. we have Elc] xx, cf] O. Hence, we have
E (VVf()))))>> cf = (Vf(2)) clI
E(( =0
(11)
We also have
E (Vf(z)) v)(x:), g)) e = (V(()(z))) vx(x.), (x.,e)) e/].
14

---

Under review as a conference paper at ICLR 2022
Then taking expectation w.r.t. x; and ej, we have
(Vf))()))V(()))..)) (V
(12)
(111//(1) - -
nT.
1
|||
2 E
2
i=1
[x]])
+ 2 (1- - cc}
(o2 G9)
where (c) by Young's inequality; (d) uses Assumption from Lemma
and z, X 2 Ei=
et: and (e) comes
Next, we have
B (((((())).))) BB (VV())))))) = {x)
(13)
To proceed, we have
L
7
Σ
(14)
2
N
N Σ c
$
g - vf(x)))
- V
LE
N
i=1
N
N
< ||3] + LTアeE
Σ gi -
LE
Σ
N
N
InPo²
Σ c:11
+ LE
N
Ln
1 c c/\ 2L50n (0² + G2)
< <
c
N
where the last inequality comes from Lemma Taking expectation both sides of 10 and plugging
12 13
and (14 in, we have
E f( f(zz)] s (- + [|V(x)))
+ c T G2)
o I
1 1-c+ c/> 250m G2)
+
(1)
N
1-c
Rearranging the terms and dividing both sides with n, arrive
2 - (x)))( B[f(z) - f(((41)]
c) 2 + n L
122 + G2)
1 1-c+
1f + +G)
N +
1-c
N
Summing over t, and using the facts Zu = xu and f(zr) 2 f", we arrive at
(f(x)) - f²)
1 Lm) T
B[IVFf(x))11]
1/L
1=0
1,212(02 + G2)
n L
1 1 c + c/2 200 + G2)
(1 (1- c)P
2
N
N
15

---

Under review as a conference paper at ICLR 2022
Let min + Liv +///s> Using these three inequalities, we have
}. In this case, have 1 Ly 1.2 S (TTLS and f) 2 /N.
LVT
4L(f(x)) -(f(xo) -8a)
+ ((f(x)) - f
B
< 0² + G 11 272/3
V (xx ]
47
T
VNT
T2/3
o²
1 1-c+ c/> 250 + GG.
VNT
1
VNT
If we consider sufficiently large T, i., T > N3, we have VNT 22/3, Plugging this inequality in and viewing both À and e as constants, we have
Σ B(IV) S (H - 2 0 +0(xx())
G2
+ O 188(0² + +9)
VNT
/NT
VNT
The proof is thus completed.
Lemma Suppose that there exist e E (0,1) 1) and x such that (1+2)[++00)2 It
guaranteed to have
i+1
S
10"
(1 cc
Proof. To start with, we have
1 N
E
E
Σ
E
E[le
(15)
N2
N
Conditioning on gi the randomness only comes from two compressors.
E [[e|| 12 g
=E [[ A +
(16)
12) (1 [IIpp All + (1 B
(1+a+ + 8) [|lp: 1
(9)
x (1+ vo) ' [|Ip: [g
(
- 611+ + vo) 2 [| gd
5(1 + "0) [[lns] + cf
(1 + ) + v0 2 |g 1 + (1 X)6 + v0) " ||e |1 g/
where (a) is by Young's incquality, i.c., aa + bl2 < (1 + (1 + b/2 with a > to be specified shortly; (b) is the result of 8 (c) is by choosing = vo, which minimizes the coefficient; (d) results from Assumption and (e) follows again from Young's 's inequality.
Then taking expectation w.r.t. g/. we arrive at
E [[leet+111 [1 < (1 )))(( 6(1 v0)² 2 E (1+ A)ō(1 v0) E e||
B
Ax
16

---

Under review as a conference paper at ICLR 2022
Summing over i, get
N
BAn² N N
N
E [
119]
Σ
+
A
B[|ee[]]]
(17)
N
1=1
==1
2 Bx
+ G2)
+
4
E |
(g)
Bx (o2 G*).
where (f) follows from Assumption
2 and (g)
obtained by recursively unrolling
1 N Em | [ and using the fact that oj = 0. Given the parameter choice (1+A)(++0))
for some E (0, 1), we have A c and B, The proof can be completed by using (15)
Lemma 2. Choosing the parameters the same as those in Lemma 7 it is guaranteed to have
N E
1 1- c c/>
(o² (o² G²)
E
N
-
Proof. Given
7 is not hard to that for i + j,
E
(()
St
[x1]
=
which implies that
N
N
1
E [1]
(18)
N 1=1
N
Then we have from
8 that
E || A < Opp A
Then taking expectation w.r.t the randomness of Q and by Assumption 4
we have
[| [p:] < 60|[p:11 50 Ing + e
Finally, taking expectation w.r.t. p/ have
[[[ < 50T [1vef eill < 280 28 [16:)]] + 250 [
Summing over i, we arrive at
N N Σ [[I
1 N
N
< 2001²
Σ N
E [[lg::111+ 258
E
[[|c
N
i=1
1=1
< 280
+ G2) + 260
c
70"
(I (I-
1 c c/- 200
where we use Assumption 2 and 17
in Lemma
simultaneously in the second last incquality. The
proof is completed by applying 18)
C PROOF OF THEOREM 2
The proof idea is to define of := E g and to view of41 as a single error compressor so that we can reuse the proof of Theorem Then we have
To see this, define compression error as Ç
pp A e/-1
E E
p A
=
p
Aj - (p) -
(19)
B
A
C a ) A -pp -a 0.
17

---

Under review as a conference paper at ICLR 2022
where the last equation uses the fact C[c(p) A; means that 1/+1 is still unbiased estimator of p A However, by adding the compression error back, the variance of çi can be reduced, i.e.,
=(41)/pp. 0/1 pj A e This
1 [|
A
E [1 C(P: A (/41) P A.l
AJ
(20)
OF [| (P) A/) PP A
[E[[ A (P) 366--911 4 P A:l
- 8² Ip: -1
Comparing with 8 one can see that 0 dependence is indeed improved given accurate C with Next, we modify Lemmas and to finish the proof.
Lemma 3. Suppose that there exists guaranteed to have
(0,1) and À such that ó (1+x)(1+0)=- It is
1'| (1- n + 22
B
e11
Proof. The proof is basically the same as Lemma 1 except for using tighten the bound. Hence, we only highlight the difference here.
20 rather than in 16 to
E [ [ g.) = E [Ipi A 1g
(21)
g + (1 (1+ 1
$ (1 + [
All
||
(0)
1 a 0 8²
| A
(1+ (1+0) " |lp
0)
A l
s 5( '
= 6(1 0) " I1gs +e
_ (1 +) 0(1 +0)
|sll +1++++++++ (1++))(11
where in (a) we uses 20 (b) chooses 0.
Lemma 4, Choosing parameters the same as those in Lemma 3 it is guaranteed to have
1 c c/> 280 12 (o² + G
E
Si
N
Proof. The proof is exactly the same Lemma 2 except for using 20 rather than omitted here.
Hence it is
Proof of Theorem 2 The rest of proof the as Theorem in (12 and ii) applying Lemma in
except for i) applying Lemma
D PROOF OF THEOREM 3
Proof. The basic idea is again to define ei-1 ē + T441 and to view ei4, as single error compressor that we reuse the proof of Theorem [ Applying (Horváth & Richtárik 2020 Theorem 3), we have of unbiased with bounded variance. In particular, we have
E e[e41 (p)
DpI. A = [ + (4n) (pi 4))p A =
(22)
E [l|e:41 (p.
A P Ai = B[ll(et+) qq+1) - (p) 11 A
(23)
50llp; Alp
18

---

Under review as a conference paper at ICLR 2022
Therefore, the derivation in Theorem [ The only change need is modify Lemmas
lndd 2 to Lemmas and respectively. After applying these modified lemmas, Theorem 3 directly follows.
Lemma Suppose that there exists E (0.1) and 0 such that 8 (1+1)(1+00) If
guaranteed to have
e41
S (1 c) (022 + vL2)
Proof. The proof is basically the same as Lemma 16 here. Define Ç c++1 P + A we have
hence we only highlight the different steps in
11 g = E [lpp a
+
<
1/ g
(24)
3 [IP A |1 |g + (1+ 2) E
(1 a
(2)
88
(1+a + 80 +
EE [[ 2
(0)
(1+ V50 [[ A ||:]
(1 'T) - [g]]]
where (a) the result (23
(b) is by choosing a = v89; and (c) follows from 1.
Lemma 6. Choosing the parameters the same as those in Lemma 5 guaranteed in iConEF-v2 to have
N 1- c- c/220 (02 + +2)
E
N
1-c
N
Proof. The proof is almost the same as that of Lemma From
2
hence we only highlight the differences.
23 we have
E [1 <8001p::12 800l ei
Finally, taking expectation w.r.t Pt. we have
|[ [1]] < 8'0E [[ngi e < 28 2 E[lggl] + 25 [|
c-c+ c/ 28" + G
c
where we use Assumption 2 and Lemma 5 simultancous in the last inequality With this modifica- tion, 6 follows directly.
E PROOF OF THEOREM 4
We focus ConEF. The proofs for iConEF-vl and iConEF-v2 follow the same steps (simply by
defining e'41 t + 4i+1) and hence are omitted here. Recall that in (9) we have Z
2:
N 1 Bi Ei Gi with 2,
Xx 1
N
ej This implies that
1
1
77 N
Σ Ci.
X1+1
N
N
N
1
1=1
19

---

Under review as a conference paper at ICLR 2022
Conditioned on fx,, felti. {g/he] = Pa and only take expectation w.r.t the randomness of C,
have
N
N
N
1
E2
X++1
e +
P:
X
P
E
S
N
N
N
2=1
i=1
1
E
X
P1
N
Then we further take expectation w.r.t P. and unroll E
[x
N
Σ si=1
ei]
we can get
i
N
E X
11 = Xn -,E
8
Given that Xo E RR(AT), and gi E R,
Vt, it is straightforward to see that E [xx+11 DE e(+1] R(AT). Hence the proof is completed.
F PARTIAL CONEF/EFSGD
To utilize memory in the most efficient manner when adopting count sketches as the error com- pressor, we introduce a variant ConEF, termed partial ConEF Alg. Partial ConEF is adapted from partial EFSGD (Abdi & Fekri 2020), which can be recovered when C in line 9 is an identity
mapping. The main difference with ConEF the introduction of the scaler / E [0, 1). highlighted
in blue. Partial EFSGD/ConEF adds part of the compression error, i.e., (1 - 8)ei, to the stochastic
gradient before compressing; see line The remained local error Bei kept and included in the update of e in line 9 for the use of next iteration. The convergence of partial ConEF is straight forward when combining our proof with (Abdi & Fekri 2020).
Algorithm Partial EFSGD) partial ConEF
Initialize: X Fd ej = 0 e Fd, Vi, 3 (0.1)
2: for = 0, 1....,,.. T
do
3: assert x; = x; for every worker
4: for worker i = .......... N in parallel do
5:
p; = 7/ + (1 3)e
6:
A ((p()
7:
A, = Aggregate( A Vi)
8:
X,+1
A
9:
e = CBe + p: A
10: end for
11: end for
The partial ConEF update in line 9 is helpful when count sketch. In particular, we can rewrite line 9 as c/41 = C(e: (1 - 3) + P A;). This means that the compression error in of is also scaled down or subtracted. This is helpful for suppressing the accumulation of compression error.
Partial ConEF benefits from the linearity of count sketch since the decompression of of can be avoided when updating ei41 in line One can simply compress P A and add to the scaled ef- Moreover, auxiliary variables in global memory can be avoided by taking advantage of the shared memory of the GPU. Compared to nonlinear error compressor C, count sketch further reduces the burden runtime.
G MORE ON NUMERICAL EXPERIMENTS
20

---

Under review as a conference paper at ICLR 2022
Table 2: / vs. sketch size for convergence for unscaled random block &t gradient compressor
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
smallest sketch size
0.9
0.9
0.8
0.7
0.5
0.3
0.3
0.1
Experiments are repeated 3 times and averaged results are re- ported. In the implementation of count sketches, the tensor trick can be employed to avoid computing too many hashes, which im- proves the runtime. In the tensor trick, instead of using element- wise compressing, we view the error vector one row or column as an "entry" of the compressed vector, result- ing in a tensor sketch (matrix when = 1). More specifically, suppose the error vector lives in IR4 whose matrix view is R=xm with d mn. It takes (resp. m) hash computation in row- (resp. column-) tensor trick, while mn hashes are needed without this trick. Differences test accuracy between row- column-based see Fig. 7
matrix, and treat
Figure 7: ConEF with row or column hashes has similar per- formance. tensor tricks not observed;
G.1 PARAMETER CHOICES FOR RQ1
Experiments in this subsection is carried out using single Amazon EC2 p3.8xlarge instance with 4 GPUs. The goal here simulate a parameter-server setting since we do not have a real testbed.
ResNet18 on CIFARIO. The model is trained for 150 epochs with weight decay 10-4 and momen- tum 0.9. We decrease the learning rate by factor of 10 epochs SO and 120. Overall batchsize 128 (32 per worker). And the initial learning rate for SGD is tuned from {0.1, 0.075, 0.05, 0.025), with final choice of 0.1. EFSGD, ConEF, and QSGD use the same learning rate. In CoNEF-CS we use 3 0.9.
MobileNetV2 on CIFAR10. The model is trained for 150 epochs with weight decay 10-5 and momentum 0.9. We decrease the learning rate by factor of 10 at epochs 80 and 120. Overall batchsize is 128 (32 per worker). And the initial learning rate for SGD is tuned from {0.1, 0.075, 0.05, 0.025]. with final choice of 0.1. The same learning rate is used for EFSGD and ConEF. 3 = 0.9 is adopted in ConEF-CS.
Choices of 3 for allreducable gradient compressors. While the parameter guidances for scaled- sign gradient compressor are discussed, we also include the choice of 3 and the smallest sketch size for convergence in Table. 2 when the gradient compressor Q is unscaled random-block: which is allreducable. We choose such that 90% communication overhead is reduced. Similar to scaled- sign, it is observed that larger leads more saved memory. Hence, we recommend to choose g 0.9 or even larger.
G.2 PARAMETER CHOICES FOR RQ2
The experiments are carried out using 4 Amazon EC2 p3. 3xlaare instances (16 GPUs in total).
ResNet18 on CIFAR1O. The model is trained for 150 epochs with weight decay 10- and momen- tum 0.9. We decrease the learning rate by factor of 10 at epochs 80 and 120. We focus on small batchsize setting with 16 data sample per worker (256 in total). The initial learning rate for SGD is tuned from 10.1, 0.075, 0.05, 0.025), finally chosen as 0.1. EFSGD, ConEF, and hEFSGD use the same learning rate. ConEF-CS with 60% memory saving uses 0.85; while its 90% memory saving relies on 3 0.9.
G.3 PARAMETER CHOICES FOR RQ3
All experiments are carried out using 4 Amazon EC2 p3.8x large instances (16 GPUs in total).
ResNet18 on CIFAR10. We train this model for 120 epochs and decrease the learning rate by 10 at epochs 60 and 100. Momentum is chosen 0.9 and weight decay is set to 10 To save memory, we focus on small batch setting with batchsize 16 per GPU (hence 256 in total). The learning rate for SGD is tuned from (0.05, 0.1, 0.2), and 0.2 is chosen. We use the same learning rate in EFSGI
21

---

Under review as a conference paper at ICLR 2022
Table 3: Numerical results for ResNet18
Algorithm
test accuracy
runtime (min)
memory saving (MB)
SGD
93.20
54.83
rbSGD
86.58
40.12 12
48.2
EFSGD
92.52
40.41
0
ConEF 60%
92.53
42.45
31.5
ConEF 90%
92.02
42.45
44.1
Table 4: Numerical results for WRN-28-10
Algorithm
test accuracy
runtime (min)
memory saving (MB)
SGD
96.12
139.70
rbSGD
82.92
70.88
T22.1
EFSGD
95.28
71.13
0
ConEF 60%
96.00
72.11
76.2
ConEF 90%
95.23
71.98
101.5
and ConEF-CS. For CoNEF-CS with 60% saved memory, choose B 0.9; and for ConEF-CS with 90% memory saving we use 3 = 0.95. For rbSGD, we test step sizes from (0.05.0.1,0.2) and 0.1 is chosen.
e on CIFAR1O. The model trained 150 epochs. Learning rate is decreased by on epochs 50, 90, and 120. We set weight decay as 5 x 10 and momentum 0.9. Nesterov momentum is also adopted. A small batchsize 16 per GPU (256 in total) is considered for memory saving. The learning rate for SGD tuned from {0.05, 0.1, 0.2), where 0.1 performs the best. EFSGD and ConEF-CS adopt the same learning rate. For ConEF-CS with 60% saved memory, we choose 3 0.75; and for ConEF-CS with 90% memory saving we use B 0.995. For rbSGD, we test step sizes from (0.001, 0.005, 0.05.0.1) and 0.005 is the final choice.
LSTM on Wikitext-2. We use a 2-layer LSTM with 672 hidden units and 672-dimension word embeddings. We set BPTT as 35, and clip the gradient norm to 0.25. The momentum is chosen as 0.9, aided with Nesterov momentum as well. Dropout rate is chosen as 0.5. We also consider small batchsize setting, e.g., per GPU (32 in total). The model is trained for 60 epochs where the learning rate is decreased by 4 at epochs 15, 30, and 45. The initial learning rate for SGD is tuned from {0.5, 1, 2, 4). and 2 is chosen. The same learning rate schedule is adopted for EFSGD and ConEF-CS. For ConEF-CS with 60% saved memory, we choose B = 0.8; and for ConEF-CS with 80% memory saving is chosen.
0.9. For rbSGD, test step sizes from (0.5, 1, 4) and
G.4 ADDITIONAL EXPERIMENTS
Adam type algorithms on a transformer. A single layer transformer for English-Germen machine translation is trained on Multi30k dataset (Elliott et al. 2016). particular, we use a 512 dimen- sional embedding layer. Both encoder and decoder have 3 layers with hidden dimension 512 per layer and 8-head attention adopted. The initial learning rate for ADAM and other algorithms is set as 10-4, The transformer is trained for 30 epochs, where the learning rate is decreased by at the end of epochs 15 and 25. Batchsize is set to 128 and dropout ratio is set as 0.1. The biased gradient compressor is chosen as unscaled random block k to reduce 90% communication overhead.
Adam with an allreducable and unbiased gradient compressor (rb-Adam) struggles in terms of train- ing loss. EF-Adam converges even slower than its ConEF counterpart. This once again demonstrates
Table 5: Numerical results for LSTM
Algorithm
perplexity
runtime (hour)
memory saving (MB)
SGD
92.72
7.57
rbSGD
120.07
1.45
262.5
BFSGD
98.29
1.49
Co 60%
97.76
1.51
180.3
ConEF 80%
98.59
1.50
220.2
22

---

Under review as a conference paper at ICLR 2022
Adam
Adam
60% ConEF CS 90%
CorEF-CS 9054
velicwaton low
teinies
(a) train
(b) validation
Figure 8: Performance ConEF with unscaled random block gradient compressor on transformer.
95
8.-
85
7.0
BFSGD
COMEF-CS Cs 95%
ConEF
ConBi-CS 98%
BR-CorEF
80
25
800 ipoch
375 200
opoch
Figure 9: More aggressively saved memory with random-k gradient compressor.
Figure 10: Test of ConBF-CS with error reset using random-k gradient compressor.
that EF-Adam does not take full advantage of memory. ConEF with 60% and 90% memory saved obtain similar training loss both slightly larger than Adam, but there is gap on validation.
Regarding validation loss, rb-Adam fails to match with other tested algorithms. With 90% mem- ory saved, ConEF-CS still outperforms EF-Adam slightly. ConEF-CS with 60% saved memory has comparable performance vanilla Adam, and both are much better than EF-Adam. These ob- servations suggest that ConEF is an improved alternative of error feedback to endow Adam type optimizers with communication and memory efficiency in distributed training. Lastly, the validation gap between ConEF with 60% and 90% memory saved intuitively makes sense, since shown Theorem the best generalization error can be achieved when subtracting averaged local error vectors from current model. The count sketch in ConEF-CS introduces larger compression error when more memory is saved (small sketch size), thus losing more on generalization behavior.
Random-k gradient compressor with more memory saving, We also test the unscaled random-k gradient compressor on R8 with CIFARIO, where 90% communication burden is reduced. As shown in Fig. 9 EFSGD has a test accuracy of 93.42, while ConEF-CS with 0.05 (95% memory saving) and w = 0.02 (98% memory saving) achieve a test accuracy of 92.70 and 92.68. Hence, it is possible have aggressive memory saving with less than loss test accuracy. In addition, is observed that the compressed error vector helpful to get a faster convergence initially. But after decreasing the step size, it has negative impact resulting in the accuracy drop.
iConEF with a random-k: gradient compressor. To validate the improvement of iConEF over ConEF, train ResNet-18 on CIFARIO, and the results are reported in Fig. 6 A random- gradient compressor reducing 90% communication overhead is adopted. For ConEF, we use a 64-level stochastic quantizer as the error compressor. iConEF-v2 is considered in this case, and
23

---

Under review as a conference paper at ICLR 2022
top-k compressor (5% elements) the first enror compressor, and 64-level stochastic quantizer as the second error compressor. As shown in Fig. 6 although ConEF has similar performance EFSGD, iConEF-v2 outperforms both of them, validating its efficiency. iConEF-vl also included in Fig. 6 In this case, both error compressors are chosen as 8 = 256-1evel quantizer. iConEF-vl converges much faster comparing with EFSGD initially, and it has similar test accuracy after learning rate is decreased.
ConEF-CS can be used easily with error reset (ER). As discussed in Section 4.2.2, error (Basu et al. 2019 Xie et al., 2020) can be applied directly when the error compressor C is count sketch. Thanks the fact that count sketch allreducable and small in size, ER can be done through allreducing the compressed error among all workers every a few iterations, which in our case is 512. ER slightly improves the test accuracy of CoNFF-CS by 0.1 as observed in Fig. [O More specifically, we train ResNet-18 on CIFAR10 with unscaled random-k gradient compressor reduce 90% communication overhead, and choose memory. As shown here, both ConEF and ER-ConEF outperform EFSGD, and ER-ConEF has the best test accuracy.
0.9 with a count sketch that saves 80%
24


Reviews:
[{"review_id": "QMK29_dDzZJ", "reviewer": "Reviewer_VhWp", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- I have not seen before that a multi-level error correction procedure is applied. This seems to be novel and interesting.\n\nWeaknesses:\n- I did not understand most theorems, but it is probably because I am not familiar with the theoretical background. Other reviewers probably have more to say about this.\n- The paper is difficult to read. It feels like it is lacking structure between sections. Often I found myself reading a section and wondering how did I end up here and why. I think this can be fixed relatively easily by rewriting and restructuring the paper to guide the reader and explain what is coming next and why.\n- The model contains several statements which I think are untrue or not specific enough to be true in most contexts. In particular, memory problems due to gradients are usually not a problem on GPUs due to ZeRO-3 (fully shared parallelism). ZeRO-3 allows the training of models with 10bn parameters or more on relatively few GPUs without a large communication overhead. While the approach in this paper is still valuable, it should be set into context why it is significant\n- The presentation of the results is not easy to inspect. I would rather have tables with final performance and speedup/runtime numbers. The charts are too small to really see the differences in methods\n- I do not understand the motivation for the sketch count algorithm. Expanding on this would make it clearer\n- All the experiments are done on CIFAR-10 and the models have relatively few parameters (small gradients). I do not think this is the best dataset to showcase this method. The current results feel too thin to make accurate judgments about this method and how it fits into the current and future literature\n\n===============================UPDATE================================\n\nSome of my concerns have been alleviated in particular the transformer results in the appendix (that I overlooked) are convincing. I think this paper still has issues that need to be resolved. I think the work is better positioned as communication efficient training rather than training to save memory. There are indeed use-cases where this approach could outperform current approaches that are communication efficient and save memory such as ZeRO.\n\nTo me, it feels the rebuttal has been fruitful and could lead to a much better paper. I think it is better that the authors take their time to improve the paper and resubmit it to the next conference. As such, I will keep my current score.\n\nDue to lacking expertise, I am not able to judge the theoretical part of this paper and I would refer to other reviewers for that part of the paper.", "summary_of_the_paper": "The paper introduces a two-stage error correction procedure for approximated (doubly compressed) gradients. Multiple theorems are derived to prove convergence and scaling properties. The algorithm can be combined with any compression algorithm for the gradient. The algorithm is applied to CIFAR-10 with results showing favorable results.\n", "summary_of_the_review": "Overall, this paper is difficult to read and understand, the experiments on CIFAR-10 are not convincing enough, and some claims are underspecified. The innovation of multi-level error correction does not outway these negative factors and as such I recommend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "NNwAJMtytVQ", "reviewer": "Reviewer_2Hku", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Regarding the method/novelty\n\n1. The author propose to a simple technique to compress the local error either once or twice. It is interesting to see that compressing twice improves the convergence from $\\mathcal(O)(\\theta)$ to $\\mathcal(O)(\\theta^2)$ by doubling the memory cost to store the local error. However, the extra computation overheads are not compared. The author did not show the tradeoff between actual training speed v.s. extra memory cost.\n\n2. Closely related works are not compared such as compression of the error [1] and faster training [2].\n\nRegarding the experiment\n1. The most important issue is about the unrealistic settings of the experiment.\n\n1.1 4 GPUs is far from convincing to demonstrate the scalability of the proposed method and a fair comparison with other baselines. Standard settings would be 16 GPUs with larger-scale datasets like ImageNet.\n\n1.2 The batch size settings unnecessarily enlarge the communication/computation ratio. A larger local batch size (e.g. b=128 with learning rate warmup) on each worker should be set for training small models like ResNet-18 on CIFAR-10.\n\n1.3 The author mentions 1) growing model size and 2) federated learning as motivation. However, All models considered in experiments are very small. There are no federated learning experiments nor corresponding theoretical analysis.\n\n2. Is compressing the local error really necessary? The proposed methods decreases the performance both theoretically and empirically. There is obvious performance decrease most figures for the proposed method. However, what is the real run-time memory reduction? The model size of ResNet-18 on CIFAR-10 should be trivial compared with the activations.\n\nA suggestion would be summarizing the compression ratio of the gradient and the local error, overall memory reduction (instead of the reduction of local error), and final model performance in a table to clearly show the benefits/trade-off of the proposed method.\n\nReferences\n\n[1] Xie, C., Zheng, S., Koyejo, O.O., Gupta, I., Li, M. and Lin, H., 2020. Cser: Communication-efficient sgd with error reset. Advances in Neural Information Processing Systems, 33.\n\n[2] Xu, A., Huo, Z. and Huang, H., 2021, January. Step-Ahead Error Feedback for Distributed Training with Compressed Gradient. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 35, No. 12, pp. 10478-10486).", "summary_of_the_paper": "The authors propose to compress the local error in communication-efficient distributed training to reduce the memory to store the local error.\n\nThe paper also proposes to compress the local error twice, which doubles the memory cost to store the local error but improves the convergence compared with compressing once.\n\nExperiments show the training performance of the proposed method with different compression ratio. But the settings are unrealistic and can not validate the claims.", "summary_of_the_review": "The need to compressing the local error in distributed training is not well justified in the experiments. The proposed application scenarios of training large models and federated learning are not demonstrated by the experiments. Besides, the scalability regarding the number of workers and the model size is not very convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "43n2Alv3X9B", "reviewer": "Reviewer_HC53", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I see two significant issues with this work.\n1. It has been previously mentioned by Ramesh et al. (\"Zero-shot text-to-image generation\", 2021) that error feedback can be optimized if we accumulate the gradients directly into the error buffer. For instance, in PyTorch one manually sets the gradients to 0 after each gradient computation by calling .zero_grad() but instead we could keep the error vector in this memory space, and then the gradient is added directly there, and no extra memory is used. This small observation makes me wonder why the tools from this work are required at all.\n2. Even if we ignore the previous issue, the promised efficiency is very low. Let us say that we take a compression with theta=10. For rand-k or top-k it means that we keep about 10% of coordinates, which is indeed an improvement. However, this may imply a 10 times slower convergence. This is a very big price to pay for a somewhat small reduction in memory use. Since compression operators, such as PowerSGD, usually lead to a speed-up that is smaller than 10x, it may mean that it's better for us to not use compression at all.\n\nI found the iConEF algorithms an interesting addition to the paper story but the theoretical improvement seems to hold only for very niche compressors. The improvement is significant only when the compression ratio is close to 0. This corresponds to almost no compression, and requires to compute an extra compression operator, which make these algorithms unattractive.\n\nThe experiments do not seem to be done in the considered setting of large models that require huge memory, but they seem fine to me as a proof of concept. I believe this work should be mainly judged based on its theoretical results.\n\n--Minor--\n1. The notation for the objective is inconsistent. In problem (1), the authors write f(x; \\xi), but in the paragraph right after that they write f(x, \\xi). Please use either a comma or a semicolon throughout the work.\n2. The comment \"Biased gradient compressors, on the other hand, have been more successful in practice\" seems like a stretch to me. As far as I know, the efficiency of PowerSGD is more due to its support of Allreduce. \n3. It is also not true that \"Biased gradient compressors <...> support a more impressive compression ratio\": For instance, top-k and random-k have exactly the same compression ratio, simiarly to how top-k eigenvalues gives the same compression ratio as random-k eigenvalues.\n4. \"which is typically contractive thus more robust to the gradient variance in a\nsmall batch size setting.\" I do not see how \"contactive\" implies \"more robust to the gradient variance\". The same claim is stated again a bit later and, as far as I can see, without any justification. Please add some supporting reference/evidence or remove this claim.\n5. The \"Aggregate\" operation in the formulation of the algorithms is pretty vague. Even though it is clarified in the text, I'd find it more natural to write this operation as the standard average directly in Algorithms 1 and 2.\n6. The training of Resnet18 on Cifar10 is a bit suboptimal. One can achieve test accuracy above 95% by training for 200 or 300 epochs with cosine annealing learning rate schedule.\n\n--Typos--\n\"state of the art method\" => \"state-of-the-art method\"\n\"EF based methods\" => \"EF-based methods\"\n", "summary_of_the_paper": "Motivated by the memory limitations of large-scale training, this paper proposes a new modification to the error-feedback algorithm for parallel optimization. In particular, the authors suggest compressing the error vector with a separate compressor, which results in the ConEF algorithm. Under the assumption that this compressor is unbiased and has compression ratio theta, the authors prove that the convergence rate has some terms of the same order as in error feedback and others get multiplied by a factor of theta. \nIn addition, the authors propose the iConEF algorithms that introduce an additional error feedback for the extra compressor. This leads to yet another sequence of compressed vectors that need to be maintained. On the other hand, if theta<1 (or delta<1), the rate will become theta (or delta) times better.", "summary_of_the_review": "\nThe results in this work are rigorous and the motivation is well explained. The theory is done under reasonable assumptions and the rates are close to what is expected. Unfortunately, there are a few big issues with the proposed solution. First of all, there seems to be a way to make EF memory-efficient without any algorithmic changes. Secondly, the guarantees for the method imply that the methods are significantly slower than standard EF and may be even slower in runtime than SGD without compression. Finally, the experiments may not be the best possible, but I personally think that this is not a big issue as the main contribution is to propose new methods and analyze their convergence.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers initially struggled to position this contribution in terms of usefulness. During the discussion phase, it became (more) clear that the proposed method is best used to reduce the communication overhead of ZeRO3. While the integration of this work and ZeRO hasn't been attempted yet, the authors claim that this work "clears the theoretical barrier". From that point of view, the reviewers were not satisfied with the guarantees of the method, arguing that the resulting algorithm is slower than standard EF and could suffer in terms of runtime (when one factors the cost of compression) even when compared to standard uncompressed SGD. Overall, the discussion greatly improved the paper, although directly integrating ConEF with ZeRO could be even more convincing.
Decision: Reject