Debiasing Federated Learning with Correlated Client Participation

Authors: Zhenyu Sun, ziyang zhang, Zheng Xu, Gauri Joshi, Pranay Sharma, Ermin Wei
Primary area: optimization
Keywords: federated learning, Markov chain, time-correlated participation

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

Decision: accept (poster)
Reviewer scores: 8, 8, 6, 5

Reviews and discussion:
<thread>
creation date:
1729955894777

thread_type:
official_review

<thread_object>
creator: reviewer_ehnb

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

strengths:
- Motivation: the minimum separation in federated learning is reasonable to analyze.
- Literature review is thorough.

weaknesses:
- The FL setting is not rigorous. In line 121, authors use $p_i$ to capture the willingness to be sampled at each iteration which means a client may not join the training for arbitrarily long amount of iterations (with small probability). However, in line 128~129, it is claimed that "the cyclic participation corresponds to the case, R = N / B − 1", which means in the last round of the cycle, all of the remaining B clients will definitely be sampled. So the setting is not consistent. Besides, forcing clients to join cross-device federated learning is not practical.

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

questions:
Are Markov-chain model really necessary to analyze this problem?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730110687693

thread_type:
official_review

<thread_object>
creator: reviewer_cr1n

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

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.

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.

questions:
1. If there is extreme heterogeneity among clients, how might a larger minimum separation $R$ impact the model's performance?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730699796548

thread_type:
official_review

<thread_object>
creator: reviewer_yi23

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

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.

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

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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731353191870

thread_type:
official_review

<thread_object>
creator: reviewer_gyum

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

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.

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.

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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731982326354

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General response to all reviewers

comment:
We appreciate all valuable comments and suggestions provided by the reviewers. We have fully addressed all the concerns and made corresponding editions (in red) in the updated manuscript. We are eager to discuss with the reviewers for any further comment.
</content>
</thread_object>

</thread>


Metareview:
metareview:
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.