2020

Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond

Liu, Fanghui, Huang, Xiaolin, Chen, Yudong et al.

Understand

Random features is one of the most popular techniques to speed up kernel methods in large-scale problems.

Related works have been recognized by the NeurIPS Test-of-Time award in 2017 and the ICML Best Paper Finalist in 2019.
The body of work on random features has grown rapidly, and hence it is desirable to have a comprehensive overview on this topic explaining the connections among various algorithms and theoretical results.
In this survey, we systematically review the work on random features from the past ten years.

Built on

“Positive definite functions on spheres,”
I. J. Schoenberg, · 1942
Earlier work this paper cites.
“Orthogonal random features,”
Felix Xinnan Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel Holtmannrice, and Sanjiv Kumar, · 1983
Earlier work this paper cites.
Correlation Theory of Stationary and Related Random Functions
Akiva M Yaglom, · 1987
Earlier work this paper cites.
Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications
Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro, · 1987
Earlier work this paper cites.
Random number generation and quasi-Monte Carlo methods
Harald Niederreiter, · 1992
Earlier work this paper cites.
Practical numerical integration
Gwynne Evans, · 1993
Earlier work this paper cites.
“Computing with infinite networks,”
Christopher K.I. Williams, · 1997
Earlier work this paper cites.
“Stochastic integration rules for infinite regions,”
Alan Genz and John Monahan, · 1998
Earlier work this paper cites.
“A stochastic algorithm for high-dimensional integrals over unbounded regions with gaussian weight,”
Alan Genz and John Monahan, · 1999
Earlier work this paper cites.
“Sparse greedy matrix approximation for machine learning,”
Alex J. Smola and Bernhard Schölkopf, · 2000
Earlier work this paper cites.
“Using the Nyström method to speed up kernel machines,”
Christopher K.I. Williams and Matthias Seeger, · 2001
Earlier work this paper cites.
“Regularization with dot-product kernels,”
Alex J. Smola, Zoltan L. Ovari, and Robert C. Williamson, · 2001
Earlier work this paper cites.
“Classes of kernels for machine learning: a statistics perspective,”
Marc G. Genton, · 2001
Earlier work this paper cites.
Least Squares Support Vector Machines
Johan A.K. Suykens, Tony Van Gestel, Jos De Brabanter, Bart De Moor, and Joos Vandewalle, · 2002
Earlier work this paper cites.
“On the eigenspectrum of the gram matrix and its relationship to the operator eigenspectrum,”
John Shawe-Taylor, Chris Williams, Nello Cristianini, and Jaz Kandola, · 2002
Earlier work this paper cites.
“On the mathematical foundations of learning,”
Felipe Cucker and Steve Smale, · 2002
Earlier work this paper cites.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf and Alexander J. Smola, · 2003
Earlier work this paper cites.
Harmonic Analysis and the Theory of Probability
Salomon Bochner, · 2005
Earlier work this paper cites.
“Learning bounds for kernel regression using effective data dimensionality,”
Tong Zhang, · 2005
Earlier work this paper cites.
“Local rademacher complexities,”
Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson, · 2005
Earlier work this paper cites.
Spherical harmonics
Claus Müller, · 2006
Earlier work this paper cites.
“Extreme learning machine: theory and applications,”
Guang-Bin Huang, Qin-Yu Zhu, and Chee-Kheong Siew, · 2006
Earlier work this paper cites.
“Random features for large-scale kernel machines,”
Ali Rahimi and Benjamin Recht, · 2007
Earlier work this paper cites.
Learning theory: an approximation theory viewpoint
Felipe Cucker and Dingxuan Zhou, · 2007
Earlier work this paper cites.
“Optimal rates for the regularized least-squares algorithm,”
Andrea Caponnetto and Ernesto De Vito, · 2007
Earlier work this paper cites.
“Learning theory estimates via integral operators and their approximations,”
Steve Smale and Ding-Xuan Zhou, · 2007
Earlier work this paper cites.
“Fast rates for support vector machines using Gaussian kernels,”
Ingo Steinwart and Clint Scovel, · 2007
Earlier work this paper cites.
“Training invariant support vector machines using selective sampling,”
Gaëlle Loosli, Stéphane Canu, and Léon Bottou, · 2007
Earlier work this paper cites.
“Likelihood approximation by numerical integration on sparse grids,”
Florian Heiss and Viktor Winschel, · 2008
Earlier work this paper cites.
“Uniform approximation of functions with random bases,”
Ali Rahimi and Benjamin Recht, · 2008
Earlier work this paper cites.
Support Vector Machines
Ingo Steinwart and Christmann Andreas, · 2008
Earlier work this paper cites.
“Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning,”
Ali Rahimi and Benjamin Recht, · 2009
Earlier work this paper cites.
“Kernel methods for deep learning,”
Youngmin Cho and Lawrence K Saul, · 2009
Earlier work this paper cites.
“Learning multiple layers of features from tiny images,”
Alex Krizhevsky and Geoffrey Hinton, · 2009
Earlier work this paper cites.
“Imagenet: A large-scale hierarchical image database,”
Jia Deng, Wei Dong, Richard Socher, Li Jia Li, Kai Li, and Fei Fei Li, · 2009
Earlier work this paper cites.
“Random Fourier approximations for skewed multiplicative histogram kernels,”
Fuxin Li, Catalin Ionescu, and Cristian Sminchisescu, · 2010
Earlier work this paper cites.
“Two-stage learning kernel algorithms,”
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh, · 2010
Earlier work this paper cites.
“Optimal learning rates for kernel conjugate gradient regression,”
Gilles Blanchard and Nicole Krämer, · 2010
Earlier work this paper cites.
Oracle Inequalities in Empirical Risk Minimization and Sparse Recovery Problems
Vladimir Koltchinskii, · 2011
Earlier work this paper cites.
“Random feature maps for dot product kernels,”
Purushottam Kar and Harish Karnick, · 2012
Earlier work this paper cites.
“Efficient additive kernels via explicit feature maps,”
Andrea Vedaldi and Andrew Zisserman, · 2012
Earlier work this paper cites.
“Nyström method vs random Fourier features: a theoretical and empirical comparison,”
Tianbao Yang, Yu Feng Li, Mehrdad Mahdavi, Rong Jin, and Zhi Hua Zhou, · 2012
Earlier work this paper cites.
Topics in random matrix theory
Terence Tao, · 2012
Earlier work this paper cites.
“Divide and conquer kernel ridge regression,”
Yuchen Zhang, John Duchi, and Martin Wainwright, · 2013
Earlier work this paper cites.
“FastFood—approximating kernel expansions in loglinear time,”
Quoc Le, Tamás Sarlós, and Alex J. Smola, · 2013
Earlier work this paper cites.
“Fast and scalable polynomial kernels via explicit feature maps,”
Ninh Pham and Rasmus Pagh, · 2013
Earlier work this paper cites.
“Gaussian process kernels for pattern discovery and extrapolation,”
Andrew Gordon Wilson and Ryan Prescott Adams, · 2013
Earlier work this paper cites.
“Sharp analysis of low-rank kernel matrix approximations,”
Francis Bach, · 2013
Earlier work this paper cites.
“A divide-and-conquer solver for kernel support vector machines,”
Cho-Jui Hsieh, Si Si, and Inderjit Dhillon, · 2014
Earlier work this paper cites.
“Randomized nonlinear component analysis,”
David Lopez-Paz, Suvrit Sra, Alex J. Smola, Zoubin Ghahramani, and Bernhard Schölkopf, · 2014
Earlier work this paper cites.
“Quasi-Monte Carlo feature maps for shift-invariant kernels,”
Jiyan Yang, Vikas Sindhwani, Haim Avron, and Michael Mahoney, · 2014
Earlier work this paper cites.
“Scalable kernel methods via doubly stochastic gradients,”
Bo Dai, Bo Xie, Niao He, Yingyu Liang, Anant Raj, Maria-Florina F Balcan, and Le Song, · 2014
Earlier work this paper cites.
“Subspace embeddings for the polynomial kernel,”
Haim Avron, Huy Nguyen, and David Woodruff, · 2014
Earlier work this paper cites.
“Compact random feature maps,”
Raffay Hamid, Ying Xiao, Alex Gittens, and Dennis Decoste, · 2014
Earlier work this paper cites.
“On the error of random Fourier features,”
Danica J. Sutherland and Jeff Schneider, · 2015
Earlier work this paper cites.
“Spherical random features for polynomial kernels,”
Jeffrey Pennington, Felix Xinnan X. Yu, and Sanjiv Kumar, · 2015
Earlier work this paper cites.
“Random feature mapping with signed circulant matrix projection,”
Chang Feng, Qinghua Hu, and Shizhong Liao, · 2015
Earlier work this paper cites.
“Optimal rates for random Fourier features,”
Bharath K. Sriperumbudur and Zoltán Szabó, · 2015
Earlier work this paper cites.
“Compact nonlinear maps and circulant extensions,”
Original
Felix X. Yu, Sanjiv Kumar, Henry Rowley, and Shih Fu Chang, · 2015
Earlier work this paper cites.
“À la carte–learning fast kernels,”
Zichao Yang, Andrew Wilson, Alex J. Smola, and Le Song, · 2015
Earlier work this paper cites.

Similar

“Scale up nonlinear component analysis with doubly stochastic gradients,”
Bo Xie, Yingyu Liang, and Le Song, · 2015
Cited alongside, same era.
“Distributing many points on spheres: minimal energy and designs,”
Johann S. Brauchart and Peter J. Grabner, · 2015
Cited alongside, same era.
“Fast randomized kernel ridge regression with statistical guarantees,”
Ahmed Alaoui and Michael W Mahoney, · 2015
Cited alongside, same era.
“Batch normalization: accelerating deep network training by reducing internal covariate shift,”
Sergey Ioffe and Christian Szegedy, · 2015
Cited alongside, same era.
“Regularized linear regression: A precise analysis of the estimation error,”
Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, · 2015
Cited alongside, same era.
“Understanding deep learning requires rethinking generalization,”
Original
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals, · 2016
Cited alongside, same era.
“Quasi-Monte Carlo feature maps for shift-invariant kernels,”
Haim Avron, Vikas Sindhwani, Jiyan Yang, and Michael W. Mahoney, · 2016
Cited alongside, same era.
“Random projections through multiple optical scattering: Approximating kernels at the speed of light,”
Alaa Saade, Francesco Caltagirone, Igor Carron, Laurent Daudet, Angélique Drémeau, Sylvain Gigan, and Florent Krzakala, · 2016
Cited alongside, same era.
“Recycling randomness with structure for sublinear time kernel expansions,”
Krzysztof Choromanski and Vikas Sindhwani, · 2016
Cited alongside, same era.
“Gaussian error linear units (GELUs),”
Original
Dan Hendrycks and Kevin Gimpel, · 2016
Cited alongside, same era.
“Toward deeper understanding of neural networks: The power of initialization and a dual view on expressivity,”
Amit Daniely, Roy Frostig, and Yoram Singer, · 2016
Cited alongside, same era.
“Learning kernels with random features,”
Aman Sinha and John C. Duchi, · 2016
Cited alongside, same era.

Then

“Data-dependent compression of random features for large-scale kernel approximation,”
Raj Agrawal, Trevor Campbell, Jonathan Huggins, and Tamara Broderick, · 2019
Later among the works it cites.
“On lazy training in differentiable programming,”
Lenaic Chizat, Edouard Oyallon, and Francis Bach, · 2019
Later among the works it cites.
“On the inductive bias of neural tangent kernels,”
Alberto Bietti and Julien Mairal, · 2019
Later among the works it cites.
“Linearized two-layers neural networks in high dimension,”
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari, · 2019
Later among the works it cites.
“Tight dimensionality reduction for sketching low degree polynomial kernels,”
Michela Meister, Tamas Sarlos, and David Woodruff, · 2019
Later among the works it cites.
“Harmonizable mixture kernels with variational Fourier features,”
Zheyang Shen, Markus Heinonen, and Samuel Kaski, · 2019
Later among the works it cites.
“Unifying orthogonal Monte Carlo methods,”
Krzysztof Choromanski, Mark Rowland, Wenyu Chen, and Adrian Weller, · 2019
Later among the works it cites.
“Kernel quadrature with dpps,”
Ayoub Belhadji, Rémi Bardenet, and Pierre Chainais, · 2019
Later among the works it cites.
“A general scoring rule for randomized kernel approximation with application to canonical correlation analysis,”
Original
Yinsong Wang and Shahin Shahrampour, · 2019
Later among the works it cites.
“Automated scalable Bayesian inference via Hilbert coresets,”
Trevor Campbell and Tamara Broderick, · 2019
Later among the works it cites.
“Optimal rates for coefficient-based regularized regression,”
Zheng-Chu Guo and Lei Shi, · 2019
Later among the works it cites.
“Simple and almost assumption-free out-of-sample bound for random feature mapping,”
Original
Shusen Wang, · 2019
Later among the works it cites.
“Surprises in high-dimensional ridgeless least squares interpolation,”
Original
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani, · 2019
Later among the works it cites.
“The generalization error of random features regression: Precise asymptotics and double descent curve,”
Original
Song Mei and Andrea Montanari, · 2019
Later among the works it cites.
“On the multiple descent of minimum-norm interpolants and restricted lower isometry of kernels,”
Tengyuan Liang, Alexander Rakhlin, and Xiyu Zhai, · 2019
Later among the works it cites.
“Deep double descent: Where bigger models and more data hurt,”
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever, · 2019
Later among the works it cites.
“Learning and generalization in overparameterized neural networks, going beyond two layers,”
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang, · 2019
Later among the works it cites.
“The generalization error of max-margin linear classifiers: High-dimensional asymptotics in the overparametrized regime,”
Original
Andrea Montanari, Feng Ruan, Youngtak Sohn, and Jun Yan, · 2019
Later among the works it cites.
“On the power and limitations of random features for understanding neural networks,”
Gilad Yehudai and Ohad Shamir, · 2019
Later among the works it cites.
“The lottery ticket hypothesis: Finding sparse, trainable neural networks,”
Jonathan Frankle and Michael Carbin, · 2019
Later among the works it cites.
“Limitations of lazy training of two-layers neural network,”
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari, · 2019
Later among the works it cites.
“Learning data-adaptive non-parametric kernels,”
Fanghui Liu, Xiaolin Huang, Chen Gong, Jie Yang, and Li Li, · 2020
Closest in time.
“Graph random neural features for distance-preserving graph representations,”
Daniele Zambon, Cesare Alippi, and Lorenzo Livi, · 2020
Closest in time.
“Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks,”
Ziwei Ji and Matus Telgarsky, · 2020
Closest in time.
“Random Fourier features via fast surrogate leverage weighted sampling,”
Fanghui Liu, Xiaolin Huang, Yudong Chen, Jie Yang, and Johan A.K. Suykens, · 2020
Closest in time.
“Fourier sparse leverage scores and approximate kernel learning,”
Tamás Erdélyi, Cameron Musco, and Christopher Musco, · 2020
Closest in time.
“Proving the lottery ticket hypothesis: Pruning is all you need,”
Original
Eran Malach, Gilad Yehudai, Shai Shalev-Shwartz, and Ohad Shamir, · 2020
Closest in time.
“Near input sparsity time kernel embeddings via adaptive sampling,”
David P Woodruff and Amir Zandieh, · 2020
Closest in time.
“A double-variational Bayesian framework in random Fourier features for indefinite kernels,”
Fanghui Liu, Lei Shi, Xiaolin Huang, Jie Yang, and Johan A.K. Suykens, · 2020
Closest in time.
“Subgroup-based rank-1 lattice quasi-monte carlo,”
Yueming LYU, Yuan Yuan, and Ivor Tsang, · 2020
Closest in time.
“Towards a unified quadrature framework for large-scale kernel machines,”
Original
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A.K. Suykens, · 2020
Closest in time.
“Fast quantum algorithm for learning with optimized random features,”
Hayata Yamasaki, Sathyawageeswar Subramanian, Sho Sonoda, and Masato Koashi, · 2020
Closest in time.
“Harnessing the power of infinitely wide deep nets on small-data tasks,”
Sanjeev Arora, Simon S Du, Zhiyuan Li, Ruslan Salakhutdinov, Ruosong Wang, and Dingli Yu, · 2020
Closest in time.
“A random matrix analysis of random fourier features: beyond the gaussian kernel, a precise phase transition, and the corresponding double descent,”
Zhenyu Liao, Romain Couillet, and Michael Mahoney, · 2020
Closest in time.
“Generalization of two-layer neural networks: an asymptotic viewpoint,”
Jimmy Ba, Murat A. Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang, · 2020
Closest in time.
“Double trouble in double descent: Bias and variance(s) in the lazy regime,”
Original
Stéphane d’Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala, · 2020
Closest in time.
“Generalisation error in learning with random features and the hidden manifold model,”
Federica Gerace, Bruno Loureiro, Florent Krzakala, Marc Mézard, and Lenka Zdeborová, · 2020
Closest in time.
“Understanding double descent requires a fine-grained bias-variance decomposition,”
Ben Adlam and Jeffrey Pennington, · 2020
Closest in time.
“A precise performance analysis of learning with random features,”
Original
Oussama Dhifallah and Yue M Lu, · 2020
Closest in time.
“Universality laws for high-dimensional learning with random features,”
Original
Hong Hu and Yue M Lu, · 2020
Closest in time.
“Implicit regularization of random feature models,”
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel, · 2020
Closest in time.
“Two models of double descent for weak features,”
Mikhail Belkin, Daniel Hsu, and Ji Xu, · 2020
Closest in time.
“Memorizing without overfitting: Bias, variance, and interpolation in over-parameterized models,”
Original
Jason W Rocks and Pankaj Mehta, · 2020
Closest in time.
“What causes the test error? going beyond bias-variance via anova,”
Original
Licong Lin and Edgar Dobriban, · 2020
Closest in time.
“A precise high-dimensional asymptotic theory for boosting and min-
Original
Tengyuan Liang and Pragya Sur, · 2020
Closest in time.
“Kernel methods through the roof: Handling billions of points efficiently,”
Giacomo Meanti, Luigi Carratino, Lorenzo Rosasco, and Alessandro Rudi, · 2020
Closest in time.
“Multiple descent: Design your own generalization curve,”
Original
Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi, · 2020
Closest in time.
“On the optimal weighted
Denny Wu and Ji Xu, · 2020
Closest in time.
“The optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization,”
Dmitry Kobak, Jonathan Lomond, and Benoit Sanchez, · 2020
Closest in time.
“Scaling neural tangent kernels via sketching and random features,”
Original
Amir Zandieh, Insu Han, Haim Avron, Neta Shoham, Chaewon Kim, and Jinwoo Shin, · 2021
Closest in time.
“Rethinking attention with performers,”
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, and Weller Adrian, · 2021
Closest in time.
“Random feature attention,”
Hao Peng, Nikolaos Pappas, Dani Yogatama, Roy Schwartz, Noah Smith, and Lingpeng Kong, · 2021
Closest in time.
“Deep equals shallow for ReLU networks in kernel regimes,”
Alberto Bietti and Francis Bach, · 2021
Closest in time.
“Fast learning in reproducing kernel Kreĭn spaces via signed measures,”
Fanghui Liu, Xiaolin Huang, Yingyi Chen, and Johan A.K. Suykens, · 2021
Closest in time.
“Quantization algorithms for random fourier features,”
Xiaoyun Li and Ping Li, · 2021
Closest in time.
“Towards a unified analysis of random fourier features,”
Zhu Li, Jean-Francois Ton, Dino Oglic, and Dino Sejdinovic, · 2021
Closest in time.
“Kernel regression in high dimensions: Refined analysis beyond double descent,”
Fanghui Liu, Zhenyu Liao, and Johan A.K. Suykens, · 2021
Closest in time.
“Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration,”
Original
Song Mei, Theodor Misiakiewicz, and Andrea Montanari, · 2021
Closest in time.
“Precise tradeoffs in adversarial training for linear regression,”
Adel Javanmard, Mahdi Soltanolkotabi, and Hamed Hassani, · 2078
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…