Research map / Learning theory and algorithms / Prediction and decision losses
Efficiently Verifiable Proofs of Data Attribution
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an interactive two-message PAC-verification protocol that lets a resource-constrained Verifier check that a Prover's data attributions are near-MSE-optimal, using O(1/ε²) model retrainings independent of dataset size.
Problem
Resource-constrained third parties cannot cheaply verify whether data attributions (e.g., empirical influence / datamodels) computed by a powerful, possibly malicious Prover are accurate, which matters for applications like data pricing.
Approach
Combine residual estimation of the optimal linear-predictor error (via noise stability and Fourier weights on the p-biased cube) with a spot-checking interaction in which the Prover retrains challenge subsets and the Verifier re-trains a small random subset to detect cheating; the residual estimator is shown robust to O(1/ε) corruptions.
Key results
- Verifier workload of the interactive protocol is O(log(1/δ)/ε²) model retrainings, independent of dataset size N, versus O(1/ε³) for the non-interactive residual-estimation protocol.
- Residual estimation is shown robust to m = O(1/ε) adversarially corrupted function evaluations, with error Õ(b²ε) under ρ = Θ(√ε).
- The protocol uses only two messages between Verifier and Prover and is a (ε,δ)-PAC verifier for empirical influence attributions.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use interactive spot-checking to delegate residual-estimation evaluations to the Prover | Non-interactive data-attribution verification · PAC verification for data attribution | Verifier cost (model trainings): O(1/ε^3 · polylog(1/δ)) -> O(log(1/δ)/ε^2) | Helped |
| Use residual estimation to estimate the optimal linear-predictor residual without computing the predictor | Non-interactive data-attribution verification · Linear datamodel residual estimation | sample complexity: O(1/ε^3) | Mixed |
Limitations
- Purely theoretical; no experiments on real models are reported in the provided text.
- Equivalence checking of nondeterministic training runs is assumed and not fully specified.
- Honest prover may only estimate attributions, so completeness can fail if ε is set too small.
Experimental setup
Metrics: mean squared error suboptimality err gap verifier retraining count
Baselines: Datamodels Empirical Influence naive MSE-checking verifier non-interactive residual-estimation protocol
Builds on: Datamodels Empirical Influence PAC-verification residual estimation (noise stability)
Closest papers by meaning
- Intriguing Properties of Data Attribution on Diffusion Models (ICLR 2024 · similarity 0.85)
- Taming Hyperparameter Sensitivity in Data Attribution: Practical Selection Without Costly Retraining (NeurIPS 2025 · similarity 0.85)
- How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions (ICLR 2025 · similarity 0.84)
- Provably Better Explanations with Optimized Aggregation of Feature Attributions (ICML 2024 · similarity 0.84)
- It's My Data Too: Private ML for Datasets with Multi-User Training Examples (ICML 2025 · similarity 0.84)
- $\texttt{dattri}$: A Library for Efficient Data Attribution (NeurIPS 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.