2020

Towards a Unified Quadrature Framework for Large-Scale Kernel Machines

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

Understand

In this paper, we develop a quadrature framework for large-scale kernel machines via a numerical integration representation.

Considering that the integration domain and measure of typical kernels, e.g., Gaussian kernels, arc-cosine kernels, are fully symmetric, we leverage deterministic fully symmetric interpolatory rules to efficiently compute quadrature nodes and associated weights for kernel approximation.
The developed interpolatory rules are able to reduce the number of needed nodes while retaining a high approximation accuracy.
Further, we randomize the above deterministic rules by the classical Monte-Carlo sampling and control variates techniques with two merits: 1) The proposed stochastic rules make the dimension of the feature mapping flexibly varying, such that we can control the discrepancy between the original and approximate kernels by tuning the dimnension.

Built on

“Orthogonal random features,”
Felix Xinnan Yu, Ananda Theertha Suresh, Krzysztof Choromanski, Daniel Holtmannrice, and Sanjiv Kumar, · 1983
Earlier work this paper cites.
“Efficiency of multivariate control variates in monte carlo simulation,”
Reuven Y Rubinstein and Ruth Marcus, · 1985
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.
“Fully symmetric interpolatory rules for multiple integrals over infinite regions with gaussian weight,”
Alan Genz and Bradley D Keister, · 1996
Earlier work this paper cites.
“Constructing cubature formulae: the science behind the art,”
Ronald Cools, · 1997
Earlier work this paper cites.
“Monte carlo and quasi-monte carlo methods,”
Russel E Caflisch et al., · 1998
Earlier work this paper cites.
“Stochastic integration rules for infinite regions,”
Alan Genz and John Monahan, · 1998
Earlier work this paper cites.
“Methods for generating random orthogonal matrices,”
Alan Genz, · 1998
Earlier work this paper cites.
“Simple cubature formulas with high polynomial exactness,”
Erich Novak and Klaus Ritter, · 1999
Earlier work this paper cites.
“Ijcnn 2001 challenge: Generalization ability and text decoding,”
Chih-chung Chang and Chih-Jen Lin, · 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.
Learning with kernels: support vector machines, regularization, optimization, and beyond
Bernhard Schölkopf and Alexander J. Smola, · 2003
Earlier work this paper cites.
Scattered data approximation
Holger Wendland, · 2004
Earlier work this paper cites.
Harmonic Analysis and the Theory of Probability
Salomon Bochner, · 2005
Earlier work this paper cites.
“Random features for large-scale kernel machines,”
Ali Rahimi and Benjamin Recht, · 2007
Earlier work this paper cites.
Methods of numerical integration
Philip J. Davis and Philip Rabinowitz, · 2007
Earlier work this paper cites.

Similar

“Likelihood approximation by numerical integration on sparse grids,”
Florian Heiss and Viktor Winschel, · 2008
Cited alongside, same era.
“Kernel methods for deep learning,”
Youngmin Cho and Lawrence K Saul, · 2009
Cited alongside, same era.
“Cubature kalman filters,”
Ienkaran Arasaratnam and Simon Haykin, · 2009
Cited alongside, same era.
“The spectrum of kernel random matrices,”
Noureddine El Karoui, · 2010
Cited alongside, same era.
“Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands,”
Josef Dick et al., · 2011
Cited alongside, same era.
“Randomized nonlinear component analysis,”
David Lopez-Paz, Suvrit Sra, Alex J. Smola, Zoubin Ghahramani, and Bernhard Schölkopf, · 2014
Cited alongside, same era.
Introduction to quasi-Monte Carlo integration and applications
Gunther Leobacher and Friedrich Pillichshammer, · 2014
Cited alongside, same era.
“Relations between sparse-grid quadrature rule and spherical-radial cubature rule in nonlinear Gaussian estimation,”
Original
Bin Jia, Ming Xin, and Yang Cheng, · 2015
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.
“Spherical structured feature maps for kernel approximation,”
Yueming Lyu, · 2017
Cited alongside, same era.
“Gaussian quadrature for kernel features,”
Tri Dao, Christopher M. De Sa, and Christopher Ré, · 2017
Cited alongside, same era.
“The unreasonable effectiveness of structured random orthogonal embeddings,”
Krzysztof M. Choromanski, Mark Rowland, and Adrian Weller, · 2017
Cited alongside, same era.

Then

“Fully symmetric kernel quadrature,”
Toni Karvonen and Simo Sarkka, · 2018
Later among the works it cites.
“CROification: accurate kernel classification with the efficiency of sparse linear SVM,”
Mehran Kafai and Kave Eshghi, · 2019
Later among the works it cites.
“On exact computation with an infinitely wide neural net,”
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Russ R. Salakhutdinov, and Ruosong Wang, · 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.
“Low-precision random Fourier features for memory-constrained kernel approximation,”
Jian Zhang, Avner May, Tri Dao, and Christopher Re, · 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.
“Large-scale nonlinear AUC Maximization via triply stochastic gradients,”
Zhiyuan Dang, Xiang Li, Bin Gu, Cheng Deng, and Heng Huang, · 2020
Closest in time.
“Random features for kernel approximation: A survey in algorithms, theory, and beyond,”
Original
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan A.K. Suykens, · 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.
“Adaptive random fourier features with metropolis sampling,”
Petr Plecháč Mattias Sandberg Anders Szepessy Aku Kammonen, Jonas Kiessling, · 2020
Closest in time.
“Kernel alignment risk estimator: Risk prediction from training data,”
Arthur Jacot, Berfin Şimşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel, · 2020
Closest in time.
“Just interpolate: Kernel “ridgeless” regression can generalize,”
Tengyuan Liang and Alexander Rakhlin, · 2020
Closest in time.
“Generalization properties of hyper-RKHS and its application,”
Fanghui Liu, Lei Shi, Xiaolin Huang, Jie Yang, and Johan A.K. Suykens, · 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.
“Latent variable modeling with random features,”
Gregory Gundersen, Michael Zhang, and Barbara Engelhardt, · 2021
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…