mlsanityData to 7 Oct 2026

The Price of Robustness: Stable Classifiers Need Overparameterization

arXiv 2603.02806 ↗First posted 3 Mar 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

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 ≈ n parameters on n 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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 41 of its 55 references that are in the map. First posted on arXiv 3 Mar 2026.

Builds on

41 of 55 references.

References · 41

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  3. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  4. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  5. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  6. 2015DeepFool: a simple and accurate method to fool deep neural networkscited by 1,315
  7. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  8. 2018Robustness May Be at Odds with Accuracycited by 873
  9. 2017Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networkscited by 739
  10. 2017Spectrally-normalized margin bounds for neural networkscited by 681
  11. 2019Benign Overfitting in Linear Regressioncited by 544
  12. 2019Fantastic Generalization Measures and Where to Find Themcited by 507
29 more
  1. 2018Lipschitz regularity of deep neural networks: analysis and efficient estimationcited by 413
  2. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  3. 2018Regularisation of Neural Networks by Enforcing Lipschitz Continuitycited by 311
  4. 2020An Investigation of Why Overparameterization Exacerbates Spurious Correlationscited by 310
  5. 2018Towards Fast Computation of Certified Robustness for ReLU Networkscited by 254
  6. 2019Uniform convergence may be unable to explain generalization in deep learningcited by 223
  7. 2018Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networkscited by 193
  8. 2020The Lipschitz Constant of Self-Attentioncited by 171
  9. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  10. 2018Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networkscited by 140
  11. 2016Robust Large Margin Deep Neural Networkscited by 117
  12. 2015Analysis of classifiers' robustness to adversarial perturbationscited by 76
  13. 2019Convergence of Adversarial Training in Overparametrized Neural Networkscited by 58
  14. 2022Rethinking Lipschitz Neural Networks and Certified Robustness: A Boolean Function Perspectivecited by 48
  15. 2019Stable Rank Normalization for Improved Generalization in Neural Networks and GANscited by 41
  16. 2023Some Fundamental Aspects about Lipschitz Continuity of Neural Networkscited by 25
  17. 2022Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)cited by 18
  18. 2023Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernelscited by 13
  19. 2023On the Lipschitz Constant of Deep Networks and Double Descentcited by 11
  20. 2024Towards Robust Out-of-Distribution Generalization Bounds via Sharpnesscited by 10
  21. 2024ECLipsE: Efficient Compositional Lipschitz Constant Estimation for Deep Neural Networkscited by 10
  22. 2024Building a stable classifier with the inflated argmaxcited by 8
  23. 2022A Universal Trade-off Between the Model Size, Test Loss, and Training Loss of Linear Predictorscited by 7
  24. 2024On the Benefits of Over-parameterization for Out-of-Distribution Generalizationcited by 7
  25. 2022Malign Overfitting: Interpolation Can Provably Preclude Invariancecited by 6
  26. 2024A direct proof of a unified law of robustness for Bregman divergence lossescited by 4
  27. 2024Do stable neural networks exist for classification problems? -- A new view on stability in AIcited by 2
  28. 2024A Margin-based Multiclass Generalization Bound via Geometric Complexitycited by 2
  29. 2025Understanding Nonlinear Implicit Bias via Region Counts in Input Spacecited by 2

Built on by

Not cited yet.