{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T18:48:30Z","timestamp":1778006910246,"version":"3.51.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T00:00:00Z","timestamp":1618963200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T00:00:00Z","timestamp":1618963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"European Research Council","award":["SEQUOIA 724063"],"award-info":[{"award-number":["SEQUOIA 724063"]}]},{"DOI":"10.13039\/100006394","name":"Air Force Materiel Command","doi-asserted-by":"publisher","award":["FA9550-19-1-7026"],"award-info":[{"award-number":["FA9550-19-1-7026"]}],"id":[{"id":"10.13039\/100006394","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006394","name":"Air Force Materiel Command","doi-asserted-by":"publisher","award":["FA9550-18-1-0226"],"award-info":[{"award-number":["FA9550-18-1-0226"]}],"id":[{"id":"10.13039\/100006394","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10107-021-01618-1","type":"journal-article","created":{"date-parts":[[2021,4,21]],"date-time":"2021-04-21T09:19:19Z","timestamp":1618996759000},"page":"41-83","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Optimal complexity and certification of Bregman first-order methods"],"prefix":"10.1007","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4600-7748","authenticated-orcid":false,"given":"Radu-Alexandru","family":"Dragomir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrien B.","family":"Taylor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandre","family":"d\u2019Aspremont","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00f4me","family":"Bolte","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,4,21]]},"reference":[{"issue":"3","key":"1618_CR1","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1137\/S1052623403427823","volume":"16","author":"A Auslender","year":"2006","unstructured":"Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16(3), 697\u2013725 (2006)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1618_CR2","first-page":"115","volume":"25","author":"F Bach","year":"2015","unstructured":"Bach, F.: Duality between subgradient and conditional gradient methods. SIAM J. Imaging Sci. 25(1), 115\u2013129 (2015)","journal-title":"SIAM J. Imaging Sci."},{"issue":"3","key":"1618_CR3","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1007\/s10957-019-01516-9","volume":"182","author":"HH Bauschke","year":"2019","unstructured":"Bauschke, H.H., Bolte, J., Chen, J., Teboulle, M., Wang, X.: On linear convergence of non-Euclidean gradient methods without strong convexity and Lipschitz gradient continuity. J. Optim. Theory Appl. 182(3), 1068\u20131087 (2019)","journal-title":"J. Optim. Theory Appl."},{"issue":"2","key":"1618_CR4","doi-asserted-by":"publisher","first-page":"330","DOI":"10.1287\/moor.2016.0817","volume":"42","author":"HH Bauschke","year":"2017","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(2), 330\u2013348 (2017)","journal-title":"Math. Oper. Res."},{"key":"1618_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9467-7","volume-title":".: Convex Analysis and Monotone Operator Theory in Hilbert Spaces","author":"HH Bauschke","year":"2011","unstructured":"Bauschke, H.H., Combettes, P.L.:: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer Publishing Company, Inc., Berlin (2011)"},{"issue":"3","key":"1618_CR6","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1618_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"issue":"1","key":"1618_CR8","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1137\/S1052623499354564","volume":"12","author":"A Ben-tal","year":"2001","unstructured":"Ben-tal, A., Margalit, T., Nemirovski, A.: The ordered subsets mirror descent optimization method with applications to tomography. SIAM J. Optim. 12(1), 79\u2013108 (2001)","journal-title":"SIAM J. Optim."},{"key":"1618_CR9","doi-asserted-by":"publisher","first-page":"123006","DOI":"10.1088\/0266-5611\/25\/12\/123006","volume":"25","author":"M Bertero","year":"2009","unstructured":"Bertero, M., Boccaci, P., Desidera, G., Vicidomini, G.: Image deblurring with Poisson data: from cells to galaxies. Inverse Probl. 25, 123006 (2009)","journal-title":"Inverse Probl."},{"issue":"3","key":"1618_CR10","doi-asserted-by":"publisher","first-page":"2131","DOI":"10.1137\/17M1138558","volume":"28","author":"J Bolte","year":"2018","unstructured":"Bolte, J., Sabach, S., Teboulle, M., Vaisbourd, Y.: first order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim. 28(3), 2131\u20132151 (2018)","journal-title":"SIAM J. Optim."},{"key":"1618_CR11","unstructured":"Bubeck, S.: Introduction to online optimization. Lecture Notes (2011)"},{"key":"1618_CR12","doi-asserted-by":"crossref","unstructured":"B\u00f9i, M.N., Combettes, P.L.: Bregman Forward-Backward Operator Splitting. arXiv preprint arXiv:1908.03878 (2019)","DOI":"10.1007\/s11228-020-00563-z"},{"issue":"3","key":"1618_CR13","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/BF00940051","volume":"73","author":"Y Censor","year":"1992","unstructured":"Censor, Y., Zenios, S.A.: Proximal minimization algorithm with D-functions. J. Optim. Theory Appl. 73(3), 451\u2013464 (1992)","journal-title":"J. Optim. Theory Appl."},{"key":"1618_CR14","doi-asserted-by":"publisher","unstructured":"Dragomir, R.A., d\u2019Aspremont, A., Bolte, J.: Quartic first-order methods for low rank minimization. J Optim Theory Appl. (2021). https:\/\/doi.org\/10.1007\/s10957-021-01820-3","DOI":"10.1007\/s10957-021-01820-3"},{"key":"1618_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jco.2016.11.001","volume":"39","author":"Y Drori","year":"2017","unstructured":"Drori, Y.: The exact information-based complexity of smooth convex minimization. J. Complex. 39, 1\u201316 (2017)","journal-title":"J. Complex."},{"key":"1618_CR16","unstructured":"Drori, Y., Shamir, O.: The Complexity of Finding Stationary Points with Stochastic Gradient Descent. arXiv preprint. In: Proceedings of the 37th International Conference on Machine Learning, PMLR, vol. 119, pp. 2658\u20132667 (2020)"},{"key":"1618_CR17","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10107-019-01410-2","volume":"184","author":"Y Drori","year":"2020","unstructured":"Drori, Y., Taylor, A.B.: Efficient first-order methods for convex minimization: a constructive approach. Math. Program. 184, 183\u2013220 (2020). https:\/\/doi.org\/10.1007\/s10107-019-01410-2","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1618_CR18","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s10107-013-0653-0","volume":"145","author":"Y Drori","year":"2014","unstructured":"Drori, Y., Teboulle, M.: Performance of first-order methods for smooth convex minimization: a novel approach. Math. Program. 145(1\u20132), 451\u2013482 (2014)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"1618_CR19","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10107-016-0985-7","volume":"160","author":"Y Drori","year":"2016","unstructured":"Drori, Y., Teboulle, M.: An optimal variant of Kelley\u2019s cutting-plane method. Math. Program. 160(1\u20132), 321\u2013351 (2016)","journal-title":"Math. Program."},{"issue":"1","key":"1618_CR20","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1287\/moor.18.1.202","volume":"18","author":"J Eckstein","year":"1993","unstructured":"Eckstein, J.: Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18(1), 202\u2013226 (1993)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1618_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jco.2014.08.003","volume":"31","author":"C Guzm\u00e1n","year":"2015","unstructured":"Guzm\u00e1n, C., Nemirovski, A.: On lower complexity bounds for large-scale smooth convex optimization. J. Complex. 31(1), 1\u201314 (2015)","journal-title":"J. Complex."},{"key":"1618_CR22","unstructured":"Hanzely, F., Richtarik, P., Xiao, L.: Accelerated Bregman Proximal Gradient Methods for Relatively Smooth Convex Optimization. ArXiv preprint arXiv:1808.03045v1 (2018)"},{"key":"1618_CR23","first-page":"121","volume-title":"Optimization for Machine Learning","author":"A Juditsky","year":"2010","unstructured":"Juditsky, A., Nemirovski, A.: First order methods for nonsmooth convex large-scale optimization, I : General purpose methods. In: Wright, S.S., Nowozin, S.S.J. (eds.) Optimization for Machine Learning, pp. 121\u2013147. MIT Press, Cambridge (2010)"},{"issue":"1\u20132","key":"1618_CR24","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/s10107-015-0949-3","volume":"159","author":"D Kim","year":"2016","unstructured":"Kim, D., Fessler, J.A.: Optimized first-order methods for smooth convex minimization. Math. Program. 159(1\u20132), 81\u2013107 (2016)","journal-title":"Math. Program."},{"key":"1618_CR25","unstructured":"Lofberg, J.: YALMIP : A toolbox for modeling and optimization in MATLAB. In: In Proceedings of the CACSD Conference (2004)"},{"issue":"1","key":"1618_CR26","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1137\/16M1099546","volume":"28","author":"H Lu","year":"2018","unstructured":"Lu, H., Freund, R.M., Nesterov, Y.: Relatively-smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1), 333\u2013354 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1618_CR27","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. Fr. 93(2), 273\u2013299 (1965)","journal-title":"Bull. Soc. Math. Fr."},{"key":"1618_CR28","unstructured":"Mosek, A.: The MOSEK optimization toolbox for MATLAB manual. Version 9.0. (2019). http:\/\/docs.mosek.com\/9.0\/toolbox\/index.html"},{"key":"1618_CR29","doi-asserted-by":"crossref","unstructured":"Mukkamala, M.C., Ochs, P., Pock, T., Sabach, S.: Convex-Concave Backtracking for Inertial Bregman Proximal Gradient Algorithms in Non-Convex Optimization. arXiv preprint arXiv:1904.03537 (2019)","DOI":"10.1137\/19M1298007"},{"key":"1618_CR30","unstructured":"Nemirovski, A., Yudin, D.B.: Problem Complexity and Method Efficiency in Optimization (1983)"},{"key":"1618_CR31","unstructured":"Nesterov, Y.: A Method for Solving a Convex Programming Problem with Convergence Rate O (1\/K2). In: Soviet Mathematics. Doklady, vol. 27, no. 2, pp. 367\u2013372 (1983)"},{"key":"1618_CR32","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2003","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, 1st edn. Springer Publishing Company, Inc, Berlin (2003)","edition":"1"},{"key":"1618_CR33","unstructured":"Nesterov, Y.: Implementable Tensor Methods in Unconstrained Convex Optimization. CORE Discussion Paper (2018)"},{"key":"1618_CR34","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)"},{"issue":"3","key":"1618_CR35","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1137\/16M108104X","volume":"27","author":"A Taylor","year":"2015","unstructured":"Taylor, A., Hendrickx, J., Glineur, F.: Exact worst-case performance of first-order methods for composite convex optimization. SIAM J. Optim. 27(3), 1283\u20131313 (2015)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1618_CR36","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-016-1009-3","volume":"161","author":"AB Taylor","year":"2017","unstructured":"Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Program. 161(1\u20132), 307\u2013345 (2017)","journal-title":"Math. Program."},{"key":"1618_CR37","doi-asserted-by":"crossref","unstructured":"Taylor, A.B., Hendrickx, J.M., Glineur, F.: Performance estimation toolbox (PESTO): automated worst-case analysis of first-order optimization methods. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), Melbourne, VIC, 2017, pp. 1278\u20131283. (2017). https:\/\/doi.org\/ 10.1109\/CDC.2017.8263832","DOI":"10.1109\/CDC.2017.8263832"},{"issue":"3","key":"1618_CR38","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 mappings with applications to nonlinear programming. Math. Oper. Res. 17(3), 670\u2013690 (1992)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1618_CR39","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/s10107-018-1284-2","volume":"170","author":"M Teboulle","year":"2018","unstructured":"Teboulle, M.: A simplified view of first order methods for optimization. Math. Program. 170(1), 67\u201396 (2018)","journal-title":"Math. Program."},{"issue":"1","key":"1618_CR40","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 45\u201349 (1996)","journal-title":"SIAM Rev."},{"key":"1618_CR41","first-page":"2845","volume":"28","author":"K Walid","year":"2015","unstructured":"Walid, K., Bayen, A., Bartlett, P.L.: Accelerated mirror descent in continuous and discrete time. Adv Neural Inf Process Syst 28, 2845\u20132853 (2015)","journal-title":"Adv Neural Inf Process Syst"},{"key":"1618_CR42","unstructured":"Woodworth, B., Srebro, N.: Lower Bound for Randomized First Order Convex Optimization. arXiv preprint arXiv:1709.03594 (2017)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01618-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01618-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01618-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T19:14:57Z","timestamp":1656357297000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01618-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,21]]},"references-count":42,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1618"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01618-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,21]]},"assertion":[{"value":"27 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}