Ridge regression formulation as constrained versus penalized: How are they equivalent?

Question

I seem to be misunderstanding a claim about linear regression methods that I've seen in various places. The parameters of the problem are:

Input:

$N$ data samples of $p+1$ quantities each consisting of a "response" quantity $y_i$ and $p$ "predictor" quantities $x_{ij}$

The result desired is a "good linear fit" which predicts the response based on the predictors where a good fit has small differences between the prediction and the observed response (among other criteria).

Output: $p+1$ coefficients $\beta_j$ where $\beta_0 + \sum_{j=1}^p x_{ij} * \beta_j$ is a "good fit" for predicting the response quantity from the predictor quantities.

I'm confused about the "ridge regression" approach to this problem. In "The Elements of Statistical Learning" by Hastie, Tibshirani, and Friedman page 63 ridge regression is formulated in two ways.

First as the constrained optimization problem:

$$ \text{argmin}_\beta \sum_{i=1}^N { ( y_i - (\beta_0 + \sum_{j=1}^p (x_{ij} * \beta_j)) )^2 } $$ subject to the constraint $$ \sum_{j=1}^p \beta_i^2 \leq t $$ for some positive parameter t.

Second is the penalized optimization problem: $$ \text{argmin}_\beta ( \lambda \sum_{j=1}^p { \beta_j^2 } ) + \sum_{i=1}^N { ( y_i - (\beta_0 + \sum_{j=1}^p (x_{ij} * \beta_j)) )^2 } $$ for some positive parameter $\lambda$.

The text says that these formulations are equivalent and that there is a "one to one correspondence between the parameters $\lambda$ and $t$". I've seen this claim (and similar ones) in several places in addition to this book. I think I am missing something because I don't see how the formulations are equivalent as I understand it.

Consider the case where $N=2$ and $p=1$ with $y_1=0$, $x_{1,1}=0$ and $y_2=1$, $x_{1,2}=1$. Choosing the parameter $t=2$ the constrained formulation becomes:

$$ \text{argmin}_{\beta_0,\beta_1} ( \beta_0^2 + (1 - (\beta_0 + \beta_1))^2 ) $$

expanded to

$$ \text{argmin}_{\beta_0,\beta_1} ( 2 \beta_{0}^{2} + 2 \beta_{0} \beta_{1} - 2 \beta_{0} + \beta_{1}^{2} - 2 \beta_{1} + 1 ) $$

To solve this find the solution where the partial derivatives with respect to $\beta_0$ and $\beta_1$ are zero: $$ 4 \beta_{0} + 2 \beta_{1} - 2 = 0 $$ $$ 2 \beta_{0} + 2 \beta_{1} - 2 = 0 $$ with solution $\beta_0 = 0$ and $\beta_1 = 1$. Note that $\beta_0^2 + \beta_1^2 \le t$ as required.

How does this derivation relate to the other formulation? According to the explanation there is some value of $\lambda$ uniquely corresponding to $t$ where if we optimize the penalized formulation of the problem we will derive the same $\beta_0$ and $\beta_1$. In this case the penalized form becomes $$ \text{argmin}_{\beta_0,\beta_1} ( \lambda (\beta_0^2 + \beta_1^2) + \beta_0^2 + (1 - (\beta_0 + \beta_1))^2 ) $$ expanded to $$ \text{argmin}_{\beta_0,\beta_1} ( \beta_{0}^{2} \lambda + 2 \beta_{0}^{2} + 2 \beta_{0} \beta_{1} - 2 \beta_{0} + \beta_{1}^{2} \lambda + \beta_{1}^{2} - 2 \beta_{1} + 1 ) $$ To solve this find the solution where the partial derivatives with respect to $\beta_0$ and $\beta_1$ are zero: $$ 2 \beta_{0} \lambda + 4 \beta_{0} + 2 \beta_{1} - 2 = 0 $$ $$ 2 \beta_{0} + 2 \beta_{1} \lambda + 2 \beta_{1} - 2 = 0 $$ for these equations I get the solution $$ \beta_0 = \lambda/(\lambda^2 + 3\lambda + 1) $$ $$ \beta_1 = (\lambda + 1)/((\lambda + 1)(\lambda + 2) - 1) $$ If that is correct the only way to get $\beta_0 = 0$ is to set $\lambda = 0$. However that would be the same $\lambda$ we would need for $t = 4$, so what do they mean by "one to one correspondence"?

In summary I'm totally confused by the two presentations and I don't understand how they correspond to each other. I don't understand how you can optimize one form and get the same solution for the other form or how $\lambda$ is related to $t$. This is just one instance of this kind of correspondence -- there are others for other approaches such as lasso -- and I don't understand any of them.

Someone please help me.

Answer 1

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} $ 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.

Answer 2

The confusion here comes from trying to work in a range of $t$ or $\lambda$ values where there is no constraint on the regression.

In your example, at the perfect fit of the regression line the sum of the squares of the regression coefficients is 1. So the value of $t=2$ (or any value of $t$ that is 1 or greater) places no constraint on the regression. In the space of $\lambda$ values, the entire unconstrained regression is represented by $\lambda = 0$. There is no one-to-one correspondence between $t$ and $\lambda$ in the unconstrained regression; all values of $t$ of 1 or greater in this case correspond to $\lambda=0$. That was the region that you have been investigating.

Only a value of $t$ less than 1 will place a constraint on the regression, corresponding to positive values of $\lambda$. As the accepted answer to this page shows, the one-to-one correspondence between $t$ and $\lambda$ holds "when the constraint is binding," in your example for values of $t$ less than 1.