Goldwasser et al. (ITCS'21) 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 $\Omega((\sqrt{d})/\varepsilon^2)$ i.i.d. samples for PAC verification of hypothesis classes with VC dimension $d$. Second, we present a protocol for PAC verification of unions of intervals over $\mathbb{R}$ 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. In particular, this protocol can be used for verification of adaptive data analysis.

----------------

A conference version of this paper appeared in the Proceedings of the Thirty-Sixth Conference on Learning Theory (COLT'23).