{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T21:41:11Z","timestamp":1780090871400,"version":"3.54.0"},"reference-count":57,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>We study Sinkhorn\u2019s algorithm for solving the entropically regularized optimal transport problem. Its iterate [Formula: see text] is shown to satisfy [Formula: see text], where H denotes relative entropy and [Formula: see text] denotes the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with sub-Gaussian marginals. We also obtain the rate [Formula: see text] for the dual suboptimality and [Formula: see text] for the marginal entropies. More precisely, we derive nonasymptotic bounds, and in contrast to previous results on linear convergence that are limited to bounded costs, our estimates do not deteriorate exponentially with the regularization parameter. We also obtain a stability result for [Formula: see text] as a function of the marginals quantified in relative entropy.<\/jats:p>\n                  <jats:p>Funding: P. Ghosal was supported by the National Science Foundation [Grant DMS-2153661]. M. Nutz was supported by the National Science Foundation [Grants DMS-1812661, DMS-2106056, and DMS-2407074].<\/jats:p>","DOI":"10.1287\/moor.2024.0427","type":"journal-article","created":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T12:58:05Z","timestamp":1746709085000},"page":"1080-1096","source":"Crossref","is-referenced-by-count":7,"title":["On the Convergence Rate of Sinkhorn\u2019s Algorithm"],"prefix":"10.1287","volume":"51","author":[{"given":"Promit","family":"Ghosal","sequence":"first","affiliation":[{"name":"Department of Statistics, University of Chicago, Chicago, Illinois 60637"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2936-2315","authenticated-orcid":false,"given":"Marcel","family":"Nutz","sequence":"additional","affiliation":[{"name":"Department of Statistics, Columbia University, New York, New York 10025"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1137\/21M1440165"},{"key":"B2","doi-asserted-by":"crossref","unstructured":"Alvarez-Melis D, Jaakkola T (2018) Gromov\u2013Wasserstein alignment of word embedding spaces.\n                      Proc. 2018 Conf. Empirical Methods Natl. Language Processing\n                      (Association for Computational Linguistics, Stroudsburg, PA), 1881\u20131890.","DOI":"10.18653\/v1\/D18-1214"},{"key":"B3","volume-title":"A Primer of Nonlinear Analysis","volume":"34","author":"Ambrosetti A","year":"1995"},{"key":"B4","unstructured":"Arjovsky M, Chintala S, Bottou L (2017) Wasserstein generative adversarial networks.\n                      ICML\u201917 Proc. 34th Internat. Conf. Machine Learn.\n                      , vol. 70 (ACM, New York), 214\u2013223."},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.3150\/24-BEJ1725"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-020-01127-x"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1215\/00127094-2022-0035"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2023.11.007"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.5802\/afst.1095"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1137\/21M1410634"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1137\/19M1253800"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1051\/cocv\/2024013"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/s00526-023-02455-0"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061382"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-015-0803-z"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1214\/16-AOS1450"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1080\/03605302.2023.2215527"},{"key":"B18","doi-asserted-by":"crossref","unstructured":"Chizat L, Delalande A, Va\u0161kevi\u010dius T (2024) Sharper exponential convergence rates for Sinkhorn\u2019s algorithm in continuous settings. Preprint, submitted July 1, https:\/\/arxiv.org\/abs\/2407.01202.","DOI":"10.1007\/s10107-025-02242-z"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582220"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2021.108964"},{"key":"B21","unstructured":"Conforti G, Durmus A, Greco G (2023) Quantitative contraction rates for Sinkhorn algorithm: Beyond bounded costs and compact marginals. Preprint, submitted April 10, https:\/\/arxiv.org\/abs\/2304.04451."},{"key":"B22","unstructured":"Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport.\n                      Adv. Neural Inform. Processing Systems\n                      , vol. 26 (MIT Press, Cambridge, MA), 2292\u20132300."},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1214\/23-AAP1970"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731829"},{"key":"B25","unstructured":"Eckstein S (2023) Hilbert\u2019s projective metric for functions of bounded growth and exponential convergence of Sinkhorn\u2019s algorithm. Preprint, submitted November 7, https:\/\/arxiv.org\/abs\/2311.04041."},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1137\/21M145505X"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.0245"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0086180"},{"key":"B29","first-page":"83","volume":"19","author":"Fortet R","year":"1940","journal-title":"J. Math. Pures Appl."},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(89)90490-4"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392620"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2022.109622"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.4171\/jems\/1042"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/55.1.179"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177698249"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1007\/s00245-020-09697-w"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2011.11.026"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.3934\/dcds.2014.34.1533"},{"key":"B39","unstructured":"L\u00e9onard C (2019) Revisiting Fortet\u2019s proof of existence of a solution to the Schr\u00f6dinger system. Preprint, submitted April 30, https:\/\/arxiv.org\/abs\/1904.13211."},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-020-01325-7"},{"key":"B41","unstructured":"Mena G, Niles-Weed J (2019) Statistical bounds for entropic optimal transport: Sample complexity and the central limit theorem.\n                      Adv. Neural Inform. Processing Systems\n                      , vol. 32 (MIT Press, Cambridge, MA), 4541\u20134551."},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1214\/ECP.v7-1061"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-004-0340-4"},{"key":"B44","author":"Nenna L","year":"2024","journal-title":"Canadian J. Math."},{"key":"B45","unstructured":"Nutz M (2021) Introduction to entropic optimal transport. Working paper, Columbia University, New York."},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-021-01096-8"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1214\/22-AOP1611"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.1214\/23-AAP1983"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1561\/2200000073"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176324703"},{"key":"B52","first-page":"144","volume":"144","author":"Schr\u00f6dinger E","year":"1931","journal-title":"Akad. Wiss. Berlin. Phys. Math."},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177703591"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1967.21.343"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"B56","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71050-9"},{"key":"B57","unstructured":"Weed J (2018) An explicit analysis of the entropic penalty in linear programming.\n                      Proc. Machine Learn. Res.\n                      , vol. 75 (PMLR, New York), 1841\u20131855."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2024.0427","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:27:16Z","timestamp":1778228836000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2024.0427"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":57,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2024.0427"],"URL":"https:\/\/doi.org\/10.1287\/moor.2024.0427","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}