mlsanityData to 7 Oct 2026

Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels

arXiv 2302.01629 ↗First posted 3 Feb 2023stat.ML cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

Machine learning models are vulnerable to adversarial perturbations, and a thought-provoking paper by Bubeck and Sellke has analyzed this phenomenon through the lens of over-parameterization: interpolating smoothly the data requires significantly more parameters than simply memorizing it. However, this "universal" law provides only a necessary condition for robustness, and it is unable to discriminate between models. In this paper, we address these gaps by focusing on empirical risk minimization in two prototypical settings, namely, random features and the neural tangent kernel (NTK). We prove that, for random features, the model is not robust for any degree of over-parameterization, even when the necessary condition coming from the universal law of robustness is satisfied. In contrast, for even activations, the NTK model meets the universal lower bound, and it is robust as soon as the necessary condition on over-parameterization is fulfilled. This also addresses a conjecture in prior work by Bubeck, Li and Nagaraj. Our analysis decouples the effect of the kernel of the model from an "interaction matrix", which describes the interaction with the test data and captures the effect of the activation. Our theoretical results are corroborated by numerical evidence on both synthetic and standard datasets (MNIST, CIFAR-10).

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 47 of its 54 references that are in the map. First posted on arXiv 3 Feb 2023.

Builds on

47 of 54 references.

References · 47

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2013Intriguing properties of neural networkscited by 5,114
  4. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  5. 2019Theoretically Principled Trade-off between Robustness and Accuracycited by 1,510
  6. 2016Adversarial Machine Learning at Scalecited by 934
  7. 2018Robustness May Be at Odds with Accuracycited by 873
  8. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  9. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  10. 2018On Lazy Training in Differentiable Programmingcited by 671
  11. 2019Deep Double Descent: Where Bigger Models and More Data Hurtcited by 667
  12. 2018Gradient Descent Finds Global Minima of Deep Neural Networkscited by 572
35 more
  1. 2017Provable defenses against adversarial examples via the convex outer adversarial polytopecited by 564
  2. 2019Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networkscited by 562
  3. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  4. 2019Unlabeled Data Improves Adversarial Robustnesscited by 415
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  6. 2017Implicit Regularization in Matrix Factorizationcited by 318
  7. 2018Certified Defenses against Adversarial Examplescited by 305
  8. 2021Deep learning: a statistical viewpointcited by 239
  9. 2021A Universal Law of Robustness via Isoperimetrycited by 150
  10. 2019Adversarial Training Can Hurt Generalizationcited by 131
  11. 2017Theoretical insights into the optimization landscape of over-parameterized shallow neural networkscited by 128
  12. 2020The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalizationcited by 101
  13. 2020Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networkscited by 87
  14. 2020The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Trainingcited by 84
  15. 2020Do Wider Neural Networks Really Help Adversarial Robustness?cited by 79
  16. 2020Precise Tradeoffs in Adversarial Training for Linear Regressioncited by 76
  17. 2020Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networkscited by 76
  18. 2021Exploring Architectural Ingredients of Adversarially Robust Deep Neural Networkscited by 73
  19. 2020A law of robustness for two-layers neural networkscited by 54
  20. 2020Precise Statistical Analysis of Classification Accuracies for Adversarial Trainingcited by 49
  21. 2020Random Matrix Theory Proves that Deep Learning Representations of GAN-data Behave as Gaussian Mixturescited by 47
  22. 2022The curse of overparametrization in adversarial training: Precise analysis of robust generalization for random features regressioncited by 40
  23. 2020The Curious Case of Adversarially Robust Models: More Data Can Help, Double Descend, or Hurt Generalizationcited by 39
  24. 2020Provable tradeoffs in adversarially robust classificationcited by 39
  25. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  26. 2018On the Spectrum of Random Features Maps of High Dimensional Datacited by 27
  27. 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
  28. 2022What Can the Neural Tangent Kernel Tell Us About Adversarial Robustness?cited by 21
  29. 2022Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)cited by 18
  30. 2021Interpolation can hurt robust generalization even when there is no noisecited by 15
  31. 2020Asymptotic Behavior of Adversarial Training in Binary Classificationcited by 14
  32. 2022Evolution of Neural Tangent Kernels under Benign and Adversarial Trainingcited by 14
  33. 2022On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimescited by 10
  34. 2021Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimescited by 9
  35. 2022Adversarial Robustness is at Odds with Lazy Trainingcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 3; 2025: 2; 2026: 3.

13 papers.

Sort:

  1. 2023A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networkscited by 46
  2. 2023How Spurious Features Are Memorized: Precise Analysis for Random and NTK Featurescited by 11
  3. 2025Spurious Correlations in High Dimensional Regression: The Roles of Regularization, Simplicity Bias and Over-Parameterizationcited by 9
  4. 2023Theoretical Analysis of Robust Overfitting for Wide DNNs: An NTK Approachcited by 8
  5. 2024No Free Prune: Information-Theoretic Barriers to Pruning at Initializationcited by 8
  6. 2024Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Featurescited by 5
  7. 2024Infinite Width Limits of Self Supervised Neural Networkscited by 4
  8. 2025A Law of Data Reconstruction for Random Features (and Beyond)cited by 3
  9. 2023Upper and lower bounds for the Lipschitz constant of random neural networkscited by 2
  10. 20231-Lipschitz Neural Networks are more expressive with N-Activationscited by 1
  11. 2026Is the Last Layer Sufficient for Uncertainty Quantification?cited by 1
  12. 2026The Price of Robustness: Stable Classifiers Need Overparameterizationcited by 0
1 more
  1. 2026Feature Learning in Linear-Width Two-Layer Networks: Two vs. One Step of Gradient Descentcited by 0