  Smolyak's method, also known as hyperbolic cross approximation or sparse grid
method, is a powerful tool to tackle multivariate tensor product problems
solely with the help of efficient algorithms for the corresponding univariate
problem. In this paper we study the randomized setting, i.e., we randomize
Smolyak's method. We provide upper and lower error bounds for randomized
Smolyak algorithms with explicitly given dependence on the number of variables
and the number of information evaluations used. The error criteria we consider
are the worst-case root mean square error (the typical error criterion for
randomized algorithms, often referred to as "randomized error") and the root
mean square worst-case error (often referred to as "worst-case error").
Randomized Smolyak algorithms can be used as building blocks for efficient
methods such as multilevel algorithms, multivariate decomposition methods or
dimension-wise quadrature methods to tackle successfully high-dimensional or
even infnite-dimensional problems. As an example, we provide a very general and
sharp result on the convergence rate of N-th minimal errors of
infnite-dimensional integration on weighted reproducing kernel Hilbert spaces.
Moreover, we are able to characterize the spaces for which randomized
algorithms for infnte-dimensional integration are superior to deterministic
ones. We illustrate our fndings for the special instance of weighted Korobov
spaces. We indicate how these results can be extended, e.g., to spaces of
functions whose smooth dependence on successive variables increases ("spaces of
increasing smoothness") and to the problem of L2-approximation (function
recovery).
