Rescaled Influence Functions: Accurate Data Attribution in High Dimension
Authors: Ittai Rubinstein
Samuel B. Hopkins
Venue: NeurIPS 2025 poster ()
Keywords: data attribution
influence functions
high-dimensional models
overparameterized models
model interpretability
robustness
training data influence
rescaled influence functions
data poisoning detection
machine learning theory
Primary area: theory
TL;DR: We evaluate Rescaled Influence Functions (RIF), a fast and accurate alternative to traditional influence functions for data attribution, particularly effective in high-dimensional settings where standard influence methods fail.

Abstract: How does the training data affect a model's behavior?
This is the question we seek to answer with *data attribution*.
The leading practical approaches to data attribution are based on *influence functions* (IF).
IFs utilize a first-order Taylor approximation to efficiently predict the effect of removing a set of samples from the training set without retraining the model, and are used in a wide variety of machine learning applications.
However, especially in the high-dimensional regime (# params $\geq \Omega($# samples$)$), they are often imprecise and tend to underestimate the effect of sample removals, even for simple models such as logistic regression.
We present *rescaled influence functions* (RIF) -- a tool for data attribution which can be used as a drop-in replacement for influence functions, with little computational overhead but significant improvement in accuracy.
We compare IF and RIF on a range of real-world datasets, showing that RIFs offer significantly better predictions in practice, and present a theoretical analysis explaining this improvement.
Finally, we present a simple class of data poisoning attacks that would fool IF-based detections but would be detected by RIF.

Rescaled Influence Functions: Accurate Data
Attribution in High Dimension
Ittai Rubinstein EECS and CSAIL MIT
Samuel B. Hopkins EECS and CSAIL MIT Cambridge, MA samhop0mit, t. edu
Cambridge, MA ittair@mit.. edu
Abstract
How does the training data affect model's behavior? This is the question we seek to answer with data attribution. The leading practical approaches to data attribution are based on inffuence functions (IF). IFs utilize a first-order Taylor approximation efficiently predict the effect of removing set of samples from the training set without retraining the model, and are used in a wide variety of machine learning applications. However, especially in the high nigh-dimensional regime (# params > Q samples)). they are often imprecise and tend to underestimate the effect of sample removals, even for simple models such logistic regression. We present rescaled influence functions (RIF), a tool for data attribution which can be used as a drop- replacement for influence functions, with little computational overhead but significant improvement in accuracy. We compare IF and RIF on a range of real- world datasets, showing that RIFs offer significantly better predictions in practice, and present a theoretical analysis explaining this improvement. Finally, we present simple class of data poisoning attacks that would fool IF-based detections but would be detected by RIF.
Introduction
Data attribution aims to explain the behavior of a machine learning model in terms of its training data. If 0 is model trained on a dataset {(x;, ve))) the fundamental algorithmic task in data attribution is to answer the question:
Leave-T-Out Effect: How would 0 have been different if some subset T C [n] of the training set had been missing?
The ability to quickly and accurately predict a leave-T-out (LTO) effect, or to search for subsets producing large leave-out effect, unlocks extensive capabilities from classical statistical inference to modern machine learning. For example, the jackknife, leave-k-out cross-vale coos-validattion and bootstrap are all widely used to quantify uncertainty and estimate generalization rely on the ability to quickly estimate LTO effects [Efr92, GSL+ 19, Jae72]. Machine learning has seen an explosion of applications of data attribution, for dataset curation [KL17, KATLI9], explainability [KATL19, GBA+23), crafting and detection of data poisoning attacks [EIC- BBIC-25,5 KSL.2,, SS19], machine unlearning [SAKS2], GGHVDM19, IASCZ21], credit attribution [JDW + 19, GZ19], bias detection [BAHAZI9] and more.
confidence intervals, and all
Ascertaining the ground truth leave-T-out effect in general requires full retrain of model for each of interest, which is computationally intractable all but the simplest settings. Consequently, approximations to the leave-T-out effect are widely used. Key desiderata for such approximations
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

are (1) accuracy, (2) computational efficiency even for large-scale models, and (3) additivity the predicted effect of removing T should be the sum of predicted effects removing each element of T individually. Additivity enables another important capability: search for the subset 7 of a given size with the greatest predicted effect according to given metric, by taking the & training data points with largest predicted leave-one-out (LOO) effects [BGM20, IPE+22, 22, HBN 24]..
Influence functions (IF) [Ham74] are by far the most widely used and studied data attribution method. The IF is first-order approximation to the change in model parameters when infinitesimally down- weighting an individual sample. IF approximations are well studied in classical, under- under- parameterized settings, where they are typically accurate and enjoy solid theoretical foundations [GSL* 19]. But, despite widespread adoption for data attribution in wwwecd/ennnooo/ooearraaaeeeeeeee
models, IF's accuracy in the nigh-dimensional setting is comparatively poor. Empirical studies show that IFs often underestimate the true magnitude of parameter changes, leading to potentially misleading conclusions about data importance or model robustness [BPF21, KI.17J. And, existing theoretical analyses justifying IF approximations break down for overparametrized models. But, thus far, more accurate alternatives to IFs have proved too computationally expensive be practical.
We study a simple and fast-to-compute modification of the influence function, which we the rescaled influence function (RIF). RIFs improve accuracy by incorporating a limited amount of higher-orde information about the change in model parameters from sample removal, but retain the additivity and in many settings also the computational efficiency of IFs. We show via experiments and theoretical analysis that RIFs are accurate for data attribution in overparameterized models where IFs struggle. Like IFs, RIFs are model and task agnostic, meaning that they can be applied to any empirical risk minimization-bant leave-T-our -out effect according to any (smooth) measure of change to model parameters. We therefore advocate using RIFs as a drop-in replacement for IF' across data attribution applications.
training method with smooth losses, and they can estimate the
Organization In Section 1.1, we introduce RIFs formally. Section 2 presents our experimental results, and Section 3 presents our theoretical analysis of RIF We discuss context and conclusions in Sections 4 and 5
1.1 Influence Functions, Newton Steps, and Rescaled Influence Functions
We now introduce the rescaled influence function formally. Suppose that {(x,, yr) [e)] is a training data set, C IRd is a class of models, and É(z, y, 0) is a twice-difierentiable loss function; may include regularizer. For simplicity, we imagine that l is convex, although the definition of RIFs can be extended to the non-convex case. Let 0 arg minøge Σien ((x., Vr. 0) be the empirical loss minimizer (or, in the non-convex setting, any local minimum of the empirical loss).
Influence Functions
The influence function IF; E Rd associated to the i-th training sample is first-order estimate of the effect of dropping that sample.' ! Introducing weight w, E [0, I| associated to each sample i and allowing i depend on w via (w)) arg minsge Eisn wa E(2,, yr.
IF, = - [
((w)
H
Vl(a, Vi. 0).
dw,;
Here, H is the Hessian of Eisn ((x; ys, 8) evaluated at (see e.g., [RHRS86] for a derivation). For T C [n]. the IF estimate of the leave-T oout model is
b 0 + Σ IF,
IET
We can obtain all the single-sample IF estimates IF; at the cost of a single Hessian inversion and n gradient computations, which then suffice to obtain Ö for any via additivity.
Newton Steps
IFs additive and efficiently computable, but their accuracy suffers when n and are comparable, or, worse still, if d significantly exceeds n as in the overparameterized setting
'ooee treatments replace dropping with up- -pightgtnn with a resulting difference of sign compared to our convention.

---

([KATLI9]; see also Section 2). A much more accurate approximation to the leave-T-our effect is given by taking single Newton step (NS) to optimize the leave-T-out loss Eigr (z Yi. f), starting from O. The NS approximation to the leave- -out effect is given by
0NS,T = a --Hmiy
Σ GET
Vi(a, v.. B. = 0 Hiii Σ EET
Vi(z;, Vis 81)
[N|TT
Here, H( v is the Hessian of the leave-T-ou loss, evaluated at 0, and the second equality follows from the fact that 0 is local optimum of L.
As early as 1981, Pregibon [Pre81] observes in the context of leave-one-out estimation for logistic regression that the Newton step approximation is remarkably accurate. At a high level this is because, unlike the IF approximation, the NS approximation takes into account the change to the Hessian from removing the samples in T. For convex losses, the true leave-T -out effect can often be obtained by Newton iteration taking multiple Newton steps initialized with ô. The only differences see between the one-step NS approximation and the result of Newton iteration would arise because the Hessian may change from its value at Ó. Thus, for problems with Lipschitz Hessians, we expect NS be a very accurate approximation the true leave-T--or effect; [KATL19] offers experimental validation of this idea for leave-k-out estimation in logistic regression, and some formal justification.
expect to
Rescaled Influence Functions The accuracy of the NS approximation comes significant cost, since each fresh T requires a Hessian inversion, and additivity is lost. The RIF recovers additivity and much of the computational efficiency of IF, but retains much of the accuracy of the NS approximation. For sample i E [n]] let RIF; be the NS approximation to the leave-i-out effect, given by RIF, (m) (e, Ve, 0). Then for T C [n]]. we define the RIF approximation to the leave-7-out effect to be
:RUFT = 0 Σ RIF, iET
RIF additive by definition.
The computational overhead of RIF compared to IF depends in general on the cost of computing the leave-one-out Hessian inversions once these are obtained, no fresh Hessian inversion is needed to compute Ô for any T. RIF is especially attractive in generalized linear models and neural networks with a ReLUU activation function, where RIF; can be obtained from IF; by multiplying by rescale factor (1 h₂)-1 where h; is (generalized) leverage score associated to the i-th sample, which can be computed via a single matrix-vector product with H-1 Thus, for generalized linear models, no additional Hessian inversion is needed. For example, in logistic regression, the formula for RIF; uses the rescaling (1 - h;) where h; = 1i: - 5.) x H 2, here y): E [0, 1] is the logistic predicted label of the i-th sample according to 0.
Beyond generalized linear models and ReLU neural networks, whenever each sample makes low- rank contribution the Hessian, the n leave-one-out Hessian inversions can be computed quickly via the Iiterman-Morrisonn MMorison/Woodburr Wooddury formula. In all of our experiments, the running time overhead to compute RIF is negligible (see Table 2).
In underparameterized settings, it is reasonable to expect that removing single sample has negligible effect on the Hessian, and so IF; R RIF; But for high-dimensional or overparameterized models, single sample removal can have significant effect on the Hessian. Our experiments and theory demonstrate the significant accuracy improvement of RIF compared to IF in high-dimensional and overparameterized models.
We note that the idea of summing over estimates of leave-one-out effects to estimate the leave-T'-our effect is not new, and has been a central component of many previous data models [IPE+22]. In their seminal TRAK paper, Park et al. separately consider both the idea combining LOO effects additively PPGI=2a][Deffiitto 2.3] and the idea of using Newton step to estimate LOO effects of a logistic regression [PGI [Definitin 3.1] but do not explicitly combine the rescaling effect in their estimator except note that the rescaling correction has little no effect in their setting.
similar approach that has been the focus of recent research the Additive-One-Fii which estimates the LTO effect by summing over the exact LOO effects. This data model was
data model,
3

---

ESC-50
Cat
Truck Automabile
Dog Fish
Spam Ham
Effect on test prediction
Rondern
Clader
IF
Chicanes
Hist mootlie
Effect on test loss
250
-200
-100
-200
Effect on selfloss
hiidden
250
500
750
200
400
600
200
600
Actual Effect
Figure 1: Accuracy of IF versus RIF compared across datasets from image classification (DogFish, Cat vs Dog, Truck vs Automobile), natural language (Spam vs Ham), and audio (ESC-50). In each dataset, we study binary classification task solved via logistic regression with frozen-embedding features. Each point represents single choice subset T. The horizontal axis represents ground truth leave-T-out effect measured by changes via refitting the logistic model. The vertical axis represents the prediction of this effect made by IF/RIF/NS, A perfectly accurate prediction falls along the black diagonal line. essentially every case, the RIF prediction falls nicely along this "ground truth" line, agreeing with the NS prediction, while IF typically underestimates the leave-T Toree---utt effect.
predictions, test losses, and self-loss, computed
introduced by Kuschnig al. [KZCC21] and further analyzed by Hu al. [HHZM24] and by Huang et al. [HBN=24) Kuschnig et al.. Hu et al. and Huang et al. study the accuracy of this method for identifying sets of highly influential samples ordinary least squares (OLS) regressions. Moreover, Huang et al. also note that because single Newton step is equivalent to full retrain for the case of OLS, natural extension of the Additive-Ou Caetve--One-Bee One-Onec- Exact data model is sum over the single- Newton step attributions of the individual samples 1HBN*24][Appp 24][Appendi, C.2], and Hu et al. [HHZM24][[ectto]] 3.1] hypothesize that an NS-like rescaling might explain some of the inaccuracy of the estimates in Koh et al. 's experiments. However, the experiments and theoretical analyses of these previous works focus on the case OLSS linear regression where RIF is equivalent to Additive-One-Exal the best of our knowledge. prior work offers quantitative experimental or theoretical comparisons between RIF and other data attribution methods in the high- nigh-dimensional beyond this setting."
to
2 Empirical Results
We now present empirical findings on the accuracy of RIF estimates for leave-T effects. Our experimental setup inspired by the seminal work of [KL17, KATL19], who assess the accuracy of influence function estimates using logistic regression as testbed.
We compare IF, NS, and RIF estimates across the first five datasets in Table 1, spanning vision, NLP, and audio classification tasks. Each dataset is processed using a domain -spccffc embedding, and train logistic regression model to solve binary classification task the embedded data. We compare the actual vs predicted effect of removing a given set of samples T from the training set, while varying:
We are grateful to Tamara Broderick, Jenny Huang. Yuzheng Hu, and Jiagi Ma for making us aware of these prior works via personal communication.

---

Sample-removal strategy: Following [KATLI9], we evaluate both random subsets and more structured sets of training points, selected using heuristics such as clustering by random feature or by Euclidean distance in feature space.
Accuracy metric: As in [KATL19], we assess accuracy by comparing predicted and actual changes in three scalar quantities when set 7 is removed: (1) the total predicted probability for target class over subset of test samples, (2) the total test loss on this subset, and (3) the loss on the training set including the removed samples ("self-loss"), The test subset is
selected include balanced mix of high-loss and randomly chosen test points.
Size of removed subset: We consider values of [T] ranging from 0.1% to 5% of the training set.
We illustrate our main findings in Figure 1. Across every dataset, fraction of sample removals, and accuracy metric, we find that RIF significantly outperforms IF. For more details our experimental setup, see the supplemental material.
Table Summary of datasets used in our experiments. Each dataset involves a binary classification task which we solve using regularized logistic regression with mild Lg regularization. We include both datasets used the [KATL.19] benchmark (DogFish and Enron), as well as several new datasets spanning a wide range of domains, including vision, natural language processing, and audio. For more details about these datasets, see the supplementary material.
Name
d
Test Accuracy
Description
ESC-50
512
1600
83.0%
ESC-50 dataset embedded using OpenL3; "artifi- cial" vs "natural" classification [Pic15, CWSB199 ResNet-50 embeddings of CIFAR- 10 cat and dog classes [Kri09, Tor16]
CatDog
2048
9600
80.9%
AutoTruck
2048
9600
92.7%
ResNet-50 embeddings of CIFAR-10 truck and au- tomobile classes [Kri09, Tor16]
DogFish
2048
1800
98.3%
Inception v3 embeddings of dog and fish images from ImageNet [SVI+ 16, RDS 15]
Enron
3294
4137
96.1%
Bag-of-words embeddings of the standard spam vs ham dataset [KATL19, MAP06]
IMDB
512
40000
87.7%
BERT embeddings of the IMDB sentiment dataset [MDP* 11, DCLT19]
Dimension and Regularization As the number of samples n decreases compared to the model dimension d, we expect the higher-order effect captured by RIF be stronger. Figure 2 shows this tradeoff, comparing the IF and RIF accuracy while varying the ratio of and d by sub-sampling a fixed dataset. A similar tradeoff appears when we add an L2 regularization term of / || 12 the loss for different values of A > O. Increasing X dampens the higher-order effects captured by RIF in the limit À + oo the Hessian does not vary as samples are removed. Figure we illustrate this tradeoff by varying À for a fixed dataset (DogFish), observing that IF and RIF agree for large À but not for small X.
Tradeoff::
Detecting Data Poisonings with RIF One common use of additive data attributions such as influence functions is to detect potential outliers contaminating dataset [KL17, BGM20, RH25, KLM+23), 23]. We conduct a simple experiment to demonstrate the advantages of RIF over IF for this task. We take binary image classification problem (Truck vs Automobile), add an incorrectly-labele test sample to the training set, and train a logistic regression model on the resulting poisoned dataset. We then compare the accuracy of IF and RIF estimates of the effect that removing the poisoned sample would have on the model's ''s prediction for that test sample. RIF significantly outperforms IF. See Figure 3.
3 Theoretical Results
We turn to a theoretical explanation of the effectiveness RIF to estimate leave-T-out effects in high dimensions. Prior work [KATLI9] shows that under reasonable assumptions, the NS approximation
5

---

D-g
4g
8d
n- 160
IMDB
53
200
260
260
200
20
306
200
40
500
A/h 10-4
Aln 10
Ajo
10
Min - 10
Wn=
DogFish
Actual Effect
Figure 2: First row: accuracy of IF versus RIF compared across differing ratios of n and d, for the IMDB dataset, subsampled randomly obtain datasets of varying sizes. IF and RIF are similar when n >> d, but as n decreases, RIF remains accurate while IF degrades. Second row: A similar comparison for the overparameterized DogFish dataset, where IF becomes accurate only under strong regularization, while RIF remains robust across settings. In all plots, we compare the predicted versus actual values of the self-loss metric. Blue points show the RIF estimate, green points the IF estimate, and cyan points the Newton step. Point shapes indicate different strategies for selecting training samples remove, in Figure 1.
vary the regularization strength X.
RIF
Poisoned Label: Truck
Predict Logit Change with IF
-10
-20
Predict Loglt Change with RIF
-30
Actual Effect
Figure 3: On the right we plot the actual vs predicted effect on test samples logits from removing "poisoned" sample from the train set using both IF and RIF. On the left show the poisoned image corresponding to the lefimost point in the plot an image of an automobile mislabeled as "Truck". RIF predictions (blue) align much more closely with the actual effects, while IF predictions (green) tend to underestimate these effects.
provides very accurate approximation of the true leave-T-out effect; this is also easily visible in the experiments we reproduced above. Importantly, the NS approximation remains accurate even when the IF estimate is poor. Motivated by this, focus analysis the gap between our RIF estimate and the NS estimate. This leads to comparatively simple theorem statement, avoiding too many assumptions.
Our setting is as follows. We assume that a model trained via minimization of a convex empirical risk of the form:
i arg mün (O)
OER
1=1

---

We think of each E as per-sample loss from the i-th sample in an underlying training set, although we do not actually need to assume such a training set underlies the optimization problem. Let gi = (0) and H; = (0)) denote the gradient and Hessian of the ith sample at the solution 0, and define the total Hessian : >;== H,
We make the following set of assumptions on the loss functions. Most of the assumptions are parameterized quantitatively, and our final theorem bounding the quality of the RIF approximation depends on these parameters. Crucially, these assumptions allow for & d (or even n < d. if regularization is added), so that our main theorem captures how RIF remains accurate for high- dimensional annely-underprrameeeriee
even overparameterized models. We discuss after main theorem statement how to interpret these assumptions quantitatively.
Assumption (Positive SemideeiitenessxCnxxiity. We assume that each H, is positive semidefi- nite, or equivalently, that & is convex.
The next two assumptions are the key quantitative ones. We offer some discussion now and more after we state main theorem.
Assumption 2 (No Single-Sample Gradient or Hessian Too Large). For all E nl, we assume
H H-1/2g: g:
S C.
and H H 1/2
lopp S
CR'
for some C2, CR > O. Here II-llop the operator norm/maximum singular value.
The second clause of Assumption can be rewritten H, Ca(1-CR') HJ. This just captures that no single-sample Hessian H, is too much larger any direction than the sum of all the others. This the key condition allowing for large dimension d: even if n d, this condition can be satisfied (and indeed will be satisfied for, c.g., random low-rank H,) without taking Cn = (1).
Assumption 3 (Cross-Sample Incoherence). For some E,8
> 0, and for all i + j.
H HHHHHE 1r 8 and
H g
S.
We expect 8 to be small because in high dimensions gradients and Hessians of distinct samples are likely to point mose-to-orthogone directions. We carry this intuition out in more detail below.
Ultimately, we use IF/RIF/NS to estimate the change to f(Ò) for some evaluation function For instance, in our experiments, f is typically test loss or a test prediction. To show that the RIF and NS estimates are close, we require our evaluation function
have bounded gradients:
Assumption 4 (Evaluation Gradient Projection Control). Let V(()) denote the gradient of an H
evaluation function f: I + + R. For all
2/2 H H f(O)
||
I for some 0.
Let w E [0, 1] be weight change vector. We study the NS and RIF approximations to the optimum of the weighted loss Eisn (f), (So, to capture leave-T-out we set w; = for E T and otherwise wt; 0.) We define ÓRIF w and θNs,w analogously to ÓRI,T, @NS.r, respectively. We now ready to state our main theorem:
Theorem 3.1 (Accuracy of Rescaled Influence Function). Under Assumptions for any k S 20C
(E (0), @, ÓRIF.W) S 12 (E+
The proof of Theorem 3.1 proceeds via a matrix peatur-perturration analysis which shows that the Hes- sian inversion in the NS approximation can itself be approximated well without considering the contributions to the inverse from V 's interaction with V when i * j. We defer the proof to supplemental material, and focus instead on interpreting Theorem 3.1, to illustrate how it captures the improvement of RIF compared to IF.
Interpreting Assumptions and Theorem 3.1 Prior works (GSL+19, KATL19] prove similar-in- spirit results to Theorem 1,1, but concerning IF rather than RIF. A direct comparison of Theorem 3.1 to those results prior work is challenging, as each result is derived under different assumptions. So. to better understand the practical significance of our bounds compared to those in prior work, and
7

---

why they capture the accuracy of RIF for overparameterized models, we analyze their asymptotic behavior in a simplified setting. Since this is for illustration purposes only, we keep the analysis informal.
Consider linear regression with square loss (ordinary least squares), where the data vectors drawn i..d. from standard Gaussian distribution, X; ~ (O, I). And suppose n 2 (1 (1+ +(1)d,, i.c., and d are comparable. In this case, we know that:
Each individual Hessian contribution H; xa is low rank with rk (H;) and |H; llop O(d),
The total Hessian is approximately isotropic: H Rz nI.
Gradient vectors are bounded in norm: || ll Vd.
We can apply the heuristic that random vectors u, E R& are likely to have (u, u) ss ||u|||o/// vd. and so long as n 2 (1 + R(1)dd we expect the key variables in Theorem 3. scale as:
C == [m
H
1/2
gi
Ld VR
O(),
CR == maX
1/9 1/3
8 max
H 1/2
"H-HH
'H
/2
=
op
|
Ö
vi
E == m
g
2
17 maX
1/2 H
Vof
maxie(n]
'Vo =ō ((Vaalll))
Under these conditions, Theorem 3.1 guarantees that for any set of at most k: S lithrsholld = removed samples, the discrepancy between the RIF and Newton step estimates bounded by:
(e CRC()) Ō 1:2 VV
(Q), &NS. (RUP,)) S
n2
The scaling rate n in the denominator matches what we expect for influence functions, as estab- lished in [GSL+19] 19]. But influence function approximations incur significantly worse dimension dependence in the numerator, meaning that must be much larger than d (indeed, quadratic in even larger) to obtain nontrivial guarantees. For comparison, in supplemental material, we analyze the bounds proved by [GSL+19 19, KATL19] for influence functions to the same random-design ordinary-least squares setting and show that they guarantee influence function accuracy only for much larger n or smaller d. For example, the bounds of [GSL+ 19] are only applicable for < Ô n and
yield an error bound that scales as Ô A2 [Voll1
Finally, assess the tightness of our result relative to the RIF magnitude itself, note that under the same random-design least-squares setup and the same heuristics about inner products of high- dimensional random vectors, the RIF estimate for the removal of the top-k most influential samples scales as
k Vooll2
( [V ((), @RUF,W)) ||w||1 = =k] S
max
Hence, the ratio of the RIF estimate ("signal") to the RIF-NS error (" ("noise")
(KV(()) (0)(((0),TF..)) ORTF ||w|]| - k
max
n
SNR
= ì2
( ÔNs,w ÓRIF,)) ||w||] k)
kvd
max
This implies that RIF provides good relative-error approximation NS even in high dimensions. provided l < n Vd'

---

4 Related Work
Influence functions were introduced by Hampel in the context of robust statistics [Ham74], and in the context of estimation of standard errors via the infinitesimal jackknife by Jaeckel [Jae72], with broad ensuing literature in statistics; see e.g., [Law86, GSL + 19]. Recent work in econometrics [BGM20] uses influence functions to uncover robustness issues in large empirical studies.
The seminal work [KI.7]] introduced the modern use of influence functions to study the rela- tionship between training data and model behavior in modern machine learning. Ensuing works [BNL* BPF21, GBA 23, FZ20] study influence functions for neural networks, and use them as a tool to study and interpret model behavior. [GJB19, BYF20] propose second and higher-order approximations to leave-one-out and leave-T-out effects, but these approximations sacrifice linearity and efficiency. Many applications of influence functions have appeared recently, e.g., machine unlearning [GGHVDM19, SAKS21, SW22], data valuation [JDW+19], robustness quantification [SS19], and fairness [LL22]. To scale influence functions up to very large models and datasets, where Hessian inversion becomes infeasible, several works develop sketching/random projection techniques to approximate influence functions, e.g.. [WCZ* 16, P SZVS22].
Data attribution tracing model behavior back to subsets of training data has become a major industry in machine learning; see the recent survey [HI.24] and extensive citations therein, as well as the NeurIPS 2024 workshop [NMI+24] and ICML 2024 tutorial [MIE*24] 24].
Newton-step approximations to the leave-l-out error have been studied since least 1981 [Pre81]. Cross-validation is an especially important application [RM18, WKM20J. Additionally, several recent works consider data models that additively combine estimates of leave-one-out effects to compute a leave- effect [KZCC21, IPE 22, PGI 23a, HHZM24, HBN HB]. However, to the best of our knowledge no previous work provides an empirical or theoretical evaluation of the RIF method beyond low-dimensional least-squares regression.
5 Discussion and Conclusion
IFs and ceportaacc-Orderinng Revisiting the Common Wisdom Common wisdom regarding IF approximations to leave-T--uut effects for high-dimensional models holds that the approximations typically underestimate the true leave-T-out effect, but that there strong correlation between the influence-function approximation to the leave-T-out effects and the true leave-T effects, especially measured in terms of the ordering of subsets based on their predicted/actual leave-T -out effect. The seminal [KATL19] even phrases this as an outstanding open question, writing that their work "opens up the intriguing question of why we observe [correlation and underestimation) across a wide range of empirical settings".
Our work sheds significant light on this question. First of all, explains why we see such correlation in great many cases - if most samples have similar "rescale factor" relating IF and RIF (which we would expect happen for e.g., random data), this induces linear relationship between RIF and IF estimates. Since RIF is an excellent approximation to the true leave-T -out effect, this explains the correlation between IF and the ground truth, and explains why IF typically underestimates the truth the rescale factors are always larger than 1.
[KATL19] also note that this IF/ground-truth correlation phenomenon need not be universal, and indeed we observe several experiments where it does not hold. For instance, in the first row of Figure in the Cat vs Dog dataset, we see a dramatically non-linear and even non-monotone relationship between IF and ground truth, since different subset-selection strategies yield very different relationships between IF and ground truth. Even the ordering of subsets by IF-predicted effect is not accurate in this example, but RIF remains accurate.
Limitations Although much more accurate than IFs, RIFs are still imperfect predictors of ground- truth see e.g.. the ESC-50 dataset in Figure/ 1 or the rightmost variants of the IMBD dataset in Figure 2. We expect high-dimensional logistic regression to be a good "model organism" for high-dimensiinal machine learning, so our experiments are limited to that setting. RIF also still requires inverting the Hessian; as discussed in related work for very large-scale models this can be computationally infeasible, and approximate techniques required. While we show that RIFs are

---

preferable to IFs for detecting certain simple data data-poisone poisoning attacks, we do not expect that RIFs are secure general defense against data poisoning.
Conclusion We show that RIFs are an appealing drop-in replacement for IFs, with little compu- tational overhead in generalized linear models (or whenever individual training samples contribute low-rank terms to Hessian), but dramatically improved accuracy. Both experiments and theory support this conclusion. Furthermore, the fact that RIFs and IFs differ by per-sample scaling factor helps to resolve an open question from prior work, showing that the correlation between IF and ground truth leave-T' -out occurs when the per-sample scalings all (approximately) agrec.
Acknowledgments and Disclosure of Funding
We would like to thank Jenny Y. Huang, David R. Burt, Yunyi Shen, Tin D. Nguyen, Vishwak Srini- vasan, Tamara Broderick, Yuzheng Hu and Jiaqi Ma for helpful conversations and correspondences. This work was supported by NSF Award No. 2238080 and CSAIL Alliances.
Compute Resources
All experiments were conducted on server equipped with 64GB RAM, 2 IBM POWER9 CPU cores, and 4 NVIDIA Tesla V100 SXM2 GPUs (each with 32GB memory).
Table 2 details the computational cost of training the base models and computing their IF and RIF data attribution. Another major computational overhead was in retraining the model to obtain ground-truth values for the retrain effect. Despite this, compute resources total wall-clock time for all experiments reported in the paper was under 100 hours.
not bottleneck for our work. The
Table 2: Comparison of runtime components across datasets. The rescaling step consistently added
negligible overhead across all experiments.
Dataset
Training
Hessian
Inversion
Influence
Rescaling
ESC50
1.8 s
0.056 s
0.0005
0.051
0.0033 s (0.2%)
CatDog
48 s
4.9 s
0.010 s
4.8 s
0.087 s (0.1%)
AutoTTruck
4.9
0.0094
4.8 s
0.087 s (0.2%)
DogFish
0.43 s
0.92 s
0.0095
0.89 s
0.015 s (0.7%
Enron
6.75 s
15 s
0.065
15
0.095 s (0.3%)
IMDB (n=16d)
20
0.92 s
0.0012
0.87 s
0.044 s (0.2%)
References
[BAHAZ19] Marc-Etienne Brunet, Colleen
Ashton Anderson, and Richard Zemel. Understanding the origins of bias in word embeddings. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 Proceedings of Machine Learning Research, pages 803-811. PMLR, 09-15 Jun 2019.
[BGM20) Tamara Broderick, Ryan Giordano, and Rachael Meager. An automatic finite-sample robustness metric: when can dropping a little data make a big difference? arXiv preprint arXiv:201 1..20///.19999 2020.
22] Juhan Bae, Nathan Ng, Alston Lo. Marzyeh Ghassemi, and Roger B. Grosse. If influence functions are the answer, then what is the question? In Sanmi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference Neural Infor- mation Processing Systems 2022, NeurlPS 2022, New Orleans, LA USA, November 28 December 9, 2022, 2022.
10

---

[BPF21] Samyadeep Basu, Phillip Pope. and Soheil Feizi. Influence functions in deep learning are fragile. In 9th International Conference on Learning Representations. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.nett 2021.
[BYF20] Samyadeep Basu, Xuchen You, and Soheil Feizi. On second-orde group influence functions for black-box predictions. In Proceedings of the 37th International Con- ference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Reseurch, pages 715-724. PMLR, 2020.
[CWSB19] Aurora Cramer, Ho-Hsiang Wu, Justin Salamon, and Juan Pablo Bello. Look, listen and learn more: Design choices for deep audio embeddings. In Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3852-3856, 2019.
[DCLTI9] Jacob Devlin, Ming-Wa Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre- training of deep bidirectional transformers for language understanding. In Proceed- ings of the 2019 conference of the North American chapter of the association for computational linguistics: human language technologies, volume I (long and short papers), pages 4171-4186, 2019.
[Efr92] Bradley Efron. Bootstrap methods:
another look at the jackknife. In Breakthroughs in statistics: Methodology and distribution, pages 569-593. Springer, 1992.
[EIC+25] Logan Engstrom, Andrew Ilyas, Benjamin Chen, Axel Feldmann, William Moses, and Aleksander Madry. Optimizing ml training with metagradient descent. arXiv preprint arXiv:2503. 2025.
[F720] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 13:2881-289) 2020.
[GBA 23] Roger Grosse, Juhan Bae, Cem Anil, Nelson Elhage, Alex Tamkin, Amirhossein Tajdini, Benoit Steiner, Dustin Li, Esin Durmus, Ethan Perez, al. Studying large language model generalization with influence functions. arXiv preprint arXiv:2308.cm 032296 2023.
[GGHVDM19] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. arXiv preprint arXiv: 1XXiv:911..0300 2019.
[GJB19] Ryan Giordano, Michael Jordan, and Tamara Broderick. A higher-order swiss army infinitesimal jackknife. arXiv preprint 19Xiv:1907.122 2019.
[GSL+19] 19] Ryan Giordano, William Stephenson, Runjing Liu, Michael Jordan, and Tamara Broderick. A swiss army infinitesimal jackknife. In The 22nd International Confer- ence on Artificial Intelligence and Statistics, pages 1 1139-1144 PMLR, 2019.
[GZ19] 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.
[Ham74] Frank R Hampel. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(344):383-33,, 1974.
[4]++24] Jenny Huang. David Burt, Tin D Nguyen, Yunyi Shen, and Tamara Broderick. Approximations to worst-case data dropping: unmasking failure modes. arXiv preprint arXiv:2408. 09008, 2024.
[HHZM24) Yuzheng Hu, Pingbang Hu, Han Zhao and Jiaqi Ma. Most influential subset selection: Challenges. promises, and beyond. Advances in Neural Information Processing Systems, 17:111978-119810 2024.
[HI.24] Zayd Hammoudeh and Daniel I Lowd. Training data influence analysis and estimation: A survey, Machine Learning, 113(5):2351-24033 2024.

---

[IASCZ2]] Zachary Izzo, Mary Anne Smart, Kamalika Chaudhuri, and James Zou. Approxi- mate data deletion from machine learning models. In Arindam Banerjee and Kenji Fukumizu, editors, Proceedings of The 24th International Conference on Artifi- cial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 1008-2016 PMLR, 13-15 Apr 2021.
[2] Andrew Ilyas, Sung Min Park. Logan Engstrom, Guillaume Leclere, and Aleksander Madry. Datamodels: Understanding predictions with data and data with predictions. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pages 9525-9587. PMLR, 2022.
[Jae72] L. Jaeckel. The infinitesimal jackknife, memorandum. Technical Report MM 72-1215-11, Bell Laboratories, Murray Hill, NJ, 1972.
19] Ruoxi Jia, David Dao, Boxin Wang, Frances Ann Hubis, Nick Hynes, Nezihe Merve Gürel, Bo Li, Ce Zhang, Dawn Song, and Costas J Spanos. Towards efficient data valuation based on the shapley value. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1167-1176. PMLR, 2019.
[KATL199] Pang Wei Koh, Kai-Siang Ang, Hubert H. K. Teo, and Percy Liang. On the ac- curacy of influence functions for measuring group effects. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc. Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 2019.
December 8-14, 2019, Vancouver, BC, Canada, pages
[KL17] Pang Wei Koh and Percy Liang. Understanding black box predictions via influence functions. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 1885-1894, PMLR, 2017.
[KLM+23] Alaa Khaddaj. Guillaume Leclerc, Aleksandar Makelov, Kristian Georgiev, Hadi Salman, Andrew Ilyas, and Aleksander Madry. Rethinking backdoor attacks. In International Conference on Machine Learning, pages 16216-16236. PMLR, 2023.
[Kri09] Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
[KSL22] Pang Wei Koh, Jacob Steinhardt, and Percy Liang. Stronger data poisoning attacks break data sanitization defenses. Machine Learning, pages 1 1-47, 2022.
[KZCC21] Nikolas Kuschnig, Gregor Zens, and Jesús Crespo Cuaresma. Hidden in plain sight: Influential sets in linear models. Technical report, CESifo Working Paper, 2021.
[Law86] John Law. Robust statistics the approach based on influence functions, 1986.
[LL22] Peizhao Li and Hongfu Liu. Achieving faimness at no utility cost via data reweighing with influence. In International conference on machine learning, pages 12917- 12930. PMLR, 2022.
[MAP06] Vangelis Metsis, Ion Androutsopoulos, and Georgios Paliouras. Spam filtering with naive baycs-which naive bayes? In CEAS, volume 17, pages 28-69. Mountain View, CA, 2006.
[MD++11] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. Learning word vectors for sentiment analysis. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguisties: Human Language Technologies, pages 142-150, 2011.
12

---

[4] Aleksander Madry, Andrew Ilyas, Logan Engstrom, Sung Min (Sam) Park, and cc/virtual/2024/
Kristian Georgiev. Data attribution at scale. https://ice tutorial/36228, 2024. Tutorial presented at the s1st International Conference on Machine Learning (ICMI. 2024), Vienna, Austria, July 22, 2024.
[4] Elisa Nguyen, Sadhika Malladi, Andrew Ilyas, Logan Engstrom, Sam Park, and Tolga Bolukbasi. Attributing model behavior at scale (attrib). https:/ /ttt://///uppsss// cc/virtual/2024 http:///////////////////// workshop//4704, 2024. Workshop at the 38th Conference on Neural Information Processing Systems (NeurIPS 2024), December 14, 2024.
[3G]+ Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclerc, and Aleksander Madry. TRAK: attributing model behavior scale. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Muchine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 27074-271 13. PMIR, 2023.
[PGI+ Sung Min Park, Kristian Georgiev, Andrew Ilyas, Guillaume Leclere, and Aleksander Madry. Trak: Attributing model behavior at scale. arXiv preprint arXiv:2303. 14186 2023.
[Pic15] Karol J. Piczak. ESC: Dataset for Environmental Sound Classification. In Proceed- ings of the 23rd Annual ACM Conference on Multimedia, pages 1015-1018. ACM, 2015.
[Pre81] Daryl Pregibon. Logistic regression diagnostics. The annals of statistics, 94):7055- 724, 1981.
15] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, al. Imagenet large scale visual recognition challenge. International journal of computer vision, 115:211-252 2015.
[RH25] Ittai Rubinstein and Samuel B. Hopkins. Robustness auditing for linear regression: To singularity and beyond. In Proceedings of the Thirteenth International Conference on Learning Representations (ICLR 2025), 2025.
[RHRS86] Peter J Rousseeuw, Frank R Hampel, Elvezio M Ronchetti, and Werner A Stahel. Robust statistics: the approach based on influence functions, 1986.
[RM18] Kamiar Rahnama Rad and Arian Malcki. A scalable estimate of the satra- prediction error via approximate leave-one-out, arXiv preprint arXiv: 180I. 2018.
[SAKS21] Ayush Sekhari, Jayadev Acharya, Gautam Kamath, and Ananda Theertha Suresh. Remember what you want forget: Algorithms for machine unlearning. Advances in Neural Information Processing Systems, 34:18075-18086, 2021.
[SS19] Peter Schulam and Suchi Saria. Can you trust this prediction? auditing pointwise re- liability after learning. In The 22nd international conference artificial intelligence and statistics, pages 1022-1031. PMLR, 2019.
[SVI+ 16] Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818-2826. 2016.
[SW22] Vinith Suriyakumar and Ashia C Wilson. Algorithms that approximate data removal: New results and limitations. Advances in Neural Information Processing Systems, 35:18892-18903, 2022.
[SZVS22] Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence functions. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8179-81888 8186, 2022.
13

---

[Tor16] Torch Vision Contributors.
ResNet-50 Pretrained Model. wwwedell/ggneerte//ttoooooo
https:
//pytorch. hepyttrch.org//eo org/vissiie.. org/vision// models reseet50. html, 2016. Accessed: 2025-05-14.
[WCZ*16] 16] Mike Wojnowicz, Ben Cruz, Xuan Zhao, Brian Wallace, Matt Wolff, Jay Luan, and Caleb Crable. "influence sketching": Finding influential samples in large-scale regressions. 2016 IEEE International Conference on Big Data (Big Data), pages 3601-3612. IEEE, 2016.
[WKM20] Ashia Wilson, Maximilian Kasy, and Lester Mackey. Approximate cross-validation: Guarantees for model assessment and selection. In International conference on artificial intelligence and statistics, pages 4530 4540. PMLR, 2020.
A Proof of Theorem 3.1
Recall our main theoretical result from Section 3: Theorem A.1 (Theorem 3.1 (restated)). Under Assumptions 1-4, for any ls S 28Cx*
1
f Ows, ORIF S k2 (1 2CR) + CRC²d)
Before delving into the proof of Theorem 3.1, we introduce useful technical lemma:
Lemma A.2. Let A1, A& dd and let H e Iddd be positive semidefinite. Suppose:
H H-1/2A, 1/2
S for all i,
up
IA,HH / /Ayllop I 8ūj for all i + j.
Then,
k
1/2
A,H
1/2
5
op
Proof of Theurem 3.1. We begin by analyzing the difference between the Newton step and rescaled influence function (RIF) approximation.
Recall that the Newton step is defined as:
Newton Step (V
H
H
wigi
where each g: E R the ith gradient component, and H, is the ith contribution to the Hessian. Define the weighted Hessian:
H H
w H
For each i (1,...,n). define ((() = w [[a) to isolate the i-th coordinate. The RIF estimator is given by:
RIF: = Σ (VS) H-1 WG) wig.
Our goal is to bound the difference between the Newton step and RIF estimators and we do this by bounding the contribution of each individual sample. That is, for each i [m), will try bound
(Vf) H H wl)) gi
14

---

To do so, we begin by expressing each matrix in terms of H and its perturbations. Observe:
Hw - H2/2 (I Gw) H where Gw Σ H
1/2 w HHH
Moreover, we define R := (I G w -1 where Gw!)) 1/2 H,H 1/2, We have
H w(+) -H w(i)) H
Using the matrix identity:
(A - = (A- B) BA"
with A Hi..
w(O (
Hw, obtain:
Hw H
w(X)
w()
We now expand the correction term on the right-hand side further by applying the same identity again, this time expanding Hw (H Hw))
H (
Hw)
(Hwo Hw)
H
Hw H
(Hwo
Hw)
H (()
w(t)
W()
where the second term reflects higher-order correction contributions due recursive matrix inversion.
To bound the full error
(V)) T (Hw' H g: (V
w(O H.))
H w
(V
H (H
H
H H
H wing.
suffices to control the size of each of these terms separately. other words, we will proceed to bound:
1. The first order correction (Vf)
H (H w() Hw) H wingi gi.
2. The higher order terms( ff)
H (H Hw) H (H Hw) H gg
Bounding the First Order Correction
To bound the first order correction, we use the same formula above to split H H and higher order terms. The goal of this separation show that this update the Hessian does not rotate too much of the weight of gi onto the eigenspace of H, for any j #
wit) into a leading term
We have Therefore, for any #
H-1 H
wy H.H
gi
gi
+
1/2
H.H
RH
1/2 g:
Set + 8CnCa
Therefore, this first order correction is at most
W.
w(t
gi
H 1/2
H
I kn CCC,, w(1) gi
jæi
Sc+GnCod
Bounding the Higher Order Corrections
We next bound the second (higher-order) term using the Cauchy-Schward Schwarz inequality.
(VA)
Hw) H (Hw
Hw) H win g:
s
H (H H H 1/2
Gw)
H -- w(
H H w
15

---

We will bound each of these terms independently.
The right-most multiplicand is bounded using the analysis of the first order term
H 1/2 (H)
Hw) H
Bi
H
H
1
8:
jfi
1
my
H
w 8i
S
k
(E
CnCN8)
2
From the triangle inequality,
Σ
HHHHHHHH 1/2 HHH
H
| H
Using the assumption
H 1/2 H, 10.HH1111
1/2
op V 1, it follows that
H H 1/2
S 1
op
and from Assumption 5, we also have
V
H-
H 1/2
S
Therefore,
H
1/2
S Σ
|0yl s /n/ww||l = nnk
Next, define A₁ Wi 1/2
H,H 1/2,
Then for all j.
H HH-1/ 1//1/A23 A
H
1/2
-Iwyl
H
1/2
HHHH- 1/2
H
51 1
op
op
CR
since || $ 1 and by Assumption 2
H
1/2
H
1/2
< 1
1
up
CR
Moreover, for all i + j. have
VAH'
/Ay
S
//wal
Vlwzl deg.
op
So,
Σ inj
VAH VA
I 16 I (2 2. =
22 =28
Applying Lemma A.2 to the collection
{A,}. we conclude that
| llop I
Kō.
CR
For any h < 28Cx 1_ it follows that I - Gw is PSD and || llop
1, so we have
1
(T Gw)
-1
< ST S 20n
op
CR
kō
Summary:
So far, we have show that for all E [m].
(VS)
(H
H win)
gi s npk (5 CnCC5) + 7/ 2C (c CRCx5)
Therefore,
n
Newton Step
RIF
Σ
wi (Vf)
(H -H11 1 gi (1 CRC,O)
16

---

Proof of Lemma A.2. We define the linear operator C' R 7 Rddd to be
C(M) = H M VA,H-1/2
where M Rixkxdxd is a rank-4 tensor with Mi E Raxd
For tensors M, N, define their contraction:
C(M)C(N) C(L), where Lij
Σ 9."
Mag v A VA, N
Define Σ Bixkxdxd + R as E(M) | loop and define A R with entries
ij = I Then by the triangle inequality and submultiplicatiiity of the operator
norm, we have the point-wise inequality
E(L) E(M) A E(N).
Applying this iteratively for a sequence MI...., Mr. we obtain:
Σ(N) E(M)) A E(M2) A A A.E.)).
Now consider the identity tensor M with M,;- Ia and Mij 0 for Then:
C(M) Σ H 1/2 1/2
A 1/2
Σ H 1/2 A H 1/2
Let C = C(M). Then:
C² -²M) = C(N), with E(N) & A
By triangle inequality and bounding each tensor entry:
1|p < ddd max
H A 1/2
1/2
|| 1l.p 222d0 A
op
Taking ê-th roots:
|ICll.p S d1 1/8 1l
Letting e + oo, the prefactor tends to I, giving:
H 1/2 1
H-122/2
1/2
< A lop
op
Now bound A olop- Each diagonal entry A
||VAH H
1 VA, llop 1 A 1/2
S a.
lpp
Thus,
A = DDR with D = diag(
H 1/2 A H 1/2
H
,...., 1 S a.
Then:
A op I I| ol + ||
< 5 + |
where R is the off-diagonal part of A and |R] Eits 57/
Hence:
k
Σ H 1/2
A
1/2
<o +
Σ 82
op
igfl
17

---

B Asymptotic Analyses of the Bounds of [KATL19] and [GSL+1] 19]
B.1 Analysis of [KATL19]
Koh et al. [KATL199] present two main theoretical results. The first bounds the difference between a single Newton step and full retrain, and the second bounds the difference between the Newton step and the influence function estimate. We focus on the latter, since that more directly comparable to the guarantees of Theorem 3.1. To facilitate direct comparison, we restate their Proposition 2 with all assumptions made explicit below.
Proposition B.1 (Proposition 2 of [KATL19], rephrased). Assume the evaluation function f(0) is -ipshschiizz the Hessian Vzl(a, y, 0) is Ci-Lipschit, and the third derivative of f(0) exists and is bounded in norm by C333 Let min and mmxx be the smallest and largest eigenvalues of H1, respectively, and define
Vollo,, v: b(1))l1
Ce
max IsiSn
Then the Newton-influence error Errse-int(u)) (
ErrNc-if = vof(@(1)) H x.1
1/2
D(e)(w)
(ww) H 1/2
ANNi ( Var(((1))AON (w)) + Earyya (w),
Ervor from the curvature of f6)
where
D(w) (I- 1/2 Hi (1) (
L, and H1 (1(w) Σ w. WilVall (()).
The matrix D(w) has eigenvalues between and mmax X. The residual term Err captures the error due third-order derivatives and is bounded by
(r)) S | (6(5min + +A))).
To compare this guarantee with Theorem 3.1, which bounds the inner product between the data attribution error and Vf. we focus on the first term in the bound from Proposition B. This term quantifies the error in estimating the linear evaluation function using influence functions.
Recall that in the simple linear regression setting we define for our simplified asymptotic analysis, we have H x nI, and this is also the case with H Using the bound D(w) I " I from Proposition B.1, the Cauchy-Schward Schwarz inequality gives:
Tef(@(1))TH,,, H ((w) g(w)
Fmax
Vof(((1)) llx(w)ll2
Td
The scaling of Fmax/ / depends on the regime. Under strong regularization (e.g., bottom-right of Figure 2), may be O()) However, Koh et al. observe, this rarely happens in practice, suggesting that it would be more reasonable to assume that Fmaxx/ X = (1).
Let g denote the per-sample gradient, that g(w) E, wgg, represents the total gradient over removed samples. Following Koh et al.' approach in Proposition 1, we apply the triangle inequality to bound
lg ll2 -
|w//2 max (1ggllg) @(vV7).
iE(n]
Altogether, the Koh al. bound on the difference between the and the NS estimations for the 1st order change in comes out to
kvd n
max nd
V Vof(((1)) [g(()]], -
To get a sense for the scaling of this bound, as with the bound of Theorem 3.1, we compare the actual IF estimate to obtain an estimate of signal- -o-il-t--ooi----eeeeee -aaii between IF and its distance from NS
max Sk {1 (Vo. T ew))
A
SNR
o(1)
Erryt-int (w)
F
Therefore, the guarantee of Koh et al. do not rule out the possibility of the difference between the NS estimate and the IF estimate completely dominating the removal effects even in simple scenarios (regardless of how k d may scale with n)).
18

---

B.2 Analysis of [GSL* 19]
B.2.1
Assumptions and Statement
We now summarize the theoretical guarantees provided by Giordano al., which underlie their infinitesimal jackknife approximation for estimating the effect of data perturbations.
Assumption 5 (Smoothncss; Assumption of [GSL 19]). 19]). For all 0 E Sgg each 9n ( continuously differentiable in 0.
Assumption 6 voon-degeneracy; Assumption of [GSL+ 19]). For all 0 E Qg. the Hessian H ww) non-singular, with
sup E
|| H 1-) S Cop < oc.
Assumption 7 (Bounded averages; Assumption [GSL* + 191). There exist finite constants Cg and C₁. such that
||((0)l22 S Cg and sup sup
[1(0)]12 S Cn.
DEft
VN
Assumption 8 (Local smoothness; Assumption of [GSL* + 19]). There exists Do > 0 and a finite constant Ln such that for all 0 with |00 01112 S As.
M()) m(0i)l - In 110 0.1
Assumption 9 (Bounded weight averages; Assumption 5 of [GSL+ 19]). The weighted norm 1 2| uniformly bounded for W by constant C.v oc. VN
Condition (Set complexity; Condition of (GSL+ There exists a 5 and corresponding subset Ws C W such that:
max sup wEW's GE@,
Σ wn - 1)
S 6, and
max sup WEWss DE
Σ Win 1)
5.
Definition (Constants from Assumptions). Define
Cy == 1+ LC and As := min (AoCop1 Cpp
Theorem B.2 (Error bound for the approximation; Theorem [fSL 19]). Under Assumptions 5-9, if 8 < As, then
[0u(w) - 0(w)) 20 C102. 2
max We W
B.2.2 Analysis
We now analyze the guarantees provided by Giordano et al. [G]L+19] in the context of our linear regression setting.
our setup with squared loss and a linear model, the first- and second-order statistics become:
( = xz (yi (x, 0)),
(2 = x5,;
Note that hf) does not depend 0, and thus the local smoothness constant Ln (Assumption 8) is zero. Further, the Hessian takes the form
H(O, w)
so assuming the data is appropriately scaled, we expect the spectrum of its Hessian be somewhat clustered and hence Cop O(1) (Assumption 6).
Assumption 7 requires bounds [|g( and [|A(0)]22. In general, linear regression does not admit uniform convergence over 0 due to unbounded gradients as 0 + co, but if we fix ||O]| to moderate scale by limiting the scope of Ωa, we can reasonably assume that (0)]()) = o d, giving C ovd O(vd) and Cn se d.
19

---

We now turn to Condition 1, which controls how large the weighted deviations can be. In particular, we focus on the second half of this condition, which requires that
max sup wEWss dE
(wa (),n.
56.
N ==
When removing of k points (i.e., 1 1r), the deviation includes ht terms of magnitude [14((0)l1 x d², resulting
hd
Σ (w 1)),(())
The bound in Theorem B.2 requires this to at most As = 011), so we obtain the constraint:
kd
K d2
This represents the main constraint required for Theorem B.2 to apply. Finally, recall that in the main result of Theorem B.2, the error is bounded by
[Qu(w) B(w) ||, S C Cup
Erry=
Given 8 kd and Cop = Cp = (1)), we conclude:
kd
Erry z
n²
C Experimental Details
We based experimental design that of Koh al. [KATL19] who evaluate standard influence functions a similar setting in order to have a clearer benchmark for comparison.
C.1
Model Training
We fit all the logistic regression models using the wwt.yii...iii.....o minimize function to train the model using L-BFGS-B. and set a very strict stopping criterion to ensure that we converge to the global optimum and suppress dependencies on the initial weights when using warm-start retrain.
For the DogFish and Enron datasets also considered by Koh al., used the same Lg regularization parameter, and for all new datasets, we set the regularization to 1E 5.
C.2 Removal Set Construction
Similar to Koh et al., we evaluate our data attribution methods removals of "correlated" sets of samples from every regression. We focus on relatively fewer sample removals, varying the number of samples linearly along the range from 0.1% to 5% of the training set. For each dataset and each group construction strategy, we select 40 such sets samples (1 for each size).
For each such size k, we construct removal sets of size k using the following strategies
Clustered Samples: we construct sets of samples clustered either by a single feature or by La distance. When clustering by a single feature, for each set of samples to remove, we select a random sample E [m]] and a random feature j [d]. and output the k samples for which Xy., is closest to X When clustering by I.2 distance, we select the center sample E [n] uniformly at random and output the & samples closest to it in L2 norm.
2. Top Percentile Samples: For each of the metrics, of size k by selecting first selecting the top 2k samples and outputting a random subset half of them. We consider the metrics of: high positive negative influence on test loss and high positive / negative influence on test predictions, both computed using the standard influence function keep our benchmark comparable with that of Koh al.
construct a top- percenceet of samples
3. Random Subsets: A samples selected uniformly at random.
20

---

C.3 Datasets and Embeddings
We consider several classification tasks in this paper. For each, we extract features from particular modality (vision, NLP, or audio), embed them into a d-dimensional representation using frozen pretrained model, and train logistic regression classifier on relevant 2-class classification problem.
For the Enron and DogFish datasets, we try to keep to the same conventions as Koh et al. [KATI.19] for clean comparison.
ESC-50 embedded using OpenL3 ESC-50 a dataset of second audio clips each correspond- ing one of 50 categories with 40 samples from each category [Pic15]. We convert this to class classification problem by dividing the categories into "natural" sounds (breathing, cat, cow, etc.) and "artificial" sounds (airplane, chainsaw, clapping etc.).
We embed these audio samples using last-layer embeddings the OpenL3 python library [CWSB19). This produces d = 512 dimensional embeddings, and we separate them into train and test samples using a random 80 20 train-test split.
CIFAR-2 embedded using ResNet-50 We consider 2 CIFAR-2 datasets generated by limiting the CIFAR-10 10 dataset [Kri09] to 2 classes (Cat Dog, and Automobile vs Truck).
The photos from both train and test are embedded using the last-layer embeddings of the default pretrained ResNet-50 model in the torchvision python library [TTor16.
DogFish embedded with Inception v3 We reproduce the DogFish dataset from Koh et al. [KATL19].
This dataset contains photos of dogs and fish from the ImageNet dataset [RDS 15] embedded using frozen last-layer embeddings of the Inception v3 network [SV]+16].
Enron embedded with Spacy We reproduce the Enron dataset from Koh et al. [KATL19).
This NLP dataset consists of Spam Ham emails [MAP06] embedded using bag-of-words embedding with the spacy python library using the "en__cre__eeeeeeeeeeeeeeeeee_ee_ cae_ccre_webb sr___eeb__m_________ smm dictionary. We note that our embeddings for the Enron dataset may differ slightly from those of Koh et al. [KATL19], likely due to version differences in the spacy library. However, our empirical results are consistent with theirs.
IMDB embedded with BERT We consider the NLP IMDB sentiment analysis dataset consisting of 50000 movie reviews classified into positive and negative [MDP* 11]. We embed the reviews using the BERT model [DCLT19].
C.4 Experiments
An implementation of our experiments is available github. cethub.com/ittai-ruue conniitairrubinseeirrrsaellll functions. This appendix provides a concise overview of the procedures implemented the accom- panying code.
C.4.1 Comparison of Influence and Actual Effect
To produce Figure I, select sets of samples remove based the methods described in Appendix C.2. For each set of samples we retrain the logistic regression model without these samples obtain the ground truth effect on the change the metric f. and compare the application of the same metric f to the models predicted by each of the data attribution techniques.
Removal effect vs influence One minor distinction considered in the appendix of Koh et al. [KATL19] is between the influence on a metric and the "parameter influence" on a metric. They define the influence metric to be the inner product between the gradient of the metric and the estimated change model parameters
rinf
f. ginl 0)
and the parameter influence of a set of removals (which we simply call the "removal effect") to be
param. inf.
f (@iml) f (0)
21

---

ESC:50
Cat
Truck Automobile
Dog Fish
Ham
Effect on test prediction
Rosden
IF
Ouleece
bepelion
Effect on test
-200
-250
-200
-100
-10
Effect on selfloss
hidden
200
400
600
250
500
750
200 400
10
10
Actual Effect
Figure 4: Accuracy of IF versus RIF compared across datasets from image classification (DogFish, Cat vs Dog, Truck vs Automobile), natural language (Spam vs Ham), and audio (ESC-50), Each data- point in this experiment is generated its equivalent in Figure except that instead of evaluating the metric f' (e.g., test-loss) on the retrained model or the data model prediction of the retrain effect, we the leading order Taylor approximation of the change in this metric. There is major qualitative difference between the results of this experiment and the ones reported in Figure I, so we decided to keep the original evaluation for clearer apples-to-apples comparison.
We use the latter method produce the data points in Figures and (the metric considered in Figure 3 is linear so it is not affected by this distinction). However, similar to Koh et al., we observe very little effect to using the linear method instead.
C.4.2 Varying and A
In these experiments we repeated the same experimental procedure as the one used to generate Figure 1, but with varying levels of L2 regularization for the DogFish dataset and subsampling the IMDB dataset to different numbers of samples (via uniformly random draws). We report the effect of these removals on self-loss.
C.4.3 Data Poisoning
To ground our results we consider particular application of data attribution for detecting data poisoning attacks. We consider the simple data poisoning attack, where an adversary trying to flip our models prediction on some test sample (selected uniformly at random) and adds this sample with flipped label to the train set. We then run IF and RIF data attributions on the poisoned dataset and use them to predict the effect of the poisoned sample on its own logit (z; = (0)) and compare this the ground truth of full retrain.
C.5 Licensing of External Assets
We summarize the license information for all datasets and pretrained models used in our experiments. All assets cited in the main text.
Notes
Assets without explicit licenses (e.g., CIFAR-10, Enron, IMDB) are used strictly for non-commercial research purposes. We do not redistribute any datasets pretrained weights.
22

---

Table 3: License summary for datasets used in our experiments. All assets are cited and used in accordance with their respective terms.
Asset
Source
License
Use Notes
ESC-50
[Pic15]
CC
BY-NC
Freely available for non-commercial re- search
3.0
CIFAR-10
[Kri09]
Not specified
Widely used in academic settings; original authors affiliated with the University of Toronto
ImageNet
[RDS+
Custom terms
Access requires agreement ImageNet's non-commercial license
Enron Spam
[MAP06]
Not specified
Used under standard academic fair use; available via public research repositories Publicly downloadable from the Stanford
IMDB Reviews
[MDP* 11]
Not specified
Al Lab; used for academie research
Table 4: License summary for pretrained models and libraries. All tools are used under compatible terms for non-commercial research.
Model
Version
License
Use / Notes
OpenL3
v0.4.2
MIT
Permissive open-source license; commercial use allowed
ResNet-50
v0.13.1
BSD 3-Clause
Standard pretrained model from Torch Vision; license is permissive, but pretrained weights originate from ImageNet
(TorchVision
Inception v3
Apache 2.0
Model license is permissive; weights trained ImageNet, which restricts downstream
spaCy
v3.8.2
MIT
Freely usable model provided by spaCy; allows commercial and academic Hugging Face model with permissive li- cense: trained BookCorpus and Wikipedia,
BERT (Trans- formers)
bert-base- uncased (v4.36.2)
Apache 2.0
which may have unclear redistribution terms
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: We present the RIF method in Section 1.1. We compare IF and RIF and also present our data poisoning example in Section 2. Finally, we present a theoretical analysis of this comparison in Section 3.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
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 results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
23

---

Answer: [Yes]
Justification:
We discuss the limitations of our work in Section 5.
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 on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on 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 provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a 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 an 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 set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Section 3 contains full list of the assumptions needed for our main theoretical result (Theorem 3.1) 1) as well as a detailed discussion of their meaning and the asymptotic scaling of our bounds this theorem and its asymptotic analysis the supplemental material.
Justification:
simple setting. Due to space limitations, we moved the proofs of
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 the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: 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)?
Answer: [Yes]
24

---

Justification: In the supplemental material we give a detailed explanation of all of our experimental procedures and also include a library that can be used to reproduce all the figures and tables in our paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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 a 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, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or 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.. in the case of large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors 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., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
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: In the supplemental material, we include library that can be used to reproduce all the experimental results in our paper and we plan include a link a public git repository with the same library in the camera ready version of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips. cc/ CcoodeSubisssiono iapPolicy cy) for more details.
public/ cebblccggides//.
While encourage the release of code and data, we 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. htw.:i//ggiiieeee/odeduuiiiiiiao
for more details.
25

---

The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments should state which ones are omitted from the script and why.
reproducible, they
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code 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: We give a high-level overview of our experimental procedures in Section and more detailed explanation of all of our methods well an implementation of our experimental procedures in the supplemental material.
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 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 paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: None of the experiments reported in the paper require error bars, all of the reported datapoints are computed exactly.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should 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 the standard error of the mean.
is OK to report I-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 error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
26

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: We include paragraph detailing the compute resources used for our experi- ments the end of the main text of our submission.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or 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 estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in 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 in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /tte::///euui...eeeeeeeee http:///eareppcpppepict//ee/eeee csGuidel ines?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS 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 their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: Our submission is purely foundational and to the best of our knowledge there is clear path any negative applications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an 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 a 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 being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
27

---

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 MI.).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our submission uses only existing public datasets and models.
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 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.
recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: Our submission utilizes existing datasets and pretrained embeddings. We cite the relevant sources in the main text and give additional details on licensing in the supplemental material.
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 (c.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithceee thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license 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
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release assets.
Guidelines:
28

---

The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl 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: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in 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 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 equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending 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 NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
Guidelines:
29

---

The answer NA means that the core method development in this research does not involve LLMs as any important. original, non non-standard components.
Please refer to our LLM policy (https : http///eerppppppeeee cc/Conferrecces/2222 2ttprr/nncee/2///LLL// /LLM)
for what should or should not be described.
30


Reviews:
[{"review_id": "LyiPxokjnT", "reviewer": "Reviewer_xHGk", "summary": "This paper addresses the challenge of accurately estimating the impact of training data removal in high-dimensional machine learning models, where traditional influence functions (IFs) often underestimate the true effects due to their reliance on first-order approximations. The authors propose rescaled influence functions (RIF), a computationally efficient method that incorporates limited higher-order information by leveraging leave-one-out Hessian adjustments while retaining the additivity and scalability of IFs. RIF approximates the Newton step (NS) update—a more accurate but costly second-order approximation—by precomputing leave-one-out Hessian inverses, which can be efficiently derived via matrix inversion lemmas for low-rank updates. Theoretical analysis demonstrates that RIF achieves tighter bounds on prediction errors compared to IFs, particularly when the number of parameters approaches or exceeds the sample size. Experiments across diverse datasets (image, text, audio) confirm RIF’s superior accuracy in predicting leave-T-out effects on test predictions, losses, and self-loss metrics, especially under high-dimensional or weakly regularized settings.", "questions": "1. The theoretical analysis assumes convexity and smooth losses, yet the method is claimed to be model-agnostic. How does RIF perform in highly non-convex settings, such as deep neural networks with multiple local minima? For example, do the rescaling factors derived from leave-one-out Hessians remain stable across different initialization points or training trajectories?\n\n2. The tradeoff between RIF and IF accuracy is shown to depend on regularization strength λ (Figure 2), but how sensitive is RIF to other hyperparameters (e.g., learning rate, batch size during training)? Could stochastic Hessian approximations (e.g., using mini-batch Hessians) destabilize RIF’s rescaling factors in practice?\n\n3. While the paper claims negligible overhead over IFs via Sherman-Morrison updates, how does RIF scale for models with millions of parameters (e.g., transformers)? For instance, in settings where Hessian inversion is approximated via low-rank methods (e.g., Kronecker-factored approximations), does RIF’s accuracy degrade, and what is the wall-clock time/memory footprint?\n\nIf the author can effectively solve the above problems, I will improve my score.", "limitations": "Yes.", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "### Strengths  \n1. The paper addresses a critical limitation of traditional influence functions (IFs)—their inaccuracy in high-dimensional or overparameterized regimes. By introducing rescaled influence functions (RIFs), which incorporate limited second-order information via leave-one-out Hessian adjustments, the authors demonstrate significant accuracy gains over IFs. This is theoretically justified via matrix-perturbation analysis and validated empirically across diverse datasets (image, text, audio). The RIF framework retains the computational efficiency and additivity of IFs while achieving near-Newton-step accuracy, making it a practical drop-in replacement.  \n\n2. RIFs are model-agnostic and task-agnostic, applicable to any empirical risk minimization problem with smooth losses. The method’s ability to detect subtle data poisoning attacks that evade IF-based diagnostics highlights its robustness and utility in security-critical applications. The theoretical analysis also provides tight error bounds under realistic assumptions (e.g., cross-sample incoherence), ensuring reliability in settings where $ n \\approx d $ or $ n \\ll d $, which are common in modern ML.  \n\n3. The experiments span vision, NLP, and audio domains, demonstrating consistent improvements over IFs in predicting leave-T-out effects (test predictions, losses, self-loss). The results include ablation studies on regularization and dimensionality tradeoffs, reinforcing the method’s practicality. For instance, RIFs outperform IFs even in weakly regularized or high-dimensional scenarios (e.g., DogFish dataset), showcasing their versatility.  \n\n---\n\n### Weaknesses  \n1. While the paper claims negligible overhead over IFs (e.g., via Sherman-Morrison updates for low-rank Hessians), the requirement to compute $ n $ leave-one-out Hessian inverses could become prohibitive for extremely large models or datasets. For example, in deep learning with millions of parameters, even low-rank approximations or matrix inversion lemmas may incur non-trivial memory and time costs, limiting RIF’s applicability to resource-constrained settings.  \n\n2. The theoretical guarantees rely on convexity and smooth loss functions, which may not hold for complex, non-convex models like deep neural networks. Although the authors mention extensions to non-convex settings, the empirical validation focuses on logistic regression (a convex problem). This raises questions about RIF’s performance in highly non-convex regimes, where Hessian approximations might be less reliable or require additional stabilization.  \n\n3. While the paper demonstrates RIF’s superiority in detecting synthetic poisoning attacks, it does not evaluate its effectiveness against advanced, real-world data poisoning strategies (e.g., clean-label poisoning or gradient-matching attacks). The experiments focus on simple mislabeling, leaving open whether RIF generalizes to more sophisticated threats. Additionally, the method’s sensitivity to hyperparameters (e.g., regularization strength $ \\lambda $) is only partially explored, potentially affecting reproducibility in practice.", "was_revised": true, "final_justification": "The author's response fails to address the critical issues regarding RIF's dependence on hyperparameters (Question 2) and its lack of scalability to large models (e.g., LLMs, VLMs) (Question 3). Therefore, I consider this work to represent only a minor modification of IF, which reinforces my original recommendation for rejection. I have also increased my Confidence score in this decision. Notably, I observe that other reviewers leaning toward acceptance have relatively low Confidence scores in their evaluations.", "rebuttal": "Thank you for the detailed review and feedback!\n\nThe goal of our paper is to explore the effect of the rescaling phenomenon which leads to rescaled influence functions (RIF), so we decided to aim for the simplest setting where it could be evaluated. Inspired by Koh et al. 2019, we focus on logistic regressions, since they are easy to train and their convexity allows us to evaluate removal effects independent of hyperparameter tuning, while still providing an insight into the behavior of more complex models.\n\nIn general, influence function (IF) data attribution is imperfect and has several flaws – especially in very high-dimensional and non-convex settings. RIF helps address some of these issues but we do not expect it to fix all of them. Below we detail how the ideas behind RIF could be used in combination with techniques such as the random projections and ensembling methods proposed in TRAK (Park et al. 2023), itself an adaptation of IF to very large non-convex models, to reduce the computational cost associated with large Hessians and improve accuracy in non-convex settings.\n\nWhile our initial experiments support the intuitions below, the goal of this paper is to evaluate the effect of rescaling in a simple scenario where it can be accurately measured. We believe that extensions to models so large that accurate Hessian inversion is infeasible, or to non-convex models, are beyond the scope of this paper, though they are natural and important directions for future work. We outline below some ideas regarding how such extensions could work not as a new contribution, but to answer the reviewer’s question regarding the applicability of our results beyond the setting considered in our paper.\n\n\n**Question 1:** Our theoretical analysis focuses on the convex setting because there is very little that we know how to prove about the convergence of deep neural networks in general, and we do not expect to be able to prove any simple statement about which local minimum is reached when optimizing in a non-convex setting. \n\nHowever, we do believe that IF/RIF, applied to a trained model which sits at a local minimum of the loss landscape, would provide an estimate of how that particular local minimum of the landscape would shift under sample removals. For the same reasons as in the convex setting, we expect RIF to provide a more accurate estimate of this shift than IF. We can put together such estimates of the shift of a single local minimum in the same way as TRAK does for IF. \n\nMore concretely, if we are willing to assume that:\n\nSGD converges to some distribution over these local minima \nWhen a small subset of samples are removed, each local minimum itself moves (but local minima do not disappear and new ones are not introduced), and\nWhen a small subset of samples are removed, the distribution over local minima reached by SGD does not change too much,\n\nthen we can use IF, or even better RIF, to provide an estimate of how each of these local minimum is shifted by the sample removal, and then average this estimate over many local minima found via an ensemble of base models, to yield an estimate of the shift in the distribution of trained models (see the Ensembling section of our rebuttal). Moreover, we expect to be able to show this theoretically using essentially the same techniques as in Theorem 3.1.\n\n**Question 2:** This is a very good question. Indeed, Basu et al. 2020 show that the quality of predictions produced by influence functions are very sensitive to such hyper-parameters and ultimately, we expect RIF to have a similar dependence. This is why we chose to focus on logistic regressions, where the rescaling effect (the difference between IF and RIF) can be more easily isolated, and leave the question of the effects of hyper-parameters to future research.\n\n**Question 3:** We expect to be able to use rank-1 inverse-Hessian updates (which allow very fast Sherman-Morrison based evaluation) in most applications, or at worst low-rank updates (which can still be evaluated efficiently using the Woodbury matrix identity), and for our methods to translate well to the K-FAC approximation of the Hessian – see K-FAC section of our rebuttal. \n\nThank you for pointing out the lack of clear comparison of computational costs in our experiments. Below we list the wall-clock runtimes of the base model training, influence function computation and rescaling required for the main experiments of the paper. In all of these cases rescaling accounted for less than 1% of the total runtime. We plan to add a similar table to the camera ready version of the paper should it be accepted.\n\n\n**Larger Models, Approximate Hessians and Efficient Influence Functions**\nOne of the challenges in applying influence functions to larger models is their significant computational overhead, particularly due to the need to compute and invert the Hessian of the loss. Several approaches have been considered for estimating influences without inverting a full loss Hessian, but we will focus on the random projection approach used in TRAK (Park et al. 2023), which is an IF-based data attribution method. We describe how the random projection approach combines cleanly with RIF to approximate the leverage scores used in RIF without the computational cost of a full Hessian inversion. While random projections lead to some loss in accuracy compared to full Hessian inversion, we believe that this loss is unlikely to be any worse for RIF-based data attribution than for IF-based data attribution.\n\nIn this approach, instead of computing $\\langle \\text{IF}, v\\rangle = H^{-1} g$, we select a random projection $\\Pi :\\mathbb{R}^d \\to \\mathbb{R}^{e \\ll d}$ and estimate the model change in this projected space \n$$ \\langle \\text{IF}_{\\text{TRAK}}, v\\rangle \\coloneqq v^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi g \\approx C \\cdot \\langle \\text{IF}, v\\rangle $$ \n\nThis approximation is supported by the Johnson-Lindenstrauss lemma, which states that with high probability, random projections scale down inner products by the ratio of dimensions. In other words, for any fixed vectors $v, w \\in \\mathbb{R}^d$, and a random projection $\\Pi$ that outputs vectors of embedded-dimension $e$, with high probability\n$$ \\langle \\Pi v, \\Pi w\\rangle \\approx \\frac{e}{d} \\langle v,w\\rangle $$\n\nTherefore, in order to capture the correct scaling with a TRAK-inspired version of RIF, for a model with rank-1 Hessian updates (see below why this should suffice even for deeper models), we could use an approximation of the form\n$$\\langle v, \\text{RIF}\\rangle \\approx \\langle v, \\text{RIF}_{\\text{projected}}\\rangle \\coloneqq \\frac{d}{e} \\frac{\\langle \\Pi v, (\\Pi H \\Pi^T)^{-1} \\Pi g_i \\rangle}{1 - L_i}$$\nwhere $L_i = \\frac{d}{e} \\beta_i v_i^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi v_i$ approximates the $i$th leverage.\n\nDue to the Johnson Lindenstrauss lemma, we expect this method to produce an accurate estimate of the exact RIF.\n\n**Ensembling and Non-Convex Models**\nAnother major challenge with using influence functions for deeper neural nets is the fact that loss minimization for deep neural networks is a nonconvex problem. Therefore, each training run will approach a different local minimum. \n\nInspired by TRAK, we think of the influence function as estimating the shift of a single local minimum due to the removal of a set of samples. Instead of the influence function evaluated at a single trained model, TRAK uses an ensemble of trained models and averages the influence function estimates of their change under sample removal. This can be viewed as an estimate of the overall drift of the local minima.\n\nWe expect that plugging in RIF rather than IF to the TRAK approach should yield a better estimate of the overall drift. This is because, while we expect influence functions to capture the direction of change of each local minima, we do not expect it to capture the scale of this change. By contrast, just as in the convex setting, we expect that RIF accurately captures both the direction and magnitude of the change in the location of a local minimum when a sample is removed from the training set.\n\n**K-FAC and Low-Rank Hessian Updates**\nAnother observation which we did not mention in the paper is that the low-rank inverse-Hessian updates needed for RIF can be evaluated efficiently via Sherman-Morrison even for deeper neural nets provided they use ReLU activation. This is an important factor in ensuring that RIF can be evaluated with little overhead compared to IF even beyond logistic regression.\n\nThis is because Neural Networks with ReLU activations are piece-wise linear as a function of the network input, meaning that, locally, each sample's contribution to the Hessian is exactly equal to its approximation to the Hessian of its NTK-based logistic regression (i.e., the K-FAC approximation is exact in this sense).\n\nFor deeper neural networks with other activation functions, the rank of the Hessian update would be at most equal to the depth of the neural network. However, we expect that a rescaling based on the rank-1 Hessian update corresponding to the NTK approximation would be a good approximation to the leave-one-out Hessian.\n\nAll of these updates are rank-1, allowing for fast evaluation using the Sherman-Morrison formula and using the low-rank embedding procedure described above.\n\n**Comparison of Runtimes**\n\n| Dataset      | Training | Hessian | Inversion | Influence | Rescaling        |\n|--------------|----------|---------|-----------|-----------|------------------|\n| ESC50        | 1.8 s    | 0.056 s | 0.0005 s  | 0.051 s   | 0.0033 s (0.2%)  |\n| CatDog       | 76 s     | 4.9 s   | 0.010 s   | 4.8 s     | 0.087 s (0.1%)   |\n| AutoTruck    | 48 s     | 4.9 s   | 0.0094 s  | 4.8 s     | 0.087 s (0.2%)   |\n| DogFish      | 0.43 s   | 0.92 s  | 0.0095 s  | 0.89 s    | 0.015 s (0.7%)   |\n| Enron        | 6.7 s    | 15 s    | 0.065 s   | 15 s      | 0.095 s (0.3%)   |\n| IMDB ($n=16d$) | 20 s     | 0.92 s  | 0.0012 s  | 0.87 s    | 0.044 s (0.2%)   |"}, {"review_id": "X1YSw5YlPB", "reviewer": "Reviewer_XBFo", "summary": "The paper introduces Rescaled Influence Functions (RIF), a straightforward multiplicative re-weighting approach applied to classical influence-function scores to correct their tendency to underestimate leave-T-out effects in high-dimensional and over-parameterized models.\n\nRIF maintains the attractive additivity and computational simplicity of first-order influence functions (IF), while achieving accuracy comparable to one-step Newton updates. Extensive experiments conducted across six diverse benchmarks—covering vision, audio, and NLP domains—demonstrate substantial accuracy improvements over IF, often by an order of magnitude. Additionally, a toy data-poisoning demonstration highlights the practical applicability of the method. The paper also provides theoretical insights supporting the method’s robustness and approximation quality in high-dimensional (low SNR) settings.", "questions": "See weaknesses, sorry dont have strong questions. Will read other reviews to form a better opinion.", "limitations": "None", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n**Clarity:** The paper successfully motivates the setting, even for readers who may not be deeply familiar with the topic. The methodology is clear and approachable, and the results are presented in a well-structured manner.\n\n**Novelty and Potential:** The paper addresses a well-known limitation of IFs within modern, over-parameterized models, offering an elegant and straightforward solution with substantial potential for various applications.\n\n**Robust Empirical and Theoretical Support:** The empirical evaluation is extensive, covering image datasets (CIFAR-10, ImageNet), audio (ESC-50), and text (Enron spam). The variety of subset-selection strategies employed further strengthens the external validity of the results. Additionally, the theoretical analysis is well-developed and offers convincing guarantees.\n\n## Weaknesses\n\nApplications to Non-linear Functions: While the experiments are comprehensive within their chosen settings, the paper currently limits evaluation to logistic regression on frozen features. Could the authors clarify how the method might extend to more complex scenarios involving deep-network fine-tuning, large language models (LLMs), or Transformer-based vision architectures? This would help readers better understand potential limitations or challenges in scaling the method.\n\nComparison to other scalable methods: The primary theoretical results currently require convex losses and Hessians. Given the substantial computational challenges posed by billion-parameter models, such as difficulties with Hessian-vector products, could the authors elaborate on how other approaches like TRAK or FastIF perform?\n\nOverall, the paper presents cool insights -- I really liked reading it and think it could be interesting to see at NeurIPS", "was_revised": true, "final_justification": "All of my questions have been addressed, I maintain my score.", "rebuttal": "Thank you for the detailed review and feedback!\n\nThe goal of our paper is to explore the effect of the rescaling phenomenon which leads to rescaled influence functions (RIF), so we decided to aim for the simplest setting where it could be evaluated. Inspired by Koh et al. 2019, we focus on logistic regressions, since they are easy to train and their convexity allows us to evaluate removal effects independent of hyperparameter tuning, while still providing an insight into the behavior of more complex models.\n\nIn general, influence function (IF) data attribution is imperfect and has several flaws – especially in very high-dimensional and non-convex settings. RIF helps address some of these issues but we do not expect it to fix all of them. Below we detail how the ideas behind RIF could be used in combination with techniques such as the random projections and ensembling methods proposed in TRAK (Park et al. 2023), itself an adaptation of IF to very large non-convex models, to reduce the computational cost associated with large Hessians and improve accuracy in non-convex settings.\n\nWhile our initial experiments support the intuitions below, the goal of this paper is to evaluate the effect of rescaling in a simple scenario where it can be accurately measured. We believe that extensions to models so large that accurate Hessian inversion is infeasible, or to non-convex models, are beyond the scope of this paper, though they are natural and important directions for future work. We outline below some ideas regarding how such extensions could work not as a new contribution, but to answer the reviewer’s question regarding the applicability of our results beyond the setting considered in our paper.\n\n**Reviewer Questions**\nWe discuss below how we expect RIF to apply to larger models with non-convex loss landscapes, although we leave thorough experimental investigation of this important question to future work. In particular, we address how to combine insights from TRAK with RIF to mitigate the computational burden of Hessian inversion, we discuss why the leave-one-out Hessian inverses needed by RIF remain relatively fast to compute in neural net settings, and we discuss why the idea from TRAK to handle non-convexity by averaging the IF over many training runs carries over to RIF.\n\n\n**Larger Models, Approximate Hessians and Efficient Influence Functions**\nOne of the challenges in applying influence functions to larger models is their significant computational overhead, particularly due to the need to compute and invert the Hessian of the loss. Several approaches have been considered for estimating influences without inverting a full loss Hessian, but we will focus on the random projection approach used in TRAK (Park et al. 2023), which is an IF-based data attribution method. We describe how the random projection approach combines cleanly with RIF to approximate the leverage scores used in RIF without the computational cost of a full Hessian inversion. While random projections lead to some loss in accuracy compared to full Hessian inversion, we believe that this loss is unlikely to be any worse for RIF-based data attribution than for IF-based data attribution.\n\nIn this approach, instead of computing $\\langle \\text{IF}, v\\rangle = H^{-1} g$, we select a random projection $\\Pi :\\mathbb{R}^d \\to \\mathbb{R}^{e \\ll d}$ and estimate the model change in this projected space \n$$ \\langle \\text{IF}_{\\text{TRAK}}, v\\rangle \\coloneqq v^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi g \\approx C \\cdot \\langle \\text{IF}, v\\rangle $$ \n\nThis approximation is supported by the Johnson-Lindenstrauss lemma, which states that with high probability, random projections scale down inner products by the ratio of dimensions. In other words, for any fixed vectors $v, w \\in \\mathbb{R}^d$, and a random projection $\\Pi$ that outputs vectors of embedded-dimension $e$, with high probability\n$$ \\langle \\Pi v, \\Pi w\\rangle \\approx \\frac{e}{d} \\langle v,w\\rangle $$\n\nTherefore, in order to capture the correct scaling with a TRAK-inspired version of RIF, for a model with rank-1 Hessian updates (see below why this should suffice even for deeper models), we could use an approximation of the form\n$$\\langle v, \\text{RIF}\\rangle \\approx \\langle v, \\text{RIF}_{\\text{projected}}\\rangle \\coloneqq \\frac{d}{e} \\frac{\\langle \\Pi v, (\\Pi H \\Pi^T)^{-1} \\Pi g_i \\rangle}{1 - L_i}$$\nwhere $L_i = \\frac{d}{e} \\beta_i v_i^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi v_i$ approximates the $i$th leverage.\n\nDue to the Johnson Lindenstrauss lemma, we expect this method to produce an accurate estimate of the exact RIF.\n\n**Ensembling and Non-Convex Models**\nAnother major challenge with using influence functions for deeper neural nets is the fact that loss minimization for deep neural networks is a nonconvex problem. Therefore, each training run will approach a different local minimum. \n\nInspired by TRAK, we think of the influence function as estimating the shift of a single local minimum due to the removal of a set of samples. Instead of the influence function evaluated at a single trained model, TRAK uses an ensemble of trained models and averages the influence function estimates of their change under sample removal. This can be viewed as an estimate of the overall drift of the local minima.\n\nWe expect that plugging in RIF rather than IF to the TRAK approach should yield a better estimate of the overall drift. This is because, while we expect influence functions to capture the direction of change of each local minima, we do not expect it to capture the scale of this change. By contrast, just as in the convex setting, we expect that RIF accurately captures both the direction and magnitude of the change in the location of a local minimum when a sample is removed from the training set.\n\n**K-FAC and Low-Rank Hessian Updates**\nAnother observation which we did not mention in the paper is that the low-rank inverse-Hessian updates needed for RIF can be evaluated efficiently via Sherman-Morrison even for deeper neural nets provided they use ReLU activation. This is an important factor in ensuring that RIF can be evaluated with little overhead compared to IF even beyond logistic regression.\n\nThis is because Neural Networks with ReLU activations are piece-wise linear as a function of the network input, meaning that, locally, each sample's contribution to the Hessian is exactly equal to its approximation to the Hessian of its NTK-based logistic regression (i.e., the K-FAC approximation is exact in this sense).\n\nFor deeper neural networks with other activation functions, the rank of the Hessian update would be at most equal to the depth of the neural network. However, we expect that a rescaling based on the rank-1 Hessian update corresponding to the NTK approximation would be a good approximation to the leave-one-out Hessian.\n\nAll of these updates are rank-1, allowing for fast evaluation using the Sherman-Morrison formula and using the low-rank embedding procedure described above.\n\n**Comparison of Runtimes**\n\n| Dataset      | Training | Hessian | Inversion | Influence | Rescaling        |\n|--------------|----------|---------|-----------|-----------|------------------|\n| ESC50        | 1.8 s    | 0.056 s | 0.0005 s  | 0.051 s   | 0.0033 s (0.2%)  |\n| CatDog       | 76 s     | 4.9 s   | 0.010 s   | 4.8 s     | 0.087 s (0.1%)   |\n| AutoTruck    | 48 s     | 4.9 s   | 0.0094 s  | 4.8 s     | 0.087 s (0.2%)   |\n| DogFish      | 0.43 s   | 0.92 s  | 0.0095 s  | 0.89 s    | 0.015 s (0.7%)   |\n| Enron        | 6.7 s    | 15 s    | 0.065 s   | 15 s      | 0.095 s (0.3%)   |\n| IMDB ($n=16d$) | 20 s     | 0.92 s  | 0.0012 s  | 0.87 s    | 0.044 s (0.2%)   |"}, {"review_id": "GAunJ8gVaC", "reviewer": "Reviewer_qLFf", "summary": "This paper proposes a new method for influence functions that leverages Newton steps to compute the influence of individual samples, and then additively aggregates them to evaluate the influence of a subset. The method, called RIF, demonstrates improved performance over standard influence functions (IF) in the context of logistic regression across various scenarios, showing gains in both prediction accuracy and loss values.\nRIF is also more effective in mitigating the impact of poisoned samples.\n\nThese improvements, however, come at the cost of additional computational overhead due to the need to compute the inverse Hessian matrix for each individual point.", "questions": "Mentioned in the weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nThe paper considers a variety of scenarios and employs multiple metrics to evaluate accuracy and compare against standard Influence Functions (IF).\nThe theoretical development appears sound, correct, and thorough.\nThe additional computational overhead introduced by RIF seems justified given the observed improvements.\n\nWeaknesses:\nThe main novelty of the paper—using Newton steps only for individual samples and then additively computing subset influence—is not particularly strong.\nMoreover, the focus on logistic regression is somewhat narrow. Could the authors provide experimental results on more complex models? It would also be useful to compare IF and RIF in settings where influence is approximated, which is the typical use case of influence functions.", "was_revised": true, "final_justification": "I think a borderline accept is an appropriate recommendation, as I am not sufficiently expert in this specific area to confidently recommend acceptance.", "rebuttal": "Thank you for the detailed review and feedback!\n\nThe goal of our paper is to explore the effect of the rescaling phenomenon which leads to rescaled influence functions (RIF), so we decided to aim for the simplest setting where it could be evaluated. Inspired by Koh et al. 2019, we focus on logistic regressions, since they are easy to train and their convexity allows us to evaluate removal effects independent of hyperparameter tuning, while still providing an insight into the behavior of more complex models.\n\nIn general, influence function (IF) data attribution is imperfect and has several flaws – especially in very high-dimensional and non-convex settings. RIF helps address some of these issues but we do not expect it to fix all of them. Below we detail how the ideas behind RIF could be used in combination with techniques such as the random projections and ensembling methods proposed in TRAK (Park et al. 2023), itself an adaptation of IF to very large non-convex models, to reduce the computational cost associated with large Hessians and improve accuracy in non-convex settings.\n\nWhile our initial experiments support the intuitions below, the goal of this paper is to evaluate the effect of rescaling in a simple scenario where it can be accurately measured. We believe that extensions to models so large that accurate Hessian inversion is infeasible, or to non-convex models, are beyond the scope of this paper, though they are natural and important directions for future work. We outline below some ideas regarding how such extensions could work not as a new contribution, but to answer the reviewer’s question regarding the applicability of our results beyond the setting considered in our paper.\n\n\n**Reviewer Questions**\nWe discuss below why we choose to focus on logistic regression. Regarding experiments with more complex models: while new results are out of scope for this rebuttal (see email from NeurIPS PC chairs with subject “Notes about rebuttal format”, which requests rebuttals discussing the current merits of the paper), we discuss below several of the key difficulties we would face in applying RIF to larger and more complex models below, and why we expect them to be surmountable.\n\n\n**Larger Models, Approximate Hessians and Efficient Influence Functions**\nOne of the challenges in applying influence functions to larger models is their significant computational overhead, particularly due to the need to compute and invert the Hessian of the loss. Several approaches have been considered for estimating influences without inverting a full loss Hessian, but we will focus on the random projection approach used in TRAK (Park et al. 2023), which is an IF-based data attribution method. We describe how the random projection approach combines cleanly with RIF to approximate the leverage scores used in RIF without the computational cost of a full Hessian inversion. While random projections lead to some loss in accuracy compared to full Hessian inversion, we believe that this loss is unlikely to be any worse for RIF-based data attribution than for IF-based data attribution.\n\nIn this approach, instead of computing $\\langle \\text{IF}, v\\rangle = H^{-1} g$, we select a random projection $\\Pi :\\mathbb{R}^d \\to \\mathbb{R}^{e \\ll d}$ and estimate the model change in this projected space \n$$ \\langle \\text{IF}_{\\text{TRAK}}, v\\rangle \\coloneqq v^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi g \\approx C \\cdot \\langle \\text{IF}, v\\rangle $$ \n\nThis approximation is supported by the Johnson-Lindenstrauss lemma, which states that with high probability, random projections scale down inner products by the ratio of dimensions. In other words, for any fixed vectors $v, w \\in \\mathbb{R}^d$, and a random projection $\\Pi$ that outputs vectors of embedded-dimension $e$, with high probability\n$$ \\langle \\Pi v, \\Pi w\\rangle \\approx \\frac{e}{d} \\langle v,w\\rangle $$\n\nTherefore, in order to capture the correct scaling with a TRAK-inspired version of RIF, for a model with rank-1 Hessian updates (see below why this should suffice even for deeper models), we could use an approximation of the form\n$$\\langle v, \\text{RIF}\\rangle \\approx \\langle v, \\text{RIF}_{\\text{projected}}\\rangle \\coloneqq \\frac{d}{e} \\frac{\\langle \\Pi v, (\\Pi H \\Pi^T)^{-1} \\Pi g_i \\rangle}{1 - L_i}$$\nwhere $L_i = \\frac{d}{e} \\beta_i v_i^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi v_i$ approximates the $i$th leverage.\n\nDue to the Johnson Lindenstrauss lemma, we expect this method to produce an accurate estimate of the exact RIF.\n\n**Ensembling and Non-Convex Models**\nAnother major challenge with using influence functions for deeper neural nets is the fact that loss minimization for deep neural networks is a nonconvex problem. Therefore, each training run will approach a different local minimum. \n\nInspired by TRAK, we think of the influence function as estimating the shift of a single local minimum due to the removal of a set of samples. Instead of the influence function evaluated at a single trained model, TRAK uses an ensemble of trained models and averages the influence function estimates of their change under sample removal. This can be viewed as an estimate of the overall drift of the local minima.\n\nWe expect that plugging in RIF rather than IF to the TRAK approach should yield a better estimate of the overall drift. This is because, while we expect influence functions to capture the direction of change of each local minima, we do not expect it to capture the scale of this change. By contrast, just as in the convex setting, we expect that RIF accurately captures both the direction and magnitude of the change in the location of a local minimum when a sample is removed from the training set.\n\n**K-FAC and Low-Rank Hessian Updates**\nAnother observation which we did not mention in the paper is that the low-rank inverse-Hessian updates needed for RIF can be evaluated efficiently via Sherman-Morrison even for deeper neural nets provided they use ReLU activation. This is an important factor in ensuring that RIF can be evaluated with little overhead compared to IF even beyond logistic regression.\n\nThis is because Neural Networks with ReLU activations are piece-wise linear as a function of the network input, meaning that, locally, each sample's contribution to the Hessian is exactly equal to its approximation to the Hessian of its NTK-based logistic regression (i.e., the K-FAC approximation is exact in this sense).\n\nFor deeper neural networks with other activation functions, the rank of the Hessian update would be at most equal to the depth of the neural network. However, we expect that a rescaling based on the rank-1 Hessian update corresponding to the NTK approximation would be a good approximation to the leave-one-out Hessian.\n\nAll of these updates are rank-1, allowing for fast evaluation using the Sherman-Morrison formula and using the low-rank embedding procedure described above.\n\n**Comparison of Runtimes**\n\n| Dataset      | Training | Hessian | Inversion | Influence | Rescaling        |\n|--------------|----------|---------|-----------|-----------|------------------|\n| ESC50        | 1.8 s    | 0.056 s | 0.0005 s  | 0.051 s   | 0.0033 s (0.2%)  |\n| CatDog       | 76 s     | 4.9 s   | 0.010 s   | 4.8 s     | 0.087 s (0.1%)   |\n| AutoTruck    | 48 s     | 4.9 s   | 0.0094 s  | 4.8 s     | 0.087 s (0.2%)   |\n| DogFish      | 0.43 s   | 0.92 s  | 0.0095 s  | 0.89 s    | 0.015 s (0.7%)   |\n| Enron        | 6.7 s    | 15 s    | 0.065 s   | 15 s      | 0.095 s (0.3%)   |\n| IMDB ($n=16d$) | 20 s     | 0.92 s  | 0.0012 s  | 0.87 s    | 0.044 s (0.2%)   |"}, {"review_id": "YMcD3Jm7yg", "reviewer": "Reviewer_qech", "summary": "Summary: This paper introduces a new data attribution method, Rescaled Influence Functions (RIF), that aims to more accurately estimate the effects of sample removal over the original IF method, and more efficient to compute than Newton Step (NS) by performing NS approximation.\n\nThe paper demonstrated empirically that, especially under overparameterized settings, RIF is able to estimate the leave-T-out effect at a similar accuracy of NS while offering significantly less computational overhead.", "questions": "Questions:\n\n1. Wouldn’t it be clearer to present the empirical results (Section 2) after introducing the assumptions and theorems (Section 3)?\n\n2. Could the authors suggest a few potential future research directions to build on the proposed RIF?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. Strong empirical results and thorough evaluation. Evaluated against many different settings and RIF seems to have consistently outperformed over standard IF.\n2. Provides a theoretical bound on the error between RIF and NS.\n\nWeakness:\n\n1. While the paper mentions that RIF has a computational overhead compared to standard IF, this aspect is not measured in detail beyond Section 1. It would be helpful to see empirical results showing the computational cost of each method on different datasets, similar to Figure 1 for accuracy.", "was_revised": true, "final_justification": "Questions and concerns have been addressed / answered accordingly.", "rebuttal": "Thank you for the detailed review and feedback!\n\nThe goal of our paper is to explore the effect of the rescaling phenomenon which leads to rescaled influence functions (RIF), so we decided to aim for the simplest setting where it could be evaluated. Inspired by Koh et al. 2019, we focus on logistic regressions, since they are easy to train and their convexity allows us to evaluate removal effects independent of hyperparameter tuning, while still providing an insight into the behavior of more complex models.\n\nIn general, influence function (IF) data attribution is imperfect and has several flaws – especially in very high-dimensional and non-convex settings. RIF helps address some of these issues but we do not expect it to fix all of them. Below we detail how the ideas behind RIF could be used in combination with techniques such as the random projections and ensembling methods proposed in TRAK (Park et al. 2023), itself an adaptation of IF to very large non-convex models, to reduce the computational cost associated with large Hessians and improve accuracy in non-convex settings.\n\nWhile our initial experiments support the intuitions below, the goal of this paper is to evaluate the effect of rescaling in a simple scenario where it can be accurately measured. We believe that extensions to models so large that accurate Hessian inversion is infeasible, or to non-convex models, are beyond the scope of this paper, though they are natural and important directions for future work. We outline below some ideas regarding how such extensions could work not as a new contribution, but to answer the reviewer’s question regarding the applicability of our results beyond the setting considered in our paper.\n\n**Reviewer Questions**\n\n**Weakness 1.** Thank you for pointing out the lack of clear comparison of computational costs in our experiments. Below we list the wall-clock runtimes of the base model training, influence function computation and rescaling required for the main experiments of the paper. In all of these cases rescaling accounted for less than 1% of the total runtime. We plan to add a similar table to the camera ready version of the paper should it be accepted.\n\n**Question 1.** We chose this order because we feel that the empirical results are easy to interpret and convincing.\n\n**Question 2.** Certainly. One natural direction, discussed in detail below, is to apply RIFs to improve state-of-the-art data attribution in larger and non-convex models (e.g. neural nets). Another is to use RIF, or the ideas behind it, to improve on other existing uses of influence functions, such as for leave-k-out cross-validation and approximation of data Shapley values.\n\n**Larger Models, Approximate Hessians and Efficient Influence Functions**\nOne of the challenges in applying influence functions to larger models is their significant computational overhead, particularly due to the need to compute and invert the Hessian of the loss. Several approaches have been considered for estimating influences without inverting a full loss Hessian, but we will focus on the random projection approach used in TRAK (Park et al. 2023), which is an IF-based data attribution method. We describe how the random projection approach combines cleanly with RIF to approximate the leverage scores used in RIF without the computational cost of a full Hessian inversion. While random projections lead to some loss in accuracy compared to full Hessian inversion, we believe that this loss is unlikely to be any worse for RIF-based data attribution than for IF-based data attribution.\n\nIn this approach, instead of computing $\\langle \\text{IF}, v\\rangle = H^{-1} g$, we select a random projection $\\Pi :\\mathbb{R}^d \\to \\mathbb{R}^{e \\ll d}$ and estimate the model change in this projected space \n$$ \\langle \\text{IF}_{\\text{TRAK}}, v\\rangle \\coloneqq v^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi g \\approx C \\cdot \\langle \\text{IF}, v\\rangle $$ \n\nThis approximation is supported by the Johnson-Lindenstrauss lemma, which states that with high probability, random projections scale down inner products by the ratio of dimensions. In other words, for any fixed vectors $v, w \\in \\mathbb{R}^d$, and a random projection $\\Pi$ that outputs vectors of embedded-dimension $e$, with high probability\n$$ \\langle \\Pi v, \\Pi w\\rangle \\approx \\frac{e}{d} \\langle v,w\\rangle $$\n\nTherefore, in order to capture the correct scaling with a TRAK-inspired version of RIF, for a model with rank-1 Hessian updates (see below why this should suffice even for deeper models), we could use an approximation of the form\n$$\\langle v, \\text{RIF}\\rangle \\approx \\langle v, \\text{RIF}_{\\text{projected}}\\rangle \\coloneqq \\frac{d}{e} \\frac{\\langle \\Pi v, (\\Pi H \\Pi^T)^{-1} \\Pi g_i \\rangle}{1 - L_i}$$\nwhere $L_i = \\frac{d}{e} \\beta_i v_i^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi v_i$ approximates the $i$th leverage.\n\nDue to the Johnson Lindenstrauss lemma, we expect this method to produce an accurate estimate of the exact RIF.\n\n**Ensembling and Non-Convex Models**\nAnother major challenge with using influence functions for deeper neural nets is the fact that loss minimization for deep neural networks is a nonconvex problem. Therefore, each training run will approach a different local minimum. \n\nInspired by TRAK, we think of the influence function as estimating the shift of a single local minimum due to the removal of a set of samples. Instead of the influence function evaluated at a single trained model, TRAK uses an ensemble of trained models and averages the influence function estimates of their change under sample removal. This can be viewed as an estimate of the overall drift of the local minima.\n\nWe expect that plugging in RIF rather than IF to the TRAK approach should yield a better estimate of the overall drift. This is because, while we expect influence functions to capture the direction of change of each local minima, we do not expect it to capture the scale of this change. By contrast, just as in the convex setting, we expect that RIF accurately captures both the direction and magnitude of the change in the location of a local minimum when a sample is removed from the training set.\n\n**K-FAC and Low-Rank Hessian Updates**\nAnother observation which we did not mention in the paper is that the low-rank inverse-Hessian updates needed for RIF can be evaluated efficiently via Sherman-Morrison even for deeper neural nets provided they use ReLU activation. This is an important factor in ensuring that RIF can be evaluated with little overhead compared to IF even beyond logistic regression.\n\nThis is because Neural Networks with ReLU activations are piece-wise linear as a function of the network input, meaning that, locally, each sample's contribution to the Hessian is exactly equal to its approximation to the Hessian of its NTK-based logistic regression (i.e., the K-FAC approximation is exact in this sense).\n\nFor deeper neural networks with other activation functions, the rank of the Hessian update would be at most equal to the depth of the neural network. However, we expect that a rescaling based on the rank-1 Hessian update corresponding to the NTK approximation would be a good approximation to the leave-one-out Hessian.\n\nAll of these updates are rank-1, allowing for fast evaluation using the Sherman-Morrison formula and using the low-rank embedding procedure described above.\n\n**Comparison of Runtimes**\n\n| Dataset      | Training | Hessian | Inversion | Influence | Rescaling        |\n|--------------|----------|---------|-----------|-----------|------------------|\n| ESC50        | 1.8 s    | 0.056 s | 0.0005 s  | 0.051 s   | 0.0033 s (0.2%)  |\n| CatDog       | 76 s     | 4.9 s   | 0.010 s   | 4.8 s     | 0.087 s (0.1%)   |\n| AutoTruck    | 48 s     | 4.9 s   | 0.0094 s  | 4.8 s     | 0.087 s (0.2%)   |\n| DogFish      | 0.43 s   | 0.92 s  | 0.0095 s  | 0.89 s    | 0.015 s (0.7%)   |\n| Enron        | 6.7 s    | 15 s    | 0.065 s   | 15 s      | 0.095 s (0.3%)   |\n| IMDB ($n=16d$) | 20 s     | 0.92 s  | 0.0012 s  | 0.87 s    | 0.044 s (0.2%)   |"}, {"review_id": "wsZnIJZg5m", "reviewer": "Reviewer_CdeV", "summary": "The paper presents rescaled influence functions, which make use of per-sample Hessians to rescale influence functions and achieve improved accuracy in capturing true training data attribution, especially for group influence, while preserving the linearity of group influence.", "questions": "- How strongly would a poor estimation of the Hessian affect the error in RIF compared to IF? Would the rescaling through poor leverage scores increase the error?\n- How stable are RIFs wrt the randomness from the training process in non-convex models? Do you maybe have some insights from your experiments with e.g. ResNet50?", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper presents a theoretically-grounded improvement to influence functions and underlines their analysis with empirical evidence with experiments with different model types and data modalities.\n- The proposed method is simple to implement and therefore likely easy to adopt. \n\nWeaknesses:\n- Influence functions are known to be fragile in deep learning [a], which limits their applicability. The paper does not present a sensitivity analysis of RIF to test whether they are also fragile or improve IF also in this regard. \n\n[a] Basu et al. (2020): Influence Functions in deep learning are fragile.", "was_revised": true, "final_justification": "I recommend accepting this paper because it is a well-written paper proposing a simple and principled approach to improve influence functions that has yielded convincing empirical results.", "rebuttal": "Thank you for the detailed review and feedback!\n\n**Reviewer Questions**\n\n**Question 1:** This depends on how the Hessian is approximated. Common approaches to efficiently estimating the Hessian of deeper neural nets (e.g., as used in TRAK - Park et al. 2023), is to use a combination of K-FAC (to avoid having to directly differentiate the model to a second order) and Random Projection to a lower dimensional embedding (for faster linear algebra). Below, we expand on each of these methods and why we expect them to work well within the framework of RIF.\n\n**Question 2:** We have not yet run a comprehensive set of experiments into this question. Our experience so far supports the intuition detailed below (see Ensembling and Non-Convex Models) that RIF produces a good estimate on how each local minimum is shifted by sample removals and that the distribution of local minima approached by the model is fairly robust under sample removals, allowing us to capture the overall drift of the population of local minima by using an ensemble average RIF over a large number of initial models.\n\n\n**Larger Models, Approximate Hessians and Efficient Influence Functions**\n\nOne of the challenges in applying influence functions to larger models is their significant computational overhead, particularly due to the need to compute and invert the Hessian of the loss. Several approaches have been considered for estimating influences without inverting a full loss Hessian, but we will focus on the random projection approach used in TRAK (Park et al. 2023), which is an IF-based data attribution method. We describe how the random projection approach combines cleanly with RIF to approximate the leverage scores used in RIF without the computational cost of a full Hessian inversion. While random projections lead to some loss in accuracy compared to full Hessian inversion, we believe that this loss is unlikely to be any worse for RIF-based data attribution than for IF-based data attribution.\n\nIn this approach, instead of computing $\\langle \\text{IF}, v\\rangle = H^{-1} g$, we select a random projection $\\Pi :\\mathbb{R}^d \\to \\mathbb{R}^{e \\ll d}$ and estimate the model change in this projected space \n$$ \\langle \\text{IF}_{\\text{TRAK}}, v\\rangle \\coloneqq v^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi g \\approx C \\cdot \\langle \\text{IF}, v\\rangle $$ \n\nThis approximation is supported by the Johnson-Lindenstrauss lemma, which states that with high probability, random projections scale down inner products by the ratio of dimensions. In other words, for any fixed vectors $v, w \\in \\mathbb{R}^d$, and a random projection $\\Pi$ that outputs vectors of embedded-dimension $e$, with high probability\n$$ \\langle \\Pi v, \\Pi w\\rangle \\approx \\frac{e}{d} \\langle v,w\\rangle $$\n\nTherefore, in order to capture the correct scaling with a TRAK-inspired version of RIF, for a model with rank-1 Hessian updates (see below why this should suffice even for deeper models), we could use an approximation of the form\n$$\\langle v, \\text{RIF}\\rangle \\approx \\langle v, \\text{RIF}_{\\text{projected}}\\rangle \\coloneqq \\frac{d}{e} \\frac{\\langle \\Pi v, (\\Pi H \\Pi^T)^{-1} \\Pi g_i \\rangle}{1 - L_i}$$\nwhere $L_i = \\frac{d}{e} \\beta_i v_i^T \\Pi^T (\\Pi H \\Pi^T)^{-1} \\Pi v_i$ approximates the $i$th leverage.\n\nDue to the Johnson Lindenstrauss lemma, we expect this method to produce an accurate estimate of the exact RIF.\n\n**Ensembling and Non-Convex Models**\n\nAnother major challenge with using influence functions for deeper neural nets is the fact that loss minimization for deep neural networks is a nonconvex problem. Therefore, each training run will approach a different local minimum. \n\nInspired by TRAK, we think of the influence function as estimating the shift of a single local minimum due to the removal of a set of samples. Instead of the influence function evaluated at a single trained model, TRAK uses an ensemble of trained models and averages the influence function estimates of their change under sample removal. This can be viewed as an estimate of the overall drift of the local minima.\n\nWe expect that plugging in RIF rather than IF to the TRAK approach should yield a better estimate of the overall drift. This is because, while we expect influence functions to capture the direction of change of each local minima, we do not expect it to capture the scale of this change. By contrast, just as in the convex setting, we expect that RIF accurately captures both the direction and magnitude of the change in the location of a local minimum when a sample is removed from the training set.\n\n**K-FAC and Low-Rank Hessian Updates**\nAnother observation which we did not mention in the paper is that the low-rank inverse-Hessian updates needed for RIF can be evaluated efficiently via Sherman-Morrison even for deeper neural nets provided they use ReLU activation. This is an important factor in ensuring that RIF can be evaluated with little overhead compared to IF even beyond logistic regression.\n\nThis is because Neural Networks with ReLU activations are piece-wise linear as a function of the network input, meaning that, locally, each sample's contribution to the Hessian is exactly equal to its approximation to the Hessian of its NTK-based logistic regression (i.e., the K-FAC approximation is exact in this sense).\n\nFor deeper neural networks with other activation functions, the rank of the Hessian update would be at most equal to the depth of the neural network. However, we expect that a rescaling based on the rank-1 Hessian update corresponding to the NTK approximation would be a good approximation to the leave-one-out Hessian.\n\nAll of these updates are rank-1, allowing for fast evaluation using the Sherman-Morrison formula and using the low-rank embedding procedure described above."}]

Author rebuttal:

Meta-review: This work handles a critical limitation of traditional influence functions, namely, their inaccuracy in high-dimensional or over-parameterized regimes. As pointed out by reviewers, this work well addresses the well-known limitation of IFs within modern over-parameterized models, and provides an elegant and straightforward solution with substantial potential for different applications. The authors have done extensive experiments, which show the effectiveness of this work. Due to the contributions of this work, 4 out of the 5 reviewers recommend acceptance. Considering the importance of the addressed problem, and the effectiveness of the method, AC recommends acceptance, but urges the authors to improve the final version following reviewers' comments.
Decision: Accept (poster)