Paper uses Sinkhorn distances to improve imitation learning effectiveness.
problem Improving imitation learning algorithms by comparing occupancy measures.
method Formulates imitation learning as Sinkhorn distance minimization, combining optimal transport and cosine distances.
result Proposes a new critic network and transport plan that guide imitation learning.
Optimizes distributions robustly with Sinkhorn distance.
problem Distributionally robust optimization with Wasserstein distance.
method Convex programming dual reformulation, stochastic mirror descent algorithm.
result Demonstrates superior performance in synthetic and real data.
The Sinkhorn "distance", a variant of the Wasserstein distance with entropic regularization, is an increasingly popular tool in machine learning and statistical inference. However, the time and memory requirements of standard algorithms for computing this distance grow quadratically with the size of the data, making th…
Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in …
Study convergence and approximations of entropic regularized Wasserstein distances for Gaussian and RKHS measures.
problem Convergence and approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings.
method Analysis of convergence and finite sample approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings.
result Strictly weaker convergence in 2-Sinkhorn divergence for Gaussian measures compared to exact 2-Wasserstein distance.
Paper proves generalized Talagrand inequality for Sinkhorn distance.
problem Proving a generalized Talagrand inequality for Sinkhorn distance.
method Using entropy power inequality and infinitesimal displacement convexity of optimal transport map.
result Extends previous results of Gaussian Talagrand inequality for Sinkhorn distance to strongly log-concave case.
Correctly estimating the discrepancy between two data distributions has always been an important task in Machine Learning. Recently, Cuturi proposed the Sinkhorn distance which makes use of an approximate Optimal Transport cost between two distributions as a distance to describe distribution discrepancy. Although it ha…
Paper proposes a robust hypothesis testing method using Sinkhorn distance.
problem Hypothesis testing for small samples.
method Data-driven approach using Sinkhorn uncertainty sets.
result The method provides a more flexible detector compared to Wasserstein robust test.
New online method estimates OT distances from sample streams.
problem Computing OT distances between arbitrary distributions.
method Online Sinkhorn algorithm using iterative enrichment of non-parametric representation.
result Consistent estimation of true regularized OT distance with nearly-O(1/n) sample complexity.
New stability theory for Sinkhorn semigroups with explicit decay rates.
problem Stability and convergence of Sinkhorn iterations for various divergences.
method Operator-theoretic framework based on Lyapunov techniques.
result Explicit exponential decay rates for Sinkhorn iterates.
A new method for faster estimation of Wasserstein distance using Sinkhorn divergence.
problem Estimating the squared Wasserstein distance between probability distributions.
method Proposes a new estimator based on the Sinkhorn divergence with debiasing terms, and analyzes its sample complexity and computational efficiency.
result The proposed estimator allows higher regularization levels, leading to improved computational complexity and speedup in practice.
Improved online Sinkhorn algorithm for large-scale data processing.
problem Efficiency of Sinkhorn algorithm for large-scale data streams.
method Revisit and improve convergence analysis of online Sinkhorn algorithm, introduce compressed online Sinkhorn algorithm.
result New faster convergence rate for online Sinkhorn algorithm under certain conditions.
SNS accelerates Sinkhorn algorithm with sparse Newton iterations.
problem Slow runtime of Sinkhorn algorithm for optimal transport.
method Early stopping and Newton-type subroutine for matrix scaling steps.
result SNS converges orders of magnitude faster than Sinkhorn.
The Sinkhorn flow converges to a Wasserstein mirror gradient flow from the Sinkhorn algorithm.
problem Optimizing joint distributions using the Sinkhorn algorithm.
method Wasserstein mirror gradient flow derived from the Sinkhorn algorithm.
result The Sinkhorn flow converges to a Wasserstein mirror gradient flow.
This paper tackles Sinkhorn DRO by reformulating it as a bilevel program and proposes sampling-based algorithms.
problem Distributionally robust optimization with ambiguity sets defined via the Sinkhorn discrepancy.
method Primal perspective reformulation as a bilevel program, double-loop and single-loop sampling-based algorithms.
result Simultaneously obtain the optimal robust decision and the worst-case distribution.
Applications of optimal transport have recently gained remarkable attention thanks to the computational advantages of entropic regularization. However, in most situations the Sinkhorn approximation of the Wasserstein distance is replaced by a regularized version that is less accurate but easy to differentiate. In this …
We introduce in this paper a novel strategy for efficiently approximating the Sinkhorn distance between two discrete measures. After identifying neglectable components of the dual solution of the regularized Sinkhorn problem, we propose to screen those components by directly setting them at that value before entering t…
This work studies Gaussian geometry under entropy-regularized 2-Wasserstein distance.
problem Understanding Gaussian distributions in uncertainty quantification and diffusivity.
method Entropy-regularized 2-Wasserstein distance, closed-form solutions, fixed-point characterization.
result Closed-form expressions for the 2-Sinkhorn divergence and fixed-point barycenter.
This study approximates distances between Gaussian processes and covariance operators using RKHS.
problem Approximating distances between Gaussian processes and covariance operators from finite samples.
method Using reproducing kernel Hilbert space (RKHS) covariance and cross-covariance operators, the study shows how to consistently and efficiently estimate Sinkhorn divergence from finite samples.
result Convergence rates are dimension-independent and of the same order as Hilbert-Schmidt distance.
Optimal transportation distances are a fundamental family of parameterized distances for histograms. Despite their appealing theoretical properties, excellent performance in retrieval tasks and intuitive formulation, their computation involves the resolution of a linear program whose cost is prohibitive whenever the hi…
New methods improve stability of Sinkhorn algorithm in machine learning.
problem Stability of Sinkhorn semigroups in high-dimensional settings.
method Semigroup analysis based on contraction coefficients and Lyapunov-type operator-theoretic techniques.
result Unified and simplified arguments in Sinkhorn algorithm stability.
Optimal transport induces the Earth Mover's (Wasserstein) distance between probability distributions, a geometric divergence that is relevant to a wide range of problems. Over the last decade, two relaxations of optimal transport have been studied in depth: unbalanced transport, which is robust to the presence of outli…
Paper tackles robust model training with a new stochastic algorithm.
problem Training robust models against data distribution shift.
method Derives a novel dual formulation and proposes a nested stochastic gradient descent algorithm.
result Establishes polynomial iteration and sample complexities for large-scale DRO problems.
New stability bounds for Sinkhorn's algorithm in entropic optimal transport.
problem Stability and convergence of Sinkhorn's algorithm for entropic optimal transport.
method Semiconcavity approach to analyze stability and convergence.
result Exponential convergence of Sinkhorn's algorithm under semiconcavity conditions.
Study entropic regularization of Gaussian measures and processes on Hilbert space.
problem Regularizing 2-Wasserstein distance for infinite-dimensional Gaussian measures and processes.
method Minimum Mutual Information property, closed form formulas, Fréchet differentiability, Sinkhorn barycenter equation.
result Entropic 2-Wasserstein distance and Sinkhorn divergence are Fréchet differentiable in Hilbert space.
New framework for efficient optimal transport distances between Markov chains.
problem Efficient computation of optimal transport distances between Markov chains.
method Developed a new perspective on optimal transport distances using discounted occupancy couplings and linear programming.
result Introduced Sinkhorn Value Iteration (SVI) for efficient calculation of optimal transport distances.
Paper proposes SinkhornDRL for distributional RL using Sinkhorn divergence and regularized Wasserstein loss.
problem Improving distributional reinforcement learning by minimizing Bellman return distribution differences.
method Introduces SinkhornDRL, a distributional RL algorithm using Sinkhorn divergence and regularized Wasserstein loss.
result SinkhornDRL consistently outperforms or matches existing algorithms on Atari games, especially in multi-dimensional reward settings.
Wasserstein distance plays increasingly important roles in machine learning, stochastic programming and image processing. Major efforts have been under way to address its high computational complexity, some leading to approximate or regularized variations such as Sinkhorn distance. However, as we will demonstrate, regu…
Optimal transport offers an alternative to maximum likelihood for learning generative autoencoding models. We show that minimizing the p-Wasserstein distance between the generator and the true data distribution is equivalent to the unconstrained min-min optimization of the p-Wasserstein distance between the encoder agg…
Introduces new Wasserstein distances for more intrinsic metrics.
problem Improve metric for comparing distributions.
method Introduces RWp distances, designs algorithms for computation. result New distances are more intrinsic and computable.
Debiased Wasserstein barycenters improve on entropy regularization in OT.
problem Entropy regularization in OT introduces bias, leading to blurred barycenters.
method Propose debiased Wasserstein barycenters using Sinkhorn iterations.
result Debiased barycenters preserve fast Sinkhorn-like iterations without entropy smoothing bias.
LOT Wassmap speeds up Wasserstein space manifold learning.
problem Finding low-dimensional structures in Wasserstein space datasets.
method Linearized optimal transport and approximation schemes.
result LOT Wassmap provides accurate embeddings with computational efficiency.
The paper studies how different entropic regularizations affect GAN solutions.
problem Improving numerical convergence and sparsity in GAN solutions.
method Entropic regularization of Wasserstein distance and Sinkhorn divergence.
result Entropy regularization promotes sparsity, while Sinkhorn divergence recovers unregularized solution.
SinSim improves self-supervised learning by integrating optimal transport into contrastive learning.
problem Lack of explicit regularization in contrastive learning methods leads to suboptimal generalization.
method Integrates Sinkhorn regularization from optimal transport theory into SimCLR.
result SinSim outperforms SimCLR and other self-supervised methods on various datasets.
This paper speeds up WMD computation for multiple queries efficiently.
problem Efficiently computing the semantic dissimilarity between text documents.
method Adapting the Sinkhorn-Knopp algorithm to compute WMD of one document against many targets in parallel.
result 67x speedup on 96 cores compared to sequential and naive parallel methods.
In this report, we review the calculation of entropy-regularised Wasserstein loss introduced by Cuturi and document a practical implementation in PyTorch. Code is available at https://github.com/t-vi/pytorch-tvmisc/blob/master/wasserstein-distance/Pytorch_Wasserstein.ipynb
A rapidly growing area of work has studied the existence of adversarial examples, datapoints which have been perturbed to fool a classifier, but the vast majority of these works have focused primarily on threat models defined by ℓp norm-bounded perturbations. In this paper, we propose a new threat model for adver…
We study the complexity of approximating the multimarginal optimal transport (MOT) distance, a generalization of the classical optimal transport distance, considered here between m discrete probability distributions supported each on n support points. First, we show that the standard linear programming (LP) represe…
COT-GAN generates sequential data with a causal optimal transport approach.
problem Generating sequential data with temporal causality constraints.
method Adversarial training with Causal Optimal Transport (COT) and entropic penalization.
result COT-GAN effectively learns time-dependent data distributions and generates stable time series data.
Wasserstein Discriminant Analysis (WDA) is a new supervised method that can improve classification of high-dimensional data by computing a suitable linear map onto a lower dimensional subspace. Following the blueprint of classical Linear Discriminant Analysis (LDA), WDA selects the projection matrix that maximizes the …
We define a novel class of distances between statistical multivariate distributions by modeling an optimal transport problem on their marginals with respect to a ground distance defined on their conditionals. These new distances are metrics whenever the ground distance between the marginals is a metric, generalize both…
Continuous-time Sinkhorn flow generalizes and unifies existing dynamics.
problem Entropy-regularized optimal transport problems.
method Continuous-time mirror descent framework.
result Unified perspective on various dynamics in ML and math.
The Sinkhorn-Knopp derivatives converge with linear rate.
problem Optimal transport problem with entropic regularization.
method Iterative proportional fitting procedure.
result Derivatives converge with linear rate.
As a fundamental problem of natural language processing, it is important to measure the distance between different documents. Among the existing methods, the Word Mover's Distance (WMD) has shown remarkable success in document semantic matching for its clear physical insight as a parameter-free model. However, WMD is e…
Paper solves barycenter of probability distributions using Sinkhorn divergence.
problem Computing the barycenter of a set of probability distributions under the Sinkhorn divergence.
method Recast as unconstrained functional optimization and develop Sinkhorn Descent (SD) method.
result SD converges to a stationary point at a sublinear rate and asymptotically finds a global minimizer.
Improved Sinkhorn algorithm for UOT with near-linear complexity.
problem Solving the entropic regularized Unbalanced Optimal Transport problem efficiently.
method Geometric convergence analysis of Sinkhorn updates and primal solution properties.
result Near-linear time complexity for finding ε-approximate UOT solutions. Survey of Sinkhorn algorithm for optimal transport, emphasizing its geometric origins.
problem Solving optimal transport problems efficiently and accurately.
method Discretization of a non-linear integral equation.
result Geometric interpretation and discretization of the Sinkhorn algorithm.
This work studies the statistical performance of Sinkhorn iterations in estimating Schrödinger bridges.
problem Estimating Schrödinger bridges with limited samples.
method Intermediate Sinkhorn iterations applied to the time-dependent drifts of SDEs.
result Established a statistical bound on the squared total variation error of Sinkhorn bridge iterations.