Iterative hard thresholding methods for $l_0$ regularized convex cone programming

Abstract

In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer. Also, we establish the iteration complexity of the IHT method for finding an ${{\epsilon }}$-local-optimal solution. We then propose a method for solving $l_0$ regularized convex cone programming by applying the IHT method to its quadratic penalty relaxation and establish its iteration complexity for finding an ${{\epsilon }}$-approximate local minimizer. Finally, we propose a variant of this method in which the associated penalty parameter is dynamically updated, and show that every accumulation point is a local izer of the problem.

Appendix

In this appendix we show that if $f$ is smooth strongly convex, there exists $L>L_f$ such that $\alpha >0$, which is required in Theorem 3.5. In particular, we will show that there exist at most $3n2^{n-1}$ number of $L$ such that $\alpha =0$; in other words, $\alpha >0$ for almost all $L>0$ except at most $3n2^{n-1}$ number of points. Therefore, $\alpha >0$ is almost sure for a randomly chosen $L$ and an arbitrary $L>L_f$ may be sufficient for practical implementation of the IHT method for solving problem (12).

To this aim, assume that $f$ is smooth strongly convex, which is imposed in Theorem 3.5, and let $\alpha$ be defined in (29). We now show that $\alpha >0$ for almost all $L>0$ except at most $3n2^{n-1}$ values. For simplicity, we only consider the case where $-\infty <l_i<0$ and $0<u_i<\infty$ for all $i$. The proof is similar for the other cases. Let $\mathcal{B }_I,\,\Pi _\mathcal{B }(\cdot )$ and $s_L(\cdot )$ be defined in (15)–(17), respectively. Given any $I \subseteq \{1,\ldots ,n\}$ and $1 \le i \le n$, let

$$\begin{aligned} h_i(L;I):=\left[ s_L\left( x^*\right) \right] ^2_i -\left[ \Pi _{\mathcal{B }}\left( s_L\left( x^*\right) \right) -s_L\left( x^*\right) \right] ^2_i -\frac{2\lambda }{L}, \end{aligned}$$

where $x^* \in {\mathrm{Arg}}\min \{f(x): x\in \mathcal{B }_I\}$. Clearly, $h_i(L;I)$ is well-defined since $x^*$ is unique for each $I$ due to the strongly convexity of $f$. Notice that $\alpha$ as defined in (29) can be rewritten as

$$\begin{aligned} \alpha = \min \limits _{I \subseteq \{1,\ldots ,n\}} \min \limits _{i} |h_i(L;I)|. \end{aligned}$$

(66)

As we will later show, for each $I \subseteq \{1,\ldots ,n\},\,h_i(L;I)=0$ has at most two positive roots $L$ for every $i\in I$ and at most one positive root $L$ for any $i \notin I$. This together with (66) implies that for each $I \subseteq \{1,\ldots ,n\}$ there exist at most

$$\begin{aligned} n_I \ :=\ 2|I|+n-|I| \ = \ n+|I| \end{aligned}$$

number of $L$ such that $\alpha =0$, where $|I|$ denotes the size of $I$. Therefore, the total number of $L$ such that $\alpha =0$ is at most

$$\begin{aligned} \sum \limits _{I \subseteq \{1,\ldots ,n\}} n_I = \sum ^n_{|I|=0} n_I \left( \begin{array}{c} n \\ |I| \end{array} \right) = 3n2^{n-1}. \end{aligned}$$

It remains to show that for each $I \subseteq \{1,\ldots ,n\},\,h_i(L;I)=0$ has at most two positive roots $L$ for every $i\in I$ and at most one positive root $L$ for any $i \notin I$. We prove this result by considering all possible cases below. Let $i\in \{1,\ldots ,n\}$ and $x^* =\arg \min \{f(x): x\in \mathcal{B }_I\}$.

• (1) ${[\nabla f(x^*)]}_i=0$: one can see that ${[s_L(x^*)]}_i=x^*_i$. Hence, ${[\Pi _{\mathcal{B }}(s_L(x^*))]}_i= x^*_i$ and $h_i(L;I)=(x^*_i)^2-\frac{2\lambda }{L}$. It follows that $h_i(L;I)=0$ has at most one positive root $L$.

• (2) ${[\nabla f(x^*)]}_i \ne 0$: by the first-order optimality condition for $x^* = \arg \min \{f(x): \ x\in \mathcal{B }_I\}$, one can observe that if $i \notin I$ and ${[\nabla f(x^*)]}_i < 0$, then $x^*_i=u_i$; if $i \notin I$ and ${[\nabla f(x^*)]}_i > 0$, then $x^*_i=l_i$. Hence, this case can be divided into three subcases:

  • (2a) $i\in I$: it follows that $x^*_i=0$ and ${[s_L(x^*)]}_i = -\frac{1}{L} \nabla _i f(x^*)$. Let

    $$\begin{aligned} \theta = \max \left( -\frac{\nabla _i f(x^*)}{l_i},-\frac{\nabla _i f(x^*)}{u_i}\right) \!. \end{aligned}$$

    One can observe that

    $$\begin{aligned} {[s_L(x^*)]}_i \in \left\{ \begin{array}{l@{\quad }l} {[l_i,u_i]} &{} \ \text{ if } \ L > \theta , \\ (-\infty ,l_i] &{} \ \text{ if } \ 0 < L \le \theta \ \text{ and } \ \nabla _i f(x^*)>0, \\ {[u_i, \infty )} &{} \ \text{ if } \ 0 < L \le \theta \ \text{ and } \ \nabla _i f(x^*)<0. \end{array}\right. \end{aligned}$$

    It follows that

    $$\begin{aligned} {[\Pi _\mathcal{B }(s_L(x^*))]}_i =\left\{ \begin{array}{ll} {[s_L(x^*)]}_i &{} \ \text{ if } \ L > \theta , \\ l_i &{} \ \text{ if } \ 0< L \le \theta \ \text{ and } \ \nabla _i f(x^*)>0, \\ u_i &{} \ \text{ if } \ 0< L \le \theta \ \text{ and } \ \nabla _i f(x^*)<0. \end{array}\right. \end{aligned}$$

    Using this relation and ${[s_L(x^*)]}_i = -\frac{1}{L} \nabla _i f(x^*)$, we have

    $$\begin{aligned} h_i(L;I) = \left\{ \begin{array}{ll} \frac{1}{L^2} {[\nabla _i f(x^*)]}^2 - \frac{\lambda }{2L}, &{} \text{ if } \ L > \theta , \\ -l^2_i - \frac{2l_i\nabla _i f(x^*)}{L}- \frac{\lambda }{2L}, &{}\ \text{ if } \ 0< L \le \theta \ \text{ and } \ \nabla _i f(x^*)>0, \\ -u^2_i - \frac{2u_i\nabla _i f(x^*)}{L}- \frac{\lambda }{2L}, &{}\ \text{ if } \ 0<L \le \theta \ \text{ and } \ \nabla _i f(x^*)<0. \end{array}\right. \end{aligned}$$

    Therefore, one can see that $h_i(L;I)=0$ has at most two positive roots $L$.

  • (2b) $i\notin I$ and ${[\nabla f(x^*)]}_i < 0$: as mentioned above, $x^*_i=u_i$ holds for this subcase. One can observe that for all $L>0$,

    $$\begin{aligned} {[s_L(x^*)]}_i = x^*_i - \frac{1}{L} \nabla _i f(x^*) > u_i, \end{aligned}$$

    and hence $[\Pi _\mathcal{B }(s_L(x^*))]_i=u_i$. Using this relation and $x^*_i=u_i$, we have

    $$\begin{aligned} h_i(L;I) = u^2_i - \frac{2u_i\nabla _if(x^*)}{L} - \frac{\lambda }{2L}, \ \ \ \forall L>0. \end{aligned}$$

    Thus, $h_i(L;I)=0$ has at most one positive root $L$.

  • (2c) $i\notin I$ and $[\nabla f(x^*)]_i > 0$: as mentioned above, $x^*_i=l_i$ holds for this subcase. By a similar argument as subcase (2b), one can have

    $$\begin{aligned} h_i(L;I) = l^2_i - \frac{2l_i\nabla _if(x^*)}{L} - \frac{\lambda }{2L}, \ \ \ \forall L>0. \end{aligned}$$

    Hence, $h_i(L;I)=0$ has at most one positive root $L$.

Combining all cases above, we obtain the result as desired.