cs.LGMar 3, 2026

The Price of Robustness: Stable Classifiers Need Overparameterization

Authors: Jonas von Berg, Adalbert Fono, Massimiliano Datres, Sohir Maskey, Gitta Kutyniok

Organizations: Ludwig-Maximilians-Universität München Munich, Germany Munich Center for Machine Learning (MCML) · ∗now at Aleph Alpha Research · †University of Tromso, DLR-German Aerospace Center

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

The relationship between overparameterization, stability, and generalization remains incompletely understood in the setting of discontinuous classifiers. We address this gap by establishing a generalization bound for finite function classes that improves inversely with class stability, defined as the expected distance to the decision boundary in the input domain (margin). Interpreting class stability as a quantifiable notion of robustness, we derive as a corollary a law of robustness for classification that extends the results of Bubeck and Sellke beyond smoothness assumptions to discontinuous functions. In particular, any interpolating model with p≈np \approx n parameters on nn data points must be unstable, implying that substantial overparameterization is necessary to achieve high stability. We obtain analogous results for parameterized infinite function classes by analyzing a stronger robustness measure derived from the margin in the codomain, which we refer to as the normalized co-stability. Experiments support our theory: stability increases with model size and correlates with test performance, while traditional norm-based measures remain largely uninformative.

Figures & tables

Figure 1: 8-layer MLPs on CIFAR-10. Class stability S(f)S(f) (left) and normalized co-stability S∗(g)/L(g)S^{*}(g)/L(g) (right) as a function of model size. The configuration with w=128w=128 is excluded since it failed to attain 99% training accuracy after 400 epochs.
Figure 2: Class stability S(f)S(f) for 4- and 8-layer CNNs trained on CIFAR-10.
Figure 3: Class stability S(f)S(f) for 4-layer and 8-layer Heaviside-activation MLPs trained on MNIST.
Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4
Figure 5
Figure 4: Class stability for 4-layer MLPs trained on Gaussian toy-data with different variances.
ConceptDefinition
IsoperimetryP ⁣(∥f(x)−E[f]∥∞≥t)≤2exp⁡ ⁣(−dt22cL2)\mathbb{P}\!\left(\|f(x)-\mathbb{E}[f]\|_{\infty}\geq t\right)\leq 2\exp\!\left(-\tfrac{dt^{2}}{2cL^{2}}\right)
Rademacher complexityRn,μ(F)=1nEσi,j,xi[sup⁡f∈F∣∑i=1n∑j=1Cσijfj(xi)∣]\mathcal{R}_{n,\mu}(\mathcal{F})=\tfrac{1}{n}\mathbb{E}^{\sigma_{i,j},x_{i}}\Bigg[\sup_{f\in\mathcal{F}}\Big|\sum_{i=1}^{n}\sum_{j=1}^{\mathcal{C}}\sigma_{ij}f_{j}(x_{i})\Big|\Bigg]
Marginhf(x)=∑j=1Chfj(x),hfj(x):=inf⁡{∥x−z∥2:f(z)≠j, z∈Rd}h_{f}(x)=\sum_{j=1}^{\mathcal{C}}h_{f}^{j}(x),\quad h_{f}^{j}(x):=\inf\{\|x-z\|_{2}:f(z)\neq j,\,z\in\mathbb{R}^{d}\}
Class stabilityS(f)=∑j=1CS(f)j,S(f)j:=E[hfj]S(f)=\sum_{j=1}^{\mathcal{C}}S(f)^{j},\quad S(f)^{j}:=\mathbb{E}[h_{f}^{j}]
Co-marginhg∗(x)=∑j=1Chg∗j(x),hg∗j(x):=max⁡(0,gj(x)−max⁡i≠jgi(x))h^{*}_{g}(x)=\sum_{j=1}^{\mathcal{C}}h_{g}^{*}{{}^{j}}(x),\quad h_{g}^{*}{{}^{j}}(x):=\max\big(0,g_{j}(x)-\max_{i\neq j}g_{i}(x)\big)
Co-stabilityS∗(g)=∑j=1CS∗j(g),S∗j(g):=E[hg∗j]S^{*}(g)=\sum_{j=1}^{\mathcal{C}}S^{*}{{}^{j}}(g),\quad S^{*}{{}^{j}}(g):=\mathbb{E}[h_{g}^{*}{{}^{j}}]
Appendix
Table 1: Multi-class definitions.
Figure 5: 4-layer MLPs on CIFAR10.
Figure 6: 4-layer MLPs on MNIST.
Figure 7: 8-layer MLPs on MNIST.
Figure 8: 8-layer MLPs on MNIST with extended widths up to w=16384w=16384 .
Figure 9: 8-layer MLPs on MNIST trained for 7 epochs.
More in this topic

Overparameterization

See all 22 papers

Explore similar work

CardsList

  1. Does Order Matter : Connecting The Law of Robustness to Robust Generalization

    Feb 24, 2026Mihir More, Aritra Das, Jaee Ponde +3Generalization BoundsStatistical Learning Theory

    Ashoka University, Sonepat, Haryana · Truth Audit Labs · Indian Statistical Institute, Kolkata

  2. Upper Bounds on the Generalization Error of Deep Learning Models via Local Robustness and Stability

    Jun 15, 2026Abdul-Rauf Nuhu, Parham M. Kebria, Vahid Hemmati +3Neural Network GeneralizationNeural Network Robustness

    aNorth Carolina Agricultural and Technical State University, Dept. Electrical and Computer Engineering 1601 E Market St., Greensboro, 27411, NC, USA · bUniversity of Alabama, Dept. Computer Science, Tuscaloosa, 35487, AL, USA · cSouthwest Research Institute, San Antonio, 78238, TX, USA

  3. Over-parameterization and Adversarial Robustness in Neural Networks: An Overview and Empirical Analysis

    Jun 14, 2024Srishti Gupta, Zhang Chen, Luca Demetrio +9Overparameterized Neural NetworkAdversarial Attacks

    Sapienza University of Rome, Rome, Italy. · University of Cagliari, Cagliari, Italy. · Northwestern Polytechnical University, Xi’An, China. +1