FedNK-RF: Federated Kernel Learning With Heterogeneous Data and Optimal Rates

Federated learning (FL) has become a mainstream decentralized learning paradigm due to its privacy-preserving features. However, the heterogeneity of data in FL can reduce predictive accuracy and complicate the analysis of the generalization properties of FL methods. In this article, we propose efficient federated kernel learning (FedK) algorithms and study their generalization properties. We first devise FedK with random features (FedK-RF), which acquires global information through sharing RF of local data subsets, enhancing predictive capability while protecting privacy. We then propose federated Nyström approximation with RF (FedNK-RF) that reduces errors resulted from RF. Furthermore, using integral operator theory, we derive the excess risk bounds with minimax optimal rates, which illustrate the impacts from data heterogeneity and shared information. Finally, we conduct several experiments that demonstrate the superiority of the proposed FedNK-RF.