Deep Networks Provably Classify Data on Curves
Authors: Tingran Wang
Sam Buchanan
Dar Gilboa
John Wright
Venue: NeurIPS 2021 Poster (2021)
Keywords: deep learning theory
overparameterized neural networks
low-dimensional structure
kernel methods
neural tangent kernel

Abstract: Data with low-dimensional nonlinear structure are ubiquitous in engineering and scientific problems. We study a model problem with such structure---a binary classification task that uses a deep fully-connected neural network to classify data drawn from two disjoint smooth curves on the unit sphere. Aside from mild regularity conditions, we place no restrictions on the configuration of the curves. We prove that when (i) the network depth is large relative to certain geometric properties that set the difficulty of the problem and (ii) the network width and number of samples is polynomial in the depth, randomly-initialized gradient descent quickly learns to correctly classify all points on the two curves with high probability. To our knowledge, this is the first generalization guarantee for deep networks with nonlinear data that depends only on intrinsic data properties. Our analysis proceeds by a reduction to dynamics in the neural tangent kernel (NTK) regime, where the network depth plays the role of a fitting resource in solving the classification problem. In particular, via fine-grained control of the decay properties of the NTK, we demonstrate that when the network is sufficiently deep, the NTK can be locally approximated by a translationally invariant operator on the manifolds and stably inverted over smooth functions, which guarantees convergence and generalization. 

Deep Networks Provably Classify Data on Curves
Tingran Wang Columbia University (12579@columble edu
Sam Buchanan
Dar Gilboa
Columbia University
Harvard University
s. buchanan@columbia.com
dar Bar_gilboa@fas hww.ard. edu
John Wright
Columbia University
j |w2666cclumbia. edu
Abstract
Data with low-dimensional nonlinear structure are ubiquitous in engineering and scientific problems. We study a model problem with such structure-4 binary classification task that uses deep fully-connected neural network to classify data drawn from two disjoint smooth curves on the unit sphere. Aside from mild regularity conditions, we place no restrictions on the configuration of the curves. We prove that when (i) the network depth is large relative certain geometric properties that set the difficulty of the problem and (ii) the network width and number samples are polynomial in the depth, randomly-initialized gradient descent quickly learns to correctly classify all points the two curves with high probability. To our knowledge, this is the first generalization guarantee for deep networks with nonlinear data that depends only intrinsic data properties. Our analysis proceeds by reduction to dynamics in the neural tangent kernel (NTK) regime, where the network depth plays the role of fitting resource in solving the classification problem. In particular, via fine- ane-grained control of the decay properties of the NTK, demonstrate that when the network is sufficiently deep, the NTK can be locally approximated by a translationally invariant operator on the manifolds and stably inverted over smooth functions, which guarantees convergence and generalization.
Introduction
In applied machine learning, engineering, and the sciences, we are frequently confronted with the problem of identifying low-dimensional structure in high-dimensional data. In certain well- structured data sets, identifying good low-dimensional model is the principal task: examples include convolutional sparse models in microscopy [43] and neuroscience [10, 16], and low-rank models in collaborative filtering [7. 8]. Even more complicated datasets from problems such as image classification exhibit some form of www-dimeniionaltty: recent experiments estimate the effective dimension of CIFAR-10 26 and the effective dimension of ImageNet 43 [61]. The variability in these datasets can thought of as comprising two parts: a "probabilistic" variability induced by the distribution of geometries associated with given class, and "geometric" variability associated with physical nuisances such as pose and illumination. The former is challenging to model analytically; virtually all progress this issue has come through the introduction of large datasets and high- capacity learning machines. The latter induces a much cleaner analytical structure: transformations of given image lie near low-dimessional submanifold of the image space (Figure 1). The celebrated successes of convolutional neural networks in image classification seem to derive from their ability simultaneously handle both types of variability. Studying how neural networks compute with data lying near low-dimensional manifold is an essential step towards understanding how neural
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

networks achieve invariance to continuous transformations of the image domain, and towards the longer term goal developing more comprehensive mathematical understanding of how neural networks compute with real data. At the same time, in some scientific and engineering problems, classifying manifold-structured data is the goal-one example in gravitational wave astronomy [22, 30], where the goal is to distinguish true events from noise, and the events are generated by relatively simple physical systems with only a few degrees of freedom.
Hedgehogs
M.
M-
Hairbrushes
1/1e
S 1
Figure 1: Low-dimensional structure in image data and the two curves problem. Left: Manifold structure natural images arises due invariance of the label continuous domain transformations such as translations and rotations. Right: The two curve problem. We train a neural network to classify points sampled from density p on the submanifolds M M_ of the unit sphere. We illustrate the angle injectivity radius A and curvature 1/k. These parameters help to control the difficulty of the problem: problems with smaller separation and larger curvature are more readily separated with deeper networks.
Motivated by these long term goals, in this paper study the multiple manifold problem (Figure 1), a mathematical model problem in which we are presented with a finite set of labeled samples lying disjoint low-dimensional submanifolds of high-dimensional space, and the goal is to correctly classify every point on each the submanifolds- a strong form of generalization. The central mathematical question is how the structure of the data (properties of the manifolds such dimension, curvature, and separation) influences the resources (data samples, and network depth and width) required guarantee generalization. Our main contribution is the first end-to-end analysis of this problem for a nontrivial class of manifolds: one-dimensional smooth curves that are non-intersecting, cusp-free, and without antipodal pairs of points. Subject to these constraints, the curves can be oriented essentially arbitrarily (say. non-lineario non-lincarly-separee our results depend only on architectural resources and intrinsic geometric properties of the data, To our knowledge, this is the first generalization result for training a deep nonlinear network to classify structured data that makes no a-priori assumptions about the representation capacity of the network or about properties of the network after training.
as in Figure 1), and the hypotheses of
Our analysis proceeds in the neural tangent kernel (NTK) regime of training, where the network is wide enough to guarantee that gradient descent can make large changes in the network output while making relatively small changes to the network weights. This approach is inspired by the recent work [57], which reduces the analysis of generalization the one-dimensional multiple manifold problem to an auxiliary problem called the certificate problem. Solving the certificate problem amounts to proving that the target label function lies near the stable range of the NTK. The existence of certificates (and more generally, the conditions under which ceeetically-trrinee neural networks can fit structured data) is open, except for few very simple geometries which we will review below in particular, [57] leaves this question completely open. Our technical contribution is to show that setting the network depth sufficiently large relative to intrinsic properties of the data guarantees the existence a certificate (Theorem 3.1), resolving one-dimensional case of the multiple manifold problem for broad class of curves (Theorem 3.2). This leads in turn novel perspective on the role of the network depth as a fitting resource in the classification problem, which inaccessible to shallow networks.

---

1.1 Related Work
Deep networks and low dimensional structure. Modern applications of deep neural networks include numerous examples of low-dimensional manifold structure, including pose and illumination variations in image classification [1, 5], as well as detection of structured signals such as electrocardio- grams [14, 20], gravitational waves [22, 30], audio signals [13], and solutions to the diffiusion equation [48]. Conventionally, to compute with such data one might begin by extracting a low-dimensional representation using nonlinear dimensionality reduction ("manifold learning") algorithms [2-4, 6, 12, 54, 56]. For supervised tasks, there is also theoretical work on kernel regression over manifolds [9, 11, 19,51], 51J. These results rely on very general Soboley embedding theorems, which not precise enough to specify the interplay between regularity of the kernel and properties of the data need to obtain concrete resource tradeoff's in the two curve problem. There is also a literature which studies the resource requirements associated with approximating functions over low-dimensional manifolds [15, 29, 38, 44]: typical result is that for a sufficiently smooth function there exists an approximating network whose complexity is controlled by intrinsic properties such as the dimension. In contrast, we seek algorithmic guarantees that prove that we can efficiently train deep neural networks for tasks with low-dimensional structure. This requires us to grapple with how the geometry of the data influences the dynamics of optimization methods.
Neural networks and structured data data-theory? Spurred by insights in asymptotic infinite width [23, 24] and non-asymptotic [18, 21] settings, there has been a surge of recent theoretical work aimed at establishing guarantees for neural network training and generalization [26-28, 34, 37, 40, 49, 55]. Here, our interest is in end-to-end generalization guarantees, which are scarce in the literature: those that exist pertain unstructured data with general targets, in the regression setting [32, 36, 46, 59], and those that involve low-dimensional structure consider only linear structure (i.e., spheres) [46]. For less general targets, there exist numerous works that pertain to the teacher-student setting, where the target is implemented by a neural network of suitable architecture with unstructured inputs [17. 33, 40, 49, 63]. Although adding this extra structure to the target function allows one to establish interesting separations in terms of c.g. sample complexity [31. 39, 49, 62] relative to the preceding analyses, which proceed in the "kernel regime", we leverage kernel regime techniques in our present work because they allow us to study the interactions between deep networks and data with nonlinear low-dimensional structure, which is not possible with existing teacher-student tools. Relaxing slightly from results with end-to-end guarantees, there exist 'conditional' guarantees which require the existence of an efficient representation of the target mapping in terms of a certain RKHS associated to the neural network [34, 53, 57, 58). In contrast, our present work obtains unconditional, end-to-end generalization guarantees for a nontrivial class of low-dimensional data geometries.
2 Problem Formulation
Notation. We use bold notation x. A for vectors and matricess/operaooss (respectively). We write ||>||p = (Ei 1/) for the E norm of x. (x,z) 3) = Σn= IiDii for the euclidean inner product, and for a measure space (X, p). Iglli = (1))())) d)((r))//P denotes the LP norm of a function g: X + R. The unit sphere in E is denoted g--1 and L(x, y) = cos ((xr, y)) denotes the angle between unit vectors. For a kernel for the action of the associated Fredholm integral operator; omitted subscript denotes Lebesgue measure. We write Ps to denote the orthogonal projection operator onto a (closed) subspace S. Full notation is provided in Appendix B.
X x + R, we write [,(g](x) (x) = ((x, x') (a))g(a)) du(x')
2.1 The Two Curve Problem'
A natural model problem for the tasks discussed in Section I is the classification of low-dimensional submanifolds using a neural network. In this work, we study the one-dimensional, two-class case of this problem, which we refer to as the two curve problem. To fix ideas, let no 2 3 denote the ambient dimension, and let M+ and M_ be two disjoint smooth regular simple closed curves taking values in g which represent the two classes (Figure 1). In addition, we require that
'The content of this section follows the presentation of [57]: we reproduce it here for conainentass...ss.. We omit some nonessential definitions and derivations for concision; Appendix C.I for these details.
3

---

the curves lie in a spherical cap of radius 7/2: for example, the intersection of the sphere and the nonnegative orthant {a E Io x 2 0). Given N ii.d. samples {z, 1 from a density p supported on .M = MMMMM-- which is bounded above and below by positive constants Amax and Pmin and has associated measure j4, as well as their corresponding +11 labels, we train a feedforward neural network fe Rh - I with ReLU nonlinearities, uniform width n. and depth T. (and parameters O) by minimizing the empirical mean squared error using randomly-initialized gradient descent. Our goal is to prove that this procedure yields a separator for the geometry given sufficient resources L, and N-ic., that sigu(fe,) = I on M+ and -1 on M at some iteration & of gradient descent.
To achieve this, we need an understanding of the progress of gradient descent. Let f. : :M + {+1} denote the classification function for M+ and M_ that generates our labels, write (o(x) fo(z)
(ax) for the network's ss prediction error, and let 0x+1 = 0% (T/N) Ei= Co, VV.,ooo.. (a,) denote the gradient descent parameter sequence, where T > 0 is the step size and On represents our Gaussian initialization. Elementary calculus then implies the error dynamics equation Co._
Of (,)))) Co, (ax) for k 0, I..... where O . X M + I is a certain kernel. The precise expression for this kernel is not important for our purposes: what matters is that (i) making the width n large relative the depth L guarantees that O remains close throughout training to its 'initial value' ONTK(#; x²) (Vole, (a),, VeJen ToJon(x')) (a²)), the neural langent kernel; and (ii) taking the sample size N to be sufficiently large relative to the depth L implies that a nominal NTK
Co. - (T/N)
error evolution defined as (K+1 = <x- 7 P [<x] with Co- = Ço. uniformly approximates the actual error Se. throughout training. In other words: to prove that gradient descent yields a neural network classifier that separates the two manifolds, it suffices to overparameterize, sample densely, and show that the norm of Sa decays sufficiently rapidly with k. This constitutes the "NTK regime" approach to gradient descent dynamics for neural network training [23].
[co]. The evolution of Ç& is relatively straightforward: we have Ck++1 = (Id y
and @NTK is a positive, compact operator, so there exist an orthonormal basis of L functions By and eigenvalues 0 such that Sa+1 Σ (1 =Aa)* (So, 12 U,- In particular, with bounded step
A 2 A size T < XT gradient descent leads to rapid decrease of the error if and only if the initial error Ço is well-aligned with the eigenvectors of G,TK corresponding to large eigenvalues. Arguing about this alignment explicitly is challenging problem in geometry: although closed-form expressions for the functions U, exist in cases where M and are particularly well-structured, no such expression is available for general nonlinear geometries, even in the -ieddimeniional case we study here. However, this aligmment can be guaranteed implicitly if one can show there exists a function g .M + I of small L norm such that θ j
NTK [g] = Çu-in in this situation, most of the energy of Ço must be concentrated on directions corresponding to large eigenvalues. We call the construction of such a function the certificate problem [57, Eqn. (2.3)):
Given two curves problem instance (M, p). find conditions the architec- tural hyperparameters (n, L) so that there exists : M - I satisfying [|0 [g] - Coll 2 1/L and 13 & 1/n, with constants depending on the density p and logarithmic factors suppressed.
Certificate Problem.
The construction of certificates demands a fine-grained understanding of the integral operator θ NTK and its interactions with the geometry M. We therefore proceed by identifying those intrinsic properties of M that will play a role in our analysis and results.
2.2 Key Geometric Properties
In the NTK regime described in Section 2. gradient descent makes rapid progress if there exists a small certificate g satisfying QTT 6 [g] = Ço. The NTK is a function of the network width n and depth L-in particular, we will see that the depth L serves as fitting resource, enabling the network to accommodate more complicated geometries. Our main analytical task is to establish relationships between these architectural resources and the intrinsic geometric properties of the manifolds that guarantee existence of a certificate.
"The specific value n/2 is immaterial to our arguments: this constraint only to avoid technical issues that arise when antipodal points are present in M, so any constant less than æ would work just as well. This choice allows for some extra technical expediency, and connects with natural modeling assumptions (e.g. data corresponding to image manifolds, with nonnegative pixel intensities).

---

Intuitively, one would expect it to be harder to separate curves that are close together or oscillate wildly, In this section, we formalize these intuitions in terms of the curves' curvature, and quantities which we term the angle injectivity radius and --number, which control the separation between the curves and their tendency to self- eeff-inerssett. Given that the curves regular, may parameterize the two curves at unit speed with respect to are length: for a E { we write len(M,) to denote the length of each curve, and use æz (s) [0, len(Ma)] + g to represent these parameterizations. We let w! (s) denote the i-th derivative of Do with respect to are length. Because our parameterization is unit speed. ||=6 (s)ll2 for all æy (s) M. We provide full details regarding this parameterization in Appendix C.2.
Curvature and Manifold Derivatives. Our curves Ma are submanifolds of the sphere S The curvature of MM at a point (s) is the norm (e) (s) of the component Px, (e) 3o (2)
of the second derivative of x, (s) that lies tangent to the sphere Smo-1 at æ, (s). Geometrically, this measures the extent to which the curve (s) deviates from a geodesic (great circle) on the sphere. Our
technical results are phrased in terms of the maximum curvature x = supo., { Pa - (2) (2) In
stating results, we also use & = max A to simplify various dependencies on k. When K is large, M, is highly curved, and we will require a larger network depth L. In addition to the maximum curvature K, our technical arguments require z (s) to be five times continuously differentiable, and use bounds M;- = supo,s sulp,_(ll=>"" (s)] on their higher order derivatives.
Angle Injectivity Radius. Another key geometric quantity that determines the hardness of the problem is the separation between manifolds: the problem is more difficult when MM and M__ are close together. We measure closeness through the extrinsic distance (angle) ((x, æ²) = cos (æe x') between and æ' over the sphere. In contrast, we use d (ar, æ') ) to denote the intrinsic distance between æ and x' on M,, setting dm(x, x') = co if æ and x' reside on different components M+ and M_. We set
A = inf (<xx, du(ær, x') 2 2
(2.1)
where T1 V206 and call this quantity the angle injectivity radius. In words, the angle injectivity radius is the minimum angle between two points whose intrinsic distance exceeds тΙ. The angle injectivity radius A (i) lower bounds the distance between different components M+ and M_, and (ii) accounts for the possibility that a component will "loop back," " exhibiting points with large intrinsic distance but small angle. This phenomenon is important account for: the certificate problem is harder when one or both components of M nearly self-intersect. At an intuitive level, this increases the difficulty of the certificate problem because it introduces nonlocal correlations across the operator @NTK, hurting its conditioning. As we will see in Section 4, increasing depth L makes ONT better localized; setting L sufficiently large relative to A compensates for these correlations.
H-number The conditioning of @ depends not only how near M comes to intersecting itself, which is captured by A, but also on the number of times that M can "loop back" to a particular point. If M "loops back" many times, NTK can be highly correlated, leading to hard certificate problem. The B-number (verbally, "clover number") reflects the number of near self-intersectionn
V K2 }}
(SM) = sup NM ([x') dd((x, x') 2 mı, (xx x²) S 12h, 3EM
(2.2)
20v/0AA The set (æ' d. x²) 2 TI, (x, S T2) is the union of looping pieces, namely points that are close to x in extrinsic distance but far in intrinsic distance. (T, 8) the cardinality of a minimal ó covering of C M in the intrinsic distance on the manifold, serving as way count the number of disjoint looping pieces. The C-number accounts for the maximal volume of the curve where the angle injectivity radius A is active. It will generally be large if the manifolds nearly intersect multiple times, illustrated in Fig. 2. The B-number is typically small, but can be large when the data are generated in a way that induces certain near symmetries, as in the right panel of Fig. 2.
with
19
5

---

x denoted in orange Certificate Norm
B-Number
0 2
o =1
Figure 2: The -e-number-theor and practice. Left: We generate parametric family of space curves with fixed maximum eurvature and length, but decreasing &-nuber,, by reflecting 'petals' of a clover about a circumscribing square. We set Mr to be a fixed circle with large radius that crosses the center of the configurations, then rescale and project the entire geometry onto the sphere to create a two curve problem instance. In the insets, we show a two-dimensional projection of each of the blue M curves well as base point E MM at the center (also highlighed in the dire-dimmnnional plots). The intersection of M_ with the neighborhood
represents the set whose covering number gives the -umbbeer of the configuration (see (2.2)). Top right: We numerically generate certificate for each the four geometries at left and plot its norm as a function of B-number. The trend demonstrates that increasing -e-numeer correlates with increasing classification difficulty, measured through the certificate problem: this is in line with the intuition we have discussed. Bottom right: t-SNE projection of MNIST images (top: a "four" digit; bottom: "one" digit) subject to rotations. Due to the approximate symmetry the one digit under rotation by an angle æ, the projection appears to nearly intersect itself. This may lead to a higher &-mumeer compared to the embedding of the less-symmetrie four digit. For experimental details for all panels, see Appendix A.
Main Results
Our main theorem establishes set of sufficient resource requirements for the certificate problem under the class of geometries we consider here-by the reductions detailed in Section 2.1, this implics that gradient descent rapidly separates the classes given neural network of sufficient depth and width. First, we note a convenient aspect of the certificate problem, which is its amenability to approximate solutions: that is, if we have kemel O that approximates NTK in the sense that |oo, @ 11, S n/ L. and a function Ç such that ||< Collz; S 1/L, then by the triangle inequality and the Schwarz inequality, it suffices to solve the equation (,) R Ç instead. In our arguments, we will exploit the fact that the random kernel NTK concentrates well for wide networks with n 2 L, choosing as
L-1L-1
(xx, = (n/2)
(1- 11-
(3.1)
1=0 P=t
where (t)) well as the fact that for wide networks with 2 1,5 depth 'smooths out' the initial error Co. choosing the piccewise-constant function ((x) ff(()) + Jm (x')) du(x'). We reproduce
- cos/ (1/x) sin and pll') denotes f'-fold composition of yo; as

---

probabrobabilityy concentration guarantees from the literature that justify these approximations in Appendix G.
Theorem 3.1 (Approximate Certificates for Curves), Let M be two disjoint smooth, regular, simple closed curves, satisfying 4(x, x') S 4/2 for all x' E M. There exist absolute constants C, C.C,,, C", C and a polynomial P = poly( Ma, Ma, M5, (e)(M), 1 of degree al most 36, with degree at most 12 in (Ma, Ma, M5, (MM(M) and degree most 24 A -1, -such that when
(MM
L 2 max (M))))))) (AVI+
C R P.P P.mmmxx
c Pmin log L such that 110 <ll.gg S 1e L
there exists certificate g with l1g|l13 S
Theorem 3.1 is main technical contribution: it provides sufficient condition on the network depth I. to resolve the approximate certificate problem for the class of geometries we consider, with the required resources depending only on the geometric properties introduce in Section 2.2. Given the connection between certificates and gradient descent, Theorem 3.1 demonstrates that deeper networks fit more complex geometries, which shows that the network depth plays the role of fitting resource in classifying the two curves. We provide a numerical corroboration of the interaction between the network depth, the geometry, and the size of the certificate in Figure 3. For any family of geometries with bounded --number, Theorem 3.1 implies a polynomial dependence of the depth on the angle injectivity radius A, whereas we are unable to avoid an exponential dependence of the depth on the curvature x. Nevertheless, these dependences may seem overly pessimistic in light of the existence of "easy" two curve problem instances say, Ehearly-separable is a highly nonlinear manifold for which one would expect gradient descent to succeed without needing unduly large depth. In fact, such geometries will not admit small certificate norm in general unless the depth is sufficiently large: intuitively, this is a consequence of the operator θ, being ill-conditioned for such geometries."
classes, each of which
1D
10'
.M4
lnf
.M-
Mla.
10
bo
10-2
SnO-1
0.0
Figure 3: The effect of geometry and depth on the certificate. Left: The certificate g computed numerically from the kernel θ for depth == 50 (defined in (3.1)) and the geometry from Figure 1 with a uniform density, graphed over the manifolds. Control of the norm of the certificate implies rapid progress of gradient descent, as reflected in Theorem 3.2. Comparing to Section 1, we note that the certificate has large magnitude near the point minimum distance between the two curves-this is suggestive of the way the geometry sets the difficulty of the fitting problem. Right: To visualize the certificate norm more precisely, we graph the log maggaiuie of the certificate for kernels of varying depth L, viewing them through the are-length paraneterizations H, for the curves (left: M44 right: M_). At a coarse scale, the maximum magnitude decreases as the depth increases; at a finer scale, curvature-assoce resource. See Appendix A for further experimental details.
defects 'smoothed out'. This indicates the role of depth as a fitting
The proof of Theorem 3.1 is novel, both in the context of kernel regression manifolds and in the context of NTK-regime neural network training. We detail the key intuitions for the proof in
Again, the equivalence between difficulty of the certificate problem and the progress of gradient descent on decreasing the error is a consequence of our analysis proceeding in the kernel regime with the square loss using alternate techniques to analyze the dynamics can allow one to prove that neural networks continue to fit such "casy" classification problems efficiently (e.g. [34]).
7

---

Section 4. As suggested above, applying Theorem 3.1 to construct certificate is straightforward: given a suitable setting of L for a two curve problem instance, we obtain an approximate certificate g via Theorem 3.1. Then with the triangle inequality and the Schwarz inequality, we can bound
O N TK [o] Goll = || 1x 12 |199l + 1ICo <ll + | [g] - <ll
and leveraging suitable probabilistic control (see Appendix G) of the approximation errors in the previous expression, as well as on [|5|223 then yields bounds for the certificate problem. Applying the reductions from gradient descent dynamics in the NTK regime to certificates discussed in Section 2.1, we then obtain an end-to-end guarantee for the two curve problem.
Theorem 3.2 (Generalization), Let M be two disjoint smooth, regular, simple closed curves, satisfy- ing (xx x') S 22 all æ, x' E M. For any O < s 1/e, choose I. so that
2 K max
log log (Crroo log())), e
P
CB
(AVI+ Kス
L'L 00 log 9 (1/6) (Lmo)
N L
and fix > O such that C² al S c. Then with probability at least 1 - 8, the parameters obtained at iteration //3//4//(/ [nT)] of gradient descent on the finite sample loss yield a classifier that separates the two manifolds.
The constants c, C² C", "",K,K' > 0 are absolute, and Cp equals { Pmin: P 1(1 (1+tpa)))) )2
is (min (p(M4) (MMM)-MMMM 1)j
constant only depends on μ. P a polynomial poly (Ma, M4. Ms, len(M), A -17 I of degree at most 36, with degree at most 12 when viewed as a polynomial in M3, Ma, Ms and len(M), and of degree al most 24 as a polynomial in -1
Theorem 3.2 represents the first end-to-ene tod guarantee for training deep neural network classify a nontrivial class of -iw-dimensional nonlinear manifolds. We call attention to the fact that the hy- potheses of Theorem 3.2 completely self-contained making reference only intrinsic properties of the data and the architectural hyperparameters of the neural network (as well as poly(log no)). )), and that the result is algorithmic, as it applies to training the network via constant-stepping gradient descent on the empirical square loss and guarantees generalization within I,2 iterations. Furthermore, Theorem 3.2 can be readily extended to the more general setting of regression on curves, given that we have focused on training with the square loss.
4 Proof Sketch
In this section, we provide an overview of the key elements of the proof of Theorem 3.1, where we show that the equation @ [g] Re ( admits solution (the certificate) of small norm. To solve the certificate problem for M, we require a fine-grained understanding of the kernel θ The most natural upproach is formally set g >i= 1 ut) 13 v using the eigendecoopossitonn of O
(just as constructed in Section 2.1 for NTK,, and then argue that this formal expression converges by studying the rate of decay of X; and the alignment of Ç with eigenvectors of Oμ: this is the standard approach in the literature [46, 53]. However, as discussed in Section 1, the nonlinear structure of M makes obtaining a full diagonalization for O,, intractable, and simple asymptotic characterizations of its spectrum are insufficient to prove that the solution g has small norm. Our approach will therefore be more direct: we will study the 'spatial' properties of the kernel θ itself, in particular its rate of decay away from to reduce the study of the operator θ to a simpler, localized operator whose invertibility can be proved using harmonic analysis. We will then differentiability properties of θ to transfer the solution obtained by inverting this auxiliary operator back to the operator O,,- We refer readers to Appendix E for the full proof.
x', and thereby use the network depth L as resource
We simplify the proceedings using two basic reductions. First, with a small amount of auxiliary argu- mentation, can reduce from the study of the operator-with-densit O to the density-free operator
8

---

O. Second, the kernel (xx x²) is function of the angle 2(x, x'), and hence is rotationally invariant.
This kernel is maximized at <(x, x²) 0 and decreases monotonically as the angle increases. reaching its minimum value at < (ar, æ²) æ. If we subtract this minimum value, it should not affect our ability to fit functions, and we obtain a rotationally invariant kernel (x,, æ²) = 86 (<(r, x))) that is concentrated around angle O. In the following, we focus on certificate construction for the kernel O Both simplifications are justified in Appendix E.3.
4.1
The Importance of Depth: Localization of the Neural Tangent Kernel
The first problem one encounters when attempting to directly establish (a property like) invertibility of the operator @ is its action across connected components of M: the operator @ acts by integrating against functions defined on - = .M+ U M_, and although it intuitive that most of its image's values on each component will be due to integration of the input over the same component, there will always some 'cross-talk' corresponding to integration over the opposite component that interferes with our ability to apply harmonic analysis tools. To work around this basic issue (as well as others we will see below), our argument proceeds via a localization approach: we will exploit the fact that as the depth L increases, the kernel O" sharpens and concentrates around its value at æ x', to the extent that we can neglect its action across components of M and even pass to the analysis of an auxiliary localized operator. This reduction is enabled by new sharp estimates for the decay of the angle function & that we establish in Appendix F.3. Moreover, the perspective of using the network depth as resource to localize the kernel 6 and exploiting this to solve the classification problem appears to be new: this localization is typically presented as a deficiency in the literature (e.g. [47]).
At more formal level, when the network is deep enough compared to geometric properties of the curves, for each point æ, the majority of the mass of the kernel (a x²) is taken within small neighborhood d1 x²) < of æ. When (æ, æ²) is small relative to we have d x') R (xx, x²). This allows us to approximate the local component by the following invariant operator:
( - - ---_. ( (())((((()))d.
(4.1)
This approximation has two main benefits: (i) the operator M is defined by intrinsic distance s' s. and (ii) it is highly localized. In fact, (4.1) takes the form of a convolution over the are length parameter s. This implies that M diagonalizes in the Fourier basis, giving an explicit characterization of its eigenvalues and eigenvectors. Moreover, because M is localized, the eigenvalues corresponding to slowly oscillating Fourier basis functions are large, and M stably invertible over such functions. Both of these benefits can be seen as consequences of depth: depth leads to localization, which facilitates approximation by M, and renders that approximation invertible over low- wwwffrquency functions. In our proofs, we will work with a subspace S spanned by low cow-freuuecy basis functions that are nearly constant over a length 2r interval (this subspace ends up having dimension proportional to 1/r; see Appendix C.3 for a formal definition), and use Fourier arguments to prove invertibility of M over S (see Lemma E.6).
4.2 Stable Inversion over Smooth Functions
Our remaining task is to leverage the invertibility of M over S' to argue that θ is also invertible. In doing so, we need to account for the residual θ --M. M. We accomplish this directly, using Neumann series argument: when setting X -112 and the dimension of the subspace S proportional to 1/r, the minimum eigenvalue of M over S exceeds the norm of the residual operator O -M (Lemma E.2). This argument leverages a decomposition of the domain into "near". "far" and "winding" pieces, whose contribution to @ is controlled using the curvature, angle injectivity radius and B Bnnmmeer (Lemma E.8, Lemma E.9, Lemma E0). This guarantees the strict invertibility of O over the subspace S, and yields unique solution gs the restricted equation PsO = C (Theorem 1).
This does not yet solve the certificate problem, which demands near solutions to the unrestricted equation O² [g]] = Ç. To complete the argument, we set g = gs and use harmonic analysis considera-
tions to show that ["]g] is very close to S. The subspace S contains functions that do not oscillate

---

rapidly, and hence whose derivatives are small relative to their norm (Lemma E.23). We prove that O% [g]] is close by controlling the first three derivatives of O ['[g). which introduces dependencies on M,.... M5 in the final statement of our results (Lemma E.27). In controlling these derivatives, we leverage the assumption that sup,, EM (xx, x²) S T 7/2 to avoid issues that arise at antipodal points-we believe the removal of this constraint is purely technical, given our sharp characterization of the decay of 2 and its derivatives. Finally, we move from O back to & by combining near solutions to @ [g]] ( and @0 = 1. and iterating the construction to reduce the approximation error to an acceptable level (Appendix E.3).
5 Discussion
A role for depth. In the setting of fitting functions on the sphere Shh-1 in the NTK regime with unstructured (e.g., uniformly random) data, it is well-known that there very little marginal benefit to using a deeper network: for example, [32. 46, 59] show that the risk lower bound for RKHS methods is nearly met by kernel regression with a 2-layer network's 's NTK in an asymptotic (no + oo) setting, and results for fitting degree-1 1 functions in the nonasymptotic setting [52] are suggestive of similar phenomenon. In a similar vein, fitting the NTK regime with deeper network does not change the kernel's RKHS [41, 42, 45], and in a certain "infinite-depth" limit, the corresponding NTK for networks with ReLU activations, as we consider here, is a spike, guaranteeing that it fails to generalize [47, 50]. Our results are certainly not in contradiction to these facts we consider a setting where the data are highly structured, and our proof' only show that an appropriate choice of the depth relative to this structure is sufficien! to guarantee generalization, not necessary- they nonetheless highlight an important role for the network depth in the NTK regime that has not been explored in the existing literature. In particular, the localization phenomenon exhibited by the deep NTK is completely inaccessible by fixed-depth networks, and simultancously essential to our arguments to proving Theorem 3.2, we have described in Section 4. It is an interesting open problem to determine whether there exist low-dimensional geometries that cannot be efficiently separated without deep NTK, or whether the essential sufficiency of the depth-two NTK persists.
Closing the gap to real networks and data. Theorem 3.2 represents an initial step towards understanding the interaction between neural networks and data with low-dimensional structure, and identifying network resource requirements sufficient to guarantee generalization. There are several important avenues for future work. First, although the resource requirements in Theorem 3.1, and by extension Theorem 3.2, reflect only intrinsic properties of the data, the rates are far from optimal-improveneen
here will demand more refined harmonic analysis argument beyond the localization approach we take in Section 4.1. A more fundamental advance would consist of extending the analysis to the setting of a model for image data, such as cartoon articulation manifolds, and the NTK of a convolutional neural network with architectural settings that impose translation invariance [25, recent results show asymptotic statistical efficiency guarantees with the NTK of a simple convolutional architecture, but only in the context of generic data [60]. The approach to certificate construction we develop in Theorem 3.1 will be of use in establishing guarantees analogous to Theorem 3.2 here, as approach does not require an explicit diagonalization of the NTK.
In addition, extending our certificate construction approach to smooth manifolds of dimension larger than one is natural next step. We believe our localization argument generalizes to this setting: as our bounds for the kernel s are sharp with respect to depth and independent of the manifold dimension, one could seek to prove guarantees analogous to Theorem 3.1 with similar subspace-restriction argument for sufficiently regular manifolds, such as manifolds diffcomorphic to spheres, where the geometric parameters of Section 2.2 have natural extensions. Such generalization would incur at best an exponential dependence of the network on the manifold dimension for localization in high dimensions.
More broadly, the localization phenomena at the core of our argument appear to be relevant beyond the regime in which the hypotheses of Theorem 3.2 hold: we provide a preliminary numerical experiment to this end in Appendix A.3. Training fully-connected networks with gradient descent on a simple manifold classification task, low training error appears to be easily achievable only when the decay scale of the kernel is small relative to the inter- mnter-manifodd distance even at moderate depth and width, and this decay scale is controlled by the depth of the network.
10

---

Funding Transparency Statement and Acknowledgements
This work was supported by a Swartz fellowship (DG), by fellowship award (SB) through the National Defense Science and Engineering Graduate (NDSEG) Fellowship Program, sponsored by the Air Force Research Laboratory (AFRL), the Office of Naval Research (ONR) and the Army Research Office (ARO), and by the National Science Foundation through grants NSF 1733857, NSF 1838061, NSF 1740833, and NSF 174039. We thank Alberto Bietti for bringing to our attention relevant prior art on kernel regression on manifolds.
References
[1] Peter N Belhumeur and David J Kriegman. "What is the set of images of an object under all possible illumination conditions?" International Journal of Computer Vision 28.3 (1998), Pp. 245-260.
[2] T Roweis and L K Saul. "Nonlinear dimensionality reduction by locally linear embedding". Science 290.5500 (Dec. 2000), pp. 2323-2326.
[3] Joshua B Tenenbaum, Vin de Silva, and John CI Langford. "A Global Geometric Framework for Nonlinear Dimensionality Reduction". Science 290.5500 (Dec. 2000), pp. 2319-2323.
[4] Mikhail Belkin and Partha Niyogi. "Laplacian Eigenmaps for Dimensionality Reduction and Data Representation". Neural Comput. 15.6 (June 2003), pp. 1373-1396.
[5] David L Donoho and Carrie Grimes. "Image manifolds which isometric to Euclidean space" Journal of mathematical imaging and vision 23.1 (2005), pp. 5-24.
[6] Lawrence Cayton and Sanjoy Dasgupta. "Robust Euclidean embedding". Proceedings of the 23rd international conference on Machine learning. ICML '06. Pittsburgh, Pennsylvania, USA: Association for Computing Machinery, June 2006, pp. 169-176.
[7] Robert M Bell and Yehuda Koren. "Lessons from the Netflix prize challenge". SIGKDD Explor. Newsl. 9.2 (Dec. 2007), pp. 75-79.
[8] Y Koren, R Bell, and C Volinsky. "Matrix Factorization Techniques for Recommender Sys- tems". Computer 42.8 (Aug. 2009), pp. 30-37. [9] T Hangelbroek, J Narcowich, and J D Ward. "Kernel Approximation on Manifolds I: Bounding the Lebesgue Constant". SIAM J. Math. Anal. 42.4 (Jan. 2010), pp. 1732-1760.
[10] Chaitanya Ekanadham, Daniel Tranchina, and Eero P Simoncelli. "A blind sparse deconvolu- tion method for neural spike identification". Adv. Neural lnf. Process. Syst. (2011).
[11] Edward Fuselier and Grady B Wright. "Scattered Data Interpolation on Embedded Subman- ifolds with Restricted Positive Definite Kernels: Sobolev Error Estimates". SIAM Numer. Anal. 50.3 (Jan. 2012), pp. 1753-1776.
[12] Xu Wang, Konstantinos Slavakis, and Gilad Lerman. "Multi-Manifold Modeling in Non- Euclidean spaces". Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics. Vol. 38. Proceedings of Machine Learning Research. San Diego, California, USA: PMLR, 2015, pp. 1023-1032.
[13] Bracha Laufer-Goldshtein Ronen Talmon, and Sharon Gannot. "Semi-supervised sound source localization based on manifold regularization". JEEE/ACM Transactions on Audio, Speech, and Language Processing 24.8 (2016), pp. 1393-1407.
[14] Peng Xiong, Hongrui Wang, Ming Liu, Feng Lin, Zengguang Hou, and Xiuling Liu. "A stacked contractive denoising auto-encoder for ECG signal denoising". Physiological measurement 32.12 (2016), p. 2214.
[15] Ronen Basri and David W Jacobs. "Efficient Representation of Low-Dimensionnll Manifolds using Deep Networks". 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[16] Jason E Chung, Jeremy F Magland, Alex H Barnett, Vanessa M Tolosa, Angela C Tooker, Kye Y Lee, Kedar G Shah, Sarah H Felix, Loren M Frank, and Leslie F Greengard. "A Fully Automated Approach to Spike Sorting". Neuron 95.6 (Sept. 2017), 1381-1394.e6.
[17] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. "Learning and Generalization in Overpa- rameterized Neural Networks, Going Beyond Two Layers" (Nov. 2018). arXiv: 1811. 04918 [CS.
11

---

[18] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. "A Convergence Theory for Deep Learning via Premrerramtttiiaaioon"" (Nov. 2018). arXiv: 1811. 03962 [cs.LG].
[19] Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles-Weed "Massively scalable Sinkhorn distances via the Nyström method" (Dec. 2018). arXiv: 1812. 05189 [stat.ML]
[20] Karol Antezak. "Deep Recurrent Neural Networks for ECG Signal Denoising" (July 2018). arXiv: 1807. 11551 [cs.NE].
[21] Simon Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. "Gradient Descent Provably Optimizes Over-parameterized Neural Networks" (Oct. 2018). arXiv: 1810.02054 LG].
[22] Hunter Gabbard, Michael Williams, Fergus Hayes, and Chris Messenger. "Matching matched filtering with deep networks for gravitational-wave astronomy". Physical review letters 120.14 (2018), p. 141103.
[23] Arthur Jacot, Franck Gabriel, and Clément Hongler. "Neural Tangent Kernel: Convergence and Generalization in Neural Networks" (June 2018). arXiv: 1806. 1806.07572 07572 [cs .GG. [24] Song Mei, Andrea Montanari, and Phan-Minh Nguyen. "A Mean Field View of the Landscape of Two--ayers Neural Networks" (Apr. 2018). arXiv: 1804. 06561 Mstat.ML].
[25] Roman Novak, Lechao Xiao, Jachoon Lee, Yasaman Bahri, Greg Yang. Jiri Hron, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl-Dickstein. "Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processes" (Oct. 2018). arXiv: 1810. 05148 [stat.M]].
[26] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. "Learning and Generalization in Overpa- rameterized Neural Networks, Going Beyond Two Layers". Advances in Neural Information Processing Systems. Vol. 32. 2019.
[27] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Granned Analysis of Optimization and Generalization for Overparameterizee Two-Layer Neural Networks". Proceedings of the 36th International Conference on Machine Learning. Vol. 97, Proceedings of Machine Learning Research. PMLR, 2019, pp. 322-332.
[28] Yuan Cao and Quanquan Gu. "Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks". Advances in Neural Information Processing Systems. Vol. 32.
2019.
[29] Minshuo Chen, Haoming Jiang, Wenjing Liao, and Tuo Zhao. "Nonparametrie Regression on Low-Dimensional Manifolds using Deep ReLU Networks" (Aug. 2019). arXiv: 1908.01842
LG].
[30] Timothy D Gebhard, Niki Kilbertus, Ian Harry, and Bernhard Schölkopf. "Convolutional neural networks: A magic bullet for gravitational-war wave detection?" Physical Review D 100.6 (2019), p. 063015.
[31] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "Limitations of Lazy Training of Two-layers Neural Networks" (June 2019). arXiv: 1906. 08899 [Mt
[32] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "Linearized two-layers neural networks in high dimension" arXiv preprint vrXiv:/9044 /2/9/ (2019).
[33] S Goldt, M Mézard, F Krzakala, and L Zdeborová. "Modelling the influence of data structure on learning in neural networks". arXiv preprint arXiv (2019).
[34] Ziwei Ji and Matus Telgarsky. "Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks" (Sept. 2019). arXiv: 1909 12292 [cs LG].
[35] Zhiyuan Li, Ruosong Wang, Dingli Yu, Simon S Du, Wei Hu, Ruslan Salakhutdinov, and Sanjeev Arora. "Enhanced Convolutional Neural Tangent Kernels" (Nov. 2019). arXiv: 1911. 00809 [cs.LG]
[36] Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai "On the Multiple Descent of Minimum- Norm Interpolants and Restricted Lower Isometry of Kernels" (Aug. 2019). arXiv: 1908. 10292 [math.ST]
[37] Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi. "Generalization Guar- antees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian" arXiv preprint
(June 2019). arXiv: 1906. 05392 [cs LG].
[38] Schmidt-Hieher "Deep relu network approximation of functions on a manifold". arXiv preprint arXiv: 19060559000006555 00695 (2019).
12

---

[39] Gilad Yehudai and Ohad Shamir. "On the Power and Limitations of Random Features for
Understanding Neural Networks" (Apr. 2019). arXiv: 1904. 00687 [cs. .GG.
[40] Zeyuan Allen-Zhu and Yuanzhi Li. "Backward Feature Correction: How Deep Learning
Performs Deep Learning" (Jan. 2020). arXiv: 2001 04413 [cs.LG],
[41] Alberto Bietti and Francis Bach. "Deep Equals Shallow for ReLU Networks in Kernel Regimes"
(Sept. 2020). arXiv: 2009 14397 [stat.
[42] Lin Chen and Sheng Xu. "Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS" (Sept. 2020). arXiv: 2009. 10683 [ca. LG].
[43] Sky C Cheung. John Y Shin, Yenson Lau, Zhengyu Chen, Ju Sun, Yugian Zhang, Marvin A Müller, Ilya M Eremin, John N Wright, and Abhay N Pasupathy. "Dictionary learning in Fourier-transform scanning tunneling spectroscopy". Nat. Commun. 11.1 (Feb. 2020). p. 1081.
[44] Alexander Cloninger and Timo Klock. "Deep neural networks adapt to intrinsic dimensionality beyond the target domain" (Aug. 2020). arXiv: 2008. 02545 [stat.Mi MML].
[45] Amnon Geifman, Abhay Yadav, Yoni Kasten, Meirav Galun, David Jacobs, and Ronen Basri. "On the Similarity between the Laplace and Neural Tangent Kernels" (July 2020). arXiv: 2007. 01580 [Cs.
[46] Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "When Do Neu- ral Networks Outperform Kernel Methods?" (June 2020). arXiv: 2006. 13409
[47] Kaixuan Huang, Yuqing Wang. Molei Tao, and Tuo Zhao. "Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? A Neural Tangent Kernel Perspective"
(Feb. 2020). arXiv: 2002.06262
[48] Teeratom Kadeethum, Thomas M Jørgensen, and Hamidreza M Nick. "Physics-informed neural networks for solving nonlinear diffusivity and Biot's equations". PloS one 15.5 (2020), e0232683.
[49] Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. "Learning Parammerrett Two-Layer ReLU Neural Networks beyond NTK" (July 2020). arXiv: 2007. 04596 [cs.LG].
[50] Tengyuan Liang and Hai Tran-Bach Bach. "Mehler's Formula, Branching Process, and Composi-
tional Kernels of Deep Neural Networks" (Apr. 2020). arXiv: 2004. 04767 [stat. MM]a
[51] Andrew McRae, Justin Romberg, and Mark Davenport. "Sammle complexity and effective dimension for regression on manifolds" (June 2020). arXiv: 2006. 07642 [stat.ML]
[52] Andrea Montanari and Yiqiao Zhong. "The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training" (July 2020).
arXiv: 2007. 12826
[stat.ML] MLJ.
[53] Atsushi Nitanda and Taiji Suzuki. "Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime". arXiv preprint arXiv:2006. 12297 (2020). [54] Lawrence K Saul. "A tractable latent variable model for nonlinear dimensionality reduction". Proc. Natl. Acad. Sci. U. S. A. 117.27 (July 2020). pp. 15403-15408
[55] Taiji Suzuki. "Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics". Advances in Neural Information Processing Systems. Vol. 33. Curran Associates, Inc., 2020, pp. 19224- 19237.
[56] Akshay Agrawal, Alnur Ali, and Stephen Boyd. 2021). arXiv: 2103. 025559 LG].
Embedding" (Mar.
[57] Sam Buchanan, Dar Gilboa, and John Wright. "Deep Networks and the Multiple Manifold Problem". International Conference on Learning Representations. 2021.
[58] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. "How Much Over- parameterizzaionn Is Sufficient to Learn Deep ReLU Networks?" International Conference on Learning Repre- sentations. 2021.
[59] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration" (Jan. 2021). arxiv: 2101. 10588 [math.sT].
[60] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. "Learning with invariances in random features and kernel models" (Feb, 2021). arXiv: 2102. 13219 [stat.ML]
[61] Phil Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. "The Intrinsic Dimension of Images and Its Impact on Learning". International Conference on Learning Representations (2021).
13

---

[62] Maria Refinetti, Sebastian Goldt, Florent Krzakala, and Lenka Zdeborová. "Classifying high- dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed" (Feb.
2021). arxiv: 11742 [cs.LG],
[63]
Mo Zhou, Rong Ge, and Chi Jin. "A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network" (Feb, 2021). arXiv: 2102. 02410 [Cs.LG].
14


Reviews:
[{"review_id": "jKmT4TJxKsU", "reviewer": "Reviewer_K4pY", "summary": "This paper considers classification using wide (NTK) neural networks. The data are assumed to concentrate on two separable one-dimensional curves on the unit sphere. As long as the width of the network is sufficiently large, well trained neural network can perfectly classify the two curves under some regularity conditions of the curves.\n\nA synthesis of NTK and low-dimensional data is a reasonably novel direction, despite that NTK theory has been well studied in the past few years. From a technical point of view, since the support of the data is no longer the whole unit sphere, the kernel here exhibits difficulty in analyzing. The paper makes plenty of efforts to explain this idea with both verbal and graphical illustrations, which is helpful. As discovered by the theoretical results, depth plays a role in this curve classification problem, whereas on the whole unit sphere, existing works demonstrate little impact of increased depth to the NTK. I feel like this is an interesting finding and contributes to community.\n\nThe presentation of the paper is well-organized, especially the preliminaries of some differential geometry and two curve problem.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I have the following questions for the authors, which cover the clarity and quality of the results.\n\n1) Approximate fixed kernel v.s. Kernel at initialization. In Line 137, the evolution of $\\zeta_k$ is written using the kernel at initialization. In fact, this should be considered as an approximation, which is already noted by the authors in Line 129. Does the generalization result (Theorem 3.2) takes into account the shift of the kernel during training, or it simply takes the kernel as a fixed one. If the latter is the case, what is the difficulty to analyze the former case?\n\n2) Injectivity radius and clover number. In Riemannian geometry, injectivity radius refers to the smallest radius so that the exponential map is a local diffeomorphism. The introduction of the injectivity radius in the paper seems to alter the definition, although from a geometric point of view, they are related. A discussion may be needed. Moreover, in injectivity radius and clover number, certain choices of $\\tau_1$ and $\\tau_2$ is provided without explanation. Does it have a direct geometric meaning? or it is for the sake of theoretical convenience?\n\n3) Network size. In Theorem 3.1 and Theorem 3.2, we see the lower bound of depth $L$ is a polynomial with a relatively high degree. Further, the width $n$ in Theorem 3.2 scales as $L^{99}$, which is extremely large. This is partially due to the NTK analysis, however, I am curious whether the authors attempt to optimize the network size. Maybe more interestingly, can the authors comment on how does the network size depend on the intrinsic dimension of the curves? (This is a relatively minor point, as the authors have already presented a discussion on extensions to image data and CNNs.)\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed limitations of the work in Section 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24 hours"}, "extra_text": {}}, {"review_id": "S2BlpK1JDHA", "reviewer": "Reviewer_skyx", "summary": "This paper studies the binary classification problem of datas from two disjoint curve on the unit ball using deep neural network. The authors present a systematic analysis over the geometric difficulty of the problem and relate this to the depth of the neural network. In the NTK region, they provide the generalization analysis based on certain assumptions on width and number of samples. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strength:\n\nThe curve classification problem is well-motivated and related works are exhaustively described. They present an insightful theorem about the depth of the neural network to ensure the existence of a certificate problem, which is critical to the convergence analysis of two curves problem in NTK region. They also provide an end-to-end guarantee for the generalization property of two curves problem.  \n\nWeakness and comments:\n\nThe power 99 of $L$ in the expression of the certificate problem parameter $n$ and the power 10 of $L$ in the expression of the sample number $N$ is a bit large, depending on the lower bound of the neural network depth $L$ is large. I’m wondering if these bounds can be further improved.\n\nIt will be helpful to provide numerical experiments even on toy examples to better illustrate the generalization guarantee in Theorem 3.2. \n\nMinors:\n\nIn line 122, $f_*$ shall be $\\mathbb{R}^{n_0}\\to\\{-1,1\\}$. \n\nThe linear operator $\\boldsymbol{\\Theta}_\\mu^\\mathrm{NTK}$ is not explicitly defined. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "KTLXQ7wY5e6", "reviewer": "Reviewer_t2Mz", "summary": "This paper proves that deep fully-connected neural network with gradient descent is able to successfully classify two separated curves in the NTK regime. In particular, the paper defines several key intrinsic properties of the data (two curves) which characterize the required neural network depth, width and sample complexity to obtain a classifier that separates two curves. The results show that if the nonlinearity of the curves increases, the depth requirement also increases, which shows that neural network depth is important. As far as I know, I agree with the authors' claim that this is the first paper that provides generalization guarantees for training a deep neural network to classify structured data. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper tries to answer the following question: how large network and how many samples do we need to learn a classifier on structured data. This is a critical question in deep learning theory especially in NTK theory. Therefore, the theoretical results are novel and important. I also believe the techniques developed, especially about the localization effects of NTK with DNN, might be useful to the community. However, there are a few questions and concerns about the paper. \n\n1. The paper assumes the structured data is a two disjoint smooth curves on the unit sphere. I am wondering if it is possible to extend one-dim curves to multi-dim manifold. What's the technical difficulty? \n\n2. The definition of clover number and injectivity radius includes those between inner-class samples.  I didn't find the intuition why we need to include these pairs in these two properties. For example, what if we define $\\Delta = \\text{inf}_{x\\in \\mathcal{M}^+, x'\\in \\mathcal{M}^-} {\\angle(x, x')}$ instead? As the authors mentioned in Line 235-237, a shallow network can learn a linearly-separable binary classification problem, where the geometric properties among the inner-class samples don't matter too much. \n\n3. The required depth in Theorem 3.1 and 3.2 seems quite large that is far away from practical cases. \n\n4. The paper gives a great introduction on low-dimensional structure in real applications.  However, I think there is some room for improving the related work section. For example,  more detailed comparison between the results of this paper and the relevant literature can be discussed. I think this paper is also relevant, Arora, Sanjeev, et al. \"Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.\" International Conference on Machine Learning. PMLR, 2019.\n\n5. The left part of Fig. 2 seems to show intersection between two different classes while the right part is showing self-intersection inside one class. Also, t-SNE project is a projection from high-dimension space to 2-dim space. The self-intersection might not happen in the original high-dimension space. So the right part of Fig. 2 seems not a good example to me. Also, as mentioned in Appendix A.1, there is a significant error in Fig. 2, which needs to be fixed. \n\n6. A minor: in Line 140, should $\\tau < \\lambda_1$ be $\\tau  \\lambda_1 < 1$?\n\nOverall, I think the paper is towards an important direction but the current version is not ready for publication. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is a theory paper. I don't see any potential negative societal impact. The limitations of the paper are well discussed throughout the paper. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "3_JI2JiO5Di", "reviewer": "Reviewer_2zgs", "summary": "This paper studied a binary classification problem for two disjoint smooth curves using a deep ReLU neural network. It proved that when the network depth is large relative to the geometric properties of the curves and when the network width and number of samples is polynomial in the depth, gradient descent can learn to correctly classify all the points on the two curves. The analysis is in the NTK regime and the main technical contribution is to prove that when the network depth is large enough, the corresponding neural tangent kernel can classify the two curves (certificate problem). Analyzing this neural tangent kernel turns out to be very challenging and requires highly non-trivial techniques. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I think this is a solid theory paper studying the training of neural networks given data with low-dimensional structures. Currently, there are very few theoretical results dealing with data with low-dimensional structures. So I think this paper is a good step along this line. Although the result is only for two curves, analyzing this setting is already very challenging.\n\nThe analysis is in the NTK regime, and the main contribution of this paper is to solve the certificate problem (showing the NTK can approximate the decision boundary with small L_2 norm). Theorem 3.1 requires novel techniques and intense proofs. It shows that the NTK can approximate the decision boundary when the depth of the network is polynomial in the injectivity radius and exponential in the curvature. In the proof, increasing the depth of the network makes the kernel more localized and help with the certificate problem. This is interesting since it gives one perspective on the advantages of deeper neural networks.\n\nMy main concern for this paper is that the result is restricted in the NTK regime. But we know that the neural network in practice is often not in the NTK regime and the NTK performed worse than trained neural networks. This makes me doubt to what extend this theory can explain the neural network training in practice (beyond the NTK regime). For example, what's the role of network depth if we train a network beyond the NTK regime to classify two curves.\n\nThat being said, I still think this is a solid theoretical contribution to the analysis of NTK and kernel regression under structured data. I think the techniques used in this paper, in particular the proof for the certificate problem, can be very useful in other NTK research. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies classification problems where the problem data are two disjoint curves using deep neural networks, and provides a Neural Tangent Kernel (NTK) based analysis of generalization. The authors identify key concepts related to the geometric difficulty of the problem and relate it to the depth of the network. The reviewers all agreed that the paper contains interesting ideas and insightful theoretical results, and recommended acceptance. A few reviewers expressed minor concerns and suggestions. Please take into account the updated reviews when preparing the final version to accommodate the requested changes. Thank you for your submission to NeurIPS.
Decision: Accept (Poster)