More Communication Can Widen the Generalization Gap in Streaming Federated Learning, Bounds Grow With √R
Synopsis
Streaming federated learning trains a shared model from continuously arriving client data, whose streams are often temporally dependent. For clients whose data follow Markov processes, an analysis uses information-theoretic and rate-distortion tools to bound the expected generalization gap of the aggregated model, specializing to linear and self-attention next-token prediction. The bounds show that more communication rounds loosen the guarantee at roughly √(R/N), while temporal dependence enters through the square root of the mixing time; GPT-style pretraining on TinyStories and ETTh2 forecasting both show train and test losses falling with rounds while the gap widens.
Interpretation
In streaming federated learning, more frequent server aggregation can weaken the generalization guarantee of the final aggregated model, not merely change optimization speed. Earlier federated learning analyses focused on convergence and optimization error, and the communication-generalization link had been studied only for i.i.d. data streams. In TinyStories pretraining of a GPT-style decoder with a fixed per-client gradient-step budget and only the number of rounds R varied, both train and test loss fell as R grew while the gap between them widened, for K of 2, 4 and 8; GRU next-token forecasting on the ETTh2 electricity transformer series reproduced the same picture.
Temporal dependence enters the generalization gap through the square root of the mixing time, so slowly mixing streams act like fewer effective independent samples. The i.i.d. setting has no such term, since each step supplies maximal independent information. With homogeneous mixing across clients, N trajectories of length T per client, R rounds, dictionary dimension d and context length ρ, the bounds for both linear and self-attention next-token prediction carry a √τ_min factor, where τ_min is defined from the per-client mixing times.
Under an identical total data budget, the distributed streaming bound is better than the centralized streaming bound by a factor of order √(log K/K). Setting the client count K to 1 and the per-client trajectory count to NK yields the corresponding centralized next-token prediction bound. The comparison holds for both linear and self-attention next-token prediction and compares the two bounds under the same total data budget, not measured test errors.
Analyzing the history-state process instead of individual observations can remove the explicit context-length penalty when mixing conditions are favorable. Concentration applied directly to the observation sequence puts the context length ρ into the bound as an explicit factor. The refined bound is strictly tighter whenever the history-state mixing parameter satisfies the stated inequality, and under the margin loss it removes the ρ+1 factor.
Perspective
The analysis targets streaming federated learning where client data are generated by finite-memory Markov processes and the server averages models by FedAvg, and its conclusions are upper bounds on the expected generalization gap; the experiments cover GPT-style decoder pretraining on TinyStories and next-token prediction on ETTh2, ETTh1 and Beijing multi-site air-quality data.
The authors state that an advantage in generalization gap need not translate into an advantage in population or test risk, and they report train and test errors alongside; the experiments are limited in scale, with TinyStories retaining 8% of the training split and a model of roughly 25M parameters.