# Publicly-Verifiable Certificates for Statistical Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 45 references that are in the map.
- First posted on arXiv 17 Jul 2026.

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

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [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)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [A bounded-noise mechanism for differential privacy](https://mlsanity.com/paper/2012.03817/) (2020)
- [Subsampling Suffices for Adaptive Data Analysis](https://mlsanity.com/paper/2302.08661/) (2023)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [On the Power of Interactive Proofs for Learning](https://mlsanity.com/paper/2404.08158/) (2024)
- [How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions](https://mlsanity.com/paper/2409.06594/) (2024)
- [Efficient Public Verification of Private ML via Regularization](https://mlsanity.com/paper/2512.04008/) (2025)

## Abstract (arXiv)

Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis h and corresponding certificate π; then, any user, who holds a user-specific distribution, can read the pair (h,π) and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes k adaptive queries, we construct pvCSVs where the sample complexity scales with O(log k), whereas the sample complexity of the best learning algorithms scale with tildeO(√k). More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.