# Hardness of Learning Neural Networks under the Manifold Hypothesis

arXiv: https://arxiv.org/abs/2406.01461 · HTML: https://mlsanity.com/paper/2406.01461/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 97 references that are in the map.
- First posted on arXiv 3 Jun 2024.

## Builds on (most cited first, 30 of 44)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [U-Net: Convolutional Networks for Biomedical Image Segmentation](https://mlsanity.com/paper/1505.04597/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Improved Denoising Diffusion Probabilistic Models](https://mlsanity.com/paper/2102.09672/) (2021)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Group Equivariant Convolutional Networks](https://mlsanity.com/paper/1602.07576/) (2016)
- [Geometric deep learning: going beyond Euclidean data](https://mlsanity.com/paper/1611.08097/) (2016)
- [Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions](https://mlsanity.com/paper/2209.11215/) (2022)
- [Deep Learning for Classical Japanese Literature](https://mlsanity.com/paper/1812.01718/) (2018)
- [Lipschitz regularity of deep neural networks: analysis and efficient estimation](https://mlsanity.com/paper/1805.10965/) (2018)
- [Hyperbolic Neural Networks](https://mlsanity.com/paper/1805.09112/) (2018)
- [Explaining Neural Scaling Laws](https://mlsanity.com/paper/2102.06701/) (2021)
- [The Intrinsic Dimension of Images and Its Impact on Learning](https://mlsanity.com/paper/2104.08894/) (2021)
- [Estimating the intrinsic dimension of datasets by a minimal neighborhood information](https://mlsanity.com/paper/1803.06992/) (2018)
- [Convergence of denoising diffusion models under the manifold hypothesis](https://mlsanity.com/paper/2208.05314/) (2022)
- [Score Approximation, Estimation and Distribution Recovery of Diffusion Models on Low-Dimensional Data](https://mlsanity.com/paper/2302.07194/) (2023)
- [A Universal Law of Robustness via Isoperimetry](https://mlsanity.com/paper/2105.12806/) (2021)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [Hyperbolic Deep Neural Networks: A Survey](https://mlsanity.com/paper/2101.04562/) (2021)
- [Score-Based Generative Models Detect Manifolds](https://mlsanity.com/paper/2206.01018/) (2022)
- [A Solvable Model of Neural Scaling Laws](https://mlsanity.com/paper/2210.16859/) (2022)
- [Verifying the Union of Manifolds Hypothesis for Image Data](https://mlsanity.com/paper/2207.02862/) (2022)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [A Neural Scaling Law from the Dimension of the Data Manifold](https://mlsanity.com/paper/2004.10802/) (2020)
- [Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks](https://mlsanity.com/paper/2006.12476/) (2020)
- [Your diffusion model secretly knows the dimension of the data manifold](https://mlsanity.com/paper/2212.12611/) (2022)
- [Deep Networks and the Multiple Manifold Problem](https://mlsanity.com/paper/2008.11245/) (2020)
- [Besov Function Approximation and Binary Classification on Low-Dimensional Manifolds Using Convolutional Residual Networks](https://mlsanity.com/paper/2109.02832/) (2021)
- [Learning Two Layer Rectified Neural Networks in Polynomial Time](https://mlsanity.com/paper/1811.01885/) (2018)

## Built on by (most cited first, 18 of 18)

- [Hyperbolic Deep Learning for Foundation Models: A Survey](https://mlsanity.com/paper/2507.17787/) (2025)
- [Position: Beyond Euclidean -- Foundation Models Should Embrace Non-Euclidean Geometries](https://mlsanity.com/paper/2504.08896/) (2025)
- [Position: A Theory of Deep Learning Must Include Compositional Sparsity](https://mlsanity.com/paper/2507.02550/) (2025)
- [Generative quantum advantage for classical and quantum problems](https://mlsanity.com/paper/2509.09033/) (2025)
- [Semantic Tube Prediction: Beating LLM Data Efficiency with JEPA](https://mlsanity.com/paper/2602.22617/) (2026)
- [DeepWeightFlow: Re-Basined Flow Matching for Generating Neural Network Weights](https://mlsanity.com/paper/2601.05052/) (2026)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Riemannian Metric Matching for Scalable Geometric Modeling of Distributions](https://mlsanity.com/paper/2606.14334/) (2026)
- [Towards Non-Euclidean Foundation Models: Advancing AI Beyond Euclidean Frameworks](https://mlsanity.com/paper/2505.14417/) (2025)
- [Local EGOP for Continuous Index Learning](https://mlsanity.com/paper/2601.07061/) (2026)
- [Surprisingly High Redundancy in Electronic Structure Data Across Materials Explained by Low Intrinsic Dimensionality](https://mlsanity.com/paper/2507.09001/) (2025)
- [Optimizing Multi-Modality Trackers via Significance-Regularized Tuning](https://mlsanity.com/paper/2508.17488/) (2025)
- [HomID : Benchmarking Intrinsic Dimension Estimators on Homogenous Manifolds with Anisotropic Embeddings](https://mlsanity.com/paper/2510.01335/) (2025)
- [Compositional Symmetry as Compression: Lie Pseudogroup Structure in Algorithmic Agents](https://mlsanity.com/paper/2510.10586/) (2025)
- [Why Code, Why Now: An Information-Theoretic Perspective on the Limits of Machine Learning](https://mlsanity.com/paper/2602.13934/) (2026)
- [Beyond Rigid Alignment: Graph Federated Learning via Dual Manifold Calibration](https://mlsanity.com/paper/2605.06260/) (2026)
- [The Data Manifold under the Microscope](https://mlsanity.com/paper/2606.15760/) (2026)
- [Diffeomorphic Optimization](https://mlsanity.com/paper/2607.00947/) (2026)

## Abstract (arXiv)

The manifold hypothesis presumes that high-dimensional data lies on or near a low-dimensional manifold. While the utility of encoding geometric structure has been demonstrated empirically, rigorous analysis of its impact on the learnability of neural networks is largely missing. Several recent results have established hardness results for learning feedforward and equivariant neural networks under i.i.d. Gaussian or uniform Boolean data distributions. In this paper, we investigate the hardness of learning under the manifold hypothesis. We ask which minimal assumptions on the curvature and regularity of the manifold, if any, render the learning problem efficiently learnable. We prove that learning is hard under input manifolds of bounded curvature by extending proofs of hardness in the SQ and cryptographic settings for Boolean data inputs to the geometric setting. On the other hand, we show that additional assumptions on the volume of the data manifold alleviate these fundamental limitations and guarantee learnability via a simple interpolation argument. Notable instances of this regime are manifolds which can be reliably reconstructed via manifold learning. Looking forward, we comment on and empirically explore intermediate regimes of manifolds, which have heterogeneous features commonly found in real world data.