TL;DR
This paper introduces new theoretical tools for analyzing the "Sinkhorn divergence," a computationally efficient way to measure differences between probability distributions. The authors derive central limit theorems for this divergence, enabling the development of robust statistical tests for comparing distributions, especially in high-dimensional settings.
What Problem Does This Paper Address?
Comparing probability distributions is a fundamental task in many fields, from machine learning to statistics. Traditional methods like the Wasserstein distance are powerful but computationally expensive, especially for high-dimensional data. Entropy-regularized optimal transport, particularly the Sinkhorn divergence, offers a computationally feasible alternative. However, understanding the statistical properties of this divergence, especially for hypothesis testing, has been an open challenge. This paper addresses this by providing theoretical guarantees for the behavior of the empirical Sinkhorn divergence and its variants, paving the way for reliable statistical inference.
Methods
The core of this paper lies in deriving central limit theorems (CLTs) for the empirical Sinkhorn divergence and its centered version, the "Sinkhorn loss." This involves applying the delta-method, a standard statistical technique for approximating the distribution of a function of random variables. The authors also introduce a bootstrap procedure to estimate the non-asymptotic distributions of these statistics, which is crucial for practical hypothesis testing. They analyze the behavior of these divergences as the regularization parameter $\epsilon$ tends to zero, connecting their work to the unregularized optimal transport case.
Datasets
The paper uses simulated datasets for evaluating the theoretical results and real-world datasets for demonstrating practical applications.
- Simulated Data: Used to illustrate the convergence of the empirical Sinkhorn loss to its asymptotic distributions and to assess the performance of the proposed bootstrap procedure.
- Real Data: A dataset of colored images (Autumn and Winter) is used to test the hypothesis of equal color distributions between seasons and within the Autumn dataset itself. Images are transformed into 3D color histograms.
Key Insights and Ideas
- Sinkhorn Loss for Hypothesis Testing: While the Sinkhorn divergence itself is not ideal for testing equality (it's not zero when distributions are identical), the authors introduce and analyze the "Sinkhorn loss," which does have this desirable property. This makes it a more suitable tool for statistical tests.
- Non-Gaussian Limits Under Null Hypothesis: Interestingly, when testing for the equality of two distributions (the null hypothesis), the asymptotic distribution of the Sinkhorn loss is not Gaussian but a mixture of chi-squared random variables. This is a key theoretical insight.
- Bootstrap for Practical Inference: The proposed bootstrap procedure is shown to be consistent and effective in approximating the non-asymptotic distributions, allowing for the construction of reliable confidence intervals and test statistics in practice.
- Regularization Matters: The choice of the regularization parameter $\epsilon$ influences the behavior of the Sinkhorn divergence and loss. The paper shows how to recover results for unregularized transport as $\epsilon$ goes to zero and discusses the practical implications of regularization for blending information and handling sparse data.
Key Results
- Central Limit Theorems: The paper provides CLTs for the empirical Sinkhorn divergence and Sinkhorn loss for both one-sample and two-sample testing scenarios.
- Asymptotic Distributions: The authors characterize the asymptotic distributions, including the non-Gaussian chi-squared mixture for the Sinkhorn loss under the null hypothesis.
- Bootstrap Consistency: The bootstrap procedure is proven to be consistent for estimating the distributions of the test statistics.
- Empirical Validation: Numerical experiments on simulated data demonstrate the fast convergence of the Sinkhorn loss to its asymptotic distributions and the effectiveness of the bootstrap.
- Real-World Application: The proposed methods are applied to image data, successfully testing for differences in color distributions between seasons and within a dataset, showcasing the practical utility of the Sinkhorn loss for multivariate comparisons.
Limitations and Future Work
- Computational Complexity of Hessian: Computing the Hessian matrix for the Sinkhorn loss, which is crucial for deriving the chi-squared distribution under the null hypothesis, is noted as a "delicate task." The paper leaves the explicit computation of these Hessian eigenvalues for future work.
- Babu Bootstrap Guarantees: While the Babu bootstrap is used in numerical experiments, the authors acknowledge that theoretical guarantees for its application in this specific context are missing and left for future work.
- Multivariate MANOVA: The authors suggest extending the work to analyze variance of multiple and multivariate random measures using Wasserstein barycenters, noting that choosing the regularization parameter $\epsilon$ is a critical issue in this setting.
- More Than Two Samples: Future work could involve extending the methodology to handle more than two samples, using the notion of smoothed Wasserstein barycenters.
Summary updated