# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
## 4 The FedIter-HT Algorithm  
If we apply the HT operator to each local update as well, we obtain the FedIter-HT algorithm, as described in Algorithm 2. Hence, the local update on each device performs multiple SGD-HT steps, which further reduces the communication cost because model parameters sent back from clients to the central server are also sparse. If a client has a communication bandwidth so small that it can not effectively pass the full set of parameters, the FedIter-HT provides a good solution and also can relax the strict requirements for the objective function \(f\) and reduce the statistical bias. In this section, we first present a more communication-efficient federated \(\ell_{0}\)-norm regularized sparse learning framework--FedIter-HT; then, we theoretically show it enjoys a better convergence rate compared with Fed-HT, and we further provide statistical analysis for M-estimators under the framework of FedIter-HT. We again examine the convergence of the FedIter-HT by developing an upper bound on the distance between the estimator \(x_{T}\) and the optimal \(x^{*}\), i.e., \(E[\|x_{T}-x^{*}\|^{2}]\) in the following theorem. ```
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)}=\mathcal{H}_{\tau}(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 2** Federated Iterative Hard Thresholding (FedIter-HT)  
**Theorem 2**. : _Let \(x^{*}\) be the optimal solution to (2), \(\tau^{*}=\|x^{*}\|_{0}\), and suppose \(f(x)\) satisfies Assumptions 1 and 2. The condition number \(\kappa_{s}=\frac{l_{s}}{\rho_{s}}\geq 1\). Let stepsize \(\gamma_{t}=\frac{1}{6l_{s}}\) and the batch size \(b_{t,k}^{(i)}=\frac{\Gamma_{2}}{\omega_{2}^{*}}\), \(\Gamma_{2}\geq\frac{\xi_{2}\sum_{k=1}^{N}p_{i}\varphi_{2}^{2}}{\tilde{\varrho} _{2}\|x_{0}-x^{*}\|^{2}}\), \(\delta_{2}=(2\alpha+3a^{2})(1-\frac{1}{12\kappa_{s}})^{K}\), \(\alpha=\frac{2\sqrt{\tau^{*}}}{\sqrt{\tau-\tau^{*}}}\), the sparsity level \(\tau\geq(\frac{16}{(\sqrt{\frac{16}{2\kappa_{s}-1}}-1)^{2}}+1)\tau^{*}\). Then, the following inequality holds for the FedIter-HT:_  
\[E[\|x_{T}-x^{*}\|^{2}]\leq\theta_{2}^{T}\|x_{0}-x^{*}\|^{2}+g_{3}(x^{*}).\]  
_where \(\theta_{2}=\omega_{2}=(1+2\alpha)^{2}(1-\frac{1}{12\kappa_{s}})^{K}\in(0,1)\), \(g_{3}(x^{*})=\frac{\xi_{2}\beta^{2}}{1-\theta_{2}}\|\pi_{\mathcal{I}}(\
abla f (x^{*}))\|^{2}\), \(\xi_{2}=\frac{(1+\alpha)^{2}(1-(1-\frac{1}{2\kappa_{s}})^{K})\kappa_{s}}{\theta _{2}^{2}}\), \(\phi_{2}=(1+\alpha)^{2}(1-\frac{1}{12\kappa_{s}})^{K}\), \(\alpha=\frac{2\sqrt{\tau^{*}}}{\sqrt{\tau-\tau^{*}}}\), \(\widetilde{\mathcal{I}}^{i}=supp(\mathcal{H}_{2\tau}(\
abla f_{i}(x^{*})))\cup supp (x^{*})\) and \(\widetilde{\mathcal{I}}=supp(\mathcal{H}_{2N\tau}(\
abla f(x^{*})))\cup supp (x^{*})\)._  
The proof details can be found in Appendix A.6. **Remark 3**. : _The factor \(\theta_{2}\), compared with \(\theta_{1}\) in Theorem 1, is smaller if\(2\alpha=\frac{4\sqrt{\tau^{*}}}{\sqrt{\tau-\tau^{*}}}\leq(\frac{1-1/12\kappa_ {d}}{1-1/12\kappa_{s}})^{K}-1\), which means that the FedIter-HT converges faster than the Fed-HT when the beforehand-guessed sparsity \(\tau\) is much larger than the true sparsity. Both \(\theta_{2}\) and \(\theta_{1}\) will decrease when the number of internal iterations \(K\) increases, but \(\theta_{2}\) decreases faster than \(\theta_{1}\) because \(1-\frac{1}{12\kappa_{s}}\) is smaller than \(1-\frac{1}{12\kappa_{d}}\). Thus, the FedIter-HT is more likely to benefit by increasing \(K\) than the Fed-HT.