统计算法的可公开验证证书

# 统计算法的公开可验证证书

来源：https://arxiv.org/html/2607.15528

Michael Ngo  
MIT  
mingo@mit\.edu  

研究在康奈尔大学完成，得到Bowers本科生研究体验（BURE）及Dean Archer本科生研究项目的资助。本研究还得到Google的捐赠支持。

Michael P\. Kim  
Cornell University  
mpk@cs\.cornell\.edu  

（2026年4月1日）

###### 摘要

继Goldwasser、Rothblum、Shafer和Yehudayoff定义学习交互式证明框架之后\[GRS\+21 (https://arxiv.org/html/2607.15528#bib.bib41)\]，我们开启了非交互式学习证明的研究。我们定义并研究了一个新概念：*公开可验证统计有效性证书*（publicly-verifiable Certificates of Statistical Validity, pvCSV），它允许对学习算法的结果进行公开的、分布鲁棒的认证。在pvCSV中，学习器发布假设$h$和对应的证书$\pi$；然后，任何持有用户特定分布的用户都可以读取这对信息$(h,\pi)$，并高效地判断该假设*根据该用户特定分布*是否有效。我们为自适应统计查询（SQ）算法构造了pvCSV。对于进行$k$次自适应查询的SQ算法，我们构造的pvCSV样本复杂度为$O(\log k)$，而最佳学习算法的样本复杂度为$\tilde{O}(\sqrt{k})$。更一般地，我们研究了SQ模型中的学习证明系统，展示了该模型的优势及其局限性。

## 1 引言

使用统计机器学习训练大规模AI模型成本高昂是众所周知的。由于运行机器学习算法需要大量资源，AI用户依赖少数科技公司的预训练模型。这些公司声称拥有足够的数据来训练通用模型，这些模型能在广泛场景中有效工作。然而，在这种设置下，用户得不到关于AI模型是否经过恰当训练的保证。如果用户担心训练数据未能充分反映其自身场景，他们必须自行调查模型是否在其应用中产生错误（甚至更糟的伤害）。

受这些问题启发，Goldwasser、Shafer、Rothblum和Yehudayoff\[GRS\+21 (https://arxiv.org/html/2607.15528#bib.bib41)\]引入并研究了通过PAC验证框架委托机器学习的问题。PAC验证建立在交互式证明的经典模型之上\[GMR85 (https://arxiv.org/html/2607.15528#bib.bib1),BAB85 (https://arxiv.org/html/2607.15528#bib.bib34)\]，形式化了如下问题：一个统计资源有限的用户（*验证者*）与一个强大但不可信的学习器（*证明者*）交互，后者试图说服用户某个给定模型（*假设*）是有效的。与密码学证明系统类似，PAC验证要求用于委托学习的协议满足形式化的*完备性*和*可靠性*概念。迄今为止，该领域的研究主要集中于为特定概念类开发验证不可知PAC学习\[VAL84 (https://arxiv.org/html/2607.15528#bib.bib6),HAU92 (https://arxiv.org/html/2607.15528#bib.bib7),KSS94 (https://arxiv.org/html/2607.15528#bib.bib8)\]的协议\[GRS\+21 (https://arxiv.org/html/2607.15528#bib.bib41),MS23 (https://arxiv.org/html/2607.15528#bib.bib42),GJK\+24 (https://arxiv.org/html/2607.15528#bib.bib44)\]。一个值得注意的例外是，Mutreja和Shafer\[MS23 (https://arxiv.org/html/2607.15528#bib.bib42)\]还引入了一种用于损失最小化的统计查询（SQ）算法委托概念。

先前关于学习委托工作的一个基本要素是*交互*。为了确定一个给定假设是否有效，证明者和验证者在线交换一系列消息，之后验证者选择接受或拒绝证明者的假设。一个具体例子是，关于PAC验证的原始工作展示了如何委托Goldreich-Levin算法\[GL89 (https://arxiv.org/html/2607.15528#bib.bib5)\]（该算法需要对未知函数的点查询访问），而验证者只拥有独立同分布的带标签样本。在这个证明系统中，验证者利用与证明者的交互来标记点查询，同时巧妙地隐藏一些其已知标签的点，以确保可靠性。早期关于PAC验证的工作已经表明，交互式证明系统为高效检查昂贵机器学习计算的结果提供了一个强大工具。111在这些工作以及我们的论文中，“效率”主要关注统计资源而非计算资源。

然而，交互也带来了挑战。最直接的是，运行一个交互式证明需要验证者和证明者同时在线以执行协议。此外，每次执行交互式证明可能需要证明者回答特定于执行的挑战，包括重新运行原始的机器学习计算。考虑到训练机器学习模型的首要成本极其高昂，提供商可能不愿意（甚至完全不愿意）参与多次交互式证明。在这种情况下，交互式证明只执行一次——在学习器和单个验证者之间——那么许多用户就必须信任单个实体。即使用户同意该验证者通常值得信赖，但如前所述，个别用户可能会担心验证者的数据不能代表他们的场景和应用。

#### 我们的工作

我们开启了非交互式学习证明的研究。我们的研究引出了一个新概念：*公开可验证统计有效性证书（pvCSV）*。pvCSV允许对学习算法的结果进行公开的、分布鲁棒的认证。具体而言，pvCSV使学习器能够发布一个假设$h$和有效性证书$\pi$，从而允许*任何*下游用户随后验证该假设在*用户指定的*分布上具有统计有效性。我们可以通过想象两个世界来理解pvCSV的语义。

- • 在第一个世界中，用户从其场景和应用相关的分布$\mathcal{D}$中收集大量数据。然后，他们在这批数据上正确执行统计学习算法$\mathcal{A}$，得到假设$h_{\mathrm{ideal}}$。
- • 在第二个世界中，一个集中化的、资源充足的学习器针对算法$\mathcal{A}$发布pvCSV$(h_{\mathrm{real}},\pi)$；同一个用户从$\mathcal{D}$中收集更为适量的数据，然后读取并验证$(h_{\mathrm{real}},\pi)$，使用少量用户特定数据。pvCSV保证，如果$(h_{\mathrm{real}},\pi)$通过验证，那么根据用户特定数据分布和学习算法$\mathcal{A}$，这两个世界产生了同等有效的假设$h_{\mathrm{ideal}} \approx_{\mathcal{D},\mathcal{A}} h_{\mathrm{real}}$。即使用户不知道用于生成pvCSV的数据分布，这一保证也必须成立。因此，pvCSV解决了交互式证明用于学习委托的关键缺陷：学习器可以执行昂贵的训练算法一次，并（以少量开销）生成相应的pvCSV证书，任何用户之后都可以验证该证书。

#### 自适应数据分析的认证

我们通过重新审视统计查询模型\[KEA98 (https://arxiv.org/html/2607.15528#bib.bib40)\]中的自适应数据分析问题\[DFH\+15b (https://arxiv.org/html/2607.15528#bib.bib17)\]，使我们的pvCSV研究具体化。许多从数据中学习的工具——包括像梯度下降这样的主流机器学习算法——都可以被框架化为自适应统计算法。在这种算法中，学习器被允许向数据分布提出一系列查询（例如，*$\mathcal{D}$上期望损失的梯度是多少？*），其中每个查询可能依赖于先前查询的结果。形式上，我们考虑与统计查询（SQ）预言机$\mathcal{O}$交互的学习算法$\mathcal{A}$：给定容忍度$\tau$和查询$q$，$\mathcal{O}(q)$返回谓词$q$关于数据分布的期望的一个$\tau$-精确估计。对我们的研究至关重要的是，算法可以*自适应地*根据先前的响应选择其查询序列。也就是说，算法对第$i$个查询$q_i$的选择可能任意依赖于先前的查询$q_1,\ldots,q_{i-1}$和响应$\mathcal{O}(q_1),\ldots,\mathcal{O}(q_{i-1})$（例如，*在进行了第$i-1$步梯度下降后，第$i$次迭代的梯度是多少？*）。

虽然自适应数据分析范式是学习的一种多功能且强大的工具，但此类算法已知在统计上是昂贵的。大约十年前，\[DFH\+15b (https://arxiv.org/html/2607.15528#bib.bib17)\]将自适应性确定为统计算法中的一个关键问题。为了保持自适应分析的统计有效性，学习器要么必须为每个新查询重新采样新鲜数据，要么采用复杂的（差分隐私）算法来回答查询以防止对数据集过拟合\[DFH\+15b (https://arxiv.org/html/2607.15528#bib.bib17),DFH\+15a (https://arxiv.org/html/2607.15528#bib.bib18),DFH\+15c (https://arxiv.org/html/2607.15528#bib.bib19),BNS\+16 (https://arxiv.org/html/2607.15528#bib.bib21),FS18 (https://arxiv.org/html/2607.15528#bib.bib24),JLN\+19 (https://arxiv.org/html/2607.15528#bib.bib22),DK22 (https://arxiv.org/html/2607.15528#bib.bib25),BLA25 (https://arxiv.org/html/2607.15528#bib.bib26)\]。为了回答$k$次自适应选择的统计查询，最好的算法使用的样本数量大致与$\sqrt{k}$成比例，事实上这种依赖关系本质上是紧的\[HU14 (https://arxiv.org/html/2607.15528#bib.bib23),SU15 (https://arxiv.org/html/2607.15528#bib.bib20)\]。换句话说，无论采用何种技术，自适应统计算法所需的样本量比非自适应（批量）统计分析在类似规模下*指数级*更多。

在这项工作中，我们问：何时我们能够比学习更高效地认证自适应数据分析的结果？

### 1.1 我们的贡献

我们为委托*任意自适应*的统计算法开发了证明系统，其中验证者所需的样本数量仅随*非自适应*复杂度增长。通过这样做，我们实现了执行SQ算法与验证SQ算法之间样本复杂度的*指数级*差距。超越先前关于学习*交互式*证明的工作，我们构建了新颖的*非交互式*证明系统——即*公开可验证统计有效性证书*——它实现了一种新的分布鲁棒的统计学习验证形式。在此过程中，我们对先前的学习委托证明系统模型进行了多项扩展。

#### 公开可验证统计有效性证书

在第3节（https://arxiv.org/html/2607.15528#S3）中，我们介绍我们的主要贡献：一种新的证明概念，允许对学习进行公开的、分布鲁棒的认证。*公开可验证统计有效性证书*（pvCSV）是一种非交互式证明系统，允许任何验证者*针对验证者自身的分布*认证一个统计计算的结果。pvCSV允许单个资源充足的学习器（即证明者）以一种可被任何下游验证者高效（以更少资源）检查的方式发布统计计算的结果；特别是，验证者无需持有与证明者相同的分布。相反，该证明系统保证一个*通用可靠性*性质：如果验证者接受该证明，那么统计计算的结果在验证者的分布上是有效的——即使该算法是使用来自不同分布的样本执行的。

###### 定义1（pvCSV，非正式）

*公开可验证统计有效性证书*是一种非交互式证明系统，其中拥有分布$\mathcal{D}_P$的证明者$P$发布一个假设$h$以及对应的证书$\pi$。任何拥有分布$\mathcal{D}_V$的验证者$V$都可以读取这对信息$(h,\pi)$并决定接受或拒绝，其中以下保证以高概率成立。

- • **完备性**：如果$\mathcal{D}_P = \mathcal{D}_V$，则存在一个诚实的证明者对$(h,\pi)$使得$h$对$\mathcal{D}_V$有效且$V$接受。
- • **通用可靠性**：对于任何拥有分布$\mathcal{D}_V$的验证者$V$，对于任何（可能作弊的）证明者对$(\tilde{h},\tilde{\pi})$，如果$V$接受，那么$\tilde{h}$实际上对$\mathcal{D}_V$有效。

理解pvCSV保证的一种方式是将其视为一种鲁棒的统计有效性证明，而*无需对分布偏移做显式假设*。它不是假设证明者和验证者分布之间存在某种已知关系，而是验证过程适用于任何$\mathcal{D}_P$和$\mathcal{D}_V$，并且只有当发布的证书——源于使用证明者分布执行学习算法$\mathcal{A}$——反映了验证者分布上某种合法执行时，才会导致接受。虽然我们的完备性概念假设$\mathcal{D}_P = \mathcal{D}_V$，但其保证比这种等式所暗示的更微妙。分布$\mathcal{D}_P$和$\mathcal{D}_V$在组成上可能显著不同，但如果验证者接受，那么（根据通用可靠性）假设$h$对$\mathcal{D}_V$是有效的（因为根据$\mathcal{A}$的某种调用，这些分布是不可区分的）。

细心的读者会注意到，这个“通用可靠性”条件实际上是由学习委托的标准可靠性所蕴涵的，222使用$\mathcal{D}_P$的诚实证明者相对于持有$\mathcal{D}_V$的验证者可能被视为一个作弊证明者。但在非交互式证明的背景下具有新的意义。我们对可靠性的观点，加上非交互式证明系统，使得我们能够实现任何用户都可以公开验证的学习证书。

我们可以使用各种复杂度度量来评估pvCSV构造的质量。我们的工作主要关注样本复杂度：我们旨在使pvCSV中验证者从$\mathcal{D}_V$所需的样本数量比学习（或证明）所需的样本数量显著减少。此外，我们还可以跟踪其他度量，如时间复杂度（验证者和诚实验证者的）以及证明长度。我们在第3节（https://arxiv.org/html/2607.15528#S3）中正式定义pvCSV，并深入讨论该概念及其性质（如有效性和通用可靠性）。有了这个关键定义，本工作的主要技术贡献是在SQ学习框架内为自适应统计算法构造pvCSV。我们的pvCSV在SQ验证与SQ学习之间实现了样本复杂度的*指数级*差距。虽然每个构造的核心思想相似，但最终协议根据原始SQ算法的性质在重要方面有所不同。我们将展示，算法使用随机性的方式以及SQ预言机的允许方式