Expected Sliced Transport Plans

• URL: http://arxiv.org/abs/2410.12176v2
• Date: Thu, 17 Oct 2024 15:18:31 GMT
• Title: Expected Sliced Transport Plans
• Authors: Xinran Liu, Rocío Díaz Martín, Yikun Bai, Ashkan Shahbazi, Matthew Thorpe, Akram Aldroubi, Soheil Kolouri,
• Abstract summary: We propose a "lifting" operation to extend one-dimensional optimal transport plans back to the original space of the measures. We prove that using the EST plan to weight the sum of the individual Euclidean costs for moving from one point to another results in a valid metric between the input discrete probability measures.
• Score: 9.33181953215826
• License:
• Abstract: The optimal transport (OT) problem has gained significant traction in modern machine learning for its ability to: (1) provide versatile metrics, such as Wasserstein distances and their variants, and (2) determine optimal couplings between probability measures. To reduce the computational complexity of OT solvers, methods like entropic regularization and sliced optimal transport have been proposed. The sliced OT framework improves efficiency by comparing one-dimensional projections (slices) of high-dimensional distributions. However, despite their computational efficiency, sliced-Wasserstein approaches lack a transportation plan between the input measures, limiting their use in scenarios requiring explicit coupling. In this paper, we address two key questions: Can a transportation plan be constructed between two probability measures using the sliced transport framework? If so, can this plan be used to define a metric between the measures? We propose a "lifting" operation to extend one-dimensional optimal transport plans back to the original space of the measures. By computing the expectation of these lifted plans, we derive a new transportation plan, termed expected sliced transport (EST) plans. We prove that using the EST plan to weight the sum of the individual Euclidean costs for moving from one point to another results in a valid metric between the input discrete probability measures. We demonstrate the connection between our approach and the recently proposed min-SWGG, along with illustrative numerical examples that support our theoretical findings.

Related papers

• Scalable Unbalanced Sobolev Transport for Measures on a Graph [23.99177001129992]
  Optimal transport (OT) is a powerful tool for comparing probability measures. OT suffers a few drawbacks: (i) input measures required to have the same mass, (ii) a high computational complexity, and (iii) indefiniteness. Le et al. (2022) recently proposed Sobolev transport for measures on a graph having the same total mass by leveraging the graph structure over supports. We show that the proposed unbalanced Sobolev transport admits a closed-form formula for fast computation, and it is also negative definite.
  arXiv  Detail & Related papers  (2023-02-24T07:35:38Z)
• InfoOT: Information Maximizing Optimal Transport [58.72713603244467]
  InfoOT is an information-theoretic extension of optimal transport. It maximizes the mutual information between domains while minimizing geometric distances. This formulation yields a new projection method that is robust to outliers and generalizes to unseen samples.
  arXiv  Detail & Related papers  (2022-10-06T18:55:41Z)
• Learning Optimal Transport Between two Empirical Distributions with Normalizing Flows [12.91637880428221]
  We propose to leverage the flexibility of neural networks to learn an approximate optimal transport map. We show that a particular instance of invertible neural networks, namely the normalizing flows, can be used to approximate the solution of this OT problem.
  arXiv  Detail & Related papers  (2022-07-04T08:08:47Z)
• 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)
• Approximating Optimal Transport via Low-rank and Sparse Factorization [19.808887459724893]
  Optimal transport (OT) naturally arises in a wide range of machine learning applications but may often become the computational bottleneck. A novel approximation for OT is proposed, in which the transport plan can be decomposed into the sum of a low-rank matrix and a sparse one.
  arXiv  Detail & Related papers  (2021-11-12T03:10:45Z)
• Order Constraints in Optimal Transport [6.677646909984405]
  We introduce novel order constraints into the optimal transport formulation to allow for the incorporation of structure. We derive computationally efficient lower bounds that allow for an explainable approach to adding structure to the optimal transport plan.
  arXiv  Detail & Related papers  (2021-10-14T11:26:23Z)
• Do Neural Optimal Transport Solvers Work? A Continuous Wasserstein-2 Benchmark [133.46066694893318]
  We evaluate the performance of neural network-based solvers for optimal transport. We find that existing solvers do not recover optimal transport maps even though they perform well in downstream tasks.
  arXiv  Detail & Related papers  (2021-06-03T15:59:28Z)
• BoMb-OT: On Batch of Mini-batches Optimal Transport [23.602237930502948]
  Mini-batch optimal transport (m-OT) has been successfully used in practical applications that involve probability measures with intractable density. We propose a novel mini-batching scheme for optimal transport, named Batch of Mini-batches Optimal Transport (BoMb-OT) We show that the new mini-batching scheme can estimate a better transportation plan between two original measures than m-OT.
  arXiv  Detail & Related papers  (2021-02-11T09:56:25Z)
• 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)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
  arXiv  Detail & Related papers  (2020-06-22T14:35:33Z)
• The Importance of Prior Knowledge in Precise Multimodal Prediction [71.74884391209955]
  Roads have well defined geometries, topologies, and traffic rules. In this paper we propose to incorporate structured priors as a loss function. We demonstrate the effectiveness of our approach on real-world self-driving datasets.
  arXiv  Detail & Related papers  (2020-06-04T03:56:11Z)

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.