Lower bounds for the complexity of Monte Carlo function approximation (Q1201159): Difference between revisions

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.