Publicly-Verifiable Certificates for Statistical Algorithms
Machine LearningCryptography and SecurityData Structures and Algorithms
Summary
The authors explore a new way to verify learning results without interaction, called publicly-verifiable certificates of statistical validity (pvCSVs). These certificates let anyone check if a learned hypothesis is accurate based on their own data distribution. They focus on adaptive statistical query algorithms, creating certificates that need fewer samples than prior methods. Their work reveals both the possibilities and limits of using such proofs in the statistical query learning model.
Authors
Michael Ngo, Michael P. Kim
Abstract
Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis $h$ and corresponding certificate $π$; then, any user, who holds a user-specific distribution, can read the pair $(h,π)$ and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes $k$ adaptive queries, we construct pvCSVs where the sample complexity scales with $O(\log k)$, whereas the sample complexity of the best learning algorithms scale with $\tilde{O}(\sqrt{k})$. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.