Research map / Federated learning and privacy / Communication-efficient FL
Debiasing Federated Learning with Correlated Client Participation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Models client participation under minimum separation R as an R-order Markov chain, shows FedAvg is biased under non-uniform correlated participation (bias shrinks as R grows), and proposes a debiased FedAvg that rescales each client's local step by an online estimate of its participation frequency.
Problem
FedAvg convergence in cross-device FL when clients have unknown, non-uniform availability and correlated participation enforced by a minimum separation R between successive participations; existing analyses assume independent uniform sampling.
Approach
Model the minimum-separation participation process as an R-order Markov chain, prove that the stationary participation distribution pi_R approaches uniform as R grows, and debias FedAvg by scaling each client's local learning rate by 1/(N * estimated participation frequency), where the frequency is estimated online via a counter per client.
Key results
- Theory: FedAvg converges with an asymptotic bias term O(||pi_R - uniform||_1^2) that vanishes as minimum separation R approaches M-1 (cyclic participation).
- Debiasing FedAvg converges to the unbiased objective for all tested R on synthetic data and MNIST, whereas vanilla FedAvg shows bias that decreases as R increases.
- Debiased FedAvg achieves O(tau_mix/sqrt(T) + 1/T) gradient-norm rate without bounded-gradient assumption, and its bound does not grow with the number of clients.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase minimum separation R | Vanilla FedAvg · Synthetic dataset | asymptotic bias | Helped |
| increase minimum separation R | Vanilla FedAvg · MNIST | asymptotic bias | Helped |
| reweight local updates using estimated client participation frequencies | FedAvg · Synthetic dataset | training objective bias | Helped |
| reweight local updates using estimated client participation frequencies | FedAvg · MNIST | objective bias | Helped |
| reweight local updates using estimated client participation frequencies | FedAvg · MNIST, R=8 | bias from client participation | Helped |
| use estimated participation-frequency weights | FedAvg under correlated client participation · arbitrary minimum separation R < M-1 | gradient norm convergence | Helped |
| use unweighted vanilla FedAvg under non-uniform correlated client participation | FedAvg · minimum separation R ≤ M-2 | asymptotic bias | Hurt |
Surprising findings
- Increasing the minimum separation R speeds up convergence of both vanilla and debiased FedAvg in the MNIST experiments, which the theory does not characterize; the authors conjecture it is due to smaller mixing time.
Limitations
- Analysis relies on aperiodicity, so the bound does not cover the cyclic case R=M-1.
- Theoretical bias-reduction result requires conditions on p_i (close to uniform, large batch size B, large N) and is stated for uniform minimum separation across clients.
- Experiments are small (N=100 clients, MNIST with three-layer MLP) and do not evaluate large-scale cross-device settings.
Experimental setup
Datasets: MNIST synthetic logistic-type regression data (following prior work)
Benchmarks: MNIST synthetic dataset
Metrics: training loss distance between pi_R and uniform distribution
Baselines: Vanilla FedAvg FedVARP
Builds on: FedAvg FedVARP Markov-sampling SGD
Closest papers by meaning
- Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis (NeurIPS 2024 · similarity 0.89)
- Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.89)
- Pursuing Overall Welfare in Federated Learning through Sequential Decision Making (ICML 2024 · similarity 0.88)
- Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participation (ICML 2024 · similarity 0.88)
- Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability (NeurIPS 2024 · similarity 0.88)
- A Lightweight Method for Tackling Unknown Participation Statistics in Federated Averaging (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.