×
Deligiannidis, George; De Bortoli, Valentin; Doucet, Arnaud

Quantitative uniform stability of the iterative proportional fitting procedure. (English) Zbl 07829148

Ann. Appl. Probab. 34, No. 1A, 501-516 (2024).
Summary: We establish that the iterates of the iterative proportional fitting procedure, also known as Sinkhorn’s algorithm and commonly used to solve entropy-regularised optimal transport problems, are stable w.r.t. perturbations of the marginals, uniformly in time. Our result is quantitative and stated in terms of the 1-Wasserstein metric. As a corollary we establish a quantitative stability result for Schrödinger bridges.

Cited in 1 Document

MSC:

49Q22 Optimal transportation
60-08 Computational methods for problems pertaining to probability theory

Keywords:

entropy regularized optimal transport; Schrödinger bridge; iterative proportional fitting procedure; Sinkhorn algorithm; particle filtering
Cite Review PDF
Full Text: DOI arXiv Link

References:

[1] ALTSCHULER, J., WEED, J. and RIGOLLET, P. (2017). Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. In Advances in Neural Information Processing Systems, 30.
[2] BAUER, F. L. (1965). An elementary proof of the Hopf inequality for positive operators. Numer. Math. 7 331-337. Digital Object Identifier: 10.1007/BF01436527 Google Scholar: Lookup Link MathSciNet: MR0188785 · Zbl 0148.38103 · doi:10.1007/BF01436527
[3] BAYRAKTAR, E., ECKSTEIN, S. and ZHANG, X. (2022). Stability and sample complexity of divergence regularized optimal transport. Preprint. Available at arXiv:2212.00367.
[4] BERNTON, E., GHOSAL, P. and NUTZ, M. (2022). Entropic optimal transport: Geometry and large deviations. Duke Math. J. 171 3363-3400. Digital Object Identifier: 10.1215/00127094-2022-0035 Google Scholar: Lookup Link MathSciNet: MR4505361 · Zbl 1503.49036 · doi:10.1215/00127094-2022-0035
[5] BERNTON, E., HENG, J., DOUCET, A. and JACOB, P. E. (2019). Schrödinger bridge samplers. Preprint. Available at arXiv:1912.13170.
[6] BIRKHOFF, G. (1957). Extensions of Jentzsch’s theorem. Trans. Amer. Math. Soc. 85 219-227. Digital Object Identifier: 10.2307/1992971 Google Scholar: Lookup Link MathSciNet: MR0087058 · Zbl 0079.13502 · doi:10.2307/1992971
[7] CARLIER, G., CHIZAT, L. and LABORDE, M. (2022). Lipschitz continuity of the Schrödinger map in entropic optimal transport. Preprint. Available at arXiv:2210.00225.
[8] CARLIER, G., DUVAL, V., PEYRÉ, G. and SCHMITZER, B. (2017). Convergence of entropic schemes for optimal transport and gradient flows. SIAM J. Math. Anal. 49 1385-1418. Digital Object Identifier: 10.1137/15M1050264 Google Scholar: Lookup Link MathSciNet: MR3635459 · Zbl 1365.90197 · doi:10.1137/15M1050264
[9] CARLIER, G. and LABORDE, M. (2020). A differential approach to the multi-marginal Schrödinger system. SIAM J. Math. Anal. 52 709-717. Digital Object Identifier: 10.1137/19M1253800 Google Scholar: Lookup Link MathSciNet: MR4062805 · Zbl 1436.49058 · doi:10.1137/19M1253800
[10] CHEN, Y., GEORGIOU, T. and PAVON, M. (2016). Entropic and displacement interpolation: A computational approach using the Hilbert metric. SIAM J. Appl. Math. 76 2375-2396. Digital Object Identifier: 10.1137/16M1061382 Google Scholar: Lookup Link MathSciNet: MR3579702 · Zbl 1369.49064 · doi:10.1137/16M1061382
[11] CHEN, Y., GEORGIOU, T. T. and PAVON, M. (2021). Optimal transport in systems and control. Annu. Rev. Control Robot. Auton. Syst. 4 89-113.
[12] CHIARINI, A., CONFORTI, G., GRECO, G. and TAMANINI, L. (2022). Gradient estimates for the Schrödinger potentials: Convergence to the Brenier map and quantitative stability. Preprint. Available at arXiv:2207.14262.
[13] COMINETTI, R. and SAN MARTÍN, J. (1994). Asymptotic analysis of the exponential penalty trajectory in linear programming. Math. Program. 67 169-187. Digital Object Identifier: 10.1007/BF01582220 Google Scholar: Lookup Link MathSciNet: MR1305565 · Zbl 0833.90081 · doi:10.1007/BF01582220
[14] CORENFLOS, A., THORNTON, J., DELIGIANNIDIS, G. and DOUCET, A. (2021). Differentiable particle filtering via entropy-regularized optimal transport. In Proceedings of the 38th International Conference on Machine Learning.
[15] Csiszár, I. (1975). \(I\)-divergence geometry of probability distributions and minimization problems. Ann. Probab. 3 146-158. Digital Object Identifier: 10.1214/aop/1176996454 Google Scholar: Lookup Link MathSciNet: MR0365798 · Zbl 0318.60013 · doi:10.1214/aop/1176996454
[16] CUTURI, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, 26.
[17] DE BORTOLI, V., THORNTON, J., HENG, J. and DOUCET, A. (2021). Diffusion Schrödinger bridge with applications to score-based generative modeling. In Advances in Neural Information Processing Systems, 35.
[18] DELALANDE, A. and MERIGOT, Q. (2021). Quantitative stability of optimal transport maps under variations of the target measure. Preprint. Available at arXiv:2103.05934.
[19] ECKSTEIN, S. and NUTZ, M. (2022). Quantitative stability of regularized optimal transport and convergence of Sinkhorn’s algorithm. SIAM J. Math. Anal. 54 5922-5948. Digital Object Identifier: 10.1137/21M145505X Google Scholar: Lookup Link MathSciNet: MR4506579 · Zbl 1507.90127 · doi:10.1137/21M145505X
[20] Fournier, N. and Guillin, A. (2015). On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Related Fields 162 707-738. Digital Object Identifier: 10.1007/s00440-014-0583-7 Google Scholar: Lookup Link MathSciNet: MR3383341 · Zbl 1325.60042 · doi:10.1007/s00440-014-0583-7
[21] FRANKLIN, J. and LORENZ, J. (1989). On the scaling of multidimensional matrices. Linear Algebra Appl. 114/115 717-735. Digital Object Identifier: 10.1016/0024-3795(89)90490-4 Google Scholar: Lookup Link MathSciNet: MR0986904 · Zbl 0674.15001 · doi:10.1016/0024-3795(89)90490-4
[22] GENEVAY, A., CHIZAT, L., BACH, F., CUTURI, M. and PEYRÉ, G. (2019). Sample complexity of Sinkhorn divergences. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics 1574-1583. PMLR.
[23] GHOSAL, P., NUTZ, M. and BERNTON, E. (2022). Stability of entropic optimal transport and Schrödinger bridges. J. Funct. Anal. 283 Paper No. 109622. Digital Object Identifier: 10.1016/j.jfa.2022.109622 Google Scholar: Lookup Link MathSciNet: MR4460341 · Zbl 1497.90148 · doi:10.1016/j.jfa.2022.109622
[24] Gigli, N. (2011). On Hölder continuity-in-time of the optimal transport map towards measures along a curve. Proc. Edinb. Math. Soc. (2) 54 401-409. Digital Object Identifier: 10.1017/S001309150800117X Google Scholar: Lookup Link MathSciNet: MR2794662 · Zbl 1232.49053 · doi:10.1017/S001309150800117X
[25] HOPF, E. (1963). An inequality for positive linear integral operators. J. Math. Mech. 12 683-692. MathSciNet: MR0165325 · Zbl 0115.32501
[26] HUANG, J., JIAO, Y., KANG, L., LIAO, X., LIU, J. and LIU, Y. (2021). Schrödinger-Föllmer sampler: Sampling without ergodicity. Preprint. Available at arXiv:2106.10880.
[27] KANTOROVITCH, L. (1942). On the transfer of masses (in Russian). C. R. (Dokl.) Acad. Sci. URSS 37 227-229.
[28] LEMMENS, B. and NUSSBAUM, R. (2014). Birkhoff’s version of Hilbert’s metric and its applications in analysis. In Handbook of Hilbert Geometry. IRMA Lect. Math. Theor. Phys. 22 275-303. Eur. Math. Soc., Zürich. MathSciNet: MR3329884
[29] LÉONARD, C. (2012). From the Schrödinger problem to the Monge-Kantorovich problem. J. Funct. Anal. 262 1879-1920. Digital Object Identifier: 10.1016/j.jfa.2011.11.026 Google Scholar: Lookup Link MathSciNet: MR2873864 · Zbl 1236.49088 · doi:10.1016/j.jfa.2011.11.026
[30] Léonard, C. (2014). A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Contin. Dyn. Syst. 34 1533-1574. Digital Object Identifier: 10.3934/dcds.2014.34.1533 Google Scholar: Lookup Link MathSciNet: MR3121631 · Zbl 1277.49052 · doi:10.3934/dcds.2014.34.1533
[31] LI, L., GENEVAY, A., YUROCHKIN, M. and SOLOMON, J. M. (2020). Continuous regularized Wasserstein barycenters. In Advances in Neural Information Processing Systems.
[32] LI, W. and NOCHETTO, R. H. (2021). Quantitative stability and error estimates for optimal transport plans. IMA J. Numer. Anal. 41 1941-1965. Digital Object Identifier: 10.1093/imanum/draa045 Google Scholar: Lookup Link MathSciNet: MR4286252 · Zbl 1510.65122 · doi:10.1093/imanum/draa045
[33] LUISE, G., SALZO, S., PONTIL, M. and CILIBERTO, C. (2019). Sinkhorn barycenters with free support via Frank-Wolfe algorithm. In Advances in Neural Information Processing Systems, 32.
[34] MÉRIGOT, Q., DELALANDE, A. and CHAZAL, F. (2020). Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics 3186-3196. PMLR.
[35] MIKAMI, T. (2004). Monge’s problem with a quadratic cost by the zero-noise limit of \(h\)-path processes. Probab. Theory Related Fields 129 245-260. Digital Object Identifier: 10.1007/s00440-004-0340-4 Google Scholar: Lookup Link MathSciNet: MR2063377 · Zbl 1061.58034 · doi:10.1007/s00440-004-0340-4
[36] Peyré, G. and Cuturi, M. (2019). Computational optimal transport. Found. Trends Mach. Learn. 11 355-607.
[37] RIGOLLET, P. and STROMME, A. J. (2022). On the sample complexity of entropic optimal transport. Preprint. Available at arXiv:2206.13472.
[38] RÜSCHENDORF, L. (1995). Convergence of the iterative proportional fitting procedure. Ann. Statist. 23 1160-1174. Digital Object Identifier: 10.1214/aos/1176324703 Google Scholar: Lookup Link MathSciNet: MR1353500 · Zbl 0851.62038 · doi:10.1214/aos/1176324703
[39] SCHRÖDINGER, E. (1931). Uber die umkehrung der naturgesetze. Akad. Wissen., Berlin Phys. Math 144. · Zbl 0001.37503
[40] VARGAS, F., THODOROFF, P., LAMACRAFT, A. and LAWRENCE, N. (2021). Solving Schrödinger bridges via maximum likelihood. Entropy 23 Paper No. 1134, 30. Digital Object Identifier: 10.3390/e23091134 Google Scholar: Lookup Link MathSciNet: MR4319496 · doi:10.3390/e23091134
[41] Villani, C. (2009). Optimal Transport: Old and New. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 338. Springer, Berlin. Digital Object Identifier: 10.1007/978-3-540-71050-9 Google Scholar: Lookup Link MathSciNet: MR2459454 · Zbl 1156.53003 · doi:10.1007/978-3-540-71050-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.