Expressing the LASSO regression constraint via the penalty parameter

Question

Given the two equivalent formulations of the problem for LASSO regression, $\min(RSS + \lambda\sum|\beta_i|)$ and $\min(RSS)$ such that $\sum|\beta_i|\leq t$, how can we express the one-to-one correspondence between $\lambda$ and $t$?

Answer 1

The answer to your question follows from consideration of Lagrangian duality. This is worked in the post which I consider to be a duplicate in my comment to OP's post. In what follows, I work out what I find to be a more insightful derivation.

When we're solving a lasso, really, we're trying trying to jointly minimize $\frac{1}{2n} \|y - X \beta\|_2^2 = RSS$ and $\|\beta\|_1$. That is, we seek $\arg\min_\beta (\frac{1}{2n} \|y - X \beta\|_2^2, \|\beta\|_1)$. This doesn't seem well defined at the moment, since we know there's some tension between these two objectives. This is what optimization folks call multicriterion optimization. Let's visualize this problem by plotting $\left(\frac{1}{2n} \|y - X \beta\|_2^2, \|\beta\|_1 \right)$ for many $\beta$'s. (Note, here $p=5$, $n=100$, $X$ was randomly initialized, and the true coefficient $\beta^*$ has a roughly a quarter of it's entries equal to zero.)

Here, $F = \|\beta\|_1$ and $G = \frac{1}{2n} \|y - X \beta\|_2^2$. That is, the vertical axis measures the lack of fit, and the horizontal axis measures the size of the coefficient. Note that I cut off the top of the image for the sake of clarity.

The points at the bottom left of the plot are the ones we're interested in. Those correspond to the values of $\beta$ that both have small $\ell_1$ norm and have small error. In fact, for those points at the bottom left, there are no $\beta$ which have the same fit and smaller size or the same size with better fit. To choose between these points, called pareto optimal points, we need to determine the relative importance of the fit and size, our two objectives. This should remind us of the tuning parameters $\lambda$ or $C$ in the unconstrained or constrained lasso, respectively. Below we plot in green some lasso solutions, computed from glmnet, imposed on the above graph.

Notice that lasso found exactly the pareto optimal points. This is very surprising, though! How did a multidimensional objective get optimized by a one dimensional objective? The process is called scalarization: we take weights $\mu_1, \mu_2 \geq 0$ and form the problem $$\arg\min_{\beta \in \mathbb{R}^p} \mu_1 \left( \frac{1}{2n} \|y-X\beta\|_2^2 \right) + \mu_2 \|\beta\|_1.$$ When both objectives are convex, which they are here, this scalarized problem finds all pareto optimal points.

Assuming $\mu_1 \neq 0$, which is assuming that both objectives are being considered, and writing $\lambda = \frac{\mu_2}{\mu_1}$, we have that this is just $\hat{\beta}^\textrm{unc} = \arg\min_{\beta \in \mathbb{R}^p} \frac{1}{2n} \|y-X\beta\|_2^2 + \lambda \|\beta\|_1,$ the lasso, in it's usual form. By lagrangian duality, we know that there exists from $C$ so that we can instead solve the equivalent problem $\hat{\beta}^\textrm{con} = \arg\min_{\beta : \|\beta\|_1 \leq C} \frac{1}{2n} \|y-X\beta\|_2^2,$ where $\hat{\beta}^\textrm{con} = \hat{\beta}^\textrm{unc}$.

Now that we understand better what we're trying to solve and have a good visualization, let's now focus on finding a relationship between the tuning parameters $\lambda$ and $C$.

For a given value of $C$, the constrained lasso estimate $\hat{\beta}^\textrm{con.}$ will be one of those green points in the plot above. The way $\hat{\beta}^\textrm{con.}$ can be found is by fixing ourselves at $\|\beta\|_1 = \mathrm{min}\{C, \|\hat{\beta}_\mathrm{LS}\|_1\}$ (for $\hat{\beta}_\mathrm{LS}$ the least squares coefficient) and moving down until we get the lowest possible measure of lack of fit. That is, $$C = \|\hat{\beta}^\textrm{unc}\|_1.$$ As we saw above, $\lambda$ corresponds to a scalarization of our vector objective and hence is equal to the slope at this point: $$\lambda = -\frac{\partial \frac{1}{2n} \|y - X \beta\|_2^2}{\partial \|\beta\|_1} \mid_{\beta = \hat{\beta}^\textrm{con}}$$ (Note, this formula appears to be only correct up to constants. The correct $\lambda$ can quickly be found from the first order conditions, but I'd like to find a way to motivate it directly from this framework.) This corresponds (via the chain rule) to the first answer in the post that I linked as a possible duplicate.