# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
## 3 The Fed-HT Algorithm  
In this section, we first describe our new federated \(\ell_{0}\)-norm regularized sparse learning framework via hard thresholding--Fed-HT, and then discuss the convergence rate of our proposed algorithm. A high level summary of Fed-HT is described in Algorithm 1. The Fed-HT algorithm generates a sequence of \(\tau-\)sparse vectors \(x_{1}\), \(x_{2}\), \(\cdots\), from an initial sparse approximation \(x_{0}\). At the \((t+1)\)-th round, clients receive the global parameter update \(x_{t}\) from the central server, then run \(K\) steps of minibatch SGD based on local private data. In each step, the \(i\)-th client updates \(x_{t,k+1}^{(i)}=argmin_{x}f_{i}(x_{t,k}^{(i)})+\langle g_{t,k}^{(i)},x-x_{t,k}^ {(i)}\rangle+\frac{1}{2\tau_{t}}\|x-x_{t,k}^{(i)}\|^{2}\) for \(k\in\{0,\ldots,K-1\}\), i.e., \(x_{t,k+1}^{(i)}=x_{t,k}^{(i)}-\tau_{t}g_{t,k}^{(i)}\). clients send \(x_{t,k}^{(i)}\) for \(i\in[N]\) back to the central server; then, the server averages them to obtain a dense global parameter vector and applies the HT operator to obtain a sparse iterate \(x_{t+1}\). Unlike the commonly used FedAvg, the Fed-HT is designed to solve the family of federated \(\ell_{0}\)-norm regularized sparse learning problems. It has a strong ability to recover the optimal sparse estimator in decentralized non-IID and unbalanced data settings while at the same time reducing the communication cost by a large margin because the central server broadcasts a sparse iterate for each of the \(T\) rounds. ```
Input: The learning rate \(\gamma_{t}\), the sparsity level \(\tau\), and the number of clients \(N\). Initialize\(x_{0}\) for\(t=0\) to \(T-1\)do for client \(i=1\) to \(N\) parallel do \(x_{t,1}^{(i)}=x_{t}\) for\(k=1\) to \(K\)do  Sample uniformly a batch \(I_{t,k}^{(i)}\) with batchsize \(b_{t,k}^{(i)}\) \(g_{t,k}^{(i)}=\
abla f_{I_{t,k}^{(i)}}(x_{t,k}^{(i)})\) \(x_{t,k+1}^{(i)}=x_{t,k}^{(i)}-\gamma_{t}g_{t,k}^{(i)}\) endfor endfor \(x_{t+1}=\mathcal{H}_{\tau}(\sum_{i=1}^{N}p_{i}x_{t,K}^{(i)})\) endfor
```  
**Algorithm 1** Federated Hard Thresholding (Fed-HT)  
The following theorem characterizes our theoretical analysis of Fed-HT in terms of its **parameter estimation accuracy** for sparsity-constrained problems. Although this paper is focused on the cardinality constraint, the theoretical result is applicable to other sparsity constraints, such as a constraint based on matrix rank. Then, we have the main theorem and the detailed proof. Theorem 1: _Let \(x^{*}\) be the optimal solution to Problem (2), \(\tau^{*}=\|x^{*}\|_{0}\), and suppose \(f(x)\) satisfies Assumptions 1 and 2. The condition number \(\kappa_{d}=\frac{l_{d}}{\rho_{d}}\geq 1\). Let stepsize \(\gamma_{t}=\frac{1}{\theta_{d}}\) and the batch size \(b_{t,k}^{(i)}=\frac{\Gamma_{t}}{\omega_{t}^{2}}\), \(\Gamma_{1}\geq\frac{\xi_{1}\sum_{i=1}^{N}p_{i}\sigma_{t}^{2}}{\delta_{1}\|x_{ 0}-x^{*}\|^{2}}\), \(\delta_{1}=\alpha(1-\frac{1}{12\kappa_{d}})^{K}\), \(\alpha=\frac{2\sqrt{\tau^{*}}}{\sqrt{\tau-\tau^{*}}}\), the sparsity level \(\tau\geq(16(12\kappa_{d}-1)^{2}+1)\tau^{*}\). Then the following inequality holds for the Fed-HT:_  
\[E[\|x_{\tau}-x^{*}\|^{2}]\leq\theta_{1}^{\top}\|x_{0}-x^{*}\|^{2}+g_{1}(x^{*}).\]  
_where \(\theta_{1}=\omega_{1}=(1+2\alpha)(1-\frac{1}{12\kappa_{d}})^{K}\in(0,1)\), \(g_{1}(x^{*})=\frac{\xi_{1}\mathcal{B}^{2}}{\Gamma-\phi_{1}}\|\
abla f(x^{*})\| ^{2}\), \(\phi_{1}=(1+\alpha)(1-\frac{1}{12\kappa_{d}})^{K}\), \(\xi_{1}=\frac{(1+\alpha)(1-(1-(1-\frac{1}{12\kappa_{d}})^{K})_{K}}{\delta_{2}^ {2}}\)._  
The proof can be found in Appendix A.4. Note that if the sparse solution \(x^{*}\) is sufficiently close to an unconstrained minimizer of \(f(x)\), then \(\|\
abla f(x^{*})\|\) is small, so the first exponential term on the right-hand side can be a dominating term, which approaches \(0\) when \(T\) goes to infinity. We further obtain the following corollary that bounds the number of rounds \(T\) to obtain a sub-optimal solution, i.e., the difference between the solution and \(x^{*}\) is bounded only by the second term.