<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[a4paper]{article} 


%%%%%%%% DO NOT MODIFY THIS PART %%%%%%%%%%
\usepackage{url}
\usepackage[top=2cm, bottom=2cm, left=2cm, right=2cm]{geometry}
\newcommand{\mytitle}[1]{\title{\textsf{\bf{#1}}}}
\date{} %
\pagestyle{empty} %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%% INCLUDE MACRO HERE IF NEEDED %%%%%%%%%%
\def\e{\varepsilon}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%% TITLE %%%
\mytitle{How much randomness is needed for high-confidence Monte Carlo integration?}

%%%% SPEAKER (OR PRESENTATOR OF POSTER) %%%
\author{
\begin{tabular}{c}
	Robert J. Kunsch \\ %
    RWTH Aachen University \\ 
    \url{kunsch@mathc.rwth-aachen.de}
\end{tabular}
}


\begin{document}
\maketitle
\thispagestyle{empty}


%%%% MAIN BODY -- MODIFY THIS %%%%%
We study Monte Carlo methods for integrating smooth functions based on $n$ function evaluations.

The classical way of assessing the precision $\varepsilon$ of a randomized integration method is based on the \emph{root mean squared error} (RMSE) or the \emph{mean error}. Optimal Monte Carlo error rates in terms of the mean error are well known for classical Sobolev spaces $W_p^r\left([0,1]^d\right)$ and can be achieved with methods like control variates, in some cases also via stratified sampling. For spaces $\mathbf{W}_p^{r,\mathrm{mix}}\left([0,1]^d\right)$ of dominating mixed smoothness, optimal integration methods based on a randomly shifted and dilated Frolov rule have been found in \cite{KriegNovak17,MUllrich17}. If, however, the error is measured in terms of small error $\varepsilon$ with high probability $1-\delta$, the so-called \emph{probabilistic} error criterion, see \cite{KR19}, some of the aforementioned methods turn out to be suboptimal with the error $\varepsilon = e(n,\delta)$ depending polynomially on $\delta^{-1}$ instead of the polynomial dependence on $\log\delta^{-1}$ we hope for. Optimality in classical Sobolev spaces can be restored for control variates employing the median-of-means, for stratified sampling concentration phenomena (Hoeffding's inequality) can lead to optimality; in any event, the amount of random numbers in such optimal methods is proportional to $n$. The randomized Frolov rule which uses only $2d$ random parameters independently of $n$, however, turns out to be suboptimal with respect to the probabilistic error criterion.

This raises the question: How small can the probabilistic error be if we limit the amount of randomness? \emph{Restricted} Monte Carlo methods that only use a small amount of random bits have been studied in \cite{HNP04} for the RMSE criterion. A similar study for the probabilistic error criterion of restricted Monte Carlo methods will be presented.


%%%% INCLUDE CO-AUTHORS NAMES HERE IF APPROPRIATE %%%%%

\paragraph{Joint work with:}
Daniel Rudolf.


%%%% BIBLIOGRAPHY -- MODIFY THIS %%%%%
\begin{thebibliography}{1}

\bibitem{KriegNovak17}
D.~Krieg, E.~Novak.
\newblock A universal algorithm for univariate integration.
\newblock {\em Found. Comput. Math.}, 17:895–916, 2017.

\bibitem{MUllrich17}
M.~Ullrich.
\newblock A Monte Carlo method for integration of multivariate smooth functions. \newblock {\em SIAM J. Numer. Anal.}, 55(3):1188--1200, 2017.

\bibitem{KR19}
R.J.~Kunsch, D.~Rudolf.
\newblock Optimal confidence for Monte Carlo integration of smooth functions.
\newblock {\em Adv. Comput. Math.}, 45:3095--3122, 2019.

\bibitem{HNP04}
S.~Heinrich, E.~Novak, and H.~Pfeiffer.
\newblock How many random bits do we need for Monte Carlo
integration?
\newblock In: {\em Monte Carlo and Quasi-Monte Carlo Methods 2002} (H. Niederreiter, ed.), pages 27--49, 2004.

\end{thebibliography}





\end{document}
</pre></body></html>