Relaxed Proximal Point Algorithm: Tight Complexity Bounds and Acceleration Without Momentum

In this paper, we focus on the relaxed proximal point algorithm (RPPA) for solving convex (possibly nonsmooth) optimization problems. We conduct a comprehensive study on three types of relaxation schedules: (i) constant schedule with relaxation parameter ${\alpha }_k\equiv \alpha \in (0,\sqrt{2}]$, (ii) a dynamic schedule put forward by Teboulle and Vaisbourd, and (iii) the silver step-size schedule proposed by Altschuler and Parrilo. The latter two schedules were initially investigated for the gradient descent (GD) method and are extended to the RPPA in this paper. For type (i), we establish tight nonergodic $O(1/N)$ convergence rate results measured by function value residual and subgradient norm, where N denotes the iteration counter. For type (ii), we establish a convergence rate that is tight and approximately $\sqrt{2}$ times better than the constant schedule of type (i). For type (iii), aside from the original silver step-size schedule proposed previously, we propose two new modified silver step-size schedules, and for all the three silver step-size schedules, $O(1/N^{1.2716})$ accelerated convergence rate results with respect to three different performance metrics are established. Furthermore, our research affirms a previous conjecture by Luner and Grimmer on the GD method with the original silver step-size schedule.

Funding: B. Wang, J. Yang, and D. Zhou were supported by the National Natural Science Foundation of China [Grants 12431011 and 12371301] and the Key Laboratory of Numerical Simulation of Large Scale Complex Systems of the Ministry of Education of China. S. Ma was supported in part by the National Science Foundation [Grants CCF-2311275 and ECCS-2326591].