Streaming Federated Learning with Markovian Data
Tan-Khiem Huynh, Malcolm Egan, Giovanni Neglia, Jean-Marie Gorce · 2025
Read Streaming Federated Learning with Markovian Data by Tan-Khiem Huynh, Malcolm Egan, Giovanni Neglia, Jean-Marie Gorce (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-2503-18807.txt.
Introduction
Tan-Khiem Huynh, Malcolm Egan, Giovanni Neglia, and Jean-Marie Gorce study federated learning on streaming data in this 2025 paper. In federated learning, clients train a shared model on their own data and send updates, not raw records. Most theory assumes each client holds a fixed, pre-collected dataset.
Many real clients instead gather data as a stream from a physical or living process, where each new sample depends on earlier ones, a Markov pattern. The authors ask whether joint learning still works then. Analyzing three training methods, they answer yes under standard assumptions. The data needed per client falls as clients are added. Communication costs match the independent data case, though streaming still needs more samples overall.
Catalog record
| CREATOR | Tan-Khiem Huynh, Malcolm Egan, Giovanni Neglia, Jean-Marie Gorce |
|---|---|
| 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/2503-18807
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Streaming Federated Learning with Markovian Data Tan-Khiem Huynh, Malcolm Egan, Giovanni Neglia, Jean-Marie Gorce Abstract Federated learning (FL) is now recognized as a key framework for communication-efficient collaborative learning. Most theoretical and empirical studies, however, rely on the assumption that clients have access to pre-collected data sets, with limited investigation into scenarios where clients continuously collect data. In many real-world applications, particularly when data is generated by physical or biological processes, client data streams are often modeled by non-stationary Markov processes. Unlike standard i.i.d. sampling, the performance of FL with Markovian data streams remains poorly understood due to the statistical dependencies between client samples over time. In this paper, we investigate whether FL can still support collaborative learning with Markovian data streams. Specifically, we analyze the performance of Minibatch SGD, Local SGD, and a variant of Local SGD with momentum. We answer affirmatively under standard assumptions and smooth non-convex client objectives: the sample complexity is proportional to the inverse of the number of clients, with a communication complexity comparable to the i.i.d. scenario. However, the sample complexity for Markovian data streams remains higher than for i.i.d. sampling. Our analysis is validated via experiments with real pollution monitoring time series data. 1 Introduction As edge networks grow in scale, clients are increasingly diverse [ 34 ] . Many of these clients are capable of continuously collecting and learning from data, instead of simply storing large quantities of historical data [ 28 ] . This streaming data arises in applications ranging from health [ 21 , 22 ] and environmental monitoring [ 24 ] , to control of robots [ 29 ] . Each data stream provides detailed information about individual clients. However, applications such as environmental resource management [ 54 ] or public health monitoring [ 6 ] often aim to derive population-level insights, leveraging data streams from multiple individuals to learn a global model. As this data may be sensitive or costly to communicate, centralized training solutions are undesirable. Federated Learning (FL) has emerged as a key strategy for communication-efficient collaborative learning [ 26 ] . In conventional FL scenarios, clients have access to local datasets used to train models locally. These models are then transmitted to a central server, where aggregation facilitates collaborative learning. FL minimizes communication overhead while learning models with high accuracy and ensuring client data are not shared. Clients with streaming data must also cope with memory constraints [ 38 , 35 ] . This means that clients have limited control over data sampling: local updates can only be computed using the current data samples stored in memory. Moreover, data in health and environmental monitoring applications is often generated by non-linear physical and biological systems. The data generated by these systems is frequently modeled as non-stationary Markovian data streams [ 1 , 58 ] . When client memory caches are continually refreshed by Markovian streaming data, the samples available to compute updates are statistically dependent and non-stationary in time . In this paper, we address the following question: Can FL with Markovian data streams support collaborative learning? While Markovian sampling has been explored in the centralized setting [ 17 ] , existing work in the federated setting has focused on Federated Reinforcement Learning [ 45 , 28 , 37 ] with convex objectives. However, classification and regression tasks in systems with non-linear dynamics often rely on deep neural networks or non-convex regularization [ 63 , 36 ] , resulting in non-convex minimization problems during training. We therefore consider a family of training tasks beyond the work in [ 45 , 28 , 37 ] characterized by smooth non-convex loss functions . Our main contributions can be summarized as follows: (i) Impact of Markovian sampling: We rigorously characterize the impact of Markovian sampling on the convergence rate of Minibatch and Local Stochastic Gradient Descent (SGD), the two most common baselines in FL. A key conclusion is that linear speed-up is achieved under standard assumptions on the objectives and heterogeneity: the sample complexity is proportional to the inverse of the number of clients. (ii) Mitigating client heterogeneity: We show that a momentum-based variant of Local SGD introduced in the i.i.d. setting [ 9 , 61 ] can effectively mitigate the client drift with Markovian data streams. In particular, unlike Local SGD, Local SGD with Momentum matches the performance of Minibatch SGD up to a constant without requiring any bound on client data heterogeneity. (iii) Validation on Environmental Monitoring Data: The key difference between i.i.d. and Markovian sampling is statistical dependence between consecutive samples. We validate our analysis using multi-site pollution time series data [ 7 ] , which shows the benefit of collaboration on real data with dependent samples. 2 Related Works Edge devices often encounter the challenge of processing continuous data streams while operating under memory constraints [ 38 , 35 ] . Learning from streaming data presents numerous challenges, with solutions dependent on the data-generating process. One line of research addresses scenarios where the data distribution evolves over time, with continual learning methods designed to adapt the model to the changing data distribution [ 51 ] . Another line focuses on adversarial settings, where the data stream is generated by an adversary [ 53 ] , often addressed using online learning algorithms with regret guarantees. In this paper, we focus on learning from data generated by Markovian processes. Markovian processes have been successfully applied to model various physical and biological systems [ 1 , 58 ] , and encompass the special case where data samples are drawn i.i.d. from an unknown distribution. In the centralized setting, this learning problem can be framed as a stochastic approximation problem, typically addressed by variants of stochastic gradient descent (SGD). While SGD with i.i.d. data is well-understood [ 47 , 31 ] , the Markovian nature of the data stream introduces challenges due to the temporal correlation between samples. For uniformly ergodic Markov chains, [ 16 ] first demonstrated that mirror descent achieves optimal convergence rates for Lipschitz, general convex, and non-convex problems. Recently, [ 15 ] proposed a random batch size algorithm that adapts to the mixing time of the Markov chain, while [ 3 ] adopted the same technique to develop accelerated methods and established lower bounds for strongly convex objectives. For general Markov chains, existing analysis of SGD-type algorithms [ 55 , 14 , 13 ] have shown sub-optimal dependence on the mixing time and on the variance of stochastic gradient estimates relative to the lower bounds in [ 3 , 16 ] . We refer to [ 3 , Table 1] for an exhaustive review of the literature on SGD with Markovian noise. In the case of SGD with Markovian noise on a finite state space—a common scenario in distributed optimization [ 4 ] — [ 17 , 23 ] developed convergence theories and variance reduction techniques for first-order methods, demonstrating improvements over the gossip algorithm [ 5 ] . In the context of FL, a few papers have considered learning from data streams. [ 41 ] and [ 62 ] framed the problem in an adversarial and in a continual learning setting, respectively. [ 8 ] imposed strong homogeneity assumptions, such as requiring all clients