New Certificates Offer Public Verification for Statistical Algorithms

This paper initiates the study of non-interactive proofs of learning by defining a new concept: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs). Building on previous work on interactive proofs, pvCSVs aim to provide a public and distributionally-robust method for certifying the validity of a learning algorithm's output. In this framework, a learner publishes a hypothesis along with a corresponding certificate. Any user, possessing their own specific data distribution, can then efficiently examine this pair to determine if the hypothesis is valid according to their unique distribution. This offers a significant step towards verifiable AI and machine learning. The authors construct pvCSVs within the context of Adaptive Statistical Query (SQ) Algorithms. For SQ algorithms making 'k' adaptive queries, their pvCSVs achieve a sample complexity that scales with O(log k), which is notably more efficient than the best learning algorithms' sample complexity of O(sqrt(k)). The research explores both the strengths and limitations of the SQ model for these proof systems.