Theory of Computing
-------------------
Title     : PAC Verification of Statistical Algorithms
Authors   : Saachi Mutreja and Jonathan Shafer
Volume    : 22
Number    : 5
Pages     : 1-40
URL       : https://theoryofcomputing.org/articles/v022a005

Abstract
--------

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})/\epsilon^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).