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

• URL: http://arxiv.org/abs/2412.13372v1
• Date: Tue, 17 Dec 2024 23:10:03 GMT
• Title: Sum-of-Squares Programming for Ma-Trudinger-Wang Regularity of Optimal Transport Maps
• Authors: Sachin Shivakumar, Georgiy A. Bondar, Gabriel Khan, Abhishek Halder,
• Abstract summary: We propose a provably correct computational approach which provides certificates of non-negativity for the MTW tensor. We 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.
• Score: 0.40498500266986387
• License:
• Abstract: 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.

Related papers

• Differentiable Cost-Parameterized Monge Map Estimators [19.015367254988448]
  It is desirable to use known information to tailor cost functions and hence learn OT maps which are adapted to the problem at hand. We construct a differentiable Monge map estimator which can be optimized to be consistent with known information about an OT map. Our method provides a general approach for incorporating prior information about the Monge map itself when learning adapted OT maps and cost functions.
  arXiv  Detail & Related papers  (2024-06-12T16:47:54Z)
• Conditional Optimal Transport on Function Spaces [53.9025059364831]
  We develop a theory of constrained optimal transport problems that describe block-triangular Monge maps. This generalizes the theory of optimal triangular transport to separable infinite-dimensional function spaces with general cost functions. We present numerical experiments that demonstrate the computational applicability of our theoretical results for amortized and likelihood-free inference of functional parameters.
  arXiv  Detail & Related papers  (2023-11-09T18:44:42Z)
• Normalizing flows as approximations of optimal transport maps via linear-control neural ODEs [49.1574468325115]
  We consider the problem of recovering the $Wimat$-optimal transport map T between absolutely continuous measures $mu,nuinmathcalP(mathbbRn)$ as the flow of a linear-control neural ODE.
  arXiv  Detail & Related papers  (2023-11-02T17:17:03Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• Minimax estimation of discontinuous optimal transport maps: The semi-discrete case [14.333765302506658]
  We consider the problem of estimating the optimal transport map between two probability distributions, $P$ and $Q$ in $mathbb Rd$. We show that an estimator based on entropic optimal transport converges at the minimax-optimal rate $n-1/2$, independent of dimension.
  arXiv  Detail & Related papers  (2023-01-26T18:41:38Z)
• Neural Optimal Transport with General Cost Functionals [66.41953045707172]
  We introduce a novel neural network-based algorithm to compute optimal transport plans for general cost functionals. As an application, we construct a cost functional to map data distributions while preserving the class-wise structure.
  arXiv  Detail & Related papers  (2022-05-30T20:00:19Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Scalable Computation of Monge Maps with General Costs [12.273462158073302]
  Monge map refers to the optimal transport map between two probability distributions. We present a scalable algorithm for computing the Monge map between two probability distributions.
  arXiv  Detail & Related papers  (2021-06-07T17:23:24Z)
• Comparing Probability Distributions with Conditional Transport [63.11403041984197]
  We propose conditional transport (CT) as a new divergence and approximate it with the amortized CT (ACT) cost. ACT amortizes the computation of its conditional transport plans and comes with unbiased sample gradients that are straightforward to compute. On a wide variety of benchmark datasets generative modeling, substituting the default statistical distance of an existing generative adversarial network with ACT is shown to consistently improve the performance.
  arXiv  Detail & Related papers  (2020-12-28T05:14:22Z)
• Statistical Optimal Transport posed as Learning Kernel Embedding [0.0]
  This work takes the novel approach of posing statistical Optimal Transport (OT) as that of learning the transport plan's kernel mean embedding from sample based estimates of marginal embeddings. A key result is that, under very mild conditions, $epsilon$-optimal recovery of the transport plan as well as the Barycentric-projection based transport map is possible with a sample complexity that is completely dimension-free.
  arXiv  Detail & Related papers  (2020-02-08T14:58:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.