Research map / Federated learning and privacy / Communication-efficient FL
Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable
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.
Proposes FedOSP (Federated Optimization with Exact Convergence via Push-pull Strategy), reformulating FL client sampling and local updates as time-varying stochastic-matrix graphs and adapting push-pull gradient tracking to get exact linear convergence under arbitrary client participation without decaying learning rates.
Problem
FedAvg-style algorithms under arbitrary (non-uniform, unknown) client participation and data heterogeneity with multiple local updates do not converge exactly with a constant learning rate, and decaying learning rates slow convergence.
Approach
Models client participation and local updates as time-varying row/column stochastic matrices and adapts the push-pull primal-dual decentralized algorithm to FL (pull model, push gradient-tracking variables via column-stochastic matrix), yielding exact linear convergence without knowing participation probabilities or bounded heterogeneity.
Key results
- On synthetic ridge regression (d=100, N=16, tau=5, lr=2e-4), FedOSP shows linear convergence to the exact optimum under full, uniform, and arbitrary participation, while FedAvg and FedAU fail to converge exactly.
- Theory: strongly convex linear rate (1-eta*mu*N/2)^R and PL linear rate (1-eta*beta*N)^R with learning rate bounds depending on q_min; general nonconvex rate O(1/R) without bounded heterogeneity.
- Stochastic variant FedOSP-SG is reported to converge faster and with higher accuracy than other FL baselines on CIFAR-10 (per the paper's appendix claims).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use FedASL's push-pull strategy instead of FedAvg | Federated learning under arbitrary client participation · Strongly-convex setting | iteration complexity: O(\frac{1}{\epsilon}) -> O\big(\log(\frac{1}{\epsilon})\big) | Helped |
| Use FedASL's push-pull strategy instead of FedAvg | Federated learning under arbitrary client participation · Non-convex setting with PL condition | iteration complexity: O(\frac{1}{\epsilon^2}) -> O\big(\log(\frac{1}{\epsilon})\big) | Helped |
| Use FedASL instead of FedAvg with a fixed learning rate | Synthetic ridge regression · Arbitrary participation | convergence to the optimal solution | Helped |
| Use FedASL instead of SCAFFOLD | Synthetic ridge regression · Arbitrary participation | convergence speed | Helped |
| Use FedASL instead of ProxSkip | Synthetic ridge regression · Uniform and arbitrary participation | convergence | Helped |
| Use the stochastic-gradient variant FedASLG instead of other FL algorithms | CIFAR-10 classification · CIFAR-10 | accuracy | Helped |
Surprising findings
- The paper reports that SCAFFOLD and MIFA behave unexpectedly in its experiments, with MIFA diverging in the ridge regression setting despite working in ML applications.
- Standard linear speedup in the number of clients is not reflected in the exact (deterministic) variant's nonconvex bound, since stability forces eta=O(1/N).
Limitations
- Analysis assumes independent (non-Markov) client participation; correlated Markov participation is left to future work.
- Main theory covers deterministic gradients; the stochastic variant's guarantees carry a variance residual rather than exact convergence.
- Requires each client to have non-zero participation probability and smoothness/strong convexity or PL assumptions.
Experimental setup
Datasets: synthetic ridge regression data CIFAR-10
Benchmarks: synthetic ridge regression CIFAR-10
Metrics: distance to optimum loss convergence accuracy
Baselines: FedAvg FedAU FedAWE SCAFFOLD ProxSkip MIFA LocalSGD
Builds on: push-pull algorithm FedAvg SCAFFOLD decentralized gradient descent
Closest papers by meaning
- Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis (NeurIPS 2024 · similarity 0.92)
- Efficient Federated Learning against Heterogeneous and Non-stationary Client Unavailability (NeurIPS 2024 · similarity 0.91)
- Momentum Benefits Non-iid Federated Learning Simply and Provably (ICLR 2024 · similarity 0.90)
- A New Theoretical Perspective on Data Heterogeneity in Federated Optimization (ICML 2024 · similarity 0.90)
- Communication-Efficient Federated Learning with Accelerated Client Gradient (CVPR 2024 · similarity 0.89)
- Understanding Server-Assisted Federated Learning in the Presence of Incomplete Client Participation (ICML 2024 · similarity 0.89)
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.