Communication-Efficient Randomized Algorithm for Multi-Kernel Online Federated Learning.

Area of Science:

• Machine Learning
• Distributed Systems
• Optimization

Background:

• Online federated learning (OFL) enables learning from distributed sequential data on local devices.
• Existing single-kernel OFL (S-KOFL) uses random-feature approximation, online gradient descent (OGD), and federated averaging (FedAvg).
• Multi-kernel extensions are needed but face high communication overhead.

Purpose of the Study:

• To develop practical multi-kernel online federated learning algorithms with low communication costs.
• To theoretically analyze the performance and regret bounds of the proposed methods.
• To validate the effectiveness of the new algorithms through empirical evaluation.

Main Methods:

• Introduced a single-kernel OFL (S-KOFL) using random-feature approximation, OGD, and FedAvg.
• Developed a vanilla multi-kernel OFL (vM-KOFL) and proved its asymptotic optimality.
• Proposed a novel randomized eM-KOFL and a practical pM-KOFL algorithm to address communication overhead.

Main Results:

• vM-KOFL offers asymptotic optimality but suffers from high communication costs.
• eM-KOFL achieves similar performance to vM-KOFL with significantly reduced communication.
• eM-KOFL theoretically guarantees an optimal sublinear regret bound.
• pM-KOFL demonstrates comparable performance to vM-KOFL and eM-KOFL with S-KOFL's communication efficiency.

Conclusions:

• The proposed eM-KOFL and pM-KOFL effectively reduce communication overhead in multi-kernel online federated learning.
• pM-KOFL provides a practical and communication-efficient solution for real-world online learning tasks.
• These advancements enable more scalable and efficient distributed learning from sequential data.