Breaking the curse for uniform approximation in Hilbert spaces via Monte Carlo methods

We study the L∞-approximation of d-variate functions from Hilbert spaces via linear functionals as information. It is a common phenomenon in tractability studies that unweighted problems (with each dimension being equally important) suffer from the curse of dimensionality in the deterministic setting, that is, the number n(ϵ,d) of information needed in order to solve a problem within a given accuracy ϵ>0 grows exponentially in d. We show that for certain approximation problems in periodic tensor product spaces, in particular Korobov spaces with smoothness  r>1∕2, switching to the randomized setting can break the curse of dimensionality, now having polynomial tractability, namely n(ϵ,d)⪯ϵ−2d(1+logd). Similar benefits from Monte Carlo methods in terms of tractability have only been known for integration problems so far.