Deep Networks and the Multiple Manifold Problem

Sam Buchanan, Dar Gilboa, John Wright

Abstract: We study the multiple manifold problem, a binary classification task modeled on applications in machine vision, in which a deep fully-connected neural network is trained to separate two low-dimensional submanifolds of the unit sphere. We provide an analysis of the one-dimensional case, proving for a simple manifold configuration that when the network depth $L$ is large relative to certain geometric and statistical properties of the data, the network width $n$ grows as a sufficiently large polynomial in $L$, and the number of i.i.d. samples from the manifolds is polynomial in $L$, randomly-initialized gradient descent rapidly learns to classify the two manifolds perfectly with high probability. Our analysis demonstrates concrete benefits of depth and width in the context of a practically-motivated model problem: the depth acts as a fitting resource, with larger depths corresponding to smoother networks that can more readily separate the class manifolds, and the width acts as a statistical resource, enabling concentration of the randomly-initialized network and its gradients. The argument centers around the neural tangent kernel and its role in the nonasymptotic analysis of training overparameterized neural networks; to this literature, we contribute essentially optimal rates of concentration for the neural tangent kernel of deep fully-connected networks, requiring width $n \gtrsim L\,\mathrm{poly}(d_0)$ to achieve uniform concentration of the initial kernel over a $d_0$-dimensional submanifold of the unit sphere $\mathbb{S}^{n_0-1}$, and a nonasymptotic framework for establishing generalization of networks trained in the NTK regime with structured data. The proof makes heavy use of martingale concentration to optimally treat statistical dependencies across layers of the initial random network. This approach should be of use in establishing similar results for other network architectures.

Introduction

Deep neural networks have demonstrated remarkable success in classifying high-dimensional data, such as images. A prevalent hypothesis in machine learning is that such data often lie on or near low-dimensional "manifolds" embedded within the high-dimensional input space. Despite empirical success, providing a rigorous mathematical foundation for how these networks learn to separate such structured data remains a significant challenge. Most existing theoretical guarantees focus on finite datasets or simple distributions like Gaussians, which fail to capture the intrinsic geometric structure of real-world data.

Real-world data often lies on low-dimensional manifolds (a). The paper models this as the classification of submanifolds on a sphere (b).

This paper addresses the Multiple Manifold Problem: can a deep network, trained on a finite number of samples, learn a decision boundary that perfectly separates two disjoint manifolds? Specifically, the authors investigate how architectural parameters—depth ($L$) and width ($n$)—must scale relative to the data's geometric properties, such as curvature ($\kappa$) and class separation ($\Delta$).

Theoretical Framework: The NTK Regime

The analysis is conducted within the Neural Tangent Kernel (NTK) framework. In the overparameterized regime, the training dynamics of a neural network can be approximated by a linear model associated with a fixed kernel, the NTK. This allows the complex optimization of a non-convex neural network to be analyzed as a kernel method.

The researchers introduce several technical innovations to provide a nonasymptotic analysis:

  • Martingale Concentration: To ensure a randomly initialized network behaves predictably, the authors utilize martingale techniques. This handles the complex statistical dependencies that arise as signals propagate through many layers, providing tighter bounds than standard concentration inequalities.
  • Certificate Construction: The problem of proving convergence is reduced to a "certificate" problem. By showing that a specific deterministic integral equation has a solution, the authors guarantee that gradient descent will find a separating boundary.
  • Scaling Laws: Unlike asymptotic "infinite-width" results, this work provides specific polynomial scaling requirements for depth, width, and sample size.

Architectural Resources: Depth and Width

A key conceptual contribution of this work is the distinct roles assigned to network depth and width:

  1. Depth as a Fitting Resource: As depth $L$ increases, the network's underlying kernel becomes "sharper" and more localized. This increased resolution allows the network to fit complex decision boundaries without unintended interference between class manifolds.
  2. Width as a Statistical Resource: A wider network ($n$) ensures that the actual random network at initialization remains close to its deterministic limit. This concentration is crucial for the stability of gradient descent.
Increasing depth $L$ sharpens the kernel (a), while increasing width $n$ ensures concentration around the ideal kernel (b).

The authors establish that uniform concentration of the kernel over a $d_0$-dimensional submanifold is achievable when the width scales linearly with depth ($n \gtrsim L$). Interestingly, the required width depends on depth but is independent of the number of training samples $N$, mirroring practical observations.

Main Results

For the case of one-dimensional manifolds (curves) on a high-dimensional sphere, the authors prove that if depth $L$ is sufficiently large (proportional to $1/\Delta$) and width $n$ is a large enough polynomial in $L$:

  • Rapid Convergence: Gradient descent converges to a separating solution in polynomial time.
  • Perfect Generalization: The resulting classifier correctly labels the entire manifold, achieving zero generalization error with high probability.
  • Optimal Rates: The work provides essentially optimal concentration rates for the NTK of deep ReLU networks.

Limitations and Future Work

While this work provides a significant step forward, it is currently limited to one-dimensional manifolds. Extending the "certificate construction" to higher-dimensional surfaces presents significant mathematical hurdles. Furthermore, the analysis assumes the "lazy training" NTK regime. Future research will explore "feature learning" regimes where the network actively adapts its internal representations, as well as extending these results to convolutional architectures.

Summary updated

Abstract

We study the multiple manifold problem, a binary classification task modeled on applications in machine vision, in which a deep fully-connected neural network is trained to separate two low-dimensional submanifolds of the unit sphere. We provide an analysis of the one-dimensional case, proving for a simple manifold configuration that when the network depth $L$ is large relative to certain geometric and statistical properties of the data, the network width $n$ grows as a sufficiently large polynomial in $L$, and the number of i.i.d. samples from the manifolds is polynomial in $L$, randomly-initialized gradient descent rapidly learns to classify the two manifolds perfectly with high probability. Our analysis demonstrates concrete benefits of depth and width in the context of a practically-motivated model problem: the depth acts as a fitting resource, with larger depths corresponding to smoother networks that can more readily separate the class manifolds, and the width acts as a statistical resource, enabling concentration of the randomly-initialized network and its gradients. The argument centers around the neural tangent kernel and its role in the nonasymptotic analysis of training overparameterized neural networks; to this literature, we contribute essentially optimal rates of concentration for the neural tangent kernel of deep fully-connected networks, requiring width $n \gtrsim L\,\mathrm{poly}(d_0)$ to achieve uniform concentration of the initial kernel over a $d_0$-dimensional submanifold of the unit sphere $\mathbb{S}^{n_0-1}$, and a nonasymptotic framework for establishing generalization of networks trained in the NTK regime with structured data. The proof makes heavy use of martingale concentration to optimally treat statistical dependencies across layers of the initial random network. This approach should be of use in establishing similar results for other network architectures.
BibTeX
@inproceedings{buchanan2021deep,
  author = {Sam Buchanan and Dar Gilboa and John Wright},
  title = {{Deep Networks and the Multiple Manifold Problem}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=O-6Pm_d_Q-},
}
Figure