PAC Verification of Statistical Algorithms

Goldwasser et al. (2021) recently proposed the setting of PAC verification, where a hypothesis (machine learning model) that purportedly satisfies the agnostic PAC learning objective is verified using an interactive proof. In this paper we develop this notion further in a number of ways. First, we prove a lower bound of Omegaleft(√d/varepsilon2right) i.i.d. samples for PAC verification of hypothesis classes of VC dimension d. Second, we present a protocol for PAC verification of unions of intervals over ℝ that improves upon their proposed protocol for that task, and matches our lower bound's dependence on d. Third, we introduce a natural generalization of their definition to verification of general statistical algorithms, which is applicable to a wider variety of settings beyond agnostic PAC learning. Showcasing our proposed definition, our final result is a protocol for the verification of statistical query algorithms that satisfy a combinatorial constraint on their queries.