Federated Optimization of ℓ₀-norm Regularized Sparse Learning

Abstract

Regularized sparse learning with the ${\ell }_0$-norm is important in many areas, including statistical learning and signal processing. Iterative hard thresholding (IHT) methods are the state-of-the-art for nonconvex-constrained sparse learning due to their capability of recovering true support and scalability with large datasets. The current theoretical analysis of IHT assumes the use of centralized IID data. In realistic large-scale scenarios, however, data are distributed, seldom IID, and private to edge computing devices at the local level. Consequently, it is required to study the property of IHT in a federated environment, where local devices update the sparse model individually and communicate with a central server for aggregation infrequently without sharing local data. In this paper, we propose the first group of federated IHT methods: Federated Hard Thresholding (Fed-HT) and Federated Iterative Hard Thresholding (FedIter-HT) with theoretical guarantees. We prove that both algorithms have a linear convergence rate and guarantee for recovering the optimal sparse estimator, which is comparable to classic IHT methods, but with decentralized, non-IID, and unbalanced data. Empirical results demonstrate that the Fed-HT and FedIter-HT outperform their competitor—a distributed IHT, in terms of reducing objective values with fewer communication rounds and bandwidth requirements.

1. Introduction

Sparse learning has emerged as a central topic of study in a variety of fields that require high-dimensional data analysis. Sparsity-constrained statistical models exploit the fact that high dimensional data arising from real-world applications frequently have low intrinsic complexity and have been shown to perform accurate estimation and inference in a variety of data mining fields, such as bioinformatics [1], image analysis [2,3], graph sparsification [4] and engineering [5]. These models often require solving the following optimization problem with a nonconvex, nonsmooth sparsity constraint:

$$\begin{array}{c}\hfill \underset{x}{min}f(x),\mathrm{subject}\mathrm{to}{\parallel x\parallel }_0\le \tau ,\end{array}$$

(1)

where $f(x)$ is a smooth and convex cost function in terms of a vector of parameters to be optimized x, ${\parallel x\parallel }_0$ denotes the $l_0$-norm (cardinality) of x, which computes the number of nonzero entries in x, and $\tau$ is the sparsity level pre-specified for x. Examples of this model include sparsity-constrained linear/logistic regression problems [6,7] and sparsity-constrained graphical models [8].

Extensive research has been conducted for Problem (1). The methods largely fall into the regimes of either matching pursuit methods [9,10,11,12] or iterative hard thresholding (IHT) methods [13,14,15]. Even though matching pursuit methods achieve remarkable success in minimizing quadratic loss functions (such as the ${\ell }_0$-constrained linear regression problems), they require finding an optimal solution to min $f(x)$ over the identified support after hard thresholding at each iteration, which lacks analytical solutions for arbitrary losses and can be time-consuming [16]. Hence, gradient-based IHT methods have gained significant interest and become popular for nonconvex sparse learning. IHT methods currently include the gradient descent HT (GD-HT) [14], stochastic gradient descent HT (SGD-HT) [15], hybrid stochastic gradient HT (HSG-HT) [17], and stochastic variance reduced gradient HT (SVRG-HT) [18,19] methods. These methods update the iterate $x_t$ as follows: $x_{t+1}={\mathcal{H}}_{\tau }(x_t-{\gamma }_t{v}_t)$, where ${\gamma }_t$ is the learning rate, $v_t$ can be the full gradient, stochastic gradient or variance reduced gradient at the t-th iteration, and ${\mathcal{H}}_{\tau }(x):{\mathbb{R}}^d\to {\mathbb{R}}^d$ denotes the HT operator that preserves the top $\tau$ elements in x and sets other elements to 0. However, finding a solution to Problem (1) is generally NP-hard because of the non-convexity and non-smoothness of the cardinality constraint [20].

Local datasets can be sensitive to sharing during the construction of a sparse inference model when sparse learning becomes distributed and uses data collected by distributed devices. For instance, meta-analyses may integrate genomic data from a large number of labs to identify (a sparse set of) genes contributing to the risk of a disease without sharing data across the labs [21,22]. Smartphone-based healthcare systems may need to learn the most important mobile health indicators from a large number of users; however, the personal health information gathered on the phone is private [23]. Furthermore, communication efficiency can be the main challenge to distributively training a sparse learning model. Due to the power and bandwidth limitations of various sensors, the signal processing community, for instance, has been seeking more communication-efficient methods [24].

Federated learning (FL) is a recently proposed communication-efficient distributed computing paradigm that enables collaborations among a collection of clients while preserving data privacy on each device by avoiding the transmission of local data to the central server [25,26,27]. Hence, sparse learning can benefit from the setting of federated learning. In this paper, we solve the federated nonconvex sparsity-constrained empirical risk minimization problem with decentralized data as follows:

$$\underset{x\in {\mathbb{R}}^d}{min}f(x)=\sum _{i=1}^N{p}_i{f}_i(x),\mathrm{subject}\mathrm{to}{\parallel x\parallel }_0\le \tau ,$$

(2)

where $f(x)$ is a smooth and convex function, $f_i(x)=E_{z\sim {\mathcal{D}}_i}\left[f_i(x,z)\right]$ is the loss function of the i-th client (or device) with weight $p_i\in [0,1)$, ${\sum }_{i=1}^N{p}_i=1$, ${\mathcal{D}}_i$ is the distribution of data located locally on the i-th client, and N is the total number of clients. It is thus desirable to solve Problem (2) in a communication-efficient way and investigate theory and algorithms applicable to a broader class of sparse constrained learning problems in high-dimensional data analyses [6,7,8,28].

We thus propose federated HT algorithms with lower communication costs and provide the corresponding theoretical analysis under practical federated settings. The analysis of proposed methods is difficult due to the fact that distributions of training data on each client may be non-identical and the data weights can be unbalanced across devices.

Our main contributions are summarized as follows.

(a) We develop two schemes for the federated HT method: the Federated Hard Thresholding (Fed-HT) algorithm and Federated Iterative Hard Thresholding (FedIter-HT) algorithm. In Fed-HT, we apply the HT operator ${\mathcal{H}}_{\tau }$ at the central server right before distributing the aggregated model to clients. To further improve the communication efficiency and the ability of sparsity recovery, in FedIter-HT, we consider applying ${\mathcal{H}}_{\tau }$ to both local updates and the central server aggregate. Note that this is the first trial to explore IHT algorithms under federated learning settings.

(b) We provide a set of theoretical results for the federated HT method, particularly of Fed-HT and FedIter-HT, under the realistic condition that the distributions of training data over devices can be unbalanced and non-independent and non-identical (non-IID), i.e., for $i\ne j$, ${\mathcal{D}}_i$ and ${\mathcal{D}}_j$ are different. We prove that both algorithms enjoy a linear convergence rate and have a strong guarantee for sparsity recovery. In particular, Theorems 1 (for the Fed-HT) and 2 (for the FedIter-HT) show that the estimation error between the algorithm iterate $x_T$ and the optimal solution $x^{*}$ is upper bounded as: $E\parallel x_T-x^{*}\parallel \le {\theta }^T{\parallel x_0-x^{*}\parallel }^2+g(x^{*}),$ where $x_0$ is the initial guess of the solution, the convergence rate factor $\theta$ is related to the algorithm parameter K (the number of SGD steps on each device before communication), and the closeness between the pre-specified sparsity level $\tau$ and the true sparsity ${\tau }^{*}$, and  $g(x^{*})$ determines a statistical bias term related not only to K but also to the gradient of f at the sparse solution $x^{*}$ and the measurement of the non-IIDness of the data across the devices.

The theoretical results allow us to evaluate and compare the proposed methods. For example, greater non-IIDness among clients increases the bias of both algorithms. More local iterations may reduce $\theta$ but increase the statistical bias. Due to the utilization of the HT operator on local updates, the statistical bias induced by the FedIter-HT in Theorem 2 matches the best known upper bound for traditional IHT methods [17], which exhibits the powerful capability of sparsity recovery.

(c) When instantiating the general loss function by concrete squared or logistic loss, we arrive at specific sparse learning problems, such as sparse linear regression and sparse logistic regression. We provide statistical analysis of the maximum likelihood estimators (M-estimators) of these problems when using the FedIter-HT to solve them. This result can be regarded as federated HT analysis for generalized linear models.

(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-optimal communication and computation trade-off that is controlled by the degree of gradient sparsity. Yuan et al. recently studied a federated $l_1$-regularized logistic regression problem and proposed federated mirror descent algorithm [42] 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 Section 3 and Section 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.

2. Preliminaries

We formalize our problem as Problem (2) and provide the notations (

Table 1. Brief summary of notations in this paper.

${\mathcal{H}}_{\tau }(x)$	the HT operator that maintains the top $\tau$ items of x and sets the remaining elements to 0
$N,i$	the total number, the index of clients/devices
$p_i$	the weight of each loss function on client i
$T,t$	the total number, the index of communication rounds
$K,k$	the total number, the index of local iterations
$\nabla f_i(·)$	the full gradient
$\nabla f_{I^{(i)}}(·)$	the stochastic gradient over the minibatch $I^{(i)}$
$\nabla f_{i,z}(·)$	the stochastic gradient over a training example indexed by z on the i-th device
${\gamma }_t$	the stepsize/learning rate of local update
$\mathbb{I}(·)$	an indicator function
$supp(x)$	the support of x or the index set of nonzero elements in x
$x^{*}$	the optimal solution of Problem (2)
$x_{t,k}^{(i)}$	the local parameter vector on device i at the k-th iteration of the t-th round
$\tau$	the required sparsity level
${\tau }^{*}$	the optimal sparsity level of Problem (2), ${\tau }^{*}={\parallel x^{*}\parallel }_0$
${\pi }_{\mathcal{I}}(x)$	the projector takes only the elements of x indexed in $\mathcal{I}$
$E[·]$, $E^{(i)}[·]$	the expectation over stochasticity across all clients and of client i, respectively

), 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 ${\parallel ·\parallel }_0$, $\parallel ·\parallel$ and ${\parallel ·\parallel }_{\infty }$, respectively. Let $O(·)$ represent the asymptotic upper bound, $\left[N\right]$ be the integer set $\{1,\dots ,N\}$. The support ${\mathcal{I}}_{t,k+1}^{(i)}=supp(x^{*})\cup supp(x_{t,k}^{(i)})\cup supp(x_{t,k+1}^{(i)})$ 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}}_{t,k+1}^{(i)}$, $\mathcal{I}={\bigcup }_{i=1}^N{\mathcal{I}}_{t,k+1}^{(i)}$ throughout the paper without ambiguity, and $\tilde{\mathcal{I}}=supp\left({\mathcal{H}}_{2N\tau }\left(\nabla f\left({\mathit{x}}^{*}\right)\right)\right)\cup supp\left({\mathit{x}}^{*}\right)$.

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 i

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 $\parallel x_1-x_2{\parallel }_0\le s$, $i\in \left[N\right]$, we have

$$f_i(x_1)-f_i(x_2)-\langle \nabla f_i(x_2),x_1-x_2\rangle \ge \frac{{\rho }_s}{2}{\parallel x_1-x_2\parallel }^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 $\parallel x_1-x_2{\parallel }_0\le s$, $i\in \left[N\right]$, we have

$$f_i(x_1)-f_i(x_2)-\langle \nabla f_i(x_2),x_1-x_2\rangle \le \frac{l_s}{2}{\parallel x_1-x_2\parallel }^2;$$

3. 

has ${\sigma }_i^2$-bounded stochastic gradient variance, i.e., 

$$E^{(i)}[\parallel \nabla f_{i,z}(x)-\nabla f_i(x){\parallel }^2]\le {\sigma }_i^2.$$

Remark 1.

When $s=d$, the above assumption is no longer restricted to the support at a sparsity level, and $f_i$ is actually ${\rho }_d$-strongly convex and $l_d$-strongly smooth.

Following the same convention in FL [35,37], we also assume the dissimilarity between the gradients of the local functions $f_i$ and the global function f is bounded as follows.

Assumption 2.

The functions $f_i(x)$ ($i\in \left[N\right]$) are $\mathcal{B}$-locally dissimilar, i.e., there exists a constant $\mathcal{B}>1$, such that

$$\sum _{i=1}^N{p}_i\parallel {\pi }_{\mathcal{I}}(\nabla f_i(x)){\parallel }^2\le {\mathcal{B}}^2{\parallel {\pi }_{\mathcal{I}}\nabla f(x)\parallel }^2$$

for any $\mathcal{I}$.

From the assumptions mentioned in the main text, we have the following lemmas to prepare for our theorems.

Lemma 1

([44]). For $\tau >{\tau }^{*}$ and for any parameter $x\in {\mathbb{R}}^d$, we have

$$\begin{array}{c}\hfill \parallel {\mathcal{H}}_{\tau }(x)-x^{*}{\parallel }_2^2\le (1+\alpha ){\parallel x-x^{*}\parallel }_2^2,\end{array}$$

where $\alpha =\frac{2\sqrt{{\tau }^{*}}}{\sqrt{\tau -{\tau }^{*}}}$ and ${\tau }^{*}={\parallel x^{*}\parallel }_0$.

Lemma 2.

A differentiable convex function $f_i(x):{\mathbb{R}}^d\to \mathbb{R}$ is restricted $l_s$-strongly smooth with parameter s, i.e., there exists a generic constant $l_s>0$ such that for any $x_1$, $x_2$ with $\parallel x_1-x_2{\parallel }_0\le s$ and

$$f_i(x_1)-f_i(x_2)-\langle \nabla f_i(x_2),x_1-x_2\rangle \le \frac{l_s}{2}{\parallel x_1-x_2\parallel }^2,$$

then we have:

$$\parallel \nabla f_i(x_1)-\nabla f_i(x_2){\parallel }^2\le 2l_s(f_i(x_1)-f_i(x_2)+\langle \nabla f_i(x_2),x_2-x_1\rangle ).$$

The above two inequalities also hold for the global smoothness parameter $l_d$.

The proof of Lemma 2 can be found in Appendix A.3.

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$, ⋯, 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)}=argmi{n}_x{f}_i(x_{t,k}^{(i)})+\langle g_{t,k}^{(i)},x-x_{t,k}^{(i)}\rangle +\frac{1}{2{\gamma }_t}{\parallel x-x_{t,k}^{(i)}\parallel }^2$ for $k\in \{0,\dots ,K-1\}$, i.e.,  $x_{t,k+1}^{(i)}=x_{t,k}^{(i)}-{\gamma }_t{g}_{t,k}^{(i)}$. Clients send $x_{t,K}^{(i)}$ for $i\in \left[N\right]$ 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.

Algorithm 1. Federated Hard Thresholding (Fed-HT)

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)}=\nabla f_{I_{t,k}^{(i)}}(x_{t,k}^{(i)})$            $x_{t,k+1}^{(i)}=x_{t,k}^{(i)}-{\gamma }_t{g}_{t,k}^{(i)}$         end for     end for     $x_{t+1}={\mathcal{H}}_{\tau }({\sum }_{i=1}^N{p}_i{x}_{t,K}^{(i)})$ end for

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 }^{*}={\parallel x^{*}\parallel }_0$, and suppose $f(x)$ satisfies Assumptions 1 and 2. The condition number ${\kappa }_d=\frac{l_d}{{\rho }_d}\ge 1$. Let stepsize ${\gamma }_t=\frac{1}{6l_d}$ and the batch size $b_{t,k}^{(i)}=\frac{{\Gamma }_1}{{\omega }_1^t}$, ${\Gamma }_1\ge \frac{{\xi }_1{\sum }_{i=1}^N{p}_i{\sigma }_i^2}{{\delta }_1{\parallel x_0-x^{*}\parallel }^2}$, ${\delta }_1=\alpha {(1-\frac{1}{12{\kappa }_d})}^K$, $\alpha =\frac{2\sqrt{{\tau }^{*}}}{\sqrt{\tau -{\tau }^{*}}}$, the sparsity level $\tau \ge (16{(12{\kappa }_d-1)}^2+1){\tau }^{*}$. Then the following inequality holds for the Fed-HT:

$$\begin{array}{cc}\hfill E[\parallel x_T-x^{*}{\parallel }^2]& \le {\theta }_1^T{\parallel x_0-x^{*}\parallel }^2+g_1(x^{*}).\hfill \end{array}$$

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}{1-{\psi }_1}{\parallel \nabla f(x^{*})\parallel }^2$, ${\psi }_1=(1+\alpha ){(1-\frac{1}{12{\kappa }_d})}^K$, ${\xi }_1=\frac{(1+\alpha )(1-{(1-\frac{1}{12{\kappa }_d})}^K){\kappa }_d}{l_d^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 $\parallel \nabla f(x^{*})\parallel$ 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.

Corollary 1.

If all the conditions in Theorem 1 hold, for a given precision $ϵ>0$, we need at most $T\le C_{1}log(\frac{\parallel x_0-x^{*}\parallel }{ϵ})$ rounds to obtain

$$E[\parallel x_T-x^{*}{\parallel }^2]\le ϵ+g_1(x^{*}),$$

where $C_1=-{(log({\theta }_1))}^{-1}$, ${\theta }_1=(1+2\alpha ){(1-\frac{1}{12{\kappa }_d})}^K\in (0,1)$, and  $g_1(x^{*})=\frac{{\xi }_1{\mathcal{B}}^2}{1-{\psi }_1}{\parallel \nabla f(x^{*})\parallel }^2$.

Remark 2.

Corollary 1 indicates that under proper conditions and with sufficient rounds, the estimation error of the Fed-HT is determined by the second term—the statistical bias term—which we denote as $g_1(x^{*})$. The term $g_1(x^{*})$ can become small if $x^{*}$ is sufficiently close to an unconstrained minimizer of $f(x)$, so it represents the sparsity-induced bias to the solution of the unconstrained optimization problem. The upper bound result guarantees that the Fed-HT can closely approach $x^{*}$ arbitrarily under a sparsity-induced bias, and the speed of approaching the biased solution is linear (or geometric) and determined by ${\theta }_1$. In Theorem 1 and Corollary 1, ${\theta }_1$ is closely related to the number of local updates K. The condition number ${\kappa }_d>1$, so $(1-\frac{1}{12{\kappa }_d})<1$. When K is larger, ${\theta }_1$ is smaller, so is the number of rounds T required for reaching a target ϵ. In other words, the Fed-HT converges faster with fewer communication rounds. However, the bias term $g_1(x^{*})$ will increase when K increases. Therefore, K should be chosen to balance the convergence rate and statistical bias.

We further investigate how the objective function $f(x)$ approaches the optimal $f(x^{*})$.

Corollary 2.

If all the conditions in Theorem 1 hold, let ${∆}_1=l_d{\parallel x_0-x^{*}\parallel }^2$, and $g_2(x^{*})=O(\parallel \nabla f(x^{*}){\parallel }^2)$, we have

$$E[f(x_T)-f(x^{*})]\le {\theta }_1^T{∆}_1+g_2(x^{*}).$$

The proof details can be found in Appendix A.5.

Because the local updates on each device are based on SGD with dense parameters, without the HT operator, $l_d$-smoothness and ${\rho }_d$-strongly convexity are required, which depend on dimension d and are stronger requirements for f. Furthermore, $\parallel \nabla f(x^{*})\parallel \le d\parallel f(x^{*}){\parallel }_{\infty }$, i.e., $g_1(x^{*})$ and $g_2(x^{*})$ are $O(d^2\parallel f(x^{*}){\parallel }_{\infty }^2)$, which are suboptimal compared with the results for traditional IHT methods in terms of dimension d. In order to solve such drawbacks, we develop a new algorithm in the next section.

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[\parallel x_T-x^{*}{\parallel }^2]$ in the following theorem.

Algorithm 2. Federated Iterative Hard Thresholding (FedIter-HT)

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)}=\nabla 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)})$         end for     end for     $x_{t+1}={\mathcal{H}}_{\tau }({\sum }_{i=1}^N{p}_i{x}_{t,K}^{(i)})$ end for

Theorem 2.

Let $x^{*}$ be the optimal solution to (2), ${\tau }^{*}={\parallel x^{*}\parallel }_0$, and suppose $f(x)$ satisfies Assumptions 1 and 2. The condition number ${\kappa }_s=\frac{l_s}{{\rho }_s}\ge 1$. Let stepsize ${\gamma }_t=\frac{1}{6l_s}$ and the batch size $b_{t,k}^{(i)}=\frac{{\Gamma }_2}{{\omega }_2^t}$, ${\Gamma }_2\ge \frac{{\xi }_2{\sum }_{i=1}^N{p}_i{\sigma }_i^2}{{\delta }_2{\parallel x_0-x^{*}\parallel }^2}$, ${\delta }_2=(2\alpha +3{\alpha }^2){(1-\frac{1}{12{\kappa }_s})}^K$, $\alpha =\frac{2\sqrt{{\tau }^{*}}}{\sqrt{\tau -{\tau }^{*}}}$, the sparsity level $\tau \ge (\frac{16}{{(\sqrt{\frac{12{\kappa }_s}{12{\kappa }_s-1}}-1)}^2}+1){\tau }^{*}$. Then, the following inequality holds for the FedIter-HT:

$$\begin{array}{cc}\hfill E[\parallel x_T-x^{*}{\parallel }^2]& \le {\theta }_2^T{\parallel x_0-x^{*}\parallel }^2+g_3(x^{*}).\hfill \end{array}$$

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{\mathcal{B}}^2}{1-{\psi }_2}{\parallel {\pi }_{\tilde{\mathcal{I}}}(\nabla f(x^{*}))\parallel }^2$, ${\xi }_2=\frac{{(1+\alpha )}^2(1-{(1-\frac{1}{12{\kappa }_s})}^K){\kappa }_s}{l_s^2}$, ${\psi }_2={(1+\alpha )}^2{(1-\frac{1}{12{\kappa }_s})}^K$, $\alpha =\frac{2\sqrt{{\tau }^{*}}}{\sqrt{\tau -{\tau }^{*}}}$, $\widetilde{{\mathcal{I}}^i}=supp\left({\mathcal{H}}_{2\tau }\left(\nabla f_i\left({\mathit{x}}^{*}\right)\right)\right)\cup supp\left({\mathit{x}}^{*}\right)$ and $\tilde{\mathcal{I}}=supp\left({\mathcal{H}}_{2N\tau }\left(\nabla f\left({\mathit{x}}^{*}\right)\right)\right)\cup supp\left({\mathit{x}}^{*}\right)$.

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 }^{*}}}\le {(\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 τ 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. The statistical bias term $g_3(x^{*})$ can be much smaller than $g_1(x^{*})$ in Theorem 1 because $g_3(x^{*})$ only depends on the norm of $\nabla f(x^{*})$ restricted to the support $\tilde{\mathcal{I}}$ of size $2N\tau +{\tau }^{*}$. Because the norm of the gradient is a dominating term in $g_1$ and $g_3$, slightly increasing K does not significantly vary the statistical bias terms (when $d\gg 2N\tau +{\tau }^{*}$).

Using the results in Theorem 2, we can further derive Corollary 3 to specify the number of rounds required to achieve a given estimation precision.

Corollary 3.

If all the conditions in Theorem 2 hold, for a given $ϵ>0$, the FedIter-HT requires the most $T\le C_{2}log(\frac{\parallel x_0-x^{*}\parallel }{ϵ})$ rounds to obtain

$$E[\parallel x_T-x^{*}{\parallel }^2]\le ϵ+g_3(x^{*}),$$

where $C_2=-{(log({\theta }_2))}^{-1}$.

Because $g_3(x^{*})=O(\parallel {\pi }_{\tilde{\mathcal{I}}}(\nabla f(x^{*})){\parallel }^2)$, and we also know $\parallel {\pi }_{\tilde{\mathcal{I}}}(\nabla f(x^{*})){\parallel }^2\le {(2N\tau +{\tau }^{*})}^2{\parallel \nabla f(x^{*})\parallel }_{\infty }^2$ and $2N\tau +{\tau }^{*}\ll d$ in high dimensional statistical problems, the result in Corollary 3 gives a tighter bound than the one obtained in Corollary 1. Similarly, we also obtain a tighter upper bound for the convergence performance of the objective function $f(x)$.

Corollary 4.

If all the conditions in Theorem 2 hold, let ${∆}_2=l_s{\parallel x_0-x^{*}\parallel }^2$, and $g_4(x^{*})=O(\parallel {\pi }_{\tilde{\mathcal{I}}}(\nabla f(x^{*})){\parallel }^2)$, we have

$$E[f(x_T)-f(x^{*})]\le {\theta }_2^T{∆}_2+g_4(x^{*}).$$

The proof details can be found in Appendix A.7.

The theorem and corollaries developed in this section only depend on the $l_s$-restricted smoothness and ${\rho }_s$-restricted strong convexity, where $s=2\tau +{\tau }^{*}$, which are the same conditions used in the analysis of existing IHT methods. Moreover, $\parallel {\pi }_{\tilde{\mathcal{I}}}(\nabla f(x^{*}))\parallel \le (2N\tau +{\tau }^{*}){\parallel \nabla f(x^{*})\parallel }_{\infty }$, which means $g_3(x^{*})$ and $g_4(x^{*})$ are $O({(2N\tau +{\tau }^{*})}^2\parallel \nabla f(x^{*}){\parallel }_{\infty }^2)$, where $2N\tau +{\tau }^{*}$ is the size of support $\tilde{\mathcal{I}}$. Therefore, our results match the current best-known upper bound for the statistic bias term compared with the results for traditional IHT methods.

Statistical Analysis for M-Estimators

Due to the good property of the FedIter-HT, we also study its constrained M-estimators derived from more concrete learning formulations. Although we focus on the sparse linear regression and sparse logistic regression in this paper, our method can be used to analyze other statistical learning problems as well.

Sparse Linear Regression can be formulated as follows:

$$\begin{array}{cc}\hfill \underset{x\in {\mathbb{R}}^d}{min}f(x)& =\frac{1}{N}\sum _{i=1}^N\frac{1}{B}{\parallel Y^{(i)}-Z^{(i)}x\parallel }_2^2,\hfill \\ \hfill & {\mathrm{subject}\mathrm{to}\parallel x\parallel }_0\le \tau ,\hfill \end{array}$$

where $Z^{(i)}\in {\mathbb{R}}^{B\times d}$ is a design matrix associated with client i. For each row of matrix $Z^{(i)}$, we further assume that they are independently drawn from a sub-Gaussian distribution with parameter ${\beta }^{(i)}$, $Y^{(i)}=Z^{(i)}{x}^{*}+{ϵ}^{(i)}$ denotes the response vector, and ${ϵ}^{(i)}\in {\mathbb{R}}^B$ is a noise vector following Normal distribution $N(0,{\sigma }^{2}I)$, $x^{*}\in {\mathbb{R}}^d$ with $\parallel x^{*}{\parallel }_0={\tau }^{*}$ is the underlying sparse regression coefficient vector.

Corollary 5.

If all the conditions in Theorem 2 hold, with $B\ge C_1\tau log(d){max}_i\left\{{({\beta }^{(i)})}^2\right\}$ and a sufficiently large number of communication rounds T, we have

$$\begin{array}{cc}\hfill E[\parallel x_T-x^{*}{\parallel }^2]& \le O(\frac{(2N\tau +{\tau }^{*}){\sigma }^2{\mathcal{B}}^2{({\sum }_{i=1}^N{\beta }^{(i)})}^{2}log(d)}{NB})\hfill \end{array}$$

with a probability of at least $(1-exp(-C_{5}NB))$, where $C_5$ is a universal constant.

Proof. 

Let $Z=[Z^{(1)};\dots ;Z^{(N)}]\in {\mathbb{R}}^{NB\times d}$ be the overall design matrix of the linear regression problem, and each row of Z can be treated as drawn IID from a sub-Gaussian distribution with parameter ${\sum }_{i=1}^N{\beta }^{(i)}$. $ϵ=[{ϵ}^{(1)};\dots ;{ϵ}^{(N)}]\in {\mathbb{R}}^{NB\times 1}$ is the random Gaussian noise. Then Lemma C.1 in [45] immediately implies that $f_i$ is restricted ${\rho }_s$-strongly convex and restricted $l_s$-strongly smooth with ${\rho }_s=\frac{4}{5}$ and $l_s=\frac{6}{5}$, respectively, with a probability of at least $(1-exp(-C_{2}B))$ if the total sample size $B\ge C_1\tau log(d){max}_i\left\{{({\beta }^{(i)})}^2\right\}$, where $C_1$ and $C_2$ are universal constants. Furthermore, we know that $\parallel \nabla f(x^{*}){\parallel }_{\infty }={\parallel \frac{Z^Tϵ}{NB}\parallel }_{\infty }\le C_3\sigma {\sum }_{i=1}^N{\beta }^{(i)}\sqrt{\frac{log(d)}{NB}}$, with a probability of at least $(1-exp(-C_{4}NB))$, where $C_3,C_4$ are universal constants. Gathering everything together yields the following bound with a high probability.    □

Sparse Logistic Regression can be formulated as follows:

$$\begin{array}{cc}\hfill \underset{x}{min}f(x)& =\frac{1}{N}\sum _{i=1}^N\frac{1}{B}\sum _{j=1}^B(log(1+exp(z_{i,j}^{T}x))-y_{i,j}{z}_{i,j}^{T}x)\hfill \\ \hfill & {\mathrm{subject}\mathrm{to}\parallel x\parallel }_0\le \tau ,\hfill \end{array}$$

where $z_{i,j}\in {\mathbb{R}}^d$ for $j\in \left[B\right]$ is a predictive vector and drawn from a sub-Gaussian distribution associated with client i, each observation $y_{i,j}$ on client i is drawn from the Bernoulli distribution $\mathbb{P}(y_{i,j}|z_{i,j},x^{*})=\frac{exp(z_{i,j}^T{x}^{*})}{1+exp(z_{i,j}^T{x}^{*})}$, and $x^{*}\in {\mathbb{R}}^d$ with $\parallel x^{*}{\parallel }_0={\tau }^{*}$ is the underlying true parameter that we want to recover.

Corollary 6.

If all the conditions in Theorem 2 hold, $\parallel z_{i,j}\parallel \le \mathcal{K}$, $C_{lower}\le exp(z_{i,j}^{T}x)/{(1+exp(z_{i,j}^{T}x))}^2\le C_{upper}$ for $i\in \left[N\right]$ and $j\in \left[B\right]$ and $B\ge C_7\tau {\mathcal{K}}^{2}log(d)$ and with a sufficiently large number of communication rounds T, we have

$$\begin{array}{cc}\hfill E[\parallel x_T-x^{*}{\parallel }^2]& \le O(\frac{(2N\tau +{\tau }^{*}){\mathcal{B}}^2{\mathcal{K}}^{2}log(d)}{NB})\hfill \end{array}$$

with a probability of at least $(1-exp(-C_{6}NB)-C_{9}exp(-C_{10}log(d))+\frac{C_9}{exp(C_{6}NB)exp(C_{10}log(d))})$, where $C_6$, $C_9$ and $C_{10}$ are constants.

Proof. 

If we further assume $\parallel z_{i,j}\parallel \le \mathcal{K}$ and $C_{lower}\le exp(z_{i,j}^{T}x)/{(1+exp(z_{i,j}^{T}x))}^2\le C_{upper}$ for $i\in \left[N\right]$ and $j\in \left[B\right]$, the sparse logistic regression objective function is restricted ${\rho }_s$-strongly convex and restricted $l_s$-strongly smooth with ${\rho }_s=\frac{4}{5}{C}_{lower}$ and $l_s=\frac{6}{5}{C}_{upper}$, respectively, with a probability of at least $(1-exp(-C_{6}B))$ if $B\ge C_7\tau {\mathcal{K}}^{2}log(d)$, where $C_{lower}$, $C_{upper}$, $C_6$ and $C_7$ are constants. Furthermore, according to Corollary 2 in [46], we have $\parallel \nabla f(x^{*}){\parallel }_{\infty }\le C_8\mathcal{K}\sqrt{log(d)/NB}$ with a probability of at least $(1-C_{9}exp(-C_{10}log(d))$, where $C_8$, $C_9$ and $C_{10}$ are universal constants. Therefore, we can obtain the following corollary. Based on the above result, the estimation error specified in terms of the distances $x_T$ and $x^{*}$ decreases when the total sample size $NB$ is large or the dissimilarity level $\mathcal{B}$ and the dimension d are small.    □

5. Experiments

We empirically evaluate our methods in both simulations and on three real-world datasets: E2006-tfidf, RCV1 and MNIST (

Table 2. Statistics of three real-world datasets in the federated setting.

Dataset	Samples	Dimension	Samples Per Device
			Mean	Stdev
E2006-tfidf	3308	150,360	33.8	9.1
RCV1	20,242	47,236	202.4	114.5
MNIST	60,000	784	600	–

, which are downloaded from the LibSVM website (https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/, accessed on 1 July 2022)), and compare them against a baseline method. The baseline method is a standard Distributed IHT and communicates every local update to the central server, which then aggregates and broadcasts back to clients (see Appendix A.1 for more details). Specifically, experiments for simulation I and on the E2006-tfidf dataset are conducted for sparse linear regression. We solve the sparse logistic regression problem in simulation II and for the RCV1 data set. The last experiment uses MNIST data in a multi-class softmax regression problem. The exact loss functions for the various problems are available in the Appendix A.2.

Following the convention in the federated learning literature, we use the number of communication rounds to measure the communication cost. For a comprehensive comparison, we also include the number of iterations. For both synthetic and real-world datasets, algorithm parameters are determined by the following criteria. The number of local iterations K is searched from $\{3,5,8,10\}$. We have tested the performance of our proposed algorithms under different K conditions (see Figure 1). The stepsize $\gamma$ for each algorithm is set by a grid search from $\{10,1,0.6,0.3,0.1,0.06,0.03,0.01,0.001\}$. All the algorithms are initialized with $x^{(0)}=0$. The sparsity $\tau$ is 500 for the MNIST dataset and 200 for the other two datasets.

5.1. Simulations

To generate synthetic data, we follow a similar setup to that in [37]. In simulation I, for each device $i\in \left[100\right]$, we generate samples $(z_{i,j},y_{i,j})$ for $j\in \left[100\right]$ according to $y_{i,j}=z_{i,j}^T{x}_i+b_{i,j}$, where $z_{i,j}\in {\mathbb{R}}^{1000}$, $x_i\in {\mathbb{R}}^{1000}$. The first 100 elements of $x_i$ are drawn from $\mathcal{N}(u_i,1)$ and the remaining elements in $x_i$ are zeros, $b_{i,j}\sim \mathcal{N}(u_i,1)$, $u_i\sim \mathcal{N}(0.1,\alpha )$, $z_{i,j}\sim \mathcal{N}(v_i,\mathsf{\Sigma })$, where $\mathsf{\Sigma }$ is a diagonal matrix with the i-th diagonal element equal to $\frac{1}{i^{1.2}}$. Each element in the mean vector $v_i$ is drawn from $\mathcal{N}(B_i,1)$, $B_i\sim \mathcal{N}(0,\beta )$. Therefore, $\alpha$ controls how much the local models differ from each other, and $\beta$ controls how much the local on-device data differ between one another; hence, we have simulated Non-IID federated data. In simulation I, $(\alpha ,\beta )\in \{(0.1,0.1),(0.5,0.5),(1,1)\}$. The data generation procedure for simulation II is the same as the procedure of simulation I, except that $y_{i,j}^{\prime }=exp(z_{i,j}^T{x}_i+b_{i,j})/(1+exp(z_{i,j}^T{x}_i+b_{i,j}))$; then, for the i-th client, we set $y_{i,j}=1$ corresponding to the top 100 of $y_{i,j}^{\prime }$ for $j\in \left[1000\right]$; otherwise, $y_{i,j}=0$. In simulation II, we also set $(\alpha ,\beta )\in \{(0.1,0.1),(0.5,0.5),(1,1)\}$.

The results in Figure 2 show that, with a higher degree of Non-IID, both Fed-HT and FedIter-HT tend to converge slower. We also compare the proposed methods with the baseline method—Distributed IHT. In Figure 3, we observe that in simulation I, FedIter-HT only needs 20 (∼$5\times$ less) communication rounds to reach the same objective value that the Distributed-IHT obtains with more than 100 communication rounds; in simulation II, the FedIter-HT needs 50 communication rounds (∼$4\times$ less) to achieve the same objective value that the Distributed-IHT obtains with 200 communication rounds.

5.2. Benchmark Datasets

We use the E2006-tfidf dataset [47] to predict the volatility of stock returns based on the SEC-mandated financial text report, represented by tf-idf. It was collected from thousands of publicly traded U.S. companies, for which data from different companies are inherently non-identical and the privacy consideration for financial data demands federated learning. The RCV1 dataset [48] is used to predict categories of newswire stories recently collected by Reuters, Ltd. The RCV1 can be naturally partitioned based on the news category and used for federated learning experiments since readers may only be interested in one or two categories of news. Our model training process mimics the personalized privacy-preserving news recommender system where we use the K-means method to partition the datasets, respectively, into 10 clusters. Each device randomly selects two of the clusters for use in the learning. We run t-SNE to visualize the hidden structures found by K-means as shown in Figure 4 and Figure 5, respectively, for the E2006-tfidf dataset (sparse linear regression) and the RCV1 dataset (sparse logistic regression). For the MNIST images, there are 10 digits that automatically serve as the clusters.

For all datasets, the data in each cluster are evenly partitioned into 20 parts, and each client randomly picks two clusters and selects one part of data from each of the clusters. Because the MNIST images are evenly collected for each digit, the partitioned decentralized MNIST data are balanced in terms of categories, whereas the other two datasets are unbalanced.

Figure 6 shows that our proposed Fed-HT and FedIter-HT can significantly reduce the communication rounds required to achieve a given accuracy. In Figure 6a,c, we further notice that federated learning displays more randomness when approaching the optimal solution. This may be caused by dissimilarity across clients. For instance, the three different algorithms in Figure 6c reach the neighborhood of different solutions at the end, where the proposed FedIter-HT obtains the lowest objective value. These behaviors may be worth exploring further in the future.

6. Conclusions

In this paper, we propose two communication-efficient federated IHT methods—Fed-HT and FedIter-HT—to deal with ${\ell }_0$-norm regularized sparse learning with decentralized non-IID data. The Fed-HT algorithm is designed to impose a hard thresholding operator at a central server, whereas the FedIter-HT applies this operator at each update regardless of local clients or a central server. Both methods reduce communication costs—in both the communication rounds and the communication load at each round. Theoretical analyses show a linear convergence rate for both algorithms where the Fed-HT has a better convergence rate $\theta$, but the FedIter-HT has a better statistical estimation bias. Similar to the conventional IHT methods with IID data, there is still a guarantee to recover the best sparse estimator even with decentralized non-IID data. They outperform the traditional Distributed-IHT in simulations and on benchmark datasets, according to empirical findings.