# Sum-of-Squares Programming for Ma-Trudinger-Wang Regularity of Optimal Transport Maps

arXiv: https://arxiv.org/abs/2412.13372 · HTML: https://mlsanity.com/paper/2412.13372/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 98 references that are in the map.
- First posted on arXiv 17 Dec 2024.

## Builds on (most cited first, 29 of 29)

- [Flow Matching for Generative Modeling](https://mlsanity.com/paper/2210.02747/) (2022)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Optimal transport mapping via input convex neural networks](https://mlsanity.com/paper/1908.10962/) (2019)
- [Large-Scale Optimal Transport and Mapping Estimation](https://mlsanity.com/paper/1711.02283/) (2017)
- [On the relation between optimal transport and Schr"odinger bridges: A stochastic control viewpoint](https://mlsanity.com/paper/1412.4430/) (2014)
- [Robust Optimal Transport with Applications in Generative Modeling and Domain Adaptation](https://mlsanity.com/paper/2010.05862/) (2020)
- [Generative Modeling with Optimal Transport Maps](https://mlsanity.com/paper/2110.02999/) (2021)
- [Plugin Estimation of Smooth Optimal Transport Maps](https://mlsanity.com/paper/2107.12364/) (2021)
- [Supervised Training of Conditional Monge Maps](https://mlsanity.com/paper/2206.14262/) (2022)
- [Lower Bounds on Adversarial Robustness from Optimal Transport](https://mlsanity.com/paper/1909.12272/) (2019)
- [A Faster Interior Point Method for Semidefinite Programming](https://mlsanity.com/paper/2009.10217/) (2020)
- [On the Convergence and Robustness of Training GANs with Regularized Optimal Transport](https://mlsanity.com/paper/1802.08249/) (2018)
- [HyperML: A Boosting Metric Learning Approach in Hyperbolic Space for Recommender Systems](https://mlsanity.com/paper/1809.01703/) (2018)
- [From optimal transport to generative modeling: the VEGAN cookbook](https://mlsanity.com/paper/1705.07642/) (2017)
- [Neural Monge Map estimation and its applications](https://mlsanity.com/paper/2106.03812/) (2021)
- [Minimax estimation of discontinuous optimal transport maps: The semi-discrete case](https://mlsanity.com/paper/2301.11302/) (2023)
- [A fast approach to optimal transport: The back-and-forth method](https://mlsanity.com/paper/1905.12154/) (2019)
- [Neural Optimal Transport with Lagrangian Costs](https://mlsanity.com/paper/2406.00288/) (2024)
- [Optimal transport over a linear dynamical system](https://mlsanity.com/paper/1502.01265/) (2015)
- [Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces](https://mlsanity.com/paper/1911.02536/) (2019)
- [A Generative Model for Texture Synthesis based on Optimal Transport between Feature Distributions](https://mlsanity.com/paper/2007.03408/) (2020)
- [Geodesic Sinkhorn for Fast and Accurate Optimal Transport on Manifolds](https://mlsanity.com/paper/2211.00805/) (2022)
- [Aligning Hyperbolic Representations: an Optimal Transport-based approach](https://mlsanity.com/paper/2012.01089/) (2020)
- [SOSOPT: A Toolbox for Polynomial Optimization](https://mlsanity.com/paper/1308.1889/) (2013)
- [Solution of the Probabilistic Lambert Problem: Connections with Optimal Mass Transport, Schr"odinger Bridge and Reaction-Diffusion PDEs](https://mlsanity.com/paper/2401.07961/) (2024)
- [SOSTOOLS Version 4.00 Sum of Squares Optimization Toolbox for MATLAB](https://mlsanity.com/paper/1310.4716/) (2013)
- [Sublevel Set Approximation in The Hausdorff and Volume Metric with Application to Path Planning and Obstacle Avoidance](https://mlsanity.com/paper/2303.06778/) (2023)
- [Simplification Methods for Sum-of-Squares Programs](https://mlsanity.com/paper/1303.0714/) (2013)
- [Functional portfolio optimization in stochastic portfolio theory](https://mlsanity.com/paper/2103.10925/) (2021)

## Abstract (arXiv)

For a given ground cost, approximating the Monge optimal transport map that pushes forward a given probability measure onto another has become a staple in several modern machine learning algorithms. The fourth-order Ma-Trudinger-Wang (MTW) tensor associated with this ground cost function provides a notion of curvature in optimal transport. The non-negativity of this tensor plays a crucial role for establishing continuity for the Monge optimal transport map. It is, however, generally difficult to analytically verify this condition for any given ground cost. To expand the class of cost functions for which MTW non-negativity can be verified, we propose a provably correct computational approach which provides certificates of non-negativity for the MTW tensor using Sum-of-Squares (SOS) programming. We further show that our SOS technique can also be used to compute an inner approximation of the region where MTW non-negativity holds. We apply our proposed SOS programming method to several practical ground cost functions to approximate the regions of regularity of their corresponding optimal transport maps.