Testing the Manifold Hypothesis

By Charles Fefferman, Sanjoy K. Mitter, Hariharan Narayanan. 2013

743 citations recorded by the source corpus.

The hypothesis that high dimensional data tend to lie in the vicinity of a low dimensional manifold is the basis of manifold learning. The goal of this paper is to develop an algorithm (with accompanying complexity guarantees) for fitting a manifold to an unknown probability distribution supported in a separable Hilbert space, only using i.i.d samples from that distribution. More precisely, our setting is the following. Suppose that data are drawn independently at random from a probability distribution $P$ supported on the unit ball of a separable Hilbert space $H$. Let $G(d, V, \tau)$ be the set of submanifolds of the unit ball of $H$ whose volume is at most $V$ and reach (which is the supremum of all $r$ such that any point at a distance less than $r$ has a unique nearest point on the manifold) is at least $\tau$. Let $L(M, P)$ denote mean-squared distance of a random point from the probability distribution $P$ to $M$. We obtain an algorithm that tests the manifold hypothesis in the following sense. The algorithm takes i.i.d random samples from $P$ as input, and determines which of the following two is true (at least one must be): (a) There exists $M \in G(d, CV, \frac{\tau}{C})$ such that $L(M, P) \leq C \epsilon.$ (b) There exists no $M \in G(d, V/C, C\tau)$ such that $L(M, P) \leq \frac{\epsilon}{C}.$ The answer is correct with probability at least $1-\delta$.

Subfields: Artificial Intelligence, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/bb1847fbde3d4809a6998c435fad81c782a38a39

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Achieving Robustness in the Wild via Adversarial Mixing With Disentangled Representations (2019, positive): “AdvMix stems from the manifold hypothesis [45].”
On the Privacy Risks of Model Explanations (2019, background): “This is due to an interesting connection between perturbationbased model explanations and the data-manifold hypothesis [17].”
ModelScope Text-to-Video Technical Report (2023, methodology): “To address the second obstacle, methods like LDM [46], LSGM [55] and RDM [23] resorted to manifolds with lower intrinsic dimensionality [10, 65].”
Negative Data Augmentation (2021, background): “According to the manifold hypothesis (Fefferman et al., 2016), natural images lie on low-dimensional manifolds: p data is supported on a low-dimensional manifold of the ambient (pixel) space.”
I2VGen-XL: High-Quality Image-to-Video Synthesis via Cascaded Diffusion Models (2023, methodology): “There are also methods like LDM [35], LSGM [43] and RDM [19] that utilize distribution learning in the latent space to significantly reduce computational overhead and enable the generation of high-resolution image [10,51].”
Diffusion Models: A Comprehensive Survey of Methods and Applications (2022, background): “According to the manifold hypothesis [63], most natural data lies on manifolds with significantly reduced intrinsic dimensionality.”
Self-Supervised Remote Sensing Feature Learning: Learning Paradigms, Challenges, and Future Works (2022, background): “hypothesis [4], that is, the real-world data samples presented in high-dimensional spaces are usually embedded into a lower dimensional manifold in human vision perception, where samples from different categories are naturally clustered.”
Estimating the reach of a manifold (2017, methodology): “A test procedure designed to validate whether data actually comes from a smooth manifold satisfying a condition on the reach was developed in [24].”
The Intrinsic Dimension of Images and Its Impact on Learning (2021, background): “…been conducted clearly supporting the low-dimensional manifold hypothesis for many image datasets (Rud-erman, 1994; Sch ¨ olkopf et al., 1998; Roweis & Saul, 2000; Tenenbaum et al., 2000; Brand, 2003); see also (Fefferman et al., 2016) for principled algorithms on verifying the manifold hypothesis.”
Single-Model Uncertainties for Deep Learning (2018, methodology): “ts, certiﬁcates are applied at the last layer representation ˚(x) of deep models. The rationale behind this choice follows from the manifold hypothesis (Bengio et al., 2013; Alain & Bengio, 2016; Fefferman et al., 2016), which states that natural data lives in low-dimensional manifolds, and deep”
Convergence Guarantees for Response Prediction for Latent Structure Network Time Series (2025, unknown): “High dimensional data, including network data, often admits a low dimensional underlying structure [10], [11], [12].”