Local regularized LM discrepancy stopping has logarithmic iteration count

Define $\gamma :=\sigma \tau \mathrm{/}[1+c{e}_0(1+\tau )]$. The bound $e_0<(\sigma \tau -1)\mathrm{/}(c(1+\tau ))$ gives $1+c{e}_0(1+\tau )<\sigma \tau$, so $\gamma >1$. Since $e_0=\mathrm{\parallel }{x}_0-x^{†}{\mathrm{\parallel }}_X\ge 0$ and $c>0$, the other smallness bound gives $0\le c{e}_0<(1-\sigma )\mathrm{/}2$. Hence $1-c{e}_0>0$; also $\sigma +c{e}_0>0$ because $\sigma >0$, and $2c{e}_0<1-\sigma$ gives $\sigma +c{e}_0<1-c{e}_0$. Thus $q=(\sigma +c{e}_0)\mathrm{/}(1-c{e}_0)$ lies in $(0,1)$.

For each pre-stop index, the given derivative bound and [F8] give $\mathrm{\parallel }{F}^{\mathrm{\prime }}(x_n^{\delta })\mathrm{\parallel }\le M$. Thus [F4] and ${\alpha }_n\le \sigma M^2\mathrm{/}(1-\sigma )$ give $e_n^2-e_{n+1}^2\ge D{R}_n^2,D:=\frac{2(\gamma -1)\sigma (1-\sigma )}{\gamma M^2}>0,$ where $R_n:=\mathrm{\parallel }F(x_n^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y$.

We construct the exact path up to its first crossing by finite induction. Initially $x_0^{\delta }=x_0\in B_{2r}(x_0)$ and $e_0=\mathrm{\parallel }{x}_0-x^{†}\mathrm{\parallel }$. Suppose $x_n^{\delta }\in B_{2r}(x_0)$ and $e_n:=\mathrm{\parallel }{x}_n^{\delta }-x^{†}\mathrm{\parallel }\le e_0$. If its residual is at most $\tau \delta$, the path stops. Otherwise [F2] with $e=e_0$ gives the range-approximation hypothesis with the $\gamma$ of step 1.1. Since $R_n>\tau \delta >0$, [F9] supplies the positive forcing parameter and unique minimizer. Applying [F4] shows $e_{n+1}\le e_n$ and $\mathrm{\parallel }{h}_n\mathrm{\parallel }\le e_n$. Hence $e_{n+1}\le e_0$ and $\mathrm{\parallel }{x}_{n+1}^{\delta }-x_0{\mathrm{\parallel }}_X\le \mathrm{\parallel }{x}_{n+1}^{\delta }-x^{†}{\mathrm{\parallel }}_X+e_0\le 2e_0<2r,$ so the next state remains in the local ball and the induction continues.

For $m\ge 1$, if no crossing has occurred in the first $m$ updates, then $R_n>\tau \delta$ for $0\le n<m$. Summing step 1.2 telescopes and yields $Dm{\tau }^2{\delta }^2<D{\sum }_{n=0}^{m-1}{R}_n^2\le e_0^2\mathrm{.}$ By [F6], choose a natural $m>e_0^2\mathrm{/}(D{\tau }^2{\delta }^2)$. The displayed inequality is impossible for that $m$, so a crossing occurs at a finite index $N_{\delta }$. Summing step 1.2 through $N_{\delta }-1$ also gives $N_{\delta }\le e_0^2\mathrm{/}(D{\tau }^2{\delta }^2)$.

Fix $n<N_{\delta }$ and set $T_n:=F^{\mathrm{\prime }}(x_n^{\delta })$, $h_n:=x_{n+1}^{\delta }-x_n^{\delta }$, $q_n:=y^{\delta }-F(x_n^{\delta })-T_n{h}_n$, and ${\mathrm{\Delta }}_n:=F(x_{n+1}^{\delta })-F(x_n^{\delta })-T_n{h}_n\mathrm{.}$ Both iterates lie in $B_{2r}(x_0)$ by step 2.1. Applying [F1] to the ordered pair $(x_n^{\delta },x_{n+1}^{\delta })$ gives $\mathrm{\parallel }{\mathrm{\Delta }}_n{\mathrm{\parallel }}_Y\le c\mathrm{\parallel }{h}_n{\mathrm{\parallel }}_X\mathrm{\parallel }F(x_{n+1}^{\delta })-F(x_n^{\delta }){\mathrm{\parallel }}_Y$. The forcing rule gives $\mathrm{\parallel }{q}_n{\mathrm{\parallel }}_Y=\sigma R_n$, while $F(x_{n+1}^{\delta })-y^{\delta }=-q_n+{\mathrm{\Delta }}_n\mathrm{.}$ Therefore, with $R_{n+1}:=\mathrm{\parallel }F(x_{n+1}^{\delta })-y^{\delta }{\mathrm{\parallel }}_Y$, $R_{n+1}\le \sigma R_n+c\mathrm{\parallel }{h}_n{\mathrm{\parallel }}_X(R_{n+1}+R_n)\mathrm{.}$ Using $\mathrm{\parallel }{h}_n\mathrm{\parallel }\le e_n\le e_0$ from [F4] and $1-c{e}_0>0$ from step 1.1 yields $R_{n+1}\le \frac{\sigma +c{e}_0}{1-c{e}_0}{R}_n=q{R}_n\mathrm{.}$

Let $K:=1+\mathrm{\parallel }F(x_0)-y{\mathrm{\parallel }}_Y$ and ${\delta }_0:=\min \{1,K\mathrm{/}\tau \}$. By [F7] and the data-noise bound, $R_0\le K$ for $0<\delta \le {\delta }_0$. If $N_{\delta }\ge 2$, the first-crossing definition gives $\tau \delta <R_{N_{\delta }-1}$, while repeated application of step 3.2 gives $R_{N_{\delta }-1}\le q^{N_{\delta }-1}{R}_0\le q^{N_{\delta }-1}K$. Since $\log$ is strictly increasing, $\log (\tau \delta \mathrm{/}K)<(N_{\delta }-1)\log q$; by [F5], $\log q<0$, so division reverses the inequality and gives $N_{\delta }\le 1+\frac{\log (K\mathrm{/}(\tau \delta ))}{-\log q}\mathrm{.}$ The same bound holds for $N_{\delta }=0$ or $1$, since $\delta \le K\mathrm{/}\tau$ makes its right side at least $1$. Finally, for $\delta \le {\delta }_0\le 1$, [F5] gives $\log \frac{K}{\tau \delta }\le \mid \log \frac{K}{\tau }\mid +\mathrm{\mid }\log \delta \mathrm{\mid },$ so, with $C:=1+[1+\mathrm{\mid }\log (K\mathrm{/}\tau )\mathrm{\mid }]\mathrm{/}(-\log q)$, the displayed bound is at most $C(1+\mathrm{\mid }\log \delta \mathrm{\mid })$, with $C$ independent of $y^{\delta }$ and $\delta$. By [F3], a finite run with cap at least $N_{\delta }$ and successful exact calls returns this crossing. The proof asserts no convergence rate for the stopped iterate.