Rethinking gradient sparsification as total error minimization
Year: 2021

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 errorfeedback. 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 hardthreshold sparsifier is more communication-efficient than Top-k. Code is available at https://github.com/sands-lab/rethinking-sparsification.

heading: 1 Introduction
text: 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 a common approach to rein in communication efficiency [62]. In particular, sparsification, which sends only a subset of gradient coordinates (e.g., Top-k [4, 8] sends the k largest gradient coordinates by magnitude in 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 et al. [3] note that training ResNet-18 on CIFAR-100 using sparsification speeds up training significantly (3.6×), but it also degrades final accuracy by 1.5%. On the other hand, Lin et al. [37] reports a 500× data
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
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 to practitioners to grapple with specifying an additional hyper-parameter that determines the degree of compression before training begins. Meanwhile, 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-efficient scheme than a fixed compression scheme (e.g., a static k for Top-k). However, these works lack a theoretical framework proving that adaptive compression enjoys better convergence guarantees than the fixed compression scheme.
This raises a fundamental question: Given a 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-optimal sparsifier for a fixed per-iteration communication budget (§4.3). Then, our insight is that by adopting a different perspective that accounts for the effect of sparsification throughout training, a more efficient communication scheme is possible under a revised notion of optimality that considers an overall communication budget (instead of a per-iteration budget).
We consider sparsification by using the error-feedback (EF) mechanism [8, 53], a delayed gradient component update strategy that is instrumental for the convergence of the state-of-the-art sparsifiers [10]. Let et denote the error arising due to sparsification at iteration t. In EF, this error is added to the gradient update at iteration t+ 1. We identify that the term affecting the non-convex convergence in EF-SGD is the total-error: ∑ t‖et‖2 [33, 54].
Directly minimizing the total-error is not possible; thus, Top-k minimizes ‖et‖2 at each iteration. We argue that it is possible to focus on the sum of ‖et‖2 and devise a communication scheme that achieves a smaller total-error than any fixed communication sparsifier. We demonstrate that to achieve this change of perspective; it is sufficient to consider a practical yet straightforward mechanism that is a natural counterpart of Top-k: the hard-threshold sparsifier, which communicates the gradient coordinates with magnitude greater than or equal to a fixed given threshold, λ ≥ 0, 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 a fixed threshold, λ, which implies a variable k at every iteration.
To illustrate intuitively why this change of perspective yields benefits, consider the following example. Figure 1 shows an experiment in the distributed setting where 20 workers train a 6,000-parameter logistic regression model on the gisette LIBSVM dataset [14] by using the Top-k and hardthreshold sparsifiers, configured to send the same data volume.1 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 ∼ 600× 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 hard-threshold is less than 0.04 throughout training (cf. Figure 1c). Our results with DNN training also reflect this insight (§6).
1We train for 10 epochs and set k = 0.17% for Top-k, and λ = 4.2 for hard-threshold.
Moreover, the hard-threshold sparsifier has computational benefits over Top-k sparsifier, as hardthreshold’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 O(d log2 k) [48]). For GPUs, several optimized implementations are proposed but they rely on the data distribution and are efficient only for a small k [48]. For instance, PyTorch uses Radix select algorithm [5] which has a computational complexity ofO (db/re d) where b is the number of bits to represent gradient values and r 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 in favor of hard-threshold precisely falsifies the claim by Dryden et al. [18] that stopped its widespread adoption — a hard-threshold may lead to a 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 in each iteration by only imposing a total communication budget. We show that the hard-threshold sparsifier is the communication-optimal sparsifier in this model.
Absolute compressors (§5). We identify that the hard-threshold 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 δ-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 δ 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-efficient than the Top-k sparsifier given the same communication budget.

heading: 2 Related work
text: Gradient compression techniques can 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 stateof-the-art compressors are biased δ-contraction operators [37, 57], see §4.5. We refer to [62] for a 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 a 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 a compressed version of the error. EF has also been combined with variance-reduction [22, 43] and acceleration [44].
Communication-optimal compression. [6, 15, 21, 45] devised a communication-optimal compressor by minimizing the worst-case compression factor2 under a per-vector communication budget.
Adaptive compression. [59] designed an adaptive sparsifier that minimizes expected sparsity of the compressed vector under a 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 a high compression ratio otherwise.
2For a vector x and a possibly randomized compression operator C, we denote the compression error as EC[‖x− C(x)‖2], and compression factor as EC [‖x− C(x)‖2]/‖x‖2.
Efficient Top-k estimation is a focus of many recent works. While [37] estimates the Top-k threshold on a randomly sampled subset, [1, 49] estimate it by fitting parametric statistical distributions. [25] estimates the threshold every 1, 000 iterations. These works determine a threshold to approximately determine a fixed Top-k set, while we use a hard-threshold to determine the k in each iteration.

heading: 3 Background on Error-Feedback (EF) SGD
text: Consider the following distributed optimization problem with n workers: minx∈Rd f(x) := 1 n ∑ i∈[n] fi(x), (1)
where fi(x) = Ezi∼Di l(x; zi) denotes the loss function evaluated on input zi sampled from Di, the data-distribution at the ith worker. Let gi,t denote the stochastic gradient computed at ith worker at iteration t such that gi,t = ∇fi(xt) + ξi,t with E[ξi,t|xt] = 0. Algorithm 1 gives the pseudo-code of compressed EF SGD [8, 33, 53] to solve (1). Let ei,t denote the locally accumulated error at ith worker due to compression from previous steps. Adding this error to the current gradient, γtgi,t provides the corrected update, pi,t, where γt > 0 is the step-size. This corrected update is further compressed and exchanged with other machines, and the local error is updated for the next step.
Algorithm 1: Distributed EF SGD Input: C-compressor Initialize x0 ∈ Rd; for worker i ∈ [n] in parallel do
Initialize error ei,0 = 0; for iteration t = 0, . . . , T − 1 do pi,t ← ei,t + γtgi,t /* Incorporate EF into update */; ∆i,t ← γtC(pi,tγt ) ; ei,t+1 ← pi,t −∆i,t /* Update error */; ∆̄t = 1 n ∑ i∈[n] ∆i,t /* Exchange and average ∆i,t among workers */;
xt+1 ← xt − ∆̄t;
Remark 1. In Algorithm 1, we have ∆i,t ← γtC(pi,tγt ), while [8, 33, 53] consider ∆i,t ← C(pi,t). We do this to extend the EF framework for absolute compressors. We note that Algorithm 1 is more general as γtC(pi,tγt ) is equivalent to C(pi,t) for all known δ-contraction operators.

heading: 3.1 Assumptions
text: We consider the following general assumptions on the loss function. Assumption 1. (Smoothness) The function, fi : Rd → R at each worker, i ∈ [n] is L-smooth, i.e., for every x, y ∈ Rd we have, fi(y) ≤ fi(x) + 〈∇fi(x), y − x〉+ L2 ‖y − x‖2. Assumption 2. (Global minimum) There exists x? such that, f(x?) = f? ≤ f(x), for all x ∈ Rd. Assumption 3. ((M,σ2) bounded noise) [54] For every stochastic noise ξi,t, there exist M,σ2 ≥ 0, such that E[‖ξi,t‖2 | xt] ≤M‖∇fi(xt)‖2 + σ2, for all xt ∈ Rd. Remark 2. The above assumption implies E[‖gi,t‖2 | xt] ≤ (M + 1)‖∇fi(xt)‖2 + σ2. This general noise model does not uniformly bound the second moment of stochastic gradients as in [9, 33, 64]. Assumption 4. ((C, ζ2) bounded similarity) The variance of gradients among workers is bounded, i.e., there exist constants, C, ζ ≥ 0 such that, 1n ∑ i∈[n]‖∇fi(x)−∇f(x)‖2 ≤ C‖∇f(x)‖2 + ζ2, for all x ∈ Rd. Remark 3. If all the workers have the same training data, all fi are the same, resulting in C, ζ = 0. This assumption is an extension from [31, 36], which consider C = 0.
For the convergence of strongly convex functions, we require an additional assumption as follows. Assumption 5. (µ-strong convexity) The functions, fi : Rd → R are µ-strongly convex, i.e., there exists µ ≥ 0, such that fi(y) ≥ fi(x) + 〈∇fi(x), y − x〉+ µ2 ‖x− y‖2, for all x ∈ Rd.
Convergence of EF-SGD. The following result shows the convergence of EF-SGD [33] in minimizing general smooth functions for a single worker (n = 1) case. Theorem 1. [33, 54] Let Assumption 1, 2 and 3 hold. Then Algorithm 1 with a constant step-size, γ where γ ≤ 12L(M+1) and n = 1 follows
1
T
T−1∑
t=0
E‖∇f(xt)‖2 ≤ 4(f(x0)− f?)
γT + 2γLσ2 + 2L2
T−1∑
t=0
γ2E‖gt + etγ − C(gt + etγ )‖2 T .
Remark 4. Theorem 1 is a simplified version of the distributed case for n > 1 and quoted to emphasize the effect of compression between the error-corrected gradient, gt + etγ , and its compressed form, C(gt + etγ ). The term that solely accounts for the effect of compression in the entire training process is the total-error: ∑T−1 t=0 E‖et+1‖2 = ∑T−1 t=0 γ 2E‖gt + etγ − C(gt + etγ )‖2.

heading: 4 A communication complexity perspective to sparsification
text: We now propose a communication complexity model and contrast it with the existing communicationoptimal strategies. We note that our use of the word communication-optimal is in the sense of optimization upper-bounds. Convergence analyses of compressed SGD capture the effect of compression 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-optimal strategies by optimizing the compression error related term. We start with a sparse approximation problem that we encounter in our subsequent discussions.

heading: 4.1 A sparse approximation problem
text: Let p ∈ Rm be a given vector. We want to approximate p with a sparse vector, q, that has at most 0 < τ ≤ m non-zero elements. Formally, we write the constrained sparse approximation problem as:
q? = arg minq∈Rm‖p− q‖2 subject to ‖q‖0 ≤ τ, (2) where ‖ · ‖0 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-τ magnitude entries from p and setting the rest to zeros.

heading: 4.2 Minimizing the total-error is not possible
text: Let C denote the class of all compressors. We constrain to the class of deterministic sparsifiers, denoted by S ⊂ C, but one can similarly consider other subclasses in C. For each x ∈ Rd, a deterministic sparsifier, Cp with sparsification parameter, p determines a sparse support set, Sp(x) ⊆ [d] and sparsifies as
Cp(x) = ∑ i∈Sp(x) x[i]ei,
where ei denotes the ith standard basis in Rd, and x[i] denotes the corresponding element in x. For example, for hard-threshold sparsifier, Cλ, we have Sλ(x) = {i | |x[i]| ≥ λ}. Motivated by Theorem 1 and Remark 4, we now propose the following communication complexity model:
min C∈S
T−1∑
t=0
E‖gt + et γ − C(gt + et γ
)‖2 subject to T−1∑
t=0
‖C(gt + et γ )‖0 ≤ K, (3)
where K is the budget on the number of elements communicated in T iterations. However, solving (3) is intractable owing to complex DNN loss functions and multiple sources of randomness.
4.3 Top-k is communication-optimal for a per-iteration k element budget
To simplify (3), one can focus individually at the error at each iteration. Based on this, we show in Lemma 2 that Top-k has the best compression error among all sparsifiers under a per-iteration k-element communication budget.
Lemma 2. Given the gradient gt and error et at iteration t, Top-k sparsifier achieves the optimal objective for the optimization problem:
min C∈S ‖gt + et γ − C(gt + et γ )‖2 subject to ‖C(gt + et γ )‖0 ≤ k. (4)
Similar to Lemma 1, (4) is solved when C(gt + etγ ) contains the k highest magnitude elements of gt+ et γ . That is, when C is the Top-k sparsifier. Additionally, based on the above model, a 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, to have a more communication-efficient compression, we require a communication complexity model that (i) better captures total-error in Theorem 1; and (ii) allows for adaptive communication, i.e., sends variable data in each iteration.

heading: 4.4 A communication complexity model for adaptive sparsification
text: Although the total-error cannot be minimized (§4.2), Lemma 2 motivates us to consider a simplified model that can capture the total-error. Instead of (gt + etγ ) T−1 t=0 , we consider a fixed sequence (at) T−1 t=0 and examine the following communication complexity model:
minC∈S ∑T−1 t=0 ‖at − C(at)‖2 subject to ∑T−1 t=0 ‖C(at)‖0 ≤ K, (5)
where K ∈ N denotes the total communication budget. For the sake of simplicity, we assume that no two elements in (at)T−1t=0 have the same magnitude.
Let A ∈ RdT be formed by stacking (at)T−1t=0 vertically and consider the following sparse approximation problem: minB∈RdT ‖A −B‖2 subject to ‖B‖0 ≤ K, (6) Note that (6) allows for all B that are formed by stacking (C(at))T−1t=0 vertically, for some sparsifier C satisfying ∑T−1t=0 ‖C(at)‖0 ≤ K. Therefore, the optimal objective for (6) is a lower bound to the optimal objective for (5). Let A(i) denote the element with ith largest magnitude in A, and since no two elements have the same magnitude, we have, A(i+1) 6= A(i), for all i ∈ [dT ]. Then, B = Cλ(A) with λ ∈ ( A(K+1), A(K) ] contains the Top-K magnitude entries from A, and therefore, by Lemma 1 is optimal for (6). Moreover, since hard-threshold is an element-wise sparsifier, Cλ(A) is equivalent to stacking (Cλ(at))T−1t=0 vertically. Therefore, Cλ with λ = ( A(K+1),A(K) ] achieves optimal objective in (5). The following lemma formalizes this. Lemma 3. Cλ is optimal for the communication complexity model (5). That is, for every budget K, there exists a λ ≥ 0 such that Cλ minimizes (5).

heading: 4.5 Discussion
text: To capture the effect of compression, existing works [7, 33, 53] use a bound on the compression factor, maxx∈Rd EC‖C(x)−x‖2 ‖x‖2 . We formally define them as relative compressors.
Definition 2. Relative Compressor [7, 53]. An operator, C : Rd → Rd is a relative compressor if for all vector, x ∈ Rd it satisfies EC‖x− C(x)‖2 ≤ Ω‖x‖2, (7) where Ω > 0 is the compression factor and the expectation, EC , is taken with respect to the randomness of C. δ-contraction operators [33, 53] with Ω = 1− δ and δ ∈ (0, 1], are special cases of relative compressors.
Top-k is a δ-contraction operator with δ = kd [53]. Therefore, by (7), Top-k allows for larger compression error with larger inputs. Our communication complexity model demonstrates that this might not necessarily be a good idea. Moreover, with EF, a large error at any iteration has a cascading effect — a large et results in a large γgt + et, 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 1 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 its magnitude is bigger than the threshold. This prohibits the error build-up.
Comparison with existing communication-optimal compression strategies. Since the compression factor, Ω solely determines the effect of compression in convergence [29, 54], many recent works [6, 15, 21, 45] propose communication-optimal compression strategies by optimizing for Ω under a communication budget for each vector, i.e., they propose to solve
min C∈C max x∈Rd EC‖x− C(x)‖2 ‖x‖2 subject to Bits(C(x)) ≤ B, (8)
where Bits(C(x)) denotes the number of bits needed to encode C(x). We stress that while the compression affected term in Theorem 1 has the sum of compression errors over the iterations, the above communication complexity model only captures the compression factor.

heading: 5 Absolute compressors and their convergence
text: 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 : Rd → Rd is an absolute compressor if there exists a υ > 0 such that for all vectors, x ∈ Rd it satisfies
EC‖x− C(x)‖2 ≤ υ2. (9)
In contrast to the relative compressors in (7), the compression error (or variance) of absolute compressors is bounded by a constant, independent of x. Based on the above definition, hard-threshold is an absolute sparsifier with υ2 = dλ2. 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 , is an absolute compressor with υ2 = d 2. Similarly, the scaled integer rounding scheme in [46] is an absolute compressor. While this class of compressors existed in the literature, we are the first to provide their convergence result with an EF.

heading: 5.1 Convergence results
text: Inspired by [54], we 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 δ-contraction operators. We start with a bound on the error for absolute compressors. Remark 5. (Error bound) For all i ∈ [n], t ∈ {0, . . . T − 1}, we have
EC [‖ei,t+1‖2 | pi,t] = EC‖pi,t − γtC(pi,tγt )‖ 2 = γ2t EC‖pi,tγt − C( pi,t γt )‖2 ≤ γ2t υ2.
A similar absolute bound for δ-contraction operators requires the bounded gradient assumption [33, 9], but absolute compressors achieve this by design.

heading: 5.1.1 Convex convergence
text: Let x̄T = 1WT ∑T t=0 wtxt be the weighted average of the iterates with weights, wt ≥ 0 and
WT = ∑T t=0 wt. Additionally, let Pt := E[f(x̄t)] − f? be the expected suboptimality gap at the
average iterate. Further denote Rt := ‖xt − x?‖2 and D := 1n ∑n i=1‖∇fi(x?)‖2. With these notations, we quote the strongly convex (µ > 0) and convex (µ = 0) convergence results for absolute compressors, and compare them with the δ-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 for these choices.
Theorem 4. Let µ > 0 and Assumptions 1, 2, 3, and 5 hold. Then the iterates, {xt}t≥0 of Algorithm 1 with an absolute compressor, Cυ , a constant step-size, γ(T ) with γ(T ) ≤ 14L(1+2M/n) follow 3
PT = Õ ( LR0(1 +M/n) exp [ − µT8L(1+2M/n) ] + σ 2+MD µnT + Lυ2 µ2T 2 ) .
3The Õ notation hides constants and factors polylogarithmic in the problem parameters.
Remark 6. Under the same setting as in Theorem 4, iterates of Algorithm 1 with δ-contraction operators follow:
PT = Õ ( LR0 (√ 1+Mδ δ ) exp [ − µδT 16 √ 3L √ 2+Mδ ] + σ 2+MD µnT + L(D(1+Mδ)+δσ2) µ2δ2T 2 ) .
Remark 6 implies, in distributed settings with heterogeneous data (D 6= 0), δ-contraction operators have an 1/δ2 dependence on δ, as compared to an 1/δ dependence in the homogeneous case (D = 0). In contrast, absolute compressors have the same υ2 dependence on υ in 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.
Theorem 5. Let µ = 0 and Assumptions 1, 2, 3, and 5 hold with D 6= 0. Then the iterates, {xt}t≥0 of Algo. 1 with an absolute compressor, Cυ, a constant step-size, γ(T ) with γ(T ) ≤ 14L(1+2M/n) follow
PT = O (√
(σ2+MD)R0√ nT +
( nLυ2
σ2+MD +L(1+M/n)
) R0
T
) .
Remark 7. Theorem 5 holds when both σ2 and D are not simultaneously zero. Typically, we encounter heterogeneous data settings where D 6= 0, and Theorem 5 holds. In case both σ2 and D are zero, we get O( (LυR0) 2 3
T 2 3
+ L(1+M/n))R0T ) convergence.
Remark 8. Under the same setting as in Theorem 5, iterates of Algorithm 1 with δ-contraction operators follow:
PT = O
  √
(σ2+MD)R0√ nT +
( L √
1+Mδ δ +
nL(D(1+Mδ)+δσ2)
δ2(σ2+MD)
) R0
T
  .
Similar to Remark 6, we observe that δ-contraction operators have 1/δ2 dependence on δ in the heterogeneous case, and a 1/δ dependence in the homogeneous case, while absolute compressors have no such anomaly.
Designing a variance-reduced algorithm [22, 43, 44] by using absolute compressors with EF is a fruitful direction of future research.

heading: 5.1.2 Non-convex convergence
text: Theorem 6. (Non-convex convergence of absolute compressors) Let Assumptions 1, 2, 3, and 4 hold. Then the iterates, {xt}t≥0 of Algorithm 1 with an absolute compressor and a constant step-size γ ≤ n2L(M(C+1)+n) follow
1 T ∑T−1 t=0 E‖∇f(xt)‖2 ≤ 4(f(x0)−f?) γT + 2γL(Mζ2+σ2) n + 2γ 2L2υ2.
Alongside, we compare with the non-convex convergence for δ-contraction operators in a distributed setting. The existing analyses tackle this by using a stronger uniform bounded gradient assumption [64, 33, 20]. We use weaker Assumption 3 and 4, to establish the convergence analysis.
Theorem 7. (Non-convex convergence of δ-contraction operators) Let Assumptions 1, 2, 3, and 4 hold. Then the iterates, {xt}t≥0 of Algorithm 1 with a δ-compressor and a constant step-size γ ≤ min{ n2L(M(C+1)+n) , 12L(2/δ+M)√C+1} follow
1 T ∑T−1 t=0 E‖∇f(xt)‖2 ≤ 8(f(x0)−f?) γT + 4γL(Mζ2+σ2) n + 8γ2L2 δ (( 2 δ +M ) ζ2 + σ2 ) .
Again, similar to Remarks 6 and 8, for δ-contraction operators, we find the 1/δ2 (heterogeneous case, ζ 6= 0) vs. 1/δ (homogeneous case, ζ = 0) anomaly, while absolute compressors have υ2 dependence on υ in both homogeneous and heterogeneous cases. Remark 9. With appropriate choices of step-size, both absolute compressors and δ-contraction operators with EF-SGD achieve the same O(1/ √ nT ) asymptotic rate of SGD. See Corollary 1 in §B.3 for the full result.

heading: 6 Experiments
text: 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-parameter configuration, comparison with entire-model 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: 1T ∑T−1 t=0 kt d as a measure of total data volume, where kt 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 on CIFAR-10, we observe that hard-threshold at an average density of 0.12% almost achieves the baseline accuracy and is better than Top-k at 0.75% density (∼ 6× more total data volume). For LSTM on Wikitext, at an average density of 0.025%, hard-threshold has > 2 better perplexity than Top-k. For NCF on Movielens-20M, hard-threshold has > 1% better Hit-Rate@10 at all considered average densities.
We now demonstrate that hard-threshold has faster convergence because of a 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 error-accumulation in the initial 1, 200 iterations for Top-k. Consequently, hard-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 §C.2).
Comparison against ACCORDION. We compare against the state-of-the-art adaptive sparsifier: ACCORDION [3] on CIFAR-10 and CIFAR-100 datasets. ACCORDION shifts between two userdefined k values: kmax and kmin, by using Top-kmax when the training is in a critical regime, else using Top-kmin. We compare against ACCORDION with hard-threshold λ = 12√kmin . For complete experiment details; see §C.4.
We report the CIFAR-10 result in Table 1, while the CIFAR-100 result is reported in §C.4. Each setting is repeated with 6 different seeds and we report the average. For the CIFAR-10 dataset,
we observe that hard-threshold has 0.5% − 0.8% higher test accuracy than ACCORDION and is approximately 3.5× more communication efficient than ACCORDION. For the CIFAR-100 dataset, except the ResNet-18 model, we observe that hard-threshold obtains more than 0.8% higher accuracy than ACCORDION with more than 1.26× 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 k for non-convex loss functions (including DNNs). Let M̂ , ζ̂, and σ̂ be the estimates of M , ζ, and σ, respectively, in
Assumptions 3 and 4. We set the threshold as λ ∼ 2√ k √( 2d k + M̂ ) ζ̂2 + σ̂2; see discussion in §D.
The λ in Table 1 is derived from simplifying this formula. But how to tune the hard-threshold such that it achieves no-compression baseline 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 on 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 a bottleneck, even if Top-k compression is applied. However, in the case of hard-threshold sparsification (configured for the same total communication 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 a hard-threshold with the same total communication volume may introduce non-overlapped communication in some iterations with high data transmission, thereby increasing overall training time. Here, we ignored two important aspects of hard-threshold: (i) Hard-threshold may require fewer iterations to a target accuracy owing to its better statistical efficiency, and that (ii) hard-threshold has negligible computation overhead in comparison to Top-k.

heading: 7 Conclusion
text: We proposed a 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-efficient 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 hard-threshold 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-efficient versions of Local SGD that adaptively 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.

heading: Acknowledgements
text: 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.

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

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

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.

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.   The authors also compare the convergence rates of the top-$k$ sparsifier vs the hard threshold sparsifer for image classification, language modeling, and recommendation tasks.