Reproduce “Hardness of Learning Neural Networks under the Manifold Hypothesis” on OpenResearch

About this paper

Bobak T. Kiani, Jason Wang, Melanie Weber

Research from Harvard University shows that while the manifold hypothesis suggests low-dimensional data structures, it does not inherently guarantee efficient learnability for neural networks, with computational hardness persisting for certain bounded-curvature input manifolds. Efficient learning is possible only when data manifolds also satisfy additional geometric criteria like polynomially bounded volume, a finding supported by empirical verification on synthetic and real-world datasets.

Key insights

• The manifold hypothesis alone, which posits low-dimensional data structure, is insufficient to guarantee efficient learnability for neural networks.
• Learning neural networks can remain computationally hard even when data lies on low-dimensional manifolds with bounded curvature, due to their ability to 'space-fill' exponentially large input regions.
• Efficient learnability is only guaranteed when additional geometric constraints are met, such as the manifold being 'efficiently sampleable,' implying its volume is polynomially bounded with respect to the ambient dimension.

Summary by alphaXiv.