  Classical algorithms in numerical analysis for numerical integration
(quadrature/cubature) follow the principle of approximate and integrate: the
integrand is approximated by a simple function (e.g. a polynomial), which is
then integrated exactly. In high-dimensional integration, such methods quickly
become infeasible due to the curse of dimensionality. A common alternative is
the Monte Carlo method (MC), which simply takes the average of random samples,
improving the estimate as more and more samples are taken. The main issue with
MC is its slow (though dimension-independent) convergence, and various
techniques have been proposed to reduce the variance. In this work we suggest a
numerical analyst's interpretation of MC: it approximates the integrand with a
constant function, and integrates that constant exactly. This observation leads
naturally to MC-like methods where the approximant is a non-constant function,
for example low-degree polynomials, sparse grids or low-rank functions. We show
that these methods have the same $O(1/\sqrt{N})$ asymptotic convergence as in
MC, but with reduced variance, equal to the quality of the underlying function
approximation. We also discuss methods that improve the approximation quality
as more samples are taken, and thus can converge faster than $O(1/\sqrt{N})$.
The main message is that techniques in high-dimensional approximation theory
can be combined with Monte Carlo integration to accelerate convergence.
