Don't Compress Gradients in Random Reshuffling: Compress Gradient Differences
Authors: Abdurakhmon Sadiev
Grigory Malinovsky
Eduard Gorbunov
Igor Sokolov
Ahmed Khaled
Konstantin Pavlovich Burlachenko
Peter Richtárik
Venue: NeurIPS 2024 poster (2024)
Keywords: Random reshuffling
communication compression
distributed optimization
Federated Learning
Primary area: optimization
TL;DR: In this paper we introduce an improved method that utilizes communication compression with variance reduction and sampling without replacement.

Abstract: Gradient compression is a popular technique for improving communication complexity of stochastic first-order methods in distributed training of machine learning models. However, the existing works consider only with-replacement sampling of stochastic gradients. In contrast, it is well-known in practice and recently confirmed in theory that stochastic methods based on without-replacement sampling, e.g., Random Reshuffling (RR) method, perform better than ones that sample the gradients with-replacement. In this work, we close this gap in the literature and provide the first analysis of methods with gradient compression and without-replacement sampling. We first develop a distributed variant of random reshuffling with gradient compression (Q-RR), and show how to reduce the variance coming from gradient quantization through the use of control iterates. Next, to have a better fit to Federated Learning applications, we incorporate local computation and propose a variant of Q-RR called Q-NASTYA. Q-NASTYA uses local gradient steps and different local and global stepsizes. Next, we show how to reduce compression variance in this setting as well. Finally, we prove the convergence results for the proposed methods and outline several settings in which they improve upon existing algorithms.

Don't Compress Gradients in Random Reshuffling: Compress Gradient Differences
Abdurakhmon Sadiev Grigory Malinovsky's Eduard Gorbunoy 1,2,344 Igor Sokolov!, Ahmed Khaled Konstantin Burlachenko', Peter Richtárik'
King Abdullah University of Science and Technology, Saudi Arabia
Moscow Institute of Physics and Technology, Russian Federation Mohamed bin Zayed University of Artificial Intelligence, UAE MMiaa, Université de Montréal, Canada Princeton University, USA
Abstract
Gradient compression is a popular technique for improving communication com- plexity of stochastic first-order methods in distributed training of machine learning models. However, the existing works consider only with-replacement sampling of stochastic gradients. contrast, it well-known practice and recently confirmed in theory that stochastic methods based on without-replacemeet Random Reshuffling (RR) method, perform better than ones that sample the gradi- ents with-replacement. In this work, close this gap in the literature and provide the first analysis of methods with gradient compression and without-replacemeet sampling. We first develop a distributed variant of random reshuffling with gradient compression (Q-RR), and show how to reduce the variance coming from gradient quantization through the of control iterates. Next, to have better fit to Feder- ated Learning applications, we incorporate local computation and propose a variant of Q-RR called Q-NASTYA. Q-NASTYA uses local gradient steps and different local and global stepsizes. Next, we show how to reduce compression variance in this setting well. Finally, we prove the convergence results for the proposed methods and outline several settings in which they improve upon existing algorithms.
sampling, e.g.,
Introduction
Distributed learning plays a crucial role in the training of modern Deep Learning (DL.) models since distributed approaches are able to significantly reduce training time [Goyal et al., 2017, You et al., 2019]. Moreover, distributed methods are mandatory for such applications as Federated learning (FL) [Konečný al., 2016, McMahan et al., 2017], where multiple nodes connected over network collaborate on learning task. Each node possesses its own dataset and cannot share this data with other nodes or central server. As result, algorithms for federated learning often rely local computation and lack access to the entire dataset of training examples. Federated learning finds applications in diverse fields, including language modeling for mobile keyboards [Liu et al., 2021],
Part of the work was done while A. Sadiev research intern KAUST, working in the Optimization and Machine Learning Lab of Richtárik.
Part of the work was done when E. Gorbunov was researcher at MIPT and Mila & UdeM and also a visiting rescarcher KAUST, in the Optimization and Machine Learning Lab of P. Richtárik. *Corrsponddig author, eeduard.gorbunov mbzzuii.c.ac
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

healthcare [Antunes et al., 2022], and wireless communications [Yang et al., 2022]. Its applications extend to various other domains [Kairouz et al., 2019].
Distributed learning tasks are often solved through empirical-risk minimization (ERM), where the m-th device contributes empirical loss function fm (x) representing the average loss of model on its local dataset, and our goal is to then minimize the average loss over all the nodes:
M
min
f(x)
def
Σ m=1
(m)
ZER
M
where the function f represents the average loss. Every fm is average of sample loss functions fün each representing the loss model x on the i-th datapoint on the m-th clients' dataset: that is for each E { (1.2..... M) we have
fm(x) (2)
def
Σ fm (x).
Tum 1=1
For simplicity we shall assume that the datasets on all clients are of equal size: ni = n2 = = Y.M- though this assumption is only for convenience and results easily extend the case when clients have datasets of unequal sizes. Thus our optimization problem is
M Σ M=
min EE
f(x)
(x)
TM
Because d often very large in practice, the dominant paradigm for solving (2) relies on first-order (gradient) information. Federated learning algorithms have access computation, where for a given model x E TR we can compute stochastic gradients V. (x) locally on client m, and (b) communication, where the different clients can exchange their gradients or models with a central server.
key primitives: (a) local
1.1 Communication compression
In practice, communication is more expensive than local computation [Kairouz al., 2019], and as such one of the chief concerns of algorithms for distributed learning is communication efficiency. Algorithms for distributed/feddrrreed learning have thus focused achieving communication effi- ciency, with one common ingredient being the use of gradient compression, where each client sends compressed quantized version of their update instead of the full update vector, potentially saving communication bandwidth by sending fewer bits over the network. There are many operators that can be used for compressing the update vectors: stochastic quantization [Alistarh al., 2017], random sparsification [Wangni et al., 2018, Stich et al., 2018], and others [Tang et al., 2020]. In this work we consider compression operators satisfying the following assumption:
Assumption 1. A compression operator is operator Q Rd Rd such that for some 0, the relations
E [0(z)) = and
E [10(x=)
==1²] s w| hold for x E Rdd
Unbiased compressors can reduce the number bits clients communicate per round, also increases the variance of the stochastic gradients used slowing down overall convergence, e.g. [Khirirat al., 2018, Theorem 5.2] and [Stich, 2020, Theorem 1]. By using control iterates, Mishehenko et al. [2019b] developed DIANA- an algorithm that reduce the variance due gradient compression with unbiased compression operators, and thus ensure fast convergence. DIANA has been extended and analyzed in many settings [Horváth et al., 2019, Stich, 2020, Safaryan et al., 2021] and forms an important tool in our arsenal for using gradient compression.
1.2 Random Reshuffling
Despite the importance of addressing the communication bottleneck, local computations also signifi- cantly affect the training. For simplicity, consider the 1-node scenario. In this case, the update rule of the standard work-horse method in stochastic optimization stochastic gradient descent (SGD)

---

"Complexity" Table I: Summary known new complexity resulis for solving distributed sum optimization problem (2). indicates the number of communication rounds to find a solution with accuracy > 0. Column "RR?' shows whether an algorithm uses Random Reshuufiing. "C?" indicates whether method applics the compression gradicuts or difforence between the gradients and also whether methods for communication. "H"" means independence from the constant of data beterogeneity the complexity. "CVX"" indicates whether each loss on the i datapoint on the m chinnt is conves, but not strongly conves. Notation: x fruas/s p and number of problem (2), where Liaax Lipschitz constant, ja and p are the strong convexity constants of f and f. respectively: variances
fmax/p are comditional
the solution point o X7
(..) v (2. (=?) and o²
IV II:: heterogeneity constant
<
Vmm(x.)l 2 of this paper are highlighted in
Method
Complexity
RR?
C?
H?
CVX?
SGD
x(I)
[Gower et al., 2019]
K
RR
Rm
X(I
X
[Mishchenko et al., 2020]
RR
X
X
/
[Mishchenko et al., 2020]
QSGD
[Gorbunov al., 2020]
(1 + %)
k M pPe
+
Mp
(7)
X
Q-RR
(1 17) R -.
Am
x
X
Corollary
1808
Corollary 6
Q-RR
(n + 3))
K M 16
+2+
x
DIANA
(1 + M K M p
X
/
[Mishchenko et al., 2019a]
MP
DIANA-RR
n(1 + () + (1
Corollary 2
DIANA-RR
n11 + w)
Corollary 8
In the of SGD, RR we in "H!" show that complexity of these methods provided in the non- non-distributed setup. (t) The following inequality is useful for the compurison of complexities: a
n. S a
We denote p? M (o? + <?) to?
[Robbins and Monro, 1951] - can written as follows: -Z,"((((ax),, where is sampled from {I...., . uniformly at random. This procedure thus uses with-replacement sampling in order to select the stochastic gradient used at each step from the dataset. However, in the training of DL models, without- retilouutrellcemmnt sampling is used much more often: that is, at the beginning of each epoch we choose a permutation Ti, TT...., Tr of (1,2,.... n and do the i-th update using the n,-ith gradient: 2; = x V fm (at). Without rithout-replacemme sampling SGD, also known as Random Reshuffling (RR) [Bottou, 2009], typically achieves better asymptotic convergence rates compared to with-replacement SGD and can improve upon it in many settings as shown by recent theoretical progress [Mishchenko al., 2020, Ahn et al., 2020, Rajput al., 2020, Safran and Shamir, 2021]. While with-replacemmet SGD achieves an error proportional to O (+) after steps [Stich, 2019], Random Reshuffling achieves an error of O (14 after T steps, faster than SGD when the number of steps T is large.
1.3 Can Communication Compression and Random Reshuffling be Friends?
As we described earlier, Random Reshuffling and communication compression two important tools for training modern DL models, and both techniques are relatively well understood. However, there no papers that study Random Reshuffling and communication compression in combination. This leads us to the natural question: how these techniques should be combined to improve the convergence speed of existing distributed methods?
1.4 Contributions
In this paper, we aim to develop methods for Distributed and Federated Learning that combine gradient compression and random reshuffling. While each of these techniques can aid in reducing the communication complexity of distributed optimization, their combination is under-explored. Thus our goal to design methods that improve upon existing algorithms convergence rates and in practice. We summarize contributions follows.
3

---

The issue: naive combination has no improvements. As a natural step towards our goal, we propose and study new algorithm, Q-RR (Algorithm 1), that combines random reshuffling with gradient compression at every communication round. However, for Q-RR our theoretical results do not show any improvement upon QSGD when the compression level reasonable (see Table 1). Moreover, we observe similar performance of Q-RR and QSGD in various numerical experiments. Therefore, we conclude that this phenomenon is not an artifact of our analysis but rather an issue of Q-RR: communication compression adds additional noise that dominates the one coming from the stochastic gradients sampling.
reduction of compression variance. To remove the additional variance added by the compression and unleash the potential of Random Reshuffling in distributed learning with compression, we propose DIANA-RR (Algorithm 2), a combination of Q-RR and the DIANA algorithm. We derive the convergence rates of the new method and show that it improves upon the convergence rates of Q-RR, QSGD, and DIANA (see Table 1). We point out that achieve such results we use n shift-vectors per worker in DIANA-RR unlike DIANA that uses only 1 shift-vector.
The remedy:
Extensions to the local steps. Inspired by the NASTYA algorithm of Malinovsky et al. [2022], we propose variant of NASTYA, Q-NASTYA (Algorithm 3). that naïvely mixes quantization, local steps with random reshuffling, and uses different local and server stepsizes. Although it improves in per-round communication
NASTYA but, similar to Q-RR, show that Q-NASTYA suffers from added variance due to gradient quantization. To overcome this issue, we propose another algorithm, DIANA-NASTYA (Algorithm 4), that adds DIANA-style variance reduction to Q-NASTYA and removes the additional variance.
Finally, to illustrate our theoretical findings we conduct experiments on federated logistic regression tasks and on distributed training of neural networks.
2 Algorithms and convergence theory
We will primarily consider the setting of strongly-convex and smooth optimization. We assume that the average function f is strongly convex:
Assumption 2. Function f : Rdd -> is u-strongly convex, i.e,, for all x: y E TR.d.
[(x) ((y (VS(v), 2 " 1 u11?,
(3)
and functions ft: ft......, Rd - TR. are convex all 1, ,,..., n.
Examples of objectives satisfying Assumption 2 include fz-regularized linear and logistic regression. Throughout the paper, we assume that f has the unique minimizer x, e Rd. We also use the assumption that each individual loss füh is smooth, i.e. has Lipschitz-continuuus first-order derivatives:
Assumption 3. Function fi, IRd R is Lim -smooth for every E [ni] and E [M], i.e., for all x, E Rd and for all m E [M] and E [n].
V T (x) (.T(s)) S Limmll - y/l-
We denote the maximal smoothness constant Lmax def max Li.m-
For some methods, we shall additionally impose the assumption that each function is strongly convex: Assumption 4. Each function fi. IRd R is ji-strongly convex.
The Bregman divergence associated with convex function h is defined for all x, y E Rd
Dr (x, y) def h(x) h(y) (Vh(y), - y) Note that the inequality (3) defining strong convexity can be written as Dy (x, v) 2 # v1l?.
2.1 Algorithm Q-RR
The first method we introduce is Q-RR (Algorithm 1). Q-RR is straightforward combination of distributed random reshuffling and gradient quantization. This method can seen as the stochastic without-replacemmnt analogue of the distributed quantized gradient method of Khirirat et al. [2018].

---

Algorithm Q-RR: Distributed Random Reshuffling with Quantization
Input: 20 Starting point, 7 > 0 - stepsize
1: for [= 1...., 1 do
2: Receive from the server and set zl.m Zt
3: Sample random permutation of [n]: 7m.. (I .... Tm mm-))
4: for
. 5: for 1, ..... M in parallel do
do
6: Receive 2 from the server, compute and send Q V fm (ai) back
7: end for
8: Compute and send x; i+1 2; Y Em=1 Q fm (x/)
to the workers
9: end for
10: Te++11 27
end for
Output: 2T
We shall use the notion of shuffling radius defined by Mishchenko et al. [2021] for the analysis of distributed methods with random reshuffling:
Definition 2.1. Define the iterate sequence xit1 radius is the quantity
x
3
M Em=l
V.m (x.). Then the shuffling
M
M ED
del
(1
rad
max
2
mm
m=
We provide clarifications regarding this term in Appendix C.1. To compare our subsequent results with known ones, we introduce bounds on the shuffling radius. The following lemma demonstrates that these bounds are independent of the stepsize even though y is used in Definition 2.1.
Lemma 2.1 ([Mishchenko et al., 2020]). Let Assumptions 3, 4 hold. Then the shuffling radius ord satisfies the following inequlity
pun k,n S oadd S
Limax
4
where 02 def 1 Σ (V and f 1 M
Σ
M
f
We now state the main convergence theorem for Algorithm
Theorem 2.1. Let Assumptions 1, 3, 4 hold and let the stepsize satisfy 0 < 0. [1+2 ) T.max
Then,
for all T 2 0 the iterates produced by Q-RR (Algorithm 1) satisfy
E|[TT 22112 (1 "/"""
nT 11:00
12
2-² 2
2yw
(c? + o.),
(5)
j.M
M Σ (m.))ll1 and o? del
M Σ
where ? def 1 M
Σ
VV
Vm (2+))1
Mn
All proofs are relegated to the appendix. By choosing the stepsize y properly, we can obtain the communication complexity (number of communication rounds) needed to find an e-approximate solution as follows:
Corollary 1. Under the same conditions as Theorem 2.1 and for Algorithm 1, there exists a stepsize Y such that the number of communication rounds n.T to find a solution with accuracy
(i.e. E| x.11² < +) is equal to δ
((1
Lunux
w Maee
where Õ(.) hides and Fi
N7
P
constants and logarithmic factors..
The complexity of Quantized (1C++(1+))0))) ő (1+ #) Lanxx + My3s
(QSGD) is [Gorbunov et al., 2020]: For simplicity, let us neglect the differences between
SGD
5

---

Algorithm 2 DIANA-RR
Input: 2g - starting point, ( (0mmmmmp.. m,1=1111 initial shift-vectors, y > 0 stepsize, a > 0 stepsize
Mnn
for learning the shifts
do 2: Receive 2y from the server and set z.mm 22
1: for =0 0, 1......,77
3: Sample random permutation of [n]: 7m (I (m ................................ 7
4: for = 0, ....., T 1 do
5:
for m 1, ....,. M in parallel do
6:
Receive oy from the server, compute and send Q
V Vmm" (at)
n(m)) back
im 7: Set Pi. him Q
(v (Vmm" (x) h4.m
8:
Set f = nmm + a fm (xi,m)
9: end for
Compute J7. x² - 7 Em=1 Dim and send x; ++1 to the workers
11: end for
Fe++1 = x7
13: end for
Output: ZT
and Jt. First, when which known to be better than the one of SGD as long as e is sufficiently small as we have nao2.a/8 of n/.o?../4 from Lemma 2.1. Next, when M 1 and 0 (single node, compression) our results recovers the rate of RR [Mishchenko et al., 2020].
recover the complexity of FedRR [Mishchenko al., 2021]
However, it is more interesting to compare Q-RR and QSGD when M > and > 1, which is typically the case. In these settings, Q-RR and QSGD have the same complexity since the (1/s) term dominates the O(//e=) one if is sufficiently small. That is, the derived result for Q-RR has advantages over the known one for QSGD unless w is very small, which means that there is almost no compression at all. We also observe this phenomenon in the experiments.
The main reason for that the variance appearing due compression. Indeed, even the current point is the solution of the problem (xr) = x..), the update direction -7 MM ΣM has the compression variance
Q
V fm (at)
17
Ee
M Σ
Q fa (z.))
(z.)) - (2.))
V (z.)1
M
This upper bound is tight and non-zero in general. Moreover, is proportional to >2 that creates the term proportional to in (5) like in the convergence results for QSGD/SGD, while the RR-variance is proportional to 7² in the same bound. Therefore, during the later stages of the convergence Q-RR behaves similarly to QSGD when we decrease the stepsize.
2.2 Algorithm DIANA-RR
To reduce the additional variance caused by compression, we apply DIANA-style shift sequences [Mishchenko et al., 2019b, Horváth et al., 2019]. Thus we obtain DIANA-RR (Algorithm 2), which applies compression the differences between the gradients and learnable shifts. Since the shifts are updated using the past gradients information, one can see DIANA-RR as a method with compression of gradient differences. We notice that unlike DIANA, DIANA-RR has n shift-vectors on each node.
Theorem 2.2. Let Assumptions 3, 4 hold and suppose that the stepsizes satisfy 7 S
min Zng
and a S I=m
I. Define the following Lyapunov function for every t 2
(1+
Lmax
V 1+1
def
||++11 12
4
Σ Tu-7w)7112?
(6)
M
m=1j=0

---

Algorithm 3 Q-NASTYA
Input: 20g starting point, 7 > 0 - local stepsize, > 0 - global stepsize
1: for [ = 0, 1...., T do
2: for m. E [M] in parallel do
3: Receive 2y from the server and set 2i. I't
4: Sample random permutation of [n]: 7m. mm Tm
2211
5: for 0, ,.I,...,71
do
6: Set ++1 zi,m VVm' fm (Fi,m)
7:
end for
8: Compute ft.m 1 (Te - {mmm) and send @x()r.) to the server
9:
end for
Compute 9t 2m=1 Qr (g(gt,m)
11: Compute F+++1 = 79: and send 1++1 to the workers
end for
Output: 2T
where 1,+ 11+1,, (Algorithm 2) satisfy
V V. (1x+) (xx)
Then, for all T 2 0 the iterates produced by DIANA-RR
27
E B S (7- nT Vo
rad
Corollary 2. Under the same conditions Theorem 2.2 and for Algorithm 2, there exists stepsizes
a > 0 such that the number of communication rounds n&T' to find a solution with accuracy e >> is
① n(1 n[1+w) +
Unlike O-RR/OSGD/DIANA, DIANA-RR does not have a ((1/))-term, which makes it superior to Q-RR/OSGD/DIANA for small enough e. However, the complexity of DIANA-RR has an additive Ón((1 + w)) term arising due to learning the shifts [hi.mmmjjMM.ie Nevertheless, this additional term is not the dominating one when is small enough. Next, we elaborate bit more the
comparison between DIANA and DIANA-RR. That is, DIANA has ((1 M) Lumax + (I+w)ee Ma+e
complexity [Gorbunov et al., 2020J. Neglecting the differences between μ and μu, we observe similar relation between DIANA-RR and DIANA as between RR and SGD: instead of the term (((+w)o(/[()p=)) appearing in the complexity DIANA, DIANA-RR has O(dnt/ V=za) term much better depending é. To the best of knowledge, result is the only known establishing the theoretical superiority of RR to regular SGD the context of distributed learning with gradient compression. Moreover, when
(no compression) recover the rate of FedRR and when additionally M = (single worker) we recover the rate of RR.
2.3 Algorithms with Local Steps
In this subsection, we study new variant of NASTYA, Q-NASTYA (Algorithm 3), that unifies quantization, local steps with random reshuffling, and uses different local and server stepsizes. Although it improves per-round communication cost over NASTYA but, similar to Q-RR, we show that Q-NASTYA suffers from added variance due to gradient quantization. To overcome this issue, propose another algorithm, DIANA-NASTYA (Algorithm 4), that adds DIANA-style variance reduction to Q-NASTYA and removes the additional variance.
Theorem 2.3. Let Assumptions 1, 2, 3 hold. Let the stepsizes 7, 1) satisfy 0 < S 16 (1+
0 < 7 bn Gom Then, for all T 2 0 the iterates produced by Q-NASTYA (Algorithm 3) satisfy
E [| 121 5 1p 7
T ||00 -0-1-111222 +8 x.-12
IJW 2 + 9 9~2nImmax (nn+ 1)²2 +o2)
pM
P
Corollary 3. Under the same conditions as Theorem E.1 and for Algorithm 3, there exist stepsizes ?' n/n and 1) O such that the number of communication rounds T to find a solution with accuracy
7

---

Algorithm 4 DIANA-NASTYA
Input: 20 starting point, (ho JM m=1 initial shift-vectors, 7 0 local stepsize, global stepsize, 0 > 0 stepsize for learning the shifts for 0, ................................
do
2: for m .,.... M in parallel do
3: Receive 2, from the server and set 22,m It
4: Sample random permutation of [n]: 7m. (m mm 1--1)
5:
for i 0, ,.... 1-1 = =i, - VV (Ft,,)
do
6:
Set zimm
7:
end for
8:
Compute gt = 1 (x+ mmm) and send Qi (9t.m hem ) to the server
9:
Set h141, h m + ai (gt,m h4,m)
10:
Set 9t.m = hem + Qs (9t.m h).m)
11:
end for
12:
Re+11 MI Ad
2m==1 11t1, = h4 + > Qe (9t. - me
M
9t 2m= Dt. h4 Σ 2m=1
M
M
Qi (gr. hm.m)
14:
3E++1 2i 1/9t
end for
Output: ZT
& 8> is
Linxx (1
c? epp
Lmax ex
V
c +
1f7 -
one can choose vj > 0 such
M
M
that the above complexity bound improves δ Lmax
M
We emphasize several differences with the known theoretical results. First. the FedCOM method of Haddadpour et al. [2021] was analyzed in the homogeneous setting only, i.c., fm( = f(x) for all m E [M), which an unrealistic assumption for FL applications. In contrast, our result holds in the fully heterogeneous case. Next, the analysis of FedPAQ of Reisizadeh et al. [2020] uses a bounded variance assumption, which is also known be restrictive. Nevertheless, let us compare to their result. Reisizadeh et al. [2020] derive the following complexity for their method:
δ Lmax (1+ M) +
M p2g + ) This result is inferior to the one we show for Q-NASTYA:
w
when w is small, the main term in the complexity bound of FedPAQ is Ô (1/s, while for Q-NASTYA
the dominating term is of the order Õ (t/vE) (when w and s are sufficiently small). We also highlight that FedCRR [Malinovsky and Richtárik, 2022] does not converge if w >> M²>He/(2]|=> }13) while
Q-NASTYA does for any w 2 0. Finally, when = O (no compression) we recover NASTYA as special case, and using 1/e, we recover the rate of FedRR [Mishchenko et al., 2021].
Theorem 2.4. Let Assumptions 1, 2, 3 hold. Suppose the stepsizes %, n. satisfy 0 < S 16f.
0 < 13 S min
and a S
1 I+w
Define the following Lyapunov function:
Z4
166
37
Swn?
M |1e41,
def
[141 x. 12
htt 1|2
++
aM2
Then, for all T 2 the iterates produced by DIANA-NASTYA (Algorithm 4) satisfy
97²nL ((n+ 1)ç2 +o.) +Z).
E E < (1 11-1111
M/ Vo +
(8)
μ
Corollary 4. Under the same conditions Theorem E.2 and for Algorithm 4, there exist stepsizes
= 7///n, 1 > 0, a > O such that the number of communication rounds T to find solution with
accuracy is δ w Lmax (1+
Lmax EØ²
22
o²
If O, one can choose rj >
such that the above complexity bound improves δ
(w Lunax (1 + #/

---

QUED
OAR
10
10
ESADA
FRANA
10
10--
10--
10-
100
06.00
0.91
Data poois
Ilata poons
Figure 1: Non-local methods
mushroams, Bard-2
wBe Rand-6
Ala; Band-2
BASTIA
AA TeaCOM
fodCOM
PesCoM
Ahd 0x)
Dkc 0x.
Ahol
10'
10
10'
1000
3000
5000
1000
3000 ta passess
3000
5000
Dataa passes
Data passess
Figure 2: Local methods
Figure 3: The comparison of the proposed methods (Q-NASTYA, DIANA-NASTYA, Q-RR, DIANA-RR), DIANA-RR-1S (a modification of DIANA-RR), and existing baselines (QSGD, DIANA, FedCOM, FedPAQ). All methods use tuned stepsizes and the Rand-k compressor.
contrast to Q-NASTYA, DIANA-NASTYA does not suffer from the Ö(Y:) term in the complexity bound. This shows the superiority of DIANA-NASTYA to Q-NASTYA, Next, FedCRR-VR [Malinovsky
and Richtárik, 2022] has the rate δ (1+1)(1-))* + vR((.ta.)
wwich depends on Ô (1/VE..
(1-(1-))))²
NVF
However, the first term is close to Ö ((w + 1)n2) for large condition number. FedCRR-VR-2 utilizes variance reduction technique from Malinovsky et al. [2021] and it allows to get rid of
(w+1)
permutation variance. This method has δ
complexity, but requires AVE
(1-(1--Ja))
additional assumption on number of functions n and thus not directly comparable with our result. Note that if we have no compression (w 0). DIANA-NASTYA recovers rate of NASTYA.
In Appendix J, we provide versions of Q-NASTYA and DIANA-NASTYA with partial participation of clients, which is another important aspect of FL, and derive the convergence results for them.
Experiments
We evaluated our methods for solving logistic regression problems and training neural networks in three parts: (i) Comparison of the proposed non-local methods with existing baselines; (ii) Comparison of the proposed local methods with existing baselines; (iii) Comparison of the proposed non-local methods in training ResNet- 188 on CIFAR10.
Logistic Regression. To confirm our theoretical results we conducted several numerical experiments on binary classification problem with 1.2 regularized logistic regression of the form
M
def
min RERd
f(x)
fm.
M
Pmm
where Jm, def log (1 + x)) Al|0a1 (ami, Mmm) E Rd E are the training data samples stored on machines m 1, 1,..., M, and > regularization parameter. In all experiments, for each method, used the largest stepsize allowed by its theory

---

multiplied by some individually tuned constant multiplier. For better parallelism, each worker m uses banni-bacches of size 0.1nm. all algorithms, compression operator Q, we use Rand-k [Beznosikov et al., 2020] with fixed compression ratio */a R 0.02, where d is the number of features the dataset.
In our first experiment (see Figure 1), we compare Q-RR, DIANA-RR, and DIANA-RR-1S with classical baselines (QSGD [Alistarh et al., 2017], DIANA [Mishchenko et al., 2019b]) that use with- replacement mini-batch SGD estimator. DIANA-RR-11 1S is a memory-friendly version of DIANA-RR
that stores and uses a single shift f on the worker side rather than n individual shifts h Figure illustrates that Q-RR exhibits similar behavior QSGD, with both methods being slower than DIANA methods across all considered datasets. DIANA-RR-1S and DIANA show comparable convergence rates, indicating that random reshuffling alone, without introducing additional shifts, does make a significant difference. Finally, DIANA-RR achieves the best rate among all considered non-local methods, efficiently reducing the variance and reaching the lowest functional sub-optimality tolerance. These experimental results align perfectly with our theoretical analysis.
The second experiment shows that DIANA-based method significantly outperform in practice when one applies to local methods as well. In particular, whereas Q-NASTYA shows comparative behavior existing methods FedCOM [Haddadpour et al., 2021], FedPAQ [Reisizadeh al., 2020] in all considered datasets, DIANA-NASTYA noticeably outperforms other methods.
Top1 acc (valldation)
60
Top1 (validation)
75
40
50
QSGD y= 0.001
DIANA y= 1.0
QSGD-RR RR y= 0.001
25
DIANA RR y=
2
3
# bits//
1c7
# bits//n
1e11
Figure 4: The comparison of Q-RR, QSGD, DIANA, and DIANA-RR on the task of training ResNet- -18 on CIFAR-10 with n 10 workers. Top-1 accuracy on test is reported. Stepsizes were tuned and workers used Rand-k compressor with k/a x 0.05.
Training Deep Neural Network model: ResNet-18 CIFAR-10. Since random reshuffting is very popular technique in training neural networks, it is natural to test the proposed methods on such consider training ResNet-18 [He et al., 2016) model on the CIFAR10 dataset Krizhevsky and Hinton [2009]. To conduct these experiments use FL_PyTorch simulator [Burlachenko et al., 2021].
problems. Therefore, in the second set of experiments,
The main goal of this experiment is to verify the phenomenon observed in Experiment on the training of deep neural network. That is, we tested Q-RR, QSGD, DIANA, and DIANA-RR in the distributed training of ResNet-18 on CIFAR10, see Figure 4. As the logistic regression experiments, observe that (i) Q-RR and QSGD behave similarly and (ii) DIANA-RR outperforms DIANA. For further experimental results and details, we refer to Appendix B.
Conclusion
In this work, we provide the first study of distributed random reshuffling with communication compression. Our theoretical and empirical findings illustrate the inefficiency naive combination of random reshuffling and communication compression. We also show how this issue can be resolved via the usage of shifts for communication compression. Finally, we develop and analyze methods with random reshuffling, communication compression, and local steps. It is worth mentioning that although our theoretical results are obtained for strongly convex problems, the considered methods perform well in the experiments on non-convex tasks like training neural networks.
10

---

Acknowledgements
The research reported in this publication was supported by funding from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center of Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science.
The work of A. Sadiev and E. Gorbunov (while affiliated with MIPT) supported by grant for research centers in the field of artificial intelligence, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier (00000073303245540000 and the agreement with the Moscow Institute of Physics and Technology dated November 1, 2021 No. 70-2021-00138.
References
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: httpp//rooeen...e//ee wewpiinnnnnnnuuppeee www.riips.ccppppppeeeeeeee hash/cbBache (ttp///cdddd9222277//66666666630
[]] Awstract. html.
Dan Alistarh, Demjan Grubic, Jerry 7. Li, Ryota Tomioka, and Milan Vojnovie. QSGD:
Communication-effiian SGD via gradient quantization and encoding. In Proceedings of the 3 International Conference on Neural Information Processing Systems, NIPS' 17, page 1707-1718, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN
Rodolfo Stoffel Antunes, Cristiano André da Costa, Ame Küderle, Imrana Abdullahi Yari, and Björn Eskofirr Federated learning for healthcare: Systematic review and architecture proposal. ACM Trans. Intell. Syst. Technol., 13(4), 2022. ISSN 2157-6904. doi: (0.1115/3501813 URL
https://doi. org/10 10. 1145/3501813.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-SGie Distributed SGD with quantization, sparsification and local computations. volume 32, 2019.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. abs/2002.12410. 2020. URL https: // //arXiv. org/ 2002 12410.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium learning and data science, Paris, volume 8, pages 2624-2633.
Citeseer, 2009.
Konstantin Burlachenko, Samuel Horváth, and Peter Richtárik. Fl pytorrh: optimization research simulator for federated learning. In Proceedings of the 2nd ACM International Workshop on Distributed Machine Learning, pages 1-7, 2021.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. ACM Transactions Intelligent Systems and Technology (TIST), 2(3):1-27, 2011.
Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li. and Peter Richtárik. Ef21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arXiv:2110.0323 2021.
Margalit R. Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local SGD) and continuous perspective. Gustau Camps- Valls, Francisco J. Ruiz, and Isabel Valera, editors, Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 9050-9090. PMLR, 2022. URL htttps:/proceeddingg mlr ppress/v5111 gltsg//laggoooo2o htmll.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of SGD: variance reduc- tion, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, pages 680-690. PMLR, 2020.

---

Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. Local SGD: Unified theory and new efficient methods. In Arindam Banerjee and Kenji Fukumizu, editors. Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3556-3564. PMLR, 13-15 Apr 2021. UKK.attpss/pproccading
mlr. W.rr.pess//ve hvtss///v/////// 1111///////o/////// gorbunov21a html.
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. Sgd: General analysis and improved rates. In International conference machine learning, pages 5200-5209 PMLR, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in 1 hour. arXiv preprint arXiv:/706.0000 (ane::/066..77. 2017.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In Arindam Banerjee and Kenji Fukumizu, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2350-2358. PMLR. 2021. URL http://proceediin mlr press/v130/ haddadpour21a. html.
K. He et al. Deep residual learning for image recognition. In CVPR, pages 770-778, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun, Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pages 0034,1 2015.
Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv: 15, abs/1904.05115 2019. URL https:://aartt http:///avvvvvor//aaaa
Samuel Horváth, Maziar Sanjabi, Lin Xiao, Peter Richtárik, and Michael Rabhat. FedShuffle: Recipes for better use of local work in federated learning. arXiv preprint 0rXiv:2204.13169 abs/2204.13169, 2022. URL https: //tr/var.vvvv/// org/ abs/2204. 13169.
Kun Huang, Xiao Li, Andre Milzarek, Shi Pu, and Junwen Qiu. Distributed random reshuffling over networks. arXiv preprint abs/2112. 15287.
ahbs/2112.1555 152887 2021. URL https: org/
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456. PMLR, 2015,
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón. Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song. Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning, arXiv preprint arXiv: 1911v:1912.04997 abs/1912.04977. 2019. URL https: / aarviv.ivvv.//iia//aaa/aaaaav org/ http//b///111// 04977.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, ICML. 2020, 13-18 July 2020, Viruual Event, volume 119 of Proceedings of Machine Learning Research, pages 5132-5143. PMLR. 2020. URL htttp://pprccedings mlr, war.preee wwwpppressiiiii 1119//aarraaaaaaaa carimireddy20a. html. html.
12

---

Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. Distributed learning with compressed gradients. arXiv preprint / 06573, abs/1 (os/1806.00653, 2018. URL https:
//arXiv. .rgg absa http//806.0000 06573.
Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical Report University of Toronto, Toronto, Ontario, 2009.
Ming Liu, Stella Ho, Mengqi Wang, Longxiang Gao, Yuan Jin, and He Zhang. Federated learning
meets natural language processing; a survey, arXiv preprint 1rXiv:2107.12003 abs/2107.12603. 2021. URL httph::////t htaps://arriii org/ abs abs/2107 12603.
Grigory Malinovsky and Peter Richtárik. Federated random reshuffling with compression and
variance reduction. arXiv preprint arXiv:2205.03914 abs/2205.03914, 2022. URL https:
//arXivv.rr//e/ org/ http:/bb/2220000333 03914.
Grigory Malinovsky, Alibek Sailanbayev, and Peter Richtárik. Random reshuffling with variance reduction: New analysis and better rates. arXiv preprint arXiv:2104.09344 2021.
Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sampling without replacement provably help in federated optimization. arXiv preprint arXiv:2201. 1066, abs/2201. 1106,, 2022. URL https: /
abs/aaas/// 11066.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas coaamumication-efffciiin learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pages 1273-1282. PMLR, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 1rXXv::901.00260 2019a.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takác, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint 19X1:1901. abs/1901.09269, 2019b. URL https://arXtt org/ ab9/1901 09269.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL https: btetps://proceeee /ttp///eeeeeeneeeeeeeeeeee/eesee neurips.... wwt..pp.cccpappr///// /aa/p//a/02//aah// cBcc6990ccbfff44ceee2266 11deeec446111cddc---- [] Abstract html.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. arXiv preprint arXiv:2102.06704 abs/2102.06704, 2021. URL atttps///rrk:
org/abs/2102. 06704.
Aritra Mitra, Rayana Jaafar, George J. Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Ad- vances in Neural Information Processing Systems, volume 34, pages 14606-14619, Cur- ran Associates, Inc., 2021. URL https:/ /ttp///eecccee.eeeee/ee/e/e prrooceddnggs.nuuiiss neurips htt.a/ap.../ppppee///.... cc/ppaper/22//ff1ee/ []Paper.pdt
Tomoya Murata and Taiji Suzuki. Bias- reduced local SGD for less heterogeneous federated learning. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICMI. 2021, 18-24 July 202 I, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 7872-7881, PMLR, 2021. URL http: //proceedings. mlr,
Jose Javier Gonzalez Ortiz, Jonathan Frankle, Mike Rabbat, Ari Morcos, and Nicolas Ballas. Trade- offs of local SGD at scale: an empirical study, arXiv preprint 1 abs/21 10.08133, 2021. URL https: // aariiii org/ aat/aaas//111// 08133.
13

---

Shashank Rajput, Anant Gupta, and Dimitris S. Papailiopoulos. Closing the convergence gap of SGD without replacement. In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 7964-7973. PMLR, 2020. httpttt::pppooccediieie mlr. prrss/ v119/rajput20a. html.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-effiiii federated learning method with periodic averaging and quanti- zation. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2021-2031. 2...........,.....MMMMM.MMM. PMLR, 2020. mlr, press/v100/reisizaeeeee
URL attp://proceedii
html.
Peter Richtárik, Elnur Gasanov, and Konstantin Burlachenko. Error feedback reloaded: From quadratic to arithmetic mean of smoothness constants. arXiv preprint arXiv:2402.1077 2024.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
Mher Safaryan, Filip Hanzely, and Peter Richtárik. Smoothness matrices beat smoothness constants: Better communication compression techniques for distributed optimization. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages ran Associates, Inc., 2021. URL. / p/tpe//ddioocooosssoomoo neurips cctpppcee////////////ee//e/ (7766266bbbaaa555155000006666660 [3 Paper. pdf.
Cur-
Itay Safran and Ohad Shamir. Random shuffling beats SGD only after many epochs on ill-conditioned problems. arXiv preprint arXiv:2106.0m 06880, 1b880000.00880, 2021. URL httts:///arii: org/ abs/2106. /bs//206.06880. 06880.
Sebastian U. Stich. Unified optimal analysis of the (stochastic) gradient method. arXiv preprint arXiv: 042322, 010119077042233 2019. URL https://arxii wrtp:/oor//////// /90bs/197...o .04232.
Sebastian U. Stich. On communication compression for distributed optimization on heterogeneous data. arXiv preprint arXiv:2009.023: hiss/2009003383. 2020. URL httpss//aa// org/ abs/ 2009. 02388..
Sebastian U. Stich, Jean- Saan-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 4452-4463, 2018. URL htttttt::: h/ppoceedings.neum neurips....ppp...... cc/ /ttp:///////////00000000000000a/
[] Abstract html.
Zhenheng Tang, Shaohuai Shi, Xiaowen Chu, Wei Wang, and Bo Li. Communication--fliciinnn dis- tributed deep learning: a comprehensive survey, arXiv preprint 20t.::22000..00030772.22000200.0
2020. URL https:// org/ abs/2003006377.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang, Gradient sparsification for communication efficient distributed optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: / http://prreeeing...... wwweediinnn.uuuiiiss.seess..eeee wwturips.ccppppeeeee patpp/pp////////eeeeee $3220d19ccb550463922444444444449
Paper .df..
Blake Woodworth, Brian Bullins, Ohad Shamir, and Nathan Srebro. The min-max complexity of distributed stochastic convex optimization with intermittent communication. arXiv preprint arXiv:2102.01588, abs/2102.015883, 2021. URL https: // http://aavvvvvor///a// 2at.bb//20220.2.3.
Blake E. Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local SGD for heteroge- neous distributed learning. In Hugo Larochelle. Mare' Aurelio Ranzato, Raia Hadsell, Maria-Floring Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020a. URL https: /ppppppeeedgggs..//ee wtwpoeeediinns.euuiiiieeeee www.rips.ccpppppp.///e / w17113f6ff201111 11:44133ddc df 48277884888B [] Abstract. html.
14

---

Blake E. Woodworth, Kumar Kshitij Patel, Sebastian U. Stich, Zhen Dai, Brian Bullins, H. Brendan McMahan, Ohad Shamir, and Nathan Srebro. Is local SGD better than minibatch SGD? In Proceedings of the 37th International Conference on Machine Learning, ICMI. 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 10334- 10343. PMLR, 2020b. URL http: / wttp//ewwee........ee/p// mlr, press / v 11t111/9/oothh///0
html.
Zhaohui Yang, Mingzhe Chen, Kii-Kit Wong, H. Vincent Poor, and Shuguang Cui. Federated learning for 6g: Applications, challenges, and opportunities. Engineering, 8:33-41, 2022. ISSN 2095- 8099. doi: https://doi.org/ com/science/ wetaaaattiile/eee htt.a////pppp///2000000101111110
2021.02..1.... 12.000. URL https: http///wwwwiieneeiee.e....
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv preprint arXivv1904.00900 2019.
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch vs local SGD with shuffling: Tight convergence bounds and beyond. arXiv preprini urXiv:21 abs/2110. 1bs/2110.10342, 2021. URL https://arKiv.. wwtp:/...g//////t/e.../..oosseet 22100. 10342.
15

---

Contents
Introduction
1.1
Communication compression
1.2
Random Reshufiling
1.3
Can Communication Compression and Random Reshufiling be Friends?
1.4
Contributions
2
Algorithms and convergence theory
2.1
Algorithm Q-RR
2.2
Algorithm DIANA-RR
2.3
Algorithms with Local Steps
3
Experiments
Conclusion
10
Extra Related Works
18
Experimental details
18
B.1 Logistic Regression
18
B.1.1
Experiment 1: Comparison of the Proposed Non-Local Methods with Exist-
ing Baselines
20
B.1.2
Experiment 2: Comparison of the Proposed Local Methods with Existing
Baselines
B.1.3
Experiment 3: Comparison of DIANA-RR with EF21 and DIANA
22
B.2
Training Deep Neural Network model: ResNet- 18 CIFAR-10
22
B.2.1
Computing Environment
23
B.2.2
Loss Function
23
B.2.3
Dataset and Metric
24
B.2.4
Tuning Process
24
B.2.5
Optimization-Bann Based Fine- Tane-Tuning for Pretrained ResNet -
26
B.2.6
Experiments
26
B.3
Discussion...
27
Missing Proofs for Q-RR
29
C.1 Shuffle Radius Clarification
29
C.2 Proof of Theorem 2.1
29
C,3 Non-Strongly Convex Summands
32
Missing Proofs for DIANA-RR
40
D.I Proof of Theorem 2.2
40
D.2 Non-Strongly Convex Summands
44
16

---

Theoretical Results for Q-NASTYA and DIANA-NASTYA
52
Missing Proof's for Q-NASTYA
53
G Missing Proofs for DIANA-NASTYA
56
Alternative Analysis of Q-NASTYA
I Alternative Analysis of DIANA-NASTYA
64
Partial Participation for Method with Local Steps
67
J.1 Analysis of Q-NASTYA with Partial Participation
67
J.2 Analysis of DIANA-NASTYA with Partial Participation
72
17

---

A Extra Related Works
Federated optimization has been the subject of intense study, with many open questions even in the setting when all clients have identical data [Woodworth et al., 2020b,a, 2021]. The FedAvg algorithm (also known as Local SGD) has also been a subject of intense study, with tight bounds obtained only very recently by Glasgow et al. [2022]. It is now understood that using many local steps adds bias to distributed SGD, and hence several methods have been developed to mitigate it, e.g. [Karimireddy et al., 2020, Murata and Suzuki, 2021]. see the work of Gorbunov et al. [2021] for unifying lens on many variants of Local SGD. Note that despite the bias, even vanilla FedAvg/Local SGD still reduces the overall communication overhead in practice [Ortiz et al., 2021].
The success of RR the single-machine setting has inspired several recent methods that use it as a local update method as part of distributed training: Mishchenko et al. [2021] developed a distributed variant of random reshuffling. FedRR. FedRR uses RR as local client update method in lieu of SGD. They show that FedRR can improve upon the convergence of Local SGD when the number of local steps is fixed as the local dataset size, i.e. when H n. Yun al. [2021] study the same method under the name Local RR under a more restrictive assumption of bounded inter-machine gradient deviation and show that by varying H to be smaller than n better rates can be obtained this setting than the rates of Mishchenko et al. [2021]. Other work has explored more such combinations between AR and distributed training algorithms [Huang et al., 2021, Malinovsky et al., 2022, Horváth et al., 2022].
There are several methods that combine compression or quantization and local steps: both Basu et al. [2019] and Reisizadeh et al. [2020] combined Local SGD with quantization and sparsification, and Haddadpour et al. [2021] later improved their results using gradient tracking method, achieving linear convergence under strong convexity. In parallel, Mitra et al. [2021] also developed variance- reduced method, FedLin, that achieves linear convergence under strong convexity despite using local steps and compression. The paper most related to our work is [Malinovsky and Richtárik, 2022] in which the authors combine iterate compression, random reshuffling, and local steps. We study gradien! compression instead, which is a more common form of compression in both theory and practice [Kairouz et al., 2019]. We compare our results against [Malinovsky and Richtárik, 2022] and show we obtain better rates compared to their work.
B Experimental details
In this section, we provide missing details on the experimental setting from Section 3. The codes are provided in the following anonymous repository: https:/ // aaaonyooouuu.u.a 4open. science/r/ diana_rr- BOA5.
B.1 Logistic Regression
To confirm our theoretical results conducted several numerical experiments on binary classification problem with L.2 regularized logistic regression of the form
M
f(x) def
min RERd
Fmmi
(10)
M
Pym
m==1
1=1
where Jm,s def log (1 Sapp--mm"TTaa + Al|ar112 (amss Umi)) E Rdx (-1,1),; 1, mm are the training data samples stored on machines m = =,,.... M. and X > 0 is regularization parameter. In all experiments. for each method, we used the largest stepsize allowed by its theory multiplied by some individually tuned constant multiplier. For better parallelism, each worker m uses bathhe of size* xs 0.1 In all algorithms, as compression operator Q, we use Rand-k [Beznosikov et al., 2020] with fixed compression ratio k/a = 0.02, where d is the number of features in the dataset.
Hardware and Software All algorithms were written in Python 3.8. We used three different CPU cluster node types:
1. AMD EPYC 7702 64-Core;
18

---

2. Intel(R) RR) Gold 6148 CPU @ 2.40GHz:
3. Intel(R) Xeon(R) Gold 6248 CPU @ 2.50GHz.
Datasets. The datasets were taken from open LibSVM library Chang and Lin [2011]] 1], sorted in ascending order of labels, and equally split among 20 machines |clients workers. w The remaining part of size N 20 [N/20] was assigned to the last worker, where N E Thm the total size of the dataset. A summary of the splitting and the data samples distribution between clients can be found in Tables 2, 5.
Table 2: Summary of the datasets and splitting of the data samples among clients.
Dataset
M
N (dataset size)
d (# of features)
7m
(# of datasamples per client)
mushrooms
20
8120
112
406
w8a
49749
300
2487
a9a
20
32560
123
1628
Table Partition of the mushrooms dataset among clients.
Client's Me
of datasamples of class "-1" of datasamples of class "+1"
1-
406
10
262
144
- 19
406
20
0
410
Table Partition of the w8a dataset among clients.
Client's No
of datasamples of class "-1" # of datasamples of class "+1"
1-
19
2487
20
1017
14 1479
Table 5: Partition of the a9a dataset among clients.
Client's No
of datasamples of class "-1"
# of datasamples of class "+1"
1-
14
1628
15
1328
300
16
19
1628
20
1629
Hyperparameters. Regularization parameter À was chosen individually for each dataset to guar- antee the condition number 4/μ, to be approximately 10s, where L and are smoothness and strong-convexity constants of function f. For the chosen logistic regression problem of the form (10), smoothness and strong convexity constants I,, Joms Tiims Pb, f of functions f, snn and f were computed explicitly
19

---

M Σ
Experimental setup. To compare the performance methods within whole optimization process, track the functional suboptimality metric f(z)) f(x.) that was recomputed after each epoch. For each dataset, the value f(x.) was computed once at the preprocessing stage with 10 16 AT Am + 2XI
L
Amax
M
47mm
m=
Lm
Amax
m Am + 2AI
47m
1
Lim = Amax
4 7umilmat
+ 2A1
J 2A
π = 2A,
where Am is the dataset associated with client m, and Omi is the i-th row of data matrix Am- In general, the fact that L-smooth with
M
1
L
< M
L
Thm
follows from the -s.m-hhmot of fix (see Assumption 3).
In all algorithms, as compression operator Q, we use Rand-k as a canonical example of unbiased compressor with relatively bounded variance, and fix the compression parameter [0.02d], where d is the number of features in the dataset.
In addition, in all algorithms, for all clients estimator to be bm = [0.1nm] where 1.m is the size of the local dataset.
I,..., M,, we the batch size for the SGD
The summary of the values L, Lms Lim Lmaax μ. nn and k for each dataset can be found in Table 6.
Table 6: Summary of the hyperparameters.
Dataset
L
Tamax
X
bm (batchsize)
mushrooms
2.59
5.25
2.58
10 10-4
1.29
10
40
w8a
0.66
28.5
6.6
10-5
3.3
10-5
6
248
a9a
1.57
3.5
1.57
10
7.85
10-5
162
In all experiments, we follow constant stepsize strategy within the whole iteration procedure. For each method, set the largest possible stepsize predicted by its theory multiplied by some individually tuned constant multiplier. For more detailed explanation of the tuning routine, see Sections B. and 1.2.
SGD implementation. We considered two approaches to minibatching: random reshuffling and with-replacement sampling. In the first, all clients 1,..., M independently permute their local datasets and pass through them within the next subsequent mm by. steps. In our implementations of Q-RR, Q-NASTYA and DIANA-NASTYA, all clients permuted their datasets the beginning of every new epoch, whereas for the DIANA-RR method they do only once in the beginning of the iteration procedure. Second approach of minibatching is called with-replacement sampling, and requires every client draw bn, data samples from the local dataset uniformly random. We used this strategy the baseline algorithms (QSGD, DIANA, FedCOM and FedPAQ) we compared our proposed methods to.
tolerance via conjugate gradient method. We terminate our algorithms after performing 5000 epochs.
B.1.1 Experiment Comparison of the Proposed Non-Local Methods with Existing Baselines
In our first experiment (see Figure 1), we compare Q-RR, DIANA-RR, and DIANA-RRA RR-A- with classical basclines (QSGD [Alistarh et al., 2017], DIANA [Mishchenko et al., 2019b]) that use
20

---

O-R DANNNE
CRR
10-1
(6-1
Q
10-
10-1
104
DESSA
1063
1006
10
1820
3000
Ti6e
1003
Figure 5: Non-local methods
ciall aast aastra reazon
Faccon
3210-4
10-3
10-4
10-3
10-3
10--
3050
5000
1000
3000
5000
1000
5000
Data posso5
Dona po6ses
Dana possos
Figure 6: Local methods
Figure The comparison of the proposed methods (Q-NASTYA, DIANA-NASTYA, Q-RR, DIANA-RR), DIANA-RR-1S (a modification of DIANA-RR), and existing baselines (QSGD, DIANA, FedCOM, FedPAQ). All methods use tuned stepsizes and the Rand-k compressor.
a with-replacement mini-batch SGD estimator. DIANA-RR-1S is a memory-friendly version of DIANA-RR that stores and uses single shift hrm on the worker side rather than ni individual shifts
bi.m Figure illustrates that Q-RR exhibits similar behavior QSGD, with both methods be- ing slower than DIANA methods across all considered datasets. DIANA-RR-1S and DIANA show comparable convergence rates, indicating that random reshuffling alone, without introducing ad- ditional shifts, does not make significant difference. Finally, DIANA-RR achieves the best rate among all considered non-local methods, efficiently reducing the variance and reaching the lowest functional sub-optimality tolerance. These experimental results align perfectly with our theoret- ical analysis. For each of the considered nocal methods, we take the stepsize as the largest one predicted by the theory premultiplied by the individually tuned constant factor from the set (0.000975, 0.00195, 0.0039, 0.0078, 0.0156, 0.0312, 0.0625, 0.5 0.25, 0.5, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 40963.
Therefore, for each local method on every dataset, we performed 20 launches to find the stepsize multiplier showing the best convergence behavior (the fastest reaching the lowest possible level of functional suboptimality f(xx) fx.)).
Theoretical stepsizes for methods Q-RR and DIANA-RR are provided by the Theorems 2.1 and 2.2 whereas stepsizes for QSGD and DIANA were taken from the paper Gorbunov al. [2020].
B.1.2 Experiment 2: Comparison of the Proposed Local Methods with Existing Baselines
The second experiment shows that DIANA-based method significantly outperform in practice when one applies to local methods as well. In particular, whereas Q-NASTYA shows comparative behavior as existing methods FedCOM [Haddadpour et al., 2021], FedPAQ [Reisizadch et al., 2020] in all considered datasets, DIANA-NASTYA noticeably outperforms other methods.
In this set of experiments, tuned stepsizes similarly to the non-local methods. However, for algorithms Q-NASTYA, DIANA-NASTYA and FedCOM we needed to independently adjust the client and server stepsizes, leading to more extensive tunning routine.
As before, for each local method on every dataset, tuned client and server stepsizes are defined by the theoretical one and adjusted constant multiplier. Theoretical stepsizes for methods Q-NASTYA and DIANA-NASTYA are given by the Theorems E. and E.2, whereas FedCOM and FedPAQ stepsizes were taken from the papers by Haddadpour et al. [2021] and Reisizadeh et al. [2020] respectively.
21

---

We now list all the considered multipliers of client and server stepsizes for every method (i.e. and respectively):
Q-NASTYA:
Multipliers for 7y {0.000975, 0.00195, 0.0039, 0.0078, 0.0156, 0.0312, 0.0625, 0.125, 0.25, 0.5, 1, 4, 8, 16, 32, 64,128);
Multipliers for {0.0039, 0.0078, 0.0156, 0.0312, 0.0625, 0.125, 0.25, 0.5, 1, 4, 16, 32, 64, 128).
DIANA-NASTYA:
Multipliers for y and y/: (0.000975, 0.00195, 0.0039, 0.0078, 0.0156, 0.0312, 0.0625, 0.125, 0.25, 0.5, 1, 2, 4, 8, 16, 32, 64,128);
FedCOM:
Multipliers for y (0.0312, 0.0625, 0.125, 0.25, 0.5, 2, 4, 16, 32, 64, 128, 256, 512,1024, 2048, 4096, 8192, 16384, 32768 };
Multipliers for r): (0.000975, 0.00195, 0.0039, 0.0078, 0.0156, 0.0312, 0.0625, 0.125, 0.25, 0.5, 1, 2, 4, 8, 16, 32, 64, 128).
FedPAQ:
Multipliers yor {0.00195, 0.0039, 0.0078, 0.0156, 0.0312, 0.0625, 0.125, 0.25, 0.5, 2, 4, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576 }.
For example, to find the best pair (7, v)) for FedCOM method on each dataset, we performed 378 launches. A similar subroutine was executed for all algorithms all datasets independently.
B.1.3 Experiment 3: Comparison of DIANA-RR with EF21 and DIANA
In third experiment (see Figure 8), compared DIANA-RR with DIANA and EF21-SGD [Fatkhullin et al., 2021]. The EF21-SGD is the state-of-the-art algorithm for contractive compressors in distributed non-convex settings. All compared algorithms used with-replacement mini-batch SGD estimator, consistent with the setup in Section 1.1.1. However, in this experiment contrast with Section B.I.I. we employed reliable theoretical step sizes that ensure guaranteed convergence.
The EF21 algorithm family is designed for usage with contraction compressors in non-convex optimization for L-smooth objective functions in for of Equation 1. For scenarios involving biased compressors such as Rand-k, the EF21-SGD can be adapted through scaling [Fatkhullin et al., 2021]. More specifically, unbiased compressor C(x): Rdd + Rd which satisfied Assump- def
tion 1 via applying the transformation C'(x) (w 1) 1_ C(x) yields contraction compressor 1/w+1. In particular, this procedure makes
E [[]C'(=) x < (1 a) |=]|| Yx E Rd with Rand-k compatible with the EF21 algorithm family. In this experiment, we implemented EF21-SGD following the refined analysis from [Richtárik et al., 2024], which offers stricter better convergence guarantee through improved bounds on the theoretical step size compared to [Fatkhullin et al., 2021].
As shown in Figure 8 EF21-SGD does not perform fast enough in scenarios involving using unbiased compressors for strongly-convex optimization problems compared to DIANA-RR and DIANA.
B.2 Training Deep Neural Network model: ResNet-18 on CIFAR-10
Since random reshuffling is very popular technique in training neural networks, it is natural to test the proposed methods on such problems. Therefore, the second set of experiments, we consider training ReaNet-18 18 [He et al., 2016] model the CIFAR10 dataset Krizhevsky and Hinton [2009]. To conduct these experiments we use FL_PyTorch simulator [Burlachenko et al., 2021].
The main goal of this experiment is to verify the phenomenon observed in Experiment 1 on the training of deep neural network. That is, we tested Q-RR, QSGD, DIANA, and DIANA-RR in the distributed training of ResNet-18 on CIFAR10, see Figure 9. As in the logistic regression experiments, we observe that (i) Q-RR and QSGD behave similarly and (ii) DIANA-RF RR outperforms DIANA.
22

---

mushrooms; RandK[k=2]
a9a; Randk
DIANA
1
DIANA
DIANA-RR
DIANA-RR
EF21-SGD
EF21-5GD
0.1
ftx")
0.1
0.01
0.01
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Data passes
Data passes
Figure 8: The comparison of the proposed variance-reduced DIANA-RR and baselines DIANA, EF21-
SGD. All algorithms use theoretical step-sizes, Rand-k compressor, number of workers is 20.
Topl acc (validation)
60
Top1 acc [validation]
75
40
50
QSGD y= QSGD-RR y= 0.001
DIANA y= 1.0
20
25
DIANA-RR y 1.0
3
#bits/n
1e7
#bits/n
Figure 9: The comparison of Q-RR, QSGD, DIANA, and DIANA-RR on the task of training ResNet--18 on CIFAR-10 with n 10 workers. Top-1 accuracy on test set is reported. Stepsizes were tuned and workers used Rand-k compressor with k/a x 0.05.
To illustrate the behavior of the proposed methods in training Deep Neural Networks (DNN), we consider the ResNet-18 18 [He et al., 2016] model. This model is used for image classification, feature extraction for image segmentation, object detection, image embedding, and image captioning. We train all layers of ResNet-18 model meaning that the dimension of the optimization problem equals d = 11, 173, 962. During the training, the ResNet-18 model normalizes layer inputs via exploiting 20 Batch Normalization [Loffe and Szegedy, 2015] layers that applied directly before nonlinearity the computation graph of this model. Batch normalization (BN) layers add 9600 trainable parameters the model. Besides trainable parameters, BN layer has its internal state that is used for computing the running mean and variance of inputs due to its own specific regime of working. We use He initialization [He al., 2015].
B.2.1 Computing Environment
We performed numerical experiments on a server- server-grade machine running Ubuntu 18.04 and Linux Kernel v5.4.0, equipped with 16-cores (2 sockets by 16 cores per socket) 3.3 GHz Intel Xeon, and four NVIDIA A100 GPU with 40GB of GPU memory. The distributed environment is simulated Python 3.9 via using the software suite FL FL_PyTorch [Burlachenko al., 2021] that serves for carrying complex Federate Learning experiments. FL_ PyTorhh allowed us to simulate the distributed environment in the local machine. Besides storing trainable parameters per client, this simulator stores all not trainable parameters including BN statistics per client.
B.2.2 Loss Function
Training Resliet-18 18 can be formalized as problem (1) with the following choice of fí
1 Inml
fx)
x))),
(1I)
1mm
23

---

where C' 9) def _k=1 pr log(()))) with agreement 0-log(0) is standard cross cross-entropy loss, function g 228x28 x R + [0, 1 #classsss a neural network taking image a and vector of parameters a as an input and returning vector in probability simplex, and nm is the size of the dataset on worker m.
#elasses
B.2.3 Dataset and Metric
In our experiments, we used CIFAR10 dataset Krizhevsky and Hinton [2009]. The dataset consists of input variables a; TR22x28x3, and response variables b2 {0, 1 and is used for training 10-way classification. The sizes of training and validation set are 5 10 and 10º respectively. The training set is partitioned heterogeneously across 10 clients. To measure the performance, we evaluate the loss function value f(z), norm of the gradient V and the Top-1 accuracy of the obtained model function of passed epochs and the normalized number of bits sent from clients to the server.
B.2.4 Tuning Process
In this set of experiments, we tested QSGD [Alistarh et al., 2017], Q-RR (Algorithm 1), DI- ANA [Mishchenko et al., 2019a] and DIANA-RR (Algorithm 2) algorithms. For all algorithms, we tuned the strategy E (A, B, C} of decaying stepsize model via selecting the best in terms of the norm of the full gradient on the train set in the final iterate produced after 20000 rounds. The stepsize policies are described below.
A. Stepsizes decaying inverse square root of the number epochs
Vinit
if e 2 +I
Ve
Ve
Vinits
if e 8,
where Ye denotes the stepsize used during epoch e + 1, is fixed shift.
B. Stepsizes decaying as inverse of number epochs
Vinit
if 2 8, 6 +1
Vinit
if
C. Fixed stepsize
== Tinst
We say that the algorithm passed epochs if the total number of computed gradient oracles lies M between e Em=1 Om and (e + 1) Em= Rmm For each algorithm the used stepsize "/ni and shift parameter s were tuned via selecting from the following sets:
Tinit 7set (4.0, 3.7,3..5..3.00 2.5, 2.00, 1.25, 1.0, 0.75, 0.5, 0.25, 0.1, 0.06, 0.03, 0.01, 0.003, 0.001, 0.00066.
8 E Sset
def
(50, 100, 200, 500, 1000).
In tested methods, clients independently apply Rand-k compression with carnality À = [0.05d]. Computation for all gradient oracles is carried out in single precision float (FP64) arithmetic.

---

Topl acc (validation)
80
10a
[|[xx)]| (train)
QSGD y=
60
QSGD-RR 3-0
QSGD 3,0 3.0
100
40
QSGD-RR 3=
20
200
400
600
800
1000
200
400
600
800
1000
Data passes
Data passes
Tool acc [validation)
80
((x) (train)
10a
QSGD 3.0
QSGD-RR y 3.0
60
QSGD 3
40
QSGD-RR 3-
10a
20
200
400
600
800
1000
0.5
1.5
2.0
Data passes
#bits/n
|| (train)
QSGD 3.0
QSGD y= 3.0
10a
QSGD-RR 3.
fix)) (train)
QSGD-RR y=
100
10
M MM
10-1
10"
0.0
0.5
1.5
2,0 lel1
0.0
0.5
1.0
1.5
2.0
#bits/n
#bits/n
Figure 10
Figure 11: Comparison of QSGD and Q-RR in the training of 188 on CIFAR-10, with n = 10 workers. Here (a) and (d) show Top-1 accuracy on test set, (b) and (e) norm of full gradient on the train set, (c) and (f) loss function value on the train set. Stepsizes and decay shift has been tuned from Seet and set based on minimum achievable value of loss function on the train set.
25

---

Top1 acc (validation)
75
|| (train)
DIANA y=
10
DIANA-RR y= 1.0
50
DIANA y=
10
25
DIANA-RR y= 1.0
100
200
300
400
100
200
300
400
500
600
Data passes
Data passes
Topl acc [validationn]
10
75
f(x) (train)
10a
50
DIANA y=
DIANA y
DIANA-RR y 1.0
25
DIANA-RR y 1.0
10-1
200
400
600
3
Data passes
#bits/n
|/0//all (train)
DIANA y 1.0
10a
DIANA y= 1.0
10a
DIANA RR y= 1.0
(ix,) (train)
DIANA-RR y=
10a
10
#bits/n
1el1
#bits/n
Figure 12: Comparison of DIANA and DIANA-RR in the training of ResNet- on CIFAR- 10, with n 10 workers. Here (a) and (d) show Top-1 accuracy on test set, (b) and (c) norm of full gradient on the train set, (c) and (f) loss function value the train set. Stepsizes and decay shift has been tuned from Seet and " based on minimum achievable value of loss function on the train set. For both algorithms stepsize is fixed. For both algorithms stepsize is decaying according to srategy B.
B.2.5 Optimization-Bann Based Fine- Fine-Tuning for Pretrained ResNet-18.
In this setting, we trained ResNet-18 image classification a distributed way across n = 10 clients. In this experiment, have trained only the last linear layer.
Next, we have turned off batch normalization. Turning off batch normalization implies that the computation graph of NN g(a, a) with weights of NN denoted as x is deterministic function and does not include any internal state.
The loss function is a standard cross-entropy loss augmented with extra l2 fg-regularization all=lll// /2 with a 0.0001. Initially used weights of NN are pretrained parameters after training the model on ImageNet.
The dataset distribution across clients has been set in heterogeneous manner via presorting dataset D by label class and after this, was split across 10 clients.
The comparison of stepsizes policies used in QSGD and Q-RR is presented in Figure 14. The behavior of the algorithms with best tuned step sizes presented Figure 13. These results demonstrate that in this setting there is real benefit of using Q-RR in comparison to QSGD.
B.2.6 Experiments
The comparison of QSGD and Q-RR is presented in Figure 11. In particular, Figure 9 shows that in terms of the convergence to stationary points both algorithms exhibit similar behavior. However, Q- AR has better generalization and in fact, converges to the better loss function value. This experiment demonstrates that Q-RR with manually tuned stepsize can better compared to QSGD in terms of the final quality of obtained Deep Learning model. For QSGD the tuned meta parameters are:
26

---

Vinit = 3.0,s 200, strategy = B. For QSGD-RR RR tuned meta parameters are: Voni = 3.0, 1000, strategy B.
The results comparison DIANA and DIANA-RR are presented in Figure 12. For DIANA the tuned meta parameters "Finit 1.0,s O, strategy C' and for DIANA-RR tuned meta parameters
Tinit = 1.0, 0, strategy = C. These results show that DIANA-RR outperforms DIANA in terms of all reported metries.
B.3 Discussion
More about used arithmetics. We used FP64 (IEEE 754) due to its superior numerical stability compared FP32, FP16, and BFloat16. While FP32 and FP16 are commonly used for inference tasks, the choice of precision for training depends on the specific requirements of the task. In certain cases, FP32 may be sufficient, but for others, FP64 is necessary to ensure stability.
The performance gain from switching from FP64 to FP32 can indeed vary based on the GPU model. For instance, the NVIDIA A100 40GB GPU used in our experiments offers approximately a two-fold increase in computational throughput with FP32 compared to FP64. The specific architecture of the GPU influences the choice of precision, and these characteristics can differ across various GPU models and updates.
The computational burden. The primary focus of the paper is to highlight the fundamental complexities and limits of algorithmic behavior. The experiments presented in our paper are intended for illustrative purposes.
The computational demands of our work significant. Performing experiments beyond Malteet-11/CFAAR--111
with 10 clients is near the limit of what is feasible with our com- putational resources. In our simulation involving 10 clients sharing common dataset, rounds/epochs for fine-tuning. Based on an estimate of minutes per epoch, the total computation time would be approximately 66 hours per run (2 minutes/epoch 2000 epochs = 66 hours). Taking into account the grid search with 18 preset learning rates, 5 sets of decay parameters, and 4 algorithms, the total estimated computation time would be around 23760 hours (66 hours x 18 x 4). This represents a substantial amount of computation time. Therefore, conducting comprehensive compar- ison involving four algorithms with an extensive grid of hyperparameters already challenging for models larger than ResNet-11 18 on CIFAR10. To cover 23760 hours of training would indeed require approximately 40 GPUs running continuously for about 25 days. Nonetheless, have conducted numerous experiments to ensure thorough and fair comparison.
ran 2000
Training in overparameterized regime. During training image classification Convolution Neural Networks, we got two results for QSGD-RR as an improvement of QSGD. During training only the last layer (see Fig. 13) there are no benefits QSGD-RR, but QSGD does not behave worse.
When training the whole network (Fig. 11), the results suggest that Q-RR is much better than Q-SGD. Although we do not have formal proof explaining this phenomenon, we conjecture that this can be related the significant overparameterization occurring during the training of a large model on relatively small dataset. That is, the model can almost perfectly fit the training data on all clients, leading to a decrease in the heterogeneity parameter. In this case, there is no need for shifts since the variance coming from compression naturally goes to zero, and the complexities of QSGD and DIANA match (see Table l). this situation, Q-RR performs better than QSGD since the compression does not spoil the convergence of RR. Therefore, DIANA-type shifts are not always necessary to get improvements. Nevertheless, we conjecture that they are necessary when the datasets are larger and more complex.
27

---

Top1 acc (validation)
60
AIPNN (train)
QSGD y= 0.001
QSGD-RR y= 0.001
QSGD y= 0.001
20
QSGD-RR y= 0.001
4 #bits/n
8
#bits/n
167
QSGD 0.001
(train)
2.5
QSGD-RR y 0.001
2200
2
6
# #bits/n
Figure 13: Comparison of QSGD and Q-RR in the training of the last linear layer of ResNet-18 on CIFAR-10, 10, with n 10 workers. Here (a) shows Top-1 accuracy on test set, (b) norm of full gradient the train set, (c) loss function value the train set. Stepsizes and decay shift has been tuned from seet and Yset based on minimum achievable value of loss function on the train set. Both algorithms used fixed stepsize during training.
213
Figure 14: Comparison of QSGD and Q-RR in the training of the last linear layer of ResNet 18 on CIFAR-10, with 10 workers. Here (a) and (b) show Top-1 accuracy test set, (c) and (d) loss function value on the train set, (e) and (f) norm of full gradient on the train set. Stepsizes and decay shift has been tuned from Sset and Yset based minimum achievable value of loss function the train set. During training stepsize was fixed. Batch Normalization was turned off.
28

---

C Missing Proofs for Q-RR
In the main part of the paper, introduce Assumptions 3 and for the analysis of Q-RR and DIRNA-RR. These assumptions can be refined as follows.
Assumption 5. Function f" J.. 2 M
f
Rd + I L-smooth for all sets of permutations
[T] Tm) from [m]] and all E [n]]. i.e.
max V 1T (x) V (v)ll S T.| vll Va, y E Rd. iE[n],T
Assumption Funccion fr M -=
M fm : Rd + is ji-strongly convex for all sets of
permutations π == =T Tm) from [n and all i E [n], i.e.
(x) - 5 (v) (V 1. (y), x v) 2 2 || - yll Vx,y E Rd.
min EE(n),m
Moreover, functiooss fi, f....... fir 12 - IR are convex for all = ,.
We notice that Assumptions and 4 imply Assumptions 5 and 6. In the proofs of the results for Q-RR and DIANA-RR, we use Assumptions 5 in addition to Assumptions 3 and we use Assumption instead of Assumption 4.
C.1 Shuffle Radius Clarification
Our results depend on the so-called shuffling radius proposed by Mishchenko et al. [2021]]
M
rad
def
max
ED Jm
(x
m=1
where --:11 = x
T3
Σn
1
(I.).
One can think of the shuffling radius counterpart the variance term in SGD. Both concepts measure how much the algorithm's performance can fluctuate near the optimal solution, but the cause of these fluctuations is different: in SGD, it is due random sampling, and in RR, it is due to reshuffting. Additionally, Lemma 2.1 provides bounds for the shuffling radius - showing the maximum and minimum possible values based the variance at the optimum, reinforcing the shuffling radius as a useful way to understand how RR behaves. This relationship helps clarify how the reshuffling process influences the algorithm's path and its efficiency reaching an optimal point.
C.2 Proof of Theorem 2.1
For convenience, we restate the theorem below.
Theorem C.1 (Theorem 2.1). Let Assumptions 1, 5, 6 hold and 0 <9S L+2# Lman"
Then, for
all T 2 0 the iterates produced by Q-RR satisfy
E 22112 < (1 71)))))"" 11:0
12,1 +
2r
rdd
27w
(c2 + o.)
p
j.
where 2 M
Σ (x.m(1)))1 and o² Mn
Σ
V
V ||2
m=1
Proof. Using 2.
xi
DM
f (I.)) and line 7 of Algorithm 1, we get
M
|| 1= 2.-1111
r x
?
1
(xt))
fit (I.))
M
m=1
M
|| - 211
24
Σ
V ii (at))
piin (Ixa) x4
M m=1
M
2g²
1
Σ
@
V (++)
v
moرm (xx))
M
m=1
29

---

Taking the expectation w.r.t Q we obtain
1 M
Eg [||]]*] - =, = | - xI1l"
27
Σ
V fm (xi) - v &ith (xc.) x x.
M
m=1
M
1
Σ
v (e(v)
( (a+)) - v sith (Ixx)
M
ml
In view of Assumption and Bglls- cll2 = lElle - EgE12 + ||BeE ell?, we have
Ee [| ++ - 2221 = |1
x=_ |
2
Σ
M
m (xt) - v fih (x.), 2 - x1)
M
m=1
M
Σ
(o
V
/ (at)) v s (x)))
M
m=1
M
2 2
1
filt (z1)
V fm (zz))
M
2
M
||
Σ
fm (xi) - V fi (zx x x²)
M
m=1
V fim (x+) - V fel (zr .).) )(
M
+x²
M
m=1
M
(z1)) 12
M
m=1
V fTh (+)) for m E [M]. Next, we use
where in the last step we apply independence of Q three-point identity* and obtain
Bg [||
12]
S
|1
xxll?
27 M
fiit (ar x4) + D
(4 xxa) - D
ponte (2t
(ix)
M
m
M
4-² 2
V fml" (at) - v fth (Ix,)
M m==1
M
in (z+) |
+
M
1=11
'For any differentiable function f : 1dd + Rd we have: (z(g,)).
30

---

Applying T-smoothness and convexity of Smoothhhossssss and convexity of f. we get
M Σm= finm ji-strong convexity of
Em=
sm"
and
M
M
Be [||a] +
x + 19
1 (1 1- || 1
27
Σ
D
(1
M
Im
m=1
+2 M
1
Σ
D
(x)
x.)
+
?2W
Σ
TM
(at)
11 m=
m=1
M
S (1 - 7/0 || - 2:4 11 27 (1- (1 In)
Σ
mn (1/z xin)
M
1 M
2
M
fm (zx.) ||
+2 M
Σ
D
(xf x,
x
+
Σ
V
mm
M
mml
m=1
2
M Σ
(1+) |
+
V fm (x:)
V
M
m=1
So, we get
Ee [||=]* 21 - =2/+111
<
(1 - 750 || - x111 +
2 M
V fm
th (x.) )
2
M
m=1
M
27
D
x.))
M m=1
fm.
2y
1 1 7
(I+
2w Immax
))
Σ
M
D im (ot, I.x).
M
M
m=1
Taking the full expectation and using a definition of shuffle radius, 0 <
S
[L+2 Lrmax J. and
1
D fm
(xf, v.) 2 0, we obtain
E ||la - 112 S (1- - 7x0 E || - x=[1"]] + +27 20 rnd +
27 M2
M
(2+x >|'
E
m=1
= (1 7T) EE ||=]] - <x. x=111]
+ +2230 rad + 2w
M
n
(x. )1
M2n
m= 1=1
S (1 7ut 1 ||a2 - - 2=11"]
+ +2 3 raa
272w
(c3 + +
+
M
Unrolling the recurrence in i, we derive
R-1
E |||2211 - 121 S - 1177 " E ||0| - 13] + +272
3 Fnd
(1 - -
j=0
2rpw M
(C x n-
(1 --
1=0
Unrolling the recurrence in f, we derive
T-1
E [|r - 1=]
< (1 - 7/0) NT 11:00 - xx=1 + 27
2
(1 - 77) nd
(1 - -
Fnd
t=0
j=0
272w
nT-1
n-1
+ M
(c2 + of))
Σ j=0
(1 - 7T) mr
(1 - -
0=
Since EØTo (1 11-770 -100000 < 1.
7/4 get the result.
31

---

Corollary 5. Let the assumptions of Theorem C.I hold and
1
E/
EuM
min
(12)
T.+ 2M T
T.max
60 rad
6w (C2 + o
Then, Q-RR finds solution with accuracy rounds:
0 after the following number of communication
w Lmax
w C + +
rrd
M
1
M
Eji
v Vep
Proof.
Theorem C.I implies
E E| x.112 ( (1-))²)
11:00
x=11
2 f
ra
27w
(c. + + n.
(13)
To estimate the number of communication rounds required find a solution with accuracy need to upper-bound each term from the right-hand side by s/a. Thus, we get additional conditions on y:
2 rd
27ww j.M (c:
< <
and also the upper bound on the number of communication rounds n'
nf Ō
7p
Substituting (12), we get final result.
C.3 Non-Strongly Convex Summands
In this section, we provide the analysis of Q-RR without using Assumptions 4, 6. Before we move one to the proofs, we would like to emphasize that
M
+++
= x
Σ
Q
V fm
(x:))
M
m=1
Then we have
n-
M Σ
n
M
1e+1 = Ft
(x))
It
Σ
Σ 2
(zi))
Mn n
i=0
i=0
m=1
where T = 7mn For convenience, we denote
M Σ 1=0 m=
Q fol (x:)
Mn
allowing to write the update rule Z++1 = T9h-
Lemma C.1 (Lemma from [Malinovsky et al., 2022)). For any k [n], let Em..... Enz be sampled uniformly without replacement from set of vectors (EI...., End and & be their average. Then, it holds
E E, [1KE, ElP
(14)
k(n 1)
where Ç 1 n E Eo f- E STU 0² = = Σ || - E||
Lemma C.2. Under Assumptions 1, 5, the following inequality holds
I n
Eo 1-27 Ft. - x.)I
Tp ||. - x. - - ((x.))
| - 1r.12
7
32

---

Proof. Using that E [ar]
Σi=
Em=1
Im (x+) and definition of h", we get
Mdn
M
-2rBe 199e, -x.)]
V fm (zz), It- 2x
Mn
i=0 m=1
Σ
V F (xt) V (xx)) 24 Fz
Mn
1=0
Using three-poine point identity, we obtain
M n-1
-27Eq [gt,, It
xx,)]
Σ
D
Iia) (ix) + D
pi (I,, - sm
(xt, 21)
Mn
fm
m=1
i=0
-2TD)(xe,
2f
n-1
pui (I,, +
2T n-1
Σ
D (2
1=0
==0
-2)D)(Et, +
|
Ztz 11?
i=0
where the last inequality we apply T-ssoothhesss and convexity of each function f" Finally, using p-strong convexity of f, we finish the proof of the lemma.
Lemma C.3. Under Assumptions 1, 2, 3, 5, the following inequality holds
Eg [[] s 2Î [I + w
Lmax 1
Σ [|lc] - m=l13] + 4w
Mn (c² + o?)
Mn
72
+8 (I+ w
Lmax)
(f(x)) - f(x.)).
Mn
Proof. Taking the expectation w.r.t Q and using variance decomposition [[|]][]]
[[I E [4] []] + |2 we get
M
Eo [| = Ee
o (iS (2+)
Mn
==0 m=1
n-1 1 M
= Eg
Σ
Σ
o
v
V (xt))
Vi (az))
Mn
== m=1
Finm (x+t)
+
Mn
m=l
33

---

Next, Assumption and conditional independence of Q (v (a+) for m = 1,.,,; M,, =
O,...,n n 1 imply
Ee [I]ss]]]]
M
Ee |
J (oi))
v Jm m (1t) (
M
1=0 m=1
n-1 1 M
1
m (xz²)
Mn 5=
n-1
M
1 n-1 1 M
T (xt))
+
(xt)
M 2
Mn i=0 m=1
2w
M
2w
n-
M
(xt)
sun (wx))
+
V V. (ax)
2
M
1=0
== m=1
n-1
M
+2
fm (ax)
V sلl (1z))
Mn
k= m=1
n-1
M
2 fm (axe)
+2
Mn
k=
m=
Using Lmax- smooohhessss and convexity of fin and L-smoothness and convexity of frr MM 1Tt", we derive
M
4w
n-1 M
2w 11-1 1 M
Ee [1|9]1]]]
1
Lmax
D pin (z), +
V V (xo)
22 2
2
1=0 m=1
0= m=1
+4I
par
+ (2
1=0
S 4 (I+ +
w
Imax]
Σ
D pet
(of 22)
4w
Σ
M
t (Ix) 2
Mn
2212
i=0
==0 m=1
+ 2 ==
4w
Σ
n-1
(xxe)
V
fmf (x+)
2
+ 2 V ((=))) 2
S 2T. + w
T
||gt
4w
n-1
M
V suf (I:)) )
Mn
M2n²
1=0
1=0 m=1
M EED
8w
+
M
Lmax
mi (1), + aL (J(x.) - ((x)))
0=0 mmml
Taking the full expectation, we obtain
E [119: [']
W 2I
i
Linax
Σ
n-1
E |00 - mell +
4w
M
fie (z.
Mn
2
im0
m m=1
8w
+
+
Mn. Limax
E E(s(xx)= - [(xxa)]
= 2ī [
Mn Liax
w
E E || - stel(]]
-xrel
+ 4w
Mn (c: + +o?)
1=0
+
+(4I++
+ Mn
&w
Limax]
Elf(2z) - f(xx)))
34

---

Lemma C.4. Let Assumptions 1, 2, 3, 5 hold and T S
Then, the following
2 2 [L+ sta Lima))
inequality holds
E || =x,1]
I 247² (I+
w
Lmax B[f(xe) fxx))1
Mn
0
+8,² w
(5² o²) + 872 872
Mn
72
where o² - Ei /V/' (x)) # E (1), i [m].
Proof. Since xt
EM Ejzo 2
V pm (x?)), we have
Mi
M
Eo ||
zrl13
-2B
Σ
Σ
o
Mn
m=1 j=u
M
= ,B
Σ
Σ
0
V
sm (112)
v sm (1z)) (ad)
Mn
m= 1=0
M
+
pm (a+)
Mn
1=
<
72
Σ
M i-1
Σ
Eo
V مoرm (2 - V A (
M
m=1 1=0
M 1-1 Σ
++²
Th
(x+)
Mn m=
1=
35

---

Using Assumption 1, T- T-smoothness and convexity of yor and convexity of fins we obtain
Em=1 f and I smoothhsss
M
Pw M
M
M i-1
Ee [1|-] 211² 2x11²]
V TM (x/)
+T²
(xt)
Mn
m
m=1j=0
m=1 j=0
2
M
2
i-1 Σ
fm (x/)
v sm (az)
+ +2²
V
pm
(x+)
M
n
1=0
v=
+2r²
1
V
(1x²) - (x))
(15)
1=0
2r2w
M
th ((ro))
+ M2n²
m=1
4
n-1
M Σ
Σ
L Imax D (2f, + +2²
Σ
V
pm (32)
fm
n
m=1 1=0
==0
+4Ir - 1-1
Σ
gas (1), x41 + 2
ΣΣ
M n-1
V -.
(xz) (x))
|
M2n2
11 j=0
m=1j=0
47
L +
W
Lmax
D pra (1))
Mn
j=0
1
2r +
+2r²
(xz)
(az)
(16)
M2n²
j=0
m=1
1=0
Next, we need to estimate the second term from the previous inequality. Taking the full expectation
and using Lemma C.I and using new notation of² = Σト [ - (((x)) we get
12
E
fm (ax)
E
+
E
(z,) - Vf(e)) (v))\
n
n²
j 0
12
12 12 i
n
<
E
[[v)()))))
+
E [[V (z,) - [1
n i(n 1)
j=1
-o?-
S E (z;)
(
+ π
Taking the full expectation from (16) and using (17), we obtain
E [|a]-
S 47 (ī. + w Lmax
E
D
Mn
1=0
+ 2r E [V{(t))]
+ n
272
+
2w
Σ Σ E
M n-1
V (az) 1"]
2
1=
Using L-smoothness of fr², we get
E [|a] - 21 ||
< 2Ir² (I+
Lmax
Σ
E
- 21
Mn
1=0
2 [[V
272
oo
2
E
fi
(we)) "
n
2
m=1
36

---

Since T 1
1
we have
2/ I[L ita Lmnx)
E [1la] zel1?]
I 2 2I72 (I
Imax) ))
Σ
1
||
- xel?]
Mn
1=
47
4
V (xc)))
4 Vf
oi
E
M
n
m=1
8r
M n-1
(xx) - V ft (xx |
Σ m=1 y=0
Σ
E
2
8
M n-1 Σ
(1.,
+ + -
M
m=1 j=0
47²
(x)))
-
8r2w
M
v (Ix)) 2
Σ
E
(xx)
2
m=1j=
87
M
(z..) (1,)
Σ
E
+ + 1 fl - (x+))))
M
m=1 1=ر
8T
8T
E
- [IV
E (z.)).
n²
n2
Summing from i = to - 1 and using L-smoothness of f and Lmax -mox-Shoothness of fm we obtain
1672w
167
Bla xxll S
Lmax E [f((a)) - [(x))] + LE (s(x)) - f(xx)]
Mn
n
8r2w (c. + oz + 87 02 + TT - f(x=,))
Mn
Theorem C.2. Let Assumptions 1, 2, 3, 5 hold and stepsize satisfy
1
0 O<TS
(18)
16n
[
+
- Lmnax
Mn
for all T 2 the iterates produced by Q-RR satisfy
E |2T - 11]
<
(1-22) 17/311 T
2 11:00
x211+ + 18
18
Z2I ( w
(w (a2 +o?) + +o.0)
1 M
+8 7'
(s2 + oz?)
HM
where
1 n
2
(x.))1.
(19)
+n n1
37

---

Proof. Taking expectation w.r.t. Q and using Lemma C.3, we get
Ee || - x.11²]
= || - x.112 - 2e K 2t - x.)] + Be [11"211]]
I 11 x.112 - ET [(g 2x - xx,]]
a-1
+2r2L [I++ Immax]
Σ
E [||00] =ell3]
Mn
1=0
47 Mn
+872 (i+ Mn
Imax) (f(xr) - f(x))))))))))))))))}}}
(5² + o
Using Lemma C.2, we obtain
Ee [|| - 1=1 S 11, - 1t+11
2 | - -.a11 -(f(x)) - f(x+)) + I n-1
TH
Σ
| - xell?
n2 1=0
n-1
+2r2I [
w
Lmax
E
[||- 2z 11
Mn
8=0
(f(xe) - f(xx)) + 4T²w
+87² [ +
Lmax)
Mn (5. + of)
Mn
(1 TH |0 x2112
-5 [ 87 (I. w
Mn Imaxx (fmma)))((())) (f(xx) - f(x.))
+rT. (1 (1+ + 27 (T++ w
(mxmm))) Σ
[||= - x [1
Mn
1=0
4r"w Mn (c + o.)-
Next, we take the full expectation and apply Lemma C.4:
E [| 22 < (1
TH
E [| 2=
1187 87 (I+ Mn
Lmax)
E B[f(x1) - f(x.)]
+ 3 (1 (1+22 27 [
Mn Lmmmxx )) (I+
w
Mn Lmax) (f(xz)-f(ar f(xx))
w
-
3 (1 + 2r
(I. + w
Immax)
w Mn.
(c + 0²) +
+ 47
Mn (C² + o
Mn
n
Using (18), we derive
E [[] - x2] $ (1
TH
[[|01 - 1.
2
W (G2 + of) +
2
+
2
Mn (c² + +
Mn
to0
Recursively unrolling the inequality, substituting T = ny and using result.
Σ
(1 71
we get the
prr
Corollary 6. Let the assumptions of Theorem C.2 hold and
1
- SuM
7 min
A
22.1)
(20)
16n [L+
Imaxx
V
82
M
24
A5n
38

---

where = + o². Then, finds solution with accuracy > 0 after the following number of communication rounds:
nL Lmax 1
2
o
nL
( + 0 J,20
M
M Ej1
V M
Proof. Theorem C.2 implies
[
1.1 1 (1 )- 1x.11 1-18"
(c2 0.) + + M
+8 yw
(s? -o?)
p.M
To estimate the number of communication rounds required to find a solution with accuracy & 0, we need to upper bound each term from the right-hand side by s/a. Thus, get additional conditions ry:
n2
18
w M
(c:
o + +
8
TW
( + o.) < 3
3
μM
and also the upper bound on the number communication rounds nT
nf δ
Substituting (20) in the previous equation, get the result.
39

---

D Missing Proofs for DIANA-RR
D.1 Proof of Theorem 2.2
Lemma D.I. Let Assumptions 3, 6 hold and a S
1
Then, the iterates of DIANA-RR satisfy
Σ Ee h
V.Li (xM(()))
1 1-
fm (x.)) )11
M
M
m=1
M
2a max
Σ
(1t F...
M
mm
m=1
Proof. Taking expectation w.r.t. Q, we obtain
Ee [1
V. (x:)
Ie [
1m (x))
((mm) V Vim" fx=m(=))(
11
Vim (= (x.))1
+
@(V fm (x/)
((
). ni
V fil (x=))
+a EE
1 im (xt)
h 1i 113
l m
V (x+))1
+2a
( (x²) - nmm h
Vi (xrx)
+a To
| mm (x n |1
Assumption 1, Limax -moothhess and convexity of fix and S 1/(1+w imply
Eg [ - f
| V fm ( (2+)
V fm (x:) - h amm &itl (xx))
+2a
ta (1 w|ll V fm (x h 11?
||
v (x+)
V / (x:)
11 A. + Th (a:) - 27 fi (axx)
+a
|| Tm
v fith (x+))²²
+a V fm (xx) Vinl (11
a am V fmm (x.))]
< (1 a) 1
V f )l?
+a V fm (xx) - vasl (22.)11
(21)
S (1 a:) 1/
V pof (x.))l + 22 20 D fm
(2), x.).
Summing up the above inequality for 1...,, M, we get the result.
Theorem D.1. Let Assumptions 1, 3, 5, 6 hold and 0 < T S min { 22n I. 94 Lemax }. S
1
1tw"
Then, for all T 2 0 the iterates produced by DIANA-RR satisfy
20 nad
E [T] S (1 (1-7 NT Vo +
p
where V. is defined in (6).
40

---

Proof. Using 2/ = x²
7. ΣM m1
Vim (s.) and line 9 of Algorithm 2, we derive
M
M
2
| +1 - 122111
o - x
7
1
V fm
fmm
M
m=l
||g|
2111"
2%
Σ
M
(0rt
9
2. -xa)
M
m=1
M
1
+7²
V Vin (11+))
9t.m
M
m=1
Taking expectation w.r.t. Q and using E|[g- - cll
Blfe
EEI1 + ||
cll² we obtain
2% M M
Ee [| +1 +
x
= || - 2111"
Σ
fi
(x)
v fm (ax ), x x².
m=1
M
o
Im (x;)) - hl.mm)
mim
+
1,m
mim
V Sai (Ir
M m=1
27 M
<
||l|
x ||
V Tin (x+t - v fi (xx), x. - xx6
M m=
1 M
V fmmm (xt) - -hūmm - V fm (ax)) + lt
M m=1
M
ii (xx)) V film (z;))
M
m=1
Independence of Q V ViT im (zr²) n ) m E [M], assumption and three-point identity imply
Be [||=] +1 - x + [2]
S ||ا
xxll?
2
M
(o x/) +D pntn (1), - D
(2t
a.a))
M m=1
fm
Smhh
w
M
Tm m
(z))
Tmm 2
M
m=1
1 M
+72 2
V Tin (Ir.) - v in (at))
M m=
< ||ا|
x:|| ||
27 M
(ot xx)) DD pm (xt xx,) - DD
fon Cat 2xx)
M
fm
2
1
M
V fi (cox) ||² |
Σ
i (x+²)
M
M
m
1
T (Ix)) - V fi (2+))
472
M
27 2w
M
V smi (ar.) |?
2
m==1
41

---

Using -mmoothsss and p-strong convexity of functions fin and L-smoothness and fi-strong convexity of 1" = 1 N Ei= fm" we obtain
Be [| 12] 1
(1
-==1"
2
1-7
T
2w
Lmaxx ))
1
Σ
M
D
(ot, xix)
M
M
Smi
mml
2y +
M
272w
M
Σ
D fm
(a
v.) +
Σ
Vim""" (zx))
M m=
M
m=1
Taking the full expectation and using Defenition 2, derive
E || i+1 - x.. 112 $ (1- (1-1/=)B ||oo - s=11"]
27 1 (1-7 I +
2w
Lmax ))
1
Σ E
M
D
(1)
M
M
sm
m==
2r²w
M
fm (xx,) 11/
2 +2
Σ
E
h hy
V
M
m=1
Recursively unrolling the inequality, we get
[[| - x1
S - -1-" "
||:0 - x. 12
2w
1 - V Siml (2cm |
+ M m= j=0
x
-2y
1 1-7
[[+
2w
Limax ))
ΣΣ
M n-
(1 - (1- [D
M
M
m== j=0
n-
+27 80
(1
j=0
Next, we apply (6) and Lemma D.1:
n-1
E [[ E (1- " || - 2=11
+ 227300
Σ(1 - 7m0 21
1=0
+(111- a) + 2w 2 M n-1
((1--)
Σ
Σ
v f (x. (e.)|? ||]
M
m=1j=0
[[+
2w
-27 1 11-yyaLmax-- -
Lmaxx
M
M
m=1 j=0
42

---

where
dw ad22-
Using S 1t
and y min 2np' (I+ow/atlmmx))
we obtain
E [[+++
-
(1 - -E ||< - 221
+ (1 a) A Σ Σ
" E
1
V. (x.))
aM2 m=1 j=0
n-1
+27 rad Σ (1- - ym0y"
1=0
< max - 7,0", (1- 2 [[V.]
(1-)
n-1
+2y Tmal Σ (1 - np08"
/=0
S (1-
[1 + + o
Σ (1 7/0-"
1=
Recursively rewriting the inequality, we obtain
T-1
n-1
[ < (1-7/1) nI Vp + 2y
(1 - 170 tn
Σ
t=
1=0
nT-11
S 7p)) II v + 27 302 nd
Σ (1 7i)
4:00 Σ (1-
Using that km0
2
we finish proof.
Rey
Corollary 7. Let the assumptions of Theorem D.I hold, Itm and
a
VEN
min
(22)
2mj
T.
T'max
20
M
Then DIANA-RR finds a solution with accuracy > after the following number of communication rounds:
δ n(1 ([[1+w)+
Lmuax
rad Ven
1
M
1
Proof. Theorem D.I implies
222 an
E [ S (1 -7)))
nT
Vo +
To estimate the number of communication rounds required find a solution with accuracy need to upper bound each term from the right-hand side by &. Thus, we get an additional condition on 7:
202
rad
2
and also the upper bound on the number of communication rounds n!
nf = Ö
7/44
Substituting (22) in the previous equation, get the result.
43

---

D.2 Non-Strongly Convex Summands
In this section, we provide the analysis of DIANA-RR without using Assumptions 4, 6. We emphasize that o/+1 z 7 M
Σ M
2m=1 It,m
Then have
R
11+1 = E1
Ft.m - Jt-
mt.
M
Mn
==0
W=
We denote 9. Mr Ei=o
Em=1 -r
Lemma D.2. Let Assumptions 1, 2, 3, 5 hold. Then, the following inequality holds
n-
2rE Kgt- - h4, T4 r.a] 2
TH 1 x.11 - T (f(x+) - f(x+)) +
Iz - 2/1??
12
where h vf((x)== =0.
Proof. Since h- = Vxx))) = 0, the proof of Lemma D.2 is identical to the proof of Lemma C.2.
Lemma D.3. Let Assumptions 1, 2, 3, hold. Then, the following inequality holds
Eg [lle- h4 S
2L
T +
W
Irmax)
xell2 + (T+ W |
Imuxx (f(1z) f(x.))
Mn
Mn
4w
n-
M
Sar (s.)) )11
2 2
1=0 m=1
Proof. Taking expectation w.r.t. Q, we get
n-1
M
Ee [10c hn1l2] = Eq
It.m
hr
Mn
1=0
m==
n-1
M
Eo
h 2 V pi (x
n, )) h4
Mn 1=0
1 n-1
Ee
h
V V (z)) + Q V Vitti (x²) fm²((²))
Mn
1 M
fTh (x))
h
Mn
m=1
Independence of Q V fi (x:))
[M] and Assumption imply
n-1 M
ii |1]
Eg |1|e: - 121
EQ
s (xt) +
fil (at) -,,m
M
==0 m=l
n1
+
(x:))
hr
Mn
t=U
n-1
(at)
(xt) h-
2
2w
n-1 M
in (a:)
pin (oz) l|
R- 1 +
V (xf)
V (xze ||
M
1=0 m=1
i=0
2w
n-1
M
Vittin (2sa (2ss) ||
4 (xxt) 14-
2
+ M2n
+2
i=0
44

---

Using -moothhhsss and convexity of f... and L-smoohhness and convexity of fr, we obtain
4w
M
4L
Ee ll - 11, 11.1
D
2x)
+
D yxt (x)
M2n2
fm
n
1=0
m=
==
M
4w
1 - fei
+ 4L (f(x)) - f(x.))
M 2
4w
Σ
n-1
M
V Vin"" (2x) - v fm (zx)) ||@
2n
i=0 m==
S 2 [
W
Lmax
1
|| rell + ai (f(x)) - f(x)))
Mn
==0
M
8w
1
Lmax
D i v..)
Mn
Mn
1=0 m=1
4w
n-1
M
V (2x)
M
i=0
Lemma D.4. Let S
T4u and Assumptions 1, 2, 3, hold. Then, the iterates produced by DIANA-RR
1
satisfy
R-1 1 M
n-1 M
1
Ee
| - Virr (xx)))
a
1
V VITh (x.))1
Mn
Mn
1=0 m=1
==0 m=1
2o T.max
|| xe11
==
4mx
(f(xe) - -(x)))
Proof. Fist of all, we introduce new notation: H, = M. E15 2m=l Ee |11i v (z. |13
1
Using (21) and summing it up for i 0, ......7 1, we obtain
H4t1
<
1 1- α
h
(x.)1²
Σ
m (x+)
(x.)) vith (x.))² )
Mn
Mn
1=0 m=1
1= m=1
n-1
2a
n-1
M
I mm
V (z=)]12
IV m (x)) V fth (x=))
Mn
Mn
1=0 m=1
m=1
2a
n-1
I
M
Vi (xx) V fi (1:
Mn
1=0
m=1
Next, we apply Lmox-smosthness and convexity of fi, and L-smoothness and convexity of f=i;
H4t1
1-a
Σ
n-1
M
V mm (x+))12
4ax ΣΣ
Lunax
n-1
M
D
(1 x.))
Mn
Mn
Im
0=
m=1
1=0 m=1
M
4ax Tenax
D
f 2Tx)
Mn
T= m=1
1-a
2a L
)11
|| xr
Mn
n
i=0
4a
n-1
M
Lmax
Σ
ΣΣD
(Ite 2ta)
Mn
1=0
45

---

Lemma D.5. Let Assumptions 2, 5 and 2
Then, the following inequality
2 [[+ sman)
holds
Σ 2=
E [1aa] - 2]]
s 24-² [L+
w
Lmax ([f(x)) ffx + 87 22.a
Mn
w2
+8 M
ΣΣ
| Firm
e=0 m==1
where o., = 2i [Vf
Proof. Since xt = It
Em=1
1 j=0
(ni. + 2 (e(vVo (vi (x+) mr.mm )) we have
Mn
M
Ee| |||0| x=l121
Ee
1
Ty Ntm + Q V 5m (x²) m)mm)
mm
Mn
m=1 j=ù
M
N vftl + Q @ fit" (xt) -
m
Mn
m=1 m=1j=0
M
+
Im (xt)
Mn
j=0
Independence of Q V Vivl" (xt) -
hmmmm )
E [M] and Assumption 1 imply
72
M i-1
Fo (o)) + 2 (VI mi (x+) 1. |1")
Eg [||0]] - r=ll3] =
Σ
Eg
2
m=1 1 1=0
M
++²
V fm (att
Mn m=1 3=0
?'w
M
Σ
Σ
V c (x+)
72
(a+)
M
n 0=
m= 1=
27
Σ
M
V
pin (xt
V V (1re) ||
+ 272
1 Σ
V mm (xz)
2
1= 1=
1=0
2r2
Σ
v for
(zzz)
27
V TT (x7)
v
(z,) 2
M
46

---

Using -moothhssss and convexity of fm and L-smoothness and convexity of fr,, we obtain
4r
M Σ
1
E2 [11x]
xxl1
Lmax
D ax) + 27²
(1x)
2
71
mm 1 j=0
2
Vi th (zz) ||
2,2
2
2 m=1 j=0
+
2/
3t
n
j=
2
S 2T [T. +
w Mn
Lmmax
|0g| zell
+ 222
(122)
+
2
Σ
M カー1
fm
(xz) )
||
2
M2n²
m=1 j=0
Taking the full expectation and using (17), we derive
E [[la]] - xz. 2=.1
S 2 (I+ 2i
W
LImaa
-
Σ
E
||c| - 201l²]
+ + 'B [[V] [+
Mn
j=0
+
Σ
M n-1
|
Sin (xc. >| 119]
+
27
[o?]]
M2n²
n2
m=1 o=0
8r2w
M
max
E
D
M2n
smi
Using Smoothhess and convexity of fú, and L-smoothness and convexity of fT², we obtain
E [[la] - =xe1?]]
I 2 (I+
W
Lmax))
2 Σ B
[1a 20l1
Mn
j=0
M n-1
|| Ti
fm ti (I. 11
+ 27
E
V
[o?
22n
n
m=1j=0
+ -
[
2w 2n
Lmax
B[f(x1) - -(xx))
Now we need to estimate
2r'B
[o²). Due E [of]]
S B [[V//(()) we get
E
a
2,2
2T2
E
(
n
2
472 n²
[[I (x.))) +
E
Σ
E
n²
872
472 n²
n
L
E
[D (z,, (z,,
+
n
47

---

Combining two previous inequalities, we get
|| - xz11?1 x 2 [L+
Lmax
1
12 1
Σ
||g
xell
Mn
j=
w w
M
lm (Ir.) ( 11/
E
M
j=U
+47²
Σ +
M2n Lmax
2w
[[f(xz) - f(x,)]
8T²
47 n
+ n
LE [s - -((x)) +
n²
Summing from = to n - 1 and using T S
we obtain
2 2 fit in Ienax)
R
[|0]]]
2=ll S 2 2(1 2112272 2
[I+
Imaax) ))
E
[|10 xeel
72
Mn
72
s
8w
Σ
M n- 1
|
V viml (3zx. (sa.)]])
2 2
m=1 1=0
2w
+87²
M2n1² Limax
B[f(x+) f(x.)]
1672
8T²
LE (f(+)) - -((xz)) ((x=))++
+
Σ
n²
j=1
We consider the following Lyapunov function:
V 1+1 || 1=
Tn 1+1mm
V.S.
(xx))
(23)
Mn
j=0
Theorem D.2. Let Assumptions 1, 2, 3, 5 hold and
10w
7 S min
as 1+ w
np
12n
(L++
1l Mn
Limax
aMn
Then, for all T the iterates produced by DIANA-RR satisfy
7 n2 E [ S (1 my Lo + 20
Proof. Taking expectation w.r.t. Q and using Lemma D.2, we get [1
Eg [||I--1
| Tå: I, + -h 1|2
| - 22,12 2= 2 -27EO 1(.e h² xt - x.)1 + 2 [llar 1- [1]]
| x. 1 TH |1,e x2,12
B2 [llăe h*]1]]]
-T (f(x)) - -((x)))((xx))) + n-
| - =111
48

---

Next, due to Lemma D.3 we have
11 1
Eg [1 - =.11 s (1- TH | - x2111= - T (f(xt) - (sx,)) + -T.
x; 2|
11
n-1
+2r²I (I + w
Lmuxx
Σ
| - xell?
Mn
12 1=0
+8+? 2 (T+
w
[mmax
(f(1z) - fxx)))
Mn
4wt Σ
n-1 M
Σ
m v (x.))1
+ 22
1m0 m=1
22112 + Awt n-1 M
s (1 )
Σ Σ 2
|/ -V V (1.))12
2
1= m=1
-r 1 - 88 (T+ + w
Mn Imax) ) (f(zz) - (xx)))
+rI (1 + 2r (I+ w
lmxx) )) - Σ ||= - xell?
Mn
11 1=0
Using (23), we obtain
4Nt n-1 M
Eg [4411] $ (1- TH) |2| x.112+ + M 2
V (z.)) (z.))l
1=0 m=1
8r (ī. + Mn
Immax) )) (f(xz) - f(x=))
+
(1 + 2r
(I++ w
Irmax) ))
Σ
n-1
|| soe1?
Mn
1=0
CT 2 M
V V.S.i (z ||?
E
M
Mn
To estimate the last term in the above inequality, we apply Lemma D.4:
2 11= 12 + AWT2 n-1 M
Ee [We+1] I (1-
7
|
V (x.))1
M 1=0 m=1
-T 1 8r (I+ w (mmlmax) )) (f(zt)) - ((x=))
Mn
n-1
+TI (1 + +2 (I+
Mn Lmaxx
W_
Σ
| - xz
n 1=0
R-1 M
+CT 1 1 a
k -ft 2112
Mn 1= m=1
2 22
22
tot²
| 2el1? + 4C7 aL (f(xe) - f(x*))
1=
2 n-1 M
s (1- T/-)
2 ||0 - 11,122 + 1 (1-a+ a-
4w
Tin
Vitt (x.))1
cMn
Mn
i=0 m=1
-7 (1 1- -4eeTaTmaxx - 87 (T.+
Irmaa) )) (f(zz) f(xx))
Mn
1 n-1
+r (1 20TeLmax + 2T [++
W
Lmax))
Σ
|| - x
Mn
1=0
49

---

Let He
Mn Di=o Em=1 E |10--m V V (r.))13. Taking the full expectation and using
cr²
Lemma D.5, we get
E [+1l 1 (1
TH
E -1111-12111 + (1 (1-a+ a
cMn ) He
2
-r (1 ACtaLmaa - 87 [
w
Lmax) )) E [f((x)) - f(x,)
Mn
+rI. (1 + 2cra+max +
+ 27 [T++ Mn
w
Immxx) ))
Σ
E -
n
1=0
$ (1 TH E [112, -x,11²]
(1
4w cMn
a
H4
-T (1 ACTaLmaa 8T [
w
Lmax)
E8 [[((zz)- - f(2.]
Mn
+ +247 (1 (1+ 1+2cTabmax 2 [I+ Mn
Immax) ))
[
Mn Imax) B[f(xe) - f(x.)]
22.
2 (1 + 2cTerLmxx + 2T [ +
+
w
n Lmmax) ))
Mn
87 Lw (1 + 2c + 2T
[[+ w Lmaxx) )) Ha.
cMn
Mn
Aw Selecting c aMn' where A is a positive number to be specified later, we have
actaTmax + 2T [T. +
W Trmax)
= + 2T
T. (A 1A+1 1)w
Timax
Mn
Mn
1 4cTa 87 (I+
w
Lmaxx
2 1- - 85
L
(A + 1)w
Lmmx
Mn
Mn
Then, we have
E [
5 (1- TM
E [1100 xx 111 (1-a+
4ex
) Hr.
1- 85 [[+ (A+ 1)w Liaxx ))
-7
E (1(()))
- f(x.)]
Mn
+247 2T
(I+
Lmax)) (1+27 2T
[++ (A (A+
Lemax )) Bl((rr) s(x))]
Mn
Mn
[ī+ (A+1)us
02
1+ L
Lmmax
Mn
n
8a
[,+ + (Aw
+ A
Tī
1 27
Lemax
He.
Mn
Taking 7 B(L+ (1 the Lmmax)
where B is some positive constant, we obtain
Mm
E( <
1
TH
E
[|lar
xx.13]] + (1 (1-a+ a 4a
+
Sa
1
2 B
He
2
A A
8
24
1 B ) E [(f(z)) - s(xx))
B
B2
2
02
+8 L
1
B
n
Choosing A = 10, B = 12, r < i we have
E
V [+11]
<
1 - min
TTP a)
E [ + 10, 3 2
2 2
1
TH
E [V + 10 2.m
<
2
71
50

---

t00
Recursively unrolling the inequality, substituting r = ny and using proof.
(1
S
2 pF
we finish
Corollary 8. Let the assumptions of Theorem D.2 hold, Ht:!
and
Eμ
7 min
(24)
2mp'
12n
[L
1w Ma
Lmax)
40nLo?
Then, DIANA-RR, finds a solution with accuracy = >> after the following number of communication rounds:
δ n(1 w)
+ nI +
Lmax
1 M P
sps
Jam
Proof. Theorem D.2 implics
2 E [ S (1-7)4) Vo + 2020
02
f
To estimate the number of communication rounds required to find a solution with accuracy > 0, we need upper bound each term from the right-hand side by 5. Thus, we get additional condition on y.
n 20
1
2
and also the upper bound on the number of communication rounds n..
nT =
Substituting (24) in the previous equation, we obtain the result.
51

---

E Theoretical Results for Q-NASTYA and DIANA-NASTYA
Theorem E.1. Let Assumptions 2, hold. Let the stepsizes 7, 7) satisfy n 16/max (1oxxr11+)) %t )
0 0<75 S 5nlmax Then, for all T 2 0 the iterates produced by Q-NASTYA (Algorithm 3) satisfy
E [1|ET x. x211 111 (1- 2
7l T ||00 - x-112 1 +
p.M C. + 97p'Lmmax ((n 1)32 +
IH
2 P
Corollary 9. Under the same conditions as Theorem E.1 and for Algorithm 3, there exist stepsizes 7/n and 1) >> O such that the number of communication rounds T to find a solution with accuracy
E Os δ
Lmax (1+
60 M
W.
C2
Limgr Ep
/ +
1f - O, one can choose 1) > 0 such
MME E/
that the above complexity bound improves to ①
(1 Lmax
3 M
+ M
We emphasize several differences with the known theoretical results. First. the FedCOM method of Haddadpour et al. [2021] was analyzed in the homogeneous setting only, i.c., fm( = f(z) for all m e [M.) which an unrealistic assumption for FL applications. In contrast, our result holds in the fully heterogeneous case. Next, the analysis of FedPAQ of Reisizadeh et al. [2020] uses a bounded variance assumption, which is also known to restrictive. Nevertheless, let us compare to their result. Reisizadeh et al. [2020] derive the following complexity for their method:
Liax (1
F + Myre)
o²
This result is inferior to the one we show for Q-NASTYA:
when w is small, the main term in the complexity bound of FedPAQ is Ô (Y/s), while for Q-NASTYA the dominating term is of the order ① (t/vs) (when w and & are sufficiently small). We also highlight that FedCRR [Malinovsky and Richtárik, 2022] does not converge if w >> M M²>we/t2|ee", .. I[²) while
Q-NASTYA does for any w 2 0. Finally, when w = 0 (no compression) we recover NASTYA as special case, and using 7/n, we recover the rate of FedRR [Mishchenko et al., 2021].
Theorem E.2. Let Assumptions 1, 2, 3 hold. Suppose the stepsizes % satisfy 0 < 7 S 16
0 17 S min-
2p 16 11 3tt) and S 1 Define the following Lyapunov function:
V Vet1
def
|x+11 1.
Swn o.2
Σ
M 11441, - h 21
(25)
Then, for all T 2 the iterates produced by DIANA-NASTYA (Algorithm 4) satisfy
nP T E E S (1-
11-TH) (1-2) Vo + 922nL ((n + 1)ç? + +
(26)
Corollary 10. Under the same conditions Theorem E.2 and for Algorithm 4, there exist stepsizes
= 7/n, 17 > 0, a > O such that the number of communication rounds T to find a solution with
accuracy & >
w Lmax (1 11+1)
V
Lmag EN²
VC2
+
If -> O, one can choose rj >
n
such that the above complexity bound improves Ō
(w
Lanax #
(1 + #
In contrast to Q-NASTYA, DIANA-NASTYA does not suffer from the O(1/s term in the complexity bound. This shows the superiority of MANNA-NASTYAII to Q-NASTYA. Next, FedCRR-VR [Malinovsky
and Richtárik, 2022] has the rate δ (w+D)(1-))
(M(C.+a.) which depends on Ö (1/ee. WyE
(1-(1-)))
However, the first term is close to Ö (w + 1)R²) for large condition number. FedCRR-VR-22 utilizes variance reduction technique from Malinovsky al. [2021] and it allows to get rid of
permutation variance. This method has δ (w+1)(1 mvrn
+
Jec. AVVE
complexity, but it requires
(1-(1--pa)) mem
additional assumption on number of functions n and thus not directly comparable with our result.
Note that if we have no compression (w = 0), DIANA-NASTYA recovers rate of NASTYA.
52

---

F Missing Proofs for Q-NASTYA
We start with deriving a technical lemma along with stating several useful results from [Malinovsky et al., 2022]. For convenience, we also introduce the following notation:
n-1
fmm (d
It.m
==
Lemma F.1. Let Assumptions 2, 3 hold. Then, for all 2 O the iterates produced by Q-NASTYA satisfy
Eo [1]=.1²]]
2L max
(1+
w M
M
|
=all = +8Lmmx (1+ w m (f(zz) fxx)))+
4u 2
M S
Mn
m=
1=0
where Eg is expectation w.r.f. 2, and 2
Mi Em= (I.))]
Proof. Using the variance decomposition E [||E|?] = [I|e [<] [1 + || we obtain
M
n
Eg [1]
f (ai...
fm (a/_)))
M
72
n
+
Ji
(at
Mn
1=0
Asm. I
+
M
Mn
1=0
Next, we use (Zz)
==
(xt) and
||a + 6112 < 2 2|
+ 2|16112:
M
M
Eo [|]
2w
(2t_ v V (#z))
+
2w
Σ
fm)()))
M
n
M
m=1
m=1
M
n-1
M
+2
ci (zim)) v vi (zz))
+
fm (xx)
Mn
M
m==1
1=0
m=1
2 (1
+
M
M
f (at V si (at)
M
72
M
2w
|V (m
+2 [fx)1))
M
m=1
Using -smoommots of f and f and also convexity of sm. we obtain
Eg [|]
211+ M
(st - V (o:))
4w
M
(m)( - Vmm(x.)) 12
Mn
M
M
Aw
V [m + +2/[V[(xx) - vs(x,)11
M
2
(1
+
M
M
| - x 1|2
8Lmax (1+
M
M
Dym (Xe, xt) + 4w
M S.
Mn.
M
m= 0
m=m
53

---

Lemma F.2 (see [Malinovsky et al., 2022)). Under Assumptions 1, 2, 3, it holds
1
Σ
Jm
( x2.)
P
xr - F4+ 112 1 (f(xz) f(x+))
Luuax
n-1
|
xell
Mn
2Mn
Lemma F.3 (see [Malinovsky et al., 2022]). Under Assumptions 1, 2, 3 and y S T it holds
M
Σ
2x [ S "'y2"" Tmmax (f(xz) f(x))) + 27 (o, (m++1),))
Mn
m=
1=
Theorem F.1. Let Assumptions 1, 2, 3 hold and stepsizes 7/. 77 satisfy
1 0 < 1 S 16L (1
1
0 0<7S
(27)
+ Wi
5nLmmax
Then, for all T the iterales produced by Q-NASTYA satisfy
E [|aT r- $ (1- T
) 2 |20 x=112+ 9 7 (o + (n 1)+1)
+ mh μ.M S².
2
Proof. Taking expectation w.r.t. Q and using Lemma F.1, we get
Eo [| x.11²] = || - x212 - 2n [gtt, Iz - x.>il
+
[1lg(1]]]
(
M
< 1| xx,'' 11= - 21
1
Σ
mm (zi
2 Iz
M
m=1
1=0
2n²² 1 (1 +
w
M
2z 1|?
Mn
m=1
+817² I (1+
(f(x)) f(xx)) + +17 x2
M
M
M
n-1
< || - -x,1" -21 2m17 Mn
V fm ( ) xt I,
m=1 k=0
217² L
w (1+
M
M
| 2211?
Mn
m=1 1=0
+ +81 I (1+ M (f(x)) f(xx)) + 4n7 c
M
Next, Lemma F22 implies
Ee [|| x. 11]
<
1|., 1 x. 12 12_
nH
Irz - 2111 17 (f(x)))
- f(x.))
2
M n-1
2 Lmax
(1+
w
(f(xr) - ((xx)) + LLmmx
Σ
a - 2ee1
M
Mn
m
1=0
2n7² 22
(1
X7
w
M
xz 1| + 4n M
S
Mn
m=l 1=0
(1
|| - 12.11 17 8nLmax
(1+ M ) (f(2z) f(()))
2
Mmmax (1 + 21 (1 + m
n
1 - xzll" 1| + 4r7 2 w
c.a
Mn
M
54

---

Using Lemma F.3, we get
Eo [| xx113] 1
(1
M/
1 - x.l12
87L (1+ )) (f(xt) - f(x.))
2
+n/mma
1 + 21/2mmxxxx
(1+ w
M ) ) 8 Lmax (f(x)) - f(x.))
Lm/mmax
( 21)2maxxxx
(1 M 27 (o (n+ (1+1))²2
+4n
S.
In view of (27), we have
Eg [| x=]l²]
(1 1111
2 | x=112 4m² ?
M
1) 8nLmmax (1+ ww)
M 87² L2 max (1 2Lmaxl1 (1 w
M m) (f(xz)) f(x.))
+ +27 2272107 11+21d 11
M (o. nL?))
w
(1
nT1 2)
||0
|| - x. 111 4n²
c
m 2 (o + (n 1)o3).
4
M
Recursively unrolling the inequality and using
Σ 1=
(1 2 S
2. we get the result. pn
Corollary 11. Let the assumptions of Theorem E.I hold, n/11, and
EuU 9Lmax
(n++1)5 +o?) 1/2 epM
7 = min
(28)
16 (1 is
24w
Then, Q-NASTYA finds a solution with accuracy e > 0 after the following number of communication rounds:
δ
('m Tnnax
(1+ w +
w ? M En
Truaxx
V/2 + 02/ua)
M
+
+V
EN
If + 0, one can choose 1) min
SuM 2luc?
such that the above complexity bound
16 11 #+)
improves to
TImax
(1+ w
C M Epr
M
Proof.
Theorem E. implies
9 n ((n + 1)(2 + +o?) + |00 - z. +
E || - 2. <
7/
c PMM
μ
To estimate the number of communication rounds required find a solution with accuracy > 0, we need to upper bound each term from the right-hand side by s/3. Thus, we get additional conditions on y::
9 1f Lmax ((n + 1)<? + of) 3'
2
nj
μMM
and also the upper bound on the number of communication rounds T
T
Substituting (31) in the previous equation, we get the first part of the result. When -> 0, the proof follows similar steps.
55

---

G
Missing Proofs for DIANA-NASTYA
Lemma G.l. Under Assumptions 1, 2, 3, the iterates produced by DIANA-NASTYA sarisfy
M
-Ee
1
Σ
(rcm - -2,,20 xzm)
11
|1
-xx
1 (f(2z) f(xx))
M
4
m==1
M
D
(I p,m
Mn
m
==0
Limx
n-1
Ft, 112
Jt 3t
2M m
where ht Vx((x.)
Proof.
Using that Ee mlc. = mt.m and definition h", we get
M
M
1
-Ee
@m
,0 xx.)
It.m - ht, 20 x.)
M
M
m=1
m=1
pt (1),)) V (z.), I,
Mn
1=0
Next, three-point identity and Tmax--Smotsness of each function f imply
1
n-1
-Ee
(g h", 34
x.)
(I))
D
sohn (2.; D pa (1e)
M
Mn
M n-1
< - -Dy(
Σ
M
D
(I 2 zimm)
Mn m=1
Immax
M n-1
+ 2Mn
1 x 1|
m=1 f=
Finally, using j-strong convexity of f, we finish the proof of lemma.
Lemma G.2. Under Assumptions 2, 3, the iterates produced by DIANA-NASTYA sarisfy
Bo |lle: - 11
<
2T22 max
(1+ +
w M
b xxll2 + 8Lmax
w (1+ M (f(xt) f(x.))
Mn
==0
M
4w
h;, 1|2
M
Proof. Since gt = M
EM
Dt.m and El|g - c|12 112=-B0 =E|K - + +E|EE - ccl2, we have
M
27
Eo [1l9c-
1*112]
Eo
(hr.m + 2 (gt.m -)r.m) him)
M
m==
M
27
Eg
(hr. + Q (gt.m (m.m)) )) 9t
+ 11g: - h 112
M
m=
56

---

Next, independence of Q (gr.m - he,,,, m. E M, Assumption 1, and Smoothnss and convex- ity of each function f imply
M
[10:: - h- 13]
ht.ml 1| + 119t 10112
M
M
M
2w
Σ
(x) (3),)) ) v (m)(
+
2w
fm - hem
M m=1
M
m=1
+2 19
+ 2 Vf()))
h²11
M
M
2w
2w
(ri.m) v fm((ee)
+
fm me
M
M2
m=1
M
2
+2
Am (r),m) - fm
+ (zxz)) - 11
M
m=1
1=0
2L max
(1+
w
M
2w
M
M
a xxl12
Σ
| fm -memml
Mn
M
m==
==0
m=1
+2 (xx 1²11
Using and convexity of fm, get
EQ [1l.. h" 11
2L max
(1 + w
M
M n-1
|
xell
2w
Σ
V fm((z)))
hem 11?
Mn
M
+ +4Lmax (f(x:) (xx))
2L2 2
max
(1
M
w
Σ
||at xall2
Aw
Σ
V h;m
Mn
M
1=0
M
4w
+ M
1 1|
Tmmax (f(xz) (xx))
2
(1 + 27
M n-1
8Lmaxi
M
| xxll2 2
Σ m
D (2), x..)
Mn
M
1
M
4w
+ M
|
1o 11 4.max (f(xz) f(xx))
m=1
Lemma G.3. Under Assumptions 1, 2, 3, and a _ the iterates produced by DIANA-NASTYA
satisfy
2 max
Σ
Ee [1]he41,m
12]
Σ
he 12
Σ
|
11
M
M
Mn
+4aLmax
(f(xz) -f(x))).
57

---

Proof. Taking expectation w.r.t. Q and using Assumption 1, we obtain
M
1
Σ
Ee
[1l
hmll7
Σ
Ee
[1 + a hem) h
M
M
(11 - nm 2aE l(Q(gr. hemm) hem bmm))
M
m=1
M
to
2
Ee [I@( he,m)
M
m=1
(llbe.
him 11 + 2a (gr. he k(m))
M
1
+ (1 + w)
l19.m. hemlll
M
Using S Itw get
Ee [1
1²]
b 112 + (gt,m (1lbe.
Nemm hemm It.m 2h
M
M
1
Σ (11h4.m
1m 12 all.gr,,
1t 11 callba, 1. 112)
M
M
M
a
Σ
[ - 11 +
OK
19.m 11
M
M
m=
m
Finally, Lmax- Smoothnsss and convexity of fm. imply
M
1
Σ
Ee [1l
h 12]
ll h 11?
M
M
2a
(119t, Vmm(I)))1 + [I - 1)
M
m=1
1
M
4T
M
| 112 +
Djm (1),
M
M
m=1
M
2a
Σ
Jm (x),
V (xx))
M
m=
1=0
1
|1,,,
11 11? 4Lmma (f(xz) f(x.))
M
m=1
2
maxx
R-1
x2.l" 11
Mn
1=1
Theorem G.I. Let Assumptions 1, 2, 3 hold and stepsizes y, n, satisfy
1
1
0<75
0<n S min
(29)
16
2p' 16Lmax (1+
Ow
1
1+
M
Then, for all T the iterates produced by DIANA- satisfy
E [ < (1
nu T
Un +
972
2 (0? + (n 1)(3)
(30)
58

---

Proof. We have
| 12
| 1/4r Jix + 11
= | - z.11² 2n/ (ût .0 - x.) + 1/119 1-112.
Taking expectation w.r.t. Q and using Lemma G.I, we obtain
Ee || xx-l?]
|| xI11² 2 [(g h² It x.حI + 11 1 ||:: h-" h²112)
M n-1
(1
1111
1|+e - =-11 (x(()))) -(xx)) 21
Mn Σ Σ
D
mm (Ix, T.
2
M n-1
LmaxX
Σ
1 - 2211? + +, [19: h- 11]
Mn
m=1 1=0
Next, Lemma G.2 implies
M n-1
Eq ||
-x-1?]]
(1-
1111
2 ||
- -f(x))) (o_1(-n(((x)))
2n
D mm
(Ix, x2,m)
Mn
T mm
M n-1
|| f,m - 2211? + 21,² 1 max (1 +
M n-1
Σ
| x2e1 11
Mn
Mn
m=1 1=0
m=1
1=
M
+1²²
8Tmmax (1+
w
(f(xz) - -s(x)) +
4w
1 hm 11?
M
M2
m=1
(1
1741
1 - x. 112 - 17 (1 (1- 118//mmaxx (1+
) (F(wr) f(xx))
2
M
M
n-1
+ [mmxx?]
1 + 2mp (1+ ) Mn
| 12112
2
Σ
M n-1
Σ
(Kez (( + 4nfW
Σ
M
11 - 11
Mn
fm
M
m
m=1
Using (6) and Lemma G.3, we get
Ee [[+1]
7/
(I+ w
)) (((o))
<
||0, - x.11 - -11 Sy/Lmax
2
M
[Imaxx?
1 + 2-222mmaxx
(1+ w )) Mn
|
102l2
2n
n- 1
2
M
(Iezy m) +
Mn
Jm
M2
1=0
1-a a
M
l1te, 11 + 2e max
M
t
| x2.12 + 4cxLmax (f(xx) (xx)))
M
Mn
m=1
m=1
1=0
M
<
(1-
?//1
||,, I.11 + 11²
c(l ((1-a)) +
4w
Σ
1 12
2
M
M
m=1
-n
1
8pLmmxx
w (1+
4amcLmax (f(x)) f(x.))
M
n-1
+Ll
(1+ 21/
[+
W M
+ 20xxc )
Σ
x2112
Mn
t=0
59

---

Taking the full expectation, we derive
M
E [ S (1
2 [| - 2.11 + 1p (0(1 a))
4w
[ 1 11
M
m=1
w MM - 4wnjcC) [ f(xx))) 8mpbmax (1+
M
+Lmax!| (1 21Immax (1+ w
+ 2ancImaax
E [ =ell
M
Mn
m=1
1=0
Using Lemma F.3, we get
E [++1]
- (1
-// E
+12 c1 (111a) a)
4w
M
E [1 - - 11
2
M
M
m=1
8nLmax (1+ W) - 4amelmax
E (f - f(x))l
M
88221 2 L
(1+ 2m/mmaxxxx (1+
W
+ +2rmcLmaxx
- f(xx)] (o + (n+ 1)ç2)
B [[f(xx)
M
(1 21Lmmax
(1+ M
2amccmmax
In view of (29), we have
E M++l
I (1- 1111
E || xx+13] + (1
aa
E [lle,. 11
2
2
M
+ $ ulbmar (o. + (n + 1)5?)
Using definition of Lyapunov function and using
(1
2 pn
we get the result.
t=
Corollary 12. Let the assumptions of Theorem E.2 hold, n/n, I+w' and
1
Eum 9
((n + 1)x² + +0:) -
min
(31)
2μ 16Lmax (1+
9w M
Then, DIANA-NASTYA finds solution with accuracy e >> O after the following number of communi- cation rounds:
Trmax (1+
w + +V
Tmmux
Vc2 o2./m EN3
ww+
M
P
Y + one can choose = min
such that the number of communication
Zn 16Lmaa
rounds T to find solution with accuracy 8 > 0
w + Timax (1 )
1
Proof. Theorem E.2 implies
V (1 n/
9 n72nLmax ((n + 1)(2 + +f)
Vo
2
To estimate the number of communication rounds required find a solution with accuracy > we need to upper bound each term from the right-hand side by 2- Thus, we get an additional restriction on ry:
9
n² Lemax 2 np
o) < 5'
and also the upper bound on the number of communication rounds T
T
Substituting (31) in the previous equation, we get the first part the result. When 7 -> 0, the proof follows similar steps.
D
60

---

H Alternative Analysis of Q-NASTYA
In this analysis, we will use additional sequence:
(m+)).).
(32)
==0
Theorem H.1. Let Assumptions I, 3, hold. Moreover, we assume that (1 - 711) v
9/10-100 1/0
1416
Ò < for some numerical constant C' > 1. Also let 3 = m S
30 f and 7 S Timas' Then, for all
T 2 0 the ilerates produced by Q-NASTYA satisfy
max
(1-
B 10"
1
a
V. + - - rad
(33)
2
B
4
+ +33² 1
E | 1. s
10,, x.112 + - 3y
10
11
M M
where Å,
14 EM
|| - v. and d S Lmax (c2 + n0
Proof. The update rule for one epoch can be rewritten as
1
Ft 2t.m
Tt+1
17
M
7.72
Using this, we derive
1
It Ftmm
[441 - xz
Ft 17
Q
M
7m
M
||
21)
It
t.m
M
7/11
m==1
1
+ 2
Q
M
Taking conditional expectation w.r.t. the randomness comming from compression,
M
It x
Eol1æ1+1 - xxll = =1120 - Ix112
2n
It T. M
7T8
m=1
M
1
+
Ee
Q
M
7y
m=l
Next, we use the definition of quantization operator and independence of Q
m E [M]:
7m
Ft
Eol1æ141 xxx12
|| 5
Ix11
2n
M
+ +1²
W
M
Et
Tt
+
1
M
M
M
7m
M
m=1
m=1
61

---

Since 3 2. we obtain
M
Eq - xx112 S 11,e x.112 x..12-266 23
21
Dayy
(1
xtmm
M
m=1
M
M
32 w
2
+ 82
[z - 2 mm
M M
t.m
M
m==
m==
1
= || x.1l² 112 + +2
21 aa
f Iia))
M
m=1
M
M
+ 32 W
Σ
Iz
m.
2 1²
a t.m
xt)
M M
M
m=1
m=
1 M
x21) )
32 w 1 M
21
Ix +
Σ M
(x/,m.
+
2
72
M M
m=l
m=l
M
(1 (xx - xx)) +
(x(,m) xx
M
m=1
M
32 w
Iz 22,m 1.2
M
M
m=
Using the condition that x. M Σ 2m=1
x.mm we have:
M Σ
)
M
B0]101+1-1 - 2=112 -x,1 (1 (1=
(xx - xx) +
(2
x a.m
+ 82 w
Σ
xz
27
1|
M
M
M
m=1
m=
Convexity of squared norm and Jensen's inequality imply
M
M
Eq E0 x11 - 3] - x-
-1 + B
Σ
xT,mm
+ 8 w
Σ
I x?,m
M
M M
m=
m=1
Next, from Young's inequality we get
Bollx1+1 xx.12 (1 3)(221
xx +
M Σ
(I x².mm
+ 3,2 W
22 xx 11
M
m=1
M
M
+ 382
Σ 1
z" 1|
3,2
| xx 11?
M
M
Theorem 4 from [Mishchenko et al., 2021] gives
M
b - x.7_mll 1|2
S - (1-714) [110ce xx.1
+ 27 o
Σ (1 - m1y
M
mL=
F=
= -11 710)"
|1:02 11
20 aad
7pp
62

---

It leads to
Blla4411
xx.11 < (1 3)] r.112 + 3 ( (1-)))))
y/)) [1100 - xx11²) 2, 7p
-
+,32 w
M 11 x=112 + 3 +302
M ( (11 |1oee 2211?] + 27 o 1
7p
+ 3,32 1
Σ 1 x211
M M
1 (1
311 711)" + +333² w
+ 3 w
(1 - -11)")) 1100 - x..1
M
M
M
+ 2 raad Y/
(1+
33
w
+ 333 3
|| xx1
M
M M
m=1
Using (1 (1-7u)" <
1/10
14/0 we have
9/10 1/C
(1 - xM) -
1+//c
(1+ ))
1
(1 (1))
-
10 C
3 3(1 710"
+ + 8
2 7p)" 00
10
8 [1)"
1 - 3 + B(1 -11))"
c
71)"" $
c
10"
Next, applying 3 < I+30 we derive
1 3 + - -1))))))))) 3,3 w
+ 3,3
- (1-74 1
M
M
10"
Finally, we have
(1
B
1((12
1 1
E 11111111
11 -x
|0: x. + 202
c
10
rad
M
+ +,32
w
1::0 - x2.12
M M
m=1
B
|| xz 112 + 4 =3-2 o?ad
<
10
1
M
W 1
+ 3,3
||x0 xr, 22,12.
M M
m=
63

---

I Alternative Analysis of DIANA-NASTYA
Theorem I.1. Let Assumptions J, 3, hold. Moreover, we assume that (1 (1-)))) v 9/101//1 B <1
1+1/0
for some numerical constant B > Also let B3 "n + and y S Lmaax and also a S w+1' Then, for all T 2 0 the iterates produced by DIANA-NASTYA satisfy
E max (1-
3 10'
T Vo
2
(34)
pmmn
10: 2
B
rad-
Proof. We start with expanding the square:
|
2+11
|
1
11 M
(he,m + Qgr.. -hemm)
m=
1
F. 11?
2n
(he, + Q he 2t Fn
M
(he,m
Q(ee.m hemm))
M
Taking the expectation w.r.t. Q, we get
M
EQ |0141 - x=.12= =1 =1100 - xx 11
2n
Σ
It It
Ex
M
m=1
1 M
2
+ 1/ EE
(hr,m + Qgt.. llmm))
M
M
= =112:
Iz 1==
21
It,m, It.
26.
M
m=1
M
M
+ E,
M Σ
(he,m + Q(gr.m he. m)
+ 1²²
Σ 9t.
M
m=1
m=
M
< ||
xz 112
2n
mt.
M m=1
M
Ad
+ 11
M2
w
l1
me 1l 11
M
9t.m
m=1
m=1
M
< [2 Ix 112
2n
It.ms Dt
E+
M
m=1
M
M
+ 1 2w0
M
I]ge. hm 112
17
M
2w
f
ham 2 17
M
1
Σ
9t.m
m=
64

---

Next, using definition of It.m, we obtain
M
Dt
It..
34
27,m
B141111 xx112 s 120e
x.112
2n
3/2
+ tt
M
7/n
M
7
m=1
m=1
M
M
2w 2
2w
17
g1
hrmm 112
+ 17
M
20
I+ 112 +2a
1 M
(1), xz) 24
Io
M Σ
1
(<
Izt
M
M
2w
2i M2
17 M
l1
1e 112
+ 11
|1 mm.
m=1
m=
1 M
84
Je
a
(fim 22t)
M
M
+ 17
2w
1e 112 + 11
2w M
Σ
Na.m 1
M
mm
M
(1 () - Ixx) +.3
x x².mm
M
m=
M
1
< (1 - B)][2e x2,11 +
| 1
x ml 11?
M
m=1
2w
2w
11 h 112 n²
114m hamml1?
M2
M
m=1
Let consider recursion for control variable:
[l1411, hr ml 2| | aQ( h),m) h ml
||he, hl,mll? + a (Q(ge,m hemm), hemm ha,m) a. a3(1Q((9t,m he,m))
Taking the expectation w.r.t. 2, we have
Bollht+1.m - he 2 < |l - hmmm 1l + 2a (gt.m hemm hem hmmm) + a² (w + 1) 199,m h2.ml1
Using a S w+I have
E Elihet1,m hamm! 1
hhem ha 2|2
+ 2a (gr.
mm Remm - ha,m) + 1192,m ham
11,.ml]
2a (gr.m
he,m: hemm hmmm) (ge,m he,m Ft.m he.m)
ha,m 1
+ a (gt.m
hemm, It.m
humm m + 2he.m 2/ m.)
hamm 1|
+ a (gt.m hr, St.en + ter,o 21tm,m)
hr,m 2
+ (gt.m
hemm
hmmm + ha Ir.m hemm 2h
11t.
h l|2
+ a (gt.m hamm (he,m ha, (gt. Da,m) + (Ne - hamm))
| -2e,m 2 + all.r,m - hr.m allhr.m - hamm 112
(1 a))l hm 2| allgg.m - ha,mll
65

---

Using this bound we get that
M
M
M
Σ m=
Boll/ee - Itam 12 5 - a)
homm 11 + at
11
mm
M
M
M
m
Let us consider Lyapunov function:
4wm2 1 aM
M heem hmmml 11?
V [ I=ll 11?
M
Using previous bounds and Theorem from [Mishchenko et al., 2021] we have
0 raa EV S (1 B)] - x2 + 3 (11 - [1->,))_|ll,, x. 73 Yp
1
M
+ 11 2w
2w 1
Ellgt.m
Namml 112 + 1
E Elihe, he 112
M M
M M
M
M 4war2
4w112
+ (1 a)
E ham
hamm 2| + a
Bllge.m ml,
aM
M
aM
M
m
m=1
< (1 (x) !wr1²
1
M
Gw
M
B hr.m
1mmm 11 + 2
E Ellgr.m
hmmm!
2 a.M
M
mmm 1 M
M
m
+ (1 - B)E x.112 3 3 (11 (1-7w))BBlzz x. 11
1 0
+ 73 7/1
rad
Let us consider
M
M
9t.m ham 12 =1
Tt. F.,m
3. Tamm
M
M
7yn.
T==
m=1
M
M
< 2n²
E
Ct T.
+ 2 2
E
t,
20 m
M
7/
M
7/
m==1
m=
2.8 1
E
12 x. 11
+ 2,8
1
E
2: 22
2
M
M
M
S 23
| - 2.11 + 2.3
E
M
Putting all the terms together and using
(1-711" < 1+1/a
9/10-1/1
B <
12B 12 1,
1
we have
EV,+1 S (1 1 (1-B+ B+
12
W
B²
12
8² (1-)) + 3(1 yu)") E Bl|ar xx112 12 + Bg3
22 raa
M
M
7p
+ 2,32
6i
3
1
02
rad (1 (1-
a)
Aun? 1
Σ E E h4 nm,m!l 1|
M
7t
2
a.M M
m=1
1
B
Bllare - 12,12 + - 3-
2 g
+ (1
a
4wnj² M
El ht 1 1|2
10
2
aM M
< max
(1
10'
1
a
2
V. + 37 2 ad
Unrolling this recursion we get the final result.
66

---

Algorithm 5 Q-NASTYA-PP
Input: 20g starting point, 7 > 0 - local stepsize, > 0 - global stepsize
1: for t= 0, 1....,
do
2: Sample a cohort S, with cardinality C' 'uniformly
3: for m S in parallel do
4: Receive 2y from the server and set 22,m. It
5: Sample random permutation of [r]]: 7mm. (m m -
6:
for = 0, ,,..,,,...... n 1 do
7:
Set ++1
zi.m VV VV
fm (ft.m)
8: end for
7M [2 m(,m) and send @e(gt.m) to the server 9: Compute 9t.m
end for
11: Compute O: C
1 Emes, (9t.m)
Compute F++1 Zt 799s and send #++1 to the workers
13:
end for
Output: 2T
J Partial Participation for Method with Local Steps
J.1 Analysis of Q-NASTYA with Partial Participation
Lemma J.1. Let Assumptions I, 2, hold. Then, for 2 0 the iterates produced by Q-NASTYA-PP
(Algorithm 5) satisfy
2L2 max (1 +
n-1
Eg,s, [1aad1*]] 5
C
1 xz 112 + 8Lmax (1+ ( (x)))
Mn
M C
0
C max M - 1,1
where Eg,s, is expectation w.rl. Q, St and o²
37 Em V (x (x')
Proof. E [[|E|]9]
[|l
E[[| + |[[|] obtain
Ee
[|
=EQ
Σ mes:
o
V
(zh.m)
Σ
Σ
m
Cn
m
mcS, foet
n-1
Bell Σ
fm
Tin
[13]
02
mES.
1=0
==0
Sm
pi (sk.m)
Cn
mESa 1=0
Re
Σ
1P
I15
Σ
Ei)
(xhmm)
m.lEStmmtt
67

---

Using independence between f. and & for different m, and Using (2), (3), we get
Ee
|19:1|
|
1
Σ m
Eg
o
1
(vrmm))
1
m
tm
(5i.m))
Th
n
1=0
0
1
+
V fm
(zt )
On
mESt i=0
1
fm (zf,m)
+
Jm m
(zi,m)
Cn
mES:
1=0
mES,
1=0
Rewriting previous inequality and using Vf
Σ
V
fm (zt), we have
i=0
E
|19.11
2
-
2w
Σ
m
(fi.m) - V fh (1re)
+
2w
[ (2)))
mES,
1=0
mES.
2
2
22
fmn (xi V sm (1+))
+2
mm (xzz)
Cn m 1=0
mES.
2 x1+
Σ
V
Im im (si.)) - V Viri (xte)
mES.
2w Σ I1
1 Σ Vmn (2t)
(2:) + 2
m
mES.
Using L-smoothness of fin and f and also convexity of fm. we obtain
2
2(1+
Eo [1a]|]]] <
V smin (ff,m) - V sm (xx)
On
mES,
1=0
+ 4w
Σ
I (zt) - vSm (2²))
C
mES.
+ 4w
Mm (x+))| +4
Cc
1
E(VF (x - (2*))
mES,
mESL
1
+4
V mm (x*)
C
MES.
212 max
(1
+ w)
R-1
8Lmax (1+
j - xz 2 +
EDom Drm (I))
On
C
m mE Y=0
mES.
4w +
|V (20))
+4 +4
Σ mES,
Vi (x+)
C
C
mES,
Taking expectation w.r.t. S, and using uniform sampling, we receive
68

---

Bess |19.11
2L (1+ E) Bs.
Bs
1
xTl
C
t.
n
meS, i=
+ 8 mmx
(1+ )
Es
Σ mES:
Dim (1))
C
+
Aw
Es.
1
Σ
Wm (x=))1
+ 4Bs.
Σ
fm (x*))
C
C
C
mES,
meSt
21 max
(1+
M
8Tmmax
(1 +
M
-xoll
Dim (xe,x*)
Mn
M
m= 1=0
m2
4w 1
M
1 (x*)]l
Fm (x*)]1?
M
MC max M
1,
Theorem J.1. Let step sizes n, y satisfy the following equations
16. (1 + 8) 7= 5nLmax
Under the Assumptions 1, iterates of Q-NASTYA-PP (Algorithm S) satisfy
E pr x²113] (1 2 1100 - x11 n
Σ 0² + no? m=1
r
M
+ 8 " (w
P (00 Cmax(M 1,
M-C 02 ) 0
where
M M
0.
V mm (x*)
V (x ||
m=1
As we can see, there is an additional error term proportional to C maxi 34 11.1 that arises due to client sampling in the partial participation setting. Note that when C = M (all clients are participating). this error term vanishes, allowing us to recover the previous result for the full participation case. This shows the consistency of our theoretical framework across different participation scenarios.
M C-C
69

---

Proof.
Taking expectation w.n.t Q, St and using Lemma J.1 updated, we get
Bo.s. | x²12]
=||2; x²1²- -2n 2,, 19:.
xx'|= + B [1001
(dd
Σ o
v fi (fi.m) m -=/)) )
< 1| x²1 en..
n
mES.
+
2n²²
2 max (1 +
C
w
M
Iz l| + 8nj Lmax (1+ (f
(f(zz) (ax) ((²))
Mn
m=1 1=0
w 0
C-C
+
4nj²
C'ax
M
1
<1128 x²1
2n Mn
fmi
(zi,m) It - x¹)
21 max (1 + )
M n-1
xz 1112 + 117+ Lmax (1+ 2)++)(( (f(z)) - (x)))
+
Mn
m=1 k=
M C
+
4np
C
C'mxx M - 1,1
Using Lemma F.2, we obtain
Eo,s.
|| x=1]]]
< 1|,, - -1=
7H 2
|2, x=1 (f - ( (xxx))
M n-1
+ Lmax
(1+ ④
w)
(f (xx) (x*)) + I.mmxx
Σ
j xell
Mn
+
211² 12 max (1 (1+5 ))
M n-1
bo,m - 2011 + 41²
w
+
M C
0²
Mn
C
C max M - 1,
m=1 im0
|1-re - 1=1 (1 11881/ 8max
(1+
(f (xx) - f (x*))
2
11 Lmax (1 + 21/
(1 )))
M n-1
| 1|
Mn
m=1 1= 0
2np
w
M-C C
C
Caax M - 1,1
Using Lemma F.3, we have
Eq.s. |1e411 - x² =²1]?] < <(1
2 -0-2)
7711
) ||- 1 x=112 7 (1 1-8LLL (1+ (1+
- f (f(x))((x*)) (x'))
(1+ 21 (1+ w )))= 8822' Lmax (f (x+) - f (x*))
+ n mmaa
1 M
+ nn Im
(1+22 (1+
2722
Σ
02 - + no?
M
m=l
+ 4n²²
w +
M -
0.
C
Cmax M - 1,
Finally, we receive
70

---

Be,s, |10et1 2²11²]
$ (1 1711
2 1lare -x*11 41²
w M -
c Cmax M 111
1) (1 -1- 1187/mmax
(1+ w)
8 Lmaxx
(1+2Lmax')
(1+ ())) (f (f())) f(x)) -f()))
M
+ 27 nmxxxxxxx (1+27L [1 )
oe.m + tno
M
m=1
$ (1
mi
2 || - -x"1|=+ + 41p²
w
0
c
C' max M - 1,1
M
9 + m n2n
Σ
- +m
+
no?
4
M
m=
Recursively rewriting the inequality and using +000 (1 (1-3) (1-4)² s 2. we finish proof.
71

---

Algorithm 6 DIANA-NASTYA-PP
Input: 20 starting point, (ho.m }M m=1 initial shift-vectors, 7 0 local stepsize, global
stepsize, or > 0 - stepsize for learning the shifts
for t = 1,.......... ......,. T do
2: Sample a cohort S; with cardinality C' uniformly
3: for S, in parallel do
4: Receive Ky from the server and set st,m It
5: Sample random permutation of [n)] 7m. (m -
6:
for = 0, ,,..,.., n do
7:
Set Set fim 7 V. mm (st,m)
8:
end for
9:
Compute It.m n
1 Øt m7mm) and send 2e (gt.m h)m)) to the server
10:
Set h4t1, = hem + Q (gt.m h)m))
11:
Set 9t.m he.m + Q (gt.m- hemm)
12:
end for
13:
14+1 C Ems,, 1et1. 14 + Emes, Qe (gt.m h)mm)
14:
9t Emes, Ht.m = li + Emes, Qr (gr.m h)m))
15:
1t++1 Itt 1/9t
16:
end for
Output: 2T
J.2 Analysis DIANA-NASTYA with Partial Participation
Theorem J.2. Let step sizes nl 7 satisfy the following equations
1
C
1) min
80 (1+ 8)
[((++))))
7
5nLmax
Define the Lyapunov function:
A 1 1 1|=1-=0111-
1 ht
where
A Xn12. Selecting parameters
I+w
aM Y
5nLomax also using 1)
min
C
Under the Assumptions 1, 2, 3 iterates of DIANA-NASTYA-PP (Algo-
M(1+W)M 80Lmax (1+
rithm
satisfy
np T E [ < (1-
3x2 L2 L2
M
2n(M C)) WC max (1, M
E [[ +
Σ
mm + no?
o..
2
M
Note that eliminate the variance term proportional to 8 oo? In the Partial Participation
regime, we have variance term proportional m which equals zero if C .M. This term decreases O (t),, so achieve the expected linear speedup.
(M-C)
72

---

Proof. STEP 1: we need to estimate inner product. By 9. EmEs, Hum we have
(2
- x² |]
Σ mES,
-Ee
C
Ic
E
It.m
2 x²
L
M
Er [0tmml] 32 - I.a
M
M
x²)
M
m=1
1
N Us x²))
M
m=
||-|e
- x= 1=1
2 (f (f - (x*))
1 M
fm (x" )
Mn
m=1 1=0
L
n-1
+
2t Ft
2M
STEP 2: We need to bound E @g By 9: C
1
Σ
It.m we have
meS,
Eg
|1 12|
=Eg
(he. + 2 (gt.m - hemm) -t.m + 9t,m)
C
mES:
Eg
Σ
(he.m + 2 (ge.m - hemm) - m)
+
Σ
It.m
mES,
mES,
2
Ee
[llee,m + Q (gt.m h1,
+
9t.m
meS,
mES,
2
119t. N 1amm122 12
Σ
Jt.m
mcS,
mES.
2w
2w
119t.
V (x:))1
fm (x+)
hemml 11
mcS,
mES.
1 Σ
2
Jt.m
ti=t
+2
h
mES,
mES,
Taking expectation by subsamling, we have
73

---

M
2w M
2w 1 C
Bes.
10:112
Σ
11
vm (xe)1 +
V fm (xx) hem 11?
M
C M
m=1
m=
M
2(M C)
l1gc. 11
|| 1|
M
C(M 1)M
M
M
2 C
20
1
119.. Vmn (2x))1
+ C
2w
Vmm (2x)) -1 11
M
M
M
Σ
l19c.
Vmm (2s)]]
+
Σ
|V (Ix) hmml" 11
M
M
m=1
m=1
2(M - C)
M
Σ
C(M
1)M m=1
<4
L
max
n-1
a 12el 2
2w 1
Σ
Vm (2re) mmml²
C
Mn
C M
8 Lmmax
M
2(M C)
M
Σ
Dim
(20,, x
C(M-1)) 1)M Σ
| ?1?
M
-
m=1
m=1
M n-1
M
w
| t.m - xzll2 +
2w
V fm (xt) - he 11
C
Mn
C M
m= 1=0
m=
8Lmax (xx) f (x.)) + -
Σ
|1 11?
C(M
1)M
Thus, we have
Boss, [11441-2111
s11 T ||0 - x111 - -1- (1 4Lmax (f (xz)) - ff (x*))
Tmmx (1+4 +1+ I.max)1)
1
Σ Σ
|
sell
Mn
x=0
2n12w 1
C M Σ V (xt) - he 2 + 2n C)
M
Σ ||
+
C(M - 1)M
STEP 3: Note that
M
C1
1= M - C 1
M-C
1
Σ
[het1.m
Σ
|1 h;,11
M
MC
M M mgS.
mES.
Taking expectation by compression, have
74

---

e
Σ
|| m1 = Ee
1
Σ
llke,m + (2 (ft. m)m k 11?
C
C
mES:
mES.
1
(lhe.m kmll2 + 2ax (gr.m me, hem hmd + aa2(111 w) I19e.
hemm 12²
C
mES.
1//11t
(1leeim - -hiill + 2cx (grm
+ a l1 - hemmll he hem hind
mESt
C
|1,e, ninll
1 +
a
Σ
119t. - ml
C
C
MES:
mES
Taking expectation by subsampling, we have
Eo,s,
Σ
|1
11
S E.
1-a Σ
11
Σ
119t.
hmm 112
mES.
mES.
meS.
M
M
a
1m +
1
1 11?
M
M
m=
m=
Thus, we have
Es,
1
(1 aC
Σ 11em
aC
M Σ
1t.m
h
M
M
M C
Es.
Σ
I
him !1?
M
mgS.
a)C
M
aC
M
Σ
9t.m
h 11
M
M
M
C
M
M
M
m=l
aC
1
h
h 112
M
M
2aL2 max
max
C
M2n
2m0
4Lmax
Σ
Dym (Xr, x+).
M
STEP 4: Defining Lyapunov function as follows
M
A
V ||
201
+
h ht
M
75

---

we have
B 1 [1++1] 5 (1- TT
|0, x²1² - 11(1 4Lmax 1) (f (x,) - f (a*))
2
M n-1
+ nLmmx
(1+ 4 [1
w ()) Lmax'i)
Σ
x I'e 11
Mn
m=1 i=0
2
M
2nj² 2M - -C)
M
+ M
V (xt) - hemmell
| ll
0
C(M 1)M
m=1
m=1
aC
A
+ 1
Σ
M
M
2x 1 max
AC
Σ
n-1
xel2²
4 (
+
M²n
Setting Xxx² and using Lemma F.3, we have
E [4+1 5511 - 1711 E |1ore - 11] + (1 aC
4w
Xn2
Σ E
nmml" 11
2
M
XC
M
m=1
17 1 1 S1yLmax (1+ w 4m
C
E [f (xx) f(x)]]
M
8 Dnaxx" (1+ (1+4mlmax (1+ + 21plmaxad C'
E[s 1
M
+ 22 " !!
41/mmax (1+ W) ))= + +21
C
(
1
Σ
o. + no
M
M
+ 27 - C³
C(M - 1)
Selecting & = 1 A
8w atf
17
#(1+wjJ7 also using 17
80 (1+
and applying previous steps we obtain
5y.demax
E E s (1-")
7/1
E
[
+ +
L L
1
-m + no?
2772(M - -C) C(M -1)
M
- 17 2
2 2
B[s (Ir)) - (xx))
< <(1 <1-
1/11
E
[ k) + 3- 2n I2 m
Σ
M
2 + no?
+ 20 - C) of
2
M
C(M - 1)
m=1
76

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly outline contributions in the abstract and introduction, and also include a dedicated Contributions section.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We clearly highlight all assumptions and limitations in the text.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
77

---

The main contribution of the paper is its theoretical analysis. We support the paper with necessary definitions, assumptions, and lemmas.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper is supported by reproducible experiments, with all stochastic ele- ments from pseudo-random generators fixed in advance. For details, see the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
78

---

reproducible, they Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We aim to make the paper and all source code for experiments open-sourced to accelerate scientific findings the field of Federated Learning and Machine Learning in general. For details, see the supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
Mhbllii/guides/CdeSSttmii www.ssmbbsssiooosioooooooooee for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ /twpps.cccpppppeee//o/ weaicc/guies///ee CaaieesssoooSebiiiicce iimmiissionnn onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide detailed guidelines for experiments setup in Appendix and in the folder with experiment source code. For details, see the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We provide detailed guidelines for experiments setup in Appendix and in the folder with experiment source code. For details, see the supplementary materials.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
79

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: The paper provides information on the computer resources in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Our research focuses on mathematical objects and does not involve human subjects or participants. The data used for our experiments consists of publicly available datasets. Our work does not explicitly address or examine the social implications of applying this research in practice.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work operates on mathematical objects, and the essence of our work provides new optimization algorithm. Because of theoretical nature of our work the impact discussion is not applied.
80

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considcrations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper provides optimization algorithm with the required theory. The data or models are not output assets of our work.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We provide references for used datasets and deep learning models used in experiments.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
81

---

The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The output assets of our paper is Algorithm and Source code for experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
82

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
83


Reviews:
[{"review_id": "LkT2F0qJR6", "reviewer": "Reviewer_zJsy", "summary": "This paper provide analysis of methods with gradient compression and without-replacement sampling. Based on this analysis, this paper proposes several new algorithms for distributed optimization with communication, including Q-RR and its vairants Q-NASTYA, which compress gradient differences in the scenario of data random shuffling. Empirical results on logistic regression and resnet-18 on cifar10 show that the proposed algorithm outperforms the baselines.", "questions": "1. Regardless of DIANA itself, what exactly is the difference between the \"compress gradient differences\" proposed in this paper and the algorithm of EF21?\n\n2. Could EF21 also be included in the experiments as a baseline?", "limitations": "Except for the weakness mentioned above, the limitations of this paper is well discussed and addressed.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. This paper provide analysis of methods with gradient compression and without-replacement sampling. \n\n2. Based on this analysis, this paper proposes several new algorithms for distributed optimization with communication, including Q-RR and its vairants Q-NASTYA, which compress gradient differences in the scenario of data random shuffling. \n\n3. Empirical results on logistic regression and resnet-18 on cifar10 show that the proposed algorithm outperforms the baselines.", "weaknesses": "1. The idea of compressing gradient differences is actually not very novel. EF21 [1] proposed compressing gradient differences a long time ago. The algorithm of EF21 also looks very similar to DIANA-RR. I think DIANA-RR is basically a combination of DIANA and EF21. Unfortunately, I lost track of the huge number of variants of DIANA, so I'm not exactly sure whether the variant of DIANA + EF21 has already existed somewhere.\n\n2. Since EF21 already uses compression of gradient differences, I think EF21 is a better baseline than QSGD. However, EF21 is not included in the experiments.\n\n\n--------------------\nReferences:\n\n[1] Richtárik, Peter et al. “EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback.” Neural Information Processing Systems (2021).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**... including Q-RR and its variants Q-NASTYA, which compress gradient differences in the scenario of data random shuffling.**\n\nJust to clarify, Q-NASTYA is not a variant with compressed gradient differences. The variants that utilize compressed gradient differences are DIANA-RR and DIANA-NASTYA, as they are based on the DIANA technique, which specifically compresses gradient differences.\n\n>**The algorithm of EF21 also looks very similar to DIANA-RR. I think DIANA-RR is basically a combination of DIANA and EF21. Unfortunately, I lost track of the huge number of variants of DIANA, so I'm not exactly sure whether the variant of DIANA + EF21 has already existed somewhere.**\n\n>**Regardless of DIANA itself, what exactly is the difference between the \"compress gradient differences\" proposed in this paper and the algorithm of EF21?**\n\nFrom these comments, we see that you have some questions related to DIANA, EF21, and our DIANA-RR. We explain the main features of those methods and emphasize the differences between them.\n\n**DIANA**. The DIANA method was proposed by [Mishchenko et al, 2019] as a fix to the QDGD (quantized distributed gradient descent) leading to linear convergence to the exact solution in a strongly convex case compared to QDGD. As you can see, for QSGD, there is a neighbourhood term corresponding to data heterogeneity in the complexity (see Table 1). The same phenomena have a place for QDGD. This is why DIANA can be seen as a variance reduction technique for unbiased compression. Next, DIANA is designed for unbiased compression operators (see Assumption 1); this is crucial for the analysis. The third property of DIANA, which can be inferred from the complexity results, is that the convergence rate improves when $M$ increases. In other words, the neighbourhood terms decrease with the increase in the number of clients $M$. \n\n**EF21**.  EF21 is an improved version of a well-known error feedback technique [Seide et al., 2014]. EF21 works for the wider class of compressors called biassed compressors. However, the convergence rate does not improve when $M$ is large. Also the gradient estimator in EF21 is biassed, which brings another challenge for convergence analysis. Moreover, a naive combination of EF21 with SGD requires to use of large batchsizes; see [1]. \n\n**DIANA-RR**. This new algorithm combines the DIANA technique and sampling without replacement (a.k.a. RR). However, the combination is not straightforward (we do not simply plug in RR estimator in DIANA) and requires several modifications: first of all, we do not wait until each client goes through the whole dataset to send information at the end of each epoch. Instead of this, we construct the algorithm to send a compressed gradient from clients to the server on each step of the epoch, and we make a gradient step on the server. To set up such an approach correctly, we set for each client their own set of shift- vectors $h^i_{t,m}$, which differs from the original DIANA method.\n\nAs one can see from the above explanation, DIANA, DIANA-RR, and EF21 are completely different methods, and DIANA-RR is not a combination of DIANA and EF21, as the reviewer claims.\n\n[1] Fatkhulin et al. Momentum provably improves error feedback! NeurIPS 2024.\n\n>**The idea of compressing gradient differences is actually not very novel. EF21 [1] proposed compressing gradient differences a long time ago.**\n   \nWe do not claim that we are the first who propose usage gradient differences to improve the performance of FL algorithms with communication compression. It was proposed in the DIANA paper, which is much older than EF21.  One of the main messages of our work is that the naive approach of a combination of RR and gradient compression (i.e., Q-RR) has no improvements over vanilla QSGD. Therefore, we combine two techniques – RR and DIANA – to improve Q-RR, but the combination is not trivial, as we explain above.\n\n>**Since EF21 already uses compression of gradient differences, I think EF21 is a better baseline than QSGD. However, EF21 is not included in the experiments.**\n\nAs we mentioned earlier, EF21 is a method designed for biased compression, which is not the focus of our current work. In this paper, we concentrate on unbiased compression techniques. We plan to explore biased compression in future research.\n\n>**Could EF21 also be included in the experiments as a baseline?**\n   \nSince we do not consider biased compression in this paper, we do not see a clear reason why we should add EF21 to the comparison. Our work is primarily theoretical, and the main goal of our experiments is to illustrate and support our theoretical findings. Thus, experiments with EF21 would be completely unrelated.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "4Kkh8Oaztb", "reviewer": "Reviewer_r1qn", "summary": "Gradient compression is a popular technique for improving the communication complexity of stochastic first-order methods in the distributed training of machine learning models. This work points out that existing work only considers with-replacement sampling of stochastic gradients, while in practice stochastic methods based on without-replacement sampling performs better. This paper fills this gap in the literature by analyzing for the first time methods that combine gradient compression and putback-free sampling.", "questions": "When tuning parameters (e.g. step size), could you try a more efficient way of tuning the parameters to increase the scalability of the algorithm? Whether there are plans to develop automated methods for tuning parameters to reduce the complexity of manual tuning and increase the feasibility of the algorithm in practical applications?\n\nDue to the increased implementation complexity of the algorithms proposed by DIANA-RR et al. are there any performance evaluations in practical applications, especially how well they perform in large-scale distributed systems?", "limitations": "The algorithm in this work relies on many parameters, but lacks corresponding experimental proofs. For example, DIANA-RR uses multiple shift vectors (n of them), while DIANA uses only 1 shift vector, and there are no experimental results showing the effect of different number of shift vectors on the performance. There are no detailed experimental results showing the effect of different compression levels on the performance of the algorithm at different compression levels. etc.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) This work introduces a unique combination of gradient compression and random reshuffling, which addresses a gap in the existing literature. This innovative approach aims to improve convergence rates and communication efficiency in distributed learning.\n\n(2) This work summarizes previous algorithms while providing rigorous theoretical analysis and convergence proofs for the proposed new methods (Q-RR, DIANA-RR, Q-NASTYA, DIANA-NASTYA).This solid theoretical foundation helps in understanding the behavior and benefits of the new algorithms.\n\n(3) The article is clearly structured, logically coherent and step-by-step. The research is clearly presented.", "weaknesses": "While the experiments conducted are thorough, they are limited to certain types of tasks (logistic regression and ResNet-18 on CIFAR-10). The generalizability of the results to other models and datasets is not fully explored, which could limit the broader applicability of the findings.\n\nQ-NASTYA and DIANA-NASTYA algorithms are too dependent on hyperparameters, which requires additional computation and management, affecting the practical application and deployment of the algorithms, especially in large-scale distributed environments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback and a very positive evaluation of our work.\n\n>**While the experiments conducted are thorough, they are limited to certain types of tasks (logistic regression and ResNet-18 on CIFAR-10). The generalizability of the results to other models and datasets is not fully explored, which could limit the broader applicability of the findings.**\n\nThank you for your comment! We will try to do additional experiments on other datasets and models.\n\n>**Q-NASTYA and DIANA-NASTYA algorithms are too dependent on hyperparameters, which requires additional computation and management, affecting the practical application and deployment of the algorithms, especially in large-scale distributed environments.**\n\n>**When tuning parameters (e.g. step size), could you try a more efficient way of tuning the parameters to increase the scalability of the algorithm? Whether there are plans to develop automated methods for tuning parameters to reduce the complexity of manual tuning and increase the feasibility of the algorithm in practical applications?**\n\nThank you for your comment! We agree that dependence on hyperparameters is a limitation of our methods (though many methods in the field have the same similar limitation). We will think about adaptive versions of the proposed methods (and incorporation of recently proposed adaptive methods such as D-Adaptation, Prodigy, and Schedule-Free SGD). We leave it for future work. Regarding the tuning of parameters for our methods in practice, the standard schemes for tuning the stepsizes (e.g., search at the logarithmic scale) should work well.\n\n\n>**Due to the increased implementation complexity of the algorithms proposed by DIANA-RR et al. are there any performance evaluations in practical applications, especially how well they perform in large-scale distributed systems?**\n\nWe will do our best to run the methods with a larger number of workers. Then, we can measure the efficiency of the methods in terms of the number of communicated bits to achieve convergence w.r.t. different metrics (top-1 accuracy, train loss, gradient norm).\n\n>**The algorithm in this work relies on many parameters, but lacks corresponding experimental proofs. For example, DIANA-RR uses multiple shift vectors (n of them), while DIANA uses only 1 shift vector, and there are no experimental results showing the effect of different number of shift vectors on the performance. There are no detailed experimental results showing the effect of different compression levels on the performance of the algorithm at different compression levels. etc.**\n\nWe agree with the reviewer that all of these experiments are important and would strengthen the paper. We will do our best to include them in the final version. In particular, we conducted the experiment with a $1$ local shift for DIANA-RR and attached the results to the general rebuttal message. Our results indicate that the usage of multiple shifts is important for DIANA-RR, since otherwise, the method does not work better than DIANA.\n\nRegarding the experiments with different compression levels, we expect that the behaviour will be expected: the less we compress, the better all methods converge, and the less the impact of shifts is.\n\nHowever, we also would like to emphasize that our work is primarily theoretical, and the experiments are mainly needed to illustrate and support our theoretical findings.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VynvttrTNr", "reviewer": "Reviewer_BTLT", "summary": "The authors propose communication-efficient distributed learning algorithms with faster convergence rates than previous methods. Their starting point is mini-batch stochastic gradient descent (SGD): Previous works have shown that random reshuffling (RR), i.e. sampling mini-batches without replacement (in other words, having clearly defined training epochs), has better theoretical convergence guarantees than sampling with replacement. \n\nInspired by this, in the first part of the paper, the authors propose the most natural extension of RR to the distributed learning setting: the clients quantise the gradients they computed to communicate the gradients to the server efficiently. The authors derive a bound on the quantised RR (Q-RR) convergence rate (assuming the loss is convex and its gradient is Lipschitz) and show that as the quantisation error goes to 0, their bound recovers the convergence results for non-quantised RR. However, when the quantisation error is nonzero, Q-RR no longer has an advantage over quantised SGD (Q-SGD), as quantisation introduces an additional error term that negates the benefits of RR. The authors use a variance reduction technique called DIANA to deal with this issue and name this improved method DIANA-RR. They show that DIANA-RR removes the troublesome error term and attains the faster convergence rate of RR even when the gradients are quantised. \n\nIn the second part of the paper, the authors observe the same behaviour when the clients perform the model updates and send quantised weight differences instead of gradients. That is, the authors show that quantising the weight differences introduces too much noise, which negates the benefits of RR. However, introducing the same variance reduction technique as in the SGD case restores the benefits of RR.\n\nFinally, the authors perform some basic federated learning experiments and show that their proposed methods outperform the competitors even when the losses involved are non-convex.", "questions": "n/a", "limitations": "The authors don't discuss any of their methods' limitations (see, e.g., my main technical concern in the weaknesses section); I think such a discussion would significantly strengthen the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The authors provide a rigorous, insightful analysis of simple extensions of previous methods. Concretely, their analysis reveals the flaws of the naively quantising SGD using random reshuffling, which motivates the more involved, control-iterate-based extensions. They then show that the more involved methods retain the benefits of their original, unquantised counterparts. I checked the proofs of theorems in appendices C.1 and D.1, and I believe they are correct.", "weaknesses": "I should note that I am not an expert in federated learning, so I cannot fully evaluate the significance of the authors' contributions or how realistic some of their assumptions are in practice.\n\nFrom a technical perspective, my main concern is that I am unsure how challenging it is to realise random reshuffling in practice. As I understand, using the authors' algorithms does not allow the server to start the next training epoch before every client sends updates for the current epoch. This sounds like a severe limitation, as in the worst case, some of the clients might drop out (e.g. due to connectivity issues) and never send any updates, causing the training loop to get stuck. Could the authors please comment on this? If this is a genuine concern, then the authors should discuss this limitation in the main text.\n\nThe other issue with the paper is the writing needs to be improved significantly. While the introduction section is well-written, it is three pages long, which means there is not enough space to expose the large amount of content that the authors wish to include at the level of formality they want to use. Concretely, the paper goes from a high-level discussion in the introduction section to being immensely technical in section two, with many new quantities and notations introduced without explaining what they represent. For example, what is the interpretation of the shuffling radius, or the quantity in Eq (6)? However, even more importantly, the methods the authors base their work on, namely DIANA and NASTYA, are not explained; the reader only has the pseudocode given in Algorithms 2-4 to work with. The best illustration of this is the disconnect between the paper title and its contents: there is no explicit mention of compressing gradient differences in the main text. I believe the authors' use of DIANA inspires the title, but I am not fully sure. Furthermore, the pseudocodes in Algorithms 1-4 are ambiguous, as the authors mix what happens on the client's side and on the server's side. I suggest the authors break up the code into two parts, one demonstrating the server-side operations and one showing the clients' side.\n\nBesides this, more minor weaknesses include:\n - I find Eq (1) and similar equations combining definitions with statements very confusing; please separate the two.\n - As defined, assumption (1) doesn't make sense; the expectations have no meaning as $Q$ is not stochastic; please make the meaning precise.\n - The symbol $n$ denoting the batch size is technically undefined; it should be included in the chain of equalities on line 34\n - Table 1 is difficult to interpret, and it is unclear to me what value it brings to the paper. I would either move it to the appendix or cut it altogether and use the space to address my main concern, which I outlined above.\n - Over what is the expectation in Def 2.1?\n - Figures 2 and 3 should be renamed to Figures 1a and 1b, respectively.\n - Merge the two panels in Figure 4\n - Algorithm 1, steps 2 and 3, $x_{t, m}^0$: the symbol $m$ is undefined", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**From a technical perspective, my main concern is that I am unsure how challenging it is to realise random reshuffling in practice.**\n\nRR is a well-known technique exploited in many applications: for ML training, for SGD, Monte Carlo methods, etc. For example, in many ML frameworks, such as TensorFlow or Pytorch, random reshuffling of the training dataset is performed at the beginning of each epoch to ensure that the models do not learn the order of training data.\n\nThe specific implementation and initialization of random reshuffling depend on the programming language, library, or framework being used. Most modern data processing and machine learning libraries provide built-in functions for random reshuffling, making it easy to integrate into various workflows.\n\n\n>**As I understand, using the authors' algorithms does not allow the server to start the next training epoch before every client sends updates for the current epoch. This sounds like a severe limitation, as in the worst case, some of the clients might drop out (e.g. due to connectivity issues) and never send any updates, causing the training loop to get stuck. Could the authors please comment on this?**\n\nPartial Participation and asynchronous setting are important aspects of distributed optimization. However, we believe that one paper cannot cover all possible aspects of the field. Otherwise, each paper would be several hundreds of pages. In this work, we focus on data sampling but not client sampling. We can extend our results to the partial participation setting but we believe that it will be more complicated for readers to understand the results. We believe that for the sake of readability, the paper should be focused on one or two particular ideas, and the questions that we address (how to combine RR, unbiased compression, and, optionally, local steps) are challenging and interesting on their own.\n\n>**The other issue with the paper is the writing needs to be improved significantly. While the introduction section is well-written, it is three pages long, which means there is not enough space to expose the large amount of content that the authors wish to include at the level of formality they want to use. Concretely, the paper goes from a high-level discussion in the introduction section to being immensely technical in section two, with many new quantities and notations introduced without explaining what they represent. For example, what is the interpretation of the shuffling radius, or the quantity in Eq (6)? However, even more importantly, the methods the authors base their work on, namely DIANA and NASTYA, are not explained; the reader only has the pseudocode given in Algorithms 2-4 to work with. The best illustration of this is the disconnect between the paper title and its contents: there is no explicit mention of compressing gradient differences in the main text. I believe the authors' use of DIANA inspires the title, but I am not fully sure. Furthermore, the pseudocodes in Algorithms 1-4 are ambiguous, as the authors mix what happens on the client's side and on the server's side. I suggest the authors break up the code into two parts, one demonstrating the server-side operations and one showing the clients' side.**\n\nWe thank the reviewer for the suggestions. If our paper gets accepted, we will have an extra page to add more clarifications to the main text. We also can shorten the introduction. We believe these adjustments can be easily done.\n\n>**I find Eq (1) and similar equations combining definitions with statements very confusing; please separate the two.**\n\nEq (1) is the standard finite sum formulation of the optimization objective, see (Mishchenko et al., 2019; Stich, 2020; Haddadpour et al., 2021). \n\n>As defined, assumption (1) doesn't make sense; the expectations have no meaning as $\\mathcal{Q}$  is not stochastic; please make the meaning precise.\n\nWe consider only the case when $\\mathcal{Q}$ is a random operator, e.g., see (Horvath et al., 2019). This assumption is satisfied for many compression operators, e.g., for random sparsification and quantization.\n\n>**The symbol $n$ denoting the batch size is technically undefined; it should be included in the chain of equalities on line 34.**\n\nThank you for noting this; we will add $n$ to the sentence as advised.\n\n>**Table 1 is difficult to interpret, and it is unclear to me what value it brings to the paper. I would either move it to the appendix or cut it altogether and use the space to address my main concern, which I outlined above.**\n\nTable 1 is very important, and it summarizes our main theoretical results. We will address your concerns without removing the table.\n\n>**Over what is the expectation in Def 2.1?**\n\nThe expectation is taken with respect to data permutation, which is the essential part of the random reshuffling method.\n\n>**Figures 2 and 3 should be renamed to Figures 1a and 1b, respectively.**\n\nThank you for the suggestion. We will update the paper accordingly.\n\n>**Merge the two panels in Figure 4**\n\nWe believe that it makes the plot more complicated. On the first one you can observe the performance of QSGD and Q-RR and how it is similar. On the second, it is clear that DIANA-RR works better than DIANA. To compare Q-RR and DIANA-RR it is enough to compare the obtained accuracy. \n\n> **Algorithm 1, steps 2 and 3, $x^0_{t,m}$: the symbol $m$  is undefined**\n\nWe will make such an adjustment.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lAdfnbZLNk", "reviewer": "Reviewer_X78L", "summary": "This paper analyzes compressed Federated Learning algorithms in the setting of Random Reshuffling. It first provides theory for RR with compression (Q-RR), and several variants (based on existing methods for compressed SGD) which have improved convergence guarantees. The paper sets the hypothesis that naive Q-RR does not yield improvements compared to Q-SGD (based on theory and experiments). However, the theoretical results show that the proposed DIANA-RR indeed improves over its SGD-variant when the number of samples is comparatively small to the number of iterations.", "questions": "This question relates more broader to Random Reshuffling: if you use mini-batching, and do RR with the standard Pytorch framework, then the composition of the mini-batches will be different in every epoch (the DataLoader shuffles, and then partitions into batches). In that case, the theoretical framework of the paper does not fully apply anymore, correct? This is, because in every epoch you would have a different set of $f_m , m=1,..,M$ where each $f_m$ is a mini-batch loss.\n\nIs there a way to overcome this small incosistency between Random Reshuffling analysis and the actual usage? Or is there RR analysis that explicitly takes into account mini-batching?", "limitations": "I commented on possible limitations in terms of content above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithms are the natural extensions of existing methods (DIANA, NASTYA,..) for the RR setting. All methods are supported with theory for the strongly convex, smooth case. The theory further sheds light on possible improvements from RR in the setup of Federated Learning with compressed communication.\nThe provided experiments nicely complement the theoretical results (with some caveats, see below). One of the main takeaways (also represented in the title of the paper) is that the DIANA-variance-reduction technique for compression yields improvements from RR compared to the SGD-variant.", "weaknesses": "1) On the main hypothesis that reducing the compression variance brings improvement, it is yet unclear whether this is also a necessary condition. The paper does provide a convergence result for Q-RR that does not improve over Q-SGD; but what would be preferable is a lower bound that shows how Q-RR can not improve over Q-SGD in a worst-case example. This is currently missing to complete the picture. While the experimental result presented in the main text also support the hypothesis, there are some caveats (see next point).\n\n2) The results for CIFAR10 in the main text suggest that Q-RR is on par with Q-SGD. However, in the appendix it becomes clear that this experiment refers to only training the last layer (see Fig. 12). When training the whole network (Fig. 10), the results suggest that Q-RR is actually much better than Q-SGD, and the gap is roughly equal to DIANA vs. DIANA-RR. The main text does not mention this, so this result is hard to find if it's only presented in the appendix. I would ask the authors to clarify this part in the main text - in particular, because this result weakens one of the hypotheses that the DIANA technique is necessary to get improvements (at least for nonconvex problems, like the ResNet example is). If I missed something important here, please let me know - I am happy to discuss details.\n\n3) The logistic regression examples show a clearer picture, but only three datasets are tested, and all of them are very low-dimensional ($d<500$). I would suggest to add more high-dimensional datasets, or other deep learning experiments to have more insight whether there is a difference between Q-SGD and Q-RR. \n\n4) All theoretical results only apply to strongly convex, smooth functions. While this is a standard framework for optimization analysis, it is very far from most modern machine learning applications, thus restricting the applicability of the results for such nonconvex, nonsmooth problems.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">**On the main hypothesis that reducing the compression variance brings improvement, it is yet unclear whether this is also a necessary condition. The paper does provide a convergence result for Q-RR that does not improve over Q-SGD; but what would be preferable is a lower bound that shows how Q-RR can not improve over Q-SGD in a worst-case example. This is currently missing to complete the picture. While the experimental result presented in the main text also support the hypothesis, there are some caveats (see next point).**\n\nAs the reviewer fairly notices, we provide only upper convergence bounds: according to them Q-RR is not better than QSGD, and DIANA-RR has a better worst-case guarantee than both methods and the original DIANA. Deriving algorithmic dependent lower-bounds for Q-RR is indeed an interesting research question that would complement our work and support the hypothesis. Nevertheless, our experiments also support our hypothesis, as the reviewer noticed. Therefore, the importance of deriving such a lower bound is minor. Moreover, this might require a lot of work deserving another paper since we are not aware of any algorithmic-dependent lower bounds in the literature on distributed optimization with compression.\n\n>**The results for CIFAR10 in the main text suggest that Q-RR is on par with Q-SGD. However, in the appendix it becomes clear that this experiment refers to only training the last layer (see Fig. 12). When training the whole network (Fig. 10), the results suggest that Q-RR is actually much better than Q-SGD, and the gap is roughly equal to DIANA vs. DIANA-RR. The main text does not mention this, so this result is hard to find if it's only presented in the appendix. I would ask the authors to clarify this part in the main text - in particular, because this result weakens one of the hypotheses that the DIANA technique is necessary to get improvements (at least for nonconvex problems, like the ResNet example is). If I missed something important here, please let me know - I am happy to discuss details.**\n\nAlthough we do not have formal proof explaining this phenomenon, we conjecture that this can be related to the significant over-parameterization occurring during the training of a large model on a relatively small dataset. That is, the model can almost perfectly fit the training data on all clients, leading to the decrease of the heterogeneity parameter $\\zeta_\\ast$. In this case, there is no need for shifts since the variance coming from compression naturally goes to zero, and the complexities of QSGD and DIANA match (see Table 1). In this situation, Q-RR performs better than QSGD since the compression does not spoil the convergence of RR. Therefore, DIANA-type shifts are not always necessary to get improvements. Nevertheless, we conjecture that they are necessary when the datasets are larger and more complex (since in this case the models do not perfectly fit the data).\n\n>**The logistic regression examples show a clearer picture, but only three datasets are tested, and all of them are very low-dimensional (). I would suggest to add more high-dimensional datasets, or other deep learning experiments to have more insight whether there is a difference between Q-SGD and Q-RR.**\n\nWe agree with the reviewer that the additional experiments are important and would strengthen the paper. We will do our best to include them in the final version. However, we also would like to emphasize that our work is primarily theoretical, and the experiments are mainly needed to illustrate and support our theoretical findings.\n\n>**All theoretical results only apply to strongly convex, smooth functions. While this is a standard framework for optimization analysis, it is very far from most modern machine learning applications, thus restricting the applicability of the results for such nonconvex, nonsmooth problems.**\n\nWe agree that many practically important problems are non-convex. However, the main goal of our paper was to understand how to combine RR and unbiased compression properly. This research question is not related to the convexity of the problem, and it was natural for us to investigate it in the strongly convex case first. Moreover, in many cases, convex optimization serves as inspiration for methods that work well even for non-convex problems. For example, the well-known Adam uses a momentum trick. However, we know that momentum does not theoretically improve convergence in non-convex cases..  Moreover, momentum was initially proposed by Boris Polyak to accelerate the convergence rate for GD in a convex setup (more specifically, for strongly convex quadratics). Next, very successful optimizers for DL proposed recently, such as D-Adaptation [1], Prodigy [2], and Schedule-Free SGD [3], were designed and analyzed for convex problems only. Nevertheless, they work well in the training of neural networks. To sum up, we want to say the initial step in the direction considered by us is natural. \n\n[1] Defazio & Mishchenko. Learning-Rate-Free Learning by D-Adaptation. ICML 2023\n\n[2] Mishchenko & Defazio. Prodigy: An expeditiously adaptive parameter-free learner. ICML 2024\n\n[3] Defazio et al. The Road Less Scheduled. arXiv preprint arXiv:2405.15682", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their feedback and time. We addressed all the questions, comments, and concerns raised by the reviewers in separate messages.

Following **Reviewer r1qn** question about the importance of the usage of multiple shift vectors in DIANA-RR, we conducted additional experiments with a modification of DIANA-RR that uses just one shift vector per client (DIANA-RR-1S). One can find the results in the pdf-file attached to this message. Our results indicate that the usage of multiple shifts is important for DIANA-RR, since otherwise the method works not better than DIANA.

Meta-review: In the context of communication-efficient distributed finite sum optimization problem, the authors show that it is posssible to prove that random reshuffling can converge faster than sampling with replacement, which has empirically been known to practicitioners. The authors first show that naive combination of gradient quantization and random reshuffling (Q-RR) does not lead to a better upper bound compared to quantized SGD with sampling with replacement (Q-SGD). Then the authors show an improved bound for DIANA-RR which combines compression of gradient differences proposed in DIANA with Q-RR.

The paper is mostly clearly written except that the title "compress the gradient differences" in title seem to have caused confusion with some reviewers because the paper is not the first paper to propose this.

Some reviewers thought the paper was lacking novelty because the proposed method was a combination of DIANA with random reshuffling. The authors have responded well during the rebuttal and clarified that the combination is not at all trivial.

In terms of the practical applicability, it seems that the method requires FP64 precision in its current form. This seems like a hurdle the authors need to address for the scalability and wider adoption of the method. The authors responded that the contribution of the paper is primarily theoretical.

As a theory paper, the biggest weakness to me was the fact that it is unclear if variance reduction through DIANA is necessary both in theory and in practice, especially when the model is over-parametrized. The story would have been more convincing if the authors could show lower bound of achievable error for the Q-RR method.

Overall I feel the scope of the paper is fairly narrow (gradient quantization and random reshuffling; not clear if the method can tolerate low-numerical precision; not clear if the DIANA variance reduction method is required when the model is over-parametrized) but has an interesting contribution.
Decision: Accept (poster)