# Showing that ridge regression is a solution to the following optimization problem [duplicate]

$$\hat{\theta}=\arg\min_{\theta}\{ ||y-X\theta||_2^2+\lambda||\theta||_2^2\},$$ where $X$ is an $n\times p$ matrix.

We have if $y=X\theta+\varepsilon$ then $$\hat{\theta}^{\text{ridge}}=(X^TX+\lambda I)^{-1}X^Ty$$ So I'm kinda confused, because if $y=X\theta+\varepsilon$, then $||y-X\theta||_2^2+\lambda||\theta||_2^2=||\varepsilon||_2^2+\lambda||\theta||_2^2.$ But I'm confused as to how to show that $$(X^TX+\lambda I)^{-1}X^Ty=\arg\min_{\theta}\{ ||y-X\theta||_2^2+\lambda||\theta||_2^2\}.$$ Any help would be much appreciated. Thank you. I gotta edit this cause someone said it's a duplicate of an entirely different problem cool.

• Hint: try writing the loss as a function of $\theta$, and then differentiating with respect to $\theta$. – jld Sep 18 '18 at 18:56
• @jld Sorry, how do I find the loss? – Gengar Sep 18 '18 at 19:10
• Loss is another term for the objective function. So the question is what are trying to optimize? It is probably the squared error. So write it down and differentiate and it will lead you to the final equation – Drey Sep 18 '18 at 19:22
• @Drey Yeah, still don't know how to find loss/objective function. – Gengar Sep 18 '18 at 19:23
• How do you measure the error of your prediction? That's the loss – Drey Sep 18 '18 at 19:25

I think about the problem in summation notation,

The loss is defined, as you said, as $L = \sum_{i=1}^{N}(\sum_{j=1}^{M}\theta_{j}X_{ij} - y_{i})^{2}+ \lambda\sum_{j=1}^{M}\theta_{j}^{2}$

You can differentiate this w.r.t $\theta _{k}$ to find:

$\frac{\partial L}{\partial \theta _{k}} =\sum_{i=1}^{N}2(\sum_{j=1}^{M}\theta_{j}X_{ij}-y_{i})X_{ik} +2\lambda \theta _{k}$

Note that $\sum_{i=1}^{N}X_{ik}\sum_{j=1}^{M}\theta_{j}X_{ij}=\sum_{i=1}^{N}X_{ik}(X\cdot \theta)_{i}=(X^{T}\cdot X \cdot \theta)_{k}$

and $\sum_{i=1}^{N}X_{ik}y_{i}=(X^{T}\cdot y)_{k}$

Putting this together:

$(X^{T}\cdot X\cdot \theta)_{k}-(X^{T}\cdot y)_{k} +\lambda \theta _{k}=0 \hspace{5mm}\forall k$

which you can re-write as a vector equation:

$X^{T}\cdot y= (X^{T}\cdot X + \lambda I)\cdot \theta$

and thus, finally

$\theta = (X^{T}\cdot X + \lambda I)^{-1}\cdot X^{T}\cdot y$

So this has shown that if you assume your loss is given by $||y - X\cdot \theta ||_{2}+\lambda ||\theta||_{2}$ and you wish to find the theta which minimises this loss, then $\theta = (X^{T}\cdot X + \lambda I)^{-1}\cdot X^{T}\cdot y$ is the solution. Hope this answers your question

• Just to clarify, you're condensing $\lambda I$ to just $\lambda$ correct? Thanks for your help – Gengar Sep 18 '18 at 19:56
• yes, I didn't explicitly state the presence of the identity matrix, you are correct – gazza89 Sep 18 '18 at 20:02