An Implementable Halpern-Accelerated Proximal Point Method with Sharp Residual Rates

Halpern-accelerated proximal point methods (HPPMs) improve the fixed-point residual rate from $O(k^{-1/2})$ to $O(k^{-1})$ under exact resolvent evaluations. In practice, however, exact resolvent evaluations can be computationally expensive. To address this issue, we study an implementable HPPM with a relaxation parameter $\rho \in (0,2]$ and resolvent errors satisfying $||e_k||=O(k^{-p})$, aiming to determine the error decay required to preserve the accelerated $O(k^{-1})$ residual rate. Specifically, for every fixed $\rho \in (0,2)$, we establish the sharp worst-case residual rate $\Theta (k^{1/2-p})$ for $0<p<3/2$ and $\Theta (k^{-1})$ for $p\ge 3/2$. Thus, $p=3/2$ is the exact threshold for preserving the accelerated $O(k^{-1})$ residual rate, removing the extraneous \(\log k\) factor in existing upper bounds. By contrast, at the boundary $\rho =2$, we obtain the sharp rates $\Theta (k^{1-p})$ for $0<p<2$, $\Theta ((\log k)/k)$ for $p=2$, and $\Theta (k^{-1})$ for $p>2$. Matching lower-bound constructions establish the sharpness of all these rates. These results precisely characterize the resolvent accuracy required to retain Halpern acceleration under approximate resolvent evaluations.