Random Feature Methods in Machine Learning
Last update: 08 Oct 2025 11:15First 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]
- To read:
- 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