PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimation of Wasserstein distances in the Spiked Transport Model

Jonathan Niles-Weed, Philippe Rigollet

arXiv:1909.07513v1math.STstat.TH

TL;DR

High-dimensional Wasserstein-distance estimation is difficult, and the paper asks whether low-dimensional structure can change that. It formalizes such structure in the spiked transport model and analyzes WPP. WPP attains near-optimal rates under the model, while the paper’s lower bounds and computational evidence describe limits outside that setting.

  • Problem

    In high dimensions, empirical Wasserstein distances generally converge slowly, and it is unclear whether estimating the distance itself can avoid the curse of dimensionality.

    Source: §1 · pp. 1–2

  • Method

    The paper models pairs of distributions that differ only on a low-dimensional subspace and analyzes Wasserstein Projection Pursuit (WPP) under that structure.

    Source: §1 · p. 2

  • Results

    WPP achieves near-optimal estimation rates under the spiked transport model, while estimating the distance without such structure is essentially as hard as estimating a measure in Wasserstein distance.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    The results identify low-dimensional structure as a way to alleviate the plug-in estimator’s curse, but the computational analysis suggests efficient estimators may not exploit it.

    Source: §1 · p. 3

    The lower bound leaves a logarithmic-factor gap from the naive upper bound for large d, and closing it remains open.

    Source: §3.3 · p. 6

Abstract

from arXiv · show

We propose a new statistical model, the spiked transport model, which formalizes the assumption that two probability distributions differ only on a low-dimensional subspace. We study the minimax rate of estimation for the Wasserstein distance under this model and show that this low-dimensional structure can be exploited to avoid the curse of dimensionality. As a byproduct of our minimax analysis, we establish a lower bound showing that, in the absence of such structure, the plug-in estimator is nearly rate-optimal for estimating the Wasserstein distance in high dimension. We also give evidence for a statistical-computational gap and conjecture that any computationally efficient estimator is bound to suffer from the curse of dimensionality.

1. INTRODUCTION

Wasserstein distances are difficult to estimate in high dimensions, but the spiked transport model captures cases where the distributions differ only on a low-dimensional subspace. Wasserstein Projection Pursuit (WPP) achieves near-optimal estimation rates under that structure, while the paper’s lower bounds and computational analysis delimit what is achievable without it.

1. INTRODUCTION

  • In high dimensions, empirical Wasserstein distances generally converge at the slow rate n^-1/d, making empirical distributions poor proxies for the underlying measures.The paper notes that the estimation rate is often known to be tight up to logarithmic factors.Source: §1 · pp. 1–2
  • For any p ≥ 1, estimating the Wasserstein distance itself is essentially as hard as estimating a measure in Wp-distance, so estimators must suffer from the curse of dimensionality without structure.A concurrent independent result establishes a related conclusion for p = 1 [58].Source: §1 · p. 2
  • The spiked transport model assumes that two distributions differ only on a low-dimensional subspace, a structure also underlying alternatives such as Sliced Wasserstein distance.The paper formalizes this assumption as a way to leverage plausible structure in optimal transport.Source: §1 · p. 2
  • WPP achieves near-optimal Wasserstein-distance estimation rates under the spiked transport model and alleviates the plug-in estimator’s curse of dimensionality.The paper also gives evidence that computationally efficient estimators may not exploit this low-dimensional structure.Source: §1 · pp. 2–3
  • The authors use the statistical query framework to argue that computationally efficient Wasserstein-distance estimators are bound to suffer from the curse of dimensionality.They present this as evidence of a tradeoff between statistical and computational efficiency.Source: §1 · p. 3

2. MODEL AND METHODS

The paper introduces a low-dimensional model for pairs of distributions and studies Wasserstein-distance estimation under concentration assumptions. Its Wasserstein Projection Pursuit estimator uses projections to exploit the model’s structure and is shown to be near-minimax optimal.

2.1 Wasserstein distances

  • Wasserstein distances are introduced through couplings between probability measures, with extensions to general metric spaces outside the paper’s scope.The paper refers readers to Villani for a comprehensive treatment of those extensions.Source: §2.1 · p. 3

2.2 Spiked transport model

  • The spiked transport model assumes that two high-dimensional distributions differ only on a shared k-dimensional subspace U, called the spike.The paper asks whether n observations from each distribution permit estimation faster than n^-1/d.Source: §2.2 · p. 4

2.3 Concentration assumptions

  • The analysis assumes both distributions satisfy a Tp(σ^2) transport inequality, a condition equivalent here to subgaussian concentration of Wp(μn, μ).The paper motivates these assumptions as necessary for sharp statistical results.Source: §2.3 · p. 4

2.4 Wasserstein projection pursuit

  • Wasserstein Projection Pursuit (WPP) maximizes projected Wasserstein distance over k-dimensional projections and applies the resulting estimator to empirical measures.The paper states that this estimator is near-minimax optimal.Source: §2.4 · pp. 4–5

3. MAIN RESULTS

The paper shows that Wasserstein projection pursuit exploits low-dimensional structure to estimate Wasserstein distance at a rate typical of the spike dimension, and can recover the spike under a sufficient-distance condition. Lower bounds establish near-optimality up to logarithmic factors and indicate a computational-statistical gap.

3.1 Estimation of the Wasserstein distance

  • The WPP estimator replaces the plug-in rate for d-dimensional measures with the rate typical of k-dimensional measures, with ambient-dimension dependence only in a lower-order term when p > 1 or k > 2.This result assumes the spiked transport model and transport inequalities for both measures.Source: §3.1 · p. 5

3.2 Estimation of the spike

  • For k = 1, WPP recovers the spike when the Wasserstein distance is sufficiently large, under the stated transport-inequality assumptions.The theorem states the result for p in [1, 2] and Wp(µ(1), µ(2)) ≳ 1.Source: §3.2 · p. 5

3.3 Lower bounds

  • The lower bound makes the plug-in estimator optimal up to logarithmic factors and implies that the first rate term cannot be avoided.The authors note that their lower bound is slightly stronger than Liang’s [58] and holds for all p ≥ 1, but does not match the naive upper bound by logarithmic factors for large d.Source: §3.3 · p. 6
  • Even for a one-dimensional spike, the ambient-dimension dependence in the second rate term cannot be eliminated; sparse spikes are conjectured to mitigate this limitation.The sparse-spike mitigation is a conjecture, not an established result.Source: §3.3 · p. 6

3.4 A computational-statistical gap

  • Under the spiked transport model, statistical-query estimators need exponentially many queries to an oracle with exponential sample-size parameter for inverse-polynomial accuracy, whereas a non-efficient estimator needs only polynomially many samples in d.The WPP estimator achieving the rate is computationally expensive to implement.Source: §3.4 · p. 7

4. LOW-DIMENSIONAL WASSERSTEIN DISTANCES

The k-dimensional Wasserstein distance measures discrepancy through low-dimensional projections. Under the spiked transport model it agrees with the ordinary Wasserstein distance, and under a relaxed model it still captures that distance when the orthogonal components are sufficiently close.

4. LOW-DIMENSIONAL WASSERSTEIN DISTANCES

  • The k-dimensional Wasserstein distance measures discrepancy between low-dimensional projections of two measures.The definition is described as motivated by projection pursuit and was proposed independently by other works [24] [50] [66].Source: §4 · p. 7
  • The k-dimensional Wasserstein distance is a metric and, under the spiked transport model, equals the ordinary Wasserstein distance.The equality is the design property used to relate the projected discrepancy to the full distance.Source: §4 · p. 7
  • In the relaxed spiked model, the orthogonal components may differ, but the k-dimensional Wasserstein distance still captures the true distance when their distributions are sufficiently close.The components on the spike subspace and its orthogonal complement are assumed independent.Source: §4 · p. 8

5. CONCENTRATION

The paper connects transport inequalities to concentration of empirical Wasserstein distances and shows how these properties behave under changes in distance order and low-dimensional projection. It also gives conditions linking transport inequalities to subgaussian concentration.

5. CONCENTRATION

  • For p in [1, 2], a measure satisfies Tp(σ^2) if and only if Wp(µn, µ) is σ^2/n-subgaussian for every n.The equivalence is presented as a concentration result for the Wasserstein distance between a measure and its empirical counterpart.Source: §5 · p. 8
  • If a measure satisfies Tp′(σ^2), it yields good concentration for Wp when p ≤ p′; when p > p′, it still yields a weaker concentration bound.For T1(σ^2), the stated result is nontrivial only for p < 2, while T2(σ^2) gives a result for all finite p.Source: §5 · pp. 8–9
  • For p in [1, 2], a k-dimensional projection of a measure satisfying Tp(σ^2) also satisfies Tp(σ^2).The result follows from the projection map being a contraction.Source: §5 · p. 9
  • A measure satisfies T1(σ^2) exactly when every 1-Lipschitz function of a random variable drawn from it is σ^2-subgaussian.The paper also states that Tp(σ^2) implies σ^2-subgaussianity, while the converse for a σ^2-subgaussian random vector gives T1(Ckσ^2).Source: §5 · p. 9

6. UPPER BOUNDS

Wasserstein Projection Pursuit (WPP) improves Wasserstein-distance estimation under the spiked transport model, with faster convergence than the high-dimensional plug-in rate. The section also considers approximate model adherence and subspace recovery, whose guarantees are limited for higher-dimensional spikes.

6. UPPER BOUNDS

  • Under the spiked transport model, WPP produces a significantly more accurate Wasserstein-distance estimate than the plug-in estimator.Source: §6 · p. 9
  • Under the spiked transport model and the stated T_p′(σ²) condition, the WPP estimate converges faster than n^-1/d.The supplied theorem passage does not include the specific rate expression.Source: §6 · p. 10
  • WPP also provides statistical benefits when the spiked transport model holds only approximately, under the relaxed-model theorem.Source: §6 · p. 10
  • When the distributions are well separated, the recovered subspace is guaranteed only partial alignment; for k > 1, this need not recover the full spike.The text notes that the distributions may differ only along a one-dimensional space, limiting what can be guaranteed from positive Wasserstein distance alone.Source: §6 · p. 12

7. A LOWER BOUND ON ESTIMATING THE WASSERSTEIN DISTANCE

The section establishes a minimax lower bound for estimating Wasserstein distance, showing that the high-dimensional rate is optimal up to logarithmic factors. Its proof reduces the problem to testing total-variation distance under a chi-squared constraint.

7. A LOWER BOUND ON ESTIMATING THE WASSERSTEIN DISTANCE

  • The lower bound makes the rate r_p,d(n) optimal up to logarithmic factors for estimating Wasserstein distance.The theorem applies when d > 2p and the metric space satisfies the stated covering condition.Source: §7 · pp. 12–13
  • The proof reduces Wasserstein-distance estimation to total-variation estimation and uses a refined bound involving both total variation and chi-squared divergence.Source: §7 · p. 12
  • A testing lower bound for distributions near uniformity in chi-squared divergence supplies the reduction's hard instance.The construction compares distributions close to uniform in total variation with alternatives separated from uniform.Source: §7 · pp. 12, 14

8. COMPUTATIONAL-STATISTICAL GAPS FOR THE SPIKED TRANSPORT MODEL

The paper presents statistical-query lower-bound evidence that computationally efficient estimation may not exploit the spiked structure, despite polynomial-sample information-theoretic estimation. The appendix proof of Theorem 4 reduces to distinguishing Gaussian covariance alternatives from a spiked covariance model.

8. COMPUTATIONAL-STATISTICAL GAPS FOR THE SPIKED TRANSPORT MODEL

  • The statistical-query framework allows approximate expectation queries and captures noise-tolerant algorithms, providing the model for the computational lower-bound evidence.Source: §8 · p. 16
  • A VSTAT(2^cd) algorithm requires at least 2^cd queries to estimate the distance to the stated accuracy, suggesting an exponential sample requirement for computationally efficient procedures.The text contrasts this with a polynomial sample requirement information-theoretically.Source: §8 · p. 16

A.1 Proof of Theorem 4

  • Theorem 4's proof reduces to distinguishing a standard Gaussian from a centered Gaussian with a rank-one covariance perturbation.The perturbed measure is described as an O(1)-Lipschitz pushforward when β ≲ 1.Source: §A.1 · pp. 16–17
  • The Gaussian alternatives have Wasserstein separation at least W1, with the one-dimensional comparison bounded below by a quantity proportional to β.The proof invokes Le Cam’s two-point method after the testing reduction.Source: §A.1 · pp. 16–17

A.2 Proof of Proposition 10

The proof of Proposition 10 lower-bounds testing from samples by Poissonizing count data and constructing distributions that match moments while differing in expected absolute deviation from one.

A.2 Proof of Proposition 10

  • The construction uses random variables U and V with matching moments through order L, but different expected absolute deviations from one.They have equal means and bounded support; the text gives E|U − 1| ≤ 12ε and E|V − 1| ≥ 1.Source: §A.2 · p. 17
  • The proof uses count vectors as sufficient statistics and passes from fixed-size samples to a Poissonized testing problem.Under a distribution q, the count vector has a multinomial distribution.Source: §A.2 · p. 17
  • The proof aims to lower-bound the minimax testing risk using Poissonized count-vector distributions.The counts are generated as independent Poisson variables with means determined by the probability vector.Source: §A.2 · pp. 17–18

A.3 Proof of Proposition 11

The proof constructs distributions whose moments match through degree L−1 while satisfying the required support and expectation conditions. It verifies the moment match by expressing polynomial differences in terms of lower-degree moments.

A.3 Proof of Proposition 11

  • The earlier construction gives U and V with P[U = 0] ≤ 6ε and P[V = 0] ≥ 1/4, yielding the required bounds on E|U − 1| and E|V − 1|.The proof then focuses on constructing Y and Y′.Source: §A.3 · p. 19
  • The construction begins with X and X′ matching moments through degree L−1, then rescales them to form Pε and P′ε.These rescaled distributions are used to define Q and Q′.Source: §A.3 · p. 19
  • The constructed distributions Y and Y′ are supported on [1, 16ε^-1L^2] and have equal expectations at most 6.The proof checks these support and expectation conditions before verifying moment matching.Source: §A.3 · p. 19
  • For any polynomial p of degree at most L−1, the construction reduces Ep(Y) − Ep(Y′) to differences of lower-degree moments.The displayed identity includes a term proportional to EY − EY′.Source: §A.3 · p. 20
  • Thus Ep(Y) = Ep(Y′) for every polynomial p of degree at most L−1.Source: §A.3 · p. 20

A.4 Proof of Theorem 12

The proof builds a one-dimensional subgaussian distribution that matches many Gaussian moments yet remains separated in Wasserstein distance, then plants it along a direction in higher dimensions. It uses this construction to establish an exponential statistical-query lower bound.

A.4 Proof of Theorem 12

  • Proposition 12 states that there exists an O(1)-subgaussian distribution A on R agreeing with N(0, 1) on the first 2m−1 moments.Source: §A.4 · p. 20
  • For O(1)-subgaussian distributions agreeing on their first O(m) moments, Rigollet and Weed [72, Corollary 2] give W1(µ, ν) = O(1/√m), establishing tightness of the separation rate.Source: §A.4 · p. 21
  • Planting A in a direction v yields Pv satisfying the spiked transport model, with W1(Pv, N(0, Id)) = Ω(1/√m).The construction adds Gaussian noise orthogonal to v.Source: §A.4 · p. 21
  • The SQ lower bound uses a correlated family whose pairwise χ2 divergence is controlled by the squared inner product of its directions raised to the 2m power.The proof sets ∆ = χ2(A, N(0, 1)) and bounds the divergence by |v · v′|^2m∆.Source: §A.4 · pp. 21–22
  • For m = cd with sufficiently small positive c, any SQ algorithm estimating W1 to accuracy Θ(1/√m) under the spiked transport model requires exp(Ω(d)) queries.The proof obtains this lower bound through a family of distributions indexed by well-separated unit vectors.Source: §A.4 · pp. 21–22

B.1 Additional lemmas

The additional lemmas supply geometric, probabilistic, and coupling tools used by the paper’s proofs. The omitted proofs apply these tools to concentration and Wasserstein-distance arguments.

B.1 Additional lemmas

  • The covering-number bound for Vk(Rd) and the packing lemma provide geometric controls for selecting separated subspaces or directions.Source: §B.1 · pp. 22, 24
  • A centered distribution satisfying T1(σ2) has pth-moment norm bounded on the scale √p, and the proof also derives dimension-dependent moment bounds for subgaussian vectors.The latter follows by reducing to even p and applying Proposition 16 with standard subgaussian moment bounds.Source: §B.1 · p. 22
  • If the k-dimensional Wasserstein distance equals the full Wasserstein distance, an optimal coupling exists whose displacement is supported on a k-dimensional subspace.This is presented as a converse to Proposition 3.Source: §B.1 · p. 22
  • The random-bijection lemma bounds the discrepancy between pushed-forward distributions across partition cells, using the triangle inequality and sampling without replacement.Source: §B.1 · p. 24

B.2 Omitted proofs

  • The omitted proofs use product-measure concentration and Sanov’s theorem to establish Wasserstein concentration results and their converse.The text also notes convergence of the expected empirical Wasserstein distance as sample size grows.Source: §B.2 · pp. 27–28

Related papers

Loading 1909.07513v1…