Publicly-Verifiable Certificates for Statistical Algorithms

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 tildeO(√k). More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.