Research map / Federated learning and privacy / Communication-efficient FL
SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning
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.
Analyzes sample and communication complexity of federated linear stochastic approximation (FedLSA) with local training and proposes SCAFFLSA, which uses control variates to get logarithmic communication complexity while keeping linear speed-up, applied to federated TD(0).
Problem
Federated linear stochastic approximation with heterogeneous agents and local training suffers from client-drift bias and high communication cost, and existing control-variate methods lose linear speed-up in the number of agents.
Approach
Derives an exact bias characterization for FedLSA and proposes SCAFFLSA, which corrects client drift with control variates (Scaffnew-style) and uses a virtual-iterate analysis tracking parameter and control-variate fluctuations to retain linear speed-up while making communication scale logarithmically in 1/epsilon.
Key results
- SCAFFLSA eliminates the FedLSA heterogeneity bias in the heterogeneous Garnet setting, improving MSE until noise dominates.
- Theory: SCAFFLSA communication complexity scales as log(1/epsilon) versus polynomial 1/epsilon for FedLSA, with sample complexity preserving linear speed-up in the number of agents N.
- Numerical experiments show both FedLSA and SCAFFLSA exhibit linear speed-up in the number of agents for homogeneous settings and for heterogeneous settings with SCAFFLSA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add control variates to correct client drift | FedLSA · Federated LSA, i.i.d. samples | communication complexity: \mathcal{O}\left({\tfrac{1}{ a^2 \epsilon}} \log{\tfrac{1}{\epsilon}} \right) -> \mathcal{O}\left( \tfrac{1}{a^2} \log \ | Helped |
| add control variates to correct client drift | FedLSA · Federated LSA, i.i.d. samples | sample complexity: \mathcal{O}\bigl(\tfrac{1}{ N a^2 \epsilon^2} \log{\tfrac{1}{\epsilon}}\bigr) -> \mathcal{O}\bigl(\tfrac{1}{ N a^2 \epsi | No clear effect |
| add control variates to correct client drift | FedLSA · Federated TD(0), heterogeneous agents | communication complexity: T = \mathcal{O} \left(\left(\tfrac{1}{(1-\gamma)^{2} \nu} \vee {\tfrac{\mathbb{E}_c[\norm{\theta_\star^c - \theta_\star} | Helped |
| increase the number of local updates under heterogeneous agents | FedLSA · Federated TD(0), heterogeneous Garnet environments | MSE | Hurt |
| add control variates to correct client drift | FedLSA · Federated TD(0), heterogeneous Garnet environments | MSE | Helped |
| add control variates to correct client drift | FedLSA · Federated TD(0), homogeneous Garnet environments | MSE | No clear effect |
| add control variates to correct client drift | FedLSA · Federated TD(0), heterogeneous agents with many local updates | linear speed-up with number of agents: N = 1 to 1000 | Helped |
Surprising findings
- FedLSA loses linear speed-up when agents are heterogeneous and the number of local updates is large, due to bias.
Limitations
- FedLSA bias grows with local steps under heterogeneity, requiring small H.
- Markovian analysis is stated for FedLSA with skipped observations and extended to SCAFFLSA only as a remark.
Experimental setup
Datasets: Garnet MDP synthetic environments
Benchmarks: Garnet federated TD(0) problems
Metrics: mean squared error communication rounds bias
Baselines: FedLSA Scaffnew FedAvg Scaffold
Builds on: Scaffnew Scaffold FedAvg FedLSA
Closest papers by meaning
- Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up (ICML 2025 · similarity 0.89)
- Finite-Time Analysis of On-Policy Heterogeneous Federated Reinforcement Learning (ICLR 2024 · similarity 0.88)
- Decentralized Sporadic Federated Learning: A Unified Algorithmic Framework with Convergence Guarantees (ICLR 2025 · similarity 0.87)
- Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis (NeurIPS 2024 · similarity 0.87)
- Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.87)
- FedSMU: Communication-Efficient and Generalization-Enhanced Federated Learning through Symbolic Model Updates (ICML 2025 · similarity 0.86)
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.