One-to-one correspondence between penalty parameters of equivalent formulations of penalised regression methods

Question

Ridge, LASSO and Elastic Net are three very popular methods of penalised regressions. All of these have more than one formulations. For example, two formulations for Ridge are:

1. minimise $\lVert Y - X \beta \rVert _ 2 ^ 2 + \lambda \lVert \beta \rVert _ 2 ^ 2$ with respect to $\beta$
2. minimise $\lVert Y - X \beta \rVert _ 2 ^ 2$ with respect to $\beta$ subject to $\lVert \beta \rVert _ 2 ^ 2 \leq t$

I'm following The Elements of Statistical Learning, and there it is claimed that there's a one-to-one correspondence between $\lambda$ and t (refer to Pg. 63). Though not explicitly stated (or I've missed somehow), the same claim is implied for the other two methods also.

I (intuitively) understand the equivalence between the two formulations. If we want to shrink the estimates more, the $L_2$ will be smaller, and we will use lower value of t in the $2 ^ {nd}$ formulation. And, in the $1 ^ {st}$ one, we'll use a higher value of $\lambda$, as that will increase the objective function and hence to minimise the penalty, the estimates will be shrinked. Hence, the claim is intuitive, but I don't know the proof of it. This thread is very related to my question, but it didn't derive the one-to-one correspondence.

My question is how to derive that one-to-one correspondence. I can't find any reference for this. Derivation for any one of these three will be sufficient, as I can then do the other two myself.

In case it matters, I'm interested in this relationship, because as far as I understand the R package glmnet considers penalties in form of the $1 ^ {st}$ formulation only. I'd like to impose a penalty in form of $2 ^ {nd}$ formulation, where the value of t is known to me. I asked a related question in Stack Overflow.

Thanks.

Update

Both of the first two answers try to prove that the two forms are theoretically equivalent. I understand that equivalence, and this thread is not about that. I am specifically looking for the one-to-one correspondence to apply it in a practical problem where I need to use the $2^{nd}$ form based on domain knowledge, with a specified value of t. Since Ridge have a closed form solution, theoretically it is possible to solve $\lambda$ from $\lVert(X^TX+\lambda I)^{-1}X^Ty\rVert=t$. But it does not seem to me as an easy equation to be solved, and I do not think such an equation can be obtained for the other two methods (LASSO and Elastic Net), as they do not have a closed form solution. Also, varying $\lambda$ to get many solutions of the $1^{st}$ form and choosing that solution such that it's $L_2$ norm is closest to t does not seem to be an ideal method.

Answer 1

According to Karush–Kuhn–Tucker conditions and this post, the first problem is equivalent to the second problem, and $t = ||\hat\beta||^2$, $\hat\beta = (X^TX+\lambda I)^{-1}X^TY$, so $t=Y^TX(X^TX+\lambda I)^{-2}X^TY$. Then we only need to prove $t$ is an one-to-one function of $\lambda$.

Suppose $T_1=X^TX+\lambda_1 I$, $T_2=X^TX+\lambda_2 I=T_1+\lambda_0I$ where $\lambda_0 = \lambda_2-\lambda_1>0$, then $t(\lambda_2)-t(\lambda_1)=Y^TX(T_2^{-2}-T_1^{-2})X^TY$. Note that $T_1$ and $T_2$ are positive definite.

$T_2^{-2}-T_1^{-2}=T_2^{-2}(I-(T_1+\lambda_0I)^2T_1^{-2})=-T_2^{-2}(\lambda_0^2T_1^{-2}+2\lambda_0T_1^{-1})<0$. Thus $t(\lambda_2)<t(\lambda_1)$.

Actually $t(\lambda)$ is monotone decreasing as you indicated.

Answer 2

Assume that the solution of your problem $(1)$ is $\beta_\lambda^*$, where index $\lambda$ indicates dependence on a particular value of $\lambda$.

The second problem is solved using Langrange multipliers ($\mu$) and considering KKT conditions, one of which is that $\mu(\Vert \beta\Vert^2 -t) =0$.

Set $t$ in the KTT condition above to the value of the solution of problem $(1)$, that is, $t = \Vert \beta_\lambda^*\Vert^2 $. Then $\mu=\lambda$ and $\beta = \beta_\lambda^*$ satisfy KKT conditions for $(2)$, that is, the problems share the same solution. Once again, the correspondence between $\lambda^*$ and $t$ is $t = \Vert \beta_\lambda^*\Vert^2 $.

I'm providing only a condensed conclusion from the (great) answers with proofs and detailed explanations, which can be found here:

https://math.stackexchange.com/questions/335306/why-are-additional-constraint-and-penalty-term-equivalent-in-ridge-regression/336618#336618

To answer the question on correspondence between $\mu$ and $t$ one has to solve $t = \Vert \beta_\lambda^*\Vert^2 $.

To do that, use the solution to problem $(1)$:

$$ \beta_\lambda^* = (X^TX+\lambda I)^{-1}X^Ty. $$

In other words, for a given $t$, one needs to find a $\lambda$ such that $$ [(X^TX+\lambda I)^{-1}X^Ty]^T (X^TX+\lambda I)^{-1}X^Ty = t $$

what establishes the desired correspondence.

Note that $t$ needs to be less than $1$, see here: How to find regression coefficients $\beta$ in ridge regression? and here: Ridge regression formulation as constrained versus penalized: How are they equivalent?