Hardness of Learning Neural Networks under the Manifold Hypothesis
Authors: Bobak Kiani
Jason Wang
Melanie Weber
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Manifold hypothesis
Learning theory
Hardness of learning
Neural network hardness
Manifold Learning
Primary area: learning_theory

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.

Hardness of Learning Neural Networks under the Manifold Hypothesis
Bobak T. Kiani*
Jason Wang?
Melanie Weber!
Abstract
The manifold hypothesis presumes that high- sith-diiensional data lies low-dimensional manifold. While the utility of encoding geometric structure has been demonstrated empirically, rigorous analysis of its impact the learnabil- ity of neural networks is largely missing. Several recent results have established hardness results for learning feedforward and equivariant neural networks under 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 in- put manifolds of bounded curvature by extending proofs of hardness in the SQ and cryptographic settings for Boolean data inputs 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 and empirically explore intermediate regimes of manifolds, which have heterogeneous features commonly found in real world data
1 Introduction
High-dimensional data often thought to have low-dimensional structure, which may stem, for instance, from symmetries in the underlying system. This observation has given rise to the manifold hypothesis, which presumes that high-dimensional data lies on or near a low- diweemnnnional manifold.
Empirical studies have confirmed this hypothesis across domains (20 77
37 65). A plethora of
algorithms for geometric data analysis [44, 8 80 21] and, more recently. machine learning (30) seek to leverage such structure. While these methods have shown empirical promise, few formal results on the benefits of encoding geometric structure have been established. Here, we study the impact of the manifold hypothesis the computational complexity of learning algorithms for neural networks. Specifically, we investigate, under which geometric assumptions feedforward neural networks are efficiently learnable.
15
2
The computational hardness of learning shallow, fully-connected neural networks under i.i.d. Gaus- sian data distributions has been established by [36] 26 48 32), who show that the complexity of learning even single hidden layer neural networks grows at least exponentially with the input size. Some of this analysis utilizes the correlational statistical query (CSQ) framework, of which learn ability via gradient decent is a notable instance. Recently, [57] have shown similar hardness results
JJhnn A. Paulson School Engineering and Applied Sciences, Harvard University; e-mail:
hawvard. edu
Harvard College, Harvard University; e-mail: jasonwang1@collee harvard. edu
JJhnn A. Paulson School of Engineering and Applied Sciences, Harvard University; e-mail:
mweberêg, harvard. edu
"Code made at http://///e/eeeeaaooo//////////r compleely
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

for equivariant neural networks, class of geometric architectures that explicitly encode symme- tries. Both lines of work indicate that additional assumptions on the neural network architecture or the data geometry are needed to establish learnability. Here, we focus on the latter.
A separate body of literature investigates nonlinear, low-dimensional structure in data. Approaches for estimating intrinsic dimension [44 63 87 and curvature [1 86 46] from data seek to char- acterize the geometry of low-dimensional manifolds. Manifold Learning aims identify low- dimensional structure by reconstructing low-dimensional manifolds from data. Methods such as Multi-DDmensiona Scaling [22] Isomap [9 or Diffusion Maps [1]] have shown empirical suc- cess in learning low-dimensional data manifolds. For some of these approaches. formal guarantees on their reliability with respect the geometric characteristics and sample size of the data are known [ More generally, the manifold learning problem and its complexity have been formally studied in 4 42 3 However, the impact of data geometry on the complexity of learning neural networks in downstream tasks remains open.
In this paper. we ask: Which assumptions on the data geometry guarantee learnability of neural networks? We show that the manifold hypothesis on its own does not guarantee learnability. In particular, we give hardness results for a class of low-dimensional manifolds in the statistical query (SQ) model or under cryptographic hardness assumptions. Our work follows an established line of proof techniques in the SQ literature 32 48 26), extending hardness results for neural network training in the Boolean and Gaussian input models to more general geometries. We further show that additional assumptions on the volume and curvature of the data manifold alleviate the fundamental limitations and guarantee learnability through a rather simple interpolation argument. In particular, manifolds which can be reliably reconstructed via manifold learning are this regime. We fur- ther discuss geometric regimes in which our results do not directly apply, and in which provable learnability remains an open question. We illustrate our learnability results through computational experiments neural network training in the learnable and provably hard regimes. We further com- plement our theoretical analysis with a brief computational study of the intrinsic dimension of image data manifolds, with the goal of testing the geometric assumptions in our framework.
2 Background
2.1 Basic Notation
We denote scalars, vectors, and matrices as v, v, and V respectively. We consider ambient spaces R" equipped with the usual inner product (, -) and associated Eg norm ||- Submanifolds M C R" considered in this study have intrinsic dimension d S and are compact and connected (unless otherwise stated). The tangent space TpM at point p E M denotes the d-dimensional linear subspace of R. spanned by velocity vectors of smooth curves incident at p. Given a subset S C TR. we denote by d(2,S) inf PES ||= pll the distance of point z to S. We denote Vol, as the d- dimensional volume measure inherited from the d-dimensional Hausdorff measure and denote (r( and (r( as the volume of the d-dimensional ball and d-dimensional sphere of radius respectively. For point p E M in given manifold M, Vol r) denotes the volume of the ball of radius r around the point p with respect to the Riemannian distance metric.
2.2 Learning Setting
We consider the task of learning feedforward neural networks f R. - IR composed of L hidden layers f(() IRds + RRd=-1 taking the form
f(x)= = T ((0) (rūr1) (... (.).))(())))....
(1)
(() = ReLU (W,h) + br.
where v E Rd We E dexede-1 and b Rdde are trainable weights. The input dimension dp is set to the ambient dimension and the output is scalar-valued. Throughout we will consider the setting where the weight entries and hidden widths are bounded by O(poly(n)) When guaranteeing that
a class of networks is learnable, we will assume that the number of layers I. = 0(1) is constant with respect to the input dimension. Our formal hardness results will apply for single hidden layer networks (T. 1).
2

---

We consider learnability in the iistributioonsspcciin probably approximately correct (PAC) setting where the goal to produce an algorithm which can learn a target function given polynomial time and samples (68]
Definition 2.1 (Efficiently PAC Learnable). A concept class consisting of functions c X O' is efficiently PAC-leurmable over distribution DD on X' C R", if there exists an algorithm such that for any e > 0 and > 0, and for any target concept c" C, the algorithm takes at most m = (oooy(//e,))) 1/6, n) samples drawn ii.d. from (æ, e* (x)) with D, and returns function satisfying f c* || == (EEEDl(f(E) c* (x))² I with probability at least 8 in time at (1/e: /e, mostpoly
most poly
m))
Note, that the above is distribution specific instance of PAC learning as we require the algorithm to work only for given distribution and not all distributions. In Section 3.2. we will also show a hard class of functions which is likely not efficiently PAC learnable. Hardness results proven in the restricted statistical query (SQ) setting, a query complexity based model for proving hardness capturing most algorithms in practice [55][8]] [78]. Given joint distribution D on input/output space X x y, any SQ algorithm is composed of a set of queries. Each query takes as input a function g: X [-1, and tolerance parameter 0, and returns value SQ(g. r) in the range:
(( [g(x; y)] SQ(g,7) T.
Gradient based algorithms can be queried by, for example, setting g( y) = - a (NN,(æ+) - y)² to estimate the gradient of neural network NNg with respect to parameter 0 for the MSE loss (constant C' chosen so that outputs of are bounded in [-1, forming a valid query). Hardness is quantified in the number of queries needed learn function c* drawn from function class C.
Manifold smoothness restrictions. To conform to practical settings where input features are nor- malized (e.g. image pixel values in the range [0, 1),, input distributions are assumed to be supported on smooth d-dimensional sub-manifolds M C [0. 1]" of the n-dimensional hypercube. For any given manifold M,, will assume that data distributions DM supported on that manifold have a smooth density f with respect to the volume measure and are appropriately bounded such that
M [(a)] (n)))
Pmax minec M f(x)
We will also place curvature restrictions on the manifold by bounding its reach, a global smoothness quantity introduced by [4]] and commonly studied in the manifold learning community M 3 43 (77. Informally, it is the largest number D, such that any point in ambient space at distance less than D has a unique nearest neighbor in the manifold M. It is defined more formally from descriptions of the medial axis (Figure
Definition 2.2 (Reach from medial axis). Given a closed subset S C R", the medial axis Mc)(S) of S consists of the set of points with no unique nearest neighbor:
Med(S) = {x E R" 3p q E S, 1p - 2 = 1|q - 21| =
(3)
The reach Rch (8) of S is the minimal distance from S to Med(S):
Rch (S) inf
(ist(2.5)
=EMed(S)
Bounds on the reach imply corre- sponding bounds on the radius of cur- vature (related to the geodesic and normal curvature) at any point in the manifold since Rch (M)- > (e) (t)l for any unit-speed geodesic
Figure 1: Example one-dimensional mani- fold and its medial axis. Its reach is given by the minimum distance of the medial axis to the manifold.
Medial Axis
IR + M where in' (t)l = for all e R (3). We will encounter second classical cur- vature notion, Ricci curvature, which local, intrinsic curvature notion that characterizes the volume growth of geodesic balls (see sec. B.1 for more formal definition). Positive lower bounds on the Ricci curvature imply that the manifold has bounded diameter, a fact that we will use below.
3

---

2.3 Related works
Here, we briefly summarize the most relevant prior work our study and reserve Appendix A for a more detailed discussion. Our study lies at the intersection of research in manifold learning complexity and neural network learnability. In manifold learning, various works have analyzed the complexity of learning tasks over input manifolds. In one line of work, estimation of smooth man- ifolds in Hausdorff loss has been shown to reguire sample complexity of O(E 4//2 log(L/e)), which independent of the ambient dimension [4 47 58]; ; later works also provided algorithms that run in time linear in 4 bounds on the complexity of manifold reconstruction in SQ settings. In a separate context, [7] 45 show that the sample complexity for determining whether a dataset is within a class of manifolds of specified intrinsic dimension, curvature, and volume bounds grows exponentially with the intrinsic dimension and polynomially in the reach and volume. [71] also categorizes the sample complexity for binary classification over smooth cuts on a data manifold where smoothness defined by the condition number of the classification boundary of the manifold (a quantity closely related to reach).
38
In a learning setting similar to our work, [3] provide upper and lower
The hardness of learning neural networks has long history that we detail further in Appendix [A] Under the i.i.d. Gaussian input model, superpolynomial [8] and exponential [36] lower bounds for learning single hidden layer networks in CSQ settings have been shown. For uniformly ran- dom Boolean inputs, 32) reduce the problem of learning single hidden layer neural networks to a
cryptographically hard problem, a technique, which we also use in Appendix C.3 They also show how to "Booleanize" Gaussian inputs to show hardness for three hidden layer networks, which was later extended SQ and cryptographic hardness of learning two hidden layer networks in [6).. [57 used similar techniques to give hardness results for equivariant neural networks. To the best of our knowledge, the hardness of learning feedforward neural networks under more general data geome- tries, such as under the manifold hypothesis, has not been studied previously. Various works have found efficient learning algorithms under i.i.d. input assumptions when the weights of the networks are restricted in their rank, condition number, positivity, and other criteria [90] 27 7 (6). We con- sider the generic setting where weight matrices are bounded in width and magnitude by (poly(nn), but otherwise unrestricted.
3 Learnability results
Our main results prove the existence of learnable and hard to learn class of input data manifolds illustrated Figure 2 The learnable setting the class of efficiently sampleable manifolds, which As expected, we find that a simple interpolation argument guarantees lcarnability of neural networks over these manifolds. Below and in Appendix B.3 comment on instances of data geometries commonly assumed in machine learning and data science applications that place manifolds within this regime.
form the basis for algorithms that can provably reconstruct manifolds [9] [8 70 42
The provably hard setting are manifolds without bounds on volume but with bounds on curvature quantified globally by the reach. When the bound on the reach grows no faster than o(vn) (n denoting the input size), we construct input data manifolds that feature curvature no larger than the stated bounds but for which learning neural networks exponentially hard. Our proofs construct curves that cover exponentially many quadrants of the Boolean cube, which allows us to extend classical hardness results for learning Boolean functions expressible by neural networks.
Within the manifold regimes we study, our results are relatively tight with respect to bounds on the reach, since whenever the reach grows as w(vR), such manifolds fall within the first class of efficiently sampleable manifolds. We leave as an open question the learnability of manifolds whose reach grows exactly as ((v7) (see Appendix C.4 for more details). Looking beyond our setting, real-world data manifolds feature heterogeneous properties that may not conform to the global bounds on curvature, intrinsic dimension, etc. that we set our study. Better characterizing these heteregeneous features is first step to extending our learnability results to more realistic settings. We conduct some preliminary empirical analysis in analyzing this heterogeneity in our experiments (Section 4.2

---

(Learnable) Efficiently Sampleable Regime
Figure 2: Learnability of neural networks depends on the regularity and smoothness properties of the input data manifold. In the efficiently sampleable regime corresponding to manifolds which can be ap- proximated well with samples, neural networks are learnable via simple interpolation arguments. In the regime where manifolds are bounded solely by their curvature and intrinsic dimension, we show classes of manifolds that obstruct the learnability of algo- rithms. Real-world data likely lives in an inter- mediate regime with heterogeneous properties (e.g. manifolds with varying intrinsic dimension; see Sec- tion 4.2
Example: Positive Bounded Rioci Curvature Manifold
(Potentially Learnable) Heterogeneous Regime
?
Example: Manifolds with varying intrinsic dimension (e.g. in real world data)
(Provably Hard) Bounded Curvature, Unbounded Volume Regime
Example: Space filling manifold
3.1 Sampleable regime
In the manifold reconstruction literature, the goal is to draw samples from a distribution P (typically supported on a given manifold MM) and find a manifold M' which closely approximates the sam- ple distribution target manifold in some appropriate error metric such the Haussdorf distance [ 28 70 42). Runtime and sample complexity for these algorithms are generally at least linear in the volume of the manifold, polynomial in smoothness parameters such as the reach, and exponential the intrinsic dimension, though the dependence on the ambient dimension can often be removed [42. Manifold reconstruction algorithms offer direct means for learning data from target neural network f as one can apply such algorithms to the graph of the function consisting of points (z, (x)) X' x R. As will show here, guarantees of learning in the manifold recon- struction literature directly imply guarantees for learning neural networks via a simple interpolation argument. However, caution must be taken in assuming this situation holds in practice. For this procedure to be efficient, the volume of the manifold should be at worst polynomial in the intrinsic dimension and not growing significantly with the ambient dimension n. Some empirical evidence suggests that manifolds of real-world data may not be in this regime [6).
Essential to many of the manifold reconstruction algorithms is the requirement that one can effi- ciently cover the manifold with samples 28
43 9 This requirement comes in various technical forms and we frame our results here assuming the ability to form epsilon net with samples.
Definition 3.1 ((e, 8)-net). Given a distribution DM over manifold M, subset S C M of points forms an (e, 5) -net if with probability at least ò over draws æ DM, there exists point x' S where x x' < e.
We denote sequence of manifolds indexed by ambient dimensions efficiently sampleable if for a fixed intrinsic dimension d, one can draw polynomially many samples in n and error c to form an epsilon net over the manifold M.
Definition 3.2 (Efficiently sampleable manifold). Let {M,} denote a sequence of manifolds in ambient dimension n with fixed intrinsic dimension d 0(1). Let (DM..) } be a corresponding sequence of distributions over points on the manifolds. We denote this sequence of manifolds as efficiently sampleable if with at most Ō(poly(n, 1/c)) samples drawn i.i.d. from DM,,, one can form an (c, 8)et of the manifold Mn, for any ö = ((poly(n))
Note that classical manifold learning algorithms typically implicitly assume efficiently sampleable manifolds as they assume that the algorithms run efficiently or have runtimes that depend polyno- mially on the manifold's 's volume Vol(MM (see Example BB& for details). With standard regularity assumptions on the manifold, such volume assumption typically implies that an epsilon net can be formed efficiently with Ö(Vol(M)) samples by a coupon collector argument (see, e.g., Proposi- tion (.5))
Remark 3.3. Given a target function /* with inputs on manifold M C X, we could treat the graph of the function M,- ((x,/"(<<) : x E M) as a manifold in X' x TR. Then, one can apply manifold reconstruction algorithms directly to the graph My,, which lies in an ambient space of
5

---

dimension n + 1. This likely works in practice, though it runs into some technical issues due to discontinuities introduced by ReLU activations. We apply more direct method here.
Proposition 3.4. Let n- n-dimensional inputs be drawn from a sequence of efficiently sampleable man-
ifolds Ma. with intrinsic dimension d = O(1) and distributions 'D Ma over the manifold. Denote Hn. the function class of constant depth ReLU networks on inputs with weights bounded in magnitude by B (pooy(n)) and O(poly (n)) width. Then, one can learn f E Hn. up to error in runtime and sample complexity (ppoy((n, B/)))).
Proof. From the efficiently sampleable property of the manifold, we form an (c.8))-nt using (poly(nn, 1/e)) many samples where for all but a ò-fraction of the manifold any point is within é' of a given point within the net. Any network of L layers and O(poly(n)) (n)) bounded width and weight magnitude has the Lipschitz property that 992
(x) - (x'')l s 1 x'|
[W 12
(5)
(=1
L
x'1)
W
(8)
F
S O n n1) a'1: ll.
where B' = (poolynn, B)) is a bound on the Frobenius norm of the weight matrices. Therefore, interpolate the value of f for any x E M,, from sample by setting é' = O(eB'-In-1) For the d-fraction that is not in this net, note that [f(x)) S ((poly(n)) for all æ in the hypercube so setting 5 of a=) -1) will guarantee that the contribution from these points decays. Finally, since L = O() and B (p)ly(nn) by assumption, we have the resulting polynomial complexity. Li
Restrictions the curvature convexity properties of a manifold often render the manifold efficiently sampleable. To illustrate that many manifolds implicitly fall within the regime of effi- ciently sampleable manifolds, we give an example below. Additional examples can be found in Ap- pendix B.3
Proposition 3.5 (Bounded Ricci curvature (Isoperimetric setting, see 52
17 for motivation) ). The
set of distributions P a over complete manifolds with bounded Ricci curvature Ric (M) 2 (d-1)K for a constant K are efficiently sampleable.
Proof. The bound on the Ricci curvature guarantees that the diameter of the manifold is at most 2T/ /VK K and the manifold is contained within a d-dimensional ball of radius 1/vK [69 (see also Theorem 6.3.3 of 75)). Thus, we can form an (e, 5) -ne over the manifold A by inducing from an c-cover on the ball of radius 1/VK (see Definition B.1 for definition). To achieve an c-cover of such ball in d dimensions, suffices have N. O(1/e4) points (see, e.g., Lemma 5.2 of (9I)). We denote the balls in the cover as bi...., bN. Let T denote sampling ratio where form the (e.t)-net. By coupon-collector argument (see Lemma B.5). T -2 samples suffices to guarantee with high probability that any ball b, with probability at least PM (b,) 2 т has a sample within it. 8 then at most the probability that randomly drawn sample falls within ball b, with probability (b( < r. Therefore,
we will take
((poly(n) (n)) samples
Σ
(M((b)= S N.T.
(6)
Thus, setting 5/N, suffices achieve 8 R(poly(n)-1)
We remark that the efficiently sampleable setting does not necessarily require that the manifold be fully connected. In fact, it is straightforward to extend proofs of learnability such as in Proposi- tion 3.5 to settings where there are multiple such disconnected manifolds as long as the number of disconnected components does not grow superpolynomially n.
'Here, the factor (n- - 1) accounts for the standard scaling of the Ricci curvature for sphere of radius I/VK which has Ricci curvature (n 1)K.

---

3.2 Hard regime with bounded curvature
The learnability of the networks in the manifold learning setting relied crucially on the fact that such settings implicitly place bounds on the volume of such manifolds. Here, we lift that restriction and consider a setting where manifolds are smooth and bounded only in their curvature and intrinsic dimension. More formally, we consider studying inputs drawn from manifolds with bounded reach (see Definition 2.2).
In this section, we construct a sequence of manifolds {Mr} with sufficiently bounded reach that are exponentially hard to learn the SQ model. These manifolds resemble space filling curves which wrap around exponentially many quadrants of the Boolean cube (see Appendix CC.I). Given a bound on the reach Rch (Mn)) = O(n") for a < 0.5, the space filling curve wraps around 2 = 2n quadrants allowing one to extend standard hardness results for learning Boolean functions data supported on this manifold.
Theorem 3.6. Let D.M, denote the uniform distribution over manifolds Mn constructed Defini- tion C.4 where Rch (Mn)) On²) for a < 0.5. Any SQ algorithm A capable of learning the class of linear width single hidden layer ReLU neural networks under this sequence of distributions up to mean squared error sufficiently small (e/8 suffices) with queries of tolerance T must use at least (2(7 22)0)))))) queries.
Proof sketch. We first form manifolds conforming to the stated bounds the reach and intrinsic dimension while also "looping" around exponentially many quadrants of the hypercube. This is done by forming space-filling curves whose paths follow the indexing of Gray code (51). Inputs on this manifold are real-valued, but by carefully selecting a portion of the input dimensions, we obtain inputs that with high probability are approximately distributed as uniform over Boolean inputs (0, 1 1) We then extend previous proofs of the hardness of learning networks approximating parity functions under i.i.d. Boolean inputs proven in 32 26 proofs.
to our setting. See Appendix C for complete
Remark 3.7. In Theorem C.12 we show an equivalent proof hardness in the cryptographic setting
following the techniques in 32) Namely, in Appendix C.3 we show that the class of functions in Theorem 3.6 is also hard to learn conditional on cryptographic assumptions related to the hardness of learning a class of pseudorandom functions.
The above result is relatively tight with respect the bound on the reach. Namely, whenever the reach Rch (M₂) = ((n") is growing faster than yn, one can show that the volume of such mani- folds is most (poly(n)) and fitting within the regime of efficiently sampleable manifolds studied in the previous subsection.
Proposition 3.8. Given a sequence of manifolds (M,) 1 of intrinsic dimension d (fixed and indepen- dent of r)) and reach bounded by Rch (M.)) = w(n ), the volume of the manifolds grows at most Vola(Mn) = (n)))
We refer the reader to Appendix C.4 for further details and formal proofs of this tightness.
4 Experiments
4.1 Empirical verification of main findings
To verify that neural networks are learnable in the sampleable regime (Section 3.1 and hard to learn in the bounded curvature regime (Section 3.2). we train neural networks over input data manifolds taken from these regimes to confirm the formal theoretical results. We consider target networks, which are single hidden layer neural networks of O(n) width and train overparameterized neural networks of larger width. For the sampleable regime, we draw inputs from d-dimensional hy- persphere supported over d orthogonal dimensions in the ne-dimensional ambient space. This is an instance of complete manifold of bounded curvature as in Proposition 3.5 For the hard to learn regime, we draw inputs from the 1 1-dimensional manifold constructed in Appendix C. with reach R 0.5. Target functions in this hard regime correspond to the parity functions described in our proof's in Appendix C
7

---

ambient dim. (n)
20
0.8
50
Test MSE
Telt MSB
ambient dim. (n)
0.6
0.4
0.4
0.2
0.0
0.0
20
40
60
80
100
0
5000
10000
15000
Epoch
Step
(a) Leammblee Setting
(b) Hard to Learn Setting
Figure 3: (a) Learning is successful when inputs drawn from d 10 intrinsic dimensional
hypersphere living in ambient space of dimension n an instance of the bounded positive curvature model in Proposition 3.5 Target functions hard to learn functions in the Gaussian i.i.d. input model [36], which are no longer hard to learn in the input distribution considered here. (b) When the ambient dimension large, learning algorithm struggles to learn a single hidden layer neural network drawn from the class of functions in the setting of Theorem 3.6 where the input data manifold has intrinsic dimension
single hidden layer networks taken from the class of
and reach R = 0.5. The network trained to learn this target function is over- weer-paamettriieed with respect to the target. Data aggregated over five random realizations.
The results in Figure 3 empirically confirm main findings. When inputs are drawn from the d-dimensional hypersphere (Figure Bab. the trained neural network achieves low test error with a fixed training set of size 1000 for all n. Here, target functions drawn from those in (36) who provided a class of hard to learn functions in the i.i.d. Gaussian input model. Once the input model changed the d-dimensional hypersphere, this class of functions is no longer hard to learn (see Appendix
E for similar results over random targets).
In contrast, when inputs drawn from the hard to learn manifold (Figure 3b), learning is only possible when the ambient dimension is small. Here, target functions are randomly chosen parity functions over the inputs (see Appendix E At each step of training. with a fresh batch of i.i.d. samples. In Figure g we replicate these results when training networks overparameterized in depth (i.e. three hidden layers opposed to one) as well. We refer the reader to Appendix E for further details.
provide the algorithm
Empirical study of geometry of data manifolds
We empirically investigate the intrinsic dimension of real-world data manifolds as first step towards testing the manifold regularity assumptions our framework on real data. Largely, our results cor- roborate findings in other works highlighting the heterogeneous nature of real-world data manifolds
87 T6.
Experimental Setup. We estimate intrinsic dimension using samples generated by a diffusion model, closely following the approach of [87]. The use of a diffusion model allows us to generate arbitrarily dense samples in neighborhood of given point from the data manifold. Given these samples, we perform PCA on the collection of score vectors {s:} of the diffusion model at each of these samples, which point towards the direction of de-noising and hence towards the manifold itself. Estimating the rank of such a collection of score vectors recovers an estimate of the normal and intrinsic dimensions. We defer detailed description of our approach, its implementation, and hyperparameter choices to Appendix E.1 E.
Data set
#0
#1
#2
#3
#4
#5
#6
#8
#9
MNIST (28 x 28)
102
66
120
109
73
101
109
72
114
104
KMNIST (28 28)
180
199
134
169
135
128
149
191
205
199
FMNIST (28 x 28)
429
177
596
275
225
233
312
125
201
418
Table 1: Estimated intrinsic dimension shown for each of the ten classes in MNIST, KMNIST, FMNIST.

---

Pract
130
88
Figure 4: Sample spectrum of the singular values of a collection of score vectors given by trained diffusion model pointing towards the direction de-noising an image.
Results. Estimated intrinsic dimensions for three image data manifolds are given in Table Score spectra for the three manifolds are shown in Figure 4 confirming that the score vectors do indeed cluster in linear subspace spanning the normal dimensions. Furthermore, our approach gives sim- ilar estimate for the intrinsic dimension of MNIST as reported in [87]. To the best of our knowledge, FMNIST and KMNIST were not investigated prior work. Comparing estimated intrinsic dimen- sion across classes indicates significant heterogeneity of the real data manifolds, which would place them in the potentially learnable regime our proposed framework. This may seem surprising as images drawn from different classes can have different properties and symmetries. However, it corroborates our initial hypothesis that real-world data may not conform to global bounds on intrin- sic dimension. Furthermore, we find that upon re-sizing the images to a smaller scale, the ambient dimension decreases faster in comparison to the intrinsic dimension for some datasets (see Table] 3 in Appendix) lending some limited evidence to the underlying assumption in the manifold hypothe- sis that bounds on intrinsic dimension do not grow in tandem with ambient dimension. Additional experimental results and further discussion can be found in Appendix E.3
5 Discussion
In this paper we have investigated whether regularity assumptions on the data geometry can ren- der feedforward neural networks efficiently learnable. We show that bounding curvature in low- dimensional data manifolds, a common assumption in high-ddmenssioal learning, does not suffice to alleviate the fundamental hardness of learning such architectures. However, establish learning guarantees under geometric assumptions common in the manifold reconstruction literature that al- low manifolds to be efficiently covered with (ppoly(n)) samples. Our results contribute a recent body of literature that seeks to establish learnability guarantees and provable hardness results for 48 90).
neural network architectures 112
26 36
57
While our results establish guarantees for a wide range of data manifolds, including manifolds that can be provably reconstructed via manifold learning, there are geometric regimes in which the ques- tion of learnability remains open. We hypothesize that the heterogeneity of real data manifolds might place them in this more uncertain regime and find some evidence of this heterogeneity in our experiments. further theoretical and empirical investigation of this class of data manifolds is an important direction for future work.
The experimental results on estimating the intrinsic dimension of data manifolds are merely a start- ing point for understanding realistic assumption on data geometry in machine learning architectures. In future work we hope to look at a wider range of synthetic and real data sets, as well as a wider range of geometric characteristics and estimation techniques.
Broadly, our results indicate that assumptions beyond global smoothness of data manifolds are needed to guarantee learnability of neural networks in real-world settings. To circumvent hard- ness results, the particular form of the networks and their weights can be changed for example incorporate symmetries via equivariant architectures or place restrictions on weights such as bounds on condition number or rank [27 Furthermore, some datasets live a discrete input space (e.g., language data) which does not conform directly to Riemannian analysis. In these settings, adapta- tions of the manifold hypothesis to analysis via graphs and other combinatorial objects presents an interesting direction for future work [8]] 15).

---

Acknowledgement
The authors thank Andrew Cheng and Adityanarayanan Radhakrishnan for insightful discussions. BTK and MW were supported by the Harvard Data Science Initiative Competitive Research Fund and NSF award 21 2112085. JW acknowledges support from the Harvard College Research Program (HCRP).
References
[1] E. Aamari, J. Kim, F. Chazal, B. Michel, A. Rinaldo, and L. Wasserman. Estimating the reach of a manifold. 2019.
[2] E. Aamari and A. Knop. Statistical query complexity of manifold estimation. In Proceedings of the 53rd Annual ACM SIGACT Symposium Theory of Computing, pages 116 122, 2021.
[3] E. Aamari and A. Knop. Adversarial manifold estimation. Foundations of Computational Mathematics, pages 1-97, 2022.
[4] E. Aamari and C. Levrard. Stability and minimax optimality of tangential delaunay complexes for manifold reconstruction. Discrete & Computational Geometry, 59:923-9711 2018.
[5] E. Abbe, E. B. Adsera, and T. Misiakiewicz. Sgd learning on neural networks: eapp complexity and saddle-to-sadee dynamies. In The Thirty Sixth Annual Conference on Learning Theory, pages 2552-2623. PMLR, 2023.
[6] Y. Bahri, E. Dyer, J. Kaplan, J. Lee, and U. Sharma. Explaining neural scaling laws. arXiv preprint arXiv:2102.06701, 2021.
[7] A. Bakshi, R. Jayaram, and D. P. Woodruff. Learning two layer rectified neural networks in polynomial time. In Conference on Learning Theory, pages 195-268. PMLR, 2019.
[8] M. Belkin and Niyogi. Laplacian eigenmaps for dimensionality reduction and data repre- sentation. Neural computation, 15(6):1333-1396 2003.
[9] M. Bernstein, V. De Silva, J. C. Langford, and B. Tenenbaum. Graph approximations geodesics on embedded manifolds. Technical report, Citeseer, 2000.
[10] R. L. Bishop. A relation between volume, mean curvature and diameter. In Euclidean Quantum Gravity, pages 161-161. World Scientific, 1964.
[11] A. Blum, M. Furst, J. Jackson, M. Kearns, Y. Mansour, and Rudich. Weakly learning dnf and characterizing statistical query learning using fourier analysis. In Proceedings of the sietty-sixth annual ACM symposium on Theory of computing, pages 253-262, 1994.
[12] A. Blum and R. Rivest. Training a 3-node neural network is np-complete. Advances in neural information processing systems, 1, 1988.
[13] A. Bogdanov and A. Rosen. Pseudorandom functions: Foundations of Cryptography: Dedicated to Oded Goldreich, pages 79-158. Springer, 2017.
Three decades later. In Tutorials on the
[14] J.-D. Boissonnat and A. Ghosh. Manifold reconstruction using tangential delaunay complexes. In Proceedings of the twenty-sixth annual symposium on Computational geometry, pages 324- 333, 2010.
[15] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learn- ing: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42,22 2017.
[16] B. C. Brown, A. L.. Caterini, B. L.. Ross, J. C. Cresswell, and G. Loaiza-Ganem. Verifying the union of manifolds hypothesis for image data. In The Eleventh International Conference on Learning Representations, 2022.
[17] Bubeck and M. Sellke. A universal law of robustness via isoperimetry. Journal of the ACM, 70(2):1-18, 2023.
10

---

[18] S. Buchanan, D. Gilboa, and J. Wright. Deep networks and the multiple manifold problem. arXiv preprint arXiv:2008. 11245, 2020.
[19] Camastra and A. Vinciarelli. Estimating the intrinsic dimension of data with a fractal-based method. IEEE Transactions pattern analysis and machine intelligence, 24(10):1404-144 2002.
[20] G. Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255- 308, 2009.
[21] L. Cayton et al. Algorithms for manifold learning. eScholarship, University of California, 2008.
[22] M. Chen, K. Huang, T. Zhao, and M. Wang. Score approximation, estimation and distribu- tion recovery of diffusion models on low-dimensional data. arXiv preprint arXiv:2302.0711 194,, 2023.
[23] R. T. Chen and Y. Lipman. Riemannian flow matching on general geometries. arXiv preprint arXiv:2302.03661 2023.
[24] S. Chen, S. Chewi, J. Li, Y. Li, Salim, and Zhang. Sampling is as easy as learning the score:
theory for diffusion models with minimal data assumptions. In The Eleventh Interna- tional Conference on Learning Representations, 2023.
[25] S. Chen, Z. Dou, S. Goel, A. R. Klivans, and R. Meka. Learning narrow one-hidden-layer relu networks. arXiv preprint arXiv:2304.10524 2023.
[26] S. Chen, A. Gollakota, Klivans, and R. Meka. Hardness of noise-free learning for two- hidden-layer neural networks. Advances in Neural Information Processing Systems, 35:10709- 10724. 2022.
[27] S. Chen and S. Narayanan. A faster and simpler algorithm for learning shallow networks. arXiv preprint arXiv:2307.12490 2023.
[28] S.-W. Cheng, T. K. Dey, and A. Ramos. Manifold reconstruction from point samples. In SODA, volume 5, pages 1018 1027, 2005.
[29] T. Clanuwat, M. Bober-Irizar, A. Kitamoto, A. Lamb, K. Yamamoto, and D. Ha. Deep learning for classical japanese literature, 2018.
[30] T. Cohen and M. Welling. Group equivariant convolutional networks. In ICML, 2016.
[31] R. R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5-33) -00, 2006. Special Issue: Diffusion Maps and Wavelets.
[32] A. Daniely and G. Vardi. From local pseudorandom generators to hardness of learning. In Conference Learning Theory, pages 1358-1394. PMLR, 2021.
[33] Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 537-546, 2008.
[34] V. De Bortoli. Convergence of denoising diffusion models under the manifold hypothesis. arXiv preprint arXiv:2208.05314 2022.
[35] L. Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 141-114 2012.
[36] I. Diakonikolas, D. M. Kane, V. Kontonis, and N. Zarifis. Algorithms and sq lower bounds for pac learning one-hidden-layer relu networks. Conference on Learning Theory, pages 1514-1539. PMLR, 2020.
[37] J. DiCarlo, D. Zoccolan, and N. C. Rust. How does the brain solve visual object recognition? Newrn, 73(3):415-44 434, 2012.

---

[38] V. Divol. Minimax adaptive estimation in manifold inference. Electronic Journal of Statistics, 15(2):5888 -8985923. 2021.
[39] P. Erdós and A. Rényi. On classical problem of probability theory. Magyar Tud. Akad. Mat. Kistaóó Int. Közl, 6(1):215-220, 1961.
[40] E. Facco, M. d' d'Errico, A. Rodriguez, and A. Laio. Estimating the intrinsic dimension of datasets by minimal neighborhood information. Scientific reports. 7(1):12140, 2017.
[41] H. Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418 491, 1959.
[42] C. Fefferman, S. Ivanov, Y. Kurylev, M. Lassas, and H. Narayanan. Fitting a putative manifold to noisy data. In Conference On Learning Theory, pages 688-720 PMLR, 2018.
[43] C. Fefferman, Mitter, and H. Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, 29(4))983-1049 2016.
[44] K. Fukunaga and Olsen. An algorithm for finding intrinsic dimensionality of data. IEEE Transactions computers, 100(2):176-183) 1971.
[45] O. Ganea, G. Bécigneul, and T. Hofmann. Hyperbolic neural networks. Advances in neural information processing systems, 31, 2018.
[46] N. Garcia Trillos and M. Weber. Continuum limits of Ollivier's Ricci curvature on data clouds: pointwise consistency and global lower bounds. arXiv preprint arXiv:230.002378, 2023.
[47] C. R. Genovese, M. Perone Pacifico, V. Isabella, L. Wasserman, et al. Minimax manifold estimation. Journal of machine learning research, 13:1263-129) 2012.
[48] S. Goel, A. Gollakota, Z. Jin, S. Karmalkar, and A. Klivans. Superpolynomial lower bounds for learning one-layer neural networks using gradient descent. In International Conference on Machine Learning, pages 3587-3596. PMLR, 2020.
[49] O. Goldreich. Candidate one-way functions based on expander graphs. Studies in Complex- ity and Cryptography. Miscellanea the Interplay between Randomness and Computation: Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufmmnn, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman, pages 76-87,25 20,-8,2011 2011.
[50] V. V. Goncharov and G. E. Ivanov. Strong and weak convexity of closed sets in a hilbert space. Operations Research, Engineering, and Cyber Security: Trends in Applied Mathematccs and Technology, pages 259-297, 2017.
[51] Gray. Pulse code communication. United States Patent Number 2632058, 1953.
[52] M. Gromov. Isoperimetric inequalities in riemannian manifolds. Asymptotic Theory of Finite Dimensional Spaces, 1200:1 14-129, 1986.
[53] J. S. Judd. Learning in networks is hard. In Proc. of 1st International Conference on Neural Networks, San Diego California, June 1987. IEEE, 1987.
[54] N. Kambhatla and T. Leen. Fast non-linear dimension reduction. Advances in neural informa- tion processing systems, 1993.
[55] M. Kearns. Efficient noise-ton noise-tolerant learning from statistical queries. Journal of the ACM (JACM), 4506)983-10066 1998.
[56] B. Kégl. Intrinsic dimension estimation using packing numbers. Advances in neural informa- tion processing systems, 15, 2002.
[57] B. Kiani, Le, Lawrence, S. Jegelka, and M. Weber. On the hardness of learning under symmetries. In The Twelfth International Conference Learning Representations, 2024.
12

---

[58] A. K. Kim and H. H. Zhou. Tight minimax rates for manifold estimation under hausdorff loss. 2015.
[59] T. N. Kipf and M. Welling, semi-supevviee classification with graph convolutional networks. arXiv preprint arXiv: wet.:..0990000 2016.
[60] D. E. Knuth. The art of computer programming, volume 3. Pearson Education, 1997.
[61] M. Kossaczká and Vybíral. Entropy numbers of finite-dimensional embeddings. Exposi- liones Mathematicae, 38(3):319-336, 2020.
[62] J. B. Kruskal. Multidimensionall scaling by optimizing goodness of fit to nonmetric hypoth- esis. Psychometrika, 19(1):1-27, 1964.
[63] E. Levina and P. Bickel. Maximum likelihood estimation of intrinsic dimension. Advances in neural information processing systems, 17, 2004.
[64] H. Liu, M. Chen, T. Zhao, and W. Liao. Besov function approximation and binary classifi- cation on oow-dimeniiona manifolds using convolutional residual networks. In International Conference Machine Learning, pages 6780. PMLR, 2021.
[65] Y. Ma and Y. Fu. Manifold learning theory and applications. CRC press, 2011.
[66] A. Maloney, D. A. Roberts, and J. Sully. A solvable model of neural scaling laws. arXiv preprint arXiv:2210. 16859, 2022.
[67] T. Minka. Automatic choice of dimensionality for pea. Advances in neural information pro- cessing systems, 13, 2000.
[68] M. Mohri, A. Rostamizadeh, and A. Talwalkar. Foundations of machine learning. MIT press, 2018.
[69] S. B. Myers. Riemannian manifolds with positive mean curvature. 1941.
[70] H. Narayanan and S. Mitter. Sample complexity of testing the manifold hypothesis. Advances in neural information processing systems, 23, 2010.
[71] H. Narayanan and P. Niyogi. On the sample complexity of learning smooth manifold. In COLT, 2009.
[72] A. Q. Nichol and P. Dhariwal. Improved denoising diffusion probabilistic models. In Interna- tional Conference on Machine Learning, pages 8162-8171. PMLR, 2021.
[73] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, F. Yang, Z. Vetoto, M. Raison, A. Te- jani, S. Chilamkurthy, B. Steiner, I.. Fang. J. Bai, and S. Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024-8035. 2019.
[74] W. Peng. T. Varanka, A. Mostafa, H. Shi, and G. Zhao. Hyperbolic deep neural networks: A survey. IEEE Transactions on pattern analysis and machine intelligence, 14(12):10023-1100) 2021.
[75] P. Petersen.
Riemannian geometry, volume 171. Springer, 2006.
[76] J. Pidstrigach. Score-based generative models detect manifolds. Advances in Neural Informa- tion Processing Systems, 35:35852-35865, 2022.
[77] Pope, C. Zhu, A. Abdelkader, M. Goldblum, and T. Goldstein. The intrinsic dimension of images and its impact on learning, arXiv preprint arXiv:2104.0889) 2021.
[78] I. Reyzin. Statistical queries and statistical algorithms: Foundations and applications. arXiv preprint arXiv:2004.00557, 2020.
13

---

[79] O. Ronneberger, P. Fischer, and T. Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assisted Intervention- MICCAI 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part 18, pages 234-241. Springer, 2015.
[80] S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323- 2326,, 2000.
[81] P. Rubin-Delanchy. Manifold structure in graph embeddings. Advances in neural information processing systems, 33: 1687-11699, 2020.
[82] D. Scieur, I. Kerdreux, A. d' Aspremont, S. Pokutta, et al. Strong convexity of sets in rieman- nian manifolds. arXiv e-prints, pages arXiv-2312, 2023.
[83] U. Sharma and J. Kaplan. A neural scaling law from the dimension of the data manifold. arXiv preprint arXiv:2004. 10802, 2020.
[84] J. Skilling. Programming the hilbert curve. In AIP Conference Proceedings, volume 707, pages 381-387. American Institute Physics, 2004.
[85] L. Song, S. Vempala, J. Wilmes, and B. Xie. On the complexity of learning neural networks. Advances in neural information processing systems, 30, 2017.
[86] D. Sritharan, S. Wang, and S. Hormoz. Computing the riemannian curvature of image patch and single-cell rna sequencing data manifolds using extrinsic differential geometry. Proceed- ings of the National Academy of Sciences, 11829)::2100473118, 2021.
[87] Stanezuk, G. Batzolis, T. Deveney, and C.-B. Schönlieb. Your diffusion model secretly knows the dimension of the data manifold. arXiv preprint 1rX1v:2212.12611,,00
[88] B. Tahmasebi and S. Jegelka. The exact sample complexity gain from invariances for kernel regression, 2023.
[89] J. B. Tenenbaum, V. d. Silva, and C. Langford. A global geometric framework for nonlinear dimensionality reduction. science, 29065500):2319-2333, 2000.
[90] S. Vempala and J. Wilmes. Gradient descent for one-hidden-layer neural networks: Polynomial convergence and sq lower bounds. In Conference on Learning Theory, pages 3115-3117. PMLR, 2019.
[91] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint 1rXiv:1011.3027, 2010.
[92] A. Virmaux and K. Scaman. Lipschitz Lipschitzrreuulariyy of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[93] M. Weber, M. Zaheer, A. S. Rawat, A. Menon, and S. Kumar. Robust large-margin learning in hyperbolic space. In Advances in Neural Information Processing Systems 34, 2020.
[94] N. Whiteley, A. Gray, and P. Rubin- -eeain--eench. Statistical exploration of the manifold hypothe- sis, 2023.
[95] H. Xiao, K. Rasul, and R. Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint 1oXiv:170.007744 2017.
[96] M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. Smola. Deep sets. Advances in neural information processing systems, 30, 2017.
14

---

A Extended Related Works
Hardness of learning neural networks. The first results showing the hardness of learning neural networks are those of [53] [2] proving that proper learning of neural networks is an NP complete task. As mentioned earlier, a number of works prove hardness results for learning feedforward
ReLU networks under the Gaussian i.i.d. data model [48
36
85
32 Many of these works 26
Similar hardness results, also in the SQ model, have also been shown for classes of symmetric or equivariant neural networks [57]. These results show that additional assumptions on the network class are needed to prove learnability results. Such assumptions which lead to provable learnability include those on the condition number or positivity of weights 7 33), polynomial approximation guarantees [90], or bounds on width 17 (5]. When the target is not necessarily a feedforward network, [3] show that single hidden layer ReLU networks can efficiently learn functions with low so-called leap complexity categorized by the growth in the degrees of polynomials over a linear subspace for i.idd Gaussian or uniform Boolean inputs.
prove hardness results in the statistical query model 78 55
Intrinsic dimension estimation. There are many algorithms, dating back decades, which estimate the intrinsic dimension of a given set of data points including approaches based on PCA A4 [7], nearest neighbor methods [63], and others [19 [56). In the context of modern large image datasets such as Imagenet, (77) perform estimates of the intrinsic dimension which are noticeably smaller than the input dimension. Various works study scaling laws arguing that the intrinsic dimension may be useful indicator of the complexity of dataset correlating to the rate at which neural network performance scale with increased data or training 83 6). These works estimate the intrinsic dimension via a maximum likelihood estimator caleulating the intrinsie dimension in relation to the distances of a point to its nearest neighbors 63 40 In later work which estimates the intrinsic dimension using diffusion models, [87 empirically show that this MLE estimator can underestimate the intrinsic dimension for various toy datasets where the intrinsic dimension is known. For this reason, our experiments follow the approach in (87)
Learning algorithms over data manifolds. Among the earliest algorithms for learning over data manifolds those for dimensionality reduction and representation learning [44 8 54 [3 80). As mentioned carlier, a number of works provide algorithms and statistical analysis for manifold reconstruction learning where the goal is to construct manifold that closely fits target [21 3 (2). Perhaps closest to our work are studies of the hardness of learning functions defined over input manifolds. [71] categorize the sample complexity for binary classification over smooth cuts data manifold where smoothness is defined by the condition number of the classification boundary of the manifold (a quantity closely related to the reach). When restrictions are placed on the probability distribution of data on the manifold, they show that the VC dimension is unbounded when this condition number exceeds the reach of the manifold. For nicer distributions where there is an upper bound on the density of the distribution on the manifold, a covering number argument shows that the sample complexity is dependent on the intrinsic dimension, reach, and condition number but independent of the ambient dimension. [64] show that for certain class of convolutional networks trained on data lying in a low-dimensional manifold, the sample complexity depends weakly on the ambient dimension. [88 study the sample complexity of learning a target dataset over inputs taken from manifolds in kernel settings where the target function is invariant over some group operation acting on the input data manifold. The goal of their work was to quantify the gains in sample complexity from enforcing invariance and their sample complexity bounds depend on the volume of the manifold and dimension of the quotient space.
In recent years, various works have empirically tested and analyzed various aspects and implications of the manifold hypothesis. [16] argue that manifolds of data may have many connected components of potentially varying intrinsic dimension and provide some empirical estimates of intrinsic dimen- sion by image class supporting this argument. Our empirical analysis of the intrinsic dimension also supports this point. [8] consider the task of learning a binary classification task where the two classes are two separate disconnected one dimensional manifolds (curves) on the sphere. Under regularity conditions on the extrinsic curvature and Riemannian distance properties of the curves, they prove that sufficiently wide and deep feedforward networks can learn to separate the manifolds.
Their proofs are based on a neural tangent kernel approach. (66) theoretically and empirically study kernel models trained under settings where the latent dimension of the data can be varied. They
15

---

show that the rate of decay in the spectrum of the kernel is more strongly related to the scaling of the loss as opposed the intrinsic dimension of the data with some discussion of potential connections between the two measures. [94] propose a statistical model of real-world data where low dimen- sional features and manifold structures can naturally emerge. [7] categorize the sample complexity for binary classification over smooth cuts on data manifold where smoothness is defined by the condition number of the classification boundary of the manifold (a quantity closely related to reach). When no restrictions are placed the probability distribution of data on the manifold, they show that the VC dimension is unbounded when this condition number exceeds the reach of the manifold. For nicer distributions where there is upper bound on the density of the distribution ifold, a covering number argument shows that the sample complexity is dependent on the intrinsic dimension, reach, and condition number but independent of the ambient dimension.
the man-
Generative modeling. From the perspective of generative modeling, various works have recently considered the task of sampling from low-dimensional manifolds embedded in high dimensional space. 776 consider distributions supported over a data manifold of low intrinsic dimension. They provide sufficient conditions for score-based generative models to identify the support of the learned distribution matching that of the target manifold, (34] prove convergence results in Wasserstein dis- tance between score-based models and target distributions which supported on manifold under the assumption that the score estimator is accurate in the 7 norm. These results were subsequently improved in [24] which only required a score estimator is accurate the L norm, among other im- provements. For data supported on a low-dimensional linear subspace, [22] provide an end-to-end sampling guarantee avoiding the curse of dimensionality and showing that the score function can be efficiently estimated. The resulting sampling algorithm in their work thus approaches the true distribution in total variation distance and recovers the linear subspace appropriately.
Geometric Machine Learning, We briefly mention a related body of work, which studies ma- chine learning algorithms, which directly leverage geometric structure in data. Such methods have shown empirical promise in a variety of domains 15] Examples of such architectures are translation- and rotation-equivarian neural networks (30, graph neural networks [59] and DeepSets for permutation -nvaarian inputs [96), as well as hyperbolic machine learning algorithms [55]] 93 which assume that data lies on a manifold of constant negative curvature.
B Deferred Proofs
B.1 Auxiliary statements
For completeness, we recall several classical notions from metric geometry. Definition B.1 (Packing and covering numbers). Given a set S S RR" the covering number cv is the minimum number of balls of size needed to cover every point in S:
cc == min {k= > 0 #1...., Ty E S such that Væ E S, 5.3t E [k]] such that ||,, x1 S c}
(7)
The packing number (c)(s) is the maximum number of disjoint ehalls that can be contained in S: (c) = max (k > ,,...., Iy E S such that Vi + j ||=, æzاl > 2c}
(8)
Lemma B.2 (Packing and covering duality). For any compact S IR" and 0: pkg (2e) cvs(2e) S pkg(e).
(9)
Proof. For the first inequality, assume by contradiction that (2e) < (2g) Then, there must exist two points x,, v, in the maximal packing, which are within the same 2e-ball in the cover and thus have distance ||=, æ, I 2e contradicting the assumption.
For the second inequality, note that any maximal packing with balls of radius e is 2c-covering, because otherwise, there would exist a point æ E which is least 2c distance away from all the packing points contradicting the definition of a packing.
Before stating the next result, we give a brief definition of Ricci curvature, which locally character- izes the curvature of M in a neighborhood of point E M.
16

---

Definition B.3 (Ricci Curvature), Let E T.M denote a unit vector and fui..... mm-1, 2) an orthonormal basis of T,M; 9N denotes the inner product on T.M. Then the Ricci curvature along the direction v is defined as
m E
Ric (v)
In (R(v, uz),
(10)
m
where R(u, v)w ;= V. V.w V.V.Vo of is the Riemann curvature tensor, with [u, vl denoting the Lie Bracket between u and v.
75 Lemma 7.1.))). Let Volm(p,r) r) denote the volume of the ball of radius r around the point p with respect to the Rie- mannian distance metric. If a manifold M of intrinsic dimension d has bounded Ricci curvature O and p M, (o, S Vol (r) where Volgy (r) denotes the volume of a ball of radius r around an arbitrary point E St in the space S with constant sectional curvalure K (d-sphere if K 0 d-dimensional Hyperbolic space if K < 0).
Theorem B.4 (Corollary
Bishop-Gromon Theorem I0 (see
Rie (M) 2 (d 1)K, then for all
Lemma B.5 (Coupon collector bound (3 ). Let Li....... ......E be i.i.d. random variables taking values in [ni] with uniform probability: Piç, = k] for all k E [n]. Let Tn be the minimum value T such that for all & In], there exists at least one [T] where & k (i.e. every value in [n] covered). Then, [T = (n log(n)) and
lim P [T llg(()) + en] exp(- exx((x)x)))) n-000
(11)
B.2 SQ lower bounds
To show lower bounds in the statistical query model, we follow the technique employed [26 [3). which constructs hardness from statistical independence properties of function class. Since our setting differs slightly from those in 26 13 we provide an adapted version of their constructions below.
Definition B.6 ((1 - 17) pairwise independent; see also Definition C.1 of [26]. Let C be function class consisting of functions f X + V. Let 'D be distribution on X'. C is (1 - 1)-pairwise independent if there exists a finite subset 3 S y such that with probability (1 7)) over x' E X
drawn independently from D, the distribution of (f(x), f(x')) for f ~ Unif(C) drawn uniformly
at random from C is the product distribution Unif()) @ Unif()).
The above agrees with Definition C. of [26] apart from the extension that here we define the inde- pendence with respect to a finite subset D Y of the output space.
Theorem B.7 (Theorem C.4 of (6))). Let the function class C functions J X be (1 1)) pairwise independent function family with respect to a distribution D X. For any E C, let Dj denote the distribution of (x, f(x)) where x ~ D. Let Duni(()) denote the distribution of (x. y) where x ~ 'D and y = f(x) for f Uni Any SQ learner able to distinguish the labeled distribution Dj- for unknown f" E C from the randomly labeled distribution Dunit(cy using bounded queries of tolerance requires at least t² such queries.
Proof. We follow the proof in 26 Let Φ: X x - [-1,1] be any query made by the learner and set of Ee- f())) Then,
Var [ø[s]] = F [ F, [o[l]] E. [o[["]
= Es,y En (a(x,, (zx) )} Be (6(0', / [(x')) E.n (0(2,, Em (o'',
= Bar. E (6(x, (x) (d( , - $(æ, (z))) f
2n.
(12)
In the last line, we use the fact that for any (1 (1-1))pairee) pairwise independent class C, the inner expectation is zero with probability at least 1 77 over the choice of x, x' ~ D and at most 2 otherwise.
17

---

Since any SQ algorithm must work with any given value of the noise within the stated tolerance, consider the adversarial strategy where the SQ oracle responds to query with e E Uniftccy whenever possible. By Chebyshev's inequality,
y-uifiC [o[f]]
2n
Py-Uuif(C) [ - r]
(13)
-
So each such query only allows the learner to rule out at most a ? fraction of C. Thus to distinguish
D- from Duna(()). the learner requires at least 2nj queries.
B.3 Additional examples of learnable manifolds
Here, we provide additional examples of manifolds and their properties that render such manifolds learnable as detailed Section 3.1 There, Iearnability of the distribution of the manifold corre- sponded to the property that one can efficiently approximate the manifold with an epsilon net.
As mentioned in the main text, many algorithms in the manifold reconstruction literature implicitly assume that the manifold is efficiently sampleable. We give one such example below.
Example B.8 (Manifold Learning Setting 19). [9] provide provable guarantees for the Isomap al- gorithm in the sense of recovering geodesic distances on a manifold M via shortest-pare -aaeesst--ahhhhee distance on similarity graph G under the following assumptions (listed in Main Theorem A in [9],, which informally require among other things: (1) the algorithm is given a set of samples {z²}, J. which form 8-net over the manifold M: (2) M is geodesically convex; (3) the reach (equivalently en- coded as bounds on the radius of curvature and branch separation) is bounded as Rch (M) = O()).
Assumption (1) suffices to guarantee learnability in our setting.
We also extend Proposition 3.5 to incorporate manifolds with negative curvature. Negatively curved manifolds have volume that can grow exponentially with respect to the radius around given point. However, as long as the radius of sequence of manifolds does not grow with the ambient dimen- sion, the Bishop-Gromov inequality bounds the volume of such manifolds rendering them efficiently sampleable. As far as we are aware, estimating the diameter of real-world manifolds is a challenging task and it is unknown whether real-world data manifolds
fit within this regime.
Example B.9 (Manifolds with bounded curvature and radius). Any sequence of distributions (PM.)} } supported over manifolds {M,} where each manifold M,, has bounded Ricci curva- ture Ric (Mn) 2 (d 1)K for an arbitrary constant K and is contained within a ball of radius r = (l(gg((T) around a point pn. E M, is efficiently sampleable.
Proof. By the Bishop-Gromov theorem (Theorem [B44) the volume of any such manifold is bounded by Volgg (r) which is the volume of a ball of radius r in the d-dimensional Hyperbolic space of constant curvature K. This means that
Volg(M,,) S Volgg (r) Ja-1 I" sinh (t) dt Ja-1r
(exp(
(exp(r) d-1
(14)
Thus, whenever r = On (log(n)), this allows for an e-cover of size On(poly(n)). The rest of the proof follows directly from that of Proposition 3.5
Another example of class of manifolds that fall in the learnable regime are those which are a- strongly convex [82). property that can be leveraged in instances of Riemannian optimization. This property is extended from the standard notion of strong convexity on Hilbert spaces.
Definition B.10 (a-strong convexity of a Hilbert space (50). Given real Hilbert space H with
inner product ( -) and corresponding induced norm || ||. denote by Bc(c) the closed ball of radius
R centered around e E H. A subset C H is a-strongly convex there exists set C C H such that
A = 0 Br(c),
(15)
cEC
where R ===0 1
18

---

Figure 5: Enumeration of Gray code for n bits. Each column corresponds bitstring where black square is equal to 0 and tan square is 1. Note that the variation takes place largely in the last entries (bottom-most)
The above definition captures the equivalent notion in the Euclidean space Id that an a-strongly convex set A C IRdd is one where for any æ; y E A and unit norm z E R such that ||||| = 1, we
have that 82
(1 - t) ty + a(1 t)t| yl E A.
(16)
Riemannian manifolds are a-strongly convex the image the exponential map over inputs set A living in the tangent space a-strongly convex in the Euclidean sense.
Definition B.11 (a-strong convexity of Riemannian manifold [2 Let M be a Riemannian manifold that is uniquely geodesic (i.e. any two points æ, y E M can be connected by a unique geodesic). Then, M is Riemannian a-strongly convex if for any x E M, the set
Expa (M) fy E T. z Expx x M)
(17)
is a--strongly convex with respect to the inner product || I|. on T in the sense of Definition B.
The above definition places restrictions on the diameter of manifolds, essentially placing them the setting of bounded radius manifolds studied in Example B.9
Example B.12 (Strongly convex manifolds). As stated in Definition B.10 for any a-strongly convex manifold M, the diameter of Exp= (MM) is at most 2r = a- For sequence of such Riemannian a-strongly convex manifolds {M,). as long as the metric over the manifold in the normal coor- dinates at T.M is bounded everywhere (or say the curvature is bounded), then such sequences of manifolds are efficiently sampleable similar to the setting of Example B.9
C Proofs for Section 3.2
C.1 Space-filling manifold
To construct a manifold which achieves the desired lower bound, we form a customized manifold which acts as space-filling curve touching exponentially many quadrants of the n-dimensional hypercube. This space-filling curve is constructed by maneuvering around a Gray code which enu- merates Boolean strings in such fashion that successive strings differ by Hamming distance one. This procedure is motivated by and reminiscent of techniques used in constructing Hilbert curves from Gray codes
Lemma C.1 (Gray code (51)). For every integer k >> O, there exists bijective function G [2*] +
(0, 13 enumerating length & bitstrings such that successive bitstrings G(i) and G(i + differ in only one coordinate, i.e., [Gi - Gli + 1) = where |- |H denotes the Hamming distance.
As simple example, for A 3, the sequence 1000, 011, 010, 110, 111, 101, 100) is one such Gray code which can be constructed recursively as a binary-reflected Gray code 66)] We also visualize the k 7 bit Gray code in Figure
Given an intrinsic dimension d, we will construct manifolds M as products of Pa = (a e [0, 1]d-1). the (d 1) dimeensional hypercube, and a one-dimensional submanifold over the re- maining dimensions, which resembles a one-dimensional space-filling curve. The submanifold is constructed touch the corners of the hypercube following a Gray code.
One-dimensional space-filling curve construction. Our goal is to construct a one-dimensional sub-manifold M C [0, 1]n-4+1 that covers as many quadrants the hypercube as possible. Given a radius of curvature R, which we will later set to be within the bounds of the stated reach, let n = (n - d + 1)) and on = [4.2. In our construction, we will use the Gray code on na bits and map these to bitstrings in dimension n by copying the bitstring of the Gray code óg times.
19

---

1d Manifold (n 3)
1.0
0.5
0.0
1.0
0.0
0.5
0.5
+
0.0
X2
1.0
Figure Shape of constructed manifold M3-
This construction will allow the manifold to have radius of curvature conforming to the given bound on the reach.
Specifically, let G [2m*] - {0. 1 be a Gray code over n. bits, which maps indices 1,.... 2 to the corresponding bitstring in the Gray code (see Lemma C.I Then, for [2 let b, G(1) @ On where G(1))6n is the bitstring G(i) repeated ōµ times and 0g is the bitstring of length & with each entry equal to O. Og is concatenated at the end to ensure the input is of dimension Then, the space- space-filling
filling sub-manifold takes the form:
2
be + bett
bb:
ba+1
(b ba-
Mng
cos(t)
sin(t) [0, aT 7/2
2
(18)
As an example, the manifold M3 visualized in Figure Indexing of the bitstrings by assumed circular and taken & mod 2 Lemma C.2. The manifold Mnn defined in Equation 18 has Rch (Max) = R. Furthermore, defining
{ (sign(æ 1na/2) + lax): Mnn
Round(Mnat
(19)
as the operation which projects each point onto the nearest corner corresponding to bitstrings of the hypercube, we have that [Round[Mnx)) = 2
Proof. Each segment of the manifold in Equation (18 is an are circle centered by 14ba11
and radius V0R/2. For two segments indexed by & such that |A - k'| 2 2, the segments differ maximally in least 6R locations so the medial axis between these segments least /8n/22 2 distance away.
Between neighboring segments indexed by ls and k + 1, of circular ares from (0,æ; 1 1 @ to [05R- lgg /2]@ and then to [16 15 05 @ for some bitstring which shared between all of the points in the curve. Here. for simplicity, have permuted the distinct elements in the neighboring segments to the beginning of the bitstrings. Consider now the medial axis of this curve and set dn directly follow. Here, the medial axis takes the form of points (a, 1 - b, cl O where 0 S a, b < 1/2 and < 1. For any such point where be a point in the first or second segment respectively. For such points, the medial axis will thus be center of the corresponding circle which the are spans. When unique nearest point is always (0, 1, 1/2) @ 8. Otherwise, if c 0.5 and < b or b < the nearest point in the manifold will be a point the first or second segment respectively in the previous case. Putting this all together, the reach of this manifold is v0g/2 > R.
that have curve which consists
for simplicity as the general case will
0.5 or e < 0.3, the nearest point in the manifold will
0.5, if = b < 0.5, then
20

---

Finally, to count the number of elements in Round (Mnn) note that setting t = x/4 4 for segment k: in Equation (18) obtains a point the form
v2 (ba-1 bx+1) 2 2
1 1-
2
+
bk.
(20)
The above is rounded to by. Applying this procedure for all k gives 2 total rounded points.
Corollary C.3. For sequence of manifolds {M,} of intrinsic dimension d O(1) and reach Rch (Mx) = O(n)) for a < 0.5 taking the form of Lemma C.2 the manifold covers exponentially many quadrants of the Boolean cube, i.e. [Round(M,)) 21mm)
In proofs, will consider the setting where we have a sequence of manifolds of increasing intrinsic dimension n and bounded reach. We choose the parameters of this sequence as follows.
Definition C.4 ((or, dd-sequence of manifolds). For given intrinsic dimension d and bound on the reach R = (n")) for some < 0.5, set [4R + d - 1. We construct a sequence of manifolds } of the form given in Equation 18 with the given values of R, n, d where n is incremented by increasing values ns.
C.2 SQ hardness
We present here the hardness results in the statistical query (SQ) model by mapping a class of hard to learn Boolean functions to real-valued neural network functions, which approximate those Boolean functions well. This follows a commonly used set of proof techniques employed in [36] 32 26 48)
We follow most closely the line of reasoning in [26] for showing hardness results for learning two hidden layer ReLU networks though the nature of the distribution in our case will allow us to show SQ hardness results for single hidden layer networks. Similar hardness results based reductions to cryptographically hard problems as shown in the work of [32 are also provided in Appendix CC.3
Hardness in our setting is based on classic results of the SQ hardness of learning parity functions over Boolean inputs [55
parity function Xs {0, 1] > {0, 1} is a Boolean function taking
the form
(s()))) = D(as]:
mod 2,
(21)
iES
which determines whether the summation of the input Boolean string over indices in the set S S [d] even or odd. The class of such parity functions indexed by subsets C [d] is exponentially hard to learn in the SQ model.
Theorem C.5 (SQ hardness of parities I1 (5), see also Theorem 4.3 of (26).. Any SQ algorithm
given SQ access the distribution of labeled pairs (26, where a; (ni 1}a) and y
Xs for an unknown S C [d] capable of learning Xs up to classification error sufficiently small with queries of tolerance T requires (2(722d) queries.
For Boolean inputs Ty E {0. 1)d, the parity function (3()))) can be constructed as single hidden layer neural network with Odd) nodes. Ideally, one would want to replicate this over real-valued inputs, but since ReLU networks are continuous, this construction cannot be made exactly. [32] show that, in practice, one form network which is equivalent the sign function for all but small percentage of inputs. Combined with an indicator function that zeros out the output wherever such inputs cannot be rounded exactly, they show that equivalent hardness results can be obtained in real-valued settings. This construction was extended to SQ settings by [26].
In our setting where the underlying distribution is uniformly drawn from the space-filling manifold described in Appendix C.I. we can resort to a simpler construction given that most input values either 0 or at any point in the space-filling manifold. This lets us identify approximate parity functions which for all but an exponentially small fraction of inputs equivalent to the Boolean parity function.
To achieve this goal, we need to map Boolean parity functions Xss {0, 1) - {0, to real-
valued neural network functions f IR" + R that approximate the parity functions appropriately. In this construction, for given intrinsic dimension d and bound on the reach = O(n)) for some
< 0.5, we set n [4R2] m,, + d - 1 in the construction given in Appendix C.1 (n chosen so
21

---

that the number of bits in the Gray code na is equal to n&). Each input entry is repeated [4R² times this construction, so for a given imput a R", we define P R" - 12 as an operation, which selects one of the [4R²] many equivalent inputs for each of the ne potentially unique values.
That is, for segments of the manifold taking the form of Equation (T8), each segment is sum of
elements b; = ((i) < On,n, where G [2nh] -
{0. 11%h is a Gray code over ng bits. Setting Px= = [ mng to capture the first na elements then suffices to perform such an operation.
The intuition for our construction is as follows: We have to show that at most points on the manifold, inputs are with high probability equal to some Boolean string. If we choose the marginal distribution over the first k input locations of Pæ with &o < Ry sufficiently smaller than nh, then with high probability, these will always be constantly set to either value 0 in the segments of the manifold (Equation (T8). This is because the reflected Gray code is formed by changing the right-most bits first whenever possible so the left-most bits are constant along most segments. We formalize this below.
Lemma C.6. Let DM,, denote the uniform distribution over the (ax, d)-sequencc of manifolds Mn constructed in Definition [.Afor given bounds on the reach R = O(n²) and intrinsic dimension d. Given x E Mn, constructed over the binary code over ny bits, let (Px) (Px))n,,+ denote the vector consisting of the first na t. entries of Pa. for & E [mx). Then, with probability 1 - -(2--), a draw of x ~ D M. will have the property that [Palons E {0, [0,1)mm- Additionally, with probability + 2t-mo 0(2 over independent draws x, x' ~ DM.. mp-m (Px')ins-- and the resulting values will differ in at least one location.
Proof. In the binary reflected Gray code G : [2 - {0, 1) over ny bits, at any location i E [2"h], there exists a span of integers [a, b) containing i of length b b- a = 2 such that [G(j)l = [G(]")] nt is equal for all j. (a, b). Furthermore, by removing the endpoints where for any j.J E [a + 1,b 1). any entry of [GGj]& for E [ng - t] will also have the property that [G()]& [G('") (see Figure for example for visualization of this property). The value at given point in a segment of the manifolds in Equation (18) is not equal to zero or one only when bitstring indices are differing in three adjacent points in the Gray code. Given random point a ~ DM,,- it will fall within a given segment of the Gray code spanned over elements i i- 1, i, + of the Gray code for i ~ )) Thus, the probability that [Px] m {0, 1] 1 is least
1 - 0(2-)).
To prove the additional fact, note that for any {0, 1 -t we have that
2 -8
IP P[[P =]
(22)
2ns
This follows from the previously stated property that at any location E [2nh] in the gray code, there
exists span of integers (a, b) containing i of length b
2 such that [G(j]] = [G(j")] is
equal for all j.j" E aa + 1, 6 1) and all k E [Ta- t]. From this span |a, b) we remove the first
+ and last three indices get the span [a + 4, - 4) over which [G(i)],,- = [G] k)],,- for
all E (a + 4, 4) and k E 2-2, 2]. L.e. this span is chosen to ensure that un,-t is constant
in Equation (18) over those segments of the Gray code. From here, we have that over independent
draws x, x ~ DM.:
P DM [P (Pa'lmm-tt -t (Px) mt E 9 =
Σ
P P
P[ - x]?
(E (0.1)
max
P P[P
P[[xx]mm-t' m6 = =2]
=6(01))mb-
< 1 - (2 -1 - -1) 2' -8
2nd
< 2 + 8(2-')
(23)
The second line above follows from Hölder's inequality. The third line above applies Equation 22 Noting that the last term is 2 ne. + 0(2-t) completes the proof.
The above shows that with exponentially high probability, samples drawn from the distribution over the space-filling manifold will be equivalent to those drawn uniformly over Boolean inputs. This lets us complete the proof of hardness.
22

---

Theorem C.7. Let DM, denote the uniform distribution over the (a. d) sequence of manifolds Mn constructed in Definition where Rch (M,) (n²)) f a < 0.5. Any SQ algorithm A capable of learning the class of linear width single hidden layer ReLU neural networks under this sequence of distributions up to mean squared error sufficiently small (c/8 suffices) with queries of tolerance т must use at least (0(722n0))) queries.
Proof. Given the sequence of manifolds {M,] from the construction in Definition C.4 nh = - which is chosen to fit the bounds on the reach of the manifold.
we have
Given a parity function Xs : {0, 12 - [00,1) 1] taking the form
x
Σ [aals mod 2,
(24)
iES
consider its continuous approximation Žs (0, 11 + (0, defined as
[Eies k {=(x=) - -ies Eiss x; E [k, k + 1], E (1,3, ...,, d 1
Eies Hi E [k, k- 11 k (0,2,4..... d}
(25)
Note, that the above is valid for d even and a similar equation can be obtained for d odd. The above is also piecewise linear and can be constructed as a single hidden layer ReLU network with O(d) width. We consider learning the class of single hidden layer networks consisting of
C= C=ffs: S [ng t}} where fa(x)) Xs ([Px).n,
(26)
Setting = ns/2 suffices by Lemma C.6 to guarantee that [Px]:n//2 is a Boolean string with probability 1 (22 (122)) Furthermore, for æc, x'' drawn i.i.d. from DM,, [Pxt] m2/2 + [Pxx] l:ms/2 with probability 1 ((2-9(m))) Conditioned on this event, the distribution of (Js(z)), fs(x')) is equal to Unif 1).). Since n& 2(n=-2a), we apply Theorem B.7 noting that learning the function class up to MSE e sufficiently small suffices to distinguish the distribution task in Theorem B
C.3 Cryptographic hardness reduction
Here, we will prove hardness results for learning single hidden layer networks under cryptographic hardness assumptions following the methodology in [32]. First, we detail the construction of Gol- dreich's 's pscudorandom generator (PRG) 49 which are used as the basis for the hard to learn class of single hidden layer neural networks in 32). In fact, [32) show that given random Boolean inputs, a neural network with width w()) suffices construct these hard learn functions. From here, we show that the manifold constructed in Section 3.1 can produce inputs that are approximately uniformly distributed over the Boolean cube when restricted to a certain set of input locations. This lets us directly apply the results of 332 to this distribution.
Pseudorandomness assumption The pseudorandom functions are constructed over an (n, m, k)- hypergraph with n vertices [n] with m ordered hyperedges and no repeated entries. Hypergraphs are drawn from the Réngi distribution Gn.m, where each hyperedge is drawn i.i.d. from the set of nn/(nn k)! possible hyperedges (equivalent to ordered sets).
S.., each having cardinality
Definition C.8 (Goldreich's pseudorandom generator (PRG) 44)) Given constant integer k > O, predicate P (0. 1). + (0. 1), and a (n, m, hypprgggaa G, Goldreich's pseudorandom gener- ator (PRG) is the function fr. : (0. 1) > {0, 1mm, such that given input x E {0, 13 returns P(Es.... The PRG has polynomial stretch if m = n for some a > 1.
fP,a(z)
Denoting the collection of functions fr. over (n, m, k) -ypperrgrsss as Fr.m then Fr an e- pseudorandom generator (s-PRG) if every polynomial-
probabilistic algorithm A has advantage at most e distinguishing pairs (G, (T.)())) from random pairs (G, y) where y is drawn i.i.d. from the uniform distribution on (0, 1)m This is formalized below.
Definition C.9 (e (e-pseudorandom generator (s-PRG) (32). Fpmm is an e-pseudorandom generator (g-PRG) if for every polynomial-time probabilistic algorithm A. it holds that
PG m.n.In.,...w0... [A(G, fP.)(z)) = 1] PG m...9,.m,k.00 k.y.BB [A(G. y) = =1] S c, (27)
where Bg denotes the uniform distribution over bitstrings (0. 1kk
23

---

The cryptographic hardness assumption posits that there does exist such a class as above for which it hard distinguish between the cases where y is completely random or the output of randomly drawn function JP..G.
Assumption C.10 (Existence of c-PRG (2)). For every constant $ > 1, there exists a constant and predicate P: (0, 1)* + (0, 1}, such that Fran is J-PRG.
Hard to learn neural network function class We follow the procedure in the previous subsection to map hard to learn Boolean functions to the task of learning real-valued functions where inputs drawn from the data manifold. In this procedure, we must show that instances where a given input does not correspond to Boolean string occur with vanishingly small probability. Following the previous construction, for given intrinsic dimension and bound on the reach R = O( for some < 0.5, we again set n [4R] + d - in the construction given in Appendix C. (n2 chosen so that the number of bits in the Gray code na is equal to ri)) As each input entry is repeated [4R2] times in this construction, we recall the definition of g + I selecting one of the [4R2] many equivalent inputs for each of the nu potentially unique values. The following lemma then guarantees upon that taking the first n& -t entries, with probability 1- 0(2 () the distribution of [Px):ng- will be equivalent to the uniform distribution over Boolean strings.
Lemma C.11. Let DM,. denote the uniform distribution over the (a, d) -sseuencce of manifolds Mn constructed in Definition C.4 f.r for given bounds the reach R. = O(n") and intrinsic dimension denote the vector consisting of the first ny -t entries of Px for E [ng]. Denoting PD the distribution of [Px]mn, for a ~ DM. we have that with probability at least 1 23-t, PDM returns a uniformly random Boolean string:
Given x E .M, constructed over the binary code over nh bits, let
[Bmptt
w.p. 1 1-22 -2--
PDM, (D
(28)
Drem
w.p. 23-t
where By denotes the uniform distribution over bitstrings {0, 13 and Drem is an arbitrary distribu- tion handling the event where draws from the distribution PD PDM,,, string.
M,, are not uniform over the Boolean
Proof. It suffices to show that there exists an event E' occuring with probability least 1-2 -23-t
such that conditioned on this event, for every = E 10,1) 1)
[[Px] km = z F? = 2
(29)
i.c. every bitstring 10 is returned with equal probability. In fact, previously in Lemma C.6 and specifically Equation 22). we showed that
2
[[Px ( = 2] 2n
(30)
Therefore, we can construct the event E by taking the union over the bitstrings z, each of probability 2'-8 ignoring a portion of the distribution whenever a given PP[Px))sstt = x] exceeds this value. 2nd
This implies that
8
PP 2 2m
= 1 23-
(31)
2n
Theorem C.12 (Cryptographic hardness). Let D,M,, denote the uniform distribution over manifolds Mn constructed in Definition C.4 where Rch (M,) O(r)) for a < 0.5. Set a >> 0 to be constant. Then under Assumption C.10 there does not exist any polynomial time algorithm A that with probability 1 - 5 for 0 < 8 I/2 is capable of learning the class of width O(re)) single hidden layer ReLU neural networks under this sequence of distributions up to mean squared error sufficiently small (c/ (c/40 suffices).
Proof. Theorem 8 (part 3) of [32 states that under Assumption C.10 there does not exist an efficient algorithm to learn the class of O(n²) width neural networks under the uniform input distribution Bm over bitstrings (0, 1)m Namely, they show that there exist a set of neural network functions
RM + [0, 1] that have the property that they recover a hard to learn Boolean DNF formula
24

---

f(x) E 10 for any æ E {0. 1). mh Theey then show that any algorithm which with probability 1 1-6 returns a hypothesis h, {0. 1) - [00.1) achieving classification error PawBm [h)(x) + f()) -
1/10 suffices to contradict Assumption C.10
Any efficient algorithm can only take (ppoly(n)) samples. From Lemma we can set m ns/2 with = n2/2 so that with probability least 1- exp(-n(01) a given sample is drawn from Bm./2- By union bounding over (poly(n)) samples, we are guaranteed that all samples are drawn i.i.d. from B,,,/ with probability 1 1-6 for 8' vanishing exponentially in n. Given any input 26 E {0, I we can convert it to a random point on the corresponding quadrant in the manifold Tas E Mm, by drawing t ~ (n, 'T /2)) and applying Equation (18). This recovers the distribution D.M.. Now, assume that the algorithm for learning single hidden layer neural networks under the distribution D.M,, returns hypothesis h II" + R. We can convert this to boolean-
output function h' : IR' + {0, 1} by setting h' (x) sign (()) (x) - 1/2). Note that (see also Lemma 23 of (32) whenever H (T xb) # (()) then (h(Tx>) + f(x))) 2 1/4 and
P Tey=-B,,,--Uiit((0..11 [h' (Tæs)) + f f(x))] S B.
[(h(Tas) f(x6))²]
(32)
The right hand side above contains the mean squared error loss over random Boolean inputs. This is equivalent to the mean squared error loss under the distribution DM.,, up to an exponentially small correction for the event where [P is not Boolean. Thus, learning the function f up to mean squared error e/40 suffices to output a function h achieving classification error e/10 (up to these exponentially vanishing corrections). Applying Theorem 8 of 32 finishes the proof.
C.4 Volume bounds based on reach
The reach of a manifold lower bounds the radius of curvature manifold. In our setting where manifolds are contained within the hypercube [0, 1j", restrictions the reach can intuitively limit the space-filling capacity of manifold resulting upper bounds on the volume of the manifold. Namely, as will show below, for sequence of manifolds {M,, } of intrinsic dimension d. if the reach is bounded by Rch (M,) = w(n..)). then the volume of the manifold is (Ml,)M,,) = (nly(n).. This implies that the results proven in the previous subsections are tight up to Rch (Mn) 5.5, where similar exponential hardness results may apply though are not immediately obtained from our proofs. We formally detail the tightness of our results in what follows below.
Our volume bounds will follow from Lemma B.1 of [3] which locally bound the volume of mani- fold of bounded reach contained within ball.
Lemma C.13 (Adapted from Lemma B.1 of B... Consider a Riemannian manifold M C R" of intrinsic dimension d with reach bounded by R S Rch (M). Let D be measure on R" supported on M with density fanction I with respect to the volume measure Vola where J is Lipschitz smooth and bounded by smin S f(x)= S fmax for all x E MM. Denote B(x,, h) =(xx= =| x'| s h}
as the ball centered around x: of radius h. Then for any Dn E IR" and h S R/S, it holds that
D(B(x, h)) S (5/4))/222
fmaxts fmaxwa max { (122 d(x M)) .0].
(33)
Lemma C.14. Denote B(x, h) = (a' =|a a'll S h) as the ball centered around x of radius
h. Given manifold M C T of intrinsic dimension d bounded in reach by Rch (M) 2 R, the volume of the intersection of the manifold and a ball B(x,, h)) with h S R/8 8 is bounded by
R
Vola (M n B(x, h)) S wid
(34)
2
where Wa is the volume of the d-dimensional unit ball.
Proof. This is a consequence of Lemma B.1 of [3] recalled in Lemma setting finn = funx = to recover the standard volume measure, i.e. for a given point x E R and h I Rch (M)) /8, Lemma C.13 states
Vola (M h)) < (5/4)4/22 (h² d(æ, M)²)
(35)
Applying the bound S Reh (M) /8 and noting that (5/4)//224(11/8) S (1/2)d completes the proof.
D
25

---

The above lemma provides an immediate bound on the volume as one can note that for large enough n, any manifold M [0, 1 is contained within a single ball B(x, h) for h == =n(.
Proposition C.15. Given sequence of manifolds {M,) of intrinsic dimension (fixed and inde- pendent of n. and reach bounded by Rch (Mn) = w(n".)) the volume of the manifolds grows at most (M, = O(poly(n)).
Proof. There exists large enough such that [0, 1]"h is contained within ball of radius equal the bound on the reach Rch (M,, = wnn..6). Applying Lemma C.14 with = vn/2 and x = 1/2 then implies that for large enough
<n= 4
Vola (M₂) Vold (M, (Bx S wd
poly(n).
(36)
Remark C.16. The above implies that manifolds with reach bounded as Rch (M₂)= w(n fall within the class of efficiently sampleable manifolds defined in Definition 3.2 The proof above does extend to the setting where Rch (M,)) (n.0. Covering number bounds (e-g. see Theorem 2 of [61] show that exponentially many (in n) balls of radius cn are needed to cover the space [0, 1]" when e is sufficiently small. Therefore, Proposition C.15 does not guarantee that volume polynomially bounded in specifically for the setting where Rch (Mn) ((n..).
D Experiments confirming learnability results
ambient dim. (n)
0.8
Test MSE
100
200
0.4
0.2
0.0
100
150
200
Epoch
where the target a neural network of the same form but with randomly chosen weights. Results aggregate over five random initializations.
Figure 7: Replication of Figure 3a
ambient dim. (n)
2.0
Test MSE
1.5
1.0
0.5
0.0
5000
10000
15000
Step
Figure 8: Replication of Figure 3b where the trained neural network is overparameterized both width (3 hidden layers instead of just 1) and width. Results are consistent with that of Figure 3b further corroborating the hardness of this learning task. Results are aggregated over five random initializations including random tuning of the optimization hyperparameters.
26

---

For Figure 3a the data is generated by drawing random unit norm vectors from a subspace of dimension d 10 with ambient space of dimension n. The random d-dimensional subspace is obtained by drawing random x orthogonal matrix and taking its first d = 10 columns. Target functions for Figure Baj are drawn from the class in Equation (5) in [6). which form a hard class of single hidden layer neural networks to learn under the i.i.d. Gaussian input model. We set the hidden layer width & = n/4 = (n) for this construction. To corroborate these findings, we also show in Figure 7 the results are consistent when the objective is to learn target function which is a single hidden layer ReLU neural network with randomly chosen weights of the same form. To normalize all target functions to have a consistent MSE benchmark, we divide by the norm of the function which is approximated by taking the average norm over a batch of 100 randomly chosen inputs.
We use the Pytorch package for our neural network experiments 73 Training single neural network on the tasks shown in Figure 3 took no longer than few minutes on a single GPU. For the learnable setting in Figure 3a we use a training set of size 1000 and a neural network of a single hidden layer and width 100 to learn the target function. For the hard setting of Figure 3bb we provide the algorithm with a fresh randomly drawn batch of data each training step. The trained neural network is overparameterized with width 2n in these experiments. For the hard setting in Figure [3b] we also attempted to learn the target function with an overparameterized network with three hidden layers and width 2n. The results, shown in Figure [8] are consistent with those shown in Figure (3b] In all experiments, the learning rate for the optimizer was varied by the default value times random multiplicative factor exp(c) where Unif([ 2, 1)); results were largely consistent across all ranges of the tuned values.
E Estimating Intrinsic Dimension
E.1 Details on Experimental Setup
Following 87). to calculate the intrinsic dimension at a given point p E M, we sample a local neighborhood of points around p by noising p a small amount. Then, from trained diffusion model, we collect a series of score vectors {s; at the sampled neighborhood which point in the direction of the de-noised sample. We then apply PCA upon this collection of N score vectors (treated as a matrix S E R=xN) which gives us a basis for the tangent space Tp.M and normal space Np.M. Given potential instabilities inherent in training diffusion models and performing statistical estimation on manifolds, we use the stable rank to estimate the rank of S [91]. Given a matrix M, the stable rank is given by
M M 2
rs (M)
(37)
where || || and ||- lloo denote the Frobenius norm and maximum singular value respectively. Since S is actually high rank, we estimate instead the rank of 8max I - S where 8max is the max singular value of M to convert this into low rank estimation problem. We find the stable rank above to be a more robust measure of estimated rank in comparison to other such metrics such as the maximum difference in singular values.
We note that this approach can also be taken by estimating the rank over a neighborhood of sampled points well. That is, find that collecting difference vectors between p and the denoised points as samples also estimates the dimension of the tangent space d accurately. Such a method may be more suited to higher dimensional inputs. However, to be consistent with prior work, we perform our analysis on collections of score vectors here. [87] have confirmed this overall methodology on synthetic datasets where the intrinsic dimension is known, showing that in general, it outperforms other statistical means to estimate intrinsic dimension.
Diffusion model and training. For Euclidean datasets, we train a fully-connected 5-layer ReLU network of width 2048 on 100000 samples for 30 epochs, batch size 64, and a learning rate of 4 x 10
For image datasets, we pre-process the images to have pixel values in [-1, We train DDPM U-Net 2D model (79 on 10000 samples for 30 epochs, batch size 64, and a learning rate of 4 10-4 The architecture is held the same across all three datasets: ResNet block, ResNet downsampling
27

---

block with spatial self-attention, and ResNet block with 64, 128, and 256 channels each (and the reverse for upsampling).
We use a noise scheduler in the DDPM paradigm with 1000 timesteps between the image and pure Gaussian noise, with the squared cosine beta schedule introduced by 72 This training was done on an NVIDIA L4 24GB GPU.
We investigate synthetic unit hyperspheres to sanity check method and proceed to three real- world image datasets: MNIST [35), Fashion MNIST (FMNIST) (95), and Kuzushij-MNIST (KM- NIST) 299 For each of the three image datasets, consider two sizes: the original 28 28 and downsampled 12 x 12.
E.2 Results on synthetic data manifolds
Following (8), we verify our intrinsic dimension estimation procedure unit hyperspheres of dif- ferent dimension, randomly projected into a higher-dimensional ambient space. We vary intrinsic and ambient dimension and report estimates of intrinsic dimension measurements (Table 2). We observe that, generally, the estimated and true intrinsic dimension align well. Our results further suggest overall higher accuracy if the intrinsic dimension is small compared to the ambient di- mension. Figure 9 shows the singular values of the score vector for different configurations; the curves, resembling step function, distinguish normal from tangent directions.
Ambient Dim.
Intrinsic Dim.
Estimated Intrinsie Dim.
20
2
20
10
10
20
18
17
100
10
12
100
50
47
100
90
82
Table 2: Estimated intrinsic dimension for the hypersphere.
2-5phere Dimenda1ss
50-Spher 20 Simerdinns
18 13-Spherm 2020 Simerdons
022
300
15:
302
53
25-
10-5phare mimmissss
52-5ohere Demernions
92/Ustare 182 Dimemiios
253
Figure 9: Intrinsic Dimension Estimation on Hyperspheres
E.3 Results on real-world data manifolds
As stated in the main text, we observe that our estimate of MNIST's intrinsic dimension matches that obtained in [87]. We observe slightly lower values, which we believe to be due to different
28

---

Dataset
Intrinsic Dimension (Std Dev)
MNIST (12 12)
29.8 (7.0)
MNIST (28 x 28)
97.0 (18.4)
KMNIST (12 12)
52.9 (9.4)
KMNIST (28 28)
168.9 (28.6)
FMNIST (12 x 12)
39.8 (10.5)
FMNIST (28 x 28)
299.1 (135.9)
Table Estimated intrinsic dimension for the data manifolds considered. We report the mean across classes with standard deviation in brackets.
input sizes. In [87]. MNIST images were upscaled to size 32 x 32. which differs from our input sizes (28 28, 12 12). addition to MNIST, we also analyze FMNIST and KMNIST, which have not been considered in previous studies. Our results suggest that among the three datasets, FMNIST has the largest intrinsic dimension. Images in FMNIST cover part of the image comparison to MNIST and KMNIST; we believe that much of this increase in intrinsic dimension is due to the larger set possible perturbations of the image within this area.
We also explore how resizing the image impacts the data manifold's intrinsic dimension in Figure TO and Table 3 We see that for MNIST and KMNIST, resizing to a smaller ambient dimension can reduce the intrinsic dimension though at slightly slower rate than that of the ambient dimension. We note that all the images we consider here have relatively intrinsic dimension, where the effects of resizing may be more prominent.
2-54
110
Strt
Bay
Figure 10: Impact of Resizing on Score Spectrum for Estimating Intrinsic Dimension from Diffusion Models
29

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In this work, support formal claims with proofs and include experimental evidence the main findings.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have described limitations our work various points. Given our work describes theoretical setting where we can prove hardness under data manifold assump- tions, many of these limitations relate to the assumptions fo the work. For example, in the discussion section, we mention various places where our formal statements do not apply and mention future areas of work to address these limitations. In our experiments, we also outline areas of differences between practice and theory.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairnsss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't it acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
30

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
All formal statements are proven either in the main text or Appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Ys]]
Justification: Code is supplied which replicates all experiments. We include additional details of experiments the main text and in appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, deseribing the architecture fully might suffice, or the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), relcasing of model checkpoint, or other means that are appropriate to the research performed.
also be provided via
While NeurlPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility.
31

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
Code is supplied and details are provided in appendix for experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.com
public/guides (eeali//uulles//ddeuuubiisssss Pollcyy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: htwpuiddeeeeeeuuueeeeeeeee
//nips. httpssccccpblllee
ssionpolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/eetails
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Details of optimizers, hyperparameters, etc. are provided in Appendices D and D
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should presented in the core the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For experiments where we train neural networks (Appendix D). we include етror bars over random instantiations of the training.
Guidelines:
The answer NA means that the paper does not include experiments.
32

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures sy symmetric error bars that would yield results that are out of range (e.g. negative enror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Computational resources were relatively limited for this largely theoretical
work. All experiments required only single GPU (see Appendices D Dland
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't t make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http:ppppp///eeepp.oo////p////aa
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
33

---

Justification: This work fits within the scope of foundational research and is theoretical in nature. We do introduce any new models techniques, instead focusing on understand- ing data manifolds and learning in more theoretical framework. Although this work can advance our knowledge of machine learning, there are no clear negative societal impacts that directly arise from this work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work is largely theoretical and apart from some small datasets like MNIST, we do not perform any experiments on data that has high risk for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: The real-world datasets used in our paper are cited with their respective li- censes explicitly named in the README and are properly respected.
34

---

Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name the license (e-g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, haperswithcodee com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given participants and sereenshots, applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
35

---

Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
36


Reviews:
[{"review_id": "ZCaigCZ96r", "reviewer": "Reviewer_VtS6", "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.", "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)?\n\nThe 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?\n\nMight 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?", "limitations": "Yes they have.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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.\n\nIt 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.\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and feedback. We address their questions below.\n\n___\n\n> 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)?\n\nThe number of degrees of freedom is indeed $\\exp(n)$ in the sense of the number of quadrants touched. However, note that we restrict to finite depth and width neural networks, so it is not true that there are $\\exp(\\exp(n))$ many functions. There are $poly(n)$ many weights in the neural network, so the number of possible functions is at most $\\exp(O(poly(n)))$. There are additional restrictions as well such as the form of the nonlinearity, bounded weights, etc. which limit the number of unique functions. This is why we can't just use a counting argument as stated in your question. \n\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.\n\nWe agree with the reviewer, but do want to point out one caveat. Our results look at *runtime complexity* in the SQ formalism or via cryptographic hardness reduction. Sample complexity is a not unrelated but different question from runtime complexity.\n\n> 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?\n\n\nWe agree with the reviewer. These types of manifolds have localized regions with high curvature. They are probably learnable but fall outside the formal scope of our results. It is an interesting next question to explore how to formalize such manifolds.\n\n\n> 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?\n\nIf we understand the question correctly, there may be other ways to form classes of manifolds with high curvature, e.g. via polynomial equations or algebraic varieties. We suspect the results and techniques we use extend to such settings, though we do not have any formal results thereof. It is an interesting question nonetheless and one we hope to explore later.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vy1b3TdhiQ", "reviewer": "Reviewer_PDhw", "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.\nThe 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.", "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?\n\n- 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?\n\n- 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)?", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\nThe 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.\n\n(1)\nThe sampleable approach restricts the class of included manifolds.\n\n(2)\nThe 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.\n\n(3) Only one class, namely feedforward neural networks, is considered.\n\n### Minor\n- l 115: to to", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful questions and positive feedback. We answer their questions below.\n____\n\n> Any of the following concerns can be assumed mediocre and the first two are also discussed transparently.\n> (1) The sampleable approach restricts the class of included manifolds.\n> (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.\n> (3) Only one class, namely feedforward neural networks, is considered.\n\nWe tried our best to find the broadest setting that is still closely tied to practice. Regarding point (3), we found this class of manifolds a good starting point as it is canonical in some sense and encompasses other types of architectures as well (e.g. CNNs can be written as fully connected networks of large enough width). In the revised manuscript, we will expand the discussion section to emphasize these restrictions of our setting.\n\n> Typo: l 115: to to\n\nThank you. This is now corrected.\n\n> 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?\n\nWe suspect many of the techniques for lower bounds extend to other network classes. For example, a recent work (ICLR 2024: On the Hardness of Learning Under Symmetries) analyzes such a question for Gaussian inputs in various equivariant and invariant architectures. Replacing the Gaussian input assumption with one of a manifold is an interesting question. We do not immediately see why proof techniques would fall apart, but it is worth exploring.\n\n> 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?\n\nIf we understand the question correctly, hardness does indeed also apply to multilayer networks. If an algorithm cannot learn a single hidden layer network, then it cannot learn multi-layer ones that encompass even more functions. E.g., one can simply ignore added layers by setting weights to identity and passing the input after the first layer through the later layers. \n\n> Does your analysis capture hyperbolic spaces, i.e., dimensional Riemannian manifold of constant sectional curvature equal to since the latter are shown to be adequate for image learning (see Khrulkov et al.: Hyberbolic Image Embeddings, CVPR, 2020)?\n\nWe suspect our analysis would be able to capture hyperbolic spaces, though the details would depend on the formal structure of these spaces. Changes to the setup would also need to be made. For example, we restrict manifolds via the reach, which is different than sectional curvature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Rn7URzKeLL", "reviewer": "Reviewer_7hKF", "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.", "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?", "limitations": "See weaknesses. Overall, this is an interesting paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive comments and feedback. We address their questions below.\n\n___\n\n> 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.\n\n\nWe believe the reviewer is referring to Figure 3a, but in Figure 3b we actually include another synthetic experiment which is with the space-filling curve as the input distribution rather than a hypersphere.\nFor positively bounded manifolds, we chose the hypersphere because it is a canonical instance of a bounded positive curvature manifold. Other bounded positive curvature manifolds are in some sense contained within a hypersphere as can be formally shown via Bishop-Gromov inequalities.\nAdditional experiments in Appendix C using unit hyperspheres are devoted to sanity check an intrinsic dimension estimation routine before being applied to MNIST data. The focus of that experiment is more on describing real-world manifolds, which likely lie in the middle heterogeneous regime that have varying intrinsic dimensions.\n\n> 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?\n\nSample complexity is not unrelated to runtime complexity and SQ complexity, but nonetheless is still a separate question. In fact, the bounded depth and width neural networks we study have polynomial sample complexity since their VC dimension is always polynomial in the input dimension (see for example Bartlett et al. Almost Linear VC-Dimension Bounds for Piecewise Polynomial Networks). This does not imply that one can *learn* these functions efficiently in polynomial time. This question of learnability is the focus of our study.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DXh7YqhtUB", "reviewer": "Reviewer_Wvq2", "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.", "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.\n\nCould the authors comment about whether their results should still hold for deeper networks. I am particularly curious given the results of [1] mentioned above.", "limitations": "Limitations have been addressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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. \n\nIn 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.\n\nOne 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. \n\n[1] Wang, Tingran, et al. \"Deep networks provably classify data on curves.\" Advances in neural information processing systems 34 (2021): 28940-28953.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. We answer their questions and comments below.\n\n___\n\n> There is no attempt for instance to check empirically whether the scaling of the sample complexities in the hardness result matches the experiment.\n\nIf we understand the reviewer's point correctly, they are referring to the runtime complexity of the interpolation-based argument in section 3.1. As mentioned in the text, we do not believe the scaling of this algorithm is tight. We only wanted to show that it can be polynomial. Hence, it is unlikely that the experiments which use a neural network to learn the function will match the scaling of this bound.\n\n> The novelty of the experiments estimating the intrinsic dimension of standard image datasets is also unclear.\n\nWe wanted to use this to stress that our formal results may need to be expanded to better apply to realistic datasets. Our goal was primarily to show that image datasets are heterogeneous in nature and, for example, do not have just a single intrinsic dimension. \n\n> One weakness of the hardness results is that they only apply to shallow networks.\n\nIndeed, our formal results are stated for bounded depth networks. Though, we should note that the lower bounds in Section 3.2 apply to single hidden layer networks, so they also apply trivially to any depth more than that as well. \n\n> 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.\n\nThank you for pointing out this work; we will cite it. The question studied in the paper you reference though is rather different. They look at classification problems where the classes are different manifolds. We look at learning a neural network where the input distribution is over a manifold. An analogous classification task in our case would be given by the output of a neural network and may no longer even be a regularized manifold. \n\nWe should remark that there are other papers that study fitting a manifold or classifying data that is a manifold itself. We cite them in the related works section of our paper. \n\n> 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.\n\nSQ access is not crucial in general. In fact, our results also hold under cryptographic hardness assumptions. We should remark that proving **efficient** PAC learnability is generally very hard. We stress the word efficient, because in general, PAC learnability is framed as a question of only sample complexity and not runtime complexity. \n\nIn fact, without any assumptions or restrictions to the learning model, a proof that one cannot learn a network in polynomial time would imply that $P\\neq NP$. So, we have to make restrictions. Ours is the SQ setting which lets us quantify hardness in number of queries (or via cryptographic hardness reductions).\n\n\n> Could the authors comment about whether their results should still hold for deeper networks.\n\nAs mentioned earlier, our lower bounds in Section 3.2 apply trivially to any network that has more than a single hidden layer. The upper bounds in Section 3.1 likely will not apply if the depth of the network grows with input dimension $n$. Here, other techniques likely need to be used as you mention.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the hardness of learning neural networks when their input data lies on a low-dimensional manifold, establishing learnability when the reach of the manifold is large, and constructing an example requiring exponentially many samples when the reach is small. Reviewers agree the paper is well written, and that the results are novel and of interest to the NeurIPS community. I thus recommend acceptance.
Decision: Accept (spotlight)