5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi -- you got the answer to your question, in particular I gave you an explicit answer on how to obtain the $t$ from $\lambda$. There has been some positive response to my answer from the community which is an additional evidence that the answer is correct. So my question to you is -- where's the bounty? Thanks. $\endgroup$ – dnqxt May 15 at 18:00
  • $\begingroup$ @dnqxt I'm sorry, but I didn't award the bounty to either of you. As far as I can see, my question is unanswered and I explained it in my comments to your answer and also in the update to my question. As it happened, both the answers got 2 upvotes within bounty period and the 1st one was awarded the bounty automatically. Since you're claiming that your answer is correct (I'll agree completely that it's not wrong), so is the other answer. $\endgroup$ – yarnabrina May 15 at 18:27
  • $\begingroup$ I answer (in a comment) your main specific question about how to establish the correspondence between $t$ an $\lambda$. What else would you expect for an answer? $\endgroup$ – dnqxt May 15 at 18:29
  • $\begingroup$ @dnqxt (contd.) Most certainly your answer was not explicit (not to me, at least), since your method is not generalizable for LASSO or ElasticNet as there's no closed form solution. I mentioned it in comments and the question, and hence I fail to see any reason for awarding +50 bounty. $\endgroup$ – yarnabrina May 15 at 18:30
  • $\begingroup$ Your question in your own words: "My question is how to derive that one-to-one correspondence." I gave you an explicit answer which requires 'search'. Sorry, there are no closed form answers. Moreover, any "generalization" would be a different question and you can ask it separately. $\endgroup$ – dnqxt May 15 at 18:35
2
+25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for responding, but I'm afraid that it does't answer my question. I've already read the thread that you linked, and mentioned in my question. My question was given t, how do we get the value of $\lambda$? The expressions at the beginning of your answer may provide a reverse way, but only for Ridge, as the other two don't have closed form solutions. $\endgroup$ – yarnabrina May 7 at 3:20
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks for responding, but as I commented to the previous answer, I'm looking for an way to get $\lambda$ given t. Given the value of t, I think it's theoretically possible to solve for $\lambda$ from the final equation. However, I don't think that'll be straightforward. Also, for LASSO and elastic net, there's no closed form solution. So, I doubt whether it'll work there or not. $\endgroup$ – yarnabrina May 7 at 14:22
  • $\begingroup$ Note that if $t = \Vert \beta_\lambda^*\Vert^2 $, where $\beta_\lambda^*$ is the solution of the first problem, then to this $t$ corresponds one single $\lambda$ from the first solution. That $\lambda$ has the value of $\alpha$ from your solution $(2)$. $\endgroup$ – dnqxt May 7 at 16:12
  • $\begingroup$ I agree with the unique correspondence, but my question is given a value of t, for example 5, how can I get a value of $\lambda$. The equation is not really trivial to be solved, and for the other two methods, it'll not be possible to get the RHS of your equation as a function of $\lambda$. $\endgroup$ – yarnabrina May 7 at 16:35
  • $\begingroup$ Also, can you please tell me which $\alpha$ you're talking about? $\endgroup$ – yarnabrina May 7 at 16:37
  • 1
    $\begingroup$ The equation is 'solved' by searching on the grid of, say 100, points from zero to one for $\lambda$ and then selecting $\lambda$ that yields the value of that expression closest to $t$. $\endgroup$ – dnqxt May 8 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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