Samenvatting
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 TdL, that admit densities with respect to the Haar measure of TdL. 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.
Originele taal-2 | Engels |
---|---|
Titel | 6th Annual Conference on Learning Theory, COLT 2023 |
Uitgeverij | PMLR |
Pagina's | 716-746 |
Aantal pagina's | 31 |
Status | Gepubliceerd - 2023 |
Evenement | 36th Annual Conference on Learning Theory, COLT 2023 - Bangalore, India Duur: 12 jul. 2023 → 15 jul. 2023 |
Publicatie series
Naam | Proceedings of Machine Learning Research (PMLR) |
---|---|
Volume | 195 |
Congres
Congres | 36th Annual Conference on Learning Theory, COLT 2023 |
---|---|
Land/Regio | India |
Stad | Bangalore |
Periode | 12/07/23 → 15/07/23 |
Bibliografische nota
Publisher Copyright:© 2023 G. Greco, M. Noble, G. Conforti & A. Oliviero–Durmus.
Financiering
GG thanks École Polytechnique for its hospitality, where this research has been carried out, and NDNS+ for funding his visit there (NDNS/2023.004 PhD Travel Grant). GG is supported from the NWO Research Project 613.009.111 ”Analysis meets Stochastics: Scaling limits in complex systems”. GC acknowledges funding from the grant SPOT (ANR-20-CE40-0014). AD acknowledges support from the Lagrange Mathematics and Computing Research Center. AD would like to thank the Isaac Newton Institute for Mathematical Sciences for support and hospitality during the programm The mathematical and statistical foundation of future data-driven engineering when work on this paper was undertaken. This work was supported by: EPSRC grant number EP/R014604/1.
Financiers | Financiernummer |
---|---|
SPOT | ANR-20-CE40-0014 |
Engineering and Physical Sciences Research Council | EP/R014604/1 |
Nederlandse Organisatie voor Wetenschappelijk Onderzoek | 613.009.111 |