Newton's Method

Definition

An iterative algorithm for finding the roots of a differentiable function, which are solution to the equation $f(x)=0$

Algorithm

Find the next point such that the Taylor series of the given point is 0 Taylor first approximation: $f(x)\simeq f(x_n)+f^{\prime }(x_n)(x-x_n)$ The point such that the Taylor series is 0: $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$

multivariate version: ${\mathbf{x}}_{n+1}=f({\mathbf{x}}_n)-\nabla f({\mathbf{x}}_n{)}^{-1}f({\mathbf{x}}_n)$

In convex optimization,

Find the minimum point^[its derivative is 0] of Taylor quadratic approximation. Taylor quadratic approximation: $f(x)\simeq f(x_n)+f^{\prime }(x_n)(x-x_n)+\frac{f^{\prime \prime }(x_n)}{2}(x-x_n{)}^2$ The derivative of the quadratic approximation: $f^{\prime }(x_n)+f^{\prime \prime }(x_n)(x-x_n)$ The minimum point of the quadratic approximation^[the point such that the derivative of the quadratic approximation is 0]: $x_{n+1}=x_n-\frac{f^{\prime }(x_n)}{f^{\prime \prime }(x_n)}$ multivariate version: ${\mathbf{x}}_{n+1}={\mathbf{x}}_n-{\nabla }^{2}f({\mathbf{x}}_n{)}^{-1}\nabla f({\mathbf{x}}_n)$

Examples

Solution of a linear system

Solve $A\mathbf{x}=\mathbf{b}$ with an MSE loss

The cost function is $f(\mathbf{x})=(A\mathbf{x}-\mathbf{b}{)}^{⊺}(A\mathbf{x}-\mathbf{b})$ and its gradient and hessian are $\nabla f(x)=-2(\mathbf{b}-A\mathbf{x}{)}^{⊺}$, ${\nabla }^{2}f(x)=2A^{⊺}A$

Then, solution is ${\mathbf{x}}_{n+1}={\mathbf{x}}_n+(A^{⊺}A{)}^{-1}{A}^{⊺}(\mathbf{b}-A{\mathbf{x}}_n)$ If $(A^{⊺}A)$ is invertible, ${\mathbf{x}}_{n+1}=(A^{⊺}A{)}^{-1}{A}^{⊺}\mathbf{b}$ is a Least Square solution.