Deep Networks Provably Classify Data on Curves

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.

NeurIPS 2021

References in corpus (7)

• Enhanced Convolutional Neural Tangent Kernels
• Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
• Learning with invariances in random features and kernel models
• The Intrinsic Dimension of Images and Its Impact on Learning
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Limitations of Lazy Training of Two-layers Neural Networks
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK