Hardness of Learning Neural Networks under the Manifold Hypothesis

Summary

It is widely believed that the low-dimensional structure in natural data is the key to the success of modern machine learning methods. Characterizing this structure and designing algorithms that leverage it, and the complementary problem of understanding when learning under this structure is hard, are thus important problems. In this work the authors provide a hardness result for learning data lying on manifolds using a shallow neural network in the statistical query model. This result is based on reductions from learning Boolean functions, by constructing space-filling manifolds that cover exponentially many quadrants of the Boolean cube.

Strengths

The construction of manifolds that are hard to learn is novel, and the paper is clearly written.

Weaknesses

In terms of novelty and impact, I am concerned that it is not particularly surprising that one can construct space-filling manifolds that are hard to learn, while at the same time other highly structured classes of manifolds can be learned easily. In terms of the empirical results, it's unclear to what extent they corroborate the theoretical results. There is no attempt for instance to check empirically whether the scaling of the sample complexities in the hardness result matches the experiment. The novelty of the experiments estimating the intrinsic dimension of standard image datasets is also unclear. One weakness of the hardness results is that they only apply to shallow networks. Note that for data lying on curves, there are results proving that networks of sufficient depth and width can generalize when trained with gradient descent [1]. These results essentially show that when depth is large compared to a scale set by the curvature of the class manifolds and the distance between them, they can be distinguished by a neural network trained in the NTK regime (with polynomial training time and sample complexity). It would be interesting to better understand how these results can be reconciled, and I suspect either shallow depth or the additional noise inherent in SQ access make the setting considered in the submission harder. [1] Wang, Tingran, et al. "Deep networks provably classify data on curves." Advances in neural information processing systems 34 (2021): 28940-28953.

Questions

I'm curious about whether SQ access is crucial for obtaining such hardness results, or whether the authors believe they can be strengthened to the PAC setting. Could the authors comment about whether their results should still hold for deeper networks. I am particularly curious given the results of [1] mentioned above.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations have been addressed.

Summary

The paper establishes bounds on the learning hardness for a class of low-dimensional manifolds in the statistical query (SQ) model. It extends existing hardness results for neural network training in Boolean and Gaussian input models to more general geometries. These theoretical results are validated through synthetic experiments. Additionally, the proposed method offers a framework for studying the geometry of data manifolds.

Strengths

1. The paper is clearly written and easy to read. The authors effectively state their motivations and results before delving into the mathematical details, enhancing the paper's readability. 2. The paper makes theoretical contributions by extending the proofs of hardness in the Statistical Query (SQ) for Boolean and Gaussian input to the geometric setting. This broadens the understanding of the learnability of neural networks beyond traditional data distributions. 3. The theoretical results are validated through experiments, and the paper also provides new inspiration for studying the geometry of data manifolds.

Weaknesses

1. The synthetic experiment itself does not seem convincing enough. The authors only use hypersphere as the input data. It remains unclear whether the results hold for other geometries besides the hypersphere.

Questions

The results appear very similar to those in papers discussing the sample complexity of learning a manifold via a ReLU network. This paper, however, reformulates the problem from a Statistical Query (SQ) perspective. How do the authors differentiate their results from those existing studies of sample (or network) complexity?

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See weaknesses. Overall, this is an interesting paper.

Summary

The present work considers the hardness of learning under the manifold hypothesis, i.e., the identification of low-dimensional structure by reconstructing low-dimensional manifolds from data and how the latter impacts on the computational complexity of learning algorithms. The authors investigate the data geometry in order to derive minimal assumptions that render the learning problem, e.g., for the class of feedforward neural network, efficiently learnable. Hardness results for a class of low-dimensional manifolds are provided in the framework of statistical query models or under cryptographic hardness assumptions. The latter shows that assuming the manifold hypothesis solely is insufficient for guaranteeing learnability and learning is proved hard under input manifolds of bounded curvature. However, given additional assumptions, e.g., on the volume of the manifold can alleviate the fundamental limitations and is proven to ensure learnability. The authors conclude by providing empirical evidence that illustrate the learnability results through computational experiments on neural network training in the learnable and provably hard regimes.

Strengths

To the best of my knowledge, this work is novel and can be described as a valuable contribution to the field of manifold learning opening up new research perspectives. It provides interesting insights and results of a theoretical and empirical nature on the problem of the learnability of neural networks from a data geometry perspective by drawing connections to statistical query and cryptographic settings. The results assumptions are based on intrinsic manifold properties which is another plus. Interesting examples for the learnable and provably hard case increase the value of this work. The submission is clearly written, well organized and shows a complete status which made reviewing an enjoyable task.

Weaknesses

Any of the following concerns can be assumed mediocre and the first two are also discussed transparently. (1) The sampleable approach restricts the class of included manifolds. (2) The presented approach requires prior knowledge about the distributions over the sequence of efficiently sampleable manifolds. This is a disadvantage in real-world data problems and is prone to biases, e.g., when the true unknown manifold is inferred from the data. (3) Only one class, namely feedforward neural networks, is considered. ### Minor - l 115: to to

Questions

- The learnability results are provided with respect to the broad class of feedforward neural networks. Can you provide arguments that open or prevent your approach from analyzing other neural network classes, such as the class of residual or recurrent neural networks? - l. 80: You state that your formal hardness results apply to single-layer networks. Does the hardness result automatically apply to multi-layer networks or is the single-layer regime a necessary restriction? - Does your analysis capture hyperbolic spaces, i.e., $n-$dimensional Riemannian manifold of constant sectional curvature equal to $-1$ since the latter are shown to be adequate for image learning (see Khrulkov et al.: Hyberbolic Image Embeddings, CVPR, 2020)?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are provided regarding real data manifolds that may fall into the heterogeneous regime and those regarding the sampleable manifold approach that restrict the class of included manifolds. However, I would have liked to see an additional discussion – if any – of the limitations imposed by the chosen class of feedforward neural networks.

Summary

The paper relates the sample complexity required for learning a manifold to its curvature – the curvature is characterized by its “reach” that is defined as the minimum distance from a point on the manifold to some point that has multiple nearest neighbors on the manifold. For a manifold in a n-dimensional hypercube they show that if the reach is \omega(sqrt n) then the manifold can be learned with polynomial sample complexity. On the other hand if it is o(sqrt n) then expotentially many samples may be required. This is proved by constructing a space filling curve that has exponential complexity. They obtaining lower bounds under SQ and cryptographic hardness assumptions.

Strengths

The paper presents a nice clean connection between the "worst case" curvature and sample complexity of learning a manifold. There is a tight split of sqrt(n) for the curvature around which the problem becomes hard. It is well written with clearly defined theory that flows smoothly.

Weaknesses

That at high curvature exponentially many samples would be required is not too surprising. The worst case curvature may not be the main determinant of the hardness of learning a manifold – there may be real world manifolds with very high curvature somewhere in the manifold but still learnable with low sample complexity.

Questions

Do you really need the SQ and the cryptographic hardness assumptions for the exponential lower bound? Cant you just get unconditional hardness bounds as with a space filling curve that goes to a large fraction of the quadrants, the number of degrees of freedom is exp(n) -- so number of such functions is exp(exp(n)). So shouldn't automatically the sample complexity be exp(n)? The worst case curvature may not be the main determinant of the hardness of learning a manifold – there may be real world manifolds with very high curvature somewhere in the manifold but still learnable with low sample complexity. For example if you take a V-shaped manifold with the very small angle at the vertex then this has a high curvature. Any thoughts on a tighter characterization of the complexity of learning a manifold? Might there be other simpler ways of lower bounding the number of functions of high curvature for example maybe if you take polynomials of high degree then the number of coefficients could be exponentially many and the curvature would increase with the degree?

Rating

7

Confidence

4

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes they have.

Answer to the rebuttal

Dear authors, thank you for your response and your efforts to address my concerns. I would like to emphasize once again that your results add valuable insights to the field of manifold learning and I hope that this work will be expanded in the near future. The authors do not foresee any major obstacles in extending their work to other classes of manifolds and neural networks, which addresses my main concerns. However, to be fully convinced, I need a more detailed elaboration. For this reason, I maintain my score.