mlsanityData to 14 Oct 2026

Generalization Properties of Learning with Random Features

arXiv 1602.04474 ↗First posted 14 Feb 2016stat.ML cs.LGcited by 164

Not on the map. Why?

Abstract (arXiv)

We study the generalization properties of ridge regression with random features in the statistical learning framework. We show for the first time that O(1/√n) learning bounds can be achieved with only O(√nlog n) random features rather than O(n) as suggested by previous results. Further, we prove faster learning rates and show that they might require more random features, unless they are sampled according to a possibly problem dependent distribution. Our results shed light on the statistical computational trade-offs in large scale kernelized learning, showing the potential effectiveness of random features in reducing the computational complexity while keeping optimal generalization properties.

Key facts. Cited by 164 papers in the map (data through 14 Oct 2026). First posted on arXiv 14 Feb 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 28; 2022: 25; 2023: 34; 2024: 29; 2025: 27; 2026: 21.

164 papers.

Sort:

By area:

  1. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  2. 2022Learning Single-Index Models with Shallow Neural Networkscited by 92
  3. 2021Learning with invariances in random features and kernel modelscited by 89
  4. 2024Model Collapse Demystified: The Case of Regressioncited by 82
  5. 2023How Two-Layer Neural Networks Learn, One (Giant) Step at a Timecited by 68
  6. 2024Strong Model Collapsecited by 65
  7. 2024Scaling Laws in Linear Regression: Compute, Parameters, and Datacited by 57
  8. 2021Understanding neural networks with reproducing kernel Banach spacescited by 50
  9. 2022Unbalanced Optimal Transport, from Theory to Numericscited by 46
  10. 2023Operator learning with PCA-Net: upper and lower complexity boundscited by 44
  11. 2023What can a Single Attention Layer Learn? A Study Through the Random Features Lenscited by 40
  12. 2022Information Theory with Kernel Methodscited by 37
38 more
  1. 2021Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionalitycited by 34
  2. 2021Scaling Neural Tangent Kernels via Sketching and Random Featurescited by 32
  3. 2021PSD Representations for Effective Probability Modelscited by 23
  4. 2022Policy Optimization over General State and Action Spacescited by 23
  5. 2023Error Bounds for Learning with Vector-Valued Random Featurescited by 23
  6. 2021Generalization Bounds for Sparse Random Feature Expansionscited by 22
  7. 2023Potential and limitations of random Fourier features for dequantizing quantum machine learningcited by 22
  8. 2021Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networkscited by 21
  9. 2022Learning new physics efficiently with nonparametric methodscited by 21
  10. 2024Operator Learning Using Random Features: A Tool for Scientific Computingcited by 21
  11. 2023Six Lectures on Linearized Neural Networkscited by 20
  12. 2022Regularized Stein Variational Gradient Flowcited by 19
  13. 2023More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatorycited by 18
  14. 2021Learning to Forecast Dynamical Systems from Streaming Datacited by 17
  15. 2023Universal Approximation Theorem and error bounds for quantum neural networks and quantum reservoirscited by 16
  16. 2021The Separation Capacity of Random Neural Networkscited by 14
  17. 2021Exact Gap between Generalization Error and Uniform Convergence in Random Feature Modelscited by 13
  18. 2021Learning Augmentation Distributions using Transformed Risk Minimizationcited by 13
  19. 2023When is Importance Weighting Correction Needed for Covariate Shift Adaptation?cited by 13
  20. 2023Fundamental limits of overparametrized shallow neural networks for supervised learningcited by 13
  21. 2023Unsupervised Behavior Extraction via Random Intent Priorscited by 13
  22. 2023Universal approximation property of Banach space-valued random feature models including random neural networkscited by 13
  23. 2021An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddingscited by 12
  24. 2022HARFE: Hard-Ridge Random Feature Expansioncited by 12
  25. 2023Self-Supervised Reinforcement Learning that Transfers using Random Featurescited by 11
  26. 2023Personalized Online Federated Learning with Multiple Kernelscited by 11
  27. 2021Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCAcited by 10
  28. 2022Random Feature Models for Learning Interacting Dynamical Systemscited by 10
  29. 2023Benign Overfitting in Deep Neural Networks under Lazy Trainingcited by 10
  30. 2023How many Neurons do we need? A refined Analysis for Shallow Networks trained with Gradient Descentcited by 10
  31. 2024Accelerating Heterogeneous Federated Learning with Closed-form Classifierscited by 10
  32. 2025Kernel ridge regression under power-law data: spectrum and generalizationcited by 10
  33. 2022Concentration of Random Feature Matrices in High-Dimensionscited by 9
  34. 2023Random Fourier Signature Featurescited by 9
  35. 2026Optimal scaling laws in learning hierarchical multi-index modelscited by 9
  36. 2021Sampling from Arbitrary Functions via PSD Modelscited by 8
  37. 2023Nonlinear Meta-Learning Can Guarantee Faster Ratescited by 8
  38. 2023Adaptive learning of density ratios in RKHScited by 8

50 most cited of 164 All 164 (JSON)