72
$\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$
14
  • $\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, 2011 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, 2011 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, 2011 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, 2011 at 1:31
  • 4
    $\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, 2016 at 13:26

3 Answers 3

87
$\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$.

$\endgroup$
11
  • 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, 2011 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$ Nov 10, 2012 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$ Nov 2, 2013 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, 2018 at 3:20
  • 1
    $\begingroup$ @whuber that's not what I meant. I cant see why this soft thresholding gives us the vertex of the lower parabola. Can you explain it please? $\endgroup$
    – Dennis
    Jun 7, 2021 at 4:34
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.

$\endgroup$
2
  • 1
    $\begingroup$ what happens if we don't have $X$ being orthonormal? $\endgroup$ Oct 8, 2021 at 14:18
  • $\begingroup$ @CharlieParker In practice, I usually the QR transform. So $X = QR$ then $X \beta$ becomes $Q \hat{\beta}$ with $\hat{\beta} = R \beta$. Then, at the end, transform back and check that the original $\beta$ has the sparsity you want. If not, increase $\lambda$ and repeat. Usually, I just find a $\lambda$ that tends to work for my dataset, set it, and deploy. I like the coordinate descent implementation because it can be done in a distributed manner, and oftentimes can be interrupted while still giving me a workable answer. $\endgroup$
    – The Dude
    Feb 23, 2022 at 16:38
1
$\begingroup$

A Proof based on KKT Conditions

Under the orthogonal design matrix assumption $X^\top X = I_{(p)}$, the LS estimate $\hat{\beta} = X^\top y$, whence minimizing $(y - X\beta)^\top(y - X\beta)$ is equivalent to minimizing \begin{align*} & (y - X\beta)^\top(y - X\beta) - y^\top y + \hat{\beta}^\top\hat{\beta} \\ =& \hat{\beta}^\top\hat{\beta} - 2\beta^\top X^\top y - \beta^\top X^\top X\beta \\ =& \hat{\beta}^\top\hat{\beta} - 2\beta^\top\hat{\beta} - \beta^\top\beta \\ =& (\beta - \hat{\beta})^\top(\beta - \hat{\beta}). \end{align*} Therefore the LASSO optimization problem is \begin{align*} & \min_\beta \sum_{j = 1}^p(\beta_j - \hat{\beta}_j)^2, \\ & \text{subject to } \sum_{j = 1}^p |\beta_j| \leq t. \tag{P}\label{1} \end{align*}

The KKT conditions for problem $\eqref{1}$ can be laid out as follows: \begin{align*} & 2(\beta_j - \hat{\beta}_j) + \lambda s_j = 0, 1 \leq j \leq p, \tag{Stationarity}\label{2} \\ & \sum_{j = 1}^p |\beta_j| \leq t, \tag{Primal feasibility}\label{3} \\ & \lambda \geq 0, \tag{Dual feasibility} \label{4} \\ & \lambda\left(\sum_{j = 1}^p|\beta_j| - t\right) = 0. \tag{Complementary Slackness}\label{5} \end{align*}

In $\eqref{2}$, $s_j$ is a subgradient of $f(x) = |x|$ at the point $\beta_j$, hence when $\beta_j \neq 0$, $s_j = \operatorname{sgn}(\beta_j)$, while when $\beta_j = 0$, $s_j$ satisfies $|s_j| \leq 1$ (that means, any $s_j \in [-1, 1]$ is a subgradient of $f(x)$ at $\beta_j = 0$).

Case 1: $\sum |\hat{\beta}_j| \leq t$.

In this case, it is easy to verify that $\lambda = 0, \beta_j = \hat{\beta}_j$ satisfy all the KKT conditions. Since KKT conditions are sufficient for the solution to $\eqref{1}$, $\beta_j = \hat{\beta}_j$ is the LASSO solution.

Case 2: $\sum |\hat{\beta}_j| > t$.

In this case, we first show $\lambda > 0$. Otherwise by $\eqref{4}$, we must have $\lambda = 0$. It then follows by $\eqref{2}$ that $\beta_j = \hat{\beta}_j$, whence $\sum |\beta_j| = \sum|\hat{\beta}_j| > t$, but this violates $\eqref{3}$. Therefore, $\lambda > 0$, which and $\eqref{5}$ then imply $\sum |\beta_j| = t$ (this provides an equation for solving $\lambda$ in terms of $\hat{\beta}_j$, thereby determines the parameter $\gamma$ in the closed-form solution expression, see derivation below).

Denote $\lambda/2 > 0$ by $\gamma$. By $\eqref{2}$, \begin{align*} \beta_j = \hat{\beta}_j - \gamma s_j, 1 \leq j \leq p. \tag{$\dagger$}\label{dagger} \end{align*}

Hence our goal is to show that for each $j \in \{1, \ldots, p\}$. \begin{align*} \beta_j = \hat{\beta}_j - \gamma s_j = \operatorname{sgn}(\hat{\beta}_j)(|\hat{\beta}_j| - \gamma)^+. \tag{$\star$}\label{star} \end{align*}

There are two cases:

Case 2.1: $\beta_j \neq 0$.

If $\beta_j \neq 0$, then $s_j = \operatorname{sgn}(\beta_j)$. It then follows by $\hat{\beta}_j = \beta_j + \gamma\operatorname{sgn}(\beta_j)$ (i.e., $\eqref{dagger}$) and $\gamma > 0$ that $\operatorname{sgn}(\hat{\beta}_j) = \operatorname{sgn}(\beta_j)$. Therefore, using $\eqref{dagger}$ again, we get \begin{align*} \beta_j &= \hat{\beta}_j - \gamma s_j \\ &= \operatorname{sgn}(\hat{\beta}_j)|\hat{\beta}_j| - \gamma\operatorname{sgn}(\beta_j) \\ &= \operatorname{sgn}(\hat{\beta}_j)|\hat{\beta}_j| - \gamma\operatorname{sgn}(\hat{\beta_j}) \\ &= \operatorname{sgn}(\hat{\beta}_j)(|\hat{\beta}_j| - \gamma) \\ &= \operatorname{sgn}(\hat{\beta}_j)(|\hat{\beta}_j| - \gamma)^+. \end{align*} The last equality holds because $\eqref{dagger}$ and $\gamma > 0$ imply that \begin{align*} |\hat{\beta}_j| = |\beta_j + \gamma\operatorname{sgn}(\beta_j)| = |\beta_j| + \gamma > \gamma. \end{align*} Therefore, $\eqref{star}$ holds when $\beta_j \neq 0$.

Case 2.2: $\beta_j = 0$.

If $\beta_j = 0$, then $\eqref{dagger}$ reduces to $\hat{\beta}_j = \gamma s_j$, which implies that (recall that $|s_j| \leq 1$ when $\beta_j = 0$) \begin{align*} |\hat{\beta}_j| = \gamma|s_j| \leq \gamma. \end{align*} Therefore, \begin{align*} \operatorname{sgn}(\hat{\beta}_j)(|\hat{\beta}_j| - \gamma)^+ = 0 = \beta_j. \end{align*} That is, $\eqref{star}$ holds when $\beta_j = 0$.

This completes the proof.


A Geometrical Argument

In the original paper, as the OP quoted, the author claimed that the closed-form solution $\beta_j = \operatorname{sgn}(\hat{\beta}_j)(|\hat{\beta}_j| - \gamma)^+$ are "easily shown". The formal proof, as shown above, is not that easy, so I believe this statement is based on a geometrical intuition outlined as follows (consider the non-trivial Case 2 only).

The feasible region $\mathcal{D} := \{\beta \in \mathbb{R}^p: \sum |\beta_j| \leq t\}$ is a $p$-dimensional diamond, and thanks to the orthogonality assumption, the contours of the objective function $\sum(\beta_j - \hat{\beta}_j)^2$ are spheres in $\mathbb{R}^p$ centered at $\hat{\beta}$. In general, the LASSO solution is the point in $\mathcal{D}$ that has the shortest distance to $\hat{\beta}$ -- it is either some vertex of $\mathcal{D}$ (some $\beta_j$s are $0$) or the projection of $\hat{\beta}$ onto the hyperplane $\mathcal{P}$ containing the diamond face that is closest to $\hat{\beta}$ (all $\beta_j$s are non-zero). If denote $\|\hat{\beta} - \beta\|$ by $d$, then $\gamma$ in $\eqref{star}$ is either $\sqrt{p}^{-1}d$ (when $\beta$ is the projection, see the first graph below) or the maximal length of projections of $\hat{\beta} - \beta$ onto $p$ axes (when $\beta$ is a vertex, see the second graph below). For each case, it can be easily seen from graphs below that the LASSO solution $\beta$ has the unified form $\eqref{star}$.

projection

vertex

$\endgroup$

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