# Conditioning of Random Feature Matrices: Double Descent and Generalization Error

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 21 Oct 2021.

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

- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (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)
- [Stable Architectures for Deep Neural Networks](https://mlsanity.com/paper/1705.03341/) (2017)
- [High-dimensional dynamics of generalization error in neural networks](https://mlsanity.com/paper/1710.03667/) (2017)
- [Two models of double descent for weak features](https://mlsanity.com/paper/1903.07571/) (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)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Benign overfitting in ridge regression](https://mlsanity.com/paper/2009.14286/) (2020)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice](https://mlsanity.com/paper/1711.04735/) (2017)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't](https://mlsanity.com/paper/2009.10713/) (2020)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [A Random Matrix Approach to Neural Networks](https://mlsanity.com/paper/1702.05419/) (2017)
- [A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent](https://mlsanity.com/paper/2006.05013/) (2020)
- [NeuPDE: Neural Network Based Ordinary and Partial Differential Equations for Modeling Time-Dependent Data](https://mlsanity.com/paper/1908.03190/) (2019)
- [On the Spectrum of Random Features Maps of High Dimensional Data](https://mlsanity.com/paper/1805.11916/) (2018)
- [Generalization Bounds for Sparse Random Feature Expansions](https://mlsanity.com/paper/2103.03191/) (2021)
- [Double descent in the condition number](https://mlsanity.com/paper/1912.06190/) (2019)
- [On Random Matrices Arising in Deep Neural Networks. Gaussian Case](https://mlsanity.com/paper/2001.06188/) (2020)
- [Forward Stability of ResNet and Its Variants](https://mlsanity.com/paper/1811.09885/) (2018)
- [The Slow Deterioration of the Generalization Error of the Random Feature Model](https://mlsanity.com/paper/2008.05621/) (2020)
- [Avoiding The Double Descent Phenomenon of Random Feature Models Using Hybrid Regularization](https://mlsanity.com/paper/2012.06667/) (2020)

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

- [HARFE: Hard-Ridge Random Feature Expansion](https://mlsanity.com/paper/2202.02877/) (2022)
- [Random Feature Models for Learning Interacting Dynamical Systems](https://mlsanity.com/paper/2212.05591/) (2022)
- [SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruning](https://mlsanity.com/paper/2112.04002/) (2021)
- [Concentration of Random Feature Matrices in High-Dimensions](https://mlsanity.com/paper/2204.06935/) (2022)
- [SRMD: Sparse Random Mode Decomposition](https://mlsanity.com/paper/2204.06108/) (2022)
- [Understanding the Role of Optimization in Double Descent](https://mlsanity.com/paper/2312.03951/) (2023)
- [Towards Atoms of Large Language Models](https://mlsanity.com/paper/2509.20784/) (2025)

## Abstract (arXiv)

We provide (high probability) bounds on the condition number of random feature matrices. In particular, we show that if the complexity ratio fracNm where N is the number of neurons and m is the number of data samples scales like log-1(N) or log(m), then the random feature matrix is well-conditioned. This result holds without the need of regularization and relies on establishing various concentration bounds between dependent components of the random feature matrix. Additionally, we derive bounds on the restricted isometry constant of the random feature matrix. We prove that the risk associated with regression problems using a random feature matrix exhibits the double descent phenomenon and that this is an effect of the double descent behavior of the condition number. The risk bounds include the underparameterized setting using the least squares problem and the overparameterized setting where using either the minimum norm interpolation problem or a sparse regression problem. For the least squares or sparse regression cases, we show that the risk decreases as m and N increase, even in the presence of bounded or random noise. The risk bound matches the optimal scaling in the literature and the constants in our results are explicit and independent of the dimension of the data.