Fixed-memory L-Bfgs converges linearly under uniform curvature and scale bounds

Since $x_{\ast }$ is a global minimizer in the open domain ${\mathbb{R}}^n$, each coordinate restriction $t\mapsto f(x_{\ast }+t{e}_j)$ has a minimum at $0$, so its derivative there is zero and $\mathrm{\nabla }f(x_{\ast })=0$. For every $x\in L_0$, [F9] applied with $u=x$ and $v=x_{\ast }$ give $f(x)\ge f(x_{\ast })+\frac{\mu }{2}\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2^2$. Points outside $L_0$ have value greater than $f(x_0)\ge f(x_{\ast })$, so $x_{\ast }$ is the unique global minimizer.

Suppose $x_k\in L_0$. By [F3] and [F4], the matrix represented by the two-loop recursion is SPD and has eigenvalues in $[\underset{‾}{\lambda },\bar{\lambda }]$. If $g_k\mathrm{\ne }0$, then $-g_k^T{p}_k=g_k^T{H}_k{g}_k\ge \underset{‾}{\lambda }\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2>0,\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2=\mathrm{\parallel }{H}_k{g}_k{\mathrm{\parallel }}_2\le \bar{\lambda }\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{.}$ Thus $p_k$ is a strict descent direction. By the Euclidean inner-product convention in [F8], its descent-angle cosine satisfies $\cos {\theta }_k=\frac{-g_k^T{p}_k}{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2}\ge \frac{\underset{‾}{\lambda }}{\bar{\lambda }}>0.$ If $g_k=0$, then for every $x\in L_0$ [F9] applied with $u=x$ and $v=x_k$ gives $f(x)\ge f(x_k)+\frac{\mu }{2}\mathrm{\parallel }x-x_k{\mathrm{\parallel }}_2^2$, and points outside $L_0$ have value greater than $f(x_0)\ge f(x_k)$; hence $x_k=x_{\ast }$. Otherwise the accepted Armijo step puts $x_{k+1}$ in $L_0$.

Armijo decrease keeps every iterate in $L_0$, and convexity keeps each accepted step segment there. For $u,v\in L_0$, [F9] gives $\mathrm{\parallel }\mathrm{\nabla }f(u)-\mathrm{\nabla }f(v){\mathrm{\parallel }}_2\le \mathrm{\Lambda }\mathrm{\parallel }u-v{\mathrm{\parallel }}_2$. By [F2], every accepted strong Wolfe step is a Wolfe step, so the Wolfe hypothesis of [F6] holds. The uniform angle bound from step 1.2 then gives $\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\to 0$.

For a nonstationary step, [F5] and the bound $\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2\le \bar{\lambda }\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2$ give ${\alpha }_k\ge \frac{1-c_2}{\mathrm{\Lambda }}\frac{\underset{‾}{\lambda }}{\bar{\lambda }}\frac{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2}{\mathrm{\parallel }{p}_k{\mathrm{\parallel }}_2}\ge \frac{(1-c_2)\underset{‾}{\lambda }}{\mathrm{\Lambda }{\bar{\lambda }}^2}\mathrm{.}$ Also $-g_k^T{p}_k\ge \underset{‾}{\lambda }\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2$ by step 1.2. Using Armijo, $r_k-r_{k+1}\ge c_1{\alpha }_k(-g_k^T{p}_k)\ge \frac{c_1(1-c_2){\underset{‾}{\lambda }}^2}{\mathrm{\Lambda }{\bar{\lambda }}^2}\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2\mathrm{.}$

For $e_k:=x_k-x_{\ast }$, [F9] applied with $u=x_{\ast }$ and $v=x_k$ gives $r_k\le g_k^T{e}_k-\frac{\mu }{2}\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2-\frac{\mu }{2}\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2^2\le \frac{\mathrm{\parallel }{g}_k{\mathrm{\parallel }}_2^2}{2\mu },$ where the last inequality is completion of the square. Combining with step 3.1 yields $r_{k+1}\le (1-\kappa )r_k$. The bounds $\mu \le \mathrm{\Lambda }$, $\underset{‾}{\lambda }\le \bar{\lambda }$, and $2c_1(1-c_2)<1$ give $0<\kappa <1$.

Iterating step 4.1 proves $r_k\le (1-\kappa {)}^k{r}_0$. The strong-convexity lower bound $r_k\ge \frac{\mu }{2}\mathrm{\parallel }{e}_k{\mathrm{\parallel }}_2^2$ gives the stated iterate bound, so $x_k\to x_{\ast }$. The gradient norms also tend to zero by step 2.1 (or by continuity of $\mathrm{\nabla }f$ at $x_{\ast }$).