Nonlinear Landweber with discrepancy stopping

Fix a current point $u$ and any exact solution $z$ in the outer ball, and set $e=u-z$, $R=F(u)-y^{\delta }$, and $w=F(u)-F(z)-F^{\mathrm{\prime }}(u)e$. The uniform TCC gives $\mathrm{\parallel }w{\mathrm{\parallel }}_Y\le \eta \mathrm{\parallel }F(u)-F(z){\mathrm{\parallel }}_Y$. Since $y=F(z)$, $y^{\delta }-F(u)+F^{\mathrm{\prime }}(u)e=y^{\delta }-y-w$, so by the noise bound and the triangle inequality, $\mathrm{\parallel }{y}^{\delta }-F(u)+F^{\mathrm{\prime }}(u)e{\mathrm{\parallel }}_Y\le \delta +\eta \mathrm{\parallel }F(u)-y{\mathrm{\parallel }}_Y\le (1+\eta )\delta +\eta \mathrm{\parallel }R{\mathrm{\parallel }}_Y$.

The update has $e^{+}=e+A^{\ast }(y^{\delta }-F(u))$. Expanding its squared norm and using the adjoint identity yields $\mathrm{\parallel }{e}^{+}{\mathrm{\parallel }}_X^2-\mathrm{\parallel }e{\mathrm{\parallel }}_X^2=2⟨y^{\delta }-F(u),Ae{⟩}_Y+\mathrm{\parallel }{A}^{\ast }(y^{\delta }-F(u)){\mathrm{\parallel }}_X^2$. Since [F13] makes $A$ a bounded operator, [F11] gives $\mathrm{\parallel }{A}^{\ast }(y^{\delta }-F(u)){\mathrm{\parallel }}_X\le \mathrm{\parallel }{A}^{\ast }\mathrm{\parallel }\mathrm{\parallel }R{\mathrm{\parallel }}_Y=\mathrm{\parallel }A\mathrm{\parallel }\mathrm{\parallel }R{\mathrm{\parallel }}_Y\le \mathrm{\parallel }R{\mathrm{\parallel }}_Y$.

Write $Ae=-(y^{\delta }-F(u))+(y^{\delta }-F(u)+Ae)$. By [F5] and step 1.2, $\mathrm{\parallel }{e}^{+}{\mathrm{\parallel }}_X^2-\mathrm{\parallel }e{\mathrm{\parallel }}_X^2\le -\mathrm{\parallel }R{\mathrm{\parallel }}_Y^2+2\mathrm{\parallel }R{\mathrm{\parallel }}_Y\mathrm{\parallel }{y}^{\delta }-F(u)+Ae{\mathrm{\parallel }}_Y$. Substituting step 1.1 gives the stated one-step estimate $\mathrm{\parallel }{e}^{+}{\mathrm{\parallel }}_X^2-\mathrm{\parallel }e{\mathrm{\parallel }}_X^2\le \mathrm{\parallel }R{\mathrm{\parallel }}_Y(2(1+\eta )\delta -(1-2\eta )\mathrm{\parallel }R{\mathrm{\parallel }}_Y)$.

If $\delta >0$ and $\mathrm{\parallel }R{\mathrm{\parallel }}_Y>\tau \delta$, then $2(1+\eta )\delta -(1-2\eta )\mathrm{\parallel }R{\mathrm{\parallel }}_Y<0$ by the strict lower bound on $\tau$, so the squared error decreases. For exact data $\delta =0$, the same bound is $-(1-2\eta )\mathrm{\parallel }R{\mathrm{\parallel }}_Y^2\le 0$ for every residual, including zero.

Put $c_{\tau }:=1-2\eta -2(1+\eta )\mathrm{/}\tau$, which is positive by the strict hypothesis on $\tau$. For each $n<N(\delta ,y^{\delta })$, the residual is greater than $\tau \delta$; step 2.1 then gives $\mathrm{\parallel }{x}_{n+1}^{\delta }-x^{†}{\mathrm{\parallel }}_X^2-\mathrm{\parallel }{x}_n^{\delta }-x^{†}{\mathrm{\parallel }}_X^2\le -c_{\tau }(R_n^{\delta }{)}^2$.

For exact data, step 2.1 gives $\mathrm{\parallel }{x}_{n+1}-x^{†}{\mathrm{\parallel }}_X^2-\mathrm{\parallel }{x}_n-x^{†}{\mathrm{\parallel }}_X^2\le -(1-2\eta )\mathrm{\parallel }F(x_n)-y{\mathrm{\parallel }}_Y^2$ for every $n$. Summing the first $K$ inequalities telescopes and yields $(1-2\eta ){\sum }_{n<K}\mathrm{\parallel }F(x_n)-y{\mathrm{\parallel }}_Y^2\le d_0^2-\mathrm{\parallel }{x}_K-x^{†}{\mathrm{\parallel }}_X^2\le d_0^2$.

The initial point satisfies $\mathrm{\parallel }{x}_0-x^{†}{\mathrm{\parallel }}_X=d_0\le r$. At every update before the noisy stop, or at every exact-data update, step 3.1 keeps $\mathrm{\parallel }{x}_n^{\delta }-x^{†}{\mathrm{\parallel }}_X\le d_0$; consequently $\mathrm{\parallel }{x}_n^{\delta }-x_0{\mathrm{\parallel }}_X\le \mathrm{\parallel }{x}_n^{\delta }-x^{†}{\mathrm{\parallel }}_X+d_0\le 2r$. Induction therefore keeps every iterate needed by the recurrence in the declared outer ball and proves Fejér decrease relative to $x^{†}$.

Suppose $\delta >0$ and the discrepancy test never succeeds. Summing step 3.2 over the first $K$ updates telescopes, while every residual exceeds $\tau \delta$, so $K{\tau }^2{\delta }^2<{\sum }_{n<K}(R_n^{\delta }{)}^2\le d_0^2\mathrm{/}{c}_{\tau }$ for every natural $K\ge 1$. The Archimedean property in [F9] supplies a natural $K>d_0^2\mathrm{/}(c_{\tau }{\tau }^2{\delta }^2)$, contradicting this bound. Hence the first stopping index is finite.

The partial sums of the nonnegative residual-square series are bounded by step 3.3. By [F8] the series converges, its tails tend to zero, and its terms tend to zero; thus $\mathrm{\parallel }F(x_n)-y{\mathrm{\parallel }}_Y\to 0$ and the claimed infinite-series bound holds.

Let $e_j:=x_j-x^{†}$, $a_j:=\mathrm{\parallel }{e}_j{\mathrm{\parallel }}_X^2$, and ${\rho }_j:=\mathrm{\parallel }F(x_j)-y{\mathrm{\parallel }}_Y$. The sequence $a_j$ is nonincreasing by step 3.1. Hence ${\mathrm{\Delta }}_j:=a_j-a_{j+1}\ge 0$, and the partial sums satisfy ${\sum }_{j<K}{\mathrm{\Delta }}_j=a_0-a_K\le a_0$. Applying [F8] again shows that the tail sums $D_n:={\sum }_{j\ge n}{\mathrm{\Delta }}_j$ tend to zero.

If $N(\delta ,y^{\delta })=0$, the bound $N(\delta ,y^{\delta })<C{\delta }^{-2}$ is immediate because $C>0$ and $\delta >0$. If $N(\delta ,y^{\delta })\ge 1$, telescoping through that positive first index gives $N(\delta ,y^{\delta }){\tau }^2{\delta }^2<d_0^2\mathrm{/}{c}_{\tau }$, hence the same bound. If $d_0=0$, then $x_0=x^{†}$ and the initial residual is at most $\delta <\tau \delta$, so $N=0$ and the same bound holds for the stated positive $C$. By [F1], a budget reaching $N$ returns the first stop, while a shorter budget returns budget_exhausted.

Fix $m\ge n$ and choose $k\in \{n,\dots ,m\}$ minimizing the finite set of residuals ${\rho }_j$; [F10] supplies a least index among minimizers. For $n\le j<m$, put $A_j=F^{\mathrm{\prime }}(x_j)$, $w_j=F(x_j)-y-A_j{e}_j$, and $v_{j,k}=F(x_j)-F(x_k)-A_j(x_j-x_k)$. The uniform TCC gives $\mathrm{\parallel }{w}_j{\mathrm{\parallel }}_Y\le \eta {\rho }_j$ and $\mathrm{\parallel }{v}_{j,k}{\mathrm{\parallel }}_Y\le \eta \mathrm{\parallel }F(x_j)-F(x_k){\mathrm{\parallel }}_Y\le \eta ({\rho }_j+{\rho }_k)\le 2\eta {\rho }_j$. Since $A_j{e}_k=(F(x_j)-y-w_j)+(F(x_k)-F(x_j)+v_{j,k})=F(x_k)-y-w_j+v_{j,k}$, Cauchy–Schwarz gives $\mathrm{\mid }⟨y-F(x_j),A_j{e}_k{⟩}_Y\mathrm{\mid }\le {\rho }_j({\rho }_k+\mathrm{\parallel }{w}_j{\mathrm{\parallel }}_Y+\mathrm{\parallel }{v}_{j,k}{\mathrm{\parallel }}_Y)\le (1+3\eta ){\rho }_j^2$.

For any fixed finite number of executed updates, the noisy iterates converge to the exact iterates as $\delta \to 0$ along data sequences whose discrepancy stop occurs no earlier. Indeed, the update map $(x,z)\mapsto x+F^{\mathrm{\prime }}(x{)}^{\ast }(z-F(x))$ is continuous: $F$ is continuous by Fréchet differentiability, $F^{\mathrm{\prime }}$ is continuous by hypothesis, and [F3] together with [F11] gives operator-norm continuity of the adjoint action. Induction from the common initial point proves the fixed-index assertion.

The exact update gives $e_{j+1}-e_j=A_j^{\ast }(y-F(x_j))$. Summing this identity and using [F3] shows $⟨e_k-e_m,e_k{⟩}_X\le (1+3\eta ){\sum }_{j=k}^{m-1}{\rho }_j^2\le (1+3\eta ){\sum }_{j\ge n}{\rho }_j^2$, and likewise $⟨e_k-e_n,e_k{⟩}_X\le (1+3\eta ){\sum }_{j=n}^{k-1}{\rho }_j^2\le (1+3\eta ){\sum }_{j\ge n}{\rho }_j^2$.

Real inner-product expansion gives $\mathrm{\parallel }{e}_m-e_k{\mathrm{\parallel }}_X^2=2⟨e_k-e_m,e_k{⟩}_X+a_m-a_k\le 2(1+3\eta ){\sum }_{j\ge n}{\rho }_j^2$, since $a_m\le a_k$. It also gives $\mathrm{\parallel }{e}_k-e_n{\mathrm{\parallel }}_X^2=2⟨e_k-e_n,e_k{⟩}_X+a_n-a_k\le 2(1+3\eta ){\sum }_{j\ge n}{\rho }_j^2+D_n$, because $a_n-a_k={\sum }_{j=n}^{k-1}{\mathrm{\Delta }}_j\le D_n$.

By the triangle inequality, $\mathrm{\parallel }{e}_m-e_n{\mathrm{\parallel }}_X\le \sqrt{2(1+3\eta ){\sum }_{j\ge n}{\rho }_j^2}+\sqrt{2(1+3\eta ){\sum }_{j\ge n}{\rho }_j^2+D_n}$, which tends to zero uniformly in $m\ge n$ by steps 4.3 and 4.4. Thus $(e_n)$ is Cauchy. Completeness of $X$ gives $x_n\to \bar{x}$. By Fréchet differentiability at $\bar{x}$, $F(x_n)-F(\bar{x})=F^{\mathrm{\prime }}(\bar{x})(x_n-\bar{x})+o(\mathrm{\parallel }{x}_n-\bar{x}{\mathrm{\parallel }}_X)$, so boundedness of $F^{\mathrm{\prime }}(\bar{x})$ implies $F(x_n)\to F(\bar{x})$; step 4.3 gives $F(\bar{x})=y$. step 4.1 and the triangle inequality give $\mathrm{\parallel }{x}_n-x_0{\mathrm{\parallel }}_X\le 2r$, so passage to the limit gives $\bar{x}\in {\bar{B}}_{2r}(x_0)$.

Suppose the uniform noisy-data conclusion fails. Then some $\epsilon >0$ and, for every integer $j\ge 1$, a positive ${\delta }_j<1\mathrm{/}j$ and admissible datum $y_j$ can be selected so that the stopped iterate is at least $\epsilon \mathrm{/}2$ from $\bar{x}$; [A1] supplies this countable selection from the nonempty bad-data sets. Let $N_j=N({\delta }_j,y_j)$. Passing to a subsequence, either $N_j$ is a fixed integer or $N_j\to \mathrm{\infty }$: a bounded sequence of natural indices has a value occurring infinitely often, and an unbounded one has an increasing subsequence chosen recursively by least indices.

In the fixed-index case, write $N_j=N$. Step 5.3 gives $x_N^{{\delta }_j}\to x_N$. Fréchet differentiability at $x_N$ and boundedness of $F^{\mathrm{\prime }}(x_N)$ imply $F(x_N^{{\delta }_j})\to F(x_N)$. The discrepancy test and noise bound give $\mathrm{\parallel }F(x_N^{{\delta }_j})-y{\mathrm{\parallel }}_Y\le \tau {\delta }_j+{\delta }_j$, so $F(x_N)=y$. The exact update at $x_N$ is then zero, so $x_n=x_N$ for every $n\ge N$ and therefore $x_N=\bar{x}$. Step 5.3 now gives $x_N^{{\delta }_j}\to \bar{x}$, contradicting the selected distance lower bound.

In the case $N_j\to \mathrm{\infty }$, choose $L$ with $\mathrm{\parallel }{x}_L-\bar{x}{\mathrm{\parallel }}_X<\epsilon \mathrm{/}4$ by step 8.1. For all sufficiently large $j$, $N_j\ge L$ and step 5.3 gives $\mathrm{\parallel }{x}_L^{{\delta }_j}-x_L{\mathrm{\parallel }}_X<\epsilon \mathrm{/}4$. Each noisy iterate before its stop stays in the outer ball by step 4.1, and $\bar{x}$ lies there by step 8.1; applying the one-step estimate of step 2.1 with the exact solution $\bar{x}$ makes the noisy iterates Fejér monotone relative to $\bar{x}$ up to $N_j$. Hence $\mathrm{\parallel }{x}_{N_j}^{{\delta }_j}-\bar{x}{\mathrm{\parallel }}_X\le \mathrm{\parallel }{x}_L^{{\delta }_j}-\bar{x}{\mathrm{\parallel }}_X<\epsilon \mathrm{/}2$, again contradicting the selected lower bound.

Both subsequence cases contradict the failure assumption in step 9.1. Therefore the supremum over all data satisfying $\mathrm{\parallel }{y}^{\delta }-y{\mathrm{\parallel }}_Y\le \delta$ tends to zero as $\delta \downarrow 0$.