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.
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-Knopp derivatives converge with linear rate.
problem Optimal transport problem with entropic regularization.
method Iterative proportional fitting procedure.
result Derivatives converge with linear rate.
This paper refines the Gaussian Sinkhorn algorithm for general multivariate models.
problem Finite-dimensional solutions for general Gaussian multivariate models.
method Recursive formulation of the Sinkhorn algorithm for Gaussian models, including closed form expressions of entropic transport maps and Schrödinger bridges.
result Refined convergence analysis of Gaussian Sinkhorn algorithms.
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.
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 …
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.
The Sinkhorn-Knopp algorithm converges quickly but the number of iterations is poorly understood.
problem Understanding the number of iterations required for the Sinkhorn-Knopp algorithm to converge.
method Analyzing the Sinkhorn-Knopp algorithm for matrices with a specific density threshold.
result The Sinkhorn-Knopp algorithm requires Ω ( n 1 / 2 / ε ) Ω(n^{1/2}/\varepsilon) Ω ( n 1/2 / ε ) iterations for matrices with density γ < 1 / 2 γ<1/2 γ < 1/2 . Paper analyzes convergence of Sinkhorn algorithm for discrete probability measures on torus.
problem Achieving exponential convergence of Sinkhorn algorithm in general settings.
method Coupling by reflection techniques for controlled diffusions on the torus.
result Proves pointwise exponential convergence of Sinkhorn iterates and their gradient.
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.
New algorithm for computing Wasserstein barycenters with guarantees.
problem Computing Wasserstein barycenters with varying regularization strengths.
method Damped Sinkhorn iterations followed by exact maximization/minimization steps.
result First non-asymptotic convergence guarantees for approximating Wasserstein barycenters.
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.
A new method reduces the computational cost of Sinkhorn algorithm for OT and UOT problems.
problem High computational complexity of Sinkhorn algorithm for OT and UOT problems.
method Importance sparsification method called Spar-Sink to efficiently approximate entropy-regularized OT and UOT solutions.
result The method reduces computational cost from O ( n 2 ) O(n^2) O ( n 2 ) to O ~ ( n ) \widetilde{O}(n) O ( n ) , and is consistent under mild regularity conditions. A new method uses optimal transport for semi-supervised classification.
problem Semi-supervised learning with limited labeled data.
method Optimal transport formulation with Sinkhorn iteration for label assignment.
result Improved performance on CIFAR-10, CIFAR-100, and SVHN datasets compared to FixMatch.
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.
New method finds closest martingale to Brownian motion.
problem Finding optimal martingale interpolating marginals.
method Martingale Sinkhorn algorithm, iterative scheme.
result Algorithm yields Bass potential in arbitrary dimension.
We consider the entropic regularization of discretized optimal transport and propose to solve its optimality conditions via a logarithmic Newton iteration. We show a quadratic convergence rate and validate numerically that the method compares favorably with the more commonly used Sinkhorn--Knopp algorithm for small reg…
The paper analyzes stability and convergence rates of entropic and Sinkhorn potentials.
problem Stability and convergence rates of entropic and Sinkhorn potentials.
method Semiconcavity properties of entropic potentials and Schrödinger bridges.
result Exponential convergence rates for gradient and Hessian of Sinkhorn iterates.
Permutations and matchings are core building blocks in a variety of latent variable models, as they allow us to align, canonicalize, and sort data. Learning in such models is difficult, however, because exact marginalization over these combinatorial objects is intractable. In response, this paper introduces a collectio…
Develops a new algorithm to calibrate signed datasets to specified marginals.
problem Calibrating signed datasets to specified marginals.
method Extends Schrödinger-Fortet-Sinkhorn paradigm to sign-indefinite multi-dimensional arrays.
result Proposes an optimization problem to update a sign-indefinite prior to match given marginals.
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.
A new method speeds up computation of Sinkhorn divergences to linear time.
problem Expensive computation of Sinkhorn divergences for comparing probability distributions.
method Using positive features to approximate ground costs, reducing computation time to linear.
result Sinkhorn divergences can be computed in linear time, scaling as O(nr).
The Sinkhorn flow is a gradient flow in a nonlocal Wasserstein geometry.
problem Entropy-regularized optimal transport and its applications.
method Thermodynamic interpretation of the Sinkhorn algorithm.
result The Sinkhorn flow is the gradient flow of entropy in a nonlocal Wasserstein geometry.
cuRegOT accelerates GPU-based entropic OT solving.
problem Slow convergence and high computational cost of optimal transport on GPUs.
method High-performance GPU solver with algorithmic and architectural optimizations.
result Significant speedups over state-of-the-art solvers.
Stability result for a popular algorithm in optimal transport.
problem Stability of the Iterative Proportional Fitting Procedure in time and metric.
method Uniform stability analysis in the 1-Wasserstein metric.
result Quantitative stability result for entropy-regularized Optimal Transport and Schrödinger bridges.
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
The paper improves boundary detection and density estimation on noisy data.
problem Detecting boundary points and estimating density on noisy data from compact manifolds.
method Doubly stochastic scaling of the Gaussian heat kernel via Sinkhorn iterations.
result The new estimates of boundary points and density outperform standard methods, especially under noise.
A new method estimates Schrödinger bridges without iterative simulations or neural networks.
problem Estimating the time-dependent drift between two probability distributions.
method Solving the static entropic optimal transport problem and modifying the potentials.
result The Sinkhorn bridge method provably estimates Schrödinger bridges with a rate of convergence dependent on the target measure's intrinsic dimensionality.
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 \ell_p ℓ p norm-bounded perturbations. In this paper, we propose a new threat model for adver…
New algorithm tackles low-rank constraints in optimal transport problems.
problem Optimal transport problems with low-rank constraints.
method Explicit factorization of low-rank couplings as a product of sub-coupling factors linked by a common marginal.
result Stationary convergence of the algorithm proved.
It is of increasing importance to develop learning methods for ranking. In contrast to many learning objectives, however, the ranking problem presents difficulties due to the fact that the space of permutations is not smooth. In this paper, we examine the class of rank-linear objective functions, which includes popular…
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 work studies the contraction coefficients of Schrödinger bridge problems in linear systems.
problem Optimally controlling the evolution of a system's state density over time.
method Analyzes and improves the convergence rates of dynamic Schrödinger systems via geometric and control-theoretic interpretations.
result New insights into improving computation of worst-case contraction coefficients by preconditioning.
sEM uses optimal transport to improve EM algorithm for better convergence and avoiding local optima.
problem Improving the EM algorithm for better convergence and avoiding local optima.
method sEM uses entropic optimal transport to compute responsibilities in the expectation step, leading to better global convergence guarantees and avoiding local optima.
result sEM learns cell labels significantly better than other approaches, improving convergence and avoiding local optima.
Paper tackles robust optimal transport with improved computational complexity and barycenter approximation.
problem Computing robust optimal transport and its barycenter efficiently.
method Sinkhorn-based algorithms for robust optimal transport and iterative Bregman projections for barycenter approximation.
result Improved computational complexity for robust optimal transport and barycenter approximation.
The paper analyzes mirror descent in measure spaces and its applications.
problem Optimizing convex functionals over measure spaces.
method Derives convergence of mirror descent for relatively smooth and convex pairs of functionals.
result Shows Sinkhorn's primal iterations and EM as mirror descent.
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.
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.
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.
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…
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.
FVI method calculates bicausal OT with neural networks, outperforming other methods.
problem Computing bicausal optimal transport with adapted coupling structures.
method FVI method using multilayer neural networks to approximate value functions.
result FVI method outperforms linear programming and Sinkhorn methods in scalability.
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…
This paper surveys algorithmic advancements in Optimal Transport with applications in machine learning.
problem Quantifying differences between distributions in various fields.
method Examines classical and modern computational techniques, including Sinkhorn iterations and primal-dual strategies.
result Highlights the robustness and scalability of OT algorithms in high-dimensional problems.
New discretization scheme for Wasserstein gradient flows using Schrödinger bridges.
problem Computing Wasserstein gradient flows efficiently and without score functions.
method Iterated Schrödinger bridge approximation with particle-based Sinkhorn algorithm.
result The scheme converges to Wasserstein gradient flows for certain flows, including heat flow.
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.