Improving Approximate Optimal Transport Distances using Quantization

• URL: http://arxiv.org/abs/2102.12731v1
• Date: Thu, 25 Feb 2021 08:45:06 GMT
• Title: Improving Approximate Optimal Transport Distances using Quantization
• Authors: Gaspard Beugnot, Aude Genevay, Kristjan Greenewald, Justin Solomon
• Abstract summary: Optimal transport is a popular tool in machine learning to compare probability measures geometrically. Linear programming algorithms for computing OT scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access.
• Score: 23.319746583489763
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Optimal transport (OT) is a popular tool in machine learning to compare probability measures geometrically, but it comes with substantial computational burden. Linear programming algorithms for computing OT distances scale cubically in the size of the input, making OT impractical in the large-sample regime. We introduce a practical algorithm, which relies on a quantization step, to estimate OT distances between measures given cheap sample access. We also provide a variant of our algorithm to improve the performance of approximate solvers, focusing on those for entropy-regularized transport. We give theoretical guarantees on the benefits of this quantization step and display experiments showing that it behaves well in practice, providing a practical approximation algorithm that can be used as a drop-in replacement for existing OT estimators.

Related papers

• Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently [14.262270388108112]
  We propose a new framework for formulating optimal transport distances between Markov chains. We show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program.
  arXiv  Detail & Related papers  (2024-06-06T13:25:14Z)
• QestOptPOVM: An iterative algorithm to find optimal measurements for quantum parameter estimation [17.305295658536828]
  We introduce an algorithm, termed QestPOVM, designed to directly identify optimal positive operator-Opt measure (POVM) Through rigorous testing on several examples for multiple copies of qubit states (up to six copies), we demonstrate the efficiency and accuracy of our proposed algorithm. Our algorithm functions as a tool for elucidating the explicit forms of optimal POVMs, thereby enhancing our understanding of quantum parameter estimation methodologies.
  arXiv  Detail & Related papers  (2024-03-29T11:46:09Z)
• Efficient Computation of Sparse and Robust Maximum Association Estimators [0.5156484100374059]
  High-dimensional empirical examples underline the usefulness of this procedure. A combination of Lagrangian algorithm and sparse descent is implemented to also include suitable constraints for inducing sparse sparsity.
  arXiv  Detail & Related papers  (2023-11-29T11:57:50Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Entropic Neural Optimal Transport via Diffusion Processes [105.34822201378763]
  We propose a novel neural algorithm for the fundamental problem of computing the entropic optimal transport (EOT) plan between continuous probability distributions. Our algorithm is based on the saddle point reformulation of the dynamic version of EOT which is known as the Schr"odinger Bridge problem. In contrast to the prior methods for large-scale EOT, our algorithm is end-to-end and consists of a single learning step.
  arXiv  Detail & Related papers  (2022-11-02T14:35:13Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  We explore the connection between high-dimensional statistics and non-robust optimization in the presence of sparsity constraints. We develop novel and simple optimization formulations for these problems. As a corollary, we obtain that any first-order method that efficiently converges to station yields an efficient algorithm for these tasks.
  arXiv  Detail & Related papers  (2021-09-23T17:38:24Z)
• Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient Descent [8.714458129632158]
  Kolmogorov model (KM) is an interpretable and predictable representation approach to learning the underlying probabilistic structure of a set of random variables. We propose a computationally scalable KM learning algorithm, based on the regularized dual optimization combined with enhanced gradient descent (GD) method. It is shown that the accuracy of logical relation mining for interpretability by using the proposed KM learning algorithm exceeds $80%$.
  arXiv  Detail & Related papers  (2021-07-11T10:33:02Z)
• Linearized Optimal Transport for Collider Events [0.0]
  We introduce an efficient framework for computing the distance between collider events using the tools of Linearized Optimal Transport (LOT) It also furnishes a Euclidean embedding amenable to simple machine learning algorithms and visualization techniques.
  arXiv  Detail & Related papers  (2020-08-19T18:00:09Z)
• Adaptive Learning of the Optimal Batch Size of SGD [52.50880550357175]
  We propose a method capable of learning the optimal batch size adaptively throughout its iterations for strongly convex and smooth functions. Our method does this provably, and in our experiments with synthetic and real data robustly exhibits nearly optimal behaviour. We generalize our method to several new batch strategies not considered in the literature before, including a sampling suitable for distributed implementations.
  arXiv  Detail & Related papers  (2020-05-03T14:28:32Z)

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.