Hypercontractivity Meets Random Convex Hulls: Analysis of Randomized Multivariate Cubatures

Abstract

Given a probability measure $\mu$ on a set $\mathcal{X}$ and a vector-valued function $\phi$, a common problem is to construct a discrete probability measure on $\mathcal{X}$ such that the push-forward of these two probability measures under $\phi$ is the same. This construction is at the heart of numerical integration methods that run under various names such as quadrature, cubature, or recombination. A natural approach is to sample points from $\mu$ until their convex hull of their image under $\phi$ includes the mean of $\phi$. Here we analyze the computational complexity of this approach when $\phi$ exhibits a graded structure by using so-called hypercontractivity. The resulting theorem not only covers the classical cubature case of multivariate polynomials, but also integration on pathspace, as well as kernel quadrature for product measures.

arXiv comment20 pages

References in corpus (9)

• Invariance principles for homogeneous sums: Universality of Gaussian Wiener chaos
• High order recombination and an application to cubature on Wiener space
• Stable high-order cubature formulas for experimental data
• On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions
• Monte Carlo construction of cubature on Wiener space
• Estimating the probability that a given vector is in the convex hull of a random sample
• Monte Carlo Cubature Construction
• Positively Weighted Kernel Quadrature via Subsampling
• A Randomized Algorithm to Reduce the Support of Discrete Measures