Deep Networks Provably Classify Data on Curves
  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.
