Papers › Fundamental tradeoffs between memorization and robustness in random features and...
Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes
Elvis Dohmatob
This work studies the (non)robustness of two-layer neural networks in various high-dimensional linearized regimes. We establish fundamental trade-offs between memorization and robustness, as measured by the Sobolev-seminorm of the model w.r.t the data distribution, i.e the square root of the average squared L₂-norm of the gradients of the model w.r.t the its input. More precisely, if n is the number of training examples, d is the input dimension, and k is the number of hidden neurons in a two-layer neural network, we prove for a large class of activation functions that, if the model memorizes even a fraction of the training, then its Sobolev-seminorm is lower-bounded by (i) √(n) in case of infinite-width random features (RF) or neural tangent kernel (NTK) with d ≳n; (ii) √(n) in case of finite-width RF with proportionate scaling of d and k; and (iii) √(n/k) in case of finite-width NTK with proportionate scaling of d and k. Moreover, all of these lower-bounds are tight: they are attained by the min-norm / least-squares interpolator (when n, d, and k are in the appropriate interpolating regime). All our results hold as soon as data is log-concave isotropic, and there is label-noise, i.e the target variable is not a deterministic function of the data / features. We empirically validate our theoretical results with experiments. Accidentally, these experiments also reveal for the first time, (iv) a multiple-descent phenomenon in the robustness of the min-norm interpolator.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Methods
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections