Smoothness Matrices Beat Smoothness Constants: Better  Communication Compression Techniques for Distributed Optimization
Authors: Mher Safaryan
Filip Hanzely
Peter Richtárik
Venue: NeurIPS 2021 Poster (2021)
Keywords: distributed optimization
communication compression
smoothness matrices

Abstract: Large scale distributed optimization has become the default tool for the training of supervised machine learning models with a large number of parameters and training data. Recent advancements in the field provide several mechanisms for speeding up the training, including {\em compressed communication}, {\em variance reduction} and {\em acceleration}. However, none of these methods is capable of exploiting the inherently rich data-dependent smoothness structure of the local losses beyond standard smoothness constants. In this paper, we argue that when training supervised models,  {\em smoothness matrices}---information-rich generalizations of the ubiquitous smoothness constants---can and should be exploited for further dramatic gains, both in theory and practice. In order to further alleviate the communication burden inherent in distributed optimization, we propose a novel communication sparsification strategy that can take full advantage of the smoothness matrices associated with local losses. To showcase the power of this tool, we describe how our sparsification technique can be adapted to three distributed optimization algorithms---DCGD, DIANA and ADIANA---yielding significant savings in terms of communication complexity.  The new methods always outperform the baselines, often dramatically so.

Smoothness Matrices Beat Smoothness Constants: Better Communication Compression Techniques for Distributed Optimization
Mher Safaryan KAUST, Saudi Arabia
Filip Hanzely TTIC, United States fhanzely@gmail.. com
mher safaryan. 10kaust... edu. sa
Peter Richtárik KAUST, Saudi Arabia
peter peter.rrichtarikkkeuuss edu,
Abstract
Large scale distributed optimization has become the default tool for the training supervised machine learning models with large number of parameters and training data. Recent advancements in the field provide several mechanisms for speeding up the training, including compressed communication, variance reduction and acceleration. However, none of these methods is capable of exploiting the inherently rich data-dependent smoothness structure of the local losses beyond stan- dard smoothness constants. In this paper, we argue that when training supervised models, smoothness matrices- snttriics--iffommatioooo.. smoothness constants- can and should be exploited for further dramatic gains, both in theory and practice. In order to further alleviate the communication burden inher- ent in distributed optimization, strategy that can take full advantage local losses. To showcase the power of this tool, we describe how our sparsification technique can be adapted to three distributed optimization [Khirirat al. 2018), DIANA [Mishchenko al.) 2019) and ADIANA (Li et al.) significant savings in terms of communication complexity. The new methods always outperform the baselines, often dramatically so.
generalizations of the ubiquitous
propose novel communication sparsification
the smoothness matrices associated with
Introduction
With the desire to build and train high quality machine learning models comes an increased appetite for larger models, both in terms of the number of parameters encoding them, and in the amount of data required train them. In the big data regime, the data partitioned among many parallel machines, which then cooperatively train single global model, usually orchestrated by a central server. Distributed training is cast as the distributed optimization problem
min f(x) + R(x), Z
=<x) = - f(x),
(1)
where d is the number of parameters of model x e Fd is the number of machines participating in the training, f((x) is the loss associated with the data stored on machine i E [m] == {1, 2, n..
f() is the empirical loss, and R(x) is a regularizer. Ample research over the past two decades
has shown that first-order methods are highly scalable and as a result are the methods of choice for distributed optimization problems [Liu and Zhang 2020). In particular, substantial amount of work
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

has been devoted to speeding up the training process by developing efficient methods empowered with techniques such as compressed communication, variance reduction and acceleration.
Compressed communication. In distributed training, compute nodes have to communicate with each other, often via a central server, in order be able to maintain consensus and jointly train global model. However, communication of the information pertaining to local progress, which is typically contained in gradient(s) distilled from local data, is almost invariably the key bottleneck in distributed training systems [Xu et al. 2020]. One popular way to address this issue is to reduce the number of bits encoding the vector/tensor to be transferred via the help of a lossy compression operator. Numerous umbiased gradient compression operators have been proposed for this purpose, including several types of sparsifications [Wang al. [0018 Mishchenko et al., |020 Allisarrh et al.,
2018) and quantizations Alistarr et al. 2017 Zhang et al. 2018
et al. 2019a Wu et al.
Variance reduction. A marked issue that needs to be addressed by successful distributed optimization methods has to do with the (potential) "dissimilarity" of the local loss functions fi,..., ., fn. which in turn is due to the heterogeneity of the training data defining these functions. The higher the dissimilarity, the harder it is for the devices find the minimizer of (T. This issue exists even in the unregularized case (R = 0). Indeed, while in this case 1 E. V(((()) 0 if xt is a minimizer of f. this does not mean that the individual gradients, V=i(""),. J...., f (x*), are all zero. This shows that local gradient information alone is not enough for any node to "realize" thht a solution has been found, which encourages further, in this case unnecessary, iterations. If unaddressed properly, an algorithm is forced to use smaller learning rates, and this leads to unnecessarily slow convergence. On the other hand, when a fixed learning rate is used, the rate is fast, but convergence stops in a potentially large neighborhood of the optimum x=. This issue is exacerbated further by the extra noise coming from gradient compression. Indeed, this noise prevents methods such as Distributed Compressed Gradient Descent (DCGD) [Khirirat et al. 2018 from converging to x² with constant learning rate even in the interpolation regime characterized by the identities (f((=*) = for i. Fortunately, these issues can be resolved via carefully designed variance reduction techniques [Gower itt al. 2020]. In particular, the first variance reduction mechanism for removing the variance coming from compression operators in distributed training is due to Mishchenko et al. [2019]. embodied in their DIANA algorithm. The method was initially analyzed for ternary quantization only [Wen et al., 2017), and later generalized to handle general class of unbiased compression operators |Horváth et al. 2019b Gorbunov et al. 20206).
Acceleration. To speed up distributed training even further, it is often possible to employ Nesterov's acceleration technique [Nesterov] 1983 2004) in concert with gradient compression and variance reduction. For instance, Li et al. 2020 developed the ADIANA method, which adds acceleration on top of a variant of DIANA that relies on the computation of full-batch gradients on all nodes. The resulting method offers provable speedups in convex and strongly convex regimes. Another example is the method ECLK of Qiaa et al. [2020). which employs compressed communication via any (possibly biased) compressor satisfying a certain contraction property in combination with slightly different variance reduction technique known as error compensation (Stich and Karimireddy 2019 Karimireddy et al.; [ while acceleration is offered by loopless variant of the accelerated method Katyusha (Allen-Zhu] 2017 Kovalev et al. 2020].
Further tricks. Numerous other techniques are often used to improve some other aspects of distributed training. including implementing multiple local gradient steps before communication
[ttich] 2020 |Kariireddy et al. 22000] Woodworth et al., 2020a]. asynchronous communication protocols [Agarwal and Duchi
et al. [2015] Recht et al. 2011), in-network aggregation [Sapio et al. (021), and performing the distributed training in decentralized peer-to-peer manner without the reliance on an orchestrating server [Koloskova ct al., 2019 Alghunaim et al., 2019]. However, in this work, we do not explore these directions and focus on the three techniques described before, namely, compressed communication, variance reduction and acceleration.
2 Mining for Smoothness Information
2.1. One size fits all. Arguably, one of the most ubiquitous, if not the most ubiquitous, assumptions used in the literature on first-order optimization methods is that of L-smoothness (Nesterov 2004). A
la case, this neighborhood proportional the voriance of the local gradients at the optimum: 1 Di [V

---

differentiable function ø R + R is said to be L-smooth if there exists constant L N 0 such that yl
(xx) S ((v) + (Vo(x)) x 5)
holds for all z, R.. However, most works in the area of finite-sum distributed optimization use it very crudely: they assume that all local loss functions the same smoothness constant L (Tagg et al. 2019 Woodworth et al. 2020b Stich 2020J. This is crude because much information lost. Indeed, assuming that each fa is L, -moothh it well known that f is --mmoohh with L, satisfying L, S 3 Σ. L, In the light of this, the above assumption is crude as it effectively replaces the values L1 LI...... Ln and Ly with single parameter L satisfying Since the stepsizes and convergence rates of first-order methods depend on
well their average. f -. fi, share
I. 2 max ........ Tm 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.
2.2. "According to the work of their hands" (Lam 3:64). Significant theoretical and practical improvement can often be obtained when taking account of all the smoothness constants involved, avoiding the practice of replacing them all with single crude bound. Such analyses are more rare, but fairly common. For example, [Richtárik and Takac 2016a Hanzely and Richtárik [019a].
2.3. "Like treasure hidden in a field, which starting point of this paper is the observation that there is a hitherto untapped richness of smoothness information that can be used construct better distributed optimization algorithms and obtain better theory. This information is available, but hidden from sight, and is based on the notion of matrix smoothness.
found and covered up" (Mat 13:44). The
Definition (Matrix Smoothness). We say that a differentiable function & Rd - IR is L-smooth there exists symmetric positive semidefinite matrix L = such that
<(x) S <(v) + (Vø(y). - y) 2 1| vll.. Vx,y E Rdd
The standard L-smoothness condition 2 is obtained as special case of B for matrices of the form L = LI, where I is the identity matrix. In particular, if function fi appearing in (T) is often the average loss over the training data stored on node i.e.,
fi(x) +he Em= Dim (Aim
where Aim E Rdi xd is a data matrix, and @im -dd. + R is a differentiable function (c.g., the loss over all but the last linear layer of NN). The following simple result from Qu and Richtárik (2016b), used therein the context of randomized coordinate descent methods, states that if the loss functions aam smooth in the standard scalar sense, then is smooth in the matrix sense. Lemma 1. If each Dim is Aim- -mooth, then the function fr defined in is L--smooth with m. m- dim A Aim.
L
(5)
In cases where the local functions f, are of the form there is lot of potentially useful information contained in the matrix smoothness "constant" L, If we were to use the scalar smoothness constant of f; instead, we would be effectively tossing this richness away, and replacing with L, Amax (L.); the largest eigenvalue of L, This seems wasteful. As we show in this work, it is. However, we offer a fix.
and it is clear this structure is ubiquitous
3 Motivation and Contributions
To the best of our knowledge, none of the current distributed optimization methods, including the methods DCGD Khirirat et al., 2018), DIANA (Mishchenko et al.) (019) and ADIANA [Li et al.) 2020) discussed in Section [ are capable of exploiting the inherently rich data-dependent smoothness structure of the local losses beyond standard smoothness constants. To this effect, we impose the following assumption throughout the paper:
Assumption 1. The functions f:: R + R are differentiable, convex, lower bounded and L;- smooth. Moreover, f is L-smooth with (standard) smoothness constant L Amax (L).
"Our theoretical results hold for general loss functions fa and not assume the structure 'Lower boundedness of fz()) can be dropped if L. > 0 is positive definite. This part of the assumption is not restriction in applications all loss function are lower bounded.
3

---

Table Original and proposed new methods.
ORIGINAL
DCGD
DIANA
ADIANA
NEW
DCGD+
DIANA+
ADIANA+
(ALG
(ALG 2
(ALG
PROXIMAL
DISTRIBUTED
VARIANCE REDUCED
ACCELERATED
X
Table 2: Summary of theoretical results obtained in this work with hidden log _ factors and constants.
Below n is the number of machines, d is the number of parameters of model, L max; Li, L,
Amax (L:) and the expected smoothness constant Lmax is defined in (9). The variance of generic compression operator used in the original methods is denoted by w. In case of sparsification, we have d/- (n) when the expected size of selected coordinates is d/n. Parameters V1, P2 and y describing matrices L, are defined in (3). See Table 6 for further notations.
Regime
V v((=') 0
arbitrary Vf((²))
arbitrary V/((²')
Original
DCGD
DIANA Mishchenko al 2019
ADIANA el al 2020
Methods
Khirirat et al. 2018
Emax
Iteration Complexity
Lemax Whll
Emaxx
Lemax
Emax
Iteration Complexity 4/n
Lmax
Limax
Lmas
New Methods
DCGD+ (Algorithm
DIANA+ (Algorithm 2
ADIANA+
(Algorithm
Exaxx
Iteration Complexity
+ Emaa wp
Wimx + +
Emaa ma
amax
Smmax
knz Emax
Limaz mp
it in Emax
Complexity
'/n
Lynax Lmpax (et u, 1i am (11))
12 + Lmax + Lopax (en, 11 an (11))
noy
Lmax up
(n
3/8
(if
O(1) and Emas/n Olndd
Reference
Theorem
Remark
Theorem
Remark
Theorem Remark
facter tup
Speedup
min(n, d)
min(n, d)
V (mnin(r.d)
vi
nu Eenare and Lemao /uem Daanse/u=Oind" m.b Laxx and Lmnoe/ O(nd?)
In this paper, we argue that when training supervised models, smoothness matrices (see Definition T information-rin generalizations of the classical and ubiquitous smoothness constants can and should be exploited for further dramatic gains, both in theory and practice.
3.1. Unbiased diagonal sketches. We study unbiased diagonal sketches, defined as follows:
Definition 2 (Unbiased diagonal sketch). Let S be random subset of the set of coordinates/features of the model x E Rd we wish to train, i.e., S C [d] =
d). Let be proper, i.e.,
Pj = Prob(j E S) 0 for all coordinates j E [d]. We now define random diagonal matrix (sketch)
C Cs E gdxd via
C = Diag C1 Diag(Ci......cou Ca),
Cj = ={ 1/23 jES. otherwise.
(6)
Note that given vector x (z E Rdd, we have (Cx), = { 2s/ps if jES control the sparsity level of the product Ca by engineering the properties the random set S. Also note that E[Cx] = x for all æ.
if jés So, we can
3.2. Data-dependent sparsification operators. order further alleviate the communication bur- den inherent in distributed optimization, we further propose data deteaddeennentt sparsification operators that can take full advantage the smoothness matrices L; associated with the local losses ʃi- To the best of our knowledge, this is in sharp contrast with the design of all existing tractable compression techniques used in distributed training, which are proposed independently of the training data, and typically based on intuitive information-thewn principles.

---

With each node i we associate an unbiased diagonal matrix C₁ of the form (6.. We use this and the smoothness matrix of f. define a sparsification technique, described next.
Definition 3 (Data-dependent sparsification). In situations when the i-th node wished to communicate local gradient (a))), we ask the node to send the sparse (=compressed) vector C,I."" C.I. f to the server instead. The server then constructs (=decompresses) an unbiased estimator of V (z) as:
(x) C. V((z).
where L, 1//2 denotes the square root of the Moore-Penrose pseudoinverse of L,-
Notable differences of our proposed communication protocol when compared with standard sparsifi- cation techniques are: i) we the smoothness matrix L,, ii) the compressed vector V fi (a) not unbiased, iii) we devise a separate decompression mechanism 7 also involving L;, and this enforces effective unbiasedness.
3.3. Matrik-smoothness-aa -aaaae aware redesign of 3 methods. To showcase the power our approach, we demonstrate how our matrix-smoootness-avve
sparsification technique 7 can be adapted to DCGD, DIANA and ADIANA, in each case leading to significant communication savings. By doing so, show that matrix smoothness can be effectively used to speed up communication compression, variance reduction and acceleration, respectively. This results in three novel methods: DCGD+,
DIANA+, and ADIANA+; see Table 1
3.4. Dramatic improvements in complexity results. We perform complexity analyses for our methods and derive convergence rates under matrix smoothnes (see Assumption 3) and strong convexity assumptions (see Theorems 2 and 4 We show that new methods always outperform the originals/baselinss, and often dramatically so.
To illustrate the potential of our sparsification technique embedded in the new methods, let all machines i E [n] use sketches C; induced by independent samplings S: with probabilities Pay = Prob(j E S²). Then we show that, with optimized probabilities ps:j. DCGD+ can be O (minn(, d)) times faster then DCGD (see Remark 3 and DIANA+ can be (mmin(n, d)) times faster than DIANA (see Remark 4). depending on matrices L;- For the accelerated method, we highlight improvements when condition numbers of subproblems are Ondd)). We show that ADIANA+ can be faster than the original ADIANA by a factor of O(vd) d) in high compression regime, and by factor of O( /min(n, d)) in low compression regime (see Remark 5 Main theoretical results summarized in [
3.5. Single node case. Specializing our theory to the single machine setting (n = 1), we design new non-distributed algorithms providing an alternative viewpoint to randomized coordinate descent methods (see Appendix E).
3.6. Lower bounds. Using matrices as linear compression operators, we further investigate the trade-off between communicated bits and variance induced by the compression (see Appendix F.)
3.7. Experiments. We conduct numerical experiments using LibSVM datasets [Chang and Lin 2011], confirming the effectiveness and superiority of our sparsification protocol (7) over the standard sparsification scheme (see Section and Section C).
4 New Communication-Effiieen Methods Exploiting Matrix Smoothness
Consider the problem T with the smoothness Assumption I and for strongly convex f. Assumption (μ-convexity). f: d + R is y-convex for some μ 0. i.e., for all x, y E Rd f(x) 2 f(y) + (Vf(x), v) + | yl
We present our new distributed methods, redesigned for matrix smoothness, and their convergence guarantees. Each node E [n] generates diagonal sketches C; independently from others via an
'The closest our result work of Hanzely and Richtárik 2019b and their ISEGA method which is able exploit diagonal smoothness matrices. the best our knowledge, we are the first fully exploit smoothness matrices of arbitrary structure, and elevate them as new tool the disposal of algorithm designers.
Sampling S; is called independent if pi:3 = Prob((i.)] C St) Propes for all j. E [d] such that j # L.
5

---

arbitrary sampling S; and, togther with its smoothness matrix Lg, composes the compression matrix C,L, IV Probability matrices P., P, associated with the sampling and sketch C, are defined as
P; (Pag)) P, (Pag))
Past Prob( (1.1) Si), Pist
Pist
(8)
Pris
Next, we introduce the key quantity, Lmax. describing the joint contribution of our sparsification the complexities of the three proposed methods:
Emax maxigign E, Ê, = Amax (P; L,).
(9)
Above, stands for the Hadamard (i.e. element-wise) product.
4.1 DCGD+
We now present our rithm [Khirirat et al. 2018). Upon receiving the current model x from the server, each node
sparsification technique by adapting DCGD algo-
computes L TV V (x*)) based on local training data and smoothness matrix. Next, sparsified up-
dates C L. 2/2 V (a*) are sent back to the server, which then averages decompressed updates L 1/2 C.L 1 fa( and performs proximal step get a new model #+1
Algorithm 1 DCGD+
1: Input: Initial point x0 E IRd, current point o², step size y, diagonal sketch C
2: on server
3: send æ to all nodes
4: get sparse updates C.L. VV from each node
5:
g++ prox,,n(*** ), where g = - Σ= L
With this method we get convergence up to neighhorhood due to compressoin noise.
Theorem (see G.3). Let Assumptions and hold and assume that euch node generates its own diagonal sketch C, independently from others. Define
Σ V f((")) )| Then, for the
step-size 0 < <
the iterates {x*} of Algorithm satisfy
E
|||a x= 11 (1 7P))* 1|x00 x=
270"
(10)
p
4.2 Variance reduction: DIANA+
Next, we apply our sparsification technique to the variance reduced method DIANA MMshhchenko al. 2019 In this method, each node maintains an auxiliary control vector h called shift, which helps to reduce the variance coming from the sparsification. Moreover, the central server keeps track of only the averaged shift R, Then, the model w as well as control vectors h 1/ are updated by decompressing sparse information A using matrices L.
Algorithm 2 DIANA+
1: Input: Initial point v Rdd, initial shifts hi Range(L;), current point * step size parameter
7 and a, sketch C and C = L 2/2 C/C. t1/2
current shifts ......, 1 and h/ 1. Σ Ir.
2: on each node
3: get = from the server
4: send sparse update A C I - ht)
5: update local gradient and shift A
L
1/2 A 9¹ = 1
A o..
6: server
7: get sparse updates A from each node
8:
k Er= A = 1 Σn A
g
A + = Σh с (x* - 1bt) +
9: k+1 p 7, hk-l hh
+ a

---

In this case we get rid of the neighborhood and provide linear convergence to the exact solution x². Throughout the paper, use O notation to ignore log _ factors and constants.
Theorem 3 (sec G.4). Let Assumptions 2 hold and assume that each node generates its own
diagonal sketch C₁ independently from others. Then, for the step-size 7
Algorithm 2
I Lmaxx
guarantees [||2** x= [17] & & after
Wmax +
L 15 +
Emax np
(11)
iterations, where Wmnx maxi W/ and W/ maxis/sa Proj is the variance of compression operator induced by sketch C..
Remark (Variance Reduction: ISEGA+), In Appendix | we apply our redesign to another variance reduced method called ISEGA Mishhhenko al. 2020 Hanzely and Richtárık) 2019b]. At the core of ISEGA, the mechanism for variance reduction is based on SEGA method [Hanzely et al. 2018). The key difference between ISEGA and DIANA is that ISEGA updates the control variates h more aggressively using projection instead of the mere Q-step towards the projection used in DIANA. The method is presented as Algorithm|] 7 in [ppendix Theorem 22 provides the result - we can see that the worst case complexity is identical to DIANA+. However, in terms of the practical performance, we expect ISEGA+ to outperform DIANA+ due to the more aggressive update rule of control variates.
Remark 2 (Variance Reduction with Bi-directional Compression: DIANA++). As an extension to DIANA+, +, in Appendix ! we apply our sparsification technique both for nodes and for the central server, thus compressing gradients in both directions of communication. We develop and analyze DIANA++ (see Algorithmm { for which the central server applies compression in its turn with sketch C independently. To converge in a linear rate, DIANA++ maintains an additional control vector to reduce the variance coming from the master's 's sparsification. Our convergence theory (Theorem 23 recovers the same complexity (T) of DIANA+ if no compression applied by the master.
4.3 Acceleration with variance reduction: ADIANA
Finally, we redesign the accelerated method ADIANA Li et al. smoothness matrices. The algorithm develops four sequences xx* VV ,z*, w²) } of models, which layered via convex combinations, proximal steps and probabilistic assignments. In each iteration, nodes receive models x and w from the server, and send back sparse updates A and of using local data and control vectors h Then, decompressing these sparse vectors with matrices L,, nodes update their shifts h and the server updates all four models along with averaged shift h.F.
2020 to effectively exploit local
Algorithm 3 ADIANA+
1: Input: Initial points x0 = 10 = 00 = w E Rd, initial shifts hς E Range(L,), current point 1//2 current shifts h!...., h
x², parameters y, at 3, 3. 02 02 sketch C and C L/2 C I and htt Σ h
2: on server
3: a = 0 + A + (1 01 02)y send x and w to all nodes
4: on each node
5: send sparse updates A C. (V
h+) and 5% C httt hū +ad
6: update local gradient A - of h + A and shift 8 L y8 h
7: on server
8:
get sparse updates A and of from each node
9:
k 1 Σi= L 1/2 A z² = Σi= L 8%.
g = A +
10:
hb+l = h + ah k+ = prox, (x* - ")
11: g+1 32 + (1 D) 7 (1 x*),, wk1l
y with probubility wet with probability 1-g.
Clearly, ADIANA+ enjoys the accelerated rate, which is strictly better then the one for DIANA+
Theorem 4 (see G.5 own diagonal sketch C, independently from others. Then, the iteration complexity of Algorithm
Let Assumptions 7 and 2 hold and assume that each node generates its
7

---

guaranteeing E [||2* x²113] S E is
Wmax + V /max
Emax jam
if nL S mmax
(12)
Ö Wmax + V +
Wamax /
Lmaxx pm
if nL > Emax.
5
Improvements Over the Original Methods
To compare the proposed methods with originals and highlight improvement factors, we choose independent sampling for all nodes. For Algorithms and samplings based on the complexities we found.
we optimize probabilities of the
5.1. Parameters describing matrices L, Define parameters V. describing local smoothness as
V Σ [a
Σ
I Us == maxie[n)
(13)
max LV
where L, = Amax L.) and 8 1or s 2. Let Lmax = maxisisn L; and Laj be the jth diagonal [1, and Vs [1, [1 describe the distribution
element of matrix L, Note that parameters the nodes and coordinates respectively. If L; are distributed uniformly, then v = n and V, = d. On the other extreme, when the distribution is extremely non-unine unn-frmfrr, have v These parameters are used to highlight the range of iteration complexities new methods can provide.
and vs < d.
5.2. Importance sampling for DCGD+. Let T E [|S..]] E Pi:j be the expected mini-batch size for the samplings S,, where Pay = Ps:jj- Notice that convergence rate of Algorithm depends on mmax = mmxi L, Since each node E [n]] generates its own diagonal sketch C, independently from others, each node can optimize C. Amax (P. L;) independently based on local smoothness matrix Lj. In general, minimizing Amax (P; o L,) with respect to probability matrix P, is hard. However, when each node uses independent sampling, which means Pe:ji Pi:jPel if + 1, then
Amax (P L,) maxisisa
Piu -1) Lejo
(14)
for which we can find the optimal probabilities Pa:j- To minimize the maximum term in (14) we should have (1/2.s La.j = Pt for some p: 2 0. Then the solution
Pig
Lig
(15)
where p. 2 is the unique solution form solution for Pt, it can be computed numerically using one dimensional solvers. Thus, we can efficiently compute the optimal probabilities (15).
Ex=
Las + =. While the latter does not allow closed
Laj
Proposition 5 (Optimality). The independent sampling with probubilities
is the optimal inde-
pendent sampling for the rute (T0
Remark (Improvement over DCGD
Khirirat et al. 2018
With probabilities 75
we show in
Appendix H.I that
Emax AM
(5
M1
Lmax
(16)
In the interpolation regime (i.e. ff(=²) = 0 for all i E [m]). the iteration complexity of DCGD is
Ö(5 -Iams) for general compression operator with variance parameter w. In case of sparsification. known that d/n is the optimal choice under standard (scalar) smoothness assumption Mishhhenno et al. 2019]. If we specialize compression to sparsification with T d/n entries (which gives 4/-
un
n 1-1),
gel O Lemxe ). Notice that, in this regime, Theorem 2 also
provides linear convergence with iteration complexity Ö(4 + Emax) ). Based on 16). is bounded by Õ(CH + Lmps), which is always better than Ö Lunas and can be as small as Ö Lamax Hence, for mini-batch t = d/n, DCGD+ (Algorithm) l guarantees the same Ö (lmmax)) complexity in the worst case, but could provide up to min(n, d) times speedup. An anologous observation can be made between standord sparsificaiton with uniform probabilites and our sparsification with uniform probabilities (see Remark for the details).
minlnn,dyp?
8

---

5.3. Importance sampling for DIANA+ To find optimal probabilities for DIANA+, we minimize
Wmax + Emax
part of the complexity which is in turn equivalent minimize
Lig
1/
Last 1, pm
(17)
Pia
which can be solved the same way as (14) yielding
Paj
Leg
(1+p)amm
(18)
Proposition 6 (Optimality). The independent sampling with probabilities 18) the optima inde- pendent sampling for the complexity (77).
Remark 4 (Improvement over DIANA [Mishchenko et al.
2019
Horváth et al.
2019b]) The
iteration complexity of DIANA, with d/n is O(n + Lunxx ). With probabilities (88 the iteration complexity
we upper bound
m in Appendix H.2 as follows
Wmax
Emax pn
2d
221 Lmax
(19)
P
Therefore, with t = 4/1, DIANA+ (Algorithm guarantees the same Ö(n + Lixx) worst case, but could provide up to min(n, d) times speedup with complexity Ö(n +
complexity the Lmax
min(n,dju
5.4. Independent sampling for ADIANA+. Clearly, if we sparsify with uniform probabilities Paùj 7/d, then Algorithm 3 recovers the of ADIANA.
Remark 5 (Improvement over ADIANA aL. 2020)). To show that the rate could be significantly
better in some cases, consider the following choice Puj t L
Lis2 + 1, where pl
un
determined uniquely from Σí= Pis = т. Then, with these probabilities and for Timan/ //-
Ondd), we show in Appendix H.3 that vLmmax 1/
Wmax O
(22d)
Emax am
=0
and
Liax
Furthermore, assuming both and U2 are ((), choosing
d/n gel
1 S O
Lemax ap
Wmax
O (n), Lmax = =0 (v pLmax
Then, the complexity
12 of ADIANA+ reduces to
attml
Limax 3/4
if Inl.SEuorr
n+
Lmax Lmaax
3/8 nLL> Emar.
up
which, compared to the complexity of ADIANA with w = O(n) compression, gives vd times improvement in the first case and / /min(n, (n, d) times improvement in the second case (ignoring the first summand of the complexities).
Experiments
We numerically compare the proposed seerix--mmoohness--aae sparsification strategy with the usual sparsification scheme. We devise three different experiments on logistic regression with LibSVM data [Chang and Lin 2011]. Due to space limitations, only of them is presented in the main part. Further numerical results alongside with their experimental details are in Appendix C
Proposed and usual sparsification techniques for the 3 distributed methods. We compare six different methods: well-established DCGD, DIANA, ADIANA and our methods DCGD+, DIANA+, ADIANA+, all with uniform sampling for 7 In order to highlight the importance of the variance reduction, in this experiment we choose the starting point to be close to the optimum.
Experiment:
Figure I demonstrates that: i) methods with matrix-aware sparsification (i.e., DCGD+, DIANA+, ADIANA+) outperform their basclines (i.c., DCGD, DIANA, ADIANA) ii) acceleration almost
'I the sense that it minimizes quantity, which is the complexity of DIANA+ up to constant factor.

---

61A
madelor
107
700
Relstive 2ubopt miaatt
Robdiv Subeptmosc
A2MMA
AJVANAI
DOSO-
DCGD+
DCGB
AJMAA
AJURG
ADHANA
DIARA
50500
Coordrabe 5811 sever
conrd sint server
Coorchnaton SENvEr
präshing
10
10"
Relatwe subortmmalty
Rulabve subogttmaa
DuSM
B.MM
DCG21
DCCD1
DCCD
AZAAMA
ADIAN
AZMAA
DIANA
LEARA
AMM
1000
1506
Coarchalss saVe!
Coundr
Figure Comparison of the original methods DCGD [Khirirat al. 2018 DIANA Mishchenko et al. 2019 and ADIANA [Li et al. 2020) with the proposed new methods DCGD+ (Alg. D
DIANA+ (Alg. 2 and ADIANA+ (Alg. 3). All methods use uniform sampling with r
always outperforms the non-accelerated variant, often dramatically so and iii) variance reduction never hurts the convergence, but often stabilizes the oscillation of the non-variance reduced counterpart.
Experiment: Variance reduction with sparsification and importance sampling. We now comment on the experiment illustrated in Figure 2 We examine three sparsification schemes (two variants of strategy and the usual sparsification) and their influence convergence using six different datasets. Considered schemes are i) DIANA+ with importance sampling (18), ii) DIANA+ with uniform sampling, and iii) DIANA with uniform sampling, i.e., uniform sparsification unaware of smoothness matrices, In all three cases we fixed the sampling size 7 = 1.
31a
dubc
madeon
u-Pimm
unformm
unfcmm
1000 2010 2000 0000 500 unform
1003
2000
3010
6000
5032
5003
18003
15400
20035
mushrooms
plashing
xña
Relatvee boptimaltey
307
Bulative beptimatty
122
Valaaiive Saw.aieeellppplllllll
207
2214
22-4
22-4
inpirtance
10"
ieportance
22-1
1003
2000 3000
4000
5002
1002
2000
3200 4020
502e
1200
2000
4000
5000
Coord obcs 2011 S010
Coundratts Sprt screet
Con www.RRaass..ooo SEAE server
Figure 2: Comparison of our sparsification strategy of size using i) importance sampling with probabilities (18). ii) uniform sampling with Pty = à and iii) DIANA [Mishchenko al. 2019] using standard sparsification scheme with uniform sampling. All methods are run with stepsizes as dictated by theory.
for DIANA+ (Algorithm
As expected, conffrms our theoretical findings. First, demonstrates that our sparsification 7 always outperforms the naive/direct sparsification, sometimes by large margin. Second, it shows the benefit of importance sampling (18) over the uniform sampling.
10

---

References
Alekh Agarwal and John Duchi. Distributed delayed stochastic optimization. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Ad- vances in Newral Information Processing Systems, volume 24, pages 873-881. Curran Associates, Inc., 2011. URL https://proceediing neur nwwrneuuuuu..c cwturpp..cc/paee petripp..cc/ppprr/221///12
pdf
Sulaiman Alghunaim, Kun Yuan, and Ali H Sayed. A linearly convergent proximal gradient algorithm for decentralized optimization. In Advances in Neural Information Processing Systems, volume 32, pages 2858. Curran Associates, Inc., 2019. URL https: ptattp::/ppooeeediii //tprc/eeeeiigaa..///e neur http://2.ff.iiisgre222222236aa33
Paper pdf
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 30, pages 1709-176 1020,,0002200 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Neural Information Processing Systems Conf. (NeurIPS), 2018.
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. J. Mach. Learn. Res., 18(1):8194 8244, January 2017. ISSN 1532-4435.
Joseph K. Bradley, Aapo Kyrola, Danny Bickson, and Carlos Guestrin. Parallel coordinate descent for L -rerullrrre loss minimization. In Proceedings of the 28th International Conference on Machine Learning, 2011.
Chih-Chung Chang and Chih-Jen Lin. LibSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 23) 2011.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020a.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Lincarly converging error compensated sgd. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020b.
Robert M. Gower and Peter Richtárik. Randomized iterative methods for linear systems. SIAM J. Matrix Anal. Appl., 36: 1660-1690, 2015.
Robert M. Gower, Mark Schmidt, Francis Bach, and Peter Richtárik. Variance-reduced methods for machine learning. Proceedings of the IEEE, 108(11)11988-999) 2020.
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 Proceediings of Machine Learning Research, pages 304- 312. PMLR, 16-18 Apr 2019a. URL httpp://proceedingg: mlr wwwpspeesseeeee tatess/v89/haane /asp///////a/aaeee/aa
html
Filip Hanzely and Peter Richtárik. One method to rule them all: Variance reduction for data, parameters and many new methods. preprint arXiv:1905.11 1266,, 2019b.
Filip Hanzely, Konstantin Mishchenko, and Peter Richtarik. SEGA: Variance reduction via gradient sketching. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi and R. Gameett editors, Advances in Neural Information Processing Systems, volume 31, pages 2082-2093, Curran Associates, Inc., 2018. URL U wtw.rooeedinns..uuiis....eeeeeee (ece:c4/bb1BBd022227771111111001
pdf
Samuel Horváth, Chen-Yo Yu Ho, Ludovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. CoRR, abs/1905. 10988, May 2019a.
URL http:///axti: //rpiv///rxiv../// org/ abs/1905 10988

---

Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. preprint arXiv:1904.05115, 2019b. 2019b.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signSGD and other gradient compression schemes. In International Conference on Machine Learning, pages 3252-3261. PMLR, 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5132-5143, URL http::/ppoceeddiii mml.iiinnnmm.....m.mmmmmm.mmmr mlr htwp./pppee///11///aaarreeed/ep
PMLR, 13-18 Jul 2020.
html
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. compressed gradients. In arXiv preprint arXiv: ToXiv:/806.00 1806.06573, 2018.
Distributed learning with
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3478-3487. PMLR, 09-15 Jun 2019. URL http:://proceee///////
mlr. press/v97 http:/ooooooooaaaaooooooooao
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those Svrg and katyusha are better without the outer loop. In Aryeh Kontorovich and Gergely Neu, editors, Proceedings of the 31 International Conference on Algorithmic Learning Theory, volume 117 of Proceedings of Machine Learning Research, pages 451 451-467, San Diego, California, USA, 08 Feb-11 Feb 2020. PMLR. URL htll:ttt://prrceedingg mlr. pwwps//v17/kooalleeeeeeeeeee
loops:
html
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtarik. Acceleration for compressed gradient descent in distributed and federated optimization. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Pro- ceedings of Machine Learning Research, pages 5895-5904, PMLR, 13-18 Jul 2020. URL
http:///proceedinga mlr wtt.s/rrrs///111110000000 html
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 2737-2745 Curran Associates, Inc., 2015. URL httpst:::: h/pp::/ed/oso.sssss.oooo nwwrss.euripp...p www.ripp..cpppppr////0//.. pcc/paper/2011//1ee. 3552:0088f001222266777777666fff3
pdf
Liu and Ce Zhang. Distributed Learning Systems with First-Order Methods, volume 9. Foundations and Trends in Databases, 2020. doi: 10.1561/1900000062.
Konstamtin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. In arXiv preprint arXiv: 1901. 100.0999,,,,29,, 2019.
Konstantin Mishchenko, Filip Hanzely, and Peter Richtárik. 99% of worker-master communication in distributed optimization not needed. In Jonas Peters and David Sontag, editors, Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI), volume 124 of Proceedings of Machine Learning Research, pages 979-988. PMLR, 03-06 Aug 2020.
Yurii Nesterov. A method for unconstrained convex minimization problem with the rate of conver- gence 0(1 (1)22). In Doklady AN USSR, volume 269, pages 543-547, 1983.
Yurii Nesterov. Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers, 2004.
Yurii Nesterov. Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM Journal on Optimization, 22:341-362, 2012.
12

---

Julie Nutini, Issam Laradji, and Mark Schmidt. Let's make block coordinate descent go fast: Faster greedy rules, cassaag-passinng active-set complexity, and superlinear convergence. arXiv preprint urXiv:/712.08880 2017.
X. Qian, Peter Richtárik, and Tong Zhang. Error compensated distributed SGD can be accelerated. arXiv: Optimization and Control, 2020.
Zheng Qu and Peter Richtárik. Coordinate descent with arbitrary sampling II: expected separable overapproximation. Optimization Methods and Software, 31:858-8844 2016. doi: 10.1080/ 10556788. 01566788.201..11 190361.
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-800 884, 2016b.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, pages 693-701. Curran Associates, Inc., 2011. URL htttps//ppocceddinggg neurips....... meurips.cc/paper. pdf
Peter Richtárik and Martin Takáč. Iteration complexity of randomized coordccor descent methods for minimizing composite function. Mathematical Programming. 144:1-38 2014.
Peter Richtárik and Martin Takáč. On optimal probabilitties in stochastic coordinate descent methods. Optim Lett, 10: 20:3213-, 2016a. doi: http:///bi.orr//10.00000 159--015-096-.1
Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 356:433-484 201
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication com- pression in distributed and federated learning and the search for optimal compressor. preprint arXiv:2002.08958, 2020.
Amedeo Sapio, Marco Canini, Chen- Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik. Scaling distributed machine learning with in netnewwork aggregation. In The 18th USENIX Symposium on Networked Systems http:////wwwxwwo///////////a//// wttp:/993..0060
Design and Implementation (NSDI '21 Fall), 2021.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2020.
Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv: 1eXXiv:99000 1909.05350, 2019.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. DoubleSqueeza Parallel stochastic gradient descent with double-pass error-compensated compression. In Int. Conf. Machine Learning, 2019.
volume PMLR 97, pages
Hongyi Wang, Scott Sievert, Shengchao Liu, Zachary Charles, Dimitris Papailiopoulos, and Stephen Wright. Atomo: Communication-efficee learning via atomic sparsification. In Advances in Neural Information Processing Systems, 2018
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, page 1509-1519, 2017.
Blake Woodworth, Kumar Kshitij Patel, Sebastian Stich, Zhen Dai, Brian Bullins, Brendan Memahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 1 119 of Proceedings of Machine Learning Research, pages 10334-10343, PMIR, 13-18 Jul 2020a. TtLp: http:://proceedings mlr,
html
13

---

Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs Local SGD for Heteroge- neous Distributed Learning. Advances in Neural Information Processing Systems 33, 2020b.
Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5325-5333, Stockholmsmässann, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http:tt/proccceedingg.e mlr pwwss/v80/ess/ www.///wwwdd... html
Hang Xu, Chen-Ye Yu Ho, Ahmed M. Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Compressed Communication for Distributed Deep Learning: Survey and Quantitative Evaluation. Technical report, KAUST, Apr 2020. URL
http://hdl. handle.. net/10754/662499
Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to end low precision, and little bit of deep learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70, page 4035-4043, 2017.
14

---

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


Reviews:
[{"review_id": "yJcHORu6xOhH", "reviewer": "Reviewer_zeTh", "summary": "This paper proposes a new notion of smoothness called matrix smoothness which leads to better theory bounds and a data-dependent compression scheme. The compression scheme is applied to three existing algorithms resulting in improved convergence bounds in smooth and strongly convex setting. Simple experiments are done to show the effectiveness of the proposed scheme.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The idea of using smoothness matrices to improve convergence bounds as well as perform data-dependent compression seems novel but kind of infeasible for large-scale problems (see next section). Theoretically, the proposed scheme seems to offer a significant speed-up when importance sampling is used. The paper is reasonably well-written. Some comments:\n1) Since you consider strongly convex and smooth objectives, it’d be good to show how much speed-up you get in practice vs. how much you expect theoretically.\n2) Is it possible to give an estimate of the speed-up when you use uniform sampling and not importance sampling?\n3) In Theorem 2 for DCGD+, sigma^{*} can become large if $L_i^{*}$ is poorly conditioned (then the max eigenvalue of its inverse will become large)?\n4) line 195 - typo “compression”\nPlease see my concerns in the next section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have concerns about the feasibility of the proposed method. First, I expect it’d be hard to estimate the matrices $\\mathbb{L}_i$ especially in high-dimensional deep learning settings. Second, modern ReLU networks don’t satisfy smoothness so this method may not be applicable there. It’d be nice to know if it can be extended for non-convex and non-smooth deep learning problems. The proposed compression scheme would probably increase per-client or per-device computation because you need to invert the $L_i$’s. ", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "SO6Mn2X99mf", "reviewer": "Reviewer_WW3C", "summary": "This paper analyzes several optimization concepts: compression, variance reduction, and acceleration, using the assumption of smoothness matrices rather than the smoothness parameter. Sketching matrices are designed as sum_{i\\in S} L^{1/2}_i c_i * L^{1/2,dagger}_i where L_i is the \"smoothness matrix\" associated with the ith data sample. Taking this additional information into account, which for generalized linear models is not too hard to compute, it is suggested that there can be a factor of min(n,d) improvement in unaccelerated methods and sqrt(min(m,n)) benefit in accelerated methods. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This work is interesting, and though the contribution feels incremental, the L_i matrices are indeed not complicated to precompute for most applications. Overall, the writing is fairly clean and the results do seem novel, though it is unclear to me if they are a bit incremental, as it seems to be not that much of an improvement over using leverage scores. \n\nThe one big weakness is that it seems most of the paper is actually in a 50 page appendix, which is not just extra experiments and a few lengthy proofs, but quite a bit of clarifying text and interpretations as well. Moreover many of the proofs pushed to the appendix are short, so it is not the lengthiness of the proofs that is causing such a big appendix. The impact is that while I can check a few pages of the appendix, I cannot reasonably judge all 50 pages in this short review period, nor do I think that is fair compared to the other works that squeezed all the big ideas in the first 8 pages. At the very least, the authors should condense their main story to clearly and succinctly outline how to get their main constant factor improvements. That being said, the parts I was able to read seem reasonable; the proof techniques seem standard and the results follow expected trends. \n\nSpecific critiques:\n - The definition of L_i in (5) should be rank m_i for problems like logistic regression, but could be of higher rank in a neural network model. These two regimes seem a bit separate: sketching should make a big impact in shallow models (like logistic regression) but in the extreme case of m_i = 1, L_i matrix shouldn't be that much more handy than L_i scalar, and it seems that this is somewhat the example shown in the experimental results. On the other hand, a deep model that can overfit may have a more complex L_i. Am I misinterpreting this? Are the experiments using L_i that have more interesting rank? These details should be included in the main paper, not in the appendix. \n\n - Are the results significantly better than using leverage scores? What are the main scenarios where this method would give benefit? \n\n - Can the authors point to a specific scenario where L_i the matrix is giving a significant benefit over L_i a smoothness constant? e.g. give a specific sparsification scheme that is used in practice, or a dataset type with such features in the data matrix? ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "-Qry7NyjwH9", "reviewer": "Reviewer_1hXg", "summary": "The papers consider the standard distributed optimization scenarios, where a server wants to minimize the average of $n$ loss functions, which are evenly distributed across $n$ participating worker nodes. Typically, optimization problems designed for such distributed optimization scenarios assume a blanket smoothness constant for the average and the individual functions involved. Instead, the authors consider the notion of matrix smoothness, where the distance between the points in defining the smoothness is measured with matrix norm (of a smoothness matrix). Under the assumption that the individual loss function satisfies matrix smoothness with different matrices, the authors design compression algorithms using these smoothness matrices and then use them in conjunction with various distributed optimization algorithms. The authors show that as a result of their smoothness-aware compression, they improve over the convergence guarantees of the standard baseline algorithms considered, namely, DCGD, DIANA, ADIANA.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Originality:\n\n  a) The notion of matrix smoothness considered in this paper is a novel one. None of the present distributed algorithms have exploited loss function smoothness to this granularity to the best of my knowledge. As the authors show, this notion can further improve the performance of distributed optimization algorithms.\n\n  b) The compression operator proposed is tailored to the smoothness matrix of the loss function and therefore improves over the performance of generic compression operators proposed in the literature.\n \n c) The distributed optimization algorithms used by the authors seem to only differ in the compression part with respect to the ones present in the literature.\n\nPresentation:\n\na) The paper's presentation is excellent. The introduction clearly mentions the paper's main ideas, contributions, and comparison to prior work.\n\n b) A minor point would be to clarify if the authors introduce the notion of matrix smoothness or was it already present in the literature. (Either way, my review would remain unchanged based on this point, but it will be instructive for the reader.)\n\n\nSignificance: \n\n a) The idea of using smoothness to this granularity is a novel one and can significantly improve the performance of distributed optimization algorithms.  However, it is unclear to me how the precise smoothness matrix could be identified for complicated loss \nfunctions. \n\nb) This work could also inspire other research works to explore other properties of functions to this granularity (e.g., Strong Convexity).\n\nTo summarize, I like this paper and recommend that it be accepted.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors are in general positive agreement as to both the theoretical and empirical contributions of this paper. I would recommend this be accepted.
Decision: Accept (Poster)