On the Generalization Gap of Streaming Federated Learning with Markovian Data
Abstract
Streaming federated learning (SFL) allows clients to train a shared model from continuously arriving data without retaining large local datasets. Such streams often exhibit temporal dependence, yet its effect on generalization remains poorly understood. In this paper we study the expected generalization gap of the aggregated model when client data follow Markov processes, using information-theoretic and rate-distortion techniques. Our framework accommodates heterogeneous Markovian dynamics across clients and distinguishes temporal dependence from information acquired during local learning. We establish bounds under cross-entropy loss, specializing them to Linear Next-Token Prediction (LNTP) and Self-Attention Next-Token Prediction (SANTP). These results quantify the effects of client count, communication rounds, sample size, data dimension, mixing time, and context length. In particular, they reveal a communication--generalization tradeoff: although frequent aggregation may help optimization, it can weaken generalization guarantees. They also suggest a potential advantage of distributed over centralized streaming learning under a fixed total data budget. Temporal dependence enters through the square root of the mixing time. By analyzing the history-state process, we obtain refined bounds with improved context-length dependence under suitable mixing conditions. Experiments on GPT-style language-model pretraining with TinyStories and real-world time-series forecasting illustrate how collaboration and communication frequency influence generalization under temporal dependence
Related
- Progressive-Resolution Secure Aggregation for Federated Learning
- Personalized Federated Learning through Global Knowledge Distillation and Local Head Adaptation
- Geographically Regularized AUC-Maximizing Personalized Federated Learning
- Learning to Refer: Inference-Time Collaboration in Decentralized Federated Learning
- A Large-Dimensional Analysis of Least-Squares Federated Learning via Generalized Total Variation Minimization
BibTeX
@misc{kavian2026generalization,
title = {{On the Generalization Gap of Streaming Federated Learning with Markovian Data}},
author = {Masoud Kavian and Milad Sefidgaran and Youssef Attia El Hili and Malik Tiomoko and Abdellatif Zaidi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38686},
eprint = {2610.38686},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38686},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the Generalization Gap of Streaming Federated Learning with Markovian Data
AU - Masoud Kavian
AU - Milad Sefidgaran
AU - Youssef Attia El Hili
AU - Malik Tiomoko
AU - Abdellatif Zaidi
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38686
UR - https://arxiv.org/abs/2610.38686
AB - Streaming federated learning (SFL) allows clients to train a shared model from continuously arriving data without retaining large local datasets. Such streams often exhibit temporal dependence, yet its effect on generalization remains poorly understood. In this paper we study the expected generalization gap of the aggregated model when client data follow Markov processes, using information-theoretic and rate-distortion techniques. Our framework accommodates heterogeneous Markovian dynamics across clients and distinguishes temporal dependence from information acquired during local learning. We establish bounds under cross-entropy loss, specializing them to Linear Next-Token Prediction (LNTP) and Self-Attention Next-Token Prediction (SANTP). These results quantify the effects of client count, communication rounds, sample size, data dimension, mixing time, and context length. In particular, they reveal a communication--generalization tradeoff: although frequent aggregation may help optimization, it can weaken generalization guarantees. They also suggest a potential advantage of distributed over centralized streaming learning under a fixed total data budget. Temporal dependence enters through the square root of the mixing time. By analyzing the history-state process, we obtain refined bounds with improved context-length dependence under suitable mixing conditions. Experiments on GPT-style language-model pretraining with TinyStories and real-world time-series forecasting illustrate how collaboration and communication frequency influence generalization under temporal dependence
ER -