Tid: 13 februari 2017 kl 15.15-16.15.Seminarierummet 3721, Institutionen för matematik, KTH, Lindstedtsvägen 25, plan 7. Karta!
Föredragshållare: Lawrence Murray, (Uppsala)
Titel: Anytime Monte Carlo
Abstract A Monte Carlo algorithm typically simulates a prescribed number of samples, taking some random real time to complete the computations necessary. This work considers the converse: to impose a real-time budget on the computation, so that the number of samples simulated is random. To complicate matters, the real time taken for each simulation may depend on the sample produced, so that the samples themselves are not independent of their number, and a length bias with respect to compute time is apparent. We propose an anytime framework to address this concern, using a continuous-time Markov jump process to study the progress of the computation in real time. We show that the length bias can be eliminated for any Markov chain Monte Carlo algorithm by using a multiple chain construction. The utility of this construction is demonstrated on a large-scale Sequential Monte Carlo Squared implementation, using four billion particles distributed across a cluster of 128 graphics processing units on the Amazon EC2 service. The anytime framework is used to impose a real-time budget on move steps, ensuring that all processors are simultaneously ready for the resampling step, demonstrably reducing wait times.
|Sidansvarig: Filip Lindskog