Anytime Monte Carlo
dc.contributor.author  Murray, LM  
dc.contributor.author  Singh, Sumeetpal  
dc.contributor.author  Lee, A  
dc.date.accessioned  20211022T23:30:16Z  
dc.date.available  20211022T23:30:16Z  
dc.date.issued  2021  
dc.identifier.issn  26326736  
dc.identifier.uri  https://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 realtime 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 continuoustime 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 realtime computing budget can be eliminated by using a multiple chain construction. The utility of this construction is then demonstrated on a largescale SMC<jats:inlineformula> <jats:alternatives> <jats:inlinegraphic xmlns:xlink="http://www.w3.org/1999/xlink" mimesubtype="png" xlink:href="S263267362100006X_inline1.png" /> <jats:texmath>$ {}^2 $</jats:texmath> </jats:alternatives> </jats:inlineformula> implementation, using four billion particles distributed across a cluster of 128 graphics processing units on the Amazon EC2 service. The anytime framework imposes a realtime budget on the MCMC move steps within the SMC<jats:inlineformula> <jats:alternatives> <jats:inlinegraphic xmlns:xlink="http://www.w3.org/1999/xlink" mimesubtype="png" xlink:href="S263267362100006X_inline2.png" /> <jats:texmath>$ {}^2 $</jats:texmath> </jats:alternatives> </jats:inlineformula> 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.language  en  
dc.publisher  Cambridge University Press (CUP)  
dc.rights  Attribution 4.0 International  
dc.rights.uri  https://creativecommons.org/licenses/by/4.0/  
dc.title  Anytime Monte Carlo  
dc.type  Article  
prism.number  e7  
prism.publicationDate  2021  
prism.publicationName  DataCentric Engineering  
prism.volume  2  
dc.identifier.doi  10.17863/CAM.77236  
rioxxterms.versionofrecord  10.1017/dce.2021.6  
rioxxterms.version  VoR  
rioxxterms.licenseref.uri  http://www.rioxx.net/licenses/allrightsreserved  
rioxxterms.licenseref.startdate  2021  
dc.contributor.orcid  Singh, Sumeetpal [0000000254301496]  
dc.identifier.eissn  26326736  
rioxxterms.type  Journal Article/Review  
pubs.funderprojectid  Alan Turing Institute (unknown)  
cam.issuedOnline  20210629 
Files in this item
This item appears in the following Collection(s)

Cambridge University Research Outputs
Research outputs of the University of Cambridge