  Given a probability measure $\mu$ on a set $\mathcal{X}$ and a vector-valued
function $\varphi$, a common problem is to construct a discrete probability
measure on $\mathcal{X}$ such that the push-forward of these two probability
measures under $\varphi$ 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 $\varphi$ includes the mean of
$\varphi$. Here we analyze the computational complexity of this approach when
$\varphi$ 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.
