GEX: A flexible method for approximating influence via Geometric Ensemble
Authors: SungYub Kim
Kyungsu Kim
Eunho Yang
Venue: NeurIPS 2023 poster (2023)
Keywords: Influence Function
Geometric Ensemble
Loss Landscape

Abstract: Through a deeper understanding of predictions of neural networks, Influence Function (IF) has been applied to various tasks such as detecting and relabeling mislabeled samples, dataset pruning, and separation of data sources in practice. However, we found standard approximations of IF suffer from performance degradation due to oversimplified influence distributions caused by their bilinear approximation, suppressing the expressive power of samples with a relatively strong influence. To address this issue, we propose a new interpretation of existing IF approximations as an average relationship between two linearized losses over parameters sampled from the Laplace approximation (LA). In doing so, we highlight two significant limitations of current IF approximations: the linearity of gradients and the singularity of Hessian. Accordingly, by improving each point, we introduce a new IF approximation method with the following features: i) the removal of linearization to alleviate the bilinear constraint and ii) the utilization of Geometric Ensemble (GE) tailored for non-linear losses. Empirically, our approach outperforms existing IF approximations for downstream tasks with lighter computation, thereby providing new feasibility of low-complexity/nonlinear-based IF design.

GEX: A flexible method for approximating influence via Geometric Ensemble
Sung-Yub Yub Kim
Kyungsu Kim
Graduate School of AI, KAIST sungyub. kim@kaise st. kc
Massachusetts General Hospital and Harvard Medical School kskim doc@gmail. com
Eunho Yang!
Graduate School of AI, KAIST and AITRICS eunhoy@kaist.. ac
Abstract
Through deeper understanding of predictions neural networks, Influence Func- tion (IF) has been applied to various tasks such as detecting and relabeling misla- beled samples, dataset pruning, and separation data sources in practice. However, found standard approximations of IF suffer from performance degradation due to oversimplified influence distributions caused by their bilinear approximation, suppressing the expressive power of samples with relatively strong influence. To address this issue, we propose new interpretation of existing IF approximations average relationship between two linearized losses parameters sampled from the Laplace approximation (LA). In doing so, we highlight two significant limitations of current IF approximations: the linearity of gradients and the singu- larity of Hessian. Accordingly, by improving each point, we introduce a new IF approximation method with the following features: the removal of linearization alleviate the bilinear constraint and ii) the utilization of Geometric Ensemble (GE) tailored for non-linear losses. Empirically, our approach outperforms existing approximations for downstream tasks with lighter computation. thereby providing new feasibility of low-complexity/ooniienn based IF design.
Introduction
In the last decade, neural networks (NNs) have made tremendous advances in various application areas [49, 24, 47]. To make reasonable predictions with NN-based systems, models must able to explain their predictions. For example, those who doubt the model's, prediction can gain insight and foresight by referencing the explanation of the model. Moreover, mission-critical areas like finance and medicine require a high degree of explainability to ensure that the predictions are not biased [30]. Understanding the mechanism predictions also allows researchers and engineers to improve prediction quality, ensuring that NNs are performing as intended [32].
To this end, Influence Function (IF) was proposed to explain predictions of pre-trained NNs through training data [25]. Intuitively. IF measures how the leave-one-out (LOO) retraining of training sample changes the loss of each sample. Therefore, the sign of influence determines whether the training sample is beneficial to others, and the scale of influence measures its impact. Specifically, self-influence, the increase loss when a sample is excluded, was used to measure how much the sample is memorized [48, 15]: When LOO training is performed on memorized training sample, its loss will increase substantially since matching its (corrupted) label will be difficult. Therefore, self-influence is used to detect mislabeled samples [48, 52] where memorization occurs. Furthermore,
37th Conference on Neural Information Processing Systems (NeurIPS 2023).
Correspondence to

---

recent works successfully applied IF to various downstream tasks, including dataset pruning [58] and data resampling [59, 63].
Despite its broad applicability, we found that IF and its approximations [25, 48, 52] suffer from oversimplified self-influence distributions due their bilinear form'. Although these approximations are introduced to avoid prohibitive retraining costs of IF, they impose structural constraint that self-influence becomes quadratic gradients of pre-trained NNs. Due to this constraint, self-influence follows an unimodal distribution, as gradients of pre-trained NNs typically follow a zero-centered Stable distribution [7, 56]. Unfortunately, unimodal distributions are too restrictive for representing self-influence in real-world datasets containing mislabeled samples. While self-infuuence distributions estimated by LOO retraining may become bimodal depending on the proportion of (high self- influential) mislabeled samples, unimodal distributions cannot handle this case.
To resolve this problem, we propose non-linear IF approximation via Geometric Ensemble (GE; [16]). Our method is motivated by a novel connection between IF approximation and linearized Laplace approximation (LA; [38]) that discovered: IF approximations can be translated to an averaged relationship between two linearized losses over parameters sampled from LA. As linearized losses in this connection cause bilinear forms of IF approximations, we consider an IF approximation without linearization. However, we then identify an additional issue of this approximation due to the singularity of Hessian and its solutions (e.g., damping and truncation). To mitigate this issue, we propose a novel approach using GE to manage the relationship of non-linear losses more effectively. As result, our approach. Geometric Ensemble for sample eXplanation (GEX), accurately represents the multimodal nature of LOO retraining, leading to improved performance in downstream tasks across various scenarios. Furthermore, Taxx is easy to estimate as it does not require Jacobian-vecto products (JVPs) for batch estimation or sub-curvature approximations like LA.
We summarize our contributions follows:
We identify a distributional bias in commonly used IF approximations. We demonstrate how this bias results oversimplified distributions for self-influences.
We provide a novel connection between IF approximations and LA. By identifying an inherent issue of LA, we provide a non-linear IF approximation via GE, named TaEx. Due to its non-linear nature, Taex can express various influence distributions depending on the characteristic of the datasets.
We verify that Teex outperforms standard IF approximations in downstream tasks, including noisy label detection, relabeling, dataset pruning, and data source separation. We also show that ToEx is competitive with well-known baselines of downstream tasks with lighter computation."
2 Background
Consider an independently and identically (i.i.d)) sampled training dataset S := {zn (In, Fn Bn)) J where In E R is an input vector of n-th sample and Un. R is its label. To model the relation between inputs and outputs of training samples, we consider a neural network (NN) f : RR x RR
RK which maps input v E R. and network parameter 0 R to a prediction ún = f(x,, mm 0) R Empirical risk minimization (ERM) solves the following optimization problem
0" = argmin ((S,0)
BER
where L(S,0) = O)/, for sample-wise loss f(=., 0) (e.g.. cross-entropy between and yn). In general, 0" trained using stochastic optimization algorithm (e.g., stochastic gradient descent (SGD) with momentum), For the reader's convenience, we provide the notation table in Appendix A for terms used in the paper.
The Leave-One-Our (LOO) retraining effect of E S on another instance z' E IR. is defined as the difference of sample-loss z' between the d" and the retrained point 8 without [9]:
I (2, 2') == ((2', (2) ((2/.0) 8*)
'eere, bilinearity refers to the and its approximations being bilinear with respect to sample-wisg wise gradients. Consequently, the self-influence hased on these bilinear metrics is quadratic for sample-wise gradients. "Code available https: //gi:t/ttt gigthu..... com/ wwwsssukiin////////ee ggx.

---

where 4- := argmingeR* L(S - ()N. Since retraining for every pair (2. is computa- tionally intractable where we have huge number of data points in practice, Koh and Liang [25] proposed an efficient approximation of Tooo named Influence Function (IF):
x(z,,') 9- 92
(2)
where 9s := Vol(z, 0*) E ER and H == ViL(S, 0*) E Px by assuming the strictly convexity of e (i.e., H is positive definite). Here, I can be understood as two-step approximation of Zzoo
12 = (=' , 07) - (1'
(z',0z) 00) = 00 0*)
(3)
= 9 H 9= I(z,z')
where (2, =
( 0r) and va E TR. is an arbitrary vector in the parameter space RRP. Here, we use the superscript lin to indicate linearization. Note that (3) applies linearization to the sample-loss z' and (4) approximates parameter difference a Newton ascent term (i.e.,
+ (== -==
8- ~ 0" H
While the computation of is cheaper than Iia, it is still intractable to modern NNs (e.g., ResNet [20] and Transformer [62]) because of the prohibitively large Hessian. To alleviate this problem, two additional approximations are commonly used: stochastic approximation methods such as Llsss [1]. and sub-curvature approximations such as LLast-Layer. which limits the Hessian computation only to the last-layer of NÑs [10]. However, both methods also have their own problems: ZliSsA takes high time complexity since the inverse Hessian- vectoor product (IHVP) for each training sample needs to be computed separately, as shown in Schioppa et al. [52]. On the other hand, Laast-Layer may cause inaccurate IF approximations, as shown in Feldman and Zhang [15].
As another alternative, Pruthi et al. [48] recently proposed to exploit intermediate checkpoints during pre-training, named Irractn:
1 ITracIa(2, 2') C 92 g
(5)
where == Vol(z, 08) for checkpoints 0f (c (c= C) sampled from the pre-training trajectory of 6" Here, it further simplifies the computation by assuming the expensive H in (2) is an identity matrix. Instead. the performance of Treacin is replenished by averaging over several intermediate checkpoints, which capture various local geometries of loss landscapes. In addition, Pruthi et al. [48] enhanced the efficiency of IrracIn using random projection, named TrracInBP.
C Σ gfd QRQ
(2,= := π
(6)
where QR E RPXR is random projection matrix whose components are i.idd sampled from (O 1/R) for R < P. Note that ITraCIuRP an unbiased estimator of TrracIn as R Ip
where Ip is the identity matrix of dimension / x P. However, IrracIn and TTraCIaPP cannot be applied checkpoints of the open-source community, such as TorchHub [45] and Huggingface models [65] since they only provide the final checkpoints without any intermediate results during pre-training.
On the other hand, Schioppa et al. [52] proposed to approximate IF in purely post-hoc manner as
Tarmolai (z, 2') = R.
where AR E IR nx is a diagonal matrix whose elements are top-R eigenvalues of H and the columns of UR E Px and UR. Contrary to TreaCInRP with the random projection, Tarnoddi projects Jes 92r to the top-R eigenspace of the Hessian. Due to this difference, Schioppa al. [52] argued that Iarnoldi perform comparably to TrracInRP with less R.
corresponding eigenvectors. They use Arnolii iteration [3] to estimate Ar
Finally, it is important to note that TrrecInpe and TArnolsi can perform batch computations using Jacobian- products (JVPs). To be more precise, computing I and Trracto for multiple samples requires sample-wise gradient computation for each 9z, gf which is difficult to parallelize because of heavy memory complexity. contrast, TTracInRP and Tarnolas can avoid this sample-wise computation by computing JVPs for batch at once (i.e., parallelize gf QR. 92 UR for multiple 2).
3

---

301
30-
37
6:000
(a) Random proj. of grads.
(b) TArnoldi
(c) IrreCToPP
(d) T
Figure I: Since pre-trained gradients follow Gaussian distributions (Fig, ((a),, quadratic self-influences follow unimodal distributions (See Proposition 3.1), even in noisy label settings (Figs. 1(b)-1(c)). This issue can be solved by removing lincarization in the IF approximation (Fig. 1(d))
3 Identifying distributional bias in bilinear influence approximations
Throughout the discussion above, IF approximations ((2), (5), (6), and (7)) are defined as bilinear forms of gradients. In this section, demonstrate a side effect of this form computing self- influence. Our key empirical observation is that gradients of pre-trained NNs follow Gaussian distributions centered at zero. To verify this, train VGGNet [55] MNIST [33] with 10% label corruption following Schioppa et al. [52]. Then, we project {9s hees onto each of 5 random vectors {d. ) (with d, E H²),, uniformly sampled on the unit sphere. If a pre-trained gradient Iz follows Gaussian distribution, its projected component g2 d: will also follow Gaussian distributions for all i= 1, 5. We visualize histograms of projected components 9._ de for each d, and the resulting p-values of the normality test [57] in Fig. ((a). In agreement with our hypothesis, the randomly projected components follow Gaussian distributions with significantly low p- p-values. Moreover, one can observe that Gaussian distributions are centered at zero. This is because gradients at 0 satisfy
Eg- 9
1
Σ ZES
g. d 0.
by the first-order optimality condition at 6" (i.e., (S 0*) = 0p) where Op is the zero vector of dimension P. Note that similar observation on the normality of gradient was reported in the context of differential privacy in Chen et al. [7].
Now let us write the eigendecomposition of Hessian as H = D Amnn where An.... Ap > 0 are eigenvalues of H in descending order and u1...... up E IR are corresponding eigenvectors by positive definite assumption of Koh and Liang [25]. We then arrange self-influence of I
Σ (02,)²
I(2,2) = =9 H-
(8)
X
where I2.i := -_ u, are i-th component of g= in the eigenspace of H. Following the above discussion, one can assume that Рz.: follows a Gaussian distribution. Consequently, I(=, follows (general- ized) x² -d-distritttion due to squared components in (8). The following proposition shows that this phenomenon can be generalized to any stable distribution [56] and positive definite matrix.
Proposition 3.1 (Distributional bias in bilinear self-influence). Let us assume 9N follows P- dimensional stable distribution (e.g., Gaussian, Cauchy, and Lévy distribution) and M E PRP is positive (semi-)definee matrix. Then, self-influence in the form of IIs(2, 2) 9 Mg follows unimodal distribution. Furthermore, if g2 follows a Gaussian distribution, then the self-influence follows generalized x² -isitribbtiio
We refer to Appendix B for the proof. Self-influence distributions approximated by Iarnolai (Fig. 1(b)) and IrraCIORP (Fig. I(c)) provide the empirical evidence of Proposition 3.1 in the noisy label setting in Fig. (a). In this setting, each mislabeled sample exhibits high self-influence values since predictions by incorrect labels are challenging to recover when removed and retrained. Therefore, mislabeled samples constitute distinct mode with greater self-influence than correctly labeled samples. Still, the distributional bias in Proposition 3.1 squeezes correct and mislabeled samples in a unimodal distribution. As a result, two types (clean and corrupted) of samples are indistinguishable in Tarnoldi and TrractaRP. Proposition 3.1 shows that this observation can be generalized to a more diverse setting (e.g., heavy-tailed distributions). In See. 5.1, we demonstrate that this bias occurs regardless of the dataset and the architectures of NN.

---

30
10-22
(a) Traininig dataset
(b) Iot
(c) I (a 100)
(d) TOEX
Figure 2: Fig. 2(a): The modified two-circle dataset in Sec. 4. Here, the typical samples are the two outer circle samples with relatively high density, and influential samples correspond to the inner circle, demonstrating relatively low density. The self-influence histogram estimated with Tzoo. I, and Taxx are provided in Fig. 2(b)- 2(d). Fig. 2(h): Tano properly separates the influential samples from the typical samples in the modified two-cirele dataset. Fig. 2(c): I mixes typical and influential samples due to the distributional bias Sec. 3. Fig. 2(d): Tox accurately represents the bimodal nature of Tum-
4 Geometric Ensemble for sample eXplanation
To mitigate the distributional bias in Sec. 3, we propose a flexible IF approximation method using Geometric Ensemble (GE; [16]), named Geometric Ensemble for sample eXplanataion (GEX). Here is a summary of how GEX is developed.
I Delinearization ILA
to IGEX
Section 4.1
Section 4.2
In Sec. 4.1, we ensure that the influence approximation is not a bilinear form for the gradient by replacing gradients in IF with sample-loss deviations. The theoretical foundation for this step is provided by our Theorem approximation (LA; [38]). Moving to Sec. 4.2, we modify the parameter distribution to compute the sample-loss deviation from LA to GE. This modification is necessary because GE based on the local geometry of the loss landscape around 0r, similar to LA, while avoiding overestimating loss deviations caused by the singularity of the Hessian.
below, which establishes relationship between the IF and the Laplace
4.1
GEX and its motivation
The proposed method, GEX, comprises three steps. The first step involves the collection of post-hoc checkpoints { through multiple SGD updates the training loss starting from 0", Then, the empirical distribution of Geometric Ensemble (GE) is computed as
PaR(w)
1 M
Σ
Sgims (1)).
where 6gcm)() (-) denotes the Dirac delta distribution at ((mm) In the final step, GEX is obtained as the expectation the product of sample-loss deviations from the pre-trained parameter as follows
ToEx (z, x²) = Espeper A (z, v) Ale- (2',))) +)]
(10)
where A (z, w/) = ((2, v) - ((2, 0*) means the sample-loss deviations from 0* We provide the pseudocode for computing ToEx in Appendix C.
The main motivation behind TÆzx in (10) is to establish new connection between I and LA. This connection demonstrated in Theorem 4.1, which shows that I is an expectation of the product of linearized sample-loss deviations given that parameters are sampled from LA.
Theorem 4.1 (Connection between IF and LA). I in Koh and Liang [25] can be expressed as
I(z, z') = Engropp [A (2, w) A Alin (z', +)]
(11)
where Adhi (z, vb) = Aiu (z, 1b finl 0*) 3_ (1b 0*) and PLa is the Laplace approximated
posterior
pb)(1) = N (1/10, .H 1)
5

---

3x37
2x
LoGo LO55 let.
1d1t
10-4
(a) TIA (a- = 0.01)
(b) ILA (a = 100)
(c) ILA (R = 50)
(d) I(R 50)
Figure 3: Damping trick for singular Hessian causes severe overestimation of self-influence (Fig. 3(a). This issue cannot be addressed with a large damping coefficient (Fig. 3(b)). Although truncating small cigenvalues reduce the overestimation of self-influence (Fig. 3(c)), it introduces another error that even occurs in I (Fig. 3(d)).
The LA was proposed to approximate the posterior distribution with a Gaussian distribution. Recently, it has gained significant attention due to its simplicity and reliable calibration performance [50, 11]. Intuitively, LA is equivalent to the second-order Taylor approximation of log-posterior at 8* with Gaussian prior defined as p(()) == (
log P(OS)) = p(S + log - log Z
-L(S, 0) + log log Z
-( (0 0¹) (H + (1 8²2 - log Z
x -0 11)
Here, the training loss represents the negative log-likelihood L(S, 0) = log p( (S10), and 2 == p(0)p(S))))d represents the evidence in Bayesian inference [5]. Similar to the IF, LA becomes computationally intractable when dealing with modern architectures due to the complexity of the Hessian matrix. To address this computational challenge, recent works have proposed various sub- curvature approximations, such as KFAC [50] and sub-network [11], which provide computationally efficient alternatives for working with LA.
According (1)), samples with a high degree of self-influence experience significant (linearized) loss changes for the parameters sampled from LA. Furthermore, Theorem 4.1 reveals that the gradients, the origin of distributional bias, arise from the linearizations in (11). Hence, address the distributional bias of the bilinear IF approximations in Proposition 3.1, we remove the lincarizations in (1 This leads us to consider modified version of I. named IZA= == Eurep [ (/) A (2', v)]]
(12)
The pseudocode for computing Ira using Kronecker-Factored Approximate Curvature (KFAC; [40]) is available in Appendix C.
While ILA no longer thcoretically produces unimodal self-influence. it turns out that it still mixes correct and mislabeled samples, even in toy datasets. To illustrate this problem, we train a fully- connected NN on the two-circle dataset [29] with a modification as shown in Fig. 2(a): We add ten influential training samples the center of the two-circle dataset containing 30 train samples per class (cirele). These influential samples are highly susceptible (i.e., hard to recover) to leave-one- out retraining samples of the opposite class are densely located around them. We provide other experimental details in Appendix E.
As discussed in Sec. 3, highly influential samples form a separate mode of high self-influence in the histogram of Too (Fig. 2(b)) and I mixes typical and influential samples (Fig. 2(c)) due to the distributional bias of bilinear form. While Proposition 3.1 does not apply to Iza- Fig. 3 shows that Iy still fails to distinguish between correct and mislabeled samples by severely overestimating the self-influence of typical samples (Fig, 3(a)-3(b)) squeeze them into unimodal distribution (Fig. 3(c)), similar to (Fig. 3(d))
4.2 Pitfalls of inverse Hessian in non-linear IF approximation
To analyze the limitation of IZa, we reparameterize the sampled parameter from LA as follows
e = + 1 = 0* +
U:
U4
(13)

---

From this reparameterization, one can see that for (13) to be valid, all eigenvalues of H must be positive definite (i.e., all eigenvalues are positive), Koh and Liang [25] assumed. However, werrpparameterized NNs in practice can contain many zero eigenvalues in their Hessian.
Proposition 4.2 (Hessian singularity for over-parane par--ataaattezed NNs). Let us assume a pre-trained parumeter 0 R achieves zero training loss L(S, 0*) for squared error. Then, H has least P- -NK zero-eigenvalues for NNs such that NK < P. Furthermore, if x is an input of training sample 2 E S, then the following holds for the eigenvectors {ui)-NN++
4 uu==Vo - V.J [22, 0))
0 f(2,0') =0
(14)
OK
We refer to Appendix B for the cross-entropy version of Proposition 4.2 with empirical Fisher (EF) matrix, a well-known approximation of the Hessian [31, 22], defined as F := N =x==1-e 9=9. Note that the over parametteeernnnno assumption (NK < P) in Proposition 4.2 is prevalent in real-world situations, including the settings of Fig. 1- 3. Also, the zero training loss assumption can be satisfied with sufficient over-parameterization [14, 2]. Accordingly, empirical evidences of Proposition 4.2
have been reported in different scenarios [51, 18].
simple solution to mitigate this singularity is adding an isotropic matrix to H, known as the damping technique: Hl sJ (aa) == H + alp for a > 0. Then, the modified LA sample is
Vu = 0" (H(a)) 1/2 = 0" 0
(15)
Although the damping trick can make all eigenvalues positive in principle, the order of the eigenvalues remains unchanged. Therefore, the null space components (ge.i for i NN K ,,..., P) in Proposi- tion 4.2 are the most heavily weighted by Va. These heavily weighted null space components do not affect the linearized sample-loss deviations in (11) as follows
NK
Achi (2, v.) 9- (vaa --)=)
Σ
U2
A + 92
U.
+ 9=
by Proposition 4.2. However, this is not applicable to the sample-loss deviations in (12), since the null space components cause Agg. (z, th) to change rapidly (i.e., overestimating the influence of samples). This be confirmed by observing that setting overestimating self-influences. To prevent this issue, one can enlarge a (i.e., decrease 1 l/a). However, since the scale of a does not change the order of eigenvalues, the null space components still receive a higher weight than the others. Consequently, Iea with a = 100 (Fig. 3(b) does not correctly represent the multi-modality of self-influence distribution.
0.01 in ILa (Fig. 3(a)) leads to significantly
Another way to handle the Hessian singularity is to limit (13) to only the top-R eigenvalues of Hessian, similar to Iarmoldi- However, this approximation method may result in significant errors due to using only the smallest eigenvalues of the inverse Hcssian (i.e., 1/vAx). Consequently, even linearized sample-loss deviations (i.e., Z) with R 50 (Fig. 3(d)) suffer from severe performance degradation, compared to full Hessian with damping (Fig. 2(c)).
Compared to damping and truncation, ToEX (Fig. 2(d)) accurately captures the bimodal self-influence distribution. This effectiveness stems from the differential impact of SGD steps on typical and influential samples [61]: :: Since typical samples are robust to SGD steps [35], loss deviation of these samples are small in T In contrast, influential samples experience significant loss deviations as they sensitive to SGD steps. As GE makes diverse predictions [16]. the members of GE introduce varying levels of loss deviation for each influential sample. An ablation study exploring the impact of ensemble size is provided in Appendix F.
4.3 Practical advantages of GEX
In addition to the above benefits, TaEx offers several implementation advantages. First, it can be obtained using only open-source final checkpoints, unlike Trracta and TrractaPP. This advantage broadens the range of applicable models. Second, batch estimation easy to implement in T Projection- based methods like TrecI and TArnolai require JVP computation, which is only efficient
7

---

Table I: Area Under Curve (AUC) and Average Precision (AP) for noisy label detection tasks four datasets. Due the high time complexity associated with sample-wise gradients, we do not repeatedly measure the self self-inftuence of Treactn-
Synthetic label noise
Real world label moise
CIFAR-10
CIFAR-100
CTFAR-IO-N
CIFAR- CIFAR-I00-N
Dotection method
AUC
AP
AUC
AP
AUC
AP
AUC
AP
Deep-Kiil
92.51 + 0.19
69.93 0.71
84,00 0.14
40.17 0.22
78.32 0.19
72.60 0.33
71.59 + 0.21
59.76 = 0.25
CL
57.60 0.30
16.27 40.20
84.16 a 0.10
35.76
75.94 0.02
66.50 0.09
69.49 a 0.15
58.69 0.23
F-score
73.34
0.009
59.18 0.21
11.04
69.39 0.06
52.89
68.95 0.11
$2.29
E12N
98.29 + 0.03
95.82
96.42 + 0.05
73.82
93.57 0.17
0.113
84.65 + 0.08
77.26 0.06
LandPres
6
17,90 0.17
79.96 a 0.32
26.25 2
56.75 a 0.38
45.61 0.338
67.25 0.09
54.14 0.09
Ttracts
89.89
43.21
75.53
22.25
76,48
64.69
68.91
55.86
7 Traciar
89.56 0.14
44.26 + 0.37
74.99 + 0.25
21.62 0.26
66.67 0.45
69.04 + 0.28
56.41
Tamoia
61.64 0.13
77.20 0.35
22.61 0.42
0.40
45.63 0.40
66.57 0.12
53.26
Tars-tt
64.11 0.34
18.34 + 0.36
76.06 = 0.36
22.26 = 0,47
56.88 + 0.29
45.67 0.33
66, = 0.15
0,13
Tams
99.74 0.02
98.31 + 0.06
+ 0.03
96.08 0.12
96.20 0.03
94.89 + 0.04
89.76 0.01
86.30 0.01
for packages that provide forward-mode auto-differenniation, such as JAX [6]. In contrast, batch computation in TGEX necessitates only forward computations, which are efficient in almost all auto-differentiation packages, Since IF is computed for each training sample in most downstream tasks [25, 48, 52], efficient batching critical for practical applications. As a result, we believe that this distinction will be vital for researchers and practitioners in their work. We provide the complexity approximations Appendix D and discuss the limitations of our method and broader impacts in Appendix G.
analysis of TaEx and other IF
5 Experiments
Here we describe experiments demonstrating the usefulness of GEX in downstream tasks. We conducted two experiments for each noisy and clean label setting: Detection (Sec. 5.1) and relabeling (Sec. 5.2) of mislabeled examples for noisy label setting and dataset pruning (Sec. 5.3) and separating data sources (Sec. 5.4) for clean label setting. We refer to Appendix E for experimental details.
5.1 Noisy label detection
In this section, we evaluate the performance of IF approximation methods for detecting noisy labels. We use self-influence an index for the noisy label of IF approximation methods following Koh and Liang [25] and Pruthi et al. [48]. A high degree of self-influence indicates mislabeled examples since the removal of mislabeled examples will significantly change prediction or loss.
We train ResNet- 18 [20] on DIFAR-IO/100 [27] with 10% random label corruption for synthetic noise and CIFAR-N [64] for real-world noise. We use the "worse label" version of CIFAR-1O-N since it corresponds to the highest noise level. We compare TGEx to the following baselines: TrraCIaRP with 5 checkpoints and 20 random projections, I with 20 random projections only for the final checkpoint, Tarnoldi with 100 iterations and 20 projections. We assess F-score [61], and EL2N [46] as they offer alternative approaches identifying influential samples. We also evaluate an ablative version of TZEx: Toex-lin. which replaces LA with GE for (11) (i.e., TeEx with linear sample-loss deviation). Finally, we report the performance of well-known baselines, Deep-KNN [4] and CL [43], for comparison. We provide results for cross-influence I(z, =') in case of = o z' in Appendix F.
Table 1 shows that TaEx distinguishes mislabeled samples better than other methods. Furthermore, we find that ZaE is more effective than CL, a ofate-of-the-art noisy label detection technique. Since CL requires additional K-fold cross-validation for sample scoring (K = 2 used in our experiments), IoEx will be an attractive alternative in terms of both computational complexity and detection performance. Notably, results of Taxx-lia demonstrate that removing linearization is essential for performance improvement of TEE
One interesting observation in Table is that Tarmolai did not show improvement compared to simple IRandProg- Indeed, a similar observation was reported Table 1 in Schioppa et al. [52]. In contrast, TTractnRP showed improvements in CIFAR-10 10 and SVHN compared to TaandProj- IrracInRP computationally expensive since it requires JVP computations for multiple checkpoints. On the other hand, IoEx can be applied in pure post-hoc style and does not require (framework-dependeen
8

---

Table 3: Relaheled test accuracy for mislabeled samples
Table 2: Noisy label detection performance for
Syatetic label noise CIFAR-10
Real-workc label noise
ImageNet [12]
CIFAR-100
CIFAR-IO-N
CIFAR-100-N
VIT-S-32
MLP-Mixer-S-32
Noisy lahel icc.
Clean label acc.
95.75 a 0.06 90.94
0.15
7908 a 2005 72.35
+0.17
95.75 0.05
68.63 0.33
79.08 0.05
$5.50 0.09
Detection method
AUC
AP
AUC
AP
Detection method
Relabeled
F-score EL2N
1.56
9.44
1.07
9.21
Deep-RVu
91.58
12
0.25
50.03
87.28
38.37
88,47
41.63
F-scorw
50 0.28
80.28
80:40 0.10
61.72
0.18
72:01 0.51
47.58
Traacton
IandPraj
72.22
76.09
15:09
12.08
82.36
75.01
21.86
16.62
Stwets
90.94 a 0.09
91.24
72,42 a
72.07
68. 0.117
08.36
55.47 a 0.08
54,87
Iaroolas
73.95
16.09
82,16
21.83
90.22 a 0.06
71.70 0.155
68.12 0:223
3 0.06
01.10
72.50 = 0.08
68.67 0.02
0.13
Taza
99.39
95.22
98.73
90.65
91.04 1
70.08 + 0.12
68 0.08
02.51
93.54 à 0.05
2.10
73.94
$7,13 0.10
JVP computation. Motivated by ToEx. one can propose a purely post-hoc IrraIIaRP using checkpoints generated by GE. We provide an ablation study for this setting in Appendix F.
To verify the scalability of results, we train Vision Transformer (VIT; [13]) and MLP-Mixer [60] on ImageNet [12] with 10% label corruption and evaluate the performance of IF approximation methods. Table 2 shows that the performance gap between IGEx and other baselines is still large. Specifically, in this scenario, F-score fails since some samples have never been correctly predicted during pre-training (i.c., no forgetting events for such samples). We provide additional results for other vision datasets (MNIST [33] and SVHN [42]) and text classification settings in Appendix F.
5.2 Relabeling mislabeled samples
Following up on the detection task in Sec. 5.1, we improve classification performance by relabeling mislabeled samples following Kong al. [26]. To this end, Otsu algorithm [44] was used to find a threshold that distinguishes between noisy and clean labels, given the self-influence of approximation methods. Since the Otsu method has no inputs other than (influence) distribution, practitioners can apply it for noisy label settings without onerous hyperparameter optimization. Following Kong et al. [26]. we relabel training samples as follows:
O, log
k = m, V 1m otherwise
Ok -
(16)
where m is the training sample's original (corrupted) label and yp; is the predicted probability for i-th class of the training sample. Therefore, the relabel function in (16) masks the original (noisy) label and re- re-distributes the remaining probabilities. We provide additional results for MNIST and SVHN in Appendix
Table shows the relabeled test accuracy with the other settings for comparison. critical observation in Table 3 is that not all methods achieve performance improvements with relabeling. Otsu algorithm did not find an appropriate threshold for mislabeled examples for these methods. In contrast, since TαEX can separate mislabeled samples from the self-influenc, distribution, performance improvements were obtained through relabeling. We provide additional results for ImageNet in Appendix F.
5.3 Dataset pruning
We evaluate methods in the previous section data pruning task [58] to validate the efficacy of TeEx in clean label settings. We quantify the importance of training samples based on self-influence following Feldman and Zhang [15]: We prune low self-influence samples as they are relatively easy samples that can be generalized by learning other training samples. We use networks and datasets in Sec. 5.1 without label noise. We provide additional results for MNIST and SVHN in Appendix F.
As shown Fig. 4, TOEX consistently detects samples that can be pruned. It is worth noting that among the IF approximation methods considered, only TaEx is comparable to the well-known state-of-the-art methods, F-score and EL2N. This suggests that existing IF approximation methods may experience performance decrease in downstream tasks because of the errors caused by distributional bias.

---

Fiscere
Table 4: Detection metrics for scparating MNIST and SVHN
Vacaep
AUC
AP
Facrre amo D12h
Deep-Rt8
44.58
(andies)
CL
49.88 0.15
89.1
2.111
P-acore
67.39
65.37 0
EL.8
68.36
72.20
Teattrod
4.28
56.53
1.8
61.33
1.65
(a) CIFAR-10
(b) CIFAR-100
0..33
50.09
Tas-ii
5.56
Figure 4: Data pruning results using various scoring methods. We refer
Ago
73.11
to Sec. 5.3 for the details of scoring methods.
5.4 Separation of data sources
We also evaluate IF approximations separating heterogeneous data sources following Harutyunyan et al. [19]. One often combines multiple datasets to improve generalization. In general, these datasets differ in their informativeness. Therefore, IF can be used determine which dataset is the most essential based on the informativeness of each dataset. In this experiment, we train ResNet-18 8 on mixed dataset of MNIST and SVHN, with 25K random subsamples for each training dataset. Then, we use self-influence as an index for the informativeness following Harutyunyan et al. [19].
Table 4 shows detection metries for MNIST and SVHN separation using various IF approximations (and other baselines in previous sections). In contrast to the noisy label detection experiment in Sec. 5.1, many IF approximations in this experiment fail to distinguish between data sources: MNIST and SVHN can only be significantly separated by Toex, TrracInR,, and F-score. Assuming only the final checkpoint available, only TeEx be applied among them.
6 Conclusion
In this work, we studied the oversimplification of influence distributions due to their bilinear ap- proximations. To mitigate this bias, we developed non-linear IF approximation, GEX, with GE. Empirically, GEX consistently outperforms the standard IF approximations in various downstream tasks in practice. Also, GEX is user-friendly excludes JVP computation, often constrained by frameworks, for efficient batch estimation. With these advantages, GEX can be used as a practical tool for researchers and practitioners.
only requires the final checkpoint of pretraining and
Acknowledgements
This work was supported by the Institute of Information & Communications Technology Planning Evaluation (ITP) grant funded by the Korea government (MSIT) 0-00984) and the National Research Foundation of Korea (NRF) grants (No.2018P) 1A5A 1059921 (RS-2023-0200066) funded by the Korea government (MSIT). This work was also supported by Samsung Electronics Co., Ltd 2No.10201214-08133.2
No. 2022-
References
[1] Naman Agarwal, Brian Bullins, and Elad Hazan. Second-orde stochastic optimization in linear time. stat, 1050:15, 2016. 3
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over-parameterizzaion.. In International Conference on Machine Learning, pages 242-252.
PMLR, 2019.
[3] Walter Edwin Amoldi. The principle of minimized iterations in the solution of the matrix cigenvalue problem. Quarterly of applied mathematics, 9()::17-29, 1951. 3
[4] Dara Bahri, Heinrich Jiang, and Maya Gupta. Deep k-nn for noisy labels. In International Conference Machine Learning, pages 540-550, PMLR, 2020. 8
10

---

[5] Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. 6, 16
[6] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-M Milne,, and Qiao Zhang. JAX: composable transformations of Python+NumPyy programs. github, 2018. 8, 19
[7] Xiangyi Chen, Steven Z. Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: geometric perspective. Advances Neural Information Processing Systems, 33:13773-13782,
2020. 2, 4
[8] William G Cochran. The distribution of quadratic forms in normal system, with applications to the analysis of covariance. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 30, pages 178-191. Cambridge University Press, 1934. 16
[9] R Dennis Cook. Detection of influential observation in linear regression. Technometries, 19(1):
15-18, 1977. 2
[10] Erik Daxberger, Agustinus Kristiadi, Alexander Immer, Runa Eschenhagen, Matthias Bauer, and Philipp Hennig. Laplace redux effortless bayesian deep learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. 3
[11] Erik Daxberger, Eric Nalisnick, James U Allingham, Javier Antoran, and Jose Miguel Hernandez- Lobato. Bayesian deep learning via subnetwork inference. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 151102552.. PMLR, 18-24 Jul 2021. 6
[12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE conference on computer vision and pattern recognition, pages
leee, 2009. 9, 19, 20, 21, 23
[13] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint
arXiv:2010.11922 2020. 9,20
[14] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International conference on machine learning, pages 1675-1685. PMLR, 2019. 7
[15] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. Advances in Neural Information Processing Systems, 33: 2881-2891, 2020. 3.9
[16] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P Vetrov, and Andrew G Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Biance and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. 2, 5, 7, 18, 19
[17] Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast approximate natural gradient descent in kronecker factored eigenbasis. Advances in Neural Information Processing Systems, 31, 2018. 18
[18] Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural net opti- mization via hessian eigenvalue density. In International Conference on Machine Learning. pages 2332-2241. PMLR, 2019. 7
[19] Hrayr Harutyunyan, Alessandro Achille, Giovanni Paolini, Orchid Majumder, Avinash Ravichan- dran, Rahul Bhotika, and Stefano Soatto. Estimating informativeness of samples with smooth unique information. arXiv preprint 1.X.i:211100664: 2021. 10, 20, 24
[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016. 3, 8, 20
11

---

[21] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in a neural network. arXiv preprint St03:::50000233333 2015. 23
[22] Alexander Immer, Matthias Bauer, Vincent Fortuin, Gunnar Rätsch, and Khan Mohammad Emtiyaz. Scalable marginal likelihood estimation for model selection in deep learning. In International Conference on Machine Learning, pages 3563-4573, PMLR, 2021. 7
[23] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 Proceedings of Machine Learning Research, pages 448 446,55,,1 Lille, France, 07-09 Jul 2015. PMLR. 20
[24] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583 589, 2021.
[25] Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885-1894. PMLR, 2017. 1, 2, 3, 4, 5,
7, 8, 16
[26] Shuming Kong. Yanyan Shen, and Linpeng Huang. Resolving training biases via influence-based data relabeling. In International Conference on Learning Representations, 2021. 9
[27] Krizhevsky. Learning multiple layers of features from tiny images. Master's 's thesis, University
of Toronto, 2009. 8, 20
[28] Taku Kudo and John Richardson. Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing, arXiv preprint arXiv: 1808.060,. 2018. 20
[29] Brian Kulis, Sugato Basu, Inderjit Dhillon, and Raymond Mooney. Semi sumi-supe graph clustering: kernel approach. In Proceedings of the 22nd international conference on machine learning, pages 457-464, 2005. 6
[30] Shinjini Kundu. Ai in medicine must be explainable. Nature medicine, 27(8):1328 1328, 2021.
[31] Frederik Kunstner, Philipp Hennig, and Lukas Balles. Limitations of the empirical fisher approximation for natural gradient descent. Advances in neurul information processing systems, 32, 2019.
[32] Valliappa Lakshmanan, Sara Robinson, and Michael Munn. Machine learning design palterns. O'Reilly Media, 2020.
[33] Y LeCun, C Cortes, and C Burges. The mnist dataset of handwritten digits (images). NYU: New York, NY, USA, 1999. 4, 9, 20, 21
[34] Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick Van Kleef, Sören Auer, et al. Dbpedia-a large- scale, multilingual knowledge base extracted from wikipedia. Semantic web, 6(2):167-195, 2015. 20, 22
[35] Sheng Liu, Jonathan Weed, Narges Razavian, and Carlos Fermandez-Granda Early- learning regularization prevents memorization of noisy labels. Advances in neural information processing systems, 33:2033 1-2332,, 2020. 7
[36] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint 16Xiv: 03983, 2016. 20
[37] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference Learning Representations, 2019. 20
12

---

[38] David J. C. MacKay. A practical bayesian framework for backpropagation networks. Neural Comput., 4(3):448 472. may 1992. ISSN 0899-7667. doi: 10.1162/neco..1992....44
[39] James Martens. New insights and perspectives on the natural gradient method. arXiv preprint arXiv:1412.1193, 2014. 18
[40] James Martens and Roger Grosse. Optimizing neural networks with frattreer-factored approx- imate curvature. In International conference on machine learning, pages 2408-2417 PMLR. 2015. 6
[41] Stefan Mittmik, Svetlozar T Rachev, and Jeong-Ryeod Kim. Chi-square-tyee distributions for heavy-tailed variates. Econometric Theory, 14(3):339 1998. 16
[42] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning, In NIPS Workshop on Deep Learning and Unsupervised Feature Learning 2011, 2011. 20, 21
[43] Curtis Northcutt, Lu Jiang, and Isaac Chuang. Confident learning: Estimating uncertainty in dataset labels. Journal of Artificial Intelligence Research, 70:1373-1411 2021.
[44] Nobuyuki Otsu. A threshold selection method from gray-level histograms. IEEE transactions on systems, man, and cybernetics, 9(1):62-66, 1979. 9
[45] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary VeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pages 6024-8035. Curran Associates, Inc., 2019. URL htL:ttt:://pape http://pppprrre..eispsppp newrips cc/paper/ 9015-pytorch. an- tn--inperative-sttee htg.gpppeffrrann---------eee-eee 1araap---eeamnn---bbbarr library. pdf. 3
[46] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on data diet: Finding important examples early training. Advances in Neural Information Processing Systems, 34:20596-20600) 2021. 8, 20
[47] David Pfau, James Spencer, Alexander GDG Matthews, and W Matthew Foulkes. Ab initio solution of the many-electron schrödinger equation with deep neural networks. Physical Review Research, 2(3):033429, 2020.
[48] Garima Pruthi, Frederick Liu, Satyen Kale, and Mukund Sundararajan. Estimating training data influence by tracing gradient descent. Advances Neural Information Processing Systems, 33: 19920-19930, 2020. 1, 2, 3, 8, 20
[49] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. arXiv preprint arXiv:2103.00000, 2021. 1
[50] Hippolyt Ritter, Aleksandar Botev, and David Barber. A scalable laplace approximation for neural networks. International Conference on Learning Representations, 2018. 6
[51] Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv: 1611107776 2016. 7, 17
[52] Andrea Schioppa, Polina Zablotskaia, David Vilar, and Artem Sokolov. Scaling up influence functions. Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 8179-8186 866 2022. 1, 2, 3, 4, 8, 19
[53] Dinghan Shen, Guoyin Wang, Wenlin Wang, Martin Renqiang Min, Qinliang Su, Yizhe Zhang, Chunyuan Li, Ricardo Henao, and Lawrence Carin. Baseline needs more love: On simple word- embedding- based models and associated pooling mechanisms, arXiv preprint arXiv: 1805 098449 2018. 20, 22
13

---

[54] Thomas Simon. A multiplicative short proof for the unimodality of stable densities. Electronic Communications in Probability, 16:623- 629, 2011. 16
[55] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015. 4, 20
[56] Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis of stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pages 5827-5837. PMLR, 2019. 2,4, 16
[57] Nickolay Smirnov. Table for estimating the goodness of fit of empirical distributions. The annals of mathematical statistics, 19(2)277-281, 1948. 4
[58] Ben Sorscher, Robert Geirhos, Shashank Shekhar, Surya Ganguli, and Ari S Morcos. Be- yond neural scaling laws: beating power law scaling via data pruning. arXiv preprint arXiv:2206. /4486, 2022. 2, 23
[59] Daniel Ting and Eric Brochu. Optimal subsampling with influence functions. Advances in neural information processing systems, 31, 2018. 2
[60] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, et al. Mlp-mixer: An all-mlp architecture for vision. Advances in neural information processing systems, 34:
24261-24272, 2021. 9, 20
[61] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint 1812.v:882..5/1111 2018. 7,8
[62] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008, 2017. 3
[63] Zifeng Wang, Hong Zhu, Zhenhua Dong, Xiuqiang He, and Shao-Lun Huang. Less is better: Unweighted data subsampling via influence function. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6340-6347, 2020. 2
[64] Jiaheng Wei, Zhaowei Zhu, Hao Cheng, Tongliang Liu, Gang Niu, and Yang Liu. Learning with noisy labels revisited: study using real-world human annotations. arXiv preprint arXiv:2110. 12088, 2021. 8, 20, 21
[65] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, et al. Huggingface's trans- formers: State-of-the-art natural language processing. arXiv preprint arXiv: 190.::1910..3371,,,000 2019. 3
[66] Makoto Yamazato. On strongly unimodal infinitely divisible distributions of class eme. Theory of Probability & Its Applications, 40(3):518-523 1996. 16
[67] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization, 2017. 20
[68] Juntang Zhuang, Boqing Gong, Liangzhe Yuan, Yin Cui, Hartwig Adam, Nicha Dvornek, Sekhar Tatikonda, James Dunean, and Ting Liu. Surrogate gap minimization improves sharpness-awarc training. arXiv preprint arXiv:2203.0m 08065, 2022. 20
14

---

A
Notations
Table 5: Notations used in the main paper
(true) distribution
S (2n (In, M/ )n))
i..dd sampled training dataset from D a training instance (or sample)
In == (In Mu
Zu RDD Vu 12
training inputs/outputs parameter of NNs output of NN given x, 0
8, v0 RR
9n
[In 0)
0)
instance-wise loss given sample z,
L(S,0)
# >Σ +E ((,,,))
0* 6 CRP
pre-trained parameter of NN
0g ERP
argming L(S,0) - 8(2, 0)/N (leave-one-out retrained parameter)
0: RR
Vol(2, (*) (gradient of instance-loss w.r.t. parameter given 2, (**)
H NER RPXP
V)L(S, 8*) (Hessian of training loss w.r.t parameter given 0*)
q ()
[(2, (0)) + 92 (v 0*) (linearization of instance-loss w.r.t parameter)
(2,
(z) v)) - {(2,0")
(2.42
Eg- (z, v) ((200)
R Tp IPEPPXP
the P-dimensional zero vector the P-dimensional identity matrix
9 ERP
Vol(z, 0*) (gradient of instance- w.r.t parameter for a checkpoint c)
QR RRR
4
Random matrix sampled from N 1/R) component-wisely
H = H(a)
Bigendecomposition of Hessian
A
Damped Hessian matrix H + aIp
AR E RRRR UR RRR
Submatrices of the top-D eigenvalnes/eigenveetrss the i-th largest eigenvalue of H/ and its eigenvector i-th component of gs in the eigenspace of
E u: E R
I3.1 -=.1 9. U, E
PLa (V)
N( H (the Laplace approximated posterior)
Poe (1b)
1. -M 6gtms (1²) (the Geometric Ensemble distribution)
{((m) ) M
checkpoints of Geometric Ensemble (GE)
m=1
15

---

B Proofs
B.1 Proof of Proposition 3.1
Proposition B.1 (Distributional bias in bilinear self-inftuence). Let us assume 9= follows a P- dimensional stable distribution (e.g., Gaussian, Cauchy, and Lévy distribution) and M E PxP is a positive
matrix. Then, self-infueene in the form of I2(2222) = 92 Mg, follows a unimodal distribution. Furthermore, 9a follows a Gaussian distribution, then the self-influence follows a generalized x² -dittribbution
Proof. We first consider the of gradients with stable distributions [56]. According Corollary 1 in Mittnik et al. [41], the sum of squares of stable random variables is stable distribution with the stability of a/2. Since stable distributions are unimodal [66, 54], the resulting self-influence is also unimodal.
Now proof the of the Gaussian gradient. By positive semi-definite assumption, let write the cigendecomposition of M as M ΣL= Aun where eigenvalues are sorted in descending order. Specifically, one can compress this summation for the strictly positive cigenvalues: M = Zi=1 \un.u, where 7' is the cardinality of strictly positive eigenvalues. Then the self-influence IM can be expressed as follows:
=5 Mg; Mg
where 92.1 = 9. u; is the i-th component of g= in the eigenspace M. As a linearly transformed Gaussian random variable follows Gaussian distribution [5], one write Is,k follows
9z.i N(r..i o2)
Therefore, Is.; follows following generalized x2 -dditrribution [8]
g 2 o, 1,))
where uē is the non-centrality parameter and of is the weight of non-central x². As a result, IM follows following generalized x² -diittiibtiion
(2, (²(IM(z, 02, 1r,1)))))
where 22² (Mi....,, . ) RT. 0² (of....,of)) e R". and 1r (I. RT.
B.2
Proof of Theorem 4.1
Theorem B.2 (Connection between IF and LA), I in Koh and Liang [25] can be expressed as
I(z, x') = Eginn [A A (z, w) Aege (z', [}]] where Adli (z, vb) = (2, 1/ - (2, 8r) = g_ (wb 8r) and PLa is the Laplace approximated posterior
(17)
((a(b)= == N (1510,,11 ,H-1).
Proof. One express A (2, 16) as follows
A lin (z, v Alim (2, Φb) pliny (2, 8*) 9_ (x 8*)
Therefore,
E pir-a
Aeliin ge (z, +b)
A plin (2', }) can be arranged as follows
E PPPP
Aelii lin (z, w) Aelio (z', w)]
IE virpa
9. (sb 8*) (16 -0)) go'
[N 0*) (vp - - Der
= 9__ E
= H- 92' I(2,2
16

---

B.3 Proof of Proposition 4.2
Proposition B.3 (Singular Hessian for over- wer-paameterizzed NNs). Let us assume pre-trained parameter 0 E RR achieves zero training loss L(S, 8*) for squared error. Then, H has at least P-NE NK zero-eigenvalues for NNs such that NK < P. Furthermore, if x an input of training sample E S, then the following holds for the eigenvectors (u=)
9s u = V.J E22 0*) 0 f(, 0 =0
(18)
Ok
Proof. The Hessian matrix training loss w.r.t. parameters can be expressed as follows [51]
N
H
(xn (=) ((zn, 0³) 0') [(an, 0-) + Vg. l(zz, V' (xnn 0*)
N
(o 0" 1' f(zn, 0 V f 0*)
N
n=1
(I,( V') frn, 0*)
where the first equality holds due to the zero training loss assumption
Vgn [(n, 0*) = (f 0*) yn) = Og
Vn = 1, N
and the second equality holds due to the squared error assumption
V Un (zn. 0*) I Vn 1,
Therefore, H is sum of NK rank-one products. As result, H has most NK non-zero eigenvalues and at least P - NK zero-eigenvalues for over-parameterized NNs such that NK < P. As training Jacobians V fxx 0*) for n I,..., N contained in the linear span of {u; f=) which is
orthogonal to {u, N the following holds for any training input æ
V (xx = 0x: Vuu E (u:)
B.4 Cross-entropy version of Proposition 4.2 and its proof
Proposition B.4 (Cross-entropy version of Proposition 4.2). Let us assume pre-trained parameter O TR. for cross-entropy loss. Then, the empirical Fisher (EF) matrix F = Ezes 9=9- has at least P N zero-eigenvalues for NNs such that N < P. Furthermore, the following holds for the last N eigenvectors {ui)==N4 and any training sample S
9. 0
(19)
Proof. As F is sum of rank-one products. As a result, F has at most non-zero eigenvalues and at least P N zero-eigenvalues for over- over-vvrane parameterized NNs such that N < P. As gradients V [(z,, 0*) for n 1,..., N are contained in the linear span of {ux) which is orthogonal to {u:) the following holds for any training input
Vu, (us)
9
17

---

C Implementations
C.1 Pseudocode of LA for IF approximation
Algorithm ILA with KFAC [39, 17] sub-curvature approximation
1: Input: training data pre-trained parameter 0", number of LA samples M, data samples z
3: # Estimation of KFAC sub-curvature
4: Initialize activation statistics A' and gradient statistics G' for each layer / = ,,
5: for 1. N (This computation can be conducted batch-wisely do
6: for - 1,... T. do Accumulate activation statistics A and gradient statistics G'
8: end for (Fn(End accumulation for layers)
9:
end for [End accumulation for training samples)
10: Compute eigendecompositton of activattin//raadint statisties:
A' U UALA G¹ Ues
11:
12: # Sample Laplace approximated posteriors
13:
for m 1.... M do
14:
Sample P-dimensional standard Gaussian random variable 2m No 0r, Ir)
15:
for =0 1,.1,,...
16:
Use reparameterization trick for each layer:
V (0*)² 20')'+ UG! (1/n @ (diagg(Agi )diag
U
where diag(A) is the diagonal components of matrix A, @ denotes Hadamard product of two matrices, and the square root is applied for each component of the matrix.
17: end for
18:
end for(End End LA sampling { (1hm pm=1
19:
20: # Compute MC estimator of non-linear IF approximation (12)
21: (2(2z') + EM [Als- (z, tmm) Agg- (z', vm)
22:
23: Output: 22)
C.2 Pseudocode of GEX
Algorithm 2 IGEX
Input: training data S, pre-trained parameter 0", number samples M, number fine-tuning steps T,
two data samples x, z'
2:
3: # Generating Geometric Ensemble (GE; [16])
4: for m 1,..., M (This computation Initialized 6: for f = 1,..., do
parallelized for multiple devices) do
m-th checkpoint 4% <- (or 0%
7: Apply stochastic optimization update (e.g.. SGD with momentum); of, <- 6-.
8: end for(Ent (nd fine-tuning the me-th checkpoint 0%
end [End generation of GE J
10:
11: # Compute the non-linear IF approximation (10)
12: (e 2') + EM= [ (z, 8%) Alg (x', kT.
13:
14: Output: =2,
18

---

D Complexity analysis
Table 6: Comparison of computational complexity between IF approximations. and Plast the entire parameter dimension and the last-layer parameter dimension, respectively. N is the number training samples and R is the projection dimension used in Zarmlai and Treectopp. C' is the number of checkpoints used in Treacte and Trre and T is the number of SGD steps used in Tarx (See Appendix C). Ma and MIA are the number of samples used in Geometric Ensemble and Laplace approximation, respectively. Crervard. Crackvard. and Cypp are the constant for the single computation of forward, backward, and JVP. Crorwadd and Cyvp are similar for packages that offer forward- mode AD computation and Caccuard is much slower than the others.
Time complexity for cache
Space complexity for cache
Time complexity for evaluation
Trisaa
O NaS Craaavrd PP-) ONN Plass)
O(P- N)
OCCaacaart P)
O(P
O Crankverd P)
Treast
Requires internediate ckpts during pre-training
OCC-P) P)
(C Chacuuant P)
Traataat
Requires intermediate ckpts during pre-training
OCC P)
OCC R. R.Copp
Iacuridi
Of Chusbvass P)
(N P)
O Cyp P))
TA with KFAC
O(CrFa - P-N) N)
O P)
O(Ma Ctaroara P))
Tarx-inn
OTT Ma Craccoara P)
O P)
O R. Cyz"
Tax
OCT Mat Cracavace P)
O(Max
O(Mæ Croavace P)
In Table 6, compare computational complexities of various IF approximations, including TGEX- We provide three computational complexities of each IF approximation method: time and space complexity for cache construction and the time complexity for evaluation. As discussed in Sec. 4.3, all IF approximations except TrracIn and TrracIaRP can be implemented using only the final checkpoint, which is usually publicly released. However, the time and space complexity of cache construction significantly different between the post-hoc methods: As mentioned in Sec. 2, the time and space complexity of 1SsS for cache construction are proportional to the size of the training dataset N, as ILASSA requires IHVP computation for each training sample. Therefore, ILASSA cannot be used in datasets with many training samples. On the other hand, Lest-Laaer requires high space complexity proportional to the square of the number of last-layer parameters PLast. As a result, Tiaet-Layer cannot be applied to classification tasks with many classes (e.g., ImageNet [12]. While TArmoIa avoid this issue by using the principal subspace of It, we found that they suffer from the OOM issue on GPU RAM, as eigendecomposition computation (the DISTILL procedure in Schioppa et [52]) requires the space complexity proportional to NArmolai. the number of steps in IArmoldi, which is about 100-200 in Schioppa et al. [52]. However, IaEx and Ieex-lin does not suffer from the high time and space complexity for cache construction, as the cache construction procedure of them is just post-hoe fine-tuning in Garipov et [16].
For the time complexity for evaluation, we assume each method computes a single influence pair (e.g., I(z, z') or I(z, 2)). According to Table 6, all methods except ILa and IGEx require either backward computation (C or JVP computation (Gjup), Among them, methods that require backward computation (ILISSA, Iaast-Layer and Irrecia) do not support batch computation for multiple samples, as mentioned in Sec. 2. Therefore, computing self- seff-influence for all training samples in practice inefficient. On the other hand, methods that require JVP computation (IrracIaRP. TArnoldi, and Togx-lin) are efficient for packages that offer aaward-mode AD computation (e.g., JAX [6]). On the contrary, IL and Taex do not suffer from these issues, as they require only forward computation.
E Experimental settings
In the main paper, we conducted empirical studies in four different settings. We provide details on these settings in this section. We use four random seeds to compute the standard errors for all experiments in the main paper. We use 8 NVIDIA RTX 3090 GPUs for all experiments.
Two-circle classification task We use a modified two-cirele classification task to study the side effects of damping and truncation in Sec. 4. We use sklearn. datasets www.eaaaicllaaaaaae circles function to sample the training samples. We use 30 train samples for each class (circle) and add ten influential samples at the center. We use a two-layer fully connected NN with hidden dimension of 200. We use ja.. hessian function to compute the Hessian matrix of training loss and np. www.lllll..... eigh to compute the principal subspace of H
19

---

Detecting and relabeling of mislabeled samples Noisy label settings [67] are used to study the distributional bias of the standard bilinear IF approximations. We use standard datasets in the computer vision domain: MNIST [33], CIFAR-10/100 [27]. and SVHN [42]. For MNIST, we use VGGNet-B
[55] with batch normalization [23] after each convolution layer, similar to pytorch implementation in https: //pp:://pyttae //tp://ptttchhhc org/visionn htt//visin/maaaaae htt//mainnmmmo/// wwwnn//omls////eemeeeeeeememmeee /vgg--gg... .ttml. We use ResNet- 18 [20] for CIFAR and SVHN. We use random label corruption for 10% of randomly selected training samples for synthetic noise and CIFAR-N [64] for real-world label noise. We use batch size of 1024 for all datasets. For all datasets, we use the cosine learning rate annealing [36] with a linear warm-up where the peak learning rate is 0.4, and the warm-up ratio (percentage of warm-up steps training steps) is 10%. We use 0.0005 for the L2 regularization coefficient. We use 200 training epochs for all datasets.
To verify the scalability of our method, we also use ImageNet [12] with Vision Transformer [13] and ML.-Mixer [60]. We use the "S-32" setting due to the heavy computation of ImageNet. We use random label corruption for 10% of randomly selected training samples. We use batch size 4096 and RandomResizeddrrop following Zhuang et al. [68]. We use the cosine learning rate annealing with a linear warm-up where the peak learning is 0.003 and the warm-up step is 10,000. We use AdamW [37] with 0.3 for the weight decay coefficient. We train 300 epochs for ImageNet, following Zhuang et al. [68].
To verify the effectiveness of our method in another modality, we train SWEM [53] to DBpedia [34], following Pruthi et al. [48]. However, Pruthi et al. [48] used this setting for clean label case study, while we used for noisy label detection with 10% label corruption. For text representation. we use SentencePiece [28] tokenizer and apply average pooling of word embeddings. We train 60 epochs using the AdamW [37] optimizer with a peak learning rate of 0.001 and a weight decay of 0.001. We performed a grid search on the search space mentioned in [53] to find these hyperparameters. aiming to achieve the 95.5% train accuracy mentioned in [48]. We provide our results in Appendix F. Deep-KNN was omitted because it took more than 15 hours to calculate for each random seed.
We use 20 dimensions for all projection-based methods (i.e., TrandProj. IrraCInRF ZArnolds). We use 100 iterations for Zarooldi. Five checkpoints, evenly sampled from the latter half of training epochs, are used for IIreCIaPP and Deep-KNN. We use 10% of training samples to compute the neighborhoods in Deep-KNN. KNN. For CL, we use two-fold cross-validation. Thus, CL requires at least a separate pre- training level of computational cost. We use 20 initial training epochs for EL2N with five repetitions. We use 32 samples for Ia and Tagx. We use cosine learning rate of 0.05 with 800 steps for the fine-tuning procedure to generate GE, We provide an ablation study exploring the impact of ensemble size in Appendix F.
Dataset pruning We conducted dataset pruning task in Paul et al. [46] to validate TaEx for clean label settings. We use the same pre-training and post-hoc hyperparameters as noisy label settings for this task (except for the presence of mislabeled samples). Since the pruning capacity (i.e., the maximum number of samples to be pruned) of all datasets is not the same, we prune 40K samples for MNIST (within 1% test acc. degradation for all methods), 25K samples for CIFAR-10 and SVHN (within 0.5% test acc. degradation for F-score, EL2N, and IαEx), and 20K samples for CIFAR-100 (within 4% test ACC. degradation for TEEX, F-score, ITa).
Sepearation of data sources We also conducted a data source separation task in Harutyunyan et al. [19] to validate Tœxx for clean label settings. In this task, we train a ResNet-18 on a mixed dataset of MNIST and SVHN, with 25, 50000 random subsamples for each training dataset. The other pre-train and post-hoe hyperparameters are the same as for noisy labels.
F Additional results
In this section, we conducted additional experiments for completeness. To this end, we provide an ablation study for the ensemble size of TOEX in Appendix F. We also provide additional results of Sec. 5 in Appendix F.2 F44. In Appendix F:5, we report the noisy label detection performance with cross-influence. Finally, we study a purely post-hoc TrrocInpe by using GE in Appendix F.6.
20

---

F1
Ablation study for the ensemble size
Table 7: AUC and AP for noisy label detection with 10% label corruption
CIFAR-I0
CIFAR-I00
Ma
AUC
AP
AP
32
99.74 0.02
98.31 = 0.06
99.33 = 0.03
96.08 0.12
99.73 0.01
0.01
98.16
99.32 0.03
9..92
9
9.07
99,29
9.11
9.07
97.99
99.25
95.59 0.12
9.02
0.08
9.13 9.02
12
9.06
9..04
94.94 9.05
99.57
9 0.12
94.16
99.40 * 0.04
96.27
98.75 * 0.07
92.99 * 0.18
Themoldi (Mamelas 100, R 20)
61.64 0.13
17.05
77.20 + 0.35
22.61 + 0.42
VeracInte (C 5 20)
89.56 0.14
4.326
0.25
21.62 # 0.26
To evaluate the effectiveness the size of an ensemble in TeEx, we conduct an ablation study for the number of fine-tuned models Mae for the noisy label detection task in Sec. 5.1 with 10% label corruption. Table 7 shows that even a small number of checkpoints (about 8) can achieve better performance of GEX than other state-of-the-art IF approximations, While we used 32 checkpoints to ensure low variance of results, small checkpoints as small as may be sufficient situations requiring low computational cost.
F.2 Results on MNIST and SVHN
Table 8: Noisy label detection performance on MNIST and SVHN
Table 9: Relabeled test accuracy for mislabeled samples
MNIST
SVHN
MNIST
SVHN
Detection method
AUC
AP
AUC
AP
Clean
Deep-KIN
97.28 0.13
90.34
0.41
93.07 i 0.06
Noisy
0.04
CL
87.31 = 0.07
58.
0.226
59.18
11.04
Desection method
Relabeled ace.
F-score
96.67 0.03
$7.2420.13
0.07
2.072
Deep-RK3
58. 0:04
95.15 0.0
EL22N
99.99 0.00
99,90
2 0.02
9.070
9.03
CL
64.57 0.30
79.08
0.05
F-acoze
91.25 0:08
91.71 0.10
JaundPeoj
70.90 + 0.48
20.61 + 0.46
0.28
17194
F1.2H
99.13 + 0.04
95.86 0.04
Treactane
97.22 0.05
71.22 0.54
0,152
47.25 =
99.78 0.07
96.39 0.06
Iemrsiss
70.02 2 0.44
19.88 : 0.40
58.23
0.48
17.71 0.24
Treetso
98.08
94.
Togr-lia
91.67 a 0.23
62.93 à 0.75
61.59 à: 0.18
18.95 0.17
Jamonss
99.99 0.00
99,90 0.02
99.74 0.00
96.59
Zepe-tto
Xua
98.89 0.03
96.32 0.03
(a) MNIST
(b) SVHN
Figure 5: Data pruning results on MNIST and SVHN.
In this section, provide the additional results of Sec. for MNIST [33] and SVHN [42] with 10% label corruption. The overall tendency of MNIST and SVHN similar to the results in Sec. 5. While EL2N is comparable (or even better) to Tozx on MNIST, their good performance is not generalized to more scalable and practical settings in CIFAR-N [64], and ImageNet [12].
21

---

F33 Results on DBpedia
Table 10: Noisy lahel detection performance DBpedia
DBPedia
Delection method
AUC
AP
CL
86.49 0.01
56.14 0.04
F-score
48.18 0.15
8.91 + 0.01
EL2N
99.56 + 0.00
95.26 + 0.02
TaandProj
98.42 a: 0.05
79.05 0.90
Trraciase
98.42 * 0.04
79.34 0.60
Tasuolas
98,54 + 0.02
80.69 0.25
Tig
97.10 + 0.13
74.46 1.14
TOEX
99.79 * 0.00
97.83 0.03
In this section, we provide the additional results of Sec. 5.1 for DBPedia [34] with SWEM [53]. Table 10 shows that GEX better discriminates noisy labels than other methods. In addition to the robustness of various model types (including VGGNet, ResNet, VÝT, and MLP-Mixer) and noise types (synthetic label noise and real-world label noise), this result indicates that GEX has consistently excellent performance for various data types.
F,4
Results on 30% label corruption
Table 11: Noisy label detection performance with 30% label cor-
Table 12: Relaheled test accu- racy for mislabeled samples
ruption
CIFAR-10 10
CIFAR- 100
CIEAR-10
CIFAR-100 100
Detection method
AUC
AP
AUC
AP
Clean
0.06
7908 0.05
Noney
70.81
Deep-Kll KNN
88.39 a: 0.57
77.94 : 1.04
82.09
0.23
64.01
0.37
method
Relabeled
CL
82.28 0.04
64.55
0.06
78.36
0.13
60.42 0.18
F-score
31.98 0.21
53.61 0.12
28.91 0005
Deep-KA.
CL
38.26 0.02
0:43
30.25 0.00
9.01
97.8110.00
97.50 0.03
93.17
P-acore
65
D:57
44.13=0.40
TaanPPooj
0.51
33.36 0.29
71.72 + 0.01
46.33 0.20
EL2H
88.07 0.177
60.56 0.13
Treaciah
84.08 0.56
59.56 + 0.85
68.30 0.29
43.79 0.37
Teattred
79.80
58.58 0.19
Tarasss
0.51
32.80
4..38 0.05
Sametes
79.59
58.76 0.32
58.50 0.28
Tagsii
58.82
33.93 + 0.26
69.36 1:6660000 0.25
43.96 0.21
Igss-ino
Iax
99.74 0.01
98.19 + 0.06
98.98 0.01
97.84 = 0.03
Zgo
0.06
In this section, provide the additional results of Sec. 5.1-5.2 with 30% label corruption. Table 11-12 shows that Tezz achieves better detection and relabeling performance than other methods on higher label noise settings. This is consistent with the empirical evaluation in Sec. 5 and shows the practicality of Teex.
F5 Cross-influence results for noisy label detection
Table 13: AUC and AP for noisy label detection tasks four datasets
MNIST
CIFAR-I0
CIFAR- 100
SVHN
Detection method
AUC
AUC
AUC
AP
AUC
AP
TrandPee
56.64 +
87.42 0.61
58.72 + 0.40
36.35 + 0.56
51.59 + 0.47
37.51+0.33
59.97 1.62
37.21
1.45
Traciiat
57.09 + 1.11
87.84 0.31
60.74 # 0.77
51.04 1.11
51.88 + 0.22
36.67 0.35
64.10 + 0.69
54.46
1.49
Zarwher
76.09 0.66
93.76 1 0.17
77.64
0.93
62.20 2 2000
53.64 0.67
38.8 0.39
1.52 80.85
64.62
2.84
Tex
99.83 + 0.03
99.83 + 0.03
86.82 + 1.24
81.98 + 1.58
98.96 + 0.01
97.69 + 0.02
99,32 a 0.19
97.51 0.55
In this section, we apply the cross-influence on test dataset Stest defined
I(z, Steet) =
Σ I(z, z')
Steeet
x'E
22

---

for the noisy label detection task in Appendix F.4. As the wveriiting/memorizatioo of mislabeled samples causes performance degradation for NNs, the estimated eross woss-influence values should be negative for these samples. Table 13 shows that IF approximations represent this tendency correctly. Mislabeled samples are best distinguished from clean samples using LaEX-
F.6 TracInRP with Geometric Ensemble checkpoints
Table 14: Noisy label detection performance for TrraCToRD with Geometric Ensemble checkpoints
MNIST
CIFAR-IB
CIFAR- 100
SVHN
Detection method
AUC
AP
ADC
AP
AUC
AP
AUC
AP
7
20.61
62.70 0.19
1.11
0.32
26.25 0.47
58.82 0.28
17.94
Traacttto
68.87 0.12
0.97
89.56
0.14
44,26
74.99 0.25
21.62 0.26
91.52
+
Tractap with GF
0.47
90.96 0.14
0.25
88.84
48,91 0.85
85.35 +
23,06 0.23
Lax
99.98 = 0.00
99.87 0:01
2..74
98.31
99.33 0:00
96.08 0.12
99.74 0.00
96.59 0.06
As discussed in Sec. 2, IrracIn and Trrccimp are not purely post-hoc as they require intermediate checkpoints during pre-training. Motivated by Iezx, one can propose to replace the intermediate checkpoints of IIraCIaPP with post-hoc checkpoints generated by Geometric Ensemble. In this section, we evaluate this setting for the noisy label detection task in Sec. 5.1. Table 14 shows that this modification consistently outperforms ZRaddProj. which uses the last checkpoint 6 only. Also, TrracIaRP with GE performs better than the original TrracInRe except SVHN. However, this improvement does not outperform IZEI-
F.7 Further ImageNet results
Table 15: Relabeled accuracy for ImageNet [12]
Table 16: Pruned acc. for ImageNet [12]
VIT-S-32
Mixer-S-32
Mixer-S-32
Clean acc.
67.83%
64.37%
Full sample acc.
67.83%
Noisy acc.
63.42%
61,84%
Pruned with EL,N
54.87%
Relabeled with EL2N
63.18%
63.16%
Relabeled with GEX
66.17%
63.45%
Pruned with GEX
56.34%
Our first additional ImageNet experiment is the relabeling task presented in Sec. 5.2 on the ImageNet- IK environment with ViT and MLP-Mixer. To this end, we follow the relabeling process in Sec. 5.2 with the estimated influence in Table 2. As ViT and Mixer use multi-task binary classification loss instead of cross- cross-entropy loss, the relabel function in (16) cannot be applied to this setting. To mitigate this issue, we use well-known distillation loss [21] for detected influential samples. Therefore, these influential samples receive milder signal than from the hard label of the initial training. Table 15 presents the relabeled test accuracy for TaEx and EL2N (the best method for noisy label detection except ours). shows that ToEx can detect mislabeled samples that require relabeling more accurately than EL2N. The second additional ImageNet experiment is the dataset pruning task in Sec. 5.3 on the ImageNet-IK 1K with MLP-Mixer. For this purpose, we reproduce Mixer-S-32 and estimate the self-influence of TEEX and EL2N score (which verified its scalability on the dataset pruning task in Sorscher et al. [58]). Then, prune 512,466 samples (40%) with the smallest self-influence in ImageNet-1K and retrain neural networks with these pruned datasets. Table 16 presents the pruned test accuracy for Texx and EL2N. Similar the results shown in Fig. 4, TGEx demonstrates more effective identification of prunable samples than EL2N on the scalable ImageNet- IK dataset. Additionally, it is worth noting that EL2N cannot make use of open-source checkpoints and requires a computational cost of (10 ~ 20 epochs) x (number of checkpoints) from initialized neural network. In summary, the better-prund pattee-pruned accuracy and the lower computational cost further illustrate the effectiveness of TeEx in scalable settings.
23

---

G Limitations and Broader Impacts
While ZaEx effectively captures the multi-modal nature I 's self-influence distribution, we do delve into the theoretical guarantees, such as approximation bounds, for Toex. Nevertheless, we believe that this concern can be addressed in future research by making assumptions about the SGD steps used in generating checkpoints. Furthermore, although the data pruning results of IGEX are significantly superior to other methods approximating IF, they do not outperform the performance achieved by state-of-the-arr techniques like F-score and EL2N. This issue can be resolved by implementing the iterative pruning approach proposed in Harutyunyan al. [19].
Our study examines the distributional bias present in current IF approximations and proposes an efficient solution. As result, our approach has broad applicability in different scenarios. Specifically, our method offers enhanced efficiency in identifying mislabeled and prunable samples compared existing approaches. Consequently, believe that our method can contribute enhancing and expediting the training process of energy-intensive intensive deep learning models.
24


Reviews:
[{"review_id": "otwjLHikfI", "reviewer": "Reviewer_8KEq", "summary": "In this paper, the authors point out that standard approximations of Influence Function (IF) suffer from performance degradation due to oversimplified influence distributions caused by their bilinear approximation, suppressing the expressive power of samples with a relatively strong influence. Therefore, they propose a new interpretation of existing IF approximations as an average relationship between two linearized losses over parameters sampled from the Laplace approximation (LA). By doing so, they highlight two limitaions and propose GEX to improve them. The proposed GEX outperforms standard IF approximations in downstream tasks, including noisy label detection, relabeling, dataset pruning, and data source separation.\n", "questions": "1. I think nosiy label detection combined with relabeling mislabeled samples is very useful in many practical scenarios. But the experiments are only executed on CIFAR, which is a quite small dataset. What is the result if we use GEX to detection noisy labels in Imagenet and relabel them?\n2. How can this approach help some pratical scenarios?", "limitations": "See weakness. Most experiments are executed on small and relatively easy datasets. The effectiveness of this approach on those more challenging and large benchmarks is not explored.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper is well written. The details of movtivation, methodology, experiments and proofs are described clearly.\n2. The insight of this paper is quite reasonable and the proposed approach looks novel.\n3. The proposed method is verified on a wide range of downstream tasks, including noisy label detection, relabeling, dataset pruning, and data source separation.", "weaknesses": "1. In table 2, the gap between GEX and the other settings is very large. It seems that the other settings are not specificly designed for this task. Is this comparison meaningful?\n2. Except table 2, the other experiments are executed on some small and relatively easy dataset, I am not sure whether the conclusions from these results are solid enough.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful review and constructive comments! We give point-to-point replies to your comments in the following.\n\n* Q1. [**Scalability issue of other IF approximations**] In table 2, the gap between GEX and the other settings is very large. It seems that the other settings are not specificly designed for this task. Is this comparison meaningful?\n\n* A1. The Influence Function (IF), EL2N, and F-score are known to be applicable for noisy label detection [1, 2, 3], which can be confirmed by Table 1 of our paper. Table 2 aims to investigate whether the findings from Table 1 are scalable to large-scale datasets. This table shows that other influence approximations exhibit significant performance degradation compared to GEX. A similar scalability issue was pointed out in [4] in the context of dataset pruning. The scalability issue also exists for non-influence approximation methods: F-score fails in cases where certain samples were never correctly predicted during pre-training, as mentioned in Lines 283-284. Since EL2N is based on the Brier score (i.e., L2 distance of prediction and label) at the early training phase, there is a performance degradation in the ImageNet setting where the training speed is slow. However, GEX does not suffer from such a scalability issue.\n\n  [1] Koh, Pang Wei, and Percy Liang. \"Understanding black-box predictions via influence functions.\" International conference on machine learning. PMLR, 2017.\n\n  [2] Mansheej Paul, Surya Ganguli, and Gintare Karolina Dziugaite. Deep learning on a data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 34:20596–20607, 2021\n\n  [3] Mariya Toneva, Alessandro Sordoni, Remi Tachet des Combes, Adam Trischler, Yoshua Bengio, and Geoffrey J Gordon. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv:1812.05159, 2018.\n\n  [4] Sorscher, Ben, et al. \"Beyond neural scaling laws: beating power law scaling via data pruning.\" Advances in Neural Information Processing Systems 35 (2022): 19523-19536.\n\n* Q2. [**Scalability of GEX**] Except table 2, the other experiments are executed on some small and relatively easy dataset, I am not sure whether the conclusions from these results are solid enough. // I think nosiy label detection combined with relabeling mislabeled samples is very useful in many practical scenarios. But the experiments are only executed on CIFAR, which is a quite small dataset. What is the result if we use GEX to detection noisy labels in Imagenet and relabel them?\n\n* A2. Following the recommendation of reviewer 8KEq, we further validate the scalability of GEX by extending the relabeling task (Section 5.1) and dataset pruning task (Section 5.2) to the ImageNet-1K setting. We refer to G1 [**Additional experiments: Relabeling**] and G2 [**Additional experiments: Dataset pruning**] in the Global Rebuttal for these results.\n\n* Q3. [**Practical scenarios for GEX**] How can this approach help some pratical scenarios?\n\n* A3. The tasks of noisy label detection, relabeling, and dataset pruning presented in Section 5 have several practical applications. One of the applications of GEX is to prune samples with minimal impact on training, allowing for more efficient training than conventional neural scaling laws, as described in [1]. Also, GEX can effectively detect and correct mislabeled samples in datasets obtained from (noisy) crowd annotations, where various people contribute to labeling (as demonstrated in Section 5.1-5.2).  For instance, recent research in the medical domain, particularly on chest X-rays [2, 3], shows that annotations made by doctors in public datasets are sometimes incorrect [2]. Thus, models trained with these datasets can be improved by retraining or fine-tuning with corrected labels [3]. Considering that GEX improves performance in a general relabeling benchmark, it is reasonable to expect that it will also enhance performance in medical applications.\n\n  [1] Sorscher, Ben, et al. \"Beyond neural scaling laws: beating power law scaling via data pruning.\" Advances in Neural Information Processing Systems 35 (2022): 19523-19536.\n\n  [2] Tang, Siyi, et al. \"Data valuation for medical imaging using Shapley value and application to a large-scale chest X-ray dataset.\" Scientific reports 11.1 (2021): 8366.\n\n  [3] Kim, Doyun, et al. \"Accurate auto-labeling of chest X-ray images based on quantitative similarity to an explainable AI model.\" Nature communications 13.1 (2022): 1867.\n\n  [4] Wang, Xiaosong, et al. \"Chestx-ray8: Hospital-scale chest x-ray database and benchmarks on weakly-supervised classification and localization of common thorax diseases.\" Proceedings of the IEEE conference on computer vision and pattern recognition. 2017."}, {"review_id": "qSetlCY9qd", "reviewer": "Reviewer_sNxP", "summary": "The paper identifies that existing influence functions suffer from a fundamental drawback due to their bilinear form. To address, this they propose an influence calculation that is nonlinear                                                    . ", "questions": "I did not find it very clear what benefit or cards the geometric ensemble brings to the table. \n\nIt would be nice to have an actual example using only open source checkpoints, since this is one of the purported benefits of the research. \n\nIn the limitations, the authors believe their method can expedite the training process of energy-efficient deep learning models. ", "limitations": "In the appendix. ", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The GEX influences seem to outperform all baselines when detecting label noise on CIFAR10-like datasets. \n\nThe approach is motivated by principled failures of existing influence functions due to factors such as singularity of the Gaussian. ", "weaknesses": "There is a lot of information pushed to the appendix that is reference in the main text, to the extent that it more difficult to really understand without having the appendix at hand. The current main text was too sparse for me to really understand any particular component. \n\nIt seems the experiments largely focused on MNIST/SVHN/CIFAR10 variants. It would be nice to see some kind of breadth in application or scalability to more than CIFAR10. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review of our paper. We appreciate your feedback and would like to provide point-to-point replies to your questions in the following.\n\n* Q1. [**Lack of details in main text**] There is a lot of information pushed to the appendix that is reference in the main text, to the extent that it more difficult to really understand without having the appendix at hand. The current main text was too sparse for me to really understand any particular component.\n\n* A1. We apologize for not including all the necessary content within the main text due to the length constraints. We understand that relying heavily on the appendix might affect the readability. Our appendix contains additional material, such as proofs for propositions discussed in the main text, complexity analysis, experimental setups, and additional experimental results. We use this supplementary content to support the key points covered in the main paper, including the problem we address (distributional bias in Section 3) and the rationale behind our approach (Section 4). If you have any suggestions regarding specific content from the appendix that should be moved to the main text, please share them with us. We will take your feedback into careful consideration while preparing the revised version.\n\n* Q2. [**Scalability of GEX**] It seems the experiments largely focused on MNIST/SVHN/CIFAR10 variants. It would be nice to see some kind of breadth in application or scalability to more than CIFAR10.\n\n* A2. Following reviewer sNxP's recommendation, we verify the scalability of GEX for various tasks. In fact, Table 2 in our paper provides evidence that the effectiveness of GEX in Table 1 scales well with larger datasets by showing that GEX outperforms the baselines in noisy label detection tasks on ImageNet-1K with ViT and MLP-Mixer. In the rebuttal phase, we further validate the scalability of GEX by extending the relabeling task to the ImageNet-1K setting. We refer to G1 [**Additional experiments: Relabeling**] in the Global Rebuttal for these results.\n\n* Q3. [**Rationale for using GE**] I did not find it very clear what benefit or cards the geometric ensemble brings to the table.\n\n* A3. We use the GE distribution because GE is suitable for expressing the local geometry of the loss landscape around $ \\theta^* $, similar to LA. However, unlike LA, GE does not overestimate loss deviations due to the singularity of Hessian. To clarify this, we will revise the introduction of Section 4 (Lines 155-162) as follows:\n  To mitigate the distributional bias in Section 3, we propose a flexible IF approximation method using Geometric Ensemble (GE; [15]), named Geometric Ensemble for sample eXplanataion (GEX). Here is a summary of how GEX is developed.\n  $$\n  \\mathcal{I}\\_\\mathtt{Hess}\n  \\overset{\\texttt{Delinearization}}{\\underset{\\texttt{Section 4.1}}{\\longrightarrow}}\n  \\mathcal{I}\\_\\mathtt{LA}\n  \\overset{\\texttt{LA to GE}}{\\underset{\\texttt{Section 4.2}}{\\longrightarrow}}\n  \\mathcal{I}\\_\\mathtt{GEX}\n  $$\n  In Section 4.1, we ensure that the influence approximation is not a bilinear form for the gradient by replacing gradients in IF with sample-loss deviations. The theoretical foundation for this step is provided by our Theorem 1 below, which establishes a relationship between the IF and the Laplace approximation (LA; [36]). Moving on to Section 4.2, we modify the parameter distribution to compute the sample-loss deviation from LA to GE. This modification is necessary because GE is based on the local geometry of the loss landscape around $\\theta^*$, similar to LA while avoiding overestimating loss deviations caused by the singularity of the Hessian.\n\n* Q4. [**Experiments using open-source checkpoints**] It would be nice to have an actual example using only open source checkpoints, since this is one of the purported benefits of the research.\n\n* A4. Following the recommendation of reviewer sNxP, we tried to conduct additional experiments by extending the dataset pruning task in Section 5.4 to ImageNet-1K with MLP-Mixer. However, as Mixer-B-16 and bigger models, which is beyond our computational budget, are released in the official repository, we decided to pre-train the smaller Mixer-S-32 model and conduct experiments. The reproduced accuracy of Mixer-S-32 is 64.37%, which is higher than the published accuracy of 63.9% [1, 2]. We refer to G2 [**Additional experiments: Dataset pruning**] in the Global Rebuttal for these results."}, {"review_id": "eAEMz0Fb2k", "reviewer": "Reviewer_TEqY", "summary": "This paper proposes a new method for approximating influential examples. It treats losses as non-linear functions, addresses the singularity problem of hessians and does not require multiple checkpoints or JVP computations for the influence. The authors also highlight a connection between Influence Functions (IF) and Laplace Approximation (LA) and discuss its limitations. They propose an approximation using Geometric Ensembles (GE) instead. The authors show empirically that their approach outperforms existing IF approximation methods on downstream tasks for noisy label detection, relabeling, dataset pruning and data source separation.", "questions": "+ Line 167: what’s the motivation of choosing Dirac delta distribution\n+ Figure 2: Are 2a - 2d computed for self-influence or influence w.r.t. Test examples ? Have we compared I_GEX with I_Hess for influence on test examples ?  What does typical vs influential mean for self-influence ? High self-influence means that these are potentially mislabeled. So we want to say that the green ones are mislabeled ? \n+ In terms of evaluation were there any experiments made for the original tracin without random projections for the Table 1.\n", "limitations": "The limitations of the work are not discussed. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ The paper aims to address two important limitations of influential examples: singular nature of hessians and linearity of influence functions.\n+ The paper is well written, related work and existing limitations are properly discussed.\n+ The paper also discusses and benchmarks their approach on several important downstream tasks including noisy label detection, relabeling and dataset pruning on several datasets and models.\n\n", "weaknesses": "+ The authors emphasize bilinear approximation but they do not explain what bilinearity applies to in the approximations. It would be good to explain it briefly to make it clear.\n+ The overall motivation of GEX using dirac distribution in section 4.1 seems a bit unclear. It seems that GEX is highlighted by surfacing the connection between IF and Laplace Approximation (LA) and the limitations of p_{LA} but it is still unclear why GE distribution (Eq. 9) was chosen.\n+ It’s a bit challenging to follow the descriptions of Figures 2 and 3 since the authors refer both to influence and self-influence. Self-influence also means potentially mislabeled and it is unclear whether it is what the authors mean. Typical vs influential annotations on those figures are also a bit unclear. What does typical mean in this case ?\n\n**Minor comments**\n+ Figure 2: Are 2a - 2d: axes annotations are missing.  Perhaps it would be good to mention that these are histograms in advance or in figure description.\n+ Eq 9: parameter \\psi is not explained in that section.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for reviewing our paper so thoroughly. We appreciate your feedback and would like to provide point-to-point replies to your questions in the following.\n\n* Q1. [**Bilinearity used in IF approximations**] The authors emphasize bilinear approximation but they do not explain what bilinearity applies to in the approximations. It would be good to explain it briefly to make it clear.\n\n* A1. The bilinearity in our paper refers to the influence approximations being bilinear with respect to the sample-wise gradients. Consequently, the self-influence based on these bilinear metrics (Eq. (2), (5), (6), and (7)) is quadratic for sample-wise gradients. Intuitively, bilinear approximation methods can be understood as inner products of sample-wise gradients with additional consideration of curvature. We will revise the manuscript to incorporate this explanation in Line 118.\n\n* Q2. [**Rationale for using GE**] The overall motivation of GEX using dirac distribution in section 4.1 seems a bit unclear. It seems that GEX is highlighted by surfacing the connection between IF and Laplace Approximation (LA) and the limitations of p_{LA} but it is still unclear why GE distribution (Eq. 9) was chosen.\n\n* A2. We use the GE distribution because GE is suitable for expressing the local geometry of the loss landscape around $ \\theta^* $, similar to LA. However, unlike LA, GE does not overestimate loss deviations due to the singularity of Hessian. To clarify this, we will revise the introduction of Section 4 (Lines 155-162) as follows:\n  To mitigate the distributional bias in Section 3, we propose a flexible IF approximation method using Geometric Ensemble (GE; [15]), named Geometric Ensemble for sample eXplanataion (GEX). Here is a summary of how GEX is developed.\n  $$\n  \\mathcal{I}\\_\\mathtt{Hess}\n  \\overset{\\texttt{Delinearization}}{\\underset{\\texttt{Section 4.1}}{\\longrightarrow}}\n  \\mathcal{I}\\_\\mathtt{LA}\n  \\overset{\\texttt{LA to GE}}{\\underset{\\texttt{Section 4.2}}{\\longrightarrow}}\n  \\mathcal{I}\\_\\mathtt{GEX}\n  $$\n  In Section 4.1, we ensure that the influence approximation is not a bilinear form for the gradient by replacing gradients in IF with sample-loss deviations. The theoretical foundation for this step is provided by our Theorem 1 below, which establishes a relationship between the IF and the Laplace approximation (LA; [36]). Moving on to Section 4.2, we modify the parameter distribution to compute the sample-loss deviation from LA to GE. This modification is necessary because GE is based on the local geometry of the loss landscape around $\\theta^*$, similar to LA while avoiding overestimating loss deviations caused by the singularity of the Hessian.\n\n* Q3. [**Elaborations for Figures 2-3**] It’s a bit challenging to follow the descriptions of Figures 2 and 3 since the authors refer both to influence and self-influence. Self-influence also means potentially mislabeled and it is unclear whether it is what the authors mean. Typical vs influential annotations on those figures are also a bit unclear. What does typical mean in this case? // Figure 2: Are 2a - 2d: axes annotations are missing. Perhaps it would be good to mention that these are histograms in advance or in figure description. // Figure 2: Are 2a - 2d computed for self-influence or influence w.r.t. Test examples ? Have we compared I_GEX with I_Hess for influence on test examples ? What does typical vs influential mean for self-influence ? High self-influence means that these are potentially mislabeled. So we want to say that the green ones are mislabeled ?\n\n* A3. Figures 2-3 are all **histograms of self-influence**. In this setting, we do not measure influence w.r.t. test examples. Generally, \"Typical samples\" are those in which the presence or absence of individual samples has no significant impact on the decision boundary (i.e., low self-influence). In our setting, the typical samples are the two outer circle samples with relatively high density in Figure 2(a). Conversely, \"Influential samples\" refer to individual instances that substantially influence the decision boundary, resulting in high self-influence. Hence, influential samples correspond to the inner circle in Figure 2(a), demonstrating relatively low density. Note that mislabeled samples also greatly impact the decision boundary. We will modify Figure 2 (a) as G4. [**Modified Figure 2 (a)**] in the Global rebuttal. Also, We will clarify this information with axes annotations in the caption of Figure 2 of the revised manuscript.\n\n* Q4. [**Motivation of choosing Dirac delta**] Eq 9: parameter \\psi is not explained in that section. Line 167: what’s the motivation of choosing Dirac delta distribution\n\n* A4. $\\psi \\in \\mathbb{R}^{P}$ is an arbitrary vector in the parameter space to denote the Dirac delta distribution and Gaussian distribution. We will clarify this in Line 167 of the revised version. We used the Dirac delta distribution to represent the empirical parameter distribution of GE. This is a common usage of the Dirac delta distribution, as mentioned in p.64 of [1]: \"A common use of the Dirac delta distribution is as a component of an empirical distribution, ~\"\n\n  [1] Goodfellow, Ian, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.\n\n* Q5. [**Comparison to TracIn**] In terms of evaluation were there any experiments made for the original tracin without random projections for the Table 1.\n\n* A5. We refer to G3 [**Additional experiments for TracIn**] in the Global Rebuttal for these results.\n\n* Q6. [**Limitations**] The limitations of the work are not discussed.\n\n* A6. We discuss our method's limitations and broader impacts in Appendix G. We will clarify this information after the discussion in Section 4.3 (Practical advantages of GEX) in the revised manuscript.\n\n"}, {"review_id": "KTJEeymfDl", "reviewer": "Reviewer_FeGS", "summary": "The paper provide a novel connection between IF approximations and LA, and introduces a new IF approximation method. The motivation takes advantage from two observations, the removal of linearization can alleviate the bilinear constraint and, the utilization of Geometric Ensemble is advantageous.  Empirical results demonstrates the advantage of the proposed method with reduced computational complexity. ", "questions": "Please see weakness about the scale of the training data above. ", "limitations": "Yes. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper provide a novel connection between IF approximations and LA, and introduces a new IF approximation method. The motivation takes advantage from two observations, the removal of linearization can alleviate the bilinear constraint and, the utilization of Geometric Ensemble is advantageous.  Empirical results demonstrates the advantage of the proposed method with reduced computational complexity. \n\nI enjoyed a lot reading the literature review and the analysis offered by the paper. The paper also introduced several application scenarios where the proposed method demonstrated obvious performance boost, including the noisy label identification task. ", "weaknesses": "W1. The  method is only justified on small dataset such as MIST and SVHN. Is it possible to verify the effectiveness of the method on larger dataset such as ImageNet1K?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your valuable comments and suggestions! We provide a detailed reply to your questions in the following. \n\n* Q1. [**Scalability of GEX**] W1. The method is only justified on small dataset such as MIST and SVHN. Is it possible to verify the effectiveness of the method on larger dataset such as ImageNet1K?\n\n* A1. Following reviewer FeGS's recommendation, we verify the scalability of GEX for various tasks. In fact, Table 2 in our original submission already provides the evidence that the effectiveness of GEX in Table 1 scales well with larger datasets by showing that GEX outperforms the baselines in noisy label detection tasks on ImageNet-1K with ViT and MLP-Mixer. In the rebuttal phase, we further validate the scalability of GEX by extending the relabeling task (Section 5.1) and dataset pruning task (Section 5.2) to the ImageNet-1K setting.\n  \n  Our first additional experiment is the relabeling task presented in Section 5.2 on the ImageNet-1K environment with ViT and MLP-Mixer. To this end, we follow the relabeling process in Section 5.2 with the estimated influence in Table 2. The following table presents the relabeled test accuracy for GEX and EL2N (the best method for noisy label detection except ours).\n  * **Table A. Relabeled accuracy for mislabeled samples**\n    \n    |                     |       ViT-S-32      | MLP-Mixer-S-32 |\n    |:-------------------:|:-------------------:|:--------------:|\n    |      Clean acc.     |        67.83%       |     64.37%     |\n    |      Noisy acc.     |        63.42%       |     61.84%     |\n    | Relabeled with EL2N |        63.18%       |     63.16%     |\n    |  Relabeled with GEX |      **66.17%**     |   **63.45%**   |\n    \n  Table A shows that GEX can detect mislabeled samples that require relabeling more accurately than EL2N.\n\n  The second additional experiment is the dataset pruning task in Section 5.4 on the ImageNet-1K with MLP-Mixer. For this purpose, we reproduce Mixer-S-32 and estimate the self-influence of GEX and EL2N score (which verified its scalability on the dataset pruning task in [1]). Then, we prune 512,466 samples (40%) with the smallest self-influence in ImageNet-1K and retrain neural networks with these pruned datasets. The following table presents the pruned test accuracy for GEX and EL2N:\n  * **Table B. Pruned accuracy for mislabeled samples**\n    \n    |                  | MLP-Mixer-S-32 |\n    |:----------------:|:--------------:|\n    | Full sample acc. |     67.83%     |\n    | Pruned with EL2N |     54.87%     |\n    |  Pruned with GEX |   **56.34%**   |\n    \n  Similar to the results shown in Figure 4, GEX demonstrates more effective identification of prunable samples than EL2N on the scalable ImageNet-1K dataset. Additionally, it is worth noting that EL2N cannot make use of open-source checkpoints and requires a computational cost of (10~20 epochs) x (number of checkpoints) from an initialized neural network. In summary, the better pruned accuracy and the lower computational cost further illustrate the effectiveness of GEX in scalable settings. We will include these results in the revised version.\n  \n  [1] Sorscher, Ben, et al. \"Beyond neural scaling laws: beating power law scaling via data pruning.\" Advances in Neural Information Processing Systems 35 (2022): 19523-19536."}, {"review_id": "frSu8cEhWH", "reviewer": "Reviewer_KU2o", "summary": "This work studies approximations methods for data influence. The work identifies a common theoretical drawback behind popular approximation methods to Influence Function (IF) which suppresses their expressive power and affects their performance.\n\nThis work proposes a novel interpretation of existing IF approximations as some special form of Laplace approximation (LA) and points out that the drawback is due to the linearity of gradients and the singularity of Hessian. This work proposes an original IF approximation method that circumvents these issues, which removes the linearization to ease the bilinear constraint and leverages Geometric Ensemble (GE) for non-linear losses. Both conceptually and empirically, this work demonstrates significant improvement over existing IF approximation methods. The work includes a variety of experiments including many use cases.", "questions": "How does the proposed method compare to TracIn (not TracInRP)? And how does the result compare to the actual counterfactual (LOO)?\n\nAppendix should not be submitted within the main paper, which has a page limit of 9.\n\nWhat is the \"retraining cost of IF\"? IF does not need training or \"retraining\".", "limitations": "See Weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is nicely written. The narrative is smooth and the conceptual development is attractive. The problem being considered is of interest and finding of common drawback behind the mechanism of existing IF approximations is novel and insightful. Visualizations of conceptual findings are very helpful and give a straightforward presentation to help to understand.\n\nEvaluations are thorough. Various use cases are considered and the empirical performance is satisfactory. Comprehensive details for experiments are given in Appendix.", "weaknesses": "Influence Function (IF) refers to the celebrated method proposed in < Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885–1894. PMLR, 2017.> that is used to estimate the quantity in Eq. (1). Equation (1) is essentially the definition for LOO. It is NOT the \"ground truth\" of Influence Function (IF). Eq. (2) is the \"Influence Function\". It is NOT named \"I_{Hess}\".\n\nThe transition to Section 4.1 needs more elaborations. I_GEX proposed in this subsection is the core contribution of the paper, yet it isn't thoroughly discussed before moving on to discussing the limitation of other methods. Similarly, an introduction to LA is much needed as it lays important grounds for the development of this work. I may consider increasing my score if this can be reasonably addressed.\n\nThough the conceptual flow of the paper is smooth, some important parts remain unclear. For example, what is Eq. 9 exactly and how is it calculated in actual implementation? How to conceptually interpret Eq. 10 and how it differs from Eq. 12?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your careful review and constructive comments! We give point-to-point replies to your comments in the following. Official comments will address questions that could not be answered due to the character limit.\n\n* Q1. [**Terminology**] Influence Function (IF) refers to the celebrated method proposed in < Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In International conference on machine learning, pages 1885–1894. PMLR, 2017.> that is used to estimate the quantity in Eq. (1). Equation (1) is essentially the definition for LOO. It is NOT the \"ground truth\" of Influence Function (IF). Eq. (2) is the \"Influence Function\". It is NOT named \"I_{Hess}\".\n\n* A1. As the reviewer mentioned, [1] introduced Eq. (2) as an Influence Function (IF) to provide an approximation for the counterfactual effect of LOO retraining (Eq. (1)). In our work, we used the notation $ \\mathcal{I}\\_\\mathtt{GT} $ and $ \\mathcal{I}\\_\\mathtt{Hess} $ since the similar notations were originally introduced in [2] to emphasize that Eq. (2) approximates Eq. (1) using Hessian. However, we understand that this notation might be misleading for some readers. In response to the reviewer's feedback, we will revise the manuscript, denoting Eq. (1) as $\\mathcal{I}\\_\\mathtt{LOO}$ and Eq. (2) as $\\mathcal{I}$. Moreover, we believe that with this modification, it would become clear that the IF (Eq. (2)) does not require retraining, which addresses the following question: \"What is the 'retraining cost of IF'? IF does not need training or 'retraining'.\"\n\n  [1] Koh, Pang Wei, and Percy Liang. \"Understanding black-box predictions via influence functions.\" International conference on machine learning. PMLR, 2017.\n  \n  [2] Schioppa, Andrea, et al. \"Scaling up influence functions.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 36. No. 8. 2022.\n\n* Q2. [**Elaboration for Section 4.1**] The transition to Section 4.1 needs more elaborations. I_GEX proposed in this subsection is the core contribution of the paper, yet it isn't thoroughly discussed before moving on to discussing the limitation of other methods. Similarly, an introduction to LA is much needed as it lays important grounds for the development of this work. I may consider increasing my score if this can be reasonably addressed.\n\n* A2. Thank you for the helpful suggestions. To provide a clear motivation for GEX, we will revise the introduction of Section 4 (Lines 155-162) as follows:\n  To mitigate the distributional bias in Section 3, we propose a flexible IF approximation method using Geometric Ensemble (GE; [15]), named Geometric Ensemble for sample eXplanataion (GEX). Here is a summary of how GEX is developed.\n  $$\n  \\mathcal{I}\n  \\overset{\\texttt{Delinearization}}{\\underset{\\texttt{Section 4.1}}{\\longrightarrow}}\n  \\mathcal{I}\\_\\mathtt{LA}\n  \\overset{\\texttt{LA to GE}}{\\underset{\\texttt{Section 4.2}}{\\longrightarrow}}\n  \\mathcal{I}\\_\\mathtt{GEX}\n  $$\n  In Section 4.1, we ensure that the influence approximation is not a bilinear form for the gradient by replacing gradients in IF with sample-loss deviations. The theoretical foundation for this step is provided by our Theorem 1 below, which establishes a relationship between the IF and the Laplace approximation (LA; [36]). Moving on to Section 4.2, we modify the parameter distribution to compute the sample-loss deviation from LA to GE. This modification is necessary because GE is based on the local geometry of the loss landscape around $\\theta^*$, similar to LA while avoiding overestimating loss deviations caused by the singularity of the Hessian.\n\n  Also, the revised manuscript will include the following introduction to LA after Theorem 4.1 to assist readers:\n  The LA was proposed to approximate the posterior distribution with a Gaussian distribution. Recently, it has gained significant attention due to its simplicity and reliable calibration performance [1, 2]. Intuitively, LA is equivalent to the second-order Taylor approximation of log-posterior at $ \\theta^* $ with Gaussian prior defined as $p(\\psi):= \\mathcal{N}(\\psi| \\mathbf{0}_P, \\gamma^{-1} \\mathbf{I}_P )$:\n  $$\n      \\log p(\\theta|S)\n      = \\log p(S|\\theta) + \\log p(\\theta) - \\log Z \\\\\n      = - N\\cdot L(S, \\theta) + \\log p(\\theta) - \\log Z \\\\\n      \\approx - N\\cdot L(S, \\theta^*) - \\frac{1}{2}(\\theta-\\theta^*)^{\\top}(N\\cdot H + \\gamma \\mathbf{I}_P )(\\theta-\\theta^*) - \\log Z \\\\\n      = \\log p(\\theta^*|S) - \\frac{1}{2}(\\theta-\\theta^*)^{\\top}(N\\cdot H + \\gamma \\mathbf{I}_P )(\\theta-\\theta^*). \\\\\n  $$\n  Here, the training loss represents the negative log-likelihood $L(S, \\theta) = -\\frac{1}{N}\\log p(S| \\theta)$, and $Z:= \\int p(\\theta) p(S|\\theta) d\\theta$ represents the evidence in Bayesian inference [3]. Similar to the IF, LA becomes computationally intractable when dealing with modern architectures due to the complexity of the Hessian matrix. To address this computational challenge, recent works have proposed various sub-curvature approximations, such as KFAC [1] and sub-network [2], which provide computationally efficient alternatives for working with LA.\n\n  [1] Ritter, Hippolyt, Aleksandar Botev, and David Barber. \"A scalable laplace approximation for neural networks.\" 6th International Conference on Learning Representations, ICLR 2018-Conference Track Proceedings. Vol. 6. International Conference on Representation Learning, 2018.\n  \n  [2] Erik Daxberger, Eric Nalisnick, James U Allingham, Javier Antoran, and Jose Miguel Hernandez- Lobato. Bayesian deep learning via subnetwork inference. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 2510–2521. PMLR, 18–24 Jul 2021b.\n  \n  [3] Bishop, Christopher M., and Nasser M. Nasrabadi. Pattern recognition and machine learning. Vol. 4. No. 4. New York: springer, 2006."}]

Author rebuttal:
* G1. [**Additional experiments: Relabeling**] Our first additional experiment is the relabeling task presented in Section 5.2 on the ImageNet-1K environment with ViT and MLP-Mixer. To this end, we follow the relabeling process in Section 5.2 with the estimated influence in Table 2. The following table presents the relabeled test accuracy for GEX and EL2N (the best method for noisy label detection except ours).
  * **Table A. Relabeled accuracy for mislabeled samples**
    
    |                     |       ViT-S-32      | MLP-Mixer-S-32 |
    |:-------------------:|:-------------------:|:--------------:|
    |      Clean acc.     |        67.83%       |     64.37%     |
    |      Noisy acc.     |        63.42%       |     61.84%     |
    | Relabeled with EL2N |        63.18%       |     63.16%     |
    |  Relabeled with GEX |      **66.17%**     |   **63.45%**   |
    
  Table A shows that GEX can detect mislabeled samples that require relabeling more accurately than EL2N.

* G2. [**Additional experiments: Dataset pruning**]   The second additional experiment is the dataset pruning task in Section 5.4 on the ImageNet-1K with MLP-Mixer. For this purpose, we reproduce Mixer-S-32 and estimate the self-influence of GEX and EL2N score (which verified its scalability on the dataset pruning task in [1]). Then, we prune 512,466 samples (40%) with the smallest self-influence in ImageNet-1K and retrain neural networks with these pruned datasets. The following table presents the pruned test accuracy for GEX and EL2N:
  * **Table B. Pruned accuracy for mislabeled samples**
    
    |                  | MLP-Mixer-S-32 |
    |:----------------:|:--------------:|
    | Full sample acc. |     67.83%     |
    | Pruned with EL2N |     54.87%     |
    |  Pruned with GEX |   **56.34%**   |
    
  Similar to the results shown in Figure 4, GEX demonstrates more effective identification of prunable samples than EL2N on the scalable ImageNet-1K dataset. Additionally, it is worth noting that EL2N cannot make use of open-source checkpoints and requires a computational cost of (10~20 epochs) x (number of checkpoints) from an initialized neural network. In summary, the better pruned accuracy and the lower computational cost further illustrate the effectiveness of GEX in scalable settings. We will include these results in the revised version.
  
  [1] Sorscher, Ben, et al. "Beyond neural scaling laws: beating power law scaling via data pruning." Advances in Neural Information Processing Systems 35 (2022): 19523-19536.

* G3. [**Additional experiments for TracIn**] The downstream task performance of TracIn and TracInRP is similar, as mentioned in the TracIn paper [1]. In the rebuttal phase, we additionally measure the performance of TracIn on the noisy label detection (Section 5.1) and relabeling (Section 5.2) tasks to verify this. Due to the high time complexity associated with sample-wise gradients, we do not repeatedly measure the self-influence of TracIn. The following tables present the noisy label detection performance and relabeled accuracy achieved by TracIn with baselines (TracInRP and GEX).
  
  * AUC (Area Under the Curve) and AP (Average Precision) results for different datasets
  * 
    |     AUC / AP    |     CIFAR-10 (synthetic)    |    CIFAR-100 (synthetic)    |          CIFAR-10-N         |         CIFAR-100-N         |
    |:---------------:|:---------------------------:|:---------------------------:|:---------------------------:|:---------------------------:|
    |      TracIn     |        89.98 / 43.21        |        75.53 / 22.25        |        76.48 / 64.69        |        68.91 / 55.86        |
    |     TracInRP    | 89.56 ± 0.14 / 44.26 ± 0.37 | 74.99 ± 0.25 / 21.62 ± 0.26 | 77.24 ± 0.45 / 65.17 ± 0.68 | 69.04 ± 0.28 / 56.41 ± 0.31 |
    |       GEX       | 99.74 ± 0.02 / 98.31 ± 0.06 | 99.33 ± 0.03 / 96.08 ± 0.12 | 96.20 ± 0.03 / 94.89 ± 0.04 | 89.76 ± 0.01 / 86.30 ± 0.01 |
    
  * Relabeled accuracy results for different datasets
    
    | Relabeled acc. | CIFAR-10 (synthetic) | CIFAR-100 (synthetic) |  CIFAR-10-N  |  CIFAR-100-N |
    |:--------------:|:--------------------:|:---------------------:|:------------:|:------------:|
    |     TracIn     |         91.24        |         72.07         |     68.36    |     54.87    |
    |    TracInRP    |     90.82 ± 0.06     |      71.70 ± 0.15     | 68.12 ± 0.23 | 55.20 ± 0.06 |
    |       GEX      |     93.54 ± 0.05     |      75.04 ± 0.10     | 73.94 ± 0.24 | 57.13 ± 0.10 |
    
  In accordance with Figure 1 in [1], we found that neither TracIn nor TracInRP consistently outperforms the other.

  The LOO counterfactual effect requires significant computational resources due to the necessity of LOO retraining for each sample. Consequently, we report the result of the LOO counterfactual only for the toy dataset in Figures 2-3. This computational challenge has been highlighted in various papers on Influence Functions [1, 2, 3]. To the best of our knowledge, no previous work used the LOO counterfactual effect for downstream tasks in Section 5.

  [1] Pruthi, Garima, et al. "Estimating training data influence by tracing gradient descent." Advances in Neural Information Processing Systems 33 (2020): 19920-19930.

* G4. [**Modified Figure 2 (a)**] We also provide a modified Figure 2 (a) to clarify the definition of "Typical" and "Influential" in Figures 2-3.

Meta-review: This paper proposed a new algorithm for influence function approximation, aimed at addressing the issues of the previous approximations. It is demonstrated that the new algorithm outperformed previous methods on downstream tasks such as noisy label detection and dataset pruning. The analysis and formulation are convincing, and with additional results on larger datasets added during the rebuttal, the proposed method could be a promising alternative IF approximation with better performance and lighter computation.
Decision: Accept (poster)