Integration in reproducing kernel Hilbert spaces of Gaussian kernels

Authors:
Toni Karvonen, Chris J. Oates and Mark Girolami

Journal:
Math. Comp. **90** (2021), 2209-2233

MSC (2020):
Primary 65D30, 46E22; Secondary 65D12, 41A25

DOI:
https://doi.org/10.1090/mcom/3659

Published electronically:
June 18, 2021

MathSciNet review:
4280298

Full-text PDF

View in AMS MathViewer

Abstract | References | Similar Articles | Additional Information

Abstract: The Gaussian kernel plays a central role in machine learning, uncertainty quantification and scattered data approximation, but has received relatively little attention from a numerical analysis standpoint. The basic problem of finding an algorithm for efficient numerical integration of functions reproduced by Gaussian kernels has not been fully solved. In this article we construct two classes of algorithms that use $N$ evaluations to integrate $d$-variate functions reproduced by Gaussian kernels and prove the exponential or super-algebraic decay of their worst-case errors. In contrast to earlier work, no constraints are placed on the length-scale parameter of the Gaussian kernel. The first class of algorithms is obtained via an appropriate scaling of the classical Gauss–Hermite rules. For these algorithms we derive lower and upper bounds on the worst-case error of the forms $\exp (-c_1 N^{1/d}) N^{1/(4d)}$ and $\exp (-c_2 N^{1/d}) N^{-1/(4d)}$, respectively, for positive constants $c_1 > c_2$. The second class of algorithms we construct is more flexible and uses worst-case optimal weights for points that may be taken as a nested sequence. For these algorithms we derive upper bounds of the form $\exp (-c_3 N^{1/(2d)})$ for a positive constant $c_3$.

- David L. Barrow,
*On multiple node Gaussian quadrature formulae*, Math. Comp.**32**(1978), no. 142, 431–439. MR**482257**, DOI 10.1090/S0025-5718-1978-0482257-0 - Alain Berlinet and Christine Thomas-Agnan,
*Reproducing kernel Hilbert spaces in probability and statistics*, Kluwer Academic Publishers, Boston, MA, 2004. With a preface by Persi Diaconis. MR**2239907**, DOI 10.1007/978-1-4419-9096-9 - François-Xavier Briol, Chris J. Oates, Mark Girolami, Michael A. Osborne, and Dino Sejdinovic,
*Probabilistic integration: a role in statistical computation?*, Statist. Sci.**34**(2019), no. 1, 1–22. MR**3938958**, DOI 10.1214/18-STS660 - Jia Chen and Heping Wang,
*Average case tractability of multivariate approximation with Gaussian kernels*, J. Approx. Theory**239**(2019), 51–71. MR**3892003**, DOI 10.1016/j.jat.2018.11.001 - S. De Marchi and R. Schaback,
*Nonstandard kernels and their applications*,*Dolomites Res. Notes Approx.*,**2**(2009) 16–43. - Josef Dick, Christian Irrgeher, Gunther Leobacher, and Friedrich Pillichshammer,
*On the optimal order of integration in Hermite spaces with finite smoothness*, SIAM J. Numer. Anal.**56**(2018), no. 2, 684–707. MR**3780119**, DOI 10.1137/16M1087461 - G. E. Fasshauer, F. J. Hickernell, and H. Woźniakowski,
*Average case approximation: convergence and tractability of Gaussian kernels*, Monte Carlo and quasi-Monte Carlo methods 2010, Springer Proc. Math. Stat., vol. 23, Springer, Heidelberg, 2012, pp. 329–344. MR**3173842**, DOI 10.1007/978-3-642-27440-4_{1}6 - Gregory E. Fasshauer, Fred J. Hickernell, and Henryk Woźniakowski,
*On dimension-independent rates of convergence for function approximation with Gaussian kernels*, SIAM J. Numer. Anal.**50**(2012), no. 1, 247–271. MR**2888312**, DOI 10.1137/10080138X - Fasshauer, G. and McCourt, M. (2015).
*Kernel-based Approximation Methods Using MATLAB*. Number 19 in Interdisciplinary Mathematical Sciences. World Scientific Publishing. - Gregory E. Fasshauer and Michael J. McCourt,
*Stable evaluation of Gaussian radial basis function interpolants*, SIAM J. Sci. Comput.**34**(2012), no. 2, A737–A762. MR**2914302**, DOI 10.1137/110824784 - Walter Gautschi,
*Orthogonal polynomials: computation and approximation*, Numerical Mathematics and Scientific Computation, Oxford University Press, New York, 2004. Oxford Science Publications. MR**2061539**, DOI 10.1093/oso/9780198506720.001.0001 - F. B. Hildebrand,
*Introduction to numerical analysis*, 2nd ed., Dover Publications, Inc., New York, 1987. MR**895822** - Christian Irrgeher, Peter Kritzer, Gunther Leobacher, and Friedrich Pillichshammer,
*Integration in Hermite spaces of analytic functions*, J. Complexity**31**(2015), no. 3, 380–404. MR**3325680**, DOI 10.1016/j.jco.2014.08.004 - Christian Irrgeher, Peter Kritzer, Friedrich Pillichshammer, and Henryk Woźniakowski,
*Approximation in Hermite spaces of smooth functions*, J. Approx. Theory**207**(2016), 98–126. MR**3494224**, DOI 10.1016/j.jat.2016.02.008 - Toni Karvonen and Simo Särkkä,
*Gaussian kernel quadrature at scaled Gauss-Hermite nodes*, BIT**59**(2019), no. 4, 877–902. MR**4032891**, DOI 10.1007/s10543-019-00758-3 - Frances Y. Kuo, Ian H. Sloan, and Henryk Woźniakowski,
*Multivariate integration for analytic functions with Gaussian kernels*, Math. Comp.**86**(2017), no. 304, 829–853. MR**3584550**, DOI 10.1090/mcom/3144 - Frances Y. Kuo and Henryk Woźniakowski,
*Gauss-Hermite quadratures for functions from Hilbert spaces with Gaussian reproducing kernels*, BIT**52**(2012), no. 2, 425–436. MR**2931357**, DOI 10.1007/s10543-011-0358-9 - F. M. Larkin,
*Optimal approximation in Hilbert spaces with reproducing kernel functions*, Math. Comp.**24**(1970), 911–921. MR**285086**, DOI 10.1090/S0025-5718-1970-0285086-9 - Ha Quang Minh,
*Some properties of Gaussian reproducing kernel Hilbert spaces and their implications for function approximation and learning theory*, Constr. Approx.**32**(2010), no. 2, 307–338. MR**2677883**, DOI 10.1007/s00365-009-9080-0 - J. Oettershagen,
*Construction of optimal cubature algorithms with applications to econometrics and uncertainty quantification*, PhD thesis, University of Bonn, 2017. - Rodrigo B. Platte,
*How fast do radial basis function interpolants of analytic functions converge?*, IMA J. Numer. Anal.**31**(2011), no. 4, 1578–1597. MR**2846767**, DOI 10.1093/imanum/drq020 - Rodrigo B. Platte and Tobin A. Driscoll,
*Polynomials and potential theory for Gaussian radial basis function interpolation*, SIAM J. Numer. Anal.**43**(2005), no. 2, 750–766. MR**2177889**, DOI 10.1137/040610143 - Rodrigo B. Platte, Lloyd N. Trefethen, and Arno B. J. Kuijlaars,
*Impossibility of fast stable approximation of analytic functions from equispaced samples*, SIAM Rev.**53**(2011), no. 2, 308–318. MR**2806639**, DOI 10.1137/090774707 - Carl Edward Rasmussen and Christopher K. I. Williams,
*Gaussian processes for machine learning*, Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006. MR**2514435** - Christian Rieger and Barbara Zwicknagl,
*Sampling inequalities for infinitely smooth functions, with applications to interpolation and machine learning*, Adv. Comput. Math.**32**(2010), no. 1, 103–129. MR**2574569**, DOI 10.1007/s10444-008-9089-0 - Christian Rieger and Barbara Zwicknagl,
*Improved exponential convergence rates by oversampling near the boundary*, Constr. Approx.**39**(2014), no. 2, 323–341. MR**3171377**, DOI 10.1007/s00365-013-9211-5 - Herbert Robbins,
*A remark on Stirling’s formula*, Amer. Math. Monthly**62**(1955), 26–29. MR**69328**, DOI 10.2307/2308012 - Robert Schaback,
*Error estimates and condition numbers for radial basis function interpolation*, Adv. Comput. Math.**3**(1995), no. 3, 251–264. MR**1325034**, DOI 10.1007/BF02432002 - Ian H. Sloan and Henryk Woźniakowski,
*Multivariate approximation for analytic functions with Gaussian kernels*, J. Complexity**45**(2018), 1–21. MR**3748595**, DOI 10.1016/j.jco.2017.11.001 - Ingo Steinwart and Andreas Christmann,
*Support vector machines*, Information Science and Statistics, Springer, New York, 2008. MR**2450103** - Ingo Steinwart, Don Hush, and Clint Scovel,
*An explicit description of the reproducing kernel Hilbert spaces of Gaussian RBF kernels*, IEEE Trans. Inform. Theory**52**(2006), no. 10, 4635–4643. MR**2300845**, DOI 10.1109/TIT.2006.881713 - T. J. Sullivan,
*Introduction to uncertainty quantification*, Texts in Applied Mathematics, vol. 63, Springer, Cham, 2015. MR**3364576**, DOI 10.1007/978-3-319-23395-6 - Y. Suzuki,
*Applications and analysis of lattice points: time-stepping and integration over $\mathbb {R}^d$*, PhD thesis, Faculty of Engineering Science, KU Leuven, 2020. - Holger Wendland,
*Scattered data approximation*, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, Cambridge, 2005. MR**2131724**

Retrieve articles in *Mathematics of Computation*
with MSC (2020):
65D30,
46E22,
65D12,
41A25

Retrieve articles in all journals with MSC (2020): 65D30, 46E22, 65D12, 41A25

Additional Information

**Toni Karvonen**

Affiliation:
The Alan Turing Institute, London NW1 2DB, United Kingdom

MR Author ID:
1256975

ORCID:
0000-0002-5984-7295

**Chris J. Oates**

Affiliation:
The Alan Turing Institute, London NW1 2DB, United Kingdom; and School of Mathematics, Statistics & Physics, Newcastle University, Newcastle upon Tyne NE1 7RU, United Kingdom

MR Author ID:
998570

**Mark Girolami**

Affiliation:
The Alan Turing Institute, London NW1 2DB, United Kingdom; and Department of Engineering, University of Cambridge, Cambridge CB2 1PZ, United Kingdom

MR Author ID:
665653

ORCID:
0000-0003-3008-253X

Received by editor(s):
July 1, 2020

Received by editor(s) in revised form:
December 16, 2020

Published electronically:
June 18, 2021

Additional Notes:
The authors were supported by the Lloyd’s Register Foundation programme on data-centric engineering at the Alan Turing Institute, United Kingdom

Article copyright:
© Copyright 2021
American Mathematical Society