PaperlayerView exact revision on arXiv

Source-linked AI summary

Sample Complexity of Sinkhorn divergences

Aude Genevay, Lénaic Chizat, Francis Bach, Marco Cuturi, Gabriel Peyré

arXiv:1810.02733v2math.ST

TL;DR

The paper addresses limited knowledge of Sinkhorn divergences’ sample complexity relative to OT and MMD. It derives approximation and regularity results and proves a 1/sqrt(n) convergence rate whose constant depends on ε, revealing a tradeoff between OT approximation and sample convergence.

  • Problem

    Sinkhorn divergences’ sample complexity was less understood than the contrasting convergence behaviors of OT and MMD, despite their use for comparing probability measures.

  • Method

    The paper bounds Sinkhorn’s approximation error to OT, establishes measure-independent regularity of regularized OT potentials, and derives sample complexity through a reformulation in a reproducing-kernel Hilbert space.

  • Results

    1/sqrt(n) convergence matches MMD, while its constant depends on the inverse regularization parameter, so convergence worsens as regularization approaches standard OT.

  • Takeaways & Limitations

    The results establish a tradeoff between approximating OT with small regularization and achieving faster sample convergence with larger regularization.

  • Takeaways & Limitations

    The experiments indicate that the uniform bound on fε may not be tight, motivating tighter bounds in future work.

Abstract

from arXiv · show

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 $\varepsilon$, between OT ($\varepsilon=0$) and MMD ($\varepsilon=\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 $\varepsilon$, \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 $\varepsilon$, making the bridge between OT and MMD complete.

1 Introduction

The paper studies Sinkhorn divergences as a regularized bridge between computationally difficult OT and statistically efficient MMD. It addresses the open question of their sample complexity while developing theoretical properties of regularized OT.

  • Motivation: OT compares probability distributions with meaningful geometric sensitivity, including when their supports do not overlap.Its use in data science has been limited by computational cost and slow statistical convergence.
  • Motivation: MMD is an RKHS-based integral probability metric that is easy to compute.It has been applied broadly, including to generative-model estimation.
  • Sample-complexity gap: MMD sample complexity scales as 1/√n independently of dimension, whereas standard OT suffers from the curse of dimensionality.Poor sample complexity can cause overfitting and high gradient variance in parameter estimation.
  • Sample-complexity gap: Sinkhorn divergences interpolate between OT as ε approaches zero and MMD as ε approaches infinity, but their empirical convergence had remained largely unresolved.Regularization was suggested as a remedy for OT’s statistical difficulties.
  • Contributions: The paper contributes an OT-approximation bound, measure-independent Sobolev control of regularized OT optimizers, and an RKHS-based sample-complexity result.These results also motivate kernel-SGD for regularized OT.
  • Contributions: Sinkhorn divergences achieve the MMD-like 1/√n sample-complexity rate, with a constant depending inversely on regularization.Larger regularization improves convergence, while smaller regularization gives a better OT approximation; simple experiments examine dependence on ε and d.

2 Reminders on Sinkhorn Divergences

This section defines regularized OT by adding relative-entropy penalization and normalizes it into Sinkhorn divergences. The resulting quantity recovers OT and MMD in opposite regularization limits.

  • Optimal transport: The cost function c measures the cost of moving a unit of mass from x to y.The paper assumes c is smooth; choosing c(x,y)=dX(x,y)^p yields the p-Wasserstein distance.
  • Regularized OT: Regularized OT adds entropic regularization based on relative entropy with respect to α⊗β.This is the formulation introduced for regularized transport.
  • Regularized OT: Relative-entropy regularization permits a dual formulation as an expectation maximization problem.The optimal dual potentials exist and are unique almost everywhere up to an additive constant.
  • Sinkhorn divergences: Sinkhorn divergences normalize regularized OT so that the self-divergence of a measure is zero.The normalization corrects the nonzero value of regularized OT evaluated at identical measures.
  • Sinkhorn divergences: As ε approaches zero, Sinkhorn divergences recover OT; as ε approaches infinity, they yield the MMD associated with k=−c/2.The paper studies sample complexity first for Wε and states that the results extend to the normalized divergence.

3 Approximating Optimal Transport with Sinkhorn Divergences

The paper bounds the error from replacing OT with entropically regularized OT by constructing finite-entropy approximations of an optimal transport plan. Block resolution balances transport-cost error against entropy error.

  • Approximation bound: Under bounded supports and an L-Lipschitz cost, Theorem 1 bounds the regularization gap between Wε and W.The stated result applies to probability measures on subsets of Rd with equal support diameters bounded by D.
  • Proof strategy: The proof constructs π∆ by block-approximating an optimal transport plan at resolution ∆.The block construction preserves nonnegativity, fixed marginals, and finite entropy.
  • Approximation bound: 0 ≤ Wε(α,β)−W(α,β) ≤ (C(π∆)−C(π0))+εH(π∆).The inequality compares a finite-entropy approximation π∆ with an optimal unregularized plan π0.
  • Proof strategy: Lipschitz regularity of the cost controls the transport-cost increase caused by block approximation.The relevant bound depends on the cost’s Lipschitz constant in x and y.
  • Entropy control: For continuous measures, H∆(α) is bounded below by −d·log(2D/∆), while discrete measures relate H∆ to discrete entropy below atom separation.The continuous entropy term diverges as ∆ approaches zero, so its rate must be controlled.
  • Entropy control: The combined bound is minimized by choosing a resolution ∆ that balances the approximation terms.The text states that the resulting bound is convex in ∆.

4 Properties of Sinkhorn Potentials

The paper proves that Sinkhorn potentials are uniformly controlled in Sobolev spaces independently of the input marginals. This yields an RKHS representation that supports sample-complexity analysis and kernel-SGD.

  • Sobolev control: Sinkhorn potentials are bounded in Hs(Rd) when the supports are compact and the cost is smooth.The required smoothness order satisfies s>d/2, making Hs(Rd) an RKHS.
  • Sobolev control: The Sobolev-norm constants depend on support diameters, dimension, and cost regularity rather than on the measures themselves.This is the measure-independent control needed for the later statistical argument.
  • Regularity properties: The potentials satisfy pointwise bounds and are L-Lipschitz when c has Lipschitz constant L.Corresponding statements hold for v after exchanging the roles of u, X, and Y.
  • Proof strategy: Potential derivatives are controlled through recurrence relations derived from the dual optimality condition.The proof uses differentiation under the integral and auxiliary-function bounds.
  • Algorithmic consequence: The RKHS formulation enables kernel-SGD by representing potentials as kernel combinations and optimizing their coefficients stochastically.Knowing the RKHS radius and Sobolev or Matérn kernel is important for convergence and numerical performance.

5 Approximation from Samples

The paper bounds the error from replacing probability measures with empirical samples in Sinkhorn divergences. By placing optimal potentials in a measure-independent Sobolev RKHS ball and applying PAC-learning tools, it obtains 1/√n convergence with ε-dependent behavior.

  • Finite samples require bounding the gap between Sinkhorn divergences of the original measures and their empirical counterparts.
  • 1/√n is the convergence rate for empirical Sinkhorn divergences, with different asymptotic behaviors as ε becomes small or large.
  • For sufficiently large ε, the convergence rate no longer depends on ε, whereas small ε produces critical regularization dependence.
  • Optimal potentials lie in a Sobolev RKHS ball whose radius is independent of the measures, enabling an RKHS maximization formulation.The RKHS is Hs(Rd), with s = ⌊d/2⌋ + 1.
  • PAC-learning bounds apply because the Sinkhorn loss is Lipschitz over a bounded subspace containing the optimal potentials.The argument combines bounded potentials, Lipschitzness of fε, and RKHS Rademacher-complexity bounds.

6 Experiments

Experiments examine how sample-size convergence varies with dimension, regularization, cost smoothness, and domain boundedness. They broadly support stronger ε effects at small regularization, while variance also reflects dimension and domain diameter.

  • Experimental setup: 300 repetitions estimate normalized Sinkhorn divergence against sample size using log-log curves with shaded standard-deviation bars.The experiments evaluate the average empirical divergence across repeated runs.
  • Bounded quadratic-cost experiments: For bounded hypercube distributions with quadratic cost, ε influences convergence more strongly as dimension increases.Curves are nearly parallel across ε in dimension 2 but separate more at higher dimensions.
  • Bounded quadratic-cost experiments: ε = 1 is an observed cutoff: values ε ≥ 1 have similar convergence rates, whereas smaller ε produces clearer dependence on 1/ε.The same cutoff appears when comparing dimensions at fixed ε.
  • Nonsmooth-cost experiments: With the nonsmooth L1 cost, convergence slows as ε decreases, with the effect especially clear in dimension 2, while dimension influence remains similar.The ε effect is more pronounced than under the quadratic cost, even for small dimensions.
  • Unbounded-domain experiments: For standard normal distributions on unbounded domains, ε still visibly affects convergence, but dimension effects are less clear and variance is higher.The higher variance is consistent with a concentration bound depending on domain diameter.
  • Variance and open questions: Observed variance depends on d and ε, while the ε exp(κ/ε) factor in the uniform bound suggests the bound may not be tight for small ε.The authors identify tighter bounds as an open direction.

7 Conclusion

The conclusion presents convergence results for approximating OT and for empirical Sinkhorn divergences, with an MMD-like rate whose constant depends on regularization. It also connects the RKHS reformulation to kernel-SGD and identifies tighter bounds and broader conditions as open problems.

  • 7 Conclusion: The paper proves both an approximation-error bound from regularized OT to standard OT and a sample-complexity bound for empirical Sinkhorn divergences.These are presented as the paper’s two convergence theorems.
  • 7 Conclusion: 1/√n convergence matches MMD, but its constant depends on the inverse regularization parameter.This dependence complements the interpolation of Sinkhorn divergences between OT and MMD.
  • 7 Conclusion: Reformulating Sinkhorn divergences as expectation maximization in an RKHS ball opens the door to kernel-SGD computation.The conclusion links the theoretical reformulation to a potential computational use.
  • 7 Conclusion: Tighter theorem bounds could yield a sharp estimate of the optimal ε for approximating OT at a given sample size.The authors also flag unbounded domains and nonsmooth costs as settings where the rate appears empirically to persist.

Appendix

The appendix develops derivative bounds through recurrence arguments, extending the one-dimensional proof to multivariate functions with multi-index notation. It repeatedly differentiates optimality conditions and controls the resulting terms.

  • Appendix: The one-dimensional proof establishes derivative bounds by recurrence and uses Leibniz’s formula for successive derivatives of products.The recurrence controls higher-order quantities through previously bounded terms.
  • Appendix: Differentiating the optimality condition and rearranging provides the starting relation for extending the bounds.Further differentiation yields the recurrence used in the proof.
  • Appendix: The second lemma is proved by induction on a property P_n that bounds the relevant derivative quantities across indices and orders.The proof initializes the recurrence and assumes P_n to derive the next bounds.
  • Appendix: The multidimensional extension indexes successive differentiation directions by σ ∈ {1, . . . , d}^N and uses multi-indices for derivatives.The multivariate Leibniz formula replaces the one-dimensional version in the same recurrence strategy.
Loading 1810.02733v2…