Methods with Local Steps and Random Reshuffling for Generally Smooth Non-Convex Federated Optimization
Authors: Yury Demidovich
Petr Ostroukhov
Grigory Malinovsky
Samuel Horváth
Martin Takáč
Peter Richtárik
Eduard Gorbunov
Venue: ICLR 2025 Poster (2025)
Keywords: Optimization
Federated Learning
Distributed Optimization
Local Training
Random Reshuffling
Generalized Smoothness
Primary area: optimization

Abstract: Non-convex Machine Learning problems typically do not adhere to the standard smoothness assumption. Based on empirical findings, Zhang et al. (2020b) proposed a more realistic generalized $(L_0,L_1)$-smoothness assumption, though it remains largely unexplored. Many existing algorithms designed for standard smooth problems need to be revised. However, in the context of Federated Learning, only a few works address this problem but rely on additional limiting assumptions. In this paper, we address this gap in the literature: we propose and analyze new methods with local steps, partial participation of clients, and Random Reshuffling without extra restrictive assumptions beyond generalized smoothness. The proposed methods are based on the proper interplay between clients' and server's stepsizes and gradient clipping. Furthermore, we perform the first analysis of these methods under the Polyak-Łojasiewicz condition. Our theory is consistent with the known results for standard smooth problems, and our experimental results support the theoretical insights.

Published as a conference paper at ICLR 2025
METHODS WITH LOCAL STEPS AND RANDOM RESHUFFLING FOR GENERALLY SMOOTH NON- CONVEX FEDERATED OPTIMIZATION
Yury Demidovich" KAUST
Petr Ostroukhov MBZUAL, MIPT
Grigory Malinovsky
Samuel Horváth MBZUAI
KAUST
Martin Takáč MBZUAI
Peter Richtárik
Eduard Gorbunov
KAUST
MBZUAI
ABSTRACT
Non-convex Machine Learning problems typically do not adhere to the standard smoothness assumption. Based on empirical findings, /Zhang et al. (2020b) pro- posed a more realistic generalized (Lo, (1)-smoothnes assumption, though it re- mains largely unexplored. Many existing algorithms designed for standard smooth problems need to be revised. However, in the context of Federated Learning, only a few works address this problem but rely on additional limiting assumptions. this paper, address this gap in the literature: we propose and analyze new meth- ods with local steps, partial participation of clients, and Random Reshuffling with- out extra restrictive assumptions beyond generalized smoothness. The proposed methods are based on the proper interplay between clients' and server's 's stepsizes and gradient clipping. Furthermore, we perform the first analysis of these methods under the Polyak-Lojasient results for standard smooth problems, and our experimental results support the theoretical insights.
condition. Our theory is consistent with the known
INTRODUCTION
Distributed optimization problems and distributed algorithms have gained a lot of attention recent years in the Machine Learning (ML) community. In particular, modern problems often lead to the training of deep neural networks with billions of parameters on large datasets (Brown et al., 2020 Kolesnikov al., 2019). To make the training time feasible (Li) 2020), is natural to parallelizz Telize computations (c.g., stochastic gradients computations), i.c., apply distributed training algorithms (Goyal al. 2017: You et al., 2019 Le Scao al., (003). Another motivation for the usage of distributed methods is dictated by the fact that data can be naturally distributed across multiple devices/clients and be private, which typical scenario in Federated Learning (FL) (Koneený)
et al. 2016 McMahan et al. 2016, Kairouz et al. 2019).
Typically, such problems are not I-smooth as indicated by Defazio & Bottou (019) that motivated the optimization researchers to study so-called generalized smoothness assumptions. In particular, Zhang et al. (020b) propose (Tog I.,) -s)osoootnssss assumption, which allows the norm of the Hes- sian to grow linearly with the norm of the gradient, and empirically validate it for several problems involving the training of neural networks. In addition, Ahnn et al. (2023); Crawshaw et al. (2024b); Wang al. (2024) demonstrate that linear transformers with few layers satisfy this assumption, highlighting the practical importance of (Lo, L1 smoothhnsss Moreover, the theoretical conver- gence of different methods studied under (Lo, L, )smoothhnsss in the literature (Zhang et al. 2020b a Koloskova et al. 2023a Chen et al., 2023 Li et al.) 2024a] b) Crawshaw et al.) 20246) Noticeably, most of these methods utilize gradient clipping (Pascanu et al. 2013).
However, in the context of DistributedFFederaeed Learning, the theoretical convergence of meth- ods is weakly explored under (Lo, L1) smoothness.. In particular, only couple of papers analyze
Equul contribution. Contacts: yery
demi dovi ch@kaust..... edu.

---

Published as a conference paper at ICLR 2025
methods with local steps and Random Reshuffting two highly important techniques in FL un- der (Lo. L1 -smoothness but only with additional restrictive assumptions such as data homogeneity (Liu et al. 2022), bounded variance (Wang et al. 2024) cosine relatedness (Qian et al. 2021 Also, to the best of our knowledge, there is only a single result for the methods with partial partic- ipation of clients under (To, [1] }-smoothness with local steps but without data shuffling Crawshaw et al. (2024a). This leads us to the question: is it possible to design methods with local steps, Ran- dom Reshuffling, and partial participation of clients with provable convergence guarantees under (Lu. L1 >-mmoothness without additional restrictive assumptions? In this paper, we give positive answer this question.
1.1 OUR CONTRIBUTIONS
New method with local steps. We propose a new method with local steps called Clip-LocalGDI (Algorithm M. This method can be seen as a version of LocalGD (Mangasarian 1995 McMahan
et al. 2016) with different clients and server stepsizes and (smoothed) gradient clipping (Pascanu et al. 2013) on a server side. We also prove the convergence of Clip-LocalGIIJ for distributed non-convex (Lo, Lsmoohh problems without additional assumptions such as data homogeneity used in the previous works (Liu et al. 2022).
New method with local steps and Random Reshuffling. The second method we propose utilizes local steps and Random Reshufiling and clipping once-in-a- epoch. For the new method, we derive rigorous convergence bounds for distributed non-convex (Lu, -smooohh problems without additional assumptions such as bounded variance (Wang et al.,
CLERR (Algorithm
2024) or cosine relatedness (Qian et al. 2021).
New method with local steps, Random Reshuffting, and partial participation. We extend RR-CLI (Malinovsky et al. 2023a). utilizing Random Reshuffling of clients (as an alternative clients' sampling) and clients' data each meta-epoch, and adjust it to the case of (Lo, Li)- smooth objectives through the usage of (smoothed) gradient clipping at the end of each meta- epoch. For the resulting method called Clipped RR-CLI (Algorithm we derive a convergence rate for distributed non-convex (To, In )ssmoth problems without additional restrictive assump- tions. To the best of our knowledge, this is the first result for an FL method with partial participa- tion of clients under (Lo, L1) -moothhesss assumption.
Results for the PE.-functions. For all three new methods, we derive new results under Polyak- Lojasiewiez condition (Polyak) 1963 Lojasiewicz (963) that, the best of our knowledge, are the first results for FL methods under (Lo, Li L))-moothhness and Polyak-Lojasiewiis The analysis is based on the careful consideration of two possible cases (the gradient is either "small" or "big") and induction proof of the boundedness of certain metrics.
condition.
Tightness of the results. The derived results are tight: in the special case of L-smooth functions, results recover the known ones for the non-clipped version of the algorithms.
Numerical experiments. Our numerical experiments illustrate the superiority of the proposed methods over the existing baselines.
1.2 PRELIMINARIES
In this paper, we consider a standard distributed optimization problem
M
} )
min FER
f(x)
def
1 M
fm
(1)
1==1
where [M] def (1, M) represents the set of all workers participating in the training, and each the loss computed on the data available
fm : Rdd R is non-convex function corresponding on client m for the current model parameterized by x E Rd. Throughout the paper, we consider two setups: either workers can compute the full gradient fm of their loss functions or they can compute only a stochastic gradient at each step. In the latter case, we will assume that functions {Im m= M== have the finite-sum form
fm(x)= 1 Σ
fmg(z),
Vm E [M],
2

---

Published as a conference paper at ICLR 2025
where fmy corresponds to the local loss of the current model parameterized by x E R evaluated for the j-th data point on the dataset belonging to the m-th client.
1.3 RELATED WORK
Local training. Local Training (L.T), where clients perform multiple optimization steps on their local data before engaging in the resource-intensive process of parameter synchronization, stands out of the most effective and practical techniques for training FL models. LT was proposed by Mangasarian ( (995); : Povey et al. (2014): Moritz et al. (2015) and later promoted by McMahan al. (2016). Early theoretical analyses of LT methods relied on restrictive data homogeneity as- sumptions, which are often unrealistic in real-world federated learning (FL) settings (Stich) 2018]
Li al. Haddadpour & Mahdavi 2019). Later, Later,|Khaled |Khaled et al. (2019a b) removed limiting data homogeneity assumptions for LocalGD (Gradient Descent (GD) with LT). Then. WWoodoorhh et al.
(2020): Glasgow et al.] (2022) derived lower bounds for GD with LT and data sampling, showing that its communication complexity is no better than minibatch Stochastic Gradient Descent (SGD) in settings with heterogeneous data. Another line of works focused on the mitigating so-called client drift phenomenon, which naturally occurs in LocalGD applied to distributed problems with hetero-
geneous local functions (Karimireddy et al.
2020 Tran-Dinh et al. 2021 Gorbunov et al.
20216
Thapa al. 2022: Mishchenko et al. 2022
Malinovsky et al.] 2023b).
Random reshuffling.
Although standard Stochastic Gradient Descent (SGD) Robbins & Monro
1951 is well-understood from a theoretical perspective (Rakhlin et al. 2012, Bottou et al. 2018
Nguyen et al. 2018 Gower et al. 2019: Drori & Shamir, 2020; Khaled & Richtárik 2020: Demi-
dovich et al. 2024), most widely-used ML. frameworks rely on sampling without replacement, as it
works better in the training neural networks (Bottou) 2009 Recht & Ré. 2013 Bengio 2012: Sun
2020). It leverages the finite-sum structure by ensuring each function is used once per epoch. How- ever, this introduces bias: individual steps may not reflect full gradient descent steps on average. Thus, proving convergence requires more advanced techniques. Three popular variants of sampling without replacement are commonly used. Random Reshuffling (RR), where the training data is ran- domly reshuffled before the start of every epoch, is an extremely popular and well-studied approach. The aim of RR is to disrupt any potentially untoward default data sequencing that could hinder train- ing efficiency. RR works very well in practice. Shuffle Once (SO) is analogous to RR, however, the training data is permuted randomly only once prior to the training process. The empirical perfor- mance is similar to RR. Incremental Gradient (IG) is identical to SO with the difference that the initial permutation is deterministic. This approach is the simplest, however, ineffective. IG has been extensively studied over a long period (Luo) [991| Grippo| 19944] Li et al. 2022; Ying et al. 2019] Gürbüzbalaban et al. 2019 Nguyen et al. 2021)) ). A major challenge with IG lies in selecting par-
ticular permutation for cycling through the iterations, a task that Nedic & Bertsekas 2001 highlight as being quite difficult. (Bertsekas 2015) provides an example that underscores the vulnerability of IG to poor orderings, especially when contrasted with RR. Meaningful theoretical analyses of the SO method have only emerged recently (Safran & Shamir, 2020 Rajput et al.) 2020). RR has been shown to outperform both SGD and IG for objectives that are twice-smooth (Gürbüzbalaban et al.)
2015 Haochen & Sra, 2019). Jain et al. (2019) examine the convergence of RR for smooth objec-
lives. Safran & Shamir (2020) Rajput et al. (2020) provide lower bounds for RR. Mishchenkk et al.
2020 recently conducted thorough analysis of IG, SO and RR using innovative and simplified
proof techniques, resulting in better convergence rates. Recent advances on RR can be found in (Cha
ct al. 2023 Cai et al. 2023 Koloskova et al. 2023b).
Generalized smoothness. ist L > 0 such that (x)
Let us remind that the function f is said to be L-smooth if there ex-
V [[yy]l L | y/ for all x, y E Rd. For twice-differentiable functions. it is equivalent to V f(x) < L, for all E Rdd This assumption is very standard in the optimization field. Recently, based on extensive experiments. Zhang et al. (20205) introduced a generalization of this condition called (To, L1)-smoothnsss. Namely, twice-differene
function [>)]]) < Lo + L, [[V](x)], for all E Rd. Compared to
f is said to be (Lo, -smoohhhh if the standard smoothness, this condition is its strict relaxation, and it is applied to a broader range of functions, Zhang et al. (2020b) demonstrated empirically that generalized smoothness provides a more accurate representation of worl-world task objectives, especially in the context of training deep neural networks. During LSTM training, it was noted that the local Lipschitz constant To
3

---

Published as a conference paper at ICLR 2025
Algorithm Clip-LocalGDJ: Clipped Local Gradient Descent with Jumping
1: Input: Sycchoniiztoon/oommniictiioo times 0 = to < t < to < < sp-1, initial vector
zo E R2 number of epochs P 2 1, constants co, C1 0.
2: Initialize 26 Bo zu for all [M] def {1. ..... ..... M).
3: for p 0, o,l, P do
4: Choose the server stepsize Tpp coto [
5: Choose small inner stepsize ap O.
6:
for m = 1..... M do
7:
T St,,
8:
for t E [tp.... 1p+1 - 2) do
9:
2+41 x 0g V fm (2.7)
10: end for
11: end for
9y Op [pp
[t,,
M 2m 20 -11
13:
Pt,+1
Ttp 9ppp
14:
end for
the stationary point is thousands of times smaller than the global Lipschitz constant L. Un- der this condition, Zhang et al. (2020b) provided a theoretical justification for the gradient clipping technique (Pascanu al., 2013). which considered effective in mitigating the issue of exploding
gradients. Their results were improved by (Zhang et al. 2020a Koloskova et al., (023a). (Chen
al. 2023) establish various useful properties of generalized- izations of (Lo. Lss-sooohsness and optimal first-order algorithms for solving generalized-smooth non-convex problems. Li et al. (2024a b) extend the (Lo, L1 -smoothness condition, introduce a novel analysis technique that bounds gradients along the trajectory, analyze GD, SGD, Nesterov's 's accelerated gradient method and Adam. (Crawshaw et al.] (2024b) consider a coordinate -wise ver- sion of generalized smoothness. (Ahn et al.] 2023] Crawshaw et al.] 2024b) [aan al. (024)) demonstrate that linear transformers with few layers satisfy generalized smoothness empirically. There are few papers distributed algorithms that combine local steps reshuffling with gener- alized smoothness. Qian et al. (202T) examined clipped IG; Wang et al. (2024) investigated Adam with RR; (Liu et 2022) studied LocalGD, however, all of the papers contain additional restrictive assumptions. This is a significant gap in the literature and we close it in our paper. Finally, Craw- shaw et al.) (2024a) use local steps and partial participation for (Lo, L -mooth objectives, but they do not use reshuffling and add heterogeneity assumptions.
functions, propose general-
2
NEW METHODS
In this section, we introduce the new methods Clip-LocalGID (AIIDiAAAAAoiii (Algorithm CLERR (Algo- rithm and Clipped RR-CLI (Algorithm
Clip-LocalGDJ. As standard LocalGD, the first method (Clip-LocaIGDI, Algorithm [T) alternates between local GD steps on each worker and synchronization/aveeagii steps. However, there are two noticeable differences between Clip-LocaIGDJ and LocalGD. The first one is the usage of different clients' and server's 's stepsizes. In our method, clients' stepsizes are typically smaller than the server's ones, which allows to handle the client drift. Then, on the server, the pseudogradient 9p is computed, and the server performs Clip- step, which is a second important difference compared LocalGID. Since the server's stepsize is typically larger than the clients' stepsizes, the local steps can be seen as steps determining the update direction, and the server step can be seen as a larger "jump" in the averaged update direction.
CLERR. In CLERR (Algorithm) 2 each client does full epoch of RR before between synchro- nization steps (similarly to (Malinovsky et al., (023b)), and similarly to Clip- LocalGo,, (smoothed) clipping is applied only to the averaged pseudogradient 9i once in epoch. In contrast, naïve combination of clipping with RR uses clipping at each step, which can amplify the bias of RR and lead to poor performance (as we illustrate in our experiments).
4

---

Published as a conference paper at ICLR 2025
Algorithm 2 CLERR: Clipped once in an Epoch Random Reshuffling
1: Input: Starting point 20 IRd number of epochs T, constants co, 61 > 0.
2: for /.= .,..., 7 do
3: Choose global stepsize "t = co [[[(=)]
4: Choose small inner stepsize 04 > 0.
5: Sample permutation क. ( (1) (.))))))))).))
6:
for m = L..... M do
7:
24,0 2t
8:
for j = 0, N do
9:
21 j+1 m
at I (m.a(i)
10:
end for
11:
9i"h N,N (Iz- - -x(,))
12:
end for
M
13: 9t M m= Di"
14:
Ø(+1 Zt 9t.
15:
end for
Clipped RR-CLL Clipped RR-CLI (Algorithm is the first FL algorithm that combines clip- ping. local steps, local dataset reshuffling, server and client step sizes and regularized client partial participation (sampling of clients without replacement). It is based
RR-CLI proposed by Ma- linovsky et al.] (2023a) and leverages the core techniques proposed in FedAvg (McMahan et al. 2016). The key idea is similar to CLERR, but in addition to the reshuffling of clients' data, Clipped RR-CLI performs a reshuffling of the groups of clients as an alternative to the standard i.i.d. sam- pling of clients each communication round. At the end of each meta-epoch, the server performs smoothed Clip-GD-tyyp step similar to the one used in CLERR, which allows the method to make a larger step with an accumulated pseudogradient.
When the number of workers is large, partial participation is preferable. In this case, Clipped RR- CLI (Algorithm 3 is the best option as utilizes partial participation. Otherwise, if we have access to full gradients the workers, then Looo--oaaGDDAAlgrriiii [ is preferable. In case when the workers can compute only a stochastic gradient, then CLERR (Algorithm 2 recommended.
ASSUMPTIONS
In this section, we list assumptions adopted in the paper. Assumption 1. There exists S* Jis: Jins E IR such that f(x) 2 8*, fm(x) 2 Jin Smj(2) 2 Jmjj m [M] j forr all IRd.
The next assumption is strict relaxation of the standard smoothness.
Assumption 2 (Asymmetric (Lo, L1)-smoothness (Zhang et al. 2020b Chen et al. 2023)). The
functions f(x), {fm(2) (z) [ and {f (x) m=1j=11 are asymmetrically (Lo, L1 smooth:
M.N
[v vs(1) (Lo [/>))>> wll. Va,y Rd. (z)]))
(x) (v)l < (Lo + L, V fm
vll. Vm e [M]
( < (Lo + L V (z) yll. Vm [M],] E [N], R
Rd.
Empirical findings of Zhang et al. (020b) revealed that generalized smoothness characterizes real- world task objectives in more precise way, particularly when applied to the training of DNNs. Moreover, the above assumption is satisfied Distributionally Robust Optimization for some prob- lems (Tin et al. 2021).
The assumption below generalizes the smoothness condition even further.
Assumption (Symmetric (Lo, L1) smoothness (Chen et al. (023)). The functions f(x),
{f (x)) { and {fmy (z)] ( are symmetrically (Lo, L1) -mooth::
[Vf(=) vf(v)] < (Lo L1 sup ac [r.yy
[Vf(w))) vll. Vz,y R
5

---

Published as a conference paper at ICLR 2025
Algorithm 3 Clipped RR-CLI: Federated optimization with server and global steps, clipping, ran- dom shuffling and partial participation with shuffling
1: Input: cohort size C E {1, 2, ................................ M; number of rounds R M/C; initial iterate/model Zo E R number of meta-epochs T 2 constants co: C1 > 0.
2: for meta-epoch t = 0, 1,. ..... T 1 do
3: Choose global stepsize 8, = tu but V[(+]]]]
4: Choose small server stepsize π) > 0.
5: Choose small client stepsize " >
6: 2i
It.
7:
Reshuffishuffinn:: sample a permutation X = :.: of [R]]
8:
for communication rounds r = .,..., R do
9: Send model of to participating clients E S (server broadcasts of to clients E S²"))
10:
for all clients E S locally in parallel do (client initializes local training using the latest global model x:{)
11:
r.0 Fm.t 2t
Data-Random- Reshuffling: sample permutation Tm (I ग. my.... -N- N-11 of [N]]
Seti-Raaddm-RRshuffinng
13:
for all local training data points j 0,.....,
do
14:
m.t Fm, V. ti (z,,
(client m passes once its local data in order)
end for In,
16:
1 TNN
(x) -x =m,
(client computes local update direction gm.t)
17:
end for
18:
gi = c
Σ Im.t
(server aggregates local directions 9m., of the clients cohort S()
mES.""
19:
2. xt ne.t
(server updates the model in aggregated direction ge with server stepsize 17c)
20:
end for
9: = Zi=0 12-1 gi
22:
Et++ 2t Ocgi
(global step after all communication rounds during meta epoch))
end for
[V]m(x) - Vmm(u))l S (Lo Li sup
V (m))l vll, Vm [M], R
uE[z,)]
( & (To+ +1 Ln sup
IV [my (v) - vll. Vm e (M)J 2,, E Rd.
wE(a.))
A common generalization of strong convexity in the literature is the Polyak-Lojasiewicz condition. Assumption 4 (Polyak-tojasiewir condition (Polyak 1963 Lojasiewicz. 1963)). Suppose As-
sumption / holds for the function f. There exists μl 0, such that [[V[())] 2 2p (f()) f*).
4 THEORETICAL CONVERGENCE RATES
In this section, we describe our convergence results. Let us first introduce the notation. Put A der M f* 37 Em=1 f A del
N -1 fmj. Define &n def (*p) ft. Let & be f* 1// EM & Zj=0
constant such that 0 < Ç
S
4. Fix accuracy & > 0. Let 2 1 be the number of epochs. For all
0 < < 1, denote
áp = Lo L, f(:,,), Il, ap Lo + L1 max I fm (I
1 to H.
We start by formulating the convergence result for Clip-LocaIGDJ (Algorithm in non-convex asymmetric generalized-smooohh case. More details can found in Appendix B.
Theorem 1. Let Assumptions 7 and hold. Choose any P 2 1. Choose small local stepsizes ap server stepsizes 7In so that
Then, the iterates {& 1-11 of Algorithm
7p
4n,"
satisfy
(1+ 3(H 3(H118a3a)
min 1S min
[V v f 112
24g
80
0SPSP-1
Lo
L1
3(H 1) 1)
2āp

---

Published as a conference paper at ICLR 2025
Corollary
1. If
P [ IV S.
324
and
Op is small enough,
then
minospsr-1 min
Lo
L1
The rates we obtain in Corollary D are consistent with the previously established rates of LocalGD
and GD in the standard smooth case, i.c., when L1 = 0. Indeed, we recover the rate (Lddu) for
LocalGD) (Koloskova al. 2020 Notice, that if H 1. the Algorithm I reduces to vanilla GD, Khaled & Richtárik 2020). In the (Lu, 41). -mmoohh case, setting
and we recover its rate O
H 1, we recover the rate
Ladu
of clipped GD from (Zang et al. 2020b
Below we state the convergence result for Clip-LocalGDJ (Algorithm in non convex asymmetric generalized-smoote case under the PÉ-condition. For more details, see Appendix B.2
Theorem Let Assumptions I 2 hold. Let Assumption hold. Choose any integer P 648g Choose small local stepsizes Opp server stepsizes "(p so that
By Tip _āp 1. -.t P be integer
such that 0 S <
be a constant, S Ap. Put 8p p=0 of Algorithm satiisyy
648.
A >>>
def (6tp)= - f*. Then, the
uc
iterates { |
5p s (1- MC
P-B
ALo
60 +
4Lo
us
{ V
Corollary 2. Choose a S min
Ln
86gz LoAP
IfP
618. 4hg In 260 then 8p S c.
Ap:
In the standard smooth case, when L = 0, we guarantee the iteration complexity O Le In 260
which matches the LocalGD (Koloskova al., 2020) and GD (Khaled & Richtárik, 2020) rates.
The above results can be generalized to the symmetric (Lu, L))-moothh case, see Theorem 5 in
Appendix B.3 for details.
Let T 2 1 be the number of epochs. For all 0 t -1, 1, denote
â, = Lo + L [z++)] ar = Lo + L1 max
V fm (x:)ll. ā;= Lo + L1 max fmj (at))l
Further, outline the convergence result for CLERR (Algorithm in non-convex asymmetric generalized -moohh case. For more details, see Appendix C.1
Theorem 3. Let Assumptions 7 and hold. Choose any T 2 Choose small client stepsizes Oity global stepsizes "/t so that Te
S Jt S ah." Then, the iterates { of Algorithm 2 satisfy
[V{(()))
E
min
min
Lo
L1
8 3a?u; Sâ,
((N - 1)(2N 1) + 2(N + 1)) T
6afa a
d0
(N 1)A*. (2)
T
If T [V E min min { [[V((2)1)
Corollary
2506a
and
Oz
small
enough,
we
have
}
SE.
L1
In the standard smooth case, we recover the rate Loōu of RR (Mishchenko et al. 2020).
We relegate the convergence result for CLERR (Algorithm 2 in non-convex asymmetric
generalized-smooth case under the Pl-ccondiionn to Appendix C.2 In the standard smooth case
recover the rate O La In 26u of RR Mishchenko et al. 2020 μ
Further, we formulate the convergence result for Clipped RR-CLI (Algorithm 3 in non-convex asymmetric generalized-smoothh case. For more details, Appendix D.

---

Published as a conference paper at ICLR 2025
Theorem 4. Let Assumptions I and 2 hold for functions {fm I=1 and (fmj) Y m=1g=11 Choose
M.N
any T 2 1. Choose small local stepsizes "i, small server stepsizes Tr, global stepsizes O, that
< O2 S L. Then, the iterates 1 of Algorithm satisfy
B1
48,
min { min
[V+((=)
0S1ST
Lo
L
26,07 10;
T (nfar ns RRRa + N² + n1 Rai)
1
50
T
20, +
aj
Ii/ + NNNaa + n Ra.s))
+
40²
Corollary 4.
If
T
725p
and
Yt.
are
small
enough,
then
min
T-1
min
[ La
[V
L1
}
S.
Finally, we provide the convergence result for Clipped RR-CLI (Algorithm 3 in non-convex asym- metric generalized-smoothh case under the PÊ-condition in Appendix D.2
5 EXPERIMENTS
We split our experimental results into 3 parts. In Section 5.1 we provide results for the Algorithm P with random reshuffting and jumping in the end of each epoch. In Section [5.2] consider Algo- rithm [ with local steps and jumping in the end of every communication round. In Section 5.3 we consider Algorithm B. which has local steps, uses random reshuffling of clients and client data and performs jumping in the end of every epoch. Moreover, in Section we provide additional technical details on the experiments. Finally, in Section G we provide additional experiments, that did not fit in the main text. In Section G.T we investigate the influence of inner step size on the convergence of Algorithm 2 and Section G.2 we provide additional logistic regression experiments.
All the mentioned methods have parameterized stepsize
To If we denote
1
B
200
we can estimate "/t as stepsize multiplied by clipping coefficient: min (1, T
S
S
A 1 We use this connection the process of tuning constants co and e₁- min {1, |or f.
In our experiments, we consider the synthetic problem, sum of shifted fourth-order functions:
N
f(x)
Σ - x.ll xs E [-10, 10 N
4)
The main reason consider this problem is that it is (Top [ -smooth, but not L-smooth Zhang ct al. (202b)). Additionally, in Section 5.1.1 we consider the problem of image classification of ResNet-20 He al. (2016) on CIFAR- 10 dataset KKrizhevsky al. (2009). All the methods and baselines were tuned with grid-search over logarithmic grid.
5.1 METHODS WITH RANDOM RESHUFFLING
We conduct this experiment on problem 4). where d 1, N 1000. We consider the Shuffle Once methods, which shuffle data once at the beginning of training. As baselines, we consider the following methods: regular SO method, which just SGD with shuffling at the start of training, Nastya from Malinovsky et al. (2022) with one worker, Clipped SO (CSO), which clips stochastic gradients at every step of the method. The results are presented in Figure [ As one can see from Figure [1 methods with clipping significantly outperform the rest. This empirical result justifies the theoretical fact of the importance of clipping for optimization of (Lo, L1) -mooth objectives. Additionally,
that among methods with clipping, CLERR shows better results than CSO. From this, we can conclude that clipping the final (pseudo)gradient approximation at the end of an epoch gives better results than clipping on every step.
8

---

Published as a conference paper at ICLR 2025
10
NASTYA
CRO
10
CLEAR
10
107
130
00'
Epcchs
Figure 1: Function residual for 10-7
Loss
||0fix;]1
Accuracy
2.0
20
0.8
0.6
Test
1.5
10
0.4
CSO
1.0
NASTYA
0.2
CLERR
0.5
CLERR-h
0
50
100
150
200
50
100
150
200
50
100
150
200
Epochs
Figure 2: Loss, gradient norm and accuracy on test dataset for ResNet-18 on Cifar- 10, a; = 0.01
5.1.1 RESNET-18 ON CIFAR-10
In Zhang et al. (2020b) the authors obtained results positive correlation between gradient norm and local smoothness for the problem training neural networks language modeling and image classification tasks. To check, whether findings in synthetic experiments also take place for neural networks, we decided to test Algorithm 2 in the same image classification problem: train ResNet- 18 He al. (2016) on the CIFAR-10 dataset Krizhevsky et al. (2009). Additionally, consider heuristical modification of Algorithm| 2 which we call CLERR-h. The details of we provide next. The overall results of the experiment test data shown in Figure Additionally, we provide results on train data along with technical details in Appendix ??.
From this Figure (CLERR) does not have any impact on this problem. On the other hand, CSO shows the best results. Since in this problem regular clipping already works very well, we decided to heuristically modify our Algorithm 2 take the best clipping level and inner stepsize of CSO and use it on inner iterations, and tune co with C₁ for outer stepsize. We call this method CLERR-h and also provide its results in Figure 2 CLERR-h chooses rather big outer stepsize, while the outer clipping level is very tiny. For big clipping levels method diverges. These results show that jumping does not give performance gains when the method clips every inner step.
see, that both jumping (Nastya and CLERR) and clipping outer step
5.2 METHOSS WITH LOCAL STEPS
In this experiment, we aim to show the effect of the jumping technique on federated learning meth- ods. We consider problem (4) with 100, client more distinct between each other, we sort the whole dataset at the beginning of the experiment by ||æ||||- Here we consider a high-dimensional setup so that the starting point has less impact on the algorithm performance. Indeed, in me-dimmesional case, if we started from To & [-10, 10), the anti-gradient of every f1(x) = (x xx,)* would point towards minimum. Therefore, we could find such stepsize, that method converges in one iteration. On the other hand, if we consider a high- dimensional setup, then regardless of the starting point, the gradient of each fi(x) has different direction. In this experiment compare Algorithm [ (C-LGDJ) with Communication Efficient Local Gradient Clipping (CELGC) (Liu et al. 2022) and Clipping- Enabled- -Feddvg (CE-FedAvg)
1000. To make the distributions of data on each
Zhang al. (022). The results shown in Figure

---

Published as a conference paper at ICLR 2025
10"
C-ODU
10
10"
CE-Fiskogg
CE-PesANg, E-1
C-UGZU 1-10
10'
EXLSOM 1-10
10
CELOO, T:10
CELOC, 1-10
CF-FWAAN T-10
EFF
10
10
10
10"
10
10
(a) (1.....1) Figure 3: Function residual for starting from different zo for different number of local steps on the client device T.
(b) (10,..., 10)
Overall, we arrive two conclusions. Firstly, local steps do not have any positive effect on this problem. The plots with the increased number of client steps T only strengthen this point. Secondly, since local steps pointless, the method works better if the server gets better gradient approxi- mation, which is true if the method clips gradients on the server, not on the client. This is exactly the reason why C-LGDJ has better performance in Figure 3b
5.3 METHODS WITH LOCAL STEPS, RANDOM RESHUFFLING AND PARTIAL PARTICIPATION
In the final experiment, we consider methods with partial participation. The goal of this experiment to investigate how clipping, local steps, partial participation and random reshuflling of both clients and client data works together. We compare Algorithm 3 with CE-FedAvg Zhang et al. (022) with partial participation (CE-FedAvg-PP) on prob-
10
CE
10'
10'
10
lem with d 100, N 1000. Again, to make the distributions of data on each client more distinct between
each other, we sort the whole dataset the heginning of the experiment by || The results are presented in Figure
16"
50
75
100
125
175
200
epoche (commun
Since CRR-CR CLI uses random reshuffling of the data instead of sampling with replacement, and clips only in the end of meta-epoch, it has better gradient approximation on the starting from zo (I,.., 1) with batch global step, which results in better performance, than CE- size 16. FedAvg-PP.
Figure 4: Function residual for (4)
DISCUSSION
In this paper, we consider a more general smoothness assumption and propose three new distributed methods for Federated Learning with local steps under this setting. Specifically, we analyze local gradient descent (GD) steps, local steps with Random Reshuffling, and a method that combines local steps with Random Reshuffling and Partial Participation. We provide a tight analysis for general non- convex and Dolyak-Lojasiewicz settings, recovering previous results as special cases. Furthermore, we present numerical results to support our thcoretical findings.
For future work, it would be valuable to explore local methods with communication compression under the generalized smoothness assumption, as well as methods incorporating incomplete local epochs. Additionally, investigating local methods with client drift reduction mechanisms to address the effects of heterogeneity, along with potentially parameter- free approaches. represents a promis- ing direction.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The authors thank M. Crawshaw for drawing our attention to the related literature, Éric Moulines for spotting mistake in the proof (which affected the choice of the inner stepsizes, but the main results remained the same), and anonymous reviewers for valuable feedback.
The work of Yury Demidovich, Grigory Malinovsky and Peter Richtárik from King Abdullah University of Science and Technology (KAUST): i) KAUST Baseline Research Scheme, ii) Center Excellence for Generative AI, under award number 5940, iii) SDAIA-KAUST Center of Excellence in Artificial Intelligence and Data Science.
was supported by funding
The work of Petr Ostroukhov was supported by the Ministry Science and Higher Education the Russian Federation (Goszadaniye), project No. FSMG-2024-0011.
REFERENCES
Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Linear at- tention is (maybe) all you need (to understand transformer optimization). ArXiv, abs/2310.01088 2023. URL btttp:::/// //api. semant icscholar htt.:///......o/oouupuaa22223333
Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Proceedings of the 32nd Inter- national Conference Neural Information Processing Systems, NIPS' 18, pp. 5977-5987, Red Hook, NY, USA, 2018. Curran Associates Inc.
Yoshua Bengio. Practical recommendations for gradient-based training of deep architectures. In Neural Networks, 2012. URL https: semanticscholeeeeee ottp::///ppp.eeannnccccccooooooo oeeaaptti.cccoolaaa.oooooooooooo
org/CorpusID:
10808461
Dimitri P. Bertsekas. Incremental gradient, subgradient, and proximal methods for convex optimiza- tion: A survey, ArXiv, abs/1507.01030, 2015.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. 2009. wwt.aaa.rrrroooou......... 11: 68221333
URL httptttsss/ppp...eeaaa.eeeeeeeee
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-11, 2018.
doi: 10.11137/16M00001773. URL https://
doi foi.org/10, 1137/1 0117/6611880 080173
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle. M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., neurips ccppper files/paper/2020/ pdf
2020. URL #tle///5ccccisrr0000444bsaasae23
Xufeng Cai, Cheuk Yin Lin, and Jelena Diakonikolas. Empirical risk minimization with shuffled SGD: A primal-dual perspective and improved bounds. CoRR, abs/2306. 12498, 2023, doi: 10. 48550/ARXIV.23066 12498. https: /ooi org/10.../...ooo 48550 arxiv. 12498
Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling sgd: random per- mutations and beyond. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1-2::27. 2011. Software available at http:// /tww://wwww.... cs ie. ntu. edu. http:ttt/w///////aaa//ee
11

---

Published as a conference paper at ICLR 2025
Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large-cohort training for federated learning. In M. Ranzato, A. Beygelzimer, Y. Dauphin. P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural In- formation Processing Systems, volume 34, pp. 20461-20475. Curran Associates, Inc., 2021. URL https::/
neurips httpi//sscccpppeefeesss/e//eee ffless/paper//221// htl1://baec1117/1100000111111883
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learn- ing. Trans, Mach. Learn. Res., 2022, 2020. URL wttpt:t:t///ttt /aps:///ap... semanticscholar org
CorpusID:22500
Ziyi Chen, Yi Zhou, Yingbin Liang, and Zhaosong Lu. Generalized-smoothh nonconvex optimiza- tion is as efficient as smooth nonconvex optimization. In Proceedings of the 40th International Conference on Machine Learning, ICML'23, JMLR.org, 2023.
Michael Crawshaw, Yajie Bao, and Mingrui Liu. Federated learning with client subsampling, data heterogeneity, and unbounded smoothness: A new algorithm and lower bounds. Advances in Neural Information Processing Systems, 36, 2024a.
Michael Crawshaw, Mingrui Liu, Francesco Orabona, Wei Zhang, and Zhenxun Zhuang. Robust- ness to unbounded smoothness of generalized signsgd. Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024b. Curran Associates Inc. ISBN 978171387 1088.
Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Yury Demidovich, Grigory Malinovsky, Igor Sokolov, and Peter Richtárik. A guide through the 700 of biased sgd. Proceedings of the 37th International Conference on Neural Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024. Curran Associates Inc.
Yoel Drori and Ohad Shamir. The complexity of finding stationary points with stochastic gradient descent. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Con- ference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 2668-2667. PMLR, 13-18 Jul 2020. / URL https: http:///oocceeeeeeeeeeeeee
mlr press/v119/
dror 120a. html
Margalit R. Glasgow, Honglin Yuan, and Tengyu Ma. Sharp bounds for federated averaging (local sgd) and continuous perspective. In Gustau Camps-Valks Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings The 25th International Conference on Artificial Intelligence and Statisties, volume 151 of Proceedings of Machine Learning Research, pp. 9050-9090, PMLR, 28-30 Mar html
2022. URL htttttts://prceeeeeee
mlr
Eduard Gorbunov, Konstantin P. Burlachenko, Zhize Li, and Peter Richtarik. Marina: Faster non- convex distributed learning with compression. In Marina Meila and Tong Zhang (eds.), Proceed- ings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 3788-3798 PMLR, 18-24 Jul 2021a.
Eduard Gorbunov, Filip Hanzely. and Peter Richtarik. Local sgd: Unified theory and new ef- ficient methods. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 3556-3564. PMLR, 13-15 Apr 2021b. URL. https:
httpa////11///ooooooolaaa.. / //proceedings.o .lr. www.ppessssse... hvtss//vlvv///// gwrpunov2l..aaammmmm html
Eduard Gorbunov, Nazarii Tupitsa, Sayantan Choudhury, Alen Aliev, Peter Richtárik, Samuel Horváth, and Martin Takáč. Methods for convex I-mmooth optimization: Clipping, ac- celeration, and adaptivity, 2024. HtRL:ttp:: http://awwww..o//ab/////
Robert Mansel Gower, Nicolas Loizou, Xun Qian, Alibek Sailanbayev, Egor Shulgin, and Peter Richtárik. SGD: General analysis and improved rates. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5200 52090 PMLR, 09-15 Jun 2019. URL wwt.::tpps..m. pettps:/prroceed: ngs. ngs ml www.pp/sss/ggggappppppp htt.://m...rrre/////////11111/11
html
12

---

Published as a conference paper at ICLR 2025
Priya Goyal, Piotr Dollár, Ross B. Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training ima- genet in hour. ArXiv, abs/1706.022677 2017.
Luigi Grippo. class of unconstrained minimization methods for neural network training. Opti- mization Methods & Software, 1555-50..11 1994.
M. Gürbüüzalaaaa, A. Ozdaglar, and P. A. Parrilo. Convergence rate of incremental gradient and incremental newton methods. SIAM Journal on Optimization, 29(4):2542-22 2565, 2019. doi: 10. 1137/17MI 147846. URL httLLttp:::/ae ott/
Mert Gürbüzzalaban, Asuman Ozdaglar, and Pablo A. Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 186:49 84, 2015.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods in feder- ated learning. ArXiv, abs/1910.14422, 2019.
Jeff Haochen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In Kama- lika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Con- ference on Machine Learning, volume 97 of Proceedings of Machine Learming Research, pp. URL htttps://proceellngs wat.ssmmr..ee www.ssssss.r..........
2624 2633. PMLR, 09-15 Jun 2019.
haochen19a html
Andrew Straiton Hard, Kanishka Rao, Rajiv Mathews, Françoise Beaufays, Sean Augenstein, Hu- bert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard pre- diction. ArXiv, abs/1811 103604, 2018. URL https:
/aass:/appl /api. www.settiitinool.ee..... org/
Corpus 532076681
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Prateek Jain, Dheeraj M. Nagaraj, and Praneeth Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. ArXiv, abs/1903.01163. 2019.
Jikai Jin, Bohang Zhang, Haiyang Wang, and Liwei Wang. Non-convex distributionally robust optimization: Non-asymptotic analysis. Advances in Neural Information Processing Systems, 34: 2771-2782 2021.
Peter Kairouz, H. B. McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary B. Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim Y. El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Kho- dak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Oluwasanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, R. Pagh, Mari- ana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Xiaodong 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. Found. Trends Mach. Learn., 14:1-210, 2019.
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 Ja- vidi, Gauri Joshi, Mikhail Khodak, Jakub Konecný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock. Ayfer Özgür, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranceth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Found. Trends
13

---

Published as a conference paper at ICLR 2025
Mach. Learn., 14(1-))11-100, June 2021. ISSN 1935-8237. doi: 10.1561/22200000033, URL
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learn- ing. In Hal Daumé III and Aarti Singh (eds.). Proceedings of the 37th International Confer- ence on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp- 5132-5143. PMLR, 13-18 18 Jul 2020. URL httth:::/pppooeeee karimireddy 20mmmm1mm
ngs. ml press/v119/
Ahmed Khaled and Peter Richtárik. URL
Better theory for sgd in the nonconvex world. ArXiv,
abs/2002.03329, 2020.
211069380
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik, First analysis of local gd on hetero- geneous data. ArXiv, htbs/1999.0471555 2019a.
Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local sgd on identi- cal and heterogeneous data. In International Conference Artificial Intelligence and Statistics, 2019b.
Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In European Con- ference on Computer Vision, 2019.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian U. Stich. unified theory of decentralized sgd with changing topology and local updates. In Proceedings of the 37th International Conference on Machine Learning, ICML'20. JMLR.org 2020.
Anastasia Koloskova, Hadrien Hendrikx, and Sebastian U. Stich. Revisiting gradient clipping: stochastic bias and tight convergence guarantees. In Proceedings of the 40th International Con- ference Machine Learning, JCML'23. JMLR.org. 2023a.
Anastasia Koloskova, Ryan McKenna, Zachary B. Charles, Keith Rush, and Brendan McMahan. Convergence of gradient descent with linearly correlated noise and applications differentially private learning. ArXiv, abs/2302.01465 2023b. URL https://aaaaaa www.ssicccmccsoo...............e
org/CorpusID: :D:
Jakub Konecny. H. B. McMahan, Felix X. Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. ArXiv, abs/1610.05592, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilié, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. Bloom: A 176b- parameter open-access multilingual language model. 2023.
Chuan Li. Demystifying gpt-3 language model: A technical overview, 2020. URL https://
lambda abss www.com///a. /b/ oo/ wyw.sstiiiinnngggaa..
Haochuan Li, Jian Qian, Yi Tian, Alexander Rakhlin, and Ali Jadbabaie. Convex and non-convex optimization under generalized smoothness. NIPS '23, Red Hook, NY, USA, 2024a. Curran Associates Inc.
Haochuan Li, Alexander Rakhlin, and Ali Jadbabaie. Convergence of adam under relaxed assump- tions. In Proceedings of the 37th International Conference on Newral Information Processing Systems, NIPS '23, Red Hook, NY, USA, 2024b. Curran Associates Inc.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg non-iid data. ArXiv,
2019.
14

---

Published as a conference paper at ICLR 2025
Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Jason D Lee. Incremental methods for weakly convex optimization, 2022. /
.16687
Mingrui Liu, Zhenxun Zhuang, Yunwen Lei, and Chunyang Liao. A communication-effitti dis- tributed gradient clipping algorithm for training deep neural networks. Advances in Neural Infor- mation Processing Systems, 35:26204-26211 2022.
Stanislaw Lojasiewicz. A topological property real analytic subsets. Coll. du CNRS, Les équations aux dérivées partiellex, 117(87-89):2, 1963.
Zhi- Zhi-Quan Tom Luo. On the convergence of the Ims algorithm with adaptive learning rate for linear 1991.
feedforward networks. Neural Computation,
Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sam- pling without replacement provably help in federated optimization. Proceedings of the 4th Inter- national Workshop on Distributed Machine Learning. 2022.
Grigory Malinovsky, Samuel Horv'ath ath, Konstantin Burlachenko, and Peter Richt arik. Federated learning with regularized client participation. ArXiv, abs/2302.03662, 2023a. URL https:
Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sam- pling without replacement provably help in federated optimization. In Proceedings of the 4th International Workshop on Distributed Machine Learning, DistributedMI. '23, pp. 85-104, New York, NY, USA, 2023b. Association for Computing Machinery. ISBN 9798400704475. 10. 11555//3363044333331530
doi: http:: wwg/10. 10e......1333.11 3630187 httppp///ii..rr/11111111////////
LO Mangasarian. Parallel gradient distribution in unconstrained optimization. SIAM Journal on Control and Optimization, 1995.
H. B. McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera Arcas. Communication-effiienn learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, 2016.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 17309-17320. Cur- ran Associates, Inc., 2020. URL
filaaperr_rll____eeeeeeeepeeeess files/
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtarik. ProxSkip: Yes! Local gradient steps provably lead to communication acceleration! Finally! In Ka- malika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 15750-15769, PMLR, 17-23 Jul 2022. URL https://proceeding mlr www.s:pppes//ooommm vttpvvl222////1 mi swwhenko22b.b..omm html
Philipp Moritz, Robert Nishihara, Ion Stoica, and Michael I. Jordan. Sparknet: Training deep net- works spark. CoRR, 055/1511.0605. 2015.
Angelia Nedic and Dimitri P. Bertsekas. Incremental subgradient methods for nondifferen-
tiable optimization. SIAM Journal on Optimization, 12(1):109-138, 2001. doi: 10.1137/ $10526234993611111 wtt.://ps//oooooor///////////223
Lam M. Nguyen, Quoc Tran-Dinh, Dzung T. Phan, Phuong Ha Nguyen, and Marten Van Dijk. A unified convergence analysis for shuffling gradient methods. J. Mach. Learn. Res., 22(1), jan 2021. ISSN 1532-4435.
Phuong Ha Nguyen, Lam M. Nguyen, and Marten van Dijk. Tight dimension independent lower bound on the expected convergence rate for diminishing step sizes in sgd. In Neural Information Processing Systems, 2018. URL https: //api. swwanticscholee........ http:s//aa.....mmicceccoo.o.... wtg//orrpssoDiD
52965883
15

---

Published as a conference paper at ICLR 2025
Andrei Panferov, Yury Demidovich, Ahmad Rammal, and Peter Richtárik. Correlated quantiza- tion for faster nonconvex distributed optimization, 2024. URL htttttsss///xx..oo abs/
2401100525
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference on International Conference on Machine Bearning-Volume 28, 2013.
Boris Polyak. Gradient methods for the minimisation of functionals. Ussr Computational Mathe- matics and Mathematical Physics, 3:864-878, 1963.
Daniel Povey, Xiaohui Zhang, and Sanjeev Khudanpur. Parallel training of deep neural networks with natural gradient and parameter averaging. In International Conference Learning Repre- sentations, 2014.
Jiang Qian, Yuren Wu, Bojin Zhuang, Shaojun Wang, and Jing Xiao. Understanding gradient clip- ping in incremental gradient methods. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceed- ings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Leurning Research, pp. 1504-1512, PMLR, 13-15 Apr 2021. URL https: httpsss/ppccceedinng. ml wtwpsp/rss///ppppptppppp hhtmmmmmm...mm
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th Inter- national Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 7964-7973. PMLR, 13-18 Jul 2020. URL https://proeediing mml.
press/v119rrajjutt220 html
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In Proceedings of the 29th International Coference on International Conference on Machine Learning, ICML' 12, pp. 1571-1578, Madison, WI, USA, 2012. Omnipress. ISBN 9781 450312251.
Benjamin Recht and Christopher Ré. Parallel stochastic gradient algorithms for large-scale matrix completion. Mathematical Programming Computation, 5:201 - 226, 2013. URL https:// api. semanti ieamantissch... ar org/ wwt.aaorooooooooooaaii.... CorpusID::11104111
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Math- ematical Statistics, 22(3):400- 407, 1951. doi: 10.1214/amm//117799990 URL https:
7/dei. 100 / aomms///////// /atp://177799995
Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Kon- stantin Burlachenko, and Peter Richtárik. Federated optimization algorithms with random reshuf- fling and gradient compression, 2022. URL
www.orggg///..oooo..o//.o..//.ee 6206. 07021
Itay Safran and Ohad Shamir. How good is sgd with random shufiling? Jacob Abernethy and Shivani Agarwal (eds.), Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3250 3284. PMLR, 09-12 Jul 2020. URL
https::/prooeeedings mwr www.s/pressssissse wttp:////aaaaa.aaaaaaaaaaaa attpppreess///2///aaaaaaaaaaaaa
I. Sokolov. Non-convex stochastic optimization with biased gradient estimators, 2022.
Sebastian U Stich. Local sgd converges fast and communicates little arXiv preprint
1rXiv:1805.09767 2018.
Ruoyu Sun. Optimization for deep learning: An overview. Journal of the Operations Research Suciety of China, 8:249 294, 2020. URL https://api..emmaattccccc..i
CorpusID:220511 ID:22051179
Chandra Thapa, Mahawaga Arachchige Pathum Chamikara, Seyit Camtepe, and Lichao Sun. Splitfed: When federated learning meets split learning. In AAAI, pp. 8493. AAAI Press, 2022. ISBN 978-1-57735-876-3
16

---

Published as a conference paper at ICLR 2025
Quoc Tran-Dinh, Nhan H. Pham, D. Phan, and Lam M. Nguyen. Feddr randomized douglas- rachford splitting algorithms for nonconvex federated composite optimization. In Neural Information Processing Systems, 2021. URL https: http:/ppp..emmattcccccccoaa..aa.
CorpusTD:23537611
Bohan Wang, Yushun Zhang, Huishuai Zhang, Qi Meng, Ruoyu Sun, Zhi-Ming Ma, Yan Liu, Zhi- thi-Quan Luo, and Wei Chen. Provable adaptivity of adam under non-uniform smooth- ness. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '24, pp. 2960-2969, New York, NY, USA, 2024. Association for Com- puting Machinery. ISBN 9798400704901.
doi: 10. (0.1145/33355883377777 URL https:
//doi.org/10. T1..11...1113331 1145/3637528 36717718
Blake Woodworth, Kumar Kshitij Patel, and Nathan Srebro. Minibatch vs local sgd for hetero- geneous distributed learning. In Proceedings of the 34th International Conference Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020. Curran Associates Inc.
ISBN 9781713829546.
Kai Yi, Timur Kharisov, Igor Sokolov, and Peter Richtárik. Cohort squeeze: Beyond sin- gle communication round per cohort in cross-device federated learning, 2024. URL https:
// war.iv.org//bs//266...6
Bicheng Ying. Kun Yuan, Stefan Vlaski, and Ali H. Sayed. Stochastic learning under random reshuffling with constant step-sizes. IEEE Transactions Signal Processing, 67(2):474-489,
2019. doi: 10.1109//P.201822888
Yang You, Jing Li, Sashank J. Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsich. Large batch optimization for deep learning: Training bert in 76 minutes. arXiv: Learning, 2019.
Bohang Zhang, Jikai Jin, Cong Fang, and Liwei Wang. Improved analysis of clipping algorithms for non-convex optimization. Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, Red Hook, NY, USA, 2020a. Curran Associates Inc. ISBN 9781713829546.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020b. URL httpttt:///pepeeevieeee nnt/ worumorrrmiio htt.:etttoooommmddaddaa..... Forum??i-BBJgpppWWWW
Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. In International Conference on Machine Learning, ICMI, 2022, 2022.
17

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
Our contributions
Preliminaries
Related Work
2
New methods
Assumptions
Theoretical convergence rates
5
Experiments
5.1
Methods with random reshufiling
5.I.1
Re 18 on CIFAR-I 10
5.2
Methods with local steps
5.3
Methods with local steps, random reshufiling and partial participation
10
6
Discussion
10
Implications of generalized smoothness
19
Local gradient descent
20
B.1
Asymmetric generalized-smood smooth non-convex functions
20
B.2
Asymmetric generalized-smooth functions under Pf.-condition
24
Symmetric generalized-smootf non-convex functions
26
B.4
Symmetric generalized-smmooth functions under Pt-condition
32
Random reshufiling
34
Asymmetric generalized-smooth non-convex functions
34
Asymmetric generalized-smooth functions under Pt--condtionn
40
Symmetric generalized-smooth non-convex functions
Symmetric generalized-smooth functions under Pł-condition
49
D Partial participation
51
D.I Asymmetric mnneralized-smoolt non-convex functions
D.2 Asymmetric generalized-smoot functions under PE-condition
57
Extension to global stepsizes with pscudogradients
60
Additional experimental details for main part
60
F1 Methods with random reshuffling
61
18

---

Published as a conference paper at ICLR 2025
R8 on CIFAR-I 10
62
Methods with local steps
63
3
Methods with local steps, random reshufiling and partial participation
64
Additional experiments
65
G.1
How the inner step size affects convergence of the method
65
G.2
Logistic regression experiments
65
Extended Related Work
66
A
IMPLICATIONS OF GENERALIZED SMOOTHNESS
Lemma 1. Let f satisfy Assumption 2
Then, for any x, y E R2 we have
f()) S 1(x) + (VI(x), x) + Lo Li [()))
| - y112.
Moreover, if == inf f(x) > -c. then, for all x E ER, we obtain
[Vf(2)
2(Lo + V[()(( f(x)
Proof of Lemma The first statement of the lemma is proven in Zhang al., 2020b Appendix l). The second statement is proven in (Gorbunov et al. 2024): it follows from the first statement, [((a
if one substitutes y for x La+ZilV/(2)) f((x) and uses the fact that f* f(v)
L
Lemma 2. Let f satisfy Assumption
Then, for any x, E Rd we have
Lo Ln [())]
f(v) f(x) S (Vf(x), 2) +
exp(L1 v|li[= y/1?.
2
Moreover, if f := and f(x) > -cc then, for > 0, such that nexp 17 S for all x E Id we
obtain
n| [(x)2 2(Lo + VV(((II f(x)
Proof of Lemma 2 The first part of this lemma is one of the results of (Chen et al. 2023 Proposition 3.2). The second statement proven (Gorbunov et al. 2024). To deal with it, let us substitute y
in the first statement with x Lo+2. I V()):
f(x))
Lo L (=)
f s f(e) S f(z) + (Vf(z). xx
exp(Lillx y|D) || a/1
[=))
= f(x) Lo + L, [/(x)]
Lo fx))l
[(n]
17 [(x))1
2
cxp
Lo [V
+ f()))l)
n| v
$ f((x) Lo + L, V f(())
2(Lo + L, [())]] e)xp(1)
n/ 12
< f(z) 2(Lo - L1 (=))))
Rearranging the terms, we get the second statement of the lemma.
Lemma 3. Assumption holds
holds for the function if and only if. for any x, y E Rd
[Vf((z) vf(y)) < (Lo + L, [)) exp (L1 ||x - vll) || vll
Proof of Lemma
This lemma is of the results of (Chn al. 2023
Proposition 3.2)
19

---

Published as a conference paper at ICLR 2025
B LOCAL GRADIENT DESCENT
B. ASYMMETRIC GENERALIZED-SMOOTH NON-CONVEX FUNCTIONS
Theorem 1 [non-convex asymmetric generalized-smooth convergence analysis of Algorithm [ Let
Assumptions / and hold for functions f and (fm ) m=1- Choose any P 2 1. For all 0 p P-1, 1, denote
Og = Li ap
ap= = Lo L1 max [
1pt11 - to S H.
Put A f
M Em= fin Impose the following conditions on the local stepsizes Op and server
stepsizes "p-
0p
1 1 S PSPSP-1. 1,
0p min
2Hap cap
àp
4āp"
where 0 <<< 1, satisfy
VP. Let 60
def
f (20)
f Then, the iterates
{ ) pmo of Algorithm
P-1
3(H 3(H-1)"000)
5 min
[V LA
}}
11
26p
min 0SPSP-1
80
Lo
P
3(H 1)
A
20p
Put Up def
tp+1 1.
Lemma 4. Assume that f and each I' satisfy Assumptions)
7 and 2
Then have the following
bound:
M M m=1
Σ
|
2r,11² 5.8 (c, - 4p) a -
+1
Proof of Lemma
We have
10 21,1 11
Σ
ap V vm fm (25))
1=
1-1
:-1
Σ
ap V fm (2x)) - V.m (mx)))))
+
_
Σ
ap
v fm (fte))
1=
2(t 4p)
Σ (ap)² )2 (To + Tu V.m (mm
|| - n.c 11
j=t,
+2
Σ
0ip (m
1
20

---

Published as a conference paper at ICLR 2025
Averaging, get
3t, 11
2(t - tp)
(ap)² (Lo + Li (1t, I1) |39 2=,,1
M
M
m=
j=tp
+
2
Σ
Σ j=
P
fm (
M
2(1
(p)
M
1-1
(ap)
(ap) 2
8t, 11 |.
M
1=
M
+
2
Σ
Σ
Ap
V
mm (ftep)
M
m=1
1=1p
Recall that Op S 21(Lo to by max... pic..IlvA. fm
Then we have
M M
M
t-1
-r,1 11
t -
tp
aa -r,,11 11
2H2
m=1
m= m=1j=m j=tp
2 M
Σ
Σ
ap v f (Tr,))
(5)
M m=1
j=fp
Let us bound the last term:
2
2
Σ /=
ap V (it,)
fm (3, (t- t,,) 2a
M
4
Σ
(Lo + L1 (fm((),)))) (frr (De,)) fim)
M
x (t - tp)) ot
4(t tp) apap 2
Σ
(Sm (fr,) -fi)
M
m=1
= 4 - ty)² apaz [((;,)- fr (5- -
M m=
= 4 (t 12)² apaz (f(2t,) - f + A+).
21

---

Published as a conference paper at ICLR 2025
Further, summing 7 with respect to t, we obtain
1 M (=
Σ
Σ
2,, 11
2H²M Σ
Σ (t (t-bp) kp)
Σ || ,,,
1=1++1
1=1p
+
Σ
( - tp) apa (f( - f + +
t=1p1
M
1p
Σ
|, - 1,,
2H
m= 1= 1=
+4
(u (u-tz) apaz (f( - f + D4)
(1pp1
(U tp) 2 M
|a - $,,11
2H²M
m= j=tp
+ 4 (v 1 tp)² a (f((t f + A7).
Using the fact that v - 1p S H - 1 < H, we obtain that
1 M
x 81 111 88 - (tttt) apa (f(ee,) - ff - +
M
m=
t=
Proof of Theorem 1 Applying Lemma D we obtain that
3
2
11
f(i),_)) S f(6r,)) - 7x (ft,)) ,pp) + (Lo + L1 |V (I))
2
Additionally, from the fact that 2(a, b)- = ||a - b|l2 + ||ا| + +10012
3/ 11 1
(( S I((,,, - (p (ix,)) mpl + (To + L V (B,,)11
2
Le (-11V) gpl2 + [ )1 + |19
S f(tr,))
2
1211op112
+ +Lo + L V (1.,,)l))
2
1211.pp 12
$(((t,,)
72
V f (ā, |11
+
2e [VS(( - + (Lo + L. /I
2
2
2
Consider (+v+) - 12. We have
M
Tp
V (
7p 2
M Σ
V. mi
1
V fm (2))e)
V tp j=st
M
< Yp
Σ
(Lo + L1 V (Rt, 11)
2
|| & 11?
2 M (v- tp)
m=1
j=tp
M
7p
(To + I.
max m
V ( 11)
1
|, - 112
2( - t,p)
M
m=1j=tp
7n 2
1
M
e
Σ Σ
|0 šz,11 1|2
2(v - tp) M
1= j=lp
22

---

Published as a conference paper at ICLR 2025
Notice that
2 p
119pl
2
Σ
V fm (2)")
2
M tp)
mm +
S (U 7/
1
M
Σ
V sm (1)7T) - mm (it,,)
)2
M
j
7p
1
mm (5tey)
(v- - 1p))
M
j=lp+1
M
S (v - tp)
pp
TTg + Ii
max m
(mt,
2
Σ
5t, 1?
M
j=ty
2 V (itep) ||
+ 1p
M
Σ
Σ
|ل
11, +
+1
M(U- 1p)
1=1p
Therefore, we obtain
f (
S (((r),
7/ | ( M11
7p
p
2
|, -2,,12+ + ap7;"199p1
2M
tp)
j=tp
Yp 2 p
S {((r,)))
1e || |V M1
||a 112
2
2M (v - -(p)
j=tp
M
|ay - -r,, 112 + 2 | (i+,,)'
M(u (pp) m=1 j=(,
= =((Et)) + +arr? - Te)
|| VJ (12
2
(10377 2 +
M
1
Σ
Σ
||
Et 11
2
M( tp)
Recall that 7/p S 76. Then, using Lemma 4
we have
f (0)pz)) 5f (3i,) - 2e
V (0,,) l
4
222 + 7pag
M
+ (ppo7:1'
Σ
1a 2,,11 11
2 / M(U - tp) m=1j==fpp
S f (Br,)) -
Te
| (Rt,)11 ||
4
+ a007710 + 7paz
8(v - tx) aap (f((t,) - - + A²)
2
| (ix,) | 3(H - 1)933a3 (f(x),) - -f"
< (5x, 2o
2āp
Let us rewrite the inequality in the following way:
3(H 1)2 ( A2)
yp
Vf (2x,,) (22 < s ( - ff (8iptz)
(6)
2āp
23

---

Published as a conference paper at ICLR 2025
Since 7/p 2 ā, we get that
V 11t,
2
/| V[(55(1,)) (1,,)
5
40p
Therefore,
1p
<11
< (dx IlI
((
8h0
(V [V
1
La
La
L
min
[V
To
| IV
L1
8..1
L
Denote 6p def f (2,,)- - Then we have
fr.
[V [Vf( Lo
}
3(H - 2 (6p, + A*)
min
6p 8p41
p
L
2ā,
Let 0p S cap
where c cz vP. Applying the result of Mishchenko et al. (202
Lemma 6), we
ap
appear at
(1+ 3(H a
S
[V((s,,)
[V
20p
min OSPSP-
min
5n
Lo
L1
P
3(H - 1)2
A
2āp
Corollary 1. Fix e
O. Choose
V3(11 - 1) Let Op $ 2
00
Then, if
3P(H 17 1
P2 325g we have minospsp-1 min
[V/(())
|V I1l }} SE.
ce
Lo
L1
Proof of Corollary 7 Since - and 0pp S ca, V a, ap S 2
3)(1-1)2a52 due
to the choice of 2
326p (e
we obtain that
1)3
1 +
24p
v
eé0o
280
{E
80
S
<
P
P
P
16
and that
3(H
1)202
{
<
20p
16
[ La
[V SE.
Therefore, minospsp-1 min
L1
B.2 ASYMMETRIC GENERALIZED-SMOOD FUNCTIONS UNDER PE-CONDITION
Theorem Assymeeric generalized-smooee smooth convergence analysis of Algorithm in Pł.-case). Let M
Assumptions land 2 functioos f and {m m==
Let Assumption hoold. Choose S 1
Let 6o def (xr) f* Choose any integer P 646.L? For all 0 S S P 1, denote aa
āp Lo + f(l,V((;,,)... ap = Lo L1 max ( Put A f*
tp+1 - to H.
i
1 ΣM fün Impose the following conditions on the local stepsizes Og and server M
stepsizes 7op
àg ap
uCap -H
ap 5 min
2Hap cap
+
280
1 3P(H - -1203 (J(rt,) A
24

---

Published as a conference paper at ICLR 2025
$ ap
S 7p
OSpsP- -
4
where c 2 /P. Let P be an integer such that 0 S P
S
646.24 us
A > 0 be constant, a S V AP
Then, the iterates { 1 Y of Algorithm satisfy
8p - (1
ue
P-P
ALo
d0 +
4L0
u²
where 6p def f (Etp)) f*
Proof of Theorem
Let us follow the first steps of the proof of Theorem
| Consider (6)
V [I S f (āx,) f (fep4:) 3(H - 2,, (f A
T' 4
2āp
Since 7pp 2 -, and satisties Polyak-Lojasiewee Assumption
we obtain that
ps (f(ot,) f*) S (B1,) -f (2+p4:) 3(H - -1)aa (f(0z,) S + A1)
2āp
2āp
1. Let P be the number of steps p. that V (ft,))
2
For such p, have Lo + L
La
L V (#+,,) || = áp - 2h, Vf (is,) || Therefore, we get
nS (f(a),) - )*)
4ha V ( (ix,) f (1t 3(H1 1)2 2)20200 (f(2t,) +
2āp
Notice that the relation àp < 2L V (it,) || and Lemma
together imply
v (tx,,)
S f (it,) f
4L1
2āp
Hence, we have
NC 1677
S f (1t,)) f ( + 3(H 1) (f($t,) f
2āp
Subtracting f on both sides and introducing 8p ( ff" we obtain
3(H 1)? (f( 1 + A+)
us
8pt1 S 5p
+
1617
20p
As Op Σ V )( it follows that
mCa,
3(H 3(H-1)² (J (1 )-(++))) <
uc 32
24p
Therefore, we get
PC 8p+1 S 8p
32L
Suppose now that |VV (i.,) Hence,
L
La
For such p, we have Lo L1 Vf (f:,)] = âp S 2Ln.
MC (f(et,) f*)
(D:p.)) - 3(H - 1)2 (f(i.,,) S + +1')
< f (2t,)) f
4Lp
2āp
Subtracting f* on both sides and introducing 8, def (it,) - f*, we obtain
3(H - a (f(ee)) - f + A*)
where p 1 HC
8pt1 5 6pp
2āp
400
25

---

Published as a conference paper at ICLR 2025
Let Op adp and dg S V 31H )-
24 for some constant A 0. Then,
0pt1 I póp + Aa²
Unrolling the recursion, we derive
N-1
0p S
P- 80 Aa
2
32L 1=
1=0
Aa
1 p 1C
- pp-
80 +
1-p
1 - 32L3
Notice that 6p+1 S 6p + Aa?, which implics
8p S So (P-P) Aa P pC
32T
Since $ &VAp, Ap. we conclude that
28,- P MC
648gL2
0 5 8p
P
32L2"
MC
Therefore, for P> 646,12 MC
guarantee that P - P and
óp $ p
P- P80
Aaz
P p uC
1-p
32L?
Aa
S p
P-P 80
1-
Corollary 2 Fixe O. Choose S min
{v
Ap,
bu
L1
88us LP
Then, if 2
6480
nal
1Lg 1C
In
26n
we have öp S.
Proof of Corollary
2
Since 0 < p <
646
A > 0, a
An V
AP. a S In Li
due to the
LoAP:
choice of P G16,22
4hg In
26. E
we obtain that
11- nr
P-P
(P-P
80 S E 2
8n Se
2ho
4Lv
and that
4 ó0
< E
PC
AP 2
Therefore, 8p S
B.3 SYMMETRIC GENERALIZED NON-CONVEX FUNCTIONS
Theorem 5. Let Assumptions
and 2 hold for functions z and {Sm 1 Choose any P 2 1. For
all p S P 1, denote
åp = Lu + Vf Il,
ap = Lo + L1 max (m 1 tp S H.
Put A 1r
M fin Impose the following conditions on the local stepsizes Og and server
1 M
stepsizes ip:
à a
5
Op < min
2Ha cup V dp ap (To In Ae,
< < 80p
0SPSP-1,
áp
26

---

Published as a conference paper at ICLR 2025
where 0 <<> 8, c c H A
l.1.5
def
max { {Velnar (Sptt
21, Mldd((pp 21,d0(6,,t")))
v such
v
that / expv = 1, Let 60 _ f (20) - fr. Then, the iterates
fy=0 Algorithm
satisfy
(1+ 7(H- 20
min 0SpS 1-
5 min
[V(
up
80
8
To
11
P
7(H 1)202
àp and A+ 8
Let us remind that áp - Lo + Li
LII Up Lo + L1 maxm (mt( (ft,
1 Em=1 fm. Put Up =
def
1pt1-1.
M
Lemma 5. Assume that f and each fm satisfy Assumptions 7 aadd 3 bound:
Then we have the following
M
Σ
10
11,11 S 32 (v - txp)² ap (f(2t,) - f +
M
12
Proof of Lemma 5
We have
1-1
| - 2,,11 11
Σ
ap vm (2
=
jty
2 2
Σ Op (V vm
+2
Σ
0p
V fm (ptp))
1
$ 2(( tn))
Σ (ap)² (Lo + L mm (m (1)
1=6p
1-1
x xexp {41 |3 - 2 |1} ||- - &,,,1' +
2
Σ 1=1,
ap a fm (axp))
2 - tp) Σ
(ap)) 2 (Lo + L1 || V ( )|)
j=lp
j-1
} ba - 20p 112 + 2
t-1
x exp
L1
Σ
0pp
V (x
Σ j=tp
ap fmm((ee))
Let us show that if app
2 max. max,, sest,-1 (l (1)))) then fm("))) S fm for
tp S S 1pt1 1. Notice that locally we perform the iterations of the gradient descent. means, that
Lo + L1 / fm (x7")
fm [m(11711) S Fm((7 0xl V (a
exp (Tra, (VV a fm (z?)))?
2
< fm((")) apll V (- 21²
3g
(z I1 exp (ap (Lo + L1 Vfm
fm) ap 1 v3
| (.
2
Then fm( S fm (2777) fm (Ze,)) for tp s S tp+1 follows. Therefore, for such ap we
have that
M
fm Sin < fm(())) - fm < Σ
[m -s = -Mo, + *M*
m=1
27

---

Published as a conference paper at ICLR 2025
From Lemma Sammma2wwa we have
V (m?)))) v
(2;""))
vI V (2:"))
min
fm((?) Sin
To
L
2(Lo + La (mm
S M (6,, + -r)
For every 1p S 5 1p+1 1, for every we establish
2L (δt, + + M (ōtp + An) Agg.
V (x7')l S max
Let choose Op S Lot for some C 1.5 and show by induction that for such lo- cal processes maxm IIV Fm (x?"") S Ar,, for all tp I l S 1p+1 1. Indeed, for bp holds trivially. Suppose holds for all such that tp S E s for some l' Then, fm (I7++) S fm (xz) holds for any ap S Io including the chosen stepsize. Hence, fm (x7+1) S fm (2+,)) Therefore, max, [ (z7")) Ar,, for all t, S l S tpt1 1. Then, Li, I Loo maxm maxe, sese p--1 [mm((>))))
means that exp Li | ap Vm Averaging, we get
(zm]))))) S 11 1.5.
1z, 11
3(t - tp)
(ap)² (Lo + L1 (mm, |,, 2z,,1'
M
M
m=1
m=1 j=tp
2
+
Σ
ap
fm (ftz))
M
j=tz
3(t
tp)
(a,))
M
(ap)) ) ||557
2r, 11
M
m=jj=
+
2
M
Σ
t-
V fm (ftz))
M
m=1
Recall that a, <
Then we have
2Hop
M
1
24
21,1
1.5 (t
2
Σ
Stp
Σ
M
Σ
1
ap
V
Vf (6t,))
m=1j=1,
j=1p
1=
28

---

Published as a conference paper at ICLR 2025
Let us bound the last term, using Lemma
2 and the fact that 1/1
2 M
Σ xxp V イ
(
2
(mx (1- (p))² oz
M m=l
M
m=l
8
(Lo + L1
V (Be (fm (3t,) fm)
M
x (t tp)
2
Pp
8 (t tp) 2
M
ap
p
Σ m=1
(Sm (5t,)) (sm)
M
8( 1p)² anaz
[((x))
M
m=m
= 8 (t- tpp a (f(tt)) - f- + +*)
Further, summing
7 with respect to 1, we obtain
M
1 M
2,, 112
1.5
Σ Σ (t-tp) tp) Σ || 11,l1
2
2H²M
tmtp-1
t
j
+
Σ
8 - 1p) ana 2 (f(tr,)) - 8 + a+)
t=
1.5 - tpp)
M
1
Σ m=1
22 $,,11 11
2H²M
1jmty
+8 Σ
(u - 1pp)² apa 2 (f(it,) 5 + +4)
(=t+1)
1.5 (u tpp)
M
Σ>
m -8tp 1?
1
2H²M
m=1j=tp
+ 8 (n - 1,)) a (1(zz,) - 5 + 2r)
Using the fact that v tp 1<< H, we obtain that
M Σ
S2,11 11 3 (v - tp)) ag (f(bt,) - +*+)).
Proof of Theorem 5 Applying Lemma we obtain that
2 |1
[(ttp::) ) S J ( 7op / (..,,) (p) + (To + Ln | (ixx exp (To 11
2
Additionally, from the fact that 2(a, b) = -Iaa- b1| + ||a|| 12 + ||b|2
3/
(( S s(tt, - 7p /V/ / (ft,) .p) + (Lo + L || / (it,,) I|) exp (117p [1sp113
2
$ f(tt,)) - N0
(-1 f ( 12 + | )l + 1| 12)
2
3/ 1111
+ + + L1 VJ (.,, )1) exp (117 |1
30l1,p1 12
< <(()).) - 2p Vf 2| +
22
[f(Ett)) gp 1|2 + (Lo + LIVVS(() II) exp (L1%) |1
2
2
2
29

---

Published as a conference paper at ICLR 2025
Consider (( lpll?. We have
2
M
7ip Vf(e,,)
9pl1 = Yp
1
V. (
V fm (ag²)
2
2
M
tp j=tp
m=1
M
7p
1
(Lo + / Fm (8t, 11)
||
Stp 112 exp {2L1 a2 21,
M
(p)
m=1
j=tp
M
97p
1
(Lo + Li max I fm (fr, ||)
| Rz,l 11
8(1 1p))
M
97 ?
1 M
ba 22,11 11
8(v
tp)
M
12 jmmtp
Notice that
2 7p
11pppl
2
1p
1
M
fm (z))e)
2
M( bp)
m= j=ty +1
M
M
$ (v 12
fm (x.))
vmn (2t,))
+ [v - (p-1pp) bp)
Σ
vim (8t))
M
M
m= j=tp+1
m=1j=tpfh
M
v
5 (0 1p)
Loo + Li max
V fm (
Σ
Σ
|
tt,, 112 exp (2L) || 2,,111
M
m=1 j=tp
1p V (it,,))
97202
M
Σ
12
11 + + |V (1
4M
m=
m=1j=t j=tp
Further, recalling that 75 8ap
1 and ap <
C,C ap(LooLe
S
C Lo+LiA
we have
M
Lrip =
fm (xmh)
M(U - tp)
m= 1 j= +1
M
M
5 M (v- tp)
Σ
Σ
V (I,71 vm (2t,))
+ M (v - tx)
IpL1
Σ
Σ
v (2rp)
m=1 j=t++1
m=1 j=
M
5 7papL1
| - - + 2 I VJ (1:
M tpp)
m= 1 j=tpp1
M
1-1 Σ
< 8d.M (v tp)
ap
V fm (27²)
+7 V (#t,)]
m= jt
In 1.5
8'
30

---

Published as a conference paper at ICLR 2025
Therefore, since exp (L1% [19p11) 2, we obtain
Pypaz p
M
ap 2 1111pp1 12
f (Ztpe1) (Z(tp)) - 7p
|
f )1 + 8M (v tp)
|| 1xy Ltp 112 +
exp (L17p 11
2
2
mm= f
S f(( - 1e
| f
( )| + 9 9ppap
M
|| | - Rep 11
2
8M (v tp)
m= 1 1=
M
bo - =1,11 2| + +2 VS (12
+ 2M tpp
m=1a=tp
= = + (2
|V (
2
2n2
97pmi 8
M
up
2,, 11?
+ 2
M
m=1
Since 7p S 8a,
S 20
Then, using Lemma 5
we have
f (B(pt1) S f
Te Vf
(B,,))
272
M
Σ Eaaga $2,11
+
2
M - tp)
m=m m=1jjt j=
1 f (5c,)
Te V. (it,)) 2
94
2n 1p
97pa
32( - Papa (f(es,) -f
2
7(H 1)2 (f(e,,) +2))
< (it,)
Po
| (tx,,) 1|
4
àg
Let us rewrite the inequality in the following way:
7(H (HH-))a030) (s(iz,) [ - +
Yp 4
V (ix,)) S 5 (2x,)) - f (5tp41)
(8)
àp
Since 7/p 2 S, we get that
V (8r,)
2
5 <| (12
Pi
4
4dp
Therefore,
<l| ((e,)) I
[V,(),,)] [V
S
Eu
ff )2
V
( )12
8Lo C1l 87,
min
Lo.
Lo
L
Ln
Denote 5n def f (3t,) fr Then we have
< min
[IVI [VS(E,)) |1
7(H a (8p + A*)
5p +
8
Lu
L
áp
Let 0p
<
1
dz ap
where e 2 VP. Applying the result of Mishchenko et al. 2020
Lemma 6), we
cap
appear at
11+
7(H 1
P
15 min
|V
)12
[Vf(f, (I1
7(H 1)203a8
min 0SPSP-1
80 +
Lo
L1
P
àp
31

---

Published as a conference paper at ICLR 2025
Corollary 5, Fix > Choose c
= -14(H- 1) ae & V
20
Then, if PP
326n ÇE
have minospsp-1 min
| )1l }} Se.
Lo
Proof of Corollary
Since c = 14(H - 1 and ap S 1
ma
V
S Op
ap S
7P(H- 1y due
20,00
the choice of
326p ç3
obtain that
1 +
7(H 1) ag
P
0p
80 S
Véo
260
ÇE
P
P
16
and that
7(H - 1)2 a
5
A
v
0p
16
IV I
Therefore, mitlospp-11 min
Se.
La
L1
B.4 SYMMETRIC GENERALIZED FUNCTIONS UNDER PL-CONDITION
Theorem 6 (Symmetric semerahized-smmoth convergence analysis of Algorithm in Pł-ccse). Let M
Assumptions 1 and 3 functions and {f m=1 Let Assumption 4 hold. Choose 0 5 1
Let 80 def f (IO) f Choose any integer P 64%
For all S 1. denote
áp = Lo + [ "p= Lo + L max IV (ft, Il, 1 1 1p S H.
Put A f M Em fü Impose the following conditions on the local stepsizes Opp and server stepsizes ?p=
åg ap
HCā 2HA1 - 1)
ap S min
211ap cap
- -++
δoåp V 7P(H - 1) - A+
S
S 7p S
0 OSPSP-1,
åp
Sā
where e 2 VP. Let P be an integer such that P Then, the iterates { po-o of Algoorthmm satisfy
G4dg uc
>
constant, a S
/ Ap.
1
MC
P-P
80 + 4LoAa²
8p S
4Lo
HC
where 6p def f (Ztp) f*.
Proof of Theorem
6 Let follow the first steps of the proof of Theorem 5 Consider 8
T' V (.,, || < ( - I (stp.r) 7(H 11)aaaa3 (f f A 4
àp
Since 1p 2 S, and satisfies Solyak-E-ojsiewiiee Assumption
4 we obtain that
pg (f( -5)) 5 {ft,), (2ipts)
7(H a)2 (f +
20p
32

---

Published as a conference paper at ICLR 2025
1. Let P be the number of steps p. that V (at,)) )
||
2
Lo
For such p, have Lo +
L
L1 VS (Dt,)) || = a - 2 Vf [ ||. Therefore, we get
pa (Jrr,) - )*)
S $ (āt,) f (6tp11) 7(H - 1)9a - f
4I, V (
ap
Notice that the relation áp 1 2L, V (itz) || and Lemma
together imply
vf (ir,)]
Vff [1
S ( 5
4h1
2āp
Hence, we have
PC 16T.
7(H - 1)2a,a - +
S ʃ (it,,) - S (6t.
0p
Subtracting f on both sides and introducing 5p f (it,) f obtain
us
7(H - 1)2 (f(ie,) - 1 + ++)
8pt1 S 6p
+
16L7
åp
As 0p S (f) it follows that Therefore, we get
uça,
7(H (10))
<
K 320
4
PC
8p+1 S 8p
32L3
2. Suppose now that |[ (2,,,) s Hence,
La T.
For such p, we have Lu + L1 V (s:,)] = â, S 2Lo-
- (8t,) ( - 1 (1)) 7(H - 12 (f f +
nC (f(A))) <
4La
àp
Subtracting S' on both sides and introducing 5p def f - f we obtain
6pt1 S 6pp+ + 7(H - 1) (J(ze,) l + A*) where p def HS
4Lo
Let Op def adp and åp S
Aāp 7(1 112 (-+t))))))) for some constant 0. Then,
6p+1 S pop Aa².
Unrolling the recursion, we derive
2 8p S P- PP8 + Aa²
N -1
p²
32L
1=0
1=0
s P 1 p
2a2
1 - 0 μ²
1 p 32L?
Notice that 8pt1 S 6p + Aa², which implies
8p S do (p- P) Ao² 5 MC
321
Since a S V dg AP; we conclude that
0 S 5p S 25,- - p uS
= p 5
645
321
HC
33

---

Published as a conference paper at ICLR 2025
Therefore, for P> 646.4 #Ç
we can guarantee that P P and
6p S p
P000
Aa²
pp p²
1- p
3212
Aa
I p
p- 80 1 p
Corollary 6. Fix > O. Choose min
{v
An AP
LIV
8dnz LgAP
Then, if
615.L1
4hg Su
In 26g
we have 8p S E.
Proof of Corollary
Since 0 & P <
64 J.?
A > 0 S V
Tp. a S Li
bn
8ông
due to the
LeAP,
choice of 646n L
4La uc
260 we obtain that
P- p
1
PC
4c p- P) P) 80 S E
4L.
6n
S
2'
and that
4
d0
I
MC
AP
2
Therefore, 8p S 6.
C RANDOM RESHUFFLING
There are several approaches, that fall under the category of permutation methods, and one of the most popular is Random Reshuffling (RR). In each epoch t of the RR algorithm, we sample indices Te (1),,...., Ne (N) without replacement from the set (1.2..... .N. In other words, T1(1), ..., Te (N)
forms random permutation of {1, .., We then perform N steps in the following manner:
EJ í-j a4 V (m
(9)
where s,)) is the m-th function after permutation n, epoch and oz is stepsize 1-th epoch. We can rewrite this step as
000
(1)
kmm
After each epoch we perform additional outer step with stepsize 7t
N
It+1 Ft -iett
9:
(10)
MN
C.I ASYMMETRIC GENERALIZED-SMOOT NON-CONVEX FUNCTIONS
Theorem 3 non--convx asymmetric generalized-smoot convergence analysis of Algorithm 2) Ler
Assumptions 1 and 2 for functions f and {fm I Choose any T 2 1. For all 0 - 5 1, denote
à To + Ta ( ă = Lo T1 max IV (x:)l
Put T = and global stepsizes 7t
M MN En=o EM= f Impose the following conditions the client stepsizes a
22
Vor
S
1 0
aj S min
S n S
VNN(N ljā.
ca3/2 8
4a,"
34

---

Published as a conference paper at ICLR 2025
where 0 < << S 5. V(N- 1)(2N - 1))7. Let 60 - [(00) f Then, the
iterates {rel1= T of Algorithm 2 sattisfy
[
[V(())]
E
min (=0.....
min
Lo
L
8
1 +
30
8d.
((N
- 1)(2N 1) + 2(N + +1))
6a
d0 +
(N 1)A"
T
0g
Lemma 6. Recall that ā = Lo + In m | mmy((a))ll
Then
2 9c
1
N
M
I ā
| xzll² + Vf(x=)]
(1I)
2
MN
j=1 m==1
Proof.
|9:11
1
M
Σ m=1
V (n
2
2
MN
V (mm.. - V VS (mmma)))(11)))
+ +x+V)(+
MN
j=1
N M
Σ
(La + L, Vom. || -
2=l2+ -2,1 [f(x)))11
MN
m=
M
1
(ā.))
zell [=))))))
MN
j=1
(ā.)²
- x + [x
MN
Lemma 7. Let Assumptions
andd
hold for functions f and { Then, if we choose On S
/
/3n(n-1) get
E
m
1
< 20 ((N 1)(2N - 2(N (x() f())
N
1=1
+ Aafāa(N + 1)
(12)
Proof. From
9
we have
x m
Ocs Vf
(1)))))))))))))) = Iz
Os V V fm.m (2))))))
35

---

Published as a conference paper at ICLR 2025
Thus,
xell
Ot V (m. (2)
$ 2
Σ ar (V (V (m,,(((((z)))
Σ as V (m.m(((((((e))
+
< 2j
(ax)) (Lo + L1 (m)
||= -xal|
k=1
j
+
Σ
V (1m
k=1
Using last inequality, we get
| - well"
(o,)) (Lo + L1 (m | - xzll"
N
2 N
+
Σ
Σ
v f (1)
N
Ø=1
k=1
2a
(ax) (ā.)
S Sm (I+)
where 3 is constant. Then, we take conditional expectation of the last inequality and get the following
Let ar < 3 a,
N
2 N
E
m G
xell
Ft
1=1
1=1
k=1
2o
N
2
E
(2)
Denote o3 = N Enrn
/|
(1:)))) - (xx)) ?| and consider
E
fm,,(())( It
From Malinovsky al.
2022
Lemma 1) we get
2
E
V f n (2))
It
<
V (m))( - f(z:))
21
j(N -
< (V)
N - o7
36

---

Published as a conference paper at ICLR 2025
Thus,
N
28
E
mell
S E
1 xell sell" 1
N
j=1
==1
2
N
+ -(N - - of
j²
N
N -
==1
2
N(N 1)
E
Σ |0 - zzll x2
N
2
20g
((N(N 1)(2N - 1))
[V((t)))1
N
2a
N(N
+
3
Further,
N
N
3 E
m - 2=11 Tt
S 3332N(N - 1)E
| - =ell? 224
N
N j=1
j=1
(N- (N-1)(2N
+ 2a
|| fxx)))1 + (N + 1)o?
2
Thus, we choose 3 S
3N(N-1)>
2
we get
N
N
E
xz 1
I (3- N - 1])E
22 - zell? It
N
N
< 20
11(2N - 1)
| f(xx))1 + (NV + 1100
2
< 2a
(N - 1)(2N - 1)(((x)) - f") + L (vf(,))
(N + 1)
1
Σ
V
5=1
1 Lemma
2a
- 111)22-1)( - f)²
N
+ +NNN + (ā.)
1
Σ(fm (fmm((x)) -fin))
NV
s 220? ()2N
- 1)(5(r)) -ār
N
+ +2(N + 1) (āx) N
Σ
(smj (I2) - -fing)
37

---

Published as a conference paper at ICLR 2025
Now, adding and removing f to the sum factor the right- side, get
N
E
1t 112 2t
< 22 - 1)(2N 1)((()))
MN 1=1
M
+ 40 1) 1
Σ Σ j=1
(J1s(10)) smm)) {mmj)
NM
-2aaā, ((N - 1)(2N 1) + 2(N + (f(z)) - 8*)
aa + +1)A"
Proof of Theorem
From Lemma
1 and 10
we get
$( f(x)) - n (2))())).oo + (Lo + La (=l))(( lfll
2
Additionally, from the fact that 2 (a,,b) = - -|a 61 + ||a|2 + |]6|
we can get
2/ 19:11
f(x+1) S f(x) 72 (Vf(x)) + (Lo + 4 fx
2
f(xx)) 7t (-1V)((;) 9.11 |V +1
+ +Lo + [zx))(()))))
2
1211911
S f(x)) - 2/ (( + 2 [[V goll2 + (Lo + (())(
2
2
2
Consider Tt Vz(z)) - 9ell2 and denote âz = (Lo + ((IV)(())I) and at = (Lo +
Lj maxm [m then:
M
7 [Vf(z)) gell== = ?t 2
Σ
Σ
V f (m. Vmm
2
MN
j=1
N
M
$ %
Σ
(Lo + L (1 x", 1?
2
MN
j=1 m=1
N
Σ
-
2
MN
From the above inequality and Lemma 6 we get
Yt
[+(x)))1
It at
1
M
| x 12 + à,
72 211 112
2
MN
J=1
f(xx)
7t
+
Yt
d
1
I1are -.,7,1'
MN
j=1 m=1
N M
+ 0g0 1t
2 MN
|mm x I| + an? 2 [I
J=l m=1
N
M
$ {x()) + (ar??
7t
[[T((x))1 + (ā.a??? + 7t naa)
m
xx 12
2
2
MN
m=1
38

---

Published as a conference paper at ICLR 2025
Let 91 3 then
N
M
| [V + (arafrl +
Th 2
at
m
- 24 11
MN
j=1 m=1
Now, if we take conditional expectation of this and use Lemma 9
we get
E (((x+1)) S f(x))
7 [1)((
2%
+ (dvāī?²² + ož E
Σ
|0 xell² 22
MN
2 f(x)) - 2%
(1x))
2a (ina377
Ttt a3
マ/2
1)(2N
2(NV + 1)) (f( + +1)
Since 7/ S 4ā," then
30fa8
It
[+(()))] & f(x)) - E [[((xe1))=a]+ 4
((IN-
1) + 2(N + 1)) 6; + 2(N + 1)A²)
Så,
(13)
Consider the left-hand side (16). Due to the bounds
2 7/t 2 S. on Th. we have
40,
4a,
Then, we get
Tt [+())))1
BLg
Vf(x;)) S L. [+
4
/
> En
8L1
[f(m))]
[V((x)]]
min
(14)
Lo
L1
Denote & = =(xx) - f", then from 16 and
17
we get
30
f(x)) f(x411)+ +
((N
((N- + + +1) + 2 +1)
3ajat
d. dct1
((N
1) 1) + 2(N + + + +1)4*)
Sāz
[V
[Vf(z)]]
min
Lo
Li
Let ar < cd. we take full expectation and use from Mishchenko et al. 2000 Lemma 6):
where e constant such that V((N 1)(2N - -1) 2(N + 1))T S c. Now
[f(x2)
[f(x))]
E
min
min
Lo
Ln
(1+
3afa; S4,
((N - 1)(2N - 1) + 2(N + +1)))² T
30 50 +
(N 1)A"
T
4
39

---

Published as a conference paper at ICLR 2025
Corollary
Fix 0. Choose
V(N 1)(2N 1) 2(N 1))T. Let at
S
BV
Then, if > 2568g
huve
T
Ee
[V
[Vf((a))
| Sc.
min t= 0 T
min
Lu
L1
Proof of Corollary 3
Since c
12)22 - 1) 2(N + 1))T and az S on
I
V
ās
du
0t
S
B
due to the choice of 2
2568g Çe
we obtain that
TN
34
+
1 +
3nj Sûs
((N
1)(2N
+ 2(N + +1))
00
28n
Ç
60
S
T
T
16'
and that
a
{8
(N
+ +1
S
40
16
Therefore, E min
min
Vs(a)]
S..
f1
C.2 ASYMMETRIC GENERALIZED-SMOON FUNCTIONS UNDER PL-CONDITION
Theorem 7. Let Assumptions 7 and 2 hold for functions f, J and {fms [fmmim==1.
M Let
m=1
Assumption 4 hold. Choose 0 < S 4. Let on def fxx) f Choose any integer T all t denote
648 1.3
For
u6
ā. Lo + L (xx)l,,
a, Lo + L1 max fm
Put A-- = and global stepsizes
1 ΣM Ey Jm Impose the following conditions on the client stepsizes
MN
V2
a I min
(3 1)ā,
cā," 3/2
12L3as3
(,(((N - 1)(2N -1) + 2(N + 1)) + 2(N + 1)A²)
84,60
3T
(50((N - 1)(2N 1) + 2(N 1)) + 2(N + +1
S 7/t S 40;
0 0S1ST-1,
where c -((N1)((2)) 1)N - 1) NNN + T)) Let do del f (20) - fr. Let T be an integer such 648.L2
that 0 T
A > 0 be constant, a S / AT uC
6a
Then, the iterates (xt) T-1 of Algorithm
satisfy
87 S (1 uS
T-F
Aa
50
4Lo/
pw
where 5T def (IT) gt.
Proof of Theorem
Let follow the first steps of the proof of Theorem
Consider (16):
[V < f(x)) f(x++1)
3,f
(((N-1)
+ 2(N + 1)) 6 2(N + +1)A*)
Sâ,
40

---

Published as a conference paper at ICLR 2025
Since 7/p 2, and satisfies Polyak Lojasiewwizz 4 obtain that
MC (
f(x)) 5(12+1)
2āp
30/ (6i((N 1) - 1) + 2(N + 1)) + 2(N + 1) Sā;
Let T be the number of steps 1, so that [VV (f:))l 2 L: For such t, we have LO+L, L1 V (xt)
â, & 2L1 VV (z1)l Therefore, we get
pC (f(z)) - -
(1x) f(x++1)
4h [V] (x+)]l
30fa, (6.((N - 1)(2N - -1) + 2(N + 1)) + 2(N + 1)A²)
8â,
Notice that the relation à S 2L,
[f((x))l and Lemmal
together imply
[(())
[
f(()) - f
4L1
20,
Hence, we have
uC 167?
S f(x)) - f((+11)
3afa,²
2(N + 1)) + 2(N + +))²)
84,
Subtracting f on both sides and introducing 8, def (xx) f*, we obtain
uS
8.+1 S 6,
16I7
30, at
(6(((N-))22)
2(N + 1)) + 2(N + 1)
As 04 S
12 (1000000-11120----22--=--------- follows that
3afat
(6((N-1)(2)) - 1) 2 1)) 2(N +))
uS 32L
Therefore, we get
uu
8141 S 6,
32L
2. Suppose now that VV (z.)1 < 7, For such t, we have Lo + L1 || (x:)l = â, 2Lo. Hence,
WL (f(x))) 1*) < f(x)) f(((+1)
4Lo
30fa,3 3
(B.((N- (6(((N1)(22)) -1) 2(N 1)) + 2(N + 1)A²)
8û,
Subtracting f* on both sides and introducing 8, del fxx) f*, we obtain
30
dct1 < 8
(5.((N 1)(2N - 1) + 2(N + 1)) + 2(N + ))
Sà,
where p def _c_ 4L.
def Let ar aă, with ai S
84,4
for
some constant A > Then,
8141 & pp, Aa?
41

---

Published as a conference paper at ICLR 2025
Unrolling the recursion, we derive
8T S TT + Aa
MC
32 32L
Aa
1 T m²
p 60
1 p
1 p 321
Notice that 8,41 S 8, + Aa which implies
dT S + (T- Aa? -T 1C
3212
Since
AT we conclude that
á MC
640
0 0 6T S 280
+ $
32T.7'
Therefore, for 7 >
648,2] PC
we can guarantee that T - T > 0 and
T-T -0000
Aa²
Tp 5 1C
8T S p
1-
32L
S p²
f 80
+
Aa?
1-
Corollary 7. Fixe O. Choose min { (Vár
LVV
88us AT
Then, ifT
615g2
4Lp
In 26p
nal
nC
we have 8r S E.
Proof of Corollary
Since 0 < T
64
A > a S
Au
S Li
8dns A
due to the
Pc
AT
choice of T 646g
1Lo. uC
In 26g.
obtain that
1a
T-T
uS (1- 4L.
nc (T - F) 80 2tp
E 2
5g
Se
and that
4 A
5g
< 3
AT
2
Therefore, 87 S E.
C.3 SYMMETRIC GENERALIZED-SMOOK NON-CONVEX FUNCTIONS
Theorem 8. Let Assumptions and hold for functions f and {f {m]mm Choose any T 2 1. For all 5T5T denote
à Lo Ln I (xxx)l
à Lo L1 max
[m)((
my
Put A =
EN-o DM
f Impose the following conditions on the client stepsizes at
MN
and global stepsizes 7t.
V2
Vāe
ae S <in
a2 S max (G,L 1)' 6 L.Go) (N 1)5
19N(N 1)ā,
3/2
cā
< 7/t < Sā,"
0stsT-1,
42

---

Published as a conference paper at ICLR 2025
where 0
1. 2 V(N 1)(2N 2 + 1)) and G.
maxm=1 M
[ (zt)]]}
Let d0
=
f (x0) f.. Then, the iterates { of Algo-
rithm
satissfy
[V((z)]]
E
min
min
To
In
8
1 3afat ((N - 1)(2N 1) + 2(N + 1))
6a
60 +
(N 1)
T
ág
Lemma 8. Recall that ā Lo + L1 maXm.
fm
Then
21 1 112
1
M
S 30,7
| xzll2 + + (
MN
j=1 m=1
Proof.
N
M
1
v (1)
2
MN
N
M
(m. - Vmmm)(((t))) -:nme))))))))))
+ +++){(
MN
j=1 m=1
N M
Σ
(Lo + In
V [mmmn || =xll exp {2L, || xx + [
MN
m=
N
M
S (āx)²
Σ
Σ - - zell exp {2T, | - xxl1] + [[xx((
MN
Let G2 maxm=l....
M j=l...,N N
V (2+) By the induction with respect to j 1, L.... .N, we prove
that, for any m E [I....,M} M), we have V f (m) (2 s 2G,, Indeed, notice that
(mm()tt (x%)-1)) - (V5m.am ()) (x+) || + Vfm..()) (1 Vmm.F(()) (s:)
< G2 + (Lo + L, V f (zx) cxp L || Zz
1 1- 3z
< G. + (Lo + L1 V mm (1) (xx) exp L1 ||
xx
| I.
< G. + (Lop L,G,) exp [L | xell ||:71-11 zzll
By the induction assumption, we obtain that
J-1 S0
| 2zl1 S
Σ
(m, (x
V (m, (17-1)
1=1
1=1
S Sa - 1) 2G, < 11 2G,
Hence, we have that
[ (2H)-1) S G. + (To + Ln G.) exp (arta (N (N-1) 2Gr ov - 1) 2G.
Let ag S max
(V-Ti 6 Then, (fmmm) (4% S 2G,.
Therefore, we conclude that
||g. 2
N M
S (āt))
1 =zel + [
2
MN
==1 m=1
43

---

Published as a conference paper at ICLR 2025
Lemma 9. Let Assumptions 1 and
2
hold for functions f and {fmlm= Then, if we choose dq 1
/2
we get
V /3((n-1)(aa 1)(a))
m E.
- 24 1 Tt
S 4a ((N 1)(2N - 1) + 2(N ()))(a)) -
N
==1
+ on + 1)
(15)
Proof. From 9
have
2t 2(j
04 (m Iz
ae V m. (8) (2) 1).
Thus,
|| 2012
V Fm, (m)
0x
Σ at (1)
V (x)
k=1
+
Σ ai V (m,mm(())(aa))
< 2j
Σ (at)2 (Lo + L1 (mmm(())))))
exp f2L, || xz - xzll
k=1
+ 2
v V. (m,z((k)((z))
Using last inequality, we get
6j
wzll 11
(ox) (Lo Li
| xxll?
1=1
2 N
+
Σ
a2 V
(1
N
1=1
2a²
(
(ā+)
S
Let 04 < a. where constant. Then, we take conditional expectation of the last inequality and get the following
2
E
2z|12
E1
E
a Pik
xz
2t
2a
E
(m.me(A)((0z))
N
44

---

Published as a conference paper at ICLR 2025
Denote
of
m. (1x) (())
(xx))l
and
consider
Σ k=
V. (k) (2+)
From Malinovsky et al. (0022 Lemma 1) we get
|2 m. (2+)
E
5t
5 [f +
V (m).s(()(13))) - [(xz)) 21
5 (z:)) + j(N 5) o..
1
Thus,
6
E
mell
Z't
SE
m sell? Stt
j=1
2
N
j² [x+((l + J(N - 33 of
N -
E
6
N(N - 1)
|. - 2rel? x
N
2
2a
(NNN - 1)(2N - 1))
N
20 N(N
+ 1)
3
Further,
N
3 E
1
zell? It
I NNN - 1)IE
1
xell Zt
N
N
3=1
(N - 1)(2N 1)
+ 201
[[=)() + (N + 1)o7
2
Thus, if we choose B I
9N) such that 17 exp = 1, we get 1 1/1 S and
2
V
N
E
1re ||
21
I (3 - 982 N(N - 1))E
b - 2=|l xt
N
N
j=l
(N - 1)(2N (N-1)(2N - 1)
S 2a
f(xx)) + (N + 1)0?
2
S 2a 22(N - 1)(2N 1)(((x)) - f')LLo + L ([v)(())
+ (N + 1) N Σ
V (mmm))(()))1))
I Temma <
4a (N - 1)(2N - 1)(f(x)) - a
N N
+ +2(N + +1) (ā.)
(fmp((x) - -iin))
S 40 (N 11)2N 1)(((z)) - -āa
N
+ +(N + 1) (ā.) N
Σ (Fe) - -fins)
1=1
45

---

Published as a conference paper at ICLR 2025
Now, adding and removing f the sum factor the right- hiaht-handPi side, get
N M
Σ
21 11?
- I -
Et
MN
2=
m==1
N M
+ aa + +1)
1
Σ
(fms((z) (mj))
NM
j=1 m=1
=4aţā, ((N 12(2N-11))) + 2(N + (f(xz) 8*)
+ 88 + +)
Proof of Theorem
From Lemma 2 and 10
we get
22l
(Lo -.IV exp {Linh |1
Additionally, from the fact that 2 (a, b) -11aa b11² + ||a||2 + ||b| we can get
2e 1111 ((441) () (To L. exp (LiJ 11
2
<(()) 74 (-IV/(x;) gell + [V[)(( 11x
2
+ (Lo + 1 fxx))) exp (Lr> ||..1] 22 1/
- f(x)) [f + 24 [V gell + (Lo + L1 L exp (Lr [1
2
2
Consider V((x))
1e and denote àe (Lo L[IV](=)))) and (Lo +
Ln maxm 1 fm (xx) []) then:
M
2t
Vf(x)) - 12
7t
1
V {m...()) V (m
2
2
MN
J=1 m=
N
M
Σ
(Lo I. [
x 1 exp {2L, 1 -x,33/
MN
j=1 m
N
M
37tt
04
Σ
| -
2
MN
46

---

Published as a conference paper at ICLR 2025
Let us consider Li @elll now. Recall that as 4N,(N-1)I1GG)
d
N
M
L |19al1 = L178
v
(mant)
MN
j=
N
M
< Li7
| |mm V/(<))]] + [
MN
j=1 m=1
N Σ
M
$ L17
| 1 x
exp (L | =111} + [VV
MN
3=1
m=1
3L1
N
M
1 4 1
21.j-1 xz
m
11|
MN
f=1 m=1
M
3L
| - x |1
4agMM MN
j=1 m=1
1
ar(N - 1 Ge +
40;
1
2
From the above incquality and Lemma 6 we get
3 -2
N
M
7/2 19119.11 12
(((+11 (zx.)
[+(x))) 2/4
1 1/ "
ā
2 exp (L 19:11)
2
MN
J= m=1
N
M
11
f(x))=
7 [Vf(,;))
3 a
| - x ||
2
2
MN
j= I m=
N
+ 22 Yt
|- 23 112 + 2202 [x)(2
MN
$ fzx)) + (aan)
[f( + (2 +
3 ož 2
1
| 22
2
MN
m=1
1 Sine 7h S 86. we obtain
N
M
f(r+1) ((x)) 7tt 1Vf((()) + (2arās? +
3
ap
b - 2z 11
2
MN
j=1
m=
Now, if we take conditional expectation of this and use Lemma
9
get
E (((++1))az)) & f(xx)
3/1
7t [[((())
N
M
37 =2 + 2ām 7/ +
E
2z 11
Zt
MN
m=1
< f(xx))
7't - [(rr))
2azāe 22ām0² +
37
2 ae
((AV- (o)-1)(2N- 1) + 2(N + (f(xz) - +1)Aa)
47

---

Published as a conference paper at ICLR 2025
Since N Så, then
[Vf(z=)]] & f(x)) - E [f(++))))= 4
afa.
((LN- 1)(2N - 1) + 2(N - 1)) + 2(N + 1)/²)
2ā,
(16)
Consider the left-hand side of (T6). Due to the bounds
7t az f(lVf(
40,
ThS have
Ve
[[x)))
46,
Then, we get
<IV
La [Vf(z))] S
Tt (xx))1
|V
8L0
Li
4
[Vf()))]] > La TA
811
[(())
|V/(a))]
min
(17)
Lo
L1
Denote 8N =f(x)) - f", then from (16) and (17 we get
a
f(x1) - f(((+1)
((N - 1)(2N -) 1) + 2(N 2 1)) 6, + 2(N + 1)
2ā;
6₁ 0c+1
a
(((N- - 2(N + 1)) + 2(N + +1)A²)
26
|[f(21I1
[V
2
8
To
L
Let oz I
1
where is constant such that V(N 1)(2N +1) + 1))T s c. Now
cä:
we take full expectation and use from Mishehenko al. (2020 Lemma 6):
S
[f(())]
E
min
Lo
L1 [
aja 2a,
1 +
((N 1)(2N - 1) + 2(N + +1)
2-3
80
(N + 1)A
T
a
Corollary 8. Fix >
0. Choose
V(N - 1)(2N - 1) 2(N 1JJT. Let a S
AV
de TIIN+ Then, if
23660
we have
ÇE
[Vf(z)]]
Vf((x))]
E
min
min
SS.
Lo
L1
Proof of Corollary g
Since c
V((N 1)(2N - 1) + 2(N + 1))T and ar
S
ca
V
aa
at
4v
a IT(++ due to the choice of T >
258ha
obtain that
Çe
+
a, 2ā,
((N
T 1)(2N 1) + 2(N + +1))
6200 80
280
8n
S
T
T
T
16'
and that
afa dz
ÇE 16"
(N
+ 1)A" <
Therefore, E min, min. min [[
}}]
< e. Notice that the computation of Gr < 1 < T 1, requires additional T' epochs. Therefore, the total number of epochs is least 27 5128g E
La
La
48

---

Published as a conference paper at ICLR 2025
C.4 SYMMETRIC SELERALLZED-SMOOREE FUNCTIONS UNDER PE PE-CONDITION
Theorem 9. Let Assumptions
and 3 hold for functions J, {mmm= and (fmimm=ll Let
Assumption 4 hold. Choose
Ç S Let 60 def (xa) - f Choose any integer T
61óp For
all S 1, denote
ā = Lo + L ((lVil
Lo + L1 max fmm(()))))
Put A = MN
Em=1 EN Im Impose the following conditions on the client stepsizes on
and global stepsizes y
ae S min { V9N(N - -))a cā." 3/2¹
V2
vā=
16I7aae (o(((N- - 1)(2N 1) 2(N + 1)) + 2(N + 1)4²)
20
T
(e(((N 1)(2N + 2(N 1)) + +1
S 24 S sā;" 0st5T-1,
where c 2 V(N 1)( 1) 2NN + I) Let do def (oo) fr. Let T be an integer such
that 0 s T 615,L2 A > 0 be constant, a S V by AT
Then, the iterates (x=)e= of Algorithml
satisfy
89 - (1 MC
T-ア
4L Ao
do +
4Lo
where 8T def f (IT) ft
Proof of Theorem
Let us follow the first steps of the proof of Theorem
Consider (66
aña
7 [V/())) s f(xx) f(x+11)
20,
x ((NN- - 1) - 2(N 1)) 2(N + +))²)
Since " S. and f satisfies Polyak Lowaseeewwzzzssunpupnn
we obtain that
#C (f())) - f*)
f(x)) ((54))(((44))
24,
af (B.((NV - 1)(2N 1) + 2(N + 1)) + 2(N + +))').
+ 24,
1. Let T be the number of steps so that |V (fx)) 2 La For sucht t, we have Lo L1 /| V (zx)l
à, 2L, VV (z:) Therefore, get
#c (fx) - ft)
f(x)) - f(x44)(((441)
4L, V (x))
an
(Be((N - (6(((N-1)(2N 1)NN 1) + + 1)) + 2(N + 1)5²)
+
2I;
Notice that the relation à < 2L, [Vf(x))] and Lemma together imply
V [x)))
{(()) - f¹
4L1
2å,
49

---

Published as a conference paper at ICLR 2025
Hence, we have
pe S f(1z) f(z++1)+ + 1627
of
(6c((N- 1)(2N 1) + 2(N +)) + 2(N +))*')
Subtracting f* on both sides and introducing 5, def (xx) f", obtain
af
dc+1 S 6
+
(6c((N 1 1) + 2(N + + + + 1)
1677
20,
As 0g S
a.
follows that
af
RC
66(((N- 1)(2N -
-1) +) 2(N + +1) + 2(N + +))²² 1
2û,
32L
Therefore, we get
de+1 S 6:
32L;
2. Suppose now that VV (z:)ll z L. sucht t, we have Lo + L1 (x:)l åp 2Lo Hence, #f (J(zz) - 1
< f(x)) f(xx+1)
4Lo
af
- (6((N-1)(22) - + 2(N + 1)) + 2(N + 1)5')
+
24,
Subtracting f on both sides and introducing 8, def f( f+, we obtain
afal
8z+1 S 6ep + (5.((N - 1)(2N - 1) + 2(N + 1)) + 2(N + 1)
2â,
where p def _CC Ahp
Let a₁ del aå, with âi S ai (6NN 12
2
for some
constant 0. Then,
8e+1 S pd: + A
Unrolling the recursion, we derive
8T 5
T-T
60 + Aa
2
MC
32T
1=0
i=
- d0 +
Aa²
1 -
p HK
1 p 32
p
Notice that 6,41 S be + 2o², which implies
8t S 50 + (T (T-
Aa² HC
321
Since VV 60 AT
we conclude that
0 8T < 260 - Ī us
646
# T <
321
mC
Therefore, for
648 1. we can guarantee that -
T > 0 and
8T < p
T-f 00
Aa²
T 4 HC
1- p
32
Aa²
<
TTT-
60
1 p
50

---

Published as a conference paper at ICLR 2025
Corollary Fix O. Choose a S min
du 17
L1
Sine LTAT
Then, if
6480
4he je{
In 2án
have dr S
Proof of Corollary
9
Since 0
S T v
646p
A
> 0
do A7
a S Liv
8ôns LgAP:
due to the
PC
choice of T 2
648pL.
4Lg MC
260
we obtain that
(1 (1- HS
T T-f
us (T-T)
50 S E 2
ón S c
4Lo/
and that
4
d0 E
MC
AT
2
Therefore, 57 S Notice that the computation of Gt, 1. < T 1, requires additional epochs.
Therefore, the total number of epochs is at least 27
1286 1
+
SLg In 260
D PARTIAL PARTICIPATION
D.1 ASYMMETRIC GENERALIZED NON-CONVEX FUNCTIONS
M.N Theorem Let Assumptions and 2 hold for functions f, {m)m and {5mz) J m=1.==1 Choose any T Z For all 0 S T 1, denote
à, Lo = -.1. ((z))l
at Lo L1 max V (Iz)).....
ā Lo + L1 max VV (x,)ll
Put A = 5 M
EM=iF ftm and A = f + Σm=
Eÿ= fig.. Impose the following
N
conditions on the local stepsizes "ia server stepsizes Th: global stepsizes 0,:
24,
2û,
NN S n. < min
166,
VV at (2 + ag²)
71 S
āe (2 + a;) cRN
5 50 < Aāi
0SIST-1,
àt
where VT,0 < < 1 Let 80 ddl f (zo) fr. Then, the iterates {ac) T-1
of Algorithmm satisff
{ [|VS(()))1 |V [V
|
E
min 0StST-1
min
8
Lo
L
2
(niar + n/ Ra, + Y, + np Ra:)) T
1 +
407
50
T
0² + ag
(ia, + 22 Na, t
40²
We need the following relations to establish convergence guarantees:
N-1
R
Σ
Σ
=
Ft
Ft
C
N
1=
j-1
kj
m.t
3t
7'
fm
k=D
m
1=0
0,
Tt+1
(st
xx()
n7 R
51

---

Published as a conference paper at ICLR 2025
We assume that the whole sum is zero when the upper summation index is smaller than the lower index. We can derive the following recursion from the above relations:
0₂
(Ie x xt²)
24 It+1
N
0
Σ
V
(mm.t)
R
N
m
MEST
j=0
Further, the first statement of Lemma yields the following inequality:
xe41 112
((o4)) (V) I(41) + (Lo 41 IVV (z,)l)
We deal with the last term, using the second statement of Lemma] T
R-
|| 22+1112 = 02
1
V
pm
o. Fmit)
R
N
T=
mE
j=0
N
$ 207
R 2
Σ MESA
V sm
(2 (mm+))
V
+ [
N
j=0
20g RCN
24 2 2
(To + L V (Tx
Σ
0=
mES 1=0
40 (Lo L, / (f(x))
We use the following notation: à = Lo + L as = Lo + L1 maxm [Vf((z))l: ā =
V. (#z) Next, we have that
Lo + L1 maxm.j
n.. Fm,
Σ
V
fm
Fm.11)
+
fm
ri (m,t))
N
k=0
mESA
f=0
(=0
j 1
T 2
Σ
mm
(mmit)
Aij
+2 7t
V
ptd
(mm.))
m
K=
MES
1=0
1=0
Using Young's 's inequality, we obtain
N-1
4
Σ
V
pm
V
fm (3r))
MESAL
j=0
N
+ +
f
(Ix)
N
mESAA
j=0
2
+
2
m
(mmet)
- f (#x))
+4
m (x+)
52

---

Published as a conference paper at ICLR 2025
2 2
Using Malinovsky et al. 2002
Lemma 1), we derive the following upper bound on
N-1
I 4n 2 (ar)
2 1
Σ
Σ
Σ
Aud l2 ?
22 2 m.,
21
rCN
k= MESt
Cr (M - Cr) 0f
(M-
+ 41 N²C²
M M-1
j-1
Ct - x || 2
+ +472 (āt)²
2
Σ
1=0
[m (xx))) + j(N - 5)
:(N-
+ 4ht
- im.t
where
M N-1 Σ
of MN
Σ
V (z+) vm (z.))1
12 j=0
0 m
Σ
V f (z1)
vm (x,)
N
j=0
Using this bound on
|
m
2
for V del
CRN EK'E Σ Emespr Σラ=
1
Fm, It 2
we ob-
tain
N-1
E [
Σ
Σ
E
CRN
D
me
1=0
(at)²
CRN
R-1
Σ
N-1
1
Σ
MJ 2
+ +
Σ
rd
Zz 2
rCN
r=
MES
f=0
k=0 mESA
1=0
1=0
R-1
N-1
+ j(N - 5)
N - omn.t )
Σ
CRN
0=0
mESA
1=0
R-1
(NPOPPIT( + Cr(M - Cr) 0f ))
Cr(M-
4t N2C²
CRN mestr j=0
M-1 1
Recall that 7r NR < R S Tous
Summing over indices, we arrive at
R(R - 1)
Ane (a.)² E M(M - 1)
BM <
172 [VV)
2
2
M
M
3 M
2 1
(x.))
11(2M-1)))))))) - 1) +
3 7/ (N + +1)
2
M
1
Σ
m
2
2 M C
*R+1 2
3
+
3 3MM 1)C
!1
2
N2 00
2, 1
$ (o.)² + R+) +
Σ
V
12 - 1)
3"
2
2/
+ 3
2
72
(N + 1) Σ a
1 M
3
3
M
m==1
2 R+ M C
3 t N2
(M -4-177 1 o?:
53

---

Published as a conference paper at ICLR 2025
To derive the bound on E [V] we need to require % I n. < 16a, to have 1 1-2n/ (0e) (1+
R²) > O. Using Lemma we have
M
E [V]] S N2
(m)(())) + R ((V
M
M
1
R M C
+ +
N
m + 21 N2 (M- 1)cº
M
m=1
M
Σ
(Lo + 1i V (xx)ll) (Jm(wr) - fm)
M
m=1
M
N-1
+ 4n (f(1)) f(x.)) + 22²2N
| (2:)
N
m=1
j=0
M - C 1 M
+ 2n R
Σ (m,
(M 1)C M
m=l
M
I 41j 2 1
Σ
(To + L1 (fm())))))))) - (mm
M
m=1
+ 4nk R2 a, (f f(x.))
M
N-1
1
+ + N
Σ
Σ
(Lo + L1 (V (f) -fra"t)
M
N
m=1
j=0
M - C 1
+ 4n R
Σ
(Lo + L, (z) (fm(()) - f(n)
(M 1M-1IC I)C M
m=1
The bound for E [Vi] is given by the following:
Σ fm ))
M
E [V.] S an
(((x)) -5 8r
+
4n a ae (f(x.)- - 1*)
M
m=1
M
N
+ 472 Noe
-5+ /r
M
m=
j=U
M C-C
M
+ 4np Ra;
(f(x)) (f(z))+++ ff + fr
f
(M - 1)C
M m=1
Recall that A== f + Em s A= S 1 ΣM
N Σ5= fmL"" .Thrrffrre
M
E [ S an (f f + A²) + 4n R2 ae (f(z)) - -(r)
+ N (f(x.) / + )²) + 4n Ro:
(M 1)C (f(xz) - A'))
M - C
Rewriting, we obtain
E M < 4(f(x)) -f) (1 niaa + R² a, + +22NG, + ni Ro: (M - 1)C
M - C
M C
+ +nta,' + NY,. + An Ra (M - 1) ب A
<4(f(x)) - fr) (3/a + n/ R2 a + Nā. + THe Ra,)
+ 4n/aA'' + 2, + +ni A.
54

---

Published as a conference paper at ICLR 2025
Following this, we need to establish a bound for the scalar product
R-1
N-1
- (1)) =t- - ze41) B1 Vf (z1). :
1
Σ
fm
N
mES!"
j=0
Using the identity 2(a, b) = ||a bl1 - |lal2 -1bb1 ? we obtain
-(Vf (z+) 3z I1+1)
0: 01 2
f (x:))1²
+
0g 2
Σ
N
0=
mest
j=0
+ 2
O0
(ar)
v
1 R-1
Σ
Σ
N
1
fm
Fmitt
R r=
C
N
mESA
j=0
00
V (=+))|
Imm
(mm.t
2
2
N
mesp
j=
N-1
0g +
Σ
Σ
Σ
V
(=
sm
(me))
2
R
N
mES
j=0
Using Lemma T and omitting one of the terms, we get
0 - (z)) s - - IVI (z,) + (a,) π -
O
2
R-1
Σ
Fm,t x2.
P=
mESt
j=0
Taking the expectation with respect to the randommess of the algorithm, we have
0:
E [[(+++)]] S (xx))
| (=+)
2
0.07
Σ C
Σ mESA
Σ
2
+
Iz
2R
N
j=0
a |1=e
+
Fz+ 1 11?
2
Recalling the definition of E [Vi] and taking the conditional expectation, we obtain
- 0:
0.02
[[[((41)) ma] s fxx))
V (xx))
+
E
[V4] +
8. V/ + [V]
2
2
02 (1 20,
0.03
[xx)
| (xx)
E [.] + 0. [Vi].
2
2
Using the fact that 0g <
1 40, we arrive at
B |f 4
af
a
E E[f(2(+1) xa] < fl (z,)
(x))
+
[Vi]
+
E [Vi]
Sā
16a;
Recalling the bound on F. [Vi,, we obtain
0
a² E[V]+
a
E [[ S f(x)
(x.))
+
E [V]]
4
Sā.
166
0
< f(x))
V (x=)))
+
(s(xz) - - (1/ + 11 R2. + 72 Nor + n/ Ra.)
2a,
4n
ag
33
(RRu,S' + + 1/ R
+
(18)
22,
40²
55

---

Published as a conference paper at ICLR 2025
Using the fact that 8, 2 &, get that
(
<
4
40
Therefore,
O f ((=))l &ho
[V(()))]
[
[Vf(z)]]
T1"
4
| 811
f((x)))
8
min
L0
L1
Denote &c def f -
f Then we have
min
S 5241 + òz
Lo
L1
2ā,aß + ag
(n + n/ 12, + + Nā, + naa))) de
40²
20,4 + a
+
+ + Nā, A + +n Ro,A
4d²
Recall that 17 S
24.
cR V az
(2 + 70 S
cRN
28.
V d2(2
N VT. Using Mishchenko et al.
2020 Lemma 6), appear
c min
[((+))11
min t=0, I.... T-1
Lo
L1
2ā, 107
(nf R²a + 7/ Nā; + o/ Ra.) T
50
T
2ā + a
(njas + + + rs Raa Ra...).
+
40²
Corollary
Fix & > 0. Choose = 2VT. Let $ 201 20 22r -aj) RT 7t S
36a
24.
38n
Then, ifT 2
126n (c we have
N
(20x0)+ +
[[[(()))]]
min 1=0 t= T-
min
S.c.
Lu
Lı
Proof of Corollary 4 Since c = 2VT and
I
28.
cR
a. (2ā,
+ap)
cRN
(266,277aa))
and W)
200
2as (2
+o J RT Tt
28, N
02
+
36g
'R RT
due the choice of T 2
max
726y ÇE
12A"
GA
we obtain that
2a, aa, 1d?
(ntaa + R2, - N2 + n/ Roi)
Edg
36g
ÇE
50 5
T
T
a² + a3
CE
(ma.S* + 11 Ra,
<
44?
24'
and that
2û. i + a
(E
Nā. -
46
1t.
24'
Therefore, E ooi, { min
[
}}
Se.
Lu
L1
56

---

Published as a conference paper at ICLR 2025
D.2 ASYMMETRIC SEEERALIZED-SMOOKK FUNCTIONS UNDER PE- PE-CODIITIO
Theorem 10. Let Assumplions
and 2 hold for functions J, {mmm= and (mmi)m=l..
Let
Assumption 4 hold. Choose
< 3. Let 60 def
f (xo) - -f* Choose any integer T
61ôok? For uC
all 5 5 T 1, denote
â Lo L [xx))]
at Lo Ln max (mm((1)))))
ā Lo I1 max
V S (st)]l-
m.j
Put A = f- M Em= sm and & = = M Em= N Eÿ=o Jms- Impose the following conditions on the local stepsizes "i, server stepsizes nt, global stepsizes 0,
20, 16û,"
NR S m min
V as (2ā, + ag)' 3213 (6, + A+) at (2ā, + az)
03.00
TL3 (ō, + A+) ar (20, + 0z.)
20
07
7N S min
ā (2 0 + ag)²
TL;
6 + A¹)
ā (2āzā? + +,?)
\ |322 8c + 5
ās (2ā, + a,,)
S 5 <
1
0S1ST-1,
40,
where c 2 VT. Let T be an integer such that r of Algorithm 3 satisfy
S
G16.L uc
> be constant, a: S V
bp
AT
Then, the iterates {Iz)t=) T-1
T-$
dT S (1
MC
AL
do
4Lo
where 5T E - ft.
Proof of Theorem
10
Let us follow the first steps of the proof of Theorem
Consider
18
0
[V)())) < (xx)) (((++))
4
20, ag
(f(x)) -1² (nia, + Rē, + 7 Nā, + n Rai)
40²
28, of ag
(
22 Aā, + ol Ra.s
4a²
Since 02 2 n,, and f satisfies Polyak-Lojjsiewiic. Assumption we obtain that
nC (f(x)) f*)
S f(x)) f((141)
26,
2ū,0; + a3
(f(z)) - -f¹) (nior + R², Na ni Roi)
46²
24 2²,0 + 0g
+ + Nā,
Ray
407
57

---

Published as a conference paper at ICLR 2025
1. Let be the number of steps so that [V (fx) 2 La L,"
For suchtt t, we have L1+ || Vf (ax)
4 2T, // (x4) Therefore, get
PC (f())))) - (r)
4L V (+)) - f(xt) - (((2+1)
20,07 + az
(f(x)) -1") (n/ + Mf + +22 + n Rai)
40z
20,0 + +0
1 22 Nā, + nr Ra.
40g
Notice that the relation à s 2L1 [x)() and Lemma
together imply
[
[Vf(2)))
S f(x)) - S
4h,
24z
Hence, we have
S f(x)) - ((1+11)
16I7
2ā à² + aZ (f(zz) ((()))-8) (
(1h + 1/ na, + N2,Na, - ni Ra,)
40²
"/aAs'n(Naa) + nイ Ra, A.) 2ā, ai + 0z
Subtracting f* on both sides and introducing 8, fz ft, we obtain
8,41 S 6,
16L
20,a at + a
8e (nia; a: + + - -22 + ni Rat)
403
2I 20,ā² + 0
2 a, + 2 N + U Ra.s*)
+
40²
48 As 7/ S 16.1 (2.
40/nC 128T, )o, (26 it follows that
and 1tt S
2ā,a + a3
be (naa + 1/ R² + 72 + Rai) +
4a²
20, + ag
(1,a, + + "N, + + Ra, S
uC
40
32T.7
Therefore, get
uS
dr+1 S 8z
32T.
2. Suppose now that (x,)l < L. such 1, we have Top L, [V)(( åp 2T. Hence,
#C (f(x)) f*)
< f(x)) f(x141)
4Lo
28 à + a3
(f(x)) - -f¹) (nto: + R2a Na ni Roi)
44²
24 2a,0 + 0g
(i/a= Nā, + +
Ra,
407
58

---

Published as a conference paper at ICLR 2025
Subtracting f on both sides and introducing 8, def f (21) fr, we obtain
26,0; + a
sc+1 S dept +
dc (nh + R& + Nā + m/ Rat)
46
2g + 0i
1/1 a + N + n Ra, Ra,
4d
where P
def
1
MC ALo
Let ary and 1p def onl with 7e 4L5(6:+A Ro and
del'
40
16 ie S V 11/16++ Jo, R [2a])
for some constant A > Then,
d141 S pō: + Ao?.
Unrolling the recursion, we derive
N-1
81 S T-
60 + Aa
2
nC
Σ
32L
==
i=0
$ p 60 +
Aaz
1-
p
PC
1 321
Notice that 81+1 dc + Aa?, which implies
dt S do + (T- Aa² - A uC
32T.7
Since
V A7
conclude that
0 87 S 200- - T MC
6.
= T <
32L
PC
Therefore, for
646 23 MC
we can guarantee that
T > 0 and
8T < p
T-f 60
Aa²
Tpp i 1C
1-
32
T -- 80
Aa?
< p
1 1- p
S min {V
Corollary 10. Fix > 0. Choose
AT.
by In
880e LT
Then, T
616g
+
MC
ALe In 26g nc g
we have dr & E.
Proof of Corollary 10
Since 0 < /
646,2?
A> a S
dn AT
S Li
8805
due to the
ac
LoAT
choice of T 2 P5
4ha ac
In 26g we obtain that
T-T
uS ( (1-
#o (T-
8n
80 S 2
4Lo
and that
4LoA
d0
8
<
AT
2
Therefore, 87
59

---

Published as a conference paper at ICLR 2025
E EXTENSION TO GLOBAL STEPSIZES WITH PSEUDOGRADIENTS
Let us consider Algorithm manner. We replace %/p co pseudocode. Recall that
I For the other two algorithms same results can be obtained in a similar with Tpp +ctell9911 after the computation of 9p in the
V [/())))
M M( tpp
|1
V Vm (x
m=1 1=
By the triangle inequality, we obtain that
M
1
11 S
(Vim(z)))
v(m((())))
+ [+(x,,,
(u
1p)
M
1
Σ
(2,,,,)
(u M
m=
Since every fm is (Lo, L1 smoothh have that
Op
Σ
Σ
(v
tp
M
++
By Jensen's 's inequality we have that
M
M
Op
Σ
23'l
1 (v M
Up
(0- (p- M
Σ
(V tp)
M
j=
j=ty-1
Lemma
(Up - tp) a? (f(itt) - f
For any sufficiently small 8 > 0, let us choose ap I
v (100)) Then, 11 S
||V f + 8.
The lower bound on |1gp1 obtained similarly: we just need to write the triangle inequality for the || f(t,,))) IlI. We have
ff || S (v M
Σ Vmm( V (1)) + 11g
+1
5 ||pp||
Finally, we obtain that [[+,((t,,,)] 8 |لرو|| s || )l
Hence
1
1
(cb + +G+) + & [f(;,,)) o + c |ل (6-46) + V
It means that the practical choice of the stepsize only slightly differs in the constants in the denomi- nator. So, all our theory works for it as well.
F ADDITIONAL EXPERIMENTAL DETAILS FOR MAIN PART
In this section, we provide additional experimental details: parameters search grids and some tech- nical details that did not fit in the main text. For all the plots provide in the legend all the best parameters found by the grid search. The parameter grids are provided as table for every method. The code is available at whttp:: ttt.tt..uuuu..o//gg htt.ttccco//oootooo//oeee
60

---

Published as a conference paper at ICLR 2025
It can be seen from pseudocode of Algorithms 2 that global stepsize depends the full gra- dient. However, our numerical tests showed that use of gradient approximations 9p for Algorithm I and gt for Algorithms 2 3 gives better numerical results while being less computationally pensive. Thus, in our practical experiments we decided to use this approximation calculation of global stepsize. We want point out, that the theoretical analysis for this "practical" version of the algorithm can be done considering very small inner stepsizes. Although, we decided not to include the current version keep the presentation more concise and avoid additional complexities.
F.1 METHODS WITH RANDOM RESHUFFLING
10
10
SO, 1r-1e-07
10
NASTYA, Ir=fe-06
f6x
CSO, c=10000.0, |=0.0001
CLERR, c=100000.0, 10-000001
10
10
10
0
20
40
60
80
100
Epochs
Figure 5: Function residual for Qq 10-? The best parameters provided in the legend. In these experiments we compare methods with random reshuffling, that shuffle data once at the start of training process. The main idea is show the positive impact of random reshuffing and clipping on algorithm performance. We incorporate these two techniques inside our CLERR method (Algorithm{)) 2)
Firstly, consider (4. For these experiments we take d = 1 and randomly sample 1000 shifts e [-10, 10). We run all the methods for 10 different seeds on a logarithmic hyperparameter grid. Then we choose the best hyperparameters according to the best mean loss values on the second half of epochs. The parameter grid provided Table T To find f*, we run the Newton method for couple iterations until convergence.
Since both Nastya and Algorithm 2 have jumping the end of every epoch, if we tuned the inner stepsize along with other parameters, the inner stepsize would go zero and the outer stepsize would be selected such as these methods solve the problem in step. This would be unfair because other baselines do not
jumping technique, they would not be able to achieve such performance. Thus, we decided to fix the inner stepsize for Algorithm 2 and Nastya equal to the best stepsize, chosen for SO, and tune the clipping level and outer stepsize with the outer stepsize the values supported in theory. Here and later, for simplicity, we speak about Algorithm 2 in terms of stepsize and clipping level, that can obtain from on and from (3). The best stepsize for SO is 10-7, so we choose inner stepsize for Nastya and Algorithm 2 the same. Nastya chooses outer stepsize equal 10-7, while CSO and CLERR (Algorithm 2 choose it equal to 10-4 CSO clips gradients at the level 10a, while CLERR at the level 10a.
exceeding
Method
Stepsize
Clipping Level
Inner Stepsize
SO
10 10-8. 10-2
NASTYA
10 10-8, 10
10
CSO
10- 10-2
100 10
Algorithm
10 5,10 1000
10". 10
Table 1: Parameter grids for experiments on methods with random reshuffling on
61

---

Published as a conference paper at ICLR 2025
F.1.1
RESNET-18 18 ON CIFAR 10
Accuracy
15
1.0
2.0
0.8
10
0.6
0.4
0.5
0.2
100
200
100
200
100
200
2.0
20
0.8
15
0.6
50, Ir-0.01
Test
10
0.4
CSO, cl=10.0, Ir-0.1
NASTYA, in_ 0n__m=0.01,, Ir=0.1
CLERR. in in__r-0.00,,00 d-11000. Ir-0.1
0.2
CLERR-h, c0 4=1000
100 200
100
200
100
200
Epochs
Figure 6: Loss, gradient norm and accuracy train and test dataset for ResNet-18 18 CIFAR-10. The best parameters are provided in the legend.
In this experiment we consider image classification task. We train ResNet- 18 He al. (2016) the CIFAR-10 Krizhevsky et al. (2009) dataset. The implementation ResNet-18 was taken from https::/g
com. wwwaanngiu/yytoorrrg cifrr All the methods are run on differ- ent random seeds on logarithmic hyperparameter grid. Then we choose the best hyperparameters according the best mean test accuracy on the last 25% of epochs.
In this experiment, we do not fix the inner stepsize for Nastya and CLERR, since methods do not try to make it as small as possible, as it was in the previous experiment. However, both SO, Nastya, and CLERR choose the same inner stepsize 10 as the best. Then, both Nastya and CLERR choose bigger outer step size 10-1, and CLERR also chooses clipping level on outer step size as 10. Despite the fact that both Nastya and CLERR choose bigger outer stepsizes compared to inner stepsize, jumping does not have any impact on this problem. CLERR clips outer gradients at the level of 10, so this also does not help method converge to a better area.
Moreover, we provide results of heuristically modified Algorithm where we fix clipping level and inner stepsize of Algorithm _ equal to the best clipping level and the best stepsize from CSO correspondingly. The tunable parameters are only Co and с1 for outer stepsize. We call this method CLERR-h. CLERR-h chooses outer stepsize equal to 5, while the clipping level very tiny and equal to 10-2 All the parameter grids are provided in Table
Method
Stepsize
Clipping Level
Inner Stepsize
Co
RR
10 1003. 10
NASTYA
10 10-3, 10-1
10
10
CRR
10 10
10", 10
CLERR
10 1010'
10", 10
[10 10
CLERR-h
10a
10
10
10
[00
10
Table 2: Parameter grids for experiments methods with random reshuffling ResNet-18 CIFAR-10.
62

---

Published as a conference paper at ICLR 2025
F.2
METHODS WITH LOCAL STEPS
C-LGDJ, 101--000 0_000000000 c_1=1e-10
CLCDU, d 2_0_=ee-00._00:1000000 0_ e_1=0001
10"
CELGG 1.1, c_ 0_0010000.4 c_1-fe-10
10'
GELGC r1,_0000000000000000000000000000 f_1-1-100
16
CE-FedAug, 1-1, 69 1r10,, d_ 6L.6100.0
FF-Fadkug. F-1, se__ I-1.0, d_irte005 clee-100
C-LGgu, T-10, 10 10 0_0-1000000, 10
10"
CUEDJ, 1-10, te 10 1_00000000 c_1-000
16
CELGO, 1-10, 0-100000000 C_ 1-
CELGO 1-10, 0-1000000000 1-te 10
Fe-Aed 100000..0
le 1.1.0
10"
Festvg. 1-10 1-1.0,
I11e-00. d-10.0
10
10
10
10
10
10"
10"
10
0
25
50
75
100
125
150
175
200
0
25
50
75
100
125
150
175
200
Number of communications
Number communications
(a) = (1....,1 1)
(h) = (10,... 10)
Figure 7: Function residual for 4 starting from different vo for different number of local steps on the client device T. The best parameters are provided in the legend.
In these experiments we compare methods with local steps: Algorithm (C-LGDI) with Communi- cation Efficient Local Gradient Clipping (CELGC) (Liu et al., (202)) and Cropiig-Enabble-Pe
(CE-FedAvg) Zhang al. (2022). For comparison we take problem (4) for d 100, where we randomly sample 1000 shifts E [-100 10j6. To make the distributions of data on each client more distinct between each other, we sort the whole dataset at the beginning of the experiment by ||zi||-- Each method has 10 clients, where each client has equal number of data. We provide results for two starting points: To = (I,..., 1) and æig = (10, ...,, 10). All the methods are run for 10 different random seeds on logarithmic hyperparameter grid. The best hyperparameters are chosen according to the best mean loss on the last 25% of epochs.
Each client performs local data. For case of implementation and due to computational limitations we iterate over all the clients sequentially.
1
10 local steps, and each local step is performed on the whole
We reformulate constants cu and C1 as server stepsize and clipping level from (3) to better interpret the experimental results. We start by paying attention to results with single local step. Firstly, consider C-LGDJ (Algorithm []. It chooses tiny client stepsizes 10-10 10 and small server stepsizes 5 10-5 for both starting points. For Figure 7 it also takes very big clipping level for server 1024, compared to Figure 7b) where it clips on level 106, which is obvious because on the second picture methods start farther from the minimum and have bigger gradients. Secondly, consider CELGC. In both cases, it takes very small client stepsizes: 5 10-5 and 5 10 respectively, and very big clipping levels: 14 and 10 respectively. Finally, CE-FedAvg also takes small client stepsizes: 10- and 10-5, rather big server stepsizes, which are equal to 1, and average client clipping levels: 10 both cases. For r = 10 we have the same parameters for C-LGDJ, CELGC tries to make even smaller steps with high clipping levels, while CE-FedAvg uses much bigger server stepsize and much smaller client stepsize, for the case from Figure 7al
The grids of hyperparameters for zo (1, (I..... 1) are provided in Table and for 20 in Table
(10, .... 10)
Method
Cl. Stepsize
Se. Stepsize
Cl. Clip Level
Co
C)
CLipped-L--GiD-J
10 10 10
10-10 10
10
10
CELGC
10
10
[10 10
CE CE-FedAvg
10 10 10
10
10
10". 10
Table 3: Parameter grids for experiments on methods with local steps on Here "cl." means "Client", and "se." "server".
for T0 = (1, 1).
63

---

Published as a conference paper at ICLR 2025
Method
Cl. Stepsize
Se. Stepsize
Cl. Clip Level
CSippe
10
10
10 1o
10
10 10 10
CELGC
10
100 10, 1010)
CE-FedAvg
10 10 10")
10
10
10", 10
Table 4: Parameter grids for experiments methods with local steps Here "cl." means "client", and "se." "server".
(4 for 20
(10, 10).
F.3 METHODS WITH LOCAL STEPS, RANDOM RESHUFFLING PARTIAL PARTICIPATION
10
10
10
CRR-CLI, s s_ir=fe-10 c_rr=1e-10 co 100000000000000 1==1e-10
10"
fx)
CF-FedAvg PP, r=10, s 1r=10.0, 10.0, c 1r- c_cl=1.0
10
10
1
0
25
50
75
100
125
150
175
200
Number of meta-epochs (communications)
Figure 8: Function residual for 4. starting from zo = (L, 1) with batch size 16. The best parameters are provided the legend.
In these experiments we compare methods with clipping, random reshuffling, local steps and partial participation: Algorithm 3 (CRR-CLI and with CE-FedAvg Zhang al. (2022) with partial par- ticipation (CE-FedAvg-Pa) PP.). For comparison we take problem (4) for d = 100, where we randomly sample 1000 shifts I; E [010, 10jd. Again, make the distributions of data each client more distinct between each other, we sort the whole dataset at the beginning of the experiment by ||>;||- All the methods are for 10 different random seeds logarithmic hyperparameter grid. The best hyperparameters are chosen according to the best mean loss on the last 25% of epochs.
Each method has 10 clients, where each client has the is chosen to be 2. The method performs local steps on each client from the cohort, after which it performs communication and goes the next cohort. In the Algorithm 3 the clients to the cohort chosen sequentially with sliding window after FlientRRehuffllng. In CE-FedAvg-PP clients to the cohort are always chosen randomly. The starting point is chosen 2g (1, (.., 1). All the methods are run for 10 different random seeds. The best hyperparameters are chosen according to the best mean loss on the last 25% of epochs.
amount of data. The size of the cohort
For local steps we chose batch size equal to 16. In Algorithm 3 eevrry client goes sequentially over the whole shuffled local dataset with batch size window. In CF- CF- we fix number of local steps to 10, and each client samples batch every local step.
Just like in previous experiment in Section 5.2 all the methods try to reduce the influence of local steps by making inner stepsizes very small. Algorithm 3 chooses both client and server stepsizes equal 10 10 and CE-FedAvg- -PP chooses client stepsize equal 10 and client clipping level equals 1. Speaking of outer steps, Algorithm 3 chooses global stepsize equal to 5 10 with clipping level 16 And CE-FedAvg- -P has server stepsize equal to 10. The grids of hyperparameters are provided in Table
64

---

Published as a conference paper at ICLR 2025
Method
Cl. Stepsize
Se. Stepsize
Cl. Clip Level
Co
C1
CRR-CLI
[10-10 10 10
[10 10 10
10 10
10
[0
10
CE-FedAvg-PP
10 10
10 10, 10
110", 10
Table 5: Parameter grids for experiments methods with clipping, random reshuffling, local steps and partial participation. Here "cl." means "client", and "se." "server".
Loss
||ffix||l
Accuracy
30
1.0
25
0.8
0.6
0.2
0.0
200
CLERR, in_ir=0.0001
25
0.8
CLERR, in_ir=0.001
20
0.6
CLERR, in 0r0001
15
CLERR, Ir=0.1
0.4
10
0.2
0.0
50
100
150
200
100
150
200
50
100
150
200
Epochs
Figure 9: Algorithm
2 with different step sizes on ResNet-18 on CIFAR-10.
G ADDITIONAL EXPERIMENTS
In this section, we provide additional numerical experiments, that did not in the main paper: in Section G.1 we investigate the influence of that inner step size the behavior of Algorithm and in Section G.2 we provide additional experiments on logistic regression, where we compare Algorithm
2 with clipped SGD.
G.1 How THE INNER STEP SIZE AFFECTS CONVERGENCE OF THE METHOD
In this experiment, we investigate the influence of the inner step size on the behavior of Algorithm on 18 on CIFAR-10. To do this, take the same hyperparameters for Algorithm in and only change the inner step size. The results are provided in Figure
Sections 5.1.
On the hand, if take the inner step size too small (blue and orange lines), it converges very slowly. This is obvious since Algorithm 2 becomes regular Clipped-GD, which can be seen from pseudocode. Because CD performs a single step per epoch, it has slow convergence. On the other hand, if we take the inner step size too big (red line), the method diverges. It does not have clipping on the inner step, so such behavior expected. To summarize, is important to take the inner step size small, but not too small, because it may slow down the convergence.
G.2 LOGISTIC REGRESSION EXPERIMENTS
Since the experiments on neural networks (Sections F.I.I regular CSO (SGD with clipping) showed very good results, decided to conduct additional experiments on logistic regression, where we compare CSO with our Algorithm We consider gisette and realsim datasets from libsvm library Chang & Lin (201I). All the methods are run for 3 different random seeds on logarithmic hyperparameter grid. The best hyperparameters are chosen according to the best mean loss on the last 25% of epochs. The results presented in Figure 9
65

---

Published as a conference paper at ICLR 2025
CSO, cl=10.0, 0r=0.001
CSO, cl=10.0, 1r=0.01
CLERR, 1r=0.1, cl=100, 1r=0.001
10"
CLERR, in 0.001, cl=100, 0.001
10
|
||ff(x))l
10-1
10-1
10
10
50
100
150
200
250
0
20
40
60
80
100
Epochs
Epochs
(a) gisette
(b) realsim
Figure 10: Gradient norm for logistic regression problem on gisette and realsim datasets. The best parameters are provided in the legend.
Since the inner stepsize for CLERR has the same meaning stepsize for CSO, we decided to take the same parameter grids for these two parameters. The same goes for clipping levels in spite of the fact that CLERR clips the gradient approximation only in the end of the epoch. This experiment shows that CLERR either has the same performance as CSO or better. Since logistic regression (Lo, La smmoohh such result is expected, Algorithm 2 designed for such type of functions. Figure 10a shows us that CLERR chooses very small outer stepsize 10-3 while inner step size is bigger than the one in CSO: 10-1 10-2, In the Figure [0b CLERR chooses parameters in the opposite way: inner step size is very small and equal to the one from CSO, while the outer stepsize bigger. The parameter grids for gisette dataset is presented Table and for realsim in Table
Stepsize
Clipping Level
Inner Stepsize
CSO
10
100, 10a
CLERR
10
10
100. 10
10
Table 6: Parameter grids for logistic regression experiments on gisette dataset
Stepsize
Clipping Level
Inner Stepsize
CSO
10
10
100
10a
CLERR
10 10-3 10
10", 10a
10 10
Table 7: Parameter grids for logistic regression experiments on realsim dataset
H EXTENDED RELATED WORK
The usage of distributed methods is dictated by the fact that data can be naturally distributed across multiple devices/clients and be private, which typical scenario in Federated Learning (FI.) (Konecný et al. 2016; McMahan et al.) [016]] Kairouz et al.) 2019). FL systems have practical considerations and are backed by extensive experiments from recent years. These highlight impor- tant effective design rules and algorithmic features. Below is a quick overview of some key points.
Partial Participation. Partial Participation (PP) FL technique in which a server selects subset of clients to engage in the training process during each communication round. Its application may be necessary in scenarios where server capacity client availability is limited (Kairouz al. 2021). The technique is useful when the number of clients is large, as the benefits of convergence do not grow proportionally with the size of the cohort (Charles al.) (02T). Clients can be selectively chosen to form cohort, prioritizing those that deliver the most impactful information (Chen et al.) 2020).
Local training. Local Training (LT), where clients perform multiple optimization steps on their local data before engaging in the resource-intensive process of parameter synchronization, stands
66

---

Published as a conference paper at ICLR 2025
out as of the most effective and practical techniques for training FL models. LT was proposed by Mangasarian | Povey et al. (2014); Moritz et al. (2015) and later promoted by McMahan eet al. (2016). While these works provided strong empirical evidence for the efficiency and potential of L.T-based methods, they lacked theoretical backing. Early theoretical analyses of LT methods re-
lied on restrictive data homogeneity assumptions, which are often unrealistic in real-world federated
learning (FL) settings (Stich) 2018 Li et al. 2019 Haddadpour & MMhddavi 2019). Later, [haled] al. (2019a b) removed limiting data homogeneity assumptions for LocalGD (Gradient Descent (GD) with LT). Then, WWodwoothh et al. (2020); Glasgow et al. (2022) derived lower bounds for GD with LT and data sampling, showing that its communication complexity is no better than minibatch Stochastic Gradient Descent (SGD) in settings with heterogeneous data. Another line of works focused on the mitigating so-called client drift phenomenon, which naturally occurs in LocalGD applied to distributed problems with heterogeneous local functions (Karimireddy et al. 2020 Tran-
Dinh ct al. 2021; Gorbunov et al. 2021b; Thapa et al. 2022, Mishchenko et al. 2022 Malinovsky
al. 2023b Yi ct 2024).
Although removing the dependence on data homogeneity was a key advancement, the theoretical result suggests LT worsens GD, which contradicts empirical evidence showing LT significantly im- proves it. Karimireddy et al. (2020) identified the client drift phenomenon as the main cause of the gap and proposed solution to mitigate it, which led the development of the Scaffold method, featuring the same communication complexity as GD. Later, another algorithm S-Local-GD was proposed by [Gobbnnvv et al. (2021b). Finally, MMshhhenko et al. (2022) demonstrated that a novel and simplified form of LT exemplified by their ProxSkip method, results in provable communication acceleration compared GD. LocalGD is at the base of Federated Averaging (FedAvg) (McMahan et al. 2016). Essentially, FedAvg is variant of LocalGD with participating devices and data sam- pled randomly. FedAvg has found applications in various ML tasks, such as, e.g., mobile keyboard prediction (Hard et al. 2018). Wide applicability of FedAvg motivates theoretical study of its back- bone LocalGD algorithm.
Random reshuffting. Stochastic Gradient Descent (SGD) serves the foundation for nearly all advanced methods used to train supervised machine learning models. SGD is often refined with techniques like minibatching, momentum, and adaptive stepsizes. However, beyond these enhance- ments, it is important to decide how to select the next data point for training. Typically, variants of SGD apply a sampling with replacement approach where each new training data point is selected from the full dataset independently of previous samples. Although standard Stochastic Gradient De- scent (SGD) (Robbins & Monro 1951) is well-understood from theoretical perspective (Rakhlin)
iet al. 2012, Bottou et al. 2018; Nguyen et al.) 2018 Gower et al., 2019 Drori & Shamir 2020
Khaled & Richtárik 2020: Sokolov 2022 Demidovich et al. 2024), most widely-used ML frame-
works rely on sampling without replacement, as it works better in the training neural networks (Bot-)
tou 2009] Recht & Ré, [2033] Bengio 2012, Sun 2020p. leverages the finite-sum structure by ensuring each function is used once per epoch. However, this introduces bias: individual steps may not reflect full gradient descent steps on average. Thus, proving convergence requires more advanced techniques. Three popular variants of sampling without replacement are commonly used. Random Reshuffting (RR), where the training data is randomly reshuffled before the start of every epoch, is an extremely popular and well-studied approach. The aim of RR is to disrupt any potentially unto- ward default data sequencing that could hinder training efficiency. RR works very well in practice. Shuffle Once (SO) is analogous to RR, however, the training data is permuted randomly only once prior to the training process. The empirical performance is similar to RR. Incremental Gradient (IG) identical to SO with the difference that the initial permutation is deterministic. This approach is the simplest, however, ineffective. IG has been extensively studied over a long period (Luo) 1991 Grippo 1994; Li et al. 2022; Ying et al.) [2019] Gürbüzbalaban et al. 2019 Nguyen et al. 2021). A
major challenge with IG lies in selecting a particular permutation for cycling through the iterations, a task that Nedic Bertsekas (200T) highlight as being quite difficult. (Bertsekas) 2015) provides an example that underscores the vulnerability of IG to poor orderings, especially when contrasted with RR. Meaningful theoretical analyses of the SO method have only emerged recently (Safran &
Shamir 2020 Rajput et al. 2020). RR has been shown to outperform both SGD and IG for objec-
tives that are smoce- (Gürbiizbalaban et al. 2015 Haochen & Sral 2019). Jain et al. (2019)
examine the convergence of RR for smooth objectives. Safran & Shamir 2020); Rajput et al. (0200)
provide lower bounds for RR. Mishchenko et al. (2020) recently conducted a thorough analysis of IG, SO and RR using innovative and simplified proof techniques, resulting in better convergence
67

---

Published as a conference paper at ICLR 2025
rates. Recent advances on RR can be found in (Sadiev et al. 2022 Cha et al. 2023 Cai al. 2023 Koloskova et al. 2023b).
Other useful features. Further techniques in FL include compression during the communication
rounds (Alistarh et al. 2018; Gorbunov et al. 2021a Panferov et al. 2024), clients' drift reduc-
tion (Karimireddy al. 2020
Gorbunov al. 2021b
68


Reviews:
[{"review_id": "WTb0NUHdri", "reviewer": "Reviewer_tEec", "summary": "This paper proposed and analyzed new methods with local steps, partial participation of clients, and Random Reshuffling for Federated Learning with generalized $(L_0, L_1)$ smoothness assumption. Moreover, they also analyzed these methods with the additional Polyak-Łojasiewicz condition. Their results are consistent with the known results for standard smoothness, and they also conducted experiments to support their theoretical claims.", "questions": "See Weakness.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The authors proposed new methods with local steps, Random Reshuffling, and partial participation for Federated Learning and proved the convergence of their algorithms under $(L0, L1)$-smoothness assumption and under additional PL assumption.", "weaknesses": "(1): It would be better if the authors can add a conclusion/discussion section at the end of the main text.\n\n(2): The section E Additional experimental details are missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JaeUVE6uS3", "reviewer": "Reviewer_pNnc", "summary": "This paper studies and analyzes the federated learning algorithms under the nonconvex setting with the generalized smoothness condition. In the deterministic setting where each client can compute its full gradient, the authors propose a new method with local steps with jumping. In the stochastic (finite-sum) setting, the authors propose two algorithms with partial participation and shuffling on both clients and data sides. All the algorithms proposed are new, and rigorous convergence analysis under generalized smoothness is provided in this paper.", "questions": "Besides the weaknesses mentioned, I have the following questions.\n- Is it possible to analyze the local steps for Algorithms 2 and 3? Would the local steps bring benefits with random reshuffling, or are there any technical difficulties that the authors foresee?\n- Is it possible to analyze the case of different inner stepsizes for different clients?\n- In general how does one choose the constants $c_0, c_1$ in the step sizes?\n- Is Appendix E on additional experiment details unfinished? There are only a few figures with captions that extend beyond the box.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors provide a comprehensive analysis for federated learning under generalized smoothness conditions, which I believe is novel and new.\n- It is interesting to see random reshuffling is analyzed under generalized smoothness for federated learning problems.\n- The spectrum of the federated learning algorithms with their convergence results in this paper is quite substantial.", "weaknesses": "- In the section of related work, the authors missed recent advances since 2020 in random reshuffling (e.g., [1-3]), which I believe should be included for a complete context.\n- The global step size $\\theta_t$ requires evaluating the full gradient, i.e., $\\|\\nabla f(x_t)\\|$, which requires further computation and communication costs.\n- Algorithm 2 returns $x_T$ in the statement, but the convergence is only analyzed for the best iterate. The statement of Algorithm 2 possibly needs rephrased.\n- The experiments are mostly conducted on a synthetic function (4). \n\n[1] Cha, Jaeyoung, Jaewook Lee, and Chulhee Yun. \"Tighter lower bounds for shuffling SGD: Random permutations and beyond.\" International Conference on Machine Learning. PMLR, 2023.\n[2] Cai, Xufeng, Cheuk Yin Lin, and Jelena Diakonikolas. \"Empirical risk minimization with shuffled SGD: a primal-dual perspective and improved bounds.\" arXiv preprint arXiv:2306.12498 (2023).\n[3] Koloskova, Anastasia, et al. \"On Convergence of Incremental Gradient for Non-Convex Smooth Functions.\" arXiv preprint arXiv:2305.19259 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yTLiZQm1YM", "reviewer": "Reviewer_mTke", "summary": "The paper proposes three federated learning algorithms for solving minimization problems under a generalized smoothness assumption. More specifically, the authors propose a new method, called Clip-LocalGDJ, that uses local steps, a second one that combines local steps with Random Reshuffling, while the third method allows also for partial participation of the clients in the federated learning regime. For all the above methods, convergence guarantees are established under a generalized smoothness assumption, matching the existing results under the classical smoothness assumption. In addition, the authors provide theoretical guarantees for the convergence of each method in the  Polyak-Łojasiewicz (PL) setting, proving a linear rate of convergence. Extensive experimental results are provided, validating the theory and testing the effectiveness of each method in practice.", "questions": "- Which algorithm of the three should be preferred in practice? In particular, given that Algorithm 3 allows also the partial participation of the clients, it seems to be the best choice in practical scenarios where all clients are not available during the time that the algorithm is run. However, in cases where all clients are available, are there any potential disadvantages of using Algorithm 3 in comparison to Algorithm 2? Additionally, in full participation cases should one prefer in practice Algorithm 2 that utilizes also Random Reshuffling over Algorithm 1? \n- Algorithm 3 allows for partial participation by performing a reshuffling of the clients that participate to solve the underlying problem. Is there any practical application, where performing random reshuffling in the clients turns out to be more beneficial than the classical sampling with-replacement technique for partial participation? Are there any theoretical insights or empirical evidence on the trade-off between these two approaches?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The analyses of all algorithms are made under the relaxed smoothness assumption and the results are tight in the sense that they coincide with the already established ones in the case when the classical smoothness assumption is true.\n- The Clipped RR-CLI algorithm combines local steps, random reshuffling and partial client participation and is analyzed for distributed non-convex and ($L_0, L_1$) smooth problems. This is the first algorithm that combines all the above three properties and is being analyzed under such relaxed conditions.\n- The paper is well-written and the presentation is easy to follow for the reader.", "weaknesses": "- Since the analysis is provided under the most relaxed assumptions that exist in the literature, do you believe that an analogous proof could be extended in cases where the underlying problem is a minimax optimization problem or in scenarios where extrapolation is also used in the process? \n- How does the stepsizes used in Theorems 1, 2 compare with the ones in previous works? Do the best stepsizes found in the Experimental Section coincide with the ones predicted in the theory? \n- How might the large-scale nature of data in practical federated learning settings pose challenges for implementing the proposed algorithms? What potential obstacles do you see in adopting these methods widely in practice?\n\nMinor Typos:\n- In Section 1.3 (line 186): \" clipped IGWang et al. (2024)\" the reference should be added correctly.\n- In Appendix E: it would be better to incorporate beyond the plots some further details on the additional experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "m9QFJIUCt0", "reviewer": "Reviewer_R3wR", "summary": "This paper introduces three novel federated learning (FL) algorithms—Clip-LocalGDJ, CLERR, and Clipped RR-CLI. The first method adds gradient clipping to localGD on the server side. Building on the first method, the second method adapts reshuffling to local updates. The third method extends the second method to address the client drift problem by shuffling the clients. The convergence of all methods is analyzed under $(L_0, L_1)$ generalized smoothness in non-convex settings without assuming data heterogeneity. Additionally, this paper analyzes the proposed methods under the Polyak-Łojasiewicz condition within the generalized smoothness setting.", "questions": "please refer to the weakness.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This work adapts gradient clipping to local GD with convergence guarantees.\n\n2. This work fills in several theoretical gaps:\n\n2.1. Convergence analysis for an FL method with partial participation of clients under the $(L_0, L_1)$-smoothness assumption.\n\n2.2. Convergence analysis for FL methods under both $(L_0, L_1)$-smoothness and Polyak-Łojasiewicz conditions.", "weaknesses": "1.This work claims that its analysis uses weaker assumptions by not assuming data heterogeneity. However, in the convergence upper bounds presented in Theorems 1, 3, and 4, the right-hand side contains terms such as $\\Delta^$ or $\\bar{\\Delta}^$, which are closely related to data heterogeneity. Specifically, $\\Delta^*$ is an example of data heterogeneity as defined in earlier work [1]. This undermines the claim of weaker assumptions since the convergence analysis still implicitly depends on data heterogeneity through these terms. It would be better to make it clear that what is the cost of removing the heterogeneity assumptions.\n\n[1] Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, Zhihua Zhang:\nOn the Convergence of FedAvg on Non-IID Data. ICLR 2020\n\n2.  There are many works [2, 3, 4] that provide convergence guarantees without heterogeneity bounds in their complexity. It would be more complete to add these related work.\n\n [2] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, Ananda Theertha Suresh:\nSCAFFOLD: Stochastic Controlled Averaging for Federated Learning. ICML 2020: 5132-5143.\n\n [3] Quoc Tran-Dinh, Nhan H. Pham, Dzung T. Phan, Lam M. Nguyen:\nFedDR - Randomized Douglas-Rachford Splitting Algorithms for Nonconvex Federated Composite Optimization. NeurIPS 2021: 30326-30338.\n\n[4] Chandra Thapa, Mahawaga Arachchige Pathum Chamikara, Seyit Camtepe, Lichao Sun:\nSplitFed: When Federated Learning Meets Split Learning. AAAI 2022: 8485-8493 2020.\n\n3. After Corollary 1 and Corollary 2, the authors claim that when $L_1 = 0$, their iteration complexity matches that of local GD and GD. However, from my understanding, the motivation for analyzing generalized smoothness is not just to recover known results in the smooth case. In Zhang et al. (2020b), it was empirically shown that gradient clipping can achieve faster convergence. Therefore, to strengthen the theoretical contributions of this work, the authors could add more theoretical discussions on how the iteration complexity of the proposed methods accelerates beyond local GD, rather than simply stating that their complexity matches the previous results in the smooth case. A discussion similar to Remark 5 in Zhang et al. (2020b) would be helpful.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)