mlsanityData to 7 Oct 2026

SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning

arXiv 2402.04114 ↗First posted 6 Feb 2024stat.ML cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

In this paper, we analyze the sample and communication complexity of the federated linear stochastic approximation (FedLSA) algorithm. We explicitly quantify the effects of local training with agent heterogeneity. We show that the communication complexity of FedLSA scales polynomially with the inverse of the desired accuracy ε. To overcome this, we propose SCAFFLSA a new variant of FedLSA that uses control variates to correct for client drift, and establish its sample and communication complexities. We show that for statistically heterogeneous agents, its communication complexity scales logarithmically with the desired accuracy, similar to Scaffnew. An important finding is that, compared to the existing results for Scaffnew, the sample complexity scales with the inverse of the number of agents, a property referred to as linear speed-up. Achieving this linear speed-up requires completely new theoretical arguments. We apply the proposed method to federated temporal difference learning with linear function approximation and analyze the corresponding complexity improvements.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 33 of its 55 references that are in the map. First posted on arXiv 6 Feb 2024.

Builds on

33 of 55 references.

References · 33

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  3. 2018Federated Learning with Non-IID Datacited by 1,099
  4. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  5. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  6. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  7. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  8. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  9. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  10. 2022ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!cited by 134
  11. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  12. 2020Local SGD: Unified Theory and New Efficient Methodscited by 88
21 more
  1. 2021Federated Reinforcement Learning: Techniques, Applications, and Open Challengescited by 79
  2. 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 65
  3. 2022Federated Reinforcement Learning with Environment Heterogeneitycited by 61
  4. 2020Least Squares Regression with Markovian Data: Fundamental Limits and Algorithmscited by 56
  5. 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
  6. 2022On the Unreasonable Effectiveness of Federated Averaging with Heterogeneous Datacited by 36
  7. 2022Variance Reduced ProxSkip: Algorithm, Theory and Application to Federated Learningcited by 33
  8. 2022FedKL: Tackling Data Heterogeneity in Federated Reinforcement Learning by Penalizing KL Divergencecited by 29
  9. 2022RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updatescited by 27
  10. 2021Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsizecited by 26
  11. 2023Federated Temporal Difference Learning with Linear Function Approximation under Environmental Heterogeneitycited by 25
  12. 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
  13. 2022Can 5th Generation Local Training Methods Support Client Sampling? Yes!cited by 22
  14. 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
  15. 2021Accelerated and instance-optimal policy evaluation with linear function approximationcited by 18
  16. 2023High-probability sample complexities for policy evaluation with linear function approximationcited by 16
  17. 2023Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Samplingcited by 14
  18. 2013Off-policy Learning with Eligibility Traces: A Surveycited by 12
  19. 2022CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimizationcited by 11
  20. 2023Distributed TD(0) with Almost No Communicationcited by 11
  21. 2020Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithmscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 1.

6 papers.

  1. 2025SciPostGen: Bridging the Gap between Scientific Papers and Poster Layoutscited by 4
  2. 2025Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agentscited by 2
  3. 2025Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Samplingcited by 1
  4. 2025Personalized Collaborative Learning with Affinity-Based Variance Reductioncited by 1
  5. 2024Refined Analysis of Federated Averaging and Federated Richardson-Rombergcited by 0
  6. 2026High-Probability Convergence of SGD via Batched Updatescited by 0