Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimation

2023-06-02 · Davoud Ataee Tarzanagh, Mingchen Li, Pranay Sharma, Samet Oymak

Stochastic approximation with multiple coupled sequences (MSA) has found broad applications in machine learning as it encompasses a rich class of problems including bilevel optimization (BLO), multi-level compositional optimization (MCO), and reinforcement learning (specifically, actor-critic methods). However, designing provably-efficient federated algorithms for MSA has been an elusive question even for the special case of double sequence approximation (DSA). Towards this goal, we develop FedMSA which is the first federated algorithm for MSA, and establish its near-optimal communication complexity. As core novelties, (i) FedMSA enables the provable estimation of hypergradients in BLO and MCO via local client updates, which has been a notable bottleneck in prior theory, and (ii) our convergence guarantees are sensitive to the heterogeneity-level of the problem. We also incorporate momentum and variance reduction techniques to achieve further acceleration leading to near-optimal rates. Finally, we provide experiments that support our theory and demonstrate the empirical benefits of FedMSA. As an example, FedMSA enables order-of-magnitude savings in communication rounds compared to prior federated BLO schemes.

📄 PDF Abstract BibTeX arXiv:2306.01648

Code (1)

ucr-optml/fedmsa 공식 구현 pytorch

Tasks

Bilevel Optimization

Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms

2020-06-24 · Thinh T. Doan

Motivated by broad applications in reinforcement learning and federated learning, we study local stochastic approximation over a network of agents, where their goal is to find the root of an operator composed of the loca…

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

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…

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)

Federated Stochastic Gradient Langevin Dynamics

2020-04-23 · Khaoula El Mekkaoui, Diego Mesquita, Paul Blomstedt, Samuel Kaski

Stochastic gradient MCMC methods, such as stochastic gradient Langevin dynamics (SGLD), employ fast but noisy gradient estimates to enable large-scale posterior sampling. Although we can easily extend SGLD to distributed…

Federated Learning Metric Learning

Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling

2025-04-15 · Feng Zhu, Aritra Mitra, Robert W. Heath

Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving $M$ agents, where each agent is characterized by …

Reinforcement Learning (RL)