Random Feature Methods in Machine Learning

Last update: 26 Jul 2026 23:02
First version: 13 May 2021

---

(and other parts of statistics and/or computational mathematics...)

Recommended, big picture:
• Ali Rahimi and Benjamin Recht
  • "Random Features for Large-Scale Kernel Machines", pp. 1177--1184 in John C. Platt, Daphne Koller, Yoram Singer and Samuel T. Roweis (eds.), Advances in Neural Information Processing Systems 20 [NIPS 2007]
  • "Weighted Sums of Random Kitchen Sinks: Replacing Minimization with Randomization in Learning", pp. 1313--1320 in Daphne Koller, D. Schuurmans, Y. Bengio and L. Bottou (eds.), Advances in Neural Information Processing Systems 21 [NIPS 2008]
  • "Uniform Approximation of Functions with Random Bases", pp. 555--561 in P. Moulin and C. Beck (eds.), 46th Annual Allerton Conference on Communication, Control, and Computing (Urbana-Champaign, Illinois: IEEE, 2008) [PDF reprprint via Prof. Recht]
  • "Reflections on Random Kitchen Sinks", argmin blog, 5 December 2017

Recommended, close ups:
• Jonathan H. Huggins, Lester Mackey, "Random Feature Stein Discrepancies", NeurIPS 2018, arxiv:1806.07788
• Quoc Le, Tamas Sarlos, Alexander Smola, "Fastfood --- Computing Hilbert Space Expansions in loglinear time", ICML 2013
• Nicholas H. Nelsen, Andrew M. Stuart, "The Random Feature Model for Input-Output Maps between Banach Spaces", arxiv:2005.10224 [This looks almost like magic]
• Hiteshi Sharma, Rahul Jain
  • "Finite Time Guarantees for Continuous State MDPs with Generative Model", pp. 3617--4622 in 59th IEEE Conference on Decision and Control (CDC) (2020)
  • "Randomized Policy Learning for Continuous State and Action MDPs", arxiv:2006.04331
• Eric V. Strobl, Kun Zhang, Shyam Visweswaran, "Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery", Journal of Causal Inference 7 (2019): 20180017, arxiv:1702.03877
• Danica J. Sutherland and Jeff Schneider, "On the Error of Random Fourier Features", pp. 862--871 in UAI-2015, arxiv:1506.02785
• Qinyi Zhang, Sarah Filippi, Arthur Gretton and Dino Sejdinovic , "Large-scale kernel methods for independence testing", Statistics and Computing 28 (2018): 113--130, arxiv:1606.07892

Recommended, close-ups, historical:
• Yoh-Han Pao, Gwang-Hoon Park and Dejan J. Sobajic, "Learning and Generalization Characteristics of the Random Vector Functional-Link Net", Neurocomputing 6 (1994): 163--180 [This is at the least a highly similar idea, if not in fact formally identical. See the references here for earlier publications by these authors giving earlier versions of the idea, and a post-script giving citations to some follow-up papers which I honestly have not read.]

Modesty forbids me to recommend:
• The lecture on random features in my undergrad course on statistical learning theory
• CRS, "A Note on Simulation-Based Inference by Matching Random Features", arxiv:2111.09220 [auto-vulgarization]
• Michael Wieck-Sosa and CRS
  • "Dynamic models with $p$ parameters are identified by $2p+1$ random features", arxiv:2607.16035
  • "Estimating dynamic models by matching random features", arxiv:2607.21916

To read:
• Danil Akhtiamov, Reza Ghane, Babak Hassibi, "One-Bit Quantization for Random Features Models", arxiv:2510.16250
• David Bosch, Ashkan Panahi, Ayca Ozcelikkale, Devdatt Dubhashi, "Random Features Model with General Convex Regularization: A Fine Grained Analysis with Precise Asymptotic Learning Curves", pp. 11371--11414 in Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (2023)
• Krzysztof Choromanski, "Taming graph kernels with random features", arxiv:2305.00156
• Hengyu Fu, Tianyu Guo, Yu Bai, Song Mei, "What can a Single Attention Layer Learn? A Study Through the Random Features Lens", arxiv:2307.11353
• Abolfazl Hashemi, Hayden Schaeffer, Robert Shi, Ufuk Topcu, Giang Tran, Rachel Ward, "Generalization Bounds for Sparse Random Feature Expansions", arxiv:2103.03191
• Samuel Lanthaler, Nicholas H. Nelsen, "Error Bounds for Learning with Vector-Valued Random Features", arxiv:2305.17170
• Song Mei, Theodor Misiakiewicz, Andrea Montanari, "Learning with invariances in random features and kernel models", arxiv:2102.13219
• Mateus P. Otto, Rafael Izbicki, "RFFNet: Scalable and interpretable kernel methods via Random Fourier Features", arxiv:2211.06410
• Isaac Reid, Krzysztof Choromanski, Adrian Weller, "Quasi-Monte Carlo Graph Random Features", arxiv:2305.12470
• Bharath Sriperumbudur, Nicholas Sterge, "Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off", arxiv:1706.06296
• Zitong Yang, Yu Bai, Song Mei, "Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models", arxiv:2103.04554
• Michael Minyi Zhang, Gregory W. Gundersen, Barbara E. Engelhardt, "Bayesian Non-linear Latent Variable Modeling via Random Fourier Features", arxiv:2306.08352