# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
## Appendix A1 Distributed IHT Algorithm
### Proof of Theorem 1  
Proof. : For the Fed-HT algorithm:  
\[E[\|x_{t+1}-x^{*}\|^{2}] =E[\|\mathcal{H}_{\tau}(\sum_{i=1}^{N}p_{i}x_{t,K}^{(i)})-x^{*}\| ^{2}]\] \[\leq(1+\alpha)E[\|\sum_{i=1}^{N}p_{i}x_{t,K}^{(i)}-x^{*}\|^{2}]\] (A3) \[=(1+\alpha)E[\|\sum_{i=1}^{N}p_{i}x_{t,K}^{(i)}-\sum_{i=1}^{N}p_{ i}x^{*}\|^{2}]\] (A4) \[\leq(1+\alpha)\sum_{i=1}^{N}p_{i}E^{(i)}[\|x_{t,K}^{(i)}-x^{*}\|^ {2}].\] (A5)  
* [PERSON] and [PERSON] (2012) [PERSON]; [PERSON] [PERSON] Learning sparsifying transforms. _IEEE Trans. Signal Process._**2012**, _61_, 1072-1086. [CrossRef]
* [PERSON] and [PERSON] (2007) [PERSON]; [PERSON] Signal recovery from random measurements via orthogonal matching pursuit. _IEEE Trans. Inf. Theory_**2007**, _53_, 4655-4666. [CrossRef]
* [PERSON] et al. (2022) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Greedy Sparsity-Constrained Optimization. Available online: [[https://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.365.3874&rep=rep1&type=pdf](https://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.365.3874&rep=rep1&type=pdf)]([https://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.365.3874&rep=rep1&type=pdf](https://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.365.3874&rep=rep1&type=pdf)) (accessed on 1 July 2022). * [PERSON] et al. (2011) [PERSON]; [PERSON]; [PERSON] On learning discrete graphical models using greedy methods. _Adv. Neural Inf. Process. Syst._**2011**, _24_, 1935-1943. * [PERSON] and [PERSON] (1993) [PERSON]; [PERSON] Matching pursuits with time-frequency dictionaries. _IEEE Trans. Signal Process._**1993**, _41_, 3397-3415. [CrossRef]
* [PERSON] et al. (1993) [PERSON]; [PERSON]; [PERSON] Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of the 27 th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA, 1-3 November 1993; pp. 40-44. * [PERSON] and [PERSON] (2009) [PERSON]; [PERSON] CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. _Appl. Comput. Harmon. Anal._**2009**, _26_, 301-321. [CrossRef]
* [PERSON] (2011) [PERSON] Hard thresholding pursuit: An algorithm for compressive sensing. _SIAM J. Numer. Anal._**2011**, _49_, 2543-2563. [CrossRef]
* [PERSON] and [PERSON] (2009) [PERSON]; [PERSON] Iterative hard thresholding for compressed sensing. _Appl. Comput. Harmon. Anal._**2009**, _27_, 265-274. [CrossRef]
* [PERSON] et al. (2014) [PERSON]; [PERSON]; [PERSON] On iterative hard thresholding methods for high-dimensional m-estimation. In Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada, 8-13 December 2014; pp. 685-693. * [PERSON] and [PERSON] (2017) [PERSON]; [PERSON] [PERSON]; [PERSON] Linear convergence of stochastic iterative greedy algorithms with sparse constraints. _IEEE Trans. Inf. Theory_**2017**, _63_, 6869-6895. [CrossRef]
* [PERSON] et al. (2013) [PERSON]; [PERSON]; [PERSON] Greedy sparsity-constrained optimization. _[PERSON]. Learn. Res._**2013**, _14_, 807-841. * [PERSON] and [PERSON] (2018) [PERSON]; [PERSON]; [PERSON] Efficient stochastic gradient hard thresholding. In Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada, 3-8 December 2018; pp. 1988-1997. * [PERSON] et al. (2017) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON] Stochastic variance reduced optimization for nonconvex sparse learning. In Proceedings of the International Conference on Machine Learning, New York, NY, USA, 19-24 June 2016; pp. 917-925. * [PERSON] and [PERSON] (2017) [PERSON]; [PERSON] A tight bound of hard thresholding. _[PERSON]. Learn. Res._**2017**, _18_, 7650-7691. * [PERSON] (1995) [PERSON] Sparse approximate solutions to linear systems. _SIAM J. Comput._**1995**, _24_, 227-234. [CrossRef]
* [PERSON] et al. (2003) [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; [PERSON]; et al. Different data from different labs: Lessons from studies of gene-environment interaction. _J. Neurobiol._**2003**, _54_, 283-311.