Exact-MMSE PnP-ISTA has monotone objective and vanishing gradient

For a point $s\in {\mathbb{R}}^n$, define the extended-real quadratic model ${\mu }_s(x)=g(s)+⟨\mathrm{\nabla }g(s),x-s⟩+\frac{1}{2\gamma }\mathrm{\parallel }x-s{\mathrm{\parallel }}_2^2+h_{\sigma ,\gamma }(x)$. By [F3] and $\gamma \le 1\mathrm{/}L$, its smooth part majorizes $g(x)$ and is tight at $x=s$. Adding $h_{\sigma ,\gamma }$ preserves the majorization; when $h_{\sigma ,\gamma }(x)=+\mathrm{\infty }$ both objective values are $+\mathrm{\infty }$. Thus ${\mu }_s(x)\ge f(x)$ for every $x$, and ${\mu }_s(s)=f(s)$ in extended-real order.

For $t\ge 2$ put $s=x_{t-1}\in X_{\sigma }$ and define $r_t(x)=g(s)+⟨\mathrm{\nabla }g(s),x-s⟩+\frac{1}{2\gamma }\mathrm{\parallel }x-s{\mathrm{\parallel }}_2^2-g(x)$. By [F3], $r_t(x)\ge 0$ for every $x$, $r_t(s)=0$, and $\mathrm{\nabla }{r}_t(s)=0$. Its gradient is $\mathrm{\nabla }{r}_t(x)=\mathrm{\nabla }g(s)+(x-s)\mathrm{/}\gamma -\mathrm{\nabla }g(x)$, so the triangle inequality and positive homogeneity [F6], the Lipschitz bound [F4], and the hypothesis on $\mathrm{\nabla }g$ give $\mathrm{\parallel }\mathrm{\nabla }{r}_t(x)-\mathrm{\nabla }{r}_t(y){\mathrm{\parallel }}_2\le (1\mathrm{/}\gamma +L)\mathrm{\parallel }x-y{\mathrm{\parallel }}_2\le (2\mathrm{/}\gamma )\mathrm{\parallel }x-y{\mathrm{\parallel }}_2$. On $X_{\sigma }$, ${\mu }_s-f=r_t$.

Completing the square gives ${\mu }_s(x)=\frac{1}{2\gamma }\mathrm{\parallel }x-(s-\gamma \mathrm{\nabla }g(s)){\mathrm{\parallel }}_2^2+h_{\sigma ,\gamma }(x)+g(s)-\frac{\gamma }{2}\mathrm{\parallel }\mathrm{\nabla }g(s){\mathrm{\parallel }}_2^2$. By [F1] and the exact update in [F2] with ${\tilde{D}}_{\sigma }=D_{\sigma }$, $x_t$ is the unique global minimizer of ${\mu }_{x_{t-1}}$. Hence $f(x_t)\le {\mu }_{x_{t-1}}(x_t)\le {\mu }_{x_{t-1}}(x_{t-1})=f(x_{t-1})$. Also $x_t\in X_{\sigma }$ for $t\ge 1$, where $h_{\sigma ,\gamma }$ is finite, so $f(x_t)$ is finite.

The sequence $(f(x_t){)}_{t\ge 1}$ is finite, nonincreasing by step 2.1, and bounded below by $\inf f\in \mathbb{R}$. It therefore converges: if $\mathrm{\ell }={\inf }_{t\ge 1}f(x_t)$, then for every $\epsilon >0$ some $N$ has $f(x_N)<\mathrm{\ell }+\epsilon$, and every $t\ge N$ has $\mathrm{\ell }\le f(x_t)\le f(x_N)$.

Because $x_t$ minimizes ${\mu }_s$, step 2.1 and the identity in step 1.2 yield $0\le r_t(x_t)={\mu }_s(x_t)-f(x_t)\le f(x_{t-1})-f(x_t)$. Summing from $t=2$ to $N$ gives ${\sum }_{t=2}^N{r}_t(x_t)\le f(x_1)-f(x_N)\le f(x_1)-\inf f$. The nonnegative summands therefore tend to zero.

Apply [F3] to $r_t$ with gradient Lipschitz constant $2\mathrm{/}\gamma$ and point $x_t$, taking $u_t=x_t-\frac{\gamma }{2}\mathrm{\nabla }{r}_t(x_t)$. Then $0\le r_t(u_t)\le r_t(x_t)-\frac{\gamma }{4}\mathrm{\parallel }\mathrm{\nabla }{r}_t(x_t){\mathrm{\parallel }}_2^2$. Step 3.2 implies $\mathrm{\parallel }\mathrm{\nabla }{r}_t(x_t){\mathrm{\parallel }}_2^2\le 4r_t(x_t)\mathrm{/}\gamma \to 0$.

For $t\ge 2$, $x_t$ is a global minimizer of ${\mu }_s$ and belongs to the open set $X_{\sigma }$, where ${\mu }_s$ is differentiable. For every direction $v$, the global minimum gives nonnegative directional difference quotients along $v$ and $-v$ for small positive increments; taking limits gives $⟨\mathrm{\nabla }{\mu }_s(x_t),v⟩=0$. Thus $\mathrm{\nabla }{\mu }_s(x_t)=0$. Since $r_t={\mu }_s-f$ on $X_{\sigma }$, $\mathrm{\nabla }{r}_t(x_t)=-\mathrm{\nabla }f(x_t)$; step 4.1 now proves $\mathrm{\parallel }\mathrm{\nabla }f(x_t){\mathrm{\parallel }}_2\to 0$.