A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond
Authors: Yipeng Li
Xinchen Lyu
Zhenyu Liu
Venue: NeurIPS 2025 poster ()
Keywords: stochastic gradient descent
random reshuffling
federated learning
convergence analysis
Primary area: optimization
TL;DR: A unified convergence analysis for permutation-based Stochastic Gradient Descent (SGD) with arbitrary permutations of examples.

Abstract: We aim to provide a unified convergence analysis for permutation-based Stochastic Gradient Descent (SGD), where data examples are permuted before each epoch. By examining the relations among permutations, we categorize existing permutation-based SGD algorithms into three categories: Arbitrary Permutations, Independent Permutations (including Random Reshuffling and FlipFlop Rajput et al., 2022), Dependent Permutations (including GraBs Lu et al., 2022a; Cooper et al., 2023). Existing unified analyses failed to encompass the Dependent Permutations category due to the inter-epoch permutation dependency. In this work, we propose a generalized assumption that explicitly characterizes the dependence of permutations across epochs. Building upon this assumption, we develop a unified framework for permutation-based SGD with arbitrary permutations of examples, incorporating all the existing permutation-based SGD algorithms. Furthermore, we adapt our framework for Federated Learning (FL), developing a unified framework for regularized client participation FL with arbitrary permutations of clients.

A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond
Yipeng Li
Xinchen Lyu
Zhenyu Liu
Tsinghua Shenzhen International Graduate School, Tsinghua University
National Engineering Research Center for Mobile Network Technologies, Beijing University Posts and Telecommunications
DDeartmeent of Broadband Communication, Pengcheng Laboratory 1 liyp25@mails. tsinghua, edu. 1vxinchen@bupt. edu. cn zhenyuliu@sz. www.insss..tiinnnu.. tsinghua. edu. cn
Abstract
We aim to provide unified convergence analysis for permutation-base Stochas- Gradient Descent (SGD), where data examples are permuted before each epoch. By examining the relations among permutations, we classify existing permutation-buet SGD algorithms into three categories: Arbitrary Permutations, Independent Permutations (including Random Reshuffling and FlipFlop RRijuu
2022 ). Dependent Permutations (including GraBs [Lu et al. 2022a Cooper ct al.
al. 2023 ). Existing unified analyses failed encompass the Dependent Permu-
tations category due to the inter-epoch permutation dependency. In this work, we propose generalized assumption that explicitly characterizes the dependence of permutations across epochs. Building upon this assumption, we develop a unified framework for permutation-based SGD with arbitrary permutations of examples, incorporating all the existing permutation-baser SGD algorithms. Furthermore, we adapt our framework for Federated Learning (FL), developing a unified frame- work for regularized client participation FL with arbitrary permutations of clients.
Introduction
We study the finite-sum minimization problem
minxER" [((x) + + fn fx)
(1)
where d denotes the dimension of the model parameter vector, N denotes the number of the local objective functions {fr} and each fn Rdd IR assumed to be differentiable.
1.1 Initial Motivation: Example Ordering in Permutation-based SGD
Permutation-basee SGD, One popular way to solve problem (I) is Stochastic Gradient Descent (SGD). It updates the parameter vector iteratively according to the rule
x" = = x" - (x())x"").
where 7 denotes the step size and т (n) denotes the index of the local objective function at itera- tion For classic SGD, π (n) is chosen uniformly with replacement from {0, 1. N 1): for permutation-bant SGD, (n) is the (n + 1)-th element of a permutation æ of I, .N 1).
Due to its simple implementation and empirical superiority [Bottou 2012]. permutation- SGD
Part of the work was done when the author was with Beijing University of Posts and Telecommunication.. t *Corresponding authors.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

has garnered more attention recently. The first topic of this paper is the convergence analysis of permutation- SGD (Algorithm
A measure of the quality of the permutation of examples. The convergence rate of permutation- based SGD is determined by the permutations of examples. Thus, to study it, we need a measure of the quality of the permutation of examples. Note that we say that permutation is good if it leads to high convergence rate of permutation- based SGD, and vice versa. For a small finite step size ? the cumulative updates in any epoch q are
N Σ v
x++ Xx NV
(x,
==0 ien
optimization vector
V2 2 (x())(X))) (Vir()(())) - vf((x)).
error voctor
where this equation is from Smith et al. 2021 Equation (13)] (we replace with z as omit O3)2N3)), and it can be proved by Taylor expansion. Here, we additionally assume that each fn is twice differentiable. The optimization vector is beneficial; the error vector is detrimental and depends on the order of examples. Thus, the goal is to suppress the error vector. For instance, we use Lebesgue 2-norm for both vectors and matrices:
N-1
Error vector|| S
[
(VSz( Vs(xx)) -V)(())))VV(((()))
S
L2
7
ien
where the last inequality is due to L-smoothness (see Definition and Definition [here, p 2).
Definition (Order Error, Lu et al. 2022b al). The order error &g in any epoch is defined as
V (x,,()))x)) (V(x))))))
BE[N]
This implies the order error Qq can be used as measure of the quality of the permutation of examples: smaller oy means faster convergence rate, and better permutation, and vice versa. Even though the order error was proposed in et al. (2022b), where the authors justified its validity on synthetic experiments empirically, the rationale behind it (that is, the above analysis) has not been well understood until this work.
Existing permutation-basst SGD algorithms. Based the relations among permutations, classify the existing permutation-bastt SGD algorithms into three categories:
Arbitrary Permutations (AP): Permutations are generated without any specific structure, allow- ing for completely arbitrary permutations for all epochs.
Independent Permutations (IP): Permutations are independent across epochs.
Random Reshuffling (RR): The permutation in each epoch is generated randomly.
FlipFlop Rajput et al.
2022 See Appendix F3 for details.
Greedy Ordering Lu et al.
2022b Mohtashami et al. 2022 |:
The permutation in each
epoch is generated by greedy algorithm.
Dependent Permutations (DP): Permutations are dependent across epochs, with the permutation in one epoch affected by the permutations in previous epochs (explicitly).
One Permutation (OP): The initial (first-epoch) permutation is used repeatedly for all the subsequent epochs. When the initial permutation arbitrary, it called Incremental Gradient (IG); when the initial permutation is random, is called Shuffle Once (SO).

---

GraBs: It includes GraB Lu et al. 2022a and PairGraB Lu et al. 2022a; Cooper et al.,
2023]. In particular, GraB has been proven to outperform RR, and even theoretically
optimal permutation- based SGD algorithm [Cha et al. 2023 See Appendix
C for details.
For Greedy Ordering and OP, as done in prior works (see Lu et al. 2022b] for Greedy Ordering and Mishchenko et al. [2020] for OP), we use the bound of AP as their bounds (The bound of AP applies to all the other algorithms.) and will not discuss them in the remainder of this paper.
A more general assumption. For AP or IP, the relation among permutations is arbitrary or inde- pendent, and thus we can bound the order error for any epoch and then apply this bound for all the epochs. To deal with these categories, Lu et al. [0226] proposed Assumption T Lu et al. [002bb
considered an interval of arbitrary length, not necessarily an epoch.).
Assumption (Lu et al. ) There exist nonnegative constants B and D such that for all Xy (the outputs of Algorithm
(5,) B f(IVf( D.
By proving that Assumption I holds for AP and IP with specific values of B and D (under some standard assumptions in SGD), prior works [Lu al. 2022b Mohtashami al. 2022 Koloskova et al., 2024) successfully incorporate them into one framework. However, none of the unified frame- works permutation-bant can be that, existing works implicitly deal with the order error é, separately across epochs (as in Assumption D. while in DP (in particular, GraBs), the example orders across consecutive epochs are dependent. This limitation sparked our initial motivation for this work-to develop unified convergence analysis framework of permutationn -based SGD that includes DP.
SGD has successfully incorporated DP. The main reason for the failure
To achieve this, we propose more general assumption (Assumption 2 than Assumption !
Assumption 2. There exist nonnegative constants {A.) {B:} and D such that all Xy (the outputs of Algorithm 7
(6g) S
A (3) + Σ B₁ [V 1=0
i=1
This assumption explicitly characterizes the dependence between permutations across different epochs. In particular, when A; = O and B; = 0 for all i (1, .q. it reduces to Assumption Our analytical framework transforms the task of obtaining the algorithm's 's bound into proving that Assumption 2 holds. Especially for DP, the task is to identify the relation between order errors. For instance, for GraBs, the main task is to establish the relation between o. and 6 for 2 1.
1.2 New Challenges: Client Ordering in FL with Regularized Client Participation
FL with regularized client participation. Federated Learning (FI.) [MMMahan et al.; 2017 one of the most popular distributed machine learning paradigms, which aims to learn from data dis- tributed across multiple clients while ensuring data security and privacy. In cross-device FL. [Kairouz al. 2021], only small fraction of clients can participate in the training process simultaneously. FL with regularized client participation (regularized- pattern, where each client participates once before any client is reused, which can be caused by diurnal variation [Eichner et al.) 2019]. Wang and Ji [2022] and Cho et al. (2023) showed that the regularized participation pattern is better than the vanilla participation pattern (ang et al.) 2021] The second topic of this paper is the convergence analysis of FL with regularized participation (Al- gorithm 2)
reggularize--paticipattoo participation FL) is one realistic participation
New challenges. Equation I is also the problem of FL if the local objective functions fn represent the clients (In contrast, in SGD, the local objective functions represent the examples.). This correla- tion raises one important question: Is possible to apply the example ordering algorithms in SGD to client ordering in FL? The answer is affirmative; in fact, prior works [Cho et al. 2023 Malinovsky et al., 2023a] have taken a first step toward this. In this paper, we aim to advance this line of work by developing unified framework of regularized eegularized-prrtiipattoo clients. Compared to SGD, the main challenges of FL lie in the following two aspects:
FL with arbitrary permutations of
1. Partially parallel updates. In round of federated training, the selected clients are in parallel.
3

---

2. Local updates. It performs multiple local updates on each local objective function.
(i) The first challenge causes that diy (for SGD) cannot be applied in FL.. To address introduce a new order error Pg for FI. in Definition 2 (ii) The second challenge causes that we can only access the - (that is, P in Algorithm 2) of the local objective functions, instead of the true gradients, which complicates our analysis largely.
Definition 2. The order enror Pg in any epoch q in FL is defined as
v(n)
Pq
max NE[N]
(i(n)
Σ
(VSn,()(Xa) -VS(x))
where v(n)) =
S and S 2 2 denotes the number of selected clients in each round (see The main difference compared to dg is highlighted in red.
Algorithm
1.3
Main Contributions
The main contributions are follows:
Example ordering in SGD (Section 3). We propose more general assumption (Assumption 2 to bound the order error, which explicitly characterizes the dependence between permutations across different epochs. Based on it, we develop a unified framework for permutation-bant SGD with arbitrary permutations of examples, which is the first unified framework that includes DP. We prove that all the existing permutation-base SGD algorithms can be incorporated into our framework.
Client ordering in FL with regularized participation (Section We develop unified frame- work for regularized partteciiaiiiiioonnn FL with arbitrary permutations of clients, which is the first unified framework that focuses on client ordering. In particular, we propose FL-GraB accel- erate the training of FL.
2 Related Works
Detailed related works are deferred to Appendices A and C
2.1 Permutation-based SGD
Table I:
Existing unified analyses of permutation- SGD and their upper bounds (of conver- gence rates). Numerical constants and polylogarithmic factors are hided. We translate all the bounds with our notations, assumptions, and step size choice. We let a 0 in Assumption 3 for comparison.
Alg.
Lu et al. 20226
Koloskova et al. 2024400 (1)
This work
AP
+
L. NQ
LEA.N NQ
LFFNNe NQ
(3)
Lia Q
LRNNs NQQ
NQ
IP
RR
L.uu
+
LRey/Ns NQ
Same as AP
L.Fu
LE./Ns
NQQ
FlipFlop
LFo
(LFayNN))
Q
NQ
DP
GraBs
L 3
La
((4)
NO
[2022b] and ours, equivalent Assumption For cleurer comparison with other bounds, keep "N" in both numerators and denommators in the bounds of AP.
It stronger assumption than La Lu
Here, A represents min (a, b).
For GraBs (that is, GraB-prote GraB, PairGraB), L = L L2,00 Loo. See Definition 3 for L, Lu, and Loe.
Convergence analyses of permutation- SGD. The most relevant works the unified anal- yses [Lu et al. 2022b Koloskova et al.. 2024], which are summarized Table
AP. For AP, the best bound is from Koloskova et al. 20244] (i) Their advantage lies in the first term, which is not dominant when the number of epochs Q is large. (ii) They bound the order error over period of O (())), rather than an epoch, which complicates the analysis of other algorithms largely. For instance, for RR, their bound is worse than the other works.

---

IP. (i) For RR. Lu et al. [2022b] and this work achieve the same convergence rate, which matches the baseline Mishhhenko et al. 2020]. (ii) addition, this work includes FlipFlop for the first time, showing that FlipFlop can achieve the same rate as RR.
DP. For GraBs, this work includes GraBs for the first time. In addition, our bounds (for GraBs) match the original bounds of GraBs [Lu et al. 2022a Cooper el al. 2023 under a weaker assumption (Assumption B
2.2 FL with Regularized Client Participation
Table 2: Existing upper bounds (of fxxq) f.) for regularized-particpattoo FL algorithms. Nu- merical constants and polylogarithmic factors are hided. We set = 1 (in Algorithm 2 and a (in Assumption (3) for comparison. See Appendix G.3
Alg.
Prior works
This work (unified frameworkk
FL-AP
Po 1282. + PN
1222 ()) Q²""""
Fo exp (-42)
+ 1252_2 Q"
1.22 p
NO
FL-RR
L exp
(- (_KKN
g N
22. N
(2)
Fo exexp
(-22) +
2
JeN=
FL-GraB
Fr + exp
12 8 Je Q
12 N
Theorem 2. The difference in the first term can be due to the step size choice. 2 It's from Malinovsky et ul. 2203aa 's Theorem 6.1. The difference in the optimization term is because they consider g-strongly y ponvex objectives (in contrast, we consider PL. condition), and use the advanced technique shuffling variance in Mishchennk et 22020)
It's from Cho al.
2023's
Convergence analyses of FL with regularized client participation. The convergence analy- ses of regularized-parricinatoo FL. have been studied in Wang and Jil [2022), Cho et al. [2023
and Malinovsky et al.) [202aa]. where Wang and Ji [0022] and Choo et al. [2023] consid- ered regulatized-parriiiptttto FL with AP (FL-AP) and Malinovsky et al. [2023a] considered
popilarized-paticcpple FL with RR (FL-RR). This work aims to develop a unified framework that includes these cases. Since Cho et al. [023] considered the μ-PL condition and Malinovsky
et al. [2023a] considered the j--tronngy convex objective functions, we next translate our bounds
(non-convex) with PL condition (see Appendix (.3). Table 2 shows that bounds match the existing bounds when the optimization term (the first term) is omitted (when Q is large).
2.3 Preliminaries of GraBs
The goal of GraB (including other variants) is to find permutation to minimize the order error o, = maxne[N]
E (V5x,()(xx,)) (x(,)) (Notably, in GraBs, oy is defined by
I1-11oo) which
is aligned with the goal of herding [Welling 2009 With this insight, [uu et al.
[202aa] proposed
GraB (to produce good permutations online) based on the theory of herding and balancing [Harvyy
and Samadi
2014; Alweiss et al. [. Consider N vectors {z,, - such that 2N-1 Zn
and x. Then, GraB applies the process of balancing and then reordering.
Balancing, For any permutation म. assign the signs {En) N-1 (e,, E +1)) to the permuted
vectors 3 using the balancing algorithms (such Algorithm
3 in Appendix C
Reordering. With the assigned signs and the old permutation π, produce new permutation x
by the reordering algorithm (that is, Algorithm f in Appendix(C)
Then, Lemma
3
(in Appendix
D
proves that the following equation holds:
maxx WE[M]
Σ
(()
Σ Z Ž=U
+ 2
1
max RE
Σ
nE[N]
i=
the new herding error
the old herding enror
5(1). if (c:) assigned by Alg.
where we call the three terms, the herding error under T' (new), the herding error under т (old), and the signed herding error under т, respectively. Equation (2) ensures that the herding error will be reduced (from to x') as long as the signed herding error small. That is, the herding error can be progressively reduced by balancing and reordering the vectors. By iteratively applying this process (balancing and then reordering), the herding error will approach the signed herding error, which
5

---

is proved to be Ó (1), if the signs are assigned by Algorithm Alweiss et al. 2021] The above content introduces the key idea of GraB. We show how use Equation GraB Section [.2
(i) Importantly, GraB has been proven to outperform RR, and even be a theoretically optimal permutation-based SGD algorithm [Cha et al., 2023]. (ii) Furthermore, the GraB algorithms have also been applied in distributed optimization (not FL) [Cooper et al. [2023] and multi-objective opti- mization (ang and Kwok 2025]. Both give us strong motivations to incorporate this DP algorithm into one unified framework.
3 Permutation-based SGD
Notations. We use II-IIp to denote the Lebesgue p-norm: For simplicity, we use ||-I| to denote the Lebesgue 2-norm. We use S to denote "less than" up to some numerical constants and polylogarithmic factors. See more notations in Appendix B
Algorithm 1: Permutation- SGD
Input: un, Xo; Output: (x,)
for 0, 1,1,..... Q
do
x xg
for = 0, 1, ..... N do
Setup. For SGD, we consider the problem in Equa- tion I.. In the context of SGD, the local objective functions represent the examples. See Algorithm Here, denotes permutation of 10. (at the same time, it serves as the training order of examples). At the end of each epoch, produces the next-epoch permutation by some permuting algorithm (Algorithm D The details of the function Permute Algorithm for GraBs are specified in Table
x + x 7V (n,)
Xx+1 x
I
T9+1 Permute ..rmute....)
3.1 Main Theorem
Theorem gives main framework for permutation- SGD. See Appendix the additional extension for Theorem
Definition 3 will help deal with the multiple smoothness constants in GraBs. We assume that the global objective function f is lower bounded by S. and let Fo = -xx
Definition 3 smoothness. We say f is "pp.p-smooiie if differentiable and for x,y Rdd
- - (y)llp S Lpsy |x - yll,
p = pl, we write Lp.p' as Lpi ppp 2, we write Lp.z/ as for convenience.
Theorem 1. Let the global objective functton f be L-smooth and each local objective functions fre be smoghh and sm-othh (p 2 2).
2 be a numerical constant. Suppose that there
exist and D such that for S 9 S v - 1,
(0,)² S (
and there exist (4,) {B,} and D such that for q 2 v.
(²,)² 2 A ))² 2- + Σ B, / [[V[((xx D.
/1 ンイ
Ifr min
then
LN 32
41.2,0 -5
ALz. vB
32L
Q-1
Σ
5Fo NNQ
+ cr
L2 L2
D o oo
Q 4=0
where c = 10/(1- Ei A,) is a numerical constant.
3.2
Case Studies
In this section, we prove that the existing algorithms can be incorporated into our framework (The- orem T under some given assumptions (e.g., Assumption B. The key results are summarized in
Table 3 The specific choices of A,, B, and are summarized in Table Due to space limitations, we focus on GraBs, and deferred the details of other algorithms to Appendix

---

Table Upper bounds of permutation based SGD. Numerical constants and polylogarithmic factors are hided. To maintain consistency with GraBs, we use brghh-robability bounds for RR. FlipFlop and GraBs, instead of in-expectation bounds.
Alg.
Upper bound of (o,)*
Upper bound (of 7 Eg=o [
AP
AP
(o.) < Na [f(x,)]
+ N3²
LR(1+-))
LPaNs
(Prop.
RR
(o,)* s No² |V +N2
LFo 2x)
<RRw//Ns NQ
(Prop.3
TP
LP6 L88(1+ +x
(o,)* < No? [VV +
LFow/N NY
(Prop.
4
+
GraB-
3/
proto
(6,)² s (0.-1)² aa? IV [Vx(x,)1)1 +
(a NQ
(Prop.
DP
GraB
(0,)% s (0 (N2 |V i)l
ho Hos No
(Prop.
20) No (xx
PairGraB (Prop.
(o.)² 2 (0.-1)² (Nº a2) VV +5
L Kocha
La Kas NQ
For a clearer comparison with other bounds, keep "N" in both numerators and denominators the bounds of AP.
For FlipFlop, we bound the order error period 2.N instead of N (Appendix F.3 Rajput et al. [2022] gave the upper bound of FlipFlop for quadratic functions (in contrast, this work gives the bound for non-convex objectives).
For GraBs (that GraB-proto, GraB, PairGraB), L- = L L2.00 (1 + a) + Lxe.
Assumption 3. There exist nonnegative constants & and such that for any n {0, 1, I....,, NN 1},
fv fx(( S a² [V(()) + + Vx R..
Analysis of GraB-proto. To clearly present our theory and analyze GraBs, we focus on GraB-proto, the simplified version of the original GraB. The key characteristic of GraB-prote Prroto (and other variants) that the example order depends on the example order of previous epochs. Thus, the goal is find the relation between og and 1 Specifically, for all 2 and [N],
0g 2L |x,-- - 1l + max
Σ (V
V f
(3)
nE[N]
(i) First, note that the first term on the right hand side in Equation
3 is the well-studied "parameter
deviation" [Mishchenko et al. [020]. whose upper bound is provided in Lemma 6 (ii) Second, since in GraB-proto, (zz(s)) } correspond to ([ [Vfn,()) (x V (1 we can apply Equation (2 to the second term in Equation (3) (we
[ and {z+(() correspond to
denote this term as T2):
S max T2 in
Σ
V
1 CG = 2 + CG 2
1 2
2
NEIN]
2
where C = O (log
dN
Ô (1) is from Alweiss al. 2021
Theorem 1.1] and G
to scale the vector length to be no greater than 1. Now, combining (i) and (ii) gives the relation Proposition [
aa |/ fxxx-1111 + Here, we use Assumption
Proposition 1 (GraB-proto). Suppose that Assumption holds. If each In is smoohh and y S
N, we obtain that, for q = O, (ōo) s <2aa2 V fxxo) 11 + N2 and for q 2 1, with probability at least 8.
3 (ō ))² (1 N2 +2022 |V +C252
(σg) < 4
50
7

---

where C' = O (log(
C=
) = Ô (1). Applying Theorem and tuning the step size, we obtain that,
with probability at least 1 Q61
[((xx)]|= 1 (1+ (1 + Loo) ) Fo + (o
(42000 NQ
Q
Analyses of Graß and PairGraB. See Table 3 (i) First, the upper bounds of GraB and PairGraB almost identical that of GraB-proto. (ii) Second, the & of GraB is affected by the factors from the previous two epochs (such as Qg-1 and gg-2). This is because GraB uses the average of the stale gradients for centering, while PairGraB is free of centering (see Appendix C). Formal statements of GraB and PairGraB in Propositions O and (in Appendix(F)
Federated Learning
Setup. In this section, we adapt theory on example ordering in SGD for client order-
Algorithm 2: Regularized- FL
ing in FL. For FL, we consider the same prob- lem as that in SGD (that is, Equation [ No-
Input: To. Xo: Output: (x,)
for q .. Q do
tably, in FL, the local objective functions rep- resent the clients in FL. We focus on FL with regularized client participation (regularized- participation FL), where each client participate once before any client reused [Wang and Ji] 2022]. More concretely, see Algorithm 2 Dur- ing each epoch, it selects S clients at time from the permuted clients (under the permuta- tion т) to complete round of federated train- ing, until all the clients have participated. Pay 10 attention that one "epoch" may include multiple I To+1 f Permute (...)
w < Xg
for n 0. 1..,,
do
Initialize x f- w
5
for k: 0, 1...... K do
x x2 f Xg1
V (n (x
P2 + x5.0 x2
if if + 1) mod S = then
1 5:==0 P
w -
5
Xg+1 < X2 (/ -w)
"rounds". At the end of cach epoch, it produces the next-epoch permutation by some permuting algorithm. Here, we also consider the global amplification (Wang and Ji 2022 (see Line 10p. Con- sidering that we mainly study the client ordering of FL in this paper, we use Gradient Descent (GD) as the local solver of FL (see Lines 5 and 6) for simplicity. We assume N mod S = 0.
4.1 Main Theorem
Theorem 2 gives our main framework for regularizeel-partiipattoo participption FL. See Appendix K for the additional extension for Theorem 2
Let the global objective function f be L-smooth and each local objective functions fn be p smooth and Ly-smooth (p 22). Suppose that Assumption 3holds. Suppose N mod $ = 0.
Theorem 2.
Letv 2 be numerical constant. Suppose that there exist B and D such thatfor S q S v 1.
( < B (Vxxx)1 D.
and there exist {A:). {B.} and D such that for q 2 v,
v
(g,)² 2 < ( )² Σ Ba V [V)(
1fr S min
1
EE Ag ( // Vi B,
VI M-EEs A,
AL2, VD' KNT then
gI.KNg' 321,,, KN (1+o)' 4la,,
Q-1
5F,
1 vD + 2 L2 k3, + + 23 K2 S D())
V fx,,)))
MKN Q + + L3 K2
Q
S Q
4=
where c= 10/1-E1 A,) is a numerical constant.
'To main consistency with Lu et al. 2022a] and Cooper et al. 2023 we use failure probability of Q8
rather than d. Appendix E.9 shows that the framework can provide bounds that hold with probability 1 1- 8.
8

---

We note that the third term (containing <) on the right hand side in Equation (4) is not subsumed into the assumptions of the order error. This is because this term comes from the local updates, which is affected by the example order within each client, rather than by the client order in Fl..
4.2
Case Studies
Table 4: Upper bounds of FL with regularized client participation. Numerical constants and poly- logarithmic factors are hided.
Alg.
Upper bound of (p,)²
Upper bound (of
Eg-0
Q
FL-AP
L. Q
+
LFa8s) NQ
+
LFiNNs)
NQ
(Prop. 8
FL.AP
(F,)) s N2 (IV N252
LBa8s NQ
+
LLANNs NQQ
FL-RR
(Prop. g
(Fr))² x Na² Na> [V))(,,)) N2²
(NN
LPo8c NQ
+
LRow
NQ
FL.-GraB
(0,)² $ (fp-1)² + (N² + a²) [
LFut(ly - Fae)
(
RoBe NQ
$
Lo
(Prop. 10
+
NO
Wang and Ji 2022]² 's Theorem 3.1. It uses a stronger assumption, equivalent to Assumption 3 with a = 0. For clearer comparison with other bounds, we keep "N" in both numerators and denominators in the bounds of FL.-AP.
For FL-GGraB, 7. = + 12 (1 + a) Toge
Our unified framework covers regularized- pitiiizdddpattiiaattion FL with AP (FL-AP), with RR (FL-RR) and with GraB (FL-GraB). They correspond to AP, RR and PairGraB in SGD, respectively. In particular, we propose FL-GraB (see Appendix[C) by replacing the true gradients in GraBs with the pseudo-gradients (that is. p in Algorithm 2 of the local objective functions generate the "good" permutation as the training order of clients. The key results are in Table 4
Analysis of FL-GraB. See Table 4 The main difference (in convergence rates) lies in the last term. The upper bound of FL-GraB O (((N))) )$) dominants those of the other algorithms in terms of the number of epochs and the number of clients N. This conclusion is aligned with that in SGD. Notably, the changes (from oy to pg. and from true gradients to greudo-gradeents make the analysis
of FL-GraB more complex than that of PairGraB in SGD.
Experiments
In this section, we use the following simulated experiments to validate the theory. Refer to Lu et al. [2022a] and Cooper et al. (2033 for the experiments of SGD real data sets; refer to Appendix II for the experiments of FL on real data sets. The details of the experiments can be found the code
available at https: /ttp///ggtttttt wetthub.ccm/iinn
Spocho
Epodto
Spocio
Ssedt
Figure 1: The experiments on simulated data. Shaded areas show the min-max values across 10 different random seeds. The left two figures are for SGD; the right two figures for FL. For both SGD and FL, is set to be the same for the algorithms; N = 1000. For FL, K = and S = 2.
We use the one-dimensional functions (x) = ((0.5 an) 1xc0 + a, (x20) x2 + b, as the local objective functions. We model a, (0.5, 1) and b, ~ N0 1) (N is the normal distribution). Here, an and bn control the heterogeneity of the local objective functions. The observations on Figure [ validaaee validate
our theoretical results:
The distance to the optimum (that is, ||x- x*|) and the order errors have the same trend, which validates that the order errors measure the convergence rate.

---

The performances of FlipFlop and RR are close. This does not contradict the conclusion in Rajput al. [2022), which shows FlipFlop is better than RR on quadratic functions, given that the functions used in our simulation are strongly convex but not quadratic.
The performances of PairGraB and GraB close, and better than RR in both SGD and FI..
Conclusion
We study example ordering in permutation-base SGD and client ordering in regularized- participation FL. For SGD. we propose more general assumption (Assumption (2) to bound the order error. Using it, we develop unified framework for permutation-basee SGD with arbitrary permutations of examples, including AP, IP (including RR, FlipFlop) and DP (including GraBs). Furthermore, we develop a unified framework for regularized participation FL with arbitrary per- mutations of clients, including FL-AP, FL-RR and FL-GraB.
eegularized-partciiaatoo
Limitations and possible future directions: First, explore new algorithm for SGD (no new algorithms are proposed for SGD in this work). Second, extend the framework to more practical scenarios for FL (our theory is for FL with regularized participation). Third, study example ordering in local updates for FL (we use GD as the local solver). Forth, explore the combination of permutation- based SGD and other algorithms (see Appendix for an example combining permutation-base SGD with online learning).
Acknowledgments and Disclosure of Funding
This work was supported in part by the National Natural Science Foundation of China under Grants 62371059 and 62571297, in part by the Fundamental Research Funds for the Central Universities under Grant 2242022k60006, and in part by the Shenzhen Science and Technology Program under Grant 1
We thank the anonymous Reviewers of ICML 2025 and NeurlPS 2025 for their insightful sugges- tions.
10

---

References
Durmus Alp Emre Acar, Yue Zhao, Ramon Matas, Matthew Mattina, Paul Whatmough, and Venkatesh Saligrama. Federated learning based on dynamic regularization. In International Con- ference on Learning Representations (ICLR), 2021.
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: Optimal rates without compo- nent convexity and large epoch requirements. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Ryan Alweiss, Yang Liu, and Mehtaab Sawhney. Discrepancy minimization via self-balancing walk. In ACM Symposium on Theory of Computing (STOC), 2021.
Aleksandr Beznosikov, Sergey Samsonov, Marina Sheshukova, Alexander Gasnikov, Alexey Nau- mov, and Eric Moulines. First order methods with Markovian noise: from acceleration to varia- tional inequalities. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
Léon Bottou. Stochastic gradient descent tricks. In Neural Networks: Tricks of the Trade: Second Edition. 2012.
Xufeng Cai and Jelena Diakonikolas. Last iterate convergence of incremental methods and applica- tions in continual learning. arXiv preprint arXiv:2443. 06873, 2024.
Xufeng Cai, Cheuk Yin Lin, and Jelena Diakonikolas. Tighter convergence bounds for shuffled SGD via primal-dual perspective. Neural Information Processing Systems (NeurIPS), 2024.
Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. International Conference on Machine Learning (ICML), 2023.
Jiseok Chae, Chulhee Yun, and Donghwan Kim. Stochastic extragradient with flip-flop shuffling & anchoring: Provable improvements. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Towards understanding biased client selection in federated learning. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2022.
Yae Jee Cho, Pranay Sharma, Gauri Joshi, Zheng Xu, Satyen Kale, and Tong Zhang. On the con- vergence of federated averaging with eyclic client participation. In International Conference on Machine Learning (ICML), 2023.
Feder Cooper, Wentao Guo, Khiem Pham, Tiancheng Yuan, Charlie Ruan, Yucheng Lu, and Christopher De Sa. Coordinating distributed example orders for provably accelerated training. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
Luke N Darlow, Jlliot Crowley, Antreas Antoniou, and Amos J Storkey. CINIC-10 is not ImageNet or CIFAR-10. arXiv preprint arXiv:1810.08:: 180.003555, 2018.
Yury Demidovich, Petr Ostroukhov, Grigory Malinovsky, Samuel Horváth, Martin Takáč, Peter Richtárik, and Eduard Gorbunov. Methods with local steps and random reshuffling for generally smooth non-convex federated optimization. In International Conference on Learning Represen- tations (ICLR), 2025.
Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. International Conference on Machine Learning (ICML), 2019.
Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. In International Conference on Machine Learning (ICML), 2023.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 2013.
Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of SGD: Variance reduc-
tion, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
Eduard Gorbunov, Filip Hanzely, and Peter Richtarik, Local SGD: Unified theory and new efficient methods. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2021.
11

---

Nick Harvey and Samira Samadi. Near-optimal herding, In Conference on Learning Theory (COLT), 2014.
Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends@ in Opti- mization, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Samuel Horváth, Maziar Sanjabi, Lin Xiao, Peter Richtárik, and Michael Rabbat. FedShuffle: Recipes for better use of local work in federated learning. Transactions on Machine Learning Research (TMLR), 2022.
Rustem Islamov, Mher Safaryan, and Dan Alistarh. AsGrad: A sharp unified analysis of asynchronous-SCn algorithms. In International Conference on Artificial Intelligence and Statis- fics (AISTATS), 2024.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 2021.
Sai Pranceth Karimireddy, Satyen Kale, Mchryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning (ICML), 2020.
Donghwa Kim, Jaewook Lee, and Chulhee Yun. Provable benefit of random permutations over uni- form sampling in stochastic coordinate descent. In International Conference on Machine Learn- ing (ICML), 2025a.
Yujun Kim, Jaeyoung Cha, and Chulhee Yun. Incremental gradient descent with small epoch counts is surprisingly slow on ill-conditioned problems. In International Conference on Machine Learn- ing (ICML), 2025b.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized SGD with changing topology and local updates. In International Confer- ence on Machine Learning (ICML), 2020.
Anastasia Koloskova, Nikita Doikov, Sebastian U Stich, and Martin Jaggi. On convergence of incremental gradient for non-convex smooth functions. In International Conference on Machine Learning (ICML), 2024.
Alex Krizhevsky et Learning multiple layers of features from tiny images. Technical report, 2009.
Junyi Li and Heng Huang. Provably faster algorithms for bilevel optimization via without- replacement sampling. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-IID data. In International Conference on Learning Representations (ICLR), 2020.
Yipeng Li and Xinchen Lyu. Convergence analysis of sequential federated learning on heteroge- neous data. In Conference on Neural Information Processing Systems (NeurIPS), 2023.
Yipeng Li and Xinchen Lyu. Sharp bounds for sequential federated learning heterogeneous data. Journal of Machine Learning Research (JMLR), 2025.
Zijian Liu and Zhengyuan Zhou On the last-iterate convergence of shuffling gradient methods. In International Conference Machine Learning (ICML), 2024.
Yucheng Lu, Wentao Guo, and Christopher De Sa. GraB: Finding provably better data permutations than random reshuffling. In Conference on Neural Information Processing Systems (NeurIPS), 2022a.
12

---

Yucheng Lu, Si Yi Meng, and Christopher De Sa. A general analysis of example-selection for stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2022b.
Grigory Malinovsky, Samuel Horváth, Konstantin Pavlovich Burlachenko, and Peter Richtárik. Fed- erated learning with regularized client participation. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities workshop at ICML 2023, 2023a.
Grigory Malinovsky, Konstantin Mishchenko, and Peter Richtárik. Server-side stepsizes and sam- pling without replacement provably help in federated optimization. In Pruceedings of the 4th International Workshop Distributed Machine Learning, pages 85-104, 2023b.
Grigory Malinovsky, Alibek Sailanbayev, and Peter Richtárik. Random reshufiling with variance reduction: New analysis and better rates. In Uncertainty in Artificial Intelligence (UAI), 2023c.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effcieent learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Random reshuffling: Simple analysis with vast improvements. In Conference on Neural Information Processing Systems (NeurIPS), 2020.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. In International Conference on Machine Learning (ICML), 2022.
Amirkeivan Mohtashami, Sebastian Stich, and Martin Jaggi. Characterizing & finding good data orderings for fast convergence of sequential gradient methods. arXiv preprint 200.08,20,.01888, 2022.
Dheeraj Nagaraj, Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning (ICML), 2019.
Lam M Nguyen, Quoe Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten Van Dijk. A unified convergence analysis for shuffling-typ gradient methods. Journal of Machine Learning Research (JMLR), 2021.
Francesco Orabona. A modern introduction online learning. arXiv preprint 2019.
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGI) without replacement. In International Conference on Machine Learning (ICML), 2020.
Shashank Rajput, Kangwook Lee, and Dimitris Papailiopoulos, Permutation-based SGD: Is random optimal? In International Conference on Learning Representationss/CLR, 2022.
Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Kon- stantin Pavlovich Burlachenko, and Peter Richtárik. Federated optimization algorithms with ran- dom reshuffling and gradient compression. In Federated Learning and Analytics in Practice: Algorithms, Systems, Applications, and Opportunities workshop at ICML 2023, 2023.
Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Kon- stantin Pavlovich Burlachenko, and Peter Richtárik. Don't compress gradients in random reshuf- fling: Compress gradient differences. In Conference on Neural Information Processing Systems (NeurIPS), 2024.
Itay Safran and Ohad Shamir. How good is SGD with random shuffling? In Conference on Learning Theory (COLT), 2020.
Itay Safran and Ohad Shamir. Random shuffling beats SGD only after many epochs on ill- conditioned problems. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
Samuel L. Smith, Benoit Dherin, David Barrett, and Soham De. On the origin of implicit regular- ization stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2021.
13

---

Zhenyu Sun, ziyang zhang, Zheng Xu, Gauri Joshi, Pranay Sharma, and Ermin Wei. Debiasing federated learning with correlated client participation. In International Conference on Learning Representations (ICIR), 2025.
Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client par- ticipation. In Conference on Neural Information Processing Systems (NeurIPS), 2022.
Shiqiang Wang and Mingyue Ji. A lightweight method for tackling unknown participation statistics in federated averaging. International Conference on Learning Representations (ICLR), 2024.
Guanghao Wei. StrB-samplerr Optimal permutation- based SGD data sampler for PyTorch. arXiv preprint arXiv:2309. 16809, 2023.
Max Welling. Herding dynamical weights to learn. In International Conference on Machine Learn- ing (ICMI.),00)
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker partici- pation in non-IID federated learning. In International Conference Learning Representations (ICLR), 2021.
Hansi Yang and James Kwok. Joint gradient balancing for data ordering in finite-sum multi-objective optimization. In International Conference on Learning Representations (ICLR), 2025.
Hengxu Yu and Xiao Li. High probability guarantees for random reshuffling. In NeurIPS 2023
Workshop Heavy Tails in Machine Learning, 2023.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Open problem: Can single-shuffle SGD be better than reshuffling SGD and GD? In Conference on Learning Theory (COLT), 2021.
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch local SGD with shuffling: Tight con- vergence bounds and beyond. In International Conference on Learning Representations (ICLR), 2022.
Dun Zeng, Siqi Liang, Xiangjing Hu, Hui Wang, and Zenglin Xu. FedLab: flexible federated learning framework. Journal of Machine Learning Research (JMLR), 2023.
14

---

Appendix
A Related Works
A.1 Related Works
A.2 Reformulating Existing Convergence Rates Our Setting
B Notations
20
Algorithms
C.I Preliminaries of GraBs
C.2 Implementations of GraBs
D Helper Lemmas
25
Theorem
E,
Proof of Theorem
Special Cases in SGD
F.1
Arbitrary Permutation (AP)
F.2
Random Reshuffling (RR)
F33
FlipFlop
36
F.4
One Permutation (OP)
F.5
GraB-proto
38
F.6
PairGraB-proo
40
F.7
GraB
40
F88
PairGraB
F.9
Refinement of the High Probability Bounds from Q5 to
48
G Theorem
2
49
G.I Order Error in FL
G.2 Proof of Theorem
50
G.3 PL Condition
H Special Cases in FL
56
H.1 FL-AP
57
H.2 FL-RR
58
H.3 FL-GraB
59
I Experiments
J Additional Extensions of SGD
J.1 Results
65
J.2 Proofs
66
K Additional Extensions of FI
70
K.1 Results
70
K.2 Proofs
L Permutation-based SGD and Online Learning
75
15

---

A Related Works
A.1 Related Works
Convergence analyses of permutation-basee SGD. Up to now, there have been a wealth of works
analyzing the convergence of IG, SO and RR (the most classic permutation -aasettttttt---dddddddee SGD algorithms):
Nagaraj et al. [2019]. Ahhn et al. [2020), Mishchenko et al. [2020), Nguyen al. [2021), Yun et al.
2021 Yu and Li | 2023). Cai and Diakonikolas [2024), Liu and Zhou [024] and Koloskova et al.
[024] analyzed their upper bounds and [afraa and Shamir [2020). (Safran and Shamir [2021] Ra-
jput et al. [2020), Yum et al. [022]] Cha et al. [0233 and Kim et al. [2025b] analyzed their lower
bounds. There are also some works analyzing their variants [Mishchenko et al. 2022; Malinovsky
ctt al. 2023c; Liu and Zhou 2024; Cai et al.,
2024 Kim et al. 2025a] especially in the FL set-
tings Mishchenko et al.
2022 Yun et al.
2022
Horváth et al. 2022 Sadiev al. 2023 2024
Malinovsky et al. 2023b Li and
Lyu 2023
2025
2022b Mohtashami et al. 2022 started to explore the other permutation- based SGD algorithms beyond the simple IG, SO and RR. Rajput al. [2022] proposed the FlipFlop variants (of IG, SO and RR), and proved that these FlipFlop variants are better than their corresponding original algorithms on the quadratic functions. In this paper, we only stud-
Several works [Rapuut et al. 2022: Lu et al.
ied the FlipFlop variant of RR, introduced in Appendix H3 Recently, Chae et al. (0024) extended the FlipFlop algorithm to stochastic extragradient methods for convex-concave objective functions. Lu et al.] (2022b) and MMohtasaami et al. 2022) proposed the Greedy Ordering algorithms to select the examples greedily to minimize the order error. However, the Greedy Ordering algorithms lack theoretical justification and suffer from non-trivial memory and computation overhead (Lu et al.] 2022a Lu et al. 2022a] found that the goal to minimize the order error is aligned with the goal of
herding WWlling 2009]. and proposed GraB based on the theory in Harvey and Samadi (2014) and
Alweiss et al. [2021]. PairGraB first appeared in the public code of of al. [2022a], and was later
Formally introduced in Cooper et al. [202)] GraB has also been applied in distributed optimization
(not FL) [Cooper al. 2023 and multi-bjjective optimization (Yang and Kwok 2025].
The most relevant works are the unified analyses of permuration-based SGD Lu et al., 2022b Mohtashami et al. [2022] Koloskova et al. 2024). They all rely on Assumption (they may consider an interval of arbitrary length, not necessarily an epoch); this assumption has been widely adopted
in the subsequent works [Islamov et al. [2024] Li and Huang 2024] for other settings beyond this
paper. See Scction
2 for the comparison with Lu et al. [202bb and and et al. 2024
Convergence analyses of FL with regularized client participation. The convergence of vanilla client participation pattern (the selection of clients across different rounds are independent) has
been analyzed in the early works [Li et al. 2020 Karimireddy al. 2020 Yang et al.) 2021). The
convergence of regularized client participation pattern [Eichner et al., [2019] was initially analyzed in Wang and Ji| [2022]. Cho al. [2023]. Malinovsky al. [2023a] and Demidovich et al. [2025),
where Wang and Jil [022] and Cho et al.
[2023] considered patllaiized-patccppattoon FL with AP (FL-AP) and Malinovsky et al. [2023a] considered
partiiipitpaiiiiiiatiionnn FL with RR (FL.RR).
This work aims to develop a unified framework that includes these cases. See Tables 2 and [
for the
comparison with Wang and Ji (2022). [Coo et al. (2023) and Malinovsky et al.] [2023a] Importantly, this work focuses on client ordering in FL with regularized participation, which is different from
the studies of FL with arbitrary participation [Wang and Ji 2022 2024 Sun et al. 2025 and client
sampling [Cho et al. 2022
Horváth et al. 2022
Assumption 2 closely resembles the assumptions used in Gorbunov et al. contexts.
2020 2021 1
in different
A.2 Reformulating Existing Convergence Rates in Our Setting
In the main body, to facilitate comparison, we have reformulated the existing convergence rates to fit our setting. Here, we provide the details of how these rates are reformulated.
The rates from Lu et al. 2022b]. We reformulate the results of et al. [002bb as the convergence rates for AP and RR reported in Table
The correspondence between Lu et al. (022b] 's notation and ours is as follows: T in Lu et al. [2022b corresponds to NQ this paper; I. corresponds to T.; A corresponds to Fo: A corresponds to 5; B corresponds to o; corresponds to N; a corresponds to ?
16

---

AP. Substituting the results of Lu et al. [2022b]'s Proposition into Lu et al. [202bb] s Theorem 1, and using the correspondence, we obtain
LAC 3
Prep 1 = [AAAA
T T= δ
where B set to for comparison (implying that 0). This complexity (number of iterations to achieve accuracy E) is equivalent to the convergence rate of Ô (( (L
Based on
the notation correspondence, we obtain the rate of Ô (( (( 55) which matches the error term
(the last term) the convergence rate of AP in Table The constraint of the step size for AP not clearly given in Lu et al. [20226]. So, for the optimization term (determined by the constraint of the
step size), we use the one recovered by Koloskova et 2024 Table 1].
RR. Substituting the results of Lu et al. 2022b]'ss Proposition 3 into Lu et al. [022b]'s 's Theo- rem 1, following the steps as those in AP, using the constraint S I. (that is, ? S AN in our setting) with our Lemma] [ and using the notation correspondence, we can obtain the rate of LF
L.oo/N
NQ
The rates from Koloskova al. [202]]. We reformulate the results of Koloskova et 2024 as the convergence rates for AP and RR reported in Table and the rate for classic SGD in Table
The correspondence between Koloskova et al. 2024] 's notation and ours is follows: in Koloskova et al. [2024) corresponds to L in this paper; Fo corresponds to Fo; T denotes the number of iterations and corresponds to NQ; n corresponds N; ØSGD corresponds to
Using the notation correspondence, it is convenient to translate Koloskova et al. (0044 bounds into ours. In fact, Koloskova et al. 20244 gave the same rate for IG, SO and RR (their Examples 3.2, 3.3 and 3.4). We note that this rate also applies to AP.
The rates from Lu et rate for GraB.
2022a We reformulate the results of Lu et al. 2022a as the convergence
In the proof of Theorem 3 in Lu al. 2022a we can find the inequality
K
(wwi S + K
a2 + 122
VV
<
anK
The correspondence between Lu al. [2022a]'s 's notation and ours is as follows: f(wi) f" in Lu et al. [2022a] corresponds to Fo in this paper; a corresponds to 7: n corresponds to N; K corresponds to Q; L, Loo and Lg correspond to L, Loo and L2,00 respectively, s corresponds to s: A corresponds to C; t >k [[+/()))]] corresponds to क E [x,)( Using the notation correspondence, we obtain
Fo ( Σ 1=
(7NQ + 22 N2
N2
2 222
Q
Then, using the constraint of the step size in Lu al. [022a] 's Theorem 3, and tuning the step size with Lemma can obtain the same rate this paper.
The rates from [ooper et al. [023). We reformulate results of Cooper al. [023 as the convergence rate for PairGraB. CD-GraB [Cooper et al.) 2023) is an extension of PairGraB, For Theorem 2, after setting a 0 and m = and using the notation correspondence (that is, Fi
ct al. 2022a] corresponds to Fb in this paper, L to L, Los to Loo. L2,00 to L2,00, T to Q. A C and to N),
obtain the same rate this paper.
The rates from Cho et al. 2002).. We reformulate the results Cho al. 2023 as the convergence rates for FL-AP reported in Table 2
After comparing Cho et al. 2023 Algorithm I (their LocalSGD case) with ours, we find that their setting is more general than ours, need to adapt their results to match ours: Setting N M
17

---

and a = 0 in their Theorem 2 gives
E [(w((k00)- - Fr = =0 (
K (F(w(o.0)) )
Fr)
k KK
a²
R²F²
MT²
μT
In addition, comparing their model update rule given in Section 3 (Problem Formulation) and Equa-
tion (37), we notice that a factor of I is missing in Equation (37). The model rule of Equation (37) is used in their Equation (54), causing the missing of the factor of N² in the term caused by local updates in their bounds. As result, obtain
N
K (F(w1000)) FT)
K
02 N2
F(w(K.0)) - F
+ 2T +
MT
MN
where we highlight the missing factor 2 in red.
After the adapting, the correspondence between perween[Cho et al. [2023]'s notation and ours is as follows: K Cho et al. 2023) corresponds to N in the main body of this paper; F(w((.0)) F corre- 3
N sponds to Fq; F(w():)) - F corresponds to Fo: T corresponds to S Q; N corresponds to S; M
corresponds to N; both a and correspond s. Using the notation correspondence, we obtain
E B Ō Fo L L²s² NQQ NANQQ A
+
+
The rates from Malinovsky al. 2023a]. We reformulate the results of Malinovsky al. [2033a as the convergence rates for FL-RR reported Table
Malinovsky al. 2023a] uses RR as the local solver while this paper uses GD, need adapt their results to fit our setting: Setting a, = ō. in their Theorem 6.1 gives
22
LMNN2 C2
E E| x.1 1250 (1 (1-71) yu) NRT 110 xx11+
o.
LN LNN?
1
$ (1 - (a11
(1-1
NRT ||:0 x=1 + 72
LMN
C TF
+ +2 +
S Eexp (-7uNN |1:0 =r.12 + LMN 1
C + - LN
Then, using
|| xx s f(x) - f(x.) s _ - 1=1 2 we obtain
(1(00) exp 7 1
LMN 1
f(oT)- - f(x+) x /
T 72 LN C2
P
P
After the adapting, the correspondence between Malinovsky al.
2023a 's notation and ours is as
follows: I. in Malinovsky et al. [2033a] corresponds to in this paper; corresponds to μr f(rr) f(x,) corresponds to Fr; f(x) f(x.) corresponds to Fo: y corresponds to 7: corresponds
to S; M corresponds to N; Ncorresponds K; R corresponds to N. T corresponds to Q; o? corresponds to c. Using the notation correspondence, we obtain
S
L Fo exp (-MUKN 1 00) + Fq < P
L2 +22 +7
ns²
In addition, we need the constraint the step size 7 S et al. 2020 Lemma 15), we obtain the reported bound in Table
J. Then, tuning the step size with Koloskova
The rates from Wang and Ji [022]. We reformulate the results of Wang and Ji 2022 as the convergence rate for FL-AP reported Table and the rate for FL with independent participation in l
Wang and Ji 2202]; 's framework covers multiple participation patterns (including the regularized participation and independent participation), and uses SGD as the local solver.
18

---

For regularized participation, we set 8(P) = 0 (see)
Wang and Ji 2022 's Proposition 4.2) and ø 0
in Wang and [0022 Theorem 3.1, which gives
min E [V =
F MIT ( -
+
The correspondence between Wang and Ji] [022 notation and ours as follows: FF Wang and
Jil [022) corresponds to Fo in this paper; " corresponds to y 1f corresponds to 7); / corresponds to K; P corresponds to N. T corresponds to N Q: both 3 and & correspond to (see Wang and Ji [
g
2022 Section 4.1, Discussion on B and v: Decomposition of Divergence); min, E
corresponds to min, E [V Using the notation correspondence, we obtain the bound
( + +2
Fo MKKN
min E [V 0
+ $2
where y, denotes the model parameter vector in iteration t (see Appendix K). Then, setting 1)
and tuning the step size with Lemma we obtain the reported bound in Table 2
For independent participation, we set ((P) O O N²d") (see Wang and Ji [2022] 's Proposition 4.7)
and a 0 in Wang and Ji 2222]'ss Theorem 3.1, which gives
min E
| fx =
- + +
F (T/TT
N p
Using the notation correspondence, we obtain the bound
V f()))) ( Fo (SHRN +
Nºs² P
min E
For comparison, we set 17 = 1 and P= P S). This gives
min
| = WKNJQ
Fo
+ + + t N222
( S)), there is non-vanishing term in Wang and Ji [202 when 7 + O. Then, following the same steps as Proposition 14 tuning the step size we obtain
Notably, under the same setting (1/ = and P O P
with Lemma
min E [IVS(NI Ô
LFo T
LFos T
(LEON2
+ +
+
ST
The rates from Yang et al. [2021]. We reformulate the results of Yang et al. [022] as the conver- gence rate for FL with independent participation in Table
Yang et al. 2021 uses SGD the local solver while this paper uses GD, so we adapt their results to fit out setting: Setting oz. in Theorem (Strategy 1) gives
[ (1 fo f. + LKMLL [E[2]
K3mi L
min
oe + K2
n oc.
MLLTT n
Then, using NL L S obtain
S fo - fm
LKMML 2
K2 L2 0G
[| r
min
OG 12n
mTKT n
n
Jo fa
LKYML 0g + K2 12
Mi KT
where in the last inequality, the forth term is subsumed into the third term the right hand side.
The correspondence between Yang et al. 2021 's notation and ours is as follows: fo - S. Yang al. 2021 corresponds to Fo in this paper; 7 corresponds to y n corresponds to 7; K corresponds
19

---

to K; T corresponds to N 3 L corresponds to L; n corresponds to S; corresponds to min [[IV) corresponds to min, E f(vell Using the notation correspondence, we obtain
Fo TA JQ
22 MLLK x2
min R [VV
Setting 77 1 and tuning the step size with Lemma (mLK x and 7LK S 1), obtain
$
LFo T
LFos T
[Foos*
min E
+
+
ST
B
Notations
Table 5: Summary of key notations.
Notation
Description
Q
Number of epochs.
Number local objective functions.
Number of local steps in FL..
S
Number of participating clients in each round in FL.
μ
Strong convexity constant PI. condition constant. Smoothness constants (see Definition
Lppp'
A, B, D
Constants Assumption and Theorems and Constants in Theorems andd Dimension of the model parameter vector.
B, D
d
a,s
Constants Assumption
G
== V a² [xxxx)]ll + <2; see Equation 5
7
Step size.
7
Global step size (in FL))
Order Error in SGD.
Order Error in FL.
A permutation of {0, N -1. It serves as the order examples clients.
(n)
The (n + 1) -h element permutation n.
f
Global objective function.
fn
Local objective function. It represents examples in SGD and clients in FL.
Fo
fxx)) fr.
x
Model parameter vector.
x
Parameter vector after n steps in epoch (in SGD).
Parameter vector after A: local updates in client in epoch g (in FL).
P
Pseudo-gradient of client in epoch q in FL.
Key notations are summarized in Table
Norm. We use II-Il, to denote the Lebesgue p-norm; unless otherwise stated, we use ||-I| to denote the Lebesgue 2-norm.
Set. We let [n] == (1, n for n E N+ and (arhies == {#a E S} for any set S. We let [S] be the size of any
Big O notations. We use S to denote "less than" up to some numerical constants and polylogarith- mic factors, and 2 and x are defined likewise. We also use the big O notations, Ô, O, Z, where O, Ω hide numerical constants, Ô hides numerical constants and polylogarithmic factors.
20

---

for Notations in proofs. For convenience, we will use "T, to denote the n-th term on the right hand side in some equation the following proofs. We will use + mean "add (+)" and then "subtract (-)" the term: + b means b b.
For Assumption we let
Gg = a² V +33
(5)
which gives
V (x₂) Vf(x,)) v a² +
Importantly, is permutation of {0, 1, ..... .V. examples SGD or training orders of clients in FL. Next, we need to define an operation on æ as done in Lu et al. [2022a] Appendix B] and Cooper al. 2003 Appendix C.4]:
1), and it serves the training orders of data
π
(i) = such that x(j) -, i,j E 10, -
represents that the index of in the permutation т is j. where i. {0, N. 1}. This operation will be very useful in Appendices F5 F.6 E.7 F8
H.3
According to the definition,
follows that
(T(i)) j- can be proved as follows: Assume that - (T{))) k + j. Then, according to the definition, we obtain ( = xkk), which implies that = k. This contradicts our assumption. Thus, we have (T(j)) = l j.
C
Algorithms
In this section, we provide more details about GraBs.
C.1
Preliminaries of GraBs
Algorithm 3: Balancing [Awwesss et al. 2021
Algorithm 4: Reordering
Harvey and
Samadi 2014)
Function Balance ((Z,, } ) Initialize running sum s, hyperparameter e Initialize {fn,) for assigned signs
Function Reorder (Tr, fer )== Initialize lists Lepsiiive ()+ Lnegative +
for n O...., N do
for n O...., N do
5
Compute ş + 2 2c
(s.2al
if En +1 then
Assign signs:
Append Tnn) to Lpasitive
En with probability P:
6n f with probability p
Append (n) to Lnegative
Update + s 6n. Zn
concatenate Lpaitives reverse (nngurne))
return the assigned signs (ex)
return the new order T''
Algorithm Basic Balancing and Re- ordering
Algorithm 6: Pair Balancing and Reorder- ing
Function (asicBR(T. {zn -
n=0 m) Function PairBR(T, (Zr J
Centering: (cn 2n m n=
/eenterin:: {c,, 2, m
(en <- Balance (f ((cn) N--1
Compute {di == C2i C21+1 1-0 N
x' Reorder (n., { N-1)
return n²'
{E:] + Balance ((d 1
Compute {r, LN-1 such that
"The mean vector m is used to center the input vectors {z., ) J-1 (Line 2). In most cases, it is the average of the input vectors 1 >>N Zn. except in N the original GraB algorithm, where it is replaced by an estimate the actual average.
E2i = and 62i+1 1 0. O...,,
n Reorder (sT, fen. (N-1) return
"The step of centering not required in practical implementations
21

---

In Section 2.3 we have introduced the key ideas of GraBs. Now, we introduce the concrete GraB algorithms. We start from GraB-proto and PairGraB-prokke where the former is a simplified version of the original GraB algorithm [Lu et al. 2022a], and the latter is a simplified version of PairGraB
algorithm [Lu al. 2022a Cooper et
2023
GraB-proto. Use BasicBR (Algorithm inputs of q. (z.) (xx,) > and V fx(,)) ) for each epoch 9.
as the Permute function in Algorithm | with the
PairGrraB-proto. Use PairBR (Algorithm 6 as the Permute function in Algorithm with the inputs of q. (v))(()) (x,)) and V (x,)), for each epoch q.
The main difference is that GraB-pre -roto uses the basic balancing and reordering algorithm (BasicBl) while PairGraB- proto uses the pair balancing and reordering algorithm (PairBR). The advantage of PairBR is that it is free of centering the input vectors in the practical implementation. As shown in Algorithm (Linee 3 it balances the difference of two centered vectors, which equivalent to balancing the difference of the two original vectors as the mean vectors are canceled out:
d (Z2 m) (221+1 m) Z2 2-1+1
This advantage makes it seamlessly compatible with online algorithms such as SGD, Notably, com- pared with the original GraB and PairGraB algorithms, whose implementation details are deferred to Appendix C.2, GraB-proto and PairGraB- Buprott are impractical in computation and storage, however, they are simple, and sufficient to support our theory.
Next, we briefly introduce the original GraB and PairGraB algorithms.
GraB. Use BasicBR (Algorithm 5) as the Permute function in Algorithm with the inputs of Ty. (Vgnz(m)) (xx)))= 1- W-1 and
N En= V (m)) (x)-)) for each epoch
PairGraB. Use PairER (Algorithm 6 as the Permute function in Algorithm with the inputs of Tgg [V (xx) ( and
N Enn (xx((n)(x{), for each epoch g.
They replace (n, (x,) in their prototype versions with the easily accessible V (n) (x.), re- ducing the unnecessary computational cost. In addition, for GraB, to overcome the challenge of centering the gradients in the BasicBR algorithm. GraB uses the average of the stale gradients as the estimate of the actual average of the fresh gradients, to "center" the (fresh) gradients. This trick not required for PairGraB. See the implementation details in Algorithms and IT
In FL, we propose regularized pattiiiepppatiiittattonn FL with GraB, which uses the meuuo-gradientt {p" J== to generate the permutations.
FL-GraB, Use PairBR (Algorithm 6 as the Permute function Algorithm 2 with the inputs of Ty. [p:)a=d and N Σ p for each epoch q.
The main differences of GraB algorithms are summarized in Table
Table 6:
The main differences of GraB Algorithms.
Algorithm
Permute
Inputs of Permute (in epoch ④)
GraB-proto (Prop.
BasicBR
Ty. {V (n)(
mm E
(n)(()((x)))
PairGraB--rrot (Prop.
PairBR
Ty. ( (n)
(x,) | En=
GraB (Prop.
BasicBR
Tg. V (T,(())
V V (mj
PairGraB (Prop.
PairBR
Tg. V (m,(
(x N-1
1 N EN=I
V fm) (x,))
FL-GraB (Prop. 10
PairBR
Ty. (p:)
ENNI1 P
C.2
Implementations of GraBs
The practical implementations GraB are provided in Algorithms and TO The implementation of PairGraB is provided in Algorithm| II The implementation of FL-GraB is provided in Algorithm 12
22

---

As done in Lu et al. [202aa] and Cooper et al. (0023). we use Algorithm for the theories in this paper, while we use Algorithm for the experiments Appendix
Notably, Algorithm
9 (the original algorithm in Lu al. 2022a
Algorithm 4J) logically equivalent
to Algorithm 10
Compared with Algorithm 9 which updates the new order at the end of each
step (Lines 11
Algorithm T0 generates the order at the end of each epoch (Line 12 In
fact, in Algorithm
10 we can reorder the examples for multiple times with the same signs (see Line 12. which may be useful in practice [Wei 2023 Similar variants also be formulated for Algorithms and
Algorithm 7: Assign signs.
Alweiss et al.
Algorithm 8: Assign signs without normal-
2021
ization. [Lu at. 2022a| Algorithm 5]
Function AssignSign z, o
Function AssignSign 2)
Compute ÿ + 2
if ||s + 2|| < ||s x|| then
Assign signs:
+1 with probability p;
c <- with probability 1 7
é 6 return
return e
is a hyperparameter. Lu 2022a
Theo-
rem 4].
Algorithm 9: GraB [Lu al. 2022al Algorithm 4]
Input: Xo: Output: {x,]
Initialize + 0, m 0, Mstale <
for q 0. 1,... 1...., Q 1 do
+- 0: Maale f- m; m 0: O,
for 0, 0,,,, N
do Compute the gradient [sn(n)((())
Update the parameter: xx+ +- x" ? VVS (x,(m)(x)))
Update the mean: m t- m + N V J (m) (xx)
Center the gradient с - V (m) (x") Matale
Assign the sign: + AssignSigm (s, c)
10
Update the sign sum: -- s + [n,(m(
11
if = +1 then
(() + To (1));
+ 1.
13
else
Z 1 (r) f- n., (n)) f- r- Update the parameter: Xy+1 +- x
N
15
23

---

Algorithm 10: GraB
Input: To. Xo: Output: {xg}
Initialize <- 0, m +- 0. Msale <- 0
for q = ,,.... Q do
for 0: Mauue <- m: m + 0;1 < O N -1
N.
do
Compute the gradient V. (xg)
Update the parameter: x x
x V (x,(m)(()))
Update the mean: m m + N V fr, (n) (xx)
Center the gradient с (n) xx) masale
Assign the sign: E, f AssignSign (s, c)
Update the sign sum: - s + en (x,)
11
Update the parameter: X,+11 X
1g+1 f Reorder (TTp. (en [ N--1
12
"ee can reorder the examples for multiple times with the same signs in this step.
Algorithm 11: PairGraB
Input: To. Xo: Output: {x,}
for q 1. do
2. S 0,d-0.1=0rr+
for n O.
4
Compute the gradient V (n) (x
Update the parameter: x; if (n + 1) mod 2 = then
x 7V fr (m)
Compute the difference:
V=,(nn-1) Vin((n))
Assign the sign: e + AssignSign (s, d) Update the sign sum: < s d
if +1 then
Tq+1 (1) + n. (n); + 1+1
12
k t (n 1); + r
else
g (1) - (n - 1);1 ++
g (r) f- (n); t--1
16
Update the parameter: X,+1 t x
24

---

Algorithm 12: FL-GraB (Server-side)
Input: To. Xo: Output: {xg}
for 0. 0.. 0, - 0. N-1 for n 0,.,,.,,... -. do
do
s
Get the sneudo-gradien P Σ k=
X-1
V (x),))
/+ Update the parameter */ if (n++1) mod S = then w w S-1 P if (n++1) mod 2 then
5
/* Balance */ Compute the difference: d t- (n-11= fn,(1))
Assign the signs: <- AssignSign (s, d)
10
Update the sign sum: f s e order */
/* Update the
11
if c +1 then
g c (n); 1
To+1 (r) f ( 1); r + --1
14
else
go+1 (1) t no ( - 1); - ++1 (r) t (n); t r-1
16
/* Update the parameter */
17
Xq+1 X, 77 (x, w)
D Helper Lemmas
Lemma 1. For any parameters ro > 0, T > 0, c >
0 and y S a. there exists constant step sizes
min { 1 (3r)
{1 I d such that
1
Vr = 7
ro
+ oo² 1
dro
c
dro
c
T
T
T
T
Proof. If 1 < (c))
.choosingg 7 = gives
d
V = dra
drn
ctri
T
d
T
T
[20) < 7. choosing = (= gives
dru
ct
r
ctro
ctrr
V
2
T
d2
T
T
T
Thus,
V v dro
c3r
dro
et
+
2
0
T
T
T
Lemma 2. For any parameters To > 0, T >
0, c >
0
and y
- 1/2
there exists constant step sizes
mim
{ 1
(are)
< 1 such that
d.
To
dro
c2 ro
drg
2 r
+ +
S
+
T
T
T
T
25

---

Proof.
If 3 S
ro. cT
choosing 7 = gives
d
1 = dro
c
dro
C2
2
+
+
T
T
T
Po 3 27
< 2.
choosing
= (
gives
v
dro
+
c
0
ctro
0
2
c
T
d2
T
T
T
Thus,
dro
c2r
dro
ctro
T S
2
=
0
T
T
T
T
NN and a permutation π of 10. signs {<n (=) (en E {-1,+11}) by the balancing algorithms (such as Algorithm 3) to the permuted N-1), ). Let nO be the new permutation produced by Algorithm 4 with the impust of the old permulation and the assigned signs {en N Then,
Lemma 3. Consider vectors {za I
1}. Assign the
N-1
vectors under the permutation π (that is, (
1--1
Σ (x(())
1
Σ E (x(i)
Σ
max RE[M]
(()(
max NE(N]
max 2 N
+
Z
1000
00
Furthermore, suppose that the signs
f(n
n= are assigned by Algorithm 3.
N --1
If |f||znllz S for all
n E 10.1,...,,N N
and N-1
2i
E b, then, with probability at least
1
Σ
(z)
max N
Σ 2-) i=0
Ca
2
i=0
where C' 30 log( dN
= O
(lg
dN 8
= (() is from Alweiss et al. 20221 Theorem 1.1].
Proof. This is Lemma 5 in Lu et al
2022a and we reproduce it for completeness.
Let M+ {i E {0, 1........ . N
1}
+13 and M {i {0, 1, ..... N - 13 | = =-1.
Then, for any E (1,2...,NN) N).
n-1
(() +
Σ
4 (m(s)) =
Σ
2x(())
(6)
1=0
(EM++n0.1....n-11
n-1
n-1
Σ
Σ
E (x) =
Σ
2x((1)
t=0
jEM LC..I....n-1)
By using triangular inequality, for any (1,2.... ...,. N}. have
Σ
1
Σ
Zx(i)
2
(3)
+
E
Zz(1))
2
2
n-1
i=0
1=0
n-1
Σ
1
Σ
1
Σ
(i(i
<
2
Z
(i)
+
2
E;
Zz(1))
LEM-nnO.1....o
1=0
t=0
Recall that Algorithm 3 puts the vectors with positive assigned signs in the front of the new permutation and the vectors with negative assigned signs in the back of the new permutation.
Next, we consider the upper bound of Σn' 2x((3)
for all n' E (1,
N}.
26

---

If n'' S M (M+1 denotes the size of M we obtain
E
(x)
max RE[M]
bx(i)
feM.nno........ n- 11
00
n-1
1
Σ (x()
max nE[N]
+ max
4 2 (1)
2
2 nE
If nn' > M+ (M-
denotes the size of Mt), we obtain
n 1
N 1
N-1
Σ (x)
Σ
=
(s)
(i)
t=
N-1
Σ i=
(i)
+
Z (i)
8
Σ
(i)
max N
bm(())
iEM- (1, n0.
20
VA
Z
max WE[N]
Σ
m-1 1
(x(
+ max
1
n-1 1
E Bz(i)
2
2 nE(N
i=0
1=0
Thus combine the two cases and obtain the relation
N-
(0)
1 max
Σ (x(s)
max NE
Σ E
2x(i)
+
Σ
[EIN]
2
NEIN]
1=0
1=0
10
1=0
Using Alweiss et al.
2021
s Theorem 1.1, for all n E [N]. we have
Σ
Σ
Zx(i)
| 112 S Ca.
G (()
m l1
max jE N
max (0............N.II
x
1=0
IIND 2
Then, using
b. obtain the claimed bound.
Lemma 4. Let n., (Zxin) N-1 and &. N-1 Zx(x)) be the inputs of Algorithm and n¹ be the corresponding output. Suppose that mod 2 O. If f|znlll2 S for all n E IU. - 13
and N-1 zi
< b, then, with probability at least 6,
max NN
Σ (x)
S
max Σ (x)()) [N
+ Ca + b.
i=
where C' = 30 log(
dN 28
O (log
(dN)
(1) is from Alweiss et al. 2021
Theorem 1.1].
Proof. This is Lemma 1 in Cooper al. 2023 and we reproduce it for completeness.
We use ? to denote the assigned sign of d
(2)) - (x(2++1) for all j E {0, 1,... N -1): we N
2
use to denote the assigned sign of 2i()) for all E 1, NN 11. Since {d,},- is the input
of Algorithm 3
according to Alweiss al. 2021 is Theorem 1.1, for all / {,,2, ..., 2 ).
d
j0 |d
max
||d]||2
c
max
||d/ll2 - 2Ca,
je jE.0.1....1111
27

---

where the last inequality is because for any j E (0.1.... N - -}},
2
| 2| ||z0(2)) 2z(2i+1)122 - | + ( s 2a. We define 2y and y for E 21,,,....,
21-1
(2)) + 7x(23+1))
Σ xx)()
1=0
1-1
1-1
= Σ (2)))(2 + (2)+12+(2++1)
Σ
(3/2((2) - -(2((2541) = Σ jdd
=
0=
1=
1=0
Let M {i E {0, 1, ..... N - 13 4 = +13 and M = {i =0011 ........,N - 13 G -13.
Then, for all / E (1.2....
]. it follows that
Σ
xix
Σ
1-1
(1++))22(22)) + (1- - -3, -2))2((2++1)) = =2" + /0,,
1
2
NEM ( 21-3
1=0
Σ
zi)
1 1-1
((1 - Ej (Z(12) + (1+ =
2 2 y
1
2
LEM............. 21
j=0
By using the triangle inequality, for all / E {1,2,....
N 2
). we obtain
1
1
(()
S
|101
+
11 loo
2
2
iE LEM..oO......21111 11
21 Σ
I-1 1
1
(a)
+ 2
{j
dj
2
i=0
00
1=0
80
21-1
S 2
1
Σ
Ca,
8
21 Σ
Σ
bm((t)
S -
1
(a(())
+ +Ca.
iEM (EM-n((1,....I-I1)
1=0
Next, we consider the upper bound of >X= (s) for all 1' E (,,2....,N) Recall that Algorithm 4 puts the vectors with positive assigned signs in the front of the new permutation and the vectors with negative assigned signs in the back of the new permutation.
If l' {1.2..... ... N), ) we obtain
Σ (x)
Σ
( (x((()
10
2/' 1
- 2
1
Σ Zm(()
+ Ca.
8
Note that I' E 21,,,,...,
). then 21' E {2, 22,4,...,NT Thus, we obtain
Z (1)
< max
Σ z (()
+ Ca.
2 ]E[M]
1=0
1=0
28

---

If E N +1, N
,,,,.. we obtain
N-1
N-1
Σ 2 (1)
(i)
(1)
'=!!
N
N-1 1
(1)
+
Σ (1)
1=1
Σ
(1)
Zx(())
i n0..1.0......................0.. (............-111 2
80
N -N-111-1
-1
(N-1)-1
1
Σ 21
2
(1)
Σ
Ej dj
j=
8
8
Note that if 1' E {
+ + 2, (O.2....,NN N 2}. Thus,
N
,,,.., N). then (N - 1') {0, 10.1,....
N
1] and 2(N 17)
2
2
M'
N-
Σ
2 (+)
Zi
max nE[N]
Σ Za(i)
CCa.
i=
00
k=0
Thus, combining the two cases and using
En= 2i
< b. we obtain
Σ (x)
1
Σ (i)i 2=0
+ +Ca
2
nE(N]
i=
which is the claimed bound.
Lemma 5. Let n. {Zx(n)) Ni-1 and 1 -N bz(n) be the inputs of Algorithm and be the
NV mod 0 and S mod 2 If Mn ll S a for all
corresponding output. Suppose that
{0, 1.......N. N 1) and Ei=
zi
s b, then, with probability at least
m-1 |
m
max (5.2........)
Σ (x) 1=0
5
max 2 mE (AEESS2
Σ
2x(s)
+ Ca bb,
where C' = 30 log( 26
dN
O (log
dN
( is from Alweiss et al. 2021 Theorem 1.1].
Proof. This lemma is first introduced in this paper and tailored to FL-GraB.
We use ēj to denote the assigned sign of d, = Zm(25) - Z=(2++1) for all j E {0, 10... N 1}: we use to denote the assigned sign of Bx(() for all E (,, N - 11. Since [d,} N
is the input
of Algorithm according to Alweiss al. 2021 's Theorem 1.1, for all / 21, ..., ).
d
d
max
||dj122
(00. 1-1) d
(E 1-1 1}
max 10.0.......111
||d/l22 $2aa.
where the last inequality is because for any j E 10, 1, N - 1}.
2
| 11 = || - 2x(2i+1112 S
/ + ( 112 22a
2a.
29

---

We define and y for / f1,2...., )
21-1
31
(25) 2x(22+1))
Σ
x1)(
i=0
1-1
51 =
(22))x(2) (2)+12x(2)+1)
Σ
(320((2)) - -((x(21+1) = Σ cdd..
==
1=
1=
Let M ii e {0, 1, ...
...........11. - 1 and M fi (0.1 ...,, N 13 | a -1}.
Then, for all {1.2....
N) follows that
1-1
Σ
(xx(1= = Σ
(11 (7)2((2)) + (1 2g ())
=
2 2 + yi
2
i (00,,....... 21-1
1=0
1-1
Σ
(x(i)
Σ
((1-6 - (z)(z((2) + (1 (1+53 ())22(21++111
= -º 2
2
SEM -60,1 21-1
j=0
By using the triangle inequality, for all E (1, ). we obtain
Σ
Zi(ii
|
1
11
alo
2
2
iE (0..........
21-1
1-1
Σ
Z (t)
Σ
dj
8
j=0
21
<
Z (())
+ Ca,
2
1=0
21-1
Σ
(i)
1
Σ
(a(i)
+ Ca.
2
iEM 21-1
1=0
Next, we consider the upper bound of En' 2x((1)
for all E $,,,, N S}.
If < 5/ J. or equivalently, l' s 3.. s......
N C ...,, N ). then we obtain
2
Σ
(+)
Σ
Zm(1)
S
Σ Z (z)
+ Ca.
i=
(o....n0.......''-
i=0
Then, note that if E S, S......... $ SJ,, which implies that 21' E
NN, then
(x)
<
max 2 me SS,.83S.....
Σ (i)
+Ca.
1=
30

---

If N. 1, or equivalently, 1' E {($ +1) 9.
( +2) S
2 N.. then we obtain
2
N-
N-1
Σ 40
(1)
(+)
i=ll
N 1
N-1
Σ
(0)
+
(t)
i=l'
Σ
(x)
+
(x)(
iEM 2(0.1...,( ((N-)))-)
1((N-1)
(N 1') -
W
(x)
+
xx)
+
1
Σ
{dd]
2
2
1=0
1=0
Note that if I' E { + +1)
(5
2
2...., N). then (N - 11) E (0,
S S, ..... ( - 1) 5 and
2(N (1) E S, ................................ N S}. Thus, we obtain
N-1
Σ (0) 1=0
Σ
(
1
max
2m((1)
+ +Ca
2
3S...
i=0
x
1=0
x
N
1
1
m-1
V
(1)
max
Σ Zm(i)
+ Ca.
2 me mm (S.25,38.....N
The bounds for these two cases hold for all 1' E $,
N g
5), which means that
F'
N-1 1
1 max (5,28,35.....
max (E 9)
Σ (()
S
Σ (
Σ (x)
+ Ca.
2 me
i=0
i=0
100
i=U
x0
Since (5,25,35.....
N 5} C
N
S). then
3
N-1
1
max me (8,2
Σ (t) i=0
max me (5,25,38
Σ
xx((I)
+
Σ
(x)
+ Ca.
i=0
00
Using
NN 23
S b, we obtain the claimed bound.
E
Theorem
E.1 Proof of Theorem 1
We define the maximum parameter deviation (drift) in any epoch g, A, as
A max
- [N[N]
||x;
Lemma 6. LL < 32. the maximum parameter drift is bounded:
32
32
A 31
70, +
N [x,(x))
31
(A,)² < 37² (3,)²
2
2 + 37 N2 [Vxx)))
31

---

Proof. For any [N], it follows that
X
V (xx(
(Vf(()(x))) (x(()(())) + (( - Vx((x) -
v((x())
Σ
V (x)))) (x)
+y Σ
(V V((2?)) -VXx)))))))(()() +
{f(x+)
==
$ 7T
Σ
xx
x 1lpp + 770 ym [
1=0
I + + > V [
Note that this bound holds for any n E [N]. This means
Ag H > N4 + 70 7N IV f(x))l,
Then, using No S 32. we have
32
32
A S 31
, +
7
| (x,))x 1Ip
31
(A,) 2 < 3y (Ø,)
2
+
3 N2
| V
At last, using |x|I, < ||||| for x E Rdd and 2, we obtain the claim of this lemma.
Proof of Theurem
For permutation-basee SGD, the cumulative updates over any epoch y are
Xq+1 Xg
(8)
Since the global objective function f is L-smooth, it follows that
fxx+11) S f(x,) + (Xxx)) Xx+1 - xx) + 2 ||x++1 - xx,1
(9)
Using Equation { obtain fXx(x))
Xg+1 xz)
N-1
= =
V f((x))
V (x())(())
N
n=0
N-1
2
N-1
~
-
N
V V [m (x²)
+ 7
V V (m) (x,) V v((x))
-
n=
==
where the second equality uses y(x,y) ||x| + ||
|| y 2. Using Equation
we obtain
N
[||x,11 x, 1| = ク LN2
fz (r) (x+)
Plugging back the preceding two inequalities into Equation
we obtain
(x S fxx,) + (V (x,, (x+), xx,) + _/2 |x 12 2
N Σ
1 7 [x,(x,))
1 (1
$ f(x,)
V Sa (xx)
n=0
N
+ N
1
Σ
V
N
0=
32

---

Since SLN I 1, we obtain
f(x++1) s f(xg) 1 2 (V) )| +
1
|/
1 N-1
Σ V
(10)
N
Since each local objective function fn is L2,p we have
N W-1 1 V (mn((n)(x)) - -
T3 in 10 = 2
N N-1
1
= N
V (F (5mmt)(Xx))
N
_ 2
L2
2
x
Xx
1
2.
n=0
Plugging the preceding inequality back into Equation 10), we obtain
N-1
[(x++1) S f(x,)
1
+
1/12
Σ
x
x, 111
2
n=0
1
1
S f(xg)
NN
[V 11
2 2 N (4g)²
2
s f(x))
1
N
[V )|
2 23 N (37² (Ø,) + N +3
2
1
3
$ f(x))
NN (1- 37 2 L3 1 N2) [V, )1² + $22²0 و (ō,)²
2
255
S fxx))
N fx,)( 2 + 2v 12 N (ōa)²
(11)
512
where the third inequality uses Lemma
6 and the last inequality uses L22 N S 1 Then, 32'
1(x++1) f(xx) <
255
512 7N
|V + 2- 12 N (Ø,) 2
Average both sides over 9 E (0,,1....,
Q- 1}. we obtain
f(x2) ((xo)
255
Σ
[x 1
1
(12)
7NQ
512 Q
Q
0=0
9=0
Since
(3,)
2 S Ai (3,- ) + A2 (0)-2)² +... Av (
+ Bo { )11 + B1 V VJ 1)] +... By / f( (x DD
we obtain
Q 1-1 1
1
2
1
1
(σ.) 2
<
Q
(1
E A,)
Q
0
1=0
(E B.)
1
Q-1
[V,(,)) 12 +
|
D.
(13)
- A:)
(1- -1-Er A,)
0=0
For (5.) (0))2 c0 1), we have
Q-1
(0))² s B [| 2 +D
Σ
(3.)²
< B Σ
(14)
0=0
33

---

1 Plugging Equation using the condition
14 into Equation
[3 and the resulting inequality into Equation 12 and then
vI 2i A;
VI 2i Ai
7 S min
4
L2,
Ei=
Bi
4
L2, VB
obtain
(x,))l 55. f(x)) -(x0))((xx) f(xQ)
cc. 22. q
vD c
?NQ
where c (1-2%-: A:)
Using f(xo) f(xq) S 5(xx) - f. Fo. we obtain the claimed bound.
At last, summarize the constraints on the step size 7.:
V1- Ei=1 A 1 VI Ei=1 Ai
S min
12.
B 4
L2, VB B
YLN & 1,
222 N 1
32'
1
N <
32'
where the last one from Lemma
6 For simplicity, we use tighter constraint
1
VI-
Ei= A
VI- A
S min
LN'
32L2,,
V Ei
4L2,V
'322,
F Special Cases in SGD
As shown in Theorem I the constraint of relies on the choices of all A, and B, (for E (1.2....,")) w. For clarity, we summarize the constraints of the existing permutation-bast SGD algorithms in Table 7 It can be seen that the choices of A, and B; do not impose stronger con- straints than the existing works [Lu et 2022b a Cooper et al. 2023 Koloskova al. 2024].
Table 7: Specific choices A,, B, and for different algorithms. The coefficients not explicitly specified equal O. The numerical constants and polylogarithmic factors of B, and D are omitted.
Algorithm
Bo
A
B
A2
B2
D
?
AP
0
0
0
0
N²52
Y S LN(14))
RR/FlipFlop
22
0
0
0
0
N₂²
? S LN(149/53)
GraB-proto
0
3(1)
N
+ a
0
0
2²
Y S min LN M(14a) N
1
GraB
0
3(1)
N
+
1
N
2
7 x min LN M(14a) No
50
PairGraB
0
4(1)
N
+
0
0
2²
7 x min LNo N(14a) No
A: may take other values as long as Ex= As <: 1 for GraBs.
Arbitrary Permutation (AP)
Proposition 2 (AP). Suppose that Assumption 3 holds. Then, obtain that, for
(0,)² N2 |V [xx((,))) N252
Applying Theorem Mand tuning the step size, we obtain
(nRO)
L.oo
[.Foos $)
|&s(x,)|
Q
Q
34

---

Proof. For any it follows that
(Ōg)
2 max
max =EIN]
1=0
{n²
max NE[N]
S N2 a² [V N25
In this example, for Theorem
p 2, - Bo N2 D= N25² and 10. These lead to
( (TNO +
[V((x))] =
Q 9=0
Next, summarize the constraints:
1
Ei A A B,
V1 Ei= A; 1 VB
y min
LN ,2
322 N
It is from Theorem For simplicity, we can use tighter constraint
32LN (1 + a)
After we the effective step size 7 NN, the constraint becomes
1
32L (1+a)*
and the upper bound becomes
Q-1
VV [F(x,))1
Fo
+ x22332)
7Q
9=0
Applying Lemma
D we obtain
Q-1
I.F (1 +
(TFONS) $
|f(xx))1
Q
Q
NQ
q=U
F.2 Random Reshuffling (RR)
Proposition (RR). Suppose that Assumption 3 holds. Then, we obtain that, for q 2 0, with probability at least - 8.
( Na² [V ([ +N=2).
(ō,)² < 4log²
Applying Theorem and tuning the step size, obtain that, with probability at least Q6,
Q-1
(
LFo
[1 VN
LFoV
(xxx)))
NQ
9=0
Proof. Since the permutations {T,) are independent across different epochs, for any q, when ditional on Xg. we obtain that, with probability at least 1 - ō,
(o,)²
max [N[N]
Σ (V - -V((1)) O
< NCaa I
(15)
35

---

where C' = 4 log' (g) and the last inequality uses Yu and Li 2003 's Proposition 2.3.
In this example, for Theorem p= 2, -. Bo = NCa². D NC²² and c= 10. These lead to
1
[V)(xx))
(TNOQ +
Fo
9=0
Equation (5) used for each epoch (that is, for times), so, by the union bound, the preceding bound holds with probability at least 1 - Q5. Next, we summarize the constraints:
1 LN ,2 4L2,,V
-I-E-A A. VI- A. 1
S min
V
4L22VB
32L N
is from Theorem For simplicity, we can use a tighter constraint
1
75
32L N + +NCC)
After we use the effective step size 7 VN, the constrain becomes
1
32L (1 {
and the upper bound becomes
Q
V f((x)))11 = Ô 6 Fu
7 L2 1
+
iQ
N
q=0
Applying Lemmal
I
we obtain
Q-1
LPo
1
a
(LFOVNS
Vf(x,))1
vN
+
Q
Q
NQ
0
F3 FlipFlop
Introduction of FlipFlop. The permutation in each even epoch (q 2. generated randomly and independently; the permutation each odd epoch (q = 1, ..) is the reversed version of the previous epoch's 's permutation. Take N 3 as example: If (0, 1) then Ti (2, 1,.
FlipFlop belongs IP. We regard each even epoch and succeeding odd epoch as meta epoch. Accordingly, we regard the permutation in such a meta epoch as the meta permutation (denoted as σ). For instance, if the original permutations are कn = (0, 1, 1,2) and क) = (2, 1, 0), then the meta permutation is dg = (1) = (No. (To)) = (0, 1, 2, 1, O). Now, we see that the meta permutations are independent. Thus, it should be seen as a variant IP.
Analysis of FlipFlop. Since the length of each meta permutation is 2N and the meta permutations are independent, we define the order error of each meta epoch m (m = 0, 0, 2 1) as emm := ))ll to distinguish it from the original order error 5.- As shown in Proposition 4 FlipFlop achieves the same convergence rate as RR. This is aligned with the conclusion of Chae al. 2024). and the observation of Lu al. 2022a].
[ax D= (V (5) (X2m) f
Proposition 4 (FlipFlop). For FlipFlop, we assume that Q mod 2 = O. Suppose that Assumption holds. Then, we can obtain that, for m = 0,,...., 0 1, with probability at least - 8,
(bm))) < log² (o) (NIVV)(X2m)) N
Applying Theorem 7 and tuning the step size, we obtain that, with probability at least (Q81/2.
Q/2-1
Σ
[f(x2m))
LFo
[
JN
+
LFavNs NQ
Q/2 m==
36

---

Proof. FlipFlop is one variant of IP. For clarity, we define the order error of each meta epoch m as 4/m = max nE(
V V f(x2m))
1=0
where mm is the meta permutation m (mms T2m++) = (T2m reverse(T2m.)). Since the meta permutations are independent, next deal with each t'm separately, and thus drop the subscripts m. For each I n I N,
(157)2
(x Vf(x))
Σ (Vir(o()) -Vfx))((xx()))
NCaa + NC
where log (#) and the last inequality uses Yu and Li 2023 's Proposition 2.3. Similar to 2N,
Chae et al. 2024 Lemma E.5], obtain that, for each N
n
(v
(x(()()) vf(x))
2N
n-
(Va(()())) vf(x))
Σ
[[a(()())) vf(())
2N
Σ
(Vfo()()) vf(x))
(2N-n)-1
Σ
(V)+()())) - VS(x)) -V(xx)
2Ca² [Vx + NOS2
This implies that e.m < NC. + NCa² // fx22m) 21 for each meta epoch m. Following the same steps as those of RR Appendix
222
obtain
Q/2-1
LFo
1
JN
LFoVNs NQ
$
Σ
(x 1
+
Q/2
Q
which shows the sames rate as that of RR.
F.4 One Permutation (OP)
OP, the simplest DP algorithm, is persistent topic due to its simple implementation. However, as shown the prior works [Mishchenko et al.) |220 Koloskova et al. 22024). for non-convex objective functions. its convergence rate is no better than AP. In this section, show that our framework can still help analyze the convergence of OP.
As done in the prior works, we can use the bound of AP as the bound of OP. However, this general bound (for AP) cannot catch the key characteristic of that the initial permutation is reused for the subsequent epochs. To further explore the potential of OP, have the following analysis.
In OP, the key characteristic is that the initial permutation is reused for the subsequent epochs. To fully use this characteristic, we try to establish the relation between o, and Φo- Specifically, for all q Z 1 and n E [N] (here, p 2).
6 2LN ||29 xollp +
Σ V (x)(())))) vf(xo))
< 2LN ||x,, Xollp + 20.
37

---

where the last inequality is due to Fy To for all 2 1. Under the standard settings, to bound the term | xoll, the step size needs to be made very small (that is, 7 S .Nक) causing a very slow convergence. Therefore, to use the dependence property of OP, we need additional assumptions bound | - xollp [Lu al. 2022b Further research is left for future work.
E55 GraB-proto
GraB-proto: Use BasicBR (Algorithm 5 as the Permute function in Algorithm with the inputs and V fx,)), for each epoch q.
of Tg.
Thus, the key idea of our proof is follows:
(V (0)++1(0 v((x))
Lemman
max Ee [M]
Proof of Proposition n E [
We need to find the relation between oy and 0- for q 1. For any
0a 9+1
V (xx+1)) (xx))))))(())))))
V (0)++10) (1 (xx))
+ Σ (((x)))
V (1)))()(()))))))) vf(xx))
1 (x1)
[xxxx)+)) - V/((x)llo
V (
vf(x,))
S 2Loo [|x++1 xglloc +
Σ
V
k=0
Since the above inequality holds for all E [N], we have
5ot1 S N | - -xpl + max
Σ
V (x)))
NEIN]
Note that V (0 (x.) - (x²x) and ( (x,) - vx(x,) correspond to 2x(x) and ( in
Lemma 3 respectively. In GraB- paBBo,,oto, since
[V)((x,) f(x,)) S Gg.
Vi
N
Σ
(V)((x)) - ((x,))
=0,
we apply Lemma 3 with < and b 0. and obtain
1
V ( vs(x,))
V [x,((((x,) vs(x,))
CG
[N[
2
x
i=0
1
04
CG
2
2
38

---

Using Lemma that Ag -
32
31 N f (x,) |b, we obtain
31
0u+1 - 2o ||x
-xyl + max
(V -
-
NEIN
- N
(32
70q +
32
N | fVx)(x)) +
(2 + + 2G,
31
31
1 44
35
N
[V,
2 CG N S
62
31
where the last inequality Nox
1
Next, we obtain
32
(6o+1)²
3 +
k0))²
N2 + (1)x,))++)
4
50
As result, the relation between o and Q is
(Ø,) 2 v 4 ( ) +
3
50 N2
N2 -
[V[(x,-))]+++33 Cos?
(16)
for q 2 1. In addition, we need to obtain the bound of (0b))
(ōo)²
max [E[N]
M
( - v)((o)))
N [V
In this example, for Theorem 1 oc, v- = 1, = प.4 By - 0, B1 = - C
B = 2 and D N25² and 40. These lead to
Q Q-1
( (~NO +
1 Q 13
Σ
[V
(1, o
Q
0=
where Fo f(x)) f.. Lemma 3 is used for each epoch (that is, for Q times), so, by the union bound, the preceding bound holds with probability at least 1 - Q6.
Next, we summarize the constraints on the step size:
7 min 1
1
VI- EL. A VI 1 A. 1
LN 321n, N' AT2.v B AL2, B
N
where the first one is from Theorem [ and the other is from the derivation of the relation. For simplicity, use tighter constraint
7 S min LN 32 + a)' 32I
After we use the effective step size 7. == YN, the constraint will be
7 min [T 1T3322,00 (1 + ax) 32L
and the upper bound will be
[V[(x,) 0
(Fo Fo 7Q
+ 12 -² 12 N2 04
1
Q
Applying Lemma
D we obtain
Q-1
((L+ L2,00 (1+a) + Loo) Fo
(L2 Fos) + (La
3
[x,(x,))
Q 00
Q
NQ
39

---

E6 PairGraB-proto Proposition 5 (PairGraB-proto). Suppose that Assumption S N2 we obtain that, for 0. (0o)² 22 [VS( + N2252, and for 9 2 1, with probability at least -6,
3 holds. If each fa is L foo-shooth and
(0,)
2 S - N50 | |V 4C2
where O (log (dN) Ô (1). Applying Theorem
and tuning the step size, we obtain that,
with probability at least 1 Qô.
1
(ERR (12,,0 Fos)
LFo
)
$
(NNQ
Q
NQ
where L L 02,0 (1 + a) + Loo.
PairGraB-prote Use PairBR (Algorithm 6 as the Permute function in Algorithm | with the inputs of T.. (V (x,)) - and V (x()), for each epoch q.
Thus, the key idea of our proof is as follows:
0++1
max [
(( V v((xx))
Lemma
Qq
Proof. The proof of Example 5 is almost identical to that of Example T is replaced by Lemma This difference only causes that some numerical constants are changed accordingly.
except that Lemma
F.7 GraB
Proposition 6 (GraB). Suppose that Assumption
3 holds. If each fo is -mooo- and }. we obtain that, for 0,1. (Ø,) s 2 f |1 2 + 2 and for q 2 2. with probability least 8.
L smooth and y I min 12812 x 128L
(o.)
2 - 5
3
c ())-1)² 1)²² +
1
2²)
50
1 N2 [V 20
+ N2 + 22²
|| [[ 50
where C = O (log ( = Ô (1). Applying Theorem and tuning the step size, we obtain that,
C=
with probability at least 1 Qô,
Q-1
[FFo (o2, +
(Lexxfocc) $ )3) NQ
[1((2)111
21=
Q
Q
P=0
where L = L + L2,00 (1+ & +a) + Lsc.
GraB. Use BasicBR (Algorithm
5 as the Permute function in Algorithm 1 with the inputs of Ta.
(T, (xx) N- and
NV
Σ ( (x.-)) for each epoch g.
Thus, the key idea of our proof is as follows:
N-1
Φ + max WE M
V (T
(mT+1((1))
Σ
(0g-10)
N
1=0
Lemma
max nE nE(N]
Vir((1
(x+)
V (0)
40

---

Proof. We need to find the relation between 0y+1 and ōg.
0 g+1
(X - V (x
x (zg))
V (+ (x
(i
N-
N-1
1
V V (x)+++))))
V
J5z (x
N
N
1=
1=0
N-1
V (5)
Xg
To¹ (mmt2(1))))
(0,-0()((-11))
(17)
Then,
T1 in
V (xx+t)) - V (
Xq
To (T++
V (0) V (igee(0)
Xx
< 110
X--1 Xgg
20
n-1
S 1100
Σ
||x Xgl100 +
X2
x (Tg+z (i1)
$ 2T NDg:
N
N
T2 in 17
V F. (xx+1)
1
V
VSr 100) (x6-1)
N
N
1=0
N
1
- (4)
V (x+++)
Vii
x--1
N
N
1=0
(0)
Vi((x+1) - V/i
[x-1
-0
X-+1 x2--
[|x+1 xol1,c + +|1x, x-- +
x
L. 2 -1
Since the preceding inequalities hold for all n E [N], we have
Jet1 S NA,
2L
1 N-1
+ max RE[M
Σ
x- (m000))))))
Σ
V n (0x-)
(18)
N
Note that Vin((()) (xx)
N Ei V VS
(x
and Vi
Xq
N EN' V5n-11()((411) correspond to (x) and (z((() in Lemma respectively. We next
41

---

obtain the upper bounds of
N-1
Σ
2
(x(
and
max nEIN
Σ xx(i)
and then apply Lemma 3 to the last term on the right hand side in Equation 18
12xcoll2
N-1
V Va (x,())(()))
Vm (x/-1)
N
|| (Vimlo()))
N-1
1 N-1
Σ
V
x (x(
+ (Vinco(ta))
Σ
V (l,((((x)))
N
N
1=0
N-1
N
< [xx((())())
(x))
+
V 10 (x--1)
v
(x,(10
+ GG
N
N
1=0
1=0
N-1
(0-1(0)
< [x,((0()()))
(xn,()(x))1l
x x--1
Σ fi(xx)
GG
N
N
N-1
1
(1)
< L2,0 12
-xolla0
+
L2,00
x
x-1
Xg
+ +G
N
1=0
N-1
< L22 1|x xalloo
+
1
Σ
L2
x
X--1
+ +1|xg-1 xpl1x) ) + Gg
N
1=0
20
< L22 + 20 1
GG
The preceding inequality holds for any i E (0. 1, NO..,...,N
N 13.
N-1
N-1
[x,
V (x
(i)
N
i=0
(x)()(())) (x
V
(2)
(x
N
11)
(1)
Vf
Xg
Vij
x
Xq
m
(
Vff
x
x (3)
1(1)
(1)
Lo0
X
(()
Loc
Xg'
xx
||>
Xg
x
x
1=0
$ NA, + 2L N NA 1-
42

---

For any n E [N], we have
(3)
N-1
(Z, (xx)
1
V
(x
N
N-1 1
N-1
Vi (x))
|00 (2)
+
V/n,(0 (xa)
V (
N
N
1=0
1=0
N-1
(V
[xn(()((1)))
Σ
(0
V (10
+ Φ
1
N
ft
x
())
(1)
Σ
[((g))
+ pn
N
1=0
Σ (0 - (x), 00
Σ
1.
v.fi(x))
+
100
n-1
N
S Lox)
Σ
||x;
- -xel
+ +ox
Xg
+ +
N
1=0
1=0
30
S Lix0 1=0
Σ
||x
xell
11 + LLx
xx-1
x
+ -1xx-1 xg1100 + +0,
N
10
TI + 2T. NAg-1 NT
+ 9/-
Since it holds for all n E [N], we have
M
S Loo + 2Lo A + o.
max [E[N]
Zm(()
Now, applying Lemma to the last term on the right hand side in Equation (18), we obtain
6 S (3 + NA + 1
2 (Tx + 2T N - + +,))
+ NA, + 2Lx
+ ([2,04 + 222 9-1 + Gg)
LooN+ /L2,00
1
Ag + (5L N + C022,00 A
2 0 CGg
1-
2
9 LLaN 0L2,00
1
12
32
N V \ !l)
70g
+
2
31
31
+ + + C
(32
70
32
N [
+ 200- + cG
1
31
31
where the last inequality uses Lemma No + (22,00 31 S 124 and
If 7 TLo
N$
p3 and 7 222 C 128
then
Lo + L2,00)
उश < 12 we obtain
67
6
5
6
1 N NI + 2 + cG.
0 5 124
+
N [V(x,)1
+
124
124
124
Then, we obtain
(drt1)² 2 5 5
(0,)²
2 +
1
(3,-1)²
50
1
+
N2 + 2C²
||V[(x))11
+
N2 [| 1)1? +2022
50
50
43

---

So the relation between dy and Φ is
(o₂) 2 -
2 +
1
26 )²
5
50
1
+ 50
N2 + 202
||V[(x,-1) || +
N2 / 2)) + 20
50
for q 2. We have (0o) S 22 /
(xo)l NN²²² and (~1)
2
2 N² | (xx )| +N²52.
In this example, for Theorem 1 p 00,
3 A2 50. Bo 0. B1 50 -2 + 22).. B2 = N = 20 B = N2a? lead to
A1
= N2 and c = 25. These
Q Q-1 1
[fxxx))
Fo + 2 (
(
N2 /²²²² 5 7 2, 02(2)
(NQ
where Fo = f(x)) f.. Lemma 3 is used for each epoch (that is, for Q times), so, by the union bound, the preceding bound holds with probability at least 1 - Q6.
Next, we summarize the constraints on the step size:
1
VI E
A VI
2i=1 A
7 S min
LN 32L2
2i B,
4L2, B
322
1
7 S 1
1
7 S 128T.2, C
where the first one from Theorem D and the others is from the derivation of the relation. For simplicity, use tighter constraint
1
7 min
LN
128
Na) 128
After we use the effective step size 7 YN, the constraint will be
1
S min
L 128 (1 +
C N
+a)"
128
and the upper bound will be
| (x,(x,) 0
7Q
Fo
+
L
2,00
Q
1 2
N2
1
C25²)
q=0
Applying Lemma
we obtain
V 1(x,))1
0=0
(I. T22 (1
N a) + T.o0) Fo
C
+ (L2)c + (Laxtfoc))
3
Q
Q
E8 PairGraB
Proposition (PairGraB). Suppose that Assumption 3 holds and that N mod 2 If each fa is L2 smooth and -moothh and y I minf 61L2 GiL J. we obtain that, for q 0,
(σu)² s N2aa (Vx(x))' )1 +N22² and for q 2 1, with probability at least 8.
(ō,)² 2 < 5
( 2 2+ +
( 50
N2 + 4C202) (V)((x-1))1= 44222
44

---

where C = O (log 4N Ô (1). Applying Theorem and tuning the step size, we obtain that,
with probability at least Q6,
[LFo (12, Fos) +
$
[V =0
(NQQ
Q
Q
NQ
where L L+ 02 (1+
C N +
+a) Lxo
PairGraB. Use PairER (Algorithm 6 as the Permute function in Algorithm [ Tg. (n) and N En (x,()) for each epoch q.
with the inputs of
Thus, the key idea of our proof is follows:
max [N[N]
V
Xg"
Σ
(
1=0
N-1
Lemma
Vin((0 (xx)
V (),(0)(x))) (xx)
N
1=
Proof. We need to find the relation between Φy+1 and og
(x)+11) - V fxx++1))
(TT+1((0)) (1))
V (1) - V ((gg)((1)
Xy
N-1
1
(x,(0((xx+1) -
V (xx,(1(x())
N
N-1
V f
Xx
V
(19)
N
1=0
Then,
T
V (x V 15
Xg"
Ta (Xx+1) Vircesl)
Xy
mg ((T011(0))
< L
Xg-1 - Xg"
R-1
< L.3
Σ
||xx+1 Xyllo0 +
Xg x,
1=0
< 21 2L No,
45

---

T2 in 19
N-1
V (5 (x++1)
1
N-1
Σ
V
S (m
N
1=0
V (0) (x,+0( ST, (1) (2/)
X5+1 x2yloc
WE
(1x++1- - -xploo+ + +1|x, - -11l00)
Loc
N
1=
< N
Since the preceding inequalities hold for all n E [N], we have
N-1
0o+1 S ND, + max
5
(()) Xg a
Σ
N
1=0
(20)
(
Note
that
Sm, (xx) - # Σ (x,(()x))) and (ines10))
X4
correspond to Zx(i) and (s) in Lemma respectively. We next derive the upper bounds of
N Eー VSn (x(x)
N-1
Σ
zz(1)
and max NE(N
Σ Z
i=0
and then apply Lemma 4 to the last term on the right hand side in Equation 20
1 N-1
||2,,(00122
V
(m,()))))))
v
(0,
N
1=0
(V/ncolbt)
N-1
N-1
vmme)(()))) /
Σ
V
(T (x()
- ()
Σ
V
N
-
N
1=0
1=0
1 N-1
N-1
< (m,(())(²))))))
- (x))))((x))1
+
Σ
1
Σ
N
N
1=0
N-1
+ [)n,()(())) - Σ
(x
N
1=0
1 N-1
< 12,00
- xx ||
Σ
1,,00
|xx/
x=ll:0
Gg
N
1=0
s 2L22,,0 Ag + +gg.
N-1
N-1
1 N-1
((, ) =0.
Σ
Σ
[x,()(x))))
Σ
Z (x)
=
N
0=0
0=0
1
46

---

For any n E [N], we obtain
TesT( (3)
N-1
SZx((0) (x²)
v
(x)()((()))
N
N-1
N-1
Vi(((t) (xx)
Σ (lm((0(x())
+
(x)(0)))))
Σ
V (nm(1)(2)) (xn)
N
N
1=0
1=0
1
(+)(((()))) ()m(()((x)))
(x
V ([n((((x)))
0
N
20
1=0
n-1
N
V ST (0) (x:) - (x),(
+
V
1 (xx) - (x))l) + +
N
1=0
1=0
1=0
N-1
Loo
Σ
||x Xx xulloo
Loo
Xx
1l
+ 00g
N
1=0
==0
<2Lio
+ ,q
Since it holds for all n E [N], we obtain
nn-1 1
max N
Σ
xx(1)
S 2Loo Dg + 0g.
i=0
Now, applying Lemma to the last term on the right hand side in Equation (20). obtain
1
6 S NA, + 2 NS, + og) + C (212,xx + Gg)
1
< N5 NN + 2L2 C)
Ag
+ 0 CGg
2
32
32
+ 1 2500 + CGg:
< N5 N + 2L 0,
70g
N [V](x,)]]
31
31
where the last inequality uses Lemma
6 If Loo N
and ,2, C
C a we obtain
54
38
7
+
N
\f(x))l + +CG.
62
62
Then, we obtain
(0.+1)² - 5 (0g)² +
3 N5 + +4C9a2) (1Vx(x)))++++) +40
So the relation between o, and - is
(5,) 2 S (āp-1)² 2 + 50
N2 + 4C302) /[ + 40222.
for q 2 1. In addition, we have (Øo) 2 < N2 2 ||V (x)) ) 2 N2
In this example, for Theorem p x,
A, 1. Bo 0, B, 32 + 40"a2.
D = 40 B a² D = 2 and c = 50. These lead to
1 Q
[
N2 1 -
o
(,NOO
Fo
+ 72 L3
20 - (13
Q 0
TNQ
where Fo = f(xx) f.. Lemma is used for each epoch (that is, for Q times), so, by the union bound, the preceding bound holds with probability at least 1 - Q6.
47

---

Next, we summarize the constraints on the step size:
1
v1
Eiz Ag
vI Ei=1 Ai 1
y min
LN' 32
B,
4l2, B 322 N
S 64
y S 6'
where the first one is from Theorem [ and the others are from the derivation of the relation. For simplicity, we can use tighter constraint
min
LN 64L2, (N + C Na)' 64Loo N
After we use the effective step size o yN, the constraint will be
7 S min
L' 64L2,00 (1+ o + a) 6ALco )
and the upper bound will be
1
Fo + L (
1 1 ,² 12,00 N2 02.2)
[xxx2))
12,
Q 0=
7Q
Applying Lemma
1
we obtain
Q-1
fxx,))1
Q 4=0
(L (L+ L2 (1+ @ + a) + Loo) Fo Po + (
3
o
Q
Q
NQ
F99
Refinement of the High Probability Bounds from Q5 to
failure probability of Q6 rather than 6 in the main body. This can lead to looser bounds as Q increases. This section shows that the framework
To maintain consistency with Lu et al. [2022a] and Cooper al. 20023).
also provide bounds that hold with probability at least 6.
Considering that the bound for AP deterministic (not probabilistic onc), we next only discuss IP and DP:
IP. Taking RR as an example. Starting from Equation 1 8',
we obtain that, with probability least
(5,) < 4 llgg
U,
8'
where No2 Nr² for brevity. That is,
()
P (1h))² > 1lg
58'
for any g E {0, 1,.,,,...0 Q 1). Then, applying the union bound for q E {0, I,..,,, Q 1}, we obtain
P 3q, (o,))² 2 4 logg
U
< Q8'.
8
Then, setting d =
5' Φ. we obtain
[QQ
TP 3q, 22,)2= 4 4log2
U
< 8.
48

---

That is, with probability least 1 1 8. (0,)) < 4 (29) ( U for all q E (o........ ........-..... 1}. Then, using these bounds, obtain the desired bound that holds with probability at least 1 - 8.
DP. Taking GraB-proto as an example. Starting from Equation (16). least 1 -',
we obtain that, with probability
ddN 8
(0,)² 2 S log"
U
+V,
where U =
+ and V = -0
+ 50 N2 That is,
ddN (
(0,)² 2 log?
2
U
V S 8
8
for any q E 21, Q 13. Then, applying the union bound for q E {1, 21,2..... 13, we obtain
IP 3q, (0,)² log²
(
U U+ S (Q SQ-11)) 1)8".
Then, setting 8
8' Q-I- obtain
3q, (o,) 2 log² [dN(Q
IP
U U+V) - -QQ-1)b
That is, with probability at least 1 8, (10g)² S log² (N(g-1) U+V for all g (1.2....QQ-1)
Then, using the bound of (oo)² (it is deterministic) and these bounds, obtain the desired bound that holds with probability at least 1 -
G Theorem 2
G.1 Order Error in FL
Theoretical understanding of Definition lative updates in one epoch are
We prove that, for small finite step sizes, the cumu-
Xg+1= X
N-IK-1
= =
V (n)( (x(())
1= k=
1
-
Sa(n) (Xx)
N-1K-1
(x)
fa((n) (Xg)
5 ==0
j=0
N- 1-1K- K-1
u(n)
K-1
Vin(s (x,) + +0 (
1) 53
Σ
Σ
(x))
(21)
R== k=
1=0
Similar to the analysis in the main body, it can be seen that the error vectors are caused by the second and third terms on the right hand side in Equation 21. Note that when we consider V VV (xf) x
T., the second term can be also seen as optimization vector (with the same direction as (x(x))) o))- This is mainly because the local solver is the classic SGD in our setup, and it can be different when the local solver is the permutation-bast similar decomposition in the main body, our goal turns to suppress the error vector as follows
SGD. As result, we next focus the third term. With
N K-1
v(n)-1 K-1
Error vector = 2
VV (Z))))(()))
Σ
Σ
(f (x2,0) V.a(i) (x₂))
j=0
49

---

One straightforward way is to minimize the norm of error vector
N-1K
f(n)
K-1
Error vector| S 5
Σ
Σ
(Viz()) (x²) - Vir(O) (x4))
s n=0
s
Am
1
j=0
N-1
[(m)-1
5 LK2
Σ
Σ
(Zi(s)) (xn) - Vir(i) (xn))
5
n=0
1=0
S LK?N
52 pq.
G.2 Proof of Theorem To avoid ambiguity, we define
N-1 q.K
x
x
4.0
Due to the amplified updates (see Lines
5
and 6
Wang and Ji 2022 we have
N-IK
x Xx = -y 5
(aa(() (x)x))
n=0 k=0
N
K-1
Xg+1 Xx, = -
Σ
Σ
(xg)it)
5
A=0
k=0
We define the maximum parameter deviation (drift) of FL in any epoch g. 4g as
A = max
max nE N-1) (e -1
[x], - -xll,, 11x.111111 Xgllp
Then, obtain the relation
[xx+1 - Xzll, = 17 ||x Xgll, S nAg.
Lemma 7. We first prove that if LL,
J S 52
the maximum parameter drift in FL is bounded:
32
1
32
KK 1
32
Ag
K
04
+
[
31 KKG.
31
5
31
S
(4,) 2 < 2
5 (7g) + 4, 2 N2
2 4
g2
Proof. Let v(n) = [ S. Then,
x", X2 x x + x²x0
x v(x)
4.0
+ +x,00
v(n) 9.0
Xg
=0
u(n) - K -1
V (m) (x 2
V Vfx(()) (x(r)
1=0
1=0
1=
For any q >> O and all {0, I,.., N - 1} and A E 10,,,..... K 1}. it follows that
k-1
u(n) 1 K
||x Xullp
7
(x.(n)(X 7
v
1=0
1=0 j=0
k-1
v(n)-1k-1
1
7
V xx (m) fm) (x
+
13
Σ
Σ
V (1)
(22)
3
50

---

Then, we bound the two terms on the right hand side in Equation 22
respectively.
T in
22
V S (T
1=0
59
Σ
V [m,(m)) (x))
+7
Σ
V
- -Vx((x)
j=0
+7
V fx,))
h-1 1
k-1 1
$ Σ
(m) - (xn(a)(xx)l) +
Σ
V
- -
+ Σ
V [x,,))))
1=0
==
j=
k-1
4-1
k-1
S 5TL, 1=0
Σ
| x111p +7 Σ
Gg + 7
Σ
(x,
1=0
1=0
S < + TKG + | (x,))lp
T2 in 22
b(n)-1 K-1
1
Σ
V Vzz (x)1))
3
[o(n)-1 - K-1
1
Σ
(V (VSx,0)(2 (xx())(xx) + ()n(()(xx)) - VS(x,) + v
=
[(n)
((n)-1
59g S
1
Σ
Σ
V ( (x,)()((())
1
Σ Σ
V ( -
1=0
1
(()) K-
+78
(V)()))) )
1=
((n)-1K-
r(n) K-1
59g
1
Σ
Σ
V {
(x)())(x)))l + 7 5
+75
1
|V
8
5
1=0
1
1=0 ==
((n) K
1
Σ
Σ
|| - -xllp + + g +7K (v(()( 3 [V
==0
0=
1 A + t S 2g 1 s [xx,))l
1
(xLpK(((n))
Next, we return to the upper bound of || x1 for any n, k such that n + k < NK. If = 0. then un) < N and the first term on the right hand in Equation (22 equals zero, so we obtain
|| - xyl1, S SLLKKN A + 7k 54 + 7KN 5 [f(x)))pp
51

---

If k > 0, then v(n) SN N- - S. so we obtain
|| x1l1, STyKA + -KGG > 7K (V))(,
KYL, (v(n)) 1 A 7 30, + 7 (o(n)) 1
5 \V()))
S StiKK + +gKGg 7 [|x
N
1
(NN -1) |
+
-1 1
0g + ,
oq + +
S
s
1
1
fg + KNN 1
STLKKN
Ag + 7k
|VI(x,)], + +2KG.
5
8
5
Therefore, for any n, h such that nk + I NK, we obtain
A max
x,y
n,k
S 5
A + 7 54 + +yKN [VS((x))lp+ + +xKGg
5
5
Then, if 7
1 3
<
we obtain
32
32
1
32
KK 1
32
4
K
P +
5
[ + KKG.
31
31
31
It also implies that
(A,)² < 4472'' K2
5 (7a)
2 + 47 =2
5 |V +
At last, using |x||, - |||| for E Rd and 2 2, we obtain the claim of this lemma.
Proof of Theorem 2 For FL with regularized participation (Algorithm 2 the cumulative updates over any epoch q are
N-1K-1
X++1 101-xx,p Xg = -111 S
Viz(()) (x(jk).
(23)
=== K=
Since the global objective function f is L-smooth, it follows that
f(x++1) - f(x,) S (Vf(x)) X,+1 - xg) + 2
L |xy+1 - -xy11.
(24)
Using Equation 23 we obtain
(V (V[(x)) Xy+1 - xx)
= =-M3KN KN ( (x(x))
N-1 K
V (n) (xg.2) )
N
K
n=0
k=
N 1
K-1
1 1
2 n s
KN V f(x,))))1 1|
2 g
KN
v f (m) (
N
K
n=0
k==
1 N- K
2 M
KN
V
n (m) (x - fx(xx)
N
K
n=0
k=
where the second equality uses 2(x, y)
||x||
22 + +|y||| 2|
||x y112.
Using Equation 23 we obtain
1 N-1 K-1
1 マ/ L |xx+++1
x,11
-//
M
Σ
V (t,
n=0
k=
N-1 K-1
1
N2
V 102,00)(872
52
K
==0
k=0
52

---

Plugging the preceding inequalities back into Equation (24). and using MLKN S 1, we obtain
f( - f(x))
N
1
K
1 KN V [x,,)l
<
2"
+
2 2
KN
V
[mz(n)) (x..))((())))
-VS(x))
N n=
K
R=U
N-
1
5
1
KN
fx 11 2
22
1
1
Σ
Σ
xx
X
n=U
k=0
1 $ 2 " KN
\V ) + 1
2 mL
KN (4,)
8
where the second inequality is because (x)(x) is Lz, smooth for all n. Applying Lemma 7 and the constraints 2L2 KN I 32 and yL2 Ka 1 32
we obtain
1xx+11) - -f(x))
127
MNN [1,
27 nI, K
(0a)²
2
+
(25)
256
5
53
Averaging over q (0.1.....
Q
1}, we obtain
1(x0) - 1(x0)
127 Q-1
Q Q-1
[V 21 2
2 2,
K2
(5g)
+ 27
2 12
R²22.
MKN
256 Q
52
(26)
The following steps are similar those in Theorem
Since
(2,)² S Ai (1) )² + A2 ( 2)² + + Av (p)
+ Bu [xx,,) 2I? + B1 [ + B, 1 + D.
we obtain
1 Q-1 1
1
1
(pg)
<
(p))
Q 0=0
(1 Σ Ar)
Q
1=0
15 B,) 1
Q-1
+ (1 1 X 1= A:)
+
D.
(27)
Q
(1- EE A:)
For (0 1), we have
B Q-1
(5.)² < B [V 2=
(
2
<
V (x 11 + DDD
(28)
Substituting Equation then using the condition
28 into Equation 27 and the resulting inequality into Equation 26 and
A
--
M A Ma
S min
T2
K 8
B,
L2 2
we obtain
|V 12 55. f(xo) - f(x2)
MKN$5Q
vD L22 2 te. L K2 1
+ L2 12,
x22
S2 D.
5²
where
10
Using f(xo) f(xQ) S f(xo) - f. = Fo. we obtain the claimed bound.
[1-E A.)
53

---

At last, we summarize the constraints on the step sizes 7 and r7:
-i-E A
V Ei=IA Ai
y S 4 K VV Bi 4
min
122 K K / V
MLKN S
5
1
1
112KKN <
5 32'
1
122 Ka S
32
1
NLpKN
S
5
32
where the last one is from Lemma]
7 For simplicity, we use a stricter constraint
EE=1A A
VI-
E A
1
y S min [LLKN K2 4L2,, K 3 Vi B,
4L2
VBB
32L,KN
G.3 PL Condition
In this section, we translate bounds in Theorem 2 with J-PL condition
[V) 2 2n (f(x) fa), Vx Rdd
Using Theorem 3 and the relations derived in Appendix Hi we can obtain the bounds in Table 2 for FL-AP, FL-RR and FL-GraB. Here, we tune the step size with Koloskova et al. 20200 Lemma 15].
Theorem 3. Unless explicitly stated, we assume the same conditions as those Theorem that all the local objective functions fn satisfy the pu-L condition. If
3 Suppose
VI >' A,C
S min
32nLKN 32L,, KN (1 a) 4L2 K 1/2 v
(B+ En B,c
,2L, KN
we obtain
f(xQ) - fo (1 11- muKNN! 1)
8
D
[(xo) fa +a
S
LN
+ 47² 1 N252 + c2 72 12 K22
K2 1
D.
52
2 I- A and C2 E A.e
where e 63 Ci
Proof. Starting from Equation 25 we obtain
127
f(x++1) - f. S f(x,) - ft
MNK
)1,
256
S
+ + n K
53
(p,)²
+
2
K3
5
1
1
63
MKN 1
$ 5((x)) ff-
MKKN
N
f
V
4
256
s
+ +222n KaN
1
+ 2 +,22,
2,
K
53
5
< <11- 2ー-22 MunkN (f(x,) -p)) 256
63
Mk N
|V
+ +2y K N
(0,)) + 27 L K
N
53
5
54

---

where the last inequality is due to PL condition, |Vf(x)] > 2/ (f(x) - f.). Letting Fg. =
f f(x,) - f. and 1 - - N g. and then applying the recursion repeatedly, we obtain
Q-1
63
FQ S F0 MKN
0-
fxx,)))
256
S
9=0
Q-1
Q-1 K
+ 27 123
2
K N
53
p
R-1-9 (7,)² + 2
p
1-9
(29)
0=0
4=0
Since for 0 5SiS 11 1,
(0.)² S (xx)) +D
and for q 2 v.
(0,)) S A1 (1 + A2 (P +... + A, (p
+ Bo / (x,) )I² + Bi | [x,( + +.... + Bu [[ D,
after some lengthy calculations, we can obtain that
Q-1
Σ po---o 1-9 (0a)²= 2
A1 P
1
A2
1
Av
1
0 (7z)
p
p"
8
1
1
+
Bo + B1
+ ... + B
Q-11- | (1
P
D,
(30)
1 p
and
Q-1 BB
w-1
Σ E0e-1- 1-4 (3,)²
2
8 1 (x 2 + 0D
Σ
p p-1-9
(31)
9=0
q=0
Combining Equation (30) and Equation
31
gives
Q-1 1
Q-1 8 1- a (0,) < A B
AD
w-1
Σ
[())))) 12 + 1-p + ADP&
Σ
p-1- (32)
p
0=
T=0
q=0
where A
and B = Bo + Bi p + ... + B, pr.
1- 1-(11 +.... A
Substituting
Σ9-1 pQ-1-9
1 (1/g) ) in Equation 29 with Equation 32
yields
w-1 ADpo p
Fq S R + L KON 53
1-9
9=0
1 52
K AD
+ 2 122 K3 NN_
+
5
51-p
p
2,p
53 1-p
Q-1
- -MnKN
1
63
1 2
2 2
K2
1
(B+B)
Σ
[xx,))1
5
256
$2 5
0=0
Since p =1 bynuKN and mn I.NN
we obtain
S
32
2
1 <
64
and
1-p M
I
63
s
55

---

For simplicity, we let c= 64
Then,
63
1
A=
1 1- A1 p
+ A2
+ A 1
1 1- (A1c A2c + ... + Abce)
1- Σ A
pa
p"
B = Bo + B + ... +
B, -
< Bo + Bict....
+ Byc
Σ BiC
/
i=0
and
Σ
w-1
1-1
-+ ....
1 1
1
Sc sc+c2 + t
P p²
p
0=0
Next, after we use the condition
Ei=1 A&e
S
422 K $ / B+ Eizo Bie
and the upper bounds of A, B and Σ P 1-1, we obtain
FQ S p +
20 & N
ADp
Σ p
53
22
K AD
+ nT K N
+ 27
nTg
51 51-p
p
53 131-p
2 Σ i=1 c²
D
$ 8 Fo +
1 Σ i= Age
LN2
472 12 K2
4
72 L2
K2 1
D.
E
Act
4 2.
52
At last, we summarize the constraints on the step sizes 7 and ry:
v1 >m= A&c²
7
4T2,
k&v B + Bid
MLKN N
<
5
32
K2
<
5 32'
T22, Ka
1
LL
5
32
where the last one is from Lemma]
7
For simplicity, we use stricter constraint
E A,c
7 < min
32mLKN3 KN
4L2, K 1 3
B + En Bid 32L,KN 3
H
Special Cases in FL
In this section, we provide proofs of the examples of FL.
56

---

H.1 FL-AP
Proposition 8 (FI.-AP). Suppose that Assumption holds. Then, we obtain that, for q 2 0.
(Fa) 2 [ N
Applying Theorem
we obtain
IVI 11 0
Fo WKK + 2 + 2 1 52
If
we
set
1 and
tune the $
step size, the upper
bound becomes
O
LFa(1+a)
+
LFoSc NQ
+
LraNs NQ
Q
Proof. For any epoch 9.
(0,))²
Σ
(Vlx,()(x,,) - -v
S SN S N2 [V/(x)I + Nº52.
max N
In this example, for Theorem 2 p= == = D= N2 and 10. These lead
Q-1
Σ
[V
(
Fo
+ + 1 525
Q 9=0
(mKN
3Q
Next, summarize the constraints:
- A
V1- -1- A
1 4T,, K VB
7 min
1LKNN 32L,,, KN (1++)) 4L2,, V Vi
B
32L,
from Theorem
2 For simplicity, we can use a tighter constraint
1
7 32LKN (1+n+a)
After we the effective step size 7 mK N g. the constraint becomes
32L 1 + +
and the upper bound becomes
1
[Vf(x))
Fo ?Q
12 + L²
1
2 122
N22 N2.2
1
Q
1
gz
Applying Lemma
we obtain
1 Q-1
LF (1 +
(LFoss
3
+ (LEONS)
[V
Q
nNQ
nNQ
q=0
For comparison with other algorithms, we set 1, and get
Q-1
LFo(1+ + +
(FFOSc)
+ LFoNS 3
Σ
[2((x))))=
NQQ
NQ
57

---

H.2 FL-RR
Proposition 9 (FL.RR). Suppose that Assumption holds.
Then, we obtrain, for o 2 0, with
probability at least -6,
(0,)² S 4 log (5/6) (Na² [x + Noc)
Applying Theorem
we obtain that, with probability at least Q6,
(0 Fu 1 and
=
1mKN + + L2 2 52 2
Q
9=0
If
we set
lune LFoNNs NQ
the step
size, the upper bound
becomes
LF [1+(1
LFa8s NQ
Proof.
Since the permutations { are independent across different epochs, for any when con-
ditional Xq. we obtain that, with probability least 1 d,
v(n)-1
(Ø,)²= = max nE[N]
Σ t=U
VV (V),(()( - -Vf(xx
S + IVV
(33)
where C 4 log 2 (8)
and the last inequality is due to Yu and Li 2023 Proposition 2.3.
In this example, for Theorem 2 2, 0, Bo NCa², D = NC5² and 10. These lead to
Q Vf(xx)]1 o
1
Fo
+ + + 52 522²)
used for each epoch (that is, for Q times), by the union bound, the preceding bound holds with probability at least 1 Q6.
where Fo = f(x)) - f. and = L =
Lp when p 2. Equation (33
Next, summarize the constraints:
VI E A
VI-
A
1
S min
4T2 K E nLKNN 32L KN
4L2
K
BB
32L
32L,KNN
It is from Theorem 2 For simplicity, we can use tighter constraint
7
32LKN (1 (1+1+a+ V(a) After use the effective step size 5 MMN 1, the constrain becomes
5
1 1 $o
32L
71
and the upper bound becomes
[V ō
Fo 7Q
1
2 R22L2
12 Ns²).
1
N2
g
Applying Lemma obtain
Q-1
LFO (1 (1+ +1+
LFoSs
(
3
Σ =
11Q
nN
For comparison with other algorithms, we set = 1, and get
1 Q-1
/LFo (1 (1++a) (LFo(1+a)
LFoSs)
LFovNs
+
Q 0=0
Q
NQ
NQ
58

---

H.3 FL-GraB
Proposition 10 (FL-GraB), Suppose that Assumption 3 holds and that N mod S O and S mod 2 = 0. If each fn is L2 -moooth and -moothothh and ? S
1 minf 12 3 1)) KN s
}. we obtain that, for 9 = O, (pu)² S N2 [VVf(x)) + N25- for 2 1, with probability at least ò- ò,
1
3 (ga)² S (0)-1)²+
(1
N2 + 6C2(2) 1I
36 s² S + 6C
96
96
where C = O (log (
Ö (1). Applying Theorem
we obtain that, with probability at least
1 - Qô.
1
fx,,))11
Q
1 MMKN JQ + L22 K2N
Fu
5 Q²Q + 222 + L2 K² 1
5 5
=
After
set O LootlLa +
we
and time the step size, the upper bound becomes (La
PaCs) NQ
where i. = L+ 12,00 (1 + N + a)) + Toxo
C
FL-GraB. Use PairBR (Algorithm 6 as the Permute function in Algorithm -
with the inputs of
Ty. [p-]n= and N En=o D. for each epoch q.
Thus, the key idea of our proof is as follows:
K
N-1K-1
Fyt1
max m (8,25 N)
V fxx(1)
(x2xg)
ffg(() (x4s))
N
1=0
1=0
m-
K-1
N N-1 K-1
Lemma 5
Σ
Σ Σ
Vize(t) (x(xs)
max mE (5.28.....N N)
My
1(8)
1=0
j=0
+ 4g
Proof. We need to find the relation between 0g+1 and Pgg. For all m 25,25.... ..., N).
V fm (Xx+1) V (x
P9+1
K
V Unzt (1) (X (occi)-//
Vʃ (X++1))
K
1=0
1=
K
11 K-1
<
V Tmp (1) (xp-1)
X
K
0
0=
1=0
1=
N-1
N-1K- 1-11
V Sngli) (xx+1)
V T7,110 (25
0
1=1
1=0
1=
K
N-1K-1
T ((ooe((1))
V Vf
fm)))
X
Σ
V
fr,(0) (25
(34)
N
1=0
59

---

where the last inequality is due to vf(xx+1)=
N Ei=o Vim(()) (xx+1). Then.
1
K
K
mo (
in
34
(1) (xc+1)
(1))
Xgg
K
1=0
1=0
(To+z2(1))
V fmgzi (1) (xg+1)
V (mg+((0)
X
1=0 j=0
m-
5o (T))
Xy+1
93
1=0
m-1 1 K-1 Σ
9 (TT-) (3))
0 K
-xolo + Xx
i=U j=ر
1 m-1
2 K
Σ Σ
(n + 4n)
j=U
L (71g + Ag),
N-1 K
T2 in
34
Sz (x
V Fxz(0 ( (213)
K
N
1=0 1=
1=
1=0
j=U
m-
V 50, (xx+1)
Vi (x
K
j=0
||x Xgg0loo
K-
[|x++1 - -xol + +1|x0 )yo)l
LL m- K-1
(nAy + A,))
N An + Ag).
Since it holds for any m {S, 25..... ...., N), we have
Pgt1 S 2L N (n + Ag)
m-
N-1K-1
+ K
1 max
Σ
Σ
V
s
x3
Σ Σ
Vxx(0) (x))a)
f=0
(35)
Note that
K-1 1
N-1K-1
1
V Sm, (x(xs)
Sin(()) (x
N
0=0
1=0
f=0
and
K
W-IK-1 Σ
x 7 ((0001000))
V fagtzlt)
Via,()) (x)
0=
1=0 0=
60

---

correspond to (x))) and (r) in Lemma 5 respectively. We next obtain the upper bounds of
N-1 1000
Σ 2x(i)
and max nE[N]
Σ zx(i)
1=0
k=
and then apply Lemma to the last term on the right hand side in Equation 35
K
N-1K-1
| 2
S(x(00) (x)3)
1
Σ
V
Sma(1) (x
N
j=0
2
K
K-
<
(ix((t) (x)g)
Σ
V
(0x (xx)
1=
1=0
N-1K-1
N-1K-1
Vi2,(1) (Xy,))
V V0 (Xp)
j=0
1=0
K
W-1K-1
Vim((1) (xn) - Σ
V ( (xn)
1=0
1=0
2
K-
[ix(()) (x)gs) - V (i,( (x4)l12
N-1 K-1
+
Σ
V (Fx(0) (x41)) (5,(0)) (xx))l2 + KG,
N
1=0 1=0
K
N K-1
< L2,00
Σ
|
Xyllo + L2,00
|>
x x1l1o0 + KG
1=0
K-1
1 N-1K-1
< L2,00 Σ
Dg + L2,00
Σ
Σ
Dq + KG
N
1=0
1=0 f=0
< 2L2
+ KGg.
N-1
N-1 K-
1 N-IK-1
Σ z (
Σ
V
(z)(() (x(s)
Σ Σ
V
Vf (1) (x)
= 0.
N
1=0 f=
61

---

In addition, for any m E 2S........ N.. we have
K-
N K-1 1
Σ (t)
Σ
VzZ (x)3))
Σ
V frg (25))
N
1=0
1=0
1=0 1=
K
K-1
V ( (Z)a)
V (9 (xp)
1=0 1=
== 1=0
N-1K-1
N-1K
VagW (2
v (a (xg)
N 1=0
1=0 ==
5=
K-
1 N-1K-1 1
Vag(( (x₂)
Σ
V
Vin (Xx)
N
1=0
1=0
V. (x - (iz((() (xa)lloc
N-IK-1
V (( (22.)) - VSra()) (xu)lloc + K Kgg
1= 1=0
K-
N 1 K-1
< Lox
Σ
|x] - x0 + Loo
x5 -xol1 xx11.0 + Kg
i=0 1=0
0=0
1=U 1=0
m-
m-1K-
m-
N-1 M-IK-1 K-1 Σ
S
Loo
Σ
Σ
A. + Loo
Σ
Aq + Kgp
1=0 j=0
1=0
1=0
j=0
$ 2L ( KNA, + Kgg
Since it holds for all m E (8,28, ..... N}. we have
max m
Σ xx(1)
S 22 + KKG.
Now, applying Lemma to the last term on the right hand side in Equation (35,, we obtain
1
Pot1 S 2T N (nA Ag) +
2 (2 NA, + Pg) + C C2I22 + Gy)
N + 2L2 C) Ag + pg + +GG. <(3 2n) N
Applying Lemma] 7 we obtain
1
pa+1 S ((3 + 2n) NooN + 2L C)
A₂ + p, + CG,,
32
1
1 5 + CG,
< ((3 + 2m) N + 222,00
K S (p, + N IV
31
13
1
< 24
p
|| + SG
q + CG
24
24
where the last inequality uses 7(1 + LoN 1 S + and 2L, S 1.
125 Then, we obtain
3 (2,)) 2 + N2 [V || + 60 |VS(x,))
1
1 s + 60
(p
12
96
96
So the relation between Gy and - is
(p,)² < 3 (R)-1)² + N2
IV + 6
1 S2 + +6022
+
5 96
96
62

---

for 2 1. In addition, we have (0u)² _ N /V ) ]| + +
In this example, for Theorem 2 p xc, A 3. Bn 0, B1 N2 60
D 5 B a², D 22ç² and = 25. These lead to
1
[Vf(x,)]l*
8=0
Fn + 1 K2N WKKN JQ
11 1 5²Q" + + 22 + K2
5 5
=
where Fo f(x0) f.. Lemma is used for each epoch (that is, for Q times), so, by the union bound, the preceding bound holds with probability at least 1 - Q8.
Next, we summarize the constraints on the step size:
A: Bi 4L2, K V
A
7 S min
mLKN
5 4L2 K S
Vizo
32L,KN?
S 128(1 + L) K
S k2
where the first one is from Theorem | and the others are from the derivation of the relation. For simplicity, we can use tighter constraint
S min
1LLKN' 128L2 K(N C + Na) 128(1 + Loc
After we use the effective step size 7 MKN $. the constraint becomes
7 L' 128 (1 +
1
7 C. N + aa) 128(1 + 1) L
S min
and the upper bound becomes
Q
[F(xx))) o
Fo 5Q + 12
11 Q²²
+ 2
5² 2
12 C252)
2.00
12 5
0
Applying Lemma
! and setting y = 1, we obtain
Q-1
V (x,))
0
[L 12,00 (1+ C N a + Loo) Fo oo2
(
31
((L
(L2ahiCs)
3
=0
Q
NQ
NQ
Experiments
In this section, we provide the experimental results FL real data sets. Refer to Lu al. 2022a
and Cooper et al. [2033 for the experimental results of SGD on real data sets.
Algorithms. We consider the two algorithms in (regularized patpiiiieddpattiiipaattooo FL in the main body:
FL-RR and FL-GraB.
Datasets and models. We consider the datasets CIFAR-10 Krizhevsky et al. 2009 CIFAR-100 Krizhevsky al., 2009) and CINIC-10 (Darlow et al. 2018). We use the convolutional neural He et al. 2016).
network (CNN) from [Acar et al. 2021 and ResNet-10 10
63

---

Hyperparameters. We partition the data examples by the way in McMahan et al. [0117 and Zeng al. [2023] among .N- 1000 clients, ensuring that each client contains data examples from about one label. We use SGD as the local solver with the learning rate being constant, the momentum being 0 and weight decay being We set the global step size to r = 1. We set the total number of training rounds to 20000 (that is, Q = 200 epochs). For other setups, following those in Wang and Ji 2022]. we set the number of participating clients in each training round to S 10, the number of local update steps to K 5, the mini-batch size to 16.
Two-stage grid search. We use two-stage grid search for tuning the step size. Specifically, we first perform a coarse-grained search over a broad range of step sizes to identify best step size at high level. After that, based on the best step size found, perform a fine-grained search around it by testing neighboring step sizes to find a more precise value. For instance, in the first stage, we can use a grid of {10 - 10 10"} to find the coarse- coarse-grained best step size; in the second stage, the coarse-grained best step size is 10-1, we use the grid of {10-1.5 10-1 100.6 to find the fine-grained best step size. Notably, we tune the step size by the two-stage grid search for FL-RR, and reuse the best step size for FL-GraB. We get that the best step size is 10 = 0.1 for CNN; in the same way, we get that the best step size is 10-0.5 0.5 0.316 for ResNet-10.
Computational resources. We use one machine with one CPU and three GPUs. The CPU is Intel(R) Xeon(R) Gold 5218R CPU with 10GHz. The GPU is NVIDIA GeForce RTX 4090. It takes about 3 hours, hours and 4 hours for each single run of training CNN CIFAR-10, CIFAR- 100 and C0, respectively. It takes about 4 hours, 4 hours, and 5 hours for each single run of training ResNet-10 on CIFAR-10, 10, CIFAR-100 and CINIC-10, respectively.
Experimental results. The experimental results are in Figures
We see that FL-GraB outperforms FL-RR across all tasks, especially in the early stages. This is aligned with our theory that the convergence rate of FL-GraB better than that of FL-RR.
2 and 3
FL-RR
FL-GraB
CIFAR-10
CIFAR 100
CINIC-10
Text Top1 Accumcyy (N3
Tust Accuracy
Toust Top1 Accuraoy
%
3500 s96e, 7500 Lodao uidao 15k0e uda 2000 Training Rounds
1500 sal 1880 Lodes uido soice uides 2000 Training Rounds
2004 2009 1599 Lodo 32500 soice uidoo 2800 Training Rounds
Figure 2: Test accuracy results for training CNN on CIFAR-IO, CIFAR- and CINIC-10. As done in Wang and Ji [2022), we apply moving average on the recorded data points with window length of 6; note that we record the results every 100 rounds (that is, one epoch). The shaded areas show the standard deviation across 5 random seeds.
FL-RR
FL-GraB
1I
CIFAR 100
CINIC-10
Test 1op1 Accuncy
That Accuracy
Toust 1 Accurascy
3500 5906, 2500 Locas 12590 1500 Lide 2003 Training Rounds
1000 5969 7080 LocK Lido 1oice Lid0 2000 Training Rounds
2004 5009 1593 1000 32500 sp0ce Lido0 2000
Training Rounds
Figure 3: Test accuracy results for training Re CI CIF and CINIC-10. As done in Wang and Ji 2022). we applied moving average on the recorded data points with window length of 6: note that we record the results every 100 rounds (that is, one epoch). The shaded areas show the standard deviation across 5 random seeds.
64

---

J Additional Extensions of SGD
In the main body, we considered periods of the same size as an epoch, which sufficient for the convergence of permutation-based SGD. In fact, we can consider periods of arbitrary fixed sizes, by which we can extend the framework to include classic SGD. This mainly relies on the techniques developed in Lu et al. [202bb], Wang and Ji [0222] and Koloskova et al. [2024].
J.1 Results
Let the size of the periods be E, which can be different from the epoch length N. To extend the results developed in the main body for this scenario, make the following changes. First, before stating the adjusted results, we redefine some notations, that is, to reformulate those defined over "epochs" in terms of "periods". For instance, the order error og in any period q is defined
0g = max
Σ (x -
cE[E]
where Ty denotes the order in period q and x, means the initial parameter vector period q. See Definition for comparison. Furthermore, we need define
Σ -
max ge 10. Q-1..----111
where x denotes the parameter vector after e steps in period q.
Theorem provides the extended framework for SGD.
Theorem 4. Let the global objective function f be L-smooth and each local objective functions fn
be L22g-mmooth and Sm--th (p 2 2). Let 2 0 be a numerical constant. Suppose that there exist and D such that for O S q S v 1
(0,)² S (I
and there exist {A,) (B.) and D such that for q 2 v,
(²,)² 2 < Σ
A )
-1) + + B₁ 11VV 1)12 D.
1=0
v VI-E Ai V1-Eis1
Ifr S min
then
LE , 412,
Dizo Bi¹
AL2.VB
+33b
Q-1
(x,,)) 2 < 10
Fo
tc.
L o + c. ? D+ 10 E
(v
Q 4=0
EE
where 30/ 30/1->x-,11 A.) a numerical constant.
When E a multiple of N ( = =0), Theorem is reduced to Theorem including the permutation-bant based SGD algorithms. When E = θ 7 (w, is allowed to be nonzero). we can obtain the convergence rates of AP (Proposition 11 and classic SGD (Proposition 12 As shown in
Table theses rates match those Koloskova al. [2024).
Assumption 4. There exists nonnegative constant 5 such shatffr any n E 1..,, N - 1}.
fx) Vf(x)) 2 VX V..
Proposition 11 (AP). Suppose that Assumption 4 holds. Then, we can obtain that, for q 2 0.
(3,)² 2 S 22
22F52.am .and th S 2
Applying Theorem choosing E = O(L 111 and tuning the step size, for E < H. we obtain
3
$ 1).
LFo min
(LFONS)
LF
{
(0........11
T
T
where Yt denotes the model parameter vector in iteration t.
65

---

Proposition 12 (Classic SGD). Suppose that Assumption 4 q 2 with probability at least 1 6.
holds. Then, we can obtain that, for
(Ø,)² S ECC, and vi S EO52.
where C = 9 (g)) Applying Theorem choosing E' - O (((,,,) and tuning the step size, for
E S 2' we obtain that, with probability at least Tö,
LFo
LFos² T
[V O
min
(E (0.
where denotes the model parameter vector in iteration t.
At last, we discuss Theorem and the technique of setting E = 0 [;:):
For classic SGD, Theorem 4 does not require the unbiased condition, which often used in the convergence analysis of classis SGD [Ghadimi and Lan 2013]. This motivates a new approach
for the convergence analysis of Markov chain SGD Even 2023 Beznosikov et al. 2023 Koloskova al. 2024], where the unbiased condition is not satisfied.
The standard approach (analyzing convergence over periods based SGI) causes constraint of ry LE & 1. In the main body, E === N, causing the constraint on the step size LLN 11 which finally leads a worse bound on the optimization term (See the "AP" row in Table I). As noted in Koloskova et al. (2024), we can set E = = 9 to
fixed size E) permutation-
circumvent the constraint of LEE x leading better bound the optimization term for AP (Proposition] 11
For AP, whose permutations are arbitrary (without any specific structure), analyzing conver- gence for arbitrary E will not affect the statistical properties of these permutations. However, this does not apply to IP and DP. Take IP as an example. For IP, whose permutations are independently generated across epochs, analyzing convergence for E e (E does not necessarily equal N) will compromise the nice statistical properties of these permutations: The elements in different permutations may be divided into the same period and the elements in one permutation may be divided into different periods.
For the cases E e (,)) Theorem and the previous works Wang and Ji 2022 Koloskova et al. 2024 use Assumption 4 which is stronger than Assumption used the cases E 18 multiple of (in the main body).
Compared with Koloskova al. 2024], one additional constraint E required for ours (Propositions and and Wang and 2022
Table 8: Comparison of convergence rates (of AP and classic SGD) with Koloskova et al. 2024 Numerical constants and polylogarithmic factors are hided.
Algorithm
Koloskova et al. [2024]
This work
AP
LE. T
+ min
(LPINs)
[F,N.
(1)
LE min
(LR.Ns)
(LFIN(2)
Classic SGD
+ LEUs"
8(1
LF
LF 2) 8
These bounds for 7 ET- flr)) and do require the additional constraint E T. Therefore, these factors taken into consideration, the bounds of Koloskova [2024) better than ours.
These bounds for m To11 IV [V((y.)| and require the additional constraint 4.
J.2 Proofs
This section provides the proofs of Theorem 4 and the helper lemmas for Theorem
Lemma 8. Suppose that there are n vectors Xo, Xi.... . Xn-1 E IRd such that 1 E x; = and
|x, 2 < 2 for any {0, (0. 1}. Suppose that the indices a sampled uniformly at
66

---

random from 10,1...., 1} with replacement in an i.i.d. manner. Then, for any integer m 2 1, the following inequality holds with probability at least 1 8:
m-11
S 9ms 2 log"
x
1=0
Proof. The proof modified from Yu and Li 2003 the matrix
Proposition 2.3]. For any i {0, .....,,., 1},
X
0
Oaxd
x,
E pdd+1)x((+1)
x
can be constructed. It can be obtained that
X ll2
=
||x
S
Σ X
ns²
1=0
Then, applying Yu and Li 2023 Lemma 2.1] (it also holds for sampling with replacement) with n252 b 5, obtain
m Σ 1=0
S 4dexp (-
82/2
= 4dexp (-ms² $2/2 ms² + 5s/33
P
X (())
2 8
Am/n + bs/3
2
Solving 4d exp
2/22 +s3++e/3
I 8 yields s 2 log( 4d
+ v 52 log"? ( + 2mm² log( 4d Using
ms
log( dul) obtain
> 1, we obtain that if s 2 3/ms log( 4d), then 4dexp
(- (-ms= S 8. As result, we
m 1
4d
Σ
x
xx(() (1)
2 m/ log
S 5.
i=0
Using
EnT
Xx()
(1)
=
xx())
and d = 2, we obtain the claimed result.
2
2
Proof Theorem
For SGD, the cumulative updates any epoch are
Xq+1 Xx
(xz()))(x))
(36)
e=0
Since the global objective function f is L-smooth, it follows that
f(x++1) & f(xg) + (V)(x),, - xx) + / |x - xx,12
(37)
Using Equation (36
obtain
(V)(()), X
x,)
E
=
V)(x)),
V
(x)())
E
e=0
E-1
E-1
V
V (x,)
+ 2
V
(x)
- V v((x))
2
E
2
E
==0
==0
where the second equality uses 2(x,y) ||x|| 2 ||yl1" 11
||x -
y11
Using Equation 36). we obtain
F-1
1
1 3ラ
L
[1xx+11101
-
LE
V
2
E
67

---

Next, plugging the preceding two equalities back in to Equation
37 we obtain
1
f(xx+1)= - f(x)) + (Vx() Xx+1
xx)
- |
x11 2
1
1 E
s fx²x)
2 [I [x,
[V,,(
27
2
>LEEE
V fr (c)()) (xg)
+ 1
1
V (x)
-
{)(xa))
E ==0
Since yLE S 1, we obtain
1 E-1
[(x++)) S f(xx)
+
Σ
V
(x,) -V((x)
(38)
2
E
c=0
Since each local objective function fn is
we obtain
E-1
1
T3 in
38
27F
E
V
v1((p)
2
E
E
E-1
(x (x,)
V
(xx)
E
E c=0
c=0
E-1 1
+ 7
(e, (x₂) - fxx,)
E e=0
E-1
Σ
| x1l1, + +7 (2:
1
S 2.22
S E + +
E (w)))
This is the key change of the proof of Theorem 4 compared to Theorem inequality back into Equation 338) we obtain
Plugging the preceding
f(xy+1) S f(x,)
1
E E V f(((x)))' )11 713 EA,)) 2 + +7 E (v,7)
2
S fxx,)
E7E(
(1 6-
2,p (x,,) 11 + + 13 E (ōx))
+ +7 (1/))
1
S f(x,)
1024" 7 fx(xx))) 211 3y 3 L3 E (0.)) + +7 (vg)²
509
1
where the second inequality uses Lemma and the last inequality uses LL2 S 32 Notably, the resulting inequality is almost identical to Equation
except an additional term 7 (vz)² The
term (w.)² will not be dealt with further in this theorem, so the remaining steps of this proof are almost the same as those in Theorem I For these reasons, we omit the remaining steps.
To prove Theorem 4 we require the following lemma. In particular, we define the maximum param- eter deviation (drift) in any period g, A, as
A,
max
x x x=I1p
cE[E]
Lemma 9. Ef S $.2 the maximum parameter drift is bounded:
32
32
Ag <
yo, +
E V fxx()))l |||
31
31
(A,)² S 33 (o,)²
2 +332 fxxx))l ||?
68

---

Proof. The proof is identical to that of Lemma 6 except that the epoch-based notations are replaced by the period- period-based based notations.
Proof of Proposition 17
For any E {0, 1. ......Q.......
Q - 1} and e E [F].
(6))
(= - vf(x,))
I 4minnEE
(39)
i=0
See the detailed analyses of Equation 39 in Koloskova et al.
2024 Appendix C. Proofs of the
bounds in Table 2] and [u et al. 2022b
Appendix A.5, Justifications for Assumption 2 under
various example orderings].
In this proposition, for Theorem 4 min E, N52 These lead to
2, = 0, D = 4min(E,N)Ns,.. 30 and v/
? [V((x))
Fo <EQ
+ m NN., + E min
min
with the constraint 7 32LE
Then, choosing = 1.2yr.1.
= J. we obtain
1 Q-1
[x(x,)1 =0
+ min m (1/Fo
Fo 7E
Q
Using y S T. which is due to == 12yT, L 2 1, and applying Lemmas and
we obtain
3
LFo EQ
{
LFoNs) EQ
+
min
EQ
Given that ? can be chosen different in different propositions, EQ (E is chosen according to y) can be different in different propositions. To ensure fair comparison between algorithms, we use the total number of iterations 7 instead of NQ in the bounds:
min 1-
[V <
min LE (E
fy:)(1
1-1}
min
Q-1 [x,{(x))1
(0.
[x(22)11
q=0
I.Fo T
L.FoNS T
#
(
$
1)
0
+
min
T
where yt denotes the model parameter vector in iteration and the last equality uses
11 S
QE
when E S T Wang and Ji 2022
Appendix C, Proofs].
Proof of Proposition 12
For any E {0, 10.1.....2
Q 1} and E [E].
(o:)== = Σ
V (o, (x₂) vf((,)) 8
< ECS?
(40)
==
where C= (g)) and the last inequality uses Lemma
In this proposition, for Theorem = 2, v 0, NCS2,
30 and 1/ FCS2 These give
Q-1
[V = Fo
1 )
+
22
7BQ
0=
69

---

with the constraint 7 S 32LE Since Equation (40) is used for each period (that is, for Q times), by the union bound, the preceding bound holds with probability least 1 Q6.
1
Then, choosing = 12 J. we obtain
Q-1
Fo YEQ
+
Q 8=0
Using Y S (due to E' 2 1) and applying Lemmal)
! we obtain
I.Fos² $
1
IV [V
I.Fo EQ
+
Q 4=0
EQ
To ensure fair comparison between algorithms, we use the total number of iterations 7 instead of NQ in the bounds:
LFo
LFFs
min
| [V
(0, 7.......11
T
where Yt denotes the model parameter vector in iteration
K
Additional Extensions of FL
In this section, extend the framework cover the independent client participation pattern in Karimireddy et al. 2020). Yang et al. [2021) and Wang and [022] with the same way studied in Appendix
K.1 Results
Similar to Appendix J "epochs" in terms of "periods". For instance, the order error og in any period q is defined
we redefine some notations, that is. to reformulate those defined over
[(c)-1
Pq = max E
Σ
(V)n,()((g))
-V)()x)))((())))))))) v((x,))
T=
where Tg denotes the order in period and X2 means the initial parameter vector in period q. See Definition 2 for comparison. Furthermore, we define
Σ VS,( Vf(x,)
(o.
where x, denotes the parameter vector after & local updates in client n in epoch q.
Theorem 5 provides the extended framework for FL, which covers the independent participation
pattern (Propositions) 13 and (4).
Theorem 5. Let the global objective function f be L-smooth and each local objective functions Jn be p2 smooth and Lp-smooth (p 2 2). Suppose that Eesumptionnholde Suppose E mod S 0.
Let v 2 0 numerical constant. Suppose that there exist ß and D such that S S v 1,
(gg) < B [Vx((x)) + +D,
and there exist {Ai). (B.) and D such that for q 2 v,
(g,)² A ) Σ
B: V V (x( D.
1=0
V- V-
If < min
1
Ei 41,,, V 32 then
1
gLKEY 32 A
51%
1 1
V Tfxxx,111'
2 L2
2
+ 20,
Q
mKE
5 Q
+
t K2
D
+5
1
(vg)
52
F
where 10/(1-1/ As) is a numerical constant.
70

---

When E is multiple of N (, = 0), and Theorem is reduced to Theorem covering the examples in FL with regularized participation. When E = ( (2/ is allowed to be nonzero), obtain the convergence rates of FL with independent participation. Two strategies appeared in previous works are considered (see Propositions) and and The comparison of convergence rates
2022 are provided in Table Note that with the previous works (Yang al. 2021 Wang and Ji
the assumption that the clients are selected according to Equation (46) is also used in Wang and Ji
[202]] Proposition 4.7]. See the statement in Wang and Ji 2022]: "In the following, we assume that M4, Is chosen such that Pto = E[g""] for all n. E (L.....,N and {to,4o + L,... 1,...,to to + - 13".
Proposition 13 (Strategy 1). Let the clients selected uniformly at random with replacement in each round, independently across rounds. Suppose that Assumption holds. Then, obtain that, for q 2 0, with probability at least 6.
(pa)² S ECS2, 3BCS2,and .and v.g $ EC52
where (g). Applying Theorem choosing = 6 ((1 and tuning the step size, for S
T
2. we obtain that, with probability at least T5,
$
LFos 2 3
LFo T
LFos
min 1E(0.I....TII1
+
ST
where Yt denotes the model parameter vector in round
Proposition 14 (Strategy 2). Let the clients be selected in manner that satisfies Equation (46) in each round, independently across rounds. Suppose that Assumption 4 holds. Then, we obtain that, for q 0. with probability least -
( < ESCS2, and v < ESCs2
where C = (8). Applying Theorem 5 choosing E = O ( and tuning the step size,
for 5 I 2. we obtain that, with probability at least T5,
I.Fo +
L.oos T
$ +
I.Fos $
min 1610.1...TT11
T
where denotes the model parameter vector in round t.
Table 9: Comparison of convergence rates (of FL with independent participation) with previous works. Numerical constants and polylogarithmic factors hided. We set for comparison.
Algorithm
Previous works
This work
Strategy
LE
(FFs))
LF ST
LE
LF ST
Strategy 2
LF LPgs)
LF ST
2(2.)
LF. LFgs)
LFas
This bound from Yang et al. [2021
Theorem 2]. This bound is + E [(v(())) and do require the additional constraint _ Therefore, these factors are taken into consideration. the bounds of Yang et al. [2021] are better than ours.
These bounds is for min mint (u.1..... T-1) [|+/(x))) and requires the additional constraint 3 < T.
This bound is from Wang and Ji [0222]
K.2 Proofs
This section provides the proofs of Theorem 5 and the helper lemmas for Theorem To avoid ambiguity, we define
Xg+1 == x E-1 9.K
x 9.0-
71

---

Due to the amplified updates (Wang and Ji 2022].
we have
E
K-1
1
x++1 - X, = -y
(ex(()) (x
5
<= k=
E-
K-1
1
x - X4 = ー
Σ
Σ
((
(x
c=
k=
We define the maximum parameter deviation (drift) of FL in any period g, Ag as
A = max
max DE (O...... E-1...,111 ke (o......,K K
| xellp: 11:1111111 xzll
Then, obtain the relation
|x xzllp = 1) || Xgllp S ndr
Lemma 10.
H S
and E is a multiple of S, the maximum parameter drift in FL is
32
bounded:
32
32
32
4 S
K
5
+
KE
|V
KKs,
31
S
31
S
31
(A,) 2 K2 1
1
(9a)
K
[V(x,,]
g2
5
Proof. The proof is identical to that of Lemma 10
except that the epoch-baser notations are replaced
by the prriod-baséd notations.
Proof of Theorem 5 For FL with regularized participation (Algorithm 2. the cumulative updates over any period g are
N-1K-1
Xg+1 Xg - -
ΣΣ
Vir((n)) (xg.t)
(41)
n=0 k=0
Since the global objective function f is L-smooth, it follows that
1 L |1 -x,1?
[xx++1) f(x,) S (VI(x)),
Xpp11 Xp+1 xx) +
(42)
2
Using Equation 41 we obtain
V (x,) Xp+1 - x,)
E
K-
1
=-17 KE
[)(xx)
v
F
K
em0
k=
K-1
1 1 --Σ 3 K /
1
1
12
F
(x
F
K
c=0
k=0
1 1 + ッ
KE
E
V
(c) (x v fx(,))
K
e=0
k=0
where the second equality uses 2(x,y)
||x||
2
||y 1| ||x y112.
Using Equation 41
we obtain
1
1
E- K-1
L ||x - x,11²
-
M
V V (x)( (xg
2
2
e=0
k=
K
1
1
E²
V (x
2
52
n=0
k=
72

---

Plugging the preceding two equations back into Equation 42
and using mLLK S I 1, we obtain
[(x++1) - ((x,)
E-1 K-1
- 2 2 KE VV )2
1
+
2 S
1 2
KE
Σ
V
(0)
V5(x2)
(43)
E e=U
K
k=0
Then,
E-1
1 1 2 5
1 E 7-11
T2 in
KF
(x vf(xp)
K
1 F
K-1
F-1 K
1 $ Mi
V ( (x
V f (xn)
E
E
K
e=0
k=0
E
K
+ 3 KE
V (x - (\(xx) -V/(())
k=
E- 1 K-1
$ $mII2 S
X x
c=0
k=0
E-1 K-1
+ s
KE
(x)) fx(x))
E
K
e=0
k=0
$ 1 KE
(A,)² + mK
(v:9)²
S
ES
where the second inequality is because (e,(e) is L2, smooth and the last inequality uses the defini- tions of Ag and o.. Plugging the preceding inequality back into Equation 43 we obtain
1 1 fxx++1) - f(x,) S -""
(ETSSEIIV<>))) + mL2 KE E 1 (An)² + mn 1 ES (w)))
5
Using Lemma 7 and .N.2,NKK S 32.
we obtain
127
1
K
E
[
K3 E + L
5 (p,)
256
S
+ + n1 K2 E 1 +
2 +m
ES
Note that the preceding inequality almost identical to Equation 25 except an additional term
yn ES (w²)² 2 The term (wit) will not be dealt with further in this theorem, so the remaining For these reasons, we omit the
steps this proof are almost the same as those in Theorem 2 remaining steps.
Proof of Proposition 13 For any g (0,1...,.2
Q- 1} and [E].
12
v())-1
2
(V -vfx))
S FCC2
(44)
where = (g) and the first inequality uses Lemma 8
In this proposition, for Theorem p= 22 0, D E c= 10 and v ECs2, These give
1 Q Σ |vf(xx))
Fo
1 _ + 1 E -()
+ + +
mkEEJ
S2
with the constraint y S 3 Equation (44 is used for each period (that is, for Q times), so, by the union bound, the preceding bound holds with probability at least 1 - Q6.
73

---

Then, choosing E = 32yLK |S, we obtain
Fo V fx, o (m<KEj + +
Using 7 S
1_ LK
32yLK 1S2 S), and applying Lemmas andd (due E
we obtain
$ +
$
LFu =
LFos nE
[Vx(x)))
nEQ
9=0
Given that can be chosen different in different propositions, EQ (E is chosen according to 7) can be different in different propositions. To ensure fair comparison between algorithms, the total number of iterations 7 instead of NQ in the bounds:
min
Vf(y:)1 v
min
16. --1
1E(0,
1-1)}
min
[V,(())
QQ........-
Q-1
||,[(x))1
9=0
3
LF%
LFos T/T
LFos2
+
n/T
SS
where yt denotes the model parameter vector in round and the last equality uses
1
S
2 when
E T
[Wang and Ji 2022
Appendix C, Proofs]. We set for comparison:
T
g
2
$ +
LFo
LFos
(FFOs
[f(y.)) Ō
min
T
T
ST
Proof of Proposition 14
For any g (0.1...,QQ 1} and [E].
w(e)-1
(vg(t))
Σ
(V
1=0
u(e)-1
2
Σ
f (=((())++))(x)) - -Vf(x))
ESC
max iE(0,1..,E-1]
V (x) -f
S
S-1
ESCC
max (E(0,L..,E-1)
Σ
(x)) (x(x))
5
ESC
(45)
where C (g) and the first inequality uses Lemma 8 and the condition
S-1
E
V T.
(L.
V f((x))
(46)
S
==0
for any e {0, 10... E 1} and g {0, 1, .... Q 1-1..
74

---

In this proposition, for Theorem = 2 D E = 10 and 2i = ESCs?. These
lead to
Q-1 [V
Fg
Q=0
with the constraint y 3 Equation (44 is used for each period (that is, for Q times), so, by the union bound, we obtain that the preceding bound holds with probability at least 1 Qó. Then, choosing
32yKT. RT, JS, obtain
Fo + 7LKs3
IV [V[(x,)1 1x
Q
9=0
Using y 7
1 LK
(due to E = 32yLK 1 1S S), and applying Lemmas and
we obtain
Q-1
LFo + nE
LFOS nE
LFos² nE
Σ Q=0
[IF((x))
+
To ensure fair comparison between algorithms, we use the total number of iterations T instead of NQ in the bounds. Following the same steps as Proposition 13
we obtain
LFo
LFos 7f
LF
min
Vf(y))] Ö
+
1E.0.1...T-11
nfT
T/T
where denotes the model parameter vector in round f. We set for comparison:
LFo
LFos
3
[Foos
$
min 1ef0.1....T11 T-11
[f(y))
+
+
T
T
T
L Permuuatiio--baeed SGD and Online Learning
In modern large-scale language model training, it may be impossible actually shuffle all the data examples in a very large dataset. In this section. we analyze a hybrid algorithm that combines conmutation-basedd SGD with online learning (Orabona 2019 Hazan al. 2016).
The hybrid algorithm, notations and assumptions. The data examples are sampled from a very large dataset in online fashion. Each time K data examples are sampled (which can be stored in small memory), these data examples are permuted and then fed into the model. For simplicity, we use projected online gradient descent (see Orabona 2019 Algorithm 1]) to train this model with shuffled examples. The details are Algorithm 13 which combines Algorithm aadd Orabona [2099] Algorithm 2.1]. Intuitively, Algorithm 13 hierarchical algorithm where the top-level part is projected online gradient descent and the bottom-level part is permutation- based SGD.
In this section, we need to redefine some notations. We call each group of K examples block, indexed by q. We use (k)(k) to denote the loss function of the k-th example in block q. where my
the permutation in block We use Fg * Σ K-1 -1 fi to denote the loss function of the block q- We use denote the iterates: x denotes the iterate in example and block and X, denotes the initial iterate in block g.
Algorithm 13: An algorithm that combines permutation-basel SGD with online learning
Input: V. mo, X0 V
Output: {x,}
for = 0,1,,.., 1 do
2 Sample examples in an online fashion
for k = 0, 10,1,... K do
4
x++1 t- x² (
Xq+1 <- (x = arg min min yev 1x - y
Mg+1 f Permute(...
75

---

The assumptions are as follows:
Assumption 5. All iterations V, where V is closed convex with diameter D.
Assumption 6. There exists constant a such that for any q E {0, , 1},,
[V),(x))1 E o², Vx Rd
where F2(x) t En=o (x().
Assumptions 5 are used in Orabona
2019
Theorem 2.13].
Definition 4. The order error in any block q is defined as
k-1 (
(x) VFg(Xa))
6 = max KE[K]
Assumption 7. There exists a constant & such that for any q 10,1,...,QQ 1} and l {0, 1, K 10,,,..,,K-- 1-
[V) (F Vx Rd
Regret analysis. The average regret bound of Algorithm 13 given in Theorem Suppose that Assumption 7 holds, we can obtain the bounds of by for AP and IP (as in Appendix by which we can further obtain the average regret bounds for AP and IP. These bounds imply that a nice permutation (the value of by is small) will lead to a nice bound. Thus, shuffling subset of the dataset can also help improve the performance. Notably, in online learning, the examples appear only once, which means that the information gained from the previous blocks may not apply to the subsequent blocks. As a result, the original DP algorithms cannot be applied for online learning. Given the complexity, we leave DP to future works.
Theorem 6. Suppose that Assumptions 5 and hold. The average regret bound of Algorithm B3
Q-1
D2
Σ
VF(())) S 2TKQ + L + 27
where u E V is an arbitrary competitor.
Proof. This analysis is based on Orabona 2019 Theorem 2.13].
|xx+1 u112 |xC
[I
u
||x, ull
|
||x,
ul|
K- 1
$ ||x; -
8 (k) (x/) - -ul2 ||x, - ull
k=0
K-1 I
+ 2 K
< 2y
(xq
u,
V (k)
(xx))
(k) (x+))1 (47)
k=
k=0
where u E V is an arbitrary competitor, and the first inequality uses Orabona 2.11]. Then, using Karimireddy et al. [2020) Lemma 5], we obtain
2019
Proposition
K-1
T in 47
27
{xq
VJ (a) (x,,)
k=
K
S 22
Σ
[[,(k)(xx) (x,) - -52,(e)(u) - -I1[xx xx, xx((²)
k=
K-1
=-27K (Fg(Xg) (u() + 2
Σ
||
xx
xg ?
k=
76

---

and
T2 in
47
2
My (k) (x
K-1
K-1
K
< 27²
V
(x5)
n (x) (X,)
+ 27²
Σ
V f
(xn)
x (R)
k=0
K-1
-,
x
27 K
K
S 2
|
+2
k=
Plugging the preceding two bounds into Equation 47 we obtain
|x u/1 || ull
S 2 (x,()en) (u)) + 2 LK)
|
x,l| + +22 K20² 2222"20'-
Note that Lemma applies the local updates (Lines 3 in Algorithm 13 and then obtain
||xx+11 - ul| - 1|xg - ull
S -2 (F, (x,) - Ful) + (1 +>LK) 222K202
s -2nK (F2(xg) 1..-FF. -Fy(u)
+ (1 +TLK) (37² (3x) +3 1VE, (VF,,, + +222K202
< 2y (F,( - (u)) + 2 (6,) +44 [ )l( [ 2222"20
< 2YK (Fg(x,) (u)()) + 4 (0,)) + K2O
S -2N (F, - (u)) LK (0,)² + +3 K2
where the first inequality uses the definition 4 max || x2 11 the second inequality uses Lemma the third inequality uses LLK 32 fifth inequality uses yLK & 32 Then,
the forth inequality uses Assumption and the
Xg+1 u/12
Fx((x)) (u)
Xg
+ ( + +2yKo²
27
2~
Averaging over q the preceding inequality, we obtain
Q-1 (Fg(x,)- - FF(())
< ||xo
--/²- -ul ull
+ + (0n)² + 22
2yKQ
D2
+ +2 (7,)² + 2-Ko²,
where we use Assumption 5 Applying Lemmas [ [addd 2 we obtain the average regret bound
1 Q-1
LD² [
VVDD'O
+ =000))
$
Σ (F,(x,)) - F.()))
+
KQ
77

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Answer: [Yes]
Justification: We claim that we provide a unified analysis for permutation- based SGD with arbitrary permutations of examples and a unified analysis for regularized client participa- tion FL with arbitrary permutations of clients in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
It is fine to include aspirational goals motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yss]
Justification:
We discuss the limitations in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specificatiin, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
78

---

judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We provide the full set of assumptions all the theorems (Theorems 1 and 3) and propositions (Propositions T
2
8 and 10). The proof of The-
orem is provided in Appendix E
The proofs of Theorems and are provided in Ap-
pendix G The proofs of Propositions
5 6 and 7 are provided in Appendix F The
proof' of Propositions
8 and 10 are provided in Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the details of the experiments on simulated data in Section 5 and real data sets in Appendix [ We also provide the codes for the experiments on simulated data the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
79

---

While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results way produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We provide the codes for the experiments simulated data in the supplemen- tary material. We will provide open access to the data and code the paper is accepted.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines buttps://nipt: cc/
for more details.
While we encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips ctrippscc//pblic//gge httpa///ggiideeeeeeeuutttttte ssi http:/iwiissiiinonosooeee onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yss]
80

---

We provide the details of the experiments on simulated data in Section S and real data sets in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [Yss]
We run the experiments for multiple random seeds, and provide the min-max values in the experiments on simulated data in Section 5 and provide the standard deviation in the experiments on real data sets in Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer:
[Yes]
Justification:
We provide the information the computational resources in Appendix !
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
81

---

The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary failed experiments that didn't t make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:///aaaaaaa.cccoooaa//aaaaaa
Answer: [Yes]
Justification:
This work adheres to the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
There are two main contributions in this work: (i) A unified convergence analysis framework for permutation-based SGD with arbitrary permutations of examples. (ii) A unified convergence analysis framework for FL with regularized client participation with arbitrary permutations of clients. This work is primarily theoretical and foundational, it contributes to better understanding of optimization methods widely used in machine learning systems. Thus, we do not feel specific societal impacts beyond those existing in general machine learning and federated learning.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g.. deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks,
82

---

mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses such risks,
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safery filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
All assets are properly cited.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-pes re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's is creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
83

---

Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used
84

---

only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs any important, original, or non-standard components.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy httpp://eeurrpss.c/oootrrrorr 20tp:/2225/22// /LLM) for what should or should be described.
85


Reviews:
[{"review_id": "o29I1Zpqeq", "reviewer": "Reviewer_ediT", "summary": "This work focuses on the analysis of permutation-based SGD. The authors propose a framework that enables a unified analysis for the three categories: arbitrary permutations, independent permutations, and dependent permutations. They address the dependency of permutations by introducing a more general assumption. They extend the analysis to Federated Learning scenarios where client permutations are considered. The framework establishes new convergence rate results and also results that are consistent with existing works.", "questions": "Corresponding to the weakness, is there any hidden factors that prevent one from choosing, e.g., $\\delta = o(1/Q^2)$ so that the bounds will hold with higher probability with increasing $Q$?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The paper is well-structured and clearly written.\n2. The provide extensive comparisons with previous work.\n3. The authors propose a more general assumption that leads to a unified theorem for all three classes of SGD with data permutations. Mainly, the assumption accounts for dependency of the permutations between epochs.\n4. The authors define a new order error for Federated Learning and extend the techniques for analysis of the convergence of FL with regularized participation.\n5. The authors apply their main theorems to analyze multiple existing algorithms. They show that the results match the existing bounds. They also establish new results for methods that previously lack convergence guarantees (namely, FL-GraB), which indicates the effect of client ordering in Federated Learning.\n\nWeakness:\nThe probabilistic bounds becomes less and less effective with increasing $Q$ due to $Q \\delta$.", "was_revised": true, "final_justification": "The authors have addressed my concern. I'd keep the original score.", "rebuttal": "> Weakness: The probabilistic bounds becomes less and less effective with increasing $Q$ due to $Q\\delta$.\n\n> Corresponding to the weakness, is there any hidden factors that prevent one from choosing, e.g., $\\delta=o(1/Q^2)$ so that the bounds will hold with higher probability with increasing $Q$?\n\nAs noted, our current version uses a failure probability of $Q\\delta$ rather than $\\delta$, which could lead to looser bounds as $Q$ increases. We adopted this formulation primarily to maintain consistency with [A1,A2], which established initial bounds for GraBs.\n\nHowever, we would like to clarify that our framework can provide bounds that hold with probability $1-\\delta$, addressing your specific concern. Given that the bound for Arbitrary Permutations (AP) is deterministic (not a probabilistic one), we next only discuss Independent Permutations (IP) and Dependent Permutations (DP):\n\n1. IP. Taking Random Reshuffling (RR) as an example. Starting from Equation (12) in this paper, we get that, with probability at least $1-\\delta$, $(\\bar \\phi_q )^2 \\leq 4\\log^2(\\frac{8}{\\delta})U $, where $U=N\\alpha^2\\\\|\\nabla f(x_q)\\\\|^2 + N \\varsigma^2$ for brevity. That is, $\\Pr( (\\bar\\phi_q)^2 \\geq 4\\log^2(\\frac{8}{\\delta})U) \\leq \\delta$ for any $q$. Then, applying the union bound for $q=0,\\ldots,Q-1$, we get $\\Pr( \\exists q, (\\bar\\phi_q)^2 \\geq 4\\log^2(\\frac{8}{\\delta})U) \\leq Q\\delta$. Then, setting $\\delta = \\frac{\\delta}{Q}$, we get $\\Pr( \\exists q, (\\bar\\phi_q)^2 \\geq 4\\log^2(\\frac{8Q}{\\delta})U) \\leq \\delta$. That is, with probability $1-\\delta$, $(\\bar\\phi_q)^2 \\leq 4\\log^2(\\frac{8Q}{\\delta})U$ for all $q=0,\\ldots,Q-1$. Then, using these bounds, we get the desired bound that holds with $1-\\delta$.\n2. DP. Taking GraB-proto as an example. Starting from the equation between Lines 764 and 765, we get that, with probability $1-\\delta$, $(\\bar\\phi_q)^2 \\leq \\log^2(\\frac{dN}{\\delta})U + V$ where $U = 900(\\alpha^2\\\\|\\nabla f(x_{q-1})\\\\|^2 + \\varsigma^2)$ and $V = \\frac{3}{4} (\\bar\\phi_{q-1})^2 + \\frac{1}{50}N^2\\\\|\\nabla f(x_{q-1})\\\\|^2$. That is, $\\Pr( (\\bar\\phi_q)^2 \\geq \\log^2(\\frac{dN}{\\delta})U+V)\\leq\\delta$ for any $q= 1,\\ldots,Q-1$. Then, applying the union bound for $q=1,\\ldots,Q-1$, we get $\\Pr( \\exists q, (\\bar\\phi_q)^2 \\geq \\log^2(\\frac{dN}{\\delta})U+V) \\leq (Q-1)\\delta$. Then, setting $\\delta = \\frac{\\delta}{Q-1}$, we get $\\Pr( \\exists q, (\\bar\\phi_q)^2 \\geq \\log^2(\\frac{dN(Q-1)}{\\delta})U+V) \\leq (Q-1)\\delta$. That is, with probability $1-\\delta$, $(\\bar\\phi_q)^2 \\leq \\log^2(\\frac{dN(Q-1)}{\\delta})U+V)$ for all $q=1,\\ldots,Q-1$. Then, using the bound of $(\\bar\\phi_0)^2$ (it is deterministic) and these bounds, we get the desired bound that holds with $1-\\delta$.\n\n[A1] Lu et al., GraB Finding Provably Better Data Permutations than Random Reshuffling, NeurIPS, 2022.\n\n[A2] Cooper et al., Coordinating Distributed Example Orders for Provably Accelerated Training, NeurIPS, 2023.\n\n[A3] Yu and Li, High Probability Guarantees for Random Reshuffling, NeurIPS 2023 Workshop Heavy Tails in Machine Learning, 2023."}, {"review_id": "P7goVUJiMv", "reviewer": "Reviewer_iP1W", "summary": "This paper gives a unified framework for studying different permutation-based algorithms. The framework is general enough to include arbitrary parameter orders, random reshuffling, and some adaptive shuffling algorithms such as GraB. The main novelty is in Assumption 2-- It connects the gradient error (difference between shuffled gradients and the true gradients) over an epoch *between* epochs. It vaguely reminds me of some of the unified assumptions made in prior work in other contexts like federated learning [1] where the gradient error at epoch $k$ is related to the error at epoch $k-1$. Theorem 1 gives a convergence rate under this assumption in the nonconvex and smooth setting, and is specialized to various algorithms in Propositions 1-7. Not all of these results are restatements of existing results, as e.g. for FlipFlop and PairGraB. Finally, the results are directly applicable to the case when the different \"data points\" represent clients in a federated setting, and we can control how we sample them.\n\n[1] Gorbunov, Eduard, Filip Hanzely, and Peter Richtárik. \"Local SGD: Unified theory and new efficient methods.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.", "questions": "1. Can your analysis extend to a sort-of hybrid algorithm where we choose a number (say $K$ that is smaller than $N$), sample $K$ differrent data points and then shuffle them? This might be more relevant to modern large-scale language model training.\n2. Can your analysis be used with the shuffling variance technique of [3] to recover the $1/(NQ)$ dependence at least in the strongly convex setting?\n\n[3] Mishchenko, Konstantin, Ahmed Khaled, and Peter Richtárik. \"Random reshuffling: Simple analysis with vast improvements.\" Advances in Neural Information Processing Systems 33 (2020): 17309-17320.", "limitations": "N/A.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "1. (Strength) The framework is quite elegant and unifies many existing results. It provides a direct point-of-view as to *why* methods like GraB work. I actually like that no new methods are introduced here, it is relatively rare to see papers that do a good job at taking a field with a diverse number of methods and find a unifying framework to look at them.\n2. (Strength) The paper provides a new analysis for PairGraB, a practical variant of GraB that was not analyzed prior.\n3. (Weakness) The paper's analysis framework is to treat all of these methods as equivalent to doing one large step of gradient descent plus deviation error. Unfortunately, this means that all the convergence results obtained here outperform SGD only in the same regime that GD outperforms SGD, and underperform SGD in the regime when SGD is better than GD. This can be seen from e.g. the last column in Table 1, where the paper's leading term scales as $1/Q$ rather than $1/(NQ)$ as in the analysis of [2]. This is unfortunately common to a lot of the literature on RR.\n4. (Weakness) The relevance of shuffling-based algorithms to modern training is a bit in doubt, since now we've looped back to the case where datasets are far too large to actually shuffle through and we instead rely on sampling. This isn't really this paper's fault though but is a more generic concern. I guess I would ask: how might we use some of the insights here to develop methods where shuffle only a subset of the dataset?\n\n[2] Koloskova, Anastasia, et al. \"A unified theory of decentralized SGD with changing topology and local updates.\" International conference on machine learning. PMLR, 2020.", "was_revised": true, "final_justification": "The paper is good and the authors have addressed most of my concerns in the rebuttal.", "rebuttal": "> ... the paper's leading term scales as $1/Q$ rather than $1/(NQ)$ as in the analysis of [2]...\n\n> Can your analysis be used with the shuffling variance technique of [3] to recover the $1/(NQ)$ dependence at least in the strongly convex setting?\n\n1. The shuffling variance technique [B1] cannot be used to achieve the better bound in the strongly convex setting. The failure is primarily due to technical reasons arising from the incorporation of DP. We provide the details in Detail 1.\n2. Another technique developed in [B2] can be used to achieve the better bound $1/(NQ)$ for AP in the non-convex setting; however, whether a tighter upper bound can be achieved for the other algorithms (i.e., IP and DP) remains an open problem. We provide the details in Detail 2. In this paper, given that this advanced technique [B2] (i) only applies to AP and (ii) can complicate the framework substantially, we did not use it in the current version.\n\n**Detail 1: Details for using the shuffling variance technique in the strongly convex setting.**\n\n1. Since the shuffling variance technique only applies to the strongly convex setting [B1], we assume the strong convexity of all local functions and the existene of the minimizer $x_\\ast$ of $f$.\n\n2. In the strongly convex setting, we need a new definition for the order error $(\\bar\\phi_q)^2 = \\max_n \\\\| \\sum_{i=0}^{n-1} ( \\nabla f_{\\pi_q(i)}(x_\\ast)-\\nabla f(x_\\ast) ) \\\\|^2$. A similar assumption is made as $(\\bar \\phi_q)^2 \\lesssim (\\bar\\phi_{q-1}) + (\\bar\\phi_{q-2})+\\cdots+(\\bar\\phi_{q-\\nu})+\\cdots+ D$ ($\\nu$ is a numerical constant).\n\n3. To deal with DP, we need to define a more general shuffling variance (associated with the epoch $q$), $\\sigma_q^2 = \\max_{n=1,\\ldots,N-1}[\\frac{1}{\\gamma}\\mathcal{D}\\_{f\\_{\\pi_q(n)}} (x_\\ast^n, x_\\ast) ]$ ($\\mathcal{D}$ denotes the Bregman divergence, $N$ is the total number of local functions). When $\\sigma_q$ is independent of $q$, it reduces to the original definition in [B1]'s Definition 2. According to [B1]'s Proposition 1, we get that $\\sigma_q^2 \\leq \\frac{1}{2}\\gamma L (\\bar\\phi_q)^2$.\n\n4. Let us focus on the [B1]'s Theorem 1. See [B1]'s Equation (23). It is safe to follow the same steps as [B1] before Equation (23). For $\\sigma_q^2$, we get the following equation rather than its Equation (23):\n   \n   $$\n   \\begin{align}\n   \\mathbb{E} \\\\|x_Q-x_\\ast \\\\|^2 &\\leq (1-\\gamma \\mu)^{NQ} \\\\|x_0-x_\\ast\\\\|^2 + 2\\gamma^2\\sum_{n=0}^{N-1}(1-\\gamma \\mu)^n\\sum_{q=0}^{Q-1}(1-\\gamma\\mu)^{N(Q-q-1)}\\sigma_q^2 \\\\\\\\\n   &\\leq (1-\\gamma \\mu)^{NQ} \\\\|x_0-x_\\ast\\\\|^2 + \\gamma^3L\\sum_{n=0}^{N-1}(1-\\gamma \\mu)^n\\underbrace{\\sum_{q=0}^{Q-1}(1-\\gamma\\mu)^{N(Q-q-1)}(\\bar\\phi_q)^2}_{T}\n   \\end{align}\n   $$\n   \n    We see that when $\\sigma_q$ is independent of $q$ (the case in [B1]), as done in [B1], we can get that the second term on the right hand side is upper bounded by $2\\frac{\\gamma}{\\mu}\\sigma^2$. However, $\\sigma_q$ varies with $q$ and is bounded by $(\\bar \\phi_q)^2$, which relies on the order errors in the previous epochs (e.g., $(\\bar\\phi_{q-1})^2$).\n\n5. Next, our goal is to use the assumption that $(\\bar \\phi_q)^2 \\lesssim (\\bar\\phi_{q-1}) + (\\bar\\phi_{q-2})+\\cdots+(\\bar\\phi_{q-\\nu})+ D$  to bound $T$. As shown in Theorem 3 in this paper, it requires that $\\frac{1}{(1-\\gamma\\mu)^N}\\leq c$, where $c>1$ is a numerical constant. Then, using the fact $(1-x)^t\\leq \\frac{1}{1+tx}$ for $x\\in [0,1]$ and $t\\geq 0$, we get $1+\\gamma \\mu N\\leq (1-\\gamma \\mu)^N \\leq c$. Thus, if $\\frac{1}{(1-\\gamma\\mu)^N}\\leq c$, then $\\gamma \\leq \\frac{c-1}{\\mu N}=O(\\frac{1}{N})$. This constraint on $\\gamma$ will cause a worse bound (on the optimization term).\n\n**Detail 2: Details for the technique in [B2].**\n\n1. *The limitation of the standard approach.* As noted, we divide all iterations into smaller chunks (with the same size) and analyze each of the chunks separately. We denote the size of these chunks as $P$. This standard approach in permutation-based SGD cause a constraint of $\\gamma LP \\lesssim 1$. In this paper, $P=N$, where $N$ is the total number of the local objective functions. This causes the constraint on the step size $\\gamma \\lesssim \\frac{1}{LN}$, which finally causes a worse bound on the optimization term.\n2. *The core idea of the new technique [B2].* As noted in [B2], we can set $P=\\Theta(\\frac{1}{\\gamma L})$ to circumvent the constraint of $\\gamma L P \\lesssim 1$. This technique finally leads to a better bound $O(\\frac{1}{NQ})$ for AP. For AP, whose permutations are arbitrary (without any specific structure), analyzing convergence for arbitrary $P$ will not affect the statistical properties of these permutations. However, this does not apply to IP and DP. Take IP as an example. For IP, whose permutations are independently generated across epochs, analyzing convergence for $P=\\Theta(\\frac{1}{\\gamma L})$ ($P$ does not necessarily equal $N$) will compromise the nice statistical properties of these permutations: The elements in different permutations may be divided into the same chunk and the elements in one permutation may be divided into different chunks.\n3. *Use this new technique [B2] in our framework.* One straightforward way to use this technique is to establish the framework for arbitrary $P$, and then use $P$ as a algorithm-specific parameter. For example, for AP, we let $P=\\Theta(\\frac{1}{\\gamma L})$, and for IP and DP, we let $P=N$. Given (i) that using this technique will complicate the framework substantially, (i) that this technique only applies to AP and the main contribution of this paper is to incorporate DP, we did not use it in this version.\n\n[B1] Random Reshuffling Simple Analysis with Vast Improvements, NeurIPS, 2020.\n\n[B2] On Convergence of Incremental Gradient for Non-Convex Smooth Functions, ICML, 2024.\n\n\n> (Weakness) The relevance of shuffling-based algorithms to modern training is a bit in doubt, since now we've looped back to the case where datasets are far too large to actually shuffle through and we instead rely on sampling. This isn't really this paper's fault though but is a more generic concern. I guess I would ask: how might we use some of the insights here to develop methods where shuffle only a subset of the dataset?\n\n> Can your analysis extend to a sort-of hybrid algorithm where we choose a number (say $K$ that is smaller than $N$), sample $K$ different data points and then shuffle them? This might be more relevant to modern large-scale language model training.\n\nThis forward-looking suggestion naturally leads us to consider the integration of permutation-based SGD and online learning [B3,B4]. As far as we know, there is no existing works that combines these two theoretically. So we next try to analyze such a hybrid algorithm that you mentioned.\n\n1. Algorithm. First, we online sample the data examples from a very large dataset. Then, every time $K$ examples are sampled, we shuffle these $K$ examples and feed them to a model. For simplicity, we use projected online gradient descent (GD) (see [B3]'s Algorithm 2.1) to train this model with the shuffled examples. Intuitively, this algorithm is a hybrid algorithm where the top-level part is online GD and the bottom-level part is permutation-based SGD.\n\n2. Notations. We call each $K$ examples as a block. We use $f_{\\pi_q(k)}$ to denote the loss function of the $k$-th example in block $q$, where $\\pi_q$ is the permutation in block $q$. We use $F_q = \\frac{1}{K}\\sum_{k=0}^{K-1}f_{\\pi_q(k)}$ to denote the loss function of the block $q$. We use $x$ to denote the iterates, $x_{q}^k$ to denote the iterate in example $k$ and block $q$, $x_q$ denote the initial iterate in block $q$.\n\n3. Assumptions. We use the assumptions: (i) Assumption B1: All iterations $x\\in \\mathcal{V}$, where $\\mathcal{V}$ is a closed convex set with diameter $D$. (ii) Assumption B2: $\\\\|\\nabla F_q(x)\\\\| \\leq \\sigma$ for all $q$. Assumptions B1 and B2 are standard in online GD [B3, B4]. We also use the order error $\\bar \\phi_q = \\max_k \\\\|\\sum_{i=0}^{k-1}(\\nabla f_{\\pi_q(k)} - \\nabla F_q(x))\\\\|$, $L$-smoothness.\n\n4. Regret analyses. This analysis is based on [B3]'s Theorem 2.13. Here, we provide the key steps.\n   \n    $$\n   \\begin{align}\n   \\\\| x_{q+1} - u\\\\|^2 - \\\\| x_q - u\\\\|^2 & \\leq \\\\| x_q - \\gamma \\sum_{k=0}^{K-1} \\nabla f_{\\pi_q(k)}(x_q^k) -u\\\\|^2 - \\\\| x_q - u\\\\|^2\\\\\\\\\n   &\\leq \\underbrace{-2\\gamma\\sum_{k=0}^{K-1} \\langle x_q-u,\\nabla f_{\\pi_q(k)}(x_q^k)\\rangle}\\_{T_1} + \\underbrace{\\gamma^2 \\\\|\\gamma\\sum_{k=0}^{K-1}\\nabla f_{\\pi_q(k)}(x_q^k)\\\\|}_{T_2} \\\\\\\\\n   \\end{align}\n   $$\n   \n    where $u\\in \\mathcal{V}$ is an arbitrary competitor. Then, $T_1$ can be bounded by [B5]'s Lemma 5 and our Lemma 5. $T_2$ can be bounded by Jensen's inequality and our Lemma 5.\n\n5. Regret bound. The average regret bound of the algorithm is as follows:\n   $$\n   \\frac{1}{Q}\\sum_{q=0}^{Q-1} ( \\nabla F_q(x_q) - \\nabla F_q(u)) = O\\left( \\frac{\\sigma D}{\\sqrt{Q}} + \\frac{L^{1/3}D^{4/3}(\\bar\\phi_q)^{2/3}}{(KQ)^{2/3}} + \\frac{D^2}{LK^2Q}\\right),\n   $$\n   where the last term is due to the constraint $\\gamma L N \\lesssim 1$ of our Lemma 5. This framework includes AP and IP readily. The original online GD corresponds to AP here. This bound means that a nice permutation (the value of $\\bar\\phi_q$ is small) will lead to a nice bound. Thus, shuffling a subset of the dataset can also help improve the performance.\n\nGiven the complexity, we leave DP for future works. Furthermore, we think combining permutation-based SGD and online learning can be a promising future direction. We thank you again for these valuable suggestions, which have inspired meaningful extensions to our work. We will incorporate these insights into the revised manuscript.\n\n[B3] A Modern Introduction to Online Learning, arXiv, 2019. (500+ citations)\n\n[B4] Introduction to Online Convex Optimization, Foundations and Trends® in Optimization, 2016. (2400+ citations)\n\n[B5] SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML, 2020."}, {"review_id": "cop5811TYK", "reviewer": "Reviewer_MycC", "summary": "This paper presents a unified framework for analyzing permutation-based Stochastic Gradient Descent (SGD), including arbitrary, independent, and dependent permutations. By introducing a more general assumption (Assumption 2) that captures inter-epoch permutation dependencies, the authors generalize existing analyses and derive upper bounds for prior algorithms (e.g., GraB). The framework is further extended to Federated Learning (FL) with regularized client participation. The authors propose FL-GraB, a new algorithm that improves FL training performance under permutation constraints.", "questions": "1. Can the unified framework be extended to cover independent client sampling, as in Wang & Ji (NeurIPS 2022)?\n2. Can you provide a comparison or discussion of how FL-GraB performs against prior client sampling strategies, such as SCAFFOLD (Karimireddy et al., 2020)\n3. Can you clarify the implementation details of the AP and FL-AP algorithms used in the experiments?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper presents a new upper bound for dependent permutation-based SGD algorithms.\n2. It offers a clean and comprehensive theoretical analysis, with results that are consistent with prior work.\n3. The findings are interesting: FlipFlop and PairGraB are shown to achieve upper bounds comparable to those of RR and the original GraB, respectively.\n4. The proposed unified framework is extended to federated learning FL. FL-GraB empirically outperforms FL-RR in the experiments provided.\n\nWeaknesses\n1. Only covers regularised participation in FL; the much more common independent sampling setting (e.g., Wang & Ji 2022) seems outside the framework.\n2. The advantage of FL-GraB or dependent client sampling is not clear. There is no comparison with FL baselines such as SCAFFOLD (Karimireddy et al., 2020) under heterogeneous data distributions.\n3. The implementation AP / FL-AP are not clearly described, and the corresponding results are not discussed.\n4. Figure 1 lacks an x-axis label (likely \"epochs\").\n5. \"Initilize\" in Algorithm 2 line 4 should be \"Initialize\".\n\nReferences\n1. Wang, S., & Ji, M. A unified analysis of federated learning with arbitrary client participation. In Proceedings of the Conference on Neural Information Processing Systems (NeurIPS), 2022.\n2. Karimireddy, et al. SCAFFOLD: Stochastic controlled averaging for federated learning. In Proceedings of the International Conference on Machine Learning (ICML), 2020.", "was_revised": true, "final_justification": "Technically solid paper and the authors have addressed my concerns in the rebuttal.", "rebuttal": "> Only covers regularised participation in FL; the much more common independent sampling setting (e.g., Wang & Ji 2022) seems outside the framework.\n\n> Can the unified framework be extended to cover independent client sampling, as in Wang & Ji (NeurIPS 2022)?\n\nBefore drawing the conclusion, let us revisit the definition of independent participation (their Proposition 4.7) in [C1]: If $\\{u_r^n\\}$ is independent across $r$, for any $n$, where $u_r^n$ is the participation weight of client $n$ ($u_r^n$ is a random variable and is the key component of [C1]'s framework), and $r$ is the index of the communication round. In the experiments of their Figure D.1, they gave a more concrete example (a simplified version): \"For independent participation, the subset of clients are selected randomly according to a uniform distribution, independently across rounds\". As we can see, this simplified independent participation pattern is the typical pattern studied in [C2,C3].\n\nNow, we are sure that our unified framework can be extended to cover the independent participation pattern in [C1] (at least the simplified version).\n\n1. *Cover the simplified independent participation pattern*. In our framework, we divide all rounds into smaller chunks (with the same size) and analyze each of the chunks separately. We denote the size of these chunks as $P$. In the original framework, for simplicity, we let $P=\\frac{N}{S}$, where $N$ is the total number of the clients and $S$ is the participating clients in each round. To incorporate independent participation: (i) We treat $P$ as an algorithm-specific parameter. (ii) For independent participation, we set $P = \\Theta(\\frac{1}{\\gamma L})$ as done explicitly in [C4] and implicitly in [C1]'s Proposition 4.7. (ii) For the original algorithms in our paper, we set $P=\\frac{N}{S}$. \n2. *Extension for arbitrary participation weights*. In the first step, we show that our framework can incorporate the independent participation with uniform participation weights (the simplified version). Next, we consider the arbitrary participation weights. The main challenge is due to the participation weight $u_q^n$ (of client $n$ in epoch $q$) can be arbitrary. One simple approach to circumvent this challenge is to apply different weights (in the parameter aggregation stage) to different clients' updates [C5,C6]. For example, if the participation weight of client $n$ is $u_q^n$ in epoch $q$, we can use the weight $\\frac{1}{u_q^n}$ (we need to assume that $u_q^n>0$) in the parameter aggregation stage. By this, we can transform the complex problem (with arbitrary participation weights) into the original problem (with uniform participation weights) in this paper. Furthermore, as pointed out by [C6], the original FedAvg with arbitrary participation in fact optimizes a different objective from the true objective, and this modified algorithm (with different weights) has been proved to optimize the true objective and shown better performances [C6].\n\n[C1] Wang and Ji, A Unified Analysis of Federated Learning with Arbitrary Client Participation, NeurIPS, 2022.\n\n[C2] Karimireddy et al., SCAFFOLD: Stochastic Controlled Averaging for Federated Learning, ICML, 2020.\n\n[C3] Yang et al., Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning, ICLR, 2021.\n\n[C4] Koloskova et al., On Convergence of Incremental Gradient for Non-Convex Smooth Functions, ICML, 2024.\n\n[C5] Wang et al., Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization, NeurIPS, 2020.\n\n[C6] Wang and Ji, A Lightweight Method for Tackling Unknown Participation Statistics in Federated Averaging, ICLR, 2024.\n\n> The advantage of FL-GraB or dependent client sampling is not clear. There is no comparison with FL baselines such as SCAFFOLD (Karimireddy et al., 2020) under heterogeneous data distributions.\n\n> Can you provide a comparison or discussion of how FL-GraB performs against prior client sampling strategies, such as SCAFFOLD (Karimireddy et al., 2020)\n\nWe compare SCAFFOLD [C2] and FL-GraB theoretically and empirically.\n\n1. *Theoretical Aspect*. According to the convergence guarantees, SCAFFOLD is immune to data heterogeneity, while FL-GraB still suffers from heterogeneity.\n\n2. *Empirical Findings*. In cross-device FL settings (using the same experimental setup as our Appendix I), FL-GraB consistently outperforms both FL-RR and SCAFFOLD. The results are shown in Table C1. The client ordering for SCAFFOLD is the same as FL-RR.\n\n   *Key observations*: (i) FL-GraB outperforms FL-RR and SCAFFOLD, especially at the early stage. (ii) SCAFFOLD underperforms FL-RR, which can be due to the high heterogeneity [C7,C8] and the staleness of control variates [C6] in cross-device FL.\n\n[Table C1: Test accuracies (averaged over the last 10 epochs and 5 random seeds) for training CNN on CIFAR-10/CIFAR-100/CINIC-10.]\n\n| CIFAR-10  | FL-RR | SCAFFOLD | FL-GraB      |\n| --------- | ----- | -------- | ------------ |\n| epoch 100 | 77.2  | 71.1     | 79.12 (+1.9) |\n| epoch 200 | 80.0  | 76.4     | 81.20 (+1.2) |\n\n| CIFAR-100 | FL-RR | SCAFFOLD | FL-GraB     |\n| --------- | ----- | -------- | ----------- |\n| epoch 100 | 41.1  | 30.5     | 44.8 (+3.7) |\n| epoch 200 | 47.5  | 41.1     | 49.2 (+1.7) |\n\n| CINIC-10  | FL-RR | SCAFFOLD | FL-GraB     |\n| --------- | ----- | -------- | ----------- |\n| epoch 100 | 59.7  | 53.6     | 63.1 (+3.4) |\n| epoch 200 | 64.2  | 58.6     | 66.7 (+2.5) |\n\n[C7] TCT Convexifying Federated Learning using Bootstrapped Neural Tangent Kernels, NeurIPS, 2022.\n\n[C8] Federated Learning on Non-IID Data Silos An Experimental Study, ICDE, 2022. (1300+ citations)\n\n\n> The implementation AP / FL-AP are not clearly described, and the corresponding results are not discussed.\n\n> Can you clarify the implementation details of the AP and FL-AP algorithms used in the experiments?\n\nThe specific implementations of AP and FL-AP (AP allows for arbitrary permutations) are as follows:\n\n1. The data examples are sorted in ascending order with respect to the value of $b_n$.\n2. This sorted permutation is used repeatedly for all the epochs.\n3. Additional implementation details are available in our submitted code (specifically in the `train_IG()` function)\n\n\n> Figure 1 lacks an x-axis label (likely \"epochs\").\n\n> \"Initilize\" in Algorithm 2 line 4 should be \"Initialize\".\n\n> According to the formatting instructions (Section 4.2), footnotes should be placed at the bottom of the page on which they appear.\n\nWe thank you for catching these presentation issues:\n\n1. We will add \"epochs\" as the x-axis label for Figure 1.\n2. \"Initilize\" in Algorithm 2, line 4 will be corrected to \"Initialize\".\n3. We will revise our footnote usage to comply with formatting guidelines."}, {"review_id": "QjXHYfCOdj", "reviewer": "Reviewer_625o", "summary": "The paper proposed a new general framework for analyzing the stochastic gradient descent algorithm with various kinds of permutations in the smooth setting. A more general assumption was introduced to handle the potential dependency of the permutations across different rounds. The framework was further extended to the federated setting.", "questions": "> 1. In practical federated learning setting, the data is often heterogeneous across different clients. How would this affects the algorithm, would it be reflected by the convergence guarantee?\n\n> 2. Would the same kind of technique be applicable to other optimization algorithms besides SGD? Is there a specific reason of picking SGD as the base optimizer in this case?\n\n> 3. How does the algorithm scales with large systems. In fact, is there a reason of choosing dependent permutation over the other algorithms?", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n> 1. The author proposed a novel assumption which is more general that handles potential dependencies of permutations effectively. \n> 2. The framework proposed was further developed and extended into the federated learning setting.\n> 3. Convergence guarantees were provided together with numerical experiments further supporting its validity.\n\nWeaknesses:\n> 1. The newly proposed assumption brings additional difficulty into practical implementations, in Theorem 1, the step size $\\gamma$ seems to be dependent on the parameters such as $A_i,B_i$. Given the complexity in practice, I am not sure whether the theoretical indication actually can be helpful at all.\n\n> 2. Do the authors have an example, where all of the assumptions in Theorem 1 holds? The sets of assumptions seem quite restrictive to me. In order to apply the theorem, do we need to determine all of $A_i, B_i$ and $D$? If it is the case, how can we actually determine them in a practical setting? \n\n> 3. I am curious about the original motivation of the authors. If dependent permutation is better, why bother developing a theory that includes the three cases. Why not focusing alone on the dependent case.\n\n> 4. Given the complication that the theories involve, I would suggest the authors test the algorithm on a broader scope of machine learning and deep learning tasks.", "was_revised": true, "final_justification": "The rebuttal of the authors addresses most of my concerns.", "rebuttal": "> The newly proposed assumption brings additional difficulty into practical implementations, in Theorem 1, the step size $\\gamma$ seems to be dependent on the parameters such as $A_i$, $B_i$. Given the complexity in practice, I am not sure whether the theoretical indication actually can be helpful at all.\n\n> Do the authors have an example, where all of the assumptions in Theorem 1 holds? The sets of assumptions seem quite restrictive to me. In order to apply the theorem, do we need to determine all of $A_i, B_i$ and $D$? If it is the case, how can we actually determine them in a practical setting?\n\n1. The assumptions. The main assumptions used in Theorem 1 is $L$-smoothness (Definition 3) and Assumption 2. The main assumption used in propositions (for specific algorithms) is $L$-smoothness and Assumption 3. (i) $L$-smoothness and Assumption 3 are the standard assumptions in non-convex optimization. (ii) Assumption 2 has been proved to be weaker than Assumption 3 [D2]. (iii) We also acknowledge that, although the assumptions we adopt are standard, they may not hold in modern deep learning models (e.g., CNNs), which we think is out of the scope of this paper.\n\n2. The constraint of the step size $\\gamma$. The constraint of $\\gamma$ relies on the choices of $A_i$, $B_i$, which may seem to be stringent. In fact, as shown in Table D1, in the given algorithms, the choices of $A_i$ and $B_i$ does not impose stronger constraints than the existing works [D2,D3,D4,D5].\n\n   [Table D1: Specific choices of $A_i$, $B_i$, D under the standard assumptions ($L$-smoothness and Assumption 3). The numerical constants and polylogarithmic factors of $B_i$ and $D$ are omitted. We use $\\lesssim$ to denote \"less than\" up to some numerical constants and polylogarithmic factors.]\n\n   | Algorithm   | $B_0$       | $A_1$         | $B_1$            | $A_2$          | $B_2$ | $D$              | $\\gamma$                                                     |\n   | ----------- | ----------- | ------------- | ---------------- | -------------- | ----- | ---------------- | ------------------------------------------------------------ |\n   | AP          | $N^2\\alpha^2$           | 0             | 0                | 0              | 0     | $N^2\\varsigma^2$ | $\\gamma \\lesssim \\frac{1}{L(N+N\\alpha)}$                     |\n   | RR/FlipFlop | $N\\alpha^2$ | 0             | 0                | 0              | 0     | $N\\varsigma^2$   | $\\gamma \\lesssim \\frac{1}{L(N+\\sqrt{N}\\alpha)}$              |\n   | GraB-proto  | 0           | $\\frac{3}{4}$ | $N^2 + \\alpha^2$ | 0              | 0     | $\\varsigma^2$    | $\\gamma \\lesssim \\min \\\\{\\frac{1}{LN}, \\frac{1}{L_{2,\\infty}N(1+\\alpha)}, \\frac{1}{L_{\\infty}N}\\\\}$ |\n   | GraB        | 0           | $\\frac{3}{5}$ | $N^2 + \\alpha^2$ | $\\frac{1}{50}$ | $N^2$ | $\\varsigma^2$    | $\\gamma \\lesssim \\min \\\\{\\frac{1}{LN}, \\frac{1}{L_{2,\\infty}N(1+\\alpha)}, \\frac{1}{L_{\\infty}N}\\\\}$ |\n   | PairGraB    | 0           | $\\frac{4}{5}$ | $N^2 + \\alpha^2$ | 0              | 0     | $\\varsigma^2$    | $\\gamma \\lesssim \\min \\\\{\\frac{1}{LN}, \\frac{1}{L_{2,\\infty}N(1+\\alpha)}, \\frac{1}{L_{\\infty}N}\\\\}$ |\n\n3. The implementations of the algorithms. (i) As shown in Table D1, we can derive the values of $A_i$, $B_i$, $D$ for the given algorithms theoretically. This is mainly to use Theorem 1 to obtain their convergence guarantees, which is a important metric to measure the convergence of algorithms. (ii) However, it is not necessary to compute their values in practice. For example, for RR and FlipFlop, we only need to shuffle the dataset, and tune the step size (and other hyperparameters) in the usual way; for GraBs, we need to run Algorithms 9, 10, 11 (in Appendix C.2) and reuse the hyperparameters from RR (or tune them as RR). In addition, no additional hyperparameters are introduced in GraBs.\n\n[D1] Lan, First-order and Stochastic Optimization Methods for Machine Learning, 2020. (540+ citations)\n\n[D2] Lu et al, A General Analysis of Example-Selection for Stochastic Gradient Descent, ICLR, 2022.\n\n[D3] Koloskova et al., On Convergence of Incremental Gradient for Non-Convex Smooth Functions, ICML, 2024.\n\n[D4] Lu et al., GraB Finding Provably Better Data Permutations than Random Reshuffling, NeurIPS, 2022.\n\n[D5] Cooper et al., Coordinating Distributed Example Orders for Provably Accelerated Training, NeurIPS, 2023.\n\n> I am curious about the original motivation of the authors. If dependent permutation is better, why bother developing a theory that includes the three cases. Why not focusing alone on the dependent case.\n\n+ Developing a unified framework is a consistent topic in permutation-based SGD [D2,D3,D6,D7,D8].\n+ Existing frameworks cannot include the DP categories. Meanwhile, the DP algorithms have been shown to perform better in multiple areas (e.g., distributed learning [D4], multi-objective opti-\n  mization [D9], and also federated learning in this paper).\n+ The framework can help us understand the impacts of the permutations in permutation-based SGD, e.g., the definition of the order error $\\bar \\phi_q$.\n+ The framework can also be used to analyze the convergence of future permutation-based SGD algorithms.\n\n[D6] A Unified Convergence Analysis for Shuffling-Type Gradient Methods, JMLR, 2021.\n\n[D7] Characterizing & Finding Good Data Orderings for Fast Convergence of Sequential Gradient Method, arXiv, 2022.\n\n[D8] A Unified Convergence Theorem for Stochastic Optimization Methods, NeurIPS, 2022.\n\n[D9] Joint Gradient Balancing for Data Ordering in Finite-Sum Multi-Objective Optimization, ICLR, 2025.\n\n> Given the complication that the theories involve, I would suggest the authors test the algorithm on a broader scope of machine learning and deep learning tasks.\n\nAs suggested, we will add more tasks in the revision. For the current version, the main contributions of this paper are theoretical.\n\n+ We validate the theoretical conclusions through a simulated experiments (Section 5).\n+ For SGD, our theoretical conclusions are aligned with the existing experiments in [D4,D5].\n+ For FL, we use the experiments of training CNN/ResNet on CIFAR-10/CIFAR-100/CINIC-10 to validate the effectiveness of the new proposed FL-GraB (Appendix I), which shows that FL-GraB outperforms FL-RR in cross-device FL settings.\n\n> In practical federated learning setting, the data is often heterogeneous across different clients. How would this affects the algorithm, would it be reflected by the convergence guarantee?\n\nYes, our convergence guarantees can reflect the heterogeneity. The guarantees are given in Table D3. Here, we mainly study the heterogeneity, so the local solver of FL is set to be GD. The level of the heterogeneity is measured by $\\varsigma$: Larger value of $\\varsigma$ means higher heterogeneity. The conclusions: (i) High heterogeneity will hurt the convergence. (ii) The convergence of FL-GraB is the best (when $Q$ and $N$ are large).\n\n[Table D2: Convergence guarantees for FL.]\n\n| Algorithm | Guarantee                                                    |\n| --------- | ------------------------------------------------------------ |\n| FL-AP     | $\\frac{L F_0}{Q} + \\left(\\frac{LF_0 S\\varsigma }{ NQ}\\right)^{\\frac{2}{3}} + \\left(\\frac{LF_0 N \\varsigma }{ NQ}\\right)^{\\frac{2}{3}}$ |\n| FL-RR     | $\\frac{L F_0\\left( 1+\\alpha\\right)}{Q} + \\left(\\frac{LF_0 S\\varsigma }{ NQ}\\right)^{\\frac{2}{3}} + \\left(\\frac{LF_0 \\sqrt{N} \\varsigma }{ NQ}\\right)^{\\frac{2}{3}}$ |\n| FL-GraB   | $\\frac{\\tilde L  F_0+\\left (L_{2,\\infty}F_0 \\varsigma \\right)^{\\frac{2}{3}}}{Q} + \\left(\\frac{L_{2,\\infty}F_0 S\\varsigma }{ NQ}\\right)^{\\frac{2}{3}} + \\left(\\frac{L_{2,\\infty}F_0 \\varsigma }{ NQ}\\right)^{\\frac{2}{3}}$ |\n\n> Would the same kind of technique be applicable to other optimization algorithms besides SGD? Is there a specific reason of picking SGD as the base optimizer in this case?\n\nFor now, the framework only applies to SGD. The reasons of picking SGD as the base optimizer.\n\n1. SGD is simple and effective.\n2. The existing theory of SGD is more well-developed.\n3. We think studying SGD is a good starting point. Studying the effects of the permutations on other optimizers can be a promising future direction.\n\n> How does the algorithm scales with large systems. In fact, is there a reason of choosing dependent permutation over the other algorithms?\n\nWe acknowledge that scalability remains an open issue in this version. We think our theory can serve as a first step toward understanding how permutations may affect convergence, potentially inspiring more scalable variants in future works.\n\n> Some tables contain vertical lines which seem a bit strange.\n\nAs suggested, we will remove vertical lines in the revision."}]

Author rebuttal:

Meta-review: This paper proposes an assumption that can incorporate permutation-based SGD with *past-dependent* permutations into a unifying framework. The authors prove convergence results on nonconvex smooth optimization problems under the framework, which can be applied to various specific example selection schemes. Particularly, the analysis yields new convergence results for FlipFlop and some GraB variants. The paper also applies this framework to federated learning with regularized client participation, and derives new bounds.
All reviewers were positive about the paper and appreciated the usefulness of the new assumption. The authors put extensive efforts into addressing reviewers’ concerns and all of them were satisfied. I also find that the paper successfully pushes the boundary of permutation-based SGD analysis. I hence recommend acceptance; I would like to ask the authors to incorporate the rebuttal and the discussion into the final version of the paper.

A couple minor comments:
- From my own reading, I think “when $Q$ is large” in line 132 uses $Q$ without stating it denotes the number of epochs.
- I think it would be a particularly good idea to include Table D1 in the paper.
Decision: Accept (poster)