{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T18:32:44Z","timestamp":1772044364909,"version":"3.50.1"},"reference-count":39,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T00:00:00Z","timestamp":1619740800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>This article describes a set of methods for quickly computing the solution to the regularized optimal transport problem. It generalizes and improves upon the widely used iterative Bregman projections algorithm (or Sinkhorn\u2013Knopp algorithm). We first proposed to rely on regularized nonlinear acceleration schemes. In practice, such approaches lead to fast algorithms, but their global convergence is not ensured. Hence, we next proposed a new algorithm with convergence guarantees. The idea is to overrelax the Bregman projection operators, allowing for faster convergence. We proposed a simple method for establishing global convergence by ensuring the decrease of a Lyapunov function at each step. An adaptive choice of the overrelaxation parameter based on the Lyapunov function was constructed. We also suggested a heuristic to choose a suitable asymptotic overrelaxation parameter, based on a local convergence analysis. Our numerical experiments showed a gain in convergence speed by an order of magnitude in certain regimes.<\/jats:p>","DOI":"10.3390\/a14050143","type":"journal-article","created":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T05:10:55Z","timestamp":1619759455000},"page":"143","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Overrelaxed Sinkhorn\u2013Knopp Algorithm for Regularized Optimal Transport"],"prefix":"10.3390","volume":"14","author":[{"given":"Alexis","family":"Thibault","sequence":"first","affiliation":[{"name":"Inria Bordeaux, 33400 Talence, France"}]},{"given":"L\u00e9na\u00efc","family":"Chizat","sequence":"additional","affiliation":[{"name":"Laboratoire de Math\u00e9matiques d\u2019Orsay, CNRS, Universit\u00e9 Paris-Saclay, 91400 Orsay, France"}]},{"given":"Charles","family":"Dossal","sequence":"additional","affiliation":[{"name":"Institute of Mathematics of Toulouse, UMR 5219, INSA Toulouse, 31400 Toulouse, France"}]},{"given":"Nicolas","family":"Papadakis","sequence":"additional","affiliation":[{"name":"Institut de Math\u00e9matiques de Bordeaux, University of Bordeaux, Bordeaux INP, CNRS, IMB, UMR 5251, 33400 Talence, France"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,30]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1026543900054","article-title":"The Earth Mover\u2019s Distance As a Metric for Image Retrieval","volume":"40","author":"Rubner","year":"2000","journal-title":"Int. J. Comput. Vis."},{"key":"ref_2","unstructured":"Cuturi, M. (2013, January 5\u20138). Sinkhorn distances: Lightspeed computation of optimal transport. Proceedings of the Advances in Neural Information Processing Systems 27, Lake Tahoe, NV, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1214\/aoms\/1177703591","article-title":"A relationship between arbitrary positive matrices and doubly stochastic matrices","volume":"35","author":"Sinkhorn","year":"1964","journal-title":"Ann. Math. Stat."},{"key":"ref_4","unstructured":"Seguy, V., and Cuturi, M. (2015, January 7\u201312). Principal geodesic analysis for probability measures under the optimal transport metric. Proceedings of the Advances in Neural Information Processing Systems 29, Montreal, QC, Canada."},{"key":"ref_5","unstructured":"Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A. (2015). Optimal Transport for Domain Adaptation. arXiv."},{"key":"ref_6","unstructured":"Frogner, C., Zhang, C., Mobahi, H., Araya-Polo, M., and Poggio, T. (2015). Learning with a Wasserstein Loss. arXiv."},{"key":"ref_7","unstructured":"Montavon, G., M\u00fcller, K.R., and Cuturi, M. Wasserstein Training of Restricted Boltzmann Machines. Proceedings of the Advances in Neural Information Processing Systems 30, Barcelona, Spain, 29 November\u201310 December 2016."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Rolet, A., Cuturi, M., and Peyr\u00e9, G. (2016, January 9\u201311). Fast Dictionary Learning with a Smoothed Wasserstein Loss. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), Cadiz, Spain.","DOI":"10.1137\/15M1032600"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1137\/17M1140431","article-title":"Wasserstein dictionary learning: Optimal transport-based unsupervised nonlinear dictionary learning","volume":"11","author":"Schmitz","year":"2018","journal-title":"SIAM J. Imaging Sci."},{"key":"ref_10","first-page":"590","article-title":"Regularized optimal transport and the rot mover\u2019s distance","volume":"19","author":"Dessein","year":"2018","journal-title":"J. Mach. Learn. Res."},{"key":"ref_11","unstructured":"Rabin, J., and Papadakis, N. (2014, January 13). Non-convex Relaxation of Optimal Transport for Color Transfer Between Images. Proceedings of the NIPS Workshop on Optimal Transport for Machine Learning (OTML\u201914), Quebec, QC, Canada."},{"key":"ref_12","unstructured":"Chizat, L., Peyr\u00e9, G., Schmitzer, B., and Vialard, F.X. (2016). Scaling Algorithms for Unbalanced Transport Problems. arXiv."},{"key":"ref_13","unstructured":"Altschuler, J., Weed, J., and Rigollet, P. (2017, January 4\u20139). Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Proceedings of the Advances in Neural Information Processing Systems 31, Long Beach, CA, USA."},{"key":"ref_14","unstructured":"Alaya, M.Z., Berar, M., Gasso, G., and Rakotomamonjy, A. (2019). Screening sinkhorn algorithm for regularized optimal transport. arXiv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0041-5553(64)90137-5","article-title":"Some methods of speeding up the convergence of iteration methods","volume":"4","author":"Polyak","year":"1964","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ghadimi, E., Feyzmahdavian, H.R., and Johansson, M. (2014). Global convergence of the Heavy-ball method for convex optimization. arXiv.","DOI":"10.1109\/ECC.2015.7330562"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/BF01128757","article-title":"Heavy-ball method in nonconvex optimization problems","volume":"4","author":"Zavriev","year":"1993","journal-title":"Comput. Math. Model."},{"key":"ref_18","unstructured":"Ochs, P. (2016). Local Convergence of the Heavy-ball Method and iPiano for Non-convex Optimization. arXiv."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321296.321305","article-title":"Iterative procedures for nonlinear integral equations","volume":"12","author":"Anderson","year":"1965","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Scieur, D., d\u2019Aspremont, A., and Bach, F. (2016, January 5\u201310). Regularized Nonlinear Acceleration. Proceedings of the Advances in Neural Information Processing Systems 30, Barcelona, Spain."},{"key":"ref_21","unstructured":"Scieur, D., Oyallon, E., d\u2019Aspremont, A., and Bach, F. (2018). Online regularized nonlinear acceleration. arXiv."},{"key":"ref_22","unstructured":"Young, D.M. (2014). Iterative Solution of Large Linear Systems, Elsevier."},{"key":"ref_23","unstructured":"Peyr\u00e9, G., Chizat, L., Vialard, F.X., and Solomon, J. (2016). Quantum Optimal Transport for Tensor Field Processing. arXiv."},{"key":"ref_24","unstructured":"Dvurechensky, P., Gasnikov, A., and Kroshnin, A. (2018, January 10\u201315). Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn\u2019s algorithm. Proceedings of the International Conference on Machine Learning, Stockholm, Sweden."},{"key":"ref_25","unstructured":"Lin, T., Ho, N., and Jordan, M. (2019). On the efficiency of the Sinkhorn and Greenkhorn algorithms and their acceleration for optimal transport. arXiv."},{"key":"ref_26","unstructured":"Lin, T., Ho, N., and Jordan, M. (2019, January 10\u201315). On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. Proceedings of the International Conference on Machine Learning, Long Beach, CA, USA."},{"key":"ref_27","unstructured":"Thibault, A., Chizat, L., Dossal, C., and Papadakis, N. (2017). Overrelaxed sinkhorn-knopp algorithm for regularized optimal transport. arXiv."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Lehmann, T., von Renesse, M.K., Sambale, A., and Uschmajew, A. (2020). A note on overrelaxation in the Sinkhorn algorithm. arXiv.","DOI":"10.1007\/s11590-021-01830-0"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"A1111","DOI":"10.1137\/141000439","article-title":"Iterative Bregman projections for regularized transportation problems","volume":"37","author":"Benamou","year":"2015","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","article-title":"The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming","volume":"7","author":"Bregman","year":"1967","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1561\/2200000073","article-title":"Computational optimal transport","volume":"11","author":"Cuturi","year":"2019","journal-title":"Found. Trends Mach. Learn."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2766963","article-title":"Convolutional Wasserstein Distances: Efficient Optimal Transportation on Geometric Domains","volume":"34","author":"Solomon","year":"2015","journal-title":"ACM Trans. Graph."},{"key":"ref_33","first-page":"307","article-title":"IX. The approximate arithmetical solution by finite differences of physical problems involving differential equations, with an application to the stresses in a masonry dam","volume":"210","author":"Richardson","year":"1911","journal-title":"Philos. Trans. R. Soc. Lond. Ser. A Contain. Pap. A Math. Phys. Character"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1080\/10556788.2017.1396601","article-title":"A generic online acceleration scheme for optimization algorithms via relaxation and inertia","volume":"34","author":"Iutzeler","year":"2019","journal-title":"Optim. Methods Softw."},{"key":"ref_35","unstructured":"Schmitzer, B. (2016). Stabilized sparse scaling algorithms for entropy regularized transport problems. arXiv."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1137\/060659624","article-title":"The Sinkhorn\u2013Knopp algorithm: Convergence and applications","volume":"30","author":"Knight","year":"2008","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_37","unstructured":"Ciarlet, P. (1982). Introduction \u00e0 l\u2019Analyse Num\u00e9rique Matricielle et \u00e0 l\u2019Optimisation, Masson."},{"key":"ref_38","unstructured":"Chizat, L. (2017). Unbalanced Optimal Transport: Models, Numerical Methods, Applications. [Ph.D. Thesis, Universit\u00e9 Paris Dauphine]."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0606055","article-title":"On the optimization of the classical iterative schemes for the solution of complex singular linear systems","volume":"6","author":"Hadjidimos","year":"1985","journal-title":"SIAM J. Algebr. Discret. Methods"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/143\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:55:56Z","timestamp":1760162156000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,30]]},"references-count":39,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5]]}},"alternative-id":["a14050143"],"URL":"https:\/\/doi.org\/10.3390\/a14050143","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,30]]}}}