Debiasing Federated Learning with Correlated Client Participation
Authors: Zhenyu Sun
ziyang zhang
Zheng Xu
Gauri Joshi
Pranay Sharma
Ermin Wei
Venue: ICLR 2025 Poster (2025)
Keywords: federated learning
Markov chain
time-correlated participation
Primary area: optimization

Abstract: In cross-device federated learning (FL) with millions of mobile clients, only a small subset of clients participate in training in every communication round, and Federated Averaging (FedAvg) is the most popular algorithm in practice.  Existing analyses of FedAvg usually assume the participating clients are independently sampled in each round from a uniform distribution, which does not reflect real-world scenarios. This paper introduces a theoretical framework that models client participation in FL as a Markov chain to study optimization convergence when clients have non-uniform and correlated participation across rounds. 
We apply this framework to analyze a more practical pattern: every client must wait a minimum number of $R$ rounds (minimum separation) before re-participating. We theoretically prove and empirically observe that increasing minimum separation reduces the bias induced by intrinsic non-uniformity of client availability in cross-device FL systems. 
Furthermore, we develop an effective debiasing algorithm for FedAvg that provably converges to the unbiased optimal solution under arbitrary minimum separation and unknown client availability distribution.

Published as a conference paper at ICLR 2025
DEBIASING FEDERATED LEARNING WITH CORRELATED CLIENT PARTICIPATION
Zhenyu Sun', Ziyang Zhang;; Zheng Xu', Gauri Joshi', Pranay Sharma', Ermin Wei"
Northwestern University, 1 "Google Research, Caamegie Mellon University
(zhenyusun2026, ziyangzhang22224Jau htw.://ieeeenoootteetteerrrte nwwthwestern edu, xuzheng8google com, (pranaysh, gauri andrew. cmu. .mu.edu, ermin. wei wei edu
ABSTRACT
In cross-device federated learning (FL) with millions of mobile clients, only a small subset of clients participate training in every communication round, and Federated Averaging (FedAvg) is the most popular algorithm in practice. Exist- ing analyses of FedAvg usually assume the participating clients are independently sampled in each round from a uniform distribution, which does not reflect real- world scenarios. This paper introduces a theoretical framework that models client participation in FL Markov chain to study optimization convergence when clients have non-uniform and correlated participation across rounds. We apply this framework analyze a more practical pattern: every client must wait a min- imum number of R rounds (minimum separation) before re-participating. We theoretically prove and empirically observe that increasing minimum separation reduces the bias induced by intrinsic non-uniformity of client availability in cross- device FI. systems. Furthermore, we develop an effective debiasing algorithm for FedAvg that provably converges to the unbiased optimal solution under arbitrary minimum separation and unknown client availability distribution.
INTRODUCTION
The massive amounts of data generated on edge devices such as cellphones or sensors offers an op- portunity to train machine learning (ML) models for various applications. However, communication and privacy constraints of edge devices preclude the transfer of raw data to the cloud. Federated learning (FL) (MeMahan et al., 2017: Kairouz et al., 2019; Li et al., 2020a; Yang al., 2019) has emerged as powerful framework to operate within these constraints by keeping decentralized data on the edge devices and instead moving model training to the edge. Federated model training oper- ates in communication rounds. In each round, the current model is sent by the central server to edge clients, which perform model updates using their own local data, and the resulting models are then averaged by the central server. A typical cross-device FL. framework consists of millions of inter- mittently connected edge clients, each round only a small subset of them participate in training (Bonawitz al., 2019). The subset of participating clients is affected by devices' intrinsic properties such as battery status and network connectivity, and also system induced constraints for efficiency and privacy. In this paper, we seek understand the effect of such client participation patterns on convergence of federated training.
The federated averaging (FedAvg) algorithm and its variants are widely used practice (Kairouz et al., 2019; Wang et al., 2021: Hard et al., 2018; Xu et al., 2023), and the convergence has been ex- tensively analyzed in literature (Li al., 2020b; Woodworth et al., 2020; Wang et al., 2022; Karim- ireddy et al., 2019; Wang & Joshi, 2021; Wang et al., 2020). However, most works assume uniform client participation which ensures that the model update applied to the global model is an unbiased estimate of the model update in the full client participation setting. This enables convergence results for the full partpaacciiitioonn setting to be extended to the partial participation setting resulting in an ad- ditional variance term appearing in the convergence bound (Jhunjhunwala et al., 2022; Karimireddy et al., 2019: Wang et al., 2020). A generalization of the uniform client participation model is to consider that each client has intrinsic availability probability pt that is either known unknown

---

Published as a conference paper at ICLR 2025
to the central server. The set of participating clients is chosen according to this probability. Such non-uniform client participation introduces a bias in the model updates received by the server, with more frequently participating clients dominating the average update. To counter the bias, the central server can normalize the updates by the corresponding availability probabilities (Wang & Ji, 2022; Cho et al., 2022) their estimates (Wang& & Ji, 2023; Ribero et al., 2022). We consider the setting of unknown client availability and analyze the convergence.
Both the uniform and non-uniform client participation models described above assume that client participation follows a Bernoulli process that is independent across clients and rounds. This assump- tion fails to capture practical settings where the client participation are correlated across rounds due to memory or deme-deendeecce constraints. In cross-devies FL systems, a device can only be avail- able for training when it is plugged in for charging, connected to unmetered network and not being actively used by the owner (Hard et al., 2018; 8; Paulik et al., 2021; Huba et al., 2022). These criterion, which typically occurs during the night of the devices' local time, not only results in the client avail- ability probability for non-uniform client participation, but also correlated client participation of periodic pattern due to user preference and time zone (Kairouz et al., 2019; Eichner et al., 2019; Zhu et al., 2021). More recently, new criteria is introduced on devices in a FL system to impose min- imum separation constraint on successive participation instances of a client (McMahan & Thakurta, 2022; Xu et al., 2023). Specifically, once client participates in training, it cannot become avail- able to participate for at least R more rounds (R specified by the central aggregating server). The minimum separation is introduced effectively combine differential privacy (DP) and FL (Kairouz et al., 2021; Choquette-Chov et al., 2023; McMahan et al.. 2024) as advanced crivacy-preeervig methods, and quickly becomes the default criterion in many FL applications (Xu et al., 2023; Xu & Zhang, 2024). The client participation across rounds are correlated under the minimum separation criterion, and the extreme case of very large R will force cyclic client participation as studied in (Cho et al., 2023; Malinovsky et al., 2023). However, setting It to be the exact value for cyclic client par- ticipation can be challenging and may cause system slowdown, and these recent work did not study non-uniform client participation or the large spectrum of minimum separation R in practice. Other existing convergence analyses of federated training with generalized client participation (Wang & Ji, 2022; Rodio et al., 2023) do not fully explain the effect of such correlated client participation patterns, calling for new theoretical advances. See Appendix A for more related work discussions.
In this paper bridge the gap of algorithms in practical FL system and the theoretical guarantees on their convergence with correlated client participation and unknown client availability. Our paper makes the following key contributions: (1) To the best of our knowledge we are the first ana- lyze the convergence of FedAvg with a minimum separation constraint on successive participation instances of each client, which general setting widely used in practical FL systems. We show that such correlated participation patterns can be captured by a Markov chain model. (2) We show that as the minimum separation R increases, the effective client participation probabilities become more uniform and reduces the asymptotic bias in the solution attained by the FedAvg algorithm. (3) We propose a debiased FedAvg algorithm that estimates the unknown client participation probabil- ities and incorporates them in the local updates. We prove that this algorithm achieves unbiased solution that is consistent with the global FL objective under arbitrary minimum separation R.
For any positive integer N, we denote [N] = {1,.... N}. Let || ll. || lla and || lloc denote 12-nomm, ln-norm and loo -nom,, respectively. For an ordered sequence {i...... (. it is represented by (i....., i and we use the same notation for vector when the context causes no confusion. Unless otherwise specified, EE()) means the total expectation taken on all randomness. We use to denote the vector where all entries are The d-dimensional Euclidean space is denoted by Rd, and R4 is the space formed vectors where every entry is strictly positive.
Notations:
2 PROBLEM FORMULATION
We consider the federated learning setting where N clients cooperate to minimize the following global objective:
1 N N
min F(z) : Σ f(x)
(1)
where fi is the local objective function of client i. We aim to solve problem equation I in the fed- erated learning setting, i.e., the system implements the some federated learning algorithm which
2

---

Published as a conference paper at ICLR 2025
operates in rounds. In each round, subset of the clients participate in training, and each of the clients in the subset performs multiple local updates based on the local gradients and then commu- nicates with the server.
Non-uniform and correlated client participation. In this paper, we consider the scenario where each client requires some resting periods between participation and hence the participation pattern is correlated over time. Specifically, once participating in the system, an client has to wait as least R rounds until its next participation, where R is called the minimum separation. In other words, suppose client i's last participation is in round 4. It may join again at any round (. with / 2 1 1 ++ R and not before then. Moreover, when a client is available be sampled, instead of assuming uniform sampling, consider that each client is associated with some unknown strictly positive scalar p: > 0 to characterize its intrinsic willingness to be sampled at every round. Without loss of generality, we assume Σ P: = 1 and hence refer to as the availability probability of client Therefore, the client participation pattern is as follows: each communication round, client i is sampled to participate in the training process with probability proportional to if it has waited for R rounds after its last participation; otherwise client i cannot be sampled.
The above setting encompasses many of those in existing literature as special cases. For instance, note that which is consistent with (Wang& & Ji, 2023). And the cyclic participation corresponds to the case R = B 1 where B number of clients are sampled in each round (Cho et al., 2023), assuming the total number of clients in the FL. population N is divisible by B. We investigate the potential bias in- troduced by the non-uniform and correlated client participation on federated algorithm performance and propose debiasing scheme to mitigate it.
means each client sampled every round with probability ps independently.
3 MARKOV CHAIN MODEL AND ITS PROPERTIES
In this section, propose Markov chain model to capture the correlated participation scenario described above. Intuitively, the fact that every client cannot be sampled again within rounds motivates us to maintain a memory window with length R to track which clients have not waited for R rounds. In other words, clients that are possible to be sampled in the current round only depend on which clients appearing in the memory window. This calls for Markov chain with R-memory, also known as R-order Markov chain, defined as below.
Definition Let {X+] be a stochastic process where X, X, VI 2 O. said to an R-order Markov chain if
P(X, X Xp) = P(Xe X Xt-n), 4E R.
X' is called the state space.
If R = 1 it reduces to conventional Markov chain; if R = O. then the clients can be sampled each round with probability p:, independent of the history. In a conventional Markov chain (with R 1) with finite state space X, can the transition probability matrix P to represent the Markov chain, where the (i. entry of P is [P]c = P(X, j X = i), i.e., the probability of transitioning from state i state j.
Recall that each client is associated with a strictly positive availability probability p: > 0, Vi E [N]. At each round the server samples size-B subset of clients S,, where |S, = B, with probability for each client proportional to p; to join the training system. Note that only clients that have waited for R rounds are available. In other words. set S, is sampled with probability proportional to Eies, p. from all subsets of size B formed by the available clients. We assume N MB for some M 0 and note that the minimum separation R ranges from to M 1, where R = M 1 corresponds to cyclic participation pattern where subsets of clients participate training in fixed order.
Denote X' as the collection of all possible ordered subsets of [N] with exactly B elements. Then, | oNN, B) where oNN, B) (N-B represents the total number of B B-permutations of [N].
N!
Any R M- - would resulting in periods with insufficient available clients. We do not consider those
cases here.
3

---

Published as a conference paper at ICLR 2025
Considering the stochastic process {2 where X₁ X, the participation pattern in Section can be precisely described by an R-order Markov chain defined in Definition 1. Formally,
P(X; = To X I,, 2 Iz ..,,..,, Xo Ix) p(X; To X,-1 II...... Xt- R IR)
(2)
where each state I& X represents which ordered subset of size B has been sampled at round k. For example, suppose clients 1 to B are sampled during the current round. 21, B) and (2, 1,.,...., B) are two different states, although the probability of these two states to appear is the same. The reason we consider this ordered case is that it allows us to cleanly define the probability of client i to be sampled (which is the marginal distribution of P(X,)) by noting that P(i to be sampled at round t) Eig.....p P(X, = (i, ................................ iB)). Here we calculate the prob- ability of client i appearing as the first element in the ordered set X,. The probability of being sampled in any position would need an additional scaling factor of B. Since the scaling factor B is the same for all clients and only the relative frequency across clients contribute towards any bias effect, ignoring this factor of B would not affect the debiasing calculation.
The above high-order Markov chain equation 2 has some nice properties as summarized below (see Appendix C for proofs). The insights are important for deriving Theorem 2, which is the reason we formally present them here.
Proposition 1. The R-th order Markov chain equation 2 maintains the following properties:
(1). The ordered sequence .I,II,...,IRR) is non-repeated, meaning I₁ n Ig = -0, * kk. k.
(2). For any non-repeated (Io...., In).
XI-R= = IRR P(X,= Io To |X,11= = -...,,,,,,,,1--
Ejes, PJ
PIo
TR)
(3)
Otherwise P(X+ Io | X Ii...., 1I...,KI-RR IR) O. Since In is set with B unique elements, we define PT,, == IInETA Pe, VIy. St., is the collection containing all B-permutations of
[M] UN In.
X1- (3). For L. 2 R- 1, define Y, = (Xt.....:x-R4)) E R.R. Then n is a conven- tional Markov chain with its cardinality of the state space being d(M, R), where d(M, R) =
R- aBB(M - k), B). Moreover its transition probability
P(Y, = (II, IR....,,TR-Ill 1- ((I,..,,RRR) IR))= {{
Th = I 1] P( (R....TT))-
0
otherwise
(4)
for any non-repeated (Io....IIn).
(4). Define vector Inn E RA(M, with II.In.... II..I,..,IIIIII) IR-I)-th
entry as P(Y, = (Io, II....,III In-1) Y = (II,...;II)) IR))- Then, U(T E R (BM c RdM,) and
"(I.... In) [To,... [Zo....,IR-I]] = PIo (EJEs, pJ) > VIo E S
(5). Denote (n RR with J2, Jn)-th entry as P(Y. (Jo, ... ((b...,JTnI)) Y = (JI,J2,.... [R)).. Then, V(J E RRR (B(M and V.oo 1)T JR)]
PJ. (EJEs, p3) > for any Jn E SJ
Properties (1). essentially state that clients to be sampled in the current round cannot be those who have not waited for R rounds, which establish the equivalence of our Markov-chain modeling equation 2 and the participation pattern in Section 2. Property (3) means that can augment our state space by considering R-length history to formulate an equivalent Markov chain (Y:) with order 1. The last two properties explicitly shows what entries are for each row and column of the transition probability matrix of the new Markov chain {Y Also since there are only (B(M R), B) < d(M, R) non-zero entries in every row and column, the transition matrix is sparse.
A main benefit of this Markov-chain modeling is allowing us look into the probability of each client to be sampled as f. goes on. Specifically, given any R, denote Pn E R)d( as the
4

---

Published as a conference paper at ICLR 2025
transition probability matrix of the Markov chain {YlteR where its entry is given by equation 4. Let (t) E (d), be the state distribution at round i of the Markov chain (Y))==R and m)z(()
RN be the distribution of clients to be sampled at round t. We have the following evolution of distributions with respect to t:
(s(()) (h)n(t), +) (t))t
(5)
for any initial distribution ()((0) and corresponding (n((0) such that nn()) = (z where
QR = QR,QQR2 and QR,1 E (gd(M.))xx(NM is defined by
Piz (a)--- (J.I In} non-repeated
otherwise.
and Qn E (N is defined by
J (J+
QRR2I
0 otherwise,
where - (j, +) denotes that the first entry of I is We are particularly interested in the distribu- tion of (t) as t - oc because it helps us characterize the asymptotic performance existing FL algorithms. From classical Markov chain literature, and aperiodic (see formal definitions in Appendix B), it has a stationary distribution which is unique as the stationary distribution of Markov chain and strictly positive. We denote Çn= -iim--oo (n(()) PR and we have
know that if Markov chain is irreducible
=A =
(6)
where na E R is marginal stationary distribution of clients to be sampled, i.e., the i-th entry of aR given by - = lim (t). On the other hand, if the Markov chain is irreducible and peroidic, we let ÇR be the Perron vector?. which is also strictly positive. We now show our Markov chain irreducibile and (a)periodic to justify the definitions of Ça and RR in Lemma 1. The proof is in Appendix C.
Lemma 1. The Markov chain {r R with transition matrix PR defined by equation 4 is irre- ducible for all M 2 1 and 0 S S M - Further, when R < M 2, it is also aperiodic.
We provide an example to illustrate the intuition of our Markov-chain model above, considering the case of N = 4, B 1, R = 2, i.e., every round one client is sampled, then it has to wait for two rounds. For instance, client 1 and client are consecutively selected in the first two rounds, in the third round only client 3 or 4 can be selected with probabilities of pa/ Pa/(ps + Pa) pa/ + pœ) respectively. Then, the state (2, 1) can only transition to (3, 2) or 2), where the second index is sampled before the first
as in equation 2. Similarly, if we are currently state (1, 4), the previous state has to be (4, 3) or (4, One can easily check that Proposition i holds. To see how is calculated, we take the first entry of RR as an example:
TR (2.33 (2.3) -1 P(2.0-11 (3.2)
P( +1 (3.44
(4.2) p1a
(4.3) (4.3) P(13)-1
by noting that the remaining P().))+11 = 0, if ir 1.
The vectors in equation 6 characterize the final distribution according which clients will be sam- pled when the communication round / becomes infinitely large. In other words, each client is sampled with probability th given some fixed R. Although TM-1 is the uniform distribution no matter what p. 's are (by observing that all clients follow a cyclic participation), we note that πR for R. M 1 does not necessarily follow the uniform distribution. because {PI...., ......,,) are arbitrary. This will be problematic in the sense that existing federated learning algorithms may no longer guarantee convergence to the correct and optimal solution of equation no matter how many rounds of training are implemented. We call this phenomenon the asymptotic bias induced by TR- We will characterize both empirically and theoretically this phenomenon in the next section.
We say v is the Perron vector of the transition matrix P if of TT P, i.e., is right eigenvector of P corresponding to eigenvalue and o² 1 = 1.
5

---

Published as a conference paper at ICLR 2025
4 ASYMPTOTIC BIAS UNDER NON-UNIFORM CORRELATED PARTICIPATION
In this section, we utilize the Markov chain model in the previous section to analyze asymptotic bias of existing federated learning algorithms caused by R < M - 2 and arbitrary pa s. In particular, we consider FedAvg with local gradient descent updates, i.e., each round, a set St with |Sa]| B clients are sampled and after being selected client i updates its model as
$2.0 = Tt, Fi,t11 t - a Ve( k == = 0, K
(7)
where 24 denotes the server's model round and oi,s is the local model maintained by client i at k-th iteration. The server then updates T++1 = B Eies, zi,x- We next show in the following that FedAvg may not converge to the desired optimal solutions of equation 1. Instead there may exist some error neighborhood, i.e., the asymptotic bias, that is related to x even as t goes to infinity. Before we formally deliver the result, two standard assumptions needed.
Assumption 1. There exists G such that [| (+)) - VF S G², Va and E [N].
Assumption 2. Each Jt is L-smooth, ie., [V)((>)) Vi((i)] - L|| yll. Var y and Vi E [N]
Then we are ready to state the convergence of FedAvg under correlated client participation (see Appendix F for the proof).
Theorem 1. Suppose Assumptions 1,2 hold and assume FF())) S D, Ya with some finite D > O. Then for any T > 2Tmin log Tmiz choosing a ((1((mmiz K KV T),, FedAvg with local updates equation 7 generates the trajectory {x satisfying
BI <
Tmiz
+
O
+0 1 T
|
1N l1). N
1
(8)
for any S << M - where 3e is drawn uniformly from Io...., TT-1, O()) hides logrithmic factors, and Tiir denotes the mixing time of Markov chain equation 5. Moreover, the bias term O[[[TR- 11 shown in equation is unavoidable.
Theorem I implies that without any debiasing technique, FedAvg can only converge to a solution with unavoidable asymptotic bias which measured by the distance between म (defined in equa- tion 6) and the uniform distribution. Except for R = M 1, where AM is the uniform distribution, for < M 2. there is generally some gap between गा and (1/N)IN, which shows that FedAvg may fail to perform under correlated client participation. However, if IT is not too far away from the uniform distribution, we expect FedAvg to converge to solution reasonably close to the optimal so- lution of equation 1. We next investigate what factors influence the distance from æ to the uniform distribution. We find that one factor is the spread among P, ss Stated by the following proposition, if all p.'s 's are equal, no gap between RR and (I/N)IN exists (see Appendix D for the proof).
Proposition Suppose p1 = P2
PN N. Then for any < R < M 1, RR N 1N.
When P.'s are not equal to each other, we turn to understand how R affect RR. In fact, we em- pirically observe that n. approaches the uniform distribution as R increases. This key observation illustrated in Figure 1. We consider the case where N = 500, B = 1 and assign each client random P; O. We then calculate RR for each R ranging from 0 to N distance from the uniform distribution. As shown in the figure, increasing f causes wards the uniform distribution. One explanation for this observation is that when R becomes larger, fewer clients are ready to be sampled in the current round, because many clients have not waited for enough rounds and hence are not available. Rather than dictated by the availability probabil- ity ps 's, which is the case for a small R and many available clients, here the sampling process is mostly determined by the waiting requirement. round, only B clients are available, hence all clients are sampled with equal frequency. Another point suggested by this observation that we can choose a large minimum separation in the practical scenario to reduce the asymptotic bias for existing FL algorithms, even with unknown p, ss
and measure its moving to-
the extreme case, when = M 1, at each
Please refer to Appendix B for the formal definition of the mixing time.

---

Published as a conference paper at ICLR 2025
Algorithm Debiasing FedAvg for correlated client participation
1: Input: initial point Te, stepsizes {a} some 0, Ào ON. & 0, Vi [N] for each client
2: for = 0, 1,..., do
3: A batch of clients St with size [Sa]] B is selected. The server sends current and model
to clients in S.
4: for E in parallel do
5: Each client sets f; + f + and calculates X [2+1)B and vi
6: for 1: L..... Client i updates its local model by
do
7:
1.+1 = 2 azi Vi(
(9)
8:
end for end for
9:
10:
The server updates its model #r+1 = B Eies, xt,K.
end for
12:
Output: är sampled uniformly from (x1 T-1
The above empirical observation verifies the formal the- orem that characterizes the debiasing effect of increasing minimum separation R in Theorem 2. (see Appendix D) for the proof).
10-2
norriitt uni((N))
Theorem 2. Given a set of pi's, with least ele- ment ps * N. Without loss of generality, let pP, be the B smallest values among all pa s. Define qa E}=1P Pj. then QB 1/M. There exists 8 > such that any size-B batch of clients B, picking from [N] \ [B), 8, == EiEB, Pt M-1l S 8. then an converges neighborhood of N IN characterized by
330
minimum Separation
Figure 1: || 1 1n/NIl R increases (N 500, B
I O(N-1)} as R ranging from 0 to { || 1. When = M 1, -M-1 - is the uniform distri-
bution supported on [V].
Theorem 2 states that when the availability probabilities p 's of clients are not too far away from each other or when B is relatively large (i.c.. 5, 's are small for all j), and when the total number of clients N is large, nn approaches the uniform distribution as R increases. It is worth noting that practically when the requirements Theorem 2 are not strictly satisfied, the effect of increasing on can be still observed as shown in Figure 1.
5 DEBIASING FEDAVG AND ITS CONVERGENCE
As we discuss in the previous section, existing federated learning algorithms like FedAvg cannot guarantee convergence the correct optimal solution if R < M M and p are arbitrary. Although we can reduce the asymptotic bias caused by тæ by increasing R, it may still be problematic under some particular circumstances. Clients have intermittent and non-uniform availability, and forcing large minimum separation R in practice may cause significant slowdown of the training in the FL. system due to the small number of available clients. The minimum separation R can be relatively be very different from each other, which then suggests by Figure I and The- orem 2, RR can be far from the uniform distribution, making the asymptotic bias non-negligible. We next design debiasing process that can be easily integrated into the existing federated learn- ing algorithms to address asymptotic bias. Our proposed algorithm based on FedAvg is given by Algorithm 1.
small and the p
The main difference between our algorithm and vanilla FedAvg lies the stage of local updates (Lines 5 and 7). Specifically, require each client to maintain estimator of its corresponding

---

Published as a conference paper at ICLR 2025
component of TR. which is only updated when the client is sampled. This estimator is later used to scale the gradient step during the local update. The estimator is designed by counting the times the client has been sampled and then used to compute the running empirical frequency of the client's participation. Recall that z represents the frequency of client i to be selected when / is large enough (i.e., when the Markov chain equation 5 becomes steady, meaning (n(( (tt). If we reweigh the local objective function fi by - (corresponding to vi " in equation 9), this weighting cancels FR the asymptotic bias introduced by unbalanced sampling, which drives the trajectory of the server's models towards the correct solution of equation 1. If we know RR for every client in prior, the above-mentioned reweighting method provides us with unbiased solutions. Then, X serves as a role iteratively approximate T round by round, which yields Algorithm 1. Also note that Algorithm I reduces to FedAvg if fixing X 1/N, Vi [N]. This shows the advantage of our algorithm: it is computationally cheap in the sense that each client only maintains two additional scalars (Af and vz) and can be easily embedded with existing algorithms by just multiplying the learning rates by vz. We note that other federated algorithms suffering from asymptotic bias due to non-uniform sampling could also benefit from our debiasing technique based on simple counting.
However, formally characterizing the convergence of of to N remains challenging due to the
samples of clients are not independent across different rounds. In particular, the clients sampled in the current round may affect those in the future, which makes the conventional concentration tools and law of large numbers not applicable. To address this challenge, we carefully analyze the transition of the Markov chain equation 5 and its influences on the marginal distribution of clients to be sampled to conclude that X₁ an unbiased estimate of & asymptotically. Then, we further leverage the fact that the Markov chain is irreducible as stated in Lemma to show that Xi is almost surely strictly positive even is infinite, concluding the convergence of vn to Ag as summarized in Lemma 2 (see Corollary 2 in Appendix G for the proof).
Lemma 2. Given λg ON. then vi, Vi [N] in Algorithm 1 satisfies
E 1 S 00( Tmiiz
for any O, where of vs J.N and it = (ot ,..,..., )) Tmin is the mixing time of Markov
chain equation
Based on the above, we can achieve the following convergence result of Algorithm (see Appendix G for the proof).
Theorem 3. Suppose Assumptions I and 2 hold. For any 0 S R < - and T > T'i log Tmii (with ct being some constant), choosing a ((1) vT)), the output of Algorithm I satisfies
E B|F δ
Tiic
+
where उr is defined as that Theorem 1; Tmii is the mixing time of Markov chain equation S.
Comparing Theorem 1, bounded gradient assumption is needed reach the convergence of our algorithm. Unlike the result in (Cho et al.. 2023) where clients are forced to participate in the system cyclically, our bound shown in Theorem does not grow as the number of clients increases. Particularly, for the bounds in (Cho et al., 2023) to be non-vacuous, the total number of communication round T should be proportional satisfy in practice especially when client number is super large. To prove Theorem 3 we critically rely on the fact that the Markov chain equation 5 is aperiodic to make analysis go through. That is to say our bound does not suit for R = M - 1, which is the limitation of our analysis. However, since R M is the cyclic case, where the Markov chain follows much nicer structure, one may be able to get better bound (Cho et al., 2023).
the number of clients, which could be hard to
We remark that our convergence result achieves nearly the same order of rate as Markon-sampling SGD literature (Beznosikov et al., 2024; Even, 2023) (where rates of O(yTmiz/ / + Tmiz Trsz/T) obtained). However, their analysis only suits for the first-order Markov chain and debiasing results are presented, while our results generalize to high-order Markov chain and guarantee ap- proaching unbiased solutions. We note that utilizing variance-reduced techiques may accelerate the
8

---

Published as a conference paper at ICLR 2025
convergence rate for Markov-samplinn SGD (Even, 2023). Then whether variance reduction can be used in our problem to design faster algorithms would be an interesting future direction.
It is worth noting that although uniform minimum separation R for all clients is placed throughout the paper, we also allow each client maintains its own specific R, vi E [N. In this more general case, could still use the same modeling technique in Section 3 where the order of the Markov chain is chosen to be an upper bound of all R s (e.g. max; R,). Then Theorems and 3 can be obtained without any modification as the analysis stays valid for any irreducible and aperiodic Markov chain. However, Theorem 2 becomes tricky in this case as our proof highly relies on nice properities of the Markov chain summarized by Proposition which now cease to hold. Therefore, more advanced mathematical tools might be needed in order to obtain similar statements as Theorem 2 when clients have various R2 s.
NUMERICAL RESULTS
In this section, we provide numerical experiments to illustrate our theoretical results. In particular, we compare vanilla FedAvg with our proposed algorithm (Algorithm 1) under non-uniform and correlated client participation described in Section 2. For simplicity, we partition the N clients into M groups and exactly one group of clients are selected at each round to fully participate in the system. Here we choose N = 100, M = 20. Since all clients in the same group participate in the system together once being sampled, group, where p; x i 1.5 i E [M] is a long-tailed distribution.
only need to associate availability probabilities to each
Synthetic dataset. We test Vanilla FedAvg and Debiasing FedAvg (Algorithm 1) under synthetic dataset constructed following (Sun & Wei, 2022): for each client i, A; E R is the feature matrix, where n, is the number of local samples and is the feature dimension. Every entry of A, is generated by a Gaussian distribution (0, (0.5i) - We then generate by E IR", the labels of client i, by first generating a reference point 0g E Rd where 0g ~ N(p Ta)) And μ4 is drawn from (a, 1) with
(0, 100). Then b, A,0, + E, with e, NO0 0.25In,). We set (og(( ((A.bi + b,D1)) + 1) where A. represents the j-th row of A; and bı[j] is the j-th entry of by The outcomes are shown in Figures 2a,2b, where Figure 2a shows that Vanilla FedAvg suffers from bias which can be mitigated by increasing R, and Figure 2b shows that Debiasing FedAvg effectively reduces bias no matter what value of R is set.
d = 20, n, = 100, Vi E [N]. And we define fi(z) = 1 Zi=1 log(
MNIST dataset. We also test our proposed algorithm under the MNIST dataset. Each client maintains a three-layer fully-connected neural network for training. All learning rates are chosen to be with the order of O(10-3) In Figure 3c, compare Debiasing FedAvg with Vanilla FedAvg and FedVARP (Jhunjhunwala et al., 2022), and Debiasing FedAvg can effectively mitigate the bias effect. Another interesting empirical observation is that increasing R can possible fasten the speed of both Debiasing and Vanilla FedAvg (as shown by Figures 3a,3b). This is yet not characterized by our theoretical demonstration. Here we conjecture that larger R corresponds smaller mixing time Tmii and hence faster rate as the bounds in Theorems 1,3 scale with respect to T We provide more detailed and intuitive discussions in Appendix I.
LIMITATIONS
Our Markov-chain framework works for that all clients share the same static minimum separation R and in the last paragraph of Section 5 we further allow static client-specific R,'s. However, more practical scenarios call for even time-varying R, which lies outside the scope this paper. In Theorem 2, we force the availability probabilities p. 's not too far away from each other to make the theory hold, while this assumption not required in practice. Moreover, Theorems 1,3 do not enjoy uniformly sampled. We believe
speedup in the number of clients FL literature when clients it is mainly due to the non-uniformity and time-correlation of the client sampling process and more advanced mathematical tools needed to show speedup in the Markov setting.
Many of the challenges in cross-device federated learning can also be addressed by system design in addition to algorithm design. For example, incorporating trusted execution environment (TEEs) in

---

Published as a conference paper at ICLR 2025
12--20
Fediig on form Sampero)
R=10
R-15
1063
02x36'
334
27
61>22
212433
3308
3006 4008
2000
5000
6250
6500
5730
1003
7250 7500
1750
8002
number of rounds
(a) FedAvg under different R after conver- gence (synthetic data)
(b) Debiasing FedAvg under different (synthetic data)
Figure 2: Experiments synthetic dataset. (a) The training loss of Vanilla FedAvg (after conver- gence) with different R is shown. Larger R leads to smaller bias. (b) Debiasing FedAvg is tested under different values of R, where the red line represents Vanilla FedAvg when clients are sampled under an oracle uniform distribution. The subtigure on the right shows that all curves reach unbiased objective after convergence, indicating that the asymptotic bias is effectively canceled.
Van Fedliy
Feewhop
kx32
Exta avrg hollng
100
325
210
600
1985
1988
Lare
430
612
1004
1200
number munds
numbar rounds
(c) FedAvg. FedVARP, Debias- ing FedAvg when R 8 (MNIST)
Debiasing FedAvg under dif- ferent (MNIST)
(b) FedAvg under different (MNIST)
Figure 3: Experiments on MNIST. (a) The convergence of our Debiasing FedAvg under different client minimum separation It configurations. The red horizontal line is the convergence value of the objective function by vanilla FedAvg when clients are sampled under an oracle uniform distribution. Our Debiasing FedAvg converges the unbiased objective with larger R converges faster. (b) For Vanilla FedAvg, increasing causes smaller bias. (c) When R = 8, Vanilla FedAvg, FedVARP and Debiasing FedAvg compared. Note that both Vanilla FedAvg and FedVARP designed only for uniform client sampling and hence are significantly affected by bias from client participation.
the FL. system (Huba et al., 2022; Daly et al., 2024) can potentially provide more control on client sampling.
CONCLUSION
In this paper, we consider FL with non-uniform and correlated client participation, where every client must wait as least rounds (minimum separation) before participating again, and each client has their own availability probability. A high-order Markov chain is introduced to model this prac- tical scenario. Based on this Markov-chain modeling, we are able to study the convergence per- formances of existing FL algorithms. Due the effect of non-uniformity and time correlation, FL algorithms can only converge with asymptotic bias, which can be reduced by increasing minimum separation R as shown by our empirical and theoretical results. Finally, propose debiasing algo- rithm for FedAvg that guarantee convergence to unbiased solutions given arbitrary non ae--uifformity and minimum separation R.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported part by NSF grants CCF-2045694, ECCS- CMMI-2024774, CNS-2112471, CPS-2111751, ONR N00014-23-1-2149, and a Google Research Scholar Award to GJ.
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Pro- ceedings of Symposium on Theory of Computing (STOC), pp. 1200-1205, 2017.
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International conference on machine learning, pp. 699-707. PMLR, 2016.
Alcksandr 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. Advances in Neural Information Processing Systems, 36, 2024.
Shalabh Bhatnagar, Mohammad Ghavamzadeh, Mark Lee, and Richard S Sutton. Incremental nat- ural actor-critic algorithms. Advances neural information processing systems, 20, 2007.
Jieming Bian, Lei Wang, Kun Yang, Cong Shen, and Jie Xu. Accelerating hybrid federated learning convergence under partial participation. IEEE Transactions on Signal Processing. 2024.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konecny, Stefano Mazzocchi, H. Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and Jason Roselander. Towards Federated Learning at Scale: System Design. SysML, April 2019. URL https: htmp:://wwiw /wwww syaml. cc/doc/2019/ 193.pd.
Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. arXiv preprint arXiv:2010.13723 2020.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022. URL "https:/ /ttps://azae /aaaaiivvvo./// org/ abs// 2010 0.10001 0
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. International Conference on Machine Learming, pp. 5677-5721. PMLR, 2023.
Christopher A Choquette- Choo, Arun Ganesh, Ryan McKenna, H Brendan McMahan, John Rush, Abhradeep Guha Thakurta, and Zheng Xu. (amplified) banded matrix factorization: A unified approach to private training. Advances Neural Information Processing Systems, 36, 2023.
Katharine Daly, Hubert Eichner, Peter Kairouz, H Brendan MeMahan, Daniel Ramage, and Zheng Xu. Federated learning in practice: reflections and projections. In 2024 IEEE 6th International Conference on Trust, Privacy and Security in Intelligent Systems, and Applications (TPS-ISA), pp. 148-156. IEEE, 2024.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Infor- mation Processing Systems 27, pp. 1646-1654, 2014.
Hubert Eichner, Tomer Koren, Brendan McMahan, Nathan Srebro, and Kunal Talwar. Semi-cyclic stochastic gradient descent. In International Conference on Machine Learning, pp. 1764-1773. PMLR, 2019.
Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In International Conference Machine Learning, pp. 1412-94399 PMLR, 2023.

---

Published as a conference paper at ICLR 2025
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low- variance and improved representativity for clients selection in federated learning. In International Conference on Machine Learning, pp. 3407-3416. PMLR, 2021.
Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint 1811. 1.03604, 2018.
Dzmitry Huba, John Nguyen, Kshitiz Malik, Ruiyu Zhu, Mike Rabbat, Ashkan Yousefpour, Carole- Jean Wu, Hongyuan Zhan, Pavel Ustinov, Harish Srinivas, et al. Papaya: Practical, private, and scalable federated learning. Proceedings of Machine Learning and Systems, 4:814 4:814-832, 2022.
Divyansh Jhunjhunwala, Pranay Sharma, Aushim Nagarkatti, and Gauri Joshi. FedVARP: Tackling
the variance due partial client participation in federated learning. In Proceedings of the Confer- ence on Uncertainty in Artificial Intelligence (UAI), aug 2022. URL pdf/2207. 14130. pdf.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013,
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascon, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi. Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecny, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrede Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Ozgur, Rasmus Pagh, Mariana Raykova, Hang Qi, Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Se- bastian Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao Advances and open problems in federated learning. arXiv preprint arXiv:
2019.
Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling shuffling. In International Conference on Machine Learning, pp. 5213-5225. PMLR, 2021.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J Reddi, Sebastian U Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for on-device federated learning. arXiv preprint arXiv: 1900.669,, 2019.
David A Levin and Yuval Peres. Markov chains and mixing times, volume 107, American Mathe-
matical Soc., 2017.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In Intermational Conference on Learning Representations (ICLR), July 2020b. URL https::////. /ttp//aavvvv../// org. atsp////bs/199../.. 02189.
Grigory Malinovsky, Samuel Horváth, Konstantin Burlachenko, and Peter Richtárik. Federated learning with regularized client participation, 2023.
Brendan McMahan and Abhradeep Thakurta. Federated learning with formal differential privacy guarantees. Google AI Blog, 2022.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agøura Arcas. Catpuunniicaio--fffffieeeee Learning of Deep Networks from Decentralized Data. International Conference on Artificial Intelligenece and Statistics (AISTATS), April 2017. URL https:/ // arxiv. org/ abs/ / 1602..0200 05629.
H Brendan McMahan, Zheng Xu, and Yanxiang Zhang. A hassle-free free algorithm for private learning in practice: Don't it tree aggregation, use blts. arXiv preprint arXiv:2408. 08868, 2024.
12

---

Published as a conference paper at ICLR 2025
Kumar Kshitij Patel, Lingxiao Wang, Blake E Woodworth, Brian Bullins, and Nati Srebro. Towards optimal communication complexity in distributed non-convex optimization. Advances in Neural Information Processing Systems, 35:13316-13333 2022.
Matthias Paulik, Matt Seigel, Henry Mason, Dominic Telaar, Joris Kluivers, Rogier Dalen, Chi Wai Lau, Luke Carlson, Filip Granqvist, Chris Vandevelde, et al. Federated evalua- tion and tuning for on-device personalization: System design & applications. arXiv preprint arXhv:2102.08503 2021.
S Sundhar Ram, A Nedić, and Venugopal V Veeravalli. Asynchronous gossip algorithms for stochas- tic optimization. In Proceedings of 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pp. 3581-3586. IEEE, 2009.
Mónica Ribero, Haris Vikalo, and Gustavo De Veciana. Federated learning under intermittent client availability and time- varring communication constraints. IEEE Journal of Selected Topics in Signal Processing, 17(1):98-111, 10,2,2,
Angelo Rodio, Francescomaria Faticanti, Othmane Marfoq, Giovanni Neglia, and Emilio Leonardi. Federated learning under heterogeneous and correlated client availability. In IEEE INFO- COM 2023 IEEE Conference on Computer Communications, pp. 1-10, 2023. doi: 10.1109/
INFOCOMS3999.2023..00 1022888877...
Zhenyu Sun and Ermin Wei. A communication-effcceen algorithm with linear convergence for federated minimax learning. Advances in Neural Information Processing Systems, 35:6060-6073, 2022.
Richard Sutton, David McAllester, Satinder Singh, and Yishay Mansour. Policy gradient meth- ods for reinforeement learning with function approximation. Advances in neural information processing systems, 12, 1999.
John Tsitsiklis and Benjamin Van Roy. Analysis of cemforal-difffrrence approximation. Advances in neural information processing systems, 9, 1996.
diffference learning with function
John Tsitsiklis and Benjamin Van Roy. Average cost temporal-differee difference learning. Automatica, 35(11):1799-1808, 1999.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication--fficcenn SGD algorithms. Journal of Machine Learning Research (JMLR), 2021. URL httpss:////xxi org/ abs/ Atss/180 18081180000 07576.
Jianyu Wang. Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization. preprint, May 2020. URL
https://arxe org/ abs
Jianyu Wang, Zachary Charles, Zheng Xu, Gauri Joshi, H Brendan McMahan, Maruan Al-Shedivat, Galen Andrew, Salman Avestimehr, Katharine Daly, Deepesh Data, et al. A field guide to feder- ated optimization. arXiv preprint arXiv:2107.06917, 2021.
Jianyu Wang, Rudrajit Das, Gauri Joshi, Satyen Kale, Zheng Xu, and Tong Zhang. On the unreasonable effectiveness of federated averaging with heterogeneous data. arXiv preprint arXiv:2206.047223 2022.
Shiqiang Wang and Mingyue Ji. A unified analysis of federated learning with arbitrary client par- ticipation. In Advances in Neural Information Processing Systems, 2022.
Shiqiang Wang and Mingyue Ji. A lightweight method for tackling unknown participation probabil- ities in federated averaging. arXiv preprint arXiv:2306.03400 034001 2023.
Blake Woodworth, Kumar Kshitij Patel, and Nati Srebro. Minibatch vs local sgd for heterogencous distributed learning, Advances in Neural Information Processing Systems, 33:6281-622 2020.
Ming Xiang, Stratis loannidis, Edmund Yeh, Carlee Joe- foe-Wong, and Lili Su. Efficient feder- ated learning against heterogeneous and non-stationary client unavailability. arXiv preprint arXiv:2409. 17446, 2024.
13

---

Published as a conference paper at ICLR 2025
Zheng Xu and Yanxiang Zhang. Advances in private training for production on-device language models. Goolge Research Blog, 2024.
Zheng Xu, Yanxiang Zhang, Galen Andrew, Christopher Choquette, Peter Kairouz, Brendan McMa- han, Jesse Rosenstock, and Yuanbo Zhang. Federated learning of gboard language models with differential privacy. ACL Industry, 2023.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participa- tion in non-iid federated learning. arXiv preprint arXiv:2101.1120: 2021.
Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Chen Zhu, Zheng Xu, Mingqing Chen, Jakub Konečný, Andrew Hard, and Tom Goldstein. Diurnal or nocturnal? federated learning of multi-branch networks from periodically shifting distributions. In International Conference on Learning Representations, 2021.
14

---

Published as a conference paper at ICLR 2025
A RELATED WORK
Non-uniform & correlated client participation. There is a recent surge of efforts to investigate FL with non-uniform client participation both from theoretical and empirical perspectives. Earlier work presumes that clients are sampled by the server uniformly, which guarantees the global model held by the server is unbiased estimate that in the full participation setting and hence allows extension of convergence results for the full-participation setting to the partial-participation setting (Jhunjhunwala et al., 2022; Karimireddy al., 2019; Yang et al., 2021; Bian al., 2024). The uniform participation is, however, far from the reality as clients may have their in- trinsic sampling probabilities p. 's that are non non-uniform due to, for example, intermittent availability resulting from practical constraints. Recent works analyzed the convergence behaviors of FL. algo- rithms when such p:'s are known as a prior or controllable (Wang & Ji, 2022; Karimireddy et al., 2019; Chen et al., 2020; Fraboni et al., 2021). However, pointed out by (Bonawitz et al., 2019; Wang et al., 2021), I), client participation pattern can highly depend on the underlying system characteristics, which is thus hard to know or control. As characterized by (Wang & Ji, 2022; Xiang et al., 2024), such unknown and non- non-uniform participation statistics causes a bias in the model updates as more frequently participating clients dominate the average update. In order to mitigate the effect of bias, (Patel et al., 2022; Ribero et al., 2022; Wang & Ji, 2023) introduced reweighting mechanisms com- bined with dynamically estimating client participation distributions. Such idea is also introduced in asynchronous distributed learning literature (Ram et al., 2009). Most works aiming at analyzing non-uniform participation, however, rely on the unrealistic assumption that every client participates in the system independently, which fails to capture practical scenarios where each client's partici- pation influenced by others across rounds(Kairous et al., 2019; Eichner al., 2019; Zhu et al., 2021). One interesting time-cor correlate participation pattern is that clients have to wait for at least R (called minimum separation) rounds between consecutive participation (McMahan & Thakurta, 2022; Xu et al., 2023). In particular, imposing minimum separation constraint has been empiri- cally shown to benefit privacy preservation in FL applications (Kairouz ct al., 2021; Choquette- Choo et al., 2023; Xu et al., 2023; Xu & Zhang, 2024). Instead, such time-correlated participation has not been fully investigated theoretically. The only work that partially captures the above case is (Cho et al., 2023) where the clients are forced to follow cyclic participation, which is an extreme case of very large R. Therefore, in this paper we study convergence performances of FL algorithms under non-uniform and correlated client participation, which provides theoretical explanations for their empirical counterparts in practice.
Stochastic optimization with Markoy-sampling, Another line of related works is stochastic gradient-based optimization under Markov sarpligs Unlike classical stochastic optimization lit- erature where i.i.d. samples are drawn during the training process (Allen-Zhu & Hazan, 2016;
Allen-Zhu, 2017; Johnson & Zhang, 2013; Defazio et al., 2014), many contexts, including TD- learning and reinforcement learning (RL), require to optimize the objective function by utilizing samples generated by Markov chain (Tsitsiklis & Van Roy, 1996; 1999; Bhatnagar et al., 2007; Sutton et al., 1999). Recently, the work (Even, 2023) provided convergence guarantees for SGD under Markov- sampling when the objectives are convex, strongly convex and non-convex. Then (Beznosikov et al., 2024) further proposed an accelerated method and generalized the analysis to variational inequalities. Both of them restrict on the first-order Markov chains. It has been shown by literature that gradient-basee based methods converge to the optimal solution of the objective induced by the stationary distribution of the underlying Markov chain (Even, 2023; Beznosikov al., 2024). This indicates that the final solution is biased if the stationary distribution is non-uniform and ex- isting literature cannot deal with such bias problem. In contrast, in this paper our analysis suits for higher-order Markov chains and the proposed algorithm enables the convergence to an unbiased solution without any information and constraint on the Markov chain and stationary distribution.
B PRELIMINARIES OF MARKOV CHAINS
In this section, we summarize several notions and properties of the conventional Markov chain (i.e., first-order Markov chain). We only focus on finite Markov chains, meaning the state space is finite. Note that for finite Markov chain, we use its transition matrix to uniquely represent it. Definition 2. Given a finite Markov chain with transition matrix P, we say it is irreducible if its induced graph is strongly connected, i.e., every state can be reached from every other state.
15

---

Published as a conference paper at ICLR 2025
Note that [P is the probability transiting from state to state j with exactly & steps, based on which we introduce the definition of aperiodic and periodic Markov chains.
Definition 3. The period of state is the greatest common divisor (g.c.d.) of the set {k E N [P*],, > 0). If every state has period then the Markov chain is aperiodic, otherwise is periodic.
In order words, the period of state can be achieved by caleulating the g.c.d. of the number of steps starting from and returning back. If the Markov chain is also irreducible, we have the following. Lemma 3. If the Markov chain is irreducible, every state has the same period.
Next important result states the convergence of the Markov chain. Lemma 4. Suppose a finite Markov chain with transition matrix P is irreducible and aperiodic. Then, there exist some E (0, 1) and C > O such that
max PK (x, a|lrv S SCpt
where a is the unique, strictly positive stationary distribution; || ||rv denotes the total variation.
Lemma 4 implies that starting from any initial distribution, the Markov chain converges to the stationary distribution at linear rate. Without confusion, we denote drv (Pk, 1 Im²) max, | -x;
æ|lrv. Note that drv dr (Ph,1m) mixing time of the chain.
1 11 Then, define the
Definition 4. Given any O, the mixing time (msss is defined as (m inf(l 1
(P 1x")) S E}. Conventionally, we denote Tmie = Emis (1/4).
Lemma 5. We have the following statements:
(1). drv (pt+), 1x S drv 1 v2
(2). For k 2 1i (2-k) (k- 1)Tmir.
(3). Moreover,
Σ drv 1n=)) S coTmiay v
for some constant > O.
Proof. The first two claims are shown in (Levin & Peres, 2017). To see the third claim, we note that
T
Σ dP' 1xT) s
Σ drv (Pk 1I7)
0=
k=0
(miz (t 1111)
Tmii
Σ 1=0
drv (Pl, 1mm
Σ E
drv(Pl 1TT)
2=
Iim (2-A))))) +1+1
< ddv Tmite
(tmi (2 (k+12) tmio (2 (22
ddyv SSrv(P,15 1x T
Σ km
k2 k Tmix
S
Tiiin + 2Tmin
which completes the proof with co drv (P, 1 +
C PROOFS OF PROPOSITION 1 AND LEMMA 1
C.1 PROOF OF PROPOSITION
Property (1) follows from equation 2, where by definition within R + 1 rounds, the clients cannot participate in the system twice or more. Property (2) follows from the fact that every client is
16

---

SR+1 := Published as a conference paper at ICLR 2025
sampled with probability proportional to its availability probability p; it has waited for R. rounds. Property (3) then directly follows from the definition of the first-order Markov chain and Properties (1), (2). Properties (4) and (5) are due to the observation that every row and column has exactly (B(M - R): B) non-zero entries due to Property (3).
C.2 PROOF OF LEMMA 1
It is obvious that the Markov chain is irreducible in the sense that all ordered sequences (Iz...., IR) can be observed due to every client has strictly positive probability to be selected. To see that it is aperiodic for R < M 2. we only need to show that starting from the state (Iı,...; .In) where I = ((k- - 1 +1,..... +1, such that the first return happens, which implies aperiodicity. This is because if a Markov chain is irreducible, all the states have the same period by Lemma 3.
................................ kB). k = l..... R. both R+ 1 steps and R+ 2 steps can be possibly taken
Then, we consider the following two constructed sequence. (II...., Ix. I II....,IAa for state IR+1 (RB + I..... (R + 1)B), where the length of h1 is 2R + 1. Denote h1 [k] as the entry at the k-th position. We construct the sequence V2,1, ..t..... Y++n) V+++11 (h1 (k mod (2R+ 1)], -....... hu [k + - 1) mod (2R+1) 1))),
Let h1
1,...,21 2R+ + i.e. starting from (I,.... ".....,Ii) Ir) exactly R+1 steps are taken to firstly return. Similar to the definition of h1, let h2 (Ii.... IR. IR+1, IR+2, II. ....... IR) with its length 2R + 2 and
state IR+2 = ((R+ + B)B + 1. RR + B).. We then construct the sequence (Y,,.... Y++R+1} as
Y (h2ík mod (2R + 2) ................... he2 [k + R-1) mod (2R + 2)))), k I..... 2R + 2, which
then suggests exactly R 2 steps are required to return back to (I1... IR). Combining these two
cases leads to the Markov chain is aperiodic for any R S M- 2.
D PROOFS OF PROPOSITION 2 AND THEOREM 2
D.1 PROOF OF THEOREM? 2
Let us first consider the case when B = 1 and given P1 > 0. P. = N-I Vi = 2....,
N. Then, for any 0 R N 1 and any (Jo..... (Ju...., jn-.). pick an arbitrary ju E (Ju.... By (which are the column sums for each column of PR and PR+1, respectively) and letting SR = ,j......
denoting 6R = b( Ppll: ((bb....jj-n]])) bR+1 = b b(Pntal,, (Ju....,
jRR for notation simplicity. By observing that when π is exactly the uniform distribution, the sum of PR for each column is exactly one, we then tend to prove that the column sum of PR asymptotically approaches one as R increases. We have four cases.
Case jo = [1). Then, for any 0 S R S N- 2, utilizing last two properties in Proposition 1,
bR+1 bR Pi
Σ
(pi + Σ
P pk) P1
Σ (p1
+
Σ
pt
ph)
KES R+1
iESc R+1
RESE
iESc R
P1 Σ
(pi +
1 Pi
(N - R- 2)) P1
(pi +
1 P1 (N - R 1))
N -
N - 1
RESE R+1
KE
= =N - R () +
1 1-p1 P1 (N R R22))
Pi - R) + 1- Pi
- (N - R 1))
N -
N -
Let = N - R - 1. We simply ba as
pi P((N-1))
bn
Pir
(N - 1)
+
1-p1
P1 + N-
PL
1 1- P1
Pi
Pit
+
I- 11 (r 1) N-1
Then,
bR+1 bR = Pi (1 Pi(N- -1(
1-p1
Pi + I-p1 (r 1) P1 + 1 -21 N-1
N
(1 - pp1)
- (1
PI(N - 1) (m +
1 pl (r- - 1)) -1
(p +
1 P1
r) -1
1-p1
N
N N-1
17

---

Published as a conference paper at ICLR 2025
which is strictly positive for P1 1/N for all 0 R R N - 2.
Case II: {1} E Sht1 Then, we obtain Pju
1-P1 N
and hence
1 - P1 (N - R- 1)) + (N - R- 1
1- P1 (N R- ---
bR/P3o = (P)o
NN
N N
-
+ +r(pi 1 P1 r)
N-1 "--
(1 pı)(r +)
-
N
MiNN- -1
(1 -1)pt)(r +1)
1-P1
1 1-P1
Pt +
1-P N-1
where we let N - R 1. Then, denoting p
1-m and
P1 yields
N-1
(bR+1 - bR)/Pjo
pt
pr(r+ 1) p + (r (rta)(+ta-1)-
pr(r+ +|(++1)(++//++aa))
(1-a)(1-
pr(r + + +r
Note that when P1 < 1/N, a < 1, which indicates bR+1 bR > 0, 04 S R N --3 by observing
p2 - a 2 0. Moreover, note that bR > 1, < N - 2 in this case by
a
= (1 - -a)r
bn = r +1 r+a 1r+))
+1>1
3 for a < 1. And a straightforward calculation gives bx-2 < 2.
which then indicates |óR - 1| <
2 VR < N 1. 1.
Case III: [1} E S% and {1} & Sh+1- In this case, Pjo gives
1-P1 N-1
P. Then, a simple calculation
(a- 1)r (bR+1- - bR)/P5o = P + 1(++1)(r+o) <0
when < <I/N.
Case IV: {1} & Sh. Then, all the clients available in both Si and Sh have availability probability p. Then, it is obvious that bR 1, 44 < R < N 1.
For Cases III and IV, we conclude that when p1 < 1/N and p. 1-p1 == 2...., N |bR+1-1| <
N
|RR 11. YO < R S
by further noting that by-1 = 1. By Case II, we then have all |RR converges J0, 0.5] R increases. Observe bN-1
corresponds to the that -N- is exactly the uniform distribution and so is N This indicates that л converges to some neighborhood of the uniform distribution 1 1N. In order characterize this neighborhood, we turn to carefully analyze Case II. i.c., b6R - 1 < 0.5. Noting that Case II corresponds to at most 1 R/N portion of columns in Pn and so does n, therefore the neighborhood is characterized by
[x || x 1Nll O(1/N)}
Next, in order prove the statement, we perturb each p: Nー 2,..., N by some scalar
& such that Σ/² O. Note that bR+1 bR is continuous in (E2, EE, EN) and is TR. which then implics that there exists some positive A > 0 such that bR+1 - bR preserves the original properties before the perturbation is added for all |e,] < A. Therefore, we achieve the statement that я converges to the neighborhood { || { 1vll = (1/NN) when B = 1. Obtaining always calculate the
the statement for B > follows the same technique by noting that equivalent 6; for each batch with size B. Specifically, given a batch of clients, say B,, then ñ; I[jes, Pj/C with suitable normalization constant C and we can then obtain the convergence of π.. to neighborhood of the uniform distribution by similar development.
18

---

Published as a conference paper at ICLR 2025
D.2 PROOF OF PROPOSITION 2
The proof of Proposition is straightforward by observing that bn - 1, vR when p; 1/N, Vi e
[N]. Then 1 PR 1 VR which indicates я is always the uniform distribution.
E INTERMEDIATE LEMMAS
In this section, present some useful intermediate results under the following generalized set- ting: we consider general global objective function defined Fx) = Σi waf((z) where Σ 1 and w 2 0, Vi E [N]. And we consider the following local update
#1,411 #1,x og V (x((,)
(10)
where of = "is for some positive sequence vŁ- Note that the above update equation 10 is a general- Vi
ized version of equation 9 in Algorithm 1. Then have the following useful lemmas when forcing the update equation 10.
Lemma 6. Under Assumption 1, we have for any x
[z) VF())] S V - 2G, e
Proof. Note that Assumption implies
N Σ
uc (Vf(z) - VF(x))I
Vf(c)) VF(*)]
N
S G Σ
W/ G.
Then, for any E [N]
< V
VF(*)] SG
Lemma 7. Given any t and i, we have || xzel² < 4,2 Vk
O,..., K, when S min { { skigg y
} and y S 1/3.
Proof. During the 1-th communication round, S, and of are fixed. Then, for any 3 > 0 and a S min 3 3Lo ). using Lemma 6 gives
|| - 2
- =
< (1
<1 <((-=~""i44s----4444444000XXX010 -TAGI))
+
2112 +
3 3)2
8
|1 x 2 2 + (1V
L2
3(1 + 3)y
(1 (1 1113333 (1+372) 23-
1|b
(AG² +
312
1+67²
3(1 + 3)72
$ exp
|
12
(AG² + [V
B²12
19

---

Published as a conference paper at ICLR 2025
for any / 2 1. Unrolling the above gives for any k= =0..... K --1
k-
622
1 1+
6y
3(1+ + n)2
| xz 12
exp
k
(G² + (VF((())))))
B
B²
K=
which further indicates by choosing 7 S 1//3
K
2BB 13(1 + 9)2
| - x 11 -
(4G² + (z))(
B²12
km
2K13
3(1 + 3)7
(4G² + IIV (z))1
21B
L
2K/8 - 1)37²
(AG² + (I)P((2,)11)))
172
2
[ 2
(AG2 + (VF((()))1
when choosing 3 = 8K.
Lemma 8. For any t 2 T, we have 1| 2z-7
1 <
Et [V)(()))
when o S mink Lg sKLq;) and < 1/3.
Proof. Note that
|, - xzll2 =1
Σ
L - xel1
S1
ieS:
| - 1211?
|
iES.
2
(4G² ([FF)
2
Then,
10,- x2-r| 2| ||
Σ
I1+1 - x1
1=t-T
1-1
S T
Σ
|,141 - 111??
1=t-
4,2
22 + 72 T Σ (x))).
$
1
I
l=t-r
Lemma! 9. For any E [t-T, t] with t 2 r 2 and a S mint
Lk skig
7
} with y S minf 1
27 }
we have
E [ < 4 (F 1672
max
t- t-rsist
Proof. For any L- < 11 L, we have
Fx))ll
< 2E VF + (z)
< 2T?
Σ
[ VF VF
1=
< 22222 1-7
max
E 22 + 2F aN (xt_,))1
1
max
V
E
27
21 VF 7f
2
1-75K51
20

---

Published as a conference paper at ICLR 2025
where the second inequality follows Lemma 8 and 7 f 1/(2r) in the last inequality. Finally, taking the maximum over 1 on the left-hand side completes the proof.
Lemma 10. Define Fw := Ei= wift for Σ wi L, w, 2 Suppose Assumptions 1.2 hold.
Considering any sequence vi that satisfies 2im1 Vi 1, 2 a > 0, vi E [N],t 2 0 and
letting of
wa Vi E [N], then, given T 2 Tiin log(1/0) with 0
8 < 1, for a S SaKI with
Vi
S min( 384TL 3847
I. 31. we have VT >
32aLA,
T-
VF (x)
T- Σ
[1
VF
( [x )|
(3t-
7(T T]
27
37
72
+ 32aLC2
37 + GyT +
+
T,
161.2
16aT.
32G T-1 T
Ell@d + 8c27802
and ei is some constant. Moreover, where ā a max:(w;) [w;). q: (g........ ..... x with qi = qt =,
TT G2 + (z)) - Fwl.
A, == E(F min Fv Fw. (x)] -
2
Proof. For notation simplicity, we drop subscript for af,e- Define of 2i Note that
x =
ag
(x())
k=0
T++1 34
aq
(x(z)
B
iES.
where St denotes the subset of clients drawn in the t-th round. Due to the smoothness of every fi, have
I.
F[Fu(1141) (xx)) s B(VF xz)
E E1 xzll?.
2
Considering 2 for any r 0,
x441 - -xr) -E E.(
ogii f(({)))))
iES. k=0
E(VFF
VF
Σ
aq f((f))
K
+ VE
0q) V (((())-)))
B
iE9t k=0
+ VE (x:
(V((((() v.(a.)))
169:
K
+
(V((()(())))) vf((zr)))))
B
16 k=0
21

---

Published as a conference paper at ICLR 2025
We first note that according to the conditions vi, w; S qi aw; with some positive constant
a < oo for every E [N] and Vt 2 O. Then by choosing a I
Sa Lam I min SKL 8KL max, max {
with 7 S 1/3 and Wm max; Wi.
K- og V
1 5 R
(
E
2
B
iESt k=0
1,2 <
K-1
Bla
x1--|| +
aq (V)()t) vf(())))
B
iES, k=
K- 1 iES,
+E
0q. f((a))
B
k=0
1
E|
F4- ?
KE
1
Σ
K-1
Σ
(a)
-
2
B
iES.
K-1
+E
aq.
B
(ES)
k=0
T7
Σ
2r
-
72
G²0²
2
641.2
16T.
72
E
1
Σ
vi(la))
64I.²
B
iES.
t-1
3x²
V + 27 + 1612 + 8BL2
E
G2
Bl B[VF((
2
64L
where we use Lemmas 7 and 8 in the fourth inequality; we use the fact FEll B Eies.
Vf((2,))1 s
2 (x)))) + 8G (G2/Ba B in the last inequality. Next we turn to bound e2. Note that
62 =KKE
(( B
Σ
4 (fi((=+>)) (F
S
ak
aK de (i Fc
EI
V
(x
- EE
E
F
2
B
2
iES
ak
E
E
2
B
EES.
aK
E
V
F
[
E
Σ
aK
E|
V
F
||
2
B
2
1
aK
< aKEE
V
F
EE
V
|
E
V
mm
(3+ 12
B
2
+ +aKE
Σ (gi - (()
B
iES.
where n: = wi and Fi-r is the filtration up t-r. Next, we provide the bound for E//V F.n (x)--)- E Eies, q. (z 11? Since we are focusing on the case for particular R, without causing confusion, we drop R for notation simplicity in the following analysis.
Denoting vi == lim P(S, S), we have
Es. U'S.
Es, USS.
N Σ S. 1/8.
B
22

---

Published as a conference paper at ICLR 2025
where S, denotes any set with size B containing Then, for any vectors {ur have
ΣΣ SES EE
Σ
Us
Vi
8 π
where S is the collection of all sets with size B. Thus, by letting es = wi w:Vf((((-r) in the above, we obtain
F
E( Σ (
iES.
(
ΣΣ = - SES
=E 1 ΣE (P(S ( S(F- 4S) d B SES
by noting q. ws/n'. Moreover, P(S. -) can be uniquely induced by Φn((t defined by equa- tion under proper linear transformations, which also indicates that P(Se Fi-r) = P(S: =
St-)). Thus, Lemma 4 implies PP(S: = 5 Fi-r) vsl S e₁ cTmni V C for some e > 0.
N
SS when r 2 Tiin log(1/8 with CP
Then,
B
E F (I: (zt-r)
g. (
B
iES.
E
(P(S: = S/F:-) 4s) 9 V fi (x)_T)
B
SES iEs
E
(P(S: S|F,,) 25)9. v (x)
iES
SEES
2 S
11 V Si (xx
min
B
iES
< (E) 4G2)
where we use the fact that
[
Utilizing the following
E
E lat (()
E
1
Σ
B
tES.
iES.
8G
+
2E
|
where we denote क.. of G. Then bound
aK 12
1) VF + 2aK
4E (112) + +2KE [F(2.-))13].
62
23

---

Published as a conference paper at ICLR 2025
In order to bound e3, note that according to Lemma 7 for S sKLa S SKL
K-1
63 S E
V || [V] - v/i(a|)]
B
IES.
(aq')2 K
L
| x= =11 )
< E
VF (x) (-- )1 +
B
2
2k
EES
K-
72
(x + (I AG3) ]
E
V (32 11
(1]
B
1281,2K
2K
VESt
h=0
7/2
-
18|
V
(zx_r)
)1
+
EB| V (x,))1 (
128
2
Finally, based on Lemma 8, similarly we obtain
64 S E
aq = - (.((
iES,
K-1
(a
L2
|,, 22-111 112)
E
VF )1
B
2
2K
VES: k=0
72
7AT
1-1
E
(
VF
+
(
Σ
E
V + 47G²).
128L2
2
1=t-
Thus, denoting ā max; {w:}
E V Far (21 S ((F - (. + T72(1
72
E| VF (x)))
16aL
2
?2
72
372
V (Tx) 12 + 7
+
+
+
E
2
2L
64L2
aL
VF (Ix M13 + 7o/0 G2
+ γ
E 11
47L
2
3
+ 022
2
2T + 27
+ + 161.
702
72
+
E
(1++)) 2
8ØL
64I2
24

---

Published as a conference paper at ICLR 2025
which implies that
16aLT +1+1+++ 72)
1-1
> V (5c-
16aLLE(Fu(0. (x+41))) +
Σ
E
V (x)))
2
1-t-
+y 16all - 80y + 30y
E (x)))l +4c
4L
+ +4ylE [1IT:113
V (F -) ||
+ G
2 3
+ C
2+ 2T + +2727²
+
L 16L2
+7 (2076²
87
B|| VF (1
4L
30y
$ 16aLE| (x)(
F (x+41)) +2
+ + 80y +
E
V F (x)))
4L
+ (20760
a7
+ 32 + (1 + E (x-
4L
4 [llãell
16 El
47070002
2
3
+ G2
2 22/2
L 16L
where we make use of by Lemma 9, Under the following conditions
Σ
(r10/))))PP//1)///00o0/0-))11 22
20 - 6'
@n
S
7 5 min( 1
}
4L 36'
2r" 384
64alTy S
12'
which implies 32aIr)(1+7)) < _/ and hence 202 + an + +212)7(1+72) < 1.
then we obtain
3
32... (II)) F (x+++)))) 1) 27 16āl. + 80y +
E V F.n (2x)
4L
+ + ||
VF. - 32 113 0
2
3
32 22+
+ 16L2
Summing over T St5 gives
T-1
T-1
V (2)-))11 32aLA, + +27 [1GaLy+877 88y +
3
E
V Fu (1
4L
87
E [1lTe]] VV (o + G2
Σ
Bllgg &se
2
3
3 13662 6-2 + T, + 322
(T- GT
1672
where A, = E(Fu (z,) F and we use 7272 < 1/4. Again leveraging Lemma 9, we observe
E V Fu E <
25

---

Published as a conference paper at ICLR 2025
which thus renders
T Σ F
1
320LA, )1 7(T -T)
+
8
Σ
T-1
[1
FV,, (1)
T T
27
37
72
+ +222LG2
37 +67+
+
+ 8c702
L
161.2
16aT.
32G T-1 +
11
by noting that 16ãLy + Say + In the following, we turn to bound A,, Noting that
3ä7 4T
S T6
K-1 [v(Et) +
a²L
Σ K-1
Fo - Fu((ze) S (V
Σ
fa f((x)
BK
2B²
iES, k=0
iES k=0
ak 2
K (V)(()))) - (zI()
aK
V F (x,)))
BK
2
iES, k=0
by S SaLK
1 2LK
Moreover, since
2
(V)((+)) - (Fu(Ie))
I
(L 12 =112+ 1G3)
BK
BK
iES,
k=
iES, k=
$ V + 8G2
conclude that
Fa( - (x)) S aK
(1 - VFF + 4aK - 7 G2
2
2aL
which implies
A = E(Fu - Fr] < YT
G² + Fu - F
24L
F CONVERGENCE ANALYSIS OF FEDAVG UNDER CORRELATED CLIENT PARTICIPATION
In this section, we provide the convergence analysis of Vanilla FedAvg for correlated client partici- pation. We first show FedAvg suffers from unavoidable bias (stated in Theorem 1), summarized by the following proposition.
Proposition 3. There exists a problem case such that FedAvg converges with unavoidable asymptotic bias.
Proof. We consider problem case with N = 3, B = 1, We set P1 = 0.25, = 0.25, P3 0.5 and fi(x) (x - i)2 1,2, 3 and R. In this case, we have the Markov chain induced by the problem denoted by P E p3x3 Letting
R be the stationary distribution of P, straightforward calculation gives क n2 0.3, R3- = 0.4. Then we obtain the server's update of FedAvg given by
T++1 Bz, + (1 -3y
where / = (1 a)* K client round which is random variable. Taking the expectation on both sides yields
< with a being the stepsize of local updates; i, is the index of the sampled
E[
[3[22] [ + (1 - = P'T [
+ (1 (3 pt ITTI++(1 3)x
26

---

Published as a conference paper at ICLR 2025
where μ (p1. P2. Pa), and I (1, is the vector formed by clients' indices. Noting that the third term vanishes as + oc due to the convergence the Markov chain (shown by Lemma 4), we conclude that lim [[ma] = Ei= me which is the minimizer Fx = >i=1 mefi(a) but not F(x) 5/ Ei= f(()). And (F"(""") I (Λ {11)1. Therefore, the bias in Theorem is unavoidable.
Then show the convergence result of FedAvg.
Theorem 4. Suppose Assumptions 1.2 hold and assume [F & D, Vx. Then, by choosing
0 x and T 2 2Tmiz log Tmizi the output äT generated by FedAvg satisfies
Ao
Tmiz log T
VF
O +0
+ +0 ((TTmis log" T + + G²)
7T
T
1
+0 (G²
D2)[[T
INlf
N
where Ao == (z)) min, Fz)) and Tiix is the mixing time.
Proof. For FedAvg, we have v = 1/N. Utilizing Lemma 10 and setting w; = N. it yields
32L 7(T -
8 T-1
36G T-1
Bllge + 16r
E V
+ T- E=
B + T-
T
T-T
t=0
+ 32LG2
(3
33 + 6yT²
27
+
37
+
72
+ 8c/0²
L
16L
16L
Then noting that llão1130 S Tiin ||
Nv 11 we conclude
Au +
TG2
+ ((TT² + + ( (G
E V
N 1wll
TT
T
N
by setting ő = -1/VT. For the above to be true, we need T 2 Tiir log T, which is actually always satisfied for T 2 2mmix log Tmir- To see this, we observe that if Tmias Tmis log T
2Tmir log Tmin; T 2 miiax Tmix log T & log S T. This completes the proof.
The following corollary restates the convergence result of Theorem 1.
Corollary 1. Suppose all conditions in Theorem 4 hold. Then, choosing = (KTi(Kmmiz VT)), the oulput ãt of FedAvg satisfies
Tiia
+ =0(12+
N - 1N IN It)
VT
Proof. The proof is straightforward by simply plugging in 7 = ((1/(T(T) and r Tmix log T to Theorem 4.
G CONVERGENCE ANALYSIS OF ALGORITHM
We first provide the following theorem showing that yt serves as a reasonable estimation of m/ Theorem 5. For any veal-valued function f E R. and any initial distribution E R.N, we have the following:
12
Σ
((xi)-
TTI
IT Q 1F))R
TE
f(X,)
< fd IR (I- - 1N + ca NT
T 1=0
TE,
1
Σ
f(Xi)
- -Tf
< TERR
[ f(xi) -x75
1
+3cuN221oo1B3 Tiin
T
T
t==l
1=0 1=Ul
27

---

Published as a conference paper at ICLR 2025
where E.).) means the initial state Xo follows μu; IR diag(TR (i) and Q}, is defined such that
μ² Q" Sn and Cj Qn = μi g = f fRRiii Tiia is the mixing time of Pn-
Proof. We firstly show the first equality. Note that
T-1
T-1
H f(xi)
Σ
(1t PhQnf P
-
T 10
km0
7 Σ n" (PP QR]
R=
where we observe that μ²' 1.
Then we turn to show the second inequality. By the definition, we have
1 T-1
2
T-1
TERR
E f(xi)
-Tisf Varan (f(Xo)) +
2
Σ (T (f
T
T k=1
(11)
For any k. let Sk and मं be the distributions after the Markov chain evolves steps. Then, we have ST 27 PR and oh = C QR. Defining Q& E Nxd(M, R) as an inverse mapping from Ty to
Sk. i.e., _ oh Qx. it is straightforward to verify that we can always pick nonnegative Q% such
that Q 1 I in the sense that the freedom of Qu is (N - 1) d(M, R) N when forcing both co nे Qu and Q 1N hold. Moreover,
Cov (f(Xo) = Σ (R)is(()) E(NPARR) Σ W
= =' NTT (F RF
where we utilize Q+1 1y. Further, 1|Qu = 1, 2 0 since Q2 is nonnegative. Then,
Cov (f(X)), f(Xx)) I maax |1 |P 16h
Substituting it into equation 11 yields
T Σ
2
TE
f(xi) - -
s Var (f(Xu)) + > Cov (((X)),f(X))
T 1=
kml
< Var (f(Xo) 2m max 11 1R
Σ
|| | 1
k=
$ T I cy
11 Tmiz
where we make use of Lemma 5. Finally noting that |Q < 11n.all & N completes the proof of the second inequality. To obtain the third inequality, defining g(i) = f(i) T we aim to bound
T-1
8(Xx)
2
ENn
1
1
T-1
Σ
(Xx))
T
k=0
T-1
T-1 T-1
<
Σ
Engg
2 (Xx) - -Erng((Nr))
+
Σ
Σ
(o(x))))))))) - EE (o(x))))))))
k=O
k=O
1=k+1
28

---

Published as a conference paper at ICLR 2025
For notation simplicity, we drop the subscript R without confusion to get (x(o())))(Xi)) - Bun (o(Xx))((x))
Σ f
(ot - mz) -() m
Σ p= 10) D(Qi( - 15 -(((()=>1("")))))) ()))(r))))))) A
I N -15-111-1 1l00
Thus, by Lemma 5,
T
Ep
1
Σ
s(Xx))
EERR 1
Σ k=U
g(Xx))
T
K=0
Σ nd Q - -1c")09² +
T co. N2 1191
2
Tiin
T Σ n² Q - -16=)Q9² + 2c (1911e
Tiir
k=0
$ 20 Tmiz 2c0 Tmie
Tmiz
$ 30. 1gl| Tinia
where n² denotes the elementwise square of g. Combining all the above completes the proof.
Then, the following corollary induced by Theorem 5 is exactly Lemma 2. Corollary 2. Given initial No ON and let vi N as in Algorithm 1, we have
E E 11 S
Tmiz
where 8/ =v 2x and in (it ( D.
Proof. By Theorem 5, setting f = e; for any i, we have
N Tiai
B(A T:)² 0
(12)
Note that
X ne
X
E(DD)2
E
E.
{ 2 a
P() 2 a)
N
AfTTy
N22
A
1
X
π
2
P( <a)
(13)
N2
XtT
for any positive a. Moreover, due to the Markov chain in Section 3 is irreducible by Lemma every client will be visited infinitely as t goes to infinite, which then implies there always exists some strictly positive constant Gg independent of such that X₁ 2 ag almost surely for any E [N]. Combining equation 12,equation 13 we conclude
E b>
11
O
Timia
t
29

---

Published as a conference paper at ICLR 2025
G.1 CONVERGENCE PROOF OF ALGORITHM
The following lemma is useful to derive the convergence proof of Algorithm 1.
Lemma 11. Supposing that the stochastic scalar sequence E[U2(t)?} S u(t) with u being mono- tonically decreasing positive function w.r.t. L and assuming that Us (L) S oo almost surely, then given any ó, e > 0, for all i 2 (lo u(la)/8² S e/m²} and stochastic scalar sequence U2((),
E U22)()))2(()))
S (E (0)E)(2U((1)
Proof. For any > O, we have for all 2 14 m((o)/0² s <c/"²) U(2((1)) P(U)(() > (1) Ui(() > 6]+ P(U)()) S () | s
((U)(t) > 8) (t)
( (((U(()
where we the Markov inequality in the last step, i.e.,
((Ui(t) x > 5 u(l)
8
Then we are ready provide the proof for Theorem
Proof of Theorem 3: As discussed in the proof of Corollary 2, we know that there exists positive a- which lower bounds each X; for all almost surely, implying that Ey any > T > d'iiiz (with e' being some constant), we have
S N (a + )min). Then for
E [1 1i VF(*==))
< [(
16
by Lemmas 2 and 11. Further Utilizing Lemma 10 with setting ii +. we obtain
1 T-1
64āLAo
64G2 T-1
32rG²
E V
Σ
B
+1G2,82
T
7T 7T)
T-
T-
27
72
64aLG²
33 + 6y72
16L
16aL
for 2 Tmiz max(c'
Similar the proofs of Theorem 4, setting ō 1/VT, with 2 c. T'ii log Tiin for some constant ct, we finally conclude that
V
δ
Timix VT
+ O (
by choosing 7 ((I((TVT) with т 52( log T) and by leveraging the fact that
T-1 TET E1 = O(Tri log T) implied by Lemma 2. This completes the proof.
H ADDITIONAL EXPERIMENTS
In this section, we compare Vanilla FedAvg, Debiasing FedAvg (ours) and FedVARP under the CIFARIO 10 dataset given the same participation pattern as in Section Each client maintains a CNN with three convolution layers. Learning rates for three algorithms
selected to be with the order of O(10-3). 3). In Figure 4, Debiasing FedAvg achieves the highest training accuracy due to its debiasing nature shown in Theorem 3, while Vanilla FedAvg and FedVARP suffer from bias. Moreover, in Table 1, the training and test accuracies for different are presented, where one can see that Debiasing FedAvg achieves the best performance.
30

---

Published as a conference paper at ICLR 2025
0.5
63-
toartry
rambe cuund
maabba rounds
(a) FedAvg, FedVARP, Debias- ing FedAvg when R = (CI- FARIO)
(b) FedAvg, FedVARP, Dehias- ing FedAvg when R = 10 (CI- FAR10)
(c) FedAvg, FedVARP, Debias- ing FedAvg when R = 15 (CI- FARI0)
Figure 4: Experiments on CIFARIO. The training accuracies of Vanilla FedAvg, Debiasing FedAvg (ours) and FedVARP are compared given different values of R. The results show that Debiasing FedAvg achieves the highest accuracy and outperforms the other two, since FedAvg and FedVARP suffer from bias.
Rt 5
R 10
R 15
Algorithms
Train acc
Test acc
Train
Test
Train acc
Test acc
FedAvg
74.9%
67.6%
75.3%
68.8%
75.6%
70.1%
FedVARP
76.7%
68.0%
77.5%
69.4%
79.5%
72.5%
Debiasing FedAvg
79.3%
73.8%
81.5%
74.9%
82.9%
74.1%
Table Training and test accuracies for different R under CIFARIO
I THE INFLUENCE OF R ON CONVERGENCE RATES
In this section, we discuss the effect of different values of R on the convergence rates of Debiasing FedAvg g and Vanilla FedAvg as observed empirically in Figure 3. We simulate the "effecctive" client sampling distribution (i.e.. ()())) time evolves for different minimum separation R, where set N 100, = 1. The code for all experiments can be found through htspp::// // / thub. com/ Starrskyy debias fl. Figure 5 shows the total variation distance of the evolution of client sampling distributions to their corresponding stationary RR'S. s. Clearly increasing It, the convergence rate of "effective" client sampling distribution the stationary distribution also increases, implying the decrease of mixing time Tmix (see Appendix B for details). Combining this observation together with Theorems and leads that larger implies faster convergence rate, which then consistently explains the observation in Figure 3. However, the above explanation is only from an empirical perspective. More rigorous explanations need theoretical advance in the convergence results to reveal explicitly the relation between the rates and values of R.
31

---

Published as a conference paper at ICLR 2025
R=20
R-20
R-88
10
2000
4000
8000
20000
Figure Convergence of client sampling distribution TR for different R (NV 100, 1).
32


Reviews:
[{"review_id": "rb4WNdTvaP", "reviewer": "Reviewer_GYuM", "summary": "This paper studied the federated learning problem with partial client participation. In particular, it focused on the case where there is minimum separate between clients in terms of minimum rounds. The authors formulated the client participation process as a R-th order Markov chain and characterize the marginal stationary distribution of clients to be sampled. The authors proposed a debiasing FedAvg based on the estimation of this marginal stationary distribution and provided the convergence analysis of the proposed algorithm as well as the original FedAvg algorithm. There are several very interesting observations of this paper. The performance of the proposed algorithm is also verified using simulations.", "questions": "1. The algorithm is based on GD instead of SGD. If SGD was used, will there be any challenges?\n\n2. I suggest the authors put the proof of Proposition 1 in the appendix.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors formulates the client participation process as a R-th order Markov chain. \n\n2. The authors proposed the debiasing FedAvg algorithm based on the estimation of marginal stationary distribution of clients to be sampled. \n\n3. The authors provided the convergence analysis of both FedAvg (to indicate the problem) and the proposed algorithm which can converge.", "weaknesses": "1. The paper is not well written and there are some notations not explained, e.g., $\\tau_{mix}$ (is it the mixing time?) and $p_e$, although the paper presented quite a few interesting ideas. \n\n2. The authors discussed quite a few limitations of the proposed approach and its proofs. These seem the weaknesses of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FGCkYAipvT", "reviewer": "Reviewer_Yi23", "summary": "This paper proposes a theoretical framework that models client participation in FL as a Markov chain, enabling the study of optimization convergence when clients exhibit non-uniform and correlated participation across rounds. The authors find that FL algorithms converge with asymptotic bias, which can be mitigated by increasing the minimum separation $R$. Additionally, they propose a debiasing algorithm for FedAvg, providing both theoretical and empirical performance guarantees for this approach.", "questions": "1. Theorem 2 holds only under specific requirements. What about more general settings that relax these requirements?\n2. The authors claim that each client can maintain its own specific $R_i$. In this more general setting, Theorems 1 and 3 hold without modification, while Theorem 2 becomes more challenging. What modifications would be needed to obtain Theorem 2?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The authors introduce a theoretical framework that models client participation in FL as a Markov chain, allowing the study of optimization convergence when when each client must wait at least $R$ rounds before participating again and has its own availability probability.\n2. Through both theoretical and empirical results, the authors find that due to non-uniformity and time correlation effects, FL algorithms converge with asymptotic bias, which can be reduced by increasing the minimum separation $R$. \n3. To achieve unbiased solutions, the authors propose a debiasing algorithm for FedAvg, with performance guarantees provided through both theoretical analysis and empirical evaluation.", "weaknesses": "1. The authors restrict the choices of $R$ to range from $0$ to $M-1$. However, the theoretical analysis only considers cases where $R$ ranges from $0$ to $M-2$. It would be beneficial to include the results for $R=M-1$.\n2. In the experiments, the authors simplify the algorithm by partitioning the $N$ clients into $M$ groups, with exactly one group selected in each round. This setup does not align with the more complex proposed algorithm and is insufficient for a comprehensive evaluation of its performance.\n3. The experiments are only conducted on synthetic dataset and MNIST dataset, which is relatively simple. More complex datasets (e.g., CIFAR-100, Shakespeare) and tasks (e.g., NLP) are recommended for a more comprehensive evaluation of the proposed algorithm's performance.\n\n\nMinor: In line 109, delete “some”.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "W7XUAq2mx4", "reviewer": "Reviewer_Cr1N", "summary": "This paper finds that traditional FL algorithms like FedAvg assume clients participate independently and uniformly, which is unrealistic in practical applications. It addresses the bias in FL due to non-uniform and time-correlated client participation. The authors introduce a Markov chain model to simulate the sequential and dependent nature of client participation, where each client waits a minimum number of rounds before participating again. A debiasing algorithm for FedAvg is proposed to improve convergence and ensure unbiased model updates. Empirical results also demonstrate that Debiasing FedAvg effectively reduces bias during training.", "questions": "1. If there is extreme heterogeneity among clients, how might a larger minimum separation $R$ impact the model's performance?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The authors find common FL assumption that clients participate independently and uniformly is unrealistic.\n2. The paper frames client participation as a Markov process, capturing real-world constraints and interdependencies among clients.\n3. The paper proposes Debiasing FedAvg converging to an unbiased solution with theoretical analysis.\n4. Experiments on both synthetic and real datasets validate the algorithm’s effectiveness.", "weaknesses": "1. The paper claims that a larger minimum separation $R$ reduces bias. However, it lacks a discussion of how $R$ affects the server's model performance on the test set empirically and how to choose the best $R$.\n2. The paper assumes a uniform minimum separation for all clients, which may not reflect real-world situations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xyhyUQMapX", "reviewer": "Reviewer_ehNB", "summary": "Existing federated learning algorithms assume clients are sampled uniformly at random at each iteration which does not reflect the real scenario. In this paper, the authors assume that each client requires a minimum separation of R rounds between sampling. Then they model client selection as a Markov chain to theoretically analyze the setting and propose a debiasing algorithm with provable guarantees.", "questions": "Are Markov-chain model really necessary to analyze this problem?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- Motivation: the minimum separation in federated learning is reasonable to analyze.\n- Literature review is thorough.", "weaknesses": "- The FL setting is not rigorous. In line 121, authors use $p_i$ to capture the willingness to be sampled at each iteration which means a client may not join the training for arbitrarily long amount of iterations (with small probability). However, in line 128~129, it is claimed that \"the cyclic participation corresponds to the case, R = N / B − 1\", which means in the last round of the cycle, all of the remaining B clients will definitely be sampled. So the setting is not consistent. Besides, forcing clients to join cross-device federated learning is not practical.\n\n- As has been mentioned in the \"Limitations\" section, the theoretical results do not enjoy linear scalability.\n\n- I am not very convinced that Markov-chain Model is necessary to analyze the problem. The algorithm 1 essentially only try to estimate p_i and then inversely scale 1/pi to gradients in order to have uniform weight to all clients. \n\n- The presentation of the paper can be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)