Does there exist a uniform Monte-Carlo Approximation of certain function classes?

45 Views Asked by At

Given a measurable and bounded function $f:X \to \mathbb{R}$ on a metric-measure space $(X, d, \mathcal{P})$, we can approximate $\int_\chi f$ in terms of $N$ iid samples $X_1, \ldots, X_N \sim \mathcal{P}^N$, i.e., for $\delta \in (0,1)$, with probability at least $1-\delta$, we have $$ |\frac{1}{N}\sum_{i=1}^N f(X_i) - \int_X f| \lesssim \frac{\|f\|_\infty \sqrt{\log(1/\delta)}}{\sqrt{N}} $$ by Hoeffdings. Are there sufficient conditions on $X$ or $f$ under which this approximation is uniform in the samples, i.e., a result of the form: Given samples $X_1, \ldots, X_N \sim \mathcal{P}^N$ it holds for all sufficiently regular functions $g$, $$ |\frac{1}{N}\sum_{i=1}^N g(X_i) - \int_X g| \lesssim R\frac{\|g\|_\infty \sqrt{\log(1/\delta)}}{\sqrt{N}}, $$ where $R$ is a term depending on the regularity of the function class or $X$? If not, do there exists results with a worse rate of convergence?