Year: 2021

Abstract:
We study the MARINA method of Gorbunov et al. (2021) – the current state-of-theart distributed non-convex optimization method in terms of theoretical communication complexity. Theoretical superiority of this method can be largely attributed to two sources: the use of a carefully engineered biased stochastic gradient estimator, which leads to a reduction in the number of communication rounds, and the reliance on independent stochastic communication compression operators, 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 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 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 random permutations, for which we coin the term PermK, the use of which leads to O( √ n) (resp. O(1 + d/ √ n)) improvement in the theoretical communication complexity of MARINA in the low Hessian variance regime when d ≥ n (resp. d ≤ 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.

√ n) (resp.
O(1 + d/ √ n)) improvement in the theoretical communication complexity of MARINA in the low Hessian variance regime when d ≥ n (resp. d ≤ 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.
1 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 on 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., 2021). 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 x∈Rd
[ f(x) := 1n n∑ i=1 fi(x) ] , (1)
where n is the number of workers/machines/nodes/devices working in parallel, and fi : Rd → R is a (potentially nonconvex) function representing the loss of the model parameterized by weights x ∈ Rd on training data stored on machine i. While we do not assume the functions {fi} to be convex, we rely on their differentiability, and on the well-posedness of problem (1): Assumption 1. The functions f1, . . . , fn : Rd → R are differentiable. Moreover, f is lower bounded, i.e., there exists f inf ∈ R such that f(x) ≥ f inf for all x ∈ Rd.
We are interested in finding an approximately stationary point of the nonconvex problem (1). That is, we wish to identify a (random) vector x̂ ∈ Rd such that
E [ ‖∇f(x̂)‖2 ] ≤ ε (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 a point with a small gradient (e.g., think of f being linear), which would render problem (2) unsolvable. However, lower boundedness ensures that the problem is well posed. Besides Assumption 1, we rely on the following smoothness assumption:
Assumption 2. There exists a constant L+ > 0 such that 1n ∑n i=1 ‖∇fi(x)−∇fi(y)‖
2 ≤ L2+ ‖x− y‖ 2 for all x, y ∈ Rd. To avoid ambiguity, let L+ be the smallest such number.
While this is a somewhat stronger assumption than mere L−-Lipschitz continuity of the gradient of f (the latter follows from the former by Jensen’s inequality and we have L− ≤ L+), it is weaker than Li-Lipschitz continuity of the gradient of the functions fi (the former follows from the latter with L2+ ≤ 1n ∑ i L 2 i ). So, this is still a reasonably weak assumption.
1.2 A BRIEF OVERVIEW OF THE STATE OF THE ART
To the best of our knowledge, the state-of-the-art distributed method for finding a point x̂ satisfying (2) for the nonconvex problem (1) in terms of the theoretical communication complexity1 is the MARINA method of Gorbunov et al. (2021). MARINA relies on worker-to-server communication compression, and its power resides in the construction of a carefully designed sequence of biased gradient estimators which help the method obtain its superior communication complexity. The method uses randomized compression operators Ci : Rd → Rd to compress messages (gradient differences) at the workers i ∈ {1, 2, . . . , n} before they are communicated to the server. It is assumed that these operators are unbiased, i.e., E [Ci(a)] = a for all a ∈ Rd, and that their variance is bounded as E ‖Ci(a)− a‖2 ≤ ω ‖a‖2 for all a ∈ Rd and some ω ≥ 0. For convenience, let U(ω) be the class of such compressors. A key assumption in the analysis of MARINA is the independence of the compressors {Ci}ni=1. In particular, MARINA solves the problem (1)–(2) in T = 2∆0ε−1(L− + L+ √ (p−1 − 1)ω/n) communication rounds2, where ∆0 := f(x0) − f inf , x0 ∈ Rd is the initial iterate, p ∈ (0, 1] is a parameter defining the probability with which full gradients of the local functions {fi} are communicated to the server, L− > 0 is the Lipschitz constant of the gradient of f , and L+ ≥ L− is a certain smoothness constant associated with the functions {fi}. In each iteration of MARINA, all workers send (at most) pd + (1 − p)ζ floats to the server in expectation, where ζ := maxi supv∈Rd size(Ci(v)), where size(Ci(v)) is the size of the message v compressed by compressor Ci. For an uncompressed vector v we have size(v) = d in the worst case, and if Ci is the RandK sparsifier, then size(Ci(v)) = K. Putting the above together, the communication complexity of MARINA is T (pd+(1−p)ζ), i.e., the product of the number of communication rounds and the communication cost of each round. See Section B for more details on the method and its theoretical properties.
An alternative to the application of unbiased compressors is the practice of applying contractive compressors, such as TopK (Alistarh et al., 2018), together with an error feedback mechanism (Seide et 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.
1For the purposes of this paper, by communication complexity we mean the product of the number of communication rounds sufficient to find x̂ satisfying (2), and a suitably defined measure of the volume of communication performed in each round. As standard in the literature, we assume that the workers-to-server communication is the key bottleneck, and hence we do not count server-to-worker communication. For more details about this highly adopted and studied setup, see Appendix F.
2Gorbunov et al. (2021) present their result with L− replaced by the larger quantity L+. However, after inspecting their proof, it is clear that they proved the improved rate we attribute to them here, and merely used the bound L− ≤ L+ at the end for convenience of presentation only.
1.3 SUMMARY OF CONTRIBUTIONS
(a) Correlated and permutation compressors. We generalize the analysis of MARINA beyond independence by supporting arbitrary unbiased compressors, including compressors that are correlated. In particular, we construct new compressors based on the idea of a random permutation (we called them PermK) which provably reduce the variance caused by compression beyond what independent compressors can achieve. The properties of our compressors are captured by two quantities, A ≥ B ≥ 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 a 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 a 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. (2021).
(c) Improved communication complexity results. We prove iteration complexity and communication complexity results for MARINA, for smooth nonconvex (Theorem 4) and smooth PolyakŁojasiewicz3 (Theorem 5) functions. Our results hold for all unbiased compression operators, including 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. (2021) by up to the factor √ n in the d ≥ n case, and up to the factor 1 + d/ √ n in the d ≤ n case. The improvement factors degrade gracefully as Hessian variance grows, and in the worst case we recover the same complexity as those established by Gorbunov et al. (2021).
(d) Experiments agree with our theory. Our theoretical results lead to predictions which are corroborated through computational experiments. In particular, we perform proof-of-concept testing with carefully engineered synthetic experiments with minimizing the average of nonconvex quadratics, and also test on autoencoder training with the MNIST dataset.
2 BEYOND INDEPENDENCE: THE POWER OF CORRELATED COMPRESSORS
As mentioned in the introduction, MARINA was designed and analyzed to be used with compressors Ci ∈ U(ω) that are sampled independently by the workers. For example, if the RandK sparsification operator is used by all workers, then each worker chooses the K random coordinates to be communicated 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 ω instead4 of ω/n, which would mean no improvement as the number n of workers grows, which is problematic because ω is typically very large5. For this reason, independence is assumed in the analysis of virtually all distributed methods that use unbiased communication compression, including 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 extends its use to a much wider array of (still unbiased) compressors, some of which have interesting theoretical properties and are useful in practice.
2.1 AB INEQUALITY: A TOOL FOR A MORE PRECISE CONTROL OF COMPRESSION VARIANCE
We assume that all compressors {Ci}ni=1 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 1n ∑ i Ci(ai) as a stochastic estimator of 1 n ∑ i ai.
3The PŁ analysis is included in Appendix D. 4This is a consequence of the more general analysis from our paper; Gorbunov et al. (2021) do not consider the case of unbiased compressors without the independence assumption. 5For example, in the case of the RandK sparsification operator, ω = d/K − 1. Since K is typically chosen to be a constant, or a small percentage of d, we have ω = O(d), which is very large, and particularly so for overparameterized models.
Assumption 3 (Unbiasedness). The random operators C1, . . . , Cn : Rd → Rd are unbiased, i.e., E [Ci(a)] = a for all i ∈ {1, 2, . . . , n} and all a ∈ Rd. If these conditions are satisfied, we will write {Ci}ni=1 ∈ U. Assumption 4 (AB inequality). There exist constants A,B ≥ 0 such that the random operators C1, . . . , Cn : Rd → Rd satisfy the inequality
E [∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1n n∑ i=1 ai ∥∥∥∥2 ] ≤ A ( 1 n n∑ i=1 ‖ai‖2 ) −B ∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥2 (3) for all a1, . . . , an ∈ Rd. If these conditions are satisfied, we will write {Ci}ni=1 ∈ U(A,B).
It is easy to observe that whenever the AB inequality holds, it must necessarily be the case that A ≥ B. Indeed, if we fix nonzero a ∈ Rd and choose ai = 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 Ci ∈ U(ωi) for all i ∈ {1, 2, . . . , n}, 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. If Ci ∈ U(ωi) for i ∈ {1, 2, . . . , n}, then {Ci}ni=1 ∈ U(maxi ωi, 0). If we further assume that the compressors are independent, then {Ci}ni=1 ∈ U( 1n maxi ωi, 0).
In Table 1 we provide a list of several compressors that belong to the class U(A,B), and give values of the associated constants A and B.
2.2 WHY CORRELATION MAY HELP
While in the two examples captured by Lemma 1 we hadB = 0, with a carefully crafted dependence between the compressors it is possible for B to be positive, and even as large as A. Intuitively, other things equal (e.g., fixing A), we should want B to be positive, and as large as possible, as the AB inequality says that in such a case the variance of 1n ∑ i Ci(ai) as a stochastic estimator of 1 n ∑ i ai is reduced more dramatically. This is a key intuition behind the usefulness of (appropriately) correlated compressors. We now provide an alternative point of view. Note that
A ( 1 n n∑ i=1 ‖ai‖2 ) −B ∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥2 = A [(1− BA )( 1n n∑ i=1 ‖ai‖2 ) + BAVar(a1, . . . , an) ] , (4)
where Var(a1, . . . , an) := 1n ∑n i=1 ‖ai − ā‖
2 is the variance of the vectors {ai}ni=1 and ā := 1 n ∑n i=1 ai is their average. So, the AB inequality upper bounds the variance of 1 n ∑ i Ci(ai) as A times a particular convex combination of two quantities. Since the latter quantity is always smaller or equal to the former, and can be much smaller, we should prefer compressors which put as much weight on Var(a1, . . . , an) as possible.
2.3 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 in Section 4, such compressors have favorable communication complexity properties. This leads to the following definition: Definition 1 (Input variance compressors). We say that a collection {Ci}ni=1 of unbiased operators form an input variance compressor system if the variance of 1n ∑ i Ci(ai) is controlled by a multiple of the variance of the input vectors {ai}ni=1. That is, if there exists a constant C ≥ 0 such that
E [∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1n n∑ i=1 ai ∥∥∥∥2 ] ≤ CVar(a1, . . . , an) (5)
for all a1, . . . , an ∈ Rd. If these conditions are satisfied, we will write {Ci}ni=1 ∈ IV(C).
In view of (4), if {Ci}ni=1 ∈ U(A,B) and A = B, then {Ci}ni=1 ∈ IV(A).
We now define two input variance compressors based on a random permutation construction.6 The first compressor handles the d ≥ n case, and the second handles the d ≤ 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.7 Since both these new compressors are sparsification operators, in an analogy with the established notation RandK and TopK for sparsification, we will write PermK for our permutationbased sparsifiers. To keep the notation simple, we chose to include simple variants which do not offer freedom in choosing K. Having said that, these simple compressors lead to state-of-the-art communication complexity results for MARINA, and hence not much is lost by focusing on these examples. Let ei be the ith standard unit basis vector in Rd. That is, for any x = (x1, . . . , xd) ∈ Rd we have x = ∑ i xiei.
Definition 2 (PermK for d ≥ n). Assume that d ≥ n and d = qn, where q ≥ 1 is an integer. Let π = (π1, . . . , πd) be a random permutation of {1, . . . , d}. Then for all x ∈ Rd and each i ∈ {1, 2, . . . , n} we define
Ci(x) := n · qi∑
j=q(i−1)+1 xπjeπj . (6)
Note that Ci is a sparsifier: we have (Ci(x))l = nxl if l ∈ {πj : q(i − 1) + 1 ≤ j ≤ qi} and (Ci(x))l = 0 otherwise. So, ‖Ci(x)‖0 ≤ q := K, which means that Ci offers compression by the factor n. Note that we do not have flexibility to choose K; we have K = q = d/n. See Appendix J for implementation details.
Theorem 1. The PermK compressors from Definition 2 are unbiased and belong to IV(1).
In contrast with the collection of independent RandK sparsifiers, which satisfy the AB inequality with A = d/K−1n and B = 0 (this follows from Lemma 1 since ωi = d/K − 1 for all i), PermK satisfies the AB inequality with A = B = 1. While both are sparsifiers, the permutation construction behind PermK introduces a favorable correlation among the compressors: we have 〈Ci(ai), Cj(aj)〉 = 0 for all i 6= j. Definition 3 (PermK for n ≥ d). Assume that n ≥ d, n > 1 and n = qd, where q ≥ 1 is an integer. Define the multiset S := {1, . . . , 1, 2, . . . , 2, . . . , d, . . . , d}, where each number occurs precisely q times. Let π = (π1, . . . , πn) be a random permutation of S. Then for all x ∈ Rd and each i ∈ {1, 2, . . . , n} we define
Ci(x) := dxπieπi . (7)
Note that for each i, Ci from Definition 3 is the Rand1 sparsifier, offering compression factor d. However, the sparsifiers {Ci}ni=1 are not mutually independent. Note that, again, we do not have a choice8 of K in Definition 3: we have K = 1.
Theorem 2. The PermK compressors from Definition 3 are unbiased and belong to IV(A) with A = 1− n−dn−1 .
6More examples of input variance compressors are given in the appendix. 7The general situation is handled in Appendix I. 8It is possible to provide a more general definition of PermK in the n ≥ d case, allowing for more freedom in choosing K. However, such compressors would lead to a worse communication complexity for MARINA than the simple K = 1 variant considered here.
Combining PermK with quantization. It is easy to show that if {Ci}ni=1 ∈ U(A,B), and Qi ∈ U(ωi) are chosen independently of {Ci}ni=1 (we do not require mutual independence of {Qi}), then {Ci ◦Qi}ni=1 ∈ U((maxi ωi + 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).
3 HESSIAN VARIANCE
Working under the same assumptions on the problem (1)–(2) as Gorbunov et al. (2021) (i.e., Assumptions 1 and 2), in this paper we study the complexity of MARINA under the influence of a new quantity, which we call Hessian variance. Definition 4 (Hessian variance). Let L± ≥ 0 be the smallest quantity such that
1 n n∑ i=1 ‖∇fi(x)−∇fi(y)‖2 − ‖∇f(x)−∇f(y)‖2 ≤ L2± ‖x− y‖ 2 , ∀x, y ∈ Rd. (8)
We refer to the quantity L2± by the name Hessian variance.
Recall that in this paper we have so far mentioned four “smoothness” constants: Li (Lipschitz constant of∇fi), L− (Lipschitz constant of∇f ), L+ (see Assumption 2) and L± (Definition 4). To avoid ambiguity, let all be defined as the smallest constants for which the defining in equalities hold. In case the defining inequality does not hold, the value is set to +∞. This convention allows us to formulate the following result summarize the relationships between these quantities.
Lemma 2. L− ≤ L+, L− ≤ 1n n∑ i=1 Li, L2+ ≤ 1n n∑ i=1 L2i , and L 2 + − L2− ≤ L2± ≤ L2+.
It follows that if Li 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 L− and L± are finite, and L± ≤ L+. We are not aware of any prior use of this quantity in the analysis of any optimization methods. Importantly, there are situations when L− is large, and yet the Hessian variance L2± is small, or even zero. This is important as the improvements we obtain in our analysis of MARINA are most pronounced in the regime when Hessian variance is small.
3.1 HESSIAN VARIANCE CAN BE ZERO
We now illustrate on a few examples that there are situations when the values of L− and Li are are large, Hessian variance can be zero. The simplest example is the identical functions regime. Example 1 (Identical functions). Assume that f1 = f2 = · · · = fn. Then L± = 0.
This follows by observing that the left hand side in (8) is zero. Note that while L± = 0, it is possible for L− and L+ to be 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 n grows. This is because when ai = aj for all i, j, 1n ∑ i TopK(ai) = TopK(ai). As the next example shows, Hessian variance is zero even if we we perturb the local functions via arbitrary linear functions.
Example 2 (Identical functions + arbitrary linear perturbation). Assume that fi(x) = φ(x)+ b>i x+ ci, for some differentiable function φ : Rd → R and arbitrary bi ∈ Rd and ci ∈ R. Then L± = 0.
This follows by observing that the left hand side in (8) is zero in this case as well. Note that in this example it is possible for the functions {fi} to have arbitrarily different minimizers. So, this 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 Hessian variance may be small but not necessarily zero, we establish a useful second order characterization.
Theorem 3. Assume that for each i ∈ {1, 2, . . . , n}, the function fi is twice continuously differentiable. Fix any x, y ∈ Rd and define9
Hi(x, y) := ∫ 1 0 ∇2fi(x+ t(y − x)) dt, H(x, y) := 1n n∑ i=1 Hi(x, y). (9)
Then the matrices Li(x, y) := H2i (x, y), L−(x, y) := H 2(x, y), L+(x, y) := 1n ∑n i=1 H 2 i (x, y) and L±(x, y) := L+(x, y)−L−(x, y) are symmetric and positive semidefinite. Moreover,
L2i = sup x,y∈Rd,x 6=y
(x−y)>Li(x,y)(x−y) ‖x−y‖2 , L 2 − = sup
x,y∈Rd,x 6=y
(x−y)>L−(x,y)(x−y) ‖x−y‖2 ,
L2+ = sup x,y∈Rd,x 6=y
(x−y)>L+(x,y)(x−y) ‖x−y‖2 , L 2 ± = sup
x,y∈Rd,x 6=y
(x−y)>L±(x,y)(x−y) ‖x−y‖2 .
While L2± is obviously well defined through Definition 4 even when the functions {fi} are not twice differentiable, the term “Hessian variance” comes from the interpretation of L2± in the case of quadratic functions.
Example 3 (Quadratic functions). Let fi(x) = 12x >Aix + b > i x + ci, where Ai ∈ Rd×d are symmetric. Then L2± = λmax( 1 n ∑n i=1 A 2 i − ( 1 n ∑n i=1 Ai) 2 ) , where λmax(·) denotes the largest eigenvalue. Indeed, note that the matrix 1n ∑n i=1 A 2 i − ( 1 n ∑n i=1 Ai )2 can be interpreted as a matrix-valued variance of the Hessians A1, . . . ,An, and L2± measures the size of this matrix in terms of its largest eigenvalue.
See Table 2 for a summary of the examples mentioned above. As we shall explain in Section 4, the data/problem regime when the Hessian variance is small is key to the contributions of this paper.
4 IMPROVED ITERATION AND COMMUNICATION COMPLEXITY
The key contribution of our paper is a more general and more refined analysis of MARINA. In particular, we i) extend the reach of MARINA to the general class of unbiased and possibly correlated compressors {Ci}ni=1 ∈ U(A,B), while ii) providing a more refined analysis in that we take the Hessian variance L2± into account.
Theorem 4. Let Assumptions 1, 2, 3 and 4 be satisfied. Let the stepsize in MARINA be chosen as 0 < γ ≤ 1M , where M = L− + √ 1−p p ( (A−B)L2+ +BL2± ) . Then after T iterations, MARINA
finds point x̂T for which E [∥∥∇f(x̂T )∥∥2] ≤ 2∆0γT .
In particular, by choosing the maximum stepsize allowed by Theorem 4, MARINA converges in T communication rounds, where T is shown in the first row Table 3. If in this result we replace L2± by the coarse estimate L2± ≤ L2+, and further specialize to independent compressors satisfying
9Note that Hi(x, y) is the average of the Hessians of fi on the line segment connecting x and y.
Table 3: The number of communication rounds for solving (1)–(2) by MARINA and EF21.
Method + Compressors T = # Communication Rounds MARINA
⋂
{Ci}ni=1 ∈ U(A,B) (this paper, 2021) O
(
∆0 ε
(
L− +
√
1−p p ( (A−B)L2+ +BL2±
)))
MARINA ⋂ Ci ∈ U(ω) and independent
(Gorbunov et al., 2021) O ( ∆0 ε ( L− + √ 1−p p ω n L+ ))
EF21 ⋂ Ci are α-contractive (Richtárik et al., 2021) O ( ∆0 ε ( L− + ( 1+ √ 1−α α − 1 ) L+ ))
Ci ∈ U(ω) for all i ∈ {1, 2, . . . , n}, then since {Ci}ni=1 ∈ U(ω/n, 0) (recall Lemma 1), our general rate specializes to the result of Gorbunov et al. (2021), which we show in the second row of Table 3.
However, and this is a key finding of our work, in the regime when the Hessian variance L2± is very small, the original result of Gorbunov et al. (2021) can be vastly suboptimal! To show this, in Table 4 we compare the communication complexity, i.e., the # of communication rounds multiplied by the maximum # of floats transmitted by a worker to the sever in a single communication round. We compare the communication complexity of MARINA with the RandK and PermK compressors, and the state-of-the-art error-feedback method EF21 of Richtárik et al. (2021) with the TopK compressor. In all optimization methods, we do not consider the communication complexity of initial steps equal to O(d). In each case we optimized over the parameters of the methods (e.g., p for MARINA and K in all cases; for details see Appendix L). Our results for MARINA with PermK are better than the competing methods (recall Lemma 2).
4.1 IMPROVEMENTS IN THE IDEAL ZERO-HESSIAN-VARIANCE REGIME
To better understand the improvements our analysis provides, let us consider the ideal regime characterized by zero Hessian variance: L2± = 0. If we now use compressors {Ci}ni=1 ∈ U(A,B) for which A = B, which is the case for PermK, then the dependence on the potentially very large quantity L2+ is eliminated completely.
Big model case (d ≥ n). In this case, and using the PermK compressor, MARINA has communication complexity O(L−∆0ε−1d/n), while using the RandK compressor, the communication complexity of MARINA is no better than O(L−∆0ε−1d/√n). Hence, we get an improvement by at least the factor √ n. Moreover, note that this is an n× improvement over gradient descent (GD) (Khaled & Richtárik, 2020) and EF21, both of which have communication complexity O(L−∆0ε−1d). In Appendix M, we discuss how we can get the same theoretical improvement even if L2± > 0.
Big data case (d ≤ n). In this case, and using the PermK compressor, MARINA achieves communication complexity O(L−∆0ε−1), while using the RandK compressor, the communication complexity of MARINA is no better than O(L−∆0ε−1(1 + d/√n)). Hence, we get an improvement by at least the factor 1 + d/ √ n. Moreover, note that this is a d× improvement over gradient descent (GD) and EF21, both of which have communication complexity O(L−∆0ε−1d).
5 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 dependencies that our theory predicts. In the second experiment, we consider practical machine learning 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 a synthetic (strongly convex) quadratic function f = 1n ∑ fi composed of nonconvex quadratics fi(x) := 1 2x >Aix − x>bi, where bi ∈ Rd, Ai ∈ Rd×d, and Ai = A>i . We enforced that f is λ–strongly
convex, i.e., 1n ∑n i=1 Ai < λI for λ > 0. We fix λ = 1e−6, and dimension d = 1000 (see Figure 1). We then generated optimization tasks with the number of nodes n ∈ {10, 1000, 10000} and L± ∈ {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 PermK outperforms RandK, and their differences in the plots reproduce dependencies from Table 4. Moreover, when n ∈ {1000, 10000} and L± ≤ 0.21, EF21 with TopK has worse performance than MARINA with PermK, while in heterogeneous regime, when L± = 0.91, TopK is superior except when n = 10000. See Appendix A for detailed experiments.
5.2 TRAINING AN AUTOENCODER WITH MNIST
Now we compare compressors from Section 5.1 on the MNIST dataset (LeCun et al., 2010). Our current goal is to learn the linear autoencoder,
min D∈Rdf×de ,E∈Rde×df
[ f(D,E) := 1N N∑ i=1 ‖DEai − ai‖2 ] ,
where ai ∈ Rdf are MNIST images, df = 784 is the number of features, de = 16 is the size of encoding space. Thus the dimension of the problem d = 25088, and compressors send at most 26 floats in each communication round since we take n = 1000. We use parameter p̂ to control the homogeneity of MNIST split among n nodes: if p̂ = 1, then all nodes store the same data, and if p̂ = 0, then nodes store different splits (see Appendix A.5). In Figure 2, one plot for each compressor with the best convergence rate is provided for p̂ ∈ {0, 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 a grid search as before. In all experiments, PermK outperforms RandK. Moreover, we see that in the more homogeneous regimes, when p̂ ∈ {0.9, 1.0}, PermK converges faster than TopK. When p̂ = 0.75, both compressors have almost the same performance. In the heterogenous regime, when p̂ ∈ {0, 0.5}, TopK is faster than PermK; however, the difference between them is tiny compared to RandK.
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-efficient 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 compression for distributed learning. arXiv preprint arXiv:2002.12410, 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877–1901. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/ 1457c0d6bfcb4967418bfb8ac142f64a-Paper.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 Processing 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 nonconvex distributed learning with compression. In 38th International Conference on 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 arXiv:1905.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 on Machine Learning (ICML), 2019.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03329, 2020.
Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint arXiv:1806.06573, 2018.
Donald E. Knuth. The Art of Computer Programming, Volume 2 (3rd Ed.): Seminumerical Algorithms. 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://yann.lecun.com/exdb/mnist, 2, 2010.
Zhize Li, Dmitry Kovalev, Xun Qian, and Peter Richtárik. Acceleration for compressed gradient descent in distributed and federated optimization. In International Conference on Machine Learning, 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp. 6286–6295. PMLR, 2021.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09269, 2019.
Lam Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In The 34th International Conference on Machine Learning, 2017.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006.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 arXiv:2106.05203, 2021.
Mher Safaryan, Rustem Islamov, Xun Qian, and Peter Richtárik. FedNL: 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-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:1909.05350, 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 stochastic gradient descent with double-pass error-compensated compression. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6155–6165, Long Beach, California, USA, 09–15 Jun 2019. PMLR. URL http://proceedings.mlr.press/ v97/tang19d.html.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł 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 Associates, Inc., 2017. URL https://proceedings.neurips.cc/paper/2017/file/ 3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: 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 on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 5325–5333, StockholmsmĂ¤ssan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
Appendix CONTENTS
1 Introduction 1
1.1 The problem and assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 A brief overview of the state of the art . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Summary of contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2 Beyond Independence: The Power of Correlated Compressors 3
2.1 AB inequality: a tool for a more precise control of compression variance . . . . . . 3
2.2 Why correlation may help . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Input variance compressors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4 PermK: permutation based sparsifiers . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Hessian Variance 6
3.1 Hessian variance can be zero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Second order characterization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4 Improved Iteration and Communication Complexity 7
4.1 Improvements in the ideal zero-Hessian-variance regime . . . . . . . . . . . . . . 8
5 Experiments 8
5.1 Testing theoretical predictions on a synthetic quadratic problem . . . . . . . . . . 9
5.2 Training an autoencoder with MNIST . . . . . . . . . . . . . . . . . . . . . . . . 9
A Extra Experiments 14
A.1 Experiments setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.2 Experiment with quadratic optimization tasks: full description . . . . . . . . . . . 14
A.3 Comparison of MARINA with RandK and MARINA with PermK on quadratic optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.4 Comparison of EF21 with TopK and MARINA with PermK on quadratic optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.5 Experiment with MNIST: full description . . . . . . . . . . . . . . . . . . . . . . 18
A.6 Comparison of MARINA with RandK and MARINA with PermK on MNIST dataset 18
A.7 Comparison of EF21 with TopK and MARINA with PermK on MNIST dataset . . 19
B MARINA Algorithm 20
C Missing Proofs 22
C.1 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
C.2 Proof of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
C.3 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
C.4 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
C.5 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
C.6 Proof of Theorem 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
D Polyak-Łojasiewicz Analysis 29
D.1 Proof of Lemma 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
D.2 Proof of Theorem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
E EF21 Analysis 31
E.1 EF21 rate in the non-convex regime . . . . . . . . . . . . . . . . . . . . . . . . . 31
E.2 EF21 in PŁ regime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
F Communication Model 34
G On Contractive Compressors and Error Feedback 34
G.1 On Contractive Compressors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
G.2 On Error Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
H Composition of Compressors with AB Assumption and Unbiased Compressors 36
I General Examples of PermK 37
I.1 Case d ≥ n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 I.2 Case n ≥ d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
J Implementation Details of PermK 39
K More Examples of Permutation-Based Compressors 39
K.1 Block permutation compressor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
K.2 Permutation of mappings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
L Analysis of Complexity Bounds 43
L.1 Nonconvex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
L.1.1 Case n ≤ d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 L.1.2 Case n ≥ d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
L.2 PŁ assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
L.2.1 Case n ≤ d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 L.2.2 Case n ≥ d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
M Group Hessian Variance 49
A EXTRA EXPERIMENTS
In this section, we provide more detailed experiments and explanations.
A.1 EXPERIMENTS SETUP
All methods are implemented in Python 3.6 and run on a 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 one machine.
In all experiments, we compare MARINA algorithm with RandK compressor and PermK compressor and EF21 with TopK side-by-side. In RandK and TopK, we take K = dd/ne; we show in Lemma 13 that K = dd/ne is optimal for RandK. For TopK, the optimal rate predicted by the current state-of-the-art theory is obtained when K = d (however, in practice, TopK works much better when K d). Lastly, we have the pessimistic assumption that L2± and L2+ are equal to their upper bound 1n ∑n i=1 L 2 i .
A.2 EXPERIMENT WITH QUADRATIC OPTIMIZATION TASKS: FULL DESCRIPTION
First, we present Algorithm 1 which is used in the experiments of Section 5.1. The algorithm is designed to generate sparse quadratic optimization tasks where we can control L± 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 1 Quadratic optimization task generation 1: Parameters: number nodes n, dimension d, regularizer λ, and noise scale s. 2: for i = 1, . . . , n do 3: Generate random noises νsi = 1 + sξ s i and ν b i = sξ b i , i.i.d. ξ s i , ξ b i ∼ N (0, 1)
4: Take vector bi = νsi 4 (−1 + ν b i , 0, · · · , 0) ∈ Rd 5: Take the initial tridiagonal matrix
Ai = νsi 4  2 −1 0 −1 . . . . . . . . . . . . −1
0 −1 2  ∈ Rd×d 6: end for 7: Take the mean of matrices A = 1n ∑n i=1 Ai 8: Find the minimum eigenvalue λmin(A) 9: for i = 1, . . . , n do
10: Update matrix Ai = Ai + (λ− λmin(A))I 11: end for 12: Take starting point x0 = ( √ d, 0, · · · , 0) 13: Output: matrices A1, · · · ,An, vectors b1, · · · , bn, starting point x0
Homogeneity of optimizations tasks is controlled by noise scale s; indeed, with noise scale equal to zero, all matrices are equal, and, by increasing noise scale, functions become less “similar” and L2± grows. In Section 5.1, we take noise scales s ∈ {0, 0.05, 0.1, 0.2, 0.8}. In Figure 3, we provide the same experiments as in Section 5.1 but with λ = 0.0001 to capture dependencies under PŁ condition. Here, we also see that PermK has better performance when the number of nodes n ≥ 1000 and L± ≤ 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 of RandK and PermK with different step sizes (see Figure 4 and Figure 5). We omitted plots where algorithms
diverged. We can see that in all experiments, PermK behaves better than RandK and tolerates larger step sizes. The improvement becomes more significant when n increases.
A.4 COMPARISON OF EF21 WITH TOPK AND MARINA WITH PERMK 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 omitted plots where algorithms diverged. As we can see, when L± ≤ 0.21 and n ≥ 10000, PermK converges faster than TopK. While in heterogeneous regimes, when L± is large, TopK has better performance except when n = 10000. When n > d, we see that PermK converges faster in all experiments.
A.5 EXPERIMENT WITH MNIST: FULL DESCRIPTION
We introduce parameter p̂. Initially, we randomly split MNIST into n + 1 parts: D0, D1, · · · , Dn, where n = 1000 is the number of nodes. Then, for all i ∈ {1, . . . , n}, the ith node takes split D0 with probability p̂, or split Di with probability 1 − p̂. We define the chosen split as D̂i. Using probability p̂, we control the homogeneity of our distribution optimization task. Note that if p̂ = 1, all nodes store the same data D0, and if p̂ = 0, nodes store different splits Di.
Let us consider the more general optimization problem than in Section 5.2. We optimize the following non-convex loss with regularization:
min D∈Rdf×de ,E∈Rde×df
[ f(D,E) := 1N N∑ i=1 ‖DEai − ai‖2 + λ2 ‖DE − I‖ 2 F ] ,
where ai ∈ Rdf are MNIST images, df = 784 is the number of features, de = 16 is the size of encoding space. regularizer λ ≥ 0. Each node stores function
fi(D,E) := 1
|D̂i| ∑ j∈D̂i ‖DEaj − aj‖2 + λ 2 ‖DE − I‖2F , ∀i ∈ {1, . . . , n}.
In Figure 8, one plot for each compressor with the best convergence rate is provided for λ = {0, 0.00001, 0.001} and p̂ = {0, 0.5, 0.75, 0.9, 1.0}. We see that in homogeneous regimes, when p̂ ∈ {0.9, 1.0}, PermK outperforms other compressors for any λ. And the larger the regularization parameter λ, the faster PermK convergences compared to rivals.
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 9). We omitted plots where algorithms diverged. We see that in all experiments, PermK is better than RandK. Practical experiments on MNIST fully reproduce dependencies from our theory and experiments with synthetic quadratic optimization tasks from Section 5.1.
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 RandK and PermK with different step sizes (see Figure 10). We omitted plots where algorithms diverged. We see that, when p̂ ∈ {0.9, 1.0}, PermK tolerates larger step sizes and convergences faster than TopK. When a probability p̂ ∈ {0, 0.5}, both compressors approximately tolerate the same step sizes, but TopK has a better performance when λ ∈ {0, 0.00001}.
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 et al., 2021). In its simplest variant, MARINA performs iterations of the form
xk+1 = xk − γgk, gk = 1 n n∑ i=1 gki , (10)
where gki is a carefully designed biased estimator of the gradient ∇fi(xk), and γ > 0 is a learning rate. The gradient estimators used in MARINA are initialized to the full gradients, i.e., g0i = ∇fi(x0), for i ∈ {1, . . . , n}, and subsequently updated as
gk+1i = { ∇fi(xk+1) if θk = 1 gk + Cki (∇fi(xk+1)−∇fi(xk)) if θk = 0 ,
where θk is a Bernoulli random variable sampled at iteration k (equal to 1 with probability p ∈ (0, 1], and equal to 0 with probability 1 − p), and Ci : Rd → Rd is a randomized compression operator sampled at iteration k on node i independently from other nodes. In particular, Gorbunov et al. (2021) assume that the compression operators Ci are unbiased, and that their variance is proportional to squared norm of the input vector:
E [Ci(x)] = x, E [ ‖Ci(x)− x‖2 ] ≤ ωi ‖x‖2 , ∀x ∈ Rd.
In each iteration of MARINA, the gradient estimator is reset to the true gradient with (small) probability p. Otherwise, each worker i compresses the difference of the last two local gradients, and communicates the compressed message
mki = Cki (∇fi(xk+1)−∇fi(xk))
to the server. These messages are then aggregated by the server to form the new gradient estimator via
gk+1 = gk + 1
n n∑ i=1 mki .
Note that i) this preserves the second relation in (10), ii) the server can compute gk+1 since it has access to gk, which is the case (via a recursive argument) if g0 is known by the server at the start of the iterative process10.
Algorithm 2 MARINA 1: Input: starting point x0, stepsize γ, probability p ∈ (0, 1], number of iterations T 2: Initialize g0 = ∇f(x0) 3: for k = 0, 1, . . . , T − 1 do 4: Sample θt ∼ Be(p) 5: Broadcast gt to all workers 6: for i = 1, . . . , n in parallel do 7: xt+1 = xt − γgt 8: Set gt+1i = ∇fi(xt+1) if θt = 1, and g t+1 i = g t + Ci ( ∇fi(xt+1)−∇fi(xt) ) otherwise
9: end for 10: gt+1 = 1n ∑n i=1 g t+1 i 11: end for 12: Output: x̂T chosen uniformly at random from {xt}T−1k=0
Further, note that the expected communication cost in each iteration of MARINA is equal to
Comm = pd+ (1− p)ζ, ζ = max i ζi,
10This is done by each worker sending the full gradient g0i = ∇fi(x0) to the server at initialization.
where d is the cost of communicating a (possibly dense) vector in Rd, and ζi ≤ d is the expected cost of communicating a vector compressed by Ci. MARINA one of the very few examples in stochastic optimization where the use of a biased estimator leads to a 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).
C MISSING PROOFS
C.1 PROOF OF LEMMA 1
Lemma 1. If Ci ∈ U(ωi) for i ∈ {1, 2, . . . , n}, then {Ci}ni=1 ∈ U(maxi ωi, 0). If we further assume that the compressors are independent, then {Ci}ni=1 ∈ U( 1n maxi ωi, 0).
Proof. Let us first assume unbiasedness only. By Jensen’s inequality,∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 ≤ 1 n n∑ i=1 ‖Ci(ai)− ai‖2 .
It remains to apply expectation on both sides and then use inequality E [ ‖Ci(ai)− ai‖2 ] ≤ ωi ‖ai‖2 ,∀i ∈ {1, . . . , n},
to conclude that {Ci}ni=1 ∈ U(maxi ωi, 0). Let us now add the assumption of independence.
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 
= E ∥∥∥∥∥ 1n n∑ i=1 (Ci(ai)− ai) ∥∥∥∥∥ 2 
= 1
n2 n∑ i=1 E [ ‖Ci(ai)− ai‖2 ] + 1 n2 ∑ i 6=j E [〈Ci(ai)− ai, Cj(aj)− aj〉]
≤ maxi ωi n2 n∑ i=1 ‖ai‖2 ,
by independence, thus, A = maxi ωi/n, B = 0.
C.2 PROOF OF LEMMA 2 Lemma 2. L− ≤ L+, L− ≤ 1n n∑ i=1 Li, L2+ ≤ 1n n∑ i=1 L2i , and L 2 + − L2− ≤ L2± ≤ L2+.
Proof. Let us define
L−(x, y) := ‖∇f(x)−∇f(y)‖2 ,
L+(x, y) := 1
n n∑ i=1 ‖∇fi(x)−∇fi(y)‖2 ,
L±(x, y) := L+(x, y)− L−(x, y). The inequalities are now established as follows:
1. By Jensen’s inequality and the definition of L+,
L−(x, y) ≤ L+(x, y) ≤ L2+ ‖x− y‖ 2 ,
thus, L− is at most L+.
2. By the triangle inequality, we have
‖∇f(x)−∇f(y)‖ ≤ 1 n n∑ i=1 ‖∇fi(x)−∇fi(y)‖ ≤ 1 n n∑ i=1 Li ‖x− y‖ ,
thus L− is at most 1n ∑n i=1 Li.
3. From the definition of Li, we have
L+(x, y) = 1
n n∑ i=1 ‖∇fi(x)−∇fi(y)‖2 ≤ 1 n n∑ i=1 L2i ‖x− y‖ 2 ,
and L2+ is at most 1 n ∑n i=1 L 2 i .
4. The right inequality follows from L−(x, y) ≥ 0 and
L±(x, y) ≤ L+(x, y) ≤ L2+ ‖x− y‖ 2 .
Now, we prove the left inequality. From the definition of L±, we have
L±(x, y) ≤ L2± ‖x− y‖ 2 ,
and
L±(x, y) = L+(x, y)− L−(x, y),
hence,
L+(x, y) ≤ L2± ‖x− y‖ 2 + L−(x, y) ≤ (L2− + L2±) ‖x− y‖ 2 ,
thus L2+ ≤ L2− + L2±.
C.3 PROOF OF THEOREM 1
Theorem 1. The PermK compressors from Definition 2 are unbiased and belong to IV(1).
Proof.
We fix any x ∈ Rd and prove unbiasedness:
E [Ci(x)] = n qi∑
j=q(i−1)+1
E [ xπjeπj ] = n  qi∑ j=q(i−1)+1 1 d d∑ i=1 xiei  = nq d x = x.
Next, we find the second moment: E [ ‖Ci(x)‖2 ] = n2
qi∑ j=q(i−1)+1 E [ |xπj |2 ] = n2 qi∑ j=q(i−1)+1 1 d d∑ i=1 |xi|2 = n2 q d ‖x‖2 = n ‖x‖2 .
For all a1, . . . , an ∈ Rd, the following inequality holds:
E ∥∥∥∥∥ 1n∑ i=1 Ci(ai) ∥∥∥∥∥ 2  = 1 n2 n∑ i=1 E [ ‖Ci(ai)‖2 ] + ∑ i6=j E [〈Ci(ai), Cj(aj)〉]
= 1
n2 n∑ i=1 E [ ‖Ci(ai)‖2 ] = 1
n n∑ i=1 ‖ai‖2 .
Hence, Assumption 4 is fulfilled with A = B = 1.
C.4 PROOF OF THEOREM 2
Theorem 2. The PermK compressors from Definition 3 are unbiased and belong to IV(A) with A = 1− n−dn−1 .
Proof.
We fix any x ∈ Rd and prove unbiasedness:
E [Ci(x)] = dE [xπieπi ] = d 1
d d∑ i=1 xiei = x.
Next, we find the second moment:
E [ ‖Ci(x)‖2 ] = 1
d d∑ i=1 d2|xi|2 = d ‖x‖2 .
For all i 6= j ∈ {1, 2, . . . , n}, x, y ∈ Rd, we have E [〈Ci(x), Cj(y)〉] = E [ 〈Ci(x), Cj(y)〉|πi = πj ]Prob (πi = πj)
= (q − 1)
(n− 1)d d∑ q=1 E [ 〈Ci(x), Cj(y)〉|πi = d, πj = d]
= (q − 1)
(n− 1)d d∑ q=1 d2xqyq
= (q − 1)d n− 1 〈x, y〉 .
For all a1, . . . , an ∈ Rd, the following inequality holds:
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai) ∥∥∥∥∥ 2  = 1 n2 n∑ i=1 E [ ‖Ci(ai)‖2 ] + 1 n2 ∑ i6=j E [〈Ci(ai), Cj(aj)〉]
= d
n2 n∑ i=1 ‖ai‖2 + 1 n2 ∑ i6=j E [〈Ci(ai), Cj(aj)〉]
= d
n2 n∑ i=1 ‖ai‖2 + (q − 1)d n2(n− 1) ∑ i 6=j 〈ai, aj〉
=
( d
n − (q − 1)d n(n− 1)
) 1
n n∑ i=1 ‖ai‖2 + (q − 1)d n− 1 ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ = ( 1− n− d
n− 1
) 1
n n∑ i=1 ‖ai‖2 + n− d n− 1 ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ . Hence, Assumption 4 is fulfilled with A = B = 1− n−dn−1 .
C.5 PROOF OF THEOREM 3
Theorem 3. Assume that for each i ∈ {1, 2, . . . , n}, the function fi is twice continuously differentiable. Fix any x, y ∈ Rd and define11
Hi(x, y) := ∫ 1 0 ∇2fi(x+ t(y − x)) dt, H(x, y) := 1n n∑ i=1 Hi(x, y). (9)
11Note that Hi(x, y) is the average of the Hessians of fi on the line segment connecting x and y.
Then the matrices Li(x, y) := H2i (x, y), L−(x, y) := H 2(x, y), L+(x, y) := 1n ∑n i=1 H 2 i (x, y) and L±(x, y) := L+(x, y)−L−(x, y) are symmetric and positive semidefinite. Moreover,
L2i = sup x,y∈Rd,x 6=y
(x−y)>Li(x,y)(x−y) ‖x−y‖2 , L 2 − = sup
x,y∈Rd,x 6=y
(x−y)>L−(x,y)(x−y) ‖x−y‖2 ,
L2+ = sup x,y∈Rd,x 6=y
(x−y)>L+(x,y)(x−y) ‖x−y‖2 , L 2 ± = sup
x,y∈Rd,x 6=y
(x−y)>L±(x,y)(x−y) ‖x−y‖2 .
Proof. The fundamental theorem of calculus says that for any continuously differentiable function ψ : R→ R we have ψ(1)− ψ(0) = ∫ 1
0
ψ′(t)dt.
Choose i ∈ {1, 2, . . . , n}, j ∈ {1, 2, . . . , d}, distinct vectors x, y ∈ Rd, and let ψij(t) := 〈∇fi(x+ t(y − x)), ej〉,
where ej ∈ Rd is the jth standard unit basis vector. Since fi is twice continuously differentiable, ψij is continuously differentiable, and by the chain rule,
ψ′ij(t) = 〈∇2fi(x+ t(y − x))(y − x), ej〉. Applying the fundamental theorem of calculus, we get
ψij(1)− ψij(0) = ∫ 1
0
〈∇2fi(x+ t(y − x))(y − x), ej〉dt. (11)
Let ψi : R → Rd be defined by ψi(t) := ∇fi(x + t(y − x)) = (ψi1(t), . . . , ψid(t)). Combining equations 11 for j = 1, 2, . . . , d into a vector form using the fact that∫ 1
0
〈∇2fi(x+ t(y − x))(y − x), ej〉dt = 〈(∫ 1
0
∇2fi(x+ t(y − x))dt ) (y − x), ej 〉
we arrive at the identity ∇fi(y)−∇fi(x) = ψi(1)− ψi(0)
(11) = (∫ 1 0 ∇2fi(x+ t(y − x))dt ) (y − x)
(9) = Hi(x, y)(y − x). (12)
Next, since ∇2fi(x + t(y − x)) is symmetric for all t, so is Hi(x, y), and hence Li(x, y) := H2i (x, y) = H > i (x, y)Hi(x, y), which also means that Li(x, y) is symmetric and positive semidefinite. Combining these observations, we obtain
‖∇fi(x)−∇fi(y)‖2 (12) = (x− y)>Li(x, y)(x− y). (13)
Clearly,
L2i = sup x,y∈Rd,x6=y
‖∇fi(x)−∇fi(y)‖2
‖x− y‖2 (13) = sup x,y∈Rd,x 6=y (x− y)>Li(x, y)(x− y) ‖x− y‖2 .
Using the same reasoning, we have∇f(y)−∇f(x) = H(x, y)(y − x), and
L2− = sup x,y∈Rd,x 6=y
‖∇f(x)−∇f(y)‖2
‖x− y‖2 = sup x,y∈Rd,x 6=y (x− y)>L−(x, y)(x− y) ‖x− y‖2 ,
where L(x, y) := H2(x, y) = H>(x, y)H(x, y) is symmetric and positive semidefinite, since Hi(x, y) are symmetric and positive semidefinite. Finally,
L2+ = sup x,y∈Rd,x 6=y
1 n ∑n i=1 ‖∇fi(x)−∇fi(y)‖ 2
‖x− y‖2
= sup x,y∈Rd,x 6=y
(x− y)> (
1 n ∑n i=1 H 2 i (x, y) ) (x− y)
‖x− y‖2
= sup x,y∈Rd,x 6=y (x− y)>L+(x, y)(x− y) ‖x− y‖2 ,
and
L2± = sup x,y∈Rd,x6=y
1 n ∑n i=1 ‖∇fi(x)−∇fi(y)‖ 2 − ‖∇f(x)−∇f(y)‖2
‖x− y‖2
= sup x,y∈Rd,x 6=y
(x− y)> (
1 n ∑n i=1 H 2 i (x, y)−H2(x, y) ) (x− y)
‖x− y‖2
= sup x,y∈Rd,x 6=y (x− y)>L±(x, y)(x− y) ‖x− y‖2 .
Note, that L+(x, y) inherits symmetry and positive semidefiniteness from H2i (x, y). Symmetry of L±(x, y) is trivial. To prove positive semidefiniteness of L±(x, y), note that
L±(x, y) = 1
n n∑ i=1 H2i (x, y)−H2(x, y)
= 1
n n∑ i=1 (Hi(x, y)−H(x, y) + H(x, y))2 −H2(x, y)
= 1
n n∑ i=1 (Hi(x, y)−H(x, y))2 + 1 n H(x, y) n∑ i=1 (Hi(x, y)−H(x, y))
+ 1
n n∑ i=1 (Hi(x, y)−H(x, y))H(x, y)
= 1
n n∑ i=1 (Hi(x, y)−H(x, y))2 ,
which is positive semidefinite.
C.6 PROOF OF THEOREM 4
Theorem 4. Let Assumptions 1, 2, 3 and 4 be satisfied. Let the stepsize in MARINA be chosen as 0 < γ ≤ 1M , where M = L− + √ 1−p p ( (A−B)L2+ +BL2± ) . Then after T iterations, MARINA
finds point x̂T for which E [∥∥∇f(x̂T )∥∥2] ≤ 2∆0γT .
Proof. In the proof, we follow closely the analysis of Gorbunov et al. (2021) and adapt it to utilize the power of Hessian variance (Definition 4) and AB assumption (Assumption 4). We bound the term E [∥∥gt+1 −∇f(xt+1)∥∥2] in a similar fashion to Gorbunov et al. (2021), 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 (Li et al. (2021)). Suppose that L− is finite and let xt+1 = xt − γgt. Then for any gt ∈ Rd and γ > 0, we have
f(xt+1) ≤ f(xt)− γ 2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 ∥∥gt − xt∥∥2 . (14) Lemma 4 (Richtárik et al. (2021)). Let a, b > 0. If 0 ≤ γ ≤ 1√
a+b , then aγ2 + bγ ≤ 1. Moreover,
the bound is tight up to the factor of 2 since 1√ a+b ≤ min { 1√ a , 1b } ≤ 2√ a+b Next, we get an upper bound of E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1] .
Lemma 5. Let us consider gt+1 from Line 8 of Algorithm 2 and assume, that Assumptions 2, 3 and 4 hold, then
E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1] ≤ (1− p) ((A−B)L2+ +BL2±) ∥∥xt+1 − xt∥∥2
+(1− p) ∥∥gt −∇f(xt)∥∥2 . (15)
Proof. In the view of definition of gt+1, we get
E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1]
= (1− p)E ∥∥∥∥∥gt + 1n n∑ i=1 Ci ( ∇fi(xt+1)−∇fi(xt) ) −∇f(xt+1) ∥∥∥∥∥ 2 ∣∣∣∣∣∣xt+1  = (1− p)E
∥∥∥∥∥ 1n n∑ i=1 Ci ( ∇fi(xt+1)−∇fi(xt) ) −∇f(xt+1) +∇f(xt) ∥∥∥∥∥ 2 ∣∣∣∣∣∣xt+1  + (1− p)
∥∥gt −∇f(xt)∥∥2 . In the last inequality we used unbiasedness of Ci. Next, from AB inequality, we have
E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1] ≤ (1− p)E
∥∥∥∥∥ 1n n∑ i=1 Ci ( ∇fi(xt+1)−∇fi(xt) ) −∇f(xt+1) +∇f(xt) ∥∥∥∥∥ 2 ∣∣∣∣∣∣xt+1  + (1− p)
∥∥gt −∇f(xt)∥∥2 . ≤ (1− p) ( A ( 1
n n∑ i=1 ∥∥∇fi(xt+1)−∇fi(xt)∥∥2)−B ∥∥∇f(xt+1)−∇f(xt)∥∥2) + (1− p)
∥∥gt −∇f(xt)∥∥2 = (1− p) ( (A−B) ( 1
n n∑ i=1
∥∥∇fi(xt+1)−∇fi(xt)∥∥2)
+B
( 1
n n∑ i=1 ∥∥∇fi(xt+1)−∇fi(xt)∥∥2 − ∥∥∇f(xt+1)−∇f(xt)∥∥2)) + (1− p)
∥∥gt −∇f(xt)∥∥2 . Using Assumption 2 and Definition 4, we obtain (15).
We are ready to prove Theorem 4. Defining
Φt := f(xt)− f inf + γ 2p ∥∥gt −∇f(xt)∥∥2 , L̂2 := (A−B)L2+ +BL2±,
and using inequalities (14) and (15), we get E [ Φt+1 ] ≤ E [ f(xt)− f inf − γ
2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 ∥∥gt −∇f(xt)∥∥2] + γ 2p E [ (1− p)L̂2
∥∥xt+1 − xt∥∥2 + (1− p)∥∥gt −∇f(xt)∥∥2] = E [ Φt ] − γ 2 E [∥∥∇f(xt)∥∥2]
+
( γ(1− p)L̂2
2p − 1 2γ + L− 2
) E [∥∥xt+1 − xt∥∥2]
≤ E [ Φt ] − γ 2 E [∥∥∇f(xt)∥∥2]
where in the last inequality we use
γ(1− p)L̂2
2p − 1 2γ + L 2 ≤ 0
following from the stepsize choice and Lemma 4. Summing up inequalities E [ Φt+1 ] ≤ E [Φt] − γ2 E [ ‖∇f(xt)‖2 ] for t = 0, 1, . . . , T − 1 and rearranging the terms, we get
1
T T−1∑ t=0 E [∥∥∇f(xt)∥∥2] ≤ 2 γT T−1∑ t=0 ( E [ Φt ] − E [ Φt+1 ]) = 2 ( E [ Φ0 ] − E [ ΦT ]) γT ≤ 2∆0 γT ,
since g0 = ∇f(x0) and ΦT ≥ 0. Finally, using the tower property and the definition of x̂T (see Section B), we obtain the desired result.
D POLYAK-ŁOJASIEWICZ ANALYSIS
In this section, we analyze the algorithm under Polyak-Łojasiewicz (PŁ) condition. We show that MARINA algorithm with Assumption 5 enjoys a linear convergence rate. Now, we state the assumption and the convergence rate theorem. Assumption 5 (PŁ condition). Function f satisfies Polyak-Łojasiewicz (PŁ) condition, i.e.,
‖∇f(x)‖2 ≥ 2µ(f(x)− f?), ∀x ∈ Rd, (16) where µ > 0 and f? := infx f(x).
Lemma 6. For L− > 0 and µ from Assumption 5 holds that L− ≥ µ. Theorem 5. Let Assumptions 1, 2, 3, 4 and 5 be satisfied and
γ ≤ min  ( L− + √ 2 (1− p) p ( (A−B)L2+ +BL2± ))−1 , p 2µ  , (17) then for xT from MARINA algorithm the following inequality holds:
E [ f(xT )− f? ] ≤ (1− γµ)T ∆0.
We provide the proof to Theorem 5 in Section D.2.
In Table 5, we provide communication complexity of MARINA with PermK and RandK, and EF21 with TopK, optimized w.r.t. parameters of the methods. As in Section 4, we see that MARINA with PermK is not worse than MARINA with RandK (recall Lemma 2).
Let us consider zero Hessian variance regime: L± = 0. When d ≥ n, PermK compressor has communication complexity O (max {dL−/nµ, d}) , while RandK compressor has communication complexity O (max {dL−/√nµ, d}). And the communication complexity of PermK is strictly better when dL−/√nµ > d. Moreover, if d ≤ n and (1 + d/√n) L−/µ > d, then we get the strict improvement of the communication complexity fromO (max {(1 + d/√n) L−/µ, d}) toO (max {L−/µ, d}) over MARINA with RandK.
D.2 PROOF OF THEOREM 5
Theorem 5. Let Assumptions 1, 2, 3, 4 and 5 be satisfied and
γ ≤ min  ( L− + √ 2 (1− p) p ( (A−B)L2+ +BL2± ))−1 , p 2µ  , (17) then for xT from MARINA algorithm the following inequality holds:
E [ f(xT )− f? ] ≤ (1− γµ)T ∆0.
Proof. The analysis is almost the same as in Gorbunov et al. (2021), but we include it for completeness. Let us define
Φt := f(xt)− f inf + γ p ∥∥gt −∇f(xt)∥∥2 , L̂2 := ((A−B)L2+ +BL2±) . As in Appendix C.6, we use (14) and (15) to get that
E [ Φt+1 ] ≤ E [ f(xt)− f inf − γ
2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 ∥∥gt −∇f(xt)∥∥2] + γ p E [ (1− p)L̂2
∥∥xt+1 − xt∥∥2 + (1− p)∥∥gt −∇f(xt)∥∥2] (16)
≤ E [ (1− γµ)(f(xt)− f inf)− ( 1
2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 ∥∥gt −∇f(xt)∥∥2] + γ p E [ (1− p)L̂2
∥∥xt+1 − xt∥∥2 + (1− p)∥∥gt −∇f(xt)∥∥2] = E [ (1− γµ)(f(xt)− f inf) + ( γ
2 + γ p (1− p) )∥∥gt −∇f(xt)∥∥2] + E [( γ
p (1− p)L̂2 − 1 2γ + L− 2 )∥∥xt+1 − xt∥∥2] ≤ (1− γµ)E [ Φt ] .
In the last inequality, we used γp (1 − p)L̂ 2 − 12γ + L− 2 ≤ 0 and γ 2 + γ p (1 − p) ≤ (1 − γµ) γ p , that follow from (17) and Lemma 4. Unrolling E [ Φt+1 ] ≤ (1− γµ)E [Φt] and using g0 = ∇f(x0), we have
E [ f(xT )− f inf ] ≤ E [ ΦT ] ≤ (1− γµ)TΦ0 = (1− γµ)T ( f(x0)− f inf ) .
This concludes the proof.
E EF21 ANALYSIS
We provide convergence proofs of EF21 algorithm from Richtárik et al. (2021) for non-convex and PŁ regimes. They will be almost identical to the one by Richtárik et al. (2021) (indeed, the only change is the constant L+ instead of L̃), but we have decided to include it 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 α-contractive for 0 < α ≤ 1. Define Gti := ‖gti −∇fi(xt)‖ 2 and W t := {gt1, . . . , gtn, xt, xt+1}. For any s > 0 we have
E [ Gt+1i |W t ] ≤ (1− θ(s))Gti + β(s) ∥∥∇fi(xt+1)−∇fi(xt)∥∥2 , (18) where
θ(s) := 1− (1− α)(1 + s), and β(s) := (1− α) ( 1 + s−1 ) . (19)
Lemma 8 (Richtárik et al. (2021)). Let 0 < α ≤ 1 and for s > 0 let θ(s) and β(s) be as in equation 19. Then the solution of the optimization problem
min s
{ β(s)
θ(s) : 0 < s <
α
1− α
} (20)
is given by s∗ = 1√ 1−α − 1. Furthermore, θ(s
∗) = 1− √
1− α, β(s∗) = 1−α 1− √
1−α and√ β(s∗)
θ(s∗) = 1√ 1− α − 1 = 1 α + √ 1− α α − 1 ≤ 2 α − 1. (21)
We are now ready to conduct the proof. Theorem 6. Let Assumptions 1 and 2 hold, and let the stepsize be set as
0 < γ ≤ ( L− + L+ √ β
θ
)−1 . (22)
Fix T ≥ 1 and let x̂T be chosen from the iterates x0, x1, . . . , xT−1 uniformly at random. Then E [∥∥∇f(x̂T )∥∥2] ≤ 2 (f(x0)− f inf )
γT +
E [ G0 ]
θT . (23)
Proof. STEP 1. Recall that Lemma 7 says that E [∥∥gt+1i −∇fi(xt+1)∥∥2 |W t] ≤ (1−θ)∥∥gti −∇fi(xt)∥∥2 +β ∥∥∇fi(xt+1)−∇fi(xt)∥∥2 , (24)
where θ = θ(s∗) and β = β(s∗) are given by Lemma 8. Averaging inequalities equation 24 over i ∈ {1, 2, . . . , n} gives
E [ Gt+1 |W t ] = 1
n n∑ i=1 E [∥∥gt+1i −∇fi(xt+1)∥∥2 |W t]
≤ (1− θ) 1 n n∑ i=1 ∥∥gti −∇fi(xt)∥∥2 + β 1n n∑ i=1 ∥∥∇fi(xt+1)−∇fi(xt)∥∥2 = (1− θ)Gt + β 1
n n∑ i=1 ∥∥∇fi(xt+1)−∇fi(xt)∥∥2 ≤ (1− θ)Gt + βL+
∥∥xt+1 − xt∥∥2 . (25) Using Tower property and L-smoothness in equation 25, we proceed to
E [ Gt+1 ] = E [ E [ Gt+1 |W t ]] ≤ (1− θ) E [ Gt ] + βL2+E [∥∥xt+1 − xt∥∥2] . (26)
STEP 2. Next, using Lemma 3 and Jensen’s inequality applied to the function x 7→ ‖x‖2, we obtain the bound
f(xt+1) ≤ f(xt)− γ 2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 ∥∥∥∥∥ 1n n∑ i=1 ( gti −∇fi(xt) )∥∥∥∥∥ 2
≤ f(xt)− γ 2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 Gt. (27)
Subtracting f inf from both sides of equation 27 and taking expectation, we get E [ f(xt+1)− f inf ] ≤ E [ f(xt)− f inf ] − γ 2 E [∥∥∇f(xt)∥∥2]
− ( 1
2γ − L− 2
) E [∥∥xt+1 − xt∥∥2]+ γ 2 E [ Gt ] . (28)
COMBINING STEP 1 AND STEP 2. Let δt := E [ f(xt)− f inf ] , st := E [Gt] and rt :=
E [∥∥xt+1 − xt∥∥2] . Then by adding equation 28 with a γ2θ multiple of equation 26 we obtain δt+1 + γ
2θ st+1 ≤ δt − γ 2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 ) rt + γ 2 st + γ 2θ ( βL2+r t + (1− θ)st )
= δt + γ 2θ st − γ 2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 − γ 2θ βL2+ ) rt
≤ δt + γ 2θ st − γ 2 ∥∥∇f(xt)∥∥2 . The last inequality follows from the bound γ2 βL 2 +
θ + L−γ ≤ 1, which holds from our assumption on the stepsize and Lemma 4. By summing up inequalities for t = 0, . . . , T − 1, we get
0 ≤ δT + γ 2θ sT ≤ δ0 + γ 2θ s0 − γ 2 T−1∑ t=0 E [∥∥∇f(xt)∥∥2] .
Multiplying both sides by 2γT , after rearranging we get T−1∑ t=0 1 T E [∥∥∇f(xt)∥∥2] ≤ 2δ0 γT + s0 θT .
It remains to notice that the left hand side can be interpreted as E [∥∥∇f(x̂T )∥∥2], where x̂T is chosen
from x0, x1, . . . , xT−1 uniformly at random.
E.2 EF21 IN PŁ REGIME
Theorem 7. Let Assumptions 1, 2 and 5 hold, and let the stepsize in EF21 be set as
0 < γ ≤ min  ( L− + L+ √ 2β θ )−1 , θ 2µ  . (29) Let Ψt := f(xt)− f inf + γθG
t. Then for any T ≥ 0, we have E [ ΨT ] ≤ (1− γµ)TE [ Ψ0 ] . (30)
Proof. Again, this follows Richtárik et al. (2021) almost verbatim.
We proceed as in the previous proof, but use the PŁ inequality and subtract f inf from both sides of equation 27 to get
E [ f(xt+1)− f inf ] ≤ E [ f(xt)− f inf ] − γ
2 ∥∥∇f(xt)∥∥2 − ( 1 2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 Gt
≤ (1− γµ)E [ f(xt)− f inf ] − ( 1
2γ − L− 2 )∥∥xt+1 − xt∥∥2 + γ 2 Gt.
Let δt := E [ f(xt)− f inf ] , st := E [Gt] and rt := E [∥∥xt+1 − xt∥∥2]. Then by adding the above inequality with a γθ multiple of equation 26, we obtain
δt+1 + γ
θ st+1 ≤ (1− γµ)δt −
( 1
2γ − L− 2
) rt + γ
2 st +
γ
θ
( (1− θ)st + βL2+rt ) = (1− γµ)δt + γ
θ
( 1− θ
2
) st − ( 1
2γ − L− 2 − βL2+γ θ
) rt.
Note that our assumption on the stepsize implies that 1 − θ2 ≤ 1 − γµ and 1 2γ − L− 2 −
βL2+γ
θ ≥ 0.
The last inequality follows from the bound γ2 2βL 2 +
θ + γL− ≤ 1, which holds because of Lemma 4 and our assumption on the stepsize. Thus,
δt+1 + γ
θ st+1 ≤ (1− γµ)
( δt + γ θ st ) .
It remains to unroll the recurrence.
F COMMUNICATION MODEL
As mentioned in the introduction, we consider the regime where the worker-to-server communication is the bottleneck of the system so that the server-to-workers communication can be neglected. While this is a standard model used in many prior works, we include a brief explanation of why and when this regime is 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 no 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 to all workers without the need for any additional communication.
2. Fast broadcast. Second, the above regime makes sense in situations where the server exists physically, but is able to broadcast to the workers at a much higher speed compared to the worker-to-server communication. This happens in several distributed systems, e.g., on certain supercomputers (Mishchenko et al., 2019). Virtually all theoretical works on communication efficient distributed algorithms assume that the server-to-worker communication 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 is also costly (Horváth et 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 problem (1) in a communication-efficient manner under the communication model described in Appendix 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 involved: (i) methods that work with contractive (and possibly biased stochastic) compression operators, such as TopK or RankK, and (ii) methods that work with unbiased and independent (across the workers) stochastic compression operators, such as RandK.
A (randomized) compression operator C : Rd → Rd is α-contractive (we write C ∈ C(α)), where 0 < α ≤ 1, if
E [ ‖C(x)− x‖2 ] ≤ (1− α) ‖x‖2 , x ∈ Rd. (31)
A canonical example is the (deterministic) TopK compressor, which outputs the K largest (in absolute value) entries of the input vector x, and zeroes out the rest. TopK is α-contractive with α = K/d. Another example is the RankK compressor based on the best rank-K approximation of x represented as an a×b = dmatrix. It can be shown that RankK is α-contractive with α = K/min{a,b} (Safaryan et al., 2021, Section A.3.2). We refer to the work of Vogels et al. (2019) for a practical communication-efficient method PowerSGD based on low-rank approximations.
Of special importance are α-compressors arising from unbiased compressors via appropriate scaling. LetQ : Rd → Rd be an unbiased operator with variance proportional to the square norm of the input vector. That is, assume that E [Q(x)] = x for all x ∈ Rd and that there exists ω ≥ 0 such that
E [ ‖Q(x)− x‖2 ] ≤ ω ‖x‖2 , ∀x ∈ Rd. (32)
We will write Q ∈ U(ω) for brevity. It is well known that the operator C = (ω + 1)−1Q is α-contractive with α = (ω + 1)−1. An example of a contractive compressor arising this way is
(ω + 1)−1RandK, which keeps a subset of K entries of the input vector x chosen uniformly at random, and zeroes out the rest. As TopK, (ω + 1)−1RandK is α-contractive, with α = K/d.
Distributed SGD methods relying on general contractive compressors, i.e., on contractive which do not arise from unbiased compressors from scaling, need to rely on the error-feedback / errorcompensation mechanism to avoid divergence.
G.2 ON ERROR FEEDBACK
An alternative approach to the one represented by MARINA is to seek more aggressive compression, even at 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 (31), which have studied at least since the work of Seide et al. (2014). Example of such compressors are the TopK (Alistarh et al., 2018) and RankK (Vogels et al., 2019; Safaryan et al., 2021) 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 (exponential) divergence, even in simple problems (Beznosikov et al., 2020). Because of this, Seide 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., 2018; Stich & Karimireddy, 2019; Wu et al., 2018; Koloskova et 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 theoretical communication complexity results for error feedback belong to the EF21 method of Richtárik et al. (2021) 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 L that EF21 with TopK is only proved to have the communication complexity of the gradient descent without any compression.
H COMPOSITION OF COMPRESSORS WITH AB ASSUMPTION AND UNBIASED COMPRESSORS
Lemma 9. If {Ci}ni=1 ∈ U(A,B) and Qi ∈ U(ωi) for i ∈ {1, 2, . . . , n}, then {Ci ◦ Qi}ni=1 ∈ U((maxi ωi + 1)A,B).
Proof. By the tower property, for all a1, . . . , an ∈ Rd, we have
E ∥∥∥∥∥ 1n n∑ i=1 Ci(Qi(ai))− 1 n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2 
= E E ∥∥∥∥∥ 1n n∑ i=1 Ci(Qi(ai))− 1 n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2 ∣∣∣∣∣∣Q1(a1), · · · ,Qn(an)  ≤ E A 1 n n∑ i=1 ‖Qi(ai)‖2 −B ∥∥∥∥∥ 1n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2  .
Since Qi ∈ U(ωi) for i ∈ {1, 2, . . . , n}, we get
E ∥∥∥∥∥ 1n n∑ i=1 Ci(Qi(ai))− 1 n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2 
≤ (
max i ωi + 1
) A 1
n n∑ i=1 ‖ai‖2 −BE ∥∥∥∥∥ 1n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2  .
Using Jensen’s inequality, we derive inequalities:
E ∥∥∥∥∥ 1n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2  ≥ ∥∥∥∥∥ 1n n∑ i=1 E [Qi(ai)] ∥∥∥∥∥ 2 = ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 ,
and
E ∥∥∥∥∥ 1n n∑ i=1 Ci(Qi(ai))− 1 n n∑ i=1 Qi(ai) ∥∥∥∥∥ 2 
≤ (
max i ωi + 1
) A 1
n n∑ i=1 ‖ai‖2 −B ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 .
The last inequality completes the proof.
I GENERAL EXAMPLES OF PERMK
For the sake of clarity, in the main part of our paper, we assumed that n | d or d | n, and provided corresponding examples of PermK (see Definition 2 and Definition 3). Now, we provide two examples of PermK that work with any n and d and generalize the previous examples.
I.1 CASE d ≥ n
The following example generalizes for the case when n does not divide d. Let us assume that d = kn + r and 0 ≤ r < n. As in Definition 2, we permute coordinates and split them into the blocks of sizes {k, . . . , k, r}. The first n block of size k we assign to nodes. Next, we take the last block of size r and randomly assign each coordinate from this block to one node. As the size of the last block of size r is less than n, some nodes will send one coordinate less.
Definition 5 (PermK (d ≥ n)). Let us assume that d ≥ n, d = kn + r, 0 ≤ r < n, πd = (πd1 , . . . , πdd) is a random permutation of {1, · · · , d}, and πn = (πn1 , . . . , π n n) is a random permutation of {1, · · · , n}. We define the tuple of vectors S(x) = (xπdkn+1eπdkn+1 , . . . , xπdkn+reπdkn+r , 0, . . . , 0) of size n. Then,
Ci(x) := n  ki∑ j=k(i−1)+1 xπdj eπdj + (S(x))πni  . Theorem 8. Compressors {Ci}ni=1 from Definition 5 belong to IV(1).
Proof. We fix any x ∈ Rd and prove unbiasedness:
E [Ci(x)] = n  ki∑ j=k(i−1)+1 E [ xπdj eπdj ] + E [ (S(x))πni ] = n ( k
d x+
( 1− r
n
) 0 + r
n
1 d x ) = n ( kn+ r
nd
) x
= x,
for all i ∈ {1, . . . , n}. Next, we derive the second moment:
E [ ‖Ci(x)‖2 ] = n2  ki∑ j=k(i−1)+1 E [∥∥∥xπdj eπdj ∥∥∥2 ] + E [∥∥∥(S(x))πni ∥∥∥2 ]
= n2 ( k
d ‖x‖2 +
( 1− r
n
) ‖0‖2 + r
n
1 d ‖x‖2 ) = n2 ( kn+ r
nd
) ‖x‖2
= n ‖x‖2 ,
We fix x, y ∈ Rd. For all i 6= l ∈ {1, . . . , n}, we have
E [〈Ci(x), Cl(y)〉]
= n2
〈 ki∑
j=k(i−1)+1
xπdj eπdj + (S(x))πni , kl∑ j=k(l−1)+1 yπdj eπdj + (S(y))πnl
〉 = 0,
due to orthogonality of vectors ep, for all p ∈ {1, . . . , d}, and the fact that i 6= l.
Thus, for all a1, . . . , an ∈ Rd, the following equality holds:
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai) ∥∥∥∥∥ 2  = 1 n2 n∑ i=1 E [ ‖Ci(ai)‖2 ] + 1 n2 ∑ i 6=j E [〈Ci(ai), Cj(aj)〉] = 1 n n∑ i=1 ‖ai‖2 .
Hence, Assumption 4 is fulfilled with A = B = 1.
I.2 CASE n ≥ d
The following definition generalizes Definition 3 for the case when d does not divide n. Let us assume that n = qd + r 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 qd to one node. Note that r randomly chosen nodes are idle. Definition 6 (PermK, (n ≥ d)). Let us assume that n ≥ d, n = qd + r, 0 ≤ r < d. Let us fix point x ∈ Rd, that we want to compress. Define the tuple of vectors Ŝ(x) = (x1e1, . . . , x1e1, x2e2, . . . , x2e2, . . . , xded, . . . , xded), where each vector occurs q times. Concat r zero vectors to Ŝ(x): S(x) = Ŝ(x)⊕ (0, . . . , 0). Let π = (π1, . . . , πn) be a random permutation of {1, . . . , n}. Define
Ci(x) := n
q (S(x))πi .
Theorem 9. Compressors {Ci}ni=1 from Definition 6 belong to IV (A) with A = 1− n(q−1) (n−1)q .
Proof. We start with proving the unbiasedness:
E [Ci(x)] = n
q d∑ j=1 xjejProb (πi = j) = n q d∑ j=1 xjej q n = x,
for all i ∈ {1, . . . , n}, x ∈ Rd. Next, we find the second moment:
E [ ‖Ci(x)‖2 ] = n2
q2 d∑ i=1 x2iProb (πi = j) = n q ‖x‖2 ,
for all i ∈ {1, . . . , n}, x ∈ Rd. For all i 6= j ∈ {1, . . . , n} and x, y ∈ Rd, we have
E [〈Ci(x), Cj(y)〉] = n2
q2 d∑ k=1 xkykProb (πi = k, πj = k)
= n2
q2 d∑ k=1 xkyk q(q − 1) n(n− 1) = n(q − 1) (n− 1)q 〈x, y〉 .
Thus, for all a1, . . . , an ∈ Rd, the following equality holds:
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai) ∥∥∥∥∥ 2  = 1 n2 n∑ i=1 E [ ‖Ci(ai)‖2 ] + 1 n2 ∑ i 6=j E [〈Ci(ai), Cj(aj)〉]
= 1
nq n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)q  1 n2 ∑ i6=j 〈ai, aj〉  = ( 1
q − (q − 1) (n− 1)q
) 1
n n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)q ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 .
Hence, Assumption 4 is fulfilled with A = B = 1− n(q−1)(n−1)q .
J IMPLEMENTATION DETAILS OF PERMK
Now, we discuss the implementation details of PermK from Definition 2. Unlike RandK and TopK compressors, PermK compressors are statistically dependent. We provide a 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 2, they are shared between nodes and generated in each communication round. However, instead of sharing the samples, we can generate these samples in each node regardless of other nodes. Almost all random generation libraries and frameworks are deterministic (or pseudorandom) and only depend on 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 a random permutation. The computation complexity of generating a sample from a random permutation π = (π1, . . . , πd) 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.
K MORE EXAMPLES OF PERMUTATION-BASED COMPRESSORS
K.1 BLOCK PERMUTATION COMPRESSOR
In block permutation compressor, we partition the set {1, . . . , d} into m ≤ n disjoint blocks. For each block Pi, ⌊ n m ⌋ devices sparsify their vectors to coordinates with indices in Pi only. Definition 7. Let P to be a partition of the set {1, . . . , d} into m ≤ n non-empty subsets, and n = mq+ r, where 0 ≤ r < m. Define matrices A1, . . . ,An as follows: put Ai := 0 if i > mq. Denote the subsets in P as P1, · · · , Pm. Next, for any Pi ∈ P , we set A(i−1)q+1,A(i−1)q+2, · · · ,Aiq to n q Diag(Pi). Here by Diag(S) we mean the diagonal matrix where each i
th diagonal entry is equal to 1 if i ∈ S and 0 otherwise. Let π = (π1, . . . , πn) be a random permutation of set {1, . . . , n}. We define Ci(x) := Aπix. We call the set {Ci}ni=1 the block permutation compressor. Lemma 10. Compressors {Ci}ni=1 belong to IV(A) with A = 1− n(q−1) (n−1)q .
Proof. We start with the proof of unbiasedness:
E [Ci(x)] = 1
n n∑ i=1 Aπix =
( 1
n · n q m∑ i=1 qDiag(Pi)
) x = Ix = x,
for all i ∈ {1, . . . , n}, x ∈ Rd. Next, we establish the second moment:
E [ ‖Ci(x)‖2 ] = r
n · 0 + m∑ l=1 q n ∑ j∈Pl ∣∣∣∣nq xj ∣∣∣∣2 = qn d∑ j=1 ∣∣∣∣nq xj ∣∣∣∣2 = nq ‖x‖2 ,
for all i ∈ {1, . . . , n}, x ∈ Rd. The following equality will be useful for the AB assumption:
E [〈Ci(x), Cj(y)〉] = E [〈 Aπix,Aπjy 〉] =
m∑ k=1 (∑ l∈Pk n2 q2 xlyl ) Prob (πi ∈ Pk, πj ∈ Pk)
= m∑ k=1 (∑ l∈Pk n2 q2 xlyl ) q(q − 1) n(n− 1)
= n(q − 1) q(n− 1) 〈x, y〉 ,
for all i 6= j ∈ {1, . . . , n}, x, y ∈ Rd. Thus,
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai) ∥∥∥∥∥ 2  = 1 qn n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)qn2 ∑ i 6=j 〈ai, aj〉
=
( 1
qn − n(q − 1) (n− 1)qn2 ) n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)q ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2
=
( (n− 1)− q + 1
(n− 1)q
) 1
n n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)q ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2
= n− q (n− 1)q · 1 n n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)q ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2
= ( 1− n(q − 1)
(n− 1)q
) 1
n n∑ i=1 ‖ai‖2 + n(q − 1) (n− 1)q ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 ,
for all a1, . . . , an ∈ Rd. Hence, Assumption 4 is fulfilled with A = B = 1− n(q−1)(n−1)q .
K.2 PERMUTATION OF MAPPINGS
Definition 8. Let Q1, . . . , Qn : Rd → Rd be a collection of deterministic mappings Rd → Rd. Let π = (π1, . . . , πn) be a random permutation of set {1, . . . , n}, where n > 1. Define Ci := Qπi . Assume that the following conditions hold:
1. There exists ω ≥ 0 such that E [ ‖Ci(x)‖2 ] ≤ (ω + 1) ‖x‖2 for all i ∈ {1, . . . , n},
x, y ∈ Rd.
2. There exists θ ∈ R such that n∑ i=1 〈Qi(x), Qi(y)〉 = θ 〈x, y〉 for all x, y ∈ Rd.
3. 1n n∑ i=1 Qi(x) = x for all x ∈ Rd.
We call the collection {Ci}ni=1 the permutation of mappings.
Lemma 11. Permutation of mappings belongs to U(A,B) with A = ω+1n − 1 n−1 ( 1− θn2 ) and
B = 1− nn−1 ( 1− θn2 ) .
Proof. Unbiasedness follows directly from Condition 3. Let us fix a1, . . . , an ∈ Rd. We shall now establish the AB assumption.
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 
= E ∥∥∥∥∥ 1n n∑ i=1 (Qπi(ai)− ai) ∥∥∥∥∥ 2 
= 1
n2 E  n∑ i=1 ‖Qπi(ai)− ai‖ 2 + ∑ i 6=j 〈 Qπi(ai)− ai, Qπj (aj)− aj 〉 ≤ 1 n2 E ω n∑ i=1 ‖ai‖2 + ∑ i 6=j 〈 Qπi(ai)− ai, Qπj (aj)− aj
〉 = 1
n2 ω n∑ i=1 ‖ai‖2 + E ∑ i 6=j 〈 Qπi(ai), Qπj (aj) 〉−∑ i 6=j 〈ai, aj〉  = 1
n2 ω n∑ i=1 ‖ai‖2 − ∥∥∥∥∥ n∑ i=1 ai ∥∥∥∥∥ 2 + n∑ i=1 ‖ai‖2 + ∑ i 6=j E [〈 Qπi(ai), Qπj (aj) 〉] = (ω + 1)
n
1
n n∑ i=1 ‖ai‖2 − ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 + 1 n2 ∑ i 6=j E [〈 Qπi(ai), Qπj (aj) 〉]
Let us now compute 1n2 ∑ i 6=j E [〈 Qπi(ai), Qπj (aj) 〉] .
1
n2 ∑ i6=j E [〈 Qπi(ai), Qπj (aj) 〉] = 1 n2 ∑ i 6=j
1 n(n− 1) ∑ u 6=v 〈Qu(ai), Qv(aj)〉
= 1 n(n− 1) ∑ i6=j 1 n2 ∑ u 6=v 〈Qu(ai), Qv(aj)〉 .
Now,
1
n2 ∑ u6=v 〈Qu(x), Qv(y)〉 = 1 n2 n∑ u=1 n∑ v=1 〈Qu(x), Qv(y)〉 − 1 n2 n∑ u=1 〈Qu(x), Qv(y)〉
Condition 3 = 〈x, y〉 − 1
n2 n∑ u=1 〈Qu(x), Qu(y)〉
Condition 2 = ( 1− θ
n2
) 〈x, y〉 , ∀x, y ∈ Rd.
Hence,
1
n2 ∑ i 6=j E [〈 Qπi(ai), Qπj (aj) 〉] =
1
n(n− 1)
( 1− θ
n2 )∑ i 6=j 〈ai, aj〉 .
Finally,
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 
≤ (ω + 1) n 1 n n∑ i=1 ‖ai‖2 − ∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 + 1 n(n− 1) ( 1− θ n2 )∑ i 6=j 〈ai, aj〉
=
( ω + 1
n − 1 n− 1
( 1− θ
n2
)) 1
n n∑ i=1 ‖ai‖2 − ( 1− n n− 1 ( 1− θ n2 ))∥∥∥∥∥ 1n n∑ i=1 ai ∥∥∥∥∥ 2 .
Hence, Assumption 4 is fulfilled with A = ω+1n − 1 n−1 ( 1− θn2 ) , B = 1− nn−1 ( 1− θ 2 n ) .
L ANALYSIS OF COMPLEXITY BOUNDS
In this section, we analyze the complexities bounds of optimization methods, and typically these bounds have a structure of a function that we analyze in the following lemma.
Lemma 12. Let us consider function
f(x, y) = (x+ (1− x)y) ( a+ b √( 1 x − 1 )( 1 y − 1 )) ,
where x ∈ (0, 1], y ∈ [ymin, 1], ymin ∈ (0, 1/2], a ≥ 0, and b ≥ 0, then
f(x, y) ≥ 1 2 min{a, aymin + b}, ∀x, y ∈ (0, 1].
Proof. First, let us assume that x ≥ 1/2. Then,
f(x, y) ≥ a 2 .
Second, let us assume that y ≥ 1/2. Then, f(x, y) ≥ a ( x+ 1
2 (1− x)
) ≥ a
2 .
Finally, let us assume, that y ≤ 1/2 and x ≤ 1/2. Then,
f(x, y) = (x+ (1− x)y) ( a+ b √( 1 x − 1 )( 1 y − 1 ))
≥ a(1− x)y + b(x+ (1− x)y)
√( 1 x − 1 )( 1 y − 1 )
≥ a(1− x)y + b(x(1− y) + (1− x)y)
√( 1 x − 1 )( 1 y − 1 )
≥ a(1− x)y + bxy (( 1 y − 1 ) + ( 1 x − 1 ))√( 1 x − 1 )( 1 y − 1 )
≥ a(1− x)y + 2bxy ( 1 x − 1 )( 1 y − 1 )
≥ a(1− x)y + 2b (1− x) (1− y)
≥ aymin 2 + b 2 .
L.1 NONCONVEX OPTIMIZATION
L.1.1 CASE n ≤ d
We analyze case, when n ≤ d. For simplicity, we assume that n | d, n > 1, and d > 1. For PermK from Definition 2, constantsA = B = 1 in AB inequality (see Lemma 1). We define communication complexity of MARINA with PermK asNPermK(p),where p is a parameter of MARINA, and MARINA with RandK as NRandK(p, k), where k is a parameter of RandK. From Theorem 4, we have that oracle complexity of MARINA with PermK is equal to
O (
∆0 ε
( L− + √ 1− p p L± )) .
During each iteration of MARINA, on average, each node sends the number of bits equal to O ( pd+ (1− p) d
n
) ,
thus, the communication complexity predicted by theory is
NPermK(p) := ∆0 ε
( pd+ (1− p) d
n
)( L− + √ 1− p p L± ) (33)
up to a constant factor.
Analogously, for RandK, the communication complexity predicted by theory is
NRandK(p, k) := ∆0 ε (pd+ (1− p)k)
L− + √
1− p p d k − 1 n L+  (34) up to a constant factor. To the best of our knowledge, this is the state-of-the-art theoretical communication complexity bound for the RandK compressor in the non-convex regime.
Finally, for TopK, by Theorem 6, the theoretical communication complexity is
NTopK(k) := ∆0 ε k
( L− + L+ d− k + √ d2 − dk
k
) (35)
up to a constant factor. We consider the variant of EF21, where g0i are initialized with gradients ∇fi(x0), for all i ∈ {1, . . . , n}, thus E [ G0 ] = 0 in Theorem 6.
The following lemma will help us to choose the optimal parameters of NPermK(p), NRandK(p, k), and NTopK(k). Lemma 13. For communication complexity NPermK(p) of MARINA with PermK, communication complexityNRandK(p, k) of MARINA with RandK and communication complexityNTopK(k) of EF21 with TopK defined in (33), (34) and (35) the following inequalities hold:
1. Lower bounds:
NPermK(p) ≥ ∆0 2ε min
{ dL−, d
n L− + dL±√ n
} , ∀p ∈ (0, 1].
Upper bounds:
NPermK
( 1
n
) ≤ 2∆0
ε
( d
n L− + dL±√ n
) , (36)
NPermK (1) = ∆0dL−
ε . (37)
2. Lower bounds:
NRandK(p, k) ≥ ∆0 2ε min
{ dL−,
dL+√ n
} , ∀p ∈ (0, 1],∀k ∈ {1, . . . , d},
Upper bounds: For all k ∈ {1, . . . , d/ √ n}, p = k/d,
NRandK (p, k) ≤ 4∆0dL+ ε √ n . (38)
Moreover, for all k ∈ {1, . . . , d}, p = 1,
NRandK (1, k) = ∆0dL−
ε . (39)
3.
min k∈{1,...,d}
NTopK(k) = NTopK(d) = ∆0dL−
ε (40)
Proof.
1. We start with the first inequality:
NPermK(p) = ∆0 ε
( pd+ (1− p) d
n
)( L− + √ 1− p p L± ) =
∆0 ε
( p+ (1− p) 1
n
)( dL− + dL± √ 1− p p ) =
∆0 ε
( p+ (1− p) 1
n
)( dL− + dL± √ n
n √ 1− p p ) ≥ ∆0
ε
( p+ (1− p) 1
n
)( dL− +
dL±√ n
√( 1 p − 1 ) (n− 1) ) .
Using Lemma 12 with a = dL−, b = dL±√ n , and ymin = 1/n, we get
NPermK(p) = ∆0 ε
( pd+ (1− p) d
n
)( L− + √ 1− p p L± ) ≥ ∆0
2ε min
{ dL−, d
n L− + dL±√ n
} .
for all p ∈ (0, 1]. We can obtain the bound 36 if we take p = 1/n:
NPermK
( 1
n
) =
∆0 ε
( d
n +
( 1− 1
n
) d
n
)( L− + √ n− 1L± ) ≤ 2∆0
ε
( d
n L− + d√ n L±
) .
We obtain the equality 37 by taking p = 1.
2.
NRandK(p, k) = ∆0 ε (pd+ (1− p)k)
L− + √
1− p p d k − 1 n L+  =
∆0 ε
( p+ (1− p)k
d
)( dL− +
dL+√ n
√( 1 p − 1 )( d k − 1 )) .
Using Lemma 12 with a = dL−, b = dL±√ n , and ymin = 1/d, we get
NRandK(p, k) ≥ ∆0 2ε min
{ dL−, L− +
dL+√ n
} ≥ ∆0
2ε min
{ dL−,
dL+√ n
} ,
for all p ∈ (0, 1], k ∈ {1, . . . , d}. We can obtain the bound 38 if we take k ∈ {1, . . . , d/ √ n} and p = k/d:
NRandK(p, k) ≤ 2∆0 ε
( kL− + k ( d k − 1 ) L+√ n ) ≤ 2∆0
ε ( dL−√ n + dL+√ n ) ≤ 4∆0dL+ ε √ n .
The equality 39 is obtained by taking p = 1.
3. This part is easily proved, using L− ≤ L+ from Lemma 2, and directly minimizing (40).
In Table 4, we summarize bounds (36), (37), (38), (39), and (40).
L.1.2 CASE n ≥ d
Now, we analyze case, when n ≥ d. For simplicity, without losing the generality, we assume that d | n, n > 1, and d > 1. Then, PermK from Definition 3 satisfies the AB inequality with A = B = d−1 n−1 .
In each iteration of MARINA, on average, PermK sends
O (pd+ (1− p)) bits, thus the theoretical communication complexity is
NPermK(p) := ∆0 ε (pd+ (1− p))
( L− + √ 1− p p d− 1 n− 1 L± ) (41)
up to a constant factor. Lemma 14. For communication complexity NPermK(p) of MARINA with PermK, communication complexityNRandK(p, k) of MARINA with RandK and communication complexityNTopK(k) of EF21 with TopK defined in (41), (34) and (35) the following inequalities hold:
1. Lower bounds:
NPermK(p) ≥ ∆0 2ε min
{ dL−, L− +
dL±√ n
} , ∀p ∈ (0, 1].
Upper bounds:
NPermK
( 1
d
) ≤ 4∆0
ε
( L− +
dL±√ n
) , (42)
NPermK (1) = ∆0dL−
ε . (43)
2. Lower bounds:
NRandK(p, k) ≥ ∆0 2ε min
{ dL−, L− +
dL+√ n
} , ∀p ∈ (0, 1],∀k ∈ {1, . . . , d},
Upper bounds:
NRandK
( 1
d , 1
) ≤ 2∆0
ε
( L− +
dL+√ n
) , (44)
Moreover, for all k ∈ {1, . . . , d}, p = 1,
NRandK (1, k) = ∆0dL−
ε . (45)
3.
min k∈{1,...,d}
NTopK(k) = NTopK(d) = ∆0dL−
ε (46)
Proof.
1.
NPermK(p) = ∆0 ε (pd+ (1− p)) ( L− + √ 1−p p d−1 n−1L± ) ≥ ∆0ε ( p+ (1− p) 1d )( dL− + dL±√ n √( 1 p − 1 ) (d− 1)
) Using Lemma 12 with a = dL−, b = dL±√ n , and ymin = 1/d, we get
NPermK(p) ≥ ∆0 2ε min
{ dL−, L− +
dL±√ n
}
for all p ∈ (0, 1]. We can show the bound 42 if we take p = 1/d:
NPermK
( 1
d
) =
∆0 ε
( 1 + ( 1− 1
d
) 1 )( L− +
d− 1√ n− 1 L± ) ≤ 4∆0
ε
( L− +
dL±√ n ) The bound 43 is obtained by taking p = 1.
2. As in Lemma 13 we can get, that
NRandK(p, k) ≥ ∆0 2ε min
{ dL−, L− +
dL+√ n
} ,
for all p ∈ (0, 1], k ∈ {1, . . . , d}. Moreover, if we take p = 1/d and k = 1, we have
NRandK
( 1
d , 1
) ≤ 2∆0
ε
( L− +
dL+√ n
) .
The bound 45 is obtained by taking p = 1.
3. For TopK, the reasoning the same as in Lemma 13.
In Table 4, we summarize bounds (42), (43), (44), (45), and (46).
L.2 PŁ ASSUMPTION
L.2.1 CASE n ≤ d
Using the same reasoning as in Appendix L.1, Theorem 5 and Theorem 7, we can show that communication complexities predicted by theory are equal to
NPermK(p) := log ∆0 ε
( pd+ (1− p) d
n
) max {( L− µ + √ 2 (1− p) p L± µ ) , 1 p } , (47)
NRandK(p, k) := log ∆0 ε (pd+ (1− p)k) max  L− µ + √ 2 (1− p) p d k − 1 n L+ µ  , 1 p  , (48) NTopK(k) := log
∆0 ε kmax  ( L− µ + L+ µ d− k + √ d2 − dk k ) ,
1 1− √
1− kd  . (49) up to a constant factor. Lemma 15. For communication complexity NPermK(p) of MARINA with PermK, communication complexityNRandK(p, k) of MARINA with RandK and communication complexityNTopK(k) of EF21 with TopK defined in (47), (48) and (49) the following inequalities hold12:
1.
inf p∈(0,1] NPermK(p) = Θ
( max { 1
µ min
{ dL−, d
n L− + d√ n L±
} , d }) ,
2.
inf p∈(0,1],k∈{1,...,d} NRandK(p, k) = Θ
( max { 1
µ min
{ dL−,
d√ n L+
} , d }) ,
12In the lemma, we use “Big Theta” notation, which means, that if f(x) = Θ(g(x)), then f is bounded both above and below by g asymptotically up to a logarithmic factor.
3.
min k∈{1,...,d} NTopK(k) = Θ ( dL− µ ) .
Proof. Rearranging (47), (48) and (49), we get
NPermK(p) = log ∆0 ε max
{( pd+ (1− p) d
n )( L− µ + √ 2 (1− p) p L± µ ) , d+ (1− p)d pn } ,
NRandK(p, k) = log ∆0 ε max (pd+ (1− p)k) L− µ + √ 2 (1− p) p d k − 1 n L+ µ  , d+ (1− p)k p  , NTopK(k) = log
∆0 ε max k ( L− µ + L+ µ d− k + √ d2 − dk k ) ,
k 1− √
1− kd  . Note, that
k 1− √ 1− kd ≥ d, ∀k ∈ {1, . . . , d},
thus in all complexities, the second terms inside the max brackets are at least d.
Analysis of first terms inside the max brackets is the same as in Lemma 13.
In Table 5, we provide complexity bounds with optimal parameters of algorithms.
L.2.2 CASE n ≥ d
The only difference here is that the communication complexity of PermK predicted by our theory is the following:
NPermK(p) := log ∆0 ε (pd+ (1− p)) max {( L− µ + √ 2 (1− p) p d− 1 n− 1 L± µ ) , 1 p } . (50)
Lemma 16. For communication complexity NPermK(p) of MARINA with PermK, communication complexityNRandK(p, k) of MARINA with RandK and communication complexityNTopK(k) of EF21 with TopK defined in (50), (48) and (49) the following inequalities hold:
1.
inf p∈(0,1] NPermK(p) = Θ
( max { 1
µ min
{ dL−, L− +
d√ n L±
} , d }) ,
2.
inf p∈(0,1],k∈{1,...,d} NRandK(p, k) = Θ
( max { 1
µ min
{ dL−, L− +
d√ n L+
} , d }) ,
3.
min k∈{1,...,d} NTopK(k) = Θ ( dL− µ ) .
The proof of Lemma 16 is the same as in Lemma 15.
Using the same reasoning as before, we provide complexity bounds in Table 5.
M GROUP HESSIAN VARIANCE
We showed the communication complexity improvement of MARINA algorithm with PermK under the assumption that L± L−. In general, L± can be large; however, we can still use the notion of L± but in a different way, by splitting the functions into several groups where L± is small.
We split a set {1, · · · , n} into nonempty sets {Gk}gk=1, ⋃g k=1 Gk = {1, · · · , n}, Gi ⋂ Gj = ∅, for all i 6= j ∈ {1, · · · , g}, and |Gk| > 0, for all k ∈ {1, · · · , g}. Let us fix some set Gk and define functions
LGk− (x, y) := ∥∥∥∥∥∥ 1|Gk| ∑ i∈|Gk| (∇fi(x)−∇fi(y)) ∥∥∥∥∥∥ 2 ,
LGk+ (x, y) := 1 |Gk| ∑ i∈|Gk| ‖∇fi(x)−∇fi(y)‖2 ,
LGk± (x, y) := L Gk + (x, y)− L Gk − (x, y)
and the smallest constants LGk− , L Gk + , L Gk ± for functions L Gk − (x, y),L Gk + (x, y), and L Gk ± (x, y), such that
LGk− (x, y) ≤ ( LGk− )2 ‖x− y‖2 ,LGk+ (x, y) ≤ ( LGk+ )2 ‖x− y‖2 ,LGk± (x, y) ≤ ( LGk± )2 ‖x− y‖2 ,
for all k ∈ {1, · · · , g}, x, y ∈ Rd. In this section, we have the following assumption about groups.
Assumption 6. Compressors between groups are independent, i.e. Ci and Cj are independent, for all i ∈ Gk, j ∈ Gp, k 6= p. And Assumption 4 is satisfied with constants AGk and BGk inside each group Gk, for k ∈ {1, · · · , g}.
Now, we prove group AB inequality.
Lemma 17 (Group AB inequality). Let us assume that Assumptions 3 and 6 hold, then
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 
≤ g∑ k=1 AGk |Gk|2 n2 1 |Gk| ∑ i∈Gk ‖ai‖2 − g∑ k=1 BGk |Gk|2 n2 ∥∥∥∥∥ 1|Gk| ∑ i∈Gk ai ∥∥∥∥∥ 2 . (51)
Proof.
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 
= 1
n2 g∑ k=1 E ∥∥∥∥∥∑ i∈Gk Ci(ai)− ∑ i∈Gk ai ∥∥∥∥∥ 2 
+ 1
n2 ∑ k 6=p E 〈∑ i∈Gk Ci(ai)− ∑ i∈Gk ai, ∑ i∈Gp Ci(ai)− ∑ i∈Gp ai 〉 .
Due to independence and unbiasedness, the last term vanishes, and, using AB inequality, we get
E ∥∥∥∥∥ 1n n∑ i=1 Ci(ai)− 1 n n∑ i=1 ai ∥∥∥∥∥ 2 
= 1
n2 g∑ k=1 E ∥∥∥∥∥∑ i∈Gk Ci(ai)− ∑ i∈Gk ai ∥∥∥∥∥ 2 
= g∑ k=1 |Gk|2 n2 E ∥∥∥∥∥ 1|Gk| ∑ i∈Gk Ci(ai)− 1 |Gk| ∑ i∈Gk ai ∥∥∥∥∥ 2  ≤ g∑ k=1 |Gk|2 n2 AGk ( 1 |Gk| ∑ i∈Gk ‖ai‖2 ) −BGk ∥∥∥∥∥ 1|Gk| ∑ i∈Gk ai ∥∥∥∥∥ 2  .
From this we can get the result.
Next, we prove analogous lemma to Lemma 5.
Lemma 18. Let us consider gt+1 from Line 8 of Algorithm 2 and assume, that Assumptions 3 and 6 hold. Moreover, if Assumption 2 holds for every group Gk, for k ∈ {1, · · · , g}, then
E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1] ≤ (1− p)
( g∑ k=1 (AGk −BGk) |Gk|2 n2 ( LGk+ )2 + g∑ k=1 BGk |Gk|2 n2 ( LGk± )2)∥∥xt+1 − xt∥∥2 + (1− p) ∥∥gt −∇f(xt)∥∥2 . (52)
Proof. In the view of definition of gt+1, we get
E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1]
= (1− p)E ∥∥∥∥∥gt + 1n n∑ i=1 Ci ( ∇fi(xt+1)−∇fi(xt) ) −∇f(xt+1) ∥∥∥∥∥ 2 ∣∣∣∣∣∣xt+1  = (1− p)E
∥∥∥∥∥ 1n n∑ i=1 Ci ( ∇fi(xt+1)−∇fi(xt) ) −∇f(xt+1) +∇f(xt) ∥∥∥∥∥ 2 ∣∣∣∣∣∣xt+1  + (1− p) ∥∥gt −∇f(xt)∥∥2 .
In the last inequality we used unbiasedness of Ci. Using (51), we get E [∥∥gt+1 −∇f(xt+1)∥∥2∣∣∣xt+1] ≤ (1− p)E
∥∥∥∥∥ 1n n∑ i=1 Ci ( ∇fi(xt+1)−∇fi(xt) ) −∇f(xt+1) +∇f(xt) ∥∥∥∥∥ 2 ∣∣∣∣∣∣xt+1  + (1− p)
∥∥gt −∇f(xt)∥∥2 . ≤ (1− p)
( g∑ k=1 AGk |Gk|2 n2 1 |Gk| ∑ i∈Gk ∥∥∇fi(xt+1)−∇fi(xt)∥∥2 −
g∑ k=1 BGk |Gk|2 n2 ∥∥∥∥∥ 1|Gk| ∑ i∈Gk ∇fi(xt+1)−∇fi(xt) ∥∥∥∥∥ 2)
+ (1− p) ∥∥gt −∇f(xt)∥∥2
= (1− p) ( g∑ k=1 (AGk −BGk) |Gk|2 n2 LGk+ (xt+1, xt) + g∑ k=1 BGk |Gk|2 n2 LGk± (xt+1, xt) ) + (1− p)
∥∥gt −∇f(xt)∥∥2 ≤ (1− p)
( g∑ k=1 (AGk −BGk) |Gk|2 n2 ( LGk+ )2 + g∑ k=1 BGk |Gk|2 n2 ( LGk± )2)∥∥xt+1 − xt∥∥2 + (1− p) ∥∥gt −∇f(xt)∥∥2 .
Let us define
L̂2G := ( g∑ k=1 (AGk −BGk) |Gk|2 n2 ( LGk+ )2 + g∑ k=1 BGk |Gk|2 n2 ( LGk± )2) .
Theorem 10. Let Assumptions 1, 2, 3 and 6 be satisfied. Let the stepsize in MARINA be chosen as γ ≤ ( L− + √ 1− p p L̂2G )−1 ,
then after T iterations, MARINA finds point x̂T for which E [∥∥∇f(x̂T )∥∥2] ≤ 2∆0γT .
Theorem 11. Let Assumptions 1, 2, 3, 5 and 6 be satisfied and
γ ≤ min  ( L− + √ 2 (1− p) p L̂2G )−1 , p 2µ  , then for xT from MARINA algorithm the following inequality holds:
E [ f(xT )− f? ] ≤ (1− γµ)T ∆0.
We omit proofs of this theorems as they repeat proofs from Appendix C.6 and D.2; the only difference is that we have to take L̂2 = L̂2G .
Let us assume that n ≤ d, all groups have equal sizes |Gk| = G and constants LGk± = LG±, for all k ∈ {1, . . . , g}, and in each group we use PermK compressor from Definition 2, thus communication complexity predicted by our theory is the following:
NGPermK(p) := ∆0 ε
( pd+ (1− p) d
G
)( L− + √ (1− p)G
pn LG±
) .
Using the same reasoning as in Lemma 13, we can take p = 1 or p = 1/G to get that
inf p∈(0,1]
NGPermK(p) = O (
2∆0 ε min
{ dL−, d
G L− + d√ n LG±
}) . (53)
For the case when we have one group, we restore the communication complexity from Lemma 13.
Comparing (36) with (53), we see that dL−/n from (36) is always better than dL−/G from (53); however; if dL±/ √ n is a bottleneck and LG± is small, then communication complexity (53) can be better.
Let us consider an example of a 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 6= B, A = A> < 0 and B = B> < 0, then G = n/2, LG± = 0, and L± > 0 (see Example 3). Hence, we get that
inf p∈(0,1]
NGPermK(p) = O ( ∆0d
εn L−
) .
This bound is better than (36) by at least the factor 1 + √ nL±/L−.

Review summaries:
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.