Interactive proofs make model evaluation faster with less data
Interactive Proofs of Proximity for Model Evaluation
Computational Complexity
Summary
Evaluating machine learning models usually needs a lot of data and computing power. The authors study a method where a small verifier checks a model’s behavior by interacting with a model owner who has more resources, but might not be trusted. Their approach lets the verifier check important properties of the model using much fewer data samples and queries, even when the verifier and prover see the data or evaluate the model differently. This speeds up audits of things like fairness, accuracy, and robustness of models.
What this means in practice
- •For machine learning audit teams: Efficiently certify model accuracy and fairness using fewer samples and limited computational checks.
- •For data integrity teams: Validate average-case robustness and harmlessness of deployed models under unknown input distributions with minimal data access.
A theory result. No direct application yet.
Authors
Geoffroy Couteau, Nikolas Melissaris, Tamara Paris
Abstract
We study interactive proofs of proximity (IPPs) for model evaluation, where a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation separates sampling the input distribution from querying the model and evaluating its output; distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and allows the prover and verifier to use different evaluators. We focus on doubly-sublinear IPPs, where both the verifier and honest prover use sublinear resources, and on (weighted) Hamming weight properties. For ordinary Hamming weight, we give a tolerant doubly-sublinear IPP. For completeness and soundness radii $\varepsilon_c<\varepsilon_f$ and gap $g=\varepsilon_f-\varepsilon_c$, a logarithmic-round instantiation uses $\widetilde{O}(1/g)$ verifier queries and $O(1/g^2)$ honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum (ITCS 2025). We prove matching query lower bounds up to polylogarithmic factors. For distribution-weighted Hamming weight, black-box sampling requires $Θ(1/g^2)$ verifier samples but only $\widetilde{O}(1/g)$ evaluations; the quadratic sample complexity is necessary in the interior regime. With chosen-randomness access, the problem reduces to ordinary Hamming weight, yielding $\widetilde{O}(1/g)$ calls and evaluations. If the parties' evaluators disagree arbitrarily on a $ρ$-fraction of the distribution and by at most $γ$ elsewhere, our protocols remain doubly sublinear whenever $g>2κ$, where $κ=ρ+(1-ρ)γ$. Applications include auditing accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.