I am trying to use the Newton's method

$\theta^{(t+1)} = \theta^{(t)} - [H^{(t)}]^{-1} [\nabla L(\theta^{(t)})]$ to minimise the following loss fucntion

$L(\theta) = (y - X\theta)^T(y-X\theta) + \lambda \theta^T\theta$

Here $\theta $ is $n\times 1$ vector, $X $ is $m\times n$ matrix, $y $ is $m\times 1$ vector and $H^t = \nabla^2 L(\theta^{(t)})$ is the $n\times n$ Hessian matrix

I calculated the following details:

$\nabla L(\theta^{(t)}) = X^TX\theta^{(t)} + \lambda \theta^{(t)} - X^T y $ and

$H^t = X^TX + \lambda I_n$

Since, I know that there is a closed form solution to the loss function I am trying to minimise, I want to apply Newton's method by hand to this loss function and get that closed form again... But in doing so, I am facing problem. The major problem is calculating the inverse of $X^TX + \lambda I_n$

How do I do this?


I don't think you really need to calculate the inverse for the purpose. Substitute $\nabla L$ to the update function, you get

$$ \begin{align} \theta^{(t+1)} &= \theta^{(t)} - H^{-1} \left[ (X^t X + \lambda I_n) \theta^{(t)} - X^ty\right] \\ &= \theta^{(t)} - H^{-1} H \theta^{(t)} + H^{-1} X^ty \\ &= H^{-1} X^ty \end{align} $$ This is the closed form solution to the linear ridge regression. This means that the Newton's method converges in one step.

  • $\begingroup$ Indeed, the loss function is a quadratic and Newton's method has quadratic termination. +1 $\endgroup$
    – Sycorax
    Oct 22 '20 at 15:48

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.