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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Lower bounds for the complexity of Monte Carlo function approximation
scientific article

    Statements

    Lower bounds for the complexity of Monte Carlo function approximation (English)
    0 references
    0 references
    17 January 1993
    0 references
    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.
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    information operator
    0 references
    Sobolev space
    0 references
    embedding operator
    0 references
    Monte Carlo approximations for linear operators
    0 references
    average Gelfand and approximation numbers
    0 references
    Gaussian measures
    0 references
    Mayorov discretisation technique
    0 references
    0 references
    0 references