The curse of dimensionality for numerical integration on general domains

Abstract

We prove the curse of dimensionality in the worst case setting for multivariate numerical integration for various classes of smooth functions. We prove the results when the domains are isotropic convex bodies with small diameter satisfying a universal ${\psi }_2$-estimate. In particular, we obtain the result for the important class of volume-normalized ${\ell }_p^d$-balls in the complete regime $2\le p\le \infty$. This extends a result in a work of A. Hinrichs, E. Novak, M. Ullrich and H. Woźniakowski [J. Complexity, 30(2), 117-143, 2014] to the whole range $2\le p\le \infty$, and additionally provides a unified approach. The key ingredient in the proof is a deep result from the theory of Asymptotic Geometric Analysis, the thin-shell volume concentration estimate due to O. Guédon and E. Milman. The connection of Asymptotic Geometric Analysis and Information-based Complexity revealed in this work seems promising and is of independent interest.

19 pages

References in corpus (2)

• A probabilistic approach to the geometry of the \ell_p^n-ball
• A Central Limit Theorem for Convex Sets

Cited by in corpus (8)

• Fusion of Probability Density Functions
• Exponential tractability of $L_2$-approximation with function values
• On norms in some class of exponential type Orlicz spaces of random variables
• Spectral flatness and the volume of intersections of $p$-ellipsoids
• Approximation of Functions: Optimal Sampling and Complexity
• Algorithms and Complexity for some Multivariate Problems
• Tractability properties of the discrepancy in Orlicz norms
• Limit theorems for mixed-norm sequence spaces with applications to volume distribution