Computational methods for adapted optimal transport. (English) Zbl 1543.49038

Eckstein, Stephan; Pammer, Gudmund

Ann. Appl. Probab. 34, No. 1A, 675-713 (2024).

Summary: Adapted optimal transport (AOT) problems are optimal transport problems for distributions of a time series where couplings are constrained to have a temporal causal structure. In this paper, we develop computational tools for solving AOT problems numerically. First, we show that AOT problems are stable with respect to perturbations in the marginals, and thus arbitrary AOT problems can be approximated by sequences of linear programs. We further study entropic methods to solve AOT problems. We show that any entropically regularized AOT problem converges to the corresponding unregularized problem if the regularization parameter goes to zero. The proof is based on a novel method – even in the nonadapted case – to easily obtain smooth approximations of a given coupling with fixed marginals. Finally, we show tractability of the adapted version of Sinkhorn’s algorithm. We give explicit solutions for the occurring projections and prove that the procedure converges to the optimizer of the entropic AOT problem.

MSC:

49Q22	Optimal transportation
90C15	Stochastic programming

Keywords:

adapted optimal transport; causal optimal transport; entropic regularization; Sinkhorn’s algorithm; stability; regularization; algorithm

Software:

Gurobi; Wasserstein GAN; POT

References:

[1]	ACCIAIO, B., BACKHOFF VERAGUAS, J. and JIA, J. (2021). Cournot-Nash equilibrium and optimal transport in a dynamic setting. SIAM J. Control Optim. 59 2273-2300. Digital Object Identifier: 10.1137/20M1321462 Google Scholar: Lookup Link MathSciNet: MR4274834 · Zbl 1470.91029 · doi:10.1137/20M1321462
[2]	ADAMS, D. R. and HEDBERG, L. I. (1996). Function Spaces and Potential Theory. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] 314. Springer, Berlin. Digital Object Identifier: 10.1007/978-3-662-03282-4 Google Scholar: Lookup Link MathSciNet: MR1411441 · doi:10.1007/978-3-662-03282-4
[3]	BACKHOFF, J., BARTL, D., BEIGLBÖCK, M. and WIESEL, J. (2022). Estimating processes in adapted Wasserstein distance. Ann. Appl. Probab. 32 529-550. Digital Object Identifier: 10.1214/21-aap1687 Google Scholar: Lookup Link MathSciNet: MR4386535 · Zbl 1492.60104 · doi:10.1214/21-aap1687
[4]	BACKHOFF, J., BEIGLBÖCK, M., LIN, Y. and ZALASHKO, A. (2017). Causal transport in discrete time and applications. SIAM J. Optim. 27 2528-2562. Digital Object Identifier: 10.1137/16M1080197 Google Scholar: Lookup Link MathSciNet: MR3738324 · Zbl 1387.90168 · doi:10.1137/16M1080197
[5]	BACKHOFF-VERAGUAS, J., BARTL, D., BEIGLBÖCK, M. and EDER, M. (2020). Adapted Wasserstein distances and stability in mathematical finance. Finance Stoch. 24 601-632. Digital Object Identifier: 10.1007/s00780-020-00426-3 Google Scholar: Lookup Link MathSciNet: MR4118990 · Zbl 1440.91036 · doi:10.1007/s00780-020-00426-3
[6]	BACKHOFF-VERAGUAS, J., BARTL, D., BEIGLBÖCK, M. and EDER, M. (2020). All adapted topologies are equal. Probab. Theory Related Fields 178 1125-1172. Digital Object Identifier: 10.1007/s00440-020-00993-8 Google Scholar: Lookup Link MathSciNet: MR4168395 · Zbl 1476.60079 · doi:10.1007/s00440-020-00993-8
[7]	BACKHOFF-VERAGUAS, J. and PAMMER, G. (2022). Stability of martingale optimal transport and weak optimal transport. Ann. Appl. Probab. 32 721-752. Digital Object Identifier: 10.1214/21-aap1694 Google Scholar: Lookup Link MathSciNet: MR4386541 · Zbl 1492.60105 · doi:10.1214/21-aap1694
[8]	BACKHOFF-VERAGUAS, J. and ZHANG, X. (2023). Dynamic Cournot-Nash equilibrium: The non-potential case. Math. Financ. Econ. 17 153-174. Digital Object Identifier: 10.1007/s11579-022-00327-3 Google Scholar: Lookup Link MathSciNet: MR4596034 · Zbl 1518.91013 · doi:10.1007/s11579-022-00327-3
[9]	BARTL, D., BEIGLBÖCK, M. and PAMMER, G. (2021). The Wasserstein space of stochastic processes. Preprint. Available at arXiv:2104.14245.
[10]	BARTL, D. and WIESEL, J. (2023). Sensitivity of multiperiod optimization problems with respect to the adapted Wasserstein distance. SIAM J. Financial Math. 14 704-720. Digital Object Identifier: 10.1137/22M1537746 Google Scholar: Lookup Link MathSciNet: MR4599319 · Zbl 1520.91364 · doi:10.1137/22M1537746
[11]	BEIGLBÖCK, M. and LACKER, D. (2018). Denseness of adapted processes among causal couplings. Preprint. Available at arXiv:1805.03185.
[12]	BEIGLBÖCK, M., PAMMER, G. and SCHROTT, S. (2022). Denseness of biadapted Monge mappings. Digital Object Identifier: 10.48550/ARXIV.2210.15554 Google Scholar: Lookup Link · doi:10.48550/ARXIV.2210.15554
[13]	BINDINI, U. (2020). Smoothing operators in multi-marginal optimal transport. Math. Phys. Anal. Geom. 23 Paper No. 21, 27. Digital Object Identifier: 10.1007/s11040-020-09349-z Google Scholar: Lookup Link MathSciNet: MR4107950 · Zbl 1445.60008 · doi:10.1007/s11040-020-09349-z
[14]	BOLLEY, F. and VILLANI, C. (2005). Weighted Csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities. Ann. Fac. Sci. Toulouse Math. (6) 14 331-352. MathSciNet: MR2172583 · Zbl 1087.60008
[15]	BRÜCKERHOFF, M. and JUILLET, N. (2022). Instability of martingale optimal transport in dimension \(\mathit{d} \geq 2\). Electron. Commun. Probab. 27 Paper No. 24, 10. Digital Object Identifier: 10.1134/s1560354722010051 Google Scholar: Lookup Link MathSciNet: MR4416823 · Zbl 1492.60108 · doi:10.1134/s1560354722010051
[16]	CARLIER, G. (2022). On the linear convergence of the multimarginal Sinkhorn algorithm. SIAM J. Optim. 32 786-794. Digital Object Identifier: 10.1137/21M1410634 Google Scholar: Lookup Link MathSciNet: MR4418040 · Zbl 1505.49037 · doi:10.1137/21M1410634
[17]	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
[18]	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
[19]	CUTURI, M. (2013). Sinkhorn distances: Lightspeed computation of optimal transport. Adv. Neural Inf. Process. Syst. 26 2292-2300.
[20]	CUTURI, M. and DOUCET, A. (2014). Fast computation of Wasserstein barycenters. In International Conference on Machine Learning 685-693. PMLR.
[21]	DUPUIS, P. and ELLIS, R. S. (1997). A Weak Convergence Approach to the Theory of Large Deviations. Wiley Series in Probability and Statistics: Probability and Statistics. Wiley, New York. Digital Object Identifier: 10.1002/9781118165904 Google Scholar: Lookup Link MathSciNet: MR1431744 · Zbl 0904.60001 · doi:10.1002/9781118165904
[22]	ECKSTEIN, S., KUPPER, M. and POHL, M. (2020). Robust risk aggregation with neural networks. Math. Finance 30 1229-1272. Digital Object Identifier: 10.1111/mafi.12280 Google Scholar: Lookup Link MathSciNet: MR4154769 · Zbl 1508.91619 · doi:10.1111/mafi.12280
[23]	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
[24]	Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes: Characterization and Convergence. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Wiley, New York. Digital Object Identifier: 10.1002/9780470316658 Google Scholar: Lookup Link MathSciNet: MR0838085 MathSciNet: MR138128 · Zbl 0592.60049 · doi:10.1002/9780470316658
[25]	FLAMARY, R., COURTY, N., GRAMFORT, A., ALAYA, M. Z., BOISBUNON, A., CHAMBON, S., CHAPEL, L., CORENFLOS, A., FATRAS, K. et al. (2021). POT: Python optimal transport. J. Mach. Learn. Res. 22 1-8.
[26]	Folland, G. B. (1999). Real Analysis: Modern Techniques and Their Applications, 2nd ed. Pure and Applied Mathematics (New York). Wiley, New York. MathSciNet: MR1681462 · Zbl 0924.28001
[27]	GULRAJANI, I., AHMED, F., ARJOVSKY, M., DUMOULIN, V. and COURVILLE, A. C. (2017). Improved training of Wasserstein gans. Adv. Neural Inf. Process. Syst. 30.
[28]	GUO, G. and OBŁÓJ, J. (2019). Computational methods for martingale optimal transport problems. Ann. Appl. Probab. 29 3311-3347. Digital Object Identifier: 10.1214/19-AAP1481 Google Scholar: Lookup Link MathSciNet: MR4047982 · Zbl 1433.49043 · doi:10.1214/19-AAP1481
[29]	GUROBI OPTIMIZATION, L. L. C. (2022). Gurobi Optimizer Reference Manual.
[30]	Kallenberg, O. (1997). Foundations of Modern Probability. Probability and Its Applications (New York). Springer, New York. MathSciNet: MR1464694 · Zbl 0892.60001
[31]	Kechris, A. S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer, New York. Digital Object Identifier: 10.1007/978-1-4612-4190-4 Google Scholar: Lookup Link MathSciNet: MR1321597 · Zbl 0819.04002 · doi:10.1007/978-1-4612-4190-4
[32]	KERIVEN, N. (2022). Entropic Optimal Transport in Random Graphs. Preprint. Available at arXiv:2201.03949.
[33]	KOMLÓS, J. (1967). A generalization of a problem of Steinhaus. Acta Math. Acad. Sci. Hung. 18 217-229. Digital Object Identifier: 10.1007/BF02020976 Google Scholar: Lookup Link MathSciNet: MR0210177 · Zbl 0228.60012 · doi:10.1007/BF02020976
[34]	LASSALLE, R. (2018). Causal transport plans and their Monge-Kantorovich problems. Stoch. Anal. Appl. 36 452-484. Digital Object Identifier: 10.1080/07362994.2017.1422747 Google Scholar: Lookup Link MathSciNet: MR3784142 · Zbl 1385.93087 · doi:10.1080/07362994.2017.1422747
[35]	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
[36]	Massart, P. (2007). Concentration Inequalities and Model Selection. Lecture Notes in Math. 1896. Springer, Berlin. MathSciNet: MR2319879 · Zbl 1170.60006
[37]	PEYRÉ, G. and CUTURI, M. (2019). Computational optimal transport: With applications to data science. Found. Trends Mach. Learn. 11 355-607.
[38]	PFLUG, G. CH. (2009). Version-independence and nested distributions in multistage stochastic optimization. SIAM J. Optim. 20 1406-1420. Digital Object Identifier: 10.1137/080718401 Google Scholar: Lookup Link MathSciNet: MR2587733 · Zbl 1198.90307 · doi:10.1137/080718401
[39]	PFLUG, G. CH. and PICHLER, A. (2012). A distance for multistage stochastic optimization models. SIAM J. Optim. 22 1-23. Digital Object Identifier: 10.1137/110825054 Google Scholar: Lookup Link MathSciNet: MR2902682 · Zbl 1262.90118 · doi:10.1137/110825054
[40]	PICHLER, A. and WEINHARDT, M. (2022). The nested Sinkhorn divergence to learn the nested distance. Comput. Manag. Sci. 19 269-293. Digital Object Identifier: 10.1007/s10287-021-00415-7 Google Scholar: Lookup Link MathSciNet: MR4423922 · Zbl 07557211 · doi:10.1007/s10287-021-00415-7
[41]	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
[42]	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
[43]	WIESEL, J. (2019). Continuity of the martingale optimal transport problem on the real line. Preprint. Available at arXiv:1905.04574.
[44]	NUTZ, M. (2021). Introduction to Entropic Optimal Transport.
[45]	XU, T. and ACCIAIO, B. (2021). Quantized Conditional COT-GAN for Video Prediction. Preprint. Available at arXiv:2106.05658.
[46]	XU, T., WENLIANG, L. K., MUNN, M. and ACCIAIO, B. (2020). Cot-gan: Generating sequential data via causal optimal transport. Adv. Neural Inf. Process. Syst. 33 8798-8809.