mlsanityData to 7 Oct 2026

A Random Matrix Analysis of Random Fourier Features: Beyond the Gaussian Kernel, a Precise Phase Transition, and the Corresponding Double Descent

arXiv 2006.05013 ↗First posted 9 Jun 2020stat.ML cs.LGcited by 69

Not on the map. Why?

Abstract (arXiv)

This article characterizes the exact asymptotics of random Fourier feature (RFF) regression, in the realistic setting where the number of data samples n, their dimension p, and the dimension of feature space N are all large and comparable. In this regime, the random RFF Gram matrix no longer converges to the well-known limiting Gaussian kernel matrix (as it does when N → ∞ alone), but it still has a tractable behavior that is captured by our analysis. This analysis also provides accurate estimates of training and test regression errors for large n,p,N. Based on these estimates, a precise characterization of two qualitatively different phases of learning, including the phase transition between them, is provided; and the corresponding double descent test error curve is derived from this phase transition behavior. These results do not depend on strong assumptions on the data distribution, and they perfectly match empirical results on real-world data sets.

Key facts. Cited by 69 papers in the map (data through 7 Oct 2026). First posted on arXiv 9 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 20; 2022: 19; 2023: 9; 2024: 8; 2025: 11; 2026: 1.

69 papers.

Sort:

By area:

  1. 2020Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networkscited by 166
  2. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
  3. 2021Learning curves of generic features maps for realistic datasets with a teacher-student modelcited by 126
  4. 2021Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regimecited by 95
  5. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  6. 2021A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learningcited by 54
  7. 2021Risk Bounds for Over-parameterized Maximum Margin Classification on Sub-Gaussian Mixturescited by 48
  8. 2023High-dimensional analysis of double descent for linear regression with random projectionscited by 47
  9. 2022Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterizationcited by 36
  10. 2021Taxonomizing local versus global structure in neural network loss landscapescited by 34
  11. 2022Spectral Evolution and Invariance in Linear-width Neural Networkscited by 30
  12. 2021Towards an Understanding of Benign Overfitting in Neural Networkscited by 29
38 more
  1. 2022Homogenization of SGD in high-dimensions: Exact dynamics and generalization propertiescited by 26
  2. 2022Implicit Regularization or Implicit Conditioning? Exact Risk Trajectories of SGD in High Dimensionscited by 23
  3. 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
  4. 2023Six Lectures on Linearized Neural Networkscited by 19
  5. 2021Model, sample, and epoch-wise descents: exact solution of gradient flow in the random feature modelcited by 17
  6. 2021Dynamics of Stochastic Momentum Methods on Large-scale, Quadratic Modelscited by 15
  7. 2021Harmless interpolation in regression and classification with structured featurescited by 14
  8. 2021On the Generalization Power of Overfitted Two-Layer Neural Tangent Kernel Modelscited by 13
  9. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  10. 2021On the interplay between data structure and loss function in classification problemscited by 12
  11. 2024High-dimensional learning of narrow neural networkscited by 12
  12. 2023The Interpolating Information Criterion for Overparameterized Modelscited by 11
  13. 2022Multiple Descent in the Multiple Random Feature Modelcited by 10
  14. 2022Monotonicity and Double Descent in Uncertainty Estimation with Gaussian Processescited by 10
  15. 2023Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Datacited by 10
  16. 2021SHRIMP: Sparser Random Feature Models via Iterative Magnitude Pruningcited by 9
  17. 2023The Underlying Scaling Laws and Universal Statistical Structure of Complex Datasetscited by 9
  18. 2023Random Fourier Signature Featurescited by 9
  19. 2025Models of Heavy-Tailed Mechanistic Universalitycited by 9
  20. 2022Concentration of Random Feature Matrices in High-Dimensionscited by 8
  21. 2021Random matrices in service of ML footprint: ternary random features with no performance losscited by 7
  22. 2021Conditioning of Random Feature Matrices: Double Descent and Generalization Errorcited by 7
  23. 2022Bias-variance decomposition of overparameterized regression with random linear featurescited by 7
  24. 2022Overparameterized random feature regression with nearly orthogonal datacited by 6
  25. 2021Double-descent curves in neural networks: a new perspective using Gaussian processescited by 5
  26. 2021On the Double Descent of Random Features Models Trained with SGDcited by 5
  27. 2022Exact Phase Transitions in Deep Learningcited by 5
  28. 2024A High Dimensional Statistical Model for Adversarial Training: Geometry and Trade-Offscited by 5
  29. 2021The Geometry of Over-parameterized Regression and Adversarial Perturbationscited by 4
  30. 2023Robust and Communication-Efficient Federated Domain Adaptation via Random Featurescited by 4
  31. 2023A PAC-Bayesian Perspective on the Interpolating Information Criterioncited by 4
  32. 2021Asymptotics of Ridge Regression in Convolutional Modelscited by 3
  33. 2021Learning from learning machines: a new generation of AI technology to meet the needs of sciencecited by 3
  34. 2024Analyzing the Neural Tangent Kernel of Periodically Activated Coordinate Networkscited by 3
  35. 2025A Model Zoo on Phase Transitions in Neural Networkscited by 3
  36. 2025Random Matrix Theory for Deep Learning: Beyond Eigenvalues of Linear Modelscited by 3
  37. 2022Generalized Reference Kernel for One-class Classificationcited by 2
  38. 2022On The Relative Error of Random Fourier Features for Preserving Kernel Distancecited by 2

50 most cited of 69 All 69 (JSON)