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 wwwddimeniionaltty: 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 diffiusio 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') (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, // 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)
f- 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, (a:) 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, (2), 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 See 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 concentrated on directions corresponding to large eigenvalues. We call the construction of such a function the certificate problem [57, Eqn. (2.3)):
NTK [g] = Çu-in in this situation, most of the energy of Ço must be
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-inersset.. 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 To with respect to are length. Because our parameterization is unit speed. (s))2 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 }}
((M) = sup NM ([x') dd(( 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 =
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, @ ||, 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|113 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) (MM4)-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, M4, 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 (< 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 [cs. 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": "raEAvmIoLST", "reviewer": "Reviewer_qqCj", "summary": "The paper considers the problem of binary classification where the data from the two classes lie on two disjoint nonlinear curves in the unit sphere. They show that given a sufficiently overparameterized deep neural network, gradient descent from a random initialization converges to a classifier which separates the two classes. They show a reduction to the certificate problem in Buchanan et al. and similarly utilize the NTK regime to prove convergence.", "questions": "", "limitations": "", "rating": 8, "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": "Overall, I find this paper to be an excellent theoretical contribution. It relies heavily on the work by Buchanan et al. but nevertheless, it is a significant contribution. These are some of the first generalization bounds I have seen concerning data which is not necessarily linearly-separable and though they are probably not tight, they are powerful results.\n\n- Originality: The work relies heavily on the paper by Buchanan et al. and resolves some of the open problems asked there while extending their results.\n\n- Clarity: The paper is extremely well written. Despite being an extremely technical result, the main paper provides good intuition and proof sketches relegating the technical details to the appendix.\n\n- Significance: I think this is a good result that takes us in the right direction towards understanding generalization and deep learning but I have some questions:\n    1. I see that this result assumes that the gradients are exact i.e, the optimization algorithm is full gradient descent. Does a similar result hold for Stochastic Gradient Descent? In practice, it seems that the randomness is an important element. Perhaps the low-dimensional structure is what helps you avoid local minima?\n    2. The result shows that GD eventually reaches a solution that separates the classifier when one uses MSE. However, this would require sufficiently dense sampling (as is mentioned in the paper). Does the analysis provide any insight into whether it would eventually reach a max-margin classififier if one used hinge-loss, say?\n    3. This is perhaps an oversight on my part, but I found the usage of the one-dimensional setting very subtle and tricky to identify even in the theorem statements. Is there a significant benefit to assuming the data to lie in a high dimensional space if it comes from a 1-dimensional submanifold?\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes. Since the results are theoretical, I don't think they need to consider the societal impact.\nHowever, they have addressed their limitations. I would also like them to include a more detailed discussion on \"Closing the gap to real networks and data\" including some of my questions above, if possible.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "aDRIHN57KE", "reviewer": "Reviewer_haaa", "summary": "This paper studies the problem of classifying data drawn from two disjoint smooth curves on the unit sphere using a deep fully-connected neural network. The work proves that certificates can exist as long as the network depth is sufficiently large. The main tool used in the paper is NTK and the author claims that this is the first generalization guarantee for deep networks with nonlinear data that depends only on intrinsic data properties.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "Strengths:\n1. The paper solves the open problem left by [55], which is the existence of the certificate in multiple manifold problems. The significance and the originality of the paper are fairly high.\n2. The paper is generally well-written, with sufficient analysis after each theorem and also figure demonstrations.\n3. The proof is highly technical. The idea to localize NTK and then to use harmonic analysis to prove its invertibility may be of independent interest in the theory community.\n\nWeaknesses:\n1. The paper can enhance its readability by providing more preliminary introduction on NTK on manifold problems. The current version seems too dense and difficult to follow when I first read it.\n2. In both theorem 3.1 and 3.2, the lower bound of depth $L$  is negatively correlated to the clover number. However the clover number is usually very small, so this will make the lower bound of $L$ extremely large?\n\n=================\n\nAfter reading the rebuttal and other reviewers' comments, I decide to maintain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper seems not to address the limitations and potential negative social impact. Personally, I suggest the author to provide some numerical experiments to validate their results, despite considering it is a theoretical paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}, {"review_id": "YucYrXlfWAh", "reviewer": "Reviewer_jk5n", "summary": "The paper studies using neural network to classify two disjoint low-dimensional submanifolds. Following the idea from Deep Networks and the Multiple Manifold Problem (Sam Buchanan, Dar Gilboa, and John Wright, 2021), the authors considered the certificate problem and provided some sufficient conditions for the existence of such a certificate.", "questions": "", "limitations": "", "rating": 4, "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 studies the classification of two disjoint low-dimensional submanifolds. It closely follows the previous work Deep Networks and the Multiple Manifold Problem (Sam Buchanan, Dar Gilboa, and John Wright, 2021). The authors reduced to consider the certificate problem.\n\nOverall, the paper is not good enough for acceptance. The major contribution lies in Theorem 3.1 and 3.2, which gives some sufficient conditions for the existence of such a certificate. However, the authors didn't provide any comments and discussion on these sufficient conditions. A careful discussion of the dependence of the network depth L on the parameters related to the target manifolds is necessary. In addition, based on the lower bound on the network depth L, the theorem suggests a very strong requirement on the network depth. The authors should consider some simple examples to give a quantitative sense on these parameters of the curves and further the depth L. Some simulations and real data examples are also needed to support the main theorems.\n\nThe paper also has some typos. To name a few, line 122, the domain and range of f*; line 166, the range of sigma. Also the paper has some syntax mistakes. The authors need a careful modification.\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper lacks careful discussion on the dependence of the network depth L from both theoretical and practical perspective. Some toy examples are recommended to illustrate the main idea of the theorems.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "ImGA9gScAIQ", "reviewer": "Reviewer_xaXB", "summary": "This paper fits into an important line of work studying implicit bias of neural networks. In order to address the question of what do neural networks learn, the paper develops a \"theory of data\" -- it identifies a geometric property of data that allows neural networks to provably learn with gradient descent. This property is that the data lies on two disjoint one-dimensional curves -- the label is +1 on one of the curves, and -1 on the other curve. Guarantees on learning are given in terms of the separation Delta of these curves, and their curvature kappa. \n", "questions": "", "limitations": "", "rating": 8, "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": "Overall impression\nThe result is presented clearly and is easy to follow. As far as I know, the result is new.\n\nThe result is based on the framework of the recent paper \"DEEP NETWORKS AND THE MULTIPLE MANIFOLD PROBLEM\" by Buchanan et al. That paper reduces learning in the neural tangent kernel regime to proving that there is a \"certificate\" for the data. The certificate problem amounts to finding low-norm approximate solution to a certain linear system involving the neural tangent kernel. \n\nHowever, Buchanan et al. paper does not prove the existence of a certificate. This is the main new technical element in this paper: a constructive proof of the certificate problem for a setting with a nonlinear data. The proof uses the fact that as the depth of the network increases the kernel localizes.\n\nI am on the fence about this paper, but recommend acceptance, since I found the results illuminating about the power of deep networks in the NTK regime. Nevertheless, a substantial counterargument against acceptance could be that the learning proved in this paper can just as simply be achieved by classical kernel methods with kernels that are sufficiently local -- instead of deep neural nets.\n\nIn any case, this paper opens some interesting future directions:\n(A) trying to extend this result to scenarios in which data lies on d-dimensional submanifolds, for d > 1. This would be substantially more convincing, and would match practice more closely. It seems that the current technique to find a certificate has an exponential dependence on the dimension d. What extra assumptions could be placed on the geometric structure of the data in order to avoid such an exponential dependence?\n(B) does high depth provably help in the NTK regime? E.g., can the nonlinear data learned in this paper be provably learned with a depth-2 NTK?\n\nMinor comments\n— Line 139-140: “In particular, with bounded step size tau < lambda_1”. Why isn’t it tau < 1 / (lambda_1)?\n\n— Lines 149-151: when you introduce the certificate problem, it could be helpful to the reader to refer to the result in https://arxiv.org/pdf/2008.11245.pdf.", "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": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper analyzes the generalization of deep neural networks for data on curves. There is some disagreement among reviewers. One reviewer raised concerns regarding the clarity and novelty of the presented results and missing supporting experiments. The results are a bit difficult to decipher, and also some polynomial terms are of very high orders, and some critical regularity conditions are insufficiently explained. The paper could be strengthened if these concerns could be addressed.
Decision: Accept (Poster)