{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T15:29:23Z","timestamp":1781537363650,"version":"3.54.5"},"reference-count":38,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["INFORMS Journal on Optimization"],"published-print":{"date-parts":[[2026,4]]},"abstract":"<jats:p>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 [Formula: see text], (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 [Formula: see text] 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 [Formula: see text] 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, [Formula: see text] 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.<\/jats:p>\n                  <jats:p>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].<\/jats:p>","DOI":"10.1287\/ijoo.2025.0075","type":"journal-article","created":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T16:31:39Z","timestamp":1765297899000},"page":"141-162","source":"Crossref","is-referenced-by-count":1,"title":["Relaxed Proximal Point Algorithm: Tight Complexity Bounds and Acceleration Without Momentum"],"prefix":"10.1287","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-1367-5579","authenticated-orcid":false,"given":"Bofan","family":"Wang","sequence":"first","affiliation":[{"name":"School of Mathematics, Nanjing University, Nanjing 210093, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1967-1069","authenticated-orcid":false,"given":"Shiqian","family":"Ma","sequence":"additional","affiliation":[{"name":"Department of Computational Applied Mathematics and Operations Research, Rice University, Houston, Texas 77005"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1981-6424","authenticated-orcid":false,"given":"Junfeng","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Mathematics, Nanjing University, Nanjing 210093, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5176-739X","authenticated-orcid":false,"given":"Danqing","family":"Zhou","sequence":"additional","affiliation":[{"name":"School of Mathematics, Nanjing Audit University, Nanjing 211815, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","unstructured":"Altschuler JM (2018) Greed, hedging, and acceleration in convex optimization. MS thesis, Massachusetts Institute of Technology, Cambridge."},{"issue":"2","key":"B2","doi-asserted-by":"crossref","DOI":"10.1145\/3708502","volume":"72","author":"Altschuler JM","year":"2025","journal-title":"J. ACM"},{"issue":"1","key":"B3","doi-asserted-by":"crossref","first-page":"1105","DOI":"10.1007\/s10107-024-02164-2","volume":"213","author":"Altschuler JM","year":"2025","journal-title":"Math. Programming"},{"key":"B4","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611974997","volume-title":"First-Order Methods in Optimization","volume":"25","author":"Beck A","year":"2017"},{"issue":"1","key":"B5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"Boyd S","year":"2011","journal-title":"Foundations Trends Machine Learn."},{"issue":"2","key":"B6","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/s10589-013-9599-7","volume":"57","author":"Cai X","year":"2014","journal-title":"Comput. Optim. Appl."},{"issue":"4","key":"B7","doi-asserted-by":"crossref","first-page":"1614","DOI":"10.1137\/130940402","volume":"24","author":"Corman E","year":"2014","journal-title":"SIAM J. Optim."},{"issue":"1","key":"B8","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s10107-023-01973-1","volume":"204","author":"Das Gupta S","year":"2024","journal-title":"Math. Programming"},{"issue":"1","key":"B9","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s10107-013-0653-0","volume":"145","author":"Drori Y","year":"2014","journal-title":"Math. Programming"},{"issue":"3","key":"B10","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01581204","volume":"55","author":"Eckstein J","year":"1992","journal-title":"Math. Programming"},{"issue":"3","key":"B11","doi-asserted-by":"crossref","first-page":"2588","DOI":"10.1137\/23M1588408","volume":"34","author":"Grimmer B","year":"2024","journal-title":"SIAM J. Optim."},{"key":"B12","unstructured":"Grimmer B, Shu K, Wang AL (2023) Accelerated gradient descent via long steps. Preprint, submitted September 27, https:\/\/arxiv.org\/abs\/2309.09961."},{"key":"B13","unstructured":"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."},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1287\/ijoo.2024.0057"},{"issue":"1","key":"B15","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/s10957-022-02058-3","volume":"202","author":"Gu G","year":"2024","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"B16","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/s10589-013-9616-x","volume":"59","author":"Gu G","year":"2014","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"B17","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1137\/0329022","volume":"29","author":"G\u00fcler O","year":"1991","journal-title":"SIAM J. Control Optim."},{"issue":"4","key":"B18","doi-asserted-by":"crossref","first-page":"649","DOI":"10.1137\/0802032","volume":"2","author":"G\u00fcler O","year":"1992","journal-title":"SIAM J. Optim."},{"key":"B19","author":"Jang U","year":"2025","journal-title":"Math. Programming, ePub ahead of print August 15"},{"key":"B20","doi-asserted-by":"crossref","first-page":"23389","DOI":"10.52202\/075280-1014","volume":"36","author":"Kim J","year":"2023","journal-title":"Adv. Neural Inform. Processing Systems"},{"issue":"1","key":"B21","first-page":"123","volume":"10","author":"Krasnosel\u2019skii MA","year":"1955","journal-title":"Uspehi Mat. Nauk."},{"key":"B22","author":"Li M","year":"2013","journal-title":"Abstracts Appl. Anal."},{"key":"B23","unstructured":"Lieder F (2018) Projection based methods for conic linear programming\u2014Optimal first order complexities and norm constrained quasi Newton methods. PhD thesis, Heinrich-Heine-Universit\u00e4t, D\u00fcsseldorf, Germany."},{"key":"B24","doi-asserted-by":"crossref","unstructured":"Luner A, Grimmer B (2024) On averaging and extrapolation for gradient descent. Preprint, submitted February 26, https:\/\/arxiv.org\/abs\/2402.12493.","DOI":"10.1287\/moor.2024.0449"},{"issue":"3","key":"B25","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1090\/S0002-9939-1953-0054846-3","volume":"4","author":"Mann WR","year":"1953","journal-title":"Proc. Amer. Math. Soc."},{"issue":"3","key":"B26","first-page":"154","volume":"4","author":"Martinet B","year":"1970","journal-title":"Rev. Fran\u00e7aise Inform. Rech. Op\u00e9r."},{"key":"B27","doi-asserted-by":"crossref","first-page":"273","DOI":"10.24033\/bsmf.1625","volume":"93","author":"Moreau JJ","year":"1965","journal-title":"Bull. Soc. Math. France"},{"key":"B28","volume-title":"Springer Optimization and Its Applications","volume":"137","author":"Nesterov Y","year":"2018"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.97"},{"issue":"5","key":"B30","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1137\/0314056","volume":"14","author":"Rockafellar RT","year":"1976","journal-title":"SIAM J. Control Optim."},{"key":"B31","unstructured":"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."},{"key":"B32","volume-title":"Relaxation Methods in Theoretical Physics","author":"Southwell RV","year":"1946"},{"issue":"3","key":"B33","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1137\/16M108104X","volume":"27","author":"Taylor AB","year":"2017","journal-title":"SIAM J. Optim."},{"key":"B34","doi-asserted-by":"crossref","unstructured":"Taylor AB, Hendrickx JM, Glineur F (2017b) Performance estimation toolbox (PESTO): Automated worst-case analysis of first-order optimization methods.\n                      Proc. IEEE 56th Annual Conf. Decision Control\n                      (IEEE, Piscataway, NJ), 1278\u20131283.","DOI":"10.1109\/CDC.2017.8263832"},{"issue":"1","key":"B35","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10107-016-1009-3","volume":"161","author":"Taylor AB","year":"2017","journal-title":"Math. Programming"},{"issue":"1","key":"B36","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/s10107-022-01899-0","volume":"201","author":"Teboulle M","year":"2023","journal-title":"Math. Programming"},{"key":"B37","volume-title":"Matrix Iterative Analysis","author":"Varga RS","year":"1962"},{"key":"B38","unstructured":"Zhang Z, Jiang R (2024) Accelerated gradient descent by concatenation of step-size schedules. Preprint, submitted October 16, https:\/\/arxiv.org\/abs\/2410.12395."}],"container-title":["INFORMS Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/ijoo.2025.0075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T10:21:16Z","timestamp":1777630876000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/ijoo.2025.0075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,4]]}},"alternative-id":["10.1287\/ijoo.2025.0075"],"URL":"https:\/\/doi.org\/10.1287\/ijoo.2025.0075","relation":{},"ISSN":["2575-1484","2575-1492"],"issn-type":[{"value":"2575-1484","type":"print"},{"value":"2575-1492","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4]]}}}