edges nice empty nodes/.style= for tree=, delay=where
content=shape=coordinate,for siblings=anchor=north ,

# Training Data Influence Analysis
and Estimation: A Survey

Zayd Hammoudeh111Correspondence to<EMAIL_ADDRESS>University of Oregon
Daniel Lowd  University of Oregon

###### Abstract

Good models require good training data. For overparameterized deep models, the
causal relationship between training data and model predictions is
increasingly opaque and poorly understood. Influence analysis partially
demystifies training’s underlying interactions by quantifying the amount each
training instance alters the final model. Measuring the training data’s
influence exactly can be provably hard in the worst case; this has led to the
development and use of influence estimators, which only approximate the true
influence. This paper provides the first comprehensive survey of training data
influence analysis and estimation. We begin by formalizing the various, and in
places orthogonal, definitions of training data influence. We then organize
state-of-the-art influence analysis methods into a taxonomy; we describe each
of these methods in detail and compare their underlying assumptions,
asymptotic complexities, and overall strengths and weaknesses. Finally, we
propose future research directions to make influence analysis more useful in
practice as well as more theoretically and empirically sound. A curated, up-
to-date list of resources related to influence analysis is available at
https://github.com/ZaydH/influence_analysis_papers.

Keywords: Influence analysis, influence estimation, data valuation, influence
functions, TracIn, Shapley value, representer point

##  1 Introduction

Machine learning is built on training data [Red+21a]. Without good training
data, nothing else works. How modern models learn from and use training data
is increasingly opaque [KL17a, Zha+21c, Xia22a]. Regarding state-of-the-art
black-box models, [Yam20a] notes, “If all we have is a ‘black box’ it is
impossible to understand causes of failure and improve system safety.”

Large modern models require tremendous amounts of training data [BF21a].
Today’s uncurated, internet-derived datasets commonly contain numerous
anomalous instances [Ple+20a]. These anomalies can arise from multiple
potential sources. For example, training data anomalies may have a natural
cause such as distribution shift [RL87a, Yan+21a], measurement error, or non-
representative samples drawn from the tail of the data distribution [Hub81a,
Fel20a, Jia+21c]. Anomalous training instances also occur due to human or
algorithmic labeling errors – even on well-known, highly-curated datasets
[EGH17a]. Malicious adversaries can insert anomalous poison instances into the
training data with the goal of manipulating specific model predictions
[BNL12a, Che+17a, Sha+18b, HL23a]. Regardless of the cause, anomalous training
instances degrade a model’s overall generalization performance.

Today’s large datasets also generally overrepresent established and dominant
viewpoints [Ben+21a]. Models trained on these huge public datasets encode and
exhibit biases based on protected characteristics, including gender, race,
religion, and disability [BCC19a, Kur+19a, TC19a, Zha+20a, Hut+20a]. These
training data biases can translate into real-world harm, where, as an example,
a recidivism model falsely flagged black defendants as high risk at twice the
rate of white defendants [Ang+16a].

Understanding the data and its relationship to trained models is essential for
building trustworthy ML systems. However, it can be very difficult to answer
even basic questions about the relationship between training data and model
predictions; for example:

  1. 1.

Is a prediction well-supported by the training data, or was the prediction
just random?

  2. 2.

Which portions of the training data improve a prediction? Which portions make
it worse?

  3. 3.

Which instances in the training set caused the model to make a specific
prediction?

One strategy to address basic questions like those above is to render them
moot by exclusively using simple, transparent model classes [Lip18a]. Evidence
exists that this “interpretable-only” strategy may be appropriate in some
settings [Kni17a]. However, even interpretable model classes can be grossly
affected by training data issues [Hub81a, CHW82a, CW82a]. Moreover, as the
performance penalty of interpretable models grows, their continued use becomes
harder to justify.

With the growing use of black-box models, we need better methods to analyze
and understand black-box model decisions. Otherwise, society must carry the
burden of black-box failures.

###  1.1 Relating Models and Their Training Data

All model decisions are rooted in the training data. Training data influence
analysis partially demystifies the relationship between training data and
model predictions by determining how to apportion credit (and blame) for
specific model behavior to the training instances [SR88a, KL17a, Yeh+18a,
Pru+20a]. Essentially, influence analysis tries to answer the question: What
is each training instance’s effect on a model? An instance’s “effect” is with
respect to a specific perspective. For example, an instance’s effect may be
quantified as the change in model performance when some instance is deleted
from the training data. The effect can also be relative, e.g., whether one
training instance changes the model more than another.

Influence analysis emerged alongside the initial study of linear models and
regression [Jae72a, CW82a]. This early analysis focused on quantifying how
worst-case perturbations to the training data affected the final model
parameters. The insights gained from early influence analysis contributed to
the development of numerous methods that improved model robustness and reduced
model sensitivity to training outliers [Hog79a, Rou94a].

Since these early days, machine learning models have grown substantially in
complexity and opacity [Dev+19a, KSH12a, Dos+21a]. Training datasets have also
exploded in size [BF21a]. These factors combine to make training data
influence analysis significantly more challenging where, for multilayer
parametric models (e.g., neural networks), determining a single training
instance’s exact effect can be NP/̄complete in the worst case [BR92a].

In practice, influence may not need to be measured exactly. methods provide an
approximation of training instances’ true influence. Influence estimation is
generally much more computationally efficient and is now the approach of
choice [Sch+22a]. However, modern influence estimators achieve their
efficiency via various assumptions about the model’s architecture and learning
environment [KL17a, Yeh+18a, GZ19a]. These varied assumptions result in
influence estimators having different advantages and disadvantages as well as
in some cases, even orthogonal perspectives on the definition of influence
itself [Pru+20a].

###  1.2 Our Contributions

To the extent of our knowledge, there has not yet been a comprehensive review
of these differing perspectives of training data influence, much less of the
various methods themselves. This paper fills in that gap by providing the
first comprehensive survey of existing influence analysis techniques. We
describe how these various methods overlap and, more importantly, the
consequences – both positive and negative – that arise out of their
differences. We provide this broad and nuanced understanding of influence
analysis so that ML researchers and practitioners can better decide which
influence analysis method best suits their specific application objectives
[Sch+22a].

In the remainder of this paper, we first standardize the general notation used
throughout this work (Sec. 2). Section 3 reviews the various general
formulations through which training data influence is viewed. We also
categorize and summarize the properties of the seven most impactful influence
analysis methods. Sections 4 and 5 describe these foundational influence
methods in detail. For each method, we (1) formalize the associated definition
of influence and how it is measured, (2) detail the formulation’s strengths
and weaknesses, (3) enumerate any related or derivative methods, and (4)
explain the method’s time, space, and storage complexities. Section 6 reviews
various learning tasks where influence analysis has been applied. We provide
our perspective on future directions for influence analysis research in
Section 7.

##  2 General Notation

This section details our primary notation. In cases where a single influence
method requires custom nomenclature, we introduce the unique notation
alongside discussion of that method.222Supplemental Table 3 provides a
reference for all notation specific to a single influence analysis method.
Supplemental Section A provides a full nomenclature reference.

Let ${[r]}$ denote the set of integers $\\{1,\ldots,r\\}$.
${A\stackrel{{\scriptstyle m}}{{\sim}}B}$ denotes that the cardinality of set
$A$ is $m$ and that $A$ is drawn uniformly at random (u.a.r.) from set $B$.
For set $A$ (i.e., ${\lvert A\rvert=1}$), the sampling notation is simplified
to ${A\sim B}$. Let $2^{A}$ denote the of any set $A$. Set subtraction is
denoted ${A\setminus B}$. For singleton ${B=\\{b\\}}$, set subtraction is
simplified to ${A\setminus b}$.

The is denoted $\vec{0}$ with the vector’s dimension implicit from context.
${\mathbbm{1}[a]}$ is the , where ${{\mathbbm{1}[a]}=1}$ if predicate $a$ is
true and 0 otherwise.

Let ${x\in\mathcal{X}\subseteq^{d}}$ denote an arbitrary , and let
${y\in\mathcal{Y}}$ be a (e.g., label, target). ,
${\mathcal{D}\coloneqq\\{z_{i}\\}_{i=1}^{n}}$, consists of $n$ training
instances where each instance is a tuple,
${z_{i}\coloneqq(x_{i},y_{i})\in\mathcal{Z}}$ and
${\mathcal{Z}\coloneqq\mathcal{X}\times\mathcal{Y}}$. (Arbitrary) test
instances are denoted
${z_{\text{te}}\coloneqq(x_{\text{te}},y_{\text{te}})\in\mathcal{Z}}$. Note
that $y_{\text{te}}$ need not be $x_{\text{te}}$’s true dependent value;
$y_{\text{te}}$ can be any value in $\mathcal{Y}$. Throughout this work,
subscripts “$i$” and “te” entail that the corresponding symbol applies to an
arbitrary training and test instance, respectively.

${f:\mathcal{X}\rightarrow\mathcal{Y}}$ is parameterized by ${\theta\in^{p}}$,
where ${p\coloneqq\lvert\theta\rvert}$; $f$ is trained on (a subset of)
dataset $\mathcal{D}$. Most commonly, $f$ performs either classification or
regression, although more advanced model classes (e.g., generative models) are
also considered. Model performance is evaluated using a
${\ell:\mathcal{Y}\times\mathcal{Y}\rightarrow}$. Let
${{\mathcal{L}(z;\theta)}\coloneqq\ell\big{(}{f(x;\theta)},y\big{)}}$ denote
the of instance ${z=(x,y)}$ w.r.t. parameters $\theta$. By convention, a
smaller risk is better.

This work primarily focuses on overparameterized models where ${p\gg d}$. Such
models are almost exclusively trained using first-order optimization
algorithms (e.g., gradient descent), which proceed iteratively over ${T}$
iterations. Starting from ${\theta^{(0)}}$, the optimizer returns at the end
of each iteration, ${t\in{[T]}}$, updated model parameters $\theta^{(t)}$,
where $\theta^{(t)}$ is generated from previous parameters $\theta^{(t-1)}$,
loss function $\ell$, ${\mathcal{B}^{(t)}\subseteq\mathcal{D}}$,
${\eta^{(t)}>0}$, and ($L_{2}$) strength ${\lambda\geq 0}$. Training gradients
are denoted ${\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t)})}}$. The training
set’s for iteration $t$ is denoted
${H_{\theta}^{(t)}\coloneqq\frac{1}{n}\sum_{z_{i}\in\mathcal{D}}\nabla_{\theta}^{2}{\mathcal{L}(z_{i};\theta^{(t)})}}$,
with the corresponding denoted ${(H_{\theta}^{(t)})^{-1}}$. Throughout this
work, superscript “${(t)}$” entails that the corresponding symbol applies to
training iteration $t$.

Some models may be trained on data other than full training set $\mathcal{D}$,
e.g., subset ${\mathcal{D}\setminus z_{i}}$. Let ${D\subset\mathcal{D}}$
denote an alternate training set, and denote model parameters trained on $D$
as $\theta^{(t)}_{D}$. For example, ${\theta^{(T)}_{\mathcal{D}^{\setminus
i}}}$ are the final parameters for a model trained on all of $\mathcal{D}$
except training instance ${z_{i}\in\mathcal{D}}$ (note this alternate notation
for compactness). When training on all of the training data, subscript
$\mathcal{D}$ is dropped, i.e.,
${\theta^{(t)}\equiv\theta^{(t)}_{\mathcal{D}}}$.

##  3 Overview of Influence and Influence Estimation

As explained in Section 1, training data influence quantifies the “effect” of
one or more training instances. This effect’s scope can be as localized as an
individual model prediction, e.g., ${f(x_{\text{te}};\theta^{(T)})}$; the
effect’s scope can also be so broad as to encompass the entire test data
distribution.

Positive influence entails that the training instance(s) improve some quality
measure, e.g., risk ${\mathcal{L}(z_{\text{te}};\theta^{(T)})}$. Negative
influence means that the training instance(s) make the quality measure worse.
Training instances with positive influence are referred to as or . Training
instances with negative influence are called or [KL17a, Yeh+18a].

Highly expressive, overparameterized models remain functionally black boxes
[KL17a]. Understanding why a model behaves in a specific way remains a
significant challenge [BP21a], and the inclusion or removal of even a single
training instance can drastically change a trained model’s behavior [Rou94a,
BF21a]. In the worst case, quantifying one training instance’s influence may
require repeating all of training.

Since measuring influence exactly may be intractable or unnecessary, influence
estimators – which only approximate the true influence – are commonly used in
practice. As with any approximation, influence estimation requires making
trade-offs, and the various influence estimators balance these design choices
differently. This in turn leads influence estimators to make different
assumptions and rely on different mathematical formulations.

When determining which influence analysis methods to highlight in this work,
we relied on two primary criteria: (1) a method’s overall impact and (2) the
method’s degree of novelty in relation to other approaches. We also chose to
focus on influence analysis methods targeted toward parametric models since
those models generally achieve state-of-the-art results in most domains.
Nonetheless, where applicable, we also note related non-parametric influence
analysis methods.

The remainder of this section considers progressively more general definitions
of influence.

###  3.1 Pointwise Training Data Influence

is the simplest and most commonly studied definition of influence. It
quantifies how a single training instance affects a model’s prediction on a
single test instance according to some quality measure (e.g., test loss).
Formally, a pointwise influence analysis method is a function
${\mathcal{I}:\mathcal{Z}\times\mathcal{Z}\rightarrow}$ with the pointwise
influence of training instance $z_{i}$ on test instance $z_{\text{te}}$
denoted ${\mathcal{I}\left(z_{i},z_{\text{te}}\right)}$. Pointwise influence
estimates are denoted
${{\widehat{\mathcal{I}}\left(z_{i},z_{\text{te}}\right)}\in}$.

Below, we briefly review early pointwise influence analysis contributions and
then transition to a discussion of more recent pointwise methods.

####  3.1.1 Early Pointwise Influence Analysis

InlierOutlierLeast Squares Inliers OnlyLeast Squares All

$1$$2$$3$$4$$5$$1$$2$$3$$4$$x$$y$

Figure 1: Outlier Pointwise Influence on Least-Squares Regression: Influence
of a single outlier (1) on a least-squares model where in-distribution data
(1) are generated from linear distribution ${y=2x}$. The single outlier sample
(${x=5}$ & ${y=1.2}$) influences the inlier-only least-squares linear model
(1) substantially such that a least-squares model trained on all instances (1)
predicts all training $y$ values poorly. Adapted from [RL87a, Fig. 2(b) ].

The earliest notions of pointwise influence emerged out of robust statistics –
specifically the analysis of training outliers’ effects on linear regression
models [Coo77a]. Given training set $\mathcal{D}$, the least-mean squares
linear model parameters are333For simplicity, the bias term is considered part
of $\theta$.

$\theta^{*}\coloneqq\operatorname*{arg\,min}_{\theta}\frac{1}{\lvert\mathcal{D}\rvert}\sum_{(x_{i},y_{i})\in\mathcal{D}}\left(y_{i}-\theta^{\intercal}x_{i}\right)^{2}\text{.}$
(1)

Observe that this least-squares estimator has a of 0 [Rou94a]. This means that
least-squares regression is completely non-robust where a single training data
outlier can shift model parameters $\theta^{*}$ arbitrarily. For example,
Figure 1 visualizes how a single training data outlier (1) can induce a nearly
orthogonal least-squares model. Put simply, an outlier training instance’s
potential pointwise influence on a least-squares model is unbounded. Unbounded
influence on the model parameters equates to unbounded influence on model
predictions.

Early influence analysis methods sought to identify the training instance that
was most likely to be an outlier [Sri61a, TMB73a]. A training outlier can be
defined as the training instance with the largest negative influence on
prediction ${f(x_{\text{te}};\theta^{*})}$. Intuitively, each training
instance’s pointwise influence can be measured by training
${n\coloneqq\lvert\mathcal{D}\rvert}$ models, where each model’s training set
leaves out a different training instance. These $n$ models would then be
compared to identify the outlier.444Section 4.1 formalizes how to measure
pointwise influence by repeatedly retraining with a different training
instance left out of the training set each time. However, such repeated
retraining is expensive and so more efficient pointwise influence analysis
methods were studied.

Different assumptions about the training data distribution lead to different
definitions of the most likely outlier. For example, [Sri61a], [SC68a], and
[Ell76a] all assume that training data outliers arise from mean shifts in
normally distributed training data. Under this constraint, their methods all
identify the maximum likelihood outlier as the training instance with the
largest absolute , $\lvert y_{i}-{\theta^{*}}^{\intercal}x_{i}\rvert$.
However, [CW82a] prove that under different distributional assumptions (e.g.,
a variance shift instead of a mean shift), the maximum likelihood outlier may
not have the largest residual.

These early influence analysis results demonstrating least-squares fragility
spurred development of more robust regressors. For instance, [Rou94a] replaces
Eq. (1)’s mean operation with median; this simple change increases the
breakdown point of model parameters $\theta^{*}$ to the maximum value, 50%. In
addition, multiple robust loss functions have been proposed that constrain or
cap outliers’ pointwise influence [Hub64a, BT74a, JW78a, Lec89a].

As more complex models grew in prevalence, influence analysis methods
similarly grew in complexity. In recent years, numerous influence analysis
methods targeting deep models have been proposed. We briefly review the most
impactful, modern pointwise influence analysis methods next.

####  3.1.2 Modern Pointwise Influence Analysis

/tikz/every node/.append style=font=, for tree= line width=1pt, if=level()¡4
my rounded corners, draw=linecol, , if level=0forked edges, l sep+=0.35cm, s
sep+=0.35cm, align=center, if level=1l sep+=0.35cm, s sep+=8pt, parent
anchor=south, child anchor=north, align=center, for descendants= align=center,
, if level=2 l sep+=0.35cm, s sep+=8pt, if level=3 tier=parting ways, parent
anchor=south west, for descendants= child anchor=west, parent anchor=west,
anchor=west, align=left, , if level=4 shape=coordinate, no edge, grow’=0,
calign with current edge, xshift=15pt, for descendants= parent anchor=south
west, , for children= s sep-=10pt, edge path= [edge] (!to tier=parting
ways.parent anchor) —- (.child anchor)edge label; , for descendants= no edge,
, , , , , , ,, [Influence Analysis Methods [Retraining-Based [,nice empty
nodes,calign=child, calign child=2 [ Leave-One-Out [ [ $k$NN LOO ] [ LeafRefit
] [ Inf. Sketching ] ] ] [ Downsampling [ [ C/̄Score ] [ Generative ] ] ] [
Shapley Value [ [ TMC/̄Shapley ] [ G/̄Shapley ] [ $k$NN Shapley ] [ Beta
Shapley ] [ AME ] [ SHAP ] [ Neuron Shapley ] ] ] ] ] [Gradient-Based [Static
[ Influence Func. [ [ FastIF ] [ Scaled IF ] [ LeafInfluence ] [ Group IF ] [
Second-Order ] [ RelatIF ] [ Renorm. IF ] ] ] [ Representer Pt. [ [ RPS/̄LJE ]
[ TREX ] ] ] ] [Dynamic [TracIn [ [ TracInCP ] [ TracInRP ] [ TracIn/̄Last ] [
VAE/̄TracIn ] [ TracInAD ] [ TracInWE ] [ BoostIn ] [ GAS ] ] ] [HyDRA [ [
SGD/̄Influence ] ] ] ] ] ]

Figure 2: Influence Analysis Taxonomy: Categorization of the seven primary
pointwise influence analysis methods. Section 4 details the three primary
retraining-based influence methods, leave-one-out (Sec. 4.1), Downsampling
(Sec. 4.2), and Shapley value (Sec. 4.3). Section 5 details gradient-based
static estimators influence functions (Sec. 5.1.1) and representer point (Sec.
5.1.2) as well as dynamic estimators TracIn (Sec. 5.2.1) and HyDRA (Sec.
5.2.2). Closely-related and derivative estimators are shown as a list below
their parent method. See supplemental Table 4 for the formal mathematical
definition of all influence methods and estimators. Due to space, each
method’s citation is in supplemental Table 5.

Figure 2 provides a taxonomy of the seven most impactful modern pointwise
influence analysis methods. Below each method appears a list of closely
related and derivative approaches. Modern influence analysis methods broadly
categorize into two primary classes, namely:

  * •

: Measure the training data’s influence by repeatedly retraining model $f$
using different subsets of training set $\mathcal{D}$.

  * •

: Estimate influence via the alignment of training and test instance gradients
either throughout or at the end of training.

An in-depth comparison of these influence analysis methods requires detailed
analysis so we defer the extensive discussion of these two categories to
Sections 4 and 5, respectively. Table LABEL:tab:InfluenceEstimators:Comparison
summarizes the key properties of Figure 2’s seven methods – including
comparing each method’s assumptions (if any), strengths/weaknesses, and
asymptotic complexities. These three criteria are also discussed when
detailing each of these methods in the later sections.

###  3.2 Alternative Perspectives on Influence and Related Concepts

Note that pointwise effects are only one perspective on how to analyze the
training data’s influence. Below we briefly summarize six alternate, albeit
less common, perspectives of training data influence. While pointwise
influence is this work’s primary focus, later sections also contextualize
existing influence methods w.r.t. these alternate perspectives where
applicable.

(1) Recall that pointwise influence quantifies the effect of a single training
instance on a single test prediction. In reality, multiple related training
instances generally influence a prediction as a group [FZ20a], where group
members have a total effect much larger than the sum of their individual
effects [BYF20a, Das+21a, HL22a]. quantifies a set of training instances’
total, combined influence on a specific test prediction.

We use very similar notation to denote group and pointwise influence. The only
difference is that for group influence, the first parameter of function
$\mathcal{I}$ is a training (sub)set instead of an individual training
instance; the same applies to group influence estimates
$\widehat{\mathcal{I}}$. For example, given some test instance
$z_{\text{te}}$, the entire training set’s group influence and group influence
estimate are denoted ${\mathcal{I}\left(\mathcal{D},z_{\text{te}}\right)}$ and
${\widehat{\mathcal{I}}\left(\mathcal{D},z_{\text{te}}\right)}$, respectively.

In terms of magnitude, previous work has shown that the group influence of a
related set of training instances is generally lowered bounded by the sum of
the set’s pointwise influences [Koh+19a]. Put simply, the true influence of a
coherent group is more than the sum of its parts, or formally, for coherent
${D\subseteq\mathcal{D}}$, it often holds that

$\lvert{\mathcal{I}\left(D,z_{\text{te}}\right)}\rvert>\sum_{z_{i}\in
D}\lvert{\mathcal{I}\left(z_{i},z_{\text{te}}\right)}\rvert\text{.}$ (2)

Existing work studying group influence is limited. Later sections note
examples where any of the seven primary pointwise influence methods have been
extended to consider group effects.

(2) extends influence to consider multiple test instances collectively
[Jia+22a, Che+22a]. These test instances may be a specific subpopulation
within the test distribution – for example in [Jag+21a, Wal+21a]. The test
instances could also be a representative subset of the entire test data
distribution – for example in [BMK20a] or [BNL12a, Fow+21a].

Most (pointwise) influence analysis methods are meaning for target set
${\mathcal{D}_{\text{te}}\subseteq\mathcal{Z}}$, the joint (pointwise)
influence simplifies to

${\mathcal{I}\left(z_{i},\mathcal{D}_{\text{te}}\right)}=\sum_{z_{\text{te}}\in\mathcal{D}_{\text{te}}}{\mathcal{I}\left(z_{i},z_{\text{te}}\right)}\text{.}$
(3)

Additivity is not a requirement of influence analysis, and there are provably
non-additive influence estimators [YP21a].

(3) Overparameterized models like deep networks are capable of achieving near-
zero training loss in most settings [Bar+20a, Fel20a, DAm+20a]. This holds
even if the training set is large and randomly labeled [Zha+17a, Arp+17a].
Near-zero training loss occurs because deep models often memorize some
training instances.

Both [Pru+20a] and [FZ20a] separately define a model’s 555[Pru+20a] term
“memorization” as . We use [FZ20a]’s [FZ20a] terminology here since it is more
consistent with other work [vW21a, KWR22a]. of training instance $z_{i}$ as
the pointwise influence of $z_{i}$ on itself. Formally

${\textsc{Mem}(z_{i})}\coloneqq{\mathcal{I}\left(z_{i},z_{i}\right)}\approx{\widehat{\mathcal{I}}\left(z_{i},z_{i}\right)}\text{.}$
(4)

(4) measures the effect of training instances on the model parameters
themselves [Coo77a, Eq. (5)]. Formally, the pointwise Cook’s distance of
${z_{i}\in\mathcal{D}}$ is

${\mathcal{I}_{\text{Cook}}\mathopen{}\left(z_{i}\right)\mathclose{}}\coloneqq\theta^{(T)}-{\theta^{(T)}_{\mathcal{D}^{\setminus
i}}}\text{.}$ (5)

Eq. (5) trivially extends to groups of training instances where for any
${D\subseteq\mathcal{D}}$

${\mathcal{I}_{\text{Cook}}\mathopen{}\left(D\right)\mathclose{}}\coloneqq\theta^{(T)}-\theta^{(T)}_{\mathcal{D}\setminus
D}\text{.}$ (6)

Cook’s distance is particularly relevant for interpretable model classes where
feature weights are most transparent. This includes linear regression [RL87a,
Woj+16a] and decision trees [BHL22a].

(5) All definitions of influence above consider training instances’ effects
w.r.t. a single instantiation of a model. Across repeated stochastic
retrainings, a training instance’s influence may vary – potentially
substantially [BPF21a]. is the average influence across all possible
instantiations within a given model class [KS21a]. Expected influence is
particularly useful in domains where the random component of training is
unknowable a priori. For example, with poisoning and backdoor attacks, an
adversary crafts malicious training instances to be highly influential in
expectation across all random parameter initializations and batch orderings
[Che+17a, Sha+18b, Fow+21a].

(6) Observe that all preceding definitions view influence as a specific
numerical value to measure/estimate. Influence analysis often simplifies to a
relative question of whether one training instance is more influential than
another. An orders (groups of) training instances from most positively
influential to most negatively influential. These rankings are useful in a
wide range of applications [KZ22a], including data cleaning and poisoning
attack defenses as discussed in Section 6.

With this broad perspective on influence analysis in mind, we transition to
focusing on specific influence analysis methods in the next two sections.

##  4 Retraining-Based Influence Analysis

Training instances can only influence a model if they are used during
training. As Section 3.1.2 describes in the context of linear regression, one
method to measure influence just trains a model with and without some
instance; influence is then defined as the difference in these two models’
behavior. This basic intuition is the foundation of retraining-based influence
analysis, and this simple formulation can be applied to any model class –
parametric or non/̄parametric.

Observe that the retraining-based framework makes no assumptions about the
learning environment. In fact, this simplicity is one of the primary
advantages of retraining-based influence. For comparison, Table
LABEL:tab:InfluenceEstimators:Comparison shows that all gradient-based
influence estimators make strong assumptions – some of which are known not to
hold for deep models (e.g., convexity). However, retraining’s flexibility
comes at the expense of high (sometimes prohibitive) computational cost.

Below, we describe three progressively more complex retraining-based influence
analysis methods. Each method mitigates weaknesses of the preceding method –
in particular, devising techniques to make retraining-based influence more
viable computationally.

######  Remark 1:

This section treats model training as where, given a fixed training set,
training always yields the same output model. Since the training of modern
models is mostly stochastic, retraining-based estimators should be represented
as expectations over different random initializations and batch orderings.
Therefore, (re)training should be repeated multiple times for each relevant
training (sub)set with a probabilistic average taken over the valuation metric
[Lin+22a]. For simplicity of presentation, expectation over randomness is
dropped from the influence and influence estimator definitions below.

######  Remark 2:

Section 2 defines $\mathcal{D}$ as a supervised training set. The three
primary retraining-based influence analysis methods detailed below also
generalize to unsupervised and semi-supervised training.

######  Remark 3:

When calculating retraining’s time complexity below, each training iteration’s
time complexity is treated as a constant cost. This makes the time complexity
of training a single model ${\mathcal{O}(T)}$. Depending on the model
architecture and hyperparameter settings, a training iteration’s complexity
may directly depend on training-set size $n$ or model parameter count $p$.

######  Remark 4:

It may be possible to avoid full model retraining by using machine unlearning
methods capable of certifiably “forgetting” training instances [Guo+20a,
BL21a, Ngu+22a, Eis+22a]. The asymptotic complexity of such methods is model-
class specific and beyond the scope of this work. Nonetheless, certified
deletion methods can drastically reduce the overhead of retraining-based
influence analysis.

###  4.1 Leave-One-Out Influence

(LOO) is the simplest influence measure described in this work. LOO is also
the oldest, dating back to [CW82a] who term it .

As its name indicates, is the change in $z_{\text{te}}$’s risk due to the
removal of a single instance, $z_{i}$, from the training set [KL17a, BF21a,
Jia+21b]. Formally,

${\mathcal{I}_{\textsc{LOO}}\left(z_{i},z_{\text{te}}\right)}\coloneqq{\mathcal{L}(z_{\text{te}};{\theta^{(T)}_{\mathcal{D}^{\setminus
i}}})}-{\mathcal{L}(z_{\text{te}};\theta^{(T)})}\text{,}$ (7)

where ${\theta^{(T)}_{\mathcal{D}^{\setminus i}}}$ are the final model
parameters when training on subset ${\mathcal{D}\setminus z_{i}}$ and
$\theta^{(T)}$ are the final model parameters trained on all of $\mathcal{D}$.

Measuring the entire training set’s LOO influence requires training ${(n+1)}$
models. Given a deterministic model class and training algorithm (e.g., convex
model optimization [BV04a]), LOO is one of the few influence measures that can
be computed exactly in polynomial time w.r.t. training-set size $n$ and
iteration count $T$.

####  4.1.1 Time, Space, and Storage Complexity

Training a single model has time complexity ${\mathcal{O}(T)}$ (see Remark 3).
By additivity, training ${(n+1)}$ models has total time complexity
${\mathcal{O}(nT)}$. Since these ${(n+1)}$ models are independent, they can be
trained in parallel.

Pointwise influence analysis always has space complexity of at least
${\mathcal{O}(n)}$, i.e., the space taken by the $n$ influence values
${\forall_{i}\,{\mathcal{I}\left(z_{i},z_{\text{te}}\right)}}$. Training a
single model has space complexity ${\mathcal{O}(p)}$, where
${p\coloneqq\lvert\theta\rvert}$; this complexity scales linearly with the
number of models trained in parallel. Table
LABEL:tab:InfluenceEstimators:Comparison treats the level of training
concurrency as a constant factor, which is why LOO’s total space complexity is
listed as ${\mathcal{O}(n+p)}$.

A naive implementation of LOO would train the $n$ additional models and
immediately discard them after measuring $z_{\text{te}}$’s test loss. This
simple version of LOO has ${\mathcal{O}(1)}$ storage complexity. If instead
the ${(n+1)}$ models are stored, analysis of subsequent test instances
requires no additional retraining. This drastically reduces LOO’s incremental
time complexity for subsequent instances to just ${\mathcal{O}(n)}$ forward
passes – a huge saving.666LOO’s incremental computational cost can be
(significantly) reduced in practice via batching. Note that this amortization
of the retraining cost induces an ${\mathcal{O}(np)}$ storage complexity as
listed in Table LABEL:tab:InfluenceEstimators:Comparison.

####  4.1.2 Strengths and Weaknesses

Leave-one-out influence’s biggest strength is its simplicity. LOO is human-
intelligible – even by laypersons. For that reason, LOO has been applied to
ensure the fairness of algorithmic decisions [BF21a].

LOO’s theoretical simplicity comes at the price of huge upfront computational
cost. Training some state-of-the-art models from scratch even once is
prohibitive for anyone beyond industrial actors [Dis+21a]. For even the
biggest players, it is impractical to train ${(n+1)}$ such models given huge
modern datasets [BPF21a]. The climate effects of such retraining also cannot
be ignored [SGM20a].

LOO’s simple definition in Eq. (7) is premised on deterministic training.
However, even when training on the same data, modern models may have
significant predictive variance for a given test instance [BF21a]. This
variance makes it difficult to disentangle the effect of an instance’s
deletion from training’s intrinsic variability [BPF21a]. For a single training
instance, estimating the LOO influence within a standard deviation of $\sigma$
requires training ${\Omega(1/\sigma^{2})}$ models. Therefore, estimating the
entire training set’s LOO influence requires training ${\Omega(n/\sigma^{2})}$
models – further exacerbating LOO’s computational infeasibility [FZ20a].

These limitations notwithstanding, LOO’s impact on influence analysis research
is substantial. Many pointwise influence analysis methods either directly
estimate the leave-one-out influence – e.g., Downsampling (Sec. 4.2),
influence functions (Sec. 5.1.1), HyDRA (Sec. 5.2.2) – or are very similar to
LOO – e.g., Shapley value (Sec. 4.3).

####  4.1.3 Related Methods

Although LOO has poor upfront and storage complexities in general, it can be
quite efficient for some model classes – particularly instance-based learners
[AKA91a]. For example, [Jia+21b] propose the ($k$NN LOO) estimator, which
calculates the LOO influence over a surrogate $k$/̄nearest neighbors
classifier instead of over target model $f$. $k$NN LOO relies on a simple two-
step process. First, the features of test instance $z_{\text{te}}$ and
training set $\mathcal{D}$ are extracted using a pretrained model. Next, a
$k$NN classifier’s LOO influence is calculated exactly [Jia+21b, Lemma 1]
using these extracted features. [Jia+21b] prove that $k$NN LOO influence only
requires ${\mathcal{O}(n\log n)}$ time – significantly faster in practice than
vanilla LOO’s ${\mathcal{O}(nT)}$ complexity. [Jia+21b] also demonstrate
empirically that $k$NN LOO and vanilla LOO generate similar influence rankings
across various learning domains and tasks.

In addition, [Sha+18c] propose LeafRefit, an efficient LOO estimator for
decision-tree ensembles. LeafRefit’s efficiency derives from the simplifying
assumption that instance deletions do not affect the trees’ structure. In
cases where this assumption holds, LeafRefit’s tree influence estimates are
exact. To the extent of our knowledge, LeafRefit’s suitability for surrogate
influence analysis of deep models has not yet been explored.

Furthermore, for least-squares linear regression, [Woj+16a] show that each
training instance’s LOO influence on the model parameters (i.e., Cook’s
distance) can be efficiently estimated by mapping training set $\mathcal{D}$
into a lower-dimensional subspace. By the Johnson/̄Lindenstrauss lemma
[JL84a], these influence sketches approximately preserve the pairwise
distances between the training instances in $\mathcal{D}$ provided the
projected dimension is on the order of ${\log n}$.

To measure group influence, leave/̄one/̄out can be extended to for any integer
${m\leq n}$. Leave/̄$m$/̄out777Leave/̄$m$/̄out influence analysis is also
called [RL87a].  has time complexity ${\mathcal{O}(\binom{n}{m})}$, which is
exponential in the worst case. Shapley value influence [Sha53a] (Sec. 4.3)
shares significant similarity with leave/̄$m$/̄out.

As mentioned above, LOO influence serves as the reference influence value for
multiple influence estimators including Downsampling, which we describe next.

###  4.2 Downsampling

Proposed by [FZ20a], Downsampling888[FZ20a] do not specify a name for their
influence estimator. Previous work has referred to [FZ20a]’s method as
“subsampling” [BHL22a] and as “counterfactual influence” [Zha+21d]. We use
“Downsampling” to differentiate [FZ20a]’s method from the existing, distinct
task of dataset subsampling [TB18a] while still emphasizing the methods’
reliance on repeated training-set sampling. mitigates leave-one-out
influence’s two primary weaknesses: (1) computational complexity dependent on
$n$ and (2) instability due to stochastic training variation.

Downsampling relies on an ensemble of $K$ submodels each trained on a u.a.r.
subset of full training set $\mathcal{D}$. Let
${D^{k}\,\stackrel{{\scriptstyle m}}{{\sim}}\,\mathcal{D}}$ be the $k$/̄th
submodel’s training set where ${\forall_{k}\,\lvert
D^{k}\rvert=m<n}$.999[FZ20a] propose setting ${m=\lceil 0.7n\rceil}$. Define
${K_{i}\coloneqq\sum_{k=1}^{K}{\mathbbm{1}[z_{i}\in D^{k}]}}$ as the number of
submodels that used instance $z_{i}$ during training. The 101010[FZ20a] define
their estimator specifically for classification. Downsampling’s definition in
Eq. (8) uses a more general form to cover additional learning tasks such as
regression. [FZ20a]’s original formulation would be equivalent to defining the
risk as
${{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D^{k}})}={\mathbbm{1}\big{[}y_{\text{te}}\neq{f(x_{\text{te}};\theta^{(T)}_{D^{k}})}\big{]}}}$,
i.e., the accuracy subtracted from one. is then

${\widehat{\mathcal{I}}_{\textsc{Down}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\frac{1}{K-K_{i}}\sum_{\begin{subarray}{c}k\\\
z_{i}\notin
D^{k}\end{subarray}}{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D^{k}})}-\frac{1}{K_{i}}\sum_{\begin{subarray}{c}k^{\prime}\\\
z_{i}\in
D^{k^{\prime}}\end{subarray}}{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D^{k^{\prime}}})}\text{.}$
(8)

Intuitively, Eq. (8) is the change in $z_{\text{te}}$’s average risk when
$z_{i}$ is not used in submodel training. By holding out multiple instances
simultaneously and then averaging, each Downsampling submodel provides insight
into the influence of all training instances. This allows Downsampling to
require (far) fewer retrainings than LOO.

Since each of the $K$ training subsets is i.i.d., then

$\lim_{K\rightarrow\infty}{\widehat{\mathcal{I}}_{\textsc{Down}}\left(z_{i},z_{\text{te}}\right)}=\mathbb{E}_{D^{\prime}\,\stackrel{{\scriptstyle
m}}{{\sim}}\,\mathcal{D}^{\setminus
z_{i}}}[{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D^{\prime}})}]-\mathbb{E}_{D\,\stackrel{{\scriptstyle
m-1}}{{\sim}}\,\mathcal{D}^{\setminus
z_{i}}}[{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D\cup z_{i}})}]\text{.}$ (9)

For sufficiently large $m$ and $n$, the expected behavior of a model trained
on an i.i.d. dataset of size $m$ becomes indistinguishable from one trained on
${m-1}$ i.i.d. instances. Applying this property along with linearity of
expectation and Eq. (7), Eq. (9) reformulates as

$\displaystyle\lim_{K,n,m\rightarrow\infty}{\widehat{\mathcal{I}}_{\textsc{Down}}\left(z_{i},z_{\text{te}}\right)}$
$\displaystyle=\mathbb{E}_{D^{\prime}\,\stackrel{{\scriptstyle
m-1}}{{\sim}}\,\mathcal{D}^{\setminus
z_{i}}}[{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D^{\prime}})}]-\mathbb{E}_{D\,\stackrel{{\scriptstyle
m-1}}{{\sim}}\,\mathcal{D}^{\setminus
z_{i}}}[{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D\cup z_{i}})}]$ (10)
$\displaystyle=\mathbb{E}_{D\,\stackrel{{\scriptstyle
m-1}}{{\sim}}\,\mathcal{D}^{\setminus
z_{i}}}[{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D})}-{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D\cup
z_{i}})}]$ (11) $\displaystyle=\mathbb{E}_{D\,\stackrel{{\scriptstyle
m-1}}{{\sim}}\,\mathcal{D}^{\setminus
z_{i}}}[{\mathcal{I}_{\textsc{LOO}}\left(z_{i},z_{\text{te}}\right)}\vphantom{\bigg{[}}]\text{.}$
(12)

Hence, Downsampling is a statistically estimator of the . This means that
Downsampling does not estimate the influence of training instance $z_{i}$ on a
single model instantiation. Rather, Downsampling estimates $z_{i}$’s
_influence on the training algorithm and model architecture as a whole_. By
considering influence in expectation, Downsampling addresses LOO’s inaccuracy
caused by stochastic training’s implicit variance.

In practice, $K$, $n$, and $m$ are finite. Nonetheless, [FZ20a, Lemma 2.1 ]
prove that, with high probability, Downsampling’s LOO influence estimation
error is bounded given $K$ and $\frac{m}{n}$.

######  Remark 5:

Downsampling trains models on data subsets of size $m$ under the assumption
that statements made about those models generalize to models trained on a
dataset of size $n$ (i.e., all of $\mathcal{D}$). This assumption may not hold
for small $m$. To increase the likelihood this assumption holds, [FZ20a]
propose fixing ${\frac{m}{n}=0.7}$. This choice balances satisfying the
aforementioned assumption against the number of submodels Downsampling
requires since $K$ and ratio $\frac{m}{n}$ combined dictate $K_{i}$, the
number of submodels that are trained on $z_{i}$.

####  4.2.1 Time, Space, and Storage Complexity

Downsampling’s complexity analysis is identical to that of LOO (Sec. 4.1.1)
except, instead of the time and storage complexities being dependent on
training-set size $n$, Downsampling depends on submodel count $K$. For
perspective, [FZ20a]’s empirical evaluation used ${K=2,000}$ for ImageNet
[Den+09a] (${n>14\text{M}}$) as well as ${K=4,000}$ for MNIST [LeC+98a]
(${n=60,000}$) and CIFAR10 [KNH14a] (${n=50,000}$) – a savings of one to four
orders of magnitude over vanilla LOO.

######  Remark 6:

Downsampling’s incremental time complexity is technically
${{\mathcal{O}(K+n)}\in{\mathcal{O}(n)}}$ since pointwise influence is
calculated w.r.t. each training instance. The time complexity analysis above
focuses on the difference in the number of forward passes required by LOO and
Downsampling; fewer forward passes translate to Downsampling being much faster
than LOO in practice.

####  4.2.2 Strengths and Weaknesses

Although more complicated than LOO, Downsampling is still comparatively simple
to understand and implement. Downsampling makes only a single assumption that
should generally hold in practice (see Remark 5). Downsampling is also
flexible and can be applied to most applications.

While Downsampling’s formulation above is w.r.t. a single training instance,
Downsampling trivially extends to estimate the of multiple training instances.
Observe however that the expected fraction of u.a.r. training subsets that
either contains all instances in a group or none of a group decays
geometrically with ${\frac{m}{n}}$ and ${(1-\frac{m}{n})}$, respectively.
Therefore, for large group sizes, $K$ needs to be exponential in $n$ to cover
all group combinations.

Another strength of Downsampling is its low incremental time complexity. Each
test example requires only $K$ forward passes. These forward passes can use
large batch sizes to further reduce the per-instance cost. This low
incremental cost allows Downsampling to be applied at much larger scales than
other methods. For example, [FZ20a] measure all pointwise influence estimates
for the entire ImageNet dataset [Den+09a] (${n>14\text{M}}$). These large-
scale experiments enabled [FZ20a] to draw novel conclusions about neural
training dynamics – including that training instance memorization (4) by
overparameterized models is not a bug, but a feature, that is currently
necessary to achieve state-of-the-art generalization results.

In terms of weaknesses, while Downsampling is less computationally expensive
than LOO, Downsampling still has a high upfront computational cost. Training
multiple models may be prohibitively expensive even when ${K\ll n}$.
Amortization of this upfront training overhead across multiple test instances
is beneficial but by no means a panacea.

####  4.2.3 Related Methods

Downsampling has two primary related methods.

First, training instance memorization also occurs in generative models where
the generated outputs are (nearly) identical copies of training instances
[KWR22a]. [vW21a] extend Downsampling to deep generative models –
specifically, density models (e.g., variational autoencoders [KW14a, RMW14a])
that estimate posterior probability ${p(x|\mathcal{P},\theta)}$, where
$\mathcal{P}$ denotes the training data distribution. Like Downsampling,
[vW21a]’s approach relies on training multiple submodels.111111Rather than
training submodels using i.i.d. subsets of $\mathcal{D}$, [vW21a] propose
training the submodels via repeated $d$/̄fold cross-validation. While
technically different, [vW21a]’s approach is functionally equivalent to
[FZ20a]’s [FZ20a] u.a.r. sampling procedure. The primary difference is that
[vW21a] consider generative risk

${\mathcal{L}(x_{\text{te}};\theta^{(T)})}=-\log
p(x_{\text{te}}|\mathcal{P},\theta^{(T)})\text{.}$ (13)

Beyond that, [vW21a]’s method is the same as Downsampling as both methods
consider the LOO influence (8).

Downsampling’s second closely related method is [Jia+21c]’s [Jia+21c] ,
defined formally as121212[Jia+21c] define their estimator specifically for
classification. We present their method more generally to apply to other
losses/domains (e.g., regression). As with Downsampling, it is trivial to map
between Eq. (14)’s formulation and that of [Jia+21c]

${C_{m,\mathcal{D}}(z_{\text{te}})}\coloneqq-\mathbb{E}_{D\,\stackrel{{\scriptstyle
m}}{{\sim}}\,\mathcal{D}}[{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D})}]\text{.}$
(14)

By negating the risk in Eq. (14), a higher expected risk corresponds to a
lower consistency profile. Consistency profile differs from Downsampling in
two ways. (1) Downsampling implicitly considers a single submodel training-set
size $m$ while consistency profile disentangles the estimator from $m$. (2)
Downsampling estimates $z_{i}$’s influence on $z_{\text{te}}$ while
consistency profile considers all of $\mathcal{D}$ as a group and estimates
the expected group influence of a random subset ${D\subseteq\mathcal{D}}$
given ${m\coloneqq\lvert D\rvert}$.

[Jia+21c] also propose the (C/̄score), defined formally as

${C_{\mathcal{D}}(z_{\text{te}})}\coloneqq\mathbb{E}_{m\,\sim\,{[n]}}[{C_{m,\mathcal{D}}(z_{\text{te}})}]\text{,}$
(15)

where $m$ is drawn uniformly from set ${[n]}$. By taking the expectation over
all training-set sizes, C/̄score provides a total ordering over all test
instances. A large C/̄score entails that $z_{\text{te}}$ is harder for the
model to confidently predict. Large C/̄scores generally correspond to
rare/atypical test instances from the tails of the data distribution. Since
Downsampling considers the effect of each training instance individually,
Downsampling may be unable to identify these hard/̄to/̄predict test instances
– in particular if $m$ is large enough to cover most data distribution modes.

The next section introduces the Shapley value, which in essence merges the
ideas of Downsampling and C/̄score.

###  4.3 Shapley Value

Derived from cooperative game theory, (SV) quantifies the increase in value
when a group of players cooperates to achieve some shared objective [Sha53a,
SR88a]. Given $n$ total players, ${\nu:2^{{[n]}}\rightarrow}$ defines the
value of any player coalition ${A\subseteq{[n]}}$ [Dub75a]. By convention, a
larger ${\nu(A)}$ is better. Formally, player $i$’s Shapley value w.r.t. $\nu$
is

${\mathcal{V}(i;\nu)}\coloneqq\sum_{A\subseteq{[n]}\setminus
i}\frac{{\nu(A\cup i)}-{\nu(A)}}{\binom{n-1}{\lvert A\rvert}}\text{,}$ (16)

where $\binom{n-1}{\lvert A\rvert}$ is the binomial coefficient.

[GZ19a] adapt SV to model training by treating the $n$ instances in training
set $\mathcal{D}$ as $n$ cooperative players with the shared objective of
training the “best” model.131313“Best” here is w.r.t. some data valuation
measure of interest, with different use cases potentially defining “best”
differently. For any ${A\subseteq\mathcal{D}}$, let
${{\nu(A)}\coloneqq-{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{A})}}$ where the
negation is needed because more “valuable” training subsets have lower risk.
Then, $z_{i}$’s on $z_{\text{te}}$ is

${\mathcal{I}_{\text{SV}}\left(z_{i},z_{\text{te}}\right)}\coloneqq
c\sum_{D\subseteq\mathcal{D}^{\setminus
z_{i}}}\frac{{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D})}-{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D\cup
z_{i}})}}{\binom{n-1}{\lvert D\rvert}}\text{,}$ (17)

where $c$ is a constant, multiplicative scaling factor. More intuitively, SV
is the weighted change in $z_{\text{te}}$’s risk when $z_{i}$ is added to a
random training subset; the weighting ensures all training subset sizes
($\lvert D\rvert$) are prioritized equally. Eq. (17) can be viewed as
generalizing the leave/̄one/̄out influence, where rather than considering only
full training set $\mathcal{D}$, Shapley value averages the LOO influence
across all possible subsets of $\mathcal{D}$.

While Eq. (17) only considers the influence of a single training instance,
both [Sha53a] and [GZ19a] discuss extending Shapley value to larger
coalitions/groups. Formally, the of any subset ${A\subseteq\mathcal{D}}$ is

${\mathcal{I}_{\text{SV}}\left(A,z_{\text{te}}\right)}\coloneqq
c\sum_{D\subseteq\mathcal{D}\setminus
A}\frac{{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D})}-{\mathcal{L}(z_{\text{te}};\theta^{(T)}_{D\cup
A})}}{\binom{n-\lvert A\rvert}{\lvert D\rvert}}\text{.}$ (18)

####  4.3.1 Time, Space, and Storage Complexity

[DP94a] prove that computing Shapley values is #P/̄complete. Therefore, in the
worst case, SV requires exponential time to determine exactly assuming
${\text{P}\neq\text{NP}}$. There has been significant follow-on work to
develop tractable SV estimators, many of which are reviewed in Sec. 4.3.3.

The analysis of SV’s space, storage, and incremental time complexities follows
that of LOO (Sec. 4.1.1) with the exception that SV requires up to $2^{n}$
models, not just $n$ models as with LOO.

####  4.3.2 Strengths and Weaknesses

Among all influence analysis methods, SV may have the strongest theoretical
foundation with the chain of research extending back several decades. SV’s
dynamics and limitations are well understood, providing confidence in the
method’s quality and reliability. In addition, SV makes minimal assumptions
about the nature of the cooperative game (i.e., model to be trained), meaning
SV is very flexible. This simplicity and flexibility allow SV to be applied to
many domains beyond dataset influence as discussed in the next section.

SV is provably a linear operation [Sha53a, Dub75a]. Given any two data
valuation metrics $\nu^{\prime}$ and $\nu^{\prime\prime}$, it holds that

${\mathcal{V}(D;\nu^{\prime}+\nu^{\prime\prime})}={\mathcal{V}(D;\nu^{\prime})}+{\mathcal{V}(D;\nu^{\prime\prime})}\text{.}$
(19)

SV’s additivity property makes it possible to estimate both pointwise and
joint SV influences without repeating any data collection [GZ19a].

Furthermore, by evaluating training sets of different sizes, SV can detect
subtle influence behavior that is missed by methods like Downsampling and LOO,
which evaluate a single training-set size. [Lin+22a] demonstrate this
phenomenon empirically by showing that some backdoor training instances are
best detected with small SV training subsets.

Concerning weaknesses, SV’s computational intractability is catastrophic for
non-trivial dataset sizes [KZ22a]. For that reason, numerous (heuristic) SV
speed-ups have been proposed, with the most prominent ones detailed next.

####  4.3.3 Related Methods

[GZ19a] propose two SV estimators. First, (TMC/̄Shapley) relies on randomized
subset sampling from training set $\mathcal{D}$.141414The term “truncated” in
TMC/̄Shapley refers to a speed-up heuristic used when estimating the pointwise
influences of multiple training instances at the same time. Truncation is not
a necessary component of the method and is not described here. As a simplified
description of the algorithm, TMC/̄Shapley relies on random permutations of
$\mathcal{D}$; for simplicity, denote the permutation ordering
${z_{1},\ldots,z_{n}}$. For each permutation, $n$ models are trained where the
$i$/̄th model’s training set is instances $\\{z_{1},\ldots,z_{i}\\}$. To
measure each $z_{i}$’s marginal contribution for a given permutation,
TMC/̄Shapley compares the performance of the ${(i-1)}$/̄th and $i$/̄th models,
i.e., the models trained on datasets $\\{z_{1},\ldots,z_{i-1}\\}$ and
$\\{z_{1},\ldots,z_{i}\\}$, respectively. TMC/̄Shapley generates additional
training-set permutations and trains new models until the SV estimates
converge. [GZ19a] state that TMC/̄Shapley convergence usually requires
analyzing on the order of $n$ training-set permutations. Given training each
model has time complexity ${\mathcal{O}(T)}$ (Remark 3), TMC/̄Shapley’s full
time complexity is in general ${\mathcal{O}(n^{2}T)}$.

TMC/̄Shapley may be feasible for simple models that are fast to train. For
more complex systems, ${\mathcal{O}(n^{2})}$ complete retrainings are
impractical. [GZ19a] also propose (G/̄Shapley), an even faster SV estimator
which follows the same basic procedure as TMC/̄Shapley with one critical
change. Rather than taking $T$ iterations to train each model, G/̄Shapley
assumes models are trained in just one gradient step. This means that
G/̄Shapley’s full and incremental time complexity is only
${\mathcal{O}(n^{2})}$ – a substantial speed-up over TMC/̄Shapley’s full
${\mathcal{O}(n^{2}T)}$ complexity.151515G/̄Shapley and TMC/̄Shapley have the
same incremental time complexity – ${\mathcal{O}(n^{2})}$. Both estimators’
storage complexity is ${\mathcal{O}(n^{2}p)}$. There is no free lunch, and
G/̄Shapley’s speed-up is usually at the expense of lower influence estimation
accuracy.

Since TMC/̄Shapley and G/̄Shapley rely on heuristics and assumptions to
achieve tractability, neither method provides approximation guarantees. In
contrast, [Jia+19b] prove that for $k$/̄nearest neighbors classification, SV
pointwise influence can be calculated exactly in ${\mathcal{O}(n\lg n)}$ time.
Formally, SV’s characteristic function for $k$NN classification is

$\nu_{k\text{NN}}(D)\coloneqq-\frac{1}{k}\sum_{y_{i}\in{\text{Neigh}(x_{\text{te}};D)}}{\mathbbm{1}[y_{i}=y_{\text{te}}]}\text{,}$
(20)

where ${\text{Neigh}(x_{\text{te}};D)}$ is the set of $k$ neighbors in $D$
nearest to $x_{\text{te}}$ and ${\mathbbm{1}[\cdot]}$ is the indicator
function. Each training instance either has no effect on Eq. (20)’s value
(${z_{i}\notin{\text{Neigh}(x_{\text{te}};D)}}$ or ${y_{i}\neq
y_{\text{te}}}$). Otherwise, the training instance increases the value by one
(${z_{i}\in{\text{Neigh}(x_{\text{te}};D)}}$ and ${y_{i}=y_{\text{te}}}$).

Assuming the training instances are sorted by increasing distance from
$x_{\text{te}}$ (i.e., $x_{1}$ is closest to $x_{\text{te}}$ and $x_{n}$ is
furthest), then $z_{i}$’s pointwise is

${\mathcal{I}_{k\text{NN-
SV}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\frac{{\mathbbm{1}[y_{n}=y_{\text{te}}]}}{n}+\sum_{j=i}^{n-1}\frac{{\mathbbm{1}[y_{j}=y_{\text{te}}]}-{\mathbbm{1}[y_{j+1}=y_{\text{te}}]}}{k}\frac{\min\\{k,j\\}}{j}\text{.}$
(21)

Observe that $\mathcal{I}_{k\text{NN-SV}}$’s closed form is linear in $n$ and
requires no retraining at all. In fact, $k$NN Shapley’s most computationally
expensive component is sorting the training instances by distance from
$x_{\text{te}}$. Similar to $k$NN LOO above, [Jia+19b] propose using $k$NN
Shapley as a surrogate SV estimator for more complex model classes. For
example, $k$NN Shapley could be applied to the feature representations
generated by a deep neural network.

Recent work has also questioned the optimality of SV assigning uniform weight
to each training subset size (see Eq. (16)). Counterintuitively, [KZ22a] show
theoretically and empirically that influence estimates on larger training
subsets are more affected by training noise than influence estimates on
smaller subsets. As such, rather than assigning all data subset sizes ($\lvert
D\rvert$) uniform weight, [KZ22a] argue that smaller training subsets should
be prioritized. Specifically, [KZ22a] propose , which modifies vanilla SV by
weighting the training-set sizes according to a positive skew (i.e., left-
leaning) beta distribution.

SV has also been applied to study other types of influence beyond training set
membership. For example, applies SV to identify the model neurons that are
most critical for a given prediction [GZ20a]. [LL17a]’s [LL17a] SHAP is a very
well-known tool that applies SV to measure feature importance. For a
comprehensive survey of Shapley value applications beyond training data
influence, see the work of [SN20a] and a more recent update by [Roz+22a].

##  5 Gradient-Based Influence Estimation

For modern models, retraining even a few times to tune hyperparameters is very
expensive. In such cases, it is prohibitive to retrain an entire model just to
gain insight into a single training instance’s influence.

For models trained using gradient descent, training instances only influence a
model through training gradients. Intuitively then, training data influence
should be measurable when the right training gradients are analyzed. This
basic idea forms the basis of gradient-based influence estimation. As detailed
below, gradient-based influence estimators rely on Taylor-series
approximations or risk stationarity. These estimators also assume some degree
of differentiability – either of just the loss function [Yeh+18a] or both the
model and loss [KL17a, Pru+20a, Che+21a].

The exact analytical framework each gradient-based method employs depends on
the set of model parameters considered [HL22a]. – discussed first – estimate
the effect of retraining by studying gradients w.r.t. final model parameters
$\theta^{(T)}$. Obviously, a single set of model parameters provide limited
insight into the entire optimization landscape, meaning static methods
generally must make stronger assumptions. In contrast, reconstruct the
training data’s influence by studying model parameters throughout training,
e.g., ${\theta^{(0)},\ldots,\theta^{(T)}}$. Analyzing these intermediary model
parameters makes dynamic methods more computationally expensive in general,
but it enables dynamic methods to make fewer assumptions.

This section concludes with a discussion of a critical limitation common to
all existing gradient-based influence estimators – both static and dynamic.
This common weakness can cause gradient-based estimators to systematically
overlook highly influential (groups of) training instances.

###  5.1 Static, Gradient-Based Influence Estimation

As mentioned above, static estimators are so named because they measure
influence using only final model parameters $\theta^{(T)}$. Static estimators’
theoretical formulations assume (i.e., the model parameters have converged to
a risk minimizer) and .

Below we focus on two static estimators – [KL17a] and [Yeh+18a]. Each method
takes very different approaches to influence estimation with the former being
more general and the latter more scalable. Both estimators’ underlying
assumptions are generally violated in deep networks.

####  5.1.1 Influence Functions

Along with Shapley value (Sec. 4.3), [KL17a]’s [KL17a] is one of the best-
known influence estimators. The estimator derives its name from influence
functions (also known as [Jae72a]) in robust statistics [Ham74a]. These early
statistical analyses consider how a model changes if training instance
$z_{i}$’s weight is infinitesimally perturbed by ${\epsilon_{i}}$. More
formally, consider the change in the from

$\theta^{(T)}=\operatorname*{arg\,min}_{\theta}\frac{1}{n}\sum_{z\in\mathcal{D}}{\mathcal{L}(z;\theta)}$
(22)

to

$\theta^{(T)}_{+\epsilon_{i}}=\operatorname*{arg\,min}_{\theta}\frac{1}{n}\sum_{z\in\mathcal{D}}{\mathcal{L}(z;\theta)}+\epsilon_{i}{\mathcal{L}(z_{i};\theta)}\text{.}$
(23)

Under the assumption that model $f$ and loss function $\ell$ are twice-
differentiable and strictly convex, [CW82a] prove via a first-order Taylor
expansion that

$\frac{d\theta^{(T)}_{+\epsilon_{i}}}{d\epsilon_{i}}\Big{|}_{\epsilon_{i}=0}=-{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\text{,}$
(24)

where empirical risk Hessian
${H_{\theta}^{(T)}\coloneqq\frac{1}{n}\sum_{z\in\mathcal{D}}\nabla_{\theta}^{2}{\mathcal{L}(z;\theta^{(T)})}}$
is by assumption positive definite. [KL17a] extend [CW82a]’s result to
consider the effect of this infinitesimal perturbation on $z_{\text{te}}$’s
risk, where

$\displaystyle\frac{d{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}{d\epsilon_{i}}\Big{|}_{\epsilon_{i}=0}$
$\displaystyle=\frac{d{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}{d\theta^{(T)}_{+\epsilon_{i}}}^{\intercal}\frac{d\theta^{(T)}_{+\epsilon_{i}}}{d\epsilon_{i}}\Big{|}_{\epsilon_{i}=0}$
$\triangleright$ Chain rule (25)
$\displaystyle=-\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\text{.}$
(26)

Removing training instance $z_{i}$ from $\mathcal{D}$ is equivalent to
${\epsilon_{i}=-\frac{1}{n}}$ making the

${\widehat{\mathcal{I}}_{\textsc{IF}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\frac{1}{n}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\text{.}$
(27)

More intuitively, Eq. (27) is the influence functions’ estimate of the
leave/̄one/̄out influence of $z_{i}$ on $z_{\text{te}}$.

#####  5.1.1.1 Time, Space, and Storage Complexity

Calculating inverse Hessian ${(H_{\theta}^{(T)})^{-1}}$ directly requires
${\mathcal{O}(np^{2}+p^{3})}$ time and ${\mathcal{O}(p^{2})}$ space [KL17a].
For large models, this is clearly prohibitive. Rather than computing
${(H_{\theta}^{(T)})^{-1}}$ directly, [KL17a] instead estimate Hessian-vector
product (HVP)

$s_{\text{test}}\coloneqq{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}\text{,}$
(28)

with each training instance’s pointwise influence then

${\widehat{\mathcal{I}}_{\textsc{IF}}\left(z_{i},z_{\text{te}}\right)}=\frac{1}{n}s_{\text{test}}^{\intercal}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\text{.}$
(29)

[KL17a] use the stochastic algorithm of [Pea94a] and [ABH17a] to estimate
$s_{\text{test}}$. This reduces influence functions’ complexity to just
${\mathcal{O}(np)}$ time and ${\mathcal{O}(n+p)}$ space. Since
$s_{\text{test}}$ is specific to test instance $z_{\text{te}}$,
$s_{\text{test}}$ must be estimated for each test instance individually. This
increases influence functions’ computational cost but also means that
influence functions require no additional storage.

#####  5.1.1.2 Strengths and Weaknesses

Influence functions’ clear advantage over retraining-based methods is that
influence functions eliminate the need to retrain any models. Recall from
Table LABEL:tab:InfluenceEstimators:Comparison that retraining-based methods
have a high upfront complexity of retraining but low incremental complexity.
Influence functions invert this computational trade-off. While computing
$s_{\text{test}}$ can be slow (several hours for a single test instance
[Yeh+18a, Guo+21a, HL22a]), it is still significantly faster than retraining
${\mathcal{O}(n)}$ models. However, influence functions require that
$s_{\text{test}}$ is recalculated for each test instance. Hence, when a large
number of test instances need to be analyzed, retraining-based methods may
actually be faster than influence functions through amortization of the
retraining cost.

In addition, while influence functions can be very accurate on convex and some
shallow models, the assumption that Hessian $H_{\theta}^{(T)}$ is positive
definite often does not hold for deep models [BPF21a]. To ensure inverse
${(H_{\theta}^{(T)})^{-1}}$ exists, [KL17a] add a small dampening coefficient
to the matrix’s diagonal; this dampener is a user-specified hyperparameter
that is problematic to tune, since there may not be a ground-truth reference.
When this dampening hyperparameter is set too small, $s_{\text{test}}$
estimation can diverge [Yeh+18a, HNM19a, HL22a].

More generally, [BPF21a] show that training hyperparameters also significantly
affect influence functions’ performance. Specifically, [BPF21a] empirically
demonstrate that model initialization, model width, model depth, weight-decay
strength, and even the test instance being analyzed ($z_{\text{te}}$) all can
negatively affect influence functions’ LOO estimation accuracy. Their finding
is supported by the analysis of [ZZ22a] who show that HVP estimation’s
accuracy depends heavily on the model’s training regularizer with HVP accuracy
“pretty low under weak regularization.”

[Bae+22a] also empirically analyze the potential sources of influence
functions’ fragility on deep models. [Bae+22a] identify five common error
sources, the first three of which are the most important.161616[Bae+22a, Table
1 ] provide a formal mathematical definition of influence functions’ five
error sources.

  * •

Warm-start gap: Influence functions more closely resembles performing fine-
tuning close to final model parameters $\theta^{(T)}$ than retraining from
scratch (i.e., starting from initial parameters $\theta^{(0)}$). This
difference in starting conditions can have a significant effect on the LOO
estimate.

  * •

Proximity gap: The error introduced by the dampening term included in the HVP
($s_{\text{test}}$) estimation algorithm.

  * •

Non-convergence gap: The error due to final model parameters $\theta^{(T)}$
not being a stationary point, i.e.,
${\sum_{z_{i}\in\mathcal{D}}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\neq\vec{0}}$.

  * •

Linearization error: The error induced by considering only a first-order
Taylor approximation when deleting $z_{i}$ and ignoring the potential effects
of curvature on
${\widehat{\mathcal{I}}_{\textsc{IF}}\left(z_{i},z_{\text{te}}\right)}$
[BYF20a].

  * •

Solver error: General error introduced by the specific solver used to estimate
$s_{\text{test}}$.

Rather than estimating the LOO influence, [Bae+22a] argue that influence
functions more closely estimate a different measure they term the (PBRF).
[Bae+22a] provide the intuition that PBRF “approximates the effect of removing
a data point while trying to keep predictions consistent with the … trained
model” [Bae+22a]. Put simply, PBRF mimics a prediction-constrained LOO
influence.

[Bae+22a] assert that PBRF can be applied in many of the same situations where
LOO is useful. [Bae+22a] further argue that influence functions’ fragility
reported by earlier works [BPF21a, ZZ22a] is primarily due to those works
focusing on the “wrong question” of LOO. When the “right question” is posed
and influence functions are evaluated w.r.t. PBRF, influence functions give
accurate answers.

#####  5.1.1.3 Related Methods

Improving influence functions’ computational scalability has been a primary
focus of follow-on work. For instance, applying influence functions only to
the model’s final linear (classification) layer has been considered with at
best mixed results [BBD20a, Yeh+22a].171717Section 5.1.2.2 discusses some of
the pitfalls associated with estimating influence using only a model’s final
(linear) layer. Moreover, [Guo+21a]’s [Guo+21a] (FastIF) integrate multiple
speed-up heuristics. First, they leverage the inherent parallelizability of
[Pea94a]’s [Pea94a] HVP estimation algorithm. In addition, FastIF includes
recommended hyperparameters for [Pea94a]’s HVP algorithm that reduces its
execution time by 50% on average.

More recently, early results from [Sch+22a] show that influence functions can
be sped-up by three to four orders of magnitude by using a different algorithm
to estimate $s_{\text{test}}$. Specifically, [Sch+22a] use [Arn51a]’s [Arn51a]
famous algorithm that quickly finds the dominant (in absolute terms)
eigenvalues and eigenvectors of $H_{\theta}^{(T)}$. These dominant
eigenvectors serve as the basis when projecting all gradient vectors to a
lower-dimensional subspace. [Sch+22a] evaluate their revised influence
functions estimator on large transformer networks (e.g., ViT/̄L32 with 300M
parameters [Dos+21a]), which are orders of magnitude larger than the simple
networks [KL17a] consider.

Another approach to speed up influence functions is to specialize the
estimator to model architectures with favorable computational properties. For
example, [Sha+18c]’s [Sha+18c] LeafInfluence method adapts influence functions
to gradient boosted decision tree ensembles. By assuming a fixed tree
structure and then focusing only on the trees’ leaves, LeafInfluence’s tree-
based estimates are significantly faster than influence functions on deep
models [BHL22a].

A further major strength of influence functions is that it is one of the few
influence analysis methods that has been studied beyond the pointwise domain.
For example, [Koh+19a]’s [Koh+19a] follow-on paper analyzes influence
functions’ empirical performance estimating group influence. In particular,
[Koh+19a] consider coherent training data subpopulations whose removal is
expected to have a large, broad effect on the model. Even under naive
assumptions of (pointwise) influence additivity, [Koh+19a] observe that simply
summing influence functions estimates tends to underestimate the true group
influence. More formally, let ${D\subseteq\mathcal{D}}$ be a coherent
training-set subpopulation, then

$\sum_{z_{i}\in
D}{\big{\lvert}{\widehat{\mathcal{I}}_{\textsc{IF}}\left(z_{i},z_{\text{te}}\right)}\big{\rvert}}<{\big{\lvert}{\mathcal{I}\left(D,z_{\text{te}}\right)}\big{\rvert}}\text{.}$
(30)

Nonetheless, influence functions’ additive group estimates tend to have strong
rank correlation w.r.t. subpopulations’ true group influence. In addition,
[BYF20a] extend influence functions to directly account for subpopulation
group effects by considering higher-order terms in influence functions’
Taylor-series approximation.

####  5.1.2 Representer Point Methods

Unlike this section’s other gradient-based estimators, [Yeh+18a]’s [Yeh+18a]
method does not directly rely on a Taylor-based expansion. Instead, [Yeh+18a]
build on [SHS01a]’s [SHS01a] . The derivation below assumes that model $f$ is
linear. [Yeh+18a] use a simple “trick” to extend linear representer point
methods to multilayer models like neural networks.

Representer-based methods rely on , which are functions
${\mathcal{K}:\mathcal{X}\times\mathcal{X}\rightarrow}$ that measure the
similarity between two vectors [HSS08a]. [SHS01a]’s representer theorem proves
that the optimal solution to a class of $L_{2}$ regularized functions can be
reformulated as a weighted sum of the training data in kernel form. Put
simply, representer methods decompose the predictions of specific model
classes into the individual contributions (i.e., influence) of each training
instance. This makes influence estimation a natural application of the
representer theorem.

Consider regularized empirical risk minimization where optimal parameters
satisfy

$\theta^{*}\coloneqq\operatorname*{arg\,min}_{\theta}\frac{1}{n}\sum_{z_{i}\in\mathcal{D}}{\mathcal{L}(z_{i};\theta)}+\lambda\lVert\theta\rVert_{2}\text{,}$
(31)

with ${\lambda>0}$ the $L_{2}$ regularization strength. Note that Eq. (31)
defines minimizer $\theta^{*}$ slightly differently than the last section (22)
since the representer theorem requires regularization.

Empirical risk minimizers are meaning

$\nabla_{\theta}\bigg{(}\frac{1}{n}\sum_{z_{i}\in\mathcal{D}}{\mathcal{L}(z_{i};\theta^{*})}+\lambda\lVert\theta^{*}\rVert_{2}\bigg{)}=\vec{0}\text{,}$
(32)

where $\vec{0}$ is the $p$/̄dimensional, zero vector. The above simplifies to

$\displaystyle\frac{1}{n}\sum_{z_{i}\in\mathcal{D}}\frac{\partial{\mathcal{L}(z_{i};\theta^{*})}}{\partial\theta}+2\lambda\theta^{*}$
$\displaystyle=\vec{0}$ (33) $\displaystyle\theta^{*}$
$\displaystyle=-\frac{1}{2\lambda
n}\sum_{z_{i}\in\mathcal{D}}\frac{\partial{\mathcal{L}(z_{i};\theta^{*})}}{\partial\theta}\text{.}$
(34)

For a linear model where
${{f(x;\theta)}=\theta^{\intercal}x\eqqcolon\widehat{y}}$, Eq. (34) further
simplifies via the chain rule to

$\displaystyle\theta^{*}$ $\displaystyle=-\frac{1}{2\lambda
n}\sum_{(x_{i},y_{i})\in\mathcal{D}}\frac{\partial{\ell({f(x_{i};\theta^{*})},y_{i})}}{\partial\theta}$
(35) $\displaystyle=-\frac{1}{2\lambda
n}\sum_{(x_{i},y_{i})\in\mathcal{D}}\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}\,\frac{\partial\widehat{y}_{i}}{\partial\theta}$
$\triangleright$ Chain Rule (36) $\displaystyle=-\frac{1}{2\lambda
n}\sum_{(x_{i},y_{i})\in\mathcal{D}}\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}\,x_{i}$
$\triangleright$ $\widehat{y}=\theta^{\intercal}x$ (37)
$\displaystyle=\sum_{(x_{i},y_{i})\in\mathcal{D}}\alpha_{i}x_{i}\text{,}$ (38)

where $\ell$ is any once-differentiable loss function,
$\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}$ is the
gradient of just the loss function itself w.r.t. model output
$\widehat{y}$,181818In the case of classification,
$\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}$ has
$\lvert\mathcal{Y}\rvert$ dimensions, i.e., its dimension equals the number of
classes. and ${\alpha_{i}\coloneqq-\frac{1}{2\lambda
n}\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}}$ is the
$i$/̄th training instance’s . [Yeh+18a] provide the intuition that a larger
magnitude $\alpha_{i}$ indicates that training instance $z_{i}$ has larger
influence on the final model parameters $\theta^{*}$.

Following [SHS01a]’s [SHS01a] representer theorem kernelized notation, the
training set’s group influence on test instance $z_{\text{te}}$ for any linear
model is

${\mathcal{I}_{\textsc{RP}}\left(\mathcal{D},z_{\text{te}}\right)}=\sum_{i=1}^{n}\alpha_{i}x_{i}^{\intercal}x_{\text{te}}\,|_{y_{\text{te}}}=\sum_{i=1}^{n}{\mathcal{K}(x_{i},x_{\text{te}},\alpha_{i})\,|_{y_{\text{te}}}}=\sum_{i=1}^{n}{\mathcal{I}_{\textsc{RP}}\left(z_{i},z_{\text{te}}\right)}\text{,}$
(39)

where kernel function
${{\mathcal{K}(x_{i},x_{\text{te}},\alpha_{i})}\coloneqq\alpha_{i}x_{i}^{\intercal}x_{\text{te}}}$
returns a vector.
${{\mathcal{K}(x_{i},x_{\text{te}},\alpha_{i})\,|_{y_{\text{te}}}}}$ denotes
the kernel value’s $y_{\text{te}}$/̄th dimension. Then, $z_{i}$’s on
$z_{\text{te}}$ is

${\mathcal{I}_{\textsc{RP}}\left(z_{i},z_{\text{te}}\right)}=\alpha_{i}x_{i}^{\intercal}x_{\text{te}}\,|_{y_{\text{te}}}={\mathcal{K}(x_{i},x_{\text{te}},\alpha_{i})\,|_{y_{\text{te}}}}\text{.}$
(40)

Extending Representer Point to Multilayer Models Often, linear models are
insufficiently expressive, with multilayer models used instead. In such cases,
the representer theorem above does not directly apply. To workaround this
limitation, [Yeh+18a] rely on what they (later) term [Yeh+22a].

Formally, [Yeh+18a] partition the model parameters
${\theta^{(T)}=[\leavevmode\nobreak\ \dot{\theta}^{(T)}\leavevmode\nobreak\
\leavevmode\nobreak\ \ddot{\theta}^{(T)}\leavevmode\nobreak\ ]}$ into two
subsets, where $\ddot{\theta}^{(T)}$ is the last linear (i.e., classification)
layer’s parameters and
${\dot{\theta}^{(T)}\coloneqq\theta^{(T)}\setminus\ddot{\theta}^{(T)}}$ is all
other model parameters. Since $\ddot{\theta}^{(T)}$ is simply a linear
function, the representer theorem analysis above still applies to it.
[Yeh+18a] treat the other parameters, $\dot{\theta}^{(T)}$, as a fixed feature
extractor and ignore them in their influence analysis.

To use [Yeh+18a]’s [Yeh+18a] multilayer trick, one small change to Eq. (40) is
required. Obviously, in multilayer models, the final (linear) layer does not
operate over feature vectors $x_{i}$ and $x_{\text{te}}$ directly. Instead,
the final layer only sees an intermediate feature representation. For
arbitrary feature vector $x$, let $\mathbf{f}$ be the feature representation
generated by model parameters $\dot{\theta}^{(T)}$, i.e., vector $\mathbf{f}$
is the input to the model’s last linear layer given input $x$. Then the for a
multilayer model is

${\widehat{\mathcal{I}}_{\textsc{RP}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\alpha_{i}\mathbf{f}_{i}^{\intercal}\mathbf{f}_{\text{te}}\,|_{y_{\text{te}}}={\mathcal{K}(\mathbf{f}_{i},\mathbf{f}_{\text{te}},\alpha_{i})}\,|_{y_{\text{te}}}\text{.}$
(41)

#####  5.1.2.1 Time, Space, and Storage Complexity

Treating as constants feature representation dimension
$\lvert\mathbf{f}\rvert$ and the overhead to calculate
$\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}$,
estimating the entire training set’s representer point influence only requires
calculating $n$ dot products. This only takes ${\mathcal{O}(n)}$ time and
${\mathcal{O}(n+p)}$ space with no additional storage requirements.

#####  5.1.2.2 Strengths and Weaknesses

Representer point’s primary advantage is its theoretical and computational
simplicity. Eq. (41) only considers the training and test instances’ final
feature representations and loss function gradient
$\frac{\partial{\ell(\widehat{y}_{i},y_{i})}}{\partial\widehat{y}}$. Hence,
the majority of representer point’s computation is forward-pass only and can
be sped up using batching. This translates to representer point being very
fast – several orders of magnitude faster than influence functions and Section
5.2’s dynamic estimators [HL21a].

However, representer points’ simplicity comes at a cost. First, at the end of
training, it is uncommon that a model’s final linear layer has converged to a
stationary point. Before applying their method, [Yeh+18a] recommend freezing
all model layers except the final one (i.e., freezing $\dot{\theta}^{(T)}$)
and then fine-tuning the classification layer ($\ddot{\theta}^{(T)}$) until
convergence/stationarity. Without this extra fine-tuning, representer point’s
stationarity assumption does not hold, and poor influence estimation accuracy
is expected. Beyond just complicating the training procedure itself, this
extra training procedure also complicates comparison with other influence
methods since it may require evaluating the approaches on different
parameters.

Moreover, by focusing exclusively on the model’s final linear (classification)
layer, representer point methods may miss influential behavior that is clearly
visible in other layers. For example, [HL22a] demonstrate that while some
training-set attacks are clearly visible in a network’s final layer, other
attacks are only visible in a model’s first layer – despite both attacks
targeting the same model architecture and dataset. In their later paper,
[Yeh+22a] acknowledge the disadvantages of considering only the last layer
writing, “that choice critically affects the similarity component of data
influence and leads to inferior results”. [Yeh+22a] further state that the
feature representations in the final layer – and by extension representer
point’s influence estimates – can be “too reductive.”

In short, [Yeh+18a]’s [Yeh+18a] representer point method is highly scalable
and efficient but is only suitable to detect behaviors that are obvious in the
model’s final linear layer.

#####  5.1.2.3 Related Methods

Given the accuracy limitations of relying on last-layer similarity, limited
follow-on work has adapted representer-point methods. [BHL22a] extend
representer point methods to decision forests via their Tree-ensemble
Representer Point Examples (TREX) estimator. Specifically, they use – which
provide an encoding of a tree’s learned representation structure [DG14a,
He+14a] – for similarity comparison.

In addition, [SWS21a] propose (RPS/̄LJE), which can be viewed as a
generalizing [Yeh+18a]’s [Yeh+18a] base method. Rather than relying on
[SHS01a]’s [SHS01a] representer theorem, [SWS21a]’s formulation relies on a
first-order Taylor expansion that estimates the difference between the final
model parameters and a true stationary point. RPS/̄LJE still follows vanilla
representer point’s kernalized decomposition where
${{\widehat{\mathcal{I}}_{\textsc{RP}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\alpha_{i}\mathbf{f}_{i}^{\intercal}\mathbf{f}_{\text{te}}}$,
albeit with $\alpha_{i}$ defined differently.

RPS/̄LJE addresses two weaknesses of [Yeh+18a]’s [Yeh+18a] base approach.
First, [SWS21a]’s formulation does not presume that $\theta^{(T)}$ is a
stationary point. Therefore, RPS/̄LJE does not require post-training fine-
tuning to enforce stationarity. Second, as Section 5.3 discusses in detail,
gradient-based estimators, including vanilla representer point, tend to mark
as most influential those training instances with the largest loss values.
This leads to all test instances from a given class having near identical
top/̄k influence rankings. RPS/̄LJE’s alternate definition of $\alpha_{i}$ is
less influenced by a training instance’s loss value, which enables RPS/̄LJE to
generate more semantically meaningful influence rankings.

###  5.2 Dynamic, Gradient-Based Influence Estimation

All preceding influence methods – static, gradient-based and retraining-based
– define and estimate influence using only final model parameters,
$\theta^{(T)}_{D}$, where ${D\subseteq\mathcal{D}}$. These final parameters
only provide a snapshot into a training instance’s possible effect. Since
neural network training is NP-complete [BR92a], it can be provably difficult
to reconstruct how each training instance affected the training process.

As an intuition, an influence estimator that only considers the final model
parameters is akin to only reading the ending of a book. One might be able to
draw some big-picture insights, but the finer details of the story are most
likely lost. Applying a dynamic influence estimator is like reading a book
from beginning to end. By comprehending the whole influence “story,” dynamic
methods can observe training data relationships – both fine-grained and
general – that other estimators miss.

Since test instance $z_{\text{te}}$ may not be known before model training,
in-situ influence analysis may not be possible. Instead, as shown in Alg. 1,
intermediate model parameters
${\Theta\subseteq\\{\theta^{(0)},\ldots,\theta^{(T-1)}\\}}$ are stored during
training for post hoc influence analysis.191919In practice, only a subset of
$\\{\theta^{(0)},\ldots,\theta^{(T-1)}\\}$ is actually stored. Heuristics are
then applied to this subset to achieve acceptable influence estimation error
[Pru+20a, HL22a].

Below we examine two divergent approaches to dynamic influence estimation –
the first defines a novel definition of influence while the second estimates
leave/̄one/̄out influence with fewer assumptions than influence functions.

Algorithm 1 Dynamic influence estimation’s training phase

1:Training set $\mathcal{D}$; iteration count $T$; learning rates
${\eta^{(1)},\ldots,\eta^{(T)}}$; batch sizes ${b^{(1)},\ldots,b^{(T)}}$; and
initial parameters $\theta^{(0)}$

2:Final parameters $\theta^{(T)}$ and stored parameter set $\Theta$

3:$\Theta\leftarrow\emptyset$

4:for $t\leftarrow 1\textbf{ to }T$ do

5: $\Theta\leftarrow\Theta\cup\\{\theta^{(t-1)}\\}$ $\triangleright$ Store
intermediate params.

6: $\mathcal{B}^{(t)}\,\stackrel{{\scriptstyle b^{(t)}}}{{\sim}}\,\mathcal{D}$

7:
$\theta^{(t)}\leftarrow\textsc{Update}(\eta^{(t)},\theta^{(t-1)},\mathcal{B}^{(t)})$

8:return $\theta^{(T)}$, $\Theta$

####  5.2.1 TracIn – Tracing Gradient Descent

Fundamentally, all preceding methods define influence w.r.t. changes to the
training set. [Pru+20a] take an orthogonal perspective. They treat training
set $\mathcal{D}$ as fixed, and consider the change in model parameters as a
function of time, or more precisely, the training iterations.

Vacuously, the training set’s group influence on test instance $z_{\text{te}}$
is

${\mathcal{I}\left(\mathcal{D},z_{\text{te}}\right)}={\mathcal{L}(z_{\text{te}};\theta^{(0)})}-{\mathcal{L}(z_{\text{te}};\theta^{(T)})}\text{.}$
(42)

In words, training set $\mathcal{D}$ causes the entire change in test loss
between random initial parameters $\theta^{(0)}$ and final parameters
$\theta^{(T)}$. Eq. (42) decomposes by training iteration $t$ as

${\mathcal{I}\left(\mathcal{D},z_{\text{te}}\right)}=\sum_{t=1}^{T}\left({\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}-{\mathcal{L}(z_{\text{te}};\theta^{(t)})}\right)\text{.}$
(43)

Consider training a model with vanilla stochastic gradient descent, where each
training minibatch $\mathcal{B}^{(t)}$ is a single instance and gradient
updates have no momentum [RHW86a]. Here, each iteration $t$ has no effect on
any other iteration beyond the model parameters themselves. Combining this
with singleton batches enables attribution of each parameter change to a
single training instance, namely whichever instance was in
$\mathcal{B}^{(t)}$. Under this regime, [Pru+20a] define the as

${\mathcal{I}_{\text{TracIn{}}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\sum_{\begin{subarray}{c}t\\\
z_{i}=\mathcal{B}^{(t)}\end{subarray}}\left({\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}-{\mathcal{L}(z_{\text{te}};\theta^{(t)})}\right)\text{,}$
(44)

where the name “TracIn” derives from “tracing gradient descent influence.” Eq.
(43) under vanilla stochastic gradient descent decomposes into the sum of all
pointwise influences

${\mathcal{I}\left(\mathcal{D},z_{\text{te}}\right)}=\sum_{i=1}^{n}\Bigg{(}\sum_{\begin{subarray}{c}t\\\
z_{i}=\mathcal{B}^{(t)}\end{subarray}}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}-{\mathcal{L}(z_{\text{te}};\theta^{(t)})}\Bigg{)}=\sum_{i=1}^{n}{\mathcal{I}_{\text{TracIn{}}}\left(z_{i},z_{\text{te}}\right)}\text{.}$
(45)

While the ideal TracIn influence has a strong theoretical motivation, its
assumption of singleton batches and vanilla stochastic gradient descent is
unrealistic in practice. To achieve reasonable training times, modern models
train on batches of up to hundreds of thousands or millions of instances.
Training on a single instance at a time would be far too slow [YGG17a,
Goy+17a, Bro+20a].

A naive fix to Eq. (44) to support non-singleton batches assigns the same
influence to all instances in the minibatch, or more formally, divide the
change in loss
${{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}-{\mathcal{L}(z_{\text{te}};\theta^{(t)})}}$
by batch size $\lvert\mathcal{B}^{(t)}\rvert$ for each
${z_{i}\in\mathcal{B}^{(t)}}$. This naive approach does not differentiate
those instances in batch $\mathcal{B}^{(t)}$ that had positive influence on
the prediction from those that made the prediction worse.

Instead, [Pru+20a] estimate the contribution of each training instance within
a minibatch via a first-order Taylor approximation. Formally,

${\mathcal{L}(z_{\text{te}};\theta^{(t)})}\approx{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}+{{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}^{\intercal}\,(\theta^{(t)}-\theta^{(t-1)})}\text{.}$
(46)

Under gradient descent without momentum, the change in model parameters is
directly determined by the batch instances’ gradients, i.e.,

$\theta^{(t)}-\theta^{(t-1)}=-\frac{\eta^{(t)}}{\lvert\mathcal{B}^{(t)}\rvert}\sum_{z_{i}\in\mathcal{B}^{(t)}}{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}\text{,}$
(47)

where $\eta^{(t)}$ is iteration $t$’s learning rate.

Combining Eqs. (45) to (47), the is

${\widehat{\mathcal{I}}_{\text{TracIn{}}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\sum_{\begin{subarray}{c}t\\\
z_{i}\in\mathcal{B}^{(t)}\end{subarray}}\frac{\eta^{(t)}}{\lvert\mathcal{B}^{(t)}\rvert}\,{{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}^{\intercal}\,{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}}\text{,}$
(48)

with the complete TracIn influence estimation procedure shown in Alg. 2.

A More “Practical” TracIn Training’s stochasticity can negatively affect the
performance of both ideal TracIn (44) and the TracIn influence estimator (48).
As an intuition, consider when the training set contains two identical copies
of some instance. All preceding gradient-based methods assign those two
identical instances the same influence score. However, it is unlikely that
those two training instances will always appear together in the same
minibatch. Therefore, ideal TracIn almost certainly assigns these identical
training instances different influence scores. These assigned scores may even
be vastly different – by up to several orders of magnitude [HL22a]. This is
despite identical training instances always having the same expected TracIn
influence.

[Pru+20a] recognize randomness’s effect on TracIn and propose the (TracInCP)
as a “practical” alternative. Rather than retrace all of gradient descent,
TracInCP considers only a subset of the training iterations (i.e.,
checkpoints) ${\mathcal{T}\subseteq{[T]}}$. More importantly, at each
${t\in\mathcal{T}}$, all training instances are analyzed – not just those in
recent batches. Eq. (49) formalizes TracInCP, with its modified influence
estimation procedure shown in Alg. 3.

${\widehat{\mathcal{I}}_{\text{TracIn{}CP}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\sum_{t\in\mathcal{T}}\eta^{(t)}\,{{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}^{\intercal}\,{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}}$
(49)

Observe that, unlike TracIn, TracInCP assigns identical training instances the
same influence estimate. Therefore, TracInCP more closely estimates expected
influence than TracIn. [Pru+20a] use TracInCP over TracIn in much of their
empirical evaluation. Other work has also shown that TracInCP routinely
outperforms TracIn on many tasks [HL22a].

Algorithm 2 TracIn influence estimation

1:Training param. set $\Theta$; iteration count $T$; batches
${\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(T)}}$; learning rates
${\eta^{(1)},\ldots,\eta^{(T)}}$; training instance $z_{i}$; and test example
$z_{\text{te}}$

2:TracIn influence estimate
${\widehat{\mathcal{I}}_{\text{TracIn{}}}\left(z_{i},z_{\text{te}}\right)}$

3:$\widehat{\mathcal{I}}\leftarrow 0$

4:for $t\leftarrow 1\textbf{ to }T$ do

5: if ${z_{i}\in\mathcal{B}^{(t)}}$ then

6: ${\theta^{(t-1)}\leftarrow\Theta[t]}$

7:
$\widehat{\mathcal{I}}\leftarrow\widehat{\mathcal{I}}+\frac{\eta^{(t)}}{\lvert\mathcal{B}^{(t)}\rvert}{{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}^{\intercal}\,{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}}$

8:return $\widehat{\mathcal{I}}$

Algorithm 3 TracInCP influence estimation

1:Training param. set $\Theta$; iteration subset $\mathcal{T}$; learning rates
${\eta^{(1)},\ldots,\eta^{(T)}}$; training instance $z_{i}$; and test example
$z_{\text{te}}$

2:TracInCP influence est.
${\widehat{\mathcal{I}}_{\text{TracIn{}CP}}\left(z_{i},z_{\text{te}}\right)}$

3:$\widehat{\mathcal{I}}\leftarrow 0$

4:for each $t\in\mathcal{T}$ do

5: ${\theta^{(t-1)}\leftarrow\Theta[t]}$

6:
$\widehat{\mathcal{I}}\leftarrow\widehat{\mathcal{I}}+\eta^{(t)}{{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}^{\intercal}\,{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}}$

7:return $\widehat{\mathcal{I}}$

######  Remark 7:

[Pru+20a]’s empirical evaluation uses ${\lvert\mathcal{T}\rvert\ll T}$. For
example, when identifying mislabeled examples using TracInCP, [Pru+20a]
evaluate every 30th iteration. Furthermore, [Pru+20a] note that prioritizing
the small number of checkpoints where $z_{\text{te}}$’s loss changes
significantly generally outperforms evaluating a larger number of evenly-
spaced checkpoints.

#####  5.2.1.1 Time, Space, and Storage Complexity

Below we derive the time complexity of both versions of TracIn. We then
discuss their space and storage complexities.

Consider first TracInCP’s time complexity since it is simpler to derive. From
Alg. 3, each checkpoint in ${\mathcal{T}}$ requires $n$, $p$/̄dimensional dot
products making TracInCP’s complexity
${\mathcal{O}(np\lvert\mathcal{T}\rvert)}$. For vanilla TracIn, consider Alg.
2. For each iteration ${t\in{[T]}}$, a $p$/̄dimensional dot product is
performed for each instance in $\mathcal{B}^{(t)}$. Let
${b\coloneqq\max_{t}\lvert\mathcal{B}^{(t)}\rvert}$ denote the maximum batch
size, then TracIn’s time complexity is ${\mathcal{O}(bpT)}$. In the worst case
where ${\forall_{t}\,\mathcal{B}^{(t)}=\mathcal{D}}$ (full-batch gradient
descent), TracIn time complexity is ${\mathcal{O}(npT)}$.

Recall that, by definition, ${\lvert\mathcal{T}\rvert\leq T}$ meaning TracInCP
is asymptotically faster than TracIn. However, this is misleading. In
practice, TracInCP is generally slower than TracIn as [Pru+20a] note.

Since each gradient calculation is independent, TracIn and TracInCP are fully
parallelizable. Table LABEL:tab:InfluenceEstimators:Comparison treats the
level of concurrency as a constant factor, making the space complexity of both
TracIn and TracInCP ${\mathcal{O}(n+p)}$.

Lastly, as detailed in Alg. 1, dynamic influence estimators require that
intermediate model parameters $\Theta$ be saved during training for post hoc
influence estimation. In the worst case, each training iteration’s parameters
are stored resulting in a storage complexity of ${\mathcal{O}(pT)}$. In
practice however, TracIn only considers a small fraction of these $T$ training
parameter vectors, meaning TracIn’s actual storage complexity is generally
(much) lower than the worst case.

#####  5.2.1.2 Strengths and Weaknesses

TracIn and TracInCP avoid many of the primary pitfalls associated with static,
gradient-based estimators.

First, recall from Section 5.1.1 that Hessian-vector product $s_{\text{test}}$
significantly increases the computational overhead and potential inaccuracy of
influence functions. TracIn’s theoretical simplicity avoids the need to
compute any Hessian.

Second, representer point’s theoretical formulation necessitated considering
only a model’s final linear layer, at the risk of (significantly) worse
performance. TracIn has the flexibility to use only the final linear layer for
scenarios where that provides sufficient accuracy202020Last layer only TracIn
is also referred to as TracIn/̄Last. [Yeh+22a] evaluate TracIn/̄Last’s
effectiveness. as well as the option to use the full model gradient when
needed.

Third, by measuring influence during the training process, TracIn requires no
assumptions about stationarity or convergence. In fact, TracIn can be applied
to a model that is only partially trained. TracIn can also be used to study
when during training an instance is most influential. For example, TracIn can
identify whether a training instance is most influential early or late in
training.

Fourth, due to how gradient-based methods estimate influence, highly
influential instances can actually appear uninfluential at the end of
training. Unlike static estimators, dynamic methods like TracIn may still be
able to detect these instances. See Section 5.3 for more details.

In terms of weaknesses, TracIn’s theoretical motivation assumes stochastic
gradient descent without momentum. However, momentum and adaptive optimization
(e.g., Adam [KB15a]) significantly accelerate model convergence [Qia99a,
DHS11a, KB15a]. To align more closely with these sophisticated optimizers, Eq.
(48) and Alg. 2 would need to change significantly. For context, Section 5.2.2
details another dynamic estimator, HyDRA, which incorporates support for just
momentum with the resulting increase in estimator complexity substantial.

#####  5.2.1.3 Related Methods

TracIn has been adapted by numerous derivative/heuristic variants. For
example, is identical to vanilla TracIn except gradient vectors
${\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}$ and
${\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}$ only consider
the model’s final linear layer [Pru+20a]. This can make TracIn significantly
faster at the risk of (significantly) worse accuracy [Yeh+22a].

As a counter to the disadvantages of solely considering a model’s last
layer,212121See Section 5.1.2.2 for an extended discussion of last-layer
similarity. TracIn’s authors subsequently proposed (TracInWE), which targets
large language models and considers only the gradients in those models’ word
embedding layer [Yeh+22a]. Since language-model word embeddings can still be
very large (e.g., BERT/̄Base’s word embedding layer has 23M parameters
[Dev+19a]), the authors specifically use the gradients of only those tokens
that appear in both training instance $z_{i}$ and test instance
$z_{\text{te}}$.

[Pru+20a] also propose (TracInRP) – a low-memory version of TracIn that
provides unbiased estimates of $\widehat{\mathcal{I}}_{\text{TracIn{}}}$
(i.e., an estimate of an estimate). Intuitively, TracInRP maps gradient
vectors into a $d$/̄dimensional subspace (${d\ll p}$) via multiplication by a
${d\times p}$ random matrix where each entry is sampled i.i.d. from Gaussian
distribution ${\mathcal{N}\big{(}0,\frac{1}{d}\big{)}}$. These low-memory
gradient “sketches” are used in place of the full gradient vectors in Eq. (48)
[Woo14a]. TracInRP is primarily targeted at applications where $p$ is
sufficiently large that storing the full training set’s gradient vectors
(${\forall_{t,i}\leavevmode\nobreak\
{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}}$) is prohibitive.

Note also that TracIn can be applied to any iterative, gradient-based model,
including those that are non-parametric. For example, [BHL22a]’s [BHL22a]
adapts TracIn for gradient-boosted decision tree ensembles.

TracIn has also been used outside of supervised settings. For example, [KC21a]
apply TracIn to unsupervised learning, in particular density estimation; they
propose (VAE/̄TracIn), which quantifies the TracIn influence in $\beta$/̄VAEs
[Hig+17a]. Moreover, [Thi+22a]’s [Thi+22a] (TracInAD) functionally estimates
the distribution of influence estimates – using either TracInCP or
VAE/̄TracIn. TracInAD then marks as anomalous any test instance in the tail of
this “influence distribution”.

####  5.2.2 HyDRA – Hypergradient Data Relevance Analysis

Unlike TracIn which uses a novel definition of influence (44), [Che+21a]’s
[Che+21a] (HyDRA) estimates the leave/̄one/̄out influence (7). HyDRA leverages
the same Taylor series-based analysis as [KL17a]’s [KL17a] influence
functions. The key difference is that HyDRA addresses a fundamental mismatch
between influence functions’ assumptions and deep models.

Section 5.1.1 explains that influence functions consider infinitesimally
perturbing the weight of training sample $z_{i}$ by ${\epsilon_{i}}$. Recall
that the change in $z_{\text{te}}$’s test risk w.r.t. to this infinitesimal
perturbation is

$\frac{d{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}{d\epsilon_{i}}=\frac{\partial{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}{\partial\theta^{(T)}}^{\intercal}\,\frac{d\theta^{(T)}}{d\epsilon_{i}}=\frac{\partial{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}{\partial\theta^{(T)}}^{\intercal}\,\widetilde{h}^{(T)}_{i}$
(50)

where
${\widetilde{h}^{(T)}_{i}\coloneqq\frac{d\theta^{(T)}_{+\epsilon_{i}}}{d\epsilon_{i}}}$
denotes the $p$/̄dimensional of training instance $i$ at the end of training.

[KL17a]’s [KL17a] assumptions of differentiability and strict convexity mean
that Eq. (50) has a closed form. However, deep neural models are not convex.
Under non-convex gradient descent without momentum and with $L_{2}$
regularization, ${\theta^{(t)}\coloneqq\theta^{(t-1)}-\eta^{(t)}g^{(t-1)}}$
where gradient222222Eq. (51)’s definition of risk with weight decay is
slightly different than in Section 5.1.2 where ${2\lambda}$ is used. This
difference is done to align more closely with [Che+21a]’s [Che+21a] original
formulation.

$g^{(t-1)}\coloneqq\nabla_{\theta}{\mathcal{L}(\mathcal{B}^{(t)};\theta^{(t-1)})}+\lambda\theta^{(t-1)}\text{.}$
(51)

The exact definition of gradient $g^{(t-1)}$ depends on the specific contents
of batch $\mathcal{B}^{(t)}$ so for simplicity, we encapsulate the batch’s
contribution to the gradient using catch-all term
${\nabla_{\theta}{\mathcal{L}(\mathcal{B}^{(t)};\theta^{(t-1)})}}$.

Using Eq. (51), hypergradient $\widetilde{h}^{(T)}_{i}$ can be defined
recursively as

$\displaystyle\widetilde{h}^{(T)}_{i}\coloneqq\frac{d\theta^{(T)}_{+\epsilon_{i}}}{d\epsilon_{i}}$
$\displaystyle=\frac{d}{d\epsilon_{i}}\left(\theta^{(T-1)}_{+\epsilon_{i}}-\eta^{(t)}g^{(t-1)}\right)$
(52)
$\displaystyle=\widetilde{h}^{(T-1)}_{i}-\eta^{(T)}\frac{d}{d\epsilon_{i}}\left(\nabla_{\theta}{\mathcal{L}(\mathcal{B}^{(T)};\theta^{(T-1)}_{+\epsilon_{i}})}+\lambda\theta^{(T-1)}_{+\epsilon_{i}}\right)$
(53)
$\displaystyle=(1-\eta^{(T)}\lambda)\widetilde{h}^{(T-1)}_{i}-\eta^{(t)}\,\frac{d}{d\epsilon_{i}}\,\nabla_{\theta}{\mathcal{L}(\mathcal{B}^{(T)};\theta^{(T-1)}_{+\epsilon_{i}})}$
(54)

The recursive definition of hypergradient $\widetilde{h}^{(T)}_{i}$ needs to
be unrolled all the way back to initial parameters $\theta^{(0)}$.

The key takeaway from Eq. (54) is that training hypergradients affect the
model parameters throughout all of training. By assuming a convex model and
loss, [KL17a]’s [KL17a] simplified formulation ignores this very real effect.
As [Che+21a] observe, hypergradients often cause non-convex models to converge
to a vastly different risk minimizer. By considering the hypergradients’
cumulative effect, HyDRA can provide more accurate LOO estimates than
influence functions on non-convex models – albeit via a significantly more
complicated and computationally expensive formulation.

Unrolling Gradient Descent Hypergradients The exact procedure to unroll
HyDRA’s hypergradient $\widetilde{h}^{(T)}_{i}$ is non-trivial. For the
interested reader, supplemental Section C provides hypergradient unrolling’s
full derivation for vanilla gradient descent without momentum. Below, we
briefly summarize Section C’s important takeaways, and Section C’s full
derivation can be skipped with minimal loss of understanding.

At each training iteration, hypergradient unrolling requires estimating the
risk Hessian of each training instance in $\mathcal{B}^{(t)}$.232323For
clarity, this is not the inverse Hessian ${(H_{\theta}^{(T)})^{-1}}$ used by
influence functions. This significantly slows down HyDRA (by a factor of about
1,000$\times$ [Che+21a]). As a workaround, [Che+21a] propose treating these
risk Hessians as all zeros, proving that, under mild assumptions, the
approximation error of this simplified version of HyDRA is bounded. Alg. 4
shows without Hessians for vanilla gradient descent.242424See HyDRA’s original
paper [Che+21a] for the fast approximation algorithm with momentum. After
calculating the final hypergradient, substituting ${\widetilde{h}^{(T)}_{i}}$
into Eq. (50) with
${\epsilon_{i}=-\frac{1}{n}}$252525${\epsilon_{i}=-\frac{1}{n}}$ is equivalent
to deleting instance $z_{i}$ from the training set. Influence functions follow
the same procedure for $\epsilon_{i}$. See Eqs. (26) and (27). yields training
instance $z_{i}$’s

${\widehat{\mathcal{I}}_{\textsc{HyDRA}}\left(z_{i},z_{\text{te}}\right)}\coloneqq-\frac{1}{n}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}\,\widetilde{h}^{(T)}_{i}\text{.}$
(55)

Algorithm 4 Fast HyDRA influence estimation for gradient descent without
momentum

1:Training parameter set $\Theta$; final parameters $\theta^{(T)}$; training
set size $n$; iteration count $T$; batches
${\mathcal{B}^{(1)},\ldots,\mathcal{B}^{(T)}}$; learning rates
${\eta^{(1)},\ldots,\eta^{(T)}}$; weight decay $\lambda$; training instance
$z_{i}$; and test example $z_{\text{te}}$

2:HyDRA influence estimate
${\widehat{\mathcal{I}}_{\textsc{HyDRA}}\left(z_{i},z_{\text{te}}\right)}$

3:$\widetilde{h}^{(0)}_{i}\leftarrow\vec{0}$ $\triangleright$ Initialize to
zero vector

4:for $t\leftarrow 1\textbf{ to }T$ do

5: if ${z_{i}\in\mathcal{B}^{(t)}}$ then

6: ${\theta^{(t-1)}\leftarrow\Theta[t]}$

7:
$\widetilde{h}^{(t)}_{i}\leftarrow(1-\eta^{(t)}\lambda)\widetilde{h}^{(t-1)}_{i}-\frac{\eta^{(t)}n}{\lvert\mathcal{B}^{(t)}\rvert}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}$

8: else

9:
$\widetilde{h}^{(t)}_{i}\leftarrow(1-\eta^{(t)}\lambda)\widetilde{h}^{(t-1)}_{i}$

10:$\widehat{\mathcal{I}}\leftarrow-\frac{1}{n}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}\,\widetilde{h}^{(T)}_{i}$
$\triangleright$ Influence estimate

11:return $\widehat{\mathcal{I}}$

Relating HyDRA and TracIn When ${\lambda=0}$ or weight decay’s effects are
ignored (as done by TracIn), HyDRA’s fast approximation for vanilla gradient
descent simplifies to

$\displaystyle{\widehat{\mathcal{I}}_{\textsc{HyDRA}}\left(z_{i},z_{\text{te}}\right)}$
$\displaystyle\approx-\frac{1}{n}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}\sum_{\begin{subarray}{c}t\\\
z_{i}\in\mathcal{B}^{(t)}\end{subarray}}-\frac{\eta^{(t)}n}{\lvert\mathcal{B}^{(t)}\rvert}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}$
(56) $\displaystyle=\sum_{\begin{subarray}{c}t\\\
z_{i}\in\mathcal{B}^{(t)}\end{subarray}}\frac{\eta^{(t)}}{\lvert\mathcal{B}^{(t)}\rvert}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}$
(57)
$\displaystyle=\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}\sum_{\begin{subarray}{c}t\\\
z_{i}\in\mathcal{B}^{(t)}\end{subarray}}\frac{\eta^{(t)}}{\lvert\mathcal{B}^{(t)}\rvert}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}\text{.}$
(58)

Eq. (57) is very similar to TracIn’s definition in Eq. (48), despite the two
methods estimating different definitions of influence (LOO vs. ideal TracIn
(44)). The only difference between (57) and (48) is that HyDRA always uses
final test gradient
${\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}$ while TracIn uses
each iteration’s test gradient
${\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}$

The key takeaway is that while theoretically different, HyDRA and TracIn are
in practice very similar where HyDRA can be viewed as trading (incremental)
speed for lower precision w.r.t. $z_{\text{te}}$.

#####  5.2.2.1 Time, Space, and Storage Complexity

When unrolling the $T$ training iterations, HyDRA’s fast approximation
performs a $p$/̄dimensional (hyper)gradient calculation for each of the $n$
training instances. If HyDRA’s full version with Hessian vector products is
used, [ABH17a]’s [ABH17a] Hessian approximation algorithm estimates each HVP
in ${\mathcal{O}(p)}$ time and space. Therefore, the fast and standard
versions of HyDRA both have full time complexity ${\mathcal{O}(npT)}$ – same
as TracIn, albeit with potentially much worse constant factors.

Observe that each hypergradient $\widetilde{h}^{(T)}_{i}$ only needs to be
computed once and can be reused for each test instance. Therefore, the fast
and standard version of HyDRA have incremental time complexity of just $n$
gradient dot products – ${\mathcal{O}(np)}$ complexity total. This incremental
complexity is much faster than TracIn and asymptotically equivalent to
influence functions. In practice though, HyDRA’s incremental cost is much
lower than that of influence functions.

Alg. 4 requires storing vector $\widetilde{h}^{(t)}_{i}$ throughout HyDRA’s
entire unrolling procedure, where each training instance’s hypergradient takes
${\mathcal{O}(p)}$ space. To analyze all training instances simultaneously,
HyDRA requires ${\mathcal{O}(np)}$ total space. In contrast, TracIn only
requires ${\mathcal{O}(n+p)}$ space to analyze all instances simultaneously.
This difference is substantial for large models and training sets. In cases
where the fully-parallelized space complexity is prohibitive, each training
instance’s hypergradient can be analyzed separately resulting in a reduced
space complexity of ${\mathcal{O}(p)}$ for both fast and standard HyDRA.

Like TracIn, HyDRA requires storing model parameters
${\Theta\subseteq\\{\theta^{(0)},\ldots,\theta^{(T-1)}\\}}$ making its minimum
storage complexity ${\mathcal{O}(pT)}$. Since hypergradients are reused for
each test instance, they can be stored to eliminate the need to recalculate
them; this introduces an additional storage complexity of ${\mathcal{O}(np)}$.
This makes HyDRA’s total storage complexity ${\mathcal{O}(pT+np)}$.

######  Remark 8:

Storing both the training checkpoints and hypergradients is unnecessary. Once
all hypergradients have been calculated, serialized training parameters
$\Theta$ are no longer needed and can be discarded. Therefore, a more typical
storage complexity is ${\mathcal{O}(pT)}$ or ${\mathcal{O}(np)}$ – both of
which are still substantial.

#####  5.2.2.2 Strengths and Weaknesses

HyDRA and TracIn share many of the same strengths. For example, HyDRA does not
require assumptions of convexity or stationarity. Moreover, as a dynamic
method, HyDRA may be able to detect influential examples that are missed by
static methods – in particular when those instances have low loss at the end
of training (see Section 5.3 for more discussion).

HyDRA also has some advantages over TracIn. For example, as shown in Alg. 2,
TracIn requires that each test instance be retraced through the entire
training process. This significantly increases TracIn’s incremental time
complexity. In contrast, HyDRA only unrolls gradient descent for the training
instances, i.e., not the test instances. Hypergradient unrolling is a one-time
cost for each training instance; this upfront cost is amortized over all test
instances. Once the hypergradients have been calculated, HyDRA is much faster
than TracIn – potentially by orders of magnitude. In addition, HyDRA’s overall
design allows it to natively support momentum with few additional changes.
Integrating momentum into TracIn, while theoretically possible, requires
substantial algorithmic changes and makes TracIn substantially more
complicated. This would mitigate a core strength of TracIn – its simplicity.

HyDRA does have two weaknesses in comparison to TracIn. First, HyDRA’s
standard (i.e., non-fast) algorithm requires calculating many HVPs. Second,
HyDRA’s ${\mathcal{O}(np)}$ space complexity is much larger than the
${\mathcal{O}(n+p)}$ space complexity of other influence analysis methods (see
Table LABEL:tab:InfluenceEstimators:Comparison). For large models, this
significantly worse space complexity may be prohibitive.

#####  5.2.2.3 Related Methods

The method most closely related to HyDRA is [HNM19a]’s [HNM19a] . Both
approaches estimate the leave/̄one/̄out influence by unrolling gradient
descent using empirical risk Hessians. There are, however, a few key
differences. First, unlike HyDRA, [HNM19a] assume that the model and loss
function are convex. Next, SGD/̄influence primarily applies unrolling to
quantify the Cook’s distance,
${\theta^{(T)}-{\theta^{(T)}_{\mathcal{D}^{\setminus i}}}}$. To better align
their approach with dataset influence, [HNM19a] propose a surrogate (linear)
influence estimator which they incrementally update throughout unrolling. This
means the full training process must be unrolled for each test instance
individually, significantly increasing SGD-influence’s incremental time
complexity.

[Ter+21a] adapt the ideas of SGD-influence to estimate training data influence
in generative adversarial networks (GANs).

Although proposed exclusively in the context of influence functions (Sec.
5.1.1.3), [Sch+22a]’s [Sch+22a] basic approach to scale up influence functions
via faster Hessian calculation could similarly be applied to speed up HyDRA’s
standard (non-fast) algorithm.

###  5.3 Trade-off between Gradient Magnitude and Direction

This section details a limitation common to existing gradient-based influence
estimators that can cause these estimators to systematically overlook highly
influential (groups of) training instances.

Observe that all gradient-based methods in this section rely on some vector
dot product. For a dot product to be large, one of two criteria must be met:

(1) The vector directions align (i.e., have high cosine similarity). More
specifically, for influence analysis, vectors pointing in similar directions
are expected to encode similar information. This is the ideal case.

(2) Either vector has a large magnitude, e.g.,
$\lVert\nabla_{\theta}{\mathcal{L}(z;\theta)}\rVert$. Large gradient
magnitudes can occur for many reasons, but the most common cause is that the
instance is either incorrectly or not confidently predicted.

Across the training set, gradient magnitudes can vary by several orders of
magnitude [SWS21a]. To overcome such a magnitude imbalance, training instances
that actually influence a specific prediction may need to have orders of
magnitude better vector alignment. In reality, what commonly happens is that
incorrectly predicted or abnormal training instances appear highly influential
to all test instances [SWS21a]. [BBD20a] describe such training instances as .
However, globally influential training instances provide very limited insight
into individual model predictions. As [BBD20a] note, training instances are
generally much more relevant and insightful when analyzing specific
predictions.

To yield a more semantically meaningful influence ranking, [BBD20a] propose
the (RelatIF), which normalizes [KL17a]’s [KL17a] influence functions’
estimator by HVP magnitude
${\big{\lVert}{(H_{\theta}^{(T)})^{-1}}\,\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\big{\rVert}}$.262626Note
that this HVP is different than
${s_{\text{test}}\coloneqq{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}}$
in Eq. (28). Formally,

${\widehat{\mathcal{I}}_{\text{RelatIF}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\frac{{\widehat{\mathcal{I}}_{\textsc{IF}}\left(z_{i},z_{\text{te}}\right)}}{\lVert{(H_{\theta}^{(T)})^{-1}}\,\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\rVert}=\frac{1}{n}\,\frac{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}}{\lVert{(H_{\theta}^{(T)})^{-1}}\,\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\rVert}\text{.}$
(59)

RelatIF’s normalization inhibits training gradient magnitude
${\big{\lVert}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\big{\rVert}}$
dominating the influence estimate.

RelatIF’s biggest limitation is the need to estimate an HVP for every training
instance. As discussed in Section 5.1.1.2, HVP estimation is expensive and
often highly inaccurate in deep models. To work around these issues in their
evaluation of RelatIF, [BBD20a] use either very small neural models or just
consider a large model’s final layer, both of which can be problematic.

[HL22a] make a similar observation as [BBD20a] but motivate it differently. By
the chain rule, gradient vectors decompose as

$\nabla_{\theta}{\mathcal{L}(z;\theta)}\coloneqq\frac{\partial{\ell({f(x;\theta)},y)}}{\partial\theta}=\frac{\partial{\ell({f(x;\theta)},y)}}{\partial{f(x;\theta)}}\,\frac{\partial{f(x;\theta)}}{\partial\theta}\text{.}$
(60)

[HL22a] note that for many common loss functions (e.g., squared, binary cross-
entropy), loss value ${\ell({f(x;\theta)},y)}$ induces a strict ordering over
loss norm
$\big{\lVert}\frac{\partial{\ell({f(x;\theta)},y)}}{\partial{f(x;\theta)}}\big{\rVert}$.
[HL22a] term this phenomenon a , where confidently predicted training
instances have smaller gradient magnitudes and by consequence consistently
appear uninfluential to gradient-based influence estimators.

To account for the low-loss penalty, [HL22a] propose which replaces all
gradient vectors – both training and test – in an influence estimator with the
corresponding . Renormalization can be applied to any gradient-based
estimator. For example, [HL22a] observe that renormalized TracInCP, which they
term (GAS),

${\widehat{\mathcal{I}}_{\textsc{GAS}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\sum_{t\in\mathcal{T}}\eta^{(t)}\,\frac{{{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}^{\intercal}\,{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}}}{\lVert{\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(t-1)})}}\rVert\,\lVert{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(t-1)})}}\rVert}\text{,}$
(61)

is particularly effective at generating influence rankings. [HL22a] also
provide a renormalized version of influence functions,

${\widehat{\mathcal{I}}_{\text{RenormIF}}\left(z_{i},z_{\text{te}}\right)}\coloneqq\frac{{\widehat{\mathcal{I}}_{\textsc{IF}}\left(z_{i},z_{\text{te}}\right)}}{\lVert\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\rVert}=\frac{1}{n}\,\frac{\nabla_{\theta}{\mathcal{L}(z_{\text{te}};\theta^{(T)})}^{\intercal}{(H_{\theta}^{(T)})^{-1}}\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}}{\lVert\nabla_{\theta}{\mathcal{L}(z_{i};\theta^{(T)})}\rVert}\text{.}$
(62)

Since renormalized influence functions do not require estimating additional
HVPs, it is considerably faster than RelatIF. Renormalized influence functions
also do not have the additional error associated with estimating RelatIF’s
additional HVPs.272727[HL22a] also provide renormalized versions of
representer point and TracIn, which are omitted here.

This section should not be interpreted to mean that gradient magnitude is
unimportant for influence analysis. On the contrary, gradient magnitude has a
significant effect on training. However, the approximations made by existing
influence estimators often overemphasize gradient magnitude leading to
influence rankings that are not semantically meaningful.

######  Remark 9:

[BBD20a]’s RelatIF and [HL22a]’s renormalization do not change the
corresponding influence estimators’ time and space complexities.

##  6 Applications of Influence Analysis

This section briefly reviews different settings where influence analysis has
been applied. We focus on higher-level learning tasks as opposed to the
specific application environments where influence analysis has been used
including: toxic speech detection [HT21a], social network graph labeling
[Zha+21e], user engagement detection [LLY21a], medical imaging annotation
[Bra+22a], etc.

First, aims to improve a machine learning model’s overall performance by
removing “bad” training data. These “bad” instances arise due to disparate
non-malicious causes including human/algorithmic labeling error, non-
representative instances, noisy features, missing features, etc. [Kri+16a,
LDG18a, KW19a]. Intuitively, “bad” training instances are generally anomalous,
and their features clash with the feature distribution of typical “clean” data
[Woj+16a]. In practice, overparameterized neural networks commonly memorize
these “bad” instances to achieve zero training loss [HNM19a, FZ20a, Pru+20a,
Thi+22a]. As explained in Section 3.2, memorization can be viewed as the
influence of a training instance on itself. Therefore, influence analysis can
be used to detect these highly memorized training instances. These memorized
“bad” instances are then either removed from the training data or simply
relabeled [KSH22a] and the model retrained.

craft malicious training instances that manipulate a model to align with some
attacker objective. For example, a company may attempt to trick a spam filter
so all emails sent by a competitor are erroneously classified as spam
[Sha+18b]. Obviously, only influential (malicious) training instances affect a
model’s prediction. Some training set attacks rely on influence analysis to
craft better (i.e., more influential) poison instances [FGL20a, Jag+21a,
Oh+22a]. Since most training set attacks do not assume the adversary knows
training’s random seed or even necessarily the target model’s architecture,
poison instances are crafted to maximize their expected group influence
[Che+17a].

Influence and memorization analysis have also been used to improve , where the
adversary attempts to extract sensitive training data provided only a
pretrained (language) model [Dem+19a, CG22a].

detect and mitigate poisoning and backdoor attacks [Li+22a]. Since malicious
training instances must be influential to achieve the attacker’s objective,
defending against adversarial attacks reduces to identifying abnormally
influential training instances. If attackers are constrained in the number of
training instances they can insert [Wal+21a], the target of a training set
attack can be identified by searching for test instances that have a few
exceptionally influential training instances [HL22a]. The training set attack
mitigation removes these anomalously influential instances from the training
data and then retrains the model [Wan+19a]. In addition, influence estimation
has been applied to the related task of , where the training set is pristine
and only test instances are perturbed [CSG20a].

promotes techniques that enable machine learning models to make decisions free
of prejudices and biases based on inherited characteristics such as race,
religion, and gender [Meh+21a]. A classic example of model unfairness is the
COMPAS software tool, which estimated the recidivism risk of incarcerated
individuals. COMPAS was shown to be biased against black defendants, falsely
flagging them as future criminals at twice the rate of white defendants
[Ang+16a]. Widespread adoption of algorithmic decision making in domains
critical to human safety and well-being is predicated on the public’s
perception and understanding of the algorithms’ inherent ethical principles
and fairness [Awa+18a]. Yet, how to quantify the extent to which an algorithm
is “fair” remains an area of active study [Dwo+12a, GH19a, Sax+19a]. [BF21a]
propose as a measure of a prediction’s fairness. Intuitively, when a model’s
decision (e.g., not granting a loan, hiring an employee) is fundamentally
changed by the inclusion of a single instance in a large training set, such a
decision may be viewed as unfair or even capricious. Leave-one-out influence
is therefore useful to measure and improve a model’s robustness and fairness.

attempts to make a black-box model’s decisions understandable by humans
[BH21a]. Transparent explanations are critical to achieving user trust of and
satisfaction with ML systems [LDA09a, Kiz16a, Zho+19a]. communicate why a
model made a particular prediction via visual examples [CJH19a, SWS21a] –
e.g., training images – as social science research has shown that humans can
understand complex ideas using only examples [RHS09a, Ren14a]. Influence
estimation can assist in the selection of canonical training instances that
are particularly important for a given class in general or a single test
prediction specifically. Similarly, – which collectively establish a
“standard” for a given class [CJH19a] – can be selected from those training
instances with the highest average influence on a held-out validation set. In
cases where a test instance is misclassified, influence analysis can identify
those training instances that most influenced the misprediction.

reduces the computational requirements of large datasets by training models
using only a subset of the training data [TB18a]. Existing work has shown that
high-quality training subsets can be created by greedily selecting training
instances based on their overall influence [Kha+18a, Wan+20a]. Under mild
assumptions, [Wan+20a] even show that, in expectation, influence-based
subsampling performs at least as well as training on the full training set.

Annotating unlabeled data can be expensive – in particular for domains like
medical imaging where the annotators must be domain experts [Bra+22a].
Compared to labeling instances u.a.r., reduces labeling costs by prioritizing
annotation of particularly salient unlabeled data. In practice, active
learning often simplifies to maximizing the where each unlabeled instance’s
marginal influence must be estimated. Obviously, retraining for each possible
unlabeled instance combination has exponential complexity and is intractable.
Instead, a greedy strategy can be used where the influence of each unlabeled
instance is estimated to identify the next candidate to label [Liu+21a,
Jia+21b, Zha+21e].

To enhance the benefit of limited labeled data, influence analysis has been
used to create better augmented training data [Lee+20a, Oh+21a]. These
influence-guided methods outperform traditional random augmentations, albeit
with a higher computational cost.

##  7 Future Directions

The trend of consistently increasing model complexity and opacity will likely
continue for the foreseeable future. Simultaneously, there are increased
societal and regulatory demands for algorithmic transparency and
explainability. Influence analysis sits at the nexus of these competing
trajectories [Zho+19a], which points to the field growing in importance and
relevance. This section identifies important directions we believe influence
analysis research should take going forward.

Emphasizing Group Influence over Pointwise Influence: Most existing methods
target pointwise influence, which apportions credit for a prediction to
training instances individually. However, for overparameterized models trained
on large datasets, only the tails of the data distribution are heavily
influenced by an individual instance [Fel20a]. Instead, most predictions are
moderately influenced by multiple training instances working in concert
[FZ20a, Das+21a, BYF20a].

As an additional complicating factor, pointwise influence within data-
distribution modes is often approximately where the marginal effect of a
training instance’s deletion increases as more instances from a group are
removed [HL22a]. This makes pointwise influence a particularly poor choice for
understanding most model behavior. To date, very limited work has
systematically studied group influence [Koh+19a, BYF20a, HL22a]. Better group
influence estimators could be immediately applied in various domains such as
poisoning attacks, core-set selection, and model explainability.

Certified Influence Estimation: Certified defenses against poisoning and
backdoor attacks guarantee that deleting a fixed number of instances from the
training data will not change a model’s prediction [SKL17a, LF21a, Jia+22a,
WLF22a, HL23a]. These methods can be viewed as upper bounding the training
data’s group influence – albeit very coarsely. Most certified poisoning