14
$\begingroup$

In "The Elements of Statistical Learning" (2nd ed), p63, the authors give the following two formulations of the ridge regression problem:

$$ \hat{\beta}^{ridge} = \underset{\beta}{\operatorname{argmin}} \left\{ \sum_{i=1}^N(y_i-\beta_0-\sum_{j=1}^p x_{ij} \beta_j)^2 + \lambda \sum_{j=1}^p \beta_j^2 \right\} $$

and

$$ \hat{\beta}^{ridge} = \underset{\beta}{\operatorname{argmin}} \sum_{i=1}^N(y_i-\beta_0-\sum_{j=1}^p x_{ij} \beta_j)^2 \text{, subject to } \sum_{j=1}^p \beta_j^2 \leq t.$$

It is claimed that the two are equivalent, and that there is a one-to-one correspondence between the parameters $\lambda$ and $t$.

It would appear that the first formulation is a Lagrangian relaxation of the second. However, I never had an intuitive understanding of how or why Lagrangian relaxations work.

Is there a simple way to demonstrate that the two formulations are indeed equivalent? If I have to choose, I'd prefer intuition over rigour.

Thanks.

$\endgroup$
4
$\begingroup$

If you merely want an intuitive explanation, go at 1.03.26 of this video (to the end), there is an intuitive explanation of how constraints relate to objective function.

$\endgroup$
  • $\begingroup$ This is a great set of lectures, thanks for the pointer. $\endgroup$ – Tristan Nov 11 '10 at 23:17
2
$\begingroup$

The correspondence can most easily be shown using the Envelope Theorem.

First, the standard Lagrangian will have an additional $\lambda \cdot t$ term. This will not affect the maximization problem if we are just treating $\lambda$ as given, so Hastie et al drop it.

Now, if you differentiate the full Lagrangian with respect to $t$, the Envelope Theorem says you can ignore the indirect effects of $t$ through $\beta$, because you're at a maximum. What you'll be left with is the Lagrange multipler from $\lambda \cdot t$.

But what does this mean intuitively? Since the constraint binds at the maximum, the derivative of the Lagrangian, evaluated at the maximum, is the same as the deriviate the original objective. Therefore the Lagrange multiplier gives the shadow price -- the value in terms of the objective -- of relaxing the constraint by increasing $t$.

I assume this is the correspondence Hastie et al. are referring to.

$\endgroup$

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.