Theorem 4.1 — the accelerated proximal point method has fixed-point residual $\|x_i-y_{i-1}\|^2\le R^2/i^2$

Let $\mathcal H$ be a real Hilbert space, let $M\in\mathcal M(\mathcal H)$ be a maximally monotone operator, let $\lambda>0$, and let $x_0,y_0,x_1,y_1,\dots\in\mathcal H$ be generated by the proposed accelerated proximal point method

Assume $\|x_0-x_*\|\le R$ for a constant $R>0$ and some $x_*\in X_*(M)=\{x:0\in Mx\}$. Then for every $i\ge1$,

Here $x_i-y_{i-1}=J_{\lambda M}(y_{i-1})-y_{i-1}$ is the fixed-point residual of the resolvent at $y_{i-1}$. The rate $O(1/i^2)$ improves the $O(1/i)$ rate of the plain proximal point method, and it holds in every real Hilbert space, for every step size and every maximally monotone operator.

Formalization Note The step size $\lambda$ is written lam. The resolvent step is encoded relationally as $\lambda^{-1}(y_i-x_{i+1})\in Mx_{i+1}$, i.e. $y_i\in(I+\lambda M)x_{i+1}$; for monotone $M$ and $\lambda>0$ the resolvent is single-valued, so the inclusion determines $x_{i+1}=J_{\lambda M}(y_i)$, and for maximally monotone $M$ it is defined everywhere (Minty), so runs exist from every start. The sequences are indexed by ℕ; $y_{-1}=y_0$ is y (0 - 1) = y 0 by natural-number subtraction. $i$ is cast to $\mathbb R$ in $R^2/i^2$.