The complexity of function approximation on Sobolev spaces with bounded mixed derivative by linear Monte Carlo methods

We study the information-based complexity of the approximation problem on the multivariate Sobolev space with bounded mixed derivative in the norm of Lq by linear Monte Carlo methods. Applying the Maiorov's discretization technique and some properties of pseudo-s-scale, we determine the exact orders of this problem for 1