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.
New algorithm solves Schrödinger bridge problem with mismatched channels.
problem Solving Schrödinger bridge problem with input and noise channel mismatch.
method Design of a Sinkhorn recursion with memory for nonlinear PDEs.
result Demonstrates solving control-affine Schrödinger bridge problem.
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.
New algorithm solves complex mean-field Schrödinger bridge problem.
problem Designing a controller for diffusion processes with nonlocal interaction.
method Generalized Hopf-Cole transform and Sinkhorn-type algorithm.
result Convergence guarantees for the proposed algorithm under mild assumptions.
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 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.
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.
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.
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.
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.
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.
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.
Clarifies relation for solving control-affine Schrödinger bridge problems.
problem Solving control-affine Schrödinger bridge problems via Hopf-Cole transform.
method Applies Hopf-Cole transform to conditions of optimality, resulting in nonlinear PDEs.
result Generic control-affine Schrödinger bridge requires further algorithmic development.
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.
E-ROBOT improves robust statistics and ML via Schrödinger bridge theory.
problem Statistical and machine learning tasks in high dimensions.
method Entropic-regularized Robust Optimal Transport (E-ROBOT) framework.
result E-ROBOT avoids the curse of dimensionality with O(n−1/2) sample complexity. Following closely the construction of the Schrodinger bridge, we build a new class of Stochastic Volatility Models exactly calibrated to market instruments such as for example Vanillas, options on realized variance or VIX options. These models differ strongly from the well-known local stochastic volatility models, in p…
New method estimates Schrödinger bridge potentials via empirical risk minimization.
problem Estimating Schrödinger bridge potentials from samples.
method Rewriting Schrödinger system as a fixed-point equation and estimating the potential via empirical risk minimization.
result Uniform concentration of empirical risk around population counterpart under sub-Gaussian assumptions.
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.
TreeDSB solves mOT problems on tree-structured costs for Wasserstein barycenters.
problem Optimal transport with multiple marginals and tree-structured quadratic costs.
method Tree-based Diffusion Schrödinger Bridge (TreeDSB) for continuous and dynamic solutions.
result TreeDSB efficiently computes Wasserstein barycenters in high dimensions.
We solve a Schrödinger bridge with a quadratic state cost, finding a closed-form solution.
problem Optimizing diffusion processes between given distributions.
method Regularized Schrödinger bridge with a quadratic state cost.
result Closed-form solution for the Markov kernel of the regularized Schrödinger bridge.
Estimates time-series drifts from i.i.d. data using a direct Nadaraya-Watson plug-in method.
problem Nonparametric estimation of Schrödinger bridge drifts from single time interval data.
method Direct Nadaraya-Watson plug-in estimator based on kernelized numerator and denominator terms.
result Uniform non-asymptotic bound, CLT under undersmoothing, and adaptive bandwidth selector.
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.
Proposes a new algorithm for robust learning in Schrödinger bridge problems.
problem Uncertainty in estimated learning signals in Schrödinger bridge problems.
method Variational Online Mirror Descent (OMD) framework for Schrödinger bridge problems.
result Formally proves convergence and a regret bound for the OMD formulation of Schrödinger bridge acquisition.
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.
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. 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…
Novel algorithms for entropic optimal transport from an optimisation perspective.
problem Solving the entropic-regularised optimal transport problem.
method Developed novel methods inspired by mirror descent, solving semi-dual problems or non-convex constrained problems over joint distributions.
result Non-asymptotic rates of convergence for the proposed methods under minimal assumptions.
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.
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.
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 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.
Consider a reference Markov process with initial distribution π0 and transition kernels {Mt}t∈[1:T], for some T∈N. Assume that you are given distribution πT, which is not equal to the marginal distribution of the reference process at time T. In this scenario, Schrödinger addressed t…
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.
DSB approximates SB problem for faster generative modeling.
problem Fast generation from complex data distributions.
method Entropy-regularized optimal transport on path spaces.
result DSB yields faster convergence to data distribution.
A new associative memory uses Sinkhorn divergence for efficient pattern retrieval.
problem Efficiently retrieving patterns from large datasets of weighted point clouds.
method Derived retrieval dynamics as a SHK gradient flow, discretized for a deterministic algorithm.
result Proved basin invariance, geometric convergence, and robust recovery from perturbations.
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.
OTSeg uses multi-prompt Sinkhorn attention to improve zero-shot semantic segmentation.
problem Leveraging pre-trained CLIP knowledge to align text embeddings with pixel embeddings.
method OTSeg employs Multi-Prompts Sinkhorn (MPS) and Multi-Prompts Sinkhorn Attention (MPSA) to enhance semantic feature matching.
result OTSeg achieves state-of-the-art performance in zero-shot semantic segmentation tasks.
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.
A new algorithm for training generative models using Sinkhorn divergence.
problem Training generative adversarial networks (GANs).
method Sinkhorn Natural Gradient (SiNG) algorithm for steepest descent on probability space.
result Explicit expression and efficient evaluation of the Sinkhorn information matrix (SIM).
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 …
We present a novel algorithm to estimate the barycenter of arbitrary probability distributions with respect to the Sinkhorn divergence. Based on a Frank-Wolfe optimization strategy, our approach proceeds by populating the support of the barycenter incrementally, without requiring any pre-allocation. We consider discret…
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 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.
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.