mlsanityData to 7 Oct 2026

Conditioning of Random Feature Matrices: Double Descent and Generalization Error

arXiv 2110.11477 ↗First posted 21 Oct 2021stat.ML cs.LG math.OCcited by 7

Not on the map. Why?

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.

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

Builds on

28 of 42 references.

References · 28

  1. 2018The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networkscited by 2,250
  2. 2018Reconciling modern machine learning practice and the bias-variance trade-offcited by 919
  3. 2019Benign Overfitting in Linear Regressioncited by 544
  4. 2019Surprises in High-Dimensional Ridgeless Least Squares Interpolationcited by 508
  5. 2019The generalization error of random features regression: Precise asymptotics and double descent curvecited by 410
  6. 2017Stable Architectures for Deep Neural Networkscited by 340
  7. 2017High-dimensional dynamics of generalization error in neural networkscited by 238
  8. 2019Two models of double descent for weak featurescited by 194
  9. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  10. 2018To understand deep learning we need to understand kernel learningcited by 186
  11. 2016Generalization Properties of Learning with Random Featurescited by 163
  12. 2020Benign overfitting in ridge regressioncited by 152
16 more
  1. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 136
  2. 2017Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practicecited by 132
  3. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  4. 2018Does data interpolation contradict statistical optimality?cited by 95
  5. 2020Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don'tcited by 94
  6. 2015Less is More: Nystr"om Computational Regularizationcited by 89
  7. 2017A Random Matrix Approach to Neural Networkscited by 80
  8. 2020A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descentcited by 69
  9. 2019NeuPDE: Neural Network Based Ordinary and Partial Differential Equations for Modeling Time-Dependent Datacited by 42
  10. 2018On the Spectrum of Random Features Maps of High Dimensional Datacited by 27
  11. 2021Generalization Bounds for Sparse Random Feature Expansionscited by 22
  12. 2019Double descent in the condition numbercited by 14
  13. 2020On Random Matrices Arising in Deep Neural Networks. Gaussian Casecited by 14
  14. 2018Forward Stability of ResNet and Its Variantscited by 12
  15. 2020The Slow Deterioration of the Generalization Error of the Random Feature Modelcited by 8
  16. 2020Avoiding The Double Descent Phenomenon of Random Feature Models Using Hybrid Regularizationcited by 3

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 4; 2023: 1; 2024: 0; 2025: 1.

7 papers.

  1. 2022HARFE: Hard-Ridge Random Feature Expansioncited by 12
  2. 2022Random Feature Models for Learning Interacting Dynamical Systemscited by 10
  3. 2021SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruningcited by 9
  4. 2022Concentration of Random Feature Matrices in High-Dimensionscited by 8
  5. 2022SRMD: Sparse Random Mode Decompositioncited by 6
  6. 2023Understanding the Role of Optimization in Double Descentcited by 0
  7. 2025Towards Atoms of Large Language Modelscited by 0