5
$\begingroup$

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.

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

1 Answer 1

3
$\begingroup$

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}

$\endgroup$
6
  • $\begingroup$ 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). $\endgroup$ Commented Nov 18, 2022 at 15:08
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 18, 2022 at 15:21
  • $\begingroup$ Thank you a lot. Now, I have already understood your answer. $\endgroup$ Commented Nov 18, 2022 at 15:42
  • $\begingroup$ 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$. $\endgroup$ Commented Nov 18, 2022 at 16:15
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 18, 2022 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .