{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T20:42:58Z","timestamp":1777149778518,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T00:00:00Z","timestamp":1717459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T00:00:00Z","timestamp":1717459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2006990"],"award-info":[{"award-number":["DMS-2006990"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"DOI":"10.1007\/s10107-024-02091-2","type":"journal-article","created":{"date-parts":[[2024,6,4]],"date-time":"2024-06-04T15:04:46Z","timestamp":1717513486000},"page":"49-78","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The complexity of first-order optimization methods from a metric perspective"],"prefix":"10.1007","volume":"212","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1785-1106","authenticated-orcid":false,"given":"A. S.","family":"Lewis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tonghua","family":"Tian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,4]]},"reference":[{"issue":"2","key":"2091_CR1","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1137\/040605266","volume":"6","author":"P-A Absil","year":"2005","unstructured":"Absil, P.-A., Mahony, R., Andrews, B.: Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 6(2), 531\u2013547 (2005)","journal-title":"SIAM J. Optim."},{"key":"2091_CR2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400830244","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"P-A Absil","year":"2008","unstructured":"Absil, P.-A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008)"},{"key":"2091_CR3","volume-title":"Gradient Flows in Metric Spaces and in the Space of Probability Measures","author":"L Ambrosio","year":"2008","unstructured":"Ambrosio, L., Gigli, N., Savar\u00e9, G.: Gradient Flows in Metric Spaces and in the Space of Probability Measures, 2nd edn. Birkh\u00e4user, Basel (2008)","edition":"2"},{"key":"2091_CR4","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10107-007-0133-5","volume":"116","author":"H Attouch","year":"2009","unstructured":"Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for non-smooth functions involving analytic features. Math. Program. 116, 5\u201316 (2009)","journal-title":"Math. Program."},{"key":"2091_CR5","doi-asserted-by":"publisher","first-page":"438","DOI":"10.1287\/moor.1100.0449","volume":"35","author":"H Attouch","year":"2010","unstructured":"Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka\u2013Lojasiewicz inequality. Math. Oper. Res. 35, 438\u2013457 (2010)","journal-title":"Math. Oper. Res."},{"issue":"1\u20132","key":"2091_CR6","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10107-011-0484-9","volume":"137","author":"H Attouch","year":"2013","unstructured":"Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward\u2013backward splitting, and regularized Gauss\u2013Seidel methods. Math. Program. 137(1\u20132), 91\u2013129 (2013)","journal-title":"Math. Program."},{"issue":"6","key":"2091_CR7","doi-asserted-by":"publisher","first-page":"3232","DOI":"10.1137\/090763317","volume":"20","author":"A Auslender","year":"2010","unstructured":"Auslender, A., Shefi, R., Teboulle, M.: A moving balls approximation method for a class of smooth constrained minimization problems. SIAM J. Optim. 20(6), 3232\u20133259 (2010)","journal-title":"SIAM J. Optim."},{"key":"2091_CR8","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1051\/cocv:2004013","volume":"10","author":"D Az\u00e9","year":"2004","unstructured":"Az\u00e9, D., Corvellec, J.-N.: Characterizations of error bounds for lower semi-continuous functions on metric spaces. ESAIM COCV 10, 409\u2013425 (2004)","journal-title":"ESAIM COCV"},{"key":"2091_CR9","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s10957-016-1001-3","volume":"172","author":"D Az\u00e9","year":"2017","unstructured":"Az\u00e9, D., Corvellec, J.-N.: Nonlinear error bounds via a change of function. J. Optim. Theory Appl. 172, 9\u201332 (2017)","journal-title":"J. Optim. Theory Appl."},{"key":"2091_CR10","first-page":"225","volume":"129","author":"A Barakat","year":"2020","unstructured":"Barakat, A., Bianchi, P.: Convergence rates of a momentum algorithm with bounded adaptive step size for nonconvex optimization. Proc. Mach. Learn. Res. 129, 225\u2013240 (2020)","journal-title":"Proc. Mach. Learn. Res."},{"key":"2091_CR11","doi-asserted-by":"crossref","unstructured":"Bac\u0306\u00e1k, M.: The proximal point algorithm in metric spaces. Isr. J. Math. 194, 689\u2013701 (2013)","DOI":"10.1007\/s11856-012-0091-3"},{"key":"2091_CR12","doi-asserted-by":"crossref","unstructured":"Bac\u0306\u00e1k, M.: Convex Analysis and Optimization in Hadamard Spaces. De Gruyter, Berlin (2014)","DOI":"10.1515\/9783110361629"},{"key":"2091_CR13","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s10957-017-1093-4","volume":"173","author":"GC Bento","year":"2017","unstructured":"Bento, G.C., Ferreira, O.P., Melo, J.G.: Iteration-complexity of gradient, sub-gradient and proximal point methods on Riemannian manifolds. J. Optim. Theory Appl. 173, 548\u2013562 (2017)","journal-title":"J. Optim. Theory Appl."},{"key":"2091_CR14","doi-asserted-by":"publisher","first-page":"1650","DOI":"10.1016\/j.jfa.2018.06.014","volume":"275","author":"A Blanchet","year":"2018","unstructured":"Blanchet, A., Bolte, J.: A family of functional inequalities: Lojasiewicz inequalities and displacement convex functions. J. Funct. Anal. 275, 1650\u20131673 (2018)","journal-title":"J. Funct. Anal."},{"key":"2091_CR15","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1137\/050644641","volume":"17","author":"J Bolte","year":"2006","unstructured":"Bolte, J., Daniilidis, A., Lewis, A.S.: The \u0141ojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17, 1205\u20131223 (2006)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"2091_CR16","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1137\/060670080","volume":"18","author":"J Bolte","year":"2007","unstructured":"Bolte, J., Daniilidis, A., Lewis, A.S., Shiota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556\u2013572 (2007)","journal-title":"SIAM J. Optim."},{"key":"2091_CR17","doi-asserted-by":"publisher","first-page":"3319","DOI":"10.1090\/S0002-9947-09-05048-X","volume":"362","author":"J Bolte","year":"2010","unstructured":"Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of \u0141ojasiewicz inequalities: subgradient flows, talweg, convexity. TAMS 362, 3319\u20133363 (2010)","journal-title":"TAMS"},{"key":"2091_CR18","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s10107-016-1091-6","volume":"165","author":"J Bolte","year":"2017","unstructured":"Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.: From error bounds to the complexity of first order descent methods for convex functions. Math. Program. 165, 471\u2013507 (2017)","journal-title":"Math. Program."},{"key":"2091_CR19","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1287\/moor.2015.0735","volume":"41","author":"J Bolte","year":"2016","unstructured":"Bolte, J., Pauwels, E.: Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs. Math. Oper. Res. 41, 442\u2013465 (2016)","journal-title":"Math. Oper. Res."},{"key":"2091_CR20","doi-asserted-by":"publisher","DOI":"10.1017\/9781009166164","volume-title":"An Introduction to Optimization on Smooth Manifolds","author":"N Boumal","year":"2023","unstructured":"Boumal, N.: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge (2023)"},{"key":"2091_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-positive Curvature","author":"MR Bridson","year":"1999","unstructured":"Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Springer, Berlin (1999)"},{"key":"2091_CR22","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/18M122457X","volume":"30","author":"S Chen","year":"2020","unstructured":"Chen, S., Ma, S., So, A.M.C., Zhang, T.: Proximal gradient method for nonsmooth optimization over the Stiefel manifold. SIAM J. Optim. 30, 210\u2013239 (2020)","journal-title":"SIAM J. Optim."},{"key":"2091_CR23","unstructured":"Coste, M.: An Introduction to O-minimal Geometry. In: RAAG Notes, Institut de Recherche Math\u00e9matiques de Rennes, November 1999"},{"key":"2091_CR24","first-page":"180","volume":"68","author":"E De Giorgi","year":"1980","unstructured":"De Giorgi, E., Marino, A., Tosques, M.: Problems of evolution in metric spaces and maximal decreasing curve. Atti. Accad. Naz. Lincei Rend Cl Sci. Fis. Mat. Nat. 68, 180\u2013187 (1980)","journal-title":"Atti. Accad. Naz. Lincei Rend Cl Sci. Fis. Mat. Nat."},{"key":"2091_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/j.2517-6161.1977.tb01600.x","volume":"39","author":"AP Dempster","year":"1977","unstructured":"Dempster, A.P., Laird, N.M., Rubin, D.B.: Maximum likelihood from incomplete data via the EM algorithm. J. R. Stat. Soc. Ser. B 39, 1\u201338 (1977)","journal-title":"J. R. Stat. Soc. Ser. B"},{"issue":"1","key":"2091_CR26","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/130920216","volume":"53","author":"D Drusvyatskiy","year":"2015","unstructured":"Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Curves of descent. SIAM J. Control Optim. 53(1), 114\u2013138 (2015)","journal-title":"SIAM J. Control Optim."},{"key":"2091_CR27","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/s10107-019-01432-w","volume":"185","author":"D Drusvyatskiy","year":"2021","unstructured":"Drusvyatskiy, D., Ioffe, A.D., Lewis, A.S.: Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria. Math. Program. 185, 357\u2013383 (2021)","journal-title":"Math. Program."},{"key":"2091_CR28","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/0022-247X(74)90025-0","volume":"47","author":"I Ekeland","year":"1974","unstructured":"Ekeland, I.: On the variational principle. J. Math. Anal. Appl. 47, 324\u2013353 (1974)","journal-title":"J. Math. Anal. Appl."},{"key":"2091_CR29","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1137\/0329022","volume":"29","author":"O G\u00fcler","year":"1991","unstructured":"G\u00fcler, O.: On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29, 403\u2013419 (1991)","journal-title":"SIAM J. Control Optim."},{"key":"2091_CR30","doi-asserted-by":"publisher","first-page":"4917","DOI":"10.1090\/tran\/7801","volume":"372","author":"D Hauer","year":"2019","unstructured":"Hauer, D., Maz\u00f3n, J.M.: Kurdyka\u2013Lojasiewicz-Simon inequality for gradient flows in metric spaces. TAMS 372, 4917\u20134976 (2019)","journal-title":"TAMS"},{"key":"2091_CR31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-64277-2","volume-title":"Variational Analysis of Regular Mappings","author":"AD Ioffe","year":"2017","unstructured":"Ioffe, A.D.: Variational Analysis of Regular Mappings. Springer, Berlin (2017)"},{"key":"2091_CR32","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1007\/BF02566027","volume":"70","author":"J Jost","year":"1995","unstructured":"Jost, J.: Convex functionals and generalized harmonic maps into spaces of non positive curvature. Comment. Math. Helvetici 70, 659\u2013673 (1995)","journal-title":"Comment. Math. Helvetici"},{"issue":"3","key":"2091_CR33","doi-asserted-by":"publisher","first-page":"769","DOI":"10.5802\/aif.1638","volume":"48","author":"K Kurdyka","year":"1998","unstructured":"Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier (Grenoble) 48(3), 769\u2013783 (1998)","journal-title":"Ann. Inst. Fourier (Grenoble)"},{"key":"2091_CR34","unstructured":"Lewis, A.S., L\u00f3pez, G., Nicolae, A.: Basic convex analysis in metric spaces with bounded curvature. SIAM J. Optim. arxiv:2302.03588 (2023)"},{"key":"2091_CR35","unstructured":"Lewis, A.S., Tian, T.: Identifiability, the KL property in metric spaces, and subgradient curves. arXiv:2205.02868 (2022)"},{"key":"2091_CR36","doi-asserted-by":"crossref","unstructured":"Lewis, A.S., Wright, S.J.: A proximal method for composite minimization. Math. Program. 1\u201346 (2015)","DOI":"10.1007\/s10107-015-0943-9"},{"key":"2091_CR37","unstructured":"\u0141ojasiewicz, S.: Ensembles Semi-analytiques. IHES (1965)"},{"key":"2091_CR38","doi-asserted-by":"crossref","unstructured":"Luo, Z.-Q., Tseng, P.: Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46\/47(1-4):157\u2013178 (1993). Degeneracy in optimization problems","DOI":"10.1007\/BF02096261"},{"key":"2091_CR39","doi-asserted-by":"publisher","first-page":"199","DOI":"10.4310\/CAG.1998.v6.n2.a1","volume":"6","author":"UF Mayer","year":"1998","unstructured":"Mayer, U.F.: Gradient flows on nonpositively curved metric spaces and harmonic maps. Commun. Anal. Geom. 6, 199\u2013253 (1998)","journal-title":"Commun. Anal. Geom."},{"key":"2091_CR40","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1215\/S0012-7094-62-02933-2","volume":"29","author":"GJ Minty","year":"1962","unstructured":"Minty, G.J.: Monotone (nonlinear) operators in Hilbert space. Duke Math. J. 29, 341\u2013346 (1962)","journal-title":"Duke Math. J."},{"key":"2091_CR41","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1090\/S0002-9947-1945-0011792-9","volume":"57","author":"SB Myers","year":"1945","unstructured":"Myers, S.B.: Arcs and geodesics in metric spaces. Trans. Am. Math. Soc. 57, 217\u2013227 (1945)","journal-title":"Trans. Am. Math. Soc."},{"key":"2091_CR42","doi-asserted-by":"crossref","unstructured":"Nedi\u0107, A.: Random projection algorithms for convex set intersection problems. In: 49th IEEE Conference on Decision and Control (CDC), pp. 7655\u20137660 (2010)","DOI":"10.1109\/CDC.2010.5717734"},{"key":"2091_CR43","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s10957-013-0391-8","volume":"160","author":"D Noll","year":"2014","unstructured":"Noll, D.: Convergence of non-smooth descent methods using the Kurdyka\u2013Lojasiewicz inequality. J. Optim. Theory Appl. 160, 553\u2013572 (2014)","journal-title":"J. Optim. Theory Appl."},{"key":"2091_CR44","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1561\/2200000073","volume":"11","author":"G Peyr\u00e9","year":"2019","unstructured":"Peyr\u00e9, G., Cuturi, M.: Computational optimal transport: with applications to data science. Found. Trends Mach. Learn. 11, 355\u2013607 (2019)","journal-title":"Found. Trends Mach. Learn."},{"key":"2091_CR45","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/0362-546X(85)90024-0","volume":"9","author":"RT Rockafellar","year":"1985","unstructured":"Rockafellar, R.T.: Lipschitzian properties of multi-functions. Nonlinear Anal. 9, 867\u2013885 (1985)","journal-title":"Nonlinear Anal."},{"key":"2091_CR46","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T., Wets, R.J-B.: Variational analysis. In: Grundlehren der mathematischen Wissenschaften, vol. 317. Springer, Berlin (1998)","DOI":"10.1007\/978-3-642-02431-3"},{"key":"2091_CR47","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1090\/proc\/14329","volume":"147","author":"A Valette","year":"2019","unstructured":"Valette, A.: \u0141ojasiewicz inequality at singular points. Proc. Am. Math. Soc. 147, 1109\u20131117 (2019)","journal-title":"Proc. Am. Math. Soc."},{"key":"2091_CR48","doi-asserted-by":"crossref","unstructured":"van den Dries, L.: Tame topology and o-minimal structures. In: LMS Lecture Note Series, vol. 248. Cambridge University Press, Cambridge (1998)","DOI":"10.1017\/CBO9780511525919"},{"key":"2091_CR49","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1215\/S0012-7094-96-08416-1","volume":"84","author":"L van den Dries","year":"1996","unstructured":"van den Dries, L., Miller, C.: Geometric categories and o-minimal structures. Duke Math. J. 84, 497\u2013540 (1996)","journal-title":"Duke Math. J."},{"key":"2091_CR50","first-page":"1","volume":"49","author":"H Zhang","year":"2016","unstructured":"Zhang, H., Sra, S.: First-order methods for geo-desically convex optimization. J. Mach. Learn. Res. 49, 1\u201322 (2016)","journal-title":"J. Mach. Learn. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02091-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02091-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02091-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:02:49Z","timestamp":1750176169000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02091-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,4]]},"references-count":50,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2091"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02091-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,4]]},"assertion":[{"value":"5 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2024","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 authors declare that the results presented are new, and there is no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}