Abstract
This paper investigates the "overparameterization paradox" by examining how data geometry influences generalization in neural networks trained near the Edge of Stability (EoS). By introducing the concept of "Data Shatterability" and utilizing Tukey depth, the authors demonstrate that networks naturally adapt to low-dimensional structures. They prove that generalization depends on intrinsic rather than ambient dimensions and identify the "Curse of the Sphere" as a primary driver of memorization over learning.
Introduction
Modern neural networks are massive, often possessing far more parameters than training points. Theoretically, they should be able to memorize any dataset, including random noise, yet they generalize remarkably well on real-world data. This "overparameterization paradox" is often attributed to the implicit bias of optimizers like Gradient Descent. This paper explores this bias through the lens of the Edge of Stability (EoS) regime, revealing that the "shatterability" of a dataset—how easily it can be partitioned by neural network layers—is the hidden hand guiding generalization.
Methodology: Quantifying Data Shatterability
The authors focus on two-layer ReLU networks and analyze solutions satisfying the Below-Edge-of-Stability (BEoS) condition. Their core innovation is a framework based on Data Shatterability, measured using Tukey depth (or half-space depth), which quantifies how "central" a point is within a distribution.
To quantify this, they introduce:
- Half-space-depth quantile partition: A technique to split the input space into "deep" regions (where regularization is strong) and "shallow" regions (where it is weak).
- Concentration Index ($S_{DQ}$): A scalar summary of a distribution's geometry acting as a proxy for how easily a network can "shatter" (partition) data to memorize labels.
Geometric Insights: The Shatterability Principle
Generalization is a tug-of-war between data geometry and the network's activation thresholds. If data is "hard to shatter" (densely packed in the interior), the network is forced to learn broad, shared patterns. Conversely, if data is "easy to shatter" (like points on the surface of a sphere), the network can isolate individual points and memorize them without learning useful features.
The "Curse of the Sphere"
Data concentrated on a sphere represents a worst-case scenario for generalization. On a sphere, any set of labels can be perfectly interpolated by a stable network, effectively breaking the implicit regularization that usually prevents overfitting.
Intrinsic vs. Ambient Dimension
The authors prove that for data lying on low-dimensional structures (like a mixture of subspaces), the generalization rate depends on the intrinsic dimension ($m$), not the ambient dimension ($d$). This explains why networks generalize on high-pixel images if the underlying concept has few degrees of freedom.
Key Results
- Provable Adaptation: For a mixture of $m$-dimensional subspaces, the authors prove a generalization rate of $\tilde{O}(n^{-1/(2m+4)})$, where the ambient dimension $d$ only appears in logarithmic factors. This provides a rigorous theoretical justification for why deep learning works in high dimensions.
- The Generalization Spectrum: On Beta-radial data, generalization improves as data becomes more "centrally concentrated" and degrades as it moves toward the boundary.
- MNIST vs. Noise: Empirically, Gradient Descent on Gaussian noise (highly shatterable) interpolates almost instantly, while on MNIST (low-dimensional structure), the network resists overfitting for tens of thousands of steps.
Conclusion
While currently limited to two-layer ReLU networks, this work provides a foundation for understanding how data geometry interacts with optimization. It highlights that distributions easy to overfit might be faster to optimize, suggesting a fundamental trade-off between training efficiency and generalization quality. Future work will focus on scaling these geometric metrics to complex, multi-layer models.
Summary updated