Optimal Confidence for Monte Carlo Integration of Smooth Functions

Add to your list(s) Download to your calendar using vCal

• Robert J. Kunsch (Universität Osnabrück)
• Thursday 21 February 2019, 13:40-14:15
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact INI IT.

ASCW01 - Challenges in optimal recovery and hyperbolic cross approximation

We study the complexity $n(\varepsilon,\delta)$ of approximating the integral of smooth functions at absolute precision $\varepsilon > 0$ with confidence level $1 – \delta \in (0,1)$ using function evaluations as information within randomized algorithms. Methods that achieve optimal rates in terms of the root mean square error (RMSE) are not always optimal in terms of error at confidence, usually we need some non-linearity in order to suppress outliers. Besides, there are numerical problems which can be solved in terms of error at confidence but no algorithm can guarantee a finite RMSE , see [1]. Hence, the new error criterion seems to be more general than the classical RMSE . The sharp order for multivariate functions from classical isotropic Sobolev spaces $W_p^r([0,1]d)$ can be achieved via control variates, as long as the space is embedded in the space of continuous functions $C([0,1]^{d)$. It turns out that the integrability index $p$ has an effect on the influence of the uncertainty $\delta$ to the complexity, with the limiting case $p = 1$ where deterministic methods cannot be improved by randomization. In general, higher smoothness reduces the effort we need to take in order to increase the confidence level. Determining the complexity $n(\varepsilon,\delta)$ is much more challenging for mixed smoothness spaces $\mathbf{W}_p}r([0,1]^{d)$. While optimal rates are known for the classical RMSE (as long as $\mathbf{W}_p}r([0,1]^{d)$ is embedded in $L_2([0,1]}d)$), see [2], basic modifications of the corresponding algorithms fail to match the theoretical lower bounds for approximating the integral with prescribed confidence.

Joint work with Daniel Rudolf 

[1]  R.J. Kunsch, E. Novak, D. Rudolf. Solvable integration problems and optimal sample size selection.  To appear in Journal of Complexity.
[2]  M. Ullrich. A Monte Carlo method for integration of multivariate smooth functions. SIAM Journal on Numerical Analysis, 55(3):1188-1200, 2017.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.