Faster approximation of high dimensional integrals with Monte Carlo

Start: 09/18/2013 - 1:15pm
End  : 09/18/2013 - 2:15pm

Applied Math Seminar

Mark Huber (CMC)


High dimensional integrals and sums arise often in applications coming from statistics, theoretical physics, and computer science.  Consider the problem of approximating these integrals to within a factor of $ 1 + \epsilon $ for some specified $ \epsilon > 0. $ when the integrand (or summand) is nonnegative..  Monte Carlo methods for approximating these integrals work by drawing samples randomly from a family of distributions formed from the nonnegative integrand.  Typically the value of these integrals is exponentially large in the problem input size, so let $ q $ denote the natural logarithm of the integral in question.  Previous Monte Carlo methods for such approximation used $ O(q \ln(q)^5) $ samples (suppressing the dependence on $ \epsilon $), but the big-O notation hid factors on the order of $ 10^{10} $..  In this work, a new method is presented that uses only $ O(q \ln(q) $ samples, with a factor of about 16.7.  As a bonus, this method is much simpler to implement then previous approaches.  This is the first practical method for creating provably good approximations for these problems.


CMC Campus, Adams Hall, Davidson (the largest lecture room on the first floor)