2021/06/04 by Elvis Dohmatob, Dohmatob, Elvis · 1 citation
Computer Science · Mathematics · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.2106.02630
arxiv created 2021/06/04 · arxiv updated 2021/06/07
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.