3
$\begingroup$

I hope this question wasn't asked before, I was looking for an answer and didn't find one. I'm trying to understand the Ridge regression problem.

If I understand correctly, Ridge regression is trying to solve the following problem:

Given $A \in \mathbb{R}^{n \times d}$, $b \in \mathbb{R}^n$ and $\lambda \in \mathbb{R}$, find $x \in \mathbb{R}^d$ that minimizes:

$(1)$ $arg\,min_{x \in \mathbb{R}^d}(||Ax-b||_2^2+\lambda^2||x||_2^2)$

I'm trying to understand the meaning of $\lambda$. I thought that the above equation is identical to the following equation:

$(2)$ $arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$ s.t. $||x||_2^2 \leq \lambda^2$

But after solving both problems separately in matlab, I got different solutions for $x$.

I solved problem $(1)$ by this formula: $x={(A^TA + \lambda^2 I)}^{-1}A^Tb$.

I solved problem $(2)$ by using $cvx$ library in matlab that is able to solve convex optimization problems.

As I said, in both cases I got different $x$. Are the two problems supposed to be identical? and if not, what change (if possible) should I do to problem $(2)$ so it can be identical to problem $(1)$.

Thanks

$\textbf{Edit:}$

Whoever put the link How exactly to compute the ridge regression penalty parameter given the constraint? for me. Thank you!

It indeed worked in Matlab and I got the same solution for both cases. But I did not expect to get such a strange solution.

Just to make sure I understand since it really looks strange to me.

By the answer in the link, you can actually convert the second problem to this problem:

$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$ s.t. $||x||_2^2 \leq ||x'||_2^2$

where $x'={(A^TA + \lambda^2 I)}^{-1}A^Tb$ is the solution to the first problem.

It looks too trivial/strange since it means that the constraint is actually equal constraint and not 'less than or equal' constraint (the first one is a non-convex problem and the second one is a convex problem).

It also means that you need to solve the first problem and actually find $x$ from the first problem in order to find the same $x$ again in the second problem. which makes no point on solving the second problem.

Does it guarantee that it always finds

$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$ s.t. $||x||_2^2 = ||x'||_2^2$ (non-convex problem)

and not

$arg\,min_{x \in \mathbb{R}^d}||Ax-b||_2^2$ s.t. $||x||_2^2 < ||x'||_2^2$ (convex problem)

Thanks!

$\endgroup$

marked as duplicate by whuber regression Feb 12 at 18:37

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ Probably there is some transformation between the two forms of $\lambda$ that makes the two problems come out the same. Are your two $x$ vectors at least proportional to each other? $\endgroup$ – steveo'america Feb 12 at 18:30
  • 3
    $\begingroup$ That the two problems differ can be appreciated by contemplating what happens as $\lambda$ becomes very large or close to zero. $\endgroup$ – whuber Feb 12 at 18:36
  • $\begingroup$ I just checked it and the two $x$ vectors are not proportional to each other. each coordinate of $x$ in the first solution is scaled by a different number to get the corresponding coordinate in the second $x$. $\endgroup$ – David Feb 12 at 18:37
  • $\begingroup$ I edited my question due to the link above. thanks! $\endgroup$ – David Feb 12 at 21:26
  • $\begingroup$ Re the edit: I suspect you might be interested in the ideas presented in my answer at stats.stackexchange.com/a/301561/919. It seems to be almost the same question, if I understand you correctly. $\endgroup$ – whuber Feb 12 at 21:43