PaperlayerView exact revision on arXiv

Source-linked AI summary

Statistical bounds for entropic optimal transport: sample complexity and the central limit theorem

Gonzalo Mena, Jonathan Weed

arXiv:1905.11882v2math.STcs.LGstat.ML

TL;DR

The paper addresses the need for rigorous statistical guarantees for entropic OT beyond compactly supported measures and finite metric spaces. It derives sample-complexity bounds and a central limit theorem for subgaussian measures, then develops an entropy estimator for variables corrupted by subgaussian noise. The bounds improve prior results exponentially, while the CLT is supported by simulations and the entropy-estimation methods exhibit a memory–convergence trade-off.

  • Problem

    Rigorous statistical behavior of entropic OT was previously characterized mainly for compactly supported or finitely supported measures, leaving general subgaussian measures insufficiently understood.

  • Method

    The paper analyzes population–empirical entropic costs for subgaussian measures, proves sample-complexity bounds and a CLT, and uses the results to construct an entropy estimator.

  • Results

    The analysis improves Genevay et al.’s sample-complexity bound by an exponential factor, extends it to unbounded measures, and establishes a CLT previously known only for finite metric spaces.

  • Takeaways & Limitations

    Entropic OT provides statistical tools for convergence analysis, distributional inference, and entropy estimation under subgaussian assumptions.

  • Takeaways & Limitations

    The analysis focuses on the squared Euclidean cost, while scalable implementations and detailed theory for differing entropic OT-based entropy estimators remain future work.

Abstract

from arXiv · show

We prove several fundamental statistical bounds for entropic OT with the squared Euclidean cost between subgaussian probability measures in arbitrary dimension. First, through a new sample complexity result we establish the rate of convergence of entropic OT for empirical measures. Our analysis improves exponentially on the bound of Genevay et al. (2019) and extends their work to unbounded measures. Second, we establish a central limit theorem for entropic OT, based on techniques developed by Del Barrio and Loubes (2019). Previously, such a result was only known for finite metric spaces. As an application of our results, we develop and analyze a new technique for estimating the entropy of a random variable corrupted by gaussian noise.

1. INTRODUCTION

Entropic OT combines computational efficiency with favorable statistical behavior, but rigorous guarantees require understanding its convergence and fluctuations beyond compactly supported settings. The paper develops such results for subgaussian measures and applies them to entropy estimation under noise.

  • Optimal transport is increasingly used for high-dimensional data analysis, including domain adaptation, image recognition, and word embedding.
  • Entropic regularization enables fast large-scale OT algorithms and has useful statistical properties for machine learning applications.
  • Genevay et al. showed that empirical entropic OT converges at the parametric 1/√n rate for compactly supported measures, despite standard OT’s curse of dimensionality.
  • The paper extends statistical analysis to unbounded probability measures in arbitrary dimension, improving sample-complexity bounds and establishing a central limit theorem for subgaussian distributions.
  • The results are applied to entropy estimation for random variables corrupted by subgaussian noise, motivated partly by information-theoretic analysis in deep learning.
  • The analysis focuses on the squared Euclidean cost and normalizes the regularization parameter to ϵ = 1; broader cost functions are left for future work.

2. SAMPLE COMPLEXITY FOR THE ENTROPIC TRANSPORTATION COST FOR GENERAL SUBGAUSSIAN MEASURES

The section develops sample-complexity bounds for entropic OT between subgaussian measures, extending beyond bounded supports while removing the prior exponential dependence on diameter and regularization. Its proof combines potential regularity, empirical-process control, covering-number bounds, and concentration for simultaneously varying empirical measures.

  • Sample-complexity bounds: The earlier bound applies to bounded domains but has exponential dependence on D and 1/ε, limiting its quantitative usefulness for unbounded or large-diameter measures.The earlier result concerns empirical entropic OT, contrasting with the slower n^-1/d convergence of empirical squared Wasserstein distance.
  • Sample-complexity bounds: n^-1/2: For ε = 1, the expected empirical entropic-cost error is bounded by K_d(1 + σ^(⌈5d/2⌉+6))/√n.This theorem is presented as a sharpening of the earlier bounded-domain result.
  • Sample-complexity bounds: The new bounds remove the exponential dependence on D^2/ε and replace the compact-support diameter D with the subgaussian variance proxy σ^2.The polynomial prefactor has a higher degree than in the earlier theorem, indicating a potential weakness of the new bound.
  • Proof strategy: The proof handles unbounded supports by controlling Hölder norms of optimal potentials on compact sets and completing the argument with a chaining bound.A preliminary argument removes the exponential term by reducing the problem to an empirical process.
  • Proof strategy: Optimal dual potentials for σ^2-subgaussian distributions admit derivative bounds, allowing them to be placed in a controlled function class F_σ.The resulting analysis bounds an empirical process indexed by this class.
  • Proof strategy: A covering-number bound for the function class, together with subgaussian annular decompositions and concentration, controls the empirical process for both P_n and Q_n.The argument extends a one-measure empirical-process bound to simultaneously varying empirical measures using the triangle inequality.

3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT

This section establishes a central limit theorem for empirical entropic OT with subgaussian measures, extending distributional results beyond finite metric spaces. The proof controls optimal potentials and reduces entropic OT fluctuations to an empirical-process linearization.

  • 3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT: Unlike earlier entropic-OT CLTs restricted to finite metric spaces, this result applies to arbitrary subgaussian measures.The section contrasts the present setting with finite-support results and notes that the two-sample proof is omitted because it adapts straightforwardly.
  • 3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT: Theorem 3 establishes a central limit theorem for S(Pn, Q) when P is subgaussian.The result characterizes the asymptotic fluctuations of the empirical entropic cost in the one-sample setting.
  • 3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT: The limiting variance satisfies lim n→∞ n Var(S(Pn, Q)) = VarP(f(X)).The variance is determined by the optimal potential f under P.
  • 3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT: For independent samples from P and Q, the normalized cost converges to a centered normal distribution with variance (1 −λ) VarP(f(X1)) + λ VarQ(g(Y1)).Here λ = limm,n→∞ n/(m+n) ∈ (0, 1).
  • 3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT: The potential convergence makes the nonlinear entropic cost asymptotically equivalent to a linear empirical average, enabling standard distributional and L2 limits.The argument shows the remainder variance is negligible before applying the limit statements to the linearization.
  • 3. A CENTRAL LIMIT THEOREM FOR ENTROPIC OT: The proof first obtains uniform-on-compacts convergence of empirical optimal potentials to population optimal potentials.Proposition 4 provides this convergence for subgaussian P and Q.

4. APPLICATION TO ENTROPY ESTIMATION

This section links entropic OT to differential entropy for convolutions and uses that relation to construct an estimator for a subgaussian variable corrupted by independent Gaussian noise. The estimator inherits convergence and variance guarantees from the paper’s entropic-OT results.

  • 4. APPLICATION TO ENTROPY ESTIMATION: The entropic cost is linked to the differential entropy of a convolution through a relation for costs c(x, y) := g(x −y).The construction allows the cost to be nonquadratic in the general proposition.
  • 4. APPLICATION TO ENTROPY ESTIMATION: For Q = P ∗Φg, the relation becomes −log Zg = S(P, P ∗Φg) + H(P ⊗(P ∗Φg) |P ⊗ν).The relative-entropy term is then identified with −h(P ∗Φg).
  • 4. APPLICATION TO ENTROPY ESTIMATION: Theorem 4 defines the plug-in estimator ĥ(Q) = S(Pn, Qm) + log Zg for the entropy of the sum of independent X ∼P and Gaussian noise G.Pn and Qm are independent samples from P and Q.
  • 4. APPLICATION TO ENTROPY ESTIMATION: The estimator has a 1/√n convergence rate and an asymptotic variance characterized by λ VarQ(log q(Y)).The variance statement uses λ = limm,n→∞ n/(m+n).

5. EMPIRICAL RESULTS

The experiments examine finite-sample convergence of entropic OT and compare three entropy estimators. They find CLT-consistent fluctuations and fastest convergence for the paired entropic-OT estimator, with a substantial memory trade-off.

  • 5. EMPIRICAL RESULTS: The experiments use entropy estimation because the optimal potentials have closed forms and comparison with a prior estimator is available.The setup studies a Gaussian-mixture distribution formed by convolving P with Gaussian noise.
  • 5. EMPIRICAL RESULTS: S(Pn, Qn) becomes a worse estimator for S(P, Q) as dimension increases or the regularization parameter decreases.This pattern is reported as consistent with the bounds in Theorem 2 and Corollary 1.
  • 5. EMPIRICAL RESULTS: Finite-n fluctuations of S(Pn, Qn) are broadly consistent with the central limit theorem’s predictions.Figure 1 compares predicted and actual fluctuations and displays rescaled fluctuation histograms.
  • 5. EMPIRICAL RESULTS: The paired entropic-OT estimator achieves the fastest convergence among the compared entropy estimators.The comparison includes independent entropic OT and a Monte Carlo Gaussian-mixture estimator.
  • 5. EMPIRICAL RESULTS: The paired and independent entropic-OT estimators require O(n^2) memory in the naive implementation, versus O(n) for sequential computation of the mixture estimator.The quadratic requirement comes from storing the matrix D_ij = e^−||x_i−y_j||^2/2σ^2.
  • 5. EMPIRICAL RESULTS: A detailed theoretical analysis of the different entropic-OT estimators and more scalable implementations remain future work.The authors specifically highlight the observed differences between paired and independent estimators.

APPENDIX A: OMITTED RESULTS AND PROOFS

The appendix establishes regularity and convergence properties of entropic optimal potentials, then uses them with variance tensorization and uniform integrability to prove asymptotic results.

  • Optimal potentials: Subgaussian distributions admit smooth optimal potentials satisfying the dual optimality conditions throughout R^d.The construction also provides global integrability and bounds for the potentials.
  • Variance control: The proof of the variance result uses tensorization of variance through the Efron-Stein inequality for symmetric functions of independent samples.The argument compares the statistic computed from the sample with one computed after replacing a sample copy.
  • Potential convergence: Optimal potentials for empirical and population measures converge uniformly on compact sets under subgaussian assumptions.This convergence yields pointwise convergence almost surely for the empirical potentials.
  • Variance control: The scaled difference between the empirical entropic OT statistics and their leave-one-replacement counterparts converges almost surely to zero.The proof combines pointwise convergence of potentials with finite second moments.
  • Uniform integrability: Uniform integrability of the squared scaled difference, together with almost sure convergence, completes the asymptotic argument.The proof constructs a modified coupling preserving the empirical marginal and controls its mutual-information and squared-integral terms.

APPENDIX B: TECHNICAL LEMMAS

The technical lemmas show that empirical measures inherit a random uniform subgaussian bound and provide moment estimates used to control potentials and convergence arguments.

  • Subgaussian control: Empirical measures and the underlying distribution are uniformly subgaussian almost surely under a subgaussian population assumption.The resulting parameter is random but finite.
  • Moment bounds: Subgaussianity supplies finite moments and bounds needed to establish uniform integrability of terms involving the optimal potentials.The appendix bounds tilted moments by splitting integrals into bounded and tail regions.
  • Proof tools: The lemmas use Jensen’s inequality, moment estimates, and the strong law of large numbers to control empirical quantities.These tools support almost-sure and integrability statements throughout the proofs.
Loading 1905.11882v2…