Beating Monte Carlo Integration: a Nonasymptotic Study of Kernel Smoothing Methods

Stephan Clémençon, François Portier
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:548-556, 2018.

Abstract

Evaluating integrals is an ubiquitous issue and Monte Carlo methods, exploiting advances in random number generation over the last decades, offer a popular and powerful alternative to integration deterministic techniques, unsuited in particular when the domain of integration is complex. This paper is devoted to the study of a kernel smoothing based competitor built from a sequence of $n\geq 1$ i.i.d random vectors with arbitrary continuous probability distribution $f(x)dx$, originally proposed in Delyon et al. (2016), from a nonasymptotic perspective. We establish a probability bound showing that the method under study, though biased, produces an estimate approximating the target integral $\int_{x\in\mathbb{R}^d}\varphi(x)dx$ with an error bound of order $o(1/\sqrt{n})$ uniformly over a class $\Phi$ of functions $\varphi$, under weak complexity/smoothness assumptions related to the class $\Phi$, outperforming Monte-Carlo procedures. This striking result is shown to derive from an appropriate decomposition of the maximal deviation between the target integrals and their estimates, highlighting the remarkable benefit to averaging strongly dependent terms regarding statistical accuracy in this situation. The theoretical analysis then rests on sharp probability inequalities for degenerate $U$-statistics. It is illustrated by numerical results in the context of covariate shift regression, providing empirical evidence of the relevance of the approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-clemencon18a, title = {Beating {M}onte {C}arlo Integration: a Nonasymptotic Study of Kernel Smoothing Methods}, author = {Clémençon, Stephan and Portier, François}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {548--556}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/clemencon18a/clemencon18a.pdf}, url = {https://proceedings.mlr.press/v84/clemencon18a.html}, abstract = {Evaluating integrals is an ubiquitous issue and Monte Carlo methods, exploiting advances in random number generation over the last decades, offer a popular and powerful alternative to integration deterministic techniques, unsuited in particular when the domain of integration is complex. This paper is devoted to the study of a kernel smoothing based competitor built from a sequence of $n\geq 1$ i.i.d random vectors with arbitrary continuous probability distribution $f(x)dx$, originally proposed in Delyon et al. (2016), from a nonasymptotic perspective. We establish a probability bound showing that the method under study, though biased, produces an estimate approximating the target integral $\int_{x\in\mathbb{R}^d}\varphi(x)dx$ with an error bound of order $o(1/\sqrt{n})$ uniformly over a class $\Phi$ of functions $\varphi$, under weak complexity/smoothness assumptions related to the class $\Phi$, outperforming Monte-Carlo procedures. This striking result is shown to derive from an appropriate decomposition of the maximal deviation between the target integrals and their estimates, highlighting the remarkable benefit to averaging strongly dependent terms regarding statistical accuracy in this situation. The theoretical analysis then rests on sharp probability inequalities for degenerate $U$-statistics. It is illustrated by numerical results in the context of covariate shift regression, providing empirical evidence of the relevance of the approach.} }
Endnote
%0 Conference Paper %T Beating Monte Carlo Integration: a Nonasymptotic Study of Kernel Smoothing Methods %A Stephan Clémençon %A François Portier %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-clemencon18a %I PMLR %P 548--556 %U https://proceedings.mlr.press/v84/clemencon18a.html %V 84 %X Evaluating integrals is an ubiquitous issue and Monte Carlo methods, exploiting advances in random number generation over the last decades, offer a popular and powerful alternative to integration deterministic techniques, unsuited in particular when the domain of integration is complex. This paper is devoted to the study of a kernel smoothing based competitor built from a sequence of $n\geq 1$ i.i.d random vectors with arbitrary continuous probability distribution $f(x)dx$, originally proposed in Delyon et al. (2016), from a nonasymptotic perspective. We establish a probability bound showing that the method under study, though biased, produces an estimate approximating the target integral $\int_{x\in\mathbb{R}^d}\varphi(x)dx$ with an error bound of order $o(1/\sqrt{n})$ uniformly over a class $\Phi$ of functions $\varphi$, under weak complexity/smoothness assumptions related to the class $\Phi$, outperforming Monte-Carlo procedures. This striking result is shown to derive from an appropriate decomposition of the maximal deviation between the target integrals and their estimates, highlighting the remarkable benefit to averaging strongly dependent terms regarding statistical accuracy in this situation. The theoretical analysis then rests on sharp probability inequalities for degenerate $U$-statistics. It is illustrated by numerical results in the context of covariate shift regression, providing empirical evidence of the relevance of the approach.
APA
Clémençon, S. & Portier, F.. (2018). Beating Monte Carlo Integration: a Nonasymptotic Study of Kernel Smoothing Methods. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:548-556 Available from https://proceedings.mlr.press/v84/clemencon18a.html.

Related Material