# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
###### Abstract
(d) Extensive experiments in simulations and on real-life datasets demonstrate the effectiveness of the proposed algorithms over standard distributed IHT learning. Related Work  
**Distributed sparse learning. ** Existing IHT algorithms can be extended to their distributed version--Distributed IHT (see Appendix A.1. for details), in which the central server aggregates (averages) the local parameter updates from each client and broadcasts the latest model parameters to individual clients, whereas each client updates the parameters based on the distributed local data with one step of stochastic gradient descend and sends them back to the central server. However, Distributed IHT is communication expensive since it needs to send dense local models to the central server after each step of stochastic gradient updates. Even though variants of the Distributed IHT, such as [29; 30], have been developed, information must be exchanged at each iteration, making communication costly and limiting bandwidth. Other distributed methods have also been proposed. For instance, Ref. [31] tries to solve a relaxed \(l_{1}\)-norm regularized problem and thus introduces extra bias to Problem (2); Ref. [32] experimentally studies gradient compression with practical gradient clipping techniques (i.e., the local nodes have to select threshold) in distributed training; Ref. [33] proposed a modified distributed top-k sparsification by choosing the largest absolute gradients before updating the model to reduce communication. The distributed algorithms proposed in [32; 33] use some techniques to reduce communication and bandwidth but are not designed for constrained optimization such as sparse model optimization. **Federated learning. ** FL is a privacy-preserving learning framework for large-scale machine learning on edge computing devices and solves the data-decentralized optimization problem: \(\min_{x\in\mathbb{R}^{d}}f(x)=\sum_{i=1}^{N}p_{i}f_{i}(x)\) (without the sparsity constraint in Problem (2).) The FedAvg algorithm proposed in [25] can significantly reduce the communication cost by running multiple local SGD steps before each communication round and has become the de facto federated learning technique. Later, the client drift problem was observed for FedAvg [34; 35; 36], and the FedProx algorithm came to exist [37] in which the individual clients attempt to add a proximal operator to the local subproblem to address the issue of FedAvg. Researchers also study FL in the quantization strategy and the IoT (Internet of Things) systems, and the local updates are sparsified and compressed using signSGD [38; 39; 40]. Ref. [41] presents an online gradient sparsification method, which ensures that different clients provide a similar amount of updates and automatically determines the near-optimalcommunication and computation trade-off that is controlled by the degree of gradient sparsity. [PERSON] et al. recently studied a federated \(l_{1}\)-regularized logistic regression problem and proposed federated mirror descent algorithm [PERSON] et al. (2018) to solve (convex) nonsmooth composite optimization. However, federated optimization of \(\ell_{0}-\)norm regularized sparse learning (as described in Problem (2)) is still under explored. **Organization of the paper** is as follows: Section 2 provides the preliminaries formally, which include the notations used in this study as well as several generally held assumptions and lemmas. In Sections 3 and 4, the Fed-HT and FedIter-HT algorithms are proposed and studied, respectively. In Section 4, we normally perform a statistical analysis for M-estimators in order to emphasize the advantageous property of the FedIter-HT. Experiments simulating numerical performance are presented in Section 5.1, and benchmark datasets are analyzed in Section 5.2. Section 6 summarizes our outcomes. Appendix A contains the proof of our theoretical results and additional experiment details.