The proof of equivalent formulas of ridge regression

Question

I have read the most popular books in statistical learning

1- The elements of statistical learning.

2- An introduction to statistical learning.

Both mention that ridge regression has two formulas that are equivalent. Is there an understandable mathematical proof of this result?

I also went through Cross Validated, but I can not find a definite proof there.

Furthermore, will LASSO enjoy the same type of proof?

https://en.wikipedia.org/wiki/Duality_(optimization)#The_strong_Lagrangian_principle:_Lagrange_duality — Taylor, May 27 '18 at 18:56
@jeza, Could you explain what's missing in my answer? It really derives all can be derived about the connection. — Royi, May 30 '18 at 20:13
@jeza, Could you be specific? Unless you know the Lagrangian concept for constrained problem it is hard to give a concise answer. — Royi, May 31 '18 at 04:34
@jeza , a constrained optimization problem can be converted into optimization of the Lagrangian function / KKT conditions (as explained in the current answers). This principle has already many different simple explanations all over the internet. In what direction is more explanation of the proof necessary? Explanation/proof of the Lagrangian multiplier/function, explanation/proof how this problem is a case of optimization that relates to the method of Lagrange, difference KKT/Lagrange, explanation of the principle of regularization, etc? — Sextus Empiricus, May 31 '18 at 07:05
Is this question a possible duplicate? https://math.stackexchange.com/questions/335306/why-are-additional-constraint-and-penalty-term-equivalent-in-ridge-regression — Sextus Empiricus, May 31 '18 at 09:44
@jeza, I tried adding some intuitive explanation. Let me know what you think. — Royi, May 31 '18 at 20:13

Royi · Accepted Answer · 2019-04-03T04:15:32.350

23

The classic Ridge Regression (Tikhonov Regularization) is given by:

$$ \arg \min_{x} \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \lambda {\left\| x \right\|}_{2}^{2} $$

The claim above is that the following problem is equivalent:

$$\begin{align*} \arg \min_{x} \quad & \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} \\ \text{subject to} \quad & {\left\| x \right\|}_{2}^{2} \leq t \end{align*}$$

Let's define $ \hat{x} $ as the optimal solution of the first problem and $ \tilde{x} $ as the optimal solution of the second problem.

The claim of equivalence means that $ \forall t, \: \exists \lambda \geq 0 : \hat{x} = \tilde{x} $.
Namely you can always have a pair of $ t $ and $ \lambda \geq 0 $ such the solution of the problem is the same.

How could we find a pair?
Well, by solving the problems and looking at the properties of the solution.
Both problems are Convex and smooth so it should make things simpler.

The solution for the first problem is given at the point the gradient vanishes which means:

$$ \hat{x} - y + 2 \lambda \hat{x} = 0 $$

The KKT Conditions of the second problem states:

$$ \tilde{x} - y + 2 \mu \tilde{x} = 0 $$

and

$$ \mu \left( {\left\| \tilde{x} \right\|}_{2}^{2} - t \right) = 0 $$

The last equation suggests that either $ \mu = 0 $ or $ {\left\| \tilde{x} \right\|}_{2}^{2} = t $.

Pay attention that the 2 base equations are equivalent.
Namely if $ \hat{x} = \tilde{x} $ and $ \mu = \lambda $ both equations hold.

So it means that in case $ {\left\| y \right\|}_{2}^{2} \leq t $ one must set $ \mu = 0 $ which means that for $ t $ large enough in order for both to be equivalent one must set $ \lambda = 0 $.

On the other case one should find $ \mu $ where:

$$ {y}^{t} \left( I + 2 \mu I \right)^{-1} \left( I + 2 \mu I \right)^{-1} y = t $$

This is basically when $ {\left\| \tilde{x} \right\|}_{2}^{2} = t $

Once you find that $ \mu $ the solutions will collide.

Regarding the $ {L}_{1} $ (LASSO) case, well, it works with the same idea.
The only difference is we don't have closed for solution hence deriving the connection is trickier.

Have a look at my answer at StackExchange Cross Validated Q291962 and StackExchange Signal Processing Q21730 - Significance of $ \lambda $ in Basis Pursuit.

Remark
What's actually happening?
In both problems, $ x $ tries to be as close as possible to $ y $.
In the first case, $ x = y $ will vanish the first term (The $ {L}_{2} $ distance) and in the second case it will make the objective function vanish.
The difference is that in the first case one must balance $ {L}_{2} $ Norm of $ x $. As $ \lambda $ gets higher the balance means you should make $ x $ smaller.
In the second case there is a wall, you bring $ x $ closer and closer to $ y $ until you hit the wall which is the constraint on its Norm (By $ t $).
If the wall is far enough (High value of $ t $) and enough depends on the norm of $ y $ then i has no meaning, just like $ \lambda $ is relevant only of its value multiplied by the norm of $ y $ starts to be meaningful.
The exact connection is by the Lagrangian stated above.

Resources

I found this paper today (03/04/2019):

Approximation Hardness for A Class of Sparse Optimization Problems.

edited Apr 03 '19 at 04:15

answered May 27 '18 at 19:54

Royi

1,135

does the equivalent means that the \lambda and \t should be the same. Because I can not see that in the proof. thanks – jeza May 28 '18 at 03:04
1

@jeza, As I wrote above, for any $ t $ there is $ \lambda \geq 0 $ (Not necessarily equal to $ t $ but a function of $ t $ and the data $ y $) such that the solutions of the two forms are the same. – Royi May 28 '18 at 04:07
4

@jeza, both $\lambda$ & $t$ are essentially free parameters here. Once you specify, say, $\lambda$, that yields a specific optimal solution. But $t$ remains a free parameter. So at this point the claim is that there can be some value of $t$ that would yield the same optimal solution. There are essentially no constraints on what that $t$ must be; it's not like it has to be some fixed function of $\lambda$, like $t=\lambda/2$ or something. – gung - Reinstate Monica May 29 '18 at 20:46
@Royi, I would like to know 1- why your formula have (1/2), while the formulas in question not? 2- are using KKT to show the equivalence of the two formulas? 3- if yes, I am still can't see that equivalence. I am not sure but what I expect to see is that proof to show that formula one = formula two. – jeza Apr 01 '19 at 14:49
Just easier when you differentiate the LS term. You can move form my $ \lambda $ to the OP $ \lambda $ by factor of two. 2. I used KKT fo the 2nd case. The first case has no constraints, hence you can just solve it. 3. There is no closed form equation between them. I showed the logic and how you can create a graph connecting them. But as I wrote it will change for each $ y $ (It is data dependent).

Royi

Apr 01 '19 at 15:09

1

@Royi, I have a few things. 1- what do you mean by "move form my to the OP by a factor of two. 2" not clear to me yet. 2- I am still cannot understand that logic. 3- I am confused because you introduce "mu" with "t" and "lambda", also "‖‖^2_2≤ one must set =0 which means that for large enough in order for both to be equivalent one must set =0. (+2)−1(+2)−1=. This is basically when ‖̃ ‖22=" not clear to me. 4- I expect to see that "t" = "lambda" then you mentioned "mu" = "lambda". Could you please help me by elaborating or editing the answer. Thx – jeza Apr 02 '19 at 23:17

@Jeza, Could you open new question, post a link to it here and I will try answering it? – Royi Apr 03 '19 at 02:29

1

@Royi, I think the question will be duplicated! – jeza Apr 04 '19 at 10:14

So I really don't understand the issue. I basically derived the KKT equations for the constrained case and tried to tie it to the regularized case. – Royi Apr 04 '19 at 10:26

@Royi, I do not understand the logic on how you go from constraint case to regularized one. – jeza Apr 04 '19 at 12:45

I ask which values of $ \lambda $ in the regularized case and $ t $ in the constrained case will yield the same answer. Again, you may open a question which asks for showing the function which maps one to each other. I will try show it in code. – Royi Apr 04 '19 at 14:51

@Royi, I added a new question. – jeza Apr 04 '19 at 16:06

@jeza, Please paste a link here. – Royi Apr 04 '19 at 16:34

@Royi, https://stats.stackexchange.com/questions/401212/how-to-show-the-equivalence-between-the-regularized-regression-and-their-constra – jeza Apr 04 '19 at 16:40

@Royi, could you please have a look at the question? – jeza Apr 07 '19 at 23:56

@jeza, I promise I will. Just a tight days. Once I have a free hour I will do it. – Royi Apr 08 '19 at 06:01

@Royi, thanks, now there is a bounty on the question. – jeza Apr 08 '19 at 11:44

@jeza, I added my answer. – Royi Apr 13 '19 at 06:56

@Royi, many thanks, I think I still need more time to get the idea, I am learning. – jeza Apr 17 '19 at 17:05

Well, At least you chose a really interesting subject to learn :-). – Royi Apr 17 '19 at 21:12

1

The most confusing part is that the relation between $\lambda$ and $t$ is data-dependent. @Royi has mentioned this twice in the comments, but IMO this is an important point that deserves to be put in bold in the answer. Although this fact is somewhat obvious (for given $\lambda, t$ we scale $y$ away from the regression line, so that the solution penalised by $\lambda$ doesn't fit into the constraint set by $t$), the phrasing "equivalent way to write the problem" is misleading, as in order to write the problem in the equivalent way we are required to first solve it. – paperskilltrees May 10 '22 at 23:58

Note that HTF in their ESL book put it this way, without mentioning any dependence on data: "There is a one-to-one correspondence between the parameters λ in (3.41) and t in (3.42)". – paperskilltrees May 11 '22 at 00:02

Greg Snow · Answer 2 · 2018-06-07T15:27:53.497

13

A less mathematically rigorous, but possibly more intuitive, approach to understanding what is going on is to start with the constraint version (equation 3.42 in the question) and solve it using the methods of "Lagrange Multiplier" (https://en.wikipedia.org/wiki/Lagrange_multiplier or your favorite multivariable calculus text). Just remember that in calculus $x$ is the vector of variables, but in our case $x$ is constant and $\beta$ is the variable vector. Once you apply the Lagrange multiplier technique you end up with the first equation (3.41) (after throwing away the extra $-\lambda t$ which is constant relative to the minimization and can be ignored).

This also shows that this works for lasso and other constraints.

edited Jun 07 '18 at 15:27

answered May 29 '18 at 20:33

Greg Snow

51,722

2

Don’t we have to treat it as Karush-Kuhn-Tucker rather than Lagrange, since the constraint is an inequality? – Dave Sep 24 '20 at 11:44
@Dave, Would this make any real difference? (It has been quite a while since I was in a calculus class and don't remember the details of how they compare). From a practical standpoint (understanding rather than rigorous proof), any meaningful constraints considered will have the solution equal to the constraint, so I don't think it will really matter. – Greg Snow Sep 24 '20 at 13:38
@Dave even if you take the KKT formulation, your lambda hyperparameter is positive, which means all the KKT inequality constraints are activ, i.e. they are on the boundary g(x)=0. This comes down to the Lagrangian formulation because we only have equality constraints left. – Matt Aug 21 '21 at 12:23

Matthew Gunn · Answer 3 · 2020-04-18T17:24:52.207

It's perhaps worth reading about Lagrangian duality and a broader relation (at times equivalence) between:

optimization subject to hard (i.e. inviolable) constraints
optimization with penalties for violating constraints.

Quick intro to weak duality and strong duality

Assume we have some function $f(x,y)$ of two variables. For any $\hat{x}$ and $\hat{y}$, we have:

$$ \min_x f(x, \hat{y}) \leq f(\hat{x}, \hat{y}) \leq \max_y f(\hat{x}, y)$$

Since that holds for any $\hat{x}$ and $\hat{y}$ it also holds that:

$$ \max_y \min_x f(x, y) \leq \min_x \max_y f(x, y)$$

This is known as weak duality. In certain circumstances, you have also have strong duality (also known as the saddle point property):

$$ \max_y \min_x f(x, y) = \min_x \max_y f(x, y)$$

When strong duality holds, solving $\max_y \min_x f(x, y)$ also solves $\min_x \max_y f(x, y)$.

Lagrangian for constrained Ridge Regression

Let me define the function $\mathcal{L}$ as:

$$ \mathcal{L}(\mathbf{b}, \lambda) = \sum_{i=1}^n (y - \mathbf{x}_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right) $$

The min-max interpretation of the Lagrangian

The Ridge regression problem subject to hard constraints is:

$$ \min_\mathbf{b} \max_{\lambda \geq 0} \mathcal{L}(\mathbf{b}, \lambda) $$

You pick $\mathbf{b}$ to minimize the objective, cognizant that after you pick $\mathbf{b}$, your opponent will set $\lambda$ to infinity if you chose $\mathbf{b}$ such that the constraint was violated (in this case $\sum_{j=1}^p b_j^2 > t$).

If strong duality holds (which it does here because it's a convex optimization problem where Slater's condition is satisfied for $t>0$), you then achieve the same result by reversing the order:

$$ \max_{\lambda \geq 0} \min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda) $$

In this dual problem, your opponent chooses $\lambda$ first! You then choose $\mathbf{b}$ to minimize the objective, already knowing your opponent's choice of $\lambda$. The $\min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$ part (taking $\lambda$ as given) is equivalent to the 2nd form of your Ridge Regression problem.

As you can see, this isn't a result particular to Ridge Regression. It is a broader concept.

References

I started this post following an exposition of Rockafellar.

Rockafellar, R.T., Convex Analysis

You might also examine lectures 7 and lecture 8 from Prof. Stephen Boyd's course on convex optimization.

note that your answer can be extended to any convex function. — 81235, Jul 08 '19 at 16:07
In the maxmin formulation $\max_{\lambda \geq 0} \min_\mathbf{b} \mathcal{L}(\mathbf{b}, \lambda)$ shouldn't we maximize with respect to $\lambda$ (as we do in the Wolfe dual in SVM's) or is it because we select (we fix) the value of $\lambda$? — ado sar, Jan 11 '23 at 22:04

Alecos Papadopoulos · Answer 4 · 2018-05-31T07:57:24.163

7

They are not equivalent.

For a constrained minimization problem

$$\min_{\mathbf b} \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2\\ s.t. \sum_{j=1}^p b_j^2 \leq t,\;\;\; \mathbf b = (b_1,...,b_p) \tag{1}$$

we solve by minimize over $\mathbf b$ the corresponding Lagrangean

$$\Lambda = \sum_{i=1}^n (y - \mathbf{x}'_i \cdot \mathbf{b})^2 + \lambda \left( \sum_{j=1}^p b_j^2 - t \right) \tag{2}$$

Here, $t$ is a bound given exogenously, $\lambda \geq 0$ is a Karush-Kuhn-Tucker non-negative multiplier, and both the beta vector and $\lambda$ are to be determined optimally through the minimization procedure given $t$.

Comparing $(2)$ and eq $(3.41)$ in the OP's post, it appears that the Ridge estimator can be obtained as the solution to

$$\min_{\mathbf b}\{\Lambda + \lambda t\} \tag{3}$$

Since in $(3)$ the function to be minimized appears to be the Lagrangean of the constrained minimization problem plus a term that does not involve $\mathbf b$, it would appear that indeed the two approaches are equivalent...

But this is not correct because in the Ridge regression we minimize over $\mathbf b$ given $\lambda >0$. But, in the lens of the constrained minimization problem, assuming $\lambda >0$ imposes the condition that the constraint is binding, i.e that

$$\sum_{j=1}^p (b^*_{j,ridge})^2 = t$$

The general constrained minimization problem allows for $\lambda = 0$ also, and essentially it is a formulation that includes as special cases the basic least-squares estimator ($\lambda ^*=0$) and the Ridge estimator ($\lambda^* >0$).

So the two formulation are not equivalent. Nevertheless, Matthew Gunn's post shows in another and very intuitive way how the two are very closely connected. But duality is not equivalence.

edited May 31 '18 at 07:57

answered May 30 '18 at 22:02

Alecos Papadopoulos

58,953

@MartijnWeterings Thanks for the comment, I have reworked my answer. – Alecos Papadopoulos May 31 '18 at 07:58
@MartijnWeterings I do not see what is confusing since the expression written in your comment is exactly the expression I wrote in my reworked post. – Alecos Papadopoulos May 31 '18 at 08:50
2

This was the duplicate question I had in mind were the equivalence is explained very intuitively to me https://math.stackexchange.com/a/336618/466748 the argument that you give for the two not being equivalent seems only secondary to me, and a matter of definition (the OP uses $\lambda \geq 0$ instead of $\lambda > 0$ and we could just as well add the constrain $t < \Vert \beta^{OLS} \Vert^2_2$ to exclude the cases where $\lambda=0$) . – Sextus Empiricus May 31 '18 at 09:38
@MartijnWeterings When A is a special case of B, A cannot be equivalent to B. And ridge regression is a special case of the general constrained minimization problem, Namely a situation to which we arrive if we constrain further the general problem (like you do in your last comment). – Alecos Papadopoulos May 31 '18 at 09:44
Certainly you could define some constrained minimization problem that is more general then ridge regression (like you can also define some regularization problem that is more general than ridge regression, e.g. negative ridge regression), but then the non-equivalence is due to the way that you define the problem and not due to the transformation from the constrained representation to the Lagrangian representation. The two forms can be seen as equivalent within the constrained formulation/definition (non-general) that are useful for ridge regression. – Sextus Empiricus May 31 '18 at 09:51
@MartijnWeterings Certainly, but the whole thread here started because in a book the "equivalence" was stated for the general constrained minimization problem, not some special version of it. – Alecos Papadopoulos May 31 '18 at 10:55
The reference from the OP as well as some original works on the statistical interpretation of this type of regularization (e.g. Hoerl & Kennard 1970 Ridge Regression: Biased Estimation for Nonorthogonal Problems) use $\lambda \geq 0$ instead of $\lambda > 0$. – Sextus Empiricus May 31 '18 at 12:28
@AlecosPapadopoulos they actually are equivalent in general. If we consider the dual and primal optimal points where strong duality holds, the primal point must minimize the Lagrangian. But in ridge regression, the Lagrangian is strongly convex, hence it has a unique minimizer. Therefore, minimizing the Lagrangian must recover the primal optimal point. – Leo Dec 29 '18 at 22:21
@Leo I suspect you are talking about "equivalence of solution", rather than "equivalence of problem formulation". – Alecos Papadopoulos Dec 29 '18 at 22:26
@AlecosPapadopoulos they are equivalent in the sense that for every constrained formulation, there is a penalized formulation (with some lambda, greater or equal to zero) with exactly the same set of solutions. – Leo Dec 30 '18 at 08:29
@AlecosPapadopoulos The other way, that given a penalized formulation there is an "equivalent" constrained one, is true in a different sense (perhaps this is what you mean by "equivalence of solution"): a solution to the latter leads to a solution to the former, yet their sets of solutions could still differ. – Leo Dec 30 '18 at 08:47