Communication cost-aware client selection in online federated learning: a Lyapunov approach

The proliferation of intelligence services brings data breaches and privacy infringement concerns. To preserve data privacy when training machine learning models, the federated learning (FL) paradigm emerges. Most existing works assume that training data on FL clients are static during the entire learning process. Nevertheless, various real-time intelligent services call for timely processing of continuously generated data, which fosters the advent of online federated learning (OFL). Currently, how to reconcile model utility and communication cost in OFL is still an open problem. To address this challenge, we leverage the Lyapunov optimization framework to devise a novel Low Cost Client Selection (LCCS) algorithm for OFL, which can judiciously select participating clients to maximize model utility with a low communication cost. Specifically, we design the objective as the sum of a penalty function and a Lyapunov drift function to take both gradient-based client valuation and communication cost into account. By minimizing the objective, we further design the LCCS algorithm, which is lightweight for execution on clients. At last, we conduct extensive experiments with traces generated from public datasets. The experimental results demonstrate that LCCS achieves the highest model utility with a fixed communication cost in comparison with the state-of-the-art baselines.