Delayed curse of dimension for Gaussian integration (Q1578431): Difference between revisions

The author studies multivariate Gaussian integration of Lipschitz functions in the \(l_p\)-norm, \(p\in [1,\infty]\), defined over the \(d\)-dimensional space. He assumes that the Gaussian weight has a diagonal covariance matrix with positive and ordered variances \(\sigma_i\), \(\sigma_1\geq \sigma_2,\geq\cdots\geq \sigma_d\). The problem is considered of how the worst case complexity of computing an \(\varepsilon\)-approximation, \(\text{comp}(\varepsilon)\), depends on the variance \(\sigma_i\), \(i= 1,\dots, d\). For a fixed \(\varepsilon\) the author provides lower and upper bounds on \(\text{comp}(\varepsilon)\) of the form \(\varepsilon^{-t}\) where the exponent \(t\) is small for small variances \(\sigma_i\). He calls this moderation of the exponential growth of the complexity the delayed curse of dimension. He proves similar upper and lower bounds for the problem of integration of Lipschitz functions on sequence spaces \(l_p\), \(p\in [1,\infty)\), which is essentially the problem of path integration with a Gaussian measure for which \(\sum^\infty_{i=1} \sigma^{p/2}_i< \infty\). Finally, the author obtains an upper bound for the problem of Gaussian integration when the integrands belong to the Sobolev class \(W^{r,\infty}(\mathbb{R}^d)\), \(d< \infty\), of functions with bounded (generalized) derivatives of order \(r\).