Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach.

Giacomo Greco, Maxence Noble, Giovanni Conforti, Alain Durmus
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:716-746, 2023.

Abstract

Computational optimal transport (OT) has recently emerged as a powerful framework with applications in various fields. In this paper we focus on a relaxation of the original OT problem, the entropic OT problem, which allows to implement efficient and practical algorithmic solutions, even in high dimensional settings. This formulation, also known as the Schrödinger Bridge problem, notably connects with Stochastic Optimal Control (SOC) and can be solved with the popular Sinkhorn algorithm. In the case of discrete-state spaces, this algorithm is known to have exponential convergence; however, achieving a similar rate of convergence in a more general setting is still an active area of research. In this work, we analyze the convergence of the Sinkhorn algorithm for probability measures defined on the d-dimensional torus T, that admit densities with respect to the Haar measure of T. In particular, we prove pointwise exponential convergence of Sinkhorn iterates and their gradient. Our proof relies on the connection between these iterates and the evolution along the Hamilton-Jacobi-Bellman equations of value functions obtained from SOC-problems. Our approach is novel in that it is purely probabilistic and relies on coupling by reflection techniques for controlled diffusions on the torus.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-greco23a, title = {Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach.}, author = {Greco, Giacomo and Noble, Maxence and Conforti, Giovanni and Durmus, Alain}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {716--746}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/greco23a/greco23a.pdf}, url = {https://proceedings.mlr.press/v195/greco23a.html}, abstract = {Computational optimal transport (OT) has recently emerged as a powerful framework with applications in various fields. In this paper we focus on a relaxation of the original OT problem, the entropic OT problem, which allows to implement efficient and practical algorithmic solutions, even in high dimensional settings. This formulation, also known as the Schrödinger Bridge problem, notably connects with Stochastic Optimal Control (SOC) and can be solved with the popular Sinkhorn algorithm. In the case of discrete-state spaces, this algorithm is known to have exponential convergence; however, achieving a similar rate of convergence in a more general setting is still an active area of research. In this work, we analyze the convergence of the Sinkhorn algorithm for probability measures defined on the d-dimensional torus T, that admit densities with respect to the Haar measure of T. In particular, we prove pointwise exponential convergence of Sinkhorn iterates and their gradient. Our proof relies on the connection between these iterates and the evolution along the Hamilton-Jacobi-Bellman equations of value functions obtained from SOC-problems. Our approach is novel in that it is purely probabilistic and relies on coupling by reflection techniques for controlled diffusions on the torus.} }
Endnote
%0 Conference Paper %T Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach. %A Giacomo Greco %A Maxence Noble %A Giovanni Conforti %A Alain Durmus %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-greco23a %I PMLR %P 716--746 %U https://proceedings.mlr.press/v195/greco23a.html %V 195 %X Computational optimal transport (OT) has recently emerged as a powerful framework with applications in various fields. In this paper we focus on a relaxation of the original OT problem, the entropic OT problem, which allows to implement efficient and practical algorithmic solutions, even in high dimensional settings. This formulation, also known as the Schrödinger Bridge problem, notably connects with Stochastic Optimal Control (SOC) and can be solved with the popular Sinkhorn algorithm. In the case of discrete-state spaces, this algorithm is known to have exponential convergence; however, achieving a similar rate of convergence in a more general setting is still an active area of research. In this work, we analyze the convergence of the Sinkhorn algorithm for probability measures defined on the d-dimensional torus T, that admit densities with respect to the Haar measure of T. In particular, we prove pointwise exponential convergence of Sinkhorn iterates and their gradient. Our proof relies on the connection between these iterates and the evolution along the Hamilton-Jacobi-Bellman equations of value functions obtained from SOC-problems. Our approach is novel in that it is purely probabilistic and relies on coupling by reflection techniques for controlled diffusions on the torus.
APA
Greco, G., Noble, M., Conforti, G. & Durmus, A.. (2023). Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients: a coupling approach.. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:716-746 Available from https://proceedings.mlr.press/v195/greco23a.html.

Related Material