11
$\begingroup$

In ridge regression, the objective function to be minimized is: $$\text{RSS}+\lambda \sum\beta_j^2.$$

Can this be optimized using the Lagrange multiplier method? Or is it straight differentiation?

$\endgroup$
  • 1
    $\begingroup$ What is the connection between the title (which focuses on $\lambda$) and the question (which appears to be only about the $\beta_j$)? I am concerned that "be optimized" could have distinctly different interpretations depending on which variables are considered the ones that can be varied and which ones are to be fixed. $\endgroup$ – whuber Jan 16 '16 at 18:18
  • 1
    $\begingroup$ thanks modified the question. I have read that the $\lambda$ is found by cross validation -- but I believe that means you have the $\beta_j$ already and use different data to find the best $\lambda$ Question is -- how do you find the $\beta_j$'s in the first place when $\lambda$ is an unknown? $\endgroup$ – Minaj Jan 16 '16 at 18:29
19
$\begingroup$

There are two formulations for the ridge problem. The first one is

$$\boldsymbol{\beta}_R = \operatorname*{argmin}_{\boldsymbol{\beta}} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\beta} \right)^{\prime} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\beta} \right)$$

subject to

$$\sum_{j} \beta_j^2 \leq s. $$

This formulation shows the size constraint on the regression coefficients. Note what this constraint implies; we are forcing the coefficients to lie in a ball around the origin with radius $\sqrt{s}$.

The second formulation is exactly your problem

$$\boldsymbol{\beta}_R = \operatorname*{argmin}_{\boldsymbol{\beta}} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\beta} \right)^{\prime} \left( \mathbf{y} - \mathbf{X} \boldsymbol{\beta} \right) + \lambda \sum\beta_j^2 $$

which may be viewed as the Largrange multiplier formulation. Note that here $\lambda$ is a tuning parameter and larger values of it will lead to greater shrinkage. You may proceed to differentiate the expression with respect to $\boldsymbol{\beta}$ and obtain the well-known ridge estimator

$$\boldsymbol{\beta}_{R} = \left( \mathbf{X}^{\prime} \mathbf{X} + \lambda \mathbf{I} \right)^{-1} \mathbf{X}^{\prime} \mathbf{y} \tag{1}$$

The two formulations are completely equivalent, since there is a one-to-one correspondence between $s$ and $\lambda$.

Let me elaborate a bit on that. Imagine that you are in the ideal orthogonal case, $\mathbf{X}^{\prime} \mathbf{X} = \mathbf{I}$. This is a highly simplified and unrealistic situation but we can investigate the estimator a little more closely so bear with me. Consider what happens to equation (1). The ridge estimator reduces to

$$\boldsymbol{\beta}_R = \left( \mathbf{I} + \lambda \mathbf{I} \right)^{-1} \mathbf{X}^{\prime} \mathbf{y} = \left( \mathbf{I} + \lambda \mathbf{I} \right)^{-1} \boldsymbol{\beta}_{OLS} $$

as in the orthogonal case the OLS estimator is given by $\boldsymbol{\beta}_{OLS} = \mathbf{X}^{\prime} \mathbf{y}$. Looking at this component-wise now we obtain

$$\beta_R = \frac{\beta_{OLS}}{1+\lambda} \tag{2}$$

Notice then that now the shrinkage is constant for all coefficients. This might not hold in the general case and indeed it can be shown that the shrinkages will differ widely if there are degeneracies in the $\mathbf{X}^{\prime} \mathbf{X}$ matrix.

But let's return to the constrained optimization problem. By the KKT theory, a necessary condition for optimality is

$$\lambda \left( \sum \beta_{R,j} ^2 -s \right) = 0$$

so either $\lambda = 0$ or $\sum \beta_{R,j} ^2 -s = 0$ (in this case we say that the constraint is binding). If $\lambda = 0$ then there is no penalty and we are back in the regular OLS situation. Suppose then that the constraint is binding and we are in the second situation. Using the formula in (2), we then have

$$ s = \sum \beta_{R,j}^2 = \frac{1}{\left(1 + \lambda \right)^2} \sum \beta_{OLS,j}^2$$

whence we obtain

$$\lambda = \sqrt{\frac{\sum \beta_{OLS,j} ^2}{s}} - 1 $$

the one-to-one relationship previously claimed. I expect this is harder to establish in the non-orthogonal case but the result carries regardless.

Look again at (2) though and you'll see we are still missing the $\lambda$. To get an optimal value for it, you may either use cross-validation or look at the ridge trace. The latter method involves constructing a sequence of $\lambda$ in (0,1) and looking how the estimates change. You then select the $\lambda$ that stabilizes them. This method was suggested in the second of the references below by the way and is the oldest one.

References

Hoerl, Arthur E., and Robert W. Kennard. "Ridge regression: Biased estimation for nonorthogonal problems." Technometrics 12.1 (1970): 55-67.

Hoerl, Arthur E., and Robert W. Kennard. "Ridge regression: applications to nonorthogonal problems." Technometrics 12.1 (1970): 69-82.

$\endgroup$
  • 2
    $\begingroup$ @Minaj Ridge regression has constant shrinkage for all coefficients (other than the intercept). That's why there is only one multiplier. $\endgroup$ – JohnK Jan 16 '16 at 22:15
  • 2
    $\begingroup$ @amoeba This is a suggestion by Hoerl and Kennard, the people who introduced ridge regression in the 1970s. Based on their experience - and mine - the coefficients will stabilize in that interval even with extreme degrees of multicollinearity. Of course, this is an empirical strategy and so it is not guaranteed to work all the time. $\endgroup$ – JohnK Jan 17 '16 at 1:06
  • 2
    $\begingroup$ You could also just do the pseudo-observation method and get the estimates with nothing more complicated than a straight least squares regression program. You can also investigate the effect of changing $\lambda$ in a similar fashion. $\endgroup$ – Glen_b Jan 17 '16 at 2:16
  • 2
    $\begingroup$ @amoeba It is true that ridge is not scale invariant, that's why it is common practice to standardize the data beforehand. I have included the relevant references in case you want to take a look. They are immensely interesting and not so technical. $\endgroup$ – JohnK Jan 17 '16 at 10:43
  • 2
    $\begingroup$ @JohnK in effect ridge regression shrinks each $\beta$ by a different amount, so the shrinkage isn't constant even though there is only one shrinkage parameter $\lambda$. $\endgroup$ – Frank Harrell Jan 17 '16 at 13:27
4
$\begingroup$

My book Regression Modeling Strategies delves into the use of effective AIC for choosing $\lambda$. This comes from the penalized log likelihood and the effective degrees of freedom, the latter being a function of how much variances of $\hat{\beta}$ are reduced by penalization. A presentation about this is here. The R rms package pentrace finds $\lambda$ that optimizes effective AIC, and also allows for multiple penalty parameters (e.g., one for linear main effects, one for nonlinear main effects, one for linear interaction effects, and one for nonlinear interaction effects).

$\endgroup$
  • 1
    $\begingroup$ +1. What do you think of using leave-one-out CV error, computed via the explicit formula (i.e. without actually performing CV), for choosing $\lambda$? Do you have any idea about how it in practice compares to "effective AIC"? $\endgroup$ – amoeba Jan 17 '16 at 15:00
  • $\begingroup$ I haven't studied that. LOOCV takes a lot of computation. $\endgroup$ – Frank Harrell Jan 17 '16 at 15:15
  • $\begingroup$ Not if the explicit formula is used: stats.stackexchange.com/questions/32542. $\endgroup$ – amoeba Jan 17 '16 at 15:19
  • 1
    $\begingroup$ That formula works for the special case of OLS, not for maximum likelihood in general. But there is an approximate formula using score residuals. I do realize we are mainly talking about OLS in this discussion though. $\endgroup$ – Frank Harrell Jan 18 '16 at 13:25
1
$\begingroup$

I don't do it analytically, but rather numerically. I usually plot RMSE vs. λ as such:

enter image description here

Figure 1. RMSE and the constant λ or alpha.

$\endgroup$
  • $\begingroup$ Does this mean you fix a certain value of $\lambda$ and then differentiate the expression to find the $\beta_j$'s after which you compute RMSE and do the process all over again for new values of $\lambda$? $\endgroup$ – Minaj Jan 16 '16 at 18:32

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.