Debiasing Federated Learning with Correlated Client Participation

## Abstract

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 general and practical pattern: every client must wait a minimum number of R 𝑅 R italic_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.

## 1 Introduction

The massive amounts of data generated on edge devices such as cellphones or sensors offers an opportunity 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) [, , , ] has emerged as a 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 operates 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 intermittently connected edge clients, in each round only a small subset of them participate in training []. 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 study the effect of such client participation patterns on convergence of federated training.

The federated averaging (FedAvg) algorithm and its variants are widely used in practice [, , , ], and the convergence has been extensively analyzed in literature [, , , , , ]. 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-participation setting to be extended to the partial participation setting resulting in an additional variance term appearing in the convergence bound [, , ]. A generalization of the uniform client participation model is to consider that each client has an intrinsic availability probability $p_{i}$ that is either known or unknown 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 [, ] or their estimates [, ]. 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 assumption fails to capture practical settings where the client participation are correlated across rounds due to memory or time-dependence constraints. In cross-device FL systems, a device can only be available for training when it is plugged in for charging, connected to unmetered network and not being actively used by the owner [, , ].
These criterion, which typically occurs during the night of the devices’ local time, not only results in the client availability probability for non-uniform client participation, but also correlated client participation of a periodic pattern due to user preference and time zone [, , ].
More recently, a new criteria is introduced on devices in a FL system to impose a minimum separation constraint on successive participation instances of a client [, ]. Specifically, once a client participates in training, it cannot become available to participate for at least $R$ more rounds ($R$ specified by the central aggregating server).
The minimum separation is introduced to effectively combine differential privacy (DP) and FL [, ] as advanced privacy-preserving methods, and quickly becomes the default criterion in many FL applications [, ].
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 [, ]. However, setting $R$ to be the exact value for cyclic client participation 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 [, , ] do not fully explain the effect of such correlated client participation patterns, calling for new theoretical advances. We provide further comparison of our work with related literature in Appendix A.

In this paper we 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 to analyze the convergence of FedAvg with a minimum separation constraint on successive participation instances of each client, which is a 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 probabilities and incorporates them in the local updates. We prove that this algorithm achieves an unbiased solution that is consistent with the global FL objective under arbitrary minimum separation $R$.

Notations:
For any positive integer $N$, we denote $[N]=\{1,\dots,N\}$. Let $\|\cdot\|$, $\|\cdot\|_{1}$ and $\|\cdot\|_{\infty}$ denote $l_{2}$-norm, $l_{1}$-norm and $l_{\infty}$-norm, respectively. For an ordered sequence $\{i_{1},\dots,i_{k}\}$, it is represented by $(i_{1},\dots,i_{k})$ and we use the same notation for a vector when the context causes no confusion. Unless otherwise specified, $\mathbb{E}(\cdot)$ means the total expectation taken on all randomness. We use $\mathbf{c}$ to denote the vector where all entries are $c$. The $d$-dimensional Euclidean space is denoted by $\mathbb{R}^{d}$, and $\mathbb{R}_{+}^{d}$ is the space formed vectors where every entry is strictly positive.

## 2 Problem formulation

We consider the federated learning setting where $N$ clients cooperate to minimize the following global objective:

$$ $\min_{x}\leavevmode\nobreak\ \leavevmode\nobreak\ F(x):=\frac{1}{N}\sum_{i=1}^ {N}f_{i}(x)$ (1) $$

where $f_{i}$ is the local objective function of client $i$. We aim to solve problem (1) in the federated learning setting, i.e., the system implements the some federated learning algorithm which operates in rounds. In each round, a 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 communicates 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 $t_{i}$. It may join again at any round $t$ with $t\geq t_{i}+1+R$ and not before then. Moreover, when a client is available to be sampled, instead of assuming uniform sampling, we consider that each client is associated with some *unknown* strictly positive scalar $p_{i}>0$ to characterize its intrinsic willingness to be sampled at every round. Without loss of generality, we assume $\sum_{i=1}^{N}p_{i}=1$ and hence refer to $p_{i}$ as the availability probability of client $i$. Therefore, the client participation pattern is as follows: at each communication round, client $i$ is sampled to participate in the training process with probability proportional to $p_{i}$ 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 $R=0$ means each client is sampled at every round with probability $p_{i}$ independently, which is consistent with []. And the cyclic participation [] corresponds to the case $R=\frac{N}{B}-1$ where $B$ number of clients are sampled in each round , assuming the total number of clients in the FL population $N$ is divisible by $B$. We investigate the potential bias introduced by the non-uniform and correlated client participation on federated algorithm performance and propose debiasing scheme to mitigate it.

## 3 Markov chain model and its properties

In this section, we propose a Markov chain model to capture the correlated participation scenario described above. Intuitively, the fact that every client cannot be sampled again within $R$ 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 a Markov chain with $R$-memory, also known as $R$-order Markov chain, defined as below.

###### Definition 1 .

Let $\{X_{t}\}_{t=0}^{\infty}$ be a stochastic process where $X_{t}\in\mathcal{X},\forall t\geq 0$. It is said to be an $R$-order Markov chain if

$$ $P(X_{t}\mid X_{t-1},X_{t-2},\dots,X_{0})=P(X_{t}\mid X_{t-1},\dots,X_{t-R}), \leavevmode\nobreak\ \forall t\geq R.$ $$

$\mathcal{X}$ is called the state space.

If $R=1$ it reduces to conventional Markov chain; if $R=0$, then the clients can be sampled at each round with probability $p_{i}$, independent of the history. In a conventional Markov chain (with $R=1$) with finite state space $\mathcal{X}$, we can use the transition probability matrix $P$ to represent the Markov chain, where the $(i,j)$-th entry of $P$ is $[P]_{i,j}=P(X_{t}=j\mid X_{t-1}=i)$, i.e., the probability of transitioning from state $i$ to state $j$.

Recall that each client $i$ is associated with a strictly positive availability probability $p_{i}>0,\forall i\in[N]$. At each round $t$, the server samples a size-$B$ subset of clients $S_{t}$, where $|S_{t}|=B$, with probability for each client proportional to $p_{i}$ to join the training system. Note that only clients that have waited for $R$ rounds are available. In other words, set $S_{t}$ is sampled with probability proportional to $\sum_{i\in S_{t}}p_{i}$ 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 0 0 to $M-1$, where $R=M-1$ corresponds to a cyclic participation pattern where subsets of clients participate in training in a fixed order.(^1^11Any $R>M-1$ would resulting in periods with insufficient available clients. We do not consider those cases here.)

Denote $\mathcal{X}$ as the collection of all possible
ordered subsets of $[N]$ with exactly $B$ elements. Then, $|\mathcal{X}|=\sigma(N,B)$ where $\sigma(N,B)=\frac{N!}{(N-B)!}$ represents the total number of $B$-permutations of $[N]$. Considering the stochastic process $\{X_{t}\}_{t=0}^{\infty}$ where $X_{t}\in\mathcal{X}$, the participation pattern in Section 2 can be precisely described by an $R$-order Markov chain defined in Definition 1. Formally,

$$ $P(X_{t}=\mathcal{I}_{0}\mid X_{t-1}=\mathcal{I}_{1},X_{t-2}=\mathcal{I}_{2}, \dots,X_{0}=\mathcal{I}_{t})=P(X_{t}=\mathcal{I}_{0}\mid X_{t-1}=\mathcal{I}_{ 1},\dots,X_{t-R}=\mathcal{I}_{R})$ (2) $$

where each state $\mathcal{I}_{k}\in\mathcal{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. $(1,2,\dots,B)$ and $(2,1,3,\dots,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_{t})$) by noting that $P(i\text{ to be sampled at round }t)=\sum_{i_{2},\dots,i_{B}}P(X_{t}=(i,i_{2},
\dots,i_{B}))$. Here we calculate the probability of client $i$ appearing as the first element in the ordered set $X_{t}$. The probability of $i$ 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 (2) has some nice properties as summarized below.

###### Proposition 1 .

The $R$-th order Markov chain (2) maintains the following properties:

The ordered sequence $(\mathcal{I}_{0},\mathcal{I}_{1},\dots,\mathcal{I}_{R})$ is non-repeated, meaning $\mathcal{I}_{l}\cap\mathcal{I}_{k}=\emptyset,\forall l\neq k$.

For any non-repeated $(\mathcal{I}_{0},\dots,\mathcal{I}_{R})$,

$$ $P(X_{t}=\mathcal{I}_{0}\mid X_{t-1}=\mathcal{I}_{1},\dots,X_{t-R}=\mathcal{I}_ {R})=\frac{p_{\mathcal{I}_{0}}}{\sum_{\mathcal{J}\in S_{\mathcal{I}_{1:R}}^{c} }p_{\mathcal{J}}}=:p_{(\mathcal{I}_{1},\dots,\mathcal{I}_{R})\to\mathcal{I}_{0 }}.$ (3) $$

Otherwise $P(X_{t}=\mathcal{I}_{0}\mid X_{t-1}=\mathcal{I}_{1},\dots,X_{t-R}=\mathcal{I}_
{R})=0$. Since $\mathcal{I}_{k}$ is a set with $B$ unique elements, we define $p_{\mathcal{I}_{k}}:=\sum_{e\in\mathcal{I}_{k}}p_{e},\forall\mathcal{I}_{k}$. $S_{\mathcal{I}_{1:R}}^{c}$ is the collection containing all $B$-permutations of $[N]\setminus\bigcup_{k=1}^{R}\mathcal{I}_{k}$.

For $t\geq R-1$, define $Y_{t}=(X_{t},\dots,X_{t-R+1})\in\mathbb{R}^{R}$. Then $\{Y_{t}\}_{t=R-1}^{\infty}$ is a conventional Markov chain with its cardinality of the state space being $d(M,R)$, where $d(M,R)=\prod_{k=0}^{R-1}\sigma(B(M-k),B)$. Moreover its transition probability is

$$ $P(Y_{t}=(\mathcal{I}_{0},\mathcal{J}_{1},\dots,\mathcal{J}_{R-1})|Y_{t-1}=( \mathcal{I}_{1},\dots,\mathcal{I}_{R}))=\left\{\begin{array}[]{ccc}p_{( \mathcal{I}_{1},\dots,\mathcal{I}_{R})\to\mathcal{I}_{0}}&,&\mathcal{J}_{k}= \mathcal{I}_{k},k\in[R-1]\\ 0&,&\mathrm{otherwise}\end{array}\right.$ (4) $$

for any non-repeated $(\mathcal{I}_{0},\dots,\mathcal{I}_{R})$.

Define vector $u_{(\mathcal{I}_{1},\dots,\mathcal{I}_{R})}\in\mathbb{R}^{d(M,R)}$ with $(\mathcal{I}_{0},\mathcal{I}_{1},\dots,\mathcal{I}_{R-1})$-th entry as $P(Y_{t}=(\mathcal{I}_{0},\mathcal{I}_{1},\dots,\mathcal{I}_{R-1})\mid Y_{t-1}=
(\mathcal{I}_{1},\dots,\mathcal{I}_{R}))$. Then, $u_{(\mathcal{I}_{1},\dots,\mathcal{I}_{R})}\in\mathbb{R}_{+}^{\sigma(B(M-R),B)
}\subset\mathbb{R}^{d(M,R)}$ and $u_{(\mathcal{I}_{1},\dots,\mathcal{I}_{R})}[(\mathcal{I}_{0},\dots,\mathcal{I}
_{R-1})]=p_{\mathcal{I}_{0}}(\sum_{\mathcal{J}\in S_{\mathcal{I}_{1:R}}^{c}}p_
{\mathcal{J}})^{-1}>0,\forall\mathcal{I}_{0}\in S_{\mathcal{I}_{1:R}}^{c}$.

Denote $v_{(\mathcal{J}_{0},\dots,\mathcal{J}_{R-1})}\in\mathbb{R}^{d(M,R)}$ with $(\mathcal{J}_{1},\mathcal{J}_{2},\dots,\mathcal{J}_{R})$-th entry as
$P(Y_{t}=(\mathcal{J}_{0},\dots,\mathcal{J}_{R-1})\mid Y_{t-1}=(\mathcal{J}_{1}
,\mathcal{J}_{2},\dots,\mathcal{J}_{R}))$ Then, $v_{(\mathcal{J}_{1},\dots,\mathcal{J}_{R})}\in\mathbb{R}_{+}^{\sigma(B(M-R),B)}$ and $v_{(\mathcal{J}_{0},\dots,\mathcal{J}_{R-1})}[(\mathcal{J}_{1},\dots,\mathcal{
J}_{R})]=p_{\mathcal{J}_{0}}(\sum_{\mathcal{J}\in S_{\mathcal{J}_{1:R}}^{c}}p_
{\mathcal{J}})^{-1}>0$ for any $\mathcal{J}_{R}\in S_{\mathcal{J}_{0:R-1}}^{c}$.

Properties (1),(2) 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 (2) and the participation pattern in Section 2. Property (3) means that we can augment our state space by taking into consideration of the history with length $R$ to formulate an equivalent Markov chain $\{Y_{t}\}_{t=R}^{\infty}$ 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_{t}\}_{t=R}^{\infty}$. Also since there are only $\sigma(B(M-R),B)\ll 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 that it allows us to look into the probability of each client to be sampled as $t$ goes on. Specifically, given any $R$, denote $P_{R}\in\mathbb{R}^{d(M,R)\times d(M,R)}$ as the transition probability matrix of the Markov chain $\{Y_{t}\}_{t=R}^{\infty}$ where its entry is given by (4). Let $\phi_{R}(t)\in\mathbb{R}^{d(M,R)}$ be the state distribution at round $t$ of the Markov chain $\{Y_{t}\}_{t=R}^{\infty}$ and $\eta_{R}(t)\in\mathbb{R}^{N}$ be the distribution of clients to be sampled at round $t$. We have the following evolution of distributions with respect to $t$:

$$ $\displaystyle\eta_{R}(t)=Q_{R}^{T}\phi_{R}(t),\leavevmode\nobreak\ \leavevmode \nobreak\ \phi_{R}(t+1)$ $\displaystyle=P_{R}^{T}\phi_{R}(t)$ (5) $$

for any initial distribution $\eta_{R}(0)$ and corresponding $\phi_{R}(0)$ such that $\eta_{R}(0)=Q_{R}^{T}\phi_{R}(0)$, where $Q_{R}=Q_{R,1}Q_{R,2}$ and $Q_{R,1}\in\mathbb{R}^{d(M,R)\times\sigma(N,B)}$ is defined by

$$ $[Q_{R,1}]_{(\mathcal{I}_{1},\dots,\mathcal{I}_{R}),\mathcal{J}}=\left\{\begin{ array}[]{ccc}p_{(\mathcal{I}_{1},\dots,\mathcal{I}_{R})\to\mathcal{J}}&,&\{ \mathcal{J},\mathcal{I}_{1},\dots,\mathcal{I}_{R}\}\leavevmode\nobreak\ \text{ non-repeated}\\ 0&,&\mathrm{otherwise}.\end{array}\right.$ $$

and $Q_{R,2}\in\mathbb{R}^{\sigma(N,B)\times N}$ is defined by

$$ $[Q_{R,2}]_{\mathcal{J},j}=\left\{\begin{array}[]{ccc}1&,&\mathcal{J}=(j,*)\\ 0&,&\mathrm{otherwise},\end{array}\right.$ $$

where $\mathcal{J}=(j,*)$ denotes that the first entry of $\mathcal{I}$ is $j$. We are particularly interested in the distribution of $\eta_{R}(t)$ as $t\to\infty$ because it helps us characterize the asymptotic performance of existing FL algorithms. From classical Markov chain literature, we know that if a Markov chain is irreducible and aperiodic (see formal definitions in Appendix B), it has a stationary distribution which is unique and strictly positive.
We denote $\zeta_{R}=\lim_{t\to\infty}\phi_{R}(t)$ as the stationary distribution of Markov chain $P_{R}$ and we have

$$ $\zeta_{R}^{T}=\zeta_{R}^{T}P_{R},\leavevmode\nobreak\ \leavevmode\nobreak\ \pi _{R}^{T}=\zeta_{R}^{T}Q_{R}.$ (6) $$

where $\pi_{R}\in\mathbb{R}^{N}$ is marginal stationary distribution of clients to be sampled, i.e., the $i$-th entry of $\pi_{R}$ is given by $\pi_{R}^{i}=\lim_{t\to\infty}\sum_{i_{2},\dots,i_{B}}P(X_{t}=(i,i_{2},\dots,i_
{B}))$. On the other hand, if the Markov chain is irreducible and peroidic, we let $\zeta_{R}$ be the Perron vector(^2^22we say $v$ is the Perron vector of the transition matrix $P$ if $v^{T}=v^{T}P$, i.e., $v$ is right eigenvector of $P$ corresponding to eigenvalue $1$ and $v^{T}\mathbf{1}=1$.), which is also strictly positive.
We now show our Markov chain is irreducibile and (a)periodic to justify the definitions of $\zeta_{R}$ and $\pi_{R}$ in Lemma 1. The proof is in Appendix C.

###### Lemma 1 .

The Markov chain $\{Y_{t}\}_{t=R}^{\infty}$ with transition matrix $P_{R}$ defined by (4) is irreducible for all $M\geq 1$ and $0\leq R\leq M-1$. Further, when $R\leq 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, if client $1$ and client $2$ are consecutively selected in the first two rounds, in the third round only client $3$ or $4$ can be selected with probabilities of $p_{3}/(p_{3}+p_{4})$ or $p_{4}/(p_{3}+p_{4})$ respectively. Then, the state $(2,1)$ can only transition to $(3,2)$ or $(4,2)$, where the second index is sampled before the first one as is in (2). Similarly, if we are currently at state $(1,4)$, the previous state has to be $(4,3)$ or $(4,2)$. One can easily check that Proposition 1 holds. To see how $\pi$ is calculated, we take the first entry of $\pi_{R}$ as an example:

$$ $\pi_{R}^{1}=\zeta^{(2,3)}p_{(2,3)\to 1}+\zeta^{(2,4)}p_{(2,4)\to 1}+\zeta^{(3, 2)}p_{(3,2)\to 1}+\zeta^{(3,4)}p_{(3,4)\to 1}+\zeta^{(4,2)}p_{(4,2)\to 1}+ \zeta^{(4,3)}p_{(4,3)\to 1}$ $$

by noting that the remaining $p_{(i,j)\to 1}=0$, if $i\leavevmode\nobreak\ \text{or}\leavevmode\nobreak\ j=1$.

The vectors in (6) characterize the final distribution according to which clients will be sampled when the communication round $t$ becomes infinitely large. In other words, each client $i$ is sampled with probability $\pi_{R}^{i}$ given some fixed $R$. Although $\pi_{M-1}$ is the uniform distribution no matter what $p_{i}$’s are (by observing that all clients follow a cyclic participation), we note that $\pi_{R}$ for $R<M-1$ does not necessarily follow the uniform distribution, because $\{p_{1},\dots,p_{N}\}$ 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 (1) no matter how many rounds of training are implemented. We call this phenomenon the asymptotic bias induced by $\pi_{R}$. We will characterize both empirically and theoretically this phenomenon in the next section.

###### Definition 1 .

###### Proposition 1 .

###### Lemma 1 .

## 4 Asymptotic bias under non-uniform correlated participation

In this section, we use the Markov chain model in the previous section to analyze asymptotic bias of existing federated learning algorithms caused by arbitrary $p_{i}$’s when minimum separation $R\leq M-2$. In particular, we consider FedAvg with local gradient descent updates, i.e., at each round, a set $S_{t}$ with $|S_{t}|=B$ clients are sampled and after being selected client $i$ updates its model as

$$ $x_{t,0}^{i}=x_{t},\leavevmode\nobreak\ \leavevmode\nobreak\ x_{t,k+1}^{i}=x_{t ,k}^{i}-\alpha\nabla f_{i}(x_{t,k}^{i}),\leavevmode\nobreak\ k=0,\dots,K-1$ (7) $$

where $x_{t}$ denotes the server’s model at round $t$ and $x_{t,k}^{i}$ is the local model maintained by client $i$ at $k$-th iteration. The server then updates $x_{t+1}=\frac{1}{B}\sum_{i\in S_{t}}x_{t,K}^{i}$. We next show in the following that FedAvg may not converge to the desired optimal solutions of (1). Instead there may exist some error neighborhood, i.e., the asymptotic bias, that is related to $\pi_{R}$, even as $t$ goes to infinity. Before we formally deliver the result, two standard assumptions are needed.

###### Assumption 1 .

There exists $G>0$ such that $\|\nabla f_{i}(x)-\nabla F(x)\|^{2}\leq G^{2},\forall x$ and $\forall i\in[N]$.

###### Assumption 2 .

Each $f_{i}$ is $L$-smooth, i.e., $\|\nabla f_{i}(x)-\nabla f_{i}(y)\|\leq L\|x-y\|,\forall x,y$ and $\forall i\in[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 $\|\nabla F(x)\|\leq D$, $\forall x$ with some $D>0$. Then for any $T>2\tau_{mix}\log\tau_{mix}$ choosing $\alpha=\mathcal{O}(1/(\tau_{mix}K\sqrt{T}))$, FedAvg with local updates (7) generates the trajectory $\{x_{t}\}_{t=1}^{T}$ satisfying

$$ $\mathbb{E}\|\nabla F(\tilde{x}_{T})\|^{2}\leq\tilde{\mathcal{O}}\left(\frac{ \tau_{mix}}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{1}{T}\right)+\mathcal{O} \left(\big{\|}\pi_{R}-\frac{1}{N}\mathbf{1}_{N}\big{\|}_{1}^{2}\right),$ (8) $$

for any $0\leq R\leq M-2$, where $\tilde{x}_{T}$ is drawn uniformly from $x_{0},\dots,x_{T-1}$, $\tilde{\mathcal{O}}(\cdot)$ hides logrithmic factors, and $\tau_{mix}$ denotes the mixing time(^3^33Please refer to Appendix B for the formal definition of the mixing time.)of Markov chain (5). Moreover, the bias term $\mathcal{O}\big{(}\big{\|}\pi_{R}-\frac{1}{N}\mathbf{1}_{N}\big{\|}_{1}^{2}
\big{)}$ shown in (8) is unavoidable.

Theorem 1 implies that without any debiasing technique, FedAvg can only converge to a solution with unavoidable asymptotic bias
which is measured by the distance between $\pi_{R}$ (defined in (6)) and the uniform distribution. Except for $R=M-1$, where $\pi_{M-1}$ is the uniform distribution, for $R\leq M-2$, there is generally some gap between $\pi_{R}$ and $(1/N)\mathbf{1}_{N}$, which shows that FedAvg may fail to perform under correlated client participation. However, if $\pi_{R}$ is not too far away from the uniform distribution, we expect FedAvg to converge to a solution reasonably close to the optimal solution of (1). We next investigate what factors influence the distance from $\pi_{R}$ to the uniform distribution. We find that one factor is the spread among $p_{i}$’s. Stated by the following proposition, if all $p_{i}$’s are equal, no gap between $\pi_{R}$ and $(1/N)\mathbf{1}_{N}$ exists (see Appendix D for the proof).

###### Proposition 2 .

Suppose $p_{1}=p_{2}=\cdots=p_{N}=\frac{1}{N}$. Then for any $0\leq R\leq M-1$, $\pi_{R}=\frac{1}{N}\mathbf{1}_{N}$.

Figure: Figure 1: Distance between $\pi_{R}$ and the uniform distribution as $R$ increases ($N=500,B=1$)
Refer to caption: x1.png

When $p_{i}$’s are not equal to each other, we turn to understand how $R$ affect $\pi_{R}$. In fact, we empirically observe that $\pi_{R}$ approaches the uniform distribution as $R$ increases. This key observation is illustrated in Figure 1. We consider the case where $N=500,B=1$ and assign each client a random $p_{i}>0$. We then calculate $\pi_{R}$ for each $R$ ranging from 0 0 to $N-1$ and measure its distance from the uniform distribution. As shown in the figure, increasing $R$ causes $\pi_{R}$ moving towards 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 probability $p_{i}$’s, which is the case for a small $R$ and many available clients, here the sampling process is mostly determined by the waiting requirement. In the extreme case, when $R=M-1$, at each round, only $B$ clients are available, hence all clients are sampled with equal frequency. Another point suggested by this observation is that we can choose a large minimum separation $R$ in the practical scenario to reduce the asymptotic bias for existing FL algorithms, even with unknown $p_{i}$’s.

The above empirical observation verifies the formal theorem that characterizes the debiasing effect of increasing minimum separation $R$ in Theorem 2. (see Appendix D for the proof).

###### Theorem 2 .

Given a set of $p_{i}$’s, with at least one element $p_{i}\neq\frac{1}{N}$. Without loss of generality, let $p_{1},\dots,p_{B}$ be the $B$ smallest values among all $p_{i}$’s. Define $q_{B}:=\sum_{j=1}^{B}p_{j}$, then $q_{B}<1/M$. There exists a $\bar{\delta}>0$, such that if any size-$B$ batch of clients $\mathcal{B}_{j}$ picking from $[N]\setminus[B]$, $\delta_{j}:=|\sum_{l\in\mathcal{B}_{j}}p_{l}-\frac{1-q_{B}}{M-1}|\leq\bar{\delta}$, then
$\pi_{R}$ converges to a neighborhood of $\frac{1}{N}\mathbf{1}_{N}$ characterized by $\{\pi\mid\|\pi-\frac{1}{N}\mathbf{1}_{N}\|_{1}=\mathcal{O}(N^{-1})\}$ as $R$ ranging from 0 0 to $M-1$. When $R=M-1$, $\pi_{M-1}$ is the uniform distribution supported on $[N]$.

Theorem 2 states that when the availability probabilities $p_{i}$’s of clients are not too far away from each other or when $B$ is relatively large (i.e., $\delta_{j}$’s are small for all $j$), and when the total number of clients $N$ is large, $\pi_{R}$ approaches the uniform distribution as $R$ increases. It is worth noting that practically when the requirements in Theorem 2 are not strictly satisfied, the effect of increasing $R$ on $\pi_{R}$ can be still observed as shown in Figure 1.

###### Assumption 1 .

###### Assumption 2 .

###### Theorem 1 .

###### Proposition 2 .

###### Theorem 2 .

## 5 Debiasing FedAvg and its convergence

As we discuss in the previous section, existing federated learning algorithms like FedAvg cannot guarantee convergence to the correct optimal solution if $R\leq M-2$ and $p_{i}$’s are arbitrary. Although we can reduce the asymptotic bias caused by $\pi_{R}$ by increasing $R$, it may still be problematic under some particular circumstances.
Clients have intermittent and non-uniform availability, and forcing a 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 small and the $p_{i}$’s can be very different from each other, which then suggests by Figure 1 and Theorem 2, $\pi_{R}$ can be far from the uniform distribution, making the asymptotic bias non-negligible. We next design a debiasing process that can be easily integrated into the existing federated learning algorithms to address asymptotic bias. Our proposed algorithm based on FedAvg is given by Algorithm 1.

Figure: Algorithm 1 Debiasing FedAvg for correlated client participation

The main difference between our algorithm and vanilla FedAvg lies in the stage of local updates (Lines 5 and 7). Specifically, we require each client to maintain an estimator of its corresponding component of $\pi_{R}$, 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 $\pi_{R}^{i}$ represents the frequency of client $i$ to be selected when $t$ is large enough (i.e., when the Markov chain (5) becomes steady, meaning $\phi_{R}(\infty)=\zeta_{R}$). If we reweigh the local objective function $f_{i}$ by $\frac{1}{\pi_{R}^{i}}$ (corresponding to $\nu_{t}^{i}=\frac{1}{\pi_{R}^{i}N}$ in (9)), this weighting cancels the asymptotic bias introduced by unbalanced sampling, which drives the trajectory of the server’s models towards the correct solution of (1). If we know $\pi_{R}^{i}$ for every client in prior, the above-mentioned reweighting method provides us with unbiased solutions. Then, $\lambda_{t}^{i}$ serves as a role to iteratively approximate $\pi_{R}^{i}$ round by round, which yields Algorithm 1 (^4^44This is similar to the technique used in [], where a counter is used to capture asynchronous update frequency in distributed setting. While agents may update with different relative frequency, their updates are independent and identically distributed over time unlike the correlated case here.). Also note that Algorithm 1 reduces to FedAvg if fixing $\lambda_{t}^{i}=1/N,\forall i\in[N]$. This shows the advantage of our algorithm: it is computationally cheap in the sense that each client only maintains two additional scalars ($\lambda_{t}^{i}$ and $\nu_{t}^{i}$) and can be easily embedded with existing algorithms by just multiplying the learning rates by $\nu_{t}^{i}$. We note that other federated algorithms suffering from asymptotic bias due to nonuniform sampling could also benefit from our debiasing technique based on simple counting.

However, formally characterizing the convergence of $\nu_{t}^{i}$ to $\frac{1}{\pi_{R}^{i}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 transitions of the Markov chain (6) and its influences on the marginal distribution of clients to be sampled to conclude that $\lambda_{t}^{i}$ is an unbiased estimate of $\pi_{R}^{i}$. Then, we further leverage the fact that the Markov chain is irreducible as stated in Lemma 1 to show that $\lambda_{t}^{i}$ is almost surely strictly positive even $t$ is infinite, concluding the convergence of $\nu_{t}^{i}$ to $\frac{1}{\pi_{R}^{i}N}$, as summarized in Lemma 2 (see Corollary 2 in Appendix G for the proof).

###### Lemma 2 .

Given $\lambda_{0}=\mathbf{0}_{N}$, then $\nu_{t}^{i},\forall i\in[N]$ in Algorithm 1 satisfies

$$ $\mathbb{E}\|\tilde{\nu}_{t}\|_{\infty}^{2}\leq\mathcal{O}\left(\frac{\tau_{mix }}{t}\right)$ $$

for any $t>0$, where $\tilde{\nu}^{i}_{t}=\nu^{i}_{t}-\frac{1}{\pi_{i}N}$ and $\tilde{\nu}_{t}=(\tilde{\nu}_{t}^{1},\dots,\tilde{\nu}_{t}^{N})$.

Based on the above, we can achieve the following convergence result of Algorithm 1 (see Appendix G for the proof).

###### Theorem 3 .

Suppose Assumptions 1 and 2 hold. For any $0\leq R<M-1$ and $T>c^{{\dagger}}\tau_{mix}\log\tau_{mix}$ (with $c^{{\dagger}}$ being some constant), choosing $\alpha=\mathcal{O}(1/(\tau_{mix}K\sqrt{T}))$, the output of Algorithm 1 satisfies

$$ $\mathbb{E}\|\nabla F(\tilde{x}_{T})\|^{2}=\tilde{\mathcal{O}}\left(\frac{\tau_ {mix}}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{1}{T}\right)$ $$

where $\tilde{x}_{T}$ is defined as that in Theorem 1.

Comparing to Theorem 1, no bounded gradient assumption is needed to reach the convergence of our algorithm. Unlike the result in [] where clients are forced to participate in the system cyclically, our bound shown in Theorem 3 does not grow as the number of clients increases. Particularly, for the bounds in [] to be non-vacuous, the total number of communication round $T$ should be proportional to the number of clients, which could be hard to satisfy in practice especially client number is super large. To prove Theorem 3 we critically rely on the fact that the Markov chain (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-1$ is the cyclic case, where the Markov chain follows much nicer structure (e.g. $\pi_{M-1}$ is uniform), one may be able to get a better bound [].

We remark that our convergence result achieves nearly the same order of rate as Markov-sampling SGD literature [, ] (where rates of $\mathcal{O}(\sqrt{\tau_{mix}}/\sqrt{T}+\tau_{mix}/T)$ are obtained). However, their analysis only suits for the first-order Markov chain and no debiasing results are presented, while our results generalize to high-order Markov chain and allow local updates, and further guarantee approaching unbiased solutions. It is worth noting that utilizing variance-reduced techiques may accelerate the convergence rate for Markov-sampling SGD []. 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 a uniform minimum separation $R$ for all clients is placed throughout the paper, we allow each client maintains its own specific $R_{i},\forall i\in[N]$. In this more general case, we can still utilize the same modeling technique as in Section 3 where the order of the Markov chain is chosen to be an upper bound of all $R_{i}$’s (e.g. $\max_{i}R_{i}$). Then Theorems 1 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 1 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 $R_{i}$’s.

###### Lemma 2 .

###### Theorem 3 .

## 6 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 is 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, we only need to associate availability probabilities to each group, where $p_{i}\propto i^{-1.5},i\in[M]$ is a long-tailed distribution.

#### Synthetic dataset.

We test Vanilla FedAvg and Debiasing FedAvg (Algorithm 1) under a synthetic dataset constructed following []: for each client $i$, $A_{i}\in\mathbb{R}^{n_{i}\times d}$ is the feature matrix, where $n_{i}$ is the number of local samples and $d$ is the feature dimension. Every entry of $A_{i}$ is generated by a Gaussian distribution $\mathcal{N}(0,(0.5i)^{-2})$. We then generate $b_{i}\in\mathbb{R}^{n_{i}}$, the labels of client $i$, by first generating a reference point $\theta_{i}\in\mathbb{R}^{d}$, where $\theta_{i}\sim\mathcal{N}(\mu_{i},I_{d})$. And $\mu_{i}$ is drawn from $\mathcal{N}(\alpha,1)$ with $\alpha\sim\mathcal{N}(0,100)$. Then $b_{i}=A_{i}\theta_{i}+\epsilon_{i}$ with $\epsilon_{i}\sim\mathcal{N}(0,0.25I_{n_{i}})$. We set $d=20,n_{i}=100,\forall i\in[N]$. And we define $f_{i}(x)=\frac{1}{n_{i}}\sum_{j=1}^{n_{i}}\log(\frac{1}{2}(\langle A_{i}[j,:],
x\rangle+b_{i}[j])^{2}+1)$ where $A_{i}[j,:]$ represents the $j$-th row of $A_{i}$ and $b_{i}[j]$ is the $j$-th entry of $b_{i}$. The outcomes are shown in Figures 2(a),2(b).

#### 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 $\mathcal{O}(10^{-3})$. In Figure 3(c), we compare Debiasing FedAvg with Vanilla FedAvg and FedVARP[], and Debiasing FedAvg can effectively mitigate the bias effect. Another interesting empirical observation is that increasing $R$ can fasten the speed of both Debiasing and Vanilla FedAvg (as shown by Figures 3(a),3(b)). This is yet not characterized by our theoretical demonstration. Here we conjecture that larger $R$ corresponds to smaller mixing time $\tau_{mix}$ and hence faster rate. We provide more detailed and intuitive discussions in Appendix H.

Figure: (a) FedAvg under different $R$ after convergence (synthetic data)
Refer to caption: x2.png

Figure: (a) Debiasing FedAvg under different $R$ (MNIST)
Refer to caption: x4.png

## 7 Conclusion

In this paper, we consider FL with non-uniform and correlated client participation, where every client must wait as least $R$ rounds (minimum separation) before participating again, and each client has their own availability probability. A high-order Markov chain is introduced to model this practical scenario. Based on this Markov-chain modeling, we are able to study the convergence performances of existing FL algorithms. Due to 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, we propose a debiasing algorithm for FedAvg that guarantee convergence to unbiased solutions given arbitrary non-uniformity and minimum separation $R$.

## Appendix 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 an unbiased estimate as that in the full participation setting and hence allows extension of convergence results for the full-participation setting to the partial-participation setting [, ]. The above-mentioned uniform participation is, however, far from the reality as clients may have their intrinsic sampling probabilities $p_{i}$’s that are non-uniform due to, for example, intermittent availability resulting from practical constraints. Recent works analyzed the convergence behaviors of FL algorithms when such $p_{i}$’s are known as a prior or controllable [, , , ]. However, pointed out by [, ], client participation pattern can highly depend on the underlying system characteristics, which is thus hard to know or control. As characterized by [, ], such unknown and 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, [, , ] introduced reweighting mechanisms combined with dynamically estimating client participation distributions. 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 participation is influenced by others across rounds[, , ]. One interesting time-correlated participation pattern is that clients have to wait for at least $R$ (called minimum separation) rounds between consecutive participation [, ]. In particular, imposing a minimum separation constraint has been empirically shown to benefit privacy preservation in FL applications [, , , ]. Instead, such time-correlated participation has not been fully investigated theoretically. The only work that partially captures the above case is [] where the clients are forced to follow a 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 to their empirical counterparts in practice.

#### Stochastic optimization with Markov-sampling.

Another line of related works is stochastic gradient-based optimization under Markov-sampling. Unlike classical stochastic optimization literature where i.i.d. samples are drawn during the training process [, , , ], many contexts, including TD-learning and reinforcement learning (RL), require to optimize the objective function by utilizing samples generated by a Markov chain [, , , ]. Recently, the work [] provided convergence guarantees for SGD under Markov-sampling when the objectives are convex, strongly convex and non-convex. Then [] further proposed an accelerated method and generalized the analysis to variational inequalities. Both of them limit on the first-order Markov chains. It has been shown by literature that gradient-based methods converge to the optimal solution of the objective induced by the stationary distribution of the underlying Markov chain [, ]. This indicates that the final solution is biased if the stationary distribution is non-uniform and existing literature cannot deal with such bias problem. In contrast, in this paper we allow higher-order Markov chains and our proposed algorithm enables the convergence to an unbiased solution without any information and constraint on the Markov chain and stationary distribution.

## Appendix 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 a finite Markov chain, we can 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.

Note that $[P^{k}]_{i,j}$ is the probability transiting from state $i$ to state $j$ with exactly $k$ steps, based on which we introduce the definition of aperiodic and periodic Markov chains.

###### Definition 3 .

The period of state $i$ is the greatest common divisor (g.c.d.) of the set $\{k\in\mathbb{N}\mid[P^{k}]_{i,i}>0\}$. If every state has period $1$ then the Markov chain is aperiodic, otherwise it is periodic.

In order words, the period of state $i$ can be achieved by calculating the g.c.d. of the number of steps starting from $i$ 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 $\rho\in(0,1)$ and $C>0$ such that

$$ $\max_{x}\|P^{k}(x,\cdot)-\pi\|_{TV}\leq C\rho^{k}$ $$

where $\pi$ is the unique, strictly positive stationary distribution; $\|\cdot\|_{TV}$ 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 $d_{TV}(P^{k},\mathbf{1}\pi^{T})=\max_{x}\|P^{k}(x,\cdot)-\pi\|_{TV}$. Note that $d_{TV}(P^{k},\mathbf{1}\pi^{T})=\frac{1}{2}\|P^{k}-\mathbf{1}\pi^{T}\|_{\infty}$. Then, we define the mixing time of the chain.

###### Definition 4 .

Given any $\epsilon>0$, the mixing time $t_{mix}(\epsilon)$ is defined as $t_{mix}(\epsilon):=\inf\{l\geq 1\mid d_{TV}(P^{l},\mathbf{1}\pi^{T})\leq\epsilon\}$. Conventionally, we denote $\tau_{mix}=t_{mix}(1/4)$.

###### Lemma 5 .

We have the following statements:

$d_{TV}(P^{t+1},\mathbf{1}\pi^{T})\leq d_{TV}(P^{t},\mathbf{1}\pi^{T})$, $\forall t\geq 0$.

For $k\geq 2$, $t_{mix}(2^{-k})\leq(k-1)\tau_{mix}$.

Moreover,

$$ $\sum_{k=0}^{T}d_{TV}(P^{k},\mathbf{1}\pi^{T})\leq c_{0}\tau_{mix},\leavevmode \nobreak\ \leavevmode\nobreak\ \forall T\geq 0$ $$

for some $c_{0}>0$.

###### Proof.

The first two claims are shown in [].
To see the third claim, we note that

$$ $\displaystyle\sum_{k=0}^{T}d_{TV}(P^{k},\mathbf{1}\pi^{T})$ $\displaystyle\leq\sum_{k=0}^{\infty}d_{TV}(P^{k},\mathbf{1}\pi^{T})$ $\displaystyle\leq\sum_{l=0}^{\tau_{mix}}d_{TV}(P^{l},\mathbf{1}\pi^{T})+\sum_{ k=2}^{\infty}\sum_{l=t_{mix}(2^{-k})+1}^{t_{mix}(2^{-(k+1)})}d_{TV}(P^{l}, \mathbf{1}\pi^{T})$ $\displaystyle\leq d_{TV}(P,\mathbf{1}\pi^{T})\tau_{mix}+\sum_{k=2}^{\infty}(t_ {mix}(2^{-(k+1)})-t_{mix}(2^{-k}))2^{-k}$ $\displaystyle\leq d_{TV}(P,\mathbf{1}\pi^{T})\tau_{mix}+\sum_{k=2}^{\infty}k2^ {-k}\tau_{mix}$ $\displaystyle\leq d_{TV}(P,\mathbf{1}\pi^{T})\tau_{mix}+2\tau_{mix}$ $$

which completes the proof with $c_{0}=d_{TV}(P,\mathbf{1}\pi^{T})+2$.
∎

###### Definition 2 .

###### Definition 3 .

###### Lemma 3 .

###### Lemma 4 .

###### Definition 4 .

###### Lemma 5 .

###### Proof.

## Appendix C Proof of Lemma 1

It is obvious that the Markov chain is irreducible in the sense that all ordered sequences $(\mathcal{I}_{1},\dots,\mathcal{I}_{R})$ can be observed due to every client has strictly positive probability to be selected. To see that it is aperiodic for $R\leq M-2$, we only need to show that starting from the state $(\mathcal{I}_{1},\dots,\mathcal{I}_{R})$ where $\mathcal{I}_{k}=((k-1)B+1,\dots,kB),k=1,\dots,R$, both $R+1$ steps and $R+2$ steps can be possibly taken 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. Then, consider the following two constructed sequence.

Let $h_{1}=(\mathcal{I}_{1},\dots,\mathcal{I}_{R},\mathcal{I}_{R+1},\mathcal{I}_{1}
,\dots,\mathcal{I}_{R})$ for state $\mathcal{I}_{R+1}=(RB+1,\dots,(R+1)B)$, where the length of $h_{1}$ is $2R+1$. Denote $h_{1}[k]$ as the entry at the $k$-th position. We construct the sequence $\{Y_{t},Y_{t+1},\dots,Y_{t+R}\}$ as $Y_{t+k-1}=(h_{1}[k\leavevmode\nobreak\ \mathrm{mod}\leavevmode\nobreak\ (2R+1)
],\dots,h_{1}[(k+R-1)\leavevmode\nobreak\ \mathrm{mod}\leavevmode\nobreak\ (2R
+1)]),k=1,\dots,2R+1$, i.e., starting from $(\mathcal{I}_{1},\dots,\mathcal{I}_{R})$ exactly $R+1$ steps are taken to firstly return. Similar to the definition of $h_{1}$, let $h_{2}=(\mathcal{I}_{1},\dots,\mathcal{I}_{R},\mathcal{I}_{R+1},\mathcal{I}_{R+
2},\mathcal{I}_{1},\dots,\mathcal{I}_{R})$ with its length $2R+2$ and state $\mathcal{I}_{R+2}=((R+1)B+1,(R+2)B)$. We then construct the sequence $\{Y_{t},\dots,Y_{t+R+1}\}$ as $Y_{t+k-1}=(h_{2}[k\leavevmode\nobreak\ \mathrm{mod}\leavevmode\nobreak\ (2R+2)
],\dots,h_{2}[(k+R-1)\leavevmode\nobreak\ \mathrm{mod}\leavevmode\nobreak\ (2R
+2)])$, $k=1,\dots,2R+2$, which then suggests exactly $R+2$ steps are required to return back to $(\mathcal{I}_{1},\dots,\mathcal{I}_{R})$. Combining these two cases leads to the Markov chain is aperiodic for any $R\leq M-2$.

## Appendix 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 $p_{1}>0$, $p_{i}=\frac{1-p_{1}}{N-1},\forall i=2,\dots,N$. Then, for any $0<R\leq N-1$ and any $(j_{0},\dots,j_{R-1})$, pick an arbitrary $j_{R}\in\{j_{0},\dots,j_{R-1}\}^{c}$. By denoting $b_{R}=b(P_{R}[\cdot,(j_{0},\dots,j_{R-1})])$, $b_{R+1}=b(P_{R+1}[\cdot,(j_{0},\dots,j_{R})])$ (which are the column sums for each column of $P_{R}$ and $P_{R+1}$, respectively) and letting $S_{R}:=\{j_{0},\dots,j_{R-1}\}$, $S_{R+1}:=\{j_{0},\dots,j_{R}\}$ for notation simplicity. By observing that when $\pi_{R}$ is exactly the uniform distribution, the sum of $P_{R}$ for each column is exactly one, we then tend to prove that the column sum of $P_{R}$ asymptotically approaches one as $R$ increases. We have four cases.

Case I: $j_{0}=\{1\}$. Then, for any $0\leq R\leq N-2$, utilizing last two properties in Proposition 1,

$$ $\displaystyle b_{R+1}-b_{R}$ $\displaystyle=p_{1}\sum_{k\in S_{R+1}^{c}}(p_{1}+\sum_{i\in S_{R+1}^{c}}p_{i}- p_{k})^{-1}-p_{1}\sum_{k\in S_{R}^{c}}(p_{1}+\sum_{i\in S_{R}^{c}}p_{i}-p_{k}) ^{-1}$ $\displaystyle=p_{1}\sum_{k\in S_{R+1}^{c}}\big{(}p_{1}+\frac{1-p_{1}}{N-1}(N-R -2)\big{)}^{-1}-p_{1}\sum_{k\in S_{R}^{c}}\big{(}p_{1}+\frac{1-p_{1}}{N-1}(N-R -1)\big{)}^{-1}$ $\displaystyle=p_{1}(N-R-1)\big{(}p_{1}+\frac{1-p_{1}}{N-1}(N-R-2)\big{)}^{-1}- p_{1}(N-R)\big{(}p_{1}+\frac{1-p_{1}}{N-1}(N-R-1)\big{)}^{-1}$ $$

Let $r=N-R-1$. We simply $b_{R}$ as

$$ $b_{R}=\frac{p_{1}r}{p_{1}+\frac{1-p_{1}}{N-1}(r-1)}=\frac{p_{1}(N-1)}{1-p_{1}} +\frac{p_{1}\big{(}1-\frac{p_{1}(N-1)}{1-p_{1}}\big{)}}{p_{1}+\frac{1-p_{1}}{N -1}(r-1)}$ $$

Then,

$$ $\displaystyle b_{R+1}-b_{R}$ $\displaystyle=p_{1}\big{(}1-\frac{p_{1}(N-1)}{1-p_{1}}\big{)}\left(\frac{1}{p_ {1}+\frac{1-p_{1}}{N-1}(r-1)}-\frac{1}{p_{1}+\frac{1-p_{1}}{N-1}r}\right)$ $\displaystyle=\frac{p_{1}(1-p_{1})}{N-1}\big{(}1-\frac{p_{1}(N-1)}{1-p_{1}} \big{)}\big{(}p_{1}+\frac{1-p_{1}}{N-1}(r-1)\big{)}^{-1}\big{(}p_{1}+\frac{1-p _{1}}{N-1}r\big{)}^{-1}$ $$

which is strictly positive for $p_{1}<1/N$ for all $0\leq R\leq N-2$.

Case II: $\{1\}\in S_{R+1}^{c}$. Then, we obtain $p_{j_{0}}=\frac{1-p_{1}}{N-1}$ and hence

$$ $\displaystyle b_{R}/p_{j_{0}}$ $\displaystyle=(p_{j_{0}}+\frac{1-p_{1}}{N-1}(N-R-1))^{-1}+(N-R-1)(p_{1}+\frac{ 1-p_{1}}{N-1}(N-R-1))^{-1}$ $\displaystyle=\frac{N-1}{(1-p_{1})(r+1)}+r(p_{1}+\frac{1-p_{1}}{N-1}r)^{-1}$ $\displaystyle=\frac{N-1}{(1-p_{1})(r+1)}+\frac{N-1}{1-p_{1}}-\frac{p_{1}(N-1)} {1-p_{1}}\frac{1}{p_{1}+\frac{1-p_{1}}{N-1}r}$ $$

where we let $r=N-R-1$. Then, denoting $\bar{p}=\frac{1-p_{1}}{N-1}$ and $\alpha=p_{1}/\bar{p}$ yields

$$ $\displaystyle(b_{R+1}-b_{R})/p_{j_{0}}$ $\displaystyle=\frac{1}{\bar{p}}\frac{1}{r(r+1)}-\frac{p_{1}}{\bar{p}^{2}(r+ \alpha-1)(r+\alpha)}$ $\displaystyle=\frac{(r+\alpha)(r+\alpha-1)-\alpha r(r+1)}{\bar{p}r(r+1)(r+ \alpha)(r+\alpha-1)}$ $\displaystyle=\frac{(1-\alpha)r^{2}+(\alpha-1)r+\alpha(\alpha-1)}{\bar{p}r(r+1 )(r+\alpha)(r+\alpha-1)}$ $\displaystyle=\frac{(1-\alpha)(r^{2}-r-\alpha)}{\bar{p}r(r+1)(r+\alpha)(r+ \alpha-1)}.$ $$

Note that when $p_{1}<1/N$, $\alpha<1$, which indicates $b_{R+1}-b_{R}>0,\forall 0\leq R\leq N-3$ by observing $r^{2}-r-\alpha\geq 0$. Moreover, note that $b_{R}>1,\forall R\leq N-2$ in this case by

$$ $b_{R}=\frac{1}{r+1}+1-\frac{\alpha}{r+\alpha}=\frac{(1-\alpha)r}{(r+1)(r+ \alpha)}+1>1$ $$

for $\alpha<1$. And a straightforward calculation gives $b_{N-2}<\frac{3}{2}$, which then indicates $|b_{R}-1|<\frac{1}{2},\forall R\leq N-1$.

Case III: $\{1\}\in S_{R}^{c}$ and $\{1\}\notin S_{R+1}^{c}$. In this case, $p_{j_{0}}=\frac{1-p_{1}}{N-1}=\bar{p}$. Then, a simple calculation gives

$$ $(b_{R+1}-b_{R})/p_{j_{0}}=\frac{1}{\bar{p}}\frac{(\alpha-1)r}{(r+1)(r+\alpha)}<0$ $$

when $p_{1}<1/N$.

Case IV: $\{1\}\notin S_{R}^{c}$. Then, all the clients are available in both $S_{R}^{c}$ and $S_{R+1}^{c}$ have availability probability $\bar{p}$. Then, it is obvious that $b_{R}=1,\forall 0\leq R\leq N-1$.

For Cases I, III and IV, we conclude that when $p_{1}<1/N$ and $p_{i}=\frac{1-p_{1}}{N-1},i=2,\dots,N$, $|b_{R+1}-1|<|b_{R}-1|,\forall 0\leq R\leq N-2$ by further noting that $b_{N-1}=1$. By Case II, we then have all $|b_{R}-1|$ converges to $[0,0.5]$ as $R$ increases. Observe $b_{N-1}=1$ corresponds to the case that $\zeta_{N-1}$ is exactly the uniform distribution and so is $\pi_{N-1}$. This indicates that $\pi_{R}$ converges to some neighborhood of the uniform distribution $\frac{1}{N}\mathbf{1}_{N}$. In order to characterize this neighborhood, we turn to carefully analyze Case II, i.e., $|b_{R}-1|<0.5$. Noting that Case II corresponds to at most $1-R/N$ portion of columns in $P_{R}$ and so does $\pi_{R}$, therefore the neighborhood is characterized by $\{\pi\mid\|\pi-\frac{1}{N}\mathbf{1}_{N}\|_{1}=\mathcal{O}(1/N)\}$.

Next, in order to prove the statement, we perturb each $p_{i}=\frac{1-p_{1}}{N-1},i=2,\dots,N$ by some scalar $\epsilon_{i}$ such that $\sum_{i=2}^{N}\epsilon_{i}=0$. Note that $b_{R+1}-b_{R}$ is continuous in $(\epsilon_{2},\dots,\epsilon_{N})$ and so is $\pi_{R}$, which then implies that there exists some positive $\Delta>0$ such that $b_{R+1}-b_{R}$ preserves the original properties as before the perturbation is added for all $|\epsilon_{i}|\leq\Delta$. Therefore, we achieve the statement that $\pi_{R}$ converges to the neighborhood $\{\pi\mid\|\pi-\frac{1}{N}\mathbf{1}_{N}\|_{1}=\mathcal{O}(1/N)\}$ when $B=1$. Obtaining the statement for $B>1$ follows the same technique by noting that we can always calculate the equivalent $\tilde{p}_{i}$ for each batch with size $B$. Specifically, given a batch of clients, say $\mathcal{B}_{i}$, then $\tilde{p}_{i}=\sum_{j\in\mathcal{B}_{i}}p_{j}/C$ with suitable normalization constant $C$ and we can then obtain the convergence of $\pi_{R}$ to a neighborhood of the uniform distribution by similar development.

### D.2 Proof of Proposition 2

The proof of Proposition 2 is straightforward by observing that $b_{R}=1,\forall R$ when $p_{i}=1/N,\forall i\in[N]$. Then $\mathbf{1}^{T}P_{R}=\mathbf{1}^{T},\forall R$ which indicates $\pi_{R}$ is always the uniform distribution.

## Appendix E Intermediate Lemmas

In this section, we present some useful intermediate results under the following generalized setting: we consider a general global objective function defined as $F_{w}(x):=\sum_{i=1}^{N}w_{i}f_{i}(x)$ where $\sum_{i=1}^{N}w_{i}=1$ and $w_{i}\geq 0,\forall i\in[N]$. And we consider the following local update

$$ $x_{t,k+1}^{i}=x_{t,k}^{i}-\alpha q_{t}^{i}\nabla f_{i}(x_{t,k}^{i})$ (10) $$

where $q_{t}^{i}=\frac{w_{i}}{y_{t}^{i}}$ for some positive sequence $y_{t}^{i}$. Note that the above update (10) is a generalized version of Algorithm 1.
Then we have the following useful lemmas when forcing the update (10).

###### Lemma 6 .

Under Assumption 1, we have for any $x$

$$ $\displaystyle\|\nabla F_{w}(x)-\nabla F(x)\|$ $\displaystyle\leq G$ $\displaystyle\|\nabla f_{i}(x)-\nabla F_{w}(x)\|$ $\displaystyle\leq 2G,\leavevmode\nobreak\ \forall i\in[N].$ $$

###### Proof.

Note that Assumption 1 implies

$$ $\displaystyle\|\nabla F_{w}(x)-\nabla F(x)\|$ $\displaystyle=\|\sum_{i=1}^{N}w_{i}(\nabla f_{i}(x)-\nabla F(x))\|$ $\displaystyle\leq\sum_{i=1}^{N}w_{i}\|\nabla f_{i}(x)-\nabla F(x)\|$ $\displaystyle\leq G\sum_{i=1}^{N}w_{i}=G.$ $$

Then, for any $i\in[N]$

$$ $\|\nabla f_{i}(x)-\nabla F_{w}(x)\|\leq\|\nabla f_{i}(x)-\nabla F(x)\|+\| \nabla F_{w}(x)-\nabla F(x)\|\leq 2G.$ $$

∎

###### Lemma 7 .

Given any $t$, we have $\|x^{i}_{t,k}-x_{t}\|^{2}\leq\gamma^{2}L^{-2}\|\nabla F_{w}(x_{t})\|^{2}+4
\gamma^{2}L^{-2}G^{2}$, $\forall k=0,\dots,K$, when $\alpha\leq\min\left\{\frac{\gamma}{8KL},\frac{\gamma}{8KLq_{i}^{t}}\right\}$ and $\gamma\leq 1/3$.

###### Proof.

During the $t$-th communication round, $S_{t}$ and $q_{t}^{i}$ are fixed. Then, for any $\beta>0$ and $\alpha\leq\min\{\frac{\gamma}{\beta L},\frac{\gamma}{\beta Lq_{t}^{i}}\}$, using Lemma 6 gives

$$ $\displaystyle\|x^{i}_{k+1}-x_{t}\|^{2}$ $\displaystyle\leq(1+\beta^{-1})\|x^{i}_{k}-x_{t}\|^{2}+(1+\beta)(\alpha)^{2}(q _{t}^{i})^{2}\|\nabla f_{i}(x^{i}_{k})\|^{2}$ $\displaystyle\leq(1+\beta^{-1})\|x^{i}_{k}-x_{t}\|^{2}+(1+\beta)3(\alpha)^{2}( q_{t}^{i})^{2}\big{(}\|\nabla f_{i}(x^{i}_{k})-\nabla f_{i}(x_{t})\|^{2}$ $\displaystyle+\|\nabla f_{i}(x_{t})-\nabla F_{w}(x_{t})\|^{2}+\|\nabla F_{w}(x _{t})\|^{2}\big{)}$ $\displaystyle\leq(1+\beta^{-1})\|x^{i}_{k}-x_{t}\|^{2}+(1+\beta)3(\alpha)^{2}( q_{t}^{s_{t}})^{2}\big{(}L^{2}\|x^{i}_{k}-x_{t}\|^{2}+4G^{2}+\|\nabla F_{w}(x_ {t})\|^{2}\big{)}$ $\displaystyle\leq(1+\beta^{-1})\|x_{k}^{i}-x_{t}\|^{2}+\frac{3(1+\beta)\gamma^ {2}}{\beta^{2}L^{2}}\big{(}L^{2}\|x^{i}_{k}-x_{t}\|^{2}+4G^{2}+\|\nabla F_{w}( x_{t})\|^{2}\big{)}$ $\displaystyle=(1+(1+3\gamma^{2})\beta^{-1}+3\gamma^{2}\beta^{-2})\|x_{k}^{i}-x _{t}\|^{2}+\frac{3(1+\beta)\gamma^{2}}{\beta^{2}L^{2}}\big{(}4G^{2}+\|\nabla F _{w}(x_{t})\|^{2}\big{)}$ $\displaystyle\leq\exp{\left(\frac{1+6\gamma^{2}}{\beta}\right)}\|x_{k}^{i}-x_{ t}\|^{2}+\frac{3(1+\beta)\gamma^{2}}{\beta^{2}L^{2}}\big{(}4G^{2}+\|\nabla F_{ w}(x_{t})\|^{2}\big{)}$ $$

for any $\beta\geq 1$. Unrolling the above gives for any $k=0,\dots,K-1$

$$ $\|x_{k}^{i}-x_{t}\|^{2}\leq\sum_{k=0}^{K-1}\exp{\left(\frac{1+6\gamma^{2}}{ \beta}k\right)}\frac{3(1+\beta)\gamma^{2}}{\beta^{2}L^{2}}\big{(}G^{2}+\| \nabla F_{w}(x_{t})\|^{2}\big{)}$ $$

which further indicates by choosing $\gamma\leq 1/3$

$$ $\displaystyle\|x_{k}^{i}-x_{t}\|^{2}$ $\displaystyle\leq\sum_{k=0}^{K-1}e^{2k\beta^{-1}}\frac{3(1+\beta)\gamma^{2}}{ \beta^{2}L^{2}}\big{(}4G^{2}+\|\nabla F_{w}(x_{t})\|^{2}\big{)}$ $\displaystyle=\frac{1-e^{2K/\beta}}{1-e^{2/\beta}}\cdot\frac{3(1+\beta)\gamma^ {2}}{\beta^{2}L^{2}}\big{(}4G^{2}+\|\nabla F_{w}(x_{t})\|^{2}\big{)}$ $\displaystyle\leq\frac{(e^{2K/\beta}-1)3\gamma^{2}}{L^{2}}\big{(}4G^{2}+\| \nabla F_{w}(x_{t})\|^{2}\big{)}$ $\displaystyle\leq\frac{\gamma^{2}}{L^{2}}\big{(}4G^{2}+\|\nabla F_{w}(x_{t})\| ^{2}\big{)}$ $$

when choosing $\beta=8K$.

∎

###### Lemma 8 .

For any $t\geq\tau$, we have $\|x_{t}-x_{t-\tau}\|^{2}\leq 4\gamma^{2}L^{-2}\tau^{2}G^{2}+\gamma^{2}L^{-2}
\tau\sum_{l=t-\tau}^{t-1}\|\nabla F_{w}(x_{l})\|^{2}$ when $\alpha\leq\min\{\frac{\gamma}{8KLq},\frac{\gamma}{8KLq_{t}^{i}}\}$ and $\gamma\leq 1/3$.

###### Proof.

Note that

$$ $\displaystyle\|x_{t+1}-x_{t}\|^{2}$ $\displaystyle=\|\frac{1}{|S_{t}|}\sum_{i\in S_{t}}x^{i}_{t,K}-x_{t}\|^{2}$ $\displaystyle\leq\frac{1}{|S_{t}|}\sum_{i\in S_{t}}\|x^{i}_{t,K}-x_{t}\|^{2}$ $\displaystyle\leq\frac{\gamma^{2}}{L^{2}}(4G^{2}+\|\nabla F_{w}(x_{t})\|^{2}).$ $$

Then,

$$ $\displaystyle\|x_{t}-x_{t-\tau}\|^{2}$ $\displaystyle=\|\sum_{l=t-\tau}^{t-1}x_{l+1}-x_{l}\|^{2}$ $\displaystyle\leq\tau\sum_{l=t-\tau}^{t-1}\|x_{l+1}-x_{l}\|^{2}$ $\displaystyle\leq\frac{4\gamma^{2}}{L^{2}}\tau^{2}G^{2}+\frac{\gamma^{2}}{L^{2 }}\tau\sum_{l=t-\tau}^{t-1}\|\nabla F_{w}(x_{l})\|^{2}.$ $$

∎

###### Lemma 9 .

For any $l\in[t-\tau,t]$ with $t\geq\tau\geq 1$ and $\alpha\leq\min\{\frac{\gamma}{8KLq},\frac{\gamma}{8KLq_{t}^{i}}\}$ with $\gamma\leq\min\{\frac{1}{2\eta\tau},\frac{1}{3}\}$ we have

$$ $\max_{t-\tau\leq l\leq t}\mathbb{E}\|\nabla F_{w}(x_{l})\|^{2}\leq 4\mathbb{E} \|\nabla F_{w}(x_{t-\tau})\|^{2}+16\tau^{2}\gamma^{2}G^{2}.$ $$

###### Proof.

For any $t-\tau\leq l\leq t$, we have

$$ $\displaystyle\mathbb{E}\|\nabla F_{w}(x_{l})\|^{2}$ $\displaystyle\leq 2\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}+2\mathbb{E}\| \nabla F_{w}(x_{l})-\nabla F_{w}(x_{t-\tau})\|^{2}$ $\displaystyle\leq 2\tau\gamma^{2}\sum_{l=t-\tau}^{t-1}\mathbb{E}\|\nabla F_{w} (x_{l})\|^{2}+8\tau^{2}\gamma^{2}G^{2}+2\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\| ^{2}$ $\displaystyle\leq 2\tau^{2}\gamma^{2}\max_{t-\tau\leq l\leq t}\mathbb{E}\| \nabla F_{w}(x_{l})\|^{2}+8\tau^{2}\gamma^{2}G^{2}+2\mathbb{E}\|\nabla F_{w}(x _{t-\tau})\|^{2}$ $\displaystyle\leq\frac{1}{2}\max_{t-\tau\leq l\leq t}\mathbb{E}\|\nabla F_{w}( x_{l})\|^{2}+8\tau^{2}\gamma^{2}G^{2}+2\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^ {2}$ $$

where the second inequality follows Lemma 8 and we use $\gamma\eta\leq 1/(2\tau)$ in the last inequality. Finally, taking the maximum over $l$ on the left-hand side completes the proof.
∎

###### Lemma 10 .

Define $F_{w}:=\sum_{i=1}^{N}w_{i}f_{i}$ for $\sum_{i=1}^{N}w_{i}=1,w_{i}\geq 0$. Suppose Assumptions 1,2 hold. Considering any sequence $y_{t}^{i}$ that satisfies $\sum_{i=1}^{N}y_{t}^{i}=1,y_{t}^{i}\geq a^{-1}>0,\forall i\in[N],t\geq 0$ and letting $q_{t}^{i}=\frac{w_{i}}{y_{t}^{i}},\forall i\in[N]$, then, given $\tau\geq\tau_{mix}\log(1/\delta)$ with $0<\delta<1$, for $\alpha\leq\frac{\gamma}{8aKL\max_{i}\{w_{i}\}}$ with $\gamma\leq\min\{\frac{1}{384\eta\tau L},\frac{L}{384\eta\tau},\frac{1}{3}\}$, we have $\forall T>\tau$,

$$ $\displaystyle\frac{1}{T-\tau}\sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F_{w}(x_{t- \tau})\|^{2}$ $\displaystyle\leq\frac{32\bar{a}L\Delta_{\tau}}{\eta\gamma(T-\tau)}+\frac{8}{T -\tau}\sum_{t=\tau}^{T-1}\mathbb{E}\left[\|\tilde{q}_{t}\|_{\infty}^{2}\| \nabla F_{w}(x_{t-\tau})\|^{2}\right]+\frac{32G^{2}}{T-\tau}\sum_{t=\tau}^{T-1 }\mathbb{E}\|\tilde{q}_{t}\|_{\infty}^{2}$ $\displaystyle\quad+32\bar{a}LG^{2}\left(3\gamma+6\eta\gamma\tau^{2}+\frac{2 \eta\gamma}{L}+\frac{3\eta\gamma}{16L^{2}}+\frac{\gamma^{2}}{16aL}\right)+8c_{ 1}^{2}\delta^{2}G^{2}.$ $$

where $\bar{a}=a\max_{i}\{w_{i}\}$, $\tilde{q_{t}}=(\tilde{q}_{t}^{1},\dots,\tilde{q}_{t}^{N})$ with $\tilde{q}_{t}^{i}=q_{t}^{i}-\frac{w_{i}}{\pi_{i}}$, and $c_{1}$ is some constant. Moreover,

$$ $\Delta_{\tau}:=\mathbb{E}[F_{w}(x_{\tau})-\min_{x}F_{w}(x)]\leq\frac{\eta \gamma\tau}{2\bar{a}L}G^{2}+\mathbb{E}[F_{w}(x_{0})-F_{w}^{*}].$ $$

###### Proof.

For notation simplicity, we drop subscript $t$ for $x^{i}_{t,k}$. Define $q_{t}^{i}=\frac{w_{i}}{y_{t}^{i}}$. Note that

$$ $\displaystyle x^{i}_{K}$ $\displaystyle=x_{t}-\sum_{k=0}^{K-1}\alpha q_{t}^{i}\nabla f_{i}(x^{i}_{k})$ $\displaystyle x_{t+1}$ $\displaystyle=x_{t}-\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{ i}\nabla f_{i}(x^{i}_{k})$ $$

where $S_{t}$ denotes the subset of clients drawn in the $t$-th round.
Due to the smoothness of every $f_{i}$, we have

$$ $\mathbb{E}[F_{w}(x_{t+1})-F_{w}(x_{t})]\leq\mathbb{E}\langle\nabla F_{w}(x_{t} ),x_{t+1}-x_{t}\rangle+\frac{L}{2}\mathbb{E}\|x_{t+1}-x_{t}\|^{2}.$ $$

Considering $t\geq\tau$ for any $\tau\geq 0$,

$$ $\displaystyle\mathbb{E}\langle\nabla F_{w}(x_{t}),x_{t+1}-x_{t}\rangle$ $\displaystyle=-\mathbb{E}\langle\nabla F_{w}(x_{t}),\frac{1}{B}\sum_{i\in S_{t }}\sum_{k=0}^{K-1}\alpha q_{t}^{i}\nabla f_{i}(x^{i}_{k})\rangle$ $\displaystyle=\underbrace{\mathbb{E}\langle\nabla F_{w}(x_{t-\tau})-\nabla F_{ w}(x_{t}),\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{i}\nabla f _{i}(x^{i}_{k})\rangle}_{e_{1}}$ $\displaystyle\quad+\underbrace{\mathbb{E}\langle-\nabla F_{w}(x_{t-\tau}), \frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{i}\nabla f_{i}(x_{t- \tau})\rangle}_{e_{2}}$ $\displaystyle\quad+\underbrace{\mathbb{E}\langle-\nabla F_{w}(x_{t-\tau}), \frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{i}(\nabla f_{i}(x^{i }_{k})-\nabla f_{i}(x_{t}))\rangle}_{e_{3}}$ $\displaystyle\quad+\underbrace{\mathbb{E}\langle-\nabla F_{w}(x_{t-\tau}), \frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{i}(\nabla f_{i}(x_{t })-\nabla f_{i}(x_{t-\tau}))\rangle}_{e_{4}}.$ $$

We first note that according to the conditions on $y_{t}^{i}$, $w_{i}\leq q_{t}^{i}\leq aw_{i}$ with some positive constant $a<\infty$ for every $i\in[N]$ and $\forall t\geq 0$.
Then by choosing $\alpha\leq\frac{\gamma}{8aKLw_{m}}\leq\min\{\frac{\gamma}{8KL},\frac{\gamma}{8
KL\max_{i}\{q_{t}^{i}\}}\}$ with $\gamma\leq 1/3$ and $w_{m}=\max_{i}w_{i}$.

$$ $\displaystyle e_{1}$ $\displaystyle\leq\frac{1}{2}\mathbb{E}\|\nabla F_{w}(x_{t})-\nabla F(x_{t-\tau })\|^{2}+\frac{1}{2}\mathbb{E}\left\|\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K -1}\alpha q_{t}^{i}\nabla f_{i}(x^{i}_{k})\right\|^{2}$ $\displaystyle\leq\frac{L^{2}}{2}\mathbb{E}\|x_{t}-x_{t-\tau}\|^{2}+\mathbb{E} \left\|\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{i}(\nabla f_{ i}(x^{i}_{k})-\nabla f_{i}(x_{t}))\right\|^{2}+\mathbb{E}\left\|\frac{1}{B} \sum_{i\in S_{t}}\sum_{k=0}^{K-1}\alpha q_{t}^{i}\nabla f_{i}(x_{t})\right\|^{2}$ $\displaystyle\leq\frac{L^{2}}{2}\mathbb{E}\|x_{t}-x_{t-\tau}\|^{2}+K\mathbb{E} \left[\frac{}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}(\alpha)^{2}L^{2}(q_{t}^{i})^ {2}\|x^{i}_{k}-x_{t}\|^{2}\right]+\mathbb{E}\|\frac{1}{B}\sum_{i\in S_{t}}\sum _{k=0}^{K-1}\alpha q_{t}^{i}\nabla f_{i}(x_{t})\|^{2}$ $\displaystyle\leq\frac{\tau\gamma^{2}}{2}\sum_{l=t-\tau}^{t-1}\mathbb{E}\| \nabla F_{w}(x_{l})\|^{2}+2\tau^{2}\gamma^{2}G^{2}+\frac{\gamma^{2}}{64L^{2}} \mathbb{E}\|\nabla F_{w}(x_{t})\|^{2}+\frac{\gamma^{2}G^{2}}{16L^{2}}+\frac{ \gamma^{2}}{64L^{2}}\mathbb{E}\|\frac{1}{B}\sum_{i\in S_{t}}\nabla f_{i}(x_{t} )\|^{2}$ $\displaystyle\leq\frac{\tau\gamma^{2}}{2}\sum_{l=t-\tau}^{t-1}\mathbb{E}\| \nabla F_{w}(x_{l})\|^{2}+\left(2\tau^{2}+\frac{1}{16L^{2}}+\frac{1}{8BL^{2}} \right)\gamma^{2}G^{2}+\frac{3\gamma^{2}}{64L^{2}}\mathbb{E}\|\nabla F(x_{t}) \|^{2}$ $$

where we use Lemmas 7 and 8 in the fourth inequality; we use the fact $\mathbb{E}\|\frac{1}{B}\sum_{i\in S_{t}}\nabla f_{i}(x_{t})\|^{2}\leq 2\mathbb
{E}\|\nabla F_{w}(x_{t})\|^{2}+8G^{2}/B$ in the last inequality. Next
we turn to bound $e_{2}$. Note that

$$ $\displaystyle e_{2}$ $\displaystyle=-\alpha K\mathbb{E}\left[\mathbb{E}\big{(}\langle\nabla F_{w}(x_ {t-\tau}),\frac{1}{B}\sum_{i\in S_{t}}q_{t}^{i}\nabla f_{i}(x_{t-\tau})\rangle \mid\mathcal{F}_{t-\tau}\big{)}\right]$ $\displaystyle=\frac{\alpha K}{2}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})-\mathbb{E }(\frac{1}{B}\sum_{i\in S_{t}}q_{t}^{i}\nabla f_{i}(x_{t-\tau})\mid\mathcal{F} _{t-\tau})\|^{2}-\frac{\alpha\eta K}{2}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^ {2}$ $\displaystyle\quad-\frac{\alpha K}{2}\mathbb{E}\|\mathbb{E}(\frac{1}{B}\sum_{i \in S_{t}}q_{t}^{i}\nabla f_{i}(x_{t-\tau})\mid\mathcal{F}_{t-\tau})\|^{2}$ $\displaystyle\leq\frac{\alpha\eta K}{2}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})- \mathbb{E}(\frac{1}{B}\sum_{i\in S_{t}}q_{t}^{i}\nabla f_{i}(x_{t-\tau})\mid \mathcal{F}_{t-\tau})\|^{2}-\frac{\alpha K}{2}\mathbb{E}\|\nabla F_{w}(x_{t- \tau})\|^{2}$ $\displaystyle\leq\alpha\eta K\mathbb{E}\|\nabla F_{w}(x_{t-\tau})-\mathbb{E}( \frac{1}{B}\sum_{i\in S_{t}}q_{*}^{i}\nabla f_{i}(x_{t-\tau})\mid\mathcal{F}_{ t-\tau})\|^{2}+\alpha K\mathbb{E}\|\frac{1}{B}\sum_{i\in S_{t}}(q_{t}^{i}-q_{* }^{i})\nabla f_{i}(x_{t-\tau})\|^{2}$ $\displaystyle\quad-\frac{\alpha K}{2}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}$ $$

where $q_{*}^{i}=\frac{w_{i}}{\pi_{i}}$ and $\mathcal{F}_{t-\tau}$ is the filtration up to $t-\tau$. Next, we provide the bound for $\mathbb{E}\|\nabla F_{w}(x_{t-\tau})-\mathbb{E}(\frac{1}{B}\sum_{i\in S_{t}}q_
{*}^{i}\nabla f_{i}(x_{t-\tau})\mid\mathcal{F}_{t-\tau})\|^{2}$. Since we are focusing on the case when $R$ is given, without confusion, we drop $R$ in the following.

Denoting $\psi_{S}:=\lim_{t\to\infty}P(S_{t}=S)$, we have

$$ $\pi^{i}=\frac{\sum_{\hat{S}_{i}}\psi_{\hat{S}_{i}}}{\sum_{i=1}^{N}\sum_{\hat{S }_{i}}\psi_{\hat{S}_{i}}}=\frac{\sum_{\hat{S}_{i}}\psi_{\hat{S}_{i}}}{B}$ $$

where $\hat{S}_{i}$ denotes any set with size $B$ containing $i$. Then, for any vectors $\{v_{i}\}_{i=1}^{N}$, we have

$$ $\sum_{S\in\mathcal{S}}\sum_{i\in S}\frac{\psi_{S}}{\pi^{i}}v_{i}=\sum_{i=1}^{N }\sum_{\hat{S}_{i}}\frac{\psi_{\hat{S}_{i}}}{\pi^{i}}v_{i}=B\sum_{i=1}^{N}v_{i}.$ $$

where $\mathcal{S}$ is the collection of all sets with size $B$.
Thus, by letting $v_{i}=w_{i}\nabla f_{i}(x_{t-\tau})$ in the above, we obtain

$$ $\displaystyle\mathbb{E}\|\nabla F_{w}(x_{t-\tau})-\mathbb{E}(\frac{1}{B}\sum_{ i\in S_{t}}q_{*}^{i}\nabla f_{i}(x_{t-\tau})|\mathcal{F}_{t-\tau})\|^{2}$ $\displaystyle=\mathbb{E}\|\nabla F_{w}(x_{t-\tau})-\frac{1}{B}\sum_{S\in \mathcal{S}}\sum_{i\in S}P(S_{t}=S|\mathcal{F}_{t-\tau})q_{*}^{i}\nabla f_{i}( x_{t-\tau})\|^{2}$ $\displaystyle=\mathbb{E}\left\|\frac{1}{B}\sum_{S\in\mathcal{S}}\sum_{i\in S} \left(P(S_{t}=S|\mathcal{F}_{t-\tau})-\psi_{S}\right)q_{*}^{i}\nabla f_{i}(x_{ t-\tau})\right\|^{2}$ $$

by noting $q_{*}^{i}=w_{i}/\pi^{i}$. Moreover, $P(S_{t}=\cdot)$ can be uniquely induced by $\phi_{R}(t)$ defined by (6) under proper linear transformations, which also indicates that $P(S_{t}=\cdot\mid\mathcal{F}_{t-\tau})=P(S_{t}=\cdot\mid S_{t-\tau})$. Thus, Lemma 4 implies $|P(S_{t}=S\mid\mathcal{F}_{t-\tau})-\psi_{S}|\leq c_{1}\delta\pi_{min}/\sqrt{C
_{N}^{B}}$ for some $c_{1}>0$, $\forall S$ when $\tau\geq\tau_{mix}\log(1/\delta)$ with $C_{N}^{B}=\left(\begin{array}[]{c}N\\
B\end{array}\right)$.
Then,

$$ $\displaystyle\mathbb{E}\left\|\nabla F_{w}(x_{t-\tau})-\mathbb{E}(\frac{1}{B} \sum_{i\in S_{t}}q_{*}^{i}\nabla f_{i}(x_{t-\tau})|\mathcal{F}_{t-\tau})\right \|^{2}$ $\displaystyle=\mathbb{E}\left\|\frac{1}{B}\sum_{S\in\mathcal{S}}\sum_{i\in S} \left(P(S_{t}=S|\mathcal{F}_{t-\tau})-\psi_{S}\right)q_{*}^{i}\nabla f_{i}(x_{ t-\tau})\right\|^{2}$ $\displaystyle\leq\frac{1}{B}\mathbb{E}\left[\sum_{i\in S}\left\|\sum_{S\in \mathcal{S}}(P(S_{t}=S|\mathcal{F}_{t-\tau})-\phi_{S})q_{*}^{i}\nabla f_{i}(x_ {t-\tau})\right\|^{2}\right]$ $\displaystyle\leq c_{1}^{2}\pi_{min}^{2}\delta^{2}\mathbb{E}\left[\frac{1}{B} \sum_{i\in S}\left\|q_{*}^{i}\nabla f_{i}(x_{t-\tau})\right\|^{2}\right]$ $\displaystyle\leq c_{1}^{2}\delta^{2}(\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{ 2}+4G^{2})$ $$

where we use the fact that

$$ $\displaystyle\|\nabla f_{i}(x_{t-\tau})\|^{2}$ $\displaystyle\leq 2\|\nabla F_{w}(x_{t-\tau})\|^{2}+8G^{2}.$ $$

Utilizing the following

$$ $\displaystyle\mathbb{E}\|\frac{1}{B}\sum_{i\in S_{t}}(q_{t}^{i}-q_{*}^{i}) \nabla f_{i}(x_{t-\tau})\|^{2}$ $\displaystyle=\mathbb{E}\|\frac{1}{B}\sum_{i\in S_{t}}\tilde{q}_{t}^{i}(\nabla f _{i}(x_{t-\tau})-\nabla F(x_{t-\tau})+\nabla F(x_{t-\tau}))\|^{2}$ $\displaystyle\leq 8G^{2}\mathbb{E}\|\tilde{q}_{t}\|_{\infty}^{2}+2\mathbb{E} \left[\|\tilde{q}_{t}\|_{\infty}^{2}\|\nabla F(x_{t-\tau})\|^{2}\right]$ $$

where we denote $\tilde{q}_{t}^{i}=q_{t}^{i}-q_{*}^{i}$.
Then we bound $e_{2}$ as

$$ $\displaystyle e_{2}$ $\displaystyle\leq\frac{\alpha K}{2}(2c_{1}^{2}\delta^{2}-1)\mathbb{E}\|\nabla F (x_{t-\tau})\|^{2}+2\alpha KG^{2}(\delta^{2}+4\mathbb{E}\|\tilde{q}_{t}\|_{ \infty}^{2})+2\alpha K\mathbb{E}\left[\|\tilde{q}_{t}\|_{\infty}^{2}\|\nabla F (x_{t-\tau})\|^{2}\right].$ $$

In order to bound $e_{3}$, note that according to Lemma 7 for $\alpha\leq\frac{\gamma}{8KLa}\leq\frac{\gamma}{8KLq_{t}^{i}}$

$$ $\displaystyle e_{3}$ $\displaystyle\leq\mathbb{E}\left[\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1} \alpha q_{t}^{i}\|\nabla F(x_{t-\tau})\|\left\|\nabla f_{i}(x_{k}^{i})-\nabla f _{i}(x_{t})\right\|\right]$ $\displaystyle\leq\mathbb{E}\left[\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1} \left(\frac{(\alpha q_{t}^{i})^{2}K}{2}\|\nabla F_{w}(x_{t-\tau})\|^{2}+\frac{ L^{2}}{2K}\|x_{k}^{i}-x_{t}\|^{2}\right)\right]$ $\displaystyle\leq\mathbb{E}\left[\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1} \left(\frac{\gamma^{2}}{128L^{2}K}\|\nabla F_{w}(x_{t-\tau})\|^{2}+\frac{ \gamma^{2}}{2K}(\|\nabla F_{w}(x_{t})\|^{2}+4G^{2})\right)\right]$ $\displaystyle\leq\frac{\gamma^{2}}{128L^{2}}\mathbb{E}\|\nabla F_{w}(x_{t-\tau })\|^{2}+\frac{\gamma^{2}}{2}\mathbb{E}\|\nabla F_{w}(x_{t})\|^{2}+2\gamma^{2} G^{2}.$ $$

Finally, based on Lemma 8, similarly we obtain

$$ $\displaystyle e_{4}$ $\displaystyle\leq\mathbb{E}\left[\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1} \alpha q_{t}^{i}\|\nabla F(x_{t-\tau})\|\|\nabla f_{i}(x_{t})-\nabla f_{i}(x_{ t-\tau})\|\right]$ $\displaystyle\leq\mathbb{E}\left[\frac{1}{B}\sum_{i\in S_{t}}\sum_{k=0}^{K-1} \left(\frac{(\alpha q_{t}^{i})^{2}K}{2}\|\nabla F(x_{t-\tau})\|^{2}+\frac{L^{2 }}{2K}\|x_{t}-x_{t-\tau}\|^{2}\right)\right]$ $\displaystyle\leq\frac{\gamma^{2}}{128L^{2}}\mathbb{E}\|\nabla F(x_{t-\tau})\| ^{2}+\frac{\gamma^{4}\tau}{2}(\sum_{l=t-\tau}^{t-1}\mathbb{E}\|\nabla F_{w}(x_ {l})\|^{2}+4\tau G^{2}).$ $$

Thus, denoting $\bar{a}=a\max_{i}\{w_{i}\}$

$$ $\displaystyle\frac{\gamma}{16\bar{a}L}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}$ $\displaystyle\leq\mathbb{E}[F_{w}(x_{t})-F_{w}(x_{t+1})]+\frac{\tau\gamma^{2}( 1+\gamma^{2})}{2}\sum_{l=t-\tau}^{t-1}\mathbb{E}\|\nabla F_{w}(x_{l})\|^{2}+ \frac{\gamma}{aL}G^{2}\mathbb{E}\|\tilde{q}_{t}\|_{\infty}^{2}$ $\displaystyle\quad+\left(\frac{\gamma^{2}}{2}+\frac{\gamma^{2}}{2L}+\frac{3 \gamma^{2}}{64L^{2}}\right)\mathbb{E}\|\nabla F_{w}(x_{t})\|^{2}+\left(\frac{ \gamma\delta^{2}}{8\bar{a}L}+\frac{\gamma^{2}}{64L^{2}}\right)\mathbb{E}\| \nabla F_{w}(x_{t-\tau})\|^{2}$ $\displaystyle\quad+\frac{\gamma}{4\bar{a}L}\mathbb{E}\left[\|\tilde{q}_{t}\|_{ \infty}^{2}\|\nabla F_{w}(x_{t-\tau})\|^{2}\right]+\frac{\gamma c_{1}^{2} \delta^{2}}{4\bar{a}L}G^{2}$ $\displaystyle\quad+\gamma^{2}G^{2}\left(2+2\tau^{2}+2\gamma^{2}\tau^{2}+\frac{ 2}{L}+\frac{3}{16L^{2}}\right)$ $$

which implies that

$$ $\displaystyle\gamma\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}$ $\displaystyle\leq 16\bar{a}L\mathbb{E}[F_{w}(x_{t})-F_{w}(x_{t+1})]+\frac{16 \bar{a}L\tau\gamma^{2}(1+\gamma^{2})}{2}\sum_{l=t-\tau}^{t-1}\mathbb{E}\| \nabla F_{w}(x_{l})\|^{2}$ $\displaystyle\quad+\gamma\left(16\bar{a}L\gamma+8\bar{a}\gamma+\frac{3\bar{a} \gamma}{4L}\right)\mathbb{E}\|\nabla F_{w}(x_{t})\|^{2}+\gamma\left(2c_{1}^{2} \delta^{2}+\frac{\bar{a}\gamma}{4L}\right)\mathbb{E}\|\nabla F_{w}(x_{t-\tau}) \|^{2}$ $\displaystyle\quad+4\gamma\mathbb{E}\left[\|\tilde{q}_{t}\|_{\infty}^{2}\| \nabla F_{w}(x_{t-\tau})\|^{2}\right]+16\gamma G^{2}\mathbb{E}\|\tilde{q}_{t} \|_{\infty}^{2}+4\gamma c_{1}^{2}\delta^{2}G^{2}$ $\displaystyle\quad+16\bar{a}L\gamma^{2}G^{2}\left(2+2\tau^{2}+2\gamma^{2}\tau^ {2}+\frac{2}{L}+\frac{3}{16L^{2}}\right)$ $\displaystyle\leq 16\bar{a}L\mathbb{E}[F_{w}(x_{t})-F_{w}(x_{t+1})]+\gamma \left(16\bar{a}L\gamma+8\bar{a}\gamma+\frac{3\bar{a}\gamma}{4L}\right)\mathbb{ E}\|\nabla F_{w}(x_{t})\|^{2}$ $\displaystyle\quad+\gamma\left(2c_{1}^{2}\delta^{2}+\frac{\bar{a}\gamma}{4L}+3 2\bar{a}L\tau\gamma(1+\gamma^{2})\right)\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\| ^{2}$ $\displaystyle\quad+4\gamma\mathbb{E}\left[\|\tilde{q}_{t}\|_{\infty}^{2}\| \nabla F_{w}(x_{t-\tau})\|^{2}\right]+16\gamma G^{2}\mathbb{E}\|\tilde{q}_{t} \|_{\infty}^{2}+4\gamma c_{1}^{2}\delta^{2}G^{2}$ $\displaystyle\quad+16\bar{a}L\gamma^{2}G^{2}\left(2+2\tau^{2}+2\gamma^{2}\tau^ {2}+8\tau^{4}\gamma^{2}(1+\gamma^{2})+\frac{2}{L}+\frac{3}{16L^{2}}\right)$ $$

where we make use of

$$ $\sum_{l=t-\tau}^{t-1}\mathbb{E}\|\nabla F_{w}(x_{l})\|^{2}\leq 4\tau\mathbb{E} \|\nabla F_{w}(x_{t-\tau})\|^{2}+16\tau^{3}\gamma^{2}G^{2}$ $$

by Lemma 9. Under the following conditions

$$ $\displaystyle 2c_{1}^{2}\delta^{2}\leq\frac{1}{6},\leavevmode\nobreak\ \leavevmode\nobreak\ \frac{\bar{a}\gamma}{4L}\leq\frac{1}{36},\leavevmode \nobreak\ \leavevmode\nobreak\ \gamma\leq\min\{\frac{1}{2\tau},\frac{1}{384 \bar{a}}\},$ $\displaystyle 64\bar{a}L\tau\gamma\leq\frac{1}{12},$ $$

which implies $32aL\tau\gamma(1+\gamma^{2})\leq\frac{1}{6}$ and hence $2c_{1}^{2}\delta^{2}+\frac{\bar{a}\gamma}{4L}+32\bar{a}L\tau\gamma(1+\gamma^{2
})\leq\frac{1}{2}$, then we obtain

$$ $\displaystyle\gamma\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}$ $\displaystyle\leq 32\bar{a}L\mathbb{E}[F_{w}(x_{t})-F_{w}(x_{t+1})]+2\gamma \left(16\bar{a}L\gamma+8\bar{a}\gamma+\frac{3\bar{a}\gamma}{4L}\right)\mathbb{ E}\|\nabla F_{w}(x_{t})\|^{2}$ $\displaystyle\quad+8\gamma\mathbb{E}\left[\|\tilde{q}_{t}\|_{\infty}^{2}\| \nabla F_{w}(x_{t-\tau})\|^{2}\right]+32\gamma G^{2}\mathbb{E}\|\tilde{q}_{t} \|_{\infty}^{2}+8\gamma c_{1}^{2}\delta^{2}G^{2}$ $\displaystyle\quad+32\bar{a}L\gamma^{2}G^{2}\left(2+2\tau^{2}+2\gamma^{2}\tau^ {2}+8\tau^{4}\gamma^{2}(1+\gamma^{2})+\frac{2}{L}+\frac{3}{16L^{2}}\right).$ $$

Summing over $\tau\leq t\leq T-1$ gives

$$ $\displaystyle\gamma\sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}$ $\displaystyle\leq 32\bar{a}L\Delta_{\tau}+2\gamma\left(16\bar{a}L\gamma+8\bar{ a}\gamma+\frac{3\bar{a}\gamma}{4L}\right)\sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F _{w}(x_{t})\|^{2}$ $\displaystyle\quad+8\gamma\sum_{t=\tau}^{T-1}\mathbb{E}\left[\|\tilde{q}_{t}\| _{\infty}^{2}\|\nabla F_{w}(x_{t-\tau})\|^{2}\right]+32\gamma G^{2}\sum_{t= \tau}^{T-1}\mathbb{E}\|\tilde{q}_{t}\|_{\infty}^{2}$ $\displaystyle\quad+32\bar{a}L\gamma^{2}G^{2}\left(3+6\tau^{2}+\frac{2}{L}+ \frac{3}{16L^{2}}\right)(T-\tau)+8\gamma c_{1}^{2}\delta^{2}G^{2}(T-\tau).$ $$

where $\Delta_{\tau}=\mathbb{E}[F_{w}(x_{\tau})-F^{*}]$ and we use $\gamma^{2}\tau^{2}\leq 1/4$. Again leveraging Lemma 9, we observe

$$ $\displaystyle\sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F_{w}(x_{t})\|^{2}\leq 4 \sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F_{w}(x_{t-\tau})\|^{2}+16\tau^{2}\gamma ^{2}G^{2}(T-\tau)$ $$

which thus renders

$$ $\displaystyle\frac{1}{T-\tau}\sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F_{w}(x_{t- \tau})\|^{2}$ $\displaystyle\leq\frac{32\bar{a}L\Delta_{\tau}}{\gamma(T-\tau)}+\frac{8}{T- \tau}\sum_{t=\tau}^{T-1}\mathbb{E}\left[\|\tilde{q}_{t}\|_{\infty}^{2}\|\nabla F _{w}(x_{t-\tau})\|^{2}\right]+\frac{32G^{2}}{T-\tau}\sum_{t=\tau}^{T-1}\mathbb {E}\|\tilde{q}_{t}\|_{\infty}^{2}$ $\displaystyle\quad+32\bar{a}LG^{2}\left(3\gamma+6\gamma\tau^{2}+\frac{2\gamma} {L}+\frac{3\gamma}{16L^{2}}+\frac{\gamma^{2}}{16aL}\right)+8c_{1}^{2}\delta^{2 }G^{2}.$ $$

by noting that $16\bar{a}L\gamma+8a\gamma+\frac{3\bar{a}\gamma}{4L}\leq\frac{1}{16}$.

In the following, we turn to bound $\Delta_{\tau}$. Noting that

$$ $\displaystyle F_{w}(x_{t+1})-F_{w}(x_{t})$ $\displaystyle\leq-\alpha K\langle\nabla F_{w}(x_{t}),\frac{1}{BK}\sum_{i\in S_ {t}}\sum_{k=0}^{K-1}\nabla f_{i}(x_{k}^{i})\rangle+\frac{\alpha^{2}K^{2}L}{2} \left\|\frac{1}{BK}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}\nabla f_{i}(x_{k}^{i}) \right\|^{2}$ $\displaystyle\leq\frac{\alpha K}{2}\left\|\frac{1}{BK}\sum_{i\in S_{t}}\sum_{k =0}^{K-1}(\nabla f_{i}(x_{k}^{i})-\nabla F_{w}(x_{t}))\right\|^{2}-\frac{ \alpha K}{2}\|\nabla F_{w}(x_{t})\|^{2}$ $$

by $\alpha\leq\frac{\gamma}{8aLK}\leq\frac{1}{2LK}$. Moreover, since

$$ $\displaystyle\left\|\frac{1}{BK}\sum_{i\in S_{t}}\sum_{k=0}^{K-1}(\nabla f_{i} (x_{k}^{i})-\nabla F_{w}(x_{t}))\right\|^{2}$ $\displaystyle\leq\frac{2}{BK}\sum_{i\in S_{t}}\sum_{k=0}^{K}(L^{2}\|x_{k}^{i}- x_{t}\|^{2}+4G^{2})$ $\displaystyle\leq 2\gamma^{2}\|\nabla F_{w}(x_{t})\|^{2}+8G^{2}$ $$

we conclude that

$$ $F_{w}(x_{t+1})-F_{w}(x_{t})\leq-\frac{\alpha K}{2}(1-2\gamma^{2})\|\nabla F_{w }(x_{t})\|^{2}+4\alpha KG^{2}\leq\frac{\gamma}{2\bar{a}L}G^{2}$ $$

which implies

$$ $\Delta_{\tau}=\mathbb{E}[F_{w}(x_{\tau})-F^{*}]\leq\frac{\gamma\tau}{2\bar{a}L }G^{2}+F_{w}(x_{0})-F_{w}^{*}.$ $$

∎

###### Lemma 6 .

###### Proof.

###### Lemma 7 .

###### Proof.

###### Lemma 8 .

###### Proof.

###### Lemma 9 .

###### Proof.

###### Lemma 10 .

###### Proof.

## Appendix F Convergence analysis of FedAvg under correlated client participation

In this section, we provide the convergence analysis of Vanilla FedAvg for correlated client participation. We first show FedAvg suffers from unavoidable bias, summarized by the following proposition.

###### Proposition 3 .

There exists a problem case such that FedAvg converges with unavoidable asymptotic bias.

###### Proof.

We consider a problem case with $N=3,B=1,R=1$. We set $p_{1}=0.25,p_{2}=0.25,p_{3}=0.5$ and $f_{i}(x)=\frac{1}{2}(x-i)^{2},i=1,2,3$ and $x\in\mathbb{R}$. In this case, we have the Markov chain induced by the problem denoted by $P\in\mathbb{R}^{3\times 3}$. Letting $\pi\in\mathbb{R}^{3}$ be the stationary distribution of $P$, a straightforward calculation gives $\pi_{1}=\pi_{2}=0.3,\pi_{3}=0.4$. Then we obtain the server’s update of FedAvg given by

$$ $x_{t+1}=\beta x_{t}+(1-\beta)i_{t}$ $$

where $\beta=(1-\alpha)^{K}<1$ with $\alpha$ being the stepsize of local updates; $i_{t}$ is the index of the sampled client at round $t$ which is a random variable. Taking the expectation on both sides yields

$$ $\displaystyle\mathbb{E}[x_{t+1}]$ $\displaystyle=\beta\mathbb{E}[x_{t}]+(1-\beta)\mu^{T}P^{t}I$ $\displaystyle=\beta\mathbb{E}[x_{t}]+(1-\beta)(\mu^{T}P^{t}-\pi^{T})I+(1-\beta )\pi^{T}I$ $$

where $\mu=(p_{1},p_{2},p_{3})$, and $I=(1,2,3)$ is the vector formed by clients’ indices.
Noting that the third term vanishes as $t\to\infty$ due to the convergence the Markov chain (shown by Lemma 4), we conclude that $\lim_{t\to\infty}\mathbb{E}[x_{t}]=\sum_{i=1}^{3}\pi_{i}i$ which is the minimizer of $F_{\pi}(x):=\sum_{i=1}^{3}\pi_{i}f_{i}(x)$ but not $F(x)=\frac{1}{3}\sum_{i=1}^{3}f_{i}(x)$. And $|F^{\prime}(\pi^{T}I)|=|I^{T}(\pi-\frac{1}{3}\mathbf{1}_{3})|$. Therefore, the bias in Theorem 1 is unavoidable.
∎

Then we show the convergence result of FedAvg.

###### Theorem 4 .

Suppose Assumptions 1,2 hold and assume $\|\nabla F(x)\|\leq D,\forall x$. Then, by choosing $\alpha=\mathcal{O}(\frac{\gamma}{K})$ and $T\geq 2\tau_{mix}\log\tau_{mix}$, the output $\tilde{x}_{T}$ generated FedAvg satisfies

$$ $\displaystyle\mathbb{E}\|\nabla F(\tilde{x}_{T})\|^{2}$ $\displaystyle=\mathcal{O}\left(\frac{\Delta_{0}}{\gamma T}\right)+\mathcal{O} \left(\frac{\tau_{mix}\log TG^{2}}{T}\right)+\mathcal{O}\left((\gamma\tau_{mix }^{2}\log^{2}T+\gamma^{2})G^{2}\right)$ $\displaystyle\quad+\mathcal{O}\left((G^{2}+D^{2})\|\pi-\frac{1}{N}\mathbf{1}_{ N}\|_{1}^{2}\right)$ $$

###### Proof.

For FedAvg, we have $y_{t}^{i}=1/N$. Utilizing Lemma 10 and setting $w_{i}=\frac{1}{N}$, it yields

$$ $\displaystyle\frac{1}{T-\tau}\sum_{t=0}^{T-\tau-1}\mathbb{E}\|\nabla F(x_{t}) \|^{2}$ $\displaystyle\leq\frac{32L\Delta_{0}}{\gamma(T-\tau)}+\frac{8D^{2}}{T-\tau} \sum_{t=\tau}^{T-1}\mathbb{E}\|\tilde{q}_{t}\|_{\infty}^{2}+\frac{36G^{2}}{T- \tau}\sum_{t=\tau}^{T-1}\mathbb{E}\|\tilde{q}_{t}\|_{\infty}^{2}+\frac{16\tau G ^{2}}{T-\tau}$ $\displaystyle\quad+32LG^{2}\left(3\gamma+6\gamma\tau^{2}+\frac{2\gamma}{L}+ \frac{3\gamma}{16L^{2}}+\frac{\gamma^{2}}{16L}\right)+8c_{1}^{2}\delta^{2}G^{2}.$ $$

Then noting that $\|\tilde{q}_{t}\|_{\infty}^{2}\leq\pi_{min}^{-2}\|\pi-\frac{1}{N}\mathbf{1}_{N
}\|_{1}^{2}$, we conclude

$$ $\displaystyle\mathbb{E}\|\nabla F(\tilde{x}_{T})\|^{2}=\mathcal{O}\left(\frac{ \Delta_{0}}{\gamma T}\right)+\mathcal{O}\left(\frac{\tau G^{2}}{T}\right)+ \mathcal{O}\left((\gamma\tau^{2}+\gamma^{2})G^{2}\right)+\mathcal{O}\left((G^{ 2}+D^{2})\|\pi-\frac{1}{N}\mathbf{1}_{N}\|_{1}^{2}\right)$ $$

by setting $\delta=1/\sqrt{T}$. For the above to be true, we need $T\geq\tau=\tau_{mix}\log T$, which is actually always satisfied for $T\geq 2\tau_{mix}\log\tau_{mix}$. To see this, we observe that if $T\leq\tau_{mix}^{2}$, $\tau_{mix}\log T\leq 2\tau_{mix}\log\tau_{mix}$; if $T\geq\tau_{mix}^{2}$, $\tau_{mix}\log T\leq\sqrt{T}\log T\leq T$. This completes the proof.
∎

The following corollary restates Theorem 1.

###### Corollary 1 .

Suppose all conditions in Theorem 4 hold. Then, choosing $\alpha=\tilde{\mathcal{O}}(1/(K\tau_{mix}\sqrt{T}))$, the output $\tilde{x}_{T}$ of FedAvg satisfies

$$ $\mathbb{E}\|\nabla F(\tilde{x}_{T})\|^{2}\leq\tilde{\mathcal{O}}\left(\frac{ \tau_{mix}}{\sqrt{T}}\right)+\mathcal{O}\left((D^{2}+G^{2})\big{\|}\pi_{R}- \frac{1}{N}\mathbf{1}_{N}\big{\|}_{1}^{2}\right).$ $$

###### Proof.

The proof is straightforward by simply plugging in $\gamma=\mathcal{O}(1/(\tau\sqrt{T}))$ and $\tau=\tau_{mix}\log T$ to Theorem 4.
∎

###### Proposition 3 .

###### Proof.

###### Theorem 4 .

###### Proof.

###### Corollary 1 .

###### Proof.

## Appendix G Convergence analysis of Algorithm 1

We first provide the following theorem showing that $y_{t}^{i}$ serves as a reasonable estimation of $\pi^{i}$.

###### Theorem 5 .

For any real-valued function $f\in\mathbb{R}^{N}$ and any initial distribution $\mu\in\mathbb{R}^{N}$, we have the following:

$$ $\displaystyle\mathbb{E}_{\mu}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t})-\pi_{R} ^{T}f\right)$ $\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\mu^{T}Q_{\mu}^{{\dagger}}(P_{R}^{t}- \mathbf{1}\zeta_{R}^{T})Q_{R}f$ $\displaystyle T\mathbb{E}_{\pi_{R}}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t})- \pi_{R}^{T}f\right)^{2}$ $\displaystyle\leq f^{T}\Pi_{R}(I-\mathbf{1}_{N}\pi_{R}^{T})f+c_{0}\pi_{\max}\| f\|_{\infty}^{2}N\tau_{mix}$ $\displaystyle T\mathbb{E}_{\mu}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t})-\pi_{ R}^{T}f\right)^{2}$ $\displaystyle\leq T\mathbb{E}_{\pi_{R}}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t })-\pi_{R}^{T}f\right)^{2}+3c_{0}N^{2}\|g\|_{\infty}^{2}\tau_{mix}$ $$

where $\mathbb{E}_{\mu}(\cdot)$ means the initial state $X_{0}$ follows $\mu$; $\Pi_{R}=\mathrm{diag}(\pi_{R}[i])$ and $Q_{\mu}^{{\dagger}}$ is defined such that $\mu^{T}Q_{\mu}^{{\dagger}}=\zeta_{\mu}$ and $\zeta_{\mu}^{T}Q_{R}=\mu$; $g=f-\pi_{R}^{T}f\mathbf{1}_{N}$; $\tau_{mix}$ is the mixing time of $P_{R}$.

###### Proof.

We firstly show the first equality. Note that

$$ $\displaystyle\mathbb{E}_{\mu}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t})-\pi_{R} ^{T}f\right)$ $\displaystyle=\frac{1}{T}\sum_{k=0}^{T-1}(\mu^{T}P_{R}^{k}Q_{R}f-\zeta_{R}^{T} Q_{R}f)$ $\displaystyle=\frac{1}{T}\sum_{k=0}^{T-1}\mu^{T}(P_{R}^{k}-\mathbf{1}\zeta_{R} ^{T})Q_{R}f$ $$

where we observe that $\mu^{T}\mathbf{1}=1$.

Then we turn to show the second inequality. By the definition, we have

$$ $\displaystyle T\mathbb{E}_{\pi_{R}}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t})- \pi_{R}^{T}f\right)^{2}$ $\displaystyle=\mathrm{Var}_{\pi_{R}}(f(X_{0}))+\frac{2}{T}\sum_{k=1}^{T-1}(T-k )\mathrm{Cov}_{\pi_{R}}(f(X_{0}),f(X_{k})).$ (11) $$

For any $k$, let $\zeta_{k}$ and $\pi_{k}$ be the distributions after the Markov chain evolves $k$ steps. Then, we have $\zeta_{k+1}^{T}=\zeta_{k}^{T}P_{R}$ and $\pi_{k}^{T}=\zeta_{k}^{T}Q_{R}$. Defining $\hat{Q}_{k}\in\mathbb{R}^{N\times d(M,R)}$ as an inverse mapping from $\pi_{k}$ to $\zeta_{k}$, i.e., $\zeta_{k}^{T}=\pi_{k}^{T}\hat{Q}_{k}$, it is straightforward to verify that we can always pick a nonnegative $\hat{Q}_{k}$ such that $\hat{Q}_{k}\mathbf{1}=\mathbf{1}_{N}$ in the sense that the freedom of $\hat{Q}_{k}$ is $(N-1)\times d(M,R)-N$ when forcing both $\zeta_{k}^{T}=\pi_{k}^{T}\hat{Q}_{k}$ and $\hat{Q}_{k}\mathbf{1}=\mathbf{1}_{N}$ to hold.
Moreover,

$$ $\displaystyle\mathrm{Cov}_{\pi_{R}}(f(X_{0}),f(X_{k}))$ $\displaystyle=\sum_{i}\pi_{R}[i]f(i)\sum_{j}[\hat{Q}_{k}P_{R}^{k}Q_{R}]_{i,j}f (j)-\sum_{i,j}\pi_{R}[i]\pi_{R}[j]f(i)f(j)$ $\displaystyle=f^{T}\Pi_{R}\hat{Q}_{k}P_{R}^{k}Q_{R}f-f^{T}\Pi_{R}\mathbf{1}_{N }\pi_{R}^{T}f$ $\displaystyle=f^{T}\Pi_{R}\hat{Q}_{k}(P_{R}^{k}-\mathbf{1}\zeta_{R}^{T})Q_{R}f$ $$

where we utilize $\hat{Q}_{k}\mathbf{1}=\mathbf{1}_{N}$. Further, $\|\hat{Q}_{k}\|_{\infty}=1,\forall k\geq 0$ since $\hat{Q}_{k}$ is nonnegative. Then,

$$ $\mathrm{Cov}_{\pi_{R}}(f(X_{0}),f(X_{k}))\leq\pi_{\max}\|f\|_{\infty}^{2}\|Q_{ R}\|_{\infty}\|P_{R}^{k}-\mathbf{1}\zeta_{R}^{T}\|_{\infty}.$ $$

Substituting it into (11) yields

$$ $\displaystyle T\mathbb{E}_{\pi_{R}}\left(\frac{1}{T}\sum_{t=0}^{T-1}f(X_{t})- \pi_{R}^{T}f\right)^{2}$ $\displaystyle\leq\mathrm{Var}_{\pi_{R}}(f(X_{0}))+2\sum_{k=1}^{\infty}\mathrm{ Cov}_{\pi_{R}}(f(X_{0}),f(X_{k}))$ $\displaystyle\leq\mathrm{Var}_{\pi_{R}}(f(X_{0}))+2\pi_{\max}\|f\|_{\infty}^{2 }\|Q_{R}\|_{\infty}\sum_{k=0}^{T}\|P_{R}^{k}-\mathbf{1}\zeta_{R}^{T}\|_{\infty}$ $\displaystyle\leq f^{T}\Pi_{R}(I-\mathbf{1}_{N}\pi_{R}^{T})f+c_{0}\pi_{\max}\| f\|_{\infty}^{2}\|Q_{R}\|_{\infty}\tau_{mix}$ $$

where we make use of Lemma 5.
Finally noting that $\|Q_{R}\|_{\infty}\leq\|Q_{R,1}\|_{\infty}\|Q_{R,2}\|_{\infty}\leq N$ completes the proof of the second inequality.

To obtain the third inequality, defining $g(i)=f(i)-\pi_{R}^{T}f$ we aim to bound

$$ $\displaystyle T$ $\displaystyle\left|\mathbb{E}_{\mu}\left(\frac{1}{T}\sum_{k=0}^{T-1}g(X_{k}) \right)^{2}-\mathbb{E}_{\pi_{R}}\left(\frac{1}{T}\sum_{k=0}^{T-1}g(X_{k}) \right)^{2}\right|$ $\displaystyle\leq\left|\frac{1}{T}\sum_{k=0}^{T-1}\mathbb{E}_{\mu}g^{2}(X_{k}) -\mathbb{E}_{\pi_{R}}g^{2}(X_{k})\right|+\frac{2}{T}\sum_{k=0}^{T-1}\sum_{l=k+ 1}^{T-1}\big{|}\mathbb{E}_{\mu}(g(X_{k})g(X_{l}))-\mathbb{E}_{\pi_{R}}(g(X_{k} )g(X_{l}))\big{|}.$ $$

For notation simplicity, we drop the subscript $R$ without confusion to get

$$ $\displaystyle\big{|}\mathbb{E}_{\mu}(g(X_{k})g(X_{l}))-\mathbb{E}_{\pi_{R}}(g( X_{k})g(X_{l}))\big{|}$ $\displaystyle=\left|\sum_{i,j}\mu_{i}g(j)((\hat{Q}_{k}P^{k}Q)_{i,j}-\pi_{j}) \sum_{r}((\hat{Q}_{l}P^{l-k}Q)_{j,r}-\pi_{r})g(r)\right|$ $\displaystyle=\left|\sum_{i,j}\mu_{i}g(j)(\hat{Q}_{k}(P^{k}-\mathbf{1}\zeta^{T })Q)_{i,j}\sum_{r}(\hat{Q}_{l}(P^{l-k}-\mathbf{1}\zeta^{T})Q)_{j,r}g(r)\right|$ $\displaystyle\leq\|g\|_{\infty}^{2}N^{2}\|P^{l}-\mathbf{1}\zeta^{T}\|_{\infty}.$ $$

Thus, by Lemma 5,

$$ $\displaystyle T$ $\displaystyle\left|\mathbb{E}_{\mu}\left(\frac{1}{T}\sum_{k=0}^{T-1}g(X_{k}) \right)^{2}-\mathbb{E}_{\pi_{R}}\left(\frac{1}{T}\sum_{k=0}^{T-1}g(X_{k}) \right)^{2}\right|$ $\displaystyle\leq\frac{1}{T}\sum_{k=0}^{T-1}\mu^{T}Q_{\mu}^{{\dagger}}(P^{k}- \mathbf{1}\zeta^{T})Qg^{2}+\frac{2}{T}c_{0}N^{2}\|g\|_{\infty}^{2}\sum_{k=0}^{ T-1}\tau_{mix}$ $\displaystyle\leq\frac{1}{T}\sum_{k=0}^{T-1}\mu^{T}Q_{\mu}^{{\dagger}}(P^{k}- \mathbf{1}\zeta^{T})Qg^{2}+2c_{0}N^{2}\|g\|_{\infty}^{2}\tau_{mix}$ $\displaystyle\leq\frac{1}{T}c_{0}\|g\|_{\infty}^{2}N\tau_{mix}+2c_{0}N^{2}\|g \|_{\infty}^{2}\tau_{mix}$ $\displaystyle\leq 3c_{0}N^{2}\|g\|_{\infty}^{2}\tau_{mix}.$ $$

Combining all the above completes the proof.
∎

Then, the following corollary induced by Theorem 5 is exactly Lemma 2.

###### Corollary 2 .

Given initial $\lambda_{0}=\mathbf{0}_{N}$ and let $\nu_{t}^{i}=\frac{1}{\lambda_{t}^{i}N}$ as in Algorithm 1, we have

$$ $\mathbb{E}\|\tilde{\nu}_{t}\|_{\infty}^{2}\leq\mathcal{O}\left(\frac{\tau_{mix }}{t}\right)$ $$

where $\tilde{\nu}^{i}_{t}=\nu^{i}_{t}-\frac{1}{\pi_{i}N}$ and $\tilde{\nu}_{t}=(\tilde{\nu}_{t}^{1},\dots,\tilde{\nu}_{t}^{N})$.

###### Proof.

By Theorem 5, setting $f=\mathbf{e}_{i}$ for any $i$, we have

$$ $\mathbb{E}(\lambda_{t}^{i}-\pi_{i})^{2}=\mathcal{O}\left(\frac{N^{2}\tau_{mix} }{t}\right)$ (12) $$

Note that

$$ $\displaystyle\mathbb{E}(\tilde{\nu}_{t}^{i})^{2}=\frac{1}{N^{2}}\mathbb{E} \left(\frac{\lambda_{t}^{i}-\pi_{i}}{\lambda_{t}^{i}\pi_{i}}\right)^{2}$ $\displaystyle=\frac{1}{N^{2}}\mathbb{E}\left[\left(\frac{\lambda_{t}^{i}-\pi_{ i}}{\lambda_{t}^{i}\pi_{i}}\right)^{2}\big{|}\lambda_{t}^{i}\geq a\right]P( \lambda_{t}^{i}\geq a)$ $\displaystyle+\frac{1}{N^{2}}\mathbb{E}\left[\left(\frac{\lambda_{t}^{i}-\pi_{ i}}{\lambda_{t}^{i}\pi_{i}}\right)^{2}\big{|}\lambda_{t}^{i}<a\right]P(\lambda _{t}^{i}<a)$ (13) $$

for any positive $a$. Moreover, due to the Markov chain in Section 3 is irreducible by Lemma 1, every client will be visited infinitely as $t$ goes to infinite, which then implies there always exists some strictly positive constant $a_{0}$ independent of $t$ such that $\lambda_{t}^{i}\geq a_{0}>0$ almost surely for any $i\in[N]$. Combining (12),(G) we conclude

$$ $\mathbb{E}\|\tilde{\nu}_{t}^{i}\|_{\infty}^{2}=\mathcal{O}\left(\frac{\tau_{ mix}}{t}\right).$ $$

∎

###### Theorem 5 .

###### Proof.

###### Corollary 2 .

###### Proof.

### G.1 Convergence proof of Algorithm 1

The following lemma is useful to derive the convergence proof of Algorithm 1.

###### Lemma 11 .

Supposing that the stochastic scalar sequence $\mathbb{E}[U_{1}(t)^{2}]\leq u(t)$ with $u$ being a monotonically decreasing positive function w.r.t. $t$ and assuming that $U_{1}(t)\leq\bar{u}<\infty$ almost surely, then given any $\delta,\epsilon>0$, for all $t\geq\inf\{t_{0}\mid u(t_{0})/\delta^{2}\leq\epsilon/\bar{u}^{2}\}$ and stochastic scalar sequence $U_{2}(t)$,

$$ $\displaystyle\mathbb{E}\left[U_{1}(t)^{2}U_{2}(t)\right]\leq(\epsilon+\delta^{ 2})\mathbb{E}[U_{2}(t)].$ $$

###### Proof.

For any $\delta>0$, we have for all $t\geq\inf\{t_{0}\mid u(t_{0})/\delta^{2}\leq\epsilon/\bar{u}^{2}\}$

$$ $\displaystyle\mathbb{E}[U_{1}(t)^{2}U_{2}(t)]$ $\displaystyle=P(U_{1}(t)>\delta)\mathbb{E}[U_{1}(t)^{2}U_{2}(t)\mid U_{1}(t)> \delta]+P(U_{1}(t)\leq\delta)\mathbb{E}[U_{1}(t)^{2}U_{2}(t)\mid U_{1}(t)\leq\delta]$ $\displaystyle\leq P(U_{1}(t)>\delta)\bar{u}^{2}\mathbb{E}[U_{2}(t)]+\delta^{2} \mathbb{E}[U_{2}(t)]$ $\displaystyle\leq(\epsilon+\delta^{2})\mathbb{E}[U_{2}(t)]$ $$

where we use the Markov inequality in the last step, i.e.,

$$ $\displaystyle P(U_{1}(t)>\delta)\leq P(U_{1}(t)^{2}>\delta^{2})\leq\frac{u(t)} {\delta^{2}}.$ $$

∎

Then we are ready to provide the proof for Theorem 3.

Proof of Theorem 3:
As discussed in the proof of Corollary 2, we know that there exists a positive $a^{-1}$ which lower bounds each $\lambda_{t}^{i}$ for all $t$ almost surely, implying that $\tilde{\nu}_{t}^{i}\leq\frac{1}{N}(a+\pi_{min}^{-1})$. Then for any $t>\tau>c^{\prime}\tau_{mix}$ (with $c^{\prime}$ being some constant), we have

$$ $\displaystyle\mathbb{E}\left[\|\tilde{\nu}_{t}\|_{\infty}^{2}\|\nabla F(x_{t- \tau})\|^{2}\right]\leq\frac{1}{16}\mathbb{E}\|\nabla F(x_{t-\tau})\|^{2}$ $$

by Lemmas 2 and 11. Further Utilizing Lemma 10 with setting $w_{i}=\frac{1}{N}$, we obtain

$$ $\displaystyle\frac{1}{T-\tau}\sum_{t=\tau}^{T-1}\mathbb{E}\|\nabla F(x_{t-\tau })\|^{2}$ $\displaystyle\leq\frac{64\bar{a}L\Delta_{0}}{\gamma(T-\tau)}+\frac{64G^{2}}{T- \tau}\sum_{t=\tau}^{T-1}\mathbb{E}\|\tilde{\nu}_{t}\|_{\infty}^{2}+\frac{32 \tau G^{2}}{T-\tau}+16c_{1}^{2}\delta^{2}G^{2}$ $\displaystyle\quad+64\bar{a}LG^{2}\left(3\gamma+6\gamma\tau^{2}+\frac{2\gamma} {L}+\frac{3\gamma}{16L^{2}}+\frac{\gamma^{2}}{16aL}\right)$ $$

for $\tau\geq\tau_{mix}\max\{c^{\prime},\log(1/\delta)\}$. Similar to the proofs of Theorem 4, setting $\delta=1/\sqrt{T}$, with $T\geq c^{{\dagger}}\tau_{mix}\log\tau_{mix}$ for some constant $c^{{\dagger}}$, we finally conclude that

$$ $\displaystyle\mathbb{E}\|\nabla F(\tilde{x}_{T})\|^{2}=\tilde{\mathcal{O}} \left(\frac{\tau_{mix}}{\sqrt{T}}\right)+\mathcal{O}\left(\frac{1}{T}\right)$ $$

by choosing $\gamma=\mathcal{O}(1/(\tau\sqrt{T}))$ with $\tau=\Omega(\tau_{mix}\log T)$ and by leveraging the fact that $\sum_{t=\tau}^{T-1}\mathbb{E}\|\tilde{\nu}_{t}\|_{\infty}^{2}=\mathcal{O}(\tau
_{mix}\log T)$ implied by Lemma 2.

###### Lemma 11 .

###### Proof.

## Appendix H The influence of R 𝑅 R italic_R on convergence rates

Figure: Figure 4: Convergence of client sampling distribution to $\pi_{R}$ for different $R$ ($N=100,B=1$).
Refer to caption: x7.png

In this section, we discuss the effect of different values of $R$ on the convergence rates of Debiasing FedAvg and Vanilla FedAvg as observed empirically in Figure 3. We simulate the ”effective” client sampling distribution (i.e., $\eta_{R}(t)$) as time evolves for different minimum separation $R$, where we set $N=100,B=1$. Figure 4 shows the evolution of client sampling distributions to their corresponding stationary $\pi_{R}$’s. Clearly increasing $R$, the convergence rate of ”effective” client sampling distribution to the stationary distribution also increasing, implying the decrease of mixing time $\tau_{mix}$ (see Appendix B for details). Combining this observation together with Theorems 1 and 3 leads to that larger $R$ 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$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 2
questions: 1. The algorithm is based on GD instead of SGD. If SGD was used, will there be any challenges?

2. I suggest the authors put the proof of Proposition 1 in the appendix.
soundness: 3
strengths: 1. The authors formulates the client participation process as a R-th order Markov chain. 

2. The authors proposed the debiasing FedAvg algorithm based on the estimation of marginal stationary distribution of clients to be sampled. 

3. The authors provided the convergence analysis of both FedAvg (to indicate the problem) and the proposed algorithm which can converge.
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.
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. 

2. The authors discussed quite a few limitations of the proposed approach and its proofs. These seem the weaknesses of the paper.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Theorem 2 holds only under specific requirements. What about more general settings that relax these requirements?
2. 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?
soundness: 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.
2. 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$. 
3. To achieve unbiased solutions, the authors propose a debiasing algorithm for FedAvg, with performance guarantees provided through both theoretical analysis and empirical evaluation.
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.
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$.
2. 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.
3. 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.


Minor: In line 109, delete “some”.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. If there is extreme heterogeneity among clients, how might a larger minimum separation $R$ impact the model's performance?
soundness: 3
strengths: 1. The authors find common FL assumption that clients participate independently and uniformly is unrealistic.
2. The paper frames client participation as a Markov process, capturing real-world constraints and interdependencies among clients.
3. The paper proposes Debiasing FedAvg converging to an unbiased solution with theoretical analysis.
4. Experiments on both synthetic and real datasets validate the algorithm’s effectiveness.
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.
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$.
2. The paper assumes a uniform minimum separation for all clients, which may not reflect real-world situations.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: Are Markov-chain model really necessary to analyze this problem?
soundness: 2
strengths: - Motivation: the minimum separation in federated learning is reasonable to analyze.
- Literature review is thorough.
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.
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.

- As has been mentioned in the "Limitations" section, the theoretical results do not enjoy linear scalability.

- 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. 

- The presentation of the paper can be improved.

Meta-review: This introduces a theoretical framework modeling client participation in federated learning (FL) as a Markov chain, addressing non-uniform and correlated participation across rounds. The authors analyze scenarios where clients must wait a minimum number of rounds before re-participating, demonstrating that increasing this minimum separation reduces bias caused by non-uniform client availability. They also propose a debiasing algorithm for Federated Averaging (FedAvg) that converges to the unbiased optimal solution under arbitrary minimum separation and unknown client availability distributions.

Reviewers acknowledged the novelty of modeling client participation as a Markov chain and appreciated the practical relevance of addressing correlated client participation in FL systems. The proposed debiasing algorithm was noted as a significant contribution to improving convergence in realistic FL scenarios. Reviewers found the mathematical rigor appropriate and the assumptions reasonable for the FL context. The empirical results supporting the theoretical claims were well-received. However, some reviewers suggested that additional experiments on diverse datasets and with varying system parameters could strengthen the validation of the proposed methods.

In response to the feedback, the authors provided clarifications on the Markov chain modeling approach and supplied additional experimental results addressing concerns about empirical validation. They also revised the manuscript to improve clarity, especially in sections detailing the theoretical framework and algorithmic procedures.

---
Considering the reviewers' assessments and the authors' responses, the decision is to accept the paper. The work presents a novel and practically significant approach to addressing correlated client participation in federated learning through Markov chain modeling and a debiasing algorithm. The theoretical contributions are well-substantiated, and the empirical validations, though with room for further expansion, support the claims made. The authors' revisions have adequately addressed the primary concerns regarding clarity and empirical evidence.

Decision: Accept (Poster)