On the Generalization Gap of Streaming Federated Learning with Markovian Data
Authors: Masoud Kavian, Milad Sefidgaran, Youssef Attia El Hili, Malik Tiomoko, Abdellatif Zaidi
Organizations: Huawei Paris Research Center, Huawei Technologies Ltd., France · Huawei Noah’s Ark Lab, Paris, France · Université Gustave Eiffel, France
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
Figures & tables
Figure 1: Evolution of the bound of Theorem 8 versus R , for N=100,T=10,ρ=4,τk,min=2,qe,b=1,C=1,d=8,θ=5 .
Figure 2: Communication–generalization tradeoff in TinyStories pretraining. Train loss (left), test loss (middle), and generalization gap (right) versus rounds R for K∈{2,4,8} clients. Per-client gradient-step budget is fixed across settings and evenly allocated across rounds: only communication frequency varies. Curves show seed averages, with shaded bands denoting standard deviation across three seeds.
Figure 3: Communication–generalization tradeoff in ETTh2 forecasting. Train loss (left), test loss (middle), and generalization gap (right) as functions of rounds count R , for K∈{2,4,8} clients. As in Figure 2 . Curves show the mean across seeds and shaded bands indicate standard deviation across three seeds.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: Communication–generalization tradeoff: ETTh1 Dataset. Consistent with ETTh2, increasing communication rounds R leads to lower training loss but a significantly wider generalization gap across all client configurations K . Shaded regions indicate standard deviation across three seeds.
Figure 5: Communication–generalization tradeoff: Beijing Dataset. The same phenomenon is observed in environmental time series (PM2.5 levels), confirming that the tradeoff is a robust feature of streaming federated learning on dependent data. Shaded regions indicate standard deviation across five seeds.
We study expected generalization bounds for the Hierarchical Federated Learning (HFL) setup using Wasserstein distance. We introduce a generalized framework in which data is sampled hierarchically, and we model it with a multi-layered tree structure that induces dependencies among the clients' datasets. We derive generalization bounds in terms of Wasserstein distance under the Lipschitz assumption on the loss function, by applying a supersample construction that allows us to measure the sensitivity of the algorithm to the change of a single node in the sampling tree. By leveraging the FL structure, we recover and strictly imply existing state-of-the-art conditional mutual information (CMI) bounds in the case of bounded losses. We also show that our bound can be applied together with Differential Privacy assumptions, to recover generalization bounds based on algorithmic privacy. To assess the tightness of our bounds, we study the Gaussian Location Model (GLM) and show that we recover the actual asymptotic rate of the generalization error.
Dario Filatrella, Ragnar Thobaben, Mikael Skoglund
Department of Information Science and Engineering Royal Institute of Technology Stockholm, Sweden
Federated learning (FL) is a distributed paradigm that coordinates massive local clients to collaboratively train a global model via stage-wise local training processes on the heterogeneous dataset. Previous works have implicitly studied that FL suffers from the client-drift'' problem, which is caused by the inconsistent optimum across local clients. However, till now it still lacks solid theoretical analysis to explain the impact of this local inconsistency. To alleviate the negative impact of client drift'' and explore its substance in FL, in this paper, we first propose an efficient FL algorithm FedInit, which allows employing the personalized relaxed initialization state at the beginning of each local training stage. Specifically, FedInit initializes the local state by moving away from the current global state towards the reverse direction of the latest local state. Moreover, to further understand how inconsistency disrupts performance in FL, we introduce the excess risk analysis and study the divergence term to investigate the test error in FL. Our studies show that optimization error is not sensitive to this local inconsistency, while it mainly affects the generalization error bound. Extensive experiments are conducted to validate its efficiency. The proposed FedInit method could achieve comparable results compared to several advanced benchmarks without any additional training or communication costs. Meanwhile, the stage-wise personalized relaxed initialization could also be incorporated into several current advanced algorithms to achieve higher generalization performance in the FL paradigm.
Li Shen, Yan Sun, Dacheng Tao
School of Cyber Science and Technology, Shenzhen Campus of Sun Yat-sen University · School of Computer Science, Faculty of Engineering, The University of Sydney · Generative AI Lab, College of Computing and Data Science, Nanyang Technological University
Federated learning (FL) is a communication-efficient distributed learning paradigm. However, client drift remains one of the most critical challenges, hindering the efficient training of a global model. In this study, we propose a novel latent information sharing scheme that directly mitigates data heterogeneity across clients. Our theoretical and empirical results show that sharing a small amount of hidden-layer activations significantly improves training efficiency while preserving convergence guarantees and data privacy. Furthermore, we compare our method with existing FL approaches designed to address client drift, including FedProx, SCAFFOLD, FedPVR, FedProto, and SplitFed, and demonstrate superior model accuracy under a fixed round budget without incurring excessive communication overhead. Overall, this work presents a promising new knowledge aggregation scheme and provides a comprehensive analysis of the impact of activation sharing on federated optimization.