{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:40:36Z","timestamp":1787341236146,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We examine the last-iterate convergence rate of Bregman proximal methods\u2014from mirror descent to mirror-prox and its optimistic variants\u2014as a function of the local geometry induced by the prox-mapping defining the method. For generality, we focus on local solutions of constrained, nonmonotone variational inequalities, and we show that the convergence rate of a given method depends sharply on its associated Legendre exponent, a notion that measures the growth rate of the underlying Bregman function (Euclidean, entropic, or other) near a solution. In particular, we show that boundary solutions exhibit a stark separation of regimes between methods with a zero and nonzero Legendre exponent: The former converge at a linear rate, while the latter converge, in general, sublinearly. This dichotomy becomes even more pronounced in linearly constrained problems where methods with entropic regularization achieve a linear convergence rate along sharp directions, compared to convergence in a finite number of steps under Euclidean regularization.<\/jats:p>","DOI":"10.1137\/23m1580218","type":"journal-article","created":{"date-parts":[[2024,7,9]],"date-time":"2024-07-09T04:01:20Z","timestamp":1720497680000},"page":"2440-2471","source":"Crossref","is-referenced-by-count":2,"title":["The Rate of Convergence of Bregman Proximal Methods: Local Geometry Versus Regularity Versus Sharpness"],"prefix":"10.1137","volume":"34","author":[{"given":"Wa\u00efss","family":"Azizian","sequence":"first","affiliation":[{"name":"Universit\u00e9 Grenoble, Alpes, LJK, Grenoble 38000 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2537-380X","authenticated-orcid":true,"given":"Franck","family":"Iutzeler","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble, Alpes, LJK, Grenoble 38000 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0371-0457","authenticated-orcid":true,"given":"J\u00e9r\u00f4me","family":"Malick","sequence":"additional","affiliation":[{"name":"Universit\u00e9, Alpes, CNRS, Grenoble, INP, LJK, Grenoble 38000 France."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2026-9616","authenticated-orcid":true,"given":"Panayotis","family":"Mertikopoulos","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Grenoble, Alpes, CNRS, Inria, Grenoble, INP, LIG, Grenoble 38000 France."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,9]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012902419977"},{"key":"ref2","unstructured":"K. Antonakopoulos, E. Veronica Belmega, and P. Mertikopoulos, An adaptive mirror-prox algorithm for variational inequalities with singular operators, in NeurIPS \u201919: Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019, pp. 8455\u20138465."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0568-x"},{"key":"ref5","unstructured":"W. Azizian, F. Iutzeler, J. Malick, and P. Mertikopoulos, The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities, in COLT \u201921: Proceedings of the 34th Annual Conference on Learning Theory, 2021, pp. 326\u2013358."},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0817"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(02)00231-6"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(67)90040-7"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0803026"},{"key":"ref12","unstructured":"C.K. Chiang, T. Yang, C.J. Lee, M. Mahdavi, C.J. Lu, R. Jin, and S. Zhu, Online optimization with gradual variations, in COLT \u201912: Proceedings of the Conference on Learning Theory, PMLR, 2012, pp. 6.1\u20136.20."},{"key":"ref13","series-title":"Springer Series Oper. Res. Financ. Eng.","volume-title":"Finite-Dimensional Variational Inequalities and Complementarity Problems","author":"Facchinei F.","year":"2003"},{"key":"ref14","volume-title":"Game Theory","author":"Fudenberg D.","year":"1991"},{"key":"ref15","unstructured":"G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julien, A variational inequality perspective on generative adversarial networks, in ICLR \u201919: Proceedings of the 2019 International Conference on Learning Representations, 2019."},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56468-0"},{"key":"ref17","unstructured":"Y.G. Hsieh, F. Iutzeler, J. Malick, and P. Mertikopoulos, On the convergence of single-call stochastic extra-gradient methods, in NeurIPS \u201919: Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019, pp. 6936\u20136946."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1287\/10-SSY011"},{"key":"ref19","first-page":"1865","volume":"13","author":"Kakade S. M.","year":"2012","journal-title":"J. Mach. Learn. Res."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012995281742"},{"key":"ref21","first-page":"747","volume":"12","author":"Korpelevich G. M.","year":"1976","journal-title":"\u00c8konom. i Mat. Metody"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1137\/16M1099546"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1137\/14097238X"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0778"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1254-8"},{"key":"ref26","unstructured":"P. Mertikopoulos, B. Lecouat, H. Zenati, C.S. Foo, V. Chandrasekhar, and G. Piliouras, Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile, in ICLR \u201919: Proceedings of the 2019 International Conference on Learning Representations, 2019."},{"key":"ref27","unstructured":"A. Mokhtari, A. Ozdaglar, and S. Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach, in AISTATS \u201920: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020, pp. 1497\u20131507."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"ref29","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovski A. S.","year":"1983"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0149-x"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"E. Pauwels, On the Nature of Bregman Functions, preprint, arXiv:2302.02689, 2023.","DOI":"10.1016\/j.orl.2024.107183"},{"key":"ref34","volume-title":"Introduction to Optimization","author":"Polyak B. T.","year":"1987"},{"key":"ref35","first-page":"845","volume":"28","author":"Popov L. D.","year":"1980","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"ref36","unstructured":"A. Rakhlin and K. Sridharan, Optimization, learning, and games with predictable sequences, in NIPS \u201913: Proceedings of the 27th International Conference on Neural Information Processing Systems, 2013, pp. 3066\u20133074."},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1513508112"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1007\/BF01016429"},{"key":"ref41","first-page":"995","volume":"6","author":"Tsuda K.","year":"2005","journal-title":"J. Mach. Learn. Res."},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840454"},{"key":"ref43","unstructured":"C.Y. Wei, C.W. Lee, M. Zhang, and H. Luo, Linear last-iterate convergence in constrained saddle-point optimization, in ICLR \u201921: Proceedings of the 2021 International Conference on Learning Representations, 2021."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1580218","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:10:48Z","timestamp":1787339448000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1580218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,9]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1137\/23M1580218"],"URL":"https:\/\/doi.org\/10.1137\/23m1580218","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,9]]}}}