Convergence analysis of deterministic kernel-based quadrature rules in misspecified settings. (English) Zbl 07161204
Summary: This paper presents convergence analysis of kernel-based quadrature rules in misspecified settings, focusing on deterministic quadrature in Sobolev spaces. In particular, we deal with misspecified settings where a test integrand is less smooth than a Sobolev RKHS based on which a quadrature rule is constructed. We provide convergence guarantees based on two different assumptions on a quadrature rule: one on quadrature weights and the other on design points. More precisely, we show that convergence rates can be derived (i) if the sum of absolute weights remains constant (or does not increase quickly), or (ii) if the minimum distance between design points does not decrease very quickly. As a consequence of the latter result, we derive a rate of convergence for Bayesian quadrature in misspecified settings. We reveal a condition on design points to make Bayesian quadrature robust to misspecification, and show that, under this condition, it may adaptively achieve the optimal rate of convergence in the Sobolev space of a lesser order (i.e., of the unknown smoothness of a test integrand), under a slightly stronger regularity condition on the integrand.
MSC:
| 65D30 | Numerical integration |
| 65D32 | Numerical quadrature and cubature formulas |
| 65D05 | Numerical interpolation |
| 46E35 | Sobolev spaces and other spaces of “smooth” functions, embedding theorems, trace theorems |
| 46E22 | Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) |
Keywords:
kernel-based quadrature rules; misspecified settings; Sobolev spaces; reproducing kernel Hilbert spaces; Bayesian quadratureReferences:
| [1] | Adams, Ra; Fournier, Jjf, Sobolev Spaces (2003), New York: Academic Press, New York · Zbl 1098.46001 |
| [2] | Aronszajn, N., Theory of reproducing kernels, Transactions of the American Mathematical Society, 68, 3, 337-404 (1950) · Zbl 0037.20701 · doi:10.1090/S0002-9947-1950-0051437-7 |
| [3] | Avron, H.; Sindhwani, V.; Yang, J.; Mahoney, Mw, Quasi-Monte Carlo feature maps for shift-invariant kernels, Journal of Machine Learning Research, 17, 120, 1-38 (2016) · Zbl 1367.68217 |
| [4] | Bach, F., On the equivalence between kernel quadrature rules and random feature expansions, Journal of Machine Learning Research, 18, 19, 1-38 (2017) · Zbl 1435.65045 |
| [5] | Bach, F., Lacoste-Julien, S., Obozinski, G.: On the equivalence between herding and conditional gradient algorithms. In: J. Langford, J. Pineau (eds.) Proceedings of the 29th International Conference on Machine Learning (ICML2012), pp. 1359-1366. Omnipress (2012) |
| [6] | Brenner, Sc; Scott, Lr, The Mathematical Theory of Finite Element Methods (2008), Berlin: Springer, Berlin · Zbl 1135.65042 |
| [7] | Briol, F.X., Oates, C.J., Cockayne, J., Chen, W.Y., Girolami, M.: On the sampling problem for kernel quadrature. In: D. Precup, Y.W. Teh (eds.) Proceedings of the 34th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 70, pp. 586-595. PMLR (2017) |
| [8] | Briol, F.X., Oates, C.J., Girolami, M., Osborne, M.A.: Frank-Wolfe Bayesian quadrature: Probabilistic integration with theoretical guarantees. In: C. Cortes, N.D. Lawrence, D.D. Lee, M. Sugiyama, R. Garnett (eds.) Advances in Neural Information Processing Systems 28, pp. 1162-1170. Curran Associates, Inc. (2015) |
| [9] | Briol, F.X., Oates, C.J., Girolami, M., Osborne, M.A., Sejdinovic, D.: Probabilistic integration: A role in statistical computation? Statistical Science (2018). To appear · Zbl 1420.62135 |
| [10] | Chen, W.Y., Mackey, L., Gorham, J., Briol, F.X., Oates, C.: Stein points. In: J. Dy, A. Krause (eds.) Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 80, pp. 844-853. PMLR (2018) |
| [11] | Chen, Y., Welling, M., Smola, A.: Supersamples from kernel-herding. In: P. Grünwald, P. Spirtes (eds.) Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI 2010), pp. 109-116. AUAI Press (2010) |
| [12] | Cucker, F.; Zhou, Dx, Learning Theory: An approximation theory view point (2007), Cambridge: Cambridge University Press, Cambridge · Zbl 1274.41001 |
| [13] | Diaconis, P., Bayesian numerical analysis, Statistical decision theory and related topics IV, 1, 163-175 (1988) · Zbl 0671.65117 · doi:10.1007/978-1-4613-8768-8_20 |
| [14] | Dick, J., Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high-dimensional periodic functions, SIAM Journal on Numerical Analysis, 45, 2141-2176 (2007) · Zbl 1158.65007 · doi:10.1137/060658916 |
| [15] | Dick, J., Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order, SIAM Journal on Numerical Analysis, 46, 3, 1519-1553 (2008) · Zbl 1189.42012 · doi:10.1137/060666639 |
| [16] | Dick, J., Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands, The Annals of Statistics, 39, 3, 1372-1398 (2011) · Zbl 1298.65011 · doi:10.1214/11-AOS880 |
| [17] | Dick, J.; Kuo, F. Y.; Sloan, I. H., High dimensional numerical integration - the Quasi-Monte Carlo way, Acta Numerica, 22, 133-288 (2013) · Zbl 1296.65004 · doi:10.1017/S0962492913000044 |
| [18] | Dick, J.; Nuyens, D.; Pillichshammer, F., Lattice rules for nonperiodic smooth integrands, Numerische Mathematik, 126, 2, 259-291 (2014) · Zbl 1345.65070 · doi:10.1007/s00211-013-0566-0 |
| [19] | Frazier, M., Jawerth, B., Weiss, G.L.: Littlewood-Paley Theory and the Study of Function Spaces. American Mathematical Society (1991) · Zbl 0757.42006 |
| [20] | Fuselier, E.; Hangelbroek, T.; Narcowich, Fj; Ward, Jd; Wright, Gb, Kernel based quadrature on spheres and other homogeneous spaces, Numerische Mathematik, 127, 1, 57-92 (2014) · Zbl 1302.65065 · doi:10.1007/s00211-013-0581-1 |
| [21] | Gerber, M.; Chopin, N., Sequential quasi Monte Carlo, Journal of the Royal Statistical Society. Series B. Statistical Methodology, 77, 3, 509-579 (2015) · Zbl 1414.62109 · doi:10.1111/rssb.12104 |
| [22] | Ghahramani, Z., Rasmussen, C.E.: Bayesian monte carlo. In: S. Becker, S. Thrun, K. Obermayer (eds.) Advances in Neural Information Processing Systems 15, pp. 505-512. MIT Press (2003) |
| [23] | Goda, T.; Dick, J., Construction of interlaced scrambled polynomial lattice rules of arbitrary high order, Foundations of Computational Mathematics, 15, 5, 1245-1278 (2015) · Zbl 1323.65002 · doi:10.1007/s10208-014-9226-8 |
| [24] | Gretton, A.; Borgwardt, K.; Rasch, M.; Schölkopf, B.; Smola, A., A kernel two-sample test, Jounal of Machine Learning Research, 13, 723-773 (2012) · Zbl 1283.62095 |
| [25] | Gunter, T., Osborne, M.A., Garnett, R., Hennig, P., Roberts, S.J.: Sampling for inference in probabilistic models with fast Bayesian quadrature. In: Z. Ghahramani, M. Welling, C. Cortes, N.D. Lawrence, K.Q. Weinberger (eds.) Advances in Neural Information Processing Systems 27, pp. 2789-2797. Curran Associates, Inc. (2014) |
| [26] | Hickernell, Fj, A generalized discrepancy and quadrature error bound, Mathematics of Computation, 67, 221, 299-322 (1998) · Zbl 0889.41025 · doi:10.1090/S0025-5718-98-00894-1 |
| [27] | Huszár, F., Duvenaud, D.: Optimally-weighted herding is Bayesian quadrature. In: N. de Freitas, K. Murphy (eds.) Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence (UAI2012), pp. 377-385. AUAI Press (2012) |
| [28] | Kanagawa, M.; Nishiyama, Y.; Gretton, A.; Fukumizu, K., Filtering with state-observation examples via kernel monte carlo filter, Neural Computation, 28, 2, 382-444 (2016) · Zbl 1418.62361 · doi:10.1162/NECO_a_00806 |
| [29] | Kanagawa, M., Sriperumbudur, B.K., Fukumizu, K.: Convergence guarantees for kernel-based quadrature rules in misspecified settings. In: D.D. Lee, M. Sugiyama, U.V. Luxburg, I. Guyon, R. Garnett (eds.) Advances in Neural Information Processing Systems 29, pp. 3288-3296. Curran Associates, Inc. (2016) |
| [30] | Karvonen, T., Oates, C.J., Särkkä, S.: A Bayes-Sard cubature method. In: Advances in Neural Information Processing Systems 31. Curran Associates, Inc. (2018). To appear · Zbl 1435.62030 |
| [31] | Kersting, H., Hennig, P.: Active uncertainty calibration in Bayesian ODE solvers. In: Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence (UAI 2016), pp. 309-318. AUAI Press (2016) |
| [32] | Lacoste-Julien, S., Lindsten, F., Bach, F.: Sequential kernel herding: Frank-Wolfe optimization for particle filtering. In: G. Lebanon, S.V.N. Vishwanathan (eds.) Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 38, pp. 544-552. PMLR (2015) |
| [33] | Matèrn, B.: Spatial variation. Meddelanden fran Statens Skogsforskningsinstitut 49(5) (1960) · Zbl 0608.62122 |
| [34] | Matèrn, B., Spatial Variation (1986), Berlin: Springer-Verlag, Berlin · Zbl 0608.62122 |
| [35] | Minka, T.: Deriving quadrature rules from Gaussian processes. Tech. rep., Statistics Department, Carnegie Mellon University (2000) |
| [36] | Muandet, K.; Fukumizu, K.; Sriperumbudur, Bk; Schölkopf, B., Kernel mean embedding of distributions : A review and beyond, Foundations and Trends in Machine Learning, 10, 1-2, 1-141 (2017) · Zbl 1380.68336 · doi:10.1561/2200000060 |
| [37] | Narcowich, Fj; Ward, Jd, Scattered-data interpolation on \(\mathbb{R}^n\): Error estimates for radial basis and band-limited functions, SIAM Journal on Mathematical Analysis, 36, 284-300 (2004) · Zbl 1081.41014 · doi:10.1137/S0036141002413579 |
| [38] | Narcowich, Fj; Ward, Jd; Wendland, H., Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting, Mathematics of Computation, 74, 250, 743-763 (2005) · Zbl 1063.41013 · doi:10.1090/S0025-5718-04-01708-9 |
| [39] | Narcowich, Fj; Ward, Jd; Wendland, H., Sobolev error estimates and a Bernstein inequality for scattered data interpolation via radial basis functions, Constructive Approximation, 24, 2, 175-186 (2006) · Zbl 1120.41022 · doi:10.1007/s00365-005-0624-7 |
| [40] | Novak, E., Deterministic and Stochastic Error Bounds in Numerical Analysis (1988), Berlin: Springer-Verlag, Berlin · Zbl 0656.65047 |
| [41] | Novak, E.: Some results on the complexity of numerical integration. In: R. Cools, D. Nuyens (eds.) Monte Carlo and Quasi-Monte Carlo Methods. Springer Proceedings in Mathematics & Statistics, vol. 163, pp. 161-183. Springer, Cham (2016) · Zbl 1356.65085 |
| [42] | Novak, E.; Wózniakowski, H., Tractability of Multivariate Problems, Vol (2010), II: Standard Information for Functionals. EMS, II · Zbl 1241.65025 |
| [43] | Oates, C., Niederer, S., Lee, A., Briol, F.X., Girolami, M.: Probabilistic models for integration error in the assessment of functional cardiac models. In: I. Guyon, U.V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, R. Garnett (eds.) Advances in Neural Information Processing Systems 30, pp. 110-118. Curran Associates, Inc. (2017) |
| [44] | Oates, C.J., Cockayne, J., Briol, F.X., Girolami, M.: Convergence rates for a class of estimators based on Stein’s method. Bernoulli (2018). To appear · Zbl 1459.60064 |
| [45] | Oates, C.J., Girolami, M.: Control functionals for quasi-Monte Carlo integration. In: A. Gretton, C.C. Robert (eds.) Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, vol. 51, pp. 56-65. PMLR (2016) |
| [46] | Oates, Cj; Girolami, M.; Chopin, N., Control functionals for Monte Carlo integration, Journal of the Royal Statistical Society, Series B, 79, 2, 323-380 (2017) · Zbl 1414.62088 · doi:10.1111/rssb.12187 |
| [47] | Oates, Cj; Papamarkou, T.; Girolami, M., The controlled thermodynamic integral for Bayesian model evidence evaluation, Journal of the American Statistical Association, 111, 514, 634-645 (2016) · doi:10.1080/01621459.2015.1021006 |
| [48] | O’Hagan, A., Bayes-Hermite quadrature, Journal of Statistical Planning and Inference, 29, 245-260 (1991) · Zbl 0829.65024 · doi:10.1016/0378-3758(91)90002-V |
| [49] | Osborne, M.A., Duvenaud, D.K., Garnett, R., Rasmussen, C.E., Roberts, S.J., Ghahramani, Z.: Active learning of model evidence using Bayesian quadrature. In: F. Pereira, C.J.C. Burges, L. Bottou, K.Q. Weinberger (eds.) Advances in Neural Information Processing Systems 25, pp. 46-54. Curran Associates, Inc. (2012) |
| [50] | Paul, S., Chatzilygeroudis, K., Ciosek, K., Mouret, J.B., Osborne, M.A., Whiteson, S.: Alternating optimisation and quadrature for robust control. In: The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18), pp. 3925-3933 (2018) · Zbl 1525.68124 |
| [51] | Särkkä, S.; Hartikainen, J.; Svensson, L.; Sandblom, F., On the relation between Gaussian process quadratures and sigma-point methods, Journal of Advances in Information Fusion, 11, 1, 31-46 (2016) |
| [52] | Schaback, R., Error estimates and condition numbers for radial basis function interpolation, Advances in Computational Mathematics, 3, 3, 251-264 (1995) · Zbl 0861.65007 · doi:10.1007/BF02432002 |
| [53] | Schaback, R.; Wendland, H., Kernel techniques: From machine learning to meshless methods, Acta Numerica, 15, 543-639 (2006) · Zbl 1111.65108 · doi:10.1017/S0962492906270016 |
| [54] | Sloan, Ih; Wózniakowski, H., When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?, Journal of Complexity, 14, 1, 1-33 (1998) · Zbl 1032.65011 · doi:10.1006/jcom.1997.0463 |
| [55] | Sommariva, A.; Vianello, M., Numerical cubature on scattered data by radial basis functions, Computing, 76, 295-310 (2006) · Zbl 1091.65026 · doi:10.1007/s00607-005-0142-2 |
| [56] | Sriperumbudur, Bk; Gretton, A.; Fukumizu, K.; Schölkopf, B.; Lanckriet, Gr, Hilbert space embeddings and metrics on probability measures, Jounal of Machine Learning Research, 11, 1517-1561 (2010) · Zbl 1242.60005 |
| [57] | Stein, Em, Singular Integrals and Differentiability Properties of Functions (1970), Princeton, NJ: Princeton University Press, Princeton, NJ · Zbl 0207.13501 |
| [58] | Steinwart, I.; Christmann, A., Support Vector Machines (2008), Berlin: Springer, Berlin · Zbl 1203.68171 |
| [59] | Triebel, H.: Theory of Function Spaces III. Birkhäuser Verlag (2006) · Zbl 1104.46001 |
| [60] | Wendland, H., Piecewise polynomial, positive definite and compactly supported radial functions of minimal degree, Advances in Computational Mathematics, 4, 1, 389-396 (1995) · Zbl 0838.41014 · doi:10.1007/BF02123482 |
| [61] | Wendland, H., Scattered Data Approximation (2005), Cambridge, UK: Cambridge University Press, Cambridge, UK · Zbl 1075.65021 |
| [62] | Xi, X., Briol, F.X., Girolami, M.: Bayesian quadrature for multiple related integrals. In: J. Dy, A. Krause (eds.) Proceedings of the 35th International Conference on Machine Learning, Proceedings of Machine Learning Research, vol. 80, pp. 5373-5382. PMLR (2018) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
