Convergence proof for the GenCol algorithm in the case of two-marginal optimal transport
HTML articles powered by AMS MathViewer
- by Gero Friesecke and Maximilian Penka
- Math. Comp.
- DOI: https://doi.org/10.1090/mcom/3968
- Published electronically: March 26, 2024
- PDF | Request permission
Abstract:
The recently introduced Genetic Column Generation (GenCol) algorithm has been numerically observed to efficiently and accurately compute high-dimensional optimal transport (OT) plans for general multi-marginal problems, but theoretical results on the algorithm have hitherto been lacking. The algorithm solves the OT linear program on a dynamically updated low-dimensional submanifold consisting of sparse plans. The submanifold dimension exceeds the sparse support of optimal plans only by a fixed factor $\beta$. Here we prove that for $\beta \geq 2$ and in the two-marginal case, GenCol always converges to an exact solution, for arbitrary costs and marginals. The proof relies on the concept of c-cyclical monotonicity. As an offshoot, GenCol rigorously reduces the data complexity of numerically solving two-marginal OT problems from $O(\ell ^2)$ to $O(\ell )$ without any loss in accuracy, where $\ell$ is the number of discretization points for a single marginal. At the end of the paper we also present some insights into the convergence behavior in the multi-marginal case.References
- Jason M. Altschuler and Enric Boix-Adserà, Hardness results for multimarginal optimal transport problems, Discrete Optim. 42 (2021), Paper No. 100669, 21. MR 4316704, DOI 10.1016/j.disopt.2021.100669
- Yann Brenier, Polar factorization and monotone rearrangement of vector-valued functions, Comm. Pure Appl. Math. 44 (1991), no. 4, 375–417. MR 1100809, DOI 10.1002/cpa.3160440402
- Karthekeyan Chandrasekaran, László Végh, and Santosh S. Vempala, The cutting plane method is polynomial for perfect matchings, Math. Oper. Res. 41 (2016), no. 1, 23–48. MR 3465740, DOI 10.1287/moor.2015.0714
- Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva, Maximum flow and minimum-cost flow in almost-linear time, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science—FOCS 2022, IEEE Computer Soc., Los Alamitos, CA, [2022] ©2022, pp. 612–623. MR 4537240
- Y. Dong, Y. Gao, R. Peng, I. Razenshteyn, and S. Sawlani, A study of performance of optimal transport, 2020, arXiv:2005.01182
- Joel Franklin and Jens Lorenz, On the scaling of multidimensional matrices, Linear Algebra Appl. 114/115 (1989), 717–735. MR 986904, DOI 10.1016/0024-3795(89)90490-4
- Gero Friesecke and Maximilian Penka, The GenCol algorithm for high-dimensional optimal transport: general formulation and application to barycenters and Wasserstein splines, SIAM J. Math. Data Sci. 5 (2023), no. 4, 899–919. MR 4659330, DOI 10.1137/22M1524254
- Gero Friesecke, Andreas S. Schulz, and Daniela Vögler, Genetic column generation: fast computation of high-dimensional multimarginal optimal transport problems, SIAM J. Sci. Comput. 44 (2022), no. 3, A1632–A1654. MR 4443671, DOI 10.1137/21M140732X
- Marco E. Lübbecke and Jacques Desrosiers, Selected topics in column generation, Oper. Res. 53 (2005), no. 6, 1007–1023. MR 2193875, DOI 10.1287/opre.1050.0234
- Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
- M. Scetbon, M. Cuturi, and G. Peyré, Low-rank Sinkhorn factorization, International Conference on Machine Learning, PMLR, 2021, pp. 9344–9354.
- Bernhard Schmitzer, Stabilized sparse scaling algorithms for entropy regularized transport problems, SIAM J. Sci. Comput. 41 (2019), no. 3, A1443–A1481. MR 3947294, DOI 10.1137/16M1106018
- Christoph Strössner and Daniel Kressner, Low-rank tensor approximations for solving multimarginal optimal transport problems, SIAM J. Imaging Sci. 16 (2023), no. 1, 169–191. MR 4543427, DOI 10.1137/22M1478355
Bibliographic Information
- Gero Friesecke
- Affiliation: Department of Mathematics, Technical University of Munich, 85748 Garching, Germany
- MR Author ID: 324264
- ORCID: 0000-0003-0066-3966
- Email: gf@ma.tum.de
- Maximilian Penka
- Affiliation: Department of Mathematics, Technical University of Munich, 85748 Garching, Germany
- MR Author ID: 1584751
- ORCID: 0000-0002-2072-2831
- Email: penka@ma.tum.de
- Received by editor(s): September 12, 2023
- Received by editor(s) in revised form: February 5, 2024
- Published electronically: March 26, 2024
- Additional Notes: The second author was partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) through the Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”, Projektnummer 195170736
- © Copyright 2024 American Mathematical Society
- Journal: Math. Comp.
- MSC (2020): Primary 65Kxx, 90C06
- DOI: https://doi.org/10.1090/mcom/3968