# PAC Verification of Statistical Algorithms

arXiv: https://arxiv.org/abs/2211.17096 · HTML: https://mlsanity.com/paper/2211.17096/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 40 references that are in the map.
- First posted on arXiv 28 Nov 2022.

## Builds on (most cited first, 7 of 7)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Towards Verified Artificial Intelligence](https://mlsanity.com/paper/1606.08514/) (2016)
- [Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery](https://mlsanity.com/paper/1410.1228/) (2014)
- [Preventing False Discovery in Interactive Data Analysis is Hard](https://mlsanity.com/paper/1408.1655/) (2014)
- [Learning to Give Checkable Answers with Prover-Verifier Games](https://mlsanity.com/paper/2108.12099/) (2021)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)

## Built on by (most cited first, 8 of 8)

- [Prover-Verifier Games improve legibility of LLM outputs](https://mlsanity.com/paper/2407.13692/) (2024)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [Active Fourier Auditor for Estimating Distributional Properties of ML Models](https://mlsanity.com/paper/2410.08111/) (2024)
- [StatWhy: Formal Verification Tool for Statistical Hypothesis Testing Programs](https://mlsanity.com/paper/2405.17492/) (2024)
- [Protocols for Verifying Smooth Strategies in Bandits and Games](https://mlsanity.com/paper/2507.10567/) (2025)
- [The Fair Game: Auditing & Debiasing AI Algorithms Over Time](https://mlsanity.com/paper/2508.06443/) (2025)
- [Publicly-Verifiable Certificates for Statistical Algorithms](https://mlsanity.com/paper/2607.15528/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

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 Omegaleft(√d/varepsilon2right) 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 ℝ 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.