Iteration complexity analysis of random coordinate descent methods for $\ell_0$ regularized convex problems

Introduction

where function $f$ is smooth and convex and the quasinorm of $x$ is defined as:

2 Notations and preliminaries

The function $f$ has (block) coordinatewise Lipschitz continuous gradient with constants $L_{i}>0$ for all $i\in[N]$, i.e. the convex function $f$ satisfies the following inequality for all $i\in[N]$:

An immediate consequence of Assumption 1 is the following relation :

Characterization of local minima

In this section we present the necessary optimality conditions for problem (1) and provide a detailed description of local minimizers. First, we establish necessary optimality conditions satisfied by any local minimum. Then, we separate the set of local minima into restricted classes around the set of global minimizers. The next theorem provides conditions for obtaining local minimizers of problem (1):

For the first implication, we assume that $z$ is a local minimizer of problem (1) on the open ball $\mathcal{B}_{\infty}(z,r)$, i.e. we have:

Based on Assumption 1 it follows that $f$ has also global Lipschitz continuous gradient, with constant $L_{f}$, and thus we have:

Taking $\alpha=\min\{\frac{1}{L_{f}},\frac{r}{\max\limits_{j\in I(z)}\lvert\nabla_{(j)}f(z)\rvert}\}$ and $y=z-\alpha\nabla_{I(z)}f(z)$, we obtain:

Therefore, we have $\nabla_{I(z)}f(z)=0$, which means that:

Clearly, for any $d\in\mathcal{B}_{\infty}(0,r)\backslash S_{I(y)}$, with $r=\underline{y}$, we have:

Let $d\in\mathcal{B}_{\infty}(0,r)\backslash S_{I(y)}$, with $r=\min\left\{\underline{y},\frac{\underline{\lambda}}{\lVert\nabla f(y)\rVert_{1}}\right\}$. The convexity of function $f$ and the Holder inequality lead to:

We now assume that $z$ satisfies (3). For any $x\in\mathcal{B}_{\infty}(z,r)\cap S_{I(z)}$ we have $\lVert x-z\rVert_{\infty}<\underline{z}$, which by (4) implies that $\lvert x_{(i)}\rvert>0$ whenever $\lvert z_{(i)}\rvert>0$. Therefore, we get:

We denote with $\mathcal{T}_{f}$ the set of all local minima of problem (1), i.e.

and we call them basic local minimizers. It is not hard to see that when the function $f$ is strongly convex, the number of basic local minima of problem (1) is finite, otherwise we might have an infinite number of basic local minimizers.

We additionally impose the following assumptions on each function $u_{i}$.

(iv) There exists $\mu_{i}$ such that $0<\mu_{i}\leq M_{i}-L_{i}$ and

Note that a similar set of assumptions has been considered in , where the authors derived a general framework for the block coordinate descent methods on composite convex problems. Clearly, Assumption 3 $(iv)$ implies the upper bound (6) and in this inequality is replaced with the assumption of strong convexity of $u_{i}$ in the first argument.

We now provide several examples of approximation versions of the objective function $f$ which satisfy Assumption 3.

It satisfies Assumption 3, in particular condition $(iv)$ holds for $\mu_{i}=M_{i}-L_{i}$. This type of approximations was used by Nesterov for deriving the random coordinate gradient descent method for solving smooth convex problems and further extended to the composite convex case in [NecCli:13, 25].

2. General quadratic approximation: given $H_{i}\succeq 0$, such that $H_{i}\succ L_{i}I_{n_{i}}$ for all $i\in[N]$, we define the approximation version

It satisfies Assumption 3, in particular condition $(iv)$ holds for $\mu_{i}=\sigma_{\min}(H_{i}-L_{i}I_{n_{i}})$ (the smallest eigenvalue). This type of approximations was used by Luo, Yun and Tseng in deriving the greedy coordinate descent method based on the Gauss-Southwell rule for solving composite convex problems .

It satisfies Assumption 3, in particular condition $(iv)$ holds for $\mu_{i}=\beta_{i}$. This type of approximation functions was used especially in the nonconvex settings .

Based on each approximation function $u_{i}$ satisfying Assumption 3, we introduce a class of restricted local minimizers for our nonconvex optimization problem (1).

For any set of approximation functions $u_{i}$ satisfying Assumption 3, a vector $z$ is called an u-strong local minimizer for problem (1) if it satisfies:

Moreover, we denote the set of strong local minima, corresponding to the approximation functions $u_{i}$, with $\mathcal{L}_{u}$.

and thus an u-strong local minimizer $z\in\mathcal{L}_{u}$, has the property that each block $z_{i}$ is a fixed point of the operator defined by the minimizers of the function $u_{i}(y_{i};z)+\lambda_{i}\lVert y_{i}\rVert_{0}$, i.e. we have for all $i\in[N]$:

Let the set of approximation functions $u_{i}$ satisfy Assumption 3, then any $u-$strong local minimizer is a local minimum of problem (1), i.e. the following inclusion holds:

From Definition 5 and Assumption 3 we have:

we have from the definition of $I(z)$ that

and thus $0\leq-\frac{1}{2M_{i}}\|\nabla_{(j)}f(z)\|^{2}$ or equivalently $\nabla_{(j)}f(z)=0$. Since this holds for any $j\in I(z)\cap\mathcal{S}_{i}$, it follows that $z$ satisfies $\nabla_{I(z)}f(z)=0$. Using now Theorem 2 we obtain our statement. ∎

\begin{cases}\lvert\nabla_{(j)}f(z)\rvert\leq\sqrt{2\lambda_{i}M_{i}},&\text{if}\ z_{(j)}=0\\ \lvert z_{(j)}\rvert\geq\sqrt{\frac{2\lambda_{i}}{M_{i}}},&\text{if}\ z_{(j)}\neq 0,\quad\forall i\in[N] and j\in\mathcal{S}_{i}.\end{cases}

The relations given in $(ii)$ can be derived based on the separable structure of the approximation $u_{i}^{q}(y_{i};x,M_{i})$ and of the quasinorm $\|\cdot\|_{0}$ using similar arguments as in Lemma 3.2 from . For completeness, we present the main steps in the derivation. First, it is clear that any $z\in\mathcal{L}_{u^{q}}$ satisfies:

for all $j\in\mathcal{S}_{i}$ and $i\in[N]$. On the other hand since the optimum point in the previous optimization problems can be $0$ or different from $0$, we have:

Let Assumption 1 hold and $u^{1},u^{2}$ be two approximation functions satisfying Assumption 3. Additionally, let

Assume $z\in\mathcal{X}^{*}$, i.e. it is a global minimizer of our original nonconvex problem (1). Then, we have:

and thus $z\in\mathcal{L}_{u^{1}}$, i.e. we proved that $\mathcal{X}^{*}\subseteq\mathcal{L}_{u^{1}}$. Therefore, any class of $u$-strong local minimizers contains the global minima of problem (1).

Further, let us take $z\in\mathcal{L}_{u^{1}}$. Using Definition (5) and defining

This shows that $z\in\mathcal{L}_{u^{2}}$ and thus $\mathcal{L}_{u^{1}}\subseteq\mathcal{L}_{u^{2}}$. ∎

Note that if the following inequalities hold

using the Lipschitz gradient relation (2), we obtain that

Therefore, from Theorem 7 we observe that $u^{q}\ (u^{Q})$-strong local minimizers for problem (1) are included in the class of all basic local minimizers $\mathcal{T}_{f}$. Thus, designing an algorithm which converges to a local minimum from $\mathcal{L}_{u^{q}}$ ($\mathcal{L}_{u^{Q}}$) will be of interest. Moreover, $u^{e}$-strong local minimizers for problem (1) are included in the class of all $u^{q}\ (u^{Q})$-strong local minimizers. Thus, designing an algorithm which converges to a local minimum from $\mathcal{L}_{u^{e}}$ will be of interest. To illustrate the relationships between the previously defined classes of restricted local minima and see how much they are related to global minima of (1), let us consider an example.

Random coordinate descent type methods

In order to find a local minimizer of problem (1), we introduce the family of random block coordinate descent iterative hard thresholding (RCD-IHT) methods, whose iteration is described as follows:

Choose a (block) coordinate $i_{k}\in[N]$ with uniform probability

Set $x^{k+1}_{i_{k}}=T^{u}_{i_{k}}(x^{k})$ and $x^{k+1}_{i}=x^{k}_{i}\;\;\forall i\neq i_{k}$.

then the iteration of (RCD-IHT) method becomes:

for all $j\in\mathcal{S}_{i_{k}}$. Note that if at some iteration $\lambda_{i_{k}}=0$, then the iteration of algorithm (RCD-IHT) is identical with the iteration of the usual random block coordinate gradient descent method [NecCli:13, 22]. Further, our algorithm has, in this case, similarities with the iterative hard thresholding algorithm (IHTA) analyzed in . For completeness, we also present the algorithm (IHTA).

or equivalently for each component we have the update:

Then, it can be seen that the iteration of (RCD-IHT) in the scalar case for the exact approximation $u_{i}^{e}(y_{i};x,\beta_{i})$ has the following form:

In general, if the function $f$ satisfies Assumption 1, computing $v^{i_{k}}(x^{k})$ at each iteration of (RCD-IHT) requires the minimization of an unidimensional convex smooth function, which can be efficiently performed using unidimensional search algorithms. Let us analyze the least squares settings in order to highlight the simplicity of the iteration of algorithm (RCD-IHT) in the scalar case for the approximation $u_{i}^{e}(y_{i};x,\beta_{i})$.

where $r=Ax-b$. Under these circumstances, the iteration of (RCD-IHT) has the following closed form expression:

In the sequel we use the following notations for the entire history of index choices, the expected value of objective function $f$ w.r.t. the entire history and for the support of the sequence $x^{k}$:

Due to the randomness of algorithm (RCD-IHT), at any iteration $k$ with $\lambda_{i_{k}}>0$, the sequence $I^{k}$ changes if one of the following situations holds for some $j\in\mathcal{S}_{i_{k}}$:

In other terms, at a given moment $k$ with $\lambda_{i_{k}}>0$, we expect no change in the sequence $I^{k}$ of algorithm (RCD-IHT) if there is no index $j\in\mathcal{S}_{i_{k}}$ satisfying the above corresponding set of relations $(i)$ and $(ii)$. We define the notion of change of $I^{k}$ in expectation at iteration $k$, for algorithm (RCD-IHT) as follows: let $x^{k}$ be the sequence generated by (RCD-IHT), then the sequence $I^{k}=I(x^{k})$ changes in expectation if the following situation occurs:

which implies (recall that we consider uniform probabilities for the index selection):

In the next section we show that there is a finite number of changes of $I^{k}$ in expectation generated by algorithm (RCD-IHT) and then, we prove global convergence of this algorithm, in particular we show that the limit points of the generated sequence converges to strong local minima from the class of points $\mathcal{L}_{u}$.

Global convergence analysis

In order to prove almost sure convergence results for our family of algorithms, we use the following supermartingale convergence lemma of Robbins and Siegmund (see e.g. ):

Let $v_{k},u_{k}$ and $\alpha_{k}$ be three sequences of nonnegative random variables satisfying the following conditions:

where ${\cal F}_{k}$ denotes the collections $v_{0},\dots,v_{k},u_{0},\dots,u_{k}$, $\alpha_{0},\dots,\alpha_{k}$. Then, we have $\lim_{k\to\infty}v_{k}=v$ for a random variable $v\geq 0$ a.s. and $\sum_{k=0}^{\infty}u_{k}<\infty$ a.s.

Further, we analyze the convergence properties of algorithm (RCD-IHT). First, we derive a descent inequality for this algorithm.

Let $x^{k}$ be the sequence generated by (RCD-IHT) algorithm. Under Assumptions 1 and 3 the following descent inequality holds:

In conclusion, our family of algorithms belong to the class of descent methods:

Taking expectation w.r.t. $i_{k}$ we get our descent inequality. ∎

We now prove the global convergence of the sequence generated by algorithm (RCD-IHT) to local minima which belongs to the restricted set of local minimizers $\mathcal{L}_{u}$.

Let $x^{k}$ be the sequence generated by algorithm (RCD-IHT). Under Assumptions 1 and 3 the following statements hold:

$(ii)$ At each change of sequence $I^{k}$ in expectation we have the following relation:

where $\delta=\frac{1}{N}\min\left\{\min\limits_{i\in[N]:\lambda_{i}>0}\frac{\mu_{i}\lambda_{i}}{M_{i}},\min\limits_{i\in[N],j\in{\mathcal{S}}_{i}\cap\text{supp}(x^{0})}\frac{\mu_{i}}{2}|x^{0}_{(j)}|^{2}\right\}>0.$

$(iii)$ The sequence $I^{k}$ changes a finite number of times as $k\to\infty$ almost surely. The sequence $\lVert x^{k}\rVert_{0}$ converges to some $\lVert x^{*}\rVert_{0}$ almost surely. Furthermore, any limit point of the sequence $x^{k}$ belongs to the class of strong local minimizers $\mathcal{L}_{u}$ almost surely.

On the other hand, given $j\in\text{supp}(T^{u}_{i}(x))$, from the definition of $T^{u}_{i}(x)$ we get:

Subtracting $\lambda_{i}\lVert y^{+}_{i}-U_{(j)}y^{+}_{(j)}\rVert_{0}$ from both sides, leads to:

Further, if we apply the Lipschitz gradient relation given in Assumption 3 $(iii)$ in the right hand side and use the optimality conditions for the unconstrained problem solved at each iteration, we get:

Combining with the left hand side of (15) we get:

Replacing $x=x^{k}$ for $k\geq 0$, it can be easily seen that, for any $j\in\text{supp}(x^{k}_{i})$ and $i\in[N]$, we have:

Further, assume that at some iteration $k>0$ a change of sequence $I^{k}$ in expectation occurs. Thus, there is an index $j\in[n]$ (and block $i$ containing $j$) such that either $\left(x^{k}_{(j)}=0\ \text{and}\ \left(T^{u}_{i}(x^{k})\right)_{(j)}\neq 0\right)$ or $\left(x^{k}_{(j)}\neq 0\ \text{and}\ \left(T^{u}_{i}(x^{k})\right)_{(j)}=0\right)$. Analyzing these cases we have:

Observing that under uniform probabilities we have:

we can conclude that at each change of sequence $I^{k}$ in expectation we get:

Further, if the sequence $I^{k}$ is constant for $k>K$, then we have $I^{k}=I^{*}$ and $\lVert x^{k}\rVert_{0,\lambda}=\lVert x^{*}\rVert_{0,\lambda}$ for any vector $x^{*}$ satisfying $I(x^{*})=I^{*}$. Also, for $k>K$ algorithm (RCD-IHT) is equivalent with the classical random coordinate descent method , and thus shares its convergence properties, in particular any limit point of the sequence $x^{k}$ is a minimizer on the coordinates $I^{*}$ for $\min_{x\in S_{I^{*}}}f(x)$. Therefore, if the sequence $I^{k}$ is fixed, then we have for any $k>K$ and $i_{k}\in I^{k}$:

On the other hand, denoting with $x^{*}$ an accumulation point of $x^{k}$, taking limit in (17) and using that $\lVert x^{k}\rVert_{0,\lambda}=\lVert x^{*}\rVert_{0,\lambda}$ as $k\to\infty$, we obtain the following relation:

for all $i\in[N]$ and thus $x^{*}$ is the minimizer of the previous right hand side expression. Using the definition of local minimizers from the set $\mathcal{L}_{u}$, we conclude that any limit point $x^{*}$ of the sequence $x^{k}$ belongs to this set, which proves our statement. ∎

It is important to note that the classical results for any iterative algorithm used for solving nonconvex problems usually state global convergence to stationary points, while for our algorithms we were able to prove global convergence to local minima of our nonconvex and NP-hard problem (1). Moreover, if $\lambda_{i}=0$ for all $i\in[N]$, then the optimization problem (1) becomes convex and we see that our convergence results cover also this setting.

Rate of convergence analysis

where $\theta\in(0,1)$. Using the strong convexity property for $f$ we have:

In order to derive the rate of convergence in probability for algorithm (RCD-IHT), we first define the following notion which is a generalization of relations (8) and (3) for $u_{i}(y_{i},x)=u_{i}^{q}(y_{i},x,M_{i})$ and $u_{i}(y_{i},x)=u_{i}^{e}(y_{i},x,\beta_{i})$, respectively:

We make the following assumption on functions $u_{i}$ and consequently on $\Delta^{i}(x)$:

There exist some positive constants $C_{i}$ and $D_{i}$ such that the approximation functions $u_{i}$ satisfy for all $i\in[n]$:

Note that if $f$ is strongly convex, then the set $\mathcal{T}_{f}$ of basic local minima has a finite number of elements. Next, we show that this assumption holds for the most important approximation functions $u_{i}$ (recall that $u_{i}^{q}=u_{i}^{Q}$ in the scalar case $n_{i}=1$).

Under Assumption 1 the following statements hold: $(i)$ If we consider the separable quadratic approximation $u_{i}(y_{i};x)=u_{i}^{q}(y_{i};x,M_{i})$, then:

$(i)$ For the separable quadratic approximation $u_{i}(y_{i};x)=u_{i}^{q}(y_{i};x,M_{i})$, using the definition of $\Delta^{i}(x)$ and $v^{i}(x)$ given in (20)–(21) (see also (8)), we get:

Then, since $\lVert\nabla_{i}f(x)-\nabla_{i}f(z)\rVert\leq L_{f}\lVert x-z\rVert$ and using the property of the norm $|\lVert a\rVert-\lVert b\rVert|\leq\lVert a-b\rVert$ for any two vectors $a$ and $b$, we obtain:

$(ii)$ For the exact approximation $u_{i}(y_{i};x)=u_{i}^{e}(y_{i};x,\beta_{i})$, using the definition of $\Delta^{i}(x)$ and $v^{i}(x)$ given in (20)–(21) (see also (3)), we get:

Then, using the triangle inequality we derive the following relation:

In order to bound $\Delta^{i}(x)-\Delta^{i}(z)$, it is sufficient to find upper bounds on $\lvert\delta_{1i}(x,z)\rvert$ and $\lvert\delta_{2i}(x,z)\rvert$. For a bound on $\lvert\delta_{1i}(x,z)\rvert$ we use $\lvert\delta_{1i}(x,y)\rvert=\max\{\delta_{1i}(x,y),-\delta_{1i}(x,y)\}$. Using the optimality conditions for the map $v^{i}(x)$ and convexity of $f$ we obtain:

where in the last inequality we used the Cauchy-Schwartz inequality. On the other hand, from the global Lipschitz continuous gradient inequality we get:

In order to obtain a bound on $-\delta_{1i}(x,z)$ we observe that:

where in the last inequality we used the Lipschitz gradient relation and Cauchy-Schwartz inequality. Also, from the convexity of $f$ and the Cauchy-Schwartz inequality we get:

Combining now the bounds (24) and (25) we obtain:

Therefore, from (23) and (26) we obtain a bound on $\delta_{1i}(x,z)$:

Regarding the second quantity $\delta_{2i}(x,z)$, we observe that:

From the upper bounds on $\lvert\delta_{1i}(x,z)\rvert$ and $\lvert\delta_{2i}(x,z)\rvert$ given in (27) and (28), respectively, we obtained our result. ∎

We further show that the second part of Assumption 13 holds for the most important approximation functions $u_{i}$.

Under Assumption 1 the following statements hold: $(i)$ Considering the separable quadratic approximation $u_{i}(y_{i};x)=u_{i}^{q}(y_{i};x,M_{i})$, then for any fixed $z\in\mathcal{T}_{f}$ there exist only two values of parameter $M_{i}$ satisfying $\lvert\Delta^{i}(z)-\lambda_{i}\rvert=0$. $(ii)$ Considering the exact approximation $u_{i}(y_{i};x)=u_{i}^{e}(y_{i};x,\beta_{i})$, then for any fixed $z\in\mathcal{T}_{f}$, there exists a unique $\beta_{i}$ satisfying $\lvert\Delta^{i}(z)-\lambda_{i}\rvert=0$.

$(i)$ For the approximation $u_{i}(y_{i};x)=u_{i}^{q}(y_{i};x,M_{i})$ we have:

Thus, we observe that $\Delta^{i}(z)=\lambda_{i}$ is equivalent with the following relation:

which is valid for only two values of $M_{i}$.

$(ii)$ For the approximation $u_{i}(y_{i};x)=u_{i}^{e}(y_{i};x,\beta_{i})$ we have:

where $v^{i}_{\beta}(z)$ and $h^{i}_{\beta}(z)$ are defined as in (20) corresponding to the exact approximation. Without loss of generality, we can assume that there exist two constants $\beta_{i}>\gamma_{i}>0$ such that $\Delta^{i}(z)=\lambda_{i}$. In other terms, we have:

We analyze two possible cases. Firstly, if $z_{i}=0$, then the above equality leads to the following relation:

which implies that $\beta_{i}\leq\gamma_{i}$, that is a contradiction. Secondly, assuming $z_{i}\neq 0$ we observe from optimality of $h^{i}_{\beta}(z)$ that:

On the other hand, taking into account that $z\in\mathcal{T}_{f}$ we have:

From (29) and (30) we get $\beta_{i}\leq\gamma_{i}$, thus implying the same contradiction. ∎

Let $x^{k}$ be the sequence generated by the family of algorithms (RCD-IHT) under Assumptions 1, 3 and 13 and the additional assumption of strong convexity of $f$ with parameter $\sigma$. Denote with $\kappa$ the number of changes in expectation of $I^{k}$ as $k\to\infty$. Let $x^{*}$ be some limit point of $x^{k}$ and $\rho>0$ be some confidence level. Considering the scalar case $n_{i}=1$ for all $i\in[n]$, the following statements hold:

$(i)$ From (12) and Theorem 12 $(ii)$ it can be easily seen that:

i.e. we have proved the first part of our theorem.

$(ii)$ In order to establish the linear rate of convergence in probability of algorithm (RCD-IHT), we first derive a bound on the number of iterations performed between two changes in expectation of $I^{k}$. Secondly, we also derive a bound on the number of iterations performed after the support is fixed (a similar analysis for deterministic iterative hard thresholding method was given in ). Combining these two bounds, we obtain the linear convergence of our algorithm. Recall that for any $p\in[\kappa]$, at iteration $k_{p}+1$, there is a change in expectation of $I^{k_{p}}$, i.e.

Assume that the number of iterations performed between two changes in expectation satisfies:

We show that under relation (33), the probability (31) does not hold. First, we observe that between two changes in expectation of $I^{k}$, i.e. $k\in[k_{p-1}+1,k_{p}]$, the algorithm (RCD-IHT) is equivalent with the randomized version of coordinate descent method for strongly convex problems. Therefore, the method has linear rate of convergence (18), which in our case is given by the following expression:

for all $k\in[k_{p-1}+1,k_{p}]$. Taking $k=k_{p}$, if we apply the complexity estimate (19) and use the bound (33), we obtain:

From the Markov inequality, it can be easily seen that we have:

Let $i\in[N]$ such that $\lambda_{i}>0$. From Assumption 13 and definition of parameter $\xi$ we see that the event $\lVert x^{k_{p}}-\hat{x}^{*}\rVert<\xi$ implies:

The first and the last terms from the above inequality further imply:

or equivalently $I^{k_{p}+1}=\hat{I}^{*}=\left\{j\in[n]:\lambda_{j}=0\right\}\cup\left\{i\in[n]:\lambda_{i}>0,\lvert\Delta^{i}(\hat{x}^{*})\rvert>\lambda_{i}\right\}$. In conclusion, if (33) holds, then we have:

Applying the same procedure as before for iteration $k=k_{p}-1$ we obtain:

Considering the events $\{I^{k_{p}}=\hat{I}^{*}\}$ and $\{I^{k_{p}+1}=\hat{I}^{*}\}$ to be independent (according to the definition of $k_{p}$), we have:

Therefore, between two changes of support the number of iterations is bounded by:

where we used the inequality $\log(1-t)\leq-t$ for any $t\in(0,\ 1)$. Denoting with $k_{\kappa}$ the number of iterations until the last change of support, we have:

Once the support is fixed (i.e. after $k_{\kappa}$ iterations), in order to reach some $\epsilon$-local minimum in probability with some confidence level $\rho$, the algorithm (RCD-IHT) has to perform additionally another

iterations, where we used again (19) and Markov inequality. Taking into account that the iteration $k_{\kappa}$ is the largest possible integer at which the support of sequence $x^{k}$ could change, we can bound:

Adding up this quantity and the upper bound on $k_{\kappa}$, we get that the algorithm (RCD-IHT) has to perform at most

iterations in order to attain an $\epsilon$-suboptimal point with probability at least $\rho$, which proves the second statement of our theorem. ∎

Random data experiments on sparse learning

In this section we analyze the practical performances of our family of algorithms (RCD-IHT) and compare them with that of algorithm (IHTA) . We perform several numerical tests on sparse learning problems with randomly generated data. All algorithms were implemented in Matlab code and the numerical simulations are performed on a PC with Intel Xeon E5410 CPU and 8 Gb RAM memory.

Sparse learning represents a collection of learning methods which seek a tradeoff between some goodness-of-fit measure and sparsity of the result, the latter property allowing better interpretability. One of the models widely used in machine learning and statistics is the linear model (least squares setting). Thus, in the first set of tests we consider sparse linear formulation:

where $x$ denotes a parameter vector. Then, for a set of $m$ independently drawn data samples $\{(a_{i},y_{i})\}_{i=1}^{m}$, the joint likelihood can be written as a function of $x$. To find the maximum likelihood estimate one should maximize the likelihood function, or equivalently minimize the negative log-likelihood (the logistic loss):

where now $f$ is strongly convex with parameter $\nu$. For simulation, data were uniformly random generated and we fixed the parameters $\nu=0.5$ and $\lambda=0.2$. Once an instance of random data has been generated, we ran 10 times our algorithms (RCC-IHT-$u^{q}$) and (RCD-IHT-$u^{e}$) and algorithm (IHTA) starting from 10 different initial points. We reported in Table 3 the best results of each algorithm obtained over all 10 trials, in terms of best function value that has been attained with associated sparsity and number of iterations. In order to report relevant information, we have measured the performance of coordinate descent methods (RCD-IHT-$u^{q}$) and (RCD-IHT-$u^{e}$) in terms of full iterations obtained by dividing the number of all iterations by the dimension $n$. The column $F^{*}$ denotes the final function value attained by the algorithms, $\lVert x^{*}\rVert_{0}$ represents the sparsity of the last generated point and iter (full-iter) represents the number of iterations (the number of full iterations). Note that our algorithms (RCD-IHT-$u^{q}$) and (RCD-IHT-$u^{e}$) have superior performance in comparison with algorithm (IHTA) on the reported instances. We observe that algorithm (RCD-IHT-$u^{e}$) performs very few full iterations in order to attain best function value amongst all three algorithms. Moreover, the number of full iterations performed by algorithm (RCD-IHT-$u^{e}$) scales up very well with the dimension of the problem.

References