# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
###### Abstract
In this paper, we solve the federated nonconvex sparsity-constrained empirical risk minimization problem with decentralized data as follows:  
\[\min_{x\in\mathbb{R}^{d}}f(x)=\sum_{i=1}^{N}p_{i}f_{i}(x),\quad\text{subject to}\;\;\|x\|_{0}\leq\tau, \tag{2}\]  
where \(f(x)\) is a smooth and convex function, \(f_{i}(x)=E_{z\sim\mathcal{D}_{i}}[f_{i}(x,z)]\) is the loss function of the \(i\)-th client (or device) with weight \(p_{i}\in[0,1)\), \(\sum_{i=1}^{N}p_{i}=1\), \(\mathcal{D}_{i}\) is the distribution of data located locally on the \(i\)-th client, and \(N\) is the total number of clients. It is thus desirable to solve Problem (2) in a communication-efficient way and investigate theory and algorithms applicable to a broader class of sparse constrained learning problems in high-dimensional data analyses [6; 7; 8; 28]. We thus propose federated HT algorithms with lower communication costs and provide the corresponding theoretical analysis under practical federated settings. The analysis of proposed methods is difficult due to the fact that distributions of training data on each client may be non-identical and the data weights can be unbalanced across devices. Our main contributions are summarized as follows. (a) We develop two schemes for the federated HT method: the Federated Hard Thresholding (Fed-HT) algorithm and Federated Iterative Hard Thresholding (FedIter-HT) algorithm. In Fed-HT, we apply the HT operator \(\mathcal{H}_{\tau}\) at the central server right before distributing the aggregated model to clients. To further improve the communication efficiency and the ability of sparsity recovery, in FedIter-HT, we consider applying \(\mathcal{H}_{\tau}\) to both local updates and the central server aggregate. Note that this is the first trial to explore IHT algorithms under federated learning settings. (b) We provide a set of theoretical results for the federated HT method, particularly of Fed-HT and FedIter-HT, under the realistic condition that the distributions of training data over devices can be unbalanced and non-independent and non-identical (non-IID), i.e., for \(i\
eq j\), \(\mathcal{D}_{i}\) and \(\mathcal{D}_{j}\) are different. We prove that both algorithms enjoy a linear convergence rate and have a strong guarantee for sparsity recovery. In particular, Theorems 1 (for the FedIter-HT) and 2 (for the FedIter-HT) show that the estimation error between the algorithm iterate \(x_{T}\) and the optimal solution \(x^{*}\) is upper bounded as: \(E\|x_{T}-x^{*}\|\leq g^{T}\|x_{0}-x^{*}\|^{2}+g(x^{*})\), where \(x_{0}\) is the initial guess of the solution, the convergence rate factor \(\theta\) is related to the algorithm parameter \(K\) (the number of SGD steps on each device before communication), and the closeness between the pre-specified sparsity level \(\tau\) and the true sparsity \(\tau^{*}\), and \(g(x^{*})\) determines a statistical bias term related not only to \(K\) but also to the gradient of \(f\) at the _sparse_ solution \(x^{*}\) and the measurement of the non-IIDness of the data across the devices. The theoretical results allow us to evaluate and compare the proposed methods. For example, greater non-IIDness among clients increases the bias of both algorithms. More local iterations may reduce \(\theta\) but increase the statistical bias. Due to the utilization of the HT operator on local updates, the statistical bias induced by the FedIter-HT in Theorem 2 matches the best known upper bound for traditional IHT methods [17], which exhibits the powerful capability of sparsity recovery. (c) When instantiating the general loss function by concrete squared or logistic loss, we arrive at specific sparse learning problems, such as sparse linear regression and sparse logistic regression. We provide statistical analysis of the maximum likelihood estimators (M-estimators) of these problems when using the FedIter-HT to solve them. This result can be regarded as federated HT analysis for generalized linear models.