Lower bounds for the complexity of Monte Carlo function approximation (Q1201159)

In this well organised paper the author is concerned with the Monte Carlo approximation of functions in the Sobolev space \(W_ p^ r([0,1]^ d)\) with respect to the norm of \(L_ q([0,1]^ d)\). It is assumed that \(r/d>1/p-1/q\) so that the embedding operator \(I: W_ p^ r\to L_ q\) exists and is continuous. The general framework of the paper is the study of the error of Monte Carlo approximations for linear operators \(S: X\to Y\) between Banach spaces. More precisely, the \(n\)th Monte Carlo error is defined to be \[ e_ n^{MC}(S)=\inf \sup_{\| x\|\leq 1} \int_ \Omega \| Sx-\varphi_ \omega(N_ \omega(x))\| d\omega, \] where \(N_ \omega: X\to\mathbb{R}^{n_ \omega}\) is an `information operator' (e.g., mapping a function onto \(n_ \omega\) of its Fourier coefficients) and \(\varphi_ \omega:\mathbb{R}^{n_ \omega} \to Y\) describes the actual numerical algorithm, both depending on a random parameter \(\omega\) and satisfying suitable measurability conditions. The map \(N_ \omega\) may be adaptive, and \(\varphi_ \omega\) may be nonlinear. The infimum is taken over all random \((N,\varphi)\) such that \(\int n_ \omega d\omega<n\). The first theorem gives a lower bound for \(e_ n^{MC}(S)\) in terms of average Gelfand and approximation numbers of \(S\) with respect to Gaussian measures on \(X\). Here a deviation inequality for Gaussian vectors due to Maurey and Pisier enters in a crucial way. That theorem is applied to identity operators between finite-dimensional \(\ell_ p\)- and \(\ell_ q\)-spaces from which the rate of decay of \(e_ n^{MC}(I)\) for the operator \(I: W_ p^ r\to L_ q\) can be deduced using the Mayorov discretisation technique. It turns out (Theorem 2) that \(e_ n^{MC}(I)\) is of order \(n^{-r/d}\) if \(r>d\) and \(1\leq p,q<\infty\); for the remaining choices of \(p\) and \(q\) results are proved, too.