Hardness of Learning Neural Networks under the Manifold Hypothesis

• URL: http://arxiv.org/abs/2406.01461v1
• Date: Mon, 3 Jun 2024 15:50:32 GMT
• Title: Hardness of Learning Neural Networks under the Manifold Hypothesis
• Authors: Bobak T. Kiani, Jason Wang, Melanie Weber,
• Abstract summary: manifold hypothesis presumes that high-dimensional data lies on or near a low-dimensional manifold. We investigate the hardness of learning under the manifold hypothesis. We show that additional assumptions on the volume of the data manifold alleviate these fundamental limitations.
• Score: 3.2635082758250693
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Theoretical Study of Neural Network Expressive Power via Manifold Topology [9.054396245059555]
  A prevalent assumption regarding real-world data is that it lies on or close to a low-dimensional manifold. In this study, we investigate network expressive power in terms of the latent data manifold. We present a size upper bound of ReLU neural networks.
  arXiv  Detail & Related papers  (2024-10-21T22:10:24Z)
• Robust Distributed Learning: Tight Error Bounds and Breakdown Point under Data Heterogeneity [11.2120847961379]
  We consider in this paper a more realistic heterogeneity model, namely (G,B)-gradient dissimilarity, and show that it covers a larger class of learning problems than existing theory. We also prove a new lower bound on the learning error of any distributed learning algorithm.
  arXiv  Detail & Related papers  (2023-09-24T09:29:28Z)
• Gradient-Based Feature Learning under Structured Data [57.76552698981579]
  In the anisotropic setting, the commonly used spherical gradient dynamics may fail to recover the true direction. We show that appropriate weight normalization that is reminiscent of batch normalization can alleviate this issue. In particular, under the spiked model with a suitably large spike, the sample complexity of gradient-based training can be made independent of the information exponent.
  arXiv  Detail & Related papers  (2023-09-07T16:55:50Z)
• On Deep Generative Models for Approximation and Estimation of Distributions on Manifolds [38.311376714689]
  Generative networks can generate high-dimensional complex data from a low-dimensional easy-to-sample distribution. We take such low-dimensional data structures into consideration by assuming that data distributions are supported on a low-dimensional manifold. We show that the Wasserstein-1 loss converges to zero at a fast rate depending on the intrinsic dimension instead of the ambient data dimension.
  arXiv  Detail & Related papers  (2023-02-25T22:34:19Z)
• Effects of Data Geometry in Early Deep Learning [16.967930721746672]
  Deep neural networks can approximate functions on different types of data, from images to graphs, with varied underlying structure. We study how a randomly neural network with piece-wise linear activation splits the data manifold into regions where the neural network behaves as a linear function.
  arXiv  Detail & Related papers  (2022-12-29T17:32:05Z)
• Convolutional Neural Networks on Manifolds: From Graphs and Back [122.06927400759021]
  We propose a manifold neural network (MNN) composed of a bank of manifold convolutional filters and point-wise nonlinearities. To sum up, we focus on the manifold model as the limit of large graphs and construct MNNs, while we can still bring back graph neural networks by the discretization of MNNs.
  arXiv  Detail & Related papers  (2022-10-01T21:17:39Z)
• Data-Efficient Learning via Minimizing Hyperspherical Energy [48.47217827782576]
  This paper considers the problem of data-efficient learning from scratch using a small amount of representative data. We propose a MHE-based active learning (MHEAL) algorithm, and provide comprehensive theoretical guarantees for MHEAL.
  arXiv  Detail & Related papers  (2022-06-30T11:39:12Z)
• Multi-scale Feature Learning Dynamics: Insights for Double Descent [71.91871020059857]
  We study the phenomenon of "double descent" of the generalization error. We find that double descent can be attributed to distinct features being learned at different scales.
  arXiv  Detail & Related papers  (2021-12-06T18:17:08Z)
• Inferring Manifolds From Noisy Data Using Gaussian Processes [17.166283428199634]
  Most existing manifold learning algorithms replace the original data with lower dimensional coordinates. This article proposes a new methodology for addressing these problems, allowing the estimated manifold between fitted data points.
  arXiv  Detail & Related papers  (2021-10-14T15:50:38Z)
• High-dimensional separability for one- and few-shot learning [58.8599521537]
  This work is driven by a practical question, corrections of Artificial Intelligence (AI) errors. Special external devices, correctors, are developed. They should provide quick and non-iterative system fix without modification of a legacy AI system. New multi-correctors of AI systems are presented and illustrated with examples of predicting errors and learning new classes of objects by a deep convolutional neural network.
  arXiv  Detail & Related papers  (2021-06-28T14:58:14Z)
• A neural anisotropic view of underspecification in deep learning [60.119023683371736]
  We show that the way neural networks handle the underspecification of problems is highly dependent on the data representation. Our results highlight that understanding the architectural inductive bias in deep learning is fundamental to address the fairness, robustness, and generalization of these systems.
  arXiv  Detail & Related papers  (2021-04-29T14:31:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.