Random Feature Methods in Machine Learning

Last update: 25 Aug 2025 11:40
First version: 13 May 2021

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

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

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

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]

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