Convergence Rates for Regularized Optimal Transport via Quantization

References

• [1] Adams S, Dirr N, Peletier MA, Zimmer J (2011) From a large-deviations principle to the Wasserstein gradient flow: A new micro-macro passage. Comm. Math. Phys. 307(3):791–815.Crossref, Google Scholar
• [2] Agueh M, Carlier G (2011) Barycenters in the Wasserstein space. SIAM J. Math. Anal. 43(2):904–924.Crossref, Google Scholar
• [3] Alberti G, Ambrosio L (1999) A geometrical approach to monotone functions in Rn. Mathematische Zeitschrift 230(2):259–316.Crossref, Google Scholar
• [4] Altschuler JM, Boix-Adserà E (2023) Polynomial-time algorithms for multimarginal optimal transport problems with structure. Math. Programming 199(1–2):1107–1178.Crossref, Google Scholar
• [5] Altschuler JM, Niles-Weed J, Stromme AJ (2022) Asymptotics for semidiscrete entropic optimal transport. SIAM J. Math. Anal. 54(2):1718–1741.Crossref, Google Scholar
• [6] Benamou J-D, Carlier G, Nenna L (2019) Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm. Numerische Mathematik 142(1):33–54.Crossref, Google Scholar
• [7] Bencheikh O, Jourdain B (2022) Approximation rate in Wasserstein distance of probability measures on the real line by deterministic empirical measures. J. Approx. Theory 274:105684.Crossref, Google Scholar
• [8] Berman RJ (2020) The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations. Numerische Mathematik 145(4):771–836.Crossref, Google Scholar
• [9] Bernton E, Ghosal P, Nutz M (2022) Entropic optimal transport: Geometry and large deviations. Duke Math. J. 171(16):3363–3400.Crossref, Google Scholar
• [10] Blanchet J, Jambulapati A, Kent C, Sidford A (2018) Toward optimal running times for optimal transport. Preprint, submitted October 17, https://arxiv.org/abs/1810.07717v1.Google Scholar
• [11] Blondel M, Seguy V, Rolet A (2018) Smooth and sparse optimal transport. Storkey A, Perez-Cruz F, eds. Internat. Conf. Artificial Intelligence Statist., vol. 84 (PMLR, New York), 880–889.Google Scholar
• [12] Caffarelli LA (1992) The regularity of mappings with a convex potential. J. Amer. Math. Soc. 5(1):99–104.Crossref, Google Scholar
• [13] Caffarelli LA (1996) Boundary regularity of maps with convex potentials. II. Ann. Math. 144(3):453–496.Crossref, Google Scholar
• [14] Carlier G (2022) On the linear convergence of the multi-marginal Sinkhorn algorithm. SIAM J. Optim. 32(2):786–794.Crossref, Google Scholar
• [15] Carlier G, Laborde M (2020) A differential approach to the multi-marginal Schrödinger system. SIAM J. Math. Anal. 52(1):709–717.Crossref, Google Scholar
• [16] Carlier G, Eichinger K, Kroshnin A (2021) Entropic-Wasserstein barycenters: PDE characterization, regularity, and CLT. SIAM J. Math. Anal. 53(5):5880–5914.Crossref, Google Scholar
• [17] Carlier G, Pegon P, Tamanini L (2023) Convergence rate of general entropic optimal transport costs. Calculus Variations Partial Differential Equations, 62(4):116.Crossref, Google Scholar
• [18] Carlier G, Duval V, Peyré G, Schmitzer B (2017) Convergence of entropic schemes for optimal transport and gradient flows. SIAM J. Math. Anal. 49(2):1385–1418.Crossref, Google Scholar
• [19] Chen Y, Georgiou TT, Pavon M (2016) On the relation between optimal transport and Schrödinger bridges: A stochastic control viewpoint. J. Optim. Theory Appl. 169(2):671–691.Crossref, Google Scholar
• [20] Chevallier J (2018) Uniform decomposition of probability measures: Quantization, clustering and rate of convergence. J. Appl. Probab. 55(4):1037–1045.Crossref, Google Scholar
• [21] Chiarini A, Conforti G, Greco G, Tamanini L (2022) Gradient estimates for the Schrödinger potentials: Convergence to the Brenier map and quantitative stability. Preprint, submitted July 28, https://arxiv.org/abs/2207.14262v1.Google Scholar
• [22] Chizat L, Roussillon P, Léger F, Vialard F-X, Peyré G (2020) Faster Wasserstein distance estimation with the Sinkhorn divergence. Adv. Neural Inform. Processing Systems, vol. 33, 2257–2269.Google Scholar
• [23] Cominetti R, San Martín J (1994) Asymptotic analysis of the exponential penalty trajectory in linear programming. Math. Programming 67(2):169–187.Crossref, Google Scholar
• [24] Conforti G, Tamanini L (2021) A formula for the time derivative of the entropic cost and applications. J. Functional Anal. 280(11):108964.Crossref, Google Scholar
• [25] Cuturi M (2013) Sinkhorn distances: Lightspeed computation of optimal transport. Adv. Neural Inform. Processing Systems, vol. 26, 2292–2300.Google Scholar
• [26] Di Marino S, Gerolin A (2020) Optimal transport losses and Sinkhorn algorithm with general convex regularization. Preprint, submitted July 2, https://arxiv.org/abs/2007.00976v1.Google Scholar
• [27] Duong MH, Laschos V, Renger M (2013) Wasserstein gradient flows from large deviations of many-particle limits. ESAIM Control Optim. Calculus Variations 19(4):1166–1188.Crossref, Google Scholar
• [28] Eckstein S, Nutz M (2022) Quantitative stability of regularized optimal transport and convergence of Sinkhorn’s algorithm. SIAM J. Math. Anal. 54(6):5922–5948.Crossref, Google Scholar
• [29] Eckstein S, Pammer G (2022) Computational methods for adapted optimal transport. Preprint, submitted March 9, https://arxiv.org/abs/2203.05005v1.Google Scholar
• [30] Erbar M, Maas J, Renger DRM (2015) From large deviations to Wasserstein gradient flows in multiple dimensions. Electronic Comm. Probab. 20(89):1–12.Google Scholar
• [31] Essid M, Solomon J (2018) Quadratically regularized optimal transport on graphs. SIAM J. Sci. Comput. 40(4):A1961–A1986.Crossref, Google Scholar
• [32] Fournier N (2022) Convergence in expected Wasserstein distance of the empirical measure: Non-asymptotic explicit bounds in Rn. Preprint, submitted September 2, https://arxiv.org/abs/2209.00923v1.Google Scholar
• [33] Fournier N, Guillin A (2015) On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Related Fields 162(3–4):707–738.Crossref, Google Scholar
• [34] Gangbo W, Świȩch A (1998) Optimal maps for the multidimensional Monge-Kantorovich problem. Comm. Pure Appl. Math. 51(1):23–45.Crossref, Google Scholar
• [35] Ghosal P, Nutz M, Bernton E (2022) Stability of entropic optimal transport and Schrödinger bridges. J. Functional Anal. 283(9):109622.Crossref, Google Scholar
• [36] Gigli N, Tamanini L (2021) Second order differentiation formula on RCD* (K, N) spaces. J. Eur. Math. Soc. 23(5):1727–1795.Crossref, Google Scholar
• [37] Graf S, Luschgy H (2000) Foundations of Quantization for Probability Distributions, Lecture Notes in Mathematics, vol. 1730 (Springer, Berlin).Crossref, Google Scholar
• [38] Léonard C (2012) From the Schrödinger problem to the Monge-Kantorovich problem. J. Functional Anal. 262(4):1879–1920.Crossref, Google Scholar
• [39] Léonard C (2014) A survey of the Schrödinger problem and some of its connections with optimal transport. Discrete Continuous Dynamical Systems 34(4):1533–1574.Crossref, Google Scholar
• [40] Lin T, Ho N, Jordan M (2019) On efficient optimal transport: An analysis of greedy and accelerated mirror descent algorithms. Chaudhuri K, Salakhutdinov R, eds. Proc. 36th Internat. Conf. Machine Learn., vol. 97 (PMLR, New York), 3982–3991.Google Scholar
• [41] Loeper G (2009) On the regularity of solutions of optimal transportation problems. Acta Mathematica 202(2):241–283.Crossref, Google Scholar
• [42] Lorenz DA, Manns P, Meyer C (2021) Quadratically regularized optimal transport. Appl. Math. Optim. 83(3):1919–1949.Crossref, Google Scholar
• [43] Ma X-N, Trudinger NS, Wang X-J (2005) Regularity of potential functions of the optimal transportation problem. Arch. Rational Mech. Anal. 177(2):151–183.Crossref, Google Scholar
• [44] Martins Bianco L (2022) Stochastic approximation in optimal transport. M1 Internship Report, Université Paris-Saclay, France.Google Scholar
• [45] McCann RJ, Pass B, Warren M (2012) Rectifiability of optimal transportation plans. Canadian J. Math. 64(4):924–934.Crossref, Google Scholar
• [46] Mikami T (2002) Optimal control for absolutely continuous stochastic processes and the mass transportation problem. Electronic Comm. Probab. 7:199–213.Crossref, Google Scholar
• [47] Mikami T (2004) Monge’s problem with a quadratic cost by the zero-noise limit of h-path processes. Probab. Theory Related Fields 129(2):245–260.Crossref, Google Scholar
• [48] Minty GJ (1962) Monotone (nonlinear) operators in Hilbert space. Duke Math. J. 29(3):341–346.Crossref, Google Scholar
• [49] Nutz M (2021) Introduction to entropic optimal transport. Lecture notes, Columbia University. Accessed August 4, 2022, https://www.math.columbia.edu/mnutz/docs/EOT_lecture_notes.pdf.Google Scholar
• [50] Nutz M, Wiesel J (2022) Entropic optimal transport: Convergence of potentials. Probab. Theory Related Fields 184(1–2):401–424.Crossref, Google Scholar
• [51] Nutz M, Wiesel J (2023) Stability of Schrödinger potentials and convergence of Sinkhorn’s algorithm. Ann. Probab. 51(2):699–722.Crossref, Google Scholar
• [52] Pagès G (2018) Numerical Probability (Springer, Cham, Switzerland).Crossref, Google Scholar
• [53] Pal S (2019) On the difference between entropic cost and the optimal transport cost. Preprint, submitted May 29, https://arxiv.org/abs/1905.12206v1.Google Scholar
• [54] Pass B (2015) Multi-marginal optimal transport: Theory and applications. ESAIM Math. Model. Numerical Anal. 49(6):1771–1790.Crossref, Google Scholar
• [55] Peyré G, Cuturi M (2019) Computational Optimal Transport: With Applications to Data Science, Foundations and Trends in Machine Learning, vol. 11.Google Scholar
• [56] Pooladian A-A, Niles-Weed J (2021) Entropic estimation of optimal transport maps. Preprint, submitted September 24, https://arxiv.org/abs/2109.12004v1.Google Scholar
• [57] Royden HL (1968) Real Analysis, 2nd ed. (Macmillan, New York).Google Scholar
• [58] Terjék D, González-Sánchez D (2022) Optimal transport with f-divergence regularization and generalized Sinkhorn algorithm. Camps-Valls G, Ruiz FJR, Valera I, eds. Internat. Conf. Artificial Intelligence Statist., vol. 151 (PMLR, New York), 5135–5165.Google Scholar
• [59] Villani C (2009) Optimal Transport, Old and New, Grundlehren der Mathematischen Wissenschaften, vol. 338 (Springer-Verlag, Berlin).Google Scholar
• [60] Weed J (2018) An explicit analysis of the entropic penalty in linear programming. Bubeck S, Perchet V, Rigollet P, eds. Conf. Learn. Theory, vol. 75 (PMLR, New York), 1841–1855.Google Scholar
• [61] Weed J, Bach F (2019) Sharp asymptotic and finite-sample rates of convergence of empirical measures in Wasserstein distance. Bernoulli 25(4A):2620–2648.Crossref, Google Scholar
• [62] Xu C, Berger A (2019) Best finite constrained approximations of one-dimensional probabilities. J. Approximation Theory 244:1–36.Crossref, Google Scholar