# FedSEA: Achieving Benefit of Parallelization in Federated Online Learning

arXiv: https://arxiv.org/abs/2604.19336 · HTML: https://mlsanity.com/paper/2604.19336/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 20 references that are in the map.
- First posted on arXiv 21 Apr 2026.

## Builds on (most cited first, 16 of 16)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [Stochastic Controlled Averaging for Federated Learning with Communication Compression](https://mlsanity.com/paper/2308.08165/) (2023)
- [Federated Composite Optimization](https://mlsanity.com/paper/2011.08474/) (2020)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Tighter Regret Analysis and Optimization of Online Federated Learning](https://mlsanity.com/paper/2205.06491/) (2022)
- [Online Federated Learning via Non-Stationary Detection and Adaptation amidst Concept Drift](https://mlsanity.com/paper/2211.12578/) (2022)
- [Federated Online and Bandit Convex Optimization](https://mlsanity.com/paper/2311.17586/) (2023)

## Abstract (arXiv)

Online federated learning (OFL) has emerged as a popular framework for decentralized decision-making over continuous data streams without compromising client privacy. However, the adversary model assumed in standard OFL typically precludes any potential benefits of parallelization. Further, it fails to adequately capture the different sources of statistical variation in OFL problems. In this paper, we extend the OFL paradigm by integrating a stochastically extended adversary (SEA). Under this framework, the loss function remains fixed across clients over time. However, the adversary dynamically and independently selects the data distribution for each client at each time. We propose the algoOFL algorithm to solve this problem, which utilizes online stochastic gradient descent at the clients, along with periodic global aggregation via the server. We establish bounds on the global network regret over a time horizon (T) for two classes of functions: (1) for smooth and convex losses, we prove an (O(√T)) bound, and (2) for smooth and strongly convex losses, we prove an (O(log T)) bound. Through careful analysis, we quantify the individual impact of both spatial (across clients) and temporal (over time) data heterogeneity on the regret bounds. Consequently, we identify a regime of mild temporal variation (relative to stochastic gradient variance), where the network regret improves with parallelization. Hence, in the SEA setting, our results improve the existing pessimistic worst-case results in online federated learning.