Uniform recovery of high-dimensional $C^r$-functions
Provides tight sample complexity bounds for uniform approximation of smooth functions in high dimensions, a fundamental problem in approximation theory.
The paper determines the minimal number of function evaluations needed to uniformly approximate high-dimensional smooth functions with bounded derivatives, showing the sample complexity scales as (d^{r/2}/ε)^{d/r} for even r.
We consider functions on the $d$-dimensional unit cube whose partial derivatives up to order $r$ are bounded by one. It is known that the minimal number of function values that is needed to approximate the integral of such functions up to the error $\varepsilon$ is of order $(d/ \varepsilon)^{d/r}$. Among other things, we show that the minimal number of function values that is needed to approximate such functions in the uniform norm is of order $(d^{r/2} /\varepsilon)^{d/r}$ whenever $r$ is even.