Search papers, labs, and topics across Lattice.
This paper introduces a stochastically extended adversary (SEA) model for online federated learning (OFL) where the data distribution for each client is independently selected by an adversary at each time step, while the loss function remains fixed. They propose the FedSEA algorithm, employing online stochastic gradient descent at clients with periodic server aggregation, and derive regret bounds of \(\mathcal{O}(\sqrt{T})\) for smooth convex losses and \(\mathcal{O}(\log T)\) for smooth strongly convex losses. The analysis reveals that under mild temporal variation, parallelization improves network regret, outperforming pessimistic worst-case results in standard OFL.
Online federated learning can actually benefit from parallelization, but only if temporal data variation is mild relative to stochastic gradient variance鈥攁 condition often overlooked in existing pessimistic analyses.
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 \(\mathcal{O}(\sqrt{T})\) bound, and (2) for smooth and strongly convex losses, we prove an \(\mathcal{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.
