DASHA: Distributed Nonconvex Optimization with Communication Compression and Optimal Oracle Complexity
Authors: Alexander Tyurin
Peter Richtárik
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Nonconvex Optimization
Variance Reduction
Compressed Communication
Distributed Optimization

Abstract: 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, DASHA-MVR 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 $\varepsilon$-stationary point, and considering the random sparsifier Rand$K$ 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, 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.

Published as a conference paper at ICLR 2023
DASHA: DISTRIBUTED NONCONVEX OPTIMIZATION WITH COMMUNICATION COMPRESSION AND OPTIMAL ORACLE COMPLEXITY
Alexander Tyurin
Peter Richtárik
KAUST
KAUST
Saudi Arabia
Saudi Arabia r richtarik@gmal com
elexandertiurinegne com
ABSTRACT
We develop and analyze DASHA: new family of methods for nonconvex dis- tributed optimization problems. When the local functions at the nodes have a finite-sum or an expectation form, our new methods, DASHA-PAGE, DASHA-MVR and DASHA-SYNC-MVR, improve the theoretical oracle and communication com- plexity of the previous state-of-the-ar method MARINA by Gorbunov et (2020). In particular, to achieve an e-stationary point, and considering the random sparsifier RandK as an example, our methods compute the optimal number of gradients O (VT/sv/) and O (22) in finite-sum and expectation form cases, respectively, while maintaining the SOTA communication complexity O (%/ev)). Furthermore, unlike MARINA, the new methods DASHA, DASHA PAGE and DASHA-MVR send compressed vectors only, which makes them more practical for federated learning. We extend our results to the case when the functions satisfy the Dolyak-t.ojasiewäk condition. Finally, our theory is corroborated in practice: we see a significant improvement 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 al., 2020) and robustness (Bubeck & 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' (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 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 al., 2021), fighting with stragglers (Li et al., 2020a), and optimization over time-var vare-varying directed graphs (Nedić & 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., 10. this paper, we focus on this last approach.
Alternatively, sometimes the terms: machines, workers and clients.

---

Published as a conference paper at ICLR 2023
1.1 PROBLEM FORMULATION
In this work, we consider the optimization problem
- f((2)
min ZER
f(x) f(x)=
where Rd IR a smooth nonconvex function for E [m] ( ,.). Moreover, we assume that the problem is solved by compute nodes, with the 7th node having access to function fi only, via an oracle. Communication is facilitated by an orchestrating server able to communicate with all nodes. Our goal is to find e-solution (s-stationary point) of (I): (possibly random) point t E Rd such that E [ E.
1.2 GRADIENT ORACLES
We consider all of the following structural assumptions about the functions ( each with its own natural gradient oracle:
Gradient Setting. The 7th node has access the gradient Vf R2 Rd of function fi.
2. Finite-Sum Setting, The functions {fil'= have the finite-sum form
f((x) Σ Sus(1), Vi E [n],
where Jūj Rd - IR is a smooth nonconvex function for all j E [m]. For all i E [n]]. the 7th node has access to a mini-batch of B gradients, B Ejet, (.)(),, where T is multi-set of i.i.d. samples of the set [m]) and [7,] B.
Stochastic Setting. The function fo is an expectation of stochastic function, f(()) = Eg (z)
Vi [n),
(3)
where fi Rd x Sg + R. For fixed E R, fa <) is a random variable over some distribution Di. and, for fixed & E Sgg fa(2; {) is a smooth nonconvex function. The ht node has access to mini-batch B stochastic gradients 1 Σラ (if of the function fa through the distribution Di, where [- is a collection of i.i.d. samples from D,
1.3 ORACLE COMPLEXITY
In this paper, the oracle complexity of method the number of (stochastic) gradient calculations per node to achieve an e-solution. Every considered method performs some number of communi- cations rounds get an e-solution; thus, if every node (on average) calculates B gradients in each communication round, then the oracle complexity equals O (Binie + BT'), where Biiit is the number of gradient calculations in the initialization phase of a method.
1.4 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 Rd + Rd is an unbiased compressor if there exists w E IR such that
E [[C(x)) x,
E [[((s) ~11²] < s w
Yar Rd
(4)
We denote this class of unbiased compressors as U(w).
One can find more information about unbiased compressors (Beznosikov 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, satisfying the following assumption.
Assumption 1.2. C. U(w) for all [n]. and the compressors independent.
2

---

Published as a conference paper at ICLR 2023
Table General Nonconvex Case. The number of communication rounds (iterations) and the oracle
complexity of algorithms to get an e-solution (F. [ | S E), and the necessity (or not) of algorithms to send non-compressed vectors periodically (see Section 3).
Setting
Method
T = # Communication Rounds" Oracle Complexity
Full!
MARINA
144/vm
T
Yes
Gradient
144/vR
DASHA (Cor. 6.2)
T
No
Finite-Sum
VR-MARINA
144/V7
(1++)mm
+ BT
Yes
DASHA-PAGE (Cor. 6.5)
1+s/vm
BT
No
EVAB
VR-MARINA (online)
a²
Vitwa
B BT
Yes
Stochastic (3)
DASHA-MVR (Cor. 6.8)
1tw///
+ En
x²
+
33
Buy a² mn
+ BT
No
DASHA-SYNC-MVR (Cor. 6.10)
14w/vm o²
A
Bw BT
Yes
quantization parameter, n # of nodes, # of local functions (only in finite-sum case (2)). a² variance of stochastic gradients (only in stochastic case (3)), B = batch size (only in finite-sum and stochastic case). To simplify bounds, assume that w 1 6 (4/ce), where d is dimension of (I) and the expected number of nonzero coordinates that each compressor C, returns (see Definition 1.3).
Only dependencies w.r.t. the following variables are shown:
Dues algorithm periodically send full (non-compressed) vectors? (see Section 3)
can always choose the parameter RandK such that this term does not dominate (see Section 6.5).
1.5 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; is Çc. == sup E [[]C;())llgl where | is the number of nonzero components of E Rd Let Sc Let
= max Sc.
In this paper, the communication complexity of a method the number of coordinates sent to the server node to achieve e-solution. If every node (on average) sends ( coordinates in each communication round, then the communication complexity equals O (Siit + CT), where T number of communication rounds, and Çiit is the number of coordinates sent in the initialization phase.
We would like to notice that the established communication complexities compared to previous upper bounds from (Gorbunov et al., 2021; Szlendak et al., 2021; Mishchenko et al., 2019; Alistarh al., 2017), and in this line of work, the comparisons of the communication complexities with respect to the number of send coordinates. As far as we know, in this sense, no lower bounds proved, and it deserves separate piece of work. However, Korhonen & Alistarh (2021) proved the lower bounds of the communication complexity with respect to the number of send bits in the constraint optimization setting that x E [0, 1]d, so our upper bounds can not be directly compared to their result because we operate on different level of abstraction.
made
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-ar methods were proposed by Sharma et al. (2019); Li et al. (2021b), showing that after O (1/=) communication rounds and
Vm
0
(5)
Ev
3

---

Published as a conference paper at ICLR 2023
Table Polyak-Lojasiewicz Case. The number of communications rounds (iterations) and oracle complexity of algorithms to get an c-solution (E [f]] - f I E), and the necessity (or not) of algorithms to send non-compressed vectors periodically.
Setting
Method
Communication Rounds M
Oracle Complexity
Full?
Grudient
MARINA
+ ((1+w/v7)
T
Yes
DASHA (Cor. L10)
No
Finite-Sum (2)
+ Ailtw/mm
BT
Yes
DASHA PAGE (Cix.
BT
No
Stochastic (3)
MARINA (online)
Alltw/v + penB + v/tule /EEB
BT
Yes
DASHA-MVR (Coor 1.1))
M1tHW/V)) + pent 2 Ron
BT
No
P5
DASHA SICHA-SYNG-AAR MVR (Cor. 1.21)
(//55)
BT
Yes
penz JenB
Logarithmic factors omitted and only dependencies w.t. the following variables shown: L the worst case smoothness constant, = PL constant, = quantization parameter, = # of nodes, m = # of local functions (only in finite-sum case (2)), batch size (only finite-sum and stochastic case). To assume that + è (4/a) where d is dimension of
= variance of stochastic gradients (only in stochastic case (31), simplify bounds, coordinates that each compressor C, returns (sec Definition 1.3).
and Çc the expected number of nonzero
Does the ulgorithm periodically send full (non-compresed) vectors? (see Section 3)
6 One can always choose the parameter of RandK such that this term does not dominate (sce Scction 6.5).
calculations of V fig per node, these methods can return an e-solution. Moreover, Sharma et al. (2019)
show that the same can be done in the stochastic setting after
o EN
o
(6)
Ea/2n
stochastic gradient calculations per node. Note that complexities (5) and (6) optimal (Arjevani et al., 2019; Fang et al., 80;8; Li et al., 2021a). An adaptive variant was proposed by Khanduri et al. (2020) based on the work of Cutkosky & Orabona (2019). See also (Khanduri al., 2021; Murata Suzuki, 2021).
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/hnn that the nodes send to the server to find an E-solution. Two important families of compressors are investigated in the literature 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., 202 1), 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 al. (2017) developed the QSGD method providing convergence rates of stochastic gradient method with quantized vectors. However, the nonstrongly convex case was analyzed under the strong assumption that all nodes have identical functions, and the stochastic gradients have bounded second moment. Next, Mishchenko et al. (2019); Horváth et al. (2019) proposed the DIANA method and proved convergence rates without these restrictive assumptions. Also, distributed nonconvex optimization methods with compression were developed by Haddadpour et al. (2021); Das et al. (2020). Finally, Gorbunov al. (2021) proposed MARINA the current state-of-the-arr distributed method in terms of theoretical communication complexity, inspired by the PAGE method of Li et al. 1a)
3 CONTRIBUTIONS
We develop a new family distributed optimization methods DASHA for nonconvex optimization problems with unbiased compressors. Compared to MARINA, our methods make more practical and
4

---

Published as a conference paper at ICLR 2023
simpler optimization steps. In particular, in MARINA, all nodes sinulhaneussl send either compressed vectors, with some probability p. or the gradients of functions {ft)== (uncompressed vectors), with probability 1 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 nodes always send compressed vectors, and ii) the server never synchronizes all nodes in the gradient setting.
Further, a simple tweak in the compressors (see Appendix D) results in support for partial participa- tion in the gradient setting, 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 and 2) in the finite-sum setting. Indeed, if the number of functions m is large, our algorithm DASHA-PAGE needs v times fewer communications rounds, while communicating compressed vectors only.
New theoretical SOTA complexity in the stochastic setting. We develop new method, DASHA- SYNC-MVR, improving upon the previous state of the art (see Table 1). When E small, the number of communication rounds is reduced by a factor of V + 1. Indeed, we improve the dominant term which depends on g (the other terms depend on E 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. Moreover, 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.
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 Rand compressor (see Definition F.I), we show that DASHA-PAGE, DASHA-MVR and complexities while attainting the -ftth--rtt communication complexity as MARINA, which needs to use the stronger gradient oracle! Therefore, our new methods close the gap between results from (Gorbunov al., 2021) and (Sharma et al., 2019; Li al., 2021b).
attain these optimal oracle
4 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 & Orabona, 2019: Tran- -Dnn 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", the server in each communication round calculates the next point af+1 and broadcasts it to the nodes. Subsequently, all nodes in parallel calculate vectors h 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" ++1 We refer to Section to get better intuition about DASHA.
We note that in the stochastic setting, our analysis of DASHA-MVR (Algorithm 1) provides a subopti- mal oracle complexity w.r.t. (see Tables I and 2). In Appendix J we provide experimental evidence that our analysis is tight. For this reason, we developed Appendix C) that improves the previous state-of-the -he results and sends non-compressed vectors 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.
MISHA-SYNC-MVE (see Algorithm 2 in
5

---

Published as a conference paper at ICLR 2023
Algorithm DASHA
1: Input:
starting point x E IRd stepsize 7 O, momentum a E (0, 11, momentum (0, 1] (only in DASHA-MVR), probability p E (0. (only in DASHA-PAGE), batch size B (only in DASHA-PACE and DASHA-MVR), number of iterations 2 +> Ri=t 9 on the server
2: Initialize 5. E _Rd hg E Hd on the nodes and g
3: for = 0, 1....... T
do
4: x++1 x¹ -7g
1,
with probability p
5: Flip coin et
(only in DASHA-PAGE)
0, with probability p
6: Broadcast +1 +1 to all nodes
7: for n in parallel do
V (c
(DASHA)
if = M Ejer (Viis(att))- -V/((())))))(((
fi(t+t1)
8:
h
++
if c =0
(DASHA PAGE)
B Σド v + (1-b) b) (M.
3B2 دうز V DASHA-MVR)
m C, (h$+1 14 (g) h()
9:
10:
g. = gf + m
11:
Send m; 1+1 to the server
end for
13:
g =0 =gg + 1/4 - m ++1
end for
15:
Output: HT chosen uniformly at random from {x") T-1
Ik=0 (or x under the PL-condition)
5 ASSUMPTIONS
now provide the assumptions used throughout our paper.
Assumption 5.1. There exists f" E IR such that f fx) 2 f for all R.
Assumption 5.2. The function is L-smooth, i.e.,
[v - ([(x)-//(]] < L || yll
for all v, y E Rd.
Assumption 5.3. For all E [n], the function f; is smooth. 2 We define 1² Em= L7.
The next assumption is used in the finite-sum setting (2).
Assumption 5.4. For all i E [n]. E [m]] the function fij is Liy-smooth Let Lmax == max Lij.
The two assumptions below are provided for the stochastic setting (3). Assumption 5.5. For all E [m] and for all x E Id, the stochastic gradient V f(::g) is unbiased and has bounded variance, i.e.,
(v = ff()),
and Eg [V - oz
VA()))?
where x² 2 O.
Assumption 5.6. For all i [n] and for all x, E R,, the stochastic gradient V,((z;;) satisfies the mean-squared smoothness property, i.c.,
Ee -Vi(i)) (V)((z) V {((
- - Vf((v)))
< L2 x yl
Note that one always take L2 = 8 = - L? However, the optimal constant L can be much hetter hecause 1,2 < (1 Er_ 1x)² 5" 12

---

Published as a conference paper at ICLR 2023
THEORETICAL CONVERGENCE RATES
Now, we provide convergence rate theorems for DASHA, DASHA-PAGE and DASHA-MVR. All three methods are listed in Algorithm and differ in Line 8 only. At the end of the section, provide theorem for DASHA-SYNC-MVR.
6.1 GRADIENT SETTING (DASHA)
Theorem 6.1. Suppose that Assumptions 5.1, 5.2, 5.3 and 1.2 hold. Let us take 1/ + 1)
-1
L
(2w 2
and o. = ht = -Vi((²)) for all i E [m] in Algorithm (DASHA),
1(5() S
then E
[|
7T
The corollary below simplifies the previous theorem and reveals the communication complexity of DASHA.
Corollary 6.2. Suppose that assumptions from Theorem 6. hold, and of Nº f=(xx²) for all
i E [m], then DASHA needs T T= T (S(x)) (*) (T. (.. communication rounds
to get an e-solution and the communication complexity is equal to (d + (cT), where Sc is the expected density from Definition 1.3.
In the previous corollary, we have free parameters w and Sc. Now, we consider the RandK compressor
(see Definition F.1) and choose its parameters 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
RandK with K Se d/ /n, then the communication complexity equals O d++ E(f(2')-
CVT
6.2 FINITE-SUP SUM SETTING (DASHA-PAGE)
Next, we provide the complexity bounds for DASHA-PAGE.
Theorem 6.4. Suppose that Assumptions 5. 5.2, 5.3, 5.4, and 1.2 hold. take 1/ (2w + 1),
probability p E (0. 1),
48w (2w +1)
(1 p) max
2 p) L2 2
5 L+
n
B
pnB
and di ht f((x for all [n] in Algorithm (DASHA-PAGE) then E 2 - T
|Vf(+)) s
Let us simplify the statement of Theorem 6.4 by choosing particular parameters. Corollary 6.5. Let the assumptions from Theorem 6.4 hold, B/(m+ B), and ge = hg = V/i(29)
for all i [m). Then DASHA-PAGE needs
O:= e
(+(*9))))
L+ Wi+
+ nt
w
m
Lmax B
Vn
nB
communication rounds get E-solution, the communication complexity is equal to O (d + (cT), and the expected of gradient calculations per node equals O (m + BT), where Çe is the expected density from Definition 1.3.
The corollary below reveals the communication and oracle complexities of Algorithm (DASHA- PAGE) with RandK.
7

---

Published as a conference paper at ICLR 2023
Corollary 6.6. Suppose that assumptions of Corollary 6.5 hold, B S Vm/n, and we the unbiased compressor RandK with K = SC = = (Bd/ym). Then the communication complexity of Algorithm is
o ca+ I Tmmax (5(a9) -
Ev/
and the expected # of gradient calculations per node equals
O m Lmax (f(z²) f vm
f*)
Svn
Up to Lipschitz constants factors, bound (8) optimal (Fang et al., 2018; Li 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.
6.3 STOCHASTIC SETTING (DASHA-MVR)
Let ht := + M. 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 2
b E (0,1), 5 L+ (2w+2x+1)
(1-b) B
+ {2)
+ 4(1-b)2 bn
and gf = for all e [n]]
in Algorithm (DASHA-MVR). Then
[|]
1 T
2
(
2 211000 -
E
7
32hw (2w + 1)
1
| VS(GS)))) + 96w (2w +
4
bnB 1boo.
nB
Corollary 6.8. Suppose that assumptions from Theorem 6.7 hold, momentum b 1 Eim f for all i E [mi], and batch e (min V LrBB ot, aeB] }). and de h. Bin
size Bini θ (B/b). then Algorithm 1 (DASHA-MVR) needs
T:= (1(0)) f4) (
-++
σ² En B
L
o²
Vn
B
nEB
communication rounds to get an e-solution, the communication complexity is equal to (d + (cT), and the number of stochastic gradient calculations per node equals O Binit -T), where &o 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 S VEN we take RandK
with K = Sc = BdyEn
and I == max(L, Lg, L}. Then the communication complexity equals
do -
(9)
VnE
VNE
and the expected of stochastic gradient calculations per node equals
2 + (f(x))) -
(10)
2//22
8

---

Published as a conference paper at ICLR 2023
Up Lipschitz constant factors, the bound (10) is optimal (Arjevani 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 in DASHA (see Corollary 6.3) or MARINA for small enough 8
6.4 STOCHASTIC SETTING (DASHA-SYNC-MVRR)
We now provide the complexities Algorithm 2 (DASHA-SYNC-MVFF) presented in Appendix C. The main convergence rate Theorem I.19 is in the appendix.
Corollary 6.10. Suppose that assumptions from Theorem 1.19 hold, probability p = min {
<c neB =² batch size B' = O² and hy g. Bin Eim fi for all [m],
initial batch size Binit θ [max
d² ne
B&) }
then DASHA-SYNC-MVR needs
T: o 1 (ʃ(29) (c)
L
L++ Vn
+++
w
d Cen
Lo
+
o² ne
vn
en
VB
B
communication rounds get an e-solution, the communication complexity is equal O (d + (cT), and the number of stochastic gradient calculations per node equals O -T), where Se is the expected density from Definition 1.3.
Corollary 6.11. Suppose that assumptions of Corollary 6.10 hold, batch size B
_ Ven
take
RandK with K = Cc θ [BdEEn and L == max L, Lo, D}. Then the communication complex- ity equals
o do (( - -(*
(11)
VNn
VNE
and the expected # of stochastic gradient calculations per node equals
2 +
-
(12)
nE
8/2n
Up to Lipschitz constant factors, the bound (12) is optimal (Arjevani et al., 2019; Sharma et al., 2019), and unlike VR-MARINA (online), 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 E.
6.5 COMPARISON DASHA-MVR AND
Let us consider RandK (note that + d/cc). Comparing Corollary 6.8 to Corollary 6.10 (see Table 1), we see that DASHA-SYNC-MVR improved the size of the initial batch from
+ max
o² Bw
o² nEB
o² to θ max nE Bw)) Fortunately,
control the parameter K
nE?
in RandK, and Corollary 6.9 reveals that we can take K e BBveen and get Bw ncB nc"
As result, the "bad term" does not dominate the oracle complexity, and DASHA-MVR attains the optimal oracle and SOTA communication complexity. The same reasoning applies to optimization problems under PE-condition with K θ [Bd/Ren
ACKNOWLEDGEMENTS
The work of P. Richtárik was partially supported by the KAUST Baseline Research Fund Scheme and by the -AUST- Center of Excellence in Data Science and Artificial Intelligence. The work of A. Tyurin was supported by the Extreme Computing Research Center (ECRC) at KAUST.

---

Published as a conference paper at ICLR 2023
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances Neural Information Process- ing Systems (NIPS), pp. 1709-1720, 2017.
Yossi Arjevani, Yair Carmon, John Duchi, Dylan Foster, Nathan Srebro, and Blake Woodworth. Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02363. 2019.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 2020.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. arXiv preprint arXiv:2005. 1003::2000..4165, 2020.
Sébastien Bubeck and Mark Sellke. A universal law of robustness via isoperimetry. arXiv preprint arXiv:2105./2806, 2021.
Chih Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM
Transactions Intelligent Systems and Technology (TIST), 2(3):127,, 2011.
Ashok Cutkosky and Francesco Orabona. Momentum-based variance reduction in non-convex SGD, arXiv preprint 1905. 2019.
Marina Danilova, Pavel Dvurechensky, Alexander Gasnikov, Eduard Gorbunov, Sergey Guminov, Dmitry Kamzolov, and Innokentiy Shibaev. Recent theoretical advances in non-convex optimiza- tion. arXiv preprint arXiv:20/2.066 2020.
Rudrajit Das, Abolfazl Hashemi, Sujay Sanghavi, and Inderjit S Dhillon. Improved convergence rates for non-convex federated learning with compression. arXiv e-prints, pp. arXiv-2012, 2020.
Cong Fang, Chris Junchi Li. Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex op-
timization via stochastic path integrated differential estimator. In NeurlPS Information Processing Systems, 2018.
Ian Goodfellow, Yoshua Bengio, Aaron Courville, and Yoshua Bengio. Deep learning, volume 1. MIT Press, 2016.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In 38th International Conference on Machine Learning, 2021.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mchrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference Artificial Intelligence and Statistics, pp. 1350-2355 PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Joel Hestness, Sharan Narang, Newsha Ardalani, Gregory Diamos, Heewoo Jun, Hassan Kianinejad, Md Patwary, Mostofa Ali, Yang Yang. and Yanqi Zhou. Deep learning scaling is predictable, empirically, arXiv preprint 171iv:1712.0044:
2017.
Samuel Horváth, Chen-Ye 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: 10988, 2019.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:/904.0m 05 15, 2019.
10

---

Published as a conference paper at ICLR 2023
Prashant Khanduri, Pranay Sharma, Swatantra Kafle, Saikiran Bulusu, Ketan Rajawat, and Pramod K Varshney. Distributed stochastic non-convex optimization: Momentum-bars variance reduction. arXiv preprint 2XXx::0005000224 2020.
Prashant Khanduri, Pranay Sharma, Haibo Yang. Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod Varshney. STEM: A stochastic two-sided momentum algorithm achieving near -aar-oopimall sample and communication complexities for federated learning. Advances in Neural Information Processing Systems, 34, 2021.
Jakub Konečný, H Brendan McMahan, Felix X
Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint urXiv:/610.05492, 2016.
Janne H Korhonen and Dan Alistarh. Towards tight communication lower bounds for distributed optimisation. Advances in Neural Information Processing Systems, 34:7254-7266 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, University of Toronto, Toronto, 2009.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429-450, 2020a.
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, 2020b.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp. 6286-6295, PMLR, 2021a.
Zhize Li, Slavomír Hanzely, and Peter Richtárik. ZeroSARAH: Efficient nonconvex finite-sum optimization with zero full gradient computation. arXiv preprint arXiv:2103.01447, 2021b. 20211..
Deyi Liu, Lam M Nguyen, and Quoc Tran-Dinh. An optimal hybrid variance-reduced algorithm for stochastic composite nonconvex optimization. arXiv preprini arXiv:2008. 090550000000..,.......00.0005555 2020.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09200 2019.
Tomoya Murata and Taiji Suzuki. variance reduced local SGD for less heterogeneous federated learning. arXiv preprint arXiv:2102.03: /98, 2021.
Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs. IEEE Transactions on Automatic Control, 60(3):601 -615, 2014.
Yurii Nesterov. Lectures convex optimization, volume 137. Springer, 2018.
Adam Paszke, Sam Gross. Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Aditya Ramesh, Mikhail Pavlov, Gabriel Goh, Scott Gray, Chelsea Voss, Alec Radford, Mark Chen, and Ilya Sutskever. Zero-shot text-to-image generation. arXiv preprint arXiv:2 /2092, 2021.
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.
Pranay Sharma, Swatantra Kafle, Prashant Khanduri, Saikiran Bulusu, Ketan Rajawat, and Pramod K efficient distributed nonconvex optimization
Varshney. Parallel restarted with optimal computation complexity. arXiv preprint arXiv:/9/2.06036 2019.
Rafal Szlendak, Alexander Tyurin, and Peter Richtárik. Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:21 2021.

---

Published as a conference paper at ICLR 2023
Quoc Trann Nhan H Pham, Dzung T Phan, and Lam M Nguyen. A hybrid stochastic optimization framework for composite nonconvex optimization. Mathematical Programming, pp. 1-67, 2021.
Thijs Vogels, Lie He, Anastasiaa Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. RelaySum for decentralized deep learning on heterogeneous data. Advances in Neural Information Processing Systems, 34, 2021.
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, al. field guide federated optimization. arXiv preprint 107.v:2107.06917, 2021.
Hang Xu, Chen- Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, 2020.
12

---

Published as a conference paper at ICLR 2023
CONTENTS
1
Introduction
1.1
Problem formulation
1.2
Gradient oracles
1.3
Oracle complexity
1.4
Unbiased compressors
1.5
Communication complexity..
2
Related Work
3
Contributions
4
Algorithm Description
5
Assumptions
Theoretical Convergence Rates
6.1
Gradient Setting (DASHA)
6.2
Finite-Sum Setting (DASHA-PAGE)
6.3
Stochastic Setting (DASHA-MVR)
8
6.4
Stochastic Setting (DASHA-SYNC-MVR)
6.5
Comparison of DASHA-MVR and DASHA-SYNC-MVR.
A Experiments
15
A.1 Gradient setting
15
A.2 Finite-sum setting
16
A.3 Stochastic setting
17
A.4 Deep neural network training
18
Experiments Details
18
Description of DASHA-SYNC-MVR
19
Partial Participation
19
Auxiliary Facts
19
F Compressors Facts
20
G Polyak-E.ojasiewicz Condition
20
H Intuition Behind DASHA
21
H.1 Different Sources of Contractions
21
13

---

Published as a conference paper at ICLR 2023
H.2
The Source of Improvements in the Convergence Rates
21
Theorems with Proofs
22
L1
Case of DASHA
................................
27
1.2
Case of DASHA under PL-condition
................................
28
L3
Case of DASHA-PAGE
................................
................................
30
1.4
Case of DASHA-PAGE under PE-condition
................................
35
1.5
Case of DASHA-MVR
38
166
Case of DASHA-MVR under PL-condition
45
17
Case of DASHA-SYNC-MVR
48
18
Case of DASHA-SYNC-MVR under PL-condition
55
J Extra Experiments
58
14

---

Published as a conference paper at ICLR 2023
A EXPERIMENTS
We have tested all developed algorithms on practical machine learnings problems'. Note that the goal of our experiments is justify the theoretical convergence rates from our paper. We compare the new methods with MARINA on LIBSVM datasets (Chang & Lin, 2011) (under the 3-clause BSD license) because MARINA is the only previous state-of-thh-aa method for the problem (1). Moreover, we show the advantage of our method on an image recognition task with CIFARIO (Krizhevsky et al., 2009) and a deep neural network. 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 set of powers of two {2' i E 10, 10}} and use the RandK compressor. We evaluate communication complexity; thus, each plot represents the relation between the norm of gradient or function value (vertical axis), and the total number of transmitted bits per node (horizontal axis).
experiments, we take parameters of algorithms predicted by
A.1 GRADIENT SETTING
We consider nonconvex functions
2
f((x)
Σ 3=1
exp(upa
to solve a classification problem. Here, aij E IR is the feature vector of a sample on the 7th node, Vij E {-1,1) 1) the corresponding label, and m is the number samples on the 7th 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 10 in RandK. One see in Figure 1 that DASHA converges approximately 2 times faster.
MARINA: Step size: 0.25
10
MARINA: Step size: 0.5
Number of nodes: 5
MARINA: Step size: 1.0
DASHA: Step size: 0.25
10-3.
DASHA: Step size: 0.5
DASHA: Step size: 1.0
10
10-7.
10 9
0.0
0.2
0.4
0.6
0.8
1.0
1.2
# #bits /
1e7
Figure 1: Classification task with the mushrooms dataset and gradient oracle.
'Code: http::/::....t.oooooooossseeeeee
15

---

Published as a conference paper at ICLR 2023
A.2 FINITE-SUM SETTING
Now, we conduct the same experiments as in Section A. with real-sim dataset (dimension d 20,958, number of samples equals 72, 72,309) from LIBSVM in the finite-sum setting; moreover, compare VR-MARINA versus DASHA-PAGE with batch size B = in both algorithms. Results in Figure 2 coincide with Table our new method DASHA-PAGE converges faster than MARINA. When K = 100, the improvement is not significant because 1+*/vm dominates vm and both algorithms get the same theoretical convergence complexity.
(see Table 1),
cynB
K - 100
500
K - 2000
10
10
10-5
10-5
Number of nodes: 5
10-5
10-6
10
VR-MARINA: 0.03125
MARIMI:::
MARINA: SUE: 0.0625
VR MARIMAA
MARINA: 0:125
MARINA: Stop
VR MARINA: Step size: 0.125
VR. MARINA: Step size: 0.25
VR MARINA: Stop size: 1.0
DASHAPAGE:
0.08125
DASHAPAGE:
DASHA-PAGE 5ipg.0.5
DASHA-PAGF: Step size:
DASHAPPAGE: Step
DASHA-PAGE: Step
DASIA-PAGE: Step size: 0. 125
DASHA-PAGE: Step size: 1.0
DASHA-PAGE: Step size: 2.0
10
6
7
10-7
0.0
0.5
1.5
#bits n
1e8
#bits n
1e8
#bits /
1e9
Figure 2: Classification task with the real-sim dataset and K {100; 500; 000) in RandK in the finite-sum setting.
16

---

Published as a conference paper at ICLR 2023
A.3 STOCHASTIC SETTING
In this experiment, we consider the following logistic regression functions with nonconvex regularizer (fi)=1 solve a classification problem:
exp (1.TTyc))
By k=1 fog
[1( = Pyg/mm)
log
+
Exe(112) exp (a)
WE (1.2)
where 21, 22 E R.d {.)x is an indexing operation, dij E R is feature of sample on the 7th node, Yij E { [1.2] is a corresponding label, m the number of samples located on the 7th node, constant À 0.001. We take batch size B and compare VR-MARINA (online), DASHA-MVR, and DASHA-SYNC-MVE that depend on a common ratio o² /n/n 4. We fix /n/ E (10*, 10 and K E [200, 2000) in RandK compressors. We consider real-sim dataset from LIBSVM splitted between nodes. When we increase /nne from 10 to 10 we implicitly decrease because other parameters are fixed. In Figure 3, when is small, DASHA-MVR and DASHA-SYNC-MVRR converge faster than VR-MARINA (online).
2000
10
10
MAMINAAA (anknel: Step DASHA-MA MVHH--WR..R Step size:
VR-MARINA toninnel: 0.25 DASHA-MVR:
DASHA-SYN Step size: d 125
DASHASSNNN-MYR Step site: 0.5
10000
||
10
10-5
6
0.5
1.0
1.5
2.0 n
2.5
3.0
0.0
1.0
1.5
2.0
2.5
3,0
# bits
1e9
#bits / n
1e10
10
10
MARINA (online):
0,015625
VR-MARINA (online::
0.03125
DASHA-MVR:: Step size: 0.00 0.0625
DASHHAMWII Step size: 0.125
DASHA-SYNC NVR: Stop size: 0.0625
DASHA MVR: Stop size: 0.125
-100000
10-5
10-5
". 10-6
10-6
10-1
10-7
0.00
0.25
0.50
0.75
1.00
1.25
1.50
0.00
0.25
0.50
0.75
1.00
1.25
1.50
# #bits/ /
1e10
#bits /
1e11
Figure 3: Classification task with the real-sim dataset, x²) o2/neB {104, 100), and K {200, 2000)
in RandK in the stochastic setting.
"Indeed, DASHA-SYNC-MVR and MARINA. the probability p min (//n=//innnaaaai/ D//oo) DASHA-MVR. the momentum min(K/a /tB/// neB/..).
17

---

Published as a conference paper at ICLR 2023
A.4 DEEP NEURAL NETWORK TRAINING
Finally, we test our algorithms on an image recognition task, CIFARIO 10 (Krizhevsky et al., 2009),
with the ResNet-18 (He al., 2016) deep neural network (the number of parameters d 10"). We split CIFARIO among nodes, and take K ~ 2 106 in RandK. In all methods we fine- tune two parameters: step size Y {0.05, 0.01, 0.005, 0.001} and ratio a² /nee {2, 10, 20, 100). Moreover, we trained the neural network with SGD without compression as baseline, with step size Y E (1.0, 0.5, 0.1, 0.05, 0.01, 0.001). . All nodes have batch size 25.
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-MA works better than VR-MARINA (online) and SGD.
Vanilla SGD: Step size: 0.05
[online): Step
109
DASHA-MRR. Stop size: 0.01; Momentum b: 0.1
DASHA-SYNG-MVR. Step 0.03; Batch Size
Number of rodes 5
10
10-2
1.0
1.5
3.0
1e12
Figure 4: Classification task with CIFAR1O dataset and ResNet-18 deep neural network. Dimension d R 10? and K R 2 10t in RandK.
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 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 samples in a dataset, we randomly ignore N mod n samples from a dataset (up to 4 when = 5).
18

---

Published as a conference paper at ICLR 2023
C DESCRIPTION OF DASHA-SYNC-MVR
In this section, we provide a description of DASHA-SYNC-MVR (sec Algorithm 2). This algorithm is closely related to DASHA-MVR (Algorithm 1), but MASHA-SYNC-MVE synchronizes all nodes with some probability p. This synchronization procedure enabled us to fix the convergence rate suboptimality of DASHA-MVR w.t.a..
Algorithm 2 DASHA-SYNC-MVR
1: Input: starting point x" E R stepsize Y >> 0, momentum a E (0, 1], probability p E (0, 1]. batch size B'. number of iterations T' 1.
2: Initialize g. hg on the nodes and g" = E 9. on the server
3: for 0......,
do
4: f+1 x² -79
5: cL 1, with probability p.
0, with probability 1 1-p
6: Broadcast 21+1 to all nodes in parallel do
7:
for =
8:
if cf tten
9:
h 13"
k=l V f.
c
mi
9i
++1
h
11:
else
h Ej=1 Vz
et+l)
h
Σ V
13:
m. 1+1 = C, (h 1+
- h - a (gf ht))
14:
0 of mi 1+
15:
end if
Send m the server
17:
end for
if c
1 then
19:
g++1 1 Li=1 m 1+1
else
21:
gi+1 g" + EE m 1+1
22:
end if
23:
end for
24:
Output: 4" chosen uniformly at random from {=')
D PARTIAL PARTICIPATION
partial participation mechanism, important for federated learning applications, can be easily implemented in DASHA, Let us assume that the hhh 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 compressor C, we have use the following new stochastic mapping Cy
(x) C(x), with probability p', 0,
(13)
with probability 1 p'.
The following simple result states that the new mapping Cyr is also an unbiased compressor, which that our theory applies this choice well.
Theorem D.I. IfC E U(w), then Co. E -
In the of partial participation, all theorems from Section 6 will hold with replaced by (w+l)/p
E AUXILIARY FACTS
In this section, we recall well-known auxiliary facts that in the proofs.
19

---

Published as a conference paper at ICLR 2023
1. For all E, Rd, we have
| + y1 2 2 11yl1
(14)
2. Let take random vector Rd then
E
|
E
||E [E]] + [|]|?
(15)
F COMPRESSORS FACTS
Definition F.1. Let us take a random subset S from [s] = K, K E [d]. We say that a stochastic
mapping C Rd Rd is RandK if
C(x)
Σ
IjCjo
K
JES
where {es is the standard unit basis.
Informally, RandK randomly keeps K coordinates and zeroes out the other.
Theorem F.2. IfC is RandK, then C E U - 1).
See the proof in (Beznosikov et al., 2020).
In the next theorem, we show that Cpr (z) from (13) is an unbiased compressor.
Theorem D.1. C E U(w), then Co' E [+11 -1).
Proof. First, we proof the unbiasedness:
B (x))
+ ((-
VE
Next, we get bound for the variance:
1 C(x) - -z 2 =19 (1 1xx12
E |Ic - =12] = p'E
1/2 11c(x)112 - (1 ((x), (2 ) + ||=11 )
1
d'E
+ (1 -p') ||x|1
1
[[((aa)]] -(2 -2- -1) ||=|| + (1 - p²) ||0||
E
//
[[c(=)]]] - -1<=||?
E
From C E U(w), we have
E [[ - x1|]]
w +
||0|| - ||
( p'
-11
1) ||
p'
G POLYAK POLYYA--EIJSSEWIIC CONDITION
In this section, we discuss our convergence rates under the Folyak-Lojasiewice. PE-condition: Assumption G.1. A functions f satisfy (Polyak-Lojasiene) PE-condition:
> 2p(f(x) f*), Vx E R,
(16)
where 1== innf f(x) > X
20

---

Published as a conference paper at ICLR 2023
Here different notion of an e-solution: it a (random) point ε, such that E [f(2] f S
Under this assumption, Algorithm 1 achieves a linear convergence rate O (In (?/)) instcad of sublinear convergence rate O (1/a) in the gradient and finite-sum settings. Moreover, in the stochastic setting, Algorithms and 2 also improve dependence on E. Related Theorems 1.9, I.12, 1.15 and I.20 stated in Appendix I. Note that in the finite-sum and stochastic settings, Theorems I.12 and L.20 provide new SOTA theoretical convergence rates (see Table 2).
H INTUITION BEHIND DASHA
In this section, we want outline intuition of differences between the proofs of DASHA and MARINA that helps us to improve the convergence rates.
H.1 DIFFERENT SOURCES OF CONTRACTIONS
In both algorithms the proofs analyze Ee ||10 vf(**+
1|]]]
norm of difference between gradient V J (x*+11 and gradient estimator g'+1, For simplicity, we assume that n 1, then for MARINA, we have
Ee |
p / v/( (1 (1- p)licc [lls + C
- vs(att))11)
Ee [10* (V( -)((aa) - /
(1) (1 - p) |وا vf=")) + +1
Ee |||c (Vf(z*t)) vf(x*)) (Vf(=*t)) vf((t))]11
(1- p) g6 ((("))| + (1- p)w (f - v|(=")11
||1 11 \f >||] - (1 p) 11g - vf(x*)]11 +...
In order to get a contraction, i.e., Ee
MARINA has to send full gradient (z**+)) with the probability p > 0.
Now, ler us look how we get contraction DASHA:
Ee ||g ++ Vf(a*+>>li"" 1|a]
Ec |11s + C (VS(x - Vs(c²) a (g' - VV(a))) v5(a
Ec |||s* + (Vf(x*t1) Vf(**) a (g' vf(aa))) -
(n (1 (1= 11g \1(
+ Ee ||c (v - vf(xt) a (g' vf(xt))) - (Vf(xt+1) vf(a*t - a a - vz(xx))) ||]
2 (1 a)² | - vz(zk) 111 + w / (2( - vf(z - -a - v)(++))
(1)
< ((1 a)² 2wm²) "105 - vʃ(2 1| 2w
$ (1 a) |gg () 2w Vf vz(*
In the last inequality we use that S 1/2w+1. On can see that we get exactly the same recursion and contraction. The source of contraction a correction -a(g' vf(=*)) inside the compressor
H.2 THE SOURCE OF IMPROVEMENTS IN THE CONVERGENCE RATES
Let briefly explain why we get the improvements in the convergence rates of DASHA in the finite-sum setting. The same intuitions implies to the stochastic setting.
In DASHA, we reduce variances from the compressors C and the random sampling 13 separately: have different control variables b and o two different parameters the probability p and
21

---

Published as a conference paper at ICLR 2023
the momentum For simplicity, let us assume that the number of nodes 1. Let consider Lyapunov function from our proofs:
E [f(x') [*] + (4w + 1) E [lla* 1 -111
+ ( 16w (2w 1) E -V
In contrast, MARINA (VR-MARINA) has only one control variable of and on parameter p. A Lyapunov function of MARINA is
E Bff(2) - f* + ? 2p [19"' f((""))
MARINA has simpler Lyapunov function that leads to suboptimal convergence rate. Intu- itively. having one control variable and one parameter is not enough to reduce variances from two different sources of randomness. So in DASHA, the parameter m+B:
B while in MARINA
p min compressors C.
B Se m++ d
because the parameter p of MARINA helps reduce the variance from the
I THEOREMS WITH PROOFS
Lemma I.1. Suppose that Assumption 5.2 holds and let g²+1 = x² -gg.. Then for any g' E TRd and
7 have
f(x (( [
I.
10011=x110 x21]2+ ||a041-2011
- - (17)
27
2
The proof of Lemma 1.1 is provided in (Li et al., 2021a).
There different sources randomness in Algorithm the first one from vectors {h ( Ji=1 and the second one from compressors {C.) In this section, we define E, [-] and Eg H to be conditional expectations w.r.t. [h K==1 and {C,] accordingly, conditioned on all previous randomness.
Lemma 1.2. Suppose that Assumption 1.2 holds and let us consider sequences th and 14+11 from
Algorithm 1, then
Eg
||0
h 1
11]
2w n
n
h ++
mill
+
2w
MEll + (1 - (1==)² a)2 16112
n2
i=1
(18)
and
Ec ||0 h 1[t111]]
< 2w 1
-ntll²
(2a (1 (1- 1a)=))) |1 hgll? We [n]. (19)
First, we estimate Ec 1201-1++100 -1+ 1111
Proof.
Eg [19 +1 - 112
n g" + Σ
= Eg
C, (h(+1 11 - -aa - hn))) - h+41
t=1
27
n
(4)(15)
Ee
Σ C. (h h (gt ht))
(h
(gf h())
m
(1 - a)² ||0 10
Using the independence of compressors and (4), get
Ec [100 - 11
22

---

Published as a conference paper at ICLR 2023
1
Fec ||c. (n5+) Mi a (gf -h)) (of+1 hg a agt nn)) [1]]
[]]
n²
(1
a)² ||0t - -1'122
W
|| - n1 (g) - nn) 1|2 + (1 - -a)²-a2200 10/ - -1/91
2w
h++1
M 2 2aaw
n
11 M1ll 2 + (1 - a)² ||9 11'11
n
n
|115t1 -,,---++11 1p]:
Analogously, we can get the bound for Ee
|100 1lof+t1 11= [13]
Ec
Eec |lot + C2 (N 1 - a (0) k()) - -1,+ n1/+11]]]
Ee ||c, (hŞ+) - h4 h a (9: - ht)) - (15+) hh a (gf - h2t) [1]]
+ (1 a)² ||o -!/12²
w || 14 a (oi - 11 (1 (1-a)²16 l|o1 AEll?
2w || - n!ll² 2 + 2a²w 11/5 - -/1l² (1 a)² 11 h9
2w || - hill? 2 + (2a²w + (1 - -))) |Rst hGll?
Lemma 1.3. Suppose that Assumptions 5.2 and 1.2 hold and let us take 1/ (2w + 1), then
R. [[((ttt)]] 7 (2w + 1) F
||10t1
11]
+
27w
1+1
ngtty12)
n
72
s E f(x') - 2/ |Va(att)] -(1
L
||att1
- x²1
+ y | ((=
2%
2
+ +2 + E) |1o" - 1=11a]
+
27w
E
1
ngll"
8yw (2w + +1)
| +1
htll?
n
n
n
n
Proof. Due to Lemma I.1 and the update step from Line 4 in Algorithm 1, we have
E [[(x+t))] < E s(x*) - 7 2 |
1
|
x11 2
+ 2 l1'6 - Vs(('))
27
2
2
= F. s(xt) 1 |
1
|1, - -011( 2
+ 2
"واا n²* + h²- V((a'))
(20)
2y
2
2
< E f(x²) - 1 |لل
1
|| - 11 + 7 (1ls* - hhth $11 + || -
2-
2
In the last inequality we use Jensen's inequality (14). Let us fix some constants K, 17 E [0, oo) that will define later. Combining bounds (20), (18), (19) and using the law of total expectation, we get
E [f
+ *F |1g0t1 11---1+4117 113 + +.F
1
8+1 - 14
n
i=1
< F. [(xt) - - "11
1
L
||
- xe1l
+ (10* - 16l12 + 1-1--- ()(a)))1))
2>
23

---

Published as a conference paper at ICLR 2023
+ xF
2w
|,st1 - n6ll
2a?w n²
Σ 1=1
n
1lst - -nall (1 - aa)² 11gt 101
n²
2w
| 1 - n2/1²+ + (2a + (1 - -a)²t)
-
Σ |1o/ 1:]l"
+ +,
11 i=1
" i=1
= E f(x') 7 ||
(2]
1 L
|| - 2²1 + ||1' V
2
'2
2
(7 + 16 (1 - -)²) |11o* - [1]
+
@ + 17 22 + (1 - aa+t)
l1l - n3ll?
+
(2kw + 20pw
|| M ||?
+
E
(21)
n2
Now, by taking x= = 2. we can see that 7 + K (1 - a)² S K, and thus
E [[(+tt]]]
+ 2F
+1/F.
|
+1 11
n i=1
s E fxx²) -2 2/1 ||Vs(a'))1
(
[1
1
L 2
||
201 + + 111e - V
27
+ 2 E |19' - 1²1la]
+ 2yow + (2a² + (1 -)}))
l1st - hEll Σ
E
1=1
+ 22w + 21Tw E
1 Σ 11
Next, by taking 17 = 29w and considering the choice of a, one can show that
2yaw
2aaw + (11
S Thus
E [[(]tt]]]
+ + 1) E |100 ++1 - 1 11]
27w
1 n
9 ++ h1 + 111
+
E
n
12
SE [(x') - 2/2 |[{(aa)]1
I.
||
x01|² 11 + x 1| - v[(2))12]
27
2
+ + + 1) E |110* - -1=
27w
|1of nell?
E
n
2yw (2w + +1 +
4yw=
12
| + 1 - h 12ll2
+
E
n
n
i=1
S E ((a)) - 7
|V
L
||00 [+1 - x 11 + + 111h-- - V
2
27
2
+ 72w + 1) E |11s - 1='1"7]
+ 2Yw E
l1 - n8l12)
+ 8yw (2w + 1) E
1 Σ
|
- n1ll |
1=1
24

---

Published as a conference paper at ICLR 2023
The following lemma almost repeats the previous one. We will use it in the theorems with Assumption
G.I.
Lemma 1.4. Suppose that Assumptions 5.2, 1.2 and G.I hold and let us take a = 1/ (2w + 1) and
2. then 7 S
2
E [f(ctt]]] + +22(2w + 1)E
[110t1- 1411
+
8yw
E
lo n 11
s E [(x0)- - 2 |((xt)]
1
L
|| - x1'1? + > || - {イ(m))| 11]
27
2
+ (1 - yu) (2w + 1jF ||ls - 11" [[]
8y F.
1
| m3ll? ?
+ (1 - yu)
22w + 1) E Σ
mill"
n
Proof.
Up to (21) we can follow the proof of Lemma 1.3 to get E [[(xtt)]]
a
+ nF. [10 - -1 12]
+ t/F
11
+1
h1
h1+111 11? 2
Y=1
E f(z¹) - "|
2//
1
L
||
=21 + + 111h-1 vr(a')1
27
2
(7 + x01 - (1-1))))))
(1a))) E ||10* - 1'11"]]
2nsaPw + 17 22 + (1- - (1-a)))
1 n
E
Σ
|1 hōll? 2
n1
n
12k
1 n
+
+ 2mpw
E
boft1 hill
n
n
Now, by taking k=
21, a we can see that + k (1 - a)² S (1 ()) K. and thus
F.
[[]
+ 27 E. 2
- -1,4111?) ||1 17F
1
1 - 14 n1t2113
+
-
n2 1=1
< F ((x²) - -/2 || (zxz))1-= (
-(1)
1
L
||aft1
- =01 + 1105- - -]((a))1
27
2
+ (1 - () 27 E |10' - -n'1²]
2 a
+ 4Yyw + 1) 2a²2 + (1 1- a)²)
llst - 13l1?
E
1=1
( (4yw + 2TT E 1 Σ 11 11
AEll?
+
Next, by taking 1) = 8yw and considering the choice of a, one can show that
4ymw 12
17 2aFw + (1 (1-a))) ))²) s (1 9) n. Thus
F. [[](tt]]]
25

---

Published as a conference paper at ICLR 2023
+ 2yw 1)F |11 -
+
8yw
E.
n Σ
n
o10 + nn!t11²))
n
S f(x²) 2 /f ( 2
7
||
2²1 + + 11,e v((2")]1
2
+ (1-5) ②) (2w + 1)E ||9'' h1 ||
+ [ 2
a
8y E
|1lt
11ll
12w + +1 16y
| - Ail??
+
E
fx²) - Vf(('')] )|(
1 L
|| - =211² 21 + 7 111l vf(29)12
$ E
2
27
2
[|9' h2 11] ||]
+
(2w + 1)E
2
+
1
a
8yw
E
11o 1ill
2
20yw (2w 1)
b hEll?
E
n
Finally, the assumption 7 S a. 2n
implies an inequality
2 S 1 - 7pp.
Lemma I.5. Suppose that Assumption 5.1 holds and
E [ff(x(t)] + + s EE[((x))
2 2
E (fx') [1]] + + + yC,
(22)
where V is a sequence of numbers, Tt 2 for all f. E [T]. constant C 2 0, and constant y >> 0. Then
2 (f(x)) -()
f*)
240
+
+ 2C,
(23)
T
where a point S. is chosen uniformly from a set points {x11T-1
Proof. By unrolling (22) for from 0 T 1, we obtain
7 Σ E ||
+ [f(=')] + + + t/00 + TTC.
We subtract fr, divide inequality by x and take into account that f(x) 2 fr for all x e R, and w 2 0 for all t e [T]. to get the following inequality:
[
T-1
2 ( f*)
24 + 2C.
<
7T
is left to consider the choice of point ," to complete the proof of the lemma. Lemma 1.6. Suppose that Assumptions 5.1 and G.1 hold and
E [f(x(+))] + + <E[f(x"]
+ + - - + +nc, 2 E [[[[] [|
where V is sequence of numbers, ve > ffr all 1 E [T]. constant C > 0, constant μ >> 0, and constant 7 E (0, 1/)). Then
C
E [[f(a?) - fr s 7 ((f(x9) f*) + +700
(24)
26

---

Published as a conference paper at ICLR 2023
Proof. We subtract f and use PÊ-condition (16) to get
E E[f(alt)) - - + tyblt1 Σ E [f(x*) - [*] 3 || + + + +oc
2
I (1 - [f + (1- +
(1 71) (B) [f(x²) 84 + +,C.
Unrolling the inequality, we have
E (f((=+1)-ft) + t
(1-74))+ ((f(2)) f*) +Y80) + Gc Σ (1 71)²
1=0
(1-74) ((f(2") f*) + +y80)) + c
is left to note that Tp 2 for all t t [].
Lemma 1.7. If0 < < [L [L+VA - L > 0, and A 2 0, then
1 1
7A
2 0.
2
It is easy to verify with direct calculation.
1.1 CASE OF DASHA
Despite the triviality of the following lemma, we provide it for consistency with Lemma 1.14 and Lemma 1.11.
Lemma L8. Suppose that Assumption 5.3 holds. Assuming that hς Vf((2)) all E [n].
1 from Algorithm / (DASHA) we have
1.
Eg ( = 0.
2.
Eg |11$ - (f( =0, Vi [n].
3.
En. [|1ntt1 -n]11"] S Lス | 201 Vi E [n].
Theorem 6.1. Suppose that Assumptions 5.1, 5.2, 5.3 and 1.2 hold. Let us take 1/ (2w + 1) and
7 S +
(2w(2w+1) 11 1
and hi = fiz") for all E [m] in Algorithm (DASHA), then
[V[("") 27 S
1 М
2 ( -1") [.+
16w (2w 1) 7.
n
4w (1
+ 2 1) 1100 -f((0))2
n n Σ g V
Proof. Considering Lemma I.3, Lemma 1.8, and the law of total expectation, we obtain
E [[] + (2w + F. F. [1g 111
2yw
F
T
| 6-1
1 1
< E [(x') - || 27
L
|
xo $1
2
27

---

Published as a conference paper at ICLR 2023
+ (2w + 1) ||10* - -1919] +
2yww
|1
nill +
8yo (2w 1) 8:2 || - =x01
n
7
n
= [f(('') - 2 E ||
+ (2w + 1) F: ||os 1=]1"]] +
11lt - nell?
1=1
L
8y (2w + 1) [
E
||
- x²11 2²1121
27
2
Using assumption about 7, we can show that
(2w((2+11) 2 2 0 (see Lemma 1.7), thus
24
E [[(x(t]]] + (2w + 1) |19 - 1et 1p]
2
E
n
||
++1
h
11
n
72
x=1
S {E[[(()]] - E 2 ||] + (2w + 1) E ||ss - 1011²]
27w
E
n ||st
n1ll?
n
11 1=1
In the view of Lemma 1.5 with Tp' (2w 1)F [lo' w0]s] + conclude the proof.
1 2
l1gt EE
hn]l"]
can
Corollary 6.2. Suppose that assumptions from Theorem 6. hold, and oe Nº Vf((z') for all i [n], then DASHA needs T== T= (5(#9) 1*) (L+ 3n I.)
communication rounds
to get c-solution and the communication complexity is equal to O (d + (cT), where Se is the expected density from Definition 1.3.
Proof. The communication complexities can be easily derived using Theorem 6. , At each commu- nication round of Algorithm I, each node sends &c coordinates. In the view of g = V (x²") for all E [n], we additionally have to send d coordinates from the nodes the server, thus the total communication complexity would be O (d + (eT).
Corollary 6.3. Suppose that assumptions of Corollary 6.2 hold. We take the unhiased compressor
RandK with K = Ce S d/Vn, then the communication complexity equals O (a+
-(s("))-")
oVT
Proof. In the view of Theorem F.2, we have +1 = d/K. Combining this and an inequality L < L. the communication complexity equals
O Od CeT) = 0
d+
-(xx)-())
KL + w
vn
d
a (ntii)
=
d+
(f(z9) - fr)
Vn'
(f(=9) - )r) ( 1)
0
d+
I.2 CASE OF DASHA UNDER PE-CONDITION
Theorem 1.9, Suppose that Assumption 5.1, 5.2, 5.3, 1.2 and G.1 hold. Let take 1/ (2w + 1), <
min (1+
[++
40w (0w(2w+1117 1
2p and l Vf((z") for all i E [n]] in Algorithm 1
28

---

Published as a conference paper at ICLR 2023
(DASHA), then
E (1 yu)" (1160) (³) + 2, + 1)11 /](2)]]+
8yw
n >
vS((o)1r))
+ n
Proof. Considering Lemma I.4, Lemma 188, and the law of total expectation, we obtain
E [f(x + +2y(2 + +)E |100 1111
+
8yw
E
g s+1
11
s f(x²) -?
2 [f(xt)]| ( 27 2 || - x²11
4)
+ - (1) (2w + 1)E |||* - 11' 12]12]]
+ (1 - 71)
8m
E
h
11
71
i=1
22 + 1) i | - 121
+
n
= =E [f(((²)] - = ||| Vf [1= ||²]
+ (1 - ym) (2w + 1)E |||l - n1 1²1]]] + +1 - (1-)m) 8y E
1
|
1 L
2 12) | 2²112.
20w +
27
2
Using the assumption about 7, we can show that
(2w++)1111) 7.2 z 0 (see Lemma 1.7), thus
27
2
E [[(x--1)] + 27w + 1) ||g - 1111
+
8ry
E
9 +1
||?
< E [f(xt)] - f ||| || (|2
+ (1 - 7/4 (2w + 1}E |||e* 10]13]] + (1 -114
8yw E
1
|1 n&l1
In the view of Lemma 1.6 with d 2(2w + I)E [|0* - 1=(1]]] can conclude the proof.
m8 E
E
x
!691 - hell"]
We use (-), when we provide a bound up to logarithmic factors. Corollary I.10. Suppose that assumptions from Theorem 1.9 hold, and g, = ffror all i E [n], then DASHA needs
L -+
W PVR
w
(25)
communication rounds to get an E-solution and the communication complexity is equal to O (CcT), where Sc is the expected density from Definition! 1.3.
Proof. Clearly, using Theorem 1.9, one can show that Algorithm 1 returns an e-solution after (25) communication rounds. At each communication round of Algorithm 1, each node sends &e coordinates, thus the total communication complexity would be O (CcT') per node. Unlike Corollary 6.2, in this corollary, we can initialize of. for instance, with zeros because the corresponding initialization emror T from the proof of Theorem 1.9 would be under the logarithm.
29

---

Published as a conference paper at ICLR 2023
1.3 CASE OF DASHA-PAGE
Lemma L.1. Suppose that Assumptions 5.3 and 5.4 hold. For h from Algorithm / (DASHA-PAGE) we have
1.
En | | [ -[att-// S
(1 p) Liaxx
| - x=11 + (1 -p)
p) 11' - v
nB
2.
En || - \(((t++))) x
(1 p)
max
| -2'11 + (1 ->) - We
B
3.
En
- [|15t2-n611] < ((1 1) mmxx
((1-)) ((1-D)Liax
+ 2217 || - 2²'1 + 2p |IM V)(('')] e [n].
B
Proof.
Using the definition of h*+1, we obtain
En ||A vf(x+t1) ||
=(1- -1-18 p) En
11" +
- - v((att))
B
i=1
jel!
15) (1- - p) En
1
(Viglott)) - -V/y(('))))) (V -V/e))) vf('))
jEM
+ +1- - (
From the unbiasedness and independence of mini-batch samples, we get
|| - ((
Eg
(1 - p)
Ex
Σ
n2 B
i=1
jEEf
+ (1 - p) ||1e
(1 (1-p) p)
Σ Σ
- (Vi((ztt)) vf((z*)) /13
n2 B
1=1
+1 p) |1''
(1 p1 n
m
[ifyll''!) -
n²B
m
+ (1 - p) ||1 - 2
(1 p) 12 1
||ا x01 +11 (1- p) || vS(x)))
nB
In the last inequality, we use Assumption 5.4. Using the same reasoning, we have
Es || [ \((
30

---

Published as a conference paper at ICLR 2023
=1 -1-p) En
+
Σ (Vl((())))))))
V)((ttt))
JEN,
=(1 p) F.z.
1
- -
B
jEl!
+ (1 - p) ||n! (x'('') |
(1 p) Liax
||='|~ - 2"1| + (1 - p)
-
B
Finally, we consider the last ineqaulity of the lemma:
En || -1
= - - (11
B
JEN
p Pl( 1/l12
+ - EA)Ea
Σ V (ifi(zz*)) - -Vf((z))) - (Vi((t*t))) -.
B jEN
+ +11 -
- -
Using the unbiasedness and independence of the gradients, we obtain
Ex
| ]
//(
(1 (1-2) p)
Σ [I [[(Vis(a - V(G(+9) - ( 1
En
B2
DEE
+ (1 - p))
> / - -mll?
(1-p)
m Σ
[[ Vfv(=9) (Vi((ttt)) - V)(aa)))?? -VS(()))))))()
B
(1 p)
=Mll
(1-p) p)
(it( -
B
m
(1 p) -
From Assumptions 5.3 and 5.4, conclude that
| - h[(13]]
En
< p [.((+++)) ntl1 + (1 --p) (
Lunxx
+ 13? ||/0 - 1=1
B
31

---

Published as a conference paper at ICLR 2023
- - -ill + +11-p) ( [maxxx
+ L3 || - x01?
B
04) 3 2p 3pl\v(((=*t)) - Vf((2z) )| + 2p || - v + -p) ([1p)))(+([-ppp
[Lmxx
+ Li) ||aet] - x²1
B
+ IZ) (Lina
s 2pL | - x212 + 2p ||n v/((=')]1 + (1 -p)
|| 10-1-1111
B
(1 - p)Lmaxx
+ +2L3
|| 21I1² + 2p 1lk - vfi(z')]2
B
Theorem 6.4. Suppose that Assumptions 5.1, 5.2, 5.3, 5.4, and 1.2 hold. Let us take a = 1/ (2w + 1),
probability p E (0, 11. and
48w (2w + 1)
(1 (1-p) [ max + p2 r²²+
+ 21 - p) Laax
S 1
n
B
pnB
in Algorithm 1 (DASHA-PAGEE then
E
||(
S T 2 ( (8)
48w (2w + +1
(1 p)
+ -Σ2)
+ 2 p) Lanax
x
L V
n
B
pnB
+ 2 (2w + 1) 1) 11
+
Aw
11 >
n
|| -1.11
n
2 + _ 1100- マイ( 32w (2w + 1) p
|1gp
n
Proof. Let us fix constants p,p E [0, oo) that we will define later. Lemma 1.11, and the law of total expectation, we obtain
Considering Lemma I.3,
E [(((tt)] +7 (2w + 1) F.
72w
11g
h 11
27
27w
E.
1 72
9
++
n
|
n
72
n
+ vE |1442- v f(+++)))11
pE
h
(2
n
< E ((xt) - -//2 |V](=t)]?
1
L
|| ++ - 11 + 7 11 - v)(a"))??
27
2
+ 72w + 1) |||s - -1]
27w
11ot nill?
+
E
n
8yw (2w + +1) E [(14 p) Lanx
+ 2I²²
|| - 201/2 + -2p- Σ 11g VA(
+
B
n
(1 p) L2
+ 5/E
- =011 + (1 (1-p) p) ->> 11lh--vr'
BBB
(1 p) Linax
- x((l + (1 - p) 1 Σ || v
+ +pE
B
32

---

Published as a conference paper at ICLR 2023
After rearranging the terms, we get
E [f( +7 (2w + 1) E
+ 2?w
E
11 +1 - n15111
1
+ + ||1A ff(x +1 [1a]
+ pp
||
I <E[[(r']] - 2 F [|V
+ (20 + E)
||lo* - 1011]]
27w
E
1
|19/ hill?
n
n
i=1
L
8yo (2w + 1)
(1-p))imxx
13
2Ī.2
(1 p) L miax
(1 p) L2 max
E
||
|
x² 2
27
2
7
nB
B
+ (7 + v(1 - p)) E |11e- - -V((2')11
+ 167pp (2w + 1) + p(1 -p) p) E
p(1
1
Σ
12
|
- VACOO)11
n
i=1
Next, let us fix v
7 p.
to get
E [[ + (2w + 1) E ||g/ - 1/ 11]
+
27w
E
1
11,
11,
11
n
+ IE [||l )|( ||²]
1
pb
p
12
< E [[((')]] -/ ||
+ +7(2w + E) ||0o* - 101
27w
1 n n Σ
+
E
n
E [|Is ||(
+
p
L
8ym (2w + +1)
(1-p)
max 13
+2..2
7 (1 p) Dinxx
(1 p) max
E
||a - -2011²]
27
2
71
pnB
B
16 (2w + 1) + p(1 p) )
1 n
| - -V
+
E
n
n
1=1
By taking p 16+w(2++1)
we obtain
12
E [(((+t1]] + (2w + +1) E [10 10-++1n+ttg 110+41-+444777 11 +
27w
E
12 Σ
1 n
1 1
n1 |1=1
n
+ IF [| p
V5 [1 [[a
16 (2w + 1)
E
T1
||
V.
n
< [B[[(x']] - 1e ||
+ (2w + 1) ||0s sgler
+ n
27w E
1
|1 - hgll?
n2 i=1
+ EE | v + 16tw (2w + 1).
Σ
||n
vA(
p
n
n
33

---

Published as a conference paper at ICLR 2023
(1-m)/ime / + +20²
L
&yw (2w + 1)
B
27
2
7 (1 p)
L
16yw (2w + 1) (1 p) Lanaxx
E -
- =011?]
pnB
nB
S B [B(((=)]]
2 1z ||V(
+ (2w + 1) |10s n9]1"]
2 n
E
1
|
hlll
71
i=1
E
|
ff()1)11 + 16 (2w + 1)
E
1
||
((((a)))
p
n
n2
L 2
24m (2w + 1) (1- max
+
I
7 (1
p) L
E
|| 20112]
27
pnB
Next, considering the choice of y and Lemma 1.7, get
E [[(x'=1]] + (2w 1) E |110t1 - 1/' 11] +
2yw
E
1
1
++1
- hot
n
i=1
+ E [11-t1 \ [|2] p
167 (2w + 1)
E
|ntt
i=1
< E [[(x))] - 2 ||>
+2w 1) [100 |19''1111"
2yw
E
1 n
Σ
o1
nil
2F [I' - 16 (2w + 1) F.
1
||nt
n
Finally, in the view of Lemma 1.5 with
w² = (2w =(2 + 1) E [|g* - -1*1=1
+
2w E
Σ
n
19
i=1
+ [1ll'-vf(*')))) 16w (2w + 1)
n2
n E
hht - vf(('')11
can conclude the proof.
Corollary 6.5. Let the assumptions from Theorem 6.4 hold, p B/(m+ and g: = h2 Vf((2")
for all E [n). Then DASHA-PAGE needs
T:=0
- e
(166)) (1+ -I+
Lmax / B
Vn
Vn
V
nB
communication rounds to get an e-solution, the communication complexity is equal to O (d + CcT), and the expected of gradient calculations per node equals O (m + BT), where So 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 2B.
2mB m+B
34

---

Published as a conference paper at ICLR 2023
Corollary 6.6. Suppose that assumptions of Corollary 6.5 hold, B S Vmfn, and we the unbiased compressor RandK with K = SC = e ( (md)ym). Then the communication complexity of Algorithm is
o (a+ Lmax (f(x")
&V7L
and the expected of gradient calculations per node equals
O m + Lmax (f(29) - f() vm
(8)
8VT
Proof. In the view of Theorem F.2, we have + K. Combining this, inequalities L L > < Lmax, and K = θ
Bd mm
= 0
we can show that the communication complexity equals
((d+co7)
o
d
1
- (f(=9)11))
KT. K vn
T. K
Lmax
8
n/
nB
BB
Irmaz) ))
1
(1(#9) - -)) ( (+/rtt
d T. +
o
d
vn
vn
((()))1)) (1) |)
d
E
And the expected number of gradient calculations per node equals
O (m BT)
O
m
(5(=9) - BL. + T.
B
+
m
L Lmax
8
vn
/n
nB
BB
1
(f(=9) (1
o
m
L
+
Lmax
1)
(f(z0) - (1)
o
m +
m
Luax)
I.4 CASE OF DASHA-PAGE UNDER PL-CONDITION
Theorem
I.12. Suppose that Assumption 5.1, 5.2, 5.3, 1.2, 5.4, and G.I hold.
Let and
us take
= 1/ (2w +1), probability E (0, 1], batch size B E [m],
{ L+ 200
7 S min
(1-p) L2
+ + 4(1 22 LR pnd
4.
p. in Algorithm
B
2a
2μ
(DASHA-PAGE), then
E [f(+*)-
(1 - -
(f(x²) - + + 1/9 - -1011²
8yw
| h 12
1=1
35

---

Published as a conference paper at ICLR 2023
27 |1 vf(a")] + 80yw (2w + +1) p
+
Σ
|
n
Proof. Let us fix constants v, P E 0o) that we will define later. Lemma 1.11, and the law of total expectation, we obtain
Considering Lemma I.4,
E [f(x + +2 + 1)E [110 -
-1----h41111 10111(]] +
8Yw
E
1
99
c+1
-
n 1|
+ +E - [1]]
+ pE
1
|
V
i=1
S E ((0t) "|([((=))|=
L
||
x
1| + |1 {f(
27
2
+ (1 - (ww) 27 + 1} |||'* - h²' 101 + (1 - 7w)
8yw
1 Σ
11 - noll?
E
71
n2
i=1
22 + +1
[(1- L) max + +2(2)
- 2011 ||00 + 2p
Σ
||n] V((
n1
B
(1 p) Lmax
|2tt 2-1? + (1 -1> ->>|n''~V/ [
nBB
+ +pF
(1 p) Lixxx
|2tt] 121 + (1 p) 1 n
Σ
1 - VA(OOTI
B
After rearranging the terms, we get
E [[ + 22 + 1)E [1g - -1(22|
8ym
E
1
|1
h 1|
n
n
+vE | (
(00-1--5((())) ||] + +PE
n Σ
1
|
| (1
<E[[([])] - 1B ||V
(/41 (w + E)E [|00 (10'= 10[[]]] + (1 11--11 714)
87w
1
+
n
1
1 L.
207m0(2w + 1) (11p)) max
+ +2ī²)
(1
p) 1 12
(1 p)
T.2
maax
E [|aott
- x² x²1]"]
1/
27
2
n
B
nB
B
+ (7 + v(1 - p)) F. [[[n'-[((a'))]
+ mmmm (2w + 1) + p(1 -pppp) p)
E
1
12
M -
V
n
n
By taking v= = 27 and p= 82w 1)
one can see that 7+ S (1 - ?) v and 40p7m(2w+1)
p
p(1- p) S (1 ()) p. thus
E [[ + 22 + 1)E |10 - 101111]]
-1
8yw E
l - -nt2 1
n
1=1
1
+ +E - + +pE
|
4+
n
i=1
36

---

Published as a conference paper at ICLR 2023
- E [f('0] - 2 [| \
+1--14) + E)E ||05 -11l + +(1
87ws
1
Σ
o - nEll?
n
n2 1=1
+11 2) p
2) 27
||' v)(
+ (1
p
80mw (2w + 1)
Σ | v)(
2
E.
1 L (2w + 1) (1--)) I
B + 2T.2
2y 2
2 (1 p)
L
80y (2w + +1 - p) I I.
E (1o=t1==")
pn.
nB
I E [ 2 [|]
8y (1-74) (2w 1)E ||0* -w1l]] + +(1 (1-
E
1
nill?
n
n2
+ (1 (1-2) () 21 E [ + ) 80 (2w +
p)
1
|
p
11
71
1 L 120 1)
(1 (1-p)L max
21.2
27 (1
p) Limaxx
[1xttt-2011?
27 2
n
B
pnB
Next, considering the choice of y and Lemma 1.7, we get
E [[(x + 22w + 1)E [19
1 12 2
8row
E
11
++ 1,t2112
n
+vF | - v
+ pF
SE [f[('=)] - E ||]
+ (1 - (o1c (2w 1)F |||0* - 11|1]]] + (1 7/1)
8yw F.
n Σ
11ot
hill?
+ (1 (1- 21 E | ((()))
s0 (2w + 1)
VAGOS112
+1177/1
E
||
11
In the view of Lemma 1.6 with
2(2w + 1}E ||o0* - 19]p3]]
8w E
1 n
|1
nill?
2 || V [ 80w (2w + 1) p
E
1
Σ
|
n
n
we can conclude the proof of the theorem.
Corollary I.13. Suppose that assumptions from Theorem I. 1.12 hold, probability p = B/(m + B),
and hi g = 0 for all i E [n], then DASHA-PAGE needs
L
m VnB
Lmax
Ō w
(26)
B
/Vn
Vn
pvB B
communication rounds get an E-solution, the communication complexity is equal to O (SeT), , and the expected number of gradient calculations per node equals (BT), where &e is the expected density from Definition l.3.
37

---

Published as a conference paper at ICLR 2023
Proof. Clearly, using Theorem 1.12, show that Algorithm returns E-solution after (26) communication rounds. At each communication round of Algorithm 1, each node sends Ço coordinates, thus the total communication complexity would be O (ScT). Moreover, the expected number of gradients calculations at each communication round equals pm + pm+ (1 p) m - 2B,
2mB
thus the total expected number of gradients that each node calculates is O (BT) Unlike Corollary 6.5, in this corollary, we can initialize ny and gf for instance, with zeros because the corresponding initialization error y from the proof of Theorem 1.12 would be under the logarithm.
1.5 CASE OF DASHA-MVR
We introduce new notations: Vf(e"t);
B EA Vf(('t): ' and vflatti,gtt)
Lemma L14. Suppose that Assumptions 5.3, 5.5 and 5.6 hold. For h from Algorithm (DASHA-
MVR) we have
1.
2620² nB
2 - 21 6)2 L2
En Miftt-Vf(z+H))
+
|| -2'1 + (1 ==112++ b)a 11 - Vf(a")]12
+11-)))
nB
2.
26o02
2 2 - b)2 L2
En || (/((o++\)11
| - x211 + (1 b)² || \ vi [n].
B
B
3.
ob
(1 - b)² La + L3
En [1 h3ll"] - 2
| 2011² + 26 | -Vf(((((=')'''' Vi [n].
Proof. First, let us proof the bound for En
En || ((( |1|]]
=En || g( + (1 - (1 -
(s) 10n Ein 4111 (V ( - +
- (v -d- -/((='))
+ -V/c)) ||]
+ +(- 6)² h1- 2
04
V +1 ((t)) -
2 b)² En V (1 ( - V/(2a) \/(l//(t)) [|]
+ (1 - b)2 hh' - ||
26
Σ En || : - \1(
21 0)² n
- -V/aatt)-V/(a') [7]
n²
+(1 (1 -1-18 b)2 |n vf(+t)1
26 n B
[| - -
En
B²
#=1
2 - 6)2
- -V/()tt)-V((("))
n2 B
38

---

Published as a conference paper at ICLR 2023
+ (1 (1-b) b)² |n' 1 V>/''>'''''''
Using Assumptions 5.5 and 5.6, obtain
o2
nB + 2(1 - -1) 1
EA [|| Vf(x+t) ||]]
(1 - -b)² |M-- -V)(2=)1
nB
Similarly, we can get the bound for En, || f(((tt1))18
EA | [ [
Ex V + + (1 -VL
(/(att)) -
E ||b [V
( -V + - vA((a(:)))))) [?]
(1 (1= - ((
2
26202
B + b)
L3
| - (1- -M-=>)>))
B
Now, we proof the last inequality of the lemma:
En
-En (I (4 -( -
15) E. +1 - 1)
|[ V/(('' 66 V\(=')]
F. |10 (V (x't1 (x'"1 V)( + (1 (1 -1 (-T/(=")--~=()))))) VA(G))))
+ +1IV5/(2 Vf((2') 6 (N) [(()')]
x/ Eb V ( V/( ||]]
04)
+ 2 b)² En V (
-
2 +2 V//
Vii(2') )1² 21 | v/((11)1
2b B
Σ En
V +1 ( (1(
B j=1
2 - b)2
Ey V ( V -
B2
2 [
-
26 |I {((')))1
In the view of Assumptions 5.5, and 5.6, we obtain
2620²
21 [1]-b) b)2 1
EA [1 Ml1 <
|| | - 2²11 + +T.2 a12 x0112= + 2b² 114 v/((2'))
B +
B
Theorem 6.7. Suppose that Assumptions 5.1, 5.2, 5.3, 5.5, 5.6 and 1.2 hold. Let us take 1.2)
2W4T. b E (0, 1), and 7 S T.+ (DASHA-MVR). Then
(1 11 92w(2w+1)
4(1- 4(1-8)²13
Algorithm
bnB
E
[17]
< T
2(f(2))
-
39

---

Published as a conference paper at ICLR 2023
96w (2w + +1)
(1 b) L2
4(1 - 6) 12
x
++
+ 12 +
n
B
bn
+ 2 (2w + +1) 1l - -no +
4w
1
Σ
9
1
i=1
2 + b |100 -/((")11 + 326w (2w + 1)
1 Σ 1
96w (2w + 1)
+
+ bnB 0²02.
nB
Proof. Let us fix constants v, E [0, 0o) that we will define later. Lemma 1.14, and the law of total expectation, we obtain
Considering Lemma L.3,
E [f + y (2w + E)
||
111
+
27ww
1
+1
n1
113
n
72
+ +vE ((ao-)
+ +pE
| 41
n 1=1
< E f(xt)) - 2/1 (|
| - =²1 + y 111t V {((x))1²
22
2
+ (2w + 1) E)E |Ilo*~ - 101
27w
1 Σ
|1o - -nal??
+
E
n
n2
i=1
8yw (2w + 1)
22b202
(1
b)²
L2
+ 1.2 || - -x²11² + 212 Σ || V)(
+2 2
n
B
B
26202
2 (1 - b)2 L2
+ +vE
|0 x²1 111
+ (1 - -b)² |11- - -vs(tt)]
BB
nB
26202 2
2(1 - b)2 L2
- 20112 + (1 - b)² 1
Σ | - V)((a'))11
+ pF
B
B
n 1=1
After rearranging the terms, we get
E. [[( + (2w + 1) F.
|10
- 11 + 27w
E.
|10 - 1n=
i=1
+ +E [115-1 - v [[(a(t)) |13
+ pE
|
++
SE [E[((E)) -3 ||| |
+7 (2w + E |100* - 1011]]
+ 2yw
1
l nill?
E
n
71
16 (2w + 1) ( [1-b)222
12
+ 722)
L
B
2 (1
b)2 12
2p (1 1)² 12
E [|aatt -
27 2
n.
B
+ (7 + v(1 b))) F. |1' - -VS(a')1
1662 ywu (2w + 1) + p(1 - b)²)
M vi(
+
40

---

Published as a conference paper at ICLR 2023
+ 8yw (2w + 1)
P b²0².
+
nB
nB
B
By taking v= = :. one can see that y + u(1 - b)2 S v, and
E {[ +
(2w + 1) ||0 - 12 113]] +
m7
n
119
11
n
72
F || V5 [1]] + pE
1
|nf
)1(
b
n2
S E [](o]]] - 3 ||
(2w + 1) E [100 - n5' x013]
+
27w
E
Σ
lo - 1/l??
n
n2
E
[|
+
b
16 (2w + 1) ( (1
+ 1:2)
L
2y (1 b)² L3
2p (1 b)² L2
E || - 2²11"]
27
2
n
bnB
1602 yow (2w + 1)
+ p(1 b)) F.
I
n
n
+ 2
8ryw (2w 1)
7
+ P
b²02.
nB
bnB
B
Next, we fix = (20+)))
With this choice of p and for all b E [0, 1], we can show that
1662 1)
+ p 10--b- 6)2 S p, thus
E [f + (2w + 1 [110 - 11]] +
27w
11 ++1 - 11 11
E
+ E |11 V ((a=+t>111 [1]]
16by (2w + 1) E
1
|n$t - vii(e't))1'
< {E[((()] 2 E || ||²]
(2w + 1) |10* - 101
2yw
1
nell?
E
n
n
1=1
E
[110-
vf('')]1 +
16byw (2w + 1)
E
|| vf((2))
b
n
i=1
L
16 (2w 1)
(1=b)²13 12
7.2
2y (1 b)² L3
32byw (2w + 1) b)² L2
E
| - =11
27
2
n
bnl3
nB
2
8yw (2w + +1)
7
166yw (2w + 1)
0202
nB
lBB
nB
< E [f(x))] 73 ||V
+2 + 1) E |la'- 10--1-1p 1011
27w
1
noll?
+
E
n
n i=1
E |11 [5(+))11] + 16by (2w + 1) E
v)(
+ 5
n
41

---

Published as a conference paper at ICLR 2023
(1-b)²12
L
48 (2w + 1)
B
27 (1 b)² 12-
F. || - -|11tt--=/11 201
27
2
bn
(48 (2w
+
1)
27
0²0²
+
nB
bnB/
In the last inequality we use b e (0. 1]. Next, considering the choice of y and Lemma 1.7, we get
E [[(x/(]]] + (2w + 1) E ||10 - 11]] +
27w
E
9 r+1
11, ||
1=1
+ E |11441 v f (
16byw (2w + 1)
E
1
11
(f((
S <E[[(x")] - -o ||
Y2w + E |1g* 1111
2 n
E
1
|1
h&l1?
n2
E
vf(xt))
16hr (2w + 1)
E
Σ
n
||n
b
n
48yy (2w + 1)
2y
6²02.
uB
bBB)
In the view of Lemma 1.5 with
V
(2w 1)E
[11s - -1011]]
2w E
n
196
11
71
1 [1l' vf(("))
16tw (2w + 1)
|lnt vi((o\))
+
and C (2w-+)
+ bn o² conclude the proof.
nB
Corollary 6.8. Suppose that assumptions from Theorem 6.7 hold, momentun b
(min w V BeB neB] }) and gf = h. 1 Emm fi(x= ( for all i E [m]] and batch
Bin
size Binit = (B/b) then Algorithm 1 (DASHA-MVR) needs
T=
1 ( 5r)
L+
-++
w
-+
w
+
La
+
Vn
EN²B
VB
nsB
communication rounds get E-solution, the communication complexity is equal to O (d + CcT), and the number of stochastic gradient calculations per node equals O Binit BT), where So is the expected density from Definition 1.3.
Proof. In the view of Theorem 6.7, we have
E [ ||]]
/a-b3 / Lo bn BB
1 T L+
(f(29)-
-f*)
(1
b)²
L2
Î +
+
vnl
B
42

---

Published as a conference paper at ICLR 2023
+ -
1 b
Vf(z0))2
bw?
-11 m1
Σ
h
V
n
12
+ 2
o²
b²
Note, that } max
WV
neB neB
o² o²
1) s (max fw² nēB
n }) thus
[[| |||]]
E
= = _ (f(x9) fr) (L+
w
[+ La
L
+
vB
E VB
+ 11/1000 -
bw2
1 Σ
n
72 i=1
Thus we can take
7= 0
1
(5(09) (r)
1.
w
i.
Lo
+
0²
La /B
Vπ
/B
E
+ 5 1110 V)(21)|1
1
l
n
V((AO)1))
n
n
Note, that 11 = 000
1 Σ
Vf(x0"; 50)) for all i E [n]] Let us bound |1100 [)+ k=
Bar
Bis
E -|\n0~V/(+>11]
E
Vi(x
v5(ao)
T1
Bini
1=1
1
Bus
E
n B2
Init
2
n n.Buii
Likewise, 1 Ex= E
|118 v)((~))1
< 0² Bun"
All in all, we have
(1 L
(I+ La
0² La
T=0
(f(=0)-ft)
Vn
vB
En2
VB
d²
2ooo?
+ bn bn
+
BBiini
43

---

Published as a conference paper at ICLR 2023
(L+
0
(1(29)
(
w
i
Lo
+
0² Lo B /B)
Vn
vB
d²
62
nB
nB
EL2 E
(f(29) ff) f4) (++ w
v
[
Lo vB
Lo en B VB)
0²
= =
+
+
NEB
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 Bint 2BT O + BT).
Corollary 6.9. Suppose that assumptions of Corollary 6.8 hold, batch size B S Vcn we take RandK
with K = <c = 0 Rd.yEn
and T. == max [,, Log, T.J. Then the communication complexity equals
o
(
do (f((2)- - ffff)) f²)d]
VnE +
(9)
VnE
and the expected # of stochastic gradient calculations per node equals
02 +
(f(x2)-
O
(10)
mE
8/2
Proof. In the view of Theorem F.2, we have w+1 d/K. Moreover, K = A Bdd/n thus the communication complexity equals
= 0
d
vT
O (d CcT o
1 d+ 3 (f(29)
KL [KL+
(I+ Lo
KK
σ² L
K
O²
Vn
/B
En
vB)
BEB
0
d
1
(f(#9) (f(#9) - fr)
(
d
i
Lg
+ d
Lo
+
do
8
vn
vn
/B
vn
Vne
+ (1(x9) ( (
dg
d
+
VnE
do
1 (s(09-) -(² (
Vne +
And the expected number of stochastic gradient calculations per node equals
O (Binit + BT)
1
=0
B 0²
+ Bwy
a² nEB
1 + (f(x²) (f(=0)-f)
BL+
BL
W
[
La
+ B
o² Lo
Bne
Vn
/B
En2 B vB)
44

---

Published as a conference paper at ICLR 2023
1)
0
a²
(f(x))
(VEnLt
L+
[ La
o L.o
NEE
NE
V
B
VEN
BB
VeN
(3 (1art))))
0²
1
0
+
((a")-f9)
TEE
g
1.6
CASE OF DASHA-MVR UNDER PE-CONDITION
Theorem
I.1..
that Let us take
Suppose
Assumption
5.1, 5.2,
5.3, 1.2, 5.5, 5.6 and
G.I
hold.
1/(2w + 1),
(0. 1] and
400 1) (1-b)2 +E2) 1
min
L+
8(1- 8(1-6)2L2
b
in Algorithm 1 (DASHA-
hn
2/ 2p
MVR), then
E [f(("))
8rw S (1 (1-74)² "1²² (f(6") (((x)))f*) + +27 + 1) 11 -1011- +
Σ 1 11
n
i=1
+
27 b
|1100 \|(2"))2
80by (2w 1)
= Σ
1
- V((OP)11
11
n
n
1
200w (2w + 1)
+
8202.
11 nB
bnB
Proof. Let us fix constants p, [0, that will define later. Considering Lemma I.4, Lemma 1.14, and the law of total expectation, we obtain
E [ + 22w + 1]E |11 - 1 113)
10+111]]
8y
E
10
h
1|
FE | 7 [ + pL
1
1 ++1
Vi (z
n i=1
E ((x') 3 ||
I,
||00 | - 101 + > || v
(27
(1 - -744) 22w
1)E
[[l''
11l"~~1'1' -1113]]
+ +11 (1- - (1)
87w
E
1 Σ
o1 - mnll??
n
n
22 (2w + 1)
26202
(1 - b)² L 7.2 ||0 - -011 + 21² 1 n
F
2
Σ
|| Vル(
B
26202
(1 - 6)2 L2
+EB
1 141 xd 112 (1 1 6)2² |11 -
nB
nB
+pE
212
2 - b)2 L
|
201 (1
1 n b)²
n Σ
| VA(G59112
B
45

---

Published as a conference paper at ICLR 2023
After rearranging the terms, we get
E [f( + 2 + 1)E ||1 - -h^ +11] +
8y
E
1 Σ
19."
- n 12
i=1
+ +E |110-1 - 4 )| 119
+ pا
1
|n
V.
(z )
< <R [)(])= - 1. ||>
+ (1 7/1) (2w + 1) |11s* -b'l(] + (1 711)
811
E
1
Σ
11 - -121?
n1
71 i=1
40yw (2w + 1) (1-b))212 7.2
L 2
2v (1 b)2 L3
2p (1
b)2 L3
E
||la - 2081
27
n
n.B
B
+ (7 + v(1 - 2) E |1'' - -V]()))1
4062yw ywu (2w + +1
+
+ p(11- -6)2
Σ |nt - (((
2 20y (2w + 1)
v
+ p
0²02.
nB
nB
B
By taking V/ 2/, one can see that + v(1 - b)2 s (1
b) 2)
v. and
E [f((
+ 2 + 1)E ||10* - h 1111 ||
8y
E
1
- h.4 12
n
i=1
27 E || -|n5+1- [5x [10] + +pE b
|
(e( 2
< E [[(()))]] - 33 ||
+ 7x4) 22 1) [|I* -100 + (1 7p4)
87w
1 n
ll -n2l
n2ll?
n
n
b)
2% b
|| - [
E.
2
40yw (2w + 1) (
(1-b)=
+ 9.2)
L
B
4y (1
6)² 12
2p (1 - -b)² L2
E |||a - -2'11
27y
2
bn
B
4062gw (2w + 1)
+
+ p(1 - b))
M
{((
+ 2
20yw (2w + 1)
+
27
+
p
6²02.
nB
bnB
B
Next, we fix p = 8067
With this choice of p and for all & E (0, 1], we can show that
406 (2w++ 1) p - 6)2 < (1 - 1)) p, thus
n
E [f( + +2 + 1)E 110 - 10
8yw
1o - -nt42 2
E
n
71
i=1
2% E 1 v5 + 8067w (2w + 1) +
E
|| Vii(o(ti)12
b
n
46

---

8yw Published as a conference paper at ICLR 2023
E [f(''] - - [| [
2
(1--4)) (1-24) + E)E ||o- -h + (1 - 711)
87us
1
Σ
lIst - n&ll?
n
n2
1=1
*11
b)
b)
2% F. b
+ (1 (1-2) /
80bmw (2w + 1) F)
+
-V
Σ
1
2
2
n
1=1
40yw (2w + 1) ( [1-0)-22 + 2
L
27
2
n
4y (1
6)2 123
160byw (2w + 1) -1 1
| -
E
bnB
nB
20 (2w + 1)
2
80by (2w +1)
2
6²00
nB
bnB
nB
[f(x')] -2 [[
E
+11 - 714) (01- 27w 1)E ||0s - -m] + (1 -m1)
8yw n
1
l1st - nill?
E
n2
1
2)
b)
2% E
|1 v
+ 1
b)
80byyw (2w + 1)
E
Σ 1 v vi((a))1
n
b
2
11
L
2007w (2w + 1)
(1-b)212 B
+ [22)
47 (1 - 6)² L2
E ||aat| - ==']1]]
27
2
bn
2000y (2w
+ 1)
47
+
+
1²o²
nB
bnB
In the last incquality we use b E (0, 1]. Next, considering the choice of y and Lemma 1.7, we get
E [((*))))] + +2y(2w+ + 1)E [10011-1+11 11 +
-
++1
n1 12
n
n
27 + b
||6-11 -
80byw (2w + 1)
|
n
< <E [[[(x')] - E |V](a'))1*]
2
+ - +11-714 (2w - 1)E [1|s' - -1'1 + (1 - 744)
8yw E
- Σ
|19 nill? 3
i=1
+ (1 - 744
2 E
|||s- - vf(x')]1
+ (1 74) 8007w (2w + 1)
E
1
Σ
| - v.(6E)112
b
1=1
200 (2w + 1)
47
+
nB +
8202
bnB
In the view of Lemma 16 with
V = 2(2w + 1)E |||o* - n=]13]
+ 8w Fs
lof 16912
1=1
+ BB |11- - - + 800o (2w + 1) E
1
|| - v((
11
47

---

Published as a conference paper at ICLR 2023
and C
(200m(2w++)) 2w n
+ bn 6² we can conclude the proof.
Corollary
I.16.
Suppose that assumptions from Theorem 1.15 hold, momentum
O
min
unnB ad
and li =g.- for all i E [rd], then Algorithm I needs
0²
+ - wī
w BVBue
Lo
T T Ô
w + W
+
(Vn
(27)
p/n
HVB
communication rounds get E-solution, the communication complexity is equal O (CeT), and the number of stochastic gradient calculations per node equals O(BT), where Sc is the expected density from Definition 1.3.
b² Therefore, is enough to take the number of communication rounds equals (27) to get an E-solution. In the view of Algorithm and the fact that complexity is equal to O (C and the number of stochastic gradients that each node calculates equals (BB)). Unlike Corollary 6.8, in this corollary, can initialize hę and gf. for instance, with zeros because the corresponding initialization error o from the proof of Theorem I.15 would be under the logarithm.
Proof. Considering the choice of b, have 200ww(2w+1) bn
nB
mini-batch of stochastic gradients, the communication
1.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++1, In this section, we define Ep [:] to be conditional expectation w.r.t. c conditioned all previous randomness. And define Ex+1 [-] to be conditional expectation w.r.t. cf+1, {C ( (h[+1) Ji=1 conditioned on all previous randomness. Note, that E [1
EA [Ec [Ep [II].
Lemma 1.1. Suppose that Assumptions 5.3, 5.5 and 1.2 hold and let us consider sequences {o,
Iin Ji=1 and {M+ J 1 Algorithu 2, then
Es41 (ight-h"+h
L (1 - p))
+ 1.2 B
|z 22112= + 2a²w(1 p)
n² Σ l1st hill + (1 p) (1 (1-11100) (l1-a)211 1lg 121l2
n1
and
Ex+1 [118 -h₂ 112
12 + 13 B
< 2w 1-p))
1 1112 (1 p)
(20iw + (1 -0)) lo -b1l?,
Wi [n].
Proof. First,
estimate E.+1 - B E Vli(x't1 ( h ΣE V
we
Let
denote
h++1
E+t1
|1 - -11112
= -E441
Ep [19 -
1
-1 - E441
C (M(t) [+1 M - (ot -h!)
h ++1
1.0
1=1
i=1
(4.(15)
(1 - En
Ee -e C. (n -h: a (g) h!))
(h h (g) - kt))
48

---

Published as a conference paper at ICLR 2023
+ (1- 119 wºll?.
Using the independence of compressors and (4), we get
Ex+1 [|| 1=]
n (1 p)
En Ec [|c, (R1,0) hnj -a agi - -n)) - (14,0' h/ a (gf - -h3)) -1))
n²
i=1
+ (1 p) (1 a)² 110¹ - h0ll
w(1 p)
n
Eq, |110021 h - a (o) - -ht)ll"] +(1 (1-p) (1-a)
llg - a))
-
n²
i=1
2111 - p)
|| n ["] +
2a²w(1 pp)
Σ 10 - m=]l + (1 p) (1 - -a)aaa/00 a)9 121?
En
n²
n²
1=1
==1
2w(11 - p)
B
1
B
En
Vf ,
V fi(''141) 1
n²
B
B
1=1
5=1
2n (1 p))
n
+
Σ
|1
n$ll? + (1 - p) (1 (1- (1-
11gt -h'1?
n²
i=1
(15)
2w 1 p)
n
En
1
Σ j=1
B
n
{)((ot>1?
w1 - p)
Σ
|1oا - m/ll + (1- o) - -
+
n²
Y=1
21 p)
B
(V/((ett)) -V [(G
F..
n
B²
j=1
+ [1
2a w1 p) n
Σ
|1of
hill? (1 - p) (1 1a)2211 1121?
112
f=1
21 p)
12
B
+ [2)
| - x 211 + 2a²w(1 - p)
Σ l1st - 11ll + (1-p) p) (1 1)8110* - 1691?
n
n²
1=1
where in the inequalities we use Assumptions 1.2, 5.5 and 5.3, and (14). Analogously, we can get the [11 - -44 [|] for all i E [n]]
bound for Ex+1
Es41
[1055 - h 1,211177
Exp [105" ++1 - h1 11]]
= -E++1
=(1 -x+)
|108 + C. (b1,t) - h1 a (gf - -1)) - n=,,
L2
< 2w(1 - p)
+ 13 || - 21 + wa - - -b!ll +
+11
- p) (1 (1=a)21 1|ot -h
B
49

---

Published as a conference paper at ICLR 2023
We introduce new notations: Vil( + 1BB EA ff((ttt);))) and V vf(xtt), (tt
Ei Vi((a'll; ;
Lemma L18. Suppose that Assumptions 5.5 and 5.6 hold and let consider sequence (hi 1++ yiz1 from Algorithm 2, then
Eet1
[|
po²
(1 (1-p)La
|x_ x²11² + (1 -p) 111t -Vf(')|1
nB'
nB
Proof.
Ex+1
|
R'
pEn
( -
B'
+ (1 b)
V f( (x + ) + h²' -
po²
+ p)
v
nB'
where we use Assumption 5.5. Next, using Assumption 5.6
5.6 and (15), we have
||6441 - f((
Es+1
2o
+ (1 -))
-
nB3
po²
+ (1 - Ep
V +1 1 - V) (1-p) -Vf(2']
nB'
po²
(1 p)
n
+
Fi
(1-)))) -
nB'
n
po²
(1- p)
Σ Σ
En (
-
nB'
n2 B
i=1 j=1
+ (1 p) || vf(**)] ||2
2
(1 - L3
|
1
+ (1 p) | | vf(z)]]²
nB'
nB
Theorem 1.19. Suppose that Assumptions 5.1, 5.2, 5.3, 5.5, 5.6 and 1.2 hold. Let us take a probability p E (0, 1), batch size B' 2 and
1
-1
12w (2w + 1)(1 p)
L2 B
2(1 L3
7 L+
+ 72
pnB
in Algorithm 2. Then
E
V5(2"))) M1?
S T
2 ((((2)) - -r)
(2w + 1)(1 - p)
L2
2(1 L3
x L
+ 1.2 +
B
pnB
+ 2 (2w + 11) - -10112 +
4w
1 h. 2
||
im1
50

---

Published as a conference paper at ICLR 2023
+ 2 p n100 vf(a9)1
20² nB
+
Proof. Let us fix constants k; 7), V E [0, 20) that we will define later. Using Lemma 1.1, we can get (20). Considering (20), Lemma 1.17, Lemma 1.18, and the law of total expectation, we obtain
E [ <E |1104] 111 11] n
1
99
wE |11-11 -
$ E
f(x0)= - 7 ||
(1)
1
2 |
+ 7 -1112++711
1 +> -
2
22
2w(1 p)
4 + +[²)
| - =/1 + 2a²w(1 p)
Σ 11 - 11ll + (1- - p) (1 =a)² 110 - 11'11
+kE
n²
L22
+ +/
21 p)
+ 1:2
||
10-1-x'' x01 + (1 - p) (2aiw + (1 - -a)²) Σ lost - 155
B
+ vE
po²
(1 - D)
| - 2² 1| + (1 - p) 1>) vf(=t)|13
11(t1-2''
nB
nB
After rearranging the terms, we get
n
[f( nF |10 1+] + n
9
++1
h
1.+111 11
7
+ +vE || v
$ E [f(x')] - - || ||{
L
2kw(1 - p)
[ + +22)
21pw(1 p)
[23 112
+ +D²)
v(1 - 11
E -x'1--
27
2
B
nB
+ (7 + x(1 p)(1 a)²) E -1'11?
2na w( p)
n Σ
+ 1)(1 p) (2 (2a2 + +(1-a)))
E
|.0 hCll
i=1
(++ p)) F. -|1s- [
upo²
nB'
Let take 3, Λ 2, Iw+1 and r) = 2rw
Thus (+1(x=+)((ppp0)0 S (x,7+v(1-p) =v,
n
2na 2 (1-p) + 1)(1 p) (2n²w + (1 a)2) < 11, and
E [[] + 722 + 1)E [1g - 1 -11
+
2
+1
n
n2 i=
+ IF ||14t1 < [|21
p
< <E [f[(x()]] - -3E ||
51

---

Published as a conference paper at ICLR 2023
L
(2 + 1)(1 - p)
12
B
+
+1²
4yw2
p)
B
+ Σ2)
1(1 -p)
F:
27
2
pn.
+
72w + 1)
||0* - 16119] +
2
E
1
| nill?
==1
+ E [11A [
P
?0²
nB
E
[f(x')]
2
|| | )1
L2 12
L
(2w 1)(1- p)
7(1 p
E
x - x² x0113]
27
2
n
pnB
+ 72 + 1)E [Il'-
10--11% n0]13]
+
27ww
E
1 n
71
+ E |115 111h--vfi {f('")]
702
"B"
In the view of the choice of 7, we obtain
E [f(x + 72w + 1)E 1104211042111
1=]
27w E
|| ++1
==1
+ E |1 - v |1 |1?]
p
< [f(x')]] - -2
||
+ +2(2w + 1)E |110* |115'~19111 13117] + 2mw E
11 - 10ll
+ F - [[(at)]
p
702
+ rB'
Finally, using Lemma 1.5 with
V'
(2w+ + 11E |||s*
10113]
2w +
l1
h&ll"
n
n
1 (V--v(((')) p
+
and C = o² nB we can conclude the proof.
Corollary 6.10. Suppose that assumptions from Theorem I.19 hold, probability
min {
Sc neB) d o
} batch size B' = [2 and h g. Bun Bun (x. for all E [n]]
initial batch size Bum |maxx { 0² B Sc }) tten DASHA-SYNC-MVR needs
ne
T = 0
1 8
(f(z9) ((a))-()
L+
Vn
w
i
vn
w
+
V
Son
+V
En² B
VB
L
+
nsB
52

---

Published as a conference paper at ICLR 2023
communication rounds get E-solution, the communication complexity is equal to O (d + (cT), and the number of stochastic gradient calculations per node equals O BT), where Se is the expected density from Definition 1.3.
Proof. Considering Theorem 1.19 and the choice of B", we have V
E
1 << T
12w + 1)(1
p)
L2 B
T,2
2(1 - 1} pnB
(f(xx) - f²)
L+
n
2
20²
1100 {|(2")12 p
+
+
nB'
1 T
12w + 1)(1 - p)
L2
B + T,2
2(1 - p3
<
2 2f(x0) - -()
L+
+
pnd
110 |[(29))
+
+
Due to p min
{
: a
n=B
we have
| |
12 + 1)(1 -p) p) ()
(4
1 +T²)
2d(1 p)
20 L2
00
2 2 pr)
1+1
+
Cen
en 2 B
1
+2
d
+
a²
|110- -V
2 3
neB
2
( (r) 1r)
1+1
w²(1 p)
L2
B
22
d(1 L)
20 - L2
CenB
en² B2
+ d o²
2
+ neB 111-
V
Sc
Therefore, we can take
T= ! (f(z))- (r) L
[
Lo
d
Lo
a² La
d a²)
vn
VB
V
Sen VB
en²B vB
cc
neB
|1100
-
Note, that
Bin Σ
E [1110 -
E
Vi((2 (.) -V((a)
B
1=1
1=
53

---

Published as a conference paper at ICLR 2023
Bus
E
( - -
n2 B
0²
BBinn
0² ne
}
Next, by taking Biit = max
B
5c J
and using the last incqaulity, we have
:11
Tia d Lo
a² L.g
d
o²
{
T = 0
(1(=9)-8)
I+ vn
L +
+V Sen vB
+V en B vB)
min
/B
Cc
nEB
ndB
w ++ ( [ Lia
Log Sen /B
d
a² L +V En B
a² nEB
= =0
((a))-Pp
+ vn /B +V
+
/B
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 +
P)e I & + (1-$) ce 2ce. Therefore, the communication complexity is equal to O (d T) Considering the fact that the number of stochastic gradients that each node calculates at each communication round equals pB' + (1 p)2B S O neB
mini-batch of stochastic gradients, average,
+ 2B (B). Considering the initial batch size Binis the number of stochastic gradients that each node calculates equals O (Biit + BT).
o²
nE
Corollary 6.11. Suppose that assumptions of Corollary 6. hold, batch size B S VEn
Ven' we take
RandK with K Sc O
[Bdyen and L := max (L, Lo, D). Then the communication complex- a
ity equals
( do (f(())) f fz)
o
(11)
VNE
VNE
and the expected of stochastic gradient calculations per node equals
2 +
-
(12)
2//2n
Proof. In the view of Theorem F.2, we have w+1 1 d/K. K. Moreover, = thus the communication complexity equals
BBd/en
0
d
vn
d+ 1 3
(f(=9) - KL (it Los
L
02 La
o²
Odd o
K
K
K
Vn
BB
V
n /B
En² B
VB
nEB
0
d+
1
(((5))$1
(
d
i +
Lo
+ d
Lo
+
do
3
vn
v
/B
vn
Tne
((tt))
o
d
do
+
=
1
(f(x²)
- (f()
NE
54

---

Published as a conference paper at ICLR 2023
do 1 -r) (z)z) 1) VnE & (f(29)
+
And the expected number of stochastic gradient calculations per node equals
O [aait + BT)
1)
O
0²
+ B +
()(x))
BT. [BL++
(
Lo /B/
B
Lo
+ B
d² Log
ne
vn
n VB
En /BB
1
Ven I. (
T++ Lo vB
0
(1(9)-17
+
Iog
ne
n
g
VEn
Ven
((antt
0²
1
0
+
(f(x")- -1¹ ((6))-1a)
E
1.8 CASE OF DASHA-SYNC-MVR UNDER PL-CONDITION
Theorem
1.20.
Suppose
that Assumption 5.1, 5.2,
1.2,
5.5, 5.6 and
G.
hold.
Let
take
12w probability
p
(0, and
?
S
12w 1)(1-p) p) 43 +B+)
min
L +
1(2-p)L2 +
P. 2p
Algorithm 1, then
pub
2p
E
[f(x")) f*]
< (1 - 7H)² (f(2") + 22 + 1) 19 -11112 +
8yw
Σ 11
11
i=1
27 |110 Vf(22)11
202
+
+
nuB
Proof. Let us fix constants K. 77, E [0, 00) that we will define later. Using Lemma I.1, we can get (20). Considering (20), Lemma [.17, Lemma 1.18, and the law of total expectation, we obtain
<E E [[f(att]]]
||g N
m
vE |115-11 -V)
f(x²) 7 [| -
I
< E
| 121 + "111**
-1011 + -V
2
22
2
2w(1 p) 12 + (.2)
+ 2a² - p)
+ KE
| - z0ll3
11 - -tll + (1 - p) (1 - a)² 11 - 11t12
n²
1=1
2w p) ( L13
+ 1
+ 7.3
||
x² 2112 + (1 - p) (2a²w + (1 a)²) Σ
|o n 11
B
1=1
55

---

Published as a conference paper at ICLR 2023
po²
(1
L2
+ VE
+
|| - 2¹1 1 + (1 (1-p)) p)]ln - PV|"''Vf(2>111
nB'
nB
After rearranging the terms, we get
n
E [[( + RE
|1g - - n+]]
+ nB
9 ++1 - -1 1/
i=1
+ +vE |1 - - [19]]
<R( - F. [|V
$
1
L
21w(11 - p)
(=/² + 1.2)
21pw p)
L3 B
+ 1.3
v(1 - 2)L3
E.
[|lattt - =
27
2
nB
+ (7 + x(1 p1 a)²) E ||9 1=1
2xaaw(1- - p)
(1-aa²) + 11(11 p) 2202 + (1 - )
E
1 n
Σ
1103 hill
7
+ (7 + ((1 p)) -Vaaavaaa))
vpo
nB'
Let us take v == 27.
p. 1 == 27 a 2w 7 and 17 8ow Thus 7 + x(1 - -p)(1- - -a)² S (1 2 K
7 (1 - p) = (1- - ()) u,
2nee w((-p) + 171 p) (2a2w + (1 ao)²) S (1 - ()) 17, and
1
E [[ + 22w + 1)E 11o 11
8yw
1 n
19% +0 htt1 12
E
n
n
jml
+ "E |11- - (5( |1|]]
$ F [f(xt)] - F/ -
[|
2
1 L 42w(2w + 1)(1-)) p) (42 + +0²)
16 - p)
(4 + +[²)
12
27(1 - L
E ||a - ze [²]
27
2
n
n
pnB
+ (1 - 9) 22w2w + 1)E -1o-'~"' [3] + (1-
a)
8yw
E
1
Σ
o h0ll
n
n
i=1
11 p) 27 E [||* [
+
2) p
2700
TB'
E
[f(20]
1
[|
||(]
2
L
22w + 1)(1- p)
122 + [2)
27(1 2)12
E. ||ott
2y 2
n
pnB
1 a
27(2w 1)EE |100-~ 1011]] + (1- )
87w
1 Σ
l1 -ntlp
2)
n
11
(1- p) 27 F ||15 [
+
2 p
56

---

Published as a conference paper at ICLR 2023
27
+
nB'
(1)
417u(2w+1(1-22)
In the view of the choice of y and Lemma 1.7, one can show that
2/2
27
4y(1-p)42 pnB
1- - s 2 0,
7/4, and 1 S 7P, thus
E [f( + +2v(2w 1)13 |10 htt1
8yw
E
11 +1
R1
112
7
73
+ I | - [ |1(]
p
< [E(((()] - E ||>
+ (1 - (m) (2w + 1)F ||9* n²11"]
+ (1 ym)
8mw
F.
1
+ (1 - 71) 2% E || {((
2yo²
nB
In the view of Lemma 1.6 with
v
2(2w 1)F |||0*
Sw F.
l1ot mell?
=
+ E V
and C'
2g² nB
we can conclude the proof.
Corollary 1.21. Suppose that assumptions from Theorem 1.20 hold, probability p Sc aneB
min?
d fo batch size B' +
a²
and hi o6 0 for all i E [n], then DASHA-
unc
SYNC-MVR needs
d
o² μneB
wi P
L
d
La
T T: O
+
(28)
Sc
PVn
nn
Sen
n
BBpe
uvB
communication rounds to get an e-solution, the communication complexity is equal to O (ScT), and the number of stochastic gradient calculations per node equals O(BT), where Ço is the expected density from Definition 1.3.
Proof. Considering the choice of B', have 2n R
( Therefore, is it enough to take the number of communication rounds equals (28) get e-solution.
is left to estimate the communication and oracle complexity. On average, in Algorithm 2, at each communication round the number of coordinates that each node sends equals pd + (1
p)çe & (1d+(1-0m $$) Sc < 2Cc. Therefore, the communication complexity is equal to O (CcT).
Considering the fact that we use a mini-batch of stochastic gradients, on average, the number of stochastic gradients that each node calculates each communication round equals pB' (1-
pnn
+ 2B O (B), thus the number of stochastic gradients that each node calculates unc
equals (BT).. Unlike Corollary 6.10, in this corollary, can initialize h. and g.. for instance, with zeros because the corresponding initialization error T from the proof of Theorem I.20 would be under the logarithm.
57

---

Published as a conference paper at ICLR 2023
J EXTRA EXPERIMENTS
DASHA-MVR improves VR-MARINA (online) when is small (see Tables and 2 and experiments in Section A). However, our analysis shows that DASHA-MVR gets term Bw en in the oracle
complexity and term W Jen in the number of communication rounds in general nonconvex and PL settings accordingly. Both terms can be bottleneck some regimes; now, we verify this dependence in the PL setting.
We take a synthetically generated stochastic quadratic optimization problem with one node (n 1):
min {f(x:) {) == x (A + (I) x b²xz 2E
where E Iddd DERR A > 0, and 5 ~ Normal (0, 0²)
We generate A in such way, that R 1.0 < R 2.0, take d 10 o² 1.0, RandK with = (w x d), batch size = 1, and pen 10a, With this particular choice parameters, w
ken
would dominate in the number of communication rounds T = W o² uenB
I(14=/v))
o²
uen
La
1 VEnB
Results are provided Figure 5. We consider DASHA-MVR with momentum b from Corollary I.16
With the latter choice of momentum DASHA-MVR converges the same rate as DASHA-SYNG SYNC-MR or VR-MARINA (online) but to an e-solution with a smaller e. On the other hand, the former choice of momentum b guarantees the convergence the correct e-solution, but with slower rate. Overall, the experiment provides the pieces of evidence that our choice of b is correct that our analysis Theorem 1.15 is tight.
and b min
If we decrease from 10 to 10 (see Figure 6). or d² from 1.0 to 0.1 (see Figure 7), from 1.0 (see Figure 8), then the gap between algorithms closes.
K
VR-MARINA (online)
DASHA-MVR
10a
DASHA-MVR mint..
5'
DASHA-SYNC-MVR
10a
10-1
10-4
10-1
10
0.0
0.5
1.0
1.5
2.0
2.5
3.0
#bbts m
1e8
Figure Comparison of algorithms on a synthetic stochastic quadratic optimization task
58

---

Published as a conference paper at ICLR 2023
10a
VR-MARINA (online)
DASHA-MVR
10a
DASHA-SYNC-MVR
10
10
10
10-1
0.25
0.50
0.75
1.25
1.50
1.75
#bits
1e9
Figure 6: Comparison of algorithms synthetic stochastic quadratic optimization task with K
10
101
VR-MARINA (online)
DASHA-MVR
10a
DASHA-SYNC-MVR
10-1
10-1
0.0
1.0
2.5
3,0
#bits n
1eB
Figure 7: Comparison of algorithms synthetic stochastic quadratic optimization task with
g² = 0.1
59

---

Published as a conference paper at ICLR 2023
10a
VR-MARINA (online)
DASHA-MVR
102
DASHA-SYNC-MVR
10-2
10
10-1
0.0
0.5
1.0
1.5
2.0
2.5
3.0
#bits n
1eB
Figure 8: Comparison of algorithms synthetic stochastic quadratic optimization task with f 0.1
60


Reviews:
[{"review_id": "x2-WqMX20Uo", "reviewer": "Reviewer_cCdR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a novel propose novel methods improving the theoretical oracle and communication complexity of the previous state-of-the-art method. New methods can compress vectors, which makes them more useful in federated learning", "summary_of_the_review": "This paper proposes a novel propose novel methods improving the theoretical oracle and communication complexity of the previous state-of-the-art method. New methods can compress vectors, which makes them more useful in federated learning\nThe paper is theoretically sound, and the current version can be significantly improved in the following aspects:\n1.\tPage 21, 1/n^2  ∑_(i=1)^nE_C[...] should be  1/n  ∑_(i=1)^nE_C[...].\n2.   Page 29,   E_h [‖h^(t+1)-∇f(x^(t+1) )‖^2 ]≤  ((1-p))/(n^2 B^2 )..... should be E_h [‖h^(t+1)-∇f(x^(t+1) )‖^2 ]≤  ((1-p))/(n B^2 )..... \n3.  Finally, some experiments on federated learning should be done to verify the performance.", "strength_and_weaknesses": "Strength: This paper proposes a novel propose novel methods improving the theoretical oracle and communication complexity of the previous state-of-the-art method. This paper is theoretically sound in general\n\nWeaknesses: Some experiments on federated learning should be done to verify the performance.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "rNHtvf6mo4", "reviewer": "Reviewer_xs5t", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The goal of the paper is to solve, to $\\epsilon$-additive accuracy, finite-sum non-convex optimization under the coordinator model of distributed computation, with as small a communication cost as possible. Each server (there are $n$ of them) has access to an oracle: the paper studies three natural variants, the gradient, the mini-batch gradient, and stochastic gradient.", "summary_of_the_review": "I recommend acceptance of this paper: the problem is interesting in its own right and of great practical importance to modern machine learning where functions are potentially nonconvex and dimensions large, and the algorithms make intuitive sense. I also appreciate the effort put into keeping the paper clear and easy-to-understand. ", "strength_and_weaknesses": "STRENGTHS - I think the paper studies an important problem, is very clearly written, and seems to have done a reasonable job of comparing against prior work. \n\nWEAKNESSES - This isn't really a weakness, rather a question I have (perhaps the authors can address this in their rebuttal) --- Is the proposed algorithm a \"distributed version\" of SVRG (or some algorithm in that family)? Again, even if it is, I don't think that's a problem, I just think (if it is), it would help contextualize the paper better by discussing this connection.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "8uUegkYvBs", "reviewer": "Reviewer_hqd4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies convergence of compressed SGD to a first-order stationary point. The paper considers unbiased compressors and improves state-of-the-art convergence rate and communication complexity for both finite-sum and stochastic settings. The algorithms presented in the paper differ in update rules and their requirement for periodical synchronization. The paper uses unbiased RandK compressor with the proper K to avoid synchronization.\n", "summary_of_the_review": "Solid paper, accept.", "strength_and_weaknesses": "I have the following suggestions about the paper:\n-- I think the paper would benefit from outlining the proofs\n-- The proofs look similar to that of MARINA. Can you please elaborate on the differences between the techniques in these two papers?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "64XQHfkHQRK", "reviewer": "Reviewer_f95g", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The focus of this paper is on distributed nonconvex smooth optimization in a setting where there is synchronization among the $n$ workers and there is a central server that is coordinating communications among the workers. The authors are interested in obtaining an $\\varepsilon$-approximate first-order stationary point as a solution to three variants of the finite-sum distributed optimization problem in which the objective function $f$ is respectively:\n\n- $f(x) = \\frac{1}{n} \\sum_{i=1}^n f_i(x)$ (Gradient Setting)\n- Each local function $f_i(x)$ has a further finite-sum form (Finite-Sum Setting)\n- Each local function is expectation of a stochastic function (Stochastic Setting)\n\nThe authors aim to reduce the number of communications rounds needed in these three settings to achieve optimal oracle complexity, and this is accomplished through the use of independent, unbiased compressors at each worker. The resulting algorithms are respectively termed DASHA, DASHA-PAGE, DASHA-MVR, and DASHA-SYNC-MVR, where DASHA-SYNC-MVR is a variant of DASHA-MVR in which workers synchronize with each other every once in a while using uncompressed messages.", "summary_of_the_review": "Overall, it is a very nicely written paper and was a real pleasure to read. The algorithmic novelty of this work seems to be overstated. The theoretical novelty of the work needs to clarified better so that the reader can appreciate it. The experiment results also need to be described in a better fashion, rather than simply being presented.", "strength_and_weaknesses": "**Strengths**\n- The authors provide rigorous theoretical guarantees for the four different variants of DASHA for distributed nonconvex optimization. The results show that DASHA and DASHA-PAGE improve on the SOTA communications complexity without requiring any uncompressed synchronization steps. The variant DASHA-SYNC-MVR also improves on the SOTA communications complexity while requiring communications of uncompressed messages.\n- Results of a substantial number of numerical experiments are provided in the paper to showcase the superiority of DASHA over the SOTA algorithm MARINA.\n\n**Weaknesses**\n- DASHA is a mash-up between MARINA and existing distributed nonconvex optimization methods. Other than the fact that three variants of DASHA get rid of the uncompressed synchronization in MARINA, this reviewer could not pinpoint a difference between MARINA and DASHA. As such, the main novelty of this work seems to be in terms of theoretical analysis of MARINA when the uncompressed synchronization step is removed. The authors could have done a better job of clarifying where does this novelty lie in the analysis (e.g., pinpointing the key analytical approaches in the lemma that helped improve the analysis).\n- The experimental results are not described clearly in my opinion. It is not clear from reading the description how did the authors count the number of bits. Additionally, how exactly was the fine tuning done for the step sizes in the experiments? The results for stochastic setting don't seem as convincing for the case of $K = 2000$ and the choice of $B=1$ also seems strange.\n\n**Some Additional Feedback**\n- The mathematical expressions in the abstract have symbols that are not defined in the abstract and one has to guess about them till one gets to the later part of the paper.\n- Section 1.1: Might be useful to clarify what is the expectation going to be over.\n- Equation (2): We have $\\frac{1}{n}$ in both this equation and in (1). Is this right?\n- Definition 1.1: Does $\\omega$ really belong to $\\mathbb{R}$? Can it be negative?\n- Section 4, Third paragraph: Why does it say that it provides a \"suboptimal oracle complexity w.r.t. $\\omega$\"? Are not the additional factors not a function of $\\omega$?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%