A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting
Authors: Alexander Tyurin
Peter Richtárik
Venue: NeurIPS 2023 poster (2023)
Keywords: Nonconvex Optimization
Partial Participation
Variance Reduction
Compressed Communication
Distributed Optimization

Abstract: We present a new method that includes three key components of distributed optimization and federated learning: variance reduction of stochastic gradients, partial participation, and compressed communication. We prove that the new method has optimal oracle complexity and state-of-the-art communication complexity in the partial participation setting. Regardless of the communication compression feature, our method successfully combines variance reduction and partial participation: we get the optimal oracle complexity, never need the participation of all nodes, and do not require the bounded gradients (dissimilarity) assumption.

A Computation and Communication Efficient Method for Distributed Nonconvex Problems in the Partial Participation Setting
Alexander Tyurin KAUST Saudi Arabia al alexandert.uurii@@gaal.c.cc
Peter Richtárik
KAUST
Saudi Arabia
richtarik@gaillcom
Abstract
We present method that includes three key components of distributed opti- mization and federated learning: variance reduction of stochastic gradients, partial participation, and compressed communication. We prove that the method has optimal oracle complexity and state-of-the-e communication complexity in the partial participation setting. Regardless of the communication compression feature, our method successfully combines variance reduction and partial participation: we get the optimal oracle complexity, never need the participation of all nodes, and do not require the bounded gradients (dissimilarity) assumption.
1 Introduction
Federated and distributed learning have become very popular in recent years (Konečný et al., 2016; McMahan et al., 2017). The current optimization tasks require much computational resources and machines. Such requirements emerge in machine learning, where massive datasets and computations are distributed between cluster nodes (Lin et al., 2017: Ramesh al., 2021). In federated learning, nodes, represented by mobile phones, laptops, and desktops, do not send their data to server due to privacy and their huge number (Ramaswamy et al., 2019), and the server remotely orchestrates the nodes and communicates with them to solve an optimization problem.
As in classical optimization tasks, of the main current challenges is find computationally efficient optimization algorithms. However, the nature of distributed problems induces many other (Kairouz al., 2021), including i) partial participation of nodes in algorithm steps: due stragglers (Li et al., 2020) or communication delays (Vogels et al., 2021), ii) communication bottleneck: even a node participates, can be costly to transmit information et al., 2017; Ramesh et al., 2021; Kairouz et al., 2021; Sapio et al., 2019; Narayanan et al., 2019). It necessary to develop method that considers these problems.
server or other nodes (Alistarh
2 Optimization Problem
Let us consider the nonconvex distributed optimization problem
f(x) = M - }
min ZERd
(1)
where fi information about function f. is stored on 7th node. The communication between nodes is maintained in the parameters server fashion (Kairouz et al., 2021): we have a server that receives compressed
Rd is a smooth nonconvex function for all E [n] = {I,... n). The full
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

information from nodes, updates a state, and broadcasts an updated model.' Since we work in the nonconvex world, our goal to find an g-solution (e-stationary point) of (1): a (possibly random) point ã E Rd, such that [[Ilv/(T)]
S.
We consider three settings:
Gradient Setting. The 7th node has only access the gradient V R + R of function fi- Moreover, the following assumptions for the functions fs hold.
Assumption 1. There exists f E IR such that f() 2 f for all x E R..
Assumption 2. The function f is L-smooth, i.e., [V V f(y)l -| for all x, y E Rd.
Assumption 3. The functions fi are L;-smooth for all E [n]. Let us define L == Ei=1 L.?²
2. Finite-Sum Setting, The functions {fi}==1 have the finite-sum form
m
f((x)
(c(())
Vi E [n].
(2)
m j=1
where fij IR + I is smooth nonconvex function for all E [m]. We assume that Assumptions 1, 2 and hold and the following assumption.
Assumption 4. The function fiy is Lig-smooth for all E [m]]ij E [m]. Let Lmax ==
jae Lig.
3. Stochastic Setting. The function St is expectation of stochastic function,
f((x) = Eg [fi(;;
E [r],
(3)
where fi: R2 x 22 + R. For fixed E I, (((=;) is a random variable over some distribution Dr and, for a fixed & E Sçg fa(:;; E) is a smooth nonconvex function. The 7th node has only access to stochastic gradients V f:: Eey) of the function fa through the distribution D., where Eıy a sample from D. We assume that Assumptions 1, 2 and 3 hold and the following assumptions.
Assumption 5. For all i [n] and for all x E Rd the stochastic gradient V fa:: {) is unbiased and has bounded variance, i.e., Eg (1 E)] V(((x), and Ee [IV]((<;E) {+(()) S 00², where o² 2 0.
Assumption 6. For all E [n] and for all x, y E I, the stochastic gradient f.(( {) satisfies the mean-squand meua-e smoothness property. i.e., Eg [[V - Vf((::))ll - L2 || - yl?
We compare algorithms using the oracle complexity, i.e., the number of (stochastic) gradients that each node has to calculate to get e-solution, and the communication complexity, i.e., the number of bits that each node has send the server to get E-solution.
2.1 Unbiased Compressors
We use the concept of unbiased compressors to alleviate the communication bottleneck. The unbiased compressors quantize and/or sparsify vectors that the nodes send to the server.
Definition 1. A stochastic mapping C Rd IRd is an unbiased compressor if there exists w E I
such that [[C(x)]
and
E [C(x)) - =13] w ||=||
Va E Rd.
We denote a set of stochastic mappings that satisfy Definition as U(w). In our methods, the nodes make use of unbiased compressors {C.} The community developed a large number of unbiassed compressors, including Rand (see Definition 5) (Beznosikov et al., 2020; Stich et al., 2018), Adaptive sparsification (Wangni al., 2018) and Natural compression and dithering (Horváth et al., 2019a). We are aware of correlated compressors by Szlendak et al. (2021) and quantizers by Suresh al. (2022) that help in the homogeneous regimes, but in this work, we mainly concentrated on generic heterogeneous regimes, though, for simplicity, assume the independence of the compressors. Assumption 7. C. ((w) for all E [n], and the compressors statistically independent.
Note that this strategy can be used in peer-to-peer communication, assuming that the server is an abstraction and all its algorithmic steps are performed each node.
Note that L < L, L < Lmax, and L < Lo.

---

Table 1: Summary of methods that solve the problem (1) in the stochastic setting (3). Abbr: VR (Variance Reduction) = Does a method have the optimal oracle complexity Does a method support partial participation from Section 2.27 CC Does method have the communication complexity equals to O
PP (Partial Participation)
Method
VR
PP
CC
Limilations
SPIDER, SARAH, PAGE, STORM
(Fang 2018; Nguyen al. 2017)
(Li ot al., 2021a; Cutkosky and Orabona, 2019)
MARINA (Gorbunov al., 2021)
X
Suhoptimal convergence rate (see (Tyurin and Richtärik, 2023).
FedPAGE
X-9
Suboptinal oracle complexity O
2021b)
FRECON (Zhao 2021a)
x
FedAvg
Bounded gradients (dissimilarity) assumption of fz.
(McMahan et al., 2017; Karimireddy al., 2020b)
SCAFFOLD
Suboptimal convergence rate" (0)
(Karimireddly et al., 2020b)
Calculates full gradient.
MIME
x²4)
Bounded gradients (dissimilarit) assumption fr.
(Karimireekly et al., 2020a)
Suboptimal onacle compl. (1/2/3) the setting
CE-LSGD ffor Partial Participation)" 22 (Patel 2022) (concurrent work)
Bounded gradients (dissimilarity) assumption ft- Suboptimal oracle compl. O (1/33/2) in the sotting (2).
DASHA (Tyurin und Richtärik, 2023)
DASHA-PP (new)
MARINA and FedPAGE, with small prohability, require the participation of all nodes so that they can support partial participation from Section 2.2. Morcover, these methods provide suboptimal oracle complexities.
0i On average. MARINA provides the compressed communication mochanism with complexity O Vic However, with small probability,
methed sends non-compressed
Note that MIME and CE-LSGD can not be directly compared with DASHA-PP because MIME and CE-LSGD consider the online version of problem di Although MIME obtains the convergence rale O gradients.
require
assumptions.
3/2 of variance reduced method, it requires the calculation of the full (exact)
@) can be seen when 0. Consider the s s-nice sampling of the nodes, then SCAFFOLD requires O (,,/3 (3////33/2) communication rounds e-salution, while DASHA-PP requires O (v//ee) communicatin rounds (see Theorem 4 with 0, Po/2 and
P.
2.2 Nodes Partial Participation Assumptions
We now try to formalize the notion of partial participation. Let assume that have events {1th node is participating) with the following properties.
Assumption 8. The partial participation of nodes has the following distribution: exists constants E (0, 1] and Pea E [0, 1], such that
1.
Prob (ith node is participating) Pa Vi [m]],
2.
Prob (5th and jth nodes are participating) Paa Vi [n].
3.
Pma S P2
(5)
and these events from different communication rounds are independent.
We are not fighting for full generality and believe that more complex sampling strategies can be considered in the analysis. For simplicity, we settle upon Assumption 8. Standard partial participation strategies, including s-nice sampling, where the server chooses uniformly s nodes
without replacement (pa s/n and Pma s(s s(s-1)/n(n-1)) and independent participation, where each
3

---

Table 2: Summary of methods that solve the problem in the finite-sum setting (2). Abbr: VR (Variance Reduction) = Does a method have the optimal oracle complexity O m + ym PP CC are defined in
Table
Method
VR
PP
CC
Limitations
SPIDER, PAGE
(Fang al., 2018: al. 2021a) 2021a))
/
X
X
MARINA (Gotbunov et al,, 2021)
x/x
Suboptimal convergenice (see (Tyurin and Richtärik, 2023)).
ZeroSARAH (Li et al., 2021b)
Only bomogencous regime, i... functions are equal.
FedPAGE (Zhao et al., 2021b)
x
x(a
Suboptimal oracle complexity O (T))
DASHA (Tyurin and Richtärik, 2023)
/
x
DASHA-PP (new)
06 (h) see Table 1.
node independently participates with probability Pa (due to independence, we have Peu p²), satisfy Assumption 8. In the literature, s- s-nice sampling is one of the most popular strategies (Zhao et al., 2021a; Richtárik et al., 2021; Reddi et al., 2020; Konečný et al., 2016).
3 Motivation and Related Work
The main goal of our paper is to develop method for the nonconvex distributed optimization that will include three key features: variance reduction of stochastic gradients, compressed communication, and partial participation. We now provide an overview of the literature (see also Table 1 and Table 2).
1. Variance reduction of stochastic gradients
important to consider finite-sum (2) and stochastic (3) settings because, in machine learning tasks, either the number of local functions m is huge the functions fi expectation of stochastic function due to the batch normalization (loffe and Szegedy, 2015) or random augmentation (Goodfellow al., 2016), and is infeasible calculate the full gradients analytically. Let us recall the results from the nondistributed optimization. In the gradient setting, the optimal oracle complexity O (1/s,, achieved by the vanilla gradient descent (GD) (Carmon et al., 2020; Nesterov, 2018). In
the finite-sum sum setting and stochastic settings, the optimal oracle complexities are O (m+ Vm and
o ( 2/12 (Fang al., 2018; Li et al., 2021a; Arjevani et al., 2019), accordingly, achieved by methods SPIDER, SARAH, PAGE, and STORM from (Fang et al., 2018; Nguyen et al., 2017; Li et al., 2021a; Cutkosky and Orabona, 2019).
2. Compressed communication
In distributed optimization (Ramesh al., 2021; Xu et al., 2021), lossy communication compression can be a powerful tool to increase the communication speed between the nodes and the server. Different types of compressors are considered in the literature, including unbiased compressors (Alistarh et al., 2017; Beznosikov et al., 2020: Szlendak et al., 2021), contractive (biased) compressors (Richtárik et al., 2021), 3PC compressors (Richtárik al., 2022). We will focus on unbiased compressors because methods DASHA and MARINA (Tyurin and Richtárik, 2023; Szlendak et al., 2021; Gorbunov al.. 2021) that employ unbiased compressors provide the current theoretical state-of-ther (SOTA) communication complexities.
Many methods analyzed optimization methods with the unbiased compressors (Alistarh al., 2017: Mishchenko et al., 2019; Horváth et al., 2019b; Gorbunov et al., 2021; Tyurin and Richtárik, 2023). In the gradient setting, the methods MARINA and DASHA by Gorbunov et al. (2021) and Tyurin and Richtárik (2023) establish the current SOTA communication complexity, each method needs 1+"/y= communication rounds to get s-solution. In the finite-sum and stochastic settings, the current

---

SOTA communication complexity is attained by the DASHA method, while maintaining the optimal oracle complexities
m + v and
o /2/2 per node.
EVR
3. Partial participation
From the beginning of federated learning era, the partial participation has been considered to be the essential feature of distributed optimization methods (McMahan et al., 2017; Konečný et al., 2016; Kairouz et al., 2021). However, previously proposed methods have limitations: i) methods MARINA and FedPAGE from (Gorbunov et al., 2021; Zhao al., 2021b) still require synchronization of all nodes with a small probability. ii) in the stochastic settings, methods FedAvg, SCAFFOLD, and FRECON with the partial participation mechanism (McMahan et al., 2017; Karimireddy al., 2020b; Zhao et al., 2021a) provide results without variance reduction techniques from (Fang et al., 2018; Li al., 2021a; Cutkosky and Orabona, 2019) and, therefore, get suboptimal oracle complexities. Note that FRECON and DASHA reduce the variance only from compressors (in the partial participation and stochastic setting). iii) in the finite-sum setting, the ZeroSARAH method by Li et al. (2021b) focuses on the homogeneous regime only (the functions ft are equal). iv) The MIME method by Karimireddy al. (2020a) and the CE-LSGD method (for Partial Participation) by the concurrent paper (Patel et al.. 2022) consider the online version of the problem (1). Therefore, MIME and CE-LSGD (for Partial Participation) require stricter assumptions, including the bounded inter-client gradient variance assumption. In the finite-sum setting (2), MIME and CE-LSGD obtain suboptimal oracle complexity O (1/2722) while, in the full participation setting, is possible to get the complexity O (1/e).
4 Contributions
We propose a new method DASHA-PP for the nonconvex distributed optimization.
As far as we know, this is the first method that includes three key ingredients of federated learn- ing methods: variance reduction of stochastic gradients, compressed communication, and partial participation.
Moreover, this is the first method that combines variance reduction of stochastic gradients and partial participation flawlessly: i) it gets the optimal oracle complexity ii) does not require the participation of all nodes iii) does not require the bounded gradients assumption of the functions fi-
We prove convergence rates and show that this method has the optimal oracle complexity and the state-of- ooftthearttttt communication complexity in the partial participation setting. Moreover, in our work, we observe a nontrivial side-effect from mixing the variance reduction of stochastic gradients and partial participation. It is general problem not related to our methods or analysis that we discuss in Section C.
In Section A, we present experiments where we validate our theory and compare our new methods to previous ones.
5 Algorithm Description and Main Challenges Towards Partial Participation
We now present DASHA-PP (see Algorithm 1), a family of methods solve the optimization problem (I). When we started investigating the problem, we took DASHA as a baseline method for two reasons: the family of algorithms DASHA provides the current state-of sute-of-the-arr th-th-rrt communication complexities in the non non-partial participation setting, and, unlike MARINA, it does not send compooereeee gradients and does not synchronize all nodes. Let us briefly discuss the main idea of DASHA, its problem in the partial participation setting, and why the refinement of DASHA is not an exercise.
In fact, the original DASHA method supports the partial participation of nodes in the gradient setting. Since the nodes only do the following steps (see full algorithm in Algorithm 6):
[+1 = of CC, -1 9,
- (1-4) - -
(6)
5

---

Algorithm DASHA-PP
1: Input: starting point x. E Rd, stepsize 0, momentum E (0, 1/, momentum b (0. probability Paage E (0, 1] (only in DASHA-PP-PAGE), batch size (only in DASHA-PP. and DASHA-PP-MVR), probability Pa E (0, 1| that node is participating (9), number of iterations T T
PAGE, DASHA-PP-FINITE--IEE
2: Initialize 5 E RR, h2 E R' on the nodes and g Σ i= of on the server
3: Initialize 11g E Rdd on the nodes and take hi 2 hi (only DASHA-PP-IINIT-MMA
4: for 1- 0, 11............. ,,,,,..,
do
5: 2=*+1 = x² 79
6: Broadcast w²t x² all participattin (0) nodes
7: for = 1,... n in parallel do
8:
if' 1thh node is participating then
Calculate k. k!-1 using Algorithm 2, 3, or
9:
10:
ht*1 = h + 1 k m m++1 C.
1
1
P. (gf - ht)
12:
9, = ot + +m
!+1
13:
Send m, 1+1 to the server
14:
else
15:
M = |il (only in DASHA-PP-FINTEENWAR) h++1 h
9;
g..
m 0
17:
end if end for
18:
19:
++ gf+1 =g + Σ m
end for Output: Ht chosen uniformly at random from {x* T==)
21:
(a): For the formal description see Section 2.2.
Algorithm 2 Calculate k++1 for DASHA-PP in the gradient setting. See line in Alg.
1: k Vf(x++1)) fx(x') b (h) f(("))
Algorithm 3 Calculate kt+1 for DASHA-PP-PAGE in the finite-sum setting. See line in Alg.
1: Generate a random set I of size B from [m] with replacement
V [f(x*+1) fi(²²) Pisse (M fx(())),
with probability Ppage on all participating nodes,
2: 11+1
B Ejer; (V f (x²))
with probability 1 Ppage on all participating nodes
Algorithm 4 Cale. kLt1 for DASHA-PP-FINTTE-NE in the finite-sum setting, See line 9 in Alg.
1: Generate a random set I of size B from [m] without replacement
m B
(Viig(z*+1) - fiy((=)) - b (hi vfb(a'))) j I
2: 1++1 Mg
0,
3: 1
hig 1+1
Pa
4: 1++
1
1
Algorithm 5 Calculate k/*1 for DASHA-PP-MVR the stochastic setting. See line 9 in Alg.
1: Generate i.i.d. samples (cr /
1 of size B from D..
2: 11+1
Σ (
Viil'' 1-b (M/ + Σ Vllatiett)

---

The partial participation mechanism (independent participation from Section 2.2) can be easily implemented here if we temporally redefine the compressor and use another one" instead:
L Ci, w.p. Ph.
of + P. C, (Vii(xttt) - (1-a)=))))--- agf) w.p. Pa gi:
C
Pa
- @ 9. +1
0,
w.p. Pa-
w.p. 1 Pa
With probability 1 Pa, a node does not update of and does not send anything the server. The main observation is that we can do this trick since o depends only on the vectors x++1, x², and gi. The points 21+1 and x" are only available in a node only during its participation.
However, we focus our attention partial participation in the finite-sum and stochastic settings. Consider the nodes' steps in DASHA-MVF (Tyurin and Richtárik, 2023) (see Algorithm 7) that is designed for the stochastic setting:
b) - V g + = of C. (h: hy a h1))
h Vf((
(8)
Now we have two sequences h and of- Even if we use the same trick for (8), we still have to update (7) in every iteration of the algorithm since of +1 additionally depends on h + and li. In other words, if a node does not update of and does not send anything to the server, it still has to update /1, what is impossible without the points =++1 and x², One of the main challenges was to "guess" how to generalize (7) and (8) to the partial participation setting. We now provide solution (DASHA-PP-MVR with the batch size = 1):
1
1 = h1 +
1++ h4+11
V - V/((''s! - b (N. V((a+()+)))
Pa
of = gt + Ci
ktt1
a (of n!)
with probability Pa:
Pa
Pa
and ho#1 = h4. 94 e+1 = of with probability 1- P-pa-
Now both control variables of and h do not change with the probability 1 Pa- When the 7th node participates, the update rules of !+1 and h5+1 in (9) were adapted to make the proof work. When P. (no partial participation), the update rules from (9) reduce to (7) and (8).
The theoretical analysis of the new algorithm became more complicated: unlike (7) and (8), the control variables h&+1 and of in (9) (see also main Algorithm 1) are coupled by the randomness from the partial participation. Going deeper into details, for instance, one can compare Lemma I.2 from (Tyurin and Richtárik, 2023) and Lemma 5, which both bound ||s. - A
++ 11 The former lemma does not use the knowledge about the update rules of h works with one expectation Ee [+], uses only (4), (15), and (16). The latter lemma additionally requires and uses the structure of the update rule of h h1 (the structure very important in the lemma since the control variables 1 and g; ++1 are coupled), surgically copes with the expectations Ec [-] and Ep, [:] (for instance, it is not trivial in each order one should apply the expectations), and uses the sampling lemma (Lemma I). The same reasoning applies to other parts of the analysis and the finite-sum setting: the generalization of the previous algorithm and the additional randomness from the partial participation required us to rethink the previous proofs.
At the first reading of the proofs, we suggest the reader follow the proof of Theorem 2 in the gradient setting (DASHA-PP), which takes a small part the paper. Although the appendix seems to be dense and large, the size is justified by the fact that we consider four different sub-algorithms, DASHA-PP, DASHA-PP-PAGE, DASHA-PP-FINITE-ME -VR, and theory is designed so that the proofs do not repeat steps of each other and use one framework).
and also PL-condition (The
6 Theorems
We now present the convergence rates theorems of DASHA-PP in different settings. We will compare the theorems with the results of the current state-of-the-an methods, MARINA and DASHA, that work
If Cs U (w), then C.¹h E U 1=+11/p 1).
7

---

in the full participation setting. Suppose that MARINA or DASHA converges to E-solution after T communication rounds. Then, ideally, we would expect the convergence of the new algorithms to e-solution after up to 7/P, communication rounds due to the partial participation constraints'. The condition we provide Section F. Let
detailed analysis of the algorithms under us define Ag = f(x")= f²
6.1 Gradient Setting
Theorem 2. Suppose that Assumptions 1, 2, and 8 hold. Let us take Zw+I b 2-ps
48w (2w
1)
16
upi
Po
and 9. 1 fi(a')) for all i [m] in Algorithm / (DASHA-PP), then F.
| (7 |1
[V)))
Let us recall the convergence rate of MARINA or DASHA, the number of communication rounds get e-solution equals
A
L+ ン ) while the rate of DASHA-PP equals O A -+ - 2
+
Up to Lipschitz constants factors, we get the degeneration up to 1/8. factor due to the partial participation. This is the expected result since each worker sends useful information only with the probability Pa-
6.2 Finite-Sum Setting
Poope Theorem 3. Suppose that Assumptions 1, 2, 3, 4, 7, and hold. Let us take Iw+I b
2-pa
probability Ppage (0, 1).
42w + 1) 22 (1 - Pooge) Lunx (P-p
16
((1-
Pee 22 (1
Powee) I. max
)100)
np?
B
npp Ppace
P.
B
and
of
h (z for all i [n]] in Algorithm 1 (DASHA-PP-PAGES then E
V (f(()T) )+
2Aa 7T
We now choose Prage balance heavy full gradient and light mini-batch calculations. Let us define
1y
v Pes [0, 1]. Note that if Pa then Psa and 1p,
Corollary 1. Let the assumptions Theorem 3 hold and Prnge
(m B). Then DASHA-PP-PAGE
needs
Au
[
Linax VB
1
Lmax
T
+
(10)
Payn
Pa
n
v VB
communication rounds get s-solution and the expected number of gradient calculations per node equals O (m + BT).
The convergence rate the rate of the current State-of-thh-eee art method DASHA-PAGE without partial participation equals O Ae L+ (I+
Let us closer compare it with (10). As expected, we see that the second term w.r.t w degenerates up to 1/p.- Surprisingly, the third term w.r.t. /m/n can degenerate up to vB/p, when L. R Lmax- Hence, in order to keep degeneration up to I/n., one should take the batch size B O (Lmns/"²)) This interesting effect we analyze separately in Section C. The fact that the degeneration is up to 1/2. we check numerically in Section A.
Lmmax
+ V /m /m Luma
vB
In the following corollary, we consider RandK compressors (see Definition 5) and show that with the particular choice of parameters, up to the Lipschitz constants factors, DASHA-PP-PAGE gets the
*We check this numerically in Section A.
'The choice of the compressor is driven by simplicity. and the following analysis can be used for other unbiased compressors.

---

optimal oracle complexity and SOTA communication complexity. Indeed, comparing the following result with (Tyurin and Richtárik, 2023, Corollary 6.6), one can see that we get the degeneration up to l/n, factor, which is expected in the partial participation setting. Note that the complexities improve with the number of workers n.
and we use the unbiased compressor RandK with K (Bdd Then the communication complexity of Algorithm 1 is O (d
Corollary 2. Suppose that assumptions of Corollary hold, S min
(d+
LmarAnd and the expected number of gradient calculations per node equals PLEVE
O (m
Limax Any
The convergence rate of DASHA-PP-FINIT-MWR is provided Section E.5.
6.3 Stochastic Setting
We define h² : - h4.
Theorem 4. Suppose that Assumptions 1, 2, 3, 6, 7 and 8 hold.
Let us take a
= Iu+1
n
b E (0 Pe 2- 0 7s (1++
48w[2w up?
( (1 61223 + mpab ((1
T.²
a 23
and
Pa
g hº for all E
[n] Algorithm (DASHA-PP-MVR) Then
V)(a") 11"
24o
-/(""/])]'+++ + b
2
|100
32bw(2
PM
Σ m2 -V(c=>))))
$ T
np3
(2w + 1)
12b
d²
P
Ps
nB
In the next corollary, we choose momentum and initialize vectors hi to get e-solution.
Corollary
3. Suppose that
assumptions from Theorem 4 hold, momentun b
θ min
E V
BeB o
PineB a²
nEB 2 1, and hy Σ
o²
Bui T= fill2: 5l)) for all i E [n].
Ban
V
and batch size Binit = -
then Algorithm 1 (DASHA-PP-MVRR) needs
T=
w
(L+
+
Lo
VB VB+BB
1 I Lo
]
0² VDane
Pavn
VB
Paven
communication rounds to get an E-solution and the number of stochastic gradient calculations per node equals O (Bii + BT).
The convergence rate of the DASHA-SYNC-MVE the state-of-the-art method without partial participa-
tion, equals O A L + v (ī. /B VEn
Similar Section 6.2, we that in n
the regimes when ~ Lg the third term w.r.t 3/23/2 can degenerate to vB/pL. However, if we take B = O (1.2/D2). then the degeneration of the third term will be up to 1/z. This effect we analyze in Section C. The fact that the degeneration is up to 1/p. we check numerically in Section A.
In the following corollary, we consider RandK compressors (see Definition 5) and show that with the particular choice of parameters. up the Lipschitz constants factors, DASHA-PP-MVR gets the optimal oracle complexity and SOTA communication complexity of DASHA-SYNC-MVE method. Indeed, comparing the following result with (Tyurin and Richtárik, 2023, Corollary 6.9), one can see that we get the degeneration up to 1/2, factor, which is expected in the partial participation setting. Note that the complexities improve with the number of workers n.
{
Corollary 4. Suppose that assumptions of Corollary 3 hold, batch size B S min
L P.VEn 13
take RandK compressors with K θ Bd. 5m
Then the communication complexity equals
If p. then
12 +000
13 22

---

O
Lnd
and the expected number of stochastic gradient calculations per node equals
VP.yTe
?
VPAme
We are aware that the initial batch size Binit can be suboptimal w.r.t. w in DASHA-PP-MVR in some regimes (see also (Tyurin and Richtárik, 2023)). This is a side effect of mixing the variance reduction of stochastic gradients and compression. However, Corollary 4 reveals that can escape these regimes by choosing the parameter K of RandK compressors in particular way. To get the complete picture, we analyze the same phenomenon under PŁ condition (see Section F) and provide new (see Section G).
method
Acknowledgements
This work of P. Richtárik and A. Tyurin was supported by the KAUST Baseline Research Scheme (KAUST BRF) and the KAUST Extreme Computing Research Center (KAUST ECRC), and the work of P. Richtárik was supported by the SDAIA-KAUSE Center Excellence Data Science and Artificial Intelligence (SDAIA-KAUST AI).
References
Alistarh, D., Grubic, D., Li, J., Tomioka, R., and Vojnovic, M. (2017). QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Process- ing Systems (NIPS), pages 1709-1720.
Arjevani, Y., Carmon, Y., Duchi, C., Foster, J., Srebro, N., and Woodworth, B. (2019). Lower bounds for non-convex stochastic optimization. arXiv preprint arXiv:1912.02365.
Beznosikov, A., Horváth, S., Richtárik, P., and Safaryan, M. (2020). On biased compression for distributed learning. arXiv preprint 1rXiv:2002.12410.
Carmon, Y., Duchi, C.,, Hinder, O., and Sidford, A. (2020). Lower bounds for finding stationary points i. Mathematical Programmingg 184(1):71-120.
Chang, C.-C. and Lin, C.-J. (2011). LIBSVM:
library for support vector machines. ACM Transac- fions Intelligent Systems and Technology (T7S7), 2(3):1-27.
Cutkosky, A. and Orabona, (2019). Momentum-based variance reduction in non-convex SGD. arXiv preprint arXiv: 1901.
Fang, C., Li, C. J., Lin, Z., and Zhang, T. (2018). SPIDER:
Near-optimal non-convex optimization via stochastic path integrated differential estimator. In NeurIPS Information Processing Systems.
Goodfellow, L., Bengio, Y., Courville, A., and Bengio, Y. (2016). Deep learning, volume 1. MIT Press.
Gorbunov, E.. Burlachenko. K., Li, Z., and Richtárik, P. (2021). MARINA: Faster non-convex
distributed learning with compression. In 38th International Conference Machine Learning.
Horváth, S., Ho, C.-Y., Horvath, L., Sahu, A. N., Canini, M., and Richtárik, P. (2019a). Natural compression for distributed deep learning, arXiv preprint arXiv: 1905.::995..0000
Horváth, S., Kovalev, D., Mishchenko, K., Stich, S., and Richtárik, P. (2019b). Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv: NXi::/994005//55
Ioffe, S. and Szegedy, C. (2015). Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning, pages 448- 456. PMLR.
Kairouz, P., McMahan, H. B., Avent, B., Bellet, A., Bennis, M., Bhagoji, A. N., Bonawitz, K., Charles, Z.., Cormode, G., Cummings, R., et al. (2021). Advances and open problems federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-21..
10

---

Karimireddy. S. P.. Jaggi, M., Kale, S., Mohri, M., Reddi, S. J., Stich, S. U., and Suresh, A. T. (2020a). Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint urXiv:2008.03660
Karimireddy, S. P., Kale, S., Mohri, M., Reddi, S., Stich, S., and Suresh, A. T. (2020b). Scaffold: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pages 5132-5143. PMLR.
Konečný. J., McMahan, H. B., Yu, F. X., Richtárik, P., Suresh, A. T., and Bacon, D. (2016). Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv: 1610.05492.
Li, T., Sahu, A. K., Zaheer, M., Sanjabi, M., Talwalkar, A., and Smith, V. (2020). Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Systems, 2:429- 450.
Li, Z., Bao, H., Zhang, X., and Richtárik, P. (2021a). PAGE: simple and optimal probabilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pages 0286-6295. PMLR.
Li, Z., Hanzely, S., and Richtárik, P. (2021b). ZeroSARAH: Efficient nonconvex finite-sum optimiza- tion with zero full gradient computation. arXiv preprini arXiv:2103.01447.
Lin, Y., Han, S., Mao, H., Wang, Y., and Dally, W. J. (2017). Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv: 1712.008
McMahan, B., Moore, F.,, Ramage, D., Hampson, S., and y Areas, (2017). Communication- efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR.
Mishchenko, K., Gorbunov, E., Takáč, M., and Richtárik, P. (2019). Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.000 1901.09269.
Narayanan, D., Harlap, A., Phanishayee, A., Seshadri, V., Devanur, N. R., Ganger, G. R., Gibbons, P. B., and Zaharia, M. (2019). PipeDream: generalized pipeline parallelism for dnn training. In Proceedings of the 27th ACM Symposium Operating Systems Principles, pages 1-15.
Nesterov, Y. (2018). Lectures on convex optimization, volume 137. Springer
Nguyen, L., Liu, J., Scheinberg, K., and Takáë, M. (2017). SARAH: A novel method for machine learning problems using stochastic recursive gradient. The 34th International Conference on Machine Learning.
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS).
Patel, K. K., Wang, L., Woodworth, B., Bullins, B., and Srebro, N. (2022). Towards optimal commu- nication complexity distributed non-convex optimization. In Advances in Neural Information Processing Systems.
Ramaswamy, S., Mathews, R., Rao, K., and Beaufays, F. (2019). Federated learning for emoji 04329.
prediction in a mobile keyboard. arXiv preprint
Ramesh, A., Pavlov, M., Goh, G., Gray, S., Voss, C.,, Radford, A., Chen, M., and Sutskever, I. (2021). Zero-shot text-to-image generation. arXiv preprint arXiv:2 102. /2092.
Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečný, J., Kumar, S., and McMahan, H. B. (2020). Adaptive federated optimization. arXiv preprint arXiv:2003.00295
Richtárik, P., Sokolov, I., and Fatkhullin, I. (2021). EF21: new, simpler, theoretically better, and practically faster error feedback. In Neural Information Processing Systems, 2021.
Richtárik, P., Sokolov, I., Fatkhullin, I., Gasanov, E.,, Li, Z., and Gorbunov, E. (2022). 3PC: Three point compressors for communication--ffieee distributed training and a better theory for lazy aggregation. arXiv preprint arXiv:2202.00999.

---

Sapio, A., Canini, M., Ho. C.-Y., Nelson, J., Kalnis, P., Kim, C., Krishnamurthy, A., Moshref, M.. Ports, D. R., and Richtárik, P. (2019). Scaling distributed machine learning with in-network aggregation. arXiv preprint arKiv: arXiv:1903.006 1903.06701.
Stich, S. U., Cordonnier, J.-B., and Jaggi, M. (2018). Sparsified SGD with memory. Advances in Neural Information Processing Systems, 31.
Suresh, A. T., Sun, Z., Ro, H., and Yu, F. (2022). Correlated quantization for distributed mean estimation and optimization. arXiv preprint arXiv:2203. 04925.
Szlendak, R., Tyurin, A., and Richtárik, P. (2021). Permutation compressors for provably faster distributed nonconvex optimization. arXiv preprint arXiv:2110.03300
Tyurin, A. and Richtárik, P. (2023). DASHA: Distributed nonconvex optimization with commu- nication compression and optimal oracle complexity. International Conference on Learning Representations (ICIR).
Vogels, T., He, L., Koloskova, A., Karimireddy, S. P., Lin, T., Stich, S. U., and Jaggi, M. (2021). RelaySum for decentralized deep learning on heterogencous data. Advances in Neural Information Processing Systems, 34.
Wangni, J., Wang, J.. Liu, J., and Zhang, T. (2018). Gradient sparsification for communication- efficient distributed optimization. Advances in Neural Information Processing Systems, 31.
Xu, H., Ho, C.-Y, Abdelmoniem, A. M., Dutta, A., Bergou, E. H., Karatsenidis, K., Canini, M.. and Kalnis, (2021). Grace: A compressed communication framework for distributed machine learning. In 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS), pages 561-572. IEEE.
Zhao, H., Burlachenko, K., Li, Z., and Richtárik, P. (2021a). Faster rates for compressed federated learning with client-variance reduction. arXiv preprint arXiv:2112.13097.
Zhao, H., Li, Z., and Richtárik, P. (2021b). FedPAGE: A fast local stochastic gradient method for communication-efioee effficcct federated learning. arXiv preprint arXiv:2108.0477
12

---

Contents
Introduction
2 Optimization Problem
2.1 Unbiased Compressors
2.2 Nodes Partial Participation Assumptions
3
Motivation and Related Work
Contributions
5
Algorithm Description and Main Challenges Towards Partial Participation
6
Theorems
6.1
Gradient Setting
6.2
Finite-Sum Setting
6.3
Stochastic Setting
Numerical Verification of Theoretical Dependencies
15
A.I Experiments in Partial Participation Setting
16
Original DASHA and DASHA-MVR Methods
17
Problem of Estimating the Mean in the Partial Participation Setting
18
D Auxiliary facts
19
D.I Sampling Lemma
19
D.2 Compressors Facts
21
Proofs of Theorems
E.1
Standard Lemmas in the Nonconvex Setting
22
E.2 Generic Lemmas
................................
23
E.3 Proof for DASHA-PP
26
E,4 Proof for DASHA-PP-PAGE.
30
E.5 Proof for DASHA-PP-FINITEMMR
E.6 Proof for DASHA-PP-MVR
52
Analysis of DASHA-PP under Polyak-Lojasiewiez Condition
65
F.1
Gradient Setting
65
F2
Finite-Sum Setting
65
F3
Stochastic Setting
66
F.4
Proofs of Theorems
67
R4.1
Standard Lemma under Polyak-Lojasiewva Condition
67
13

---

F.4.2
Generic Lemma
67
F.4.3
Proof for DASHA-PP under Pf.-condition
69
F.4.4
Proof for DASHA-PP-PAGE under Pt.-condition
F.4.5
Proof for DASHA-PP-MVR under Pł-condition
76
Description of DASHA-PP-SYNC-MVR
83
G.I Proof for DASHA-PP-SYNC-MVR
14

---

A Numerical Verification of Theoretical Dependencies
COCHER2
DARIMEA Mn Sea 021
DANAN STTC MAA Way
2--000 INbe
INUNAAGE bn Seep atre Room with sin
Seepaie
(b) Stochastic setting, "//nD 10000, and 200
(a) Finite-sum setting, K = 500 in RandK.
in RandK.
Figure 1: Classification task with the real-sim dataset.
Our main goal is verify the dependeces from the theory. We compare DASHA-PP with DASHA. Clearly, DASHA-PP can not generally perform better than DASHA. In different settings, we verify that the bigger Pa, the closer DASHA-PP to DASHA, iee, DASHA-PP converges no slower than l/x. times.
In all experiments, we take the real-sim dataset with dimension d = 20,958 and the number of samples equals 72,309 from LIBSVM datasets (Chang and Lin, 2011) (under the 3-clause BSD license), and randomly split the dataset between = 100 nodes equally, ignoring residual samples. In the finite-sum setting, we solve a classification problem with functions
1 m
112
[xx)
exp(uraaf 1-1+exp(uja,pa)
(11)
where as E Rd the feature vector of sample on the 7t node, Biy (-1,1) the corresponding
label, and is the number of samples the 7th node for all E [n]. In the stochastic setting, consider functions
exp (arzImn)) Eye(1,)) exp (a.garn))
{ay 1 1+ t
22) = Ejn(m)
log
+1
Σ
Σ
(12)
12
VE(1.2) A=
where 11, x2 E R2d {.hx is an indexing operation, ai E Rd a feature of sample on the 7th node, Yiy E 21. is corresponding label, m is the number of samples located on the 7th node, constant A = 0.001 for all i E [n].
The code written in Python 3.6.8 using PyTorch 1.9 (Paszke et al., 2019). A distributed environment was emulated on machine with Intel(R) Xcon(R) Gold 6226R CPU @ 2.90GHz and 64 cores.
We use the standard setting in experiments' where all parameters except step sizes are taken as suggested in theory. Step sizes are finetuned from set (2' E [-10, 10]]. We emulate the partial participation setting using s-nice sampling with the number of nodes n = 100. We consider the Rand compressor and take the batch size B = 1. We plot the relation between communication rounds and values of the norm of gradients at each communication round.
In the finite-sum (Figure la) and in the stochastic setting (Figure 1b), we see that the bigger probability Pa = s/n to 1, the closer DASHA-PP to DASHA, Moreover, DASHA-PP with 10 and & converges approximately x 10 (= 1/p.) and 100 (= 1/p.) times slower, accordingly. Our theory predicts such behavior.
Code: http://hhibbbemmmnyyyyyyysssrder partiall-aaalalaaaaa participation pattiiiiooooooiaiiaaictitttooo
15

---

A.1 Experiments in Partial Participation Setting
In this experiments, we compare our new algorithm DASHA-PP with previous baselines MARINA and FRECON in the partial participation setting. We consider MARINA and FRECON because they are the previous SOTA methods in the partial participation setting with compression. We investigate the same optimization problem and setup as in Section A of the paper. All methods use the Rand compressor in these experiments.
1. Finite-Sum Setting. We now consider the function from (11). In Figures and 3, we compare all three methods in the finite-sum setting on two different datasets: real-sim and MNIST. The parameter s is the number of clients participating in each round that are selected randomly using the s-nice sampling (server chooses uniformly s nodes without replacement). We can see that DASHA-PP converges faster than MARINA. Since FRECON does not support variance reduction of stochastic gradients, it converges less accurate solutions.
(a) I % of nodes participating (b) 10 % of nodes participating (c) 90 % of nodes participating Figure 2: Classification task on real-sim
(a) 10 % of nodes participating (b) 50 % of nodes participating (c) 90 % of nodes participating
Figure Classification task on MNIST
2. Stochastic Setting. In Figures 4 and 5, we consider the stochastic setting with the function from (11). We can see that DASHA-PP convergences to high accuracy solutions, unlike FRECON. Moreover, DASHA-PP improves the convergence rates of MARINA.
(a) 10 % of nodes participating (b) 50 % of nodes participating (c) 100 % of nodes participating
Figure 4: Classification task on real-sim
(a) 10 % of nodes participating (b) 50 % of nodes participating (c) 100 % of nodes participating
Figure Classification task on MNIST
16

---

B Original DASHA and DASHA-MVR Methods
To simplify the discussion and explanation from the main part, we present the algorithms from (Tyurin and Richtárik, 2023)
Algorithm DASHA
1: Input: starting point x E IR stepsize y > 0, momentum E (0, 4], number of iterations T 2 1
2: Initialize g. E R on the nodes and gd 1 E of on the server
3: for 0, 0.1....,
do
4: xx++1 x² 7g
5: Broadcast x²+1 and xt
6: for .2 in parallel do
7:
m 1+ = c; (V V Vff((())
8:
9, [+1 g m r+1
9:
Send mi to the server
++1
10:
end for
g g+1 =g" 4
12: end for
Output: $f' chosen uniformly random from {x²)
Algorithm 7 DASHA-MVR (with batch size B 1)
1: Input: starting point x E Rdd stepsize y 0, momentums a, (0, 1J. number of itera-
tions 7 2
2: Initialize Φ Rd the nodes and 9 " Σi= A the server
3: for 1.= 0, T
do
4: xx+11 x² 3
5: Broadcast x x and x²
6: for ,...., in parallel do
7:
h++1 -Vf((x*+11 +f+1)
() - vf((ft://))), 5t2 ~ D. m, ++1 C, (1tt1 M 4--a (gl 1))
8:
9i (+1 of + m
1+1
9:
10: Send m; to the server
11: end for
12:
g ++1 g" +
13: end for
T-1 14: Output: TT chosen uniformly at random from {=))
17

---

C Problem of Estimating the Mean in the Partial Participation Setting
L
We now provide the example to explain why the only choice B - min
m
and
L2 in DASHA-PP-PAGE and DASHA-PP-MVR, accordingly, guarantees
B = O min
a
paven 12,
the degeneration up to 1/p. This is surprising, because methods with the variance reduction of stochastic gradients (L.i et al., 2021a; Tyurin and Richtárik, 2023) we can take the size of batch size and guarantee the optimality, Note that the smaller the batch size and the nodes have communicate to get e-solution.
B O (V+ and = O
Ven
B. the more the
Let us consider the task of estimating the mean of vectors in the distributed setting, Suppose that we have nodes, and each of them contains vectors {z4j J==1. where T,j R for all i [m], E [m]. First, us consider that each node samples mini-batch I of size with replacement and sends to the server. Then the server calculates the mean of the mini-batchan from nodes. One can easily show that the variance of the estimator is
m
E
Σ JEZ
Dif
Zij
(13)
nB
mm
F3j
BB YM
1=1
Next, we consider the same task in the partial participation setting with s-nice sampling, i.c., we sample random set C [n] of [m] nodes without replacement and receive the mini-batches only from the sampled nodes. Such sampling of nodes satisfy Assumption 8 with Ps = s/n and
Pa <(o-11/n(n-1), In this case, the variance of the estimator (See Lemma with r; and Ejen(a)) x2j) is
n
m
ΣΣ
Vij
Zig
(14)
BB
THTTI
iES JET
j=1
Tíj
Zijj
sB 1= j=1
n
1
Tij
8n
1=1
Let us assume that S n/2. Note that (13) scales with any B 2 1, while (14) only scales when B = O (C In other words, for large enough B, the variance in (14) does not significantly improves with the growth of due the term _ In our proof, due partial participation, the variance from (14) naturally appears, and we get the same effect. As was mentioned in Sections 6.2 and 6.3, can be seen in our convergence rate bounds.
18

---

D Auxiliary facts
We list auxiliary facts that we our proofs:
1. For all x, E Rd, we have
|| + w/l 2| + l
(15)
2. Let us take random vector E R then
[|]| = [I - EE + [|]
E
(16)
D.1 Sampling Lemma
This section provides a lemma that regularly use in our proofs, and it is useful for samplings that satisfy Assumption 8.
Lemma 1. Suppose that a S is a random subset of a [n] such that
1.
Prob (i E S) = Pa.
Vi E [ra].
2.
Prob (i {,, 8)
Pans
Vi Vi [n].
3.
Pma S Pa
where E (0, 1] and Pma E [0, 1]. Let us take random independent vectors 8, E IRd for all i E [n]. nonrandom vector r; E Rd for all E [m], and random vectors
rs + 1 11, ii, & S.
2/
then
E.
F
0/
E
||s;
E
[s:]]]
Pmn
[s:]]
Pmn
[s:]
P
2²p2
pd
i=1
E
||s
E
[s
+
Pmu
[s11.
Pa
n²
Proof. Let us define additional constants Pan and Pmns such that
1.
Prob (Ej E S) = Pan:
Vi E [m].
2.
Prob (i S.j & S)
Pmn- Vij [n].
Note, that
Pa Pea + Pan
(17)
and
Pno Paa 2pan-
(18)
Using the law of total expectation and
E.
Pa
+
E
+ (1
pa)r; + [s.
Pa
19

---

we have
1
E
0 E
U/
[|0 - (r, + E [s:))1]]
71
E Kuz
(rr + E(s:)) Uy (ry + Es
n (g/
8; (r: + +E(ss)) 127
Pa
E
Fi +
n 1=1
Pa
+ 122
Pa
||rs (r. + E {s)))]]
i=1
10
8, (r: (b++)ss))). .r, + 1,,, - (ry + ((sss)) }
Pua
E
T: +
11
Ph
ph
1
2aa
-8: 8, (r: + [s.] .r - (ry + E [o.1)
+
r1d +
n
Pa
Pun
(Ta (r, + E(st)) .y (ry + Es,)D)
72
From the independence of random vectors 8i. we obtain
E
Σ
U/S
E
0
1=1
E
E
[s:]
n2
Pa
+
Pa
||E [s.]1
n²
Y=1
Pao (1 Pa)
(E [ss]] E [s,,)
n²22
2pa (Pa
1)
n
+
EEl [8:] (3)))
n² P2Pa
itj
+
Pnn
EE [sa] E [s51)>
n2
Using (17) and (18), we have
1
E
-
E
0/3
1=1
P4
E
E
[+
72
Pa
1=1
1
Pa
|E
[s:]]]|
112
1=1
20

---

(E [+i] E [s)))
n² p2p2
$
(16
1
||sc E [s:]]]]
71. Pa
|| [s:]]]
n²pp Pa
1=1
Pea Pa
+
E [s:] E [sy]}
n² p²
E ||s;
E [s:]
n Pa
Pa
Pus
E [s 2
n n²pp2
im
Paa
P
[s
P
1=1
Finally, using that Pea S p. we have
E
U2
E
1=1
F
|8
[s
E
Pa n
Pea
[ [s:]]]
n
Pa
ph
D.2 Compressors Facts
We define the RandK compressor that chooses without replacement K coordinates, scales them by constant factor to preserve unbiasedness and zero-out other coordinates.
Definition 5. Let us take random subset S from [d], ||| K, K [d]. We say that stochastic mapping C Rd - IRd is Rand if
d Σ IjCjo
C(x)
K jES
where {es) is the standard unit basis. Theorem 6. C is RandK, then U ( 1).
See the proof in (Beznosikov et al., 2020).
E Proofs of Theorems
There are three different sources of randomness Algorithm 1: the first one from vectors {kt ++++ the second from compressors {C; ). and the third one from availability of nodes. We define Es f.l. Eg [] and Epp, to be conditional expectations w.r.t. (K(+1) y 1 {C,} and availability, accordingly, conditioned on all previous randomness. Moreover, we define E,+1 [-] to be a conditional expectation w.r.t. all randomness in iteration |+ conditioned all previous randomness. Note,
J==
that Ex+1 [+] = Ex [Ec Ex, [:]]]-
In the case of DASHA-PP PAGE, there are two different sources of randomness from {K. {K++1 ia
-==1-
We define Eppac [:] and Eg [:] to be conditional expectations w.r.t. the probabilistic switching and mini-batch indices If. accordingly, conditioned on all previous randomness. Note, that E [
Eg [Ec [Ep, [Epre [:]]]]] and E [ Eg [Epeer Ec [pp [.]]]]
21

---

E.1 Standard Lemmas in the Nonconvex Setting
We start the proof of theorems by providing standard lemmas from the nonconvex optimization.
Lemma 2. Suppose that Assumption 2 holds and let x = x² -ng'. Then for any g E IR and
y > we have
1 4 2 | 2'112 2 1 -Vf (19)
f(x sf()) [f(x')]]
Proof. Using L L-smoothness, we have
f(x!t2) - +(=') (Vf(x*), x -x²) = L
2 || - xell
= f((x²) - (vf(2') ),9²) + L ||_ - x2l1?
Next, due to -0-(2,1) 1/2 || v/1²= || |1yl1 obtain
(( 7 [ 27 2) || - 2212²+ 7 Elg -Vf(='||
Lemma 3. Suppose that Assumption I holds and
[[f( + [f(()²]
E [[=)() +7000 + yC,
(20)
2
where V is sequence of numbers, d for all t [T]. constant C 2 O, and constant Then
0.
E [|]
2
2y
+
2C,
(21)
TT
T
where point aT is chosen uniformly from a set of points {x'17 T-1
T-
Tt=0
Proof. By unrolling (20) for from 0 to T - 1, we obtain
T-1 F [|V
+ [s(=)) + +N
S1(x)) + +TCC
We subtract f*, divide incquality by 2f and take into account that f(x) 2 f for all R, and d > 0 for all t [T', get the following inequality:
24.
2T0
E E
+ +C..
T
left to consider the choice of point /f to complete the proof of the lemma.
Lemma 4. 1f0 < (L VA
L 0, and A 0, then
1
7A
20 0.
27
2
The lemma can be easily checked with the direct calculation.
22

---

E.2
Generic Lemmas
Lemma 5. Suppose that Assumptions 7 and 8 hold and let us consider sequences gi ++1, h,+1, and
kit1 from Algorithm 1, then
|11
h 1 [[]]
Fee
2w
1 a²((2w + 1111 Pa - Pmu)
Σ
l1
hill + (1 - -a)) =a) - 1112, (22)
12" Pa
n²pp
i=1
1=1
and
lg ++1 n 15t1112]
Fic
Epp
2w <
|
+ a (2w (2w+++ +
Pa) + (1 +11-a) a)²
/1g1 -b:ll vi [m].
(23)
Proof. First, we estimate Ee Ep, [l1g - - -1-
Ee [Ep, [11ot1 - - 1111
= Ec EEn, ||g 12 Ec Ep, [ -
[1] III [1] + ||Ec En [g 1
where we used (16). Due to Assumption have
Ec Epp
E.Ee
9i
C.
a
(g) h!)
+ (1 PP))g
Pa
Pa
oو + Palic
C:
a
(g) h!t)
Pa
Pa
of k(t1
(g.
N!))
and
1 1
Ee [E, [h]+1]
E.Ee
h4 +
+ (1 Pb)h h1 + +
Pa
Thus, we can get
Ec Ep, 11 -110 11]1
Ec Ep. [19 h2+1 Ec EE,, [g 11 + + a)²
I|g h1912.
Due the independence of compressors,
use Lemma with r, ot hg and 8; (of 1()) kgt1 and obtain p.
PaC.
1 1 Pa
Fyp,
|1g - - 1111
Ee
1
Fic
paCi
1++1
(of - h!)) ) -(tt
Fec
PaC;
blt1 a (gf h!)
1,+1
n n2pa 1=1
Pa
Pa
Pa
Pa
n
Pn
Pan
Ec
PaC.
blt1
(of h!)
1it+1
n1 2
Pa
Pa
23

---

+ (1 aa2 1111g - -h²ll²
(of h!) 12
Pa
Ee
C
- x++1
1
-
(gf
k!))
-
1
k
112
Pa
Pa
Ph
Ph
1=1
a² (1a
Pma) )
12
+ (1 -a)-2)11
111 - n911
n2
p2pp
From Assumption 7. we have
Ee
Epp
|1g
+
4Pa n
1 Ret
a
(gf hb)
2
+
a² (pa - Pm
||
Mill 2 + (1 =)2]|1² - -
Pa
Pa
n2 Ps
==1
i=1
+ a² (Pa Pan)
n
w
Σ
|
a (g) - hb)ll
9 hil
+ (1 - a)² a)²11g² - 1²1l
n Pa
n2 n²p2
i=1
(15)
2w
| + a² ((2w + 1)ps
Pea
|19
-All + (1 (1-a)2 - -1812.
n Pa
n²1²
The second inequality can be proved almost in the same way:
||0: ++1 - n₂t []]]
Ec
Epp
|10, 1+1 - -,++1 - Ee Ep, 10 1+1 n1t [1]]]]] + |Ee Exp 19, r+1 11
Ee
Exp
Ee
Eyg
|10 - -1$t1 - ot + (gt - hi)) + n]]][]] + (1 - a))² 11% 11 2
(o) - h!)) )
1 kttz
1 ket1 + a (0f -na)
E.Ec
C,
Pa
Pa
Pa
+ a² (1-
Pa)
|19
hill
2
+ (1 a)² 110/ - h?ll?
(16)
EgE
C.
1
h++1
a
(g) hら)) -
1
k h
(g h3)
Pa
Pa
Ph
+ 2 (1
Pa)²
0
nill?
Pa
+ a1 pa) |10| MIll 2 + (1 a)² 11o8 n!ll?
|| a
(o) ht) 2
Pa
a2 Pa)
1 hg | + (1 a)² |10 - -h?l1²
Pa
(15) 2w
(++1 113
d2(2w + +1+ - Pa)
|1 -hill + (1 a)2 -
Pn
Pa
Lemma 6. Suppose that Assumptions 2, 7, and 8 hold and let take
Pr- then
E []] 72w + 1)
[110 - n 1121 7((w + 1) Pa
Paa)
11 + 11 n2t211
E
E
Pa
np²
72
< E [(x') - ||
( -(1
4
||0 - x²'l + 7 ||A1" v {12)))11
27 2
72w + 12 [1os - -no1p]]
2(2w + 1) Paa)
n Σ l1lt - n3l1²)
n
+ 47w + 1)
1 12
Pa
npp
24

---

Proof. Due to Lemma 2 and the update step from Line 5 in Algorithm 1, we have
E441 ([(x)t|)]
$ &Ea+1 [(x9) - 7 |
L
| =0'1 + 2 2 'll' - [
2
27
2
= =E++1
s(x²) - 2 |v((t))]
L
|| x²11² + - 'llo* h² + h² - V
27
2
2
(16)
((x!) - 1 |(({tt)]
1
||0 - =²I + (1ls - 1² + ||a'- -V())))11)
< Ex+1
27
2
Let us fix some constants k E [0, oo) that we will define later. Combining the last inequality, bounds (22), (23) and using the law of total expectation, we get
[f(x(t)]]
+ +nE |1got1 - 11] + nB
19 - n1 1/
n
= =F [Fet [
1 n
|19b +1 - -h. ]]
[|]]]] + nE
+ +xE| Ec Ep.
Ec
Ep,
1=1
< E f(x') )
(1 ||²
- (1) 1 L
2 2 ||a/t1 x''l 11 + 7 (lg' - h1yl² + ||/l - Vf(2")]+))
2
+ *KE
2w
||,-1111
+
a² <2w + 1) - Paa)
Σ
|191 11ll² + (1 - a)² 1/0* - n]qee
P2
n²pp"
1=1
+ +n
2w
|M+1112=
|
+
a² (2w + 1 - pa)
+ (1 (1-10 0)²
Σ |o - 1tll?
r2pa 1=
Pa
1=1
E f(x²) 7 || )|²
(1
1
L
- 2011 y || {
2
y2
2
(7 + K (1 -a)²) E. |1l9* -ht- [3]
+
ka² ((2w + 1) PPaa) +1 11
a² a22
+ 1 Pa) + (1 - -(1=a)) E Σ 11at - -
npp
Pa
(2kw
2mT
| +1 1|?
+
+
E
nia
Pa
Now, by taking x = 2. we can see that 7 + K (1 - a)² < K, and thus
E
[[(xtt
EE - -10 1=211²] + +nE
Σ
12
19
(+1 - h1 1/t2112
a
71 im1
E ((xt)- - - "
1
L
||02 - 22112 + > (1l'-v/((+)))
27
2
7 E |100* - =n11²]
a
(2w + 1) Pa- Pma) + 17
(2w + 1 - pm) + (1 -(²))) F.
1 Σ
1 n
U1 m9l1
+
np2
P2
22w anpa
+ 2mpw
1 n
1 2
E
Pa
n2
25

---

Next, by taking 1) 7((2w+ Pps) and considering the choice of a, one can show that
np7
(na((2w+))n Pul + 17 ngs
a a2(2w+1-p)) po) + +11 (1-))) S 7. Thus
E [[((((tt]
+ 7/2 + 1) E -11 + 7((2 + 1) Pa Pan)
10 ++1
1|
Pa
np2
1=1
S E ((00) - -// || ( 1 L.
24 2 | - x011?
+ 111² vs(2')] 11
2
7(2 + +11 F. |100* - ==91"]] + 7[(2w + 1)1a
Paa)
E
1
l1of
nt1l?
Pa
mp3
22w + 1)w
(2w + 1)
Pwa)w
E
k
1
nyp
npp
am1
Considering that Pmu 2 O, we can simplify the last term and get
[f(x E
72w + 1) F. |10 - - 119-
+ 7(ww + 1)pp
Paa) F.
10 ++1 n 1/ 113
Pa
np?
S E
f(at) - 7
1 | (
1 ||a - =²11
+ + 111²"
vf(=")) 19
2
27
2
7(2 + 1) ||10* - =1]0'
+ 7112w + 1) Pea) F.
1
Σ
l1st mt|1²)
Pa
n 1=1
(2w + 1)w
| 122
E
mp2
E.3 Proof for DASHA-PP
Lemma 7. Suppose that Assumptions 3 and 8 hold. For h2t1 and k6t+ from Algorithm I (DASHA-PP)
we have
1.
Ep. |1 - )
(Pa Paa) I || - 201 + 26 (pa Pea)
| - 1) - v
5
np²
n²p2
2.
Ep, |11//- - vf((a=1)111 [11²]
2(1 - Pa) 1 |1 - xz 211 + 225p(1 - Pa)
+ (11-)))) 1)9) 1 - V/(0"1| [r].
<
Pa
Pa
3.
|| < 2L? || - -2011 + 26 1 -Vf(=())1
Proof.
First, let us proof the bound for Ex. [Eg,
[ [V(++t)1()
Epp [|1st1 - V[(aa~1)|1 [||]]
26

---

Ep. [1 Ep. [ + |m [ht [f(
Using
Ep. [4++2]= = 14 + V/i(attt)) - V.((aa) - -1n v(((o!))
and (16), we have
Epp || - [
EE [ - Ep, "[+1]|
+ (1'
We can use Lemma I with ri = / and s; = kft1 to obtain
|
v((x++1]1" ||²]
Ep.
| 1/t11122 + Pa - Pan
|k
11tt + (1 (
Pa i=1
n2 12213
i=1
P4 Psa
[f(( Vf((x') b (h1 Vf((a))]l + (1 1|n 11-' v/(('))1
n²pp t=1
(15) 2 (Pa- Pan)
Vi(ltt1) [)((+')1 20 (pn Paa)
Σ 1 Vf((>')|1 + +1 (1- - b)² |11 - vf((")]1
n² n2pp
n²p?
2 (pn Pma)
i?2
| - x²
26 (pa - Pma)
+ - b)² 11' - Σ V
2
p²pp
In the last in inequality, we used Assumption 3. Now, we prove the second inequality:
Ep.
|| V ((((=+1)111"
Eyp
||1 Ep,, [h] [M]+]]]] + E|
- -
Epp
||ast1 (h) + Vf((att))= Vf((=') 6(4g - V(((+')))
(1- - b) vf((a()22
ppa)²
[[((t't) - V/((a') - b( VA(E!))
Pa
+ (1 Pa)
(1(( - V/(a0') - 6(4 - V(((+)) + (1- ([1-b)) b)11 vA(+>))
(1 - Pa)
[ ++1 V)((=") 6(4 - V.((''))|| + - (1-b) M|M V/(('')]
Pa
2(1 Pa)
T 11 1+ 11 x¹ 1 1 22/ (1-1122) - pb) + (1 (l-by) 11²) | - vs((+')1
Pa
Finally, the third inequality of the theorem follows from (15) and Assumption
Theorem 2. Suppose that Assumptions 1, 2, and hold. Let us take a 2
P..
b Pa
2-pa
3
L
48w (2w
1)
Pau
1/2
npp
and of = =b for all i E [n]] in Algorithm / (DASHA-PP), then E
|
|1| < 2
$290
Proof. Let us fix constants p [0, oo) that we will define later. Considering Lemma 6, Lemma 7, and the law of total expectation, we obtain
[[a 72w + 1) E [11 + ((2w + 1) Pa
Pea)
E
n 11 +1
1
n.,211
nyg
72
27

---

+ zE |1 [|(b-1-((((+t))) \
+ pb
1 | (htt1= ()((t(t))1?
=E [E((tt\)>] + 7(2w + 1) E |19
-h-1111 ||]]
11 + 7((2w + 1) Pa
Pau
E
1
12
96
h
Pa
nepā
71
+ + Ep. | /f(x*+)))
[|]]
+ +pE Ep. n
|nst
f1((
S E f(x²) 2/2 ||
1
4
||al|1
x²1l
+ y 11/1
v vf(x'')
2 2
+ 72w + 1/ ||00* - -191(²] + 71(2 + P)
Paa)
1
Σ
n
l1at n|ll?
Pa
npp
n2
42w (2w 1)
F. 2T.2 ||aft1 - ==11 + 2b2
1
n
|| - () )?)
npa
n1 i=1
2 (Pa-
Pan) I²
|| - x²21 $1
26 (Pa
Paa)
Σ | - V)(('')) + +11 (1-b) () V)(2))12
+ sE
+
nºp2
2(1 Pa)
2 |22t1 - 10112= + (2b2(1 Pa)
ト/ n Σ 1 - v5(OO111)
+ pم
+ (1 - b)3
Pa
After rearranging the terms, we get
E [[(]tt]]]
72w + 1) E
|100t1- -211²] + 7(2 + 1) Pa
Paa)
E
Σ 1
++1 1 2
Pa
ny²
+ +EE |115 vf(( (( ||²]]
+ pE
1 n
|
S <E[[(a)]] E [|V=((=')1
72w + +12
[|0a - n 11'""]] 7(22 + 1) Pa Psa)
1
Σ
11ot - nill"
Pa
npa
17. 1=1
L
8yw (2w + 1) 1.2
2 (Pa- Pma) 1.2
2(1 P.2
[| -20 201]"]
27
2
np²
10
npp
p
Pa
+ (7 + v(1 - -6)2) E |1'' 11''-vi' -V(xt)))
+ 886 n2 + 1) + V
2b² (p. - Paa)
22b2 - Pa)
+ (1 +(1-6)²)
1 Σ l1n - v((CO))1
+ pp.
E
np²
Pn
By taking v= = T. one can show that (7 + v(1 - b))2 S U, and
E. [[
72w + 1) E. (1o+t-n+2101 + 7(2 + Pa-
Paa
F.
Σ
n
|0 ++1
n2t2112
Pa
np?
EE [|N-t1 11 <
+
1 n
|ntt1 - V V
< <E[f(r'] - 33 ||0
72w + 1) E [11s - -1a1ps + 7(2w + 1) Paa)
Σ l1 - n,!1?3
Pa
npp
n
28

---

1
L
8yw (2w + 1)
2y (pa Pea)
2(1 Pa)
|||--1 x011"
27
2
npp
bni2
p
Pa
2
E
[1''-v5(z') [(x)t)1
b
(2w + 1)
2yb (pa Pua)
(26² Pa)
+ (1 (1- b)²) F: Σ
n
| v163911
+
+
+ p
npp
np?
Pa
Note that b
Pr_ thus
p-p;
86 + 1)
2yb (pa Pea)
22 (12(1-1d) + (1 (1-b))) -b)²)
+
npp
mpp
Ph
812 y0 (2w + 1) 2yb (Pa Paa)
+ p b))
np?
np?
And if we take p (2
+ 2
then
"pd
862 rw (2w + 1) +
+ (1(1-b) 1) s p. 27b (Pa - Paa)
mp2
npp
and
E [f
72w + 1) E 11
1411"] + 7(2w + 1) Pa
Pan
E
n
|1 +1
h b4+211 11 3
Pa
np²
E [110t2 v ( |1]
(2b + 1) 27 (Pa Paa)
n
| V/i(ott2)11
E
npp
np?
<E <E(((t)] -3 ||vf(='))*
$
72w + 1) E [|oo* - nº|19] + 7((2 + P1 - Pea
Σ
11 - ntll?
+
Pa
npp
n2
1=1
L
8yw (2w + 1) 2
27 (Pa- Pea 2
2r 2
np?
bnp?
(2w
+ 1)(1 P.2
4y (Pa - Pea) (1 P.2
E
|1 - 20113]]
npp
np2
FE [11' [11''= [(("")11)
+ (2w +1)
24 (pa Paa)
| v
+
Tpp m
npp
n
Let us simplify the last inequality. First, note that
16b + 1)(1 - T.2
12 + 1)T.
npa
np?
due to b < Pa- Second,
27 (Pa Paa) L
47 (Pa Paa) I
bnp
np
due to b 2 8. All in all, we have
[[( 72w + 1)
E. [1g -
1o--1~-41pp 1+111²]- + 7(22 + 1) Pa
Pan
F.
n
|0 ++
h 1
nyp
FE [| (1nt--/(64421111 + (26 + 1)
27 (pa Paa)
E
np2
np2
29

---

S [B[((e)] - 2 [|
$
72w + 1 [als - - 2((2w + P) Paa)
11st n1ll?
mpp
L
247w (2w + 1) 2
8y (Pa Paa) i
E |
x² [1]
27
2
mpp
npn
+
E - +
(Stru)22 + 1)
mpp npp
27 (Pa Paa))
|
mp3
n2
Using Lemma and the assumption about 7, we get
[[((x(t)] 72w + 1) E 1190+111441p + 7(2w
1) Pa
Pau
E
n
|1
h.t110 11
Pa
np?
71
F ||, (
(Sbrwu2w +1)
27 (pa Pua)
F
|ngt
V/i(o(t))11 1
npp
nph
$ E [s((tt]] 1 | }|
72w + 11 F. [ll1 - ]1]]"]] + ((2 + 1) - Paa) E
11 - -nll??
Pa
npp
+
E |1 {()')\)) + (00++++(0))))0) (Sbry(2w + 1)
1 reph
2x (pa - Pea)
E
l1as
v
It is left to apply Lemma 3 with
= (2w + 1)
[100 [ --01 + ((2w + 1)pa - -Paa)
-19f - A
Pa
npà
n2
1=1
+
+ (8bw(2w + 1) (
+ (pa - Pua)
E
1
Σ | - v
np?
nph
n
to conclude the proof.
E.4 Proof for DASHA-PP-PAGE
Let us denote
b Peuge
K1 VSi -VS((')
(n) {i(")))
k = Σ (VSis(a(t)) -v)((a))
B
jel:
MC
+
1
M
hh node is participating, otherwise,
P.
hhf + p LM
hh node is participating, otherwise,
h
h/!
M+1 i h641 and h+t1= == 7i
1 E
1 Note, that
with probability Ppage
h++1=
(h541
with probability Ppuge
30

---

Lemma 8. Suppose that Assumptions 3, 4, and hold. For h and Kt#! from Algorithm (DASHA-PP-PAGE) we have
1.
E
E
Pauee
|
V (1(]]+
2 (pa
Peal
I
(1
Ppage L
| =011
+
npz
1p
(Pa-
11 V.f((=')11* Pan) 6²
(1-_ Ppage
2 (1 Ppnnee) ) (
+
+
Ppage
1i2 12 P.prr
2.
[l V (z ||]
En
Eyg.
E B
2
Pa) L
(1 Ppoge) Lmax
| 2²11
Pa B
+
2 (1 Pa) 62
+ Pouge (1
2
+ (1 Pouge)
V.fi(a))12, |
|
Wi [n].
PaPpage
Ppage
3.
EB
E Eppe
||,.
11]]
2L
(1 Ppage
max
||
x 2011
11 - V/(("))1 vi [ 26
Ppage
Proof. First, prove the first inequality of the theorem:
EB
[En, |mno
[|nst1
[xxx'+ )|
Ep. ||Ast1 vf +1 + (1 Ppage EB Ep, [1 vf(++t))|
Ppage EB
Using
Eg Ep. [M
b
=paht + (x((+t1) - v.f((t))
(h² Vf((z')) + (1 -pa)h!
Ppage
hτ + vf(+++)) vf((z')
(hi (
Ppage
and
Ep
EE, [h4t1]]
-pal + E
( - +1-pp))l
B
jEL
hf Vi((att)) v(((d)
we obtain
Eg Ep.
E Egpner
|11 vf(a
(16)
Ppage Ep, || Ep, [1]+ + (1 Prage En Ex. [1 E Epp [M5 [[]
31

---

Prage p
[
vf(x++1)|
+ (1 Ppage)
EB Epp [h2+1]]
vf(atti) }²
-Ppage Ey,
||1ft11 Taft-EEp BB, [ 11?] + -paage 1B
Ep. || EB
[E 112 [
[11]]
Ppago
1 b (1 Ppess)
111e (PPppp)))
vf(z')12
(24)
Ppage
Next, we consider Ey,,
|| Ep.. [n
We can use Lemma 1 with = hn and = k
obtain
11tt - Ey. [1st_]11]]
Ey.
1
| - 1,,1111
Pa Psa
|
12 P2 i=1
n n2p2
n
Pa
Paa p²
vf(( vf((x')
(hº v.fi(='1))
Ppage
(15) 2 (Pa- Paa)
+ (pa- Pan) b²
[ Vf((=))]²=
1hg Vf((=')]2
n²pp
n² 2 p
From Assumption 3, we have
Ep.
||4 ++ - Ep. [11 |1
2 (pa Pea) 2
|| | x2112 n² n2p2.fuuge
(Pa
Paa) 6²
Σ 1 V
(25)
npk
Now, we prove the bound for EB Ep [|lnst EB Bp, [1s
[15t1111]]]
[]]
Considering that mini-
batches in the algorithm independent, can use Lemma with hς and ss A to obtain
FB
|1
Fg FP...
[n
[12
[]]""]]]]]]"""""
P2
1
Eg
Eg
2
Pa Paa
Σ
Eg [M1,2]]
n 2
Pa
n pp
1
1
EB
V
(Vi((((t1) - - -v+(==+))))(((()))
n Pa
B
i=1
jEN
Ph Pan
V Vii(I' VA(Tt1)1
n 12
1=1
En
([ -((s(+') - -VVS(ttt)) - v)((a'))]
p B
1=1
JEL
Pn Pan
Vii(a'tt) VA(TN)1
n² n2
(VSes(ott1) Vib(2t)) -V -
n2p.Bm
Pa Paa
( Vf(221112
n² 2
1
V - (z +
Pa Pm
vf((+++)- - v.((++))1
n1 Bm
n²p2
32

---

Next, we use Assumptions 3 and 4 to get
L2 1max rep
(Pa - Pea) D=
EB Ep.
F.B E.g. I12 "]1"]]]]
|| - =dl1?
(26)
np²
Applying (25) and (26) into (24), we get
Ep
Ep.
||
(x(x+t)) >| 11]
2 (pa=
Peul I
|| 1,'t1=2'11 x2'1/
2 (Pa- Pua) b² n
| V
$ Ppage
np=
n² Pp
1 max np&B
(Do Pas) 1.2
+
(1 Ppuge)
+
|| 2012
np?
b
Ppago
1
+ (1 Ppage)
1 -V(-)())'11"
Ppage
2 (Pa
Poa)
2
(1 - Ppage) Imax
||a -x/1
x'l1
npp
ripa B
2 (ya- Paa) 62
Prage (1-2)
b 2
+ (1 Prugee ) 1 Vs("")]1?
||4 (x((2=))
n² Pppge
Ppuge
The proof of the second inequality almost repeats the previous one:
EB
Ep,
Eppne
E
||,tt1
||1 Vii ||]]] + (1 Prage En By.
[1,,21 - V[i(a'+)) [|]]
-Ppage En
Exp
(16)
| - F. [Pp, [M |1]]]] []]] + (1 Prage) F.13
FPpp. [|11522 En [Fp,, [M []]]
Ppage Fiss
F.g
Ppage
EE Epp
[n4,t1]] V ff( || + (1 Poage) ) || [Eps
[ntt']]
Vf((att))] ?
-Ppage
EB
Eps
|1
EB [Ep. [1 ']] [|]] + (1 Ppago )B
Eps || EB [Ep, [1 []]
b
+ Pruge
1
+ (1 - Prose) || - (
(27)
Ppage
Let us consider Es
Epp [1
EB EL [
Eg
1+1 1,1
-EB
Epp.
pb
Ey.
|1 ++1 - EE [Ep.
M/ + k5tt h + (1((xtt1) - V/i(o
b.
(11) v)((z'))) 1
Pa
Ppage
b
+ (1 pa))
1/ - h - -
(16 1n6-V/i (V(-v((()))
Prage
(1 - 2a)
12 (hi vf((att)
(l( vf((x')
Pa
Pruge
V - v.fi(=*) b
+ (1 Pa)
(h) v((((())
Ppage
12
1 1- Pa
Vi( Vf((z')
(hL - vf(((z'))
Pa
Ppage
33

---

Considering (15) and Assumption 3, we obtain
Eg Ep.
||
EB Ep. [n [
2 (1 Pa) L2
|1 - w21 2(1 Da) 1 Vii(x')]1
(28)
Ps
PuPPage
Ep. |1, -EB Ep. [4, |1]11]]
Next, we obtain the bound for EB
EB
Fr..
|, - F.B [Eg, [1]]]]11]]]]]]
1 k (ht + V)i(=!t))- -V(())))
= PBEB
h +
Pa
[Ins - (M V/((o(t))- {((
+ (1 - -Pa)EE
(V.(((('))) - |
| kot1 1.2
= P.
+ (1 Pb) (x - V
(6 1
En || - (Vi(( - vf((+t)) (1- pa)² [fi( - V=((2))
Pa
Pa
+ (1 Pa) (Vi(att)) VS((a'1
EB || - (VS((t(t)) v)(('')
1 Pa
[f((at+)) - v
Pa
Pa
1 EB
||K4 - (V.1(1 v((+')
(1 -1-18 Pa) L
|| - x111?
(29)
Pa
P/
where we used Assumption 3. By plugging (28) and (29) into (27), we get
Emrre [11,t22 Vf(la ||]|
EB
Ep.
(2 - Pa) L?
|| - 2011 2(1 pn) PaPPago
11M4 - V)(
< Ppage
Pa
- EB || - (Vf((z(t2) -f((()))
(1 - Pa) L3
|0041_xx'0 22133)
+ (1 Ppago)
Pa
Pa
(1
+ Ppago
+ (1 Ppage)
| -
Ppage
2 (1 Paa)a) L
1,,2 11112
Prage
E,
[| (V
Pa
Ps
+ 2 (1 - (1-pa) b²
(1
2
+ (1 Ppage) ) | [
+ Prage
PaPpuge
Pruge
From the independence of elements in the mini-batch, we obtain
Ep
Ep.
||
||
2 2(1 Pa) L ||, - 1²112
+
Prage
En
Σ ((ottt)--/vtete - (V/((((+1) v\((a())
Pa
B
JEL
(1 Pw) B2
b
+
+ Ppage
1
+ (1 Ponge)
||A! - v,((=')11
PaPpage
Ppage
34

---

2(1 Pa) Pa) L2
|1/ x2112
Prage
En
Σ (VV - -V/s((+))))((( (V/((ott)) v,((z'))]
Pa
Pa B2
JEL
2 (1 Pa) b²
b
Ppago
1
+ (1 Prees) |In v(((='))1
PaPpage
Ppage
2 2(1 Pa) 1
|| x²
x²112
Pruge
(Vii(attt)) - -V(((tt)))))((( - (VIi(att))- - -VA(()))
Pa
mpp.B. B
3=1
2 (1 Pa) 62
b
Prage) ||ns V.A((''))
+
+ Pruge
PuPpage
Ppuge
2 Pa) I.2
11000 - x x2112=
- Ppage
[is( {is(("')11
Pu
mp, B
(1 Pa) 6²
1
b
+ (1 - Prese)
||n - v(((2))1
+ Prage
PuPrage
Ppage
(1 Pa) L?
Pruge)
)
mimax
1 x²1l ||
+
Pa
PaB
2 (1 Pa) B2
(1-
b
+
+ Pruge
+ (1
Poage)
||nt v.((='))1?
PaPpage
Ppage
where we used Assumption 4. Finally, we prove the last inequality:
EB Eppue
||,]
b Prage
[fi(
(14 v fi(x'')
-Ppage
127
+ (1 Ppage EB Dp
1
-
B
SEL
(16)
(f((t(11) - vf((z')
b (N: 18-vAt ((-x)(()'))
Ppage
Ppago
11 Σ
+ (1 Ppage Eg
- -Vfs(tt)--ii((())) - (Vf((t+t))
((V((==)))(((((+)))) -
B
JE
+ (1 Ppage)
vi((a'))1?
(15)
262
- + - (i(
2 2Paage
Ppage
+ (1 - Prage >
1 B
Σ -((((())))) (Vi((ttt)) -
JEL
(1 Mpage) |[/[((tt)) V/
212
2
[/*(t++)> V/((0')112
|| V/((t')
Ppage
35

---

+ (1 Prage) EB
B
Σ
-
- - v(((t))
(Vii(e't))
Using the independence of elements in the mini-batch, we have
EB
Pypue
|M!+111 []]]
25
2 fi((t+1) vf((2')1 +
||n - (f((2')11
Ppage
Ppuge Eg
11 (VV - -V(((()) -
-
B²
jE!!
212
|| -op-v(((>']
Ppage
Ppage
[V V(ss(a'))
Bm
5 2 V Vi(x - v(((z')1 + 21
|| - V
Ppage
+
Prage
[ig((att)
Bm
It it left to consider Assumptions 3 and 4 to get
|| [[]
EB
Eywes
< 2 + (1 Ppage max
262 Ppage
- -2-1 +
|1n.
B
Theorem 3. Suppose that Assumptions 1, 2, 3, 4, 7, and 8 hold. Let us take probability Ppage (0, 1].
2w+1 b Paoye
2 pb
18w + 1) up?
1.2 (1 Ppogy 22
16
Psa ((1
8.2 + (1 Prnge L2 max
)
5
1++
max
B
P.
and 9f hº Vf((z9) for all i [n] in Algorithm 2A0
(DASHA-PP-PAGG then |V{(>>>|
7T
Proof. Let us fix constants p [0, xc) that we will define later. Considering Lemma 6, Lemma 8, and the law total expectation, we obtain
[[(] 7(2 + 1)
E.
[|1 - 144119] + 7((w + 1) Pa
Pan
F.
n
11 +1 n n
np2
+ +E || V ((( 11]
+ +pE
|1 4+ V (21
n7
< E [(xt) - -/ || 2(1
(+)
L
||0
- x²' 11
+ 7 ||A1 {(())))
27
2
72w + 12 [1os - -nalpp
((2w + 1) Paa)
Σ l1 - 11113
Pa
mpp
36

---

(2w 1)
1 n
E
k
11
71
+EE |16--1 v (f((=*1)\11
||
+ +pE
| lhitl
\/(
n
E f(0')) - //2 ||
(5/)
L
||
+ y |1 v ff((1))
72w + 1)
[119* |19*-- -11
?((2w + 1)
Pao)
n2 Σ l1gt - n3!1?
Pa
npp
(2w
1) E
n Σ
EB
Eppey
k 11
np?
11
vE
EB
Expeae
||
V 1
p,
+ pE
EB
Ep
E
Eprexs
|1 v (1
n i=1
S E
f(x²)
7 ||
2 || - 2²1 + y 1| {
I.)
2
27
72w + 12 [110* - -1911²]
722 + 1) pa - Paa)
Σ 11at - holl?
npă
4r 2w +1)
E {
{(2Te 22² +
(1 Ppage max
||
2 211
+ 26 1
Σ
| - ff(("))1
np2
B
Ppage n2 im1
22(p) Pea) 1.2
(1 Ppuge) ) max
+ vE
+
|| - 101
np?
B
+ (pa
Pau ) 122
h V vf((a')11 + Ppage
1
b
+ (1 Pange)
|11 (
n2 P2 Ppage
Ppage
1=1
2 (1 pa) 2
Pruge Im
+ pE
| - =121?
Pa
PaB
+
2
pb) 12
+
Ppage
2
+ (1 Ppago)
1
Σ
| - VS((a))1?)
PaPpage
Ppage
n i=1
After rearranging the terms, we get
E [f(((t))] 72w + 1) E
1104+1n4441p + 7(22 + 1) Pa
Pau
E
1
19 +1
11 1
Pa
1
+ +vE |115-1 V /f
+ +pE
|1
ve(
n
$ [f[((()] -
2 E ||V](a'))1
7(2 + 1) E [|g' - -1|1'] + 7(2w + 1) Pa Pea)
l1 - h!ll²
npp
L
47w + 1)
2Î2 + (1 Ppuge] I 2
27 2
np?
B
37

---

2 (pa-
Pea) I
(1
Ppage L L
( 2 Pa) I
(1
Ppage L L
Eb || =x'1"
1
p
npg
np B
Pa
Pa
7 +
Prage
1
b
2
+ (1 Ppage)
E | (1n-~v/(a")) (
Prage
81/ yw (2w + 1)
2v (Pa Peal bs
aPP.Paage
Ppge
2 21 Pa)
2 + (1 Ppage)
+ p
+ Ppage
1
E
| vf(e'')
PaPpags
Ppage
Due to b
Pa
Ppage: one can show that
Ppago
(1
b Ppuce
2
+ (1 Prase)
s b. Thus,
2-pr
take
7, then
Ppage (1
b
2
+ (1 Ppese) )) 5 (1) - =v,
7 +
Ppage
therefore
E [(
7/2 1)
E -11 -1 + 7(22 + 1)Pa Pa
Paa
E
11 ++ 1,t110
Pa
np²
E |11 - vf (f(
1 +pE
b
n
[[(() F [|
7(w 1)
[|90* - n-]la]
7((2 + 1)
Paa)
1
11 hill?
Pa
npp
n2
L
42w + +1
(1 Ppage D
2T.2
2y
2
np
(Pa
2
Paa)
(1
Prage) L'maxx
2 211
Pa) i2
(1
Ppage max
|| x" [1"]
np?
np, 1
Pa
pa B
E |112 F(x''')
862 (ww (2w + 1)
+ 27 (pa Pea)
npp
n.ph
2 (111 + Ppage
2
n
+
+ (1 Prage)
| V
PaPpage
Ppage
n
Next, with the choice of b PuuePe 2-9a we ensure that
2 Pa) 1/
Ppage (1-
b
(1 Prage)
51 11-b -1-b.
PaPrage
Ppage
If we take p
(2w+(2
+ 27(p.- -pa). then Ppue
np Pooe
8b2 + 1) 2 (Pa - Pau) b
(1 - Pa) 62 + Ppage
11
+ Proge) )) s
+p
upgppuge
mp2p Prage
PaPpage
Prage
therefore
[[(x+t))] 72w + 1) 11 + 1(2w + 1) Pa Pea
n 11 +1 11, n2t2113
nyz
38

---

E |1 [
(bby + +1) 27 (Pa Pea)
n
E
Tepi
E [[[(x))]] - E ||v
2
72w + 12 ||9* - h1 n011²] + 7((2w + 1) Pa
Paa
l1st - hill?
nap
n
L
(2w +1)
2î² + (1 Peuge) m
27
2
np?
B
?
2
Pan
1?2 +
(1 - Ppage Linxx
bripa
Pa
B
187y (2w + 1)
27
Pu
Pa
2 (1-p)
Pa) 1.2 (1
Pruge I max
[1lott3- - 1111
Ppgg
np?
B
EE [11-- V(('))] + 8br (2w +1
2x (Pa Pas)
E
| -
mp2 Prage
Let us simplify the inequality. First, due to b
Praeee
we have
2
(2 22111 Pau
22 (1 Ppage L
4Y
(11-
Pau
2 +
(1
Ppage ) max
Imp
Pa
B
nup Ppage
Pa
B
Second, due to b S PaPpage and Paa S P2. we get
(2w + 1) + Ppgge
Pra 27
Ps
2 21 - +
Ppage)
T
max
Ppgee
B
(2w +
27
Pio
(2 (2(11=
Pea 1.2
(1
Ppage
I
maax
mp3
Pruge
Pa
B
16 (2w
+ 1)
Pau
2 +
(1 Ppage I max
np?
Pa
B
4y
Pai
Pe
Pan
2 +
(1
Ppage L
Pa
B
16 (2w + 1)
(1 Ppage L
2 +
B
47
((1
Pan
1.2 +
(1 - Ppage L2
mmax
npp Tpp2 Pruge
Pa
B
Combining all bounds together, obtain the following simplified inequality:
7(2 1) F. ||1 1--t--n+1g -n421]] 7((2w + 1) Pa Pea
E.
[[[(att)]]
F.
9 1+1
h5
11?
Pa
np2
E || - [
(Str +
27 (p. Pau)
E
|ntt2
v/((ott1))1
Douge
< <E[f(x') 3 [|V
72w + 1)
|111 - -1]1p]
7(2 + 1) Paa)
l1 n!l??
np2
T
39

---

L
24 2ww + +)
(1 Ppage L
2
27
Tip2
87
(11
(1-1)
Pan
7?2
(1 - Prage) L max
B
[1aet1
- x
11p2Ppuge
Pa
13
E ||n V
(2 1)
2 (Pa Pea)
E
1
1
v((
b
mppPPage
np Ppage
Using Lemma 4 and the assumption about 7, we get
E [[(( + 7(2w + 1) E
[ - 11 + 7((w + 1+) Pa
Pau
E
110 ++1
n,4
nph
+ 1 |1 - [ 11 + (2 +
2 (pa Paa)
E
12p2 Prage
< [[((xz)] E ||
2
E 7(2w + r(2 +11 |6|1* - -111 7((2 + P) Peal
11st - -h?l?
Ps
npp2
E 111-' V [(=)))] + (2w 1)
2n (Pa Pas)
E
||
b
npp2Paas
Ppage
It is left to apply Lemma 3 with
(2w + 1)
119 - n² 1013] + ((2w 1) Pa
Paa)
E
12
11
hill"
Pa
np?
i=1
+ ( + (8lb (2w + 1)
(pa Pan)
1
+
F>
| - V
Ppprpaage
PPa.Ppage
12
conclude the proof.
Corollary 1. Let the assumptions from Theorem 3 hold and Prage needs
B/(m+ B). Then DASHA-PP-PAGE
Ao
[
Linax
m
1
I
Liax
T O
L
+
(10)
Payn
VB
Pa
B
B
communication rounds to get an s-solution and the expected number of gradient calculations per node equals O (m + BT).
Proof. In the view of Theorem 3, is enough to do
=
+
W2
7,2 (1
Ppage 2
+
((1
Pea
1.2
(1
Ppage) L2
max
np
B
Ppp2P
B
steps to get e-solution. Using the choice of Pinega and the definition of 1,,,, we can get (10).
Note that the expected number of gradients calculations at each communication round equals Pmega M
(1 - Pmoga) ) B
2m
< 2B.
m++
2 and we
Corollary 2. Suppose that assumptions of Corollary hold, S min
mAX
Pa
12
use the unbiased compressor RandK with K 2 (Bd/ Then the communication complexity of
12 $1f p. then
13 22
+000
40

---

Algorithim is O (d+ And and the expected number of gradient calculations per node equals
0mm= + Luax A
PoEyn
Proof. The communication complexity equals
O KT) o
od+
d+
Ao
KL +
w (I. [
Lmax VB
+
m
Lp
+
Lmax
)1)
E
Payni
VB
B
Since B <
Laage Dx 1.2
we have
1np
1
+
Limxx I 2lemas and
vB
o (d + KT) = 0
d+
Ao
KL + K
w
L
Tamax
+ K
m Txmax
Payn
VB
Pa
B
Note that K = 0
Bd
0
d
d and w + 1 = K
due to Theorem 6, thus
vm
Payn
Ao
d
L d
(I+
Lmax
d
O + KT)
O
d
maxx
Payn
Payn
VB
Pav
Imaxxnnd
o
d
PLEVT
Using the same reasoning, the expected number of gradient calculations per node equals
O (m BT)
o
m
+
Ao
BL
Payn
W
T.+
Lmax
VB
n
B
L
Limxx
0
m
+
D
BL +
d
i
Limax
+
B
m
Lmax
Kpayn
VB
Pa
n
B
0
+
Ao
1
m
m
(I+
Liaa
+
1
m
Imax
Pa
Payn
Pa
Lmaxx Dov
0
+
P&t /
E,5
Proof for DASHA-PP-FINITE-MRR
Lemma 9. Suppose that Assumptions 3, 4, and 8 hold. For h high and kR+1 from Algorithm 1 (DANHA-P-- we have
1.
EB
Ep,
|| - (f(a+t1))1]
2L2 max +
2 (Pa-
Pao) Z2
1,2 - =11?
B
mpa
2 (pa Poa) b²
n
26
m
+
Σ -V-(a))11
11
vis(xt)11
n²p2z
p2 Bm ==1 j=1
1=1
+ (1 b)2 111 21
2.
Em. || -V [|]]
En
2T2
2(1 1/)
||
2012
+
PaB
Pa
262
m
|| - Vfo((()))
(2(1-pa)) pa)
+ (1 (1--)) | VA(T))1,
wi In].
Pr Dm
Pa
41

---

3.
EB
E
[11 1+1
V
fag( ||]
figl
2
1
P.
max
I
m
|/ x²11
P3
2
6²
+ (1 6)2
|1n - Vfo(a)))?
vie [n]. Vj [m].
P.
4.
||4--111
F.B
2
+ +21
| - 2012
B
2h
m
Σ
hhi - Vffg(z'))1 + 26² | 1 (N--(((''))?
Vi [n].
Bm
Proof. We start by proving the first inequality. Note that
En
Ep,
[h]tt]
Pa
h
EB
[R(+1]]
(1-bah
Pa
B m
(Vig(z - (f(((=") -b V)i((z')) + (1-B)..
) 0 m
h
B
+ (1 b) (M: V)((2'))
thus
Pp || - ( ||
En
E [11441 Es [Ep, [ 11 (1- 6)3 1h- vf(z"||?
Eg
We use Lemma
with ri = h and s; + obtain
Eg
Ep.
|
v5(x ||
Eg
||as - Eg [M4 [1]]
Pa Pmu
Eg
[K. [M="||]* |1
p2pp i=1
n 2 P
1=1
+ (1 - b)2 11' 22
n
m
Σ EB
Σ h
-
- bb v)((a'))) -bb(-vv(((a'))
n2pp i=1
+ Pa Pm Σ (i - V/i('') b (W) {)(tt))]1
n2 p2
+ (1 6)2² n -
Next, again use Lemma 1 with = Vfs(ott)) - -((,--V(()())
B(B-1) B and Pan mmm-1))
Pa
EB Ep. || (a 11
42

---

m- B
m
V -V/(((")))) b(g V(((E))))))
11 Pa
Bm(m- 1)
Pa Pau
Vf(( - Vf((=') - - -Vf(''')'' |
p² im1
+ (1 - b)2 || - V
1
[iig(((1) - Vfa((z') b (1/) [f)((a))]
n² p2 Bm
n
+ Pa Paa
V V - -n; vf((tt)) |
n²p2 i=1
+ (1 - b)2 v
(15)
2
2b
| (fr(('))1
n² Bmn
p12pBBB Bm
j=1
2 (Pa- Paa)) n² p²p22
(pa Paa) 6²
|M - [)((+')11
n² n²p²
+ (1- b)2 | (z''))
Due to Assumptions 3 and 4, we have
Eg
Epp
|| )1 ||
2L
2 (Pa
Paa) 1²2
| - =912
x
+
Bp
nph
+ 2 (Pa Paa) b²
n
26
n
V fez (x))))
n²p2
p22pa Bm
i= 1=
+ +11 b)2
||
(f=)))
Let us get the bound for the second inequality:
Eg
Epp
||a_t1
[[((ott)))]]]
(16)
|nn+1 (Vi((''t)) + +1- D)(45 (1000-vA6a VA(+)) [*]]
EB
Epp
(1
b)2 | - V/(at))1
|nt + 1 ktt1 (VS, + (1- -V())V)(())))
P&EB
vi(++)))
Pa
+ (1 Pa) ||A (V + (1 ()( V((+\)))
+ (1 2)2 M - V/(
(16)
F.B
16+1 - EB [M. [=]""
Pa
+ 1 Pa
|| V (1) - vf((=') - b(h) - (f()''))
Pn
+ (1 6)2 || -VA(<>111
Let us use Lemma 1 with r; = 0, 8; = Vi( - Vis((z - b (1i5 V(is(z')) Pa
m
B
and
B(B-1). m1)
Paa
EB Ep.
||nEt1 - 1|1
43

---

B m
Vlis(ttt)) -
Pa
Bm(m- 1)
Pa
V - -V((==)))--((())>>)) - 6(0 v
Pa
(1
b)2
1
Viig(e't) - b (hi - Vfa((())1
Pa
Bm
- Pa
V VA(a9) AC - -
Pa
+ (1 b)2 ||n! - V
(15)
2 m
Via((''t -VSo(+))] 2(1- -Pa)
PaBm
Pa
26
Σ |11 - (fu(zz)) + 2 - pa) b²
m
+ (1 - 0)²) 11- - v)((z')
Pa PaBm 1=1
Pa
2T. maax
2(1 Pa)l?) ||a5t] -xt11
BaB
Pa
26²
Σ |1nb - (1) + (2 - pa) j=1
+ +1 (1- bj² |1 - vi(et)]]
Pa PaBm
Pa
where
we
used Assumptions 3 and 4.
We
continue the proof by considering
EB
Ep.
|1tt1
fz [[]]
EB
Ep.
[1411
V (zr(t
(16)
EB
Ep.
||15t1 - (Vi(((+*+)) +1 - [[](())]]
+ (1
b)² 2 |1/ - V/1(("')1
B&B
EB
Mig + m (Viis(o - Vi(((z - b (1/g -
- (V +111+ -b)( Viis(a")))
m
Bp
+ (1
PBB) ) |InE/ (Viv(a + (1- (1-b)(( - Vf(s("'))) 1²
m
+ (1 b)2 | - V/i0(a1)1
2
B.B
m
|[ - Vii((( - -bM, - Vir(('')11
B.B
m
B&B
Vitg(e Vir(a') -6hh {fb((())11
m
+ (1 b)² | Vig(a
p.B
m
[Vo((ott)) VSo(2= - BCh - Vig(E()))1
B
m
+ (1 6)2 |1اi/ V1
2 1
BB
(2(1-
2
BB
62
(15)
m
- -
(1 - 6)2 |1 - -fa((()))
2,13
B.
m
44

---

It is left to consider Assumption 4:
EB
Ep.
||
Vig(x''
[11]]
2
1
P.
L
max
[2 (2(1-
P.
b²
m
||, - x. 1112 +
(1 - b)2 1 - (ios(("))1
+
P.
m
Finally, we obtain the bound for the last inequality of the lemma:
|| [|a]
Eg
(16)
EB || EB [A] "11]
V vf((z)) - -(03))))(((3-(((((())
Using Lemma 1, we get
EB 114++11
m. B
V (1/ - V/i(a - b fig(')))
Bm(mm- - 1) 1=1
VVi(z(+)) V5((z') 601 V/(E')111
<
V fzy(x((1) -V(y))))))()))) - b 6 -
Bm
V (z+ Vb((2') 609 - VA(29)11
2
(zi((t(t1) (x)()(')1 2 + + - v.((+')11
Bm
21
|1nis Vis((*))|1 + 26 | - v/(x'11
Bm
2L2 max
+ 212
-
B
212 m
Vii((a"))' 2b2 1 v/(211)
Bm
where we used Assumptions 3 and 4.
Py B
Theorem 7. Suppose that Assumptions 2, 4, 7, and 8 hold. Let us take
Pa
b
2w+1
2
5 L +
12 +1) [ + B
12
72m
(11-2)
Paa
Ī2 +
2
max
T2p2
np2B
Pa
B
60 = N. = Va((a)) for all i E [n) and h: = (x) for all i E [n].j E [m] in Algorithm
(DASHA-PP- IDASHA-PP-INNITEMAR) then E [| |12]
20g 7
Proof. Let us fix constants v, p, d E [0, oo) that we will define later. Considering Lemma 6, Lemma 9, and the law of total expectation, obtain
[(x 72w 1) E
[10 1 - 1 + ((2w + Pa
Pea
7 11 +1
11 1,t211
E
nyz
72
45

---

zE | ------/(((+]]11) )
+ pp:
1 Σ |1
m
+ .
nmm ==1
E.
((x1) 2/2 ||
( 1 L
2 2 ||aft]
- 1²1
+ 7 1111" < (( 1
72w + 1) F. ||05* -
((2 + p) Paa) E
1 Σ l1st n0/17)
Pa
np?
4rw 2w 1)
1 n
E
m1a2
71
1
/E
|16-
+ مE
|1 (h - [/((e(t))))
+ +BE
| (
num j=1
E
(00') 7/2 ||
27 - ) ||a5t11 - =011
-/
+ 7/ || -V {((=))
72w + 1) E [100 [110-~11]] -+]1']
((( + 1) Ph Pan)
Σ l1lt n3s1s
Pa
4rw 2w
1)
E
EB
npa
EB
Ep,
|11tt1
V
(2x
1 12
+ pE.
EB
E.p.
| (
n
n
m
+
SE
EB
Epp.
| (is 2
7m
j=1
E
f(at)- 2/2 ||
1 L
||a|t1 -2'1 + y ||A² (f("))1
27
2
?2w + 1) E [||"* 1o-'-1ll'" -11]"]]
71(2w + 1) Pea)
11 h3ll?
Pa
npp
n
(2w + 1) nyzz
22
2b
m
26a
E
2222
||a0t1- - =11
| [1((=")))++ n
|
v
B
Bmn
1=
2.22
2 (pa- Pea) L²
| - x01l
ni,, B
np?
+
2 (pr-
Pau)) b2
Σ
h - Vf((a())1
+ n2pp Bm
2b
hhi - V fig(("))
n2pp
1=1
1=1 j=1
+ +(1 (116)) - V)((3)1))
46

---

22 max BaB
2(1- Pa)
+ pl
|| -0---=111 x'11
Pa
26
m
| V[o((=')) + (2 (2(1-Pa) ((11))))))) (1 (1-b)² - ΣΣソ | v (((
Pa
Bum
Pa
1=1
2
1
2.B
Imax
6E
|| - x011
P,B
+
2
1
B
m
b²
+ (1 b)2
ΣΣ i=
n m
M - V
P. B
mm
ExE
Due to b
m
mm we have
2- 2ats
2 2(11 (1
R. b²
+1 b)²
-1-b
p,
and
2 (1-Pa) b²
(1 (1- 6)2 s b.
Pa
Moreover, we consider that 1
PBB
< 1, therefore
E [ + 7(2 + 1)
E
-
1 + 7((w + 1) Pa
Pmu F
Σ
1
++1
11
1
np²
+ vE |
)1
+ +E
| (1
+ dE
|ott V)b(a=1>)1
nm 1= j=1
< E f(xt) - 7 ||(](at)])
(1) 1.) |1 - 212 + 1| vf(21)112
2
2 2
72w + 1)
E [11o* - -1lls]]
+ ?((2w + 1) - Pma)
1
l1ot - n!ll?
Pa
npp
n
iml
(2w +1)
[2Lmmxx B
2b
262
E
+ 28²² || - =211
|| Vfr(a+))1
n Σ | Vf(
npw
Bmn
1=
222 2
2 (Ps
Pea) Í
+ zE
| - -z011
npa
2 (pa Pmu) 1.2
212
12
Σ | -Vs(((((
My [ig((ot)12
+
n²p??
n² 12p.Bm
+ (1 - 1)2)) [V/1'''V[<>>]]''
[2L
2(1 P.2
+ pE
+
||
201
B.B
Pa
47

---

26
m
[hip ) + (1 -) b 1 V
Pa DaBm
j=1
2mL max
+ +
++1
x' || + (1 b) ΣΣ
PaB
j=1
After rearranging the terms, we get
E [f(
722 +
1)
E
+
7(22 + 1) Pa
Pmu
E
Σ
n
|
+1
no.
n5t111
Pa
np?
vE (00-1-
+ +p
n Σ
| [ 1|
.F
nm
<R F. [ ||
$
12w + +1)p
|||' - -1'1]]
7((2w + 1) Pa Psa)
1
l1
h&ll
Pa
npp
11
1
L
42 + +1)
(2L
+ +202
27
2
?pp
B
2T2
2 Puu) 1.2
2L
2(1 - p2)
2m I
P
E
|| 1 1o
11
nppBB B
np2
PaB
Pa
Pa
v (1 b)²) E |116" VVf(a'))
862 n2 (2w + +1
2v (p.- Pau) b²
72
+
+
+
E
v
np²
np3
71
y2w + 1)
2vb²
+
2pb2
+8 +811 (1-b)
E
1
1
Σ
m
np? B
BaB B
TUT
j=1
Thus, if we take y F. then y + + 11-b) 6)2² < and
[[
7(2 + 1)
E |10 |1a
7(2 + 1) Pa
Paa
E
Σ
n
|| +1
h
12t211
Pa
np?
+
E
||l (
+ pE
1
|ns
b
n
n m
+ 8E
|+ |1
num
j=l
E [f(x')]
7 EE ||(,(('))}
2
7(2 + 1) E [|g' - 10]1"]] + 7((2 + 1) Pa Pea)
11 - h!ll²
npp
T
L
47w (2w + +1) (222
+ +i.2
27
2
np?
B
48

---

27
24 (Pa
Poal I
2 max
2(1 Po)
2m L max
E || 10:--11-111 x²123)
+
bripB1
bnp
Pr
Pa
Pa B
E
[|1' [
812 ww (2w + 1) +
27 (Do Paa) )b b
+ p1 -
M
np3
nph
11 i=1
(W (2w + 1)
27b
2pb²
1
m Σ
n
+
+
+
+ 5(11 (1-b)
Mig
npp B
B
PaB
nm
j=1
Next, if we take p
27(24- then np2
npf
812 (2w +1
27 (Pa p b
+ p (11-b) 1) = P.
+
np?
np²
therefore
E.
[ + 722 + 1) F. |19 - 10 + 7((2 + Pa
11
Pea F.
1 ++1 11 11t
npp
+ E b
| \((t+\)))1
(2w + 1)
27 (Pa- Pan)
E
| - ]/(
npg
np2
|ot1 - V
+ +0E
nm
1= j=1
$ E [E(())
2 F ||
+
7(2 + +1) E [|o' - -1'11"] + ?((2 + 1)Pa - Pea)
E
1
l1 - n9ll?
Pa
np2
i=1
1
L
(2w 1)
22
max B
+ +P.
27
2
npp
27 T. max
2y (Pa Paa) T.2
(8ryw + 11
2 (pa Pas)) )
22 max BaB
2(1
Pa) Pa) 1.2
+
+
+
bnp,B
bnp?
npa
npp
Pa
2m Lunx
||alt|- - =01
E
PB B
+ E |115 - {((")))
b
8b7w (2w - 1) +
27 (pa - Pma)
1 Σ 11M- v
E
np2
npp
8ll (2w + 1)
27b
1663)m0(2
1)
4b2 (pa - Pam)
+
+ 5 (1 b)
F.
| - (is((tt))
np² B
B
n B
nBp
nm
1=1
Due to S Pa and PM-Pa < 1, we have
862 (2w + 1) +
27b
16b yob (2w +
462.y (Pa Pna)
+
+
np2 B
np. B
np B
n nBpa2
812 8022 (2w + 1)
2-bb
161
(2w + 1)
4-b
+
npp B
np B
np B
np,B
49

---

2462 yo +
67b
npp B
nipa B
Let us take
8
24w9
+
6n np,
Thus
np
86 s02 2w + 1)
2-b
16b (2w + 1) 452n (pa
Paa)
5 -b)
np?
np,
npp
nBp²
and
E
[[((tt))]]
72w 1)
111 7(22w + Pa
Pmn
E.
1 +1
no
11tt112
Pa
npp
E
|16 v (2(
(2r +
2y (Pa Paa)
- v.((cott))
E
npp
nph
(2w
+ 11
by
+
E
sag
fe5(
npg21 B
vpp
mm
E [[(x')] 2 ( [|
72w + +1)
||99* - -111"
7((2w + 1) 1) a Paa)
11 h&ll?
Pa
npp
n
1
L
42 + 11
m2
2-
np²
B
2
2y (Pa
Paa) L
8by (2w + +1)
27 (p. Paa)
22 max
2(1 Pa P2)
+
+
bripaB
bnp
npp
Pr
Pa
24bryw(uu
+ 1)
6y
2m 2mL2 max
|||ott!-=*]]
np²
np,BB
Ps B
Y E
|lII f(()))1
80y
2- (Pa
Poa)
E
1 n
|
V
np²
np?
n2
(2w + 11
By
E
n
m
M
(ing(()111
B
B
nmm
Let us simplify the term near E
|10t1
x21(?
Due to b S Pa.
Pa-Po
S 1, and
Pa 1 1, we
Pr
have
42w +
222
27.2
np?
B
2-
27 (pn Pma) 1.2
+
brp,B33
bnp2
(2w (2w + 1)
2 (pa
Pam)
212
2(1 P.?
+
npp
np²
B.B
Pa
24bryw (2w
+1)
67
2mL2
+
B
rip B
P.B
12
+ 1)
2222
2
+
npp
B
50

---

GyLmmux
By (Pa Paa) I
+
1rip113
24bry (2w +1
67
2m max
+
n
np
P.
Considering that S B
and
2
BB
we obtain
m
2m
47w + +1
22
+202
npp
B
2- 2
27 (p Paa) I
+
brep,
bnp?
8by (2w + +1 mpp
27 (Pa Pan))
2
2(1 D2)
+
riph
BaB
Pa
24bryw (2w 1)
By
2mI
mpp B
n
PaB
3 (2w + 1)
221
18 L
By (Pa Pua) 1.2
2Ī.2
+
npp
B
bnpaB
bnp?
36 (2w + 1)
2
max
36mmy L
12my (Pa Pea) I
2D
+
npp
B
Bno
All all, we have
[[
7(w 1)
E
119
h
11]
+ 7((w + Pa
Pun E
|1 h
np}
+ E |
Vf
(2w + 1) 2y (pa
Paa)
E
b
npp
np
iml
24try (2w + 1)
By
+
mp? 1np2
+
E
V (es(
B
np.B
B
nm
i=
j=1
[f(x*]] ] (V
E
72w + 1)
E |||s - --11" + 7((2w + Pa - Pea
l1 - holl
Pa
rup
L
36y 2w +1
22
+ 2Î²
36m, Dinax
12my (p. Paa) 1?
E || - =²113]
27
2
npp
B
npp B2
Bnp
E
[115 - {1( 11]
+
8by - 1)
27 (pa Pma)
1
v
+
E
npp
npp
22b
by
E
v
np? B
np..
B
Using Lemma 4 and the assumption about 7, we get
[[x 72w + 1), E
[110 - 1 ((2w + Pa Pea
n
|1 +1
11 n.t211
nyg
51

---

E |1 [
(2 + +1)
27 (Pa Peal
E
n
h
nip
np2
(2w
1)
by
n
m
+
E
V
(e
npf B
vepa B
mimm
E [B[[((]]] - 1 [|[
72w + 1 [611* 11s-- 111 7((w + 1)
Paa)
1 11
Σ
11 n!ll?
Pa
npp
+ E |11e (
(2y +1) 1) +
27 (Pa Pan)
E
||
- V
npp
npp
n
22tryw(2w + 1)
By
+
+
E
vig(==111
B B
Bpp.B.
nm
i=1
j=1
It is left apply Lemma 3 with
V
(2w + 1)
E
-1-1(]
((2w + 1) Pa
Pau
11 1
nyp
Pa
1=1
1 E
| (f(aa))1
+
8bw + 1)
(pa Pua)
V
+
npp
npp
n
(2w + 1)
6
7
+
E
|
npp B
B
num
to conclude the proof.
E.6 Proof for DASHA-PP-MVR
Let us denote
Lemma 10. Suppose that Assumptions 3, 5, and 8 hold. For hit and k5t1 from Algorithm (DASHA-PP-MVR) we have
1.
Ex
Epp
|| - [1(
2020z
2(1 6)
2 (pa Pea) Z²
1:0 - =01?
nip
n B
np3
+ (pa
Pru) b
| vf((z')] 2 + (1)) 110111-- {f(2")1
n²p2
==1
2.
|| Vsi(x ||r]
Em
262
(2(1 - 6)222 -2(1-b)L2 + 2(11 2(1-pp))
|| -291
+
BBB
P.B
Pa
(2(1-
pa)b2
+ (1 - bjp) ||n! - V W
+
Pn
52

---

3.
Es ||]
ob²
(2
b)2 L2a
+ 213
| - -2'1 + 26 114 - VA(at)), vie [n].
S
+
B
B
Proof. First, let us proof the bound for Eg
Ep, [|[x+++~(((++)11]]]
Ex Ep. [| [|(
Ex [Ep |1:441 - Exe [E, [ [1]] + EE (E [b++1]] V ( ||?
Using
Ex Ep, [b]+t]] = h2 + Ek [x$+t]] = No + (z((t())- - - b(h) - v.(((())
and (16), we have
Ex Ep. ||6411- - (
= Ex
Ep. [1 - Es [Ep, [h [11+]
+ +1 11' |1' {f("')|?
We can use Lemma with ry hi and 8; = k to obtain
| - (f(
Eg
Ep.
Ex || || - Es [1]] + Pa Pan
Σ
Es
[M + (1
11 p i=1
pp
Ex [|] (/42) VI( (n² (((ctt
n Pa
-V - (f(x') 6 (W) -V((=)))
Pa Pan
\ 6 6b4
+ (1 b)² Ih'- Vf
(15)
2
Σ
En [ll6
[Ib(V - - 1²]
P
2
- (V/ott - (((()=))))/(((()))) [9]
Es
-
n2
Pa Paa
[ V/((2') - b( v)(
n2p2
+ (1 6)2 |1h' 1 [
26²
|| ( - -/1=+-111 [|]]]
Fx
n n2pp
+ 2(1 6)2
En - - -
- -
n²pa
Pa Pan
[ VS((2)) 105---00 U(M -
n2p2
(1 b)2 |1' [](
53

---

2b
B
ER
V
p²pp 12 i=1 j=1
2(1 - b)2
Fik
( +
- -
p2pa
Ph Pan
Vfi(x(t1) Vf((2')
n² n2pp
(1 (1=b)² b)2
- V
In the last equality, we use the independence of elements in the mini-batches. Due to Assumption we get
10-1--f(a't) [|]
Es
Ep.
ob
12p B
+ 2(1 - 6)3
(VSilatt)) - V(ie'' -VVncttt - v\i(a')) - [P]]
En
i=1
Pa Paa
[V - VA(C') - -MN - v
+
n² p²p22
1=1
+ (1 - 6)2 111t - 2
(15) 26202
B.
2(1 6)2
Vi -V/((+ (VS((2tt)) V)((=)) ||]
Fx
n2pu
2 (Pa- Paa)
Vfi(z(+)) vf((21)12 + 2 (p. - Paa) b2
+
| - {(((t\)
n2p2
n2p?
i=1
+ (1 - b)2 111 - -
26o02
np.B
+ 2(1 2(1- (11- b)2
E& ( Vi - - V(((4))
(V
n²p.BB²
1=1
2 (px Paa)
Vf((z+1) - + 2 (p. - Pam) ba
Σ
|l {i(a)))1
n2pp2 i=1
n²'p2
1=1
+ (1 - 6)² |1 vfx'')11
where we use the independence of elements in the mini-batches. Using Assumptions 3 and 6, we obtain
Ex
Ep.
[|N-t]-
- [|(
o6
(2(1-b)21 6)
2 (pa P=a)
|| - 2211 =2'1
+
nipa
12paBB B
np2
2 2(p
Poa) B2
Σ ||n v(((t\)) + (1 11-b) b)) ->(>"'-VV(<>)]]
n n2p2
i=1
54

---

Now, we prove the second inequality:
Eg
Ep.
h 1eet1 - V
F& Eip ||nst1 - Fx Er, [+]+*]]
+ |E Epp [1ott]]] V fi((e( y/(
Ep, || - (1/ + V ( Vii(=') b(h- - VA(
E&
+ ||M + V/((x(())- -V/((2) - 699 - V/((')) - )/ u
E& Ep. [11ft1 (M V)(( V/(('')
1y0 - V)((2())
+ (1 b)21 || - (
1o + 1 ket1 (n: + -Vi((ttt) - -Vf((+' u(1 - v(((a)))
Pa EsE
Pa
+ (1 pb) || - (M/+ + V.((tt))) - V.((2 - b(9 VA(+')))11
+ (1 b)2 |/4 ((('"))
1. (V Vf(('') b(4) - V 12]
Eb
Pa
+ (1 Pa) ( V/(('') 6(4 - vf((2)))
+ (1 6)3 by - (
(16)
EN +1 (V V/((ot) - b04 - V((+))))
pa)²
| - Vi(0o)- b(M) v)(('\))
Pa
+ (1 pa) [Vi(att))- V/(aa') 6(1 - v((+1))
+ (1 6)2 |44 - Vf((='))1
P2 Ex
| +1 :1 -2 -Vi(of/:(t b (b) V(i(+:s(())) -(VA()ttt)-VVV
- -V/(-)) - (0000-66-----1 100--VAA V(1
1- Pa [f - vf((=') - 6(h) - v(((a)))
Pa
+ (1 1--b) b)2 | -VV(aa())'''
ER |16 (Vii(z (gtl) --ft)-(ii((tt)) + (1- (Vfi(t'+)) v/(('' - -V
Pa
+ 1 Pa ( Vf((z') -O( v
Pa
+ (1 2)2
| - /)
(15) 282
EA V (1: [1(
Pa
2(1 b)2
En
(rff(ttt: - v(((+()tt) -VVS(e+t))- -V
Pa
1 Pa
\Vf(ttt)) - vf((a)) 6(M V)((2())1
+
Pa
+ (1 b)2 | - -
55

---

Considering the independence of elements in the mini batch, we obtain
Eig
Eyp
||n
[]]
26
Ek
-
B² j=1
2(1 b)2 B
Σ Eg
- -V -VA()))) [2]
P₂B²
1 Pa || V(((2)) 614 V
Pa
+ (1 6) 1|4 - V/(ea))/
(15) 26
Ex
2(1 - 6)2 B
Σ E*
[|
)
- (Vfi(ettt) - v((('')) |||
P₂B² j=1
2(1 Pa)
(2 pa)6² +(1 b)²) 1 - v)(
Pa
Pa
Next, we use Assumptions 3, 6, 5, to get
|| - ) ||]
Ex
Ep,
22202
+ 22(1 - b)2 10 +
2(1 11--pp. -pa)
- 2011
<
B.B
PaB
Pa
+
2(1 - -Pa)b²
+ +(1 (1-b)) 1)²)
|
{)((2()1
Pa
is left to prove the bound for Eg [|]4
Es
|1ast211
=Fie || - (b( v(((+( ||]
1 Ex V (1: (/1)) (f((=t=/tt) - 140
- b(M v)(a'()) ||]
+ +I[VA(2(+1) -/(('' 6(h) - V)((1)))
Ex [116 (V f( +1 (1
+ -
+ +IV7A(0(+1 V/('') b(h) - 1
(1)
2 E || /11 V/(
2( - b) V
( V/il'' -V
2 V vf((2') || 2b | {=
Using Assumptions 3, 6, 5 and the independence of elements in the mini-batch, we get
Eg ||
56

---

2b²02
2(
6)
+ 2(2 ||ot| - 1412 + 26² 1 - V)i("')|?
B +
Theorem Suppose that Assumptions
2, 3, 5, 6, 7 and 8 hold. Let us take a 1
b (0.
7 .7
L+
(2+ 2 + Awa ((1 me)
I2 2-
and
d. h for all i E [n]] in Algorithm 1 (DASHA-PP-MVR) Then
D4 1(1
240
2
- V/(a")/'' +
32bbo22 +
1 Σ m2 1 -
E
T
7
b
np?
np,
(18620(2w +)
12b o²
nB
Proof. Let fix constants v. p E [0, oo) that we will define later. Considering Lemma 6, Lemma 10, and the law of total expectation, we obtain
E [
7/2w + 1) E
-1 +
7((2w + 1) Pa
Pau
E
11.55 ++1
11
Pa
nyg
+ EE | v f(
+ +pli n
1
|
()
E [(x')) 2 ||
(1)
2 //) ||a5t1
I.
- 10²
+ 7 || v {(>'))1
22
72w + 1) |11o* - -1]1
>((2 + 1) Pan)
1
Σ 11 - millr]
E
Pa
npp
n
1) (2w
1 a
Σ
1
F.
np²
+ +vE || [|1----
pE
| h+( (o
n2
-E -B(re ((x)) -B(M(O))
2// ||
(2)
L
||,
+ 7 ||
v {(>)))
27 2
72w + 12 [1l"'~>'11? -1910]]
((22 + 1) Pa
Paa)
Σ l1 1811*)
Pa
mpp
4w 2w + 1)
1
E
Ex
||
7i
+
Eg
Ep,
|1
f +2) || ||]]
1
12
+ +p..
EB
P.p
|
n
S F. [(x²) 3/2 || ||())))))
2% 2 ||aft1 - 1²11
1 L
+ 7 ||/1" V <
72w 1)
|||a - 1111]]]
+ 71(2w + 1)pb Pio)
1
Σ 11 - ns|l?
Pa
npo
m
(2w + 1)
E
26202
+
(((1 (2(1-b))
6)2
+ 2
|| 211 + 2b2
Σ
|| - v/(
B
B
57

---

26²00
2((1 2(1-b)8L3
2 (pa-
Peal I
+ vB
| x'11
B
BpaBB
npp
2 (Pa-
Pma) 6²
Σ
1 V + +11- ([00))) -V(0)))))
+
n² p2
i=1
26 02
22(1 - L2
2(1 - pa)L3
|
+ p
PaB
PBB
Ph
+
22(1 (2(11 pa)b?
(1 -b)2
| v)(6)))))
Pa
After rearranging the terms, we get
F
[[((ttt)]]
+ 72w + 1)
E.
+ 7(2w + 1) Pa
Peal
F.
n
1105 +
n n1t211
Pa
np?
+ +vE |110-1 4 /
+ +pE
1
||
n i=1
S [E[[(r)] - 3 [|| ||
12w + 1) E [|0' - -=1"
+ 7((2w + Pa - Pan) E
11 - n3ll"
np2
Pa
1
L
42 +1)
2((1- - 6)
+ +2ī2
27
2
B
2(1 - 6)²L2
2 (Pa- Pma) 22
2(1 2211-))2 161--yy-
6)2
2(1 - pa)
E || [|00"))-=0'())
+
mpa B
npp
PaB
Pa
+ 1 (1 b)²) F.
rw (2w + +1)
2v (Pa-
Paa)
6²
2(1 p2))6²
+ (1 +(1-b)²) b)²) ) E 1 Σ 1Ins -
+
+
+
np²
npp
Pn
y22> + 1)
26
26 o²
+
+ p Pa
mp2
npa
B
By taking v= 7. one can show that (7 + v(1 b))) S 1/ and
E [[
(2w + 1)
E -1o+t-nh+1g
+ 7(2w + 1) Pa
Paa
E
110 1+ 13 11
Pa
np²
FF ||1 v (5
PE n
1
| v Viaatt>
<
<E( - 1 ||> |||]
72w + 1) F. [|o' - n0]l"] [|l]] + 7(2w + Ph Pao)
1 Σ 11ø8 n!ll?
+
Pa
npp
n
1 L
(2w + +1)
(2(1 D)
+ 27.2
27
2
npp
B
7
2(1
1)21.3
2 2pp
Pam) 1.2
(
22(1= -1)213
+ 2(1 P.)
)F [||
+
p
B
np?
B.B
Pa
E
{(
58

---

(2 + 1)
2y (Pa Pea) b
(((1 [2(1- - 22(1-Pabb
+ (1 1)0)
ト
| v((''))
+
+
+ p
npa
npp
Pa
"
862 + 1)
276
+ p 2b²²
o²
+
+
npp
nPnn
Pn
B
Note that b S
Pr_ thus
2-p;"
86 y6 (2w + 1) +
27 (Pa
Pan)
b
(2 P(1--a)6
+ +(1 + +(1-b)²) ))
+(1-b))
+ p
np2
np²
Pa
86 yol (2w + 1) +
27 (Pa-
Paa
b
+ p (1 - (1-1)) b)
npp
And if we take p (bym((2w+1) npd
+ 20(n, Pw) then
npi
8b² 8b2 2w +1)
27 (Pa - -Pa) b
+ p p (1 0)
+
S SP.
np2
npp
and
E
[f(](t]]]
72w + 1) [10011 1190+1114411 + ((2w + 1) Pa Pan
E
n
|19 +1
nott11 11
Pa
np²
71
E |11441 (
(2w +1) 27 (pa Paa)
E
n
|ngtt
v/i(o(t2)1?
b
npp
n2p
72
$ E [f('t]] - 1 | |
72w + 1) E [101 - -"|]"]] + 7((2w + +1) Pa
Paa
11 - h!ll?
Pa
npp
n mml
L
47w + 1) (2 - b)
+ 2T.2
27
2
np?
B
Y
(2(1- - b)2
Pea
+
1
nppb
B
Pa
(2w + +1)
27
[1
Ru
Pr
(2(1- - 1)212%
+ +2(11
pa)
F.
[latt2
npa
np?
B
EE
[115- (06--V53 -/((")]1²] + (8brw(2w (2w +1)
2 (Pa- Paa)
E
1
|
npp
npp
12
i=1
866 122 1) +
276 +
(8byw(2w (2w + +1)
27 (Pa Paa)
26b
o²
np?
nPn
np2
Pa
B
Let us simplify the inequality. First, due to b S ps and (1 - PPa)= S (1 (1-
Pee
we have
(2 11
27 (1
Pm
(( - 2)2L3
Ps
+ 2(1 pa)
npp
np2
B
8byw (2w + +1) (2 - b)2
+ 2(1 E2)
np
B
27
Pss Ps
2 b)2L2
+ +2(1 - 23)
npp
B
59

---

(2 +1)
(2(1 6)
+ 2
npp
B
27
2((1
11)3122
+2
1
Pma
12
npab
B
Pa
therefore
E [[][ + 72w + 1)
E
|11/t1 - 1 + 7(2w + 1) Pa
Paul F.
11
1+1
n1
1 |
Pa
np?
1=1
L [|1411- \|( [1]]
(2w + 1)
27 (Pa- Paa))
E
1
-
|ntt2 -
mp2
mp?
< E [E[((=']] - 2015 | |||]]
72w + 1
[lo' - -1'1']] + 722w + 1) Paa)
l1 - -]9l?
E
Pa
repi
n2
1
L
12 22w + 1)
(2(1 - 6)2L?
+ 2T.2
27
2
np?
B
3y
(2 -
b)
+2
1
Paa
12 E | - 2²11"]]
np,b
B
Pa
7 E'
||10 1110' [[(x")]]]+
+
(8bmu(2 (2w + 1)
2 (Pa- - Pas)
E
1
Σ
|
b
npp
np²
(2w + 1)
276
(2b + 1)
27 (pa- Paa)
26² o²
+
+
+
np?
nPpn
np2
npp
Ph
B
E [f(((]]]
2 23 [|]](=*))]]]
72w + +12p
[||a* - -01l²]]
+ 7((2w + 1) Paa)
n
l1st - ndll?)
+
Pa
npă
T
1
L
(2 + 1)
(1 6)2L2
+ I22
27
2
np2
B
67
(1
(1-b)²L2
+
1
Paa
1.2
E.
1
- 10913]]
npab
B
Pa
+
E b
||nt (in--Vi3 -((())))
+
(8hr (2w 1)
27 (Na- - Paa)
1 n
Σ
||
vi(aa\))
np?
np?
n
(2w + 1)
+ 2yb +
8bb (2w + +1)
27 (Pa- Paa)
21²
0²
+
+
np?
npa
np²
np²
Pa.
)
B
Also, we can simplify the last term:
8by + +1
27 (Pa - Paa)
262
+
npg
Pa
1603 (2w + 1)
462 [
Pia
nip
1662 ywu (2w + 1)
4by
+
np3
repa
thus
E []((tt1))] + 7(w + 1) E [10 - -n 1,] + ((2w + 1) Pa
Pea)
E
n
11 +1
n n.t2113
Pa
nyg
60

---

+ 1 |1 (((
(b + 1)
27 (Pa- Pea)
1 n
E
npp
np2
E [f[(x=)]] -
2 E [|
72w + 12 ||9* - 11 1²11²]] + 7((2w + 1) Pa
Paa
T1 Σ
l1st - nill?
npp
L
24 2w + 1)
8)2
+ I
27 2
npā
B
by
(1
+
Pea
I
E5
|| | - =²(12]
npab
B
Pa
E [1lh'v/r -
(8br + +1
27 (Pa Pna))
n Σ |
+
+
b
npp
np²
n2
+ 12402yw(2 (2w + 1)
67b o²
np2
npaa
B
Using Lemma 4 and the assumption about 7, we get
E [[(
72w + 1)
- 1+1] + 7(2w + 1) Pa
Pau
E
n
1 ++1
h6 11
Pa
nph
E |1 Vf
(2 + +1) npp
27 (ps Pua)
E
n
hgtt1
n2p2
s E [f(xt]] - 33 ||>
72w + 1) E ||0' - st]1i] + 7((w + 1) Pa
Paa)
1
11at - h!ll?
Pa
npp
n
+
E ||n | ((((+))1 +
(2 + 1)
2x (Da Paa)
Σ |
b
np2
np?
n
yw 2w + 1) 67b) o²
+
np?
npa B
It is left apply Lemma 3 with
va = (2w (2w+1) 1) E [|o" - -1a113] ((2w + 1) Pa
Paa)
91 - 13ll"
npp
71
(2w + 1)
(pa Pra))
1
+ E In' (h''-V((a')1 +
|| Vf((=')1
np2
npp
n2
and C= (2462
Gh
a² RB to conclude the proof.
Corollary
3. Suppose that assumptions from Theorem 4 hold, momentum b
C min
pane B
neB 2 andd hy
o²
Pla Σk V Vi(a"" for all i [n]]
a²
and batch size Bini
B B A
then Algorithm I (DASHA-PP-MVP needs
b
Ao E
(T.+
La VB
I La
)}
0² VDane
T:=0 communication rounds to get an e-solution and the number of stochastic gradient calculations per node equals (Biii + BT).
I
Payn
Paven
BB
B
61

---

Proof. Using the result from Theorem 4, we have
E
1
2Do
++ V
48w (2w + 1)
13 (1 - 1b)222
12
(1
Pea
12 +
(1
b)2
T
np2
np,b
Pa
B
4(1 Ru
+ b
2
1120
Vvf(2 +
32bw + 1)
+
Σ |n
nPa
( (28 + 1)
12b
o²
+
pd
Pa
nB
We choose
b to ensure
1)
+
126
o²
= (c).
Note that
p2
nB
max
w
x² B
S
max
puin }) thus
Da
)
1
(T.
Lo vB
σ2
1,, Le
o
Do
T.
Payn
P B
1 b
l22
1
+
n10- |)(09)1
+
|ng
np
npa
1=1
where 1p. 1
Pu. Ps
It enough to take the following T to get e-solution.
(++
Lo VB
Lo L
)
T 0
Do
L +
Povn
V
D
vB)
1 + _/2 b 1100 \)(>>\11
+ (
low2
)
1 Σ
+
np?
npa
n
i=1
Let us bound the norms:
n
Ban
E -[ v5(2タ)17]
= E
[1(12" - -VS(a))
n1 i=1
Binit
Ban
1
[ - |)(
n² B2
0²
nBBiii
Using the same reasoning, one cat get n Ex_ ities, we have
E. |110 VS((29)1 <
d²
Combining all inequal-
Pua
62

---

w
[
Lo
o²
[22I+
(r )
T= O
Ao
L
+
+
Puvn
VB!
p
lu202
+
bn Bini
up? Binit
np Binit
Using the choice of Binit and b, we obtain
1
Lo L+
σ²
Lo VB)
)
T
0
Do
+
E
Pa
Pa
/B/
D
0²
B2-002
bo²
+
v
PanB
nipa
5/2 B
3/2 nB 'nB
w
1++
Lo vB/
σ²
1
Lo VB) )
Ao
+
Payn
P2en²B
0²
E
+
+
BBnBB
VP
Au
L
(T+
La vB
σ²
1 I.
Lo vB.
σ² B
E
Payn
*V
p
PPu
Using B 1, we can conclude the proof the inequality. The number of stochastic gradients that each node calculates equals Bum + 2BT O(Bun BT).
Corollary 4. Suppose that assumptions of Corollary 3 hold, batch size B < min
Piven
take RandK compressors with K = 0 (nd./m) Then the communication complexity equals
O
Lnd
and the expected number of stochastic gradient calculations per node equals
Payne
LnAna PAp
VpsnE
Proof. The communication complexity equals
0 (d+ KT) = o
d+
A
KL +
K
w
La
+ K
Φ²
1 T
Lo
+
o² VPaneB
3
Payn
BB.
p2en² B
BB
63

---

Due to 3
I.2 12 12 we have Ip,L
Le vB
2hm and vB
d Ao
La
x²
Le /B
o² VaneB
O kT) o
KL + K
+
K
+
K
Pav'n
VB
B
From Theorem 6, we have d.
R-
Since K = A
Bdy
O
d
the communication
complexity equals
O KT)
d+
Au
d
L
+
d
[+
Lo
+
Lo
do VPVNTE
Payn
Pavn
vB
Pav
Pavn
0
do
La Lod
+
VPayne
Pa PaynE
And the expected number of stochastic gradient calculations per node equals
(Bint + BBT)
0²
Bw
Ao
(it
Lg vB
La VB
0² BanEB
0
BL +
B
B
PanE
Pa
nEB
E
Pay
Džen²B
0²
Bd
σ²
A
[I+
La VB)
o²
Lg
o²
0
BL + B
+ B
VPne
K /
Pa
B
KPayn
DeenBB
VB
Vane
Ao
0 Paven
[+
Lo VB
+ σ Lo
0
+
L +
VPnn VPaneVB
PaVEn
PavEn
02
Ano
0
+
VPan
P2
64

---

Analysis of DASHA-PP under Polyak-Lojasiewiez Condition
In this section, provide the theoretical convergence rates of DASHA-PP under Polyak-t.ojasiewiczz Condition.
Assumption 9. The function sstissyy (Polyak-Lojasiewicc) PL-condition:
[V > (z)((x) f*), Vx E R,
(30)
where f znR f(x) -00
Under Dalyak-Lojasiewice condition, a (random) point 3 e-solution, i[ S. We now provide the convergence rates of DASHA-PP under PL-condition.
F.1
Gradient Setting
Theorem 8. Suppose that Assumption 1, 2, 7, and 9 hold. Let us take
P. 20+1
b = Pr
2-ph
7 S min (++1/
200w (2w + 1)
+
48 ny
1
Paa
T
np?
Ps
4p
and h
5 = Vi((=") for all i E [n]] in Algorithm (DASHA-PP), then E [[(x*]] - 8" S
(1 - --11)) An-
Let us provide bounds up to logarithmic factors and use θ (.) notation. The provided theorem states that get e-solution DASHA-PP have
w +
+
Pal//n
Palyn
communication rounds. The method DASHA from (Tyurin and Richtárik, 2023), have to run
w
uVn
communication rounds get e-solution. The difference is the same as in the general nonconvex case (see Section 1).. Up to Lipschitz constants factors, we get the degeneration up to 1/r. factor due to the partial participation.
F.2 Finite-Sum Setting
Theorem 9. Suppose that Assumption 2, 3, 7, 4, 8, and 9 hold. Let take 2 probability
PaauPa 2 2-ps
Ppage
m
S min
{ (1+)/
200 +
[2 Powww) 1.2 Lmaxx
48
((
Pia P.
Ża + (1 Ponge 1.2uax
tpp?
upp Peage
24 24
and 11 = of
Vf(x))) for all i E [n) in Algorithm (DASHA-PP-PAGE then E. - -
- 71) An-
The provided theorem states that get e-solution DASHA-PP have
L
(I+
Liax
vm
(I+
Linax
Pa
Ba
Paliynn
VB
PauVnB
vB
communication rounds. The method DASHA-PAGE from (Tyurin and Richtárik, 2023), have to run
δ w (w++) B p pVn (i+
Temax
TTmaxx /BB
VB
pVnB
communication rounds to get e-solution. We can guarantee the degeneration up to 1/n. factor due to
partial participation only if B O (2 The same conclusion we have Section 6.2.
65

---

F33 Stochastic Setting
Theorem 10. Suppose that Assumption 1, 2, 7, 5, 6, 8 and 9 hold. Let take
2w+1'
b E
0. 2-pi
-1
y S min
L+
200w (2w + 1)
(
6)2
+
12 +
(1
b)3
+
Peu
ï ))
np2
B
np&
B
2
2/
and hg oh for all i E [ni in Algorithm / (DASHA-PP-MVRR) then
E [ -
(1 7m))"
27 Ao
|140
v((x0)1 +
[407bo(220 1
8y (Da - Pea)
Σ 1 V1(2O111)
b
7iph
npp
1006 +
206
o²
P
Pa
nB
The provided theorems states that to get e-solution DASHA-PP have to run
+
+
d2
+
L (T.+
Lia
i
Lo VB
Pa
LnEB
PaumE
P PaNYn
vB
lampulVVE
P.
(31)
communication rounds.
We
take
b =
min
uae B
P.anen
2
o²
o²
min
Putmn
})
The method DASHA-SYNC-MYN from (Tyurin and Richtárik, 2023), have to run
Ō 0²
L
w
[
Lo
L
+
(32)
J
fA Pvn
VB
eBB
/B
communication rounds to get e-solution
In the stochastic setting, the comparison a little bit more complicated. As in the finite-sum setting, we have take O However, MASHA-PP-MMV has also suboptimal term Pa. This suboptimality is tightly connected with the suboptimality of Binit in the general nonconvex case, which we discuss in Section 6.3, and also appears in the analysis of DASHA-MVR (Tyurin and Richtárik, 2023). Let provide the counterpart of Corollary 4. The corollary reveals that we can escape regimes when P2 is the bottleneck by choosing the parameters of the compressors.
22 7,2
to guarantee the degeneration up to 1/2, of the term Pi from (31).
Corollary 5. Suppose that assumptions of Theorem 10 hold, batch size B S min
Pay/ee
we take Rand compressors with K
/ dLa
Then the communication complexity equals
do
Pay/en
PaP
and the expected number of stochastic gradient calculations per node equals
δ
Pajine Pamp2l2
Up to Lipschitz constants, DASHA-PP-MVS has the cate-offthe-arr oracle complexity under PE.- condition (see (Li et al., 2021a)). Moreover, DASHA-PP-MVR has the state-of-the-art communication complexity of DASHA for a small enough μ.
For simplicity, omitted d <c term from the complexity in the stochastic setting, where Ce is defined
in Definition 12. For instance, for the RandK compressor (see Definition and Theorem 6), Se = K and = H (w)
66

---

F.4 Proofs of Theorems
The following proofs almost repeat the proofs from Section And one of the main changes that instead of Lemma 3, we use the following lemma.
F.4.1 Standard Lemma under Polyak-Lojasiewiez Condition
Lemma 11. Suppose that Assumptions I and 9 hold and
E [f(x*t)] + <E(((=)) ? [|V + +11 -uply + +,C,
where T is sequence of numbers, T 2 0 for all t [T.. constant C 2 constant μs 0, and constant 7 E (0, 1/)). Then
[ (1- ((S(1)) 1r) + +200) C. 1
(33)
Proof. We subtract f and use Pł.condition (30) to get
E [[f(att))- - --] + tpttt
I E [ff(x') - [-] E [|V + + + Gc
I (1 - 7F [5(x²) f*]
+ (1- - +
= (1 - (1) (E [f(x') fr] + +,C.
Unrolling the inequality, we have
E [ 71041 S (1 (1-7p) (ssxx9) -5*) +7N0) 7 Σ (1 y
S (1-74)* ((5(x9) 1*) +T00) + c
/
is left to note that V 2 0 for all t E [T].
F.4. Generic Lemma
We now provide the counterpart of Lemma 6.
Lemma 12. Suppose that Assumptions 2, 7, 8 and 9 hold and let take
Iw+II then
Po
[f( 27w2w 1)
h411p²]
47((2w
1) Pa
Pan)
E
1
n
11
+
h
111111
Pa
np²
n
S E [xx') - 3 "| 27
L
||0 - -x'1² + [1''~V[(a'))
2
+ (1 - -744 (2w 1) 1) [l00 - -1'1
(1 7p4)
47/(2w + 1) Paa)
Σ 19
1ill?
Pa
npp
72
10w(2w + 1)w
| ||,5t2|1 |
Proof. Let fix some constants K, 17 E [0, 00) that we will define later. Using the same reasoning as in Lemma 6, we can get
E [f(x(+]]]
+ <F ||10 1 11 11 F.F..
+1
1 13
72 1=1
< (( - [ -
L
| - =0l12 + 7 1112- v(((t)) ||
27
2
67

---

(T + 12 (1 - -00) E |lg' 12' 1=11"]
Kaa ((2w + 1) Ps Pam) + 17
a= (22 + 1 - -Pa)
+(-aa²)
n lost ngl2
+ (1 (1-a)²)
E
n Σ
np?
Pa
2kw
2muw
11 F
+
nps
Pa
n
Let us take x
27 One can show that y + K (1 a)² s (1- 9) n. and thus
E [f(
+ EB |11 - 11
27
llst 1- - n1 114
+ n
a
i=1
< B ((xt) - -/5 || |v((=)]1- -
1
I.
|| - 20112 + 1112 {
2
27
2
(1 2) 27 [lIo* - n²1
a
(2w + 1) Pa - Pea)
a (2w + 1 - pa)
+ (1 - +((-aa) E
1 Σ llst n3ll"
+ 17
np²
Pa
444w
2mpw
1
11
+
+
E
ampa
Pa
1=1
Considering the choice of a, one can show that (d((2++1-pe) + -1)) S 1 a. If we take
Pr
42w( Pw) then 2xa((2u++ 1pp. Pue)
a² a2(ww+l-pu)
+ (1 - a)²) s (1 - 9 1 and
7 ned
np?
+
E [[
+ 27 + +1) E [|10 - 11]] + 47 + 1) Pa - Paa)
E
1
1|
1-1 - 1 112
Pa
npp
11
7 [1 || - 1 L
||a5t11 - 10112 + + 1|A²² V vf(z"))' )|(²
< E f(x')
2
2
2
(1 () 22(2w + 1) [110'' - -1²11 + (1
47:(2W + Pu - Pan) E
11 - -mll
+
②)
npa
Pa
(2w + 1)w + 87((2w + +1) Pea)es"
+
E
npp
npp
E ((xt) 30- 7 [|
(1
1 L
||x
- 101 + y || {
2
22
2
+ (1 - 2) 27(2w +
+1)
F. [lb'' - -n'11
+ (1- 2
m)
4r:(2w + +1)pa- - pmn) E
Σ 1o - n3(1))
Pa
np3
12w + 1)w
1 Σ ||att211 1
E
mp2
It it left to consider that 7 - and therefore 1 - - < 1 7p.
68

---

F.4.3 Proof for DASHA-PP under Pł-condition
Theorem 8. Suppose that Assumption 2, 7, 8 and 9 hold. Let us take a
Pr
b
b=
Pa
20+1:
2 p-ps"
7 S min (
200w (2w + 1)
+
48
Pan
I
a
nP2
nyg
Pa
4p
and hς g.- = ff(("") for all i E [n] in Algorithu 1 (DASHA-PP). then E [f(x")] - f S
(1 (1-744 "1-) Do-
Proof. Let us fix constants v. E [0, 0o) that we will define later: Considering Lemma 12, Lemma 7, and the law of total expectation, we obtain
E [[ 22w + 1)
1oott-h4tjj 47y(22 +
1)
Pan)
1 n |10
E
E
Pa
np2
n
+ +E
V ( >|
+
+pF
1
|
n
< E f(x') - 2// "(
-(2
1
L
||0
+2 x² || + y ||A {(='))1
27
2
+ (1 -744 22w - -1) E |110* - 11]1"]]
(rw + 1) Pa Pea)
Σ la6 -
(1 7pm
Pa
npp
(2 + 1)
n + 2b 1
E
2T.2 || - 2011?
Σ || {)((=1)1
np²
2 (pu Paa) 1.2
100+1=0011 21² (pa- Pam)
| | v.(i(=')11 + | 102(11--//( -
+ =E
n²pp2
+ pE
2(1 pa) 2 | 1--41=x111 -201/=+ + (2b2(1 Pm)
+ (1 b)2
ト/ ni
Σ | v
Pa
Pa
After rearranging the terms, we get
E [[
22w + 1)
E
|10 11411)
47/(22 + 1) Pan)
E
1 n
11 + - n6.2
Pa
np²
1 | v
+ || V5(a 1|]
+ +pF
$ SE <E[f(="] - 2 E ||V
+ - -744)
(2w F2 [1o0= + (1 - 710)
47<(2w + 1) P4
Psa)
1
Σ
l1e1 - n2ll?
Pa
npp
72
1
L
20yw (2w + 1) i²
2 (p. - -Paa) 2
2(1 Pa)
|| 1o0tt-=x010 =0(13]]
27
2
mp²
10
np2
1
Pa
E
+ (7 + v(1 - -6)2) E |1'' - vf(at))1
2062 + 1)
26 (pa- Paal
262 pa)
+ +(1 (1-b)²) 1)²))
1 Σ 1I - vA(C2))1
np2 + p
E
nyg
Pa
By taking v 6. one can show that (7 + v(1 -
((1)) b)2) $ (1 - (2) v, and
E [[( + 22w + 1)
+1 - 1 + 47((2w 11 Pa- Paa)
n
1 ++1 - 13
E
Pa
np2
69

---

27 E ||n vf(e(1111 + +p 71
12
h 1,tt1 /
+ bb"
$ E [f((x')] - [|
27(2w + 12 E ||0* - -$1]]]] + (1 - 710)
4r + 1) Pa Pea)
1
+ (1 11--14 -744)
72 Σ
|
n1
Pa
npn
-
1
L
20yw (2w + 1) 1.2
4y (p. -Pa)) 2?2
P
2(1 ((1-p)) p.)
E
| -
27
2
npp
bnp?
Pa
b)
2% E [1 - V\(2')]
+
2
+
2002gwl(2 + 1)
4yb (Pa- Pan)
+ p
22 -
-Pa) Pa)
+ (1 - ))²)
((-bb)))
E
- n
Σ
11 - v((
npp
npp
Pa
Note that b
p-p, _r, thus
2002yw you (2w + 1)
47b (p. Paa)
225 - Pa)
+ (1 (1- (1--))) 1)9)
+ p
?
npp
Pa
2062ga nw + +1)
47b (Pa - Pan))
+ + ((1-b) b)
npp
nph
And if we take p= 12w-
1)
+ 8y(11 pwo)
m then
npp
np.
+ + (b) s <11-3 b) 2062)w((2 + +1) 47b (Pa Paa)
2)
npp2
npp
p.
and
[f + 27(2w + 1) E ||1ot1 1 11 47<(2w + Pa Paa)
E
E
||9 ++1
hτ 11
Pa
np²
2% E ||1st1 - V ( ||1] + b
[111|++((0000)) (400)a(22+ +1)
87 (pa - -Pa)
1
E
|ns+1
np?
np?
n2
< F. [[('')) - FF [|V
+ +(1 -711 (2w 1)F E [lo0* 11''- -h(]]]] +(1 710)
4r:(2w + 1)p= Pa))
1 n
Σ
go nil??
Pa
n2p
n
1 L
20Tw (2w + 1) 2
47 (Pa - -Pza) 122
27 2
np2
bmp²
80by (2w + 1)(1 P2)
16y (pa Paa) (1 --))
[||att] - 201]
E
npp
np3
(1 1 2 b
b) 2 E |1 vf('')]
+ (1 (1-b) 2) (
/40bya (2w + 1)
8y (Pa -Paa)
1 Σ | IIn- -((Ct)))))))
E
npp
Due to 2 <bb S Pa: we have
R. [[((ttt))] + 27w + 1)
(ottt-Ntupp) + 47((2w 1) Pa-
Pan)
n
1+1 h n1t1112
F.
|
Pa
np3
+ 27 [114t2 -
( nyp
+ /40by + 1)
87 (Pa Pea)
E
1
|,442
- v/(Co42211
np22
12
70

---

$ E [F[((()] - - [1 [|
+(1 (144
+
27(2w - 1 E |l1o - 1011(] + + - +1
-w1) 47:(2w + 1) Pea)
199 - hill?
Pa
n
L
100yw (2w + 1) 2
24y (pa Peal) I
|| 1oli-xx x²113]]
27
2
np2
nipz
b) 2% b
[Ine - v + (1 (1-
6 2
4006
2w + 1) +
87 (pa -Pa))
1 1
+
E
E
1
2
np3
nip
Using Lemma and the assumption about 7, we get
E [f((
(2w + 1)
||get1 - 11] 47((2w + 1) Pa
Paa)
E
1 n
++ - h
1 11
Pa
np2
T1
+ 2% b
E |||5 (f(=++1113 1|²]] + (400))(22 +1)
8y (pa Pum)
1
E
np?
npp
n2
S E. [[(('')]] - F. [|| ||>
+ +11- -714) 22(2w + 1) ||00* - -ha]l]] + +(1 1 yx4)
47 + 1) Pa
Pas)
1
1o% - nill"
Pa
npp
n
+ 1 b)
b)
2 E hh' vf(z'))
+ (1-) /)
b)
(400 (2w + 1) +
87 (pa - -Pa)
| - Vii(at))
E
2 b
nP22
np²
n1
Note that 5 4u
s
Po
S
b
thus 1 - S 1 yop and
4p
2n
E [[
+ 27 (2w + 1)
E
11 +
47((2w + 1)
Paa)
E
||g 1+1 - h 11
Pa
np3
+
2% b
E. ||1 v f(
+
(40 1)
87 (Pa - -Paa)
E
1
|
np?
np?
i=1
< E [f((')] - E ||
2
+ (1 -711) 22w + 1) F. |lo0 [111] +11 714)
+ 1)ps- 4
Paa)
F.
1
19
-M nell?
Pa
np?
12
21 E ||1'- |P] + +(1 +1- (406yw(2u (2w + 1)
8y (Pa Paa)
+ (1 7u)
E
|
b
npp
np8
In the view of Lemma 11 with
2(2w + 1)
|100 - -01[²]] + 4((2w + 1) Pa Paa)
1 m
ge
lo
hil
Pa
np²
72
2E [|1h'~v((>>)9' + (400bu(2w + 1) npp
+ 87 (Pa Pea)
+ t
E
||
np?
12
we can conclude the proof of the theorem.
F.4.4 Proof for DASHA-PP-PAGE under PL-condition
Theorem 9. Suppose that Assumption 1, 3, 7, 4, 8, and 9 hold. Let us take
2 1 probability
P.
Ppuge
B b
Po
2 2-Pe
7 min [+
220 + 1)
[a
(1 Prowe 1/2
48 mpp Ppay
((1
Pia p.
Za
+
(1
Proge
122
mpp
B
B
2
71

---

and h = s. = ff((z") for all i E [n]] in Algorithm / (DASHA-PP-PAGE), then E [f(x")] f - (1 (1-74)² Do-
Proof. Let us fix constants P E [0, oo) that we will define later. Considering Lemma 12, Lemma 8, and the law of total expectation, we obtain
E [f
2y + 1) E
47:(22 + 1) Pa
Pan)
E
11 ++1 - hg 11
Pa
np
+ + |1:5- v ((a
+ tpE
1
Σ
|| )2
i=1
( 22
< E ((at) 1// ||
|| - -ل'l + 7 || -V {(()))|
2
+ (1 - -744 27(2w - 12 E
[lo'' -
47 + 1) - Pea)
lot n&l1?
+ (1 7m1)
Pa
npp
10y(2w + 1)w
1 ||a5t211
F:
np2
+ +E |115 -11-----((0""" (((
+ pE
1
|| 4+ \/(
E f(a²) - 2/2 ||
(2)
1
L
||_|1 - 2² || + 7 || 2
(277 22
2
+ (1 -744 27(2w +
1) +1)
E [llo* - -h'l1"] (1- - 714) 42 + 1) Ps Pua)
1
E
Pa
npp
72
10 + 1)
(1 - Prage) T
26
E
2f.2
|1
x² 112
||
mp3
B
Ppage
2 (ph- Paa) L2
(1 Pagge ) Linxx
2F
| - -211
np?
nppBB
2 (Pa
Pau) bb
b )
+
M Vf((="))1 + Ppage
1
(1 Ppage)
n² Ppage
Ppage
1=1
2 (1 pa) 2
(1
Prage ) Mnaxx
pF.
1 - =0yl?
Pa
BBB
2 -P.) 82
(1
b
2
1
+
Ppage
+ (1 Ppage)
| -
PaPpage
Ppage
72
After rearranging the terms, we get
E. [[[[attt)]
22w + 1)
F.
47((2w + 1) Paa)
F.
1 n
Σ
11 +1 n1 18t2113)
Pa
nph
+vE |11-- v ( 11
+ +p
|| 1 v
SE [f[((=)] - - ||| ||
+ (1 - 7/41 22w2w + 1) E |100 - n1|13]
47<( + 1) Pa Pea)
Σ o16 - n3l1?
+ (1 710)
Pa
npp
72

---

1
L
10yz0 22x + +1)
22 + (1
Ppage )
27
Tip5
B
2 (Pn Paa)
2
(1
Ppage Laxx
2(1 Pa) Dz
(1
Prage L max
E [1aott =2'1²]
p
nyz
npp
Pa
Pa
Prage (1-
2
7 +
+ (1 Pruge)
E
lite [
Ppage
2002 ywl 2w + 1)
2 (Pn Paa) b²
repi Ppage
n2p22 Ppage
+ p
2
Pa) b²
+ Ppage
1
+ (1 Ppage)
E Σ
| v)(
PaPpage
Ppage
Due to
Pa 2-pa
Prage: one can show that
Prage
(1
2
+ (1 Prase)) ) s - b. Thus,
Ppass
we take V
2%
then
5:
(1 Peongee )) s 1 -b)=
b
)
b (1-2 2
(++
PPaaee
1
Ppage
therefore
[f(
2-(2w 2w + 1)
14-1-1+112) 4r + 1)
Paul
E
1 n
9
h1 1
Pa
np2
2% E |11 v
12
+ +pE
|
[f(()]]] -
E ||V
E
+ (1 (144
27y2w 1) E |||* - -h²l1²] (1 (1- 7/0)
4r((2w + 1) Pa
Pea
Σ
g. - nill"
np3
72
L
10 1w + 1)
(1 Ppage Ianaxx
2 +
27
2
np²
B
27
Paa
2 +
(1
Ppage L
2(1 Pa) L
Ppage L
||aa
xz
bripa
Pa
B
Pa B
27
|1
vf(z")11
2)
b
200 2002>aw' you 12w 1)
47 (Pa - Pea)
mp2PP Ppage
mpp
2 (1-Pa) 6²
2
m
+ p
+ Ppage
1
+ (1 Ppage)
E
PaPpage
Ppage
n
Next, with the choice of b = Ppppi 2-Do we ensure that
2 Pa) + Ppage
(1
+ (1 Ppage)
$ 51-b b.
PaPpuge
Ppuge
10bry (2
+ 9x(p--Pa) then nog Prage
we take p
1991 Proge
20022ww(2u + 1) 47 (Ds Pea) +p
(1
Pa) b2
b
2
)) <
1
+ Ppage 1
+ (1 Penge)
npppPage
Ppago
PaPpago
Ppage
73

---

therefore
[[((a(t))] 2y(2w + 1) |1gtt1 ntt1 - 47((2w 1) Pa
E Paa)
n
9 +++ n 1 11
Pa
np?
n
+ 2% E. ||1st| -ali-vi [[(x 11²] + (400)) (2w + 8y (Pa Peal
|ntt1
PpgPrage
r.pā
$ E [f(x))] - - ||V
+ (1 - 7/14
27(2w - 1) |110 - 1191 + (1--711 11--10 7010
4r + Pa - Pea)
Σ |1 - nill?
npp
Pa
L
(2w + 11 22 +
(1 Ppage L
27
2
B
27
(2
(
Paa
1
(1
Ppage ) I I
bnpp
Pa
B
(1
400rya (2w
(2w
1)
8y
Ps
21 -1a) (1 Ppage )
12 -2y1-
Pragerage
(1
b 2% E 2 b
{
|1''
(
<00 ( (2w + 8y (Pa Pan)
E
1
Pephprage
Let us simplify the inequality. First, due to b >>- Prazetl
we have
2%
(2 (2(1
Pan
1 + (1 - Ppage )
8Y
(11-
Pan
2 +
(1
Ppage Linxx
bmpa
Pa
B
PppgPaage
Pa
B
Second, due to b S PaPpage and Pmu S 1/a we get
40w + +1
8y
(1- Po
P2) 12 (1 Ppage L2 max
2 (ca)
PppP
Ppppe
40w + 1)
87
Pas Pa
(2 (2(1- Pan
1.2 +
(1
Prage
L2
max
myp
npp2ppage
Pa
B
80y + 1)
Pau
2 +
(1
Paage) L 2
np3
Pa
B
16y
(1 -
Pai
Pa
Pea
2 +
(1
Ppage
T
max
Pa
B
80yw
+
(1
Ppage ) Iiaax
2 +
mpp
B
16y
Pan
L +
(1 Ppago L 1
Pragee
Pa
B
Combining all bounds together, we obtain the following inequality:
[[(((tt)] E
22w + 1)
[110*1 - 10111?] 47((2w + 1) Pa
Pau)
n E
++1
Pa
np2
2% E || V f 111 <E [f((t(]] E [|(
+ (40byw (2w +
8y (pa Pea)
E
1
v.((o(+>>11
nyp2ppse
pppge
74

---

+ (1 710)
22w 1) 10
|l9s 10]19] +(1 (1- 7pe
(~ + 1) Pa Pea)
1
Σ
g
n311?
Pa
nip
7
1
L
100 (2w +1 [
(1 Ppuge mmax
27y
2
npp
B
24y
(11
Paa
2
(1- Ppage L mmxx
Ei [|aet1 - x² 22133]
Ppggs
Pn
B
(1
b
2% b
E
[|
+ (1
6) 2
(
440 (2w +1) 8y (pa Pan)
F
1
Σ
1
V
2
mpp Prage
n2 nppppaage
Using Lemma 4 and the assumption about 7, we get
[[(
22w 1)
[11
---tt-n*t 1111 4>((2w 1) Pa
Pan)
E
n
nntt1l
Pa
np?
n
+ 27 E
||1 v [s( 11 [1]] + 440y (2w +
87 (Pa Paa) mpp.Ppun
1
|ntt1
ny
$ E [f(x)] 1 || (Vvf((²)) ||
+ (1 7744
27(2w - 1) E ||00 - [111] + +(1 -11-7/4 -10) 47 + 1) - Pea)
11 - noll?
Pa
np3
72
+ (1 (1- 2 b
2% E
| - [(=0)) + (1- 2)
[40byw (2w + 1) 8y (Pa
- r Prage
Pan)
E
1 Σ
1
V
PppP
Note that 7
thus s 7 and
2n²
[f(c
(2w 1) 11 1t1 4-y(2w 1)
Paa))
E
n n
19
++1
h
Pa
np?
+ 27 F. || v 5 ((a |12] + (400) (2w + (10
87 (pa Paa) n.p.
1
|
npp2Paage
< E [s(x)] - 13 [|
+ (1 - 7/44
22w2w 1) F. [lo'- - nºll3] -191 + (1 (1)) 47 + 1) - Paa)
11 - n&ll?
Pa
np?
n2
27 + (1 - (1)) b
[||^* |11'' v + -1--7))
[40by (2w + 1)
+
87y (Pa Pea)
E
Σ l
nygppage
It is left to apply Lemma 11 with
ve 2(2w + 1)
E ||lo* 1e]lp] + 4((2w - 11 Pa Paa) E
l1
h?ll
np2
Pa
i=1
2 [[I*- vs(at)]13]
(40mw(22 + 11) |(00)) pppppase
8 (pa Pea
+
+
E
Σ
|
b
npp
i=1
to conclude the proof.
75

---

F.4.5 Proof for DASHA-PP-MVR under PL-condition
Theorem 10. Suppose that Assumption 1, 2, 3, 7, 5, 6, 8 and 9 hold. Let take 20+1
Pa] b E 0.
z-p
-1
y min
L
200w + 1)
(11
b) (1
+ [ +
40
(1 - b)
1
Pas
I
a
b
np?
np4b
B
Pa
2
2/4
and h.t = ge for all i E [n] in Algorithm 1 (DASHA-PP-MVR), then
E [f 1*]
(1 - 7m²=²
Au +
27 b
1140 vf(29)]2 +
(A07)w((WW+) + 1)
8y (Pa Paa)
|
V
np?
npn
1 1000>2 +1) 20b> o²
1
Pa
nB
E {[((tt)))] + (2w + 1)
h + 47((2W + P) Paa)
n
|1 ++ - n! not211?
E
Pa
np²
72
SE f(x²) - 11 (
27 - 2 - ||0 - 201 + 1--11'-vo -V5()')1
27(2w - 1) E |||s* - 161l + (1 - 710
4 (2w + Pa - Pea)
+ (1 - 7144
Σ g - 1&ll?
Pa
12w +
1)w
1
|| 11?
E
mpp
Proof. Let us fix constants v. p E [0, oo) that we will define later. Considering Lemma 12, Lemma 10, and the law of total expectation, we obtain
22w + 1) E [[](tt+)]]
11g 1--1-11 -1+111²]
4-y((2 1)
Pau)
E
n
00
-h. 11
Pa
np?
+E |11--1 / V 11(
+ +pli
1
| 1 2
n
S E f(x') - 7
|| (2,
2 --'1"
I.
2²11 + y 1| {
2
+ (1 -744) (2w 1) [l00 - 10]l3]
(1)) 4r + 1) pm)
Σ go nil1?
12
Pa
np?
n
107(2w + 1)w
1
| ||_
mp?
17
+ +rE | 1011--a(++ >
+ +pE
1
|1 41 \11
n
< E ((x1) - -// || - 2%
L
|| - x² 2 + 7 || {
2
+ (1 - 7441 22w + 1) E |100 - -1'13)
+ +1 73e) 47 + Pa Pea)
Σ
19 - ntl1?
Pa
npp
76

---

10y (2w + +1)
2b
2((1 22(1-b)LL3 L3
-222) ||aft1 - 2011
262
1
Σ
|
Vi(aa)))
npp
11
ob
22(1 - 6) L2
(ps- Pua) I2
|| - =z/1
npa B
npp
+
2 (Pa-
Paa b²
| v.(((')) )1 (1-b)
6) 111 -V/11=-V((+
v)(at)))*
n²
2b 0²
[2(1 - 2111-)2L1g
2(1 - pa)t
||-0||- -2'1?
pE
+
PaB
PnL
Pa
22(1
Pa)b2
Σ | MM-vAtl -
+
+ (1 (1)
b)²
Ph
n
After rearranging the terms, we get
E []]( + +1 (1- 71)) 22(2w + +1)
+ (mm 47((2w + 1) Pa Paa)
E
E
11 ++1 - 1ot111 11
Pa
np2
+E |1 v )(x 18]
11 -
+ pl
I E [f(()=)] - E ||| | 31
+ (1 -74)
(2w 1) 1 ||0* 1ll''~h'' -h'1]] +[1 7m0)
47 + 1) Pa Pea
1
Σ
g
Pa
nip
71
1
L
(2w 1)
(2(1 - b) + 2Σ²
2/
2
npp2
/v ( 2 b)
2 (Pa Paa) 2
2(1- 161-b7 6)
2(1 pb)Le)
(lott
||
+
P
npp
PaB
Pa
(7 (1 b)²) E || - \)(+)))
2002 (2w 1)
2v (pa
Paa) b²
(2(1 Pb)
+ (1 -(1 -1-b)²)
1 ト I v)(
+p
mpp
np²
Pa
206 (2w + 1)
26
26
o²
+ p
np?
npa
Pa
B
By taking v= = 2% one can show that (r + v(1 - b) S 31- (1) v, and
(2w +1)
47 + 1) Pa Pmu)
n
E [[ +(1 7p)
E
1
+ (1 744)
E
|1
10t211 11?
Pa
np²
2% + b
E ||1441 (1(
12 |
V
+ +pE
71
< E [f(()(]] - - |||T((=>)13
2-(2w 1) E ||00* - -h-113] + +(1 11-744 700) 4r.(2w + 1) Pa Pea)
+ (1 (14)
g - A1l
Pa
np3
72
L
(2w +1) (2 2
+ 2i²
27
2
np2
B
77

---

2y
2(1- - L3
2 (p, Paa) I
2(1 b2
2(1 pa)
)) 1s) ||aatt x01
P
+
b
npp
PaB
Pa
b)
2% E |11** |I1'-- -Vf(2')1
1
2
206 2062 22w 1)
4y (Pa Paa) b
2(11 pa)b²
+ (1 -10) ) )B
1 ト InI v
+p p
np2
np²
Pa
2062 2062yw (2w + 1)
47b npa
+ p 2b² o²
+
npp
Pa
B
Note that b S
Pr_ thus
p-p.
200 ywu y002yw (2w 1)
47 (pa Paa) b +p
2[(1 (2(1-pa)
+ (1 (1- (1-b)²) )
np?
np²
Pa
200 yw (2w + 1)
4y (pa
Pau
b
tp(1 (((1-b) )
npp
And if we take p (2w+
sp()-pp)) then nng
+
ny3
206 ywb2 2w + 1)
47 (Pa- - Paa) b
+
+ p S.p
mpp
npp
and
E [f(( + +(1 7/4) 22w + 1)
E
[1ss - 11]
+ (1 744)
47 + 1) Pa Paa)
E
1
Σ
11
++ - 11 |1?
Paa
np²
+ 2% E ||1-t1 - v ff(x*11) |1 + 400 +1 b
8y (pa - -aa)
E
1
-
+
v
npp
npp2
< E [[(((')] B [
+ (1 - 711)
22 + 11 E -h'1]] + +11 +11-700 (1-71) 710
4r + 1)
Pea
E
1 Σ
b9 - A3l1?
-
Pa
npp
1
L
12w + 1)
(2(1 - -b)212
+ 2π
27
2
np2
B
27
22(1
6)² L3
+
1
Pea
1.2
npab
B
Pa
406yw (2w + 1)
87
1
Puu
P.
22(1 b)2
+ +2(1 - pb) E ||act11 x² 11]]
+
mpp
npp
B
+
1
2
b
27 71
E
+ (1 (1-9) b)
/
4406yw (2w + 1) + 87 (ps Paa)
E
|
- V/(
npp
n1
(w + 1)
47b npa
4406/a(2w + 1)
8y (Pa - Paa)) )
262 o²
np?
np?
np3
Pa
B
Let us simplify the inequality. First, due to b S Ps and (1 pa) 1 (1
Pha
we have
p1
(2w
+ +1
2y [1
Pm
2(
b) 2
Ps
+ 8(1 - P3)
+
npp
npp
B
78

---

(2 (2
[2 - 2211-b)213
+ +2(1 tp))
npp
B
8y
1
Pe)
(2(1 1)2
+ - pa)
+
np?
B
40nw (2w + 1)
2((1 b)2L3
+ 27?
npp
B
+
87
22(1
b)2
+2
1
Pm
i?² 11)
npab
B
Pa
therefore
E [[(((t]] + +(1 7m)
27(2w + 1)
E
|1g + (1 - 711)
47((2w + 1) Pa
Pau)
E
11 of+
|
Pa
nph
1=1
27 E. |l1nt2= - V 5 ((x |13] + + b
(20 +1) 87 (Pa - -Pam)
1
E.
V
np?
np2
< [E[s(=0) 25 || ||[]
+ (1 -74)
22w + 1) E |10' - -111?] (1 (1-710 710)
47<( + 1) Pa Pea)
E
1
Σ
llft -
Pa
npp
72
1 L
50yw (2w + 1)
22(1 b)2
+ 2f.²
2-
2
np?
107
22(1 - b)2
2 1
Pna
1:2 F.
|1,4t2 =x(1²]]
npab
Ps
b)
2% E 11' - [ + (1- b) 2)
(
(406ya (2w + 1)
87 (Pa Paa)
1
1
E
|
b
npp
np?
n
2002 2002yo
(2w 12w + 1)
4yb
(400)/ (2w 1)
8y (Pa Pua)
2b²
0²
np?
npa
np?
nip
Pa
B
$ E [f(x0)] E [|
+
(1 - 7144
(2w + 12 F. |110* - 1-113] +11 -10
47 + 1) Pa Psa)
Σ
1661 -
-n?l?
Pa
naph
n2
L
100 +1]
(4- ((1-b) b)))2
+ T22
27 2
npp
B
207
(1
1)
+ (1-
Pea
9.2 T:2)
| - =001(3]
F.
npab
B
Ps
b)
n% b
E |1 V + (1- 2
b)
( (40byw (2w + +)
87 (Pa Pan)
1 n
+
E
Σ
|
Vf(
2
np?
np?
n
200
(2w + 1) np2
4yb
4400m (2w 1)
8y (pu Pra))
2b²
raaa
np2
npp
Pa
B
Also, we can simplify the last term:
400y (2w + 1) 87 (pa Poa))
262
np?
np?
Pa
1662, >
1
+ 1)
Ps
npp
npp
79

---

30622wo( (2w + 1) 166y
npp
riPa
thus
E [[( +(1 - 7m2) 22w + +1) E [|1 - =+]] + (1 (1-11) yu)
47((2w + 1) Pa
Pmm)
E
n
|1
- 115 11 |
Pa
npā
2% E ||10t1 - ( ||1] b
+ 420rw((w + 87 (Pa -Pa))
1
E
|ng
V
np?
r2p
n
iml
s E [f(')] - 13 [|(
22w 1) E ||10* |10'' + (1-
4r.(2w + P1 Pea
1 Σ
+ (1 -744)
- 710
Pa
np3
n2
1 L
100 2w 11 ((1 -1]-b)22 1
+ T,2)
27
2
nph
B
20y
(1 - [1-b)811, 1)
+ 1
Pea
1 E
12 - 12411=
napab
B
Pa
2 b
b
2%
I11 - vf('')1?
+
(1-
= (
/40bya (2w + 1)
npp2
8y (Pa Paa)
nyp
E
1 12
Σ
|
v
(ww + +1
20yb) o²
+
upa
B
Using Lemma 4 and the assumption about 7, we get
E [[ + +(1 19--100 714)
27(2w
+ 1) E
|1ght1-1 + (1 (1-71) 714)
47((2w + 1) Pa
Pan)
E
|| l 1 1 |
Pa
np²2
+
27 b
E |11442 - v f(x
+
420 +1)
87 (Da - Paa)
E
1
V
np?
npp
n2
E [f(a')] 2 -315 || f ||
+ (1 - 774
22w + 1) E [lo' - -11]3]] ((1774) 47,(2w + +1)pa - Paa)
E
1
11 - -mtll?
Pa
np?
12
(1 1 b) 2 E. |1 v((=t)]
2)
+ (1-2) 2) (
+ (406yus (2wr
87 (Pa
Poa)
E
1
Σ |
V
2 b
np3
np?
n
100 + 1)
+ 2070) a²
np?
npa B
Note that
b 7 2n² thus - s 1 7/4 and
E [[[[(ttt)]] +1 7m1)
22w + +1) F. 11g+t1nn00
+ (1 7y11
47((2w + 1) Pa
Paa)
F.
n
110 + n 11?
Pa
np3
+ 2% E ||15t11 - v ( 1|| +
[406)w(2 + 1) 87 (p. -Pa))
1
n
E
h
1+4
-
npp
np2
n2
< [f(()))] - - || [|
+ (1 11-7/4 7441 27(2w + 1) |1o0 - n1113] + (1 - 710)
47 + 1) Pa Psa)
Σ 1 - -m:1?
Pa
npp
n2
80

---

(1 740)
2
b
|1 vf(xz) 18]
+ +11 (1-Tw)
(40by (2w
nng npg
Byy (pa Paa
Σ
np2
n
yw0 +1) + 20yb o²
nip
niPa
B
is left apply Lemma 11 with
2(2w + 1k'1= + 4((2w + 1) Pa Pus)
ve
llf - kill"
Pa
71
E |1 - + (40bw(2ww + 1)
8 (pa Paa)
+
+
E
Σ ||
v((('))
npp
npp
and C (1000>
20b o² to conclude the proof.
19 Pa
Corollary 5. Suppose that assumptions of Theorem 10 hold, batch size B
S mmin
Paypeen
take RandK compressors with K =
BBdype
TTen the communication complexity equals
δ do
dLa
Pay PEN
PaP/R
and the expected number of stochastic gradient calculations per node equals
0²
oLo
PalinE
Panipi/aee
Proof. In the view of Theorem 10, DASHA-PP have
w + w
L + J
w Pauynn
[
Lo VB)
[+t Lo
+
Pa
u B
PapnnB
Ve
vB)
communication rounds in the stochastic settings get E-solution. Note that K O
PLyn
Moreover, skip the initialization procedure and initialize h! and of. for instance, with zeros because the initialization error under logarithm. Considering Theorem 6, the communication complexity equals
+
K
w
KK
+
o²
+ - + K- w (I+
-_=
Lig VB
+ K-
L+
Lo VB
Pa
Pa
unE
B
PaumeB
1 Pall/n
VEB
K
w
+1
K
w
02
K-
o²
KL +K K-K
i+ Lo
+ K
oho Panuulaa
Pa
Pa
unEB
PapnEB
H Palu/n
VB
d
Ko²
dL
d
(I+
L
Kal.
+
+
Pa
PaunEB
PaHl/T PaHLT
vB
Panpola
VEB
d
da
da
dL
[[+
L vB/
dl.a
+
Pa
PaN
Pay d.L.
PaPyT
PAHVT
PaHA/T
do
PayMET
The expected number of stochastic gradient calculations per node equals
w +1
Φ2
L +
W
[
La
[ Le vB
+
B +
+
B
Pa
pnEB
PaumB
Pauyn
vB
Va
VeB
81

---

0
B
+1
1
+
B
w
o²
B
o²
+ B
+ +B- w
[ La
+ B
La VB)
1/a
Pa
ums
Dalmn B
Pallyni
vB)
PampiRaaER
Bd
Bd
o²
o²
B P
Bd
(I.+ Lo VB
oLo PaTILiTaVEE
Kp
Kp
uneB
PalinE
Kpalynn
d²
02
Tl.
I T.o
TTe PanuulV
Pa PEn
Palenv B
Pajie
PatelaVEn
Pate Ven
vB
0²
LGr
PajinE
Panueaa VE)
82

---

G Description of DASHA-PP-SYNC-MVR
By analogy (Tyurin and Richtárik, 2023), we provide "synchronized" version of the algorithm. With small probability, participating nodes calculate and send a mega batch without compression. This helps us to resolve the suboptimality of MASHA-PP-MVR w.r.t. w. Note that this suboptimality not a problem. We show in Corollary 4 that DASHA-PP-MVR can have the optimal oracle complexity and SOTA communication complexity with the partieular choices of parameters of the compressors.
Algorithm 8 DASHA-PP-SYNC-MME
1: Input: starting point x E R stepsize y > O, momentum a E (0, 1], momentum E 1], probability Pmega E (0, 1], batch size B' and B, probability Pa E (0. 1] that node is participating number of iterations T
2: Initialize g. h on the nodes and gd = D df on the server
3: for t. = 0, ....., --1 do
4: x x++1 x² 77
5: cl-1 1, with probability Pmega
10, with probability 1 - Pmega
6: Broadcast x. ,x all participating" nodes
7: for = .,...,72 in parallel do
8: if 7thh node is participating then
9:
c = then
Generate i.i.d. samples (ett y' of size B' from D;. & 1
fi (x ett]] B En
fi('''
et
b prop
(n1 $ Enn v
m
++1 1 1++
(g) h!)
else
14:
Generate i..d. samples { 1==1 of size B from Dj,
15:
kL+1 B m C.
Σ [i(xtt1 c 1/2 Σラ Vi(ct)
16:
k
++1
(g) kt)
Po p.
17:
end
18:
h
1 + 1 bt+l
19:
9, [+1
of m ++1
20:
Send m,
++1
to the server
21:
else
22:
h h
23:
m ++1 0
24:
g. 4+ gi
25:
end if
26: end for
27:
ge+1
= ==" + Ei m ++1
28:
end for
29: Output: 3ff chosen uniformly at random from (x²) T=)
k==
(a): For the formal description see Section 2.2.
In the following theorem, we provide the convergence rate of DASHA-PP-SYNC-MMR.
Theorem 11. Suppose that Assumptions 1, 2, 5, 6, 7 and 8 hold. Let us take a 2w+1
ParroTa
2 probability Pinega E (0, 1], batch size B' 2 B 2
-1
8 (2w + 1)w
1 +
f2
16
(1-
Pmu
1 +
L2
npp
B
rtPmeguP2
Pa
B
83

---

and ho g for all i E [n] in Algorithm 8. Then
1
1(1
|
1
2
+
4
|1
Vff(2))
n Pa
Σ ||n v=f((=))11
T
7
PmegaPa
TiPmezaPa
71
12
nB
First, we introduce the expected density of compressors (Gorbunov et al., 2021; Tyurin and Richtárik, 2023).
Definition 12. The expected density of the compressor Cj is Çc, == sup E (x) where | is the number of nonzero components of E R Let Se max;g[1] Sc..
Note that Ce is finite and &e s d. In the next corollary, we choose particular algorithm parameters to reveal the communication and oracle complexity.
Corollary 6. Suppose that assumptions from Theorem 11 hold, probability Pmega min
Sc d
neB 0²
butch size B' = + and i.! = = Bun
E
Bas k=
Vi(x""; Suk) for all i E [r)) initial butch size
Bunt
O
B + max {
/pulee Vpinc }). then DASHA-PP-SYNC-MYR needs
Bd o²
Parga
A
w Payni
[+ Lo
i
Lo B
T = O
L+
+
+
+
pāSon
VB
Paven
VB
VanaB
communication rounds to get an E-solution, the expected communication complexity is equal to O [d+ (cT), and the expected number of stochastic gradient calculations per node equals O (Biit BT),, where & is the expected density from Definition 12.
The main improvement of Corollary 6 over Corollary 3 is the size of the initial batch size Bui- However, Corollary reveals that we can avoid regimes when DASHA-PP-MVR is suboptimal.
We also provide theorem under PE-condition (see Assumption 9).
Theorem 13. Suppose that Assumptions 1, 2, 3, 5, 6, 7, 8 and hold. Let us take a = 2w+1
b Pa P-
probability Pmoga (0, 1], batch size B' > B 1,
16 (2w + 1)
L2 B
48L2
24
Pai
1.2
7 S min
L+
+
D2
+
+
Ps.
npp
TePmeqa
T2PmeegaP8
2p
2p
and Ky 0 for all i E [nx] in Algorithm 8. Then
E [f(x²) [*]
< (1 T
27 Do + b 1
1 8y (pa Paa) 1111
| v((e=)))
200²
B
Let us provide bounds up logarithmic factors and use (.) notation.
Corollary 7. Suppose that assumptions from Theorem 13 hold, probability Pmeza min
Go d
a batch size B' = j then DASHA-PPSYYC-MWVF needs
= δ
w w+1 +
+
PaumaB +
+
w
La
Vd +2) + Palt + Pan
)
(
Lo + +2))
Pa
PaSe
PaHVn
/B
VB
84

---

(w) (holds for the RandK compressor), then the convergence rate of communication rounds to an E-solution, the expected communication complexity is equal to O (CcT), and the expected number of stochastic gradient calculations per node equals OBBT), where Sc is the expected density from Definition 12.
The proof of this corollary almost repeats the proof of Corollary 6. Note that we can skip the initialization procedure and initialize hi and gf for instance, with zeros because the initialization error is under a logarithm.
Let us assume that d = DASHA-PP-SYNC-MO
+1 o²
L Palyn
(Lr + T.) VB
Los
Pany + (
Lo ( VB + +
+
(34)
Pa
PaumEBB μ
Comparing (34) with the rate of DASHA-PP-MVR (31), one can see that DASHA- improves the suboptimal term P2 from (31). However, Corollary reveals that we can escape these suboptimal regimes by choosing the parameter K RandK compressors a particular way.
G.1 Proof for PP-AA--PPYSN-
In this section, we provide the proof of the convergence rate for DASHA-PP-SYNC-MWVR There are four different sources of randomness in Algorithm 8: the first one from random samples g!+1, the second one from compressors {C.)- == the third one from availability of nodes, and the fourth one from c++1, We define E& [.]. Ec [-], Ep, [:] and Exucess [:] be conditional expectations w.r.t. g!+1, {- availability, and cf+1 accordingly, conditioned on all previous randomness. Moreover, define E [-] to be conditional expectation w.r.t. all randommess in iteration + conditioned on all previous randomness.
Let us denote
B'
B'
1
b
Vf
fi (x
et+1)
h
V Vf (
Sik
B'
B'
Pmega
B'
k=1
k=1
B
k+11
V
B
j=1
1
+++1
th node participating, otherwise,
1141
h/
h
+
1.41 7th node participating, otherwise,
M4+1
1,2
1,2
h/
of
11+1 1,1
(of M)), th node participating, otherwise.
o0 + C.
1
11411
a Go! - nt)
7th node is participating, otherwise,
1,2
0
h1+1 E 1+1 ho+1
1 Em 1 g 2+1 = E Pil
and of
E 8
Note, that
11411,
cl+ 1, 0,
h++1
d+l 112t1
and
( ++1 d=1==1 =
g1
1+1 cl-1 = 0 1/2
First, we will prove two lemmas.
85

---

Lemma 13. Suppose that Assumptions 3, 5, 7 and hold and let us consider sequences {g; 1+1 1 and (
12+110 ) Fi=1 from Algorithm 8, then
Ee
Ep. Eyp
[11o
11 11]+
< (1
Pmega
| +
(Pa-Pun Paa) a²
2 2(1 Pmeeg)) a²w
Σ 9 - nill"
+
P22Pa
12
n²pr
i=1 + (1 - (1-a))216 h91?
and
E Prnso |1 ++1 11 [1]]
Ex
Epp
2 (1 Pmeea ) w ||,.,2112
(" Pa)a² (
2
Pimega) aZw
Pa
Pa
Pa
+ (1 a)²
100 - -hill?
Vi E [n].
Proof. First, get the bound for Ex+1 [||o - -h
En [Erazs [11.43 [110+t-14** 11+11 (2]
Ec
Pmoga Eyg [|99 hit 11] + (1 Pmoga Ec
Ep.
|
h2t [1]]
Using
Ep. 4+1 - 11,11
of + K
(1 a) (gf - 11) (of - h2) - 118 M
and
Fee Eep. 1
h h
of + k a (g) h:) M 1 (1 a) (g) -h()
have
|1 h2+11 []]]]
Ee
E
E Epneg
(16)
[|1g] hit1 Ep, [9] 1 h1+111 [1]]]
Pmoga Exp.
+ (1 - -Pmega) ) Eec Eyp
++1 h2t1 E.p. [9b n12 1 ]|]]]
+ (1 a)² ||g2 11112
We Lemma
two times with i) r, 9 - h1 and s; -a (o) h2) and ii) r; of - h and
PaC;
[
P. (of h&) 4.2 to obtain
Pa
Ee Epp E Expnep [||9 h++1 |
Pinega a² (pa
Paa)
Σ
llof - hell
n?p?
i=
(of nn)) 11))(²))
+ (1 Pinega)
F&c
PaCa
- 10+1
a (o)
n!)
(R
n2 p2 i=1
Pa
Pa
a² (pa
Paa)
l1of - n&ll?
+ (1 Pmmega)
p2pp
mm
+ (1 a)2 ||g5 - 11=11
a² (Pa Paa)
n1
l1st 16l1
n²22
i=1
86

---

(1 Pmoga)
Pa
Ec
c+
1
k.2
(gf
n2)
1
4.2
(gf
11
112 i=1
Pa
Pa
Pa
Pa
(1 a)² 119"
-1111
2 (Pa Pan)
|19
n Pd
(1 Pmmcga) ) Paw n12
2
k,2
(of - k())
Pa
(1 a)² >11
1²1l
a² (pa- Pua)
Σ
|1st - h!ll
n2222
i=1
(1 Pmnega)
w
| a (9) - -h:]l
p22pa
+ (1 a)² |19 - 1²11?.
In the last inequality, we use Assumption Next, using (15), we have
Ec
Epp
-
<
2 (1 Pmogga) w
12 1 + ((aa-Pa)
-Pa a² 2(1 - Pmoga)) wa?
n²12 +
Σ 11 - -|ll?
n2pp
n² Ps
+ +1 a)² 1
111
The second inequality can be proved almost in the same way:
Ec
Ep.
|10,
|| - n1,t/11 [1 + (1 Punegl Ee [Epp [1 11 |1]]
-Pmega Ep.
(16)
Pmega Exp. |102,11 1+1 - 11.11 (1 -a) a) (of -
11-)1))1 n=))1²] + (1 Pmega EC Eyp.
1100,,2 N, []]
Pmogal (1 - aa)211 ||9/ -1112
Pmoga 1 pa)aa
|1ot 1tll2 + (1 Pmogga) Ee Ep. |19 ++1 - n 11]
Pn
Pmogal (1 2=² 1191 hill
(16) Pmogal 1 p2
|1 h&ll + (1 Pmogga) Ec Ep. [19, 11,57
(1 - a) (gt - -n1) 11) [1]]
(1 a)2 0191 - -1211
Pmegal (1 pa)
11 h?ll
Pa
+ (1 Pmogaa) E.
01 + C.
1+1
(gf h?)
h + 1 [ ) (1 a) (ot -ht)
Pa
Pa
Pa
+ (1 Pmogga) (1 Pa) I1gt - ht - (1 a) (o) - h²)ll
+ (1 2) 1191 - 11?1?
Pmegal? (1 a2)
ع6اا - 16:l1
Pa
27
(g) h?) ) -
+ (1 Pmoga) E.
C.
k
a (g) h2)
Pa
Pa
87

---

(1 Pmogga (1 Pa) a² |1 kill
+ (1 a)² 119i - 1151 11
(16)
Pmega (1 p2)
(1
Pinega) ) (1 - Pa) a²
11g, -hill
Pa
Pa
(1 Pmegaa PaEe
C2
1
(9) h?) -
(g) kt)) |
Pa
Pa
Pa
Pa
+ (1 a)² 166 - hill"
(1 - a
199
1ill?
Pn
+ (1 Pmoga) Pa Fic
c.
a
(of
h;)) -
1
a
(gf M1)
1,2
Pa
Pa
Pa
Ph
(1 a)² |19
1111
aa
9 h
Pa
Pmoga)
|14,2 a (0f A3)l
+ (1 a)² 1111 - hill
(15) 2 (1 Pinega) |KE + (1 pa)aa
2(1
Pmogga a²w
1191 hg
Pa
Pa
Pa
+ (1 a)² o1o - -hil1²-
Lemma 14. Suppose that Assumptions 3, 5, 6 and 8 hold and let us consider sequence {h 11++1 1 from Algorithm 8, then
[| (((
Es
Ep.
202202
2Pmmega L?
(1
b
(1
Demoga) L'
2 (pa Paa) 22
|| 2211
n-PmeyaPa
mp,BB B'
Pinega
np
np?
2 (pa- Paa) 6²
Σ | Vf((=')11
Pmeea 1
+ (1 Pmeeaa)
| (f('))??
n n22 Pmega
Pmeza
E2
Exp,
Fypaoo
[|nst1
[1 |1
26202
22Pmegu I.2
(1
b
Pmogo T2
2(1 Pa)L
|1 20:12
B' +
PaPmoga
B'B'
Pioega
B.B
Pa
2 (1- - -Pa)
b
1/ Vf((+")112
+
Pmegu
1
+ (1 Pmogga)
| (f(=')(('))1
vi [n].
PmegaPa
Pmoga
and
L2
Ex
|
123 |10011 - =011 Vi E [m].
Proof. First, we prove the bound for Ex Ep, Epacps [|15t1- V [|]]] Using
Eg [p. []]
88

---

)
b
1
hi Es
ct+1
h1
Σ
B
B'
Pinega
B
b
hτ + Vfi(x*t1) Vii(a*)
(M - Vi((t))
Pmeeg
and
Ex Epp. [h(,22]
1 B
B E
= -M + Ex
Vii(=' (
B 1=1
B j=1
= no + Vf((x(t1) vf((x'))
we have
Eg
Epp
E
Epuas
11 1 V fz(
|/tt1 ( [|]]]]]] + (1 Pmega Er Epps
|| [
Pmmea Ex
Ep
(16)
Pmega ER
Exp
|1 - Ex Ep. |11 +f+11 [1]]] + (1 - Denggl En En [1n5tt
En En
[n1t]]
"| []]]"]
b
+
Pmoga
+ (1 Pmoga)
|11' vf(z')]²²
Pmoga
We can use Lemma I two times with i) r; = ht and s; = K and ii) ry = nf and s, k to
obtain
Eg
Epp
Ep
Eppne
[1tt1
Pmega
n2² n22Pa i=1
Ex
E& [KST"
Pa
n p2
Pmu
fi((t++)) - -V((()))
Pmega
b
(n
V
(1 Pinega)
1
Fxe [ F. [11
Pa Paa
[ -VA(G0)11
n.Ppu
p2
i=1 b
(1 Pmocpd)
| |
Pmoga
Pmeea
(15) Pmega
Ex || - Ex [1(
n2
i=1
1 Panega
Σ Es [| - Es [M,,"111
n1 Pa
2 (Pa- Puu)
p2
2 (pa- Pau) 62
| v)((21)11
Pmocga
1
b
2
+ (1
Piocga)) )
(Vf-(((a'))
n2² 122 Piggg
Procga
(35)
Let us consider Es
||
Es [M]1111]]]
E,
|
Fxx
12+1
22
B'
B'
B'
E.
1
fz
v fz
et+1)
b
h
1
Σ
sl41)
B
B
Pmega
B
k=1
k=
89

---

(Villott) Vfi(=')
b
(hç v(((zz))
Pregg
Ex
:
B fi(x'; ( (
v f(
B'
Pmoga
B
(i(( vf(('') +
(Vf((='))
Pmega
B'
Ex
( v(((('+1))
B
Pmega
k=
(Vi((z' ; ( V fi(a' - (V -V/((=tt)-VV((((t))
Prnega
where we used independence of the mini-batch samples. Using (15), we get
Es
|
Ex
[1]
26
13
En Vii ( - v.(((t+t))11
B
k=1
2
Σ E. Vi (
Viil''; sttl) (Vii(tttt) V.A(()))
B
Pmegg
Due to Assumptions 5 and 6, we have
Fx
E&
-
21202
2
b
2
|,,21 - 0012
(36)
B' B'Panega
B'
Pinega
Next, we estimate the bound for Eg
[| Es [M
F&
F.e
[1]
B 41 (
Ex
1
Σ f( (V -VA(+*)
B
B3
- (VSi(ott)) V.((a)))11]
Ex
B²
Due to Assumptions 6, we have
L2 || -2112
Ex || Eg [
11']
s
(37)
Plugging (36) and (37) into (35), we obtain
Eg
E Epang
[h+t1_
P.
Pmega
21
2L2
|la0t22 2013
+
1
nt,
B' "Pinega
B'
Pinega
(1
Pmnega)
12221 - 2²11
13
2 (Pa Paa)
n
90

---

2 (pa Pea) 6²
Σ |
Pmoega [
b
2
+
Pinoga)) ) Vf("))()))]'""
n²2z n2222Pmee
Proega
Using Assumption 3, we get
E
Pp
||att1
(((
||]]]]
26²0²
Pancca T2g
b
+ (1 Ponega
1.3
+ (Pa Paa) I
| - x² x²1
B'
Dinega
rupa B
np
2 (Da Paa)) 6²
|
V (x
Pmeea
+ (1 - Prnega)
110'- -V(()')
n 12P2PPmege
Prnea
Using almost the same derivations, we can prove the second inequality:
Eg
Ep.
Eprap
|
f(((
PPmega Fat
[+1
Vss(a! +1 }]]]]] + (1 - Pmnega) Fd Fip, [1 - V
(16)
Pmoga Ex
Exp
| - Es Ep. [
[[]]] 1111
+ (1 Ponogal Ex
Ey |1 - Es Ex
[
b
+ Pmnga
+ (1 - Pmoga)
||4 - Vfi(=')]1
Pmega
m + - k.ttt - (hg + Es (x(tt])
Da
(1 Pa) 1|g - (nt + E& [xst
+ Pmega
|| |33 Pa k1 (1 + Es |4 1)
+ (1 Pinega) Po
(1 Pimegu)(1
- Pa) ||n! (h1 + Es [Ktt''))]'
b
|Pmaaa
+ (1 - Pmmega))
|| Vf(
Pmoga
- kit - Es [kttt]] |
1
Ex
Pa
+ Pmega
(1 Pa)
Vi((((t1) - V((('')
(bt - vs((a())
Pmega
| -katt E& [M=
+ (1 Pmmgg Pa
(1 Pmmoga)(1 Pa) Vi vf((2')1
b
2 (1 Pimppe)) [n(-va((''))
Pmoga
Pincga
(16) Pmoga Fit
[1 FAx 111
(1 Proega)
Fix
|| Feg. [A4
Pa
Pmeega
(1 - (Pa)
V (((( - - b
(o) - Vs((at))
Pa
Pinega
Pmega) ) (1
Pa)
[.((+++1) - [
Pa
91

---

b
(1 Pmocza)) 1|4 1 vf((t')l
Pmoga
Pineza
(15)
Pmeza
Ex ||
Ex [k 111
Pn
(1 - Pmncga)
||15,27 Es [ [1
Ex
Pa
2(1 Pa)
[[i(x(t)) - vsi(z')) I
Pa
2 Pa) b²
b 2
1 v)((at))1 +
Pmega
1
+ (1 Pmegga)
|1n - vf((z')]'
PmegaPa
Piega
Using (36) and (37), we get
Ex
E
E
Prop
||n
)|
26 0²
2Pmcca
1 - x²11
+
PaPmega B
PaB
Pmegg
(1
Pmega) I2
|| 11-1-00 x211
PaB
2(1 Pa)
VV((z (2
Pa
Pa) b²
b
2
1 vf((=')|2++ +
Pmngaa
+ (1
Pmoga))
||nt (f((2')]1
PmogaPa
Pinoga
Next, due to Assumption 3, we obtain
[|nst1 (ia(ttt)]|
Ex
Epp
2620z
P2neee I
(1- b
(1 Pmega
2(1 pa)Li
| =²l1
+
PoPmeya
B'
BaB'
Penega
P,B
Pa
21 (11-aa)
b
||n
Pinega
(1
Pinega)
1 VSi(2')11
PmegaPa
Prnega
The third inequality can be proved with the help of (37) and Assumption 3.
Ex
(16)
F2
[14711 - E&e [M + |/(a(t)) - VA(a'))1
2
- -1'1 ||
+|V vf((21)12
L2
+ LZ) |aatt_=z11"
B
Theorem 11. Suppose that Assumptions 1, 2, 5, 6, 7 and 8 hold. Let us take
2w+1
b PaweoP
2 probability Pmoga E (0, 1], batch size B' 2 2
5
8 (2w + 1)w np
1.2
L2 B
16
Pea Pa
1,2 +
12
T&PmegaP5
B
and hi of for all i [n] in Algorithm 8. Then
4 1(1
1 ||3 <
2
Pai
n
|1:00
11
(=((21))12
T
PaegaPa
TiPmeguPa
92

---

12o²
nB
Proof. Due to Lemma 2 and the update step from Line 5 in Algorithm 8, we have
Es41
[
$ E141
f(x²) ?
Vf(2')/1
L
|
x²11² 2 2110' 1 |
2
27
2
2
E
f(xl) 2/2 Vf(29)|1
L
|| =²I|² + 2 =
h²' + - - V Elgg =
27
2
(16) S Es+1
2 [(x²) 2 |[
1
T.)
|| =''l + + (119) w'll + +1 v
2
2
Let us fix constants K, 7) U, P E [0, oo) that we will define later. Considering Lemma 13, Lemma 14, and the law of total expectation, we obtain
n
E [f(x(t)]] <E [110+1 1 1
9
/E
| \((
+ pE
| ++
n
$ E. f(x²)
7
||
L
||aft1 - 121 + 7 (1l9* - n0ll + 1--ll--vvi -Vr(a))19)
2
2
2
+ +K
F&
Fec
Fype
Fipaepo
||get1
h2+
n
+
+
Ex
Ec
Epp
Exerys
11 +1 - 1
72
+
+vE
Ex
Epp
E
Panzs
|11
f(a > ||11
+
pE
Ex
Epp
E
Expop
| - vi(
n2 i=1
$ E.
f(x')
7
||
I.)
|| - 201 + (10* (102= + 1|1e v)(E))11))
2
2
+ <E
(1
Progza) w
12
+ F,2)
|
npa
B
+ (p. Paa) a
2
Pimega) a²w
Σ 9 - n:ll + +1 (1-a))118 - 10'1
+
n²pp
n2ppa
1=1
2 (1 Pinega) ) w
1
- xz + I22) ||x0t1
+ 17E
Pa
B
( (1 p
(1
Pmmaga a²w
10 htll2 + (1 a)² 1196 - -holl?
+
+
Pa
+ yE
212
+
PPmmaa 1.2 B',B'
(1-
b
2
Pinega) np.B B
I2
+
2 (pr - Paa) 1.2
|| - =211
MPPmagaPa B
Pmoga
np
+
2 (pa-
Paal bb
h - Vf((at))1==
+
Pmncga
b
2
+ (1 - Prnogaa)
110-- - -
n² n2pppPmces
Pmoga
212
12Pmegu I.2 BaB'
1
b
2 (1
Pmegg
L2
2(1 (01ppa) P.)
|| - -2'1""
+ pP
+
+
PaPmoga B'
Pmoga
BaB
Pa
93

---

+ Σ |
2 Pa) D2 62
n
Vfi(+')] +
Pmoga (1
b
(1
Pmooga)
riPmegaPP
Pmeega
Let us simplify the last inequality, Since B' 2 B and
Piecaala 2-Pa
Pmegas we have 1 Pmoga S 1,
Prmega L3
b
Pmoga L.
Pa BB
Pmeeaa
Pa B
Pmega
Pieega)
S 11-10 b,
Pinega
and
(1 -Paa 12
2
Pmnega
+ (1 Pmnega)
$ $1 b.
PmegaPa
Pmoga
Thus
E [[(x xE |11 1--1-1't 11 n
-11
++1 h5 1222112
9
1
+E
|11--1 V ff
+ pE
| + \1(
n
f(x1) - 2/2 [|
1.
||_||1 - =²12² + 7 (19) 1011 + 111e v.(aa))19)
E
KE
2w
L2
12
||
=011
TiPn
B
((w
1) Pa
Paa) a n
Σ
1196 hill + (1 a)²
11g (1-a))110
1011?)
n²pp
2w
L2
+ [23 1100 -2'1" 22112
7
Pa
B
(2w + 1 - pala?
1
n
|1 hill (1 a)² 1101 1193-10 -M21l
+
Pa
n1
vE
21²²0
2T2
(pa
Pam) 1.?
|| 20'11
TiPmegaPa B
12paB
np?
+
2 (pa- Pau) bb
I
V(c(">))'' +(1 (1-bb]lltt- [|('''>((>')1''' V)((3)1))
n P2negaa
1=1
2b²
2T2
2(1 P.2 - x111
pE
PoPmega
PaB
Pa
+ (1 b)
|| V[(
After rearranging the terms, we get
[[(xx++)] + xF. [1g 1,+ [|]]
htt11??
+ F/FF
+1
15t21??
+ 11041-
pE
vs(
71
94

---

S E [f((t]]] - 2 [|V {z*))(
-2
1
L 2kW
L2
+ [2-
2nw
L2
+ 2²2
27
2
vipa
B
Ph
B
2
2 (Pa Paa)) 122
212 +
2(1 Pa)) L22
|||-----a xz x011(]
V
F.
B B
np²
PaB
Pa
7 + K (1- a)²) E ||10* 1 -1
k (2w + 1) Pa- -Daa) a²
(2w + 1 -Pa)a²
1 n
+
+1
+ +11 -a)a)
E
Σ
1o n:
npp
Pa
+ (7 + V (1 - b)) E |110' - {}(
1/ 2 (Po- PPaa) b²
+
+ p((1 b)
E
|M V
np3
2vb2
2pb
0²
+
TiPmogaPa
PaPmoga
B².
Let us take x 2, thus 7 + x aa)² S k and
n
E
[ + IF 1 12]
+ F
|
- n1 11
a
72
+ +vE |1:42 - V (
+ pE
|
I E [f(x')]
- =/ [|]
L
27w
L2-
1.2
2nT
L2
+ 1
+
27
2
anp
B
Pa
B
(
2T2
(p=-
Paa)
) 1?
2T2 +
2(1 p.) ) E || 10]
- -00"
v
+
Bp
np2
P.B
Pa
7 E
[|g' 1=
+
a
7 ((2w + 1) Pa-
Pea) a
17 (
(2w + (2w++1
pada?
+ (1 +1- (1-a) 0)²) -1-00²)
E Σ lost - 13/1
+
np²
Pa
+ (Y + 1 (1 - b)) E [|16 -F(("'113)
+ 1 2 (va= - -Paa) 6²
1
| 1h--vil -
+ p(1 - b)
E
i=1
2v/b²
2pb²
0²
niPmggaPa
PaPmoga
B
Next, since a 2++1 we have
1out1-pale + (1 (1-a) a)2) $ 1 a. We the choice n
Po
((2x+1)p, pp)) we guarantee ((2w-+1)p,,p.) + (200t--p)a² + (1 a)2 npf
S n and
mp3
R. [[(attt)] + 7 (2w +1)
[|get]
1--44111++10 11 1=4111]] + 7 (22 1) Pa= Pea)
F.
n2
g
++1
h 11
Pa
npp
n2
+ +E [| 1-01--((a4t]]1 + +p
1 Σ
|
n
95

---

E [f(x)] 2
[|
1
L
27 (2w 1)w
LL3
+ 1
27 ((2w
11 Pa
Pea) w
(
B + I²2
27
2
npp
B
212
2 (pa- Paa)) I22
2
2(1
pa)
| -
V
+
P
F.
npp
P.B
Pa
7 (2w +1)
||1g* - 11 7 ((20
+ 1) Pa
Pau)
1
l1ot
ngll3)
Pa
npp
72
+ (7 + (1 - b)) F. ||IN [](a")||1
2 (Pa- Paa) b²
1
+ p(1 -
E
Σ
I
npp.Pmeg.
2v02
2pb6
0²
T.Pregaalss
PaPmmgga
B²
E
[f
7 E
[IV
2
1
L
4ry (2w + +1)w
L
+ 1.2
27
2
nph
BB
213
2 (Pa Paa)) Σ2
213 P&B
2(1 Pa) E 1 201
+
np?
Pa
+ 7 72w + +1)
E [110" - 12'1?)
+ 7 ((2 + 1) Pa
Pun)
l1st - ssd1p)
E
Pa
np
+ (7 + (1 - (1-b)) |116* {1(
2 (Pa- Pan) 6²
1 1
+
+ p(1 -b)
E
|
mppppmege
1=1
2pt
0²
T.PmegaPa
PaPmega
B
where simplified the term using pea 2 O. Let us take v = 2/2 to obtain
E
[[
(2w +1)
E
|11441- n
((2w + 1) Pa
Paa
E
12
11
n3
+
|
Pa
np3
F b
| v (5 ||²
pE
1
n
E
[[x'))]
3 || |1
2/4
1
L
47 (2w 1)w
1
+ 1.2
24
2
np²
B
L2
2y (pa- Pau) 1e
222
2(1 p.) )
E [||
| 201
+
bnpaB
bnp
PaB
Pa
7 (2w + 1)
E ||1g' -1'1111 11.113] + 7 ((2w + 1) Pa
Paa)
E
11
n2l1?
Pa
np2
Y2
E
[lI,* {(2)))1?
6
96

---

27 (Pa Paa) b
+ p(1 -b)
E
Σ
lint v
nh
2ybb
2pb²
o²
+
PPPmegaPa
PaPmega
B
22(2e-Pal thus Poop
Next, we take p
E [f + 7 (2w + 1) 1114t1-14+1) 1=1] + y ((2w 1) Pa Peal
12
E
Σ
11
++1
1,
+
Pn
npp
+ E || [ 1|(]]
2y (Pa- Paa) npā Pmppa
\1(
72
$ E [f(xt)]
E
[|
2
1
L
4n (2w + 1)w w
L2
+ I22
2y
2
np3
B
2y (Pa Pea)
I2
2> (pa - Paa)
2L3 PaB
2(1 - pa)
E |110 - 20-11²]
+
+
bnppBB B
bnp2
Prega
Pn
7 (2w + 1)
E. ||o" [Io''
-1'1(11 [1] + 7 ((2w + 1) Pn - Paa)
l1st - nill?
+
E
Pa
np?
+
E
|| [((+t)]
+ 2y (Pa- Paa)
E
||n - (((=+))
b
Prega
i=1
2yb
4y (pa- Pan) b²
0² B'
+
PPPmegaPa
npppri Pmega
Since
Pr 2
< b S PmmggPP and 1 Pa S
Ps < 1, we get
E [[]
+
7 (2w + 1)
E ||| 1 111] + ((2w + 1) Pa Pea)
E
|1 +1 - h 11?
Pa
np3
+ b
E
||1at1 -Vf (((=+t1111
+
2y (pa- Pam)
E
1
n
1=1
$ F
[[(')]
FF
2
1
L
4y (2w
+ 1)w
I2
+ 1.2
2y
2
np²
B
4YL3
47 (pa -Paa) I
4rL32
47 - pa)
||| || - =0(1"]]
E
TtProppaD2
7 (2w + +1)
DE
E [[lo'- - -n-11]] + 7 ((2w + 1) Pa
-Pan)
11st - mill?
E
Pa
np2
+ TE |11-- - -V((+))1 b
+ 27 (pa Paa) E ppggPmega
1
||nt
i=1
6
nB'
E [f(x']]
-
E |V
2
97

---

8% (1 Rea I
L
4y (2w + 1)w
L'a
B + 1.2) -
1y
F. [1aott - 11
+
27 2
nph
TiPreggaPi
B
roPmeyaP? P3
7 (2w + 1)
E. ||o'* -1'1= + 7 ((2 + 1) Pa
1111²]
Puu)
Σ 72
l1o8 - nEll
Pa
r2pă
+ E
|1 | -Vf(('))))
+ 27 (Pa Paa E
|
b
npā
6
nB'
Using Lemma 4 and the assumption about 7, we get
E
[f(
(2w + 1) E - 1(11 + 7 ((2w + 1)Pa Pa
1
Paa)
E
1
||
|
h
Pa
mp3
im1
F b
|
v (
2y (Pa- Pea)
E.
1
11+11
{1(
mp Pmnega
1=1
I E [f(()))]
2 E || |17]
7 (2w + +1)
E. |10' n²1l]]
+ 7 ((2w + 1) Pa
Pan)
E
1
l1,t
nill?
Pa
np?
E [
- VV)(')) +
27 (pa Pan)
E
n
|
b
Pmega
67
nB'
left to apply Lemma 3 with
We
(2w + 1)
E |11s* n091²] + ((2w 1) Pa Pan)
1 n
11ot
n681?
Pa
mph
n2
(
Baa Du
F. || Vs(at)]1
F.
1
M
V
niPaPmega
1=1
and C' = 2 to conclude the proof.
Corollary 6. Suppose that assumptions from Theorem 11 hold, probability Pmoga min { So neB d o²
butch size B' = + and i!! = 5º Bin
+EE Ban k=
[ii(x" (u.) for all i E [m), initial butch size
Bunt O
B θ max {
Vpuse' Vpins }). )²me))
Bd o²
then PASSA--P-S needs
Perge vpu
Do
Lu [T+
i,
Log B
2 VPaneB
=
O
L
+ VV p2sen
+
E
Pavt
VB
Payen
VB
communication rounds to get an e-solution, the expected communication complexity is equal to O (d+ SCT), and the expected number of stochastic gradient calculations per node equals O O Buni BT), where &e is the expected density from Definition 12.
98

---

Proof. Due to the choice of B', we have
Vf
[1]) - T
1
20o
+ V
8 (2w + +
2
L2
16
Puu
2
+
L B
np2
B
TtPancgaP2
Pa
(1
110 f(x
1
12
1
Vf((2)11
PmegaPa
72 7PPmagaPa 71
2x +
3
Using
n
Bun
σ² Tt Biit
[|{2))
Σ
Vf(lo -
Binit
k=
and
1
E E 11
15
Σ
Bun
Vf(l
σ² BB
n
Binit
have
E
V
|11]
1
2Do L V
8 (2w 1)w
[
L3
16
((1
Pma
2 +
L3 B
T
np3
B
T2PingaP2
Pa
80²
Pa Binit
2e
Therefore, can take the following T to get soluunio...
1 c
W
L2
L2 B
T
o
Do
L
12
+
2
np?
B
TDDmegaPhs
TiPreggaPa Buit
Considering the choice of Pmegu and Buit we obtain
d psScn
[++
La VB
i
L
))
A
L+
+
+
+
c
Pavn
Ven
VB
B
TPProgaPP Binit
An
Le VB
Le
2² VansB
0
L
Payn +
V
i
+
Payen
Pay
En
VB
B
The expected communication complexity equals O (d+ (c) and the expected number of stochastic gradient calculations per node equals O (Binit + Bm (1 BB) O (Biit + B).
O (d Pmnea (1 Pmeeg Kc)
99

---

Theorem 13. Suppose that Assumptions 2, 3, 5, 6, 7. 8 and 9 hold. Let us take = 2w+1'
b Parcols probability pmega [0,1], batch size B' 2 B 2 1,
2-p,
16 (2w + 1)
L3 B
48L2
24
I
7 S min
++
+
12
+
+
Pe.
npp
TiPmegaPh
B
TiPmogaals
2/
2p
and ho g for all i E [n] in Algorithm 8. Then
E [[((x)) [r]
< (1 (1-74)" A + b -
27
+
8y (p(Pa Paa)
Σ
11
11n@
+
200²
mpp Prarga
11
Bn B'
Proof. Let fix constants K, 7/ v, E [0, 00) that will define later. As in the proof of Theorem 11, we can get
E [f(z ((1'+1) "] + KE |19 - -1
+ E
l ++1
115 |??
+vB |115 Vf
|||
pE
1
h
i=1
E
[f(x)]]] - F
2
||V
1
L 2nw
L + 1?2
2nw
L2 1?
27
Pa
2L3
2 (Pa Peal L
2L2
2(1 - P2)
F. || 20(1(]]
P
np,B B
np²
BBB
Pa
7 + K (1 - a)²) E |1|9 11-6-11'' -1-13))
(2w + P) Peaa a²
(2w + 1-1 12
(1 -1--))²)
F. 1 Σ
|og n4 1212"
+1
npa
Pa
(7 V. (1 - -b) E |11e vf(a")]1
2 (Pa Paa)) b²
| 1 vi(co\)13
+ p(1 p(11-b)
mp22Pmeee
n
2vb²
2pb² 0²
+
TiPmogaPa
PaPmoga
B"
Let us take x = 27 thus 7 + 16 (1 - a)² < (1 ②) k and
E [f(('+1) + 2% E ||g 1 12+111 ||3]
nE
| +
a
n
+ +vE [1__[114-t4fc
|| 2
+ pE
|
S SB[S(at)
- FF ||{
L 4yw
L2
+ 1?
2mw
I22
+ 8?
27 2 anpa
B
Pa
B
100

---

2L3
2 (pa-
Pea) I
2L3 Pr
2(1 pa)lz²)
) 1s ||attt x11
p
+
rppBB B
11p2
Pa
a
2% E
|lls* 1=11"]]
+
2
27 ((2w + P) (Paa) a +1
(2w + 1 Pa)aa²
(1 -a)²² ) E
1 Σ l1st -
+
np/
Pa
(r + 1 (1 (1-bb)) b)) E ||Ih Vf((=')) |²]
+
+
2 (ph- Pam) 1s
tp(1 b)
E
1
1 - \
Pmgga
2ub²
2pb²
0²
71PmegaP
PaPmega
B'
Next, since a
Ps
we have
-wwt--piaa + (1- a)3) S 1 - a. We the choice f)
Zw+I
Ps
27((2 -1pps-p)) we guarantee >(22++1pp -Paja + (2o+1-pijaa + (1 - -]} S (1 ② and
mpp
mpp
Ps
E [[(
22w + 1)
|1ghh1 h4111²] 27 ((2 + 1) Pm Pun)
E
[ 1 2
Pa
nap2
+ +vE | - v ff(
1|]]
+
pE
Σ | -
n2
$ E [f('')]
E
||| f >1
1
L
87 (2w 1)w
T
+ 1.2
24
2
npp
B
212
2 (pa- Paa) 122
212
2(1 pT)
[|act] x =01
1
+
P
E
13
npp
PB
Pa
+ (1
a)
(2w + 1) F. |10' - htt [1²]
2)
Pa
+ +11-2 2
a)
2 ((2w + 1) Pa Pan) E
1
l1ot n&l1?
npp
+ (7 + v1 - b)) b)) E [||A* [((
2 (Pa Paa) 62
n
+ p(1 b)
E
|
npp Pmnga
2vb²
2pb2
0²
12PmcgaPa
PaPmoga
B
where simplified the term using Pea 2 0. Let us take -= b to obtain
27
E [
(2w + 1)
E
11+111 [10
27 ((2w + 1) Pa Pau)
E
12
11
+1
1,
2
Pa
np?
+ 2% E ||15 - V f
+ +p
1 | /4tt1
Vi(cotti)1
72
<E [f((t]]] E ||[
101

---

1
L
By (2w 1)w
L3
_22
+
27
2
npp
B
47
4y (Pa Peal
1
2 Pa
2(1 Pb) ) E |1
- -0011
bmp,
bmp2
p
Pa
11 2
2)
22w + 1) E. [1o'-111] 101
(1
a
2 ((2w + 1) Pa Paa)
E
Σ
n
11
mill
Pa
2
nap
n
b
2 L |1 vf(x")]1
1 2
b
47 (Pa Paa) b Ppp.Pmega
+ p(1 p(1
-b)
E
Σ |14 v.G
4yb
2pb 0²
nPPmegaPa
PaPmoye
B
By (P, thus
Next, we take p
Press
[f(
(2w 2ww + 1)
11 + 27 ((2 + 1) Pa Paa)
Σ
9
0++1
2
Pa
np2
72
+ 2% b
E ||10 (
8y (pa Pan)
E
|1
n.p Pmoga
n2
$ E [[(x')]]
- F [|V
-
L
8y (2w + 1)
(I2
+ 12
27
2
npp
B
(
47 (Da Peal
I2²
88 (pa Pea)
222 PaB
2(1
Pa)
|| - x 2=11"]
+
+
E
bripB B
bnpA
nepiprece
(1
5)
(2w + 112 |110 -1'11
Pa
+
(1
2
a)
27 ((2w 1)
npp
Pan))
E
1 n
Σ 11st
mell??
+
1
b)
2 E |1Iet - vf(xt))1 b
+ 1
b)
8y (Pa Pea
E
Σ
n
|
- V
2
2
4yb
16y (p. Pua) 6²
σ²
+
nPPoggaPa Pa
np
B
Since
< S Pmeeaaa and
Pa 1
Pe
< 1, we get
2
Pr
E
[[(
(2w 1)
|11gt11- - 1+
27 ((2w + 1) Pa
Pan)
E
n Σ
19. +1
|1? 2
Pa
np2
72
27 F. ||15t1 v5 b
+ 87 (pa pam)
n
+
E
||
Pmega
n 1=1
< E [[('d)]
- B ||
L
87 (2w + 1) w
L2
+ 1.2
2y
2
nph
B
8
8y (p.
Pau) 1.2
16
16 px)
[|aat x²
nPmoggaP?
B
T2PmcgaP3
riPmogap?
nPmagaaP
102

---

+ +(1 a)
27w2w + 1) 10 |19' - 11' 10]1]] + (1- 2 2 ((2w + 1) Pao)
1/110
1 n
nill?
2)
E
Pa
1 2
by
2 E (+("')
+ (1-
b)
By (pa Pau)
E Pmpga
n Σ
|
|
b
2
71
20ya²
nB'
$ F. [f(xt)]
F
||| ||
- 2
+ =2 - 24 24y (1- - Pe
I
1
L By (2w + 1)w
L
Ps
E [|lett - =011
27
2
npp
(B B
1iPmegaD/ B
n1Pmezalls 2
(1-
2
22w + 1) E [100 "1'--n11p 11]
+ (1
2
2 ((2w + 1)
Pao
E
1
>
n
1lst nil??
Pa
npp
n
1
b)
2% F.
|| - V((Et)17] + (1
b)
yy (Pa Paa) F.
1 n
|n
- V
2
b
np' Pmega
20y0² nB'
Using Lemma 4 and the assumption about 7/ we get
+ (2w + 1)g E
[104t1- - -14 + 27 ((2w + 1) Pa - Paa) E
E []
19
n,71 11
Pa
npp
+ 2% b
E ||nstt V ff ff [|a]
+ 8y (Pa Paa) E
1
|1
np² Pmega
12
$ E [f(()) - 2 - || [| [1]]
+ +(1- 2)
27(2w + 1) E [10' |101- 2 + (1
a) 27 ((2w + 1) Pa
Paa) E Σ l1 nall
2
Pa
np?
by
2% F. || - {s(x')] [|=
+ (1
b
8y (Pa- - Paa) F.
| - V
+
1
2)
b
2
npp Pueega
1=1
20y0²
nB''
Due to 7 S a and 7 S b
we have
2p
2n
E [[( +
(2w (2w + 1)
E (1g4t-bb411 +
27 ((2w + 1) - Pam)
E
1
1 ++ - n2t111 11²
Pa
npp
i=1
27 F. ||1+t1 - v ((a [|-]
+ 8y (pa- pas) F np Progg
| - \1
+ b
i=1
SE [E[](a') -3 [||
+ -741 27w2 + 12
F. [loo' [1lo'=~'0 -n1]²]] +1 11-7701 711) 2x ((2w + 1) Paa)
1 n
Σ 11
mil??
F.
Pa
npph
n
21 E ||A'- -V(++))1 + (1) 87 (pa Paa) npp Pmega
1 Σ 1
(1 7u) b
E
n
20702
nB'
103

---

is left to apply Lemma 11 with
Ve
2(2 1)
E [100 - -ht + ((2w + P) Pa
Pmu)
E
11
nGll?
np²
2
E || {((x"))
8 (Da Paa) E
|| Vii(2(111?
+
+
b
npp Prnega
1=1
and C' 20g²² nB" to conclude the proof.
104


Reviews:
[{"review_id": "acoFFq3xb6", "reviewer": "Reviewer_QePY", "summary": "The paper injects existing algorithm for distributed optimisation in the compressed and variance reduced setting with a mechanism for partial participation of nodes. Theoretical guarantees are given in the general non-convex setting, but also under PL-condition. The theoretical results are verified empirically in a classification problem.", "questions": "I struggle a bit to understand the intuition behind Algorithms 3 and 4. For algorithm 3, I don't see immediately the connection with the PAGE algorithm and, for Algorithm 4, I don't see which algorithm tries to generalise. Could you elaborate?\n\nIs it possible to show that the chosen batch sizes of $B=O((L_{max}/\\hat L)^2)$ and $O((L_{\\sigma}/\\hat L)^2)$ are at most $n$? Otherwise, there is a chance that such a batch size is not available.\n\nMinor: there are some issues with the writing, e.g.:\n\"it is not trivial in each order one should apply the expectations\"\n\"We are not fighting for the full generality\"\n\" The main goal of our paper is to develop a method for the nonconvex distributed optimization\"\n\"From the beginning of federated learning era, the partial participation...\"\n\nI would recommend to the authors to go through the text once more and improve the quality of writing.", "limitations": "The authors do not discuss limitations of their work, but I cannot see any profound ones. Perhaps the issue of batch sizes specified in my questions deserves a bit more attention.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper considers the setting of partial participation, which is of importance in distributed optimisation. The setting of partial participation  considered, is general enough to include at least two specific partial participation strategies. The theoretical results match the state of the art guarantees for variance reduced algorithms with limited communication up to scaling of $1/p_a$, where $p_a$ governs the probability of some node to participate in the gradient estimation during some iteration of the algorithm. I find this result elegant and I like that this scaling is pretty much observed in the experiments. The authors give some intuition on why passing from the full to the partial participation setting is non-trivial.", "weaknesses": "The paper is very technical (if one wishes to follow proofs of the claims) and builds to an extensive amount of previous work, thus it is difficult to be appreciated by readers that do not belong to this specific research community. The appendix is about 90 (!) pages and a significant portion of them is essential to the proper understanding of this work, thus it's quite hard to review it in the context of neurips (the results are believable though). Since the topic is distributed computing with limited communication, I would expect a wider experimental analysis of the proposed algorithms in various tasks (also would be good some of the experiments to be in the main text).\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\n> The paper is very technical (if one wishes to follow proofs of the claims) and builds to an extensive amount of previous work, thus it is difficult to be appreciated by readers that do not belong to this specific research community. The appendix is about 90 (!) pages and a significant portion of them is essential to the proper understanding of this work, thus it's quite hard to review it in the context of neurips (the results are believable though). Since the topic is distributed computing with limited communication, I would expect a wider experimental analysis of the proposed algorithms in various tasks (also would be good some of the experiments to be in the main text).\n\n* The flow of our proofs is quite standard for the literature on optimization methods. One can look at the proofs of celebrated optimization methods (e.g. \\[1\\]). We agree that the appendix is large and admit it in Lines 183-187. However, the size of the appendix is justified by the number of new methods that we developed. And, in Lines 183-187, we suggest how to approach the proofs. \n* Our main goal was to develop methods with strong *theoretical* guarantees. Once we've done that, we expect that the developed methods will have the best performance in the analyzed setting with any loss functions, datasets, and parameters. **Note that we added new experiments that are presented in a separate file in the \"global\" comment to all reviewers called \"Author Rebuttal by Authors\".** Click \"Revisions\" if you can not find the pdf.\n\n\n> I struggle a bit to understand the intuition behind Algorithms 3 and 4. For algorithm 3, I don't see immediately the connection with the PAGE algorithm and, for Algorithm 4, I don't see which algorithm tries to generalise. Could you elaborate?\n\nRegarding Algorithm 4, it does not try to generalize any algorithm because it is somewhat new. However, it has connections to ZeroSARAH \\[2\\] which has stronger assumptions on the functions $f_i$ (see Table 2). For Algorithm 3, one can compare it to Line 4 of Algorithm 1 in \\[3\\]: we also use the probability switching technique. However, Algorithm 3 is not exactly PAGE because, with probability $p$, Algorithm 3 calculates $\\nabla f_i(x^{t+1}) - \\nabla f_i(x^{t}) - \\frac{b}{p} (h^t_i - \\nabla f_i(x^{t}))$ instead of $\\nabla f_i(x^{t+1}).$ This modification is necessary for the partial participation setting.\n\n> Is it possible to show that the chosen batch sizes ...\n\nIn the nonconvex case, these quantities can be as large as possible (we can not bound them by $n.$ Note that they are lower bounded by $1$). However, we never say that $B = (L_{\\max} / \\widehat{L})^2.$ Instead of it, we only say that $B = O ((L_{\\max} / \\widehat{L})^2),$ which means that $B \\leq C * (L_{\\max} / \\widehat{L})^2$ for some constant $C \\geq 1$ (This the definition of the Big-O notation). So it is always possible to choose a batch size $B.$\n\n\\[1\\]: G. Lan First-order and stochastic optimization methods for machine learning\n\\[2\\]: Z. Li. et al. ZeroSARAH: Efficient nonconvex finite-sum optimization with zero full gradient computation\n\\[3\\]: Z. Li. et al. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization\n\n"}, {"review_id": "zQzY6Cn2ji", "reviewer": "Reviewer_ZASs", "summary": "This manuscript considers distributed non-convex optimization in the federated learning setting. It proposes an algorithm DASHA-PP that brings three important features of federated learning together: i) variance reduction, ii) compressed communication, and iii) partial participation. The authors derive the oracle and communication complexities of finding an $\\epsilon$-stationary point of the smooth non-convex objective. It is the first method that includes those three important features.\n\nThe algorithm presented in the paper is built upon DASHA, presented in [1]. In particular, in its form in [1], DASHA could work in the partial participation case only when the exact gradient oracle was available. In this manuscript, the authors extended the partial participation property of DASHA to the stochastic and finite-sum settings.\n\n[1] Tyurin, Alexander and Peter Richt'arik. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” ArXiv abs/2202.01268 (2022): n. pag.", "questions": "NA", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "* I think the paper is very well-written.\n\n* The problem the manuscript considers is an important problem for the large-scale federated learning setting, where including all three features, i.e., partial participation/compressed communication/stochastic gradient, is inevitable.", "weaknesses": "* The main technical contribution of the manuscript over [1] is the update rule given in Eq. (9). Similar update rule adjustments are frequently used in bandit optimization literature, cf [Section 2, 2] and [Section 6, 2].\n\n* Besides the new update rule, it seems to me that the mathematical derivations in the manuscript are very similar to those in [1]. In that sense, I find the contribution of the manuscript is rather incremental.\n\n[1] Tyurin, Alexander and Peter Richt'arik. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” ArXiv abs/2202.01268 (2022): n. pag.\n\n[2] Cesa-Bianchi, Nicolò and Gábor Lugosi. “Prediction, learning, and games.” (2006).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the comments!\n\n> Besides the new update rule, it seems to me that the mathematical derivations in the manuscript are very similar to those in [1]. In that sense, I find the contribution of the manuscript is rather incremental.\n\nIn Lines 168-182, we describe the difference between the proof techniques. The partial participation setting required us to rethink the proofs from the previous methods. Note that we had two challenges: *develop method* and *prove convergence.* When you have a developed method and you know that it is a correct method, it is much easier to prove the convergence rate (still may be very challenging though). However, at the beginning of our research journey, we didn't have either the method, nor the proof technique.\n\n\n> The main technical contribution of the manuscript over [1] is the update rule given in Eq. (9). Similar update rule adjustments are frequently used in bandit optimization literature, cf [Section 2, 2] and [Section 6, 2].\n\n* We agree that there are many connections in mathematics. One can also argue that there is a connection to the Markov chain with infinitely many states, where we move to the next state with probability $p,$ or stay at the same state with probability $1 - p.$ \n* But we respectfully disagree that this is a weakness of our paper because our paper and \\[2\\] solve completely different problems. Even if we knew about \\[2\\], how could it help us to design the first step (the update rules of $h^{t+1}_i$ and $g^{t+1}_i$) of (9) from our paper? The connections between (9) and LABEL EFFICIENT FORECASTER from [2, p. 130] are not straightforward except for the fact that they both choose a step based on a random variable. \n\nPlease let us know if you have any questions.\n\n\\[1\\] Tyurin, Alexander and Peter Richt'arik. “DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization.” ArXiv abs/2202.01268 (2022): n. pag.\n\n\\[2\\] Cesa-Bianchi, Nicolò and Gábor Lugosi. “Prediction, learning, and games.” (2006)\n"}, {"review_id": "aLzDVr5ql2", "reviewer": "Reviewer_wGcA", "summary": "This paper introduces a novel method for distributed optimization and federated learning that integrates three critical components: variance reduction of stochastic gradients, partial participation, and compressed communication. The proposed method is shown to have optimal oracle complexity and leading-edge communication complexity in a setting of partial participation. A significant advantage of this method is that it effectively blends variance reduction and partial participation, thus providing optimal oracle complexity without the necessity of all nodes' participation or the bounded gradients assumption.", "questions": "See weakness", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "One of the primary strengths of this paper is the integration of three crucial elements in distributed optimization and federated learning. By encompassing variance reduction of stochastic gradients, partial participation, and compressed communication into a single method, the authors have created a holistic approach that takes into account the multifaceted nature of distributed optimization.\n\nThe authors demonstrate that their method achieves optimal oracle complexity, which is an important measure of the efficiency of an algorithm. This is a significant contribution, suggesting that the method has a high degree of efficiency in processing the data.", "weaknesses": "Despite the significant theoretical contributions, this paper falls short in one crucial aspect, which restricts its overall impact and practical applicability.\n\nLack of Empirical Validation: The major limitation of this paper is the absence of empirical experiments to substantiate the theoretical findings. While the theoretical results are compelling, they need to be complemented with practical validation to establish the practicality and effectiveness of the proposed method. The lack of experimental results makes it difficult to ascertain the method's performance in real-world scenarios, to gauge its scalability with varying data sizes and distributions, and to compare it with existing methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Despite the significant theoretical contributions, this paper falls short in one crucial aspect, which restricts its overall impact and practical applicability.\n\n> Lack of Empirical Validation: The major limitation of this paper is the absence of empirical experiments to substantiate the theoretical findings. While the theoretical results are compelling, they need to be complemented with practical validation to establish the practicality and effectiveness of the proposed method. The lack of experimental results makes it difficult to ascertain the method's performance in real-world scenarios, to gauge its scalability with varying data sizes and distributions, and to compare it with existing methods.\n\nWe agree experiments are important, and that is why we have experiments in Section A. **Note that we added new experiments that are presented in a separate file in the \"global\" comment to all reviewers called \"Author Rebuttal by Authors\".** Click \"Revisions\" if you can not find the pdf.  We compare our new method with other baselines, MARINA and FRECON, that support compressed communication in the partial participation setting.\n\nWe show that our new method requires significantly fewer communication rounds to find an $\\varepsilon$-stationary point. We believe that these experiments, together with the experiments from Section A in the main paper, give us strong evidence that our method has an excellent practical performance.\n\nMoreover, please see Section A. The DASHA \\[1\\] method is considered to be the current SOTA method in *the full participation setting.* So, it is reasonable to compare our new method with DASHA. However, our method supports partial participation, and from the discussions in Section 6, we know that partial participation should degenerate the convergence rate up to $1 / p.$ When $p = 1$ ($s = 100$, full participation regime) we observe that our method and DASHA have almost the same convergence rates. Then we take $p < 1$ by taking the number of clients $s$ smaller and observe that the degeneration of the convergence rates is up to $1/p$ factor. This is the expected dependence because some clients do not participate. \n\nIn total, we compare our new method with three previous baselines that support compressed communication with different datasets and settings. If our paper gets accepted, we will be allowed an additional content page, where we will be happy to add our numerical experiments.\n\n*In view of the extra experiments, we kindly ask the reviewer to reconsider the score. If the reviewer thinks that there should be some other experiments that would enhance the paper, then let us know.*\n\n\\[1\\]: Tyurin A, et al. DASHA: Distributed nonconvex optimization with communication compression and optimal oracle complexity (ICLR 2023)\n"}, {"review_id": "gYy1L2SMdX", "reviewer": "Reviewer_MQ7w", "summary": "This research focuses on distributed learning problems and introduces a novel approach that incorporates three key elements: variance reduction, compression, and partial participation. It extends the DASHA method to address the partial participation scenario in both finite-sum and stochastic scenarios. In the context of partial participation, the proposed method achieves state-of-the-art communication complexity. Furthermore, in the scenario involving variance reduction and partial participation (without compression), it achieves optimal oracle complexity without relying on strict bounded gradient assumptions. ", "questions": "After examining equations (7)-(8), it is mentioned that step (7) requires further updating if the same idea as in the full gradient step is utilized. The question arises as to why this is necessary. Would the method still function if only the participating nodes updated $h$ while the others retained the previous values? Essentially, is this a limitation of the analysis or would the method diverge under such circumstances?\n\nAnother query pertains to practical applications that satisfy Assumption 6. Is there a specific real-world scenario that meets this criterion? Additionally, it is worth exploring whether achieving state-of-the-art bounds in the stochastic setting is possible without relying on Assumption 6.\n\n", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The extension of DASHA to accommodate the partial participation setting is nontrivial addition. The analysis involving partial participation introduces additional complexity, but this work successfully establishes state-of-the-art bounds (although not that surprising).", "weaknesses": "The presentation can be further improved in several ways to enhance clarity and readability. Firstly, instead of listing the assumptions and results for all three settings (full gradient, finite sum, stochastic) consecutively, it would be beneficial to present each setting individually with a particular focus on the stochastic setting, which is the main focus of this work. This approach would make it easier for the reader to understand and follow the discussion. Additionally, by adopting this approach, it would be possible to cover the results for both the nonconvex and PL condition cases in the main text.\n\nFurthermore, there are a few minor typos that need to be addressed. The set $\\mathbb{R}^d$ is written as $\\mathbb{R}$ in various places, specifically lines 35, 44, 51, and 59. Additionally, in line 164, \"what\" should be replaced with \"which.\" Finally, in line 405, \"dependeces\" should be corrected to \"dependencies.\"\n\nAnother aspect that requires attention is the presentation of the algorithm. Currently, it lacks motivation and clarity. For instance, it is unclear how step (9) is derived to address the issue in steps (7) to (8), where it is mentioned that these updates are adapted to ensure the validity of the proof. Providing a clearer explanation or justification for step (9) would greatly improve the understanding of the algorithm and its purpose.\n\n\nAlthough the specific setup presented in this study has not been previously explored, and its analysis poses challenges, it can be viewed as a minor blend of previous setups, and the results can be considered as a slight extension of the work done in DASHA.\n\nFinally, the scope of the experiments conducted in this research is somewhat limited, as they do not encompass the more intriguing nonconvex neural network scenarios. Furthermore, there is a notable absence of numerical comparisons with other methods, such as FRECON or any other method within the full gradient setup. While I understand that space constraints may be a factor, with careful organization, it may be possible to allocate some room for such comparisons. One possible approach could involve dedicating the main body solely to the stochastic setting, while relegating the finite-sum case to the appendix. This would create additional space for the inclusion of numerical comparisons and provide a more comprehensive evaluation of the proposed approach.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review!\n\n> The presentation can be further improved in several ways to enhance clarity and readability. ...\n\nWe agree. One can see that we separate assumptions in the parts \"1. Gradient Setting.,\" \"2. Finite-Sum Setting,\" and \"3. Stochastic Setting,\" which begin at Lines 33, 38, and 43, accordingly. We tried to separate assumptions for each particular setting.\n\n> Although the specific setup presented in this study has not been previously explored, and its analysis poses challenges, it can be viewed as a minor blend of previous setups, and the results can be considered as a slight extension of the work done in DASHA.\n\n1. The **partial participation setting** with **stochastic gradients** was explored in many previous papers, including FedAvg, FedPAGE, MIME, and CE-LSGD. However, these methods have weaknesses (see Tables 1 and 2).\n2. The **partial participation setting** with **stochastic gradients** and **compression** was explored in FRECON, MARINA and DASHA (gradient setting only).\n\nOur paper also considers **partial participation setting** with **stochastic gradients** and **compression,** so we consider the setup that was explored in the papers from 2., and partially explored the papers from 1.\n\n> Finally, the scope of the experiments conducted in this research is somewhat limited ... Furthermore, there is a notable absence of numerical comparisons with other methods, such as FRECON or any other method within the full gradient setup. While I understand that space constraints may be a factor, with careful organization, it may be possible to allocate some room for such comparisons. ...\n\n**Note that we added new experiments that are presented in a separate file in the \"global\" comment to all reviewers called \"Author Rebuttal by Authors\".** Click \"Revisions\" if you can not find the pdf. \n\nThere we compare our new method with other baselines, MARINA and FRECON. Also, in Section A, we compare with DASHA. If our paper gets accepted, we will be allowed an additional content page, where we will be happy to add our numerical experiments.\n\n> Another aspect that requires attention is the presentation of the algorithm. Currently, it lacks motivation and clarity. For instance, it is unclear how step (9) is derived to address the issue in steps (7) to (8), where it is mentioned that these updates are adapted to ensure the validity of the proof. ...\n\n> After examining equations (7)-(8), it is mentioned that step (7) requires further updating if the same idea as in the full gradient step is utilized. The question arises as to why this is necessary. ...\n\nIn Lines 162-167, we discuss that DASHA-MVR *can not* work in the partial participation scenario because $h_{i}^{t+1}$ requires the points $x^{t+1}$ and $x^{t}$ to make the update (7). We can not evaluate (7) if the $i^{th}$ does not participate. The step (9) resolves this problem because $h_{i}^{t+1} = h_{i}^{t}$  when the $i^{th}$ does not participate. However, we can not use (7) anymore if the $i^{th}$ does not participate because **the proofs do not work** in such a case. So we redesigned (7) and obtained (9) to make new proofs work.\n\nLet us give an intuition of how we come up with (9). Imagine that we do not have partial participation. Then, using the results from DASHA, we know that (7) works:\n\n$h_i^{t+1} = \\nabla f_i(x^{t+1};\\xi^{t+1}_{i}) + (1 - b) (h_i^t - \\nabla f_i(x^{t};\\xi_i^{t+1})).$ ( * )\n\nConsider that we the partial participation. If we understood the question correctly, the reviewer asks if the following strategy will work:\n\n$h_i^{t+1} = \\begin{cases}\\nabla f_i(x^{t+1};\\xi^{t+1}_{i}) + (1 - b) (h_i^t - \\nabla f_i(x^{t};\\xi_i^{t+1})),& p \\\\\\\\ h_i^{t}, & 1 - p\\end{cases}$ ( ** )\n\nLet us take the expectation of $h_i^{t+1}$ w.r.t. the partial participation randomness. We get\n\n$$E_p [h_i^{t+1}] = p (\\nabla f_i(x^{t+1};\\xi^{t+1}_{i}) + (1 - b) (h_i^t - \\nabla f_i(x^{t};\\xi_i^{t+1}))) + (1 - p) h_i^{t}$$\n$$=p \\nabla f_i(x^{t+1};\\xi^{t+1}_i) +p (1 - b) (h_i^t - \\nabla f_i(x^{t};\\xi_i^{t+1}) + (1 - p) h_i^{t}$$\n\nNote that this $E_p [h_i^{t+1}]$ is not equal to r.h.s of ( * ). At the same time, if we take $h_i^{t+1}$ from (9), one can show that $E_p [h_i^{t+1}]$ equals to ( * )!  This indicates that we can not use ( ** ) in the partial participation setting, and the right choice is (9).\n\n> Another query pertains to practical applications that satisfy Assumption 6. Is there a specific real-world scenario that meets this criterion? Additionally, it is worth exploring whether achieving state-of-the-art bounds in the stoch. setting is possible without relying on Assumption 6.\n\nAssumption 6 is crucial to use the variance reduction technique and obtain the $1 / \\varepsilon^{3/2}$ rate. This assumption is the mean-squared smoothness property. It was shown \\[1\\] that this is crucial to get the $1 / \\varepsilon^{3/2}$ rate. Without this assumption, one can only get the $1 / \\varepsilon^{2}$ rate (the rate of the vanilla SGD method). In the context of the ML and FL problems, this assumption is not strong. For instance, for the logistic regression problems, this assumption holds. In other words, this assumption requires the smoothness of $f_i(x, \\xi)$ w.r.t $x,$ which holds for most ML problems.\n\n> Regarding the Main theorems, there is uncertainty surrounding the meaning of $\\omega$. Does it represent any positive scalar, or is there a specific definition or interpretation attributed to it?\n\n$\\omega \\geq 0$ is the variance of the compressor from Definition 1. For instance, consider the Rand$K$ compressor that takes $K$ random values of a vector scaled by $d / K.$ Using the definition, one can show that this compressor is unbiased and $\\omega = \\frac{d}{K} - 1.$ So the more we compress ($K$ smaller), the larger is $\n\\omega.$ If let say $K = d$ (we don't compress), then $\\omega = 0.$ Since we use compressors in our method, $\\omega$ affects our convergence rates.\n\n\\[1\\]: Arjevani et. al Lower Bounds for Non-Convex Stochastic Optimization\n"}]

Author rebuttal:
Dear AC and Reviewers,

We are now presenting new **extra experiments**. See the attached pdf to this rebuttal. If you do not see the pdf here, click "Revisions," after "Author Rebuttal by Authors" and there you will find a link to the pdf

In these experiments, we compare our new method with the previous theoretical state-of-the-art baselines (FRECON and MARINA) that work with the **partial participation setting** and **compression**. We choose only those baselines that support compressed communication from Table 1. We compare the algorithms on two datasets (real-sim and MNIST) and in stochastic and finite-sum settings.

We show that our new method requires significantly fewer communication rounds to find an $\varepsilon$-stationary point. **We believe that these experiments, together with the experiments from Section A in the main paper, give us strong evidence that our method has an excellent practical performance.**

Even more important, we have a theory that provides new state-of-the-art convergence guarantees in the considered settings.

Thank you! Please let us know if you have any additional questions or suggestions.

Meta-review: This paper considers the partial participation setting for federated learning. By bringing together variance reduction and compressed communication to the partial participation setting, the paper extends the DASHA algorithm to stochastic and finite-sum settings, and the new DASHA-PP method achieves the optimal oracle complexity. Overall, I agree with the reviewers that this work provides an important contribution, and so I would recommend acceptance.
Decision: Accept (poster)