Optimal Monte Carlo Methods for \(L^2\)-Approximation

We construct Monte Carlo methods for the \(L^2\)-approximation in Hilbert spaces of multivariate functions sampling not more than n function values of the target function. Their errors catch up with the rate of convergence and the preasymptotic behavior of the error of any algorithm sampling n pieces of arbitrary linear information, including function values.