{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T06:01:15Z","timestamp":1775628075632,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T00:00:00Z","timestamp":1636588800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["788368"],"award-info":[{"award-number":["788368"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"name":"miai grenoble alpes","award":["ANR-19-P3IA-0003"],"award-info":[{"award-number":["ANR-19-P3IA-0003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we present a new framework of<jats:italic>bi-level unconstrained minimization<\/jats:italic>for development of accelerated methods in Convex Programming. These methods use approximations of the high-order proximal points, which are solutions of some auxiliary parametric optimization problems. For computing these points, we can use different methods, and, in particular, the lower-order schemes. This opens a possibility for the latter methods to overpass traditional limits of the Complexity Theory. As an example, we obtain a new second-order method with the convergence rate<jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\left( k^{-4}\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mfenced><mml:msup><mml:mi>k<\/mml:mi><mml:mrow><mml:mo>-<\/mml:mo><mml:mn>4<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:mfenced><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where<jats:italic>k<\/jats:italic>is the iteration counter. This rate is better than the maximal possible rate of convergence for this type of methods, as applied to functions with Lipschitz continuous Hessian. We also present new methods with the exact auxiliary search procedure, which have the rate of convergence<jats:inline-formula><jats:alternatives><jats:tex-math>$$O\\left( k^{-(3p+1)\/ 2}\\right) $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mfenced><mml:msup><mml:mi>k<\/mml:mi><mml:mrow><mml:mo>-<\/mml:mo><mml:mo>(<\/mml:mo><mml:mn>3<\/mml:mn><mml:mi>p<\/mml:mi><mml:mo>+<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>)<\/mml:mo><mml:mo>\/<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:mfenced><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where<jats:inline-formula><jats:alternatives><jats:tex-math>$$p \\ge 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>p<\/mml:mi><mml:mo>\u2265<\/mml:mo><mml:mn>1<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is the order of the proximal operator. The auxiliary problem at each iteration of these schemes is convex.<\/jats:p>","DOI":"10.1007\/s10107-021-01727-x","type":"journal-article","created":{"date-parts":[[2021,11,11]],"date-time":"2021-11-11T13:02:19Z","timestamp":1636635739000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Inexact accelerated high-order proximal-point methods"],"prefix":"10.1007","volume":"197","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0542-8757","authenticated-orcid":false,"given":"Yurii","family":"Nesterov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,11]]},"reference":[{"key":"1727_CR1","unstructured":"Agarwal, N., Hazan, E.: Lower Bounds for Higher-Order Convex Optimization. arXiv:1710.10329v1 [math.OC] (2017)"},{"key":"1727_CR2","doi-asserted-by":"crossref","unstructured":"Arjevani, O.S., Shiff, R.: Oracle Complexity of Second-Order Methods for Smooth Convex Optimization. arXiv:1705.07260 [math.OC] (2017)","DOI":"10.1007\/s10107-018-1293-1"},{"key":"1727_CR3","unstructured":"Baes, M.: Estimate sequence methods: extensions and approximations. Optimization Online (2009)"},{"key":"1727_CR4","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.2016.0817","volume":"42","author":"HH Bauschke","year":"2016","unstructured":"Bauschke, H.H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first order methods revisited and applications. Math. Oper. Res. 42, 330\u2013348 (2016)","journal-title":"Math. Oper. Res."},{"key":"1727_CR5","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s10107-016-1065-8","volume":"163","author":"EG Birgin","year":"2017","unstructured":"Birgin, E.G., Gardenghi, J.L., Martinez, J.M., Santos, S.A., Toint, P.L.: Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Math. Program. 163, 359\u2013368 (2017)","journal-title":"Math. Program."},{"key":"1727_CR6","unstructured":"Bubeck, S., Jiang, Q., Lee, Y.T., Li, Y., Sidford, A.: Near-optimal method for highly smooth convex optimization. In: COLT, pp. 492\u2013507 (2019)"},{"issue":"2","key":"1727_CR7","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.1137\/17M1114296","volume":"28","author":"Y Carmon","year":"2018","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Accelerated methods for nonconvex optimization. SIAM J. Optim. 28(2), 1751\u20131772 (2018)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1727_CR8","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1137\/100812276","volume":"22","author":"C Cartis","year":"2021","unstructured":"Cartis, C., Gould, N., Toint, P.: On the oracle complexity of first-order and derivative-free algorithms for smooth nonconvex minimization. SIOPT 22(1), 66\u201386 (2021)","journal-title":"SIOPT"},{"key":"1727_CR9","doi-asserted-by":"crossref","unstructured":"Gasnikov, A., Gorbunov, E., Kovalev, D., Mohhamed, A., Chernousova, E.: The Global Rate of Convergence for Optimal Tensor Methods in Smooth Convex Optimization. arXiv:1809.00382 (2018)","DOI":"10.20537\/2076-7633-2018-10-6-737-753"},{"issue":"5","key":"1727_CR10","first-page":"877","volume":"14","author":"O G\u00fcller","year":"1992","unstructured":"G\u00fcller, O.: New proximal point algorithms for convex minimization. SIAM J. Control Optim. 14(5), 877\u2013898 (1992)","journal-title":"SIAM J. Control Optim."},{"issue":"4","key":"1727_CR11","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1287\/moor.19.4.790","volume":"19","author":"AN Iusem","year":"1994","unstructured":"Iusem, A.N., Svaiter, B.F., Teboulle, M.: Entropy-like proximal methods in convex programming. Math. Oper. Res. 19(4), 790\u2013814 (1994)","journal-title":"Math. Oper. Res."},{"key":"1727_CR12","unstructured":"Jiang, B., Wang, H., Zang, S.: An Optimal High-Order Tensor Method for Convex Optimization. arXiv:1812.06557 (2018)"},{"issue":"1","key":"1727_CR13","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/16M1099546","volume":"28","author":"H Lu","year":"2018","unstructured":"Lu, H., Freund, R., Nesterov, Y.: Relatively smooth convex optimization by first-order methods, and applications. SIOPT 28(1), 333\u2013354 (2018)","journal-title":"SIOPT"},{"key":"1727_CR14","doi-asserted-by":"crossref","unstructured":"Martinet, B.: Perturbation des methods d\u2019Optimization. Application., RAIRO. Analyse num\u00e9rique, tome 12, no 2, pp. 153\u2013171 (1978)","DOI":"10.1051\/m2an\/1978120201531"},{"key":"1727_CR15","doi-asserted-by":"publisher","first-page":"273","DOI":"10.24033\/bsmf.1625","volume":"93","author":"JJ Moreau","year":"1965","unstructured":"Moreau, J.J.: Proximit\u00e9 et Dualit\u00e9 dans un Espace Hilbertien. Bull. Soc. Math. France 93, 273\u2013299 (1965)","journal-title":"Bull. Soc. Math. France"},{"issue":"3","key":"1727_CR16","first-page":"543","volume":"296","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence $$O({1\\over k^2})$$. Dokl. AN SSSR 296(3), 543\u2013547 (1983)","journal-title":"Dokl. AN SSSR"},{"key":"1727_CR17","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Accelerating the cubic regularization of Newton\u2019s method on convex problems. Math. Program. 112(1), 159\u2013181 (2008)","DOI":"10.1007\/s10107-006-0089-x"},{"key":"1727_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on Convex Optimization","author":"Y Nesterov","year":"2018","unstructured":"Nesterov, Y.: Lectures on Convex Optimization. Springer, Berlin (2018)"},{"key":"1727_CR19","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.: Inexact basic tensor methods for some classes of convex optimization problems. In: Optimization Methods and Software. https:\/\/doi.org\/10.1080\/10556788.2020.1854252 (2020)","DOI":"10.1080\/10556788.2020.1854252"},{"key":"1727_CR20","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s10107-019-01449-1","volume":"186","author":"Y Nesterov","year":"2021","unstructured":"Nesterov, Y.: Implementable tensor methods in unconstrained convex optimization. Math. Program. 186, 157\u2013183 (2021)","journal-title":"Math. Program."},{"key":"1727_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10957-021-01930-y","volume":"191","author":"Y Nesterov","year":"2021","unstructured":"Nesterov, Y.: Superfast second-order methods for unconstraine convex optimization. JOTA 191, 1\u201330 (2021)","journal-title":"JOTA"},{"key":"1727_CR22","doi-asserted-by":"crossref","unstructured":"Nesterov, Y.: Inexact high-order proximal-point methods with auxiliary search procedure. Accepted for publication, SIOPT (2021)","DOI":"10.1137\/20M134705X"},{"key":"1727_CR23","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior Point Polynomial Methods in Convex Programming: Theory and Applications","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior Point Polynomial Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia (1994)"},{"issue":"3","key":"1727_CR24","first-page":"123","volume":"1","author":"N Parikh","year":"2013","unstructured":"Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 123\u2013231 (2013)","journal-title":"Found. Trends Optim."},{"key":"1727_CR25","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/moor.1.2.97","volume":"1","author":"RT Rockafellar","year":"1976","unstructured":"Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1, 97\u2013116 (1976)","journal-title":"Math. Oper. Res."},{"key":"1727_CR26","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1287\/moor.17.3.670","volume":"17","author":"M Teboulle","year":"1992","unstructured":"Teboulle, M.: Entropic proximal mapping with applications to nonlinear programming. Math. Oper. Res. 17, 670\u2013690 (1992)","journal-title":"Math. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01727-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01727-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01727-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T14:08:22Z","timestamp":1699798102000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01727-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,11]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1727"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01727-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,11]]},"assertion":[{"value":"7 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author declared that he has no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}