Streaming Federated Learning with Markovian Data
This addresses a key limitation for real-world applications like physical or biological processes where data streams are non-stationary, though it is incremental as it extends existing FL methods to Markovian data.
The paper tackles the problem of federated learning with non-stationary Markovian data streams, showing that collaborative learning is feasible with sample complexity proportional to the inverse of the number of clients and communication complexity comparable to i.i.d. scenarios, though sample complexity remains higher than for i.i.d. sampling.
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.