  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 $\Omega\left(\sqrt{d}/\varepsilon^2\right)$ 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 $\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.
