Permutation Compressors for Provably Faster Distributed Nonconvex Optimization
Authors: Rafał Szlendak
Alexander Tyurin
Peter Richtárik
Venue: ICLR 2022 Poster (2022)
Keywords: MARINA
distributed training
permutation compressor
correlated compressor
Hessian variance
communication complexity
nonconvex optimization

Abstract: In this work we study the MARINA method of Gorbunov et al (ICML, 2021) -- the current state-of-the-art distributed non-convex optimization method in terms of theoretical communication complexity. Theoretical superiority of this method can be largely attributed to two sources: a carefully engineered biased stochastic gradient estimator, which leads to a reduction in the number of communication rounds, and  the reliance on
 {\em independent} stochastic communication compression, which leads to a reduction in the number of  transmitted bits within each communication round. In this paper we  i) extend the theory of MARINA to support a much wider class of potentially {\em correlated} compressors, extending the reach of the method beyond the classical independent compressors setting,  ii) show that a new quantity, for which we coin the name {\em Hessian variance}, allows us to significantly refine the original analysis of MARINA without any additional assumptions, and iii) identify a special class of correlated compressors based on the idea of {\em random  permutations}, for which we coin the term Perm$K$, the use of which leads to up to $O(\sqrt{n})$ (resp. $O(1 + d/\sqrt{n})$) improvement in the theoretical communication complexity of MARINA in the low Hessian variance regime when $d\geq n$ (resp. $d \leq n$), where $n$ is the number of workers and $d$ is the number of parameters describing the model we are learning. We corroborate our theoretical results with carefully engineered synthetic experiments with minimizing the average of nonconvex quadratics, and on autoencoder training with the MNIST dataset.

Published as a conference paper at ICLR 2022
PERMUTATION COMPRESSORS FOR PROVABLY FASTER DISTRIBUTED NONCONVEX OPTIMIZATION
Rafal Szlendak'
Alexander Tyurin KAUST Saudi Arabia
Peter Richtárik KAUST Saudi Arabia
KAUST
Saudi Arabia
ABSTRACT
We study the MARINA method of Gorbunov al. 202 the current state-of-the- art distributed non-convex optimization method in terms of theoretical communi- cation complexity. Theoretical superiority of this method can be largely attributed to two sources: the use of a carefully engineered biased stochastic gradient esti- mator, which leads to a reduction in the number of communication rounds, and the reliance on independent stochastic communication compression operators, which leads to reduction in the number of transmitted bits within each communication round. In this paper we i) extend the theory of MARINA to support much wider class of potentially correlated compressors, extending the reach of the method be- yond the classical independent compressors setting, ii) show that new quantity, for which we coin the name Hessian variance, allows us to significantly refine the original analysis of MARINA without any additional assumptions, and fii) identify a special class of correlated compressors hased on the idea of random permuta- tions, for which we coin the term PermK. The use of leads O(yn) (resp. 0 d/ vn)) improvement in the theoretical communication complexity of MA- RINA in the low Hessian variance regime when d n (resp. d S n)), where n the number of workers and d is the number of parameters describing the model we are learning. We corroborate our theoretical results with carefully engineered synthetic experiments with minimizing the average of nonconvex quadratics, and on autoencoder training with the MNIST dataset.
INTRODUCTION
The practice of modern supervised learning relies on highly sophisticated. high dimensional and data hungry deep neural network models (Vaswani et al. 2017; Brown et al. 2020) which need to be trained specialized hardware providing fast distributed and parallel processing. Training of such models is typically performed using elaborate systems relying on specialized distributed stochastic gradient methods (Gorbunov et al.) (02I). In distributed learning, communication among the compute nodes is typically a key bottleneck of the training system, and for this reason it is necessary to employ strategies alleviating the communication burden.
1.1 THE PROBLEM AND ASSUMPTIONS
Motivated by the need to design provably communication efficient distributed stochastic gradient methods in the nonconvex regime, in this paper we consider the optimization problem
min -
where n is the number of wotters/macchins/nodee//eeei working in parallel, and fi Rd + IR (potentially noncorvex) function representing the loss of the model parameterized by weights E Rd training data stored on machine i.
'The work of Rafal Szlendak was performed during Summer research internship in the Optimization and Machine Learning Lab KAUST led by Peter Richtárik. Rafal Szlendak is an undergraduate student at the University of Warwick, United Kingdom.

---

Published as a conference paper at ICLR 2022
While we do not assume the functions {fi} to be convex, rely their differentiability, and on the well-posedness of problem (
IR + R are differentiable. Moreover, is lower bounded, ie., there exists fint E R. such that f(x) 2 fint
Assumption 1. The functions fi...., fn
firt for all x E R..
We interested in finding approximately stationary point of the nonconvex problem I That is, we wish to identify (random) vector E Rd such that
E
| S
(2)
while ensuring that the volume of communication between the n workers and the server is as small as possible. Without the lower boundedness assumption there might not be point with small gradient (e.g., think of f being linear), which would render problem 2 unsolvable. However, lower boundedness ensures that the problem well posed. Besides Assumption I smoothness assumption:
we rely on the following
Assumption 2. There exists constant L+ > such that 1 E [Vf()) - Vf(()) S L3 | yl for all z, y E Rd To avoid ambiguity, let L4 be the smallest such number.
While this is somewhat stronger assumption than mere -iipschit continuity of the gradient of (the latter follows from the former by Jensen's inequality and we have L- S L.),, it is weaker than L Li-Liisccitz continuity of the gradient of the functions fi (the former follows from the latter with 2 S A E, LZ). So, this still a reasonably weak assumption.
1.2 BRIEF OVERVIEW OF THE STATE OF THE ART
To the best of our knowledge, the late-of-the-ar distributed method for finding point 4 satisfying (2) for the nonconvex problem (1) in terms of the theoretical communication complexity is the MA- RINA method Gorbunov al. (202T) (see Algorithm MARINA relies on worker-to-see to--eve com- munication compression, and its power resides in the construction of carefully designed sequence of biased gradient estimators which help the method obtain its superior communication complexity.
[T]
Algorithm MARINA
1: Input: starting point x0 stepsize y, probability p E (0, 1], number of iterations T
2: Initialize 8 V (2x))
3: for & = 0, 1,....... T
4: Sample 0₂ Be(p)
5: Broadcast g¹ to all workers
6: for , in parallel do
7: x11
x² rg
8: Set g;
++ (i if and g d + + (VI((tt)))) Vf(x')) otherwise
9:
end for
g ++1
Σm= D
11: end for
Output: ST chosen uniformly at random from k=o
The method uses randomized compression operators C₁ Rdd. + Rd to compress messages (gradient differences) at the workers i E 21,2,... n. before they are communicated to the server. It is assumed that these operators are unbiased, i.e., E [C(()) is bounded as
for all IRd, and that their variance
E [1((()) - =| S w ||a||
for all a E Id and some 2 O. For convenience, let U(w) be the class of such compressors. A key assumption in the analysis MARINA is the independence of the compressors {C,
Forr the purposes of this paper. by communication complexity we mean the product the number com- munication rounds sufficient to find satisfying (2). and suitably detined measure of the volume of commu- nication performed in each round. As standard in the literature, we assume that the workers workers-to-sent to-serv commu- nication is the key bottleneck, and hence we do not count carver-to-worker communication. For more details about this highly adopted and studied setup, see Appendix
2

---

B for more details on Published as a conference paper at ICLR 2022
In partieular, MARINA solves the problem
1
2 in
T = 2 L- + L+
1_ Pu
communication round where A := f(x²) - fint, x0 E R is the initial iterate, E (0, a parameter defining the probability with which full gradients of the local functions [f:] are
communicated to the server, I._ > 0 is the Lipschitz constant of the gradient of f. and L 2 I._ is a certain smoothness constant associated with the functions (fi)-
In each iteration of MARINA, all workers send (at most) pd + (1 - (1- floats to the server in ex- max,sup,es sup (c (v)), where (iz)(C,(v)) is the size of the message v compressed by compressor C. For uncompressed vector we have size(v) = d in the worst case, and if C, is the RandK sparsifier, then (i)) = K. Putting the above together, the communication complexity of MARINA is T(pd (1 p)c), i... the product of the number of com- munication rounds and the communication cost of each round. See Section the method and its theoretical properties.
pectation, where < == max;
An alternative to the application of unbiased compressors is the practice of applying contractive com- pressors, such as Topk (Alistarh et al. 20188), together with an error feedback mechanism (Seide iet al. 2014; Stich et al.) 2018: Beznosikov et al. 2020). However, this approach is not competitive in theoretical communication complexity with MARINA; see Appendix G for details.
1.3 SUMMARY CONTRIBUTIONS
(a) Correlated and permutation compressors. We generalize the analysis of MARINA beyond independence by supporting arbitrary unbiased compressors, including compressors that are corre- lated. In particular, we construct new compressors based on the idea of random permutation (we called them PermK)) which provably reduce the variance caused by compression beyond what inde- pendent compressors can achieve. The properties of our compressors are captured by two quantities, 2 2 0, through a new inequality (which we call "AB inequality") bounding the variance of the aggregated (as opposed to individual) compressed message.
(b) Refined analysis through the new notion of Hessian variance. We refine the analysis of MARINA by identifying new quantity, for which we coin the name Hessian variance, which plays an important role in our sharper analysis. To the best of our knowledge, Hessian variance is new quantity proposed in this work and not used in optimization before. This quantity is well defined under the same assumptions as those used in the analysis of MARINA by Gorbunov et al. (202T).
(c) Improved communication complexity results. We prove iteration complexity and commu- nication complexity results for MARINA, for smooth nonconvex (Theorem + and smooth Polyak- Eojasiewic (Theorem 5) functions. Our results hold for all unbiased compression operators, in- cluding the standard independent but also all correlated compressors. Most importantly, we show that in the low Hessian variance regime, and by using our PermK compressors, we can improve upon the current state-of-the-art communication complexity of MARINA due to Gorbunov et al. (202T) by up to the factor /ni in the d 2 case, and up to the factor 1 + d/ vn in the d S n case. The im- provement factors degrade gracefully as Hessian variance grows. and in the worst case we recover the same complexity as those established by DyGorruooov et al. (202T).
(d) Experiments agree with our theory. Our theoretical results lead to predictions which are cor- roborated through computational experiments. In particular, we perform proof-of-concee testing with carefully engineered synthetic experiments with minimizing the average of nonconvex quadrat- ics, and also test on autoencoder training with the MNIST dataset.
BEYOND INDEPENDENCE, THE POWER OF CORRELATED COMPRESSORS
As mentioned in the introduction, MARINA was designed and analyzed to be used with compressors C, E U(w) that are sampled independently by the workers. For example, the Rand sparsification
1 present their result with T._ replaced by the larger quantity I... However, after inspecting their proof, it is clear that they proved the improved rate we attribute to them here, and merely used the bound I__. < L4 at the end for convenience of presentation only.
+Gorbunov
'The Pf. analysis is included in Appendix D
3

---

Published as a conference paper at ICLR 2022
operator is used by all workers, then each worker chooses the K random coordinates to be commu- nicated independently from the other workers. This independence assumption is crucial for MARINA to achieve its superior theoretical properties. Indeed, without independence, the rate would depend on w instead of 4/n, which would mean no improvement as the number n. of workers grows, which is problematic because w is typically very large. For this reason, independence is assumed in the analysis of virtually all distributed methods that use unbiased communication compression, includ- ing methods designed for convex or strongly convex problems (Khirirat et al. 2018; Mishchenko et al. 2019 Li et al. 2020 Philippenko & Dieuleveut 2020).
In our work we first generalize the analysis of MARINA beyond independence, which provably ex- tends its use to much wider array of (still unbiased) compressors, some of which have interesting theoretical properties and are useful practice.
2.1 AB INEQUALITY: TOOL FOR A MORE PRECISE CONTROL OF COMPRESSION VARIANCE
We assume that all compressors {Ci]2= are unbiased, and that there exist constants A, B > 0 for which the compressors satisfy a certain inequality, which we call "AB inequality", bounding the variance of Σ, Ca(a;) as stochastic estimator of !, E, dg.
Assumption& 3 (Unbiasedness). The random operators C,.....C. IR - R are unbiased, i.e., [C)(a) = a for all i E 2 ,n] and all a E TR
Assumption 4 (AB inequality). There exist constants A, B 2 O such that the random operators C2 C,....,C,
Rd Rd satisfy the inequality
E
1
- a
A
1 Σ [ai11)
B 1
(3)
for all a On E Rd. If these conditions are satisfied, we will write {c: E UUA,
It is easy to observe that whenever the AB inequality holds, it must necessarily be the that A 2 B. Indeed, if we fix nonzero a E TRd and choose a; a for all i, then the right hand side of the AB inequality is equal to A B while the left hand side is nonnegative.
Our next observation is that whenever C, E U(w.) for all i E (1.2...., nn. the AB inequality holds without any assumption on the independence of the compressors. Furthermore, if independence is assumed, the A constant is substantially improved.
Lemma 1. IfC, E U(w,) for E 21, }. then {C,} E U(max; wi, 0). If we further assume that the compressors are independent, then [C, E U max; wi, 0).
In T we provide list of several compressors that belong to the class U(A, B), and give values of the associated constants A and B. While in the two examples captured by Lemma | we had B
intuitively, we should want be as large possible.
2.2 INPUT VARIANCE COMPRESSORS
Due to the above considerations. compressors for which A = B are special, and their construction and theoretical properties are a key contribution of our work. Moreover, as we shall see Section such compressors have favorable communication complexity properties. This leads to the following definition:
Definition (Input variance compressors). We say that a collection (C of unbiased operators form an input variance compressor system if the variance of } E, Ca(a,) is controlled by a multiple of the variance of the input vectors {a,) That is, if there exists constant C 2 O such that
|] S CVar(an........ an
n (a))
-
E
(4)
for all ai, ai....,,, an E Rd. If these conditions are satisfied, we will write (C.) (VC(C)
If (C:) U(A, and B, then (C:) E (V(A).
"This is consequence of the more general analysis from our paper; the case of unhiased compressors without the independence assumption.
paper, Gorbunov et al, 2021 do not consider
4

---

Published as a conference paper at ICLR 2022
Table I: Examples of compressors {C,
(A B). See the appendix for many more.
Compressors
A
B
Calculation of A, B
Reference
C E U(w;)
max; Ws
0
Lemma
standard
C, E U(w;), independent Perm/ (d n); Def
max; Wi
0
Lemma
standard
1
Theorem
new
PermK (d n); Def
Theorem
new
2.3 PERMA: PERMUTATION BASED SPARSIFIERS
We now define two input variance compressors based on a random permutation construction The first compressor handles the d 2 case, and the second handles the d I n case. For simplicity of exposition, we assume that d is divisible by n in the first case, and that n is divisible by d in the second case [ Since both these new compressors established notation RandK and Top for sparsification, we will write Perm for our permutation- based sparsifiers. To keep the notation simple, we chose include simple variants which do offer freedom in choosing K. Having said that, these simple compressors lead to state-of-the-a communication complexity results for MARINA, and hence not much is lost by focusing on these examples. Let e; be the 7th standard unit basis vector in Rd. That is, for any x (#1...., Fd) E RR we have x Σ; 22
sparsification operators, in analogy with the
Definition 2 (PermK for d 2 n), Assume that d 2 and d = where 2 is an integen Let (Fi,..., Td) be a random permutation of {L.....de d}. Then for all x Rd and each i EE (1.2....,N) n} we define
c(z): :
Cn,
(5)
j= 1)+1
Note that C2 is sparsifier: we have (C,())) = n.i if {Tt : + qi} and (x)( 0 otherwise. So, (z) S q == K, which means that C, offers compression by the factor n. Note that we do not have flexibility to choose K; we have = q= = d/n. See Appendix for implementation details.
Theorem 1. The PermK compressors from Definition 2 are unbiased and belong IV(I).
In contrast with the collection of independent RandK sparsifiers, which satisfy the AB incqual- ity with A = d/K-1 and B 0 (this follows from Lemma 1 since w; d/K - 1 for all i), PermK satisfies the AB inequality with A B While both are sparsifiers, the permutation construction behind Perm K introduces favorable correlation among the compressors: we have (a))) = 0 for all i j.
Definition (PermK for n 2 d). Assume that 2 d. n > 1 and n qd. where 2 1 is an integer. where each number occurs precisely q times. Let π = ( Ta) be random permutation of S. Then for all x E Rd and each i (1,2..... ..] we define
Define the multiset == {l...., 1, 1.2............ .....dd.....
C,(x) == dx., Cas
Note that for each i, C₁ from Definition 3 is the Rand1 sparsifier, offering compression factor d. However, the sparsifiers (C are not mutually independent. Note that, again, we do not have a choice of K in Definition Theorem 2. The PermK compressors from Definition 3 are unbiased and belong to IV(A) with 1
have K = 1.
a-d
R-1"
Combining PermK with quantization. It is easy to show that if [C)) E U(A, B), and Q U(w;) are chosen independently of {C, ) (we do not require mutual independence of (Q.)). then
{C, o 2 E U(max; w; 1)A, B) (see Lemma 9). This allows us to combine our compression
techniques with quantization (Alistarh et al. 2017 Horváth et al. 2019
More examples of input variance compressors are given in the appendix.
'The general situation is handled in Appendix
5

---

Published as a conference paper at ICLR 2022
Table 2: Value of L7 in cases when fi(x) 6(x) + (z(x,, where & R - IR is an arbitrary dif- ferentiable function and 6; R + R is twice continuously differentiable. The matrices A, E Rdxd are assumed (without loss of generality) to symmetric. The matrix-valued function L (x. y) defined in Theorem 3
((x)
Φ1(z)
Hessian variance L
any
0 0
any
bi + C2
0
22
A
6,_ +
Amax ( E. A E A))
smooth
sup 2,yEB" .azky
(a-y) (x-))
vll
HESSIAN VARIANCE
Working under the same assumptions on the problem (2 as Gorbunov et (202)) (i.e., As- sumptions [ and and 2 in this paper we study the complexity of MARINA under the influence of new quantity, which we call Hessian variance.
Definition 4 (Hessian variance). Let L 2 0 be the smallest quantity such that
1 Σ IVA(2) -VA()))
1IV - < L3 | vll?, VE
(7)
We refer to the quantity L3 by the name Hessian variance.
Recall that in this paper we have so far mentioned four "smoothness" constants: L; (Lipschitz constant of V fi). L_ (Lipschitz constant of f). 4+ (see Assumption and L (Definition 4. To
avoid ambiguity, let all be defined as the smallest constants for which the defining inequalities hold. In case the defining inequality does hold, the value set to +00. This convention allows us to formulate the following result summarizing the relationships between these quantities.
Lemma 2. L- L4,, L.
L. L2 < Σ Li and L3, L2 L3 L.
It follows that if L; is finite for all i, then L_, L+ and L are all finite as well. Similarly, if L is finite (i.e., if Assumption 2 holds), then I._ and L+ are finite, and L1 S L4. We are not aware of any prior use of this quantity in the analysis of any optimization methods. Importantly, there are situations when L_ large, and yet the Hessian variance L small, or even zero. This important as the improvements we obtain in our analysis of MARINA are most pronounced in the regime when the Hessian variance is small. We also wish to stress that the finiteness of L nor an additional assumption it follows directly from Assumption 2
3.1 HESSIAN VARIANCE CAN BE ZERO
We now illustrate on a few examples that there are situations when the values of L_ and L; are large and the Hessian variance is zero. The simplest such example is the identical functions regime. Example 1 (Identical functions). Assume that fi = f2 -... = fn-
Then L 0.
This follows by observing that the left hand side in 7 is zero. Note that while L+ for L_ and L+ to arbitrarily large! Note that methods based on the TopK compressor (including all error feedback methods) suffer in this regime. Indeed, EF21 in this simple scenario is the same method for any value of n, and hence can't possibly improve as grows. This is because when Topk (a;). As the next example shows, Hessian variance is zero even if we perturb the local functions via arbitrary linear functions.
is possible
a, aj for all j. 1 Σ, TopK n
Example 2 (Identical functions arbitrary linear perturbation), Assume that f((z) ((2) x for some differentiable function Φ Rd TR and arbitrary be E RRd and es R. Then T 0.
This follows by observing that the left hand side in 7 is zero in this case as well. Note that in this example it is possible for the functions {fi) have arbitrarily different minimizers. So, this

---

Published as a conference paper at ICLR 2022
example does not correspond to the overparameterized machine learning regime, and is in general challenging for standard methods.
3.2 SECOND ORDER CHARACTERIZATION
To get an insight into when the Hessian variance may be small but not necessarily zero, we establish a useful second order characterization.
Theorem 3. Assume that for each E (1,2....,n) the function fi is twice continuously differ- entiable. Fix any 2, y E E and define H,(z,)) y) == So V + t(y z)) dt,
H HI,
Hi(z, v). Then the matrices L; y) == Hz( (z == (z, L4 ==
k== Hf v) and Ly(x,y) = L+ (xx v) (z are symmetric and positive semidefinite
Moreover,
L7 sup a.yER4 .
(x- L. (1.
L
sup uyER ..y Ja
(#-v) L (2.z)(vrv1)
||
| レzzツح yly
L3 sup ayy
(m- L. (x,y)(x-)))
L
sup Z.EER ayyy
(a- y) L (x.))aa-)))
While L3 is obviously well defined through Definition even when the functions {fi) are nor twice differentiable, the term "Hessian variance" comes from the interpretation of L in the case of quadratic functions.
Example (Quadratic functions). Let [i(x)) = 1/² A₁T + bj x + 6, where A: E Rdxd are symmetric. Then L = Amax ( E A?- - (1 E. A.)²), where Xmaxx denotes the largest eigenvalue.
Indeed, note that the matrix 1 Σ A variance of the Hessians A An, and L3 measures the size of this matrix in terms of its largest eigenvalue.
CL A.)² can be interpreted as a matrix-valued
See Table 2 for summary of the examples mentioned above. As we shall explain in Section the data/problem regime when the Hessian variance small of key importance to the improvements we obtain in this paper.
4 IMPROVED ITERATION AND COMMUNICATION COMPLEXITY
The key contribution of our paper is more general and more refined analysis of MARINA. In par- ticular, we i) extend the reach of MARINA the general class of unbiased and possibly correlated compressors {C.)" E U(A, B) while ii) providing more refined analysis in that we take the Hessian variance L2_ into account.
Theorem 4. Let Assumptions
2 3 and 4 be satisfied. Let the stepsize in MARINA be chosen as ((A B)I33 BI3). Then after T iterations, MARINA
0 < M. where M I_
finds a random point a 12d for which
|V <
24 7I
In particular, by choosing the maximum stepsize allowed by Theorem MARINA converges in T communication rounds, where T is shown in the first row Table If in this result we replace L by the coarse estimate L3 < L3 and further specialize to independent compressors satisfying C, E U(w) for all i E (1, 2, ... n then since { _ U(w/n, (recall Lemma our general rate specializes to the result of Gorbunov et al. 202TT) which we show in the second row of Table
7 At this point, the authors wish to point out an independent work by Yun et al. 2022) which appeared online shortly after ours. While the problem addressed by Yun et al. (2022) is different, the spirit remains the same improving the performance of method of interest by designing carefully correlated randomness.
7

---

Published as a conference paper at ICLR 2022
Table 3: The number of communication rounds for solving ① 2 by MARINA and EF21.
Method Compressors
T # Communication Rounds
MARINA n {- U(A, B)
o
0
A"
1, +
1-p ((A B) + BL3
(this paper, 2021)
MARINA C, E U(w) and independent
0
4
-- +
1-p I-p ))
Gorbbnov et al. 2021)
E C; are a-Contractive
A
L- -_+ +
14vI-a L+)
[Richtárik al. 2021)
Table Optimized communication complexity of MARINA and EF21 with particular compres- sors.
Communication Complexity
Method + Compressor
nl (Lemma 13
S (Lemma 14
MARINA n PermK
min dl_ d L_ + vn
L
A min dL_, L + L
MARINA n RandK
O
A min dL L+
A min
dL L + Let
EF21 n Top
O A" dl_
A dl
(a) Note, that L_ S L4 and Ls S Ltp
However, and this is a key finding of our work, in the regime when the Hessian variance L3_ is very small, the original result Gorbunov et al. (2027) can be vastly suboptimal! To show this, in Table we compare the communication complexity, i.e., the of communication rounds multiplied by the maximum # of floats transmitted by worker the sever in a single communication round. We compare the communication complexity of MARINA with the RandK and Permy compressors, and the state-of-the-art arror-feedbac. method EF21 of Richtárik et al. (20TT) with the Top com- pressor. In all cases we do not consider the communication complexity of the initial step equal to (d). In each case we optimized over the parameters the methods (c.g., p for MARINA and K in all cases; for details see Appendix D). Our results for MARINA with PermK are better than the competing methods (recall Lemma
4.1 IMPROVEMENTS IN THE IDEAL
VARIANCE REGIME
To better understand the improvements our analysis provides, let us consider the ideal regime char- acterized by zero Hessian variance: I. = O. If we now use compressors {C:) E U(A, B) for which B. which is the case for PermK, then the dependence on the potentially very large quantity L is eliminated completely.
Big model case (d 2 11). this case, and using the PermK compressor, MARINA has communi- cation complexity A" -dfn))) while using the RandK compressor, the communication com- plexity MARINA is no better than OLL A v/).). Hence, we get an improvement by at least the factor /n. Moreover, note that this is nx improvement over gradient descent (GD) (Khaled & Richtárik 2020) and EF21, both of which have communication complexity O 0 dd. In
Appendix M
discuss how can get the same theoretical improvement even if 1 0.
Big data case (d < n). In this case, and using the PermK compressor, MARINA achieves commu- 1") while using the RandK compressor, the communication com- plexity of MARINA is no better than ALLAA" + d/vr)). Hence, we get an improvement by least the factor 1 + d/ /n. Moreover, note that this is a dx improvement over gradient descent (GD) and EF21, both of which have communication complexity O(L-A"=-1
nication complexity
EXPERIMENTS
We compare MARINA using RandK and PermK, and EF21 with TopK, in two experiments. In the first experiment, we construct quadratic optimization tasks with different L to capture the depen- dencies that our theory predicts. In the second experiment, consider practical machine learning
8

---

Published as a conference paper at ICLR 2022
task MNIST (LeCun et al. 2010) to support our assertions. Each plot represents the dependence between the norm of gradient (or function value) and the total number of transmitted bits by a node.
5.1 TESTING THEORETICAL PREDICTIONS ON A SYNTHETIC QUADRATIC PROBLEM
To test the predictive power of our theory in a controlled environment, we first consider synthetic (strongly convex) quadratic function f = ΣΣ Ji composed of nonconvex quadratics fi(a))
2 A x. bi, where b, E IRd A; E Raddd and A; A. We enforced that f is X-strongly convex, i.e., E A, & AI for À > O. We fix À = 1e-6, and dimension d = 1000 (see Fig- ure D. We then generated optimization tasks with the number of nodes n E {10, 1000, 10000) and L E {0, 0.05, 0.1, 0.21, 0.91). We take MARINA's and EF21 's parameters prescribed by the theory and performed a grid search for the step sizes for each compressor by multiplying the theoretical ones with powers of two. For simplicity, we provide one plot for each compressor with the best convergence rate. First, we see that Perm/K outperforms RandKK and their differences in the plots reproduce dependencies from Table | Moreover, when n {1000, 10000} and L+ I 0.21, EF21 with Top has worse performance than MARINA with PermK, while in heterogeneous regime, when L+ 0.91, TopK is superior except when n 10000. See Appendix Afro detailed experiments.
1+ 0:1 1.0
-.05.1 1.0
0.121
0..99
02%, 1.0
1- = 0.9122 A.8
Hombe recees 38000 Rumoor oheee 5000 Novoor 53
Famvi
Permit Thal
Particc 40 Tell
Toal X38
130
1:0
10
52:
330
02
513
530
60
175
tore int
1071/
Arrot add
Aivid
boxic
to
Kosic d22
Auardi1 Topk
Takk >255
Topl:
Figure 1: Comparison of algorithms on synthetic quadratic optimization tasks with nonconvex (.i).
5.2 TRAINING AN AUTOENCODER WITH MNIST
Now we compare compressors from Section 5.1 on the MNIST dataset (LeCun et al. 2010). Our N
current goal is to learn the linear autoencoder, S(D, E) = N Σ DEa; - ail where D E
Rdyx E E Rd a E Rd are MNIST images, d, = 784 is the number of features, de = 16 25088, and compressors send
the size of encoding space. Thus the dimension of the problem at most 26 floats in each communication round since we take n 1000. We use parameter ç to control the homogeneity of MNIST split among n nodes: if P = 1, then all nodes store the same
data, and if p- = O, then nodes store different splits (see Appendix A.5) In Figure one plot for each compressor with the best convergence rate is provided for e- E 10. 0.5, 0.75, 0.9, 1.0). We choose parameters of algorithms prescribed by the theory except for the step sizes, where we performed grid search as before. In all experiments, Perm outperforms RandK. Moreover, we see that in the more homogeneous regimes, when P E {0.9, 1.0). PermK converges faster than TopK. When Ø 0.75, both compressors have almost the same performance. In the heterogenous regime, when p E 0.,0. TopK is faster than PermK, but they both significantly outperform RandK.
Probubl by Ei L0
Probeda By 24 - 0.3
bybubllly 1i E75
Probulekky by lst 0.5
Probube by (i) 0e
Tarit: See Mte 4:25
Bunelt Sto see 33
baret Step site 3235
Fandio Shee star -1
barett See ste -225
0005//1 km
4/ 7
Figure 2: Comparison of algorithms on the encoding learning task for the MNIST dataset.
9

---

Published as a conference paper at ICLR 2022
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication-efficiee SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pp. 1709-1720, 2017.
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning. arXiv preprint wrXiv:2002.124100 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss Gretehen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URL https: httpss///ppcceeeasss.eeeeee neurips cc/papeer/222//ilee 1457c0d6bfcb49.oo 741496771800 8ww.88fffalcc.om 22
pdf
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path integrated differential estimator. In NeurIPS Information Pro- cessing Systems, 2018
Ronald A Fisher and Frank Yates. Statistical tables for biological, agricultural aad medical research. 1938.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated SGD. In 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In 38th International Conference Machine Learning, 2021.
Samuel Horváth, Chen-Yu Ho. L'udovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik, Natural compression for distributed deep learning. arXiv preprint urXiv: 10988, 2019.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. In 36th International Conference Machine Learning (ICML), 2019.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03322 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with com- pressed gradients. arXiv preprint 1.X.vv1880000677. 2018
Donald E. Knuth. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminueriical Algo- rithms. Addison- Wesley Longman Publishing Co., Inc., USA, 1997. ISBN 0201896842.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, 2019.
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available; http:///ww.eeccc.o.o//////////i/
2010.
10

---

Published as a conference paper at ICLR 2022
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradi- ent descent in distributed and federated optimization. In International Conference on Machine Learning. 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal prob- abilistic gradient estimator for nonconvex optimization. In International Conference on Machine PMLR, 2021.
Learning. pp.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning 2019.
with compressed gradient differences. arXiv preprint
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In The 34th International Conference on Muchine Learning, 2017.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous set- tings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint ar0iv:2066. / 14591, 2020.
Xun Qian, Hanze Dong, Peter Richtárik, and Tong Zhang. Error compensated loopless SVRG for distributed optimization. OPT2020: 12th Annual Workshop on Optimization for Machine Learning (NeurIPS 2020 Workshop), 2020.
Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. arXiv preprint #rXiv:2106.05203 2021.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. FedNI.: Making Newton-type methods applicable to federated learning. arXiv preprint arXiv:2106.02969 2021.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- data-parallel distributed training of speech DNNs. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Sebastian Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv: 0tti::99990053300 2019.
Sebastian U. Stich, J.-B. Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS). 2018
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochas- tic gradient descent with double-pass crope-compessteed compression. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6155-6165, Long Beach, California, USA. 09-15 Jun 2019. PMLR. URL http: http:///oooeeeeeinggee ml presss/ 1v97/tang99d.htmm
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, E ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems. volume 30. Curran Asso- ciates, Inc., 2017. URL https:://prooeeddgggg wwwpiiiiiinnnnnnuinngeeeoe nwwrips....... http://eeeene.eeeeeereee.ce/r/rp 33f5e22354 1bt34//ccee Paper. .pdf
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGI: Practical low-rank gradient compression for distributed optimization. In Neural Information Processing Systems, 2019.
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 (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5325-53250 5333, StockholmsmmAsssan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local sgd with shuffling: Tight conver- gence bounds and beyond. In 10th International Conference on Learning Representations (ICLR), 2022.
11

---

Published as a conference paper at ICLR 2022
Appendix
CONTENTS
Introduction
1.1
The problem and assumptions
A brief overview of the state of the art
Summary of contributions
Beyond Independence: The Power Correlated Compressors
2.1
AB inequality: tool for a more precise control of compression variance
2.2
Input variance compressors
2.3
PermA: permutation based sparsilters
3
Hessian Variance
6
Hessian variance can be zero
3,2
Second order characterization
4
Improved Iteration and Communication Complexity
Hessian-variance Improvements in the ideal zero -eoo--Hssia---- variance regime
Experiments
5.1
Testing theoretical predictions on a synthetic quadratic problem
5.2
Training an autoencoder with MNIST
Extra Experiments
14
Experiments setup
14
A.2
Experiment with quadratic optimization tasks: full description
14
A.3
Comparison of MARINA with RandK and MARINA with Perm on quadratic opti- mization problems
14
A.4
Comparison of EF21 with Topk and MARINA with PermK on quadratic optimiza- tion problems
15
A.5
Experiment with MNIST: full description
18
A.6
Comparison of MARINA with RandK and MARINA with Perm/ on MNIST dataset
18
A.7
Comparison of EF21 with Topk and MARINA with PermK on MNIST dataset
19
A.8
Behavior the Hessian Variance Experiments
20
A.8.1
Linear Regression with nodes
20
A.8.2
Local Hessian Varaince MNIST experiments
20
MARINA Algorithm
21
Missing Proofs
22
12

---

Published as a conference paper at ICLR 2022
Proof of Lemmal
22
Proof of Lemmal
22
Proof of Theorem
23
Proof of Theorem
24
Proof of Theorem
24
Proof of Theorem
26
D Polyak-Looasiieen Analysis
29
D.I Proof of Lemma
29
D.2 Proof of Theorem
30
EF21 Analysis
EF21 rate in the non-convex regime
31
EF21 in PL regime
32
Communication Model
34
On Contractive Compressors and Error Feedback
34
G.1 On Contractive Compressors
34
On Error Feedback
35
H
Composition of Compressors with AB Assumption and Unbiased Compressors
36
General Examples of PermK
37
I.I Case d d>1
37
I.2 Case
38
J
Implementation Details of PermK
39
More Examples of Permutation-Base Compressors
39
K.1 Block permutation compressor
39
Permutation of mappings
40
Analysis of Complexity Bounds
43
L.I
Nonconvex optimization
43
L.I.1
Case n d
43
1.2
Case n > d
46
L.2
Pt assumption
47
1.2.1
Case n < d
47
..2
Case > d
48
M Group Hessian Variance
50
13

---

Published as a conference paper at ICLR 2022
A EXTRA EXPERIMENTS
In this section, we provide more detailed experiments and explanations.
A.1 EXPERIMENTS SETUP
All methods implemented in Python 3.6 and run machine with 24 Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHz cores with 32-bit precision. Communication between master and nodes is emulated in machine.
In all experiments, we compare MARINA algorithm with RandK' compressor and Perm compres- and EF21 with TopK. In RandK and TopK, take K [d/n]; show in Lemma [3] that K = =ddnn] is optimal for RandK. For TopK, the optimal rate predicted by the current state- of-the-art theory is obtained when K (however, in practice, Top works much better when K & d). Lastly, we make the pessimistic assumption that L and L3 are equal to their upper
bound Σ 21=1 L..
A.2 EXPERIMENT WITH QUADRATIC OPTIMIZATION TASKS: FULL DESCRIPTION
First, we present Algorithm which is used in the experiments of Section 5.1 The algorithm is designed to generate sparse quadratic optimization tasks where we can control L1 using the noise scale. Furthermore. it can be seen that the procedure generates strongly convex quadratic optimization tasks; thus, all assumptions from this paper are fulfilled to use theoretical results.
Algorithm Quadratic optimization task generation
1: Parameters: number nodes n. dimension d, regularizer X, and noise scale s.
2: for I,...,, do
3: Generate random noises v/ = + of and ut = set i..dd En 2 ~ 10,
4: Take vector b; (-1 v 0/ ......... 0) E 12d
5: Take the initial tridiagonal matrix
A
1/
ddxd
1. -1
-1
6:
end for
7: Take the mean of matrices A 1 - A;
8: Find the minimum eigenvalue Amain A)
"
9: for i == =1 n do
10: Update matrix A, A, + (A Amin (A))
end for
12: Take starting point _ = (Vd. 0,
0)
13: Output: matrices A - ... An, vectors b1. bn. starting point
Homogeneity of optimizations tasks is controlled by noise scale indeed, with noise scale equal to zero, all matrices are equal, and, by increasing noise scale, functions become less "similar" and L grows. In Section 5.1 we take noise scales E {0, 0.05, 0.1, 0.2,
In Figure 3. we provide the same experiments as Section 5.1 but with À 0.0001 to capture dependencies under PL condition. Here, also that Permk has better performance when the number nodes n 2 1000 and L+ S 0.21.
A.3 COMPARISON OF MARINA WITH RANDK AND MARINA WITH PERMK ON QUADRATIC OPTIMIZATION PROBLEMS
In this section, we provide detailed experiments from Section 5.1 and comparisons between RandK
and Perm K using different step sizes (see Figure and Figure We omitted plots where algorithms
14

---

Published as a conference paper at ICLR 2022
dee cot
Figure 3: Comparison of algorithms under PE condition on synthetic quadratic optimization tasks. Each row corresponds to fixed number nodes; each column corresponds to fixed noise scale. In the legends, provide compressor names and fine-tuned multiplicity factors of step sizes relative to theoretical ones. Abbreviations: NS noise scale. Axis x represents the number bits that every node has sent. Dimension d 1000.
diverged. We can see that in all experiments, Perm/ behaves better than Rand K and tolerates larger step sizes. The improvement becomes more significant when increases.
A.4 COMPARISON OF EF21 WITH TOPK AND MARINA WITH PERM ON QUADRATIC OPTIMIZATION PROBLEMS
In this section, we provide detailed experiments from Section 5.1 and comparisons of EF21 with TopK and MARINA with PermK with different step sizes (see Figure 6 and Figure 7). We omit- ted plots where algorithms diverged. As we can see, when L_ < 0.2T and n 2 10000, PermK converges faster than TopK. While in heterogeneous regimes, when L is large, Top has better performance except when n = 10000. When n > d, we see that PermK converges faster in all experiments.
15

---

Published as a conference paper at ICLR 2022
tome
Figure 4: Comparison of RandK and PermKon synthetic quadratic optimization tasks. Each row corresponds to fixed number of nodes; each column corresponds to a fixed noise scale. In the legends, we provide compressor names and fine-tuned multiplicity factors of step sizes relative to theoretical ones. Abbreviations: NS noise scale. Axis x represents the number of bits that every node has sent. Dimension d 1000.
22214
Aend m
of
Figure 5: Comparison of Rand and PermK under PL condition on synthetic quadratic optimiza- tion tasks. Each row corresponds to a fixed number of nodes; each column corresponds fixed noise scale. In the legends, we provide compressor names and fine-tuned multiplicity factors of step sizes relative to theoretical ones. Abbreviations: NS noise scale. Axis x represents the number of bits that every node has sent. Dimension d = 1000.
16

---

Published as a conference paper at ICLR 2022
tome
bal
Figure 6: Comparison of Topk and PermKon synthetic quadratic optimization tasks. Each row corresponds to fixed number of nodes; each column corresponds to a fixed noise scale. In the legends, we provide compressor names and fine-tuned multiplicity factors of step sizes relative to theoretical ones. Abbreviations: NS noise scale. Axis x represents the number of bits that every node has sent. Dimension d 1000.
20
32214.
far Call
non at
Arie at
of
Figure 7: Comparison of Topk and PermK under Pt condition on synthetic quadratic optimization tasks. Each row corresponds fixed number of nodes; each column corresponds to a fixed noise scale. In the legends, we provide compressor names and fine-tuned multiplicity factors of step sizes relative to theoretical ones. Abbreviations: NS = noise scale. Axis æ represents the number of bits that every node has sent. Dimension d = 1000.
17

---

Published as a conference paper at ICLR 2022
A.5 EXPERIMENT WITH MNIST: FULL DESCRIPTION
We introduce parameter P. Initially, we randomly split MNIST into n + 1 parts: Do. DI.-.., Dr. where л 1000 is the number of nodes. Then, for all E (I,..., ..). the jth node takes split Do with probability p. or split D; with probability - P. We define the chosen split as Dj. Using probability control the homogeneity of our distribution optimization task. Note that if p 1, all nodes store the same data Db, and if p = O, nodes store different splits Dj.
Let us consider the more general optimization problem than in Section 5.2 ing non-convex loss with regularization:
We optimize the follow-
min DER'S Xde BERdexdy xdy
F(D,E) E) = Σ
DEa, - -.ll
I DE I1I?
where a; Rd are MNIST images, dy = 784 the number of features, de 16 the size of encoding space. regularizer À A20 0.
Each node stores function
DEa, a,ll X IDE I vi (I. n).
fiDD
Σ jEñ;
D
In Figure 8 one plot for each compressor with the best convergence rate is provided for A {0, 0.00000,, J.001} and p = (0, 0.5, 0.75, 0.9, 1.0).
We see that in homogeneous regimes, when ğ E (0.9, 1.0), Perm outperforms other compressors for any A. And the larger the regularization parameter X, the faster Perm convergences compared to rivals.
Prewcatee 11
Podbabilyy by Ui
Pretabiity 20 ETS
Fersali EK a
Pooial Biy
And Resdent
Auct Soareend
Food
Hge Aecit Bee Sertnnt
Aorid Soaterr
ca fook
denca
Cai Keds bentn
Figure 8: Comparison of algorithms on the encoding learning task for the MNIST dataset. Each row corresponds to fixed regularization parameter X; each column corresponds to fixed probability p. In the legends, we provide compressor names and fine-tuned step sizes. Axis x represents the number of bits that every node has sent.
A.6 COMPARISON OF MARINA WITH RANDK AND MARINA WITH PERMK ON MNIST DATASET
In this section, we provide detailed experiments from Section 5.2 and comparisons of RandK and PermK with different step sizes (see Figure We omitted plots where algorithms diverged. We see that in all experiments, PermK is better than RandK. Practical experiments on MNIST fully produce dependencies from our theory and experiments with synthetic quadratic optimization tasks from Section 5.1
18

---

Published as a conference paper at ICLR 2022
Frotsoiity Gl- 3,
Prised By 5 625
Fritelity 94-03 05
P5338 By S5 63
ca
Syst bid da
Nor 2
Rest by 33
Acoit
Pecii Back 10
be
tol
Quat the oo AD)
Figure 9: Comparison of RandK and PermKon the encoding learning task for the MNIST dataset. Each row corresponds to a fixed regularization parameter A; each column corresponds to a fixed probability p. In the legends, represents the number of bits that every node has sent.
provide compressor names and fine-tuned step sizes. Axis
A.7 COMPARISON OF EF21 WITH TOPK AND MARINA WITH PERMK ON MNIST DATASET
In this section, we provide detailed experiments from Section 5.2 and comparisons of Rand and Perm with different step sizes (see Figure 10). We omitted plots where algorithms diverged. We see that, when p E {0.9, 1.0). Perm tolerates larger step sizes and convergences faster than TopK. When P E {0, ).5), both compressors approximately tolerate the same step sizes, but TopK has a better performance when E {0, 0.00001).
Pridi valia Win 2.0
tee for
Sae cats
fand
Tat Laus
bud the das
4 the Eil
Figure 10: Comparison of TopK and PermKon the encoding learning task for the MNIST dataset. Each row corresponds to a fixed regularization parameter x; each column corresponds to a fixed probability p. In the legends, we provide compressor names and fine-tuned step sizes. Axis represents the number of bits that every node has sent.
19

---

Published as a conference paper at ICLR 2022
Table The "adaptive" ratio [4 and PermK on MNIST (see Figure
(44)²
(L4)
calculated at points xf from experiments with MARINA
1
Iteration number
10
300
600)
900
(E4) (L4) ((4)
(14)
Homogeneous (p = 0.9)
104.73
9.96
5.69
3.61
Heterogeneous (p- 0.0)
18.83
2.31
1.69
1.30
A.8 BEHAVIOR OF THE HESSIAN VARIANCE IN EXPERIMENTS
Now, investigate the behavior of the Hessian Variance L in practical machine learning tasks and compare it with IT. Our goal is to show that L can be much smaller than L4 in some tasks.
A.8.1 LINEAR REGRESSION WITH 2 NODES
Let us consider the linear regression problem distributed between 2 machines:
min WER
[f(w) X v1ll + 21 -22l
y2]l?]
where (X1, (1) and (X2, V2) refer to random split of the "mg" dataset from LIBSVM 385 samples and = 6 features). Using the results from Example 3 we get L4 = 3609.6653 while L+ 34.58. Clearly, Ly orders smaller than Lt.
A.8.2 LOCAL HESSIAN VARAINCE IN MNIST EXPERIMENTS
Now, estimate L+ and L+ in the following way. While MARINA running, capture points xf and calculate the "adaptive" LL_ and L4 that satisfy
Vf((=') V 21 - V
(L1) ||00" - 1111112
and
[V)('*) - vi( (L4) 1| 1121
In experiments from Section 5.2 (see also Figure 2). evaluate (z4)² (L1) in MARINA with PermK. Results are presented in Table 5
We see that in the homogeneous case, (L1)² is about 10x times smaller than (IZ)² (on average), and (LI.)² is much larger at the start of the process. On the other hand, in the heterogeneous case, the difference is smaller. The above experiments provide further numerical justification that L2 can be effectively much smaller than L3, and that this drives the improvement our new Perm K compressor.
20

---

Published as a conference paper at ICLR 2022
B MARINA ALGORITHM
To the best of our knowledge, the state-of-the-art method for solving the nonconvex problem [1 in terms of the theoretical communication efficiency is MARINA (Gorbunov 2021 (see Algo- rithm Tb. In its simplest variant, MARINA performs iterations of the form
n g
1 71
x² 79"
9
(8)
where of is a carefully designed biased estimator of the gradient V ff(")),, and > 0 is a learning rate. The gradient estimators used MARINA are initialized to the full gradients, i.e. g. Vf((²"), and subsequently updated as
for E (I. n).
(((attt)) + C. (V. v)((*)) if
if 0g =1 0==0¹
g; 8++
where 0g is a Bernoulli random variable sampled at iteration (equal to with probability p E (0, 1J. and equal with probability 1 p). and C, R2 Rd is randomized compression operator sampled at iteration & on node i independently from other nodes. In particular, Gorbunov et al. (2021) assume that the compression operators C, are unbiased, and that their variance proportional to squared norm of the input vector:
E [C(())) = E [[G)(() - x1|²] S wi ||
Va E Rd.
In each iteration of MARINA, the gradient estimator is reset to the true gradient with (small) prob- ability p. Otherwise, each worker compresses the difference of the last two local gradients, and communicates the compressed message
m = C. (Vii(**t)) - (x**))
to the server. These messages are then aggregated by the server to form the new gradient estimator via
g+ g
m
Note that this preserves the second relation in (8), ii) the server can compute g K+I since it has access to gf, which is the case (via a recursive argument) if gd is known by the server at the start of iterative p
Further, note that the expected communicution cost in each iteration of MARINA is equal to
Comm pd p1--)))) C = max C.,
where d is the cost communicating (possibly dense) vector in Rd. and S. S d is the expected cost of communicating vector compressed by C,.
MARINA one of the very few examples stochastic optimization where the use of a biased estimator leads to better theoretical complexity than the use of an unbiased estimator, with the other example being optimal SGD methods for single-node problems SARAH (Nguyen et al. 2017). SPIDER (Fang
et al. 2018). PAGE (Li et al. 2021).
*This done by each worker sending the full gradient gf Vf((x") the at initialization.
21

---

Published as a conference paper at ICLR 2022
C MISSING PROOFS
C.I. PROOF OF LEMMA
Lemma 1. IfC, E U(w) for E (1,2,...,m), then {C.) E U(max wi, 0). we further assume that the compressors are independent, then {C, l E U(2 max; wi, 0).
Proof. Let us first assume unbiasedness only. By Jensen's inequality,
E -
- a2
IIC((a;) - aill
remains to apply expectation on both sides and then use inequality
E) [IC.(a.) aill]] S wi || Vi E .1......).
conclude that {c,) E U(max, W, 0). Let us now add the assumption of independence.
E
(a.)
E
(((a:) - az)
E
[[C - -x113]
E ((C((a))) - a,, C,,,) az)]
n
m188; Wi
Σ |ail1
n
by independence, thus, A max, W// /n, B = 0.
C.2 PROOF OF LEMMA 2
Lemma 2. L_ S 44, L- < 1 E Li L < Σ L3 and L3 - L2 < L3 2
1=1
Proof. Let us define
(x,v)) [Vf(x) V
(2. v) = Σ [Vf((z) - V
(+(2.)) = L4 v) L- (x.
The inequalities are now established as follows:
1. By Jensen's incquality and the definition of L+,
L- (xx v) S C_ (x. y) < 1 |a 311
thus, L_ is at most L4.
2. By the triangle inequality, we have
[V vs(wil Σ
s Σ La || - -
thus L__. is most Σラ L...
22

---

Published as a conference paper at ICLR 2022
3. From the definition of L5, we have
(+(,,)) 1 VAWll
Σ 1=1
1. | v11
and I2 is at most :/2 - T.
4. The right inequality follows from C- C- y) 2 and
(= < C+ (z. y) - L3 | yll
Now, we prove the left inequality. From the definition of Lr, we have
(1(0,)) - 12 | y11².
and
(+(x,)) C- (2. 9) C- (x,1))
hence,
C+ v) S L || ylI² + (_ S S(2 +22 1| u
thus L3 < L + L.3
C.3 PROOF OF THEOREM I
Theorem 1, The PermK compressors from Definition 2
are unbiased and belong to (V(1).
Proof.
We fix any x Rd and prove unbiascdness:
q
[(C())) =n
[ CT,] = n
Σ
Σ
nq xr
R.
d
j=
1)+1
j=o((i
1)+1
1=1
Next, we find the second moment:
[[C[(0]]]] =n n
gé
E
[ 2
n²
gi
1
bx 12
n² d
||0||
- ||
( 1)+1
j=
1)+1
For all an,...,a an Rd the following inequality holds:
E
(a()))
[[c((())11]
Σ E((C(())
n
n
[IC((N))
E
n
||:111
Hence, Assumption 4 is fulfilled with A B 1.
23

---

Published as a conference paper at ICLR 2022
C.4 PROOF OF THEOREM! 2
Theorem 2. The PermK compressors from Definition 3
are unbiased and belong to (V(A) with
=
a-d
Proof.
We fix any x Rd and prove unbiasedness:
[[C[(x)) = dF [,,] [T,] d. Σ T24 = x.
Next, we find the second moment:
[[IC([))]]]] = Σ d | = d|
For all j E Rd, we have
C((C(()))CC(,)
C[IG((), Prob (ro (-,=,,)
(1-1)
E [[
(n 1)d 9=1
(q 1)
Σ
d Brgya
(n 1)d
9=1
(q 1)d
(a, v)
For all dj,.... Rd. the following inequality holds:
E
Σ ((as))
E
[[C((a))1P]
Σ C((C(()))
n
n
[a
Σ
E C(((((a)))
n
itj
(q 1)d
Σ
(a
(as, az)
2
n 1)
i=1
(
d
(q- 1)d
1
(g - 1)d
||,111
n
n(n - 1)
1=1
(1 n
| 2
a
71
Hence, Assumption is fulfilled with A B
C.5 PROOF OF THEOREM 3
Theorem 3. Assume that for each ",2,...,n), the function fú is twice continuously differ-
entiable. Fix any 2, y E Rd and define H2(z, y) = fo 22f(( + t(y x)) dt, H H(x.v) ==
H y)- Then the matrices L,(x,V) v) = H²( L (x. = H(xx,)) L (I, =
24

---

Published as a conference paper at ICLR 2022
1 Ei= Hf v) and L+(r,y) == L+ (2, v) - L- (xx, v) are symmetric and positive semidefinite.
Moreover,
L7 sup
(x-1) v) L (x.y)(=-1))
1z-Ø81"
L
sup
(a- L (x.z)(ar y)
| [x-
a.yER syy
a. any
L
sup E.e azy
(x-v) L- (x-y))x-v))
||-~!||
sup
(x- L- (2.g)((=))) ||o-vll
Proof. The fundamental theorem of calculus says that for any continuously differentiable function w : R- - R we have
(11) x0 J. (t)dt.
Choose E (1,2..... n).j E .1.,,...dd, d). distinct vectors x; y E RR, and let
(t) = (V + fly x)), ez),
where E Rd the jth standard unit basis vector. Since fi is twice continuously differentiable, buy is continuously differentiable, and by the chain rule,
(t(() fi + ((y==))(v - z), ez)-
Applying the fundamental theorem of calculus, we get
(1) tha (0) /. ( fi(x + 1ly x))(U (y x)), ez)dt.
[V
Let v/ TR + Rd be defined by (t) == Vz + t(y x)) = (1 (t),...,,(a(())))
(ta( Combining
equations for j 1,2..... d into vector form using the fact that
[. f1 + t(v -()-x))(v -))(
(() V + t x))dt) (v x). eg
we arrive the identity
f((y) ff(())
(1) (0)
v Sil + (ly (1y- x))(ll) x))dl) (y x)
H. v) z).
(10)
Next, since V fz(x + t(y x)) is symmetric for all t. so is (x v), and hence (, v) = (z v) = H (z. Hz, y). which also means that L, (x. y) is symmetric and positive semidef- inite. Combining these observations, we obtain
[v V/
(x- Li(5, (x v)-
(11)
Clearly,
[V.(2z) 2
xx y) L,(a, 8) y) sup
L sup Z.E Mad aayly
|0 wll Using the same reasoning, we have V ( Vx(x) H (a, (y x), and
|| y1
a.yERd ,
Ví(xr - V (
(x y) L (x, y) v) sup Z.EER wyy
L = sup F.yERdayy
x - 21
|| y1
where (_ 9) == (1 y) = H (z, HI, y) is symmetric and positive semidefinite, since (x, 8) are symmetric and positive semidefinite. Finally,
D [Vf((x - v
L
sup 2.yER
11 1r-vvl 21l
(x T) (1 Σn H2 v)) (x v)
sup x.yeRd .z
|| y1
(x y) L. (x,, (x (x - y)
sup
||x - y/ 1
2.ye3 Lad
25

---

Published as a conference paper at ICLR 2022
and
1 E Vf((x) - (VV(t))
L
sup
z.yER",ayy
1/2 111
(x y) ( Σ
(x, u) (x, (x -)
sup
z.y
| -y1?
(x - v) - (2r, y) y) || y 1
sup -.yEr
Note, that (x. y) inherits symmetry and positive semidefiniteness from H2 y). Symmetry of Lg (r. y) is trivial. To prove positive semidefiniteness of - (2r, y), note that
L1 (2.
(a (x,
n
(2, H(x, v) + H(I,)))² (x
n
(H:(r,)) v) - H(r,)))² Hx,
H (x. v) H (x,,)))
1=1
+
(H, v) H(x, v)) H(x,))
n i=1
(H v) Hz
n
which is positive semidefinite.
C.6 PROOF OF THEOREM 4
Theorem 4. Let Assumptions
7 3 and 4 be satisfied. Let the stepsize in MARINA be chosen
0 < 1 M. where M = I._
1-P ((A B) + BI2). Then after T iterations, MARINA
finds random point aT 12d for which
E
[1]
24" 7
Proof. In the proof, we follow closely the analysis of Gorbunov al. (2221) and adapt it to utilize the power of Hessian variance (Definition 4 and AB assumption (Assumption We bound the term E ||0 )|]+ in similar fashion Gorbunov al. (021). ) but make use of the
AB assumption. Other steps are essentially identical, but refine the existing analysis through Hessian variance.
First, we recall the following lemmas.
Lemma' 3 (ii et al. (021 Suppose that L_ is finite and let x!+1 = x² - n Then for any ge E ddd and 7
have
f(att)) f(x') 2
(1_L-
27 2 1='ti_z(117 =z(12
7 lg -V- (12)
Lemma RRicháárik et al. (022))). Let a, b > 0. 1f0 < ST Vous then an² + by S 1. Moreover,
the bound is tight up to the factor of2 since 1
Ja=b < min { (ta t) < Vatb
Next, we get an upper bound of E [1/441 (5(x+1)/11 51+1|
26

---

Published as a conference paper at ICLR 2022
Lemma 5. Let us consider g from Line 8of of Algorithm 7 and assume, that Assumptions 2 3 andd
hold, then
E 11g--1- (
1 (1 p) ((A L3 + +BL)) || =2'1
2²12
-(1-p) 1|g* V|((>)|
(13)
Proof. In the view of definition of g we get
E |10
fx (1
1 Σ g'
c. (V.i(++1)) -
VA(a)) - / ret1
n i=1
= (1 - F)
C. (V -(A())) -/(ett)//( V x
+ (1 - p) |9 2f(z')]2
In the last equality we used unbiasedness of C. Next, from AB inequality, we have
F. - (1 x
V
1/2 Σ C. -((l))))--((()-)----)))))))+())) vf((ttt)+ + vf(at)
S ((1-
x1t1
+ (1 p) 1691 |f(=")|
Vf(('++)- -(( - B BB( -V
$ (1- p) A
i=1
+ p) 110 - V1( ?
-
(1 p)
(A B)
+ B 1
( - ( -((=tt))(((())))) vr(ebirr)
i=1
+ (1 - p) ||gا - v
Using Assumption 2 and Definition we obtain 13
We are ready to prove Theorem 4 Defining
Φ' = f(x²) - -flul + 7 -|g² - vf((=))
2p
1 := (A B) I2 + BL2
27

---

Published as a conference paper at ICLR 2022
and using inequalities (12) and 13
get
E
[
( 1 --
s E
f(=') - -finf [
| - x'Il + 2-2 11g (
2y
+ 2 F. (1 7,² || - x01l 21
+ (1 p) 11g - v](xa)]1]]
2p
= E[ - E || ||²]]
(11 - T.
I__
E |1:211 =x111
+
+
2p
27
2
< E [0]] E
||
[19]
where in the last inequality we use
7(1 p)
1
+ 00 0
2p
27
following from the stepsize choice and Lemma 4
Summing up inequalities E [[
< E E[04]
- EE
[V for = 0, 0.1,..., T
and
rearranging the terms, we get
(E (0) E
(TTT)
2
Σ
S
(E [5'] E [0+
7T
7T
7T
since go vz(²)) and क7, 2 0. Finally, using the tower property and the definition of .T (see Section B we obtain the desired result.
28

---

Published as a conference paper at ICLR 2022
D POLYAK-LOIASIEWIC ANALYSIS
In this section, we analyze the algorithm under Dolyak-Lojasicwicz (PL) condition. We show that MARINA algorithm with Assumption Wenooys a linear convergence rate. Now, state the assump- tion and the convergence rate theorem.
Assumption condition) Function satisfies Polyak Lojjskk-ojasiewiczz (PL) condition, i.e., [|V 2 2u(f(x) - f*), Vx E 12,
(14)
where μ > O and f = inf, fxx)..
Lemma 6. For > 0 and p. from Assumption 5 holds that L- 2 μ. Theorem 5. Let Assumptions
>
2
3
4
landd be satisfied and
Y S min {
2 (1-p) p) ((A- (
B12)
p
(15)
2/
then for x² from MARINA algorithm the following inequality holds:
E [f(xx) - S (1- 74)² A
We provide the proof to Theorem in Section
D.2
In Table 6 we provide communication complexity of MARINA with PermK and RandK, and EF21 with TopK, optimized
parameters of the methods. As in Section 4 we see that MARINA with Perm is not worse than MARINA with RandK (recall Lemma 2)
Let consider communication complexity O (max { (dL-/na, d}), while RandK compressor has communication complexity O (max /dli d)). And the communication complexity of PermK strictly better when dr. /vTy > d. Moreover, if d I n and (1 + 4/ (R) r. /p > d, then we get the strict improve- ment of the communication complexity from O (max {(1 + d/v5) /v, (,dd) to O (max {L- d}) over MARINA with RandK.
Hessian variance regime: T O. When d
Perm compressor has
Table 6:
Optimized communication complexity of MARINA and EF21 with particular compressors under PL condition (up logarithmic factor).
Communication complexity
Method
(Lemma 15
(Lemma 16
MARINA
n PermK
maxx
1 min dL_,, 4b_ L
max
min
dl
MARINA
RandK
O max 1 min dL 4 L+
O max
min
dl L-
L
EF21 Topk
di_ P
dk_
D.1 PROOF OF LEMMA 6
Lemma 6. For L_ and p. from Assumption 5 holds that L_ n.
Proof. We can define I_ using the following inequality:
(V)(w), ( + L
f(x) < f()) +
2 || y11 Vx, Va,Y,
Let us take y 1/L_Vf(z) V2))). Then,
1 - v() < f(v) 2L_
1 [V Vy Yy.
Rearranging the tenms and using Definition 14 we have
2T_ |V f(v) -1 < <s(w)
1
fint S |
24
thus, / L...
29

---

Published as a conference paper at ICLR 2022
D.2 PROOF OF THEOREM 5
Theorem S. Let Assumptions 2 3 4 aandn 5 be satisfied and
{ 2 p) ((A ((A-B)LE B)L + BLA)
YS min
p
(15)
2/
then for x² from MARINA algorithm the following inequality holds:
E (f((=))ff) (1 A
Proof. The analysis is almost the same in Gorbunov et al. (20II, but we include it for complete- ness. Let us define
Φ' = f(x") finl + ? 1 vf(")]"
i= ((A-B) L3 + BL3))
As in Appendix C.6 we use 12 and (3) get that
E
[+
1 L- | - - + 2 E1g V
s f(x') pinnf - [
27
+ 2 E (1 2) || 11 + (1 - p) ||g' - vf(x')]1
14
(1 4-
2y 2 ) || - x² 2²12 Illa V
(1)(f(2') pint)
+ " (1 - p) 11 z²1' $1(
+ (1 p) 11g - -
[ (
1(1 - p)) 1 &)(
(1 (
pinf)
p
(2 p)
1
L_)
| 2013
E
+
p
24
s (1 1B)1 (
In the last inequality, used (1 p) b- I 0 and + 7 - p) s (1 -y1)² 7 that follow from 15 and Lemma Unrolling have
p.
[pp++] < (1 F (क-) and using g" vf(x.)) ), we
E [f(x")
I E
x T
S 5 (1- <1 = - -1-7 (f(x²)- - -jint).
This concludes the proof.
30

---

Published as a conference paper at ICLR 2022
E EF21 ANALYSIS
We provide convergence proofs of EF21 algorithm from Richtárik et al. (2021) for non-convex and PL regimes. They will be almost identical to the one by Richtárik et al. (0021) (indeed, the only change the constant L+ instead of L), but we have decided to include for the sake of clarity.
E.1 EF21 RATE IN THE NON-CONVEX REGIME
We will be using the following lemmas, the proofs of which are in their corresponding papers.
Lemma 7 (Richtárik et al. (2021)) Let C to be a-contractive for O < a S 1. Define G =
|lo
(x"""") and W = (.i....,gh x², x. For any >> O we have
E B w s - (((s)))) + B(0) V V)(("")]?
(16)
where
0(s) 1- a1 + s),
and
B(s) = (1 a) (1+
(17)
Lemma 8 Richtárik al. (2021). ) Let < a S and for s let 0(s) and 3(s) be as in
equation
17
Then the solution of the optimization problem
(())
0 <8 8
(18)
((s)
1 02
given by s*
1. Furthermore, 0(s*) 1 vI a, B(s*)
1-0 and
vI-a
T-vi-a
B(s²) 0(**)*
1
vI 1-
1 15 2 -1 1.
(19)
vi-a
We are now ready conduct the proof.
Theorem 6. Let Assumptions and hold, and let the stepsize be set
0<7s L- + L
B
(20)
Fix T 2 1 and let &T be chosen from the iterates x² x,,xt .x.....,
x., 1 uniformly at random. Then
E [[[V=(6911) 2 (f(22)) - find)
[G']
+
(21)
7/
Or
Proof. STEP 1. Recall that Lemma says that
E |10 110 (i( w*] s (1 - 0) |1lt v)(=+) V -/((')) (22)
where 0 = 0(s") and B = B(*)) are given by Lemma
Averaging inequalities equation 22 over
E (1,2.... n gives
G Wt]
1 Σ
110 ++1 v w
=
n
< (1 0) n
l1lt v>( + + Σ
[V - V
1 (1 f)G¹ + B / - {)((2))
< (1-0)C + BL || x'
(23)
Using Tower property and L-smoothness in equation
23 we proceed to
E [c = E E [G w']] < (1 0) E [ + 3L E [| [0(1-=
(24)
31

---

Published as a conference paper at ICLR 2022
STEP 2. Next, using Lemma 3 and Jensen's 's inequality applied to the function + ||=]| obtain the bound
f(a!t1) _ f(at) - ?
2 |\(('']|
1 I_
)
|| 2²1 22122 n2 Σ
?
n
(g)
Vfi(a'))
2y
I f(tt) 2
2 ||[a))]|
1 L_) >
) ||//|1 2¹1 =122 G
(25)
2y
Subtracting finf from both sides of equation
25 and taking expectation, we get
E | sin s
E[f(x') - -
E
L-
E |1 - x²' x0'1?] + 2 [G)
(26)
27 2
COMBINING STEP AND STEP 2. Let 8 = E [f(x*) - p = E G and rf
E |||lt| -
-2'11 =²1
Then by adding equation 26
with
29 multiple of equation 24 we obtain
8++1 + 2 st
S 8³ |fx'')]
1
L
rf
7 s'
+
(BL
+ (1 0)s²)
20
27
2
29
8' + st 7 |
)|
L_
7
3L3
pt
20 2
2>
2
20
< 8 + 20 2
7
||
The last inequality follows from the bound 722 a
غ + L_ S 1, which holds from our assumption
on the stepsize and Lemma 4 By summing up inequalities for t O,..., T - 1, we get
T-1
0 5
Y ST < 8
2
2 5
E ||]
20
t=0
Multiplying both sides by TT after rearranging we get
28 s"
7T
OT
remains to notice that the left hand side can be interpreted as from Z ,.,."
[|V[())) ["].
where 2: is chosen
x7 T-1 uniformly at random.
E.2 EF21 IN PL REGIME
Theorem 7. Let Assumptions
and 3 hold, and let the stepsize in EF21 be set
0 < 7 < min { I T+V 0
23
0
(27)
2p
Let := = f(x²)= pint + G Then for any
T 2 0, we have
E 1
< (1 - mp) T E [
(28)
Proof: Again, this follows Richtárik et al. (2021) almost verbatim.
We proceed as in the previous proof, but use the PE. inequality and subtract finft from both sides of equation 25 to get
E [ pinf]
< E [f(xt) - |'m| -3 2 [|
( 1
4
|1/2t1 - -2'12
2-12+ + 2 c
24
2
2
s (1 - F. [f(x²) - pin']
L_
||
- -x-12 l
2y
2
2
32

---

Published as a conference paper at ICLR 2022
Let 8 : Bf((²) - fi == E [G"] and := E
||| - -x-11]
Then by adding the above
inequality with & multiple of equation 24
we obtain
8 + 2 2 0
< (1 - 71100
L_
r
+
=
8¹
+ 7 ((1 - 0)5² + +112rr)
2 2
2
0
1
L- 3122
7w)) +
8²
r".
27
2
0
Note that our assumption on the stepsize implics that
1/ 2 1 7/p and
AL
0.
27
2
72 2
The last inequality follows from the bound and our assumption on the stepsize. Thus,
+ - 1, which holds because of Lemma
8++1 + - stt
- (1 7x) (8' + )
It remains to unroll the recurrence.
33

---

Published as a conference paper at ICLR 2022
F COMMUNICATION MODEL
As mentioned in the introduction, we consider the regime where the worker-to-server communica- tion the bottleneck of the system so that the server-to-workers communication can be neglected. While this is standard model used in many prior works, we include a brief explanation of why and when this regime useful.
1. Peer-to- peer communication. First, this regime makes sense when the server is merely an abstraction, and does not exist physically. Indeed, from the point of view of each worker, the server may merely represent "all other nodes" combined. In this model, "a worker sending a message to the server" should be interpreted as this worker sending the message to all other workers. Clearly, in this model there is need for the "server" to communicate the aggregated message back to the workers since aggregation is performed on all workers independently, and the aggregated message is immediately available all workers without the need for any additional communication.
2. Fast broadcast. Second. the above regime makes sense in situations where the server ex- ists physically, but able broadcast the workers at a much higher speed compared to the worker-to-serve communication. This happens in several distributed systems, e.g., on certain supercomputers (Mishchenko et al.) (019). Virtually all theoretical works on communication efficient distributed algorithms assume that the server-to-worker commu- nication is cheap, and in this work we follow in their footsteps.
Having said that, our work can be extended to the more difficult regime where the server-to-worker communication also costly (Horväth al.] 2019 Tang et al. 2019 Philippenko & Dieuleveut, 2020 Gorbunov et al. 2020). However, for simplicity, we do not explore this extension in this work.
G ON CONTRACTIVE COMPRESSORS AND ERROR FEEDBACK
G.1 ON CONTRACTIVE COMPRESSORS
The most successful algorithmic solutions to solving the nonconvex distributed optimization prob- lem (T) in a communication-efficcett manner under the communication model described in Ap- pendix F involve stochastic gradient descent (SGD) methods with communication compression. There are two large classes of such methods, depending on the type of compression operator volved: (i) methods that work with contractive (and possibly biased stochastic) compression oper- ators, such as TopK or RankK, and (ii) methods that work with unbiased and independent (across the workers) stochastic compression operators, such RandK.
(randomized) compression operator C Rdd + Rd is a-contractive (we write E C(a)), where 0 < if
E [IC(x) -11 =1| < (1 - a) |=ll EER.
(29)
canonical example is the (deterministic) TopK compressor, which outputs the K largest (in ab- solute value) entries of the input vector and zeroes out the rest. 'TopK' is a-contractive with = K/a. Another example the Rank compressor based on the best rank- K approximation of x d matrix. It can be shown that Rank is a-contractive with K K/minta.b) (Safaryan et al. communication-e efficienn method PowerSGD based on low-rank approximations.
represented 2021 Section A.3.2). We refer to the work of /Vogels et al. (2019) for practical
Of special importance are a-compressors arising from unbiased compressors via appropriate scal- ing. Let Q : Rd > Rd be unbiased operator with variance proportional the square norm of the input vector. That is, assume that E [Q(x)] = x for all x E Rd and that there exists w 2 0 such that
E [10(z)
=|| S sw 1
Vr E Rd.
(30)
We will write Q e U(w) for brevity. is well known that the operator C = (w + 1) Q is a-contractive with (w +w+1) 1)-1 An example of contractive compressor arising this way is
34

---

Published as a conference paper at ICLR 2022
(w + RandK,,, which keeps subset of K entries of the imput vector chosen uniformly random, and zeroes out the rest. As TopK, (w + +1 1 RandK a-contractive, with a = K/a.
Distributed SGD methods relying general contractive compressors, i.c., contractive which do not arise from unbiased compressors from scaling, need to rely on the error-feedback erro-- compensation mechanism to avoid divergence.
G.2 ON ERROR FREDBACK
An alternative approach to the one represented by MARINA is to seek more aggressive compression, even the cost of abandoning unbiasedness, in the hope that this will lead to better communication complexity in practice. This is the idea behind the class of contractive compressors, defined in (29).
which have studied at least since the work of Seide et al. (2014). Example such compressors are the TopK (Alistarh et al. 2018) and RankK (Vogels et al. 2019 Safaryan et al. 202 compressors.
While such compressors are indeed often very successful in practice, their theoretical impact on the methods using them is dramatically less understood than is the case with unbiased compressors. One of the key reasons for this that a naive use of biased compressors may lead to (cxponential) divergence, even in simple problems (Beznosikov et al. 2020). Because of this, (Sede et al. (2014) proposed the error feedback framework for controlling the error introduced by compression, and thus taming the method to convergence. While it has been successfully used by practitioners for many years, error feedback yielded the first convergence results only relatively recently (Stich et al. aaal,,221) 2018
Stich & Karimireddy 2019; Wu et al. 2018 Koloskova al. 2019 Tang et al. 2019 Karimireddy
et al. 2019 Qian et al. 2020 Beznosikov et al. 2020 Gorbunov et al. 2020).
The current best thcoretical communication complexity results for error feedback belong to the EF21 method of Richtárik et al. (202T) who achieved their improvements by redesigning the original error feedback mechanism using the construction of a Markov compressor. However, even EF21 currently enjoys substantially weaker iteration and communication complexity than MARINA. For instance, we show in Appendix that EF21 with TopK is only proved to have the communication complexity of the gradient descent without any compression.
35

---

Published as a conference paper at ICLR 2022
H COMPOSITION OF COMPRESSORS WITH AB ASSUMPTION AND UNBIASED COMPRESSORS
Lemma 9. If (C: U(A, B) and Qi U(ws) for i (1,2,..., n), then {C, 2 U((max; W, + +1 A, B).
Proof. By the tower property, for all ;l,...;aa E RR, we have
a
E
c(O(aa)))
Σ (((a))
E
E
((2((a)))
1 Σ
2(a)))
(i(a)). 2n(an)
n
1 n
$ E
A-
Σ
(a.)l B
Σ (a.)
Since 2₁ E U(w,) for {1,2.... n), get
C(Q((a))) 1 Σ (aa))) |
E
Σ
(maxws Wi +1) A Σ
||a 11 BE
1 Σ 2.(a))
-=1
1=1
Using Jensen's 's inequality, we derive inequalities:
E
(a.))
1 Σ [Q z
=
a
n2
72
and
E
(a)) -1
(a.)
max We + +1) A >
||
a
n 1=1
The last inequality completes the proof.
36

---

Published as a conference paper at ICLR 2022
I GENERAL EXAMPLES OF PERMY
For the sake of clarity, in the main part of our paper. we assumed that d or d and pro- vided corresponding examples of PermK (see Definition and Definition B Now, we provide two examples of PermK that work with any and and generalize the previous examples.
1.1
CASE d 2 n
The following example generalizes for the case when does not divide d. Let us assume that = kn + r and S r < n. As Definition [ we permute coordinates and split them into blocks of sizes {k, ..,, r.. The first block of size k we assign to nodes. Next, we take the last block of size and randomly assign each coordinate from this block to one node. As the size of the last block of size is less than some nodes will send one coordinate less.
Definition 5 (PermK
n)). Let assume that 2 d = kn + E r < n,, x" = (TÍ....., T.) is a random permutation of (l....,d), and n (T "I...,
(d
nn) is random permutation of {1.... , We define the tuple of vectors S(x) (I Exd 2 2 Fxd Exteer Cad .,...,0) of size n. Then, k0+1
ki
Cx(x) ==
Eadeag + (S(x))a?
j=k(i-1)at 1)+1
Theorem 8. Compressors (c from Definition
belong to (V(1).
Proof.
We fix any x E Rdd and prove unbiasedness:
ki
(aggrr) + + (((((())))))
E [C)()))
= n
j=k(i 1)+1
(1 )
n )
r 0+
= n
+
n d
km + r
n
x
nd
F,
for all E nI, n}.
Next, we derive the second moment:
ki
2
+ E [[s( 11)
E [Ic](=0)]]]
= n?
E Cageag |
j=k(i- 1)+1
n?
||-|| + (1 (1- =) |lo1|
+ r1
n ||x11
(km+ + ||
kn
n?
nd
n n||==1?,
We fix x, E Rdd For all i *lE (1....,nk) n), we have
E C(C,()).CC())))
ki
n²
Σ
2 Eayezy + (S(x))
Σ
Mayeng + (5()))
=0
due to orthogonality of vectors ep. for all p (1,.... d). and the fact that i +
37

---

Published as a conference paper at ICLR 2022
Thus, for all 01....,0, On R,, the following equality holds:
[]
c(a.)
Σ B [[((())) + E
C(a,)
Σ a; 1?
71
71
Hence, Assumption is fulfilled with A 4= =.
I.2 CASE n 2 d
The following definition generalizes Definition 3 for the case when d does not divide n. Let us assume that = gd + and 0 < r < d. As in Definition 3 we permute the multiset, where each coordinate occures q times. Then, we randomly assign each element from the multiset of size gd to one node. Note that randomly chosen nodes are idle.
n 0 d. Let us fix point x E Rd, that we want to compress. Define the tuple of vectors S(x) = (#1e),..., "2, ... TdEds ,.,,,, where each vector occurs q times. Concat r zero vectors to S(æ): S(x) = S(x) @ (O....,.) 0). Let क = (TI,...., Tn) be a random permutation of nI.. Define
Definition (PermK, (n 2 d)). Let us assume that n. 2 d,
(x(x) == n (S(x)),.
Theorem 9. Compressors i from Definition 6 belong to TV (A) with A = 1 n(g-1)
(n
Proof. We start with proving the unbiasedness:
d x,
E [[((x)] 12
eye T Prob
9
j=1
for all E (I,...,,), n), Rd.
Next, we find the second moment:
d n²² Σ q
E. [[IIC())P]]
x
Prob (T, = j) = q
-|ar 12
i=1
for all i E u Rd.
For all Hj e E (l,...,, n} and x, Rd, we have
n²
C((((()) =
Tn Prob (TT = k. xΙ k)
q2 k=1
n
o1g 1)
nlg (x, 11)
D
nnn - 1)
(n 1)4
Thus, for all a1 a....., On Rd, the following equality holds:
1 a
E
n Σ
c((aa)
Σ
E [[c((a))]]]
+ n²
Σ
E((C((a)
n
itj
n(g 1)
1
|0,11
(ac ag)
ng
(n 1)g
n
i
L
( 1) 1)
1 Σ
n(g - 1)
|a.11
+
-
0
nn 1)g
(n 1 1)g
i=1
38

---

Published as a conference paper at ICLR 2022
Hence, Assumption is fulfilled with A ==1== 1
niq-1) (n-1)4
J IMPLEMENTATION DETAILS OF PERMK
Now, we discuss the implementation details of PermK from Definition Unlike RandK and Top compressors, Perm/ compressors are statistically dependent. We provide simple idea of how to manage dependence between nodes. First of all, note that the samples of random permutation are the only source of randomness. By Definition each communication round. However, instead of sharing the samples, we can generate these samples each node regardless of other nodes. Almost all random generation libraries and frameworks are deterministic (or pseudorandom) and only depend the initial random seed. Thus, at the beginning of the optimization procedure, all nodes should set the same initial random seed and then call the same function that generates samples of random permutation. The computation complexity of generating a sample from a random permutation π (T1...., TT) is O (d) using the Fisher- Yates shuffle algorithm (Fisher & Yates 1938 Knuth 1997). All other examples of compressors can be implemented in the same fashion.
2 they are shared between nodes and generated in
MORE EXAMPLES OF PERMUTATION-BASSED COMPRESSORS K
K.1 BLOCK PERMUTATION COMPRESSOR
In block permutation compressor, we partition the set (l. into S disjoint blocks. For each block P.. [ n devices sparsify their vectors to coordinates with indices in P. only.
Definition 7. Let P to be a partition of the set {1.....d} d} into m I n non-empty subsets, and n = Define matrices A1...., An as follows: put A, := 0 mq. Denote the subsets in as P,,... .mm- Next, for any P; E P. we set (i--1)t11 ()- - Aig to Diag(P.) P.). Here by Diag(S) we mean the diagonal matrix where each ith diagonal entry is equal 1 i E S and 0 otherwise. Let π = (T....., Tn) be random permutation of set {1...., n). We define C,(x) := A We call the set {C the block permutation compressor.
mr+ where 0 I
Lemma 10. Compressors {c.) belong to (V(A) with A = (x-11)
x(g-1)
Proof. We start with the proof of unbiasedness:
1 n
E(C,(1))
Ar,
x
2 Diag(P?)
1x x,
q
for all E (I....,,I]] n), Rd.
Next, we establish the second moment:
2
E -
- 0+
9
n
9
n
n
2
71
jEN
==1
for all i E (1,...,,n,.. Rdd
The following equality will be useful for the AB assumption:
E ((C(()))
E (A An,u))
n² Til
Prob (T: E Pk. ny E Pt)
k=
VEP
m
n²
ala 1) n(n 1)
q2 IIli
A=1
MEP
n(g- 1)
(I, y)
g(n 1)
39

---

Published as a conference paper at ICLR 2022
for all i # (1,.,.,,),,,,, e Rd. Thus,
E
aas)
1
Σ
|| + n(g -11 1)
Σ
(1s
gm 1=1
(n 1)
1=1
n(q
n
n(q 1)
||ss
mm
(n - 1)mm
(n - 1)4
(n
1) -)-99 + 1
1
n(g 1)
||a||
(n 1)q
(n 1)g
n
q
||ail
+ n(q - 1)
(n 1)9
(n 1)
1=1
1=1
1 n(q -11--1111
|| + n(9- 1)
1
0
(n 134
(n 1)4
n
for all aq...., On Rd. Hence, Assumption is fulfilled with =
x(g-1) (x- l)4
K.2 PERMUTATION MAPPINGS
Definition 8. Let QI...., Qn : Rd be a collection of deterministic mappings IRd + Rdd Let (T.,... ..i....,T)))) be a random permulation of set {1,..., where n > Define Qu, Assume that the following conditions hold:
x. y E Rdd 0 such that E [IC((=)]?] (w 1||/ for all i (l.....m),
1. There exists
2. There exists 0 E R such that (Q((z), Qx)) = (z. v) for all x. y E Rd.
n
3.
Σ Qi(x)) = x for all E TRd.
"
We call the collection (Ca) the permutation of mappings.
Lemma 11. Permutation of mappings belongs to U(A, B) with A w+1
n-1 (1
0
and
n²
B 1 --I -2)..
40

---

Published as a conference paper at ICLR 2022
Proof. Unbiasedness follows directly from Condition establish the AB assumption.
Let us fix ; E Rd. We shall now
C.(a,)) 1 d
Σ
i=1
12
n1
E
QT. (a:) - a:)
1
E
112, (a:) -aill Σ
(2x, as, (0,) az)
ifj
E
Σ |a:ll + Σ ((0+ (Q+
ai 2r, ax))
ifs
|a:12 E
Σ (Q (a.), (az))
Σ (as ag)
2
i=1
|all
|a
2
[10 ((:T; (a:), Qr, (a))))
2
1=1
1=1
1=1
{
(w
(w+1)
1
[a:
ag
+ n12
Σ
1( (a:): Qn,
11
Let us now compute
Σ ((0(
n²
ifj
E
(m, (=,
1 Σ
Σ Qo(aa)
n²
n1 1) uFN
itj
1
Σ n
Σ (a(aa))
n(n 1)
Now,
Σ
(Q((z))
(Q(()),
1
Σ
(Qu(z),
2
n²
n² ==1
u
==
Condition K
(x, v)
1
(Q)x))
n
Condition
(1
0
(x,n),
VI, E Rd.
n²
Hence,
1
(1 0
F (QQ (a:), (x,(1)))
Σ
(ai, az)
n(n - 1)
n
41

---

Published as a conference paper at ICLR 2022
Finally,
E
(a.)
Σ
1=1
+
|ay1l |
0
Σ
(as ag)
n
n(n - 1)
n?a
W
|
1
n
( (1- (1-2) n² )
1 Σ
n
n2
1
Hence, Assumption 4 is fulfilled with 4 w+1
_ B =
ش (1-4) 3)
42

---

Published as a conference paper at ICLR 2022
L ANALYSIS OF COMPLEXITY BOUNDS
In this section, we analyze the complexities bounds of optimization methods, and typically these bounds have a structure of function that we analyze in the following lemma.
Lemma 12. Let us consider function
f(x,V) (x + +1 (1))) b (
where x E (0, 11,y Wmins 11, Mmin E (0.1/2), a 0, and 2 then
1 min(a, azymin + +b,, Vx, e (0, 1].
f(a, v) 2 2
Proof. First, let us assume that x 2 1/2. Then,
[xx 2 2
Second, let us assume that y 2 Then,
f(x,8) 2 x: + 2 x)
2 a
2
Finally, let assume, that y S 1/2 and 1/2. Then,
1 -1 - -111) )
((,,))
(xr + (1 - x)1)) (1-x)1)
a a+b///
x
a(1 x b(x (1 (1- (1-11 (2-1)
2 a(1 z)y b(I(1 5) (1 /l
(1-11
3 (1-1)
2 a(1 2)y + bay (()
( |
(1- (--1)
+
1
1 -1-1
w W
a(1 2)y + 2bzy
x
a(1 (1 - z)y + 2b (1 x)) (1 - y)
W/min b 2
L.I NONCONVEX OPTIMIZATION
L.1.1 CASE 5d
We analyze case, when < d. For simplicity, we assume that d, n > 1, and d 1. For PermK from Definition 2 constants A B = in AB inequality (see Lemma D.. We define the upper bound for the communication complexity of MARINA with PermK a parameter of MARINA, and MARINA with Randk as NRamak (p, k), where is a parameter of RandK. From Theorem 4 have that oracle complexity of MARINA with PermK is equal to
Nremm (p)) where p
L +
P1
1.2
43

---

Published as a conference paper at ICLR 2022
During each iteration of MARINA, average, each node sends the number of bits equal
o pd pdd (1 (pd= -p)
thus, the communication complexity predicted by theory is
A
pd (1 -p))m)) (1-))
Nerm K (p) = &
(31)
up constant factor.
Analogously, for RandK, the communication complexity predicted by theory is
A NRand (p. k) (pd + [))]]]]
1- d
レ- (
L+
(32)
up to constant factor. To the best of our knowledge, this is the state-of-the-at art theoretical commu- nication complexity bound for the RandK compressor in the non-convex regime.
Finally, for TopK, by Theorem 6 the theoretical communication complexity is
-h L- + L4 d k vd dk
NTpp (k)
(33)
up to a constant factor. We consider the variant of EF21, where of are initialized with gradients fi("), for all i E {1,...,m), n), thus E. [Go] 0 in Theorem 6
The following lemma will help us choose the optimal parameters of Neem (p), NRanak (p, k). and N1op (k). We wish to stress that in the following sections the term lower bound should not be understood as the lower bound for the communication complexity. We merely provide lower bounds for the upper bounds predicted by the current sfatc-of-the-at art theory by optimizing their parameters.
Lemma 13. For communication complexity Nremk (p) of MARINA with PermK, communication complexity NRamak (p, k) of MARINA with RandK and communication complexity NToK (k) of EF21 with TopK defined 437. 32
and 33
the following inequalities hold:
1. Lower bounds:
0
d L_ min dL_, n
dLg
Npemk (p)
2
Ap (0.
2E
vn
Upper bounds:
1 5
2 0
dLp
Nrrmm
L +
(34)
11
E
Vn
AdL
Npemk (1)
(35)
2. Lower bounds:
NRankK (p. k) 2 min { dol.,
A
dl,
vnc j. Ap (0. 4k 4k E fl......0
2=
Upper bounds: For all l E (1...., d/ k/d,
4A dd
NRandk (p,k) <
(36)
8VTL
Moreover.for for all E {1,................ .........p.. di. = 1,
NRandK (1,
(37)
44

---

Published as a conference paper at ICLR 2022
3.
AddL.
min (e
Noop (k) Nropk (d)
(38)
Proof.
1. We start with the first inequality:
A
pd + (1 - (1-p)= d
1 P L
Nerm Kc (p)
L_ +
n1
P
0
p (1 - 1)
dh_ + dh= =
P
0
p+ (1 /)
1
dL_ + dL=
n
1-2 P
p
A
p (1 - p) pp+(1
dL_ + vn /
(1-1)ac (n
(1-1)
n
Using Lemma 12 with a = dL_, b = dhe Vn
and Ymin = 1/n, we gett
A
(p- d
P レ+
Nerm (p)
pd + (1 - n1
L- +
8
p
A
db+
min dlL,, ; L- +
2e
vn
for all E (0, 1]. We can obtain the bound
34 if we take p 1/n:
1
0
d
d
Nprmn
+
1
(L= + vn - I1+)
2
0
d
L
+
41
vn"
We obtain the equality 35 by taking p p-
2.
NRand (p. k:)
0 (pd + (1 - p)k)
L +
V
1 -
P
L1p
g
p n
0
p (1 - 1)
dl
dl+
(--1)
c
vn
Using Lemma 12 with = dI,,, b = dhz
v and Vmuin = 1/d, we get
NRaNdK (p, k)) 2 0
min { dL L. +
dL
0
dLy
min
dL_,
2s
Vn
2s
vn
for all p (0,1], [l,...,d.. We can obtain the bound 36 if we take k
{l,..., d/ V and p = k/d:
24"
d L+
NRandx (p, k)) -
kL +
k
-1)
k
Vn
2 u
dL_
dL+
41 ddd
Vni
v
The equality 37 is obtained by taking p
1.
45

---

Published as a conference paper at ICLR 2022
3. This part is easily proved, using L-
L+ from Lemma 2
and directly minimizing (88
In T summarize bounds (34
35
36
37
and
388
L.1.2 CASE 2 d
Now, we analyze case, when n 2 d. For simplicity, without losing the generality, we assume that
d n, > 1, and d > 1. Then, PermK from Definition 3 satisfies the AB inequality with A = B
d-1 I-I"
In each iteration of MARINA, on average, PermK sends O (pd + (1 p))
bits, thus the theoretical communication complexity is
1- pd p
N K (p) = (pd + (1 pp)) (1-
L7
(39)
up to constant factor.
Lemma 14. For communication complexity Npemn (p) of MARINA with PermK, communication
complexity Naadd (p, MARINA with RandK and communication complexity NTop (k) of EF21 the following inequalities hold:
with TopK defined in 39
32
and 33
1. Lower bounds:
0
min dl. I. + dL+ }. vn
Nerm (p)
2
Ap E (0, 1].
2
Upper bounds:
1
4A" U
dh+
Neem K
S
(40)
vn
Npemnk (1) AT
(41)
2. Lower bounds:
A
dl+
NRankK (p, k)
min dl b-
vp (0,1), (1....,,d
28
vn
Upper bounds:
1
2
dL+
NRandK
7.11 <
レ-
(42)
vii
Moreover, for all ls E {1, d.. 1,
NRandK (1,k)= A
(43)
3.
min kE(l....d)
NNopk (k) Nropk (d)
(44)
Proof.
46

---

Published as a conference paper at ICLR 2022
1.
Nermk (p) 3 (pd (1 -p)) (I- v / L
dh+ 4 (p+ (1 p) (dl. + vil v ( (2-1) (d-1)
Using Lemma 12 with = dl_, b=
dhs vn
and Ymin = 1/d, we get
A
min dl_,, Lu dl
N (p)
28
vn
for all E 10, We can show the bound 40 if we take = 1/d:
Neemm
1
A
+ 1 1
-1- 1)
-- + d-
Vn 4+
410
via
The bound
41 is obtained by taking p 1.
2. As in Lemma 13 can get, that
A NRamak (p. k)) 2 min dl,,, Ii +
dL+
/n
for all p E (0,1), E (I....,.d d}. Moreover, we take p 1/d and is
we have
NRank (d) )11)=²
24
dT,
Vn
The bound 43 is obtained by taking p =
3. For TopK, the reasoning the same as Lemma
13
In Table 4 we summarize bounds 44
and 44
L.2 PE ASSUMPTION
L.2.1 CASE <
Using the same reasoning as in Appendix L.1 Theorem 5 and Theorem 7 we can show that com- munication complexities predicted by theory equal
0
pd (1-p) d)
L
2 - p)
L1
1
Npemk (p) log
max
(45)
g
n
1
p
p
p
0 (pd + (1 k))k max
L
2
p)
1
L
NRandk (p, = log
+
(46)
11
n
P
p
0
(T #
Ir-
Lt d
+
Vil2 dk
1
NTgK (k) = log
h max
(47)
1
k
up to constant factor.
Lemma 15. For communication complexity Npemk (p) of MARINA with PermK, communication complexity NRanak (p, k) of MARINA with RandK and communication complexity NT (k) EF21 and
with TopK defined in 45 46
47 the following inequalities hold
In the lemma, we use "Big Theta" notation, which means, that if f(x) ((g(z)), then is bounded both above and below by g asymptotically up to logarithmic factor.
47

---

Published as a conference paper at ICLR 2022
1.
dd_,, d - }
inf pE(0.]]
Neamk (p) O max
min
2.
mmxx {
min dl-,, In 1ut . .d.).
d
inf (EE,
NRanaK (p, =
-
11
3.
NTpp (k)) = = dl
((
min kE(
Proof. Rearranging
45
46 and (47
we get
max [pd+ (1 p) n2
L-
2 - p)
L1
(1 p)d
Nermk (p) = log
,d 4
11
P
11
pm
A
L= +
2
p)
L+
(1 p)k
NRanák (p, k)) = log
max
(pd + (1 (p)})
d +
E
A
--
L+
k + ddz dk
NTop (k) log max
k
k
Note, that
k
2 d, Vk E {l.....d}.
thus in all complexities, the second terms inside the max brackets are at least Analysis of first terms inside the max brackets is the same as in Lemma 13
In Table 6 we provide complexity bounds with optimal parameters of algorithms.
L.2.2 CASE d
The only difference here that the communication complexity of PermK predicted by our theory is the following:
A
{
2 p) d L
Nremk (p) = log
(pd p)) max
(48)
p
Lemma 16. For communication complexity Nremk of MARINA with PermK, communication complexity NRamak (p, k) of MARINA with RandK and communication complexity NT (k) of EF21
with TopK defined in 48
46
and 47 the following inequalities hold:
1.
Npemk (p) θ -0( (max min dd_, L- d
{
d
Lx j.af).
inf [E(0.1]
Vn
2.
NRandr (p. k:) = O (max min dI. I. + d
In 1u+ .a))
inf (E(
maxx
48

---

Published as a conference paper at ICLR 2022
3.
(dL-
[LL_
min k (E
Nopk
(k) =
The proof of Lemma 16 is the same in Lemma 13 Using the same reasoning as before, we provide complexity bounds in Table 6
49

---

Published as a conference paper at ICLR 2022
M GROUP HESSIAN VARIANCE
We showed the communication complexity improvement of MARINA algorithm with Perm under the assumption that l < T... general, T can large; however, we can still use the notion of LA but in different way, by splitting the functions into several groups where L is small.
We split a set {I, ni into nonempty sets { U Gh = {I, n), G. Ng = 0, for all + j E (1,-.. , and |Gal O, for all k E {1,-.,, ,g). Let us fix some set GR and define functions
1
2 (x.,))
(Vf(())
v((C))
99
iE|Sul
4 (v.y)
[V - VS(E))
c (z. v) C (z. v) - Sh (z. v)
and the smallest constants L L L for functions - (x, v). L. (x. v). and c (x,y), such that
C (x, (x, S (1.90) ||00 y/1² 2% (zc, v) S (1.44) ||0 - yl1² f (f, v (I.+) 1| v11
for all & E f1, 99. x, ERd.
In this section, we have the following assumption about groups.
Assumption 6. Compressors between groups are independent, i.e. C, and C2 are independent, for all E G E Sp. k # p. And Assumption 4 is satisfied with constants Ag, and Bg, inside each group GE, for ls E (1.....))
Now, we prove group AB inequality.
Lemma (Group AB inequality). Let us assume that Assumptions 3 and 6 hold, then
1
E
(as)
1
Ag.
1all
1
||a 11
Σ
Bøg G 2
(49)
n
Gk
112
GN
RES
1=1
iE9
Proof.
(a.) - - n
Σ a4
Σ E
Σ
Cilai))
Σ as
REDx
seB
F
Σ Cilas)
Σ
di Σ
Cilas)
Σ 1E9,
ai
kpp
11E9*
leg
iE9,
50

---

Published as a conference paper at ICLR 2022
Due to independence and unbiasedness, the last term vanishes, and, using AB inequality, get
E
(((ss)
Σ
dj
1=1
1=1
Ci(a.)
Σ
di
n
1=1
REG
27
19
Ci(as)
Σ
ai
n2
|Gk 1E9*
99
iE9#
1
Age
llail?
Bg
as
n²
(Ghel
9Kk
iEGx
iEG
From this we can get the result.
Next, we prove analogous lemma Lemma 5
Lemma 18. Let us consider ge+l from Line 8 of Algorithm 7 and assume, that Assumptions and
hold. Moreover, if Assumption 2
holds for every group for & (", .g). then
E 19 +1
x
9
(Ag. Bea) ) 19
g
Bgg 19 12
L ( 2)
S S - p)
Σ
(L4))
| | - 101
n²
n²
4=11
k=1
+ (1 p) 11g - -v
(50)
Proof. In the view of definition of gt+,, we get
E |1g
Σ c, (V/i(ottt) - - V -
= (1-pp)
ge
+ n ==1
= (1 - E)
Σ c. (V.((z*+1) vx((a)) ()(=+1)) vf(a') x1+1
+ (1 p) -
51

---

Published as a conference paper at ICLR 2022
In the last inequality used unbiasedness of C. Using 49
we get
19 + ( r1
m
$ (1 p)
Ci ( -
+V 1141
+11 p) |1gs ()('')|?
Age |h
(1 p)
Σ |
n²
19k1
1E9L
8
Be 1
1
-
12
VEGN
(1 p) 11g2
V((x') !|
9
(Age Bge)
1
9 Beg 1kkl
(1 p)
c (x ,x4)
Lep (s 222))
n²
n²
+ +(1 p)
119' - (2(22))1
(1 p)
9
(Ag. Boa)
14al
[L+
Gx
g
Beg G 12
[
Gz
|| =211
n²
n²
+ (1 p) 11o {f(2")112
Let us define
g
(Ag. - BBx)) 1
5
Ba, 19 19 ? (L (L
L3
+
n²
n²
k=1
Theorem 10. Let Assumptions
and be satisfied. Let the stepsize in MARINA be chosen as
S L- ( LLG
then after T iterations, MARINA finds point i² for which E
[|V
||2]
S
24"
7
Theorem 11. Let Assumptions I and 6 be satisfied and
{ LL_
2 p) L3
p
7 S min
2
then for xT from MARINA algorithm the following inequality holds:
E [ - [*] S (1-110)))))) 7 A
We omit proofs of this theorems as they repeat proofs from Appendix C.6 and D.2 the only differ- ence is that we have take i22 i.z.
Let us assume that n I d, all groups have equal sizes G& G and constants {l....,g), and in each group use PermK compressor from Definition 2 thus communication complexity predicted by our theory is the following:
1 LG for all E
A NG "Pemm K. (p) (pd (1 -1) -_ --+
(1 (1- D)G LG
pn
52

---

Published as a conference paper at ICLR 2022
Using the same reasoning in Lemma 13 take or 1/G to get that d 2 min dL d + d vr (
NG Perm (p) (E
inf
o
(51)
For the case when we have one group, restore the communication complexity from Lemma 13
Comparing (34 with we see that dL- /n from (34) is always better than dL.//G from (51)
however, if dL+/ n bottleneck and L$ is small, then communication complexity 51 can be
better.
Let us consider example of quadratic optimization task with two groups, wherein one group, all matrices are equal to A, and in another one, all matrices are equal to B, A + B, A A > 0 and
B B > 0, then G n/2, - 0, and L O (see Example Hence, get that
Nemm (p) = =0 ( pE(U,1]
Ad
inf
EN
This bound is better than 34 by at least the factor 1 + VTLL//L..
53


Reviews:
[{"review_id": "yiPS5Yz-GXG", "reviewer": "Reviewer_JiFh", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Overall, the paper is interesting, and the analysis in the  main paper is careful and clear. The assumptions are not too outlandish, and it makes sense that sparsification should be easier when data / Hessians are more uniform. (I suspect that is what is happening in the MNIST example, for example.) The paper seems strong, but I am not familiar enough with this specific area to comment on its novelty or impact.\n\nWeaknesses: Since the paper seems mainly to put forward the theoretical advantages of different schemes, I question if the proposed methods are better because of better proof techniques, or if they are really always like that in practice. For example, I suspect a fully correlated scheme where every worker uses the *same* sparsification (but randomly regenerated at each iteration) should achieve good performance as well. It is unclear to me, at least intuitively, why a permutation approach would be better than random sampling. (For this, a few toy examples would be illuminating.) I also think (and this is less easy to address, so it's not really factoring to my decision of the review) that the few experiments given may not be exhaustive enough to provide general conclusions as to the superiority of each method. \n\nAlso, since the appendix is about 40 pages long, I did not have time to read it. If the authors feel there is one specific proof that they are particularly proud of, I'd be happy to take a look and give a less lukewarm review.", "summary_of_the_paper": "This paper investigates a permutation based sparsification technique for distributed optimization, and prove that, under a mildly tighter condition than L-smoothness, it can achieve better communication complexity than the existing random sparsification technique. The method is largely under the larger construct of MARINA, a distributed optimization scheme by Gorbunov. A (1+d/sqrt(n)) factor improvement is shown with the permutation vs randomization technique when the Hessian variance is small, and several promising numerical results are given. ", "summary_of_the_review": "See above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Hgc27zoDfz", "reviewer": "Reviewer_mZxC", "summary": "", "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": "### Strength\n1. The paper proposes some new techniques (e.g. AB inequality and input variance compressors) to relax the original assumption of independent compressors.\n2. The paper proposes a new quantity called Hessian variance to refine the analysis of communication complexity.\n\n\n### Concerns\n1. The advantages of the new theoretical results are based on the regime Hessian variance is 0 or small. To illustrate, the paper gives some examples of Hessian variance equal 0, i.e. identical functions and linear perturbation. But these seem to be very simple cases. For more complicated models, it is not clear if and when the Hessian variance is small.\n2. In the big data case ($d \\leq n$), when $d \\ll n$, there is no improvement.\n3. In Figure 1, PermK does not outperform other algorithms, although the paper claims the theoretical improvement of $\\sqrt{n}$. In Figure 2, the difference between PermK and TopK is very small, which does not show the theoretical improvements.", "summary_of_the_paper": "This paper extends the theory of MARINA to support potentially correlated compressors and refines the original analysis of MARINA based on a new quantity called Hessian variance. They show their proposed compressors, random permutations, have improvements in theoretical communication complexity in the low Hessian variance regime.", "summary_of_the_review": "Although not perfect and build upon existing works, the paper proposes some new techniques and quantity to refine the analysis of distributed non-convex optimization algorithm. The theoretical novelty is sufficient.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FyOO-wsVSqG", "reviewer": "Reviewer_wJjy", "summary": "", "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": "Improving communication complexity is an important topic in distributed optimization. The paper tried to extend the analysis of the SOTA algorithms in a more detailed case to refine the complexities. The paper is clearly written and easy to read.\n\nMy main concern are as follow:\n1. The analysis (Theorem 4) here seems to be heavily relied on the AB inequality and correspondently Hessian variance assumption, but I am not sure whether the Hessian variance is motivated enough. Now authors verify the assumption holds on only identical functions and quadratic functions, I am not sure whether it is applicable to more general problems. \n\n2. For the experiments, does the autoencoder example satisfy the extra assumptions?\n\n3. For the proof, the difference seems to lie in the Lemma 5 here and derivation above Eq (21) in MARINA paper, where AB inequality and Hessian variance work to bring some difference in the coefficients in my opinion, and the claimed difference of using correlated compressor is incorporated into the coefficient computation of AB inequality, the remaining things are similar, e.g., the Lyapunov function $\\Phi$. Can the authors kindly provide more intuition on the benefits of the new analysis, with the additional assumption?  \n\nSome minor thoughts:\n1. Even though closely related to MARINA paper, but as a separate independent submission, to make it self-contained, I may suggest that at least authors can consider to add a formal description (e.g., an \\algorithmic environment or the main update rule) of the algorithm into the main content (rather than mentioning it in Appendix B), I think, at least now, readers should not be required to be familiar with MARINA as they are with SGD before reading the submission.\n\nAll in all, now I view the contributions here are a little marginal, and skeptical on whether it is suitable as a separate work. I hope to have more insights from authors on the importance and practicality of the additional assumptions. Please definitely indicate here if I misunderstand any point. I will appreciate the authors to address my confusions, and definitely reconsider my decision. Thank you very much.", "summary_of_the_paper": "This paper studied MARINA method (proposed in a previous work) in distributed nonconvex optimization problems. With a new assumption on the Hessian variance, the paper extend the original analysis of MARINA to accomodate correlated compressor, which avoid the independent compressor setting and can lead to improvement to the communcation complexity in a case when the number of dimension is larger than that of component.", "summary_of_the_review": "The paper improves the analysis of MARINA algorithm, but the introduced new assumptions need to be further justified.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2MLO7wA-ODh", "reviewer": "Reviewer_YEbP", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 proposition of studying correlated compressors in a distributed environment is good, but I'm a little confused on the motivation -- why is the hypothesis limited on MARINA but not on other algorithms? To me the hypothesis is fairly simple and interesting: in a distributed setting, workers follow parameter server architecture and communicate via compressed gradients, how will the correlation in the compressors affect the convergence? This should be independent to the algorithm itself. Actually, some analysis have already been done in the literature, for instance (Acharya et al., 2019)(Acharya et al., 2020), which are analyzed in more general cases. Same question for the Hessian variance part: could you elaborate why this is specific for MARINA? Understanding a newly proposed algorithm is great, but the contribution of a paper seems limited if the results only hold on one algorithm.\n\nThe idea of PermK, where unbiased sparsifier is constructed via some random state and selected coordinates are enlarged, seems to be overlapped with (Jianqiao et al., 2017). In that paper, unbiased gradient sparsification is guaranteed in a similar manner. The similar idea can also be found in (Wang et al., 2018). It's unclear to me about the novelty on this method.\n\nThe experiments are done on linear tasks, but it's unclear what hypothesis they are verifying. In the main paper, a new complexity bound on the iteration is shown, but in the experiments all the X-axis are number of bits. They only match when the same compressors are used in each run and number of bits in each case grow linearly with the iteration at the same rate.\n\n\n- Reference\n\nJianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. *Gradient Sparsification for Communication-Efficient Distributed Optimization* https://arxiv.org/pdf/1710.09854.pdf\n\nJayadev Acharya, Clément L. Canonne, Himanshu Tyagi. *Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction* https://arxiv.org/pdf/1812.11476.pdf\n\nJayadev Acharya, Clément L. Canonne, Himanshu Tyagi. *Communication-Constrained Inference and the Role of Shared Randomness* http://proceedings.mlr.press/v97/acharya19a/acharya19a.pdf\n\nHongyi Wang, Scott Sievert, Zachary Charles, Shengchao Liu, Stephen Wright, Dimitris Papailiopoulos *ATOMO: Communication-efficient Learning via Atomic Sparsification* https://arxiv.org/pdf/1806.04090.pdf", "summary_of_the_paper": "This paper extends the analysis to an existing algorithm called MARINA, and proposes two results: 1) Correlated compressors among the workers, and one realization called PermK; In the analysis, an inequality called AB inequality is used to study the compression variance. 2) A new metric called Hessian variance to refine the results of MARINA.", "summary_of_the_review": "Could you take a look at my main review and address the concerns on motivation, PermK and experiments?", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers have agreed that the paper is in borderline. Although the reviewers are not really convinced about the authors’ responses, they still acknowledge that the paper is interesting and developed some new techniques for the analysis of distributed optimization. 

The following concerns are raised by the reviewers from their discussions: 

1) The paper is heavily based on existing work. 
2) The theoretical advantages are based on the regime Hessian variance is 0 or small, but it is not clear if and when the Hessian variance is small for more complicated models, which means we will not know if the theory will be helpful in practice. Although the authors provide some experimental results in the rebuttal showing that $(L_+)^2 / (L_{\pm})^2$ can be large at initial iterations, it is still not clear how long will this advantage keep during training and how much the advantage is.
3) Reviewer wjjy increased the score from 5 to 6, considering that the additional result truly suggests that the implicit setting can hold in some case at the beginning of iteration, which makes the submission a complete story for him/her now, to some extent. But if we are more strict on the evaluation, the experiment result also suggests that the implicit assumption will not hold anymore over iterations, because the ratio is approaching 1 quickly, i.e., $ L_\pm$ is about the same order as $ L_+$, so there is a mismatch between theory and practice, which even brings out the risk that the paper will fail from the beginning because Sec 4.1 will not make sense anymore.
4) On the theory side, two main contributions of this paper is relaxation on the compressors used in MARINA and a new assumption to refine the analysis. These two contributions seem rather limited if only used to analyze this specific algorithm -- it's unclear what the authors mean in practice or how they correlated to the MARINA. For example, it is still hard for us to compare or understand MARINA with another algorithm as we wouldn't know if the improvement from MARINA is due to a better design, or this additional assumption. The reviewer also finds the authors statement that "their analysis focuses on MARINA because it is SOTA" confusing. Different from NLP and vision community where standard benchmarks are usually used to evaluate new models, He/she is confused by what it means for a newly proposed optimization algorithm to be SOTA.
5) Since the paper proposes a specific algorithm named PermK, it's quite reasonable to question how it relates to some previously proposed sparsification methods with similar design such as (Jianqiao et al., 2017). However, the authors insist their main contribution is in theory, and the small-scale experiments comparing with TopK and RandK are sufficient. The reviewer disagrees about this. As communication compression is usually need in larger scales (at least beyond MNIST), and TopK/RandK are not SOTA baselines of sparsification.

The authors are expected to address them for the clarifications in the final version.
Decision: Accept (Poster)