# How to go from $\frac{\|g_{k+1}\|}{\|g_{k}\|^2} \leq c$ to $\frac{\|x_{k+1} - x_*\|}{\|x_{k} - x_*\|^2} \leq c$ as $k\to \infty$

I am reading a paper where

$$\frac{\|g_{k+1}\|}{\|g_{k}\|^2} \leq c \tag{1}$$ as $$k\to \infty$$ where $$g_k = g(x_k) \stackrel{\Delta}{=} \nabla f(x_k)$$ and $$\| \nabla^2 f(x_k)\| \leq L_H$$. Then, it is stated that from Taylor expansion of $$g_k$$ and $$g_{k+1}$$ around $$x_*$$ and from $$g(x_*)=0$$ we get

$$\frac{\|x_{k+1} - x_*\|}{\|x_{k} - x_*\|^2} \leq c \tag{2}$$ as $$k\to \infty$$. I know that the Taylor expansion is

$$g_{k+1} = \nabla f (x_k + p_k) = \nabla f (x_k) + \int_{0}^{1} \nabla^2 f (x_k + t p_k) p_k dt$$ with $$p_k = x_{k+1} - x_k$$ but I found it confusing to apply it in $$x_*$$ instead of $$x_k$$. The most possibly useful relation I have found is

$$\nabla f_k -\nabla f_* = \int_{0}^{1} \nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)dt \tag{3}$$ in the proof of Theorem 3.5 in [1] but again I could not understand how it is derived from Taylor's theorem in Theorem 2.1 in [1]. Taking the norm of $$(3)$$ we get

\begin{aligned}\| \nabla f_k\| \leq & \underbrace{\|\nabla f_k \|}_{0}+ \|\int_{0}^{1} \nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)dt \| \\ \leq & \underbrace{\|\nabla f_k \|}_{0}+ \int_{0}^{1} \|\nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)\|dt \leq L_H \|x_k - x_* \|\end{aligned}\tag{4} where $$\|\nabla^2 f(x) \| \leq L_H$$ is used. Similarly for step $$k+1$$ we get

$$\| \nabla f_{k+1}\| \leq \|x_{k+1} - x_* \|$$ which get as close to $$(2)$$. Could you please someone help to proceed?

[1]Jorge Nocedal, Numerical Optimization

• Can You give The link of the paper!!!
– user860474
Commented Jun 20, 2022 at 16:09
• @Math_Buddy Thanks for the response. You can see the end of the proof of Theorem 13 here and more specifically, eq. (82). Commented Jun 20, 2022 at 16:42
• The same fact can be found in the end of the proof of Corollary 4.8 here. Commented Jun 20, 2022 at 18:54
• Can someone explain why $$\nabla f_k -\nabla f_* = \int_{0}^{1} \nabla^2 f (x_k + t(x_* -x_k))(x_k - x_*)dt$$ using $$g_{k+1} = \nabla f (x_k + p_k) = \nabla f (x_k) + \int_{0}^{1} \nabla^2 f (x_k + t p_k) p_k dt$$? You can found this equation in Theorem 3.5 book Jorge Nocedal, Numerical Optimization. Commented Jun 24, 2022 at 12:01
• your first line is just $n$ dimensional version of: $$f'(a) - f('b) = \int_0^1 f''(a + t(b-a))(b-a)dt$$ Commented Jun 24, 2022 at 15:15

For simplicity in notation assume $$x_*=0$$ from now on. It looks as if you work in Euclidean space $$V={\Bbb R}^n$$ (but the result in fact holds in any Banach space). $$|\cdot|$$ denotes norm in $$V$$ and $$\|\cdot\|$$ is the induced operator (or matrix) norm in $$L(V)$$.

In order for this to work you need that the Jacobian $$J=Dg(0)=D^2f(0)$$ be invertible, i.e. there exists $$0<\alpha\leq \beta<+\infty$$ so that $$\alpha |x| \leq |J x| \leq \beta |x|, \ \ \forall\ x\in V.$$ $$f$$ should also be $$C^2$$ so that for any $$\epsilon>0$$ there is $$\delta(\epsilon)>0$$ so that $$\|Dg(x)-J\| < \epsilon$$ for $$|x|<\delta(\epsilon)$$.We have

$$g(x) = g(x)-g(0) = \int_0^1 \left( \frac{d}{dt} g(tx)\right) dt = \left(\int_0^1 Dg(tx) \; dt \right)x.$$ Taking $$\epsilon=\alpha/2$$ we get for $$|x|<\delta(\alpha/2)$$ $$|g(x)-Jx| = \left| \int_0^1 \left( Dg(tx)-Dg(0)\right) dt \ x \right| \leq \left\| \int_0^1 \left( Dg(tx)-Dg(0)\right) dt \right\|\ |x| \leq \alpha/2 |x|,$$ so we get for such $$x$$: $$\alpha/2 \; |x| \leq |g(x)| \leq (\beta+\alpha/2) \; |x| .$$ From this the equivalence of (1) and (2) follows (with distinct constants $$c$$) when the points are close enough to $$x_*$$ ($$=0$$). For example, if $$|x_k|,|x_{k+1}|<\delta$$ and $$|g(x_{k+1})|/|g(x_k)|^2 \leq c$$ then $$|x_{k+1}| / |x_k|^2 \leq c \times \frac{2}{\alpha} \times (\beta+\alpha/2)^2$$.

• Thanks for the response! I am trying to get into your point. You assume that $J$ is positive definite. Can we relax this by assuming positive semi-definiteness? From the technical point of view I do not understand the calculations with the integrals involving $g$. Could you please provide some more details? In addition, the upper bound of $| g(x) - Jx|$ is $\epsilon a / 2$ more correctly? Finally, could you please provide some more details on how $(1) \equiv (2)$ is implied when using the last inequality? Commented Jun 25, 2022 at 20:35
• $J$ need not be postive definite. But it must be invertible, so no zero eigenvalues. Otherwise, for $|x|>0$, the value of $|g(x)|$ may be arbitrarily close to zero. Not sure what you need for understanding the integrals. The first expresses that $g$ is the integral of its derivative (which I then calculate). The second uses the trivial identity: $Jx=Dg(0)x = \int_0^1 Dg(0) x \; dt$. I have added one direction (1) implies (2) just using the previous upper/lower bound on $|g(x)|/|x|$. Commented Jun 25, 2022 at 21:58
• Thanks for the comment and the edit! I have two questions. Why $| g(x)|$ goes to zero if $J$ has zero eigenvalue? In addition, I have some questions about $|x|<\delta(\epsilon)$? Why we need that? In addition, I am not used to bounds like $\delta(\epsilon)$. I mean using $\delta$ as a function of $\epsilon$. In the same scope, why do we use $\epsilon = a/2$? Could you please provide some details? Commented Jun 26, 2022 at 15:15
• For the $\delta=\delta(\epsilon)$ part you could just as well say: For any $\epsilon$ there is $\delta$ such that... In the present context you could say given $\epsilon=\alpha/2$ (which is what we need in the end because we want to get a non-zero lower bound for $g(x)$) there is $\delta>0$ such that ... etc.... If $v\neq 0$ is in the kernel of $J$ then for $x=v$ you have no control of what happens to $g(v)$. It could e.g. simply equal zero if $g(x)=Jx$. Commented Jun 26, 2022 at 17:28
• Thanks for the response again. I am trying to understand the example. So if there is a zero eigenvalue, then there might $a=0$ witch makes $| g(x) - Jx| \leq a |x| = 0$ which implies $g(x)=Jx$? In addition, a last question I hope. We define $| g(x) - Jx|$ to reach arithmetically the finally result but is there any intuition to compare $g(x)$, i.e., the gradient, with $Jx$, i.e., a Hessian-vector product? In other words, I am trying to understand the rationale as I didn't do it my self. Any help is highly appreciated. Commented Jun 27, 2022 at 11:32

REVISED

From Theorem 2.1 in your citation $$[1]$$ we have: for $$p_k=h_k=x_{k}-x_{*}$$ and $$x_k$$ is a sequence of points in $$\textbf{R}^N$$ such that $$\lim_{k\rightarrow \infty}x_k=x_{*}$$ , $$\nabla f(x_{*})=0$$, $$\nabla^2 f(x_{*})\neq 0$$. Hence for all $$x$$ in an open ball $$B$$ with center $$x_{*}$$ we have $$||\nabla^2f(x)||>0$$. $$\nabla f(x_k)=\nabla f(x_{*}+h_k)=\nabla f (x_*)+\int^{1}_{0}\nabla^2 f(x_{*}+th_k)h_kdt\Rightarrow$$ $$\nabla f(x_k)=\int^{1}_{0}\nabla^2 f(x_{*}+th_k)h_kdt.\tag 1$$ Since $$L_H\geq ||\nabla^2f(x)||\geq L'>0$$ : $$(2)$$ in $$B$$, we get $$||g_k||=||\int^{1}_{0}\nabla^2 f(x_{*}+th_k)h_kdt||\leq \int^{1}_{0}||\nabla^2f(x_*+th_k)||\cdot ||h_k||dt=$$ $$\leq L_H\int^{1}_{0}dt(||h_k||)=L_H ||h_k||.$$ Also it holds from the definition of norm of matrices $$A,B$$, where $$A\in M_{n\times n}$$ and $$B\in M_{n\times 1}$$ that $$||A\cdot B||\leq ||A||\cdot ||B||$$ hence we can define $$\Gamma(A,B)$$ to be such that $$\Gamma(A,B)=\frac{A\cdot B}{||A||\cdot ||B||}$$. (Note that $$\Gamma(A,B)$$ is a vector and if $$A\in M_{n\times n}$$, $$B\in M_{n\times 1}$$, then $$\Gamma=\Gamma(A,B)\in M_{n\times 1}$$ and $$0\leq ||\Gamma(A,B)||\leq 1$$ see also Matrix Norm provited that $$B$$ is small enough and positive). One can see that one such norm is $$||A||_2:=\left(\sum^{n}_{i,j=1}|a_{i,j}|^2\right)^{1/2}\textrm{, }A\in M_{n\times n}$$ and $$||B||_2:=\left(\sum^{n}_{i=1}|b_i|^2\right)^{1/2}\textrm{, }B\in M_{n\times 1}.\tag 2$$ Hence there holds if $$A,C\in M_{n\times n}$$ and $$B\in M_{n\times 1}$$ $$i)\textrm{ }||A||_2\geq 0\textrm{ and }||A||_2=0\Leftrightarrow A=0$$ $$ii)\textrm{ }||cA_2||_2=|c|\times ||A||_2$$ $$iii)\textrm{ }||A+C||_2\leq ||A||_2+||C||_2$$ $$iv)\textrm{ }||A\cdot C||_2\leq ||A||_2\cdot ||C||_2$$ $$v)\textrm{ }||A\cdot B||_2\leq ||A||_2||B||_2.$$ Also if $$A=(a_{i,j})_{n\times n}$$ and $$0<||A||_2\leq 1$$, then exists $$i_0,j_0$$ such that $$a_{i_0,j_0}\neq 0$$ and for all $$i,j\Rightarrow |a_{i,j}|\leq 1$$ and if $$B=(b_{i,j})_{n\times 1}$$ and $$0<||B||_2\leq 1$$, then exists $$i_0$$ such that $$b_{i_01}$$ and for all $$i$$, $$0<|b_{i,1}|\leq 1$$. In our case it is $$A=\nabla^2f(x_{*}+th_k)\in M_{n\times n}\textrm{ and }\Gamma_k(t),g_k,h_k\in M_{n\times 1}.$$ Also $$\Gamma_k(t)=\frac{\nabla^2f(x_{*}+th_k)\cdot h_k}{||\nabla^2f(x_{*}+th_k)||_2\cdot ||h_k||_2}.$$ Hence $$g_k=\int^{1}_{0}\nabla^2f(x_{*}+th_{k})\cdot h_kdt=\int^{1}_{0}||\nabla^2 f(x_{*}+th_k)||_2\cdot ||h_k||_2\Gamma_k(t)dt=$$ $$=||h_k||_2\int^{1}_{0}||\nabla^2 f(x_{*}+th_k)||_2\Gamma_k(t)dt.$$ Here $$\Gamma_k(t)=\sum^{n}_{j=1}\Gamma^{(j)}_{k}(t)\left(\overline{e}_{j}\right)^T$$, where $$\overline{e}_1=\{1,0,0,\ldots,0\}$$, $$\overline{e}_{2}=\{0,1,0,\ldots,0\}$$,$$\ldots$$, $$\overline{e}_{N}=\{0,0,0,\ldots,1\}$$ is the usual base of $$\textbf{R}^{n}$$ and $$\Gamma^{(j)}_{k}(t)$$ are continuous functions of a single variable in $$\textbf{R}$$ such that $$0\leq ||\Gamma_k(t)||_2\leq 1\Rightarrow 0\leq |\Gamma^{(j)}_k(t)|\leq 1$$, (since we can choose such norm). Hence in our case it is $$g_k=||h_k||_2\cdot \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\left(\sum^{n}_{j=1}\Gamma^{(j)}_{k}(t)(\overline{e}_j)^T\right)dt=$$ $$=||h_k||_2\cdot \sum^{n}_{j=1}\left(\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\cdot \Gamma^{(j)}_{k}(t)dt\right)(\overline{e}_j)^T.$$ Hence $$||g_k||_2=||h_k||_2\cdot ||\sum^{n}_{j=1}\left(\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\cdot \Gamma^{(j)}_{k}(t)dt\right)(\overline{e}_j)^T||_2.$$ But $$0<||\sum^{n}_{j=1}\int^{1}_{0}||\nabla^2 f(x_{*}+th_k)||_2\cdot \Gamma^{(j)}_k(t)dt(\overline{e}_j)^T||_2=$$ $$=\left(\sum^{n}_{j=1}\left|\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt\right|^2\right)^{1/2}\leq C.$$ Otherwise for all $$j$$ it would hold
$$\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt=0\Rightarrow ||g_k||_2=0\Rightarrow g_k=0,$$ for a certain $$k=k_0\in\textbf{N}$$ hence we have two points $$x_{k_0},x_{*}\in B$$, such that $$\nabla f(x_{*})=\nabla f(x_{k_0})=0\Rightarrow \exists \xi\in B: \nabla^2f(\xi)=0$$, which is imposible (see Mean value theorem). If we have two distinct points $$P_1,P_2$$ near each other with zero gradient, then exists point $$P_0$$ near $$P_1,P_2$$ such that Hessian is zero at $$P_0$$.

Thus from not vanish of $$||\sum^{n}_{j=1}\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt(\overline{e}_j)^T||_2=$$ $$=\left(\sum^{n}_{j=1}\left|\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt\right|^2\right)^{1/2}$$ we have that exists at least one $$j=j_0$$ such that
$$0 Hence from the continuity of all $$\Gamma^{(j)}_{k}(t)$$, we can write for some costants $$m,M$$ such that $$0 that $$0 Hence $$\frac{m ||h_{k+1}||_2}{M^2 ||h_k||_2^2}\leq\frac{||g_{k+1}||_2}{||g_k||_2^2}\leq \frac{M||h_{k+1}||_2}{m^2||h_k||_2^2}$$ Hence we have using $$||g_{k+1}||_2\leq c ||g_k||_2^2$$ that $$||h_{k+1}||_2\leq c \frac{M^2}{m}||h_k||_2^2=c' ||h_k||_2^2\textrm{, when }k>>1.$$

Note

1. In this way $$||.||_2$$ it is a traditional norm plus the condition $$||A\cdot x^{T}||\leq ||A||_2\cdot ||x^{T}||_2$$. For $$A$$ given and $$x^T$$ small enough (where $$x=\{x^{(1)},x^{(2)},\ldots,x^{(n)}\}$$).

2. We have $$S=||\sum^{n}_{j=1}\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt(\overline{e}_j)^T||_2=$$ $$=||\sum^{n}_{j=1}\left(\int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(j)}_k(t)dt\right)(\overline{e}_j)^T||_2=$$ $$||\left( \begin{array}{cc} \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(1)}_k(t)dt\\ \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(2)}_k(t)dt\\ \ldots \\ \int^{1}_{0}||\nabla^2f(x_{*}+th_k)||_2\Gamma^{(n)}_k(t)dt \end{array} \right)||_2$$ Hence from relation $$(2)$$, we get $$S=\left(\sum^{n}_{j=1}\left|\int^{1}_{0}||\nabla^2f(x_{*}+h_kt)||_2\Gamma^{(j)}_{k}dt\right|^2\right)^{1/2}$$

• Thanks for the response. In (1) $h_k$ shouldn't have transpose? In addition, (2) how is formed? If you apply norm in (1) shouldn't have an inequality? Commented Jun 24, 2022 at 20:35
• Thanks for the response! When $\cos(\theta)=\frac{A\cdot B}{||A||\cdot ||B||}$ is applied, $A$ is $\nabla^2f (x_* + t h_k)$ which is a matrix and $B$ is $h_k$ which is not a matrix. $B$ shouldn't be a matrix too? In other words, can we apply $\cos(\theta)=\frac{A\cdot B}{||A||\cdot ||B||}$ in this case? Commented Jun 27, 2022 at 10:55
• @Thoth. $B=h_k$ is also a matrix $n\times 1$ i.e. $h_k=\left(x^{(1)}_{k}-x^{(1)}_{*},x^{(2)}_{k}-x^{(2)}_{*},\ldots,x^{(N)}_k-x^{(N)}_{*}\right)^{T}$. Commented Jun 27, 2022 at 16:00
• Thanks for he response. I found it strange because in this case $\cos(\theta)=\frac{A\cdot B}{||A||\cdot ||B||}$ involves both spectral norm and $\ell_2$ norm for vectors but the definition is only about the norm between matices. This way $cos (\theta_k) = \Gamma$ is not $n \times n$ matrix but a $n \times 1$ vector. Am I suspicious without reason? Could you please explain a little? Commented Jun 27, 2022 at 16:51
• @Thoth. I have added a note (see Note-(2)) in my proof. If you want to ask something else please feel free to ask. Commented Jul 25, 2022 at 9:45