Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression
Authors: Xinmeng Huang
Yiming Chen
Wotao Yin
Kun Yuan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed Learning
Communication Compression
Optimal Complexity
Non-convex Optimization

Abstract: Recent advances in distributed optimization and learning have shown that communication compression is one of the most effective means of reducing communication. While there have been many results for convergence rates with compressed communication, a lower bound is still missing.

Analyses of algorithms with communication compression have identified two abstract properties that guarantee convergence: the unbiased property or the contractive property. They can be applied either unidirectionally (compressing messages from worker to server) or bidirectionally. In the smooth and non-convex stochastic regime, this paper establishes a lower bound for distributed algorithms whether using unbiased or contractive compressors in unidirection or bidirection. To close the gap between this lower bound and the best existing upper bound, we further propose an algorithm, NEOLITHIC, that almost reaches our lower bound (except for a logarithm factor) under mild conditions. Our results also show that using contractive compressors in bidirection can yield iterative methods that converge as fast as those using unbiased compressors unidirectionally. We report experimental results that validate our findings.

Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression
Xinmeng Huang 1+
Yiming Chen 2.3+
Wotao Yin
Kun Yuan 2.4
University of Pennsylvania
DAMO Academy, Alibaba Group *Peking University
MetaCarbon
xinmengh@sas. upenn. edu yiming@metaccrbon. {wotao. yin, kun. y aaaaaaallbbaaaiin
Abstract
Recent advances in distributed optimization and learning have shown that communi- cation compression one of the most effective means of reducing communication. While there have been many results for convergence rates with compressed com- munication, lower bound is still missing.
Analyses of algorithms with communication compression have identified two ab- stract properties that guarantee convergence: the unbiased property or the contrac- tive property. They can be applied either unidirectionally (compressing messages from worker to server) or bidirectionally. In the smooth and non-convex stochastic regime, this paper establishes lower bound for distributed algorithms whether using unbiased contractive compressors unidirection bidirection. To close the gap between this lower bound and the best existing upper bound, we further propose algorithm, NEOLITHIC, that almost reaches lower bound (except for logarithm factor) under mild conditions. Our results also show that using contractive compressors in bidirection yield iterative methods that converge fast as those using unbiased compressors unidirectionally. We report experimental results that validate our findings.
Introduction
Large-scale optimization is critical step in many machine learning applications. Millions billions of data samples contribute to the excellent performance tasks such as robotics, computer vision, natural language processing, healthcare, and on. However, such scale of data samples and model parameters leads to enormous communication that hampers the scalability of distributed machine-learning training systems. We urgently need communication-recuctioo strategies. State-of- the-art strategies include model and gradient compression [4, 56), decentralized communication 9
39
lazy communication 73 57 33 [8]. and beyond. This article will focus on the former.
The most common method of distributed training is Parallel SGD (P-SGD) 13 In P-SGD, the stochastic gradients that workers transmit server cause significant communication overhead in large-scale machine learning. To reduce this overhead, many recent works propose to compress the messages sent unidirectionally from worker to server [5| 28
compress the messages between them bidirectionally 662 70). The method of compression is either sparsification or quantization
5 28 4 their combination [28 [4]. The literature [58 55
62 70 reveals that bidirectional
compression can save more communication, but leads to slower convergence rates.
'Equal Contribution. Corresponding Author: Kun Yuan
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table I: Comparison between various distributed stochastic algorithms with communication compression for non-convex loss functions. To explicitly clarify the influence of different compression strategies, keep the stochastic gradient variance o², data heterogeneity bound b² gradient square norm bound G (used in in the below results. Moreover, notation (-) hides all logarithmic terms. "LB" and "UB" indicate lower and upper bound, respectively. Notation d and w compressor--elated parameters (see detailed discussions in Section
[58 62 68], much larger than b² and L). , but omit smoothness constant L, and initialization f(x(0)
Algorithm
Convergence Rate
Compression"
Trans. Compl."
Uni/Bidirectional
Theorem
Corollary
Ω
2(1/8")
LB
VnT
Contractive
Uni/Bidirectional
Theorem
Corollary
Ω
1ow 7
Ω Q +
VnT
Unbiased
Theorem
Uni/Bidirectional
Ö(1/6%)
vxT
Contractive
Uni/Bidirectional Unbiased
Corollary 3
1t
Ö(n(1 + +w))
UB
VnT
(1w) 112m) 1/2 4/2///1 1,o
Unidirectional i..d, Unbiased
Q-SGD
32
0
vuf
MEM-SGD 58
0
2//3
Unidirectional
184
val
84/0p273
T)
Contractive
Double-Squeeze 62
0
G2/3
Unidirectional
1(12180)
VnT
84/372/3
Contractive
CSER
0
g
G2/3
Unidirectional
O(12/8*)
VnT
84/T2//3
Contractive
Unidirectional
EF21-SGD 24
V55T +
8T
Contractive
This column indicates type of the compressor and in what direction the compression is applied. b This column indicates the transient complexity, i.e., the number of gradient queries (or communication rounds) the algorithm has experience before reaching the linear-speedup stage, i.e., O(
This convergence rate is valid only for T ((n(1 + () Since the rate (1+w)"/2 Vn _ worse than VnT" the transient complexity is not available.
is always
VnT
Since the convergence rate does not show linear-speedup. the transient complexity are not available.
The rates are either strengthened by relaxing the original restrictive assumptions or extended to the same setting as NEOLITHIC for fair comparison, see more details in Appendix D
Although there are many specific compression methods, their convergence analyses are mainly built on unbiased compressibility contractive compressibility. The literature [14 54 71 summarizes these two properties and how they appear in the analyses. An unbiased compressor compresses long vector x into a short vector C(x) and satisfies [=[((=)] = x. i.c., no bias is introduced. The contractive compressor may introduce bias, but its compression introduces much less variance. We give their definitions below. Although the contractive compressor can empirically work better, the analysis of the unbiased compressor yields faster convergence due to unbiasedness [14
29 26
Despite the quick progress made in compression techniques and their convergence, do not yet understand the limits of algorithms with communication compression. Since unbiased and contractive compressibilities are the two representative characteristics of various compressors, we use them to theorize two types of compression methods. For each type, we intend to answer:
What is the optimal convergence rate that a distributed algorithm can achieve when using any of the compression methods of this type?
Here, we assume that only unbiased compressibility or contractive compressibility can be used, not considering any additional special compressor design; after all, any special design in the literature has been heuristic, whose effectiveness can be explained at best and not proved or quantified. So, we further clarify our question: Given a class of optimization problems (specified below) and a class of compression methods of the same type, if we choose the worst combination of them to defeat an algorithm, what will the convergence rute that the best-defending algorithm can reach? ? To our knowledge, they are fundamental questions not addressed yet.

---

1.1
Main Results
This paper clarifies these open questions by providing lower bounds under the non-convex smooth stochastic optimization setting, and developing effective algorithms that match the lower bounds up logarithm factors. In particular, our contributions are:
We establish convergence lower bounds for distributed algorithms with communication compres- sion in the stochastic non-convex regime. Our lower bounds apply to any algorithm conducting unidirectional or bidirectional compression and using unbiased or contractive compressors. We find clear gap between the established lower bounds and the existing convergence rates.
We propose novel nearly optimal algorithm with compression (NEOLITHIC) to fill in this gap. NEOLITHIC can adopt either unidirectional or bidirectional compression, and is compatible with both unbiased and contractive compressors. Using any combination. NEOLITHIC provably matches the above lower bound, under an additional mild assumption and up to logarithmic factors.
The convergence results of NEOLITHIC also imply that, for non-convex problems, algorithms using biased contractive compressors bidirectionally can theoretically converge as fast as those with unbiased compressors used unidirectionally. Before out work, it is only established in [48] that, for convex problems and unbiased compressors, algorithms with bidirectional compression can match with the counterparts with unidirectional compression.
We provide extensive experimental results to validate our theories.
All established results in this paper well as convergence rates of existing state-of-the-ar distributed algorithms with communication compression are listed Table The transient complexity, which measures how sensitive the algorithm is to the compression strategy (see Section B is also listed in the table. The smaller the transient complexity is, the faster the algorithm converges.
1.2 Related Works
Distributed learning. Distributed learning has been increasingly useful in training large-scale machine learning models (2T. It typically follows a centralized or decentralized setup. Centralized approaches 22 388 with P-SGD as the representative, require all workers to synchronize with central server per iteration. Decentralized upproaches, however, are based on partial averaging in which each worker only needs to synchronize with its immediate neighbors. Well-known decentralized
algorithms include decentralized SGD 45| 77
76 39],
ol 774, stochastic gradient tracking
[69 36 3 30 and their momentum variants 40 75 The lazy communication [73 57 [8] is also
utilized to reduce communication overheads in which workers conducts multiple local updates before
sending messages.
Communication compression. To alleviate the communication overhead in distributed learning, researchers have proposed two mainstream communication compression methods: quantization and sparsification. Quantization [32 60 80) is essentially an unbiased operator with random noise. For example, (56] develops Sign-SGD by using only bit for each entry whose convergence is studied in [3 66]. Q-SGD 44 compresses each entry with more flexible bits and enables a trade-off' between convergence rates and communication costs. Sparsification,
the other hand, amounts to biased but contractive operator. [65 propose to transmit small number of entries, randomly or by taking the largest ones, to achieve sparsity in communication. The theories behind contractive compressors are limited to those in 644
58
59 due to analysis challenges, and they are established with assumptions such bounded gradients {82 34 or quadratic loss functions 677 More discussions on unbiased
41
and biased compressors can be found in [14 54 53 Communication compression can also be
combined with other communication-sen saving techniques such as decentralization 42 81
Error compensation. The error compensation (feedback) mechanism is introduced by 56 to mitigate the error caused by 1-bit quantization. [67] studies SGD with cror--compensteed quantization for quadratic functions with convergence guarantees. (58] shows that error compensation can reduce ilantizationineurree errors for strongly convex loss functions in the single-node setting. Error- compensated SGD studied in [5] for non-convex loss functions with no establishment of an improved convergence rate. The algorithm EF21 52 applies to the deterministic setting, using contractive compressors unidirectionally. can converge under very mild assumptions. has been recently extended to the stochastic setting [24] yet linear-speedup rate is achieved.
3

---

Lower bounds in optimization. Lower bounds are well studied in convex optimization 23 22
20 especially when there no gradient noise 8 78 10 25]. In non-convex optimization, [16 propose a zero-chain model and show a tight bound for first-order methods. By splitting the zero-chain model into multiple components, the authors of 83 extend the analysis technique to finite sum and stochastic problems. Recently, [43 [6 also show the lower bounds in the decentralized stochastic setting based on a similar approach. For distributed learning with communication compression, useful work [49] establishes a lower bound for unidireciionl/bidircciion compression for strongly convex problems with fixed learning rates and unbiased compressors. There are limited studies on lower bounds for non-convex distributed learning with unbiased/contraatiiv compressions.
2 Problem Setup
We consider standard distributed learning with n parallel workers. The data samples each worker i follow a local distribution D,, which can be heterogeneous among all workers. These workers, together with a central parameter server, collaborate to train a model by solving
min FER
[xx
ni + f((x) with fi(x) RE,- Ln Ei),
(I)
where F(x; {) is the loss function evaluated at parameter x with sample ç. Since the objective f can be non-convex, finding a global minimum of (1) is generally intractable. Therefore, we turn to seeking model é with a small gradient magnitude in expectation, i.e., [+)[]] Next we introduce the setup under which perform a convergence analysis.
2.1 Function Class
We let the function class FA,L denote the set of all functions satisfying Assumption | for any underlying dimension E N+ and given initialization point x:()) R.d."
Assumption (Smoothness). We assume each local objective Si has L-Lipschitz gradient, i.e.,
[V(((z) - {.(il) S L||x - yll
for any i E nI....,,,,,,,u v Rd, and (xx(0)) inf f(x) s A with f = 1 Ei fi-
2.2 Gradient Oracle Class
We assume each worker i has access its local gradient (x(x) via a stochastic gradient oracle (x( ()) subject to randomness Ç., e.g., the mini-batch sampling & ف & D₁. We further assume that the output (z (1) is time-independent and unbiased estimator of the full-batch gradient fz)) with bounded variance. Formally, we let the stochastic gradient oracle class O,2 denote the set of all oracles O satisfying Assumption 2
Assumption (Gradient noise). For any Rd and E (n.....,,, the oracle O, satisfies
Ex (O, Gi) = V((()) and (x,1)O,(r;;)) - V[(()))))
2.3 Compressor Class
The two classes of widely-used compressors are i) the w-unbiased compressor, described by Assump- tion 3 e.g., the stochastic quantization operator [4, and ii) the 8-contractive compressor, described
by Assumption 4 e.g., the rand-K K and top-K operators [58 51].
Assumption (Unbiased compressor). For a (possibly random) compression operator C: Rd Rd we assume there exists constant w 2 O such that
[[C(z)] x, B[I[C(=) - = 2
Rd
where the expectation is taken over the randomness of the compression operator C.
Assumption 4 (Contractive compressor). For a (possibly random) compression operator C Rd Rd, we assume there exists a constant 8 E (0, 1] such that
E[I[C(x) = < (1 8) Vx E Rdd
where the expectation is over the randomness of the compression operator C.

---

Formally, we let the compressor classes Uw and Cj denote the set of all w-uubbased compressors and ò-contractive compressors satisfying Assumptions and respectively. Note that the identity operator 7 satisfies / E U_ for any 2 0 and / E Ca for any (0, Generally, an w-unbiased compressor not necessarily contractive when wi larger than However, since C' E Ms implies (1 + -C E - the scaled unbiased compressor is also contractive though the converse does not hold. Hence, the class of contractive compressors is strictly more general since it contains all unbiased compressors through scaling.
2.4 Algorithm Class
We consider centralized and synchronous algorithm A in which i) workers allowed to com- municate only directly with the central server but not between one another; ii) all iterations are synchronized so that all workers start each of their iterations simultaneously. Each worker i holds local copy of the model, denoted by z; at iteration t. The output g(0) of A after t iterations can be any linear combination of all previous local models, namely,
( E span (1 ( :
:5 s sts s
We further require algorithms A to satisfy the so-called "zero-respecting" property, which appears in [16 17 43). Intuitively, this property implies that the number of non-zero entries of the local model of worker can be increased only by conducting local stochastic gradient descent with its own samples or synchronizing with the server. The zero-respess rero-respecting property holds in all algorithms in Table[]and most first-order methods based on SGD 46 35 31 [9].. In addition to these properties, the algorithm A has to admit communication compression. Specifically, we endow the server with compressor Co and each worker i (1,...,, ,n) with compressor C.. If C, T for some i E {0. .................. n), then worker (or the server if i 0) conducts lossless communication. When G * for any i E (O..... n), algorithm A conducts bidirectional compression. When Co I, algorithm A conducts unidirectional compression on messages from workers to server. The formal definition of the algorithm class with bidrectionnllunddrectinnall compression is as follows.
Definition (Algorithm class). Given compressors {Co, Ci,..., C,.), write Alc.y for the set of all centralized, synchronous, zero-respecting algorithms admitting bidirectional compression in which i) compressor C, v S S is applied to messages from worker to the server, and ii) compressor Co is applied to messages from the server to all workers. When Co = I, we write A (C==TJu(C.)) or A(c,y, for short, for the set of algorithms admitting unidirectional compression. The superscript B or U indicates "bidirectional" or "unidirectional" respectively.
3 Lower Bounds
With all interested classes introduced above, we now define the lower bound measure. Given local loss functions {.f )i C F..L, stochastic gradient oracles {0 C O, (with O for worker i), compressors {C,) 10 C C (C can be Uw or Cs), and an algorithm A E A to solve problem []) (A can be A [c. A A(,,,, ), let á &AA.A. - P.o.T denote the output of algorithm A using no more than T gradient queries and rounds communication by each worker node. We define the minimax measure
inf sup AEA RE (O.).
sup
sup CF..
EI| BIAAefaaaaannnno.........o.
(2)
In (2). we do not require the compressors (C.) to be distinct or independent. When C is Uu or Cs. allow the compressor parameter or å to be accessible by algorithm A.
3.1 Unidirectional Unbiased Compression
Our first result is for algorithms that admit unidirectional compression and w-unbiased compressors. Theorem (Unidirectional unbiased compression). For every A, I.> 2 2, w 2 0, a > T > (1 + 3 there exists set of local loss functions {fi C FA.L. stochastic gradient oracles
5

---

[0 Co,, w-umbiased compressors {Cil-- Uu with Co = I, such that for any algorithm
A E A (c)) starting from a given constant x: 10) it holds that
((AL)) nT
(1+
(3)
T
Consistency with previous works. The bound in is consistent with best-known lower bounds in different settings. When w = 0, our result reduces to the tight bounds for distributed training without 1 and O, result reduces to the lower bound established in [ under the single-node non-convex stochastic setting. When n = 1,w = 0 and o² = O, our result recovers the tight bound for deterministic non-convex optimization []6].
compression 77. When
Linear-speedup. When T is sufficiently large, the first term 1/v dominates the lower bound 33_ If an algorithm achieves an O(1/ D(//vnT) rate, it will require 7 = ((1/(ne)) gradient queries to reach a desired accuracy e, which is inversely proportional to n. Therefore, an algorithm achieves linear-speedup at 7'th iteration if, for this T,, the term involving n''' is dominating the rate.
Transient complexity. Due to the cumpressionninnuuree overhead in convergence rate, a distributed stochastic algorithm with communication compression has to experience a transient stage to achieve its aneer--peedup stage. Transient complexity are referred the number of gradient queries (or communication rounds) when I' is relatively small so non-n terms still dominate the rate. The smaller the transient complexity is, the less gradient queries or communication rounds the algorithm requires to achieve the linear-speedup stage. For example, if an algorithm can achieve the lower bound established in (3) requires (ALa2
(1+w)AL i.e., T = [n ++)² transient gradient queries (or communication rounds) to achieve linear-speedup, which is proportional to the compression- related terms (1 2 Transient complexity is important metric to evaluate how sensitive the
nf
algorithm is to compression errors. It was widely used in decentralized learning [50] 72 to gauge
how the network topology can influence the convergence rate.
3.2 Bidirectional Unbiased Compression
Theorem D applies to unidirectional compression where Co = I. We next consider the bidirectional compression with Co E Uue Since { C Uh with Co = 7 a special case of {C+] S Uas
the lower bound for algorithms that admit bidirectional compression is greater than or equal to that with unidirectional compression due to definition in 2
Corollary 1 (Bidirectional unbiased compression). Under the same setting as in Theorem 7 there exists a set of local objectives (ft C FALL. stochastic gradient oracles {0:)__ C Oge, w-unbiased compressors k C Uw such that for any algorithm A E A (C,) starting from
()) the lower bound in 3 is also valid.
Theorem D and Corollary indicate that distributed learning with both unidirectional and bidirec- tional communication compression share the same lower bound. It is intuitive since unidirectional compression just special case of bidirectional compression by letting Co I.
3.3 Unidirectional Contractive Compression
To obtain the lower bounds for communication compression with contractive compressors, we need the following lemma [54] Lemma 1].
Lemma (Compressor relation). It holds that 84,-1-1 ( C E 28- Co-
The above Lemma reveals that any (8 11 - un-ubiideed compressor is 8-contractive when scaled by Therefore, if an algorithm A admits all ò-contractive compressors, it will also admits all compressors in - due to Lemma [ This relation, together with Theorem helps us achieve the following lower bound with respect to ô-contractive compressors.
Theorem 2 (Unidirectional contractive compression). For every A, L> 0, n
2, 0, < 1,
0, T 2 8-2, there exists a set of loss objectives (fi)2 C F L. a set of stochastic gradient oracles {0, j C Og,, set of 8-contractive compressors {C.) Cs with Co = 1, such that

---

Algorithm Fast Compressed Communication: y(k.R) FCC( C, R, target receiver(s))
Input: The original vector (((A)) to communicate iteration compressor C rounds R: initial vector u(k.0) 0; target receiver(s);
for -0.--. R - 1 do
Compress v(R,*) (k,,r) into e(frr) C(v(R,n) o(h.r))
Send ((k.r) to the target receiver(s)
Update v(b,+11) v(k.r) + clk.r)
end for
> The set (o(*.r) p
R--1 will be sent to the receiver during the for-loop Tr
return Variable ((..R)
b It holds that (4, Ev R-1 ((hir)
for any algorithm A E Acc.n starting from (0)), holds that
B||| BIIV//AA000..1101:00000.. ( (nTT
AL 8T
(4)
Transient complexity. With the discussion transient complexity in Section 3.1 is easy derive the transient iteration complexity as (2( for the lower bound with 5-contractive compressor.
3.4 Bidirectional Contractive Compression.
Noting that (C))e S C. with Co / is special case of (C,) i= C Cs. we can also establish the lower bound for algorithms that admit bidirectional compression and contractive compressions.
Corollary (Bidirectional contractive compression). Under the same settings as in Theorem there exists set of loss objectives {fil C F..LL. a set of stochastic gradient oracles {0,) Og,, set of 6-contractive compressors {C+ S Cs. such that for any algorithm A E A AC, starting form (0),, the lower bound (4) is also valid.
NEOLITHIC: A nearly optimal algorithm
Comparing the best-known upper bounds listed in Table with and 4 we find existing algorithms may not be optimal. There exists clear gap between their convergence rates and our established lower bounds. In this section, we propose NEOLITHIC to fill in this gap. Its rate will match the lower bounds established in (3) and 4 up to logarithm factors. NEOLITHIC can work with both unidirectional and bidirectional compression, and is compatible with both unbiased and contractive compressors. NEOLITHIC will be discussed in detail with bidirectional contractive compression in this section. easy to adapted other settings by simply removing the server-to-worker compression utilizing the scaled unbiased compressor.
with the established lower bounds in (3)
4.1 Fast Compressed Communication
NEOLITHIC is built a compression communication protocol listed in Algorithm D which call fast compressed communication (FCC). Given input vector (kk,*) to communicate in the k-th iteration, FCC will first initialize (k.0) 0 and then recursively compresses the residual with (k.r) A (kr(k,+) o(kkr) and sends it to the receiver for R consecutive rounds, see the main recursion in Algorithm [ When FCC operation finishes, the sender will transmit a set of compressed variables (c(k.r) ( R-1 r=0 to the receiver, and return (k, = RR-1 c(b..) to itself. Quantity (k, R) can be regarded as compressed vector of the original input 2 (R.*) after the FCC protocol.
The FCC protocol be conducted by the server (for which all variables in FCC are without any subscripts, e.g., c(k.r) and p(krr) by any worker i (for which all variables are with subscript i, e,g. C3 (kir) and v (k.r)) When 1, FCC reduces to the standard compression utilized in existing While FCC requires R rounds of communication per iteration, the following lemma establishes that the compression error will be exponentially decreased with the number of communication rounds R.
literature 62
58
24
68
32
7

---

Algorithm 2 NEOLITHIC
Input: Initialize ,,(0); learning 7,, compression round R; 5(-1) o6- vi E [n]
for = 0, U, K do
On all workers in parallel:
Query stochastic gradients 9. 1
ER-1 ((((0)))(())))))
Gradient accumulation >
Ri
Error compensate 9 (k)
8 6(4-1)
Update error 0. 9i
(k) FCC Ci R. server)
Worker sends (c( to server
On server:
Error compensate g(() 5(k-1) + E Sh- (k.r)
(ot received from workers
oj
Update error 8(k) g(k) FCC (k),
Co, R, all workers)
P Server sends (c(h.r) } workers
On all workers in parallel:
Update model parameter (k+1) = xx)) Ex=o clk.r) D (clkr)) received from server
end for
Lemma (FCC property). Let be a 8-contractive compressor and (k..)) FCC(U((M) C, holds for any R and (((x*) E IRd that (proof is in Appendix
( - (1-6) ( Vk 0, 1,
(5)
When 1, the above FCC property pressors. When large, FCC can output (k. endowed with very small compression errors. The FCC protocol is also closely related to EF21 compression strategy [52 However, the major novelty of FCC is utilize multiple such compression rounds to help develop algorithms that can nearly match the established lower bounds.
5 reduces to Assumption for standard contractive com-
4.2 NEOLITHIC Algorithm
NEOLITHIC is described in Algorithm 2 The FCC protocol in NEOLITHIC communicates R rounds per iteration. To balance the gradient queries and communication rounds, NEOLITHIC will query R stochastic gradients per iteration, see the gradient accumulation step Algorithm 2. Compared to other algorithms listed in Table [ the proposed NEOLITHIC takes R times more gradient queries and communication rounds than them per iteration. Given the same budgets to query stochastic gradients and conduct communications as the other standard compression algorithms, we shall consider T/R iterations in NEOLITHIC for fair comparison.
We introduce the following assumption to establish the convergence rates of NEOLITHIC. Assumption (Gradient dissimilarity). There exists some b² such that
- - Vx E Rd.
When local distributions D; equivalent across all nodes i, have fa(x)) = fxx and the above assumption will always hold. We first establish the convergence rate of NEOLITHIC with bidirectional and contractive compressors.
Theorem 3 (NEOLITHIC with contractive compressors). Given constants > 1.
5 E (0, and Assumption 5 and let x(()) be generated by Algorithm 2 [max (In (8T max(b?, o28) / LL). (8) and learning rate set as Appendix holds for any K and compressors {C. C Cs that
Σ K+1
1
K
111
11:=
((ALO)) nnT
(ALO*)
AL
K
8T
where T K. is the total number of gradient query/communication rounds on each worker and notation Ó-) hides logarithmic factors. The above rate implies transient complexity of Ö
II the roles of and x in Eq. (8) of 52 switched, can get the single round of FCC recursions.

---

Least Square, 32
P-SGD
NEM-SGO
SCM
3.5
10
NIDUTTIC
Dousle Squereze
3.0
EF21-SGD NEOL ITHIC
Train
2.0
10-3
1.5
0.5
0.0
10"4
0
100
200
300
400
500
600
communication rounds
bits/n(1e8)
Figure 1: Left: Convergence the synthetic least square problem in terms of | (x))]] versus communi-
cation rounds. Right: Convergence on the CIFAR-10 terms of training loss versus communication cost.
When the compressor is replaced with w- unbiased compressors, we utilize the fact that (1+w)- is (1 + w)" -contractiv to derive that
Corollary 3 (NEOLITHIC with unbiased compressors). Under the same assumptions as in Theorem holds for any K 2 0 and compressors {C.) S Uw that
K
(ALo2) nT
+ (1+
Σ [I K=
K+1
This further leads to transient complexity of Ô (n(1 + w)
Remark 1. The convergence rates established in Theorem 3 and Corollary 3 are also valid for unidirectional compression when Co I. They can match the lower bounds established in Section up to logarithm factors. Moreover, these rates are faster than other algorithms listed in Table !
Remark 2. The results in Theorem 3 and Corollary Balso imply that NEOLITHIC with bidirectional compression can perform as fast as its counterpart with unidirectional compression. In other words, imposing bidirectional compression can save communications in NEOLITHIC without hurting that bidirectional compression leads to slower convergence than unidirectional compression for non-convex problems.
convergence rates. Before our work, is established literature [58 55 62
70 14
Remark 3. We remark that Assumption 5 is not required to obtain the lower bounds in Section 3 It is not known whether the lower bounds established in Section cann be achieved by NEOLITHIC when Assumption does not hold. However, it is worth noting that Assumption 3 is milder than those made in most works 182
T7] such as bounded gradients. To our best knowledge, only EF2 I-DD (24) is guaranteed to converge without Assumption 5 which, however, leads to a fairly loose convergence rate (see Table that cannot show limear-ppedupp (n]//TT).
34
58
68
62
Remark 4. In the deterministic scenario, i.e., 0² 0, NEOLITHIC produces rate (((1+))LLTT)
There exist literature (e.g.. (26) (33) that can achieve rate Ö((1 + W/n)AL/TT which outperforms NEOLITHIC especially when w and n are sufficiently large. However, this improvement is built upon additional assumption that all local compressors {C:); are independent of each other and cannot share the same randomness. On the contrary, NEOLITHIC does not impose such an assumption and can be applied both dependent and independent compressors.
Experiments
This section empirically investigates the performance of different compression algorithms with both synthetic simulation and deep learning tasks. We compare NEOLITHIC with PSGD and its variants with communication compression: MEM-SGD, Double-Squeeze and EF21-SGD. Implementation details and more experiments are provided in Appendix C
Linear regression. We solve a synthetic least-square square problem with all aforementioned algorithms. We set d = 30, n = 32, R = 4 (for NEOLITHIC) and utilize the rand-l compressor. It is observed in Figure [ (left) that NEOLITHIC beats MEM-SGD and Double-Squeeze with performance close to P-SGD. implies that algorithms with bidirectional compression can converge as fast as the counterparts with unidirectional compression, which is consistent with results in Remark []

---

Table Accuracy comparison with different algorithms on CIFAR-IO (8 workers, compression ratio).
METHODS
8ESNET18
RESNET20
PSGD
93.99 0.52
91.62 + 0.13
MEM-SGD
94.35 0.01
91.27 0.08
DOUBLE-SQUEEZE
90.73 9.11
EF-21
87.37 +.477
65.82 4.86
NEOLITHIC
94.63 # 0.09
91.43 0.10
Table 3: Accuracy comparison with different algorithms on CIFAR-I0 (8 workers, 1% compression ratio).
METHODS
RESNETI8
RESNET20
93.99 + 0.11
89.68 0.17
DOUBLE DOUBLE-SQUEEZE
3..17
89.35 0.04
EF-21
67.78 + 2.14
NEOLITHIC
94.155 0.10
89.82 # 0.37
Image classification. We investigate the performance two common ResNet models [27 with CIFAR-10 (37] dataset. We train total 300 epochs and set the batch size to 128 on every worker. All experiments were repeated three times with different seeds. For NEOLITHIC, we set R = 2. We
utilize top-k compressor [62 with different compression ratios. As shown in Figure | (right) and
Table 2 NEOLITHIC consistently outperforms other compression methods and reach the similar performance to PSGD.
The effeec of compression ratio. We also investigate the influence of different compression ratios. Table used compression ratio 1,, which indicates a more harsh setting for compression methods. NEOLITHIC still outperforms other compression methods.
6
Conclusion
This paper provides lower bounds for distributed algorithms with communication compression, whether the compression is unidirectional or bidirectional and unbiased or contractive. An algorithm called NEOLITHIC introduced to match the lower bounds under the assumption of bounded gradi- ent dissimilarity. Future directions include developing optimal algorithms without the assumption, as well as discovering additional compression properties that might produce a better lower bound.
Acknowledgements
The authors are grateful to Professor Peter Richtarik from KAUST for the helpful discussions in the relation between FCC and EF21 and various other useful suggestions.
References
[1] A. Agarwal and L. Bottou. A lower bound for the optimization of finite sums. In International Conference on Machine Learning. 2015.
[2] A. Agarwal and C. Duchi. Distributed delayed stochastic optimization. In IEEE Conference on Decision and Control, pages 5451-5452, 2012.
[3] S. A. Alghunaim and K. Yuan. unified and refined convergence analysis for non-convex decentralized learning. arXiv preprint arXiv:21 10.09993, 2021.
[4] D. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnovic. Qsgd: Communicatonn-fficienn sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, 2017.
[5] D. Alistarh, T. Hoefler, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, 2018.
[6] Allen-Zhu. How to make the gradients small stochastically: Even faster convex and noncon- vex sgd. In Advances in Neural Information Processing Systems, 2018.
10

---

[7] Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. E. Woodworth. Lower bounds for non-convex stochastic optimization. ArXiv, abs/1912.02365. 2019.
[8] Y. Arjevani and O. Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems, 2015.
[9] M. Assran, N. Loizou, N. Ballas, and M. Rabhat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pages 344-353, 2019.
[10] E. Balkanski and Y. Singer. Parallelization does not accelerate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. ArXiv, abs/ 1tw./188.0000 808.03880 2018.
[11] D. Basu, D. Data, C. Karakuş, and S. N. Diggavi. Osparse-local-sge Distributed sgd with quantization, sparsification, and local computations. IEEE Journal on Selected Areas in Information Theory, 1:217-226, 2020.
[12] J. Bernstein, Y.-X. Wang, K. Azizzadenesheli, and A. Anandkumar. Signsgd: compressed optimisation for non-convex problems. In International Conference on Machine Learning, 2018.
[13] J. Bernstein, J. Zhao. K. Azizzadenesheli, and A. Anandkumar, signsgd with majority vote is communication efficient and byzantine fault tolerant. ArXiv, abs/ 10.05291, 2018.
[14] A. Beznosikov, S. Horvath, Richtárik, and M. H. Safaryan. On biased compression for distributed learning. ArXiv, abs/2002. 12410, 2020.
[15] L. Bottou. Large-scale machine learning with stochastic gradient descent. In COMPSTAT, 2010.
[16] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points
i. Mathematical Programming, pages 1-50, 2020.
[17] Y. Carmon, C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185:315-353 --555,3552250 2021.
[18) T. Chen, G. Giannakis, T. Sun, and W. Yin. LAG: Lazily aggregated gradient for communication- efficient distributed learning. In Advances in Neurul Information Processing Systems, pages 5050-5060, 2018.
[19] Y. Chen, K. Yuan, Y. Zhang, P. Pan, Y. Xu, and W. Yin. Accelerating gossip SGD with periodic global averaging. In International Conference on Machine Learning, 2021.
[20] A. De, S. Khanna, H. Li, and M. NikpeySalekde. Approximate optimization of convex functions with outlier noise. Advances in Neural Information Processing Systems, 2021.
[21] Dean, G. Corrado, R. Monga, K. Chen, M. Devin, Q. V. Le, M. Z. Mao, M. Ranzato, A. W. Senior, P. A. Tucker, K. Yang, and A. Ng. Large scale distributed deep networks. In Advances in Neural Information Processing Systems, 2012.
[22] J. Diakonikolas and C. Guzmán. Lower bounds for parallel and randomized convex optimization.
In Conference on Learning Theory, 2019.
[23] C. Fang, C. J. Li, Z. Lin, and T. Zhang. Spider: Near-optimal non-convex optimization via stochastic path integrated differential estimator. In Advances in Newral Information Processing Systems, 2018
[24] Fatkhullin, I. Sokolov, A. Gorbunov, Li, and P. Richtárik. Ef21 with bells & whistles: Practical algorithmic extensions of modern error feedback. ArXiv, abs/2110.03225 2021.
[25] D. J. Foster, A. Sekhari, O. Shamir, N. Srebro, K. Sridharan, and B. E. Woodworth. The complexity of making the gradient small in stochastic convex optimization. In Conference on Learning Theory, 2019.
[26] E. A. Gorbunov, K. Burlachenko, Z. Li, and P. Richtárik. Marina: Faster non-convex distributed learning with compression. ArXiv, 2021.
[27] K. He. X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, 2016.
[28] S. Horvath, C.-Y. Ho, I. Horvath, A. N. Sahu, M. Canini, and P. Richtárik, Natural compression for distributed deep learning. ArXiv, 10011905519988. 2019.

---

[29] S. Horvath, D. Kovalev, K. Mishchenko, S. U. Stich, and P. Richtárik. Stochastic distributed learning with gradient quantization and variance reduction, arXiv: Optimization and Control, 2019.
[30] X. Huang and K. Yuan. Optimal complexity in non-convex decentralized learning over time- varying networks. arXiv preprint S.di:222/.005333 2022.
[31] X. Huang, K. Yuan, X. Mao, and W. Yin. Improved analysis and rates for variance reduction under without-replacement sampling orders. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[32] Jiang and G. Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems, 2018.
[33] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, 2020.
[34] S. P. Karimireddy, Q Rebjock, S. U. Stich, and M. Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, 2019.
[35] D. Kingma and J. Ba. Adam: A method for stochastic optimization. CoRR, abs/1412.6980, 2015.
[36] A. Koloskova, T. Lin, and S. Stich. An improved analysis of gradient tracking for decentral- ized machine learning. In Advances in Neural Information Processing Systems, 2021.
[37] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's thesis, Department of Computer Science, University of Toronto, 2009.
[38] M. Li, D. G. Andersen, J. W. Park, A. Smola, A. Ahmed, V. Josifovski, J. Long, E. J. Shekita, and B.-Y. Su. Scaling distributed machine learning with the parameter server. In OSDI, 2014.
[39] 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 Advances in Neural Information Processing Systems, 2017.
[40] T. Lin, S. P. Karimireddy, S. U. Stich, and M. Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In International Conference on Machine Learning, 2021.
[41] Y. Lin, S. Han, H. Mao, Y. Wang, and W. J. Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. ArXiv, abs/1712.018877, 2018.
[42] X. Liu, Y. Li,, R. Wang, J. Tang, and M. Yan. Linear convergent decentralized optimization with compression. In International Conference on Learning Representations, 2021.
[43] Y. Lu and C. D. Sa. Optimal complexity in decentralized training. In International Conference on Machine Learning, 2021.
[44] K. Mishchenko, E. A. Gorbunov, M. Takác, and P. Richtárik. Distributed learning with compressed gradient differences. ArXiv, abs/1901.09208 2019.
[45] A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1):48-66) 61, 2009.
[46] Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence 0(1K2), In Doklady ussr, volume 29, 1983.
[47] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin,
N. Gimelshein, L. Antiga, et al. Pytorch: An imperative style, high-performance deep learning 2019.
library. In Advances in Neural Information Processing Systems, pages
[48] C. Philippenko and A. Dieuleveut. Preserved central model for faster bidirectional compression in distributed settings. Advances in Neural Information Processing Systems, 2021.
[49] C. Philippenko and A. Dieuleveut. Bidirectional compression heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. ArXiv, 2022.
[50] Pu, A. Olshevsky, and C. Paschalidis. sharp estimate on the transient time of distributed stochastic gradient descent. arXiv preprint 190iv: 02w000000022............2.2222 2019.
12

---

[51] X. Qian. P. Richtárik, and T. Zhang. Error compensated distributed sgd can be accelerated. arXiv, 2020.
[52] P. Richtárik, I. Sokolov, and I. Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. ArXiv, abs/2106.052000 2021.
[53] Richt' arik, Sokolov, I. Fatkhullin, E. Gasanov, Li, and E. A. Gorbunov. 3pe: Three point compressors for communication-effiiene distributed training and a better theory for lazy aggregation. In International Conference on Machine Learning, 2022.
[54] M. H. Safaryan, E. Shulgin, and P. Richtárik. Uncertainty principle for communication compres- sion in distributed and federated learning and the search for an optimal compressor. Information and Inference: A Journal of the IMA, 2021.
[55] A. N. Sahu, A. Dutta, A. M. Abdelmoniem, T. Banerjee, M. Canini, and P. Kalnis. Rethinking gradient sparsification as total error minimization. In Advances in Neural Information Processing Systems, 2021.
[56] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In INTERSPEECH, 2014.
[57] S. U. Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2019.
[58] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, 2018.
[59] H. Sun, Y. Shao, Jiang, B. Cui, K. Lei, Y. Xu, and J. Wang. Sparse gradient compression for distributed sgd. In Database Systems for Advanced Applications. 2019.
[60] H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu. Communication compression for decentralized training. In Advances in Neural Information Processing Systems, 2018
[61] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu. d: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4856, 2018
[62] H. Tang, X. Lian, T. Zhang, and J. Liu. Doublesqueeze: Parallel stochastic gradient descent with double-past saoblee-pssseeee ewror- crro--compensate compression. ArXiv,
2019.
[63] A. Tyurin and P. Richt'arik Dasha: Distributed nonconvex optimization with communication compression, optimal oracle complexity, and no client synchronization. ArXiv, 2022.
[64] T. Vogels, S. P. Karimireddy, and M. Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems, 2019.
[65] J. Wangni, J. Wang, J. Liu, and T. Zhang. Gradient sparsification for communication--fficcee distributed optimization. Advances in Neural Information Processing Systems, 2018
[66] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. H. Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, 2017.
[67] J. Wu, W. Huang. J. Huang, and T. Zhang. Error compensated quantized sgd and its applications to large-scale distributed optimization. In International Conference on Machine Learning, 2018.
[68] C. Xie, S. Zheng, O. Koyejo, I. Gupta, M. Li, and H. Lin. Cser: Communication-effccceent sgd with error reset. In Advances in Neural Information Processing Systems, 2020.
[69] R. Xin, U. A. Khan, and Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 2020.
[70] A. Xu, Z. Huo, and H. Huang. Step-ahead error feedback for distributed training with com- pressed gradient. In Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[71] H. Xu, C.-Y. Ho, A. M. Abdelmoniem, A. Dutta, F. H. Bergou, K. Karatsenidis, M. Canini, and Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, 2020.
[72] B. Ying, K. Yuan, Y. Chen, H. Hu, P. Pan, and W. Yin. Exponential graph is provably efficient for decentralized deep training. In Advances in Neural Information Processing Systems, 2021.
[73] H. Yu, R. Jin, and S. Yang. On the linear speedup analysis of communication efficient momentum sgd for distributed non-convex optimization. In International Conference on Machine Learning, pages 7184-7193. PMLR, 2019.
13

---

[74] K. Yuan, S. A. Alghunaim, and X. Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized sgd. arXiv preprint 0rXiv:2105.08023 2021.
[75] K. Yuan, Y. Chen, X. Huang, Y. Zhang, P. Pan, Y. Xu, and W. Yin. Decentlam: Decentralized
momentum sgd for large-batch deep training. In 2021 IEEF/CVF International Conference on Computer Vision (ICCV), pages 3009-3019, 2021.
[76] K. Yuan, X. Huang, Y. Chen, X. Zhang, Y. Zhang, and P. Pan. Revisiting optimal convergence rate for smooth and non-convex stochastic decentralized optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[77] K. Yuan, Q. Ling, and W. Yin. On the convergence of decentralized gradient descent. SIAM Journal of Optimization, 26:1 1335-1888,, 2016.
[78] N. Yurri. Introductory Lectures Convex Optimization: Basic Course. Kluwer Academic Publishers, Norwell, 2004.
[79] M. D. Zeiler. Adadelta: An adaptive learning rate method. ArXiv, abs/ 1212.521,,,00, 2012.
[80] H. Zhang, Li, K. Kara, Alistarh, J. Liu, and C. Zhang. Zipml: Training linear models with end-to-end low precision, and little bit of deep learning. In International Conference on Machine Learning, 2017.
[81] H. Zhao, Li. Z. Li, Richt' arik, and Y. Chi. Beer: Fast o(It) rate for decentralized nonconvex optimization with communication compression. In Advances in Neural Information Processing Systems, 2022.
[82] S.-Y. Zhao, Y.P.. Xie, H. Gao, and W.-J. Li. Global momentum compression for sparse communication distributed sgd. ArXiv, abs/1905. 12948, 2019.
[83] D. Zhou and Q. Gu. Lower bounds for smooth nonconvex finite-sum optimization. ArXiv, abs/1901. 12224, 2019.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "bskWzb7Tg-h", "reviewer": "Reviewer_wUMh", "summary": "The paper studies the problem of minimizing the objective, defined as a  finite sum of smooth and possibly non-convex functions in a Federated learning setting.\nThis paper aims to tackle the problem of expensive communications that appeared in the distributed scenario between one central server and multiple nodes\\workers.\nIn particular, this work considers unidirectional and bidirectional communication compression as the approach to tackle the problem of communication bottleneck.\nLooking into details authors establish the following list of contributions:\n\n1) They establish convergence lower bounds for distributed algorithms with communication compression in the stochastic non-convex regime. This lower bound is applicable to any algorithm performing unidirectional or bidirectional compression and using unbiased or contractive compressors. They clearly compare the established lower bounds and convergence rates of the existing methods.\n\n2) They propose a novel, nearly optimal algorithm with compression called NEOLITHIC that provably matches the established lower bound. Moreover, NEOLITHIC can adopt either unidirectional or bidirectional compression and is compatible with both unbiased and contractive compressors. \n\n3) In particular, the convergence result of NEOLITHIC shows that algorithms using biased contractive compressors bidirectionally can theoretically converge as fast as those with unbiased compressors used unidirectionally.\n\n4) In addition, they provided a set of numerical experiments comparing their novel method with existing baselines.\n", "questions": "1) Experiments on least squares and logistic regression:\nRegarding compression properties, it is only said that the rand-1 compressor is utilized. \n- 1) Could you please clarify whether you are using scaled rank-1% in all methods? Do you use unidirectional or bidirectional compression for NEOLITHIC?\n- 2) Is there any reason why you exclude EF21-SGD from the comparison?\n- 3) What stepsizes did you use? Were they constant or decreasing?\n\n2) Could you please compare rates of VR-MARINA and DAHSA with QSGD that was mentioned in Table 1?\n\n3) Could you please clarify where did you get the following rate for MEM-SGD (mentioned in Table 1):\n\n$\\mathcal O\\left(\\frac{\\sigma}{\\sqrt{n T}}+\\frac{G^{2 / 3}}{\\delta^{2 / 3} T^{2 / 3}}+\\frac{1}{T}\\right)$\n\nI checked the original work [4] and does not have any results on non-convex losses. In fact, it deals only with convex losses.\n\n4) The same question about method CSER [5].\nI checked the original work, and it shows (Corollary 1 on page 20) that the rate of CSER does not have a term with 1/T dependence. Could you please clarify this inconsistency with Table 1?\n \n5) I checked the original paper on Double Sqeeze, and their rate is \n\n$\\frac{1}{T} \\sum_{t=0}^{T-1} \\mathbb E \\lVert\\nabla f\\left(\\boldsymbol{x}_{t}\\right)\\rVert^{2} \\lesssim \\frac{\\sigma}{\\sqrt{n T}}+\\frac{\\epsilon^{\\frac{2}{3}}}{T^{\\frac{2}{3}}}+\\frac{1}{T}$ \nwhere $\\epsilon$ is the noise bound, such that\n\n$ \\mathbb E_{\\omega} \\lVert {\\delta}_{t}^{(i)} \\rVert \\leq \\frac{\\epsilon}{2},  \\forall t, \\forall i $\n\n$ \\mathbb E_{\\omega} \\lVert {\\delta}_{t} \\rVert \\leq \\frac{\\epsilon}{2},  \\forall t$. \n\nHowever, Table 1 says that Double Squeeze has a rate \n\n$\\mathcal O\\left(\\frac{1}{\\sqrt{n T}}+\\frac{G^{2 / 3}}{\\delta^{4 / 3} T^{2 / 3}}+\\frac{1}{T}\\right)$\n\n(the second term differs compared to the original work).\n\nCould you please clarify this inconsistency?\n\n6) Regarding QSGD, using the notation of Paper8019, Corollary 3 in [6] states the rate \n\n$\\mathcal O\\left(\\frac{(1 + \\omega)\\sigma^2 + \\omega b^2}{\\sqrt{MT} } \\right)$, where M is minibatch size (not a number of workers $n$). \n\nAt the same time, Table 1 claims \n\n$\\mathcal O\\left(\\frac{(1+\\omega) \\sigma+\\omega b^{2} / \\sigma}{\\sqrt{n T}}\\right)$.\n\nCould you please clarify this inconsistency in the QSGD rate from Table 1 and the original result from [6]?\n\nReferences:\n\n[4] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. In Advances in Neural 445\nInformation Processing Systems, 2018.\n\n[5] C. Xie, S. Zheng, O. Koyejo, I. Gupta, M. Li, and H. Lin. Cser: Communication-efficient sgd 464\nwith error reset. In Advances in Neural Information Processing Systems, 2020.\n\n[6] Jiang, Peng, and Gagan Agrawal. \"A linear speedup analysis of distributed deep learning with sparse and quantized communication.\" Advances in Neural Information Processing Systems 31 (2018).", "limitations": "1) I would recommend making the y-axis in the right subfigure of Figure 1 logarithmic scale. Otherwise, it is hard to distinguish plots corresponding to different methods.\n\n2) One more possibly relevant and missing citation is [7]. The Algorithm 3PCv3 (Appendix C.6, page 26) already employs a similar nested structure as proposed in Paper8019 by FCC.\n\n3) I would recommend running least squares and logistic regression experiments for a longer period. It looks like the methods on the left subfigure of Figure 1 and Figure 2 were stopped quite early and did not reach the SGD-specific oscillation region.\n\n4) Some minor notes:\n- 1) (line 685): instead of Cauchy-Schwarz, one needs to refer to Young's inequality for product;\n- 2) (line 693): instead of Cauchy-Schwarz, one needs to refer to Jensen's inequality\n\nFINAL REMARKS: \n\nI would be happy to rate this paper an 8 for its solid theoretical contributions and reliable experiments. \n\nHowever, at this moment, I can not do so since the paper still contains several crucial issues that are needed to be clarified or fixed. \n\nI am ready to reconsider my current rate during rebuttals once you respond to me on Weaknesses 2-4 and Questions 1 - 6.\n\nUPDATE: After the Authors-Reviewers discussion, I decided to increase the score since my concerns were resolved.\n\nReferences:\n[7] Richtárik, Peter, Igor Sokolov, Ilyas Fatkhullin, Elnur Gasanov, Zhize Li, and Eduard Gorbunov. 2022. “3PC: Three Point Compressors for Communication-Efficient Distributed Training and a Better Theory for Lazy Aggregation.” arXiv [cs.LG]. arXiv. http://arxiv.org/abs/2202.00998.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) The paper is very well written and easily read; the main claims are outlined. The paper adequately mentions related works, including other papers establishing lower bounds. In addition, it clearly explains \ntheir relationship to this one. All notations that is being used in the theoretical claims are rigorously defined. \n\n2) To the best of my knowledge, this is the first work establishing lower bounds for stochastic methods involving unidirectional and bidirectional compressions in a Federated learning setting. It closes an essential gap in such a relevant area.\n\n3) Being a solid theoretical paper, it provides an extensive amount of experiments. Firstly, they confirm that NEOLITIC has a similar convergence rate as parallel-SGD, MEM-SGD, and Double Squeeze on least squares and logistic regression problems. Secondly, On the CIFAR10 classification problem via ResNet, train loss of NEOLITHIC converges slightly better than Double Squeeze and EF21-SGD, and it is compatible with MEM-SGD. However, the Top1 accuracy metric of NEOLITHIC outperforms all considered baselines in experiments on ResNet18 and ResNet20 with 1% and 5% compression ratios.\n\nWeaknesses:\n\n1)\nThe main theoretical flaw is that the analysis of NEOLITHIC relies on a restrictive Assumption 5 (bounded dissimilarity):\n\n$$\\frac{1}{n} \\sum_{i=1}^{n} \\lVert \\nabla f_{i}(x)-\\nabla f(x) \\rVert^{2} \\leq b^{2}, \\quad \\forall x \\in \\mathbb R^{d}$$\n\nOne can easily come up with an example for which this assumption does not generally hold.\nFor example, let us consider $f_{i}(x)=x^{\\top} \\mathbf A_{i} x$, where $\\mathbf A_{i} \\in \\mathbb R^{d \\times d}$. Since $\\nabla f_{i}(x)=\\mathbf B_{i} x$, where $\\mathbf B_{i}=\\mathbf A_{i}+\\mathbf A_{i}^{\\top}$.  The bounded dissimilarity assumption (Assumption 5), which can be written in the form $\\frac{1}{n} \\sum_{i=1}^{n}\\left\\|\\left(\\mathbf B_{i}-\\frac{1}{n} \\sum_{j=1}^{n} \\mathbf B_{j}\\right) x\\right\\|^{2} \\leq b^{2}$, also does not hold, unless $\\mathbf B_{i}=\\mathbf B_{j}$ for all $i, j$, which reduces to the identical data regime, which is of limited interest.\n\n2) Some details on the experimental setting are missing. See Question 1) in the next section.\n\n3) Literature review ignores several papers that are seemed to be relevant [1], [2]. It seems VR-MARINA for online problems from [1] and DASHA-MVR from [2] both satisfy Assumption 2 and have a better rate than QSGD in the stochastic regime.  See Question 2) in the next section. \n\n4) Table 1 contains possible typos: \n- 1) It mentions a paper on MEM-SGD that does not have a non-convex rate. Their rate is applicable to strongly convex functions. I would recommend here to mention another, more relevant work [3].  See Question 3) in the next section. \n- 2) Similar problems with CSER, Double Squeeze, and QSGD.  See corresponding Questions 4), 5) and 6) in the next section.\n\nReferences:\n\n[1] Gorbunov, Eduard, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. 2021. “MARINA: Faster Non-Convex Distributed Learning with Compression.” arXiv [cs.LG]. arXiv. http://arxiv.org/abs/2102.07845.\n\n[2] Tyurin, Alexander, and Peter Richtárik. 2022. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” arXiv [cs.LG]. arXiv. http://arxiv.org/abs/2202.01268.\n\n[3] Koloskova, A., Lin, T., Stich, S. U., \\& Jaggi, M.. Decentralized deep learning with arbitrary communication compression. arXiv preprint arXiv:1907.09356, 2019\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Nv3Tgz60Yu", "reviewer": "Reviewer_nEJw", "summary": "This work considers smooth and non-convex distributed learning problem under communication compression schemes to reduce communication costs between the server and devices. It discusses widely adopted classes of unbiased and contractive compression operators, unidirectional (device to server) and bidirectional (device to server and server to device) communication compression schemes. The paper proposes lower bounds on the number of stochastic gradient evaluations (or communication rounds) for all these regimes and designs a method, called NEOLITHIC, that achieves those lower bounds for the mentioned regimes up to log factors.", "questions": "Please see the comments under Strengths And Weaknesses section. The critical points are detailed comments (1) and (2).", "limitations": "IMO, no need.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**(1: Lower bounds).** There are 4 lower bounds discussed in the paper: two classes of compression operators (unbiased or contractive) and two types of communication reduction schemes (unidirectional or bidirectional). The first result (Theorem 1) shows the lower bound for unidirectional unbiased compression and the other three lower bounds are corollaries from Theorem 1 following standard arguments (unidirectional compression is a special case of bidirectional one and unbiased compression can be treated as a special case of contractive compression). ***However, the lower bound (3) of Theorem 1 does not seem consistent with existing upper bounds.*** As you mention in lines 64-65, algorithms with unidirectional and unbiased compressors enjoy better convergence rates. Specifically, convergence rates with unbiased compressions typically depends on $\\frac{\\omega}{n}$. For example, the method MARINA from [27](Gorbunov et. al. 2021 - Marina: faster non-convex distributed learning with compression) has $(1+\\frac{\\omega}{n})\\frac{1}{T}$ rate with full gradients (i.e., $\\sigma=0$). On the other hand, the lower bound (3) claims $(1+\\omega)\\frac{1}{T}$ rate when $\\sigma=0$. In other words, the upper bound from [27] is better than the proposed lower bound (3). As the other lower bounds are special cases of (3), ***the correctness of the lower bounds are questionable.***\n\n\n**(2: Upper bound).** ***The proof of the convergence rate of the proposed NEOLITHIC algorithm has an issue.*** The proof of Theorem 3 goes quite neat and clean up to equation (45). To get to the issue, consider (44) showing the following rate for the method (ignoring constants):\n$$\n\\mathbf{E} [ || \\nabla f(\\hat{x}) ||^2 ] \\lesssim \\frac{1}{\\gamma K} + \\frac{\\gamma \\sigma^2}{n R} + \\gamma^2\\theta.\n$$\n\nThen, choosing the stepsize as in (45), it continues (before equation (46))\n$$\n\\mathbf{E} [ || \\nabla f(\\hat{x}) ||^2 ] \\lesssim \\frac{1}{\\gamma K} + \\frac{\\gamma \\sigma^2}{n R} + \\gamma^2\\theta  {\\color{red} \\lesssim \\frac{\\sigma}{\\sqrt{n R K}} + \\frac{\\theta^{1/3}}{K^{2/3}} + \\frac{1}{K}}.\n$$\n\n***I do not think that this upper bound in red holds.*** In particular, $\\frac{1}{\\gamma K}$ term ($\\frac{8\\Delta}{\\gamma(K+1)}$ exact expression) in (44) is upper bounded by $\\frac{1}{K}$ (exact expression is $\\frac{88L\\Delta}{K+1}$) using the upper bound $\\gamma \\le \\frac{1}{11L}$ from (45). However, since $\\gamma$ is in the denominator of $\\frac{1}{\\gamma K}$ term, we have the ***reverse inequality***, namely $\\frac{8\\Delta}{\\gamma(K+1)} {\\color{red}\\ge} \\frac{88L\\Delta}{K+1}$. In order to upper bound $\\frac{1}{\\gamma K}$ by $\\frac{1}{K}$, one need to have a lower bound for $\\gamma$. But, the choice (45) for $\\gamma$ does not allow a lower bound, namely $\\gamma\\to0$ as $T\\to\\infty$.\n\n\nMoreover, ***I do not think this issue can be fixed and the same rate of Theorem 3 be proven***. In order to minimize the sum of first two terms $\\frac{1}{\\gamma K} + \\frac{\\gamma \\sigma^2}{n R}$, one needs to choose $\\gamma$ such that $\\frac{1}{\\gamma K} = \\frac{\\gamma \\sigma^2}{n R}$, which implies that $\\gamma = \\frac{1}{\\sigma}\\sqrt{\\frac{nR}{K}}$. With this choice of $\\gamma$, the first two terms recover the desired term in the rate, namely $\\frac{1}{\\gamma K} + \\frac{\\gamma \\sigma^2}{n R} \\lesssim \\frac{\\sigma}{\\sqrt{nT}}$. However, the third term $\\gamma^2\\theta$ becomes $\\frac{nR}{K\\sigma^2}\\frac{1}{\\delta T} \\lesssim \\frac{n}{\\sigma^2} \\frac{1}{\\delta^3 T^2}$, which blows up when $\\sigma\\approx 0$.\n\n--------\n\n**(3: References on Table 1).** Does the reference [32] really showed the mentioned rate, which blows up for $\\sigma\\approx 0$ ? MEM-SGD paper [53] seems to be on convex problems, could you point the place in [53] where the non-convex rate is mentioned ? There are some typos in the rate of DoubleSqueeze, I think the rate is $\\mathcal{O}(\\frac{\\sigma}{\\sqrt{nT}} + \\frac{G^{2/3}}{\\delta^{1/3}T^{2/3}} + \\frac{1}{T})$.\n\n**(4: On FCC).** I understand why FCC (with $R>1$) is introduced and used in the proof. However, FCC sends $R$ times more bits and I think this cost outweighs the exponential decay of the error shown in Lemma 2. For example, applying Top-$2$ is (slightly) better applying Top-$1$ twice (namely FCC with Top-$1$ and $R=2$). The reason is that theoretical contraction factor of Top-$2$ is smaller than of FCC with $R=2$, i.e., $1-\\frac{2}{d} < (1-\\frac{1}{d})^2$.\n\n**(5: On Remark 2).** Check the MCM algorithm of (Philippenko and Dieuleveut 2021 - Preserved central model for faster bidirectional compression in distributed settings) related to bidirectional/unidirectional communication compression.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "NaqfKjDC1sG", "reviewer": "Reviewer_MLpo", "summary": "This paper is focused on the compression technique of distributed ML. It considers two well-studied types of compressors, i.e., the unbiased compressor and the contractive compressor. The paper provides lower bounds for those compression algorithms in the context of both unidirectional and bidirectional communication. Based on this theory, the authors come up with a new distributed training algorithm called NEOLITHIC. According to the experiment results, NEOLITHIC can achieve better training accuracy compared with the existing compressed algorithm.", "questions": "- As mentioned in the appendix, it seems that 2 is the best value for communication round R. Can you explain why?\n- Assuming R=2, then NEOLITHIC has 2 times more communication overhead than other methods, therefore it only has T/2 iterations for training. But with half number of iterations, how can you guarantee the best accuracy? In other words, in order to achieve the best accuracy, do you still need to train with NEOLITHIC for the same iterations as other methods? \n- Given your theory, can you give compression guidelines for a distributed task? For example, for a given task (optimization problem), how can you decide the following: 1) which compressor can achieve the best accuracy 2) how much is the compression ratio 3) unidirectional or bidirectional?", "limitations": "Please refer to the weakness.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Strength\n    - This paper takes unbiased and contractive compressors, unidirectional and bidirectional communication patterns all into a unified analysis, which can be quite helpful to better understand this field from a new perspective.\n    - The theoretical analysis is solid and clear.\n    - The proposed algorithm NEOLITHIC is quite creative in the sense that it involves multiple communication rounds to send a vector once.\n- weakness\n    - In the experiment, the authors only use contractive compressors, like random-1, top-k, but not unbiased compressors. So the effectiveness of quantization is not clear", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept