Efficiently Verifiable Proofs of Data Attribution

This paper introduces a novel interactive protocol that allows computationally limited verifiers to efficiently verify whether training data attribution vectors computed by a powerful prover are approximately optimal. The verification is grounded in a PAC framework, aiming to estimate the gap between the candidate attribution and the best possible attribution (in terms of MSE). The key technical contributions include a transformation of a previously known residual estimation algorithm into a two-message interactive protocol with spot-checking, reducing verifier cost from $O(1/\varepsilon^3)$ to $O(1/\varepsilon^2)$.

The paper addresses the challenge of verifying data attributions in machine learning models, particularly in scenarios where a computationally powerful entity (the Prover) provides attributions to a resource-constrained party (the Verifier). The authors propose an interactive verification protocol to ensure that the attributions are "good" (i.e., close to optimal) without requiring the Verifier to perform the computationally expensive task of computing the attributions themselves.

Suppose that we train an ML model on an $N$ size dataset, and we would like to know how much each data element (or subset of elements) influenced the training. This is modeled by a function $f \colon \\{-1,1\\}^N \rightarrow \mathbb{R}$, where each $x \in \\{-1,1\\}^N$ encodes a subset ($x_i = 1$ iff the $j$’th element is included in the subset), and this function can be estimated for every $x$ by retraining the model on the subset $x$ and then computing the prediction quality or test error of the new model. The problem is that computing this function is very expensive (each subset requires a fresh training), and we would like to compute an approximation of $f$, hopefully using only a few retrainings. The work of Saunshi et al. (2022) showed how to compute a linear model $a$ such that $f(x) \approx <a,x>$, where the number of retrainings to obtain $a$ is only $\approx 1/\epsilon^3$, which is independent of $N$ ($\epsilon$ is the required accuracy measured by the MSE distance from the optimal linear model). This is done using Residual Estimation.

This paper considered a model where we have two entities: a prover, which has more computational resources, and the verifier, which is more restrictive but still would like to get the estimation of $f$. The problem arises when the prover is not necessarily honest, so the verifier must have a way to check whether the linear model $a$ produced by the prover is indeed close to optimal. The main result of this paper is to provide a 2-message interactive protocol between the prover and the verifier, where the verifier, using only $\approx 1/\epsilon^2$ retrainings (and not $\approx 1/\epsilon^3$ as in the non-interactive version of Saunshi et al. (2022)), can catch an unhonest prover with high probability. The solution relies on the same Residual Estimation of Saunshi et al. (2022): The verifier asks the prover to perform the $1/\epsilon^3$ retrainings, but checks only $\epsilon$ fraction of them by doing the retrainings itself (where the exact $\epsilon$ fraction is unknown to the prover). If the prover lied in more than $1/\epsilon$ out of the $1/\epsilon^3$ requests, the verifier will catch it with high probability. Otherwise, there could be at most $1/\epsilon$ wrong values, so the main technical contribution of this paper is to prove that the approach of Saunshi et al. (2022) is error-robust against such an amount of errors.

This paper studies the "verifiable" problem for data attribution, an important growing field in data-centric AI. Specifically, the paper defines the verifying problem in data attribution and proposes an "efficient" interactive protocol that is PAC-verifiable.

This paper proposes a technical solution to the trust problem centered around data attribution vectors computed from datamodels. In this context, datamodels refer to mappings that quantify the relationship between subsets of a training dataset and the resulting performance of a model trained on those subsets. For example, given a fixed training set of size $N$, we can define a mapping $f: \\{\pm 1\\}^N \to [0,1]$, where the selection vector $x \in \\{\pm 1\\}^N$ indicates which data points are included in the subset and $f(x)$ gives the final 0/1 loss of the classifier trained on that subset.

Current approaches compute data attribution vectors from datamodels. They are defined as the linear coefficients $a \in \mathbb{R}^N$ of the optimal linear approximation to $f$ with respect to an inner product. For simplicity, we work in the inner product space induced by the uniform distribution over $\\{\pm 1\\}^N$. The analysis extends essentially unchanged to the case of i.i.d. products of $p$-Bernoulli distributions. These vectors have important practical applications, such as data pricing, allowing one to compensate individual data points within a training set according to their “influence” on the final performance of the model.

Evaluating the datamodel $f$ on each training subset $x$ is extremely expensive, and therefore computing honest data attribution vectors creates significant asymmetry and trust issues. Only a few parties have the resources to perform these computations, while most others must rely on, and therefore trust, this small group of powerful actors. The paper addresses this asymmetry by introducing an interactive protocol in which the Verifier can check the optimality of the Prover’s data attribution vector with much less computational cost. Here, the Verifier’s computational cost, defined to be the number of datamodel evaluations, is shown to be independent of the dataset size $N$.

A key technical insight comes from previous work by Saunshi et al., who observed that computing certain Fourier coefficients of the residual $g(x) = f(x) - \langle a, x\rangle$, given $a$ is much cheaper than computing the attribution vector from scratch. The novelty of this paper lies in formulating the trust problem as a PAC verification task and offloading the computation of the residual’s Fourier coefficients to the Prover. With the spectral computation pushed to the Prover, the Verifier only needs to perform random spot checks on the Prover’s results to verify their validity. The offloading reduces the Verifier’s computational cost from $1/\epsilon^3$ to $1/\epsilon^2$ (ignoring other parameters of the interaction), where $\epsilon$ denotes the (additive) suboptimality of the Prover’s candidate attribution vector relative to the optimal one.

Estimating data subset influence on an ML model is computationally expensive due to repeated retraining. Building on Saunshi et al. (2022), who proposed an efficient linear approximation, this work introduces an interactive protocol where a weak verifier outsources this task to a powerful but untrusted prover. The verifier spot-checks a small fraction of the prover's computations. The paper's main technical contribution is proving that the approximation method is robust against a small number of errors, which allows the verifier to efficiently detect a dishonest prover. All reviewers are supportive, and the paper would make a great addition to NeurIPS.