Deep Networks Provably Classify Data on Curves
arXiv:2107.14324
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.
arXiv commentNeurIPS 2021
References in corpus (25)
- Neural Tangent Kernel: Convergence and Generalization in Neural Networks
- A Convergence Theory for Deep Learning via Over-Parameterization
- Gradient Descent Provably Optimizes Over-parameterized Neural Networks
- Matching matched filtering with deep networks in gravitational-wave astronomy
- Convolutional neural networks: a magic bullet for gravitational-wave detection?
- Physics-informed Neural Networks for Solving Nonlinear Diffusivity and Biot's equations
- Deep Recurrent Neural Networks for ECG Signal Denoising
- Enhanced Convolutional Neural Tangent Kernels
- When Do Neural Networks Outperform Kernel Methods?
- Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
- Kernel Approximation on Manifolds I: Bounding the Lebesgue Constant
- Deep ReLU network approximation of functions on a manifold
- Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian
- Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
- On the Power and Limitations of Random Features for Understanding Neural Networks
- 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
- Massively scalable Sinkhorn distances via the Nyström method
- On the Multiple Descent of Minimum-Norm Interpolants and Restricted Lower Isometry of Kernels
- On the Similarity between the Laplace and Neural Tangent Kernels
- Limitations of Lazy Training of Two-layers Neural Networks
- Deep Equals Shallow for ReLU Networks in Kernel Regimes
- A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Network
- Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK