# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
###### Abstract  
Regularized sparse learning with the \(\ell_{0}\)-norm is important in many areas, including statistical learning and signal processing. Iterative hard thresholding (IHT) methods are the state-of-the-art for nonconvex-constrained sparse learning due to their capability of recovering true support and scalability with large datasets. The current theoretical analysis of IHT assumes the use of centralized IID data. In realistic large-scale scenarios, however, data are distributed, seldom IID, and private to edge computing devices at the local level. Consequently, it is required to study the property of IHT in a federated environment, where local devices update the sparse model individually and communicate with a central server for aggregation infrequently without sharing local data. In this paper, we propose the first group of federated IHT methods: Federated Hard Thresholding (Fed-HT) and Federated Iterative Hard Thresholding (FedIter-HT) with theoretical guarantees. We prove that both algorithms have a linear convergence rate and guarantee for recovering the optimal sparse estimator, which is comparable to classic IHT methods, but with decentralized, non-IID, and unbalanced data. Empirical results demonstrate that the Fed-HT and FedIter-HT outperform their competitor--a distributed IHT, in terms of reducing objective values with fewer communication rounds and bandwidth requirements. they require finding an optimal solution to \(min\;\;f(x)\) over the identified support after hard thresholding at each iteration, which lacks analytical solutions for arbitrary losses and can be time-consuming [16]. Hence, gradient-based IHT methods have gained significant interest and become popular for nonconvex sparse learning. IHT methods currently include the gradient descent HT (GD-HT) [14], stochastic gradient descent HT (SGD-HT) [15], hybrid stochastic gradient HT (HSG-HT) [17], and stochastic variance reduced gradient HT (SVRG-HT) [18; 19] methods. These methods update the iterate \(x_{t}\) as follows: \(x_{t+1}=\mathcal{H}_{\tau}(x_{t}-\gamma_{t}v_{t})\), where \(\gamma_{t}\) is the learning rate, \(v_{t}\) can be the full gradient, stochastic gradient or variance reduced gradient at the \(t\)-th iteration, and \(\mathcal{H}_{\tau}(x):\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}\) denotes the HT operator that preserves the top \(\tau\) elements in \(x\) and sets other elements to 0. However, finding a solution to Problem (1) is generally NP-hard because of the non-convexity and non-smoothness of the cardinality constraint [20]. Local datasets can be sensitive to sharing during the construction of a sparse inference model when sparse learning becomes distributed and uses data collected by distributed devices. For instance, meta-analyses may integrate genomic data from a large number of labs to identify (a sparse set of) genes contributing to the risk of a disease without sharing data across the labs [21; 22]. Smartphone-based healthcare systems may need to learn the most important mobile health indicators from a large number of users; however, the personal health information gathered on the phone is private [23]. Furthermore, communication efficiency can be the main challenge to distributively training a sparse learning model. Due to the power and bandwidth limitations of various sensors, the signal processing community, for instance, has been seeking more communication-efficient methods [24]. Federated learning (FL) is a recently proposed communication-efficient distributed computing paradigm that enables collaborations among a collection of clients while preserving data privacy on each device by avoiding the transmission of local data to the central server [25; 26; 27]. Hence, sparse learning can benefit from the setting of federated learning.