Research map / Learning theory and algorithms / Sample complexity
Hardness of Learning Neural Networks under the Manifold Hypothesis
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that bounded-reach (curvature-bounded) data manifolds can still yield SQ and cryptographic hardness for learning single-hidden-layer ReLU networks, while manifolds with bounded volume (efficiently sampleable, e.g. via manifold reconstruction) are learnable by interpolation.
Problem
Whether geometric assumptions on the data manifold (curvature via reach, volume/regularity) make feedforward neural networks efficiently learnable under distribution-specific PAC learning.
Approach
Constructs space-filling curve manifolds with reach O(n^alpha), alpha<0.5, that wrap around exponentially many quadrants of the Boolean cube, transferring SQ and cryptographic hardness for parity-like targets to the geometric setting; conversely, efficiently sampleable (bounded-volume) manifolds admit learnability via epsilon-net interpolation.
Key results
- Learning single-hidden-layer ReLU networks over bounded-reach space-filling manifolds requires Omega(tau^2 2^{n^{Omega(1)}}) SQ queries when reach is O(n^alpha) with alpha<0.5.
- Manifolds with bounded volume (efficiently sampleable) are learnable in poly(n, B, 1/epsilon) time via epsilon-net interpolation.
- Estimated intrinsic dimension of MNIST classes ranges roughly 66 to 120, with FMNIST class 2 estimated at 596.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use hypersphere inputs instead of the Gaussian i.i.d. input distribution | Single hidden-layer neural network training · d-dimensional hypersphere in ambient dimension n | test error | Helped |
| Train on the constructed one-dimensional manifold with reach R=0.5 | Single hidden-layer neural network training on parity targets · Bounded-curvature manifold at large ambient dimension | learnability | Hurt |
| Compare estimated intrinsic dimension across image classes | Score-vector PCA estimate · MNIST, KMNIST, and FMNIST | estimated intrinsic dimension | Mixed |
Surprising findings
- Bounded curvature (reach) alone, despite common assumption, does not suffice for learnability of neural networks.
- Intrinsic dimension estimates vary significantly across classes within the same dataset, suggesting heterogeneous real-world manifolds.
Limitations
- Hardness proven only for single hidden layer networks (L=1); learnability results assume constant depth.
- Reach growing as Theta(sqrt(n)) left as open question.
- Real-world data may not fall in either regime; intrinsic dimension experiments are preliminary and limited to three image datasets.
Experimental setup
Datasets: MNIST KMNIST FMNIST
Benchmarks: MNIST KMNIST FMNIST
Metrics: test error (MSE) estimated intrinsic dimension
Baselines: Gaussian i.i.d. input hardness results MLE intrinsic dimension estimator
Builds on: statistical query lower bounds for neural networks Boolean parity hardness under i.i.d. inputs manifold reconstruction (Isomap guarantees) score-based intrinsic dimension estimation
Closest papers by meaning
- Effects of Data Geometry in Early Deep Learning (NeurIPS 2022 · similarity 0.88)
- Deep Networks and the Multiple Manifold Problem (ICLR 2021 · similarity 0.88)
- Sample complexity and effective dimension for regression on manifolds (NeurIPS 2020 · similarity 0.87)
- Verifying the Union of Manifolds Hypothesis for Image Data (ICLR 2023 · similarity 0.87)
- Approximating Latent Manifolds in Neural Networks via Vanishing Ideals (ICML 2025 · similarity 0.86)
- Building Transformation Layers for Riemannian Neural Networks (NeurIPS 2026 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.