Trustworthy Monte Carlo

Juha Harviainen, Petteri Kaski, Mikko Koivisto

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

Abstrakti

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.
AlkuperäiskieliEnglanti
OtsikkoAdvances in Neural Information Processing Systems 35 (NeurIPS 2022)
ToimittajatS. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
KustantajaCurran Associates Inc.
Sivumäärä12
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
https://nips.cc/

Julkaisusarja

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

Conference

ConferenceConference on Neural Information Processing Systems
LyhennettäNeurIPS
Maa/AlueYhdysvallat
KaupunkiNew Orleans
Ajanjakso28/11/202209/12/2022
www-osoite

Sormenjälki

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

Siteeraa tätä