Show simple item record

dc.contributor.authorMurray, LM
dc.contributor.authorSingh, Sumeetpal
dc.contributor.authorLee, A
dc.date.accessioned2021-10-22T23:30:16Z
dc.date.available2021-10-22T23:30:16Z
dc.date.issued2021
dc.identifier.issn2632-6736
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/329791
dc.description.abstract<jats:title>Abstract</jats:title> <jats:p>Monte Carlo algorithms simulates some 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, which results in the number of samples simulated being 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. This is especially problematic when a Markov chain Monte Carlo (MCMC) algorithm is used and the final state of the Markov chain—rather than an average over all states—is required, which is the case in parallel tempering implementations of MCMC. The length bias does not diminish with the compute budget in this case. It also occurs in sequential Monte Carlo (SMC) algorithms, which is the focus of this paper. We propose an <jats:italic>anytime</jats:italic> framework to address the concern, using a continuous-time Markov jump process to study the progress of the computation in real time. We first show that for any MCMC algorithm, the length bias of the final state’s distribution due to the imposed real-time computing budget can be eliminated by using a multiple chain construction. The utility of this construction is then demonstrated on a large-scale SMC<jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S263267362100006X_inline1.png" /> <jats:tex-math>$ {}^2 $</jats:tex-math> </jats:alternatives> </jats:inline-formula> implementation, using four billion particles distributed across a cluster of 128 graphics processing units on the Amazon EC2 service. The anytime framework imposes a real-time budget on the MCMC move steps within the SMC<jats:inline-formula> <jats:alternatives> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="png" xlink:href="S263267362100006X_inline2.png" /> <jats:tex-math>$ {}^2 $</jats:tex-math> </jats:alternatives> </jats:inline-formula> algorithm, ensuring that all processors are simultaneously ready for the resampling step, demonstrably reducing idleness to due waiting times and providing substantial control over the total compute budget.</jats:p>
dc.languageen
dc.publisherCambridge University Press (CUP)
dc.rightsAttribution 4.0 International
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.titleAnytime Monte Carlo
dc.typeArticle
prism.numbere7
prism.publicationDate2021
prism.publicationNameData-Centric Engineering
prism.volume2
dc.identifier.doi10.17863/CAM.77236
rioxxterms.versionofrecord10.1017/dce.2021.6
rioxxterms.versionVoR
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserved
rioxxterms.licenseref.startdate2021
dc.contributor.orcidSingh, Sumeetpal [0000-0002-5430-1496]
dc.identifier.eissn2632-6736
rioxxterms.typeJournal Article/Review
pubs.funder-project-idAlan Turing Institute (unknown)
cam.issuedOnline2021-06-29


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution 4.0 International
Except where otherwise noted, this item's licence is described as Attribution 4.0 International