Abstract
This paper introduces a novel framework for estimating the intrinsic dimension of high-dimensional data manifolds using Wasserstein distances. By leveraging graph-based metrics to approximate geodesic distances, the authors provide the first non-asymptotic guarantees for dimension estimation. The work demonstrates that the sample complexity of generative models like GANs is governed by the data's intrinsic dimensionality rather than its ambient dimension, offering a theoretical explanation for their success in high-dimensional spaces.
Introduction: The Manifold Hypothesis
In modern machine learning, datasets often reside in high-dimensional ambient spaces, such as the 784-pixel space of MNIST images. However, the Manifold Hypothesis posits that such data actually lies on a much lower-dimensional "surface" or manifold. Estimating this intrinsic dimension ($d$) is vital for manifold learning and hyperparameter tuning. Existing estimators frequently struggle with manifolds that are highly curved or folded, often lacking rigorous theoretical guarantees. This research provides a mathematically grounded estimator that remains efficient and accurate even under complex geometric conditions.
Methodology
The proposed approach utilizes a fundamental property of the Wasserstein distance ($W_1$): the distance between a population distribution and an empirical sample of size $n$ scales at a rate of approximately $n^{-1/d}$.
The authors introduce two primary estimators:
- $d_n$ (Euclidean): Employs standard Euclidean distance metrics.
- $\tilde{d}_n$ (Graph-based): Utilizes a $k$-Nearest Neighbor (kNN) graph to approximate geodesic distance—the distance measured along the manifold's surface.
By comparing two independent samples of sizes $n$ and $\alpha n$, the ratio of their Wasserstein distances allows for the direct calculation of $d$. The graph-based approach is particularly innovative as it handles manifolds with a small reach—areas where distant parts of the manifold are extrinsically close in space, which typically confounds Euclidean-based methods.
Theoretical Insights
A key contribution of this work is the distinction between reach ($\tau$), an extrinsic property of the manifold's embedding, and injectivity radius ($\iota$), an intrinsic property related to curvature. The authors prove that their graph-based estimator $\tilde{d}_n$ remains robust even when the reach is small, provided the injectivity radius is sufficiently large.
Furthermore, this framework provides a theoretical explanation for the success of Generative Adversarial Networks (GANs). The authors establish that GANs converge at a rate of $n^{-1/d}$. This implies that GANs do not suffer from the "curse of dimensionality" associated with the ambient pixel space ($D$), but instead scale according to the much smaller intrinsic dimension ($d$) of the data manifold.
Empirical Results
The effectiveness of the graph-based estimator was demonstrated using the MNIST dataset (specifically the digit '7'). The researchers compared the decay of Wasserstein distances as sample sizes increased for both Euclidean and kNN-based metrics.
As shown in the log-log plots, the graph-based approach yields a significantly cleaner linear trend compared to the Euclidean version. The residuals for the kNN-based estimator are more tightly clustered around zero, indicating a more stable and reliable dimension estimate for practitioners working with real-world, non-linear data.
Conclusion and Future Work
This paper establishes a rigorous foundation for intrinsic dimension estimation with finite-sample guarantees. While the current framework assumes data lies exactly on a manifold, future research aims to address "off-manifold" noise, which currently forces estimators to revert to the ambient dimension $D$. Additionally, while the kNN-based approach is more efficient than alternatives like those based on the Traveling Salesman Problem, optimizing the computational cost for massive datasets remains an area for ongoing development.
Summary updated