# Federated Optimization of \(\ell_{0}\)-norm Regularized Sparse Learning
## 2 Preliminaries  
We formalize our problem as Problem (2) and provide the notations (Table 1), assumptions and prepared lemmas used in this paper. We denote vectors by lowercase letters, e.g., \(x\). The model parameters form a vector \(x\in\mathbb{R}^{d}\). The \(\ell_{0}\)-norm, \(\ell_{2}\)-norm and the \(\ell_{\infty}\)-norm of a vector are denoted by \(\|\cdot\|_{0}\), \(\|\cdot\|\) and \(\|\cdot\|_{\infty}\), respectively. Let \(O(\cdot)\) represent the asymptotic upper bound, \([N]\) be the integer set \(\{1,\ldots,N\}\). The support \(\mathcal{I}^{(i)}_{t,k+1}=supp(x^{*})\cup supp(x^{(i)}_{t,k})\cup supp(x^{(i) }_{t,k+1})\) is associated with the \((k+1)\)-th iteration in the \(t\)-th round on device \(i\). For simplicity, we use \(\mathcal{I}^{(i)}=\mathcal{I}^{(i)}_{t,k+1}\), \(\mathcal{I}=\bigcup_{i=1}^{N}\mathcal{I}^{(i)}_{t,k+1}\) throughout the paper without ambiguity, and \(\widetilde{\mathcal{I}}=supp(\mathcal{H}_{2N\tau}(\
abla f(\mathbf{x}^{*}))) \cup supp(\mathbf{x}^{*})\). We use the same conditions employed in the theoretical analysis of other IHT methods by assuming that the objective function \(f(x)\) satisfies the following conditions:  
**Assumption 1**. : _We assume that the loss function \(f_{i}(x)\) on each device \begin{table}
\begin{tabular}{l l} \hline \hline \(\mathcal{H}_{\tau}(x)\) & the HT operator that maintains the top \(\tau\) items of \(x\) and sets the remaining \\  & elements to 0 \\ \hline \(N,i\) & the total number, the index of clients/devices \\ \hline \(p_{i}\) & the weight of each loss function on client \(i\) \\ \hline \(T,t\) & the total number, the index of communication rounds \\ \hline \(K,k\) & the total number, the index of local iterations \\ \hline \(\
abla f_{i}(\cdot)\) & the full gradient \\ \hline \(\
abla f_{i\cap}(\cdot)\) & the stochastic gradient over the minibatch \(I^{(i)}\) \\ \hline \(\
abla f_{i\circ}(\cdot)\) & the stochastic gradient over a training example indexed by \(z\) on the \(i\)-th device \\ \hline \(\gamma_{t}\) & the stepsize/learning rate of local update \\ \hline \(\mathbb{I}(\cdot)\) & an indicator function \\ \hline \(supp(x)\) & the support of \(x\) or the index set of nonzero elements in \(x\) \\ \(x^{*}\) & the optimal solution of Problem (2) \\ \hline \(x^{(i)}_{tk}\) & the local parameter vector on device \(i\) at the \(k\)-th iteration of the \(t\)-th round \\ \hline \(\tau\) & the required sparsity level \\ \hline \(\tau^{*}\) & the optimal sparsity level of Problem (2), \(\tau^{*}=\|x^{*}\|_{0}\) \\ \hline \(\pi_{\mathcal{I}}(x)\) & the projector takes only the elements of \(x\) indexed in \(\mathcal{I}\) \\ \hline \(E[\cdot]\), \(E^{(i)}[\cdot]\) & the expectation over stochasticity across all clients and of client \(i\), respectively \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Brief summary of notations in this paper. 1. _is restricted_ \(\rho_{s}\)_-strongly convex (RSC_ _[_43_]_) at the sparsity level_ \(s\) _for a given_ \(s\in\mathbb{N}_{+}\)_, i.e., there exists a constant_ \(\rho_{s}>0\) _such that_ \(\forall x_{1},x_{2}\in\mathbb{R}^{d}\) _with_ \(\|x_{1}-x_{2}\|_{0}\leq s\)_,_ \(i\in[N]\)_, we have_ \[f_{i}(x_{1})-f_{i}(x_{2})-\langle\
abla f_{i}(x_{2}),x_{1}-x_{2}\rangle\geq \frac{\rho_{s}}{2}\|x_{1}-x_{2}\|^{2};\]
2. _is restricted_ \(l_{s}\)_-strongly smooth (RSS_ _[_43_]_) at the sparsity level_ \(s\) _for a given_ \(s\in\mathbb{N}_{+}\)_, i.e., there exists a constant_ \(l_{s}>0\) _such that_ \(\forall x_{1},x_{2}\in\mathbb{R}^{d}\) _with_ \(\|x_{1}-x_{2}\|_{0}\leq s\)_,_ \(i\in[N]\)_, we have_ \[f_{i}(x_{1})-f_{i}(x_{2})-\langle\
abla f_{i}(x_{2}),x_{1}-x_{2}\rangle\leq \frac{l_{s}}{2}\|x_{1}-x_{2}\|^{2};\]
3. _has_ \(\sigma_{i}^{2}\)_-bounded stochastic gradient variance, i.e.,_ \[E^{(i)}(\|\
abla f_{i,z}(x)-\
abla f_{i}(x)\|^{2}]\leq\sigma_{i}^{2}.\]  
**Remark 1**.