To prevent overfitting people people add a regularization term (proportional to the squared sum of the parameters of the model) with a regularization parameter $\lambda$ to the cost function of linear regression. Is this parameter $\lambda$ the same as a lagrange multiplier? So is regularization the same as the method of lagrange multiplier? Or how are these methods connected?
Solved – the connection between regularization and the method of lagrange multipliers
optimizationregressionregularization
Related Solutions
You can estimate an optimal lambda that minimizes testing error during cross-validation. Testing error (i.e. Mean Squared Prediction error on a hold-out testing set) should decrease as lambda increases from zero as the training data is less and less overfit, but beyond a certain point it will increase back up again as the model is inadequately capturing the data. Optimal lambda can be conservatively chosen as the one which produces a testing error that is one standard error away from the minimum testing error (on the side of the higher lambda value).
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.
Best Answer
Say we are optimizing a model with parameters $\vec{\theta}$, by minimizing some criterion $f(\vec{\theta})$ subject to a constraint on the magnitude of the parameter vector (for instance to implement a structural risk minimization approach by constructing a nested set of models of increasing complexity), we would need to solve:
$\mathrm{min}_\vec{\theta} f(\vec{\theta}) \quad \mathrm{s.t.} \quad \|\vec{\theta}\|^2 < C$
The Lagrangian for this problem is (caveat: I think, its been a long day... ;-)
$\Lambda(\vec{\theta},\lambda) = f(\vec{\theta}) + \lambda\|\vec{\theta}\|^2 - \lambda C.$
So it can easily be seen that a regularized cost function is closely related to a constrained optimization problem with the regularization parameter $\lambda$ being related to the constant governing the constraint ($C$), and is essentially the Lagrange multiplier. The $-\lambda C$ term is just an additive constant, so it doesn't change the solution of the optimisation problem if it is omitted, just the value of the objective function.
This illustrates why e.g. ridge regression implements structural risk minimization: Regularization is equivalent to putting a constraint on the magnitude of the weight vector and if $C_1 > C_2$ then every model that can be made while obeying the constraint that
$\|\vec{\theta}\|^2 < C_2$
will also be available under the constraint
$\|\vec{\theta}\|^2 < C_1$.
Hence reducing $\lambda$ generates a sequence of hypothesis spaces of increasing complexity.