Breaking the Curse for Uniform Approximation in Hilbert Spaces via Monte Carlo Methods
It extends the known tractability benefits of Monte Carlo methods from integration to approximation problems, providing a new theoretical result for high-dimensional approximation.
The paper shows that for L∞-approximation in periodic tensor product Hilbert spaces (Korobov spaces with smoothness r > 1/2), randomized algorithms break the curse of dimensionality, achieving polynomial tractability with n(ε,d) ≾ ε^{-2} d (1 + log d), whereas deterministic methods suffer exponential growth.
We study the $L_{\infty}$-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(\varepsilon,d)$ of information needed in order to solve a problem to within a given accuracy $\varepsilon > 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(\varepsilon,d) \preceq \varepsilon^{-2} \, d \, (1 + \log d)$. Similar benefits of Monte Carlo methods in terms of tractability have only been known for integration problems so far.