Interactive Proofs for Verifying Machine Learning
summary
Defines PAC verification (verifier with sample access plus an interactive prover) and gives concrete separations: realizable thresholds admit order 1/ε verification versus learning needs order d/ε (VC dimension d), and there exist classes where verification uses order sqrt(d) random samples while learning needs order d. Builds interactive protocols using certificates for thresholds, distribution-testing ideas, and a combination of Goldreich‑Levin and Kushilevitz‑Mansour with hidden sample checks. Shows a qualitative gap: a t-sparse Fourier class is agnostically hard under the LPN assumption yet verifiable with efficient prover and verifier.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 4:30Example
- 8:05Pac verification
- 10:47Realizable case
- 13:29Agnostic case
- 15:31Class of hypothesis
- 19:26Soundness completeness
- 20:37First result
- 22:29Second result
- 23:23caveats
- 25:10qualitative separation
- 27:49twosplice functions
- 29:24the crucial laboratory algorithm
- 32:30the golden 11 algorithm
- 34:13the solution
- 38:30summary
- 40:45future work
related talks
41mTheory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives
19mVelvet: A Multi-Modal Verifier for Effectful Programs
01h 08mLean: Machine-Checked Mathematics and Verified Programming, Past and Future
26mWeaver: Shrinking the Generation-Verification Gap with Weak Verifiers
20mIncremental Verification of Neural Networks
22mScalable Zero-Knowledge Protocols From Vector-OLE
22mQuantum space, ground space traversal, and how to embed multi-prover...
14mToward Provably Private Insights into AI Use