Matching Pursuit Based Scheduling for Over-the-Air Federated Learning

This paper develops a class of low-complexity device scheduling algorithms for over-the-air federated learning via the method of matching pursuit. The proposed scheme tracks closely the close-tooptimal performance achieved by difference-of-convex programming, and outperforms significantly the well-known benchmark algorithms based on convex relaxation. In the light of dramatically increasing numbers of mobile devices and data traffic in the Internet-of-Things era, the need for a paradigm-shift in wireless networks from traditional centralized cloud computing architectures to distributed ones is growing [1]-[5]. By performing data processing at the edge of networks, several shortcomings of cloud computing, such as long latency and network congestion, can be effectively addressed [6]-[8]. Notably, edge computing is an appealing technology to perform real-time tasks and make real-time decisions by exploiting the abundant computational resources of the edge servers [9]-[11]. H. Vincent Poor is with the Department of Electrical and Computer Engineering at the Princeton University; email: poor@princeton.edu. One way of overcoming these challenges is to integrate the edge-intelligent network within wireless networks and leverage the superposition property of wireless multiple-access channels [15]. Recently, a new paradigm of distributed machine learning, referred to as federated learning (FL) has been introduced, in which distributed devices jointly train a shared global machine learning model without sharing their raw data explicitly [16]-[18]. In essence, FL is a collaborative machine learning framework that enables distributed model training from decentralized data under coordination of a parameter server (PS) [17]. In principle FL is performed over a decentralized network as follows: 1) A PS first shares a global model with participating devices in the network. It then transmits its trained model parameters to the PS while keeping its private data locally within its own device. These steps are alternated until the global model parameters converge [16], [18], [19]. Further illustrations can be found through the comprehensive example of FL given in Appendix A. Compared to the extreme cases of centralized and individual learning, FL provides a tractable approach to handle a joint learning task over a distributed network. Nevertheless, this tractability comes with some costs which can be roughly categorized into three major forms: 1) The statistical inference problem in FL is more challenging. This follows from the fact that the local datasets in the decentralized setting are not independent and identically distributed (i.i.d.).