DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization

We develop and analyze DASHA: a new family of methods for nonconvex distributed optimization problems. When the local functions at the nodes have a finite-sum or an expectation form, our new methods, DASHA-PAGE and DASHA-SYNC-MVR, improve the theoretical oracle and communication complexity of the previous state-of-the-art method MARINA by Gorbunov et al. (2020). In particular, to achieve an epsilon-stationary point, and considering the random sparsifier RandK as an example, our methods compute the optimal number of gradients $\mathcal{O}\left(\frac{\sqrt{m}}{\varepsilon\sqrt{n}}\right)$ and $\mathcal{O}\left(\frac{\sigma}{\varepsilon^{3/2}n}\right)$ in finite-sum and expectation form cases, respectively, while maintaining the SOTA communication complexity $\mathcal{O}\left(\frac{d}{\varepsilon \sqrt{n}}\right)$. Furthermore, unlike MARINA, the new methods DASHA, DASHA-PAGE and DASHA-MVR send compressed vectors only and never synchronize the nodes, which makes them more practical for federated learning. We extend our results to the case when the functions satisfy the Polyak-Lojasiewicz condition. Finally, our theory is corroborated in practice: we see a significant improvement in experiments with nonconvex classification and training of deep learning models.

Introduction
Nonconvex optimization problems are widespread in modern machine learning tasks, especially with the rise of the popularity of deep neural networks (Goodfellow et al., 2016). In the past years, the dimensionality of such problems has increased because this leads to better quality (Brown et al., 2020) and robustness (Bubeck and Sellke, 2021) of the deep neural networks trained this way. Such huge-dimensional nonconvex problems need special treatment and efficient optimization methods (Danilova et al., 2020).
Because of their high dimensionality, training such models is a computationally intensive undertaking that requires massive training datasets (Hestness et al., 2017), and parallelization among several compute nodes 1 (Ramesh et al., 2021). Also, the distributed learning paradigm is a necessity in federated learning (Konečný et al., 2016), where, among other things, there is an explicit desire to secure the private data of each client.
Unlike in the case of classical optimization problems, where the performance of algorithms is defined by their computational complexity (Nesterov, 2018), distributed optimization algorithms are typically measured in terms of the communication overhead between the nodes since such communication is often the bottleneck in practice (Konečný et al., 2016;Wang et al., 2021). Many approaches tackle the problem, including managing communication delays (Vogels et al., 2021), fighting with stragglers Preprint. Under review. (Li et al., 2020a), and optimization over time-varying directed graphs (Nedić and Olshevsky, 2014). Another popular way to alleviate the communication bottleneck is to use lossy compression of communicated messages (Alistarh et al., 2017;Mishchenko et al., 2019;Gorbunov et al., 2021;Szlendak et al., 2021). In this paper, we focus on this last approach.

Problem formulation
In this work, we consider the optimization problem where f i : R d → R is a smooth nonconvex function for all i ∈ [n] := {1, . . . , n}. Moreover, we assume that the problem is solved by n compute nodes, with the i th node having access to function f i only, via an oracle. Communication is facilitated by an orchestrating server able to communicate with all nodes. Our goal is to find an ε-solution (ε-stationary point) of (1): a (possibly random) point x ∈ R d , such that E ∇f ( x) 2 ≤ ε.

Gradient oracles
We consider all of the following structural assumptions about the functions {f i } n i=1 , each with its own natural gradient oracle: 1. Gradient Setting. The i th node has access to the gradient ∇f i : where f ij : R d → R is a smooth nonconvex function for all j ∈ [m]. For all i ∈ [n], the i th node has access to a mini-batch of B gradients, 1 B j∈Ii ∇f ij (·), where I i is a multi-set of i.i.d. samples of the set [m], and |I i | = B.
3. Stochastic Setting. The function f i is an expectation of a stochastic function, where f i : R d × Ω ξ → R. For a fixed x ∈ R, f i (x; ξ) is a random variable over some distribution D i , and, for a fixed ξ ∈ Ω ξ , f i (x; ξ) is a smooth nonconvex function. The i th node has access to a mini-batch of B stochastic gradients 1 B B j=1 ∇f i (·; ξ ij ) of the function f i through the distribution D i , where {ξ ij } B j=1 is a collection of i.i.d. samples from D i .

Oracle complexity
In this paper, the oracle complexity of a method is the number of (stochastic) gradient calculations per node to achieve an ε-solution. Every considered method performs some number T of communications rounds to get an ε-solution; thus, if every node (on average) calculates B gradients in each communication round, then the oracle complexity equals O (B init + BT ) , where B init is the number of gradient calculations in the initialization phase of a method.

Unbiased compressors
The method proposed in this paper is based on unbiased compressors -a family of stochastic mappings with special properties that we define now. Definition 1.1. A stochastic mapping C : R d → R d is an unbiased compressor if there exists ω ∈ R such that We denote this class of unbiased compressors as U(ω).   (2)), σ 2 = variance of stochastic gradients (only in stochastic case (3)), B = batch size (only in finite-sum and stochastic case). To simplify bounds, we assume that ω + 1 = Θ ( d /ζ C ) , where d is dimension of x in (1) and ζC is the expected number of nonzero coordinates that each compressor Ci returns (see Definition 1.3). (b) Does the algorithm require periodic synchronization between nodes? (see Section 3) (c) One can always choose the parameter of RandK such that this term does not dominate (see Section 6.5).
One can find more information about unbiased compressors in (Beznosikov et al., 2020;Horváth et al., 2019). The purpose of such compressors is to quantize or sparsify the communicated vectors in order to increase the communication speed between the nodes and the server. Our methods will work collection of stochastic mappings {C i } n i=1 satisfying the following assumption. Assumption 1.2. C i ∈ U(ω) for all i ∈ [n], and the compressors are independent.

Communication complexity
The quantity below characterizes the number of nonzero coordinates that a compressor C returns. This notion is useful in case of sparsification compressors. Definition 1.3. The expected density of the compressor C i is ζ Ci := sup x∈R d E [ C i (x) 0 ], where x 0 is the number of nonzero components of x ∈ R d . Let ζ C = max i∈ [n] ζ Ci .
In this paper, the communication complexity of a method is the number of coordinates sent to the server per node to achieve an ε-solution. If every node (on average) sends ζ coordinates in each communication round, then the communication complexity equals O (ζ init + ζT ) , where T is the number of communication rounds, and ζ init is the number of coordinates sent in the initialization phase.

Related Work
• Uncompressed communication. This line of work is characterized by methods in which the nodes send messages (vectors) to the server without any compression. In the finite-sum setting, the current state-of-the-art methods were proposed by Sharma et al. (2019); Li et al. (2021b), showing that after O ( 1 /ε) communication rounds and calculations of ∇f ij per node, these methods can return an ε-solution. Moreover, Sharma et al. (2019) show that the same can be done in the stochastic setting after O σ 2 εn + σ ε 3 /2 n   (2)), σ 2 = variance of stochastic gradients (only in stochastic case (3)), B = batch size (only in finite-sum and stochastic case). To simplify bounds, we assume that ω (1) and ζC is the expected number of nonzero coordinates that each compressor Ci returns (see Definition 1.3). (b) Does the algorithm require periodic synchronization between nodes? (see Section 3) (c) One can always choose the parameter of RandK such that this term does not dominate (see Section 6.5).
• Compressed communication. In practice, it is rarely affordable to send uncompressed messages (vectors) from the nodes to the server due to limited communication bandwidth. Because of this, researchers started to develop methods keeping in mind the communication complexity: the total number of coordinates/floats/bits that the nodes send to the server to find an ε-solution. Two important families of compressors are investigated in the literature to reduce communication bottleneck: biased and unbiased compressors. While unbiased compressors are superior in theory (Mishchenko et al., 2019;Li et al., 2020b;Gorbunov et al., 2021), biased compressors often enjoy better performance in practice (Beznosikov et al., 2020;Xu et al., 2020). Recently, Richtárik et al. (2021) developed EF21, which is the first method capable of working with biased compressors an having the theoretical iteration complexity of gradient descent (GD), up to constant factors.
• Unbiased compressors. The theory around unbiased compressors is much more optimistic. Alistarh et al. (2017)

Contributions
We develop a new family of distributed optimization methods DASHA for nonconvex optimization problems with unbiased compressors. Compared to MARINA, our methods make more practical and simpler optimization steps. In particular, in MARINA, all nodes simultaneously send either compressed vectors, with some probability p, or the gradients of functions {f i } n i=1 (uncompressed vectors), with probability 1 − p. In other words, the server periodically synchronizes all nodes. In federated learning, where some nodes can be inaccessible for a long time, such periodic synchronization is intractable.
Our method DASHA solves both problems: i) the server never synchronizes all nodes, and ii) the nodes always send compressed vectors.
Further, a simple tweak in the compressors (see Appendix D) results in support for partial participation, which makes DASHA more practical for federated learning tasks. Let us summarize our most important theoretical and practical contributions: • New theoretical SOTA complexity in the finite-sum setting. Using our novel approach to compress gradients, we improve the theoretical complexities of VR-MARINA (see Tables 1 and 2) in the finite-sum setting. Indeed, if the number of functions m is large, our algorithm DASHA-PAGE needs √ ω + 1 times fewer communications rounds, while communicating compressed vectors only.
• New theoretical SOTA complexity in the stochastic setting. We develop a new method, DASHA-SYNC-MVR, improving upon the previous state of the art (see Table 1). When ε is small, the number of communication rounds is reduced by a factor of √ ω + 1. Indeed, we improve the dominant term which depends on ε 3 /2 (the other terms depend on ε only). However, DASHA-SYNC-MVR needs to periodically send uncompressed vectors with the same rate as VR-MARINA (online). Nevertheless, we show that DASHA-MVR also improves the dominant term when ε is small, and this method sends compressed vectors only.
• Closing the gap between uncompressed and compressed methods. In Section 2, we mentioned that the optimal oracle complexities of methods without compression in the finite-sum and stochastic settings are (5) and (6), respectively. Considering the RandK compressor (see Definition F.1), we show that DASHA-PAGE, DASHA-MVR and DASHA-SYNC-MVR attain these optimal oracle complexities while attainting the state-of-the-art communication complexity as MARINA, which needs to use the stronger gradient oracle! Therefore, our new methods close the gap between results from (Gorbunov et al., 2021) and(Sharma et al., 2019;Li et al., 2021b).
• Experiments. We provide detailed experiments on practical machine learning tasks: training nonconvex generalized linear models and deep neural networks, showing improvements predicted by our theory. See Appendix A.

Algorithm Description
We now describe our proposed family of optimization methods, DASHA (see Algorithm 1). DASHA is inspired by MARINA and momentum variance reduction methods (MVR) (Cutkosky and Orabona, 2019;Tran-Dinh et al., 2021;Liu et al., 2020): the general structure repeats MARINA except for the variance reduction strategy, which we borrow from MVR. Unlike MARINA, our algorithm never sends uncompressed vectors, and the number of bits that every node sends is always the same. Moreover, we reduce the variance from the oracle and the compressor separately, which helps us to improve the theoretical convergence rates in the stochastic and finite-sum cases.
First, using the gradient estimator g t , the server in each communication round calculates the next point x t+1 and broadcasts it to the nodes. Subsequently, all nodes in parallel calculate vectors h t+1 i in one of three ways, depending on the available oracle. For the the gradient, finite-sum, and the stochastic settings, we use GD-like, PAGE-like, and MVR-like strategies, respectively. Next, each node compresses their message and uploads it to the server. Finally, the server aggregates all received messages and calculates the next vector g t+1 .
We note that in the stochastic setting, our analysis of DASHA-MVR (Algorithm 1) provides a suboptimal oracle complexity w.r.t. ω (see Tables 1 and 2). In Appendix I we provide experimental evidence that our analysis is tight. For this reason, we developed DASHA-SYNC-MVR (see Algorithm 2 in Appendix C) that improves the previous state-of-the-art results and does synchronizations among the nodes with the same rate as VR-MARINA (online). Note that DASHA-MVR still enjoys the optimal oracle and SOTA communication complexity (see Section 6.5); and this can be seen it in experiments.

Assumptions
We now provide the assumptions used throughout our paper. Assumption 5.1. There exists f * ∈ R such that f (x) ≥ f * for all x ∈ R. Assumption 5.2. The function f is L-smooth, i.e., ∇f (x) − ∇f (y) ≤ L x − y for all x, y ∈ R d .

6:
Broadcast x t+1 to all nodes 7: for i = 1, . . . , n in parallel do 8: Send m t+1 i to the server 12: end for 13: The next assumption is used in the finite-sum setting (2).
The two assumptions below are provided for the stochastic setting (3). Assumption 5.5. For all i ∈ [n] and for all x ∈ R d , the stochastic gradient ∇f i (x; ξ) is unbiased and has bounded variance, i.e., where σ 2 ≥ 0. Assumption 5.6. For all i ∈ [n] and for all x, y ∈ R, the stochastic gradient ∇f i (x; ξ) satisfies the mean-squared smoothness property, i.e.,

Theoretical Convergence Rates
Now, we provide convergence rate theorems for DASHA, DASHA-PAGE and DASHA-MVR. All three methods are listed in Algorithm 1 and differ in Line 8 only. At the end of the section, we provide a theorem for DASHA-SYNC-MVR.
2 Note that one can always take L 2 = L 2 := 1 n n i=1 L 2 i . However, the optimal constant L can be much better because L 2 ≤ 1 n n i=1 Li 2 ≤ 1 n n i=1 L 2 i .
Corollary 6.2. Suppose that assumptions from Theorem 6.1 hold, and g 0 to get an ε-solution and the communication complexity is equal to O (d + ζ C T ) , where ζ C is the expected density from Definition 1.3.
In the previous corollary, we have free parameters ω and ζ C . Now, we consider the RandK compressor (see Definition F.1) and choose its parameters to get the communication complexity w.r.t. only d and n. Corollary 6.3. Suppose that assumptions of Corollary 6.2 hold. We take the unbiased compressor

Finite-Sum Setting (DASHA-PAGE)
Next, we provide the complexity bounds for DASHA-PAGE. Theorem 6.4. Suppose that Assumptions 5.1, 5.2, 5.3, 5.4, and 1.2 hold. Let us take a = 1/ (2ω + 1), probability p ∈ (0, 1], Let us simplify the statement of Theorem 6.4 by choosing particular parameters. Corollary 6.5. Let the assumptions from Theorem 6.4 hold, p = B /(m+B), and g 0 communication rounds to get an ε-solution, the communication complexity is equal to O (d + ζ C T ) , and the expected # of gradient calculations per node equals O (m + BT ) , where ζ C is the expected density from Definition 1.3.
The corollary below reveals the communication and oracle complexities of Algorithm 1 (DASHA-PAGE) with RandK.
Corollary 6.6. Suppose that assumptions of Corollary 6.5 hold, B ≤ m /n, and we use the unbiased compressor RandK with K = ζ C = Θ ( Bd / √ m) . Then the communication complexity of Algorithm 1 is and the expected # of gradient calculations per node equals Up to Lipschitz constants factors, bound (8) is optimal (Fang et al., 2018;Li et al., 2021a), and unlike VR-MARINA, we recover the optimal bound with compression! At the same time, the communication complexity (7) is the same as in DASHA (see Corollary 6.3) or MARINA.

Stochastic Setting (DASHA-MVR)
This vector is not used in Algorithm 1, but appears in the theoretical results. Theorem 6.7. Suppose that Assumptions 5.1, 5.2, 5.3, 5.5, 5.6 and 1.2 hold. Let us take a = 1 2ω+1 , communication rounds to get an ε-solution, the communication complexity is equal to O (d + ζ C T ) , and the number of stochastic gradient calculations per node equals O(B init + BT ), where ζ C is the expected density from Definition 1.3.
The following corollary reveals the communication and oracle complexity of DASHA-MVR. Corollary 6.9. Suppose that assumptions of Corollary 6.8 hold, batch size B ≤ σ √ εn , we take RandK with K = ζ C = Θ Bd and the expected # of stochastic gradient calculations per node equals Up to Lipschitz constant factors, the bound (10) is optimal (Arjevani et al., 2019;Sharma et al., 2019), and unlike VR-MARINA (online), we recover the optimal bound with compression! At the same time, the communication complexity (9) is the same as in DASHA (see Corollary 6.3) or MARINA for small enough ε.

Stochastic Setting (DASHA-SYNC-MVR)
We now provide the complexities of Algorithm 2 (DASHA-SYNC-MVR) presented in Appendix C.
The main convergence rate Theorem H.19 is in the appendix. Corollary 6.10. Suppose that assumptions from Theorem H.19 hold, probability p = min ζ C d , nεB communication rounds to get an ε-solution, the communication complexity is equal to O (d + ζ C T ) , and the number of stochastic gradient calculations per node equals O(B init + BT ), where ζ C is the expected density from Definition 1.3.
Corollary 6.11. Suppose that assumptions of Corollary 6.10 hold, batch size B ≤ σ √ εn , we take RandK with K = ζ C = Θ Bd and the expected # of stochastic gradient calculations per node equals Up to Lipschitz constant factors, the bound (12) is optimal (Arjevani et al., 2019;Sharma et al., 2019), and unlike VR-MARINA (online), we recover the optimal bound with compression! At the same time, the communication complexity (11) is the same as in DASHA (see Corollary 6.3) or MARINA for small enough ε.

A Experiments
We have tested all developed algorithms on practical machine learnings problems 3 . Note that the goal of our experiments is to justify the theoretical convergence rates from our paper. We compare the new methods with MARINA on LIBSVM datasets (Chang and Lin, 2011) (under the 3-clause BSD license) because MARINA is the only previous state-of-the-art method for the problem (1). Moreover, we show the advantage of our method on an image recognition task with CIFAR10 (Krizhevsky et al., 2009) and a deep neural network. In all experiments, we take parameters of algorithms predicted by the theory (stated in the convergence rate theorems our paper and in (Gorbunov et al., 2021)), except for the step sizes -we fine-tune them using a set of powers of two {2 i | i ∈ [−10, 10]} -and use the RandK compressor. We evaluate communication complexity; thus, each plot represents the relation between the norm of a gradient or function value (vertical axis), and the total number of transmitted bits per node (horizontal axis).

A.1 Gradient setting
We consider nonconvex functions to solve a classification problem. Here, a ij ∈ R d is the feature vector of a sample on the i th node, y ij ∈ {−1, 1} is the corresponding label, and m is the number of samples on the i th node. All nodes calculate full gradients. We take the mushrooms dataset (dimension d = 112, number of samples equals 8124) from LIBSVM, randomly split the dataset between 5 nodes and take K = 10 in RandK. One can see in Figure  Step size: 0.25 MARINA: Step size: 0.5 MARINA: Step size: 1.0 DASHA: Step size: 0.25 DASHA: Step size: 0.5 DASHA: Step size: 1.0 Figure 1: Classification task with the mushrooms dataset and gradient oracle.

A.2 Finite-sum setting
Now, we conduct the same experiments as in Section A.1 with real-sim dataset (dimension d = 20,958, number of samples equals 72,309) from LIBSVM in the finite-sum setting; moreover, we compare VR-MARINA versus DASHA-PAGE with batch size B = 1 in both algorithms. Results in Figure 2 coincide with Table 1 -our new method DASHA-PAGE converges faster than MARINA. When K = 100, the improvement is not significant because Table 1), and both algorithms get the same theoretical convergence complexity.

A.3 Stochastic setting
In this experiment, we consider the following logistic regression functions with nonconvex regularizer {f i } n i=1 to solve a classification problem: is a corresponding label, m is the number of samples located on the i th node, constant λ = 0.001. We take batch size B = 1 and compare VR-MARINA (online), DASHA-MVR, and DASHA-SYNC-MVR that depend on a common ratio σ 2 /nεB 4 . We fix σ 2 /nεB ∈ {10 4 , 10 5 } and K ∈ {200, 2000} in RandK compressors. We consider real-sim dataset from LIBSVM splitted between 5 nodes. When we increase σ 2 /nεB from 10 4 to 10 5 , we implicitly decrease ε because other parameters are fixed. In Figure 3, when ε is small, DASHA-MVR and DASHA-SYNC-MVR converge faster than VR-MARINA (online).
Results are provided in Figure 4. We see that DASHA-MVR converges significantly faster than other algorithms in the terms of communication complexity. Moreover, DASHA-SYNC-MVR works better than VR-MARINA (online) and SGD.

B Experiments Details
The code was written in Python 3.6.8 using PyTorch 1.9 (Paszke et al., 2019). A distributed environment was emulated on a machine with Intel(R) Xeon(R) Gold 6226R CPU @ 2.90GHz and 64 cores. Deep learning experiments were conducted with NVIDIA A100 GPU with 40GB memory (each deep learning experiment uses at most 5GB of this memory).
When the number of nodes n does not divide the number of samples N in a dataset, we randomly ignore N mod n samples from a dataset (up to 4 when n = 5).

C Description of DASHA-SYNC-MVR
In this section, we provide a description of DASHA-SYNC-MVR (see Algorithm 2). This algorithm is closely related to DASHA-MVR (Algorithm 1), but DASHA-SYNC-MVR synchronizes all nodes with some probability p. This synchronization procedure enabled us to fix the convergence rate suboptimality of DASHA-MVR w.r.t. ω.
Broadcast x t+1 to all nodes 7:

D Partial Participation
A partial participation mechanism, important for federated learning applications, can be easily implemented in DASHA. Let us assume that the i th node either participates in a communication round with probability p , or sends nothing. From the view of unbiased compressors, it can mean that instead of using a compressor C, we have use the following new stochastic mapping C p : The following simple result states that the new mapping C p is also an unbiased compressor, which means that our theory applies to this choice as well.
In the case of partial participation, all theorems from Section 6 will hold with ω replaced by (ω+1) /p − 1.

E Auxiliary Facts
In this section, we recall well-known auxiliary facts that we use in the proofs.
1. For all x, y ∈ R d , we have 2. Let us take a random vector ξ ∈ R d , then We say that a stochastic mapping C : is the standard unit basis. Informally, RandK randomly keeps K coordinates and zeroes out the other. (Beznosikov et al., 2020).
In the next theorem, we show that C p (x) from (13) is an unbiased compressor.
Proof. First, we proof the unbiasedness: Next, we get a bound for the variance:

G Polyak-Łojasiewicz Condition
In this section, we discuss our convergence rates under the (Polyak-Łojasiewicz) PŁ-condition: Here we use a different notion of an ε-solution: it is a (random) point Under this assumption, Algorithm 1 achieves a linear convergence rate O (ln ( 1 /ε)) instead of a sublinear convergence rate O ( 1 /ε) in the gradient and finite-sum settings. Moreover, in the stochastic setting, Algorithms 1 and 2 also improve dependence on ε. Related Theorems H.9, H.12, H.15 and H.20 are stated in Appendix H. Note that in the finite-sum and stochastic settings, Theorems H.12 and H.20 provide new SOTA theoretical convergence rates (see Table 2).

H Theorems with Proofs
Lemma H.1. Suppose that Assumption 5.2 holds and let x t+1 = x t − γg t . Then for any g t ∈ R d and γ > 0, we have and Proof. First, we estimate E C g t+1 − h t+1 2 : Using the independence of compressors and (4), we get Analogously, we can get the bound for E C g t+1 i − h t+1 i 2 : Lemma H.3. Suppose that Assumptions 5.2 and 1.2 hold and let us take a = 1/ (2ω + 1) , then Proof. Due to Lemma H.1 and the update step from Line 4 in Algorithm 1, we have In the last inequality we use Jensen's inequality (14). Let us fix some constants κ, η ∈ [0, ∞) that we will define later. Combining bounds (20), (18), (19) and using the law of total expectation, we get Now, by taking κ = γ a , we can see that γ + κ (1 − a) 2 ≤ κ, and thus Next, by taking η = 2γω n and considering the choice of a, one can show that The following lemma almost repeats the previous one. We will use it in the theorems with Assumption G.1. Lemma H.4. Suppose that Assumptions 5.2, 1.2 and G.1 hold and let us take a = 1/ (2ω + 1) and γ ≤ a 2µ , then Proof. Up to (21) we can follow the proof of Lemma H.3 to get Next, by taking η = 8γω n and considering the choice of a, one can show that Finally, the assumption γ ≤ a 2µ implies an inequality 1 − a 2 ≤ 1 − γµ. Lemma H.5. Suppose that Assumption 5.1 holds and where Ψ t is a sequence of numbers, Ψ t ≥ 0 for all t ∈ [T ], constant C ≥ 0, and constant γ > 0. Then where a point x T is chosen uniformly from a set of points {x t } T −1 t=0 .
Proof. By unrolling (22) for t from 0 to T − 1, we obtain We subtract f * , divide inequality by γT 2 , and take into account that f (x) ≥ f * for all x ∈ R, and Ψ t ≥ 0 for all t ∈ [T ], to get the following inequality: It is left to consider the choice of a point x T to complete the proof of the lemma.
Lemma H.6. Suppose that Assumptions 5.1 and G.1 hold and where Ψ t is a sequence of numbers, Ψ t ≥ 0 for all t ∈ [T ], constant C ≥ 0, constant µ > 0, and constant γ ∈ (0, 1/µ). Then Proof. We subtract f * and use PŁ-condition (16) to get It is left to note that Ψ t ≥ 0 for all t ∈ [T ].

H.1 Case of DASHA
Despite the triviality of the following lemma, we provide it for consistency with Lemma H.14 and Lemma H.11. Lemma H.8. Suppose that Assumption 5.3 holds. Assuming that h 0 3.
Theorem 6.1. Suppose that Assumptions 5.1, 5.2, 5.3 and 1.2 hold. Let us take a = 1/ (2ω + 1) and Proof. Considering Lemma H.3, Lemma H.8, and the law of total expectation, we obtain Using assumption about γ, we can show that 1 In the view of Lemma H.5 with Ψ t = (2ω can conclude the proof.
Corollary 6.2. Suppose that assumptions from Theorem 6.1 hold, and g 0 to get an ε-solution and the communication complexity is equal to O (d + ζ C T ) , where ζ C is the expected density from Definition 1.3.
Proof. The communication complexities can be easily derived using Theorem 6.1. At each communication round of Algorithm 1, each node sends ζ C coordinates. In the view of g 0 i = ∇f i (x 0 ) for all i ∈ [n], we additionally have to send d coordinates from the nodes to the server, thus the total communication complexity would be O (d + ζ C T ) . Corollary 6.3. Suppose that assumptions of Corollary 6.2 hold. We take the unbiased compressor Proof. In the view of Theorem F.2, we have ω + 1 = d/K. Combining this and an inequality L ≤ L, the communication complexity equals H.2 Case of DASHA under PŁ-condition Theorem H.9. Suppose that Assumption 5.1, 5.2, 5.3, 1.2 and G.1 hold. Let us take a = 1/ (2ω + 1) , Proof. Considering Lemma H.4, Lemma H.8, and the law of total expectation, we obtain Using the assumption about γ, we can show that 1 2γ − L 2 − 20γω(2ω+1) n L 2 ≥ 0 (see Lemma H.7), thus In the view of Lemma H.6 with Ψ t = 2(2ω can conclude the proof. We use O (·), when we provide a bound up to logarithmic factors. Corollary H.10. Suppose that assumptions from Theorem H.9 hold, and g 0 i = 0 for all i ∈ [n], then DASHA needs communication rounds to get an ε-solution and the communication complexity is equal to O (ζ C T ) , where ζ C is the expected density from Definition 1.3.
Proof. Clearly, using Theorem H.9, one can show that Algorithm 1 returns an ε-solution after (25) communication rounds. At each communication round of Algorithm 1, each node sends ζ C coordinates, thus the total communication complexity would be O (ζ C T ) per node. Unlike Corollary 6.2, in this corollary, we can initialize g 0 i , for instance, with zeros because the corresponding initialization error Ψ 0 from the proof of Theorem H.9 would be under the logarithm. 2. 3.
Proof. Using the definition of h t+1 , we obtain From the unbiasedness and independence of mini-batch samples, we get In the last inequality, we use Assumption 5.4. Using the same reasoning, we have Finally, we consider the last ineqaulity of the lemma: Using the unbiasedness and independence of the gradients, we obtain

From Assumptions 5.3 and 5.4, we can conclude that
Theorem 6.4. Suppose that Assumptions 5.1, 5.2, 5.3, 5.4, and 1.2 hold. Let us take a = 1/ (2ω + 1), probability p ∈ (0, 1], and Proof. Let us fix constants ν, ρ ∈ [0, ∞) that we will define later. Considering Lemma H.3, Lemma H.11, and the law of total expectation, we obtain After rearranging the terms, we get Next, let us fix ν = γ p , to get Next, considering the choice of γ and Lemma H.7, we get Finally, in the view of Lemma H.5 with we can conclude the proof.
Corollary 6.5. Let the assumptions from Theorem 6.4 hold, p = B /(m+B), and g 0 communication rounds to get an ε-solution, the communication complexity is equal to O (d + ζ C T ) , and the expected # of gradient calculations per node equals O (m + BT ) , where ζ C is the expected density from Definition 1.3.
Proof. Corollary 6.5 can be proved in the same way as Corollary 6.2. One only should note that the expected number of gradients calculations at each communication round equals pm + (1 − p)B = 2mB m+B ≤ 2B.
Corollary 6.6. Suppose that assumptions of Corollary 6.5 hold, B ≤ m /n, and we use the unbiased compressor RandK with K = ζ C = Θ ( Bd / √ m) . Then the communication complexity of Algorithm 1 is and the expected # of gradient calculations per node equals Proof. In the view of Theorem F.2, we have ω + 1 = d/K. Combining this, inequalities L ≤ L ≤ L max , and K = Θ Bd And the expected number of gradient calculations per node equals
Corollary H.13. Suppose that assumptions from Theorem H.12 hold, probability p = B/(m + B), and h 0 i = g 0 i = 0 for all i ∈ [n], then DASHA-PAGE needs communication rounds to get an ε-solution, the communication complexity is equal to O (ζ C T ) , and the expected number of gradient calculations per node equals O (BT ) , where ζ C is the expected density from Definition 1.3.
Proof. Clearly, using Theorem H.12, one can show that Algorithm 1 returns an ε-solution after (26) communication rounds. At each communication round of Algorithm 1, each node sends ζ C coordinates, thus the total communication complexity would be O (ζ C T ) . Moreover, the expected number of gradients calculations at each communication round equals pm+(1−p)B = 2mB m+B ≤ 2B, thus the total expected number of gradients that each node calculates is O (BT ) . Unlike Corollary 6.5, in this corollary, we can initialize h 0 i and g 0 i , for instance, with zeros because the corresponding initialization error Ψ 0 from the proof of Theorem H.12 would be under the logarithm.
Proof. First, let us proof the bound for E h h t+1 − ∇f (x t+1 ) 2 : Using Assumptions 5.5 and 5.6, we obtain Similarly, we can get the bound for Now, we proof the last inequality of the lemma: In the view of Assumptions 5.3, 5.5 and 5.6, we obtain Theorem 6.7. Suppose that Assumptions 5.1, 5.2, 5.3, 5.5, 5.6 and 1.2 hold. Let us take a = 1 2ω+1 , b ∈ (0, 1], and γ ≤ L + 96ω(2ω+1) Proof. Let us fix constants ν, ρ ∈ [0, ∞) that we will define later. Considering Lemma H.3, Lemma H.14, and the law of total expectation, we obtain After rearranging the terms, we get By taking ν = γ b , one can see that γ + ν(1 − b) 2 ≤ ν, and Next, we fix ρ = 16bγω(2ω+1) n . With this choice of ρ and for all b ∈ [0, 1], we can show that In the last inequality we use b ∈ (0, 1]. Next, considering the choice of γ and Lemma H.7, we get In the view of Lemma H.5 with and C = 48ω(2ω+1) nB + 2 bnB b 2 σ 2 , we can conclude the proof.
Corollary 6.8. Suppose that assumptions from Theorem 6.7 hold, momentum b = Θ min 1 ω nεB σ 2 , nεB σ 2 , and g 0 , and batch size B init = Θ ( B /b) , then Algorithm 1 (DASHA-MVR) needs communication rounds to get an ε-solution, the communication complexity is equal to O (d + ζ C T ) , and the number of stochastic gradient calculations per node equals O(B init + BT ), where ζ C is the expected density from Definition 1.3.
Proof. In the view of Theorem 6.7, we have Thus we can take In the view of Algorithm 1 and the fact that we use a mini-batch of stochastic gradients, the number of stochastic gradients that each node calculates equals B init + 2BT = O(B init + BT ).
Corollary 6.9. Suppose that assumptions of Corollary 6.8 hold, batch size B ≤ σ √ εn , we take RandK with K = ζ C = Θ Bd √ εn σ , and L := max{L, L σ , L}. Then the communication complexity equals and the expected # of stochastic gradient calculations per node equals Proof. In the view of Theorem F.2, we have ω+1 = d/K. Moreover, K = Θ Bd And the expected number of stochastic gradient calculations per node equals H.
Proof. Let us fix constants ν, ρ ∈ [0, ∞) that we will define later. Considering Lemma H.4, Lemma H.14, and the law of total expectation, we obtain After rearranging the terms, we get Next, we fix ρ = 80bγω (2ω+1) n . With this choice of ρ and for all b ∈ (0, 1], we can show that In the last inequality we use b ∈ (0, 1]. Next, considering the choice of γ and Lemma H.7, we get In the view of Lemma H.6 with , and h 0 i = g 0 i = 0 for all i ∈ [n], then Algorithm 1 needs . Therefore, is it enough to take the number of communication rounds equals (27) to get an ε-solution. In the view of Algorithm 1 and the fact that we use a mini-batch of stochastic gradients, the communication complexity is equal to O (ζ C T ) and the number of stochastic gradients that each node calculates equals O(BT ). Unlike Corollary 6.8, in this corollary, we can initialize h 0 i and g 0 i , for instance, with zeros because the corresponding initialization error Ψ 0 from the proof of Theorem H.15 would be under the logarithm.

H.7 Case of DASHA-SYNC-MVR
Comparing Algorithm 1 and Algorithm 2, one can see that Algorithm 2 has the third source of randomness from c t+1 . In this section, we define E p [·] to be a conditional expectation w.r.t. c t+1 conditioned on all previous randomness. And we define E t+1 [·] to be a conditional expectation w.r.t. c t+1 , Proof. First, we estimate E t+1 g t+1 − h t+1 2 . Let us denote h t+1 Using the independence of compressors and (4), we get where in the inequalities we use Assumptions 1.2, 5.5 and 5.3, and (14). Analogously, we can get the bound for E t+1 g t+1 We introduce new notations: Lemma H.18. Suppose that Assumptions 5.5 and 5.6 hold and let us consider sequence {h t+1 from Algorithm 2, then Proof.
Proof. Considering Theorem H.19 and the choice of B , we have Due to p = min ζ C d , nεB Therefore, we can take Note, that Next, by taking B init = max σ 2 nε , B d ζ C and using the last ineqaulity, we have Finally, it is left to estimate the communication and oracle complexity. On average, the number of coordinates that each node in Algorithm 2 sends at each communication round equals pd + (1 − p)ζ C ≤ ζ C d d + 1 − ζ C d ζ C ≤ 2ζ C . Therefore, the communication complexity is equal to O (d + ζ C T ) . Considering the fact that we use a mini-batch of stochastic gradients, on average, the number of stochastic gradients that each node calculates at each communication round equals pB + (1 − p)2B ≤ O nεB σ 2 · σ 2 nε + 2B = O (B) . Considering the initial batch size B init , the number of stochastic gradients that each node calculates equals O(B init + BT ).