Adaptive Compression for Communication-Efficient Distributed Training
Authors: Maksim Makarenko
Elnur Gasanov
Abdurakhmon Sadiev
Rustem Islamov
Peter Richtárik
Venue: Accepted by TMLR ()

Abstract: We propose Adaptive Compressed Gradient Descent (AdaCGD) -- a novel optimization algorithm for communication-efficient training of supervised machine learning models with adaptive compression level. Our approach is inspired by the recently proposed three point compressor (3PC) framework of Richtarik et al. (2022) , which includes error feedback (EF21), lazily aggregated gradient (LAG), and their combination as special cases, and offers the current state-of-the-art rates for these methods under weak assumptions. While the above mechanisms offer a fixed compression level or adapt between two extreme compression levels, we propose a much finer adaptation. In particular, we allow users to choose between selected contractive compression mechanisms, such as Top-$K$ sparsification with a user-defined selection of sparsification levels $K$, or quantization with a user-defined selection of quantization levels, or their combination. AdaCGD chooses the appropriate compressor and compression level adaptively during the optimization process. Besides i) proposing a theoretically-grounded multi-adaptive communication compression mechanism, we further ii) extend the 3PC framework to bidirectional compression, i.e., allow the server to compress as well, and iii) provide sharp convergence bounds in the strongly convex, convex, and nonconvex settings. The convex regime results are new even for several key special cases of our general mechanism, including 3PC and EF21. In all regimes, our rates are superior compared to all existing adaptive compression methods.

Published in Transactions on Machine Learning Research (07/2023)
Adaptive Compression for Communication--ffiienn Distributed Training
Maksim Makarenko
maksim.mdkarenkoe kaust.
King Abdullah University of Science and Technology
Elnur Gasanov
einurgaasanov@ kaust. edu. sa
King Abdullah University of Science and Technology
Rustem Islamov
rustem.islamov @ ip-paris.
Institut Polytechnique de Paris
Abdurakhmon Sadiev
abdurakhmon sadiev kaust.edu..
King Abdullah University of Science and Technology
Peter Richtárik
peter.richtarik koust. edu. sa
King Abdullah University of Science and Technology
Reviewed on OpenReview: https///////aeeeeeeeeee/ee////ee
Abstract
We propose Adaptive Compressed Gradient Descent (AdaCGD) - a novel optimization algorithm for communication ifnfunication-efficientt effiicient training of supervised machine learning models with adaptive compression level. Our approach inspired by the recently proposed three point compressor (3PC) framework feedback (EF21), lazily aggregated gradient (LAG),
Richtárik et al. (2022), which includes and their combination special cases, and offers the current state-of-the-art rates for these methods under weak assumptions. While the above mechanisms offer fixed compression level or adapt between two extreme compression levels, we propose much finer adaptation. In particular, we allow users to choose between selected contractive compression mechanisms, such as Top-K sparsification with user-defined selection of sparsification levels K, or quantization with a user-defined selection of quantization levels, or their combination. AdaCGD chooses the appropriate compressor and compression level adaptively during the optimization process. Besides i) proposing theoretically- grounded multi-adaptiv communication compression mechanism, framework to bidirectional compression, i.e., allow the server to compress as well, and iii) provide sharp convergence bounds in the strongly convex, convex, and nonconvex settings. The convex regime results are new even for several key special cases of our general mechanism, including 3PC and EF21. In regimes, our rates are superior compared all existing adaptive compression methods.
further ii) extend the 3PC
1 Introduction
Training machine learning models is computationally expensive and time-consuming. In recent years, researchers have tended use increasing datasets, often distributed over several devices, throughout the training process in order improve the effective generalization ability of contemporary machine learning frameworks Bareooorrs/Vawaaiii Vaswani et al. 2019). By the word "device" or "node," we refer any gadget that can store data, compute loss values and gradients (or stochastic gradients). and communicate with other different devices. For example, this distributed setting appears in federated learning (FL) (Konečný et al.] 2016 McMahan et al.) 2017 Lin et al. 2018). FL is machine learning setting where a substantial number of strongly heterogencous clients attempt to cooperatively train a model using the varied data stored on these devices without violating clients' information
et al.)) In this setting, distributed methods are very Efficient(Goyal al. 2017 You et al. 2019), and therefore, federated frameworks have attracted tremendous attention in recent years.

---

Published in Transactions on Machine Learning Research (07/2023)
Algorithm DCGD method with master compression
1: Input: starting point x." Rd; g. Rd for i 1, n (known by nodes), g0 1/ 7 -i= of (known by
master); learning rate 7 > 0, worker compressor M master compressor MM
for t 0,1.2, T- --1 - do
Server broadcasts g' to all workers
4: for all devices i .....,
n. in parallel do
5:
x++11 = x² 7g'
g, = M, w. (V (V(((**)))
6:
7:
Communicate 9 ++
to the server
end for
Server aggregates received gradient estimators g²+1= n > g ot
10: ge+l = =MM((g
II: end for
Dealing with the distributed environment, consider the following optimization problem
min f(x) +
(1)
1=1
where E Id is the parameter vector of a training model, dl is the dimensionality of the problem (number of trainable features), is the number of workers/devicessnodess and f(( is the loss incurred by model a data stored on worker i. The loss function fs Rd + E often has the form of expectation of some random function fi(x) == Eg-D, [fç(z)) with D; being the distribution of training data owned by worker i. In federated learning, these distributions can be different (so-called heterogeneous case). This finite sum function form allows us to capture the distributed nature of the problem very efficient way.
The most effective models frequently over-parameterized, which means that they contain more parameters than there are training data Cmmples(Aror) et al. 2018).
In this case, distributed methods may experience communication bottleneck: the communication cost for the workers to transfer sensitive information in joint optimization can exceed by multiple orders of magnitude the cost of local computation Dutta et al. 2020). One of the practical methods to transfer information more efficiently is to apply a local compression operator (Seide et al., 2014, Suresh et al., 2017 Konečný & Richtárik 2018 Zhang et al., 2017) to the model's parameters (gradients or tensors) communicated across different clients.
DDuutt
Definition 1. A (possibly randomized) mapping C Rd Rd is called compression operator if transmission of compressed tensor C(x) incurs less communication cost than the transfer of initial tensor x.
Although compression decreases the number of bits transferred during each communication cycle, also introduces extra compression errors. As result, the number of rounds necessary to obtain solution with the appropriate accuracy typically increases. However, as the trade-off frequently appears to favor compression over no compression, compression has been proven to be effective in practice.
Distributed Compressed Gradient Descent (DCGD) (Khiiratt et al. 2018) provides the simplest and universal mechanism for distributed communication-effiieen training with compression. With the given learning rate DCGD implements the following update rule
x: r = 3 of = -M(((((('))
Here, of represents an estimated gradient, the result of the mapping of original dense and high-dimensional gradient V fx') Hd into vector of same size that can be transferred efficiently with far fewer bits via MM compression mechanism.
In some cases Tang et al. 2020: Philippenko & Dieuleveut
2020 Fatkhullin et al. 2021 it is desirable to add
compression on the server side to have efficient communication between the server and clients both directions. One could easily extend the general framework of DCGD to the case of bidirectional compression. we define the general master compression mechanism as M. and the worker compression mechanism as M. we could formally write the general bidirectional DCGD algorithm as Algorithm
2

---

Published in Transactions on Machine Learning Research (07/2023)
2 Motivation and Background
Our primary motivation in this work is design compression mechanism that can vary the level of gradient compression depending a local optimality condition. This section of the paper introduces several key concepts essential for the proposed adaptive scheme. We describe constant contractive compressors, discuss what adaptive compressors already exist in the literature, and rehash a lazy aggregation mechanism - the precursor for our adaptive compression.
2.1 Constant contractive compressors
Most methods employing gradient compression mechanisms compressor with constant compression level. In this approach (Beznosikov et al., 2020 Khirirat et al., 2018), one sets
(x) C(x).
(3)
where C: Fd + 12 is a compression operator. There are two large classes of compression operators (or compressors) widely presented in the literature: i) unbiased compression operators and ii) biased contractive compression operators. Our focus in this paper is on biased operators, the definition of which we provide below.
Definition 2 (Biased or contractive compression operator). A mapping C: Rd IR is called biased or contractive compression operator if there exists 0 < s such that
[[[((z) x |2| s (1 a1 |=
Ve Rd
(4)
Top- (Alistarh et al. 2018) and adaptive random (Beznosikov et al. 2020) sparsification compressors are typical examples contractive compressors. Due the biased nature of these compressors, until recently, there was a gap between the experimental and theoretical development of gradient descent methods based contractive compressors. Thus, during the last years, algorithmic approaches have provided several methods of high practical importance, most notable of which is the so-called error feedback mechanism (Seide et al. 2014), fixing divergence issue that appeared in practice and theory [Beznosikov et al. 2020). In contrast, in the theoretical development, until very recently, analytical studies offered weak sublinear (Stich et al. 2018 Karimireddy et al.) 2019 Horváth & Richtárik (20TT) convergence rates under, in some cases, strong unrealistic assumptions. Recently, Richtárik et al. (202T) fixed this by providing novel algorithmic and theoretical development that recovers GD O(//T) rates, with the analysis using standard assumptions only. |aathhullin et al. (2021) subsequently extended the framework by including several algorithmic and theoretical extensions, such as bidirectional compression and client stochasticity. Despite these advances, there are still many challenges in the theoretical understanding of these methods. One such challenge is lack of thorough theoretical study of error feedback methods in a convex setting.
2.2 Existing adaptive compressors
Using a static compression level of the compressor for all clients could limitate the optimization framework's 's capability. Conversely, adjusting the compression level for every client could help reduce overall training time, for example, in hardware heterogeneous cases (Horváth al. 202 Abdelmoniem & Canini 202II.deally. the optimizer should be able to define the particular compression level for each client separately based on the local client's 's data.
Despite the significant practical interest in developing such methods, there is currently little research and understanding of adaptive mechanisms of this type. Only a few papers (Qu et al. 2021 Hönig et al. 202T Mishchenko et al., 2022] Alimohammadi et al. 2022)) provide convergence guarantees with explicit rates, and most them are designed for the specific type of compressors only, mostly quantizers (Guo et al. 2020 Wen et al.) 2017 So, in (Jhunjhunwala al.
2021), the authors design a mechanism for adaptive change of quantization level &
f(a9)
of random dithering
operator (Alistarh et al. 2017). DAdaQuant (Hönig et al. 2021) and FedDQ (Qu et al.
2021) suggest ascending and
descending quantizations throughout the training. AQUILA (Zhao et al. 2022) and AGQ Mao et al., 202T) build an adaptive quantization on top of the Lazily Aggregated Quantized (LAQ) gradient algorithm (Sun et al. 2019). Faghri et al. (2020) proposes ALQ, an adaptive method for quantizing gradients that minimizes the excess variance of quantization given estimate of the distribution of the gradients. It adapts individual quantization levels iteratively to
3

---

Published in Transactions on Machine Learning Research (07/2023)
Table 1 Summary of adaptive compressed methods, AdaCGD, proposed in this work, is superior to its counterparts in all three settings.
Paper
C? Theory?
Strongly conves rate!")
Convex
General nonconvex rate
Thanjhonwala et
X
Abdelmomem
2021
X
X
Hönig ct
2021
(0
X
4
Qu al.
2021
x
x
0
y
Ziaso
2012
X
linear
x
x
Mao et al.
2021
X
linear
x
X
Khinial
Alimohammadi et al.
2022
X
x
+
12n
V7n
r
Zhong al.
2021
x
0
Faghi
x
Mishchenko al.
2022
x
(4)
O
L.
2
Ln
16
0
THIS WORK
/
(1 (1-min min
Mrg Amin
M1
22 M2
( Rates, as suggested in the original paper, are derived from Reeisizadh et al. 2020 and calenlated for non-local full gradient setup
@a 0, 1).
present any explicir rate. We show the rate for noa-local full gradient setup, iee. o² = 0 and = 1.
() Their
>- O is a parameter of InISGD algorithm.
(5) This column incorporates rates the Polyak-Lojjnsewicz nonconvex setting its similarity with the strongly convex setting.
Notation:
#² {C.) 12
scalar constants, A. !|z"" x= I12, A,
f(xa) f², M2
max +
Ammn ), M2 (8) These rates were obtained for noustandard compressor types (C) x||
L+
-
+ L+V Emax Lemma for details), Amin
s
B, where B is constant value.
minimize the expected normalized variance. L-GRECO (Alimohammadi al. 2022) dynamically adapts the degree of compression across the model's different layers during training using dynamic programming. IntSGD (Mishchenko) et al. 2022) adaptively sets the scaling parameter a of a vector plugged in randomized integer rounding operator. CLAN (Zhong et al.) 2021 deals with constant contractive compressors and combines adaptive stepsize rule similar to ADAM(Kingma & Ba 2017) with error-feedback applied on both server and client sides. The work of (Agarwal ct al. (021) presents Accordion, an adaptive compression algorithm that avoids over-compnesiing gradients in critical learning regimes, which can have a negative impact on model performance. The critical regime detected by the rate of change in gradient norms. CAT S+Q (Khirirat al. 2021 proposes an adaptive way to choose k: the top-k elements of the gradient at iteration i, only signs of which clients send to the server along with the gradient norm. Table provides detailed comparison of these works.
2.3 Adaptive compression via selective (lazy) aggregation
We revisit the LAG mechanism, proposed by Chen al. (2018), and consider it an alternative way to embed adaptivity into the framework by introducing communication skipping. According the lazy aggregation communication scheme, each worker i only shares its local gradient if it is significantly different from the last gradient shared previously. Otherwise, the worker decides to skip the communication round. One can consider LAG as an adaptive mechanism that chooses between two extremes: sending a full gradient or skipping the communication round.
Richtárik et al. 2002)) recently extended this idea by introducing the CLAG algorithm that dispatches a compressed update when an old gradient estimate differs too much from the gradient at a new iteration or skips the communication at all. At each iteration of the algorithm, worker i updates its gradient estimate g by the following rule:
of + +CVSs(ct+)) of
gf) if [V sfll > <l -
of
(5)
otherwise,
where Ç >> 0 is a trigger parameter, of is a gradient estimate at previous iteration, and C is a biased compression operator. When the condition the first line, called trigger condition, fires, worker sends an update (( gf) to
the server that smartly aggregates updates from workers and gets new full gradient estimate g" EI 9. ++1 When the trigger condition does not fire, worker i skips communication, which means g gf. Trigger parameter
4

---

Published in Transactions on Machine Learning Research (07/2023)
Table 2 Comparison of convergence guarantees results of methods employing lazy aggregation.
Adaptive compression?
Bidirectional
General BOBCVX case
Method
Cvx case
case
case
DODCVX case
Sun ml
2019
X
LENA
Chackkolad et al
2021
x
Kuchlarkk
Krehaäkk 8)
x
X
AdeCOD INEW, 2022)
controls how frequently the trigger condition will fire, i.e., how often clients skip communication, The update rule in Equation (5) also could be seen as an adaptive compression switching between two extremes: compressing a pre-defined compression level compressing at the maximum possible level, in other words, not sending anything at all.
Although both LAG and CLAG perform well in practice, their fixed and limited compression levels could restrict their performance and make these methods sub-optimal. It is of particular practical interest to create more general method with evolving fine-tuned compression levels.
3 Summary of Contributions
We highlight main contributions follows:
New class of adaptive compressors. In (Richtárik et al. 2022). the authors propose the different classes of compressors unified through single theory. Despite the large variability of the compression mechanisms, including the algorithms with lazy aggregation rule, the compression level all of the considered algorithms is pre-defined and constant during the training. In this work, we take step further and formulate an extended class of adaptive 3PC compressors (Ada3PC) with tunable compression levels defined by some general trigger rules. As original 3PC compressors, this class of compressors very general and includes several specific compressors such AdaCGD, which includes EF21 and CLAG special cases. We build Ada3PC compressors upon large class of biased compressors, such as Top-K and adaptive random sparsification.
Convergence guarantees with strong rates unified by a single 3PC theory. We provide strong convergence bound for strongly convex, convex, and nonconvex settings. Compared with the adaptive methods outside the 3PC context, we provide more elaborate theory with better convergence rates. For AdaCGD, we recover (11/T) rate of GD up to a certain constant in general nonconvex case. It superior in comparison with O(1/VT) rate (Hönig al. 2021 Qu al. 2021 for SOTA in adaptive compression outside 3PC context. The convergence theory in convex set of particular interest due to its novelty even in the case of 3PC for some key cases of AdaCGD, such as EF21 and CLAG. In other words, it is a new SOTA result for the error-feedback method in the convex setting.
Extension of 3PC theory with bidirectional compression. We extend 3PC methods with bidirectional compression, i.e., we allow the server to compress as well.
Table compares AdaCGD with other described the literature lazy algorithms.
4 Ada3PC: A Compression-Adaptive 3PC Method
4.1 3PC compressor
Richtárik al. (2022) introduces the general concept of three point compressors. Here we provide its formal definition for consistency:
Definition 3. We say that a (possibly randomized) map Ch.yy
Rdd
Rd is a three point compressor
AE
yE
(3PC) if there exist constants < A < and B 2 O such that the following relation holds for all x, y. E Rd
E [[]Ch.y(x)) x < A) u1l + Blx v11.
(6)
5

---

Published in Transactions on Machine Learning Research (07/2023)
Authors show that EF21 compression mechanism satisfies Definition with contraction parameter and define
Let C R - R be contractive compressor
FF h,y (z) = h C(x ht)
(7)
If we use this mapping to define compression mechanism M via within DCGD, we obtain the EF21 method.
Another variant of 3PC compressors introduced in (Richtárik et al. 2022 is CLAG compressor. Let C R + R be
contractive compressor with contraction parameter a. Choosing a trigger > 0, authors define the CLAG rule
h C(x h), if 1 -11- > C|| yll?
(, =
(8)
h,
otherwise,
If we employ this mapping into DCGD method 2 as communication mechanism Mj, we obtain CLAG. It includes LAG compressor C² as a special case when compressor C is identity.
4.2 Adaptive 3PC compressor
We are ready introduce the Adaptive Three Point (Ada3PC) Compressor.
Definition 4 (Ada3PC compressor). Let C³ .a...,,, e be 3PC compressors: Ci R + gd for all i. Let Pi, .a. Pm-1 be conditions depending h, y, I. i.e. Pj Rd
Rd + {0,1) for all j. Then, the
adaptive 3PC compressor, associated with the above 3PC compressors and conditions, is defined as follows:
(x)) (xx)
if Pi (h, v) else if P2(h, v,
Cnd (x) =
(9)
cm-1(a) (x)
else Pm-1 v), otherwise.
h.y Chyy (I)
Ada3PC compressor first finds the smallest index j which (y y, x:) = such index does not exist, we set m). Then, Ada3PC applies C compressor on vector x.
4.3 Adaptive Compressed Gradient Descent
There many ways to define meaningful and practical compressors in the context of the adaptive 3PC framework. Here provide particular, perhaps the simplest scheme, which define AdaCGD. In this scheme, have set of m EF21 compressors EFF .J (x:) sorted in order from the highest compression level to the lowest, i.e. < a2 < a'm, where aj is corresponding contractive parameter of the j-th compressor. For example, if we use Top-K C compressors, the first and last indices correspond to the compressors with the smallest and the largest K, respectively. We choose the first compressor, í.e. with the strongest compression, which satisfies trigger rule. We design the j-th trigger rule following an intuition of lazy aggregation rule:
PR = || ch.p . (x)ll < <1I - y/12.
(10)
As in the original LAG rule, the left side of (10) presents the difference between the actual gradient and its estimate, while the right side compares gradient differences on neighboring iterations. The key difference of (IO) trigger from LAG and CLAG rule (5) that the left side of this trigger condition depends explicitly on the level of compression. This feature is essential enables the desired ule-based compressor selection. Altogether, we can define AdaCGD compressor formally.

---

Published in Transactions on Machine Learning Research (07/2023)
Definition 5 (AdaCGD compressor). Given the set of m EF21 compressors (Cy.y (a)) (x))) (x)) sorted in descending order of compression level and Ç 2 0, adaptive AdaCGD compressor is defined with switch condition as follows:
EF
h (x)
if ø hll² - < y1|
else if || Ch,y (x)l1 - C1| yl?
cEF
h.y
CAC (2:)
(11)
Chyy
-1 (a)
else if || C m [x: <1 -yll?
CEP m (x)
otherwise.
h.y
If Ch,y .m uses Top-d compression, Lee. identity operator, AdaCGD is an adaptive compressor composed of the whole spectrum of compressors from full compression, i.e., communication "skip", to zero compression, i.e, sending full gradient. Since the standalone "skip" connection is not 3PC operator, it may not be evident that AdaCGD is special case of Ada3PC. For this reason, here provide the following lemma:
Lemma 1. AdaCGD is special case of Ada3PC compressor.
It is easy to see that if Ç = AdaCGD reduces to EF21. Similarly, CLAG is a special case of AdaCGD when m = 1.
5 Theory
In this section, we present theoretical convergence guarantees for Algorithm ! with Ada3PC compressors in two new cases presented in Table [ The results for general and Pł. nonconvex cases can be found in the appendix.
5.1 Assumptions
We rely on standard assumptions to get convergence rates of Algorithm I
Assumption 1. The functions fi....: fn Fd are convex, i.e.
S((x) [z(u) (y))), y) 2 0, Vxr, y E Rd, Vi.
(12)
Assumption 2. The function f :RR + R __sooothh, i.e.
[V((x) VS(i))I < T-_ vll, Vx, Rd.
(13)
Assumption 3. There exists L4 0 such that 1 L+ be the smallest such number.
à Σ.= V f(()) VfOU) 1, ull? for all x. y Rd. Let
We borrow (L_, } notation from (Szlendak et al. 2022). Assumption 3 avoids a stronger assumption on Lipschitz smoothness of individual functions ft- Moreover, one can easily prove that T._ T._.
The next assumption is standard for analysis of practical methods (Ahn al. 2020 compared previous works, we require a more general version.
Rajput et al. (2020). However,
Assumption 4. We assume that there exists a constant Ω >> 0 such that Billz* x= [2] < ? where x' is any iterate generated by Algorithm 7
Assumption 5. The functions f1,..., In are differentiable. Moreover, J is bounded from below by an infimum fiul R, i.e. f(x) 2 fint for all x Rdd.
5.2 Adaptive 3PC is 3PC compressor
While this may not be obvious at first glance, Adaptive 3PC compressors belong to the class of 3PC compressors. We formalize this statement in the following lemma.
Lemma 2. Let Cad be adaptive 3PC compressor. Let {Ciym, y be 3PC compressors associated with Cad i.e. for all there exists constants 0- < A < and B, 2 0, such that for all h, x E Rd
BlICk (x) 2 < (1- A,) - yl + B.lla 2112.
Then, Cod is 3PC compressor with constants Amin min (inf(A,,... And and Buax max (B,..., Bm).
7

---

Published in Transactions on Machine Learning Research (07/2023)
Proof. Let fix h, y. E R and let j be the index, such that P. 0 for all i j and, if j m, U,,,, = 1. Then,
E| Cl h,g (x) x²2² = E x|| (1 Aj) - ul1 + B, || y/1²
(1 Amin) || y11² Bmax | y11
In the definition Ada3PC compressor, we never specify what conditions P,s are. They are completely arbitrary! The latter enables us build infinitely many compressors out of few notable examples, presented in (Richtárik al. 2022).
5.3 Convergence
In this subsection, we show how assumptions we make about minimized functions and compressors affect the conver- gence rate of Algorithm I
Convergence for convex functions.
The first result assumes that M in Algorithm is a 3PC compressor, M is
identity compressor. (M) Vz E Rd.
Theorem 6. Lel Assumptions
and 4 hold. In Algorithm 1 assume M W is 3PC compressor, M is an identity
compressor, and the stepsize 7 satisfies < 1/M, where M L- L
2B Then, for any T we have
[[((>"] f(x²) max { 11 2000+00))
7 AJ
where Φ' := fxx) f(x)) 2 2 (x())) of for any 2 0.
The theorem combined with Lemma implies the following fact.
Corollary 1.
Let the assumptions of Theorem hold, assume MW is an Ada3PC compressor, MM is identity Then, for any T 2 1 we have
compressor, and choose the stepsize 7 1L+LIy
[ff(TT) - f(x²) I max [L_ + L+
2mmax Ania
200
Amiu
Thus, to achieve E [f(*]] - f(x") S for some & > 0, the Ada3PC method requires
T o (max f-- Li /
2Bmax Amin
2(22++03)
Amto
6
iterations.
Convergence for bidirectional method. Here, we analyze the case when meaningful compressors are applied on both communication directions, i.e., both M and MW are 3PC compressors.
Theorem 7. Let Assumptions and 5 hold. Let MM and M" be 3PC compressors and the stepsize in Algorithm be set as
1
0<75
(14)
L_
L+
(BM((WW1)) 13
+
28" A
(1
3BM A3)
1
Fix and let a² be chosen uniformly from {2 aott
x - uniformly at random. Then
[ ||
24 T
(15)
where vh = f(x²)- - fiul + म llg - - + + (1+
3B (2
1/2 E ll V[i(+'))1 for any 2 0.
8

---

Published in Transactions on Machine Learning Research (07/2023)
In the theorem, superscripts "M" and "W" denote master and worker compressor parameters, respectively. Theorem implies the following corollary.
Corollary 2. Let the assumptions of Theorem hold, assume MM and M
Ada3PC compressors and the stepsize
6nl may
SPM 2M
L- 1-+
A
4 gan
14
A
min
Fix T and let 2 be chosen uniformly from fa",aa x }} uniformly at random. Then, we have
24
+bi
28 GDn (8 A
max
14
3B
A
minn
Thus, to achieve [|VS(*") 1| x² for some e > O, Algorithm requires
24 +b+
eny
2n
32 (2 A
==0
mio
min
iterations.
6 Experiments
In this work, we use the similar setup described (Richtárik et al. 2022 regression problem with nonconvex regularizer:
Namely, we aim to solve the logistic
N Σ log(1 e-maaaa
d Σ
min ZER
where E IRdd E 1-1,1] are the training samples and labels with regularization hyperparameter À > 0 are chosen at A = 0.1 level. In training we use LIBSVM Chang & Lin (201T) datasets phishing, ala, a9a. Each dataset has been split into n = 20 equal parts, each representing a different client.
0.16
0.54
Z=2177
[= 256.00
10-
10-
10-
10-1
10
10
10
10-1
LAG-I
10
LAGAl
10
LAGat
10-1
LAG-4i
(D
CD
GDxi
0
S000
10000
3000
100000
0
5000
10000
5000 AMBsisha
10000
iMbils'n
JMbiuii
4Mbiisaa
Figure 1: Comparison of LAG, CLAG, EF21 and GD with AdaCGD phishing dataset. 1x, 2x, 4x (and on) indicates the multiplication factor we use for the optimal stepsizes predicted by theory. For example, GD-x1 means gradient decent (GD) with theoretical stepsize multiplied by 1.
Figure compares the performance of our proposed algorithm, AdaCGD, with other popular 3PC methods. In order to make a fair comparison, we fine-tuned the stepsize of each considered algorithm with a set of multiples of the corresponding theoretical stepsize, ranging from 2 to 28, We implemented all simulations in Python 3.8, and ran them on cluster of 48 nodes with Intel(R) Xeon(R) Gold 6230R CPUs. To evaluate the effectiveness the contractive compressor used in each algorithm, chose the Top-k operator
compressor of choice. For EF21 and CLAG,

---

Published in Transactions on Machine Learning Research (07/2023)
used the top-1 compressor, which has been shown to be the best in practice for these methods. For AdaCGD, we chose array of compressors that varied from full compression (skip communication) to zero compression (sending the full gradient), with step of 5, We used the communication cost of the algorithm as the stopping criterion for all experiments.
Our findings indicate that AdaCGD achieves comparable performance CLAG, and certain cases (notably the phishing dataset), it outperforms CLAG. Additionally, AdaCGD consistently outperforms LAG in all experimental settings. However, it is worth noting that datasets such ala and a9a, where higher compression is more advantageous, CLAG exhibits slightly better convergence rates. These results highlight the valuable role of AdaCGD complement to existing 3PC methods, with the potential to enhance the convergence rate of distributed optimization algorithms. For further experimental details and results, please refer to the appendix.
<
<
Top-35
Top-5
Top-35
Skip
gradient
Fall gradient
Full gradient
[= 1.85
{ 6.35
(= 256.00
Top-5
Skip
Top-35
Top-5
Skip
Top-35
gradiont
Tup-35
Fall gradient
Top-5
Full grudicat
Figure 2:
Distribution of compressors utilized during the training process on the phishing dataset for different Ç values,
shown as multiple pie charts. The setting the same as for Figure] T
Figure provides insights into how adaptivity in compression is utilized during the training process. The plot displays the distribution of compressors that selected during training by all clients. The intuition behind the of adaptivity is that when there is smaller gap between neighboring time step gradients, it leads to smaller updates, allowing AdaCGD to apply larger compression without losing information. Conversely, when there is larger gap between gradients, it means more informative updates that are more susceptible to higher compression, hence requiring AdaCGD to compress less. As expected, when = 0, AdaCGD is equivalent to EF21, which tends to choose the maximum compression level across different compressors. Conversely, with a larger Ç value, the AdaCGD behaves more like LAG/CLAG and has an increased number of skip connections. However, there range values (0.16, 0.54, 1.85, and 6.35) where the algorithm benefits from adaptivity and utilizes the full spectrum of compressors.
7 Discussion and Limitations
The main limitations of the work are assumptions we make upon functions fa of the problem However, on the other hand, these assumptions govern the convergence rates we report: for example, we cannot show linear rates for convex functions due to the fundamental lower bound (Nesterov al. 2018).
Another limitation comes from the analysis of the Bidirectional algorithm (Theorem 7). We show the analysis only for general nonconvex functions.
10

---

Published in Transactions on Machine Learning Research (07/2023)
References
Abdelmoniem, A. M. and Canini, M. Towards Mitigating Device Heterogeneity in Federated Learning via Adaptive Model Quantization. In Proceedings of EuroMLSys 21, Apr 2021. (Cited on
Agarwal, S., Wang, H., Lee, K., Venkataraman, S., and Papailiopoulos, D. Adaptive gradient communication via critical learning regime identification. In Smola, A., Dimakis, A., and Stoica, I. (eds.), Proceedings of Machine Learning and Systems, volume pp. 55 55-80, 2021. URL httptttt////soteetettteeee -1Paper.ppd (Cited on 4
m sys. org/ paper leel /lle/paper/
2021/Eile/1d7f7ee http:///0.......ooooooo666633939
Ahn, K., Yun, C., and Sra, S. Sgd with shuffling: optimal rates without component convexity and large epoch requirements. Advances in Neural Information Processing 3ystems,33:11726-1 2020. (Cited on 7
Alimohammadi, M., Markov, I,, Frantar, E., and Alistarh, D. L-greco: An efficient and general framework for layerwise-ddaptive gradient compression, 2022. (Cited on
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. QSGD: Communication-efficinn SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pp. 1709-1720, 2017. (Cited on 3)
Alistarh, D., Hoefler, T., Johansson, M., Khirirat, S., Konstantinov, N., and Renggli, C. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), 2018. (Cited on
Arora, S., Cohen, N., and Hazan, E. On the optimization of deep networks: Implicit acceleration by overparamettriizatin. In Proceedings of the 35th International Conference on Machine Learning (ICML), 2018. (Cited on 2
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. On biased compression for distributed learning. arXiv preprint arXiv:2002.124110 2020. (Cited on
Chang, C.-C. and Lin, C.-. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems
and Technology (TIST), 2 2011. (Cited on 9 24
Chen, T., Giannakis, G., Sun, T., and Yin, W. LAG: Lazily aggregated gradient for communication--fficeent distributed
learning. Advances in Neural Information Processing Systems, 2018. (Cited on
Dutta, A., Bergou, E. H., Abdelmoniem, A. M., Ho, C.-Y., Sahu, A. N., Canini, M., and Kalnis, P. On the discrepancy between the theoretical analysis and practical implementations compressed communication for distributed deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3817-3824, 2020. (Cited on
Faghri, F., Tabrizian, I. Markov, I., Alistarh, D., Roy, D. M., and Ramezani-Kebrya, A. Adaptive gradi- ent quantization for data-parallel sgd. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 3174-3185. Curran Asso- ciates, Inc., 2020. URL ltttps: wttp://ss....urrrn.eeeeecca (aboeelofaa99af77cccllaaaaaaaa/
E.LLes/paper/222/EEL
.ddf (Cited on
Fatkhullin, I., Sokolov, I., Gorbunov, E.,, Li, Z., and Richtárik, P. B121 with bells & whistles: practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.03294, 2021. (Cited on 3
Ghadikolaei, H. S., Stich, S., and Jaggi, M. LENA: Communication-effiiee distributed learning with self-triggered gradient uploads. International Conference on Artificial Intelligence and Statistics, pp. 3943-3951. PMLR, 2021.
(Cited 5)
Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L.,, Kyrola, A., Tulloch, A., Jia, Y., and He, K. Accurate, large minibatch sgd: Training imagenet in hour. arXiv preprint arXiv:1706.02677, 2017. (Cited on [T]
Guo, J., Liu, W., Wang, W., Han, J., Li, R., Lu, Y., and Hu, S. Accelerating distributed deep learning by adaptive gradient quantization. In ICASSP 2020 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1603-1607, 2020. doi: 10. RL.1099CAASSP447766000000090
(Cited on

---

Published in Transactions on Machine Learning Research (07/2023)
Hönig, R., Zhao, Y., and Mullins, R. D. Dadaquant: Doubly-adaptive quantiiaaionn for communication-effiiiiii federated learning. CoRR, abs/211 111.1.....0 100465, 2021. URL http://s//aaxiv..orr//////////// 00465 (Cited on 3
Horváth, S. and Richtárik, P. A better alternative to error feedback for communication 9th International Conference on Learning Representations (ICLR), 2021. (Cited on
distributed learning. In
Horváth, S., Laskaridis, S., Almeida, M., Leontiadis, I., Venieris, S., and Lane, N. D. FjORD: Fair and accurate federated learning under heterogeneous targets with ordered dropout. In Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, 2021. URL hittps://openreet
aet/forumiid-a 4fl:ed444fLL... 7H5D
eT (Cited on 3)
Jhunjhunwala, D., Gadhikar, A., Joshi, G., and Eldar, Y. C. Adaptive quantization of model updates for communication-
efficient federated learning. In ICASSP 2021 2021 IEEE International Conference Acoustics, Speech and Signal doi: 10. 10.1109/CASSP339229 200.99722222222.2222 0.011.9916977 (Cited on
Processing (ICASSP), pp. 3110-3114, 2021.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z., Cormode, G., Cummings, R., D'Olvveir,, R. G. L., Eichner, H., Rouayheb. E., Evans, D., Gardner, J., Garrett, Z., GascAşn, A., Ghazi, B., Gibbons, B., Gruteser, M., Harchaoui, Z., He, C., He, L., Huo, Z., Hutchinson, B., Hsu, J., Jaggi, M., Javidi, T., Joshi, G., Khodak, M., Konecny, J., Korolova, A., Koushanfar, F., Koyejo, S., Lepoint, T., Liu, Y., Mittal, P., Mohri, M., Nock, R., Ozgur, A., Pagh, R., Raykova, M., Qi, H., Ramage, D., Raskar, R., Song, D., Song, W., Stich, S. U., Sun, Z., Suresh, A. T., TramAir, F, Vepakomma, P., Wang, J., Xiong, L., Xu, Z., Yang, Q., Yu, F. X., Yu, (Cited on
H., and Zhao, S. URL http::tttt://ate http://wwww.gggga.ooaaoooooo abs////b//// 1912. 19t./99911..99997 04977
Karimireddy, P., Rebjock, Q.. Stich, S., and Jaggi, M. Error feedback fixes SignSGD and other gradient compression schemes. In 36th International Conference on Machine Learning (ICML), 2019. (Cited on
Khirirat, S., Feyzmahdavian, H. R., and Johansson, M. Distributed learning with compressed gradients. arXiv preprint BBKi::880600573,, 2018. (Cited on 23
Khirirat, S., MagnAšsson, S., Aytekin, A., and Johansson, M. A flexible framework for communication-efficinnt machine learning. Proceedings of the AAAI Conference Artificial Intelligence, 35(9))8101-8100) May 2021. URL
https://ojst aaa. http:///...aa...ooo/eeeeeee.ee.p
(Cited on 4
Kingma, D. P. and Ba, J. Adam: method for stochastic optimization, 2017. (Cited on 4
Konečný, J. and Richtárik, P. Randomized distributed mean estimation: Accuracy communication. Frontiers in Applied Mathematics and Statistics, 4:62, 2018. (Cited on 2
Konečný, J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. Federated learning: Strategies for improving communication efficiency, arXiv preprint arXiv:1610.05492, 2016. (Cited on I
Li, Z., Bao. H., Zhang, X., and Richtárik, P. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference Machine Learning (ICML), 2021. arXiv:2008. 100999 (Cited on [6]
Lin, Y., Han, S., Mao, H., Wang, Y., and Dally, B. Deep gradient compression: Reducing the communication bandwidth for distributed training. International Conference on Learning Representations, 2018. (Cited on M
Mao, Y., Zhao, Z., Yan, G., Liu, Y., Lan, T., Song, L., and Ding, W. Communication efaeeaaaaatioefffiiiiiiiiili federated learning with adaptive quantization. CoRR, abs/2104.06023, 2021. httl:pps//aaaii..o//////////1/// 06023 (Cited on
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-effiiennn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp. 1273-1282, PMLR, 2017. (Cited on
Mishchenko, K., Wang, B., Kovalev, D., and Richtárik, P. IntSGD: Adaptive floatless compression of stochastic gradients. In International Conference on Learning Representations, 2022. URUnnttp:://pperrevveew forum?id-pP pptpXxXc2xccccc (Cited on 4h
Nesterov, Y. al. Lectures on convex optimization, volume 137. Springer, 2018. (Cited TO
26
12

---

Published in Transactions on Machine Learning Research (07/2023)
Philippenko, C. and Dieuleveut, A. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. ,,591, (Cited on
2
Pishro-Nik Nik. H. Introduction to Probability, Statistics, and Random Processes. Kappa Research, LLC, 2014. ISBN 9780990637202. URL http::://bools..pooll.........as http://s......e.....oo....oooooa
(Cited on 15)
Qu, I.,, Song. S., and Tsui, C. Feddq: Commanicaiion--fffccinnnnniiecio learingg with descending quantization. CoRR, abs/2110.02291, 2021. URL [
(Cited on
Rajput, S., Gupta, A., and Papailiopoulos, D. Closing the convergence gap of sgd without replacement. In International Conference on Machine Learning, pp. 7964-79977 7973. PMLR, 2020. (Cited on
Reisizadeh, A., Mokhtari, A., Hassani, H., Jadbabaie, A., and Pedarsani, R. Fedpaq: communication-effiee federated learning method with periodic averaging and quantization. In Chiappa, S. and Calandra, (eds.), Proceedings of the Twenty Third International Conference Artificial Intelligence and Statisties, volume 108 of Proceedings of Machine Learning Research, pp. 2021-2031. PMLR, 26-28 Aug 2020. URL https://
proceedings.mil mlr. wtwpes//v1//reesiieeooeeeee
html (Cited 4
Richtárik, P., Sokolov, I., and Fatkhullin, I. Ef21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint arXiv:2106.05200 2021. (Cited on 3 15
Richtárik, P., Sokolov, I., Fatkhullin, I., Gasanov, E., Li, Z., and Gorbunov, E. A. 3pe: Three point compressors for communication--eficieenn distributed training and better theory for lazy aggregation. CoRR, abs/2202.00998, 2022.
URL BRRL:tt:::/// http//aaiviv...///..//e../...av. org. abs 22002.222222222 00998 (Cited on
Seide, Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochastic gradient descent and its application data Mata--arallll distributed training of speech dnns. In Fifieenth Annual Conference of the International Speech Communication Association, 2014. (Cited on 3
Stich, S. U., Cordonnier, J.-B., and Jaggi. M. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), 2018. (Cited 3)
Sun, J., Chen, T., Giannakis, G., and Yang, Z. Communication-effiiennn distributed learning via lazily aggregated quantized gradients. Advances Neural Information Processing Systems, 32:3370-3380, 2019. (Cited on
Suresh, A. T., Felix, X. Y., Kumar, S., and McMahan, H. B. Distributed mean estimation with limited communication. In International Conference on Machine Learning, pp. 3329-3337. PMLR, 2017. (Cited on 2
Szlendak, R., Tyurin, A., and Richtárik, P. Permutation compressors for provably faster distributed nonconvex optimization. In International Conference on Learning Representations, 2022. URL https:://///........ /tttps::/openreviee:
met/fformm2.dd=ugz255::
(Cited on 7
Tang, H., Lian, X., Yu, C., Zhang, T., and Liu, J. DoubleSqueeze: Parallel stochastic gradient descent with double-pass cooo--oomensated compression. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2020. (Cited on 2
Vaswani, S., Bach, F., and Schmidt, M. Fast and faster convergence of sgd for werrpaaaaeterized models and an accelerated perceptron. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1195-1204. PMLR, 2019. (Cited [
Wen, W., Xu, C., Yan, F., Wu, C., Wang, Y., Chen, Y., and Li, H. Terngrad: Ternary gradients to reduce com- munication in distributed deep learning. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran As- sociates, Inc., 2017. URL httpst newrips. wwt.sssss...pprpppppperraaeaeee. cc/paper httpee/eesss//ppp///////1
39fcd07f2 (1118882222244ccc11116100
Paper. pdf (Cited 3
You, Y., Li, J., Reddi, S. Hseu, J., Kumar, S., Bhojanapalli, S., Song, X., Demmel, J., Keutzer, K., and Hsieh, C.-J. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint 1rXiv:1904.00962, 2019. (Cited on
13

---

Published in Transactions on Machine Learning Research (07/2023)
Zhang, H., Li, J., Kara, K., Alistarh, D., Liu, J., and Zhang, C. ZipML: Training linear models with end-to-end low precision, and little bit of deep learning. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 4035-4043, PMLR, U6-11 Aug 2017. URL
mlr 2orress/700/hanqq177 7 html (Cited on 2
Zhao, Z., Mao, Y., Zeeshan, M., Liu, Y., Lan, T., and Ding, W. AQUILA: Communication efficient federated learning with adaptive quantization of lazily-aggregated gradients, 2022. URL httpppss//ppeeerrreeeeeee//trttr
1d-cd2Le5SOur (Cited on 3 4
Zhong, Y., Xie, C.,, Zheng, S., and Lin, H. Compressed communication for distributed training: Adaptive methods and system, 2021. (Cited on 4
14

---

Published in Transactions on Machine Learning Research (07/2023)
APPENDIX
In Appendix A we state the basic facts needed for detailed proofs of the propositions. In Appendix B we provide the proofs missing the main part of the paper. Appendix [ contains experimental details and extra experiments. We briefly discuss the main limitations of the paper in Appendix D
A Basic facts
We start the appendix with common math facts. Lemmas B and present classic in metric space and random variables in probabilistic space, respectively. Lemma shows classic upper bound on quadratics. Lemma provides sufficient condition that ensures quadratic inequality appearing in our convergence proofs holds.
inequality for vectors
Lemma 3 (Cauchy- Schwwrtz inequality for arbitrary vectors). Let 2. Rdd be arbitrary vectors. Then, the following inequality holds
(2, v) |
(16)
where (:,) and ||-1| denote the inner product and the induced norm, respectively.
Lemma 4 (Cauchy-Schwarze inequality for random variables; section 6.2.4 (Pishro-Nik 2014)). For any two random
variables X and we have
[[[Y|| S |
(17)
where equality holds if and only if aY, for some constant a R.
Lemma 5. Let a, b, c, d IRd be arbitrary vectors. Then, the following inequalities hold
||a s 2([1a clI + ||c ||c-)))²),
(18)
||a - b112 < 3(1la c|1 + ||c - dl12 + l|d - b1
(19)
Lemma 6 (Lemma 5 of (Richtárik al. 2021 1f0 <> - up to the factor of since Vatb
Jatb then a7² by S 1. Moreover, the bound is tight
5. min
Va I Va+5
15

---

Published in Transactions on Machine Learning Research (07/2023)
B
Proofs for Sections 4 and 5
B.1
Lemma 1
At first glance, AdaCGD does not seem to be an Ada3PC compressor. However, we can construct an Ada3PC compressor, which is equivalent to AdaCGD. Lemma
1
AdaCGD is special case of Ada3PC compressor.
Proof. Let consider the following Ada3PC compressor constructed from one LAG compressor and m EF21 compressors.
h
|| h|12
- <|1= yll?,
CLAG
| h||2 <|| y11
x
otherwise.
Ch 11 (x)
else if || Ch,y .1 (x) 1 C|| - yl1?
(2))(a))
C m- (x) Ci m (x)
else if
||x-
Ch.y
cEP .m
( (1))1 - Cl| v1l?
otherwise.
If || - -1l2 < C1 - yll? then Ch.yy applies the LAG compressor to æ. This LAG compressor in turn outputs h, as does CAC for the same condition. If the opposite true, ie., | hil² > C|| yll², Cb.y checks the same conditions and h.y
chooses the same compressor as Ch.. Thus, Chyy is equivalent to Ada3PC compressor Ch.y-
B.2 Theorem
The proof of Theorem O requires several auxiliary results. Lemma 7 states the descent lemma typical for the analysis
of biased compressors. Lemma 8 shows how individual 3PC compressors, applied at clients, affect the aggregated divergence of gradient estimates from gradients. Lemma presents a technical upper bound on Lyapunov function Vpa
Lemma 7 (Lemma 2 of (Li et al. 20211). Suppose the function L--smooth and x1+1 x² --g". where g² Rd is any vector, and 7 > 0 is any scalar. Then we have
f f(x*) - 2 21
(2,-1
1
I_
|1at1 -0-11-x011200 + 2I1o*= vf(x')1
(20)
2
27
2
Lemma 8 (Lemma B.3 of (Richtárik et al. 2022 ). Let Assumption 3 holld Consider Algorithm 7 with 3PC compressor
M" and identity compressor M Then for all 2 0 the sequence
G
[V((2')- - gf11
(21)
satisfies
E [ (1- A)E [ + BLI [11-4t1=0111 -x-11] =]]
(22)
where A and B are parameters of M". Lemma 9. Let Assumption holdd Let Lyapunov function v = f(x²) - -f- + 2 G Then, for any 2 0, the following
+
inequality holds
ENG' < V
(B(I - x² 111 + 2 EE(GE [G'). (BIIV)(+))))++ 2
(23)
A
where x² is any point belonging to Argmin fz))
Proof. By definition convexity we get
Expt = Ef(x') - 1 + 2 1EG*
A
B(VI(a'). ),"" -x²) + A
BG²
E ((TF(ct), / 2 EG'
x²' -a'-2" x², 3 BG
16

---

Published in Transactions on Machine Learning Research (07/2023)
By applying Cauchy-Schwarte inequality vectors and random variables we finish the proof
1 - -x",, V22OO)
E
vf(x'),
EG
A
E
|V / 11 + BG -1at-
1²112 + EG
A
A
[EIIVf((=*)[]]
2 BG¹)
(B11Iz- x+1 + 2 E [G*)
A
A
Now we ready to prove the main theorem.
Theorem [ Let Assumptions
7
3 and 4 hold. Assume the stepsize ry of algorithm satisfies 0 << S 1/M, where
M L_ + L+ / 2B A. Then, for any T 0 we have
2( + Vo)
E [[(+T)] - 1(x)) E max
> A
T
Proof. Combining Lemma 7 Jensen's inequality, we get
(( -
1
L_
|
-2112
+ ?
1
1
fi(x')
91
24
2
91
n
s 2 -1
1
L_
1
x1112 + 1
11o1
(f(('')1?
(24)
2y
2
2
1=1
((((()))
1
|| x11 + - L_
2
2
Now applying Equation 24h and Lemma
8 on the difference of Lyapunov functions, we obtain
E
[
E
v
E [ f(x')] +
E [
? E [[
-25 [|][ 119
1
I_
EE [1 - x x011]
21 [G']
27
2
A 2 - 2 B [G]]
- [
L_
E [11= 10-11-=1'1 121
27
2
+ (11 A)E BLI
- -
Rearranging the term, we get
EE [1] - EE [w']]
-2 [IV
11 -
1
L_
BB2
IE [[| - 2¹
A Y
E [G']
27
2
A
2 A
We further note that
1
L_
BBL
+
2
0
+
1-2
2B
2
+
L
1
Lemana 7 <
29
2
A
A
L_ + L+ 1
2B
Appropriately chosen stepsize gives
2 A
(E
[E[IV](>')) [1]] + (G'])
E.
< - -min
2 2
17

---

Published in Transactions on Machine Learning Research (07/2023)
Rearranging the terms, we have
IE [bF] E [v+++]]
E [[Vvf(>)11]
+
7 |G"
(25)
A
min { 2)
from what deduce that EE [v++]] [VV.
Using Lemma 9 and (25 we have
Eu++EE
(BW)² - EE [IV)
+ 2 AG
(E ||-1"]=*1]]]
+ A B (Gy)
A
E || 1=1 7 [G
TR [v] E [v[tt]]-
min (
Using that [
[ I EN s Vo and E [||=r x11 s Ω2 obtain
Ω2 + vo
EV+tIEw
E [1
[ [v(+]])
min 3 +
Rearranging again, we get
min ( +}
Ω T0
-
B [1ctt]]
E [(
Summing up from 0 T 1, we finish the proof
2 2
Ω
To
[f(("))] f(x²(()++))))))) SE
S max
(26)
7
B.3 Theorem
Algorithm 2 3PC-BD (Bidirectional 3PC algorithm)
Input: starting point z Rdd 9. Rd fori 1.... (known by nodes), g"
Σ E
(known by master);
learning rate ? > 0.
2: for = 0,1,2,
do Broadcast g' to all workers for for all devices I,..., in parallel do r+1 x² "
o. = Ct (i (v((t))))
Communicate g to the server
8: end for
Σ g. 1+1 9: -= =
1=1 10: g++1 = g" .g (+++1)
I1: end for
18

---

Published in Transactions on Machine Learning Research (07/2023)
For Theorem 7 assume that both compressors M and M in Algorithm | of the algorithm are:
are 3PC compressors. The main steps
x1+1 x² 7
g. ++1
C.. F. (Vi((((t1)
9
9i ++
==1 g g+1 C g. (1
Unlike in the previous subsection, we use additional notations: P. == |lø V(((("))))))))))))))))()))))VV ) p = Σ P and
R' := || x0
Lemma 10 is an analogue of Lemma 8 (in bidirectional case we need slightly different arguments at some steps).
Lemma another technical lemma that upper bounds E Illg' 1 1
Lemma 10. Let Assumption hold, C be 3PC compressor, and g be an 3PC-BD estimator of Vilstt) Lie
i.e.
x ++ = C (i (V
(27)
for arbitrary o. for all i E [m], 2 0. Then
E [pt+]] S (1- A + BW E [R']
(28)
Proof. Define W = (0i.
For xt _0 (.rt11 ). then
E [ = E
E [pt+] ]
E
E o
(f(t+t)) wr]
f((()) (Vf((ttt)) - VS((ott2) ? [wm)
E
E
(29)
a.
AWD
E
|b
V/('')| B (
Averaging the above inequalities over i E [n]. we obtain (28). Indeed,
E
[pt+1]
E
[
71
J
|0
(f(('')]1 |||
Σ "B [| V
(1
E P
+ T2
Bw
V v((
Assumption 5
A E
P
+ B 1 - 1112
= (1 - A
PM]
+ B 1. [
Lemma 11. Let Assumptions and hold, CM " be 3PC compressors. Let g be an 3PC-BD estimator of f((+++)), i.e.
g
++1
C
(e (Vf((ttt)
(30)
19

---

Published in Transactions on Machine Learning Research (07/2023)
" 12 Σ Di Le.
and let gl+h1 be an 3PC-BD estimator of g =
9f CM
gr (g'
(31)
for arbitrary g" 96 for all E [n].t t 2 0. Then
E - of -11 |2] | 2 (1 - AM L ||ls* --11]] + +3B² (2-33 JB + +3B (B" + +1)L3E where g' n Ei=1gi = E 01.
(32)
we define W {gf, ... Ih x² ,.++1} and bound E - g-+1
Proof. Similarly to the proof of Lemma
10
|19 -
E E 11 +1 - g [/]
E
E EE |1 Se (g(t1)- - -1 ]
(1 A E |1g' - 51]]]] + BB | 5-1
(33)
Further, we bound the last term in 33
Recall that
n
a
ge+1
Cu ((=))))) (V. (V.((z(+1))
(34)
n
Then,
E
||ght1
-
E
0f ( ( (Vf((x(1)) -
Co (
19
3
|| (i (VA(att))
V/(
E
11
3
IE
fi \
E [(+)t) [511
3(1
AW)
+ +3B" ||V m011"]
[
3
n E V x''1"]
E
+
n
Assumption S
3(2 - A 13 [M]] + +3
+ +1)23 LE
|| - x202=" 20113]
= 3(2 - J P*] + BW 1 [R')
(35)
where the first inequality follows from Young's 's incquality. Plugging
35
into 33 we finish the proof:
JE [loo 3²|l"] + 3B (2- - EE E -11 ---11 s (1
+ +3BM(B" + +1)L3B [n').
20

---

Published in Transactions on Machine Learning Research (07/2023)
Having proved the previous lemmas, now show the convergence of bidirectional 3PC algorithm.
Theorem 7 Let Assumptions 3 and S hold, and let the stepsize in Algorithm 2 be
6B +1)
2BW
3BM - AW)
0 059< - I
1
(36)
AM
AM
AM
Fix T and let tt be chosen uniformly from (a",x',." 1... TT } uniformly at random. Then
2T
Vs("")) 11 -
E
(37)
where ToT f(x*) pimt Fo l1g1
A (1
32"
Σ 1l
VSi(xt)11
Proof. We apply Lemma 7 and split the error |1g V)((t)|1 into two parts
f(x(+1) f(x') 3 [
20
1 L
R² + 2 l1g' vf(x')]1
27 2
18
f(x²) 7 |
I
R' + +~ vf(x')] 12 + 11g - g²12
2
27 2
f(x'') 2/ [
(1 L_
R¹ + 2
|0 Vf(('')|| + 1lø g²ll
22 2
11
7 = f(x') 2 [
L_
R¹ + 7 + "112* و 9²ll
(38)
27
2
where in the last inequality we applied Young's inequality. Subtracting pint from both sides of the above inequality, taking expectation and using the notation 8² -xx²) fiul, we get
- ( 1 L- 27 2
E
E
E 2
E [
MI [Pd]
+ y [|0 -000--g11 0']]"]]
(39)
Further, Lemmas T0 and provide the recursive bounds for the last two terms of 39
E [pt+1] < (1 A P + B L Re
(40)
E |1l0
- 9- < (1 ME |11l --'1" 3B (2 A JE
3BM (BW + 1 [R']
(41)
Summing up 39 with A multiple of 41 obtain
E 8 11
E
[|ls*
34|1]
E [5]]
FF V |19)
1 L_
E [R]]
AM
2r
[P*] + >E [10* -
(a - A ل [||s x0(13])
+
AM
7
(3BM(2 (2 A Awy ما [ + 3B3 (BWW + 1)L (129)
AM
S E [88
E
V |1 113 + 2
[110- 1111-~=9110 3-|["] -
AM
1
-_ 3,B BM (BW + +1)13
IE [nc|]
27
2
AM
3BM AW)
+
1+
E [P'].
AM
21

---

Published in Transactions on Machine Learning Research (07/2023)
Then adding the above inequality with a _y (1
12 A AN
multiple of (40), we get
(1
3BM (2 - )
E [[
E
[6
E
||g* - 0-|l + AW
14
E [ptt]]
AM
AM
<B(6
V (z))) [1=] + AM E
[ll9* 9
1
L_ 37 BM (B" 1)L?
E [R'] +- 11 3B (2- - An)
E [Pd]
27
AM
AM
3BM (2 1
?
+
((1
A [P'] + B [R*])
AW
AM
|lls 0411"] + AW ( 1+ 3BM(2 A")
I E
[8"]
+ 7
E
E [PP)] - [ [|V
AM
AM
2
1
L.
ByBM
(B" + 1)
7B L23
3BM (2- AW)
[1
E R'
(42)
27
AM
AW
AM
Thus by Lemma and the choice of the stepsize
3BM - AW) -1
6BM
+ 1)
2BW
0sT< L
+
1
(43)
AM
AM
AM
the last term in (22 is not positive. By summing up inequalities for f 0,1, T 1, we get
T-1
0 < E
V T
Σ
E
Multiplying both sides by 3, and rearranging get
2400
T
7/"'
B.4 Convergence for general nonconvex functions
The results in two subsequent subsections M W as a 3PC compressor and AM as an indentity one. According to Lemma [ Adaptive 3PC is 3PC compressor. Thus, convergence results from (Richtárik al. 2022 valid for Adaptive 3PC compressor. It leads us to the following corollary.
Corollary 3 (Corollary 5.6 of (Richtárik et al. 2022 Let Assumptioons 2 and 5 hold. Let MW and MM in Algorithm)
be Ada3PC and identity compressors, respectively, and choose the stepsize 7
Then, for any T
Bmax
Amin
we have
2(f(29)- f(xinf)) ((aitt) (L-
L
Bmaxe Amia
DL 1191 Vf((2)111
E [[V <
T
Amiu T
That is, to achieve E [V < E² for some E > O, Algorithu
requires
2(ʃ(2²) ((cin)) (I- + L4
Buax Amin
E R
10 v1((x)))12]
T
52
Aming
iterations.
22

---

Published in Transactions on Machine Learning Research (07/2023)
B.5 Convergence for Płnonconvex functions
The setup here is the same as in the previous subsection, except we add the following assumption.
Assumption 6 (PE. condition). Function f μ 0, i.e.,
R2 IR. satisfies the Polyakktoojssiewicz (Pt.) condition with parameter
2 -
Vx E
where x² == arg min (() and l = f(x*).
2E84
Corollary 4 (Corollary 5.9 of (Richtárik et al. 2022 ) Let Assumptions 2
3 5 and 6
hold. Let M" and MM
in Algorithm 7 The Ada3PC and identity compressors, respectively, and choose the stepsize
Amin
min
L_
L7
V
2mmax
2p
Amnn
Then, to achieve E [f(x²)] - f < S for some & > O the method requires
L_ + L+
Bmax Anin
f(x") f(xint) +
E. 119 V//29911/\/A //mio]
O
max
Amiu
log
iterations.
23

---

Published in Transactions on Machine Learning Research (07/2023)
C Experimental details and extra experiments
All simulations are implemented in Python 3.8 and run on Intel(R) Xeon(R) Gold 6230R CPU cluster with 48 nodes. We fine-tune the stepsize of each considered algorithm with (2"; 21 ,.,....... 2*) multiples of the corresponding theoretical stepsize. As contractive compressor we use Top-k operator. For EF21 and CLAG we use top-1 compressor, which usually the best in practice for these methods. For AdaCGD choose compressors varying from full compression (skip communication) to zero compression of features (sending full gradient). In order to provide fair comparisons, we choose master compressor MM as identity operator in these experiments. For the stopping criterion we choose communication cost of the algorithm.
We use the setup described Richtárik al. 2022), namely logistic regression with nonconvex regularizer:
min zE
f(x) N
Σ
log(1 + te-mala E 1t27
zj
where E RR Vi E (-1,1} are the training samples and labels with regularization hyperparameter À > 0 chosen at À = 0.1 level. We solve this problem using LIBSVM [CBSVg & Lin (201I) datasets phishing, ala, a9a. Each dataset has been evenly split into n = 20 equal parts where each part represents separate client. Figures] 3 6 compare AdaCGD with LAG, EF21 and their generalization CLAG. Figure 4 provides the comparison convex regime, i.e. À 0, for phishing dataset. In the experiments, AdaCGD shown be comparable and some cases superior CLAG and always superior LAG. other words, AdaCGD efficiently complements CLAG and other 3PC methods.
0,16 0.16
= 0.54
21777
[= 256.00
10-2
10--
10/-1
|198x)11
10-
10
10
10-1
10
10--
uMbilon
#Mbiush
#Mbitshh
AMINishh
Figure 3: Comparison of LAG, CLAG, EF21 and GD with AdaCGD on phishing dataset.
ap Aac00a1N
(LA0325661g)
ALCODal2
Figure 4: Comparison of LAG, CLAG, EF21 and GD with AdaCGD phishing dataset in the convex regime i.e. A = 0.
24

---

Published in Transactions on Machine Learning Research (07/2023)
-
0.54
6.35
256.00
2771 sts
IPl xte
ITI: xiE
LAG CTAGistfapp AurYEns
LAG-al
LAGal (lotis NarTE vis
-
(3)
(20
60xX
5000 AMbilatt
1000]
5000
10000
0
9000
10000
9000 +Mibishi
10000
AMB
AMBNts/i
Figure Comparison of LAG, CLAG, EF21 and GD with AdaCGD on ala dataset.
0
= 0.4
6:35
[= 256.00
LAGST
LAGiT
LAGiS CLAG agl
CLAO oet
CLAGkd opt
McCO
[1990))11
10-1
10-1
10-1
LAG-si
10-3
(0-2)
10-2
GDx1
5000 4Mbisan
10000
5000
10000
5000
[000]
5000
18000
#Mbisai
#Mbissaa
AMbsisaa
Figure 6: Comparison of LAG, CLAG, EF21 and GD with AdaCGD a9a dataset.
25

---

Published in Transactions on Machine Learning Research (07/2023)
D Limitations
The main limitations of the work are assumptions make upon functions fi of the problem |
But, on the other hand,
these assumptions govern the convergence rates we report: for example, we cannot show linear rate for convex functions due to the fundamental lower bound (Nesterov et al. 2018).
Another limitation comes from the analysis of Bidirectional 3PC algorithm (Theorem 7 We show the analysis only for general nonconvex functions.
26


Reviews:
[{"review_id": "EeUn3ZqIBb", "reviewer": "Reviewer_bcXK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- A very well-written paper with a nice flow of ideas. The background and existing literature are discussed in very details.\n- Unified theoretical analysis framework with SOTA convergence results.\n- Nice extensions of the 3PC framework to increase the potential practical implication of such theoretic framework.\n\nWeaknesses:\n- I wonder why the bidirectional method is only analyzed for the non-convex case, is there any specific difficulty?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes an Adaptive Three Point Compressor (Ada3PC) framework, which is a variant of the 3PC framework proposed in (Richtárik et al., 2022) that supports adaptive or tunable compression level. The authors provided unified analysis based on the 3PC framework and established SOTA convergence guarantees for convex, strongly convex and non-convex objectives, extending the existing theoretical development of the 3PC framework. The new Ada3PC induces the AdaCGD method, which covers several existing methods such as EF21, CLAG, LAG as specially cases, and extends their convergence analysis in the convex case. Numerical results demonstrated the benefits of having adaptive compression level.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Add some discussion of the convex analysis of the bidirectional version of AdaCGD. If the convex cases can also be covered here, the whole picture will be more complete and Table 2 will be better supported.", "broader_impact_concerns": "N/A, a mainly theoretic work ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DNhM6iViyW", "reviewer": "Reviewer_xFzN", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\n\nThe adaptivity mechanism and the proposed algorithm are clearly explained and the theoretical analysis seems correct. Moreover, the results and contributions are clearly compared against some of the related works (tables 1 & 2), although there are still unclear points.\n\n**Weaknesses**:\n- There is a disconnect between the theoretical analysis and the proposed adaptive 3PC method. The theoretical results are mainly derived for the 3PC under almost the same assumptions as in [Richtarik 2022], hence can be seen as an extended analysis to that paper. Then the authors show that the adaptive 3PC is indeed a 3PC compressor with $A_{min}$ and $B_{max}$ parameters and the convergence results boil down to the 3PC results with $A_{min}$ and $B_{max}$ replacing the original A and B parameters. Although, I assume that the actual analysis of the adaptive 3PC would be much more involved and possibly complex, but at least the authors should devote some discussions to how the adaptiveness actually affects the convergence.\n- The other issue is the simulations. Some details are missing, the setup is very simplistic and the results actually doesn't show AdaCGD is superior to e.g., CLAG.\n\n(minor issue, not affecting the evaluation) It is worth noting that the AdaCGD requires the actual gradient of the functions, hence it is not clear whether in more practical scenarios where only an estimate of the gradient is available, the proposed algorithm works or have comparable convergence rate.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes an adaptive variant of the 3-point compression [Richtarik 2022]. The proposed adaptive scheme is essentially an extension of the LAG mechanism to m 3PC compressors accompanied with corresponding condition functions as follows: the adaptive 3PC sequentially checks the conditions and uses the first 3PC compressor whose corresponding condition function is satisfied. For the case of AdaCGD, the condition function can be interpreted as a measure of compression error.\nThe authors provided a new theoretical analysis for the convergence rate of 3PC, as well as bidirectional 3PC (i.e., both workers and server use compresses their data). Since adaptive 3PC can be interpreted as a more general 3PC, the convergence results of 3PC are readily extended to the adaptive 3PC and AdaCGD. Finally, they used a simple logistic regression problem over LIBSVM datasets to compare the proposed algorithm with EF21, LAG, CLAG, and GD.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. How the theoretical analysis of the paper for 3PC compares w.r.t, [Richtarik, 2022], e.g., theorems 5.5 and 5.8\n2. The experimental results actually show that AdaCGD is worse than CLAG and EF21 on *a1a* and *a9a* datasets, and better than *phishing* dataset by a relatively small amount. Hence, the extra computations by AdaCGD does not necessarily translate to better convergence rate or fewer communication bits.\n3. How that $\\zeta$ affects the algorithm? Intuitively, larger values make AdaCGD behave like CLAG. Does this actually happens in practice, i.e., AdaCGD mostly uses the first 3PC compressor?\n4. How the algorithms compare in the convex setting, e.g., setting $\\lambda=0$ in the experiments. \n5. It would be better to give the experiments' details in the main part, not the appendix, e.g., \n\t- what is GD-x1 algorithm. (not mentioned even in the appendix)\n\t- what does '-xN' stands for in the legend of the figures.", "broader_impact_concerns": "there is no concern on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dchlUZ2mjt", "reviewer": "Reviewer_NXKS", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think it is interesting to consider adaptive variants of biased compression schemes. The paper is relatively well-written. However, this paper has significant issues and requires substantial work. I do not think the paper is ready for publication. \n\n-----\n\nMy major concern is that several closely related work have not been cited/compared (Zhang et al., 2017; Wen et al., 2017; Wang et al., 2019; Guo et al., 2020; Faghri et al., 2020; Zhong et al, 2021; Agrawal et al., 2021; Alimohammadi et al., 2022). This is really unfortunate that all those work are ignored. Adaptive compression has been studied extensively in various scientific/engineering areas. In distributed ML, adapting the communication frequency in local SGD, adapting the number of quantization levels, and adaptive quantization levels/sparsification have been studied extensively (Wang et al., 2019; Guo et al., 2020; Faghri et al., 2020;  Agrawal et al., 2021; Alimohammadi et al., 2022). In particular, the authors should properly (algorithmically, theoretically, and empirically) compare with the previous work that proposed adaptive quantization levels and sparsification .\n\n\nHantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In International Conference on Machine Learning (ICML), 2017.\n\nWei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. TernGrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems (NeurIPS), 2017.\n\nJianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error- runtime trade-off in local-update SGD. In Proceedings of Machine Learning and Systems (MLSys), 2019.\n\nJinrong Guo, Wantao Liu, Wang Wang, Jizhong Han, Ruixuan Li, Yijun Lu, and Songlin Hu. Accelerating distributed deep learning by adaptive gradient quantization. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020.\n\nFartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M. Roy, and Ali Ramezani-Kebrya. Adaptive gradient quantization for data-parallel SGD. In Advances in Neural Information Processing Systems (NeurIPS), 2020.\n\nYuchen Zhong, Cong Xie, Shuai Zheng, and Haibin Lin. Compressed communication for distributed\ntraining: Adaptive methods and system. arXiv preprint arXiv:2105.07829, 2021.\n\nSaurabh Agarwal, Hongyi Wang, Kangwook Lee, Shivaram Venkataraman, and Dimitris Papailiopoulos. Adaptive gradient communication via critical learning regime identification. In Proceedings of Machine Learning and Systems (MLSys), 2021.\n\nMohammadreza  Alimohammadi, Ilia Markov, Elias Frantar, and Dan Alistarh. L-GreCo: An efficient and general framework for layerwise-adaptive gradient compression. arXiv preprint arXiv:2210.17357, 2022.\n\n-----\n\nThe motivation of considering ${\\cal M}^M$ at the server is not very clear. The downlink capacity in communication network is typically significantly more than the uplink. Also the server needs to broadcast only a single vector to all workers. So the additional complexity of compressing at the worker side given much smaller communication load and higher downlink capacity is not clear.  \n\n-----\n\nTuning this LAG-based method is significantly more challenging than unbiased and compressed variants of SGD mainly due to additional hyperparameters like $\\zeta$ and also the bias in compression. I am not sure whether the proposed scheme can be used in practical distributed settings.   \n\n-----\n\nIn the definition of 3PC compressors, $h$, $x$, and $y$ are treated as independent quantities while they are indeed statistically correlated considering e.g., (5). I think A and B obtained from Definition 3 are quite conservative (overestimated) and the corresponding bounds are loose.  The same comment applies to the overestimation of $\\alpha_j$'s in Adaptive 3PC compressor (Section 4.2). Such overestimation will lead to highly suboptimal (in terms of mean squared compression error) but computationally expensive compressor.  \n\n-----\n\nThe analysis based on PL and smoothness assumptions is quite standard. Not sure the emphasis on nonconvex analysis is really needed since such rates are indeed expected. I am curious to understand the additional difficulty of convex and smooth analysis like Theorem 6 compared to similar analyses for LAG and 3PC (simple compression only at workers). \nSome results like Lemma 2 are trivial maybe it is better to put the proof to the appendix.  \n\n-----\n\nThe author should improve presentation of the paper e.g., the paragraph following Definition 1; the notation of compression operator in (2) is different from that of Algorithm 1. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors have proposed a method that adaptively updates the compression scheme and levels during the optimization process, extended their consideration to bidirectional compression, and provided convergence  guarantees in a number of standard settings. They focus on a biased and LAG-based compression and use the estimated $\\alpha_j$'s in 3PC compression to switch among $m$ EF21-based compression outputs. The theory is based on PL and smoothness assumptions, which is standard in optimization. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not think this paper is ready for publication mainly due to significant lack of comparison with related work. The authors should properly (algorithmically, theoretically, and empirically) compare with the previous work that proposed adaptive quantization levels and sparsification (detailed comment is provided above). Also the motivation behind bidirectional compression, additional tuning effort, overestimation of  $\\alpha_j$'s in Adaptive 3PC compressor, its mean squared analysis, and difficulty of convex and smooth analysis in the considered setting compared to similar analyses for LAG and 3PC should be carefully addressed. \n\n\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The manuscript can be accepted as-is, but I ask the authors to bring back some of the results from appendix to main body (as suggested by Reviewer xFzN) or, at the very least, clearly mention that there exists datasets where Ada3PC is clearly outperformed by other baselines.
Decision: Accept (poster)