Local quadratic convergence of Newton's method

ProofAdvanced⏱ 1 hourAdvanced Optimizationnewtonquadratic convergencelipschitz hessian

Theory: Newton, Quasi-Newton and Conjugate Gradient →

Problem

Prove that if $\nabla^2f$ is $M$ -Lipschitz and $\nabla^2f(x^\star)\succeq\mu I$ at a stationary point $x^\star$ , then Newton's method satisfies $\|e_{t+1}\|_2\le\frac M\mu\|e_t\|_2^2$ in a neighbourhood of $x^\star$ , where $e_t = x_t-x^\star$ . Quantify the size of the basin.

Write a complete argument. Every inequality you use should be one you could state precisely.

Solution

Opening this before you have a real attempt on paper is the fastest way to feel like you understand something you cannot reproduce.

Related problems

All problems

Problem	Field	Type	Difficulty	Time
IRLS is a weighted least-squares solve	Classical ML	Proof	Intermediate	30 min
Newton's method is affine invariant	Advanced Optimization	Proof	Intermediate	30 min
Conjugate gradient and Krylov optimality	Advanced Optimization	Proof	Advanced	1 hour
The BFGS update satisfies the secant condition	Advanced Optimization	Proof	Advanced	30 min