Trustworthy Monte Carlo

Juha Harviainen, Petteri Kaski, Mikko Koivisto

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu


Monte Carlo integration is a key technique for designing randomized approximation schemes for counting problems, with applications, e.g., in machine learning and statistical physics. The technique typically enables massively parallel computation, however, with the risk that some of the delegated computations contain spontaneous or adversarial errors. We present an orchestration of the computations such that the outcome is accompanied with a proof of correctness that can be verified with substantially less computational resources than it takes to run the computations from scratch with state-of-the-art algorithms. Specifically, we adopt an algebraic proof system developed in computational complexity theory, in which the proof is represented by a polynomial; evaluating the polynomial at a random point amounts to a verification of the proof with probabilistic guarantees. We give examples of known Monte Carlo estimators that admit verifiable extensions with moderate computational overhead: for the permanent of zero--one matrices, for the model count of disjunctive normal form formulas, and for the gradient of logistic regression models. We also discuss the prospects and challenges of engineering efficient verifiable approximation schemes more generally.
OtsikkoAdvances in Neural Information Processing Systems 35 (NeurIPS 2022)
ToimittajatS. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
KustantajaCurran Associates Inc.
ISBN (painettu)978-1-7138-7108-8
TilaJulkaistu - 2022
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaConference on Neural Information Processing Systems - New Orleans, Yhdysvallat
Kesto: 28 marrask. 20229 jouluk. 2022
Konferenssinumero: 36


NimiAdvances in Neural Information Processing Systems
KustantajaMorgan Kaufmann Publishers
ISSN (painettu)1049-5258


ConferenceConference on Neural Information Processing Systems
KaupunkiNew Orleans


Sukella tutkimusaiheisiin 'Trustworthy Monte Carlo'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä