Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution
Authors: Ian Connick Covert
Chanwoo Kim
Su-In Lee
James Zou
Tatsunori Hashimoto
Venue: NeurIPS 2024 poster (2024)
Keywords: Amortization
feature attribution
data valuation
stochastic optimization
Primary area: interpretability_and_explainability
TL;DR: We accelerate feature and data attribution by training amortized models with noisy supervision

Abstract: Many tasks in explainable machine learning, such as data valuation and feature attribution, perform expensive computation for each data point and are intractable for large datasets. These methods require efficient approximations, and although amortizing the process by learning a network to directly predict the desired output is a promising solution, training such models with exact labels is often infeasible. We therefore explore training amortized models with noisy labels, and we find that this is inexpensive and surprisingly effective. Through theoretical analysis of the label noise and experiments with various models and datasets, we show that this approach tolerates high noise levels and significantly accelerates several feature attribution and data valuation methods, often yielding an order of magnitude speedup over existing approaches.

Stochastic Amortization: A Unified Approach to Accelerate Feature and Data Attribution
Ian Covert" Stanford University icovert@stanfore ord. edu
Chanwoo Kim University of Washington chanwkimOus edu
Su-In Leef University of Washington suinleeduw. edu
James Zou' Stanford University jameszsstanf ood.nfordeeee edu
Tatsunori Hashimoto Stanford University thashim@stanf ord edu
Abstract
Many tasks in explainable machine learning, such data valuation and feature attribution, perform expensive computation for each data point and are intractable for large datasets. These methods require efficient approximations, and although amortizing the process by learning a network to directly predict the desired output is promising solution, training such models with exact labels often infeasible. We therefore explore training amortized models with noisy labels, and we find that this is inexpensive and surprisingly effective. Through theoretical analysis of the label noise and experiments with various models and datasets, we show that this approach tolerates high noise levels and significantly accelerates several feature attribution and data valuation methods, often yielding an order of magnitude speedup over existing approaches.
1 Introduction
Many tasks in explainable machine learning (XML) perform some form of costly computation for every data point in dataset. For example, common tasks include assessing individual data points' impact on model's accuracy [33], or quantifying each input feature's influence on individual model predictions [68]. Many of these techniques are prohibitively expensive: in particular, those with game-theoretic formulations have exponential complexity in the number of features or data points, making their exact calculation intractable [89, 4].
Accelerating these methods is therefore topic of great practical importance. This has been addressed primarily with Monte Carlo approximations [96, 16, 74], which are faster than brute-force calculations but can be slow converge and impractical for large datasets. Alternatively, a promising idea is to amortize the computation, or to approximate each data point's output with a learned model, typically a deep neural network [2]. For example, in the feature attribution context, we can train an explainer model to predict Shapley values that describe how each feature affects a classifier's prediction [50].
There several reasons why amortization is appealing, particularly with neural networks: similar data points often have similar outputs, pretrained networks extract relevant features and can be efficiently fine-tuned, and if the combined training and inference time is low then amortization can be faster than computing the object of interest (e.g., data valuation scores) for the entire dataset. However, it is not obvious how to train such amortized models, because standard supervised learning requires a dataset of ground truth labels that can be intractable to generate. Our goal here is therefore explore efficiently training amortized models when exact labels are costly. Our main insight is that
"Equal contribution. 'Equal advising.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(1) Generate noisy labels
(2) Train network
(3) Predict outputs
(1) Run expensive approximation
Per-instance computation
Stochastic amortization
a(b,)
a(b))
bj
a()))
a(b,)
Bz
a(b²)
a(b; 8)
a(bg)
b2
a(b))
a(by)
a(by)
a(b2))
Figure 1: Diagram of stochastic amortization. Left: using a dataset with noisy labels ā(b) (e.g.. images and data valuation estimates), can train amortized model that accurately estimates the true outputs a(b) (c.g., data valuation scores). Right: the default approach of running an expensive approximation algorithm for each example (e.g., Monte Carlo estimator with many samples [33]).
amortization is surprisingly effective with noisy labels: train with inexpensive estimates of the true labels, and we find that this is theoretically justified when the estimates are unbiased.
We refer to this approach stochastic amortization (Figure 1), and we find that it is applicable to a variety of XML tasks. In particular, we show that effective for feature attribution with Shapley values [68], Banzhaf values [11] and LIME [83]; for several formulations of data valuation [33, 35, 60, 103]; and to data attribution with datamodels [47]. Our experiments demonstrate significant speedups for several of these tasks: we find that amortizing across entire dataset with noisy labels is often more efficient than current per-ex per-example approximations, especially for large datasets, and that amortized feature and data attribution models generalize well to unseen examples.
Our contributions in this work are the following:
We present the idea of stochastic amortization, training amortized models with noisy labels. We analyze the role of noise from the label generation process and show theoretically that it is sufficient to use unbiased estimates of the ground truth labels (Section 3). We find that non-zero bias in the labels leads to learning an incorrect function, but that variance in the labels plays more benign role of slowing optimization.
We identify a range of applications for stochastic amortization in XML. Our theory only requires unbiased estimation of the task's true labels, and we find that such estimators exist for several feature attribution and data valuation methods (Section 4).
Experimentally, test multiple estimators for Shapley value feature attributions and find that amortization works when the labels are unbiased (Section 5). We also verify that amortization is effecttve for Banzhaf values and LIME. For data valuation, we apply amortization to Data Shapley and show that it allows us to scale this approach to larger datasets than in previous works.
Throughout our experiments, we also analyze the scaling behavior with respect to the amount of training data and the quality of the noisy labels. general, we find that amortization is more efficient than per-example computation when the training set used for amortization contains at least a moderate number data points (e.g., > 1K for data valuation).
Overall, our work shows the potential for accelerating many computationally intensive XML tasks with the same simple approach: amortizing with noisy, unbiased labels.
Background
We first introduce the basic idea of amortization ML, which we discuss a general setting before considering any specific XML tasks. Consider scenario where we repeat similar computation for a large number of data points. We represent this general setup with a context variable b and per-context output a(b) E A. For example, these can be an image and its data valuation score, or an image and its feature attributions. Amortization can used with arbitrary domains, but we assume Euclidean spaces, A C m and B C IRd, because many XML tasks involve real-valuce outputs.

---

The computation performed for each context b E B can be arbitrary as well. In some cases a6b) an intractable expectation, in which case we would typically approximate it with a Monte Carlo estimator [96, 33]. In other situations it is the solution to an optimization problem [91, 2}, in which case we can define a(b) via a parametric objective h A x B +> R:
a ((b) = arg min h(al; b).
d'EA
We do not require a specific formulation for a(b) in this work. but we will see that both the expectation and optimization setups provide useful perspectives on our proposal of training with noisy labels.
In situations with repeated computation, our two options are generally to (i) perform the computation separately for each b B, (ii) amortize the computation by predicting the output with learned model. We typically implement the latter with a neural network a(;; 8), and our goal is to train such that a(b; 0) xz a(b). In training these models, the main challenge occurs when the per-instance computation is costly: specifically, it is not obvious how to train a(b; 0) without a dataset of ground truth solutions a(b), which can be too slow to generate for many XML methods [68, 33]. We address this challenge in Section 3, where we prove that amortization tolerates training with noisy labels.
2.1 Related work
The general idea of amortized computation captures many tasks arising in physies, engineering,
control and ML [2]. For example, amortization is prominent in variational inference [56, 82], meta learning [38, 29, 80] and reinforcement learning [45, 64, 39]. In the XML context, many recent works have explored amortization to accelerate costly per-datapoint calculations [12, 108, 49, 50, 18, 19]. Some of these works are reviewed by [13], and we offer a detailed overview in Appendix A.
For feature attributions, two works propose predicting Shapley values by training with a custom weighted least squares loss [50, 18]; our simpler approach can use any unbiased estimator and resembles a standard regression task. Two other works suggest modeling feature attributions with supervised learning [87, 14]; these recommend training with exact high-quality labels, whereas we recognize the potential to use noisy labels that can be generated orders of magnitude faster. Concurrently. Zhang et al. [1 [1] proposed training with custom estimator for Shapley value feature attributions: our work is similar but derives stochastic amortization algorithms for a range of settings, including the use of any unbiased estimator (Section 3) and usage for various XML tasks including data valuation (Section 4).
For data valuation, two works consider predicting data valuation scores with supervised learning [35, 36], but these also use near-exact labels that limit the applicability to large datasets. Concurrently, Li and Yu [65] propose a family of data valuation estimators and learning- -baen approach analogous to [50] but for data valuation; our approach uses a simpler training loss that works with any unbiased estimator, and unlike [65] its memory usage does not scale with the dataset size. Separately, another line of work focuses on accelerating the model retraining step underlying most data valuation methods [57, 104, 107], and these are complementary our approach. Finally, while there works that accelerate data attribution with datamodels [78, 27], we are not aware of any that use amortization."
More broadly, our proposal to train amortized models with noisy labels can be viewed as version of stochastic optimization, or training with noisy gradients. This fundamental idea is widely used in machine learning [5], but to our knowledge we are the first to study the broad applicability of noisy labels for accelerating diverse XML tasks.
3 Stochastic Amortization
We now discuss how to efficiently train amortized models with noisy labels. Following Section 2, we present this as a general approach before focusing on a specific XML task. One natural idea is to treat amortization like standard supervised learning problem: we parameterize model a(; 8), adopt a distribution p(b) over the context variable, and then train our model with the following objective,
Creg (8) [la 6) a(b)
'atamodees [47] performs data attribution by fitting linear regression model, but this is not amortization because the model cannot predict attributions for new data points (see Appendix B).
3

---

This approach is called regression- regression-based amortization [2] because it reduces the problem to simple regression task. The challenge is that this approach cannot be used when we lack a large dataset of exact labels a(b), which is common for computationally intensive XML methods (Section 4).
A relaxation of this idea is to train the model with inexact labels (see Figure 1). We assume that these are generated by noisy oracle ä(b), which is characterized by a distribution of outputs for each context b E B. For example, the noisy oracle could be a statistical estimator of a data valuation score [33]. With this, we can train the model using a modified version of Eq. (2), where we consider the loss in expectation over both p(b) and the noisy labels ā(b):
Ereg (8) E [aa 8) a(b)
is not immediately obvious when this approach is worthwhile: if the noisy oracle is too inaccurate we will learn the wrong function, it is important to choose the oracle carefully. We find that there are two properties of the oracle that matter, and these relate to its systematic error and noise level, or more intuitively its bias and variance. We denote these quantities as follows for a specific value b,
B b) = ||a(b) B[ā(b) b]]?
N(a b) E [|ā(b) - E(ā(b) 611 16]
and based on these we can also define the global measures B(a) = E Ba 6)] and N(ā) = E, [N b)] for the distribution over context variables p(b). These terms are useful because they reveal a relationship between the two amortization objectives. In general, the objectives are related
by the following two-sided bound (see proof in Appendix D):
N(ā) - (os(a)-V((a)) < Creg(()) (0) S (V N(ā) + /B(ā)
This relationship shows that reducing Greg(( (0) towards its minimum value N(ā) is similar training with Lreg(0 (0). only with a disconnect introduced by the bias B(ā). The bias represents a source of irreducible error, because in the limit Creg (0) N(@) + 0 we have Lreg = B(ā). On the other hand, when B(ā) 0 we can see that Lreg (0) Ergg (0) N(ã), which means that training with the noisy loss is equivalent and will recover the correct function asymptotically. This last equality is easy to see given an unbiased noisy oracle ā(b). but the more general relationship in Eq. (4) emphasizes how non-zero bias can be problematic and lead to learning an incorrect function.
Aside from the bias, the variance plays role as well, not in determining the function we learn but in making the model's s optimization unstable or require more noisy labels. To illustrate the role of variance, we present theoretical result considering the simplest case of a linear model a(b; f) trained with SGD, which shows that high label noise slows convergence (see proof in Appendix D).
Theorem 1. Consider a noisy oracle à(b) that satisfies E(ā(b) bj = Ôb with parameters ē E RRmx such that |00|e < D. Given distribution p(b), define the norm-weighted distribution q(b) x p(b) . [bb12 and the terms Ep = [bb and Egg = F.g Ebybbb]] [bbT]. If we train a linear model a(f; b) = Ab with the noisy objective (o) using SGD with step size n
a(t+1)' then the averaged iterate
2
or = - TTT O2 at step T satisfies
BICreg N(a)) < 4TH(Ep)) (N) + 4Amax Baaaxx(E) (2)) Amin (Tp) + 1)
where Na(a) = N, b)] is the noisy oracle's 's norm-weighted variance, and Amase (-), Amin(-) are the maximum and minimum eigenvalues.
The bound in Theorem 1 shows that noise slows convergence by its presence in the numerator, and interestingly, it appears in the form of a weighted version N₂(ā) that puts more weight on values with large norm ||b]| this is a consequence of assuming a linear model, but we expect the general conclusion of label variance slowing convergence to hold even for neural networks. As a corollary, we can see that the rate in Theorem applies directly to Lreg(0) (0) when the noisy oracle is unbiased (see Appendix D). We note that very high noise levels can in principle prevent effective optimization, and this can be mitigated by either reducing the noisy oracle's variance or taking more steps T.
NN (ā 6) is equal to the trace of the conditional covariance Cov(ā b). and N(@) Tr(BoCovv 6)]).

---

Overall, our analysis shows that amortization with noisy labels is possible, although perhaps more difficult to optimize than training with exact labels. We next show that unbiased estimates are available for many XMI. tasks (Section 4), and we later find that this form of amortization is consistently effective with the noise levels observed in practice (Section 5), even providing better accuracy than per-example estimation in compute-matched comparisons. As shorthand, we refer to training with the noisy objective (0) in Eq. (3) stochastic amortization.
4 Applications to Explainable MI
We now consider XML tasks that can be accelerated with stochastic amortization. Rather than using generic variables b E B and a(b) E A, this section uses an input variable I E X' a response variable y E y, and model f or a measure of its performance. As we describe below, each application of stochastic amortization is instantiated by noisy oracle that generates labels for the given task.
4.1 Shapley value feature attribution
One of the most common tasks in XML is feature attribution, which aims to quantify each feature's s influence on an individual prediction. The Shapley value has gained popularity because of its origins in game theory [89, 68], and like many feature attribution methods is based on querying the model while removing different feature sets [17]. Given a model f and input æ that consists of d separate features x (#1...... za), we assume that we calculate the prediction (*s) E R for any feature set S S [d]. With this setup. the Shapley values (x(x) E R for each feature E [d] are defined as:
1 (x))) = d SE(AN()
Σ d (1=1) (f(#su()) -f
These scores satisfy several desirable properties [89], but they impractical calculate due to the exponential summation over feature subsets. Our goal is therefore to learn an amortized model (xx;0) E Rd to directly predict feature attribution scores, and for this we require noisy oracle.
Many recent works have studied efficient Shapley value estimation [10], and we first consider noisy oracles derived from Eq. (5), which defines the attribution the feature's ' expected marginal contribution. There are several unbiased statistical estimators that rely on sampling feature subsets or permutations [6, 96, 77, 74, 58], and following Section 3 we can any of these for stochastic amortization. Our experiments use the classic permutation sampling estimator [96, 74], which approximates the values (x) definition of this noisy oracle to Appendix E, along with the other estimators used in our experiments.
expectation across feature orderings. We defer the precise
Next, we also consider noisy oracles derived from an optimization perspective on the Shapley value. famous result from Charnes et al. [7] shows that the Shapley values are the solution to the following problem (with abuse of notation we discard the solution's 's intercept term),
2
(xx) = arg min
Σ ((S) SC14
f(xs) - a0
Σ iEs
ai
1
aER4+1
where least squares weighting kernel defined as ,r 1S) (1)) (S]). Several works have proposed approximating Shapley values by solving this problem with sampled subsets, either using projected gradient descent [92] or analytic solutions [68, 16]. Among these, we use KemelSSHA [68] and SGD-Shapley [92] as noisy oracles our experiments. The first is an M- estimator whose bias shrinks as the number of sampled subsets grows [99], so we expect it to lead to effective amortization; the latter has been shown to have non-negligible bias [10], so our theory in Section 3 suggests that it should lead to learning an incorrect function when used for amortization.
4.2 Alternative feature attributions
Next, we consider alternative feature attribution methods: Banzhaf values [4, 11] and LIME [83]. These are closely related to Shapley values and are similarly intractable [26, 40], but we find that they offer statistical estimators that be used for stochastic amortization.
'There many ways do so [17]. e.g., can set features to their mean masked self-attention.
5

---

First, Banzhaf values assign the following scores to each feature for a prediction f(x) [4]:
(x(2) 2
Σ (f(asu())- f(zs))
SCINA
These differ from Shapley values only in their choice of weighting function, and they admit a range of similar statistical estimators. One option the MSR estimator from [103], which is unbiased and re-uses all model evaluations for each feature attribution estimate. We adopt this as a noisy oracle in our experiments (see a precise definition Appendix E), but several other options are available.
Second, LIME defines its attribution scores (x(x) as the solution to the following optimization problem, given weighting kernel (S) and penalty term 52 [83]:
arg min
f((ss) Σx(s) SCI4]
x(S)
ao Σ iES
+ +(aa).
(8)
agR4+1
As our noisy oracle for LIME, sampled according to क (S). Similar to KernelSHAP [68], J. this is an M-estimator whose bias shrinks zero the sample size grows [99]. so we expect it to lead successful amortization.
the popular approach of solving the above problem for subsets
Aside from these methods, other costly feature interpretation methods rely on unbiased statistical estimators and can be amortized in similar fashion [98, 62, 32]. We leave further investigation of these methods to future work.
4.3 Data valuation
Next, data valuation aims to quantify how much each training example affects a model's accuracy. We consider labeled examples = (I,, y) and a training dataset D { and we analyze each data point's value by fitting models to subsampled datasets Dr D with T S [r]] and calculating measure of the model's performance (Dr) E R (e.g.. its 0-1 accuracy). This general approach was introduced by Ghorbani and Zou [33], who defined the Data Shapley scores (2;) E IR as follows:
(2,))
Σ TEMME
n
IT') )T
(u(D)
-
Subsequent work generalized the approach in different ways, which we briefly summarize before considering amortization. For example, Wang and Jia [103] used the Banzhaf value rather than Shapley value, and Kwon and Zou [60] considered the case of arbitrary semivalues [75]. These
correspond to adopting a different weighting over subsets in Eq. (9), and the general case can be written follows for normalized weighting function w(k).
(<x,) = Σ
w([T)) (v(Dr (z+)) - v(Dr)).
(10)
TCNMM
Next, another extension is the case of distributional data valuation. Ghorbani et al. [35] incorporate an expectation over the original dataset D. which they show leads to well defined scores even for data points = (Ir y) outside the training set. Given distribution over datasets of size (D] a weighting function wkk), this version defines the score v²(2) R for arbitrary 2 as follows:
1 and
(2) ED Σ
-
(11)
TC(n-1)
When using any of these methods in practice, the scores are difficult to calculate due to the intractable expectation across datasets. However, a crucial property they share is that they can all be estimated in an unbiased fashion, and these estimates can therefore be used as noisy labels for stochastic amortization. We focus on Data Shapley and Distributional Data Shapley our experiments [33, 35), and we use the Monte Carlo estimator from Ghorbani and Zou [33] as a noisy oracle (see the precise
Following [17], we only consider the version of LIME with binary interpretable representation.
'For this to be valid expectation, semivalues require that n- ("x3) wokk = 1. Note that Data Shapley
adopts wkk) ("=1)= -1 /n and Data Banzhaf adopts w(k) 1/2n-1

---

definition in Appendix E). Doing allows us to train an amortized valuation model (2;2; 0) E IR that accelerates valuation within our training dataset, and that can also be applied to external data, e.g.. when selecting informative new data points for active learning [36].
Finally, Appendix B discusses amortization for the datamodels data attribution technique [47]. This method measures how much each training data point 2; E D affects the prediction for an inference example E X, and show that the scores are equivalent to simple expectation that can be estimated in an unbiased fashion. The datamodels scores can therefore be amortized by adopting these estimates as noisy labels, but we leave further investigation of this approach future work.
Experiments
Our experiments apply stochastic amortization to several of the tasks discussed in Section We consider both feature attribution and data valuation, for image and tabular datasets, and using multiple architectures for our amortized models, including fully-connected networks (FCNs), ResNets [43] and ViTs [24]. Full details are provided in Appendix F, including our exact models and hyperparameters.
Our goal in each experiment is perform feature attribution data valuation for entire dataset, and to compare the accuracy of stochastic amortization to running existing estimators on each point. We adopt noisy oracle for each task (e.g., Monte Carlo estimator of data valuation scores), we then fit an amortized network with one noisy label per training example, and our evaluation focuses on the accuracy of the amortized predictions relative the ground truth. Our ground truth is obtained by running the noisy oracle to near-convergenee for large number of samples: for example, we run KemelSHHA [68] for feature attribution with 1M samples. and the TMC estimator [33] for data valuation with 10K samples. We test amortization when using different numbers of training examples, and for both training and unseen external data evaluate the model's generalization. We find that amortization often denoises and strongly improves upon the noisy labels, leading to a significant accuracy improvement for the same computational budget.
5.1 Feature attribution
We first consider Shapley value feature attribu- tions. This task offers a diverse set of noisy oracles, and we consider three options: Ker- neISHAP [68], permutation sampling [74] and CGD-Shapley [92]. Among these, our theory from Section suggests that the first two will be effective for amortization, while the third may not because it is not an unbiased estimator. We follow the setup from [18] and implement our amortized network with a pretrained ViT-B architecture [24], and we use the ImageNette dataset [46] with 224 x 224 images partitioned into 196 patches of size 14 x 14.
Context
Noisy .ib]
Prediction a(b; 8)
Truth a(b)
Casselte player
Parachate
Church
As a first result, Figure compares our train- ing targets the amortized model's predictions. The predicted attributions are significantly more accurate than the labels, even for the noisiest setting with just 512 KernelSHAP samples. Fig- ure 3 (left) quantifies the improvement from amortization, and we observe similar results for both KernelSHAP and permutation sampling (see Appendix G): in both cases the error is sig- nificantly lower than that of the noisy labels, and it remains lower and improves as the labels become more accurate. To contextualize our amortized model's accuracy, we find that the error is similar to that of running KernelSHAP for 10-40K samples, even though our labels use an order of magnitude fewer samples (see Appendix G). We also find that the model generalizes to external data points (see Appendix G). In addition,
Golf ball
Figure 2: Stochastic amortization for Shapley value feature attributions. We compare the pre- dicted attributions to the noisy labels and ground truth, which are generated using KernelSHAP with 512 and 1M samples, respectively.
7

---

10
KernelSHAP
Error
Error
Amortized KomaiSHAP
Emor (Labo)
10
Error
10"
10"
1024
10
2048
512
1024
3072
2018
3072
KaMA
10"2
10
10"
19"
10
10
10
10"
10"
10"
10"
Error (Prediction)
FLOPs
# Training Datapolnts (Amortized)
Figure 3: Amortized Shapley value feature attributions using KernelSHAP as a noisy oracle. Left: squared error relative to the ground truth attributions when using noisy labels with different numbers of samples (different noise levels). Center: estimation error as a function of FLOPs, where KemneSSHA incurs FLOPPs via classifier predictions used to estimate the attributions, and amortization incurs additional FLOPs from training (training appears as a vertical line because the FLOPs are relatively low, and endpoints represent results from the final epoch). Right: estimation error with different training dataset sizes given equivalent compute per data point (matched by using fewer KernelSHAP samples when generating noisy labels for amortization and allowing up to 50 epochs of training).
show results for SGD-Shapley, where confirm that it leads to poor amortization results due to its non-negligible bias (see Appendix G).
Next, we investigate the compute trade-off between calculating attributions separately (e.g.. with KemnlSSHAP and using amortization. Figure 3 (center-right) shows two results regarding this tradeoff. First, measure the eπrоr as a function of FLOPs, where we account for the cost of generating labels and training the amortized model (see Appendix F). The FLOPs incurred by training are negligible compared to the KernelSHAP estimates, and we find that stopping at any time to fit an amortized model yields significantly better estimates. This suggests that amortization is an inexpensive final denoising step, regardless of how much compute used for the noisy estimates.
Second, we test the effectiveness of amortization for different dataset sizes. We match the compute between the two scenarios, using 2440 KemneISHAP samples for per-example computation" and 2257 for amortization to account for the cost of training. This compute-matched comparison shows that amortization achieves lower estimation error for datasets ranging from 250-10K data points (Figure 3 right); it becomes more effective as the dataset grows, but is useful even for small datasets.
Finally, Appendix G shows comparison between stochastic amortization and FastSHAP [50, 18]. an existing approach to amortized Shapley value estimation. We observe similar estimation accuracy in compute-matched comparisons, and find that both methods are significantly more accurate than per-example estimation (similar to Figure 3 center). Appendix G also show results for amortizing Banzhaf values and LIME: we find that amortization is more difficult for these methods due to the inconsistent scale of attributions between inputs, but we nonetheless observe an improvement in our amortized estimates versus the noisy labels.
5.2 Data valuation
Next, we consider data valuation with Data Shapley. For our noisy oracle, we obtain training labels by running the TMC estimator with different numbers of samples [33]. We first test approach with the adult census and MiniBooNE particle physics datasets [25, 84], and following prior work conduct experiments using versions of each dataset with different numbers of data points [53]. Our valuation model must predict scores for each example 2 = (x, y). so we train FCNs that output scores for all classes and use only the relevant output for each data point.
As a first result, Figure 4 (left-center) shows the estimation accuracy for the MiniBooNE dataset when using 1K and 10K data points. The noisy estimates converge we use more Monte Carlo samples, but we see that the amortized estimates are always more accurate in terms of both squared error and correlation with the ground truth. The improvement is largest for the noisiest estimates, where the amortized predictions have correlation >0.9 when using only 50 samples. Amortization
'This is the default number of samples for 196 features in the official repository: https: /tte:://tttti wiigghttb..oom com/ shap/shap.
8

---

MiniBooNE Error
MiniBooNE Correlation
Data Valuation Scaling
1.0
Planson Corrdation
Amertized (1000 Points)
0..
Correlatoo
10'
Amortized (10000 Points)
Amortized (1030 Points)
Error
Monte 11000 Pcints]
0.6
Points)
Monta Carlo (10000 Points)
Monte Carlo (1000 Points)
Monte Cario (10000 Points)
0.5
Amort aed (MindlooM!)
Amortzed (Adult)
10-1
Norte Cario (MiniBookE)
Norta Caroo (Adui))
1.00 # SSmpless//// / Point
1.5 Somples / Point
10a Datapoints
10'
Figure 4: Amortized data valuation accuracy for tabular datasets. Left: mean squared error relative to the ground truth for the MiniBooNE dataset, normalized so that the mean valuation score has error equal to 1 (for KK and 10K data points). The x-axis indicates how many Monte Carlo samples were used for each data point. Center: Pearson correlation with the ground truth for the MiniBooNE dataset (for IK and 10K data points). Right: estimation accuracy for the MiniBooNE and adult census datasets as function of dataset size (250 to 10K data points); we use 50 Monte Carlo samples per data point for all results and show the Pearson correlation with the ground truth.
CIFAR-10
CIFAR-10 Correlation
CITAR-10
2.0
Monte Carlo Amortized
0.9
Pearson Correlation
2.0
1.5
0.8
1.5
Monte Carto (Intemali
Amortized (intemati)
1.0
1.0
Ameriiced [Extemall
Monte
0.5
Amortized
0.5
35
10a
10 Datapoints
# SSamples/// / Point
Samples / Point
Figure 5: Distributional data valuation for CIFAR-10. Left: estimation error when using different numbers of samples for the noisy label estimates. Center: Pearson correlation with the ground truth for different numbers of noisy samples. Right: estimation error function of dataset size, where all results use Monte Carlo samples per data points; we compare the error for amortized estimates on internal (training) and external (unseen) data points, demonstrating strong generalization.
more beneficial for the 10K dataset, which suggests that training with more noisy labels can be a substitute for high-quality labels. Appendix G shows similar results with the adult census dataset.
Next, Figure 4 (right) considers the role of training dataset size for the estimates with 50 Monte Carlo samples. For both the adult census and MiniBooNE datasets, we see that the benefits of amortization are small with 250 data points but grow as we approach 10K data points. This number of samples is enough to maintain 0.9 correlation with the ground truth when using amortization, whereas the raw estimates become increasingly inaccurate. Stochastic amortization is therefore promising to scale data valuation beyond previous works, which typically focus on < IK data points [34, 60, 103].
5.3 Distributional data valuation
Finally, we consider Distributional Data Shapley [35], which is similar to the previous experiments but defines valuation scores even for points outside the training dataset; this allows us to test the generalization to unseen data. We use the CIFAR- 10 dataset [59], which contains 50K training examples, and for our valuation model we train a ResNet-18 that outputs scores for each class.
Similar to the previous experiments, Figure 5 (left-center) evaluates the estimation accuracy for different numbers of Monte Carlo samples. We observe that the distributional scores converge faster because we use a smaller maximum dataset cardinality (see Appendix F), but that amortization still provides a significant benefit. The improvement largest for the noisiest estimates, which this case use just 5 samples: amortization achieves correlation 0.81 with the ground truth, versus 0.58 for the Monte Carlo estimates. The improvement is consistent across several measures of accuracy, including squared error, Pearson correlation and Spearman correlation (see Appendix G).

---

Next, we study generalization and the role of dataset size. We focus on the noisiest estimates with 5 Monte Carlo samples, because this low-sample regime is most relevant for larger datasets with millions of examples. We train the valuation model with different portions of the 50K training set, and we measure the estimation accuracy for both internal and unseen external data. Figure (right) shows large improvements in squared error with few as 1K data points, and we also observe improvement in correlation when we use at least 5K data points (10% of the dataset, see Appendix G). We additionally observe a small generalization gap, suggesting that the valuation model can be trained with subset of the data and reliably applied to unseen examples.
Lastly, we test the usage of amortized valuation scores in downstream tasks. Following [53], the tasks we consider are identifying mislabeled examples and improving the model by removing low-value examples. These results are shown in Appendix G, and we find that the amortized estimates identify mislabeled examples more reliably than Monte Carlo estimates, and that filtering the dataset based on our estimates leads to improved performance.
Conclusion
This work explored the idea of stochastic amortization, or training amortized models with noisy labels. Our main finding that fast, noisy supervision provides substantial compute and accuracy gains over existing XML approximations. This approach makes several feature attribution and data valuation methods more practical for large datasets and real-time applications, and it may have broader applications to amortization beyond XML. [2]. Our proposal has certain limitations, including that stochastic amortization may become ineffective with sufficiently high noise levels, and that is difficult to know priori how much compute is necessary for label generation to achieve desired error level in the amortized predictions.
Our work suggests multiple directions for future research. One direction to study the trade-off between using& larger number of noisy labels smaller number of more accurate labels, which is a key difference from prior work that uses near-exact labels for amortization [14]. Other directions include scaling datasets with millions of examples test the limits of noisy supervision, leveraging more sophisticated data valuation estimators [106], using alternative model retraining primitives [57, 63, 37], and exploring amortization for other methods like datamodels (discussed in Appendix B).
Code
We provide two repositories reproduce each our results:
Feature attribution
Data valuation
Acknowledgements
The authors thank Yongchan Kwon for helpful discussions and advice on using OpenData Val. We also thank Mukund Sudarshan and Neil Jethani for early conversations about amortizing data valua- tion. Chanwoo Kim and Su-In Lee were supported by the National Science Foundation (CAREER DBI-1552309 and DBI-1759487) and the National Institutes of Health (R35 GM 128638 and R01 AG061133 132).
References
[1] Samira Abnar and Willem Zuidema. Quantifying attention flow in transformers. arXiv preprint arXiv:2005.00928. 2020.
[2] Brandon Amos. Tutorial on amortized optimization for learning to optimize over continuous domains. arXiv preprint arXiv:2202.0000 20666600..066 2022.
10

---

[3] Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better under- standing of gradient- based attribution methods for deep neural networks. In International Conference on Learning Representations, 2018.
[4] John F Banzhaf. Weighted voting doesn't 't work: a mathematical analysis. Rutgers Law Review, 19:317, 1964.
[5] Sébastien Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends@ in Machine Learning, 8(3-4):231-3577 2015.
[6] Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 3665):172-11330, 2009.
[7] A Charnes, B Golany, M Keane, and Rousseau. Extremal principle solutions of games in characteristic function form: core, Chebychev and Shapley value generalizations. In Econometrics of Planning and Efficiency, pages 123-133. Springer, 1988.
[8] Aditya Chattopadhyay, Stewart Slocum, Benjamin Haeffele, Rene Vidal, and Donald Geman. Interpretable by design: Learning predictors by composing interpretable queries. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2022.
[9] Aditya Chattopadhyay, Kwan Ho Ryan Chan, Benjamin Haeffele, Donald Geman, and René Vidal. Variational information pursuit for interpretable predictions. arXiv preprint arXiv:2302.02876 2023.
[10] Hugh Chen, Ian C Covert, Scott M Lundberg, and Su-In Lee. Algorithms to estimate Shapley value feature attributions. arXiv preprint arXiv:2207.07600. 2022.
[11] Jianbo Chen and Michael Jordan. LS-Tree: Model interpretation when the data are linguistic. Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 3454-3461, 2020.
[12] Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information-theorrtie perspective on model interpretation. arXiv preprint 10X.xv180020700 2018.
[13] Yu-Neng Chuang, Guanchu Wang, Fan Yang, Zirui Liu, Xuanting Cai, Mengnan Du, and Xia Hu. Efficient XAI techniques: A taxonomic survey, arXiv preprint arXiv:2302.03225, 2023,
[14] Yu-Neng Chuang, Guanchu Wang, Fan Yang, Quan Zhou, Pushkar Tripathi, Xuanting Cai, and Xia Hu. CoRTX: Contrastive framework for real-time explanation. arXiv preprint arXiv:2303.0277 2023.
[15] R Dennis Cook and Sanford Weisberg. Characterizations of an empirical influence function for detecting influential cases in regression. Technometrics, 22(4):495-508, 1980.
[16] Ian Covert and Su-In Lee. Improving KernelSHAP: Practical Shapley value estimation using linear regression. In International Conference on Artificial Intelligence and Statistics, pages 3457-3465. PMLR, 2021.
[17] lan Covert, Scott Lundherg, and Su-In Lee. Explaining by removing: A unified framework for model explanation. Journal of Machine Learning Research, 22(209):1-90 2021.
[18] Ian Covert, Chanwoo Kim, and Su-In Lee. Learning to estimate Shapley values with vision transformers. arXiv preprint arXiv:2206. 055882 2022.
[19] Ian Covert, Wei Qiu, Mingyu Lu, Nayoon Kim, Nathan White, and Su-In Lee. Learning to maximize mutual information for dynamic feature selection. arXiv preprint arXiv:2301.0053: 2023.
[20] Ian C Covert, Scott Lundberg, and Su-In Lee. Shapley feature utility. In Machine Learning in Computational Biology. 2019.
[21] Piotr Dabkowski and Yarin Gal. Real time image saliency for black box classifiers, In Advances in Neural Information Processing Systems, pages 6967-6976, 2017.
11

---

[22] Ofer Dekel, Ran prediction using mini-batchen Journal of Machine Learning Research, 13(1), 2012.
Ohad Shamir, and Lin Xiao. Optimal distributed online
[23] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, pages 148-255. IEEE, 2009.
[24] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, al. An image worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010.
1929, 1929, 2020.
[25] Dheeru Dua and Casey Graff. UCT machine learning repository, 2017. htt.http:/arrccive... ics uci edu/ml.
[26] Pradeep Dubey and Lloyd S Shapley. Mathematical properties of the Banzhaf power index. Mathematics of Operations Research, 4(2):99-131, 1979.
[27] Logan Engstrom, Axel Feldmann, and Aleksander Madry. DsDm: Model-aware dataset selection with datamodels. arXiv preprint arXiv:2401. 12926, 2024.
[28] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33: 2881-2891, 2020.
[29] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International Conference on Machine Learning, pages 1135, PMLR, 2017.
[30] Ruth Fong, Mandela Patrick, and Andrea Vedaldi. Understanding deep networks via extremal perturbations and smooth masks. In Proceedings of the IEEE International Conference on Computer Vision, pages 2950-2958, 2019.
[31] Ruth C Fong and Andrea Vedaldi. Interpretable explanations of black boxes by meaningful perturbation. In Proceedings of the IEEE International Conference on Computer Vision, pages 2017.
[32] Fabian Fumagalli. Maximilian Muschalik, Patrick Kolpaczki, Eyke Hüllermeier, and Barbara Hammer. SHAP-IQ: Unified approximation of any-order Shapley interactions. arXiv preprint arXiv:2303.01173 2023.
[33] Amirata Ghorbani and James Zou. Data Shapley: Equitable valuation of data for machine learning. In International Conference on Machine Learning, pages 2242-2251. PMLR, 2019.
[34] Amirata Ghorbani. Abubakar Abid, and James Zou, Interpretation of neural networks is fragile. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 3681-3688
2019.
[35] Amirata Ghorbani, Michael Kim, and James Zou. A distributional framework for data valuation. In International Conference on Machine Learning, pages 3535-3544. PMLR, 2020.
[36] Amirata Ghorbani, James Zou, and Andre Esteva. Data Shapley valuation for efficient batch active learning. In 2022 56th Asilomar Conference Signals, Systems, and Computers, pages 1456-1462. IEFF, 2022.
[37] Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, et al. Studying large language model generalization with influence functions. arXiv preprint arXiv:2308.0334 03296, 2023.
[38] David Ha, Andrew M Dai, and Quoe Le. HyperNetworks. In International Conference on Learning Representations, 2016.
[39] Tuomas Haarnoja, Aurick Zhou, Kristian Hartikainen, George Tucker, Sehoon Ha, Jie Tan, Vikash Kumar, Henry Zhu, Abhishek Gupta, Pieter Abbeel, al. Soft actor-critic algorithms and applications. arXiv preprint 17X1v:1812.05505, 2018.
12

---

[40] Peter L Hammer and Ron Holzman. Approximations of pseudo-boolean functions; applications to game theory. Zeitschrift für Operations Research, 36(1):3-21, 1992.
[41] Elad Hazan et al. Introduction to online convex optimization. Foundations and Trends& in Optimization, (3--4)155--325) 2016.
[42] He He, Paul Mineiro, and Nikos Karampatziakis. Active information acquisition. arXiv preprint arXiv:1602.022. 02080. 2016.
[43] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, pages 770-778, 2016.
[44] Weijie He, Xiaohao Mao, Chao Ma, Yu Huang, José Miguel Hernandez-Lobato, and Ting Chen. BSODA: a bipartite scalable framework for online disease diagnosis. In Proceedings of the ACM Web Conference 2022, pages 2511-2521, 2022.
[45] Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learning continuous control policies by stochastic value gradients. Advances in Neural Information Processing Systems, 28, 2015.
[46] Jeremy Howard and Sylvain Gugger. FastAl: A layered API for deep learning. Information, 1(2):108, 2020.
[47] Andrew lyas, Sung Min Park, Logan Engstrom, Guillaume Leclerc, and Aleksander Madry. Datamodels: Predicting predictions from training data. arXiv preprint arXiv:2202.00) 2022.
[48] Saachi Jain, Hadi Salman, Eric Wong, Pengchuan Zhang, Vibhav Vineet, Sai Vemprala, and Aleksander Madry. Missingness bias in model debugging. In International Conference on Learning Representations, 2021.
[49] Neil Jethani, Mukund Sudarshan, Yindalon Aphinyanaphongs. and Rajesh Ranganath. Have we learned to explain?: How interpretability methods can learn to encode predictions in their interpretations. In International Conference on Artificial Intelligence and Statistics, pages 1459-1467. PMLR, 2021.
[50] Neil Jethani, Mukund Sudarshan, Ian Connick Covert, Su-In Lee, and Rajesh Ranganath. FastSHAP: Real-time Shapley value estimation. In International Conference on Learning Representations, 2021.
[51] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nezihe Merve Gurel, Bo Li, Ce Zhang, Costas J Spanos, and Dawn Song. Efficient task- specific data valuation for nearest neighbor algorithms. arXiv preprint arXiv:1908.08611 2019.
[52] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas Spanos. Towards efficient data valuation based on the Shapley value. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[53] Kevin Fu Jiang, Weixin Liang, James Zou, and Yongchan Kwon, OpenData Val: unified benchmark for data valuation. arXiv preprint arXiv:2306. 10577, 2023.
[54) Hoang Anh Just, Feiyang Kang, Jiachen Wang, Yi Zeng, Myeongseob Ko, Ming Jin, and Ruoxi Jia. Lava: Data valuation without pre-specified learning algorithms. arXiv preprint urXiv:2305.00054 2023.
[55] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014.
[56] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint arXiv:1312.6111 2013.
[57] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions.
In International conference machine learning, pages 1885-1894. PMLR, 2017.
13

---

[58] Patrick Kolpaczki, Viktor Bengs, Maximilian Muschalik, and Eyke Hillermeier. Approxi- mating the shapley value without marginal contributions. arXiv preprint arXiv:2302.00736. 2023.
[59] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[60] Yongchan Kwon and James Zou, Beta Shapley: unified and noise-reduced data valuation framework for machine learning, arXiv preprint arXiv:21 10.2//00.00 14049, 2021.
[61] Yongchan Kwon and James Zou. Data-OOB: Out-of-bag- estimate as a simple and efficient data value. arXiv preprint arXiv:2304.077/6 2023.
[62] Yongchan Kwon and James Y Zou. WeightedSHAP: analyzing and improving Shapley based feature attributions. Advances in Neural Information Processing Systems, 0134363-343770 2022.
[63] Yongchan Kwon, Eric Wu, Kevin Wu, and James Zou. Datalnf: Efficiently estimating data influence in lora-tuned Ilms and diffusion models. arXiv preprint arXiv:2310.00902, 2023.
[64] Sergey Levine and Vladlen Koltun. Guided policy search. In International Conference on Machine Learning, pages 1-9. PMLR, 2013.
[65] Weida Li and Yaoliang Yu. Faster approximation of probabilistic and distributional values via least squares. In International Conference on Learning Representations, 2024.
[66] Chris Lin, Ian Covert, and Su-In Lee. On the robustness of removal-based feature attributions. arXiv preprint arXiv:2306. 07462, 2023.
[67] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019.
[68] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems, pages 4765-4774, 2017.
[69] Scott M. Lundberg, Gabriel Erion, Hugh Chen, Alex DeGrave, Jordan M. Prutkin, Bala Nair, Ronit Katz, Jonathan Himmelfarb, Nisha Bansal, and Su-In Lee. From local explanations global understanding with explainable AI for trees. Nature Machine Intelligence, 2(1): 2522-5839, 2020.
[70] Chao Ma, Sebastian Tschiatschek, Konstantina Palla, Jose Miguel HernandezzLobato, Sebas- tian Nowozin, and Cheng Zhang. EDDI: Efficient dynamic discovery high-value information with partial VAE. In International Conference on Machine Learning, pages 4234 4243. PMLR, 2019.
[71] Chris Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: continuous relaxation of discrete random variables. arXiv preprint 16 (o..://110000 1.007 2016.
[72] Divyat Mahajan, Chenhao Tan, and Amit Sharma. Preserving causal constraints in coun- terfactual explanations for machine learning classifiers. arXiv preprint 1rXiv:1912.03377. 2019.
[73] Jean-Lue Marichal and Pierre Mathonet. Weighted Banzhaf power and interaction indexes through weighted approximations games. European Journal of Operational Research, 211 (2):352-358, 2011.
[74] Rory Mitchell, Joshua Cooper, Eibe Frank, and Geoffrey Holmes. Sampling permutations for Shapley value estimation. arXiv preprint arXiv:2104.1 12199, 2021.
[75] Dov Monderer, Dov Samet, et al. Variations on the Shapley value. Handbook of Game Theory, 3:2055-2076, 2002.
[76] Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization, 19(4): 1574-1609, 2009.
14

---

[77] Ramin Okhrati and Aldo Lipani. A multilinear sampling algorithm to estimate shapley values. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 7992-7999. IEFE, 2021.
[78] Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Madry, TRAK: Attributing model behavior scale. arXiv preprint 1rXi::2303.14186 2023.
[79] Kaare Brandt Petersen, Michael Syskind Pedersen, al. The matrix cookbook. Technical University of Denmark, 7(15):510, 2008.
[80] Aravind Rajeswaran, Chelsea Finn, Sham M Kakade, and Sergey Levine. Meta-learning with implicit gradients. Advances in Neural Information Processing Systems, 32, 2019.
[81] Samrudhdhi B Rangrej and James J Clark. A probabilistic hard attention model for sequentially observed scenes. arXiv preprint arXiv:2 2021.
[82] Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference deep generative models. In International Conference on Machine Learning. pages 1278-1286 PMLR, 2014.
[83] Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?" Explaining the predictions of any classifier. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135-1144, 2016.
[84] BP Roe, HJ Yand, J Zhu, Y Lui. Stancu, et al. Boosted decision trees, an alternative to artificial neural networks. Nucl. Instrm. Meth. A, 543:577-584, 2005.
[85] Nikunj Saunshi, Arushi Gupta, Mark Braverman, and Sanjeev Arora. Understanding influence functions and datamodels via harmonic analysis. arXiv preprint arXiv:2210.01072, 2022.
[86] Patrick Schwab and Walter Karlen. CXPlain: Causal explanations for model interpretation under uncertainty. In Advances in Neural Information Processing Systems, pages 10220-10230, 2019.
[87] Robert Schwarzenberg, Nils Feldhus, and Sebastian Möller. Efficient explanations from empirical explainers. arXiv preprint orXiv:2103.3 /5429, 2021.
[88] Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-CAM: Visual explanations from deep networks via gradient- based localization. In Proceedings of the IEFE International Conference on Computer Vision, pages 618-626, 2017.
[89] Lloyd S Shapley. A value for n-person games. Contributions to the Theory of Games, 2(28): 307-317, 1953.
[90] Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference on Machine Learning. pages 3145-3153, PMLR, 2017.
[91] Rui Shu. Amortized optimization, 2017. URL http:://ruushh..oo001///111 peartized-optimizaatee
[92] Grah Simon and Thouvenot Vincent. A projected stochastic gradient algorithm for estimating Shapley value applied in attribute importance. In International Cross-Domain Conference for Muchine Learning and Knowledge Extraction, pages 97-115. Springer, 2020.
[93] Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 2013.
[94] Sumedha Singla, Brian Pollack, Junxiang Chen, and Kayhan Batmanghelich. Explanation by progressive exaggeration. arXiv preprint 191 2019.
[95] Daniel Smilkov, Nikhil Thorat, Been Kim, Fernanda Viégas, and Martin Wattenberg. Smooth- grad: removing noise by adding noise. arXiv preprint arXiv:1706.0388 2017.
15

---

[96] Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. Journal of Machine Learning Research, 11:1-18, 2010.
[97] Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of the 34th International Conference Machine Learning-Volie 70, pages 2319-3328, JMLR. org. 2017.
[98] Mukund Sundararajan, Kedar Dhamdhere, and Ashish Agarwal. The Shapley taylor interaction index. In International Conference Machine Learning, pages 9259 02689992... PMLR, 2020.
[99] Aad W Van der Vaart. Asymptotic Statistics, volume Cambridge University Press, 2000.
[100] Sahil Verma, John Dickerson, and Keegan Hines. Counterfactual explanations for machine learning: A review. arXiv preprint arXiv:2010.1055 2020.
[101] Sahil Verma, Keegan Hines, and John P Dickerson. Amortized generation of sequential algorithmic recourses for black-box models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8512-8519, 2022.
[102] Sandra Wachter, Brent Mittelstadt, and Chris Russell. Counterfactual explanations without opening the black box: Automated decisions and the GDPR. Harvard Journal of Law & Technology, 31:841, 2017.
[103] Tianhao Wang and Ruoxi Jia. Data Banzhaf: A data valuation framework with maximal robustness to learning stochasticity. arXiv preprint arXiv:205.154666, 2022.
[104] Tianhao Wang, Yu Yang, and Ruoxi Jia. Improving cooperative game theory-based data valuation via data utility learning. arXiv preprint arXiv:2107.06336, 2021.
[105] Brian Williamson and Jean Feng. Efficient nonparametric statistical inference on population feature importance using Shapley values. In International Conference Machine Learning, pages 10282-1029 PMLR, 2020.
[106] Mengmeng Wu, Ruoxi Jia, Changle Lin, Wei Huang, and Xiangyu Chang. Variance reduced Shapley value estimation for trustworthy data valuation. Computers & Operations Research, page 106305, 2023.
[107] Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. Davinz: Data valuation using deep neural networks at initialization. In International Conference on Machine Learning, pages 24150-24177 PMLR, 2022.
[108] Jinsung Yoon, James Jordon, and Mihaela van der Schaar. INVASE: Instance-wise variable selection using neural networks. In International Conference on Learning Representations, 2018.
[109] Matthew D Zeiler and Rob Fergus. Visualizing and understanding convolutional networks. In European Conference on Computer Vision, pages 318-833. Springer, 2014.
[110] Borui Zhang, Baotong Tian, Wenzhao Zheng, Jie Zhou, and Jiwen Lu. Exploring unified perspective for fast Shapley value estimation. arXiv preprint arXiv:2311.01010, 2023.
[111] Jianming Zhang, Sarah Adel Bargal, Zhe Lin, Jonathan Brandt, Xiaohui Shen, and Stan Sclaroff. Top-down neural attention by excitation backprop. International Journal of Computer Vision, 126( 1084-1100, 2018.
16

---

A Extended Related Work
This section provides a more detailed review of amortization in XML. Many XML tasks involve analyzing individual data points, e.g., to determine the most important features or concepts model, or a data point's 's influence on the model's 's accuracy or an individual prediction. Among these methods, many require expensive per-example algorithms, and trend in recent years has been to amortize this computation using deep learning. We discuss these works below, grouping them into several main XML problems that they address.
Within this discussion, we differentiate works not only based on their goal (e.g.. feature attribution or data valuation) but also based on how they calculate the object of interest. For those that perform per-example computation, we distinguish between methods that solve a parametric optimization problem of the form a(b) = arg min,' hia';b) (e-g., with gradient descent) from those that exploit an analytic solution, either by directly calculating the result or using Monte Carlo approximation. For those that use amortization, we distinguish those that use regression- -based amortization with Lreg (0) from those that perform objective-basse amortization with (ob (see Appendix C for more details on objective- based amortization [2]).
Table summarizes the methods we discuss, including the various tasks they solve, the context and output domains (A, B) for each problem, and the computational approach. This perspective highlights the significant role of amortization in XML., and it also reveals opportunities for new applications, some of which we discuss in Section 4. Some of the same works discussed by Chuang al. [13), but we cover a wider range of methods, and we adopt the framing of Amos [2] by outlining the various parametric optimization problems and different amortization approaches.
Feature attribution. These methods aim to quantify the importance of a model's input features, typically for individual predictions (such methods are called local rather than global feature attribu- tions, see Lundberg et al. [69]). The context is therefore a data example x E X, and the output is a vector of attributions in Rd when we have d features. Feature attribution algorithms can be efficient to calculate, particularly when they are based on simple propagation rules [93, 97, 90, 95, 88, 111, 3] or transformer's attention values [1]. However, another family of approaches
based on feature removal [17], and querying the model with many feature subsets is typically less efficient.
Among the feature removal-based methods, one of the most famous is Shapley value feature attribu- tions [68, 89]. Two related methods are LIME [83] and Banzhaf values [11, 4]. see our discussion of their similarity in Section 4. Many works have focused on efficiently calculating these attributions, because their computational complexity is exponential in the number of features. As discussed by Chen et al. [10], there are many stochastic estimators derived from analytic expression for the attri- butions| [6, 96, 77, 16, 74, 103, 58], and these are typically unbiased Monte Carlo estimators. Others are based solving an optimization problem, for example with either M-estimation [83, 68, 105, 16] or gradient descent [92].
Lastly, there are also methods based on amortization, which offer the possibility of real-time feature attribution without a significant loss in accuracy. Two works consider abjective-based amortization, which avoids the need for labels during training [50, 18]. Others consider regression- tion [86, 87, 14], and these recommend using high-quality labels; for example, Chuang et al. [14] use exact labels when possible. Our perspective is most similar to the concurrent work by Zhang et al. [110], in that we highlight the potential for regression-baat based amortization with inexpensive, noisy labels; but our work is more general in that we highlight the potential to use noisy labels from any unbiased estimator, and the applicability of this approach to other XML tasks like data valuation.
amortiza-
Instance-wist wise feature selection. A related set of methods select the most important features for individual predictions. The context in this case is an input x E X, and the output is a set of feature indices S P((d) where we use PP-)) to denote the power set. The optimal subset can be defined either based on the prediction f(rs) or f(zj))) for a specific class [31], or based on the deviation from the original prediction fax) [12]. Among these methods, some solve the underlying optimization problem on per-input basis [31, 30], and others solve it using objective- based amortization [21, 12, 108, 49]. These methods all require differentiating through discrete subsets, so they employ various continuous relaxations (e.g., the Concrete distribution [71]), as well as other tricks to constrain or penalize the subset size. These methods are sometimes thought of as attribution methods due to the continuous relaxations [31, 30], but we describe them as feature
17

---

Dahkowsks and Gall (21)
Jethani (50)
Civen et [18]
Clen [12]
Your er al [108]
Civen et [19]
Verna et al. [101]
L and Yn [65]
Cabo (0)
Clattopudlly et
Mahajan ct
Jethani
Sehwarzesherg al. [87]
Schwab and Karlen (86)
Ghorrbnni et all [3S, 30]
Chuang et [14]
Zhung [110)
He al. (42)
Eyeg (0)
Table Summary of amortized methods in XML.
Peretample optiiizaiion
Landberg and Lee [68]
Simon and Vincent (92)
Covert and Lee [16]
Ribeiro et [83]
Clen and Jordan [1)]
Fong and Vediali [31]
Fong (30)
Ma al [70]
Wiehter al [102)
Sirumbelj und Konemenko (96)
Okhnii and Liponi [77]
Zeiler and Forgus [109)
Ghorban and Zou [33]
Mitchell (94)
Covert ata [17]
Kwon (60)
[103]
Analytic
Domain
P(d))
Rd
(d]
X
R
R
#3 C x P((d))
(S,,a) E DXX
Cintext
E 2
SE D
* E
Shapley value attribution
Ceve-ooc--on attribution
Banzhaf valte attributioo
Instance wisse selection
Dynamic feature relection
Counterfactual explanation
LIME attribution
Image masking
Dita Shapley
Bein Shapley
Banshal
Datamodels
Problem
18

---

selection methods because the final scores for each feature are restricted to the range [0, 1] and are made continuous mainly for optimization purposes.
Dynamic feature selection. Next, other works select features separately for each prediction to achieve high accuracy with small feature aequisition budget. Each selection is made based on a partially observed input, so the context is a feature subset Is, which we write as belonging to the domain X X P(dd), and the oulput is an index optimal selection at each step, but one common approach is to define it as the feature with maximum conditional mutual information, or i" arg max, I(y; x4 æs). where the response variable y and unobserved features F; are random variables and øs has fixed observed value. Given access to this objective, it is trivial to solve by enumerating the possible indices; however, the mutual information is typically unavailable in practice and must be approximated. One approach is therefore to fit proxy for the mutual information (e.g. via a generative model) and then optimize this proxy for each selection [70, 81, 8, 44]. An alternative is to learn a network that predicts the optimal selection at each step: He al. [42] do so using imitation learning, which resembles regression-basees amortization, and Chattopadhyay et al. [9] and Covert et al. [19] do so with an optimization-base view of the mutual information [ x; zg), which is objective-based amortization.
[d]. There are several ways to define the
Counterfactual explanation. The goal of counterfactual explanations (also known as recourse explanations) to identify small changes to an input that cause a desired change in a model's prediction. The context is an input I E X, and the output is a modified version x' E X' that is typically not too different from the original input. This family of methods was introduced by Wachter et al. [102] and is generally framed as an optimization problem involving the prediction (xx' and a measure of the perturbation strength between x' and æ. Verma et al. [100] provide a review of these methods and the various choices for the optimization formulation. When computing these explanations, the most common approach is to solve the problem separately for each input, e.g., using gradient descent [102]. Other works have explored learning models that directly output the modified example x', and these are typically implemented using objective-based amortization [72, 94, 101, 13].
Data valuation. The goal of data valuation is to assign scores to each training example that represent their contribution to a model's performance. The context is therefore a labeled training example 2 E DD. and the output is a real-valued score. These methods are typically not defined via an optimization problem, but instead as a measure of the example's s expected impact on performance across distribution of preceding datasets [33, 35, 60, 103]. Existing methods therefore rely on analytic expressions for the valuation scores, which require Monte Carlo approximation because they are intractable. Two works have considered predicting data valuation scores given dataset of near-exact estimates [35, 36), which regression-based amortization. Our work is similar, but we use inexpensive estimates to reduce the cost of amortization and scale more efficiently to larger datasets. Concurrently, Li and Yu [65] proposed a learning- based approach analogous to FastSHAP for feature attribution [50]. but whose memory requirements scale with the dataset size and limit applicability to large datasets. Besides these methods, there are also data valuation approaches that can be calculated without any approximations [51, 54, 61].
Data attribution. Finally, data attribution methods aim to quantify the effect of training examples on individual predictions. The context is therefore training example DD paired with an inference example x E X, and the output a real-values attribution score. One classic approach to this problem is influence functions [15], which use a gradient- based approximation to avoid the cost of retraining [57, 37, 63]. Another class of methods involve measuring the effect of training with subsampled datasets [28, 47]. For datamodels, the main existing approximation algorithm is based on solving global least squares problem| [47], which does not correspond to any of the computational approaches listed in Table 1; notably, it is not a form of amortization because there is no model that can predict the attribution given a new tuple (2, As an alternative to the global least squares problem. TRAK calculates similar scores datamodels using a gradient-based based approximation [78, 27]. We not aware of any work investigating amortization for datamodels, but our results in Appendix B show how to approximate the scores based their analytic solution, and how to amortize the computation by adopting Monte Carlo estimates as noisy training labels.
19

---

B Datamodels
The datamodels technique [47] aims to quantify how much each training data point 2; D affects the prediction for an inference example E X. Similar to data valuation, the inference example's output given training dataset D is represented by a function 2/ (Dr), and the attribution scores ((2,, 22 R are then defined as the solution to a joint least squares problem that can be solved after training many models with different datasets, as we show below. For the inference example's output Ux (Dr), Ilyas et al. [47] focus on the loss rather than the raw prediction, but our perspective can accommodate any definition of this output.
Our insight on the datamodels technique is twofold. First, we show that the datamodels scores are equal simple expectation and can be estimated in an unbiased fashion. Second, we show that these calculations can be amortized by using the noisy Monte Carlo estimates as training targets. Our findings rely on slight reformulation the datamodels scores, where we deviate from Ilyas et al. [47] by using an intercept term and a subtly different dataset distribution: our distribution biased towards size nq for value 9 (0, 1) rather than using a fixed size, which was also considered in recent work by Saunshi et al. [85]. In the following result, we use the shorthand ((x) = [C(21, ((m,,,,((( for the vector of data attributions. Given a probability & E (0, 1), we also define the weighting function u(k) q² (1-1)--1-4 With this setup, our reformulation the following (see the proof in Appendix D).
Proposition 1. Given a subset distribution that includes each data point 2t E D with probability q E (), the data attribution scores defined by
((ao (( (a0 (ao+I
((x) arg min ET aεRn+1
22 (Dr)
iET
can be expressed the following expectation:
((21,))
Σ u(IT)) (vx (+()) - uz (Dr))
TCh
Perhaps surprisingly, this corresponds to game-theoretic semivalue and reduces to the Banzhaf value when q 1/2 [73]. Based on this perspective, we can estimate the score ((2,, without solving the regression problem from Ilyas et al. [47]. For example, we can simply sample & datasets Dr from the distribution with E (0, 1). and then calculate the empirical average as follows:
((2,,))
1
Σ Ca (Dr, ((:)) j=1
uz (Dr, \ (zi)).
Following Proposition 1, we have the unbiasedness property E[{(=;, S(2s, æ).. Furthermore, rather than repeating this estimation for each attribution score, we can amortize the process by fitting an attribution model ((2,, x; 0) using the noisy estimates ((2;, as training targets. Our experiments do not test this approach, which we leave direction for future work. Implementing this requires a more complex architecture to handle two model inputs x and 2, but we speculate that trained effectively, amortization could accelerate attribution within the training set and generalize to new inference examples & E X' with no additional overhead.
"As we noted in the main text, although datamodels performs data attribution by fitting linear regression model, it is not a form of amortization because the resulting model cannot predict attribution scores ((2, x) for datapoints. The attribution scores given by the model's coefficients, not its predictions.
20

---

C Connection to Objective-Based Amortization
Recall that many tasks with repeated computation have an optimization view where a(b) arg min. Maa;;
; b) [91, 2] (see Section 2). For completeness, this section describes an interpretation of stochastic amortization from this optimization perspective. An alternative to regression-base amortization when we have an objective h(a'; b) that defines a(b) is to train a(b; 8) directly with the objective:
Lobs (0) [E|((((b; 0); 0)]
(12)
This approach provides an alternative when exact labels are costly, but it can be unappealing because (i) the task may not offer a natural objective h(a' b). and (ii) minimizing h(a'; b) may seem discon- nected from the error [|a(b; 0) a(b)lI. We discuss these issues below and how they are related to stochastic amortization.
For issue (i), certain problems like Shapley values have a natural optimization characterization (see Section 4.1), but this is not always the case: for example, data valuation scores framed as an expectation rather than via optimization (see Section 4.3 or [33]). so they lack an optimization view, We always have the trivial optimization perspective h(a'; b) = || a(b)]l but this is useful because it reduces Lobj( (0) to Ereg(0) and requires the exact outputs a(b). Regardless of whether the task offers natural objective h(a'; b), stochastic amortization can be viewed as defining new objective that does not require the exact outputs: given noisy oracle ā(6), stochastic amortization is equivalent to Lobj(8 (f) with the objective h(a'; b) = E [lla' - a(b)]l²] and if the oracle is unbiased then the optimal predictions are a(b; 0) = =ab).
Next, issue (ii) is a concern when h(a'; b) is available but lacks clear connection to the estimation error, which is directly reflected by Lreg(0), The squared error is in many cases a more meaningful accuracy measure, and it is commonly used to evaluate estimation accuracy for feature attribution and data valuation [50, 103, 10]. Certain works on objective- based amortization have considered non- convex objectives baa'; b) where the exact output a(b) is not well-defined [2], but we can understand the potential disconnect by focusing on a class of well behaved objectives. particular, we assume that h(a'; b) is c-strongly convex and 8-smooth in a' for all b, then the Lieg(0) and Lobj (0) objectives bound one other as follows,
3
Creg(0) (0) I Lob)(0) - Cōbs S
2 (r)
(13)
2
where we define Caj ([](a(b):b)) b]] (see proof in Appendix D.I). Eq. (13) shows that by mini- mizing (f), we effectively minimize both upper and lower bounds on Creg (0). However, these bounds can be loose: for example, because we have Lreg (0) < 2 (() and the strong convexity constant shrinks zero for Shapley values the number of features grows [18], optimizing
Labj (0) may become less effective in high dimensions. Stochastic amortization resolves this potential disconnect between (0) and Creg( (0) follows: if we an unbiased noisy oracle â(b), then
training with Erog (0) is equivalent to using (ab with haaa; b) E [lla' a(b)] so we have
= 3 = 1 in Eq. (13) and the regression objectives Lreg and Ereg (0) are equal up to a constant (.,) -(a).
21

---

D Proofs
This section provides proofs for our claims in the main text. Appendix D.1 shows proofs for our results related to stochastic amortization in Section 3 and Appendix C, and then Appendix D.2 shows the proof for Proposition related datamodels.
D.1 Amortization proofs
We first derive the inequality in Eq. (4) from the main text, which is the following:
(0) - (N))
< Creg - (rrr N(a)
N(ē) + NN))) VB(a))
Proof. We begin by decomposing a per-input version of the noisy oracle loss Creg 0). which takes an expectation over the noisy oracle ä(b) for a fixed b:
Creg (b; 0) E [lla(b; 0) a(b)ll [6]
|la(b; 0) B(ā(b) b11 B(lā(b)) B(ā(b) |0]l |
|la(b; 0) B(ā(b) 6]]l N(@ b).
Next, we can also decompose per-input version of the original regression loss Lreg (b; 0) as follows using triangle inequality:
Creg(b; = |la(b;; 0) a(b)ll
S (Ila(b; 0) E(ā(b) blll + [|a(b) - E(ā(b) b]ll)
= ( Creg (b: N(ā b) + /B(ā [b]
2
Taking both sides of the inequality in expectation over p(b), we arrive at the following upper bound:
N(@ b) (Vn)
(0) s E
B(a 6)
One side of the bound in Eq. (4) comes from developing the square and applying Cauchy-Schwaad to the cross term:
Crop ( & E (V N(a b) + / B(a b)
Cray N(ā 1b) b)] + E [B b)] - 22
B(ā b) (Creg(b;0) - N(a 6))
Erog -0)- N B(ā) + 2 B(a) (Creg( N(a)
(V) N(a) B(a)
This proves the upper bound in Eq. (4). For the lower bound, we return to the decomposition of the per-input noisy oracle loss Creg (b: 0) and apply triangle inequality as follows:
22

---

Greg(:: (b; = |Ia(bb;;)) 0) - E(((b) ||| + N( b)
S (Ila(b;)) a(b)l ||a(b) [lā(b) blll + N(ā 6)
2
(Vorog((: (b; vB(ā b) + N(a b).
Rearranging terms, we have
(voeg((:0)NN((0 /B(( 10)
Leeg (b;
and applying the same logic above with Sauchy-Schwarz, arrive at:
Creg (0) z (o) 1----B(a) BB(a)
Putting the two results together, this yields the two-sided bound in Eq. (4):
(0) (Vens (O) N(ā) v /Bāa) Creg(() 1
N(ā) + + BB(a)
Next, we prove our SGD result for stochastic amortization Theorem
Theorem 1. Consider noisy oracle ā(b) that satisfies B[ā(b) 6] 0b with parameters E mxd such that |0 D. Given distribution p(b), define the norm-weighted distribution q(b) x p(b) - [b6l2 and the terms Dp = Ebbbbb] and Mn = Eg [bb }. we train linear model a(0;b) = Ob with the noisy objective (reg(0) using SGD with step size a(t+T) then the averaged iterate
2
Or -t
TT at step T satisfies
([Creg(0r)) N(ã) < 4TH(ET)) (Nz(ā) + 4Amax (0max(E.g))) (22))22)
Amin (Tp) +1)
E, bi] is the noisy oracle's norm-weighted variance, and Aenase Amin() are the maximum and minimum eigenvalues.
where Ng(a) =
Given assumption about the noisy oracle, we re-write the noisy objective Lrog(0) (0) as follows:
Proof.
Ereg (0) = E [1(00 (1)0-))611) + N(a)
Tr 1T(10 () 6)) + N(a).
clear that the minimizer is 9 and that the minimum achievable error is Ereg (0) N(a). Because the objective composes linear function with convex function, it is convex in 0 and can analyze its convergence using a standard SGD result. Specifically, because we assume that ||@||æ < D, we consider a projected SGD algorithm where each step followed by a projection into the D-ball, t- 0 min(1, D/ [[]l))))) Note that it is common assume bounded solution space when proving SGD's convergence [76, 22.5]. 5].
Before proceeding to the main convergence result, we must derive several properties of this objective and its stochastic gradients. The first the strong convexity constant, and we begin by noting that the gradient is the following (see Section 2.5 of Petersen et al. [79] for review of matrix derivatives):
23

---

Vlrog(0) 2 []] = 2(0 0))2p.
For the strong convexity constant, we require a value a > such that the following satisfied for all parameters 0, 8::
Ereg(0) 2 (0') + Tr (10 VVieg()) + 2 0' ll...
(14)
For the first two terms on the right side of the inequality, we can write:
Erom (0') + Tr (10 0') (0--0) (() N(a) + +Tr (10' 00' + (10' - -0 (0
-()) + (0 (0- 0) Tr (00 2) 1)
By using the minimum eigenvalue of Epp. we write the following.
Tr ((0' 0) - 0) 2 Amin (Ep) 11
and therefore satisfy Eq. (14) as follows:
Erop(() (0) = N(a) + Tr (00 0000)))00-00)
= Eregg(0) (0') + Tr (0 0¹) Viree + Tr 00)'''0 -0T)
2 Erog( + Tr (0 0¹) [T)]TV.,,o (0)) + Amin (Ep)((p) 1
We can therefore conclude that Ereg (8) is 2Xmin strongyy convex.
The next property to derive is the expected gradient norm. When running SGD, we make updates using the following stochastic gradient estimate:
( (06 (ob-
We require upper bound on the stochastic gradient norm, which can be written as follows:
E [1 E [[lo(0) (0) + (0))
(15)
For the first term in Eq. (15), which represents the gradient variance, we have:
E [ls(0) V Virg (0)1B (0)11) = 4E 1100-- 1()0-
To find a simple expression for this term, first consider the expectation over the distribution a(b) with fixed b B3 which isolates label variation due to the noisy oracle:
Eapo [I(0b- T(b))oT [(())_ (0 - Eaj [[(((() 0b)b T 1
+ I1(0
()bb Ep)1
= N(ā 6) ||6|| + ( 0)6 - 2p)
When we take this in expectation over p(b), the first term can be understood as norm-weighted average of the noisy oracle's conditional variance:
24

---

E [(
[[6| p(6)N(ā b) 16/1
- -TrEEp) /
p(b) 1[611
N(a b)db
Tr(E,)
-T(E))NN(a)..
The second term can be rewritten as follows using Ep and Zgg:
[[( 066
Tr (6b T - 20 0)6 -pp)
E Tr (0- (bb [bb Ep)(B 8) T)
(00 - E} [bb (bb Σn] (0 - T)T)
= (0 - (Tr - 22) - 0)
For the deterministic gradient upper bound in Eq. (15), we have:
(V = 4'r ( (00-0)22(-0))
Putting these results together, we can upper bound the expected gradient norm for any parameter values | D as
E [1s{0)]]2]] = (T) Tr ((0 - 00 0)T)
<4TH (a) +4TH Mmax (En) 011
<4THE, N, (a) + 16 T Tr Amax D2
Using results for the objective's strong convexity and expected gradient norm, a standard SGD convergence result. Following Theorem 6.3 from Bubeck et al. [5], if we make T updates with the specified step size, we have the following upper bound on the expected objective value:
invoke
N,, + 16 Amax D2
(16)
Amin (Tp) +1)
Next, we prove simple consequence of this result, which is that the rate from Theorem applies to the original objective freg (0) when we assume an unbiased noisy oracle.
Corollary 1. Following the setup from Theorem 1, if the noisy oracle is unbiased, then the averaged iterate at step T satisfies
(0T)) (T, + (x Amax D2
Amin (Tp)
If the oracle is also noiseless, or if we assume access to the exact oracle ā(b) = a(b). then the averaged iterate step T satisfies
BlLreg (0r)) S 16 {mm) \max >m)x
Amin (2,) +1)
25

---

Proof. The first result follows from combining Theorem 1 with the relationship between Lreg (0) and Lreg(0) (0): if we assume the noisy oracle is unbiased, or B(ā) 0, then we have Leeg (0)
Ereg (0) N()), which implies the first inequality. The second inequality follows from setting
(a = 0 in the upper bound.
Next, provide proof for Eq. (13) regarding the connection between regression- and objective- based amortization, which is the following:
3 2 Creg( S (ob) - Lobs S Lreg(
Proof. This result relics on well known properties from convex optimization [41]. Consider fixed context variable E B. Strong convexity with means that for all a' E A we have:
h(a;b) b) 2 b()';b) + (a - Vah(d':b) Ilaa - d'11?
Considering the optimal value a' = a(b). this simplifies to:
a 2 aa - a - h(a; h(a(b);)))
(17)
Next, smoothness with 8 >> 0 means that for all a' Rd we have:
Vah(a: b) Voh(d': b]]2 s 3|la 3lla-d' d'll.
Lemma 3,4 in Bubeck et [5] shows that 8-smoothness also implies the following:
[b(a; b) - h(d';b) - (a V.h'VaD - 1 lla a'112. Considering the optimal value a' = a{b), this simplifies to:
2
3 2 01110 1la-
h(a; ba()):
(18)
The bounds in Eq. (13) follow from substituting a for predictions from model a(b; 0), and consider- ing Eq. (17) and Eq. (18) in expectation across the distribution p(b).
D.2 Datamodels proofs
Before proving our main claim for datamodels in Proposition 1, we first prove more general result. This version considers an arbitrary symmetric distribution p(T)) over datasets, rather than the specific distribution parameterized by 9 E (0, used in Proposition 1. By symmetric distribution, we mean one that satifies p(T) = p(T") whenever [T] = [
As setup for our derivation, notice that when we assume symmetric distribution p(T), we can define the following probabilities that are identical for all indices i,j E [n]:
Pi = Pr(i T) for [n]
P2 Pr(i,j for forit1
P3 = Pr(i E T for i
Note that we have P1 = P2 + Ps- For example, given a uniform distribution p(T) over subsets with size [T' k. which is used by llyas et al. [47], we have:
26

---

(n-2) 2)
k(k 1) n 1)
(x=1)
k(n k)) n(n 1)
P1
P2
P3
Alternatively, if we have each data point included independently with probability E (0, 1), which is used by Saunshi al. [85] and Proposition 1, then we have p1 = q. P2 q². and pa q(1 q). Our more general claim about datamodels with symmetric distribution p(T') is the following. Lemma 1. Given a symmetric distribution p(T), the data attribution scores defined by
( +
2a--aaeaa Ea-veel7 (aa-vaDDi)) (a=+Ia-ca(r))) 21
((x) = arg min Ex(r)
aER==1
iET
can be expressed the expectation ((Zi,z) = (TG((T)) (DT)), where define the weighting function (T)) as follows:
(T))= = 1 (0-(((11
((iET)
T
PIP3 P3 + n pr)
P3
P3 m(p
Proof. We can write the problem's partial derivatives follows, both for the intercept term ag and the coefficients a, for i E [n]:
à dan
(ao a 11-- - oo (DT)) - 2 (ao + +I [1 - E (vx()
2 (au +1 E(u,(D)))
① E (a0 - da:
(Dr))) (E [1( T) + aQ)] - EE
(Dr)))))))
ao p21 + (p) p2)as pi E 12 (Dr) | 7])
We use the shorthand notation E 1 for a vector with entries üp E (Dr) and ū; (Dr) i E 7 for i E [n]. Combining this with the partial derivatives, we can derive an analytic solution a" E [ by setting the derivative to zero,
1 (niL P2ln1, palm
-
0 p(hn) 0,
a
which yields the following equation for the solution:
1 "'((p1 121,11 + paln
a' a'= = (p1
T(b
-1
0 ú.
p1lm
To find the required matrix inverse, we can combine the Sherman-Morristt formula with the formula for block matrix inversion. The formula for block matrix inversion is the following [79]:
A C D
B
A -A- -BBAA-BB--- - - CA - -C -'AA-'AA -D CA -CC--
-1
-A -A-'B - CA -B)-
B
(D CA CA--B--
We are mainly interested in the lower rows of this matrix because we do not use the learned intercept term. For the lower right matrix, we have the following:
27

---

DD CA 'B) (p21nln + p3ln - p(in11n)
((p2 - pi) + +p31n)
p2 - pr
la
Ps(Ps + +n(p2 - -pi) 1
Ps
Next, for the lower left vector, we have the following:
(-In,
P2 - p
- CD-CA-
In
Inl 1
P3
Ps +n(p2 pf))
P1
np1
p2 pi
1n
n( p4) 1n
P3
P3 Pa
P1
1n.
P3 n(p
Pi
This yields the following solution for the optimal coefficients ot with i [n]:
U. Pi Pi - D (2 + mp pi))
PL P3
Pi 00-
af
P3 n(p2 Pi
jE(n)
Based on this solution, ((c)(T)) = a.- We define the function as follows,
design function c, (T) that we have the expectation
1 1(i ((iETT)
P2 Pî
PIP3
(T)
T
p3
P3 + m(p
pi)
p3 + n(p2 ps)
and it can be verified that this satisfies the required expectation.
similar derivation Lemma is possible when omit intercept term in the datamodels optimization problem, but we do not show the result here.
Finally, we prove the special case of Lemma considered in Proposition 1.
Proposition 1. Given a subset distribution that includes each data point 2 E D with probability q E (0, 1), the data attribution scores defined by
( ao + ++ u2 Dat
27
((x) = arg min Er
aERa11
iET
can be expressed as the following expectation:
((z;,x) Σ TCLNj
((IT)) U vx
Proof. Consider the weighting function (T) introduced in the proof for Lemma In this case, we use the fact that p2 oe and write the weighting function as follows:
1-P1
i
T
(T) (I P1)
Ps
P1
E
Using the fact that p(T) 1 --12 and the coefficient values (1 pi)/ps -q-1 and
-P1/ Ps = -(1 q)-1 we arrive at the result in Proposition 1.
28

---

E Noisy Oracles for XML Methods
This section describes the statistical estimators used for each XML task, which are briefly introduced in Section 4. Each estimator serves as a noisy oracle for the given task, which allows us to train amortized models with inexpensive supervision.
Shapley values. We use three statistical estimators for Shapley value feature attributions. The simplest is permutation sampling, where we average each feature's contribution across set of sampled orderings [6, 96]. For this approach, we use p to denote permutation of the indices [d] where let p(i) [d] { denote the elements appearing before in the permutation. The Shapley value can be understood as the marginal contribution (())())(()))
f(Fp(t) averaged across all possible permutations [89], so first estimator involves sampling l permutations then calculating the following average for each feature:
Pks and
(x) K Σ (1 (()
(19)
Next, we consider two estimators based on the Shapley value's least squares view. Recall that the Shapley value the solution to the following problem (where we discard the intercept term),
2
((r) = arg min
Σ M(S) SCId
[(xx) - -a0
Σ iES
a;
(20)
agRd+1
where we use weighting kernel defined as 1 (S) = ([s))s((dd [7]. The first estimator
we use based on this perspective KernelSHAP [68], which solves this problem using k subsets Sj S [d] sampled according to p(S). The problem is convex but constrained due the weighting terms p((d) = (()) = oo, so it must be solved via the KKT conditions; we refer readers to Covert and Lee [16] for the closed-form solution. We also consider the SGD-Shapley approach from Simon and Vincent [92]: rather than solving Eq. (20) exactly given sampled subsets, this
approach solves the problem iteratively with projected stochastic gradient descent. Unlike the other estimators, SGD-Shapley has been shown to have non-negion non-negligible bias [10]. We used a custom implementation for SGD-Shapley, and we used an open-source implementation of permutation sampling and KernelSHAP."
Banzhaf values. When calculating Banzhaf value feature attributions, we adapt the maximum sample re-use (MSR) estimator from Wang and Jia [103], which was originally used for data valuation but equally applicable to feature attribution. For single example z E X' we generate predictions using subsets S; C [d] sampled uniformly at random. We then split the subsets into those that include or exclude each feature [d], and we estimate the Banzhaf value follows:
(x)x) Hi: S,H
1
Σ f(Es,) Ki:i STT juES;
Σ f(zs,). jogS,
(21)
The re-use of samples across all features makes this estimator more efficient than independent Monte Carlo estimates [103], and re-using samples in this way is simpler for Banzhaf values than for other methods like Shapley values [20, 58]. We used custom implementation for this approach.
LIME. Similar KernelSHAP, the most popular estimator for LIME feature attributions is based on approximately solving its weighted least squares problem. Following the problem formulation in Section 4.2, which we simplify by omitting the regularization term Ω we sample subsets S, S [d] uniformly at random and solve the following importance sampling version of the objective:
(z)....... Ō5(z) = arg min
Σ ((S)) 1=1
e0 + + -a. f(2s,)
(22)
aCR 4-1
iES;
29

---

When doing so, we discard the intercept term, we ensure that k is large enough to avoid singular matrix inversion, and we use the default weighting kernel (TS) for images the official LIME implementation."" 10 We opt to sample subsets uniformly rather than according to x (S) because this approach is used in the official implementation, and because the weighting kernel similar to sampling subsets uniformly at random [66]. We used custom implementation of this approach.
Data valuation. For the various data valuation methods discussed in Section 4.3, use the simplest unbiased approximation, which a Monte Carlo estimator that averages the performance difference across a of sampled datasets. Given a labeled data point 2, we sample datasets Dj D from the appropriate distribution and calculate the following empirical average:
((2)
Σ (D, -
(23)
This is similar to the TMC algorithm from Ghorbani and Zou [33], but we do not employ truncation; approach can be used with truncation, but the noisy labels and valuation model predictions would both become biased. Similar to previous works, we also adopt minimum subset cardinality to avoid training models with insufficient number of data points. We implemented this approach using the OpenData Val package [53]. More sophisticated estimators are available, like those that exploit stratification [106]. re-use samples across all data points [103], assume sparse attribution scores [52], but we leave exploration of these estimators to future work.
Pttpps///gttub..oo//rrrr///////
30

---

F Experiment Details
Model architectures. For the feature attribution experiments, we used the ViT-Base architecture [24] for the classifier, and we used modified version of the architecture for the amortized attribution model: following the approach from Covert et al. [18], we added an extra self-attention layer and three fully-connected layers that operate on each token, so that the output contains an attribution score for each class. When estimating feature attributions, we make predictions with subsets of patches by setting the held-out patches to zero, and the classifier was fine-tuned with random masking to accommodate missing patches [17, 48, 50, 18].
For the data valuation experiments, datasets, and we used a ResNet-18 architecture [43] for CIFAR-10. Valuation scores are defined for labeled examples = = (ar, y), so the valuation model must account for both the features x and the class when making predictions; rather than passing y as a model input, our architecture makes predictions simultaneously for all classes, and we only use the estimate for the relevant class. When generating noisy labels using the TMC estimator [33], we trained a logistic regression model on raw input features for the tabular datasets, and for CIFAR-10 we trained logistic regression on pre-trained ResNet-50 features whose dimensionality was reduced with PCA.
used FCN with two hidden layers of size 128 for the tabular
Hyperparameters. For the feature attribution experiments, optimized the models using the AdamW optimizer [67] with a linearly decaying learning rate schedule. The maximum learning rate was tuned using the validation loss, trained for up to 100 epochs, and we selected the best model based on the validation loss. Due to the small scale of the noisy labels for Banzhaf and LIME feature attributions,
re-scaled the labels during training to improve the model's stability (see Appendix G.2), but this re-scaling was not necessary for Shapley values.
For the data valuation experiments, we optimized the models using Adam [55] with cosine learning rate schedule. The maximum learning rate, the number of training epochs and the best model from the training run were determined using the validation loss. Due to the small scale of the noisy labels, we found it helpful to re-scale them during training to have standard deviation approximately equal to 1. The cost of performing multiple training runs is negligible compared to generating the noisy training labels, so is not reflected in our plots comparing amortization to the Monte Carlo estimator (e.g., Figure 4).
Pretraining. We found that training the amortized models was faster and more stable when we initialized using pretrained architectures. For the feature attribution experiments, we initialized the model using the existing ViT-Base classifier weights For data valuation, we initialized from a classifier trained using the entire dataset, where we used a FCN for the tabular datasets and a ResNet- 18 for CIFAR-10 10. When adapting these models to their respective amortization tasks, the feature attribution models had freshly initialized output layers (one self-attention and three fully-connected),, and the data valuation models had identical output layers that we re-initialized to zero.
Validation loss. For the feature attribution experiments, we calculated the validation loss using independent estimates generated with same estimator and the same number of samples used for the noisy training labels. For the data valuation experiments, we implemented the validation loss using independent Monte Carlo estimates of the data valuation scores. Our independent estimates use only 10 samples for the tabular datasets, and just one sample for CIFAR-10. Amortization provides significant benefit over per-example calculations even after accounting for the cost of the validation loss.
Noisy oracle details. The estimators used for each task are described in detail in Appendix E. For the feature attribution experiments, the permutation sampling and KernelSHAP estimators only require the number of samples as hyperparameters, and we tested multiple values in our experiments (e.g.. Figure 3). For SGD-Shapled we tuned the algorithm in several ways to improve its performance: we used constant rather than decaying learning rate, we took uniform average over iterates, we calculated gradients using multiple subsets, and we used the paired sampling trick from Covert and Lee [16] to reduce the gradient variance. We also tuned the learning rate to a value that did not cause divergence for any examples (5e-4). As described in Appendix G. we observed that SGD-Shapley often had the lowest squared error among the three Shapley value estimators (Figure 1 11), but that did not lead to successful amortization due to its non-negligible bias (Figure 10).
31

---

For the data valuation experiments, models were trained on each subsampled dataset by fitting logistic regression model. either on raw imput features for the tabular datasets or on pre-traine pre-trained ResNet-50 features for CIFAR-10. For the Data Shapley experiments in Section 5.2 with tabular datasets, we sampled datasets without replacement, we used a minimum cardinality of points and a maximum cardinality equal to the number of points n. For the Distributional Data Shapley experiments in Section 5.3 with CIFAR-IO, 10, we sampled datasets with replacement, and we used a minimum cardinality of 100 and maximum cardinality of 1000.
Ground truth. In all our experiments, the ground truth is obtained by running an existing per- instance estimator for large number of samples, and we use enough samples to ensure that it has approximately converged the exact result. For the Shapley value feature attribution experiments, we run KemneSHHAP for 1M samples. For Banzhaf values, we run the MSR estimator for IM samples. For LIME, we run the least squares estimator for 1M samples. For the data valuation experiments, we run the Monte Carlo estimator for 10K samples. These estimators are costly to run for large number of samples, so we do so for only small portion of the dataset: we calculate the ground truth for 100 examples for the feature attribution experiments. For the data valuation experiments, use 250 examples for the tabular datasets and 500 for CIFAR-10.
Metrics. The performance metrics used throughout our experiments are related to the estimation accuracy, which we evaluate using our ground truth values. Other works have evaluated Shapley value feature attributions against other methods [50, 18] or used data valuation scores in range of downstream tasks [53], but our focus is on efficient and accurate estimation. For the feature attribution experiments, we used the squared error distance, which we calculate across all attributions; we used Pearson and Spearman correlation, which are calculated individually for each flattened vector of attribution scores and then averaged across data points; and we used sign agreement, which is averaged across all attributions. For the data valuation experiments, we used squared error distance, which we normalized so the mean ground truth valuation score has error equal to 1 (i.e., we report the error divided by the variance in ground truth scores); and we used Pearson correlation, Spearman correlation and sign agreement, which were calculated using the vectors of estimated and ground truth valuation scores.
Datasets. We used publicly available. open-source datasets for our experiments. For the feature attribution experiments, we used the ImageNette dataset, natural image dataset consisting of ten ImageNet classes [46, 23]. We partitioned the 224 x 224 inputs into 196 patches of size 14 x 14, and the dataset was split into a training set with 9469 examples, validation set with 1962 examples, and test set with 1963 examples. The validation set was used to perform early stopping, and the test set was only used to evaluate the model's performance on external data.
For the data valuation experiments, we used two tabular datasets from the UCI repository: the MiniBooNE particle classification dataset [84] and the adult census income classification dataset [25]. We obtained these using the OpenData Val package [53], we used variable numbers of training examples ranging from 250 10K, and we reserved 100 examples for validation in each case; these examples are only used to evaluate the performance of models trained on subsampled datasets. We also used OpenDataVar Val to add label noise to 20% of the training examples. For CIFAR-10, we used 50K examples for training and IK for validation. We tested multiple levels of label noise for CIFAR-10 10 (Appendix G.3), and our main text results use 10% label noise.
Compute resources. For the feature attribution experiments, we used a single GeForce RTX 2080Ti GPU to train the amortized models. Training an amortized model on ImageNette dataset for 50 epochs required roughly 4 hours. For the data valuation experiments, we used a single RTX A6000 to train amortized models, and these each trained in under an hour.
FLOPs profiling. When profiling compute for our feature attribution experiments (see Figure 3), we first measured the following constants using the DeepSpeed FLOPSs profiler, all using the ViT-Base architecture:
The classifier's forward pass requires 17,563,067,904 FLOPs 17.6 GFLOPs per prediction.
The amortized model's 's forward pass requires 21,335, 15335,153,664 FLOPs x 21.3 GFLOPs per prediction, due to the model having an extra transformer block for fine-tuning.
The amortized model has 104,730,000 ss 105M trainable parameters.
32

---

Next. for the FLOPs comparison shown in Figure 3 we calculated total FLOPs for the two approaches as follows. For KernelSHAP, the total FLOPs 17.6 GFLOPs x (number of subset samples) x (number of training datapoints). For the amortized models, the total FLOPSs are the sum of multiple terms:
1. FLOPs for obtaining noisy labels 17.6 GFLOPs (number of subset samples) x (number of training datapoints)
2. FLOPs for the forward pass during training = 21.3 GFLOPs x (number of epochs) x (number of training datapoints)
3. FLOPs for the backward pass during training 21.3 GFLOPs x 2 x (number of epochs) x (number of training datapoints), where is standard multiplier for calculating FLOPs during the backward pass
4. FLOPs for updating parameters 105 MFLOPs x (number of epochs) x (number of training datapoints) (batch size) 19, where 19 is due to the optimizer state
In the calculation above, 1) dominates due the large number of subset samples used for each datapoint (e.g., >512 for KemelSHAP), Mcanwhile, the training epochs in 2), 3) and 4) are relatively low due to our models' fast convergence (<25 epochs). In the FLOPs calculation above, training an amortized model for one epoch is equivalent to obtaining predictions for roughly 3.65 additional subset samples per training datapoint. This is because (3 21, 1,33,1155 153, 664 + 104,730,000 x 19/64)/17 17,5633001 .904 x 3.65. In other words, the amount of compute for training an amortized model for up datapoint, which is not enough to meaningfully improve the estimates by running KerneISHAP for more iterations. This explains why the lines for amortized models appear almost vertical Figure when we compared amortization to KemnelSHA. Our procedure for calculating FLOPs is similar to other works that profile computation when training neural networks."
epochs translates to obtaining predictions for just 182.5 subset samples per
We consulted the following resources: (i) ttttttt::/www http:///www......ooooooooooooo// hotp:/o/ee///////004444/00
how-ta to- s- fetasurr--ppppsssf-oooaaaaaaeeee
(ii) http:://ww.eessvrnn.,
posts/fn http://wwwwwccccs..oooo//aaa/a/a https///wwwa.ceeeeoo/////ttttrta htw.::/oooooo.ooooooooooooaaaaaa
and (iii) https: ////////ww /wwww ada.casson
33

---

G
Additional Results
This section provides additional experimental results involving Shapley value feature attributions (Appendix G.I,, Banzhaf value and LIME feature attributions (Appendix G.2), and data valuation (Appendix G.3).
G.1 Shapley value amortization
First, Figure 6 shows that the performance of our amortized models is comparable running KernelSHAP for 10-40k samples. For example, an amortized model trained on noisy KernelSHAP labels generated with 512 samples produces outputs of similar quality running KemelSHHA for about 20k samples in terms of MSE, which is equivalent to a speedup of roughly 40x.
Enor
Commlstion
Rank comsiation
10
1.2
1.0
1.0
2048
1924
Cunsizoon
3072
2
10"
0.2
0.0
0.0
$0,000
50:030
50,000
150,00
50 820
(KemetSHAA))
/Serppes: (KarrestshM)))
Figure 6: Comparison of the estimation accuracy between KernelSHAP and amortized predictions.
Next, Figure 7 shows an expanded version of Figure (right) from the main text, where we compare amortization to per-instance estimation given a fixed amount of compute per data point. We observe that across four metrics, amortization provides a benefit over KernelSHAP even when training with small portion of the ImageNette dataset.
Ert
Conoladon
Rank Conclatin
Sig Agroement
1.0
3.0
0.0
0.0
Kenediie
0
4.4
04
10' TTiiking Daraoo ris (Amorizzed
1200
2000
2000
4000
5000
1000
2300
3000
4003
5003
1000
2000
3000
4000
5000
&Traning Datapok-te its (Amortzod)
.Triiiing Dacapiins (Aasoriized)
#Taoiiing Datopoints (Amoriize))
Figure 7: Estimation accuracy for amortization and KernelSHAP with different dataset sizes given
equivalent compute.
Figure 8 shows a similar result, but the amortized model's performance is evaluated with external data points (i.e., points that are not seen during training). The benefits of amortization remain significant for most dataset sizes, reflecting that the model generalizes beyond the training data and can be used for real-time feature attribution with new examples.
Er
Comcladoo
Rank Concution
Sign Agrccment
1.6
1.
1.0
Amerize
0.B
0.6
0/6
Emme
0.2
0.6
0.5
1202 2000
2000
4003
2030
1000
2033
2000
1000
5003
-100
2000
3000
4000
2000
Training Datasonts (f
4 Traiking Dalapoirss (alapirrs/Anooiiii (Aror
2 TTraring Datapo ria (Amnoriau))
A ATroning Dakapoinss (Amorizzd)
Figure 8: Estimation accuracy for amortization and KernelSHAP with different dataset sizes given
equivalent compute (external data points).
Figure 9 shows an expanded version of Figure (center) where we can see the benefits of amortization across multiple numbers of KemelSHHA samples when we account for the number of FLOPs.
34

---

Brorr
Commistion
Park Connebtiion
SignAgwmeer
1.0
Pospon Oarearon
05
0.3
76
Stp Agteeeeeee
E/
05
2.5
16
04
1.4
1I24
2048
2372
16
Kar Sernermi
167
12"
30"
FLOPS
RLOPs
FLOPs
FLOPs
Figure 9: Error of amortization and KerneISHAP as a function of FLOPs.
Figure 10 shows an expanded version of Figure 3, where we can see the benefits of amortization for KernelSHAP and permutation sampling across four metrics. We also see that SGD-Shapley does not lead to successful amortization, because the predictions are worse than the noisy labels across all four metrics. This is perhaps surprising, because Figure 11 shows that SGD-Shapley has the lowest squared error among the three noisy oracles. The crucial issue with SGD-Shaphe is that its estimates are not unbiased (see Section 3), an issue that has been shown in prior work [10].
Erron BHAP
Cormistion (HAP
Park Conseaatin (Mer HAP
5kg Agrestmnnt (KarelSHPP))
10'
1.0
Car: 3.2tel
0.0
Srontabe)
0.0
0.0
04
0.4
10
0.2
10
0.0
10"
12'
03
0.3
1.0
0.
06
0.2
04
Erer (Prwtizton)
Con: (Pred elor)
Sacarnan Con, (Prekttoor)
Aggteeet (Preditton)
Eroor (Porrutat on Bampl rg)
Conolation CarokaionPPumuaaae (Pamutationn Bampknn)
Rank Corrulation (Pormuationn Bamsling
Bign Agroement (Pemuraioon Sump ingl
Spsemen Can: (L.E4)
Stw (L044)
10"
1:35
952
648
1176
10"
10"
03
0.2
0.4
0.5
033
1.0
0.0
0.2
0.4
05
05
1.0
0.0
0.2
54
0,6
0.0
10
Enor (Prodicton)
Pharson Con: (Pred clor)
Spearman Con (Prckktoon)
5
ggnnggeement (Prukiloor)
Ernoe (50D-Sbxxlle)
Commbrion (SGD-Glussle)
Rank Carw on (5G2-Shies
Sign Agreament (RCD-Snapieg)
10
5.0
Paennsn Con LLbbe
Speamun Cur: (Labol)
0.6
Enw Lardl
101
0.6
04
0.2
9495
10
0.4 0.4
0.4
Enor (Prodictio)
Plarson Conr. (Pred clor)
Spcarman Cort (Pruckstio))
8 Sgg.Agtemmet (Prudistion)
Figure 10: Comparison of the estimation error between noisy labels and amortized predictions for Shapley value feature attributions. Top: noisy labels generated using KernelSHAP with different numbers of samples. Middle: noisy labels generated using permutation sampling with different numbers of samples. Bottom: noisy labels generated using SGD-Shaple with different numbers of samples.
Figure 12 is similar to Figure 10, only the performance metrics are calculated using external points not seen during training. Like Figure 12, this result emphasizes that the amortized attribution model generalizes well and can be reliably used with new data points.
35

---

Eirr
Commattioon
Rank commirtooo
Sign Agrnnerre
KamelWWP
1.0
10
Pemmaation
Sheakly
08
Spurman Conwaatinn
03
00gn Agw.ggeennt
2.6
00
1530
2003
1000 1503
1200
1907
2000
3000
3000
Figure 11: Comparison of the estimation error between different per-example estimators for Shapley value feature attributions across varying numbers of samples.
Bror (KAM)
Comneetion (KmmSSHAP)
Rank Compaaion (4 KemneSSMPP
Sig Agreement (amelSHMP)
Deevenn Coe: (E.04))
Con (Labb0
Ersl (aake)
T0"1
10"1
5:2
10
03
0.2
0d
84
1.
0.0
022
0.4
04
08
5.0
0.0
6.2
6.4
0.6
0.5
18
Ercr (Prediztonn
Pharaon Con: (Pred dlor)
Spserre man Con (Pracidtor)
Sig.Apreemerr (Predicior)
Emor (Pormutat Bumpling ngl
Comreation PPatmutation Bamping)
Rani Correlation (Pemmattion Sampling
Sign Agreement (Pemmration Samp
10
Pettenn Con (bace))
Spuerman Con S.4b0)
1TV 3.100)
1077
145
322
533
1175
08
84
1.0
0.4
04
08
0.0
0.2
64
0.6
0.8
(Pradizton)
Pearson Con: clon)
Spcarnan Con: (Preckator)
5 Agreemee (Predidton)
(SGD-Shacke))
Conulatoon (SCD-Bhapke)
(800-
AgrrsaemettBB0 Snaples!
107
1.0
1.0
Paanee Coe (Lack)
2.8
Spaanrr S.4ke)
0.5
0.0
BrorLabo)
0.6
0.0
244
0.4
0.4
0.2
10
0.0
10"
Emer (Prdtition)
(Pred
Con (Preckston))
SignAgreeent: (Prediston)
Figure 12: Comparison of the estimation error between noisy labels and amortized predictions for Shapley value feature attributions (external data points). Top: noisy labels generated using KernelSHAP with different numbers of samples. Middle: noisy labels generated using permutation sampling with different numbers of samples. Bottom: noisy labels generated using SGD-Shapley with different numbers of samples.
36

---

Finally, Figure 13 provides comparison between stochastic amortization and FastSHAP [50, 18], one of the main existing approaches amortized Shapley value estimation. For stochastic amortization, we use our previous results with permutation sampling as the noisy oracle and five different numbers of samples. For FastSHAP, we train the same ViT-Base architecture following the approach from Covert et al. [18), using 32 subset samples per gradient step. We monitor FastSHAP's estimation accuracy at the end of each epoch while training for a total of 100 epochs. We observe that FastSHAP and stochastic amortization achieve similar error at each total FLOPs budget, where both methods incur FLOPs from training the amortized model, stochastic amortization incurs FLOPs upfront when generating noisy labels, and FastSHAP incurs FLOPs during training while sampling subsets for each gradient step. FastSHAP is slightly more accurate at the largest computational budget, and both significantly more accurate than per-sample estimation with KemelSHAP. Due to their similar performance, the main advantage of our approach is its simplicity (a standard regression objective rather than the custom HAPtSHAP objective), and the flexibility noisy oracle; future work may find that stochastic amortization is more effective with other noisy oracles that we did not try here.
any unbiased estimator the
Error
10
10
Error
10
Amortized (196)
Amortized (3136)
Amortized (392)
KemelSHAP
Amorized (588)
FastSHAP
Amorized (1178)
10 16
10"
10
FLOPs
Figure 13: Comparison between stochastic amortization, FastSHAP and KerneSHHAP as a function of total FLOPs.
37

---

G.2 Banzhaf value and LIME amortization
As we discussed in Section 4.2, Banzhaf value and LIME feature attributions are two XML tasks closely related to Shapley values that can be amortized in similar fashion. Both are intractable to calculate exactly, but they have (approximately) unbiased estimators that can be used as noisy labels for stochastic amortization. Appendix E describes these estimators, namely the MSR estimator for Banzhaf values [103] and the least squares estimator for LIME [83]. Prior work has also shown that these approaches generate similar outputs [66], although the standard computational approaches are quite different.
In amortizing these methods, one trend we observed is that Banzhaf value and LIME feature attri- butions have a very different scale from Shapley values. Figure 14 shows that they not only have smaller norm, but that the distribution is concentrated at small magnitudes with long tail of larger magnitudes. This is troublesome, because our theory focused on the squared error ||a[b; 0) a(b)]? (see Section 3), which is dominated by the small number of examples with large magnitudes. As a result, an amortized attribution model can appear to train well by accurately estimating attributions with large norm, and predicting the remaining attributions to be roughly zero; in doing so it may fail to provide the correct relative feature ordering for most examples, which is more important for practical usage of feature attributions.
Shapley values
Banchal values
LINE
80
80
20
60
80
Coumt
10
0.10
0.15
0.35
0.00
0.10
0.15
0.20
0.00
0.10
no
nom
nom
Figure 14: Comparison of the distribution of norms between different feature attribution methods. We plotted the L2 norm of the 100 ground truths for each feature attribution.
The issue described above is precisely what occurs when we amortize Banzhaf value feature attribu- tions, shown in the top of Figure 15. We observe that the squared error from our predictions is lower than that of the noisy labels, which is consistent with our theory from Section 3 and our results for Shapley values (Appendix G. However, the amortized estimates perform worse than the noisy labels on the remaining metrics, particularly for the correlation scores that evaluate the relative feature ordering in each example's 's attributions (see details for the metrics in Appendix F).
To alleviate this issue, we experimented with a per-label normalization that eliminates the long tail of large attribution norms that dominate training: simply normalized each example's 's attributions for each class to have a norm of 1. The results are shown in the bottom row of Figure 15, where we see that the predictions have higher correlation scores than the noisy labels. The squared error is higher for the amortized predictions, and the sign agreement is roughly the same. One issue with this heuristic is that the normalized noisy labels are biased: the normalized noisy label is not an unbiased estimator of the normalized exact label, because the normalization constant is not known priori and must be calculated using the noisy label. However, the results show that amortization can to some extent denoise inexact labels even with this non-zero bias.
Figure 16 shows similar results as Figure 15 but with LIME feature attributions. We observe the same improvement in squared error from amortization, and a similar degradation in the correlation metrics (Figure 16 top). We then apply the same lar-label normalization trick, and we observe similar modest improvement in the correlation metrics, at least for noisier settings of the least squares estimator (Figure 16 bottom).
Overall, these results show that for the purpose of amortization, the consistency in scale of Shapley values is an unexpected advantage over Banzhaf values and LIME. This property is due in part to the Shapley value's efficiency axiom [89], which guarantees that the Shapley values sum to the difference between the prediction with all features and no features [68]. In comparison, LIME and Banzhaf values focus on marginal contributions involving roughly half of the features, which many cases near zero when the prediction is saturated; for example, previous works have observed that for
38

---

Brrer
Commistin
Bark Commetiin
Agueerrett
1.0
10'
Paenon Con (.4044
Sparmnn Cun: (Lazee)
0.8
Eiw (La546
10"
0.6
76
04
0.4
10
100
0.2
200
16
tn"
Emor (Prodiction)
Pearson Con: (Pred clon)
Spcarman Cort (Prccktioo)
ggn.Atremmnt (Prudittio))
Ing)
(Pa-lattel ngaling)
(Pwed Scoling)
Agrearment (Perd Scaling)
10
10
1.0
1.0
10'
Pharmen Car: (Label)
2.8
Speamar Cant (Lave)
0.8
0.0
End (1800
10"
0.6
42.4
94
0.4
10
16"
02
0.2
16a
0.
0.0
0.0
10"
14th Entr (Predidian)
10"
(Prod clar))
(Prckktiar)
SgnnAgtemmer: (Piudision)
Figure 15: Comparison of the estimation error between noisy labels and amortized predictions for Banzhaf value feature attributions. Noisy labels were generated using the MSR estimator with different numbers of samples. Top: using raw estimates as noisy training labels. Bottom: normalizing each noisy training label separately to have unit norm for each class.
natural images containing relatively large objects, a large portion of the patches must be removed before we observe significant changes in the prediction [48, 18].
Eror
Corrlattoo
10
10
10
1.0
16"
Phanco Con (LMBAT
4.8
0.5
0.5
Ero (La24)
10"
12.
0.5
0.6
16"
12.
0.4
0.4
16
295
02
02
0.2
512
16"
0.
0.0
0.0
10
10"
12
10'
Emor (Prodictio))
Pwerson Con: (Pred clon)
Speartor Com (Preckdior)
AggnAgeeeee (Preckstio)
Enor jleeiaae Scstngg
Corneeeton (ThesLatel niaiing
Dank Commlation (Pendabell Bexting)
Sign Agpeemmnt (Pen-aaea racel Scaling)
16
16
Tharont Con (1M004))
2.8
Spaamen Can: (Lavel)
0.
0.5
D/0 (L224)
10
0
0.6
10
1444
44
0.4
10
0.2
10
0.0
10
12 Emor (Prodiatio))
10.
15"
10'
0.8
1.0
0.5 0.8
0.2
0.4
son Cotr (Pred edor))
Bocorman Con, (Prdditioo)
SggnAtttmmnt: (Prudittio))
Figure 16: Comparison of the estimation error between noisy labels and amortized predictions for LIME feature attributions. Noisy labels were generated using LIME's least squares estimator with different numbers of samples. Top: using raw estimates noisy training labels. Bottom: normalizing each noisy training label separately to have unit norm for each class.
39

---

G.3
Data valuation
For the data valuation experiments, our first additional result compares amortization to the Monte Carlo estimator when using the MiniBooNE and adult datasets with different numbers of data points. The results are shown in Figure 17 and Figure 18, where we use datasets ranging from 1K to 10K points, and we see that the benefits of amortization increase with the size of the dataset.
Sign
Morte Cafb
Arne Rood
Souatter Condarker
0.7
10-1
310 Sumpriss 7aint
103
3.00
152
240
220
50
365
220
250
200
# P.Seplica iPaint
-Sampll PNert Phirt
# -Sumplis Pain:
Cormeasiin
Sign
1.0
Monts Cafo Arterkood
Conteeson
Spautron Cotolaiion
183
350
200
250
50
160
230
350
200
Sumppes cs Point
SSampii Paint
Paint
0 /Samples Falm
Meste Call
Arto Bood
Stuaman 04 Corro Madi
1.5
D10r
10-1
0.
8
23
103
150
200
250
162
150
SSarppe et/ Point
SSamptes/ Partt
SSrpplee Poitt
# .Samplee/ Faim
wadion
Comdation
Agreemert
Henta Caro
Attntbedd
Sparmen OUT 4Mp
Enet
0.6
153 SSarpees/ Point
200
Paart
.Sanples, Partt
*Songlees Pain
Figure 17: Amortized data valuation for the MiniBooNE dataset with different numbers of training data points (1K to 10K). We show four metrics: squared error (normalized that the mean valuation scores has error equal to 1), Pearson correlation, Spearman correlation, and sign agreement.
40

---

Moeta Cafo
1.93
350
150
200
250
50
365
230
150
200
Sampres PaRK
SSmmlles Phant
53mmales Partt
-Sorpliss Paint
2503
Conmivttio
2530 Rank Cormecttoo
J-LBB
Morte Cafo
1por maT Dandattar
2101
1.55
2
350 Sumpres / Tarn
1.0
3.00
152
200
220
50
300
150 # -Supliia Poin:
220
S.mplica Phant
Samaala Phint
Camedodin
Adullt
Modte Cafs
Arrar Rtnd
51000 man Condoceen
183
350
158
260
250
100
220
150
200
Sampres Print
SSameles/Pa Point
-aamples Paint
3 "Sarplies Paint
Modte cath
Sccurtea Cindriin
& 2 &
2 &
14
103
150
152
200
150
Sumprss / TURK.
Sampaas Phint
Sumplica Pain:
Figure 18: Amortized data valuation for the adult dataset with different numbers training data points (1K to 10K). We show four metrics: squared error (normalized so that the mean valuation scores has error equal to 1), Pearson correlation, Spearman correlation, and sign agreement.
41

---

CINIL Dr
CPAR 32 Condition
CPAI 52 Pank dtinn
CPAI 12 Sign Agrsomont
Maria Carlo Aeavitive
POYOO Condsation
Spea TOAATTEET ClRr
Sompres, PORT
Samples/Pentt
-Sorpptes /Poin
"Samples//20 PONC
Figure 19:
Distributional data valuation for CIFAR-I0 with 50K data points. We generate Monte Carlo estimates and amortized estimates with different numbers of samples per data point, and the scores are compared to ground truth values using four metrics.
We also provide more detailed performance metrics for CIFAR-10: Figure 19 shows an expanded version of Figure 5, and we observe that amortization improves upon the Monte Carlo estimator across all four performance metrics.
Next, consider the of CIFAR-10 data valuation scores in two downstream tasks. First, attempt to identify mislabeled examples, which we expect should have large negative valuation scores. Figure 20 shows how quickly each method identifies negative examples when we sort the scores from lowest to highest: our amortized estimates that train with just samples provide the highest accuracy, outperforming Monte Carlo estimates that as many as 100 samples. This result is consistent across different levels of label noise, where we randomly flip either 10%, 25% or 50% of the labels.
Table 2 performs similar analysis involving mislabeled examples: we expect these examples to have lower scores than correctly labeled examples, so we use the estimated scores to calculate the AUROC, the AUPR, and the portion of mislabeled examples with negative scores. Across the different levels of label noise, our amortized estimates achieve the best performance according to all three metrics. The strong performance of our amortized data valuation scores is largely due to the improved estimation accuracy, but we expect that it is also due to the valuation network being trained on raw images: the noisy labels are derived from training logistic regression models on pretrained ResNet-50 embeddings, which can lead to somewhat arbitrary valuation score differences between semantically similar examples, and the valuation network may learn more generalizable notion of data value.
Mescl
55% hoiso
1000
12028
25:03
+4000oree Cusmple
4000
10022
Woand (5
6032
2000
Mesto Carlo
10303
3000
Meite
Ments Carb (32)
2012
5202
Mente Caro (133)
0
2000
10000
15000
20000
25800
22.00
10000
31000
20302
25230
5000
10303 Doommieee identitte
150300 20000
200ce
Ccarrpies Stenitted
Ccamplle Ideriifiec
Figure 20: CIFAR- mislabeled example identification with different amounts of label noise. We compare the number of mislabeled examples among the lowest-scoring data points, where the amortized model uses just samples for training and the Monte Carlo estimator uses between 5 and 100 samples.
Table 2: Mislabeled example identification accuracy for CIFAR-10 with different amounts of label noise.
10% Noise
25% Noisc
50% Noise
AUROC
AUPRC
Negative
AUROC
AUPRC
Negative
AUROC
AUPRC
Negative
Amortized (5)
0
0.917
0.974
0.985
0.964
0.973
0.972
0.973
0.915
Monte Carlo
0,515
0.802
0.687
0.758
0.815
0.829
0.708
Monte Curlo (10)
0.844
0.619
0.826
0.867
0.784
0.821
0.883
0.892
0.769
Monte Carlo (25)
0.906
0.738
0.931
0.888
0.943
0.947
Monte Carlo (50)
0.934
0.794
0.909
0.956
0.918
0.918
0.965
0.967
0,878
Monte Carlo (100)
0.941
0.808
0.918
0.960
0.923
0.922
0.965
0.967
0.878
42

---

Finally, we experiment with using the data valuation scores to improve the dataset. Using the version with 25% label noise, we experiment with several possible modifications to the dataset, where in each case we train 5 models and report the mean cross entropy loss. First, we consider perfect filtering of the data where we remove all mislabeled examples. Next, we remove different numbers of examples chosen uniformly at random. We also consider removing the examples with the lowest scores according to the Monte Carlo estimates with 10 samples. Finally, we test two possible approaches based on the amortized valuation model: (i) filter out the lowest scoring examples ("Amortized filtering"), similar to how we use the noisy Monte Carlo estimates; (ii) we attempt to correct the lowest scoring examples using the class that the valuation model predicts to be most valuable (" ("Amortized cleaning"), ") which is a unique capability enabled by our valuation model that predicts valuation scores simultancously for all possible classes (see Appendix F). The results of this experiment are shown in Figure 21. We see that removing samples at random hurts the model's performance relative to using all the data, that filtering with the amortized estimates outperforms filtering with the Monte Carlo estimates, and that cleaning the estimates is the best approach by a narrow margin.
CIFAR-10 Performance (25% Noise)
0.60
0.55
0.50
Log
0.45
Monte Carlo 110)
Peact filtering
Amertized filtaring
Random
Amortized cleaning
38000
40000
42000
44000
45000
48000
50000
Dalapoints
Figure 21: CIFAR-10 performance when training data is removed or adjusted based on estimated valuation scores.
H Broader Impact
Our proposed method aims to make many computationally challenging XML tasks feasible and scalable to large datasets. We expect our research to contribute to a better understanding of MI. models, enhancing their transparency and explainability. Additionally, our research could help understand model fairness properties if our method is used to identify undesirable or unfair dependencies of ML models on input features related to protected attributes like race or gender. The potential downside is that that if users overly trust our method and rely solely on it for these tasks without careful usage, it could lead to misunderstanding of models and result in harmful outcomes.
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our claim made in the abstract and introduction is that training amortized models with unbiased noisy oracles is effective and provides significant speed-ups for various XML tasks. This is supported by theoretical and experimental results in Section 3, Section and Section 5.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations of our work are discussed in Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
44

---

Answer:
[Yes]
Justification:
The proofs for all theoretical results are provided in Appendix D.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The details for reproducing the experimental results described in Section 5 and Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
45

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Links code are provided in the paper. Our experiments only open-source software and datasets, all of which are referenced in the text.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cr
wwtemmiissssooliiiioiooo onPolicy) icy for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /nips. cc/public//pe hwtpc//gggge//eeeeeeeeeeeeeeeeee /Cods//dmdSsbmii sswssssssssiiiiooeo
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details of the experimental settings are discussed in Section and Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We performed experiments across multiple XML tasks, noisy oracles, noise levels, model architectures, and datasets, so performing multiple runs for each experiment would be too computationally expensive.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
46

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Information on compute resources is provided in Appendix F,
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https /tte:r//neerrieee Doppbiic/thicshuideee.....
Answer: [Yes]
Justification: Our proposed method aims to make computationally challenging XML tasks feasible, so research promotes transparency and interpretability ML.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: The potential positive and negative societal impacts of our work are discussed in Appendix H.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
47

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Our paper does not release a new dataset or model.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The open-source packages and datasets we used are cited in Appendix F,
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
48

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. www.coo//aaooooo datasttss has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
The code we provide contains usage instructions and scripts for running experiments.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing experiments research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
49

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
50


Reviews:
[{"review_id": "5kbf4yOuVD", "reviewer": "Reviewer_GyYk", "summary": "This paper proposes a stochastic amortization framework for efficiently estimating feature attribution and data attribution values. The idea is to learn a parameterized model from noisy while unbiased samples of the value to be estimated. In comparison to naive Monte Carlo sampling, this amortized estimation is empirically more efficient when achieving similar estimation accuracy. The authors conducted experiments on a diverse set of feature attribution and data attribution problems.", "questions": "See Weaknesses.", "limitations": "None.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper tackles the computational efficiency issue in a set of feature attribution and data attribution problems, which is an important problem that could have significant impact to the area of explainable machine learning (XML).\n- This paper abstracts the paradigm of learning a parameterized function to estimate the attribution values in some XML methods with a more general amortized estimation framework, making it possible to extend this approach to more XML methods that conventionally rely on naive Monte Carlo estimators.\n- The authors conducted comprehensive experiments in diverse settings to demonstrate the effectiveness of the stochastic amortization.", "weaknesses": "- The theoretical analysis, especially Theorem 1, is not directly relevant to the main argument of this paper, i.e., stochastic amortization is more efficient than naive Monte Carlo. IMO this Theorem 1 is a bit distracting than being helpful for this paper. Furthermore, the theoretical result about the unbiasedness in lines 128 - 132 only concerns the expected loss, $\\tilde{\\mathcal{L}}_{reg}$, which doesn't directly imply the property of the empirically learned parameterized model. Overall, the advantage of stochastic amortization over Monte Carlo estimation is established empirically instead of theoretically, while the current presentation reads a bit misleading on this point.\n- In most of the experiments, only relatively naive Monte Carlo estimators compared as baselines. However, for certain specific problems, more efficient estimators may be available. For example, in the context of Data Shapley, how does the stochastic amortization compare with Gradient Shapley proposed in Ghorbani and Zou [33], or the compressive-sensing-based method proposed in Jia et al. (2019).\n\nReferences\n- Jia et al. (2019) Towards Efficient Data Valuation Based on the Shapley Value. AISTATS 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, we've responded to your points below.\n\n> The theoretical analysis, especially Theorem 1, is not directly relevant to the main argument of this paper, i.e., stochastic amortization is more efficient than naive Monte Carlo.\n\nThanks for bringing up this concern. To clarify, Theorem 1 shows that when training the amortized model $a(b; \\theta)$ with SGD and noisy labels $\\tilde a(b)$, the convergence rate is affected by label noise via $\\text{N}_q(\\tilde a)$. This means that noisier labels make training slower, which is an important theoretical point to understand about stochastic amortization: label noise is the key difference between stochastic amortization and the noiseless version, so it seems important to include Theorem 1 and highlight its role in slowing optimization.\n\nHowever, you’re correct that Theorem 1 doesn’t consider the stochastic amortization vs. Monte Carlo comparison. We found that harder to characterize in a satisfactory way and therefore relied on empirical results. But just to show that it’s possible, here’s a result that follows from Theorem 1 and demonstrates the advantage of sharing information across data points (as compared to Monte Carlo estimation, which treats each point independently):\n\nWhen we take $T$ SGD steps to update the amortized model, Theorem 1 shows that the estimation error shrinks at a rate of $\\mathcal{O}(1/T)$. If we instead used the exact same training labels $\\tilde a(b)$ as one-sample Monte Carlo estimates for each training data point $b$, our expected error across those would be $\\text{N}_p(\\tilde a)$ (this is a quick result to show). Crucially, this error does not shrink with $T$, as we just obtain (bad) estimates for more data points. So, we can see that for a sufficient number of gradient steps $T$, which depends on the label noise and data distribution, our error from the amortized model will eventually become lower than the error from the single-sample Monte Carlo estimates. And notably, the model can be used to generate estimates for any data point $b$ rather than only the fixed set of training data points. Hopefully this helps clarify the advantage of amortization over per-example Monte Carlo estimation. We’re happy to add the result to the paper, but we think the empirical results are most convincing for this point.\n\n> Furthermore, the theoretical result about the unbiasedness in lines 128 - 132 only concerns the expected loss, $\\tilde{\\mathcal{L}}_{\\text{reg}}(\\theta)$, which doesn't directly imply the property of the empirically learned parameterized model.\n\nThanks for pointing this out. Your concern seems to be that our theoretical results don’t address the generalization gap between the empirical and population version of $\\tilde{\\mathcal{L}}_{\\text{reg}}(\\theta)$. That’s correct, but if you’re concerned about a large generalization gap in practice, generalization is famously not much of an issue with deep learning (https://arxiv.org/abs/1611.03530). We use standard approaches like a validation set to avoid overfitting, and some existing theoretical results also apply here (https://arxiv.org/abs/1901.08584). We can mention these points in the paper, but extending our theory to include the generalization gap doesn’t seem helpful given the technical complexity of the topic.\n\n> In most of the experiments, only relatively naive Monte Carlo estimators compared as baselines. [...] For example, in the context of Data Shapley, how does the stochastic amortization compare with Gradient Shapley proposed in Ghorbani and Zou [33], or the compressive-sensing-based method proposed in Jia et al. (2019).\n\nThanks for raising this point. We prioritized breadth of experiments across XML techniques rather than depth in a single one, and as a result we can’t explore the full range of Monte Carlo estimators. There are numerous choices for both data valuation and feature attribution, several of which are discussed in Section 4 and Appendix E; since our theory applies to any unbiased estimator, we can’t see a reason why other options wouldn’t work. However, the two techniques you mentioned are different because they’re both *biased estimators* (Gradient Shapley because it uses a cheap proxy for the marginal contribution, and Compressive Permutation because it relies on sparsity assumptions). Our work is focused primarily on unbiased estimators, so adding these doesn’t seem like a priority, but it could be an interesting topic for other work to explore. One immediate intuition for such work is that with these approaches, stochastic amortization would learn to predict the expectation of those biased estimators, which may or may not be close to the true Data Shapley values.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ah98ijRbZt", "reviewer": "Reviewer_x1Ww", "summary": "In this paper, the authors introduce a framework termed stochastic amortization that can accelerate computationally expensive explainable machine learning (XML) tasks by training models with noisy but unbiased labels. They provide theoretical analysis that shows that unbiased noisy labels allow learning the correct function. Empirically, the authors demonstrate the effectiveness of this approach on several XML tasks, including Shapley value feature attributions, Banzhaf values, LIME, and data valuation, achieving speedups over traditional per-example computation and improvements over simply using noisy labels.", "questions": "- For applying stochastic amortization to a new XML task, how should practitioners determine an appropriate error level from a practical perspective?\n- Regarding line 99, \"while there are works that accelerate data attribution with datamodels, we are not aware of any that use amortization\". Could datamodels themselves be considered a form of amortized optimization (linear regression model)?\n- What guidelines can you provide for defining the architecture for amortization (e.g., ResNet) in practice? Did you observe significant differences with various architectures? Should the architecture be similar to the base model?\n- In Figure 4 (right), why does the correlation decrease for MC as the number of data points increases (intuitively, I expected correlation to remain relatively flat for both MC and amortized approaches, assuming a constant number of samples per point)?", "limitations": "The authors adequately addressed the limitations of the proposed approach.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written, with clear motivations and a thorough discussion of related work. The technical details appear sound and well-presented.\n- The proposed approach offers a simple yet effective framework for accelerating computationally expensive XML methods, potentially enabling their application to large-scale datasets.\n- The authors provide code (with good documentation) and detailed experimental information in the Appendix for reproducability.\n- Limitations of the proposed approach are well discussed, demonstrating a balanced perspective.\n- Comprehensive experiments across multiple XML tasks (Shapley values, Banzhaf values, LIME, and data valuation) consistently demonstrate the benefits of stochastic amortization over per-example computation.", "weaknesses": "While the concept of amortization for Shapley value prediction is not entirely new, this paper makes a good contribution through its use of noisy labels and the accompanying theoretical analysis. I don't find any major weaknesses that would significantly detract from the paper's value, and I recommend acceptance. Reflecting my limited familiarity with some aspects of the relevant literature, I set my confidence to 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, we've responded to your points below.\n\n> For applying stochastic amortization to a new XML task, how should practitioners determine an appropriate error level from a practical perspective?\n\nThanks for asking this question. Our recommendation is to create a small validation set with near-exact estimates, for example by running a standard Monte Carlo estimate for many iterations, and then use this to determine what level of label noise achieves low enough error. This is how we evaluated estimation accuracy in our experiments. As for how to define “low enough error”, this depends on the task and its error tolerance, e.g., feature attribution can tolerate some error if its goal is to visually show humans the important part of an image.\n\n> Regarding line 99, \"while there are works that accelerate data attribution with datamodels, we are not aware of any that use amortization\". Could datamodels themselves be considered a form of amortized optimization (linear regression model)?\n\nThat’s a good question and one that we get a lot. Datamodels isn’t a form of amortization because it doesn’t learn a neural network that takes two data points as input and predicts the attribution score. It instead learns a linear model that takes a one-hot representation of the training dataset as the input, and predicts the loss for an inference example. The attribution scores are the learned coefficients of that model, not its predictions. Crucially, you can’t use the datamodels linear model to estimate attributions for new data points. Appendix B contains a brief discussion on how amortization would be implemented for datamodels, including a neural network $\\zeta(z, x; \\theta)$ whose output is the estimated attribution score.\n\n> What guidelines can you provide for defining the architecture for amortization (e.g., ResNet) in practice? Did you observe significant differences with various architectures? Should the architecture be similar to the base model?\n\nThat’s an interesting question. The best architecture for each problem is likely a function of how much expressive power you need and how much training data is available, similar to any setting where you use deep learning. Using the pre-trained base model is natural because it already extracts many relevant features, which can help with efficient fine-tuning, but it’s possible that in some cases you could benefit from a larger architecture or that you could get sufficient accuracy with a smaller one. In our experiments, we only tried training the base model architecture.\n\n> In Figure 4 (right), why does the correlation decrease for MC as the number of data points increases (intuitively, I expected correlation to remain relatively flat for both MC and amortized approaches, assuming a constant number of samples per point)?\n\nThis was somewhat surprising to us as well. We believe it’s because as you increase the size of the dataset, the variance of each data point’s marginal contributions becomes larger relative to the expectation (reflecting a lower signal-to-noise ratio), and this leads to decreasing correlation even with a fixed number of samples. This observation is related to, but not exactly the same as one in the Beta Shapley paper (see Figure 1 in https://arxiv.org/abs/2110.14049).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qiDQt5RLOS", "reviewer": "Reviewer_cihK", "summary": "This paper presents a fast prediction explanation approach for machine unlearning models that approximates traditional explanation approaches by using an neural network. The network is trained with noisy labels (so called stochastic amortization) such that it learns to approximate the prediction explanations of various approaches, including Shaply, LIME, and others. Experiments covers multiple explanation approaches from feature explanation to data instance explanation, showing effectiveness of the approximation.", "questions": "How do you prove the proposed approximation is, in general, faithful to the ground-truth explanation results from the actual explanation models? \nWhy would the proposed approach to be useful if the explanation is off from the ground-truth?", "limitations": "I don't see limitations. But, as the proposed approach is about XAI, it should be sound in terms of improving the trustworthiness of prediction instead of introducing another layer of uncertainty.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Using network to approximate prediction explanation of various explanation methods seem an interesting idea.\nUsing noisy labels to train the approximation model is also well justified with corresponding proofs. \nExperiments covers the various scenarios from feature to instance based explanation approaches.", "weaknesses": "It is concerning to use neural networks to explaining the predictive behaviour of another machine learning model. In fact, how do we know whether the explanation itself is trustworthy? If the prediction explanation is given to an stakeholders, is it possible to distinguish the potential concern between target machine learning model's trustworthiness and the approximative explainer? This concern needs to be addressed further to let the proposed approach practically useful.\n\nPartial experimental results show the proposed model may not be a good approximation approach; the results can be interpreted as the approximation fails to provide correct explanation to feature importance (Section 5.1). It causes me wonder if there is a practical value for the proposed approach if it is fast but not accurate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, we've responded to your points below.\n\n> It is concerning to use neural networks to explaining the predictive behaviour of another machine learning model. In fact, how do we know whether the explanation itself is trustworthy?\n\nThanks for raising this question—by “trustworthy”, we assume you’re asking how we know that the amortized estimates are accurate. Ensuring high accuracy is very important, and our theory and experiments are all about showing that the error from amortization is small despite training with noisy labels. You can see that across all our experiments, amortization is always more accurate than Monte Carlo estimation for an equal computational budget, in most cases by a wide margin. For example, Figure 3 shows that the error from amortization is 1-2 orders of magnitude smaller than the standard KernelSHAP approach. This high accuracy (low error) is what makes the explanations trustworthy.\n\nWe aren’t sure if this is what you meant, but you may be getting at the fact that our analysis focuses on average error across data points rather than worst-case error. Minimizing average-case error is useful in many scenarios, e.g., identifying mislabeled data points with data valuation scores, understanding a classifier by visually checking many feature attributions, and identifying common shortcuts/confounders. There’s an established literature on this type of approach, but there may be cases where Monte Carlo estimation with a large computational budget is preferable to provide guarantees for each data point's explanation.\n\n> Partial experimental results show the proposed model may not be a good approximation approach; the results can be interpreted as the approximation fails to provide correct explanation to feature importance (Section 5.1).\n\nWe aren’t sure what you mean and which of these results reflect that the approximation is inaccurate. The examples in Figure 2 are qualitatively quite accurate, and the metrics in Figure 3 show that amortization achieves significantly lower error than the non-amortized estimates. Note that some of the metrics are shown in log-scale, which may make the error appear far from zero when it’s actually quite small. If you’re expecting to see zero error, note that these XML methods are never used with zero error due to the high computational cost – the only option is to use approximations, that’s why there’s so much work on efficient approximation algorithms.\n\n> How do you prove the proposed approximation is, in general, faithful to the ground-truth explanation results from the actual explanation models? Why would the proposed approach to be useful if the explanation is off from the ground-truth?\n\nThanks for bringing this up. We establish the faithfulness of the approximation empirically: the estimation error is often small in our experiments, where we substitute the ground truth for estimates obtained using a large number of samples (e.g., 1M samples for KernelSHAP, see details in Appendix F). The error from amortization is always smaller than the Monte Carlo error given an equal computational budget, so our approach seems strictly preferable.\n\nThe proposed approach wouldn’t be useful if the explanation was significantly off from the ground truth. However, a small degree of error is generally tolerable in practice, as evidenced by the fact that the community relies entirely on approximation algorithms, which are rarely run long enough to reach exact convergence (see for example the number of samples in KernelSHAP https://github.com/shap/shap/blob/master/shap/explainers/_kernel.py#L192). Our focus on fast/accurate approximation is not unusual, it’s an established line of work in the literature.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pdlF8vc2ql", "reviewer": "Reviewer_hGpm", "summary": "The paper proposes using stochastic amortization to speed up feature attribution and data attribution. This is applicable when the attribution technique is expensive to compute exactly (e.g. LIME), and when unbiased estimators of the attributions exist. Specifically, the paper proposes to, for a given machine learning model (e.g. Resnet) and a dataset of inputs (e.g. cifar) on which we want to compute attribution (e.g. Shapley feature values), obtain noisy estimates of the attributions (e.g. by sampling permutations), and then train a least square regression model to predict these noisy estimates from the input. The paper evaluates this method against the ground-truth attribution values for Shapley values on Imagenette,  data valuation shapley on adult census and MiniBooNE datasets, and Distributional data valuation on the CIFAR-10 dataset.", "questions": "- S5.1: would be interested to look at fig 3 right with a log scale on the y axis. Amortization seems to benefit with increasing dataset size, and I wonder what the scaling looks like\n- Related to that, a key hyperparameter in your amortization set up is to choose between spending compute to get fewer but more accurate labels vs more noisy labels. Is there a way of determining an optimal trade-off?\n- How does the paper's method compare with prior works? This is a crux for me.", "limitations": "The authors adequately discussed technical limitations of their amortization approach in the appendix.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper clearly explains its motivations and approach\n- Using the amortized model improves performance over the initial noisy labels used for training, clearly showing the benefits of using an amortized method\n- The paper provides some theoretical arguments for using unbiased estimators.", "weaknesses": "- The related work section could benefit with a more direct and concrete comparison with prior work. For example, the paper says that \"while there are works that accelerate data attribution with datamodels, we are not aware of any that use amortization\". It is not clear to me in what \"amortization\" mean here exactly --- in what way does your work perform amortization that datamodels do not?\n- In addition, the experimental results lack baselines that compare with prior amortization work. The related work section describes a number of prior works (citations 50, 86, 18, 14) that all seem to be about computing Shapley values with amortization. \n- Figures are missing error bars", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review, we've responded to your points below.\n\n> The related work section could benefit with a more direct and concrete comparison with prior work. For example, the paper says that \"while there are works that accelerate data attribution with datamodels, we are not aware of any that use amortization\". It is not clear to me in what \"amortization\" mean here exactly --- in what way does your work perform amortization that datamodels do not?\n\nWe can clarify this in the paper, but datamodels isn’t a form of amortization because it doesn’t learn a neural network that takes two data points as input and predicts the attribution score. It instead learns a linear model that takes a one-hot representation of the training dataset as the input, and predicts the loss for an inference example. The attribution scores are the learned coefficients of that model, not its predictions. Crucially, you can’t use the datamodels linear model to estimate attributions for new data points. Appendix B contains a brief discussion on how amortization would be implemented for datamodels, including a neural network $\\zeta(z, x; \\theta)$ whose output is the estimated attribution score.\n\n> In addition, the experimental results lack baselines that compare with prior amortization work. The related work section describes a number of prior works (citations 50, 86, 18, 14) that all seem to be about computing Shapley values with amortization. [...] How does the paper's method compare with prior works? This is a crux for me\n\nThanks for this request, you raise a good point. There are fewer relevant comparisons than it might seem, but you’re correct that we missed the comparison with FastSHAP. We’ve now fixed this, as we describe below, and we can also clarify why certain other papers aren’t useful comparisons.\n\nFirst, we’ll address [86] and [14]. Setting aside some minor details, these are basically versions of stochastic amortization with much less noisy labels. They train explainer models to predict SVs using a supervised objective and targets computed with relatively high accuracy: [86] uses 10$\\times$ the number of samples we do, and [14] claims to use either exact labels or orders of magnitude more than us depending on the experiment. (Besides these details, [86] also includes an unnecessary normalization step and regularization term, and [14] suggests a custom pre-training approach, which is an orthogonal contribution.) Given that these are basically much less noisy versions of stochastic amortization, a direct comparison wouldn’t be very interesting: using more accurate labels will yield a more accurate explainer, but at the cost of much more computation. This type of comparison is already shown in our work (e.g., Figure 3 left), only we don’t use as many samples as those works even in our most compute-intensive settings. Our goal here was to explore the other direction and demonstrate the ability to use noisier supervision.\n\nNext, [50, 18] both explore SV amortization using a custom weighted least squares objective, which we’ll refer to as “FastSHAP.” The main differences from our approach are that FastSHAP uses new samples for every gradient step and requires a complex training procedure, whereas we use pre-computed noisy labels from any unbiased estimator and train with MSE loss. Notably, the FastSHAP explainer model *can’t make predictions without access to the original model’s predictions* due to an output transformation required by its objective (“additive efficient normalization” [18]). Our approach is simpler to train, more flexible in the supervision, and the explainer can operate as a standalone model.\n\nStill, it’s worth including the comparison. To provide a compute-matched comparison, we implemented FastSHAP and measured the error from each approach as a function of the total FLOPs (including the cost of querying the original model, plus the cost of training the amortized model), using 32 subset samples/step for FastSHAP as in [18]. We found that the error and correlation with the ground truth is very similar between FastSHAP and our approach, with both significantly more accurate than KernelSHAP, but that FastSHAP is marginally more accurate ([plot link](https://imgur.com/a/5oGOjTK)). The result doesn’t seem conclusive, however, because our approach can be implemented with any noisy oracle, including more advanced ones that we didn’t test here; future work testing other unbiased estimators could find that stochastic amortization is more accurate. Overall, we believe our work is still valuable in presenting a simpler/more flexible alternative that reaches basically the same accuracy, and which can be easily applied to other XML methods like data valuation.\n\n> Figures are missing error bars\n\nThanks for noticing this. We didn’t perform multiple trials due to the high computational cost, specifically the time required to run the Monte Carlo estimators for a small-to-moderate number of samples for all training data points. Given the wide margin of improvement we saw in the experiments (often an order of magnitude lower error), we didn’t think it would add much value to repeat the experiments multiple times. But we’ll try to fix this and prepare error bars in time for the final version of the paper.\n\n> S5.1: would be interested to look at fig 3 right with a log scale on the y axis. Amortization seems to benefit with increasing dataset size, and I wonder what the scaling looks like\n\nThat’s a good idea, we made a version of the plot with both axes shown in log-scale ([plot link](https://imgur.com/a/lWC1YPR)). We hoped to see a log-linear trendline, because this is similar to a Kaplan et al. (2020)-style scaling curve, and it’s close but not quite linear. The error for the smallest dataset size is a bit too high, perhaps because it’s the least reliable point. If it’s helpful, we can change the plot in the final version to use log-scale on both axes.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you to all reviewers for your detailed feedback. We have addressed your points in individual responses below. If you find that we have resolved your concerns, we would greatly appreciate it if you would consider revising your score.

Meta-review: The reviewers were generally positive, and the authors did a good job addressing their concerns during the response period. Please make sure that the changes you promised to the reviewers are incorporated into the current version of the paper.
Decision: Accept (poster)