How to solve a problem that Lasso plus a l-2 regularizer?

Question

The problem is a that:

$\min_{t\in \mathbb{R^n}} \{\Vert t-b\Vert_2^2 + \lambda_1\Vert t\Vert_1 + \lambda_2 \Vert t\Vert_2\}$.

Does it have a closed form solution? If not, how to solve it efficiently?

Answer 1

Yes, it does. I prefer to change the parameters slightly to avoid unnecessary fractions and indices, so I'll minimize $\|t-b\|_2^2+2\lambda\|t\|_1+2\mu\|t\|_2$ (assuming $\lambda,\mu> 0$).

Notice that it makes no sense to have opposite signs for $t_i$ and $b_i$ because you can flip and get a smaller value. Thus we can just consider the case when everything is in the positive cone ($t_i,b_i\ge 0$).

The problem is that $\|t\|_2$ doesn't split into a sum of functions of one coordinate. To overcome this difficulty, notice that $2x=\min_{a>0}(ax^2+a^{-1})$. Thus, we will introduce an extra parameter and consider the minimization problem $$ \|t-b\|_2^2+2\lambda\|t\|_1+a\mu\|t\|_2^2+\mu a^{-1}\to\min $$ Now, for fixed $a$, the minimization in $t$ is a piece of cake: in each coordinate we have to minimize $$ (a\mu+1)t_i^2-2(b_i-\lambda)t_i+b_i^2 $$ over $t_i\ge 0$. The answer is $$ t_i=0\text{ if }b_i\le\lambda; \qquad t_i=\frac{b_i-\lambda}{a\mu+1}\text{ if }b_i>\lambda $$ Now the whole sum evaluates to $$ \operatorname{const}+\mu a^{-1}-\frac{U}{a\mu+1}, \text{ where }U=\sum_{i:b_i>\lambda}(b_i-\lambda)^2 $$ Thus all we need is to minimize $\mu a^{-1}-\frac U{a\mu+1}$. When $\mu^2\ge U$, this expression obviously stays positive for all $a>0$ and tends to $0$ as $a\to+\infty$, so we should send $a$ to infinity, which results in $t=0$. Otherwise, taking the derivative we get $$ \mu a^{-2}=\mu U(a\mu+1)^{-2} $$ i.e. $$ \mu+a^{-1}=\sqrt{U} $$ and, finally, $$ a=(\sqrt U-\mu)^{-1} $$ That's all!