# On the Power of Interactive Proofs for Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 31 references that are in the map.
- First posted on arXiv 11 Apr 2024.

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

- [Junta correlation is testable](https://mlsanity.com/paper/1904.04216/) (2019)

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

- [Protocols for Verifying Smooth Strategies in Bandits and Games](https://mlsanity.com/paper/2507.10567/) (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)

We continue the study of doubly-efficient proof systems for verifying agnostic PAC learning, for which we obtain the following results. - We construct an interactive protocol for learning the t largest Fourier characters of a given function f colon 0,1n → 0,1 up to an arbitrarily small error, wherein the verifier uses mathsfpoly(t) random examples. This improves upon the Interactive Goldreich-Levin protocol of Goldwasser, Rothblum, Shafer, and Yehudayoff (ITCS 2021) whose sample complexity is mathsfpoly(t,n). - For agnostically learning the class mathsfAC0[2] under the uniform distribution, we build on the work of Carmosino, Impagliazzo, Kabanets, and Kolokolova (APPROX/RANDOM 2017) and design an interactive protocol, where given a function f colon 0,1n → 0,1, the verifier learns the closest hypothesis up to mathsfpolylog(n) multiplicative factor, using quasi-polynomially many random examples. In contrast, this class has been notoriously resistant even for constructing realisable learners (without a prover) using random examples. - For agnostically learning k-juntas under the uniform distribution, we obtain an interactive protocol, where the verifier uses O(2k) random examples to a given function f colon 0,1n → 0,1. Crucially, the sample complexity of the verifier is independent of n. We also show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial. Specifically, we show a protocol for an arbitrary class C of Boolean functions in the distribution-free setting, where the verifier uses O(1) labeled examples to learn f.