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

arXiv: https://arxiv.org/abs/2106.02630 · HTML: https://mlsanity.com/paper/2106.02630/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 42 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 19 of 19)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [On the Inductive Bias of Neural Tangent Kernels](https://mlsanity.com/paper/1905.12173/) (2019)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Generalisation error in learning with random features and the hidden manifold model](https://mlsanity.com/paper/2002.09339/) (2020)
- [The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization](https://mlsanity.com/paper/2008.06786/) (2020)
- [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020)
- [A Random Matrix Approach to Neural Networks](https://mlsanity.com/paper/1702.05419/) (2017)
- [Adversarial examples from computational constraints](https://mlsanity.com/paper/1805.10204/) (2018)
- [Triple descent and the two kinds of overfitting: Where & why do they appear?](https://mlsanity.com/paper/2006.03509/) (2020)
- [A law of robustness for two-layers neural networks](https://mlsanity.com/paper/2009.14444/) (2020)
- [A Brief Prehistory of Double Descent](https://mlsanity.com/paper/2004.04328/) (2020)
- [Neural tangent kernels, transportation mappings, and universal approximation](https://mlsanity.com/paper/1910.06956/) (2019)
- [A Law of Robustness for Weight-bounded Neural Networks](https://mlsanity.com/paper/2102.08093/) (2021)

## Built on by (most cited first, 9 of 9)

- [The Eigenlearning Framework: A Conservation Law Perspective on Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2110.03922/) (2021)
- [Fast Neural Kernel Embeddings for General Activations](https://mlsanity.com/paper/2209.04121/) (2022)
- [Beyond the Universal Law of Robustness: Sharper Laws for Random Features and Neural Tangent Kernels](https://mlsanity.com/paper/2302.01629/) (2023)
- [On the (Non-)Robustness of Two-Layer Neural Networks in Different Learning Regimes](https://mlsanity.com/paper/2203.11864/) (2022)
- [A law of adversarial risk, interpolation, and label noise](https://mlsanity.com/paper/2207.03933/) (2022)
- [Towards Understanding the Word Sensitivity of Attention Layers: A Study via Random Features](https://mlsanity.com/paper/2402.02969/) (2024)
- [Robust Linear Regression: Gradient-descent, Early-stopping, and Beyond](https://mlsanity.com/paper/2301.13486/) (2023)
- [Robust Linear Regression: Phase-Transitions and Precise Tradeoffs for General Norms](https://mlsanity.com/paper/2308.00556/) (2023)
- [auto-fpt: Automating Free Probability Theory Calculations for Machine Learning Theory](https://mlsanity.com/paper/2504.10754/) (2025)

## Abstract (arXiv)

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.