58
$\begingroup$

For the lasso problem $\min_\beta (Y-X\beta)^T(Y-X\beta)$ such that $\|\beta\|_1 \leq t$. I often see the soft-thresholding result $$ \beta_j^{\text{lasso}}= \mathrm{sgn}(\beta^{\text{LS}}_j)(|\beta_j^{\text{LS}}|-\gamma)^+ $$ for the orthonormal $X$ case. It is claimed that the solution can be "easily shown" to be such, but I've never seen a worked solution. Has anyone seen one or perhaps has done the derivation?

$\endgroup$
  • $\begingroup$ This seems slightly confused. At the beginning you assume a constraint $t$ and in the solution you introduce a parameter $\gamma$. I'm guessing you intend these two to be related via the dual problem, but maybe you can make clear what you are looking for. $\endgroup$ – cardinal Nov 1 '11 at 0:41
  • 2
    $\begingroup$ Partially responding to @cardinal, finding the $\beta$ that minimizes $(Y-X\beta )'(Y-X\beta )$ subject to $\|\beta\|_1 \leq t$ is equivalent to finding the $\beta$ that minimizes $(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$. There is a 1-1 relationship between $t$ and $\gamma$. To 'easily' see why the soft-thresholding result is so, I'd recommend solving the second expression (in my comment). $\endgroup$ – user5594 Nov 1 '11 at 1:12
  • 2
    $\begingroup$ Another note, when finding the $\beta$ that minimizes $(Y-X\beta )'(Y-X\beta )+\gamma\sum_j |\beta_j |$, break the problem up into the cases $\beta_j >0$, $\beta_j<0$, and $\beta=0$. $\endgroup$ – user5594 Nov 1 '11 at 1:19
  • 2
    $\begingroup$ @cardinal Ah yes, 1-1 is incorrect. Correction: for every $t\geq0$, you can find a $\gamma\geq 0$. $\endgroup$ – user5594 Nov 1 '11 at 1:31
  • 3
    $\begingroup$ Thanks for a great discussion! I came across this video on coursera - Deriving the lasso coordinate descent update, that is very relevant to this discussion, and walks through the solution very elegantly. Might be helpful for future visitors :-) $\endgroup$ – zorbar May 14 '16 at 13:26
70
$\begingroup$

This can be attacked in a number of ways, including fairly economical approaches via the Karush–Kuhn–Tucker conditions.

Below is a quite elementary alternative argument.

The least squares solution for an orthogonal design

Suppose $X$ is composed of orthogonal columns. Then, the least-squares solution is $$ \newcommand{\bls}{\hat{\beta}^{{\small \text{LS}}}}\newcommand{\blasso}{\hat{\beta}^{{\text{lasso}}}} \bls = (X^T X)^{-1} X^T y = X^T y \>. $$

Some equivalent problems

Via the Lagrangian form, it is straightforward to see that an equivalent problem to that considered in the question is $$ \min_\beta \frac{1}{2} \|y - X \beta\|_2^2 + \gamma \|\beta\|_1 \>. $$

Expanding out the first term we get $\frac{1}{2} y^T y - y^T X \beta + \frac{1}{2}\beta^T \beta$ and since $y^T y$ does not contain any of the variables of interest, we can discard it and consider yet another equivalent problem, $$ \min_\beta (- y^T X \beta + \frac{1}{2} \|\beta\|^2) + \gamma \|\beta\|_1 \>. $$

Noting that $\bls = X^T y$, the previous problem can be rewritten as $$ \min_\beta \sum_{i=1}^p - \bls_i \beta_i + \frac{1}{2} \beta_i^2 + \gamma |\beta_i| \> . $$

Our objective function is now a sum of objectives, each corresponding to a separate variable $\beta_i$, so they may each be solved individually.

The whole is equal to the sum of its parts

Fix a certain $i$. Then, we want to minimize $$ \mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma |\beta_i| \> . $$

If $\bls_i > 0$, then we must have $\beta_i \geq 0$ since otherwise we could flip its sign and get a lower value for the objective function. Likewise if $\bls_i < 0$, then we must choose $\beta_i \leq 0$.

Case 1: $\bls_i > 0$. Since $\beta_i \geq 0$, $$ \mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 + \gamma \beta_i \> , $$ and differentiating this with respect to $\beta_i$ and setting equal to zero, we get $\beta_i = \bls_i - \gamma$ and this is only feasible if the right-hand side is nonnegative, so in this case the actual solution is $$ \blasso_i = (\bls_i - \gamma)^+ = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>. $$

Case 2: $\bls_i \leq 0$. This implies we must have $\beta_i \leq 0$ and so $$ \mathcal L_i = -\bls_i \beta_i + \frac{1}{2}\beta_i^2 - \gamma \beta_i \> . $$ Differentiating with respect to $\beta_i$ and setting equal to zero, we get $\beta_i = \bls_i + \gamma = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)$. But, again, to ensure this is feasible, we need $\beta_i \leq 0$, which is achieved by taking $$ \blasso_i = \mathrm{sgn}(\bls_i)(|\bls_i| - \gamma)^+ \>. $$

In both cases, we get the desired form, and so we are done.

Final remarks

Note that as $\gamma$ increases, then each of the $|\blasso_i|$ necessarily decreases, hence so does $\|\blasso\|_1$. When $\gamma = 0$, we recover the OLS solutions, and, for $\gamma > \max_i |\bls_i|$, we obtain $\blasso_i = 0$ for all $i$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Great writeup @cardinal! $\endgroup$ – Gary Nov 1 '11 at 2:16
  • 9
    $\begingroup$ +1 The entire second half can be replaced by the simple observation that the objective function $\beta\to\frac{1}{2}\beta^2+(\pm\gamma-\hat{\beta})\beta$ is a union of parts of two convex parabolas with vertices at $\pm\gamma-\hat{\beta}$, where the negative sign is taken for $\beta\lt 0$ and the positive otherwise. The formula is just a fancy way of choosing the lower vertex. $\endgroup$ – whuber Nov 1 '11 at 3:12
  • $\begingroup$ If possible, I would like to see the derivations using the KKT-optimality conditions. What other ways are there to derive this result? $\endgroup$ – user1137731 Nov 10 '12 at 20:23
  • 5
    $\begingroup$ @Cardinal: thanks for a nice derivation. One observation. If I recall, matrix with orthogonal columns is not the same as an orthogonal (aka orthonormal) matrix. Then $X'X=D$ for some diagonal matrix $D$ (not necessarily identity matrix). With orthogonal matrix assumption (as is in the original question), we do have $X'X=I$ and all looks great :) $\endgroup$ – Oleg Melnikov Nov 2 '13 at 21:25
  • $\begingroup$ @cardinal I don't get why you say "since otherwise we could flip its sign and get a lower value for the objective function". We are taking the derivative of the objective function. So what if the objective function is higher or lower, who cares. All we care about is the derivative is set to zero, we care about the extrema. Whether it's higher or lower by a constant does not affect the argmin. $\endgroup$ – user13985 Jan 16 '18 at 3:20
7
$\begingroup$

Assume that the covariates $x_j$, the columns of $X \in \mathbb{R}^{n \times p}$, are also standardized so that $X^T X = I$. This is just for convenience later: without it, the notation just gets heavier since $X^T X$ is only diagonal. Further assume that $n \geq p$. This is a necessary assumption for the result to hold. Define the least squares estimator $\hat\beta_{OLS} = \arg\min_\beta \|y - X \beta\|_2^2$. Then, the (Lagrangian form of the) lasso estimator \begin{align*} \hat\beta_\lambda & = \arg\min_{\beta} \frac{1}{2n} \|y - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{defn.} \\ & = \arg\min_\beta \frac{1}{2n} \|X \hat\beta_{OLS} - X \beta\|_2^2 + \lambda \|\beta\|_1 \tag{OLS is projection} \\ & = \arg\min_\beta \frac{1}{2n} \|\hat\beta_{OLS} - \beta\|_2^2 + \lambda \|\beta\|_1 \tag{$X^TX=I$} \\ & = \arg\min_\beta \frac{1}{2} \|\hat\beta_{OLS} - \beta\|_2^2 + n \lambda \|\beta\|_1 \tag{algebra} \\ & = \mathrm{prox}_{n \lambda \|\cdot\|_1} \left( \hat\beta_{OLS} \right) \tag{defn.} \\ & = S_{n \lambda} \left( \hat\beta_{OLS} \right) \tag{takes some work}, \end{align*} where $\mathrm{prox}_f$ is the proximal operator of a function $f$ and $S_{\alpha}$ soft thresholds by the amount $\alpha$.

This is a derivation that skips the detailed derivation of the proximal operator that Cardinal works out, but, I hope, clarifies the main steps that make possible a closed form.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.