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

References

• Altschuler JM (2018) Greed, hedging, and acceleration in convex optimization. MS thesis, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Altschuler JM, Parrilo PA (2025a) Acceleration by step-size hedging: Multi-step descent and the silver step-size schedule. J. ACM 72(2):1–38.Google Scholar
• Altschuler JM, Parrilo PA (2025b) Acceleration by step-size hedging: Silver step-size schedule for smooth convex optimization. Math. Programming 213(1):1105–1118.Google Scholar
• Beck A (2017) First-Order Methods in Optimization, MOS-SIAM Series in Optimization, vol. 25 (SIAM, Philadelphia).Google Scholar
• Boyd S, Parikh N, Chu E, Peleato J, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations Trends Machine Learn. 3(1):1–122.Google Scholar
• Cai X, Gu G, He B (2014) On the O(1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators. Comput. Optim. Appl. 57(2):339–363.Google Scholar
• Corman E, Yuan X (2014) A generalized proximal point algorithm and its convergence rate. SIAM J. Optim. 24(4):1614–1638.Google Scholar
• Das Gupta S, Van Parys BPG, Ryu EK (2024) Branch-and-bound performance estimation programming: A unified methodology for constructing optimal optimization methods. Math. Programming 204(1–2):567–639.Google Scholar
• Drori Y, Teboulle M (2014) Performance of first-order methods for smooth convex minimization: A novel approach. Math. Programming 145(1):451–482.Google Scholar
• Eckstein J, Bertsekas DP (1992) On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Programming 55(3):293–318.Google Scholar
• Grimmer B (2024) Provably faster gradient descent via long steps. SIAM J. Optim. 34(3):2588–2608.Google Scholar
• Grimmer B, Shu K, Wang AL (2023) Accelerated gradient descent via long steps. Preprint, submitted September 27, https://arxiv.org/abs/2309.09961.Google Scholar
• Grimmer B, Shu K, Wang AL (2024) Composing optimized step-size schedules for gradient descent. Preprint, submitted October 21, https://arxiv.org/abs/2410.16249.Google Scholar
• Grimmer B, Shu K, Wang AL (2025) Accelerated objective gap and gradient norm convergence for gradient descent via long steps. INFORMS J. Optim. 7(2):156–169.Link, Google Scholar
• Gu G, Yang J (2024) Tight ergodic sublinear convergence rate of the relaxed proximal point algorithm for monotone variational inequalities. J. Optim. Theory Appl. 202(1):373–387.Google Scholar
• Gu G, He B, Yuan X (2014) Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: A unified approach. Comput. Optim. Appl. 59(1–2):135–161.Google Scholar
• Güler O (1991) On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29(2):403–419.Google Scholar
• Güler O (1992) New proximal point algorithms for convex minimization. SIAM J. Optim. 2(4):649–664.Google Scholar
• Jang U, Das Gupta S, Ryu EK (2025) Computer-assisted design of accelerated composite optimization methods: OptISTA. Math. Programming, ePub ahead of print August 15, https://doi.org/10.1007/s10107-025-02258-5.Google Scholar
• Kim J, Ozdaglar A, Park C, Ryu EK (2023) Time-reversed dissipation induces duality between minimizing gradient norm and function value. Adv. Neural Inform. Processing Systems 36:23389–23440. Google Scholar
• Krasnosel’skii MA (1955) Two remarks on the method of successive approximations. Uspehi Mat. Nauk. 10(1(63)):123–127.Google Scholar
• Li M, You Y (2013) Convergence analysis of the relaxed proximal point algorithm. Abstracts Appl. Anal. 2013:912846.Google Scholar
• Lieder F (2018) Projection based methods for conic linear programming—Optimal first order complexities and norm constrained quasi Newton methods. PhD thesis, Heinrich-Heine-Universität, Düsseldorf, Germany.Google Scholar
• Luner A, Grimmer B (2024) On averaging and extrapolation for gradient descent. Preprint, submitted February 26, https://arxiv.org/abs/2402.12493.Google Scholar
• Mann WR (1953) Mean value methods in iteration. Proc. Amer. Math. Soc. 4(3):506–510.Google Scholar
• Martinet B (1970) Brève communication. Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Inform. Rech. Opér. 4(R3):154–158.Google Scholar
• Moreau JJ (1965) Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. France 93:273–299.Google Scholar
• Nesterov Y (2018) Lectures on Convex Optimization, Springer Optimization and Its Applications, vol. 137, 2nd ed. (Springer, Cham, Switzerland).Google Scholar
• Rockafellar RT (1976a) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
• Rockafellar RT (1976b) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898.Google Scholar
• Rotaru T, Glineur F, Patrinos P (2024) Exact worst-case convergence rates of gradient descent: A complete analysis for all constant step-sizes over nonconvex and convex functions. Preprint, submitted January 25, https://arxiv.org/abs/2406.17506.Google Scholar
• Southwell RV (1946) Relaxation Methods in Theoretical Physics (Clarendon Press, Oxford, UK).Google Scholar
• Taylor AB, Hendrickx JM, Glineur F (2017a) Exact worst-case performance of first-order methods for composite convex optimization. SIAM J. Optim. 27(3):1283–1313.Google Scholar
• Taylor AB, Hendrickx JM, Glineur F (2017b) Performance estimation toolbox (PESTO): Automated worst-case analysis of first-order optimization methods. Proc. IEEE 56th Annual Conf. Decision Control (IEEE, Piscataway, NJ), 1278–1283.Google Scholar
• Taylor AB, Hendrickx JM, Glineur F (2017c) Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Programming 161(1–2):307–345.Google Scholar
• Teboulle M, Vaisbourd Y (2023) An elementary approach to tight worst case complexity analysis of gradient based methods. Math. Programming 201(1–2):63–96.Google Scholar
• Varga RS (1962) Matrix Iterative Analysis (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• Zhang Z, Jiang R (2024) Accelerated gradient descent by concatenation of step-size schedules. Preprint, submitted October 16, https://arxiv.org/abs/2410.12395.Google Scholar