On the tractability of multivariate integration and approximation by neural networks

AbstractLet q⩾1 be an integer, Q be a Borel subset of the Euclidean space Rq, μ be a probability measure on Q, and F be a class of real valued, μ-integrable functions on Q. The complexity problem of approximating ∫fdμ using quasi-Monte Carlo methods is to estimateEn(F,μ)≔infx1,…,xn∈Qsupf∈F∫fdμ−1n∑k=1nf(xk).The problem is said to be tractable if there exist constants c, α, β independent of q (but possibly dependent on μ and F) such that En(F,μ)⩽cqαn−β. We explore different regions (including manifolds), function classes, and measures for which this problem is tractable. Our results include tractability theorems for integration with respect to non-tensor product measures, and over unbounded and/or non-tensor product subsets, including the unit spheres of Rq with respect to various norms. We discuss applications to approximation capabilities of neural and radial basis function networks