A Straggler-resilient Federated Learning Framework for Non-IID Data Based on Harmonic Coding

Federated learning (FL) has recently emerged as a promising learning paradigm, that enables local gradient update and global model aggregation and synchronization. With the advantages of data privacy protection and communication overhead reduction, FL has been widely adopted in a multitude of edge intelligence and IoT applications. However, except the benefits, FL also suffers from stragglers effect and non-IID data, leading to unpredictable training delay and unstable convergence. Meanwhile, coding theory-based approaches have been proposed for stragglers mitigation in distributed computing, i.e., coded computing. Motivated by coded computing, there are several works introduce coding techniques into federated learning. In this paper, to further exploit the potential of coded federated learning, we propose HarFL, a stragglers resilient federated learning framework for non-IID data based on harmonic coding, which is suitable for general machine learning model with multivariate polynomial gradients and achieves a better stragglers mitigation than former coded federated learning schemes with the same coded computation redundancy. We first describe the basic harmonic coded federated learning framework with two phases: encoded data sharing and gradient results decoding. Moreover, we formulate an optimization problem aiming to maximize the successful probability of decoding, which is proved to be NP-hard. An efficient approximate algorithm with theoretical performance guarantee is also developed to mathematically solve the formulated problem. Finally, simulation results demonstrate the superiority of HarFL over several compared schemes.