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

2024-02-06 · Paul Mangold, Sergey Samsonov, Safwan Labbi, Ilya Levin, REDA ALAMI, Alexey Naumov, Eric Moulines

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 $\epsilon$. 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.

📄 PDF Abstract BibTeX arXiv:2402.04114

Code (0)

등록된 구현이 없습니다.

Is Heterogeneity Notorious? Taming Heterogeneity to Handle Test-Time Shift in Federated Learning

2023-09-21 · NeurIPS 2023 11

Federated learning (FL) is an effective machine learning paradigm where multiple clients can train models based on heterogeneous data in a decentralized manner without accessing their private data. However, existing FL s…

Gaussian Approximation and Multiplier Bootstrap for Federated Linear Stochastic Approximation

2026-05-19 · Ilya Levin, Maksim Shuklin, Eric Moulines, Paul Mangold 외 arxiv

In this paper, we establish Berry-Esseen-type bounds for federated linear stochastic approximation (LSA). Our results provide the first federated Gaussian approximations for LSA that explicitly capture communication-comp…

RELTA-SGLD: Relative-Growth Localized Taming for Nonconvex Stochastic-Gradient Langevin Learning

2026-07-21 · Yiwei Zhou, Ziheng Chen arxiv

We introduce RELTA-SGLD, a taming scheme that stabilizes superlinear stochastic-gradient updates while reducing unnecessary suppression of the original learning drift. A threshold determines where the taming turns on, wh…

Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning

2022-06-21 · Sajad Khodadadian, Pranay Sharma, Gauri Joshi, Siva Theja Maguluri

Since reinforcement learning algorithms are notoriously data-intensive, the task of sampling observations from the environment is usually split across multiple agents. However, transferring these observations from the ag…

Q-Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

HeteroSwitch: Characterizing and Taming System-Induced Data Heterogeneity in Federated Learning

2024-03-07 · Gyudong Kim, Mehdi Ghasemi, Soroush Heidari, Seungryong Kim 외

Federated Learning (FL) is a practical approach to train deep learning models collaboratively across user-end devices, protecting user privacy by retaining raw data on-device. In FL, participating user-end devices are hi…

Domain Generalization Fairness Federated Learning