Metraipolis › archive › dc_3885ca3d0afd

Interactive Proofs of Proximity for Model Evaluation — arXiv:2609.32007

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.32007
License (as archived)
CC0-1.0
Archived
2026-10-08T00:43:18.817Z
SHA-256 of the archived text
0515b78248513fad4a19f6a0e5cbfab067112f6b0afcd8274a1f0f0a4e364d87
Stable URL of this page
https://metraipolis.com/documento/dc_3885ca3d0afd

How to cite

Interactive Proofs of Proximity for Model Evaluation — arXiv:2609.32007 — arXiv (en), https://arxiv.org/abs/2609.32007 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3885ca3d0afd (Metraipolis archive dc_3885ca3d0afd, sha256 0515b78248513fad4a19f6a0e5cbfab067112f6b0afcd8274a1f0f0a4e364d87)
BibTeX
@misc{dc3885ca3d0afd,
  title = {Interactive Proofs of Proximity for Model Evaluation — arXiv:2609.32007},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32007},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3885ca3d0afd; sha256 0515b78248513fad4a19f6a0e5cbfab067112f6b0afcd8274a1f0f0a4e364d87},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.32007. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Theta(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 $\rho$-fraction of the distribution and by at most $\gamma$ elsewhere, our protocols remain doubly sublinear whenever $g>2\kappa$, where $\kappa=\rho+(1-\rho)\gamma$. Applications include auditing accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.32007 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T00:17:42.539Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).