The Proximal Point Algorithm Is $\mathcal{O}(1/\epsilon)$

In this paper, we give two new results on the proximal point algorithm for finding a zero point of any given maximal monotone operator. First, we prove that if the sequence of regularization parameters is non-increasing then so is that of residual norms. Then, we use it to show that the proximal point algorithm can find an approximate zero point (assume the existence of such zero point) in at most $\mathcal{O}(1/\epsilon)$ outer iterations, where $\epsilon>0$ is the accuracy parameter described in the stopping criterion.



View The Proximal Point Algorithm Is $mathcal{O}(1/epsilon)$