Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling
Feng Zhu, Robert W. Heath Jr, Aritra Mitra · 2025
Read Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling by Feng Zhu, Robert W. Heath Jr, Aritra Mitra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-11645.txt.
Introduction
Feng Zhu, Robert Heath, and Aritra Mitra (2025) prove that a team of learning agents can solve a shared problem faster together. Their data arrive in correlated streams, which makes the task harder. The setting is federated stochastic approximation: each agent holds its own operator, and the group seeks the root of their average. Each agent's samples follow a Markov chain, so they are not independent. The agents' own roots also differ. Earlier work stumbled on these points.
Their algorithm, FedHSA, lets agents take several local steps between talks with the server. It needs no projection step to keep values bounded. The proof shows the group reaches the true root. Collaboration buys an M-fold speedup in samples, where M is the number of agents. The authors note the result covers federated reinforcement learning tasks such as policy evaluation, where each agent's world can differ in rewards and dynamics.
Catalog record
| CREATOR | Feng Zhu, Robert W. Heath Jr, Aritra Mitra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 142 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11645
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling Feng Zhu, Robert W. Heath Jr, Aritra Mitra Abstract Motivated by collaborative reinforcement learning (RL) and optimization with time-correlated data, we study a generic federated stochastic approximation problem involving M M agents, where each agent is characterized by an agent-specific (potentially nonlinear) local operator. The goal is for the agents to communicate intermittently via a server to find the root of the average of the agents’ local operators. The generality of our setting stems from allowing for (i) Markovian data at each agent and (ii) heterogeneity in the roots of the agents’ local operators. The limited recent work that has accounted for both these features in a federated setting fails to guarantee convergence to the desired point or to show any benefit of collaboration; furthermore, they rely on projection steps in their algorithms to guarantee bounded iterates. Our work overcomes each of these limitations. We develop a novel algorithm titled FedHSA , and prove that it guarantees convergence to the correct point, while enjoying an M M -fold linear speedup in sample-complexity due to collaboration. To our knowledge, this is the first finite-time result of its kind , and establishing it (without relying on a projection step) entails a fairly intricate argument that accounts for the interplay between complex temporal correlations due to Markovian sampling, multiple local steps to save communication, and the drift-effects induced by heterogeneous local operators. Our results have implications for a broad class of heterogeneous federated RL problems (e.g., policy evaluation and control) with function approximation, where the agents’ Markov decision processes can differ in their probability transition kernels and reward functions. 1 Introduction In the classical stochastic approximation (SA) formulation [ 1 , 2 , 3 , 4 ] , the goal is to solve for a parameter \theta^{\star}\in\mathbb{R}^{d} such that \bar{G}(\theta^{\star})=0 , where \bar{G}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d} is a potentially nonlinear operator satisfying \bar{G}(\cdot)=\mathbb{E}_{o\sim\mu}\left[G(\cdot,o)\right] . Here, G:\mathbb{R}^{d}\times\mathcal{X}\rightarrow\mathbb{R}^{d} is the noisy version of the true operator \bar{G} , and o is an observation random variable drawn with some unknown distribution \mu from a sample space \mathcal{X} . The agent (learner) tasked with finding \theta^{\star} only has access to the operator \bar{G} via noisy samples \{G(\cdot,o_{t})\} , where \{o_{t}\} is a stochastic observation process that is typically assumed to converge in distribution to \mu [ 2 ] . Interestingly, the SA formulation described above captures a large class of problems arising in stochastic optimization, control, and reinforcement learning (RL). For instance, popular iterative algorithms like stochastic gradient descent (SGD) in optimization, and temporal difference (TD) learning, Q-learning in RL turn out to be specific instances of SA. Federated learning (FL) has also made extensive use of SA. The general idea of FL is to leverage data collected from multiple agents to train accurate statistical models for downstream prediction [ 5 , 6 , 7 ] . SA has primarily been used in FL to solve stochastic optimization problems that arise in the context of empirical risk minimization (ERM), under assumptions like offline data collection and i.i.d. (independent and identically distributed) data at each agent. In contrast, when the data arrives sequentially and exhibits strong temporal correlations - as is the case in multi-agent/federated RL - very little is understood about non-asymptotic/finite-time performance. This is particularly the case when the agents’ data-generating processes are potentially non-identical. In our paper, we develop convergence and sample-complexity results for a general class of federated SA methods that significantly improve upon existing bounds, and provide a deeper understanding of the interplay between data-heterogeneity and temporal correlations in FL . Our Federated SA Setup. We aim to develop a unified framework that can accommodate a broad class of distributed SA problems. To that end, we consider a setup involving M agents that can exchange information via a central server, as is typical in an FL setting. Each agent i\in[M] has its own true and noisy operators \bar{G}_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d} and G_{i}:\mathbb{R}^{d}\times\mathcal{X}_{i}\rightarrow\mathbb{R}^{d} , respectively, where \bar{G}_{i}(\cdot)=\mathbb{E}_{o\sim\mu_{i}}\left[G_{i}(\cdot,o)\right] . Here, \mathcal{X}_{i} is the sample space of agent i , and the observation random variable o is drawn from an agent-specific unknown distribution \mu_{i} . The information available locally at an agent i comprises a sequence of noisy samples \{G_{i}(\cdot,o_{i,t})\}. To capture temporal correlations, we assume that the the observation sequence \{o_{i,t}\} is generated from an ergodic Markov chain \mathcal{M}_{i} with stationary distribution \mu_{i} . Given this setup, the collective objective is to find the root \theta^{\star}\in\mathbb{R}^{d} of the “average” operator \bar{G} ; this objective can be succinctly stated as \boxed{\text{Find}\ \theta^{\star}\,\text{s.t.}\ \bar{G}(\theta^{\star})=0,\text{where}\ \bar{G}:=\frac{1}{M}\sum_{i=1}^{M}\bar{G}_{i}.} (1) Note that to achieve the above objective, communication via the server is necessary . In a typical FL scenario, communication takes place over low-bandwidth channels, and can hence be costly and slow. To mitigate the communication bottleneck, we will adhere to the standard intermittent communication protocol in FL, where an exchange of information with the server takes places only once in every H>1 time-steps, where H is some predefined synchronization time-period. To summarize, there are three main features in our formulation: (1) Heterogeneity: The local operators \{\bar{G}_{i}\} at the agents can be non-identical and, as such, have different roots; (2) Markovian Sampling: The agents’ observation sequences are generated in a Markovian manner; and (3) Sparse Communication: Agents need to perform local computations in isolation between communication rounds. Additionally, complying with the FL paradigm, the agents are required to solve the problem in ( 1 ) without ever exchanging their raw observations. 1.1 Motivation and Related Work When one considers the challenging setting involving all of the above features, there are significant gaps in the understanding of the problem in Eq. ( 1 ). We now explain these gaps by considering several motivating applications of ( 1 ). Along the way, we also review relevant literature. 1. Motivation 1: Federated Optimization in Dynamic Environments. \circ I.I.D. Data. When \bar{G}_{i} is the gradient of a local loss function at agent i , and G_{i} a noisy stochastic version thereof, the problem in Eq. ( 1 ) reduces to the standard FL setting that has been extensively studied under the assumption that the observation process \{o_{i,t}\} at each agent i is generated in an i.i.d. manner from \mu_{i} [ 7 ] . Under this i.i.d. data regime, a large body of work has studied the heterogeneous federated optimization problem [ 8 , 9 , 10 , 11 , 12 , 13 ] . \circ Markovian Data. Our formulation substantially generalizes the standard FL setting by allowing the observation process at each agent i to be generated from an ergodic Markov chain that converges in distribution to \mu_{i} . As explained in detail in [ 14 ] and [ 15 ] , there is ample reason to consider such Markovian data streams. Moreover, temporally correlated Markovian data arises naturally in several real-world applications: dynamic environments such as non-stationary wireless systems where the channel statistics drift over time following Gauss-Markovian processes, linear dynamical systems in control with input noise, and distributed sensor networks with correlated measurements. With these reasons in mind, considerable recent attention has been given to the study of Markovian gradient descent in the single-agent setting [ 14 , 16 , 17 , 18 ] . Research