Timezone: »

Trustworthy Monte Carlo
Juha Harviainen · Mikko Koivisto · Petteri Kaski

Tue Dec 06 05:00 PM -- 07:00 PM (PST) @

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.

Author Information

Juha Harviainen (University of Helsinki)
Mikko Koivisto (University of Helsinki)
Petteri Kaski (Aalto University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors

  • 2022 Spotlight: Lightning Talks 2A-2 »
    Harikrishnan N B · Jianhao Ding · Juha Harviainen · Yizhen Wang · Lue Tao · Oren Mangoubi · Tong Bu · Nisheeth Vishnoi · Mohannad Alhanahnah · Mikko Koivisto · Aditi Kathpalia · Lei Feng · Nithin Nagaraj · Hongxin Wei · Xiaozhu Meng · Petteri Kaski · Zhaofei Yu · Tiejun Huang · Ke Wang · Jinfeng Yi · Jian Liu · Sheng-Jun Huang · Mihai Christodorescu · Songcan Chen · Somesh Jha
  • 2021 Poster: Approximating the Permanent with Deep Rejection Sampling »
    Juha Harviainen · Antti Röyskö · Mikko Koivisto
  • 2020 Poster: Towards Scalable Bayesian Learning of Causal DAGs »
    Jussi Viinikka · Antti Hyttinen · Johan Pensar · Mikko Koivisto