Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?
Authors: Yutong He
Xinmeng Huang
Kun Yuan
Venue: NeurIPS 2023 poster (2023)
Keywords: Communication Compression
Distributed Optimization
Unbiased Compression
Optimal Complexity
TL;DR: This paper explores when unbiased compression can reduce the total communication cost and how much it can do so

Abstract: Communication compression is a common technique in distributed optimization
that can alleviate communication overhead by transmitting compressed gradients
and model parameters. However, compression can introduce information distortion,
which slows down convergence and incurs more communication rounds to achieve
desired solutions. Given the trade-off between lower per-round communication
costs and additional rounds of communication, it is unclear whether communication
compression reduces the total communication cost.

This paper explores the conditions under which unbiased compression, a widely
used form of compression, can reduce the total communication cost, as well as the
extent to which it can do so. To this end, we present the first theoretical formulation
for characterizing the total communication cost in distributed optimization with
unbiased compressors. We demonstrate that unbiased compression alone does not
necessarily save the total communication cost, but this outcome can be achieved
if the compressors used by all workers are further assumed independent. We
establish lower bounds on the communication rounds required by algorithms using
independent unbiased compressors to minimize smooth convex functions and
show that these lower bounds are tight by refining the analysis for ADIANA.
Our results reveal that using independent unbiased compression can reduce the
total communication cost by a factor of up to $\Theta(\sqrt{\min\\{n,\kappa\\}})$ when all local
smoothness constants are constrained by a common upper bound, where $n$ is the
number of workers and $\kappa$ is the condition number of the functions being minimized.
These theoretical findings are supported by experimental results.

Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?
Yutong He" Peking University yutonghe@pku, edu. on
Xinmeng Huang" University of Pennsylvania xinmenghōsas. upenn. edu
Kun Yuan Peking University kunyuanōpku edu, en
Abstract
Communication compression is common technique in distributed optimization that can alleviate communication overhead by transmitting compressed gradients and model parameters. However, compression can introduce information distortion, which slows down convergence and incurs more communication rounds to achieve desired solutions. Given the trade-off' between lower per-round communication costs and additional rounds of communication, it unclear whether communication compression reduces the total communication cost.
This paper explores the conditions under which unbiased compression, widely used form of compression, can reduce the total communication cost, as well as the extent to which it can do so. To this end, we present the first theoretical formulation for characterizing the total communication cost in distributed optimization with unbiased compressors. We demonstrate that unbiased compression alone does not necessarily the total communication cost, but this outcome be achieved if the compressors used by all workers are further assumed independent. We establish lower bounds the communication rounds required by algorithms using independent unbiased compressors to minimize smooth convex functions and show that these lower bounds tight by refining the analysis for ADIANA. Our results reveal that using independent unbiased compression can reduce the total communication cost by a factor of up to D(yming( k]) when all local smoothness constants are constrained by common upper bound, where n is the number of workers and x is the condition number of the functions being minimized. These theoretical findings are supported by experimental results.
Introduction
Distributed optimization is widely used technique in large-scale machine learning, where data distributed across multiple workers and training is carried out through worker communication. However, dealing with a vast number of data samples and model parameters across workers poses significant challenge in terms of communication overhead, which ultimately limits the scalability of distributed machine learning systems. To tackle this issue, communication compression strategies
55, 49 have emerged, aiming to reduce overhead by enabling efficient yet imprecise message transmission. Instead of transmitting full-size gradients models, these strategies exchange compressed gradients or model vectors of much smaller sizes communication.
3 g 52
There are two common approaches to compression: quantization and sparsification. Quantization 52 maps input vectors from large, potentially infinite, set to a smaller set of discrete values. In contrast, sparsification [57 55, 50 drops a certain amount of entries to obtain sparse
vector for communication. In literature 3 27 21, these compression techniques are often modeled
'Equal Contribution. Corresponding Author: Kun Yuan. Kun Yuan is also affiliated with National Engineer- ing Labratory for Big Data Analytics and Applications, and Science Institute, Beijing, China.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

as random operator C, which satisfies the properties of unbiasedness [[C(x)] = x and w- w--bounded variance [x]C(x) z1|² I wi <||==||? Here, z represents the input vector to be compressed, and w is fixed parameter that characterizes the degree of information distortion. Besides, part of the compressors can also be modeled as biased yet contractive operators [19
While communication compression efficiently reduces the volume of vectors sent by workers, it suffers substantial information distortion. As result, algorithms utilizing communication compression require additional rounds of communication to converge satisfactorily compared to algorithms without compression. This adverse effect of communication compression has been extensively observed both empirically [57 25 g and theoretically [21 49]. Since the extra rounds of communication needed to compensate for the information loss may outweigh the saving in the per-round communication cost from compression, this naturally motivates the following fundamental question:
Q1. Can unbiased compression alone reduce the total communication cost?
By "unbiased compression alone", we refer the compression that solely satisfies the assumptions of unbiasedness and w-bounded variance without any additional advanced properties. To address this open question,
formulate the total communication cost the product of the per-round communica- tion cost and the number of rounds needed to reach an e-accurate solution to distributed optmiization problems. Using this formulation, we demonstrate the decrease in the per-round communication cost from unbiased compression is completely offset by additional rounds of communication. Therefore, we answer Q1 by showing unbiased compression alone cannot ensure a lower total communication cost, even with an optimal algorithmic design, see Sec. [ for more details. This negative conclusion drives us to explore the next fundamental open question:
Q2. Under what additional conditions and how much unbiased compression provably save the total communication cost?
Fortunately, some pioneering works 40 32 33
have shed light on this question. They impose independence on unbiased compressors, i.c., the compressed vectors {C;(z))) 3 sent by workers are mutually independent regardless of the inputs { This independence assumption enables an "error cancellation" effect, producing more accurate compressed vector n Ei= C;(1;) and hence incurring fewer additional rounds of communication compared to dependent compressors. Consequently, the decrease in the per-round communication cost outweighs the extra communication rounds, reducing the total communication cost.
However, it remains unclear how much the total communication cost can be reduced at most by independent unbiased compression and whether reduction. Addressing this question poses significant challenges as it necessitates a study of the optimal convergence rate for algorithms using independent unbiased compression.
develop algorithms achieve this optimal
This paper provides the first affirmative answer to this question for convex problems by: (i) establishing lower bounds on convergence rates distributed algorithms employing independent unbiased compression, and (ii) demonstrating the tightness of these lower bounds by re- visiting ADIANA 32 and presenting novel and refined convergence rates nearly attaining the lower bounds. Our results reveal that compared non-compression algorithms, independent unbiased compression can save the total communication cost by up to @( min R-)-- fold, where is the number of workers and k E [1, +00 is the function condition number. Figure provides a
ADIANA Rand-1
10"
ADIANA id Rand-2
ADIANA Rand-4
Rand-
20
ADIANA a.d Rand-2
ADIANA a daRadd
10t1
10:14
1.0
2.0
2.0
4.0
5.0
6.0
communication bits (x1e3)
Performance of ADIANA us- ing random-s sparsification compressors with shared (s.d.) or independent (i.d.) randomness against distributed Nesterov's accelerated algo- rithm with no compression in communication. Experimental descriptions are in Appendix F.I
Figure
simple empirical justification. It shows independent compression (ADIANA i.d.) reduces communication costs compared to no compression (Nesterov's Accel- erated algorithm), while dependent compression (ADI- ANA s.d.) does not, which validates our theory.
1.1 Contributions
Specifically, our contributions are as follows:

---

Table 1: Lower and upper bounds on the number of communication rounds for distributed algorithms using unbiased compression to achieve an e-aceurate solution. Notations A n. I, (K _ L/μ 2 1) are defined
in Section 2 is parameter for unbiased compressors (Assumption Ô and ② hides logarithmic factors
independent GC and SC denote generally-convex and strongly-convex functions respectively.
Method
GC
SC
Lower Bound
? (w +
LL
((
(1 1+ v
VR
In (2)
Vn
Lower Bound 19
52
+ w) ve
((1+w) (t)
CGD
(1 (1+w) مA
Ô ((1+w)) in (t)
ACGD 3
(1+ vIa
((1+wVVEl (2))
DIANA 40
+w
0 ((++(1+))) K) (t)
EF21 49
(11 (W+ (A)
-/4 0(1+w))m (:)
ADIANA
32
6( (1
प: मं) vn) (n
CANITA 33
VLA Vc
[
1174
2//4
VLA Vt
NEOLITHIC 19
① (1 + w)
vL3
(1+
V2
ADIANA (Thm.
VTA E
+
LLA
(( (
3. In (:)
Results obtained in the single-worker setting and cannot be extended the distributed setting. The rate is obtained by correcting mistakes in the derivations of (33). See details in Appendix Results hold without assuming independence across compressors.
We present theoretical formalization of the total communication cost in distributed optimization with unbiased compression. With this formulation, we demonstrate that unbiased compression alone is insufficient to save the total communication cost, even with an optimal algorithmic design. This is because any reduction in the per-round communication cost is fully offset by the additional rounds of communication required due the presence of compression errors.
We prove lower bounds on the convergence complexity of distributed algorithms using indepen- dent unbiased compression to minimize smooth convex functions. Compared to lower bounds when using unbiased compression without independence [19]. our lower bounds demonstrate significant improvements when n and x are large, see the first two lines in Table [ This improvement highlights the importance of independence in unbiased compression.
We revisit ADIANA 32 by deriving an improved rate for strongly-convex functions and proving novel convergence result for generally-convex functions. Our rates nearly match the lower bounds, suggesting their tightness and optimality. Our optimal complexities reveal that, compared to non-compression algorithms, independent unbiased compression can decrease total communication costs by up to O min(n, (n, foldd when all local smoothness constants are constrained by common upper bound.
We support our theoretical findings with experiments on both synthetic data and real datasets.
We present the lower bounds, upper bounds, and complexities of state-of-the-arr distributed algorithms using independent unbiased compressors in Table With our new and refined analysis, ADIANA nearly matches the lower bounds for both strongly-convex and generally-convex functions.
1.2 Related work
Communication compression. Two main approaches to compression are extensively explored in literature: quantization and sparsification. Quantization coarsely encodes input vectors into fewer discrete values, e.g., from 32-bit to 8-bit integers [37 [8] Schemes like Sign-SGD 52 g use bit per entry, introducing unbiased random information distortion. Other variants such as Q-SGD 3 TurnGrad (58). and natural compression 20 quantize each entry with more effective bits. In contrast, sparsification either randomly zeros out entries to yield sparse vectors (57) or transmits only the largest model/gradient entries [55].
3

---

Error compensation. Recent works [52 59 55 propose error compensation or feedback to relieve the effects of compression errors. These techniques propagate information loss backward during compression, thus preserving more useful information. Reference [22 uses error compensation
for 1-bit quantization, while the work [59] proposes eroor-compensated quantization for quadratic problems. Error compensation also reduces sparsificatonninduuee errors (55] and is studied for convergence in non-convex scenarios [4]. Recently, the work [49] introduces EF21, an error feedback scheme that compresses only local gradient increments with improved theoretical guarantees.
Lower bounds in optimization set limit for the performance of single or class of algorithms. Prior works have established numerous lower bounds for optimization algorithms [ 6.
Lower bounds.
44]. In the field of distributed optimization with communication compression. reference 44 provides an eegorithm-speciinn lower bound for strongly-cony
64
17
functions, while the work [53] establishes the bit-wise complexities for PI.-type problems, which reflect the influence of the number of agents n and dimension d. but not the condition number i. and the compression w. In particular, [21] characterizes the optimal convergence rate for all first-order and linear- linear-spanning algorithms, in the stochastic non-convex case, which is later extended by [99 to convex cases.
Accelerated algorithms with communication compression. There scarcity of academic research on compression algorithms incorporating acceleration, as evident in a limited number of studies 32
33 48 References 32 331 develop accelerated algorithms with compression in
the strongly-conve and generally-conee cases, respectively. For distributed finite-sum problems, accelerated algorithms with compression can further leverage vuriance-reductioo techniques to expedite convergence 48
Other communication-effiiees strategies. Other than communication compression studied in this paper, there are few different techniques to mitigate the communication overhead in distributed systems, including decentralized communication and lazy communication. Notable examples of
decentralized algorithms encompass decentralized SGD 12 34 30 64], D2/Exact-Diffusion [56] 62]
61], gradient tracking [47 60, 29 21 and their momentum variants [55] 63 Lazy communication
allows each worker to either perform multiple local updates as opposed to a single communication
round 38 54
24
22 or by adaptively skipping communication 13 36
2 Problem setup
This section introduces the problem formulation and assumptions used throughout the paper. We consider the following distributed stochastic optimization problem
f(z) f()= f(()).
min ZER
(1)
where the global objective function f(x) is decomposed into n local objective functions {ff()))] and each local [i())) maintained by node Next, we introduce the setup and assumptions.
2.1 Function class
We let FE,, S μ S L) denote the class convex and smooth functions satisfying Assumption
I We define & L/ue [1, +oo] as the condition number of the functions to be optimized. When > 0. Fe, represents strongly-convex functions. Conversely, when ls = 0, F represents generally-conve functions with D0.
Assumption 1 (CONVEX AND SMOOTH FUNCTION). We assume each fz(z) is L-smooth and μ-strongly convex, i.e., there exists constants L 2 μ 2 O such that
lly x11² < f(()) fa(x) (Vf()),) x) < - x||
2
for any x, E Rd and 1 < < 5 n. We further assume || x=1 1 < A where x" is one of the global
minimizers of fx) = 1/2 Σー f((x).
2.2 Compressor class
Each worker E (1.... n is equipped with a potentially random compressor C₁ : Rd. We let Mm denote the set of all w-unbiased compressors satisfying Assumption 2 and 24ind denote the set of all independent w-unbiased compressors satisfying both Assumption 2 and Assumption 3

---

Assumption 2 (UNBIASED COMPRESSOR). We assume all compressors {Ci satisfy
B[C[(z)] 2, (x 2 =| S w|| e Rd
(2)
for constant 2 0 and anyy input R2, where the expectation taken over the randomness of the compression operator C
Assumption (INDEPENDENT COMPRESSOR). We assume all compressors {Ci]i=1 are mutually independent, i.e., outputs {C;( mutually independent random variables for any {az)i=r
2.3 Algorithm class
Similar to 19 we consider centralized and synchronous algorithms in which first, every worker allowed to communicate only directly with a central server but not between one another; second, all iteration/commmuniationn are synchronized, meaning that all workers start each of their iterations simultaneously. We further require algorithms satisfy the so-called "linear- "linear-spanning" property, which appears in [9] [00 21 [9] (see formal definition in Appendix C. Intuitively, this property requires each local model x to lie in the linear manifold spanned by the local gradients and the received messages at worker i. The sinear-spanning property is satisfied by all algorithms in Table ]
as well most first-order methods 42 28 23 65].
Formally, this paper considers a class of algorithms specified by Definition I
Definition (ALGORITIM CLASS). Given compressors {Ci] we let A(c.y denote the of all centralized, synchronous, linear-spanning algorithms admilling compression in which compressor C. LA Sis n, applied for the messages sent by worker to the server.
For any algorithm A E A we define at and x as the output of the server and worker i respectively, after & communication rounds.
2.4 Convergence complexity
With all the interested classes introduced above, ready define our complexity metric for convergence analysis. Given a set of local functions {f E Ff.... a set of compressors {C:}a= e C (C- u or Uw), and an algorithm A AAc,,,_, we let 4'A denote the output of algorithm A after t communication rounds. The convergence complexity of solving f(x) 1 -E fi())
under {(fi, C/ is defined as
n
(A, (ffs C.) = min { N: :. - min min f(x) sc
{(x)
(3)
This measure corresponds to the number of communication rounds required by algorithm A to achieve an e-accurate optimum of f (x) expectation.
Remark The measure in 3 commonly referred to as the communication complexity in literature (57 27 37 52%. However, we refer to it as the convergence complexity here to avoid potential confusion with the notion of "communication complexity" " and "total communication cost". This complexity metric has been traditionally used to compare communication rounds used by distributed algorithmss (32 33). However, cannot capture the total communication costs of multiple algorithms with different per-round communication costs, e.g., algorithms with or without communication compression. Therefore, is unable to address the motivating questions Q1 and Q2.
The definition Tf can be independent of the per-round communication cost, which is specified only through the degree of compression wi (i.e., choice of compressor class). However, to be precise, we may further assume these compressors are non-adaptive with the same fixed per-round communication cost. Namely, the compressors output compressed vectors that can be represented by a fixed and common number of bits. Notably, such hypothesis of non-adaptive cost is widely adopted for practical comparison of communication costs and is valid when input x is bounded or can be encoded with finite bits
Remark 2.
59 20 22
*Compression is typically employed input æ that bounded 59 or encoded with finite bits (e.g.. float64 numbers) (0). In these practical scenarios, w-unbiased compression can be employed with finite bits. For instance, random-s sparsitication for bit d-dimensional vectors costs (nearly) rs rd/(1 + w) bits per communication where d/s-
5

---

3 Total communication cost
3.1 Fomulation of total communication cost
This section introduces the concept of Total Communication Cost (TCC). TCC can be calculated at both the level of an individual worker and of the overall distributed machine learning system compris- ing all n workers. In a centralized and synchronized algorithm where each worker communicates compressed vectors of the same dimension, the TCC of the entire system is directly proportional to the TCC a single worker. Therefore, is sufficient to use the TCC of a single worker as the metric for comparing different algorithms. In this paper, we let TCC denote the total communication cost incurred by each worker in achieving a desired solution when no ambiguity is present.
Let each worker to be equipped with a non-adaptive compressor with the same fixed per-round communication cost, i.e., the compressor outputs compressed vectors of the same length (size), the TCC of an algorithm A to solve problem ① using set of w-unbiased compressors [C+)== in achieving an e-accurate optimum can be characterized as
(AC,(A, {(fe C.) == per-round cost ((st(())EE)) (A ((f, C))
(4)
3.2 A tight lower bound for per-round cost
The per-round communication cost incurred by {C.). in 44) will vary with different values. Typically, compressors that induce less information distortion, i.e., associated with a smaller w, incur higher per-round costs. To illustrate this, consider random-s sparsification compressors, whose per-round cost corresponds to the transmission of s entries, which depends on parameter w through d +w) (see Example in Appendix A). Specifically, if each entry of the input æ is numerically represented with bits, then the random-s sparsification incurs a per-round cost of rd/(1 + w) bits up logarithm factor.
The following proposition, motivated by the inspiring work (50. establishes a lower bound of TCC when using any compressor satisfying Assumption| 2
Proposition 1. Let x E Rd be the input to compressor C' and b be the number of bits needed to compress Suppose each entry of input is numerically represented with r hits, i.e., errors smaller than 2 are ignored. Then for any compressor C satisfying Assumption 2 the per-round communciation cost of ((x) is lower bounded by b Ω2 (d/ w)) where viewed as an absolute number in (-) (See the proof in Appendix B
Proposition presents lower bound on the per-round cost of an arbitrary compressor satisfying Assumption This lower bound is tight since the random-s compressor discussed above can achieve this lower bound up to a logarithm factor. Since d only relates to the problem instance itself and is often constant absolute number in practice, e.g., 32 or 64, both of which are independent of the choices of compressors and algorithm designs, they can be omitted from the lower bound order. As a result, the TCC in (4) can be lower bounded by
TCC. = 2((1+w) TT ())E)
(5)
Notably, when no compression is employed (i.c., w = 0), TCC, = ={(1) T.(A, ((f.. C.)) consistent with the convergence complexity.
Unbiased compressor alone cannot save total communication cost
With formulation 5). given the number of communication rounds Tr, the total communication cost can be readily characterized. A recent pioneer work (19 characterizes a tight lower bound for (A, {(Ji, G,)), when each C₁ satisfies Assumption 2
Lemma (199) Theorem 1, Informal). Relying on unbiased compressibility alone, i.e., {Cil Us without leveraging additional property of compressors such mutual independence, the fewest rounds of communication needed by algorithms with compressed communication to achieve an e-accurate solution distributed strongly-conver and generally-convex optimization problems are lower bounded by T. (2(1 + w) (μA/r)) and T. = 22(1 + w) LLA/c) respectively.
Substituting Lemma into our TCC lower bound in (5) we obtain TCC, = ((Veen(1/e) or Ω( LA/e) in the strongly-convex generally-conver case, respectively, by relying solely

---

unbiased compression. These results do not depend on the compression parameter indicating that the lower per-round cost fully compensated by the additional rounds of communication incurred by compressor errors. Notably, these lower bounds are of the same order optimal algorithms without compression such as Nesterov's accelerated gradient descent
44 leading to the conclusion:
Theorem 1.
When solving corvex optimizution problems following Assumption ! any algorithm A E A(C.Y, that relies solely on unbiased compression satisfying Assumption 2 cannot reduce the total comminication cost compared to using compression. The best achievable total communication cost with unbiased compression alone is of the same order as without compression.
Theorem presents negative finding that unbiased compression alone is insufficient to reduce the total communication cost, even with an optimal algorithmic design Meanwhile, also implies that to develop algorithms that provably reduce the total communication cost, one must leverage compressor properties beyond w-unbiasedness as defined in ( Fortunately, mutual independence one such property which we discuss in depth in later sections.
Independent unbiased compressor provably saves communication
5.1 An intuition on why independence can help
A series of works 40
have shown theoretical improvements in the total communication cost by imposing independence across compressors, i.e., {C.). E Uind The intuition behind the role of independence among worker compressors can be illustrated by simple example where workers intend to transmit the same vector æ to the server. Each worker i sends a compressed message (x) that adheres to Assumption 2 Consequently, the aggregated vector D==1 Ci(ar) is unbiased estimate of æ with variance
32 33
1]
E
Σ
-
a
C1(x) - x
1 n
Σ
m
(2) [E(CC()- x/} =
(6)
If the compressed vectors [C; are further assumed to be independent, i.e., {Ci) E unnd then the cancellation of cross error terms leads the following equation:
Σ Cl(x,) x
n Σ (1l|C(())
- x13 ||0|
(7)
We observe that the mutual independence among unbiased compressors leads to a decreased variance, which corresponds to the information distortion, of the aggregated message. Remarkably, this reduction is achieved by factor of n compared to the transmission of single compressor. Therefore, the independence among the compressors plays pivotal role in enhancing the accuracy of the aggregated vector, consequently reducing the number of required communication rounds.
On the contrary, in cases where independence is not assumed and no other properties of compressors can be leveraged, the use of Cauchy's 's inequality only allows us to bound variance (6) as follows:
E
Σ
C1(x)
[x] - x1|21 s w||2||2
(8)
It important to note that the upper bound w||=|| can only be attained when the compressors } are identical, indicating that this bound cannot be generally improved further. By comparing (7) and
we can observe that the variance the aggregated vector achieved through unbiased compression with independence can be times smaller than the variance achieved without independence.
5.2 Convergence lower bounds with independent unbiased compressors
While mutual independence boost the unbiased worker compressors, it remains unclear how much the total communication cost can be reduced al most by independent unbiased compression
'The theoretical results can vary from practical observations due to the particularities of real datasets with which compressed algorithms can enjoy faster convergence, compared to the minimax optimal rates (e.g., ours and (19) justified without resorting any additional condition.
7

---

and how to develop algorithms to achieve this optimal reduction. The following subsections aim to address these open questions.
Following the formulation in ( to establish the best achievable total communication cost using inde- pendent unbiased compression, shall study tight lower bounds on the number of communication rounds T. to achieve an e-accurate solution, which is characterized by the following theorem.
Theorem 2. For any 2 p 2 0. n 2 the following results hold. See the proof in Appendix
Strongly-convex: For any A O, there exists constant cu only depends on _ L/p. a set of local loss functions {fi] E F independent unbiased compressors {C;) E Uind such that the output & of any A E AIC.3.., starting from x. requires
TA (U,, C.))= =5 ((u+ (1
-8(((
Vk
In
vnl
rounds of communication to reach E[f(E)] ming f(x) & for any 0 < c CAHAA.
Goner:: For any > O, there exists a constant = (1), a set of local loss functions (fi)==1 E FE.o independent unbiased compressors {Ci] Unnd, such that the output it of any A E A(C.),., starting from x. requires at least
T.A,A(F ( 55
LA
LA
(1+
Vni
rounds of communication reach B[S(+)] min, (xx S for any 0 < cLA
Consistency with prior works. The lower bounds established in Theorem 2 are consistent with the best-known lower bounds in previous literature. When O, result reduces to the lower bound for distributed first-order algorithms established by Y. Nesterov in [3 When n = 1, our result reduces to the lower bound established in 19 for the single-node case.
Independence improves lower bounds. A recent work [9 establishes lower bounds for unbiased compression without the independence assumption, listed in the second row of Table Compared to these results, our lower bound in Theorem replaces w with w/ /Ti showing a reduction in order. This reduction highlights the role of independence in unbiased compression. To better illustrate the reduction, we take the grrongly-conver case as an example. The ratio of the number of communication rounds T. under unbiased compression with independence to the one without independence is:
w (1 + (1+w/VD)Vr (1+W)Vk
1 1+ 1+
VK =
mmnnn1 + W, VT, VK
(9)
Clearly, using independent unbiased compression can allow algorithms to converge faster, by up to factor of @(yminn (nn x}) (attained at w Z /min(n, in terms of the number of communication rounds, compared the best algorithms with unbiased compressors but without independence.
Total communication cost. Substituting Theorem 2 into the TCC formulation in (5). we can obtain the TCC of algorithms using independent unbiased compression. Comparing this with algorithms without compression, such as Nesterov's accelerated algorithm, and using the relations in (9), we can demonstrate that independent unbiased compression can reduce the total communication cost. Such reduction be up to ( ((/min(n, (n)]) by using compressors with 2 /min(n, kj., e.g.. random-s sparsification with s S d/ v k..
5.3 ADIANA: a unified optimal algorithm
By comparing existing algorithms using independent unbiased compression, such as DIANA, ADI- ANA, and CANITA, to our established lower bounds in Table D becomes clear that there is a noticeable gap between their convergence complexities and our established lower bounds. This gap could indicate that these algorithms are suboptimal, but it could also mean that our lower bounds are loose. As a result, our claim that using independent unbiased compression reduces the total commu- nication cost by up O /
min (2, F times is not well-grounded yet. In this section, we address this issue by revisiting ADIANA [2] (Algorithm) T and providing novel and refined convergence results in both strongly- and generally-conver cases.

---

Algorithm 1: ADIANA
Input:
Scalars k0 ) 1- B2 9, (7k T-1 k=D
k (nk 1 T-1
R P.
Initialize w² = x² yr = x = 11 = -M, 11 Sis n.
for k 0..... ,T do
On server:
Update x: x² 0 + 02 + (1 - 01 02) and broadcast to all workers;
On all workers in parallel:
Compress the increment of local gradient m. C; ((((a(((**)) h.) and send the server;
Compress the increment of local gradient of C((VSi(w*) h1.) and send to the server;
Update local shift h, = h + ac;;
On server:
Aggregate received compressed message 9 11t + 1 Ei=1 m Update shift h+1 = h² + a n Ex= c;; Apply gradient descent y = x nagh:
Update 2: 2 B2 + (1 - 3)x*
22 (y - x²);;
Th
Update w: wh+11 = Tt" with probability p.
ww with probability p:
Output: TT if f(w") S f(y") else =²²
In the strongly-convex case, we refine the analysis of [32] by: (i) adopting new parameter choices where the initial scalar 0g is delicately chosen instead of being fixed as 02 1/2 in (32, (ii) balancing different terms in the construction of the Lyapunov function. While we do not modify the algorithm design, our technical ingredients are necessary to obtain an improved convergence rate. In the generally-convex case, we provide the first convergence result for ADIANA, which is missing in literature to our knowledge. In both strongly- and generally- convex cases, our convergence results (nearly) match the lower bounds in Theorem 2 This verifies the tightness of our lower bounds for both the convergence complexity and the total communication cost. In particular, our results are:
Theorem For any L> p
A
0, n 2 and precision e >> 0, the following results hold. See
the proof in Appendix D
Strongly-convex: If > O, by setting parameters тr- = 17 = 11fg/(120w/ L). 01,x = 01 1/(3/m), = =p=1/( + w). 7h = (20 + nn), 3 = 20/ (201 + nu), and 02 =
1/(3/n+ 33/w), ADIANA requires
o ((u+ (0++1++
(1+
vx
In
LA
Vn
rounds of communication to reach [ff - min. f(x) S E.
Generally-convex: 1f 0, by setting parameters a 1/(1 + w), 8 1, p 02 w)) 01,x = =9/(k 27(1 w)), 7h m and
k ++1+ 27(1 w) ((1+ 27(1 ~) 200 + w) 2T
3n
1
mh min
ADIANA requires
o (a+wr)
LA + (1+
LA
rounds of communication to reach B[f(i)] - min, f(x) S.
Tightness of our lower bounds. Comparing the upper bounds in Theorem 3 with the lower bounds in Theorem 2, ADIANA attains the lower bound in the strongly-conver case up to a In(x) factor, the generally-convex case,
implying the tightness of our lower bound and ADIANA's optimality. the upper bound matches the lower bound's dominating term (1 + w/ vn) / /.A./ but mismatches the smaller term. This shows the tightness of our lower bound and ADIANA's optimality in the

---

Nadarry
Mosteray
28"4
10
2814
DIANA
SF31
GIANA
EPST
(110111 110
23"7
communication bits [xled)
communication bita (x2a6)
1.0
communication bita (=led)
4.0
7.0
Figure 2: Convergence results various distributed algorithms on synthetic least squares problem (left),
logistic regression problems with dataset a9a (middle) and w8a (right). The y-axis represents f(ā) f and the 7-axis indicates the total communicated hits sent by per worker.
regime <
LA
Ltw/yR
Our refined rates for ADIANA are state-of-the-
I+w
among existing algorithms using independent unbiased compression.
6 Experiments
In this section, we empirically compare ADIANA with DIANA B2 EF21 49
and CANITA B3
using unbiased compression, as well as Nesterov's 's accelerated algorithm 43 which an optimal algorithm when compression is employed. We conduct experiments on least-square problems (strongly-conven) with synthetic datasets as well as logistic regression problems (generally-convex) with real datasets. In all experiments, measure the total communicated bits sent by single worker, which is calculated through communication rounds to acheive an e-accurate solutions X per-round communicated bits. All curves averaged over 20 trials with the region of standard deviations depicted. Due to the space limit, we only provide results with random-s compressors here. More experimental results be found in Appendix F22
Least squares. Consider a distributed least-square problem (I) with f((x) -11 6,112. where A; E Ax and b, E RM are randomly generated. We set d 20, n - 400, and M = 25, and generate A,'s by randomly generating Gaussian matrix in R= then modify its condition number to 10a through the SVD decomposition, and finally distribute its rows to all A,. We use independent random-1 compressors for communication compression. The results are depicted in Fig. 2 (left) where we observe ADIANA beats all baselines in terms of the total communication cost. We do not compare with CANITA since it does have thcoretical guarantees for strongly-convex problems.
Logistic regression. Consider a distributed logistic regression problem with f((x) =
I EM In(1 exp(-bi,md pppp-b..m.T... ")). where (0a htmm)hgign Sm SMSM are datapoints in a9a and M
w8a datasets from LIBSVM [11]. We set n = 400 and choose independent random- (onomm|d//0)) compres- sors for algorithms with compressed communication. The results are as shown Fig. (middle and right). Again, we observe that ADIANA outperforms all baselines.
Influence of independence in unbiased compression. We also construct delicate quadratic problem to validate the role of independence in unbiased compression to save communication, see Fig. [ Experimental details are Appendix F.I We observe that ADIANA with independent random-s compressors saves more bits than Nesterov's 's accelerated algorithm while random-s compressors of shared randomness do not. Furthermore, more aggresive compression, i.c., a larger w, saves more communication costs in total. These observations are consistent with our theories implied in (9)
Conclusion
This paper clarifies that unbiased compression alone cannot save communication, but this goal can be achieved by further assuming mutual independence between compressors. We also demonstrate the saving can be up to O( / (n, x}). Future research can explore when and how much biased (
compressors can save communication in non-convex and stochastic scenarios.
8 Acknowledgment
This work is supported by NSFC Grant 12301392, 92370121, and 12288 101.
10

---

References
[1] A. Agarwal and L. Bottou. A lower bound for the optimization of finite sums. In International Conference on Machine Learning, 2015.
[2] S. A. Alghunaim and K. Yuan. A unified and refined convergence analysis for non-convex decentralized learning. arXiv preprint 10..0221 2021.
[3] D. Alistarh, D. Grubic, Li, R. Tomioka. and Vojnovic. QSGD: Communication--fice SGD via gradient quantization and encoding. In Advances Neural Information Processing Systems, 2017.
[4] D. Alistarh, Hoefler, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, 2018.
[5] Y. Arjovani, 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.
[6] Y. Arjevani and O. Shamir. Communication complexity of distributed convex learning and optimization. In Advances in Neural Information Processing Systems, 2015.
[7] E. Balkanski and Y. Singer. Parallelization does not accelcrate convex optimization: Adaptivity lower bounds for non-smooth convex minimization. ArXiv, abs/I N0011088800,,, 2018.
[8] J. Bernstein, Y.X. Wang, K. Azizzadenesheli, and A. Anandkumar: Signsgd: compressed optimisation for non-convex problems. In International Conference on Machine Learning, 2018.
[9] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(())71-112) 2020.
[10] Y. Carmon, J. C. Duchi, O. Hinder. and A. Sidford. Lower bounds for finding stationary points ii: first-order methods, Mathematical Programming, 185:315-355, 2021.
[11] C.-C. Chang and C.-J. Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1-27, 2011
[12] J. Chen and A. Sayed. Diffusion adaptation strategics for distributed optimization and lcarning over networks. IEEE Transactions on Signal Processing, 60(8):22894300 2012.
[13] T. Chen, G. Giannakis, T. Sun, and W. Yin. LAG: Lazily aggregated gradient for communicatio--eficcentt distributed learning. In Advances in Neural Information Processing Systems, pages 5050-5060 2018.
[14] Z. Cheng, X. Huang, and K. Yuan. Momentum benefits non-iid foderated learning simply and provably. arXiv preprint 2r36v:2306. 16504, 2023.
[15] J. Diakonikolas and C. Guzmán. Lower bounds for parallel and randomized convex optimization. In Conference on Learning Theory, 2019.
[16] P. Elias. Universal codeword sets and representations of the integers. IEEE transactions on information theory, 21(2):194-033, 1975.
[17] 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.
[18] V. Gandikota, D. Kane, R. K. Maity, and A. Mazumdar. vqsgd: Vector quantized stochastic gradient descent. In International Conference Artificial Intelligence and Statistics, pages 2197-2205. PMLR, 2021.
[19] Y. He, X. Huang, Y. Chen, W. Yin, and K. Yuan. Lower bounds and accelcrated algorithms in distributed stochastic optimization with communication compression. arxiv preprint arXiv:2305.07612 2023.
[20] S. Horvath, C.-Y. Ho, L. Horvath, A. N. Sahu, Canini, and P. Richtárik. Natural compression for distributed deep learning. ArXiv, 0tts//995.109900 2019.
[21] X. Huang, Y. Chen, W. Yin, and K. Yuan. Lower bounds and nearly optimal algorithms in distributed lcarning with communication compression. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[22] X. Huang. P. Li, and X. Li. Stochastic controlled averaging for federated learning with communication compression. arXiv preprint wrXiv:2308.08165 2023.

---

[23] 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 (NeurlPS), 2021.
[24] S. P. Karimireddy, Kale, M. Mohri, S. Reddi, S. Stich, and T. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, 2020.
[25] 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.
[26] A. Khaled, O. Sehbouh, N. Loizou, R. M. Gower, and P. Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint mxXiv2006.11573 2020.
[27] S. Khirirat, H. R. Feyzmahdavian, and M. Johansson. Distributed learning with compressed gradients. arXiv preprint 0rXiv:/806006577 2018.
[28] D. P. Kingma and J. Ba. Adam: method for stochastic optimization. CoRR, abs/ (11.1912..,.0 2015.
[29] A. Koloskova, T. Lin, and S. U. Stich. An improved analysis of gradient tracking for decentralized machine learning. In Advances in Neural Information Processing Systems, 2021.
[30] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pages 5381-5393 PMLR, 2020.
[31] D. Kovalev, E. Shulgin, P. Richtarik, A. V. Rogozin, and A. Gasnikov. Adom: Accelerated decentralized optimization method for time-varying networks. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 5784-5793, PMLR, 18-24 Jul 2021.
[32] 7. Li, Kovalev, X. Qian, and P. Richtárík. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002.11664, 2020.
[33] Z. Li and P. Richtárik. Canita: Faster rates for distributed convex optimization with communication
compression. Advances in Neural Information Processing Systems, 34:13770-1133 13781, 2021.
[34] X. Lian, C. Zhang, H. Zhang, C.-J. Hsich, W. Zhang, and J. Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, 2017.
[35] T. Lin, S. P. Karimireddy, S. U. Stich, and M. Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In International Conference Machine Learning, 2021.
[36] Y. Liu, W. Xu, G. Wu, Z. Tian, and Q. Ling, Communication-censooee admm for decentralized consensus optimization. IEEE Transactions on Signal Processing, 67(10):556-2277, 2019.
[37] P. Mayekar and Tyagi. Ratq: universal fixed bendth quantizer for stochastic optimization. In International Conference on Artificial Intelligence and Statistics, pages 1399-1408) PMLR, 2020.
[38] B. McMahan, Moore, D. Ramage, S. Hampson, and B. A. y Arcas Communication-effiicentt learning of deep networks from decentralized data. In Artificial Intelligence and Statistics, 2017.
[39] P. Micikevicius, S. Narang, J. Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, et al. Mixed precision training. In International Conference on Learn- ing Representations, 2018
[40] K. Mishchenko, E. A. Gorbunov, M. Takác, and P. Richtárik. Distributed learning with compressed gradient 2019.
differences. ArXiv, abs/1901
[41] K. Mishchenko, G. Malinovsky, Stich, and P. Richtárik. Proxskip: Yes! local gradient steps provably lead to communication acceleration! finally! In International Conference on Machine Learning, nng pages 1,770015769. PMLR, 2022.
[42] Y. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence o(1kk)). In Doklady an ussr, volume 29, 1983.
[43] Y. Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
12

---

[44] Y. E. Nesterov. A method of solving convex programming problem with convergence rate o(1/k?). In Doklady Akademii Nauk, volume 269, pages 543-547. Russian Academy of Sciences, 1983.
[45] F. Nogueira et al. Bayesian optimization: Open source constrained global optimization tool for python. 2014.
[46] C. Philippenko and A. Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. ArXiv, 2022.
[47] S. Pu and A. Nedié. Distribated stochastic gradient tracking methods. Mathematical Programming, 187:409-455 2021.
[48] X. Qian, P. Richtárik, and T. Zhang. Error compensated distributed sgd can be accelerated. Advances in Neural Information Processing Systems, 34:30401-30413, 2021.
[49] P. Richtárik, I. Sokolov, and Fatkhullin. Ef21: A new, simpler, thcorctically better, and practically faster error feedback. ArXiv, 0bbs/2006.052000 2021.
[50] M. H. Safaryan, F. Shulgin, and P. Richtárik. Uncertainty principle for communication compression in distributed and federated learning and the search for optimal compressor. Information and Inference: Journal of the IMA, 2021.
[51] K. Scaman, F. R. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization networks. In International Conference on Machine Learning, 2017.
[52] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu. 1-bit stochastic gradient descent and application to data-parallel distributed training of speech dans. In INTERSPEECH, 2014.
[53] B. Song, I. Tsaknakis, C.-Y. Yau, H.-T. Wai, and M. Hong. Distrihuted optimization for overparameterived problems: Achieving optimal dimension independent communication complexity. In Advances in Neural Information Processing Systems. volume 35, pages 6147-6160, 2022.
[54] S. U. Stich. Local sgd converges fast and communicates little. In International Conference on Learning Representations, 2019.
[55] S. U. Stich, J.-B. Cordonnier, and M. Jaggi. Sparsified sgd with memory. In Advances in Neural Information P Processing Systems, 2018.
[56] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu. df: Decentralized training over decentralized data. In International Conference on Machine Learning, pages 4848-4856, 2018
[57] J. Wangni, J. Wang, J. Liu, and T. Zhang. Gradient sparsification for communication-efian distributed optimization. In Advances in Neural Information Processing Systems, 2018
[58] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. H. Li. Tergrrdd Temary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, 2017.
[59] 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
[60] R. Xin, U. A. Khan, and S. Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 2020.
[61] K. Yuan, S. A. Alghunaim, and X. Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized sgd. Journal of Machine Learning Research, 24(280): 1-53, 2023.
[62] K. Yuan, S. A. Alghunaim, B. Ying, and A. H. Sayed. On the influence of bias-correction on distributed stochastic optimization. IEEE Transactions Signal Processing, 2020.
[63] 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 202/ IEEE/CVF International Conference on Computer Vision (ICCV), pages 3009-3019, 2021.
[64] 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 Neural Information Processing Systems (NeurlPS), 2022.
[65] M. D. Zeiler. Adadelta: An adaptive lcarning rate method. ArXiv, abs/1212.5701,, 2012.
13

---

A Random sparsification
We illustrate the random-s sparsification here. More examples of unbiased compressors can be found in literature [50].
Example 1 (RANDOM-S SPARSIFICATION; For any x E R2, the random-s sparsification is defined by C(x) : [ @ x) where & denotes the entry-wise product and & {0, 13d a uniformly random binary vector with s non-zero entries. This random-s sparsification operator C satisfies Assumption 2 with d/s 1. When each entry of the input x is represented with bits, random-s sparsification compressor takes rs bits to transmit & entries and log2 (.) bits to transmit the indices of transmitted
entries, resulting in a total rd
+ log2 (a) bits in each communication round, see 50 Table 1].
14
B Proof of Proposition
1
We first recall a result proved by 150
Lemma (150), Theorem 2). Let LerC: be any unbiased compressors satisfying 2 Lnn b be the total number of bits needed to encode the compressed vector (z) for any E R If each entry of the input x is represented with bits, it holds that max w 4 4-/////d 1.
I4w
Using Lemma 2 when w/ +w) < 4- i.e., < (4" 1)-1 < 1/3, we have (1 + w) (1) and
b 2 rd- 22 (1 + w)), where is regarded as constant in (2)(). When W/ (1 + w) 2 4 we
have
[n(4)(1+ = Sr ( d
b dlog, (1 + w - = dln(1 + / (n(4)) 2 d
[++
where we use the inequality In(1 + t) 2 t/(1 + 1) with / = w- 2 0.
C Proof of Theorem 2
Following
5 9
we denote the k-th coordinate of a vector x E RRd by [x]a for h: = 1,....dd d, and let
prog(r) be
0,
prog(z) = max <ksu [k: [x]] # 0}, otherwise.
Similarly, for set of multiple points X' = {21, .2,... }, we define prog(A)) == max prog(r). We call function zero-chain if it satisfies
prog V (x))) prog(a)) e Ted
which implies that starting from 2º 0, single gradient evaluation can only earn most one more non-zero coordinate for the model parameters.
Let us now illustrate the setup of distributed optimization with communication compression. For any t 2 1. we consider the t-th communication round, which begins with the server broadcasting a vector denoted as u' to all workers. We initialize u' as zº. Upon receiving the vector u' from the server, each worker performs necessary algorithmic operations, and the round concludes with each worker sending a compressed message back to the server.
We denote of as the vector that worker i aims to send in the 1-th communication round before compression, and of as the compressed vector that will be received by the server, i.c., of = (x()) While we require communication be synchronous among workers, we do not impose restrictions on the number of gradient queries made by each worker within a communication round. We use y to represent the set of vectors at which worker makes gradient queries the t-th communication round, after receiving u' but before sending of. Following the above description, now formally state the linear spanning property in the setting of centralized distributed optimization with communication compression.
Definition (IANNIGG ALGORITHMS), We say distributed algorithm is linear- spanning if. for any t 2 1, the following conditions hold:
14

---

1. The server can only send vector in the linear manifold spanned by all the past received messages, sent messages, i.e,, u² E span (fu")== U8& :1 :
2. Worker can only query at vectors in the linear manifold spanned by its past received messages, compressed messages, and gradient queries, i.e., y S span (fu")r=1 (VV())) VV (6))=)))
3. Worker i can only send a vector in the linear manifold spanned by its past re- ceived messages, compressed messages, and local gradient queries, ie., of span U y VT U (6pr=1).
4. After t communication rounds, the server only output model in the linear manifold spanned by all the past received messages, sent messages, i.e. It span ((u")r=1
1== U [6}
1 is n)==))
In essence, when starting from x. O, the above linear-spanning property requires that any expansion of non-zero coordinates in vectors held by worker i (e.g.. vf) are attributed to its past local gradient updates, local compression, or synchronization with the server. Meanwhile, also requires that any expansion of non-zero coordinate in vectors held, including the final algorithmic output, in the server due to the received compressed messages from workers.
Without loss of generality, we assume algorithms to start from x0d throughout the proofs. When {J.) further assumed to be zero-chain, following Definition can easily establish by induction that for any 2 1,
max prog(u") & max max prog(ú;) Srrst
(10)
1SrctiSis
max prog(u/) S max max gg
max prog(Of), prog()?))
max max prog (i.) + isrct Isisn
isret
Isign
prog(#*)
max max prog(
iSrst Isinn
Next, we outline the proofs for the lower bounds presented in Theorem For each case, we provide separate proofs for terms in the lower bound by constructing different hard-to-optimize examples, respectively. The construction of these proofs follows four steps:
Constructing set of zero-chain local functions {fi)
Constructing of independent unbiased compressors {C+) S u These compressors are delicately designed to impede algorithms from expanding the non-zero coordinates model parameters.
Establishing limitation on zero-res pero-respecting algorithms that utilize the predefined compressor with t rounds of compressed communication on each worker. This limitation is based on the non-zero coordinates of model parameters.
Translating the above limitation into the lower bound of the complexity measure defined in equation
While the overall proof structure is similar that of [19], our novel construction of functions and compressors enable us to derive lower bounds for independent compressors. These lower bounds clarify the unique properties and benefits of independent compressors.
We will use the following lemma in the analysis of the third step.
Lemma 3 (11),, Lemma 3). Given a constant
[0, and random variables [B'} such that
B' < Bt+ + 1 and PB < B² {Br) )==)
2 1 p for any t 2 it holds for t 2 1/p, with
probability at least - e that B < B + ept.
C.1 Strongly-conver case
Below, we present two examples, each of which corresponding to a lower bound LBm, for Te. We integrate the lower bounds together and use the inequality
T. max {LBm) Ω (LB, LB2)
15m52
15

---

to accomplish the lower bound for strongly-conver problems in Theorem
Example 1. In this example, we prove the lower bound @ + (1 + vR/n) In (nA/c)).
(Step 1.) We assume the variable x E & - {[x]] [a]g....,) Er= [x] < oo to be infinitely dimensional and square-summable for simplicity. It easy adapt the argument for finitely dimensional variables as long as the dimension is proportionally larger than Let M be
2 -1
1
2 -1
M
-1 2
-1
120x00
then it is easy to see 0 3 M 4T. Let (f:)==1 be as follows
/ | + - Σ [200[[1//r00 [x]
Hisisn-b 1,
f((x)
1 ||:||| + - [m Erzi
ifi=..
where À E [R} is to be specified. It is easy to see that Er [+]n++s+1) ) and [x:] + +Z220([=) [x) 21 are convex and 4-smooth. Consequently, all fis L- smooth and ju-strongly convex. More importantly, it is easy to verify that all fis defined above zero-chain functions and satisfy
prog(r) + 1, if prog(x) = mod n, otherwise.
prog( f(()))
(11)
S prog(z),
We further have f(z) E fi(z) |||=|| + 4-" T Mx 2A(211). For the functions defined above, we also establish that
Lemma 4. Let L/p 2 1, it holds for any that,
2prog(ar)
- min f(x)
1 1-2 1
1
2(x
| x0 1=1
2
n
Proof. The minimum x² of function f satisfies
4IE M + 11) x² -t which is equivalent 2n
to
2x + 2n
[x"] - [x112 X,
1
2x + 2n 2
[x" [ 1 +
[x=1] - (011 = 0, Vj 2.
(12)
K
Note that
+ n 1 V /2(2 + 2)
9
2(x
the only root of the equation q² 2x+2n forward to check x² ([x*), >q'), f2 unique solution. Therefore, we have that
that is smaller than 1. Then it straight
x-1
satisfies 12
By the strong convexity of f. xx is the
20
\2 22 2
||.
X2g21
92 1101 x²12
1 1-
+=prog(#)+1
Finally, using the strong convexity of ff leads to the conclusion.
Following the proof of Lemma 4 we have
| x² 1|2 = 2
2
1 q
j=1
16

---

Therefore, for any given A > 0, letting X = V((1-99 /2) results in 1|200 - A. Consequently, our construction ensures (fi) E FF...
(Step 2.) For the construction of w-unbiased compressors, we consider {C, to be independent random sparsification compressors. Building upon Example[T] we make a slight modification: during a round of communication on any worker, each coordinate is independetly chosen with a probability of (1 + w) to be transmitted, and if selected, its value is scaled by (1 + w) and then the scaled value is transmitted. Notably, the indices of chosen coordinates are not identical across all workers due to the independence of compressors. It can be easily verified that this construction ensures that {C:) C
(Step 3.) Since the algorithmic output i' calculated by the server lies in the linear manifold spanned by received messages, we can use (T0) to obtain the following expression:
prog(f") S max max max{prog(u)) prog( igrgt i
max max prog (7) 2 B
(13)
15 1SiS
We next bound 8 with 1 == by showing that {B' 100 satisfies Lemma
3 with p = (1 + w)
For any linear-spanning algorithm A, according to (II, the worker i can only attain one additional mod n. In other
non-zero coordinate through local gradient-based updates when prog()?)
words, upon receiving messages {u] from the server, we have
maxigrsa prog (T)) + B +1, 1, if prog()))) i mod n, maxigrs: prog(u) (T]) B
prog(u!)
otherwise.
Consequently, we have
max prog(u;) max B" + 1= B 11-1+1 +1.
Isrst
It then follows from the definition of the constructed C₁ in Step 2 that maxigign prog(e)) S maxigigo prog(uf), and therefore we have:
B
< max max prog(v)) S B²-1+++ +1. ggrgrigign
Next, we aim to prove that B < B + with probability of at least w/(1 + w). For any 2 1, let i {1....,nj n be such that Bt = mod Due to the property in equation (II), during the 1-th communication round, if prog
Bt-1, worker i can push the number of non-zero entries forward by 1, resulting in prog (v() B- worker j cannot achieve this even if prog()') = B²-1 due to equation
using local gradient updates. Note that any other
Therefore, to achieve 8² = B²-1 + 1, it is necessary for worker i to transmit a non-zero value at the (B'-1= + 1)-th entry to the server. Otherwise, we have 13 < Bt-1, However, since the compressor C associated with worker i has a probability w/(1 w) to zero out the (Bi-1+ + 1)-th entry in the t-th communication round, we have
PP (B' <B--1 (B* w/(1 + w).
In summary, we have shown that Ba S BB and P(B' - Bt (B 2 w/(1 + w).
By applying Lemma 3 we can conclude that for any t t> (1+ + w) -| with probability of at least
1 it holds that B² S et/(1 w) and hence prog(E') & et + due [3).
(Step 4.) Using Lemma 4 and that prog(**) < et/(1 + w) with probability at least - =1, we obtain
2et/(1+w)
[ff()') - min f(x) 2 (1 - 1---11p 1
2(x 1)
1-2 1 V
(14)
2
J
mdexp
(TVR/n+ 1)(1 + w) (-
4et
))
17

---

Therefore, to ensure E[f( - ming f(x) I e, relation 144 implies the lower bound T
(((1 [[(1+w)(1= / k/n) In(uA/e)).
be homogeneous and C; I to be loss-less compressor for all 1 i n. the problem reduces to single-node convex optimization. In this case, the lower bound of ((vR In (uA/e)) well-known in the literature, as shown in 44 43
Example 2. Considering
With the lower bounds achieved in Examples and 2, we have
T. = 22((1 + (1 + V//N) VEIn(uA/c))
5s (1 w wttp-/////w/w//t V (R)((A/A
=Q - + (n)
which is the result for the strongly-convex case in Theorem
C.2 -enerally-convex case
Below, present three examples, each of which corresponding lower bound LBm for Te. We integrate the three lower bounds together and use the incquality
T. 1Sm53 (LBm) = QLBB + LB2 + LB3)
accomplish the lower bound for the generally-conver case in Theorem 2
Example 1. In this example, prove the lower bound (?(( + w)
(Step 1.) assume variable x Rdd, where can sufficiently large and will be determined later. Let M denote
2 -1
-1 2 -1
M
: -1
:.
Rddd
-1
-1 2
it is easy to verify 0 = M N 4I. Similar to example 1 of the strongly-conver case, we consider
fi(x) E,>0 [1)++ - [x]nr+++1]
if disisn-l
[+]] + Er>i ([x)er - [=] -2Ap]1).
if = n.
where À R (0) to be specified. is easy to see that all f&s are L-smooth. We further have f(x) = - f((z) (x Mx - 2A(x))). The fr functions defined above are also zero-chain
functions satisfying
Following 48
is easy to verify that the optimum of satisfies
A (x 11-=+ Iskgd
L2 and ʃ(x*) min f(x) 4n(d + 1)
More generally, holds for any < S d that
A
min 2: prog(()
f(x)
(15)
4n + 1)²
Since ||00- - x²1 - JA
X Σd k==
22 x2d(2++1) 6(d+1)
< X'd letting À /3A/d, we have (fi)
(d+1)2
(Step 2.) Same as Step Example of the strongly-convex case, we consider ( to be independent random sparsification operators.
18

---

(Step 3.) Following the same argument as step 3 of example of the strongly convexx case, we have that for any 2 (1 +w) holds with probability least e thht prog( S et/ w).
(Step 4.) Thus, combining
15
wC have
ATL
d
e/(1
{( min (x) 2(1
e-
4n
d+1
1 1+ ct/(1++))
3LA
d
et/(1
= e
And
d+1
e+et/(++
Letting 1= w), we further have
3
(1++)) ( nt2
B[f( min f(x) Snet + +1 2et(1 + w)-
Therefore, to ensure [[f( ming f(z) S the above inequality implies the lower bound to be
T = (2(1 (n)))())))
Example 2. Considering fi to be homogeneous and C; to be a loss-less compressor for all < i S n. The problem reduces to the single-node convex optimization. The lower bound ( (L)/) is well-known in literature, see, e.g., 44 43
Example 3. In this example, we prove the lower bound Q(w In (LA/e)).
|||>=|1// + nX(1a, 2) where 1a E gd is the vector with all enries being 1 and À E R is to be determined. By definition, (fi) p-strongly-convex and L-smooth and the solution x² + 1.. Letting LVA/VT, we have
(Step 1.) We consider f1
fa-1 T||>=1//2 and
|| 1 - A. Thus, the construction ensures {fi] F
(Step 2.) Same as in Example 1, we consider {C: to be independent random sparsification operators.
(Step 3.) By the construction of [fi] we observe that the optimization process relies solely on transmitting the information of 1. from worker the server. Let E' denote the set of entries which the server has received a non-zero value from worker n in the first communication rounds. Note that for each entry, due the construction of {C,] the server has a probability of least (w (1 + w)) of not receiving a non-zero value at that entry from worker n. Consequently, ((E) ) is lower bounded by the sum of n independent Bernoulli(w* /(1 w)) random variables. Therefore, we have E [[[(E") [ 2 d's / +W)
(Step 4.) Given EE due to the linear-spanning property, we have if E spantej : E E²) where ej the j-th canonical vector. As a result, we have
[[[(=')] min fx)
fx)) min f(x) LA LAE(
LA
W
E
min 2 2Espan(e)JEEF)
(16)
d
2 (1 w)²
Therefore, to ensure E[f(t')] min, f(x) < e, (6) implies the lower bound T. = liw l(Wln(L))))
With the three lower bounds achieved in Examples 1, 2, and 3, we have
LA
LA
T. == 12
(1 + w)y
+ wIn(LA/E)
-0
LA
w/
LA
wl((LA/e)
ne
which is the result for the generally-convex case in Theorem
19

---

D Proof of Theorem 3
D.1 Strongly-convex case
We first present several important lemmas, followed by the definition of Lyapunov function with delicately chosen coefficients for each term. Finally, we prove Theorem by utilizing these lemmas. Throughout the convergence analysis, we use the following notations:
W =f(w²) fr, y f(y))))))))))))r)))))) f 2t 11 x²1
11 - V]ii g - 11 - \1(
1=1
[Vii(")) V/Aaa)I1 0 | n
Σ [VA((* - VS((=))1
n
We use Es E indicate the expectation with respect to the randomness the k-th iteration or all histortical randomness, respectively.
Lemma 5. 1f0 S B < 1, it holds for V k 2 0 that,
gh+1 2n (g x²' x + 372 (gt; w 2/)
3yx
01,k
82) (g 3 - =²t)
1
01,
+ 3 + (1 - B)||=* - x² 11? + 11.
(17)
Proof. Following the update rules in Algorithm T we have
z 32 + (1 9)x* - xx" +
Th (g - xzt)
=11 -113(2* xx") + (1 ()( x²)) =²² + 22l 912
+ (2 v .B² + (1 - B)x² x²).
(18)
Since x² = 01 -1,,22² + 0x + (1 - 11 0g) we have
Bz + (1- 3) x² =(x* - x²) + S02 (** - w + 3(1 - 01. 02) (2+ 1 - (19)
01,x
01,5
Plugging 19 into 18) using
11(
(1- (x* x1)11² B1 - 1=1 (1 B)1|=* =111
we obtain 17
Lemma 6. Under Assumption) 1 if parameters satisfy 01,k, 02 1 - 01, 02 E (0, 1), mhe E (0, 2T.
7h tmm and? 3 7pp
28
then we have for any iteration k 2 that
20,
2Th Eg 1 + s
27 273300 W
2T
01, 02) 3ih t + +2 +
3T gk 10
0
01,
01,k
3w.302
71.(1
01,5 02)
gh:
g/..
(20)
L
L0
Proof. By Assumption D and update rules in Algorithm
we have
f(1+11) <s(x²) + (Vf(x*) A+1
x²)) + 2
11
k+1 - x21
I.
=s(2²) - (v neg + n 112
=f(x²) no (V
) +
mh 11g/112.
(21)
2
20

---

By L-smoothness and p-strongly convexity, we have for Vu E R² that
f(u) 2 f(== + (Vf(2") u- x4, + 2 1 - x= 1²1
and that
1
fi(u) 2 f((x²) + +V
u- 2t)
[V((2)) V)((=t))1
2L
thus we obtain for Vu E R.d.
{(x (s(u)
(V f [x* -xx
max
H x
1lu
113
Vfi(u) v((e2))
(22)
2
2Ln
Applying Young's inequality to 21 and using 1/k S 1/L),, we reach
My k+) <s(x") + 7k gh
11
(1
|1
2
2
<f(x") + Uk gh
l
(23)
2
4
Adding 17 in Lemma 5 to B1.
2
+ 2 - B) x 23
+ 2
22
(where x²)+
22
11.x
(where w*) 2%x 21x (1-001.11 61.4 - 02)
22
(where u y and using the unbiasedness of g", we
obtain
2 Eg (M +1 1x(1
01,
<82 k + (1 3 -- -1-1))01100 =1*1
7k
Th Th7
20 1,k
Ex ExIlg*
?
01,
+ +
(1x(1-3)) -3) gh
N1.302 gh 31, -
-11
02)
30,
W + 2013B11 - 0 02) yi
10
L0
0 1
11,
-2 B)E&(>**+) Y) -
11
Ex
2
On top of that, by applying our choice of the parameters, it can be easily verified that 1 1 p7 0.
7
2
3
20,
0, 1
S 40,,a* which leads to (20).
Lemma (32), Lemma 3, 4, 5). Under Assumptions
and the iterates of Algorithm
satisfy
the following inequalities:
E| '1 = - P + pEP*),
(24)
Eigh1 S 2w Elght + 2w E
(25)
n
EH +1 < (1 2
1 + 2p
1+ 2p)
(LIG + EIG.
(26)
Now we define Lyapunov function k for k 2 1 as
Yok = - 27k- 18 yk zk 10m ([1 + w)
Vk 121.
(27)
0
01
where A 7h phi, verify that
-0.001., 02 p p+ v(p 01 -02) + 4p02). Furthermore, it is straightforward
27,
27,.3 02)
< A
p01.
p01,
Now we restate the convergence result in the strongly-convex case in Theorem 3 and prove using Lemma 6 7 and the Lyapunov function.
21

---

Theorem 4. If > O and parameters satisfy ?ソ = = (
-= 1/(1+ w), "h = n/ n/(29, + mH)), _ == =0, /28) + nh), and 02 = 1/33 3n 3n/w), w) then the number of communication rounds performed by ADIANA to find an e-accurate solution such that [=] - minz f(x) S e is at most
(1 (/) (TTT//))).
Proof. In the strongly-convex case, parameters {7R and (01, are constants, then so is dR-
Thus, we simply write y - Tk. 01 & 01, and x - d for all k 2 1. Considering
24
Sy 481
25
10m
26), we have
n81
27,302
27/(11
- 01 10-2
-02)
E.
+ +11 (1-p))) W
+ pd +p2)
) + 32
f1
81
1
10mpw(1 + w/B
(7/302
125
+
1 -
H1
gt.
4(1 + w)
Onn
10
2n01
7:3(1 01 02)
60rju7/3
g
(28)
L0
n01
By the definition of X, we have
2y302
2p02
+ +(1 (1-p)}= =x
1 1-p+
01
V(p 01 82) )2 + 4p02 + 01 + 02 p
2p02
=x
1 - p +
28
10,0,
v 0p 02 4p82 92+02pp
<X
1- p +
p
1
p0d
A (29)
p 02 022
[p+01 02) 01 02
and
2y 01 -1))
+ pd
2xB
1 - 01 - 02 + 2
(0, + 02 - ((-- 0, 02)² + 4p002)
01
01
2yB
2p01
1
01
p 01 0g
v (p- 01 02) + 4p02
p0,
27B
(30)
+ 01 + 02
0₁
From the choice of 17, it easy to verify that
y30
5yBmp
60mwyy3
0,
(31)
L0
2n01
nd01
and further noting - 01 - 02 2 82.
7/3(1 - 01 02)
60mw7
2 0.
(32)
L0
n01
Plugging
30
31 and
32
into
28
we obtain
E E4 s
min
p0
20, + np 4(1 + w) }) vi
mp
+ 01 + 02
p+ 0 +0g
20g +op
+ 4(1 + w)
ndl
7//4
AA 20
(33)
w + (1 + Jia vx)
250
22

---

where y0 = AM
y + 0 +
10po[+u)72 76. Note that since we use initialization y"
6.
Bi
2" wD 11. 11, indicates that
v1
S n. we have 2 3 - (LA)/2, 0 A. 7D S L2A, which
L
40 -
(Aw + dy + +
where Aw = X 2r
xy
2x
Az = 1.
A
20m +w)n88
These coefficients have the
0.p
01
01m
following inequalities:
Aw + Av 2 (n + p)
n02 + p)
n02 p)s
(220) + 11112
30wT.p(233
n02/ 1102/11000 120wk)3
15w T.p
2 16
2 Az:
135L 270
and
3 (Aw + Xx)
+ wn03k 40r + W)L
An-
32
1440T.
160
(201 + m2)
Consequently, the initial value of the Lyapunov function can bounded as
< 136L(Aw + A
which together with (33) further implies that
min Lin(B[f(u))
E[f(u f
T
(
1 1 1
1
<inn
Aw
Ax
250
w 1 +
w
vn
T
<272LA
1
250
w
+
1
w
Vx
Thus, O (ww+
(1+
(
vk
In
(A)
iterations are sufficient to guarantee an e-solution.
D.2 Generally-convex case
In this subsection, we restate the convergence result in the generally-convex case as in Theorem and prove it using Lemma 6 and the Lyapunov function defined (27).
Theorem 5. If 0 and parameters satisfy 1/(1 w), B 1, 02 1/(3(1 + w)), f1, = (/ + 27(1 + w)), 7 = /2x/(201,1) and
1: 1 27(1 +w) m min w1 27(1 + w)) 200w(1 + L 2I.
3n
then the number of communication rounds performed by ADIANA to find an e-accurate solution such
that [+) ming f(x) I is provided by O(11 + w/ vT) LLAC+
VLA/c)
Proof. Considering 20
24
5y 10
25
(1 n01,
26 and applying the choice of 02.
p and ar we have
Ex. (x(T
300
p)1b +11-p)Ab) nu + 221x8(1 - 01. - -02)
+1
+
pdv 1 + 1332
B
81
1
10mmw(1 + w)rk
1Tk.82
3wyx
100m
+
1 4(1+w)
H.
G
n01,
T.0
2n01,
9n0
3x13(1 - 01,K - 0z) 100m
Gty.
(34)
L0
9101,
23

---

Similar to the proof of Theorem 4 we can simplify (34) by validating
2ra,8002
+ (1 - -)) - (1
p ds S (1
-3
$1,4
1+01
21=0(1-011 (1.11--011---0 + +p>x S (1
p0l.
2
-
01,
B
01.4
11.
3
02.6
72,002
100
2 0,
L8,,E
2
768(1
01.0 (0..==02)
02)
100
2 0,
10
9,
and then obtain
81.
d Xx + (1 01.
27 gok + z²
Ex
< 1
3
01.
10m w)rk
1
Hhh
(35)
4(1 + w)
01,212
For Vk 2 1, we have 01,b S 01,x-1 and thus
1
01,4
2 =
1
3
The 2p0f,
(0L. + v 08 + 4p02))
3
1: + + w)
Thk
(01 + Vo9.A-11 + 4p02)
1: + 2+(2(
2p0f. k.
1: 27 + w)
)²
2 Tk Ak-1-
k 1 + 27(1 + w)
1: + 27(111111 + +w)
M---
Further noting
nu <
+ ++27(++a)* we obtain
(1
01,6
+ 27(1 : (1-
3
++ 27(1 + +w) (w))
27(1
-2 (11
k+ 27(1 27 w) )w) 2k-1
1
3
SA
(36)
Similarly,
11,6
27k
3
01,6
k+ 27(1 + w)
2
1/ 27k-1
1o + 27(1 + w)
1-1+ 27(1 w)
M 01.
(1- + 27(1 ww)
1
-2
1
1
27k-1 1
1o + 27(1 + w)
k + 27(1 + w)
01,k-1
27k
(37)
01
and
1
10mma(1 (1 + w)
4(1 + w)
n11.k
1: 27 + w)
2 M/
2 101j 1w(1 + ()))) 7 1,9
4(1 + w)
- + 27(11 + w)
7
n01,k-1
k+27(1-06 )
x+27
10m (1(1 + w) 133
1
n81,k-1
k+27(1+w)
107j- ( 1 + () 7k 1/3
(38)
-
24

---

Combining 335
36
and
38
we have for A4 2 that
Eg 1 +++
I Ar
(39)
By applying
39
with T
1,7
and (35) with k
we obtain
01.0
27o 0100 + 02)
1
270
E V
1
n
y 2
3
p01.0
3
1,0
(1
1
10mgw(1 w) H2a
4(1 + w)
01,0m
2
-0
1
3
1
3
wo
+ 0
H
S
1
A $ 3D.
L
L
40L2
40
Note that
2 2AT 12 + 2T
2 2T
1:02
W
+
2TT
yr
11
(W + +)²)),
-1
-1P
-1
0 1,7-1
thus
max
max [E[f( )1, (g
fi, E|
11-1
243A
9 + w) + 27(1 + +W)
200w(1 + W) 2L
(7 + 27(1 + w))²
max
T 27(1 +w)
3n
(1 w² /n)
(1 + L
=0
7
T
thus suffices to achieve an e-solution with O
(1+ v/ V
LA + (1+W)
LA
iterations.
E
Correction on CANITA 33
We observe that when w >> n, the original convergence rate of CANITA 33 bounds presented in our Theorem - equations (35) and (36) [3), or from the omission of certain conditions such as 2(n). To address this issue, we provide corrected proof and the corresponding convergence rate. Here we modify the choice of 3g in ((33), Theorem 2) 9(1 + b b++b++4 (2( + b)), while keeping all other choices consistent with the original proof, i.e., b = min(w, / (w1 w)3/n), Pt 1/(1+
contradicts the lower This discrepancy may stem from errors in the derivation of
ar = 1/(1+ Or = 3(1 (1 9(1 + +b w)))), 3 48w(1 + + (0)))(+++++++()(((0()))))))))))) and
for t = 0,
116++322) min
1)
(1+ (
11 L(043/2) }
for > 1.
By definition we have
T 1 9
1
IT
1+ (1+9(++b+))
70:
L(B (18+3/2) 33/2)
7+1+9(1+b+u
1
min
1+9(1+b+w)
L(3 3/2)
L(B + 3/2)
(T+91+bb=))
min
(40)
60L(1+ w)²
L(3 LB+3/22)
Plugging
40 and
33 344 into
133 1,33), we obtain
(1+b+w)
(1 () + 3/2)
E
E
(T 17+9(1 (T+ b+ w))²
(1+b+ +
(1+ b) 3/2)LA
=0
(41)
T3
T
25

---

Using b = min(w, vw(1 + w)2/n), we have
(1 (1+b+))==((++u)))))
and
w11 + w) + b+
(1 (L+b)(3+32)) =0
(1+b) +
n(1+b)
3/2
W²
=
1+
1/22
thus (41 can be simplified as
B (1+ w1+ //2 w² ///////
T
T
Consequently, for < LA/2 (i.e., precision that the initial point does not satisfy), the communica-
tion rounds to achieve precision e is given by O w VLA
(1+
3/4 77
VLA
Ve
+
v
Ve
F
Experimental details and additional results
This section provides more details of the experiments listed in Sec. validate our theories.
6 as well as few new experiments
F1
Experimental details
This section offers a comprehensive and detailed description of the experiments listed in Sec. 6 including problem formulation, data generation, cost calculation, and algorithm implementation.
Least squares. The local objective function of node defined as ft(x) = A11 b. 12 where A; E Mx b; E MRM We set d = 20, = 25, and the number nodes n = 400. To generate A, 's, first randomly generate Gaussian matrix G' RaMxd, we then apply the SVD decomposition G UVVT and replace the singular values in Σ by an arithmetic sequence starting from and ending at 100 to get and the resulted data matrix G = UEVT; we finally allocate the submatrix of G composed of the (( 1)M + 1) 1-tth row to the (i.)) row to be A, for all S n.
Logistic regression. The local objective function of node is defined as fe(x) == 37 E In(1 + exp(-bi, a..m.,). 0 in the node i's dataset, and bi.m stands for the corresponding label. In a9a dataset, node owns the (81(i - 1) 1)-th to the (816)-th datapoint with feature dimension = 123. In w8a dataset, node i owns the (120(1
where number of nodes 400, aimm stands for the feature of the m-th datapoint
+ 1) the (120i)- -th datapoint with feature dimension d 300.
Constructed problem. The local objective function of node is defined as
if 5 n/2, - || L ([=] + Eisrea/2-1(1t)r - [x]2r41)² + [o] 2[x]1),
[1(x)
| 4 Eisrspppp )2)
if > n/2,
where [z] denotes the I-th entry of vector x E Rd. We set μ = 1, = 10 d 20 and number of nodes 400.
Compressors. We apply various compressors to the algorithms with communication compression through our experiments. In the constructed quadratic problem, consider ADIANA algorithm with random-s compressors (see Example
Appendix [A] in six different settings, i.e., three choices of (s 1, 2, 2,4,,, 4), with two different (shared or independent) randomness settings. In the least squares and logistic regression problems, we apply the independent random- dd/20] compressor to ADIANA, CANITA and DIANA algorithm. In particular, we use the unscaled version of the independent random-Ld/ [d/20] compressor for EF21 to guarantee convergence, where the values of selected entries are transmitted directly to the server without being scaled by d/s times. In Appendix F.2 we further apply independent natural compression and random quantization with s above algorithms.
Vd in the
26

---

Nadaray
NAdMHOY DAANA
Mosteray GIANA
10"
1311
SF31
EFS1
(1/011
communication bits Ixled)
communication bita (x2a6)
communication bita (=led)
4.0
7.0
Figure 3: Convergence results various distributed algorithms on synthetic least squares problem (left), logistic regression problems with dataset a9a (middle) and w8a (right). The y-axis represents f(ă) f and the a-axis indicates the total communicated hits sent by per worker. All compressors used are independent natural compression.
Total communicated bits. For non-compression algorithms and algorithms with a fixed-length compressor, such as random-s and natural compression, the total communication bits can be calculated using the following formula: total communication bits number of iterations x communication rounds per iteration X communicated bits per round. Among the algorithms we compare, ADIANA and CANITA communicate twice per iteration, while the other algorithms communicate only once. The communicated bits per round for non-compression algorithms amount to 64d for d float64 entries. In the case of the random-s compressor, the communicated bits per communication are calculated as 64s + [log2 (o) Similarly, for natural compression, the communicated bits per round are fixed at 12d, with sign bit and 11 exponential bits allocated for each entry. In the case of adaptive-lengle random quantization, the communication cost is evaluated using Elias integer encoding [6]. This cost is then averaged among n nodes, providing a more representative estimate.
Algorithm implementation. We implement ADIANA, CANITA, DIANA, EF21 algorithms fol- lowing the formulation in Algorithm| accelerated algorithm with the following recursions:
B3). [26]. and 49
respectively. We implement Nesterov's
y² (1 0,) 0,)x* + 0,2
x. y² Mh ()(())
2k+1 x.th + 0h (xx x*)).
The value of a in ADIANA, CANITA and DIANA are all set to 1/(1 + w). and we set Yk 8 of ADIANA as in Theorem 3 Other parameters are all selected through running Bayesian Optimization (45) for the first 20% iterations with 5 initial points and 20 trials. The exact value of the selected parameters are listed Appendix F3 Each curve (except for Nesterov's accelerated algorithm which does not involve randomness) is averaged through 20 trials, with the range of standard deviation depicted.
Computational resource. All experiments are run on an NVIDIA A100 server. Each trial consumes up 10 minutes of running time.
F.2 Additional experiments
Addtional compressors. In addition to the experiments in Sec. we consider applying different compressors in the algorithms with communication compression. Fig. 3aand Fig. show results of using natural compression and random quantization, respectively. These results are consistent with the results in Sec. 6
CIFAR-10 10 dataset. We also consider binominal logistic regression with CIFAR-10 dataset, where labels of each datum are categorized by whether they equal to 3, i.e., the corresponding figures belong to the cat category. The full training set with 50000 images, are devided equally nodes. The compressor choices follow the same strategies as in Appendix F.I where dimension = 3072. Fig. 5 compares convergence results between Nesterov method and ADIANA with different compressors. It can be observed that ADIANA equipped with more aggressive compressors, i.e. those with bigger w, benefits more from the compression, which consistent with our theoretical results.
250
27

---

Nadarry
Mosterry
2011
10"
DIAVA
16-
BIANA
SF3!
EF31
10
V1n
communicatiin bits Ixled)
communication bita (x2a6)
communication [=led]
2.0
4,0
7.0
Figure 4: Convergence results various distributed algorithms synthetic least squares problem (left), logistic regression problems with dataset a9a (middle) and wêa (right). The y-axis represents f(ă) f and the 7-axis indicates the total communicated bits sent by per worker. All compressors used are independent random quantization.
Nesterov
ADIANA w. R.S.
10
ADIANA w. R.Q.
ADIANA w. N.C.
F(x f*
10-2
0.0
2.0
4.0
6.0
8.0
communication bits (x1e6)
Figure 5: Experimental results of logistic regression problem on the CIFAR-IO dataset. The objective function constructed by relabeling the classes into 2 classes, namely cat (corresponding the original class) and non-cat (corresponding the rest classes). ADIANA w. R R.Q. N.C. represents ADIANA algorithm with random- [d/20] compressor random quantization compressor with [vd] / natural compression compressor, where d 3072 the dimension of gradient vectors as well the number of features CIFAR-10 dataset. experiments are conducted under same setting as "Algorithm implementation" part in
Appendix F.1
F.3 Parameter values
In this subsection, we list all the parameter values that are selected by applying Bayesian Optimization. Table 2
3 5 6 list the parameters chosen in the least squares problem, logistic regression using a9a dataset, logistic regression using w8a dataset, the constructed problem, and logistic regression using CIFAR-10 dataset, respectively.
28

---

Table 2: Parameters for algorithms in the least squares problem. Notation R.S. stands for independent random sparsification, N.C. stands for independent natural compression, R.Q. stands for independent random quantization.
Algorithm
Parameters
Nesterov
7) = =30 x 10-2, 0 = 1.4 10-2
ADIANA R.S.
17 4.8 10-2. 8 = 10-2, 02 7.6 10 p= X 10-2.
ADIANA N.C.
3.9 10 =10x 1002.0 = -29 10-1. 10-1
ADIANA R.Q.
6.5 x 1052,0 = 114x10-2.0 = x 5 10-1
DIANA R.S.
7 =799 10-2.
DIANA N.C.
7 =7.4 10-2
DIANA R.Q.
7 = =7.6 X 10-2
EF21 R.S.
7 = 6.2 10
EF21 N.C.
7 6.8 10
EF21 R.Q.
7 = 7.4 10
Table 3: Parameters for algorithms in the logistic regression problem with a9a dataset. Notation stands for the index of iteration. Other notations are as in Table 2
Algorithm
Parameters
Nesterov
1) = 9.4 10-1, 0 1.7 10-1
ADIANA R.S.
= 2.1,1,66 01 = k+5.2x 102, 02 = 2.1
1.3x
x 10-1 221 x 10 -== 10-1--=177
ADIANA N.C.
= 2.1, 01
02 = 8.0 x 10 10-3 pp 10-1 1.0
k+4.33
ADIANA R.Q.
2.2, 01 = k+1.33
1.3
02 = 1.5 x 10-1, 10- 8 8.5xx.... 10-1
CANITA R.S.
1) = min 1+2.1x102
1.4), 0
2+233110 p 7 10-1
10
2.1x10"
CANITA N.C.
1 1.2,
1.2x 10 p 5.2 10
CANITA R.Q.
1 2.0,
k43.0 P- 7.2 10
30
DIANA N.C.
2.6.
DIANA R.S.
7 = 9.4 x 10-1
DIANA R.Q.
7 4.7 10-1
EF21 R.S.
= 1.3.
EF21 N.C.
7 1.6.
EF21 R.Q.
= 2.7.
29

---

Table 4: Parameters for algorithms in logistic regression with w8a dataset. Notations are as in Table
Algorithm
Parameters
Nesterov
1= 1.5 x 10
0 9.4 10-1
ADIANA R.S.
- 1-mm 1 10
.15). 01 K44.8x107 02 - 2.4 x -0 10-1
8.8
1.2x10
ADIANA N.C.
17 1.5 x 1000000000 01 k+1.1x101 02 -,76.7 10 x 10-1
2.5
ADIANA R.Q.
17 = 1.5 x 10', 01 k+7.4.
02- = 4.2 x 10 9 10
1.9
CANITA R.S.
1) min { k+2.0x10*
.7773. 0= 1.1x10
p p= 4.3 10-1
2.2x10
1+2.3x
CANTTA N.C.
min ++1.1x10'
1.1 x 10 0 ++TAx100 . p= 4.9 10
5.4
2.7
CANITA R.Q.
1) min 1+x
1.5x x 100),00 1++22X10 p 4.6 10
7.3
DIANA R.S.
= 1.5 10
DIANAN.C.
7 1.6 x 10a
DIANA R.Q.
7 = 1.5 X 10º
EF21 R.S.
7 2.0 104
EF21 N.C.
7 = 1.5 x 10a
EF21 R.Q.
7 = 1.5 10
Table 5: Parameters for algorithms in the constructed problem. Notation i.d.rand-s denotes independent random-s compressor, s.d.rand-s denotes random-s compressor with shared randomness.
Algorithm
Parameters
Nesterov
1/ 1.4 10 0 = 1.2 10-1
ADIANA i.d.rand-1
1) 1.5 x 10-1, 01 1.8 x 10-1, 02 = 1.3 X =0 1.5 10-1
ADIANA rand22
1) = 1.5 x 10-4 01 = 1.5 10-4, 00-1.00 02 = 5.0 10-2pp=1.9 10-1
ADIANA i.d-rand-4
1) 1.3 x 10-4 0, =9.2 10-2. 02 5.0 10 10
ADIANA s.d.rand-1
" 1.4 x 10-6.0 0, = =20 100x10",00, = 1.6 10-1.p-2.77 10
ADIANA s.d.rand-2
" = 79966 10 0, = x 100 = 4.3 x 10 -p= x 10
ADIANA s.d.rand-4
" 1.6 10
6.0 x 10 82 = 2.1 10 . 1.6 10
Table 6: Parameters for algorithms in logistic regression with CIFAR-10 10 dataset. Notations are as in Table
Algorithm
Parameters
Nesterov
7) 1.1 x 10
0 1.5 10-1
ADIANA R.S.
== 1.4 x 10-1 01
12
02 09:090 =9.0 x 10-2, p0= 4.3 x 10-1
K+3.3x10
ADIANA N.C.
7 1.4x 10-1 1,,
1.0110-
02 = 7.0 10-1.p= 8.5 10-1
k47.0
ADIANA R.Q.
17 1.2 10. 0 k+58
02 8.0 10-1 6.0 x 10-1
30


Reviews:
[{"review_id": "eydTwj9mLC", "reviewer": "Reviewer_gfiB", "summary": "The paper investigated the overall communication costs for federated learning algorithms. A lower bound on the per-round communication cost is presented, then an analysis of an existing algorithm, ADIANA, is provided to obtain an improved upper bound.", "questions": "There are possible places of improvement in terms of clarity. For example:\n\n1. Generally, it would be better if any concept is defined before it is formally used. For example, in the current manuscript, the definition of “linear spanning” is lost in the texts.  \n\n2. Similarly, the assumption of fixed communication load per round could be introduced before the definition of $T_{\\epsilon}$ in Sec. 2.4, otherwise, the meaning of minimization in its definition is not clear. \n \n3. For strongly convex results, it might be cleaner to replace $L/\\mu$ with $\\kappa$. \n\n4. The notation of $U^{int}_{\\omega}$ (or $U_\\omega$) can be removed (or moved to appendices) if not used.", "limitations": "The limitation is appropriately discussed in Section 7.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The general ideas for the settings and the results are clearly presented. Besides, the presented bounds are clean compared to related works in this field.", "weaknesses": "There is an absence of several crucial details, or perhaps typos, which makes it difficult to concretely understand the results. For example, one central concept required in this work is the unbiased compressor, which based on the current manuscript, applies to all real input values. However, if we require it to output a discrete variable with a bounded number of bins, such a compressor may not exist as it is not clear how the unbiased condition could hold for all $x\\in\\mathbb{R}$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. All questions have been clarified as best as we can. We are glad to address any further comments or questions.\n\n**1. There is an absence of several crucial details, or perhaps typos, which makes it difficult to concretely understand the results.**\n\nThe example about unbiased compressors is replied in the next point. We apologize if there are more typos or absence of details that affect the readability. We hope that the reviewer can point them out directly if possible, so that we can give specific responses.\n\n**2. Concept on unbiased compressor.**\n\nThe concept of unbiased compressor defined in Assumption 2 is standard in literature. It is consistent with existing concepts on unbiased compressor, such as Eq. (2) in reference [40] on EF21, Definition 2 in reference [26] on CANITA, Definition 1 in reference [25] on ADIANA, Lemma 2 in reference [49] on ECQ-SGD, Assumption 3 in reference [R1] on compressed push-pull, Assumption 4 in reference [13] on NEOLITHIC, Definition 4 and Remark 1 in reference [R2] on DIANA, Lemma 3.1 in reference [3] on QSGD.\n\nMany examples fall into the family of compressor, see Examples 1 and 2 in references [25, 26].\n\n[R1] Z. Song et. al., Compressed Gradient Tracking for Decentralized Optimization Over General Directed Networks, IEEE TSP 2022.\n\n[R2] Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. *arXiv preprint arXiv:1904.05115,* 2019.\n\n**3. It would be better if any concept is defined before it is formally used. The definition of “linear spanning” is lost in the texts.**\n\nWe agree. We temporarily put some definitions in the Appendix because of the page limit. For example, the formal definition of “linear spanning” is stated in **Appendix D**. We will move the definition of \"linear spanning\" in Definition 2 in Appendix D to subsection 2.3 prior to the definition of algorithm class in Definition 1.\n\n**4. The assumption of fixed communication load per round could be introduced before the definition of $T_\\epsilon$ in Sec. 2.4, otherwise, the meaning of minimization in its definition is not clear.**\n\nThe convergence complexity $T_\\epsilon$ is defined as the minimal number of communication rounds needed for guaranteeing an algorithm to find an $\\epsilon$-accurate optimum. The notion is customary in literature of communication compression (see, e.g., [20, 25, 32, 25, 26]) and is not explicitly related to the per-round communication load. We chose to state $T_\\epsilon$ first as it is widely used and self-explanatory. \nThe definitions of per-round communication workload and total communication costs are less investigated in literature. Therefore, we chose to write an entire section to motivate and argue for them. \nAs suggested by the reviewer, the comparison in terms of $T_\\epsilon$ is more meaningful for algorithms with the same per-round communication cost.\nWe thank reviewer gfiB for pointing out the potential misleadingness. We will introduce the matter of the fixed per-round communication cost before $T_\\epsilon$  when preparing the camera-ready draft.\n\nSpecifically, we will move the following assumption in Line 198~199: *Let each worker equip with a non-adaptive compressor with the same fixed per-round communication cost, i.e., the compressor outputs compressed vectors of the same length (size)* to an additional remark as follows directly after Remark 1 in subsection 2.4.\n\n**Remark 2.** Though the definition of $T_\\epsilon$ can be independent of the per-round communication cost, which is specified through the degree of compression $\\omega$ (i.e., choice of compressor $C_i$'s), we further assume here that these $C_i$'s equipped by each worker are **non-adaptive compressors with the same fixed per-round communication cost**, i.e., the compressor outputs compressed vectors of the same length (size). \n\n**5. For strongly convex results, it might be cleaner to replace $L/\\mu$ with $\\kappa$.**\n\nWe agree. Thanks for advice.\n\n**6. The notation of $U_\\omega^{ind}$ (or$U_\\omega$) can be removed (or moved to appendices) if not used.**\n\nThese notations are convenient for us to describe our theoretical results (e.g., in line 177, 228, 259, 263) and highlight the difference between ours and [13]. \n\n\nWe thank the reviewer again for his careful and valuable comments. We hope these response can clarify the reviewer's questions. We are looking forward to the follow-up discussion, and more than happy to address any further comments or questions.\n\n"}, {"review_id": "A7VXmW0bVS", "reviewer": "Reviewer_oD7w", "summary": "The paper explores the conditions of unbiased compression to reduce the communication cost in distributed optimization. Specifically, the paper first presents a theoretical formalization of the total communication cost (TCC) in distributed optimization. With this formulation, the paper proves that unbiased compressor alone cannot necessarily save TCC. Then the paper proves lower bounds on the convergence complexity and shows that independent unbiased compressor provably saves TCC. The paper also improves ADIANA and provides the upper bound of the TCC that can be reduced. Experiments are also provided to support the theoretical findings.", "questions": "N/A", "limitations": "N/A", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality:\n\nThe paper focuses on how to save TCC, which is a more practical concern in distribution optimization. Though the paper relies on the findings (independence on unbiased compressors) of previous works, it provides new findings (on the upper bound of the TTC that can be reduced) and applicable modifications of existing methods to obtain an match the bound. Overall the paper seems novel to me. \n\nQuality:\n\nThe claims in the paper are well supported by theoretical analysis.\n\nClarity:\n\nThe paper is well organized and easy to read. The authors give good introduction and clearly list the questions (Q1, Q2) they need to answer. They also provide detailed intuition on why independent unbiased compressor saves communications.\n", "weaknesses": "Overall the paper looks good to me.  One concern is that the current dataset is relatively small. It would be better if the author can provide experiments on a larger real dataset to better prove the effectiveness of the theoretical findings.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and valuable suggestions. The datasets used in our current manuscript follow the experimental settings in prior works (e.g. [25, 26]) in the literature. According to the reviewer's suggestion, we conducted additional experiments with a larger dataset, CIFAR-10. The new experimental results are shown in Fig. 1 in the pdf attached to our “global response” to all reviewers.\n\nWe are looking forward to the follow-up discussion with the reviewer, and more than happy to address any further comments or questions."}, {"review_id": "JvmxqFVWrI", "reviewer": "Reviewer_tEWM", "summary": "Several communication compression strategies have been proposed in the last few years to improve distributed optimization. The authors consider the tradeoffs between lowering the communication costs per round vs the number of communication rounds and understand how they affect total communication costs. They theoretically formulate this and prove that under some assumptions, unbiased compression might not save total communication. However,  if the compressors used by all workers are further assumed independent, they prove that total communication cost can be decreased. They also prove lower bounds on certain classes of algorithms by refining the analysis for ADIANA.", "questions": "It would be better if some experiments from the appendix were moved to main body.", "limitations": "NA", "rating": 7, "confidence": 1, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The results are provably improved. The presentation is clear and easy to follow. ", "weaknesses": "The lower bounds are proved only for certain classes of algorithms. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments. All questions have been clarified below. \n\n**1. The lower bounds are proved only for certain classes of algorithms.**\n\nWe agree that our lower bounds only apply to the class of certain algorithms described in Section 2.3. However, these settings are broad enough to cover most first-order algorithms in literature, e.g., [38, 25, 20, 61] , as well as all algorithms listed in Table 1. Therefore, our established lower bounds remain valuable and sufficient to address questions Q1 and Q2 raised in the introduction.\n\n**2. It would be better if some experiments from the appendix were moved to main body.**\n\nWe temporarily put these experiments into Appendix because of the page limit. We will reorganize them once we have more space allowed. Specifically, we will move Figure 4 and 5 to Section 6 next to Figure 2 and modify the description in Line 339~340 to:\n \n*We set $n=400$ and separately choose independent random-$\\lfloor d/20\\rfloor$ compressors (Figure 2), independent natural compression (Figure 4) and independent random quantization compressors (Figure 5) as the compressors used in the compression algorithms.*\n\nWe thank the reviewer again for his careful and valuable comments. We hope the above response can clarify the reviewer's questions. We are looking forward to the follow-up discussion, and more than happy to address any further comments or questions."}, {"review_id": "DsikcCH5gX", "reviewer": "Reviewer_u1Ro", "summary": "The paper analyzes the communication cost of unbiased compression algorithms for distributed optimization and proves that unbiased compression alone cannot reduce communication cost since whatever is saved via compression is lost due to an increase in the number of communication rounds needed for convergence. The authors then show that if in addition to being unbiased if the compressors are also independent then the lower bound on the number of communication rounds is reduced by a factor of $\\Theta(\\sqrt(\\min(n, \\kappa)))$ where $n$ is the number of nodes and $\\kappa$ is the condition number of the function being minimized. They then improve the convergence analysis of ADIANA, an existing algorithm for communication compresssion in distributed optimization, and show that the lower bounds can be matched upto a log factor. Simulations on distributed least squares and distributed logistic regression corroborate their analysis and validate their claims.", "questions": "1. To address the first point under weaknesses above, I would recommend moving the content of Appendix A which provides intuition on why independence helps to the main pape. Algorithm 1 can be moved to the Appendix to make space, since it appears to be just a reproduction of the ADIANA algorithm from [25]. \n\n2. Can you also provide an example of a compression scheme where the compressors are unbiased but not mutually independent and provide some intution for its sub-optimality or show it through any of the experiments in Section 6?\n\n3. Were any changes made to the ADIANA algorithm at all in your analysis or experiments or was the algorithm the same as that in [25] everywhere?", "limitations": "The authors have identified the major limitation of the analysis being limited to convex functions only and have marked that as an issue to be addressed in future work which is fine with me. I have identified a couple of more minor limitations under Weaknesses above and look forward to the authors' responses to those.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors identify an important gap in the existing literature on communication compression where emphasis is primarily laid on the unbiasedness of compressors, without also considering the effect of independence. They systematically build and explain their analysis providing theoretical proofs for all their claims. The theoretical analysis coupled with the clear explanation can make this an important and impactful addition to the literature.\n\n2. Considering the total communication cost (per-round cost x number of rounds) makes the analysis more realistic and complete than previous works which just show savings in either per-round cost or on the number of rounds. Moreover, by proposing a general lower bound for all distributed optimization algorithms with unbiased and independent communication compression this work clarifies the target communication cost for all such communication compression algorithms which can make them easier to evaluate and analyze theoretically.", "weaknesses": "1. The writing is a bit heavy on notation and the analysis may be hard to follow for readers unfamiliar with the literature. Especially since their is not clear example or intuition provided in the main paper to indicate why independence may help.\n\n2. It is a bit unclear why ADIANA is chosen for analysis. The transition from deriving a general lower bound to analyzing a specific algorithm feels a bit abrupt. If possible, it would be good to provide some intuition for the kind of properties that would make a communication compression algorithm likely to be close to the lower bound thereby justifying the choice of ADIANA for analysis. This is a minor point however, as I understand that such an intuition may not be available at this time so it is okay if that is the case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive feedback and valuable comments. Below are our answers to the concerns you proposed.\n\n**1. I would recommend moving the content of Appendix A which provides intuition on why independence helps to the main pape. Algorithm 1 can be moved to the Appendix to make space, since it appears to be just a reproduction of the ADIANA algorithm from [25].**\n\nThanks for the great suggestions! We put the argument of intuition in Appendix mainly because of the page limit. We will re-organize the paper as the reviewer suggested in the revision. \n\n**2. Can you also provide an example of a compression scheme where the compressors are unbiased but not mutually independent and provide some intuition for its sub-optimality or show it through any of the experiments in Section 6?**\n\n- A proper example can be the scaled random sparsification where each worker randomly chooses $s$ entries out of the total $d$ entries, scales their values to guarantee unbiasedness, and transimts them to the server, see Appendix B in our paper for reference. When each worker samples $s$ entries randomly and independently, the compressors are mutually indepedent and unbiased. When all workers **share the same random seed** to sample $s$ entries, the compressors are unbiased but correlated with each other. \n\n- According to the above example, it is evident that if compressors are independent, then the indices of transmitted entries by all workers are likely to be uniformly diverse, and the server apparently can observe more entries in this case and thus the compression-incurred information distortion is milder. In contrast, when using the same random seed, all compressors will sample entries with the same indices, and the server will observe much fewer entries in this scenario. This would explain the intuition behind the sub-optimality of mutually dependent unbiased compressors.\n\n- The sub-optimality of the dependent case can be viewed through Line 342~347 in Section 6, where we can see clearly through Figure 1 that ADIANA with random-$s$ compressors with shared randomness behave much worse than those with identical independent compressors.\n\n- Unbiased compressors with the same seed are still widely used in practice due to its compatibility with All-Reduce operation, a highly effective protocol of distributed gradient aggregation used by default in PyTorch and TensorFlow, see Point 3 in the \"global response\" for more details. For example, unbiased compressors with the same seed are used in references [R1] and [R2] listed below. \n\n[R1] T. Vogels et. al., PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization, arXiv:1905.13727\n\n[R2] C. Xie et. al., CSER: Communication-efficient SGD with Error Reset, arXiv:2007.13221.\n\n**3. Were any changes made to the ADIANA algorithm at all in your analysis or experiments or was the algorithm the same as that in [25] everywhere?**\n\nAt the level of algorithmic design, the only difference in ours is to remove the proximal mapping as we consider the smooth case. However, **the improvement of analysis is significant**. We adopt effective choices of parameters (such as $\\theta$, $\\alpha$, $\\beta$) to obtain an improved rate and thus attain the optimality in the strongly convex case. Furthermore, the analysis in the generally convex case is brand new and no convergence result of ADIANA exists in the generally convex case, to our best knowledge.\n\n**4. Justfying the choice of ADIANA to achieve lower bound** \n\nWe choose to improve upon ADIANA mainly because **its previous convergence rate (in the strongly convex case) is the closest to our lower bound among all existing algorithms**. Another intuition is that DIANA-type algorithms is known to **benefit from independence of compressors** in the sense that it provably outperforms the best achievable rate proved by [13] when using non-independent compressors. While we believe there can be other algorithms with similar performance, we simply choose to improve upon ADIANA to verify the tightness of our lower bounds, which is important in addressing the *how much* question we concern.\n\nWe thank the reviewer again for his careful and valuable comments. We hope these response can clarify the reviewer's questions. We are looking forward to the follow-up discussion with the reviewer, and more than happy to address any further comments or questions.\n\n"}, {"review_id": "9GFl19gfJh", "reviewer": "Reviewer_MRty", "summary": "This paper investigates the communication saving of unbiased compression on distributed optimization. The main contributions are: \n\ni) a communication lower bound of distributed optimization algorithms with (not necessarily independent) unbiased compression;\n\nii) a communication lower bound of distributed optimization algorithms with (independent) unbiased compression;\n\niii) refined analysis of ADIANA to show tightness of these bounds;\n\niv) discussions on the importance of independence to the communication saving.", "questions": "i) Section 1 claims that quantization and sparsification are modeled as unbiased compressors in some papers. But they can be biased too. Please clarify.\n\nii) The error cancellation explanation of independence to unbiased compression makes sense. But, if $x_i$ at different nodes are quite different, do we still need independence to achieve the communication saving?\n\niii) Table I considers both convex and strongly convex cases. Are there any difficulties in analyzing the non-convex case?\n\niv) Some bounds in Table 1 are summations of two terms, for example, $\\ln(1/\\epsilon)$ and $\\epsilon^{-1/2}$, $\\epsilon^{-1/3}$ and $\\epsilon^{-1/2}$, etc. Is it possible to reduce to one term?\n\nv) Which compressors satisfy Assumption 2 (unbiased compressor) and Assumption 3 (independent compressor)? Please comment below the assumptions.\n\nvi) The communication saving is discussed via comparing the lower bounds. However, in some datasets some algorithms might perform much better than the lower bounds. In this case, the comparisons would yield different conclusions. Please comment on this.", "limitations": "N/A.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "i) Overall, this paper is well written and easy to follow.\n\nii) The investigated problem is important to distributed optimization, and the results are convincing.", "weaknesses": "i) Section 1 claims that quantization and sparsification are modeled as unbiased compressors in some papers. But they can be biased too. Please clarify.\n\nii) The error cancellation explanation of independence to unbiased compression makes sense. But, if $x_i$ at different nodes are quite different, do we still need independence to achieve the communication saving?\n\niii) Table I considers both convex and strongly convex cases. Are there any difficulties in analyzing the non-convex case?\n\niv) Some bounds in Table 1 are summations of two terms, for example, $\\ln(1/\\epsilon)$ and $\\epsilon^{-1/2}$, $\\epsilon^{-1/3}$ and $\\epsilon^{-1/2}$, etc. Is it possible to reduce to one term?\n\nv) Which compressors satisfy Assumption 2 (unbiased compressor) and Assumption 3 (independent compressor)? Please comment below the assumptions.\n\nvi) The communication saving is discussed via comparing the lower bounds. However, in some datasets some algorithms might perform much better than the lower bounds. In this case, the comparisons would yield different conclusions. Please comment on this.\n\nvii) I give a score of 6 at this stage, and would like to change it after the rebuttal period.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. All questions have been clarified as best as we can. We are glad to address any further comments or questions.\n\n**1. Section 1 claims that quantization and sparsification are modeled as unbiased compressors in some papers. But they can be biased too.**\n\nThanks for pointing it out. In Section 1 (Line 34~36) we wrote: *In literature [3, 20, 15], these compression techniques are often modeled as a random operator $C$, which satisfies the properties of unbiasedness $\\mathbb{E}[C(x)] = x$ and $\\omega$-bounded variance $\\mathbb{E}[\\\\|C(x) − x\\\\|^2] \\leq \\omega\\\\|x\\\\|^2$.* We did not mean that all these compressors are all modeled as unbiased ones, and we'll address the existence of biased compressors in later revisions to prevent misleading. \n\nSpecifically, we will add the following comments directly after Line 37:\n\n*Besides, part of the compressors can also be modeled as biased estimators with $\\mathbb{E}[\\\\|C(x)-x\\\\|^2]\\leq(1-\\delta)\\\\|x\\\\|^2$ where $\\delta\\in(0,1]$ [13,39,40].*\n\n**2. If $x_i$ at different nodes are quite different, whether we still need independence to achieve the communication saving.**\n\nAs long as the independence exists, the aggregation of compressed messages always benefits from the error cancellation because all the cross terms in the expansion of $\\mathbb{E}[\\\\|\\frac{1}{n}\\sum_{i=1}^n C_i(x_i)-x_i\\\\|^2]$ are zero in expectation so that $\\mathbb{E}[\\\\|\\frac{1}{n}\\sum_{i=1}^n C_i(x_i)-x_i\\\\|^2]=\\frac{\\omega}{n^2}\\sum_{i=1}^n\\\\|x_i\\\\|^2$. As for non-independent compressors, in the worst case, there remains the possibility that the compression error of the aggregated messages approaches to the upper bound obtained from Cauchy's inequality, i.e., $\\mathbb{E}[\\\\|\\frac{1}{n}\\sum_{i=1}^n C_i(x_i)-x_i\\\\|^2]\\approx \\frac{\\omega}{n}\\sum_{i=1}^n\\\\|x_i\\\\|^2$, which can be greater than the one of independent compressors, up to $n$ times.\n\n**3. Difficulties in analyzing the non-convex case.**\n\nUnfortunately, in the non-convex scenario, we have not found any algorithm that belongs to the considered family and is capable to achieve provable savings in total communication costs. One close work is  (MARINA: Faster Non-Convex Distributed Learning with Compression, ICML 2021) which exhibits an extraordinary convergence rate but requires transmitting full (i.e., uncompressed) gradients occasionally, making it jumping out of the algorithm class we consider. As for ADIANA, it is specially designed for the convex case, and it may not even converge in the non-convex case.\n\n**4. Whether summations like $\\ln(1/\\epsilon)$ and $\\epsilon^{-1/2}$, $\\epsilon^{-1/3}$ and $\\epsilon^{-1/2}$, etc. are possible to be reduced to one term?**\n\nEach term can be the dominating one depending on the magnitude of precision $\\epsilon$ and the setup-related constants including $L$ and $\\Delta$. For example, in the lower bound of the generally-convex case: \n\\begin{equation}\n\\tilde{\\Omega}\\left(\\omega\\ln\\left(\\frac{1}{\\epsilon}\\right)+\\left(1+\\frac{\\omega}{\\sqrt{n}}\\right)\\frac{\\sqrt{L\\Delta}}{\\sqrt{\\epsilon}}\\right),\n\\end{equation}\nThe $\\ln(1/\\epsilon)$ term can dominate when the parameters satisfy $\\omega=\\sqrt{n}\\gg L\\Delta/\\epsilon$, and the $1/\\sqrt{\\epsilon}$ term can dominate in a high-precision regime where $\\frac{\\ln(1/\\epsilon)}{1/\\sqrt{\\epsilon}}$ is sufficiently small.\n\nIn the upper bound of CANITA in the generally-convex case:\n\\begin{equation}\n\\mathcal{O}\\left(\\omega\\frac{\\sqrt[3]{L\\Delta}}{\\sqrt[3]{\\epsilon}}+\\left(1+\\frac{\\omega^{3/4}}{n^{1/4}}+\\frac{\\omega}{\\sqrt{n}}\\right)\\frac{\\sqrt{L\\Delta}}{\\sqrt{\\epsilon}}\\right),\n\\end{equation}\nThe $1/\\sqrt[3]{\\epsilon}$ term can dominate when $\\omega=n^{1/3}\\gg \\left(\\frac{L\\Delta}{\\epsilon}\\right)^{1/6}$, and the $1/\\sqrt{\\epsilon}$ term can dominate in a high-precision regime where $\\epsilon$ is sufficiently small.\n\nTherefore, these summations should not be reduced into one term without further conditions.\n\n**5. Which compressors satisfy Assumption 2 (unbiased compressor) and Assumption 3 (independent compressor)?**\n\nWe'll comment the following examples under Assumption 3:\n\n*In fact, lots of compressors in the literature satisfy Assumption 2, see, e.g., standard dithering [3, Lemma 3.1], natural compression [14, Thm 3], natural dithering [14, Thm 8], ternary quantization [48]. As long as the worker-associate compressors have irrelavant sources of randomness (e.g., using different seeds for randomness), they further satisfy Assumption 3.*\n\nWe also refer the reviewer to Point 3 in the \"global response\" where we show examples that independent compressors can be transformed into dependent compressors when using the same random seed.\n\n**6. The communication saving is discussed via comparing the lower bounds. However, in some datasets some algorithms might perform much better than the lower bounds. In this case, the comparisons would yield different conclusions.**\n\nAs described, our lower bounds consider the worst case of the objective function that satisfy the $L$-smoothness and convexity. Thus our lower bounds only provide insights and laid down the standard for comparing the theoretical convergence rate relying merely on the $L$-smoothness and convexity. \n\nWe'll comment this under Theorem 1:\n\n*It is worth noting that the theoretical results can vary from practical observations due to the particularities of certain datasets, where these datasets may exhibit additional structures with which algorithms can enjoy faster convergence, compared to the one theoretically justified without using any additional condition. However, such studies are beyond the scope of our work and we will leave it for future work.*\n\n\n\nWe thank the reviewer again for his careful and valuable comments. We hope these response can clarify the reviewer's questions. We are looking forward to the follow-up discussion with the reviewer, and more than happy to address any further comments or questions."}, {"review_id": "ECDiqTitTC", "reviewer": "Reviewer_JbF9", "summary": "The authors study the extent to which unbiased compression can reduce the total communication cost of optimizing smooth convex functions. Additionally, they refine the analysis of ADIANA ([25]) to show that the bounds are near-optimal.", "questions": "Can you please clarify the differences in the asymptotics with [13]? (Also, what is specified in the table seems to be different than in their paper, where they have an additional additive term.)\n\n", "limitations": "Seems fine", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Quantifying how much unbiased compression helps is an interesting topic. While I believe that nearly anyone (that uses compression) works with unbiased compressors in the distributed case, it is interesting to learn by how much it helps compared with biased compressors.\n\n", "weaknesses": "It is not very surprising to me what without independence, unbiasedness cannot help in general. \nFurther, I do not recall seeing works that do not use independence to get the error-cancellation, *other than works that use correlated compression to drive the error lower than that of i.i.d. compressors* (e.g.,  Correlated quantization for distributed mean estimation and optimization, ICML 2022). \n\nAlso, the writing is hard to follow and seems to be contradictory in places.\nFor example, You write, \"Compared to lower bounds when using unbiased compression without independence [13], our lower bounds demonstrate significant improvements when n and κ are large\". \nHowever, the upper and lower bounds of [13] seem to match in your Table 1, while your lower bound seems *weaker* than that of [13].\n \nIn general, there cannot be two matching sets of upper and lower bounds.\n\nSome of the claims also seem inflated; I don't view $O(\\omega \\epsilon^{-O(1)})$ as being near optimal for a lower bound of $\\Omega(\\omega\\log\\epsilon^{-1})$ -- the dependency on $\\epsilon$ is exponentially worse.\n\nThe improvement in the analysis of ADIANA is only applicable to some parameter range as it shaves an additive factor.\n\n(As a side note, it took me a minute to understand that by **ADIANA (Ours)** you don't actually mean that it's your *algorithm*, but just a refined analysis.)\n\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed comments. We have clarified all questions as clearly as possible, and will be glad to address any further comments or questions.\n\n**1. Not surprising that unbiasedness cannot help without independence**\n\nWe respectfully disagree with this opinion. Lots of literature believes that compression always saves the total communication costs, regardless of the relationship between compressors. While the reviewer's intuition is correct, it is essential to provide rigorous proofs, as what we contribute in the paper, to translate intuition into facts. It would be inappropriate to make definitive claims without in-depth mathematical clarifications.\n\n**2. Rare works do not use independence**\n\nPlease see Point 3 in the \"global response\".\n\n**3. Contradictions in lower bounds**\n\nPlease note that our lower bound/optimal complexity is proved in a different setup from [13]. Specifically, [13] does not assume the independence of compressors. In contrast, we impose the independence of compressors and only consider the lower bound and convergence of algorithms under this additional assumption. Due to the difference in setups, our results are different from and do not contradict with [13].\n\nFurthermore, as supported with our upper bound part, our lower bounds are nearly tight (at least in the strongly convex case) and thus represent the optimal complexities. Given the fact that ours and [13] are both optimal complexities in their respective setups (with or without independence), our complexities improves [13] by factors depending on $n$, $\\kappa$, and $\\omega$ (also see the response in point 7). This reveals the nontrivial advantage brought by independence of compressors. We hope this clarifies the reviewer's confusion.\n\n**4. Inflated claims**\n\nTo resolve reviewer's concern, we will replace the statement of \"nearly optimal\" with \"nearly optimal in the strongly convex case\" throughout the paper to avoid inflated claims.\n\nThe polynomial gap exists in the generally convex (GC) case whereas our result in the strongly convex (SC) case is polynomially tight. However, it is worth noting that even with such gap, our result is still the **state-of-the-art** in the GC case.  The existence of this tiny gap does not affect the major conclusion in our paper: independent unbiased compression saves communication costs up to $\\sqrt{\\min\\\\{n,\\kappa\\\\}}$ times while unbiased compression alone cannot. The established result in the GC case still outperforms the complexity in [13] with advantage at most $\\sqrt{\\min\\\\{n,\\kappa\\\\}}$ times when $\\epsilon\\lesssim (\\frac{1+\\omega/\\sqrt{n}}{1+\\omega})^6$ such that the $\\epsilon^{-1/3}$ term is dominated. \n\n**5. ADIANA improvement**\n\nOur improvement over existing ADIANA analysis is significant.\n\n- First, the additive term $\\omega^{3/4}/n^{1/4}\\sqrt{\\kappa}$ shaved by us is not trivial and can **dominate** in certain regimes. When $\\min\\\\{n,\\kappa^2/n\\\\}\\gtrsim \\omega\\gtrsim n^{1/3}$, the term $\\omega^{3/4}/n^{1/4}\\sqrt{\\kappa}$ dominates $\\sqrt{\\kappa}$, $\\omega\\sqrt{\\kappa} /\\sqrt{n}$, and $\\omega$, and thus the rate of ADAINA in [25] becomes $\\omega^{3/4}/n^{1/4}\\sqrt{\\kappa}\\ln(1/\\epsilon)$. Compared to our complexity in this case, the ratio is \n$$\\frac{\\mathrm{ADIANA}[25]}{ \\mathrm{ADIANA [Thm3]}} \\asymp \\frac{ \\omega^{3/4}/n^{1/4}\\sqrt{\\kappa} }{ \\\\omega+(1+\\\\omega/\\sqrt{n} )\\sqrt{\\kappa} }\\asymp \\min\\left\\\\{\\frac{\\sqrt{\\kappa}}{(n\\omega)^{1/4}}, \\frac{\\omega^{3/4}}{n^{1/4}},\\frac{n^{1/4}}{\\omega^{1/4}}\\right\\\\}\\gtrsim 1.$$\nHere $\\lesssim$, $\\gtrsim$, and $\\asymp$ denote (in)equalities that hold up to a numeric constant.\nNote that the ratio can be as large as $\\min\\\\{\\kappa^{3/8}/n^{1/4} ,n^{1/8}\\\\}$ if compressors are with $\\omega\\asymp \\min\\\\{\\sqrt{n}, \\sqrt{\\kappa}\\\\}$. Therefore, when $\\kappa \\gtrsim n$ and $\\omega\\asymp \\sqrt{n}$, our improved rate is faster than the original one by $n^{1/8}$ which is significant as $n$, the number of workers, can be large.\n\n- Second, shaving the additive term directly leads ADIANA to tightly matches with the lower bound in the SC case under independent unbiased compression. This milestone has not been attained or even explored in literature, to our knowledge. \n\n- Third, we establish the first convergence of ADIANA in the GC case, while exsiting ADIANA does not. In addition, our convergence rate outperforms all existing literature. \n\n**6. ADIANA (Ours)**\n\nWill rephrase as ADIANA (Thm3).\n\n**7. Asymptotic differences with [13]**\n\nFirst, [13] studies stochastic optimization where gradients are noisy with $\\sigma^2$-bounded variances (see [13, Assumption 3]). Our work instead considers deterministic distributed optimization where gradients are noiseless, corresponding to the case of $\\sigma =0$. The results of [13] can apply to noiseless gradients by setting $\\sigma^2$-dependent terms to zero. This is the reason why we removed the $\\sigma$-dependent terms in our table.\n\nWe are not sure what the word \"asymptotic\" mean by the reviewer. We conjecture the reviewer indicates the simplified rates of [13] when the additional $\\sigma$-dependent terms removed. In this case, the main difference of ours and [13] lies in the independence of compressors. In [13], compressors are not assumed to be independent and those complexities also apply to non-iid compressors. As we compared in Sec 5 in details, our rate is smaller than theirs justified by the factor\n$$\\frac{(1+\\omega)\\sqrt{\\kappa}}{\\omega+(1+\\omega/\\sqrt{n})\\sqrt{\\kappa}}=\\frac{1}{1+\\omega}+\\frac{\\omega}{1+\\omega}\\left(\\frac{1}{\\sqrt{n}}+\\frac{1}{\\sqrt{\\kappa}}\\right)\\asymp\\frac{1}{\\min\\\\{1+\\omega,\\sqrt{n},\\sqrt{\\kappa}\\\\}}.$$\nWhen adopting compressors with $\\omega \\gtrsim\\min\\\\{\\sqrt{n},\\sqrt{\\kappa}\\\\}$, our rate is $\\min\\\\{\\sqrt{n},\\sqrt{\\kappa}\\\\}$ times faster. The improvement mainly comes from exploiting the independence across compressors while [13], though more generally applicable to correlated compressors, inevitably sacrifices convergence.\n\n"}, {"review_id": "rSzYdrYcRr", "reviewer": "Reviewer_yR98", "summary": "The authors consider the distributed convex optimization problem in the centralized setting. In this setting, the authors provide the new lower bounds on the total communication cost under the assumption that nodes send unbiased independent compressed vectors to a master. They also provide improved analysis of the current state-of-the-art ADIANA method in the general convex and strongly convex regimes.", "questions": "-", "limitations": "-", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provides two important things to the distributed optimization community:\n1. While the upper bounds obtained by the ADIANA and CANITA methods are well known, finally, the authors provide lower bounds in the described setting.\n2. The improved analysis of ADIANA is very surprising. I checked the proof. I'm not 100% sure, but the improved analysis seems to be correct. I believe that it is an interesting contribution on its own.\nAll in all, I think that this paper deserves to be published in NeurIPS.", "weaknesses": "However, I would like to point out some very important weakness that I want the authors to fix.\n\nThe authors compare the total communication cost of compressed methods with the accelerated (Nesterov's) method. They claim that it is possible to improve the complexity by $\\min [n, \\kappa].$ I agree with this fact but only under the assumption that **the local smoothness constants are equal to the global smoothness constant.** The author ignore the fact (or I missed it in the text, then sorry me for that) that the local smoothness constants can be $n$ times larger than the global one. The authors define the local $L$--smoothness constant as \n$$f_i(y) \\leq f_i(x) + <\\nabla f_i(x), y - x> + \\frac{L}{2} ||x - y||^2 \\quad \\forall i$$ While the non-compressed methods define it as \n$$f(y) \\leq f(x) + <\\nabla f(x), y - x> + \\frac{L}{2} ||x - y||^2.$$ The $L$--constant of $f_i$  can be $n$ times larger than $L$--constant of $f$! I want to ask the authors to clarify it clearly in the paper. Ideally, in the abstract and in the contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and the valuable question. \n\nAs the reviewer accurately points out, the convergence analysis presented in our paper is contingent upon the condition on local smoothness constants. Under the difference of local and global smoothness, it remains uncertain whether our assertion regarding the potential communication cost reduction by independent unbiased compressors, on the order of $\\Theta(\\sqrt{\\min\\\\{n,\\kappa\\\\}})$, remains valid.\n\nDespite our earnest efforts, we have been unable to clarify this open question within the confines of the demanding rebuttal deadline. Consequently, to address the reviewer's valid concern, we will make revisions in our abstract and contribution sections and explicitly clarify that our claims hold under the assumption that the local smoothness and the global smoothness constants are constrained by a common upper bound $L$.  For example, we will revise statements in Line 18-19 in the abstract as \"Our results reveal that using independent unbiased compression can reduce the total communication cost by a factor of up to $\\Theta(\\sqrt{\\min\\\\{n,\\kappa\\\\}})$ under the assumption that all local smoothness constants are constrained by a common upper bound $L$\". \n\nAdditionally, we will also revise statements in Line 100-101 in the introduction as \"independent unbiased compression can decrease total communication costs by up to $\\Theta(\\sqrt{\\min\\\\{n,\\kappa\\\\}})$ when all local smoothness constants  are constrained by a common upper bound $L$.\"\n\nOn the other hand, we hope the reviewer can understand that **it is not uncommon to make the assumption that all local functions share a common upper bound of smoothness  in literature on distributed optimization**, which can significantly simplify the convergence analysis. For example, most algorithms listed in Table 1 in our paper such as CGD [20], ACGD [25], DIANA [32],  ADIANA [25], CANITA [26], and NEOLITHIC [13] assumes $L$-smoothness across all local functions. \n\nWe hope this response can resolve the reviewer's concerns. We are looking forward to the follow-up discussion with the reviewer, and more than happy to address any further comments or questions.\n\n\n"}]

Author rebuttal:
We thank all the reviewers for their careful review and valuable feedback. We have addressed each question raised by the reviewers in the separate rebuttals below and are glad to address any further concerns. As several matters have been brought up by multiple reviewers, we present a global response to these concerns below.

**1. Paper organization**

We thank all the reviewers for suggestions on reorganizing some parts of our manuscript, and adding comments or examples for further details. However, the page limit imposes unavoidable sacrifice of the content that we eager to present in the main text. As a result, we have to present details to important concepts and theorems, and refer the rest (e.g., typical examples, standard concepts, customary definitions) to our **Appendix in the Supplementary Material**. We will reorganize our main text by carefully following the advice provided by reviewers (e.g., make modifications as stated in the separate rebuttals) once we have more space allowed when preparing the camera-ready draft.

**2. Concerns related to the lower bounds.**

We find that some concerns of the reviewers are on the understanding of lower bounds. To precisely understand our results, we remark that the lower bound complexity should always be interpreted in the sense of **the limit of best-performing algorithms in convergence (or communication costs) when facing the worst-case instances under pre-specified assumptions of objectives and compressors**. In other words, we aim to investigate the theoretically best-achievable performance under the pre-specified assumptions of objectives and compressors. As a result, the conclusion naturally binds to the setup regularized by pre-specified assumptions.
Once the setup is modified (e.g., the compressors or objective functions are assumed to further enjoy certain properties), the according **worst-case** instance and the best achievable performance also vary. 

Consequently, when new assumptions are introduced, some algorithms can surpass the present lower bounds, which does not contradict with our established results since they are with different setups. On the other hand, the communication saving based on the lower bounds is concerned about the worst cases under **the exact settings in our paper**, and any additional assumption on the problem will change the setting and hence may affect our conclusions. 

**3. Concern on the use of correlated compressors. Rare works do not use independence.**

We respectfully disagree with the opinion that "rare works do not use independence". Non-IID unbiased compressors can offer practical advantages over IID compressors in many scenarios. Specifically, non-IID random sparsification compressors are more compatible with **All-Reduce** operation, which is a highly effective protocol of distributed gradient aggregation used by default in PyTorch and TensorFlow. However, IID sparsification compressors output compressed gradients with indices of non-zero entries poorly aligned across workers, hindering the efficacy of all-reduce, as illustrated in Fig. 2 in the pdf attached to this "global response". In fact, as noted in [R1, page 7], **gradient compression provides limited benefits if it is not compatible with all-reduce**. To enable unbiased compression to work with all-reduce, compressors across workers must share the same random seed, making them non-IID, as shown in Algorithm 4 of the well-known PowerSGD paper [R2]. In addition, the CSER algorithm also use a shared random seed across compressors [R3, Page 5].

[R1] S. Agarwal et. al., *On the Utility of Gradient Compression in Distributed Training Systems*, arXiv:2103.00543 

[R2] T. Vogels et. al,, *PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization*, arXiv:1905.13727

[R3] C. Xie et. al., *CSER: Communication-efficient SGD with Error Reset*, arXiv:2007.13221.

**4. More figures**

We provide two additional figures related to our rebuttal in the attached pdf.

**Figure 1.** In Fig.1, we display the results of an additional experiment, where we compare ADIANA with three different compressors and non-compression Nesterov's accelerated algorithm using a more practical dataset, CIFAR-10.

**Figure 2.** In Fig.2, we display the intuition why random sparsification compressors with shared randomness are more compatible with All-Reduce compared with those with independent randomness.

We thank all the reviewers again for the valuable comments. We are looking forward to the follow-up discussion, and more than happy to address any further comments or questions.

Meta-review: The reviewers agree on the good contribution of the paper in the area of federated learning. Here are some suggestions for the authors to incorporate: 1) This paper is less about total communication, but rather about the estimation error ($\omega$) of stochastic gradients - and as such, compression issues are completely decoupled, beyond trivially showing that compression lead to some estimation error. This should be made clear; 2) Related to the first issue, the authors seem completely oblivious to compression or communication literature in general, and finally, 3) Even in federated learning, there are *unbiased* compressors and error analysis that this paper does not mention, eg.  Mayekar and Tyagi (AISTATS 2020), Gandikota et al. (AISTATS 2021), and should be included in discussion.
Decision: Accept (poster)