# Question about the assumption of Newton's method for optimization

Problem: Consider the Newton's Method for optimization \begin{align*} \nabla f(x) + \nabla^2 f(x) \Delta x = 0, \end{align*} which leads to the iterative updating \begin{align*} x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1}f(x_k). \end{align*} Let us assume that:

$$f$$ is Lipschitz Hessian: $$\Vert \nabla^2 f(x) - \nabla^2 f(y) \Vert \le M\Vert x-y \Vert$$.

$$f$$ is strong local convexity: There exists a local minimum $$x^*$$ such that $$\nabla^2 f(x^*) \succeq \mu I$$.

Locality: Starting pount $$x_0$$ "close enough" to $$x^*$$, i.e, $$\Vert x_0 - x^* \Vert < r := \dfrac{2\mu}{3M}$$.

Then, $$\Vert x_k - x^* \Vert < r$$ for all $$k$$ and the Newton method converges quadratically. \begin{align*} \Vert x_{k+1} - x^* \Vert \le \dfrac{M \Vert x_k - x^*\Vert^2}{2(\mu - M \Vert x_k - x^*\Vert)}. \end{align*}

My attempt:

Before going to prove this problem, I would like to propose a lemma that is useful for this work.

Lemma. Let $$f: \mathbb{R}^n \to \mathbb{R}^n$$. If $$f'(x)$$ exists and $$f$$ is L-smooth in a neighborhood $$x$$, $$f'(x)^{-1}$$ exists and $$\beta = \Vert f'(x)^{-1}\Vert$$, $$\Vert\delta x\Vert \le \min\left\{r,\dfrac{1}{2L\beta}\right\}$$ then $$f'(x+\delta x)^{-1}$$ exists and $$\Vert f'(x+\delta x)^{-1}\Vert \le 2\Vert F'(x)^{-1}\Vert.$$

Back to the proof.

Since $$x^*$$ is local minimum point of $$f$$, then $$\nabla f(x^*) = 0$$. Hence, we have \begin{align*} x_{k+1} - x^* &= x_k - x^* - \left[\nabla^2 f(x_k)\right]^{-1}\nabla f(x_k).\\ & = \left[\nabla^2 f(x_k)\right]^{-1}\left[\nabla^2 f(x_k)(x_k-x^*) - (\nabla f(x_k) - \nabla f(x^*))\right]. \end{align*} By Taylor's theorem \begin{align*} \nabla f(x_k) - \nabla f(x^*) = \int_{0}^1 \nabla^2 f(x_k+t(x^*-x_k))(x_k-x^*)dt, \end{align*} which leads to \begin{align*} \Vert \nabla^2 f(x_k)(x_k-x^*) - \nabla f(x_k) - \nabla f(x^*)\Vert& = \bigg\Vert \int_{0}^1 (\nabla^2 f(x_k) -\nabla^2 f(x_k+t(x^*-x_k))(x_k-x^*)dt \bigg\Vert\\ & \le \int_{0}^1 \Vert (\nabla^2 f(x_k) - \nabla^2 f(x_k+t(x^*-x_k))(x_k-x^*)\Vert dt\\ & \le \int_{0}^1 Mt\Vert x_k - x^*\Vert^2 dt = \dfrac{1}{2}M\Vert x_k-x^* \Vert^2. \end{align*} Therefore, we have \begin{align*} \Vert x_{k+1} - x^*\Vert &= \bigg\Vert \left[\nabla^2 f(x_k)\right]^{-1}\left[\nabla^2 f(x_k)(x_k-x^*) - (\nabla f(x_k) - \nabla f(x^*))\right] \bigg\Vert \\ & \le \dfrac{1}{2}M\big\Vert \left[\nabla^2 f(x_k)\right]^{-1}\big\Vert \Vert x_k-x^*\Vert^2. \end{align*} By the lemma, we see that if $$r_k = \Vert x_k - x^*\Vert \le \min\left\{r_k,\dfrac{1}{2L\beta}\right\}$$ we obtain that $$\Vert \left[\nabla^2 f(x_k)\right]^{-1}\big\Vert \le 2\Vert \left[\nabla^2 f(x^*)\right]^{-1}\big\Vert$$. So, by choosing $$x_0$$ such that $$\Vert x_0-x^*\Vert \le \min\left(r_1,r_2,\ldots, r_k, \dfrac{1}{2L\beta}\right)$$, we will claim that for every $$k$$ $$\Vert x_{k+1} - x^*\Vert \le \dfrac{M}{2}\cdot 2 \Vert \left[\nabla^2 f(x^*)\right]^{-1}\big\Vert\cdot \Vert x_k-x^*\Vert^2.$$

My question: If I end here, I still get the quadratic convergence. However, I want to get exactly the inequality \begin{align*} \Vert x_{k+1} - x^* \Vert \le \dfrac{M \Vert x_k - x^*\Vert^2}{2(\mu - M \Vert x_k - x^*\Vert)}. \end{align*} I think I have to use the assumption of strong local convexity, but I do not know how to use it. I hope that anyone can show me a way.

• I think you can improve your lemma. Using Neumann series approach, one can get a more precise bound of inverses of perturbed matrices/operators.
– daw
Commented Nov 17, 2022 at 6:42
• @daw Thank you for the recommendation. I will study this concept. Commented Nov 17, 2022 at 11:11

If $$A$$ is invertible and $$B=(I-T)A$$, with $$\|T\|<1$$, then using the Neumann and geometric series \begin{align} B^{-1}&=A^{-1}(I+T+T^2+...)\\ \|B^{-1}\|&\le \|A^{-1}\|(1+\|T\|+\|T\|^2+...)\\ &=\frac{\|A^{-1}\|}{1-\|T\|} \le\frac{\|A^{-1}\|}{1-\|A^{-1}\|\,\|B-A\|} \end{align}

Applied to the given situation, $$B=∇^2f(x_k)$$, $$A=∇^2f(x_*)$$, $$\|A^{-1}\|\le\frac1\mu$$ and $$\|B-A\|\le M\|x_k-x_*\|$$ gives $$\|[∇^2f(x_k)]^{-1}\|\le\frac1{μ-M\|x_k-x_*\|}$$

Now if $$\|x_k-x_*\|\le r=\frac{2μ}{3M}$$, then $$\|x_{k+1}-x_*\|\le\frac{\frac{4μ^2}{9M}}{2(μ-\frac23μ)}=\frac{2μ}{3M}=r$$ and moreover \begin{align} \|x_{k+1}-x_*\|&\le\frac1r\|x_k-x_*\|^2\\\implies \|x_k-x_*\|&\le r\left(\frac{\|x_0-x_*\|}{r}\right)^{2^k} \end{align}

• After reading your answer, I still can not understand how you get the result about Neumann series. May you give me a document that contains this concept? And why you can apply for the gradient below (I do not see why we have $B=(I-T)A$ in this case). Commented Nov 18, 2022 at 15:08
• The Neumann series is just the geometric series for operators. Selecting $T$ this way is just convenient, set $H=B-A$, $T=-HA^{-1}$ to get there from given matrices $A,B$. // This is an error, it should indeed be the Hessean matrices. Commented Nov 18, 2022 at 15:21
• Thank you a lot. Now, I have already understood your answer. Commented Nov 18, 2022 at 15:42
• Sorry for disturbing you again. For the last question, how can you apply your lemma in this case when you do not know $\Vert T\Vert = \Vert (\nabla^2f(x_k)^{-1} - \nabla^2 f(x^*)^{-1})A^{-1}\Vert < 1$. Commented Nov 18, 2022 at 16:15
• You get the upper bound $\|∇^2f(x_k)-∇^2f(x_*)\|·\|[∇^2f(x_*)]^{-1}\|\le M·\|x_k-x_*\|·\mu^{-1}$. Meaning you have to select the initial point with $\|x_0-x_*\|\le\frac\mu{M}$. As the radius $r$ is smaller than this bound, this condition is always satisfied for admissible $x_0$ and all the following iterates. Commented Nov 18, 2022 at 17:33