Research map / Federated learning and privacy / Communication-efficient FL

Streaming Federated Learning with Markovian Data

NeurIPS 2025 · Federated learning and privacy › Communication-efficient FL · approach: Local drift correction · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes federated learning (Minibatch SGD, Local SGD, Local SGD-M) when each client streams non-stationary Markovian data, proving linear speed-up in sample complexity with M clients for smooth non-convex objectives, and validates on Beijing multi-site air-quality PM2.5 data.

Problem

Federated learning with clients that continuously collect temporally dependent, non-stationary Markovian data streams, where prior theory assumed i.i.d. or pre-collected data and Markovian FL work was limited to convex federated RL.

Approach

Extends FL convergence analysis to Markovian client streams with smooth non-convex objectives using a change-of-measure argument instead of uniform geometric ergodicity, and shows a momentum-based Local SGD (Local SGD-M) removes the need for bounded heterogeneity while matching the communication complexity of i.i.d. lower bounds.

Key results

• Minibatch SGD and Local SGD-M improve as local steps K increase, while Local SGD and SCAFFOLD show little to no improvement under heterogeneity.
• Sample complexity of all three algorithms scales with 1/M, and gradient norm decreases as the number of clients grows on the pollution data.
• Local SGD-M achieves communication complexity O(LΔ0/(β ε^2)) without bounded heterogeneity assumptions, matching the i.i.d. lower bound up to constant 1/β.

Measured effects reported in the paper

Surprising findings

• Local SGD and SCAFFOLD show little to no improvement as the number of local samples K increases, unlike Minibatch SGD and Local SGD-M.
• Bias from Markovian sampling cannot be controlled by a decaying step size, so the number of local steps K must be sufficiently large.

Limitations

• Sample complexity with Markovian data remains higher (order 1/(Mε^4)) than with i.i.d. sampling.
• Local SGD requires bounded gradient dissimilarity heterogeneity assumption; experiments use full participation only.
• Experiments are limited to a single real dataset with a linear regression model with non-convex regularizer.

Experimental setup

Datasets: Beijing Multi-Site Air-Quality dataset

Benchmarks: Beijing Multi-Site Air-Quality dataset

Metrics: gradient norm

Baselines: Minibatch SGD Local SGD SCAFFOLD

Builds on: Local SGD Minibatch SGD FedAvg SCAFFOLD

Closest papers by meaning

• Federated Learning under Periodic Client Participation and Heterogeneous Data: A New Communication-Efficient Algorithm and Analysis (NeurIPS 2024 · similarity 0.88)
• Improving Generalization in Federated Learning with Model-Data Mutual Information Regularization: A Posterior Inference Approach (NeurIPS 2024 · similarity 0.87)
• Exact and Linear Convergence for Federated Learning under Arbitrary Client Participation is Attainable (NeurIPS 2025 · similarity 0.87)
• Improved Modelling of Federated Datasets using Mixtures-of-Dirichlet-Multinomials (ICML 2024 · similarity 0.87)
• Adaptive Federated Learning with Auto-Tuned Clients (ICLR 2024 · similarity 0.87)
• FLHetBench: Benchmarking Device and State Heterogeneity in Federated Learning (CVPR 2024 · similarity 0.86)