Debiasing Federated Learning with Correlated Client Participation

Response to Weakness 1: There seems to be a misunderstanding of our problem setting and therefore its applicability and associated contribution. We clarify our setup here. Our participation pattern is as following:

1. Each client $i$ is sampled with probability proportional to $p_i$, only after it has waited for at least $R$ rounds;

2. Otherwise, client $i$ is not sampled.

3. At every round, $B$ clients are sampled to participate in the system.

Thus, as cyclic participation in literature (see Cho et al., 2023 in References), sampling $B$ clients every round forces them to participate exactly once within every $N/B$ rounds. Moreover, we note that our setting is much more general compared to literature, although there is still a gap to the real-world scenario. In particular, setting $R=0$, we reduce to uniformly and independently sampling of clients; setting $R=1$, we reduce to conventional first-order Markov chain case; and setting $R=M-1$, we recover the cyclic participation case. More importantly, our introduced markov-chain framework provides a systematic way to quantify the bias under non-uniform and time-dependent participation, and then allow us to propose solutions to resolve the bias. This is the main contribution and novelty of this paper, which is totally not captured by literature.

Response to Weakness 2: We acknowledge that our convergence bounds do not enjoy speedup as in literature. This is actually due to the technical difficulty in dealing with time-correlated client sampling. We note that all literature enjoying speedup in convergence relies on the assumption of independent client sampling, which makes the analysis much tractable compared to ours. The only relevant setting that theoretically studies time-correlated participation is (Cho et al., 2023), where it forces clients to participate exactly once within every $M=N/B$ rounds (i.e., in a cyclic way) which is quite restrictive compared to ours. Even in the cyclic participation case, the convergence bounds shown in (Cho et al., 2023) grow with respect to $M$, while ours get rid of the dependence on $M$. How to get a speedup in the convergence analysis is interesting and important and we hope to address it in the future.

Response to Weakness 3: We believe that the Markov-chain modeling is an effective way to solve this problem. Actually, we have to point out that Algorithm 1 does not try to estimate $p_i$, but rather it tries to estimate $\pi_i$ which is the stationary distribution induced by the Markov chain. The values of $p_i$ define the transition probability matrix (see eqs. (3)-(5) for details) of the Markov chain, which has a stationary distribution $\pi$, i.e., its left eigenvector corresponding to eigenvalue 1. But the values of $p_i$ do not directly translate to values of $\pi_i$. There is a fundamental difference between $p_i$ and $\pi_i$. Due to time correlation, the “effective” probability of client $i$ to be sampled at round $t$ is no longer $p_i$. Instead, the “effective” sampling distribution is now a time-varying distribution defined in eq. (5). If $R=0$, then it reduces to $p_i$ because now clients are sampled independently. But this is generally not true when $R > 0$! We also recommend the reviewer to refer to Lines 1340-1343 in the proof of Proposition 3 in Appendix F, where $p_1 = p_2 = 0.25, p_3=0.5$ but $\pi_1=\pi_2=0.3, \pi_4=0.4$, indicating that $\pi_i$ and $p_i$ are not the same.

Therefore, although Algorithm 1 counts the participation times of clients to estimate $\pi$ which seems simple, this estimator is not independent but time-correlated. We recommend the reviewer to refer to Theorem 5 and Corollary 2 in Appendix G to see that the convergence of the estimator involves much more careful analysis and technical difficulties.

Response to Weakness 4: We kindly request the reviewer to elaborate their feedback on the presentation, and would be happy to discuss and adopt concrete suggestions. Meanwhile, we updated the manuscript to include more explicit definitions of some of the notations which are marked in red.

Response to Question: There might be some other techniques to analyze this problem, but the Markov-chain framework offers an effective way to systematically solve it. Leveraging such Markov-chain framework, we are able to characterize the bias suffered by existing FL algorithms and then propose methods to mitigate the bias. Moreover, note that there is no existing analysis for such a practical problem in literature and we are the first to provide theoretical characterization.

Response to Weakness 1: We have added the results of test accuracies among FedAvg, Debiasing FedAvg (ours) and FedVARP under Cifar10 in Appendix H in the updated manuscript. The experimental results show that increasing $R$ reduces bias and increases test accuracy for both FedAvg and FedVARP; and our Debiasing FedAvg outperforms FedAvg and FedVARP in both training and test settings (see Table 1 in Appendix H). We also highlight that the main problem studied in this paper is the bias effect induced by correlated client participation (justified by Theorem 1 and 2) and how to reduce it (justified by Theorem 3). Thus, we mainly focus on the training stage, i.e., solving problem (1) in the federated setting. Shown by our theories and experiments, the training error of server’s model output by conventional FL algorithms does suffer from unavoidable bias. And we can effectively reduce the bias, i.e., getting a smaller training error, by increasing $R$, and particularly no bias when $R=M-1$.

Response to Weakness 2: We argue that a uniform $R$ is actually considered in the real-world setting. In particular, as discussed in (Xu et al., 2023) in References, a uniform minimum separation $R$ is adopted in Google Gboard to achieve privacy guarantees with larger $R$ leading to stronger privacy (Kairous et al., 2021). We still note that compared to literature where clients are sampled independently or from a cyclic pattern, our problem is much more general and captures them as special cases. Moreover, in the last paragraph of Section 5 (see Line 435), we discussed the possibility to extend uniform $R$ to client-specific $R_i$. In fact, for client-specific $R_i$, our theories (Theorems 1 and 3) still hold.

Response to Question 1: We omitted the dependence on heterogeneity in the main text. Actually, our bounds are proportional to the heterogeneity level $G^2$ (defined in Assumption 1). In Appendices G and F, one can see explicitly the effect of heterogeneity on the convergence (see Lines 1384 and 1547 for details, respectively). In particular, as heterogeneity grows, the larger the gap is between what the vanilla FedAvg converges to and the original optimal solution. With larger minimum separation, this gap shrinks. Under our debiasing algorithm, however, even with large heterogeneity, we can recover the original optimal solution.

Response to Weakness 1: We acknowledge that Theorems 1 and 3 hold for $R \le M-2$. The reason is that when $R \le M-2$ the underlying Markov chain (5) is aperiodic as shown in Lemma 1, then guaranteeing the unique stationary distribution $\pi_R$ exists, based on which our analysis can go through. For $R=M-1$ since now the Markov chain is periodic, then its stationary distribution is not well-defined (so is the mixing time $\tau_{mix}$). Rather, we define $\pi_{M-1}$ to be the induced Perron vector (see Line 244). Actually, the analysis of $R=M-1$ is much easier compared to $R \le M-2$, since now the clients participate cyclically and hence it is equivalent to that clients are sampled uniformly. In particular, the term $e_2$ in the proof of Lemma 10 is zero for any $t$ and $\tau$. Therefore, as we stated in Lines 423-427, much better convergence bounds can be obtained due to such nice cyclic pattern (see Cho et al., 2023 for more details in References in the paper). The reason we did not include $R=M-1$ to our Theorems 1 and 3 is that the mixing time $\tau_{mix}$ is not well-defined in this case, since the Markov chain is periodic.

Response to Weakness 2: In Algorithm 1 and all our analysis, there is no restriction to partition clients into separate “groups”. We note that our analysis holds true even for $B=1$, which would effectively remove the partition. Initially, any subset of clients with size $B$ can be sampled. Then due to the requirement of minimum separation, the group of clients becomes available at the same time. We therefore group them in experiments only for implementation simplicity. Our algorithm can still effectively reduce bias without partitioning.

Response to Weakness 3: We thank the reviewer for the suggestion. We have added the experiment for Cifar 10 in the appendix. Moreover, we note that the main contribution of the paper is to theoretically analyze FL under correlated client participation. Thus we acknowledge that the experimental part of the paper might not be comprehensive enough, while we note that our experimental results effectively verify our theoretical claims.

Response to Question 1: In Theorem 2, the only assumption we made is that the availability probabilities $p_i$’s are not “too far away” (characterized by $\delta$) from the uniform distribution. The reason for this assumption is due to the perturbation technique we used in the proof, which only holds for a small neighborhood around uniform distribution. We believe that some new proof technique is needed in order to remove the assumption and we hope to address it in the future.

Response to Question 2: The nice thing about a uniform $R$ across clients is that the indices of clients within every $R+1$ rounds are non-repeated, which enables us to analytically get the expression of the column sum $b_R$ of $P_R$ in Appendix D.1. Then, our proof idea relies on studying the monotonicity of $b_R$. However, if each client maintains its own $R_i$, taking $R = \max_i R_i$ no longer guarantees non-repeated indices within $R+1$ rounds, which renders much technical difficulty to analyze the monotonicity of $b_R$ in the sense that the analytical expression of $b_R$ is stochastic and unknow. Therefore, our proof fails in this case. We hope to solve this problem in our future work.

Response to Weakness 1: We thank the reviewer for pointing out the presentation issue. We defined $\tau_{mix}$ as the mixing time in the statement of Theorem 1 (see Line 297) and $p_e$ denotes the $e$-th client availability probability. We also made corresponding changes in our updated version.

Response to Weakness 2: We acknowledge the weakness and we provided discussions in Section 7. As stated in Section 7, the limitations are technical difficulties of our analysis. This paper serves as a first step towards analysis of federated learning under correlated client participation. We would like to look for more advanced mathematical tools to solve them in the future.

Response to Question 1: In our analysis, we just applied local gradient descent in the local updates for simplicity. And our analysis can be easily extended to local SGD. In such case, we can similarly bound $\Vert x_{t+1} - x_t \Vert^2$ as in Lemma 7 by introducing bounded variance of stochastic gradient for each client (which is a standard assumption in stochastic optimization analysis). Then, all the following analysis goes through as well, while the final convergence bounds additionally depend on the variance of the stochastic gradient. Moreover, we highlight that in the experiment, we did use local SGD during local updates, and the results verify our theoretical demonstration.

Response to Question 2: We thank the reviewer for the suggestion. We have added the proof of Proposition 1 in our updated Appendix C for clarity.