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.
New method speeds up computation of Sinkhorn distances for large datasets.
problem Quadratic time and memory requirements of standard Sinkhorn distance computation.
method Combining Nyström method and Sinkhorn scaling for faster approximations.
result Accurate approximations of Sinkhorn distances on massive datasets.
New method learns semidefinite regularizers from data.
problem Learning suitable regularization functions from data without domain-specific expertise.
method Combines linear and semidefinite programming techniques for structured factorizations of data matrices.
result Algorithm identifies correct regularizer promoting data structure, converging locally linearly.
This paper introduces Gumbel-Sinkhorn networks for learning latent matchings.
problem Learning in latent variable models with permutations is difficult due to combinatorial intractability.
method Approximates maximum-weight matching using the Sinkhorn operator, extending Gumbel-Softmax.
result Demonstrates effectiveness on sorting, jigsaw puzzles, and neural signal identification tasks.
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.
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.
Fast algorithm for online optimization on transport polytopes.
problem Optimizing convex objectives on transport polytopes.
method Mirror Sinkhorn algorithm combining Sinkhorn scaling and mirror descent.
result Robust and efficient online optimization for convex objectives.
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.
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.
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.
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 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 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.
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).
Paper introduces a new Brenier approach for more accurate Wasserstein distance calculation.
problem Estimating discrepancy between two data distributions, especially with quasi-discrete and discrete measures.
method Introduces a new Brenier approach to calculate a more accurate Wasserstein distance between two discrete distributions.
result Successfully avoids the limitations of the Sinkhorn distance, such as approximation and divide by zero issues.
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…
Improved spectral convergence bounds for diffusion maps on tori.
problem Weak theoretical error bounds for diffusion maps.
method Spatial Hardy space estimates, PDE spectral stability, Sinkhorn weights.
result Matched pointwise error bounds for spectral data and operator convergence.
Extends geostatistical simulation method to handle multiple variables and large grids.
problem Scalability and handling of multiple variables in geostatistical simulation.
method Uses Sinkhorn optimal transport with sparse matcher and FFT-MA Gaussian backbone.
result MST-Direct reproduces joint distribution with zero histogram error and accurately preserves spatial correlation.
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 Ω(n1/2/ε) iterations for matrices with density γ<1/2. Study Hilbert's projective metric for bounded growth functions leading to Sinkhorn's algorithm convergence.
problem Optimal transport in unbounded settings with heavy-tailed distributions.
method Hilbert's projective metric for integrable functions of bounded growth, kernel integral operators as contractions.
result Exponential convergence of Sinkhorn's algorithm for light-tailed marginal distributions.
Large Sinkhorn couplings improve flow models in data generation tasks.
problem Training flow models with optimal transport couplings.
method Using large batches of source and target points, and applying entropic regularization with a low ε. result Flow models perform better with large Sinkhorn couplings and low regularization.
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.
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).
Improved neural framework for scaling entropic MOT with significant computational gains.
problem High computational overhead in multimarginal optimal transport.
method Neural Entropic MOT (NEMOT) using mini-batch training to reduce complexity.
result Significant speedups and feasibility improvements for multimarginal data.
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.
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 framework for efficient PD averaging and clustering.
problem Challenges in averaging and clustering persistence diagrams.
method Reformulate PD metrics as optimal transport problems, leveraging recent computational advances.
result Scalable computations of PD barycenters and clustering on thousands of diagrams.
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 proves convergence of bi-stochastically normalized graph Laplacian to manifold Laplacian and robustness to outlier noise.
problem Convergence of bi-stochastically normalized graph Laplacian to manifold Laplacian and robustness to outlier noise.
method Proves convergence of bi-stochastically normalized graph Laplacian to manifold Laplacian with rates, and proposes an approximate and constrained matrix scaling problem to achieve the same consistency rate.
result Graph Laplacian consistency rate matches the rate for clean manifold data plus an additional term proportional to the boundedness of the inner-products of the noise vectors.
A new algorithm screens negligible components to efficiently approximate optimal transport distances.
problem Efficiently approximating the Sinkhorn distance between discrete measures.
method Screening of negligible components in the dual solution of the regularized Sinkhorn problem.
result Screenkhorn algorithm provides provable guarantees with smaller computational complexity.
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.
New method generates adversarial examples using Wasserstein distance.
problem Creating robust classifiers against image manipulations.
method Developed a procedure to project onto Wasserstein ball using modified Sinkhorn iteration.
result Successfully attacked image classification models with 3% accuracy within a 10% pixel mass movement.
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. FedAVOT improves federated learning by aligning user distributions.
problem Partial client participation leads to biased and unstable updates in federated learning.
method Formulates aggregation as masked optimal transport to align availability and importance distributions.
result Achieves a standard O(1/√T) rate, independent of the number of participating users per round.
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.
Paper proposes Sinkformers for Transformers with doubly stochastic attention.
problem Improving Transformer models' accuracy in vision and natural language processing.
method Using Sinkhorn's algorithm to make attention matrices doubly stochastic instead of SoftMax normalization.
result Sinkformers enhance model accuracy in vision and natural language processing tasks.
New scalable algorithm for non-negative linear regression with entropy-regularized OT loss.
problem Generalizing task-specific linear models to broader applications.
method Sinkhorn-like scaling iterations for convex penalty and datafit terms.
result Simple multiplicative updates for various penalty and datafit terms.
Wasserstein Discriminant Analysis improves classification of high-dimensional data.
problem Improving classification of high-dimensional data.
method Computes a suitable linear map onto a lower dimensional subspace using regularized Wasserstein distances.
result WDA shows promising results in prediction and visualization on various datasets.
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.
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.
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…
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.
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.
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.
Paper shows near-linear time approximation for optimal transport.
problem Computing optimal transport distances efficiently.
method New analysis of Sinkhorn iteration and greedy coordinate descent algorithm, Greenkhorn.
result Achieves near-linear time approximation for optimal transport distances.
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.
New algorithm estimates barycenters of distributions using Frank-Wolfe.
problem Estimating the average of arbitrary probability distributions.
method Frank-Wolfe optimization for Sinkhorn divergence, incrementally populating support.
result Converges in both discrete and continuous distributions, with proven rates.