Fundamental tradeoffs between memorization and robustness in random features and neural tangent regimes

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 L2-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 gtrsim 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.