Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
Authors: Bokun Wang
Mher Safaryan
Peter Richtárik
Venue: NeurIPS 2022 Accept (2022)
Keywords: Distributed optimization
smoothness matrices
gradient quantization

Abstract: To address the high communication costs of distributed machine learning, a large body of work has been devoted in recent years to designing various compression strategies, such as sparsification and quantization, and optimization algorithms capable of using them. Recently, Safaryan et al. (2021) pioneered a dramatically different compression design approach: they first use the local training data to form local smoothness matrices and then propose to design a compressor capable of exploiting the smoothness information contained therein. While this novel approach leads to substantial savings in communication, it is limited to sparsification as it crucially depends on the linearity of the compression operator. In this work, we generalize their smoothness-aware compression strategy to arbitrary unbiased compression operators, which also include sparsification. Specializing our results to stochastic quantization, we guarantee significant savings in communication complexity compared to standard quantization. In particular, we prove that block quantization with $n$ blocks theoretically outperforms single block quantization, leading to a reduction in communication complexity by an $\mathcal{O}(n)$ factor, where $n$ is the number of nodes in the distributed system. Finally, we provide extensive numerical evidence with convex optimization problems that our smoothness-aware quantization strategies outperform existing quantization schemes as well as the aforementioned smoothness-aware sparsification strategies with respect to three evaluation metrics: the number of iterations, the total amount of bits communicated, and wall-clock time.

Theoretically Better and Numerically Faster Distributed Optimization with Smoothness-Aware Quantization Techniques
Bokun Wang
Mher Safaryan KAUST, Saudi Arabia mher safarann 10kaust. edu. sa
Texas A&M University, United States*
bokunw. lraanggmmil.com com
Peter Richtárik KAUST, Saudi Arabia
peter reter.rrichtarikkkauuss edu.
Abstract
To address the high communication costs of distributed machine learning, a large body of work has been devoted in recent years designing various compression strategies, such as sparsification and quantization, and optimization algorithms capable of using them. Recently, SSfaryan et al. [202T] pioneered a dramatically different compression design approach: they first use the local training data to form local smoothness matrices and then propose design compressor capable of exploiting the smoothness information contained therein. While this novel approach leads to substantial savings in communication, it limited to sparsification as it crucially depends on the linearity of the compression operator. In this work, we generalize their smoothness-aware compression strategy to arbitrary unbiased compression operators, which also include sparsification. Specializing to stochastic quantization, we guarantee significant savings in communication complexity compared to standard quantization. In particular, we prove that block quantization with n blocks theoretically outperforms single block quantization, leading to reduction in communication complexity by O(n) factor, where is the number nodes the distributed system. Finally, we provide extensive numerical evidence with convex optimization problems that smoothness- quantization strategies outperform existing quantization schemes as well as the aforementioned smoothness- aware sparsification strategies with respect to three evaluation metrics: the number of iterations, the total amount of bits communicated, and wall-clock time.
results
Introduction
Training modern machine learning models is typically cast in terms of (regularized) empirical risk minimization problem and requires increasingly more training data to make empirical risk closer to the true risk (Schmidhuber 2015 Vaswani al. 2019]. This natural requirement makes it harder (and in some scenarios impossible) to collect all data in one place and carry out the training using single data source. As result, we reconciled with flock of datasets disseminated across various compute nodes holding the actual training data [Bekkerman et al. 2011 Vogels et al.) 2019]. However, such divide-and aedee-and-oonuue conquer approach of handling vast amount data means that local updates need to be communicated among the nodes (or through some central server orchestrating the process), which
Work done when the author was research intern KAUST, Saudi Arabia.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

often forms the main bottleneck in modern distributed systems [Zhang et al. 2017 Lin et al., 2018
This issue is further exacerbated by the fact that modern highly performing models are typically overparameterized [Brown et al. 2020 Narayanan et al.) 2021].
1.1. Distributed training. In this paper, consider distributed training formalized the following optimization problem
min f(z) + R(x), where f(x) def 1 Σ fi(x), FER
(I)
im1
and where is the number of parameters of model x E Rd to be trained, is the number of machines/nodes participating in the training, fa)) is the loss/risk associated with the data stored on
machine i E [x]] def {1,2..... n). f(r is the empirical loss/risk, and R(z) is a regularizer.
Because of the communication constraints, large body of work has been devoted in recent years to the design of various compression strategies, such as sparsification [Konečný and Richtárík] 2018
Wangni et al., 2018 Alistarh et al., 2018), quantization [Goodall 1951 Roberts 1962 Alistarh
ct al.
2017]. low-rank approximation |Vogels et al., 2019). three point compressor RRihháárik et al.
2022 and optimization algorithms capable of using them, such as Distributed Compressed Gradient
Descent (DCGD) [Khirirat et al. 2018), QSGD [Alistarh et al. |
Faghri et al., 2020]. NUQSGD
Gramezani-Keble et al. 2021]. DIANA [Mischeenko al. [2019]]Hovvas]
al. 2019]. PowerSGD
Vogels et al.J 2019)] SignSGD [Bernstein et al. 2018]] Safaryan and Richtárik] [202]]. intSGD
Mishchenko et al. [221]] ADIAÑA [Li al. 2020]. MARINA [Gorbunov et al. [221]]
1.2. From scalar smoothness matrix smoothness. Typically, distributed optimization algo-
rithms in the literature that employ compressed communication, including all methods from the aforementioned works, use only shallow smoothness information of the loss function such as scalar L-smoothness Nesterov| 2004).
Definition (Scalar Smoothness). Differentiable function e Rdd - R is called s-soooth if there exists non-negative scalar value L 2 such that
(zz) S (gy) + (Vo(y), -)) +1 yl
As pointed out by Safaryan et al. 2021]. smoothness constant L reflects small part of the rich smoothness information often easily available through the training data. In their recent work, Safaryan et al. [2021] pioneered a dramatically different compression design approach. First, they propose to use the local training data form local smoothness matrices, which they claim contain much more useful information than standard smoothness constants.
Definition (Matrix Smoothness). Differentiable function .dd exists symmetric positive semidefinite matrix L > 0 such that
R is called smoohhh if there
Φ(z) < p(v) + (Vl()), y) + 111z - vIl..
Vr, R.VERT Rd.
(3)
Intuitively, the usefulness of L-smoothhess over the standard L-smoothness is the tighter upper bound for functional growth. In other words, if for a function & we have the tightest scalar smoothness L
and the tightest matrix smoothness L parameters, then L= Amax (L) and, hence, upper bound (3) is better than (2). To understand the relationship deeper, consider the functional growth of & along
the direction E Rd (without loss of generality assume ||e]| = 1). Let æ = + te, where t > 0 is
positive scaling parameter, and consider the quadratic terms 5 L of (2) and _ (e. Le) of (3) bounded the functional growth. Obviously, depending on the direction e, the quadratic form (e, Le) can be
much smaller than L Amax (L) sup( (e, Le): |el| =}.
Non-uniform functional growths over different directions hints to design optimization algorithms that are aware of such properties of the objective. Several works randomized coordinate descent have successfully exploited this approach [Richtárik and Takáe 2016 Qu and Richtárik] 2016a b Hanzely and Richtárik 2019 Hanzely and Richtárik 2019]. For example, the "NSyne algorithm of Richtárik and Takáe [016)] uses the smoothness matrix to estimate smaller, so-called ESO (Expected Separable Overapproximation parameters for each coordinate, leading larger stepsizes for the update rule and improved complexity for the algorithm. Note that randomized coordinate descent can be viewed compressed gradient descent with random sparsification (n 1 number of workers).
In the context of distributed optimization, using smoothness matrices L, of all local loss functions fz), i [n). Safaryan et al. [222]] design compressor capable of exploiting the smoothness

---

Table 1: Summary of main theoretical results of this work. Below constants and log factors are
c
hidden, n is the number of nodes, d is the model size, Lmax max; Li, L; = Amax [L),, the expected smoothness constant Lax is defined in (4), the variance of generic compression operator denoted by w. parameters / and are defined in (8) See Table 3 in the Appendix for the notations. We discuss some limitations of the proposed algorithms in Section A.3
Regime
Vi(aa))
arbitrary Vf:(a")
Original Methods
Khirirat 2018
DIANA [Mishchenka al. 2019
lteration Complexity
Communication Complexity
Aiaax
nod + L'max
Standard Quantization (w = O(n))
Redesigned Methods
DCGDs (Algorithm|] with general compresstin
DIANA+ (Algorithm)) with general comprestin up
2
lteration Complexity
Communication Complesity Black Quantization (y ((vZ))
Amoxx
nd + Vind ((13)
Amax
n P
(if v. OCA))
Communication Complexity
d Lamax
Amaa
nd 4 Limax + Amaax (2(3))
Quantization varying steps
Thoorems
2
6
Speedup (up
min(n, d)
min(n,
information contained within the smoothness matrices. In particular, under certain heterogeneity conditions the smoothness matrices L;, their new compressor reduces total communication cost by a factor of O Omin(n, d)).
While this novel approach leads to substantial savings in communication, it is limited to random sparsificution as it crucially depends on the linearity of the compression operator. not clear whether this approach can be useful in the design of other swwothness compression techniques.
2 Summary of Contributions
Motivated by the above mentioned development, in this work, made the following contributions.
2.1. Extending matrix-smootthess-awaa sparsification to general compression schemes. First, we generalize the smoothness- aware sparsification strategy (Safaryan et al. [021] to arbitrary unbi- ased compressors. Instead of sparsification operator, we consider the generic class B (w) of (possibly
randomized) unbiased compression operators C: Rdd + Rd with bounded variance 0, i.e.
E [C(x)] =, E [[[C(x) - =1| S w||+||? Va E R..
This class is quite broad including random sparsification and various quantization schemes. To benefit from the matrix smoothness information with general compressor C, we propose the following modification in the communication protocol. If a E IRd is the vector to be communicated, instead of applying compressor C directly to z and sending (xx. we compress it by C(L and decompress it by multiplying L/ Overall, the receiver estimates the original x by L tL
2.2. Distributed compressed methods with improved communication complexity. To highlight the appropriateness of our generalization, we redesign two distributed compressed methods- Khirirat et al.) 2018 and DIANA (Mishchenko et al. 2019 effectively utilize both matrix smoothness information and general compression operators leading to new methods, which we call DCGD+ (Algorithm[T I and DIANA+ (Algorithm
2). The key notion we introduce that enables the technical analysis is the following quantity deseribing interaction between compression operator C (w)) and smoothness matrix L ž 0:
L(C,L) def inf (c Ell((=) - = s C| S W (L).
This quantity generalizes the one defined in Safaryan et al. (00T] for sparsification, and provides means for tighter theoretical guarantees (Theorems) and and better compression design.
3

---

2.3. Block quantization. As we are no longer constrained to sparsification to exploit matrix smooth- ness, we consider more aggressive quantization schemes to further reduce the communication cost. Our first extension of standard quantization [Alistarh et al. 2017] is block quantization, where each block allowed to have separate quantization parameter. Notably, we show theoretically that our block quantization with n blocks outperforms single block quantization and saves in communication by factor of (n) for both DCGD+ (Theorem and DIANA+ (Theorem 4 when v O(vd).
2.3. Quantization with varying steps. In our second extension of standard quantization, we go even further and allow all coordinates to have their own quantization steps. This extension turns out to be more efficient in practice than block quantization and provides savings in communication cost by factor of O (mmin(n, d)) for both DCGD+ (Theorem 5) and DIANA+ (Theorem 6).
2.4. Experiments. Finally, we perform extensive numerical experiments using LibSVM data CCang and Lin 2011] and provide clear numerical evidence that the proposed smoothness-awar quantization strategies outperform existing quantization schemes as well the aforementioned smoothness-awan
sparsification strategies with respect to three evaluation metrics: the number of iterations, the total amount of bits communicated, and wall-clock time (see Section and the Appendix).
Smoothness-Aware Distributed Methods with General Compressors
In this section we extend methods DCGD+ and D of Safaryan et al. [202] to handle arbitrary unbiased compression operators. We consider the problem (1) with matrix smoothness assumption for all local losses fi(x) and with strong convexity of loss function f(x).
Assumption (Matrix smoothness). The functions f:: Rd - R are differentiable, convex, lower bounded and L.smooth. Besides, f is L-smooth with the scalar smoothness constant L
def Amax (L).
First, note that lower boundedness of (x) is not needed once L; > is invertible. This part of the assumption is not restriction in applications as all loss function are lower bounded. Regarding the relation between L and L,, notice that [I) implies L = n Σ L, This means that while 1 - L, can serve as a smoothness matrix for f. there might be a tighter estimate, which we denote by L. Clearly, matrix smoothness provides much more information about the loss function than scalars smoothness. However, estimating dense smoothness matrix L could be expensive for problems beyond generalized linear models because of the d² number of entries and lack of closed-form expression. On the other hand, estimating sparse, such as diagonal, smoothness matrix Diag(L' I?? ..... L") should be feasible. Lastly, if L is smoothness matrix (could be dense, diagonal or any structure) of f. then any matrix L < is also a smoothness matrix for f. This implies that our theory would still work if the smoothness matrix is over-approximated.
Assumption 2 (p-convexity). The function f: Rd - R is μ-convex for some > 0, i.e.,
f(x) 2 f()) (Vf(y), v) ~ v112.
Yx,y Rd.
This assumption is rather standard in the literature, sometimes referred to as strong convexity.
3.1. DCGD+ with arbitrary unbiased compression. In our version of DCGD+, each node [M] allowed control its own compression operator C, Bd Bd(w)) independent of other nodes. Denote
def
maxi<ign Li, where L. def L(C,,
Lyxx
(4)
Furthermore, as the compressor C; can be random, denote by C² copy of C, generated at iteration k.
Algorithm DCGD+ WITH ARBITRARY UNBIASED COMPRESSION
1: Input: Initial point d0 E Rdd, step size y > 0, compression operators {CH,..., C.h)
2: on server
3: send = all nodes
4: get compressed updates C. (I, 1/22 ((((t))) from all nodes i E [n]]
5: update the model to A+1 = prox, p h >g where g E L 1/2 c/ (I.""((((>>))

---

Similar to the standard DCGD method, convergence of DCGD+ is linear up to some oscillation neighborhood. However, for the interpolation regime this neighborhood vanishes and the method converges linearly to the exact solution.
Theorem 1, Let Assumptions! copy of compression operator C E (wr,), independently from others. Then, for the step-size
7 and hold and assume that each node E [n]] generates its own
0<1 7 S Lt 3 fumaa
the iterates {x } of DCGD+ (Algorithm 1 satisfy
11 x x²1 S (1 - "Y1)** 1|x00 x=
270
(5)
where of def for all i E [n]), then DCGD+ converges linearly with iteration complexity
E L ) In particular, for the interpolation regime (i.e., V(((=)) = 0
(1 Lmax) mp
log 4
(6)
We show later that the iteration complexity (6 of DCGD+ can be much better than one of DCGD. However, the size of the neighborhood of DCGD+ might be bigger than of DCGD. In case of standard (scalar) smoothness (i.e. L, L,I) the size of the neighborhood would be o²
def 1 Ei= wi ((===' which might be smaller than of. Even though we have
C, we wedmmnx (L,) from the definition of L, it does not imply LLL. 3 w.I. Thus, with matrix- smoothness-awar compression we ensure faster linear convergence at the cost of a possibly larger oscillation radius. This is not issue for the interpolation regime, which can interpolate the whole training data with zero loss. Moreover, next we present an algorithmic solution to remove the neighborhood using the DIANA method.
3.2. DIANA+ with arbitrary unbiased compression. The mechanism allowing to remove the neighborhood in DIANA+ is based on the DIANA method, which was initially introduced for ternary quantization by Mishchenko et al. [2019). and then extended to arbitrary unbiased compression operators by Horváth et al. [2019]. The high level idea is to learn the local optimal gradients fi(")) by estimates uf for all nodes E [n]] in communication efficient manner. Nodes use these estimates u to progressively construct better local gradient estimates gā reducing the variance induced from the compression.
Algorithm 2 DIANA+ WITH ARBITRARY UNBIASED COMPRESSION
1: Input: Initial point x0 Rd, initial shifts uf range(L.) L.) and u 1 E uf. step size parameters y 0 and a >> 0, compression operators {Ck ,C Ck)
2: for each node i = I,..., in parallel do
3: get = from the server and compute local gradient (i
4: send compressed update A = C. (L; 1//2 (V+( -uf))
) to the server
5: update local gradient and shift A L 1/2 A. of = = u 6+1 up + a
6: end for
7: on server
8: get all sparse updates A i E [n] and A - g A + u*
9: update the global model x+1 prox, Ra (a* 7 and global shift to u b+1 u² + AA*
We prove in the Appendix that both iterates x and all local gradient estimates up converge linearly to the exact solution xx and V fa (xx" respectively.
Theorem 2. Let Assumptions 7 and 2 hold and assume that each node i [n] generates its own copy of compression operator C² Bd independently from others. Then, if Wmax max sign Wi 2 converges linearly with iteration complexity
and the step-size y E. Limax DIANA+ (Algorithm
((wmax
+
L Emax log !
P
Notice that the cost of removing the neighborhood is the extra Ow log !) iterations, which negligible in the overall complexity 7 above. Another interesting observation is the second order
5

---

flavor of the gradient learning technique employed by DIANA+. Let, for concreteness, matrices L; be invertible and (- = - (a) for all R (both random sparsification and quantization satisty this). Typically, the learning procedure the original DIANA method, uf +++1 = u aC, (uf V)((x))) can be interpreted as a single step of CGD applied to the problem of minimizing the
convex quadratic function x (u) def 1 ||u fa(*>>)) which changes in each iteration because the gradient changes. In contrast, we observe that the learning mechanism of DIANA+ can be interpreted as a single step of a (damped) Newton's 's method with compressed gradients and with 1/a v/ ( (ut
the true Hessian. Indeed, fix the iteration counter k and denote 4p (u) def 2 ||u (x
Then, the update rule of shifts uf in DIANA+ can be rewritten as k+1 = u aL, C(L ff("))) - a p, c. (V (u,)). This might serve as an extra explanation on why incorporating smoothness matrices properly can improve the performance of first order methods with communication compression.
3.3. Baselines for the original methods. To make the theoretical comparison against DCGD and DIANA more transparent, we fix the following baselines using the standard quantization scheme.
Baseline for DIANA. The iteration complexity of DIANA is T Olw Liax
whiaxr) When nys
applying standard quantization from [Alistrrh et al., 2017], the amount of bits each node commu- nicates is = Os2 svd)= = max(s" sVd) = O since w = min( 52
vdl
max( (Lemma 3.1., Alistarh al. (2017). Thus, the total communication complexity of DIANA is n . O(nd + ndl-max al.max Thus, the optimal total communication complexity DIANA wif
Ond + dLmax) ), which attained when + (n).
Baseline for DCGD. Based the iteration complexity O + w of DCGD (in case ny f((x*) = for all i E [n]), we fix the same level of compression w = O()), which results in Immax) iterations complexity. From the estimate of quantization variance w = min 52 x
(
va we
conclude that O vd should be used. Finally, with this choice of s, each node communicates Oss + svd)= = O ( amount of bits. Thus, total communication complexity (i.e. how many bits flows through the central server) of DCGD is Ö ddlmax)
To compare the proposed methods with these baselines and highlight improvement factors, define parameters v and 1n descríbing local smoothness matrices L, as follows
def En La max:clu T.p
def
EL. Las
VI max;g|]] maxscld T.
(8)
where T. (amax(L,), I Lamax def L. Parameters n] and 11 [1, df describe the level of heterogeneity over the nodes and coordinates respectively. If L; matrices coincide, then v = n and v1 = d. On the other extreme, when the values of L; are extremely non-uniform, we have v < and v << d.
maxiçisn I, and Lay is the jth diagonal element of matrix
Notice that the quantity fmax in (6) and the quantity Wmax + Emax in 7 depend on compression an
operators C applied by the nodes. For the rest of the paper we are going to minimize these quantities with respect the choice of C. in such way minimize total communication complexity of the proposed distributed methods. We specialize compressors C, to two different extensions of standard quantization and optimize with respect compression parameters.
4 Block Quantization
We now present our first extension to standard quantization in order to properly capture the matrix smoothness information. Instead having a single quantization parameter (c.g. number of levels) for all coordinates, here we divide the space Hd into B E [1,2,... d} blocks as IR = gd x 1d x x ds and for each subspace Rd4, 1 E [B] we apply standard quantization independently from
"this can be shown by specializing Theorem 1 or Theorem 2 of Safaryan et al. 2021 to scalar smoothness setup and interpolation regime, namely L, L,I and | Vff((*)] I|l = for all E nt).

---

other blocks with different number of levels st. Thus, for any E [B] we allocate one parameter for 1th block of x E Rdd Hence quantization is applied block-wise: for each block we send the norm ||=||| of the block x' E Rd and all entries within this block are quantized with levels {0. 1 2 "."-.. 1}. In the special case of B 1, we get the standard quantization of Alistarh et al. [2017].
To get rid of the constraints on to be integers, instead of working with the number of levels st, we introduce the size of the quantization step by = 1 and allow them to take any positive values (even si
bigger than 1). Thus, for each block / E [B] we quantize with respect to levels {0, h4 2h,,..
Definition 3 (Block Quantization). For a given number of blocks B [d] and fixed quantization steps h = (hi..... .......,),....... define block-wise quantization operator 0 R + IR as follows:
[
def
||'||| sign(rx)
1r |
where L (1-1)B+ x E Rd, jE [di], E [B] and EI( for v 2 is defined via the quantization
levels {0, h1, ...,... follows: if khy S < (k 1)h for some ls E 1,,1,2.... then
(v(
def
Ahz with probability
1+1- n
(R+1))2
with probability
Note that 0 is an unbiased compression operator as [[)] = v for any 2 0. To communicate
a vector of the form 2 we encode each block [ (z)) E Rd using Elias w-coding as in the standard quantization scheme (Alistarh et al. 2017 Hence, for each block E [B] we need to send O 1 +
Jdl bits and one floating point number for ||z||]- Overall, the number of encoding
Rg bits for 2 (z) (up to constant and log factors) can be given by E + v ) + B. As for the hi
compression noise, we prove in the Appendix the following upper bound for L(2, L):
C( L) I maxicigB hy|] (L)
(10)
where L is the t diagonal block matrix of L with sizes di x dr. Next, we are going to minimize communication complexity of DCGD+ and DIANA+ by optimizing parameters of block quantization.
4.1. DCGD+ with block quantization. We fix the number of blocks B E [d] for all nodes i E [n] and allow each node apply different block quantization operator 2 with quantization steps h4 = (hi.1,.... hg,B). ). To minimize communication complexity of DCGD+, we need to minimize Laax subject to the communication constraint mentioned above. Since Lmax max C(C,, L.). each node i E [n]] can minimize the impact of its own compression by minimizing L(C,, L;) based on local smoothness matrix L, This leads to the following optimization problem for finding optimal values of h2 for each node E [n]]
min maxigien hull Diag(L s.t. EE Vdl B 3, h: > 0, LE [B]. hER
(11)
where 3 is the "budget" of communication: Larger 3 leads to finer quantization levels. Note that the constraint in (IT) depends monotonically from each h4- Therefore, the optimum is at- tained when hull Diag [L."]] is uniform over E [B]. Thus, the solution to this problem is given by ha = L(a) where 8LB 2 uniquely determined by the constraint equal-
ity of ITT as the only positive solution of 82 -6,
dTi 3-B
ar F-B
0, which implies 6,
dT. LTe aT? T0-BY=
d D-B Ti,,, where Tin def Σ Vil Diag(L,))
+ +
If this solution of quantization steps h2 is used by all nodes i E [n]. then show reduction in communication complexity by factor of O(n).
O(Vd) and both v,v are O(L). Then DCGD+ using block quan- tization with B = n blocks, di = (44n)) block sizes for all E [n] and quantization steps hig n,,n/11 | with 3 (d//)) reduces overall communication complexity by factor of (n) compared to DCGD using B single block quantization. Formally, to guarantee s > accuracy, the communication complexity of DCGD+ is O Lanax log 2 which is O(n) times smaller over DCGD.
Theorem 3. Assume
7

---

4.2. DIANA+ with block quantization. For the rate 7 of DIANA+, we need to optimize wmax part of the complexity under the same communication constraint used in III. Since
Lumas rp
maX.g[1] (wi + mnd) S Wmax + Lmax ny
< 2 ma]]
(wi + Li mi)
(12)
we can decompose the problem into subproblems for each node i to optimize Wi + c. with respect to its own quantization parameters hG. Analogously, this leads to the following optimization problem for finding optimal values of h; for each node i E [n]:
ag
min maxigien hu (vā + J Diag(L()1l) 8.1. EE + v KEBB
B B, h1 0, (13)
which can be solved with similar argument as done for (II). Details are deferred to the Appendix.
Theorem 4. Assume n ((vd) and both v, are (1). Then DIANA+ using block quantization
with = n blocks, di = (())u) block sizes for all E [n] and ha, quantization steps (solution to 13) with B = (()))) reduces overall communication complexity by factor of ((n) compared to DIANA using B single block quantization. Formally, to guarantee e > O accuracy, the
L communication complexity of DIANA+ ((nd + VV. Lmaxx ) log 2 which (ignoring n summand in the complexity) is (n) times smaller over DIANA.
5 Quantization with Varying Steps
Our second extension of standard quantization scheme is to allow different quantization steps for all coordinates {1, (1.2..... d}. In other words, for each coordinate j [d] we quantize with respect to .....
levels {0, h,. 2hj..... J. The standard quantization (Alistarh et al. 2017] is the special case when
h = for all j E [d]. where is the number of quantization levels.
Definition 4 (Quantization with varying steps). For fixed quantization steps h = (li,.... ha) E Rd. define quantization operator Qn: Rd + Rd as follows:
[x)()), = || sign(z,)) E, [ x EER j- =1,,.....
where E, is defined via the quantization levels (0, hy, 2h 2....... as in 9
Note that compression operator Qn is unbiased as E [s, [u)] = v for any v 2 0 and is not a special case of block quantization defined earlier. To understand how the number of encoding bits of Qn (œ) depends on / exactly seems challenging, since it depends on the actual encoding scheme (i.e. binary representation of compressed information). Besides, even if we fix binary mapping, the closed form expression of total amount of bits is too complicated to be utilized in the further analysis. We provide
theoretical arguments and clear numerical evidence that || = j=1 hy² is reasonable proxy for the number of encoding bits for compressor Qh.
Assumption 3. For any input vector x E Ed and quantization steps h E Rd, compressed vector Q (I) can be encoded with O(144-11 I1) number of bits.
First, consider the special case when all quantization steps are the same, i.e. h = 1 Then ||- svd recovers the dominant part (provided O (d)) in Ö(s² svd) showing total amount of bits for standard quantization scheme. Second, in the Appendix we present an encoding scheme which (up to constant and log d factors) requires I.. (((((&]lo) + ||A=1|| number of bits in d + 7 d dolog 3, if [0, dl and
expectation to communicate f (x), where (T) def Hg is the binary entropy function. Note that, based on the definition (.. increasing quantization steps hy forces more sparsity in f and hence reduces ||@]|o- Thus, ||0||o and hence e0 (i((=]loo) (notice that (0) = 0) are proportional to |/4 --l Furthermore, we present a numerical experiment which shows that the number of encoding bits (x)x) and | are positively correlated.
Hence, in the further analysis, we fix the number of encoding bits of @x(x) by the constraint | = 3 for some parameter 0. As for the variance induced by the compression operator Qn. we prove the following upper bound for L ((2,, L):
L(Q L) < Diag(L)/l))
(14)
8

---

5.1. DCGD+ with varying quantization steps. Now, we optimize the rate (6) of DCGD+ with respect to quantization steps h, = (hi:a .......,, of compressor 2r, controlled by 1th node for all i E [n]. The term in 6 affected by the compression is Lmax = max4e(n] [(C, L,), which implies that each node E [ni can minimize the impact of its own compression by minimizing [(C,, L,) based on local smoothness matrix Lg Based on the upper bound (14) and communication
constraint given by // || 3 for some 3 > 0, we get the following optimization problem to choose the optimal quantization parameters h2 for node E [n]:
min hER
(L,)
s.t. ||h I| B, h, 0, j [d].
(15)
This problem has the following closed form solution due KKT conditions (see Appendix):
bas B
باحي Line
E [n]. j E [d].
(16)
Las
With this choice of quantization steps save O(min(n, d)) times in communication.
Theorem 5. Assume both v. 1/1 are (1)) and β = O(4n). Then DCGD+ using quantization
with varying steps (25) for all i E [n] reduces overall communication complexity by a factor of Ominn(n, d)) compared to the baseline of DCGD. Formally, the iteration complexity ( can be
which is min(n, d) times smaller than the one for DCGD. As both methods communicate (1/x)) bits per node per iteration, we get min(n, d) times savings in communication complexity.
upper bounded as I + fimaa S
Limua
+ 1) Iewas = O nj
( L-mn + Lumos
5.2. DIANA+ with varying quantization steps. Based on 12 each node e [n] optimizes w, + with respect to its quantization parameters h4, which is equivalent to the problem
Ca ng
min hER
Σj (1 + 4t,) h3, s.t. || = 3, h2 > 0, = [d]
(17)
where Asj def Les/nn. Due to the KKT conditions (see Appendix), we get the following solution
/1+A4
hag
(18)
V++
With this choice of quantization steps we save (min(n, (n, d)) times in communication.
Theorem 6. Assume both v, 1/1 are O(1) and = O(dnn). Then DIANA+ using quantization
with varying steps (18) for all i E [n] reduces overall communication complexity by a factor of Ominn(n, d)) compared to the baseline of DIANA. Formally, the iteration complexity (7) can be
upper bounded Wmax
L
Lmax
<
/2d v Laaax P Bn
Yān
Lmas = O I Lmax
Lanax 1
P
Dit
3
which is min(n,d d) times smaller than the one for DIANA (ignoring negligible term n)).
6 Experiments
6.1. Setup. In this section we present two key experiments. Additional experiments can be found in the Appendix. We conduct range of experiments with several datasets from the LibSVM repository [Chang and Lin 2011] on the fz-regularized logistic regression problem [
min ZERd
E. f((x), f((x) = 1 m Σm log(1 + exp( Sxp(-bb,.AATee + 11
where A are data points sorted based their norms before allocating local workers for the heterogeneity. The experiments are performed on a workstation with Intel(R) Xeon(R) Gold 6246 CPU @ 3.30GHz cores. The gather and broadcast operations for the communications between master and workers are implemented based on the MPI4PY library [Daleín et al. 2005] and each CPU core is treated random seeds for each worker. Due to space limitations, we present only two of our experiments here deferring the remaining experiments along with experimental details in the Appendix.
local worker. For each dataset, we each algorithm multiples times with 5
6.2. Comparison to standard quantization techniques. In our first experiment, we compare smoothness-await DCGD+ and DIANA+ methods with our varying-step quantization technique

---

(quant+) +) to the original DCGD [Khirirat et al. 2018) and DIANA Mishchenko et al. 2019 methods with the standard quantization technique (quant) of Alistarh et al. [2017]. Figure demonstrates
that DCGID+/DIAN++ with quant+ lead to significant improvement in both transmitted megabytes and wall-clock time. An ablation study to disentangle the contributions of exploiting the smoothness
matrix and utilizing varying number of levels can be found in Appendix B
Sob. Caeg
concgrte neb
Inoo 1wd
30-1
10
1044
10
12
1011
Bobll (parts)
Tranonitted Megatyhes
Tranemitee Megasstee
Transniteed Megatyyee
Transmatee Vegatytec
Ice, rwd
cortyos. net
60s, no3
ntc. 1wB
10-
10
3051
11-
16t1
ove
SAkA prewe
10" Thmee
Time
Timee
Timee
Figure 1: Comparison of smoothness-awarr DCGD+/DIANA+ methods with varying-step quantiza- tion (quant+) to original DCGD/DIANA methods with standard quantization (quant). Note that in quant+ workers need send L R and quantization steps h; Rdd to the master before the training. This leads to extra costs in communication bits and time, which are taken into consideration.
6.3. Comparison to matrix-smoothnes-aaare sparsification. Second experiment is devoted to the performance of three smoothness-awarc compression techniques -lock quantization (block quant+) of Section 4 varying-step quantization (quant+) of Section [5] and smoothness-aware sparsification strategy (rand-r+) of |SSataryan al. 2021]_ All three compression techniques are shown to outperform the standard compression strategies by at most (nn) times in theory. For the sparsification, we use the optimal probabilities and the sampling size T d/n as suggested in Section 5.3 of [Safaryan el al. [022]. The empirical results in Figure 2 Lillustrate that the varying-step quantization technique (quant+) is always better than the smoothness-awand sparsification [Safaryan iet al.) 2021], in terms of both communication cost and wall-clock time. Our block quantization technique also beats sparsification when the dimension of the model is relatively high.
WFA 1:0
10F
10
22a
20a
104
10
1244
2044
204
2020
22
22
12"
10" Transmitted Hegabyten
12"
10
30" Traramittec Megsbyton
Tranamitted Megabyyes
Trassr itad Hagubaylss
nil
covtyoe, 6
pña,
wis,
1.0
30a
104
3043
10a
2011
10a
30
20F
10a
122
29"
20P
324
301
Time (aocortb)
Time (scconda)
Time lucoo
Time (a000113
Figure 2: Comparison of three matrix-smmootheess-aye DIANA+ method: strying-step quantization quant+, our variant of block quantization block quant+, and smoothness-aware sparsification rand-7+ of Safaryan et al. 2021
compression techniques employed in
References
Alyazeed Albasyoni, Mher Safaryan, Laurent Condat, and Peter Richtárik. Optimal gradient com- pression for distributed and federated learning. arXiv preprint arXiv:2010.03246. 2020.
10

---

Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems, pages 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances Neural Information Processing Systems (Neur[PS), pages 5977-5987, 2018.
Ron Bekkerman, Mikhail Bilenko, and John Langford. Scaling up machine learning: Parallel and distributed approaches. Cambridge University Press, 2011.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. SignSGD: Compressed optimisation for non-convex problems. In International Conference on Machine Learning (ICML), 2018.
Tom B. Brown et al. Language models are few-shot learners. arXiv preprint arXiv:200..44665, 2020.
Chih ChingChung Chang and Chih-Jen Lin. LibSVM: library for support vector machines. ACM
Transactions on Intelligent Systems and Technology (TIST), 2(3):127,, 2011.
Lisandro Dalcín, Rodrigo Paz, and Mario Storti. MPI for Python. Journal of Parallel and Distributed Computing, 65(9): 1115, 2005.
Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel Roy, and Ali Ramezani- -eerrya. Adaptive gradient quantization for data data-parallel SGD. In Advances in Neural Information Process- ing Systems (NeurIPS), 2020.
W. M. Goodall, Television by pulse code modulation. The Bell System Technical Journal, 30(1): 33-49, Jan 1951. ISSN 0005-8580. doi: 1538272.53 1t001...66......
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. unified theory of SGD: Variance reduc- tion, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Eduard Gorbunov, Konstantin Burlachenko. Zhize Li, and Peter Richtárik. MARINA: faster non- convex distributed learning with compression. In International Conference on Machine Learning (ICML), 2021. arXiv preprint arXiv:2102.07845.
Filip Hanzely and Peter Richtárik. One method rule them all: Variance reduction for data, parameters and many new methods. arXiv preprint arXiv: /905. 1266, 2019.
Filip Hanzely and Peter Richtárik. Accelerated coordinate descent with arbitrary sampling and best rates for minibatches. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pages 304-312. PMLR, 16-18 Apr 2019. URL.http///rooeedingg mlr w.l..press/vBB8 waa.99//hazeelyyl html
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint 1rXiv:194.005115 2019.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv: 1806.088000063 06573, 2018.
Jakub Konečný and Peter Richtárik. Randomized distributed mean estimation: accuracy communi- cation. Frontiers in Applied Mathematics and Statistics, 4(62):1-11, 2018.
Zhize Li. Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning (ICML), 2020.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J. Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. International Conference on Learning Representations (ICLR), 2018.

---

Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik, Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09269, 2019.
Konstantin Mishchenko, Bokun Wang, Dmitry Kovalev, and Peter Richtárik. IntSGD: Floatless compression of stochastic gradients. arXiv preprint arXiv:2102.088344 2021.
Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, and Bryan Catanzaro. Scaling language model training to a trillion parameters using megatron. wttp://wwwwwoeeiiiiiiooooo/ooooo waagliigggnngggg--na sonese--oool--taiiinge 2021.
Yurii Nesterov. Introductory lectures on comvex optimization: a basic course. Kluwer Academic Publishers, 2004.
Zheng Qu and Peter Richtárik, Coordinate descent with arbitrary sampling I: algorithms and complexity. Optimization Methods and Software, 31:829-857, 201
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling II: algorithms and complexity. Optimization Methods and Software, 31:858-8844 2016b.
Ali Ramezani- Ramezani-Kebrya, Fartash Faghri, Ilya Markov, Vitalii Aksenov, Dan Alistarh, and Daniel M. Roy. NUQSGD: Provably communicationn-effcieenn data-parallel SGD via nonuniform quantization. arXiv preprint arXiv:2104. 112222004111111 13818, 2021.
Peter Richtárik and Martin Takáč. On optimal probabilities in stochastic coordinate descent methods. Optim Letr, 10:1233-11 1243, 2016. doi: https://doi.org/10.
wtt..or////1.0/////..... 1007/s1 1590-015-0916-1
Peter Richtárik, Igor Sokolov, Ilyas Fatkhullin, Elnur Gasanov, Zhize Li, and Eduard Gorbunov. 3pe: Three point compressors for communication-effiien distributed training and a better theory for lazy aggregation. 39th International Conference on Machine Learning (ICML), 2022.
L. Roberts. Picture coding using pseudo-random noise. IRE Transactions on Information Theory, (2):145-154, February 1962. ISSN 0096-1000, doi: 10.1109/TIT.1992100577
Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning (ICML), 2021.
Mher Safaryan, Filip Hanzely, and Peter Richtárik. Smoothness matrices beat smoothness constants: Better communication compression techniques for distributed optimization. Advances Neural Information Processing Systems (NeurIPS). 2021.
Jürgen Schmidhuber. Deep learning in neural networks: An overview. In Neural Networks, volume 61, page 85-117, 2015.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and accelerated perceptron. In International Conference Artificial Intelligence and Statistics (AISTATS), 2019.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGI: compression for distributed optimization. In Advances Neural Information Processing Systems (NeurIPS), 2019, arXiv prepring arXiv:1905. 13727.
Practical low-rank gradient
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang, Gradient sparsification for communication- efficient distributed optimization. (NeurIPS), 2018
Advances Neural Information Processing Systems
Hantian Zhang, Jenry 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. International Conference Machine Learning (ICML), 2017.
12


Reviews:
[{"review_id": "vHNSNDE5XE5", "reviewer": "Reviewer_DNd9", "summary": "This paper considers the problem of distributed optimization over a parameter-server framework wherein the information exchanged from the workers to the server at every iteration is compressed to reduce the communication demand. To design better algorithms for this, the authors consider a different assumption on the smoothness structure of the objective function. They utilize the notion of **matrix smoothness** introduced in *Safaryan et al.* To solve the problem $\\text{min}_{\\mathbf{x \\in \\mathbb{R}^d}} f(\\mathbf{x})$, where $f(\\mathbf{x}) = \\frac{1}{n}\\Sigma f_i (\\mathbf{x})$, existing works assume that each local function $f_i$, as well as the global objective $f$, is $L$-smooth. This assumption ignores the heterogeneity in the structure of the local objective functions, and the authors in this paper use **matrix-smoothness** to exploit this heterogeneity for designing compressors at each worker differently and achieve better convergence rates.\n\nScalar $L$-smoothness of a function $\\phi(\\mathbf{x})$ implies that the function curvature in the neighborhood of any point $\\mathbf{x} \\in \\mathbb{R}^d$ in the domain of f can be upper bounded by a quadratic function. In other words, the Bregman divergence with respect to $\\phi$ can be upper bounded by the Euclidean distance (with appropriate scaling), i.e. \n\n$D_{\\phi}(\\mathbf{x}, \\mathbf{y}) \\leq \\frac{L}{2}\\lVert \\mathbf{x} - \\mathbf{y} \\rVert_2^2$.\n\nThe idea behind matrix $\\mathbf{L}$-smoothness for any symmetric positive semi-definite (PSD) matrix $\\mathbf{L}$ is to generalize this upper bound to Euclidean distance in a transformed space, i.e.,\n\n$D_{\\phi}(\\mathbf{x}, \\mathbf{y}) \\leq \\frac{1}{2}\\lVert \\mathbf{x} - \\mathbf{y} \\rVert_\\mathbf{L}^2$.\n\nSince $\\mathbf{L}$ is PSD, its eigenvalue decomposition can be given as $\\mathbf{L} = \\mathbf{U}\\mathbf{\\Lambda}\\mathbf{U}^T$, and hence for any $\\mathbf{z} \\in \\mathbb{R}^d$,\n\n$\\lVert \\mathbf{z} \\rVert_\\mathbf{L}^2 = \\mathbf{z}^T \\mathbf{L} \\mathbf{z} = \\mathbf{z}^T \\mathbf{U}\\mathbf{\\Lambda}\\mathbf{U}^T \\mathbf{z}$, which gives,\n\n$D_{\\phi}(\\mathbf{x}, \\mathbf{y}) \\leq \\frac{1}{2}\\lVert\\mathbf{\\Lambda}^{1/2}\\mathbf{U}^T( \\mathbf{x} - \\mathbf{y})) \\rVert_2^2$.\n\nThat is, this gives us a more refined (as well as generalized over scalar $L$-smoothness) information about the smoothness of the objective function, stating that the Bregman divergence of is upper bounded by the Euclidean distance between $\\mathbf{x}$ and $\\mathbf{y}$ after they have been unitarily transformed into the column space of $\\mathbf{U}$, and each coordinate scaled differently in the transformed space. This **matrix smoothness** characterization of the objective function is a generalization of the scalar smoothness characterization, and its usefulness becomes apparent in designing compressors for the gradients of such functions. \n\nFrom my high-level understanding, this is because of the following reason (I request the authors to correct me if I am mistaken) -- When existing works design compressors for the gradients of functions for which only scalar $L$-smoothness information is known, the usual convergence analysis of the expected suboptimality gap is upper bounded by an expression consisting of the compression error measured in the Euclidean metric, i.e. $\\mathbb{E}\\lVert C(\\mathbf{x}) - \\mathbf{x} \\rVert_2^2$ . This work considers general unbiased compressors $C(\\cdot)$ that satisfy $\\mathbb{E}\\lVert C(\\mathbf{x}) - \\mathbf{x} \\rVert_2^2 \\leq \\omega \\lVert \\mathbf{x} \\rVert_2^2$. Here, $\\omega \\geq 0$ characterizes the expected compression error of $C(\\cdot)$. On the other hand, when the matrix smoothness characterization of objective functions is assumed, since the Bregman divergence is upper bounded by a \"transformed and scaled\" Euclidean distance, in the convergence analysis, the expected suboptimality gap is upper bounded by an expression consisting of the compression error measured in the \"transformed and scaled\" Euclidean metric, i.e. $\\mathbb{E}\\lVert C(\\mathbf{x}) - \\mathbf{x} \\rVert_{\\mathbf{L}}^2$. This \"transformed and scaled\" compression error can be characterized similar to before as, $\\mathbb{E}\\lVert C(\\mathbf{x}) - \\mathbf{x} \\rVert_{\\mathbf{L}}^2 \\leq \\mathcal{L}\\lVert \\mathbf{x} \\rVert_2^2$. Note that: \n\n$\\mathbb{E}\\lVert C(\\mathbf{x}) - \\mathbf{x} \\rVert_{\\mathbf{L}}^2 = \\mathbb{E}\\lVert \\mathbf{\\Lambda}^{1/2}\\mathbf{U}^T(C(\\mathbf{x}) - \\mathbf{x}) \\rVert_2^2 \\leq \\lambda_{max}(\\mathbf{L})\\mathbb{E}\\lVert(C(\\mathbf{x}) - \\mathbf{x}) \\rVert_2^2 \\leq \\lambda_{max}(\\mathbf{L})\\omega \\lVert \\mathbf{x} \\rVert_2^2$.\n\nSo, the matrix smoothness approach yields *clear theoretical benefits* when the \"transformed and scaled\" upper bound coefficient $\\omega \\lambda_{max}(\\mathbf{L})$ is smaller than the \"Euclidean\" coefficient, $\\omega$. I understand this is *not* the only benefit of the matrix smoothness characterization, but an intuitive understanding nevertheless about why it should be better than the existing approaches.\n\nThe authors make use of this fact to propose smoothness-aware distributed methods with general unbiased compressors. They extend existing algorithms -- Distributed Compressed Gradient Descent (DCGD) of *Khirirat et al.* and DIANA *(Mischenko et al.)* and theoretically show benefits in the convergence rate, while also numerically verifying them. They then move on to concrete examples of unbiased compression, specifically non-subtractively dithered quantization. They propose **block quantization** and **quantization with varying steps**, and have solved optimization problems to determine the optimal number of quantization steps for each worker.\n", "questions": "The work is great and has enough theoretical and numerical simulations. However I have several concerns and I would appreciate if the authors addressed them. I would be more than happy to increase my review rating if they are appropriately addressed. They are as follows:\n\n1. The intuition behind the importance of matrix smoothness for compression purposes makes sense. However, in the existing literature, the scalar $L$-smoothness assumption is utilized even in centralized optimization settings in the absence of any compression constraints. Does utilizing the matrix smoothness framework help in improving the convergence rates of uncompressed algorithms in any way? The matrix smoothness assumption was not natural to me after a first reading of this paper, so I resorted to reading the prior work of Safaryan et al. that introduced this notion. Safaryan et al. (https://arxiv.org/pdf/2102.07245.pdf) mention on Page 5 (first paragraph) -- *\"Since the stepsizes and convergence rates of first-order methods depend on the smoothness constant(s) employed, convergence analysis relying on such crude approximation may be significantly suboptimal, and the methods too slow when implemented following the theory.\"* If this is the primary intuition behind the efficacy of matrix smoothness framework, shouldn't it also yield improved convergence rates for centralized optimization settings (without any compression) just because it allows for larger step sizes? The authors are requested to comment on this, and if they agree it is relevant, should probably discuss it somewhere in the paper.\n\n2. In eq. (11) (after line 210), where does the $\\beta$ come from? Although it is mentioned in the table of notations as a pre-specified parameter to which quantization is constrained, it should be introduced somewhere in the main paper as well. Moreover, in line (212), should it be $\\frac{dT_{i,B}^2}{\\beta - B}$ instead of $\\frac{dT_{1,B}^2}{\\beta - B}$ in the last term of the quadratic expression? Furthermore, even if it is a straightforward calculation, please mention how exactly do you arrive at the solution of (11) (perhaps in the appendix somewhere?)\n\n3. In eq. (13), the first term of the objective function is $h_l \\sqrt{d_l}$. This comes from the expression $\\omega =  \\text{min}\\left( \\frac{d}{s^2}, \\frac{\\sqrt{d}}{s} \\right) = \\text{min}\\left( h^2d, h\\sqrt{d} \\right)$. For $h\\sqrt{d}$ to be the minimum, we need $h\\sqrt{d} \\geq 1 \\implies \\frac{1}{h^2} \\leq d$. Also, the constraint requires: $\\Sigma_{l \\in [B]} \\left( \\frac{1}{h_l^2} + \\frac{\\sqrt{d_l}}{h_l} \\right) + B = \\beta$. For a homogeneous setting where all local objective functions are the same $\\mathbf{L}$-matrix smooth, this constraint becomes, $B \\left( \\frac{1}{h^2} + \\frac{\\sqrt{d}}{h} + 1 \\right) = \\beta \\implies \\beta \\leq B (2d + 1)$. Moreover, since in Thm. 5, it is assumed that $\\beta = \\mathcal{O}(d/n)$, does this gives us any indication as to the regimes within which the proposed analysis will hold and the algorithm is provably beneficial? A straightforward answer may not be obvious, but since we already know that $n$ and $d$ cannot be too large (from the **Limitations** section owing to the increase in computational complexity) and the analysis further constrains the regimes where is it provably beneficial, the authors should add the discussion regarding this. On a similar note, the statement of Thm. 6 mentions \"ignoring negligible term $n$\". Is the number of workers ($n$) really negligible -- please justify?\n\n4. In *block quantization*, the vector to be quantized is divided into blocks / subvectors and each block is treated independently, with each block having a (possibly) different quantization resolution. Isn't **quantization with varying steps** just not an extreme case of block quantization where each coordinate is a block by itself? Why does the analysis of *block quantization* simplify to that of *quantization with varying steps* for the choice of parameter $B = d$, where B is the number of blocks? Please justify why a separate analysis is necessary in Sec. 5 for quantization with varying steps.", "limitations": "The authors have adequately addresses the major limitations of this work in Sec. **A.3** of the appendix and I appreciate them adding this section, as computational complexity and memory requirements were a concern in my mind right from the beginning when I started reading this paper and got introduced to the notion of matrix smoothness. I imagine any reader in the audience would have similar concerns and hence Sec. A.3 is appreciated. Perhaps the authors could also add a footnote to the appendix somewhere in the main text of the paper. Apart from this, I have raised my other relevant concerns in **Strengths and Weaknesses** and **Questions** sections of the review. Once again, I would be more than happy to increase my scores if my concerns are addressed satisfactorily.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**: This work heavily relies on the work of *Safaryan et al.* that first proposed the matrix smoothness characterization and demonstrated its utility for random sparsification. Extension to general unbiased compressor is a natural extension to consider. Although the analysis of the proposed method is very similar to *Safaryan et al.*, the contributions are non-trivial. The authors have also clarified this already in Appendices **A.1** and **A.2**, highlighting the differences and the challenges in extending the work of *Safaryan et al.* to general unbiased compressors.\n\n**Quality**: This work is pretty good. The authors have packed in a lot of ideas within 9 pages, which makes the presentation of the paper a little difficult to parse in some portions. Since this work is a generalization of Safaryan et al, some things are often not clear in a first reading. I was not aware of the work of Safaryan et al. and hence, had to go through that paper as well to appreciate this work. Although I understand it is difficult, the readers would appreciate if any paper is as self-contained as possible. Perhaps discuss important ideas like matrix smoothness on which you rely on in the appendix in more detail -- explaining the intuition, etc.  I have also reiterated this point in the *limitations* section of the review. I do have some more technical concerns that I have raised in the **Questions** section of the review.\n\n**Clarity**: Although the work is original and non-trivial, I have several concerns about the presentation of the paper which I have listed below. Mostly they are minor, but I would appreciate if the authors address them.\n\n1. In the abstract, the authors claim, \"... our smoothness-aware quantization strategies outperform existing quantization schemes as well as the aforementioned smoothness-aware sparsification strategies with respect to **all relevant success measures** ...\". \"all relevant success measures\" is an unnecessary phrase. The proposed smoothness aware strategies are not very efficient in terms of **computational complexity of preprocessing at the workers** (something the authors note in the Limitations section in Appendix **A.3**) as well as the memory requirements. The server needs to store the smoothness matrices of each worker separately -- for high-dimensional problems and a large number of workers this can be detrimental as it demands a $\\mathcal{O}(nd^2)$ memory requirement. Perhaps rephrasing sentence to only include the metrics like *number of iterations*, *total amount of bits communicated*, and *wall-clock time* would be better.\n\n2. In the characterization of unbiased compressors after line 73, $y$ is not required in $\\forall x, y \\in \\mathbb{R}^d$.\n\n3. The authors are sometimes inconsistent with their notations. The class of unbiased compressors is denoted as $\\mathbb{B}(\\omega)$, but in lines 85 and 118 for example, they add a superscript in $\\mathbb{B}^d(\\omega)$. The authors are requested to correct such typos.\n\n4. In *Assumption 1*, the authors introduce the smoothness matrices $\\mathbf{L}_i$ of the local loss functions $f_i$, and then state the $\\mathbf{L}$-matrix smoothness of the global average function $f$. It is not clear if $\\mathbf{L}$ is introduced for the first time as the smoothness matrix of the global objective $f$ here. Please mention it if that is the case. If $\\mathbf{L}$ can be obtained from the local smoothness matrices $\\mathbf{L}_i$, the authors are requested to mention that as well.\n\n5. (I am not sure about this) In line 120, is *overparametrized* the correct term? Shouldn't the term *interpolation* be preferred? I guess a problem does not need to be overparametrized to satisfy $\\nabla f_i(\\mathbf{x^*}) = 0$ for all $i \\in [n]$? Please correct me if I am mistaken.\n\n6. (Line 122) (Just a mild suggestion regarding terminology) \" ... we show later that the linear rate of DCGD+ can be much better than one of DCGD...\" -- The convergence rate of an optimization algorithm is a function of the learning rate. The authors do not actually compare the linear convergence rate, but rather, the iteration complexity. Although they can be easily derived from one another, the iteration complexity is specified for a particular choice of learning rate (in this case, the maximum allowable learning rate is $\\frac{1}{L + \\frac{2}{n}\\mathcal{L}_{max}}$). On the same note, in Theorem 2, the rate as a function of step-size $\\gamma$ is not even mentioned in the statement, just the iteration complexity is mentioned. Please ensure consistency in whether you are comparing the convergence rate or the iteration complexity, and ensure uniformity of statements in Theorems 1 and 2.\n\n7. (Lines 159 onwards) -- **Baseline for DCGD** Please mention the theorem/lemma from which the iteration complexity of DCGD, i.e. the expression $\\mathcal{O}\\left( \\frac{L}{\\mu} + \\frac{\\omega L_{max}}{n \\mu} \\right)$. Also, the authors mention, \" ... optimal level of compression variance $\\omega = \\mathcal{O}(n)$\" -- what is meant by \"optimal\" here and how is it derived -- please cite appropriately? Furthermore, the estimate of quantization variance $\\omega = \\text{min}\\left( \\frac{d}{s^2}, \\frac{\\sqrt{d}}{s} \\right)$ is a consequence of the QSGD scheme of Alistarh et al. and the relevant theorem / lemma of that paper should be cited accordingly.\n\n8. (Line 245) \"complicated enough\" --> \"too complicated\"\n\n9. What is $D_f$ in the inequality after the equation in line 591? Is is the Bregman divergence between $x$ and $x^*$ with respect to $f$? Please mention. Could not find it in the table of notations either.\n\n**Significance**: I agree that the work is significant enough for low-to-moderate dimensional optimization problems where the matrix smoothness structure can be exploited. Nevertheless, the domain of communication compression in distributed optimization is often motivated by the communication bottleneck of transmitting high dimensional vectors over a network. Does the proposed framework scale well enough for high dimensional problems? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "rjXdPceThtZ", "reviewer": "Reviewer_SKPB", "summary": "This paper is concerning compressed communication in distributed machine learning.\nSmoothness Matrices by Safaryan et al. make it possible to use compressors with different smoothness information for each node, but the choice of compression function is restricted. This paper proposes a generalized method that allows Smoothness Matrices to be applied to any unbiased compressor below a certain variance. This paper further derives how to improve the existing methods called DCGD and DIANA with the proposed framework. \n\n## Afer author feedback\nConsidering the answers to my questions and other reviewers' question, I raise my score +1 upward. \nI expect the discussion about the assumption viloations to be inculded somewhere in the appendix. \n", "questions": "* Is the idea of multiplying L^{1/2} before and after Compressor a basic common practice? Has it been used in other papers? Or is it first conceived for this paper?\n\n* How strictly must assumptions 1 and 2 be followed when dealing with uncontrolled real data?　Which assumption is more likely to cause practical problems in distributed compression learning when violated?\n", "limitations": "Discussed in aeepndx. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Originality: \n\n\nThe main result extends the new distributed compression learning results proposed last year.\n\nThis paper proposes an algorithm that applies an extended version of Smoothenss Matrices to a broader class of compression (quantization) algorithms, though the reviewer cannot fully understand the technical originality of the main result (the first point in Appendix A.2?). \nIf I correctly understand, the quantization methods applied to DCGD and DIANA are not new. \n\n## Quality: \n\nThe validity of the proofs has not been verified. \nThe technical ingenuity and the main idea are well understood.\nThe correspondence between the claims of the paper and the supporting theorem and experimental results is clear.\n\n\n\n## Clarity: \n\nThe structure of the paper and its arguments are written in an easy-to-understand manner. \nEven a non-expert reviewer (=me) on this topic can understand the technical innovations and results. \n\n\n## Significance: \n\nThe reviewer mainly works on neural data (image) compression models and is not an expert on compression \"communication\" protocols in distributed machine learning. \nThus the reviewer is not confident in accurately evaluating this study in the context of the distributed ML community. \n\nHowever, it is understandable that choosing an appropriate compression model is important to improve the efficiency of distributed compression learning. \nThe original Smoothness Matrices method is restricted to a certain type of compressor, thus the contribution of the paper seems important.  \n\nThe numerical experimental results clearly show advancements brought by the proposed framework. However, the reviewer cannot judge how significant these advancements are.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WnlDgS2PgFr", "reviewer": "Reviewer_dhtX", "summary": "This paper generalizes the smoothness-aware compression strategy to arbitrary unbiased compression. This trick was applied to two existing algorithms, DCGD and DIANA, improving communication complexity. Because it can be applied to any unbiased compression scheme, the quantization was improved further with block quantization and varying steps. ", "questions": "How does the algorithm perform if the smoothness matrix $L$ is unknown (e.g., it takes too long to find it)? If the matrix is wrong, what will happen to the algorithm? \n+ Does the transfer of the matrix $L$ use compression? The matrix $L$ is not sparse, and the size is $d\\times d$, which can take a long time. \n+ The convergence results require $\\nu,$ $\\nu_1$ being $O(1)$. In fact, the numbers can be in the order of $n$ and $d$ for IID data. In the numerical experiments, the data is split after random shuffled. So the number for $\\nu$ and $\\nu_1$ may be too big. It would be interesting to see the performance on heterogeneous data. ", "limitations": "Majors limitations are already listed in the Appendix A.3.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n+ The proposed trick uses local second-order information to compress the gradient, largely improving existing compression techniques' performance.  \n+ The convergence is provided for strongly convex functions under some assumptions. \n\nWeakness\n+ The algorithm requires the smoothness matrix $L$, which may not be easily obtained. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-qeSlI7KQNp", "reviewer": "Reviewer_WNkz", "summary": "The paper extends Safaryan's smoothness-aware compression method to the general unbiased compression method. Meanwhile, the authors propose two non-linear compressors for DCGD+ and DIANA+.\n", "questions": "Could you give the code for reproduction?", "limitations": "The authors have discussed the limitation in the detail.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n1.This paper has a solid theoretical analysis of convergence and communication complexity.\n\n2.Two non-linear compressors are proposed for DCGD+ and DIANA+ and the theoretical results show their good performance.\n\n3.The authors conduct serious experiments to evaluate their method. They are detailed and easy to follow.\n\n\n Weaknesses\n\n1.This paper is an extended paper to Safaryan's, which reduces the significance. \n\n2.Though authors have discussed the technical contribution, the main difficulty of extending to the arbitrary unbiased compression operators seems to be easy to handle.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept