Sample Complexity of Sinkhorn divergences

Abstract

Optimal transport (OT) and maximum mean discrepancies (MMD) are now routinely used in machine learning to compare probability measures. We focus in this paper on \emph{Sinkhorn divergences} (SDs), a regularized variant of OT distances which can interpolate, depending on the regularization strength $\epsilon$, between OT ($\epsilon =0$) and MMD ($\epsilon =\infty$). Although the tradeoff induced by that regularization is now well understood computationally (OT, SDs and MMD require respectively $O(n^3\log n)$, $O(n^2)$ and $n^2$ operations given a sample size $n$), much less is known in terms of their \emph{sample complexity}, namely the gap between these quantities, when evaluated using finite samples \emph{vs.} their respective densities. Indeed, while the sample complexity of OT and MMD stand at two extremes, $1/n^{1/d}$ for OT in dimension $d$ and $1/\sqrt{n}$ for MMD, that for SDs has only been studied empirically. In this paper, we \emph{(i)} derive a bound on the approximation error made with SDs when approximating OT as a function of the regularizer $\epsilon$, \emph{(ii)} prove that the optimizers of regularized OT are bounded in a Sobolev (RKHS) ball independent of the two measures and \emph{(iii)} provide the first sample complexity bound for SDs, obtained,by reformulating SDs as a maximization problem in a RKHS. We thus obtain a scaling in $1/\sqrt{n}$ (as in MMD), with a constant that depends however on $\epsilon$, making the bridge between OT and MMD complete.

Cited by in corpus (68)

• The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine
• Geometric Dataset Distances via Optimal Transport
• Faster Wasserstein Distance Estimation with the Sinkhorn Divergence
• Entropic Optimal Transport between Unbalanced Gaussian Measures has a Closed Form
• Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem
• Conditional Sig-Wasserstein GANs for Time Series Generation
• COT-GAN: Generating Sequential Data via Causal Optimal Transport
• Statistical Inference for Generative Models with Maximum Mean Discrepancy
• Unbalanced minibatch Optimal Transport; applications to Domain Adaptation
• Sinkhorn AutoEncoders
• Asymptotics for semi-discrete entropic optimal transport
• Statistical and Topological Properties of Sliced Probability Divergences
• Scalable Optimal Transport Methods in Machine Learning: A Contemporary Survey
• Learning with minibatch Wasserstein : asymptotic and gradient properties
• How Well Do WGANs Estimate the Wasserstein Metric?
• Two-sample Test using Projected Wasserstein Distance
• Minibatch optimal transport distances; analysis and applications
• Wasserstein GANs Work Because They Fail (to Approximate the Wasserstein Distance)
• Statistical guarantees for generative models without domination
• Linear Time Sinkhorn Divergences using Positive Features
• Generalization Properties of Optimal Transport GANs with Latent Distribution Learning
• Re-evaluating Word Mover's Distance
• The statistical effect of entropic regularization in optimal transportation
• Differentiable Deep Clustering with Cluster Size Constraints
• Optimal Transport losses and Sinkhorn algorithm with general convex regularization
• Stochastic Optimization for Regularized Wasserstein Estimators
• Smooth $p$-Wasserstein Distance: Structure, Empirical Approximation, and Statistical Applications
• Limit Distribution Theory for the Smooth 1-Wasserstein Distance with Applications
• Optimal Transport as a Defense Against Adversarial Attacks
• Rates of convergence for density estimation with generative adversarial networks
• Estimating Barycenters of Measures in High Dimensions
• Asymptotic Guarantees for Generative Modeling Based on the Smooth Wasserstein Distance
• Statistical Optimal Transport posed as Learning Kernel Embedding
• A contribution to Optimal Transport on incomparable spaces
• Entropic estimation of optimal transport maps
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Two-sample Test with Kernel Projected Wasserstein Distance
• Gaussian-Smooth Optimal Transport: Metric Structure and Statistical Efficiency
• Sinkhorn Barycenter via Functional Gradient Descent
• Augmented Sliced Wasserstein Distances
• Climate Modelling in Low-Precision: Effects of both Deterministic & Stochastic Rounding
• Wasserstein Measure Coresets
• Generalized Sliced Distances for Probability Distributions
• CO-Optimal Transport
• Unsupervised Hierarchy Matching with Optimal Transport over Hyperbolic Spaces
• KALE Flow: A Relaxed KL Gradient Flow for Probabilities with Disjoint Support
• Online Sinkhorn: Optimal Transport distances from sample streams
• Improving Approximate Optimal Transport Distances using Quantization
• Utility/Privacy Trade-off through the lens of Optimal Transport
• Investigating and Improving Latent Density Segmentation Models for Aleatoric Uncertainty Quantification in Medical Imaging
• Discrepancy-based Inference for Intractable Generative Models using Quasi-Monte Carlo
• Equitable and Optimal Transport with Multiple Agents
• Information Constrained Optimal Transport: From Talagrand, to Marton, to Cover
• Efficient Discretizations of Optimal Transport
• Convergence of Gaussian-smoothed optimal transport distance with sub-gamma distributions and dependent samples
• Convergence and finite sample approximations of entropic regularized Wasserstein distances in Gaussian and RKHS settings
• Estimating 2-Sinkhorn Divergence between Gaussian Processes from Finite-Dimensional Marginals
• Matching Distributions via Optimal Transport for Semi-Supervised Learning
• On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport
• Uniform Confidence Band for Optimal Transport Map on One-Dimensional Data
• Randomized Stochastic Gradient Descent Ascent
• Efficient estimates of optimal transport via low-dimensional embeddings
• Regularized Optimal Transport for Dynamic Semi-supervised Learning
• Iterative Alignment Flows
• Optimal transport weights for causal inference
• Informative GANs via Structured Regularization of Optimal Transport
• Bayesian Inference for Optimal Transport with Stochastic Cost
• Wasserstein Random Forests and Applications in Heterogeneous Treatment Effects