mlsanityData to 7 Oct 2026

Deep Networks Provably Classify Data on Curves

arXiv 2107.14324 ↗First posted 29 Jul 2021stat.ML cs.LG math.OCcited by 6

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 42 of its 62 references that are in the map. First posted on arXiv 29 Jul 2021.

Builds on

42 of 62 references.

References · 42

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  2. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  3. 2018Gradient Descent Provably Optimizes Over-parameterized Neural Networkscited by 655
  4. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  5. 2018A Mean Field View of the Landscape of Two-Layers Neural Networkscited by 463
  6. 2018Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layerscited by 340
  7. 2021The Intrinsic Dimension of Images and Its Impact on Learningcited by 307
  8. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
  9. 2018Bayesian Deep Convolutional Networks with Many Channels are Gaussian Processescited by 164
  10. 2019Linearized two-layers neural networks in high dimensioncited by 155
  11. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  12. 2019Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networkscited by 120
30 more
  1. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  2. 2019On the Power and Limitations of Random Features for Understanding Neural Networkscited by 103
  3. 2021Learning with invariances in random features and kernel modelscited by 89
  4. 2019Limitations of Lazy Training of Two-layers Neural Networkscited by 87
  5. 2019How Much Over-parameterization Is Sufficient to Learn Deep ReLU Networks?cited by 84
  6. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
  7. 2020Deep Equals Shallow for ReLU Networks in Kernel Regimescited by 83
  8. 2019Enhanced Convolutional Neural Tangent Kernelscited by 76
  9. 2020On the Similarity between the Laplace and Neural Tangent Kernelscited by 76
  10. 2020Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHScited by 74
  11. 2019Deep ReLU network approximation of functions on a manifoldcited by 73
  12. 2019Nonparametric Regression on Low-Dimensional Manifolds using Deep ReLU Networks : Function Approximation and Statistical Recoverycited by 73
  13. 2019Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobiancited by 67
  14. 2021Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeedcited by 67
  15. 2020Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspectivecited by 60
  16. 2021A Local Convergence Theory for Mildly Over-Parameterized Two-Layer Neural Networkcited by 47
  17. 2018Massively scalable Sinkhorn distances via the Nystr"om methodcited by 40
  18. 2020Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regimecited by 35
  19. 2020Deep Networks and the Multiple Manifold Problemcited by 35
  20. 2021Minimum-Distortion Embeddingcited by 26
  21. 2020Physics-informed Neural Networks for Solving Nonlinear Diffusivity and Biot's equationscited by 20
  22. 2020Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTKcited by 18
  23. 2018Deep Recurrent Neural Networks for ECG Signal Denoisingcited by 14
  24. 2020Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamicscited by 14
  25. 2016Efficient Representation of Low-Dimensional Manifolds using Deep Networkscited by 13
  26. 2019Modelling the influence of data structure on learning in neural networks: the hidden manifold modelcited by 13
  27. 2019Convolutional neural networks: a magic bullet for gravitational-wave detection?cited by 12
  28. 2020Sample complexity and effective dimension for regression on manifoldscited by 8
  29. 2020Mehler's Formula, Branching Process, and Compositional Kernels of Deep Neural Networkscited by 4
  30. 2015Semi-Supervised Sound Source Localization Based on Manifold Regularizationcited by 3

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 3; 2023: 1; 2024: 1.

6 papers.

  1. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  2. 2022On the Principles of Parsimony and Self-Consistency for the Emergence of Intelligencecited by 50
  3. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  4. 2022Effects of Data Geometry in Early Deep Learningcited by 12
  5. 2021Partial Domain Adaptation without Domain Alignmentcited by 11
  6. 2024Defining Neural Network Architecture through Polytope Structures of Datasetcited by 2