Is the magnitude coefficient vector in Ridge regression monotonic in lambda?

Question

recently an interesting question came up and while I would have intuitively said it is not, other students have now made a compelling case (while not being sure themselves).

For ridge (or l2 regularized) regression ( $RSS + \frac{\lambda}{2} ||w||^2 $)

Is the function of the magnitude of the coefficients $||w||^2 $ a function that is monotonic in lambda?

Thank you very much in advance for insights you can offer, this has been bugging me quite a bit this morning.

Answer 1

Yes it is.

Let $x$ be a fixed design matrix and $y$ a fixed response vector. Let $V \Sigma U^{T}$ be the SVD of $x$ and $U \Lambda U^{T}$ be the eigendecomposition of $x^{T} x$, where it is important to recall that $\Lambda$ has no negative entries, i.e. $x^{T} x$ is positive semidefinite, and also $\Sigma^2 = \Lambda$. Recall that $U$ and $V$ are orthogonal matrices, and that $\Lambda$ and $\Sigma$ are diagonal.

The ridge estimator with penalty parameter $\lambda$ has coefficients $$\hat{\beta}_{\text{ridge}}^{\lambda} = (x^{T} x + \lambda I)^{-1} x^{T} y.$$ We can compute its squared norm by plugging in the factorization above. $$\|\hat{\beta}_{\text{ridge}}^{\lambda}\|^{2} = (\hat{\beta}_{\text{ridge}}^{\lambda})^{T}\hat{\beta}_{\text{ridge}}^{\lambda} = y^{T} x (x^{T} x + \lambda I)^{-2} x^{T} y$$ $$ = y^{T} V \Sigma U^{T} (U \Lambda U^{T} + \lambda I)^{-2} U \Sigma V^{T} y$$ $$ = y^{T} V \Sigma U^{T} (U (\Lambda + \lambda I) U^{T} )^{-2} U \Sigma V^{T} y$$ $$ = y^{T} V \Sigma U^{T} (U (\Lambda + \lambda I)^{-2} U^{T} ) U \Sigma V^{T} y$$ $$ = y^{T} V \frac{\Sigma^{2}}{(\Lambda + \lambda I)^{2}} V^{T} y.$$ I'm abusing notation a bit in this last inequality by writing these matrices as a fraction, but I really just mean pointwise division of their elements since all of the matrices involved are diagonal. Next, substituting in that the eigenvalues of $x^{T} x$ are the squared singular values of $x$, we have $$= y^{T} V \frac{ \Lambda}{(\Lambda + \lambda I)^{2}} V^{T} y.$$ Denote $V^{T} y$ by $w$. We have $$y^{T} V \frac{ \Lambda}{(\Lambda + \lambda I)^{2}} V^{T} y = w^{T} \frac{ \Lambda}{(\Lambda + \lambda I)^{2}} w$$ $$ = \sum_{i=1}^{p} \frac{\Lambda_{i,i}}{(\Lambda_{i,i} + \lambda)^{2}} w_{i}^{2}.$$

Therefore, for two penalty parameters, $\lambda_{1} \leq \lambda_{2}$, we have $$\|\hat{\beta}_{\text{ridge}}^{\lambda_{2}}\|^{2} \leq \|\hat{\beta}_{\text{ridge}}^{\lambda_{1}}\|^{2} \iff \sum_{i=1}^{p} \frac{\Lambda_{i,i}}{(\Lambda_{i,i} + \lambda_{2})^{2}} w_{i}^{2} \leq \sum_{i=1}^{p} \frac{\Lambda_{i,i}}{(\Lambda_{i,i} + \lambda_{1})^{2}} w_{i}^{2}.$$ This last inequality is true because $\frac{\Lambda_{i,i}}{(\Lambda_{i,i} + \lambda_{2})^{2}} \leq \frac{\Lambda_{i,i}}{(\Lambda_{i,i} + \lambda_{1})^{2}}$ for each $i \in \{1,...,p\}$, which follows because $\Lambda_{i,i} \geq 0$.

Answer 2

Another way of looking at it is that ridge regression is the Lagrangian for a related constrained optimisation problem, see my answer to a related question

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.

So decreasing the ridge parameter corresponds to a loosening of the constraint on the squared norm of the weights, so if that was limiting the optimisation of the objective function, then the norm of the weights will increase.

Answer 3

Intuitive viewpoint

The regression is a trade-off in the terms $RSS$ and $||w||^2$, which are being balanced. If for some change in lambda the regression solution changes, then the one term increases while the other term decreases. They can't increase both because that will never lead to an improvement (and they can't decrease both because in the other direction that would mean an increase of both).

Now if you consider the sum $RSS(w) + 0.5 \lambda ||w||^2$ then you can see this as a sum of a decreasing and increasing (convex!) functions. As we increase $\lambda$ the minimum of the sum will shift into one direction.

Example:

library(glmnet)
set.seed(1)

x = matrix(rnorm(100 * 20), 100, 20)
y = rnorm(100)
fit1 = glmnet(x, y, alpha = 0)

beta = colSums(fit1$beta^2)
rss = (1-fit1$dev.ratio)*fit1$nulldev

plot(beta,rss, type ="l", main = "lowest/optimal RSS when norm of coefficients below beta", main.cex = 1) 
lines(beta, rss + 50*beta, col =2, lty = 2)
lines(beta, rss + 100*beta, col =2 ,lty = 2)
lines(beta, rss + 150*beta, col =2, lty = 2)

text(0.15,95.5, "relation RSS and beta")
text(0.08,99, "rss + 50 * beta" ,col = 2)
text(0.055,102, "rss + 100 * beta" ,col = 2)
text(0.04,103.5, "rss + 150 * beta" ,col = 2)