Rethinking gradient sparsification as total error minimization
Authors: Atal Narayan Sahu
Aritra Dutta
Ahmed M. Abdelmoniem
Trambak Banerjee
Marco Canini
Panos Kalnis
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Gradient compression
Distributed optimization

Abstract: Gradient compression is a widely-established remedy to tackle the communication bottleneck in distributed training of large deep neural networks (DNNs). Under the error-feedback framework, Top-$k$ sparsification, sometimes with $k$ as little as 0.1% of the gradient size, enables training to the same model quality as the uncompressed case for a similar iteration count. From the optimization perspective, we find that Top-$k$ is the communication-optimal sparsifier given a per-iteration $k$ element budget.
We argue that to further the benefits of gradient sparsification, especially for DNNs, a different perspective is necessary — one that moves from per-iteration optimality to consider optimality for the entire training.

We identify that the total error — the sum of the compression errors for all iterations — encapsulates sparsification throughout training. Then, we propose a communication complexity model that minimizes the total error under a communication budget for the entire training. We find that the hard-threshold sparsifier, a variant of the Top-$k$ sparsifier with $k$ determined by a constant hard-threshold, is the optimal sparsifier for this model. Motivated by this, we provide convex and non-convex convergence analyses for the hard-threshold sparsifier with error-feedback. We show that hard-threshold has the same asymptotic convergence and linear speedup property as SGD in both the case, and unlike with Top-$k$ sparsifier, has no impact due to data-heterogeneity. Our diverse experiments on various DNNs and a logistic regression model demonstrate that the hard-threshold sparsifier is more communication-efficient than Top-$k$.

Rethinking gradient sparsification as total error minimization
Atal Narayan Sahu KAUST
Aritra Dutta KAUST
Ahmed M. Abdelmoniem
KAUST
Trambak Banerjee University of Kansas
Marco Canini
Panos Kalnis KAUST
KAUST
Abstract
Gradient compression is eadell-established remedy to tackle the communication bottleneck in distributed training of large deep neural networks (DNNs). Under the error-feedback framework, Top-k sparsification, sometimes with &t little as 0.1% of the gradient size, enables training to the same model quality as the uncompressed case for similar iteration count. From the optimization perspective, we find that Top-k is the communication-optimne sparsifier given a per-iteration k element budget. We argue that further the benefits of gradient sparsification, especially for DNNs, a different perspective is necessary per-iteration optimality to consider optimality for the entire training.
one that moves from
We identify that the total error the sum of the compression errors for all it- erations encapsulates sparsification throughout training. Then, propose communication complexity model that minimizes the total error under a commu- nication budget for the entire training. We find that the hard-threshold sparsifier, a variant of the Top-k sparsifier with & determined by a constant hard-threshold, is the optimal sparsifier for this model. Motivated by this, provide convex and non-convex convergence analyses for the hard-threshold sparsifier with error- feedback. We show that hard-threshole has the same asymptotic convergence and linear speedup property as SGD in both the case, and unlike with Top-k sparsifier. has impact due to hetto-hetrroeneiity. Our diverse experiments on various DNNs and logistic regression model demonstrate that the hard- threshold sparsifier is more communication-effiiiee. than Top-k. Code available at https: / / thub. com/sands sands wwwabb/ehhiniing--eee wwt.sspppssssiiiiiooioii
Introduction
With the emergence of huge DNNs consisting of hundreds of millions to billions of parameters [12, 50], distributed data-parallel training [66] is an increasingly important workload. As the training process typically spans several compute nodes (or workers) that periodically exchange the local gradient vectors at each iteration of the optimizer (e.g., SGD), communication among nodes remains in many cases the main performance bottleneck [32, 40, 46).
Lossy gradient compression techniques are becoming common approach rein communication efficiency [62]. In particular, sparsification, which sends only subset of gradient coordinates (e.g., Top-k [4, 8) sends the largest gradient coordinates by magnitude each iteration), may significantly reduce data volumes and thus speed up training. However, due to its lossy nature, compression raises a complex trade-off between training performance and accuracy. For instance, Agarwal al. [3] note that training ResNet-18 CIFAR- 100 using sparsification speeds up training significantly (3.6x), also degrades final accuracy by 1.5%. the other hand, Lin et al. [37] reports a 500x data
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

10
gisette. workers
EF SGD Top 17%
10
gisette, 20 workers
gisette. workers
FF :50 Top 17%
EF SGD Hart threshoi--.22
17-500 ltars threshole-4.2
10
500
10"1
1
[mslj]
3
10
30--
10-3
10
Epech
Number of bit per worker 105
10
(a)
(b)
(c)
Figure 1: Convergence of Top-k and Hard threshhre for a logistic regression model on gisette LIBSVM
dataset with 20 workers: (a) Functional suboptimality vs. epochs; (b) functional suboptimality vs. bits communicated; (c) error norm vs. epochs. Hard-threshold converges as fast as the baseline, no compression SGD and much faster than Top-k because of smaller total-error than Top-k.
reduction via sparsification under deep gradient compression (DGC) for ResNet-50 on ImageNet while preserving the same final accuracy when adopting a carefully-tuned warmup phase.
The vast literature on gradient compression largely considers a fixed communication budget per iteration while leaving it up practitioners grapple with specifying an additional hyper- parameeree that determines the degree of compression before training begins. Mcanwhile, recent adaptive Top-k sparsifiers [3, 65] empirically demonstrate that tuning the degree of compression in different phases of DNN training yields a more communication-effiiian (e.g., static le for Top- However, these works lack a theoretical framework proving that adaptive compression enjoys better convergence guarantees than the fixed compression scheme.
scheme than a fixed compression scheme
This raises fundamental question: Given fixed communication budget, is there a provably better communication scheme than fixed per-iteration compressed communication? We first observe that Top-k is the communication-ope Then, our insight is that by adopting a different perspective that accounts for the effect of sparsification throughout training, more efficient communication scheme is possible under revised notion of optimality that considers an overall communication budget (instead of a per-iteration budget).
sparsifier for fixed per-iteration communication budget ($4.3).
We consider sparsification by using the error-feedback (EF) mechanism [8, 53], delayed gradient component update strategy that instrumental for the convergence of the state-of-the-ard sparsifiers [10]. Let e, denote the error arising due to sparsification at iteration t. In EF, this error is added to the gradient update at iteration & ++1 1. We identify that the term affecting the non-convex convergence in EF-SGD is the total-error: Eellex1 [33, 54].
Directly minimizing the total-error is not possible; thus, Top-k minimizes ||&]|3 at each iteration. We argue that it is possible to focus the sum of el and devise a communication scheme that achieves smaller total-error than any fixed communication sparsifier. We demonstrate that to achieve this change of perspective; is sufficient to consider practical yet straightforward mechanism that is a natural counterpart of Top-k: the hard-threshun coordinates with magnitude greater than or equal to a fixed given threshold, À > in each iteration. Although the two sparsifiers are in an equivalence relation (a given À corresponds to a k), under the total-error minimization perspective, we adopt fixed threshold, A, which implies a variable ic at every iteration.
sparsifier, which communicates the gradient
To illustrate intuitively why this change of perspective yields benefits, consider the following example. Figure shows an experiment in the distributed setting where 20 workers train a 6, 6.000-parameter logistic regression model on the gisette LIBSVM dataset [14] by using the Top-k and hard- threshoid sparsifiers, configured to send the same data volume." The loss function is strongly convex and has a unique minimizer, x=" therefore, a unique optimum, f(x*). We see that hard-threshold converges at the same speed as SGD while communicating ~ 600x less data, whereas Top-k has a significantly slower convergence speed. We attribute this to the fact that Top-k has a large error accumulation in the initial 500 iterations, while the error magnitude for tard-threshold is less than 0.04 throughout training (cf. Figure Ic). Our results with DNN training also reflect this insight ($6).
We train for 10 epochs and set 0.17% for Top-k, and x = 4.2 for hard-threshold

---

Moreover, the thrrdhhheehold sparsifier has computational benefits over Top-k sparsifier, as hard- threshold's underlying filtering operation requires d comparisons in each iteration, where d is the number of parameters. In contrast, Top-k is a compute-intensive sparsifier (e.g., on CPU, the computational complexity is Oddogg, k) [48]). For GPUs, several optimized implementations are proposed but they rely on the data distribution and are efficient only for small k [48]. For instance, PyTorch uses Radix select algorithm [5] which has a computational complexity of O ([6/r] d) where b is the number of bits to represent gradient values and is the radix size [42].
Finally, while the hard-threshold sparsifier already exists in the literature [20, 55], we are the first to formally study it and theoretically demonstrate its benefits as an adaptive counterpart of Top-k. Moreover, our argument favor of hard-threshole precisely falsifies the claim by Dryden et al. [18] that stopped its widespread adoption a hard-threshold may lead to degenerate situation when the EF in gradient compression builds up.
This paper makes the following contributions:
Communication complexity model ($4). We propose a communication complexity model that captures the effects of compression in the entire optimization process. We allow for variable communication each iteration by only imposing a total communication budget. We show that the hard-threshold sparsifier is the communication-optinal sparsifier in this model.
Absolute compressors ($5). We identify that the hard-threshole sparsifier, along with other existing compressors [16, 46), belongs to the class of absolute compressors, which have an absolute bound on the error. Absolute compressors have not been formally studied before with EF. We show that absolute compressors with EF converge for both strongly convex and non-convex loss functions. In both cases, similar to the 5-contraction operators [33], absolute compressors enjoy the same asymptotic convergence with linear speedup (with respect to the number of workers) as no-compression SGD, However, ô-contraction operators have a worse dependence on 5 in the distributed setting with heterogeneous data, while absolute compressors do not have such an anomaly.
Experiments ($6). We conduct diverse experiments on both strongly convex and non-convex (for DNNs) loss functions to substantiate our claims. Our DNN experiments include computer vision, language modeling, and recommendation tasks, and our strongly convex experiment is on logistic regression. We find that the hard-threshold sparsifier is consistently more communication-eeffcccnn than the Top-k sparsifier given the same communication budget.
2
Related work
Gradient compression techniques be broadly classified into quantization [7, 16, 33, 47, 60),
sparsification [4, 37, 59], hybrid compressors [9, 18, 55), and low-rank methods [57, 58]. The state- of-the-art compressors are biased 5-contraction operators [37, 57], see $4.5. We refer to [62] for recent survey and quantitative evaluation of these techniques.
Error-feedback (EF) or memory was first empirically used in [47, 55]. However, [33, 53, 54] were the first to give convergence analysis of the EF framework, which was extended to the distributed setup in [10, 64). Recently, [61] proposed error-reset, a different form of EF, while [29] introduced another alternative by communicating compressed version of the error. EF has also been combined with variance- reduution [22, 43] and acceleration [44].
Communictiion-ptinall compression. [6. 15, 21, 45] devised a communication-optinna compres- sor by minimizing the worst-case compression factor² under per-vector communication budget.
Adaptive compression. [59] designed an adaptive sparsifier that minimizes expected sparsity of the compressed vector under given variance budget. While AdaQS [23] periodically doubles the quantization states in QSGD [7] to reduce the compression factor, DQSGD [63] sets the number of quantization states proportional to the gradient norm. ACCORDION [3] chooses a low compression ratio if training is in a critical regime [2], and high compression ratio otherwise.
For vector x and possibly randomized compression operator C, we denote the compression error as Ec [|le- C() and compression factor Ee[l|æ ((=)\]
3

---

Efficient Top-k estimation is focus of many recent works. While [37] estimates the Top-k threshold on randomly sampled subset, [1. 49] estimate it by fitting parametric statistical distributions, [25] estimates the threshold every 1, 000 iterations. These works determine threshold to approximately determine a fixed Top-k set, while we use hard-threshold to determine the k in each iteration.
Background on Error-Feedback (EF) SGD
Consider the following distributed optimization problem with workers:
(1) where fz(x) =(z===EE<p (æ; z) denotes the loss function evaluated input sampled from Dj, the data-distribution at the jth worker. Let 9i. denote the stochastic gradient computed at ith worker at iteration such that gi.t = Vf(()+) + Ei.t with [( 0.
min f(x) n Eie(n) f((z),
Algorithm gives the pseudo-code of compressed EF SGD [8, 33, 53] to solve (I). Let e denote the locally accumulated error at 5th worker due to compression from previous steps. Adding this error the current gradient, Troki provides the corrected update, Pi,t, where Ti is the step-size. This corrected update is further compressed and exchanged with other machines, and the local error updated for the next step.
Algorithm 1: Distributed EF SGD
Input: C-compressor
Initialize 2n E R for worker i [n]] in parallel do
Initialize error 6i.0 = 0;
for iteration 1 0,..., 1 do
Pi,t t- Ei,t + Tefiit
/* Incorporate EF into update */;
Dit - 7:01 (1())
e1111 Pi,t Ds,t
/* Update error */;
A 1 Eiein Di,
/* Exchange and average Di, among workers */:
Tt+1 < Ft A
Remark 1. In Algorithm 1, we have A.,. + 7CC( while [8, 33, 53] consider A., + C(p.,))
We do this to extend the EF framework for absolute compressors. We note that Algorithm is more general as 7.C( (Pa)) is equivalent to C(pa,) for all known 8-contraction operators.
3.1 Assumptions
We consider the following general assumptions the loss function.
Assumption 1. (Smoothness) The function, ft Rd + R at each worker, E [n] is L-smooth, i.e. for every I, y E Rd we have, f((y) S f((x) + (V - x) + fly x1|2. Assumption 2. (Global minimum) There exists x² such that, f(=*) f f" S f()), all x E Rdd. Assumption 3. (M,,0²) bounded noise) [54] For every stochastic noise Ei,,, there exist M, 2 2 such that Eii|E,, 22a] fe
0². f22.fo for all 24; E Rdd.
Remark 2. The above assumption implies 1E[1.,..: [x]] I (M + (=) + This general noise model does not uniformly bound the second moment of stochastic gradients as in [9, 33, 64]. Assumption 4. ((C,3²) bounded similarity) The variance of gradients among workers is bounded, i.e., there exist constants, C, 2 O such that, 1 Eie(m) f((x)) - v f=x) < C(V)f(=)l1 <², for all I E Rdd.
Remark all the workers have the same training data, all f, are the same, resulting in C, = 0. This assumption is extension from [31, 36), which consider C =
For the convergence of strongly convex functions, we require an additional assumption as follows.
Assumption 5. (u-strong convexity) The functions, fi RRd - R are p-strongly convex, Lee, there exists 0, such that f.(v) 2 f((z) + ((())) z) + $| for all x e Bd.

---

Convergence of EF-SGD. The following result shows the convergence of EF-SGD [33] in minimiz ing general smooth functions for a single worker 1) case.
Theorem 1. [33, 54] Let Assumption and hold. Then Algorithu I with constant step-size, ? where Y S ZL(M+1J and n follows
T B[VS(E)) 4(f(20) 1*) Lo² + 2L TT
T-1
B gt + -(( + 2)12
T
Remark 4. Theorem is simplified version of the distributed for n 1 and quoted emphasize the effect of compression between the error-corre cror-corrected gradient, + 7. and its compressed form, Clg + ))) The term that solely accounts for the effect of compression in the entire training process
is the torol- E Blee+1ll ΣE " + C(ge 9)]1
4 A communication complexity perspective to sparsification
We now propose a communication complexity model and contrast it with the existing communication- optimal strategies. We note that our of the word commmniccation-opiinal is in the sense of optimization upper-bounds. Convergence analyses of compressed SGD capture the effect of compres- sion via the compression error, and this effect is always inverse the lower the compression error, the better the optimization upper bound [22, 29]. Therefore, ours and the existing works [6, 15, 21, 45] design communication-opiine strategies by optimizing the compression eπror related term. We start with sparse approximation problem that we encounter in our subsequent discussions.
4.1 A sparse approximation problem
Let Im be given vector. We want to approximate p with sparse vector, q, that has at most < T S m nonozeer zero elements. Formally, we write the constrained sparse approximation problem as:
/' = arg minger" |p - gl| subject to l///lo ST,
(2)
where || denotes the number of non-zero elements in a vector. Problem (2) and its variants are well studied and arise in signal processing [13, 17, 19] and matrix approximation [11, 51].
Lemma 1. The solution q* to (2) is obtained by keeping Top-r magnitude entries from and setting
the rest to
4.2 Minimizing the total-error is not possible
Let denote the class all compressors. We constrain to class of deterministic sparsifiers, denoted by S C e, but one can similarly consider other subclasses in C. For each E Rd deterministic sparsifier, Cp with sparsification parameter, p determines a sparse support set, Sp(z) S [d] and sparsifies
Cp(x) Eies,(a) a/i]e,
where e; denotes the ith standard basis IRd, and .i denotes the corresponding element in z. For example, for hard-threshold sparsifier, Cx. we have (x)x {i |=[i]]| > λ}. Motivated by Theorem and Remark 4, we now propose the following communication complexity model:
T-1 Σ
min CES
E gt
+ Et. C(g.
Ct 11
subject to
[C(g
- 1o S
(3)
where K is the budget the number of clements communicated in T' iterations. However, solving (3) is intractable owing to complex DNN loss functions and multiple sources of randomness.
4.3 Top-k communication-optine for a per-iteration element budget
To simplify (3), one can focus individually at the enror at each iteration. Based on this, we show in Lemma that Top-k has the best compression error among all sparsifiers under per-iteration k-element communication budget.
5

---

Lemma 2. Given the gradient and ervor at iteration t. Top-k sparsifier achieves the optinal objective for the optimization problem:
min CES
gt
Clge + 7 )) subject to [|C(g: + Et et ?
? )lo S k.
(4)
Similar Lemma (4) is solved when Cgg + )) contains the k highest magnitude elements of g 7
St. That is, when C is the Top-k sparsifier. Additionally, based the above model, per-iteration k-element communication budget (resulting in a total budget of kT' elements throughout training), implies that Top-k is performed at each iteration. However, have a more communication-efficie compression, we require a communication complexity model that (i) better captures total-error in Theorem I; and (ii) allows for adaptive communication, i.e., sends variable data in each iteration.
4.4 A communication complexity model for adaptive sparsification
Although the total-error cannot be minimized ($4.2), Lemma 2 motivates us to consider simplified model that can capture the total-error. Instead of (ge &
7 o we consider a fixed sequence (a:)
and examine the following communication complexity model:
minces Ei |0. - C(a))ll subject to Ei IIC(a:)llo S K,
(5)
where K E N denotes the total communication budget. For the sake of simplicity, we assume that no T-1 two elements in (==) have the same magnitude.
Let A E Rd be formed by stacking (a, (To vertically and consider the following sparse approxima- tion problem:
min ||A - B|I subject to ||B||o S K,
(6)
Note that (6) allows for all B that formed by stacking (C(a,)) T-1 vertically, for some sparsifier satisfying Σl [[C(a))]lu I K. Therefore, the optimal objective for (6) lower bound to the optimal objective for (5). Let A(s denote the element with zth largest magnitude in A, and since no two elements have the same magnitude, we have, A(i+1) + A(a), for all E [dZ]]. Then, B = (A) with X E (A(K+1): A(K)] contains the Top-K magnitude entries from A, and therefore, by Lemma I optimal for (6). Moreover, since hard-threshold an element-wise sparsifier, (A) equivalent to stacking (Cx (a))) vertically. Therefore, C2 with > (A(K+1): A(r)] achieves optimal objective in (5). The following lemma formalizes this.
Lemma 3. Cx is optimal for the communication complexity model (5). That is, for every budget K, there exists X 2 0 such that Cx minimizes (5).
4.5 Discussion
To capture the effect of compression, existing works [7, 33, 53) use a bound on the compression
factor, maX Re]1((=)==11 We formally define them relative compressors.
|
Definition 2. Relatiye Compressor [7, 53]. An operator, C Rd - Rdd is a relative compressor if for all vector, x Rdd it satisfies
Ecl (x)) < 2|/=
where Ω > 0 is the compression factor and the expectation, EE, is taken with respect to the randomness of C. 8-contraction operators [33, 53] with Ω 1 - and 8 (0, 1]. are special cases of relative compressors.
Top-k ô-contraction operator with 8 [53]. Therefore, by (7), Top-k allows for larger compression eтror with larger inputs. Our communication complexity model demonstrates that this might not necessarily be good idea. Moreover, with EF, large error at any iteration has a cascading effect - a large e, results in large 79t + Ct. out of which only k/d fraction of the total components are kept by the Top-k strategy. This results in a large et+1 (see $C.2). Figure shows that this error-buildup has severe implications on the total-error. On the other hand, the hard-threshold performs a variable Top-k in each iteration and sends an element as soon as magnitude bigger than the threshold. This prohibits the error build-up.

---

Comparison with existing communication- compression strategies. Since the compres- sion factor, 12 solely determines the effect of compression convergence [29, 54], many recent works [6, 15, 21, 45] propose communication-onn -optimall compression strategies by optimizing for St under communication budget for each vector, i.e., they propose to solve
Bellæ - C(x))1 subject to Bits(C(()) - B,
min max CEC ZER4
|
where (Cz) denotes the number of bits needed to encode C(x). We stress that while the compression affected term in Theorem has the sum of compression errors over the iterations, the above communication complexity model only captures the compression factor.
Absolute compressors and their convergence
Motivated by the previous section, we formally define absolute compressors compressors that have an absolute bound on the error.
Definition 3. Absolute Compressor. An operator, C : IRd + Rd is an absolute compressor there exists >> 0 such that for all vectors, z E Ed it satisfies
EE || C(x)]l < v².
In contrast the relative compressors (7), the compression error (or variance) absolute com- pressors is bounded by a constant, independent of Based on the above definition, hard-threshold is an absolute sparsifier with 2² = dx². The stochastic rounding schemes, used for model quantization, with bounded rounding error in [24] are absolute compressors. Precisely, any rounding scheme, with rounding error bounded by e, is an absolute compressor with 2² de². Similarly, the scaled integer rounding scheme in [46] is absolute compressor. While this class of compressors existed in the literature, we are the first to provide their convergence result with an EF.
5.1 Convergence results
Inspired by [54], establish convergence of EF-SGD (Algorithm 1) with absolute compressors. Convergence analysis for the momentum case [64] can be extended similarly. However, we do not include it for brevity, and the existing analyses do not show any benefit over vanilla SGD. Similarly, analysis for error-reset [61] and local updates [9, 61] can also be extended. We provide convergence results for the convex and non-convex cases and compare them to 5-contraction operators. We start with bound on the eтror for absolute compressors.
Remark 5, (Error bound) For all E [m], E {0,... T 1}. we have
Ee Ee P.,.] = Eellp,, nCC Put )|1 Bel Pad - C(P )|2 < 2??u0.
7
similar absolute bound for 5-contraction operators requires the bounded gradient assumption [33, 9], but absolute compressors achieve this by design.
5.1.1 Convex convergence
1. Et= W.Ft be the weighted average of the iterates with weights, we 2 0 and Let Ë7 = WT
W7 = ΣT Wt. Additionally, let Pe := [[f( f be the expected suboptimality gap at the average iterate. Further denote R; := || - 2 and D : 1 Σn [x* With these notations, we quote the strongly convex (/1 > 0) and convex (μ+ 0) convergence results for absolute compressors, and compare them with the 5-contraction operators from [10] for distributed case (n 1). The results below are for specific choices of step-sizes and weights; we refer to $B.4.1 13.4. for these choices.
Theorem 4. Let 0 and Assumptions 1, 2, 3, and 5 hold. Then the iterates, {2e of Algorithm 1 with an absolute compressor, Cy, constant step-size, 7(T) with (TT S 4L(1 41(142M/n) follow?
Pr = Ô [LRo(1 + M/n) exp
nT
2 p
Lo²
8L(1+2M/p)
FTT2
"The Ô notation hides constants and factors polylogarithmic in the problem parameters.
7

---

Remark 6, Under the same setting as in Theorem 4, iterates of Algorithm 1 with 5-contraction operators follow:
Pr = [RRo ( exp
VI+Mē
nOT 16V31.22+M8
MMD pni
L(D(1+ M0)+
Remark implies, in distributed settings with heterogeneous data (D of 0), d-contraction operators have 1/0² dependence on compared 1/6 dependence in the homogeneous case (D 0).
In contrast, absolute compressors have the same v² dependence on both cases. Therefore, we conjecture it is beneficial to use absolute compressors in settings such as federated learning [38]. where data heterogeneity is widely encountered.
Let and Assumptions 1, 2, 3, and 5 hold with D o O. Then the iterates, f2rh120 of Algo. I with an absolute compressor, Cu, a constant step-size, ((T') with 7(T) S T6(14MM/M) follow
Theorem 5.
40 VnT
L(1+M/m) Ra
Pr=
Remark 7. Theorem 5 holds when both 0² and D are simultaneously zero. Typically, encounter heterogeneous data settings where D + O, and Theorem 5 holds. In case both o² and D
zero, get O (LuRo)ã L(1+M/n))RR) convergence. T$
Remark 8. Under the same setting as in Theorem iterates of Algorithm with 8-contraction operators follow:
V(o2-MD)R
Ro
P1 0
VnT
Similar to Remark 6, we observe that ò-contraction operators have 1/62 dependence on å in heterogeneous case, and 1/8 dependence in the homogeneous case, while absolute compressors have no such anomaly.
Designing vuriance-reduces algorithm [22, 43, 44] by using absolute compressors with EF is fruitful direction of future research.
5.1.2 Non-convex convergence
Theorem 6. (Non-convex convergence of absolute compressors) Let Assumptions 1, 2, 3, and hold. Then the iterates, (21)12 of Algorithm with an absolute compressor and constant step-size
S 2L(MCC 1))n) follow
-I- B[V 4(f(m))-(") 7T
+ 2+L(MC++0²) + 222
Alongside, we compare with the non-convex convergence for ô-contraction operators distributed setting. The existing analyses tackle this by using a stronger uniform bounded gradient assumption [64, 33, 20). We use weaker Assumption and 4, to establish the convergence analysis.
Theorem 7. (Non-convex convergence of ò-contraction operators) Let Assumptions 1. 3, and 4 hold. Then the iterates, {zch120 of Algorithm I with 5-compressor and a constant step-size S min ZL(M[C+))4)) CC+ follow
ΣT= (() < 8if(zo)-/") LyL(M(
8,21² 5 ((3 + M) +
Again, similar to Remarks 6 and 8, for 8-contraction operators, we find the 1/82 (heterogeneous case, < + 0) vs. 1/6 (homogeneous case, < = 0) anomaly, while absolute compressors have u² dependence on in both homogeneous and heterogeneous cases.
Remark 9. With appropriate choices of step-size, both absolute compressors and 8-contraction operators with EFDSGD achieve the same ((IVVnIT) asymptotic rate of SGD. See Corollary I in $B.3 for the full result.

---

Tost Accune (58)
Test Purplesny
Bost treitto (%5
92
Boalnn
Top.t
Hoodne
Top.
Bouine
Topa
Hand Unooid
100
0.4
0.6
0.06
D.50
0.30
Average Deasiyy (8)
Deretty (56)
Average Deasity
(a) R8 on CIFAR-10
(b) LSTM on Wikitext
(c) NCF on Movielens220M
Figure 2: Test metric vs. Data volume. For benchmarks, average test quality with std. dev. over 3 runs. The
dashed black line denotes the no compression baseline.
Tiet Amurary (%6
y Jeuli
Tips Rep---0.665
Sold (55
1.0
86
2020
(000
0.3
Tog 4-40005
6000
2000
3000
3000
0000
6000
Nomber
Numiser (4)
(b)
(c)
Figure 3: Convergence of Top-k and Hard-threshold for ResNet-118 CIFAR-10 at 0.06% average density: (a) Test-accuracy vs. Iterations, (b) Error- norm vs. Iterations, (c) Density (ks/d) vs. Iterations.
k 0.06% of d, and À = 0.0072. hard-threshold has better convergence than Top-k because of a smaller total-error.
6 Experiments
Experimental setup. We compare Top-k and hard-threshold sparsifiers on image classification, language modelling. and recommendation tasks. We use different optimizers: vanilla SGD, SGD with Nesterov momentum, and ADAM [34]. All experiments were run on an 8-GPU cluster, using Allgather as the communication primitive. We perform compression in the standard layer-wise fashion [20, 37, 47] and follow the EF strategy used in [57]. For hyper-paramett configuration, comparison with entire-mode compression, discussion on different EF approaches, experiments without EF, and experiments with logistic regression, we refer to Appendix C.
Test metric vs. Data volume. We tune the sparsification parameters for both sparsifiers such that they send similar total data volumes during training. We use average density: 7 >E=00 iy as a measure of total data volume, where k₃ denotes the number of elements transmitted in iteration t. Figure 2 shows the average test quality across three repetitions with different initial random seeds. We observe that fixing the average density, hard- threshold consistently has better test performance than Top-k. For ResNet-18 18 on CIFAR-10, we observe that hard-thresher 1.12% almost achieves the baseline accuracy and better than Top-k at 0.75% density (~ 6x more total data volume). For LSTM on Wikitext, at an average density of 0.025%, thrd-dhreshold has 2 better perplexity than Top-k. For NCF on Movielens-20M. @it-Rate 10 at all considered average densities.
at an average density of
thre-hhd has > 1% better
We now demonstrate that hard-threshold has faster convergence because of smaller total-error in comparison to Top-k. In Figure 3, we introspect a run with average density of 0.06% from Figure 2a. In Figure 3a, while hard-threshold converges to an accuracy of 93.9%, Top-k achieves 91.1% accuracy. At the same time. in Figure 3b, we observe large aroor-cccmmlltion in the initial 200 iterations for Top-k: Consequently, thrs-threshold has a significantly lower total-error than Top-k: and therefore has better convergence. This observation about large error accumulation for Top-k is consistent across all our benchmarks (see SC.2).
Comparison against ACCORDION. We compare against the state-of-the-an adaptive sparsifier: ACCORDION [3] on CIFAR- 10 and CIFAR- 100 datasets. ACCORDION shifts between two user- defined k values: kmax and kmin by using Top-himx when the training is in a critical regime, else using Top-kunnn We compare against ACCORDION with hard-threshold À experiment details; see $C.4.
For complete 2/Emi
We report the CIFAR-10 result Table 1, while the CIFAR-100 result is reported in $C.4. Each setting is repeated with 6 different seeds and report the average. For the CIFAR- 10 dataset,

---

Table 1: Comparison against ACCORDION [3] on CIFAR-10.
Network
Method
Accuracy (%)
Average Density (%)
Top-1 Okmax /d)
94.1
1.00 (1x)
Top-0.1% 1% (kmin/ /d)
93.2
0.10 (10x)
ResNet-18
ACCORDION
93.5
0.53 (1.9x)
94.0
0.13 (7.7x)
Top-19 1% (kmaxx (d)
94.1
1.00 (1x)
Top-0.1% (Bimin/ (d)
92.9
0.10 (10x)
GoogleNet
ACCORDION
93.4
0.47 (2.1x)
Hard-threshold
94.2
0.13 (7.7x)
Top-1% O6maxx /d)
94.0
1.00 (1x)
Top-0.1% 1% (Kenin/
92.5
0.10 (10x)
SENe118
ACCORDION
93.5
0.47 (2.1x)
Hard threshold
94.2
07.4
we observe that hard-threshoid has 0.5% 0.8% higher test accuracy than ACCORDION and is approximately 3.5x more communication efficient than ACCORDION, For the CIFAR- 100 dataset, except the ResNet-18 18 model, observe that hard- threshold obtains more than 0.8% higher accuracy than ACCORDION with more than 1.26x communication savings over ACCORDION.
How to tune the hard-threshold? We use the non-convex convergence results from $5.1.2 to suggest a hard-threshold value which has better convergence than Top-k with parameter & for non-convex loss functions (including DNNs). Let M, Č, and be the estimates of M, S. and a, respectively, in
VE ( + A Ç² + ;²; discussion in SD.
Assumptions 3 and 4. We set the threshold À
The À in Table is derived from simplifying this formula. But how to tune the hard-threshhe such that it achieves co-oompression bascline performance with the least total-data transmission remains an open question. We remark, as of now, this question remains unanswered for Top-k as well.
When and when not to use hard-threshold? In a standard cluster setting with a dedicated network, the speedup in terms of per-iteration training time due to gradient compression depends the characteristics of the DNN being trained [46]. One of the determining characteristics is the extent to which the communication phase overlaps with computation. If the fraction of non-overlapped communication is significant, then communication is bottleneck, even if Top-k compression is applied. However, in the case of hard-threshold sparsification (configured for the same total commu- nication volume), during iterations with high data transmission, the non-overlapped communication remains; but during iterations with low data transmission, non-overlapped communication reduces, thereby reducing the overall training time. On the other hand, if there is complete overlap between computation and communication for Top-k, then hard-threshold with the same total communication volume may introduce overllppee communication in some iterations with high data transmission, thereby increasing overall training time. Here, we ignored two important aspects of hard-threshold (i) thrr--hreshoodd may require fewer iterations to a target accuracy owing to its better statistical efficiency, and that (ii) threshl has negligible computation overhead in comparison Top-k.
7 Conclusion
We proposed total-error perspective to compressed communication that captures the effect of compression during the entire training process. Under this, we showed that the hard-threshold sparsifier is more communication-eflicienn than the state-of-the-art Top-k sparsifier, and is a principled way to perform adaptive sparsification. Absolute compressors the class of compressors in which -erethheehold belongs have promising convergence in the heterogeneous data settings, which is a prominent issue in Federated Learning [38]. As the EF framework is also applicable to Local SGD [52), we hope that this inspires more communication-effiee determine when to communicate, rather than naively communicating in fixed intervals. Furthermore, similar to hard-threshold, we believe adaptive absolute compressor counterparts of quantization schemes and low-rank methods can also be developed.
versions Local SGD that adaptively
10

---

Acknowledgements
We thank Chen- Yu Ho and Hang Xu for many helpful discussions and the reviewers for their feedback. For computer time, this research used the resources of the Supercomputing Laboratory at KAUST.
References
[1] A. M. Abdelmoniem, A. Elzanaty, M-S. Alouini, and M. Canini. An Efficient Statistical-based Gradient Compression Technique for Distributed Training Systems. In MLSys, 2021.
[2] A. Achille, M. Rovere, and S. Soatto. Critical Learning Periods in Deep Networks. ICLR, 2019.
[3] S. Agarwal, H. Wang, K. Lee, S. Venkataraman, and D. Papailiopoulos. Accordion: Adaptive Gradient Communication via Critical Learning Regime Identification. In MLSys, 2021.
[4] A. F. Aji and K. Heafield. Sparse communication for distributed gradient descent. In EMNLP, 2017.
[5] Alabi, D. Blanchard, B. Gordon, and R. Steinbach. Fast K-Selection Algorithms for Graphics Processing Units. ACM J. Exp. Algorithmics, 17, October 2012.
[6] A. Albasyoni, M. Safaryan, L. Condat, and P. Richtárik. Optimal Gradient Compression for Distributed and Federated Learning. arXiv 2010.03246, 2020.
[7] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. QSGD: coamuumication-Efficcenn SGD via Gradient Quantization and Encoding. In NeurlPS, 2017.
[8] D. Alistarh, Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli. The Convergence of Sparsified Gradient Methods. In NeurlPS, 2018.
[9] D. Basu, D. Data, C. Karakus, and S. Diggavi. Qsparse-lcal--SGD: Distributed SGD with Quantization, Sparsification, and Local Computations. In NeurlPS, 2019.
[10] A. Beznosikov, S. Horváth, P. Richtárík, and M. Safaryan. On Biased Compression for Distributed Learning. arXiv 2002.12410, 2020.
[11] Boas, A. Dutta, X. Li, K. Mercier, and Niderman. Shrinkage Function And Its Applications In Matrix Approximation. The Electronic Journal of Linear Algebra, 32, 2017.
[12] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss. G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei. Language Models are Few-Shot Learners. In NeurIPS, 2020.
[13] K. Bryan and T. Leise. Making Do with Less: An Introduction to Compressed Sensing. SIAM Review, 55(3), 2013.
[14] C-C Chang and C-J Lin. LIBSVM: A Library for Support Vector Machines. ACM Trans. Intell. Syst. Technol., 2(3), 2011.
[15] W.-N. Chen, P. Kairouz, and A. Ozgur. Breaking the Hummunicatoon-PiivcyyACcoo Trilemma. In NeurIPS, 2020.
[16] T. Dettmers. 8-Bit Approximations for Parallelism Deep Learning. In ICLR, 2016.
[17] D. L. Donoho. Compressed sensing. IEEE Transactions on information theory. 52(4), 2006.
[18] N. Dryden, T. Moon, S. A. Jacobs, and B. V. Essen. Communication Quantization for Data- Parallel Training of Deep Neural Networks. In MLHPC, 2016.
[19] A. Dutta. Weighted Low-Rank Approximation of Matrices: Some Analytical and Numerical Aspects. PhD thesis, University of Central Florida, 2016.

---

[20] A. Dutta, E. H. Bergou, A. M. Abdelmoniem, C.-Y. Ho. A. Sahu, M. Canini, and P. Kalnis. On the Discrepancy between the Theoretical Analysis and Practical Implementations of Compressed Communication for Distributed Deep Learning. In AAAI, 2020.
[21] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar. vqSGD: Vector Quantized Stochastic Gradient Descent. arXiv 1911.07971,2011
[22] E. Gorbunov, D. Kovalev, D. Makarenko, and P. Richtarik. Linearly Converging Error Compen- sated SGD. In NeurIPS, 2020.
[23] Guo, W. Liu, W. Wang. J. Han, R. Li, Y. Lu, and S. Hu. Accelerating Distributed Deep Learning By Adaptive Gradient Quantization. In ICASSP, 2020.
[24] S. Gupta, A. Agrawal, K. Gopalakrishnan, and P. Narayanan. Deep Learning with Limited Numerical Precision. ICML, 2015.
[25] V. Gupta, D. Choudhary, T. P. Tang, X. Wei, X. Wang, Y. Huang, A. Kejariwal, K. Ram- chandran, and M. W. Mahoney. Fast Distributed Training of Deep Neural Networks: Dynamic Communication Thresholding for Model and Data Parallelism. arXiv 2010.08899, 2020.
[26] K. He, X. Zhang, S. Ren, and J. Sun. Deep Residual Learning for Image Recognition. In CVPR, 2015.
[27] X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T.-S. Chua. Neural Collaborative Filtering. In WWW, 2017.
[28] S. Hochreiter and J. Schmidhuber. Long Short-Term Memory. Neural Computing, 98)), 1997.
[29] S. Horváth and P. Richtarik. A Better Alternative to Error Feedback for Communication--Fficci Distributed Learning. In ICLR, 2021.
[30] J. Hu, L. Shen, and G. Sun. geueeze-and-exxitatie networks. In CVPR, 2018.
[31] P. Jiang and G. Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In NeurlPS, 2018.
[32] Y. Jiang, Y. Zhu, C. Lan, B. Yi, Y. Cui, and C. Guo. A Unified Architecture for Accelerating Distributed DNN Training in Heterogeneous GPU/CPU Clusters. In OSDI, 2020.
[33] S. P. Karimireddy, Q. Rebjock, S. U. Stich, and M. Jaggi. Error Feedback Fixes SignSGD and other Gradient Compression Schemes. In ICML, 2019.
[34] D. P. Kingma and J. Ba. ADAM: A Method for Stochastic Optimization. In ICLR, 2015.
[35] A. Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto, 2009.
Technical report,
[36] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and Liu. Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent. In NeurlPS, 2017.
[37] Y. Lin, S. Han, H. Mao, Y. Wang, and W. Dally. Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training. In ICLR, 2018.
[38] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. Agüera y Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. In AISTATS, 2017.
[39] S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer Sentinel Mixture Models. In ICLR, 2017.
[40] D. Narayanan, A. Harlap, A. Phanishayee, V. Seshadri, N. R. Devanur, G. R. Ganger, P. B. Gibbons, and M. Zaharia. PipeDream: Generalized Pipeline Parallelism for DNN Training. In SOSP, 2019.
[41] Y. Nesterov. Lectures Convex Optimization, volume 137. Springer, 2018
12

---

[42] PyTorch. https://pytorch: org/.
[43] X. Qian, H. Dong, P. Richtárik, and T. Zhang. Error Compensated Loopless SVRG for Distributed Optimization. In Workshop on Optimization for Machine Learning, 2020.
[44] X. Qian, P. Richtárik, and T. Zhang. Error Compensated Distributed SGD Can Be Accelerated. arXiv 2010.00091, 2020.
[45] M. Safaryan, E. Shulgin, and P. Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 2021.
[46] A. Sapio, M. Canini, C-Y Ho, J. Nelson, P. Kalnis, C. Kim, A. Krishnamurthy, M. Moshref, D. Ports, and P. Richtarik. Scaling Distributed Machine Learning with In-Network Aggregation. In NSDI, 2021.
[47] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-Bit Stochastic Gradient Descent and Application Data-Parallel Distributed Training of Speech DNNs. INTERSPEECH, 2014.
[48] A. Shanbhag, H. Pirk, and S. Madden, Efficient Top-K Query Processing on Massively Parallel Hardware. In SIGMOD, 2018.
[49] S. Shi, X. Chu, K. C. Cheung, and S. See. Understanding Top-k Sparsification in Distributed Deep Learning. arXiv 1911.08772 2019.
[50] M. Shoeybi, M. Patwary, R. Puri, P. LeGresley, Casper, and B. Catanzaro. Megatron-LMM Training Multi-Billion Parameter Language Models Using Model Parallelism. arXiv 1909,08053, 2019.
[51] G. W. Stewart. On the Early History of the Singular Value Decomposition. SIAM review, 35(4), 1993.
[52] S. Stich. Local SGD Converges Fast and Communicates Little. In ICLR, 2019.
[53] S. U. Stich, J. B. Cordonnier, and M. Jaggi. Sparsified SGD with Memory. In NeurlPS, 2018.
[54] S. U. Stich and S. P. Karimireddy. The Envor-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Updates. Journal of Machine Learning Research, 21, 2020.
[55] N. Strom. Scalable Distributed DNN Training using Commodity GPU Cloud Computing. In INTERSPEECH, 2015.
[56] C. Szegedy, Wei L., Yangqing J., P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going Deeper with Convolutions. In CVPR, 2015.
[57] T. Vogels, S. P. Karimireddy, and M. Jaggi. PowerSGD: Practical Low-Rank Gradient Com- pression for Distributed Optimization. In NeurlPS, 2019.
[58] H. Wang, S. Sievert, S. Liu, Z. Charles, D. Papailiopoulos, and S. Wright. ATOMO: Communication--fficiennn Learning via Atomic Sparsification. In NeurIPS, 2018.
[59] J. Wangni, J. Wang, J. Liu, and T. Zhang, Gradient Sparsification for ciaamunication-Effciio Distributed Optimization. In NeurIPS, 2018
[60] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Chen, and H. Li. TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning. In NeurlPS, 2017.
[61] C. Xie, S. Zheng, O. Koyejo, I. Gupta, M. Li, and H. Lin. CSER: Communicaiion-ffficceentt SGD with Error Reset. In NeurlPS, 2020.
[62] H. Xu, C.-Y. Ho, A. M. Abdelmoniem, A. Dutta, Bergou, K. Karatsenidis, M. Canini, and P. Kalnis. GRACE: A Compressed Communication Framework for Distributed Machine Learning. In ICDCS, 2021.
[63] G. Yan, S-L Huang, T. Lan, and Song. DQ-SGD: Dynamic Quantization in SGD for Communication-Efica Distributed Learning. arXiv 2107.14575, 2021.
13

---

[64] S. Zheng, Z. Huang, and J. T Kwok. Communication- Distributed Blockwise Momen- tum SGD with Freor-kedd.ck. In NeurlPS, 2019.
[65] Y. Zhong, C. Xie, S. Zheng, and H. Lin. Compressed Communication for Distributed Training: Adaptive Methods and System, arXiv 2105.07829, 2021.
[66] M. Zinkevich, M. Weimer, L, Li, and A. J. Smola. Parallelized Stochastic Gradient Descent. In NeurIPS, 2010.
14


Reviews:
[{"review_id": "izpo_kBPLuT", "reviewer": "Reviewer_o9PJ", "summary": "The paper considers gradient sparsification for learning in distributed setup, and advocates using a hard-threshold sparsifier combined with error-feedback mechanism. The paper shows that such algorithm is _optimal_ in a certain sense, and give several convergence guarantees for the error-feedback algorithms using absolute compressors and relative compressors. The empirical performance of HT and top-k compressors are also compared.", "questions": "", "limitations": "", "rating": 7, "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": "Post-rebuttal: Thank you for the reply. My concerns have been addressed well. Raising the score to 7.\n\n---\n\n__TL;DR.__ I think this paper presents several meaningful theoretical results as a contribution. However, I think some of the paper's claims are being quite oversold.\n\n__Strengths.__ Some of the theoretical results are definitely very cool to have. I believe that the convergence results in Section 5 (Theorems 2--5) is a nice contribution, and would be of interest to the distributed learning society, especially to those who study error-feedback mechanisms. Also, the proof technique going through the perturbed iteration analysis (via Lemma 10) is quite neat. Finally, the manuscript seems to discuss the related work relatively well.\n\n__Claims on optimality.__ I am very worried about the paper's claims about the optimality. The word \"optimal\" is a very bold, and should be used with a great care (in my opinion), as they could be quite misleading without delivering the assumptions and conditions it relies on. For instance, the abstract states that top-k is \"communication-optimal given a per-iteration $k$-element budget.\" But, what exactly does the word \"communication-optimal\" here mean? It is very easy to understand the statement as saying that such algorithm gives the hypothesis with a smallest loss---either in expected or high-probability sense. If I understood correctly, I think the paper is pointing to lemma 2, where authors state that Top-k gives the sparsified version of the error-feedback (or actually any signal) that has the smallest squared distortion from the original gradient signal. This also relies on the assumption that the choice of sparsification does not affect the subsequent gradient signals. This discrepancy gets more significant for the claims on the optimality of hard-threshold methods, where this \"independency assumption\" is critical for the proof. I believe that these ill-specified claims on the (possibly vacuous notions of) optimality should either be toned down to a certain degree to help readers better understand what the paper is contributing. Also, I think presenting the optimality claims in a form of lemmata without proofs is unnatural, no matter how straightforward the proofs are. I recommend either stating the claims in plain words without a formalization, or provide the result-specific assumptions clearly in the lemma statement---so that it is self-contained---and give at least a formal proof.\n\n__Stating the limitations.___ If I understood correctly, such hard-threshold sparsifiers may need a very high communication throughput at some epochs (mostly earlier). However, there are many setups such high peak communication rate is undesirable, due to the limited capacity of the communication channel (but when the delay is crucial). In such cases, having a constant communication rate could be beneficial. I think authors should discuss such scenarios to appropriately deliver the cases where the considered hard-threshold methods are desirable, and the cases they are not (sorry if I missed these parts).\n\n__Clarity: Why error-feedback?__ I am not entirely sure what is the big motivation behind considering the error-feedback mechanisms for this paper. Line 51 says: \"Consequently, we consider sparsification using the error-feedback mechanism, ...\" but I couldn't really locate the part that necessitates considering error-feedback. Could you please further clarify?\n\n__Clarity: $\\gamma_t$.__ The quantity $\\gamma_t$ appears at line 133, but I do not think this quantity is defined or introduced properly in the text.\n\n__Clarity: Assumption 2.__ I do not think Assumption 2 is explicitly assumed in any theorem appearing in the main text. But if I am correct, it is implicitly used for every theorems that use $R_0 := \\lVert x_T - x^\\star \\rVert$ in its bounds.\n\n__Question: $v$-dependency__ It was unexpected to me that the convergence guarantees for the absolute compressors $C_v ( \\cdot ) $ does not depend explicitly on the compression factor $v$, especially considering the fact that the guarantees for the $\\delta$-contraction operators contain a term that is inversely proportional to $\\delta$ (see Theorem 2 & Remark 5, for instance). Any further discussion explaining why such discrepancy happens (especially for the case $\\delta \\to 0, v \\to \\infty$) would be very nice to have; does this suggest the existence of a tighter bound for $\\delta$-contraction operators under additional assumptions the size of $p_{i,t}$?\n\n__Suggestion: Discussing $P_T$.__ While the quantity $P_T$ appears in many optimization literature, the meaning of the quantity may not be very straightforward for the readers who are relatively new to the field (like myself), especially because it gives the performance bound for $\\bar{x}_T$ generated by some weights $w_t$. Giving more ideas about the quantity may help the readers a lot, including whether one can choose $w_t$ arbitrarily or not, whether it implies that we should use an averaging scheme...", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think authors should additionally mention when can such variable-communication-load methods may not useful or usable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "20"}, "extra_text": {}}, {"review_id": "hO-JUkgT_HK", "reviewer": "Reviewer_VFA3", "summary": "The paper studies the role of compression operators on the convergence of Distributed SGD with Error Feedback. In particular, via simple observations, the authors conclude that a hard-threshold sparsifier with a carefully tuned threshold parameter minimizes the total error appearing in the analysis because of the presence of compression. Moreover, they show empirically the connection between poor behavior of EF-SGD with Top-k compression and the severe error accumulation.\n\nMotivated by these observations, the authors derive new convergence guarantees for EF-SGD with absolute compressors. This class of compressors covers hard-threshold sparsifier. The derived bounds show that the compression does not affect the slowest terms in the bound. Moreover, the authors derived the first complexity result in the non-convex case for EF-SGD with $\\delta$-cnotraction operators without bounded gradient assumption and $n > 1$ (though, under bounded data dissimilarity). Finally, the paper contains a good empirical study of the performance of EF-SGD with the hard-threshold sparsifier. The authors also provide an insight on how to tune the threshold parameter in order to outperform EF-SGD with the Top-k operator.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths\n\n1. **Simple but important observations about total error minimization.** The paper provides a closer look at the convergence of EF-SGD and identifies what quantity should be minimized in order to get better results. That is, via the sequence of simple observations, authors show that a hard-thresholding sparsifier (with fine-tuned threshold parameter) is the optimal choice in terms of the total error minimization. Moreover, the authors properly explain all the details and support their theoretical observations with empirical findings (e.g., see Figures 1 and 3).\n\n2. **Clarity and proofs.** The paper is clearly written. The proofs are easy to follow and contain only a couple of typos.\n\n3. **New results for EF-SGD.** The authors derived new results for the convergence of EF-SGD with absolute compression for strongly convex, convex, and non-convex objectives. The slowest terms in the derived bounds have a linear speedup and are not affected by compression-dependent parameters. This is a good property since the derived bounds match the ones for SGD without compression if the target accuracy is small enough / the number of communication rounds is large enough. Moreover, the authors derived the first convergence result for EF-SGD for $\\delta$-contraction operators without assuming boundedness of the gradients, but under Assumption 4, that bounds dissimilarity between local loss functions. Although the proofs substantially rely on the known techniques, the obtained results are quite good.\n\n4. **Numerical experiments** show a connection between the behavior of EF-SGD with Top-k and hard-thresholding sparsifier and \"error buildup\". Therefore, these numerical results justify the insights provided in Section 4.\n\n## Weaknesses\n\n1. **No analysis for the arbitrary heterogeneous case for non-convex objectives (minor).** The derived bounds in the non-convex case substantially rely on Assumption 4 that bounds the dissimilarity between local loss functions. Although this is a significant limitation, previous works on EF-SGD rely on even stronger assumptions. Therefore, this is a minor drawback.\n\n## Questions and Comments\n\n1. **Rates for EF-SGD with $\\delta$-contraction operator.** The rates shown in Remarks 5 and 7 can be significantly improved via the results from [19]. Although, in [19], Assumption 3 is not considered it can be easily cast in the general framework from [19] via the following derivation: $\\frac{M}{n}\\sum_{i=1}^n\\|\\nabla f_i(x^k)\\|^2 + \\sigma^2 \\leq 2LM(f(x^k) - f(x^*)) + \\frac{M}{n}\\sum_{i=1}^n \\|\\nabla f_i(x^*)\\|^2 + \\sigma^2$. Using the results from [19] one can actually show the linear speedup even for $\\delta$-contraction operators in the $\\mathcal{O}(1/T)$ and $\\mathcal{O}(1/\\sqrt{T})$ decaying terms for $\\mu > 0$ and $\\mu = 0$ respectively. Therefore, the conclusion from lines 270-272 is not correct.\n\n2. **equation after line 654:** the enumerator in the second term should be $\\mu L^2(1+M/n)^2R_0 + L\\kappa^2 \\ln(T)$.\n\n3. **line 247, $\\nu = \\gamma_t \\kappa$:** It is better not to use $\\kappa$ in the definition of $\\nu$ because $\\kappa$ usually denotes the condition number of the problem in the optimization literature.\n\n4. **lines 283-284:** This is done for $\\delta$-contraction operators in [19] and in Qian, X., Dong, H., Richtárik, P., & Zhang, T. Error Compensated Loopless SVRG for Distributed Optimization, Qian, X., Richtárik, P., & Zhang, T. (2020). Error compensated distributed SGD can be accelerated. arXiv preprint arXiv:2010.00091.\n\n5. **Lemmas 6 and 7.** First of all, one should add that $\\gamma = \\min\\left(\\frac{1}{d}, \\sqrt{\\frac{r_0}{cT}}\\right)$. Next, Lemma 7 can be tightened when $c$ is small, see Lemma D.3 from [19].\n\n6. **Lemma 9.** When $c = 0$ this result is incorrect since the logarithmic factor becomes infinity. See Lemma D.2 from [19] for the correct version.\n\n7. **Lemma 11.** It is better to cite the assumptions of the lemma in the statement (or at the beginning of the subsection).\n\n8. **lines 623-627:** The discussion in these lines should be rewritten after applying the corrections suggested in comment 1. Moreover, one should also say that $\\lambda$ can be large.\n\n## Comment after rebuttal\nI thank the authors for their response. I have read other reviews as well. Overall, my evaluation of the work remains the same. Therefore, I recommend the paper for acceptance and hope that the authors will apply all necessary corrections mentioned in the reviews.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "Inez-R5X9DB", "reviewer": "Reviewer_TZ2h", "summary": "This paper analyzes the hard-threshold sparsifier in distributed SGD with convergence analysis and extensive experiments. Main contributions include: 1. Provides upper bounds of the optimization errors for the hard-threshold sparsified distributed SGD, which improves from top-k compressor with linear speedup and compressor operator parameter dependence. 2. Conducts extensive experiments to demonstrate the benefits of hard-threshold sparsifier, achieving much better performance given the same average compression density (# of used coordinates / # of coordinates of DNN weights). ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. I am trying to understand why the proposed communication-complexity model is new, it seems to me it is an adaptive compression operator allowing different # of coordinates to be sent for each iteration. And the section 4.4 and Lemma 3 seems incorrect to me, since the optimization over B is sequential, the choice of first block will change the second block of A, so I didn’t quite follow why the proposed sparisfier is optimal for this communication-complexity model. \n2. On the confusion of total error minimization. In the paragraph starting from line 44, it seems to the authors are trying to present a new perspective that is not minimizing per iteration compression error but total compression errors, but the last sentence seems to me conveying the message of considering fixed total communication budget, which is exactly what I think other papers have discussed, how to tradeoff optimization error with total communication budgets. So there may be some confusion in this paragraph.\n3. The authors provide upper bounds of optimization errors for the proposed spasifier, in strongly convex, convex, and nonconvex settings respectively. Those upper bounds improve from the results using top-k sparsifier in terms of linear speedup and compressor parameter dependence. \n4. The provided upper bounds, however, seem to me not clearly they are more communication-efficient than the top-k sparsifier, since there is no characterization of the total number of coordinates being used in theory. Ideally, if we set the threshold be very small, most coordinates will be used. In experiments, the authors provide solid results showing that the hard-threshold sparsifier does use less coordinates in total than the top-k. \n5. The total error minimization perspective seems to me more like an observation of the consequence using a hard-threshold sparsifier, it may need further arguments to show it is the reason for better performance. \n6. The paper is in general well written and very clear, the extensive experiments are helpful for the understanding of the practical benefits of the hard-threshold sparsifier. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "-lB5hoBJkV", "reviewer": "Reviewer_eex4", "summary": "In this paper, the authors demonstrate that, in the context of distributed optimization problems with $n$ workers, the hard-threshold sparsifier is the optimal sparsifier for a proposed communication complexity model which where the goal is to minimize the total error for a sequence of responses. This allows the authors to compare the sum of compression errors for various algorithms and to demonstrate that while for the per-iteration $k$-element budget the Top-$k$ sparsifier is optimal, when it comes to total error the hard threshold sparsifier is better. \n\nThe authors also compare the convergence rates of the top-$k$ sparsifier vs the hard threshold sparsifer for image classification, language modeling, and recommendation tasks. ", "questions": "", "limitations": "", "rating": 7, "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": "I find this paper interesting and vote to accept it. I think it is an interesting result but unfortunately I am not an expert in the field and so am not sure about it's significance in the context of the field. I do like the communication complexity model. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theoretical paper and has limited societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper reformulates an existing problem (how to sparsify gradients in distributed training) and proposes to minimize a new objective (the total compression error subject to communication constraint as opposed to per-iteration compression error). This change of viewpoint leads to a new algorithm (hard threshold algorithm with variable sparsity). The authors show the effectiveness of the proposed algorithm through theoretical bounds and experiments. All reviewers agree that this is a valuable contribution. Comments from previous submission to ICML are adequately addressed.
Decision: Accept (Spotlight)