论文标题
PAC的统计算法验证
PAC Verification of Statistical Algorithms
论文作者
论文摘要
Goldwasser等。 （2021）最近提出了PAC验证的设置，其中据称满足不可知论PAC学习目标的假设（机器学习模型）使用交互式证明进行了验证。在本文中，我们以多种方式进一步发展了这个概念。首先，我们证明了$ω\ left（\ sqrt {d}/\ varepsilon^2 \ right）$ i.i.d. \ samples的下限（\ sqrt {d}/\ varepsilon^2 \ right），用于PAC验证VC尺寸$ d $的假设类别。其次，我们提出了一项协议，用于PAC验证$ \ Mathbb {r} $的间隔工会，该协议根据其提出的该任务的协议改进，并匹配我们的下限对$ d $的依赖。第三，我们将其定义的自然概括引入了对一般统计算法的验证，该算法适用于不可知论PAC学习以外的各种环境。展示我们提出的定义，我们的最终结果是验证统计查询算法的协议，该算法满足了对其查询的组合约束。
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 $Ω\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.
