Publicly-Verifiable Certificates for Statistical Algorithms

2026-07-17 · Michael Ngo, Michael P. Kim 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 $\tilde{O}(\sqrt{k})$. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.

📄 PDF Abstract BibTeX arXiv:2607.15528

Code (0)

등록된 구현이 없습니다.

SIEVE: Towards Verifiable Certification for Code-datasets

2025-10-02 · Fatou Ndiaye Mbodji, El-hacen Diallo, Jordan Samhi, Kui Liu 외 arxiv

Code agents and empirical software engineering rely on public code datasets, yet these datasets lack verifiable quality guarantees. Static 'dataset cards' inform, but they are neither auditable nor do they offer statisti…

KAYROS: An Anytime and Exact Open-Source Solver for Duration-Minimization Time-Dependent Vehicle Routing. A Technical Report and a Case Study in Human-AI Engineering

2026-07-25 · Florian Rascoussier arxiv

KAYROS is an open-source solver for duration-minimization time-dependent vehicle routing problems, with or without time windows (TDVRPTW, TDVRP). In these variants, travel times change with departure time, and each route…

Sparse PCA: Algorithms, Adversarial Perturbations and Certificates

2020-11-12 · Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer

We study efficient algorithms for Sparse PCA in standard statistical models (spiked covariance in its Wishart form). Our goal is to achieve optimal recovery guarantees while being resilient to small perturbations. Despit…

Policy Certificates: Towards Accountable Reinforcement Learning

2018-11-07 · Christoph Dann, Lihong Li, Wei Wei, Emma Brunskill

The performance of a reinforcement learning algorithm can vary drastically during learning because of exploration. Existing algorithms provide little information about the quality of their current policy before executing…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

End-to-End Verifiable Decentralized Federated Learning

2024-04-19 · Chaehyeon Lee, Jonathan Heiss, Stefan Tai, James Won-Ki Hong

Verifiable decentralized federated learning (FL) systems combining blockchains and zero-knowledge proofs (ZKP) make the computational integrity of local learning and global aggregation verifiable across workers. However,…

Federated Learning