Abstract
In statistics and machine learning, the Wasserstein distance is a powerful tool for comparing probability distributions, yet it is notoriously hindered by the "curse of dimensionality," where the convergence rate of empirical measures slows exponentially as dimensions increase. This paper investigates the impact of Gaussian smoothing on this convergence. We identify a sharp phase transition in the convergence rate determined by the relationship between the smoothing parameter $\sigma$ and the tail-heaviness $K$ of the underlying distribution. We demonstrate that when smoothing is sufficiently large ($\sigma > K$), the curse of dimensionality is bypassed entirely, achieving a dimension-independent parametric rate of $O(1/\sqrt{n})$. Conversely, when $\sigma < K$, the rate slows significantly, revealing fundamental limitations in transportation-information inequalities for Gaussian mixtures.
Introduction
Estimating a probability distribution from a finite set of samples is a foundational task in data science. The empirical distribution $\mathbb{P}_n$, composed of $n$ data points, serves as a natural proxy for the true underlying distribution $\mathbb{P}$. To quantify the accuracy of this approximation, researchers frequently employ the $L_2$-Wasserstein distance ($W_2$), which measures the optimal transport cost required to transform one distribution into another.
Despite its theoretical appeal, the $W_2$ distance suffers from a severe curse of dimensionality: in $d$ dimensions, the expected error typically scales as $n^{-1/d}$. This implies that in high-dimensional spaces, the number of samples required to achieve a reliable estimate grows exponentially with the dimension. Recent work has suggested that "smoothing" these distributions—convolving them with Gaussian noise—can mitigate this effect. This paper provides a rigorous characterization of when and why this smoothing succeeds, establishing the precise thresholds for fast convergence.
The Phase Transition: $K$ vs. $\sigma$
The core contribution of this research is the identification of a critical threshold for the smoothing variance $\sigma^2$ relative to the distribution’s tail parameter $K$. The authors focus on $K$-subgaussian distributions, where tails decay at least as rapidly as a Gaussian with variance $K^2$.
The Parametric Regime ($\sigma > K$)
When the smoothing noise $\sigma$ exceeds the tail parameter $K$, the curse of dimensionality is effectively "cured." In this regime, the squared Wasserstein distance $W_2^2(\mathbb{P}_n * \gamma, \mathbb{P} * \gamma)$ converges at a rate of $O(1/n)$, which corresponds to a $1/\sqrt{n}$ rate for the distance itself. Crucially, this rate is dimension-independent, meaning that with sufficient smoothing, the complexity of the underlying space does not degrade the convergence speed.
The Non-Parametric Regime ($\sigma < K$)
If the smoothing is insufficient ($\sigma < K$), the convergence rate slows down and becomes "non-parametric." For one-dimensional distributions, the authors pinpoint the exact slower rate $\alpha$, defined as: $$\alpha = \frac{(\sigma^2+K^2)^2}{4(\sigma^4+K^4)}$$ In this scenario, $\alpha$ is strictly less than $1/2$, indicating a significant departure from the ideal parametric rate. This regime highlights that smoothing is not a universal panacea; the noise must be calibrated to the specific tail behavior of the data.
Information-Theoretic Insights
The paper further explores the relationship between transport costs and information-theoretic measures, specifically the Kullback-Leibler (KL) divergence. A surprising finding is the divergence in behavior between $W_2$ and KL divergence in the low-noise regime.
For any subgaussian distribution, the KL divergence between smoothed empirical and true measures converges at a nearly parametric rate of $O(\log^d n / n)$. However, when $\sigma < K$, the $W_2$ distance converges much more slowly. This discrepancy proves that Talagrand’s $T_2$-transportation inequality—which traditionally bounds the Wasserstein distance by the KL divergence—must fail for these smoothed measures when the noise is low.
Additionally, these results resolve a long-standing mystery regarding the Log-Sobolev Inequality (LSI) for Gaussian mixtures. The authors prove that for $K > \sigma$, the LSI cannot hold, confirming that previous bounds in the literature regarding the constants of these inequalities were essentially optimal.
Methodology and Hard Examples
To establish these bounds, the authors utilized $\chi^2$-mutual information to link information theory to transport costs and analyzed optimal transport maps between smoothed measures. To prove the lower bounds (the "slow" rates), they constructed "hard" subgaussian distributions, such as sparse mixtures of spikes (Bernoulli-Gaussian mixtures), which are particularly difficult for the $W_2$ metric to resolve under low-noise conditions.
Limitations and Future Directions
While this work provides a definitive answer for Gaussian smoothing, several avenues for future research remain:
- Constant Factors: Although the $1/\sqrt{n}$ rate is dimension-independent for $\sigma > K$, the constant factor associated with this rate may still grow exponentially with $d$. In practice, very high-dimensional problems may still require substantial data.
- Higher-Dimensional Lower Bounds: While the 1D case is fully characterized for $\sigma < K$, the exact optimal rates for non-parametric convergence in higher dimensions ($d > 1$) are yet to be fully determined.
- Alternative Smoothing Kernels: The current study is specific to Gaussian noise. Future work could investigate whether other noise distributions, such as Laplace or heavy-tailed kernels, exhibit similar phase transitions or offer superior smoothing properties.
Conclusion
This paper establishes a sharp boundary for the effectiveness of smoothing in overcoming the curse of dimensionality in Wasserstein distances. By demonstrating that the relationship between noise level and tail behavior dictates the convergence rate, the authors provide a theoretical framework for understanding the limits of empirical distribution estimation in high-dimensional statistics.
Summary updated