The information-based complexity of approximation problem by adaptive Monte Carlo methods

In this paper, we study the complexity of information of approximation problem on the multivariate Sobolev space with bounded mixed derivative MW _p,α ^r (), 1 < p < ∞, in the norm of L _q (), 1 < q < ∞, by adaptive Monte Carlo methods. Applying the discretization technique and some properties of pseudo-s-scale, we determine the exact asymptotic orders of this problem. This work was supported by the National Natural Science Foundation of China (Grant No. 10671019) and the Research Fund for the Doctoral Program of Higher Education (Grant No. 20050027007)