Overparameterization and Stability: A New Law of Robustness for Discontinuous Classifiers
A new theoretical study establishes a crucial link between overparameterization, model stability, and generalization for discontinuous classifiers, extending foundational robustness laws beyond smooth function assumptions. The research introduces a quantifiable measure of class stability—the expected distance to the decision boundary—and proves that any model that perfectly fits (interpolates) training data with a parameter count roughly equal to the number of data points must be unstable. This finding implies that substantial overparameterization is a necessary condition for achieving the high stability that underpins reliable generalization in modern machine learning architectures.
Bridging the Theory Gap for Non-Smooth Functions
The relationship between a model's complexity, its robustness to input perturbations, and its ability to generalize to new data is a cornerstone of learning theory. However, this relationship has remained incompletely understood for the broad class of discontinuous classifiers, which includes many practical neural networks with ReLU activations. The new work, detailed in the preprint arXiv:2603.02806v1, directly addresses this gap by deriving a novel generalization bound for finite function classes. This bound improves inversely with a newly defined metric: class stability.
Class stability is formally defined as the expected distance from a data point to the classifier's decision boundary in the input domain, effectively quantifying a model's margin. By interpreting this stability as a measurable form of robustness, the authors derive a significant corollary: a law of robustness for classification. This law extends the influential results of Bubeck and Sellke, which were predicated on smoothness assumptions, to the discontinuous function classes that are prevalent in contemporary AI.
The Necessity of Overparameterization for Stability
The core theoretical implication is striking. The analysis demonstrates that for a model with approximately p ≈ n parameters trained on n data points to achieve perfect training interpolation, it must inherently possess low stability. In other words, such a model would have a very small expected margin, making its predictions fragile to minor input variations. The only path to high stability, according to this law, is through substantial overparameterization—where the number of parameters significantly exceeds the number of training samples. This provides a theoretical justification for the massive scale of modern models.
For parameterized infinite function classes, the researchers obtain analogous results by analyzing a stronger, derived robustness measure called normalized co-stability. This measure is based on the margin in the function's codomain (output space), offering a complementary perspective on model robustness that aligns with the theoretical conclusions drawn from input-space stability.
Empirical Validation and Practical Implications
Theoretical findings are supported by experimental evidence. Tests show that as model size increases, so does its measured class stability, and this increase correlates strongly with improved test performance. Notably, the study finds that traditional norm-based complexity measures, such as weight magnitudes, remain largely uninformative in predicting generalization for these overparameterized, interpolating classifiers. This highlights the unique explanatory power of stability-based metrics derived from margin analysis.
This research shifts the focus from simple parameter counting or norm minimization to a more nuanced understanding of geometric robustness. It suggests that the success of large models may be less about their raw capacity and more about how overparameterization enables the learning of stable, high-margin decision boundaries that generalize effectively.
Why This Matters: Key Takeaways
- Extends Robustness Theory: Provides a formal "law of robustness" for discontinuous classifiers, a critical class that includes most modern neural networks, going beyond previous smooth-function limitations.
- Justifies Model Scale: Theoretically demonstrates that significant overparameterization (more parameters than data points) is necessary to achieve the high stability that leads to good generalization, explaining a key driver behind large-scale AI.
- Introduces Better Metrics: Proposes class stability and normalized co-stability as informative measures correlated with test performance, outperforming traditional norm-based measures in this regime.
- Connects Geometry to Generalization: Reinforces the principle that the geometric property of a large margin (stability) is fundamental to reliable performance, offering a fresh lens for model analysis and design.