Complexity of Functional Learning on Some Classes of Multivariate Functions

We study the error of the functional learning on anisotropic Sobolev classes W_p ^r (Id) and Holder-Nikolskiiclasses H_p ^r(Id) with respect to the worst case randomized methods and the average case deterministic methods, where 1 les p les infin. Our results show that if p ges 2 then the stochastic and average error bounds are essentially smaller than the deterministic ones. Quantitatively the improvement amounts to the factor n^-1/2.