= Solution
Newton's method for minimization uses
$$
\boxed{x_{k+1}=x_k-[\nabla^2f(x_k)]^{-1}\nabla f(x_k)}.
$$
For a quantitative local bound, suppose on a convex neighbourhood containing the iterates that
$$
mI\preceq\nabla^2f(x)\preceq LI,
\qquad
\|\nabla^2f(x)-\nabla^2f(y)\|\leq M\|x-y\|,
$$
with $m>0$, and let $x^*$ be the minimizer. The <integral> form of the <gradient> and the Hessian Lipschitz bound give the <quadratic convergence bound for Newton's method>
$$
\|x_{k+1}-x^*\|
\leq\frac M{2m}\|x_k-x^*\|^2.
$$
If $q=M\|x_0-x^*\|/(2m)<1$, induction yields
$$
\|x_k-x^*\|\leq\frac{2m}{M}q^{2^k}.
$$
Since $f(x)-f(x^*)\leq L\|x-x^*\|^2/2$,
$$
\boxed{f(x_k)-f(x^*)
\leq\frac{2Lm^2}{M^2}q^{2^{k+1}}}.
$$
Back to article page
